| Titre | Parallelization of population-based evolutionary
algorithms for combinatorial optimization problems
(Parallélisation des algorithmes d'évolution basés sur des populations pour la résolution de problemes d'optimisation combinatoire) |
|
| Directeur
de these |
Professeur Giovanni Coray
Directeur du Laboratoire d'Informatique Théorique Ecole Polytechnique Fédérale de Lausanne |
 |
| Mots clés | Parallélisme, algorithmes d'évolution, optimisation combinatoire, taxonomie, conception logicielle orientée objet, planification de réseaux radio, coloration de graphes. | |
| Résumé | Le but de ce travail de thèse est de faciliter
la parallélisation efficace des algorithmes d'évolution (e.g.,
les algorithmes génétiques, les systèmes de fourmis,
etc.) afin de résoudre, en un temps acceptable, de grosses instances
de problèmes d'optimisation combinatoire difficiles sur des architectures
parallèles.
Aucune technique connue ne permet de résoudre, en un temps acceptable et de façon exacte, les grosses instances des problèmes d'optimisation combinatoire NP-complets (aussi appelés ``difficiles''). De plus, les heuristiques traditionnelles qui sont utilisées pour trouver des solutions approchées ne donnent pas toujours satisfaction car elles sont facilement attirées par les optima locaux. Les algorithmes d'évolution (AE), qui sont des heuristiques inspirées par l'évolution des systèmes biologiques, explorent simultanément différentes régions de l'espace de recherche. Ils sont donc peu sensibles à l'attraction d'un optimum local et conviennent bien pour résoudre des problèmes d'optimisation combinatoire difficiles. Leur comportement peut être amélioré en les hybridant (i.e., en les combinant) entre eux ou avec d'autres heuristiques. Malheureusement, ils sont gourmands en temps de calcul et en espace mémoire et il est donc intéressant de les paralléliser. En effet l'utilisation d'ordinateurs parallèles (comprenant des dizaines de processeurs) peut permettre d'accélérer leur exécution et de fournir l'espace mémoire important dont ils ont besoin. Il est possible de tirer profit du parallélisme intrinsèque des AE (e.g., la recherche simultanée de plusieurs solutions) pour en concevoir des implémentations parallèles efficaces, toutefois chaque AE possède ses propres caractéristiques et une règle générale ne peut pas être définie. Cette thèse commence par un état de l'art du domaine mettant l'accent sur les différentes approches et terminologies existantes. La caractérisation de chacune des composantes fondamentales des AE est alors détaillée et ces composantes sont regroupées dans un outil de classification appelé TEA (tableau des algorithmes d'évolution). Ce tableau est utilisé comme base pour l'analyse des critères influençant la parallélisation des AE afin de définir des règles de parallélisation. L'analyse considère spécialement l'implémentation d'AE hybrides sur des architectures MIMD-DM (machine à flot d'instructions multiple travaillant sur un flot de données multiple avec une mémoire distribuée). Une notation de la granularité des AE parallèles y est entre autre proposée. Suite à cette analyse, une librairie orientée objet (nommée APPEAL) est conçue, puis utilisée pour valider expérimentalement les règles de parallélisation qui ont été définies. Différents AE hybrides sont ainsi exécutés sur un réseau de stations de travail pour traiter deux problèmes : le placement des antennes d'un réseau de téléphonie mobile, et le problème classique de coloration d'un graphe. Les AE qui sont testés sont : un algorithme génétique à îles, un système de fourmis, un système de fourmis à îles, et un système de fourmis génétique à îles. Finalement, les résultats obtenus sont comparés et une discussion sur les suites à donner à ce travail conclut le rapport. |
|
| Fichiers
Disponibles |
|
|
| Financement | Ce travail a été réalisé dans le cadre du projet LEOPARD qui a été financé par le Fond National Suisse pour la Recherche (FNRS 2100-45070.95/1 et 2000-52594.97). II s'agit d'une suite logique du projet PAC (Parallélisation des Algorithmes Combinatoires) financé par le même fond (FNRS SPP-IF 5003-034349, 1993-96). Une partie de ce travail a ete réalisée en coopération avec le projet européen STORMS du 4ème programme cadre ACTS (Advanced Communications Technologies & services) partiellement financé par la Commission Européenne (AC016) et le fond suisse OFES (1995-98). | |
| Langue | Anglais | |
| Référence
(Bibtex) |
@PhdThesis{Calegari99,
author = {Cal\'egari, P.}, title = {Parallelization of population-based evolutionary algorithms for combinatorial optimization problems}, school = {number 2046, EPFL}, year = {1999}, address = {Swiss Federal Institute of Technology of Lausanne, CH-1015 Lausanne, Switzerland}, month = sep, } |
|
|
ACM et descripteurs de sujets |
C.1.2 [Processor architecture]: Multiple Data Stream Architectures (Multiprocessors) - Multiple-instruction-stream, multiple-data-stream processors (MIMD); D.1.3 [Programming techniques]: Concurrent Programming - Parallel programming; D.1.5 [Programming techniques]: Object-oriented Programming; D.2.13 [Software engineering]: Reusable Software - Reusable libraries, Reusable models; F.1.2 [Computation by abstract devices]: Modes of Computation - Parallelism and concurrency; I.2.8 [Artificial intelligence]: Problem Solving, Control Methods, and Search - Heuristic methods. | |
