Parallelization of population-based evolutionary algorithms for combinatorial optimization problems

The objective of the present work is to make efficient parallelization of evolutionary algorithms (EA) easier in order to solve large instances of difficult combinatorial optimization problems within an acceptable amount of time, on parallel computer architectures. No known technique allows one to exactly solve within an acceptable amount of time, such difficult combinatorial optimization problems (NP-complete). Moreover, traditional heuristics that are used to find sub-optimal solutions are not always satisfactory since they are easily attracted by local optima. Evolutionary algorithms (EA), that are heuristics inspired by natural evolution mechanisms, explore different regions of the search space concurrently. They are thus rarely trapped in a local optimum and are well suited to treat difficult combinatorial optimization problems. Their behavior can be improved by hybridizing (i.e., combining) them with other heuristics (EA or not). Unfortunately, they are greedy in computation power and memory space. It is thus interesting to parallelize them. Indeed, the use of parallel computers (with dozens of processors) can speed up the execution of EAs and provides the large memory space they require. It is possible to take benefit of the intrinsic parallelism of EAs (e.g., for the concurrent exploration of the search space) in order to design efficient parallel implementations. However each EA has its own characteristics and therefore a general rule cannot be defined. This thesis starts with a description of the state of the art in which the different existing approaches and terminologies are outlined. The fundamental ingredients of EAs are then detailed and these ingredients are grouped by a classification tool called TEA (Table of Evolutionary Algorithms). This table is taken as a basis for the analysis of the criteria that influence the parallelization of EAs in order to define parallelization rules. The analysis considers especially the implementation of hybrid EAs on MIMD-DM1 architectures. A notation of the granularity of parallel EAs is proposed. Further to this analysis, an object-oriented library named APPEAL (Advanced Parallel Population-based Evolutionary Algorithm Library) that applies the parallelization rules is designed and then used in order to experimentally validate these rules. During the experiments, different hybrid EAs are executed on a network of workstations in order to treat two problems: first the optimization of the best set of transceiver sites in a mobile radio network and second the classical graph coloring problem. Finally, a comparison of results and a discussion about future work conclude this thesis. --------------------1MIMD-DM stands for Multiple Instruction stream, Multiple Data stream, Distributed Memory.