První série dvacátého osmého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

• Termín série: 26. října 2015 8:00
• Termín CodExové úlohy: 26. října 2015 8:00
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Řešitelům, kteří vyřeší alespoň jednu ze dvou nejvíc bodovaných úloh první série na plný počet bodů, pošleme sladkou odměnu.

Zadání úloh

• 28-1-1: Jízda na biomotorce
• 28-1-2: Zapalování kostek
• 28-1-3: Bourání komínu I
• 28-1-4: Bourání komínu II
• 28-1-5: Likvidace plísně
• 28-1-6: Úloha z ovladače
• 28-1-7: Vyříznutý kus mříže
• 28-1-8: Programování podle Darwina

28-1-1 Jízda na biomotorce (10 bodů)

Představte si, že jedete městem na motorce, jiné než té v příběhu: na biomotorce. Takové, která jezdí na pomeranče. Na jeden pomeranč je schopná ujet celých 100 metrů. Má to ale háček: pomeranče jsou velké a vejde se jich do nádrže jen 10. Naštěstí ale pomeranče ve městě jen tak rostou na stromech.

Mapa je tvořená křižovatkami a ulicemi, které je spojují. Můžeme si ji tedy představit jak neorientovaný ohodnocený graf, v němž navíc každý vrchol má daný počet pomerančů, které v něm rostou.

Napište program, který na vstupu dostane mapu města a najde trasu ze startu do cíle, během které co nejméněkrát projedeme ulicemi (tedy nás zajímá počet přejezdů a ne celková délka trasy). Během cesty můžete brát pomeranče z křižovatek. Nesmíte však překročit limit 10 pomerančů v nádrži. Křižovatky i ulice se mohou na trase opakovat.

Všechny sebrané pomeranče na křižovatce dorostou hned po jejím opuštění a dojetí na jinou křižovatku. Na začátku má motorka prázdnou nádrž, ale můžete ji naplnit pomeranči ze startovní křižovatky.

Formát vstupu: Na prvním řádku vstupu budou čísla N, M, S a C oddělená jednou mezerou, kde N je počet křižovatek ve městě, M počet ulic, S číslo startovní křižovatky a C číslo cílové křižovatky.

Na druhém řádku bude N mezerou oddělených čísel udávající počty pomerančů v jednotlivých křižovatkách. Na dalších M řádcích jsou popsány ulice, každá třemi čísly. První dvě udávají čísla křižovatek, mezi kterými ulice vede, a třetí udává délku ulice v metrech. Všechny ulice jsou obousměrné.

Pro hodnoty na vstupu dále platí:

• 1 ≤ N ≤ 30 000
• 1 ≤ M ≤ 1 000 000
• Křižovatky jsou číslované od 1 do N.
• Na každé křižovatce leží maximálně 10 pomerančů.
• Ulice jsou dlouhé minimálně 100 a maximálně 1 000 metrů. Délky jsou násobky 100.

Formát výstupu: Na výstup vypište jedno celé číslo udávající délku nejkratší cesty v počtu projetých ulic ze startu do cíle, na které vám nikdy nedojdou pomeranče v nádrži.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Řešení

28-1-2 Zapalování kostek (8 bodů)

Hrajeme následující hru. Máme postavenou pyramidu z dřevěných kostek o K patrech. To jest v prvním patře máme K kostek, na nich stojí K-1 kostek, na těch stojí K-2 kostek, až na špičce stojí jen jedna kostka.

Dva hráči se střídají v tazích. V jednom tahu hráč vybere jednu kostku v pyramidě a zapálí ji. To zapálí (obě) kostky, které na ní stojí, ty zas zapálí kostky, které stojí na nich a tak dále. Sousední kostky od aktuální nechytnou! Pak hraje druhý hráč. Vyhrává ten, kdo zapálí poslední kostku v pyramidě.

Pro dané K navrhněte vyhrávající strategii pro prvního hráče. To znamená takovou strategii, že ať druhý hráč dělá cokoliv, první vždy vyhraje.

Lehčí varianta (za 3 body): Popište konkrétní strategii pro K=4 a K=5.

Řešení

28-1-3 Bourání komínu I (12 bodů)

Na zahradě stojí V metrů vysoký komín, který chceme zbourat. K tomu máme k dispozici N bomb. Bomba i váží w_i kilogramů a zničí přesně d_i metrů komínu. Komín bouráme postupně odshora. Při boření vždy musíme vynést bombu až na vršek zbytku komínu a tam ji odpálit. Tím se komín sníží o d_i metrů (přitom nesmí vyjít záporná výška, nechceme skončit s jámou).

