Zadání:

Iterativní metoda Simulovaného ochlazování

Naprogramujte řešení 0/1 problému batohu metodou simulovaného ochlazování (simulated annealing - SA).

Řešení:

Metoda Simulovaného ochlazování

Nastaveni parametru:

• Pocatecni stav: prazdny batoh
• Minimalni teplota: 10
• Maximalni teplota: optimalni cena ziskana metodou dynamickeho programovani
• Pocatecni teplota: maximalni teplota
• Koeficient klesani teploty: 0.98
• Koeficient klesání počtu stavů na jednu teplotní iteraci: 0.98
• Počet iterací na jedné teplotě: 20 000
• Casove omezeni vypoctu: max 20s

Detaily implementace:

Výpočet je omezen 2-ma faktory. Jednak je to klesající teplota (klesá geometricky s koeficientem) a jednak je to čas. Na každý výpočet je nastaven čas 20s. Výpočet je implementován jako vlákno, které se po 20s stopne a vezmou se aktuální výsledky. Jako jedna iterace je považováno nalezení stavu, který je různý od předchozího.

Zkusil jsem jemné změny parametrů výpočtu. Změna maximální teploty na 1/2 se projevila velkým zhoršením výsledků. Stejně tak i změny koeficientu klesání počtu iterací a koeficientu klesání teploty. Zmena minimální teploty přinesla minimální zlepšení, které je ale ve statistické chybě.

Testování jsem prováděl na instanci batohu se 40 předměty. Výsledky jsou shrnuty v následující tabulce:

Metoda výpočtu	Instance problému	Čas na jednu instanci	Průměrná chyba	Maximální chyba	Minimální chyba
Simulované ochlazováni	40	<=20s	11.8%	21.3%	4.6%

Závěr

Zkoušel jsem tuto metodu spouštět vícekrát nad stejnými daty, avšak její výsledky se zdají být rovnocenné. Ve většině případů nalezne řešení do 20% chyby, což je horší, než jakákoliv jiná heuristika, nicméně její výpočet je možné libovolně prodloužit a tím případně dojít k lepším výsledkům.

Program je psán v Javě verze 5.0. Stáhnout si ho můžete zde, nebo se můžete podívat do zdrojových kódů. Detailní výsledky naleznete v spreadsheetu.