Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

De nombreux problèmes académiques ou industriels sont multi-objectifs et ont particulièrement intéressé les chercheurs ces dernières années. Ces problèmes n’admettent généralement pas d’unique solution optimale mais un ensemble de solutions de meilleurs compromis qui forment le front Pareto dans l’espace objectif. Pour approximer cet ensemble en un temps raisonnable, des algorithmes évolutionnaires multi-objectifs ont été proposés dans la littérature autant pour des problèmes continus que des problèmes combinatoires. Ce type d’algorithmes peut fournir plusieurs solutions en une seule exécution et est moins sensible quant à la forme du front Pareto que d’autres classes de métaheuristiques. Comme ils requièrent généralement des capacités de calcul importantes pour explorer de grandes régions de l’espace de recherche dans la résolution de problèmes réels et complexes, les algorithmes évolutionnaires multi-objectifs peuvent bénéficier des nouvelles architectures de calcul haute performance. Ainsi, des approches parallèles ont été proposées à la fois pour réduire leur temps d’exécution et améliorer la qualité des solutions fournies. Bien que des progrès significatifs aient été réalisés ces dernières années dans la conception et l’amélioration de modèles parallèles pour les algorithmes évolutionnaires, la plupart de ces modèles ont une extensibilité limitée et des difficultés à manipuler des problèmes variés. Résoudre efficacement un problème combinatoire multi-objectifs sur une architecture de calcul haute performance demeure encore un défi aujourd’hui. Dans cette thèse, des mécanismes sont proposés au sein d’un nouveau modèle parallèle pour exploiter de multiples unités de calcul dans la résolution de problèmes multi-objectifs. L’approche générale reprend les principes des modèles en îles avec une division de l’espace objectif qui repose sur une méthode de regroupement. Les principales caractéristiques du modèle sont (i) la vue globale donnée à l’île organisatrice pour atteindre une meilleure distribution des solutions (ii) des communications asynchrones pour réduire les surcoûts du parallélisme (iii) des îles témoins pour accroitre la diversification (iv) une phase de recherche locale pour améliorer la qualité des solutions. Une étude expérimentale minutieuse est effectuée afin d’évaluer les performances de l’approche et plus particulièrement de chaque composante dans la résolution de deux problèmes combinatoires classiques, le problème de voyageur de commerce multi-objectifs et le problème d’affectation quadratique multi-objectifs. L’extensibilité et la qualité des solutions sont analysées comparativement aux modèles parallèles de la littérature.

Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front. As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today’s high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today. This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models.