PRZYKŁADOWE TEMATY ZADA PROJEKTOWYCH
Z PRZEDMIOTU SZTUCZNA INTELIGENCJA
1. Skonstruowa algorytm genetyczny rozwi zuj cy jeden z poni szych problemów [3]
(opisy poni szych zada w Dodatku na str. 6):
a) dylematu wi nia,
b) zadania załadunku (plecakowego),
c) zadania zbierania plonów,
d) zadania pchania wózka,
e) zadania liniowo-kwadratowego.
2. Rozwi za problem komiwoja era:
a) algorytmem symulowanego wy arzania [3].
b) algorytmem genetycznym
3. Wykorzysta algorytm ewolucyjny lub strategi ewolucyjn [3, 1] do rozwi zania
jednego z poni szych problemów:
a) zadania zbierania plonów,
b) zadania pchania wózka,
c) zadania liniowo-kwadratowego.
4. Zrealizowa algorytm genetyczny dobieraj cy parametrów regulatora PID dla
wybranego obiektu opisanego w dziedzinie czasu ci głego. Jako kryteria poszukiwa
przyj odpowiednie wska niki charakterystyk czasowych lub cz stotliwo ciowych.
Dla uzyskanych najlepszych rozwi za przeprowadzi symulacje z uzyskanymi w
sposób
genetyczny
regulatorami.
Przeprowadzi
analiz
porównawcz
zaprojektowanego rozmytego regulatora z klasycznym (tzn. zaprojektowanym na
podstawie np. metod Zieglera-Nicholsa) w warunkach zakłóce systemowych,
pomiarowych, niepewno ci modelu obiektu oraz uwzgl dnieniu nieliniowo ci.
5. Skonstruowa mini-pakiet algorytmów genetycznych lub ewolucyjnych, w którym mo liwe b dzie rozwi zywanie dowolnego zadania optymalizacji parametrycznej.
6. Zbudowa mini-pakiet algorytmów genetycznych lub ewolucyjnych rozwi zuj cych dowolne zadania wielokryterialnej optymalizacji. Jako metod oceny rozwi za
wykorzysta nale y jedno z poni szych podej [2, 3]:
a) metod wa onych zysków,
b) metod funkcji odległo ci,
c) ranking wg optymalno ci w sensie Pareto.
1
7. Zastosowa algorytm genetyczny do rozwi zywania liniowego zadania transportowego [3].
8. Skonstruowa algorytm genetyczny do planowania drogi w rodowisku ruchomego robota [2, 3]. Program powinien wczytywa mapy (przykładowe rodowiska z
przeszkodami, w którym miałby si porusza si robot) dwuwymiarowe oraz punkty
startowe i ko cowe trasy. Drog robota przykładowo budowa z kawałków linii prostych. Ponadto nale y zaprezentowa na bie co najlepsze znalezione rozwi zania.
9. Wykorzysta programowanie genetyczne [2, 3, 1] do identyfikacji zadanych procesów sygnałowych. Program powinien umo liwia wczytywanie odpowiednich próbek
sygnału z pliku. Zaproponowa odpowiedni struktur osobników oraz kryterium, według którego algorytm znajdzie najlepszy model opisuj cy rozwa any proces.
10. Wykorzysta programowanie genetyczne [2, 3, 1] do identyfikacji modeli obiektów opisanych w dziedzinie czasu ci głego. Program powinien na podstawie danych
pomiarowych (np. charakterystyk cz stotliwo ciowych) generowa odpowiedni model
obiektu. Zaproponowa odpowiedni struktur osobników oraz kryterium, według
którego algorytm znajdzie najlepszy model opisuj cy rozwa any proces.
11. Studium symulacyjne dla wybranych zada optymalizacji wielokryterialnej w oparciu o jedn z par algorytmów:
a) NSGA [4] i SPEA [7],
b) NSGA-2 [5] i SPEA-2 [8].
12. Skonstruowa algorytm genetyczny rozwi zuj cy zadanie załadunku, w którym plecak
posiada okre lona pojemno (obj to ), za mo liwe artykuły do zapakowania
posiadaj 3-wymiary.
13. Zastosowa algorytm genetyczny do optymalnego strzelania z działa armatniego do umieszczonego w pewnym miejscu celu. Przyj , e wielko ciami podlegaj cymi
optymalnemu doborowi s k t nachylenia działa oraz pr dko pocz tkow pocisku.
Ponadto zało y ograniczona liczb pocisków oraz przemieszczanie si celu.
14. Zrealizowa regulator rozmyty PID [6] dla jednego z nast puj cych modeli obiektów.
Dla rozwa anego zadania przeprowadzi analiz porównawcz zaprojektowanego
rozmytego regulatora z klasycznym (tzn. zaprojektowanym na podstawie np. metod Zieglera-Nicholsa) w warunkach zakłóce systemowych, pomiarowych, niepewno ci
modelu obiektu oraz uwzgl dnieniu odpowiednich nieliniowo ci.
a) model odwróconego wahadła
−
G s
1(
=
1
)
s −
s
1
+1
6.25
6.25
2
b) model odwróconego wahadła wraz z serwomechanizmem
2
ω
G s
n
=
2 ( )
( 2
s + 2
2
ζ s + ω
−
n ) 1
(
2 2
d s )
gdzie ω = 20π
/ , ζ = 0.7 oraz d = 0.16 rad / s .
n
rad s
d) model helikoptera
s + 0.03
G s =
3 ( )
( 2
s − 0.35 s + 0.1 )
5 (2 s + )
1
e) model serwomechanizmu
− s 0
K pe T
G s =
4 ( )
s( sT +
sT +
sT +
1
)
1 ( 2
)
1 ( 3
)
1
gdzie K
, T
, T
, T
, T
0 = 0.05 s
3 = 0.5 s
2 =
s
3
.
0
1 =
2
.
0 s
p = 10
f) system dwóch zbiorników
x
− 0.0197
0
x
0.0263
1
1
=
⋅
+
⋅ u
x
0.0178
− 0.0129
x
0
2
2
y = x 2
g) układ kulki i równowani ( ball land beam)
d 2 x = mgr 2ϕ/ J
dt 2
gdzie x jest poło eniem kulki, g oznacza przyspieszenie ziemskie, r jest promieniem kulki, ϕ oznacza k t nachylenia równowa ni, za J jest momentem bezwładno ci kulki.
3
h) układ dwóch mas poł czonych spr yn
x
0
0
1 0
x
0
0
1
1
x
0
0
0 1
x
0
0
2
=
⋅ 2 +
⋅ u +
⋅ w
x
/
/
0 0
1/
0
3
− k m
k m
x
m
1
1
3
1
x
k / m
/
0 0
0
1/
4
2
− k m
x
m
2
4
2
y = x 2 + v
gdzie x i x s poło eniem odpowiednio masy m i m , x i x oznaczaj pr dko ci 1
2
1
2
3
4
odpowiednio masy m i m , sygnał u jest sterowaniem, y reprezentuje pomiar, 1
2
natomiast sygnał w jest szumem systemowym, a v oznacza szum pomiarowy.
Współczynnik k reprezentuje stał spr yny.
15. Skonstruowa sztuczn sie neuronow [9] rozwi zuj c jeden z nast puj cych problemów:
a) rozpoznaj c znaki alfabetu łaci skiego,
b) klasyfikuj c obiekty na trzy rodzaje (np. figury geometryczne),
c) aproksymuj c dowoln ci gł wielowymiarow funkcj .
16. Zastosowa algorytm genetyczny do uczenia sztucznej sieci neuronowej sterujcej
nieliniowym modelem odwróconego wahadła. Przyj , e na wej cie sieci podawany
jest wektor stanu wahadła (k t nachylenia ramienia od pionu, pr dko k towa ramienia, poło enie wózka i jego pr dko ) na podstawie którego sie generuje odpowiednia sił działaj ca na wózek. Równania stanu dla odwróconego wahadła SA
nast puj ce:
x t = x
1 ( )
2 ,
1
g( M + m)sin x t − mlx t
x t + bx t
x t − f x t
x t
1 ( )
2
2 ( ) sin 2 1 ( )
4 ( ) cos 1 ( )
( )cos 1( )
2
x t =
2 ( )
l( M + m sin2 x t
1 ( ))
x t = x t
3 ( )
4 ( )
2
mlx t
x t − mg
x t
x t − bx t + f x t
2 ( ) sin 1 ( )
sin 1( )cos 1( )
4 ( )
( )
x t =
4 ( )
M + m sin2 x t
1 ( )
gdzie x( t) = [ x t
x t
x t
x t jest wektorem stanu wahadła a poszczególne
1 ( )
2 ( )
3 ( )
4 ( )]
jego współrz dne oznaczaj : k t nachylenia ramienia od pionu, pr dko k towa 4
ramienia, poło enie wózka i pr dko . Natomiast M jest mas wózka, m oznacza mas wahadła, l reprezentuje długo (z zało enia – niewa kiego) ramienia wahadła, b jest współczynnikiem tarcia oraz f oznacza sił przyło on do wózka.
x
17. Wykorzysta algorytm ewolucyjny do uczenia sieci neuronowej, która steruje sond
kosmiczn l duj c na planecie np. Mars. W zadaniu tym nale y tak dobiera sił
ci gu sondy by jej pr dko zderzenia z powierzchnia planety była bliska zeru.
Przyj , e na wej cie sieci podawana jest wysoko , pr dko sondy oraz jej masa,
za wyj cie sieci generuje odpowiednia sił ci gu silników hamuj cych. Zało y w modelu ograniczon ilo paliwa, która równie wpływa na ci ar sondy.
18. Zastosowa algorytm ewolucyjny do uczenia sieci neuronowej, która steruje układem dwóch mas poł czonych spr yn . Zało y , e na wej cie sieci podawany jest wektor
stanu obiektu, za wyj cie sieci generuje odpowiednie sterowanie.
Uwaga do zada projektowych ze sztucznych sieci neuronowych i sterowania rozmytego (zadania 14-18):
W przypadku tych zada mo liwe jest wykorzystanie algorytmów ewolucyjnych jako
metod dobieraj cych:
a) struktur i/lub wagi sztucznych sieci neuronowych oraz
b) rozmyte bazy reguł i/lub funkcje przynale no ci dla regulatorów rozmytych.
Je eli takie rozwi zania zostan zastosowane wówczas projekt ma wag (warto ) dwóch zada projektowych.
Z kolei je li zostan poł czone trzy elementy w zadaniach 14-18 (tzn. algorytmy ewolucyjne + logika rozmyta + sieci neuronowe), wówczas projekt taki b dzie miał
warto trzech zada projektowych.
5
Krótkie opisy rozwa anych zada optymalizacji (wi cej w cytowanej literaturze): a) dylemat wi nia mo na traktowa jako gr mi dzy dwoma graczami. W kolejnych ruchach ka dy gracz zdradza lub współpracuje z drugim wi niem. Lista wypłat dla ka dego z graczy przedstawia poni sza tabela.
Wi zie 1
Wi zie 2
Wypłata dla Wypłata dla
wi nia 1
wi nia 2
Uwagi
Zdrada
Zdrada
1
1
Kara za wspólna zdrad
Współpraca
Współpraca
3
3
Nagroda za współprac
Współpraca
Zdrada
0
5
Zapłata przez naiwnego i zach ta do
zdrady
Zdrada
Współpraca
5
0
Zach ta do zdrady i zapłata przez
naiwnego
Przyj do wyboru nast pnego ruchu 3, 4 lub 5 ostatnich wyników
b) zadanie załadunku polega na doborze dla ustalonego zbioru artykułów (rzeczy) wraz z ich warto ciami i rozmiarami (lub wagami), takiego podzbioru artykułów, aby suma ich rozmiarów (wag) nie przekraczała zadanego ograniczenia (pojemno ci lub dopuszczalnej ładowno ci plecaka) oraz by suma ich warto ci była maksymalna.
Problem mo na zdefiniowa w nast puj cy sposób. Niech istnieje plecak o zadanej dopuszczalnej ładowno ci C > 0 oraz N > 0 artykułów. Ka dy i-ty artykuł posiada warto v oraz wag w . Nale y znale taki wektor binarny x = [ x x
x ( x
oznacza
i = 1
1
2
N ]
i
i
wybrany artykuł do plecaka, za x
reprezentuje brak artykułu w plecaku), aby
i = 0
nienaruszone było nast puj ce ograniczenie
Nx w C
i i
i=1
oraz by warto wska nika warto ci plecaka była maksymalna
Nxv
i i
i=1
Przyj liczb artykułów N kolejno 100, 250 i 500. Wagi artykułów wygenerowa losowo (z rozkładem równomiernym) z przedziału [1,10]
c) problem zbierania plonów definiuje si jako nast puj ce zadanie maksymalizacji N
J = 1− u
k
k =0
przy ograniczeniu b d cych równaniem wzrostu
6
k 1
k
k ,
oraz ograniczeniu równo ciowym
x
0 = xN
gdzie x jest stanem pocz tkowym, a oznacza pewna stał , za x ,
+
u
reprezentuj
k
R
k
R
0
odpowiednio stan i (nieujemne) sterowanie. Do rozwiania zadania przyj nast puj ce parametry: a = 1.1, x
i N = ,
2 ,
4 1 ,
0 2 ,
0 45.
0 = 100
d) zadanie pchania wózka okre lone jest jako problem maksymalizacji całkowitej drogi przebytej w zadanym czasie po odj ciu całkowitego wysiłku. Dyskretny model stanowy opisuj cy taki problem wyra a si nast puj co
x k
x k
1(
+ )
1 = 2( ),
1
x k + = x k − x k +
u
k k
2 (
)
1
2 2 ( )
1 ( )
( ),
2
N
jako kryterium poszukiwa przyjmuje si nast puj cy wska nik jako ci sterowania
1 N 1−
J = x ( N)
2
−
u k
1
( ,)
2 N k=0
Zadanie rozwi za dla nast puj cych parametrów, N = 1,
5 0 1
, ,
5 2 ,
0 2 ,
5 3 ,
0 3 ,
5 4 ,
0 45
e) problem liniowo-kwadratowy okre lony polega na minimalizacji nast puj cego zadania sterowania:
N −1
J = 2
x
x
u
N +
2
( k + 2 k )
k =0
przy ograniczeniach
x
x
u k = 0, 1, 2, …, N-1
k 1
+ =
k + k ,
gdzie x jest stanem, a
N
u R jest poszukiwanym wektorem sterowania. Przyj
k
R
dziedzin poszukiwa dla ka dego u
.
i [-200, 2
00]
7
[1] Arabas J., (2001): Wykłady z algorytmów ewolucyjnych, WNT Warszawa .
[2] Deb K., Pratap A., Argarwal S., Meyarivan T., (2000). A fast and elitist multi-objective genetic algorithm: NSGA- II, Technical Report, Kanpur Genetic Algorithms Laboratory, Kanpur, India, no. 200001 (PIN 208 016).
[3] Goldberg D. E., (1995): Algorytmy genetyczne i ich zastosowania, WNT Warszawa .
[4] Michalewicz Z., (1996): Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT Warszawa.
[5] Srinivas N., Deb K., (1994). Multiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation 2 (3) 221-248.
[6] Yager R. R., Filev D. P., (1995) Podstawy modelowania i sterowania rozmytego, WNT, Warszawa.
[7] Zitzler E., Thiele L., (1998). An evolutionary algorithm for multiobjective optimization: The Strength Pareto Evolutionary Algorithm, Technical Report, Computer Engineering and Networks Laboratory, ETH, Zurich, Switzerland, no, 43.
[8] Zitzler E., Laumanns M., Thiele L., (2001). SPEA-2: Improving the strength Pareto evolutionary algorithm, Technical Report, Computer Engineering and Networks
Laboratory, Department of Electrical Engineering, ETH, Zurich, Switzerland, no. 103.
[9] uranda J., Barski M., Jedruch W., (1996). Sztuczne sieci neuronowe, PWN, Warszawa.
8