Val av algoritm

Algoritmval (ibland även kallat algoritmval per instans eller offline algoritmval ) är en metaalgoritmisk teknik för att välja en algoritm från en portfölj på en instans-för-instans-basis. Det motiveras av observationen att på många praktiska problem har olika algoritmer olika prestandaegenskaper. Det vill säga, medan en algoritm fungerar bra i vissa scenarier, fungerar den dåligt i andra och vice versa för en annan algoritm. Om vi kan identifiera när vi ska använda vilken algoritm, kan vi optimera för varje scenario och förbättra den övergripande prestandan. Detta är vad algoritmval syftar till att göra. Den enda förutsättningen för att tillämpa algoritmvalstekniker är att det finns (eller att det kan konstrueras) en uppsättning komplementära algoritmer.

Definition

Givet en portfölj ${\mathcal {P}}$ av algoritmer ${\mathcal {A}}\in {\mathcal {P}}$ , en uppsättning instanser ${\ displaystyle i\in {\mathcal {I}}}$ och ett kostnadsmått $m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R }$ , algoritmvalsproblemet består av att hitta en mappning $s:{\mathcal {I}}\to {\mathcal {P}}$ från instanser ${\mathcal {I }}$ till algoritmer ${\mathcal {P}}$ så att kostnaden $\sum _{i\in {\mathcal {I} }}m(s(i),i)$ för alla instanser är optimerad.

Exempel

Boolesk tillfredsställelseproblem (och andra svåra kombinatoriska problem)

En välkänd tillämpning av algoritmval är det booleska tillfredsställbarhetsproblemet . Här är portföljen av algoritmer en uppsättning (komplementära) SAT-lösare , instanserna är booleska formler, kostnadsmåttet är till exempel genomsnittlig körtid eller antal olösta instanser. Så målet är att välja en välpresterande SAT-lösare för varje enskild instans. På samma sätt kan algoritmval tillämpas på många andra ${\mathcal {NP}}$ -hårda problem (såsom blandad heltalsprogrammering , CSP , AI-planering , TSP , MAXSAT , QBF och svarsuppsättningsprogrammering ). Tävlingsvinnande system i SAT är SATzilla, 3S och CSHC

Maskininlärning

Inom maskininlärning är val av algoritmer mer känt som meta-lärning . Portföljen av algoritmer består av maskininlärningsalgoritmer (t.ex. Random Forest, SVM, DNN), instanserna är datamängder och kostnadsmåttet är till exempel felfrekvensen. Så målet är att förutsäga vilken maskininlärningsalgoritm som kommer att ha ett litet fel på varje datamängd.

Instansfunktioner

Algoritmvalsproblemet löses huvudsakligen med maskininlärningstekniker. Genom att representera probleminstanserna med numeriska egenskaper $f$ kan algoritmval ses som ett klassificeringsproblem i flera klasser genom att lära sig en mappning $f_{i}\mapsto {\mathcal {A} }$ för en given instans $i$ .

Instansfunktioner är numeriska representationer av instanser. Till exempel kan vi räkna antalet variabler, satser, genomsnittlig satslängd för booleska formler, eller antal sampel, funktioner, klassbalans för ML-datauppsättningar för att få ett intryck av deras egenskaper.

Statiska kontra sonderingsfunktioner

Vi skiljer mellan två typer av funktioner:

Statiska egenskaper är i de flesta fall vissa räkningar och statistik (t.ex. förhållandet mellan klausuler och variabler i SAT). Dessa funktioner sträcker sig från mycket billiga funktioner (t.ex. antal variabler) till mycket komplexa funktioner (t.ex. statistik om variabelklausulgrafer).
Undersökningsfunktioner (ibland även kallade landmarkeringsfunktioner) beräknas genom att köra någon analys av algoritmbeteende på en instans (t.ex. noggrannheten för en billig beslutsträdsalgoritm på en ML-datauppsättning, eller köra en kort tid en stokastisk lokal söklösare på en boolesk formel). Dessa funktioner kostar ofta mer än enkla statiska funktioner.

Funktionskostnader

Beroende på det använda prestandamåttet $m$ kan funktionsberäkning associeras med kostnader. Om vi till exempel använder körtid som prestandamått inkluderar vi tiden för att beräkna våra instansfunktioner i prestandan för ett algoritmvalssystem. SAT-lösning är ett konkret exempel, där sådana funktionskostnader inte kan försummas, eftersom instansfunktioner för CNF -formler antingen kan vara mycket billiga (t.ex. att få antalet variabler kan göras i konstant tid för CNFs i DIMACs-formatet) eller mycket dyra (t.ex. graffunktioner som kan kosta tiotals eller hundratals sekunder).

