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

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:

• Uporabi optimizacijski algoritem, s katerim je seznanjen.
• Uporabi optimizacijski algoritem, ki je bil že uporabljen za podoben problem.
• Uporabi trenutno “najpopularnejši” optimizacijski algoritem.
• Identificira značilnosti instance problema in gleda na to izbere najboljši optimizacijski algoritem.
• Primerja majhno podmnožico optimizacijskih algoritmov na manjšem številu testnih instanc problemov in izbere najučinkovitejšega.

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

• KOSTOVSKA, Ana, VERMETTEN, Diederick, DOERR, Carola, DŽEROSKI, Sašo, PANOV, Panče, EFTIMOV, Tome. OPTION: OPTImization algorithm benchmarking ONtology. IEEE transactions on evolutionary computation. Dec. 2023, vol. 27, iss. 6, str. 1618-1632, ilustr. ISSN 1941-0026.

• NIKOLIKJ, Ana, PLUHACEK, Michal, DOERR, Carola, KOROŠEC, Peter, EFTIMOV, Tome. Sensitivity analysis of RF+clust for leave-one-problem-out performance prediction. V: 2023 IEEE Congress on Evolutionary Computation (CEC): 1-5 July 2023, [Chicago]. [Piscataway: The Institute of Electrical and Electronics Engineers, 2023]. Str. [1-8], ilustr. ISBN 979-8-3503-1458-8.

• ŠKVORC, Urban, EFTIMOV, Tome, KOROŠEC, Peter. Analyzing the generalizability of automated algorithm selection: a case study for numerical optimization. V: 2023 IEEE Symposium Series on Computational Intelligence (SSCI): Mexico City, Mexico. December 5-8, 2023. Piscataway: IEEE = Institute of Electrical and Electronics Engineers, cop. 2023. Str. 335-340, ilustr. ISBN 978-1-6654-3064-7, ISBN 978-1-6654-3065-4.

• NIKOLIKJ, Ana, DOERR, Carola, EFTIMOV, Tome. RF+clust for leave-one-problem-out performance prediction. V: CORREIA, João (ur.), SMITH, Stephen (ur.), QADDOURA, Raneem (ur.). Applications of evolutionary computation: 26th European Conference, EvoApplications 2023, held as part of EvoStar 2023, Brno, Czech Republic, April 12-14, 2023: proceedings. Cham: Springer, 2023. Str. 285-301, ilustr. Lecture notes in computer science, 13989. ISBN 978-3-031-30229-9, ISBN 3-031-30229-X. ISSN 1611-3349.

• KOSTOVSKA, Ana, VERMETTEN, Diederick, DŽEROSKI, Sašo, PANOV, Panče, EFTIMOV, Tome, DOERR, Carola. Using knowledge graphs for performance prediction of modular optimization algorithms. V: CORREIA, João (ur.), SMITH, Stephen (ur.), QADDOURA, Raneem (ur.). Applications of evolutionary computation: 26th European Conference, EvoApplications 2023, held as part of EvoStar 2023, Brno, Czech Republic, April 12-14, 2023: proceedings. Cham: Springer, 2023. Str. 253-268, ilustr. Lecture notes in computer science, 13989. ISBN 978-3-031-30229-9, ISBN 3-031-30229-X. ISSN 1611-3349.

• NIKOLIKJ, Ana, DŽEROSKI, Sašo, MUÑOZ, Mario Andrés, DOERR, Carola, KOROŠEC, Peter, EFTIMOV, Tome. Algorithm instance footprint: separating easily solvable and challenging problem instances. V: GECCO'23: proceedings of the Genetic and Evolutionary Computation Conference Companion: July 15-19, 2023, Lisbon. New York: The Association for Computing Machinery, cop. 2023. Str. 529-537, ilustr. ISBN 979-8-4007-0119-1.

• CENIKJ, Gjorgjina, PETELIN, Gašper, DOERR, Carola, KOROŠEC, Peter, EFTIMOV, Tome. DynamoRep: trajectory-based population dynamics for classification of black-box optimization problems. V: GECCO'23: Proceedings of the Genetic and Evolutionary Computation Conference Companion: July 15-19, 2023, Lisbon. New York: The Association for Computing Machinery, cop. 2023. Str. 813-821, ilustr. ISBN 979-8-4007-0119-1.

• NIKOLIKJ, Ana, CENIKJ, Gjorgjina, ISPIROVA, Gordana, VERMETTEN, Diederick, DIETER LANG, Ryan, ENGELBRECHT, Andries Petrus, DOERR, Carola, KOROŠEC, Peter, EFTIMOV, Tome. Assessing the generalizability of a performance predictive model. V: GECCO'23 companion: proceedings of the Genetic and Evolutionary Computation Conference Companion: July 15-19, 2023, Lisbon. New York: The Association for Computing Machinery, cop. 2023. Str. 311-314, ilustr. ISBN 979-8-4007-0120-7.

• KOSTOVSKA, Ana, CENIKJ, Gjorgjina, VERMETTEN, Diederick, JANKOVIĆ, Anja, NIKOLIKJ, Ana, ŠKVORC, Urban, KOROŠEC, Peter, DOERR, Carola, EFTIMOV, Tome. PS-AAS: portfolio selection for automated algorithm selection in black-box optimization. Proceedings of Machine Learning research, International Conference on Automated Machine Learning, 12-15 November 2023, Potsdam, Germany. 2023, vol. 228, str. 1-17, ilustr. ISSN 2640-3498.

• KOSTOVSKA, Ana, JANKOVIĆ, Anja, VERMETTEN, Diederick, DŽEROSKI, Sašo, EFTIMOV, Tome. Comparing algorithm selection approaches on black-box optimization problems. V: GECCO'23 companion: proceedings of the Genetic and Evolutionary Computation Conference Companion: July 15-19, 2023, Lisbon. New York: The Association for Computing Machinery, cop. 2023. Str. 495-498. ISBN 979-8-4007-0120-7.

---

Nazaj na seznam za leto 2022