Ó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}