Ime strani: ARRSProjekti / 2022 / Auto-OPT: Avtomatizirana izbira in konfiguracija eno-kriterijskih zveznih optimizacijskih algoritmov

Auto-OPT: Avtomatizirana izbira in konfiguracija eno-kriterijskih zveznih optimizacijskih algoritmov

Nazaj na seznam za leto 2022


Oznaka in naziv projekta

J2-4460 Auto-OPT: Avtomatizirana izbira in konfiguracija eno-kriterijskih zveznih optimizacijskih algoritmov
J2-4460 Auto-OPT: Automated selection and configuration of single-objective continuous optimization algorithms

Logotipi ARRS in drugih sofinancerjev

© Javna agencija za raziskovalno dejavnost Republike Slovenije

Projektna skupina

Vodja projekta: Peter Korošec

Sodelujoče raziskovalne organizacije: Povezava na SICRIS

Sestava projektne skupine: Povezava na SICRIS

Vsebinski opis projekta

V zadnjih letih je postalo optimiranje pomembno orodje na številnih raziskovalnih področjih, kjer se uporabljajo računalniške simulacije za vrednotenje rešitev problema. Žal ni enotnega optimizacijskega algoritma, ki bi bil najboljši pri reševanju vseh možnih problemov, poznan tudi kot "no free lunch" izrek. Izbira najboljšega optimizacijskega algoritma za določeno instanco optimizacijskega problema je zato zahtevna naloga. Obstaja veliko število optimizacijskih algoritmov, med katerimi lahko uporabnik izbira. Če nameravamo poiskati najboljši algoritem za instanco problema s poskušanjem optimiranja problema z velikim številom algoritmov je to zelo dolgotrajna naloga. Večina optimizacijskih algoritmov je parametrizirana in zahteva nastavitev prametrov (tj. konfiguracijo algoritmov) za vsako reševano instanco optimizacijskega problema posebej. Torej je poleg izbire samega optimizacijskega algoritma pogosto treba določiti tudi najboljše vrednosti njegovih hiper-parametrov za reševano instanco optimizacijskega problema. Nenazadnje je tudi sama računalniška simulacija realnih problemov pogosto dolgotrajna. Torej je za določitev najboljšega optimizacijskega algoritma za dano instanco problema potrebno izbrati med številnimi algoritmi; ti imajo lahko veliko hiper-parametrov, ki jih je treba nastaviti s pomočjo dolgotrajnih računalniških simulacij. Ker je to zahtevna naloga, uporabnik običajno izbere eno od naslednjih možnosti:

Izbiro optimizacijskega algoritma olajša uporaba testnih funkcij, ki jih je treba optimirati. Te je mogoče enostavno ovrednotiti, dobro opisati s skupnimi značilnostmi (npr. unimodalnost, multimodalnost, separabilnost...) in zanje tudi poznamo optimalne rešitve. Če so znane značilnosti instance problema, se lahko najbolj obetaven optimizacijski algoritem izbere glede na rezultate, dosežene na testnih funkcijah, ki so glede na značilnosti podobne dani instanci problema.

Ko je optimizacijski algoritem izbran, se običajno uporabljajo posredne metode uglaševanja (npr. večkratno izvajanje algoritma z različnimi vrednostmi hiper-parametrov, z namenom najti najboljše nastavitve). Če računalniška simulacija rešitev problema ni zamudna, lahko tako nastavitev učinkovito izvedemo. Če pa temu ni tako, je takšno nastavljanje računsko neučinkovito. Za optimizacijske algoritme, ki uporabljajo neposredno (sprotno) uglaševanje, torej spremenijo vrednosti svojih hiper-parametrov med samo optimizacijo (glede na kakovost doslej najdenih rešitev), ta korak ni potreben. Upoštevati pa je treba, da je neposredno nastavljanje parametrov samo po sebi zahtevna naloga in lahko vodi do podaljšanja časa izvajanja optimizacijskega algoritma brez zagotovil, da bomo našli boljšo rešitev.

