Gráfszínezés adaptív evolúciós algoritmusokkal

Szegedi Tudományegyetem Informatikai Tanszékcsoport

Gráfszínezés adaptív evolúciós algoritmusokkal

Diplomamunka

Készítette: Veress Krisztián programtervez˝o matematikus szakos hallgató

Témavezet˝o: Dr. Blázsik Zoltán egyetemi tanársegéd

Szeged 2009

Tartalomjegyzék Feladatkiírás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tartalmi összefoglaló . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Evolúciós számítások 1.1. Az evolúciós algoritmus . . . . . . . . . . . . . . . . . 1.1.1. Az algoritmus m˝uködési elve . . . . . . . . . . . 1.1.2. Egyedek, fitnesszfüggvény és a génmódosítások 1.1.3. Az evolúciós algoritmusok gyenge pontjai . . . . 1.2. Egy új evolúciós keretalgoritmus . . . . . . . . . . . . . 1.2.1. B˝ovebb genetikai m˝uveletkészlet támogatása . . 1.2.2. A természetes szelekció kontrollálása . . . . . . 1.2.3. A keres˝om˝uveletek alkalmazása . . . . . . . . . 1.2.4. Párhuzamosítási lehet˝oségek . . . . . . . . . . .

4 5

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

6 6 6 7 9 10 10 11 13 13

2. Gráfszínezés, ismert gráfszínez˝o heurisztikák 2.1. A gráfszínezési probléma . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Gráfok hatékony reprezentációja . . . . . . . . . . . . . . . . . . . . 2.3. A mohó színezés algoritmusa . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Fokszámokon alapuló algoritmusok . . . . . . . . . . . . . . 2.3.2. A heurisztikák kombinálásának lehet˝oségei . . . . . . . . . . 2.3.3. MATLAB megvalósítások . . . . . . . . . . . . . . . . . . . 2.4. Maximális független csúcshalmazon alapuló szekvenciális algoritmus

. . . . . . .

. . . . . . .

14 14 15 16 17 17 18 19

. . . . . . . .

20 20 21 22 24 28 28 30 31

. . . .

34 34 35 35 38

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

3. Gráfszínezés evolúciós algoritmusokkal 3.1. Az egyedek kódolása és a fitnesszfüggvény . . . . . . . . . . . 3.2. A javasolt genetikus keres˝om˝uveletek . . . . . . . . . . . . . . 3.2.1. Evolúciós algoritmusok a MATLAB-ban . . . . . . . . 3.3. A b˝ovített eljárások verifikációja . . . . . . . . . . . . . . . . . 3.4. A heurisztikák és evolúciós módszerek összehasonlító elemzése 3.4.1. Közelítési pontosságok a kromatikus számra . . . . . . 3.4.2. Futásid˝ok elemzése . . . . . . . . . . . . . . . . . . . . 3.4.3. A kapott eredmények összefoglalása . . . . . . . . . . . 4. A sík 1 színezésének vizsgálata EKG algoritmussal 4.1. A sík 1 színezésének problémája . . . . . . . . . . . . . . . 4.2. Akadályok keresése magasabb kromatikus számú gráfokban 4.2.1. Az EKG kromoszómái és genetikus keres˝om˝uveletei 4.2.2. Az EKG algoritmus megbízatósági vizsgálata . . . .

. . . .

. . . .

. . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

2

Gráfszínezés adaptív evolúciós algoritmusokkal 4.3. Akadálykeresés és elemzés . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1. A csúcsfokszámok és a közelítési pontosság összefüggése . . . . 4.3.2. Akadályok Mycielski 4 -ben . . . . . . . . . . . . . . . . . . . .

39 41 43

Összefoglalás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

Nyilatkozat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Köszönetnyilvánítás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46 47 48

3

Feladatkiírás Megoldandó feladat: Egy NP-teljes feladat ( pl. 3-SAT, gráfok színezése, maximális méret˝u független csúcshalmaz keresése gráfokban, TSP(C), hátizsák feladat, a ládapakolási feladat ) ismertetése és megoldása. Majd néhány heurisztikus algoritmus bemutatása, és összehasonlításuk a genetikus algoritmussal kapott megoldással.

Elérend˝o cél: Különböz˝o heurisztikus algoritmusok és a genetikus algoritmusok összehasonlító elemzése. A kiválasztott problémák mindegyikéhez meg kell írni többféle elven m˝uköd˝o programot, amelyek eredményeinek jóságát össze akarjuk hasonlítani. A programnyelv szabadon megválasztható. A téma igényes kidolgozása esetén diákköri dolgozat is készülhet bel˝ole.

4

Tartalmi összefoglaló Ezen dolgozatban a numerikus optimalizálás területén jól bevált genetikus illetve evolúciós algoritmusok teljesítményét fogjuk vizsgálni gráfszínezési problémák megoldása során. Az evolúciós algoritmusokat széles körben, az üzleti szférától az autógyártásig alkalmazzák. Immáron egyre több befektet˝o jobban megbízik a szimulált evolúció túlél˝oiben, mint a pénzügyi szakért˝okben. Fényt derítünk a sztenderd evolúciós stratégiák hiányosságaira, illetve bizonytalansági tényez˝oire, s olyan megoldásokat javasolunk, amelyekkel az algoritmus hatékonysága megnövelhet˝o. A javasolt algoritmus számos újítást tartalmaz a sztenderd változatokhoz képest, s ezen újítások együttes alkalmazásától jelent˝os javulást remélünk. Tekintettel arra, hogy ezen algoritmust nagy méret˝u, nehéz problémák megoldására terveztük, a terheléselosztást és párhuzamosítási lehet˝oségeket a tervezés és implementálás minden szakaszában figyelembe vettük. Ismert számos gráfszínezési algoritmus, amelyek belátható id˝on belül megoldást szolgáltatnak, azonban ezek vagy csak speciális, általában kis méret˝u problémák esetén alkalmazhatóak, vagy a közelítéssel kapott megoldás igen messze van az optimálistól. Egy gráfszínezési feladatokat tartalmazó adatbázis elemein összehasonlítottuk a direkt módszereket a sztenderd evolúciós algoritmusokkal, illetve a továbbfejlesztett algoritmusunkkal. Ezután egy speciális, nagy méret˝u és igen bonyolult gráfszínezési problémát vizsgáltunk, amelyre nem ismert direkt módszer, így ez egy igen termékeny táptalaj az evolúciós algoritmusunknak. A probléma nyitott, így a pontos megoldás nem ismert. A dolgozatban elkészítettünk olyan evolúciós algoritmusokat, amelyek képesek ezen nyitott probléma vizsgálatára. A vizsgálatok során fontos megállapításokra jutottunk, amelyek támpontot adhatnak a kés˝obbi kutatásokhoz. A tapasztalataink azt mutatják, hogy az evolúciós algoritmusok igen jól alkalmazhatóak a gráfszínezési problémakör számos problémájára, robusztusak, könnyen kezelhet˝oek és könnyen módosíthatóak, amely a heurisztikus megközelítés miatt igen fontos. Számos esetben szolgáltattak jobb megoldást, mint az ismert gráfszínezésre használt heurisztikák, nagyobb gráfméretek, illetve bonyolultabb struktúrák esetén mindenféleképpen hatékonyabbak. Kulcsszavak: gráfszínezés, heurisztikus eljárások, evolúciós módszerek, hibrid rendszerek, sík kromatikus száma

5

1. fejezet Evolúciós számítások 1.1. Az evolúciós algoritmus Nagyon sok olyan probléma létezik, amelyre nem ismert algoritmus, vagy ismert ugyan, de az nem hatékony, vagy éppen nem megbízható. Sok ilyen feladattal találkozhatunk a nemlineáris optimalizálás területén. Olyan feladatoknál, ahol nehéz meghatározni a globális optimumot, megelégszünk az optimális megoldás egy közelítésével, és ezekre a közelítésekre keresünk hatékony, megbízható algoritmust. Ilyenek az evolúciós algoritmusok, amelyek a természetben lejátszódó folyamatokat modellezik, mégpedig a genetikus örökl˝odést, az evolúciót, illetve a darwini küzdelmet az életben maradásért. A genetikus algoritmust el˝oször John Holland a michigani egyetem tudósa javasolta a 60-as évek elején. Az els˝o eredményt 1975-ben érte el, az Adaptation in Natural and Artificial System c. publikációval (H OLLAND [11]), o˝ t˝ole származik az alábbi definíció. 1.1.1. Definíció. [Evolúciós algoritmus] „Az evolúciós algoritmus egy olyan keres˝oalgoritmus, amelynek alapja a természetes szelekció, és természetes géntechnológiák, eredménye pedig egy olyan hatékony keres˝oalgoritmus, amely az emberi keresési stratégia újító hajlamait tartalmazza. Az evolúciós algoritmusokat megalapozó hasonlat a természetes evolúció hasonlata. Az evolúció során az egyes fajok feladata az, hogy minél jobban alkalmazkodjanak egy bonyolult, ráadásul állandóan változó környezethez. A tapasztalat, melyet az egyes fajok az alkalmazkodás során szereznek, beépülnek a kromoszómákba, és azok tovább örökl˝odnek.”

1.1.1. Az algoritmus muködési ˝ elve Az EA a probléma megoldását iteratív módon keresi. Az eljárás ciklikusan m˝uködik, minden ciklusban egyidej˝uleg több egyeddel (megoldással) dolgozva. Az aktuális egyedek halmazából – mint populációból – válogatással, majd különböz˝o keres˝o m˝uveletek alkalmazásával állít el˝o újabb egyedeket, ún. utódokat. Az egyes egyedek rátermettségét a fitnesszfüggvénnyel méri, amely a rátermettebb egyedekhez nagyobb (kisebb) számot rendel, így el˝onyösebb helyzetbe juttatva azokat a következ˝o ciklusban bekövetkez˝o evolúciós szelekció során. A létrehozott utódok és szül˝ok halmazából (általában) a legrátermettebb egyedeket választja ki a következ˝o ciklus számára. Ez a rátermettség-alapú szelekció fogja eredményezni a célfüggvény minimalizálását, a problémára adott minél jobb

6

Gráfszínezés adaptív evolúciós algoritmusokkal megoldás megtalálását. Az egyedeken végrehajtott génmanipulációk és az egyedek közötti géncserék biztosítják a problématér feltérképezését illetve a minél „életképesebb” egyedek kitenyésztését. A ciklusok azaz generációk addig ismétl˝odnek, amíg egy kívánt feltétel nem teljesül (pl. a generációk száma elér egy maximális értéket, vagy egy el˝ore meghatározott szintnél jobb megoldásunk van). Az 1.1. ábrán az evolúciós algoritmus sematikus ábráját láthatjuk. Jól megfigyelhet˝o a kereteljárás iteratív jellege, amely az újabb és újabb populációk létrehozását, az egyedek értékelését, illetve a megállási feltételek ellen˝orzését foglalja magában.

1.1. ábra. Az általános evolúciós algoritmus sémája

1.1.2. Egyedek, fitnesszfüggvény és a génmódosítások Az egyed, vagy individuum mindig a problémának egy lehetséges megoldását jelöli. Formai szempontból igen változatos lehet: sztring, valós vektor, de akár összetett struktúra ( áramköri rajz, program, zenem˝u, stb. ) is lehet. Az egyedek szavakkal való leírását fenotípusnak nevezzük. A fenotípus a környezet számára észlelhet˝o tulajdonságai az egyedeknek, amelyen érthetjük teljes fizikai megjelenését, vagy egy specifikus jelleg meglétét. Az algoritmusban az egyed reprezentációjára alkalmas struktúrát genotípusnak hívjuk. A genotípus egy egyed genetikai felépítése (lényegében maga a genom), ami az egyed fenotípusát kódolja. A populációt alkotó egyedek – mint lehetséges megoldások – értékelését is szükséges elvégeznünk, erre az ún. fitnessz-függvény hivatott. A fitnessz-függvény minden egyedhez egy értéket rendel, a hozzárendelt érték annál magasabb, minél jobb az adott egyed a feladat megoldása szempontjából. Az EA pilléreinek igen részletes bemutatása megtalálható a B ORGULYA [2] könyvben. A populációt az egyedek, más néven kromoszómák alkotják. Minden populáció a lehetséges megoldások terét adja, az egyedek populációján végbemen˝o „evolúció” a potenciális megoldások halmazán történ˝o keresésnek felel meg. A populációk egymásutánját generációknak hívjuk. Az EA generációk sorozatát állítja el˝o, jobb és jobb egyedeket létrehozva az új populációkban. 7

Gráfszínezés adaptív evolúciós algoritmusokkal A szelekció felel˝os elvégezni a természetes szelekciót, azaz a gyenge egyedek elhagyását, és biztosítani az er˝osebb egyedek túlélését illetve szaporodását. Az evolúció során egy populáció egyedei közül a szelekció határozza meg, mely egyedek alkalmasak „szül˝oknek”, mely egyedeket hagyjunk el, és mely egyedeken módosítsunk. Az egyedeken végzett effajta sz˝urés olyan eljárásokkal történik, amelyek figyelembe veszik az egyedekhez tartozó életképességi tényez˝oket, így a rátermettebb egyedek nagyobb valószín˝uséggel lehetnek szül˝ok. Az egyedeken végezhet˝o génmódosításokat két csoportba sorolhatjuk: • A mutáció egy egyed genotípusán végzett változtatás, amely az egyed spontán alkalmazkodását hivatott modellezni. Olyan keres˝o m˝uvelet, amely az utódot jellemz˝o változókat kis értékkekkel (zajokkal) módosítja. A mutáció nagyon fontos szerepet tölt be a keresési tér szélesítésében, hiszen tetsz˝oleges módon megváltoztathat egy egyedet, így új „génállományt” juttatva a populációba. Ezáltal a lokális széls˝oértékeket könnyebben elkerülhetjük, illetve azokba kevésbé ragadhatunk be. • A keresztezés két egyed génjeinek kicserélését jelenti, azaz a természetben el˝oforduló szaporodást modellezni. A keresztezés a legf˝obb motorja az evolúciós algoritmusoknak, hiszen több, számunkra értékes egyedb˝ol egy várhatóan még értékesebb egyedet – azaz jobb megoldást – próbál készíteni. A keresztezés nélkül a konvergencia nem lenne lehetséges, hiszen önmagukban a mutációs operátorok a keresési térben csupán oszcillálnának. Fontos továbbá megemlíteni, hogy az evolúciós algoritmusok nem véletlen algoritmusok. Az EA ugyanis determinisztikus lépések egymásutánját hajtja végre, nem az eljárás véletlenszer˝u, hanem a kereteljárásban használt m˝uveletek végrehajtásának módja véletlenített. Az optimális megoldások megtalálása tehát nem egyszer˝uen a véletlen szerencsén, sokkal inkább a keres˝o m˝uveletek minél pontosabb specifikációján, és az algoritmus paramétereinek jól átgondolt beállításán múlik. Az EA mint optimalizáló eljárás matematikai modelljének tekintsük a következ˝ot. Keressük az y ∗ = min(fit(e)) e∈F

∗

e

= arg min(fit(e)) e∈F

