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

Algorytm genetyczny stochastyczny — losowe przeszukiwanie ewolucyjne w celu optymalizacji

Autor metody
Holland, J. H.
Rok
1975
Typ
Stochastic evolutionary metaheuristic
Rodzina
Simulation / optimization

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

Rozmiar czcionki

Do czego służy?

Algorytm genetyczny stochastyczny (SGA) to metaheurystyka oparta na populacji, która naśladuje procesy biologicznej ewolucji — selekcję, krzyżowanie i mutację — w celu wyszukiwania bliskich optymalnych rozwiązań w przestrzeniach złożonych, nieliniowych lub kombinatorycznych.

Jego losowe operatory sprawiają, że jest odporny na lokalne optima i szeroko stosowalny w inżynierii, harmonogramowaniu, uczeniu maszynowym i badaniach operacyjnych.

Intuicja stojąca za metodą

Wyobraźmy sobie populację kandydatów na rozwiązania konkurujących o przetrwanie. Lepsze rozwiązania są częściej wybierane jako rodzice; ich potomstwo dziedziczy i rekombinuje dobre cechy, podczas gdy sporadyczne losowe mutacje wprowadzają nowość. W ciągu wielu pokoleń proces ten zbiega się w kierunku wysokiej jakości regionów przestrzeni poszukiwań, bez potrzeby informacji o gradiencie. Określenie 'stochastyczny' podkreśla, że selekcja, krzyżowanie i mutacja obejmują losowania probabilistyczne, co odróżnia kanoniczny algorytm genetyczny od rzadkich wariantów deterministycznych i nadaje mu zdolność globalnego przeszukiwania.

Historia

John Holland wprowadził teoretyczne podstawy algorytmów genetycznych na Uniwersytecie Michigan w 1975 roku, opierając się na wcześniejszych pracach Frasera (1957) dotyczących symulowanych systemów genetycznych. Podręcznik Davida Goldberga z 1989 roku spopularyzował algorytmy genetyczne w optymalizacji inżynierskiej. Stochastyczna natura selekcji została sformalizowana za pomocą twierdzenia o schematach, a metoda stała się kamieniem węgielnym obliczeń ewolucyjnych i inteligencji obliczeniowej.

Kiedy stosować

Użyj algorytmu genetycznego stochastycznego, gdy: (1) przestrzeń poszukiwań jest duża, multimodalna lub nieciągła, a metody oparte na gradiencie zawodzą lub są nieodpowiednie; (2) funkcja celu jest 'czarną skrzynką', zaszumiona lub kosztowna w ocenie, ale możliwa do analizy przy próbkowaniu na poziomie populacji; (3) problemy kombinatoryczne lub mieszane liczbowo nie mają wydajnych dokładnych rozwiązań; (4) bliskie optymalne rozwiązanie znalezione w rozsądnej liczbie ocen jest akceptowalne. NIE używaj SGA, gdy: problem jest wypukły lub gradient jest dostępny i tani — klasyczna optymalizacja zbiega się szybciej; gdy oceny funkcji są niezwykle kosztowne (dziesiątki lub setki), metody oparte na populacji mogą wyczerpać budżet; lub gdy wymagane jest udowodnione optymalne rozwiązanie, ponieważ algorytmy genetyczne nie dają gwarancji optymalności.

Ograniczenia i uwagi

  • Brak gwarancji znalezienia globalnego optimum; jakość rozwiązania zależy od wielkości populacji, wyboru operatorów i liczby generacji.
  • Obliczeniowo kosztowny w porównaniu do metod opartych na gradiencie w przypadku problemów gładkich, niskowymiarowych — wymagana jest duża liczba ocen funkcji.
  • Dostrajanie hiperparametrów (wielkość populacji, tempo krzyżowania, tempo mutacji) zależy od problemu i często wymaga eksperymentów.
  • Przedwczesna zbieżność może wystąpić, jeśli presja selekcyjna jest zbyt wysoka lub tempo mutacji jest zbyt niskie, co uwięzi poszukiwania w podoptymalnych regionach.

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

