Algorytmy genetyczne i procesy ewolucyjne

Wykład 1 – Wprowadzenie

Jacek Bieganowski

Instytut Informatyki i Elektroniki

Uniwersytet Zielonogórski

email: [e-mail]

2 marca 2009

Algorytmy genetyczne i procesy ewolucyjne – W1

Plan wykładu (1)

1.

Wprowadzenie

Omówienie tradycyjnych metod poszukiwania i optymalizacji, krótka

historia obliczeń ewolucyjnych, jak działają algorytmy genetyczne, ręczna

symulacja.

2.

Implementacja algorytmu genetycznego

Kodowanie chromosomów, implementacja met. ruletki, implementacja

krzyżowania i mutacji.

3.

Metody selekcji

Eksploracja i eksploatacja, nacisk selektwyny, reprodukcja proporcjonalna,

reprodukcja rangowa, reprodukcja turniejowa, reprodukcja progowa,

skalowanie przystosowania, kryteria zatrzymania algorytmu.

4.

Kodowanie i operatory genetyczne

Schematy, twierdzenie o schematach, porządane cechy operatorów

genetycznych, operatory krzyżowania wymieniającego, operatory

krzyżowania uśredniającego, operatory mutacji, zasięg operatorów.

Algorytmy genetyczne i procesy ewolucyjne – W1

Wykłady 4–7

5.

Przykładowe zastosowania algorytmów genetycznych

Zadanie załadunku (plecakowe), problem komiwojażera, układanie planu

zajęć i inne.

6.

Kolokwium

Materiał obejmujący wykłady 1–5

7.

Strategie ewolucyjne

Strategie 1+1, µ + λ oraz µ, λ, programowanie ewolucyjne.

8.

Programowanie genetyczne

9.

Zaawansowane operacje i techniki I

Dominowanie i maskowanie, inwersja, nisze, koewolucja, algorytmy z

miękką selekcją i inne.

10.

Zaawansowane operacje i techniki II

Algorytmy genetyczne i procesy ewolucyjne – W1

Wykłady 12-14

11.

Wielokryterialne podejmowanie decyzji

Optimum w sensie Pareto. Algorytmy stosowane w opytmalizacji

wielokryterialnej: VEGA, HLGA, FFGA, NPGA, NSGA, SPGA.

12.

Kolokwium II

Materiał obejmujący wykłady 8–13.

Algorytmy genetyczne i procesy ewolucyjne – W1

Literatura

1.

Z. Michalewicz, D. B. Fogel, Jak to rozwiązać czyli
nowoczesna heurystyka

, WNT 2006

2.

David E. Goldberg, Algorytmy genetyczne i ich zastosowania,

WNT, Warszawa 1998;

3.

Jarosław Arabas, Wykłady z algorytmów ewolucyjnych, WNT,

Warszawa 2001;

4.

Zbigniew Michalewicz, Algorytmy genetyczne + struktury
danych = programy ewolucyjne

, WNT, Warszawa 1999;

5.

Roman Galar, Miękka selekcja w losowej adaptacji globalnej w
R

n

Próba biocybernetycznego ujęcia rozwoju

, Wydawnictwo

Politechniki Wrocławskiej, Wrocław 1990;

Algorytmy genetyczne i procesy ewolucyjne – W1

Zaliczenie wykładu

I

Kolokwia i egzaminy są w formie testów wyboru z pytaniami

zawierającymi wiele prawidłowych odpowiedzi.

I

Zwolnienie z egzaminu można otrzymać zaliczając kolokwium

I i II. Ocena końcowa jest wystawiana na podstawie sumy

punktów zdobytych w obu testach.

I

Do kolokwium II są dopuszczone tylko osoby, które zaliczą

kolowium I (zdobędą więcej niż 60% punktów).

I

Osoby, które nie zdobędą wystarczającej liczby punków z

kolokwiów piszą egzamin.

I

Nie ma możliwość poprawiania kolokwiów lub pisania ich w

innym terminie niż cała grupa.

Algorytmy genetyczne i procesy ewolucyjne – W1

Terminy egzaminów

I

Egzamin

19.06.2009 sala 316 A–2 godz. 9:15

Algorytmy genetyczne i procesy ewolucyjne – W1

Rozwój algorytmów ewolucyjnych

I

1957-1962

: Barricelli, Fraser, Martin i Cockerham –

symulacje procesów genetycznych

I

1962

: Holland – praca nad systemami adaptacyjnymi,

powstaje algorytm genetyczny

I

1965

: Rechenberg, 1981 Schwefel – optymalizacja urządzeń

mechanicznych metodą permutowania pewnego początkowego

rozwiązania – powstają strategie ewolucyjne

I

1966

: Fogel, Owens i Walsh – prace nad automatami

skończonymi, z których każdy miał rozpoznawać pewien

nieznany mu języku – początek programowania
ewolucyjnego

I

1967

: Bagley – adaptacyjny program gry w sześć pionków

I

1990

: Koza: zastosowanie algorytmów genetycznych do

automatycznego pisania programów w języku LISP –
genetyczne programowanie

