Algorytmy genetyczne i procesy ewolucyjne
Jacek Bieganowski
Instytut Informatyki i Elektroniki
Uniwersytet Zielonogórski
email: J.Bieganowski@iie.uz.zgora.pl
http://www.uz.zgora.pl/~jbiegano/agipe08
30 marca 2009
Problem plecakowy
Dany jest zbiór artykułów (rzeczy) wraz z ich wartościami i
rozmiarami. Należy wybrać podzbiór rzeczy, tak aby suma
rozmiarów nie przekroczyła zadanego ograniczania (pojemności
plecaka) i aby suma wartości była jak największa.
Zadanie polega na określeniu wektora binarnego X = hx
1
, . . . , x
n
i
takiego, że
n
X
i =1
X
i
W
i
¬ C
i dla którego
Z =
n
X
i =1
X
i
P
i
jest maksymalne.
W = [10, 12,
7, 1, 20]
P
= [8,
4, 20, 1, 10]
X
= [1,
1,
0, 0,
1]
C = 20; z(X ) = 8 + 4 + 10, w (X ) = 10 + 12 + 20 = 42
Jak radzić sobie z ograniczeniami?
Karanie osobników, które nie spełniają ograniczeń przez
zmiejszenie przystosowania (funkcja kary). W skrajnym
przypadku można zmniejszyć przystosowanie do 0 tzw. kara
śmierci.
Zastosować metodę naprawy chromosomu, tak aby
chromosom spełniał założenia zadania.
Opracować specjalistyczne operatory genetyczne (oraz
procedury inicjalizacji), które nie generują rozwiązań
niedopuszczalnych.
Funkcja kary dla zadania plecakowego
Karane są tylko osobniki niespełniające ograniczenia przez
odjęcie wartości K (X )
Φ =
n
X
i =1
X
i
P
i
− K (X )
Funkcja kary powinna być proporcjonalna do tego jak mocno
zostało przekroczone ograniczenie.
Liniowa funkcja kary K (X ) =
P
n
i =1
X
i
P
i
− C ,
Kwadratowa funkcja kary K (X ) = (
P
n
i =1
X
i
P
i
− C )
2
.
Algorytmy naprawy dla problemu plecakowego
Naprawa losowa polegająca na usunięciu losowych elementów
z plecaka, aż do spełnienia ograniczenia.
Naprawa zachłanna polegajaca na usunięciu z plecaka
elementów, których stosunek zysku do wagi (P/W ) jest
najgorszy.
Reperezentacja porządkowa
Można wykorzystać klasyczny operator krzyżowania
jednopunktowego.
Wszystkie trasy uzyskane w wyniku krzyżowania są
dopuszczalne.
Zadanie komiwojażera (1)
Komiwojażer ma odwiedzić każde miasto na swoim terytorium
dokładnie raz i powrócić do punktu startowego. Trasę należy
wytyczyć, znając koszt (odległość) przejazdu między
poszczególnymi miastami, w taki sposób, aby koszt przejazdu był
najmniejszy.
Zadanie komiwojażera (2)
Przestrzeń rozwiązań jest
zbiorem permutacji n
miast,
Rozmiar przestrzeni
rozwiązań wynosi n!,
Dla n = 10 problem ma
181 000 rozwiązań,
Dla n = 20 rozwiązań jest
10 000 000 000 000 000,
Dla n = 50 możliwych
rozwiązań jest 10
62
.
Krzyżowania dla reprezentacji ścieżkowej
Krzyżowanie z częściowym odwzorowaniem (ang.
patrially-mapped crossover – PMX) – operator tworzy
potomstwo w taki sposób aby zachować pozycje oraz prządek
tak wielu miast z drugiego rodzica jak to jest tylko możliwe.
Krzyżowanie z zachowaniem porządku (ang. order crossover –
OX) – operator stara się tworzyć ścieżki w taki sposób aby jak
najmniej zaburzyć kolejność miast.
Krzyżowanie cykliczne (ang. cycle crossover – CX) – operator
tworzy potomstwo w taki sposób aby każde miasto i jego
pozycja pochodziło od jednego z rodziców.
Optymalizacja rurociągu gazowego (1)
Zachowanie systemu opisane przez układ równań nieliniowych.
Należy zminimalizować całkowity pobór mocy przy zadanym
minimalnym i maksymalnym ciśnieniu.
Rurociąg składa się z 10 przewodów i 10 kompresorów.
Parametry algorytmu:
rozmiar populacji µ = 50,
pp krzyżowania p
c
= 1, 0,
pp mutacji p
m
= 0, 001.
4 bitowy kod dla każdego parametru, 10 bloków tworzy
chromosom.
Optymalizacja konstrukcji (1)
Zminimalizowanie ciężaru całkowitego struktury (kraty) przy
zachowaniu minimalnych i maksymalnych naprężeń każdego z
elementów.
Parametry: 10 pól po jednym dla każdego elementu
składowego.
10 bitowy podciąg dla każdego elementu reprezentujący
wartości z przedziału A
min
= 0, 1 do A
max
= 10 (cale kw.).
Do rozwiązania zadania wykorzystano algorytm genetyczny z
selekcją met. ruletki, krzyżowaniem i mutacją.
Ocenę chromosomów zrealizowano za pomocą standardowego
programu do analizy kratownic.
Optymalizacja konstrukcji (2)
Goldberg i Samtani, 1986
Optymalizacja konstrukcji (3)
Goldberg i Samtani, 1986
Obróbka obrazów rentgenowskich (1)
Algorytm genetyczny wykorzystano do porównania dwóch
obrazów rentgenowskich w badaniach wnętrza tętnicy.
Pierwszy z obrazów przedstawia tętnicę przed wstrzyknięciem
środka cieniującego, natomiast drugi po tym zabiegu.
Oba obrazy są porównywane (odejmowane punkt po punkcie)
w celu uzyskania obrazu różnicowego przedstawiającego obraz
badanej tętnicy.
Drobne ruchy pacjenta utrudniają operację porównania
obrazów – następują przesunięcia między obrazami.
Zadaniem algorytmu genetycznego jest wyznaczenie
współczynników równań określających przekształcenie
obrazów, tak aby zminimalizować różnicę między obrazami.
x
0
(x , y ) = a
0
+ a
1
x + a
2
y + a
3
xy
y
0
(x , y ) = b
0
+ b
1
x + b
2
y + b
3
xy
Obróbka obrazów rentgenowskich (2)
Pełny obraz tworzy siatkę 100 x 100 punktów. Współrzędne
każdego z wierzchołków obrazu zakodowano jako 8 bitowe
podciągi reprezentujące przesunięcia w granicach od -8 do 8
pikseli.
Algorytm działał na 64 bitowych chromosomach, wyznaczenie
wartości funkcji przystosowania wymagało obliczenia około
10
4
przekształceń oraz operacji odejmowania punktów.
Autorzy rozwiązania zmniejszyli nakład obliczeń związany z
obliczeniem funkcji redukując liczbę porównywanych punktów.
Pomysł redukcji liczby porównywanych punktów sprawdzono
wykonując 200 000 operacji odejmowania pikseli dla różnego
rozmiaru próby.
Badania pokazały, że wystarczy porównać jedynie 10 punktów
z 10 000 i nadal otrzymywać dobre rezultaty.
Rezultaty badań pokazują, że algorytmy działają poprawnie
nawet w przypadku niedokładnych i zakłóconych wartości
funkcji przystosowania.
Iterowany dylemat więźnia (1)
Każdy z dwóch uczestników gry może wybrać między
współpracą i zdradą. W zależności od decyzji każdy gracz
otrzymuje wypłatę zgodnie z tabelą:
WSPÓŁPRACA
ZDRADA
WSPÓŁPRACA
R=6 R=6
S=0 F=10
ZDRADA
S=10 T=0
P=2 P=2
W komputerowych potyczkach największą skuteczność
wykazała strategia „wet za wet”, która nakazuje
współpracować w pierwszym ruchu, a następnie naśladować
ruchy przeciwnika.
Axelrod zaproponował algorytm genetyczny podejmujący
decyzję o kolejnym ruchu na podstawie 3 ostatnich ruchów.
Wszystkie możliwości dla jednego ruchu można zakodować
następująco:
WW = 00, WZ = 01, ZW = 10, ZZ = 11
Iterowany dylemat więźnia (2)
Chromosom reprezentuje zachowanie osobnika dla każdej
permutacji 3 ostatnich ruchów, 6 dodatkowych bitów określa
strategię początkową.
Badania przeprowadzono tworząc turniej, w którym
uczesniczyło 8 zawodników reprezentujących różne strategie
gry.
W każdym pojedynku wykonywano 151 ruchów, AG walczył
ze wszystkimi przeciwnikami.
Populacja w AG składała się z 20 osobników, funkcja
przystosowania była określona na podstawie średniej ważonej
wyników z poszczególnymi przeciwnikami.
Algorytm genetyczny zdołał pokonać strategię „wet za wet”.
Wyszukiwarka
Podobne podstrony:
Algorytmy genetyczne i procesy ewolucyjne Wykład 3
Algorytmy genetyczne i procesy ewolucyjne Wykład 2
Algorytmy genetyczne i procesy ewolucyjne Wykład 1
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