A Genetic Model: Analysis and Application to MAXSAT
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.
combinatorial optimization approximation algorithms genetic algorithms markov chains dynamical systems hopfield's networks