2026-06-02T12:46:12Zhttps://riuma.uma.es/rest/oai/request

oai:riuma.uma.es:10630/163532026-02-03T11:16:39Zcom_10630_2254col_10630_37953

00925njm 22002777a 4500 dc Chicano-García, José-Francisco author Ochoa, Gabriela author Whitley, L. Darrell author Tinós, Renato author 2018-07-25 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. https://hdl.handle.net/10630/16353 Computación evolutiva Enhancing partition crossover with articulation points analysis