title: A genetic model: analysis and application to MAXSAT.
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 > or = 3 with respect to the worst case analysis; for Max E3-Sat the average case performances are experimentally compared with other optimization techniques.
authors.affiliation: Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, Italy. bertoni@ds.unimi.it
authors.forename: A
authors.initials: A
authors.lastname: Bertoni
authors.forename: P
authors.initials: P
authors.lastname: Campadelli
authors.forename: M
authors.initials: M
authors.lastname: Carpentieri
authors.forename: G
authors.initials: G
authors.lastname: Grossi
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008957:Models, Genetic; D015233:Models, Statistical; D009154:Mutation; D016571:Neural Networks, Computer; D011995:Recombination, Genetic; D013816:Thermodynamics