Mostrar el registro sencillo del ítem
A methodology to find the elementary landscape decomposition of combinatorial optimization problems
dc.contributor.author | Chicano-García, José-Francisco | |
dc.contributor.author | Whitley, L. Darrell | |
dc.contributor.author | Alba-Torres, Enrique | |
dc.date.accessioned | 2014-10-03T07:10:22Z | |
dc.date.available | 2014-10-03T07:10:22Z | |
dc.date.issued | 2014-10-03 | |
dc.identifier.other | doi:10.1162/EVCO_a_00039 | |
dc.identifier.uri | http://hdl.handle.net/10630/8166 | |
dc.description | Evolutionary Computation Journal 19(4):597-637 | es_ES |
dc.description.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 two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes. | es_ES |
dc.description.sponsorship | Spanish Ministry of Science and Innovation and FEDER under contract TIN2008-06491-C04-01 (the M∗ project). Andalusian Government under contract P07-TIC- 03044 (DIRICOM project). Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-08-1-0422. | es_ES |
dc.language.iso | eng | es_ES |
dc.rights | info:eu-repo/semantics/openAccess | es_ES |
dc.subject | Optimización combinatoria | es_ES |
dc.subject.other | Elementary landscapes | es_ES |
dc.subject.other | Fitness landscapes | es_ES |
dc.subject.other | Combinatorial optimization | es_ES |
dc.subject.other | Decomposition methodology | es_ES |
dc.title | A methodology to find the elementary landscape decomposition of combinatorial optimization problems | es_ES |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.centro | E.T.S.I. Informática | es_ES |
dc.type.hasVersion | info:eu-repo/semantics/submittedVersion | es_ES |