7. fejezet - Futási eredmények

Tartalom

Hegymászó keresések
alap módszer és variánsai
Iterált hegymászó
Szétszórt keresés
Sztochasztikus hegymászó
Tabu keresés
Szimulált hűtés
Konfliktusok
Evolúciós stratégia, genetikus algoritmus
Rovarok
Harmónia keresés
Kereszt-entrópia
Kontrakció
Hibrid módszerek
Összegzés
Feladatok

Lássuk, hogyan teljesítenek az egyes módszerek a korrelációs klaszterezés feladata esetén! 200 csúcsból álló gráfokkal fogunk dolgozni, olyan Erdős-Rényi gráfokkal, ahol p=70, azaz a teljes gráf éleinek 30 százaléka hiányzik. Az első teszteknél még 10 véletlen gráfot tekintünk, és minden gráfnál 10-10 véletlen kiválasztott pontból indítjuk el a keresési algoritmust. Mivel ezeknél a gráfoknál igen szépen megfigyelhető egy fázistranszformáció, így egy-egy gráf csúcsait 101 fokozatban alakítjuk át. Kezdetben minden él negatív, majd végül minden él pozitívvá válik. (Az ábrákon a q pozitív élek arányát jelzi az összes élek között.) Az elméleti eredmények alapján akkor történik a fázistranszformáció, mikor a negatív és pozitív élek száma megegyezik. Annak érdekében, hogy az egyes módszerek hatékonyságát összehasonlíthassuk, egyrészt megvizsgáljuk az egyes célfüggvényértékeket, valamint a maximális klaszterek méretét.

Az implementált módszerek között számolásigényesek is találhatóak. Ennek megfelelően ott már nem vizsgáljuk meg a gráf éleinek egymást követő 101 különféle címkézését, megelégedünk tizeneggyel. Hasonlóképpen csak 5 véletlen gráffal dolgozunk, és mindegyiknél 5 különböző indítással. Ha egymásra kerülnének a vonalak az ábrán, bizonyos eredmények konzekvensen eltolunk vízszintes irányban. Reméljük ezzel nem zavarjuk meg a megértést. Az ábrák nagy részén feltüntetjük nem csak az átlagos értéket, hanem a minimálisat és maximálisat is.

Azt könnyű belátni, hogy a korrelációs klaszterezés feladatánál ha csak - vagy ha csak + jellel jelölt éleink vannak, akkor a klaszterezéssel elérhető célfüggvényérték 0. Előbbi esetben egyelemű partíciókat kell készíteni, míg a másik esetben csak egyet, melybe minden csúcs beletartozik. Csak erre figyelve már értékelni tudjuk az ábrákon látható eredményeket

Hegymászó keresések

alap módszer és variánsai

Az első módszerünk a hegymászó keresés volt. Itt egy-egy n-dimenziós vektornak közel n2 szomszédja van. Mivel esetünkben n=200, így a szomszédok száma közel 40000. Természetesen ez már elég nagy szám, hogy próbáljunk spórolni a szomszédok vizsgálatán. A FirstBetter variáns és a HCAll összehasonlítása során látszik, hogy nagyon spórolni nem érdemes. Minél kevesebb — véletlen módon kiválasztott — szomszédot vizsgálunk meg, annál inkább eltávolodunk az eredeti hegymászó algoritmussal kapott eredménytől nagyobb q értékek esetén.

7.1. ábra - Hegymászó keresés és First Better variánsának célfüggvényértékei

Hegymászó keresés és First Better variánsának célfüggvényértékei

Ha ugyanezekben az esetekben a maximális klaszter méretét tekintjük, akkor láthatjuk, hogy az eredeti hegymászó algoritmus jól teljesít, viszont a spórolásokkal nem jutunk az elméleti határérték közelébe nagy q esetén.

7.2. ábra - Hegymászó keresés és First Better variánsának maximális klaszterméretei

Hegymászó keresés és First Better variánsának maximális klaszterméretei

Hasonló eredményeket kaphatunk akkor is, ha nem külön-külön válogatunk az egyes szomszédok között, hanem kijelölünk pár irányt, melyeket megvizsgálunk. Természetesen minél kevesebb irányt vizsgálunk meg egy-egy lépés során, annál nagyobb az esélye hogy egyik esetben megtaláljuk a jó irányt, míg máskor pedig nem, azaz a keresési módszer eredményei egyre nagyobb szórást adjanak.

7.3. ábra - Hegymászó keresés és irányok szűkítése

Hegymászó keresés és irányok szűkítése
Hegymászó keresés és irányok szűkítése

7.4. ábra - Hegymászó keresés és variánsai

Hegymászó keresés és variánsai
Hegymászó keresés és variánsai

Iterált hegymászó

A hagyományos hegymászó keresésnek első variánsa volt az iterált keresés. Ha összehasonlítjuk a hagyományos verziót a iterálttal, akkor első látásra nem sok különbséget vehetünk észre:

7.5. ábra - Hegymászó keresés és iterált hegymászó keresés (teljes környezet) összehasonlítása

Hegymászó keresés és iterált hegymászó keresés (teljes környezet) összehasonlítása
Hegymászó keresés és iterált hegymászó keresés (teljes környezet) összehasonlítása

Ha alaposabban megvizsgáljuk a célfüggvényértékeket, akkor kiderül, hogy van értelme az ismétlésnek. Természetesen minél többször indítjuk újra a keresést (a rajzon az L paraméter) a lokális minimumhoz közeli pontból, annál nagyobb az esélye, hogy egy elég jó megoldást kaphassunk. Természetesen a futási idő is ennek megfelelően nő.

7.6. ábra - Az iterált a hagyományos hegymászó keresés célfüggvényértékeinek aránya

Az iterált a hagyományos hegymászó keresés célfüggvényértékeinek aránya

Az iterált keresésnek van egy másik paramétere is: a mutáció foka (az ábrákon M), azaz mennyire változtatjuk meg az állapotot, hogy a lokális minimumból elszabadulhassunk. Ezt az értéket 1 és 19 százalék között kipróbáltuk minden egészre. Az alábbi ábrából látható, hogy 3 és 4 százalék között van az optimális érték ennél a feladatnál.

7.7. ábra - A mutáció foka megválasztásának következményei

A mutáció foka megválasztásának következményei

7.8. ábra - Iterált hegymászó keresés és variánsai

Iterált hegymászó keresés és variánsai
Iterált hegymászó keresés és variánsai

Szétszórt keresés

A szétszórt keresés az iterált keresés párhuzamos verziója. Az erre a módszerre kapott eredmények azt mutatják, hogy nagyjából egy fél százaléknyi javulást lehetett elérni az egyszerű iterált hegymászó kereséshez képest, ami nagyjából szintén ennyivel jobb a hagyományos hegymászó keresésnél.

7.9. ábra - A hagyományos, az iterált és a szétszórt hegymászó keresés célfüggvényértékeinek aránya

A hagyományos, az iterált és a szétszórt hegymászó keresés célfüggvényértékeinek aránya

7.10. ábra - Szétszórt hegymászó keresés és variánsai

Szétszórt hegymászó keresés és variánsai
Szétszórt hegymászó keresés és variánsai