Algoritmin valinta - Algorithm selection

Algoritmin valinta (jota kutsutaan joskus myös tapauskohtaiseksi algoritminvalinnaksi tai offline-algoritmin valintaksi ) on meta- algoritminen tekniikka valita algoritmi salkusta tapauskohtaisesti. Sen taustalla on havainto, että monissa käytännön ongelmissa eri algoritmeilla on erilaiset suorituskykyominaisuudet. Toisin sanoen, vaikka yksi algoritmi toimii hyvin joissakin tilanteissa, se toimii huonosti toisissa ja päinvastoin toisessa algoritmissa. Jos voimme tunnistaa, milloin mitäkin algoritmia käytetään, voimme optimoida jokaisen skenaarion ja parantaa yleistä suorituskykyä. Tähän pyrkii algoritmin valinta. Ainoa edellytys algoritmien valintatekniikoiden soveltamiselle on, että on olemassa (tai että ne voidaan rakentaa) joukko täydentäviä algoritmeja.

Määritelmä

Kun otetaan huomioon algoritmivalikoima , joukko esiintymiä ja kustannusmittari , algoritmin valintaongelma koostuu etsimisestä tapauksista algoritmeihin siten, että kaikkien esiintymien kustannukset optimoidaan. ${\ displaystyle {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {A}} \ in {\ mathcal {P}}}$ ${\ displaystyle i \ in {\ mathcal {I}}}$ ${\ displaystyle m: {\ mathcal {P}} \ times {\ mathcal {I}} \ - \ mathbb {R}}$ ${\ displaystyle s: {\ mathcal {I}} \ - {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {I}}}$ ${\ displaystyle {\ mathcal {P}}}$ ${\ displaystyle \ sum _ {i \ in {\ mathcal {I}}} m (s (i), i)}$

Esimerkkejä

Boolen tyydytettävyysongelma (ja muut vaikeat yhdistelmäongelmat)

Tunnettu algoritmien valinnan sovellus on Boolen tyydyttävyysongelma . Tässä algoritmivalikoima on joukko (täydentäviä) SAT -ratkaisijoita , ilmentymät ovat Boolen kaavoja, kustannusmittari on esimerkiksi keskimääräinen suoritusaika tai ratkaisemattomien esiintymien määrä. Tavoitteena on siis valita hyvin toimiva SAT-ratkaisija jokaiselle yksittäiselle esiintymälle. Samalla tavalla algoritmien valintaa voidaan soveltaa moniin muihin vaikeisiin ongelmiin (kuten kokonaislukuohjelmointi , CSP , AI -suunnittelu , TSP , MAXSAT , QBF ja vastausjoukkojen ohjelmointi ). Kilpailua voittaneet SAT-järjestelmät ovat SATzilla, 3S ja CSHC ${\ displaystyle {\ mathcal {NP}}}$

Koneoppiminen

Vuonna koneoppimisen , algoritmin valinta on paremmin tunnettu meta-oppimista . Algoritmivalikoima koostuu koneoppimisalgoritmeista (esim. Random Forest, SVM, DNN), ilmentymät ovat tietojoukkoja ja kustannusmittari on esimerkiksi virhetaso. Tavoitteena on siis ennustaa, millä koneoppimisalgoritmilla on pieni virhe kussakin tietojoukossa.

Ilmentymän ominaisuudet

Algoritmin valintaongelma ratkaistaan pääasiassa koneoppimistekniikoilla. Edustamalla ongelma-ilmentymiä numeerisilla ominaisuuksilla algoritmin valinta voidaan nähdä moniluokkaisena luokitusongelmana oppimalla kartoitus tietylle esiintymälle . ${\ displaystyle f}$ ${\ displaystyle f_ {i} \ mapsto {\ mathcal {A}}}$ ${\ displaystyle i}$

Ilmentymän ominaisuudet ovat esiintymien numeerisia esityksiä. Voimme esimerkiksi laskea muuttujien, lausekkeiden, Boolen kaavojen keskimääräisen lausekepituuden tai ML -tietojoukkojen näytteiden, ominaisuuksien ja luokkataseiden määrän saadaksemme vaikutelman niiden ominaisuuksista.

Staattiset vs. mittausominaisuudet

