Algorytmy genetyczne

Problem ośmiu hetmanów

Radosław Zawcki nr. Indeksu 29902 2007-07-09

1.Wstęp

Algorytm - w matematyce oraz informatyce to skończony, uporządkowany zbiór jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania. Słowo "algorytm" pochodzi od nazwiska Muhammed ibn Musa Alchwarizmi matematyka perskiego z IX wieku i początkowo oznaczało w Europie sposób obliczeń oparty na dziesiętnym systemie liczbowym.

Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zaimplementowany w postaci programu komputerowego lub dla innego urządzenia. Kiedy podczas tego procesu programista popełni błąd (ang. bug), może to doprowadzić do poważnych konsekwencji np. błędy w implementacji algorytmów bezpieczeństwa mogą ułatwić popełnienie przestępstwa komputerowego. Jako przykład stosowanego w życiu codziennym algorytmu podaje się często przepis kulinarny. Dla przykładu, aby ugotować bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma wyłącznie charakter poglądowy, ponieważ język przepisów kulinarnych nie został jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki. W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (np. GIF). Wiele koncernów komputerowych prowadzi między sobą prawnicze spory dotyczące praw własności do niektórych patentów. Kontrargumentem jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy. Prawidłowy algorytm komputerowy musi kiedyś zakończyć swoją pracę. Oznacza to, że problem musi być rozwiązany z wykorzystaniem dostępnych zasobów obliczeniowych w skończonym czasie. Jeżeli czas obliczeń algorytmu dla coraz większego zbioru danych rośnie szybciej niż dowolna funkcja wielomianowa, to mówi się że nie jest praktycznie obliczalny. Jedną z klas problemów, dla których nie znamy wielomianowych rozwiązań, są problemy NP-trudne. Jeśli znamy wielomianowy algorytm weryfikujący poprawność rozwiązania problemu NP-trudnego, to problem ten nazywamy NP-zupełnymi. Pytanie, czy P=NP, czyli czy istnieją szybkie algorytmy rozwiązujące problemy NP-zupełne, jest najsłynniejszym problemem otwartym we współczesnej informatyce. Dodatkowo istnieją problemy nierozwiązywalne za pomocą żadnego algorytmu - tzw. problemy nierozstrzygalne

2.Co to są algorytmy genetyczne?

Algorytmy genetyczne są jedną z metod optymalizacji zadań w wieloetapowym procesie doskonalenia rozwiązań, w którym wykorzystuje się zasadę doboru wartości zmiennych (stanowiących rozwiązanie zadania) wzorowaną na procesach doboru naturalnego w żywych organizmach. Przy dobrze dobranych parametrach genetycznych szybko odnajdują szukane optimum nawet w zadaniach w których inne metody mogą zawodzić. Dzięki temu stają się coraz powszechniejsze i wciąż rozbudowywane na wiele sposobów, mających poprawić skuteczność ich działania.

Algorytmy genetyczne są to algorytmy poszukiwania oparte na mechanizmach doboru naturalnego oraz dziedziczności. Algorytmy te łączą w sobie ewolucyjną zasadę przeżycia najlepiej przystosowanych osobników z systematyczną, choć zrandomizowaną wymianą informacji. W każdym pokoleniu powstaje nowy zespół sztucznych organizmów (ciągów bitowych), utworzonych z połączenia fragmentów najlepiej przystosowanych przedstawicieli poprzedniego pokolenia. Oprócz tego mogą sporadycznie zostać wprowadzane do kolejnych pokoleń nowe osobniki. Początkowa populacja zostaje utworzona w sposób losowy.

„Algorytmy genetyczne odwzorowują naturalne procesy ewolucji zachodzącej w czasie, których celem jest maksymalne dopasowanie osobników do istniejących warunków życia.”

Rys.1 Ogólny schemat algorytmu genetycznego.

Algorytm genetyczny operuje na populacji jednostek:

gdzie: n jest numerem generacji, natomiast R oznacza rozmiar populacji
.

Każda jednostka
w zależności od problemu może być wyrażona dowolną, często skomplikowaną strukturą. Reprezentuje ona potencjalne rozwiązanie, posiadające pewną miarę swojej wartości, wyliczaną przy pomocy funkcji dopasowania (fitness function). Po obliczeniu tej miary dla każdej jednostki w populacji tworzona jest nowa generacja. Odbywa się to poprzez eliminację jednostek o najniższej wartości funkcji dopasowania, pozostawienie jednostek o wartości pośredniej oraz promowanie tych z najwyższą wartością. Taki schemat postępowania za końcowy rezultat uznaje najlepszą jednostkę z pierwszej generacji. Algorytmy genetyczne uwzględniają dodatkowo możliwość doskonalenia rozwiązań. Osiągają to dzięki zastosowaniu operatorów genetycznych: krzyżowania i mutacji.