értékeket, ahol fit : F 7→ R a fitnesszfüggvény és F a fenotípus, mint egyedek halmaza. Az evolúció modellezése során fellép˝o génváltoztatásokat a mutáció és keresztezés szolgáltatják: m(e)e∈F : G 7→ G , e′ = m(e) r(e1 , e2 )e1 ,e2 ∈F : G × G 7→ G , e′ = r(e1 , e2 ) ahol G a genotípus, mint kromoszómák halmaza. Az EA módszereket egyszer˝u célfüggvénnyel rendelkez˝o, determinisztikus rendszerek esetén nem érdemes alkalmazni, hiszen ilyen problémák esetén a célfüggvény deriváltjai, és más segédinformációk ismeretében a direkt módszerek sokkal hatékonyabbak. Abban az esetben, amikor a célfüggvény ismert de bonyolult, esetleg egy black-box1 függvény, az evolúciós algoritmus egy jó választás lehet. 1

black-box függvény: egy függvényt black-box függvénynek nevezünk, ha a viselkedését csak bemenetkimeneti párokkal tudjuk leírni és zárt képlete nem ismert

8

Gráfszínezés adaptív evolúciós algoritmusokkal

1.1.3. Az evolúciós algoritmusok gyenge pontjai Az evolúciós algoritmus egy igen skálázható kereteljárás, hasonlóan a korlátozás és szétválasztás módszerhez. Tekintettel arra, hogy egy probléma megoldásának elkészítése során a keretb˝ol egy konkrét algoritmust kell készítenünk, a tervezés több pontján is fontos döntéseket kell hoznunk. A korlátozás és szétválasztás módszernél ezen döntésekre vonatkozó korlátok egyértelm˝uen le vannak fektetve, azonban az evolúciós algoritmusnál ez nincs így. A probléma egyedül a fenotípust és a célfüggvényt szolgáltatja, így döntenünk kell a következ˝okben: - Milyen genotípust használjunk, azaz milyen módon kódoljunk egy lehetséges megoldást? - Hogyan határozzuk meg a kezd˝opopulációt, és mekkora legyen a populációnk mérete? A populáció mérete fix, vagy változtatható legyen? - Milyen szelekciós sémát alkalmazzunk ? Milyen módon lehessen egy egyedet mutálni? Milyen típusú mutációt használjunk? - Milyen módon határozzuk meg két egyed keresztezésének eredményét, és hogyan válasszunk a keresztezés számára szül˝oket? - Milyen valószín˝uséggel alkalmazzuk az evolúciós operátorokat? - Kooperatív, vagy kompetitív sémát alkalmazzunk, azaz az egyedek egymás ellen „küzdjenek” a túlélésért, avagy egymást „segítsék”, hogy minél tovább éljenek? Ezen kérdésekre adott válaszok nagyban befolyásolják a leend˝o algoritmusunk min˝oségét, különös tekintettel annak konvergenciájára, megbízhatóságára és globalitására. Léteznek általános szabályok, azonban ezek alkalmazása – pontosan az általánosság miatt – nem feltétlenül vezet megfelel˝o eredményre. A legfontosabb probléma az, hogy az általános kereteljárás kizárólag egy-egy keresztezés, mutációs és szelekciós m˝uveletet támogat. A valós helyzetekben azonban több-több változat is elképzelhet˝o, amely egyrészt b˝ovebb keresési teret eredményez, továbbá az evolúció különböz˝o pontjain a különböz˝o m˝uveletek hatása más és más lehet. Ezen megfigyelés alapján elmondhatjuk, hogy valós igény van a kereteljárás olyan módosítására, amely egyszerre több m˝uveletet is képes kezelni egy genetikai m˝uvelettípuson belül. A génmódosítások alkalmazása, azaz az egyedek evolválása egy valószín˝uségvektor alapján történik. A (PXover , PM utation ) = (0.8, 0.2) vektor – amely használatával a „közel 5 egyedb˝ol 4 nemz˝oképes” állapotot fejezzük ki – általában jól használható. Azonban ezen vektor meghatározására nincs elfogadott módszertan tekintettel arra, hogy ez a modellekb˝ol nem származtatható, függ a genetikus m˝uveletek megvalósításaitól, a keresési tért˝ol, az aktuális populációktól, és az algoritmus aktuális állapotaitól is. A valószín˝uségvektor ilyen formában továbbá csak egyetlen egy szabadsági fokkal rendelkezik, hiszen fennáll a PXover = 1 − PM utation ekvivalencia. A valószín˝uségvektoron azonban nagyon sok múlhat, hiszen ez vezérli az adott m˝uveletek életbelépését, ha úgy tetszik a populáció „sorsát”.

9

Gráfszínezés adaptív evolúciós algoritmusokkal

1.2. Egy új evolúciós keretalgoritmus A sztenderd evolúciós algoritmus b˝ovítésekor a célunk az volt, hogy egy olyan kereteljárást készítsünk, amely • az evolúciós keres˝o m˝uveletekb˝ol egy osztályon (mutáció, keresztezés) belül több m˝uvelet is támogatott és ezek paraméterei önadaptívak, • konvergenciája összemérhet˝o a sztenderd változatéval, mégis globalitási szempontból túlteljesíti azt, • rendelkezik azzal az általánosítási képességgel, amely a sztenderd EA-nak is tulajdonsága, • a fitnesszértékek számítása és a populáción végzett m˝uveletek elosztott rendszereken végezhet˝oek, • továbbá kooperatív és kompetitív séma alkalmazására is lehet˝oség van. Most sorra megvizsgáljuk a kit˝uzött célokra adott megoldásainkat.

1.2.1. B˝ovebb genetikai muveletkészlet ˝ támogatása Az EA a felhasználó által megadott keres˝o eljárások használatával keres mind jobb és jobb megoldásokat. Ez utóbbiakban szolgáltatjuk ugyanis a probléma leírását, azt, hogy milyen módon lehet jobb és jobb egyedeket kreálni. A genetikus m˝uveletek b˝ovítése nem jelent mást, mint több mutációs és több keresztezés m˝uvelet megadását. Amennyiben ez nem kívánt, vagy nem lehetséges, visszakapjuk a hagyományos 1-1 keres˝o m˝uvelettel dolgozó evolúciós algoritmust. 1.2.1. Példa. Adott áramköri kapcsolásban szerepl˝o elektronikai elemeket úgy szeretnénk elhelyezni, hogy a vezetékek összhossza minimális legyen. Ez rádiófrekvenciás áramkörökben igen fontos, hiszen a vezetékek komoly zavart kelthetnek. Az egyedeket ekkor kódolhatjuk az áramköri elemek pozíciójának konkatenációjaként. Mutációs operátorokra a következ˝oket javasolhatjuk: 1. Tetsz˝oleges két áramköri elem pozíciójának felcserélése. 2. Két szomszédos áramköri elem pozíciójának felcserélése. 3. Tetsz˝oleges n elem kiválasztása, majd ezek közül a passzív elemek (Ohmikus ellenállás, induktivitás, kondenzátor) minél közelebbi csoportosítása. Hasonlóan a keresztezés m˝uveletre is megfogalmazhatnánk akár több módszert. Az evolúciós algoritmusunkat kiegészíthetjük továbbá egyéb speciális keres˝o m˝uveletekkel, ilyenek lehetnek az elitista túlélés (elite survival), illetve hibernáció (hibernation) m˝uveletek, amelyek általában a generációk közötti még b˝ovebb géncserét biztosítják (lásd C HANG [3]). Tekintettel arra, hogy a b˝ovebb m˝uveletkészlettel dolgozó eljárás többféle módon tud keresni, várhatóan a keresési teret (az összes lehetséges megoldások halmazát) hatékonyabban be tuda járni. Minél változatosabb genetikus m˝uveletekkel tudjuk felruházni az algoritmust, az annál gyorsabban és biztosabban konvergál az optimális megoldáshoz. 10

Gráfszínezés adaptív evolúciós algoritmusokkal

1.2.2. A természetes szelekció kontrollálása A hagyományos EA algoritmusokban használt szelekciós (másnéven kiválasztás) m˝uvelet a populáció átlagos min˝oségét hivatott javítani. A szelekció alapja az a megfigyelés, hogy jobb egyedeknek sokkal inkább lehetnek jobb utódaik, azaz a szül˝ok és az utódok fitnessz-értékei közt korreláció mutatható ki. Számos szelekciós séma található a szakirodalomban, a m˝uveletek egy része matematikai vizsgálatok eredménye, más része a természetben található szelekciókhoz hasonló. A szelekciós m˝uveleteket a következ˝oképpen csoportosíthatjuk: • Fitnesszarányos szelekció, amely az egyedeket fitnessz értékük arányában választja ki a sz˝ul˝ok állományának elkészítéséhez. Ilyenek a rulett szelekció, sztochasztikus univerzális mintavétel illetve a csonkolásos szelekció (H APP [6], P OLI [23]) . • Sorrend alapú szelekció, amely az egyedeket fitnessz értékük alapján sorrendbe rendezi, és a sorrendiséget használja fel alapul. Ez a módszer biztosítja, hogy ne keletkezzenek „szupermegoldások” és hogy a populáció változatossága megmaradjon. Ilyen m˝uveletek a verseng˝o szelekció illetve a lineáris sorrend alapú szelekció (B LICKLE et al., 1997). Mivel a javasolt algoritmusunk b˝ovebb m˝uveletkészlettel rendelkezik, a szelekciós m˝uveletnek nemcsak m˝uvelet típusra kell vonatkoznia, hanem konkrét m˝uveletre. 1.2.2. Definíció. Egy P populáció egyedeit rendezzük sorba fitnesszértékük alapján csökken˝o sorrendben. A legnagyobb fitnesszérték˝u egyed az 1., a következ˝o a 2., a legkevésbé ígéretes egyed a legnagyobb sorszámot kapja. Az ei egyed rank(ei ) rangján az egyed sorszámát értjük. Az effajta rangsorolás biztosítja, hogy az egyedeket sorrendi-alapon, mégis fitnesszarányosan értékeljük, amely független a fitnesszértékek egymáshoz való viszonyától. 1.2.3. Definíció. Vegyünk (e1 , e′1 ) . . . , (en , e′n ) egyedpárokat az evolúció bármely szakaszából úgy, hogy ei ∈ Pk és e′i ∈ Pk+1 azaz egymás utáni generációkban szerepelnek és e′i = M(ei ) azaz e′i az ei M típusú mutációja. Ekkor az M mutáció fittségén a n

1 X rank(e′i ) fit(M) = n i=1 rank(ei ) értéket értjük. 1.2.4. Definíció. Vegyünk (e11 , e21 , e′1 ) . . . , (e1n , e2n , e′n ) egyed-hármasokat az evolúció bármely szakaszából úgy, hogy e1i , e2i ∈ Pk és e′i ∈ Pk+1 azaz egymás utáni generációkban szerepelnek, továbbá e′i = C(e1i , e2i ) azaz e′i az e1i és e2i szül˝ok keresztezésével áll el˝o. A C keresztezés fittségén ekkor a n

n

rank(e′i ) rank(e′i ) 2X 1X   = fit(C) = n i=1 rank(e1i ) + rank(e2i ) n i=1 rank(e1i ) + rank(e2i ) 2 valós értéket értjük. 11

Gráfszínezés adaptív evolúciós algoritmusokkal A genetikus m˝uveletek fittségét tehát a m˝uvelet eredményeképpen kapott egyed illetve a kiindulási / szül˝o egyedek rangjának hányadosaként számíthatjuk. Mivel egy m˝uveletet többször is alkalmazhatunk, a kapott hányadosokat átlagolni kell. Ez a számérték kifejezi, hogy az adott keres˝o m˝uvelet milyen hatással van az egyedek rangjára. Amennyiben egy O operátor (legyen az mutáció / keresztezés vagy egyéb m˝uvelet) fittsége kisebb, mint 1, várhatóan rosszabb egyedeket hoz létre, mint a kiindulási egyed(ek). Ha ez az érték jóval nagyobb, mint 1, a szóban forgó m˝uvelet a kiindulási egyedek rangját megnöveli, azaz várhatóan jobb egyedeket hoz létre. A genetikus operátorok fittségét minden új populáció készítésekor újra kell számolni az új adatok tükrében. A m˝uveletek fittségének bevezetésével elérhet˝o, hogy az evolúció minden egyes szakaszában a keres˝o m˝uveletek is alkalmazkodjanak a változó kritériumokhoz – azaz az algoritmus maga is adaptív legyen. Algoritmus. ( Evolúciókövet˝o szelekció ) 1. Verseng˝o szelekció (tournament selection, lásd W IKIPEDIA [28]) használatával határozzuk meg az XP , MP , EP halmazokat a P populáció egyedeinek fittsége alapján. Az XP sz˝ul˝oi állományba azon egyedek tartozzanak, amelyeken keresztezést kívánunk végrehajtani. MP illetve EP halmazok alkotják a mutációs állomány és egyéb állományt, amelyeken mutációt és egyéb keres˝o m˝uveleteket hajtunk végre. 2. Az XP , MP , EP halmazokon belül hajtsunk végre sztochasztikus univerzális mintavételt (SUS, BAKER [10]), felhasználva az adott halmazokra vonatkozó keres˝o m˝uveletek fittségét. A vázolt algoritmus helyét az evolúciós kereteljárásban a 1.2.ábra mutatja.

1.2. ábra. A b˝ovített algoritmus evolúciókövet˝o szelekciós sémája

12

Gráfszínezés adaptív evolúciós algoritmusokkal

1.2.3. A keres˝omuveletek ˝ alkalmazása Az evolúciókövet˝o szelekció által meghatározott m˝uveletek végrehajtása korántsem triviális. A szelekció során minden egyedhez hozzárendeltünk 1-1 keres˝om˝uveletet, az ei egyedhez jelölje ezt Ol . Amennyiben Ol egyoperandusú (pl. mutáció vagy törlés), azt minden további nélkül végrehajthatjuk. A m˝uvelet eredményeképpen kapott utódo(ka)t felhasználjuk az új populáció kialakítása során, majd az Ol m˝uvelet fittségét újraszámítjuk. Ha Ol keresztezés, m˝uködéséhez (legalább) 2 szül˝o szükséges, így az ei egyedhez szükséges további egyed(ek) kiválasztása. További szül˝onek válasszunk véletlenszer˝uen olyan ej egyedet, amelyhez a szelekció ugyancsak az Ol keres˝om˝uveletet rendelte. Nyilvánvalóan ez jó választás lesz, hiszen mindkét egyeden a kijelölt m˝uveletet hajtjuk végre. Amennyiben nem található ilyen egyed ( az adott Ol keresztezés m˝uveletet csak az ei egyedhez rendeltük ), válasszunk véletlenszer˝uen olyan egyedet, amelyhez keresztezés m˝uveletet rendeltünk. Ekkor a szül˝ok bár nem „egymásnak” lettek kiválasztva, a szül˝oi joguk megvan, így a keresztezés várhatóan sikeres lesz. Egyébként válasszunk tetsz˝oleges egyedet az aktuális populációból. Természetesen több szül˝o választása esetén a választási stratégia triviálisan kiterjeszthet˝o.

