Partition crossover for continuous optimization: EPX

Citation

Tinós R, Whitley D, Chicano F & Ochoa G (2021) Partition crossover for continuous optimization: EPX. In: Chicano F (ed.) GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference. 2021 Genetic and Evolutionary Computation Conference, GECCO 2021, Lille, France, 10.07.2021-14.07.2021. New York: Association for Computing Machinery, Inc, pp. 627-635. https://doi.org/10.1145/3449639.3459296

Abstract
Partition crossover (PX) is an efficient recombination operator for gray-box optimization. PX is applied in problems where the objective function can be written as a sum of subfunctions fl(.). In PX, the variable interaction graph (VIG) is decomposed by removing vertices with common variables. Parent variables are inherited together during recombination if they are part of the same connected recombining component of the decomposed VIG. A new way of generating the recombination graph is proposed here. The VIG is decomposed by removing edges associated with subfunctions fl(.) that have similar evaluation for combinations of variables inherited from the parents. By doing so, the partial evaluations of fl(.) are taken into account when decomposing the VIG. This allows the use of partition crossover in continuous optimization. Results of experiments where local optima are recombined indicate that more recombining components are found. When the proposed epsilon-PX (ePX) is compared with other recombination operators in Genetic Algorithms and Differential Evolution, better performance is obtained when the epistasis degree is low.

Keywords
Recombination Operators; Partition Crossover; Gray-box optimization

People

Professor Gabriela Ochoa

Professor, Computing Science