• krzyżowanie: tworzy dwie nowe jednostki poprzez wymieszanie informacji z dwóch jednostek rodzicielskich

• mutacja: modyfikuje jednostkę poprzez losową zmianę pewnej części jej informacji

Operatory genetyczne modyfikują tylko jednostki o najwyższej wartości funkcji dopasowania. Należy podkreślić, że klasyczne algorytmy genetyczne w żaden sposób nie wykorzystują wiedzy o rozwiązywanym problemie. To, że znajdują rozwiązanie wynika z faktu, że do każdej następnej generacji przedostają się lepsze jednostki z generacji poprzedniej, a operatory genetyczne wymieniają informacje zawarte w tych jednostkach tworząc nowe, potencjalnie doskonalsze rozwiązania. Proces tworzenia nowej populacji przedstawiony jest na poniższym rysunku.

Proces rozwiązywania problemu można znacznie przyspieszyć wykorzystując wiedzę o problemie, przy określaniu struktury jednostki i konstruowaniu operatorów genetycznych.

1.1 Zalety algorytmów genetycznych:

- jedyną informacją potrzebną do działania jest wartość funkcji celu,
- praca na populacji dopuszczalnych (potencjalnych) rozwiązań,
- poszukiwanie wielokierunkowe,

1.2 Wady algorytmów genetycznych:

- stosunkowo wolne obliczenia,
- trudności z precyzyjnym odnalezieniem optimum.

1.3 Algorytm genetyczny musi posiadać następujące elementy:

- Podstawową reprezentację zmiennych,
- Sposób tworzenia reprezentacji początkowej (często losowy),
- Funkcja przystosowania oceniająca rozwiązania (funkcja celu),
- Podstawowe operatory genetyczne, które można wykonać na chromosomach np. krzyżowanie i mutacja,
- Wartości różnych parametrów (rozmiar populacji, prawdopodobieństwo działania operatorów, prawdopodobieństwo krzyżowania, mutacji, itp.

1.4 Najczęściej działanie algorytmu przebiega następująco:

1. Losowana jest pewna populacja początkowa.

2. Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą udział w procesie reprodukcji.

3. Genotypy wybranych osobników poddawane są operatorom ewolucyjnym: są sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie), przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.

4. Rodzi się drugie (kolejne) pokolenie i algorytm powraca do kroku drugiego, jeżeli nie znaleziono dostatecznie dobrego rozwiązania. W przeciwnym wypadku uzyskujemy wynik.

1. Działanie algorytmu genetycznego obejmuje kilka zagadnień potrzebnych do ustalenia:

1. ustalenie genomu jako reprezentanta wyniku

2. ustalenie funkcji przystosowania/dopasowania

3. ustalenie operatorów przeszukiwania

5. Zastosowanie algorytmów genetycznych.

Algorytmy genetyczne znalazły zastosowanie do rozwiązywania problemów optymalizacji, w tym również NP-trudnych problemów optymalizacji kombinatorycznej, przewidywania ruchów na giełdzie, rozpoznawania obrazów, tworzenia grafiki oraz projektowania budynków i maszyn. Nie mniej jednak rozwój nauki i techniki z pewnością wykorzysta je w wielu nowych dziedzinach.

2. Historia i istota problemu ośmiu hetmanów.

Problem ośmiu hetmanów został po raz pierwszy sformułowany w 1848 roku przez mistrza szachowego nazwiskiem Max Bezzel (1824-1871). Prawidłowa odpowiedź została określona dwa lata później przez Franza Naucka. Również matematyk Carl Friedrich Gauss interesował się tym problemem, jednak nie on jako pierwszy. W roku 1992 wskazano na związki pomiędzy problemem ośmiu hetmanów a kwadratami magicznymi.

