|
Abstract : |
Parallel genetic algorithms (PGA) use two major modi cations compared to the genetic algorithm. Firstly, selection for mating is distributed. Individuals liveina2-Dworld. Selection of a mate is done by each individual independently in its neighborhood. Secondly, each individual may improve its tness during its lifetime by e.g. local hill-climbing. The PGA is totally asynchronous, running with maximal e ciency on MIMD parallel computers. The search strategy of the PGA is based on a small number of intelligent and active individuals, whereas a GA uses a large population of passive individuals. We will show thepower of the PGA with two combinatorial problems- the traveling salesman problem and the m graph partitioning problem. In these examples, the PGA has found solutions of very large problems, which are comparable or even better than any other solution found by other heuristics. A comparison between the PGA search strategy and iterated local hill-climbing is made. KEYWORDS Parallel optimization, genetic algorithm, iterated Lin-Kernighan search, traveling salesman, graph partitioning, |
