Wielofunkcyjny algorytm genetyczny NSGA-2. Ktoś może mi dać "proste wyjaśnienie"?

Question

Pracuję nad algorytmem genetycznym.

Istnieją dwa cele i każdy ma swoje własne wartości fitness (fv1, fv2).

Wiem, jak działa algorytm genetyczny pokoleniowy (SGE) i stacjonarny (SS).

Próbuję zrozumieć, jak NSGA-2 i SPEA-2 (używam realizację biblioteki Java JCLEC) Praca, w szczególności:

• co jest "populacja zewnętrzny" i jak powinno być dobierane
• jaka jest różnica z SS i SGE jednego obiektywnego algorytmu (a częściowo z faktu, każdy ma tylko jedną wartość fitness)

W przypadku ktoś pracuje z biblioteki JCLEC są parametry Konfiguruję:

• populacji zewnętrzny: 1000
• wartość k: 10
• inne cechy są takie same SS i SG (populacja wielkości: 100 krzyżowym: MPX zwrotnicy itp ..)

Answer 1

Oto wyjaśnienie NSGA-II

1. pierwsze, losowo inicjuje populacji.
2. Chromosomy są sortowane i umieszczane na frontach w oparciu o zestawy zdominowane przez Pareto. W obrębie przodu Pareto chromosomy są uszeregowane na podstawie euklidesów między roztworami lub I-dist (termin stosowany w NSGA-II).Ogólnie rzecz biorąc, rozwiązania, które są daleko (nie zatłoczone) od innych rozwiązań, mają wyższą preferencję podczas selekcji. Odbywa się to w celu zrobienia zróżnicowanego rozwiązania i uniknięcia zestawu zatłoczonych rozwiązań.
3. Najlepsze chromosomy N (populacyjne) są wybierane z obecnej populacji i umieszczane w puli kojarzeń
4. W puli kojarzeń dokonuje się selekcji turnieju, krzyżowania i krycia.
5. Zbiorcza pula i aktualna populacja są połączone. Wynikowy zbiór jest sortowany, a najlepsze chromosomy N trafiają do nowej populacji.
6. Przejdź do kroku 2, chyba że osiągnięto maksymalną liczbę pokoleń.
7. Zestaw rozwiązań jest najlepiej zdominowanym zestawem Pareto z ostatniej populacji.

Answer 2

Polecam przeczytać artykuły na temat tych algorytmów, które dość dobrze wyjaśniają funkcjonalność:

• Deb, Pratab, Agarwal, Meyarivan. Szybki i elitarny wieloobiektywowy algorytm genetyczny: NSGA-II. Transakcje IEEE dotyczące obliczeń ewolucyjnych 6 (2), str. 182-197, 2002.
• Zitzler, Laumanns, Thiele. SPEA2: Poprawa siły Pareto Algorytm ewolucyjny. Raport techniczny (TIK-103), Szwajcarski Federalny Instytut Technologii (ETH), 2001.

Jestem pewien, że jesteś w stanie zlokalizować plik PDF tych publikacji w Internecie.

O różnicy między GA w stanie stacjonarnym a pokoleniem GA: w zastępstwie pokoleń tworzy się zupełnie nową populację o tej samej wielkości, co stara, wykorzystując tylko geny w starej populacji, a następnie zastępując ją jako całość. W stanie stabilnego stanu tworzysz tylko jedną nową osobę, która zastępuje tylko jedną osobę w populacji. Geny GA w stanie stacjonarnym zwykle zbiegają się szybciej, ale są mniej skłonne do znalezienia dobrej lokalnej optymalności, ponieważ nie eksplorują krajobrazu fitness tak często, jak podczas wymiany pokoleń. To zależy oczywiście od problemu, a czasami możesz wybrać, ile starego pokolenia chcesz zastąpić, co pozwala ci uzyskać dowolną skalę pomiędzy tymi dwoma.

Dostępne są dalsze algorytmy wieloobiektowe, takie jak AbYSS i PAES.