| Title | Parallelization of population-based evolutionary algorithms for combinatorial optimization problems | |
| Thesis
supervisor |
Professor Giovanni Coray
Director of the Computer Science Theory Laboratory Swiss federal institute of technology - Lausanne |
 |
| Key words | Parallel computing, evolutionary algorithms, combinatorial optimization, taxonomy, object oriented library, transceiver siting, graph coloring. | |
| Abstract | 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-DM (Multiple Instruction stream, Multiple Data stream, Distributed Memory) 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. The EAs that are tested are: an island-based genetic algorithm, an ant system, an island-based ant system, and an island-based genetic ant algorithm. Finally, a comparison of results and a discussion about future work conclude this thesis. |
|
| Download |
|
|
| Funding | This work is part of the project LEOPARD that was funded by the Swiss National Science Foundation (grants 2100-45070.95/1 and 2000-52594.97). It is a logical continuation of the project PAC (Parallelization of Combinatorial Optimization Algorithms) funded by the same foundation (grants SPP-IF 5003-034349, 1993-96). A part of this work was done within the European project STORMS that was framed in the 4th ACTS Program (Advanced Communications Technologies & services) partially funded by the European Commission (AC016) and Swiss fund OFES (1995-98). | |
| Language | English | |
| Reference
(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, } |
|
|
Categories and Subject Descriptors |
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. | |
