**
(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*_{1}^{(t)},...,*a*_{n}^{(t)})
and
*B*^{(t)}=(*b*_{1}^{(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 |