A csomagolás klasszikus optimalizálási probléma. Tegyük fel, hogy van egy teherautónk, amely képes bármilyen számú doboz szállítására, amennyiben össztömege nem haladja meg a W-t. A raktárban korlátlan számú különféle árucikk van. Minden i elemtípusnak van w i súlya és v i értéke. A problémád az, hogy meghatározd, melyik objektumkombináció éri el a legmagasabb értéket a maximálisan megengedett össztömeg túllépése nélkül. Például, ha a súlyok és az értékek
akkor egy W = 200 maximális teherbírású teherautó képes:
A legjobb stratégia az, ha a lehető legtöbb doboz narancsot betölti, a többit könyvekkel tölti meg. Oldja meg a problémát nagyobb számú, véletlenszerűen meghatározott értékekkel és súlyokkal rendelkező elemre genetikai algoritmus segítségével, néhány elem korlátozott számával, állítsa elő a probléma saját ábrázolását és a megfelelő kromoszómákat, mutációkat és térhálós algoritmusokat . (A http://www.epcc.ed.ac.uk/epic/ga/intro.html webhelyről adaptálva)
(a csapatot Jan Marиok, [email protected] .uniba.sk készíti fel)
2. téma Ütemezési probléma
Az ütemezési probléma hosszú évek óta intenzív az operatív kutatás területén. A probléma egyik megfogalmazása az a feltételezés, hogy N feladatok halmaza van t i, i = 1.N, amelyek mindegyikéhez szükség van az r j erőforrások egy részére egy adott i, rj időre. Feladatunk az, hogy megtaláljuk a leggyorsabb ütemtervet ezeknek a feladatoknak az általános teljesítéséhez, miközben az erőforrásokat egyszerre lehet használni, de az egyes erőforrásokat egy másik feladat. A feladat forrásainak sorrendje nem számít. Genetikai algoritmus segítségével oldja meg a problémát több, véletlenszerűen meghatározott szükséges erőforrásokkal és időkkel rendelkező feladathoz, állítsa össze a probléma saját ábrázolását és a megfelelő kromoszómákat, mutációkat és keresztezéseket, hasonlítsa össze algoritmusát a kanonikus genetikával. Használja a büntetés funkciót, ha a határérték nem teljesül.
(a csapatot Ján Wall készíti fel, [email protected])
3. téma A genetikai algoritmus összehasonlítása a szimplex módszerrel
Optimalizálja az f (x, y) = cos 2 (n Pi x) exp (-r 2/s 2), r 2 = (x-0.5) 2 + (y-0.5) 2 függvényt x, y értékre О [0, 1], ahol n = 9 és s 2 = 0,15. Keresse meg a függvény globális maximumát a genetikai algoritmus és a szimplex módszer segítségével. Növelje a probléma dimenzióját 3,4,5,6 dimenzióra, és hasonlítsa össze a GA teljesítményét a szimplex módszerrel (kód pl .: http://www.techxhome.com/products/o ptsolve/vagy http: // www .ulib.org /webRoot/Books/Numerical_Recipes/bookcpdf.html
(a csapatot Michaela Aиová, [email protected] készíti fel)
4. téma: A válogató hálózatok alakulása
(max. fitnesz = 120)
- Példa: az 1,3,5,4,2 értékeknél kapjon 1,2,3,4,5 vagy 5,4,3,2,1 kimenetet: a függőleges vonal az értékek cseréjét jelzi a vízszintes vonalak, ha az első érték magasabb/kisebb, mint a második második érték.
- Próbálja: populációnagyság = 10, keresztezés = 10%, mutációk = 0%
- Próbálja: a populáció mérete = 10, keresztezés = 10%, mutációk = 1% (200 generáció)
- Próbálja: populációnagyság = 10, keresztezés = 80%, mutációk = 1% (150 generáció)
- Próbálja: populációnagyság = 50, keresztezés = 90%, mutációk = 1%
A GA 5 bemeneti rendezési hálózatot hoz létre, amelyek legfeljebb 9 összehasonlító központot tartalmaznak. 120 fitnesz eset van (mind az 5! Az 1,2,3,4,5 szekvencia permutációi), és egy helyes hálózat hibákat nélkül rendezi el őket. Próbálkozzon a koevolúcióval bonyolultabb esetekben, amikor az értékek egymástól függetlenül fejlődnek és minél jobb besorolásúak, annál több hálózat bukik meg rajtuk.
5. téma A kritikus állapotok önszerveződése homokkupacokban
Kétdimenziós és egy halom homok építhető fel egy egyszerű cellás automata nagyon egyszerű szabályai alapján. A sejt állapotát a benne lévő homokszemek száma jellemzi. A helyreállítási szabály azt mondja, hogy amikor egy sejtnek 4 vagy több szemcséje van, elveszít 4-et, és a közvetlenül szomszédos sejtek mindegyikéből egy vagy négy szemcséjű szemcsét kap. A rúgási állapotok sorrendje tehát így nézhet ki
Összesen 6 cellát vontak be a lavinába, amely 4 megújulásig tartott.
Ezt a rácsot kritikus állapotba hozhatjuk, ha gyorsan hozzáadjuk a homokot az asztalhoz, amíg a homok öntésének sebessége körülbelül meg nem egyezik azzal a sebességgel, amellyel a homokszemek leesnek az asztal széléről. Az egyenértékű megközelítés az asztal túlterhelése homokkal - véletlenszerű mennyiségű 5-8 szemcse hozzáadása minden négyzethez -, majd a frissítés megkezdése (további homok hozzáadása nélkül) addig, amíg a táblázat stabil állapotba nem kerül (a helyreállítás nem változik).
A rendszer érdekes tulajdonsága, hogy a kritikus étrend elérése után egyetlen homokszem hozzáadása minden lehetséges méretű lavinát okozhat, amely szinte önkényesen sokáig tarthat. Amikor ezt a folyamatot sokszor megismételjük, arra a következtetésre jutunk, hogy N (S)
1/S a, N (S) az S méretű lavinák száma (amelyek a rács S sejtjeire hatnak), az alfa pedig az ún. kritikus kitevő
- Mi az a leghosszabb lavina, amelyet egy 5x5-ös rácson meg lehet építeni? A kiindulási állapotban legfeljebb 3 szem homok lehet a rácson, és a lavina elindításához egyetlen negyedik szemcse adható a cellához. Fel lehet-e építeni egy végtelen ciklust? Miért? (Vagy miért ne?)
- Kísérletileg határozza meg az alfa-együtthatót (ezt leginkább nagy számú lavina létrehozásával és méretük fenntartásával lehet elérni. Ezután keresse meg az egyes méretek lavináinak számát - a jó eredmények érdekében sok számításra van szükség. Végül jelenítse meg az eredményeket a naplóban, amelynek lejtése egyenlő az alfa mínuszával.
- Ha mind a 8 szomszédra növeli a területet, és a szemek kritikus számát 8-ra növeli, akkor ez a kitevő megnő. Ami ezt a változást okozza?
6. téma. Az általános kielégíthetőség (SAT) problémája, még akkor is, ha mindenféle logikai tagmondatot lefedünk, nem csak kötőszavakat és diszjunkciókat. Minden feladat 20 logikai változóból áll (A0 - A19) és egy sor korlátozásból. A cél természetesen az, hogy minden változóhoz igaz hozzárendelést találjunk, hogy minden korlát teljesüljön. A legjobb megoldások ezekre a problémákra triviálisak az emberek számára, de a GA-nak nincsenek ismereteink a logikáról, és alaposan meg kell kutatnia. Rajzoljon erő grafikont (min, max és átlag) az egyes GA futásokhoz.
A) 5 kötőszó, korlátozás
(A0 és A1, valamint A2 és A3)
(A4 és A5, A6 és A7)
(A8 és A9, valamint A10 és A11)
(A12 és A13, A14 és A15)
(A16 és A17, valamint A18 és A19)
- Írja le az erő ábrázolását és funkcióját. Az Ön ábrázolásában mekkora a keresési hely?
- Írja le a GA viselkedésének különbségeit, ha 100 vagy 20 populációnagyságot használ. Mindegyik esetben használjon 50 generációt, mutáció valószínűségét (pmut) 0,01 kromoszómánként (nem génenként) és keresztezés valószínűségét (pcross) 0,75 .
c) Használjon 50, 50 generációs populációméretet, pmut = 0,01 és 3 különböző keresztezési valószínűséget: 0,1, 0,3 és 0,8. Hogyan különbözik az algoritmus viselkedése adott 3 futtatásnál?
B) 10 kötőszó, korlátozás
(A0 és A1) (A2 és A3)
(A4 és A5) (A6 és A7)
(A8 és A9) (A10 és A11)
(A12 és A13) (A14 és A15)
(A16 és A17) (A18 és A19)
e) Futtassa ezt a problémát ugyanazokkal a feltételekkel, mint a, ugyanazzal a fitnesz funkcióval. Mi a különbség? Miért vannak különbségek, még akkor is, ha a megszorítások logikailag egyenértékűek? Használhatja a fitnesz funkciót a különbség magyarázatára?
f) Futtassa ezt a problémát 100, 100 generációs populációval, pcross = 0,8, két különböző pmut értékkel: 0,1 és 0,01. Mi a különbség? Meg tudja magyarázni, miért jelentek meg?
g) Tervezzen meg egy új fitneszfunkciót, amely jelentősen eltér az elsőtől, és tesztelje az a) és e) pontokat 100, 100 generációs populációval, pcross = 0,8, pmut: 0,01. Mik az eredmények az első fitnesz funkcióhoz képest? Hogyan változott a "felület"?
B) 7 disjunkció, 4 kötőszó, korlátozás
(A0 vagy A1 vagy A2 vagy A3)
(nem (A0) vagy nem (A1))
(A4 és A5, A6 és A7)
(A8 és A9, valamint A10 és A11)
(A12 és A13, A14 és A15)
(A16 és A17, valamint A18 és A19)
h) Teszteljen 100-as méretű populációval, 100 generáció, pcross = 0,8, pmut: 0,1. mindkét javasolt fitnesz funkcióval magyarázza el a viselkedésbeli különbségeket.
(a csapatot Pavol Љupa készíti fel, [email protected])
7. téma. Szimulált izzítással oldja meg a macska mozgását egy sakktáblán, ahol a beírt mezőből az összes többi mezőt futtatnia kell, miközben minden mezőbe csak egyszer kell belépnie. A feladat második részeként oldja meg ugyanazt a problémát azzal a feltétellel, hogy a macskának vissza kell mennie. Megoldásakor használjon olyan zavarokat (mutációkat), amelyek a mezők sorozatának elejét egy véletlenszerűen kiválasztott számú mezőbe másolják egy új megoldásba, és a többit előállítják. A feladat fordított böngészéssel is megoldható, de csak kis esetekre.
(a csapatot Tomáš Pail készíti fel, [email protected])
8. téma. Értékelje a kiválasztási stratégiák optimalizálásra gyakorolt hatását a definíciók felhasználásával
az erő arányos újraszámításához (lásd az evolúciós algoritmusok könyv 4.11c képletét), vagy a méret szerinti elrendezés (4.12b képlet) és saját választás alapján ruletten, tornán, az ún. cikkben leírt tochasztikus univerzális mintavétellel, lokális szelekcióval, csonkaválasztással
Értékelje a szelekciós stratégiák hatását a következő multimodális függvények optimalizálására (n = 1-10 esetén)
f (x) = 418.9829 * n + összeg (-x (i) * sin (sqrt (abs (x (i))))
f (x) = 10,0 * n + összeg (x (i) ^ 2 - 10,0 * cos (2 * Pi * x (i)))
f (x) = 1/4000 * összeg (x (i) -100) ^ 2 - prod ((x (i) -100)/sqrt (i)) + 1
Egy változó funkciói
f (x) = x ^ 4 - 12 * x ^ 3 + 15 * x ^ 2 + 56 * x - 60
a többváltozós funkciók minimalizálása
f (x1, x2, x3, x4, x5) = x1 * bűn (x1) + 1,7 * x2 * bűn (x1) - 1,5 * x3 - 0,1 * x4 * cos (x4 + x5-x1) + (0,2 * x5) ^ 2-x2) - 1
"Nerd" függvény - maximalizálás 10 változóhoz
(x1 * x2 * x3 * x4 * x5)/(x6 * x7 * x8 * x9 * x10) ahol (x1.x10) = [1.10]
9. téma. Értékelje a keresztezés és a mutáció optimalizálásának a definíciók használatára gyakorolt hatását
valós értékek keresztezéséhez: lineáris kombinációval, átlagos, diszkrét és bináris értékek: egypontos, kétpontos, többpontos, egyenletes és bináris változók és valós változók mutációja (az evolúciós stratégiákból az adatok függvényében 9).
10. téma. Genetikai algoritmus a feladat számfelosztási problémához. Használja mindkét megközelítést a p ábrázolásának kódolásához, mind közvetlenül egész számok N-halmazával, mind bináris karakterlánccal (lásd a Kombinatorikus optimalizálási problémák fejezet 7.1. Gyakorlatát). Hasonlítsa össze e két különböző megközelítés hatékonyságát.
(a csapatot Ján Hnila, [email protected] készíti fel)
11. téma: Feladatütemezési probléma a processzorok számára
Az Ön feladata, hogy genetikai algoritmust használjon a feladat-hozzárendelés problémájának megoldására. A feladatkészletet egy processzorhalmazon kell elvégezni. Minden feladatot két alkalommal határozunk meg: a feladat kiszámításához szükséges idő és az eredmények átadásához szükséges idő a fő processzorhoz, p0. Valamennyi processzor egy vagy több kommunikációs csatornát oszt meg, és mindegyik csatornára egyszerre csak egy eredmény küldhető el, a párhuzamos csatornamegosztás nem lehetséges. A fő processzorral működő iskolák nulla kommunikációs időt fogyasztanak. Ha egyetlen kommunikációs csatorna sem szabad, a processzornak meg kell várnia, amíg végrehajtja aktuális feladatának kommunikációs részét. A cél egy ütemezés meghatározása, vagyis a feladatoknak a processzorhoz történő hozzárendelése, amely minimalizálja az összes feladat elvégzésének idejét.
A GA használatához egy probléma megoldásához 2 alapvető elemre van szükség:
1. a menetrendeket és a menetrendek populációit képviselő egyén
2 szimulátor, amely kiszámítja a teljes időt, amikor az ütemezés elkészült
Használja programját a feladatok számítási és kommunikációs idő párokkal történő megoldására:
(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)
Kidwell (1993) szerint a 3 processzoron egy kommunikációs csatornával végzett feladatok végrehajtásának minimális ideje 202 idő lépés. Próbálja meg megtalálni ezt a megoldást genetikai algoritmusával, miközben fontos a fitnesz funkció kiválasztása. Írja le a sikert grafikonok segítségével olyan kulcsparaméterek értéke alapján, mint a mutációs ráta és a keresztezés százaléka, a keresztezési pontok száma, a populáció mérete és a szelekciós mechanizmus. (A http://www.idi.ntnu.no/ szerint
(a csapatot Alexander Moravcik készíti fel, [email protected])
12. téma Hangya algoritmusok
algoritmusának alapjául, ahol a csúcs felvételének és eldobásának valószínűségére és
használja a négyzeten kívüli más hatalmakat, és ennek a teljesítménynek a függvényében jelenítse meg a grafikont az optimalizálási hatékonyság eredményein.
(a csapatot Matúš Kalaš készíti fel, [email protected])
13. téma: Percoláció
Amikor elfogy a teje, vagy elvágja magát, és elkezd vérezni, ez valójában hasonló folyamat. Az úgynevezett szol-gél átmenet, egy folyadék átalakulása félszilárddá, amely a molekulák véletlenszerű összekapcsolódásából származik. Ez a folyamat, amely analóg az emberekkel a véletlenszerűen kezet fogó tömegben, a perkolációs jelenség jellemző jellemzője.
A percoláció a P.G. névhez társul. de Gennes, az 1991-es fizikai Nobel-díj viselésére, amelyet a sérült anyagok elméleti fizikájában végzett munkájáért kapott. A beszivárgási átmenetet a következőképpen írta le: "Sok jelenség fordul elő véletlenszerű szigetek miatt, és bizonyos körülmények között egy makroszkopikus kontinens jön létre ezek között a szigetek között."
A percoláció viszonylag gyakori jelenség a természetben. Kémiai rendszerekben (polimer reakciók), biológiai rendszerekben (immunológiai reakciók) és fizikai rendszerekben (kritikus jelenségek) fordul elő. A szivárgás, a perkoláció olyan fizikai elmélet, amely lehetővé teszi számunkra a jelenségek, például a klaszterképződés, az egyik közegből a másikba történő szivárgás megértését, ennek az elméletnek az alkalmazásával az olajlerakódások hozamának becsléséhez stb.
Véletlen helyszínek (RSP)
Az RSP m x m-ből áll egy nagy véletlenszerű logikai rácsban. Tehát ez a rács olyan helyeket tartalmaz, ahol egységek és nullák vannak. Az egységekkel rendelkező helyek elfoglalt helyet képviselnek, a nulla üresek. A p valószínűsége, hogy egy sejt elfoglalt, független a szomszédaitól. A klasztert ezután a megszállt legközelebbi szomszédos cellák csoportjaként definiáljuk. (a legközelebbi szomszéd balra, jobbra, alul és felfelé jelent cellákat.
Az 5-ös méretű fürt példája:
Ha feltételezzük, hogy p az egyes cellák elfoglalásának valószínűsége (azaz 1 besorolás), akkor mekkora a 3-as méretű klaszterek várható száma a rácson? (Az egyszerűség érdekében figyelmen kívül hagyja az élhatásokat).
A legtöbb esetben lehetetlen meghatározni a végtelen fürt megjelenésének kritikus valószínűségét (vagyis azt, amely a rács egyik oldaláról a másikra nyúlik). 64x64-es szabályos négyzetrács esetén kísérletileg határozza meg a kritikus valószínűséget annak tesztelésével, hogy "végtelen fürt" jelent-e p-re (0 és 1 közötti valószínűség). Megtudhatja, ha véletlenszerű konfigurációkat állít elő rögzített számú alkalommal, hogy megkapja a végtelen fürt megjelenési eseteinek arányát, és ismételje meg ezt az eljárást a különböző p esetén. Mutassa meg a végtelen fürt megtalálásának valószínűségét p valószínűségével szemben .
(A http: //www.krl.caltech.edu/ szerint
14. téma: Az utat kereső hangyák genetikai programozása
Genetikai programozás egy "program" létrehozására a hangyák számára egy szabályrendszer felhasználásával. A hangya állítólag a toroid rácson elhelyezkedő, nem egészen folyamatos vágányra vetett ételt gyűjti össze, miközben csak korlátozott érzékelőkkel rendelkezik (tehát csak a rács oldalsó sejtjeit látja). A hangyának a lehető legtöbb táplálékot kell összegyűjteni egy adott időintervallumban. A feladat részletei a következő címen inspirálhatók: http://www2.informatik.uni-erlangen.de/
jacob/Evolvica/GP/Java/html/ant/ant.html). A feladat szabályokat generálni a) saját véletlenszerűen generált számodra, hasonló tulajdonságokkal, mint a fenti WWW-oldalról a John Muir Trail. b) Próbáljon olyan szabályokat létrehozni, amelyek egyszerre több sávra vonatkoznának.
(a csapatot Aleksandra Taká, [email protected] készíti fel)
Kidolgozott "esettanulmányok" a šk.r. 2001/2002
Aleksandra Takachi: Genetikai programozás egy hangyának, aki utat keres (esettanulmány pdf, kivitelezés exe.zip)
Alexander Moravcik: Feladatütemezési probléma (esettanulmány pdf, kivitelezés exe.zip)
Ondrej Jaura: Szótár önszervezése az ügynökök közösségében (esettanulmány pdf)
Peter Bodík: Rókák, mezei nyulak és mások (esettanulmány pdf)