Zadanie

Po týždni strávenom lozením po horách sa Katka vrátila naspäť do civilizovaného sveta a do svojho biologického labáku. Dušu jej ale ťažilo trápenie.

Jej obľúbený plyšový hroch bol teraz vážne chorý a hrozilo to najhoršie. Hory a chlad mu proste nespravili dobre. Dlhé noci sa oňho musela starať a uplatňovať všetky svoje poznatky z imunológie, mikrobiológie, analýzy, fyziológie a iných okultných náuk.

Nakoniec ale všetko dobre dopadlo. Hroch to prežil. Kaťa si ale povedala, že niečo takéto už nikdy nechce zažiť znova a teda, že hrocha už so sebou nebude na takéto túry nosiť. To by tam ale musela chodiť sama a to sa jej nechce. Rozhodla sa teda, že si ako správna biologička vyšľachtí niekoľko silných, alergiám, malátnosti, a kazom odolných vtákopyskov.

To ale nie je sranda. Také šľachtenie je mimoriadne komplikovaná vec a ani Kaťa jej úplne nerozumie. Jediné, čo teda môže robiť, je zobrať niekoľko génov, zlepiť ich za seba a dúfať, že jej vznikne vtákopysk so chcenými vlastnosťami. Aby otestovala jeho odolnosť, pošle ho na bakalársky seminár. Čím dlhšie tam vydrží, tým je odolnejší. Takto si Katka mieša a testuje už niekoľko mesiacov. Pomôžte jej tento proces trochu zautomatizovať.

Úloha

Vašou úlohou je napísať program, ktorý bude schopný vytvoriť čo najodolnejšieho vtákopyska. Na výrobu vtákopyska potrebujeme \(50\) génov (tak málo to je, lebo je plyšový). Gény sú písmená A, C, G a T.

Dokopy máte \(n=100\,000\) pokusov na ukuchtenie toho najodolnejšieho stvorenia aké kedy tento seminár videl (a to teda naozaj nie je ľahká úloha). Po každom pokuse sa dozviete, ako veľmi bolo vaše stvorenie odolné. Kto vytvorí najodolnejšieho vtákopyska vyhrá. Samozrejme je tu aj istý časový limit.

Bodovanie

Zo všetkých (najviac \(100\,000\)) vašich pokusov jedného odovzdaného programu sa vyberie najodolnejší vtákopysk. Čím bude tento vtákopysk odolnejší, tým viac bodov za program dostanete. 1

Skoro určite sa vám nepodarí vytvoriť vtákopyska, ktorý na bakalárskom seminári vydrží viac ako 85 dní (pochybujeme, že taký vôbec môže existovať). Pokiaľ váš vtákopysk vydrží \(80\) alebo viac dní, dostanete plný počet bodov. Za \(67\) a viac dní dostanete aspoň \(10\) bodov, za \(53\) a viac dní aspoň \(5\) bodov. Ak váš vtákopysk nevydrží ani \(10\) dní nedostanete žiadne body, iba by ste Kaťu zbytočne rozosmútili. Dostať môžete ľubovoľný celočíselný počet bodov od \(0\) po \(15\), veď odovzdajte nejaké riešenie a uvidíte.

Poznámka

Možno ste si všimli, že nikde nie je napísané, čo tá odolnosť vlastne znamená. No, svet je tajomné a komplikované miesto a naozaj nikto netuší, čo treba mať na zvládnutie bakalárskeho semináru. Odporúčame vám si pri testovaní vymyslieť si nejakú vlastnú funkciu a zistiť, ako na nej vaša metóda kuchtenia funguje.

Dobré je robiť veľa testov na vlasntnom počítači, nie všetko čo naprogramujete hneď odovzdávať.

Formát vstup a výstupu

V tejto úlohe budete komunikovať s naším programom (krutý svet príkorí). Jednoducho na (štandardný) výstup vypíšte reťazec \(50\) znakov z ACGT končiaci znakom nového riadku a na vstup dostanete jedno celé číslo predstavujúce odolnosť vášho výtvoru. Toto môžete opakovať až \(100\,000\) krát, ak sa pokúsite spýtať viac otázok, váš pokus bude považovaný za neplatný.

