| Full text | |
| Author(s): |
Chicano, Francisco
;
Ochoa, Gabriela
;
Whitley, Darrell
;
Tinos, Renato
;
Aguirre, H
Total Authors: 5
|
| Document type: | Journal article |
| Source: | GECCO'18: PROCEEDINGS OF THE 2018 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE; v. N/A, p. 8-pg., 2018-01-01. |
| 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 2q solutions, where q is the number of sub-functions 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. (AU) | |
| FAPESP's process: | 15/06462-1 - Recombination by decomposition in evolutionary computation |
| Grantee: | Renato Tinós |
| Support Opportunities: | Regular Research Grants |