Řešení problému batohu pokročilou iterativní heuristikou

Úloha z předmětu 36PAA

Martin Tůma

Zadání

Zpráva by měla obsahovat:

  1. Stručný popis zvoleného algoritmu
  2. Zhodnocení Vašich experimentů. Zkoušejte sledovat vývoj řešení (populace u GA) v průběhu běhu algoritmu. Graf potěší...
  3. Experimentujte s různými nastaveními parametrů
  4. 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á)
  5. Pokuste se vyvodit nějaké závěry

Řešení

Jako heuristiku jsem zvolil simulované ochlazování, jehož základní princip uvádí následující odstavec.

Simulované ochlazování

Simulované ochlazování je lokální metoda prohledávání stavového prostoru, která je inspirovaná stejnojmenou technikou používanou v metalurgii. Metoda umožňuje při prohledávání jako následující stav s určitou pravděpodobností přijmout i stav horší než aktuální a vyhnout se tak lokálním minimům. Tato pravděpodobnost klesá s klesající teplotou, což zajištuje konvergenci algoritmu. Podrobný popis algoritmu uvádí například [3].

STATE anneal(void)
{
    temp = INIT_TEMP
    state = INIT_STATE
    best = state    

    do {
        do {
            state = next_state(state, temp)
            best = better(state, best)
        } while (!equilibrium())
        temp = cool(temp)
    } while (!frozen(temp))

    return best
}

Kostra algoritmu simulovaného ochlazování.

Naměřené hodnoty

Měření probíhala na souboru instancí velikosti 40 [1]. Naměřené relativní chyby jsou vždy průměry ze všech instancí ve vstupním souboru při změně zkoumaného parametru. Čas výpočtu je udáván pro celý vstupní soubor. Vývoj řešení je měřen na první instanci souboru.

Testovací konfigurace: CPU Duron 900MHz, OS Linux, GCC 3.4.4 (žádné optimalizační flagy)

Vývoj řešení

Graf 1: Vývoj ceny aktuálního stavu řešení v závislosti na iteraci algoritmu. (Naměřená data)

Čas výpočtu a relativní chyba v závislosti na koeficientu ochlazování

c [-] ηø [%] ηmax [%] t [s]
0.8000.30712.353 3.440
0.8250.193 7.345 4.040
0.8500.203 7.345 4.460
0.8750.28412.353 5.772
0.9000.203 9.849 7.276
0.9250.25312.353 9.841
0.9500.112 4.84114.749
0.9750.096 4.84129.738

Graf 2: Čas výpočtu a relativní chyba v závislosti na koeficientu ochlazování.

Čas výpočtu a relativní chyba v závislosti na výchozí teplotě

Tinit [-] ηø [%] ηmax [%] t [s]
1000.30412.3532.032
2000.242 9.8492.772
5000.185 7.3453.884
10000.203 7.3454.812
30000.233 9.8495.832
50000.250 9.8495.928

Graf 3: Čas výpočtu a relativní chyba v závislosti na výchozí teplotě.

Čas výpočtu a relativní chyba v závislosti na koncové teplotě

Tfinal [-] ηø [%] ηmax [%] t [s]
0.10.082 2.3378.657
10.092 2.3376.108
50.079 2.3374.380
100.145 4.8413.804
200.38114.8583.100

Graf 4: Čas výpočtu a relativní chyba v závislosti na koncové teplotě.

Závěr

Simulované ochlazování se ukázalo být poměrně efektivní heuristikou pro řešení problému batohu. V porovnání s heuristikou typu nejrychlejšího vzestupu dosahuje při "rozumné" době běhu1 výpočtu prakticky srovnatelné výsledky.

Testy dále ukázaly, že metoda je poměrně citlivá na nastavení parametrů, jejihž změny navíc nejsou navzájem nezávislé. Pro daný soubor (a budeme-li tento brát jako reprezentativní pro všechny instance velikosti 40 tak i pro úlohy velikosti instance 40) se jako ideální nastavení jeví tyto hodnoty: výchozí teplota: 500, koncová teplota: 5, koeficient ochlazování: 0.825 a počet iterací vnitřního cyklu: 10000. Při tomto nastavení metoda dává průměrnou relativní chybu 0.08%, maximální relativní chybu 2.34% a (na dnes již obstaróžním HW) čas výpočtu na instanci: 88ms

1Bohužel jsem pro tuto úlohu z důvodu poruchy neměl k dispozi HW na kterém byly testovány předchozí metody, proto nelze dobu běhu porovnat, nicméně lze předpokládat, že bude u simulovaného ochlazování vyšší.

Reference

[1] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#bench
[2] http://service.felk.cvut.cz/courses/36PAA/wknapgen.html
[3] http://service.felk.cvut.cz/courses/36PAA/prez/PAA8ochl.pdf

Přílohy

1. batoh_sa.c - Program pro řešení metodou simulovaného ochlazování.