language: en

An Evolutionary Approach to Combinatorial Optimization Problems

Sami Khuri
Department of Mathematics & Computer Science San Jose State University
One Washington Square San Jose, CA 95192-0103, U.S.A.
khuri@sjsumcs.sjsu.edu
Thomas Back and Jorg Heitkotter
Department of Computer Science University of Dortmund Systems Analysis Research Group, LSXI
D-44221 Dortmund, Germany
fbaeck,jokeg@ls11.informatik.uni-dortmund.de

[Copyright c 1993 ACM Press. All rights reserved.]

[To appear in the proceedings of CSC'94 Phoenix Arizona, March 8-10, 1994.]

Abstract: The paper reports on the application of genetic algorithms, probabilistic search algorithms based on the model of organic evolution, to NP-complete combinatorial optimization problems. In particular, the subset sum, maximum cut, and minimum tardy task problems are considered. Except for the fitness function, no problem-specific changes of the genetic algorithm are required in order to achieve results of high quality even for the problem instances of size 100 used in the paper. For constrained problems, such as the subset sum and the minimum tardy task, the constraints are taken into account by incorporating a graded penalty term into the fitness function. Even for large instances of these highly multimodal optimization problems, an iterated application of the genetic algorithm is observed to find the global optimum within a number of runs. As the genetic algorithm samples only a tiny fraction of the search space, these results are quite encouraging.

1 Introduction