Az órák ütemezésének egyik algoritmusa
Csend volt, melyet maga Svejk tört ki, sóhajtott:
"... A katonai szolgálatnak fegyelemnek kell lennie - anélkül, hogy senki sem fogta volna meg az ujját. Makovets főhadnagy mindig azt mondta: "Fegyelem, bábuk szükségesek. Ha nem lenne fegyelem, akkor felmászni, mint egy majom a fák között. A katonai szolgálat, bolond bolondok, emberek fognak tenni! "Nos, nem igaz? Képzelj el egy négyzetet magadnak, mondjuk a Károly téren, és minden fán egy fegyveres katona van. Rettenetesen megrémít.
Jaroslav GASHEK A BROWN SÓZSÁK MÉRETEI
Az osztályok ütemezése a diákok (tantárgy), a tanár (tanárok), a közönség és a csoport (alcsoport, folyó) kombinációja térben és időben.
A probléma megfogalmazása
Következtetés. Amint az állításból kiderül, az ütemterv minősége csak a teljes körű összeállítás után lehetséges. Következésképpen a genetikai algoritmusok használata lehetővé teheti számunkra, hogy megoldást találjunk a kívánt problémára, sőt egy bizonyos értelemben is az egyik jóat kapjuk. Ebben az esetben a genetikai algoritmusok nagyon gyorsan konvergálnak az optimális kezdethez, ezért a bemeneti adatok mennyisége gyakorlatilag nem lesz korlátozva.
A kép innen származik.
Genetikai algoritmus
Pusztán retorikailag megismétlem a genetikai algoritmus főbb szakaszait:
- Adja meg a lakosság egyének objektív funkcióját (fitness)
- Hozzon létre egy kezdeti populációt
- (A ciklus kezdete)
- Sokszorosítás (átkelés)
- mutálódik
- Számítsa ki az objektum értékét minden egyén számára
- Új generáció létrehozása (kiválasztás)
- Ha a leállási feltételek teljesülnek, akkor a ciklus vége, különben (a ciklus kezdete).
A genetikai algoritmusok leggyakoribb hibája a gének kiválasztása. Gyakran, mint gén, a döntés egyszerűen a választás. A genetikai választás a genetikai algoritmus létrehozásának leginkább triviális és kreatív eleme. Személy szerint úgy vélem, hogy a gének kiválasztása a következő két alapvető követelménynek kell megfelelnie.
- A gének készleténél a kívánt probléma megoldását gyorsan és egyértelműen kell megalkotni.
- Átkeléskor a leszármazottnak örökölnie kell a szülők sajátosságait.
Az ütemezés algoritmusa
Én csak a géneket fogom leírni, az algoritmust, hogy megoldásokat hozzanak létre, keresztezzék és mutálják.
Hogyan kell ütemezni egy tapasztalt diszpécsert? A tapasztalt szó azt jelenti, hogy a diszpécser időközben már összeállította az ütemtervet és ismerte a szűk keresztmetszeteket. Például a nagyméretű streaming közönségek vagy számítógéposztályok hiánya. Az első kurzus, mivel sok előadást tartanak, és ugyanakkor a számítógéposztályok alcsoportjaiban angol vagy angol, a semmiből / német / francia stb. és a hatóságok egyidejűleg megkövetelik, hogy az elsõ kurzus semmiképpen ne legyen ablak, és napi két naponta többet, és a napokat egyenletesen terhelték. Ezért egy tapasztalt diszpécser először "keskeny osztályokat", a felettesek osztályait kérésre és a különösen zavaró tanárok osztályait állítja elő. Ezután az elrendezett osztályokat csontvázaként gyorsan elvégzi az ütemezést. Próbáljuk meg bizonyos értelemben szimulálni ezt a folyamatot.
Része természetesen már megvan az a menetrend, a fennmaradó sorozat számba. A tömb szám foglalt, feltesszük a genom, bár elvileg itt fontos a sorrendben az osztályok. Az építési ütemterv következetesen abból munkahelyek számát, és tegye a választott szakma a menetrend, hogy a szükséges követelményeknek megfelelő és a lehető legnagyobb célfüggvény a diákok, a tanárok és a tantermekben (ők is a kritériumok foglalkoztatás).
Ha a szükséges követelmények nem teljesülnek, akkor az ilyen genommal rendelkező egyén elveszi, mint nem életképes. Ha az ütemterv nem működik, akkor a célkövetelményben a szükséges követelményeket egy büntetéssel helyettesítheti.
A kereszteződés számos módon szervezhető. Például egyikük. Tegyük fel, hogy a következő gének vannak
3 1 2 5 6 4 7
2 3 5 7 1 4 6
Látható, hogy a 3. foglalkozás mindkét génben a 2. pozícióba bejövő, és például a 2. pozíciótól az 5. pozícióig terjed, az 1 munkamenet intervalluma. A következő tablettát tesszük
_ * * * * _ _ 1 leckét
* * * _ _ _ _ 2 leckét
* * _ _ _ _ _ 3 lecke
_ _ _ _ _ _ _ 4 lecke
_ _ * * _ _ _ 5 órára
_ _ _ _ * * * 6 lecke
_ _ * * * * 7 lecke
Itt a csillagok az utódok számának lehetséges pozícióit jelölik. Egy vagy több lehetséges megoldás közül választhat, mint ezeknek a szülőknek a leszármazottai vagy leszármazottai. Mindig van megoldás az utódok génjének kiválasztásához, például mindkét szülő megelégszik vele. Újraírjuk az asztalt a lehetséges pozíciókban
A megoldások létrehozásához a következő algoritmust használhatja. Először a kevésbé gyakori osztályok számát tesszük. Ha növekvő sorrendben vannak rendezve, akkor leszünk
1 alkalommal 4
2 alkalommal 3, 5
3 alkalommal 2, 6
4 alkalommal 1, 7
Ezért először 4 osztályba helyeztük 6 pozícióban, majd 3 vagy 5 pozícióban, illetve. Minden lépésnél dobhat egy doboz mérkőzést. Ennek eredményeképpen a crossover algoritmus például a következõ lépésekkel érhetõ el
* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6
Mivel lehetséges, és nem a megfelelő szekvencia létrehozása, jobb az algoritmust egy egyszerű rekurzió formájában megszervezni az algoritmus megismétlésének lehetőségére, azaz egyes válogatás szervezése.
A mutáció egyszerűen megszervezhető, a foglalkozási számok véletlen átrendezésével.
következtetés
Megismételem a következő megoldást (vázlat).
Köszönet mindenkinek, aki válaszolt, miután megvitatták ezt a témát, lehetőség nyílt megszervezni.