1.2.4. Párhuzamosítási lehet˝oségek A keretrendszer számos pontján lehet˝oség van a párhuzamosítás által elérhet˝o gyorsítások alkalmazására. A keretrendszert úgy terveztük, hogy elosztott rendszereken, osztott memóriás programozási környezetben könnyen implementálható legyen. A megvalósítás során az ún. „farmer-worker” sémát javasoljuk, ahol a farmer a központi egység, amely a részproblémákat szétosztja a worker-k között, majd a kiszámított megoldásokat egyesíti. A kezd˝opopuláció létrehozásakor minden egyed létrehozása független egymástól, így az tökéletesen párhuzamosítható. Megjegyezzük azonban, hogy egyszer˝u ( pl. uniform véletlen generálás ) egyedlétrehozás esetén ez nem ajánlott, hiszen a kommunikációs többlet akár lassíthatja is a feldolgozást. A genetikus operátorok alkalmazása ugyancsak független a többi egyeden végrehajtandó operátoroktól, így tökéletesen párhuzamosítható. Ez igen nagy sebességnövekedést jelenthet olyan esetekben, amikor a keres˝o m˝uveletek nem egyszer˝u bitm˝uveletek, hanem bonyolultabb algoritmusok. Az evolúciókövet˝o szelekció során az ismertetett algoritmus 1. pontja által szolgáltatott XP , MP , EP halmazok elemeinek számításához kizárólag a P populációra van szükség, így tökéletesen párhuzamosítható. A 2. pont SUS eljárása pedig a halmazok egyedein függetlenül végrehajtható, így párhuzamosítható. Természetes módon minden egyed fitnesszértékének kiszámítása elvégezhet˝o elosztott rendszereken, hiszen két különböz˝o egyed fitnesszértéke független egymástól. A keres˝o m˝uveletek fittségének kiszámítása definíció szerint ugyancsak az adott m˝uvelet szül˝o és utód egyedeit˝ol függ, így elosztott rendszereken elvégezhet˝o. Megjegyezzük, hogy abban az esetben, ha a genetikai m˝uveletek száma nagyságrendekkel kisebb, mint az elosztott rendszerben rendelkezésre álló feldolgozó egységek száma, a párhuzamosítás lassíthatja a számítást.

13

2. fejezet Gráfszínezés, ismert gráfszínez˝o heurisztikák 2.1. A gráfszínezési probléma 2.1.1. Definíció. Egy G = (V, E) gráf jó színezése alatt annak minden csúcsához egy nemnegatív egész szám (szín) hozzárendelését értjük, mégpedig úgy, hogy a szomszédos csúcsok színei különbözzenek. Ez egy F : V 7→ N leképezést jelent, amelyre az (u, v) ∈ E ⇒ F (u) 6= F (v) összefüggés fennáll. A továbbiakban feltesszük, hogy |V | = n és |E| = m. A gráfszínezés modellként szolgál a következ˝o típusú feladatokban fellép˝o konfliktusok feloldására. Tegyük fel, hogy egy adott V halmazban bizonyos elemek páronként inkompatibilisek, a cél pedig nem más, mint minimális számú partícióra osztani V -t oly módon, hogy az egy partícióba es˝o elemek kompatibilisek egymással. A feladatot modellezhetjük egy G = (V, E) egyszer˝u gráf segítségével, ahol a csúcsok V halmaza a feladatban szerepl˝o elemeknek felel meg, és az E élhalmaz az inkompatibilis elemeket összeköt˝o éleket tartalmazza. Ekkor a V halmaz k számú partícióra bontása megfelel a G gráf legfeljebb k színt felhasználó jó csúcs-színezésének. Egy másik példa lehet egy cél eléréséhez szükséges részmunkák ütemezése is. Ekkor feltesszük, hogy bizonyos V részmunkák között ismert egy függ˝oség reláció, amely megszabja, hogy egy v1 ∈ V részmunkába csak u1 , . . . , un részmunkák elvégzése után lehet belefogni. Ekkor ha elkészítjük a G = (V, E) gráfot, ahol E = {(ui, vi )} ui , vi ∈ V ⇔ ui -tól függ vi , továbbá meghatározzuk a minimális k színt felhasználó csúcs-színezését, akkor az egy színt kapott részmunkákról elmondható, hogy egy id˝oben elvégezhet˝oek. Egy általános gráf minimális színb˝ol álló jó színezésének megtalálása NP-nehéz probléma (G AREY [15]). Nemcsak hogy nehéz ilyen színezést találni, de még ennek megközelítése is igen költséges (C RES [19]). A gyakorlatban viszont a szekvenciális mohó heurisztikák elegend˝oen hatékonynak bizonyultak (C OLEMAN [25]).

14

Gráfszínezés adaptív evolúciós algoritmusokkal

2.2. Gráfok hatékony reprezentációja Az algoritmusainkat gráfokon szeretnénk futtatni, így szükséges megadni azt a struktúrát, amellyel tetsz˝oleges irányított vagy irányítatlan gráfot számítógépeken reprezentálni tudunk . Gráfok reprezentálására több lehet˝oségünk is van, az egyik az ún. éllista használata. Ekkor minden csúcsot megszámozunk 0-tól |V | − 1 -ig, majd létrehozunk minden csúcshoz egy-egy láncolt listát, amelyekben az adott csúcs szomszédait tároljuk. Szomszédsági mátrix használatával is le tudunk írni tetsz˝oleges gráfot, ha azt a következ˝oképpen definiáljuk:   1 ha(i, j) ∈ E IG (i, j) = 0 ha(i, j) ∈ /E Ha G éls˝ur˝usége magas, a szomszédsági mátrix, ritka gráfok esetén az éllista használata javallott a sebesség és memóriaigény alacsonyan tartása végett. Mindkét reprezentáció alkalmas irányított és irányítatlan gráfok megadására, hiszen külön kezeljük az (i, j) és (j, i) éleket, így mindkett˝ot felvehetjük (irányítatlan), vagy elhagyhatjuk az egyiket (irányított). Mivel gráfszínezési problémákat vizsgálunk, az irányítottság nem számít hiszen egy él - legyen az irányított vagy irányítatlan - két végpontja ígyis-úgyis különböz˝o szín˝u kell, hogy legyen. Ezért érdemes a következ˝o, módosított szomszédsági mátrixot használni, amely mindig fels˝o-trianguláris:   0 ha i ≥ j ′ IG (i, j) = 1 ha i < j és (i, j) ∈ E | (j, i) ∈ E Az algoritmusainkat és teszteléseinket MATLAB környezetben gondoltuk megvalósítani, így a gráf reprezentációnkat is ezen környezeten belül szükséges megadnunk. Ritka mátrixok optimális tárolására a MATLAB sparse függvényét használjuk, amely gyors elérést biztosít, továbbá a felesleges memóriaigényt kiküszöböli. A gráfszínezési problémákat általában DIMACS formátumban prezentálják (lásd [5] DIMACS), így szükséges volt ezen formátumból való beolvasásra is. Az alábbi kód egy ilyen formátumú problémát olvas be, majd megjeleníti a reprezentációnkat. A kapott reprezentációt a display_graph függvénnyel grafikusan is megkaphatjuk. >> load_graph(’../tests/homer.col’) Graph (V,E) : (561,3258) - undirected DIMACS #1 ans = Problem: D: OptimalC: Directed:

’homer.col’ [561x561 double] 13 0

>> display_graph(ans) A 2.1. ábrán Homérosz Iliász cím˝u m˝uvéb˝ol származó gráf reprezentációját láthatjuk. A gráf csúcsainak a m˝uben szerepl˝o személyeket definiálták, míg két személy között 15

Gráfszínezés adaptív evolúciós algoritmusokkal homer.col

500

400

300

200

100

0

0

100

200

300

400

500

2.1. ábra. A homer.col problémát leíró gráf reprezentáció akkor és csakis akkor van él, ha a m˝uben legalább egyszer találkoznak egymással. További hasonló, irodalmi m˝uvek - úgy mint Tolsztoj Anna Kareninája (anna.col), Mark Twain Hucleberry Finnje (huck.col) és Dicken David Copperfieldje (david.col) által ihletett gráfokat készített Donald Knuth, amelyek ugyancsak megtalálhatóak abban az adatbázisban, amelyet kés˝obb széleskör˝uen használni fogunk.

2.3. A mohó színezés algoritmusa A gráfszínezési problémákra alkalmazott mohó algoritmus a gráf csúcsait egy adott sorrendben színezi ki, megpedig úgy, hogy mindig a legkisebb érvényes színt használja. Algoritmus. (Mohó színezés) 1: Jelöljük a használható színeket 1, . . . , n számokkal 2: Tekintsük a csúcsok egy tetsz˝oleges (v1 , v2 , . . . , vn ) sorrendjét 3: for i = 1 to n do 4: C ← i csúcs színezett szomszédainak színhalmaza 5: szin(i) ← min({1, . . . , n}\C) 6: end for Az algoritmus által szolgáltatott színezés min˝osége nagyban függ a csúcsok sorrendjét˝ol. A mohó algoritmus általában nem ad optimális megoldást, s˝ot közelít˝o mértéke sem kielégít˝o, hiszen megadható olyan gráf és olyan csúcssorrend, hogy a használt színek száma a csúcsok számával megegyezik (pl. Crown-gráf), azonban tetsz˝oleges gráfhoz megadható olyan csúcssorrend, amely esetén optimális megoldást kapunk (H AJNAL [8]). A mohó algoritmusra épül˝o heurisztikák kizárólag a csúcssorrend minél alkalmasabb megadására törekszenek. A csúcsok sorrendben való felsorolása (first fit - FFIT), illetve a csúcssorrend véletlen generálása (random vertex ordering - RANDO) a két triviális heurisztika. A két heurisztika id˝oigénye O(|V | · |E|), hiszen minden csúcsra meg kell vizsgálni a szomszédok színeinek minimumát.

16

Gráfszínezés adaptív evolúciós algoritmusokkal

2.3.1. Fokszámokon alapuló algoritmusok 2.3.1. Definíció. Egy G = (V, E) gráf v ∈ V csúcsának fokszáma a v csúcs szomszédainak számával egyezik meg. A mohó algoritmus általában belefut olyan esetekbe, amikor egy nagyobb fokszámú csúcs minden szomszédja színezett. Ekkor el˝ofordulhat, hogy olyan színt kell használni amely megnöveli a színezésben használt színek számát. Érdemes tehát el˝oször a nagyobb fokszámú csúcsokat kiszínezni. A csúcsok csökken˝o fokszám szerinti rendezésével (largest degree ordering - LDO) jobb közelít˝o eredmények érhet˝oek el, mint azt majd látni is fogjuk. Az LDO heurisztika id˝oigénye T = |V ||E| + |V | log |V | + |V ||E| = |V |(2|E|+log |V |) = O(|V |·|E|), amely a fokszámok kiszámításából, azok rendezéséb˝ol, majd a mohó algoritmus futtatásából tev˝odik össze. 2.3.2. Definíció. Egy G = (V, E) (nem feltétlenül teljesen) színezett gráf esetén egy v ∈ V csúcs incidencia fokát a v csúcs színezett szomszédainak számával definiáljuk. A színezés minden pontján szeretnénk biztosítani azt, hogy egy csúcs színezésére minél kevesebb korlátozó feltétel legyen érvényben, azaz minél kevesebb szomszédja legyen színezve. A fenti definíció használatával adódik a csúcsok csökken˝o incidenciafok szerinti rendezésének (incidence degree ordering - IDO) használata. A színezés minden lépése után ki kell számítani a csúcsok incidenciafokát, amely a mohó színezéssel együtt T = |V |2 |E| + |V |2 log |V | + |V ||E| = O(|V |2 |E|) futásid˝ot eredményezne. A futásid˝ot lecsökkenthetjük O(|V | · |E|) -re, ha egy csúcs színezésekor a szomszédainak incidenciafokát eggyel növeljük, ahelyett, hogy minden iterációban azt minden csúcsra újraszámolnánk. Az IDO heurisztikát továbbfejleszthetjük, ha a korlátozó feltételeket jobban megvizsgáljuk. Egy csúcs színezését a szomszédainak színe korlátozza. Azonban külöbség van vi és vj csúcsok korlátai között, ha vi színezett szomszédainak színe ugyanaz, és vj színezett szomszédainak színe mind különböz˝o. Nyilvánvaló, hogy vj -re er˝osebb korlátok vannak szabva, így a színezés során ezt a csúcsot szükséges el˝orébb venni. 2.3.3. Definíció. Egy G = (V, E) (nem feltétlenül teljesen) színezett gráf esetén egy v ∈ V csúcs szaturációs fokát a v csúcs különböz˝o színekkel színezett szomszédainak számával definiáljuk. A szaturációs fokszám szerint csökken˝o sorrendben vett mohó algoritmus ( saturation degree ordering - SDO ) futásideje O(|V |2 |E|). Ez sajnos nem csökkenthet˝o, hiszen egy színezés alkalmával minden csúcsra újra kell számítani a szaturációs fokszámot.

2.3.2. A heurisztikák kombinálásának lehet˝oségei Az ismertetett heurisztikák (LDO, IDO, SDO) a csúcsokat adott szempont szerint monoton csökken˝o rendezésben szolgáltatják. Mivel a monotonitás nem szigorú, el˝ofordulhat olyan eset, hogy több csúcs fokszáma / incidenciafoka / szaturációs foka megegyezik. Ekkor a heurisztikák bejárási sorrend alapján választanak ezen csúcsok közül, azaz általában a csúcsok indexelése szerint növekv˝o sorrendben. A heurisztikákat ilyen ekvivalenciák esetén kombinálhatjuk egymással. Használhatjuk az LDO heurisztikát, majd mikor több csúcs fokszáma megegyezik, közülük IDO heurisztika alapján választunk.

17

Gráfszínezés adaptív evolúciós algoritmusokkal Hasonló módon az IDO és SDO algoritmusokban fokszámegyezés esetén más és más heurisztikákat alkalmazhatunk. Kés˝obbi tesztjeink során két kombinációt vizsgálunk: • LIDO. Használjuk az LDO heurisztikát. Csúcsok fokszámának egyezése esetén incidencia-fok alapján válasszunk. Az algoritmus futásideje a használt heurisztikákból adódóan O(|V ||E|). • SLDO. Használjuk az SDO heurisztikát, majd a csúcsok szaturációs fokszámának egyezésekor nagyobb fokszám szerint válasszunk közülük. Mivel az SDO heurisztika dominál, a futásid˝ot is ez határozza meg, így az SLDO algoritmus O(|V |2 |E|)-es futásid˝ovel rendelkezik.

2.3.3. MATLAB megvalósítások A mohó algoritmuson alapuló heurisztikákat a color_heuristic függvényben valósítottuk meg. A függvénynek két paramétere van, a gráfszínezési probléma, illetve a használni kívánt heurisztika. A MATLAB eljárás egy struktúrát ad vissza, amelynek C mez˝oje egy konkrét színezést, x mez˝oje a visszaadott színezésben használt színek számát jelenti. >> P = load_graph(’../tests/queen5_5.col’); Graph (V,E) : (25,320) - undirected DIMACS #1 >> R = color_heuristic(P,’sdo’) R = x: 8 C: [1 2 3 4 5 3 4 1 2 6 2 5 6 3 1 6 1 2 5 4 4 7 8 1 2] >> A color_heuristic függvény második paramétereként az ffit, ldo, sdo, ido, lido, sldo és rando értékek használhatóak, amelyek a megfelel˝o heurisztikákat jelentik. A függvény pontosabb használatáról a help color_heuristic paranccsal kapunk b˝ovebb tájékozatást. A színezés érvényességér˝ol az is_valid_coloring eljárás segítségével bármikor meggy˝oz˝odhetünk. Az eljárás igazat ad vissza, ha a színezés jó, egyébként hamisat: >> P = load_graph(’../tests/mulsol.i.3.col’); Graph (V,E) : (184,3916) - directed >> R = color_heuristic(P,’sldo’) R = x: 32 C: [1x184 double] >> is_valid_coloring(P.D,R.C) ans = 1 >>

18

Gráfszínezés adaptív evolúciós algoritmusokkal