S nošením bomb se ale chceme co nejméně nadřít. Vynesení i-té bomby na komín vysoký x nás stojí x  · w_i jednotek energie. Navrhněte algoritmus, který naplánuje boření komínů tak, abychom celkem použili nejmenší možné množství energie.

Lehčí varianta (za 7 bodů): Řešte případ, kdy všechny bomby dohromady zničí přesně V metrů. Tedy víme, že je všechny musíme použít.

Řešení

28-1-4 Bourání komínu II (8 bodů)

Stejná úloha jako minulá, ale nyní ji řešte prakticky v CodExu. Stačí ovšem, když místo přesného postupu bourání budete vypisovat pouze minimální počet jednotek energie, kterou je nutno ke zbourání použít.

Formát vstupu: Na vstupu na prvním řádku dostanete dvě čísla V a N – výšku komínu a počet bomb. Na dalších N řádcích jsou vždy dvě čísla w_i a d_i udávající váhu a sílu bomby i. Dále platí:

• 1 ≤ V ≤ 10 000
• 1 ≤ N ≤ 10 000
• 1 ≤ w_i ≤ 100 000
• 1 ≤ d_i ≤ 10 000
• Pro několik prvních vstupů platí, že bomby dohromady zničí přesně V metrů.

Formát výstupu: Na výstup vypište jediné číslo udávající minimální námahu, se kterou je možno komín zbourat.

12 3
4 6
2 2
12 4

108

Nejdříve použijeme první bombu, stojí nás 12 ·4 = 48 jednotek energie, komín po ní bude mít výšku 6. Poté použijeme druhou, stát nás to bude 6 ·2 = 12, z komínu zbudou 4 metry. Nakonec třetí bombu, k použité energii přičteme 4 ·12 = 48, celkem jsme tedy využili 108 jednotek energie a z komínu nic nezbylo.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

„Ano, čtu to tady: Pán nahlásil zboření svého výstavního komínu. Podezřívá z toho svého souseda kvůli dlouhodobým sporům a protože ten jej údajně neprávem obviňuje z otrávení svého psa… Hmmm… Koukám, že jsme panu sousedovi poslali předvolání. Tak nebojte, ono se to brzy vyřeší. Ale teď zpět k vám. Jaké vy jste dneska dělal problémy?“

„Jel na motorce jako blázen, opětovně ignoroval výzvy hlídek k zastavení a po dopadení blekotal nějaké nesmysly o útěku. Možná je pod vlivem drog,“ odpovídá rázně muž z hlídky.

„Tak se na to podíváme. Dělej zase zápis,“ ukazuje na kolegu.

„Proč jste ignoroval všechny výzvy k zastavení?“

„J-já se p-p-potřeboval co-co nejrychleji d-dostat sem… a-abych n-nahlásil, c-co se stalo.“

„Pokračujte,“ vybízí policista s náznakem zvědavosti.

„V-víte, já měl vždycky h-hroznou smůlu n-na své sousedy. Už v první třídě jsem seděl v l-lavici vedle kluka, který mi k-kradl svačiny a tr-trhal o-oblečení. T-to bylo vždycky d-doma problémů, že každý t-týden roztrhnu tričko. J-já ni-nikdy nepřiznal, že to dělá on. J-jsem se b-bál na něj ž-žalovat.“

„Proboha mluvte k věci. Mě zajímá dnešek a ne váš podělanej život.“

„A-ale t-to b-byla na-naprostá pr-prkotina o-oproti tomu, c-co se stalo t-teď,“ pokračuji, jako bych policistu vůbec neslyšel.

Začalo to hned včera, jak jsem vyšel z policejní stanice. Silně pršelo, tak jsem rozevřel deštník a vyrazil. Ze stanice to mám do práce kousek, jen pár bloků. Šlo se mi těžce, protože v ulicích foukal silný vítr a zápasil jsem s rozevřeným deštníkem. Nakonec jsem jej musel naklonit před sebe, abych jím prorážel vzduch. Tím jsem si zablokoval výhled. PRÁSK! Někdo přímo přede mnou vystupoval z auta a já, nevidě před sebe, mu kovovou špičkou deštníku vyryl do dveří pořádnou rýhu.

