Permutations sequencing operators have been proved to be effective in solving (mild restrictions of) randomized hard problems such as that of finding Hamiltonian cycles in random graphs (with suitable edge densities). We introduce a simple polynomial reduction of the problem of computing satisfiability assignments for random boolean formulas in conjunctive normal form and with clauses consisting of exactly three literals (random 3-CNFs) to a constrained variant of the problem of computing simple paths in undirected graphs. We provide experimental results evidencing that a simple crossover technique, incorporated into the framework of a memetic model, inspired by Sexual Selection and Elitist/Evolution Strategy principles, is effective in practice to try to solve the satisfiability problem (for random 3-CNF instances satisfiable by hidden assignments).
On Robustness of Permutations Sequencing Operators: Solving Satisfiability of Random 3 − CNFs by Simple Crossover
CARPENTIERI, Marco
2011-01-01
Abstract
Permutations sequencing operators have been proved to be effective in solving (mild restrictions of) randomized hard problems such as that of finding Hamiltonian cycles in random graphs (with suitable edge densities). We introduce a simple polynomial reduction of the problem of computing satisfiability assignments for random boolean formulas in conjunctive normal form and with clauses consisting of exactly three literals (random 3-CNFs) to a constrained variant of the problem of computing simple paths in undirected graphs. We provide experimental results evidencing that a simple crossover technique, incorporated into the framework of a memetic model, inspired by Sexual Selection and Elitist/Evolution Strategy principles, is effective in practice to try to solve the satisfiability problem (for random 3-CNF instances satisfiable by hidden assignments).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
