(EX)

download PDF with first 40 pages
from my latest eBook
if you need more operators click here

Keywords
selection, exploration, exploitation, exploration/exploitation balance, competition for survival

Motivation
●   Assessing the effectivity of integrating the selection and crossover processes.

Source text
●   Thierens D., Goldberg D.E. (1994), Elitist Recombination: an integrated selection recombination GA, in Proceedings of the First IEEE World Congress on Computational Intelligence, pp. 508-512
WEB:      http://intl.ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=349898
             http://www.cs.uu.nl/groups/DSS/publications/

Read also
●   Vekaria K., Clack C. (1998), Selective Crossover in Genetic Algorithms: An Empirical Study, in Proceedings of the fifth Conference on Parallel Problem Solving from Nature, Springer-Verlag, pp. 438-447
WEB:     http://citeseer.ifi.unizh.ch/vekaria98selective.html
            http://citeseer.ist.psu.edu/vekaria98selective.html
●   Coli M., Genusso P., Palazzari P. (1996), A New Crossover Operator for Genetic Algorithms, in IEEE International Conference on Evolutionary Computation, pp. 201-206
WEB:     http://citeseer.ifi.unizh.ch/coli96new.html
            http://citeseer.ist.psu.edu/coli96new.html

See also
●   Best Schema Crossover
●   Selective Crossover-2
●   Partially Randomized Crossover
●   Direct Design Variable Exchange Crossover

Algorithm
1.        for every generation of GA do

2.        randomly shuffle the entire population P(t)={A₁^(t),...,A_{Population_size}^(t)}

3.                for i = 1 to Population_size  do

4.                create two vectors V₁ and V₂:
               V₁=A_i^(t)XA_i+1^(t)      V₂=A_i^(t)XA_i+1^(t) 

5.                compute the fitness value of V₁ and V₂

6.                insert best two vectors of {A_i^(t),A_i+1^(t),V₁,V₂} into the next
               population P(t+1) as offspring

7.                i = i + 2

8.                end do

where:
X – preferred crossover method

Comments
●   In the standard genetic algorithm, the selection process is always preceded by the crossover process. In the EX method both of the processes are integrated. During the first step the entire population is randomly shuffled (row: 2). Then, from each successive pair of parental vectors, two new vectors are created by crossover (row: 4). From a “family” created in this way, two best vectors are singled out and implemented as offspring to the next population (row: 6).
●   Application of elitist selection in the traditional way that is on the level of the entire population may often be the reason for the premature convergence of the algorithm. An EX elitist selection applied on the “family” level (row: 6) eliminates this danger according to the authors.

Experiment domains
●   bit counting function
●   fully deceptive trap function

Compared to
●   Uniform Crossover