„Ty šmejde! Tys mi zničil auto! Nemůžeš se doprdele dívat na cestu?“ ozvalo se.

Nadzvedávám deštník, abych viděl, s kým mám tu čest, a mohl se dotyčnému omluvit. Stál tam asi padesátiletý pohublejší muž s vyholenou hlavou, který byl aspoň o pět čísel vyšší než já. Byl to můj soused.

„Ty?! Ty se ještě odvažuješ plést se mi do cesty, po tom, cos mi otrávil psa? To mi teda zaplatíš! To ti jen tak nedaruju!“ pokračuje.

„Já??? Já nikoho neotrávil. A nic vám platit nebudu! Tohle byla vaše chyba. Máte se koukat, jestli tam nejsou lidi, když otevíráte dveře,“ bráním se a s úšklebkem dodávám, „kromě toho vás v dohledné době přijdou vyšetřovat kvůli tomu komínu, který mi v noci někdo zbořil.“

Soused zasupěl a odměřeným zastrašujícím tónem řekl: „Ty mě jako budeš žalovat?“

„Jestli budu? Právě jsem to udělal, protože tohle vám už dál trpět nebudu!“

Soused zrudl, prohlídl si mě očima a potichu supěl: „Tos přehnal chlapečku. Mě tady nikdo žalovat nebude. Rozumíš? Nikdo! A už vůbec ne ty! …Ty o mě ještě uslyšíš.“

Najednou začal křičet: „TY JEŠTĚ POZNÁŠ, CO JÁ DOKÁŽU A NEBUDE SE TI TO LÍBIT! NA TO SE MŮŽEŠ SPOLEHNOUT!“

Přešel chodník, ukázal směrem ke mně výhružné gesto, agresivně trhl dveřmi a zmizel ve vedlejší budově.

Nevyděsilo mě to. Naopak mi to zvedlo náladu a s pocitem zadostiučinění jsem pokračoval v cestě do práce. Konečně dosáhnu spravedlnosti! V duchu jsem si představoval policejní důstojníky klepající na dveře souseda a jak mi přímo on dává do ruky peníze za způsobenou škodu. Nebo ještě líp, dostává příkaz k vystěhování.

S takto dobrou náladou jsem došel do práce – dokonce přestalo i pršet. To jsem ale ještě netušil, co mě později v ten den čeká…

* * *

Z práce jdu rovnou domů. Po průchodu brankou se ještě jednou smutně podívám na hromádku cihel, která mi zbyla po komínu. On to totiž nebyl jen tak obyčejný komín. Byl to umělecky navržený výstavní komín, který jsme vlastnili už po dvě generace a ke kterému se pojí nejedna vzpomínka. Například když do něj můj mladší bratr zapadl při hře na schovávanou a přes dvě hodiny jsme jej nemohli najít. Nebo méně veselá historka: jak se nám z něj šířila plíseň do vedlejších záhonů a museli jsme se jí celý víkend zbavovat různými chemikáliemi.

28-1-5 Likvidace plísně (10 bodů)

Na zahradě nám vyrostlo N hromádek mnohavrstvé plísně. Té bychom se chtěli co nejrychleji zbavit. K tomu máme plošný postřikovač naplněný přípravkem proti plísním. V jednom kroku můžeme buď použít postřikovač a zničit tak jednu vrstvu plísně z každé hromádky, nebo vzít několik vrstev z jedné hromádky a dát je na jinou (klidně i novou) hromádku. Hromádek takto můžeme vytvořit kolik chceme.

Napište program, který spočítá, v kolika nejméně krocích je možné se zbavit celé plísně.

Formát vstupu: Na prvním řádku vstupu dostanete číslo N udávající celkový počet hromádek plísně. Na druhém řádku dostanete čísla v₁, …, v_N udávající počet vrstev na jednotlivých hromádkách.

• 1 ≤ N ≤ 10 000
• 1 ≤ v_i ≤ 10 000

Formát výstupu: Na výstup vypište jedno celé číslo udávající minimální počet kroků, v jakém je možné se plísně zbavit.

Příklad: Máme-li tři hromádky o počtech 9, 3 a 3, je nejlepší nejdříve dvěma přesuny z první hromádky vyrobit tři po třech plísních, a pak všech pět třemi postřiky vyhubit.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Řešení

28-1-6 Úloha z ovladače (12 bodů)

