the diploid chromosome mechanism for Evolutionary Algorithms


(from book Applied Evolutionary Algorithms in Java)

One interesting variance between biological evolution mechanisms and those used in most evolutionary algorithms is that organisms normally use a diploid chromosome structure, while EAs use a haploid design. First, however, we need a basic definition of the term “diploid”:

Pertaining to homologous chromosomes, where each cromosome number has a pair of chromosomes, such as th 23 pairs in humans totaling our 46 chromosome compliment. (biology online)

A diploid chromosome structure is therefore composed of a pair of chromosomes. One advantage this offers is to allow memory to be incorporated into the individual’s chromosome structure. In an EA context the choice between the two values requires some form of dominance function. Lewis et al. (1998) give a useful comparison of the relative merits of haploid and diploid designs:

A Comparison of Dominance Mechanisms and Simple Mutation on Non-Stationary Problems. Jonathan Lewis, Emma Hart, Graeme Ritchie. Lecture Notes in Computer Science

Tha main proposed application area for a diploid EA is when the fitness function is time-varying. Hence the aditional information stored in the chromosome can provide a secondary source of diversity within the population. In addition, the diploid structure may enable the retention of long-term memory of past solutions, which will be useful if the fitness landscape is time-dependent. However, very little experimental work has yet been performed in this area.

To this last point, I’ve searched for extra info (papers) on time-varying (changing) optimization problems, being that this is a clear line of research in this field. These are my findings:

Memory Enhanced Evolutionary Algorithms for Changing Optimization Problems. Jürgen Branke. Proceedings of the Congress on Evolutionary Computation (1999)

Evolutionary Approaches to Dynamic Optimization Problems A Survey. Jürgen Branke. Evolutionary Algorithms for Dynamic Optimization Problems (1999)

Evolutionary Approaches to Dynamic Optimization Problems Updated Survey. Jürgen Branke. Evolutionary Algorithms for Dynamic Optimization Problems (2001)

Evolutionary Algorithms for Non-Stationary Environments. Krzysztof Trojanowski, Zbigniew Michalewicz. Proc. of 8th Workshop: Intelligent Information systems (1999)

Non-stationary Function Optimization using Evolutionary Algorithms with a Case-based Memory. J. Eggermont, T. Lenaerts.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s