DOKTORI (PhD) ÉRTEKEZÉS
BALOGH SÁNDOR
KAPOSVÁRI EGYETEM GAZDASÁGTUDOMÁNYI KAR
2009
KAPOSVÁRI EGYETEM GAZDASÁGTUDOMÁNYI KAR Informatika Tanszék
A doktori iskola vezet˝oje:
PROF. DR. UDOVECZ GÁBOR az MTA doktora, egyetemi tanár
Témavezet˝o:
DR. HABIL. CSUKÁS BÉLA CSc egyetemi docens
TÖBBSZEMPONTÚ GAZDASÁGI DÖNTÉSEKET ˝ GENETIKUS ALGORITMUS SEGÍTO KIDOLGOZÁSA ÉS ALKALMAZÁSAI Készítette:
Balogh Sándor
KAPOSVÁR
2009
Tartalomjegyzék
BEVEZETÉS
8
˝ CÉLKITUZÉSEK
11
1. SZAKIRODALMI ÁTTEKINTÉS 1.1. Globális optimalizálási módszerek és gazdasági alkalmazásaik 1.2. A többszempontú döntések módszerei . . . . . . . . . . . . . . 1.2.1. Történeti áttekintés . . . . . . . . . . . . . . . . . . . . 1.2.2. A többszempontú döntések módszerei . . . . . . . . . 1.3. A genetikus algoritmusok . . . . . . . . . . . . . . . . . . . . . 1.3.1. Az egyszempontú genetikus algoritmusok . . . . . . . 1.3.2. A többszempontú genetikus algoritmusok . . . . . . .
13 14 24 26 27 32 32 43
2. ALKALMAZOTT MÓDSZEREK
47
3. EREDMÉNYEK 3.1. A genetikus algoritmus implementációja és továbbfejlesztése . 3.1.1. Az összetett genetikus kódolás kidolgozása . . . . . . 3.1.2. A rácsmódszer kidolgozása . . . . . . . . . . . . . . . 3.1.3. A többszempontúság kezelése . . . . . . . . . . . . . . 3.1.4. Az implementációs sajátságok . . . . . . . . . . . . . 3.2. Az eddigi alkalmazások áttekintése . . . . . . . . . . . . . . . . 3.3. Illusztráló példák . . . . . . . . . . . . . . . . . . . . . . . . . .
50 51 52 56 58 60 63 66
3.3.1. Optimális pontozásos rangsorolás kialakítása pályázati döntésekhez . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Növénytermeszt˝o családi gazdaság „optimalizálása” . 3.3.3. Egy háromtermékes gyártási folyamat vizsgálata . . . 3.3.4. Tesztfeladatok . . . . . . . . . . . . . . . . . . . . . . .
66 68 72 81
4. KÖVETKEZTETÉSEK, JAVASLATOK
93
5. ÚJ TUDOMÁNYOS EREDMÉNYEK
97
ÖSSZEFOGLALÁS
101
KÖSZÖNETNYILVÁNÍTÁS
114
IRODALOMJEGYZÉK
116
˝ MEGJELENT PUBLIKÁCIA DISSZERTÁCIÓ TÉMAKÖRÉBOL ÓK 136 RÖVID SZAKMAI ÉLETRAJZ
143
2
Ábrák jegyzéke
1. 2.
13. 14.
Multimodális függvény globális és egy lokális optimuma . . . Globális optimalizálási módszerek csoportosítása (Langdon, 1998) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A metaheurisztikák megjelenésének id˝obeni áttekintése . . . . A többszempontú döntési feladat lehetséges döntési terének (X) és értékelési terének (Z) kapcsolata . . . . . . . . . . . . . . . . A Pareto front szemléltetése . . . . . . . . . . . . . . . . . . . . A szempontok súlyozott összegével történ˝o aggregáció . . . . Az evolúciós algoritmusok általános sémája . . . . . . . . . . . A genetikus algoritmus folyamatábrája . . . . . . . . . . . . . A genetikus algoritmus különböz˝o tereinek egymásra épülése Diszkrét keresztezés fajták . . . . . . . . . . . . . . . . . . . . Folytonos rekombináció típusok . . . . . . . . . . . . . . . . . Teljes permutációt megvalósító génszakaszok genetikus operátorainak egy lehetséges megvalósítása . . . . . . . . . . . . . . Diszkrét génszakaszok mutációja . . . . . . . . . . . . . . . . . A Pareto dominancia szemléltetése . . . . . . . . . . . . . . . .
15.
A genetikus algoritmus grafikus interfésze . . . . . . . . . . .
49
16. 17. 18. 19.
Az összetett rendszerek tulajdonság hálókkal történ˝o leírása . Az összetett rendszerek tulajdonság háló alapú genetikus kódolása A kialakított egyszer˝u és összetett gének . . . . . . . . . . . . Az inicializálás módosítása a rácsmódszert felhasználva . . . .
52 53 55 57
3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
15 16 19 24 26 29 33 34 37 38 39 41 41 45
20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42.
Az összetett Pareto dominancia számításának folyamata . . . . A pályázatok pontszámainak megoszlása . . . . . . . . . . . . A pályázati pontozás kialakításának értékelési tere . . . . . . . Az algoritmus alkalmazása után választott ponthatárokkal számolt pályázati összpontszámok . . . . . . . . . . . . . . . . . . A földterületek tulajdonságai valamint a támogatások és hitelek mértékének és kifizetésének adatai . . . . . . . . . . . . . . . . A növénytermesztésben felhasznált er˝oforrások tulajdonságai Az árpa termesztéséhez szükséges tevékenységek jellemz˝oi . . A cash flow diagramok összehasonlítása . . . . . . . . . . . . . A mintafeladatban szerepl˝o gyártás illusztrációja . . . . . . . . A szabályzó algoritmus transzformált megítélési függvénye . A három naturális szempont szerinti Pareto front . . . . . . . . A maximális profitot hozó gyártás elhelyezkedése a Pareto fronton A három szempontú értékelés Pareto frontjának sz˝ukítése . . . A kötött termékösszetételt tartalmazó gyártás elhelyezkedése a Pareto fronton . . . . . . . . . . . . . . . . . . . . . . . . . . . . A ZDT3 feladat Pareto frontjának közelítése . . . . . . . . . . A ZDT6 tesztfeladat nem dominált megoldásai . . . . . . . . . A ZDT3 feladat Pareto frontjának közelítése küls˝o archívum használatával . . . . . . . . . . . . . . . . . . . . . . . . . . . . A ZDT6 tesztfeladat archívum segítségével megtalált Pareto optimális megoldásai . . . . . . . . . . . . . . . . . . . . . . . . A kezdeti megoldások és aktuális Pareto frontok vándorlása ZDT3 feladat megoldása során . . . . . . . . . . . . . . . . . . A ZDT3 feladat Pareto frontjának közelítése a kifejlesztett valamint az IBEA, NSGA2, SPEA2 algoritmusokkal . . . . . A ZDT6 tesztfeladat különböz˝o algoritmusok által szolgáltatott Pareto optimális megoldásai . . . . . . . . . . . . . . . . . . . . A TNK1 feladat nem dominált megoldásai . . . . . . . . . . . Az utazóügynök probléma megoldása 100 város esetén . . . .
4
59 67 69 70 70 71 71 72 73 75 77 78 79 80 83 84 85 86 87 89 90 91 92
Táblázatok jegyzéke
1. 2. 3.
A globális optimalizálás módszereinek gyakorlati alkalmazásai 23 A legfontosabb nem interaktív módszerek és jellemz˝o tulajdonságaik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A genetikus algoritmus gyakorlati alkalmazásai a szakirodalomban 46
4. 5. 6. 7.
Az eredeti kérdések ponthatárai . . . . . . . . . . . . . . . . . . Az eredeti és a javasolt ponthatárok . . . . . . . . . . . . . . . A Single Switch Server tulajdonság osztályai és tulajdonságai A többszempontú tesztfeladatok adatai . . . . . . . . . . . . .
67 68 76 82
Algoritmusok listája
1. 2.
Sztochasztikus hegymászó . . . . . . . . . . . . . . . . . . . . . A kifejlesztett genetikus algoritmus pszeudokódja . . . . . . . .
18 62
BEVEZETÉS
Az élet minden területén alapvet˝o törekvés, hogy a különféle folyamatokat úgy alakítsuk ki, és a létez˝oeket úgy szabályozzuk, hogy azok m˝uszakilag és ezen keresztül gazdaságilag is optimálisan viselkedjenek. Az optimalizálás a lehet˝oségek közötti legjobb megoldás kiválasztását t˝uzi ki célul. Ez csak nagyon jól definiált feladatok esetében érhet˝o el. A gyakorlatban többnyire meg kell elégednünk az elegend˝oen jó, szuboptimális megoldásokkal is. Az optimalizálás hagyományos kezelésmódját az jellemzi, hogy a vizsgált feladatot, illetve annak modelljét úgy alakítjuk át, és szükség szerint úgy egyszer˝usítjük le, hogy az lehet˝ové tegye egy matematikai konstrukció keretei között az egzakt optimum meghatározását. A mérnöki munkában nagyon fontosak a részletek, ezért az elmúlt évtizedekben fokozott törekvés nyilvánult meg arra vonatkozóan, hogy az optimalizálást minél részletesebb modellek felhasználásával végezzük el. A különböz˝o folyamatok részletes, dinamikus szimulációját biztosító eszközök gyorsan fejl˝odtek, ugyanakkor az egyre bonyolultabb folytonos és diszkrét változókat vegyesen tartalmazó hibrid modellek optimalizálása egyre nehezebben megoldható feladatot jelentett az ugyancsak fejl˝od˝o optimalizálási módszerek számára. Korunk egy másik jellegzetessége az, hogy térben és id˝oben egyre nagyobb mérték˝u, változó struktúrájú és növekv˝o komplexitású feladatokat kell „optimálisan” megoldani. Mindezeket felismerve, el˝otérbe kerültek a mesterséges intelligencia, majd az ezt felváltó számítógépi intelligencia talaján kifejl˝od˝o nem egzakt, heurisztikus és evolúciós módszerek. A nem egzakt jelz˝o azt jelenti, hogy elveszítjük a garanciát az abszolút optimum megtalálására. Ezért viszont kárpótol az a tény, hogy az elegend˝oen jó megoldásokat a szükséges és elégséges mértékben legrészletesebb modellekre határozhatjuk meg. A számítógépi intelligenciához sorolható genetikus algoritmus ezen nem egzakt optimális módszerek egyike. A módszerrel a 90-es évek elején diploma dolgozatom készítésekor ismerkedtem meg. Akkori témavezet˝om még a 80as évek elején egy naiv, az ekvivalencia osztályokba sorolt tulajdonságok értékelésének visszacsatolásán alapuló megoldással kísérletezett, és diploma dolgozatom készítése id˝oszakában találkozott a szakirodalomban a genetikus algoritmussal. A módszer fejlesztése azóta végigkíséri szakmai munkámat.
8
E munka alapvet˝o jellegzetessége kezdett˝ol fogva az volt, hogy a legkülönböz˝obb szakterületeken jelentkez˝o, és a mindenkori eszközökkel nehezen kezelhet˝o részletes és/vagy nagyméret˝u hibrid modellekkel leírható feladatokat kellett optimalizálni. A gazdasági célfüggvények mellett sokszor több naturális szempont alapján kellett végezni az optimalizációt, más esetekben viszont kombináltan kellett alkalmazni gazdaságilag megfogalmazható és naturális célkit˝uzéseket. A szimulációs számításokra használt, párhuzamosan fejlesztett módszer jellemz˝oje viszont egyre inkább az lett, hogy a számítások elt˝urték a tetsz˝oleges diszkrét és folytonos változtatásokat. Eközben a nemzetközi tendenciákkal összhangban, egyre növekedett a lehetséges megoldások szimulációjának számítás igénye. Ennek alapján, a gyakorlati feladatok megoldása által vezetett kutatómunkám alapvet˝o célja, egy olyan általánosan alkalmazható genetikus algoritmus kidolgozása lett, amely a létrehozott modellek nagy számítás igénye miatt lehet˝oleg kisszámú, és kisméret˝u generáció mellett is elegend˝oen jó eredményeket szolgáltat. Emellett lényeges szempont lett a diszkrét és folytonos változók egységes kezelése és a többszempontú értékelés is. A genetikus algoritmus és a szimulátor jelent˝osen eltér˝o számítás igénye miatt ugyanakkor el˝otérbe került a makrogranuláris párhuzamosítás igénye is. Jelen dolgozatban foglalom össze az elmúlt másfél évtizedben végzett, és a gyakorlati feladatok megoldásánál már többször kipróbált munka eredményeként létrejött genetikus algoritmus jellemz˝oit.
9
˝ CÉLKITUZÉSEK
Munkám alapvet˝o célja, a szakirodalomból megismerhet˝o módszerek és az elmúlt id˝oszakban a különféle gyakorlati problémák kihívásait figyelembe véve általam folyamatosan fejlesztett genetikus algoritmus összevetése alapján egy, a tapasztalatokat ötvöz˝o, többszempontú gazdasági döntéseket segít˝o genetikus algoritmus kidolgozása. A célkit˝uzéseket meghatározó, vizsgált probléma osztályok legfontosabb jellegzetessége az, hogy a genetikus algoritmus által el˝oállított megoldások értékelése nagy er˝oforrást igényl˝o dinamikus szimuláción alapul. Fontos korlátozást jelent, hogy a térben és id˝oben nagy kiterjedés˝u hibrid modellek esetében a lehetséges megoldások kódolására az egyszer˝u sztringek már nem elégségesek. Végül egy további lényeges jellegzetesség az, hogy az egyszempontú gazdasági értékelés mellett vagy helyett, gyakran több naturális értékelési szempontot is figyelembe kell venni. Az opcionálisan többszempontú gazdasági döntések támogatásának igényeit figyelembe véve a kutatómunka f˝obb célkit˝uzései a következ˝ok: 1. A gyakorlati tapasztalatokat felhasználva, olyan összetett genetikus kódolást célszer˝u kidolgozni, amely egységes kezelést biztosít a folytonos és diszkrét, valamint teljes permutációt megvalósító génszakaszok opcionálisan hierarchikus kezelésére. Ezen túlmen˝oen, a kódolásnál az úgynevezett szerkezetháló felhasználásával lehet˝oséget kell biztosítani az inkompatibilis gének definiálására. Az így kialakítandó összetett kódolás segítségével a különféle feladatok megoldásánál ugyanannak az általános kódolási megoldásnak a részesetei alkalmazhatók, így elkerülhet˝o a speciális, egyedi módszerek használata. 2. Az egységes kódolási megoldással összhangban, további célom, a genetikus operátorok készletét felhasználva, és szükség szerint módosított operátorokat bevezetve, egy olyan megoldás kialakítása, amely a mindenkori kódoláshoz igazodva automatikusan alkalmazza a megfelel˝o operátorokat. 3. További célom, hogy olyan paraméterezhet˝o módszert, és az ehhez illeszked˝o paraméterezhet˝o módosított genetikus operátorokat dolgozzak 11
ki, amelyek támogatják az evolúciós folyamat kis populáció méret mellett történ˝o végrehajtását. E célkit˝uzés érdekében a szakirodalmi tapasztalatok és a korábbi id˝oszakban végzett gyakorlati alkalmazások tapasztalatainak felhasználásával célom egy új, úgynevezett rácsmódszer kidolgozása. 4. A többszempontúság kezelésére célom egy, az összetett Pareto dominancia számítására alkalmas algoritmus, valamint az algoritmus m˝uködését támogató, paraméterezhet˝o operátorok kidolgozása. 5. További célom a kidolgozott algoritmusok olyan implementálása, amely a kisszámú, nagy számításigény˝u egyedek vizsgálatán alapuló evolúciós folyamatot támogatja. Ennek során, célom egyrészt annak hasznosítása, hogy lehet˝oség van az összes el˝oállított genetikus kód hatékony tárolására. Másrészt, a makrogranulárisan párhuzamosítható (például PC klaszter) architektúrák lehet˝oségeit felhasználva, célom az értékelést biztosító szimulációk genetikus algoritmus által irányított automatikus párhuzamosítása. A kifejlesztett megoldások döntéseket támogató, gazdasági és logisztikai alkalmazását illusztráló egyszer˝u példák és a szakterületen alkalmazott tesztfeladatok segítségével mutatom be.
12
1. FEJEZET SZAKIRODALMI ÁTTEKINTÉS
1.1. Globális optimalizálási módszerek és gazdasági alkalmazásaik A különféle folyamatok megismerésének és tanulmányozásának egyik legfontosabb célja az adott folyamat valamilyen (rendszerint gazdasági) szempont(ok) szerinti optimális tervezése vagy m˝uködtetése. A globális optimalizálás célkit˝uzése az, hogy egy X halmaz x elemei közül, valamilyen F = { f 1 (x), f 2 (x), f 3 (x), . . . , f k (x)} szempontok szerint megtalálja a legjobb x ? elemet. Az általánosság miatt egyenl˝ore tételezzük fel, hogy egyetlen f (x) érték szerint keressük a legjobb elemet, és a legjobb elem e szempont szerinti értéke a legkisebb. Ekkor a globális optimalizálási probléma tömören a min f (x) x∈X
(1)
formára hozható, ahol az f : X → R skalár értékelési függvényt szeretnénk minimalizálni az X halmaz elemein. A gazdasági életben használt optimalizálási feladatok dönt˝o többségénél azonban még további feltételeknek is teljesülniük kell. Ezek az ún. megkötések (constraints) a
g i (x) ≥ 0
(2)
h j (x) = 0
(3)
kifejezésekkel formalizálhatók, ahol g i : X → R és h j : X → R skalár megkötések és 0 < i < m , 0 < j < p . Az X halmaz elemei az optimalizálási feladattól függ˝oen lehetnek számok, vektorok, listák, komplex ütemezési tervek . A halmazt keresési térnek, döntési térnek vagy lehet˝oségtérnek is nevezzük a továbbiak során. Az értékelési függvények sem csak egyszer˝u matematika kifejezések, hanem a problémától függ˝oen összetett számítógépes algoritmusok, bonyolult gazdasági és/vagy technológiai folyamatok dinamikus szimulációi alapján számított összefüggések ¡ ¢ is lehetnek. Megjegyezzük, hogy mivel max f (x) = min − f (x) ezért az általá14
Globális széls˝oérték Lokális széls˝oérték − f (x) x2
x1
1. ábra. Multimodális függvény globális és egy lokális optimuma. (A jobb láthatóság érdekében egy maximalizálási feladat optimumait illusztráljuk.)
nosság megsértése nélkül a következ˝okben az optimalizálás minimalizálást jelent. A globális optimum tehát az x ? ∈ X elem, ha f (x ? ) ≤ f (x) ∀x ∈ X. Fontos még rögzítenünk a lokális optimum fogalmát. Az xˆ ∈ X elemet lokális ˆ ≤ f (x) minden olyan x ∈ X elemre, optimumnak nevezzük, ha igaz az, hogy f (x) amelyek xˆ szomszédjai. Abban az esetben, ha X ⊆ Rn , akkor ∀xˆ ∃² > 0, hogy ˆ ≤ f (x) ∀x ∈ X, |xˆ − x| < ².A lokális és a globális optimum jelentését az 1. f (x) ábrán szemléltetem. A szakirodalom a globális optimalizálás módszereinek három f˝o típusát különbözteti meg. Az els˝o a gradiens alapú, második a kimerít˝o keresésen alapuló és a harmadik a véletlent használó optimalizálási eljárás. A továbbiakban rövid áttekintést szeretnék nyújtani a 2. ábrán látható módszerekr˝ol, ismertetve a fontosabb módszerek el˝onyeit és hátrányait. A gradiens alapú módszerek kifejlesztése és tanulmányozása már évszázadokkal ezel˝ott megkezd˝odött és két f˝o típusa alakult ki, a direkt és indirekt eljárások. Az utóbbiak használata során a széls˝o értékeket a derivált függvény zérus helyeinek meghatározásával keresik meg, amely általában egy egyenletrendszer megoldását jelenti. Több dimenziós függvények esetén ez úgy
15
Részecske–raj algoritmus
Genetikus algoritmusok
Evolúciós programozás
Evolúciós algoritmusok
Evolúciós startégiák
Dinamikus programozás
Elágazás és korlátozás
Hangya kolónia Tabu keresés
Sztochasztikus módszerek
Optimálási eljárások
Szimulált h˝utés
Sztohasztikus hegymászó
Gradiens alapú Kimerít˝o keresésen alapuló
Visszalépéses technika
Indirekt Direkt Newton Fibonachi
2. ábra. Globális optimalizálási módszerek csoportosítása (Langdon, 1998)
módosul, hogy a széls˝o érték keresését azon pontokra korlátozzuk, amelyek érint˝o síkjának meredeksége minden irányban zérus. A direkt módszerek esetén a széls˝o értéket a lokális gradiens irányába történ˝o elmozdulással próbálják elérni. Ezt általában hegymászásnak nevezik, azaz a széls˝o érték eléréséhez (típusától függ˝oen) a legmeredekebb emelked˝on vagy lejt˝on kell „felmászni”, illetve „leereszkedni”. Mindkét módszer hiányossága azonban (a többszöri javítás, fejlesztés és kiterjesztés ellenére is az), hogy nem eléggé robusztusak a gyakorlatban el˝oforduló feladatok széles spektrumára. Az indirekt módszerek megkövetelik, hogy ismerjük a megoldandó feladat derivált függvényét. Sajnos valós a életben el˝oforduló problémák jelent˝os hányadára nem igaz ez a feltételezés, így az indirekt módszer gyakorlati felhasználhatósága meglehet˝osen korlátozott. A direkt módszerek valamelyest enyhébb feltételeket fogalmaznak meg a
16
feladattal szemben, de a gyakorlatban használva legjobb esetben is csak lokális széls˝oértékek felderítése lehet a céljuk. A második f˝o típust a kimerít˝o keresésen alapuló módszerek alkotják. Ezeknek a módszereknek az a lényege, hogy az adott lehet˝oségtérben az algoritmus megvizsgálja a tér minden pontját és így keresi meg a globális optimumot. A lehet˝oségtér pontjai legtöbbször leírhatók egy fa struktúrával, ezután a tér teljes bejárása elvégezhet˝o a fában található valamennyi csomópont érintésével. A fa bejárására különféle stratégiákat alkalmazhatunk: például mélységi bejárás, szélességi bejárás, azonban a gyakorlati feladatok lehet˝oségtere annyira kiterjedt, hogy belátható id˝on belül nem tudjuk elvégezni a teljes fa bejárását. Néhány esetben használhatjuk az elágazás és korlátozás elvét, ha olyan feltételek és/vagy megkötések állnak rendelkezésünkre, amelyek alapján az adott csúcsot vizsgálva eldönthet˝o, hogy az optimum nem az adott csúcsból induló részfában található. Ekkor ezt a részfát kihagyhatjuk a további keresésb˝ol, így csökkentve a keresési tér méretét. A valós problémák lehet˝oségterének komplexitása azonban határt szab e módszer hatékonyságának is, mivel ésszer˝u id˝on belül és/vagy gazdaságosan nem lehetséges az összes megoldás, vagy annak akár egy részének a bejárása sem. A gyakorlati feladatokra mindinkább jellemz˝o, hogy lehet˝oségterük nagyméret˝u és/vagy sokdimenziós, valamint nincs sok információnk a „jóságot” meghatározó, általában zajjal is terhelt értékelési függvényr˝ol. Ezért a fentebb bemutatott determinisztikus módszerek nagyon korlátozottan alkalmazhatók a megoldásukra. Ezt az hiányt próbálják betölteni a globális optimalizálási algoritmusok harmadik típusához tartozó sztochasztikus vagy véletlent használó módszerek. Ezeknél a módszereknél a véletlen is fontos szerepet játszik a keresési tér vizsgálandó pontjainak kiválasztásakor. Az egyik alapvet˝o és legegyszer˝ubben megvalósítható módszer a sztochasztikus hegymászás. Ennél az eljárásnál e keresési tér egy véletlenül választott aktuális pontjából indulunk ki, majd a „szomszédos pontok” közül sztochasztikusan választva, az lesz az új aktuális pont amelyik értéke nagyobb, mint az eredetileg választott pont értéke. Az eljárás el˝onye az, hogy a feladat értékelt terének struktúrájáról semmilyen
17
információt nem használ fel, hátránya viszont az, hogy nagy valószín˝uséggel egy lokális optimum csapdájába kerül. A sztochasztikus hegymászó konkrét megvalósítását az 1. algoritmus szerint végezhetjük el. 1. algoritmus: Sztochasztikus hegymászó Input: f : a minimalizálandó értékel˝o függvény Data: p new : az újonan generált elem Data: p ? : az (aktuálisan) legjobb elem Output: x ? : a talált legjobb megoldás 1 2
begin
3 4 5
p ? .x ←− create() while terminationCriterion() ¡ ?do¢ p new . x ←− neighbour ¡ ¢ ¡ ¢p . x if f p new .x < f p ? .x then p ? ←− p new
6
return p ? .x
7
end
A véletlent is használó keres˝o eljárások egyik legígéretesebb és egyben legintenzívebben kutatott területe, a különféle metaheurisztikákon alapuló optimalizálási eljárások csoportja. A metaheurisztikák – a feladat specifikus heurisztikákhoz képest – a problémák egy szélesebb osztályára nyújtanak megoldási lehet˝oséget. Módszertanuk alapötlete leggyakrabban a természetben megfigyelt folyamatokon alapul. Nem garantálják a globális optimumot, de belátható id˝on belül az optimumhoz közeli szuboptimális megoldást szolgáltatnak. A metaheurisztikát használó módszerek id˝obeni megjelenését a 3. ábrán követhetjük figyelemmel. A következ˝okben – a teljesség igénye – nélkül röviden áttekintjük a legfontosabb metaheurisztikus módszereket és azok jellemz˝ot (Gonzalez, 2007). A szimulált h˝utés (Kirkpatrick et al., 1983) a szilárd anyagok h˝okezelés hatására végbemen˝o energetikailag „optimális” rácsszerkezetének kialakulását másolja le. A kezdeti magas h˝omérsékletre felmelegített anyag részecskéi viszonylag szabadon mozoghatnak az energiaszintek között, majd a h˝omérséklet fokozatos csökkentésével egyre kisebb energiaszint ugrásokat tudnak végrehajtani, és így a nagyon alacsony bels˝o energiájú szabályos kristályszerkezetben stabilizálódnak.
18
Id˝o 2010
Mesterséges méh algoritmusok Méh algoritmus
T˝uzlégy algoritmusok 2005 2000
Részecske-raj algoritmusok
Memetikus algoritmusok Mesterséges immun rendszerek
Harmónia keres˝o algoritmusok
1995 1990 1985
Hangya kolónia algoritmusok Tabu keresés Szimulált h˝utés
Genetikus programozás leírása
1980 1975
Genetikus algoritmusok
1970
Evolúciós stratégiák
1965
Evolúciós programozás
1960
Az els˝o evolúciós optimalizálás
1955
Az els˝o sztochasztikus módszerek 1950
3. ábra. A metaheurisztikák megjelenésének id˝obeni áttekintése
Az algoritmikus megvalósítás alaplépései nagyon hasonlítanak a sztochasztikus hegymászás lépéseihez. Az algoritmus végrehajtása során véletlenszer˝uen választott „szomszédok” közül az aktuális egyednél rosszabb érték˝ut is elfogadunk a h˝omérséklet függvényében változó valószín˝uséggel az algoritmus során. A h˝omérsékletet az algoritmus futása során egyre csökkentjük, azaz „h˝utést” alkalmazunk, így a rosszabb egyedek elfogadási valószín˝usége egyre csökken. A h˝utés tervezését a következ˝o képlet szerint végezhetjük: T (t + 1) := αT (t ), ahol 0 < α < 1 és t az aktuális id˝o. Az elfogadási valószín˝uséget pedig a P (t ) = exp(∆f/T(t)) képlet szerint számítjuk, ahol ∆ f a két egyed értékének különbsége és T (t ) az aktuális h˝omérséklet. Az így kialakított algoritmus már képes lehet a globális optimum megtalálására, azonban nagyon er˝oforrás igényes és nagyon érzékeny a paramétereinek1 1A
„szomszéd” kiválasztást és a h˝utést meghatározó jellemz˝ok
19
megfelel˝o megválasztására. Jelenleg nem ismerünk olyan szabályt, ami a különböz˝o feladattípusok esetén segítséget nyújthatna a paraméterek helyes hangolásához. Az eljárás hatékonyságát növelhetjük, ha többször újraindítjuk vagy újra f˝utjük a rendszert. A tabu keresés Glover (1986) szintén az egy megoldással dolgozó, véletlent használó metaheurisztikák közé tartozó módszer. A nevében szerepl˝o, a polinéz szigetvilágból ered˝o tabu szó jelentése szent hely vagy szent tárgy, amelyeket tilos meglátogatni vagy megérinteni. A sztochasztikus hegymászást alapul véve alapgondolata a következ˝o: A keresési tér már eddig bejárt pontjait egy tabu (tiltó) listára gy˝ujtjük. A kiválasztott új pontot megvizsgáljuk, és csak akkor fogadjuk el ha nem található meg a tabulistán. Elfogadás esetén hozzáf˝uzzük a listához, ellenkez˝o esetben eldobjuk és új pontot keresünk. A lista mérete természetesen nem n˝ohet egy bizonyos kezelhetetlen méret fölé, így a lista hossza egy szabadon választott n egész szám. Ha ezt az n hosszúságot elérte a listánk és a következ˝o pontot a listára akarjuk helyezni, akkor annak legrégebbi elemét töröljük. A raj intelligencia egy olyan összetett csoport viselkedésforma, amelynél a rajba tartozó egyedek csak a saját közvetlen környezetük alapján hozzák meg a döntéseiket, összességében azonban mégis egy globális intelligens viselkedés alakul ki. A következ˝okben a raj intelligenciát használó eljárások két jellemz˝o reprezentánsát mutatom be. A hangya kolónia algoritmus (Stickland et al., 1992; Dorigo et al., 1996) is a természetb˝ol vette az alapötletét. A koncepció a táplálékot keres˝o hangyák viselkedését veszi alapul. A hangyák igen kifinomult módszereket alkalmaznak a kommunikációhoz, ugyanis a bolytól a különböz˝o táplálékforrásokhoz vezet˝o útvonalakat feromon hormon kibocsátásával jelölik meg. Ezeket a feromon útjelzéseket a többi hangya érzékeli, és nagy valószín˝uséggel követni kezdi. A táplálék felé vezet˝o ösvények nagyon különböz˝oek lehetnek és akár akadályokat is találhatunk rajtuk. A hangyák célja természetesen a legtöbb élelem begy˝ujtése. Az egyes egyedek lehet˝oségei korlátozottak, viszont a kolónia egésze igen hatékonyan tudja megoldani ezt a problémát. A hangya kolónia algoritmust általában kombinatorikus optimalizálásra
20
használják. Egyik lehetséges implementációban (Carbonaro and Maniezzo, 2003) a hangyáknak egyszer˝u ágensek felelnek meg. Az irányított gráfként szemléltethet˝o állapottér éleihez feromon csík értékeket rendelünk. A sikeres ill. kevésbé sikeres megoldások növelhetik ill. csökkenthetik az élekhez tartozó értékeket. A korábbi sikeres útvonalakat a feromon csík érték mátrixa tárolja. Az ágensek lépésr˝ol lépésre építik fel az útvonalakat. Ehhez kiszámolják a lehetséges következ˝o lépéseket és egy adott valószín˝uséggel választanak bel˝ole. A választási valószín˝uségek függnek egy lépésekhez rendelt heurisztikus értékt˝ol és a feromon csík értékét˝ol. A részecske-raj optimalizálás (Eberhart and Kennedy, 1995; Kennedy and Eberhart, 1995) madárcsapatok, halrajok, méhek vagy valamilyen együtt mozgó részecskék mozgásának modellezésén alapuló eljárás. A raj egyedei egy-egy megoldást írnak le a keresési térben és az egyedek valamilyen topológia szerint egymáshoz vannak kapcsolva. Minden részecske ismeri a topológia szerinti szomszédok (és természetesen saját maga) addigi legjobb értékét (aktuális lokális optimum) és a raj által elért legjobb értéket (aktuális globális optimum). Az egyedek minden lépésben módosítják a helyzetüket az addigi lokális és globális optimumot valamint a jelenlegi vagy múltbéli helyzetüket kombinálva. A kombináció kialakítása során véletlen értékeket is felhasználnak. A globális optimalizálás módszerei közül, az evolúciós algoritmusok alkotják a metaheurisztikát alkalmazó módszerek következ˝o nagy csoportját. Az evolúciós algoritmusok a keresési tér pontjait reprezentáló adatszerkezetek (kódok) populációját használó, a biológiából származó mechanizmusokkal dolgozó optimalizálási eljárások. A mutáció, a keresztezés, a szelekció, a jobban alkalmazkodó (fittest) egyedek túlélése, stb., azt próbálja biztosítani, hogy iterációról iterációra (generációs lépések) javuljon populáció min˝osége. A biológiai analógiát felhasználva az evolúciós algoritmusokat kétféle alaptípusba sorolhatjuk a keresési tér kódolásának tulajdonságai szerint. Ezek a genotípus vagy a fenotípus szintjén keresik a jobb megoldásokat. A genotípus a természetben a génekben tárolt információk összessége, amely a környezettel együttesen határozza meg az egyedek küls˝o megjelenését vagyis a fenotípusát. A fenotípus genotípusból való meghatározásához tehát ismernünk és alkalmaznunk
21
kell egy sokszor bonyolult és nem egyértelm˝uen megadható dekódoló függvényt, ami azért a természethez hasonlóan sokszor univerzálisan alkalmazható. Tehát a keresési teret a genotípus és fenotípus szerint is kialakíthatjuk. A szakirodalom az evolúciós algoritmusok családjának négy jellemz˝o tagját különbözteti meg. – A genetikus algoritmusok közé klasszikusan azokat az evolúciós algoritmusokat soroljuk, amelyek a keresési teret bitsztringek segítségével fedik le, azaz a megoldásokat a genotípus szintjén keresik. F˝o m˝uvelete a keresztezés, a mutációt ritkábban alkalmazza. Az újabb genetikus algoritmusok azonban a valós értéket tartalmazó sztringekkel (vektorokkal) is sikeresen megbirkóznak. – A genetikus programozás eredetileg genetikus algoritmusból származtatott módszer. Célja számítógépes programok fejlesztése, valamilyen számítási probléma megoldása érdekében. Szakít a bitsztringes ábrázolásmóddal és fa szerkezetben tárolja a genetikus kódot. – Az evolúciós programozás a genetikus programozáshoz hasonlít, de a programok struktúrája fix, és a keresési teret csak a programok paraméterei feszítik ki. A paraméterek a fenotípus szintjén értelmezettek és f˝o keresési m˝uvelete a mutáció. Több mint egy évtizede nagyrészt beolvadt a genetikus programozásba és a többi evolúciós módszerbe. – Az evolúciós stratégiák az evolúciót a fenotípus szintjén értelmezik, az egyedeket valós vektorok formájában kódolva, keresik az optimumot a keresési térben. A legfontosabb m˝uvelete a mutáció, de a rekombinációt is intenzíven használja. Az evolúciós algoritmus változatainak részletesebb bemutatása megtalálható (Borgulya, 2004) könyvében . Felmerülhet a kérdés, hogy miért alakult ki a metaheurisztikát alkalmazó algoritmusok ilyen sok fajtája. Erre ad választ a optimalizálási és keres˝o algoritmusokra megfogalmazot és formalizált „nincs ingyen ebéd” elmélet (Wolpert and Macready, 1995, 1997). Az elmélet szerint nincs olyan algoritmus, amely az 22
1. táblázat. A globális optimalizálás módszereinek gyakorlati alkalmazásai Alkalmazási területek
Hivatkozások
Gazdasági feladatok
Dzemyda et al. (2002); Floudas and Pardalos (2003); Jerrell (2000) Chankong and Haimes (1983); Haimes and Steuer (1998) Birk et al. (2004); Floudas and Pardalos (2003); Satoh et al. (1996); Dzemyda et al. (2002); Chawdry et al. (1998) Bhaskar et al. (2000); Sahinidis and Tawarmalani (2000); Floudas and Pardalos (2003) Floudas (1999); Floudas and Pardalos (2003) Banerjee and Hazra (1998); Tsao and Chern (2006) Corne et al. (2000) Haimes et al. (1975) Galperin and Kansa (2002) Neumaier (2006)
Többszempontú döntések (MCDM) Mérnöki optimalizálás és tervezés
Vegyész, vegyészmérnöki Biológia, biokémia Optika Telekommunikáció Operáció kutatás Matematikai problémák Reláció-homomorfizmus problémák (CSP)
összes feladattípuson hatékonyabb megoldást kínálna minden más módszernél. A gyakorlati felhasználás szempontjából ez azt jelenti, hogy ha az adott probléma típusra már létezik speciális optimáló eljárás, akkor az hatékonyabb tud lenni, mint például a problémák széles spektrumán alkalmazható és hatékony genetikus algoritmus. A gazdasági, m˝uszaki és tudományos élet különböz˝o területein felmerül˝o globális optimalizálási feladatok megoldására és problémáira vonatkozóan részletes elemzésekre jellemz˝o példákat foglaltam össze az 1. táblázatban. A gazdasági optimalizálás jelent˝oségét felismerve Magyarországon is számos jelent˝os módszertani fejlesztés folyt úttör˝o jelleg˝u gyakorlati alkalmazásokkal. A rendkívül szerteágazó kutatások és alkalmazások átfogó ismertetése szétfeszítené a dolgozat kereteit. Lényeges azonban megemlíteni azt, hogy csupán Doktori Iskolánk sz˝ukebb szakterületén, a gazdaságtudomány és az agrártudomány metszetében is nagyon sok jelent˝os eredmény született már évtizedekkel ezel˝ott is (Csáki, 1969) (Acsay et al., 1973) (Csáki and Varga, 1976) (Guba et al., 1977) (Udovecz, 1982).
23
x2
f1 f (x)
z
P (X)
x
X
Z
P F (X)
x1 x3 f2
4. ábra. A többszempontú döntési feladat lehetséges döntési terének (X) és értékelési terének (Z) kapcsolata. A döntési térben látható sötétebb színnel jelölt rész a Pareto optimális megoldások (P (X)), az értékelési térben látható vastagabb vonal pedig a Pareto frontot (P F (X)) jelöli.
1.2. A többszempontú döntések módszerei Az el˝oz˝oekben áttekintettük a globális optimalizálás fogalmait és legfontosabb módszereit. Az ott bemutatott eljárások tulajdonságait olyan aspektusban tárgyaltuk, amelyben a keresési tér pontjaihoz jellemz˝oen egy értékelési függvényértéket rendeltünk. A gyakorlati életben azonban számos gazdasági és mérnöki probléma megoldása során, többféle szempont szerinti értékelést kell párhuzamosan figyelembe venni az optimális megoldás(ok) meghatározásakor. Ezt formalizálva az optimalizálási problémát a következ˝oket kapjuk: min { f 1 (x), f 2 (x), f 3 (x), . . . , f k (x)}
x∈X, k≥2
(4)
Jelen esetben az f i : Y → R, ahol 1 < i < k , értékelési függvényeket szeretnénk szimultán minimalizálni. A döntési térben az x megoldás vektorok a lehetséges megoldások X ⊆ Y halmazába tartoznak. Ez esetben nem térünk ki a lehetséges megoldások halmazát meghatározó megkötések típusára. A lehetséges megoldások halmazának (X) képe az értékelési térben az értékelési függvényértékek, azaz
24
a z = f (x) = ( f 1 (x), f 2 (x), f 3 (x), . . . , f k (x))T vektorok halmaza. Ezt a Z = f (X) halmazt a lehetséges értékek halmazának nevezzük. A többszempontú optimalizálásnál optimálisnak nevezünk egy z értékelési vektort ha egyetlen komponense sem javítható (minimalizálásnál nem csökkenthet˝o) anélkül, hogy egy másik komponens értéke nem romlana (minimalizálásnál nem növekedne). Pontosabban egy x ? ∈ X megoldásvektort akkor nevezünk Pareto optimálisnak, ha nem létezik más olyan x ∈ X, hogy minden i = 1, . . . , k esetén f i (x ? ) ≥ f (x) valamint legalább egy j index melyre f j (x ? ) > f j (x). A Pareto optimális megoldásvektorok halmazának jelölése P (X). Hasonlóan a Pareto front a Pareto optimális megoldásvektorok képe az értékelési térben, azaz P F (X) = f (P (X)). A többszempontú optimalizálás döntési és értékelési terének kapcsolatát a 4. ábrán láthatjuk. A több szempont szerinti értékelést alkalmazó problémák megoldása sokkal összetettebb feladat mint az egyszempontú optimalizálási feladatoké, mivel az optimális megoldások a dönt˝oen több elem˝u P (X) halmaz elemei. Az 5. ábrán egy Pareto frontot láthatunk. Az többszempontú döntések problémáival foglalkozó kutatási terület a többszempontú döntések (multiple criteria decision making, MCDM) vagy többszempontú döntéstámogatás (multiple criteria decision aiding, MCDA) néven ismert. A többszempontú optimalizálás folyamatában klasszikusan egymás mellett található meg az optimalizálási módszer és a döntéshozás abból a célból, hogy a segítse a döntéshozót (decision maker, DM) a preferenciáinak legjobban megfelel˝o Pareto optimális2 megoldás kiválasztásában. A folyamat tehát két f˝o részre osztható, az optimalizálási folyamatra és döntéshozó folyamatra. Jelen dolgozat célkit˝uzései között nem szerepel a döntési folyamat komplex vizsgálata (Kindler, 1991; Temesi, 2002), hanem csak a döntési folyamat globális optimalizálás módszereivel való támogatásának lehet˝oségeivel foglalkozunk. 2 Ellenkez˝ o
esetben a döntés nem lenne racionális.
25
f1
I E A H
F B
G C
Pareto optimumok
D f2
5. ábra. A Pareto front szemléltetése.
1.2.1. Történeti áttekintés A többszempontú optimalizálás gyökerei nem annyira új kelet˝uek mint gondolhatnánk. Egyes szerz˝ok szerint (Stadler, 1986) a többszempontú optimalizálás elválaszthatatlan része a gazdasági egyensúly elméletének, és így visszavezethet˝o egészen 1776-ig, Adam Smith „The Wealth of Nations” cím˝u m˝uvének megjelenéséig. A gazdasági egyensúly általános megfogalmazása Léon Walras-hoz köthet˝o, de William Stanley Jevons, Carl Menger, Francis Ysidro Edgeworth és Vilfredo Pareto (Pareto, 1912) munkássága is meghatározó jelent˝oség˝u ebben a témakörben az 1874 és 1912 közti években. A többszempontú optimalizálás vonatkozásában a játékelmélet megjelenése szintén fontos mérföldk˝onek számított. Legtöbben a játékelmélet megjelenését Neumann János 1926-ban elhangzott el˝oadásához (majd 1928-ban megjelent publikációjához (Neumann, 1928)) kötik. Neumann János és Oskar Morgenstern 1944-ben megjelent könyvükben (Neumann and Morgenstern, 1944) megemlítik, hogy a klasszikus matema26
tika nem foglalkozik a gazdasági életben megjelen˝o ellentmondó érdekek, optimalizációs problémaként való megoldásával. Sajnos a továbbiakban nem foglalkoztak részletesebben a felvetett problémával, és egészen az 1950-es évekig nem történt lényegi el˝orelépés a megoldásban. A napjainkban is ismert többszempontú optimalizálás területének igazi kibontakozása és matematikai vizsgálata az 1950-es évek után indult meg, tehát egy viszonylag fiatal diszciplínáról beszélhetünk. Tjalling C. Koopmans 1951-ben az „Activity Analysis of Production and Allocation” (Koopmans, 1951) cím˝u könyvében használja el˝oször a „hatékony” vektor fogalmat3 . A többszempontú optimalizálás matematikailag is korrekt vizsgálatában az egyik legfontosabb eredmény az Abraham Charnes és William Wager Cooper által bevezetett cél programozás (Charnes and Cooper, 1957, 1961). A korrekt és komoly matematikai leírást Leonid Hurwicz (Hurwicz, 1958) adta, aki általánosította Kuhn és Tucker (Kuhn and Tucker, 1951) eredményeit a vektor maximum problémák kezelésében. Az 1960-as években a nagy állami beruházások beindulása még inkább megkövetelte a döntések többszempontú megközelítését. A döntéshozók és tervez˝ok körében az egymásnak ellentmondó szempontok viselkedésének megfigyelése általánossá vált. Az eredetileg a gazdasági matematika felségterületéhez tartozó módszer ezek után kezdett elterjedni a mérnöki és egyéb tudományterületeken. Igazán széles körben azonban csak az 1970-es évekt˝ol kezd˝od˝oen terjedt el. Nagyon jó áttekintés kapható a többszempontú optimalizálás történetér˝ol és fejl˝odésér˝ol (Ehrgott and Gandibleux, 2002), valamint (Cohon and Marks, 1975) munkáiban.
1.2.2. A többszempontú döntések módszerei A többszempontú optimalizálási problémák (multiobjective optimalization problems, MOOP) megoldására számos módszer található az MCDM szakirodalmában(Haimes and Steuer, 1998; Branke et al., 2004). A MOOP kezelésének bemutatott módon négy csoportját különböztethetjük 3 Koopmans
ezen munkájának is köszönhet˝oen kapja meg a Nobel díjat 1975-ben.
27
meg attól függ˝oen, hogy a döntéshozó mikor adja meg a preferenciáit az optimalizálási folyamat végrehajtásához képest (Branke et al., 2006). A dolgozat keretei között most nem szentelünk figyelmet a lineáris feladatok optimalizálási módszereinek, inkább a gyakorlati életben el˝oforduló nemlineáris feladatok megoldásának f˝o módszereit tartjuk szem el˝ott. A módszereket az alábbiak szerint csoportosíthatjuk: – A preferenciát nem használó eljárások során vagy hiányzik a döntéshozó, vagy nem tudja megadni preferenciáit. – Az a priori módszerek esetén a preferenciák illesztése az optimalizálás el˝ott történik. Az optimalizációs folyamat el˝ott aggregáljuk az értékelési függvényeket és az így kapott egyszempontú feladatot oldjuk meg. – Az interaktív metódusok alkalmazása során a döntéshozó az optimalizálási folyamat közben aktívan illeszti és az eredmények ismeretében módosítja preferenciáit. Az interaktív metódusok áttekintését adja (Branke et al., 2008) könyve. – Az a posteriori módszerek koncepciója az, hogy az optimalizálási folyamat Pareto optimális megoldásokat szolgáltat (generálja a megoldásokat) és a döntéshozó ezek közül választ a preferenciái alapján. A módszerek akkor használhatók, ha az általuk kapott megoldás Pareto optimális, illetve képesek bármely Pareto optimális megoldás el˝oállítására. Az alábbiakban két népszer˝u és klasszikus módszer legfontosabb tulajdonságait mutatom be részletesebben. Mindkét módszert alkalmazzák a priori és a posteriori módszerként is. Az egyik leggyakrabban használt és legegyszer˝ubb aggregációs eljárás az értékelési szempontok súlyozott összegének alkalmazása (Gass and Saaty, 1955; Zadeh, 1963). Az így kapott optimalizálási feladat a min
k X
x∈X, w i >0 i =1
alakban írható, ahol w i ∈ R+ és
Pk
i =1 w i
w i f i (x)
(5)
= 1.
28
i si
álá
im pt
O
f2
Pareto front
ny
rá
F ag g r = w 1 F 1 + w 2 F 2
Lehetséges megoldások
f1
a) A szempontok súlyozott összegének alkalmazása konvex Pareto front esetén.
f2
Pareto front
Op tim álá
si
irá
ny
Lehetséges megoldások
F ag g r = w 1 F 1 + w 2 F 2
f1
b) A szempontok súlyozott összegének alkalmazása konkáv Pareto front esetén.
6. ábra. A szempontok súlyozott összegével történ˝o aggregáció.
29
Az értékelési függvények értékkészlete más nagyságrend˝u lehet, ezért sokszor el˝oször normalizálni kell a szempontokat. El˝onye a módszernek az egyszer˝u formalizálhatóság és a szolgáltatott megoldások Pareto optimalitása, hátránya viszont, hogy a súlyok megválasztása és a kapott megoldás közötti kapcsolat tisztázatlan. Másik hátrányos tulajdonsága a módszernek, hogy a Pareto front konkáv részén fekv˝o megoldások elvesznek a döntéshozó számára, tehát a Pareto front el˝oállítása nem lehetséges minden esetben (Steuer, 1989). A módszer illusztrációja konvex és konkáv Pareto front esetén a 6.a) , illetve a 6.b) ábrán látható. Az ²-korlátozás módszer (Chankong and Haimes, 1983) használata során az egyik kiválasztott értékelési függvény szerint optimalizálunk, a fennmaradó szempontokat pedig megkötésekké konvertáljuk. Az el˝obbiek szerint módosult feladat a min f l (x)
(6)
f i (x) ∀ j ∈ {1, . . . , k} \ {l }
(7)
x∈X
²j
≥
kifejezésekkel írható le, ahol l ∈ {1, . . . , k} és ² j ∈ R. A módszer el˝onye, hogy könnyen implementálható és képes Pareto optimális megoldást szolgáltatni, viszont nagyon számítás igényes hiszen a megoldás csak akkor Pareto optimális, ha a (6) feladatot megoldjuk minden l ∈ {1, . . . , k}-re, amikor ² j = f (x) ∀ j ∈ {1, . . . , k} \ {l }. A szerteágazó módszerek áttekintésének megkönnyítése érdekében a 2. táblázatban foglaltam össze a nem interaktív eljárások f˝obb jellemz˝oit. A táblázatban a leggyakrabban használt módszerek tulajdonságait tüntettem fel, úgymint a preferencia információ megadásának lehetséges módozata, a módszerrel kapható megoldás(ok) optimum tulajdonságai, és a preferencia információ bevitelének típusa.
30
∗
+
∗
+
célprogramozás
+ + + +∗
lexikografikus rendezés
+ +∗ +∗
érték függvény
+ +
teljesítmény skalarizáció
+ +
súlyozott metrikák
+
+ + + +∗
semleges kompromisszum
+ +
globális kritérium
nincs preferencia a priori módszer a posteriori módszer bármely P (X) el˝oállítható a megoldás mindig P (X) eleme a preferencia információ típusa szerint súlyok határok referencia pont érték függvény lexikografikus sorrend
²-korlátozás
súlyozás
2. táblázat. A legfontosabb nem interaktív módszerek és jellemz˝o tulajdonságaik. A +∗ jel a további feltételek teljesülése esetén érvényes tulajdonságokat jelöli. Forrás: Branke et al. (2008)
+
+
+ +
+
+
+∗
+ + +
+ + +
+∗
31
1.3. A genetikus algoritmusok 1.3.1. Az egyszempontú genetikus algoritmusok A 20. század közepét˝ol az evolúciós folyamat, mint optimalizálási eszköz egyre inkább a tudományos érdekl˝odés középpontjába került. Az 1960-as években Rechenberg az un. evolúciós stratégia (Rechenberg, 1965, 1973) gondolatával állt el˝o, melyet a gyakorlatban valós érték˝u paraméterek optimalizálására alkalmazott különféle szerkezetek jellemz˝oinek javításához. Owens és Walsh 1966-ban kidolgozta az evolúciós programozás módszerét , és megjelenik a publikációjuk (Fogel et al., 1966), mely ismerteti ezen új evolúciós technikát. Ezt követte 1975-ben, az evolúciós algoritmusok területének gerincét alkotó harmadik elem, a John Holland által leírt genetikus algoritmus kidolgozása és publikálása (Holland, 1975). Bár Holland célja eredetileg az volt, hogy olyan módszert dolgozzon ki, melyben a természetes szelekció és adaptáció mechanizmusa bevihet˝o lenne a számítógépes programokba, e publikációt tekintik az els˝o mérföldk˝onek a genetikus algoritmusok történetében, melyben a genetikus algoritmus mint a biológiai evolúció absztrakciója került bemutatásra. Az evolúciós algoritmusok széles körben legkés˝obb elfogadásra került területe a genetikus programozás. Ez genetikus algoritmus egy olyan karakterisztikus alkalmazási területe, ahol adott feladatokat végrehajtó számítógépes programok (tipikusan LISP nyelven) kifejlesztése a cél. Az els˝o ilyen irányú módszer kifejlesztése Koza nevéhez f˝uz˝odik (Koza, 1989, 1992b) aki napjainkban is a genetikus programozás módszerének vezet˝o alakja. Napjainkban az evolúciós algoritmusok fajtái közti határok egyre inkább elmosódnak, mert a különböz˝o területek egymás módszertanát is felhasználva fejl˝odtek tovább. Például a mostani genetikus algoritmusnak nevezett evolúciós algoritmusok egészen más mechanizmusokat is használnak, mint az eredeti Holland féle kanonikus genetikus algoritmusok, bár az alap gondolat változatlan maradt.
32
Kezdeti populáció A kezdeti populáció feltöltése véletlenszer˝uen generált egyedekkel
Értékelés Az értékelési szempontok értékeinek kiszámítása
Reprodukció Új egyedek létrehozása rekombinációval és/vagy mutációval
Fitness számítás A fitness érték meghatározása a szempontok alapján
Szelekció A legfittebb egyedek kiválasztása szaporodásra
7. ábra. Az evolúciós algoritmusok általános sémája.
Az evolúciós algoritmusok általános sémája a 7. ábrán látható. A kezdeti populáció feltöltése véletlenszer˝uen generált egyedekkel (variánsokkal) történik olyan módon, hogy lehet˝oleg minél jobban lefedjék a keresési teret. Ezt követ˝oen ciklikusan ismétl˝odnek az értékelés, a fitness számítás, a szelekció és a reprodukció lépései. Az értékelés lényege az, hogy ki kell számítani az egy vagy több célfüggvény konkrét értékét. Ez az egyszer˝u mintapéldák esetében egy (az egyedek kódjának ismeretében) többé-kevésbé gyorsan végrehajtható algoritmus. A gazdasági, m˝uszaki és természettudományos alkalmazásoknál el˝oforduló optimalizálási és identifikálási feladatokban az egyedek célfüggvény értékének kiszámítása egy együttm˝uköd˝o másik programmal történik, aminek számítógépi er˝oforrás igénye általában több nagyságrenddel nagyobb. A populáción belül a célfüggvényérték(ek) ismeretében a változatokat a rangsoroló fitness értékek meghatározása az evolúciós algoritmus feladata. E fitness érték minden evolúciós ciklusban változhat. A szelekciós lépesben az el˝oz˝oek szerinti fitness érték alapján választjuk ki a szaporodásra javasolt egyedeket ill. nagy valószín˝uséggel töröljük a rosszabb fitness érték˝u egyedeket. A reprodukciós lépésben rekombinációval és/vagy mutációval új egyedeket hozunk létre és a populációt ennek megfelel˝oen módosítjuk. Ezt követi az új egyedek értékelésével egy új ciklus. A sz˝ukebb értelemben vett genetikus algoritmusok konfigurálásának és 33
7. Szelekció 8. nem Rekombináció 9.
1. Genetikus kódolás kidolgozása 2.
Mutáció 4.
Értékelési szempontok meghatározása 3.
Vége?
igen
stop
5. Értékelés Fitness képzés
Kezdeti populáció létrehozása 6.
Paraméterek beállítása
Visszahelyezés
8. ábra. A genetikus algoritmus folyamatábrája.
m˝uködésének egy lehetséges, részletesebb folyamat ábrája a a 8. ábrán látható. A genetikus algoritmusok tárgyalása során a – szakirodalomhoz hasonlóan – a biológiai evolúció fogalmi rendszeréb˝ol átvett kifejezéseket is használni fogom. Így az egyes megoldások egyedek, az egyedek teljes kódja kromoszóma, a kromoszómák eleme gének és a gének lehetséges értékei allél néven is el˝ofordulnak. A genetikus m˝uveletek közül a reprodukció és a keresztezés alatt ugyanazt az operátort értem4 . Természetesen az algoritmusoknál használt biológiai fogalmakkal lefedett mechanizmusok és struktúrák jóval egyszer˝ubbek, mint a biológiai megfelel˝oik. A genetikus algoritmus m˝uködtetéséhez el˝ozetesen ki kell dolgozni a genetikus kódolást, amely magában foglalja a lehet˝oségtér leírását. Egyidej˝uleg meg kell határozni az értékelési szempontokat is. Végül meg kell adni az algoritmus – lényegében heurisztikusan kiválasztandó – paramétereit is, például a populáció méretét, reprodukciós rátát vagy a mutációs rátát. Mindezek után már automatikusan létrehozható a kezdeti populáció (inicializálás). A genetikus ciklusban többféle m˝uködési sorrend valósítható meg. Az ábrán 4 Hagyományosan
a keresztezés fogalmát a bitsztringek reprodukciójára szokták használni.
34
bemutatott általános példánál a szelekciót a rekombináció és a mutáció követi, majd az új egyedek értékelése után döntünk, az új populációba kerül˝o egyedekr˝ol (visszahelyezés). A leállási kritériumok teljesülése esetén az algoritmus leáll, különben ciklikusan folytatódik. A genetikus algoritmus a 9. ábrán szemléltetett módon a genotípusos térben leírt lehet˝oségekb˝ol hozza létre a fenotípusokat, amelyek egy szuperstruktúra részeiként is elképzelhet˝ok, de jelen esetben mindig elkülönített egyedek formájában jelennek meg. Az egyedek értékelése után rajzolódik ki az értékelési tér, majd ebb˝ol származtatjuk a genetikus algoritmus fitness terét. A klasszikus vagy kanonikus genetikus algoritmusok kizárólag bitsztringekkel dolgoztak, de már évekkel ezel˝ott a folytonos kódolás és a nagyobb kardinalitású diszkrét halmazok elemeit alkalmazó diszkrét kódolás is általánossá vált (Radcliffe, 1992). Az ilyen kódolások mellet a genotípus és fenotípus terek megkülönböztetése már nem szükséges. A genetikus kódolásnál használt elemek (gének) els˝o közelítésben halmazok elemeiként értelmezett diszkrét értékek, vagy egy adott értelmezési tartományból választott folytonos értékek lehetnek. A folytonos változók kezelése mindig diszkrét intervallumokra bontással valósul meg (széls˝oséges esetben a számítógép lebeg˝opontos számábrázolásának felbontása). Speciális kezelést igényelnek azok a problémák, amelyeknél bizonyos el˝oírt jellemz˝ok teljes permutációja alkotja a lehet˝oségteret, vagy más „egzotikus” kódolást kell alkalmazni. A továbbiakban röviden áttekintjük a lényegesebb genetikus operátorokat. – A szelekciós operátor lényege az, hogy a fitness értékt˝ol függ˝oen kiválasztjuk az új egyedek létrehozásához szükséges szül˝o egyedeket. – A rekombináció feladata a szül˝o egyedek genetikus kódjának kombinálása. – A mutáció alkalmazása során egyetlen egyed véletlenszer˝u megváltoztatása történik meg. – A visszahelyezés során döntünk arról, hogy az új és a régi egyedek közül – fitness értékük alapján – melyek kerüljenek be az új populációba.
35
A továbbiakban részletesebben – de a teljesség igénye nélkül – ismertetem a genetikus operátorok legfontosabb fajtáit és tulajdonságaikat. A szelekció célja az, hogy a populációban található egyedek közül, fitness értékükt˝ol függ˝oen kerüljenek kiválasztásra az új utódokat létrehozó szül˝ok. A szelekciós eljárásokat többféleképpen csoportosíthatjuk. A determinisztikus szelekciónál egy megoldás lehet a csonkolásos szelekció, amely egyszer˝uen a populáció n legjobb elemének a kiválasztásán alapszik. A sztochasztikus szelekció során, ha a kiválasztási valószín˝uség az egyed fitness értékével arányos akkor fitness arányos szelekcióról beszélünk. Ilyen módon m˝uködik a klasszikus rulett kerék szelekció (Holland, 1975), és a hiányosságait javítani próbáló sztochasztikus univerzális mintavétel (Baker, 1987). A fitness arányos szelekciós mechanizmusok hátránya, hogy a kiugróan „jó” egyedek gyorsan el tudnak szaporodni a populációban csökkentve annak diverzitását, és növelve a lokális optimumba kerülés valószín˝oségét. Ennek kiküszöbölésére más sztochasztikus szelekciós operátorok is megjelentek. A versengéses szelekció (Wetzel, 1983) során az n elem˝u populációból m < n (általában m = 2) egyedet választunk egyenletes valószín˝uséggel, majd ezek közül a legjobb fitness érték˝ut (a verseny gy˝oztesét) preferáljuk. A rangsor alapú szelekció (Baker, 1985) szintén simítja az egyedek közti fitness különbségeket, mert a kiválasztás valószín˝usége nem a fitness értékét˝ol, hanem a fitness szerint rendezett populációban elfoglalt pozíciótól függ.
36
F 3,3 F 2,3 F 1,3 F 1,2
F 0,3 F 0,2
Fitness tér
F 3,2 F 2,2
F 3,1 F 2,1
F 1,1 F 0,1
F 3,0 F 2,0
F 1,0
f (x, y)
F 0,0
y
Értékelési tér
(3,3) (2,3)
x
(1,3)
(3,2)
(0,3)
Fenotípus tér
(2,2) (1,2)
(3,1)
(0,2)
(2,1) (1,1)
(3,0)
(0,1)
(2,0) (1,0) (0,0)
0101 0100
Genotípus tér
1101
0111 1100
0110
0000
1001
0011 0010
1111 1110
0001 1000
1011 1010
9. ábra. A genetikus algoritmus genotípus, fenotípus, értékelt (egyszempontú) fenotípus terének, valamint a fenotípus tér és fitness érték által kifeszített tér egymásra épülése. A fitness tér struktúrája a populáció összetételével összhangban folyamatosan változik.
A rekombinációs operátorok feladata a szül˝ok genetikai állományának kombinálása a létrejöv˝o utódokban. A genetikus algoritmusok módszertanában ez a legfontosabb operátor. A kombináció formája a genetikus kód típusától és a két szül˝o által kijelölt keresési térrész kezelését˝ol (sz˝ukítése, b˝ovítése) függ. A nagyon sokféle implementációs lehet˝oség közül nézzük a legtöbbször alkalmazott megoldásokat. A diszkrét rekombináció fajtáit a 10. ábrán tekinthetjük át. A keresztezések fontos tulajdonsága, hogy a két szül˝o genetikus állományából vagy az egyik vagy a másik szül˝o alléljait használja fel, tehát új értéket nem hoz be az utódok képzése során. A keresztezések különféle megoldásai a cserélend˝o gének vagy génszakaszok kijelölésében különböznek egymástól. A leggyakrabban használt 37
Sz 1 :
Sz 1 :
Sz 2 :
Sz 2 :
U1 :
U1 :
U2 :
U2 :
a) Egy pontos keresztezés.
b) Két pontos keresztezés.
Sz 1 :
Sz 1 :
Sz 2 :
Sz 2 :
U1 :
U1 :
U2 :
U2 :
c) Több pontos keresztezés.
d) Uniform keresztezés.
10. ábra. Néhány diszkrét keresztezés fajta. A különféle operátorok a két szül˝ob˝ol (Sz 1 , Sz 2 ) két utódot (U1 ,U2 ) állítanak el˝o.
megoldás az uniform keresztezés (Ackley, 1987), amely a kromoszóma hosszától függetlenül dolgozik, és minden génre 50%-os valószín˝uséggel választ allélt a két szül˝o megfelel˝o pozíciójáról. A folytonos rekombináció esetén az operátor nem csak a szül˝ok alléljait használhatja fel, hanem a gének értékeib˝ol új értéket is el˝oállíthat. Ezt az operátort f˝oleg a valós számok részhalmazán értelmezett (valós szám, egész szám) géntípusokra lehet alkalmazni. Az operátor által „letapogatható” régió szerint sokféle változat került kifejlesztésre. A leggyakrabban el˝oforduló változatok a 11. ábrán láthatók. A folytonos rekombinációs m˝uveletek másik fontos jellemz˝oje az, hogy a lehetséges keresési terület fölött, milyen valószín˝uségi eloszlást használva generáljuk az utódokat. A két leginkább elterjedt fajta az egyenletes és a normál eloszlás, de biztató eredményeket eredményeket értek még el Laplace eloszlást használva is (Deep and Thakur, 2007a). A rekombinációs operátorok harmadik jellemz˝o csoportját a teljes permutá38
x2
x 2(2)
x 2(2)
U1
x 2(1)
x 2(1) hI
Sz 2 Sz 1
x2
I Sz 1
x 1(1)
x 1(2)
x1
a) Diszkrét rekombináció. ,α ∈ {0, 1} u i = αx i(1) + (1 − α)x (2) i x 2(2)
Sz 2
x 1(1)
U2 x 1(2)
hI
x1
b) Lineáris rekombináció. u i = αx i(1) +(1−α)x (2) ,α ∈ [−h, 1+h], h > 0 i
x2
x 2(2)
x 2(1)
x2
x 2(1) Sz 1
Sz 1
Sz 2
x 1(1)
Sz 2
x 1(1) x 1(2)
x 1(2)
x1
c) Köztes rekombináció. u i = αi x (1) + (1 − αi )x (2) , αi ∈ [0, 1] i i
x 2(2)
d) Köztes kiterjesztett rekombináció. u i = αi x (1) + (1 − αi )x (2) , i i
α ∈ [−h, 1 + h], h > 0
x2
x 2(2)
x 2(1)
x1
x2
x 2(1) Sz 1
Sz 1
Sz 2
Sz 2
x 1(1)
x 1(1) x 1(2)
x1
e) Szül˝o centrikus rekombináció. u i = αi x (1) + (1 − αi )x i(2) , i
αi ∈ [ − h, h] ∪ [1 − h, 1 + h], h > 0
x 1(2)
x1
f) Aszimmetrikus szül˝o centrikus rekombináció. , αi ∈ [−h, h], h > 0 u i = αi x i(1) +(1−αi )x (2) i
11. ábra. A folytonos génen értelmezett rekombináció típusok. A két szül˝o (Sz 1 , Sz 2 ) környezetében típusuknak megfelel˝oen állíthatnak el˝o utódokat.
39
ciót leíró genetikus kódokon dolgozó operátorok alkotják. Mivel a megengedett utódok is csak teljes permutációt írhatnak le, ezért ehhez illeszked˝oen kell az operátorokat megtervezni. A többi rekombinációs operátorhoz hasonlóan nagyon sokféle változatot dolgoztak ki a permutációs problémák kezelésére. Talán legrégebbi típus a részlegesen megfeleltetett keresztezés (PMX, partially matched crossover) (Goldberg and Lingle, 1985). Ennél a keresztezés fajtánál a szül˝okb˝ol származó részek nagyrészt meg˝orzik pozícióikat az utódokban. Az átrendezéses keresztezés (OX, order crossover) (Davis, 1991) az abszolút pozíciók meg˝orzése helyett inkább az elemek relatív sorrendjét örökíti át az utódokba. A ciklikus keresztezés (CX, cycle crossover) nem használ keresztezési pontokat (Goldberg, 1989). Az él rekombináció (edge crossover) nem az elemek sorrendjével, hanem az elemeket összeköt˝o élek öröklésének el˝otérbe helyezésével generálja az utódokat. A PMX operátor m˝uködésének lépései a 12. ábrán követhet˝ok. Els˝o lépésben a kétpontos keresztezéshez hasonlóan véletlenszer˝uen kiválasztjuk a két szül˝o cserélend˝o génszakaszát majd végrehajtjuk a génszakaszok cseréjét. Az így kialakult utódok azonban nem teljes permutációt írnak le, ezért a keresztezés második szakaszában javítanunk kell o˝ ket. A javítás úgy történik, hogy megkeressük a kicserélt génszakaszokon kívüli részekben található duplikált allélokat, majd a kicserélt génszakaszok egymás alatti allélpárjainak megfelel˝oen ezeket is felcseréljük egymással az els˝o szakaszban kapott kromoszómákban. A permutációt kezel˝o keresztezési operátorokról elmondható, hogy vagy a hagyományos diszkrét keresztez˝o operátorok mechanizmusát használják fel, majd valamilyen javító algoritmussal teszik az utódot megengedetté, vagy valamilyen heurisztikát alkalmaznak. A gyakorlati életben a heurisztikus operátorok általában jobban teljesítenek. A mutációs operátorok egy kiválasztott egyed kisebb módosításával ennek az egyednek környezetében keresnek új megoldásokat. A rekombinációhoz hasonlóan a mutációs operátoroknak is sokféle fajtája alakult ki. A diszkrét génszakaszok mutációja során egy vagy több gént véletlenszer˝uen kiválasztva, az adott gén allélját véletlenszer˝uen egy másik lehetséges allélra cseréljük. A 13. ábrán a diszkrét mutáció alaptípusai láthatók.
40
Sz 1 : 2
1 10 4 3 9 6 5 8 7
Sz 2 : 3
2 4 1 10 8 7 9 6 5
Uˆ 1 : 2
1 10 4 10 8 7 5 8 7
Uˆ 2 : 3
2 4 1 3 9 6 9 6 5
U1 : 2
1 3 4 10 8 7 5 9 6
U2 : 10 2
4 1 3 9 6 8 7 5
a) PMX keresztezés.
E: 2
1 10 4 3 9 6 5 8 7
Eˆ : 2
1 10 5 10 8 7 4 8 7
b) Allél cserén alapuló mutáció.
12. ábra. Teljes permutációt megvalósító génszakaszok genetikus operátorainak egy lehetséges megvalósítása. E:
E:
Eˆ :
Eˆ :
a) gy gén mutálódik.
b) Több gén mutálódik.
13. ábra. Diszkrét génszakaszok mutációja.
A folytonos génszakaszok mutációja a folytonos rekombinációtól abban különbözik, hogy a keresési terület csak egy egyed környezetében helyezkedik el. Az egyenletest˝ol eltér˝o valószín˝uségi eloszlások alkalmazása a jellemz˝o. Az aktuális mutációs operátorok összefoglalása (Deep and Thakur, 2007b) cikkében található meg. Permutációt leíró génszakasz esetén a mutáció az elemek sorrendjét változtatja meg. Nagyon sok problémafügg˝o megoldás mellett a leggyakoribb m˝uveletek a beszúrás, a csere, az invertálás és a véletlen átrendezés. A csere illusztrációja a 12.b) . ábrán látható. A visszahelyezés m˝uvelete során a rekombináció, mutáció által létrehozott új egyedeket illesztjük be a populációba. Mivel a populáció mérete korlátos, ezért a régi és az új egyedek egyesített halmazából néhány egyedet törölnünk kell. A visszahelyezési stratégia kiválasztása attól függ, hogy milyen az újonnan 41
generált és a régi egyedek aránya, és a populáció mekkora részét szeretnénk új egyedekkel feltölteni. A visszahelyezés elvégzésekor sokszor a szelekcióhoz hasonló m˝uveleteket kell elvégezni de nemcsak a jó egyedek, hanem a rossz egyedek determinisztikus vagy véletlenszer˝u kiválasztásának a lehet˝oségét is meg kell teremteni. Nagyon gyakran csak néhány utódot (1-2 darabot) generálunk és azonnal visszahelyezzük a populációba (steady-state), vagy az utódokat a szüleikkel versenyeztetjük a populációba kerülésért. A genetikus algoritmusok hatékonysága adott kódolás és operátorok mellett is számos paramétert˝ol függ. A populáció mérete, a keresztezési és mutációs faktor, a mutációs eloszlások szórása mind-mind olyan paraméter, amely er˝osen befolyásolhatja az algoritmus konvergenciáját. A paraméterek helyes beállítására nincs, és talán nem is lehet általánosan elfogadott szabályrendszert kialakítani. A paramétereket rögzíthetjük az algoritmus futása el˝ott, de jobb eredmények érhet˝ok el a paraméterek értékeinek futás közbeni vezérléssel (determinisztikus beállítással) vagy szabályozással (adaptív paraméter ellen˝orzéssel) történ˝o megváltoztatásával. A legkifinomultabb módszer az önadaptív paraméter ellen˝orzés, amikor magát az evolúciós folyamatot használjuk a paraméter beállítására. Az algoritmus hatékonyságának másik fontos tényez˝oje az, hogy a populáció diverzitását a lehet˝o leghosszabb ideig meg˝orizzük. Ezt a csoportosítási technikák segítségével érhetjük el. A három legelterjedtebb technika közül az els˝o a fitness megosztáson alapuló eljárás. Ez a módszer az azonos csoportba tartozó egyedek fitness értékét a csoportba tartozó egyedek számával arányosan csökkenti. A tömörítési eljárás során a visszahelyezéskor mindig az egyedhez legjobban hasonlító variánsokat cseréljük le a populációban. A legegyszer˝ubb formája a determinisztikus tömörítés, amely végrehajtásakor a szül˝ok és az utódok versenyeznek a populációba kerülésért. A ritkítási technika a fitness megosztáshoz hasonlóan m˝uködik, de a csoporton belül a legrosszabb egyedek fitness értékét nullázza. Általánosan megállapítható, hogy a tömörítési technikák alkalmazhatók szélesebb körben, mivel ezek nem igényelnek többlet tudást a keresési tér struktúrájáról. A másik két módszer alkalmazásához meg kell becsülnünk a csoportok kiterjedését, ami sokszor nehéz feladat. Ha azonban jó becslést tudunk
42
adni, akkor a ritkítás kínálja a leghatékonyabb megoldást (Borgulya, 2004). A hatékonyság növelését az algoritmusok párhuzamosításával is támogathatjuk. A legegyszer˝ubb módszer a mester-szolga modell, ahol változatlan algoritmus kialakítás mellett, az értékelési függvények számítását végezhetjük párhuzamosan. Jelent˝os hatékonyság növekedést az el˝oz˝o modellel akkor lehet elérni, ha az értékelési függvény számítása jóval er˝oforrásigényesebb, mint a genetikus algoritmus. A gyakorlati feladatok jelent˝os részénél ez a feltétel áll fenn. A párhuzamos genetikus algoritmusok fajtáit és gyakorlati megvalósításuk lehet˝oségeit (Van Veldhuizen et al., 2002) publikációjában követhetjük. Az algoritmus hatékonysága minden probléma specifikus tudás bevitelével tovább növelhet˝o. A szakért˝o által javasolt kezdeti megoldások, feladat specifikus operátorok alkalmazása gyorsabb konvergenciát eredményezhet. Ha rendelkezésünkre áll a feladathoz használható valamilyen lokális keresési eljárás, akkor azt érdemes ötvözni a genetikus algoritmussal. Ezek a hibrid megoldások nagyobb hatékonysággal oldják meg az adott problémát.
1.3.2. A többszempontú genetikus algoritmusok Az evolúciós algoritmusok többszempontú optimalizálási problémákra való alkalmazásának ötlete már az 1960-as években felmerült, de a mai értelemben vett többszempontú genetikus algoritmus megvalósítása a Schaffer által publikált (Schaffer, 1984) vektor értékelést alkalmazó genetikus algoritmushoz (Vector Evaluating Genetic Algorithm, VEGA) köthet˝o 1984-ben . A többszempontú evolúciós algoritmusok kutatása 1990-es évek közepe után indult meg igazán. Az evolúciós algoritmusokat (EA) az teszi igazán ígéretessé a többszempontú optimalizálási problémák megoldásában, hogy populációt használó módszerként szimultán több megoldással dolgoznak. Ezért az algoritmus egy futtatása során képesek lehetnek a Pareto optimális megoldások halmazának több elemét felderíteni, ellentétben a több egymás utáni futtatást igényl˝o tradicionális matematikai programozási módszerrel (Ceollo Coello, 1999a). Ráadásul az evolúciós algoritmusok robusztussága érzéketlenné teszi o˝ ket a Pareto front (konvex vagy konkáv) alakjára, folytonos vagy szakadozott voltára, ami a hagyományos módszereknek komoly gondokat szokott okozni. 43
Mint láttuk a többszempontú optimalizálási problémák egyik kezelésmódja a szempontok a priori aggregálása. Ebben az esetben az egyszempontú genetikus algoritmusok szinte módosítás nélkül alkalmazhatók a problémák megoldására, az a priori módszerek minden el˝onyével és hátrányával együtt. A másik lehet˝oség az a posteriori kezelésmód, amely a Pareto front generálásával oldja meg a problémát. Itt is alkalmazható a szempontok aggregálása, ilyenkor az algoritmus futása során vagy az algoritmust többször újraindítva és valamilyen stratégia szerint az aggregálás paramétereit változtatva állíthatunk el˝o Pareto optimális megoldásokat. Napjainkban a legtöbb genetikus algoritmus Pareto dominancia bázisú rangsorolást alkalmaz. Az x 1 ∈ X egyedet akkor nevezünk dominánsak az x 2 ∈ X egyedhez képest (x 1 Â x 2 ), ha minden i = 1, . . . , k esetén f i (x 1 ) ≤ f i (x 2 ) valamint létezik legalább egy j index melyre f j (x 1 ) < f j (x 2 ). A két egyed összehasonlítása során a dominancia reláció háromféle értékkel térhet vissza: x 1 Â x 2 , x 1 ≺ x 2 , x 1 x 2 ∧ x 1 ⊀ x 2 , azaz a dominancia reláció nem ad teljes rendezést X elemeire. A Pareto dominancia szemléltetése a 14. ábrán látható. Mivel az értékelési függvények száma változik, a fitness érték számítását ehhez kell igazítani. Ez „csak” a 8. ábrán az 5. pontnál történ˝o értékelés→ fitness képzés átmenet módosítását jelenti, ami azonban jelent˝osen befolyásolja az algoritmus viselkedését. A dominancia vizsgálata mindig csak két egyed között lehetséges, ezért ezt a populáció minden elempárjára el kell végezni. Ez természetesen növeli az algoritmus komplexitását. Az összehasonlítások eredményéb˝ol többféle módszer szerint képezhetjük a fitness értéket. Az egyik módszer a dominancia rangsor alapján számolja a fitness értéket, azaz azt vizsgáljuk, hogy hány darab egyedet dominált a szóban forgó egyed (Fonseca and Fleming, 1993). A másik lehet˝oség a dominancia számosság elemzése, amikor a domináló egyedek száma lesz a fitness érték. A harmadik, legösszetettebb módszer, a dominancia mélység vizsgálata során (Deb et al., 2000) meghatározzuk a nem dominált egyedeket ( a második módszer szerint), ezekhez azonos fitness értéket rendelünk, majd kivonjuk o˝ ket a vizsgálat hatóköréb˝ol. Ezután az el˝oz˝o lépést a fitness érték növelésével addig ismételjük, amíg az egyedek el nem fogynak. Léteznek az el˝oz˝o eljárások kombinációjával operáló módszerek, amelyek még
44
f1
"rosszabbak"
"indifferensek" E
H B "jobbak"
G D
"indifferensek" f2
14. ábra. A Pareto dominancia szemléltetése. A G megoldás dominálja a H megoldást, viszont a B megoldás dominálja a G-t. A G és E valamint a G és D megoldások egyenérték˝uek.
összetettebb módon számolják a fitness értéket (Zitzler et al., 2001b). A fitness érték képzés során a f˝o szempont az, hogy a szelekciós nyomás a Pareto front felé terelje a megoldásokat. A másik elvárás az, hogy a megoldások a Pareto front mentén lehet˝oleg egyenletesen oszoljanak el, ami a Pareto front egészér˝ol jó közelítést szolgáltat. Ennek a célnak a teljesítése érdekében a fitness érték mellett az egyedekhez (az értékelési térben számolt) zsúfoltsági paramétert rendelünk. Ez a paraméter az azonos fitness érték˝u egyedek közötti másodlagos rendezést végzi el az egyedek értékelés térbeli zsúfoltságának függvényében. Több módszer használatos, amelyekr˝ol részletesebben a (Deb et al., 2000; Zitzler et al., 2001a; Knowles and Corne, 2003) szakirodalmakban tájékozódhatunk. A feltételek, prioritások és célok egységes kezelésének formalizálása (Fonseca and Fleming, 1998a) a többszempontú evolúciós algoritmusok módszertanának fontos állomása volt. Az értékelési függvényekhez prioritási szinteket és elérend˝o célokat rendelhetünk, amelyeket a Pareto dominancia számításba 45
3. táblázat. A genetikus algoritmus gyakorlati alkalmazásai a szakirodalomban. Alkalmazási területek
Hivatkozások
Gazdasági Villamos mérnöki, áramkör tervezés Vegyészmérnöki
Yuret and Maza (1994) Lohn and Colombano (1999); Lohn et al. (2000) da Cunha and Covas (2002); Xiao and Williams (1994); Meza and Martinez (1994) Cagnoni et al. (1999); Smigrodzki et al. (2005) El-Fakihy et al. (1999); Sharples (2001) Cordón et al. (1998); Kamrani et al. (2001) Levine (1996); Cleveland and Smith (1989); Beaty (1992); Cardon et al. (1999a) Chai and Ma (1998a); Kundu et al. (2002)
Orvosi Telekommunikáció Adat bányászat, adat elemzés Különféle ütemezések Fizika, geometria
integrálva használhatunk fel. Gyakran alkalmazott módszer, hogy a feltételek kezelése egy nagy prioritású értékelési függvényként valósul meg. Ezek a függvények (maximális feltételsértések) a feltételek teljesülése estén nulla értékkel, ellenkez˝o esetben a maximális feltételsértés mértékével térnek vissza. A feltételek hatékony kezelésének kérdése jelenleg is intenzíven kutatott terület a genetikus és evolúciós algoritmusok vonatkozásában. A módszerek sokféleségét és fejl˝odését (Coello Coello, 2002) publikációja részletesebben ismerteti. A genetikus algoritmusok sokrét˝u felhasználását alkalmazási területenként a 3. táblázat tartalmazza.
46
2. FEJEZET ALKALMAZOTT MÓDSZEREK
A kutatási téma jellegéb˝ol adódóan szoftverfejleszt˝o munkámhoz számos, a fejlesztést támogató nyílt forráskódú szoftvert, illetve a kutatócsoport által kifejlesztett szimulációs társprogramokat alkalmaztam. A makrogranulárisan párhuzamos evolúciós fejlesztés megvalósítására egy számítógép klasztert építettem és konfiguráltam. Ennek megfelel˝oen az értekezésben kidolgozott genetikus algoritmus elkészítéséhez és kipróbálásához felhasznált módszerek a következ˝ok voltak: – a feladatokat megoldó genetikus algoritmust megvalósító számítógépi programok készítéséhez felhasznált szoftver eszközök, – a genetikus algoritmussal együttm˝uköd˝o generikus szimulátor, valamint – a makrogranulárisan párhuzamos m˝uködés megvalósítására kidolgozott hardver és az ezt támogató szoftver. Az evolúciós keretrendszer kialakításához felhasznált legfontosabb nyílt forráskódú szoftverek a következ˝ok voltak: – fox toolkit: (http://www.fox-toolkit.org); – plplot: (http://www.plplot.org); – tclap: (http://tclap.sourceforge.net/); – c++ fordítók: gcc mingw32. A genetikus algoritmus grafikus interfészét a 15. ábrán mutatom be.
48
15. ábra. A genetikus algoritmus grafikus interfésze
Az evolúciós keretrendszer hatékonyságának növelésére alkalmazott makrogranuláris párhuzamosítás megvalósítására egy 16 PC alkatrészb˝ol épített számítógép klasztert építettem. A klaszter m˝uködtetését a nyílt forráskódú OpenSSI (http://www.openssi.org) szoftver adaptációjával oldottam meg. A dolgozatban bemutatott illusztráló példák közül – az egyszer˝u tesztfeladatok programját magam készítettem el; – a további illusztráló példák szimulációjára pedig a folyamatok közvetlen számítógépi leképezésen alapuló szimulációjára a folyamatinformatikai kutatási iskolában kidolgozott (Csukás, 2001) programrendszer WINDOWS® operációs rendszer alatt, Excel® interfésszel futtatható változatát használtam. Az elmúlt másfél évtizedben folyamatosan fejlesztett genetikus algoritmus segítségével megoldott ipari feladatokban és kísérleti esettanulmányokban szerepl˝o identifikálási, optimális irányítási, optimális tervezési, illetve optimális ütemezési problémák vizsgálatánál szimulációs programként ugyancsak a közvetlen számítógépi leképezésen alapuló generikus folyamat szimulátor különféle adaptációit alkalmaztam. (Csukás, 2001)
49
3. FEJEZET EREDMÉNYEK
3.1. A genetikus algoritmus implementációja és továbbfejlesztése A gyakorlati életben a komplex rendszerek gazdasági optimalizálására is használható módszereknek sok feltételt kell kielégíteniük. A két legfontosabb általános elvárás közül az els˝o a többszempontú értékelhet˝oség biztosítása a döntési folyamat támogatása érdekében. A másik elvárás az, hogy a módszer képes legyen komplex (gazdasági és/vagy m˝uszaki) rendszerek döntési terének szükséges mérték˝u kezelésére. Ha a fejlesztend˝o genetikus algoritmus szempontjából nézzük az elvárásokat akkor az algoritmus kialakításakor a következ˝o feltételeket kellett teljesíteni. – Biztosítani kell a többszempontú értékelés lehet˝oségét a döntéshozó preferenciáinak figyelembevételével. Olyan genetikus kódolást kell alkalmazni, amely – lehet˝oleg módosítás nélkül – lehet˝ové teszi az összetett rendszerek modellezésénél és szimulációjánál használt struktúrák minél szélesebb kör˝u kódolását. – Mivel az egyedek kiértékelése dönt˝o többségben egy sok er˝oforrást és id˝ot igényl˝o (nagy költség˝u) dinamikus szimulációt jelent, a komplex rendszerek optimalizálásának lényeges jellemz˝oje a kiértékelhet˝o variánsok meglehet˝osen korlátozott száma. Ez a probléma az algoritmus párhuzamosításával és új er˝oforrások (számítási egységek) bevonásával kezelhet˝o. Ugyanakkor ez a korlát azt is kikényszeríti, hogy meglehet˝osen kis méret˝u populációt kell használunk és kerülni kell a már egyszer kiértékelt egyedeknek ismételt értékelését. – A kis populációt használó algoritmusok végrehajtása során lényeges szerepe van a megfelel˝o inicializálásnak és nagyobb a valószín˝usége a korai konvergencia bekövetkezésének (a lokális optimum csapdájába kerülésnek). Ehhez populáció diverzitását meg˝orz˝o eljárások intenzív használatára van szükség. A többszempontú globális optimalizálásra alkalmas genetikus algoritmust az el˝oz˝okben megfogalmazottak szerint próbáltam megvalósítani. A továbbiakban 51
Tulajdonság osztályok:
T6
T7
T8
T3
T4
T5
T0
T1
T2
A tulajdonság osztályok elemei: t 6,2 t 6,1 t 6,0
t 7,4 t 7,3 t 7,2 t 7,1 t 7,0
t 8,5 t 8,4 t 8,3 t 8,2 t 8,1 t 8,0
t 3,3 t 3,2 t 3,1 t 3,0
t 4,7 t 4,6 t 4,5 t 4,4 t 4,3 t 4,2 t 4,1 t 4,0
t 5,3 t 5,2 t 5,1 t 5,0
t 0,5 t 0,4 t 0,3 t 0,2 t 0,1 t 0,0
t 1,2 t 1,1 t 1,0
t 2,4 t 2,3 t 2,2 t 2,1 t 2,0
Két teljes kombináció: t 6,1
t 7,3
t 8,4
t 6,1
t 7,1
t 8,1
t 3,2
t 4,6
t 5,2
t 3,1
t 4,1
t 5,1
t 0,4
t 1,1
t 2,3
t 0,1
t 1,1
t 2,1
16. ábra. Az összetett rendszerek tulajdonság hálókkal történ˝ o leírása. Az inkompatibili© ª tási relációk például az I = (t 0,1 , t 3,2 ), (t 2,0 , t 5,3 ), (t 8,0 , t 7,4 ) alakban adhatók meg, ahol t i , j az i . tulajdonság osztály j. eleme.
bemutatom a kidolgozott genetikus kódolást, az ennek megfelel˝o genetikus operátorokat, a diverzitás meg˝orzésére és a hatékonyság növelésére szolgáló eljárást, a használt többszempontú értékelést és a feltételek kezelését, valamint néhány implementációs sajátosságot.
3.1.1. Az összetett genetikus kódolás kidolgozása Az összetett rendszerek szerkezethálókkal való leírásában meghatározó jelent˝oség˝u volt Blickle munkássága (Blickle, 1977). A leírás lényege az, hogy a valamilyen célból létrehozható összetett rendszerek összessége, tulajdonság ekvivalencia osztályokat alkotó tulajdonság halmazokkal jellemezhet˝o. Az egyes tulajdonság osztályoknak az elemei az objektumot jellemz˝o tulajdonságok. Az osztályokat és a tulajdonságokat úgy kell létrehozni, hogy ha minden tulajdonság osztályból kiválasztunk egy és csak egy tulajdonságot (elemet), akkor ezzel egy konkrét rendszert határozunk meg. Sokszor el˝ofordul, hogy nem minden tulajdonság (elem) párt engedhetünk meg a kombinációk során. Ezeket 52
A genetikus kódolás:
G0
G1
G2
G3
G4
G5
G6
G7
G8
A lehetséges allélek:
0,5 gg0,4 0,3 gg0,2 0,1 gg0,0
g 2,4 2,3 gg2,2 2,1 gg2,0
g 1,2 1,1 gg1,0
3,3 gg3,2 3,1 gg3,0
4,7 gg4,6 4,5 gg4,4 4,3 gg4,2 g 4,1 g 4,0
5,3 gg5,2 5,1 gg5,0
g 7,4 7,3 gg7,2 7,1 gg7,0
g 6,2 6,1 gg6,0
8,5 gg8,4 8,3 gg8,2 8,1 gg8,0
Két egyed kromoszómái: g 0,1
g 1,1
g 2,1
g 3,1
g 4,1
g 5,1
g 6,1
g 7,1
g 8,1
g 0,4
g 1,1
g 2,3
g 3,2
g 4,6
g 5,2
g 6,1
g 7,3
g 8,4
17. ábra. Az összetett rendszerek tulajdonság háló alapú genetikus kódolása. A g i , j © ª alléllal inkompatibilis allélok az I i , j = g l ,m , g k,n alakban adhatók meg, ahol g i , j az i . gén j. allélja.
a kivételeket, un. inkompatibilitási relációkat megadva és figyelembe véve a tulajdonság osztályokkal leírt minden egyes megengedett rendszert generálni tudjuk. A fentiek szemléltetése a 16. ábrán látható. A genetikus kódolásnál a genetikus kódot a tulajdonság osztályok összességének tekintem. A kromoszóma egyes génjeinek egy-egy tulajdonság osztály felel meg. A gén pozíciója a hozzá tartozó tulajdonság osztály indexe. A gének lehetséges alléljai (értékei) az osztály tulajdonságainak (elemeinek) felelnek meg. Minden egyes allélhoz hozzárendelhetem a vele inkompatibilis allélok listáját. Az így megadott genetikus kódolás elemei a 17. számú ábrán láthatók. A genetikus algoritmusok bemutatásakor láthattuk, hogy az algoritmusok alkalmasak a diszkrét vagy folytonos jellemz˝ok, valamint a teljes permutációk kódolására és kezelésére. Az összetett rendszerek leírása során azonban a gének (tulajdonság osztályok) egyaránt lehetnek diszkrét (pl. a berendezések típusa), folytonos (pl. gazdasági/m˝uszaki paraméterek) és permutált diszkrét érték˝uek 53
(pl. gyártás sorrendek). Az ilyen rendszerek leírására tehát egyidej˝uleg kell használnunk a különböz˝o típusú géneket. A számítógép lebeg˝opontos számábrázolása végs˝o soron a folytonos jellemz˝oket is diszkrét értékekké transzformálja, ráadásul a gyakorlati életben el˝oforduló folytonos paramétereknek is van egy bizonyos pontossága. A genetikus kódolás során tehát minden géntípus valójában csak diszkrét vagy diszkretizált értékekkel rendelkezhet. Az igazi különbség az, hogy a genetikus operátorok alkalmazása során a géntípus alléljainak halmazán vagy az euklideszi, vagy csak a Hamming metrika értelmezhet˝o. Az els˝o esetben továbbra is a folytonos, a második esetben pedig a diszkrét megnevezéseket használom. A következ˝o lépés a különböz˝o géntípusok lehetséges alléljainak megadása. A diszkrét gének esetén ezt felsorolással vagy generálással oldom meg, míg a folytonos jellemz˝ok esetén legalább az értelmezési tartomány határok és a pontosság megadása szükséges, de ezt még kiegészítettem egy bels˝o, elvárt intervallum határai magadásának lehet˝oségével is. A kifejlesztett genetikus kódolás során az i . diszkrét géntípus elemeit a D i = © ª (g i ,1 , I i ,1 , K i ,1 ), (g i ,2 , I i ,2 , K i ,1 ), . . . , (g i ,n , I i ,n , K i ,n ) triplettekkel írom le, ahol g i , j ∈ N ami az esetek nagy részében az értékelési szempontokat számoló algoritmus (szimuláció) „katalógusában” megtalálható elem sorszáma. Az © ª I i , j = g l ,m , . . . , g k,v az inkompatibilis allélok halmaza és K i , j a kés˝obb leírt kromoszóma géntípus, ami a „katalógus” elem további jellemz˝oit (pl.: berendezés paramétereit, cserélhet˝o részeit) tartalmazhatja. A folytonos géntípus ¡ ¢ elemeinek leírását a C i = l i , hi , e il , e ih , dimax , dimi n hatosokkal adom meg, ahol l i , h i az értelmezési tartomány alsó és fels˝o határa, az e il , e ih az elvárt intervallum határai, a dimax , d imi n pedig az intervallumon értelmezett maximális és minimális felbontás. Ezt a két géntípust további három összetett géntípussal egészítettem ki. Ezek rendre a diszkrét génszakasz, a permutálható génszakasz és a kromoszóma. A génszakaszok a nevüknek megfelel˝oen diszkrét vagy diszkrét permutálandó gének sorozatai, míg a kromoszóma elemei az összes eddigi egyszer˝u vagy összetett gének közül kerülhetnek ki. Az összetett gének bevezetését egyrészt az indokolta, hogy bár az egyszer˝u kódolásoknál az inicializálás, a rekombináció és
54
Kromoszóma:
D0
C1
GP 2
GD 3
K4
D5
Allélek:
18. ábra. A kialakított egyszer˝u és összetett gének.
a mutáció alkalmazása elvégezhet˝o az egyes gén szintjén, a teljes permutációk kezelése csak a permutálandó génszakasz ismeretében végezhet˝o el. Másrészt az öszetett géneket rekurzívan egymásba ágyazva hierarchikus adatszerkezetek is kialakíthatók. A megoldás a kés˝obb bemutatandó hatékonyság növel˝o módszerhez is illeszkedik. Az így kialakított genetikus alapelemek szemléltése a 18. ábrán látható. A genetikus kódolás kib˝ovítése szükségessé teszi az algoritmus elemeinek e kódoláshoz való igazítását is. A kódon közvetlenül dolgozó algoritmus elemek az inicializálás, a genetikus operátorok közül pedig a rekombináció és a mutáció. Ezek a tevékenységek minden géntípus esetében definiálva vannak a típus tulajdonságainak megfelel˝oen. Tehát a folytonos, permutált, és diszkrét típusok a nekik megfelel˝o, szakirodalomban fellelhet˝o rekombinációs és mutációs operátorokat is használhatják, míg az inicializálás legtöbbször véletlen generálással történik. Egy adott feladat megoldáskor a genetikus kódolást az el˝oz˝oleg definiált géntípusok felhasználásával írjuk le. Az allélok létrehozása után a diszkrét génekre értelmezett inkompatibilitási relációkat is megadjuk. Minden egyes géntípusnak van egy alapértelmezett inicializálás, rekombináció és mutáció
55
készlete, de a több beépített változat közül bármelyikre kicserélhetjük o˝ ket.
3.1.2. A rácsmódszer kidolgozása A kis populáció méret használatának szükségessége több megoldandó probléma forrása. Az egyik az, hogy a megoldás nagyon érzékeny a kezdeti populáció „min˝oségére”, a másik az, hogy a populáció diverzitása gyorsan lecsökkenhet. Az egyenletes eloszlást generáló véletlenszám generátorok csak nagy populáció méretnél produkálnak igazán egyenletes eloszlást, emiatt a kis populációkat használva a keresési tér egyes részeibe jóval s˝ur˝ubben, máshova ritkábban generálunk egyedeket. A generálást irányíthatjuk a folytonos géntípusok esetében, ha a generáláshoz egyrészt szakért˝ok által becsült e il , e ih elvárt határokat használjuk fel, másrészt a gén maximális felbontását (d imax ) az inicializálás során a populáció méretnek megfelel˝o értékre állítva, a véletlenszám generátor által szolgáltatott értékeket erre a pontosságra kerekítve használjuk fel. A keresési térben létrejöv˝o rács segíti az egyedek egyenletesebb eloszlását. A módszer illusztrálása a 19. ábrán látható. A rács felhasználásának másik területe a létrejöv˝o azonos egyedek kisz˝urése. A rácsmódszer használata nélkül két egyed kódjának egyenl˝osége a lebeg˝opontos számábrázolás miatt csak nagyon ritka esetekben teljesülne, használatával viszont szabályozni tudjuk a variáns és a környezetében lév˝o variánsok minimális távolságát. Az el˝oz˝o fejezetben leírt összetett genetikus kódolást felhasználva a gyakorlati feladatok keresési tere a genetikus algoritmus számára felhasználható módon írható le. Ugyanakkor az egyszer˝u kódolásokhoz képest – ahol a kromoszóma sztringszer˝u és homogén – hátrány, hogy két egyed hasonlósági mértékének kiszámítása nehéz feladat. A folytonos és diszkrét génszakaszok és a hierarchikus géntípusok együttesére nem sikerült konzisztens hasonlósági mértéket kreálni a Hamming és euklideszi távolságok felhasználásával. Ez megakadályozza, hogy a populáció sokszín˝uségét meg˝orz˝o módszerek mindegyikét korlátozás nélkül felhasználjuk. A rácsmódszer alkalmazása viszont ötletet adott a diverzitás meg˝orzésének egy további megoldására. Ugyanis, ha az új egyedek is mindig a rácspontokba kerülnek akkor rács változtatásával dinamikusan 56
x2
x2
x1
a) Kezdeti populáció generálása rácsmódszer nélkül.
x1
b) Kezdeti populáció generálása rácsmódszerrel.
19. ábra. Az inicializálás módosítása a rácsmódszert felhasználva.
befolyásolni lehet a populáció diverzitását, azaz a felfedezés (exploration) és a kiaknázás (exploitation) egyensúlyát. Ehhez azonban módosítani kell az új egyedek el˝oállításában részt vev˝o rekombinációs és mutációs operátorokat. Folytonos génekre az operátorok módosítása hasonlóképpen történik mint az inicializálás esetében, vagyis a „hagyományos” operátorok által szolgáltatott új értékeket a legközelebbi rácspontok értékéhez „kerekítem”. Diszkrét génszakaszok esetén a rácsmódszer egyszer˝usített változatát valósítottam meg. A génszakaszhoz rendeltem egy, a génszakasz hosszának felénél kisebb egész számot, amely a keresztezés és a mutáció során a szül˝ok génszakasza és az új utód génszakasza közti elvárt minimális Hamming távolság kívánt mértékét írja le, hasonlóan a folytonos gének pontosságához. Itt sem módosítom az operátorok algoritmusát, hanem a két génszakasz Hamming távolságát összehasonlítva az elvárt értékkel, ismételten alkalmazom azokat, és ezt addig ismétlem, amíg sikerül a megfelel˝o egyedet létrehozni, vagy az ismétlések száma elér egy korlátértéket. Ez a korlátérték a génszakasz hosszának függvényében kerül megállapításra, alapértelmezett értéke a génszakasz hosszának fele. A genetikus operátorok kiegészítése a fenti tulajdonságokkal változatlanul hagyja az operátorok eredeti algoritmusát, és csak a végrehajtásuk után módosítja az eredményüket. Így széls˝oséges esetben a pontosságot és az elvárt minimális
57
távolságot zéró értékre állítva az operátorok a hagyományos módon viselkednek. Ha azonban a rács felbontása kezdetben durvább, majd a generációs lépések el˝orehaladtával egyre finomítjuk, akkor elkerülhetjük a korai konvergencia kialakulását. Kritikus elem a rács felbontás változásának ütemezése. Egyszempontú értékelés esetén használtam az adaptív ütemezést, amely az aktuális legjobb érték változásának függvényében növelte a felbontást, azonban többszempontú értékelés esetében csak determinisztikus ütemezést lehetett alkalmazni. A tapasztalat szerint jó és biztonságos ütemezési stratégiának mutatkoztak azok az esetek, amikor exponenciális csökkentés mellett a természetes pontosságot a tervezett generációs lépések nagyjából 75%-ánál elértük.
3.1.3. A többszempontúság kezelése A többszempontú döntések támogatásának lehet˝osége szintén fontos elvárás az algoritmus kidolgozása során. Figyelembe próbáltam venni, hogy a döntéshozó preferenciáinak illesztésére lehet˝oleg az a priori, az interaktív és az a posteriori módon is lehet˝osége maradjon. Az értékelési szempontok megadásakor lehet˝oség van a szempontok néhány tulajdonságának megadására. A tulajdonságok közül az els˝o a szempont prioritása, a második és a harmadik az elérend˝o cél értékének alsó és a fels˝o korlátja. E három tulajdonság segítségével tudja a döntéshozó a Pareto front preferenciáinak megfelel˝o régiói felé terelni az optimalizációs folyamatot. A feltételek, prioritások és célok egységes kezelhet˝oségének lehet˝osége és rugalmassága következtében, a módosított Pareto dominancia alapján rangsorolt fitness képzés vált be leginkább a többszempontú genetikus algoritmus használatánál. A rangsorolás használható mind egyszempontú mind többszempontú értékelés esetén, megtartva a feltételek kezelésének lehet˝oségét. A fitness képzés során többféle stratégia között választhatunk. Fitness értékként használhatjuk a szakirodalomban fellelhet˝o módszerek többségét. Így például a dominált egyedek számát, az egyedet domináló egyedek számát vagy az egyed Pareto frontjának mélységét. A dominancia kiszámításának sorrendjénél el˝oször a megadott feltételeket vesszük sorra. A feltételek csoportján belül különböz˝o prioritásokat adhatunk meg a különféle mértékeknek, így akár együtt használhatjuk 58
P1
Pl. feltétel sértések száma dominál?
1. Feltételek prioritás szerint (pl. eltérések maximuma, száma, összege, stb. . . )
Pl. feltétel sértések normalizált összege dominál?
igen
dominált
igen
nem dominált
dominál? nem 2. Az értékelési szempontok célteljesítése
dominált
igen
P2
P1 P 1 prioritású szempontok
igen
dominál? nem 3. Az értékelési szempontok értéke prioritás szerint
dominál?
dominál?
igen
dominál? nem
igen
Pi P i prioritású szempontok (i ∈ {2, . . . , m})
dominált
igen
nem dominált
nem dominált
20. ábra. Az összetett Pareto dominancia számításának folyamata.
59
például a feltételsértések számát (ami azt fejezi ki, hogy hány darab feltételt sért meg az adott egyed) és esetleg egy következ˝o szinten az összesített vagy maximális feltétel sértések mértékét (milyen messze vagyunk a megengedett tartománytól). Az értékelési szempontok is prioritásuk sorrendjében következnek. Az azonos prioritású csoportba tartozó szempontok el˝obb a célok teljesítése szerint lesznek összehasonlítva (a célokat teljesít˝ok jobbak a célokat nem teljesít˝oknél). A célokat azonosan teljesít˝o csoportba tartozók pedig az értékük szerint lesznek összehasonlítva. A 20. ábrán a számítás folyamatát követhetjük figyelemmel. A Pareto front „jó” becslésének szükséges feltétele, hogy az algoritmus által javasolt megoldások lehet˝oleg egyenletes eloszlásban közelítsék a frontot. Ezért a fitness érték mellett az egyedekhez rendelhetünk egy az értékelési térben értelmezett zsúfoltsági paramétert. Itt is többféle módszer között választhatunk (Deb et al., 2000; Zitzler et al., 2001a; Knowles and Corne, 2003), munkámban legtöbbször a k darab legközelebbi szomszéd távolságának szorzatát használtam a zsúfoltsági paraméter becslésére ahol k az értékelési szempontok száma (Kukkonen and Deb, 2006). Az alkalmazott szelekciós algoritmusok az azonos fitness érték˝u egyedek összehasonlításakor ezt a másodlagos értéket használják fel a szül˝ok kiválasztása és a visszahelyezés során, hogy biztosítsák a Pareto front egyenletes eloszlású közelítését. A kis populáció méretb˝ol adódóan az egy futás során az utolsó populációban el˝oállított nem dominált megoldások száma is kicsi. Ebb˝ol adódóan nagyon ajánlott egy küls˝o archívumban meg˝orizni az algoritmus futása során bármikor el˝oállított ismert Pareto optimális megoldásokat. Az archívum méretét szabadon beállíthatjuk. Az archívum maximális méretének elérése után a meg˝orzött optimális egyedeket a zsúfoltsági paramétert felhasználva ritkítjuk.
3.1.4. Az implementációs sajátságok Az egyedek er˝oforrásigényes értékelési függvényeinek kiszámítása sokszor csak néhány ezer, maximum néhány tízezer egyed kiszámítását teszi lehet˝ové. Az ilyen mennyiség˝u genetikus kód gyors elérés˝u eltárolása a mai modern 60
számítógép konfigurációkon, még nem szokott túl nagy lassulást okozni az algoritmus végrehajtásában. Ezért lehet˝oséget teremtettem az algoritmus futása során kiértékelt összes egyed tárolására. Ennek a tárnak a szerepe hasonló a 20. oldalon bemutatott tabu listáéhoz. Segítségével megakadályozhatjuk, hogy egy már kiértékelt egyedet újra az er˝oforrás igényes kiértékelésnek vessük alá. Az új egyedek el˝oállításáért felel˝os részek (inicializálás, rekombináció és mutáció) az új egyed el˝oállítása után megvizsgálják, hogy a kapott új genetikus kód szerepel-e a kiértékelt egyedek között. Ha már értékeltük ezt kódot, akkor újra próbálkoznak addig, amíg új értékeletlen kódot nem állítanak el˝o. Az ismételt próbálkozások számát korlátozzuk (alapértéke az genetikus kódban található egyszer˝u gének számának fele) és túllépése esetén a normál rekombináció és a normál mutáció helyett extra mutációt alkalmazva keresünk új kódokat. Ez az extra mutáció minden génre 50%-os valószín˝uséggel a gén típusának megfelel˝o módon hajtódik végre. A feltételek vagy megkötések kezelése két szinten van jelen a módszerben. Az els˝o szint a diszkrét géntípusokra megadható inkompatibilitási relációk figyelembevételével az inicializálás, a rekombináció és a mutáció szintjén értelmezhet˝o és a tiltott kombinációkat illet˝oen a tabu lista kezelésénél leírt módszer szerint járunk el. A második szinten a kiterjesztett Pareto dominancia számításánál vesszük figyelembe a feltételeket, illetve a megkötéseket. A kidolgozott genetikus kódolás jól illeszkedik az objektum orientált programozás paradigmájához. A program objektum orientált tervezése és implementálása lehet˝ové tette, hogy a program szinte minden összetev˝ojét akár a futás közben is kicserélhessük. Ez a tulajdonsága igen nagy segítséget ad az algoritmus gyakorlati problémákhoz történ˝o adaptálásához és az operátorok, fitness képzések, illetve zsúfoltsági paraméterek teszteléséhez. Az objektum hierarchia legfels˝o szintjén álló feladat osztály felel˝os az értékelési függvény számításáért. Ennek leszármazottai a különböz˝o teszt és benchmark feladatok is, de a leggyakrabban használt leszármazott a küls˝o szimulátorral kommunikáló két osztály. A régebbi verzió az Excel® alkalmazást használta a szimulátorral való kommunikációra (mint DDE szervert), az új verzió pedig egy platform független kommunikációs protokollal rendelkezik. A
61
2. algoritmus: A kifejlesztett genetikus algoritmus pszeudokódja. Input: cmpF : a módosított Pareto dominancia operátor Input: toGrid: a rácshoz illesztés függvénye Input: s, a : a populáció és az archívum mérete Input: r, m : a rekombinációs és mutációs faktorok Data: t : a generáció Data: Pop: a populáció Data: Arc: az archívum a legjobb egyedek tárolására Data: Par: az aktuális szül˝ok tárolója Data: Off: az új utódok tárolója Data: v : az egyedek fitness értékének elérése Output: X ? : a talált legjobb megoldások halmaza 1 2 3 4
begin X ←− createDecisionSpace(X) //a döntési tér megadása Y ←− createObjectiveSpace(Y) //az értékelési tér megadása C ←− createConstraintSpace(C) //a feltételek térének megadása t ←− 0 Arc ←− ; ¡ ¢ Pop ←− toGrid createPop(s,¡X ) //a populáció inicializálása ¢ Pop ←− evaluateIndividuals Pop , X , Y ,C //a szimulációk végrehajtása ¡ ¢ v ←− assignFitness Pop, Arc, cmpF //a Pareto rangsorolás elvégzése while terminationCriterion() do ¡ ¢ Arc ←− updateOptimalSetN Arc, Pop //az archívum frissítése Arc ←− pruneOptimalSet(Arc, a) //ritkítás, ha szükséges X ←− updateGrid(X , t //a rácsfelbontás változtatása ) ¡ ¢ Par ←− select Pop, Arc, v, s for i ←− 0 up to |Par| − 2 do if randu () ≤ r then Off[i ,i +1] ←− toGrid(recombine( Par[i +1])) ¡ ¡ Par[i ],¢¢ if randu () ≤ m then Off[i ,i +1] ←− toGrid mutate Off[i ,i +1] ¡ ¢ Off ←− evaluateIndividuals Off, X , Y //a szimulációk végrehajtása ¡ ¢ ,C v ←− assignFitness Pop , Arc , cmp //a Pareto rangsorolás elvégzése F ¡ ¢ Pop ←− reproducePop Par, Off, Pop, v //az új populáció kialakítása t ←− t + 1 ¡ ¢ return extractOptimalSet Pop ∪ Arc
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
end
62
protokoll támogatja a több szimulátor példánnyal való párhuzamos munkát (szerver-kliens modell). A protokoll f˝o részei a keresési (lehet˝oség) tér konfigurációja, az értékelési szempontok megadása, az egyedek értékelésre küldése, illetve az értékelt egyedek értékeinek fogadása. Az el˝oz˝oekben megfogalmazottak szerint kialakított genetikus algoritmus egyszer˝u pszeudokódját a 2. algoritmus tartalmazza.
3.2. Az eddigi alkalmazások áttekintése Az algoritmus az elmúlt 15 év gyakorlati alkalmazásokban szerzett tapasztalatok alapján nyerte el a fentiekben bemutatott formáját. A módszer „evolúciója” során el˝oször csak a diszkrét, majd a folytonos és kés˝obb a kevert génekkel leírható problémák kódolása vált lehet˝ové. A kódoláshoz hasonlóan el˝oször az egyszempontú feltételek nélküli, majd a VEGA (Schaffer, 1984) módszeréhez hasonlóan kezelt többszempontú értékelés került be az algoritmus készletébe. Ezt követte a módosított Pareto dominancia kifejlesztése és implementálása, valamint a tulajdonság osztályokon alapuló vegyes összetett kódolás megalkotása. A rácsmódszer és többi hatékonyságot javító technika az utóbbi 3–4 évben nyerte el a jelenlegi formáját.
Gyakorlati alkalmazások – Preparatív kromatográfiás technológiák dinamikus szimulációja, Richter Gedeon Vegyészeti Gyár Rt, 1993-94. A kinetikai és hidrodinamikai paraméterek identifikálása. (Csukás and Balogh, 1994) – Szakaszos polimerizációs reaktor fels˝o szint˝u irányítása és adatbázis kezelése, Magyar Olaj és Gázipari Rt. Fejlesztési Kutatási Igazgatósága, 1996. A kinetikai és hidrodinamikai paraméterek identifikálása. (Csukás and Balogh, 1996b)
63
– Szimulált mozgó ágyas kromatográfiás folyamatok dinamikus szimulációja, Richter Gedeon Vegyészeti Gyár Rt, 1997. A kinetikai és hidrodinamikai paraméterek identifikálása. (Csukás and Balogh, 1997b)Temesvári et al. (2004, 2005) – Adszorpciós/elúciós és preparatív kromatográfiás technológiák tervezési és üzemeltetési optimalizálása, Richter Gedeon Vegyészeti Gyár Rt, 1998. A kinetikai és hidrodinamikai paraméterek identifikálása. Az elválasztási technológia tervezési optimalizálása. (Csukás and Balogh, 1998a) – Olajadalék intermedier kopolimer gyártási technológiák számítógéppel segített fejlesztése, tervezése és irányítása, Mol Rt., 1998-99. A polimerizációs technológia tervezési optimalizálása. (Csukás and Balogh, 1999) – Egy tipikus gyógyszeripari üzemcsarnok munkaegészségügyi és környezetvédelmi kockázatelemzésének mennyiségi vizsgálatát segít˝o szimulációs modell rendszer kidolgozása, Richter Gedeon Vegyészeti Gyár Rt, 2001-2009. A hidrodinamikai paraméterek identifikálása. (Csukás and Balogh, 2009) (Balogh et al., 2004) – Új, hulladékszegény kromatográfiás eljárások bevezetése a gyógyszeriparban. NKFP-3A/047/2002 pályázat, (modell bázisú tervezés és irányítás) Richter Gedeon Vegyészeti Gyár Rt., Veszprémi Egyetem, Kaposvári Egyetem, 2002-2005. A kinetikai és hidrodinamikai paraméterek identifikálása. (Csukás and Balogh, 2002) – Biokémiai folyamatok szimulációs modell segítségével történ˝o vizsgálata. Richter Gedeon Vegyészeti Gyár Rt., 2005-2007. A biotechnológiai folyamat tervezési optimalizálása. (Csukás et al., 2007b)(Barthó et al., 2006) – Fluidizációs granulálási technológiák adatainak elemzése. Richter Gedeon Vegyészeti Gyár Rt., 2006-2009. A modell paraméterek identifikálása. (Csukás et al., 2006) 64
– Metabolikus hálózatok generikus kétréteg˝u háló modelljének identifikálása, Kaposvári Egyetem, 2005-2006. Az egyensúlyi és kinetikai paraméterek identifikálása. (Csukás and Balogh, 2005b)(Veizer et al., 2005) – Az enzimkoncentráció meghatározása az aktivitásmérés identifikált modellje alapján, Kaposvári Egyetem, 2007. Az egyensúlyi és kinetikai paraméterek identifikálása. (Csukás et al., 2007a)
Kísérleti fázisú alkalmazások – Az állat és környezete kapcsolatának dinamikus szimulációja, Kaposvári Egyetem, 2000. A modell paraméterek identifikálása. (Takátsy et al., 2000) – Többérdek˝u logisztikai láncok fejlesztése genetikus algoritmussal összekapcsolt dinamikus szimulátorral, Kaposvári Egyetem, 2000. A modell paraméterek identifikálása. (Balogh et al., 2000) – Az állati metabolizmus makroszint˝u dinamikus szimulációja mérnöki alkalmazásokra, Kaposvári Egyetem, 2001. A modell paraméterek identifikálása. (Takátsy et al., 2001) – Mérnöki logisztika az üzemirányításban, Kaposvári Egyetem, 2001. Irányítási optimalizálás. (Csukás et al., 2001) – Baromfiistálló energetikai és makroszint˝u metabolikus szimulációjának tapasztalatai, Kaposvári Egyetem, 2001. A modell paraméterek identifikálása. (Lukács et al., 2001) – Gazdasági potenciál számításon alapuló lokális döntéseket támogató algoritmusok fejlesztése, Kaposvári Egyetem, 2005. Ütemezési optimalizálás. (Leh˝ocz et al., 2005) – Optimális pontozásos rangsorolás pályázati döntésekhez, DDRFÜ, 2005. Optimális ponthatárok kialakítása (A 3.3.1. pont alatt részletesen bemutatásra kerül.) (Varga, 2006) 65
– Kísérlet egy farmgazdálkodást segít˝o genetikus algoritmussal fejlesztett szimulátor kialakítására, Kaposvári Egyetem, 2005. Optimális vetésforgó tervezése. (A 3.3.2. pont alatt részletesebb bemutatásra kerül.) (Bosnyák, 2005)
PhD kutatási és oktatási alkalmazások A genetikus algoritmust 8 egyetemi diplomadolgozatban (Bóity, 2001; Guldin, 2001; Bosnyák, 2005; Leh˝ocz, 2005; Varga, 2005; Veizer, 2005; Zala, 2005; Szente, 2007) egy megvédett (Varga, 2009) és két készül˝o PhD dolgozatban (Leh˝ocz és Kratafila) alkalmazták. Az el˝oz˝oek alapján több, az oktatásban demonstrációs célra felhasznált programcsomag készült „A folyamatok modellezése és szimulációja” tárgyhoz (például metabolikus hálózatok identifikálása, növénytermesztési folyamatok tervezése, valamint többtermékes gyártási rendszerek tervezése, irányítása és ütemezése).
3.3. Illusztráló példák A továbbiakban a kifejlesztett genetikus algoritmus bemutatását egy-egy egyszer˝u döntés támogató, agrárgazdasági és logisztikai példán keresztül mutatom be.
3.3.1. Optimális pontozásos rangsorolás kialakítása pályázati döntésekhez Az els˝o példa egy „optimális” pályázati rangsorolás kialakításának támogatását mutatja be, pályázatok elbírálásának megkönnyítése érdekében. A Dél-Dunántúli Regionális Fejlesztési Ügynökség Kht. (DDRFÜ) hatáskörébe tartozó 182 darab 2005-ben lezajlott Terület- és Régiófejlesztési célel˝oirányzat (TRFC) pályázat képezte a vizsgálat alapját. A pályázatok értékelése a szakmai bírálók 8 kérdésre adott pontjainak összegzésével történt. A kérdésekre adható pontszámok határai a 4. táblázatban találhatók.
66
120
Összpontszám
100
80
60
40
0
20
40
60
80
100
120
140
160
180
Pályázat sorszáma
21. ábra. A pályázatok pontszámainak megoszlása az eredeti ponthatárokkal.
A 182 értékelt pályázat összpontszámának eloszlását a 21. ábrán követhetjük figyelemmel. Az ábrán jól látható, hogy a pontszámok alapján a pályázatok többsége egy magasabb pontszámú (80–88), és egy alacsonyabb pontszámú (50–60) csoportba került. A „jó” és a „rossz” pályázatok elkülönülnek, de mindkét csoporton belül nagyon kis különbségek vannak az egyes pályázatok között. Így nehéz kiválasztani a sokkal kisebb számban befogadható pályázatot. Megoldás lehet, ha olyan ponthatárokat alakítunk ki, amelyek alkalmazásával a 10 legjobb és a 10 legrosszabb pályázat pontszáma a legmagasabb illetve a legalacsonyabb. Az új ponthatárokkal kapott összpontszámot egy pályázat esetén úgy számoljuk ki, hogy az eredeti pontozást a régi és az új határok arányában skálázzuk át majd összegezzük. A feladat tehát az, hogy keressünk olyan új ponthatárokat, amelyek alkalmazása esetén a maximalizáljuk a 10 legjobb és 4. táblázat. Az eredeti kérdések ponthatárai.
Kérdések: Ponthatárok:
1.
2.
3.
4.
5.
6.
7.
8.
0–15
0–15
0–15
0–10
0–15
0–15
0–5
0–10 67
5. táblázat. Az eredeti és a javasolt ponthatárok.
Eredeti:
0–15
0–15
0–15
0–10
0–15
0–15
0–5
0–10
Javasolt:
0–45
0–25
0–5
0–5
0–10
0–20
0–5
0–5
minimalizáljuk a 10 legrosszabb pályázat pontszámát. A megoldásra a genetikus algoritmust felhasználva a feladat jellemz˝oi a következ˝ok: A két értékelési függvény a 10 legjobbnak ítélt pályázat átlagos összpontszáma, valamint a 10 legrosszabbnak ítélt pályázat átlagos összpontszáma. A döntési teret a 8 kérdés ponthatárainak megadásával írjuk le. A ponthatárok a 0–100 intervallumba eshetnek, a minimális pontosság 1. A megoldások genetikus kódja egy 8 folytonos elemet tartalmazó „egyszer˝u” kromoszóma. A genetikus paraméterek beállítása során a populációméret 20, a küls˝o archívum mérete 80, a rekombináció valószín˝usége 0.8, a mutáció valószín˝usége 0.05. A kiértékelt megoldások száma 1600, a rácsméret kezdetben egységesen 10, majd minden 5. generációban kerekítve a felére csökken. A genetikus futás eredményét a 22. ábrán tekinthetjük meg. A 22.a) ábrán a feladat teljes Pareto frontjának közelítése látható véletlen megoldások és az eredeti ponthatárokkal meghatározott megoldás társaságában. A 22.b) ábrán a Pareto frontnak az els˝o értékelési függvény szerint 70–150 intervallumra lesz˝ukített részét láthatjuk az eredeti ponthatárokkal együtt. A szakért˝ok a Pareto fronton elhelyezked˝o egyedek közül választhatják ki az új ponthatárokat leíró megoldást. Ennek a megoldásnak az értékei láthatók az 5. táblázatban. A megoldás szerint számolt összpontszámok eloszlását a 23. ábrán mutatom be.
3.3.2. Növénytermeszt˝o családi gazdaság „optimalizálása” A második példa egy kisebb növénytermeszt˝o gazdaság er˝oforrásai id˝obeli változását vizsgálatát, illetve gazdasági elemzését támogatja a genetikus algoritmus segítségével. A családi gazdaság Pécs közelében 5 különböz˝o, – egymástól távolabb elterül˝o – összesen 75.55 hektár területen növénytermesztést folytat. 68
a) Az értékelési tér teljes Pareto frontja.
b) Az értékelési tér sz˝ukített Pareto frontja (70–150 intervallum).
22. ábra. A pályázati pontozás kialakításának értékelési tere.
69
120
Összpontszám
100
80
60
40
0
20
40
60
80
100
120
140
160
180
Pályázat sorszáma
23. ábra. Az algoritmus alkalmazása után választott ponthatárokkal számolt pályázati összpontszámok.
A termesztett növények: árpa, búza, kukorica, szója és zab. A földterületek modellben felhasznált tulajdonságai a 24. ábrán tekinthet˝ok meg. A gazdaság modellezése során figyelembe vett er˝oforrások és jellemz˝oik a 25. ábrán találhatók meg. A gazdálkodás során elvégzend˝o tevékenységek tulajdonságai és paraméterei a 26. ábrán láthatók. Ezen az ábrán terjedelmi okokból csak az árpa termeléséhez szükséges tevékenységek leírása van feltüntetve, de minden növényre ezzel azonos struktúrában kerül megadásra a szimulációhoz. A feladat
24. ábra. A földterületek tulajdonságai valamint a támogatások és hitelek mértékének és kifizetésének adatai.
70
25. ábra. A növénytermesztésben felhasznált er˝oforrások tulajdonságai.
26. ábra. Az árpa termesztéséhez szükséges tevékenységek jellemz˝oi.
71
27. ábra. A heurisztikusan talált és a genetikus algoritmus által kifejlesztett legjobb megoldások cash flow diagramjának összehasonlítása.
az, hogy olyan vetési sorrendet találjunk az 5 földterületen az 5 növényre valamint úgy ütemezzük az er˝oforrások felhasználását, hogy egy adott id˝oszak végén a gazdaság cash flow-ja a lehet˝o legtöbb legyen. A megoldásra a genetikus algoritmust felhasználva a feladat jellemz˝oi a következ˝ok: Az értékelési függvény egy adott id˝oszak végén (2 év) a cash flow érték maximalizálása. A döntési teret az 5 növény 5 földterületen történ˝o termelésének sorrendjei írják le. A tevékenységek ütemezését a szimulációs modell elvégzi. A megoldások genetikus kódja 5 darab 5 diszkrét gént tartalmazó permutálható génszakaszból álló összetett kromoszóma. A genetikus paraméterek beállítása során a populációméret 20, a rekombináció valószín˝usége 0.8, a mutáció valószín˝usége 0.05. A kiértékelt megoldások száma 1600, a diszkrét „rácsméret” kezdetben egységesen 2 majd minden 5. generációban felére csökken. Az algoritmus futása el˝ott és a futtatás után talált legjobb megoldások cash flow diagramjának összehasonlítása a 27. ábrán látható.
3.3.3. Egy háromtermékes gyártási folyamat vizsgálata A módszer használatának bemutatására harmadik példának egy még áttekinthet˝o, de már eléggé bonyolult logisztikai problémát választottam. A szakirodalomban „Single Switch Server” néven ismert probléma (Perkins and Kumark, 1989) publikációjából származik és matematikai modelljét (Agarwal 72
˙1 M
A max 1 n A mi 1
A max 2
A1
˙3 M
˙2 M
n A mi 2
A max 3
A2
n A mi 3
A3
Tisztítás
Gyártó berendezés
K3
K2
K1
28. ábra. A mintafeladatban szerepl˝o gyártás illusztrációja.
et al., 2002) is vizsgálták. A mintafeladatban három különböz˝o alapanyagot tartalmazó tartályból és egy alapanyagot feldolgozó gyártó berendezésb˝ol álló üzem szerepel, mely három eladásra szánt késztermék féleséget állít el˝o. Az üzem jellemz˝oje, hogy egy id˝oben csak egy alapanyag fajtát képes feldolgozni egy adott kapacitással, és minden alapanyag váltásnál egy tisztítási m˝uveletet kell elvégezni a másik alapanyag feldolgozása el˝ott. A tisztítási folyamat minden alapanyag típusnál más és más, a tisztító anyagok és a tisztítási technológia is különbözik. A folyamatos termelés érdekében biztosítani kell, hogy az üzem lehet˝oleg mindig hozzáférjen valamelyik alapanyaghoz, ezért a feldolgozandó termékek tartályokba áramlása gyakorlatilag folyamatos. A technológia szabályozásának részeként megadtuk a tároló tartályoknak azt a maximális szintjét, amikor a feldolgozandó alapanyag beáramlást le kell állítani a tartály véges tároló kapacitás miatt. A tartályok szintje szerint döntünk, hogy a tisztítás után melyik alapanyagot kezdjük el feldolgozni. Ha a feldolgozási kapacitás a beáramlásnál nagyobb, akkor a feldolgozás során a tartályszint csökken, és ki is ürülhetne, melynek következményeként az üzem 73
leállhatna. Ezért meg kell határozni azt a minimális szintet, amelynél az adott alapanyag feldolgozását meg kell szakítani, és váltani kell. A tisztítás után a legmagasabb szinten lév˝o tartályból kell elkezdeni a gyártást. A 28. ábrán a gyártás illusztrációja tekinthet˝o meg. A mintafeladat modellezésér˝ol és dinamikus szimulációjáról páldául (Bánkuti and Csukás, 2003) cikkében olvashatunk. A gyártás szabályozási algoritmusa a termékek közti váltást egy transzformált fuzzy-szer˝u megítélési függvény szerint végzi. A tartályok fizikai paramétereinek ismeretében az öt különböz˝o megítélés alá kerül˝o szint intervallumot határozunk meg. A (MIN,LP] tartományba ezzel a szabályzó mechanizmussal csak indításkor kerülhet a rendszer, mert folyamatos üzemben a gyártást már e fölött leállítjuk. Ennek megfelel˝oen az (LN,LP] tartományba es˝o megítélési értéknél az adott anyag gyártását leállítja a rendszer. Az (LP,UP) tartományban megfelel˝o a szint, ekkor változatlanul folyatódik a betáplálás illetve a gyártás. Az [UP,UN) tartományokba es˝o megítélési értéket f˝oként a következ˝o gyártandó alapanyag kiválasztásához használjuk. A gyártás mindig annak az alapanyagnak a felhasználásával folytatódik, amelynek a megítélési függvény értéke a legnagyobb. Az [UP,MAX) tartománybeli értéknél a szabályzó algoritmus leállítja a betáplálást. A megítélési függvényt a 29. ábrán mutatom be. A megoldásra a genetikus algoritmust felhasználva a feladat jellemz˝oi a következ˝ok: Az értékelési függvények el˝oször a „naturálisak”: a termelés maximalizálása, a készletek minimalizálása és az átállások er˝oforrásigényének minimalizálása. A költségek és eladási ár hozzárendelése után a gazdasági célfüggvény a maximális fedezeti összeg elérése. Adott alapanyag áramok esetében a feladat esetében a döntési teret a tartályok és a gyártóberendezés kiválasztása alkotja. A beszerezhet˝o tartályoknak széles a választéka, 3 egységenként növekv˝o kapacitással rendelhet˝ok. A berendezések 5 féle típusban érhet˝ok el. Minden típus más és más folytonos paraméterként állítható feldolgozási kapacitással rendelkezik minden egyes feldolgozandó alapanyagra nézve. A döntési tér a 6. táblázban látható. A megoldások genetikus kódja tehát 7 folytonos géntípusokból (tartályok)
74
megítélés
1
0
Szint MIN
LN
LP
UP
UN MAX
transzformáció
megítélés
1
0
Szint MIN
LN
LP
UP
UN MAX
-1
29. ábra. A szabályzó algoritmus transzformált megítélési függvénye.
és egy hierarchikus diszkrét géntípusból (berendezések és paramétereik) álló kromoszóma. A genetikus paraméterek beállítása során a populációméret 20, az archívum mérete 100, rekombináció valószín˝usége 0.8, a mutáció valószín˝usége 0.05. A kiértékelt megoldások száma 2400, a rácsméret kezdetben egységesen az intervallumok 20-ad része, majd minden 5. generációban felére csökken. Három naturális szempont szerinti értékelés Pareto frontja a 30. ábrán látható. A három naturális szempont a következ˝o volt: – f 1 = az összes termelés (maximalizálandó) – f 2 = az átlagos készlet (minimalizálandó) – f 3 = az átállások er˝oforrás igénye (minimalizálandó) A vizsgált példára becsült költségtényez˝ok felhasználásával egy egyszempontú gazdasági értékelést is elvégeztünk. Az optimumhoz tartozó naturális értékek Pareto fronton való elhelyezkedését (a nagyobb méret˝u pont) a 31. ábrán illusztráljuk.
75
6. táblázat. A Single Switch Server feladat felbontása tulajdonság osztályokra, a tulajdonságok megadása és a tulajdonságok paramétereinek meghatározása. Az M˙ i folytonos tulajdonság az i . anyag áramlási sebességét jelenti. Az M változó az adott tartály kapacitása, míg a MIN, LN, LP, UP, UN, MAX változók a megítélési függvény paramétereinek felelnek meg a tartály kapacitásának arányában kifejezve. A Pi , j változók a j . berendezés típus i . anyagra vonatkozó feldolgozási kapacitását írják le.
Tulajdonság osztályok A1 áram A2 áram
Tulajdonságok
Paraméterek
M˙ i
A3 áram A1 tartály A2 tartály
˙ M
MIN, MAX, LN, LP, UP, UN, M
A max A mi n
A
A3 tartály Gyártó berendezés
P1,1 , P2,1 , P3,1
Gyártó berendezés
P1,2 , P2,2 , P3,2
Gyártó berendezés
P1,3 , P2,3 , P3,3
Gyártó berendezés
P1,4 ,P2,4 ,P3,4
Gyártó berendezés
P1,5 , P2,5 , P3,5
Gyártó berendezés
76
Pareto front
0 -200 -400 -600 f3
-800 -1000 -1200 -200 0
-150
10000 20000
-100 f2
30000 40000
-50 50000
f1
0 60000
30. ábra. A három naturális szempont szerinti Pareto front.
77
Pareto front Gazdasági maximum
0 -200 -400 -600 f3
-800 -1000 -1200 -200 0
-150
10000 20000
-100 f2
30000 40000
-50 50000
f1
0 60000
31. ábra. A maximális profitot hozó gyártás elhelyezkedése a Pareto fronton
78
Pareto front Gazdasági maximum
-100 -200 -300
f3
-400 -500 -600 -700 -800 -900
-200 -150 -100 f2
-50
50000 50500 51000 51500 52000 52500 53000 f1 53500 0 54000
32. ábra. A három szempontú értékelés Pareto frontjának sz˝ukítése
A kidolgozott genetikus algoritmusnál a döntéshozó céljaival illetve heurisztikus ismereteivel összhangban sz˝ukíthetjük a Pareto front terjedelmét. Példaképpen a túlzottan kicsi (50000-nél kisebb) össztermelést kisz˝ur˝o futás eredménye a 32. ábrán látható. A genetikus algoritmusban lehet˝oséget biztosítottunk a célfüggvények mellett korlátozó feltételek el˝oírására is. a 33. ábrán azt az esetet mutatom be, amikor az egyszempontú gazdasági értékelésnél feltételként el˝oírtuk az egyes termékekb˝ol termelend˝o mennyiségeket, azaz a termékösszetétel kötött. Az erre kapott optimális megoldást a nagyobb méret˝u pont jelzi a három szempontú naturális értékelés Pareto frontján.
79
Pareto front Gazdasági max . megkötésekkel
-100 -200 -300
f3
-400 -500 -600 -700 -800
-200 -150 -100 f2
-50
49500 50000 50500 51000 51500 52000 52500 f1 53000 53500 0 54000
33. ábra. A kötött termékösszetételt tartalmazó gyártás elhelyezkedése a Pareto fronton.
80
3.3.4. Tesztfeladatok A kifejlesztett genetikus algoritmus képességeinek bemutatását néhány szakirodalomból is ismert tesztfeladatok segítségével folytatom. A genetikus kódolás kialakítása lehet˝ové teszi, hogy a módszert használva a „hagyományos” folytonos, diszkrét és permutációkat leíró kódolást használjuk, hiszen ezek az összetett kódolás egyszer˝u részesetei. Az algoritmus kialakításánál nem volt célom az egyszer˝u és gyorsan számítható értékelési függvényekkel való futások hatékonyságának növelése, de a kapott eredmények fontosak lehetnek az algoritmus konvergenciájának megítélésében. El˝oször a folytonos génszakaszok kezelését mutatom be, majd a permutációt tartalmazó génszakaszokkal leírható utazó ügynök probléma megoldását ismertetem. A folytonos feladatok adatai a 7. táblázatban találhatók. A feladatok két szempontú optimalizálási problémákat írnak le. Az els˝o feladatnál (ZDT3) egy több különálló szakaszból álló konvex Pareto front megtalálása a cél egy n = 30 dimenziós keresési tér fölött, míg a másodiknál egy konkáv Pareto front felderítését szeretném bemutatni. Itt a keresési teret n = 100 változó feszíti ki. A harmadik feladatnál kétféle megkötés és a Pareto front szakadozott és konkáv tulajdonságai nehezítik a megoldást. A genetikus algoritmus paramétereit a futtatások során nem változtattam. A paraméter beállítások a következ˝ok voltak: minden esetben 10880 kiértékelést végeztem (ez 400 generációt jelentett), a populáció mérete 34, a rekombináció valószín˝usége 0.8, a mutáció valószín˝usége 0.05. A rács felbontása kezdetben a 5.46e-3 (hogy ne illeszkedjen az értelmezési tartomány határaira), majd minden 5. generációs lépésnél a 10-ére csökkentem. A minimális pontosság 1e-30 minden génre. Az elvárt intervallumok és az értelmezési tartományok határai azonosak. A 34. ábrán és a 35. ábrán látható, hogy a megoldások egyenletes eloszlásban és jól közelíti a valódi Pareto frontot mindkét esetben. A 36. ábrán és 37. ábrán található megoldásoknál a Pareto frontok közelítéséhez 100 egyed méret˝u küls˝o archívumot használtam. Megfigyelhet˝o, hogy azonos számú értékelési függvény számítás mellett jóval több nem dominált egyedet találtunk meg, mint az archívum használata nélkül. 81
7. táblázat. A többszempontú tesztfeladatok adatai.
Név
Definíció
Feltételek
f 1 (x) = x 1 Ã
s
f 2 (x, g ) = g (x) 1 −
ZDT3
9 g (x) = 1 +
n P i =2
x1 x1 − sin(10πx 1 ) g (x) g (x)
xi
!
0 <x 1 , x 2 < 1
n −1
n = 30
ZDT6
f 1 (x) = 1 − e-4x1 sin6 (4π x 1 ) Ã ¶ ! µ f 1 (x) 2 f 2 (x, g ) = g (x) 1 − g (x) v u P u n xi u 4 9 t i =2 g (x) = 1 + n −1
0 <x 1 , x 2 < 1
n = 100
0 <x 1 , x 2 < π
TNK1
f 1 (x) = x 1 f 2 (x) = x 2
0 ≥ − x 2 − y 2 + 1 + a cos(b arctan(
x1 )) x2
1 1 1 ≥(x 1 − )2 + (x 2 − )2 2 2 2 a =0.1, b = 16
82
1.2 P F v al ód i P F i smer t
1 0.8 0.6 0.4
f2
0.2 0 −0.2 −0.4 −0.6 −0.8 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
f1
34. ábra. A ZDT3 feladat Pareto frontjának közelítése.
83
1 P F i smer t P F v al ód i
0.9 0.8 0.7 0.6
f2
0.5 0.4 0.3 0.2 0.1 0 −0.1 0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
f1
35. ábra. A ZDT6 tesztfeladat nem dominált megoldásai.
84
1.2 P F v al ód i P F i smer t
1 0.8 0.6 0.4
f2
0.2 0 −0.2 −0.4 −0.6 −0.8 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
f1
36. ábra. A ZDT3 feladat Pareto frontjának közelítése küls˝o archívum használatával.
85
1 P F v al ód i P F i smer t
0.9 0.8 0.7 0.6
f2
0.5 0.4 0.3 0.2 0.1 0 −0.1 0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
f1
37. ábra. A ZDT6 tesztfeladat archívum segítségével megtalált Pareto optimális megoldásai.
86
6 P F v al ód i 1.g ener áci ó 10.g ener áci ó 400.g ener áci ó
5
4
f2
3
2
1
0
−1 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
f1
38. ábra. A kezdeti megoldások és aktuális Pareto frontok „vándorlása” ZDT3 feladat megoldása során.
A 20 egyed méret˝u kezdeti populáció egyedeinek elhelyezkedését és a maximum 100 méret˝u archívumban található aktuális Pareto front „vándorlását” a 38. ábrán követhetjük. A fenti két tesztfeladat esetében a kifejlesztett genetikus algoritmussal talált Pareto frontok „min˝oségét” néhány, a szakirodalomban standardnak tekinthet˝o evolúciós algoritmus által szolgáltatott megoldással hasonlítottam össze. Ezek rendre az IBEA (Zitzler and Kunzli, 2004) az NSGA2 (Deb et al., 2000) és a SPEA2 (Zitzler et al., 2001a). A teszt elvégzéséhez a szabadon letölthet˝o PISA (Platform and Programming Language Independent Interface for
87
Search Algorithms)1 keretrendszert használtam fel. A felhasznált algoritmusok paramétereit a kifejlesztett algoritmus paramétereivel összhangban állítottam be. Az algoritmusok többi paramétere a szintén szabadon letölthet˝o hatékonyság tesztel˝o csomagban2 található alapértékével szerepelt. A teszt elvégzése során minden algoritmussal 10 futtatást végeztem mindkét feladatra majd a legjobb megoldásokat adó futások Pareto frontját ábrázoltam. A legjobb futások eredményeit a ZDT3 feladat esetében a 39. ábrán, ZDT6 feladat esetében pedig a 40. ábrán tekinthetjük meg. Mindkét feladat esetén vizuálisan is megállapítható, hogy ilyen kis populációméret (34) és generációszám (400) esetén a kidolgozott algoritmussal szolgáltatott megoldások a legjobbak közé tartoznak, különösen igaz ez a nagyobb méret˝u ZDT6 feladatnál. A feltételeket tartalmazó harmadik tesztfeladat (TNK1) legjobb megoldását a 41. ábra mutatja be. A feltételek kezelése a két feltételsértés normalizált értékének maximumaként történt ebben a példában. A permutációt tartalmazó génszakaszok használatát egy 100 város méret˝u egyszempontú utazó ügynök feladat kapcsán mutatom be. Az algoritmus paraméterei a következ˝ok voltak: 90000 kiértékelést végeztünk, a populáció mérete 40, a rekombináció valószín˝usége 0.8, a mutáció valószín˝usége 0.05. A keresztezésre a PMX operátort, mutációra az egyszer˝u cserét alkalmaztam. A „rács” felbontása a génszakaszra kezdetben 32, majd minden 5. generációs lépésnél a felére csökkentettük. A minimális „pontosság” természetesen egy. Egy kezdeti és a talált optimális útvonal a 42. ábrán tekinthet˝o meg.
1 http://www.tik.ee.ethz.ch/sop/pisa/ 2 http://www.tik.ee.ethz.ch/sop/pisa/?page=assessment.php
88
P F v al ód i P F sa j át P F i bea P F nsg a2 P F spea2
2.4 2.2 2 1.8 1.6
f2
1.4 1.2 1 0.8 0.6 0.4 0.2 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
f1
39. ábra. A ZDT3 feladat Pareto frontjának közelítése a kifejlesztett valamint az IBEA, NSGA2, SPEA2 algoritmusokkal.
89
4
3.5
3
f2
2.5
2 P F v al ód i P F sa j át P F i bea P F nsg a2 P F spea2
1.5
1
0.5
0 0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
f1
40. ábra. A ZDT6 tesztfeladat különböz˝o algoritmusok által szolgáltatott Pareto optimális megoldásai.
90
1.4 P F i smer t P F i g azi 1.2
1
F2
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
1.2
1.4
F1 41. ábra. A TNK1 feladat nem dominált megoldásai.
91
v 69
v 100 v 39
v 30
v 65 v 18
v4
v 70
v 45
v 84
v 61
v 68
v 33 v 86
v 17 v 10
v 99
v 55 v 47
v 73
v 63
v 95
v 62 v 44
v 87
v 20
v7
v 83 v 91
v 55 v 47
v 60
v 94
v 73
v 89
v 26
a) Az utazóügynök probléma egy véletlen kezdeti megoldása 100 város esetén.
v 78
v 63
v 62 v 44
v 96 v 19 v 59
v 91 v 42
v 20
v7
v 37
v 87
v 83
v 46
v 85
v 58 v 95
v 98 v 11
v 40
v 76 v 16
v 22
v 92 v 79
v 23
v 41 v 66
v8
v 88
v 38 v 90
v 99
v 74
v 42
v 37
v 35 v 57
v 64 v 31
v 56
v 59
v 46
v 85
v 58
v 17
v 21 v 50
v 71
v 49
v 77 v 53
v 36
v 10 v 40
v 76 v 16
v 98
v 78
v 89
v 19
v 66
v8
v 22
v 92
v 11
v 41
v 31
v 43
v 86
v 25
v 52
v 67 v 75
v 29
v 33
v 96
v 57
v 64
v 56
v 74
v 35
v 49
v 77 v 53
v 36
v 61
v 24
v 34
v 50
v 71
v 12
v 81
v1 v 43
v 15
v3
v 75
v 29
v 82
v 13
v 93
v 68
v 48
v 70
v 45
v 84 v 21
v 27 v 72
v2
v 54
v6
v 14 v5
v 25
v 52
v 67 v1
v 32
v 80
v 51 v 97
v 28
v 12
v 81
v 24
v 65 v 18
v4
v9
v 82 v 15
v3
v 34
v 72
v2
v 13
v 93
v5
v 39
v 30
v 54
v6
v 14
v 28
v 48
v 27
v 97
v9
v 69
v 100
v 32
v 80
v 51
v 88 v 79
v 38 v 60
v 90
v 23 v 94
v 26
b) Az utazóügynök probléma optimális megoldása 100 város esetén.
42. ábra. Az utazóügynök probléma megoldása 100 város esetén.
92
4. FEJEZET KÖVETKEZTETÉSEK, JAVASLATOK
A bemutatott kutatási eredmények és az elmúlt másfél évtizedben a folyamatosan fejlesztett genetikus algoritmussal végzett gyakorlati feladat megoldás tapasztalatai alapján levonható fontosabb következtetések az alábbiak szerint foglalhatók össze: Az összetett genetikus kódolás nagyon hatékonyan alkalmazható a diszkrét és folytonos jellemz˝ok együttes kezelésére. Ezen belül az inkompatibilitási relációk el˝ozetes megadása segítségével elkerülhet˝o, hogy bonyolultabb feladatok megoldásánál speciális genetikus kódolást kelljen kidolgozni. Az összetett genetikus kódolás és az ezzel összhangban alkalmazott operátorkészlet használatának hatékonyságát az illusztráló példák és a tesztfeladatok is igazolták. Ezen túlmen˝oen, a kidolgozott módszerek jól beváltak számos hibrid modell identifikálásánál, illetve a hibrid modellek alkalmazásával végzett optimális tervezési, irányítási és ütemezési feladatok megoldásánál. A folytonos tulajdonságosztályok (gének) definiálásánál nagyon hatékony az összetett kódolás és a kidolgozott rácsmódszer szinergikus alkalmazása. Ez a keresési tér (lehet˝oségtér) megadásánál a módszert alkalmazó szakért˝o számára is hatékony lehet˝oséget ad heurisztikus ismereteinek hasznosítására. A kidolgozott rácsmódszer egyidej˝uleg biztosítja a genetikus algoritmus adekvát inicializálását és hatékony futását kis populáció méret és kis generáció szám mellett is. Az ezáltal megengedhet˝o, jelent˝os számítógépi er˝oforrást igényl˝o értékelés számos gyakorlati probléma megoldásánál lehet˝ové tette a lehet˝o legrészletesebb modellek alkalmazását. Ez nagyon jelent˝os, mivel a valós m˝uszaki és gazdasági alkalmazásoknál az eredményesség a részletekben rejlik, ezért el˝onyösebb kisebb számú vizsgálatot végezni egy részletesebb modellel, mint jóval nagyobb számú értékelést készíteni leegyszer˝usített modellek alapján. A Pareto frontok vizsgálatán alapuló többszempontúság kezelésre kidolgozott módszer jelent˝os mértékben hozzájárul a többszempontúság korrekt kezeléséhez, ezen belül a szempontok adekvát kiválasztásához és a több szempontból elegend˝oen jó megoldások megfelel˝o kifejlesztéséhez. A gyakorlati feladatok megoldásánál az értékelési szempontok megadásával és/vagy az értékelési szempontok súlyozásával arra kell törekedni, hogy eleve kijelölhet˝o, illetve sz˝ukíthet˝o legyen a Pareto frontnak az a szakasza, ahol a jó megoldásokat
94
várjuk. A gyakorlatban megoldott és optimalizálási és identifikálási feladatok tanulsága egyértelm˝uen az volt, hogy nagyon sokszor nem lehet vagy nem érdemes az értékeléseket egyetlen célfüggvénybe aggregálni. Az optimalizálási alkalmazásoknál elvileg mindenki gazdasági értékelést (költségminimalizálást vagy profitmaximalizálást) szeretne, azonban nagyon sokszor nem lehet megadni a gazdasági célfüggvény kiszámításához szükséges adatokat. Tipikus eset az, amikor egy nagyon sok lépésb˝ol álló technológiai folyamat egy önmagában is bonyolult kis részletét kell optimalizálni. Ilyenkor elvileg ezt az önmagában is bonyolult, kis részletet is magában foglaló még nagyobb rendszerre kellene kiterjeszteni a vizsgálatot, mivel a részfolyamatba lép˝o, illetve onnan kilép˝o anyagoknak nem ismertek a gazdasági paraméterei. Ugyanakkor sokszor találkoztunk olyan helyzettel, hogy a vizsgált feladat szakért˝oje nagyon hatékonyan alkalmazható naturális célfüggvényeket tudott definiálni. Természetesen, a technológiai és a kapcsolódó gazdasági folyamatok között ma még sokszor jelentkez˝o szakadék megsz˝unését eredményez˝o módszerfejlesztések következtében egyre inkább lehet˝ové válik a gazdasági értékelés. A kidolgozott genetikus algoritmus illusztráló példán történ˝o bemutatásával összhangban, az átmeneti id˝oszakban valószín˝uleg hatékony a részleges gazdasági és naturális értékelési szempontok kombinációját alkalmazó többszempontú értékelés. Az elmúlt id˝oszakban fejl˝od˝o, jelen munkában továbbfejlesztett és integrált genetikus algoritmussal szerzett tapasztalatok igazolták, hogy a kis populáció méret és generációs szám alkalmazása esetén el˝onyösek azok a hatékonyságot növel˝o technikák, amelyek az összes vizsgált változat tárolásán alapulnak. A nagy számításigény˝u értékelések megvalósításánál egyértelm˝uen bevált a populációban lév˝o egyedek makrogranulárisan párhuzamos értékelésére kidolgozott megoldás. A PC klaszteren megvalósított módszer közelít˝oleg a klaszterben lév˝o központi egységek számával arányos mértékben gyorsítja a genetikus algoritmus által vezérelt evolúciós folyamat végrehajtását. A kidolgozott új megoldások minél szélesebb kör˝u kipróbálása érdekében kutató csoportunk, illetve az Informatika Tanszék és a tágabb egyetemi szakmai környezet közelmúltban indított, illetve jöv˝oben induló munkáinál célszer˝u
95
lenne kipróbálni a kutatómunka során kifejlesztett jelenlegi állapotok szerint konszolidált szoftver implementációt. Az így kapott tapasztalatok visszacsatolása után azok figyelembe vételével véglegesíthet˝ok egyes, még kevésbé kiforrott részek. Egyúttal célszer˝u lenne a tapasztalatokat is felhasználva, intenzív publikációs tevékenységet folytatni. Kétségtelen, hogy a módszer fejl˝odését az elmúlt id˝oszakban alapvet˝oen a különféle természettudományos és m˝uszaki feladatok megoldására jelentkez˝o elméleti és gyakorlati igény motiválta. Ugyanakkor nagyon aktuális és fontos feladat lenne az eredmények hasznosítása különféle gazdasági folyamatok megoldásánál. Hasonló módon lényeges és aktuális feladat a módszer ötvözése a gazdasági rendszerek kezelésére alkalmazott más szoftver rendszerekkel. A Kaposvári Egyetem Gazdaságtudományi Karának tevékenységét valamint a Gazdálkodás és Regionális Tudományok Doktori Iskola profilját is figyelembe véve, magam is törekedni fogok a gazdasági alkalmazásokhoz vezet˝o együttm˝uködésre. Sz˝ukebb szakmai szempontból, várhatóan további izgalmas kutatómunka körvonalazódik a többszempontú értékelés Pareto frontjának interaktív és/vagy automatikus elemzésén alapuló módszerek kidolgozásában. Ehhez kapcsolódóan várható, hogy a sz˝ukebb értelemben vett optimalizálási feladatok mellett, további feladatok jelentkeznek a döntés támogató rendszerek területén.
96
5. FEJEZET ÚJ TUDOMÁNYOS EREDMÉNYEK
1. Új összetett genetikus kódolási módszert dolgoztam ki, amelyben szerkezet hálón alapuló, opcionálisan hierarchikus és teljes permutációt megvalósító diszkrét génszakaszok kombinálhatók. A szerkezethálón alapuló génszakaszok esetében a tulajdonság osztályokba sorolt tulajdonságok között opcionálisan inkompatibilitási relációkat lehet definiálni. A kódolás egységesen kezeli a diszkrét és folytonos tulajdonság osztályokat. A folytonos tulajdonság osztályok alléljai egy el˝oírt értelmezési tartomány el˝oírt számú részre való felbontásával automatikusan generált diszkrét elemek. Az értelmezési tartományon belül külön megadjuk az alkalmazás során a felhasználó által el˝ozetesen definiált elvárt rész-intervallum alsó és fels˝o korlátértékét. A megoldás el˝oírt fa-struktúrákkal leírt, összetett gének megadása révén lehet˝ové teszi a hierarchikus kódolást. A módszer biztosítja az el˝oz˝oek szerinti megoldás teljes permutációt megvalósító génszakaszokkal való kiegészítését, illetve ezek automatikus felismerését és kezelését. A kezdeti populáció inicializálására, valamint a rekombinációk és mutációk megvalósítására olyan új, kiterjesztett genetikus operátorokat vezettem be, amelyek az el˝oz˝oek szerinti összetett genetikus kódolás esetén figyelembe veszik a génszakasz jellegét. A folytonos génekre és diszkrét génszakaszokra vonatkozóan a genetikus algoritmust egy olyan új, globális operátorral egészítettem ki, amely az értékelések eredményét˝ol függ˝oen automatikusan csökkenti a tulajdonságok felbontását, azaz a lépésközt. 2. A Pareto-értékelésnél jelentkez˝o Pareto-dominancia kezelésére egy olyan felhasználóbarát, összetett megoldást dolgoztam ki, amely felülr˝ol kompatibilis speciális részesetként tartalmazza a szakirodalomban alkalmazott feltételek és szempontok kezelésének módozatait. A feltételek és a szempontok csereszabatos implementációja révén azok egyenérték˝uen kezelhet˝ok, illetve felcserélhet˝ok egymással. A hatékonyság növelése érdekében lehet˝oség van a szempontokhoz tartozó, célokat meghatározó feltételek szempontokkal integrált leírására és kezelésére. Mind a feltételek, mind a szempontok esetében opcionálisan eltér˝o prioritások adhatók meg. 98
3. Új, platformfüggetlen, makrogranulárisan párhuzamosítható megoldást dolgoztam ki a genetikus algoritmus, és a genetikus algoritmus által javasolt megoldásokat kiszámító, és opcionálisan több szempontból kiértékel˝o tetsz˝oleges szimulátor közötti kapcsolat megszervezésére. 4. Az 1-3. pontok szerinti genetikus algoritmust – opcionálisan a megfelel˝oen implementált generikus szimulátorral összekapcsolva –, eredményesen alkalmaztam 11 konkrét m˝uszaki-gazdasági feladat megvalósított megoldásánál, 8 kísérleti fázisban lév˝o m˝uszaki-gazdasági probléma vizsgálatánál. Az algoritmust felhasználták 8 egyetemi diplomadolgozatban, egy megvédett valamint 2 készül˝o PhD dolgozatban, valamint több, az oktatásban demonstrációs célra felhasznált programcsomag elkészítésénél, például metabolikus hálózatok identifikálására, növénytermesztési folyamatok tervezésére, valamint többtermékes gyártó rendszerek tervezésére, irányítására és ütemezésére.
99
ÖSSZEFOGLALÁS
Az optimalizálás hagyományos kezelésmódját az jellemzi, hogy a vizsgált feladatot, illetve annak modelljét úgy alakítjuk át, és szükség szerint úgy egyszer˝usítjük le, hogy az lehet˝ové tegye egy matematikai konstrukció keretei között az egzakt optimum meghatározását. A mérnöki munkában nagyon fontosak a részletek, ezért az elmúlt évtizedekben fokozott törekvés nyilvánult meg arra vonatkozóan, hogy az optimalizálást minél részletesebb modellek felhasználásával végezzük el. A különböz˝o folyamatok részletes, dinamikus szimulációját biztosító eszközök gyorsan fejl˝odtek, ugyanakkor az egyre bonyolultabb folytonos és diszkrét változókat vegyesen tartalmazó hibrid modellek optimalizálása egyre nehezebben megoldható feladatot jelentett az ugyancsak fejl˝od˝o optimalizálási módszerek számára. Korunk egy másik jellegzetessége az, hogy térben és id˝oben egyre nagyobb mérték˝u, változó struktúrájú és növekv˝o komplexitású feladatokat kell „optimálisan” megoldani. Mindezeket felismerve, el˝otérbe kerültek a mesterséges intelligencia, majd az ezt felváltó számítógépi intelligencia talaján kifejl˝od˝o nem egzakt, heurisztikus és evolúciós módszerek. A nem egzakt jelz˝o azt jelenti, hogy elveszítjük a garanciát az abszolút optimum megtalálására. Ezért viszont kárpótol az a tény, hogy az elegend˝oen jó megoldásokat a szükséges és elégséges mértékben legrészletesebb modellekre határozhatjuk meg. A számítógépi intelligenciához sorolható genetikus algoritmus ezen nem egzakt optimalizálási módszerek egyike. A módszerrel a 90-es évek elején diploma dolgozatom készítésekor ismerkedtem meg. A módszer fejlesztése azóta végigkíséri szakmai munkámat. E munka alapvet˝o jellegzetessége kezdett˝ol fogva az volt, hogy a legkülönböz˝obb szakterületeken jelentkez˝o, és a mindenkori eszközökkel nehezen kezelhet˝o részletes és/vagy nagyméret˝u hibrid modellekkel leírható feladatokat kellett optimalizálni. A gazdasági célfüggvények mellett sokszor több naturális szempont alapján kellett végezni az optimalizációt, más esetekben viszont kombináltan kellett alkalmazni gazdaságilag megfogalmazható és naturális célkit˝uzéseket. A szimulációs számításokra használt, párhuzamosan fejlesztett módszer jellemz˝oje viszont egyre inkább az lett, hogy a számítások elt˝urték a tetsz˝oleges diszkrét és folytonos változtatásokat. Eközben a nemzetközi tendenciákkal összhangban,
101
egyre növekedett a lehetséges megoldások szimulációjának számítás igénye. Munkám alapvet˝o célja, a szakirodalomból megismerhet˝o módszerek és az elmúlt id˝oszakban a különféle gyakorlati problémák kihívásait figyelembe véve általam folyamatosan fejlesztett genetikus algoritmus összevetése alapján egy, a tapasztalatokat ötvöz˝o, többszempontú gazdasági döntéseket segít˝o genetikus algoritmus kidolgozása. A célkit˝uzéseket meghatározó, vizsgált probléma osztályok legfontosabb jellegzetessége az, hogy a genetikus algoritmus által el˝oállított megoldások értékelése nagy er˝oforrást igényl˝o dinamikus szimuláción alapul. Fontos korlátozást jelent, hogy a térben és id˝oben nagy kiterjedés˝u hibrid modellek esetében a lehetséges megoldások kódolására az egyszer˝u sztringek már nem elégségesek. Végül egy további lényeges jellegzetesség az, hogy az egyszempontú gazdasági értékelés mellett vagy helyett, gyakran több naturális értékelési szempontot is figyelembe kell venni. Kutatómunkámban a gyakorlatban el˝oforduló bonyolult, hibrid modellek sajátosságait figyelembe véve egy olyan összetett, egységes kódolási módszert dolgoztam ki, amely az el˝oforduló feladatok jelent˝os részére külön módosítások nélkül alkalmazható. A kidolgozott összetett genetikus kódolási módszernél egységesen kezelem a diszkrét és folytonos tulajdonságokat meghatározó géneket, egyúttal lehet˝oséget biztosítok a permutációt megvalósító génszakaszok kezelésére is. Az általános alkalmazást jelent˝os mértékben segíti, hogy lehet˝ové teszem a génekhez tartozó allélok közötti inkompatibilitások explicit leírását. A kidolgozott megoldás a szerkezetháló elméleten alapszik. A kódolás lehet˝ové teszi tetsz˝oleges összetett génszakaszok opcionálisan hierarchikus leírását is. A vizsgált problémaosztályoknál szükségképpen kis populációmérettel és kis generációszámmal megvalósítandó evolúciós folyamat támogatására egy olyan rácsmódszert dolgoztam ki, amely kis populációméretnél is támogatja a kezdeti populáció megfelel˝o generálását, ugyanakkor lehet˝ové teszi olyan módosított rekombinációs és mutációs operátorok kialakítását és használatát, amelyek támogatják a kevés egyed kiértékelésén alapuló evolúciós folyamatot. A kidolgozott rácsmódszer a folytonos génekre vonatkozó lehetséges értéktartomány célszer˝u megadásával a szakért˝o felhasználó heurisztikus tapasztalatainak
102
hatékony figyelembevételét is lehet˝ové teszi. Ugyanakkor a módszer szükség esetén automatikusan kiterjeszti a szakért˝o által definiált tartomány alsó vagy fels˝o határát. A kis populációméret és generációszám mellett is hatékony többszempontú értékelés kezelésére egy összetett Pareto dominancia elemz˝o folyamatot dolgoztam ki. Ez lehet˝oséget biztosít a döntéshozó preferenciáinak a priori, interaktív és a posteriori figyelembevételére is. Az el˝oz˝oek szerint kialakított genetikus algoritmus implementálásánál lehet˝oséget biztosítottam az összes vizsgált különböz˝o egyed tárolására, és ennek a felhasználását az operátorok alkalmazásánál. A bonyolult modellek szimulációján alapuló, nagy er˝oforrásigény˝u értékelést figyelembe véve egy olyan makrogranuláris párhuzamosítást dolgoztam ki, amely mind több processzoros vagy több magos (SMP), mind PC klaszteren hatékonyan megvalósítható. Ennek lényege az, hogy a master gépen futó genetikus algoritmus a slave gépeken futtatja a párhuzamos szimulációs értékeléseket. A kutatási eredmények és az elmúlt másfél évtizedben a folyamatosan fejlesztett genetikus algoritmussal végzett gyakorlati feladat megoldás tapasztalatai alapján levonható fontosabb következtetések az alábbiak szerint foglalhatók össze: Az összetett genetikus kódolás nagyon hatékonyan alkalmazható a diszkrét és folytonos és permutációt megvalósító jellemz˝ok együttes kezelésére. Ezen belül az inkompatibilitási relációk el˝ozetes megadása segítségével elkerülhet˝o, hogy bonyolultabb feladatok megoldásánál speciális genetikus kódolást kelljen kidolgozni. Az összetett genetikus kódolás és az ezzel összhangban alkalmazott operátorkészlet használatának hatékonyságát a tesztfeladatok és az illusztráló példa is igazolták. Ezen túlmen˝oen, a kidolgozott módszerek jól beváltak számos hibrid modell identifikálásánál, illetve a hibrid modellek alkalmazásával végzett optimális tervezési, irányítási és ütemezési feladatok megoldásánál. A folytonos tulajdonságosztályok (gének) definiálásánál nagyon hatékony az összetett kódolás és a kidolgozott rácsmódszer szinergikus alkalmazása. Ez a keresési tér (lehet˝oségtér) megadásánál a módszert alkalmazó szakért˝o számára
103
is hatékony lehet˝oséget ad heurisztikus ismereteinek hasznosítására. A kidolgozott rácsmódszer egyidej˝uleg biztosítja a genetikus algoritmus adekvát inicializálását és hatékony futását kis populáció méret és kis generáció szám mellett is. Az ezáltal megengedhet˝o, jelent˝os számítógépi er˝oforrást igényl˝o értékelés számos gyakorlati probléma megoldásánál lehet˝ové tette a lehet˝o legrészletesebb modellek alkalmazását. Ez nagyon jelent˝os, mivel a valós m˝uszaki és gazdasági alkalmazásoknál az eredményesség a részletekben rejlik, ezért el˝onyösebb kisebb számú vizsgálatot végezni egy részletesebb modellel, mint jóval nagyobb számú értékelést készíteni leegyszer˝usített modellek alapján. A Pareto frontok vizsgálatán alapuló többszempontúság kezelésre kidolgozott módszer jelent˝os mértékben hozzájárul a többszempontúság korrekt kezeléséhez, ezen belül a szempontok adekvát kiválasztásához és a több szempontból elegend˝oen jó megoldások megfelel˝o kifejlesztéséhez. A gyakorlati feladatok megoldásánál az értékelési szempontok megadásával és/vagy az értékelési szempontok súlyozásával arra kell törekedni, hogy eleve kijelölhet˝o, illetve sz˝ukíthet˝o legyen a Pareto frontnak az a szakasza, ahol a jó megoldásokat várjuk. A gyakorlatban megoldott identifikálási és optimálási feladatok tanulsága egyértelm˝uen az volt, hogy nagyon sokszor nem lehet vagy nem érdemes az értékeléseket egyetlen célfüggvénybe aggregálni. Az optimálási alkalmazásoknál elvileg mindenki gazdasági értékelést (költségminimalizálást vagy profitmaximalizálást) szeretne, azonban nagyon sokszor nem lehet megadni a gazdasági célfüggvény kiszámításához szükséges adatokat. Tipikus eset az, amikor egy nagyon sok lépésb˝ol álló technológiai folyamat egy önmagában is bonyolult kis részletét kell optimalizálni. Ilyenkor elvileg ezt az önmagában is bonyolult, kis részletet is magában foglaló még nagyobb rendszerre kellene kiterjeszteni a vizsgálatot, mivel a részfolyamatba lép˝o, illetve onnan kilép˝o anyagoknak nem ismertek a gazdasági paraméterei. Ugyanakkor sokszor találkoztunk olyan helyzettel, hogy a vizsgált feladat szakért˝oje nagyon hatékonyan alkalmazható naturális célfüggvényeket tudott definiálni. Természetesen a technológiai és gazdasági folyamatok között ma még sokszor jelentkez˝o szakadék megsz˝unését eredményez˝o módszerfejlesztések következtében egyre inkább lehet˝ové válik a
104
gazdasági értékelés. A kidolgozott genetikus algoritmus illusztráló példán történ˝o bemutatásával összhangban, az átmeneti id˝oszakban valószín˝uleg hatékony a részleges gazdasági és naturális értékelési szempontok kombinációját alkalmazó többszempontú értékelés. Az elmúlt id˝oszakban fejl˝od˝o, jelen munkában továbbfejlesztett és integrált genetikus algoritmussal szerzett tapasztalatok igazolták, hogy a kis populáció méret és generációs szám alkalmazása esetén el˝onyösek azok a hatékonyságot növel˝o technikák, amelyek az összes vizsgált változat tárolásán alapulnak. A nagy számításigény˝u értékelések megvalósításánál egyértelm˝uen bevált a populációban lév˝o egyedek makrogranulárisan párhuzamos értékelésére kidolgozott megoldás. A PC klaszteren megvalósított módszer közelít˝oleg a klaszterben lév˝o központi egységek számával arányos mértékben gyorsítja a genetikus algoritmus által vezérelt evolúciós folyamat végrehajtását. A kidolgozott új megoldások minél szélesebb kör˝u kipróbálása érdekében kutató csoportunk, illetve az Informatika Tanszék és a tágabb egyetemi szakmai környezet közelmúltban indított, illetve jöv˝oben induló munkáinál célszer˝u lenne kipróbálni a kutatómunka során kifejlesztett jelenlegi állapotok szerint konszolidált szoftver implementációt. Az így kapott tapasztalatok visszacsatolása után azok figyelembe vételével véglegesíthet˝ok egyes, még kevésbé kiforrott részek. Egyúttal célszer˝u lenne a tapasztalatokat is felhasználva, intenzív publikációs tevékenységet folytatni. Kétségtelen, hogy a módszer fejl˝odését az elmúlt id˝oszakban alapvet˝oen a különféle természettudományos és m˝uszaki feladatok megoldására jelentkez˝o elméleti és gyakorlati igény motiválta. Ugyanakkor nagyon aktuális és fontos feladat lenne az eredmények hasznosítása különféle gazdasági folyamatok megoldásánál. Hasonló módon lényeges és aktuális feladat a módszer ötvözése a gazdasági rendszerek kezelésére alkalmazott más szoftver rendszerekkel. A Kaposvári Egyetem Gazdaságtudományi Karának tevékenységét valamint a Gazdálkodás és Regionális Tudományok Doktori Iskola profilját is figyelembe véve, magam is törekedni fogok a gazdasági alkalmazásokhoz vezet˝o együttm˝uködésre. Sz˝ukebb szakmai szempontból, várhatóan további izgalmas kutatómunka
105
körvonalazódik a többszempontú értékelés Pareto frontjának interaktív és/vagy automatikus elemzésén alapuló módszerek kidolgozásában. Ehhez kapcsolódóan várható, hogy a sz˝ukebb értelemben vett optimalizálási feladatok mellett, további feladatok jelentkeznek a döntés támogató rendszerek területén.
106
SUMMARY In the conventional optimization methodologies the model of the investigated problem used to be simplified to the formalism of a mathematical construct that makes possible the determination of the exact optimum. Considering the importance of the details in the engineering problem solving, in the past decades increasing effort has been made for the possibly most detailed model based optimization. The dynamic simulation tools for the various processes developed rapidly, while the optimization of more and more complex hybrid (continuous/discrete) models became intractable in the development of in-parallel optimization methods. Another actual challenge is the optimal solution of the large scale, long term processes of changing structure with increasing complexity. Having recognized these difficulties, the inexact, heuristic and/or evolutionary methods of the artificial and computational intelligence became more and more important. In the case of an inexact approach there is no guarantee for the determination of the absolute optimum. This disadvantage is compensated by the fact, that good enough solutions can be determined on the basis of the necessarily most detailed models. One of the heuristic optimization methods of the Computational Intelligence is the Genetic Algorithm. I met these methods in my MSc thesis in the early 90-th, and have been dealing with it in my work since that time. This work is characterized and motivated by the demand on optimize detailed and/or large scale hybrid problems, coming from various field of application, which could not be solved with the available tools. In addition, in the case of an economic objective we had to optimize according to a number of natural criteria, or we had to combine the economic and natural objectives. The in-parallel developing generic simulation method more and more tolerates the arbitrary discrete and continuous changes. In addition, in accordance with the general tendency continuously increased the computational demand for the simulation of the possible solutions. The fundamental objective of this work is the comparison of the published methods with my results came from the continuous development of the genetic 107
algorithm, motivated by the solution of the various practical problems in the past decades. Based on this comparison, a combined genetic algorithm has to be developed for supporting the multicriteria economic decisions. The methods, applied for the economic optimization of complex systems in practical problem solving, have to satisfy many criteria. One of the two most important demands is supporting of the multicriteria evaluation in decision making. The other is, the capability for the representation of the complex possibility spaces, characterizing the economic and/or technological processes. In the development of the genetic algorithm, prepared for the multicriteria economic optimization, was motivated by the above criteria. I have been developed a new complex genetic coding, based on the structure lattice for the combination of optionally hierarchic, discrete/continuous and permutable gene sequences. The structure lattice makes possible the ‘a priory’ definition of the optional incompatibility relations between the discrete properties, classified into equivalency classes. The developed coding supports the uniform treatment of the discrete and continuous property classes. The alleles of the continuous property classes are described by automatically generated discrete elements, determined by the prescribed composition of the given domain. Within a domain, the user can define the lower and upper bounds of the awaited subinterval. The new coding supports the hierarchic coding, determined by the tree structure of the combined genes. Also the method makes possible the application, automatic recognition and treatment of the full permutations. I have introduced new, extended genetic operators for the initialization, recombination and mutation, which automatically consider the type of the given gene sequence within the scope of the previously described coding. I have extended the genetic algorithm with a new, global operator, which with the knowledge of the evaluations automatically decreases the great decomposition of the properties for both the continuous and discrete gene sequences. I have elaborated a user-friendly, complex method for the calculation of the Pareto-dominance that contains the published methods for the treatment of the constraints and evaluations, as full compatible special cases of the Pareto
108
evaluation. The implementation of constraints and evaluations supports the interchangeable equal use of them. In the case of the goal determining constraints, the increased efficiency is supported also by the integrated description and execution of the constraints, together with the evaluations. In addition, optional priority can be defined for both the constraints and the evaluating objectives. I have developed a new, platform independent macro-granularly parallelizable solution for the organization of the communication between the genetic algorithm and an optional simulator, which calculates and evaluates the proposed solution, according to the optionally multiple objectives. I have successfully applied the genetic algorithm of above 1-3. theses (optionally combine with an appropriate implemented generic simulator) for the solution of 11 industrial economical and technological problem, 8 economical and technological problem in experimental phase. The algorithm was applied in 8 MSc theses, in one successfully defended and two ongoing PhD theses, as well as in the preparation of many educational demonstration programs (e.g. identification of metabolic networks, planning of cultivation process, design, planning and scheduling a multi-product batch plant. Considering the above described research results, as well as the experiences, obtained from the application of the continuously developing genetic algorithm, the most important conclusions are the followings: The elaborated complex genetic coding can effectively be applied for the common representation of discrete and continuous genes, while the ‘a priory determination of the incompatibility relations helps to avid the elaboration specific individual genetic coding for the various complex tasks. The flexibility and efficiency of the complex genetic coding and of the respective extended set of operators are proven by illustrating examples and test problems. In addition, the elaborated methods were successfully applied for the identification and model based optimal design, control and scheduling of various complex practical problems with hybrid models. The synergic application of the elaborated complex coding and the grid method can effectively be applied for description of the genes for the continuous property classes. The developed methodology gives possibility to utilize the
109
heuristic knowledge of the expert in the description of the search space. Simultaneously, another advantages feature is, that having recognize the solutions in the vicinity of the prescribe bounds, the algorithm automatically extent the search space. The elaborated grid method supports the adequate initialization and effective run of the genetic algorithm, also in the case of small population size and of small generation number. This makes possible to increase the computational demand of the evaluation, consequently the application of the possibly most detailed models in the solution of many practical problems. This is very important, because the applicability of the economic and technical optimizations is determined by the exhaustiveness. Accordingly, the less number of calculations with a more detailed model is preferred to the more number of evaluations with a simplified one. The new method elaborated for the treatment of Paretodominance, contributes to the correct and powerful solution of the multicriteria problems. The new developments help the adequate choice and ranking of the constraints and evaluations, as well as the evolution of the multicriteria good enough solution. In the solution of the practical problems, the priority ranking of the constraints and evaluations combined with the new grid method, help to focus on the very part of the Pareto-front, where the good solutions are awaited. In practical applications to determine the evaluations, the expert often tends intuitively or consciously to define objectives of approximately identical importance. Consequently, the solutions with almost commeasurable values used to be preferred. One of the lessons, coming from the practical resolved optimization and identification problems was that it is not possible or it does not worth to aggregate the evaluation into a single objective function. In optimization, almost everybody wants to make an economic evaluation (i.e. minimizing the cost or maximizing the profit), however the data for the calculation of the economic goal function are not known. It is a typical case, when we have to optimize one, by-itself also complex part of a technological process, consisting of many steps. The economic parameters of the input and output materials are often not known. Consequently, the study ought to be extended to a greater system
110
consisting of this part. On the other hand, the field experts can declare very good natural objective functions. Nevertheless, on ongoing methodological development tends to bridge the existing gap between the technological and economical processes, and this makes possible the more and more correct economic evaluation. In accordance with the results, obtained from the logistical example of the present work, the combined application of the economic and natural evaluations seems to be a feasible method, temporarily. The experiences, obtained with the continuously developing and presently further developed, integrated genetic algorithm, proved that the applied coding and operators, as well as the archived storage of the investigated variants support the optimization process with small population and generation number. The optimization of the practical tasks with great computational demand for the evaluation can be solved by the macro-granularly parallel simulation and evaluation of the variants. The method, implemented in a PC cluster, can accelerate the genetically controlled evolutionary process almost proportionally with the number of CPUs of the cluster. The application of the developed methods for the solution of decision making, economic optimization and logistical problem solving will be illustrated by simple examples, followed by a couple of test problems elaborated for the evaluation of genetic algorithms. The consolidated software implementation of the genetic algorithm, developed in the present research work, ought to be applied in the ongoing and planned solution of the various practical problems. Accordingly, the methodology has to be utilized in the research project of the Department of Information Technology, as well as of the collaborating University environment. Considering the experiences, I plan to refine the embedded methodology. Simultaneously, the application will intensify the publication activity. The development of the methodology has been motivated by the theoretical and practical demands for the solution of various technological and scientific problems. One of the most important and actual challenge is the utilization of the results in the model based economic optimization of the various complex processes. Another important task is to combine the methodology with other
111
software tools, applied for the design and control of economic processes. Considering the activity of Faculty of Economic Sciences and Doctoral School of Economic and Regional Sciences at the Kaposvár University, I shall make additional efforts toward further collaboration in economic applications. From the field specific professional point of views, the most exciting research goal is to develop powerful methods for the interactive and automatic analysis and control of the Pareto-fronts. In addition to the optimization task, there may be interesting problems to be solved also from the field of the decision support systems.
112
KÖSZÖNETNYILVÁNÍTÁS
KÖSZÖNETNYILVÁNÍTÁS Köszönöm a Gazdálkodás és Regionális Tudományok Doktori Iskolának és a Kaposvári Egyetemnek, ezen belül a Gazdaságtudományi Karnak, hogy lehet˝ové tették számomra a kutatási téma kidolgozását. Köszönetet mondok az Informatika Tanszék kollektívájának munkám támogatásáért. Külön köszönöm témavezet˝om Csukás Béla valamint Varga Mónika és Bálint Jánosné türelmét és sokoldalú segítségét.
114
IRODALOMJEGYZÉK
Irodalomjegyzék
Ackley, D. H. (1987). A connectionist machine for genetic hillclimbing, Volume 28 of The Springer International Series in Engineering and Computer Science. Norwell, MA, USA: Kluwer Academic Publishers. Acsay, F., Csáki, Cs. and Varga, Gy. (1973). A vállalati géppark és géphasználat matematikai tervezése. In A nagyüzemi gazdálkodás kérdései. Akadémiai Kiadó Budapest. Agarwal, A., Ydstie, B. and Grossmann, I. (2002). Stability, performance and control of switched systems. In Annual Meeting of Center of Computer Aided Process Design,Carnegie Mellon University, Pittsburgh. Baker, J. E. (1985). Adaptive selection methods for genetic algorithms. In Proceedings of the 1st International Conference on Genetic Algorithms, pp. 101–111. In proceedings (Grefenstette, 1985). Baker, J. E. (1987). Reducing bias and inefficiency in the selection algorithm. In Proceedings of the second International Conference on Genetic Algorithms, pp. 14–21. In proceedings (Grefenstette, 1987). Balogh, S., Csukás, B., Sógor, A., Budai, M. and Miklósi, M. (2004). Egy soktermékes üzemcsarnok oldószer szennyez˝odésének szimulációs vizsgálata. Acta Agraria Kaposvariensis 8(3). Balogh, S., Csukás, B., Takátsy, T. and Tari, C. (2000). Többérdek˝u logisztikai láncok fejlesztése genetikus algoritmussal összekapcsolt dinamikus szimulátorral. M˝uszaki Kémiai Napok’ Veszprém, 41–45.
Banerjee, S. and Hazra, L. N. (1998). Thin lens design of cooke triplet lenses: application of a global optimization technique. In K. D. Bell, M. K. Powers, and J. M. Sasian (Eds.), Proceedings of SPIE, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference – Novel Optical Systems and Large-Aperture Imaging, Volume 3430, pp. 175–183. Barthó, I., Sinkó, B. I., Hantos, G., Balogh, S., Csukás, B. and Varga, M. (2006). Bioreaktor modelljének identifikálása és egy biokonverziós folyamat modell bázisú fejlesztése. Kaposvár május 26: V. Alkalmazott Informatika Konferencia. Beaty, S. J. (1992). Genetic algorithms for instruction sequencing and scheduling. In Workshop on Computer Architecture Technology and Formalism for Computer Science Research and Applications. Online elérhet˝o: http://citeseer.ist.psu.edu/16699.html és http://emess.mscd. edu/~beaty/Dossier/Papers/italy.pdf [Ellen˝orizve: 2007-07-29]. Bhaskar, V., Gupta, S. K. and Ray, A. (2000). Applications of multiobjective optimization in chemical engineering. Reviews in Chemical Engineering 16(1), 1–54. Birk, L., Clauss, G. F. and Lee, J. Y. (2004). Practical application of global optimization to the design of offshore structures. In Proceedings of OMAE04, 23rd International Conference on Offshore Mechanics and Arctic Engineering. OM AE2004-51225. Online elérhet˝o: http://130.149.35.79/downloads/ publikationen/2004/OMAE2004-51225.pdf [Ellen˝orizve: 2007-09-01]. Blickle, T. (1977). Anyag- és h˝oátadási rendszerek matematikai modelljei. M˝uszaki Könyvkiadó, Budapest. Borgulya, I. (2004). Evolúciós algoritmusok. Dialog Campus Kiadó BudapestPécs. Bosnyák, B. (2005). Egy agrárgazdaság dinamikus szimulációja. Diplomadolgozat, Kaposvári Egyetem.
117
Branke, J., Deb, K., Miettinen, K. and Slowinski, R. (Eds.) (2006). Practical Approaches to Multi-Objective Optimization, Number 06501 in Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany IBFI. Published in 2007. Online elérhet˝o: http://drops.dagstuhl. de/portals/index.php?semnr=06501 és http://www.dagstuhl.de/de/ programm/kalender/semhp/?semnr=06501
.
[Ellen˝orizve: 2007-09-19]
Branke, J., Deb, K., Miettinen, K. and Steuer, R. E. (Eds.) (2004). Practical Approaches to Multi-Objective Optimization, Number 04461 in Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany IBFI. Published in 2005. Online elérhet˝o: http://drops.dagstuhl. de/portals/index.php?semnr=04461 és http://www.dagstuhl.de/de/ programm/kalender/semhp/?semnr=04461
.
[Ellen˝orizve: 2007-09-19]
Branke, J., Deb, K., Miettinen, K. and Słowi´nski, R. (2008). Multiobjective optimization: Interactive and evolutionary approaches. Lecture Notes In Computer Science; Vol. 5252. Bánkuti, G. and Csukás, B. (2003). Egy hibrid automata kétréteg˝u háló modellje. Acta Agraria Kaposváriensis 7(3), 87–94. Bóity, O. (2001). Dinamikus szimuláción alapuló logisztikai modellek alkalmazása a mez˝ogazdaságban. Diplomadolgozat, Kaposvári Egyetem. Cagnoni, A., Dobrzeniecki, A., Poli, R. and Yanch, J. (1999). Genetic algorithmbased interactive segmentation of 3D medical images. Image and Vision Computing 17(12), 881–895. Online elérhet˝o: http://citeseer.ist.psu. edu/cagnoni99genetic.html [Ellen˝orizve: 2007-07-29]. Carbonaro, A. and Maniezzo, V. (2003). The Ant Colony Optimization paradigm for combinatorial optimization. Natural Computing Series, 539–557. Cardon, A., Galinho, T. and Vacher, J.-P. (1999a). An agent based architecture for job-shop scheduling problem using the spirit of genetic algorithm. In 118
Proceedings of EUROGEN’99, pp. 12–19. In proceedings (Miettinen et al., 1999a). Online elérhet˝o: http://www.mit.jyu.fi/eurogen99/papers/ vacher12.ps [Ellen˝orizve: 2008-06-07]. Ceollo Coello, C. A. (1999a). A comprehensive survey of evolutionarybased multiobjective optimization techniques. Knowledge and Information Systems 1(3), 269–308. Online elérhet˝o: http:// www.lania.mx/~ccoello/EMOO/informationfinal.ps.gz és http:// citeseer.ist.psu.edu/coello98comprehensive.html
.
[Ellen˝orizve: 2007-08-25]
Chai, J. and Ma, S. (1998a). Robust epipolar geometry estimation using genetic algorithm. Pattern Recognition Letters 19(9), 829–838. Lásd még (Chai and Ma, 1998b). Online elérhet˝o: http://dx.doi.org/10.1016/ S0167-8655(98)00032-4 [Ellen˝orizve: 2008-03-22]. Chai, J. and Ma, S. (1998b). Robust epipolar geometry estimation using genetic algorithm. In R. T. Chin and T.-C. Pong (Eds.), ACCV, Proceedings of Computer Vision - ACCV’98, Third Asian Conference on Computer Vision, Volume I, Volume 1351 of Lecture Notes in Computer Science (LNCS), pp. 272–279. Springer. Lásd még (Chai and Ma, 1998a). Chankong, V. and Haimes, Y. Y. (1983). Multiobjective Decision Making Theory and Methodology. New York: North-Holland, Elsevier, Dover Publications. Charnes, A. and Cooper, W. (1957). Management models and industrial applications of linear programming. Management Science, 38–91. Charnes, A. and Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. New York: John Wiley & Sons Inc. Chawdry, P. K., Roy, R. and Pant, R. K. (Eds.) (1998). Soft Computing in Engineering Design and Manufacturing. Springer-Verlag. Részben online elérhet˝o: http://books.google.de/books?id=mxcP1mSjOlsC [Ellen˝orizve: 200806-07].
119
Cleveland, G. A. and Smith, S. F. (1989). Using genetic algorithms to schedule flow shop releases. In ICGA, Proceedings of the third International Conference on Genetic Algorithms, pp. 160–169. In proceedings (Schaffer, 1989). Coello Coello, C. (2002). Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer methods in applied mechanics and engineering 191(11-12), 1245–1287. Cohon, J. L. and Marks, D. H. (1975). A review and evaluation of multiobjective programming techniques. Water Resources Research 11(2), 208–220. Cordón, O., Herrera, F. and Sánchez, L. (1998). Evolutionary learning processes for data analysis in electrical engineering applications. In D. Quagliarella, J. Périaux, C. Poloni, and G. Winter (Eds.), Genetic Algorithms and Evolution Strategy in Engineering and Computer Science, pp. 205–224. Chichester: John Wiley and Sons. In collection (Miettinen et al., 1999a). Online elérhet˝o: http://citeseer.ist.psu.edu/64737.html és ftp://decsai.ugr.es/ pub/arai/tech_rep/ga-fl/eurogen97.ps.Z
[Ellen˝orizve: 2007-08-25]
.
Corne, D., Smith, G. and Oates, M. (2000). Telecommunications Optimization: Heuristic and Adaptive Computation Techniques. John Wiley & Sons, Inc. New York, NY, USA. Csukás, B. (2001). Akadémiai doktori értékezés kézirata. Csukás, B. and Balogh, S. (1993 - 1994). Preparatív kromatográfiás technológiák dinamikus szimulációja. Technical report, Richter Gedeon Vegyészeti Gyár Rt. Csukás, B. and Balogh, S. (1996b). Szakaszos polimerizációs reaktor fels˝o szint˝u irányítása és adatbázis kezelése. Technical report, Magyar Olaj és Gázipari Rt. Fejlesztési Kutatási Igazgatósága.
120
Csukás, B. and Balogh, S. (1997b). Szimulált mozgó ágyas kromatográfiás folyamatok dinamikus szimulációja. Technical report, Richter Gedeon Vegyészeti Gyár Rt. Csukás, B. and Balogh, S. (1998a). Adszorpciós/elúciós és preparatív kromatográfiás technológiák tervezési és üzemeltetési optimalizálása. Technical report, Richter Gedeon Vegyészeti Gyár Rt. Csukás, B. and Balogh, S. (1998 - 1999). Olajadalék intermedier kopolimer gyártási technológiák számítógéppel segített fejlesztése, tervezése és irányítása. Technical report, Mol Rt. Csukás, B. and Balogh, S. (2001 - 2009). Egy tipikus gyógyszeripari üzemcsarnok munkaegészségügyi és környezetvédelmi kockázatelemzésének mennyiségi vizsgálatát segít˝o szimulációs modell rendszer kidolgozása. Technical report, Richter Gedeon Vegyészeti Gyár Rt. Csukás, B. and Balogh, S. (2002). Új, hulladékszegény kromatográfiás eljárások bevezetése a gyógyszeriparban. NKFP-3A/047/2002 pályázat, (modell bázisú tervezés és irányítás) Richter Gedeon Vegyészeti Gyár Rt. Technical report, Veszprémi Egyetem, Kaposvári Egyetem. Csukás, B. and Balogh, S. (2005b). Metabolikus hálózatok generikus kétréteg˝u háló modelljének identifikálása. Technical report, Kaposvári Egyetem. Csukás, B., Balogh, S., Takátsy, T., Bóity, O., Guldin, G. and Tari, C. (2001). Mérnöki logisztika az üzemirányításban. MTA Agrárm˝uszaki Bizottságának Tanácskozása, Gödöll˝o január, 23–25. Csukás, B., Varga, M. and Balogh, S. (2005 - 2007b). Biokémiai folyamatok szimulációs modell segítségével történ˝o vizsgálata. Technical report, Richter Gedeon Vegyészeti Gyár Rt. Csukás, B., Varga, M. and Balogh, S. (2006). Fluidizációs granulálási technológiák adatainak elemzése. Technical report, Richter Gedeon Vegyészeti Gyár Rt. 121
Csukás, B., Varga, M. and Balogh, S. (2007a). Az enzimkoncentráció meghatározása az aktivitásmérés identifikált modellje alapján. Technical report, Kaposvári Egyetem. Csáki, Cs. (1969). Mez˝ogazdasági vállalati távlati tervezés matematikai programozással. In A nagyüzemi gazdálkodás kérdései. Akadémiai Kiadó Budapest. Csáki, Cs. and Varga, Gy. (1976). Vállalatfejlesztési tervek lineáris dinamikus modellje. In A nagyüzemi gazdálkodás kérdései. Akadémiai Kiadó Budapest. da Cunha, A. G. L. and Covas, J. A. C. G. (2002). RPSGAe - reduced pareto set genetic algorithm: a multiobjectiv algorithm with elistim: application to polymer extrusion. In X. Gandibleux, M. Sevaux, K. Sörensen, and V. T’kindt (Eds.), MOMH Workshop on Multiple Objective Metaheuristics. Poster on the joint PM2O-EU/ME meeting. Online elérhet˝o: http: //www2.lifl.fr/PM2O/Reunions/04112002/gaspar.pdf [Ellen˝orizve: 2007-09-21], slides available at http://webhost.ua.ac.be/eume/workshops/momh/ momh_gaspar_cunha.pdf [Ellen˝orizve: 2007-09-21]. Davis, L. (Ed.) (1991). Handbook of Genetic Algorithms. Thomson Publishing Group. Deb, K., Agrawal, S., Pratab, A. and Meyarivan, T. (2000). A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. In Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 849–858. In proceedings (Schoenauer et al., 2000). Online elérhet˝o: http://citeseer.ist.psu.edu/deb00fast.html [Ellen˝orizve: 2007-0728]. Deep, K. and Thakur, M. (2007a). A new crossover operator for real coded genetic algorithms. Applied Mathematics and Computation 188(1), 895–911. Deep, K. and Thakur, M. (2007b). A new mutation operator for real coded genetic algorithms. Applied Mathematics and Computation 193(1), 211–230.
122
Dorigo, M., Maniezzo, V. and Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics 26(1), 29–41. Online elérhet˝o: ftp:// iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf és http: //citeseer.ist.psu.edu/dorigo96ant.html
.
[Ellen˝orizve: 2007-08-05]
Dzemyda, G., Saltenis, V. and Zilinskas, A. (Eds.) (2002). Stochastic and Global Optimization. Nonconvex Optimization and Its Applications. Springer-Verlag GmbH. Eberhart, R. C. and Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS’95, pp. 39–43. IEEE Press. Ehrgott, M. and Gandibleux, X. (2002). Multiple Criteria Optimization–State of the Art Annotated Bibliographic Surveys, Volume 52 of Kluwera’s International Series in Operations Research and Management Science, pp. 16–18. Kluwer Academic Publishers, Norwell, MA. El-Fakihy, K., Yamaguchiz, H. and von Bochmann, G. (1999). A method and a genetic algorithm for deriving protocols for distributed applications with minimum communication cost. In Proceedings of Eleventh IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’99). Online elérhet˝o: http://citeseer.ist.psu.edu/ 430349.html és http://www-higashi.ist.osaka-u.ac.jp/~h-yamagu/ resource/pdcs99.pdf
.
[Ellen˝orizve: 2007-09-14]
Floudas, C. A. (Ed.) (1999). Deterministic Global Optimization: Theory, Methods and Applications, Volume 37 of Nonconvex Optimization and Its Applications. Springer-Verlag GmbH. Részben online elérhet˝o: http: //books.google.de/books?id=qZSpq27TsOcC [Ellen˝orizve: 2008-03-10]. Floudas, C. A. and Pardalos, P. M. (Eds.) (2003). Frontiers in Global Optimization. Nonconvex Optimization and Its Applications. Springer US.
123
Fogel, D. B. (Ed.) (1998). Evolutionary Computation: The Fossil Record. Wiley-IEEE Press. Fogel, L. J., Owens, A. J. and Walsh, M. J. (1966). Artificial Intelligence through Simulated Evolution. New York, USA: John Wiley & Sons. Fonseca, C. M. and Fleming, P. J. (1993). Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In Proceedings of the 5th International Conferenceo on Genetic Algorithms, pp. 416–423. In proceedings (Forrest, 1993). Online elérhet˝o: http://citeseer.ist. psu.edu/fonseca93genetic.html és http://www.lania.mx/~ccoello/ EMOO/fonseca93.ps.gz
.
[Ellen˝orizve: 2007-08-29]
Fonseca, C. M. and Fleming, P. J. (1998a). Multiobjective optimization and multiple constraint handling with evolutionary algorithms – part i: A unified formulation. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans 28(1), 26–37. Online elérhet˝o: http://citeseer. ist.psu.edu/fonseca98multiobjective.html [Ellen˝orizve: 2007-07-29]. Lásd még (Fonseca and Fleming, 1998b). Fonseca, C. M. and Fleming, P. J. (1998b). Multiobjective optimization and multiple constraint handling with evolutionary algorithms – part ii: Application example. IEEE Transactions on Systems, Man, and Cybernetics, Part A 28(1), 38–47. Online elérhet˝o: http://citeseer.ist.psu.edu/ 27937.html [Ellen˝orizve: 2007-09-19]. Lásd még (Fonseca and Fleming, 1998a). Forrest, S. (Ed.) (1993). Proceedings of the 5th International Conference on Genetic Algorithms, San Francisco, CA. Morgan Kaufmann. Galperin, E. A. and Kansa, E. J. (2002). Application of global optimization and radial basis functions to numerical solutions of weakly singular volterra integral equations. Computers & Mathematics with Applications 43(3-5), 491– 499. Online elérhet˝o: http://dx.doi.org/10.1016/S0898-1221(01) 00300-5 [Ellen˝orizve: 2007-09-01].
124
Gass, S. and Saaty, T. (1955). The computational algorithm for the parametric objective function. Naval Research Logistics Quarterly 2. Giannakoglou, K. C., Tsahalis, D. T., Périaux, J., Papailiou, K. D. and Fogarty, T. (Eds.) (2001). Proceedings of the EUROGEN2001 Conference: Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems. International Center for Numerical Methods in Engineering (Cmine), Gran Capitan s/n, 08034 Barcelona, Spain. Published in 2002. Lásd: http://www.mech.ntua.gr/~eurogen2001 [Ellen˝orizve: 2007-09-16]. Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533–549. Online elérhet˝o: http://dx.doi.org/10.1016/0305-0548(86)90048-1 [Ellen˝orizve: 2008-03-27]. Goldberg, D. and Lingle, R. (1985). Alleles Loci and the Traveling Salesman Problem. In Proceedings of the 1st International Conference on Genetic Algorithms table of contents, pp. 154–159. L. Erlbaum Associates Inc. Hillsdale, NJ, USA. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning (First ed.). Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA. Gonzalez, T. (2007). Handbook of approximation algorithms and metaheuristics. Chapman & Hall/CRC. Grefenstette, J. J. (Ed.) (1985). Proceedings of the 1st International Conference on Genetic Algorithms and their Applications, Mahwah, NJ, USA. Lawrence Erlbaum Associates, Inc. Grefenstette, J. J. (Ed.) (1987). Proceedings of the 2nd International Conference on Genetic Algorithms and their Applications, Mahwah, NJ, USA. Lawrence Erlbaum Associates, Inc.
125
Guba, M., Papp, Zs. and Varga, Gy. (1977). A sz˝ol˝oszüret gépesítésének vállalatgazdasági kérdései. In A nagyüzemi gazdálkodás kérdései. Akadémiai Kiadó Budapest. Guldin, G. (2001). Csatolt növénytermesztési és állattenyésztési rendszer szimulációval segített elemzése és fejlesztése. Diplomadolgozat, Kaposvári Egyetem. Haimes, Y. Y., Hall, W. and Freedman, H. T. (1975). Multiobjective Optimization in Water Resource Systems. New York: Elsevier. ASIN: B000UUMGXE. Haimes, Y. Y. and Steuer, R. E. (Eds.) (1998). Proceedings of the 14th International Conference on Multiple Criteria Decision Making: Research and Practice in Multi Criteria Decision Making (MCDM’1998), Volume 487 of Lecture Notes in Economics and Mathematical Systems. Springer. See http: //www.virginia.edu/~risk/mcdm98.html [Ellen˝orizve: 2007-09-10]. Published June 15, 2000. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press. Reprinted by MIT Press, April 1992. Hurwicz, L. (1958). Programming in linear spaces. Stanford university press. Jerrell, M. (2000). Applications of public global optimization software to difficult econometric functions. In Computing in Economics and Finance 200. Society for Computational Economics. Number 161. Online elérhet˝o: http://econpapers.repec.org/paper/scescecf0/161.htm
[Ellen˝orizve: 2007-
.
09-01]
Kamrani, A., Rong, W. and Gonzalez, R. (2001). A genetic algorithm methodology for data mining and intelligent knowledge acquisition. Computers & Industrial Engineering 40(4), 361–377. Kennedy, J. and Eberhart, R. C. (1995). Particle swarm optimization. In Proceedings of IEEE International Conference on Neural Networks, 1995, Volume 4, pp. 1942–1948. Online elérhet˝o: http://www.engr.iupui.edu/ ~shi/Coference/psopap4.html [Ellen˝orizve: 2007-08-21]. 126
Kindler, J. (1991). Fejezetek a dönteselméletb˝ol. AULA, Budapest. Kirkpatrick, S., Gelatt, Jr., C. D. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science 220(4598), 671–680. Online elérhet˝o: http: //fezzik.ucd.ie/msc/cscs/ga/kirkpatrick83optimization.pdf
és
http://citeseer.ist.psu.edu/kirkpatrick83optimization.html
.
[Ellen˝orizve: 2008-03-26]
Knowles, J. D. and Corne, D. W. (2003). Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Transactions on Evolutionary Computation 7, 100–116. Koopmans, T. (1951). Analysis of production as an efficient combination of activities. Number 13. New York Wiley and Sons. Koza, J. R. (1989). Hierarchical genetic algorithms operating on populations of computer programs. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, pp. 768–774. In proceedings (Sridharan, 1989a). Részben online elérhet˝o: http://dli.iiit.ac.in/ ijcai/IJCAI-89-VOL1/PDF/123.pdf [Ellen˝orizve: 2008-05-29]. Koza, J. R. (1992b). Non-Linear Genetic Algorithms for Solving Problems by Finding a Fit Composition of Functions. United States Patent and Trademark Office. United States Patent 5,136,686. Filed March 28, 1990, Issued August 4, 1992. Kuhn, H. W. and Tucker, A. W. (1951). Nonlinear programming. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pp. 481–492. Berkeley, California. Kukkonen, S. and Deb, K. (2006). A fast and effective method for pruning of non-dominated solutions in many-objective problems. Lecture Notes in Computer Science 4193, 553. Kundu, S., Seto, K. and Sugino, S. (2002). Genetic algorithm application to vibration control of tall flexible structures. In Proceedings of The First 127
IEEE International Workshop on Electronic Design, Test and Applications (DELTA’02), Los Alamitos, CA, USA, pp. 333–337. IEEE Computer Society. Langdon, W. B. (1998). Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming! Genetic Programming. Springer. Leh˝ocz, G. (2005). Lokális gazdasági döntéseken alapuló szimulációs módszer vizsgálata egy egyszer˝usített takarmánykever˝o rendszer példáján. Diplomadolgozat, Kaposvári Egyetem. Leh˝ocz, G., Balogh, S., Bánkuti, G. and Csukás, B. (2005). Gazdasági potenciál számításon alapuló lokális döntéseket támogató algoritmusok fejlesztése. Informatika a Fels˝ooktatásban’Konferencia, Debrecen, 24–26. Levine, D. (1996). Application of a hybrid genetic algorithm to airline crew scheduling. Computers & Operations Research 23(6), 547–558. Online elérhet˝o: http://www.citeulike.org/user/ilapla/article/1443054 és http://citeseer.ist.psu.edu/178394.html [Ellen˝orizve: 2007-07-29]. Lohn, J. D. and Colombano, S. P. (1999). A circuit representation technique for automated circuit design. IEEE Transactions on Evolutionary Computation (IEEE-EC) 3(3), 205. Online elérhet˝o: http://ic.arc. nasa.gov/people/jlohn/bio.html és http://citeseer.ist.psu.edu/ lohn99circuit.html
.
[Ellen˝orizve: 2007-08-07]
Lohn, J. D., Haith, G. L., Colombano, S. P. and Stassinopoulos, D. (2000). Towards evolving electronic circuits for autonomous space applications. In Proceedings of the 2000 IEEE Aerospace Conference. Online elérhet˝o: http://ic.arc.nasa.gov/people/jlohn/bio.html és http:// citeseer.ist.psu.edu/336276.html [Ellen˝orizve: 2007-08-07]. Lukács, A., Takátsy, T., Csukás, B. and Balogh, S. (2001). Baromfiistálló energetikai és makroszint˝u metabolikus szimulációjának tapasztalatai. M˝uszaki Kémiai Napok’ Veszprém, 248–253.
128
Männer, R. and Manderick, B. (Eds.) (1992). Proceedings of Parallel Problem Solving from Nature 2, PPSN II. Elsevier. See http://ls11-www. informatik.uni-dortmund.de/PPSN/ppsn2/ppsn2.html [Ellen˝orizve: 2007-09-05]. Meza, J. C. and Martinez, M. L. (1994). On the use of direct search methods for the molecular conformation problem. Journal of Computational Chemistry 15(6), 627–632. Online elérhet˝o: http://crd.lbl.gov/~meza/ papers/jcc.pdf [Ellen˝orizve: 2008-06-14]. Miettinen, K., Mäkelä, M. M., Neittaanmäki, P. and Periaux, J. (Eds.) (1999a). European Short Course on Genetic Algorithms and Evolution Strategies, Proceedings of EUROGEN 1999. Neumaier, A. (2006). Global optimization and constraint satisfaction. In I. Bomze, I. Emiris, A. Neumaier, and L. Wolsey (Eds.), Proceedings of GICOLAG workshop (of the research project Global Optimization, Integrating Convexity, Optimization, Logic Programming and Computational Algebraic Geometry). Online elérhet˝o: http://www.mat.univie.ac.at/~neum/glopt.html [Ellen˝orizve: 2007-07-12]. Neumann, J. V. (1928). Zur theorie der gesellschaftsspiele. Mathematische Annalen 100(1), 295–320. Neumann, J. V. and Morgenstern, O. (1944). Theory of games and economic behavior. Princeton University Press. Pareto, V. (1912). Manuel d’economie politique. Bull. Amer. Math. Soc. 18 (1912), 462-474. DOI: 10.1090/S0002-9904-1912-02237-1 PII: S 2(9904), 02237–1. ønlineAvailablehttp://www.ams.org/bull/1912-18-09/S0002-99041912-02237-1/home.html2009-01-22. Perkins, J. and Kumark, P. (1989). Stable, distributed, real-time scheduling of flexiblemanufacturing/assembly/diassembly systems. IEEE Transactions on Automatic Control 34(2), 139–148.
129
Radcliffe, N. J. (1992). Non-linear genetic representations. In Parallel problem solving from nature 2, pp. 259–268. In proceedings (Männer and Manderick, 1992). Online elérhet˝o: http://citeseer.ist.psu. edu/radcliffe92nonlinear.html és http://users.breathe.com/njr/ papers/ppsn92.pdf
.
[Ellen˝orizve: 2007-09-05]
Rechenberg, I. (1965). Cybernetic Solution Path of an Experimental Problem. Royal Aircraft Establishment. Library Translation 1122, Farnborough. Reprinted in Fogel (1998). Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart. his dissertation from 1970. Sahinidis, N. V. and Tawarmalani, M. (2000). Applications of global optimization to process and molecular design. Computers and Chemical Engineering 24(9-10), 2157–2169. Online elérhet˝o: http://citeseer.ist. psu.edu/397733.html [Ellen˝orizve: 2007-09-01]. Satoh, T., Ishihara, T. and Inooka, H. (1996). Systematic design via the method of inequalities. Control Systems Magazine, IEEE 16(5), 57–65. Schaffer, J. D. (1984). Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. Ph. D. thesis, Vanderbilt University. Schaffer, J. D. (Ed.) (1989). Proceedings of the 3rd International Conference on Genetic Algorithms, San Francisco, CA. Morgan Kaufmann. Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Guervós, J. J. M. and Schwefel, H.-P. (Eds.) (2000). Proceedings of the 6th International Conference on Parallel Problem Solving from Nature – PPSN VI, Volume 1917/2000 of Lecture Notes in Computer Science (LNCS). Springer. Sharples, N. P. (2001). Evolutionary Approaches to Adaptive Protocol Design. Ph. D. thesis, School of Cognitive & Computing Sciences of the University of Sussex. ASIN: B001ABO1DK. 130
Smigrodzki, R., Goertzel, B., Pennachin, C., Coelho, L., Prosdocimi, F. and Parker Jr., W. D. (2005). Genetic algorithm for analysis of mutations in parkinson’s disease. Artificial Intelligence in Medicine 35, 227–241. Online elérhet˝o: http://dx.doi.org/10.1016/j.artmed.2004.11.006 [Ellen˝orizve: 2007-08-05]. Sridharan, N. S. (Ed.) (1989a). Proceedings of the 11th International Joint Conference on Artificial Intelligence, Volume 1. Morgan Kaufmann, San Francisco, CA, USA. Online elérhet˝o: http://dli.iiit.ac.in/ijcai/ IJCAI-89-VOL1/CONTENT/content.htm [Ellen˝orizve: 2008-04-01]. Lásd még (Sridharan, 1989b). Sridharan, N. S. (Ed.) (1989b). Proceedings of the 11th International Joint Conference on Artificial Intelligence, Volume 2. Morgan Kaufmann, San Francisco, CA, USA. Online elérhet˝o: http://dli.iiit.ac.in/ ijcai/IJCAI-89-VOL2/CONTENT/content.htm [Ellen˝orizve: 2008-04-01]. Lásd még (Sridharan, 1989a). Stadler, W. (1986). Initiators of Multicriteria Optimization. Jahn, J. and W. Krabs, editors, Recent Advances and Historical Development of Vector Optimization, 3–47. Steuer, R. E. (1989). Multiple Criteria Optimization: Theory, Computation and Application (Reprint ed.). Krieger Pub Co. Stickland, T. R., Tofts, C. M. N. and Franks, N. R. (1992). A path choice algorithm for ants. Naturwissenschaften 79(12), 567–572. Online elérhet˝o: http://www.springerlink.com/content/v2t8328844843l56/ fulltext.pdf [Ellen˝orizve: 2008-06-12]. Szente, P. (2007). Szállítási feladat dinamikus szimuláción alapuló ütemezése. Diplomadolgozat, Kaposvári Egyetem. Takátsy, T., Csukás, B. and Balogh, S. (2000). Az állat és környezete kapcsolatának dinamikus szimulációja. M˝uszaki Kémiai Napok’ Veszprém, 22–28. 131
Takátsy, T., Csukás, B., Balogh, S. and I., L. A. (2001). Az állati metabolizmus makroszint˝u dinamikus szimulációja mérnöki alkalmazásokra. MTA Agrárm˝uszaki Bizottságának Tanácskozása, Gödöll˝o január, 23–25. Temesi, J. (2002). A döntéselmélet alapjai. AULA, Budapest. Temesvári, K., Aranyi, A., Balogh, S., Bánkuti, G. and Csukás, B. (2005). Computer-aided process design of the separation of a two-component steroid mixture by simulated moving bed technique. J. Ind. Chem. Hung. 32, 5–12. Temesvári, K., Aranyi, A., Balogh, S. and Csukás, B. (2004). Simulated moving bed separation of a two components steroid mixture. Tsao, C.-H. and Chern, J.-L. (2006). Application of a global optimization process to the design of pickup heads for compact and digital versatile disks. Optical Engineering 45(10), 103001. Udovecz, G. (1982). A harmonikus fejl˝odés f˝obb kérdései az élelmiszertermelésben. In A nagyüzemi gazdálkodás kérdései. Akadémiai Kiadó Budapest. Van Veldhuizen, D. A., Zydallis, J. B. and Lamont, G. B. (2002). Issues in parallelizing multiobjective evolutionary algorithms for real world applications. In SAC’02: Proceedings of the 2002 ACM symposium on Applied computing, New York, NY, USA, pp. 595–602. ACM Press. Online elérhet˝o: http://doi.acm.org/10.1145/508791.508906 [Ellen˝orizve: 2007-08-14]. Varga, M. (2005). Fiktív vállalkozás részletes kétréteg˝u hálómodell alapú adószámítási eredményeinek optimalizálása. Diplomadolgozat, Kaposvári Egyetem. Varga, M. (2006). Pontozásos (pályázat) rangsorolás továbbfejlesztése az utólagos értékelés-visszacsatolás elvvel. Acta Agraria Kaposváriensis 10(3), 315–319. Varga, M. (2009). Mellékter méket hasznosító komplex körfolyamat gazdasági optimalizálása. Ph. D. thesis, Kaposvári Egyetem. 132
Veizer, A. (2005). Enzimreakciók dinamikus szimulációja. Diplomadolgozat, Kaposvári Egyetem. Veizer, A., Bánkuti, G., Balogh, S. and Csukás, B. (2005). Metabolikus hálózatok generikus kétréteg˝u háló modelljének identifikálása. Informatika a Fels˝ooktatásban’Konferencia, Debrecen, 24–26. Wetzel, A. (1983). Evaluation of the Effectiveness of Genetic Algorithms in Combinatorial Optimization. Ph. D. thesis, University of Pittsburgh, Pittsburgh, PA. Unpublished manuscript, technical report. Wolpert, D. H. and Macready, W. G. (1995). No free lunch theorems for search. Technical Report SFI-TR-95-02-010, The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, 87501, USA. Online elérhet˝o: http: //citeseer.ist.psu.edu/wolpert95no.html és http://www.santafe. edu/research/publications/workingpapers/95-02-010.pdf
[Ellen˝orizve:
.
2008-03-28]
Wolpert, D. H. and Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1(1), 67– 82. Online elérhet˝o: http://citeseer.ist.psu.edu/wolpert96no.html [Ellen˝orizve: 2008-03-28]. Xiao, Y. L. and Williams, D. E. (1994). Game: Genetic algorithm for minimization of energy, an interactive program for three-dimensional intermolecular interactions. Computers & Chemistry 18(2), 199–201. Yuret, D. and Maza, M. (1994). A genetic algorithm system for predicting the oex. Technical Analysis of Stocks & Commodities, 58–64. Online elérhet˝o: http://www.denizyuret.com/pub/tasc94.ps.gz és http: //citeseer.ist.psu.edu/yuret94genetic.html [Ellen˝orizve: 2007-08-24]. Zadeh, L. (1963). Optimality and non-scalar-valued performance criteria. IEEE Transactions on Automatic Control 8(1), 59–60. Zala, G. (2005). Szállítási feladat kétréteg˝u hálóalapú dinamikus szimulációja. Diplomadolgozat, Kaposvári Egyetem. 133
Zitzler, E. and Kunzli, S. (2004). Indicator-based selection in multiobjective search. Lecture notes in computer science, 832–842. Zitzler, E., Laumanns, M. and Thiele, L. (2001a). SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland. Online elérhet˝o: http://www.tik.ee.ethz.ch/sop/ publicationListFiles/zlt2001a.pdf és http://citeseer.ist.psu. edu/514031.html
.
[Ellen˝orizve: 2007-07-29]
Zitzler, E., Laumanns, M. and Thiele, L. (2001b). SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. In Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems. Proceedings of the EUROGEN2001 Conference, pp. 95–100. In proceedings (Giannakoglou et al., 2001). Online elérhet˝o: http://citeseer.ist.psu.edu/514031.html és http: //de.scientificcommons.org/526554 [Ellen˝orizve: 2007-07-29].
134
A DISSZERTÁCIÓ ˝ MEGJELENT TÉMAKÖRÉBOL PUBLIKÁCIÓK
Idegen nyelven teljes terjedelemben megjelen˝o közlemény: Aranyi, A., Temesvári, K., Csukás, B. and Balogh, S. (1998). Computer assisted design of industrial scale chromatographic separation. SPICA Strassbourg, 152–157. Balogh, S. (2009). Multicriteria decision support by genetic algorithm. Regional and Business Studies (under submitting). Csukas, B. and Balogh, S. (2001). Evolutionary synthesis of almost closed conservational processes. Gani and S. B. Jorgensen Eds., European Symposium on Computer Aided Process Engineering , Computer Aided Process Engineering, Elsevier 9, 381–386. Csukás, B. and Balogh, S. (1996). Combining genetic programming with generic simulation models in evolutionary synthesis. In, Bertrand, Jafari, Fransoo, Rutten Eds, 158–172. Csukás, B. and Balogh, S. (1998). Combining genetic programming with generic simulation models in evolutionary synthesis. Computers in Industry 36, 181–197. Csukás, B., Balogh, S. and Bánkuti, G. (2005). Generic bi-layered net model – general software for simulation of hybrid processes, in, daoliang li and Íbaoji wang eds., artificial intelligence applications and innovations ii. 2nd ifip conference of tc12 wg 12.5, springer. pp., 700–710. Csukás, B., Balogh, S., Kováts, S., Aranyi, A., Kocsis, Z. and Bartha, L. (1999). Process design by controlled simulation of the executable structural models. Comput. Chem. Engng. 23, 569–572. Csukás, B., Balogh, S. and Structures, E. (1997). Evaluation feedback between the generic simulation and the genetic synthesis. Joint Conf. of Information Systems, 1–5.
136
Csukás, B., Lakner, R., Varga, K. and Balogh, S. (1996). Combining genetic programming with generic simulation models in evolutionary synthesis. Comput. Chem. Engng. 20, 61–66. Temesvári, K., Aranyi, A., Balogh, S., Bánkuti, G. and Csukás, B. (2005). Computer-aided process design of the separation of a two-component steroid mixture by simulated moving bed technique. J. Ind. Chem. Hung. 32, 5–12. Temesvári, K., Aranyi, A., Balogh, S. and Csukás, B. (2004). Simulated moving bed separation of a two components steroid mixture. Magyar nyelven teljes terjedelemben megjelen˝o közlemény: Balogh, S., Csukás, B., Bartha, L., Kocsis, Z. and Kis, G. (2000). Szakaszos polimerizációs recept fejlesztése genetikus algoritmussal összekapcsolt dinamikus szimulátorral. M˝uszaki Kémiai Napok’ Veszprém, 36–40. Balogh, S., Csukás, B., Sógor, A., Budai, M. and Miklósi, M. (2004). Egy soktermékes üzemcsarnok oldószer szennyez˝odésének szimulációs vizsgálata. Acta Agraria Kaposvariensis 8(3). Balogh, S., Csukás, B., Takátsy, T. and Tari, C. (2000). Többérdek˝u logisztikai láncok fejlesztése genetikus algoritmussal összekapcsolt dinamikus szimulátorral. M˝uszaki Kémiai Napok’ Veszprém, 41–45. Balogh, S., Négyesi, G., Budai, M., Sógor, A. and Csukás, B. (2003). Szakaszos üzemcsarnok légtér szennyezettségének mérése és dinamikus szimulációja. M˝uszaki Kémiai Napok’ Veszprém, 284–290. Boity, O., Gudlin, G., Tari, C., Balogh, S., Csukás, B. and Takátsy, T. (2001). Kisérlet egy farmgazdálkodást segít˝o genetikus algoritmussal fejlesztett szimulátor kialakítására. M˝uszaki Kémiai Napok’ Veszprém, 242–247. Csukás, B. and Balogh, S. (2001). Egy konfigurálható, generikus, dinamikus szimulátor és újabb alkalmazási lehet˝oségei. M˝uszaki Kémiai Napok’ Veszprém, 45–50. 137
Kis, G., Csukás, B., Bartha, L., Kocsis, Z. and Balogh, S. (2000). Szakaszos polimerizációs m˝uvelet számítógéppel segített recept fejlesztése. M˝uszaki Kémiai Napok’ Veszprém, 29–51. Lukács, A., Takátsy, T., Csukás, B. and Balogh, S. (2001). Baromfiistálló energetikai és makroszint˝u metabolikus szimulációjának tapasztalatai. M˝uszaki Kémiai Napok’ Veszprém, 248–253. Takátsy, T., Csukás, B. and Balogh, S. (2000). Az állat és környezete kapcsolatának dinamikus szimulációja. M˝uszaki Kémiai Napok’ Veszprém, 22–28. Temesvári, K., Aranyi, A., Balogh, S., Bánkuti, G. and Csukás, B. (2004). Kétkomponens˝u szteroid elegy szimulált mozgó ágyas (smb) elválasztásának számítógéppel segített tervezése. Acta Agraria Kaposvariensis 8(3). El˝oadások: Aranyi, A., Csukás, B., Temesvári, K. and Balogh, S. (1997). Structural model based dynamic simulation of preparative hplc. International Symposium on Chromatography, Balatonszéplak, September, 3–5. Balogh, S. (2006). A genetikus algoritmussal kapcsolt generikus szimulátor szoftver implementációjának fejlesztése. V. Alkalmazott Informatika Konferencia. Balogh, S. and Csukás, B. (1995). A makroszint˝u modell, mint a mikro szint˝u modell genetikus kódja - a nem string típusú genetikus kód lehet˝oségei és korlátai. M˝uszaki Kémiai Napok’, 89–90. Balogh, S. and Csukás, B. (1996). Számítógéppel segített folyamattervezés a részletes modellel generált és értékelt genetikus algoritmussal. M˝uszaki Kémiai Napok’, 37–38. Balogh, S. and Csukás, B. (1997). Esettanulmány dinamikus szimuláció és genetikus algoritmus összekapcsolására. M˝uszaki Kémiai Napok’, 141–142. 138
Balogh, S. and Csukás, B. (1998). A genetikus programozás lehet˝oségei a folyamatmérnöki munkában. M˝uszaki Kémiai Napok’, 5–6. Balogh, S. and Csukás, B. (2001). A generikus szimulátorral visszacsatolt kapcsolatban m˝uköd˝o genetikus algoritmus és újabb alkalmazási lehet˝oségei. M˝uszaki Kémiai Napok’ Veszprém, 206–209. Balogh, S., Lakner, P. R. and Csukás, B. (1994). Többszempontú genetikus algoritmusok vizsgálata. M˝uszaki Kémiai Napok’, 26–28. Balogh, S., Négyesi, G., Budai, M., Sógor, A. and Csukás, B. (2003). Szakaszos üzemcsarnok légtér szennyezettségének mérése és dinamikus szimulációja. M˝uszaki Kémiai Napok’ Veszprém, 284–290. Barthó, I., Sinkó, B. I., Hantos, G., Balogh, S., Csukás, B. and Varga, M. (2006). Bioreaktor modelljének identifikálása és egy biokonverziós folyamat modell bázisú fejlesztése. Kaposvár május 26: V. Alkalmazott Informatika Konferencia. Csukás, B. and Balogh, S. (1998). Megmaradási folyamatok strukturális modelljének közvetlen leképezése végrehajtható program érték˝u adatbázisra. M˝uszaki Kémiai Napok’, 54–55. Csukás, B., Balogh, S., Takátsy, T., Bóity, O., Guldin, G. and Tari, C. (2001). Mérnöki logisztika az üzemirányításban. MTA Agrárm˝uszaki Bizottságának Tanácskozása, Gödöll˝o január, 23–25. Csukás, B., Debelak, K. A., Prokop, A., Balcarcel, R. R., Tanner, R. D., Bánkuti, G. and Balogh, S. (2003). Generic Bi-layered Net Model Based Discrimination of Chemical and Biological Warfare Agents, AIChE Annual Meeting, San Francisco, November 16-20. Manuscript 474f. Csukás, B., Kováts, S., Aranyi, A., Temesvári, T.-K. and Balogh, S. (1997). A valódi és szimulált mozgó ágyas folyamatos üzem˝u preparatív kromatográfia szimulációjának tapasztalatai. M˝uszaki Kémiai Napok’, 100–101.
139
Domonkos, D., Könczöl, K., Balogh, S., Csukás, B. and Varga, M. (2006). Rekombináns fehérje szintézis számítógépi modellen alapuló fejlesztésének lehet˝oségei. Katona, A., Balogh, S. and Csukás, B. (2006). A generikus kétréteg˝u háló modell fpga bázisú hardver implementációjának lehet˝oségei. Leh˝ocz, G., Balogh, S., Bánkuti, G. and Csukás, B. (2005). Gazdasági potenciál számításon alapuló lokális döntéseket támogató algoritmusok fejlesztése. Informatika a Fels˝ooktatásban’Konferencia, Debrecen, 24–26. Nagy, K., Csukás, B., Kis, G., Bartha, L. and Balogh, S. (2001). Study on preparation and properties of olefin-maleic-anhydride copolymers. 40th international petroleum conference. September, 17–19. Nagy, K., Kis, G., Bartha, L., Csukás, B. and Balogh, S. (2001). Olefin - maleinsavanhidrid kopoli-merek el˝oállítási körülményeinek és tulajdonságainak vizsgálata. M˝uszaki Kémiai Napok’ Veszprém, 24–26. Takátsy, T., Csukás, B., Balogh, S. and I., L. A. (2001). Az állati metabolizmus makroszint˝u dinamikus szimulációja mérnöki alkalmazásokra. MTA Agrárm˝uszaki Bizottságának Tanácskozása, Gödöll˝o január, 23–25. Temesvári, K., Aranyi, A., Csukás, B. and Balogh, S. (2001). Kisérletek és szimulációs vizsgálatok egy királis elválasztás szimulált mozgó ágyas megvalósíthatóságának elemzéséhez. M˝uszaki Kémiai Napok’ Veszprém, 24–26. Temesvári, K., Aranyi, A., Csukás, B. and Balogh, S. (2003). Simulated moving bed separation of a two components steroid mixture. International Symposium on Chromatography, Balatonszéplak, September, 4–6. Temesvári, T.-K., Csukás, B. and Aranyi, A. (1997). Determination of the equilibrium, hydrodynamic and kinetic parameters for the structural modeling of preparative hplc. International Symposium on Chromatography, Balatonszéplak, September, 3–5. 140
Varga, M., Bíró, B. B., Kitanics, B. T., Bánkuti, G. and Csukás, B. (2005). Vállalkozók adózási stratégiáinak szimulációja generikus kétréteg˝u háló modellel. Informatika a Fels˝ooktatásban’Konferencia, Debrecen, 24–26. Veizer, A., Bánkuti, G., Balogh, S. and Csukás, B. (2005). Metabolikus hálózatok generikus kétréteg˝u háló modelljének identifikálása. Informatika a Fels˝ooktatásban’Konferencia, Debrecen, 24–26.
141
RÖVID SZAKMAI ÉLETRAJZ
BALOGH SÁNDOR tudományos segédmunkatárs Kaposvári Egyetem, Gazdaságtudományi Kar, Informatika Tanszék, 7400 Kaposvár, Guba S. u. 40. Telefon: (82) 505-960, Fax: (82) 505-953, E-mail:
[email protected] Születési hely, id˝o: Eger, 1967. október 11. Fels˝ofokú tanulmányai: Veszprémi Egyetem (1993), szervez˝o vegyészmérnök Nyelvismeret: angol, orosz Munkahelyek: Veszprémi Egyetem (1993–1994), Kibernetika tanszék, ösztöndíjas; Veszprémi Egyetem (1994–1996), Informatika tanszék, ösztöndíjas; Magyar Tudományos Akadémia M˝uszaki Kémiai Kutató Intézet (1996–1999), ösztöndíjas; Pannon Agrártudományi Egyetem M˝uszaki Kémiai Kutató Intézet (1999–2000), tudományos munkatárs; Kaposvári Egyetem, M˝uszaki Kémiai Kutató Intézet (2000–2004), tudományos munkatárs; Kaposvári Egyetem, Informatika Tanszék (2004–), tudományos segédmunkatárs. Tudományos társasági, szervezeti tagság: MTA Veszprémi Akadémiai Bizottság Rendszerszerkezeti munkabizottság (1995–), tag Nemzetközi együttmuködések: ˝ részvétel a Vanderbilt Egyetemmel (Nashville, TN) közös pályázatok kidolgozásában. Fontosabb kutatási megbízások: Részvétel 6 OTKA pályázat, 1 NKFP pályázat, és az elmúlt 10 évben mintegy 18 ipari megbízásos munka, valamint egy GVOP/TST projekt kidolgozásában. Publikáció: 11 idegen nyelven teljes terjedelemben megjelen˝o közlemény, 10 magyar nyelven teljes terjedelemben megjelen˝o közlemény, 25 el˝oadás.
143