Držíte v ruce ovladač, na jehož displeji se postupně objevují čísla. Jakmile displej zasvítí zeleně, musíte zadat nejmenší z posledních K čísel, které jste viděli. Toto číslo K je pevně dané.

Navrhněte datovou strukturu, která bude umět efektivně zpracovávat následující dvě operace: přidání prvku a vypsání nejmenšího z posledních K přidaných prvků.

Plný počet bodů můžete získat za řešení, které potřebuje průměrně konstantní čas na dotaz. Tedy některé operace struktury můžou být pomalejší, ale posloupnost D operací zabere čas O(D). Bonusové body můžete získat za řešení, které potřebuje konstantní čas na každý jeden dotaz.

Řešení

28-1-7 Vyříznutý kus mříže (10 bodů)

Ve čtvercové mřížce je nakreslený mnohoúhelník s N vrcholy, které jsou umístěny přesně v mřížových bodech. Navrhněte algoritmus, který na vstupu dostane souřadnice bodů mnohoúhelníka (v pořadí na obvodu) a spočítá, kolika mřížovými body prochází jeho strany.

Řešení

28-1-8 Programování podle Darwina (15 bodů)

V letošním seriálu se budeme věnovat přírodou inspirovaným algoritmům, jakými jsou například evoluční algoritmy či neuronové sítě. Téma je velmi široké a obsahuje v sobě velkou spoustu postupů, ze kterých my se budeme věnovat jen těm základním a často používaným.

Úvod do evolučních algoritmů

Nabízí se tedy otázky: „Mohly by nám tyto techniky nějak pomoci při řešení těžkých algoritmických problémů?“, „Dají se jednoduše popsat, nebo dokonce naprogramovat?“, „Dokážeme naprogramovat mravence, kteří by společně namísto stavění mraveniště hledali cestu v grafu?“, „Může se i počítač pomocí simulace neuronů něco naučit?“ a tak dále. Ukazuje se, že odpovědí na většinu těchto otázek je: „Ano, je to možné!“

To všechno vypadá skvěle! Ale možná si teď někteří z vás pro sebe řekli: „Budu já tomu rozumět? Já biologii moc neumím.“ Tak toho se přesně nemusíte bát. Všechny algoritmy, kterým se během seriálu budeme věnovat, se přírodou pouze inspirují. To znamená, že sledují nějaké její základní chování, a pak si jej vysvětlí svým informatickým způsobem. Tedy prakticky žádné biologické znalosti nejsou potřeba.

Evoluční algoritmy – část 1

Prvních několik dílů seriálu se budeme věnovat evolučním algoritmům. V tomto díle si konkrétně popíšeme a naučíme se používat vůbec první typ: takzvaný genetický algoritmus. Řekneme si, čím je motivován, podrobně popíšeme jeho hlavní části a pokusíme se pomocí něj vyřešit pár problémů. Do otázek ohledně toho, proč by takový algoritmus vůbec měl mít šanci fungovat, zatím nebudeme příliš zabíhat – ty si necháme na příště.

S genetickým algoritmem poprvé přišel John Holland v roce 1970. Genetický algoritmus je inspirován myšlenkou evoluce. V přírodě platí pravidlo „silnější přežijí,“ což znamená, že nejsilnější jedinci obstojí v konkurenci ostatních, reprodukují se a zvládnou tak přenést své geny do dalších generací. Tím v každé další generaci dostáváme lepší jedince, protože nám zůstanou geny jen těch, kteří dokázali přežít.

Dále budeme předpokládat, že výkonost jedince ovlivňují pouze jeho geny a nic jiného (tomu se v biologii říká darwinismus). Tento předpoklad znamená, že při reprodukci jsou potomci a jejich vlastnosti závislí pouze na genech rodičů a ne na jejich životních zkušenostech. Nyní se pojďme podívat, jak vypadá nějaký informatický genetický algoritmus.

Genetický algoritmus sestává z populace jedinců, funkce ohodnocující výkonost těchto jedinců (fitness funkce) a tří hlavních genetických operátorů pro manipulaci s jedinci: selekce, křížení a mutace. V dalším textu si tyto jednotlivé části podrobněji popíšeme.

Jedinec je tvořen posloupností genů, která představuje nějaké řešení našeho problému. Je důležité, aby tato posloupnost měla danou fixní délku. Zatím navíc budeme předpokládat, že tato posloupnost je binární (skládá se pouze z 0 a 1). Pro binární soustavu dokážeme jednoduše popsat další operátory.

