Paper Info
Title
NP-Completeness of deciding binary genetic encodability
Abstract
In previous work of the second author a rigorous mathematical foundation for re-encoding one evolutionary search algorithm by another has been developed. A natural issue to consider then is the complexity of deciding whether or not a given evolutionary algorithm can be re-encoded by one of the standard classical evolutionary algorithms such as a binary genetic algorithm. In the current paper we prove that, in general, this decision problem is NP-complete.
Year
DOI
Venue
2005
10.1007/11513575_4
FOGA
Keywords
Field
DocType
decision problem,current paper,standard classical evolutionary algorithm,rigorous mathematical foundation,evolutionary search algorithm,natural issue,binary genetic algorithm,evolutionary algorithm,previous work,binary genetic encodability,search algorithm,genetic algorithm,genetics
Interactive evolutionary computation,Mathematical optimization,Search algorithm,Evolutionary algorithm,Computer science,Algorithm,Theoretical computer science,Genetic representation,Cultural algorithm,Time complexity,Evolutionary programming,Genetic algorithm
Conference
Volume
ISSN
ISBN
3469
0302-9743
3-540-27237-2
Citations 
PageRank 
References 
0
0.34
7
Authors
2
Name
Order
Citations
PageRank
Andreas Blass116620.37
Boris Mitavskiy210911.06