WsdSI/LJK/za2

From WikiZMSI

Spis treści 1 Problem 2 Algorytm 3 Wynik 4 Termin oddania programu

Problem

Rozwiązywany problem to n-hetmanów, gdzie n jest parametrem programu. Określa on wielkość szachownicy jak i liczbę hetmanów.

Algorytm

Rozwiązać problem stosując algorytm ewolucyjny z kodowaniem permutacyjnym.

• Chromosom: wektor zawierający n wartości określających położenie hetmanów w poszczególnych kolumnach (wartości bez powtórzeń)
• Funkcja przystosowania: liczba atakujących się hetmanów (wartość funkcji 0 oznacza rozwiązanie)
• operatory genetyczne: mutacja dla kodowania permutacyjnego (zamiana mijescami dwóch losowo wybranych hetmanów)
• selekcja rankingowa: posortować osobnik od najgorszego do najlepszego wg funkcji przystosowania, nr w liście staje się wartością, którą wykorzystuje się w metodzie ruletki.

Parametry programu

• n: wielkość szachownicy
• liczność populacji zakres od 10 do 100
• prawdopodobieństwo mutacji zakres większe od 0,3 mniejsze od 0,8
• liczba generacji zakres od 100 do 10000

Warunek stopu (zatrzymania pętli)

• Wartość funkcji przystosowania równa 0
• Osiągnięcie założonej liczby iteracji (generacji)

Wynik

• Najlepszy chromosom z populacji (taki, którego funkcja przystosowania ma najmniejszą wartość)
• Wykres zmian wartości funkcji przystosowania dla najlepszego osobnika w populacji w generacjach.
• Wykres średniego przystosowania populacji zmieniającego się w generacjach.

Termin oddania programu

• Grupa 20A --- 27 kwietnia 2019
• Grupa 20B --- 28 kwietnia 2019
• Grupa powt --- 27 kwietnia 2019