Erotamme kahdenlaisia ominaisuuksia:

Staattiset piirteet ovat useimmissa tapauksissa joitakin laskelmia ja tilastoja (esim. Lausekkeiden ja muuttujien suhde SAT: ssa). Nämä ominaisuudet vaihtelevat erittäin halvoista ominaisuuksista (esim. Muuttujien määrä) erittäin monimutkaisiin ominaisuuksiin (esim. Tilastot muuttuvalausekkeista).
Koetustoiminnot (joita joskus kutsutaan myös maamerkkiominaisuuksiksi) lasketaan suorittamalla jokin analyysi algoritmin käyttäytymisestä ilmentymässä (esim. Halvan päätöspuun algoritmin tarkkuus ML -tietojoukossa tai suorittamalla lyhyen ajan stokastinen paikallisen haun ratkaisija Boolen kaava). Nämä ominaisuudet maksavat usein enemmän kuin yksinkertaiset staattiset ominaisuudet.

Ominaisuus maksaa

Käytetyn suorituskykymittarin mukaan ominaisuuksien laskenta voidaan yhdistää kustannuksiin. Jos esimerkiksi käytämme suoritusaikaa suoritusmittarina, sisällytämme aikalaskennan ominaisuuksien laskemiseen algoritminvalintajärjestelmän suorituskykyyn. SAT -ratkaisu on konkreettinen esimerkki, jossa tällaisia ominaiskustannuksia ei voida jättää huomiotta, koska CNF -kaavojen esiintymäominaisuudet voivat olla joko erittäin halpoja (esim. Muuttujien lukumäärän saaminen voidaan tehdä vakioaikana CNF -tiedostoille DIMAC -muodossa) tai hyvin kalliita (esim. kuvaajaominaisuudet, jotka voivat maksaa kymmeniä tai satoja sekunteja). ${\ displaystyle m}$

On tärkeää ottaa ominaisuuslaskennan yleiskustannukset huomioon käytännössä tällaisissa skenaarioissa; muutoin syntyy harhaanjohtava vaikutelma algoritminvalintamenetelmän suorituskyvystä. Jos esimerkiksi päätös siitä, minkä algoritmin valita, voidaan tehdä täydellisellä tarkkuudella, mutta ominaisuudet ovat salkkualgoritmien käyntiaika, portfolion lähestymistavasta ei ole hyötyä. Tämä ei olisi ilmeistä, jos ominaisuuskustannukset jätettäisiin pois.

Lähestymistavat

Regressio -lähestymistapa

Yksi ensimmäisistä onnistuneista algoritmien valintamenetelmistä ennusti kunkin algoritmin suorituskyvyn ja valitsi parhaan ennustetun suorituskyvyn omaavan algoritmin ilmentymälle . ${\ displaystyle {\ hat {m}} _ {\ mathcal {A}}: {\ mathcal {I}} \ to \ mathbb {R}}$ ${\ displaystyle arg \ min _ {{\ mathcal {A}} \ in {\ mathcal {P}}} {\ hat {m}} _ {\ mathcal {A}} (i)}$ ${\ displaystyle i}$

Klusterointi

Yleinen oletus on, että annettu joukko esiintymiä voidaan ryhmitellä homogeenisiksi osajoukkoiksi ja kullekin näistä osajoukoista on yksi hyvin toimiva algoritmi kaikille esiintymille. Koulutus koostuu siis homogeenisten klustereiden tunnistamisesta valvomattoman klusterointimenetelmän avulla ja algoritmin liittämisestä jokaiseen klusteriin. Uusi ilmentymä määritetään klusterille ja siihen liittyvä algoritmi valitaan. ${\ displaystyle {\ mathcal {I}}}$

Nykyaikaisempi lähestymistapa on kustannusherkkä hierarkkinen klusterointi käyttäen valvottua oppimista homogeenisten esiintymien osajoukkojen tunnistamiseksi.

Pari-kustannusherkkä luokitusmenetelmä

