Evolution algorithms in combinatorial optimization. (English) Zbl 0646.65054

Mühlenbein, H.; Gorges-Schleuter, M.; Krämer, O.

Parallel Comput. 7, No. 1, 65-85 (1988).

The paper deals with a presentation of evolution algorithms. The replicator equation is introduced and an application to the graph partitioning problem (GPP) is given. A new generic algorithm for the traveling salesman problem is given. Numerical results are presented. In the last section the network algorithm for the GPP is applied. A number of other questions are also discussed.
Reviewer’s remark: This algorithm can be easily applied to the symmetric traveling salesman problem.

Reviewer: P.Stavre

MSC:

65K05	Numerical mathematical programming methods
90C35	Programming involving graphs or networks

Keywords:

Darwinian algorithm; superlinear speedup; combinatorial optimization; evolution algorithms; replicator equation; graph partitioning problem; generic algorithm; traveling salesman problem; Numerical results; network algorithm