Algorytmy genetyczne i procesy ewolucyjne – W1

Czym są algorytmy ewolucyjne?

Definicja

Algorytmy poszukiwania maksymalnej wartości funkcji
przystosowania

oparte na mechanizmach doboru naturalnego oraz

dziedziczności łączące ewolucyjną zasadę przeżycia najlepiej
przystosowanych

z systematyczną choć zrandomizowaną

wymianą informacji

[Goldberg]

I

Populacja osobników

I

Osobniki konkurują ze sobą

I

Wygrywają osobniki z lepszym dopasowaniem

I

Potomek jest mutacją rodzica

Algorytmy genetyczne i procesy ewolucyjne – W1

Schemat algorytmu genetycznego

Środowisko

Inicjalizacja

Sukcesja

Ocena

Reprodukcja

Operacje

genetyczne

Algorytmy genetyczne i procesy ewolucyjne – W1

Terminy genetyczne i ich odpowiedniki

Definicja

genotyp

– kod pozwalający na utworzenie fenotypu, punkt w

przestrzeni kodów

Definicja

fenotyp

– zestaw cech określanych przez genotyp, punkt w

przestrzeni rozwiązań problemu

biologia

komputer

chromosom

ciąg bitów

gen

bit

allel

cecha

osobnik

punkt w przestrzeni

populacja

zbiór punktów

krzyżowanie

wymiana ciągu bitów

mutacja

negacja bitów

środowisko

funkcja przystosowania

Algorytmy genetyczne i procesy ewolucyjne – W1

Selekcja

Algorytmy genetyczne i procesy ewolucyjne – W1

Krzyżowanie

0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1

1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0

0 1 0 0 1

1 0 1 0 1

1 0 1 0 1 0 1 0 1 1 0

1 0 0 1 1 0 1 0 1 0 1

0 1 0 0 1

1 0 1 0 1

1 0 1 0 1 0 1 0 1 1 0

1 0 0 1 1 0 1 0 1 0 1

Algorytmy genetyczne i procesy ewolucyjne – W1

Algorytm genetyczny – symulacja

i

X

i

Φ(X

i

)

p

r

(X

i

)

P

r

(X

i

)

k

Z

i

Y

i

Φ(Y

i

)

1 01101

169

0,144

0,144 1 01101 01100

144

2 11000

576

0,492

0,636 2 11000 11001

625

3 01000

64

0,055

0,691 0 11000 11011

729

4 10011

361

0,309

1 1 10011 10000

256

1170

1

4

1754

i – numer osobnika
X

i

– genotyp osobnika

Φ(X

i

) – przystosowanie osobnika

p

r

(X

i

) – prawdopodobieństwo reprodukcji

P

r

(X

i

) – dystrybuanta rozkładu reprodukcji

k – oczekiwana liczba kopii
Z

i

– genotyp osobnika potomnego (po reprodukcji)

Y

i

– genotyp nowego osobnika

Φ(Y

i

) – przystosowanie nowego osobnika

p

r

(X) =

Φ(X)

P

Y∈Pt

Φ(Y)

P

r

(X

i −1

) < a ¬ P

r

(X

i

)

Algorytmy genetyczne i procesy ewolucyjne – W1

Pojedyńcze uruchomienie AE (1)

Algorytmy genetyczne i procesy ewolucyjne – W1

Pojedyńcze uruchomienie AE (2)

Algorytmy genetyczne i procesy ewolucyjne – W1

Klasyczne metody optymalizacji i poszukiwania

I

Metody analityczne.

Metody pośrednie - polegające na

rozwiązaniu układu równań (zazwyczaj nieliniowych)

otrzymanych przez przyrównanie gradientu funkcji celu do

zera. Metody bezpośrednie - polegające na poruszaniu się po

wykresie funkcji w kierunku wyznaczonym przez lokalny

gradient.

I

Przeszukiwanie wyczerpujące (wyliczeniowe,
enumeratywne)

. Algorytm oblicza wartość funkcji celu,

przeglądając wszystkie punkty skończonej przestrzeni np.

sprawdzenie po kolei wszystkich rozwiązań lub wyszukiwanie z
nawrotami

przy przeszukiwaniu drzewa w głąb (DFS).

I

Metody stochastyczne.

Metoda Monte Carlo, błądzenie

przypadkowe oraz inne metody oparte na wielokrotnym

losowaniu punktu w przestrzeni i zapamiętywaniu najlepszego

rozwiązania.

Algorytmy genetyczne i procesy ewolucyjne – W1

Różnice między algorytmami genetycznymi
i tradycyjnymi metodami

I

Algorytmy genetycznie nie przetwarzają bezpośrednio

parametrów zadania, lecz ich zakodowaną postać.

I

Poszukiwanie w algorytmach genetycznych odbywa się w wielu

punktach jednocześnie (populacja).

I

Algorytmy genetyczne korzystają tylko z funkcji celu, nie zaś z

jej pochodnych i innych pomocniczych informacji.

I

Algorytm genetyczny stosuje probabilistyczne, a nie

deterministyczne reguły wyboru.

Algorytmy genetyczne i procesy ewolucyjne – W1