dr Tomasz D.Gwiazda
 Assistant Professor

 
Home page
Short CV
    Publications
   
(e-)Books
   
Papers
My latest book
Students
Office hours
Teaching
 

Contents of e-Book
Index of authors
Index of experiment domains


Introduction

Standard operators
1-Point Crossover
k-Point Crossover
Shuffle Crossover
Reduced Surrogate Crossover
Uniform Crossover
Highly Disruptive Crossover,Heuristic Uniform Crossover
Average Crossover
Discrete Crossover
Flat Crossover
Heuristic Crossover,Intermediate Crossover
Blend Crossover


Binary coded operators
Random Respectful Crossover
Masked Crossover
1bit Adaptation Crossover
Multivariate Crossover
Homologous Crossover
Count-preserving Crossover
Elitist Crossover
    Count-preserving Crossover  
         

 

 

(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)=(a1(t),...,an(t)) and B(t)=(b1(t),...,bn(t)) from
       a parent pool

2.     create two lists of differences Lup and Ldown as follows:

3.     Lup= empty_list, Ldown= empty_list, L_length = 0

4.              for i = 1 to n do

5.                              if ai = 1 and bi = 0 then

6.                              append i to Lup

7.                              L_length  = L_length + 1

8.                              else if ai = 0 and bi = 1 then

9.                              append i to Ldown

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 Ljup exchange the bits
                           between offspring A(t+1) and B(t+1)

18.                           at position determined by Ljdown 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 Lup and Ldown
Ljup  jth element of Lup
Lj
down
 jth element of Ldown

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 Lup 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 Ldown 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 Lup and Ldown (rows: 17 and 18).
   Number of elements in Lup and in Ldown 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

 
   

    :: Copyrights tomaszgwiazda e-books 2006 :: webmaster ::