(Presque) toutes les solutions mènent à l'optimum : atteignabilité de l'optimum global par les algorithmes de descente

Dans ce travail, nous mesurons l\u27impact de la solution initiale sur une recherche locale basique de type descente et basée sur la stratégie du premier améliorant. Il s\u27agit de calculer la couverture de certaines solutions de l\u27espace de recherche, que nous définissons comme la proportion de l\u27espace depuis laquelle une solution particulière peut être atteinte par une descente stricte avec une probabilité non nulle. Nous présentons ici une étude expérimentale réalisée sur les NK-landscapes, sur lesquels la dimension et la rugosité du paysage peut être contrôlée. Bien souvent, les algorithmes de descentes sont vus comme des algorithmes de recherche rapides mais trop dépendants de la solution initiale car n\u27offrant pas suffisamment de diversité pour explorer de grands espaces de recherche. Les études exactes réalisées montrent au contraire que la couverture de l\u27optimum global est généralement très élevée, ce qui signifie qu\u27une descente stricte de type premier améliorant peut mener à l\u27optimum global à partir de la plupart des solutions de l\u27espace de recherche. De plus, les études montrent que ces descentes atteignent avec une plus grande probabilité les optimums locaux de bonne qualité, ce qui est cohérent avec le fait qu\u27ils sont généralement associés à de plus grands bassins d\u27attraction. En conclusion, les résultats confirment qu\u27il est plus important de choisir une stratégie de recherche efficace plutôt que de se préoccuper du choix et des propriétés des solutions initiales. Ceci conduit à relativiser, du moins sur ce type de paysages, l\u27apport des techniques de perturbation sophistiquées au sein de recherches locales itérées. Cette étude, effectuée sur les NK-landscapes, pourrait être étendue pour comparaison à des paysages issus de problèmes combinatoires académiques