Ak nechcete využiť všetky pokusy, musíte namiesto reťazca znakov vypísať znak K (ako koniec).

Ak chcete dostať odpoveď, je nutné po každom vypísaní génov výstup presunúť z pamäte na štandardný výstup pomocou príkazu fflush(stdout); v C++, alebo flush(output); v Pascale.

Príklad

Komunikácia medzi vašim a našim programom by mohla vyzerať napríklad nasledovne:

Váš program vypisuje: Testovač vypisuje:
AAAAAA..ďalších 40 znakov..AAAA 30
ACGTAC..ďalších 40 znakov..ACGT 58
CCCCCC..ďalších 40 znakov..CCCC 42
K

Najlepší vtákopysk prežil 58 dní. Riešenie by dostalo 6 bodov.


  1. Jednotlivé programy sa však naďalej hodnotia nezávisle a ráta sa len posledný odovzdaný program. Upozorňujeme vás, aby ste v tejto úlohe neodovzdávali príliš veľa programov, napríklad takých 200 už je veľa ale 10 až 30 je úplne v poriadku. Pokiaľ budete odovzdávať priveľa programov, môžeme sa rozhodnúť ohodnotiť iný ako posledný program.

Na začiatok

Toto vzorové riešenie nebude také, na aké ste možno zvyknutí. Dôvod je, že táto úloha vzorové riešenie ako také nemá a nemôže mať. Samozrejme, určite existuje zvieratko, ktoré má najväčšiu odolnosť, ale všeobecný, zaručený a rýchly spôsob jeho hľadania neexistuje. Prečo? Lebo inak by sme vedeli jednoducho riešiť ľubovoľný informatický problém.

Celá táto úloha bol taký experiment s vami. Úloha skúmala, ako sa dokážete vysporiadať s neznámym problémom. Možných prístupov je mnoho a do vzorového riešenia sa všetky nezmestia. Ukážeme si teda niekoľko techník a niekoľko prístupov k úlohe.

Lacný bod

Napíšeme program, ktorý skúsi zvieratká, ktoré ponúka ukážkový vstup. Pár riadkov kódu a máme dva body ani nevieme ako. Ale aspoň sme sa presvedčili, že rozumieme ako má fungovať vypisovanie výstupu.

Náhodné tipovanie

Čo tak predchádzajúci prístup zlepšiť, a pýtať sa aj na ďalšie možné zvieratká. Budeme veselo generovať náhodné stringy a posielať ich do sveta. A máme tri body, s trochou šťastia štyri.

Lozenie hore kopcom

Ako rozprávka napovedá, ideme si zaloziť po kopcoch a použijeme metódu zvanú hill-climbing. Predstavme si, že sme v neznámom teréne uprostred tmy a chceme vyliezť na kopec. Môžeme spraviť jeden krok náhodným smerom a overiť, či sme takto išli hore kopcom. Ak sa nám nepodarilo ísť hore kopcom, tak sa vrátime a skúsime ísť iným smerom. Opakovaním tohto postupu sa dostaneme na vrchol nejakého kopca, odkiaľ už nebudeme môcť ísť vyššie.

Problém tohto postupu je, že keby sme to skúšali v Tatrách, tak pravdepodobne ostaneme zaseknutí na nejakom veľkom kameni v údolí a na Gerlachovský štít sa zrejme nedostaneme. Tento postup totiž nájde len takzvané lokálne maximum (bod, ktorý je vyšší od všetkých okolitých) a nie globálne maximum (najvyšší bod celkovo). Môžeme však skúsiť šťastie a začať naše putovanie z 200 náhodných miest a z každého spraviť 500 krokov smerom hore.

V reči DNA začneme vždy z nejakého náhodného DNA reťazca a budeme opakovane meniť jedno náhodné písmeno na iné. Zistíme, či vtákopysk so zmeneným jedným písmenom vydržal dlhšie a ak áno, necháme si ho. Inak zmenu zahodíme a skúsime spraviť inú náhodnú zmenu. Môžme tiež skúsiť aj iné typy zmien, napríklad vymieňať dve písmenka, meniť písmenko na náhodnej pozícií, kopírovať náhodné kusy zvieratka na iné miesto, čo nás len napadne. Vo všeobecnosti sa ale odporúča skúsiť naraz viac podobných zmien a potom vybrať tú najlepšiu. Ak sa napríklad rozhodneme, že budeme meniť druhý gén, tak skúsime všetky možnosti a tú najlepšiu si necháme.

