Úloha 6.u3: Klávesnice podruhé (4 b)

Zadáno v čísle 22.6.

Řešeno v čísle 22.8.

Zadání

Vzpomínáte si, jak se tehdy rozbila klávesnice vašeho notebooku? Museli jste použít softwarovou klávesnici v podobě obdélníkové tabulky znaků, na které jste psali pomocí kurzoru, kterým jste pohybovali šipkami (spolu s Enterem jediné funkční klávesy) (viz Úloha 4 v čísle 22.41). Klávesnice byla tenkrát tak hloupě navržená, že jste psaním strávili dlouhé hodiny. Zkušenost to byla natolik traumatizující, že jste se rozhodli navrhnout si vlastní klávesnici, na které půjde psát i dlouhé texty rychle.

Chcete tedy navrhnout klávesnici o rozměru $8\times 8$ znaků tak, aby nejmenší nutný počet stisků šipek a Enteru k napsání zadaného textu2 byl co nejmenší. Klávesnice rozlišuje velká a malá písmena (tedy L a l jsou dva různé znaky), mezera a interpunkční znaménka (tečka, čárka, vykřičník, otazník) jsou také plnohodnotné znaky, odřádkování ignorujte (tj. chovejte se k textu jako by byl napsaný celý na jedné řádce). Počet bodů, které za řešení obdržíte, se bude odvíjet od toho, kolik je třeba stisků kláves k napsání textu na vaší klávesnici (čím méně, tím lépe). Dále můžete dostat až dva body za vysvětlení toho, jak jste vaši klávesnici vytvořili.


1) Do úlohy se nám bohužel vloudila chyba, neboť slovo ahoj v příkladu lze napsat na osm stisků, ne na pět. Všem se moc omlouváme za zmatení.

2) Text je k dispozici na následující adrese: https://mam.mff.cuni.cz/media/prilohy/22-6-3-klavesnice_vstupni-text.txt

Řešení

Tato úloha na první pohled nepůjde v rozumném čase vyřešit dokonale. V textu je celkem 45 různých znaků, tabulka má 64 polí, máme tedy $45^{64} \doteq 6,39 \cdot 10^{105}$ možností, jak ji sestavit. Všechny je vyzkoušet nezvládneme (při velmi optimistické rychlosti zkoušení 3000 tabulek za sekundu by program na jednom počítači běžel přes $10^{93}$ let), budeme proto prostor všech tabulek prohledávat nějakou nekompletní metodou a spokojíme se s řešením, které bude dostatečně dobré. (Jak poznáme dostatečně dobré řešení? Hodí se třeba srovnání s výsledky ostatních řešitelů. K této úloze bohužel průběžně aktualizovaná výsledková listina k dispozici nebyla. Snad příště.)

Jedna možnost, jak úlohu řešit, je zvolit si nějakou tabulku $k$ a vyzkoušet všechny tabulky ve vzdálenosti 1 od $k$. Řekneme například, že dvě tabulky jsou ve vzdálenosti $n$, pokud se liší právě na $n$ pozicích. Také bychom mohli uvažovat třeba počet prohození dvou pozic, kterými je možno změnit jednu tabulku na druhou, nebo kombinaci těchto operací. Do dalšího kroku pak vybereme jako $k$ tu tabulku, pro kterou je hodnota optimalizované funkce $f$ (v našem případě počet stisků kláves nutný pro napsání daného textu) nejlepší. To opakujeme, dokud se nedostaneme do stavu, kdy jsou všechny sousední nenavštívené tabulky horší než $k$. Této metodě se říká hillclimbing. Proč, to je nejlépe vidět při maximalizaci funkce definované na dvourozměrném prostoru (rovině). Tehdy její graf vytváří krajinu s pohořími, na které naše $k$ šplhá (nebo spíš $f(k)$; $k$ se pohybuje stále v původní rovině). Když dojde na vrchol, nemá kam jít dál. A tady se ukazuje největší slabina této metody – co když jsme vylezli na kopec, který není nejvyšší? Našli jsme pouze lokální optimum a už jej nedokážeme opustit.

