Przejdź do treści
Wróć do wyników wyszukiwania

Algorytm genetyczny — optymalizacja ewolucyjna

Autor metody
John Henry Holland
Rok
1975
Typ
Population-based metaheuristic

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Algorytm genetyczny (GA) to metaheurystyczna metoda optymalizacji oparta na populacji, wprowadzona przez Johna Henry'ego Hollanda (1975), która naśladuje zasady doboru naturalnego.

Utrzymuje populację kandydatów na rozwiązania i iteracyjnie je ulepsza za pomocą operatorów selekcji, krzyżowania i mutacji, co czyni go szczególnie skutecznym w przestrzeniach poszukiwań nieciągłych, niewypukłych i wielomodalnych, gdzie klasyczne metody oparte na gradiencie zawodzą.

Intuicja stojąca za metodą

Wyobraźmy sobie, że mamy tysiące możliwych odpowiedzi na trudny problem i żadnego wzoru na znalezienie najlepszej. Algorytm genetyczny traktuje każdą potencjalną odpowiedź jako osobnika w populacji. W każdym pokoleniu zachowuje najsilniejszych osobników, krzyżuje ich, aby połączyć ich dobre cechy, i okazjonalnie mutuje potomstwo, aby wprowadzić nowość. Przez wiele pokoleń populacja dryfuje w kierunku coraz lepszych rozwiązań — nie przez podążanie za gradientem, ale przez naśladowanie sposobu, w jaki ewolucja kształtuje organizmy w czasie.

Historia

Algorytm genetyczny został wprowadzony przez Johna Henry'ego Hollanda w jego książce z 1975 roku Adaptation in Natural and Artificial Systems, która sformalizowała pojęcie schematu (elementu składowego) i dostarczyła podstawowej analizy teoretycznej, dlaczego krzyżowanie i selekcja napędzają poszukiwania w kierunku bardziej przystosowanych regionów. Studenci Hollanda — w szczególności David Goldberg — spopularyzowali GA poprzez zastosowania inżynieryjne w latach 80. XX wieku. Kalyanmoy Deb później rozszerzył ramy na ustawienia wielokryterialne, co doprowadziło do szeroko przyjętego algorytmu NSGA-II (2002). Obecnie GA pozostają standardowym narzędziem w obliczeniach ewolucyjnych, z aktywnymi badaniami nad metodami hybrydowymi, które łączą poszukiwania ewolucyjne z lokalnym udoskonalaniem.

Kiedy stosować

Algorytmy genetyczne są odpowiednie, gdy przestrzeń poszukiwań jest duża, nieciągła, niedyferencjowalna lub silnie wielomodalna — warunki, w których solwery oparte na gradiencie nie mogą działać lub utkną w lokalnych optimach. Mają zastosowanie do zmiennych ciągłych, kategorycznych, binarnych i porządkowych i nie nakładają żadnych założeń dotyczących normalności lub rozkładu. Jedynym wymogiem jest obliczalna funkcja przystosowania. W przypadku problemów, dla których istnieje analityczne lub wypukłe sformułowanie, metody klasyczne (programowanie liniowe, spadek gradientowy) są szybsze i powinny być preferowane. Wymagane są wystarczające iteracje (zazwyczaj znacznie powyżej 1000 pokoleń) dla znaczącej zbieżności; zbyt mała liczba pokoleń jest najczęstszym trybem awarii.

