poniedziałek, 2 lutego 2015

Własna implementacja algorytmu ewolucyjnego (1+1)

      Istota tego algorytmu czy na czym on polega to materiał na dłuuugi wykład. Jeśli ktoś jest nią zainteresowany na pewno korzystając z wujaszka Google znajdzie przydatne informacje i mnóstwo teorii.
      Do sedna. Celem algorytmu, który stworzyłem jest znalezienie minimum funkcji zaprezentowanej poniżej, w jak najkrótszym czasie.

  
Rys 1.1 Wykres badanej funkcji

    Zaprezentowana tutaj funkcja (a dokładniej jej wykres) nie jest funkcją wielomodalną ( czyli posida mało extremów, czyli minimum i maksimum). Dlatego też znalezienie najmniejszej wartości tej funkcji dla algorytmu, który przedstawie nie jest zbyt dużym problemem. Całą implementację wykonałem w Matlabie. Potężne narzędzie dzięki któremu zacząłem interesować się programowaniem. 


Cały kod zaprezentuje na samym końcu zacznę od wyników jego działania.  Po wykonaniu program otrzymujemy trzy wykresy. Pierwszy z nich został wam już zaprezentowany na Rys 1.1, a oto pozostałe dwa:

 Rys. 1.2 Wartości "punktów" w danym przebiegu pętli

Rys. 1.3 Wartość funkcji w danym przebiegu pętli


    Rys. 1.2  Przedstawia wartości punktów w przebiegu pętli. Jednak muszę wprowadzić tu trochę teorii. Generalnie algorytmy te inspirowane są biologicznie. Prościej mówiąc sytuacjami zaobserwowanymi u zwierząt roślin itd. Dlatego też nazewnictwo znane z programowania jest tu trochę inne. 
Mianowicie dwa najważniejsze pojęcia to:
-przebieg pętli  oznacza pokolenie
-wartość punktu oznacza osobnika ( poprawnie pisząc ze punktu matematycznego wartość osobnika).
     Zaczynając od pierwszego pokolenia (pierwszej iteracji pętli) istnieją dwa osobniki ( dwie wartości punktów) których wartości wstawiamy do wzoru na funkcję ( w prezentowanym przykładzie jest to wzór   Z= ∑  x^2+ y^2 czyli suma kolejnych kwadratów liczb). I tak dla kolejnych pokoleń zmieniamy wartości osobników o losowe wartości (epsilon) zapamiętując osobniki dal których wartość Z była najmniejsza. Losowość epsilona nie jest taka całkowicie losowa. Jego wartość zależy od ilości udanych wyników im więcej udanych tym ta wartość się zmniejsza im mniej tym bardziej się zwiększa. Zastanawiacie się pewnie, co to znaczy udany wynik. Żeby to wytłumaczyć musimy wziąć dwa pokolenia i wartości uzyskanych Z. Jeśli wartość Z w drugim pokoleniu zmniejszyła się, co do wartości z pierwszego pokolenia oznacza to, że mamy udany wynik. W przeciwnym wypadku droga poszukiwań nie jest właściwa ( jest tylko tak jeśli poszukujemy minimum, sytuacja jest odwrotna jeśli poszukujemy maksimum ale nie mieszajmy). Wracając, co przedstawia Rys 1.2, chyba już wiecie, a ja tylko potwierdzę wasze domysły. Są to wartości osobników (punktów) wstawiane do wzoru funkcji w każdym pokoleniu (iteracji pętli). Zaś Rys. 1.3 prezentuje wartości Z w każdym pokoleniu.
W okienku Command Window (czyli takiej matlabowskiej konsoli również pojawiają nam się komunikaty. Podczas działania programu widzimy napis :

Już liczę poczekaj chwileczkę

 Po ukończonych obliczeniach dostajemy wartości liczbowe :

minimum funkcji można spodziewać się w okolicach:
    0.0010

  -3.4777e-04

Gdzie wartość funkcji wynosi
   1.1495e-06

Warto nadmienić,że powyższe wyniki są zbieżne (nie można ich traktować jako te, które są rozwiązaniem problemu ale jako takie, które wokół tego rozwiązania oscylują). Jednak na podstawie wielu prób udaje się niektóre algorytmy "dostroić" aby podawały dokładne rozwiązanie. 

     Pora na wisienkę na torcie czyli kod programu znajdziecie pod poniższym linkiem.



   
  





Brak komentarzy:

Prześlij komentarz