2.4. Maximális független csúcshalmazon alapuló szekvenciális algoritmus 2.4.1. Definíció. Egy G = (V, E) gráf esetén egy H ⊂ V csúcshalmaz független csúcshalmaz, ha minden u, v ∈ H csúcsra teljesül, hogy u nem szomszédja v-nek. Egy független csúcshalmaz méretét a H halmaz elemszámával definiáljuk. Egy H független csúcshalmaz maximális, ha bármely új csúcs hozzáadásával H már nem alkot független csúcshalmazt. Egy független csúcshalmaz definíciója alapján egyetlen színnel színezhet˝o. Minél nagyobb az adott halmaz elemszáma, annál kevesebb csúcs marad a következ˝o színekhez, így ezen megfigyelésekb˝ol felépíthetjük a következ˝o algoritmust: Algoritmus. (Független csúcshalmazok törlése) 1: H ← V 2: col ← 1 3: while H nem üres do 4: Számítsunk ki egy HM F ⊆ H minél nagyobb elemszámú maximális független csúcshalmazt 5: szin(vi ) ← col ∀vi ∈ HM F 6: col ← col + 1 7: H ← H\HM F 8: end while Az algoritmus futásigénye nagyban függ a maximális független csúcshalmaz keresésének módszerét˝ol. Keressük a halmazt xT ∈ {0, 1}n vektorok formájában. Egy ilyen x vektor egyértelm˝uen meghatároz egy halmazt, hiszen HM F = {i | xi = 1}. Mostmár csak biztosítanunk kell, hogy x olyan koordinátáin legyenek egyesek, hogy azok által meghatározott pontok maximális független csúcshalmazt alkossanak, továbbá x minél több 1-est tartalmazzon. Az els˝o feltétel biztosításához vegyük az élek egy sorrendjét e1 , . . . , em . Az   1 ha ei él egyik végpontja vj m×n A(i, j) ∈ {0, 1} = 0 egyébként mátrix bevezetésével egy bináris egészérték˝u lineáris programozási modellt állíthatunk fel: n X min −xi feltéve, hogy i=1

A · x ≤ [1, 1, . . . 1]T és xT ∈ {0, 1}n A célfüggvény egyértelm˝uen kifejezi azt, hogy minél több 1-est szeretnénk x-ben, a feltétel pedig garantálja, hogy páronként éldiszjunkt elemeket tartalmazzon, ellenkez˝o esetben az A · x oszlopvektor legalább egy koordinátáján 2-es állna, amely nem elégítené ki a korlátozó feltételt. A fenti LP feladatot az Optimization Toolbox által szolgáltatott bintprog eljárással oldottuk meg. A color_seqdel függvény pedig ezt felhasználva megoldja a paraméterében kapott gráfszínezési feladatot az ismertetett algoritmussal. 19

3. fejezet Gráfszínezés evolúciós algoritmusokkal Az evolúciós algoritmus egy általános kereteljárás, így egy adott probléma esetén szükséges megmondani az alkalmazott fitnesszfüggvényt, az egyedek kódolását, a mutációs és keresztezés m˝uveleteket, illetve a futtatást befolyásoló egyéb paramétereket.

3.1. Az egyedek kódolása és a fitnesszfüggvény Egy gráf színezéséhez reprezentálnunk kell egy adott színezést minden egyedben, mégpedig úgy, hogy egy egyed egyértelm˝uen azonosítson egy színezést, és egyértelm˝uen el lehessen dönteni, hogy az adott gráfra nézve a színezés jó-e, vagy sem. Egy ilyen reprezentáció tökéletesen alkalmas jó színezés megtalálására, hiszen a fitnesszfüggvényt definiálhatjuk a színezésben el˝oforduló „hibák” számaként. Minimális színt használó jó színezés keresésére azonban garantálnunk kell minden egyedre, hogy az jó színezést reprezentál. A következ˝o algoritmusokban is ezt a megközelítést használtuk. Minden egyed a problémában szerepl˝o gráf egy jó színezését jelenti. Az egyedeket egy n-dimenziós sorvektorként reprezentáljuk, egy e egyed 1 ≤ j ≤ n-edik komponense megadja a j-edik csúcs színét. A kezd˝opopuláció kialakítására több módszer is lehetséges: 1. A kezd˝opopulácó minden egyede az (1, 2, . . . , n) vektor egy véletlen permutációja lesz. Ez nyilván alkalmas hiszen minden csúcs színezett, továbbá a színezés is jó, hiszen minden csúcs színe különböz˝o. Ez a módszer kell˝oen diverz kezd˝opopulációt hoz létre, így a globalitás szempontjából jó választás. Ugyanakkor valószín˝usíthet˝o, hogy az optimális megoldástól igen távoli egyedeket hoz létre, így a futásid˝ore és a konvergenciára nézve rossz hatással lehet. 2. A kezd˝opopuláció minden egyedét egy véletlen csúcssorrendet használó mohó színezéssel (RANDO) generáljuk. Ez a módszer is lehetséges megoldásokat hoz létre, továbbá garantálja, hogy az evolúciós algoritmus legalább olyan jó eredményt fog adni, mint a RANDO eljárás. A fitnesszfüggvényt illet˝oen a célunk az, hogy olyan egyedeket evolváljunk, amelyek minél kevesebb színt használnak. Ezt vizsgálhatjuk az egyedben el˝oforduló maximális szín értékével: f it(e) = arg max ei . i

20

Gráfszínezés adaptív evolúciós algoritmusokkal Ezen választás el˝onye, hogy a célfüggvényünk nagyon gyors, viszont garantálnunk kellene az algoritmus minden pontján, hogy minden e egyedben az 1, 2 . . . , f it(e) színek el˝ofordulnak. Ez igen nagy megkötés a genetikus keres˝o m˝uveletekre nézve, így inkább definiáljuk fitnesszfüggvényünket a f it(e) = |S|, S = {k | ∃ i : ei = k} összefüggés alapján, amely egy egyedhez a benne szerepl˝o diszjunkt színek számát rendeli fitnesszértékként.

3.2. A javasolt genetikus keres˝omuveletek ˝ A keresztezés m˝uveletekhez két eljárást készítettünk, a szükséges szül˝o egyedeket jelölje s1 , s2 . 1. Az els˝o módszer véletlen sorrendben végighalad a gráf csúcsain, majd egy véletlen r változó alapján vagy s1 vagy s2 alapján színezi ki az adott csúcsot. El˝ofordulhat olyan eset, amikor egyik szül˝o adott csúcsra vonatkozó színe sem használható, ilyenkor a csúcs szomszédainak színezése alapján a legkisebb használható színt használjuk. Belátható, hogy ez az eljárás két jó színezésb˝ol egy harmadik jó színezést csinál, mégpedig úgy, hogy felhasznál bizonyos információkat a megadott két színezésb˝ol. 2. A második módszer elkészít egy H1 , H2 , . . . , Hl halmaz-sorozatot, ahol Hi = {v ∈ V | s1,v = i vagy s2,v = i}, azaz Hi halmaz azon csúcsokat tartalmazza, amely vagy s1 vagy s2 szül˝oben i szín˝u. A Hi halmazokat sorrendben, azok elemeit véletlenszer˝uen végigvizsgálva, az adott csúcsokhoz a meghatározott színeket rendeljük, ha lehetséges. A végén el˝ofordulhatnak olyan csúcsok, amelyek nem lettek színezve, ezekhez a legkisebb alkalmas színt rendeljük. Ez utóbbi eljárás el˝onyben részesíti a kis színnel színezett csúcsokat, ezáltal megpróbálva egy olyan egyedet kreálni, amely kisebb színeket használ, mint szül˝oi. A mutációs m˝uveletekre a következ˝o eljárásokat használtuk: 1. A mutációra kiválasztott egyed bizonyos génjét (a gráf egy csúcsának színét) egy véletlen változó alapján vagy a legkisebb használható színre cseréljük, vagy nem változtatjuk. Nyilvánvaló, hogy így nem hozhatunk létre rosszabb egyedet, mint a kiindulási egyed, ezáltal ez egy igen hatékony keres˝o eljárás. Speciális esetben azonban a szül˝ovel ekvivalens egyedet is létrehozhatunk, így ezen eljárás egyedüli használata nem biztos, hogy elegend˝o. 2. A második mutációra javasolt eljárás a következ˝oképpen m˝uködik. Keressük meg a szül˝o egyed által leírt színezésben a legkevésbé használt szín(eke)t (a használt színek közül). Azokat a csúcsokat, amelyek ilyen szín˝uek, próbáljuk meg a legkisebb használható színre színezni. 21

Gráfszínezés adaptív evolúciós algoritmusokkal 3. A harmadik eljárás igen egyszer˝u, mégis igen hasznos. Ha a kiindulási egyedben el˝oforduló színek számát sn -el jelöljük, akkor az eljárás az egyed csúcsait újraszínezi oly módon, hogy az csak az 1, 2, . . . , sn színeket használja. Ez tulajdonképpen színek átalakítását jelenti, a színezés topológiáját nem változtatja meg, azonban a populációba új géntartalmat visz, így a diverzitásra igen jó hatással lehet. A populáció méretét tekintve a 20, 25, 30 illetve 40 értékekkel dolgoztunk, az elitek számát 2-nek, a keresztezés valószín˝uségét Pxover = 0.8 -nek vettük. A sztenderd EA esetén sztochasztikus univerzális mintavételt használtunk szelekcióra, fitnesszérték-skálázásra pedig a rang függvényt (lásd H OPGOOD [9]) választottuk. A fent megadott eljárások tükrében az alábbi EA változatokat hoztuk létre: • STEA. A kereteljárás a sztenderd evolúciós algoritmus, genetikus m˝uveletekhez pedig a keresztezés és mutációs m˝uveletek közül az 1. sorszámú eljárásokat használjuk. • EKG1 - B˝ovített EA(1,1). Az evolúciókövet˝o szelekciót, illetve az els˝o keresztezés és mutációs m˝uveletet használunk. Ezen algoritmus csak a szelekciós sémát illet˝oen különbözik a sztenderd változattól, így jól megfigyelhetjük a módosításaink hatását az eredményekben. • EKGN - B˝ovített EA(2,3). Az evolúciókövet˝o szelekciót használjuk mindkét keresztezés és mindhárom mutációs m˝uvelettel együtt. Ezen algoritmus tartalmaz minden javasolt újítást.

3.2.1. Evolúciós algoritmusok a MATLAB-ban Ami a sztenderd változatot illeti, azt a MATLAB-hoz elérhet˝o Genetic Algorithm and Direct Search Toolbox segítségével készítettük el. Ezen kiegészít˝o tartalmaz egy igen széleskör˝uen konfigurálható ga sztenderd EA-t, amely számos alkalmazásban bizonyította „rátermettségét”. Mivel ez egy kipróbált, sokak által tesztelt megvalósítás, jó alapot fog képezni kés˝obbi összehasonlításainkhoz. Az általunk elkészített color_ga2 eljárás ez utóbbin alapul, használva az el˝oz˝oekben ismertetett genetikus m˝uveleteket és beállításokat. Mivel az evolúciós algoritmusok viselkedését is szeretnénk nyomonkövetni, statisztikai adatokat is gy˝ujtünk a futtatások során, ezt a ga2_output_fcn kiegészít˝o függvény végzi. A sztenderd változatnak opcionálisan paraméterül adhatjuk a kezd˝opopuláció készítéséhez használandó függvényt, a maximum iterációk számát, a populáció méretét éppúgy mint a keresztezési rátát és elitek számát. Egy probléma megoldása: >> P = load_graph(’../tests/queen6_6.col’); Graph (V,E) : (36,580) - undirected DIMACS #1 >> [R,S] = color_ga2(P,[1 100 20 .8 3]) R = C: [1x36 double] x: 10 S = Fits: [20x51 double] 22

Gráfszínezés adaptív evolúciós algoritmusokkal DVariance: DMean: D: BestFits: FVariance: FMean: ElapsedTime: Generations: FitCount:

[1x51 double] [1x51 double] [20x20 double] [1x51 double] [1x51 double] [1x51 double] 3.0028 51 1040

>> Az S struktúrában megkapjuk az egyes iterációkban kiszámított statisztikai értékeket úgy mint a fitnesszértékek, azok minimuma, átlaga és varianciája, az egyedek távolságának átlaga és varianciája, az elvégzett iterációk száma, a célfüggvény-kiértékelése száma és a felhasznált processzorid˝o. Az evolúciókövet˝o szelekciót használó b˝ovített algoritmust az ekg.m fájlban található ekg eljárás valósítja meg. Az eljárásnak egyetlen beállításokat tartalmazó paramétere van, amelyet az ekgoptimset függvény használatával állíthatunk el˝o. A megvalósított algoritmust gráfszínezésre használja a color_ekg eljárás, amelynek két argumentuma a problémát leíró struktúra, illetve egy paremétervektor. Ez utóbbi a kezd˝opopulációra használandó függvényt (1 vagy 2), az iterációk maximális számát, a populáció méretét, illetve azt tartalmazza, hogy 1-1 (0) vagy több (1) keres˝om˝uveletet szeretnénk használni: >> P = load_graph(’../tests/myciel6.col’) Graph (V,E) : (95,755) - directed [R,S] = color_ekg(P,[2 100 30 1]); >> A futtatás során itt is statisztikai elemzést végzünk, a sztenderd változat által számított összes mutatót itt is számítjuk. Ha több keres˝om˝uveletet használunk, érdekes lehet tudni, hogy mikor, melyik m˝uveletb˝ol mennyit használtunk, illetve a m˝uveleteknek hogyan alakult a fitnesszértéke. Ezen információkat tartalmazza az eljárás által adott S struktúra OpsUsed és OpFits mez˝oje. A mért értékeket ezután könnyen kirajzolhatjuk: 1

20

0.8 Keresztezés 1 Keresztezés 2

15

Mutáció 1 Mutáció 2 10

Mutáció 3

5

0

0

20

40 Generációk

60

80

Müveletek fitnesszértéke

Müveletek alkalmazásának száma

25

0.6

0.4

0.2

0

0

20

40 Generációk

60

80

3.1. ábra. A keres˝o m˝uveletek használati mértéke és fitnesszértékük a generációk során

23

Gráfszínezés adaptív evolúciós algoritmusokkal

3.3. A b˝ovített eljárások verifikációja Az el˝oz˝o fejezetekben bemutatott módosított kereteljárás ellen˝orzéséhez annak használhatóságát fogjuk összemérni a sztenderd evolúciós algoritmussal. Vizsgálataink során három algoritmust fogunk összehasonlítani: a sztenderd EA-t, a b˝ovített kereteljárást 11 keresztezés és mutációs operátorral (ugyanazokat használva, mint a sztenderd kereteljárásban), valamint ez utóbbit több keresztezés és mutációs operátorral. Az evolúciós számításokban használt egyéb paramétereket (populációk száma, keresztezési ráta, elit egyedek száma, stb. lásd KOZA [12]) ugyanazon értékekre állítjuk, ezzel minimalizálva a vizsgálataink végeredményeinek hibáit. Tekintettel arra, hogy a dolgozat gráfszínezési problémák köré összpontosul, a verifikációt is ilyen témakörben végezzük. Az algoritmusokat ismert kromatikus számú gráfok színezése mellett vizsgáljuk. A tesztgráfokat egy ilyen célra kialakított adatbázisból nyertük ki (G RAPH C OLORING T EST DATABASE [7]): # Probléma 1. myciel6.col 2. myciel5.col 3. queen8_12.col 4. myciel7.col 5. mulsol.i.4.col 6. miles500.col 7. le450_5a.col 8. flat_300_26.0.col 9. fpsol2.i.1.col 10. le450_15b.col

