Učenje predstavitev pokrajin za razlago kakovosti stohastičnih optimizacijskih algoritmov

Nazaj na seznam za leto 2022

Oznaka in naziv projekta

N2-0239 Učenje predstavitev pokrajin za razlago kakovosti stohastičnih optimizacijskih algoritmov
N2-0239 Representation Learning of Landscape Spaces for Explainable Performance of Stochastic Optimization Algorithms

Logotipi ARRS in drugih sofinancerjev

Projektna skupina

Vodja projekta: doc. dr. Tome Eftimov

Sodelujoče raziskovalne organizacije: Povezava na SICRIS

Sestava projektne skupine: Povezava na SICRIS

Vsebinski opis projekta

Pri evolucijskem računanju (ER), delu računalniške inteligence, so glavne raziskave osredotočene na razvoj algoritmov za globalno optimizacijo, ki se zgledujejo po biološki evoluciji. Raziskovalci dokazujejo njihovo inovativnost z uporabo teorije primerjalne analize (angl. benchmarking theory), ki omogoča analizo delovanja algoritmov na osnovi izbranih performančnih mer kakovosti glede na zbirko instanc primerjalnih problemov. Čeprav so se ti algoritmi izkazali kot zelo učinkoviti pri reševanju številnih problemov, ostaja njihov inkrementalni razvoj še zmeraj odprt raziskovalni problem.

Glavna naloga primerjalne analize v evolucijskem računanju zajema oceno uspešnosti algoritma (zlasti na novo uvedenega) v primerjavi z drugimi algoritmi. Pri tem se pojavijo tri pomembna vprašanja, ki jih je potrebno previdno obravnavati: i) katere instance problema je potrebno izbrati za primerjalno študijo (tj. raziskovanje prostora problema), ii) kako oblikovati eksperimente, ki vodijo do ponovljivosti in ponovljivih rezultatov (tj. raziskovanje relacij med algoritmom, problemom in prostorom uspešnosti) in iii) katere mere uspešnosti je potrebno analizirati in s katerim statističnim pristopom (tj. raziskovanje podatkov o prostoru uspešnosti).

Primerjalna analiza je v ER ključna pri ovrednotenju uspešnosti (novo uvedenega) optimizacijskega algoritma napram drugim algoritmom. Teorija primerjalne analize vključuje tri glavna vprašanja: i) katere probleme je treba izbrati za primerjalno analizo, ii) kako nastaviti poskuse in iii) kako ovrednotiti uspešnost. Predlagani projekt se bo osredotočil na metodologije, ki se uporabljajo za ustrezen nepristranski izbor optimizacijskih problemov, ki bodo uporabljeni za nadaljnjo analizo.

Čeprav je bil s predlaganimi bolj robustnimi statističnimi metodologijami za primerjalno analizo v evolucijskem računanju dosežen velik uspeh in so bili narejeni pomembni koraki, je potrebno poudariti, da lahko izbira instanc primerjalnih problemov (tj. zbirka primerjalnih vzorcev), ki bodo vključeni v analizo ima velik vpliv na zasnovo eksperimenta (tj. drugo vprašanje) in statistično analizo (tretjo vprašanje), opravljeno z uporabo podatkov o uspešnosti. Lahko se zgodi, da isti nabor algoritmov (tj. nabor instanc algoritmov), ovrednoten na različnih naborih instanc primerjalnih problemov, določi različne zmagovalne algoritme. To pomeni, da lahko izbira instanc primerjalnega problema privede do analize pristranskosti uspešnosti (tj. izbira instanc primerjalnega problema v korist zmagovalnega algoritma). Torej to raziskovalcem omogoča, da predstavijo rezultate, zaradi katerih je njihov na novo razviti algoritem videti boljši od ostalih. Še več različnih izbir instanc problema lahko vodi do različnih konfiguracij (tj. parametrov) istega razreda algoritmov (tj. različnih instanc algoritmov), ki so najboljše, kar zmanjša posploševanje dobljenih rezultatov.

