Instytut

Podstaw

Konstrukcji

Maszyn

Wydział

Mechaniczny

Technologiczny

Politechnika

Śląska

ul. Konarskiego 18a

44-100 Gliwice

tel. [phone]

fax. [phone]

http://ipkm.polsl.pl

Metody Sztucznej

Inteligencji

Rok akademicki 2012/13

Instrukcja do ćwiczeń laboratoryjnych

Temat:

Algorytmy genetyczne

Opracował: dr inż. G. Urbanek

Gliwice 2013-02-05

1. Cel ćwiczenia

Celem ćwiczenia jest zapoznanie się z algorytmami genetycznymi oraz z ich praktycznym
zastosowaniem.

2. Wprowadzenie teoretyczne

Poszukiwanie rozwiązania optymalnego według algorytmu genetycznego odbywa się poprzez
odpowiednie przekształcanie zbioru elementów (osobników) za pomocą tzw. operatorów ge-
netycznych. Zbiór elementów (osobników) w danej chwili czasu nazywany jest pokoleniem,
zbiór ten przekształcony za pomocą operatorów genetycznych stanowi kolejne pokolenie; prze-
kształcenie takie wykonuje się n-razy. Elementy (osobnicy) przekształcanego zbioru należą
do przestrzeni zadania i są potencjalnymi rozwiązaniami. Każdy element (osobnik) zawiera
informację stanowiącą jego genotyp, który jest przepisem na utworzenie w wyniku oddziaływa-
nia środowiska fenotypu, czyli zbioru cech, na podstawie których funkcja oceniająca (funkcja
przystosowania), określa przystosowanie osobnika. Celem algorytmu genetycznego jest mak-
symalizacja funkcji przystosowania, tzn. rozwiązaniem optymalnym jest osobnik o największej
wartości funkcji przystosowania.

Genotyp osobnika składa się z chromosomów (najczęściej jednego), które składają się z

elementarnych części, zwanych genami. Przykładowo, w zadaniu optymalizacji (poszukiwaniu
maksimum) funkcji f, genotypem osobnika są współrzędne punktu, fenotypem jest wartość
funkcji f w tym punkcie. Wartość funkcji przystosowania jest wyliczana na podstawie fenotypu.

Istotę działania algorytmu genetycznego przedstawia rys. 1.
Przeprowadzenie optymalizacji za pomocą algorytmu genetycznego wymaga określenia na-

stępujących elementów:

Rys. 1: Podstawowy algorytm genetyczny; oznaczenia: t – czas (licznik kroków), P – populacja,
R – rodzice, D – dzieci [5], [3]

- 2/6 -

• podstawowej reprezentacji potencjalnych rozwiązań zadania,

• sposobu tworzenia początkowej populacji potencjalnych rozwiązań,

• funkcji oceniającej,

• sposobu prowadzenia selekcji i sukcesji,

• sposobu prowadzenia reprodukcji (operatory krzyżowania i mutacji),

• wartości różnych parametrów używanych w algorytmie genetycznym (rozmiar populacji,

prawdopodobieństwa użycia operatorów genetycznych itp.).

2.1. Reprezentacja potencjalnych rozwiązań zadania

Metody reprezentacji elementów przestrzeni (nazywanych osobnikami), w której poszukiwane
jest rozwiązanie optymalne można podzielić na dwie grupy [3]:

1. chromosomy z liniowo ułożonymi genami:

• kodowanie binarne,

• kodowanie liczbowe,

• kodowanie specjalne,

2. chromosomy będące złożonymi strukturami genów (np. drzewa)

• kodowanie binarne, liczbowe, specjalne.

Powszechnie w algorytmach genetycznych stosowane są chromosomy z liniowo ułożony-

mi genami kodowanymi binarnie. Wartości wszystkich cech (geny) każdego osobnika zostają
przedstawione za pomocą liczb dwójkowych; „sklejone” razem stanowią chromosom. Repre-
zentacja ta ułatwia analizę teoretyczną i umożliwia wprowadzenie bardzo prostych operatorów
genetycznych. Główną jej wadą jest bardzo duża długość chromosomu dla wielowymiarowych
zadań wymagających dużej dokładności, co prowadzi do bardzo dużej liczebności przestrzeni
przeszukiwania [5].

