Abstract-Målet med multiobjektiv optimering är att hitta en uppsättning av bästa kompromisslösningar för typiskt motstridiga mål. På grund av den komplexa karaktären av de flesta verkliga problem, kan endast en approximation till en sådan optimal uppsättning uppnås inom rimlig (beräknande) tid. För att jämföra sådana approximationer, och därmed prestandan hos multiobjektiva optimatorer som tillhandahåller dem, tillämpas vanligtvis obundna kvalitetsåtgärder. Bland dessa är hypervolymindikatorn (eller S-metrisk) av särskild betydelse på grund av dess gynnsamma egenskaper. Dessutom har denna indikator framgångsrikt integrerats i stokastiska optimatorer, såsom evolutionära algoritmer, där det fungerar som ett vägledande kriterium för att hitta goda approximationer till Pareto fronten. Nya resultat visar att beräkning av hypervolymindikatorn kan ses som att lösa en specialiserad version av Klee's Mätproblem. I allmänhet kan Klee ‘ s åtgärdsproblem lösas med O (n log n + n d/2 log n) jämförelser för en inmatning instans av storlek n i d dimensioner; från och med denna skrift, är det okänt om en lägre gräns högre än (n log n) kan bevisas. I detta dokument härleder vi en lägre gräns för (n log n) för komplexiteten i att beräkna hypervolymindikatorn i ett antal dimensioner d > 1 genom att minska det så kallade UNIFORMGAP-problemet till det. För 3-D-fallet presenterar vi också en matchande övre gräns för O(n log n) jämförelser som erhålls genom att utöka en algoritm för att hitta maximum för en punktuppsättning. Index Terms-Complexity analys, beräkningsgeometri, multiobjektiv optimering, prestandabedömning. Jag. MOTIVATION OCH INLEDNING TILL MULTIOBJEKTIVA OPTIMISATION N MULTIOBJEKTIVA optimering, problemet är att hitta bästa möjliga kompromisslösningar som inte kan förbättras enligt ett mål utan att försämra de andra. Denna typ av problem uppstår inom alla typer av industriella tillämpningsområden som sträcker sig från produktion till tjänsteindustri, underhållning och många andra. Eftersom många verkliga problem dock inte kan förväntas bli lösta till optimalitet (antingen alls eller inom en rimlig tidsrymd) är målet vanligtvis att uppnå en god approximation till den optimala uppsättningen lösningar inom rimlig tid.  e., q p) och q = p. Två olika punkter är ojämförliga iff ingen punkt dominerar den andra. Poäng som inte domineras inom en uppsättning är de bästa, och kallas icke-dominerad eller maximal. De delar av sökutrymmet som genererar de icke-dominerade elementen i det objektiva utrymmet bildar Pareto-uppsättningen av problemet, och uppsättningen av motsvarande bilder i det objektiva utrymmet kallas Pareto front. Multiobjektiva optimatorer genererar approximationer av Paretofronten. För att bedöma prestandan hos olika optimatorer måste deras approximationer jämföras. Detta kan göras genom att utvidga Pareto dominans förhållande till uppsättningar av punkter (se t.ex. Zitzler et al. [3]), men i detta fall, bra Pareto front approximations är ofta ojämförligt med varandra. Därför har många forskare föreslagit kvalitetsindikatorer för de uppsättningar kompromisslösningar som genereras av multiobjektiva optimatorer som – enligt flera kvalitetskriterier – kartlägger sådana uppsättningar på skalorvärden och därmed möjliggör en enkel jämförelse. Det råder allmän enighet om två (informella) kvalitetskriterier: En approximation av den optimala uppsättningen är bra om 1) dess punkter är "nära" Pareto fronten; 2) punkterna är "väldistribuerade" längs hela Pareto fronten. Dessutom anser vi att det är värt att nämna att en god approximation ska innehålla "många" icke-dominerade punkter. En fördjupad översikt över kvalitetsåtgärder och deras egenskaper ges av Zitzler et al. Kommissionens genomförandeförordning (EU) nr 668/2014 av den 13 juni 2014 om tillämpningsföreskrifter för Europaparlamentets och rådets förordning (EU) nr 1151/2012 om kvalitetsordningar för jordbruksprodukter och livsmedel (EUT L 179, 19.6.2014, s. 1).
Till exempel visade vi att QHV får O(n log n) tid, i bästa fall, vilket är den nedre gränsen REF för hypervolym, men denna prestanda är praktiskt taget omöjlig.
On the Complexity of Computing the Hypervolume Indicator
{'venue': 'IEEE Transactions on Evolutionary Computation', 'journal': 'IEEE Transactions on Evolutionary Computation', 'mag_field_of_study': ['Mathematics', 'Computer Science']}