Yleinen lähestymistapa moniluokkaiselle luokittelulle on oppia pareittain malleja jokaisen luokkaparin välillä (tässä algoritmit) ja valita luokka, joka useimmin ennustettiin pareittain. Voimme punnita pareittain ennusteongelman ilmentymät kahden algoritmin suorituskykyerolla. Tämä johtuu siitä, että välitämme eniten siitä, että ennusteet, joissa on suuria eroja, ovat oikein, mutta virheellisen ennusteen rangaistus on pieni, jos suorituskykyeroja ei juuri ole. Siksi jokainen luokitusmallin vs. koulutuksen esiintymä liittyy kustannukseen . ${\ displaystyle i}$ ${\ displaystyle {\ mathcal {A}} _ {1}}$ ${\ displaystyle {\ mathcal {A}} _ {2}}$ ${\ displaystyle | m ({\ mathcal {A}} _ {1}, i) -m ({\ mathcal {A}} _ {2}, i) |}$

Vaatimukset

SAT-ratkaisijoiden ryhmittely SAT12-INDU ASlib -skenaariosta keihäänmiehen korrelaatiokertoimen mukaan.

Shapley-arvot täydentävää analyysiä varten SAT12-INDU ASlib -skenaariossa

Algoritmin valintaongelmaa voidaan soveltaa tehokkaasti seuraavilla oletuksilla:

Salkun algoritmeja on komplementaarinen suhteessa esimerkiksi joukko , eli ei ole olemassa yhtä algoritmi , joka hallitsee kaikkien suoritusta muita algoritmeja yli (katso kuvat oikealla esimerkkejä täydentäviä analyysi). ${\ displaystyle {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {I}}}$ ${\ displaystyle {\ mathcal {A}} \ in {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {I}}}$
Joissakin sovelluksissa ilmentymän ominaisuuksien laskeminen liittyy hintaan. Jos esimerkiksi kustannusmittari on ajoaika, meidän on myös otettava huomioon tapausominaisuuksien laskemiseen kuluva aika. Tällaisissa tapauksissa ominaisuuksien laskemisesta aiheutuvien kustannusten ei pitäisi olla suurempia kuin suorituskyvyn parannus algoritmin valinnan kautta.

Sovellusalueet

Algoritmin valinta ei rajoitu yksittäisiin toimialueisiin, vaan sitä voidaan soveltaa mihin tahansa algoritmiin, jos edellä mainitut vaatimukset täyttyvät. Sovellusalueita ovat:

vaikeat yhdistelmäongelmat: SAT , kokonaislukuohjelmointi , CSP , AI -suunnittelu , TSP , MAXSAT , QBF ja vastausjoukkojen ohjelmointi
yhdistelmähuutokaupat
koneoppimisessa ongelma tunnetaan meta-oppimisena
ohjelmistojen suunnittelu
mustan laatikon optimointi
moniagenttijärjestelmät
numeerinen optimointi
lineaarinen algebra, differentiaaliyhtälöt
evoluution algoritmeja
auton reititysongelma
sähköjärjestelmät

Laaja luettelo algoritmien valintaa koskevasta kirjallisuudesta on kirjallisuuskatsauksessa.

Vaihtoehdot algoritmin valinnasta

Valinta verkossa

Online -algoritmin valinta tarkoittaa vaihtamista eri algoritmien välillä ratkaisuprosessin aikana. Tästä on hyötyä hyperheuristisena . Sitä vastoin offline -algoritmin valinta valitsee tietyn esiintymän algoritmin vain kerran ja ennen ratkaisuprosessia.

Aikataulujen laskeminen

Algoritminvalinnan laajennus on tapauskohtainen algoritmien ajoitusongelma, jossa emme valitse vain yhtä ratkaisijaa, vaan valitsemme aikabudjetin kullekin algoritmille tapauskohtaisesti. Tämä lähestymistapa parantaa valintajärjestelmien suorituskykyä erityisesti, jos ilmentymän ominaisuudet eivät ole kovin informatiivisia ja yksittäisen ratkaisijan väärä valinta on todennäköistä.

Rinnakkaissalkkujen valinta

Kun otetaan huomioon rinnakkaislaskennan kasvava merkitys, rinnakkaislaskennan algoritminvalinnan laajennus on rinnakkaisportfolion valinta, jossa valitsemme algoritmien osajoukon, joka suoritetaan samanaikaisesti rinnakkaisportfoliossa.

Languages

In other projects