home *** CD-ROM | disk | FTP | other *** search
/ Chip 2004 August / Chip_2004-08_cd1.bin / program / ctenari / Jaros / readme.txt < prev    next >
Text File  |  2004-06-20  |  10KB  |  248 lines
  1. +----------------------------------------------------+
  2. |     TV∙RCE ROZVRH┘ 2.2 (c) PAVEL JAROè 2003-04     |
  3. +----------------------------------------------------+
  4. |    Autor:    PAVEL JAROè / FUNKYSHiT               |
  5. |    Web:      http://funkyshit.webpark.cz/          |
  6. |    E-mail:   jaros.pavel@centrum.cz                |
  7. +----------------------------------------------------+
  8.  
  9. +----------------------------------------------------+
  10. | OBSAH                                              |
  11. +----------------------------------------------------+
  12.   
  13.   I.   Nßroky na HW a SW
  14.   II.  Instalace
  15.   III. Co je Tv∙rce rozvrh∙
  16.   IV.  Ovlßdßnφ programu
  17.        1) Zadßnφ vstupnφch dat
  18.        2) Ovlßdßnφ genetickΘho algoritmu
  19.        3) Ulo₧enφ v²stupnφch dat
  20.        4) Popis parametr∙ GA        
  21.   V.   Odpov∞dnost za vady
  22.  
  23. +----------------------------------------------------+
  24. | I. N┴ROKY NA HW A SW                               |
  25. +----------------------------------------------------+
  26.  
  27.   SystΘm s WIN95 a vyÜÜφ.
  28.  
  29. +----------------------------------------------------+
  30. | II. INSTALACE                                      |
  31. +----------------------------------------------------+
  32.   
  33.   Program se neinstaluje, ani se nezapisuje do systΘ-
  34.   movΘho registru. StaΦφ jej jednoduÜe rozbalit a
  35.   zaΦφt pou₧φvat.
  36.   Odinstalace spoΦφvß v pouhΘm smazßnφ programu 
  37.   z disku.
  38.  
  39. +----------------------------------------------------+
  40. | III. CO JE TV┘RCE ROZVRH┘                          |
  41. +----------------------------------------------------+
  42.  
  43.   Program Tv∙rce rozvrh∙ umo₧≥uje pln∞ automatickou 
  44.   tvorbu Ükolnφch rozvrh∙ s vyu₧itφm techniky gene-
  45.   tick²ch algoritm∙.
  46.  
  47.   Program sestavuje Ükolnφ rozvrhy podle zadan²ch 
  48.   omezujφcφch podmφnek, kter²mi jsou: 
  49.  
  50.     a) Silnß omezenφ (povinnß)
  51.        -----------------------  
  52.        - pouze jedinΘ: ₧ßdn² uΦitel nesmφ uΦit 
  53.          v danΘm Φase vφce ne₧ jeden p°edm∞t.
  54.  
  55.   Je nutnΘ, aby v p°φpustnΘm °eÜenφ rozvrhovacφ ·lohy
  56.   nebyl ₧ßdn² t∞₧k² konflikt, tzn. aby vygenerovanΘ
  57.   rozvrhy spl≥ovaly silnß omezenφ.        
  58.  
  59.     b) Slabß omezenφ (volitelnß)
  60.        -------------------------
  61.        - maximßlnφ p°φpustnß mezera v rozvrhu,
  62.        - maximßlnφ p°φpustn² poΦet hodin denn∞,
  63.        - minimßlnφ p°φpustn² poΦet hodin denn∞.
  64.   
  65.   Napln∞nφ vÜech slab²ch omezenφ nenφ pro p°φpustnΘ 
  66.   °eÜenφ nezbytn∞ nutnΘ, p°esto p°i tvorb∞ rozvrh∙
  67.   hrajφ d∙le₧itou roli. Prßv∞ slabß omezenφ urΦujφ
  68.   do jakΘ mφry budou vygenerovanΘ rozvrhy pou₧itelnΘ
  69.   v praxi. V Φφm v∞tÜφ mφ°e jsou omezujφcφ podmφnky
  70.   (silnΘ i slabΘ) spln∞ny, tφm je °eÜenφ kvalitn∞jÜφ.
  71.  
  72.   Program Tv∙rce rozvrh∙ pou₧φvß pro nalezenφ opti-
  73.   mßlnφho °eÜenφ techniku genetick²ch algoritm∙ (GA), 
  74.   kterß je zalo₧ena na p°irozenΘm v²b∞ru, repro-
  75.   dukΦnφm procesu a mutaci genetickΘ informace.
  76.   GA pracuje s populacφ jedinc∙, kterß se vyvφjφ 
  77.   v Φase. Ka₧d² jedinec v populaci odpovφdß jednomu
  78.   z mo₧n²ch °eÜenφ ·lohy (rozvrh∙). V pr∙b∞hu gene-
  79.   racφ (Φasu) dochßzφ k nßr∙stu kvality populace 
  80.   jedinc∙. Toho je dosa₧eno dosa₧eno aplikovßnφm 
  81.   selekce, k°φ₧enφ a mutace. Selekce provßdφ v²b∞r
  82.   jedinc∙, kte°φ se podφlφ na reprodukci. ╚φm je je-
  83.   dinec kvalitn∞jÜφ, tφm v∞tÜφ mß Üanci, ₧e bude vy-
  84.   brßn. K°φ₧enφ zajiÜ¥uje v²m∞nu genetickΘho materiß-
  85.   lu mezi dv∞ma jedinci - rodiΦi. Potomek zφskß od 
  86.   ka₧dΘho rodiΦe pouze Φßst genetickΘ inforamce. A 
  87.   koneΦn∞ mutace udr₧uje variabilitu v populaci, aby
  88.   proces hledßnφ °eÜenφ neuvφzl v lokßlnφm optimu. 
  89.   Vφce inforamcφ o genetick²ch algoritmech m∙₧ete najφt
  90.   nap°. na http://alife.fei.tuke.sk/projekty/gen_alg/. 
  91.   Program Tv∙rce rozvrh∙ navφc pou₧φvß tvz. opravnou
  92.   mutaci, kterß v²znamn∞ napomßhß p°i odstra≥ovßnφ
  93.   konflikt∙ v rozvrhu.
  94.  
  95.   V²stupem programu jsou jednak rozvrhy hodin pro
  96.   jednotlivΘ t°φdy, jednak rozvrhy uΦitel∙.  
  97.  
  98. +----------------------------------------------------+
  99. | IV. OVL┴D┴N═ PROGRAMU                              |
  100. +----------------------------------------------------+
  101.  
  102.   1) Zadßnφ vstupnφch dat
  103.      --------------------
  104.  
  105.   Prvnφm krokem je zadßnφ vstupnφch dat. To je mo₧nΘ
  106.   provΘst bu∩ s pomocφ pr∙vodce nebo ·pravou ji₧ 
  107.   existujφcφch dat.
  108.  
  109.   Pr∙vodce pro zadßvßnφ dat m∙₧ete spustit bu∩ z na-
  110.   bφdky Soubor p°φkazem Zadat data... nebo tlaΦφtkem 
  111.   s ikonou rozvrhu na panelu nßstroj∙ (CTRL+Z).
  112.  
  113.   Nejprve budete vyzvßni k zadßnφ jmΘna souboru se
  114.   vstupnφmi daty (takΘ m∙₧ete p°epsat ji₧ existujφcφ 
  115.   soubor). DalÜφm krokem je napln∞nφ seznamu vyuΦujφ-
  116.   cφch. Na nßsledujφcφm formulß°i zadßte p°edm∞ty
  117.   pro jednotlivΘ t°φdy. U ka₧dΘho p°edm∞tu je t°eba
  118.   vyplnit jeho nßzev, poΦet hodin a zvolit vyuΦujφcφ-
  119.   ho ze seznamu vyuΦujφcφch. Na tomto formulß°i je
  120.   takΘ mo₧nΘ zadat p°edm∞ty s pevn∞ stanov²m dnem
  121.   a hodinou v²uky. Na prvnφ zßlo₧ce poslednφho for-
  122.   mulß°e pr∙vodce nastavφte chovßnφ genetickΘho algo-
  123.   ritmu (poΦet generacφ, poΦet jedinc∙ v generaci, 
  124.   pravd∞podobnosti k°φ₧enφ a mutace atd. - viz 
  125.   Popis parametr∙ GA) a na druhΘ zßlo₧ce zadßte
  126.   data t²kajφcφ se rozvrhu (poΦet hodin denn∞, poΦet
  127.   dn∙ v t²dnu, omezujφcφ podmφnky).
  128.  
  129.   DalÜφ mo₧nostφ je ·prava ji₧ existujφcφch dat.
  130.   Ke vstupnφm dat∙m lze p°istupovat p°es nabφdku Data.
  131.   Formulß° s nastavenφm genetickΘho algoritmu zobra-
  132.   zφte p°φkazem Nastavenφ GA... z nabφdky GA 
  133.   (klßvesovΘ zkratky F5 - F8).
  134.  
  135.   Vstupnφ data je mo₧nΘ uklßdat (CTRL+U) a naΦφtat 
  136.   (CTRL+N). K tomu slou₧φ bu∩ p°φkazy v nabφdce soubor 
  137.   nebo tlaΦφtka na panelu nßstroj∙.
  138.  
  139.   2) Ovlßdßnφ genetickΘho algoritmu
  140.      ------------------------------
  141.   
  142.   Pokud mß program k dispozici vÜechna pot°ebnß 
  143.   vstupnφ data je mo₧nΘ zahßjit genetick² algoritmus.
  144.   K ovlßdßnφ genetickΘho algoritmu je mo₧nΘ pou₧φt
  145.   bu∩ p°φkazy v nabφdce GA nebo tlaΦφtka Start/Pauza/
  146.   Stop na panelu nßstroj∙ (klßvesovΘ zkratky F2 - F4).
  147.  
  148.   Genetick² algoritmus zahßjφte p°φkazem Start, jeho
  149.   b∞h m∙₧ete kdykoliv p°eruÜit p°φkazem Pauza a nechat
  150.   si vypsat dosud nejlepÜφ nalezenΘ °eÜenφ. ╚innost
  151.   algoritmu lze potΘ znovu obnovit p°φkazem Start.
  152.   Algoritmus ukonΦφte p°φkazem Stop.
  153.  
  154.   Pokud je nalezeno °eÜenφ, kterΘ spl≥uje vÜechny
  155.   omezujφcφ podmφnky, je genetick² algoritmus ukonΦen
  156.   automaticky.  
  157.   
  158.   3) Ulo₧enφ v²stupnφch dat
  159.      ----------------------
  160.   
  161.   NalezenΘ °eÜenφ je mo₧nΘ ulo₧it (CTRL+S) do texto-
  162.   vΘho souboru a odtud znovu naΦφst (CTRl+R).
  163.   V²stupnφ data se uklßdajφ jako text odd∞len² st°ed-
  164.   nφky, co₧ je formßt vhodn² pro dalÜφ zpracovßnφ v 
  165.   tabulkovΘm procesoru (nap°. MS Excel).
  166.  
  167.   4) Popis parametr∙ GA
  168.      ------------------
  169.   Pro efektivnφ Φinnost GA je klφΦovΘ jeho sprßvnΘ 
  170.   nastavenφ. Uvßdφm struΦn² popis jednotliv²ch para-
  171.   metr∙ GA, kter² by vßm to m∞l pokud mo₧no usnadnit.
  172.  
  173.   a) Provßd∞t ·pln² GA - ·pln² genetick² algoritmus 
  174.      odpovφda zßkladnφmu tvaru GA (selekce-k°φ₧enφ
  175.      -mutace) a mß smysl jej nasadit pouze na slo₧i-
  176.      t∞jÜφ ·lohy - p°i sestavovßnφ rozvrh∙ pro v∞tÜφ
  177.      poΦet t°φd t°φd). V opaΦnΘm p°φpad∞ je ·loha °e-
  178.      Üena pouze s vyu₧itφm opravnΘ mutace, co₧ je 
  179.      jednak rychlejÜφ a p°edevÜφm v °ad∞ p°φpad∙ na-
  180.      prosto postaΦujφcφ metoda. 
  181.  
  182.   b) P°eruÜit p°i stagnaci trvajφcφ po XX generacφ 
  183.      - v p°φpad∞, ₧e nebylo po urΦit² poΦet generacφ
  184.      nalezeno ₧ßdnΘ kvalitn∞jÜφ °eÜenφ, dojde k auto-
  185.      matickΘmu p°eruÜenφ GA. V p°φpad∞, ₧e proces 
  186.      hledßnφ °eÜenφ nikam nevede, je ukonΦeno a zahßjφ
  187.      se novΘ hledßnφ (viz parametr PoΦet opakovßnφ). 
  188.      Pokud je parametr nastaven na 0, k p°eruÜenφ ne-
  189.      dojde a b∞h GA je ukonΦen po nastavenΘm poΦtu 
  190.      generacφ. Standardn∞ je nastaveno 30 generacφ.
  191.  
  192.   c) PoΦet opakovßnφ GA - urΦuje poΦet nezßvisl²ch 
  193.      b∞hu GA. ╪eÜenφm ulohy pak bude nejkvalitn∞jÜφ
  194.      nalezen² rozvrh ze vÜech b∞h∙.
  195.  
  196.   d) PoΦet generacφ - urΦuje poΦet iteracφ GA. 
  197.      V p°φpad∞, ₧e mßte nasataveno p°eruÜenφ p°i 
  198.      stagnaci, m∙₧e dojφt k ukonΦenφ b∞hu GA p°ed
  199.      dosa₧enφm zvolenΘho poΦtu generacφ. TakΘ v p°φ-
  200.      pad∞, ₧e je nalezeno °eÜenφ bez konflikt∙ dojde
  201.      k p°eruÜenφ GA. DoporuΦuji nastavit vyÜÜφ poΦet
  202.      generacφ (300 a vφce) a souΦasn∞ zapnout p°eru-
  203.      Üenφ p°i stagnaci. 
  204.  
  205.   e) PoΦet jedinc∙ - urΦuje poΦet jedinc∙ v populaci. 
  206.      ╚φm vyÜÜφ poΦet jedinc∙ nastavφte, tφm ÜφrÜφ 
  207.      prostor (mo₧n²ch °eÜenφ) je prohledßvßn a tφm 
  208.      vyÜÜφ je pravd∞pobnost nalezenφ optimßlnφho 
  209.      °eÜenφ. Um∞rn∞ tomu se vÜak sni₧uje i rychlost
  210.      programu. Dobr²ch v²sledk∙ lze dosßhnout zhruba 
  211.      ji₧ od 100 jedinc∙.
  212.  
  213.   f) PoΦet elitnφch jedinc∙ - urΦuje poΦet nejkvalit-
  214.      n∞jÜφch jedinc∙, kte°φ automaticky postupujφ do 
  215.      dalÜφ generace (beze zm∞n), ani₧ by proÜli se-
  216.      lekcφ, k°φ₧enφm a mutacφ. 
  217.      Standardn∞: 1 - 5 jedinc∙.
  218.  
  219.   g) Pravd∞podobnost k°φ₧enφ - urΦuje s jakou pravd∞-
  220.      pobnostφ mß dochßzet ke k°φ₧enφ. 
  221.      Stanadardn∞: 50 - 75 %.
  222.  
  223.   h) Hornφ a dolnφ pravd∞podobnost "opravnΘ" mutace - 
  224.      v p°φpad∞ ·plnΘho GA je opravnß mutace aplikovßna
  225.      dynamicky: z poΦßtku s vyÜÜφ pravd∞pobnostφ, poz-
  226.      d∞ji s ni₧Üφ. To lze interpretovat tak, ₧e v poΦß-
  227.      teΦnφch generacφch je preferovßna v∞tÜφ Üφ°e pro-
  228.      hledßvanΘho prostoru (mo₧n²ch °eÜenφ) a v pozd∞j-
  229.      Üφch generacφch jsou spφÜe prohledßvßna blφzkß 
  230.      okolφ nejkvalitn∞jÜφch °eÜenφ. 
  231.      Stanadardn∞: 100 % a 25 %.
  232.  
  233.   i) Pravd∞podobnost "klasickΘ" mutace - urΦuje s ja-
  234.      kou pravd∞pobnostφ mß dochßzet ke klasickΘ mutaci. 
  235.      Stanadardn∞: 1 - 5 %.
  236.  
  237.  
  238. +----------------------------------------------------+
  239. | V. ODPOV╠DNOST ZA VADY                             |
  240. +----------------------------------------------------+
  241.  
  242.   Autor nenφ zodpov∞dn² za ztrßtu nebo zniΦenφ dat, 
  243.   uÜl² zisk nebo jak²koliv jin² druh ztrßty spojen² 
  244.   s u₧φvßnφm tohoto programu.
  245.  
  246. +----------------------------------------------------+
  247. |                           Pavel JaroÜ, 22. 6. 2004 |
  248. +----------------------------------------------------+