Sammanfattning Användningen av surrogatbaserad optimering (SBO) är vida spridd inom teknisk design för att minska antalet beräkning dyra simuleringar. Men "verkliga" problem består ofta av flera motstridiga mål som leder till en uppsättning konkurrenslösningar (Paretofronten). Målen är ofta aggregerade i en enda kostnadsfunktion för att minska beräkningskostnaden, men ett bättre tillvägagångssätt är att använda multiobjektiva optimeringsmetoder för att direkt identifiera en uppsättning Pareto-optimala lösningar, som kan användas av konstruktören för att fatta effektivare designbeslut (i stället för viktning och aggregering av kostnaderna i förväg). Merparten av arbetet inom multiobjektiv optimering är inriktat på multiobjektiva evolutionära algoritmer (MOEAs). Medan MOEAs är väl lämpade för att hantera stora, svåråtkomliga design utrymmen, kräver de vanligtvis tusentals dyra simuleringar, vilket är oöverkomligt dyrt för de problem som studeras. Därför kan användningen av surrogatmodeller i multiobjektiv optimering, betecknad som multiobjektiv surrogatbaserad optimering, visa sig vara ännu mer värt än SBO-metoder för att påskynda optimeringen av beräkning dyra system. I detta dokument föreslår författarna en effektiv multiobjektiv optimeringsalgoritm (EMO) som använder Kriging-modeller och multiobjektiva versioner av sannolikheten för förbättring och förväntade förbättringskriterier för att identifiera Paretofronten med ett minimalt antal dyra simuleringar. EMO-algoritmen tillämpas på flera standardriktmärkesproblem och jämförs mot de välkända multiobjektiva optimeringsmetoderna NSGA-II, SPEA2 och SMS-EMOA. Nyckelord Multiobjektiv optimering · Förväntad förbättring · Sannolikhet för förbättring · Hypervolym · Kriging · Gaussian process Surrogate modellering tekniker, även känd som metamodeling, blir snabbt populär i ingenjörsvärlden för att påskynda komplexa, beräkning dyra design I. Couckuyt (B) · D. Deschrijver · T. Dhaene Institutionen för informationsteknik (INTEC), Gent University-iMinds, Gent, Belgien e-post: ivo.couckuyt@ugent.be 123 576 J Glob Optim (2014) 60:575-594 problem [22, 37]. Surrogata modeller, eller metamodeller, är matematiska approximativa modeller som efterliknar beteendet hos beräkning dyra simuleringskoder såsom mekaniska eller elektriska finita element simuleringar, eller beräkningsvätska dynamiska simuleringar. Detta papper behandlar användningen av surrogatmodeller för att påskynda optimeringen av tidsödande (svart-box) problem av en deterministisk natur, i motsats till stokastisk simulering. Även om flera typer av surrogatmodellering kan särskiljas, handlar detta arbete om att integrera surrogatmodeller i optimeringsprocessen, ofta betecknad som surrogatbaserad optimering (SBO) eller metamodellassisterad optimering (MAO). SBO-metoder genererar vanligtvis surrogatmodeller i farten som endast är korrekta i vissa regioner av inmatningsutrymmet, t.ex. runt potentiellt optimala regioner. De genererade surrogatmodellerna kan sedan användas för att intelligent styra optimeringsprocessen till det globala optimala. Fokus för detta arbete är den globala SBO-metoden baserad på sannolikheten för förbättring (PoI) och förväntad förbättring (EI), populariserad av Jones et al. [25]................................................................. Dessa "statistiska kriterier" styr valet av nya datapunkter på ett sådant sätt att den objektiva funktionen optimeras, samtidigt som antalet dyra simuleringar minimeras. Fördelen med EI och PoI är att man förutom prognosen (medelvärdet) även tar hänsyn till surrogatmodellens osäkerhet (variation), vilket ger en balans mellan prospektering 1 och exploatering. 2 Oftast EI eller PoI används tillsammans med Kriging surrogate modellen (Gaussian Processes) [27] som ger genom konstruktion en förutsägelse av medelvärdet samt variansen, men andra surrogate modeller är också möjliga, såsom radial bas funktioner (RBF), stödja vektor regression (SVR) [13], etc. Det enda objektiva SBO-problemet beskrivs väl i litteraturen, men de flesta (om inte alla) "verkliga" problemen består faktiskt av flera motstridiga mål som leder till en uppsättning av Pareto-optimala lösningar. Ofta är målen aggregerade i en enda kostnadsfunktion, t.ex. med hjälp av en viktad summa, som kan optimeras genom standardoptimeringsmetoder. Därefter, genom att upprepa denna process många gånger med olika startförhållanden, t.ex. olika uppsättning av vikter, flera lösningar på Pareto front kan hittas. Å andra sidan kan en multiobjektiv optimeringsmetod optimera de olika objektiva funktionerna samtidigt, och försöka hitta Pareto fronten på bara en gång. Exempel på sådana metoder är i första hand multiobjektiva evolutionära algoritmer (MOEAs), t.ex. "Non-dominerad sorteringsgenetisk algoritm II" (NSGA-II; [14]), "Strength Pareto Evolutionary Algorithm 2" (SPEA2; [44] ) och "S-metrisk urval Evolutionär multimålalgoritm" (SMS-EMOA; [5] ). Tyvärr kräver MOEAs vanligtvis en massiv mängd funktionsutvärderingar, som är ogenomförbar för beräkning dyra simulatorer. Därför är det viktigt att spara på antalet funktionsutvärderingar, t.ex. genom att använda surrogatmodeller. Metoder för multiobjektiv surrogatbaserad optimering (MOSBO) framträdde helt nyligen i litteraturen. De flesta arbeten är inriktade på att integrera surrogatmodeller i MOEAs [41]. använda neurala nätverk för att antingen approxima fitness funktion eller som en lokal approximation teknik för att generera sökpunkter mer effektivt. Voutchkov och Keane [35] tillämpar NSGA-II-algoritmen på Kriging-modeller istället för den dyra simulatorn. För en översikt över tillgängliga tekniker och metoder hänvisas läsaren till [30, 42]. Även om PoI- och EI-metoden är väl utvecklad och används för ett mål SBO, är dess användning i MOSBO inte väl spridd. Enstaka objektiva versioner av EI och PoI används av Knowles [28] och Knowles et al. [29] för att lösa MOSBO-problem. Detta tillvägagångssätt, känd som ParEGO, använder Kriging och EI för att optimera en viktad summa av objektiva funktioner. Genom 1 Förbättra den totala noggrannheten hos surrogatmodellen (utrymmesfyllning). 2 Förbättra noggrannheten hos surrogatmodellen enbart i regionen (nuvarande) optimal. J Glob Optim (2014) 60:575-594 577 randomisering av vikterna varje iteration flera lösningar längs Pareto front kan identifieras. Mer nyligen föreslog Keane [26] multiobjektiva versioner av PoI och Euclidean distansbaserad EI. Samtidigt Emmerich et al. [17] föreslog det EI-kriterium som grundar sig på hypervolym. På samma sätt som för en viktad summa sammanställer de multiobjektiva versionerna av EI och PoI aggregerad information från surrogatmodellerna till en enda kostnadsfunktion, som balanserar mellan prospektering (se fotnot 1) och utnyttjande. 3 Tyvärr ges endast formler för två objektiva funktioner av Keane eftersom de statistiska kriterierna blir ganska besvärliga och komplexa för ett större antal objektiva funktioner. På samma sätt, medan Emmerich et al. [16] Beskriv formler för ett godtyckligt antal dimensioner för det EI som baseras på hypervolym, beräkningskostnaderna ökar minst exponentiellt med antalet mål och har därför endast tillämpats på två mål. Det viktigaste bidraget i detta dokument är en effektiv multiobjektiv optimeringsalgoritm (EMO) som är en mycket effektivare metod för att utvärdera multiobjektiva versioner av PoI- och EI-kriterierna för multiobjektiva optimeringsproblem. Det aktuella problemet liknar i själva verket beräkningen av hypervolym (en Pareto set quality estimator) [45] som kommer att visas nedan och därför kan hypervolymalgoritmer anpassas för att underlätta utvärderingen av de statistiska kriterierna. Dessutom föreslås ett nytt statistiskt kriterium, baserat på det hypervolymbaserade EI, som är betydligt billigare att beräkna men ändå ger lovande resultat. I Sect. 2 Kriging surrogate modellen diskuteras kortfattat. I Sect. 3, en översikt över EMO algoritm ges, inklusive allmänna uttryck för PoI och flera varianter av EI. Därefter diskuteras en grundläggande del som behövs för beräkningen av de statistiska kriterierna i Sect. 3.4. När det gäller de åtgärder som avses i artikel 3.1 a i förordning (EU) nr 1094/2010 ska de åtgärder som föreskrivs i denna förordning vara förenliga med yttrandet från den kommitté som inrättats i enlighet med artikel 15.1 i förordning (EU) nr 182/2011. Efteråt, i Sect. 4 EMO-algoritmen testas på flera funktioner från DTLZ-riktmärkets svit [15]. Äntligen, i Sect. 5 slutsatser och framtida arbete diskuteras. Kriging är en populär surrogatmodell för att approximera deterministiska bullerfria data, och har visat sig vara mycket användbar för uppgifter som optimering [25], design utrymme prospektering, visualisering, prototyper och känslighetsanalys [37]. En grundlig matematisk behandling av Kriging ges i [19, 33]. I grund och botten, Kriging är en tvåstegsprocess: först en regressionsfunktion h (x) konstrueras, och därefter, en centrerad Gaussian process Z med varians σ 2 och en korrelationsmatris  till är konstruerad genom resterna. Överväg en uppsättning n prover, ( 2) och tillhörande funktionsvärden, y = (y 1,. ., y n ), där (· ) är införlivandet av en vektor eller matris. I huvudsak är regressionsdelen kodad i n× p-modellens matris F med hjälp av basfunktioner medan den stokastiska processen huvudsakligen definieras av n × n- korrelationsmatrisen  på den plats där  till(·, ·) är korrelationsfunktionen. (·, ·) parameteriseras av en uppsättning hyperparametrar. Valet av korrelationsfunktion är avgörande för att uppnå god noggrannhet. Detta papper fokuserar på att använda Matérn korrelation funktion [34], med v = 3 2, Matérn vs= Dessutom används också den populära Gaussian korrelation funktion, De hyperparametrarna är identifierade med Maximum Likelihood Estimation (MLE). I synnerhet den negativa koncentrerade log-likelihood minimeras, där. Därefter härleds prognosmedelvärdet och förutsägelsen variansen av Kriging, respektive som, var är modellmatrisen av prediktionspunkten x, α är en p × 1 vektor som anger koefficienterna för regressionsfunktionen, bestämd av generaliserade minst kvadrater (GLS), och r (x) är en 1 × n vektor av korrelationer mellan punkten x och proven X. Effektiv multiobjektiv optimering (EMO) Ett flödesschema över EMO-algoritmen visas i bild. 1................................................................ Först genereras och utvärderas en första uppsättning punkter X på de dyra objektiva funktionerna f j (x), för j = Kriging modeller uppdateras med denna nya information och denna process upprepas på ett iterativt sätt tills vissa stoppkriteriet uppfylls. Av särskilt intresse är PoI och EI statistiska kriterier som i stor utsträckning används för en objektiv optimering [10, 24]. Därför kan det vara användbart att utvidga konceptet PoI och EI direkt till multiobjektiv optimering. Multiobjektiva versioner av PoI och EI definieras för ett godtyckligt antal objektiva funktioner i Sects. 3.2 och 3.3. För att underlätta noteringen i de kommande avsnitten kan utdata från alla Kriging-modeller betraktas som ömsesidigt oberoende Gaussiska slumpvariabler Y j (x), Den tillhörande sannolikhetstäthetsfunktionen J och den kumulativa fördelningsfunktionen 0 j av Y j (x) är kompakt betecknade som, Med tanke på en uppsättning av n punkter X som i (2), en Pareto-uppsättning P kan konstrueras som omfattar v ≤ n Pareto-optimala (icke-dominerade) lösningar, Varje lösning f(x * i) är en vektor som innehåller de objektiva funktionsvärdena för en associerad ingångspunkt 3.2 Sannolikhet för förbättring (PoI) Utvärdera sannolikheten att de objektiva funktionsvärdena för en ny ingångspunkt x är belägna inom en väldefinierad region A i det objektiva utrymmet kräver en multidimensionell integration över den regionen. Naturligtvis kan flera varianter av den multiobjektiva PoI konstrueras eftersom begreppet förbättring är tvetydigt definierat i samband med multiobjektiv optimering. Detta återspeglas i valet av integrationsregion A, t.ex., A kan vara den icke-dominerade delen av det objektiva utrymmet eller A kan vara den region i det objektiva utrymme som endast sträcker (och inte dominerar) Pareto uppsättningen, etc. I allmänhet är sannolikheten att en ny ingångspunkt x ger förbättring över Pareto uppsättning P betecknad av PoI P[I ], att utvärdera Eq. (10) kan integrationsområdet A brytas ned i q- (hyper-)rektangulära celler, som ger en ändlig sammanfattning av bidragande termer, se bild. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Den nedre och övre gränsen [l k, u k ] för varje cell, för k = 1...... kommer att beräknas i Sect. 3.4. När det gäller de åtgärder som avses i artikel 3.1 a i förordning (EU) nr 1094/2010 ska de åtgärder som föreskrivs i denna förordning vara förenliga med yttrandet från den kommitté som inrättats i enlighet med artikel 15.1 i förordning (EU) nr 182/2011. Medan cellerna kan väljas för att separera täcker integrationsområdet A, algoritmen som beskrivs i Sect. 3.4 Region A bryts ned i överlappande celler. I detta fall kan cellerna förneka det överlappande bidraget från andra celler genom subtraktion, betecknat med ±-symbolen i ekv. (11). Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Även om PoI-kriteriet redan är ganska användbart och okänsligt för skalningen av de objektiva funktionerna, uppmuntrar det inte nödvändigtvis skapandet av en enhetlig Pareto uppsättning. EI kvantifierar mängden förbättringar med hjälp av en förbättringsfunktion I (y, P) och föredrar därför lösningar som ligger längre från befintliga medlemmar i Pareto set. EI-integralen definieras som J Glob Optim (2014) 60:575-594 581 I motsats till de olika typerna av PoI-kriterier (t.ex., dominerande 4 Pareto punkter eller förlänga Pareto set som i Sect. 3.2) är det rimligare att endast integrera EI-kriterierna i region A som motsvarar den icke-dominerade delen av det objektiva utrymmet. Förbättringsfunktionen kommer automatiskt att föredra nya poäng som dominerar de flesta poäng inom Pareto ställa P (den största förbättringen). När inga sådana punkter hittas, uppmuntrar förbättringsfunktionen valet av punkter som utökar Pareto ställa P på ett enhetligt sätt. Därför är utformningen av förbättringsfunktionen för EI avgörande för att identifiera en optimal och enhetlig Pareto set. En bra teoretisk översikt över olika typer av EI ges av [36], inklusive arbete med skalar förbättring funktioner [16, 26] samt använda den enda-mål EI i en multiobjektiv inställning [23, 28]. Nedan fokuserar vi på att utvärdera den Euclidean distansbaserade EI [26] samt den hypervolymbaserade EI [16, 17] effektivt för många mål. Dessutom föreslås en förenklad version av den hypervolymbaserade EI som är betydligt billigare att beräkna. Den hypervolymmetriska (eller S-metriska) [45] används i stor utsträckning i multiobjektiv optimering för att bedöma kvaliteten på en Pareto-uppsättning eller för att driva multiobjektiva optimeringsalgoritmer [5]. Hypervolymindikatorn H(P) anger volymen i den region som domineras av Pareto-uppsättningen P, avgränsad av en referenspunkt r som måste domineras av alla punkter i Pareto-uppsättningen, se bild. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Större värden av hypervolym indikerar bättre Pareto uppsättningar. Dessutom, den exklusiva hypervolym (eller hypervolym bidrag, se bild. 2b ) av en Pareto uppsättning P i förhållande till en punkt p definieras som, H exc mäter bidraget (eller förbättringen) av punkten p till Pareto uppsättningen P och, därför, kan också användas för att definiera en skalar förbättring funktion, nämligen, därefter, integralen av den hypervolym-baserade EI är, där A är den icke-dominerade regionen (bundet av referenspunkt r). Inledningsvis föreslogs en approximation av den hypervolymbaserade EI med hjälp av Monte Carlo-teknik [17]. Nyligen, Emmerich et al. [16] föreslog en metod för att beräkna den exakt för ett godtyckligt antal dimensioner genom att dela upp den icke-dominerade regionen i en uppsättning celler, vilket också görs i detta arbete. Tyvärr antar de föreslagna matematiska uttrycken [16] att den icke-dominerade regionen bryts ned i ett enhetligt rutnät av celler baserat på Pareto-uppsättningen, se cellerna avgränsade av de streckade linjerna i bild. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Därför, antalet celler som krävs för att utvärdera kriteriet skala minst exponentiellt med antalet Pareto punkter och mål. För varje cell måste dessutom en separat beräkning av hypervolym göras, och därför är det omöjligt att tillämpa metoden för tre mål eller högre. Detta 123 582 J Glob Optim (2014) 60:575-594 arbete utvecklar ett nytt matematiskt uttryck för den hypervolymbaserade EI som lindrar några av dess beräkningskomplex genom att dekomprimera den icke-dominerade regionen till en mycket mindre uppsättning celler samt ta bort de separata hypervolymberäkningarna. I motsats till andra statistiska kriterier, de föreslagna uttrycken för den hypervolymbaserade EI kräver att den icke-dominerade regionen omfattas av en uppsättning av separata celler, då den hypervolym-baserade EI kan skrivas i sluten form som, där I C k betecknar förbättringen bidraget av cell k, nämligen, För varje cell k = 1..... bidrag beräknas per dimension enligt följande, Det finns flera sätt en cell k kan bidra till I C k beroende på dess position i förhållande till cell k, se bild. 3............................................................... Cell k representeras av den mörka skuggade cellen. Paren (·, ·) inuti varje cell k = 1.... q betecknar typ av bidrag (A, B eller C) per dimension. A, B och C hänvisar till ekvationerna i den styckevisa funktionen G, se föregående tabell. Om en cell är helt täckt av cell k i en enda dimension, är dess längd i den dimensionen alltid inkluderad (typ B). Om en cell endast delvis täcks av cellen k delas bidraget upp i två delar: integrationen när cellen eventuellt är helt täckt (första raden av A; noll om en j ≤ l j ) och när cellen delvis täcks (andra och tredje raden av A). Om en cell inte omfattas av någon Korrektheten hos denna algoritm har verifierats genom en omfattande numerisk jämförelse mot den allmänt tillgängliga koden för Emmerich et al. [16] för det två objektiva fallet. Dessutom har de två och tre objektiva fallen kontrollerats med hjälp av Monte Carlo-metoder. Oavsett om det nya förfarandet redan är betydligt billigare än den metod som Emmerich et al. [16], denna hypervolymbaserade EI är fortfarande dyrare att utvärdera än andra statistiska kriterier. Detta beror på att beräkningstiden är mer känslig för antalet celler samt beroendet av en binär uppdelning av den icke-dominerade regionen i separata celler, vilket kräver fler celler för att täcka integrationsområdet än Walking Fish Group (WFG) algoritmen förklaras i Sect. 3.4. När det gäller de åtgärder som avses i artikel 3.1 a i förordning (EU) nr 1094/2010 ska de åtgärder som föreskrivs i denna förordning vara förenliga med yttrandet från den kommitté som inrättats i enlighet med artikel 15.1 i förordning (EU) nr 182/2011. Därför föreslås en förenkling av den hypervolymbaserade EI i nästa avsnitt som kan utvärderas med hjälp av WFG-algoritmen. Inspirerad av definitionen av den hypervolym-baserade EI [16], kan den hypervolym-baserade PoI skrivas som produkten av förbättringsfunktion I (μ, P) och PoI P[I ], och så fördelarna med att använda hypervolym bidrag kan bevaras samtidigt avsevärt minska den totala beräknings komplexitet, där I (μ, P) definieras som i (14) och μ = (μ 1 (x),. ., μ m (x) är en vektor som innehåller förutsägelsen av Kriging modeller av varje objektiv funktion för en punkt x. I själva verket, förutsägelsen varians inte beaktas längre för förbättringsfunktionen, i motsats till E I hv, eftersom det flyttas utanför integralen. Integrationsområdet A för P[I ] motsvarar den icke-dominerade regionen och därför kan ett slutet uttryck för den hypervolymbaserade PoI härledas från samma uppsättning celler som används för att utvärdera P[I ], se bild. 2b, nämligen, 123 584 J Glob Optim (2014) 60:575-594 där Keane [26] definierar EI som produkten av PoI P[I] och en Euclidean distansbaserad förbättringsfunktion. Låt f c vara lösningen i P som ligger närmast centroiden (x) av P[I ] integral, där viktvektorn w = (w 1,. .., w m ) används för att skala de objektiva funktionerna i samma intervall och, med centroiden över godtyckliga integral gränser [l, b] definieras av. Slutligen definieras E euklid [I] för en indatavektor x som, liksom alla andra EI-kriterier integrationsområdet A av P[I ] och på (x) är den icke-dominerade regionen. För att kunna utvärdera dessa statistiska kriterier på ett effektivt sätt måste en eller flera integraler utvärderas över ett integrationsområde A. Eftersom A är icke-rektangelformad och ofta oregelbundet formad, särskilt för ett högre antal objektiva funktioner, måste integralen först sönderdelas i en summa k integraler över rektangulära celler. Även om dessa celler kan identifieras analytiskt i förväg för två syften [26] eller en kan använda de mest finkorniga celler som är möjliga (för totalt q  på (v + 1) m celler; [16] ), blir detta ganska oöverkomligt komplicerat och besvärligt för ett större antal objektiva funktioner (>2). J Glob Optim (2014) 60:575-594 585 I stället föreslår författarna att integrationsområdet bryts ned i så få celler som möjligt med hjälp av en effektiv datoralgoritm, dvs varje cell omfattar en stor del av integrationsområdet. En enkel metod för att bestämma cellernas nödvändiga gränser för utvärderingen av kriterierna är att använda binär partitionering [11], se bild. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Även om detta tillvägagångssätt är ganska flexibelt eftersom det gör det möjligt att identifiera olika typer av integrationsområden (t.ex. leder till flera varianter av statistiska kriterier), blir det oöverkomligt dyrt eftersom antalet mål överstiger fyra. Icke desto mindre, genom att avsluta den binära partitionering tidigt de statistiska kriterierna kan fortfarande approximeras ganska bra för ett högre antal mål. Fokus för detta arbete är dock att förbättra den exakta utvärderingen av kriterierna. Därför är det vettigt att dra nytta av de många algoritmerna för beräkning av hypervolym. Formellt, hypervolym är Lebesgue integral, där A är regionen domineras av Pareto ställa P och avgränsas av någon referenspunkt r. Eftersom de statistiska kriterierna är integraler utvärderas över ett liknande område, men med hjälp av en annan integrand, är tanken att anpassa en hypervolym rutin och hämta integrationsområdet A som en uppsättning celler i stället för att omedelbart beräkna sin (hyper)volym. Exakta algoritmer [3, 4, 31, 43] för beräkning av hypervolym och approximationer [1, 2, 7, 8, 20, 28] och alternativa versioner av hypervolymproblemet, t.ex. att hitta Pareto-punkten/-punkterna som minst bidrar till hypervolym [9], har föreslagits i litteraturen. Medan algoritmen föreslås av Beume et al. [3] har det bästa värsta fallet komplexitet, WFG-algoritmen [39] är faktiskt snabbare på de flesta praktiska optimeringsproblem och är därför anpassad i detta arbete för att utvärdera de statistiska kriterierna. Den grundläggande WFG algoritmen fungerar genom att definiera hypervolym som en summa av exklusiva hypervolymer, som ursprungligen infördes av [18], där varje exklusiv hypervolym i summan motsvarar en av de skivor som avgränsas av streckade linjer i Bild. 4........................................... Vid första anblicken kan detta se dyrt ut eftersom den exklusiva hypervolym (13) per definition kräver två separata beräkningar av hypervolym. Lyckligtvis kan flera optimeringar göras utifrån följande huvudidéer, se bild. 4........................................... -Slices till vänster om den bidragande punkten p (dvs. med mindre värden än p i det nuvarande målet) kan kasseras eftersom de inte innehåller någon hypervolym som domineras av p. -Om p domineras i de återstående (obearbetade) målen dominerar den inte mer exklusiv hypervolym. Fördelen med dessa insikter kan tas genom att skriva om den exklusiva hypervolymen från (13) som H exc (p; P) = H({p}) − H(P ), där P = {limit(p, q) och gräns (p, q) = (max{ p 1, q 1 },. ...., max p m, q m }.................................................................................................... Den första termen H({p}) är helt enkelt volymen av den cell som avgränsas av p och referenspunkten r, den andra termen H(P ) är en rekursion där hypervolymen beräknas för P. P erhålls genom att ta den maximala (gräns) för den bidragande punkten och för varje punkt i P, dvs punkterna projiceras på p, se bild. 4........................................... Självklart kommer många punkter att införas som domineras av någon annan punkt i P. Dessa punkter bidrar inte något till hypervolym och kan tas bort genom att ta den icke-dominerade delmängd av P innan kontinuerlig beräkning. Det är detta sista steg som väsentligt Ett steg i WFG algoritm för att beräkna H exc (f 2 = p; {f 3, f 4 }), betecknad av den skuggade regionen (f 1 har redan bearbetats). Den exklusiva hypervolymskivan beräknas effektivt som volymen av cellen som begränsas av p och r minus hypervolymen av en reducerad Pareto-uppsättning, representerad av kvadraterna, där alla punkter begränsas av den bidragande punkten p. Detta skapar många dominerande punkter som kan tas bort innan beräkningen fortsätter. I denna illustration subtraheras volymen av cellen som avgränsas av f3 och r för att beräkna den exklusiva hypervolymen förbättrar prestandan eftersom det har visats att de flesta datauppsättningar redan förlorar över 50 % av sina poäng efter endast en rekursion. Observera att om den bidragande punkten p i allmänhet har högre objektiva värden då sannolikt fler punkter kan beskäras. Därför är det vettigt att bearbeta de värre Pareto punkter först genom att sortera Pareto ställa P fallande på det aktuella målet före varje iteration. Dessutom kan nu beräkningen av hypervolym också klippas på det sorterade målet varje rekursion, därav användningen av termerna nuvarande mål och obearbetade mål i föregående stycke. Varje rekursion det aktuella målet sorteras och beaktas inte i efterföljande beräkningar av H exkl., för mer information om denna optimering se [38]. Detta liknar Hypervolym av Slicing Målalgoritm (HSO; [40] ). En slutlig optimering är basfallet för två mål, för vilka vi enkelt kan beräkna hypervolym i O(v) förutsatt att Pareto-uppsättningen sorteras på det aktuella målet. Grundscenariot för två mål liknar den algoritm som föreslås av [26] för att beräkna den Euclidean-sträckabaserade förväntade förbättringen och WFG-algoritmens prestanda är därför minst lika med den. WFG-algoritmen är lätt anpassad för att föra ett register över en cells nedre och övre gräns istället för att beräkna dess hypervolym. Den anpassade WFG-algoritmen, vid minimering, identifierar de celler som domineras av Pareto-uppsättningen. Naturligtvis kan algoritmen modifieras för att hitta den dominerade regionen genom att tillfälligt betrakta den som ett maximeringsproblem. För utvärderingen av de statistiska kriterierna, särskilt EI, är det dock mycket mer användbart att identifiera den icke-dominerade regionen. Detta uppnås genom att subtrahera de celler som erhålls från den anpassade WFG-algoritmen från den cell som täcker m (eventuellt avgränsad av en referenspunkt r vid användning av ett av de hypervolymbaserade kriterierna), se bild. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Därför kan den anpassade WFG-algoritmen användas för statistiska kriterier där integrationsområdet A motsvarar antingen den dominerade eller icke-dominerade regionen. Om andra integrationsområden krävs, t.ex. för att beräkna sannolikheten för att en ny punkt dominerar minst två Pareto-punkter, kan mer flexibla men långsammare metoder såsom binär partitionering [11] användas. för en godtycklig inmatningspunkt x ingår också för 2D-fallet. I motsats till den föreslagna algoritmen måste exi2D-algoritmen köras flera gånger under optimeringen av kriterierna Efter att q < < (v + 1) m-uppsättningar celler (= integrerade gränser) har identifierats kan de faktiska PoI- och EI- statistiska kriterierna utvärderas med hjälp av EKG. (10), (20), (16) eller (18). Vid utvärdering av kriterierna ersätts punkten f max + med (◀,. .., ∞) eller r beroende på kriteriet. En plott med den praktiska beräkningstiden och cellernas antal visas i bild. 5a, b, tillämpa anpassade WFG algoritm till uppsättningar av Pareto punkter slumpmässigt dras från den första kvadranten av en enhet sfär (med medelvärdet av 1000 upprepningar). Beräkningstiden för cellerna utgör inget problem för utvärderingen av kriterierna (väl inom sekunderna intervall). Den begränsade faktorn för EMO-algoritmen är antalet celler integrationsområdet A bryts ner i, som för varje cell motsvarande PoI eller EI ekvationer måste utvärderas som kan bli oöverkomligt dyrt när många celler krävs för att identifiera integrationsområdet A. Nedbrytningen av integrationsområdet A i celler och den faktiska utvärderingen av kriterierna PoI och EI är separat i den meningen att cellerna bara behöver identifieras en gång varje provtagning iteration, och sedan endast om (mellanliggande) Pareto-uppsättningen har förändrats med avseende på den tidigare iterationen. Därefter kan kriterierna PoI och EI utvärderas flera gånger 123 588 J Glob Optim (2014) 60:575-594 för en punkt x, t.ex., under optimering, med samma uppsättning celler. Slutligen är hypervolym indikatorn också lätt att få genom att summera volymen av cellerna. Exempel En bra uppsättning konfigurerbara multiobjektiva referensproblem har föreslagits av Deb et al. [15], varav fyra referensfunktioner väljs och anpassas något för att jämföra EMO-algoritmen. En sammanfattning av de valda referensfunktionerna finns i tabell 1. För en fullständig beskrivning av referensfunktionerna hänvisar författarna till [15]. Alla referensfunktioner är konfigurerade för att ha sex indataparametrar. Det första exemplet är DTLZ1-funktionen med tre objektiva funktioner där Paretofronten ligger på planet y 1 + y 2 + y 3 = 1. Det andra exemplet är DTLZ2-funktionen med tre objektiva funktioner där Paretofronten är den första kvadranten av en enhet sfär centrerad på ursprunget. Det tredje exemplet är DTLZ7-funktionen med fyra objektiva funktioner som har 2 m−1 = 2 4−1 = 8 frånkopplade Pareto-optimala regioner i det objektiva utrymmet. Det sista exemplet, DTLZ5-funktionen konfigurerad för att ha sex objektiva funktioner, liknar DTLZ2 förutom att Pareto-fronten bara är en del av enhetens hypersfär, dvs. Pareto-fronten är en (densely befolkad) kurva i ett m = 6-dimensionellt målutrymme. En första uppsättning av 65 prover genereras av en nästan optimal maximin Latin Hypercube Design (LHD; [12] ). Därefter optimeras ett statistiskt kriterium för varje iteration för att välja nästa punkt att utvärdera. Kriteriet optimeras med hjälp av en kombination av Monte Carlo provtagning och en lokal sökning. Närmare bestämt genereras och utvärderas 20 × n kandidatpoäng för Monte Carlo utifrån kriteriet. Den bästa Monte Carlo kandidaten förfinas ytterligare med hjälp av Matlabs fmincon optimizer. Olika konfigurationer av EMO-algoritmen tillämpas på referensfunktionerna. I synnerhet är EMO konfigurerad med E I euklid- och P hv-kriteriet tillsammans med Kriging-modeller med hjälp av Matérns korrelationsfunktion [32] med v = 3 2 och en konstant regressionsfunktion (M = 1 och F = 1). Kriging-modellernas hyperparametrar är optimerade med hjälp av SQPLab [6] (http://www-rocq.inria.fr/ gilbert/modulopt/optimering-rutiner/ sqplab/sqplab.html) och använder sannolikt derivatinformation. Den valfria viktvektorn w i E I-euklid-kriteriet är satt till 1 för alla referensfunktioner, utom för DTLZ7 där w = (1, 1, 1, 0,02) för att skala den sista objektiva funktionen i samma intervall som de andra objektiva funktionerna. Dessutom, EMO körningar av E I euklid kriterium upprepas med Kriging modeller med hjälp av Gaussian korrelation funktion, dessa körningar betecknas av E I gauss euklid i resultaten. J Glob Optim (2014) 60:575-594 589 Slutligen konfigureras extra EMO-körningar för DTLZ1- och DTLZ2-funktionerna med hjälp av det dyra E I hv-kriteriet med Kriging-modeller med hjälp av Matérn korrelation. E I hv-kriteriet tillämpas inte på problemen med DTLZ5 och DTLZ7. Var och en av de totalt 14 EMO-körningarna upprepas 10 gånger för statistisk robusthet och stannar när urvalsbudgeten uppfylls, nämligen 250 prov. EMO-drifterna jämförs mot de evolutionära algoritmerna NSGA-II, SPEA2 och SMS-EMOA med varierande populationsstorlek och maximalt antal generationer. Den första körningen är konfigurerad med en populationsstorlek på 25 och ett maximalt antal generationer av 10 (totalt urval budget 250) och den andra körningen är konfigurerad med en populationsstorlek på 50 och ett maximalt antal generationer av 50 (totalt urval budget 2.500). De återstående parametrarna har lämnats till sina standardvärden. På samma sätt som EMO körs, den evolutionära algoritmen körs upprepas 10 gånger. Förutom att bedöma algoritmernas prestanda med hjälp av hypervolymmätaren används även konvergensmåttet. Konvergensmåttet är medelvärdet av varje punkt i Pareto inställd till närmaste Pareto-punkt på den kända Pareto-fronten. I detta verk representeras de kända Paretofronterna av 100.000 Monte Carlo-poäng. Resultaten för referensfunktionerna har sammanfattats i tabell 2. Observera att skillnaderna i metriska hypervolymer är större än de visas på grund av det försiktiga valet av referenspunkt r (behöver anpassas till resultaten från alla provningskonfigurationer). I allmänhet ses att EMO körs har bättre prestanda än MOEAs när det gäller hypervolym poäng för de flesta funktioner utom DTLZ1. Efter en närmare granskning kan man konstatera att noggrannheten hos Kriging-modellerna av DTLZ1 för de flesta statistiska kriterier är suboptimal. I synnerhet är den första objektiva funktionen svår att uppskatta med hjälp av Kriging-modellerna, se bild. Detta anslag är avsett att täcka utgifter för tjänstemän och tillfälligt anställda som arbetar inom politikområdet Migration och inrikes frågor. En ritning över de sista Pareto-uppsättningarna som genererats av DTLZ2-problemet visas i bild. 7............................................................ Det ses att de hypervolym-baserade kriterierna betonar kanterna på Pareto front mer samtidigt som ett litet mellanrum mellan kanten och den inre delen av Pareto front. Detta är inte olikt resultaten från DTLZ2 enligt uppgifter från [5] och beror på hypervolymindikatorns karaktär. Logiskt, ju längre bort referenspunkten är placerad, desto större kommer den exklusiva hypervolymen att vara för punkter som ligger på kanten av den nuvarande Pareto-uppsättningen (eftersom den exklusiva hypervolymen då enbart begränsas av referenspunkten). Ytterligare forskning behövs för att avgöra vilken inverkan valet av referenspunkt r har på de statistiska kriterierna [1]. Medan EMO algoritm överträffar MOEAs på hypervolym indikator på de flesta problem, det finns vissa begränsningar. EMO algoritmen, och andra MOSBO tekniker, förlitar sig på kvaliteten på surrogatmodellen för att vägleda valet av nya dyra datapunkter. Kriging modellerna behöver inte vara korrekt i början av algoritmen när man använder EI och PoI kriterier, men de bör kunna fånga beteendet hos de objektiva funktionerna tillräckligt bra när tillräckligt med prover blir tillgängliga, vilket kanske inte alltid är fallet (se bild. 6 och DTLZ1 resultat). Dessutom kommer konstruktionen av Kriging modellerna och utvärderingen av de statistiska kriterierna till en beräkningskostnad, liknande beräkningskostnaden för MOEAs som förlitar sig på hypervolym (dvs. SMS-EMOA), som kan begränsa den praktiska användningen av EMO algoritm för vissa (mindre dyra) optimeringsproblem. Särskilt konstruktionen av Kriging-modellerna och den noggranna optimeringen av de statistiska kriterierna gör EMO-algoritmen dyrare än SMS-EMOA. Dessutom kräver 123 590 J Glob Optim (2014) 60:575-594 EMO-algoritmen lagring av de integrerade gränserna i minnet, vilket kan vara oöverkomligt dyrt för ett större antal mål. Författarna presenterade EMO algoritmen, som använder multiobjektiva versioner av PoI och EI för att identifiera Pareto fronten med ett begränsat urval budget. Olika konfigurationer av EMO algoritmen jämförs mot de välkända SPEA2, NSGA-II och SMS-EMOA evolutionära metoder med lovande resultat. I teorin kan ett godtyckligt antal objektiva funktioner hanteras. I praktiken undgår emellertid EMO-algoritmen inte heller i fråga om antalet objektiva funktioner och antalet Pareto-poäng på grund av karaktären av de multiobjektiva kriterierna för EI och PoI-statistik. Icke desto mindre kan EMO-algoritmen tillämpas på problem upp till åtta mål. Dessutom bör det noteras att ett stort antal mål i praktiken ofta aggregeras till ett mindre antal mål (≤4) med hjälp av t.ex. viktade belopp, eftersom sådana högdimensionella utrymmen inte är lätt att tolka för formgivare. Det framtida arbetet kommer att inriktas mer på att undersöka de viktigaste fördelarna med EMO-algoritmen för olika industriella tillämpningar och problem med riktmärken. Preliminära resultat visar att fördelarna med EMO-algoritmen är mer uttalade när de begränsas till ett mycket lågt antal funktionsutvärderingar (<100). Dessutom kan fördelarna med att använda statistiska kriterier, som balanserar prospektering och utnyttjande automatiskt, visa sig mer för problem med ett komplext optimeringslandskap och flera lokala Pareto fronter. Dessutom kommer det framtida arbetet att fokusera på att minimera antalet celler och på ett iterativt uppdateringsschema för cellerna, vilket kommer att vara betydligt effektivare än att räkna om cellerna nästan varje iteration. Indirekt kan en upptrappning också uppnås genom att välja flera uppdateringspunkter åt gången. Slutligen kan det också vara värt att undersöka användningen av approximerade statistiska kriterier, nämligen att anpassa rutiner för approximation av hypervolymer för nedbrytning av integrationsområdet i celler.
Nyligen, Couckuyt et al. REF publicerade en algoritm som är snabbare baserad på empiriska tester.
Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization
{'venue': None, 'journal': 'Journal of Global Optimization', 'mag_field_of_study': ['Mathematics', 'Computer Science']}