+----------------------------------------------------+ | TVůRCE ROZVRHŮ 2.2 (c) PAVEL JAROŠ 2003-04 | +----------------------------------------------------+ | Autor: PAVEL JAROŠ / FUNKYSHiT | | Web: http://funkyshit.webpark.cz/ | | E-mail: jaros.pavel@centrum.cz | +----------------------------------------------------+ +----------------------------------------------------+ | OBSAH | +----------------------------------------------------+ I. Nároky na HW a SW II. Instalace III. Co je Tvůrce rozvrhů IV. Ovládání programu 1) Zadání vstupních dat 2) Ovládání genetického algoritmu 3) Uložení výstupních dat 4) Popis parametrů GA V. Odpovědnost za vady +----------------------------------------------------+ | I. NÁROKY NA HW A SW | +----------------------------------------------------+ Systém s WIN95 a vyšší. +----------------------------------------------------+ | II. INSTALACE | +----------------------------------------------------+ Program se neinstaluje, ani se nezapisuje do systé- mového registru. Stačí jej jednoduše rozbalit a začít používat. Odinstalace spočívá v pouhém smazání programu z disku. +----------------------------------------------------+ | III. CO JE TVŮRCE ROZVRHŮ | +----------------------------------------------------+ Program Tvůrce rozvrhů umožňuje plně automatickou tvorbu školních rozvrhů s využitím techniky gene- tických algoritmů. Program sestavuje školní rozvrhy podle zadaných omezujících podmínek, kterými jsou: a) Silná omezení (povinná) ----------------------- - pouze jediné: žádný učitel nesmí učit v daném čase více než jeden předmět. Je nutné, aby v přípustném řešení rozvrhovací úlohy nebyl žádný těžký konflikt, tzn. aby vygenerované rozvrhy splňovaly silná omezení. b) Slabá omezení (volitelná) ------------------------- - maximální přípustná mezera v rozvrhu, - maximální přípustný počet hodin denně, - minimální přípustný počet hodin denně. Naplnění všech slabých omezení není pro přípustné řešení nezbytně nutné, přesto při tvorbě rozvrhů hrají důležitou roli. Právě slabá omezení určují do jaké míry budou vygenerované rozvrhy použitelné v praxi. V čím větší míře jsou omezující podmínky (silné i slabé) splněny, tím je řešení kvalitnější. Program Tvůrce rozvrhů používá pro nalezení opti- málního řešení techniku genetických algoritmů (GA), která je založena na přirozeném výběru, repro- dukčním procesu a mutaci genetické informace. GA pracuje s populací jedinců, která se vyvíjí v čase. Každý jedinec v populaci odpovídá jednomu z možných řešení úlohy (rozvrhů). V průběhu gene- rací (času) dochází k nárůstu kvality populace jedinců. Toho je dosaženo dosaženo aplikováním selekce, křížení a mutace. Selekce provádí výběr jedinců, kteří se podílí na reprodukci. Čím je je- dinec kvalitnější, tím větší má šanci, že bude vy- brán. Křížení zajišťuje výměnu genetického materiá- lu mezi dvěma jedinci - rodiči. Potomek získá od každého rodiče pouze část genetické inforamce. A konečně mutace udržuje variabilitu v populaci, aby proces hledání řešení neuvízl v lokálním optimu. Více inforamcí o genetických algoritmech můžete najít např. na http://alife.fei.tuke.sk/projekty/gen_alg/. Program Tvůrce rozvrhů navíc používá tvz. opravnou mutaci, která významně napomáhá při odstraňování konfliktů v rozvrhu. Výstupem programu jsou jednak rozvrhy hodin pro jednotlivé třídy, jednak rozvrhy učitelů. +----------------------------------------------------+ | IV. OVLÁDÁNÍ PROGRAMU | +----------------------------------------------------+ 1) Zadání vstupních dat -------------------- Prvním krokem je zadání vstupních dat. To je možné provést buď s pomocí průvodce nebo úpravou již existujících dat. Průvodce pro zadávání dat můžete spustit buď z na- bídky Soubor příkazem Zadat data... nebo tlačítkem s ikonou rozvrhu na panelu nástrojů (CTRL+Z). Nejprve budete vyzváni k zadání jména souboru se vstupními daty (také můžete přepsat již existující soubor). Dalším krokem je naplnění seznamu vyučují- cích. Na následujícím formuláři zadáte předměty pro jednotlivé třídy. U každého předmětu je třeba vyplnit jeho název, počet hodin a zvolit vyučující- ho ze seznamu vyučujících. Na tomto formuláři je také možné zadat předměty s pevně stanovým dnem a hodinou výuky. Na první záložce posledního for- muláře průvodce nastavíte chování genetického algo- ritmu (počet generací, počet jedinců v generaci, pravděpodobnosti křížení a mutace atd. - viz Popis parametrů GA) a na druhé záložce zadáte data týkající se rozvrhu (počet hodin denně, počet dnů v týdnu, omezující podmínky). Další možností je úprava již existujících dat. Ke vstupním datům lze přistupovat přes nabídku Data. Formulář s nastavením genetického algoritmu zobra- zíte příkazem Nastavení GA... z nabídky GA (klávesové zkratky F5 - F8). Vstupní data je možné ukládat (CTRL+U) a načítat (CTRL+N). K tomu slouží buď příkazy v nabídce soubor nebo tlačítka na panelu nástrojů. 2) Ovládání genetického algoritmu ------------------------------ Pokud má program k dispozici všechna potřebná vstupní data je možné zahájit genetický algoritmus. K ovládání genetického algoritmu je možné použít buď příkazy v nabídce GA nebo tlačítka Start/Pauza/ Stop na panelu nástrojů (klávesové zkratky F2 - F4). Genetický algoritmus zahájíte příkazem Start, jeho běh můžete kdykoliv přerušit příkazem Pauza a nechat si vypsat dosud nejlepší nalezené řešení. Činnost algoritmu lze poté znovu obnovit příkazem Start. Algoritmus ukončíte příkazem Stop. Pokud je nalezeno řešení, které splňuje všechny omezující podmínky, je genetický algoritmus ukončen automaticky. 3) Uložení výstupních dat ---------------------- Nalezené řešení je možné uložit (CTRL+S) do texto- vého souboru a odtud znovu načíst (CTRl+R). Výstupní data se ukládají jako text oddělený střed- níky, což je formát vhodný pro další zpracování v tabulkovém procesoru (např. MS Excel). 4) Popis parametrů GA ------------------ Pro efektivní činnost GA je klíčové jeho správné nastavení. Uvádím stručný popis jednotlivých para- metrů GA, který by vám to měl pokud možno usnadnit. a) Provádět úplný GA - úplný genetický algoritmus odpovída základnímu tvaru GA (selekce-křížení -mutace) a má smysl jej nasadit pouze na složi- tější úlohy - při sestavování rozvrhů pro větší počet tříd tříd). V opačném případě je úloha ře- šena pouze s využitím opravné mutace, což je jednak rychlejší a především v řadě případů na- prosto postačující metoda. b) Přerušit při stagnaci trvající po XX generací - v případě, že nebylo po určitý počet generací nalezeno žádné kvalitnější řešení, dojde k auto- matickému přerušení GA. V případě, že proces hledání řešení nikam nevede, je ukončeno a zahájí se nové hledání (viz parametr Počet opakování). Pokud je parametr nastaven na 0, k přerušení ne- dojde a běh GA je ukončen po nastaveném počtu generací. Standardně je nastaveno 30 generací. c) Počet opakování GA - určuje počet nezávislých běhu GA. Řešením ulohy pak bude nejkvalitnější nalezený rozvrh ze všech běhů. d) Počet generací - určuje počet iterací GA. V případě, že máte nasataveno přerušení při stagnaci, může dojít k ukončení běhu GA před dosažením zvoleného počtu generací. Také v pří- padě, že je nalezeno řešení bez konfliktů dojde k přerušení GA. Doporučuji nastavit vyšší počet generací (300 a více) a současně zapnout přeru- šení při stagnaci. e) Počet jedinců - určuje počet jedinců v populaci. Čím vyšší počet jedinců nastavíte, tím šírší prostor (možných řešení) je prohledáván a tím vyšší je pravděpobnost nalezení optimálního řešení. Uměrně tomu se však snižuje i rychlost programu. Dobrých výsledků lze dosáhnout zhruba již od 100 jedinců. f) Počet elitních jedinců - určuje počet nejkvalit- nějších jedinců, kteří automaticky postupují do další generace (beze změn), aniž by prošli se- lekcí, křížením a mutací. Standardně: 1 - 5 jedinců. g) Pravděpodobnost křížení - určuje s jakou pravdě- pobností má docházet ke křížení. Stanadardně: 50 - 75 %. h) Horní a dolní pravděpodobnost "opravné" mutace - v případě úplného GA je opravná mutace aplikována dynamicky: z počátku s vyšší pravděpobností, poz- ději s nižší. To lze interpretovat tak, že v počá- tečních generacích je preferována větší šíře pro- hledávaného prostoru (možných řešení) a v pozděj- ších generacích jsou spíše prohledávána blízká okolí nejkvalitnějších řešení. Stanadardně: 100 % a 25 %. i) Pravděpodobnost "klasické" mutace - určuje s ja- kou pravděpobností má docházet ke klasické mutaci. Stanadardně: 1 - 5 %. +----------------------------------------------------+ | V. ODPOVĚDNOST ZA VADY | +----------------------------------------------------+ Autor není zodpovědný za ztrátu nebo zničení dat, ušlý zisk nebo jakýkoliv jiný druh ztráty spojený s užíváním tohoto programu. +----------------------------------------------------+ | Pavel Jaroš, 22. 6. 2004 | +----------------------------------------------------+