Előszó

A Fejlett keresőalgoritmusok™ elnevezésű tantárgyat már 2007-től oktatjuk a Debreceni Egyetem Informatikai Karának Programtervező Informatikus MSc. képzésén a Mesterséges Intelligencia szakirányon belül. A kényszer-kielégítés módszerének részletes ismertetése mellett kezdetben különféle programozási nyelveken implementáltuk a már jól ismert algoritmusokat, nem igazán fordítottunk hangsúlyt az egyes módszerek eredményességének és sebességének összehasonlítására. 2010-ben kezdtük el a korrelációs klaszterezés feladatával ismerkedést, majd 2011-ben implementáltunk is több módszert. Az implementáció során törekedtünk arra, hogy egy keretrendszert hozzunk létre, melyben összehasonlíthatóak a különféle módszerekhez tartozó eredmények. Az így kapott kódot jelentősen átírva és kibővítve készült el az a programcsomag, melyet ez a jegyzet bemutat. Engedtessék meg, hogy felsoroljuk mindazokat a hallgatókat, akik tevékenyen részt vettek a jegyzet kiindulási pontjának számító módszerek összegyűjtésében és implementálásában: Bónis Balázs, Dusza Anikó, Juhász Gábor, Koós Dániel, Legoza József, Morsiani Renato, Szatmári László, Szokol Péter és Tanyi Attila.

Míg a kényszer-kielégítésről bőven található rendszerező angol és magyar nyelvű anyag, az ismertetésre kerülő módszerek egységes bemutatására nem találtunk példát. Ezért is született ez a könyv, hogy a különféle forrásokból elérhető információkat viszonylag egységes szemléletben bemutassuk, példát adjunk azok konkrét implementálására.

Egy rövid bevezető után ismertetjük az általunk használt jelölésrendszert, mellyel megfogalmazhatóak a feladatok (2.1), valamint a State, StateR és StateRCabsztrakt osztályokat, mely egy-egy feladatban előforduló állapotot írnak le (2.2-2.4), és a különféle megoldási módszerek ősosztályát a SolvingMethod-ot (2.5).

Ezután a lokális keresés módszerén alapuló algoritmusokat és azok implementációit ismertetjük. Ismertetésre kerül a jól ismert hegymászó keresés, és kevésbé ismert változatai, a tabu keresés különféle megvalósításai, a sok területen eredményesen használt szimulált hűtés, valamint a minimális konfliktusok és annak a szerzők által átírt változatai (3.1-8).

Ezt a sokaságokon alapuló algoritmusok és implementációik követik. Valamelyest követjük a módszerek kifejlesztésének idejét, így a régről ismert és elterjedt evolúciós és genetikus módszerekkel kezdünk. Majd a rovarraj algoritmus következik, amit annak egy változata, a szentjánosbogár algoritmus követ. Ezután a méhek algoritmusát ismertetjük, és végül az élővilágból származó módszereket egy zenei (harmónia keresés) és a kereszt-entrópia módszer zárja (4.1-7).

A sok általános módszer ismertetése után egy konkrét feladatot mutatunk be, a korrelációs klaszterezést. Ennek a problémának a leírása egyszerű, viszont NP bonyolultsága miatt könnyedén generálhatunk igen nehéz feladatokat, hogy az előbb ismertetett módszereket tesztelhessük. Mivel a feladat kiírásában szerepel egy gráf, külön figyelmet kell fordítani ennek megfelelő tárolására, a állapotok specialitásainak megfogalmazására, a különféle ábrázolási módok alkalmazásának hatására a program futási sebességére (5.1-6.).

A speciális feladat esetén ki lehet használni a feladat specialitásait. Mi is ezt tesszük, megadunk pár új módszert, amelyeket a korrelációs klaszterezés feladatának megoldására fejlesztettünk ki (6.1-2).

A 7. fejezet bemutatja, hogy hogyan teljesítenek az eddig ismertetett módszerek korrelációs klaszterezés feladata esetén az általunk talált legjobb paraméterek mellett.

Végül vázlatosan ismertetjük a kényszer-kielégítési problémát, mely megoldására napjainkban már nagy számban léteznek kész rendszerek.

Ahol lehet, ott nagy számban szerepeltetünk feladatokat; mert úgy valljuk, hogy úgy lehet igazán elsajátítani a módszereket, ha aktívan foglalkozunk vele, ami esetünkben programírást jelent.