| V | | E | Éls˝ur˝uség (%) 95 755 16 47 236 2 96 1368 30 191 2360 13 185 3946 23 128 1170 14 450 5714 5 300 21633 48 496 11654 9 450 8168 8

Kromatikus szám 7 6 12 8 31 20 5 26 65 15

3.1. táblázat. A verifikációra használt gráfok tulajdonságai A verifikáció során szükséges ellen˝orizni, hogy a b˝ovített kereteljárás milyen megoldást ad, illetve azt mennyi id˝o alatt számítja ki. 70 Optimális megoldás

60 Kromatikus szám

Sztenderd EA 50

Bövített EA(1,1) Bövített EA(2,3)

40 30 20 10 0

1

2

3

4

5 6 Tesztadatok

7

8

9

10

3.2. ábra. Az algoritmusok által szolgáltatott legjobb megoldások A tesztgráfokon lefuttatuk mind a három evolúciós algoritmust. Az eredményként kapott kromatikus számokat és futásid˝oket az alábbi táblázatok tartalmazzák. 24

Gráfszínezés adaptív evolúciós algoritmusokkal

Optimális megoldás Sztenderd EA B˝ovített EA(1,1) B˝ovített EA(2,3)

1 7 7 7 7

2 6 6 6 6

3 12 14 14 14

4 8 9 8 8

5 31 31 31 31

6 7 20 5 21 13 20 14 20 15

8 26 48 47 47

9 65 65 65 67

10 15 23 23 23

3.2. táblázat. Az algoritmusok által kiszámított megoldások A fenti táblázatból kiolvasható és a 3.2. ábráról leolvasható, hogy a sztenderd algoritmus háromszor adott rosszabb megoldást, és egyszer jobbat, mint a b˝ovített algoritmus 1-1 operátorral használva. A többoperátoros esetben az algoritmus hasonlóan muzsikált, csupán három esetben adott rosszabb megoldást, mint a sztenderd EA. Ez nem feltétlenül tudható be az algoritmus helytelen m˝uködésének - hiszen más esetekben jobb megoldást is szolgáltatott, mint a többi megvalósítás. Sztenderd EA B˝ov. EA(1,1) B˝ov. EA(2,3)

1 2 3 4 5 6 7 8 9 10 5.2 2.0 9.8 21.9 29.6 8.1 77.7 377.4 196.4 117.8 5.6 1.8 14.8 20.4 29.3 12.6 80.1 491.1 161.1 111.4 10.9 4.9 44.9 51.6 45.6 23.4 96.8 580.8 257.9 197.5

3.3. táblázat. Az algoritmusok futásideje 1, 667 Ghz-es processzoron másodpercekben A futásid˝ok összehasonlításához a 3.3. táblázatot vehetjük alapul. A sztenderd változat és a b˝ovített változat futásideje egy nagyságrend˝u, míg a több keres˝om˝uvelettel dolgozó algoritmus átlagosan másfélszer lassabb, mint társai. Ez a futásid˝okülönbség a keresési tér nagyobb bejárásából adódik. 600

600 Sztenderd EA Bövített 500EA(1,1) Bövített EA(2,3)

500

400 CPU idö (s)

CPU idö (s)

400

300

300

200

200

100

100

0

0

0.5

1

1.5 |E|

2

2.5 4

x 10

0

0

0.1

0.2 0.3 Elsürüség (%)

0.4

0.5

3.3. ábra. Az algoritmusok id˝oigénye az élszám és éls˝ur˝uség függvényében A 3.3. ábrán a futásid˝ok élszámtól és éls˝ur˝uségt˝ol való viszonyát jelenítettük meg. Látható, hogy mindhárom algoritmus ugyanúgy viselkedik, az élszámtól lineárisan függnek a futásid˝ok, éppen úgy, mint nagy éls˝ur˝uség esetén. Kis éls˝ur˝uség mellett pedig a csúcsszám határozza meg a futásid˝ot. 25

Gráfszínezés adaptív evolúciós algoritmusokkal Az algoritmus konvergenciájának illetve globalitásának vizsgálatához az evolúció során el˝oálló egyedek fitnesszértékeinek statisztikáit, illetve a populációk varianciáit szükséges vizsgálnunk. Ezt az 5. és 7. tesztgráfokon mutatjuk be.A választás azért ezen két tesztesetre esett, mert az 5. teszteseten mindhárom algoritmus jó megoldást adott, a 7. esetében pedig mindhárom különböz˝ot. 4

Fitnessz−érték variancia

10

150

100

50

0

20

40 Generáció

200

60

Egyedek átlagos távolsága

0

10

10

80

Bövített EA(2,3)

150

100

50

0

20

40 Generáció

60

80

0

10

20

30 40 Generáció

50

60

70

0

10

20

30 40 Generáció

50

60

70

4

Sztenderd EA Bövített EA(1,1)

0

2

10

−2

0

10 Egyedek távolságának varianciája

Egyedek fitnessz−értékei

200

3

10

2

10

1

10

3.4. ábra. Az algoritmusok statisztikái az 5.-ös teszteseten A 3.4. ábra bal fels˝o grafikonján a generációk során el˝oálló populációk egyedeinek fitnesszértékeit jelenítettük meg. A grafikonon megfigyelhet˝o, hogy a b˝ovített eljárások populációi mindig értékesebbek a sztenderd eljárás által kiszámítottaknál, továbbá a függvényalakok megegyeznek. Ugyanezen ábra jobb fels˝o grafikonján azt láthatjuk, hogy az egyes populációkban az egyedek fitnesszértékei mennyire térnek el a középértékt˝ol, átlagtól. Nyilván minél kisebb ez az érték, a célfüggvényértékek annál közelebb vannak egymáshoz, így konvergenciáról beszélhetünk. Látható, hogy a b˝ovített algoritmus mindkét futtatási módban jobb eredményt adott, mint a sztenderd algoritmus. Eredményeink alapján kijelenthet˝o, hogy a b˝ovített eljárás és a sztenderd evolúciós algoritmus konvergenciája megegyezik, s˝ot az el˝obbi általában jobban teljesít. A 3.4. ábra alsó két grafikonja az evolúció során el˝oálló egyedek átlagos távolságát illetve a távolságok varianciáját mutatja. Két színezés közötti távolságot azon csúcsok számával definiáltuk, amelyek a két színezésben különböz˝o színt kaptak. Minél nagyobb az egyedek közötti távolság és variancia, annál változatosabb a populáció, így a keresési teret annál szélesebben járjuk be. Az alsó grafikonok alapján további két fontos észrevételt tehetünk. A több operátorral m˝uköd˝o b˝ovített eljárás a lokális optimumokat sikerrel kerüli ki. Két ilyen pont fedezhet˝o fel a bal alsó grafikonon a 10. és 20. generáció környékén. Ezen 26

Gráfszínezés adaptív evolúciós algoritmusokkal pontokban az egyedek távolsága igen kicsi, és korai konvergenciáról beszélhetünk. Ezt az algoritmus jól korrigálja, a keres˝o m˝uveletek megfelel˝o használatával a populáció változatosságát újra megnöveli. Mindezalatt a konvergenciasebesség alig csökken. A második észrevétel a sztenderd és b˝ovített algoritmusok végs˝o stádiumban való viselkedésével kapcsolatos. A sztenderd algoritmus esetén az evolúció végén a populáció változatossága majdnem nullára csökken, ez annyit jelent, hogy egy konkrét színezésbe konvergál. A b˝ovített eljárások azonban megtartják a populáció változatosságát, így több különböz˝o optimumot szolgáltatnak. Ez egy nagyon jól kihasználható tulajdonság lehet az ún. többcélú optimalizálás (multiobjective optimization - A JITH [1], S ALEM [24]) területén, ahol több célfüggvény együttes használata mellett keressük az optimális megoldást. 4

10 Fitnessz−érték variancia

400 300 200 100 0

20

40 Generáció

Egyedek átlagos távolsága

500

60

0

10

10

80

Bövített EA(1,1) Bövített EA(2,3)

300 200 100

0

20

40 Generáció

60

80

0

20

40 Generáció

60

80

0

20

40 Generáció

60

80

5

Sztenderd EA

400

0

2

10

−2

0

10 Egyedek távolságának varianciája

Egyedek fitnessz−értékei

500

0

10

3.5. ábra. Az algoritmusok statisztikái a 7.-es teszteseten A 3.5. ábrán egy nehéz teszteseten történt futtatások statisztikát láthatjuk. Itt is megfigyelhet˝ok a konvergencia hasonlóságára, és a populációk diverzitására tett észrevételeink. A tesztadatokon elvégzett méréseink alapján kijelenthetjük, hogy a b˝ovített algoritmus mind teljesítményben, mind robusztusságban összemérhet˝o a sztenderd változattal, annál bizonyos esetekben jobb eredményt is szolgáltat, továbbá az evolúciós számításokban igen fontos viselkedésformák esetén is megfelel˝oen m˝uködik. A következ˝o fejezetben az eddig ismertetett algoritmusok összehasonlítására koncentrálunk, megvizsgáljuk azok teljesít˝oképességét valós gráfokon, illetve elemezzük teljesítményüket a bemeneti adatok paramétereinek függvényében.

27

Gráfszínezés adaptív evolúciós algoritmusokkal

3.4. A heurisztikák és evolúciós módszerek összehasonlító elemzése Az algoritmusok összehasonlításához szükségesek voltak olyan tesztgráfok, amelyeknek kromatikus száma ismert. A gráfokat a már említett G RAPH C OLORING DATABASE ([7]) adatbázisból nyertük, amely széleskör˝uen használt, verifikált tesztgráfokat tartalmaz. A gráfok kiválasztásakor ügyeltünk arra, hogy a csúcsszámok, élszámok, éls˝ur˝uségek és kromatikus számok széles spektrumon mozogjanak, minél többféle kombináció el˝oforduljon. A kiválasztott problémákat, illetve azok paramétereit a 3.5. táblázat tartalmazza.

3.4.1. Közelítési pontosságok a kromatikus számra A összehasonlítást két faktoron végeztük, a kapott kromatikus számok és a felhasznált processzorid˝ok voltak az összehasonlításaink alapjai. Az algoritmusok legjobb eredményeit mutatja be a 3.6. ábra. A fels˝o grafikon tartalmazza az összes gráfon az összes algoritmus eredményét. A tesztadatokat úgy sorszámoztuk, hogy kis sorszámot kapjanak a „könny˝u” problémák, míg nagyobbat a „nehezek”. Ez jól látható a grafikonokon is, hiszen a kis sorszámú esetekben a kapott értékek megegyeznek vagy alig térnek el a valódi kromatikus számoktól, míg a legmagasabb sorszámú esetekben a kapott kromatikus számok igen nagy eltérést mutatnak. 80 Kapott kromatikus számok

ffit rando 60

ldo sdo ido

40

lido sldo 20

stea ekg1 ekgn

0

5

10

15

20 25 Tesztadatok

25

30

35

40

45

χ(G)

50 40

20

30 15 20 10

5 29

10

30

31

32

33

34

35

36

37

0 38

39

40

41

42

43

44

45

3.6. ábra. Az algoritmusok által adott megoldások Az alsó két grafikon kiemeli a futtatások szempontjából érdekesebb tesztesetekre adott válaszokat. A bal alsó ábrán jól megfigyelhet˝o, hogy a heurisztikus algoritmusok közel azonos megoldásokat szolgáltattak, továbbá az is, hogy minden esetben az evolúciós 28

Gráfszínezés adaptív evolúciós algoritmusokkal

2

2

1.5

1.5 Relatív hiba

Relatív hiba

megoldások adták a legjobb eredményeket. Meglep˝o módon az ffit és rando eljárások többször is jobb eredményt adtak, mint akár az sldo vagy lido heurisztikák. A 3.6. ábra jobb alsó grafikonján a nehezebb tesztesetek szerepelnek. Az eljárások eredményei közötti különbség itt sem kisebb (csak az ordináta tengely beosztása más), viszont a valódi kromatikus számtól való távolság megn˝ott. Az er˝oviszonyok viszont továbbra is megmaradtak, az evolúciós megvalósítások az algoritmusok élmez˝onyében szerepelnek. Vizsgálatunk kiterjedt az eljárások min˝oségének probléma-függ˝oségére is. Megvizsgáltuk, hogy a kapott eredmények vajon korrelációban állnak-e a gráfszínezési problémák valamely paraméterével. A heurisztikus eljárások a gráfok topológiájára támaszkodnak, így érdemes lehet megvizsgálni, van-e, és ha igen, milyen kapcsolat a gráf felépítése, és az eljárások által adott eredmények min˝osége között. A 3.7. ábrán a valódi kromatikus számhoz tartozó relatív hibákat jelenítettük meg az élszám és éls˝ur˝uség függvényében.

1

0.5

0 1 10

1

0.5

2

10

3

10 E

4

10

5

10

0

0

10

20 30 40 Élsürüség ( % )

50

60

70

3.7. ábra. Az algoritmusok eredményeinek relatív hibája Jól látható, hogy semmiféle tendencia nem figyelhet˝o meg a grafikonokon, nem igaz, hogy nagyobb éls˝ur˝uség nagyobb relatív hibát, vagy kevesebb élszám kisebb hibát eredményezne, így kijelenthet˝o hogy az algoritmusok nem érzékenyek ezen két értékre. A vizsgálat eredménye pozitív, hiszen várhatóan a probléma bonyolultsága nem feltétlenül vonja maga után azt, hogy az eljárásaink rosszabb közelít˝o megoldásokat adjanak. Eddigi elemzéseink során nem említettünk szót a maximális független csúcshalmazon alapuló szekvenciális algoritmus eredményeir˝ol. Ennek oka az, hogy ez a módszer kifejezetten rosszul szerepelt tesztjeink során, a tesztesetek többségére belátható id˝on belül nem tudott választ adni. Ez valószín˝uleg abból ered, hogy a gráfszínezési – mint NP-teljes – problémán belül is folyamatosan NP-teljes problémákat szükséges megoldani (közelíteni) a maximális független csúcshalmazok keresésekor. Az algoritmus így inkább elméleti jelent˝oség˝u, mintsem a gyakorlatban használható. A seqdel algoritmus mindösszesen 6 tesztesetre adott választ belátható id˝on belül (a futásid˝ot 10800 másodpercre, azaz 3 órára maximalizáltuk gráfonként), ezen eredményeket a 3.4. táblázat foglalja össze.

29

Gráfszínezés adaptív evolúciós algoritmusokkal # Probléma 1. myciel3.col 2. myciel4.col 3. myciel5.col 11. myciel6.col 24. queen5_5.col 29. queen6_6.col

| V | | E | Éls˝ur˝uség (%) 11 20 36 23 71 28 47 236 22 95 755 17 25 160 53 36 290 46

χ(G) 4 5 6 7 5 7

seqdel CPU id˝o 4 1.03 5 1.12 6 1.44 7 10.8 5 2.15 10 43.45

3.4. táblázat. A seqdel algoritmus eredményei

3.4.2. Futásid˝ok elemzése A heurisztikák és az evolúciós módszerek eredményeinek kiértékelése mellett fontos elemezni azok futásidejeit is, ugyanis hiába adna tökéletes megoldást a seqdel algoritmus 24 óra alatt, ha annál egy kicsit rosszabbat ad egy másik eljárás 2 perc alatt. A tesztelés során mértük az er˝oforrásigényt is, azaz a felhasznált processzorid˝ot1. Az egyes eljárások által szolgáltatott legjobb megoldások kiszámításához szükséges processzorid˝oket a 3.8. ábrán jelenítettük meg minden tesztesetre nézve, továbbá mind az élszám, mind pedig az éls˝ur˝uség függvényében. ffit rando

