Algorytmy genetyczne i procesy ewolucyjne
Wykład 2  Implementacja algorytmu genetycznego
Jacek Bieganowski
Instytut Informatyki i Elektroniki
Uniwersytet Zielonogórski
email: [e-mail]
09.03.2009
Implementacja algorytmu genetycznego  W2
Jak zakodować parametry
Liniowe odwzorowanie zdekodowanej liczby z przedziału [0, 2l - 1]
w zadany przedział [Umin, Umax]. Dokładność takiego
odwzorowania wynosi:
Umax - Umin
� =
2l - 1
kod wartość
00 Umin
01 U1
U U1 U2 U
min max
10 U2
11 Umax
Implementacja algorytmu genetycznego  W2
Algorytm genetyczny [Holland]
procedure SGA
begin
t := 0
inicjacja P0
ocena P0
while (not warunek stopu) do
begin
Tt := reprodukcja Pt
Ot := krzyżowanie i mutacja Tt
ocena Ot
Pt+1 := Ot
t := t + 1
end
end
Implementacja algorytmu genetycznego  W2
Selekcja proporcjonalna
procedure SELEKCJA PROPORCJONALNA
begin
for i:=1 to popsize do
begin
a := random()
j := 1
partsum := 0
repeat
partsum := partsum + pr (Xj)
j := j + 1
until (partsum >= a) or (j = popsize)
i
Z := Pj
end
end
Implementacja algorytmu genetycznego  W2
Krzyżowanie jednopunktowe
procedure KRZYZOWANIE JEDNOPUNKTOWE
begin
for i:=1 to popsize/2 do begin
a := random()
if (a < ppc) then
begin
pc = (random " CHROMSIZE-2) + 2
for j:=1 to pc do begin
Yji = Zji
Yji+popsize/2 = Zji+popsize/2
end
for j:=pc+1 to CHROMSIZE do begin
Yji = Zji+popsize/2
Yji+popsize/2 = Zji
end
end
end
end
Implementacja algorytmu genetycznego  W2
Mutacja
procedure MUTACJA
begin
for i:=1 to popsize do
begin
for j:=1 to CHROMSIZE-1 do
begin
a := random()
if (a < ppm) then
begin
Yji := not Yji
end
end
end
end
Implementacja algorytmu genetycznego  W2