Ütközésmentesítő algoritmus

Az ütközésmentesítő algoritmus egy olyan speciális genetikus algoritmus, ahol csak egyetlen egyedet használunk a genetikai kód örökítésére. Az egyedet, mint általában a genetikus algoritmusokban, véletlenül állítjuk elő. Megtehetjük, hogy már az előállításkor bizonyos alapszabályoknak megfelelő elemekből állítjuk össze. Itt például 1-9 a megengedett számok, majd a megfelelő reprezentáció megválasztásával biztosítjuk, hogy a kisebb négyzeten belül ne kelljen ütközést – hibát – vizsgálnia az értékelő függvénynek, ezzel is rövidítve a futási időt. Sőt olyan esetek is lehetségesek, amikor csak megfelelő reprezentáció alkalmazásával működik megfelelően az ütközésmentesítő algoritmus.

Ezek után megállapítjuk, hogy milyen mértékben nem felel meg a példány az elvárásoknak (azaz hány hibapontos az egyed). Ez a legnehezebb része az egész eljárásnak. Jól kell tudni megválasztani a hibafüggvényt. Itt történik a számolás, összehasonlítás, mely az algoritmus futási idejét a legjobban befolyásolja. Ha a kiértékelés nem nulla hibapontot ad, akkor a következőt tesszük: véletlen helyen és értékkel megváltoztatjuk az egyed egyik (esetleg több) kódját (ez a mutáció). Majd megnézzük, hogy rosszabb lett-e az új egyed, azaz szelektálunk. Ha igen, akkor a változtatást visszavonjuk (természetesen előtte megjegyeztük milyen állapotban volt az egyed), ha nem, akkor az így létrejött egyedet használja tovább az algoritmus, ami lényegében az öröklődés.

Aztán újra meg újra próbálkozunk a mutációval mindaddig, amíg hibátlan egyedet nem kapunk. Jó esetben ez (mármint a hibátlan egyed) értelmes gépi idő alatt létrejön. Itt van az algoritmus másik buktatója: meddig (hány lépésben) és milyen módosításokat alkalmazzunk az algoritmus közben. Előfordulhat, hogy egy bizonyos hibaszámnál leáll a csökkenés, és nem változik a hibapontok száma. Ekkor szintén a tapasztalatok alapján, egy bizonyos lépésszámú ismétlés után ellenőrzés nélküli mutációt hajtunk végre, vagy teljesen új egyedet hozunk létre, és azzal kezdjük újra a keresést. Ha ügyesen vagy egyszerűen csak szerencsésen jártunk el, akkor az algoritmus végén egy, a feladat feltételeit mindenben teljesítő egyedet kaphatunk.

Miért a genetikus algoritmus?

A 9x9-es alap Sudoku tábla összes kitöltési lehetőségeinek hatalmas száma miatt a leggyorsabb számítógépeknek is olyan hosszú időre lenne szüksége az összes kitöltési lehetőség végignézésére (ezáltal a jó táblák illetve feladványok kiválasztására), amely kizárja ezt a lehetőséget. Nem láthatjuk egyszerre az összes helyes alaptáblát, de ugyanúgy az összes feladványt sem. Nem tudunk az alapszabály mellé további szabályokat helyezni, mely orientálhatná a kereső algoritmusokat. Marad a „tű a szénakazalban” módszer. A genetikus algoritmust épp ilyen problémák megoldására találták ki. Nem nekünk kell megfogalmazni a megoldást segítő további szabályokat, hanem az egyedek hordozzák magukban azt a számunkra szinte ismeretlen tulajdonságot, mely hozzásegíti az egyedfejlődés folyamán a tökéletes megoldáshoz.

Miért az ütközésmentesítő algoritmus?

Az első Sudoku táblák generálását genetikus algoritmussal, 30 egyed felhasználásával végeztem még évekkel ezelőtt. A mai algoritmusaimhoz képest nagyon nagy lépésszámú volt ez a generálás. Egy tábla előállítása percekig is eltartott egy átlagos mai PC-n. Az ütközésmentesítő algoritmus egyetlen egyedet használ, javítottam a reprezentáción is, így az algoritmus lépésszáma sokkal kisebb lett, hamarabb készít alaptáblát. Jelenleg közel 50 db alaptáblát tudok másodpercenként előállítani, köszönhetően az ütközésmentesítő gyorsaságának. De ez még csak a Sudoku tábla előállítása, mely a négy feladatból (táblakészítés, feladványkészítés, feladványok megoldása és feladványok minősítése) a legegyszerűbb, a legkönnyebben megoldható.