Innym sposobem jest zapis wartości cech (genów) w postaci dziesiętnej. Chromosom ma

wtedy postać macierzy liczb, każda liczba jest wartością jednej z rozpatrywanych cech. Taki
zapis eliminuje konieczność kodowania chromosomów (przestrzeń reprezentacji jest przestrze-
nią zadania). Stosowanie chromosomów, będących złożonymi strukturami genów, wymaga
opracowania odpowiednich operatorów genetycznych.

2.2. Generowanie rozwiązania początkowego

Populacja początkowa najczęściej (chyba że są uzasadnione podstawy, żeby postąpić inaczej)
generowana jest w sposób losowy. W przypadku kodowania binarnego losuje się wartość każdego
bitu chromosomu (łańcucha binarnego) i w ten sposób tworzy się całą populację. W przypadku

- 3/6 -

kodowania liczbowego, wartość każdego genu jest losowana z przedziału zmienności wartości
cechy, którą on reprezentuje.

2.3. Funkcja oceniająca

Funkcja oceniająca jest jednym z najważniejszych elementów warunkujących skuteczne działa-
nie algorytmu genetycznego. Nieodpowiednia funkcja oceniająca prowadzi do błędnego działa-
nia. Niestety, nie istnieje ogólny „przepis” na opracowanie dobrej funkcji oceniającej. Funkcję
taką zwykle wyznacza się metodą „prób i błędów” indywidualnie do konkretnego zadania.

2.4. Selekcja i sukcesja

Selekcja określa sposób wyłaniania z rozpatrywanej populacji zbioru rodziców, który poddawany
działaniu operacji genetycznych, daje zbiór dzieci. Sukcesja wyznacza dla pokolenia rodziców
i potomków nową populację bazową dla kolejnego kroku algorytmu genetycznego.

Przykłady metod selekcji:

• selekcja proporcjonalna, zwana również metodą ruletki (nazwa pochodzi od najprostszej

realizacji algorytmicznej tego operatora), jest procesem, w którym chromosomy zostają
powielone w stosunku zależnym (wprost proporcjonalnie) od wartości, jakie przybiera dla
nich funkcja oceniająca; stosowanie tej metody jest możliwe tylko wtedy, gdy funkcja
oceniająca przyjmuje wyłącznie wartości dodatnie;

• selekcja turniejowa polega na powtarzaniu dwóch kroków: losowania par osobników wg

metody ruletki, po wylosowaniu pary, osobnik o wyższym przystosowaniu zostaje ogło-
szony zwycięzcą i umieszczony w nowej populacji; proces jest kontynuowany aż do cał-
kowitego wypełnienia populacji.

Przykłady metod sukcesji:

• sukcesja trywialna polega na tym, że nową populacją staje się zbiór dzieci: P[t]:=D[t];

• sukcesja elitarna przeprowadzana jest w dwóch krokach: najpierw wybiera się z P[t-1]

n

najlepszych chromosomów: P

n

[t-1]

, następnie populacja P[t] jest tworzona przez

wybór m najlepszych chromosomów ze złączenia P

n

[t-1]∪[t]

.

2.5. Reprodukcja

Na reprodukcję składają się dwa operatory: krzyżowania i mutacji.

Najczęściej przyjmuje się, że w krzyżowaniu biorą udział dwa osobniki rodzicielskie, w wy-

niku otrzymuje się jeden lub dwa osobniki potomne.

Przykłady metod krzyżowania:

• krzyżowanie proste (jednopunktowe) przebiega w dwóch etapach: w pierwszej fazie koja-

rzy się w sposób losowy ciągi z puli rodzicielskiej w pary. Następnie każda para przechodzi

- 4/6 -

