NSGA-II — Niezdominowany Algorytm Genetyczny Sortowania II
- Rok
- 2002
- Typ
- Evolutionary multi-objective optimisation algorithm
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
NSGA-II (Non-dominated Sorting Genetic Algorithm II) to standardowy algorytm referencyjny do wieloobiektywnej optymalizacji ewolucyjnej, wprowadzony przez Deba, Pratapa, Agarwala i Meyarivana w 2002 roku.
Zamiast sprowadzać wiele sprzecznych celów do jednej oceny, algorytm ten ewoluuje populację rozwiązań kandydujących przez pokolenia i zwraca zbiór rozwiązań kompromisowych optymalnych w sensie Pareto — front Pareto — wykorzystując szybkie sortowanie niezdominowane i metrykę odległości zagęszczenia do zachowania różnorodności.
Intuicja stojąca za metodą
Wyobraźmy sobie, że chcemy zaprojektować produkt, który jest jednocześnie możliwie najtańszy i najtrwalszy. Tańszy zazwyczaj oznacza mniej trwały, więc nie ma jednej idealnej odpowiedzi — istnieje rodzina rozsądnych kompromisów. NSGA-II działa jak populacja konkurujących projektów: w każdym pokoleniu słabsze projekty, które są zdominowane przez inne pod każdym względem, są eliminowane, a ocalałe są rozprzestrzeniane tak, aby pokrywały pełny zakres kompromisów, zamiast skupiać się wokół jednego rogu. Po wystarczającej liczbie pokoleń pozostaje bogate menu opcji — front Pareto — z którego wybieramy równowagę odpowiadającą naszym priorytetom.
Historia
NSGA-II został opublikowany przez Kalyanmoya Deba i współpracowników z Indian Institute of Technology Kanpur w 2002 roku jako poprawiony i znacznie ulepszony następca oryginalnego NSGA (Srinivas & Deb, 1994). Kluczowymi innowacjami były szybka procedura sortowania niezdominowanego o złożoności O(MN²), jawny operator odległości zagęszczenia do utrzymania różnorodności rozwiązań bez parametru współdzielenia oraz elitarny mechanizm selekcji. Artykuł z 2002 roku w IEEE Transactions on Evolutionary Computation stał się jedną z najczęściej cytowanych prac w dziedzinie obliczeń ewolucyjnych i ustanowił NSGA-II jako de facto punkt odniesienia dla wieloobiektywnych algorytmów ewolucyjnych. Późniejsze warianty — NSGA-III (2014) i inne — rozszerzają ramy na problemy z wieloma celami.
Kiedy stosować
NSGA-II ma zastosowanie zawsze, gdy problem ma dwie lub więcej sprzecznych funkcji celu, których nie można połączyć w jedno kryterium bez utraty informacji. Zmienne decyzyjne mogą być ciągłe, binarne lub kategorialne, i nie są wymagane żadne założenia dotyczące rozkładu w przestrzeni celów. Algorytm nadaje się do projektowania inżynierskiego, alokacji zasobów, harmonogramowania i problemów portfelowych, gdzie spektrum rozwiązań kompromisowych jest bardziej użyteczne niż pojedyncze optimum. Wystarczająca liczba pokoleń (zazwyczaj kilkaset lub więcej) jest potrzebna do osiągnięcia dobrego pokrycia frontu; zbyt mała liczba pokoleń jest głównym trybem awarii.
Ograniczenia i uwagi
- Wydajność spada, gdy liczba celów przekracza trzy lub cztery — odległość zagęszczenia staje się słabą miarą różnorodności w wysokich wymiarach.
- Wymaga starannego dostrojenia rozmiaru populacji i liczby pokoleń; zbyt mała liczba pokoleń uniemożliwia odpowiednie pokrycie frontu.
- Ocena funkcji celu, które obejmują kosztowne symulacje, sprawia, że algorytm jest kosztowny obliczeniowo.
- Wyniki są stochastyczne: różne ziarna losowe mogą dawać różne fronty Pareto, dlatego zaleca się wielokrotne uruchomienia i porównanie statystyczne (np. hiperobjętości).
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Generuje zróżnicowany zbiór rozwiązań kompromisowych optymalnych w sensie Pareto w jednym przebiegu, eliminując potrzebę powtarzania optymalizacji z różnymi wagami.
- Szybkie sortowanie niezdominowane działa w czasie O(MN²) (M celów, N rozmiar populacji), co czyni je wykonalnym dla umiarkowanych rozmiarów problemów.
- Elitarna selekcja zapewnia, że dobre rozwiązania znalezione wcześnie nigdy nie zostaną odrzucone.
- Ma zastosowanie do ciągłych, binarnych i kategorialnych zmiennych decyzyjnych bez założeń dotyczących rozkładu.
- Szeroko walidowany w dziedzinach inżynierii, badań operacyjnych i nauk obliczeniowych.
Zastosowania
- Projektowanie inżynierskie: jednoczesne minimalizowanie masy i maksymalizowanie wytrzymałości konstrukcyjnej w elementach mechanicznych.
- Systemy środowiskowe i energetyczne: równoważenie kosztów, emisji i niezawodności w planowaniu sieci energetycznych lub energii odnawialnej.
- Opieka zdrowotna i badania operacyjne: harmonogramowanie, które jednocześnie optymalizuje czas oczekiwania pacjentów, wykorzystanie zasobów i koszty.
- Optymalizacja portfela w finansach i wybór projektów w biznesie: równoważenie zwrotu, ryzyka i płynności.
- Strojenie hiperparametrów w uczeniu maszynowym: optymalizacja dokładności względem złożoności modelu lub czasu wnioskowania.
Jak to działa
Jak to działa
Populacja rozwiązań kandydujących jest tworzona poprzez losowe próbkowanie zmiennych decyzyjnych (lub przez projekt) w ich granicach. Rozmiar populacji jest ustawiany na tyle duży, aby zapewnić różnorodność w przestrzeni celów od samego początku.
Każde rozwiązanie kandydujące jest dekodowane na wartości zmiennych decyzyjnych i oceniana jest każda funkcja celu. Wynikiem jest wektor ocen celów dla każdej jednostki. Ten krok jest często wąskim gardłem obliczeniowym, gdy cele obejmują symulacje lub kosztowne modele.
Rozwiązania są szeregowane poprzez sortowanie niezdominowane: pierwszy front zawiera wszystkie rozwiązania, których żadne inne rozwiązanie nie dominuje pod każdym względem; drugi front zawiera rozwiązania zdominowane tylko przez te z pierwszego frontu; i tak dalej. W obrębie każdego frontu obliczana jest ocena odległości zagęszczenia, aby zmierzyć, jak izolowane jest rozwiązanie od swoich sąsiadów — większa odległość zagęszczenia oznacza, że rozwiązanie zajmuje mniej zatłoczony obszar frontu.
Elitarna strategia selekcji łączy bieżącą populację z potomstwem i zachowuje N najlepszych osobników, wypełniając fronty po kolei i wykorzystując odległość zagęszczenia do rozstrzygania remisów w ostatnim dopuszczalnym froncie. Gwarantuje to, że dobre rozwiązania znalezione w poprzednich pokoleniach nigdy nie zostaną utracone.
Wybrane osobniki rozmnażają się za pomocą operatorów genetycznych — selekcji turniejowej binarnej, symulowanego binarnego krzyżowania (SBX) i mutacji wielomianowej — tworząc nową populację potomną. Operatory te zachowują znaczącą zmienność, jednocześnie eksplorując sąsiedztwo obiecujących rozwiązań.
Kroki od oceny do ewolucji powtarzają się przez określoną liczbę pokoleń. Konwergencja jest oceniana wizualnie na podstawie frontu Pareto lub poprzez śledzenie wskaźnika hiperobjętości. Ostatecznym wynikiem jest zbiór rozwiązań niezdominowanych, przybliżający prawdziwy front Pareto.
Częste pułapki
- Uruchomienie mniej niż kilkuset pokoleń zazwyczaj daje niekompletny front Pareto; jeśli budżet obliczeniowy jest ograniczony, należy rozważyć zamiast tego ważoną optymalizację jednoobiektywną.
- Traktowanie problemu z jednym celem jako wieloobiektywnego jest niepotrzebne — należy użyć optymalizatora jednoobiektywnego.
- Zaniedbanie ustawienia rozsądnych granic zmiennych prowadzi do populacji, które nigdy nie osiągają wykonalnych lub znaczących regionów przestrzeni poszukiwań.
- Raportowanie tylko jednego rozwiązania z frontu Pareto bez ujawniania pełnego frontu ukrywa strukturę kompromisów, którą NSGA-II ma za zadanie ujawnić.
Najczęściej zadawane pytania
Ile pokoleń potrzebuje NSGA-II?
Nie ma uniwersalnej zasady, ale uruchomienie mniej niż kilkuset pokoleń zazwyczaj daje niekompletny front Pareto. Praktycznym podejściem jest wykreślenie wskaźnika hiperobjętości w kolejnych pokoleniach i zatrzymanie się, gdy się ustabilizuje. Jeśli budżet obliczeniowy to uniemożliwia, bezpieczniejszą alternatywą jest ważony optymalizator jednoobiektywny.
Czym jest front Pareto?
Front Pareto to zbiór rozwiązań, w których nie jest możliwa poprawa jednego celu bez pogorszenia co najmniej jednego innego. NSGA-II przybliża ten front, dając pełne menu zrównoważonych kompromisów, a nie jedną odpowiedź.
Czy NSGA-II może obsługiwać więcej niż dwa cele?
Tak, ale odległość zagęszczenia — mechanizm różnorodności — staje się mniej skuteczna, gdy liczba celów przekracza trzy lub cztery (reżim „wieloobiektywny”). W przypadku problemów z pięcioma lub więcej celami, zazwyczaj preferowane są NSGA-III lub algorytmy oparte na dekompozycji, takie jak MOEA/D.
Czy NSGA-II jest deterministyczny?
Nie. Operatory genetyczne i początkowa populacja obejmują losowość, więc różne uruchomienia z różnymi ziarnami losowymi mogą dawać różne przybliżenia frontu Pareto. Najlepszą praktyką jest wielokrotne uruchomienie algorytmu i porównanie jakości frontu za pomocą wskaźnika hiperobjętości.
Pokrewne metody
Źródła
Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Otwórz odnośnik DOISkopiowano.Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
Otwórz odnośnik DOISkopiowano.