V závislosti od konkrétnej implementácie získame pravdepodobne 5 až 8 bodov.

Takmer simulované žíhanie

Toto je postup podobný lozeniu do kopca. Líši sa v tom, že dovolíme robiť aj zmeny k horšiemu. Navyše v žíhaní vystupuje aj parameter teplota, ktorý ovplyvňuje správanie algoritmu.

V každom kroku zoberieme aktuálny reťazec a spravíme v ňom nejaké drobné zmeny (počet zmien zvykne závisieť od teploty). Následne zistíme, či nový reťazec má lepšie skóre (t.j. odolnosť zodpovedajúceho vtákopyska) ako predošlý a ak áno, necháme si nový reťazec. Ak nie, tak sa náhodne rozhodneme, či si necháme nový alebo starý reťazec. Pravdepodobnosť toho, že si aj pri neúspechu necháme nový reťazec, závisí od teploty.

Potom existuje viacero prístupov ako meniť teplotu, môžeme začať s vysokou a vždy, keď sa nám podarí spraviť dobrú zmenu, tak ju trocha znížime (prenásobíme konštantou trochu menšou ako 1). Alebo môžeme dokola striedať 4 hodnoty teploty. Fantázii sa medze nekladú.

Týmto spôsobom by ste pravdepodobne dostali 10 až 11 bodov, a ak správne odladíte konštanty, tak aj 12.

Labák

Ak chceme ísť ďalej, môžeme sa inšpirovať prírodou a skúsiť takzvané genetické algoritmy. Idea je nasledovná. Budeme sa tváriť, že naše zvieratká sú naozajstné živočíchy, že si skutočne spolu nažívajú v skupine zvanej populácia a že ich DNA reťazce sú naše stringy. Na začiatku si vyrobíme náhodne niekoľko zvieratiek a zistíme si ich odolnosť (pošleme ich do sveta). Tieto zvieratká nám budú tvoriť prvú generáciu našej populácie.

Tak ako bežne v prírode, zvieratká sa budú medzi sebou krížiť a ich DNA bude podliehať náhodným mutáciam (zmenám). Aby sme celý proces urýchlili (a tým zlepšili) budú mutácie oveľa pravdepodobnejšie ako naozaj v prírode. Tiež tak ako bežne v prírode, prežijú len najsilnejší. Každé zvieratko má nejakú pravdepodobnosť, že sa dožije ďalšej generácie a tá pravdepodobnosť by mala byť tým vyššia, čím odolnejšie je zvieratko.

Novú generáciu z predošlej vyrobíme nasledovne: Zahodíme náhodne vybraté zvieratká s nízkou odolnosťou (asi tretinu). Nakopírujeme najodolnejších pár zvieratiek. Náhodným zvieratkám spravíme náhodné mutácie. Nové náhodné zvieratká vytvoríme kombináciou predošlých. Spravíme ďalšie veci čo nám napadnú, napríklad môžeme pridať niekoľko nových úplne náhodných zvieratiek.

V celom postupe sa skrýva veľké množstvo magických konštánt, od veľkosti populácie po jednotlivé pravdepodobnosti. Tiež sa treba rozhodnúť, aké mutácie budeme robiť (tu sa dajú robiť rovnaké ako v hill-climbingu, náhodná zmena písmen, vymieňanie písmen atď.), a ako sa budú zvieratá krížiť. Často kríženie prebieha tak, že zoberieme dve (kľudne ale aj viac) zvieratiek a nejako ich spojíme dokopy. Napríklad začiatok reťazca zoberieme z prvého zvieratka a koniec z druhého. Tiež môžeme občas nechať nejaké zvieratko vyvinúť, napríklad tak, že ho dáme ako počiatočné pre hill-climbing a do ďalšej generácie pošleme už vyoptimalizované zvieratko.

Je tu obrovský priestor na experimentovanie a veľmi veľa možností, čo robiť. S hala-bala neporiadnym nastavením konštánt sa dalo získať 10 bodov.