Osnovni podatki sofinanciranja so dostopni na spletni strani SICRIS.

Cilji projekta in opis njihove realizacije

Cilj predlaganega projekta je zagotoviti uporabniku novo ogrodje (imenovano Auto-OPT), s pomočjo katerega bo hitro in z malo truda izbral najboljši optimizacijski algoritem z najboljšimi vrednostmi hiper-parametrov glede na opis eno-kriterijskega zveznega optimizacijskega problema. Auto-OPT združuje izbiro in konfiguracijo algoritma v eno nalogo meta-učenja. Trenutno se obe nalogi obravnavata ločeno in same po sebi predstavljata velik izziv. Izbor optimizacijskega algoritma in konfiguracija hiper-parametrov bo izveden z uporabo napovednih modelov strojnega učena (ML), pridobljenih iz nenehno razvijajoče se podatkovne baze zagonov optimizacijskih algoritmov.

Cilj 1: Razviti predstavitev za opisovanje optimizacijskih problemov.

Razvite so bile predstavitve, ki se lahko uporabijo za opis lastnosti instanc optimizacijskih problemov, ki temeljijo na trajektorijah v prostoru rešitev, ki jih optimizacijski algoritmi tvorijo med svojim izvajanjem (ELA trajektorija, DynamoREP). Razvite predstavitve so ovrednotene na nalogah klasifikacije problemov in izbire algoritma. Rrazvite so bile tudi metode na osnovi nenadzorovanega učenja in teorije grafov, ki se lahko uporabijo za izbiro raznolikih in nepristranskih portfeljev problemov oz. algoritmov.

Cilj 2: Razviti ontologijo za opisovanje obnašanja optimizacijskih algoritmov.

Razvita je bila OPTION (OPTImization algorithm benchmarking ONtology) ontologija, ki zagotavlja besednjak, potreben za semantično označevanje entitet, potrebnih za opisovanje obnašanja optimizacijskih algoritmov preko značilk in mer povezanih z uspešnostjo algoritmov. Ontologjia nudi avtomatsko integracijo podatkov, interoperabilnost in raznolika poizvedovanja, in tako omogoča dostop do kakovostnih podatkov, ki so potrebni za izvajanje učinkovitega učenja raznovrstnih modelov povezanih z izvajanji optimizacijskih algoritmov. V pripravljeno ontologijo se bo tako lahko vključilo vse potrebne podatke, ki so bili in še bodo zgenerirani v sklopu projekta in jih tako učinkovito uporabili pri učenju napovednih modelov, ki bodo uporabljeni v sklopu avtomatiziranega izbora in konfiguracije optimizacijskega algoritma za izbrani optimizacijski problem.

Cilj 3: Avtomatizirati izbor in konfiguracijo optimizacijskega algoritma z uporabo strojnega učenja

Razvite so bile metodologije za preučevanje občutljivosti značilk, ki temeljijo na podlagi analiz preiskovanja pokrajin (ELA) in njihove uporabe pri avtomatizirani napovedi uspešnosti algoritmov in njihovi izbiri. Dodatno so bile razvite različne metodologije za razlago in analizo pomembnosti značilk ELA pri napovedovanju uspešnosti algoritmov. To je omogočilo razvoj postopka za generiranje odtisa algoritma, ki je definiran preko identifikacije enostavnosti oz. zahtevnosti reševanja izbranih problemov. Z generiranjem odtisa se tvorijo tudi razlage katere značilke ELA so vplivale na identifikacijo enostavnosti oz. zahtevnosti problema za posamezni algoritem. Raziskali smo tudi vplive izbire tehnike ML na uspešnost delovanja avtomatizirane izbire algoritma, kjer smo primerjali štiri modele ML pri nalogi napovedovanja najboljšega algoritma za reševanje na izbranem naboru problemov.

Bibliografske reference


Nazaj na seznam za leto 2022