REPOZITORIJ > REZULTATI

Povzetek

Na področju optimizacije velja, da je uspešnost optimizacijskih algoritmov odvisna od
problemov, ki jih algoritmi rešujejo. Posledično moramo za dosego dobrih optimizacijskih
rezultatov pravilno izbrati tisti algoritem, ki je zmožen ta problem dobro rešiti. To lahko
storimo s podrobnim poznavanjem tako optimizacijskih algoritmov kot tudi problemov.
Kljub temu pa je v trenutni znanstveni literaturi področje analize optimizacijskih problemov
izrazito manj zastopano od področja analize algoritmov. V tej doktorski disertaciji se
osredotočamo na analizo optimizacijskih problemov z uporabo metode raziskovalna analiza
problemske pokrajine (angl. exploratory landscape analysis), ki vzorce problema pretvori
v značilke problemske pokrajine.
V disertaciji najprej izvedemo analizo dveh najbolj znanih dogodkov za primerjavo
uspešnosti optimizacijskih algoritmov. Pokažemo, da so rezultati merjenja uspešnosti na
teh dogodkih različni, kar menimo da je posledica tega, da dogodki uporabljajo razlicne
optimizacijske probleme. Poleg tega pokažemo, da so tovrstne razlike prisotne tudi med
vsakoletnimi razlicicami problemov na enemu izmed teh dogodkov. To pomeni, da uspešnosti
algoritmov, izmerjene na najnovejših razlicicah problemov, niso nujno primerljive s
tistimi na prejšnjih razlicicah. Torej da algoritem, ki se izkaže za najboljšega na najnovejših
razlicicah problemov, ni nujno tako uspešen, ko ga uporabimo za reševanje starejših
razlicic problemov. Nato analiziramo pogosto uporabljeno metode raziskovalne analize
preiskovanja problemske pokrajine za opis znacilk optimizacijskih problemov. V sklopu te
raziskave ugotovimo, da so nekatere znacilke problemske pokrajine obcutljive na preslikavi
premika in središcnega raztega.
V zadnjem delu disertacije ovrednotimo uporabo značilk problemske pokrajine za napovedovanje
najboljšega optimizacijskega algoritma za posamezen problem. Predhodne
raziskave so pokazale, da se značilke obnesejo dobro, če se model uči na isti množici problemov,
kot je uporabljena za napovedovanje. V naših eksperimentih preverimo, če to
velja tudi, ko se model uči na povsem ločeni množici problemov. Za ta namen kot učno
množico uporabimo nabor problemov ki so bili ustvarjeni z uporabo računalniškega algoritma,
in jih uporabimo za napoved na naboru problemov iz obstoječe zbirke problemov.
Rezultati, ki jih pridobimo, so negativni, kar lahko nakazuje, da množici podatkov, ki
ju uporabimo za učenje in napovedovanje, nista dovolj splošni, ko probleme opisujemo z
značilkami pokrajin.
Glavni prispevek disertacije je bolj podrobna analiza optimizacijskih problemov s poudarkom
na analizi značilk pokrajine problema. V disertaciji pokažemo, da te značilke sicer
lahko opišejo optimizacijski problem, vendar je pri njihovi uporabi potrebna previdnost in
razumevanje, da so nekatere značilke občutljive na nekatere pogoste transformacije. Poleg
tega pokažemo, da značilke v nekaterih primerih ne morejo posplošiti informacij med različnimi
nabori problemov, ko jih uporabljamo za napovedovanje najboljšega optimizacijskega
algoritma za posamezen problem.