Mostrar el registro sencillo del ítem
Enhancing partition crossover with articulation points analysis
dc.contributor.author | Chicano-García, José-Francisco | |
dc.contributor.author | Ochoa, Gabriela | |
dc.contributor.author | Whitley, L. Darrell | |
dc.contributor.author | Tinós, Renato | |
dc.date.accessioned | 2018-07-25T07:29:18Z | |
dc.date.available | 2018-07-25T07:29:18Z | |
dc.date.created | 2018 | |
dc.date.issued | 2018-07-25 | |
dc.identifier.uri | https://hdl.handle.net/10630/16353 | |
dc.description.abstract | Partition Crossover is a recombination operator for pseudo-Boolean optimization with the ability to explore an exponential number of solutions in linear or square time. It decomposes the objective function as a sum of subfunctions, each one depending on a different set of variables. The decomposition makes it possible to select the best parent for each subfunction independently, and the operator provides the best out of $2^q$ solutions, where $q$ is the number of subfunctions in the decomposition. These subfunctions are defined over the connected components of the recombination graph: a subgraph of the objective function variable interaction graph containing only the differing variables in the two parents. In this paper, we advance further and propose a new way to increase the number of linearly independent subfunctions by analyzing the articulation points of the recombination graph. These points correspond to variables that, once flipped, increase the number of connected components. The presence of a connected component with an articulation point increases the number of explored solutions by a factor of, at least, 4. We evaluate the new operator using Iterated Local Search combined with Partition Crossover to solve NK Landscapes and MAX-SAT. | en_US |
dc.description.sponsorship | Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech. Funding was provided by the Fulbright program, the Spanish Ministry of Education, Culture and Sport (CAS12/00274), the Spanish Ministry of Economy and Competitiveness and FEDER (TIN2014-57341-R and TIN2017-88213-R), the Air Force Office of Scientific Research, (FA9550-11-1-0088), the Leverhulme Trust (RPG-2015-395), the FAPESP (2015/06462-1) and CNPq (304400/2014-9). | en_US |
dc.language.iso | eng | en_US |
dc.rights | info:eu-repo/semantics/openAccess | en_US |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/4.0/ | * |
dc.subject | Computación evolutiva | en_US |
dc.title | Enhancing partition crossover with articulation points analysis | en_US |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.centro | E.T.S.I. Informática | en_US |
dc.relation.eventtitle | Genetic and Evolutionary Computation Conference | en_US |
dc.relation.eventplace | Kyoto, Japón | en_US |
dc.relation.eventdate | julio de 2018 | en_US |
dc.rights.cc | Atribución-NoComercial-CompartirIgual 4.0 Internacional | * |
dc.type.hasVersion | info:eu-repo/semantics/submittedVersion | es_ES |