ALGORYTMY GENETYCZNE

(wykład + ćwiczenia)

Prof. dr hab. Krzysztof Dems

Treści programowe:

1. Metody rozwiązywania problemów matematycznych i

informatycznych.

2. Elementarny algorytm genetyczny: definicja algorytmu

genetycznego i jego schemat; analiza działania
algorytmu genetycznego.

3. Reprezentacja danych w algorytmie genetycznym,

kodowanie binarne i rzeczywiste.

4. Metody selekcji.
5. Operatory genetyczne.
6. Funkcja przystosowania i jej charakterystyka.
7. Reprezentacja genotypu – diploid i dominacja
8. Zastosowania algorytmów genetycznych.

Literatura:

•

T. Gwiazda, Algorytmy genetyczne, Biblioteka

Sztucznej Inteligencji, Warszawa, 1995

•

J. Cytowski, Algorytmy genetyczne – Podstawy i

zastosowania, Akademicka Oficyna Wydawnicza,
Warszawa, 1996

•

D. E. Goldberg, Algorytmy genetyczne i ich

zastosowania, WNT, Warszawa, 1998

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

2

Treść ćwiczeń:

•

Kodowanie binarne i rzeczywiste chromosomu.

•

Przekształcenie i skalowanie funkcji przystosowania.

•

Ograniczenia zbioru rozwiązań.

•

Metody selekcji deterministycznej i stochastycznej.

•

Operatory genetyczne.

•

Analiza działania algorytmu genetycznego.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

3

Metody rozwiązywania problemów

matematycznych i informatycznych

Rzeczywistość

⇒

Model fizyczny

⇒

Model matematyczny

⇓

Rozwiązanie

⇐











∗

∗

max.)

lub

(min.

cyjny

optymaliza

Problem

równań

wiele

lub

Jedno

Rozwiązywanie równań można sprowadzić do rozwiązania

problemu optymalizacyjnego

.

min

)]

(

[

0

)

(

2

→

⇔

=

x

f

x

f

lub

[

]

.

min

)

,

.

.

.

,

,

(

0

)

,

.

.

.

,

,

(

2

1

2

1

,

.

.

.

,

2

,

1

2

1

→

⇔

=

∑

=

=

n

i

n

i

n

i

n

i

x

x

x

f

x

x

x

f

Przykład:

)

3

,

1

(

0

3

4

2

1

2

=

=

=

+

−

x

x

x

x

c

.

min

)

3

4

(

)

(

2

2

→

+

−

=

x

x

x

g

0

1

2

3

4

x

0

2

4

6

8

10

g

(x

)

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

4

Metody rozwiązania:

•

Analityczne

•

Enumeracyjne

•

Losowe

Metody analityczne:

nieskończona przestrzeń poszukiwań

- (1) pośrednie

- (2) bezpośrednie

Ad. (1): poszukuje się lokalnych minimów rozwiązując układ
równań wynikający z warunku zerowania się gradientu
funkcji celu.

Ad. (2): ‘skakanie’ po wykresie funkcji w kierunku
wskazywa-nym przez lokalny gradient w celu osiągnięcia
lokalnego maximum (wierzchołka).

Wady:

•

Zakres lokalny.

•

Wymagana gładkość i

ciągłość funkcji.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

5

Metody enumeracyjne:

skończona przestrzeń poszukiwań

Oblicza się kolejno wartości funkcji celu przeglądając

wszyst-

kie możliwe

punkty przestrzeni.

Wady:

•

Metoda nieefektywna wraz ze wzrostem rozmiaru

problemu.

Niech będzie danych n niewiadomych, z których każda może
przyjąć m wartości:

Ilość możliwych rozwiązań:

n

m

Np.:

1. n = 5 , m =10

⇒

5

10

=

n

m

= 100 tys. rozwią

zań.

1000 rozwiązań jest sprawdzanych w ciągu 1 sekundy

⇒

czas

znalezienia rozwiązania:

100 sek

.

2. n = 20 , m =10

⇒

20

10

=

n

m

=

8

10

bilionów rozwiązań.

1000 rozwiązań jest sprawdzanych w ciągu 1 sekundy

⇒

czas

znalezienia rozwiązania:

3,17x10

9

lat

.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

6

Metody losowe:

skończona przestrzeń poszukiwań

Oblicza się kolejno wartości funkcji celu przeglądając

losowo

wybrane

punkty przestrzeni ⇒ czas znalezienia rozwiązania

może być istotnie skrócony w porównaniu z metodami
enumeracyjnymi

.

Cechy:

•

Ocena jak największej liczby rozwiązań w różnych

obszarach przestrzeni.

•

Dokładne zbadanie najbardziej obiecujących obszarów.

Rodzaje:

•

Metody czysto losowe – metoda Monte Carlo.

•

Algorytmy genetyczne

– wybór losowy jest traktowany

jako

„przewodnik”

w

prowadzeniu

wysoce

ukierunkowanego poszukiwania w przestrzeni rozwiązań.

Efektywność metod:

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

7

ALGORYTMY GENETYCZNE

(AG)

Teoria AG powstała w oparciu o analogie do

procesów obserwowanych w ewolucji naturalnej.

Przyroda ożywiona:

•

W jądrach komórkowych żywych organizmów znajdują

się

łańcuchy

genów

(chromosomy)

w

których

zakodowana jest informacja o strukturze danego
organizmu.

•

W wyniku krzyżowania się organizmów, dobieranych w

wyniku selekcji, powstaje nowe potomstwo, któremu
rodzice przekazują geny tworząc nową strukturę
chromosomu – a więc informacje o strukturze
organizmu który powstaje (proces reprodukcji).

•

Pojawiający się rzadko proces mutacji zmienia łańcuch

genów, a więc i strukturę organizmu (proces
reprodukcji

).

•

Naturalna

selekcja

jest

pomostem

łączącym

chromosomy

i

‘jakość’

organizmów

przez

nie

‘opisywanych’.

•

Reprodukcja jest momentem w którym następuje

ewolucja organizmu.

•

Ewolucja nie posiada pamięci – wiedza o metodzie

stworzenia nowego organizmu zdolnego do wygrania
walki ‘o przetrwanie’ jest zawarta w genach
chromosomów przez nią wytwarzanych.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

8

Algorytmy genetyczne:

•

Początki zastosowań datują się od roku 1975.

•

Za ojca AG jest uważany J. Holland, który postawił tezę,

ż

e poprzez odpowiednie zaimplementowanie procesów

ewolucyjnych występujących w przyrodzie ożywionej w
formie algorytmu komputerowego otrzymamy metodę
rozwiązywania złożonych problemów tą samą drogą jaką
kroczy natura – drogą ewolucji.

(J. Holland, „Adaptation In natural and artifical
systems”, University of Michigan Press, 1975

)

⇓

Klasyczny model algorytmu genetycznego