
Parallel populationbased methods for combinatorial optimisation

Keywords 
Researchers 
Evolutionary approaches, genetic algorithms, ant systems, hybrid methods, combinatorial optimization, parallel programming. 
Prof. Giovanni CORAY, Dr. Pierre KUONEN, Dr. Frédéric GUIDEC, Patrice CALEGARI (Ph.D. student), Prof. Alain HERTZ, Daniel KOBLER (Ph.D). 
Project period 
Funding Agency 
April 1996  October 1999. 
This project is funded by the Swiss National Science Foundation (grants #2145070.95/1 and #2052594.97). 
Description 
 The objective of the LEOPARD project 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 (NPcomplete).

 Moreover, traditional heuristics that are used to find suboptimal 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 (\ie 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 ( 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.

 The fundamental ingredients of EAs have been identified and grouped with a classification tool called 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 MIMDDM architectures. A notation of the granularity of parallel EAs has been proposed. Further to this analysis, an objectoriented library named APPEAL (Advanced Parallel Populationbased Evolutionary Algorithm Library) that applies the parallelization rules haev been designed and used in order to experimentally validate the rules. During the experiments, different hybrid EAs have been 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.


Publications 
Calégari P., Guidec F., and Kuonen P., A Parallel Genetic Approach to Transceiver Placement Optimisation, in Proceedings of the SIPAR Workshop '96: Parallel and Distributed Systems, (C.A. Héritier, B. Chopard, eds.), pp. 2124, Geneva, Switzerland, September 1996. 

Calégari P., Kuonen P., Guidec F., and Wagner D., A Genetic Approach to Radio Network Optimization for Mobile Systems, in Proceedings of the IEEE 47th Vehicular Technology Conference (VTC), IEEE, Ed., May 1997, vol. 2 of Technology in Motion, pp. 755759. 

Calégari P., Guidec F., and Kuonen P., Urban Radio Network Planning for Mobile Phones, EPFL Supercomputing Review, vol. 9, pp. 410, November 1997. 

Calégari P., Guidec F., Kuonen P., and Kobler D., Parallel IslandBased Genetic Algorithm for Radio Network Design, Journal of Parallel and Distributed Computing (JPDC): special issue on Parallel Evolutionary Computing, Academic Press, vol. 47, no. 1, pp. 8690, November 1997. 

Calégari P., Guidec F., Kuonen P., and Nielsen F., Combinatorial optimization algorithms for radio network planning, Theoretical Computer Science (TCS), 2000. 

Calégari P., Coray G., Kobler D., Kuonen P., and Hertz A., A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization, Journal of Heuristics, vol. 5, no. 2, pp. 145158, July 1999. 

Calégari P., Parallelization of populationbased evolutionary algorithms for combinatorial optimization problems, PhD thesis, number 2046, Swiss Federal Institute of Technology (EPFL), Lausanne, Septembre 1999. 
