1 Wprowadzenie i trochę historii Algorytmy genetyczne służą do rozwiązywania problemów w sposób naśladujący pewne procesy zachodzące w przyrodzie; dokładniej procesy doboru naturalnego. Możemy bowiem wyobrazić sobie ewolucję jako algorytm stale optymalizujący pewną funkcję - miarę przystosowania. Tak jak przyroda doprowadza do wytworzenia się organizmów jak najlepiej funkcjonujących w ekosystemie, tak my, rozwiązując problem, staramy się znaleźć jego możliwie optymalne rozwiązania. Przyroda nie tworzy jednak organizmów idealnych. Podobnie algorytmy genetyczne służą do poszukiwania wyników jedynie przybliżonych. Tego typu metody są jednak niezwykle przydatne w praktyce. Mając do rozwiązania trudny obliczeniowo problem (tzn. taki, dla którego nie jesteśmy w stanie skonstruować algorytmu, który dawałby dokładne rozwiązania po rozsądnym czasie działania) w zupełności zadowolimy się rozwiązaniem, o którym wiemy, że niewiele różni się ono od optymalnego. W pewnym uproszczeniu możemy przyjąć, że algorytm genetyczne służą do optymalizacji pewnych funkcji (zwanych funkcjami przystosowania). Zauważmy jednak, że klasa ich zastosowań jest dużo szersza: AG możemy stosować przy dowolnych problemach, dla których uda się skonstruować funkcję oceniającą rozwiązania. W tym ujęciu wiele problemów można przeformułować w ten sposób, aby stały się zadaniami optymalizacyjnymi. Za początek algorytmów genetycznych przyjmuje się prace biologów (Barricelli 1957, Fraser 1960). Symulowali oni procesy genetyczne przy pomocy komputerów. Chociaż nie myślano wtedy o zastosowaniu tych symulacji do rozwiązywania problemów matematycznych, nie były one zbyt odległe od współczesnego rozumienia AG. Podwaliny pod zastosowania algorytmów genetycznych w zagadnieniach sztucznej adaptacji położył Holland podczas prac nad systemami adaptacyjnymi w roku 1962. Od tej pory zaczęto używać algorytmów genetycznych w coraz szerszej klasie zastosowań. W 1967 opracowano algorytm genetyczny grający w prostą grę logiczną (Bagley). W 1970 zastosowano je do systemu rozpoznającego postacie ludzkie (przykład problemu nierozwiązywalnego tradycyjnymi metodami). W 1971 pojawiła się pierwsza praca badająca skuteczność AG do optymalizacji funkcji (Hollstein). Do dziś, AG znalazły setki nowych zastosowań.