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

Optimizacijski problemi se pojavljajo vsepovsod v našem vsakdanjem življenju; v vseh geografskih regijah, industrijskih panogah, in akademskih disciplinah. Boljše kot so metode za reševanje teh problemov, bolj učinkovito bomo lahko izkoristili naše omejene vire. Mnogo, če ne celo večine, praktičnih problemov tako ni mogoče rešiti z natančnimi analitičnimi pristopi. V takšnih situacijah se je potrebno zateči k hevrističnim pristopom, ki balansirajo med natančnostjo rešitve in preprostostjo algoritmične strukture, kratkim časom izvajanja, ali katero drugo učinkovito izrabo računskih virov. V mnogo primerih hevristike ponujajo edino možnost s katero lahko pridobimo izvedljivo rešitev. V idealnih razmerah bi radi razvili algoritme, ki so uspešni na širokem naboru problemov in njihovih različic. V praksi pa opažamo izrazito komplementarnost različnih algoritmičnih pristopov: algoritmi, ki za nekatere probleme delujejo zelo dobro, lahko pri drugih delujejo slabo. Uporabnik mora zato skrbno izbrati katero hevristiko bo uporabil za dani problem. Ta izbira algoritma je dodatno otežena, ker imajo iterativne hevristike svoje hiper-parametre. Različne nastavitve hiper-parametrov lahko privedejo do različnih uspešnosti hevristik pri reševanju problema. Uporabnik se mora tako odločiti, ne le kateri algoritem bo uporabil, ampak tudi kako ga nastaviti. Da bi raziskali in sčasoma izkoristili komplementarnost različnih hevristik in njihovih interakcij, ter tudi načrtovali nove hevristike, ki so še bolj primerne za dane probleme, bomo v ta namen uporabili nadzorovane tehnike strojnega učenja. Takšni pristopi strojnega učenja zahtevajo smiselne značilke, ki kvantitativno ovrednotijo različne vidike izbrane instance problema. Dodatno potrebujemo informacije o nastavitvi hiper-parametrov in uspešnosti hevristik. Na splošno gledano mora avtomatsko načrtovanje algoritmov razumeti in združiti informacije iz prostora problemov, prostora hiper-parametrov, in prostora uspešnosti reševanja. V zvezi s prostorom problemov je bila uvedena analiza preiskovanja pokrajine, katere namen je podpreti tehnike avtomatskega načrtovanja algoritmov z naborom funkcij oz. karakteristik, ki merijo različne značilke obravnavanega optimizacijskega problema. V okviru zvezne optimizacije tipa črne škatle je bilo v zadnjih desetletjih predlaganih veliko funkcij in vsaka izmed njih meri drugačno značilnost problema. Dobro je znano, da je pravilna izbira značilk bistvenega pomena za doseganje najvišje uspešnosti pri nadzorovanih učnih pristopih, ne le za odstranjevanje značilk z omejenimi ali celo zavajajočimi informacijami, ampak tudi za odstranjevanje značilk, ki so medsebojno korelirane. Po drugi strani je tudi potrebno zelo previdno raziskati prostor uspešnosti, tako da bomo lahko razumeli razmerja med prostorom značilk in uspešnosti reševanja. Glavni cilj predlaganega projekta je omogočiti uporabnikom, da dobijo dobre rešitve za dano instanco optimizacijskega problema brez poglobljenega a priori znanja o optimizacijskih algoritmih ali instanci problema. Da bi to dosegli, je potrebno za določitev primernosti danega optimizacijskega algoritma za dano instanco problema upoštevati številne različne značilnosti instance problema. To je zapleten večdimenzionalni problem z medsebojno odvisnostjo med posameznimi značilnostmi. Glede na primeren portfelj znanih testnih problemov z njihovimi značilnostmi in portfelj optimizacijskih algoritmov lahko dejansko uspešnost reševanja optimizacijskih algoritmov na naboru instanc problemov določimo z reševanjem vsake instance problema z vsakim od optimizacijskih algoritmov. S pomočjo razložljivih tehnik strojnega učenja lahko najdemo relacije med značilnostmi instance problema in uspešnostjo reševanja optimizacijskega algoritma. Če je mogoče najti dovolj splošne relacije, jih je mogoče uporabiti za napovedovanje uspešnosti reševanja optimizacijskega algoritma na do sedaj ne videnih instancah problemov.