Det är viktigt att ta hänsyn till overheaden för funktionsberäkning i praktiken i sådana scenarier; annars skapas ett missvisande intryck av prestandan för algoritmvalsmetoden. Till exempel, om beslutet vilken algoritm som ska väljas kan göras med perfekt noggrannhet, men funktionerna är portföljalgoritmernas körtid, finns det ingen fördel med portföljmetoden. Detta skulle inte vara självklart om funktionskostnader utelämnades.

Närmar sig

Regressionsmetod

En av de första framgångsrika metoderna för val av algoritm förutspådde prestandan för varje algoritm ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \ mathbb {R}$ och valde algoritmen med bäst förutspådd prestanda $arg\min _{{\mathcal {A}}\in {\mathcal {P} }}{\hat {m}}_{\mathcal {A}}(i)$ för en instans $i$ .

Klustrande tillvägagångssätt

Ett vanligt antagande är att den givna uppsättningen av instanser ${\mathcal {I}}$ kan klustras till homogena delmängder och för var och en av dessa delmängder finns det en välpresterande algoritm för alla instanser där. Så, utbildningen består av att identifiera de homogena klustren via en oövervakad klustringsmetod och associera en algoritm med varje kluster. En ny instans tilldelas ett kluster och den tillhörande algoritmen väljs.

Ett mer modernt tillvägagångssätt är kostnadskänslig hierarkisk klustring med hjälp av övervakad inlärning för att identifiera de homogena instansundermängderna.

Parvis kostnadskänslig klassificeringsmetod

Ett vanligt tillvägagångssätt för klassificering i flera klasser är att lära sig parvisa modeller mellan varje par av klasser (här algoritmer) och välja den klass som förutspåddes oftast av de parvisa modellerna. Vi kan väga fallen av det parvisa prediktionsproblemet med prestandaskillnaden mellan de två algoritmerna. Detta motiveras av att vi bryr oss mest om att få förutsägelser med stora skillnader korrekta, men påföljden för en felaktig förutsägelse är liten om det nästan inte är någon prestationsskillnad. Därför är varje instans $i$ för att träna en klassificeringsmodell ${\mathcal {A}}_{1}$ vs ${\mathcal {A}}_{2}$ är förknippad med en kostnad $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$ .

Krav

Klustring av SAT-lösare från SAT12-INDU ASlib scenario enligt korrelationskoefficienten för spearman.

Shapley-värden för kompletterande analys på SAT12-INDU ASlib Scenario

Algoritmvalsproblemet kan effektivt tillämpas under följande antaganden:

portfölj ${\mathcal {P}}$ är komplementär med avseende på instansuppsättningen ${\displaystyle {\mathcal {I}}} ,$ dvs. det finns ingen enskild algoritm ${\mathcal {A}}\in {\mathcal {P}}$ som dominerar prestandan för alla andra algoritmer över ${\mathcal {I}}$ (se figurerna till höger för exempel på komplementär analys) .
I vissa applikationer är beräkningen av instansfunktioner förknippad med en kostnad. Till exempel, om kostnadsmåttet är körtid måste vi också ta hänsyn till tiden för att beräkna instansfunktionerna. I sådana fall bör kostnaden för att beräkna funktioner inte vara större än prestandavinsten genom val av algoritm.

Applikationsdomäner

Algoritmval är inte begränsat till enstaka domäner utan kan tillämpas på vilken typ av algoritm som helst om ovanstående krav är uppfyllda. Applikationsdomäner inkluderar:

svåra kombinatoriska problem: SAT , Mixed Integer Programming , CSP , AI Planning , TSP , MAXSAT , QBF och Answer Set Programmering
kombinatoriska auktioner
inom maskininlärning är problemet känt som meta-lärande
mjukvarudesign
black-box-optimering
multi-agent system
numerisk optimering
linjär algebra, differentialekvationer
evolutionära algoritmer
fordonsdirigeringsproblem
kraftsystem

För en omfattande litteraturlista om val av algoritmer hänvisar vi till en litteraturöversikt.

Varianter av val av algoritm

Online urval

Val av onlinealgoritm avser att växla mellan olika algoritmer under lösningsprocessen. Detta är användbart som en hyperheuristik . Däremot väljer val av offlinealgoritm en algoritm för en given instans endast en gång och före lösningsprocessen.

Beräkning av scheman

En förlängning av val av algoritm är schemaläggningsproblemet per instans, där vi inte bara väljer en lösare, utan vi väljer en tidsbudget för varje algoritm på en per instansbas. Detta tillvägagångssätt förbättrar prestandan för urvalssystem i synnerhet om instansfunktionerna inte är särskilt informativa och ett felaktigt val av en enskild lösare är troligt.

Urval av parallellportföljer

Med tanke på den ökande betydelsen av parallell beräkning, är en utvidgning av algoritmval för parallell beräkning parallellportföljval, där vi väljer en delmängd av algoritmerna för att samtidigt köras i en parallell portfölj.

externa länkar