Glavni cilj projekta RESPONSE je zmanjšati pristranskost pri primerjalni analizi v evolucijskem računanju z iznajdbo, razvojem, izvajanjem, in ovrednotenjem ogrodja za poglobljeno analizo pokrajine optimizacije, ki bo sestavljena iz metodologij za raziskovanje izraznosti in robustnosti značilk prostora, z namenom odkritja koristnih predstavitev instanc problema (tj. nabora značilk). S tem bomo preprečili izumljanje novih in novih, sicer enakovrednih algoritmov tipa »črne škatle« za zvezno optimizacijo. Metodologije za poglobljeno analizo pokrajine bojo temeljili na sinergizmu med učenjem predstavitev, strojnim učenjem in statistiko. Razvoj tovrstnih metodologij je močno motiviran s stalno rastjo optimizacijskih problemov v industriji, kar zahteva prenosljivost pridobljenega znanja iz primerjalnih študij v industrijsko okolje. Z novo instanco industrijskega optimizacijskega problema, ki bi ga bilo treba rešiti na podlagi njegove predstavitve pokrajine (tj. lastnosti), lahko najdemo najbolj podobne že obstoječe instance problema, za katere vemo, kateri so najbolj uspešni. Poleg tega nam tovrstno znanje (tj. pretekli eksperimentalni podatki) omogoča uporabo pristopov metaučenja, s čimer lahko najdemo najprimernejšo instanco algoritma za nove (še neznane) industrijske probleme (tj. problem izbire algoritma).

Osnovni podatki sofinanciranja so dostopni na spletni strani SICRIS.

Faze projekta in opis njihove realizacije

Projekt RESPONSE bo s svojimi prispevki uvedel inovacije prek naslednjih temeljnih ciljev:

1. Cilj': Razviti semantični podatkovni model (tj. ontologijo) za opis podatkov o pokrajini (tj. prostora problema), ki bo omogočil učinkovito shranjevanje podatkov glede na „Smernice o ponovljivosti raziskav umetne inteligence“, kar bo omogočilo ponovno uporabo v nadaljnjih raziskovalnih študijah.

2. Cilj': Razviti metodologije za analizo občutljivosti ELA značilk, ki bodo omogočile oceno njihove izraznosti in robustnosti glede na različne strategije vzorčenja in velikosti vzorcev, uporabljene za njihov izračun ter transformacije, opravljene v prostoru problemov (tj. premikanje, skaliranje in rotacija) .

3. Cilj': Razviti metodologije za učenje predstavitev (angl. representations) instance problema, ki temeljijo na metodah predstavitvenega učenja (angl. representation learning) (RepL), kar bo nadalje omogočilo analizo komplementarnosti različnih instanc primerjalnih problemov, s ciljem zmanjšanja pristranskosti pri izvajanju študije primerjalne analize.

4. Cilj': Izvesti vse predlagane metodologije kot spletno storitev, ki bo vključena v javno dostopno spletno platformo, imenovano DSCTool (http://ws.ijs.si/dsc/, trenutno v razvoju na IJS).

5. Cilj': Prenos uporabnosti metodologije na druga raziskovalna področja, poleg evolucijskega računanja, zlasti v področje strojnega učenja, tako da se kot učne naloge preuči klasifikacija z več oznakami in metode RepL na osnovi grafov.

Bibliografske reference

