A distance between populations for n-points crossover in genetic algorithms

Mauro Castelli, Gianpiero Cattaneo, Luca Manzoni, Leonardo Vanneschi

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The theoretical study of Genetic Algorithms and the dynamics induced by their genetic operators is a research field with a long history and many different approaches. In this paper we complete a recently presented approach to model one-point crossover using pretopologies (or Čechtopologies) in two ways. First, we extend it to the case of n-points crossover. We extend the definition of crossover distance between populations to work for n-points crossover, proving that computing it can be performed in polynomial time for any fixed number of crossover points. Secondly, we experimentally study how the distance distribution changes when the number of crossover points increases. In particular, the average distance between a population and the optimum decreases with the increase in the number of crossover points, showing that increasing the latter can reduce the number of crossover operations needed to evolve an optimal solution.

Original languageEnglish
Pages (from-to)636-645
Number of pages10
JournalSwarm and Evolutionary Computation
Volume44
Issue numberFebruary
Early online date21 Aug 2018
DOIs
Publication statusPublished - Feb 2019

Fingerprint

Crossover
Genetic algorithms
Genetic Algorithm
Polynomials
Pretopology
Distance Distribution
Average Distance
Genetic Operators
Polynomial time
Optimal Solution
Decrease
Computing

Cite this

@article{07e9440519f347c7959b0bf4bd5cf2d1,
title = "A distance between populations for n-points crossover in genetic algorithms",
abstract = "The theoretical study of Genetic Algorithms and the dynamics induced by their genetic operators is a research field with a long history and many different approaches. In this paper we complete a recently presented approach to model one-point crossover using pretopologies (or Čechtopologies) in two ways. First, we extend it to the case of n-points crossover. We extend the definition of crossover distance between populations to work for n-points crossover, proving that computing it can be performed in polynomial time for any fixed number of crossover points. Secondly, we experimentally study how the distance distribution changes when the number of crossover points increases. In particular, the average distance between a population and the optimum decreases with the increase in the number of crossover points, showing that increasing the latter can reduce the number of crossover operations needed to evolve an optimal solution.",
author = "Mauro Castelli and Gianpiero Cattaneo and Luca Manzoni and Leonardo Vanneschi",
note = "Castelli, M., Cattaneo, G., Manzoni, L., & Vanneschi, L. (2019). A distance between populations for n-points crossover in genetic algorithms. Swarm and Evolutionary Computation, 44(February), 636-645. DOI: 10.1016/j.swevo.2018.08.007",
year = "2019",
month = "2",
doi = "10.1016/j.swevo.2018.08.007",
language = "English",
volume = "44",
pages = "636--645",
journal = "Swarm and Evolutionary Computation",
issn = "2210-6502",
publisher = "Elsevier",
number = "February",

}

A distance between populations for n-points crossover in genetic algorithms. / Castelli, Mauro; Cattaneo, Gianpiero; Manzoni, Luca; Vanneschi, Leonardo.

In: Swarm and Evolutionary Computation, Vol. 44, No. February, 02.2019, p. 636-645.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A distance between populations for n-points crossover in genetic algorithms

AU - Castelli, Mauro

AU - Cattaneo, Gianpiero

AU - Manzoni, Luca

AU - Vanneschi, Leonardo

N1 - Castelli, M., Cattaneo, G., Manzoni, L., & Vanneschi, L. (2019). A distance between populations for n-points crossover in genetic algorithms. Swarm and Evolutionary Computation, 44(February), 636-645. DOI: 10.1016/j.swevo.2018.08.007

PY - 2019/2

Y1 - 2019/2

N2 - The theoretical study of Genetic Algorithms and the dynamics induced by their genetic operators is a research field with a long history and many different approaches. In this paper we complete a recently presented approach to model one-point crossover using pretopologies (or Čechtopologies) in two ways. First, we extend it to the case of n-points crossover. We extend the definition of crossover distance between populations to work for n-points crossover, proving that computing it can be performed in polynomial time for any fixed number of crossover points. Secondly, we experimentally study how the distance distribution changes when the number of crossover points increases. In particular, the average distance between a population and the optimum decreases with the increase in the number of crossover points, showing that increasing the latter can reduce the number of crossover operations needed to evolve an optimal solution.

AB - The theoretical study of Genetic Algorithms and the dynamics induced by their genetic operators is a research field with a long history and many different approaches. In this paper we complete a recently presented approach to model one-point crossover using pretopologies (or Čechtopologies) in two ways. First, we extend it to the case of n-points crossover. We extend the definition of crossover distance between populations to work for n-points crossover, proving that computing it can be performed in polynomial time for any fixed number of crossover points. Secondly, we experimentally study how the distance distribution changes when the number of crossover points increases. In particular, the average distance between a population and the optimum decreases with the increase in the number of crossover points, showing that increasing the latter can reduce the number of crossover operations needed to evolve an optimal solution.

UR - http://www.scopus.com/inward/record.url?scp=85052743686&partnerID=8YFLogxK

UR - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000456761600046

U2 - 10.1016/j.swevo.2018.08.007

DO - 10.1016/j.swevo.2018.08.007

M3 - Article

VL - 44

SP - 636

EP - 645

JO - Swarm and Evolutionary Computation

JF - Swarm and Evolutionary Computation

SN - 2210-6502

IS - February

ER -