Ograniczenia i uwagi

  • Brak gwarancji zbieżności do globalnego optimum; wyniki mogą się różnić w zależności od uruchomienia.
  • Kosztowne obliczeniowo: każde pokolenie wymaga oceny całej populacji, co jest niewykonalne, gdy funkcja przystosowania jest powolna.
  • Wydajność jest wrażliwa na wybór hiperparametrów — wielkość populacji, prawdopodobieństwo krzyżowania i wskaźnik mutacji — które często wymagają dostrajania specyficznego dla problemu.
  • W przypadku problemów gładkich, wypukłych lub dobrze ustrukturyzowanych, klasyczne metody oparte na gradiencie lub metody liniowe będą szybsze i bardziej niezawodne.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Działa na nieciągłych, niedyferencjowalnych i wielomodalnych krajobrazach celu, gdzie metody oparte na gradiencie zawodzą.
  • Nie nakłada żadnych założeń dotyczących rozkładu — jedynym wymaganym wejściem jest obliczalna funkcja przystosowania.
  • Naturalnie obsługuje szeroki zakres typów zmiennych: ciągłych, binarnych, kategorycznych i porządkowych.
  • Różnorodność populacji pozwala na jednoczesne eksplorowanie wielu regionów przestrzeni poszukiwań, zmniejszając ryzyko przedwczesnego utknięcia w lokalnym optimum.
  • Wysoce rozszerzalne: specyficzne dla dziedziny operatory krzyżowania i mutacji, obsługa ograniczeń i warianty wielokryterialne (np. NSGA-II) są dobrze ugruntowane w literaturze.

Zastosowania

  • Optymalizacja projektowania inżynieryjnego: znajdowanie optymalnych konfiguracji parametrów dla struktur, obwodów lub systemów mechanicznych.
  • Problemy harmonogramowania i trasowania: harmonogramowanie produkcji, trasowanie pojazdów i tworzenie rozkładów jazdy, gdzie kombinatoryczna przestrzeń poszukiwań jest zbyt duża dla przeszukiwania wyczerpującego.
  • Uczenie maszynowe: dostrajanie hiperparametrów, wyszukiwanie architektury sieci neuronowych i selekcja cech.
  • Badania operacyjne: optymalizacja łańcucha dostaw, alokacja portfela i przypisanie zasobów w ramach złożonych ograniczeń.
  • Bioinformatyka: dopasowywanie sekwencji, przewidywanie struktury białek i wnioskowanie o sieciach regulacji genów.

Jak to działa

Jak to działa

1

Tworzona jest populacja kandydatów na rozwiązania (osobników), zazwyczaj losowo w przestrzeni poszukiwań. Każdy osobnik koduje potencjalne rozwiązanie — na przykład jako ciąg binarny, wektor wartości rzeczywistych lub permutację — a wielkość populacji jest kluczowym parametrem, który określa, jak szeroko przestrzeń poszukiwań jest próbkowana od samego początku.

2

Każdy osobnik w populacji jest oceniany przez funkcję przystosowania (fitness function), która kwantyfikuje, jak dobre jest dane rozwiązanie w odniesieniu do celu problemu. Funkcja przystosowania jest jedynym specyficznym dla dziedziny składnikiem, który musi dostarczyć użytkownik; może to być dowolna mierzalna wielkość — wynik symulacji, wzór kosztu lub metryka błędu modelu.

3

Osobniki o wyższym przystosowaniu są preferencyjnie wybierane na rodziców dla następnego pokolenia. Powszechne mechanizmy selekcji obejmują selekcję turniejową, selekcję kołem ruletki (proporcjonalną do przystosowania) i selekcję opartą na rangach. Presja selekcyjna kontroluje kompromis między wykorzystaniem wysokiej jakości rozwiązań a utrzymaniem różnorodności populacji.

4

Wybrani rodzice produkują potomstwo poprzez krzyżowanie (rekombinację), gdzie segmenty kodowań dwóch rodziców są łączone w celu utworzenia nowego osobnika, oraz poprzez mutację, gdzie małe losowe zmiany są stosowane do poszczególnych genów. Prawdopodobieństwo krzyżowania i wskaźnik mutacji są krytycznymi parametrami dostrajania: zbyt mało mutacji powoduje przedwczesną zbieżność, zbyt dużo zamienia poszukiwania w losowy spacer.

5

Pętla ocena → selekcja → reprodukcja trwa przez określoną liczbę pokoleń lub do momentu spełnienia kryterium zbieżności (np. brak poprawy przez pewien okres). Najlepszy osobnik znaleziony we wszystkich pokoleniach jest zwracany jako rozwiązanie. Ponieważ zbieżność do globalnego optimum nie jest gwarantowana, zaleca się wielokrotne niezależne uruchomienia dla problemów o wysokiej stawce.

