Úloha 5

Autor: Petr Chytil

Zadání

Algoritmy k výběru

• Simulované ochlazování

• Genetické algoritmy

• Tabu search

Co tedy máte udělat

• Zvolte si heuristiku, kterou budete řešit problém vážené splnitelnosti booleovské formule (simulované ochlazování, simulovaná evoluce, tabu prohledávání)

• Tuto heuristiku použijte pro řešení problému batohu. Můžete použít dostupné instance problému (zde), anebo si vygenerujte své instance pomocí generátoru. Používejte instance s větším počtem věcí (>30).

• Hlavním cílem domácí práce je seznámit se s danou heuristikou, zejména se způsobem, jakým se nastavují její parametry (rozvrh ochlazování, selekční tlak, tabu lhůta...) a modifikace (zjištění počáteční teploty, mechanismus slekce, tabu atributy...). Není-li Vám cokoli jasné, prosíme ptejte se na cvičeních.

• Problém batohu není příliš obtížný, většinou budete mít k dispozici globální maxima (exaktní řešení) z předchozích prací, například z dynamického programování.

Zpráva by měla obsahovat

• Stručný popis zvoleného algoritmu

• Zhodnocení Vašich experimentů. Zkoušejte sledovat vývoj řešení (populace u GA) v průběhu běhu algoritmu. Graf potěší...

• Experimentujte s různými nastaveními parametrů

• Výsledek měření = čas výpočtu a rel. chyba. Pokud nejste schopni vypočítat rel. chybu, stačí uvést vývoj výsledné ceny (počáteční -> koncová)

• Pokuste se vyvodit nějaké závěry

Řešení - simlulované ochlazování

Stručný popis algoritmu

Simulované ochlazování se na rozdíl od genetických algoritmů inspirovalo ve fyzice. Jedná se tak o simulaci ochlazování zahřátého kovu. Kmitání zahřátých částic pro nás představuje možnost vyskočit z aktuálního řešení do řešení v okolí, jehož velikost je dána teplotou. Vyšší teplota znamená větší rozkmit a skoky do vzdálenějších řešení. S klesající teplotou se rozkmit zmenšuje, až se postupně zastaví uplně a algoritmus „zamrzne“ na konečném řešení.

Důležitou součástí použití tohoto algoritmu je nastavení všech počátečních parametrů. Jedná se o počáteční teplotu, konečnou teplotu (po jejím dosažení se nepokračuje) a koeficient ochlazování. Posledním parametrem je pak délka vnitřní smyčky, která určuje, jak dlouho algoritmus hledá nejlepší stav na aktuální teplotě.

Vyřešit pomocí tohoto algoritmu problém batohu znamenalo v první řadě naimplementovat metodu nextState (v kódu níže je vidět, kde je volána). Ta vrací souseda, který ještě vyhovuje aktuální teplotě algoritmus. Soused je pak batoh o stejné konfiguraci, který se liši přidáním/odebráním právě jednoho předmětu.

Kód kostry algoritmu (dle slidů na cvičení)

    public State simulatedAnnealing(State initState) {
        temp = initTemp;
        state = initState;
        best = state;
        do {
            steps = initSteps;
            do {
                state = nextState(state, temp);
                best = better(best, state);
            } while (!equilibrium());

            temp = cool(temp);
        } while (!frozen());

        return best;
    }

• Zdrojové kódy celého řešení v jazyce java jsou tradičně k nahlédnutí v adresáři src.

• Export sešitu z Excelu, který byl použit pro některé výpočty a tvorbu grafů je v souboru vypocty.

Hledání počátečních parametrů

Měření jsem provedl několikrát „nanečisto“, abych zjistil jak nastavit alespon přibližně počáteční parametry. Vybral jsem parametry následující:

počáteční teplota = 1000

konečná teplota = 3

počet kroků = 10000

faktor ochlazování = 0.8

S těmito parametry jsem pak provedl všechna následující měření. A to měněním jednoho z parametrů a zaznamenáváním času běhu algoritmu a jeho relativní chyby.

Pro měření byl použit soubor instancí knap_40.txt tak, jak je k dispozici na stránkách předmětu. Relativní chyba je pak vypočítána proti výsledkům dynamického programování, které dává optimální řešení pro problém batohu.

A jako vždy - měření byla provedena pomocí knihovní funkce System.nanoTime(), kterou jazyk Java poskytuje.
A to na stroji s procesorem Core Duo 1.66GHz a operačním systémem Windows XP 32bit.
Nebylo započítáváno načítaní dat ze souboru ani jejich zapisování na výstup. Každá změřená časová hodnota v grafu je průměrem měření 50ti instancí.

• Počáteční teplota

• Konečná teplota

• Faktor ochlazování

• Počet cyklů ve vnitřní smyčce

Po těchto měřeních jsem nastavil parametry takto:

počáteční teplota = 500

konečná teplota = 10

počet kroků = 10000

faktor ochlazování = 0.85

Graf závislosti času výpočtu na počtu instancí při použití uvedených parametrů pak vypadá

A k němu odpovídající relativní chyby

Závěr

Výsledky implementace tohoto algoritmu jsou vskutku zajímavé. Při zvoleném nastavení není algoritmus závislý na počtu prvků v batohu (tuto závislost si můžeme přidat sami např. zvolením počáteční teploty jako násobku velikosti instance). Pro toto nastavení dosáhl algoritmus téměř v polovině případů optimálního výsledku (jedním případem je myšlen soubor 50ti instancí a tak relativní chyba je průměrem z 50ti naměřených relativních chyb). Jeho použitelnost je tak především u velkých instancí problému, kdy by již měl možnost dostihnout dynamické programování, které je tak doposud pro mnou testované soubory instancí nejlepším řešením.