RT Journal Article
T1 Enhancing partition crossover with articulation points analysis
A1 Chicano-García, José-Francisco
A1 Ochoa, Gabriela
A1 Whitley, L. Darrell
A1 Tinós, Renato
K1 Computación evolutiva
AB 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.
YR 2018
FD 2018-07-25
LK https://hdl.handle.net/10630/16353
UL https://hdl.handle.net/10630/16353
LA eng
NO 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).
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 19 ene 2026