Częste pułapki

  • Uruchomienie zbyt małej liczby pokoleń jest najczęstszym błędem: przy niewystarczającej liczbie pokoleń algorytm nie zbiega, dlatego metody analityczne lub oparte na gradiencie powinny być preferowane, gdy dostępny jest tylko mały budżet iteracji.
  • Przedwczesna zbieżność — utrata różnorodności populacji zbyt wcześnie — prowadzi do lokalnie optymalnego, ale globalnie suboptymalnego wyniku; należy utrzymać odpowiednią wielkość populacji i wskaźnik mutacji, aby temu przeciwdziałać.
  • Użycie źle zdefiniowanej lub błędnie określonej funkcji przystosowania prowadzi do wprowadzających w błąd wyników niezależnie od poprawności algorytmicznej; należy niezależnie zweryfikować funkcję przystosowania przed uruchomieniem GA.
  • Zastosowanie GA do gładkiego, wypukłego problemu, gdzie spadek gradientowy lub programowanie liniowe byłyby wystarczające, marnuje zasoby obliczeniowe i wprowadza niepotrzebną stochastyczność.
  • Raportowanie pojedynczego uruchomienia jako rozwiązania bez sprawdzania powtarzalności; w przypadku aplikacji o wysokiej stawce uruchom algorytm wielokrotnie i raportuj rozkład wyników.

Najczęściej zadawane pytania

Czym algorytm genetyczny różni się od spadku gradientowego?

Spadek gradientowy wymaga różniczkowalnego celu i podąża w dół za lokalnym gradientem. Algorytm genetyczny wymaga jedynie, aby przystosowanie mogło być obliczone dla dowolnego kandydata na rozwiązanie; przeszukuje poprzez ewolucję populacji, a nie przez podążanie za gradientem, dzięki czemu może obsługiwać krajobrazy nieciągłe, niedyferencjowalne i wielomodalne, gdzie spadek gradientowy zawodzi lub utyka.

Ile pokoleń i jak dużą populację potrzebuję?

Nie ma uniwersalnych zasad; oba zależą od złożoności przestrzeni poszukiwań. Populacja zbyt mała lub zbyt krótkie uruchomienie grozi przedwczesną zbieżnością. Jako praktyczny punkt wyjścia, wielkości populacji od 50 do 200 i liczba pokoleń od 100 do 1000 są powszechne w literaturze, ale trudne problemy rutynowo wymagają więcej. Zawsze analizuj krzywe zbieżności, zamiast ustalać arbitralne kryteria zatrzymania.

Czy algorytm genetyczny gwarantuje znalezienie globalnego optimum?

Nie. GA to heurystyki i nie dają gwarancji zbieżności do globalnego optimum w skończonym czasie. W celu uzyskania deterministycznych gwarancji potrzebne są metody dokładne, takie jak solwery programowania całkowitoliczbowego. W przypadku decyzji o wysokiej stawce uruchom GA wielokrotnie, raportuj rozkład wyników i porównaj najlepsze rozwiązanie z wszelkimi znanymi granicami.

Kiedy powinienem wybrać GA zamiast wyżarzania symulowanego lub optymalizacji rojem cząstek?

GA są zazwyczaj preferowane, gdy rozwiązanie jest naturalnie kodowane jako struktura kombinatoryczna (permutacje, ciągi binarne) lub gdy potrzebne są rozszerzenia wielokryterialne. Optymalizacja rojem cząstek jest często szybsza w problemach ciągłych jednokryterialnych. Wyżarzanie symulowane jest prostsze do zaimplementowania dla problemów kombinatorycznych z dobrze zdefiniowanym sąsiedztwem. W praktyce zaleca się porównanie dwóch lub trzech metod na małym przykładzie problemu przed wyborem jednej.

Pokrewne metody

Źródła

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Skopiowano.