proces krzyżowania. Odbywa się to następująco: wybiera się w sposób losowy (z jednako-
wym prawdopodobieństwem) punkt krzyżowania k spośród l − 1 początkowych pozycji
w chromosomie, po czym zamienia się miejscami wszystkie znaki od pozycji k + 1 do

l

włącznie w obu elementach pary, tworząc w ten sposób dwa nowe ciągi;

• krzyżowanie wielopunktowe przebiega analogicznie jak krzyżowanie jednopunktowe, z tą

różnicą, że wybiera się więcej niż jeden punkt cięcia;

• krzyżowanie jednorodne przebiega następująco: dla każdego bitu pierwszego potomka

decyduje się (z pewnym prawdopodobieństwem), od którego z rodziców pobierze się
wartość, drugi potomek otrzymuje bit od pozostałego rodzica;

• rekombinacja puli genów: kilku rodziców tworzy jednego potomka w ten sposób, że

kolejne geny potomka są wybierane losowo z puli genów wybranych rodziców;

• krzyżowanie arytmetyczne definiuje się jako liniową kombinację dwóch wektorów: jeżeli

krzyżowaniu mają podlegać r

1

i r

2

, to potomkowie wyznaczani są następująco: d

1

=

ar

1

+ (1 − a)r

2

oraz d

2

= ar

2

+ (1 − a)r

1

; wartość a dobiera się losowo z przedziału

[0,1];

• krzyżowanie uśredniające jest operatorem przeznaczonym dla reprezentacji liczbowej;

w metodzie tej wartość każdego genu chromosomu potomnego jest liczbą zawierającą
się między największą i najmniejszą wartością genu chromosomów rodzicielskich. Jeśli
krzyżowanie uśredniające przebiega zgodnie ze schematem, że z pary chromosomów ro-
dzicielskich powstaje para potomnych, wówczas chromosomy potomne będą symetryczne
względem środka odcinka łączącego chromosomy rodzicielskie.

Przykłady metod mutacji:

• mutacja równomierna zmienia jeden lub więcej bitów na przeciwny z określonym praw-

dopodobieństwem;

• mutacja nierównomierna uwzględnia wiek populacji: wraz ze wzrostem wieku populacji

bity znajdujące się bardziej na prawo w sekwencji kodu chromosomu otrzymują większe
prawdopodobieństwo mutacji, znajdujące się zaś na lewo mniejsze;

• mutacja „rzeczywistoliczbowa” stosowana jest wtedy, jeśli geny przyjmują wartości ze

zbioru liczb rzeczywistych, i polega na perturbacji wartości genu przez dodanie liczby
wygenerowanej w sposób losowy.

2.6. Warunki zakończenia działania algorytmu genetycznego

Można określić dwa warunki zakończenia działania algorytmu genetycznego:

• algorytm działa do momentu osiągnięcia osobnika o określonym przystosowaniu,

• pętla while jest wykonywana zadaną liczbę razy.

Najczęściej stosuje się obydwa warunki jednocześnie. Algorytm kończy działania, gdy zo-

stanie spełniony jeden z nich.

- 5/6 -

2.7. Parametry algorytmu genetycznego

Tradycyjnie algorytmy genetyczne, operują na populacji, której liczebność w czasie optymaliza-
cji nie zmienia się. Można zastosować algorytm genetyczny ze zmienną liczebnością populacji.
Algorytm ten nie zawiera żadnej odmiany mechanizmu selekcji, ale wprowadza pojęcie „wieku”
chromosomu, co jest równoważne liczbie pokoleń, przez które chromosom pozostaje „żywy”.
Tak więc wiek chromosomu pozwala na szczególne definiowanie pojęcia selekcji i, ponieważ
zależy on od dopasowania osobnika, wpływa na liczebność populacji w każdym kroku proce-
su [5].

Nie ma zaleceń co do doboru wartości prawdopodobieństwa krzyżowania i mutacji, najczę-

