Algorytmy ewolucyjne (ang. Evolutionary Algorithms), w skrócie AE, są próbą wykorzystania znanych z natury mechanizmów ewolucji do rozwiązywania problemów optymalizacyjnych. Pierwszym wyraźnym podobieństwem AE do ewolucji naturalnej jest istnienie populacji – w przyrodzie rozumianej jako zbiór współistniejących osobników różnych gatunków, w AE jako zbiór różnych możliwych rozwiązań problemu. To, co nazywamy ewolucją, jest niczym innym jak powstawaniem gatunków coraz lepiej dopasowanych do środowiska oraz zanikaniem tych dopasowanych najgorzej. Analogia AE do mechanizmów natury jest prosta: jeśli przyjąć, że osobnikom odpowiadają różne rozwiązania danego problemu, oraz ustalić pewną miarę ich dopasowania (tzw. funkcja oceny), to przy użyciu odpowiednich metod generowania nowych rozwiązań można wyewoluować populację składającą się z rozwiązań "dobrych", czyli preferowanych przez funkcję oceny.
Jakież to metody generowania używamy? I tutaj AE wzoruje się na przyrodzie. Rozwiązania traktuje się tak jak genotypy organizmów, a te jak wiadomo w połączeniu z operacjami krzyżowania oraz mutacji stanowią istotę działania ewolucji. Dla przypomnienia: krzyżowanie polega na przekazaniu potomkowi fragmentów genotypu pochodzących od obojga rodziców, mutacja natomiast na losowej zmianie nowego genotypu. Od krzyżowania oczekujemy, że pojawi się potomstwo posiadające dobre cechy obojga rodziców, a od mutacji, że pozwoli nam odkryć dobre, nieznane dotąd cechy. Oczywiście na jednokrotnej generacji potomstwa działanie AE się nie kończy. Proces ten jest powtarzany wiele razy, a żeby powtarzalność ta miała sens, potrzebny jest jeszcze jeden mechanizm – selekcji, który odpowiada selekcji naturalnej. Działa on następująco: populację poddaje się ocenie; dalej, w pewien sposób powiela się osobniki z populacji bieżącej do nowej w taki sposób, żeby większe szanse na skopiowanie miały osobniki dobre (prosta analogia – silny wygrywa, słaby wymiera). Krzyżowanie i mutację przeprowadza się na tak otrzymanej populacji. Krzyżowanie, w połączeniu z selekcją preferującą dobre osobniki, powoduje ujednolicanie populacji, czemu z kolei przeciwdziała mutacja. Intensywność tych operacji powinna być zatem wzajemnie wyważona. Schemat AE można naszkicować następująco:
Wygeneruj populację startową (np. wylosuj genotypy).
Powtarzaj do wystąpienia warunku stopu (np. wystarczająca jakość rozwiązań, ilość powtórzeń):
Wybierz najlepsze osobniki (selekcja).
Dokonaj krzyżowania pośród wybranych osobników (z określonym prawdopodobieństwem, lub przy zadanej liczności par).
Dokonaj mutacji (z okreslonym prawdopodobieństwem).
Odrzuć najgorsze osobniki, zastępując je potomstwem.
Algorytmy ewolucyjne są szczególnie przydatne w rozwiązywaniu problemów NP-trudnych (dla takich problemów czas rozwiązywania algorytmem sprawdzającym wszystkie możliwości rośnie wykładniczo ze wzrostem rozmiaru instancji problemu).
