Hypervolymindikatorn är en uppsättning mått som används i evolutionär multiobjektiv optimering för att utvärdera prestandan hos sökalgoritmer och för att vägleda sökningen. Multiobjektiva evolutionära algoritmer med hjälp av hypervolymindikatorn omvandla multiobjektiva problem till enskilda objektiva genom att söka efter en ändlig uppsättning lösningar som maximerar motsvarande hypervolymindikator. I detta dokument undersöker vi teoretiskt hur de optimala μ-distributioner-finita uppsättningar av μ-lösningar som maximerar hypervolymindikatorn sprids över Pareto fronten av biobjektiva problem. Detta problem är av stor betydelse för praktiska tillämpningar eftersom dessa uppsättningar karakteriserar de preferenser som hypervolym indikator kodar, dvs, vilka typer av Pareto ställa approximationer gynnas. Vi tar särskilt itu med frågan om huruvida hypervolymindikatorn är partisk gentemot vissa regioner. För linjära fronter bevisar vi att fördelningen är enhetlig med konstant avstånd mellan två på varandra följande punkter. För allmänna fronter där det förmodligen är omöjligt att karakterisera exakt fördelningen, får vi ett gränsresultat när antalet punkter växer till oändlighet som bevisar att den empiriska densiteten av punkter konvergerar till en densitet som är proportionell mot kvadratroten av negativet av derivatan av fronten. Våra analyser visar att det inte är formen av Pareto fronten utan bara dess lutning som avgör hur de punkter som maximerar hypervolym indikatorn fördelas. Experimentella resultat visar att gränsvärdets densitet är en god approximation av den empiriska densiteten för små μ. Dessutom analyserar vi frågan om var man ska placera referenspunkten för indikatorn så att ytterligheterna i fronten kan hittas om hypervolymindikatorn är optimerad. Vi härleder en explicit lägre gräns (eventuellt oändligt) för att säkerställa närvaron av extremerna i den optimala fördelningen. Detta resultat motsäger den gemensamma uppfattningen att referenspunkten måste väljas nära nadirpunkten: för vissa typer av fronter visar vi att ingen ändlig referenspunkt gör det möjligt att ha ytterligheterna i den optimala μ-fördelningen. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift.  Kategorier och ämnesdeskriptorer Allmänt Termer Teori Hypervolymindikator, multiobjektiv optimering Fältet evolutionär multiobjektiv optimering handlar främst om frågan om att approximera Paretooptimal set, och olika algoritmer har föreslagits för detta ändamål. Under de senaste åren, sök algoritmer baserade på hypervolym indikator [27], en uppsättning mått som återspeglar volymen som omges av en Pareto front approximation och en referensuppsättning, har blivit allt populärare, t.ex. [16, 9, 14]. De övervinna de problem som uppstår med densitet-baserade multiobjektiva evolutionära algoritmer [21], eftersom hypervolym indikator garanterar strikt monotonicitet avseende Pareto dominans [11, 28]. Dessutom har de senaste utvidgningarna [23, 1] breddat tillämpligheten av denna åtgärd med avseende på företräde för artikulation och högdimensionella målområden. Därför förväntar vi oss att det vetenskapliga intresset för hypervolymindikatorn för sökning och prestandabedömning kommer att öka ytterligare. Denna utveckling motiverar varför flera forskare har försökt att bättre förstå hypervolymindikatorn ur ett teoretiskt perspektiv, t.ex. [11, 28, 23]. Ett viktigt resultat är att en uppsättning lösningar som uppnår maximal hypervolym för ett specifikt problem täcker hela Paretofronten [11]. Motsvarande uppsättning kan dock innehålla ett oändligt antal lösningar, medan i praktiken vanligtvis bundna lösningsset beaktas. Att begränsa antalet punkter till, låt oss säga μ, förändrar situationen: i detta fall kan endast en del av Paretofronten täckas, och hur punkterna fördelas över fronten beror på flera aspekter, särskilt på de främre egenskaperna och valet av referensuppsättning. Den resulterande placeringen av punkter återspeglar fördomarna i hypervolymindikatorn, och denna fråga har inte undersökts rigoröst hittills. Zitzler och Thiele [27] angav till exempel att när hypervolymoptimeringsproblemen optimeras kan "konvexa regioner föredras framför konkava regioner", vilket är 87 som också anges i [18], medan Deb et al. [7] hävdade att "[. ............................................................................................................. Knowles och Corne konstaterade att en lokal optimering av hypervolymindikatorn " verkar vara "väldistribuerad" [16], vilket också bekräftades empiriskt [17, 9]. Vissa författare tog också upp valet av referensuppsättning som vanligtvis bara innehåller en enda referenspunkt. Knowles och Corne [17] visade hur referenspunkten påverkar resultaten av utvalda multiobjektiva evolutionära algoritmer baserat på en experimentell studie. Dessutom finns tumregler, t.ex. rekommenderar många författare att använda hörnet av ett utrymme som är lite större än det faktiska objektiva utrymmet som referenspunkt. Exempel är hörnet av en låda som är 1 % större än det objektiva utrymmet i [15] eller en låda som är större med en additiv term på 1 än de yttersta objektiva värden som erhållits som i [3]. I olika publikationer väljs referenspunkten som nadirpunkten för den undersökta lösningen, t.ex. i [20, 19, 13], medan andra rekommenderar skalning av de objektiva värdena varje gång hypervolymindikatorn beräknas [25]. Ovanstående uttalanden om fördomarna i hypervolymindikatorn verkar vara motsägelsefulla och hittills finns inga teoretiska resultat tillgängliga som kan bekräfta eller förfalska någon av dessa hypoteser. I detta dokument ges en teori som tar upp bimålsfrågan och därigenom bidrar till en teoretisk förståelse av de principer som ligger till grund för indikatorn för hypervolym. I detta syfte kommer vi först formellt att redogöra för den inställning som behandlas i detta dokument (avsnitt 2) och presentera några grundläggande resultat när det gäller den optimala fördelningen av punkter på Paretofronten (avsnitt 3). Avsnitt 4 undersöker påverkan av en referenspunkt på placeringen av en ändlig uppsättning punkter. Därefter kommer vi matematiskt att härleda optimala placeringar av poäng för Paretos fronter som kan beskrivas med en linje (avsnitt 5). Senare, Vi utvidgar dessa resultat till allmänna frontformer förutsatt att antalet punkter i fördelningarna konvergerar till oändlighet (Avsnitt 6) och ger heuristiska metoder för att bestämma den optimala fördelningen av μ-punkter (Avsnitt 7). Under hela denna studie, anser vi en bikriterion optimering problem F : R d → R 2 bestående av två mål (F1(x), F2(x)) = F(x) som är utan förlust av allmängiltighet ska minimeras. De optimala lösningarna (Pareto optima) för detta problem ges av minimala delar av den beställda uppsättningen (R d, ) där står för den svaga Pareto dominans relation : Vi antar att det övergripande optimeringsmålet är att approximera uppsättningen Pareto optima-the Pareto set-med hjälp av en lösning uppsättning och att hypervolym indikatorn [27] används som ett mått för att kvantifiera kvaliteten på en lösning uppsättning. Bilden av Pareto set under F kallas Pareto front eller bara front för kort. Den hypervolymindikator IH ger, ungefär, volymen av den objektiva subrymden som domineras av en lösning som är inställd A  på R d under övervägande; den kan definieras på följande sätt på grundval av en referensuppsättning R  på R 2 : där i följande fall det vanliga fallet med en enda referenspunkt r = (r1, r2) R 2 beaktas endast, dvs. R = {r}. Det är känt att det största möjliga hypervolymvärdet endast kan uppnås när lösningen som A innehåller för varje punkt z på Paretofronten minst en motsvarande lösning x  och A med F(x) = z, dvs. bilden av A under F innehåller Paretofronten [11]. Detta teoretiska resultat förutsätter dock att A kan innehålla ett antal lösningar, även oändligt många. I praktiken är storleken på A vanligtvis begränsad, t.ex. av befolkningsstorleken när en evolutionär algoritm används, och därför är frågan hur indikatorn IH påverkar det optimala urvalet av ett begränsat antal μ-lösningar. För enkelhetens skull kommer vi endast att beakta de objektiva vektorerna i följande och påpeka att i det biobjektiva fallet kan Paretofronten beskrivas som en funktion f för att kartlägga bilden av Pareto som anges under F1 på bilden av Pareto som anges under F2. Vi antar att bilden av F1 är ett slutet intervall [xmin, xmax] och definierar f som den funktion som beskriver Paretofronten: Ett exempel ges i figur 1 där en front representeras i termer av denna funktion f (x). Eftersom f representerar formen av avräkningsytan, kan vi dra slutsatsen att, för minimering problem, f är strikt monotont minska i [xmin, xmax] 1. Dessutom anser vi bara kontinuerliga funktioner f. Nu är en uppsättning μ punkter på Pareto front helt bestäms av x-koordinater respektive F1 värden av dessa punkter, här betecknar som (x μ 1,. ., x μ ), och f. Utan förlust av allmängiltighet, antas det att x Om f inte är strikt monotont minskande, kan vi hitta Pareto-optimala punkter (x1, f(x1)) och (x2, f(x2)) med x1, x2  till [xmin, xmax] sådan att, utan förlust av allmänhet, x1 < x2 och Figur 2 ). Den hypervolym som omges av dessa punkter kan vara analogt med Eq. 1, lätt att bestämma: det är summan av rektanglar av bredd (Här, hypervolym indikator Innan vi kan karakterisera en uppsättning punkter maximera hypervolym (dvs, Eq. 2) måste vi vara säkra på att problemet är väldefinierat, dvs. att det finns minst en uppsättning punkter som maximerar Eq. 2. Utgångspunkten är följande: Existensen bevisas i nästa teorem förutsatt att f är kontinuerlig. 1 {y>f (x)} dynx där vi förlänger f för x > xmax genom att ställa in f (x) till konstantvärdet f (xmax). Därför, från medelvärdet teorem det finns en uppsättning av μ punkter maximera hypervolym indikator. Observera att det tidigare teorem anger existensen men inte den unika, vilket inte är sant i allmänhet men kommer att vara för linjära fronter (och vissa val av referenspunkten), vilket bevisas senare i tidningen. En uppsättning punkter som maximerar den hypervolym vars existens bevisas i föregående sats kommer att kallas en optimal μ-fördelning. Det associerade värdet av hypervolym anges som I Denna fråga kommer att behandlas i följande avsnitt. I detta avsnitt presenteras preliminära resultat för optimal μ-fördelning. Det första resultatet handlar om hur den hypervolym som är förenad med optimal μ-fördelning ökar med μ. Detta resultat är särskilt användbart för bevis på Corollary 1. Det här är Lemma 1. Låt X  till R och f : X → f (X) beskriva Pareto fronten. Låt μ1 och μ2 N med μ1 < μ2, och håll sedan om X innehåller minst μ1 + 1 grundämnen xi för vilka xi < r1 och f (xi) < r2 håller. Bevis. För att bevisa lemma räcker det att visa ojämlikheten för μ2 = μ1 + 1. Antag Dμ 1 = {x H. Eftersom X innehåller minst μ1 + 1 element, är den inställda X\Dμ 1 inte tom och vi kan välja någon xnew X\Dμ 1 som inte ingår i den optimala μ1-distributionen och för vilken f (xnew) definieras. Låt xr := min{x skax  på Dμ 1... {r1}, x > xnew} vara det närmaste elementet av Dμ 1 till höger om xnew (eller r1 om xnew är större än alla element i Dμ 1 ). På samma sätt, låt f l := min{r2, {f (x) ska x Dμ 1, x < xnew}} vara funktionsvärdet för det närmaste elementet av Dμ 1 till vänster om xnew (eller r2 om xnew är mindre än alla element i Dμ 1 ). Sedan, alla objektiva vektorer inom f(xnew)) är (svagt) domineras av den nya punkten (xnew, f(xnew)) men domineras inte av någon objektiv vektor som ges av Dμ 1. Dessutom är Hnew inte en null set (dvs. har ett strikt positivt mått) eftersom xnew > xr och f l > f(xnew) vilket ger I μ 1 Nästa förslag är ett centralt resultat av papperet som anger att x-koordinaterna för en uppsättning μ-punkter måste nödvändigtvis uppfylla en upprepningsrelation (ekv. 3) för att vara en optimal μ-fördelning. Den viktigaste idén för härledningen är att, med tanke på tre på varandra följande punkter på Pareto front, flytta mittpunkten bara kommer att påverka den hypervolym bidrag som är enbart tillägnad denna punkt (de gemensamma hypervolym bidrag förblir fast). För att tillhöra en optimal μ-fördelning måste följaktligen den hypervolymkomponent som enbart tillskrivs mittpunkten vara maximal. Förslag 1. (Necessärt tillstånd för optimal μ-fördelningar) Om f är kontinuerlig, differentierad och där f betecknar derivatan av f, f (x För en optimal μ-fördelning, måste var och en av hypervolym bidrag Hi vara maximal med avseende på x μ i eftersom annars skulle man kunna öka I Omorganisation villkoren och inställning H i (x μ i ) till noll, vi erhålla Eq. 3. Vad är det som händer? Det tidigare förslaget innebär att punkterna för optimal μ-fördelning är kopplade till Eq. 3. Vad är det som händer? I synnerhet bestäms μ-punkterna helt så snart x μ 1 och x μ 2 är inställda. Att hitta punkterna för en optimal μ-fördelning, dvs. att maximera den till synes μ-dimensionella funktionen (2) visar sig därför vara ett tvådimensionellt optimeringsproblem. En första följd av Lemma 1 och Proposition 1 är att en optimal punkt är antingen på en extrem av Pareto front eller inte kan vara en stationär punkt f, dvs en punkt där derivatan av f är lika med noll.  Optimala μ-distributioner är lösningarna på maximeringsproblemet i Eq. 2 som beror på valet av referenspunkt. Vi ställer nu frågan hur valet av referenspunkt påverkar optimala μ-fördelningar och undersöker särskilt om det finns ett val av referenspunkt som innebär att extremerna i Paretofronten ingår i optimala μ-fördelningar. Vi bevisar i Theorem 2 (sp. Teorem 3) att om derivatan av Pareto front vid den vänstra extremen (sp. höger extrem) är oändlig (resp. är noll), det finns inget val av referenspunkt som kommer att tillåta att vänster (resp. höger) extrem front ingår i optimala μ-fördelningar. Detta resultat strider mot den gemensamma uppfattningen att det är tillräckligt att välja referenspunkten något ovanför och till rätten till nadirpunkten för att uppnå ytterligheterna. Dessutom, när derivatan är ändlig till vänster extrem och icke-noll till höger extrem vi bevisa en explicit lägre gräns (eventuellt oändligt) för valet av referenspunkt som säkerställer att någon referenspunkt ovanför denna lägre gräns garanterar att extremerna av fronten ingår i optimala μ-fördelningar. Kom ihåg att r = (r 1, r2) betecknar referenspunkten och y = f (x) med x [xmin, xmax] representerar Paretofronten där därför (xmin, f(xmin)) och (xmax, f(xmax)) är vänster och höger extrempunkter. Eftersom vi vill att alla Paretooptimala lösningar ska bidra till frontens hypervolym för att eventuellt vara en del av optimala μ-distributioner, antar vi att referenspunkten domineras av alla Paretooptimala lösningar, dvs.. r1 ≥ xmax och r2 ≥ f (xmin).  där överarmen i den föregående ekvationen möjligen är oändlig. När R2 är ändlig finns den vänstra yttersta punkten i optimala μ-fördelningar om referenspunkten r = (r1, r2) är sådan att r2 är strikt större än R2. Dessutom, om limx→x min −f (x) = +∞, är den vänstra yttersta punkten på fronten aldrig inkluderad i optimala μ-fördelningar. För att sektionen ska vara läsbar finns beviset på ovanstående sats samt följande bevis i bilagan. På liknande sätt härleder vi följande teorem för att inkludera den högra Pareto-optimala punkten (xmax, f(xmax)) i optimala μ-fördelningar. Om f (xmax) = 0, är den högra extrempunkten aldrig inkluderad i optimala μ-fördelningar. I följande exempel illustrerar vi hur Theorem 2 och 3 kan användas på testproblem. och därför enligt Theorem 2, den vänstra mest Pareto-optimala punkten ingår aldrig i optimala μ-fördelningar. Dessutom har vi f (x) < 0 för alla x  på] 0, 1]. Låt oss beräkna R1 definieras i Eq. 5: Från Theorem 3 vet vi därför att rätt ytterlighet ingår om r1 > 3. Tabell 1 visar resultaten även för andra testproblem. I detta avsnitt, Vi har en närmare titt på linjära Pareto fronter, dvs, fronter avbildas som raka linjer som kan formellt definieras som f: x  på [xmin, xmax] → αx + β där α < 0 och β R. För linjära fronter med lutning α = −1, Beume et al. [2] redan visat att en uppsättning av μ-punkter maximerar hypervolym om och endast om punkterna är jämnt fördelade. Deras metod tillåter dock inte att ange var de vänstra och högra punkterna måste placeras för att maximera hypervolymen med avseende på en viss referenspunkt; dessutom kan metoden inte generaliseras till godtyckliga linjära fronter med andra sluttningar än −1. Samma resultat av lika avstånd mellan punkter som maximerar hypervolym har visats med en annan teknik i [10] för front f (x) = 1 − x. Även om den bevisteknik som används i [10] kunde generaliseras till godtyckliga linjära fronter, håller det erhållna resultatet återigen endast under antagandet att både den vänstra och den högra punkten är fast. Därför är frågan om var μ-punkter måste placeras på linjära fronter för att maximera hypervolymindikatorn utan något antagande om extrema punkter fortfarande inte besvarad. Inom detta avsnitt visar vi för linjära fronter av godtycklig lutning, hur optimala μ-fördelningar ser ut utan att göra några antaganden om positionerna för extrema lösningar. Först och främst ser vi som en direkt konsekvens av Proposition 1 att avståndet mellan två angränsande lösningar är konstant för godtyckliga linjära fronter: Bevis. Tillämpar Eq. 3 till f (x) = αx + β innebär att., μ − 1 och därför avståndet mellan på varandra följande punkter av optimala μ-fördelningar är konstant. Dessutom, i fall referenspunkten inte domineras av extrema punkter i Pareto front, dvs r1 < xmax och r2 är inställd så att det finns (en unik), Det finns en unik optimal μ-fördelning som kan bestämmas exakt, se även vänster plott av Bild. 4 : Bevis. Från Eq. 3 och det tidigare beviset vi vet att I ljuset av avsnitt 4, nästa fråga vi undersöker är valet av referenspunkt som säkerställer att optimal μ-fördelning innehåller ytterligheterna av fronten. Eftersom f (x) = α med 0 < α < +∞, ser vi att R2 och R1 som definieras i teorem 2 och 3 är ändliga och därmed vi nu att det finns ett val av referenspunkt som säkerställer att få ytterligheter. Följande teorem anger motsvarande nedre gränser för referenspunkten och anger den optimala μ-fördelning som är förknippad med ett sådant val. Rätt komplott i Bild. 4 illustrerar den optimala μ-distributionen för μ = 4 poäng. [xmin, xmax] → αx + β med α < 0, β  på R och referenspunkten r = (r1, r2) är sådan att r1 är strikt större än 2xmax-xmin och r2 är strikt större än 2αxmin −αxmax+ β, det finns en unik optimal μ-fördelning. Denna optimala μ-fördelning inkluderar ytterligheterna av fronten och för alla i = 1,..., μ Bevis. Från Eq. 4, r2 strikt större än d.v.s. r2 strikt större än 2αxmin − αxmax + β, säkerställer närvaron av xmin i optimala μ-fördelningar som ger x μ i = xmin för i = 1. Från Eq. 5, r1 strikt större än sup x på]x min,xmax] x + αx+β-αx min −β α, d.v.s. r1 strikt större än sup x på]x min,xmax] 2x-xmin = 2xmax-xmin, säkerställer närvaron av xmax i optimala μ-fördelningar och därmed x μ i = xmax för i = μ. Med samma argument som i Theorem 5 visar vi att optimala μ-fördelningar är unika, de lika avstånden mellan punkterna och därmed Eq. 7. Vad är det som händer? Som påpekades i början vet vi i allmänhet inte om optimala μ-fördelningar är unika eller inte. Teorem 5 och 6 är två inställningar där vi kan säkerställa unikheten. Förutom enkla fronter som den linjära är det svårt (förmodligen omöjligt) att bestämma exakt optimala μ-fördelningar. Men i detta avsnitt bestämmer vi fördelningen av punkter på godtyckliga fronter, när deras antal går till oändlighet. Dessa fördelningar kommer att karakteriseras i termer av densitet som kan användas för att approximera, för en ändlig μ, procent av poäng i ett visst segment av fronten. Dessutom gör det möjligt att på ett rigoröst sätt kvantifiera fördomarna hos hypervolymen med avseende på en viss front. Vårt huvudsakliga resultat, som anges i Theorem 7, är att densiteten är proportionell mot kvadratroten av negativa av derivatan av fronten. Även om resultaten i detta avsnitt håller för godtycklig Pareto frontformer som kan beskrivas med en kontinuerlig funktion g : x  på [xmin, xmax] → g(x) (vänster diagram av Bild. 5 ), kommer vi, utan förlust av allmängiltighet, endast att överväga fronter f : x  på [0, xmax] → f (x) med f (xmax) = 0. Anledningen är att en godtycklig frontform g(x) enkelt kan omvandlas till den senare typen genom att översätta den, dvs. genom att införa ett nytt koordinatsystem x = x − xmin och y = y − g(xmax) med y = f (x ) som beskriver fronten i det nya koordinatsystemet (höger diagram av Bild. 5).................................................................. Denna översättning påverkar inte hypervolymindikatorn som beräknas i förhållande till (även översatt) referenspunkten r = (r1 − xmin, r2 − g(xmax)). Förutom att anta att f är kontinuerlig inom hela domänen [0, xmax], antar vi att f är differentiable och att dess derivat är en kontinuerlig funktion f definieras i intervallet ]0, xmax[. För ett visst antal punkter μ, som senare kommer att gå till oändligheten, skulle vi vilja beräkna optimala μ-fördelningar, dvs. positionerna för μ-punkter (x f (x)dx av konstant värde (lägre vänster tomt i Bild. 6 ), Vi ser att minimering (8) är likvärdigt med maximering av hypervolym indikator Vi antar att sekvensen konvergerar-när μ går till ∞-till en densitet δ(x) som är regelbunden nog. Formellt definieras densiteten i x  till [0, xmax] som gränsen för antalet punkter som ingår i ett litet intervall [x, x + h[ normaliseras av det totala antalet punkter μ när båda μ går till ∞ och h till 0, dvs., I följande, Vi vill karakterisera densiteten i samband med punkterna x μ 1,. .., x μ som maximerar hypervolym indikator. Som diskuterats ovan är maximering av hypervolym lika med minimering av Eq. 8. Vad är det som händer? Vi hävdar här att för ett fast antal punkter μ, minimering är också likvärdigt med att maximera hypervolym sådan att vi antar att likvärdigheten mellan minimering Eμ och maximering hypervolym också innehar för μ gå till oändlighet. Vi nu heuristically härleda 2 att gränsen densitet av Eq. 9 kommer att minimera gränsen för Eμ i Eq. - Tio. - Vad är det för fel på dig? Därför, vårt bevis består av två steg: (1) beräkna gränsen för Eμ när μ går till ∞. Denna gräns kommer att vara en funktion av en densitet δ. (2) Hitta den densitet som minimerar E(δ) := limμ→∞ Eμ. Det första steget består därför i att beräkna gränsen för Eμ. Låt oss först påminna oss några definitioner från integrationsteorin. En funktion g : [0, xmax] → R sägs vara integrerbar om xmax 0  på g (x) eller dx är ändlig (vanligtvis betecknad xmax 0  på g (x) eller dx < +∞). Den uppsättning funktioner g som är integrable är en (Banach) vektor utrymme betecknar L 1 (0, xmax). En annan Banach vektorutrymme är den uppsättning funktioner vars kvadrat är i L 1 (0, xmax), detta utrymme betecknas L 2 (0, xmax). Från Cauchy-Schwarz ojämlikhet, Heuristically deduce" betyder, vi kan inte bevisa det helt rigoröst. Detta skulle innebära funktionella analyskoncept som ligger långt utanför tillämpningsområdet för detta dokument. 3 Den Cauchy-Schwarz ojämlikhet anger att ( g 2 ) och därmed sätta g = 1, För läsbarhetens skull, bevis på föregående lemma, samt följande har skickats i bilagan. Observera att antagandet i Eq. 11 karakteriserar konvergensen av μ pekar till densiteten och behövs i beviset. Som tidigare förklarats minimerar gränstätheten för en optimal μ-fördelning E(δ). Det återstår därför att finna att densiteten minimerar E(δ). Detta optimeringsproblem finns i ett funktionellt utrymme, Banach utrymme L 2 (0, xmax) och är också ett hinder problem eftersom densiteten δ måste tillfredsställa begränsningen Begränsning optimering problem (P) som behöver lösas sammanfattas i: Anmärkning 1. För att få densiteten δF för punkter av fronten (x, f (x)) x på [0,xmax] och inte på projektionen på x-axeln, måste man normalisera föregående resultat genom normen av tangenten för punkter av fronten, dvs, 1 + f (x) 2. Därför är densiteten på framsidan proportionell mot: Som vi har sett följer densiteten som en gräns på grund av det faktum att arean mellan uppnåelsefunktionen hos lösningen inställd med μ-punkter och själva fronten (lägre högra diagram av Bild. 6 ) måste minimeras och en optimal μ-fördelning för finita punkter konvergerar till densiteten när μ ökar. Av detta följer också att antalet punkter för en optimal μ-fördelning med x-värden inom ett visst intervall [a, b] konvergerar till b a δ(x)dx om μ går till oändligheten. I nästa avsnitt kommer vi att visa experimentellt att densiteten kan användas som en approximation av optimala μ-fördelningar inte bara för en stor μ utan också för ett relativt litet antal punkter. Förutom att plotta densiteten för att förstå fördomarna i hypervolymindikatorn för specifika fronter, ger resultaten ovan också en mer allmän förklaring om hypervolymindikatorn. Från Theorem 7, vi vet att densiteten av punkter bara beror på lutningen av fronten och inte på om fronten är konvex eller konkava i motsats till utbredd tro [26, 18]. densitet och lutningen av fronten. Vi observerar att densiteten har sitt maximum för främre delar där tangenten har en lutning på -45 •. Därför optimerar hypervolym indikatorn betonar så kallade knä-punkter-delar av Pareto front beslutsfattare anser att vara intressanta regioner [5, 4, 6]. Extrema punkter är i allmänhet inte att föredra som hävdas i [7], eftersom densiteten av punkter inte beror på läget på framsidan utan bara på lutningen på respektive punkt. Lutningen varierar för olika platser på framsidan utom för det linjära fallet, så gör avståndet mellan punkter. Fördelningen av poäng kan därför skilja sig mycket från en väldistribuerad uppsättning punkter som föreslås i [16]. Genom att härleda densiteten hos punkter kunde vi undersöka fördomarna hos hypervolymen i allmänhet som vi har sett i föregående avsnitt, men frågan kvarstår vad som händer för en ändlig, särskilt ett litet antal punkter. För att besvara denna fråga genomför vi en experimentell studie med hjälp av två lokala sökstrategier för att approximera optimala μ-fördelningar för finita μ. Dessa sökstrategier tjänar till att (i) undersöka optimala μ-fördelningar för små μ på olika välkända testproblem och (ii) visar att optimala μ-fördelningar kan approximeras tillräckligt noggrant av densiteten redan för ganska små μ. Algoritmer för att hitta optimala μ-fördelningar. För att hitta en approximation av en optimal fördelning av μ-punkter, ges av deras x-värden (x μ 1,. .., x μ ), föreslår vi en enkel kulle klättrare (Algoritm 1) baserat på Eq. 3. Vad är det som händer? Den börjar med en första distribution som följer distributionsfunktionen i Theorem 7 (linje 2). En sådan fördelning erhålls genom att säkerställa att den kumulerade densiteten mellan två angränsande punkter är konstant. Dessutom läggs de två punkterna x μ 0 = xmin med f (x μ 0 ) = r2 och x μ+1 = r1 till för att förenkla slutet medan 12: avkastning (x μ 1,. .., x μ ) 13: avsluta förfarandet hanteringen av de extrema punkter. Den resulterande fördelningen av punkter följer densitet funktion av Theorem 7 med alla punkter i ordning från vänster till höger, dvs x Efter att punkterna har initierats, bidraget till hypervolym maximeras för alla punkter successivt genom att placera varje punkt enligt Eq. 3 (linjerna 6 till 8). Detta säkerställer att antingen hypervolym ökas i det aktuella steget eller motsvarande punkt redan placeras optimalt med avseende på sina grannar. Eftersom en ändring av positionen för en punkt kan ändra andra punkter som tidigare ansågs vara optimalt placerade för att vara suboptimalt placerade, upprepas förfarandet så länge förbättringen av hypervolymindikatorn är större än en användardefinierad tröskel ε (vanligtvis precisionen i programimplementeringen). Tyvärr, den optimala positionen för x μ i enligt Eq. 3 kan inte bestämmas analytiskt för vissa testproblem, t.ex. DTLZ2 [8]. I dessa fall används en modifierad version av bergsklättringsproceduren (se Algoritm 2). Efter att ha skapat en första fördelning av punkter som i Algoritm 1 (Line 2), ändras positionen för varje punkt igen separat en efter en. Men i motsats till Algoritm 1, bestäms en ny position x μ i slumpmässigt genom att lägga till ett Gaussiskt distribuerat värde centrerat kring det tidigare värdet. Inledningsvis, variansen σ 2 av denna slumpmässiga variabel är inställd på ett stort värde sådan att stora förändringar försöks. För icke-kontinuerliga frontformer (som DTLZ7 [8]) är punktens läge alternativt inställt på något värde mellan xmin och xmax. Detta möjliggör hopp av punkter till olika delar av fronten även i det senare skedet av algoritmerna. X-värdet x μ i sätts till den nya positionen x i μ och den nuvarande hypervolym v gamla uppdateras till v endast om hypervolymindikatorn ökar; annars kastas den ändrade positionen (linjerna 16–20). Om för ingen punkt en förbättring av hypervolym kunde realiseras, variansen σ 2 minskas med 5%. Så snart variansen är mindre än ε (definierad som i Algoritm 1), den aktuella fördelningen (x μ 1,. .., x μ ) returneras. Observera att båda de presenterade algoritmerna inte garanterar att hitta optimala μ-fördelningar. De experiment som presenteras i följande visar dock att de punktfördelningar som hittas av de två algoritmerna konvergerar till densiteten om μ går till oändligheten som optimala μ-fördelningar teoretiskt konvergerar till densiteten. Testa algoritmerna med hjälp av flera slumpmässiga initiala distributioner istället för enligt Eq. 14 inom funktionen InitialDist(·) i båda algoritmerna medan σ > ε do 6: förbättring ← false 7: J ← antingen 0 eller 1 (med prob. 1/2 var) 10: om J är 1 då 11: alltid leda till samma slutliga fördelning, även om konvergensen visade sig vara långsammare. Detta är en stark indikator på att de distributioner som finns verkligen är bra approximationer av den optimala fördelningen av μ-punkter. Vi vill också nämna att varje allmän sökheuristisk, t.ex. en evolutionsstrategi, skulle kunna användas för att approximera optimala μ-fördelningar. I inledande experiment till exempel använde vi CMA-ES [12] för att härleda optimala μ-fördelningar. Det visade sig att de problemspecifika algoritmerna är mycket snabbare än CMA-ES. Även när representationen används som ett tvådimensionellt problem (se Sec. 3), CMA-ES behövde signifikant mer tid än algoritmerna 1 och 2 för att härleda liknande hypervolymvärden. De distributioner som CMA-ES har funnit överensstämmer dock med de distributioner som Algoritm 1 och Algoritm 2 har funnit. Tillnärmning av optimala μ-fördelningar. Med hjälp av de algoritmer som föreslås ovan undersöker vi nu optimala μ-fördelningar för konkreta testproblem där Paretos fronter är kända. Figur 8 visar den bästa μ-distributionen för testproblemen i ZDT [24] och DTLZ [8] testfunktionssviter som är exemplariska för μ = 50 fler resultat finns på den kompletterande webbsidan http://www. tik.ee.ethz.ch/sop/muDistributioner. Dessutom ger tabell 2 motsvarande frontformer och härledda densiteter. De optimala μ-distributionerna för ZDT1, ZDT2 och DTLZ1 har approximatiserats med Algoritm 1, medan μ-distributionerna för ZDT3, DTLZ2 och DTLZ7 har beräknats med Algoritm 2 eftersom Eq. 3 kan inte lösas analytiskt eller så är fronten inte kontinuerlig. Referenspunkten har satts till (15, 15) så att de extrema punkterna finns i optimala μ-fördelningar om möjligt. De experimentellt härledda optimala μ-distributionerna för μ = 50 visar kvalitativt samma resultat som den teoretiskt förutsagda densiteten: fler punkter kan hittas i främre regioner som har en gradient på −45 •, frontdelar som har en mycket hög eller mycket låg gradient är mindre trånga. Dessutom kan liksidiga resultat för linjära fronter (teoremorna 5 och 6) observeras för den linjära DTLZ1-fronten. Konvergens mot densiteten. Från Avsnitt 6 vet vi att den empiriska densiteten i samband med optimala μ-fördelningar, d.v.s. den normaliserade histogrammet, konvergerar till densiteten när μ går till oändligheten och därför att gränstätheten i Theorem 7 approximerar den normaliserade histogrammet. Här undersöker vi experimentellt kvaliteten på approximationen. I detta syfte beräknar vi approximationer av den optimala μ-distributionen exemplariskt för ZDT2-problemet för μ = 10, μ = 100 och μ = 1 000 som erhålls med Algoritm 1. Referenspunkten har fastställts till (15, 15) som tidigare. Figur 9 visar både den experimentellt observerade histogrammet för μ-punkterna på framsidan och jämförelsen mellan den teoretiskt härledda densiteten och den erhållna experimentella approximationen av denna. Genom visuell inspektion ser vi att det histogram som är förknippat med de funna μ-distributionerna snabbt konvergerar till densiteten och att den teoretiskt härledda densiteten för μ = 1, 000 punkter redan ger en tillräcklig beskrivning av den finita optimala μ-distributionen. Denna studie ger rigorösa resultat på frågan om hur optimala Pareto front approximationer av ändlig storlek μ ser ut när hypervolym indikator maximeras. Mest förvånande kan vara det faktum att hypervolym indikatorn är okänslig för hur fronten är böjning (konvex eller konkava) som motsäger tidigare antaganden [27, 18]. Som vi visar är det inte själva frontformen utan endast frontens lutning som avgör fördelningen av punkter på fronten. Detta innebär att vid optimering av den standardiserade hypervolymindikatorn kan en jämnt fördelad lösningssats erhållas om och endast om den främre formen är en rak linje. Dessutom kan frågan om hur man väljer referenspunkten för att få extrema fronter, som förblir olösta i flera år, nu besvaras med våra teoretiska resultat. Den tydliga nedre gränsen i våra teorem kommer förhoppningsvis att hjälpa utövare. Även om de resultat som presenteras här endast gäller två mål antar vi att de generaliseras till ett godtyckligt antal mål. Utvidgningen av det föreslagna matematiska ramverket är föremål för framtida forskning.
Istället för att använda området under kurvan för att kondensera flera punkter, använder hypervolym metrisk den mer allmänna begreppet hypervolym under grenrör för detta mål REF.
Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point
{'venue': "FOGA '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}