ściej dokonuje się tego doświadczalnie. Zwykle prawdopodobieństwo krzyżowania zawiera się
w przedziale [0,25; 0,75], zaś prawdopodobieństwo mutacji w przedziale [0,005; 0,05].

3. Przygotowanie do ćwiczenia

Przygotowanie do ćwiczenia obejmuje szczegółowe zapoznanie się z niniejszą instrukcją. W cza-
sie ćwiczenia zostanie przedstawione, na prostym przykładzie, działanie algorytmu genetycz-
nego; zostanie sprawdzone przygotowanie studentów do zajęć.

4. Przykłady do samodzielnego rozwiązania

Opracować algorytm genetyczny do optymalizacji funkcji dwóch zmiennych. Zastosować ko-
dowanie liczbowe z liniowo ułożonymi genami w chromosomie.

Literatura

[1] Arabas J.: Algorytmy ewolucyjne: przegląd tematyki. AI-Mech 2000, Materiały konferen-

cyjne, Gliwice 2000, s. 3–23.

[2] Arabas J.: Wykłady z algorytmów genetycznych. WNT, Warszawa, 2001.

[3] Cholewa W.: Wykład z przedmiotu metody heurystyczne. Materiały niepublikowane,

Gliwice, 2001.

[4] Goldberg D.E.: Algorytmy genetyczne i ich zastosowania. WNT, Warszawa, 1998.

[5] Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne.

WNT, Warszawa, 1999.

- 6/6 -

Instrukcja obsługi programu PAG

Program

PAG

został

pierwotnie

napisany

w

programie

Matlab

(http://www.

mathworks.com/products/matlab/),

który

jest

produktem

komercyjnym.

Jednak

istnieje

możliwość

uruchomienia

tego

programu

również

w

darmowym

środowisku

