Ambalarea este o problemă clasică de optimizare. Să presupunem că avem un camion capabil să transporte orice număr de cutii, atâta timp cât greutatea lor totală nu depășește W. Aveți un număr nelimitat de diferite tipuri de mărfuri în depozit. Fiecare articol de tip i are o greutate w i și o valoare v i. Problema dvs. este să determinați ce combinație de obiecte va atinge cea mai mare valoare fără a depăși greutatea totală maximă permisă. De exemplu, când greutățile și valorile sunt
atunci un camion cu o capacitate maximă de încărcare W = 200 poate transporta:
Cea mai bună strategie este să încărcați cât mai multe cutii de portocale și să umpleți restul cu cărți. Rezolvați problema pentru un număr mai mare de itemi cu valori și greutăți definite aleatoriu utilizând un algoritm genetic, cu un număr limitat de itemi, veniți cu propria dvs. reprezentare a problemei și a cromozomilor, mutațiilor și algoritmilor reticulați corespunzători . (Adaptat de la http://www.epcc.ed.ac.uk/epic/ga/intro.html)
(echipa va fi pregătită de Jan Marиok, [email protected] .uniba.sk)
Tema 2. Problemă de programare
Problema programării a fost intensă în domeniul cercetării operaționale de mulți ani. Una dintre formulările problemei este să presupunem că avem un set de N sarcini t i, i = 1.N, fiecare dintre care necesită o parte din resursele r j pentru un timp dat i, rj. Sarcina noastră este de a găsi cel mai rapid program pentru îndeplinirea generală a acestor sarcini, în timp ce resursele pot fi utilizate simultan, dar fiecare resursă printr-o sarcină diferită. Ordinea resurselor pentru sarcină nu contează. Rezolvați problema pentru mai multe sarcini cu resurse și timpi necesari definiți aleatoriu folosind un algoritm genetic, veniți cu propria dvs. reprezentare a problemei și a cromozomilor, mutațiilor și încrucișărilor corespunzătoare, comparați algoritmul cu genetica canonică. Utilizați funcția de penalizare dacă limita nu este îndeplinită.
(echipa va fi pregătită de Ján Wall, [email protected])
Tema 3. Compararea algoritmului genetic cu metoda simplex
Optimizați funcția f (x, y) = cos 2 (n Pi x) exp (-r 2/s 2), r 2 = (x-0,5) 2 + (y-0,5) 2 pentru x, y О [0, 1], unde n = 9 și s 2 = 0,15. Găsiți maximul global al acestei funcții utilizând algoritmul genetic și metoda simplex. Măriți dimensiunea problemei la 3,4,5,6 dimensiuni și comparați performanța GA cu metoda simplex (cod de ex. La http://www.techxhome.com/products/o ptsolve/sau http: // www .ulib.org /webRoot/Books/Numerical_Recipes/bookcpdf.html
(echipa va fi pregătită de Michaela Aиová, [email protected])
Tema 4. Evoluția rețelelor de sortare
(fitness maxim = 120)
- Exemplu: pentru valorile 1,3,5,4,2 obțineți 1,2,3,4,5 sau 5,4,3,2,1 ca ieșire: linia verticală indică schimbul de valori între linii orizontale când prima valoare este mai mare/mai mică decât a doua valoare a doua.
- Încercați: dimensiunea populației = 10, încrucișarea = 10%, mutații = 0%
- Încercați: dimensiunea populației = 10, încrucișarea = 10%, mutații = 1% (200 de generații)
- Încercați: dimensiunea populației = 10, încrucișarea = 80%, mutații = 1% (150 generații)
- Încercați: dimensiunea populației = 50, încrucișarea = 90%, mutațiile = 1%
GA creează rețele de sortare cu 5 intrări care conțin maximum 9 schimburi de comparație. Există 120 de cazuri de fitness (toate 5! Permutări ale secvenței 1,2,3,4,5), iar o rețea corectă le aranjează pe toate fără greșeli. Încercați coevolutia pentru cazuri mai complexe în care secvențele de valori evoluează independent una de cealaltă și sunt evaluate mai bine cu atât mai multe rețele eșuează pe ele.
Tema 5. Autoorganizarea condițiilor critice în grămezi de nisip
Bidimensional și o grămadă de nisip pot fi construite pe baza unor reguli foarte simple pentru un automat celular simplu. Starea unei celule se caracterizează prin numărul de boabe de nisip pe care le conține. Regula de recuperare spune că, atunci când o celulă are 4 sau mai multe boabe de nisip, aceasta pierde 4 și primește câte un bob din fiecare dintre celulele imediat adiacente cu 4 sau mai multe boabe. Prin urmare, secvența stărilor de lovitură poate arăta astfel
Un total de 6 celule au fost incluse în avalanșă, care a durat 4 reînnoiri.
Putem obține această grilă într-o stare critică adăugând rapid nisip la masă până când viteza de turnare a nisipului este aproximativ egală cu viteza cu care grăunțele de nisip cad de pe marginile mesei. Abordarea echivalentă este supraîncărcarea mesei cu nisip - adăugați o cantitate aleatorie de 5-8 boabe la fiecare pătrat - și apoi începeți actualizarea (fără a adăuga mai mult nisip) până când masa atinge o stare stabilă (recuperarea nu se va schimba).
O caracteristică interesantă a acestui sistem este că, odată realizată o dietă critică, adăugarea unui singur bob de nisip poate provoca avalanșe de toate dimensiunile posibile, care pot dura aproape în mod arbitrar mult timp. Când repetăm acest proces de multe ori, ajungem la concluzia că N (S)
1/S a, N (S) este numărul de avalanșe de mărimea S (care afectează celulele S ale rețelei) și alfa este așa-numita exponent critic
- Care este cea mai lungă avalanșă pe care o puteți construi pe o grilă de 5x5? Starea inițială poate avea maximum 3 boabe de nisip pe grilă, iar un singur al patrulea bob poate fi adăugat la celulă pentru a începe avalanșa. Este posibil să construim un ciclu infinit? De ce? (Sau de ce nu?)
- Determinați experimental coeficientul alfa (acest lucru se face cel mai bine prin crearea unui număr mare de avalanșe și păstrarea dimensiunilor acestora. Apoi găsiți numărul de avalanșe pentru fiecare dimensiune - sunt necesare multe calcule pentru rezultate bune. În cele din urmă, afișați rezultatele într-un jurnal a cărui pantă este egal cu minus alfa.
- Dacă măriți zona la toți cei 8 vecini și creșteți numărul critic de boabe la 8, acest exponent va crește. Ceea ce provoacă această schimbare?
Subiectul 6. Problema satisfacției generale (SAT), chiar dacă acoperim tot felul de clauze logice, nu doar conjuncții și disjuncții. Fiecare problemă constă din 20 de variabile booleene (A0 - A19) și un set de constrângeri. Scopul, desigur, este de a găsi o atribuire veridică fiecărei variabile astfel încât să fie îndeplinite toate constrângerile. Cele mai bune soluții la aceste probleme sunt banale pentru oameni, dar GA nu are cunoștințele noastre de logică și trebuie să caute pe larg. Desenați un grafic de forță (min, maxim și mediu) pentru fiecare dintre rulările GA.
A) 5 conjuncții, restricțiile sunt
(A0 și A1 și A2 și A3)
(A4 și A5 și A6 și A7)
(A8 și A9 și A10 și A11)
(A12 și A13 și A14 și A15)
(A16 și A17 și A18 și A19)
- Descrieți reprezentarea și funcția forței. În reprezentarea dvs., cât de mare este spațiul de căutare?
- Descrieți diferențele în comportamentul GA atunci când utilizați o dimensiune a populației de 100 sau 20. În fiecare caz, utilizați 50 de generații, o probabilitate de mutație (pmut) de 0,01 pe cromozom (nu pe genă) și o probabilitate de încrucișare (pcross) de 0,75 .
c) Utilizați dimensiuni ale populației de 50, 50 de generații, pmut = 0,01 și 3 probabilități diferite de încrucișare: 0,1, 0,3 și 0,8. Cum diferă comportamentul algoritmului pentru un anumit 3 run-uri?
B) 10 conjuncții, restricțiile sunt
(A0 și A1) (A2 și A3)
(A4 și A5) (A6 și A7)
(A8 și A9) (A10 și A11)
(A12 și A13) (A14 și A15)
(A16 și A17) (A18 și A19)
e) Rulați această problemă în aceleași condiții ca a, cu aceeași funcție de fitness. Care sunt diferențele? De ce există diferențe, chiar dacă constrângerile sunt logic echivalente? Puteți utiliza funcția de fitness utilizată pentru a explica diferența?
f) Executați această problemă cu o populație de 100, 100 de generații, pcross = 0,8, cu două valori pmut diferite: 0,1 și 0,01. Care sunt diferențele? Puteți explica de ce au apărut?
g) Proiectați o nouă funcție de fitness semnificativ diferită de prima și testați-o pentru a) și e) cu o populație de 100, 100 de generații, pcross = 0,8, pmut: 0,01. Care sunt rezultatele în comparație cu prima funcție de fitness? Cum s-a schimbat „suprafața”?
B) 7 disjuncții, 4 conjuncții, restricțiile sunt
(A0 sau A1 sau A2 sau A3)
(nu (A0) sau nu (A1))
(A4 și A5 și A6 și A7)
(A8 și A9 și A10 și A11)
(A12 și A13 și A14 și A15)
(A16 și A17 și A18 și A19)
h) Test cu o populație de dimensiuni 100, 100 generații, pcross = 0,8, pmut: 0,1. cu ambele caracteristici de fitness propuse, explicați diferențele de comportament.
(echipa va fi pregătită de Pavol Љupa, [email protected])
Subiectul 7. Utilizați recușire simulată pentru a rezolva mișcarea pisicii de pe tablă, unde trebuie să rulați toate celelalte câmpuri din câmpul introdus, în timp ce introduceți fiecare câmp o singură dată. Ca a doua parte a sarcinii, rezolvați aceeași problemă cu condiția ca pisica să revină. Când rezolvați, utilizați o perturbație (mutație) de genul în care copiați începutul secvenței de câmpuri într-un număr selectat aleatoriu de câmpuri într-o nouă soluție și generați restul. Sarcina poate fi rezolvată și prin navigarea inversă, dar numai pentru cazuri mici.
(echipa va fi pregătită de Tomáš Pail, [email protected])
Subiectul 8. Evaluează impactul strategiilor de selecție asupra optimizării folosind definițiile
pentru recalcularea forței în mod proporțional (vezi formula 4.11c din cartea Algoritmi evolutivi) sau pe baza aranjamentului în funcție de mărime (formula 4.12b) și de alegerea proprie prin ruletă, turneu, folosind așa-numitul cu eșantionare universală tochastică, selecție locală, selecție trunchiată descrisă în
Evaluează impactul strategiilor de selecție asupra optimizării următoarelor funcții multimodale (pentru n = 1-10)
f (x) = 418.9829 * n + sum (-x (i) * sin (sqrt (abs (x (i))))
f (x) = 10,0 * n + sumă (x (i) ^ 2 - 10,0 * cos (2 * Pi * x (i)))
f (x) = 1/4000 * sum (x (i) -100) ^ 2 - prod ((x (i) -100)/sqrt (i)) + 1
Funcțiile unei variabile
f (x) = x ^ 4 - 12 * x ^ 3 + 15 * x ^ 2 + 56 * x - 60
minimizarea funcțiilor multivariabile
f (x1, x2, x3, x4, x5) = x1 * sin (x1) + 1.7 * x2 * sin (x1) - 1.5 * x3 - 0.1 * x4 * cos (x4 + x5-x1) + (0.2 * x5 ^ 2-x2) - 1
Funcția „Nerd” - maximizare pentru 10 variabile
(x1 * x2 * x3 * x4 * x5)/(x6 * x7 * x8 * x9 * x10) unde (x1.x10) = [1.10]
Subiectul 9. Evaluează efectul încrucișării și optimizării mutației asupra utilizării definițiilor
pentru încrucișarea valorilor reale: prin combinație liniară, valori medii, discrete și binare: punct unic, două puncte, multipunct, uniform și mutație a variabilelor binare și variabile reale (din strategiile evolutive 9 pentru funcțiile datelor).
Subiectul 10. Algoritm genetic pentru problema Problemă de partiționare a numărului. Utilizați ambele abordări pentru a codifica reprezentarea lui p, ambele folosind direct N-tupluri de numere întregi și folosind un șir binar (a se vedea Exercițiul 7.1 din capitolul Probleme de optimizare combinatorie). Comparați eficacitatea acestor două abordări diferite.
(echipa va fi pregătită de Ján Hnila, [email protected])
Subiect 11. Problemă de planificare a sarcinilor pentru procesoare
Sarcina dvs. este de a utiliza un algoritm genetic pentru a rezolva problema atribuirii sarcinii. Setul de sarcini trebuie realizat pe un set de procesoare. Fiecare sarcină este definită de două ori: timpul necesar calculării sarcinii și timpul necesar transferului rezultatelor la procesorul principal, p0. Toți procesoarele partajează unul sau mai multe canale de comunicare, iar un singur rezultat poate fi trimis fiecărui canal la un moment dat, partajarea canalelor paralele nu este posibilă. Școlile care rulează pe procesorul principal consumă zero timp de comunicare. Dacă nu există canale de comunicare gratuite, procesorul trebuie să aștepte ca acesta să îndeplinească partea de comunicare a sarcinii sale curente. Scopul este de a specifica un program, adică un set de alocări de sarcini procesorului, care ar reduce la minimum timpul când toate sarcinile vor fi finalizate.
Utilizarea GA pentru a rezolva o problemă necesită 2 elemente de bază:
1. o persoană care reprezintă orarele și populațiile orarelor
2 simulator care calculează timpul total la finalizarea programului
Utilizați programul pentru a rezolva sarcini cu perechi de timp de calcul și comunicare:
(7 16) (11 22) (12 40) (15 22) (17 23)
(17 23) (19 23) (20 28) (20 27) (26 27)
(28 31) (36 37) (31 29) (28 22) (23 19)
(22 18) (22 17) (29 16) (27 16) (35 15)
Conform lui Kidwell (1993), timpul minim pentru finalizarea sarcinilor pe 3 procesoare cu un singur canal de comunicare este de 202 pași de timp. Încercați să găsiți această soluție cu algoritmul dvs. genetic, în timp ce este important să vă alegeți funcția de fitness. Descrieți succesul utilizând grafice bazate pe valori ale parametrilor cheie, cum ar fi rata mutației și procentul de trecere, numărul de puncte de trecere, dimensiunea populației și mecanismul de selecție. (Conform http://www.idi.ntnu.no/
(echipa va fi pregătită de Alexander Moravcik, [email protected])
Tema 12. Algoritmi ant
ca bază pentru algoritmul dvs., unde pentru probabilitățile de a lua și a scăpa vârful și
utilizați alte puteri decât pătratul și arătați graficul cu privire la rezultatele eficienței optimizării în funcție de această putere.
(echipa va fi pregătită de Matúš Kalaš, [email protected])
Tema 13. Percolarea
Când rămâneți fără lapte sau vă tăiați și începeți sângerarea, este de fapt un proces similar. Asa numitul tranziția sol-gel, conversia unui lichid într-un semi-solid care rezultă din cuplarea aleatorie a moleculelor. Acest proces, care este similar cu oamenii dintr-o mulțime care își unesc mâinile la întâmplare, este o trăsătură caracteristică a fenomenului de percolare.
Percolarea este asociată cu numele P.G. de Gennes, care urmează să primească Premiul Nobel pentru fizică din 1991 pentru munca sa în fizica teoretică a materialelor deteriorate. El a descris tranziția de percolare după cum urmează: „Multe fenomene apar din cauza unor insule aleatorii și în anumite circumstanțe, un continent macroscopic apare între aceste insule”.
Percolarea este un fenomen relativ comun în natură. Apare în sisteme chimice (reacții polimerice), sisteme biologice (reacții imunologice) și sisteme fizice (fenomene critice). Scurgerea, percolarea, este o teorie fizică care ne permite să înțelegem fenomene precum formarea clusterelor, scurgerea de la un mediu la altul, folosind această teorie pentru a estima profitabilitatea zăcămintelor de petrol etc.
Percolarea aleatorie a site-ului (RSP)
RSP constă din m x m într-o rețea booleană aleatorie mare. Deci, această grilă conține locuri în care există unități și zerouri. Locurile cu o unitate reprezintă un loc ocupat, locurile cu zero gol. Probabilitatea p că o celulă este ocupată este independentă de vecinii săi. Un cluster este apoi definit ca un grup de celule vecine cele mai apropiate ocupate. (cel mai apropiat vecin înseamnă locuri la stânga, la dreapta, jos și în sus de la celulă.
Un exemplu de cluster de dimensiunea 5 este:
Presupunând că p este probabilitatea ca fiecare celulă să fie ocupată (adică evaluată cu 1), care este numărul așteptat de clustere de mărime 3 pe grilă? (Ignorați efectele de margine pentru simplitate).
În majoritatea cazurilor, este imposibil să se determine probabilitatea critică de apariție a unui cluster infinit (adică unul care se extinde de la o parte a grilei la cealaltă). Pentru o rețea pătrată obișnuită de 64x64, determinați experimental probabilitatea critică testând dacă a apărut un „cluster infinit” pentru p (probabilitate între 0 și 1). Puteți afla generând configurații aleatorii pentru un număr fix de ori pentru a obține proporția cazurilor în care a apărut un cluster infinit și repetați această procedură pentru p diferite. Arătați probabilitatea de a găsi un cluster infinit față de probabilitatea lui p .
(Potrivit http: //www.krl.caltech.edu/
Tema 14. Programare genetică pentru furnici care caută o cale
Programare genetică pentru a crea un „program” pentru furnici folosind un set de reguli. Furnica ar trebui să colecteze hrana răspândită pe o pistă nu destul de continuă situată pe rețeaua toroidală, în timp ce are doar senzori limitați (deci poate vedea doar celulele laterale ale rețelei). Furnica trebuie să colecteze cât mai multe alimente posibil într-un anumit număr de pași de timp. Detaliile sarcinii pot fi inspirate la http://www2.informatik.uni-erlangen.de/
jacob/Evolvica/GP/Java/html/ant/ant.html). Sarcina este de a genera reguli a) pentru propria pistă generată aleatoriu cu proprietăți similare cu John Muir Trail de pe pagina WWW de mai sus. b) Încercați să generați reguli care s-ar aplica simultan mai multor benzi.
(echipa va fi pregătită de Aleksandra Taká, [email protected])
„Studii de caz” elaborate în šk.r. 2001/2002
Aleksandra Takachi: Programare genetică pentru o furnică care caută o cale (studiu de caz pdf, implementare exe.zip)
Alexander Moravcik: Problemă de planificare a sarcinilor (studiu de caz pdf, implementare exe.zip)
Ondrej Jaura: Autoorganizarea unui dicționar în comunitatea agenților (studiu de caz pdf)
Peter Bodík: Vulpi, iepuri de câmp și altele (studiu de caz pdf)