Fitness funkce ohodnocuje výkonost (kvalitu) jednotlivých jedinců. Jinými slovy říká, jak jsou jedinci dobří pro řešení našeho problému. Zpravidla vyhodnocuje tak, že vyzkouší, jak dobře genetický kód jedince řeší zadaný problém a ohodnotí jej reálným číslem.

Selekce

Pomocí selekce vybíráme, které jedince použijeme pro vytvoření další populace. Bereme přitom v úvahu fitness jedinců, ale zároveň ponecháváme i určitou míru náhody. My si uvedeme dva druhy selekcí: ruletovou selekci a turnajovou selekci.

Ruletovou selekci si představíme jako opravdovou ruletu. Máme kruh rozsekaný na různě velké části, kde každá odpovídá jednomu jedinci. Velikost části kruhu je přímo úměrná fitness jedince. Do rulety pak hodíme kuličku a vybereme toho jedince, v jehož části kulička skončí. Tento proces opakujeme tolikrát, kolik jedinců potřebujeme vybrat. Nevadí nám, pokud jednoho jedince vybereme vícekrát (V přírodě by to sice nešlo, ale my si to v informatice klidně můžeme dovolit a jednoho jedince si nakopírovat, kolikrát chceme.).

V praxi je ruletová selekce počítána tak, že se vygeneruje náhodné číslo od 1 do součtu všech fitness a podle toho se vybere příslušný jedinec. Z toho důvodu je pro ruletovou selekci nutné, aby fitness funkce byla vždy kladná.

Pak ale existuje ještě turnajová selekce, u které hodnoty fitness funkce mohou být libovolné. Ta funguje tak, že vezme dva náhodné jedince a z nich vybere toho s lepší fitness. To opět zopakuje tolikrát, kolik chceme vybrat jedinců. (Turnajová selekce nemusí vždy vybírat jen lepšího ze dvou jedinců, ale klidně obecně nejlepšího z k jedinců.)

Křížení

Křížení je jedním z nejdůležitějších genetických operátorů. To vezme dva jedince a nějakým způsobem je zkombinuje. Nejčastěji se používá takzvané jednobodové křížení, které vybere náhodný bod, tam jedince rozpůlí a prohodí jejich druhé části. Obdobně také funguje dvoubodové křížení, které náhodně zvolí dva body a pak prohodí tu část jedinců, která je mezi nimi.

Také se může použít křížení, které se pro každý bit zvlášť rozhodne, zda jej prohodí nebo ne. Takové křížení se ale pro některé problémy moc nepoužívá. Později si sami můžete vyzkoušet, které z křížení vám bude fungovat lépe.

Křížení se neaplikuje na všech jedincích, ale probíhá s pravděpodobností p_k, která se obvykle pohybuje od 0,7 do 0,9. Křížení se často považuje za hlavní pohon genetických algoritmů. Na druhou stranu existuje mnoho verzí a odvození, které křížení vůbec nezahrnují.

Mutace

Mutace je operátor, který náhodně změní jednoho jedince. To jest každý bit s nějakou malou pravděpodobností změní. Tato pravděpodobnost je často volena kolem 1/d, kde d je délka jedince. Taková volba pravděpodobnosti způsobí, že během mutace v průměru prohodíme právě jeden bit jedince. Mutace se na jedince aplikuje s pravděpodobností p_m, která se obvykle volí v rozmezí 0,001 až 0,05.

Poslední pojem, který si definujeme, je generace. Generací je myšlena populace, která existuje v jedné iteraci. Na začátku máme generaci 0, z té je pak pomocí selekce, křížení a mutace vytvořena generace 1, z té pak generace 2 a tak dále. Předchozí generace vždy celá umírá a dále se používá pouze nová generace.

Pseudokód algoritmu

Nyní jsme si představili všechny důležité části genetického algoritmu, tak se pojďme podívat, jak dohromady fungují. Zde je pseudokód algoritmu.

1. Vygeneruj náhodných n jedinců velikosti d do generace 0 a spočítej jejich fitness.
2. t = 0
3. Opakuj následující:
4. Pomocí selekce vyber m jedinců z generace t.
5. Na každého z těchto m jedinců aplikuj křížení s pravděpodobností p_k.
6. Na každého dále aplikuj mutaci s pravděpodobností p_m.
7. Spočítej fitness výsledných jedinců a nejlepších n prohlaš za generaci t + 1.
8. t = t + 1

