Genetic algorithm behavior in the MAXSAT domain
作者： Soraya Rana , Darrell Whitley
DOI: 10.1007/BFB0056920
关键词: Satisfiability 、 Maximum satisfiability problem 、 Genetic algorithm 、 Time complexity 、 Computer science 、 Algorithm 、 NP-complete 、 Domain (software engineering) 、 Boolean satisfiability problem 、 Schema (genetic algorithms)
摘要: Random Boolean Satisfiability function generators have recently been proposed as tools for studying genetic algorithm behavior. Yet MAXSAT problems exhibit extremely limited epistasis. Furthermore, all nonzero Walsh coefficients can be computed exactly in polynomial time using only the clause information. This means low order schema averages quickly and very large problems. But unless P=NP, this information cannot reliably lead to global optimum, thus nontrivial must deceptive.
springer.com
sci-hub.se 参考文章(11)
Bart Selman, David Mitchell, Hector Levesque, Hard and easy distributions of SAT problems national conference on artificial intelligence. pp. 459- 465 ,(1992)
Jeremy Frank, A Study of Genetic Algorithms to Find Approximate Solutions to Hard 3-SAT Problems Springer Netherlands. pp. 547- 554 ,(1995) , 10.1007/978-94-011-7108-3_57
David E. Goldberg, Genetic Algorithms and Walsh Functions: Part II, Deception and Its Analysis. Complex Systems. ,vol. 3, ,(1989)
Colin Reeves, Christine Wright, An Experimental Design Perspective on Genetic Algorithms Foundations of Genetic Algorithms. ,vol. 3, pp. 7- 22 ,(1995) , 10.1016/B978-1-55860-356-1.50005-4
Bob Kanefsky, Peter Cheeseman, William M. Taylor, Where the really hard problems are international joint conference on artificial intelligence. pp. 331- 337 ,(1991)
Bart Selman, David Mitchell, Hector Levesque, A new method for solving hard satisfiability problems national conference on artificial intelligence. pp. 440- 446 ,(1992)
Colin R. Reeves, Christine C. Wright, Epistasis in Genetic Algorithms: An Experimental Design Perspective international conference on genetic algorithms. pp. 217- 224 ,(1995)
J. Frank, P. Cheeseman, J. Stutz, When gravity fails: local search topology Journal of Artificial Intelligence Research. ,vol. 7, pp. 249- 281 ,(1997) , 10.1613/JAIR.445
Martin Davis, Hilary Putnam, A Computing Procedure for Quantification Theory Journal of the ACM. ,vol. 7, pp. 201- 215 ,(1960) , 10.1145/321033.321034
Robert B. Heckendorn, Soraya Rana, Darrell Whitley, A tractable Walsh analysis of SAT and its implications for genetic algorithms national conference on artificial intelligence. pp. 392- 397 ,(1998)