(CPC)

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

Keywords
number of  “1” preservation

Motivation
●   Preserving constant number of bits equal to “1” in every chromosome of a population.

Source text
●   Hartley S.J., Konstam A.H. (1993), Using Genetic Algorithms to Generate Steiner Triple Systems, in ACM Conference on Computer Science, pp.366-371
WEB:     http://citeseer.ifi.unizh.ch/hartley93using.html
            http://citeseer.ist.psu.edu/hartley93using.html

Read also
●   Hou Y.-Ch., Chang Y.-H. (2004), A New Efficient Encoding Mode of Genetic Algorithms for the Generalized Plant Allocation Problem, in Journal of Information Science and Engineering, vol. 20, pp. 1019-1034
WEB:     http://www.iis.sinica.edu.tw/JISE/2004/200409_12.html

See also
●   Count-preserving Crossover-2
●   Set-Oriented Crossover
●   Self Crossover

Algorithm
1.     select two parents A^(t)=(a₁^(t),...,a_n^(t)) and B^(t)=(b₁^(t),...,b_n^(t)) from
       a parent pool

2.     create two lists of differences L^up and L^down as follows:

3.     L^up= empty_list, L^down= empty_list, L_length = 0

4.              for i = 1 to n do

5.                              if a_i = 1 and b_i = 0 then

6.                              append i to L^up

7.                              L_length  = L_length + 1

8.                              else if a_i = 0 and b_i = 1 then

9.                              append i to L^down

10.                           end if

11.           end do

12.  create two offspring A^(t+1) and B^(t+1) as follows:

13.  copy all bits from parent A^(t) to offspring A^(t+1)

14.  copy all bits from parent B^(t) to offspring B^(t+1)

15.           for j = 1 to L_length do

16.                           if Rnd < 0.5 then

17.                           at position determined by L_j^up exchange the bits
                           between offspring A^(t+1) and B^(t+1)

18.                           at position determined by L_j^down exchange the bits
                           between offspring A^(t+1) and B^(t+1)

19.                           end if

20.           end do

where:
Rnd – uniform random real number, 0≤Rnd≤1
L_length – number of elements in the L^up and L^down
L_j^up –  j^th element of L^up
L_j^down –  j^th element of L^down

Comments
●   The CPC operator carries out its task (see: motivation) assuming, that the number of bits equal to “1” in every chromosome in the initial population P(0) is the same.
●   CPC may guarantee preservation of the constant number of bits equal to “1” due to application of two lists noting the differences between the parents (rows: 3-11). List L^up includes positions (numbers) of those bits, on which there are differences between the parents, but the first parent at a given position holds a bit equal to “1” and the second equal to “0” (row: 5). List L^down similarly notes the positions of differences, but the first parent at a given position holds a bit equal to “0” and the second equal to “1” (row: 8). The offspring creation process making use of  those lists is based on the exchange of bits between the offspring at those positions which, are indicated by subsequent element pairs from lists L^up and L^down (rows: 17 and 18).
●   Number of elements in L^up and in L^down is the same, which is a direct result of the assumption, that the number of bits equal to “1” is constant for all chromosomes in P(0).

Experiment domains
●   n/a

Compared to
●   n/a