Mocne strony

  • Nie wymaga informacji o gradiencie — stosowalny do celów typu 'czarna skrzynka', nieciągłych lub niedróżniczkowalnych.
  • Naturalnie obsługuje przestrzenie poszukiwań kombinatorycznych, mieszanych liczbowo i permutacji z odpowiednim kodowaniem.
  • Z natury możliwy do zrównoleglenia: populacja może być oceniana równolegle, skracając czas rzeczywisty.
  • Odporny na lokalne optima dzięki różnorodności populacji i eksploracji stochastycznej.
  • Wysoce rozszerzalny: operatory, kodowania i schematy selekcji można dostosować do ograniczeń specyficznych dla dziedziny.

Zastosowania

  • Harmonogramowanie zadań typu job-shop i flow-shop w produkcji i logistyce
  • Selekcja cech i dostrajanie hiperparametrów w potokach uczenia maszynowego
  • Optymalizacja strukturalna i topologiczna w inżynierii mechanicznej i budowlanej
  • Problemy komiwojażera i trasowania pojazdów w badaniach operacyjnych
  • Predykcja struktury białek i odkrywanie leków w bioinformatyce
  • Wyszukiwanie architektury sieci neuronowych i optymalizacja wag

Jak to działa

Jak to działa

1

Wygeneruj początkową populację N kandydatów na rozwiązania (chromosomów) losowo lub poprzez heurystyczne rozmieszczenie. Każdy chromosom koduje wykonalny punkt w przestrzeni decyzyjnej — ciągi binarne, wektory liczb rzeczywistych, permutacje lub drzewa, w zależności od wybranej reprezentacji problemu.

2

Oblicz wartość funkcji przystosowania f(x_i) dla każdego osobnika w populacji, używając funkcji celu (lub jej zastępnika). Przystosowanie kwantyfikuje jakość rozwiązania; wyższe przystosowanie oznacza lepsze rozwiązanie. W przypadku problemów minimalizacji, przystosowanie jest często definiowane jako odwrotność lub transformacja funkcji kosztu.

Wzór
f(x_i), \quad i = 1, \ldots, N
3

Zastosuj stochastyczny operator selekcji do wyboru rodziców. Selekcja kołem ruletki (proporcjonalna do przystosowania) przypisuje każdemu osobnikowi prawdopodobieństwo proporcjonalne do jego przystosowania. Selekcja turniejowa, selekcja rangowa i elitaryzm to powszechne warianty kontrolujące presję selekcyjną.

Wzór
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

Z prawdopodobieństwem p_c (zazwyczaj 0,6–0,9) rekombinuj pary wybranych rodziców, aby wyprodukować potomstwo. Krzyżowanie jednopunktowe, dwupunktowe lub jednorodne wymienia materiał genetyczny między chromosomami rodzicielskimi, tworząc potomstwo dziedziczące cechy od obojga. Ten operator napędza eksploatację dobrych bloków konstrukcyjnych.

5

Z niskim prawdopodobieństwem p_m (zazwyczaj 0,001–0,05 na gen) losowo modyfikuj pojedyncze geny w każdym chromosomie potomnym. Mutacja utrzymuje różnorodność genetyczną, zapobiega przedwczesnej zbieżności i zapewnia, że algorytm może uciec z lokalnych optimów. Tempo mutacji jest krytycznym parametrem dostrajanym do problemu.

6

Zastąp obecną populację potomstwem (zastępowanie generacyjne) lub użyj aktualizacji stanu ustalonego. Ponownie oceń przystosowanie i powtórz od kroku selekcji, aż do spełnienia kryterium zatrzymania — maksymalnej liczby generacji, progu przystosowania lub braku poprawy przez określoną liczbę generacji.