Vedúcovské riešenie bolo tiež genetické programovanie s trocha lepšie nastavenými konštantami (aj keď určite sa dali ešte zlepšiť). Väčšinou dostalo 12 až 14 bodov.

Drobné optimalizácie na zváženie

Pokiaľ sme použili v algoritme nejakú náhodu, alebo aj keď nie, mohlo sa stať, že sme do sveta posielali to isté zvieratko dva krát. To je ale plytvanie drahocennými pokusmi. Čo môžeme spraviť je, že si každé zvieratko, na ktoré sme sa už spýtali, uložíme do mapy aj s jeho odolnosťou (a.k.a. memoizácia). Potom vždy, keď budeme chcieť otestovať nejaké zvieratko, tak sa najprv pozrieme, či už nie je v mape.

Pokiaľ by sme mali pamäťové problémy (zvieratiek je predsa len celkom dosť), môžeme si zvieratká trochu úspornejšie zakódovať, a to nie do stringov, ale do dvojíc longov (64 bitový integer). Stačí si uvedomiť, že na zakódovanie jedného génu nám stačia dva bajty. Potom vieme jedno zvieratko uložiť ako 100 bitov, čo sú dva longy. Toto prináša isté implementačné problémy a námahu, ale v pamäťovo rozšafnejších jazykoch na to treba myslieť.

Vedúcovský program takéto optimalizácie nerobil.

Tiež sme rátali s tým, že svoje riešenie odovzdáte viac krát a necháte tam to najlepšie. (Napríklad počty bodov za submity toho istého programu mohli vyzerať 13,12,14,11,12,13,14,12,14. V zadaní sme však písali aby ste to nepreháňali a odovzdať viac ako 100 programov nie je úplne fér.)

Krutý svet príkorí

Určite ste všetci zvedaví, ako vlastne fungoval svet – ako sa hodnotila odolnosť vtákopyskov.

Najprv sa z DNA reťazca dlhého 50 znakov vyrobil binárny reťazec dlhý 100 znakov a to tak, že každé písmeno si zmeníme na dva bity (\(A=00\), \(C=01\), \(G=11\), \(T=10\)) a prvých 50 bitov binárneho reťazca bude tvorených prvými bitmi písmen z DNA a druhých 50 bitov sú druhé bity z písnen z DNA. 1

Keď máme binárny reťazec, tak vypočítame takzvaný počet rôznych štvorcov v ňom. Teda spočítame koľko existuje reťazcov \(w\) takých, že \(ww\) sa nachádza v binárnom reťazci. Napríklad \(101011001100\) má 6 rôznych štvorcov a vyhovujúce \(w\)\(0,1,10,01,0110,1100\). Počítanie štvorcov sa robí pomocou hashovania, aby bolo rýchlejšie, a teda je tam nejaká, veľmi malá šanca, že sa pomýlime. (Napr. vtákopysk mal šťastný život a prežil o deň dlhšie ako by mal.)

Napokon, ešte penalizujeme reťazce, ktoré obsahujú dlhé úseky rovnakých bitov, lebo tie sú príliš nudné. Mohli ste mať však 20 rovnakých bitov za sebou beztrestne.

Áno, hodnotiaca funkcia bola pomerne komplikovaná, ale našťastie ste sa ňou nemuseli trápiť :). Keď ju poznáme, vieme spraviť o trocha lepšie riešenie, napríklad vedúcim sa podarilo nájsť zvieratko, ktoré prežilo 83 dní. Avšak nevieme, či je to najlepšie riešenie, či neexistuje nejaký lepší vtákopysk. Totiž túto úlohu, pre dané \(n\) nájsť binárny reťazec dĺžky \(n\) s najväčším počtom štvorcov nevieme efektívne riešiť. Na riešenie úloh, ktoré nevieme efektívne riešiť, často používame také heuristické algoritmy2 ako sme si spomínali vyššie. Ak spravíme dobrý heuristický algoritmus, tak na malých vstupoch dáva optimálny výsledok oveľa rýchlejšie ako exaktný algoritmus a na veľkých vstupoch, kde by exaktný algoritmus bežal milióny rokov, dáva celkom dobré výsledky pomerne rýchlo.

Algoritmus, ktorý bodoval vaše riešenia vyzeral takto:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define For(i, n) for(int i = 0; i<int(n); ++i)

