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

International audienceDans ce travail, nous mesurons l'impact 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'agit de calculer la couverture de certaines solutions de l'espace de recherche, que nous définissons comme la proportion de l'espace 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'offrant 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'optimum global est généralement très élevée, ce qui signifie qu'une descente stricte de type premier améliorant peut mener à l'optimum global à partir de la plupart des solutions de l'espace 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'ils sont généralement associés à de plus grands bassins d'attraction. En conclusion, les résultats confirment qu'il 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'apport 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.