Doc. Jan Pokorný používal podobnou metodu, nazývanou stochastický hillclimbing. Místo prozkoumávání všech okolních tabulek si vždy vybral jednu náhodně (a přesunul se na ni jen pokud byla lepší než stávající tabulka). Je vidět, že změna neodstraní problém s lokálními optimy, s trochou štěstí však může urychlit výpočet a jednodušeji se programuje.

Jak se z lokálního optima dostat? Asi nejjednodušší způsob je zapamatovat si aktuální nejlepší nalezenou tabulku a spustit výpočet znovu s jinou náhodnou počáteční tabulkou. Tím ale zbytečně ztrácíme „nastoupané metry“ – možná skočíme z druhého nejvyššího vrcholu Krkonoš někam do Polabí.

Oblíbená metoda nazývaná simulované žíhání je inspirována postupem zpracování kovů, při kterém se materiál nejprve zahřeje na vysokou („žíhací“) teplotu a následně se nechá zchladnout. Při vysoké teplotě mají atomy vyšší energii, snáze se přeskupují, kov je měkký. Během chladnutí pak postupně utvářejí krystalickou mřížku, která může být pravidelnější a pevnější než původní. Simulované žíhání je podobné stochastickému hillclimbingu, pouze s určitou pravděpodobností $P$ přijmeme novou tabulku do dalšího kroku, i pokud je horší než stávající. Díky tomu máme šanci přelézat nízké kopečky a dostat se až k horám. Pravděpodobnost $P$ bude klesat s klesajícím parametrem $T$ (teplotou). Pro stávající klávesnici $k$ a náhodně vybranou sousední $k’$ je pravděpodobnost přechodu z $k$ na $k’$ za teploty $T$

\[ P(k, k’, T) = \begin{cases} 1& \mathrm{pokud}\, f(k) > f(k’),\\ \exp \left({f(k) - f(k’) \over T}\right)& \text {jinak.} \end{cases} \]

Teplota $T$ by měla v průběhu výpočtu klesat z nějaké hodně vysoké hodnoty až k 0, například ji můžeme v každém kroku vynásobit $0,95$.

Ale šedivá je teorie. Když porovnáme průběh optimalizace pomocí stochastického hillclimbingu a simulovaného žíhání (Obrázek 1), zjistíme, že se stochastický hillclimbing do mělkých lokálních optim nedostává a simulované žíhání za vysoké teploty jen zbytečně ztrácí čas. Na tuto úlohu se tedy asi příliš nehodí.

Obrázek 1: Porovnání průběhu optimalizace. Dvacetkrát jsme vygenerovali počáteční tabulku a na ni pokaždé postupně spustili obě metody. Zobrazena je průměrná hodnota $f$ po určitém počtu kroků.

Vidět graf optimalizované funkce v průběhu výpočtu je často užitečné. Můžeme tak o výpočtu získat lepší představu a například zjistit, jestli má cenu pouštět jej s delším časovým limitem či s jinými parametry.

A konečně na obrázku 2 jsou konkrétní zkonstruované klávesnice. Dosažené skóre 68762 odpovídá přibližně $2,94$ stiskům na napsání jednoho znaku, což je pravděpodobně dost blízko globálního optima.

          WODhvMFH            wAUMEyOH            HOnjhPCD
          yj si IU            IvroCbLA            J.Sabu m
          LuenleuA            f tcidaW            T edpro.
          qtamortd            nea n.hP            LoluitcI
          gisrcasp            glisur j            Vres eng
          S~elne N            bupmteST            FfqvmauN
          Tft uiCQ            JqvN dVF            RQui.l E
          RwPb.VEJ            csQaloDR            WngwUAMy
Obrázek 2: Zkonstruované klávesnice. Zleva skóre 79257 (Doc. Petr Šimůnek, ručně), 69902 (Doc. Jan Pokorný, stochastický hillclimbing) a 68762 (simulované žíhání; program v jazyce Python, kterým jsme klávesnici našli, si můžete stáhnout z adresy https://mam.mff.cuni.cz/media/prilohy/22-6-3-klavesnice_program.py).

Existuje mnoho dalších metod, kterými se podobné úlohy dají řešit, zmiňme například oblíbené evoluční algoritmy či particle swarm optimization. Žádná metoda však není univerzální1, a tak je optimalizace většinou provázena experimentováním a laděním konstant.

Matěj


1) O tom pojednává tzv. „No free lunch“ theorem: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization