Hill-climbing, simulated annealing and genetic algorithms: a comparative study and application to the mapping problem

Hill-climbing, simulated annealing and genetic algorithms are search techniques that can be applied to most combinatorial optimization problems. The three algorithms are used to solve the mapping problem, which is the optimal static allocation of communication processes on distributed memory architectures. Each algorithm is independently evaluated and optimized according to its parameters. The parallelization of the algorithms is also considered. As an example, a massively parallel genetic algorithm is proposed for the problem, and results of its implementation on a 128-processor Supernode are given. A comparative study of the algorithms is then carried out. The criteria of performance considered are the quality of the solutions obtained and the amount of search time used for several benchmarks. A hybrid approach consisting of a combination of genetic algorithms and hill-climbing is also proposed and evaluated