(MX)

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

Keywords
adaptive, fitness driven crossover, schema preservation, epistasis

Motivation
●   Protecting good schemata from destruction.
●   Searching through the solution space in promising directions depending on fitness.

Source text
●   Louis S.J., Rawlins G.J.E. (1991), Designer Genetic Algorithms: Genetic Algorithms in Structure Design, in Proceedings of the Fourth International Conference on genetic Algorithms, Morgan Kaufman, pp.53-60
WEB:     http://citeseer.ifi.unizh.ch/louis91designer.html
            http://citeseer.ist.psu.edu/louis91designer.html

Read also
●   Maini H., Mehrotra K., Mohan Ch., Ranka S. (1994), Knowledge-Based Nonuniform Crossover, in Proceedings of IEEE International Conference on Evolutionary Computation, Orlando
WEB:     http://intl.ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=350048
●   Vekaria K., Clack C. (1999), Biases Introduced by Adaptive Recombination Operators, in Proceedings of the Genetic and Evolutionary Computation Conference, pp. 670-677
WEB:     http://citeseer.ifi.unizh.ch/vekaria99biases.html
            http://citeseer.ist.psu.edu/vekaria99biases.html
●   Chou Ch.-H., Chen J.-N. (2000), Genetic Algorithms: initialization schemes and genes extraction, in Proceedings of The Ninth IEEE International Conference on Fuzzy Systems, pp. 965 - 968
WEB:     http://intl.ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=839167

See also
●   Knowledge-Based Nonuniform Crossover

Algorithm
1.        select two parents A^(t) and B^(t) from a parent pool

2.        create two offspring C^(t+1) and D^(t+1) as follows:

3.                for i = 1 to n do

4.                c_i^(t+1)=a_i^(t)

5.                d_i^(t+1)=b_i^(t)

6.                end do

7.                for i = 1 to n do

8.                              if p_i^B=1 and p_i^A=0 then

9.                              c_i^(t+1)=b_i^(t) 

10.                            end if

11.                            if p_i^B=0 and p_i^A=1 then

12.                            d_i^(t+1)=a_i^(t)

13.                            end if

14.             end do

where:
P^A=(p₁^A,...,p_n^A) – crossover mask of the parent A^(t)  
P^B=(p₁^B,...,p_n^B) – crossover mask of the parent B^(t)  

Comments
●   The MX operator uses a mask vector to determine which bits of which parent are inherited by the offspring. The first step is the duplication of the bits of the parents. The bits of the first parent are copied to the first offspring and, accordingly, of the second parent to the second offspring (rows: 3-6).  In the second step, the offspring exchange bits among each other (rows: 9 and 12) at those positions where the mask vectors of the parent were equal to 1, indicated domination of that parent at that position and the mask vectors of the other parent were equal to 0 (rows: 8 and 11).
●   The mask vectors are initiated in P(0) randomly. During every GA iteration, the mask vectors are inherited by each offspring from its parent. Then the mask vectors of the offspring as well as  the parents undergo modification.  The modification process (not described here) is based on the comparison of fitness of the offspring and the parents. If good offspring were created, the masks of the parents do not need to be modified and the masks of the offspring may be very similar to those of the parents. In a situation where bad offspring were created the masks of the parents as well as of the offspring need to be modified.

Experiment domains
●   n-bit parity checker
●   n-bit adder

Compared to
●   1-Point Crossover