Search

International audience; In this paper, we aim at evaluating the impact of the starting point of a basic local search based on the first improvement strategy. We define the coverage rate of a configuration as the proportion of the search space from which a particular configuration can be reached by a strict hill-climbling with a non-zero probability. In particular, we compute the coverage rate of fitness landscapes global optima, in order to evaluate their attainability by hill-climbing algorithms. The experimental study is realized on NK landscapes, in which the size and ruggedness can be controlled. Results indicate that the coverage rate of global optima is usually high, which means that a basic strictly improving hill-climbing with first improvement strategy is able to reach global optima, independently to the starting point considered.This confirms that it is more important to focus on an effective search strategy rather than worrying about the choice of the initial configurations.&nbsp

Lorsque l’on cherche à résoudre des problèmes d’optimisation combinatoire difficiles, trouver une solution optimale par les méthodes complètes peut s’avérer impraticable. Dans un tel contexte, on peut déterminer des solutions approchées grâce à l’utilisation d’heuristiques. Parmi elles, les métaheuristiques sont une forme générique d’algorithmes approchés facilement applicables à une large gamme de problèmes.Nos travaux de recherche sur les métaheuristiques cherchent à s’abstraire au maximum des spécificités des problèmes d’optimisation en les modélisant notamment sous forme de paysages de recherche à explorer. Cette abstraction, proposée en 1932 en biologie pour modéliser la relation entre génotype des individus et chances de reproduction, a été reprise plus récemment en optimisation combinatoire afin de mettre en relation la qualité des solutions avec les valeurs prises par les variables de décision. Dans ce contexte, nous avons étudié principalement la résolution de problèmes d’optimisation par les algorithmes de recherche locale.En optimisation mono-objectif, l’étude des climbers classiques de la littérature combinée avec l’analyse de la structure des paysages de recherche nous a permis d’obtenir des résultats parfois à contre-courant de ce qui est fait usuellement dans la communauté. Grâce à ces observations, nous nous sommes proposé d’étudier des stratégies originales pour ces algorithmes de recherche. Les résultats obtenus permettent d’entrevoir des perspectives de recherche importantes dans ce domaine.En optimisation multiobjectif, nous avons proposé des algorithmes de type recherche locale basés sur la notion d’indicateur de qualité. Ces algorithmes, en plus d’être génériques, se sont montrés efficaces sur divers types de problèmes tout en étant peu sensibles au paramétrage. L’utilisation d’indicateurs de qualité permet de surcroît de reformuler les problèmes d’optimisation multiobjectif sous forme de problèmes d’optimisation mono-objectif sur des ensembles et ainsi ouvrir diverses perspectives de recherche.

International audience; Despite the huge number of studies in the metaheuristic field, it remains difficult to understand the relative impact of their elementary components. A major aspect determining the general efficiency of metaheuristics resides in the way to exploit a neighborhood structure to move within a search space. In particular, the study of iterative improvement neighborhood searches (climbers) provides guidelines to better understand local searches behavior. Several studies clearly state that some climbing strategies are more suited than classical best and first improvement, on which most local searches are based. Here, we are interested in determining empirically climbing strategies that allow the attainment of high quality local optima. First, we study alternative move selection criteria that globally outperform best and first improvement. Unfortunately, these strategies are time-consuming and consequently reduce their possibilities of integration into advanced metaheuristics. Then, we investigate ways to reduce their computational cost by approximation. Empirical studies on NK landscapes allow the identification of move criteria that offer good tradeoffs between the quality of the local optima attained and the computational time needed to reach them.

National audience

National audience

National audience

International audience; Within local search algorithms, descent methods are rarely studied experimentally. However,these search techniques are the basis of many modern metaheuristics and have an influence on theability of an algorithm to achieve good solutions of a fitness landscape. Through a large empirical studyof classic runs, we show that certain ideas about descents methods are false. These results indicatethat it is possible to make a descent ’intelligent’ and lead to better solutions, regardless of the problemaddressed.

International audience

International audience; Au sein des algorithmes de recherche locale, les méthodes de descente font rarement l'objet d'études expérimentales dédiées. Cependant, ces techniques de recherche sont à la base d'un grand nombre de métaheuristiques modernes et peuvent avoir une influence non négligeable quant à la capacité d'un algorithme à atteindre de bonnes solutions de l'espace de recherche. L'an passé, nous avons comparé des descentes basées sur différentes règles pivot (premier ou meilleur améliorant) et différentes politiques de gestion de la neutralité (descente stricte, stochastique, ou stricte avec perturbations neutres), puis comparé empiriquement leur efficacité sur des paysages de recherche de type NK-landscapes, de différentes tailles et enregistrant différents niveaux de rugosité et de neutralité. Nous étendons cette année cette étude à des paysages de recherche issus de problèmes combinatoires académiques (MAXSAT, QAP, Flow-shop), après avoir introduit des indicateurs de caractérisation des paysages de recherche. Dans une large étude expérimentale, nous montrons que la stratégie du meilleur améliorant est plus efficace sur les paysages lisses et/ou de petites tailles mais est rapidement dominée par la stratégie du premier améliorant sur les paysages plus rugueux et/ou plus grands. Parallèlement, nous indiquons que la descente stochastique, qui accepte indifféremment des voisins neutres tout au long de la recherche (même avant d'avoir atteint un optimum local), permet non seulement une convergence plus rapide de la recherche, mais surtout d'atteindre la plupart du temps des optimums locaux de meilleure qualité. Enfin, une étude sur les NKr-landscapes montre que la création artificielle de plateaux (en arrondissant les valeurs fitness), permet d'atteindre de bien meilleures solutions qu'à partir du paysage originel. En effet, lisser la fonction d'évaluation permet d'éviter d'être piégé trop tôt dans des optimums locaux.

National audience

International audience; Climbers constitute a central component of modern heuristics, including metaheuristics, hybrid metaheuristics and hyperheuristics. Several important questions arise while designing a climber, and choices are often arbitrary, intuitive or experimentally decided. The paper provides guidelines to design climbers considering a landscape shape under study. In particular, we aim at competing best improvement and first improvement strategies, as well as evaluating the behavior of different neutral move policies. Some conclusions are assessed by an empirical analysis on a large variety of landscapes. This leads us to use the NK-landscapes family, which allows to define landscapes of different size, rugosity and neutrality levels. Experiments show the ability of first improvement to explore rugged landscapes, as well as the interest of accepting neutral moves at each step of the search. Moreover, we point out that reducing the precision of a fitness function could help to optimize problems.

Date du colloque: 04/2012; National audience

Date du colloque: 2010; National audience

Date du colloque: 10/2010; International audience