Jelikož využíváme náhodu, vyplatí se algoritmus pustit několikrát za sebou a ze všech běhů vzít ten nejlepší výsledek. Při každém běhu začínáme s jinak nagenerovanou počáteční populací, a tedy můžeme získat i jinak dobré řešení.

A to je celé. Poslední, co zbývá říct, je, kdy se algoritmus zastaví. To může být buď ve chvíli, kdy vyvineme jedince reprezentujícího optimální řešení problému (tj. s maximální možnou fitness, pokud ji známe) nebo po určitém počtu iterací. Často se také zohledňuje počet vyhodnocení fitness funkce, protože právě ta bývá tou časově nejnáročnější částí algoritmu. Ta se ale v našem případě pustí v každé iteraci právě m-krát, takže výpočet budeme řídit počtem iterací a velikostí populace. (m ≥ n, ale často m = n)

Elitismus

Než si algoritmus vyzkoušíme, zmíníme ještě poslední věc. V algoritmu, tak jak jsme jej popsali, se lehce může stát, že během přesunu na další generaci přijdeme o nejlepšího jedince – můžeme jej nevybrat, může se špatně zkřížit a může zmutovat. Z tohoto důvodu se do algoritmu přidává ještě další vlastnost, která se jmenuje elitismus. Ta funguje tak, že do výběru pro generaci t + 1 přidáme ještě p_e  · n nejlepších jedinců z generace t. Tím určitě zachováme doposud nejlepší geny. Hodnota p_e se obvykle volí maximálně 0,1. Nemůžeme brát moc velkou část, protože pak by nám celá populace postupně konvergovala jen k jednomu aktuálně nejlepšímu jedinci.

Nyní si algoritmus pojďme vyzkoušet. Protože genetické algoritmy obsahují mnoho parametrů, které se musí správně nastavit, aby dobře fungovaly, ladí se nejdříve na jednoduchých problémech. Na takových, na kterých je dobře vidět, jak algoritmus funguje, a pro které umíme efektivně vyhodnocovat fitness funkci. My se pokusíme navrhnout genetický algoritmus, který se bude snažit vyvinout posloupnost samých jedniček.

Pro takový problém je fitness funkce jednoduchá – prostě jen spočítá, kolik jedniček jedinec obsahuje. Selekce, křížení a mutace fungují přesně tak, jak je popsáno výše. Zbývá vyladit parametry: velikost populace n, počet iterací t a hodnoty p_k, p_m, p_e. Vaším úkolem teď bude si různé kombinace těchto parametrů vyzkoušet a zjistit, jak se algoritmus chová.

Úkol 1 [6b]

Pomocí genetického algoritmu vyviňte posloupnost samých jedniček. Tedy začněte s populací náhodných jedinců a pomocí genetického algoritmu se snažte vyvinout jedince, který je složen pouze z jedniček.

Vyzkoušejte to pro velikosti jedince d = 20, 100, 500. Zkuste různé velikosti populace a různé kombinace pravděpodobností. Jak se algoritmus chová?

Sledujte, jak se během výpočtu mění maximální a průměrná fitness generací.

Vyzkoušejte si také napsat nějaký vlastní způsob křížení nebo mutace. Jak to bylo úspěšné? Tato křížení a mutace by neměly nijak záviset na znalosti řešeného problému. Cílem je odladit operátory, které by pak mohly fungovat i pro jiné, už ne tak jednoduché problémy.

Vyzkoušejte také, jak je algoritmus úspěšný, pokud má vyvinout jedince, kde se 0 a 1 střídají. (Přičemž je jedno, čím se začne.) Mělo by stačit změnit fitness funkci. Funguje váš algoritmus stále stejně dobře?

Během řešení můžete použít naše šablony genetického algoritmu ze stránky k evolučnímu seriálu.

Odevzdávejte soubor typu zip s popisem řešení, průběhem algoritmu a pokud chcete, tak i se zdrojovým kódem. V popisu rozeberte, co jste zkoušeli a jaké jste použili parametry, aby algoritmus byl co nejlepší.

Průběhem algoritmu je myšlen textový soubor, kde na každém řádku budou mezerou či tabulátorem oddělené hodnoty: číslo generace, hodnota průměrné fitness, hodnota maximální fitness. Nemusíte logovat každou generaci, stačí každá desátá.

