Odkrywanie szczytów

Mówi się, że dzięki ewolucji następuje doskonalenie organizmów. Motorem tego doskonalenia jest presja, jaka jest wywierana przez środowisko oraz inne osobniki. Wyobraźmy sobie sytuację uproszczoną, gdzie mamy jedno stałe kryterium według którego oceniamy osobniki. Jeśli osobnik posiada tylko jedną cechę, możemy na osi poziomej nanieść jej wartości, a na osi pionowej - przystosowanie osobnika. Uzyskamy wykres dwuwymiarowy - na przykład o kształcie paraboli czy też linii prostej. A gdyby osobnik miał dwie cechy? Wtedy potrzebujemy trzech wymiarów.

Odkrywanie szczytów

Cały problem (nie tylko biologiczny, również informatyczny oraz ogólnie, w wielu dziedzinach w których poszukujemy najlepszych rozwiązań) tkwi w znalezieniu takich wartości cech, dla których wartość przystosowania jest najlepsza. Cóż zrobić, jeśli nie możemy systematycznie sprawdzić wszystkich kombinacji wartości tych cech, bo jest ich zbyt dużo? Służą temu specjalne algorytmy optymalizacji. Krajobaz przystosowania nie musi być jednak wcale tak prosty, jak powyżej. Może przecież przypominać obszar w którym trudno podążać w kierunku rosnącego przystosowania. Tymczasem przecież ciągle mówimy o uproszczeniu ewolucji biologicznej.

Program OptiVis demonstruje optymalizację lokalną (zastosowane zostały algorytmy: Greedy, Steepest oraz Symulowane wyżarzanie) jak również optymalizację globalną (zastosowano algorytm ewolucyjny). Program umożliwia optymalizację funkcji o maksymalnie 20 zmiennych, przy czym wizualizacja funkcji i optymalizacji przedstawiona jest na wykresie trójwymiarowym bądź dwuwymiarowym. Dostępne są przykładowe pliki z ciekawymi funkcjami. Poniżej, po lewej widać drogę algorytmu zachłannego szukającego minimum (najniższej doliny), a po prawej populację osobników-rozwiązań (żółte punkty) w ewolucyjnym poszukiwaniu maksimum.

Interfejs programu podzielony jest na pięć zakładek:

1. Function - pozwala na wprowadzenie funkcji do optymalizacji oraz jej zmiennych (opis rozpoznawanych funkcji składowych zawarty jest w okienku dostępnym w menu Help->Function parser help). Na zakładce tej określamy kierunek optymalizacji oraz mamy możliwość wyliczenia wartości funkcji używając wartości zmiennych z tabelki.
2. Chart – służy do wizualizacji wykresu funkcji oraz optymalizacji. Funkcja przedstawiona jest w postaci trójwymiarowej. Dwie zmienne wizualizowane możemy określić samemu – wartości pozostałych zmiennych są brane z tabelki definiującej funkcję. Wartości funkcji dodatkowo wizualizowane są przy pomocy kolorów. Kolor czerwony oznacza największe wartości funkcji, a kolor jasno niebieski wartości najmniejsze.
   Rozwiązanie obrazowane jest przy pomocy niebieskich kulek połączonych niebieską linią. W przypadku algorytmu genetycznego dodatkowo przy pomocy żółtych kulek obrazowane są osobniki populacji.
   Na zakładce tej mamy możliwość wyboru zmiennych wizualizowanych (oś X i oś Y) oraz zakresu wyświetlanego przedziału dla wybranych zmiennych (definiujemy osobno minimum oraz maksimum). Dostępne są tu także opcje wyświetlania wykresu oraz rozwiązania.
3. Solutions – zakładka zawiera tabelkę z rozwiązaniami wyliczonymi przez dany algorytm, przy czym ostatnie (najlepsze) rozwiązanie jest zawsze jako pierwsze. Rozwiązania te są wizualizowane w postaci niebieskich kulek na wykresie.
4. Local Alg. – zakładka umożliwia zdefiniowanie parametrów algorytmów lokalnych oraz czasu opóźnienia pomiędzy kolejnymi krokami algorytmów.
5. Genetic Alg. - zakładka umożliwia zdefiniowanie parametrów algorytmu genetycznego oraz czasu opóźnienia pomiędzy kolejnymi krokami algorytmu.

Możesz uruchomić nieco prostszą wersję programu bezpośrednio w przeglądarce wybierając odpowiedni język przyciskiem poniżej:

Udostępniamy program OptiVis (dla MS Windows) który pozwoli zapoznać się ze sposobem działania algorytmów optymalizacji - jest on spakowany jako archiwum ZIP. Właśnie ten program narysował widoczne tu krajobrazy przystosowania. Dla programistów dostępny jest kod źródłowy programu OptiVis (w licencji GNU GPL, dla Borland C++ Builder 6.0).

Program: Ireneusz Sawicz

Tekst: Maciej Komosiński, Ireneusz Sawicz

Prowadzący: Maciej Komosiński