GNU Octave (http://www.gnu.org/software/octave/). W tym celu należy pobrać

odpowiednią wersję tego środowiska (program PAG testowano na wersji 3.6.2) dla odpo-

wiedniego systemu operacyjnego. Standardowo środowisko GNU Octave jest uruchamiane

w wierszu poleceń. Nie jest to wygodny sposób pracy z tym środowiskiem. Żeby poprawić

komfort pracy można zainstalować nakładkę graficzną o nazwie GUI Octave (ostatnia wersja

ma numer 1.5.4).

Dalsza część tego opisu dotyczy środowiska GNU Octave dla systemu MS Windows

uruchomionego w wierszu poleceń. Zakłada się, że program PAG znajduje się w katalogu

C:\PAG. W celu uruchomienia programu PAG należy:

1. Uruchomić program GNU Octave; plik startowy nazywa się octave.exe; pojawi się okno

z wierszem poleceń

2. Wpisać polecenie cd C:\PAG i potwierdzić przyciskiem Enter; poleceniem ls można

sprawdzić czy program ma dostęp do katalogu

3. Wpisać polecenie main i potwierdzić przyciskiem Enter; w wierszu poleceń pojawi się

tekst pokazany na Wydruku 1.

Wydruk 1: Ekran startowy programu PAG



1

2

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

3

ALGORYTM GENETYCZNY DO OPTYMALIZACJI FUNKCJI 2 ZMIENNYCH

4

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

5

6

W y b i e r z f u n k c j e do o p t y m a l i z a c j i :

7

8

1 :

Z = − (X^2 + Y^2 − 5 0 )

9

10

2 :

Z=−( s i n ( ( 0 . 7 5 ∗ X) . ^ 2 + ( 0 . 7 5 ∗ Y) . ^ 2 ) + a b s (X) + a b s (Y) − 1 0 )

11

12

3 :

Z = −( s i n ( ( 0 . 7 5 ∗ X) . ^ 2 + ( 0 . 7 5 ∗ Y) . ^ 2 ) + s q r t (X. ^ 2 + Y. ^ 2 ) − 8 )

13

14

N a c i s n i j o d p o w i e d n i k l a w i s z ( d o m y s l n i e 1 ) :





Następnie:

1. W oknie pokazanym na Wydruku 1. należy określić funkcję, która będzie poddana proce-

sowi optymalizacji (poszukiwania jej maksimum) - należy wybrać z klawiatury odpowiedni

numer i potwierdzić przyciskiem Enter. UWAGA1! Otworzy się nowe okno z wykresem

Gliwice 2013-02-05

trójwymiarowym ilustrującym postać wybranej funkcji. Wykres można obracać używając

lewego przycisku myszy.

Wydruk 2: Kolejne etapy pracy z programem PAG dla wartości domyślnych



1

Wprowadz w i e l k o s c

p o p u l a c j i p o p s i z e ( d o m y s l n i e 4 0 ) : 40

2

p o p s i z e =

40

3

Wprowadz l e w y k o n i e c p r z e d z i a l u z m i e n n e j x x l e f t ( d o m y s l n i e −5) :

−5

4

x l e f t = −5

5

Wprowadz prawy k o n i e c p r z e d z i a l u z m i e n n e j x x r i g h t ( d o m y s l n i e 5 ) :

5

6

x r i g h t =

5

7

<e n n e j x z p r z e d z i a l u <0,4> x p r e c i s e ( d o m y s l n i e 4 ) : 4

8

x p r e c i s e =

4

9

x l b i t s =

17

10

Wprowadz l e w y k o n i e c p r z e d z i a l u z m i e n n e j y y l e f t ( d o m y s l n i e −5) :

−5

11

y l e f t = −5

12

Wprowadz prawy k o n i e c p r z e d z i l a u z m i e n n e j y y r i g h t ( d o m y s l n i e 5 ) :

5

13

y r i g h t =

5

14

<e n n e j y z p r z e d z i a l u <0,4> y p r e c i s e ( d o m y s l n i e 4 ) : 4

15

y p r e c i s e =

4

16

y l b i t s =

17

17

Wprowadz l i c z b e

g e n e r a c j i ( p o k o l e n ) n g e n e r a t i o n ( d o m y s l n i e 1 0 ) : 10

18

n g e n e r a t i o n =

10

19

<o w a n i a p c r o s s z p r z e d z i a l u <0,1> ( d o m y s l n i e 0 . 7 5 ) : 0 . 7 5

20

p c r o s s =

0 . 7 5 0 0 0

21

< j i

p m u t a t i o n z p r z e d z i a l u <0,1> ( d o m y s l n i e 0 . 0 0 2 ) : 0 . 0 0 2

22

p m u t a t i o n =

0 . 0 0 2 0 0 0 0

23

24

C z e s c o b l i c z e n i o w a . P r o s z e c z e k a c . . .





2. W oknie pokazanym na Wydruku 2. należy określić parametry algorytmu genetycznego

wprowadzając odpowiedni numer z klawiatury i potwierdzić wybór przyciskiem Enter.

3. Po wprowadzeniu parametrów, program wykona następujące czynności:

(a) Przeprowadzi proces optymalizacji zgodnie z wprowadzonymi danymi i parame-

trami.

(b) Zilustruje wynik procesu optymalizacji w formie wykresu trójwymiarowego (Rys. 1),

na którym będzie widoczny wykres funkcji wraz z naniesionymi osobnikami ostatniej

populacji w postaci punktów.

(c) Wyliczy i wypisze w wierszu poleceń wartości przystosowania osobników ostatniej

populacji, całkowitą liczbę krzyżowań, całkowitą liczbę mutacji, najlepszych osob-

Gliwice 2013-02-05

-4

-2

0

2

4

-4

-2

0

2

4

0

10

20

30

40

50

Funkcja optymalizowana numer 1

X

Y

Rysunek 1: Przykładowy wynik procesu optymalizacji

ników w każdej i-tej populacji, maksymalną wartość funkcji celu (przystosowania)

wyznaczoną przez algorytm genetyczny, z określeniem w której iteracji miało to

miejsce oraz wartość dokładną maksimum optymalizowanej funkcji.

(d) Zakończy swoje działanie.

Gliwice 2013-02-05