Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37

Evolutionary Computation

Fall 2000, Vol. 8, No. 3, Pages 291-309
(doi: 10.1162/106365600750078790)
© 2000 Massachusetts Institute of Technology
A Genetic Model: Analysis and Application to MAXSAT
Article PDF (279.39 KB)
Abstract

In this paper, a genetic model based on the operations of recombination and mutation is studied and applied to combinatorial optimization problems.

Results are:

  1. The equations of the deterministic dynamics in the thermodynamic limit (infinite populations) are derived and, for a sufficiently small mutation rate, the attractors are characterized;

  2. A general approximation algorithm for combinatorial optimization problems is designed. The algorithm is applied to the Max Ek-Sat problem, and the quality of the solution is analyzed. It is proved to be optimal for k≥3 with respect to the worst case analysis; for Max E3-Sat the average case performances are experimentally compared with other optimization techniques.