Królowa, zwana hetmanem, ustawiona na szachownicy atakuje wszystkie pola w poziomie, w pionie i po skosie - ustawiona w polu [1, 1] atakuje łącznie 21 pól szachownicy. Jeśli w jednej kolumnie ustawimy dwa hetmany, to siłą rzeczy muszą się wzajemnie atakować. Wniosek stąd płynący jest taki, że na standardowej szachownicy o wymiarach 8 x 8 nie można ustawić więcej niż 8 hetmanów. Odpowiedź na pytanie czy można ustawić 8 jest pozytywna i znana od dawna, zwłaszcza że jest to zadanie wykonalne metodą prób i błędów, można popróbować, powinno zająć kilka (lub kilkanaście) minut.
Ale wcale nie jest to odpowiedź oczywista, bo na przykład na szachownicy o wymiarach 3 x 3 nie ustawimy w żaden sposób nie atakujących się 3 hetmanów, na szachownicy 4 x 4 można ustawić 4 nieatakujące się hetmany na dwa sposoby. W jaki sposób rozstawić osiem hetmanów na tradycyjnej szachownicy 8x8 tak, aby wzajemnie się nie atakowały? Ile jest możliwych rozstawień? Przez rozstawienie podstawowe bądź rozwiązanie podstawowe należy rozumieć rozwiązanie z dokładnością do izomorfizmu , tzn. z uwzględnieniem wszystkich pokrewnych pozycji wynikających z przekształceń o charakterze symetrii i obrotów.

3. Przykładowe rozwiązanie problemu.

Hetmany ustawione na polach [x, y] i [x^', y^'] atakują się gdy:

• stoją w tym samym wierszu, tzn. gdy x = x^',

• stoją w tej samej kolumnie, tzn. gdy y = y^',

• stoją w tej samej linii po skosie, tzn. gdy |x-x^'| = |y-y^'|

W przełożeniu na Pascal funkcję o wartościach logicznych zwracająca prawdę, gdy dwa hetmany atakują się może być zdefiniowana tak:

Function AtakujaSie(x1, y1, x2, y2 : ShortInt) : Boolean;

Begin

If (x1=x2) Or (y1=y2) Or (Abs(x1-x2)=Abs(y1-y2)) Then AtakujaSie:=True

Else AtakujaSie:=False;

End;

Do zapamiętania ustawienia 8 hetmanów wystarczy zwykła tablica 8 bajtów - tutaj ShortInt, tylko dla zgodności z powyższą funkcją:

Type

Rozmiar = 8;

Szachownica = Array[1..Rozmiar] Of ShortInt;

Poszczególne komórki tej tablicy są odpowiednikami wierszy szachownicy - odpowiednikiem kolumny będzie liczba zapisana w odpowiedniej komórce - jeśli na szachownicy ustawimy hetmana na polu [x, y], to do tablicy tej w komórkę S[x] wpiszemy wartość kolumny, czyli y:

(x, y) = (x, S[x])

Algorytm ustawiający hetmany na szachownicy jest przykładem rekurencji z powrotami. Ustawiamy kolejno hetmana w wierszu pierwszym, drugim, itd. aż do ósmego, zawsze wybierając pierwszą wolną komórkę w wierszu - wolną, to znaczy taką, aby ustawiony na niej hetman nie atakował się z żadnym z ustawionych już hetmanów w wierszach o niższych numerach. Funkcja sprawdzająca czy komórka [x, y] jest wolna:

Function Wolna(x, y : ShortInt) : Boolean;

Var

wiersz : ShortInt;

Begin

Wolna:=False;

For wiersz:=1 To x-1 Do

If AtakujaSie(wiersz, S[wiersz], x, y) Then Exit;

Wolna:=True;

End;

Do przykładowego programu, który wypisze wszystkie możliwe ustawienia i poda ich ilość potrzebna jest jeszcze procedura wypisująca poprawne ustawienie:

Var

S : Szachownica;

Ilosc : LongInt;

Procedure Wypisz;

Var

wiersz, kolumna : ShortInt;

Begin

For wiersz:=1 To Rozmiar Do

Begin

For kolumna:=1 To Rozmiar Do

If kolumna=S[wiersz] Then Write('x':2)

Else Write('*':2);

WriteLn;

End;

WriteLn;

Ilosc:=Ilosc+1;

WriteLn('Ustawienie numer = ', Ilosc);

End;

Argumentem rekurencyjnej procedury ustawiającej hetmany na szachownicy jest numer wiersza, w którym należy ustawić kolejnego hetmana - jeżeli nie jest to wiersz ostatni, to ustawieniu należy ustawić kolejnego w wierszu wiersz + 1, jeśli ustawiony został poprawnie hetman w ostatnim wierszu, to wypisujemy znalezione ustawienie. Na szachownicy o wymiarach 10 x 10 można ustawić 10 hetmanów na 724 sposoby.

Procedure Ustaw(wiersz : ShortInt);

Var

kolumna : ShortInt;

Begin

For kolumna:=1 To Rozmiar Do