PETELIN, Gašper, CENIKJ, Gjorgjina, EFTIMOV, Tome. TinyTLA : topological landscape analysis for optimization problem classification in a limited sample setting. Swarm and evolutionary computation. Feb. 2024, [article no.] 101448, vol. 84, str. 1-18, ilustr. ISSN 2210-6510.
PETELIN, Gašper, CENIKJ, Gjorgjina, EFTIMOV, Tome. Towards understanding the importance of time-series features in automated algorithm performance prediction. Expert systems with applications. [Print ed.]. 1. Mar. 2023, vol. 213, pt. b, str. 1-20. ISSN 0957-4174
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.
EFTIMOV, Tome, PETELIN, Gašper, CENIKJ, Gjorgjina, KOSTOVSKA, Ana, ISPIROVA, Gordana, KOROŠEC, Peter, BOGATINOVSKI, Jasmin. Less is more: selecting the right benchmarking set of data for time series classification. Expert systems with applications. [Print ed.]. 2022, vol. 198, str. 116871-1-116871-10, ilustr. ISSN 0957-4174.
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, 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.
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.
NIKOLIKJ, Ana, TRAJANOV, Risto, CENIKJ, Gjorgjina, KOROŠEC, Peter, EFTIMOV, Tome. Identifying minimal set of exploratory landscape analysis features for reliable algorithm performance prediction. V: 2022 IEEE Congress on Evolutionary Computation, CEC 2022,18-23 July. Piscataway: IEEE = Institute of Electrical and Electronics Engineers, 2022. 8 str. ISBN 978-1-6654-6708-7.
JANKOVIĆ, Anja, VERMETTEN, Diederick, KOSTOVSKA, Ana, NOBEL, Jacob de, EFTIMOV, Tome, DOERR, Carola. Trajectory-based algorithm selection with warm-starting. V: 2022 IEEE Congress on Evolutionary Computation, CEC 2022,18-23 July. Piscataway: IEEE = Institute of Electrical and Electronics Engineers, 2022. 8 str. ISBN 978-1-6654-6708-7.
TRAJANOV, Risto, DIMESKI, Stefan, POPOVSKI, Martin, KOROŠEC, Peter, EFTIMOV, Tome. Explainable landscape analysis in automated algorithm performance prediction. V: JIMÉNEZ LAREDO, Juan Luis (ur.), IGNACIO HIDALGO, J. (ur.), OLUWATOYIN BABAAGBA, Kehinde (ur.). Applications of evolutionary computation: 25th European Conference, EvoApplications 2022, held as a part of EvoStar 2022, Madrid, Spain, April 20-22: proceedings. Cham: Springer. Str. 207-222. Lecture notes in computer science, LNCS 13224. ISBN 978-3-031-02462-7, ISBN 978-3-031-02461-0. ISSN 0302-9743.
KOSTOVSKA, Ana, VERMETTEN, Diederick, DŽEROSKI, Sašo, DOERR, Carola, KOROŠEC, Peter, EFTIMOV, Tome. The importance of landscape features for performance prediction of modular CMA-ES variants. V: FIELDSEND, Jonathan E. (ur.). GECCO'22: proceedings of the 2022 : Genetic and Evolutionary Computation Conference: July 9 - 13 2022, Boston, Massachusetts. New York: The Association for Computing Machinery, 2022. Str. 648-656, ilustr. ISBN 978-1-4503-9237-2.
CENIKJ, Gjorgjina, DIETER LANG, Ryan, ENGELBRECHT, Andries Petrus, DOERR, Carola, KOROŠEC, Peter, EFTIMOV, Tome. SELECTOR: selecting a representative benchmark suite for reproducible statistical comparison. V: FIELDSEND, Jonathan E. (ur.). GECCO'22: proceedings of the 2022 : Genetic and Evolutionary Computation Conference: July 9 - 13 2022, Boston, Massachusetts. New York: The Association for Computing Machinery, 2022. Str. 620-629, ilustr. ISBN 978-1-4503-9237-2.
TRAJANOV, Risto, NIKOLIKJ, Ana, CENIKJ, Gjorgjina, TEYTAUD, Fabien, VIDEAU, Mathurin, EFTIMOV, Tome, LÓPEZ-IBÁÑEZ, Manuel, DOERR, Carola. Improving nevergrad’s algorithm selection wizard NGOpt through automated algorithm configuration. V: RUDOLPH, Günter (ur.), TUŠAR, Tea (ur.). Parallel problem solving from nature - PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10-14, 2022: proceedings. Part I. Cham: Springer, 2022. Str. 18-31. Lecture notes in computer science, Vol. 13398. ISBN 978-3-031-14714-2, ISBN 978-3-031-14713-5.
KOSTOVSKA, Ana, JANKOVIĆ, Anja, VERMETTEN, Diederick, NOBEL, Jacob de, WANG, Hao, EFTIMOV, Tome, DOERR, Carola. Per-run algorithm selection with warm-starting using trajectory-based Features. V: RUDOLPH, Günter (ur.), TUŠAR, Tea (ur.). Parallel problem solving from nature - PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10-14, 2022: proceedings. Part I. Cham: Springer, 2022. Str. 46-60. Lecture notes in computer science, Vol. 13398. ISBN 978-3-031-14714-2, ISBN 978-3-031-14713-5.
KOSTOVSKA, Ana, DOERR, Carola, DŽEROSKI, Sašo, KOCEV, Dragi, PANOV, Panče, EFTIMOV, Tome. Explainable model-specific algorithm selection for multi-label classification. V: ISHIBUCHI, Hisao (ur.). Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence (SSCI 2022): 4 - 7 December 2022, Singapore. Piscataway: IEEE = Institute of Electrical and Electronics Engineers, cop. 2022. Str. 39-46, ilustr. ISBN 978-1-6654-0983-4, ISBN 978-1-6654-8768-9.
PETELIN, Gašper, CENIKJ, Gjorgjina, EFTIMOV, Tome. TLA : topological landscape analysis for single-objective continuous optimization problem instances. V: ISHIBUCHI, Hisao (ur.). Proceedings of the 2022 IEEE Symposium Series on Computational Intelligence (SSCI 2022): 4 - 7 December 2022, Singapore. Piscataway: IEEE = Institute of Electrical and Electronics Engineers, cop. 2022. Str. 1698-1705, ilustr. ISBN 978-1-6654-0983-4, ISBN 978-1-6654-8768-9.
Nazaj na seznam za leto 2022