Przykładowe wykorzystanie algorytmów ewolucyjnych, czyli jak napisać program, który za nas będzie pisał programy.
Trzy różne realizacje tej idei znajdziesz na tej stronie.
Programowanie genetyczne jest próbą stworzenia systemu, który wykorzystując mechanizmy algorytmów genetycznych, będzie tworzył programy komputerowe. Ogólny zarys algorytmu genetycznego jest taki sam jak np. przy znajdowaniu optymalnej ścieżki komiwojażera. Zmieniają się tylko poszczególne elementy składowe:
Populację w tym wypadku stanowią przykładowe programy komputerowe, z których każdy wykonuje jakieś działanie.
Krzyżowanie i mutacja tworzą nowe osobniki na podstawie już istniejących (nic się nie zmienia w porównaniu z typowym AG, należy jedynie pamiętać o zastosowaniu operatora odpowiedniego do reprezentacji)
Funkcja oceny ma zadecydować, czy dany program chociaż w przybliżeniu wykonuje te działania o które nam chodzi. Np. jeśli chcemy stworzyć program, który zawsze będzie znajdywał drogę wyjścia z labiryntu funkcja oceny będzie sprawdzała jak daleko 'zaszedł' dany program. Te programy, który znajdują poprawne wyjście otrzymują najwięcej punktów, natomiast te, które od wyjścia się oddalają otrzymują tych punktów najmniej.
Poniżej chciałbym przedstawić poszczególne elementy algorytmu:
Populacja – reprezentacja pojedynczego rozwiązania
W przypadku programowania genetycznego najczęściej stosowaną reprezentacją pojedynczego rozwiązania jest struktura drzewiasta. Jest ona bardzo wygodna z punktu widzenia krzyżowania i mutacji, a poza tym wymusza kolejność przechodzenia przez węzły i liście. Jest to reprezentacja o zmiennej długości ponieważ przykładowymi programami mogą być zarówno program wykonujący sumę dwóch argumentów jak i program obliczający pierwiastki równania kwadratowego.
Przykładowy program może wyglądać następująco:
Wynikiem działania każdego programu jest pewna wartość. Aby ją wyznaczyć należy drzewo przeglądać wstecznie (przed wykonaniem działania zapisanego w węźle należy najpierw obliczyć wyrażenia 'zaczepione' w jego dzieciach). Wartość zwracana przez powyższe drzewo jest określona wzorem: (X*((5.00+X)-((((X-X)-(X*X))+(1.00-2.00))+(7.00-(7.00-5.00)))))
Elementami takiego drzewa mogą być:
Jako węzły:
Operatory arytmetyczne (+,-,/,...)
Operatory logiczne (&&,||,!,...)
Operatory bitowe (&,|,~,...)
Porównania (>,<,==,...)
Funkcje (trygonometryczne, potęgowe,...)
Instrukcja warunkowa – IF (jeśli spełniony jest warunek (pierwszy argument), wykonywane jest poddrzewo drugiego argumentu, jeśli nie trzeciego)
Instrukcja iteracyjna – FOR (pierwszy argument podaje ile razy ma zostać wykonane poddrzewo drugiego argumentu)
Jako liście:
Wartości stałe, zmienno- lub stałoprzecinkowe (np.: 5, 10.5, -11)
Wartości zmiennych (np.: X)
Wywołania funkcji (np.: WczytajZnakZKlawiatury(), lub random())
Wywołania procedur (np.: printf(), clrscr()) – W przypadku procedur problemem jest zwracana przez nie wartość (każdy element drzewa musi coś zwracać swojemu rodzicowi) – najczęściej przyjmuje się, że procedury zwracają zero.
Populacja początkowa wypełniona jest programami wygenerowanym całkowicie losowo. Podczas losowania osobników dobrze jest zadbać o to, aby osobniki nie były zbyt 'rozrośnięte'. Można to zrobić ustalając maksymalną głębokość lub liczbę wierzchołków tworzonego drzewa.
Krzyżowanie
Krzyżowanie polega na wymianie pomiędzy dwoma osobnikami wybranych losowo poddrzew. Poniżej przedstawiony jest przykład krzyżowania (ramką zaznaczone zostały wymieniane poddrzewa): Sytuacja przed krzyżowaniem:
Pierwszy rodzic:
Drugi rodzic:
Sytuacja po krzyżowaniu:
Pierwsze dziecko:
Drugie dziecko:
Mutacja
Najczęściej stosowaną mutacją w przypadku programowania genetycznego jest usunięcie z osobnika losowego poddrzewa i na jego miejsce wygenerowanie nowego. Poniżej znajduje się przykład takiej mutacji (ramką zastało zaznaczone poddrzewo usuwane oraz dodawane):
Osobnik przed mutacją:
Osobnik po mutacji:
Innym sposobem mutacji jest zmiana operatora w dowolnym wierzchołku drzewa. Należy tutaj pamiętać, że jeśli nowy operator ma mniej argumentów niż oryginalny (max(a,b)->sin(a)) należy usunąć nadmiarowe poddrzewa. Jeśli natomiast nowy operator ma więcej argumentów (max(a,b)->if(a,b,c)) należy dogenerować brakujące poddrzewa.
Można również mutować liście w drzewie. Jest to najprostszy rodzaj mutacji (nie trzeba dodawać nowych, ani usuwać starych poddrzew), jednak powoduje niewielką zmianę działania programu jaki mutowany osobnik reprezentuje. Ten sposób mutacji przydaje się gdy rozwiązanie (osobnik, program) działa 'z grubsza' poprawnie a trzeba zmienić tylko jakieś współczynniki (np. zmiana liczby iteracji, próg do porównania dla instrukcji IF, itp.)
Funkcja oceny
Głównym zadaniem funkcji oceny jest sprawdzenie czy dany osobnik wykonuje taki program o jaki nam chodziło. W zależności od tego jak bardzo wyniki programu przypominają to o co nam chodziło osobnik dostaje odpowiednią liczbę punktów. Np dla rozwiązywania zadania aproksymacji funkcji funkcja oceny sprawdza jak daleko wygenerowana funkcja odbiega od punktów bazowych.
Do funkcji oceny warto jest dodać pewną karę za wielkość osobnika. Dzięki temu poszczególne osobniki nie będą się nadmiernie rozrastać. W przypadku drzewowej reprezentacji rozwiązania można wprowadzić karę za liczbę wierzchołków oraz karę za maksymalną głębokość drzewa.
Selekcja
Ta część algorytmu jest dokładnie taka sama jak w przypadku innych wykorzystań algorytmów genetycznych. Zarówno koło ruletki jak i metoda turniejowa bazują tylko na wartościach funkcji oceny (do działania nie potrzebują informacji o osobnikach).
Iteracyjne wykonywanie wszystkich kroków AG prowadzi do otrzymania programu (przynajmniej w przybliżeniu) rozwiązującego zadany problem. Niestety (na szczęście?) program wygenerowany dzięki programowaniu genetycznemu jest daleki od optymalnego (dlatego, póki co, programiści nie stracą pracy). Zaletą programowania genetycznego jest fakt, że tworzenie programu w ten sposób nie wymaga żadnych nakładów pracy ze strony programisty.