2

Processzoridö (s)

10

ldo sdo ido

0

10

lido sldo stea ekg1

−2

10

ekgn 0

5

10

15

20 25 Tesztadatok

30

4

40

45

4

10

10

2

Processzoridö (s)

Processzoridö (s)

35

10

0

10

−2

2

10

0

10

−2

10

10 0

0.5

1 E

1.5

2

10 4

x 10

20 30 40 Élsürüség ( % )

50

60

3.8. ábra. Az algoritmusok futásideje különböz˝o szempontok alapján A fenti ábra fels˝o grafikonja talán a legszemléletesebb az összes közül, ugyanis na1

A teszteket kétmagos, 3 GHz-es Intel Core2 Duo E8400 processzoros, 4 GB RAM memóriával ellátott Fedora 8 Linux disztribúciót futtató rendszereken végeztük.

30

Gráfszínezés adaptív evolúciós algoritmusokkal gyon szépen látszódik, hogy az egyes algoritmusok futásideje hogyan viszonyul egymáshoz (vegyük észre, hogy az ordináta tengely itt is logaritmikus). Az FFIT, RANDO, LDO és LIDO algoritmusok futásidejeinek elemzésekor megállapítottuk, hogy aszimptotikus fels˝o korlátjuk ugyanaz, nevezetesen O(|V | · |E|). Ez a gyakorlatban is meglátszik, hiszen ezen 4 heurisztika közel azonos futásid˝okkel rendelkezik. Egy nagyságrenddel nagyobb a futásideje az SDO, IDO és SLDO heurisztikáknak, amely ugyancsak az elméleti korlátokból adódik. További nagyságrendbeli emelkedést tapasztalhatunk, ha az evolúciós algoritmusok futásidejét nézzük. Általánosságban elmondható, hogy az EKG1 és EKGN algoritmusok valamivel lassabban futnak le, mint a sztenderd STEA megvalósítás. Az evolúciókövet˝o szelekciót használó eljárások többlet-er˝oforrásigénye a keresési tér szélesebb bejárásából adódik, s tekintettel arra, hogy a sztenderd változathoz képest a futásid˝okülönbség nem szignifikáns (egy nagyságrend˝uek) az algoritmusok hatékonysága igen jónak mondható. A 3.8. ábra tájékoztatást nyújt számunkra afel˝ol is, hogy a gráfszínezésre használt algoritmusok és heurisztikák er˝oforrásigénye illetve a bemeneti gráf éls˝ur˝usége között nincs semmiféle kapcsolat. Az élszám valamelyest befolyásolja a fokszámokon alapuló eljárásokat, de ez a definíciójuk alapján várható volt.

3.4.3. A kapott eredmények összefoglalása Az elvégzett tesztjeink alapján azt a következtetést vonhatjuk le, hogy a triviális heurisztikák tökéletesen megfelelnek más algoritmusok - pl. az evolúciós módszerek - kiindulási alapjának, beépíthet˝oek komplexebb algoritmusokba mint ellen˝orz˝o rutinok. Alsó illetve fels˝o korlátok gyors el˝oállítására is használhatjuk o˝ ket, hiszen rendkívül gyorsak, s bizonyos esetekben ( pl. korlátozás és szétválasztáson alapuló módszereknél ) ez fontos lehet. Önmagukban nem adnak megbízható eredményeket, a szolgáltatott megoldások tetsz˝olegesen messze lehetnek az optimális megoldástól. A fokszámokon alapuló algoritmusok igen jól teljesítettek tesztjeink során, ez az az algoritmuscsalád, amely egy kompromisszum a gyors problémamegoldás illetve a minél optimálisabb megoldás megtalálása között. A heurisztikák közül az SLDO és LDO módszereket javasoljuk, az el˝obbi általában jobb megoldást ad, az utóbbi viszont átlagos esetben gyorsabban lefut. A SEQDEL algoritmus szerepelt a legrosszabbul, a gyakorlatban nem javasoljuk használni, azonban elméleti jelent˝osége igen nagy lehet, tekintettel arra, hogy az NP-teljes gráfszínezési problémát visszavezeti egy lineáris programozási modellre. Ez egyéb algoritmusok konstruálásakor a j˝ov˝oben fontos szerephez juthat. A vizsgált gráfszínezési algoritmusok közül a gy˝oztest mindenféleképpen az evolúciós algoritmusok közül kell választanunk. A min˝oség / er˝oforrásigény arányban igen jól teljesített mindegyik megvalósítás. A sztenderd változatot a kromatikus szám minél pontosabb közelítésekor felülmúlta az általunk javasolt b˝ovített algoritmus, míg a többletköltség a futásid˝oben minimális volt. Bár több esetben a közelítési pontosság továbbra sem volt megfelel˝o, mindenképpen érdemes a módosított algoritmus további vizsgálatát elvégezni, hiszen az újításokat csupán a gráfszínezési problémán teszteltük, az eljárás még nem kiforrott. További tesztek és a b˝ovített algoritmus pontosítása további javuláshoz vezethet a gráfszínezési problémák esetében is.

31

Gráfszínezés adaptív evolúciós algoritmusokkal # Probléma 1. myciel3.col 2. myciel4.col 3. myciel5.col 4. games120.col 5. huck.col 6. fpsol2.i.2.col 7. fpsol2.i.3.col 8. mulsol.i.1.col 9. inithx.i.1.col 10. fpsol2.i.1.col 11. myciel6.col 12. myciel7.col 13. inithx.i.2.col 14. inithx.i.3.col 15. mulsol.i.2.col 16. mulsol.i.5.col 17. mulsol.i.4.col 18. mulsol.i.3.col 19. anna.col 20. david.col 21. miles250.col 22. miles500.col 23. miles1500.col 24. queen5_5.col 25. le450_25b.col 26. miles750.col 27. le450_25a.col 28. miles1000.col 29. queen6_6.col 30. queen7_7.col 31. queen8_12.col 32. queen8_8.col 33. queen9_9.col 34. queen11_11.col 35. le450_15a.col 36. le450_15b.col 37. queen13_13.col 38. le450_5a.col 39. le450_25d.col 40. le450_25c.col 41. le450_15d.col 42. le450_15c.col 43. flat300_28_0.col 44. flat300_26_0.col 45. flat300_20_0.col

|V | 11 23 47 120 74 451 425 197 864 496 95 191 645 621 188 186 185 184 138 87 128 128 128 25 450 128 450 128 36 49 96 64 81 121 450 450 169 450 450 450 450 450 300 300 300

| E | Éls˝ur˝uség (%) 20 36 71 28 236 22 638 9 301 11 8691 9 8688 10 3925 20 18707 5 11654 9 755 17 2360 13 13979 7 13969 7 3885 22 3973 23 3946 23 3916 23 493 5 406 11 387 5 1170 14 5198 64 160 53 8263 8 2113 26 8260 8 3216 40 290 46 476 40 1368 30 728 36 1056 33 1980 27 8168 8 8169 8 3328 23 5714 6 17425 17 17343 17 16750 17 16680 17 21695 48 21633 48 21375 48

Kromatikus szám χ(G) 4 5 6 9 11 30 30 49 54 65 7 8 31 31 31 31 31 31 11 11 8 20 73 5 25 31 25 42 7 7 12 9 10 11 15 15 13 5 25 25 15 15 28 26 20

3.5. táblázat. Az összehasonlításra használt gráfok és azok paraméterei 32

Gráfszínezés adaptív evolúciós algoritmusokkal #

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45.

χ(G)

FFIT

LDO

SDO

IDO

LIDO

SLDO

STEA

EKG1

EKGN

54 31 31 7 5 11 11 6 5 4 10 9 12 7 7 8 73 42 9 11 49 31 31 13 31 11 31 31 20 8 20 15 25 25 25 25 5 26 28 65 30 30 15 15 15

54 31 31 7 8 12 11 6 5 4 16 13 15 10 11 8 76 44 9 12 49 31 31 21 31 17 31 34 22 9 47 31 28 27 37 35 14 45 46 65 30 30 22 22 30

54 31 31 7 6 12 11 6 5 4 15 15 17 12 11 8 74 46 9 11 49 31 31 22 31 18 31 32 21 9 49 28 26 26 33 34 13 46 45 65 30 30 20 21 31

54 31 31 7 8 12 11 6 5 4 16 13 15 10 11 8 76 44 9 12 49 31 31 21 31 17 31 34 22 9 46 31 28 27 37 35 14 48 45 65 30 30 22 22 30

54 31 31 7 8 12 11 6 5 4 16 13 15 10 11 8 76 44 9 12 49 31 31 21 31 17 31 34 22 9 48 31 28 27 37 35 14 47 47 65 30 30 22 22 30

54 31 31 7 6 12 11 6 5 4 15 15 17 12 11 8 74 46 9 11 49 31 31 22 31 18 31 32 21 9 46 28 26 26 34 33 13 46 46 65 30 30 20 20 29

54 32 32 7 7 11 11 6 5 4 13 14 17 11 8 8 73 45 9 11 49 32 32 19 32 17 32 32 21 9 46 30 27 29 35 35 13 45 49 65 30 30 21 22 31

54 31 31 7 5 11 11 6 5 4 12 11 14 9 8 8 73 43 9 11 49 31 31 18 31 15 31 32 21 8 44 29 27 26 35 35 12 45 46 65 30 30 20 21 29

54 31 31 7 5 11 11 6 5 4 12 11 14 9 8 8 73 43 9 11 49 31 31 18 31 15 31 31 20 8 43 28 26 26 33 34 12 45 44 65 30 30 20 20 29

54 31 31 7 5 11 11 6 5 4 12 11 14 9 8 8 73 42 9 11 49 31 31 18 31 15 31 32 20 8 44 28 26 26 34 34 12 45 45 65 30 30 20 20 28

3.6. táblázat. Az algoritmusok által kiszámított kromatikus számok 33

