Effektiviteten af ​​naturinspireret metaheuristik i dyr global optimering med begrænset budget

Globale optimeringsproblemer, hvor evaluering af den objektive funktion er en dyr operation, opstår ofte inden for ingeniørarbejde, maskinelæring, beslutningstagning, Statistikker, optimal kontrol, osv. Et generelt globalt optimeringsproblem kræver at finde et punkt x*, og værdien f(x*) er den globale (dvs. det dybeste) minimum af en funktion f(x) over et N-dimensionelt domæne D, hvor f(x) kan være ikke-differentierbar, multiekstrem, svært at evaluere selv på et tidspunkt (evalueringer af f(x) er dyre), og givet som en "sort boks". Derfor, traditionelle lokale optimeringsmetoder kan ikke anvendes i denne situation.

Blandt eksisterende derivatfri globale optimeringsmetoder kan to klasser af algoritmer markeres:stokastiske metaheuristiske algoritmer og deterministiske matematiske programmeringsmetoder. Den tidligere, på grund af deres enkelhed og attraktive naturinspirerede fortolkninger (genetiske algoritmer, partikelsværmoptimering, ildflue algoritmer, etc.), bruges af et bredt samfund af ingeniører og praktikere til at løse problemer i det virkelige liv, mens sidstnævnte aktivt studeres i den akademiske verden på grund af deres interessante teoretiske egenskaber, herunder en garanteret konvergens. Historisk set, disse to samfund er næsten fuldstændig usammenhængende:de har forskellige tidsskrifter, forskellige konferencer, og forskellige testfunktioner. På grund af hårdheden af ​​globale optimeringsproblemer og forskellige karakter af metoder fra disse to grupper, problemet med deres sammenligning er meget vanskeligt, og metoderne er samlet på nogle snesevis af testfunktioner, hvilket giver dårlig information og upålidelige resultater.

For at bygge bro mellem de to samfund, forskere ved Lobachevsky University (Rusland) og University of Calabria (Italien) Ya.D. Sergeyev, D.E. Kvasov og M.S. Mukhametzhanov har i deres seneste papir foreslået to nye effektive visuelle teknikker (kaldet operationelle zoner og aggregerede operationelle zoner) til en systematisk sammenligning af globale optimeringsalgoritmer med forskellig natur. Mere end 800, 000 kørsler på tilfældigt genererede 800 multidimensionelle testproblemer er blevet udført for at sammenligne fem populære stokastiske metaheuristika og tre deterministiske metoder, hvilket giver et nyt niveau af forståelse af de testede algoritmer. Testproblemerne er valgt pga. efter at de er blevet tilfældigt genereret, optimizeren er forsynet med placeringer af det globale minimum og af alle lokale minimizere (denne egenskab har gjort generatoren af ​​disse testproblemer meget populær - den bruges i dag i mere end 40 lande i verden). Kendskabet til den globale løsning giver mulighed for at tjekke, om den testede metode har fundet det globale optimum. Da den globale løsning i praktiske problemer er ukendt, og derfor, det er ikke muligt at kontrollere kvaliteten af ​​den opnåede løsning, det er meget vigtigt at se, hvordan forskellige metoder er tæt på den globale løsning, efter at deres stopregel er blevet opfyldt.

Forskningen udført i papiret viser, at de foreslåede operationelle og aggregerede operationelle zoner gør det muligt at sammenligne effektivt deterministiske og stokastiske globale optimeringsalgoritmer med forskellig karakter og giver en praktisk visuel repræsentation af denne sammenligning for forskellige beregningsbudgetter. De brede numeriske eksperimenter giver en ny forståelse for begge klasser af metoder og åbner for en dialog mellem de to samfund. Det kan ses, at begge klasser af algoritmer er konkurrencedygtige og kan overgå hinanden afhængigt af det tilgængelige budget for funktionsevalueringer.

Undersøgelsen er publiceret i Videnskabelige rapporter .