Częste pułapki

  • Użycie tempa mutacji, które jest zbyt wysokie, skutecznie sprowadza algorytm do losowego przeszukiwania i niszczy zgromadzone zyski z przystosowania.
  • Ignorowanie elitaryzmu w strategii zastępowania może spowodować utratę najlepszego znalezionego rozwiązania między generacjami.
  • Stosowanie operatorów krzyżowania dla liczb rzeczywistych do problemów zakodowanych binarnie (lub odwrotnie) narusza kodowanie i generuje nieprawidłowe potomstwo.
  • Zbyt wczesne zatrzymanie — niewystarczająca liczba generacji — jest najczęstszą przyczyną słabej jakości rozwiązania w praktyce.
  • Ignorowanie obsługi ograniczeń: nieograniczone krzyżowanie i mutacja często naruszają ograniczenia problemu; funkcje kary lub operatory naprawcze muszą być wbudowane jawnie.

Najczęściej zadawane pytania

Czym algorytm genetyczny stochastyczny różni się od standardowego algorytmu genetycznego?

Określenie 'stochastyczny' podkreśla, że wszystkie podstawowe operatory — selekcja, krzyżowanie i mutacja — obejmują losowania probabilistyczne. Kanoniczny algorytm genetyczny wprowadzony przez Hollanda jest z natury stochastyczny. Określenie to jest używane w literaturze dotyczącej symulacji/optymalizacji, aby odróżnić go od rzadkich wariantów deterministycznych (np. deterministycznego tłumienia) i wyjaśnić, że zachowanie algorytmu różni się między uruchomieniami z powodu losowości.

Jak duża powinna być populacja?

Częstym punktem wyjścia jest 50–200 osobników dla problemów o umiarkowanej wymiarowości. Większe populacje poprawiają różnorodność i zmniejszają przedwczesną zbieżność, ale zwiększają koszt obliczeniowy na generację. Istnieją reguły kciuka oparte na długości chromosomu (np. 10-krotność liczby genów), ale często konieczne jest dostrajanie empiryczne lub metaoptymalizacja.

Kiedy powinienem preferować optymalizację rojem cząstek (PSO) lub wyżarzanie symulowane (SA) zamiast algorytmu genetycznego?

Optymalizacja rojem cząstek (PSO) jest często szybsza w przypadku ciągłych problemów z liczbami rzeczywistymi, ponieważ wykorzystuje informacje o prędkości. Wyżarzanie symulowane (SA) jest prostsze w implementacji i może być skuteczne w przypadku przeszukiwania trajektorii pojedynczego rozwiązania. Algorytmy genetyczne są preferowane, gdy przestrzeń poszukiwań jest kombinatoryczna, gdy krzyżowanie sensownie rekombinuje struktury rozwiązań lub gdy różnorodność populacji jest cenna w krajobrazach multimodalnych.

Czy algorytm genetyczny stochastyczny skaluje się do problemów wysokowymiarowych?

Wydajność spada w bardzo wysokich wymiarach (setki do tysięcy zmiennych), ponieważ populacja musi być wystarczająco duża, aby odpowiednio próbować przestrzeń. Specjalistyczne warianty — takie jak algorytmy genetyczne uczące się powiązań, algorytmy estymacji rozkładu lub modele wyspowe z migracją — rozwiązują problem skalowalności, ale dodają złożoności.

Jak obsługiwać ograniczenia w algorytmie genetycznym?

Stosuje się trzy główne strategie: (1) funkcje kary, które zmniejszają przystosowanie za naruszenia ograniczeń; (2) operatory naprawcze, które rzutują nieprawidłowe potomstwo z powrotem do obszaru dopuszczalnego; (3) specjalistyczne kodowania i operatory, które generują tylko prawidłowe rozwiązania przez konstrukcję. Metody oparte na karach są najłatwiejsze do wdrożenia, ale wymagają starannej kalibracji współczynników kary.

Pokrewne metody

Źródła

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

    ISBN: 978-0262581110
    Skopiowano.
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ISBN: 978-0201157673
    Skopiowano.