Večkriterijska optimizacija z omejitvami na osnovi analize problemske pokrajine
Oznaka in naziv projekta
N2-0254 Večkriterijska optimizacija z omejitvami na osnovi analize problemske pokrajine
N2-0254 Constrained multiobjective optimization based on problem landscape analysis
Logotipi ARRS in drugih sofinancerjev
Projektna skupina
Vodja projekta: prof. dr. Bogdan Filipič, Povezava na SICRIS
Sodelavci:
doc. dr. Tea Tušar, Povezava na SICRIS
Aljoša Vodopija, Povezava na SICRIS
Andrejaana Andova, Povezava na SICRIS
Sodelujoče raziskovalne organizacije: Tehniška univerza v Ostravi na Češkem
Vsebinski opis projekta
Realni optimizacijski problemi pogosto vključujejo več nasprotujočih si kriterijev in omejitve. Takšni problemi so znani kot večkriterijski optimizacijski problemi z omejitvami (angl. constrained multiobjective optimization problems) in jih je v splošnem težko rešiti. Ko npr. inženir pri načrtovanju nove naprave skuša maksimizirati njeno zmogljivost in minimizirati stroške, je njegova izbira rešitev omejena z zahtevami glede velikosti in teže naprave, razpoložljivostjo komponent, omejitvami proizvodnega postopka itd. Optimizacijski problemi z nasprotujočimi si kriteriji nimajo ene same optimalne rešitve, temveč množico optimalnih (kompromisnih) rešitev, imenovanih Pareto-optimalna množica. V zadnjih desetletjih so bili za reševanje takšnih problemov razviti populacijske metahevristike, kot so npr. večkriterijski evolucijski algoritmi. Njihova prednost je v tem, da lahko v enem samem zagonu najdejo približek Pareto množice. Vendar z naraščajočim številom kriterijev in v prisotnosti omejitev zahtevnost teh problemov močno naraste, učinkovitost metahevristik pa kritično upade.
Predlagani raziskovalni projekt želi prispevati k teoretičnim osnovam večkriterijske optimizacije z omejitvami in zagotoviti novo generacijo evolucijskih metahevristik za tovrstne probleme. Izbrani pristop se bo opiral na analizo problemske pokrajine (angl. problem landscape). Njen primer je pokrajina uspešnosti (angl. fitness landscape), ki predstavlja preslikavo kodiranj rešitev v njihove uspešnosti. V enokriterijski optimizaciji pokrajino uspešnosti uporabljamo za analizo problemov in prilagajanje algoritmov, da bi povečali njihovo učinkovitost. Drug primer je pokrajina kršitev (angl. violation landscape), ki prostor rešitev okarakterizira glede na stopnjo kršitve omejitev. Predlagana raziskava razširja koncepte problemske pokrajine na večkriterijsko optimizacijo z omejitvami, za katero je doslej v literaturi znanih le malo začetnih poskusov analize in uporabe problemske pokrajine. To bomo dosegli z novimi metodami vzorčenja in modeliranja problemske pokrajine, tehnikami za njeno vizualizacijo in mehanizmi za obravnavanje omejitev ter z njihovim preverjanjem na novo zasnovanem naboru testnih problemov. Ta bo odražal izkušnje, pridobljene pri reševanju umetnih testnih problemov in dodatno vključeval lastnosti realnih problemov.
Povzeto povedano, cilji projekta so: (1) razviti nove metode vzorčenja, modeliranja in vizualizacije problemske pokrajine za karakterizacijo večkriterijskih optimizacijskih problemov z omejitvami, (2) prepoznati ustrezne značilnosti teh problemov in jih uporabiti za izboljšanje uspešnosti metahevristik za njihovo reševanje, (3) sestaviti nov nabor testnih večkriterijskih problemov z omejitvami z lastnostmi, ki jih najdemo v realnih problemih in (4) natančno ovrednotiti vse razvite pristope.
Projektno skupino sestavljajo raziskovalci s Tehniške univerze v Ostravi (VSB) na Češkem in Instituta »Jožef Stefan« (IJS). Prispevka obeh partnerskih ustanov k projektu sta uravnotežena in se dopolnjujeta. Medtem ko sta obe skupini izkušeni v hevrističnem reševanju optimizacijskih problemov, je na VSB poudarek raziskav na vzorčenju in modeliranju problemske pokrajine, na IJS pa na njeni vizualizaciji in obravnavanju omejitev. Pričakovani rezultati projekta so skupne objave v odprtem dostopu, izboljšave metahevristik za večkriterijske optimizacijske probleme, ki bodo koristne tako za razvijalce algoritmov kot končne uporabnike, ter nov nabor testnih problemov, ki bo na voljo za nadaljnje primerjalne študije.
Osnovni podatki sofinanciranja so dostopni na spletni strani SICRIS.
Faze projekta in opis njihove realizacije
Projekt poteka od 1. 3. 2022 do 28. 2. 2025.
Delo na projektu je organizirano v štiri vsebinske delovne sklope:
- Raziskovalni okvir (M1-M20)
- Pregled sorodnega dela
- Metodologija ocenjevanja algoritmov
- Testni problemi
- Karakterizacija problemov (M10-M24)
- Vzorčenje in modeliranje problemske pokrajine
- Vizualizacija problemske pokrajine
- Izboljšave metahevrističnih algoritmov (M14-M32)
- Analiza komponent algoritmov
- Konfiguriranje algoritmov glede na problemske pokrajine
- Vrednotenje (M17-M36)
- Vrednotenje testnih problemov
- Vrednotenje karakterizacije problemov
- Vrednotenje izboljšav algoritmov
Delo poteka brez odstopanj od predvidenega programa.