| A Methodology to Find the Elementary Landscape Decomposition of Combinatorial Optimization Problems. | |
| | |
MedLine Citation:
|
PMID: 21469972 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
Abstract A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of 2 elementary landscapes, and to show that the Quadratic Assignment problem is a superposition of 3 elementary landscapes. |
| | |
Authors:
|
Francisco Chicano; L Darrell Whitley; Enrique Alba |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-4-6 |
Journal Detail:
|
Title: Evolutionary computation Volume: - ISSN: 1530-9304 ISO Abbreviation: - Publication Date: 2011 Apr |
Date Detail:
|
Created Date: 2011-4-7 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9513581 Medline TA: Evol Comput Country: - |
Other Details:
|
Languages: ENG Pagination: - Citation Subset: - |
Affiliation:
|
Dept. de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Spain. chicano@lcc.uma.es. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Subject-verb agreement, object clitics and wh-questions in bilingual French-Greek SLI: the case stud...
Next Document: Estradiol 1?mg and drospirenone 2?mg as hormone replacement therapy in postmenopausal Chinese women.