#define QUERYCNT 100000
#define DNALENGTH 50
#define PRIME 47

string line, rotline;
string alph = "ACGT";
int H[2*DNALENGTH+17];
int powers[2*DNALENGTH+17];
int map[256];
vector<int> V;

int zivot(const string &str) {
    // spocitaj HASH a najdlhsi usek rovnakych bitov
    int mono = 0, maxmono = 0;
    H[0] = 0;
    For(i, DNALENGTH*2) {
        H[i+1] = H[i]*PRIME + str[i];
        mono = (i>0 && str[i]==str[i-1])?mono+1:0;
        maxmono = max(maxmono, mono);
    }
    maxmono /= 20;

    // najdi vsetky rozne vyskyty ww
    int h;
    int pocet = 0;
    for(int d = 1; 2*d<=2*DNALENGTH; ++d) {
        V.clear();
        for(int i = 0; i+2*d<=2*DNALENGTH; ++i)
            if ((h = H[i+d] - H[i]*powers[d]) == (H[i+2*d] - H[i+d]*powers[d])) {
                V.push_back(h);
            }
        sort(V.begin(), V.end());
        For(i, V.size()) if (i==0 || V[i]!=V[i-1]) pocet++;
    }

    return (pocet-maxmono)/(maxmono+1);
}

void zle(const string &message) {
    cout << message << endl;
    cerr << "Skore 0" << endl;
    cerr << "Chyba " << message << endl;
    exit(1);
}

int skore(int s) {
    if (s >= 80) return 15;
    if (s >= 78) return 14;
    if (s >= 76) return 13;
    if (s >= 73) return 12;
    if (s >= 70) return 11;

    if (s >= 67) return 10;
    if (s >= 65) return 9;
    if (s >= 63) return 8;
    if (s >= 61) return 7;
    if (s >= 58) return 6;

    if (s >= 53) return 5;
    if (s >= 47) return 4;
    if (s >= 36) return 3;
    if (s >= 21) return 2;
    if (s >= 10) return 1;
    return 0;
}

int main() {
    int rot = rand()%DNALENGTH;
    For(i, 256) map[i] = -1;
    For(i, alph.size()) map[alph[i]] = i;
    powers[0] = 1;
    For(i, DNALENGTH+16) powers[i+1] = powers[i]*PRIME;
    int maxzivot = 0;
    rotline.resize(2*DNALENGTH);

    For(q, QUERYCNT) {
        if (! (cin >> line)) zle("Nenasiel som DNA na vstupe.");
        if (line.size() == 1 && line == "K") break;
        if (line.size() != DNALENGTH) zle("Zla dlzka riadku!");
        For(i, line.size()) if (map[line[i]]<0) zle("Zly format riadku! Ocakavam len znaky ACGT");

        For(i, DNALENGTH) {
            // zmen vstup na retazec bitov
            int p = (i+rot)%DNALENGTH;
            rotline[i] = map[line[p]]/2;
            rotline[DNALENGTH+i] = map[line[p]]%2;
        }
        int z = zivot(rotline);
        maxzivot = max(maxzivot, z);
        cout << z << endl;
    }
    cerr << "Zivot " << maxzivot << endl;
    cerr << "Skore " << skore(maxzivot) << endl;
}

Záver

Genetické programovanie, simulované žíhanie a hill-climbing sú príklady heuristických algoritmov, ktoré sa pomerne ľahko programujú a dávajú celkom dobré výsledky.

Konkrétne v tejto úlohe má podľa nás najväčšiu nádej na úspech práve genetické programovanie, ktoré (ak ste tomu venovali dosť času) vám umožnilo získať 14 bodov. Ak by ste boli veľkí šťastlivci alebo by ste sa s úlohou naozaj dlho hrali, bola nádej získať 15 bodov. Nikomu sa to však nepodarilo.


  1. Teda ešte pred tým sa celý vstup zrotoval nejakou náhodnou cyklickou rotáciou, ktorá bola fixná počas celého behu programu. Toto tam bolo na to, aby sa funkcia trocha líšila pri rôznych behoch a aby sa nedali jednoducho využívať informácie z predošlých submitov.

  2. Teda nemáme žiadnu záruku, že dajú správnu odpoveď

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.