Szolnoki Tudományos Közlemények XV. Szolnok, 2011.
Oláh Béla1
GENETIKUS OPERÁTOROK ÉRZÉKENYSÉGVIZSGÁLATA Jelen tudományos munka célkitűzése egy általam már korábban elkészített és publikált permutáció flow-shop termelésütemezési feladatokat (FSSP) megoldó genetikus algoritmus (GA) keresztező és mutáció operátorainak érzékenységvizsgálata. Dolgozatom az algoritmus által használt különböző keresztező operátorok, mint a CycleCrossover (CX) és az Order-Crossover (OX), valamint négy különböző mutáció operátor (reciprocal exchange, simple inversion, swap és displacement) összehasonlítására terjed ki a megoldások optimum-közeli hatékonyságának függvényében. Megvizsgálom, hogy az egyes keresztező és mutációs eljárások alkalmazásával hogyan változik a program teljesítménye, értékelem a kapott eredményeket és összefüggéseket keresek, melyek segítségével a genetikus algoritmus hatékonyabb alkalmazása lehetséges. Témaválasztásom gyakorlati jelentőségű eredménye annak kiderítése lesz, hogy melyik keresztező és mutáció operátort érdemes használni, a minél hamarabbi és minél inkább optimum-közeli megoldások szolgáltatása végett. SENSITIVITY ANALYSIS OF GENETIC OPERATORS The main goal of this scientific work is the sensitivity analysis of crossover and mutation operators of my own genetic algorithm (GA) for the permutation flow-shop scheduling problems (FSSP). This paper covers the comparison of the different crossover operators such as Cycle-Crossover (CX) and Order-Crossover (OX), as well as four different mutation operators (reciprocal exchange, simple inversion, swap and displacement) used by the algorithm in function of the efficiency of the near optimal solutions. I analyze how the efficiency of the algorithm changes used by each crossover and mutation operator, I evaluate the obtained results and I search for relations that help to apply the GA more effectively and efficiently. The practical importance of my research results is to determine which crossover and mutation operators have to be used in order to supply near optimal solutions at the fastest possible time.
A FLOW-SHOP ÜTEMEZÉSI PROBLÉMA MEGFOGALMAZÁSA Adott n számú termék, amelyeken m számú különböző munkafolyamatot kell elvégezni. A technológiai útvonal, ami az összes termékre nézve azonos, valamint a műveleti idők előre adottak. Meg kell határozni a termékeknek azt a sorrendjét a gépeken, amely bizonyos előre megadott szempontok szerint optimális (1. ábra).
1
Szolnoki Főiskola, Műszaki és Agrárgazdálkodási Intézet, Műszaki és Gépészeti Tanszék, főiskolai tanársegéd, Email:
[email protected] A cikket lektorálta: Dr. Vermes Pál Szolnoki Főiskola, főiskolai tanár, PhD.
gép
A
állás idők p1
p2
p1
B
p3
p4
p2
p3
p1
C
p2
p1
D
p5
holtidők p4
p5
p3
p4
p2
p5
p3
p4
p5 idő
átfutási idő
1. ábra. Egy permutáció flow-shop ütemezés Gantt-diagramja
Ilyen a gyakorlatban is használt logisztikai célfüggvények az alábbiak lehetnek: minimális átfutási idő; technológiai berendezések maximális kihasználása (holtidők minimálása); minimális gyártásközi készletek (termékek állásidejének minimálása).
A GENETIKUS ALGORITMUS ISMERTETÉSE A genetikus algoritmusok fogalmát először Holland [5] vezette be. A genetikus algoritmusok tervezése során az evolúciót tekinthetjük mintaképnek. Kezdetben nem optimálisan megírt, vagy paraméterezett programok keresztezések során a természetes kiválasztódás elve alapján fejlődnek, és a tapasztalat szerint közelítenek egy jó megoldáshoz. Nagyon jól alkalmazhatók bizonyos optimalizálási problémákhoz. A genetikus algoritmus [6] lényege, hogy rendelkezik a lehetséges megoldások egy populációjával, a populáción értelmezett a kiválasztási folyamat – amely az egyedek alkalmasságán alapul – és értelmezett néhány genetikus operátor (2. ábra).
Induló populáció generálása
Kiértékelő függvény
További optimalizálás
nem
igen
Start Kiválasztás
Új populáció generálása Klónozás
Mutáció
Keresztezés
2. ábra. A genetikus algoritmus folyamatábrája [17]
2
Legjobb egyed eredmény
Definiáljuk a következőket: egyed: a termékek sorszámát tartalmazza, tehát egy teljes sorrendet; populáció: az egyedek összessége; fitnesz (alkalmasság): egy egyed jóságát számszerűen ábrázoló adat; klónozás: a régi populáció nagyobb alkalmassággal rendelkező egyedeinek az új populációba történő másolása; keresztezés: két (szülő) egyed genetikus anyagának egy részét kicseréli, ezáltal hozva létre új egyedeket; mutáció: apró véletlenszerű változások az egyed genetikus anyagában. Az induló populáció készítése esetünkben a lehetséges megoldások véletlenszerűen kiválasztott halmazát jelenti. A szelekció nem az egyedeken, hanem a populációkon működik. A legismertebb, és a szerző által is használt fajtái: véletlen (random selection) kiválasztás: a legegyszerűbb, ámde a legkevésbé hatékony szelekció. Gyakorlatilag az aktuális populációból véletlenszerűen választ szülőket. Legnagyobb hátránya, hogy nem veszi figyelembe azt a darwini alapelvet, miszerint a rátermettebb egyedek nagyobb eséllyel érvényesülnek az egyedlétrehozásban; rulett-kerék (roulette wheel selection) kiválasztás: az egyik legrégebbi, és leginkább használt szelekciós operátor. Egy egyed kiválasztásának valószínűsége annál magasabb, minél nagyobb a rátermettsége a populáción belül (rátermettség-arányos szelekció). A rulett-kerék kiválasztás úgy működik, mintha az egyedeket egy rulett-kerék cikkelyeihez rendelnénk, ahol a cikkelyek nagysága a fitnesz értékkel arányos. Ahol a „golyó” megáll a pörgetés után, az az egyed kiválasztásra kerül; legjobb egyed (best selection) kiválasztás: fitnesz érték alapján sorbarendezzük az egyedeket, és az első k darabot választjuk ki. A genetikus algoritmus is – mint oly sok más a tudományban – a természettől kölcsönzött ötlet alapján működik [4]. Az életben évmilliók során kialakulnak azok az egyedek, amelyek legjobban alkalmazkodtak az élőhelyükhöz, amelyek fennmaradása biztosított. Ezek az egyedek genetikus állományukat – és ezzel jó tulajdonságaikat – továbbadják utódaiknak, biztosítva ezzel a populáció fennmaradását. Néha mutációk – véletlenszerű változások – adódnak a genetikus állományban. Az új egyedekben új tulajdonságok jelennek meg, amelyek vagy jobbak az eredetinél – és így az egyedek életben maradnak, tovább örökítve jó tulajdonságaikat – , vagy rosszabbak, s így elpusztulnak. Jelen tanulmány készítője ezt a folyamatot próbálta átírni számítógépre a termelésütemezési problémák megoldására.
A SZÁMÍTÓGÉPES PROGRAM BEMUTATÁSA A 3. ábra a program – ami Borland Delphi 5-tel [1, 2] íródott – felhasználói felületét mutatja. A dialógusablakban a konstans jellegű paraméterek találhatók. Első lépésben beállítjuk a megmunkálni kívánt termékek, valamint a megmunkáló berendezések mennyiségét. Ezután a genetikus algoritmushoz szükséges alapadatokat állíthatjuk be tetszés szerint (populáció mé-
3
rete, iterációk száma, a keresztezés, a mutáció és a klónozás aránya, kiválasztási stratégia). Az optimalizáló célfüggvényt a megfelelő választógomb bekapcsolásával választhatjuk ki. Ezután a program beállítja az időmátrix fejléceit a megadott gépek és termékek számának megfelelően. A felhasználó három különböző feltöltés közül választhat, úgymint gépi feltöltés, kézi adatbevitel és a Fájl/Betöltés menüponttal fájlból való betöltés is lehetséges. A programban a Módszerek menüpontból nyíló legördülő menüből választhatjuk ki, hogy a probléma megoldására alkalmas algoritmusok közül melyikkel óhajtjuk megoldani a feladatot. Természetesen így össze lehet hasonlítani a különböző módszerek hatékonyságát a kapott eredmények függvényében, melyet a dolgozat készítője korábbi tudományos munkássága alatt, már megtett [7].
3. ábra. A program felhasználói felülete
A genetikus algoritmus esetében egy kromoszóma a termékek tetszőleges sorrendjét jelenti, ez lesz az adatok helyes reprezentációja. A kiválasztódást alapbeállításban egyszerű fitnesz szerinti rendezéssel oldjuk meg, és a magasabb fitnesszel rendelkező egyedeket választjuk ki, de lehetőség van véletlenszerű, illetve a rulett-kerék szisztémának megfelelő kiválasztásra is. A GA megírása során két keresztező eljárást alkalmazott a szerző egyenlő arányban, úgymint a Cycle-Crossover (CX) [16] és az Order-Crossover (OX) [3], valamint négy mutáció operátort (reciprocal exchange, simple inversion, swap és displacement) használt fel szintén egyenlő arányban. Kiértékeléskor a maximális út megkeresésére alkalmas Bellmann-Pontrjagin-féle optimalizálási elvre [18] épülő a szerző által kidolgozott algoritmusba [8] történik a behelyettesítés.
4
4. ábra. A genetikus algoritmus futási eredménye
Genetikus algoritmus segítségével megoldva egy feladatot az iteráció előrehaladtával a grafikonon nagyon szépen nyomon követhető a legjobb egyed célfüggvény szerinti értéke valamint a populáció átlagértéke is (4/a. ábra). A legjobb egyed piros színnel (alsó görbe), míg az átlagérték kékkel (felső görbe) szerepel a grafikonon a jobb követhetőség érdekében. Mivel előfordulhat, hogy egy szülőt alacsonyabb fitnesz-értékű utód vált fel, így a populáció átlagértéke emelkedhet is. Ezzel szemben a legjobb egyed fitnesz-értéke monoton csökkenő függvénnyel ábrázolható. Az információs ablakban (4/b. ábra) az algoritmus futása közben folyamatosan kiírásra kerül az iterációk száma, valamint a legjobb egyedhez tartozó átfutási-, holt- és állásidők egyaránt. Az iterációk befejeztével megjelenik a legjobb egyedhez tartozó sorrend is. Az iteratív működés következtében több időre van szükségünk egy optimálishoz közeli megoldás eléréséhez, mint más heurisztikus esetben, viszont lényegesen jobb eredmény érhető el. A generációk számának növekedésével a legjobb egyed átlagos fitnesz-értéke egyre jobban megközelíti az optimális értéket, amely a vizsgált paramétertérben egy többé-kevésbé erős konvergenciát mutat. A feladat fitnesz-értékeit ábrázoló grafikonon megfigyelhető, hogy a GA végül olyan állapotba jutott, amelyben mind a legjobb individuum alkalmasság-értéke, mind pedig a populáció átlagos fitnesz-értéke a kezdeti rohamos javulás után beállt. A programban lehetőség van a genetikus algoritmussal történő optimalizálás leállítására a leállít gomb megnyomásával. Ilyenkor a program megerősítést kér a felhasználótól az optimalizálás megszakítására. Az igen elfogadása után az információs ablakba kiíródnak az addig előállított legjobb egyed adatai. A nem gombon kattintva a közelítés tovább folytatódik a kívánt iterációig, vagy egy újabb leállításig. Az alkalmazott keresztező operátorok A sorrendi ábrázolás a legtermészetesebb leírása egy egyednek, egyszerűen felsorolásra kerül a munkadarabok sorszáma a megmunkálás sorrendjében. Order-Crossover (OX) – Davis javaslata alapján Először meghatározásra kerül a keresztezési intervallum. p1 : 5 7 2 1 9 3 6 8 4 p2 : 8 6 3 7 1 5 4 2 9
Az intervallumon belül a gyerekek a szülők pontjait kapják. 5
o1 :
1 9 3
o2 :
7 1 5
A következő lépésben a o1 (o2) elkészítéséhez p2 (p1) második vágási pontjától kezdve felsorolásra kerülnek a termékek (a vektor utolsó eleme után az első elem jön). 4 2 9 8 6 3 7 1 5 6 8 4 5 7 2 1 9 3
A pontok közül kiesnek azok a pontok, melyek már szerepelnek a gyerekekben. 4 2 8 6 7 5 6 8 4 2 9 3
Ezután a lista pontjai a helyükre kerülnek: o1 : 6 7 5 1 9 3 4 2 8 o2 : 2 9 3 7 1 5 6 8 4
Cycle-Crossover (CX) – Oliver javaslata alapján p1 : 5 7 2 1 9 3 6 8 4 p2 : 8 6 3 7 1 5 4 2 9
Kiválasztásra kerül egy hely a p1 szülőben és az ott található kód átkerül az utódba. Legyen például ez a pozíció az 1.
o1 : 5 Ugrás az 1. helyen található p2 értékének megfelelő értékre a p1 szülőben. Itt ismét ugrás a p2 értékének megfelelő helyre, és ezt addig kell folytatni, amíg be nem záródik a kör. Az utódba p1 szülő a körbejárás során érintett értékei kerülnek.
o1 : 5
2
3
8
A hiányzó helyeken p2 szülő megfelelő értékei lesznek.
o1 : 5 6 2 7 1 3 4 8 9 Teljesen hasonlóan állíthatjuk elő a másik gyermeket:
o2 : 8 7 3 1 9 5 6 2 4 Oliver azt is kimutatta, hogy az OX operátor 15%-kal hatékonyabb, mint a CX. Az alkalmazott mutáció operátorok A példákban p1 : {4 7 1 8 6 3 2 9 5} a mutálni kívánt egyed, m1 pedig a mutáció után létrejövő új individuum. Reciprocal exchange két pozíció kijelölése az egyedben (P1=2, P2=5). a P1-en és a P2-n levő elemek felcserélődnek egymással. 6
p1 : 4 7 1 8 6 3 2 9 5 m1 : 4 6 1 8 7 3 2 9 5
2 pontú inverzió (simple inversion) két vágási pozíció kiválasztása az egyedben (P1=2 és P2=5). megfordítja a részstringet a két pozíció között, azaz a P1 n helyen lévő elem helyet cserél a P2 n helyen lévővel, ahol n {0,…,k}, k = egészrész[(P2 – P1) / 2]. p1 : 4 7 1 8 6 3 2 9 5 m1 : 4 6 8 1 7 3 2 9 5
Swap mutation Ez az operátor két részre vágja a kiválasztott kromoszómát és felcseréli a részeket. A szakadási pont véletlenszerűen kerül kiválasztásra, legyen ez az ötös pozíció. p1 : 4 7 1 8 6 3 2 9 5 m1 : 3 2 9 5 4 7 1 8 6
Displacement mutation Az operátor kiválaszt egy részsorozatot (2. és 5. pozíció között) és beszúrja azt egy másik helyre. Jelen esetben ez a 6. pozíciótól. p1 : 4 7 1 8 6 3 2 9 5 m1 : 4 7 3 2 9 1 8 6 5
ÉRZÉKENYSÉGVIZSGÁLATOK A keresztező operátorok összehasonlítása A tanulmány szerzőjének korábbi publikációiban [9, 10, 11, 12, 13] már megvizsgálta a termelésütemezési feladatokat megoldó különböző módszerek hatékonyságát, összevetette a genetikus algoritmus és a megerősítéses tanulás eredményességét, illetve elvégezte a GA paraméter-érzékenységvizsgálatát. Ezen alfejezetben a program által is használt keresztező operátorok összehasonlítását tűzte ki célul. Vizsgálatait természetesen ugyanazon (esetemben 20 gépes, 25 termékes) permutáció flow-shop termelésütemezési feladatra végezte el, melyek alatt a mutáció műveletet teljes egészében elhagyta, és csak a kiválasztott legjobb individuumok klónozásával valamint keresztezésével állította elő a soronkövetkező populációt. Ezzel biztosítva, hogy az eredmények fejlődése csak a keresztezésnek legyen betudható, ami egyértelmű összehasonlítást tesz lehetővé. Első lépésben a keresztezés során a program által használt két keresztező operátort (Cycle-Crossover és Order-Crossover) fele-fele arányban alkalmazta.
7
4500 4450
gépi holtidők
4400 4350 4300 4250 4200 4150 4100 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
keresztezés [%]
5. ábra. A genetikus algoritmus által szolgáltatott holtidő-értékek a keresztezés arányának függvényében
Az 5. ábrán feltüntetett keresztezési arányok (a populáció 99, 98, 96, …, 2 %-a) mindegyikére a genetikus algoritmus által 30 futtatás után szolgáltatott célfüggvény (jelen esetben holtidő) értékek átlagai 100 egyedszámú populációt és a legjobb kiválasztási stratégiát alkalmazva 150 iteráció után a következőképpen alakulnak. A koordináta rendszer vízszintes tengelyén a populációba keresztező eljárással generált utódok aránya van feltüntetve, míg a függőleges tengelyen a gépi holtidő értékek szerepelnek. A diagramon jól látható, hogy a keresztezés arányának 75%-ig történő csökkenésével folyamatosan javulnak a holtidő-értékek, majd egészen 15%-ig kvázi változatlannak mondható, ezután viszont rohamos mértékű emelkedés következik be (a 2%-os keresztezés már átlag 6,5%-kal rosszabb megoldásokat eredményez a 15%-oshoz képest). Megállapítható, hogy a genetikus algoritmus a keresztező operátor 75 és 15% közötti értéke esetén szolgáltatja a legkisebb célfüggvény-értékeket mutációt nem használva. A minimumot (4155) ugyan a 25%-os keresztezés (és ezáltal 75%-os klónozás) jelenti, de ez nem feltétlenül pontos, hiszen az optimum 75 és 15% között bárhol lehet. Erre további vizsgálatok szükségesek. Természetesen el kell végezni az alábbi vizsgálódást azon esetekre is, amikor a keresztezés során teljes egészében csak az egyik, vagy csak a másik keresztező operátort használjuk, hogy azok esetén hol ígérkezik az optimum, illetve melyik operátor produkál jobb eredményeket és mennyivel. Az előbb is vizsgált feladatra a program által 30 futtatás után szolgáltatott holtidő-értékek átlagai az előzőekkel teljesen megegyező beállítások mellett csak Cycle-Crossover (CX) keresztező operátort használva a következőképp alakulnak (6. ábra). 4500 4450
gépi holtidők
4400 4350 4300 4250 4200 4150 4100 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
keresztezés [%]
6. ábra. A genetikus algoritmus által szolgáltatott holtidő-értékek csak Cycle-Crossover használata esetén
8
Megállapítható, hogy jellegében az előzőhöz nagyon hasonló görbét kapunk. Kezdetben a keresztezési arány csökkenésével gyors javulás figyelhető meg, majd 85%-tól egészen 25%-ig a legjobb individuumok átlagos fitnesz-értéke már nem közelíti jobban az optimumot (a minimum 60%-nál adódik 4244 célfüggvény-értékkel), viszont a keresztezési arány 25% alá csökkenésével újra egyre gyengébb megoldásokat ad a program. Összességében kijelenthető, hogy a CX operátor átlag 2%-kal rosszabb eredményeket szolgáltat a mindkét szisztémát egyformán használó keresztezéshez képest. Ebből a tényből arra lehet gondolni, hogy az Order-Crossover operátor hatékonyabb, mint a CX. Az utolsó elemzés ennek megerősítésére vagy cáfolatára hivatott. Végül az eddig vizsgált ütemezési feladatra 30 futtatás szolgáltatott holtidő-értékek átlagai az előzőekkel egyező beállítások mellett csak Order-Crossover (OX) keresztező operátort használva a 7. ábrán látható módon alakulnak. A vízszintes tengelyen továbbra is az alkalmazott keresztezés aránya (99-2%-ig), míg a függőlegesen a holtidők szerepelnek. 4500 4450
gépi holtidők
4400 4350 4300 4250 4200 4150 4100 99 98
96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
keresztezés [%]
7. ábra. A genetikus algoritmus által szolgáltatott holtidő-értékek csak Order-Crossover használata esetén
A korábbiaktól eltérően már az elején (80%-ig) rohamos fejlődésnek lehetünk tanúi (a 80%-os keresztezés már átlag 4,6%-kal kedvezőbb megoldásokat eredményez a 99%-oshoz képest), majd (20%-ig) az átlagos alkalmasság-érték most is beállt, viszont a végén szerényebb növekedés tapasztalható, mint eddig. A legkisebb holtidő-értékeket (4280) ugyan a 67%-os keresztezés (és ezáltal 33%-os klónozás) jelenti, de a pontos arány 80 és 20% között most is bárhol lehet. Várakozásunkkal ellentétben azonban a grafikonon megjelenített adatokból az állapítható meg, hogy az OX keresztező operátor nem hogy jobb, mint a CX (és a vegyes) keresztezés, hanem még átlag 1,1 %-kal rosszabb eredményeket is szolgáltat. Ennek tükrében viszont meglepő, hogy amikor fele-fele arányban van alkalmazva a két operátor az átlagos fitnesz-érték jobban közelíti az optimális értéket, mint külön-külön bármelyiknél. Ebből következik, hogy egy adott feladatnál tehát érdemes a keresztező eljárások széles skáláját felhasználni, mert egy gyengébb sem húzza le a másikat, hanem együtt még jobb fejlődés érnek el. A mutáció operátorok összehasonlítása Ezen alfejezetben a program által is használt négy mutáció operátor összehasonlítását tűzte ki célul a cikk készítője. Vizsgálatait természetesen most is ugyanazon (esetemben 20 gépes, 25 termékes) permutáció flow-shop termelésütemezési feladatra végzi el, melyek alatt a keresztezés műveletet teljes
9
egészében elhagyja, és csak a kiválasztott legjobb individuumok klónozásával valamint mutációjával állítja elő a soronkövetkező populációt. Ezzel biztosítva, hogy az eredmények fejlődése csak a mutációnak legyen betudható, ami egyértelmű összehasonlítást tesz lehetővé. Első lépésben a program által használt négy mutáció operátor közül csak a simple inversion (2 pontú inverzió) mutációt alkalmazza. A 8. ábrán feltüntetett mutációs arányok (a populáció 99, 98, 96, …, 2%-a) mindegyikére a genetikus algoritmus által 30 futtatás után szolgáltatott célfüggvény (jelen esetben holtidő) értékek átlagai 100 egyedszámú populációt és a legjobb kiválasztási stratégiát alkalmazva 150 iteráció után a következőképpen alakultak: 4700 4600
gépi holtidők
4500 4400 4300 4200 4100 4000 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
m utáció [%]
8. ábra. A simple inversion által szolgáltatott holtidő-értékek a mutáció arányának függvényében
Az ábrából jól kivehető, hogy a mutáció arányának 80%-ig történő csökkenésével folyamatosan javulnak a holtidő-értékek, majd egy viszonylag konstans szakasz után (40-20% alatt) rohamos mértékű romlás következik be (a 2%-os mutáció már több mint 11%-kal eredményez rosszabb megoldásokat az optimumhoz képest). Megállapítható, hogy a genetikus algoritmus a simple inversion mutációs operátor 80 és 40% közötti alkalmazása esetén eredményezte a legkisebb holtidő értékeket keresztezést nem használva. A minimumot a 67%-os mutáció (és ezáltal 33%-os klónozás) jelentette. A következő vizsgálatban a program által kezelt négy mutáció operátor közül csak a reciprocal exchange mutációt használja a szerző. Az előzőhöz nagyon hasonló jellegű görbét kaptunk. A vízszintes tengelyen az alkalmazott mutáció aránya, míg a függőlegesen továbbra is a holtidők szerepelnek. 4600 4500
gépi holtidők
4400 4300 4200 4100 4000 3900 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
m utáció [%]
9. ábra. A reciprocal exchange által szolgáltatott holtidő-értékek a mutáció arányának függvényében
10
A diagramon jól látszik, hogy a mutáció arányának 75%-ig történő csökkenésével most is folyamatosan javulnak a holtidő-értékek, majd egy kezdeti lassú emelkedés után (25% alatt) rohamos mértékű hanyatlás következik be (a 2%-os mutáció már közel 14%-kal eredményez rosszabb megoldásokat a minimumhoz képest). Kijelenthető, hogy a genetikus algoritmus a reciprocal exchange mutációs operátor alkalmazása esetén a 75%-os aránynál produkálta az optimumot (4000). A következő esetben a mutáció operátorok közül csak a swap mutációt alkalmazzuk. Az eredményeket a 10. ábra szemlélteti: 4700
gépi holtidők
4650 4600 4550 4500 4450 4400 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
m utáció [%]
10. ábra. A swap mutáció által szolgáltatott holtidő-értékek a mutáció arányának függvényében
Az eddigiektől kicsit eltérő jellegű görbén lassú javulás figyelhető meg a mutáció arányának egészen 50%-ot elérő csökkenéséig, majd ezután is csak szerény emelkedés tapasztalható. Azaz, a swap mutáció használata esetén épp a kisebb mutációs arányok jelentik a jobb megoldásokat. Bár nincs akkora eltérés az eredmények között, mint amekkorát a grafikon mutat, hisz a 99%-os mutáció is csak alig 4,5%-kal eredményez rosszabb megoldásokat a legkisebb értékűhöz (50% – 4461) képest. Az utolsó vizsgálatnál csak a displacement mutáció operátor segítségével állítja elő a következő populációt az algoritmus. A 11. ábrán feltüntetett mutációs arányok mindegyikére a GA által szolgáltatott holtidő értékek a következőképpen alakultak: 4670 4660
gépi holtidők
4650 4640 4630 4620 4610 4600 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10
5
4
2
m utáció [%]
11. ábra. A displacement által szolgáltatott holtidő-értékek a mutáció arányának függvényében
11
Most is szerény mértékű javulás látható a mutáció arányának egészen 67%-ot elérő csökkenéséig, majd ezután pedig még szerényebb emelkedés fedezhető fel a diagramon. A minimumot (4611) ugyan a 67%-os mutáció (és ezáltal 33%-os klónozás) jelentette, de a legroszszabb eredményhez (99%-os mutáció) képest is csak alig több mint 1%-kal ad jobb eredményt (az utóbbi két esetben csak a függőleges tengely korábbiaktól eltérő skálázása miatt tűntek meredekebbnek a görbék). Tudományos munkája befejezéséül az előadó megvizsgálta, hogy a program által használt négy mutáció operátor egyenlő arányban történő alkalmazásakor hogyan alakul a grafikon. Kíváncsisága oka az volt, hogy a keresztező operátorok összehasonlításakor világossá vált, hogy a legjobb eredményt a GA az operátorok együttes alkalmazása esetén szolgáltatja, még az egyébként legjobb megoldásokat adó keresztezésnél is jobbat, azaz a gyengébbek nem hogy nem rontották a jobb operátorok teljesítményét, hanem még javították is azt. A jobb láthatóság és a már említett eltérő skálázásból adódó problémák kiküszöbölése végett egy diagramban ábrázoltuk az eddigi és a vegyes alkalmazással kapott eredményeket. 4675 4600 gépi holtidők
4525 vegyes
4450
simple inversion
4375
reciprocal exchange
4300
swap
4225
displacement
4150 4075 4000 99 98 96 95 90 85 80 75 70 67 60 50 40 33 25 20 15 10 5 4 2 mutáció [%]
12. ábra. A különböző mutáció operátorok alkalmazásával kapott eredmények
Az ábrán egyértelműen kitűnik, hogy a négy mutáció operátor közül kettő sokkal jobb eredményeket szolgáltat a másik kettőnél. A legjobb megoldásokat a reciprocal exchange mutáció alkalmazása adja, de alig marad el tőle a simple inversion operátor, ami csak átlag 2,5%kal generál gyengébb célfüggvény-értékeket, sőt 10% alatti mutáció arányoknál a két görbe szinte fedi egymást. Ezzel szemben a swap mutáció már közel 9,5%-kal rosszabb, mint a reciprocal exchange, míg a displacement operátor több mint 12%-kal, így kijelenthető, hogy ez utóbbi mutáció használata eredményezi a legnagyobb holtidőket.
ÖSSZEFOGLALÁS A két keresztező operátort összehasonlítva összességében kijelenthető, hogy a flow-shop ütemezés esetében a jobb megoldást a Cycle-Crossover adja, a rosszabb közelítést pedig az OX produkálja, ami teljesen ellenkezője az utazó ügynök problémánál (TSP) megismert sorrendnek (Oliver mutatta ki, hogy az OX operátor 15%-kal hatékonyabb, mint a CX). Ez az eltérés azzal magyarázható, hogy a TSP-nél a szomszédsági információ számít, addig a FSSP-
12
nél a sorrendi az érdekes. Ezért is van a termékek listájával ábrázolva az ütemezési problémánál a sorrend (sorrendi ábrázolás), ami a legtermészetesebb leírása egy egyednek, egyszerűen felsorolásra kerül a munkadarabok sorszáma a megmunkálás sorrendjében. A keresztező operátorokkal ellentétben, a mutáció operátorok vizsgálatánál nem mondhatjuk el, hogy azok együttes alkalmazásakor kapnánk a legjobb eredményeket, bár az operátorokat egyenlő arányban alkalmazó vegyes megoldás grafikonja szinte teljesen egyezik a legkisebb értékeket felvonultató reciprocal exchange mutációéval. Természetesen érdemes lenne elvégezni más az operátorokat eltérő arányban használó vegyes rendszerek esetén is ezeket a vizsgálatokat, hogy azok esetén hogyan alakulnának a diagramok, de az már most is megállapítható, hogy inkább a reciprocal exchange és a simple inversion mutációkat érdemes preferálni a swap és a displacementtel szemben a minél inkább optimum-közeli megoldások hatékony megtalálása végett. FELHASZNÁLT IRODALOM [1] BENKŐ T.: Programozzunk Delphi 5 rendszerben, Computerbooks, Budapest, 2000. [2] CANTU M.: Delphi 5 Mesteri szinten, I.-II. kötet, Kiskapu Könyvesbolt, 2000. [3] DAVIS L.: Job Shop Scheduling with Genetic Algorithms. International Conference on Genetic Algorithms and their Applications, Erlbaum, 1985. 136–140. o. [4] GOLDBERG D. E.: Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989. [5] HOLLAND J. H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology Control, and Artificial Intelligence, The University of Michigan Press, 1975. [6] MICHALEWICH Z.: Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1996. [7] OLÁH B.: A flow shop ütemezési probléma optimalizálására szolgáló algoritmusok összehasonlítása. OGÉT 2005 XIII. Nemzetközi Gépész Találkozó, Szatmárnémeti, 2005. 268–272. o. [8] OLÁH B.: Genetikus algoritmus vs. megerősítéses tanulás, Szolnoki Tudományos Közlemények IX. 2005. [9] OLÁH B.: Genetic algorithm vs. Reinforcement learning, Chapter 80 in DAAAM International Scientific Book 2009, Vol. 8, Published by DAAAM International, Vienna, Austria, 2009. 831–844. o. [10] OLÁH B.: Genetikus algoritmus érzékenységvizsgálata, Műszaki Tudomány az Észak-Alföldi Régióban 2010, Nyíregyháza, 2010. 157–162. o. [11] OLÁH B.: Genetikus algoritmus érzékenységvizsgálata a populáció méretének függvényében, ECONOMICA (A Szolnoki Főiskola Tudományos Közleményei), Szolnok, 2010. 4–10. o. [12] OLÁH B.: Flow-shop termelésütemezési feladatokat megoldó genetikus algoritmus érzékenységvizsgálata, Szolnoki Tudományos Közlemények XIV. Szolnok, 2010. [13] OLÁH B.: Sensitivity analysis of a genetic algorithm in function of the population size, XXV. microCAD International Scientific Conference, University of Miskolc, Miskolc, Hungary, 2011. 113–118. o. [14] OLÁH B.: Flow-shop ütemezést megoldó genetikus algoritmus keresztező operátorainak érzékenységvizsgálata, XIX. Nemzetközi Gépész Találkozó – OGÉT 2011, Csíksomlyó, Románia, 2011. 282–285. o. [15] OLÁH B.: Flow-shop ütemezési feladatokat megoldó genetikus algoritmus mutáció operátorainak érzékenységvizsgálata, Műszaki Tudomány az Észak-Kelet Magyarországi Régióban 2011, Miskolc, 2011. 133–140. o. [16] OLIVER I. M.—SMITH D. J.—HOLLAND J. R. C.: A Study of Permutation Crossover Operators on the Traveling Salesman Problem. 2nd International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1987. 224–230. o. [17] POHLHEIM H.: Evolutionary Algorithms, 2009. http://www.geatbx.com/docu/algindex.html [18] TÓTH I.: Operációkutatás I., Tankönyvkiadó, Budapest, 1990.
13
