Ćwiczenie 5 Algorytmy Genetyczne
Opracował: K. Dziedzicki
Korzystając z dołączonego przybornika rozwiązać
Zadanie 1
Wybrać postać analityczną funkcji do punktów w kolumnie poniższej tabeli podanej przez
prowadzącego. Dla przyjętej funkcji wyznaczyć parametry zapewniające najlepszą
(wg normy ||N||
2
) aproksymację.
Tablica 1 Zestawienie danych do zadania 1
X
Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Y12 Y13 Y14 Y15
Y16*
0.0 9.984 13.013 21.994 14.010 18.014 -0.010 0.013 0.006 -0.005 -0.005 0.045 -0.025
0.033 -0.044 -0.046 -0.025
0.1 6.711 10.649 13.357 12.669 10.922 3.890 1.334 2.368 1.419 2.006 3.940 5.610 7.525 4.101 7.811 12.879
0.2 4.503 8.703 8.109 11.454 6.609 6.760 2.553 4.295 2.731 3.618 7.172 10.154 14.153 7.919 14.144 14.745
0.3 2.999 7.121 4.902 10.362 4.019 8.917 3.620 5.876 3.899 4.948 9.362 12.711 19.124 10.997 17.539 8.166
0.4 2.006 5.854 2.978 9.393 2.430 10.471 4.602 7.150 4.939 6.052 10.016 12.669 21.652 13.054 17.532 -0.623
0.5 1.361 4.787 1.814 8.494 1.472 11.641 5.494 8.229 5.890 6.956 9.077 10.094 21.665 13.931 14.023 -6.173
0.6 0.910 3.912 1.079 7.686 0.884 12.514 6.330 9.083 6.762 7.682 6.791 5.559 19.013 13.659 7.715 -6.606
0.7 0.614 3.210 0.667 6.967 0.527 13.169 7.056 9.808 7.551 8.271 3.393 -0.060 14.068 12.114 -0.168 -3.426
0.8 0.413 2.628 0.393 6.298 0.314 13.626 7.713 10.390 8.246 8.785 -0.631 -5.774
7.359 9.498 -7.972 0.497
0.9 0.280 2.158 0.240 5.686 0.202 13.984 8.312 10.847 8.914 9.185 -4.420 -10.270 -0.163 5.936 -14.225 2.934
1.0 0.192 1.766 0.155 5.149 0.134 14.260 8.857 11.253 9.471 9.499 -7.542 -12.708 -7.696 1.968 -17.624 2.918
1.1 0.137 1.451 0.103 4.652 0.063 14.454 9.325 11.567 10.018 9.778 -9.510 -12.654 -14.301 -2.177 -17.475 1.426
1.2 0.072 1.178 0.063 4.217 0.051 14.577 9.800 11.818 10.469 9.995 -9.998 -10.002 -19.217 -6.168 -13.921 -0.323
1.3 0.062 0.961 0.046 3.829 0.024 14.691 10.189 12.035 10.907 10.189 -8.872 -5.470 -21.688 -9.653 -7.541 -1.343
1.4 0.049 0.786 0.022 3.459 0.028 14.778 10.556 12.219 11.306 10.340 -6.318 0.235 -21.582
-12.175 0.317 -1.260
1.5 0.020 0.652 0.005 3.117 -0.003 14.850 10.866 12.345 11.663 10.463 -2.823 5.890 -18.941
-13.636 8.118 -0.550
1.6 0.001 0.536 0.017 2.842 0.009 14.866 11.162 12.475 11.970 10.546 1.168 10.310 -13.879
-13.951 14.283 0.254
1.7 0.005 0.427 -0.010 2.549 -0.003 14.900 11.457 12.551 12.272 10.621 4.917 12.757 -7.174 -12.941 17.607 0.604
1.8 0.008 0.343 -0.004 2.312 0.002 14.926 11.689 12.654 12.535 10.693 7.976 12.595
0.374 -10.770 17.432 0.586
1.9 -0.009 0.283 0.012 2.091 0.001 14.944 11.895 12.722 12.770 10.745 9.714 10.003
7.870 -7.758 13.853 0.198
2.0 -0.009 0.235 0.005 1.888 0.009 14.963 12.098 12.764 12.958 10.809 9.863 5.342 14.435 -3.923 7.394 -0.149
Zadanie 2
Przedsiębiorstwo produkcyjne wytwarza 2 rodzaje produktów A i B, w ciągu godziny może
wyprodukować 14t wyrobu A i 7t wyrobu B. Posiadany transport pozwala na przewiezienie w
ciągu godziny do 7t produktu A i do 12t produktu B. Urządzenia załadowcze pozwalają
załadować nie więcej niż 20t dowolnego z produktów. Przedsiębiorstwo otrzymuje 5000
PLN/t produktu A i 6000 PLN/t B. Dodatkowo jeśli sprzedaż produktu A jest większa niż 8t
jego cena spada o 10% to samo dzieje się z ceną produktu B po przekroczeniu 5t sprzedaży.
Jaką ilość produktów przedsiębiorstwo powinno produkować aby uzyskać maksymalny
dochód. Założyć że cała produkcja jest sprzedawana.
Przykład
Dla funkcji celu posiadającej optima lokalne poszukiwanie rozwiązania metodami
deterministycznymi nie ma pewności, że otrzymany wektor zmiennych decyzyjnych
odpowiada optimum globalnemu. Dodatkowo jeśli funkcja celu lub ograniczenia zawierają
punkty nieciągłości rozwiązanie problemu może być bardzo trudne a w skrajnych
przypadkach niemożliwe. W problemie optymalizacyjnym sformułowanym poniżej
max f(X)=[(x
1
- 1)(x
1
- 5)
2
(x
1
- 10)][-(x
2
- 5)
2
/25
+
1]
(1)
x
1
, x
2
∈
Ω
x
1
≥ 1
Ω
:
x
1
≤ 10
x
2
≥ 0
x
2
≤ 10
funkcja celu zawiera dwa punkty maksymalne. Rozwiązanie metodami deterministycznymi
nie zawsze daje zadawalające rezultaty i zależy od prawidłowego wyboru punktu startowego
(rys 1).
1
2
3
4
5
6
7
8
9
10
0
5
10
0
50
100
150
x1
x2
f(
X)
1 zbior punktow startowych
optimum wyznaczane przy startach ze zbioru 1
zbior 2 punktow startowych
optimum wyznaczane przy startach ze zbioru 2
Rys. 1 Wyniki poszukiwania punktu maksymalnej wartości funkcji celu (1) metodami deterministycznymi dla
różnych punktów startowych
Wady tej nie posiadają algorytmy genetyczne. Ogólny algorytm ich działania
przedstawiono na rysunku 2. Obliczenia rozpoczynają się od wygenerowania odpowiedniej
liczby osobników na rozpatrywanym obszarze (rys 3a). W wykorzystywanym przyborniku
służą do tego polecenia crtbp i crtrp. Tworzą odpowiednio populację osobników o
wartościach odpowiednio dyskretnych i rzeczywistych
Następnie wybierane są osobniki najlepiej przystosowane
(najkorzystniejsze wartości funkcji celu). W wykorzystywanym
przyborniku służy do tego polecenie select które wykorzystuje
kilka algorytmów wyboru (sus, rws). Tak wybrane osobniki są
krzyżowane, polecenie recombin. Przybornik udostępnia kilka
metod krzyżowania zależnych od typu populacji (rzeczywista czy
dyskretna). Szczegółowy opis metod krzyżowania w dokumentacji
przybornika.
Do
istniejącego potomstwa najlepiej przystosowanych
osobników wprowadzane są ewentualne mutacje - polecenie
mutate i metoda mut dla zmiennych dyskretnych i mutbga.
Tak wygenerowane potomstwo jest umieszczane w
populacji głównej (reins) zastępując osobniki najsłabiej
przystosowane.
Cykl jest powtarzany do momentu osiągnięcia
maksymalnej ilości generacji lub spełnienia innego kryterium
zakończenia obliczeń.
Ze
względu na losowy charakter generowania populacji
początkowej jak i późniejszego krzyżowania się u mutowania
wyniki nie są w pełni powtarzalne.
Metoda nie daje gwarancji odnalezienia optimum
globalnego umożliwia jednak wyznaczenie wartości „w pobliżu”.
Na rysunku poniżej umieszczono początkowy rozkład
populacji i jej rozmieszczenie po 10 i 20 cyklach.
Oddzielnym problemem jest określenie liczebności
populacji startowej, liczby osobników zastępowanych przez nowe potomstwo czy
prawdopodobieństwo mutacji. Prawidłowy dobór powyższych parametrów jak i metod
krzyżowania i mutacji zależy w dużej mierze od doświadczenia osoby prowadzącej
obliczenia. Podobnie osobny problem stanowi zagadnienie wprowadzenia ograniczeń
funkcyjnych.
1
2
3
4
5
6
7
8
9
10
0
5
10
x1
x2
1
2
3
4
5
6
7
8
9
10
0
5
10
x1
x2
1
2
3
4
5
6
7
8
9
10
0
5
10
x1
x2
a)
b)
c)
Rys. 2 Rozkład populacji przy obliczeniach z wykorzystaniem algorytmów genetycznych: a) startowy; b) po 10
pokoleniach; c)po 20 pokoleniach
start
generacja populacji
startowej
wybór osobników najlepiej
przystosowanych i ich
krzyżowanie
(tworzenie potomstwa)
wprowadzenie
ewentualnych mutacji w
potomstwie
reintrodukcja potomstwa
do populacji głównej
(zastępowane są osobniki
najsłabiej przystosowane )
maksymalna liczba
generacji?
nie
tak
wprowadzenie
ewentualnych mutacji w
potomstwie
stop
Rys. 2
Algorytm obliczen z
wykorzystaniem algorytmów
genetycznych
Skrypty MATLABA
plik f_obj.m zawierający funkcje celu rozpatrywaną w przykładzie
% funkcja celu dla przykladu z cwiczenia 5
% zalezy od dwoch zminnych decyzyjnych
% zawiera dwa punkty maksymalne
%
% F(x1,x2)= (x1 - 1)(x1 - 5)(x1 - 5)(x1 - 10)*(-(x2 - 5)(x2 - 5)/25 + 1)
function [F]=f_obj(X)
X1=X(:,1);% wydobycie pierwszej zmiennej decyzyjnej
X2=X(:,2);% wydobycie drugiej zmiennej decyzyjnej
F=-((X1-1).*(X1-5).*(X1-5).*(X1-10));
F=-F.*((-(X2-5).^2 + 25)/25);% wyliczenie funkcji celu
%(- ze wzgledu na to iż chcemy wyliczyć maksimum
% a posiadamy narzedzie do minimalizacji)
skrypt rozwiązujący problem z przykładu metodą deterministyczną
lb=[0 1 ]; % dolne granice dla zmiennych
ub=[10 10 ]; % gorne granice dla zmiennych
% parametry dla funkcji minimalizujacej
options=optimset('Display','iter','Diagnostics','off','maxiter',1200,'largeScale','off',
'TolCon',1e-8,'TolFun',1e-8,'TolX',1e-8);
% punkt startowy
X0=[5 1];
% obliczenie minimum funkcji umieszczonej w pliku f_obj.m
[X,FVAL] =fmincon(@f_obj,X0,[],[],[],[],lb,ub,[],options);
clear lb ub options
% zmienne
% X zawiera wartosci zmiennych decyzyjnych wyznaczonych po minimalizacji
% FVAL zawiera wartosc (pomnozona przez -1) funkcji celu w punkcie X
skrypt wykorzystujący algorytmy genetyczne do rozwiązania problemy z przykładu
NIND = 50; % ilosc osobnikow
MAXGEN = 20; % dopuszczalna ilosc generacji
NVAR = 2; % ilosc zmiennych
GGAP = 0.3; % czesc calej populacji zastepowana dziecmi
FieldDR = [ 1 0
10 10]; % gorne i dolne ograniczenia na obie zmienne
%wylosowanie populacji
Chrom=crtrp(NIND, FieldDR);
Chrom_old=Chrom;
%licznik populacji
gen = 0;
% wyliczam wartosci funkcji celu dla wylosowanej populacji
ObjV = f_obj(Chrom);
%petla zmieniajaca pokolenia
while gen<MAXGEN
% zastapienie wartosci funkcji celu liczbami nieujemnymi,
% rownomiernie rozlozonymi
FitV = ranking(ObjV);
% wybranie osobnikow do rozmnazania na podstawie FitV
% wybierane jest GGAP*NIND osobnikow
SelCh = select('sus', Chrom, FitV, GGAP);
% namnozenie odpowiedniej (GGAP*NIND) liczby nowych osobnikow
SelCh = recombin('recint',SelCh,0.7);
% potrzebyje tylko (NIND*GGAP) nowych osobnikow
SelCh = mutate('mutbga',SelCh,FieldDR,[0.01 1]);
%wyliczam wartosci funkcji celu dla nowych osobnikow
%uzyskanych przez krzyzowanie i mutacje
ObjVSel = f_obj(SelCh);
%umieszczan nowe osobniki w dotychczasowej populacji zastepujac najgorsze
[Chrom ObjV] = reins(Chrom, SelCh, 1,[1 1], ObjV, ObjVSel);
gen = gen + 1;
end
ObjV=f_obj(Chrom);
%wybor i wypisanie najlepszego osobnika
indx=find(ObjV == min(ObjV));
disp(sprintf('x1= %f; x2=%f; f(X)=%f',Chrom(indx(1),1),Chrom(indx(1),2), -
f_obj(Chrom(indx(1),:))));
clear SelCh ObjVSel FieldDR
clear tmp indx gen
Dodatkowo załączono pliki z przykładami
przykl1.m
f_obj_1.m
przykład minimalizacji funkcji
∑
=
5
1
2
i
i
x ; Zmienne mają reprezentację dyskretną.
przykl2.m
f_obj_2.m
przykład aproksymacji punktów pomiarowych funkcją analityczną.
rozpatrywano przypadek doboru parametrów
a i b równania
y=ax + b
przykl3.m
f_constr.m
f_obj_3.m
przykład rozwiązania problemy liniowego z ograniczeniami (przykład
z ćwiczenia 3) z wykorzystaniem algorytmów genetycznych