+----------------------------------------------------+ | TVůRCE ROZVRHŮ 2.3 (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) Uložení vstupních dat 3) Ovládání genetického algoritmu 4) Uložení výstupních dat 5) Popis parametrů GA V. Odpovědnost za vady +----------------------------------------------------+ | I. NÁROKY NA HW A SW | +----------------------------------------------------+ Systém s WIN95 a vyšší. +----------------------------------------------------+ | II. INSTALACE | +----------------------------------------------------+ Spusťte instalační soubor a postupujte podle in- strukcí instalačního programu. +----------------------------------------------------+ | 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: 1) 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í. 2) 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. 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íce inforamcí o genetických algoritmech můžete najít např. na: http://alife.fei.tuke.sk/projekty/gen_alg/. 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). 2) Uložení vstupních dat --------------------- 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ů. Vstupní data je možné ukládat ve dvou různých formátech: a) Formát DAT - data v tomto souboru, nelze upra- vovat pomocí textového editoru (jako je např. Poznámkový blok - Notepad). Změny je možné pro- vádět pouze v programu Tvůrce rozvrhů. Výhodou tohoto formátu je vysoká rychlost při ukládání a načítání vstupních dat. b) Formát INI - data lze měnit jak v programu, tak pomocí textového editoru, ovšem za cenu pomalej- šího ukládání a načítání (což se projeví zvláště pokud soubor obsahuje velké množství dat). Mezi těmito formáty je možné provádět konverze, tzn. načíst vstupní data ve formátu DAT a uložit je do sou- boru typu INI nebo naopak. 3) 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. 4) 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). 5) 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) 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 nezávislých běhů GA). Pokud je parametr nastaven na 0, k pře- rušení nedojde a běh GA je ukončen po nastaveném počtu generací. b) Počet nezávislých běhů GA - určuje počet opakování GA. Řešením ulohy pak bude nejkvalitnější nalezený rozvrh ze všech běhů. Pokud je v některém běhu na- lezeno řešení bez konfliktů, dojde k přerušení GA a zbývající běhy se již neprovedou. c) 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í (200 a více) a současně zapnout přeru- šení při stagnaci. d) 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ů. e) 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ů. f) Pravděpodobnost křížení - určuje s jakou pravdě- pobností má docházet ke křížení. Stanadardně: 50 - 75 %. g) 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 %. h) Pravděpodobnost mutace - pevně definované předměty - stanovuje s jakou pravděpodobností má docházet k opravné mutaci na dnech v rozvrhu, ve kterých jsou pevně definované předměty (s pevně stanovenou do- bou výuky). Stanadardně: 50 - 75 %. 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š, 21. 8. 2004 | +----------------------------------------------------+