NP-Completeness and the Coevolution of Exact Set Covers

被引：0

作者：

Horn, Jeffrey ^{[1
]}

机构：

[1] No Michigan Univ, Marquette, MI 49855 USA

来源：

GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE | 2013年

关键词：

genetic algorithm; evolutionary algorithm; evolutionary computation; coevolution; cooperative coevolution; niching; niches; speciation; species; sharing; fitness sharing; resource-defined fitness sharing; NP-completeness; exact cover; XC; X3C; tiling; shape nesting; integer programming; MWSLE;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Recent success with a simple type of coevolution, resource defined fitness sharing (RFS), involving only pairwise interactions among species, has inspired some static analysis of the species interaction matrix. Under the assumption of equilibrium (w.r.t. selection), the matrix yields a set of linear equations. If there exists a subset of species that exactly cover the resources, then its characteristic population vector is a solution to the equilibrium equations. And if the matrix is non-singular, a solution to the equilibrium equations specifies an exact cover of the resources. This polynomial-time reduction of exact cover problems to linear equations is used in this paper to transform certain exact cover NP-complete problems to certain linear equation NP-complete problems: 0-1 Integer Programming, Minimum Weight Positive Solution to Linear Equations. While most of these problems are known to be in NP-complete, our new proof technique introduces a practical, polynomial-time heuristic algorithm for solving large instances of them.

引用

页码：1597 / 1604

页数：8

共 11 条

[1]

DEB K, 1989, PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS, P42

[2]

Dighe R., 1996, J EVOLUTIONARY COMPU, V3, P239

[3]

Garey M. R., 1979, Computers and Intractability: A Guide to the Theory of np-Completeness, DOI DOI 10.1109/TEST.1990.114069

[4]

Goldberg D. E., 1987, Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, P41

[5]

Horn J, 2005, IEEE C EVOL COMPUTAT, P1800

[6]

Horn J., 2002, Parallel Problem Solving from Nature - PPSN VII. 7th International Conference. Proceedings (Lecture Notes in Computer Science Vol.2439), P381

[7]

Horn J, 2008, LECT NOTES COMPUT SC, V5199, P438, DOI 10.1007/978-3-540-87700-4_44

[8]

Horn J, 2010, ICEC 2010: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION, P255

[9]

Karp RM, 1972, REDUCIBILITY COMBINA, P85, DOI [DOI 10.1007/978-1-4684-2001-2_9, 10.1007/978-3-540-68279-0-8]

[10]

KENDALL G, 2000, THESIS U NOTTINGHAM

← 1 2 →