Tím jsme si vyzkoušeli, jak se genetický algoritmus ladí na jednoduchém problému. Často při vymýšlení nového operátoru či dokonce celého algoritmu se hodí jej nejdříve vyzkoušet a odladit na něčem takto jednoduchém. To se především týká operátorů, které jsou nezávislé na řešeném problému. O takové operátory se snažíme, protože je pak můžeme aplikovat i na složitější problémy.

Někdy ale můžeme znalost řešeného problému využít a přímo ji zahrnout do genetických operátorů, jako jsou křížení nebo mutace. To na jednu stranu může značně urychlit výpočet, na druhou stranu nás to ale může v řešení zahnat někam do suboptimálního řešení, ze kterého se nebudeme moci dostat.

To vše si vyzkoušíme na problému sedmi loupežníků. Skupinka sedmi loupežníků vyloupila vesnici a získala z ní dohromady d předmětů, každý z nich ohodnotila nějakou cenou. Vaším úkolem je tyto předměty rozdělit na 7 hromádek tak, aby jejich součet byl co nejbližší. Konkrétně tak, aby rozdíl nejhodnotnější a nejméně hodnotné hromádky byl co nejmenší.

Než se pustíme do řešení, musíme vyřešit několik problémů: Jak budeme kódovat jedince? Jak v tomto kódování bude fungovat křížení a mutace? Jak zvolit fitness funkci?

Jedinci budou délky d a budeme je kódovat čísly 0, 1, …, 6. Pokud na i-té pozici máme číslo 4, tak to znamená, že i-tý předmět přidělíme do hromádky 4. Křížení může fungovat stejně jako s binárními jedinci a mutace změní číslo na náhodnou hodnotu od 0 do 6 namísto překlopení bitu. To, jak dobře tyto operátory budou fungovat, je jiná otázka.

A co s fitness funkcí? V tomto případě máme za úkol minimalizovat rozdíl největší a nejmenší hromádky. Náš genetický algoritmus se ale snaží fitness funkci f maximalizovat a ne minimalizovat.

U turnajové selekce problém můžeme vyřešit jednoduše – prostě použijeme hodnoty -f(x) namísto f(x). Co ale dělat, pokud chceme použít ruletovou selekci? Tam všechny fitness navíc musí být kladná čísla. Máme několik možností, jak toho dosáhnout. Často se používá hodnota 1/(f(x) + 1) namísto f(x). Nebo hodnota A - f(x) pro vhodně zvolené A tak, že výsledné hodnoty určitě budou kladné. Musíme ale dát pozor, aby A nebylo příliš velké, protože pak by výsledné hodnoty byly příliš blízko u sebe a z pohledu ruletové selekce byly „skoro stejné“.

Tím jsme si poradili se všemi problémy a tedy genetický algoritmus můžeme zkusit použít.

Úkol 2 [9b]

Pomocí genetického algoritmu řešte problém sedmi loupežníků pro data, která naleznete na stránce se šablonami. Data jsme vygenerovali troje: lehká, střední a těžká. Doporučujeme je řešit postupně. Tj. až si budete myslet, že máte dost dobré řešení pro lehká data, zkuste, jak vám algoritmus funguje pro střední, atd.

Na prvním řádku dat jsou dvě celá čísla: počet loupežníků (vždy 7) a počet nakradených věcí D. Na druhém řádku je D mezerou oddělených čísel udávajících váhy jednotlivých věcí.

Opět zkoušejte různé kombinace parametrů. Také si vyzkoušejte, jak nejlépe převést fitness funkci na maximalizační – můžete vymyslet i vlastní způsob nebo nějaké modifikace způsobů popsaných výše.

Nalezněte co nejlepší řešení daného problému. Můžete použít i vlastní genetické operátory, které libovolně využívají znalost problému a provádějí křížení nebo mutace „cíleně“ na specifických částech jedinců.

V zipu odevzdejte nejlepší vyvinuté řešení společně s popisem, jak jste jej dosáhli a proč si myslíte, že takový postup funguje. Také můžete přidat záznam průběhu řešení (jako v minulé úloze).

Při řešení obou úloh můžete upravit námi vytvořenou šablonu v jazycích C++, Java, …, anebo použít svou vlastní.

Naše kódy obsahují základní verzi genetického algoritmu se všemi jeho částmi. Navíc logují, jak se během výpočtu mění průměrná a maximální fitness, a ukládají doposud nejlepšího vyvinutého jedince.

Karel Tesař

Řešení