Algorytmy genetyczne i procesy ewolucyjne
Wykład 3 – metody selekcji
Jacek Bieganowski
Instytut Informatyki i Elektroniki
Uniwersytet Zielonogórski
email: J.Bieganowski@iie.uz.zgora.pl
http://www.uz.zgora.pl/~jbiegano/agipe09
15 marca 2009
Schemat algorytmu genetycznego
procedure
SGA
begin
t := 0
inicjacja
P
0
ocena
P
0
while
(
not
warunek stopu)
do
begin
T
t
:= reprodukcja
P
t
O
t
:= krzy˙
zowanie i mutacja
T
t
ocena
O
t
P
t+1
:=
O
t
t := t + 1
end
end
Eksploracja i eksploatacja
Przez eksploatację można rozumieć przeszukiwanie obszaru
przyciągania ekstremum w celu wyznaczenia maksimum
lokalnego.
Eksploracja polega na wybraniu obszaru zawierającego
maksimum globalne ze zbioru ekstermów lokalnych.
Nacisk selektywny
Najsilniejszą tendencję do opuszczania obszarów przyciągania
ekstremum lokalnego ma algorytm błądzenia przypadkowego.
Największą szybkość podążania w kierunku ekstermum
globalnego ma algorytm wzrostu. Niestety algorytm ten łatwo
może utknąć w ekstremum lokalnym.
Algorytm optymalizacji globalnej równoważy ekslplorację
(opuszczanie obszarów przyciągania) i eksploatację (podążanie
w kierunku ekstremum).
Proporcje eksploracji i eksploatacji nazywa się naciskiem
selektywnym. Nacisk selektywny jest tym większy im algorytm
przypomina metodę wzrostu.
Reprodukcja i sukcesja
Selekcja (reprodukcja + sukcesja) skutkuje w ukierunkowaniu
algorytmu w stronę rozwiązań lepszych od dotychczasowych.
Reprodukcja polega na utworzeniu populacji tymczasowej T
t
,
która jest następnie poddawana operacjom genetycznym w
celu uzyskania populacji potomnej O
t
.
Sukcesja polega na utworzeniu nowej populacji bazowej P
t+1
na podstawie:
osobników z populacji potomnej O
t
(sukcesja z całkowitym
zastępowaniem),
populacji potomnej O
t
oraz starej populacji bazowej P
t
(sukcesja z częściowym zastępowaniem).
Reprodukcja proporcjonalna (ruletkowa)
W reprodukcji proporcjonalnej prawdopodobieństwo
wylosowania osobnika jest wprost proporcjonalna do jego
przystosowania.
p
r
(X) =
Φ(X)
P
Y∈P
t
Φ(Y)
Reprodukcja ruletkowa nie może być stosowana gdy funkcja
przystosowania przyjmuje wartości ujemne.
Reprodukcja proporcjonalna jest „wrażliwa” na dodanie
wartości stałej do funkcji przystosowania.
Intensywność nacisku selektywnego zmniejsza się wraz z
kolejnymi generacjami, ponieważ większość osobników
uzyskuje zbliżone wartości przystosowania.
Na początku działania algorytmu nacisk selektywny jest silny i
może powodować tendencję do przedwczesnej zbieżności.
Modyfikacja reprodukcji ruletkowej
Ograniczenia reprodukcji proporcjonalnej można ominąć
dokonując korekty dopasowania według wzorów:
Φ
0
(X) = Φ(X) − Φ
0
, gdzie ∨
X ∈D
Φ
0
¬ Φ(X)
Φ
0
(X) = Φ(X) − Φ
t
, gdzie Φ
t
¬ inf
X∈P
t
Φ(X).
Pierwszy wzór zapewnia, że wartość funkcji przystosowania nie
będzie ujemna.
Drugi wzór pozwala dodatkowo na utrzymanie nacisku
selektywnego dopóki istnieje choć niewielkie zróżnicowanie
populacji.
Reprodukcja rangowa
W metodzie tej prawdopodobieństwo reprodukcji każdego
osobnika jest wyznaczane na podstawie jego rangi czyli liczby
charakteryzującej tego osobnika na tle innych osobników w
populacji.
Populacja jest sortowana wg nierosnących wartości
przystosowania osobników.
Ranga osobnika odpowiada jego pozycji w szeregu, wartości
rangi są kolejnymi liczbami całkowitymi począwszy od 0.
Możliwe są dwa sposoby określenia rangi dla osobników o tym
samym przystosowaniu:
osobniki o jednakowym przystosowaniu otrzymają różne
wartości rangi,
osobniki o jednakowym przystosowaniu otrzymują tą samą
wartość rangi.
Reprodukcja rangowa –
funkcja pp reprodukcji
Po określeniu rang, przypisuje się każdemu osobnikowi
prawdopodobieństwo reprodukcji na podstawie jego rangi.
Wybór funkcji prawdopodobieństwa reprodukcji dokonywany
jest przez projektanta algorytmu.
Należy zadbać aby funkcja określająca prawdopodobieństwo
była nierosnąca wraz z numerem rangi.
Liniowa funkcja prawdopodobieństwa:
p
r
(X) = a + k(1 −
r (X)
r
max
) gdzie r
max
= max
X ∈P
t
r (X)
Parametry a i k są dobierane tak aby były spełnione warunki:
µ
X
i =1
p
r
(X) = 1 i 0 ¬ p
r
(X) ¬ 1.
Reprodukcja rangowa -
funkcja potęgowa
Reprodukcja rangowa z liniową funkcją prawdopodobieństwa
jest często określana jako mało efektywna.
Inny wariant funkcji prawdopodobieństwa to funkcja potęgowa:
p
r
(X) = a + k(r
max
− r (X))
b
.
Parametry a, b, i k dobiera się podobnie jak w funkcji liniowej.
Parametry p
r
(X) pozwalają na kształtowanie nacisku
selektywnego. Parametr a powoduje globalne osłabienie
nacisku selektywnego. Parametr b zwiększa zróżnicowanie pp
reprodukcji lepszych i gorszych osobników.
Prawdopodobieństwo reprodukcji jest z góry określone dla
każdej rangi i może być stałe lub zmieniać się wraz z
numerem generacji.
Reprodukcja turniejowa
Reprodukcja turniejowa jest dwuetapowa. W pierwszym etapie
wybiera się losowo q „kandydatów do turnieju” Q ⊂ P
t
.
Następnie przeprowadza się turniej miedzy osobnikami z Q, z
którego jest wyłaniany osobnik o największej wartości funkcji
przystosowania. Osobnik ten trafia do populacji potomnej.
Parametrem sterującym intensywnością nacisku selektywnego
jest liczność turnieju q.
Wybór osobników do turnieju może odbywać się na dwa
sposoby:
losowanie ze zwracaniem,
losowanie bez zwracania.
Wariant pierwszy pozwala na reprodukcje wszystkim
osobnikom z niezerowym prawdopodobieństwem. Wariant
drugi powoduje, że q − 1 najgorszych osobników nie będzie w
ogóle reprodukować.
Reprodukcja progowa
Reprodukcja progowa jest szczególnym przypadkiem
reprodukcji rangowej. Funkcja prawdopodobieństwa
reprodukcji ma postać:
p
r
(X) =
(
1
ρµ
dla 0 ¬ r (X) ¬ ρµ
0
w przeciwnym przypadku
Wartość ρ jest wskaźnikiem nacisku selektywnego - im jest
ona mniejsza tym mniej osobników będzie reprodukowac i tym
większa będzie liczebność potomstwa.
W skrajnym przypadku gdy ρ = 1/µ do reprodukcji wybierany
jest tylko jeden osobnik.
Parametr ρ przyjmuje się na poziomie 0, 15 ÷ 0, 5.
Wyszukiwarka
Podobne podstrony:
Algorytmy genetyczne i procesy ewolucyjne Wykład 2
Algorytmy genetyczne i procesy ewolucyjne Wykład 1
Algorytmy genetyczne i procesy ewolucyjne Wykład 5
EgzaminMikrobPytania2008, chemia organiczna, biologia ewolucyjna-wykłady, genetyka, biologia komórki
Fizjologia zwierząt wszystkie opracowania, chemia organiczna, biologia ewolucyjna-wykłady, genetyka,
Algorytmy Ewolucyjne wx algorytmy genetyczne
Egzamin z mikrobiologiiKursDużyGrI2008, chemia organiczna, biologia ewolucyjna-wykłady, genetyka, bi
Proces pielęgnowania wykład 3 ppt
Algorytmy genetyczne
Teorie algorytmow genetycznych prezentacja
Wsparcie jako element procesu pielęgnowania wykład ppt
Podstawy Procesów Polimerowych Wykład 2
ALGORYTM MNOŻENIA PISEMNE GO(1), wykłady i notatki, dydaktyka matematyki, matematyka przedszkole i 1
Algorytm genetyczny – przykład zastosowania
więcej podobnych podstron