Algorytm Ewolucyjny - implementacja C++
Algorytmy ewolucyjne to metoda optymalizacji inspirowana procesem ewolucji biologicznej. Znajdują szerokie zastosowanie w problemach, w których tradycyjne metody analityczne czy heurystyczne zawodzą ze względu na wysoką złożoność przestrzeni poszukiwań.
Jak działa algorytm ewolucyjny?
- Inicjalizacja populacji – na początku generuje się zestaw losowych rozwiązań problemu (tzw. populacja).
- Ocena rozwiązań – każde rozwiązanie jest oceniane według funkcji celu, która określa jego jakość.
- Selekcja – wybierane są najlepsze osobiniki (rozwiązania), które mają większe szanse na przetrwanie i reprodukcję.
- Krzyżowanie – wybrane rozwiązania łączą się, wymieniając informacje, co może prowadzić do lepszych rozwiązań.
- Mutacja – losowe zmiany w niektórych rozwiązaniach pozwalają uniknąć utknięcia w lokalnych minimach.
- Powtarzanie procesu – proces selekcji, krzyżowania i mutacji jest powtarzany przez wiele iteracji, aż osiągnięty zostanie limit iteracji algorytmu.
Przykład optymalizacji funkcji
W projekcie użyliśmy algorytmu ewolucyjnego do optymalizacji funkcji Rosenbrocka, Salomona i Whitleya. Posiadają one liczne minima lokalne. Pomaga to sprawdzić, czy algorytm potrafi unikać "pułapek" i znajdować rozwiązanie globalne. Eksperymenty były przeprowadzane w przestrzeni 2-wymiarowej do potwierdzenia prawidłowej implementacji funkcji testowych oraz w przestrzeniach 5-, 15- i 30-wymiarowych, analizując skuteczność algorytmu w różnych warunkach.
Wykresy ECDF
ECDF (Empirical Cumulative Distribution Function) to empiryczna funkcja dystrybuanty, która przedstawia rozkład danych w sposób skumulowany. Wykresy ECDF w naszym przypadku pokazują, jak wiele eksperymentów algorytmu było potrzebnych do osiągnięcia danego poziomu dokładności.
Wyniki eksperymentów
Eksperymenty pokazały, że algorytm skutecznie znajduje optymalne wartości funkcji testowych, a proces ewolucyjny pozwala na stopniowe przybliżanie się do najlepszego rozwiązania. Szczegółowe wyniki znajdują się w raportach eksperymentów.
Kod oraz wykresy zostaną opublikowane wkrótce. Potrzebne jest kilka poprawek :)