If Wolna(wiersz, kolumna) Then

Begin

S[wiersz]:=kolumna;

If wiersz<Rozmiar Then Ustaw(wiersz+1)

Else Wypisz;

End;

End;

Begin

Ilosc:=0;

Ustaw(1);

ReadLn;

End.

* * * * * * * * * x

* * * * * * * x * *

* * * * x * * * * *

* x * * * * * * * *

* * * x * * * * * *

x * * * * * * * * *

* * * * * * x * * *

* * * * * * * * x *

* * * * * x * * * *

* * x * * * * * * *

Ustawienie numer = 723

* * * * * * * * * x

* * * * * * * x * *

* * * * x * * * * *

* * x * * * * * * *

x * * * * * * * * *

* * * * * x * * * *

* x * * * * * * * *

* * * * * * * * x *

* * * * * * x * * *

* * * x * * * * * *

Ustawienie numer = 724

4. Podsumowanie.

Niestety algorytmy genetyczne są tylko heurystyką. Oznacza to, że otrzymane rozwiązania nie zawsze będą najlepszymi możliwymi. W zamian za to otrzymujemy rozwiązania bardzo dobre w rozsądnym czasie. W zasadzie algorytm genetyczny powinien działać w nieskończoność (chyba że zadanie lub problem ma konkretny wynik lub rozwiązanie - problem ośmiu hetmanów) jednak dobrze jest zapewnić jakieś rozsądne wyjście z pętli. Może to być np. pewna liczba iteracji, wartość osiągniętego najlepszego rozwiązania, czas, brak poprawy wyniku przez pewną ilość iteracji lub inne w zależności od rodzaju zadania. Wiele problemów związanych z codziennym życiem to problemy NP-trudne. Przykłady to znajdowanie najkrótszej trasy łączącej pewną liczbę miast i optymalne pakowanie plecaka. Oznacza to, że szybkie algorytmy mogą radzić sobie w takimi problemami tylko w przybliżeniu lub w bardzo szczególnej sytuacji. Sterowany algorytmem przybliżonym robot nie potrafi odnaleźć najkrótszej drogi w bardzo złożonym środowisku, mimo że dla człowieka może być ona oczywista.

Inżynierowie próbują rozwiązywać problemy NP-trudne przez naśladowanie żywych organizmów. Jeżeli nie da się sformułować jasnego algorytmu rozwiązującego dany problem, można maszynę wyposażyć w zdolność do samodzielnego uczenia się. Zagadnieniem tym zajmuje się dział określany jako sztuczna inteligencja. Tego podejścia nie należy mylić z ludzką inteligencją. Maszyny naśladują tylko pewne cechy istot żywych, ale jak na razie nie są w stanie im dorównać na wielu polach mimo iż moc obliczeniowa układów scalonych rośnie. Jednak postęp jaki dokonuje się w tej dziedzinie nauki jest już ogromny, i kto wie co pokaże przyszłość .

Bibliografiia.

• 1. O dokonywaniu wynalazków drogą ewolucji. John R. Koza, A. Keane, Mattethew J. Streeter;

• 2. Świat nauki; nr 4 (140), s. 40-47 Kwiecień 2003

• 3. Algorytmy genetyczne i ich zastosowania D. E. Goldberg; WNT, Warszawa, 1998

• 4. Algorytmy genetyczne + struktury danych = programy ewolucyjne Z. Michalewicz; WNT, Warszawa, 1996

• 5. Wykłady z algorytmów ewolucyjnych J. Arabas; WNT, Warszawa, 2001

• 6. Sieć Internet, Encyklopedie: PWN, WIKIPEDIA, HELIONICA.
  
  

„Kwadrat magiczny to tablica liczb składająca się z n wierszy i n kolumn (n>2), w którą wpisano n² różnych liczb naturalnych w ten sposób, że suma liczb w każdym wierszu, w każdej kolumnie i w każdej przekątnej jest taka sama (tzw. suma magiczna). Z matematycznego punktu widzenia to macierz kwadratowa, w której suma liczb w kolumnach, wierszach i obu przekątnych jest taka sama.” - artykuł ze strony : http://pl.wikipedia.org/wiki/Kwadrat_magiczny_%28matematyka%29

Izomorfizm (gr. isos - równy, morphe - kształt) - wzajemnie jednoznaczne przekształcenie jednego uniwersum w inne zachowujące jego strukturę i/lub operacje, np. zbiory, funkcje, relacje itp. - definicja ze strony : http://pl.wikipedia.org/wiki/Izomorfizm

str. 11

---