Breakout local search pour les problèmes d'optimisation difficiles
Institution:
AngersDisciplines:
Directors:
Abstract EN:
Due to the inherent computational complexity of hard combinatorial optimization prob- lems, the last several decades have seen a surge of interest in using heuristic algorithms to tackle this class of problems. While some of the heuristic methods are problem-specific, others are problem-independent since they ma1‹e few or no assumption about the problem being optimized. Examples of modern problem-independent heuristics are neighborhood search methods like tabu search, iterated local search, or simulated annealing, and biolog- ically inspired methods such as evolutionary algorithms or ant colony optimization. This work is dedicated to the elaboration of a problem-independent heuristic method, named Breakout Local Search (BLS), which can be considered as a combination of several well- established metaheuristic methods. BLS is a variant of iterated local search approach, since its basic idea of to use local search to discover local optima and to employ adaptive diversification strategies to continually move from one local optimum to another in the search space. Based on the information on the state of search, the perturbation strat- egy of BLS introduces a varying degree of diversification by dynamically determining the number of moves for perturbation and by adaptively selecting between several types of dedicated moves. So far, we have tested BLS on a number of classical combinatorial op- timization problems including maximum clique problems (both weighted and unweighted cases), quadratic assignment, graph partitioning, maximum cut and maximum sum col- oring problems. Compared to the current state-of-art algorithms from the literature, the proposed method shows remarkable performance on these problems. For a significant num- ber of instances of maximum weight clique, maximum cut and graph partitioning, as well as for several smaller in9tances of minimum sum coloring problem, our BLS method is even able to attain new record-breaking results. To further improve the performance on graph partitioning and quadratic assignment problems, we additionally present two memetic al- gorithms w'hich use BLS as their local search procedure. Beside providing highly effective methods for a number of hard problems, another objective is also to explain to some extent the behaviour of the proposed approaches on different types of problem structures.
Abstract FR:
En raison de la complexité inhérente aux problèmes difficiles d'optimisation combinatoire, les algorithmes heuristiques ont permis de réaliser des progrès remarquables dans la résolution de cette classe de problèmes au cours des trois dernières décennies. Bien que certaines méthodes heuristiques soient conçues pour traiter des problèmes très spécifiques, d'autres méthodes sont générales et peuvent être appliquées à n'importe quel type de problème. Les exemples d'heuristiques générales sont les méthodes de recherche par voisinage, telles que la recherche tabou, la recherche locale itérée, ou le recuit simulé, et les méthodes bio-inspirées, telles que les algorithmes évolutionnaires ou l'optimisation par colonies de fourmis. Ce travail est dédié à l'élaboration d'une méthode heuristique, nommée Breakout Local Search (BLS), qui peut être considérée comme une hybridation de plusieurs métaheuristiques bien établies. BLS est une variante de la recherche locale itérée puisque son idée de base est d'alterner itérativement entre une descente classique pour découvrir des optima locaux, et une stratégie de diversification dédiée, pour se déplacer d'un attracteur vers un autre dans l'espace de recherche. L'originalité de BLS réside dans son mécanisme de diversification, qui choisit de manière adaptative entre deux types de perturbation et ajuste dynamiquement la force des perturbations en fonction de l'état actuel de la recherche. Jusqu'à présent, nous avons testé BLS sur plusieurs problèmes classiques d'optimisation combinatoire: le problème de la clique maximum (cas pondéré et non-pondéré), l'affectation quadratique, le partitionnement de graphe, la coupe maximum et le problème de la somme coloration minimale. Par rapport aux algorithmes de l'état de l'art, notre stratégie procure des performances remarquables pour ces problèmes. Pour un nombre important d'instances de la clique maximum pondérée, la coupe maximum et le partitionnement de graphe, ainsi que pour plusieurs instances de la somme coloration minimale, notre méthode BLS est même capable d'améliorer les meilleures résultats présentés dans la littérature. Pour améliorer encore les performances sur les problèmes de partitionnement de graphe et d'affectation quadratique, nous avons présenté en outre deux algorithmes mémétiques qui utilisent BLS dans la phase de recherche locale. Par ailleurs, un autre objectif de ce travail est également d'expliquer, dans une certaine mesure, le comportement de l'approche proposée sur différents types de structures de problèmes.