4. fejezet A sík 1 színezésének vizsgálata EKG algoritmussal 4.1. A sík 1 színezésének problémája Számos olyan gráfszínezési probléma létezik, amelyre a pontos válasz nem ismert (lásd T HE O PEN P ROBLEM P ROJECT [27]). Az egyik ilyen nyitott feladat az 1944-ben felvetett ún. Hadwiger-Nelson probléma (lásd W IKIPEDIA [26]), amely a jelen fejezet témáját adta. A feladat nem más, mint megtalálni azt a legkevesebb színt, amellyel a síkon az egység-távolságú végtelen gráf jól színezhet˝o. A válasz nem ismert, azonban Erd˝os és de Bruijn eredményei alapján a sík kromatikus száma bizonyítottan 4 ≤ χ(E 2 ) ≤ 7 közé ˝ [20], O REN [18] ). esik ( lásd E RD OS Természetesen a mi célunk az, hogy ezt az intervallumot sz˝ukítsük: vagy az alsó korlátot emeljük, vagy a fels˝o korlátot csökkentsük. A feladatot tehát többféleképpen lehet megközelíteni : • Találjunk olyan G részgráfot a sík egység távolságú gráfjában, amely nem színezhet˝o 4, (5, 6) színnel! Ha találunk ilyen gráfot, az természetesen bizonyító erej˝u. A megközelítésben ott rejlik a probléma, hogy bár ilyen gráfok gyorsan és hatékonyan generálhatóak, minden gráfra meg kell határozni a kromatikus számot, amely ugyebár NP-teljes probléma. A heurisztikus és egyéb közelít˝o algoritmusok itt nem használhatóak, hiszen ebben az esetben a pontos kromatikus szám ismeretére van szükség. • Találjunk olyan G részgráfot, amelyben a pontok Euklideszi távolsága 1, G periodikus felhasználásával a teljes G = E 2 gráf megkonstruálható, továbbá kevesebb színnel színezhet˝o, mint 7, (6, 5). Például definiáljunk 6 ponthalmazt: A, B, C, D, E, F a síkban, hozzájuk 6 eltolást: (a1 , a2 ), . . . , (f1 , f2 ). Ezután ha elérjük, hogy az A + (pa1 , qa2 ) típusú 6 halmaz (ahol p, q tetsz˝oleges egész) diszjunkt uniója a sík legyen (periodikus parkettázás) illetve ezen halmazok jó színezések (tehát ne legyen két 1 távolságú pont egy fajta halmazból), akkor ez szintén emelné az alsó korlátot. A probléma annyira elméleti, hogy a numerikus módszerek megbízhatatlansága illetve az algoritmusaink közelít˝o volta miatt egzakt, bizonyító erej˝u megoldást aligha találnánk.

34

Gráfszínezés adaptív evolúciós algoritmusokkal Az algoritmusaink viszont felhasználhatóak kiegészít˝o vizsgálatok elvégzésére, amelyek elméleti kutatásokban fontos „ötleteknek” bizonyulhatnak.

4.2. Akadályok keresése magasabb kromatikus számú gráfokban A vizsgálódásunk célja nem más, mint keressünk olyan struktúrákat, részgráfokat, amelyek magasabb (4 < χ(G) ≤ 7) kromatikus számú gráfok esetén meggátolhatják, hogy azok az egységgráf részgráfjai legyenek. Más szóval olyan gráf-tulajdonságokra szeretnénk fényt deríteni, amelyek kizárják, hogy az adott gráfot úgy rajzoljuk le a síkban, hogy minden éle 1 hosszúságú legyen. Az eredmények érdekesek lehetnek olyan szempontból, hogy elméleti úton milyen típusú gráfokat érdemes vizsgálni ezen problémakörben, avagy milyen tulajdonságokat nélkülöz˝o struktúrákra érdemes alapozni a kutatásokat. A választott módszerünk a következ˝o. Evolúciós módszerekkel ismert kromatikus számú gráfokat próbálunk meg elhelyezni a Descartes-féle koordinátarendszerben, úgy, hogy a gráf által meghatározott, és a csúcsok pozíciója által adott élhosszúságok minél közelebb essenek az 1-hez.

4.2.1. Az EKG kromoszómái és genetikus keres˝omuveletei ˝ Az evolúciós módszernek egyetlen egyedi paramétere van, mégpedig a választott G gráf, amelyre teljesül, hogy χ(G) ∈ {5, 6, 7}. Ezt a G gráfot szeretnénk elhelyezni E 2 -re. Egyedek megadása Minden egyed egy tetsz˝oleges e ∈ R2|V | vektorként írható le, úgy hogy (ei , ei+k ) az i-edik csúcs koordinátái, valamely k ∈ {1, 2, . . . , |V |} egészre. Ez helyes reprezentáció, hiszen a G gráf egyértelm˝uen adott a síkon, továbbá a csúcsok koordinátáiból egyértelm˝uen kiszámíthatóak az élhosszak. A kezd˝opopulációt úgy alakítjuk ki, hogy minden egyed minden csúcsa az origó középpontú, 2 oldalhosszúságú négyzetb˝ol kerüljön ki. Ennek futásid˝oköltsége minimális, hiszen adott tartománybeli vektorokat kell véletlen módon generálnunk. Az alkalmazott fitnesszfüggvény A célunk az, hogy az egyedek olyan gráf-rajzolatokat reprezentáljanak, amelyekben az élhossszak 1-t˝ol való távolsága minimális. Egy e egyed fitnesszértékét az általa meghatározott élhosszak 1-t˝ol való távolságának négyzetösszegeként definiáljuk: X f it(e) = (d(P (e, v1), P (e, v2)) − 1)2 v1 ,v2 ∈E

ahol P (e, vi ) a vi csúcs koordinátái által adott pontot jelenti az e egyedben. Ez a legkisebb négyzetes értelemben keresi a legjobb megoldást, és az abszolút hibát minimalizálja, így

35

Gráfszínezés adaptív evolúciós algoritmusokkal a célunknak megfelel˝o, hiszen egy konkrét egyedet globálisan értékel. Génmódosítások, genetikus keres˝omuveletek ˝ A célkit˝uzéseink alapján igen fontosak lehetnek az apró helyi változtatások, amelyeket a mutációs m˝uveletekkel valósíthatunk meg. Mivel a b˝ovített kereteljárással dolgozunk, érdemes ezekb˝ol minél többet használni. 1. Véletlenszer˝uen válasszunk egy E ′ ⊂ E élhalmazt, amely diszjunkt éleket tartalmaz. Az élek végpontjait (csúcsokat) középpontosan skálázzuk úgy, hogy a létrejöv˝o él hosszúsága 1 legyen. A skálázásokat érdemes transzlációs és skálázó mátrixok segítségével elvégezni. 2. Egy csúcsot a szomszédai által meghatározott ponthalmaz súlypontjába helyezzük. Szerencsétlen esetben ez ronthat az egyed fittségén, azonban átlagos esetben jobb egyedeket evolvál. A m˝uvelet is gyors, hiszen ponthalmaz súlypontjára egzakt képlet ismert. 3. Egy csúcs szomszédait az élek által meghatározott irányba mozgatjuk úgy, hogy a szomszédok rajta legyenek a csúcs körüli egység sugarú körön. Ezáltal az összes szomszéd 1 távolságban lesz az adott csúcstól. 4. Egy csúcshoz választunk 2 szomszédot, amennyiben ez lehetséges. Az adott csúcsot ezen két szomszéd köré írt egység sugarú körök metszéspontjai valamelyikébe mozgatjuk. Amennyiben a két szomszéd távolsága nagyobb, mint 2, középpontosan skálázzuk o˝ ket, hogy távolságuk 2 legyen. Az utolsó három eljárás esetében véletlenszer˝uen választunk több csúcsot, és azokra egyenként hajtjuk végre a m˝uveleteket. A könnyebb érthet˝oség érdekében a m˝uveletek hatását a 4.1.ábrán illusztráltuk.

4.1. ábra. Az algoritmusban használt mutációs m˝uveletek hatásai 36

Gráfszínezés adaptív evolúciós algoritmusokkal A keresztezés m˝uveletre három megoldást készítettünk, ezek általánosabbak, és nem annyira feladat-specifikusak, mint az el˝obbiekben ismertetett mutációk. A szül˝oket jelöljük ismét s1 és s2 -vel. 1. A gyerek egyed csúcsainak pozícióját

1 2

valószín˝uséggel választjuk s1 vagy s2 -b˝ol.

2. Az éleket növekv˝o sorrendbe rendezzük hibájuk alapján mindkét szül˝oben, majd mindig az aktuálisan legkisebb hibával rendelkez˝o élt adjuk hozzá a gyerek egyedhez. Amennyiben egy ilyen él mindkét végpontja már része a gyereknek, az élt eldobjuk, egyébként a még be nem választott csúcsokat hozzávesszük ahhoz. 3. A csúcsokat felváltva választjuk s1 és s2 -b˝ol oly módon, hogy az éppen beválasztott csúcsok még be nem választott szomszédjait s1 -b˝ol, azok szomszédjait s2 -b˝ol, stb. választjuk. A MATLAB megvalósításunkat a color_plane_ekg eljárás tartalmazza. A használata gyakorlatilag ugyanaz, mint a gráfszínezésben használt color_ekg eljárásé, paraméterében meg kell adni a síkon elhelyezend˝o gráfot, illetve opcionálisan megadható egy beállítás-vektor is: >> [R,S] = color_plane_ekg(G1,[200 30]); A kitenyésztett R legígéretesebb eredményt a következ˝oképpen tudjuk kirajzolni a síkon: >> display_graph_2d(G1,R); amelynek eredménye egy hasonló grafikon kell, hogy legyen: E

: 0.885445, E

max

: 0.208691, η(G): 11.455

avg

0 −0.2 −0.4 −0.6 −0.8 −1 −1.2 −1.4 −1.6 −1.8 −2.2

−2

−1.8

−1.6

−1.4 −1.2 −1 myciel6.col, χ(G) = 7

−0.8

−0.6

−0.4

A grafikon címmez˝ojében megtalálható Emax , Eavg és η(G) értékek a maximális élhibát, az átlagos élhibát, és egy, a következ˝o alfejezetben definiált min˝oségi jellemz˝ot adnak meg. A grafikonon minél pirosabb egy él, annál nagyobb abszolút hibával terhelt – természetesen a maximális Emax hibához mérten. 37

Gráfszínezés adaptív evolúciós algoritmusokkal

4.2.2. Az EKG algoritmus megbízatósági vizsgálata Ahhoz, hogy a kés˝obbi tesztjeink során következtetéseket vonhassunk le az algoritmusunk eredményeib˝ol, szükséges annak megbízhatóságát megvizsgálni. Meg kell bizonyosodnunk arról, hogy az algoritmus tényleg képes egy adott gráf pontos elhelyezésére a síkon a megadott korlátok figyelembevétele mellett. Tekintettel arra, hogy 4 ≤ χ(E 2 ) ≤ 7, minden G gráf, melyre χ(G) ≤ 4 elhelyezhet˝o a síkon úgy, hogy éleinek hossza pontosan 1 legyen. Ilyen típusú tesztgráfok elhelyezési pontosságával jellemezhetjük az algoritmusunkat. A 4.2. ábrán a vizsgálathoz használt neves gráfokat ábrázoltuk, amelyek többsége a Hadwiger-Nelson problémához is szorosan kapcsolódik.

4.2. ábra. A megbízhatósági vizsgálathoz használt neves tesztgráfok A fent megadott tesztgráfokra lefuttattuk az evolúciós algoritmusunkat, az eredményeket a 4.1. táblázat tartalmazza. Az algoritmust egy adott gráfon a közelítési pontosság mér˝oszámmal jellemezhetjük, amely a legnagyobb élhibából adódik és definíciója: η(G) = 100 · (1 − max (|1 − d(u, v)|)) . (u,v)∈E

Tesztgráf C6 S6 Moser-inga W7 Golomb-gráf 2-Fusene 3-Sierpinski

χ(G) Maximális élhiba (Emax ) 2 0.000000 2 0.002357 4 0.007585 3 0.000025 4 0.003165 2 0.000000 3 0.145413

Átlagos élhiba (Eavg ) η(G) 0.000000 100.000 0.001336 99.764 0.004268 99.242 0.000008 99.998 0.000561 99.683 0.000000 100.000 0.030257 85.459

4.1. táblázat. Az egységgráfok elhelyezési pontosságai A kitenyésztett egyedek közül párat grafikusan is ábrázoltunk a 4.3. ábrán. Ezen ábra fels˝o két grafikonján jól látható, hogy a Moser-ingát – amely a jelenlegi 4-es alsó korlátot adta – helyesen helyezte el az algoritmus, hasonlóan a 7 csúcsból álló „kerékgráfhoz”, amelynek pontossága még az el˝obbinél is jobb. Az alsó két grafikon mutatja a két széls˝oértéket, a 2-Fusene gráfot hiba nélkül sikerült elhelyezni, míg a Sierpinski-sorozat 3. tagját volt a legnehezebb pozícionálni a síkon. 38

Gráfszínezés adaptív evolúciós algoritmusokkal E

: 0.004268, η(G): 99.242

: 0.007585, E

max

E

avg

: 0.000025, E

max

: 0.000008, η(G): 99.998

avg

1.5 1.5 1 1 0.5

0.5

0

0 0 0.5 1 Moser spindle, χ(G) = 4

E

: 0.000000, E

max

−0.5

0.5 χ(G) = 3

W7,

: 0.000000, η(G): 100.000

avg

E

: 0.145413, E

max

1

: 0.030257, η(G): 85.459

avg

1

0.5 0

0

−0.5

−1

−1

−2

−1.5 −1.5

0

−3 −1

−0.5 2−Fusene,

0 0.5 χ(G) = 2

−3

−2 −1 3−Sierpinski,

0 χ(G) = 3

1

4.3. ábra. A megbízhatósági vizsgálat eredményei Kijelenthetjük, hogy az algoritmus elhelyezési pontossága majdnem minden esetben 100%-os volt, így ha egy kés˝obbi – magasabb kromatikus számú – tesztgráfra hasonló közelít˝o eremdényeket kapnánk, azt a gráfot érdemes elméleti úton is vizsgálni a síkon való elhelyezés szempontjából.

4.3. Akadálykeresés és elemzés A vizsgálathoz a Mycielski ([16]) és a Queen ([29]) gráfsorozatok 3-3 tagját használjuk fel, amelyek egyébként az eddigi tesztjeink során már jól bevált gráfszínezési adatbázisnak is elemei. Ezen gráfok tulajdonságait a 4.2. táblázatban foglaltunk össze. A kromatikus számok mind 5 és 7 közé esnek, így vizsgálatainkhoz alkalmasak lesznek, de természetesen bármely, adott intervallumba es˝o kromatikus számú gráf megfelel˝o lenne. # Probléma 1. myciel6.col 2. myciel5.col 3. myciel4.col 4. queen7_7.col 5. queen6_6.col 6. queen5_5.col

|V | 95 47 23 49 36 25

|E| Éls˝ur˝uség (%) 755 17 236 22 71 28 476 40 290 46 160 53

χ(G) 7 6 5 7 7 5

4.2. táblázat. A használt tesztgráfok és azok paraméterei 39

Gráfszínezés adaptív evolúciós algoritmusokkal Algoritmusunkat mind a 6 tesztgráfon 10-10-szer futtatuk le, majd a futtatások legjobb eredményeit vettük figyelembe, amelyeket a 4.4. ábrán meg is jelenítettünk. A bal oldali „oszlopban” a Mycielski sorozat, a jobb oldaliban pedig a Queen sorozat tagjainak elhelyezése látható. A grafikonokon alulról felfelé haladva a sorozatok tagjait sorrendben rajzoltuk ki. E

: 0.885445, E

max

: 0.208691, η(G): 11.455

avg

0

E

: 0.278868, η(G): 11.485

: 0.885146, E

max

avg

1.5

−0.5

1

−1 0.5 −1.5 0 −2 E

−1.5 myciel6.col,

: 0.785888, E

max

−1 χ(G) = 7

−0.5

: 0.176123, η(G): 21.411

avg

0 E

0.5 queen77.col,

1.5

: 0.267303, η(G): 13.589

: 0.864109, E

max

1 χ(G) = 7

avg

1.5 1

2.5

0.5 2 0 1.5

−0.5 −1 −0.5 E

0 0.5 myciel5.col,

: 0.453073, E

max

1 1.5 χ(G) = 6

: 0.125723, η(G): 54.693

avg

1.5 2 queen6 .col, 6

E

: 0.235639, η(G): 30.757

: 0.692428, E

max

2.5 χ(G) = 7

avg

1 0.5

−1.5

0

−2

−0.5

−2.5

−1 −0.5 0 myciel4.col,

0.5 χ(G) = 5

1

−2.5

−2 −1.5 −1 queen5 .col, χ(G) = 5 5

4.4. ábra. Az evolúciós eredmények legjobbjai, és azok megbízhatósági értékei Jól megfigyelhet˝o, hogy a sorozatok kisebb fokú tagjainak elhelyezése sikeresebb volt, míg a magasabb fokú gráfok esetén – feltehet˝oleg bonyolultságuk miatt – alig értünk el 11%-os közelítési pontosságot. A Mycielski sorozat tagjaira az algoritmus általában pontosabb megoldásokat adott, ez megmutatkozik a η(G) és Eavg értékekben is. Mivel egyik esetben sem kaptunk olyan jó eredményeket, mint a verifikáció során használt gráfok esetén, érdemes megvizsgálni, hogy ennek mi lehet az oka. 1. Vajon a sík színezéséhez elegend˝o 4 szín? Ehhez be kellene látni, hogy az adott gráfok semmilyen módon nem helyezhet˝oek el megfelel˝oen E 2 -en. 2. Mik azok a gátló tényez˝ok, ami miatt az algoritmus ilyen „rossz” közelít˝o eredményeket adott? 40

Gráfszínezés adaptív evolúciós algoritmusokkal

4.3.1. A csúcsfokszámok és a közelítési pontosság összefüggése A legnyilvánvalóbb vizsgálat lehet annak kiderítése, hogy milyen módon befolyásolják a csúcsok fokszámai az elhelyezés pontosságát. A csúcsok fokszámai jellemzik az adott gráf bonyolultságát, és mivel 4.4. ábrán jól megfigyelhet˝o a bonyolultabb gráfok rosszabb elhelyezése, a vizsgálat mindenféleképpen szükséges. Mind a 6 tesztgráf legjobb elhelyezésénél megvizsgáltuk, hogy a gráfok csúcsai milyen átlagos és maximális élhibával rendelkeznek, majd ezeket a csúcsok fokszámai alapján rendeztük. A kapott eredményeket összesítettük egyetlen grafikonon: 1

Átlagos élhiba Maximális élhiba

0.9 0.8 0.7

Élhibák

0.6 0.5 0.4 0.3 0.2 0.1 0

5

10

15

20

25 30 Csúcsok fokszáma

35

40

45

4.5. ábra. Az átlagos és maximális élhibák a csúcsok fokszámainak függvényében A fenti ábrán a fokszámtengely [3, 23] intervalluma érdekes, hiszen itt több gráf adatai szerepelnek, míg a [24, 47] intervallumon csupán egyetlen gráfon mért értékek láthatók. Semmiféle tendencia nem figyelhet˝o meg az adatokban, mind az átlagos, mind a maximális élhibára elmondható, hogy nincsenek korrelációban a csúcsok fokszámaival. 4.3.1. Állítás. Megállapítható tehát, hogy a nagyobb hibával rendelkez˝o élek végpontjai nem feltétlenül nagyobb fokszámú csúcsok. Így önmagukban a magasabb fokszámú csúcsok nem tekinthet˝oek a síkon való elhelyezés akadályainak. Önmagukban nem akadályok, azonban csoportosan azok-e? Azaz mit mondhatunk az olyan élek hibáiról, amelyek mindkét végpontja magasabb fokszámú? Milyen fokszámpárosítások mellett figyelhet˝o meg a hiba növekedése, ha egyáltalán megfigyelhet˝o? A következ˝o vizsgálatunk arra irányult, hogy a tesztgráfok elhelyezésében hogyan alakultak az élhibák az élek végpontjainak fokszámából alkotott párosok függvényében. Minden esetben kiszámítottuk minden élre a két végpont fokszámát, ezen fokszámpároshoz hozzárendeltük az adott él hibáját, majd vettük ezen értékek átlagát. Ez egy Ed ∈ Rn×m mátrixszal írható le, melyre (u,v)∈E

Ed (i, j) =

X

|1 − d(u, v)|

deg(u)=i,deg(v)=j

41

Gráfszínezés adaptív evolúciós algoritmusokkal Ezen mátrixot mint kétváltozós diszkrét függvényt rajzoltuk ki háromdimenzióban, mindkét gráfsorozatra nézve. Az ábrákon jól megfigyelhet˝o a gráfsorozatok elemeinek hasonló viselkedése: myciel5.col

Átlagos hiba

myciel6.col

0.2 0 20

20 10 deg(v)

0.3

0

0.1

0 10

0

20 40

0

30

30 20

40

10

0

0.4 0.2 0 10

10

deg(v)

5

deg(u)

5 0

deg(v)

0

deg(u)

queen6 .col

queen7 .col

6

Ãtlagos hiba

7

0.4

0.4 0.2 0 15

0.3

10

5

deg(v) 0.2

0 0 queen5 .col

5

10

15

deg(u)

5

0.1 20 0

15 20

15

10 10 deg(v)

5

5 0

0

deg(u)

Ãtlagos hiba

Ãtlagos hiba

10 deg(u)

myciel4.col

0.2

Átlagos hiba

Átlagos hiba

0.4

0.4

0.4 0.2 0 15

10 deg(v)

5

0

0

10

5

15

deg(u)

4.6. ábra. Az átlagos élhibák a csúcspárok fokszámainak függvényében 4.3.2. Állítás. A Queen-sorozatban lév˝o gráfoknál egyértelm˝uen megállapítható, hogy a nagyobb fokszámú csúcsokat (∈ [18, 24] queen_7_7-re) összeköt˝o éleket volt nehéz 1 hosszúságúra beállítani. Ebben a sorozatban lév˝o akadályok tehát ezek az élek. Mivel a gráf csak ilyen fokszámú éleket tartalmaz, a sorozat definíciójából adódó éls˝ur˝uség a legf˝obb akadály. A Mycielski-sorozatra kapott eredményeink már érdekesebbek, négy elkülönül˝o lokális maximum figyelhet˝o meg az ábrákon. Ez amiatt van, hogy pl. a myciel6 gráf esetében a [25, 39] fokszám-intervallumból nincs, csak 32 fokú csúcs. 4.3.3. Állítás. A Mycielski-sorozat elemeinél olyan éleket nevezhetünk akadályoknak, amelyek legalább egyik végpontja az átlagnál kisebb fokszámú (pl. myciel6-nál ez a [6, 21] tartományt jelenti).

42

Gráfszínezés adaptív evolúciós algoritmusokkal

4.3.2. Akadályok Mycielski 4 -ben A Mycielski sorozat 4. tagjánál (myciel4.col) kaptuk a legmagasabb (54.693) pontosságot (lásd 4.4.ábra), továbbá az grafikusan is jól szemléltethet˝o a kisebb csúcsilletve élszám miatt, így a következ˝o vizsgálatunkat ezen a gráfon végezzük el. A mostani vizsgálatunk célja nem más, mint olyan részgráf keresése a Mycielskisorozat 4. tagjában, amely akadálynak min˝osíthet˝o. Egy Ga részgráfot akadálynak tekintünk, ha annak elhagyásával a fennmaradó G − Ga gráf már nagy közelítési pontossággal helyezhet˝o el a síkon. Amennyiben ezt elértük, érdekes lehet a G − Ga gráf pontos kromatikus számát kiszámítani. Ha ugyanis ez nem változik (5 marad), akkor az adott gráfot érdemes jobban megvizsgálni. Ha a kromatikus szám csökken, akkor egy újabb meger˝osítést találnánk ahhoz a sejtéshez, miszerint a sík színezéséhez elég 4 szín. Algoritmus. (Iteratív akadálykeresés(G,ηc )) 1: ǫ ← Emax 2: while igaz do 3: ǫ←ǫ−δ 4: G′ = (V, E ′ ) : E ′ = {(u, v) ∈ E | | 1 − d(u, v)| < ǫ} 5: if χ(G′ ) < χ(G) then 6: return [hamis, G − G′ ] 7: end if 8: if χ(G′ ) = χ(G) és η(G) > ηc then 9: return [igaz, G − G′ ] 10: end if 11: end while Az algoritmus m˝uködése a következ˝o: G-t addig csonkítja egy ǫ küszöbérték feletti hibával rendelkez˝o élekkel, amíg vagy a kromatikus számban, vagy az elhelyezési pontosságban nem tapasztal változást. Az algoritmus igazat ad vissza, ha talált egy akadályt, és a kromatikus szám nem csökkent, hamisat egyébként. A választott gráfunk két ǫ értékhez tartozó akadálygráfját jelenítettük meg az alábbi ábrán: E

: 0.453073, η(G): 54.693, ε: 0.30

E

1

1

0.5

0.5

0

0

−0.5

−0.5

−1

−1 −0.5

0 myciel4.col,

0.5 χ(G) = 5

: 0.453073, η(G): 54.693, ε: 0.21

max

max

1

−0.5

0 myciel4.col,

0.5 χ(G) = 5

1

4.7. ábra. Az ǫ = 0.3 és ǫ = 0.21 értékekhez tartozó akadályok 43

Gráfszínezés adaptív evolúciós algoritmusokkal Az algoritmust oly módon érdemes használni, hogy el˝oször az adott gráfot pozícionáljuk a síkon, majd az adott elhelyezésre vonatkozóan keresünk akadályokat. Ez azért szükséges, mert minden egyes pozícionálás máshol hibázhat, így b˝ovebb képet kaphatunk az akadályokról. A következ˝o MATLAB kód pontosan ezt végzi el: >> load graph_plane_test G3; >> [R,S] = color_plane_ekg(G3,[200 40]); >> [b,Ga] = barrier_seek(G3,R,80); Current eps : 0.544435 Chromatic numbers : 5 6 5 4 Trying to place G’ on the plane... Current placement Eta: 37.366494 >> Az alábbi ábrán egy, – a fentivel ekvivalens – futtatás eredményeit ábrázoltuk, a bal oldali grafikon a Ga akadálygráfot, a jobb oldali pedig G − Ga gráf újrapozícionálásának eredményét mutatja. Emax: 0.590583, η(G): 40.942, ε: 0.58

Emax: 0.392567, Eavg: 0.156073, η(G): 60.743

0 3 −0.5 2.5 −1 2 −1.5

1.5

−2

1

−2

−1.5

−1 myciel4.col,

−0.5 χ(G) = 5

0

0

0.5

1 1.5 2 myciel4.col, χ(G) = 4

2.5

4.8. ábra. Egy futtatás során kapott akadálygráf és a fennmaradó gráf pozícionálása 4.3.4. Állítás. Az akadálygráf jelenleg egyetlen él, és ennek elhagyásával a fennmaradó G−Ga gráf kromatikus száma 4-re csökkent. Hasonló eredményeket kaptunk több futtatás során is, így megállapítható, hogy a magasabb kromatikus számot okozó élek akadályok a helyes pozícionálás számára. A 4.8.ábra alapján az is megfigyelhet˝o, hogy a G − Ga gráf pozícionálása során ( jobb oldali grafikon ) pontosabb eredményeket kaptunk, mind az Emax , Eavg és η(G − Ga ) értékek javultak az akadály elhagyásával. Összefoglalva tehát eredményeinket, azon sejtés, miszerint 4 szín elegend˝o a sík színezéséhez, újabb meger˝osítéseket kapott, mind a tesztgráfok pozícionálása, mind pedig az akadályok vizsgálata során.

44

Összefoglalás Ezen diplomadolgozatban az evolúciós algoritmusok, illetve a gráfszínezési problémák házasságát vizsgáltuk számos megközelítésben. A célunk az volt, hogy olyan lágy számítási módszereket fejlesszünk ki, amelyek hatékonyan használhatóak a gráfszínezési problémakör több esetében is. A dolgozat els˝o fejezetében bemutattuk a b˝o szakirodalommal rendelkez˝o evolúciós algoritmus technikát, felfedtünk pár olyan problémát, amely gátat szabhat ilyen típusú eljárások helyes használatának. Kifejlesztettük a sztenderd EA-nak egy b˝ovített változatát, amely számos újítást tartalmaz az el˝obbi problémák kiküszöbölésére. Az elkészített algoritmust górcs˝o alá vettük, elvégeztük annak helyességigazolását, amelynek eredménye igen pozitív lett, ugyanis az újítások révén az algoritmus globalitása igen nagy mértékben javult, illetve a konvergenciasebességet is növelni tudtuk. A második fejezetben a gráfszínezési problémákra koncentráltunk, számos ismert gráfszínezési heurisztika pontos leírását adtuk meg, továbbá elkészítettünk több evolúciós módszert is, amelyeket sikerrel alkalmaztunk. A bemutatott algoritmusokat részletekbe men˝oen összehasonlítottuk, és kiderítettük, hogy az EA módszerek igen hatékonyan használhatóak igen nagy gráfok színezésére is. A harmadik és egyben utolsó fejezetben egy igen nagy méret˝u nyitott problémát elemeztünk. Az elméleti megközelítések hamar olyan pályára tereltek minket, amelyben sikerrel tudtuk alkalmazni az evolúciós technikákat. A síkszínezési problémát egy speciális módon közelítettük meg, ismert topológiájú és kromatikus számú gráfok síkon való elhelyezésére készítettünk EA algoritmust. Az algoritmus pontosságára külön vizsgálatot szántunk, amely bebizonyította, hogy a megkonstruált algoritmus helyes és hatékony. Ezután a síkon való elhelyezés akadályait vizsgáltuk, amelynek eredményeképpen több sejtésünk is megfogalmazódott a vizsgált nyitott problémával kapcsolatban. Összességében kijelenthetjük, hogy vizsgálataink sikeresek voltak, a dolgozat elkészítése során olyan tapasztalatra tettünk szert, amelyet kamatoztatni tudunk kés˝obbi feladataink során.

45

Nyilatkozat Alulírott Veress Krisztián, programtervez˝o matematikus szakos hallgató, kijelentem, hogy a dolgozatomat a Szegedi Tudományegyetem Informatikai Tanszékcsoport Számítógépes Optimalizálási tanszékén készítettem, okleveles programtervez˝o matematikus diploma megszerzése érdekében. Kijelentem, hogy a dolgozatot más szakon korábban nem védtem meg, saját munkám eredménye, és csak a hivatkozott forrásokat (szakirodalom, eszközök, stb.) használtam fel. Tudomásul veszem, hogy szakdolgozatomat / diplomamunkámat a Szegedi Tudományegyetem könyvtárában, a kölcsönözhet˝o könyvek között helyezik el.

Szeged, 2009. június 22.

................................ aláírás

46

Köszönetnyilvánítás Ezúton szeretnék köszönetet mondani Dr. Blázsik Zoltánnak, aki felmerül˝o kérdéseimre a kutatásaimat el˝oremozdító módon válaszolt, akinek ötletei, iránymutatásai és lelkesít˝o témavezetése nélkül ez a dolgozat nem jöhetett volna létre. Köszönöm továbbá Dr. Csendes Tibornak, hogy tanulmányaim során folyamatosan támogatott a min˝oségi dolgozatok elkészítésében, és akinek páratlan tapasztalatára mindig is számíthattam és támaszkodhattam. Meg szeretném köszönni jóbarátom, Kozma Attila folyamatos technikai és nem technikai támogatását, megértését és segítségét, amelyek alapvet˝o fontosságúnak bizonyultak egyetemi tanulmányaim valamint ezen diplomamunka elkészítése, elvégzése szempontjából. Hálás vagyok továbbá szüleimnek, nagyszüleimnek, páromnak, továbbá minden rokonomnak és barátomnak, akik kitartottak mellettem, segítettek munkámban, és megteremtették mindazon feltételeket, amelyek nélkül nem juthattam volna ilyen messzire.

47

Irodalomjegyzék [1] Ajith Abraham and Lakhmi Jain, Evolutionary Multiobjective Optimization, Theoretical Advances and Applications, Springer, USA, 2005. [2] Borgulya István, Evolúciós algoritmusok, Dialóg-Campus, Budapest-Pécs, 2004. [3] Chang Wook Ahn and R. S. Ramakrishna, Elitism-Based Compact Genetic Algorithms, IEEE Transactions on Evolutionary Computation, 7(4), (2003) 367–385. [4] David E. Goldberg, Genetic Algorithms in Search - Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Boston, MA, 1989. [5] DIMACS Graph Format, http://mat.gsia.cmu.edu/COLOR/general/ccformat.ps [6] E. Happ, D. Johannsen, C. Klein and F. Neumann, Rigorous analyses of fitnessproportional selection for optimizing linear functions, GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, (2008), 953– 960. [7] Graph coloring Test Database, http://mat.gsia.cmu.edu/COLOR/instances.html [8] Hajnal Péter Gráfelmélet Polygon Kiadó, Szeged, 1997. [9] Hopgood, A.A. and Mierzejewska, A., Transform Ranking: a New Method of Fitness Scaling in Genetic Algorithms, Proc. AI-2008: Research and Development in Intelligent Systems, 25, (2008), 349–354. [10] James E. Baker, Reducing Bias and Inefficiency in the Selection Algorithm, in Proceedings of the Second International Conference on Genetic Algorithms and their Application, (1987), 14–21. [11] John H. Holland, Adaptation in Natural and Artificial System, MIT Press., Cambridge, MA, 1992. [12] John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press., Cambridge, MA, 1992. [13] L. Moser and W. Moser, Solution to Problem 10, Canadian Math. Bull., 4, (1961), 187–189. [14] M. Mitchell, S. Forrest, Genetic algorithms and artificial life, Artificial Life, 1(3), (1994), 267–289. 48

Gráfszínezés adaptív evolúciós algoritmusokkal [15] M.R.Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman, USA, 1979. [16] Mycielski-gráfok, http://hu.wikipedia.org/wiki/Mycielski-konstrukció [17] N.G. de Bruijn and P. Erd˝os, A Color Problem for Infinite Graphs and a Problem in the Theory of Relations, Nederl. Akad. Wetensch. (Indag Math), 13, (1951), 371– 373. [18] Oren Nechushtan, On the space chromatic number, Discrete Mathematics, 256(1–2), (2002), 499–507. [19] P. Crescenzi and V. Kann, A compendium of NP optimization problems, http://www.nada.kth.se/~viggo/wwwcompendium/ [20] P. Erd˝os and N. G. de Bruijn, A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math., 13, (1951), 371–373. [21] Paul Erdos, Frank Harary, and William T. Tutte, On the Dimension of a Graph, Mathematika, (1965), 118–122. [22] R. Radoicic and G. Tóth, Note on the chromatic number of space, Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Springer Verlag, (2003), 695–698. www.cs.bme.hu/~geza/chromatic.pdf [23] R. Poli and L. Vanneschi, Fitness-Proportional Negative Slope Coefficient as a Hardness Measure for Genetic Algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, (2007), 1335-1342. [24] Salem F. Adra, Ian Griffin and Peter J. Fleming, Hybrid Multiobjective Genetic Algorithm with a New Adaptive Local Search Process, 2005 Genetic and Evolutionary Computation Conference (GECCO’2005), 1, (2005), 1009–1010. [25] T. F. Coleman and J. J More, Estimation of sparse jacobian matrices and graph coloring problems, SIAM Journal, Numerical Analysis, 1(20), (1983), 187–209. [26] The Hadwiger-Nelson Problem, http://en.wikipedia.org/wiki/Hadwiger-Nelson_problem [27] The Open Problem Project, http://maven.smith.edu/~orourke/TOPP/Welcome.html [28] Tournament Selection, http://en.wikipedia.org/wiki/Tournament_selection [29] Vezér-gráfok ( Queen’s Graph ), http://mathworld.wolfram.com/QueensGraph.html

49