|
(1BX)
download PDF
with first 40 pages
from my latest eBook
if you need more operators
click here
Keywords
adaptive,
recombination,
combination of crossovers
Motivation
●
Obtaining different trajectories of searching the solution space
through simultaneous application of two operators of diametrically
opposite characteristics.
Source text
●
Spears W.M. (1992),
Adapting Crossover in Evolutionary Algorithms, Technical Report
AIC-92-025, Naval Research Laboratory, Navy Center for Applied
Research on Artificial Intelligence.
WEB:
http://www.aic.nrl.navy.mil/~spears/ea.html
Read also
●
Vrajitoru
D. (2004),
Intra and Extra-Generation Schemes for Combining Crossover Operators, in
Proceedings of the Fifteenth
Midwest Artificial Intelligence and Cognitive Science Conference MAICS
2004,
pp. 86-91
WEB:
http://www.maics.us/proceedings.htm
●
Herrera
F.,
Lozano M.,
Sαnchez A.M.,
Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An
Experimental Study, in Soft Computing - A Fusion of Foundations,
Methodologies and Applications, Springer, vol. 9(4), pp. 280-298
WEB:
http://sci2s.ugr.es/publications/
http://dx.doi.org/10.1007/s00500-004-0380-9
See also
●
k-Point Crossover
●
Uniform Crossover
●
Combined Balanced Crossover
●
Adaptive Strategies of Mixing Crossovers
Algorithm
1.
select two parents A(t)
and B(t) from current population P(t)
2.
choose a uniform random real number u from
interval
<0, 1>
3.
if an(t)=bn(t)=1
then
4.
create two offspring C(t+1)
and D(t+1) by the
2-Point
Crossover as follows:
5.
randomly choose two crossover points cp1
and cp2 from set
{1,...,n-1}
(cp1<cp2)
6.
for i = 1 to cp1
do
7.
ci(t+1)=ai(t)
8.
di(t+1)=bi(t)
9.
end do
10.
for i = cp1
+ 1 to cp2 do
11.
ci(t+1)=bi(t)
12.
di(t+1)=ai(t)
13.
end do
14.
for i = cp2
+ 1 to n do
15.
ci(t+1)=ai(t)
16.
di(t+1)=bi(t)
17.
end do
18.
else if
an(t)=bn(t)=0
then
19.
create two offspring C(t+1)
and D(t+1)
by the Uniform Crossover
as
follows:
20.
for i = 1 to n
do
21.
choose a uniform random
real number u
from
interval
<0,1>
22.
if u ≤
ps then (swap bits)
23.
ci(t+1)=bi(t)
24.
di(t+1)=ai(t)
25.
else
(dont swap)
26.
ci(t+1)=ai(t)
27.
di(t+1)=bi(t)
28.
end if
29.
end do
30.
else
31.
choose a uniform random real number u
from interval
<0, 1>
32.
if u < 0.5 then
33.
create two offspring C(t+1)
and D(t+1) by the
Uniform Crossover as follows:
34.
for i =
1 to n do
35.
choose a
uniform random real number
u from interval
<0,1>
36.
if u
≤ ps then (swap bits)
37.
ci(t+1)=bi(t)
38.
di(t+1)=ai(t)
39.
else (dont
swap)
40.
ci(t+1)=ai(t)
41.
di(t+1)=bi(t)
42.
end if
43.
end do
44.
else
45.
create two offspring C(t+1)
and D(t+1) by the
2-Point Crossover as follows:
46.
randomly choose two
crossover points
cp1 and cp2
from set {1,...,n-1} (cp1<cp2)
47.
for i =
1 to cp1 do
48.
ci(t+1)=ai(t)
49.
di(t+1)=bi(t)
50.
end do
51.
for i =
cp1 + 1 to cp2 do
52.
ci(t+1)=bi(t)
53.
di(t+1)=ai(t)
54.
end do
55.
for i =
cp2 + 1 to n do
56.
ci(t+1)=ai(t)
57.
di(t+1)=bi(t)
58.
end do
59.
end if
60.
end if
where:
ps
probability of swapping, in standard form ps = 0.5
Comments
●
In the 1BX method the last bit of the solution vector is reserved
for the code of one of the two of the applied crossover operators.
Assuming that 0 corresponds with the
Uniform
Crossover
(UX) operator and 1 corresponds with the
2-Point Crossover (2-PX) operator, the choice of one of them is
made according to the rule: if the last bit of the parents is off the
same value (rows: 3 and 18) then choose the operator indicated by this
bit (rows: 4 and 19). Otherwise choose the operator through selection by
a draw (rows: 32 and 44).
●
Application of the described crossover scheme combines the choice
of the operator with the solution vector. Moreover, this choice is
carried out separately for each parent pair; hence this scheme is called
local adaptation. Global adaptation version has been also
presented, but as it was emphasized by the author, significantly worse
results were obtained by its application.
Experiment domains
●
n-peak problems
Compared to
●
k-Point Crossover
●
Uniform Crossover |
Home page
