Órarendkészítés genetikus algoritmussal

A Gépi órarendkészítő demonstrációs program menüpontban alkalmazott, géppel generált tantárgyfelosztáshoz írjunk órarendkészítő programot, mely a genetikus algoritmust használja. Emlékeztetőül: az osztályok száma 32, minden osztálynak 30 órája van (egy 5-órás, két 4-órás, három 3-órás és négy 2-órás tantárgyakkal - a teljes intézményre nézve ez 960 óra), a pedagógusok száma 50, egy tanár egy osztályban csak egy tantárgyat tanít, egy pedagógusnak maximum 26 órája lehet. A program nem tart nyilván tantárgyakat és tantermeket.

Az így előállított órarend szintén nem lesz a gyakorlatban használható. A programnak nem is ez a célja, hanem tesztelni a genetikus algoritmust órarend-készítési feladatra. Az említett menüpontbeli programnál ez a program többet követel meg, és mint láthatjuk, teljesít is az elkészült órarendre vonatkozóan, éspedig: kétórás tárgyat nem tesz két egymás utáni napra.

A genetikus algoritmust akkor célszerű használni, ha a probléma megoldására nem létezik egyszerű keresési eljárás többek között épp azért nem, mert a keresési tér nagyon nagyszámú elemet tartalmaz, melynek bejárása gyakorlatilag lehetetlen. Órarendkészítésnél pedig éppen ez a helyzet. Genetikus algoritmusban a keresés alapja a véletlen választás, majd a generációnkénti vizsgálat, minősítés mely a keresztezésnek és a mutációnak az alapja, melyek szintén véletlen választásokat használnak.

A program a genetikus algoritmusok alapelvét alkalmazva, először generál egy teljes populációt, az órarendeket véletlenül feltöltve. A populáció egyedszáma 50. Az órarendek alapján a program egy ütközési táblát készít, melyben a nem 0 elemeknek a száma, az egyed fitnesz értéke lesz. Cél a 960-as fitnesz érték elérése.

A program a genetikus algoritmus alapelvei szerint keres két átlagosnál nagyobb fitnesz értékű egyedet, melyeket egy keresztezési ponttal keresztez (160-as indexnél) és a két leggyengébb elemet ezekkel helyettesíti. Ezt mindaddig ismétli, amíg a jók száma nagyon alacsony vagy nagyon magas lesz, mert ekkor egy 3 tized százalékos teljes mutációt hajt végre, a jókra vonatkozóan egy 10 mutációs rátával.

A program paraméterei, kezelése. Először generálnunk kell egy új tantárgyfelosztást. Majd beállítjuk a szükséges egyedszámot. Kísérleteim szerint ezt 30 és 100 között célszerű megválasztani. Alacsonyabb egyedszám esetén, a generálás elején gyorsabban haladhatunk, de ekkor a végén lassabb az előrejutás. Magasabb egyedszám esetén pontosan fordítva: először lassúbb, majd később relatíve gyorsabb az újabb jó megoldás megtalálása. Célszerűbb az utóbbit választani, hiszen a generálás a vége felé a kezdeti ütemnek csak töredéke (tízezred, százezred része). Én konkrétan, szem előtt tartva a gépem teljesítményét, a legtöbb teszt esetén 50 egyedszámmal futtattam a programot.

A generálás végének gyorsítása, azaz a megoldás megtalálási idejének csökkentése végett, az algoritmus a túl lassú konvergálás esetére egy perturbációt (egy relatíve erős véletlen mutációt) használ, mely tapasztalataim szerint segít átlendíteni a keresést a dermedési pontokon. Ezek után előállíthatunk egy új populációt. További beállítási lehetőségek: módosíthatjuk az alapértelmezett mutációs értékeket, a keresztezési számot. Meghatározhatjuk a populációk maximális számát, mint korlátozó értéket arra az esetre, ha a végén az algoritmus kényelmetlenül hosszú ideig keresgélne.

A továbbiakban lássunk néhány eredményt. A legfontosabb korlátozó beállítás a megengedett óra-időpontok. A következő táblázat a különböző időpontokra a kezdeti populációk körülbelüli fitnesz értékeit tartalmazza.

Óra-időpontok	Átlagos fitnesz érték
0.-9.	740
1.-9.	720
1.-8.	695
1.-7.	660
1.-6.	625

Ezen fitnesz értékeknek a 960-ra való feljuttatása, az egyre kisebb megengedett napi óraszám mellett, egyre nehezebb. Lássuk ezt is táblázatosan.

Óra-időpontok	Átlagos populációszám	Átlagos generálási idő
0.-9.	9.000	10 sec
1.-9.	12.000	12 sec
1.-8.	40.000	40 sec
1.-7.	90.000	1 perc
1.-6.	3.200.000	30 perc

A következő screenshot-okon egy-egy futási kép látható. Középen az elkészített órarend. A jobboldali listadobozban az egyedek fitnesz értékei, alul a beviteli mezők és kezelő gombok találhatók. A program méri és kiírja a futási időt.

Először a 0.-9. órarendi órák esetén:

Az 1.-9. órarendi órák esetén:

Az 1.-8. órarendi órák esetén:

Az 1.-7. órarendi órák esetén:

Végül pedig az 1.-6. órarendi órák esetén egy futási kép, ami legtöbb esetben a legfontosabb cél. Itt minden osztály minden órája főhelyre kerül. Nincs egyetlen osztálynak sem lyukasórája és nincs hetedik vagy későbbi sem.

A program listája:

{Ami még nem publikus… L}