EVO: cvičení 1 - Úloha N dam, TSP
- Stáhněte si archív s úlohami:
- nastavte spustitelnost (chmod +x Nqueens.py)
- nastavte spustitelnost (chmod +x tsp.py)
Řešená úloha - Problém N dam
Jak lze rozmístit n dam na šachovnici o rozměrech n×n tak, aby se vzájemně neohrožovaly?
- Chceme ušetřit počet kombinací stavového prostoru
- Víme, že dámy nemohou být ve stejném sloupci ani řádku
- O(n2n) = (82)8 = 281 474 976 710 656
(tzn. 281 bilionů -- pro představu: int32_max = 2,1 mld.; veřejný dluh ČR je 1,8 bil.)
- O(n!) = 8! = 40 320
- → permutační kódování
- Permutační kódování vyžaduje vhodné genetické operátory.
- Doplňte fitness funkci:
- Fitness by měla být tím menší, čím lepší je řešení problému.
- → Počet konfliktů.
- Máme už hotové kódování, které zajišuje absenci konfliktů na řádcích a sloupcích.
- → Potřebujeme spočítat počet konfliktů na diagonálách.
- Program na stderr vypisuje průběžné údaje (číslo iterace, fitness).
Po doběhnutí vykreslí na stdout šachovnici s nalezeným řešením.
- Až budete mít fungující program, ukládejte si výpisy do souboru a zobrazte průběh několika běhů.
- python2.7 Nqueens.py 2>> param025.txt
- gnuplot
plot 'param025.txt' u 1:2:-1 w l lc variable lw 3
- (Ze zadaného souboru použij (using 1:2) první a druhý sloupec jako souřadnice x a y, zobraz jako čáry (with lines) nastav barvu (linecolor variable) jako proměnnou minusprvní sloupec vstupu, tlusté čáry (linewidth 3).)
- Experimentujte s nastavením parametru, hledejte co nejlepší.
Řešená úloha - Problém obchodního cestujícího (TSP)
V daném ohodnoceném úplném grafu najděte nejkratší hamiltonovskou kružnici.
Př.: vrtání desek plošných spojů -- co nejkratší dráha vrtáku:
(obvod http://pandatron.cz/?199&ne555_-_priklady_pouziti_-_1)
- Program na stderr vypisuje průběžné údaje (číslo iterace, vzdálenost, nejlepší vzdálenost).
Po doběhnutí graficky znázorní nejlepší nalezené dráhy vrtáku pomocí gnuplot. Př.:
./tsp.py | gnuplot - --persist
- Ověřte, že algoritmus nachází „dobré“ řešení.
- Jaký typ algoritmu je použit?
- Ukládejte si výpisy do souboru a zobrazte průběh několika běhů.
- ./tsp.py 2>> tsp-var1.txt >/dev/null
- gnuplot
plot 'tsp-var1.txt' u 1:2:-1 w l lc variable lw 1, '' u 1:3:-1 w l lc variable lw 3
- Vysvětlete rozdíl mezi jednotlivými variantami algoritmu.