I detta dokument ger vi en systematisk jämförelse av olika evolutionära metoder för multiobjektiv optimering med hjälp av sex noggrant utvalda testfunktioner. Varje testfunktion innefattar en särskild egenskap som är känd för att orsaka svårigheter i den evolutionära optimeringsprocessen, främst för att konvergera till Pareto-optimal front (t.ex. multimodalitet och bedrägeri). Genom att undersöka dessa olika problemfunktioner separat, är det möjligt att förutsäga vilken typ av problem som en viss teknik är eller inte är väl lämpad för. Till skillnad från vad som misstänktes i förväg tyder de experimentella resultaten emellertid på en hierarki av de algoritmer som övervägs. Dessutom visar de nya effekterna att de föreslagna testfunktionerna ger tillräcklig komplexitet för att jämföra multiobjektiva optimatorer. Slutligen visar sig elitism vara en viktig faktor för att förbättra det evolutionära flermålssökandet. Evolutionära algoritmer, multiobjektiv optimering, Pareto optimalitet, testfunktioner, elitism. Evolutionära algoritmer (EAs) har etablerats som den metod som finns till hands för att utforska Pareto-optimal front i multiobjektiva optimeringsproblem som är för komplexa för att lösas med exakta metoder, såsom linjär programmering och gradientsökning. Detta beror inte bara på att det finns få alternativ för att söka oåtkomligt stora utrymmen för flera Pareto-optimala lösningar. På grund av deras inneboende parallellism och deras förmåga att utnyttja likheter av lösningar genom rekombination, kan de approximera Pareto-optimal front i en enda optimeringskörning. Detta tar hänsyn till de många tillämpningarna och det snabbt växande intresset för flera mål inom EA. Efter de första banbrytande studierna om evolutionär multiobjektiv optimering dök upp i mitten av åttiotalet (Schaffer, 1984 (Schaffer, 1985 Fourman,1985) flera olika EA genomföranden föreslogs under åren 1991 (Kursawe, 1991 Hajela och Lin, 1992 Fleming, 1993; Horn et al., 1994; Srinivas och Deb, 1994). Senare tillämpades dessa metoder (och variationer av dem) framgångsrikt på olika multiobjektiva optimeringsproblem (Ishibuchi och Murata, 1996; Cunha et al., 1997; Valenzuela-Rendón och Uresticharre, 1997; Fonseca och Fleming, 1998; Parker och Miller, 1998). Under de senaste åren har vissa forskare undersökt särskilda ämnen för evolutionär multiobjektiv sökning, såsom konvergens till Pareto-optimal front (Van Veldhuizen och Lamont, 1998a; Rudolph, 1998), niching (Obayashi et al., 1998), och elitism (Parks och Miller, 1998; Obayashi et al., 1998), medan andra har koncentrerat sig på att utveckla nya evolutionära tekniker (Laumanns et al., 1998; Zitzler och Thiele, 1999). För en grundlig diskussion av evolutionära algoritmer för multiobjektiv optimering hänvisas den intresserade läsaren till Fonseca och Fleming (1995), Horn (1997), Van Veldhuizen och Lamont (1998b) och Coello (1999). Trots denna variation finns det en brist på studier som jämför prestanda och olika aspekter av dessa strategier. Följaktligen uppstår frågan: vilka genomföranden är lämpliga för vilken typ av problem, och vilka är de specifika fördelarna och nackdelarna med olika tekniker? De första stegen i denna riktning har gjorts i både teori och praktik. På den teoretiska sidan diskuterade Fonseca och Fleming (1995) inverkan av olika fitness tilldelningsstrategier på urvalsprocessen. På den praktiska sidan använde Zitzler och Thiele (1998, 1999) ett NP-hard 0/1 knapsack-problem för att jämföra flera multiobjektiva EA. I det här dokumentet ger vi en systematisk jämförelse av sex flermålsenliga EA, inklusive en slumpmässig sökstrategi samt ett enda mål för EA med hjälp av objektiv aggregering. Grunden för denna empiriska studie är en uppsättning väldefinierade, domänoberoende testfunktioner som gör det möjligt att undersöka oberoende problem. Vi drar därmed nytta av de resultat som presenterades i Deb (1999), där problemfunktioner som kan göra konvergens av EAs till Pareto-optimala fronten svårt identifieras och dessutom föreslås metoder för att konstruera lämpliga testfunktioner. De funktioner som behandlas här omfattar området konvexitet, icke konvexitet, diskreta Paretofronter, multimodalitet, bedrägeri och partiska sökytor. Därför kan vi systematiskt jämföra de metoder som bygger på olika typer av svårigheter och bestämma mer exakt var vissa tekniker är fördelaktiga eller har problem. I detta sammanhang undersöker vi också ytterligare faktorer som befolkningsstorlek och elitism. Papperet är uppbyggt på följande sätt: I avsnitt 2 introduceras nyckelbegrepp för multiobjektiv optimering och den terminologi som används i detta papper matematiskt. Därefter ger vi en kort översikt över de fleråriga EA som är under övervägande, med särskild tonvikt på skillnaderna mellan dem. Testfunktionerna, deras konstruktion och deras val behandlas i avsnitt 4, som följs av en diskussion om prestandamått för att bedöma kvaliteten på avräkningsfronter. Därefter presenterar vi de experimentella resultaten i sektion 6 och undersöker ytterligare aspekter som elitism (avsnitt 7) och populationsstorlek (avsnitt 8) separat. En diskussion om resultaten och framtidsutsikterna ges i avsnitt 9. Optimeringsproblem som involverar flera, motstridiga mål hanteras ofta genom att samla målen i en skalarfunktion och lösa det resulterande enobjektiva optimeringsproblemet. I denna studie är vi däremot intresserade av att hitta en uppsättning optimala kompromisser, den så kallade Pareto-optimala uppsättningen. I följande, vi formalisera denna Pareto-optimala beslut vektorer kan inte förbättras i något mål utan att orsaka en försämring i åtminstone ett annat mål; de representerar, i vår terminologi, globalt optimala lösningar. Men, analogt med en objektiv optimering problem, kan det också finnas lokala optima som utgör en icke-dominerad uppsättning inom ett visst område. Detta motsvarar begreppen globala och lokala Pareto-optimala uppsättningar som infördes av Deb (1999) 1 : DEFINITION 3: Överväg en uppsättning beslut vektorer X 0 X.
De utförde dock en enda objektiv optimering med hjälp av ett vägt genomsnitt av designmålen, som har visat sig inte vara effektiva REF.
Comparison of Multiobjective Evolutionary Algorithms: Empirical Results
{'venue': 'Evolutionary Computation', 'journal': 'Evolutionary Computation', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Medicine']}