1. Opis łamigłówki
2. Metoda rozwiązywania łamigłówki
3. Postać algorytmu
4. Struktury danych i implementacja
5. Wyniki testów i ich interpretacja
Łamigłówka polega na zaczernieniu pewnej liczby pól pokratkowanego prostokąta w odpowiedni sposób, aby powstał obrazek, zgodny z liczbami, które znajdują się z lewej strony obrazka oraz nad obrazkiem. Liczby po lewej stronie obrazka oznaczają, ile pól należy zaczernić w poszczególnych wierszach, natomiast liczby znajdujące się nad obrazkiem mówią nam, ile pól powinno być zaczernionych w każdej z kolumn. Na przykład sekwencja liczb 3,6,1,2 oznacza, że w danym wierszu lub w danej kolumnie powinny znaleźć się cztery „bloki” zaczernionych pól, pierwszy złożony z 3 zaczernionych pól, drugi z sześciu itd. Pomiędzy zaczernionymi blokami musi się znaleźć co najmniej jedno nie zaczernione pole. Jak łatwo zauważyć, rozwiązanie może nie być jednoznaczne – w szczególności dla prostokąta o wymiarach np. n*n rozwiązań może być n!
2. Metoda
rozwiązywania łamigłówki
Obrazek logiczny rozwiązuję, wykorzystując algorytmy genetyczne. Osobnikiem populacji jest obrazek (niekoniecznie poprawny). Program, wykorzystując podstawowe procedury algorytmów genetycznych, tj. selekcję, mutowanie, krzyżowanie oraz wymianę, poprawia znalezione dotychczas rozwiązanie, aż do znalezienia jednego z poprawnych rozwiązań.
3. Postać
algorytmu
Algorytm w pseudo-C++ wygląda następująco:
main();
{
K = 0;
wyznacz_populacje_poczatkowa();
do
{
K = K + 1;
SELEKCJA();
KRZYZOWANIE();
MUTACJA();
WYMIANA();
}
while (!warunek_konca());
zapis();
}
4. Struktury
danych i implementacja
4.1. Osobniki
W implementacji algorytmu w Visual C++ zdefiniowałem typ typ_danych, który określa typ danych wejściowych (może to być int, float itp.). Oprócz tego zdefiniowałem typ danych Osobnik:
struct Osobnik
{
long koszt;
Osobnik *nast;
int * po;
int * pi;
char ** poziom;
char ** pion;
}.
Każdy osobnik posiada pole koszt,
którego wartością jest wynik funkcji oceny danego osobnika (funkcja
‘koszt_os’). Tablice dwuwymiarowe ‘poziom’ i ‘pion’ stanowią reprezentację
danego osobnika (zawierają informacje o odstępach pomiędzy poszczególnymi
zaczernionymi blokami w danym osobniku). Jeśli np. poziom[i] zawiera liczby
a,b,c, oznacza to, że osobnik reprezentuje obrazek, który w i-tym wierszu ma
zaczernione 3 odrębne bloki, przy czym pierwszy blok zaczyna się w a+1-ej
kolumnie, natomiast między pierwszym a drugim blokiem jest b pól nie
zaczernionych, między drugim a trzecim – c itd. Jak łatwo zauważyć tak dobrana
reprezentacja osobnika wyklucza całkowicie niedopuszczalnych osobników (tzn.
takich, które mają „zlepione” bloki). Tablice ‘po’ oraz ‘pi’ informują, czy w
danym wierszu lub w danej kolumnie wszystkie kratki są wypełnione poprawnie.
Osobnik zawiera również wskaźnik na następnego osobnika.
Osobniki są pamiętane w liście
(pamiętany jest wskaźnik na aktualnie najlepszego i najgorszego osobnika).
Podczas selekcji trzeba wyselekcjonować najlepszych osobników, dlatego pamiętam
permutacje w liście uporządkowanej według wartości ‘lista^.koszt’.
Liczba osobników wyznaczanych w populacji początkowej jest zależna od współczynnika populacji, wyznaczana do następnej populacji jest uzależniona od współczynnika selekcji, wyznaczana do krzyżowania jest uzależniona od współczynnika krzyżowania, wyznaczana do mutowania jest zależna od współczynnika mutacji. Liczba potomstwa otrzymanego w skutek krzyżowania jest rzędu n3, gdzie n jest liczbą osobników wyznaczonych w populacji początkowej.
4.2. Krzyżowanie
Specjalnie zaimplementowane krzyżowanie wyklucza powstanie niedopuszczalnego osobnika. Mając danych dwóch osobników, wymieniany jest i-ty wiersz bądź też i-ta kolumna jednego i drugiego osobnika. Powstają w ten sposób dwa nowe osobniki, które są zapamiętywane w pomocniczej liście.
4.3. Mutacja
Pierwsza, podstawowa procedura mutacji polega na przesuwaniu pojedynczych bloków „zaczernionych” pól w prawo, w lewo, w górę lub w dół. Na przykład osobnik, który przed mutacją w poziom[i] miał sekwencję liczb a,b,c,d, po mutacji będzie mógł mieć np. a,b-1,c+1,d, co oznacza przesunięcie drugiego bloku w lewo. Druga mutacja polega na zamienieniu ze sobą danych dwóch liczb z tablicy ‘poziom’ lub ‘pion’ danego osobnika (podobna do pierwszej, ale przesuwamy całe bloki). Trzecia procedura mutacji polega na przekłamaniu pewnej liczby z tablicy ‘poziom’ bądź ‘pion’ danego osobnika, co oznacza przesunięcie kilku bloków w prawo lub w lewo. Ta mutacja jest podobna do drugiej. Zasadniczą różnicą jest to, że trzecia mutacja pozwala na przesunięcie bloków o dowolną liczbę kratek w prawo lub w lewo (o ile to możliwe), natomiast druga mutacja jest pod tym względem ograniczona. Czwarta mutacja jest pewnym ulepszeniem pierwszej mutacji, z tym, że na raz mutujemy zarówno tablicę ‘poziom’ jak i ‘pion’.
4.4. Wymiana
Wymiana polega na wymienieniu populacji na nową, w zależności od wartości funkcji oceny dla osobników spośród tych, które były w poprzedniej populacji oraz powstały w wyniku krzyżowania oraz mutacji. W populacji zostaje liczba osobników zależna od współczynnika populacji (wsp_pop).
4.5. Warunek końca obliczeń
Program kończy działanie, jeżeli liczba wygenerowanych osobników przekroczy LI_max lub gdy wykona odpowiednią liczbę iteracji – liczba_iteracji, bądź też znajdzie jedno z możliwych rozwiązań.
5. Wyniki
testów i ich interpretacja
Program wczytuje dane z pliku wejściowego, następnie wykonuje ciąg iteracji, a po znalezieniu pewnego rozwiązania (niekoniecznie najlepszego), zapisuje wyniki do pliku wyjściowego. W pliku wejściowym występują kolejno liczby oznaczające: liczbę wierszy, liczbę kolumn, maksymalną liczbę bloków do zaczernienia w danym wierszu, liczby, oznaczające, ile pól należy zaczernić w danych wierszach, maksymalną liczbę bloków do zaczernienia w danej kolumnie, liczby, oznaczające, ile pól należy zaczernić w danych kolumnach.
Jako wynik program zapisuje do pliku wyjściowego koszt najlepszego osobnika, oznaczający to, ile pól sprzecznych opisuje reprezentowany osobnik, a następnie reprezentację osobnika.
Tab. 1. Wyniki testów dla przykładowych obrazków przy liczbie iteracji równej 100 i wprowadzaniu losowych osobników..
|
Obrazek |
Liczba niepoprawnych rozwiązań na 20 uruchomień programu po zaimplementowaniu 1/2/3/4 mutacji |
Liczba poprawnych rozwiązań na 20 uruchomień programu po zaimplementowaniu 1/2/3/4 mutacji |
Średnia liczba iteracji potrzebna do rozwiązania obrazka |
|
Laufer |
19/18/11/10 |
01/02/09/10 |
85/83/80/79 |
|
Jablko |
20/18/12/09 |
00/02/08/11 |
--/89/83/82 |
|
Szachy |
19/17/12/11 |
02/03/08/09 |
92/89/85/84 |
|
96_07a |
20/20/13/12 |
00/00/07/08 |
--/--/89/85 |
|
96_07b |
19/18/12/10 |
01/02/08/10 |
90/88/85/82 |
|
96_07c |
17/17/10/08 |
03/03/10/12 |
89/86/83/81 |
|
96_07d |
19/18/14/12 |
01/02/06/08 |
91/87/84/80 |
|
96_08 |
17/16/11/11 |
03/04/09/09 |
88/85/80/79 |
|
96_09 |
18/16/13/12 |
02/04/07/08 |
89/83/80/80 |
|
96_11 |
17/15/11/09 |
03/05/09/11 |
88/82/81/78 |
Początkowo testy przeprowadzałem na programie, który w losowy sposób generował osobników i po ich wygenerowaniu wybierał najlepszego (tzn. takiego o najmniejszym koszcie), który stawał się tym samym rozwiązaniem końcowym, niekoniecznie poprawnym w 100%. Wyniki, jak można się było tego spodziewać, nie były zbytnio zadowalające. Właściwie żaden z obrazków większych niż 10 na 10 nie był rozwiązany poprawnie. To przekonało mnie, że bezmyślne losowanie osobników do niczego mnie nie doprowadzi. Trzeba było zastosować jakiś mechanizm związany z algorytmami genetycznymi! Zaimplementowałem procedury Selekcji oraz krzyżowania. Krzyżowanie miało jak sama nazwa wskazuje krzyżować różne osobniki ze sobą, aby w ten sposób uzyskać inne, być może lepsze, natomiast selekcja służyła jako procedura pomocnicza, która usuwała najsłabszych osobników (tych o największym koszcie). Po tak poprawionym programie wyniki znacznie się poprawiły, co było do przewidzenia. Jednak nie wykorzystywałem jeszcze wtedy wszystkich mechanizmów, które oferują algorytmy genetyczne. Skoro selekcja i krzyżowanie dalej nie rozwiązywały obrazków 10 na 10, trzeba było zaimplementować procedurę mutacji. Jak się okazało wyniki poprawiły się, jednak bardzo nieznacznie. Postanowiłem zaimplementować drugą procedurę mutacji, opartą na trochę innym pomyśle. W sumie po umieszczeniu dwóch rodzajów mutacji wyniki minimalnie poprawiły się, jednak dalej obrazki nie były poprawnie rozwiązywane. Wobec takiego obrotu sprawy, zaimplementowałem kolejną procedurę mutacji, która okazała się przełomem w moim programie. Wykorzystanie trzeciej mutacji okazywało się lepsze niż połączenie dwóch poprzednich, natomiast połączenie wszystkich trzech dawało niespotykane dotychczas rezultaty. Zaimplementowałem jeszcze czwartą procedurę mutacji, która przyniosła niewielką, ale jednak pewną poprawę wyników.
Aby polepszyć uzyskiwane rezultaty postanowiłem, że do populacji będę dokładał przy kolejnych iteracjach losowych osobników. Ku mojemu zaskoczeniu okazało się, że wyniki znacznie się polepszyły.
Z przeprowadzonych testów wynika, że każdy z mechanizmów oferowanych przez algorytmy genetyczne, tj. selekcja, krzyżowanie, mutacja oraz wymiana odegrało w programie swoją rolę. W algorytmie nie rozważałem niepotrzebnie zbyt dużej liczby gorszych osobników. Procedury dodatkowo wstawiały do populacji losowych osobników, zapobiegając w ten sposób ujednolicania populacji. Dużym problemem okazało się częste dążenie programu do znajdowania lokalnego minimum, jednak po wprowadzeniu losowych osobników sytuacja znacznie się poprawiła. Myślę, że losowe osobniki odegrały kluczową rolę w działaniu programu.
Dodatkowo na działanie programu duży wpływ odegrało ustalenie odpowiednich współczynników, szczególnie mutacji oraz krzyżowania. Im większy współczynnik krzyżowania i mniejszy współczynnik mutowania, tym program osiągał lepsze rezultaty, jednak działał nieco dłużej. Oczywiście dla konkretnego rodzaju obrazka warto ustalać pewne szczególne współczynniki, jednak znalezienie tych najodpowiedniejszych okazuje się bardzo trudne.
Algorytmy genetyczne nadawałyby się do rozwiązywania łamigłówek takich jak obrazek logiczny, jednak warto byłoby się zastanowić nad polepszeniem być może reprezentacji osobników oraz wybrania odpowiedniej funkcji oceny. Ważną rzeczą jest również zaimplementowanie odpowiedniej, być może opartej na innym pomyśle mutacji, co mogłoby znacznie polepszyć wyniki. Dobranie odpowiedniego krzyżowania również byłoby ważne. Krzyżowanie bowiem oznacza w pewnym sensie próbę wymiany informacji genetycznej pomiędzy dwoma osobnikami, co może doprowadzić do tego, że skrzyżowany osobnik będzie miał niższy koszt (to tak jak np. w szkole, jeśli dwaj uczniowie przychodzą ze szkoły z pewnymi informacjami, to wymieniając ze sobą informacje zapamiętane na lekcji, mogą razem powiększyć swoją wiedzę).
Program testowałem na komputerze z procesorem Pentium II 233 MHz z 32 MB RAM. Przykładowe wyniki znajdują się w plikach dołączonych do projektu.