Algorytmy genetyczne doskonale nadają się do rozwiązywania tzw. problemów optymalizacyjnych, czyli takich, w których istnieje wiele permutacji możliwości. Oznacza to, że w ich przypadku istnieje wiele prawidłowych rozwiązań, przy czym jedne są lepsze od drugich. Jak można je wykorzystać w praktyce?
Czym jest algorytm genetyczny?
Algorytm genetyczny jest bardzo ciekawą metodą wyszukiwania rozwiązania, która opiera się o teorię doboru naturalnego oraz biologii ewolucyjnej. Wykorzystuje się go w sztucznej inteligencji i w informatyce. Można się oczywiście zastanawiać co wspólnego może mieć teoria ewolucji z algorytmami sztucznej inteligencji, ale wbrew pozorom związek jest bardzo logiczny.
Zacznijmy od tego, że wbrew powszechnemu wyobrażeniu teoria ewolucji oparta na doborze naturalnym zaproponowana przez Karola Darwina, nie jest procesem liniowym, lecz procesem zupełnie chaotycznym, dzięki czemu możliwe jest tworzenie nowych form życia. Takich, które lepiej radzą sobie z wykonywaniem zadań w określonym środowisku. Oznacza to też, że powstają formy życia, które z tymi zadaniami radzą sobie znacznie gorzej i dlatego zostają w naturalny sposób wyparte i wyeliminowane. Prawda ta stała się inspiracją do opracowania tzw. algorytmów ewolucyjnych. To właśnie one pozwalają na szukanie rozwiązań praktycznych problemów, poprzez generowanie różnych wariantów i wybór najskuteczniejszego z nich.
źródło: shutterstock.com
Dzięki temu z pomocą algorytmów genetycznych można skutecznie przeszukiwać obszerne i bardzo złożone zestawy danych, przy czym otrzymywane rozwiązania danego problemu są oceniane z uwzględnieniem kryterium jakości. Warto jednak zauważyć, że algorytm genetyczny nie sprawdzi się tam, gdzie wymagane jest jedno poprawne rozwiązanie, a nie takie, które określa się mianem akceptowalnego, pożądanego i dość dobrego.
Działanie algorytmu genetycznego doskonale obrazuje jeden z najczęściej poruszanych problemów optymalizacyjnych, czyli problem plecakowy. Najprościej mówiąc, chodzi o to, by do plecaka włożyć takie przedmioty z określonego zbioru rzeczy opisanych wagą i ceną, by ich sumaryczna wartość była jak największa, a jednocześnie by wybrane przedmioty określonej pojemności naszego plecaka. Ilość możliwości rośnie wraz z liczbą przedmiotów. Nie jest to jednak rozważanie teoretyczne, gdyż z klasycznym problemem plecakowym mamy do czynienia na przykład wtedy, gdy chcemy zoptymalizować załadunek ciężarówek albo wykorzystanie przestrzeni magazynowej.
Praktyczne zastosowanie znajduje także zagadnienie optymalizacyjne znane jako problem komiwojażera. Jego typowa ilustracja przedstawia wędrownego sprzedawcę, który musi odwiedzić określone miasta, korzystając z trasy możliwie najkrótszej, najtańszej i najszybszej. Algorytm genetyczny w tym wypadku może pomóc chociażby firmie logistycznej wyznaczyć optymalną trasę przejazdu ciężarówek pomiędzy wybranymi lokalizacjami.
Cykl życia algorytmu genetycznego
Kluczowe jest zastosowanie odpowiednich parametrów algorytmu, tak aby zacząć od znalezienia różnorodnych rozwiązań, o zróżnicowanych cechach i by stopniowo przejść do tzw. globalnie najlepszego rozwiązania. Umożliwia to cykl życia algorytmu genetycznego. Zatem najpierw tworzy się losową populację potencjalnych rozwiązań, następnie określa się jak dobre są wyszukane rozwiązania, co nazywamy pomiarem przystosowania jednostek w populacji. Kolejny krok to wybór par rodziców na postawie ustalonego przystosowania i tworzenie potomstwa poprzez mieszanie informacji genetycznej i wprowadzanie niewielkich mutacji. Dzięki temu można wygenerować populację następnego pokolenia. Na tym można zakończyć działanie algorytmu lub ponownie wybrać najlepsze pary rodziców z otrzymanego pokolenia i kontynuować kolejne kroki. Oczywiście konieczne jest też ustalenie warunków zakończenia pracy, kiedy to z otrzymanego pokolenia udaje się wyselekcjonować najlepsze rozwiązanie.
Tworząc prosty algorytm genetyczny musimy podjąć kilka istotnych decyzji dotyczących parametrów. Trzeba zatem przemyśleć metodę kodowania, określić wielkość populacji, wziąć pod uwagę inicjowanie populacji oraz skonfigurować liczbę potomków generowanych w każdym kolejnym pokoleniu. Istotne jest też określenie techniki wyboru rodzica oraz skonfigurowanie metody krzyżowania, współczynnika mutacji, metody wprowadzania mutacji i metody selekcji osobników w pokoleniu. Ostatni krok to określenie wspomnianych już warunków zatrzymania pracy algorytmu.
źródło: unsplash.com
Praktyczne zastosowania algorytmów genetycznych
Algorytm genetyczny w przypadkach, kiedy inne metody są mało efektywne lub całkowicie nieskuteczne. Zatem wykorzystywany jest w szeregowaniu zadań, w zakresie minimalizowania kosztów, tworzeniu harmonogramów pracy. Algorytm genetyczny sprawdza się też w modelowaniu finansowym, przy podejmowaniu decyzji czy też w opracowywaniu strategii inwestycyjnych. Można to wykorzystać do łamania szyfrów i kodów. Bardzo ważnym zastosowaniem jest też selekcja cech w uczeniu maszynowym.