Wybór algorytmu

Wybór algorytmu (czasami nazywany również wyborem algorytmu na instancję lub wyborem algorytmu offline ) to metaalgorytmiczna technika wyboru algorytmu z portfela na zasadzie instancja po instancji. Jest to motywowane obserwacją, że w wielu praktycznych problemach różne algorytmy mają różne charakterystyki wydajności. Oznacza to, że podczas gdy jeden algorytm działa dobrze w niektórych scenariuszach, działa słabo w innych i odwrotnie w przypadku innego algorytmu. Jeśli potrafimy określić, kiedy użyć którego algorytmu, możemy zoptymalizować dla każdego scenariusza i poprawić ogólną wydajność. To właśnie ma na celu wybór algorytmu. Jedynym warunkiem zastosowania technik selekcji algorytmów jest istnienie (lub możliwość skonstruowania) zbioru komplementarnych algorytmów.

Definicja

Biorąc pod uwagę portfel algorytmów, zbiór instancji $} displaystyle i \ in {\ mathcal {I}}}$ $in {\ mathcal {P}$ $Displaystyle {\ mathcal$ i metryka kosztów ${\ Displaystyle m: {\ mathcal {P}} \ razy {\ mathcal {I}} \ do \ mathbb {R } }$ , problem wyboru algorytmu polega na znalezieniu odwzorowania ${\ mathcal {I}} \ do {\ mathcal {P}$ instancji $} }}}$ do algorytmów $takich$ , że koszt ${\ mathcal {I} }}m(s(i),i)}$ we wszystkich instancjach jest zoptymalizowane.

Przykłady

Boolowski problem spełnialności (i inne trudne problemy kombinatoryczne)

Dobrze znanym zastosowaniem wyboru algorytmu jest problem spełnialności Boole'a . Tutaj portfolio algorytmów to zestaw (komplementarnych) solwerów SAT , instancje to formuły boolowskie, metryka kosztu to na przykład średni czas działania lub liczba nierozwiązanych instancji. Tak więc celem jest wybranie dobrze działającego solvera SAT dla każdej indywidualnej instancji. W ten sam sposób wybór algorytmu można zastosować do wielu innych trudnych problemów (takich jak mieszane programowanie liczb całkowitych , $,$ planowanie AI , TSP , MAXSAT QBF i programowanie zestawów odpowiedzi ). Zwycięskie systemy w SAT to SATzilla, 3S i CSHC

Nauczanie maszynowe

W uczeniu maszynowym wybór algorytmu jest lepiej znany jako metauczenie . Portfolio algorytmów składa się z algorytmów uczenia maszynowego (np. Random Forest, SVM, DNN), instancjami są zbiory danych, a metryką kosztu jest np. poziom błędu. Tak więc celem jest przewidzenie, który algorytm uczenia maszynowego będzie miał mały błąd w każdym zbiorze danych.

Funkcje instancji

Problem wyboru algorytmu jest rozwiązywany głównie za pomocą technik uczenia maszynowego. Reprezentując wystąpienia problemu za pomocą funkcji numerycznych $wybór$ algorytmu można postrzegać jako problem klasyfikacji wielu klas poprzez uczenie się mapowania ${\ displaystyle f_ {i} \ mapsto {\ mathcal {A} }}$ dla danej instancji ${\ displaystyle i}$ .

Elementy instancji to numeryczne reprezentacje instancji. Na przykład możemy policzyć liczbę zmiennych, klauzul, średnią długość klauzul dla formuł boolowskich lub liczbę próbek, cech, równowagę klas dla zestawów danych ML, aby uzyskać wrażenie na temat ich charakterystyki.

Funkcje statyczne a sondujące

Wyróżniamy dwa rodzaje cech:

Cechami statycznymi są w większości przypadków liczby i statystyki (np. stosunek klauzul do zmiennych w SAT). Funkcje te wahają się od bardzo tanich funkcji (np. liczba zmiennych) do bardzo złożonych funkcji (np. statystyka dotycząca wykresów ze zmiennymi klauzulami).
Funkcje sondujące (czasami nazywane również cechami wyznaczającymi punkty orientacyjne) są obliczane poprzez przeprowadzenie pewnej analizy zachowania algorytmu na instancji (np. Formuła boolowska). Te funkcje często kosztują więcej niż proste funkcje statyczne.

Koszty funkcji

W zależności od zastosowanej metryki wydajności $obliczanie$ funkcji może wiązać się z kosztami. Na przykład, jeśli używamy czasu działania jako miernika wydajności, uwzględniamy czas potrzebny na obliczenie funkcji naszej instancji do wydajności systemu wyboru algorytmu. Rozwiązywanie SAT jest konkretnym przykładem, gdzie takich kosztów funkcji nie można pominąć, ponieważ funkcje instancji dla CNF mogą być albo bardzo tanie (np. uzyskanie liczby zmiennych można wykonać w stałym czasie dla CNF w formacie DIMAC) lub drogie (np. funkcje wykresów, które mogą kosztować dziesiątki lub setki sekund).

W takich scenariuszach ważne jest, aby wziąć pod uwagę narzut związany z obliczaniem cech w praktyce; w przeciwnym razie powstaje mylące wrażenie wydajności podejścia opartego na wyborze algorytmu. Na przykład, jeśli decyzja, który algorytm wybrać, może zostać podjęta z doskonałą dokładnością, ale cechami są czas działania algorytmów portfelowych, podejście portfelowe nie przynosi żadnych korzyści. Nie byłoby to oczywiste, gdyby pominięto koszty funkcji.

Podchodzi do

Podejście regresyjne

Jedno z pierwszych udanych podejść do wyboru algorytmu przewidywało wydajność każdego algorytmu ${\ Displaystyle {\ hat {m}} _ {\ mathcal {A}}: {\ mathcal {I}} \ do \ mathbb {R}}$ i wybrał algorytm o najlepiej przewidywanej wydajności ${\ Displaystyle arg \ min _ {{\ mathcal {A}} \ in {\ mathcal {P} }} {\ hat {m.}} _ {\ mathcal {A}} (i)}$ dla instancji ${\ displaystyle i}$ .

Podejście klastrowe

$, że$ zestaw instancji można pogrupować w jednorodne podzbiory i dla każdego z tych podzbiorów istnieje jeden dobrze działający algorytm dla wszystkich tam zawartych. Tak więc szkolenie polega na identyfikacji jednorodnych klastrów za pomocą nienadzorowanego podejścia do klastrów i powiązaniu algorytmu z każdym klastrem. Nowa instancja jest przypisywana do klastra i wybierany jest powiązany algorytm.

Bardziej nowoczesnym podejściem jest hierarchiczne grupowanie uwzględniające koszty przy użyciu uczenia nadzorowanego w celu identyfikacji jednorodnych podzbiorów instancji.

Podejście do klasyfikacji zależnej od kosztów parami

Powszechnym podejściem do klasyfikacji wieloklasowej jest nauczenie się modeli parami między każdą parą klas (tutaj algorytmów) i wybranie klasy, która była najczęściej przewidywana przez modele parami. Możemy zważyć przypadki problemu przewidywania parami na podstawie różnicy wydajności między dwoma algorytmami. Jest to motywowane faktem, że najbardziej zależy nam na tym, aby prognozy z dużymi różnicami były poprawne, ale kara za nieprawidłową prognozę jest niewielka, jeśli nie ma prawie żadnej różnicy w wydajności. Dlatego każda instancja $trenowania$ modelu klasyfikacji ${\ Displaystyle {\ mathcal {A}} _ {1}}$ vs ${\ Displaystyle {\ mathcal {A}} _ {2}}$ jest powiązany z kosztem ${\ Displaystyle | m ({\ mathcal {A}} _ {1}, i) -m ({\ mathcal {A}} _ {2}, i) |}$ .

Wymagania

Grupowanie solverów SAT ze scenariusza SAT12-INDU ASlib według współczynnika korelacji spearmana.

Wartości Shapleya do analizy uzupełniającej scenariusza SAT12-INDU ASlib

Problem wyboru algorytmu można skutecznie zastosować przy następujących założeniach:

Portfel ${\ mathcal {A}} \ in {\ mathcal {P}}},$ $komplementarny$ w stosunku do zbioru instancji $tj$ . nie ma $.$ który dominuje nad wydajnością wszystkich innych algorytmów ${\ displaystyle {\ mathcal {I}}}$ patrz rysunki po prawej stronie, aby zobaczyć przykłady analizy uzupełniającej) ja .
W niektórych aplikacjach obliczanie cech instancji jest powiązane z kosztem. Na przykład, jeśli metryką kosztu jest czas działania, musimy również wziąć pod uwagę czas obliczania funkcji instancji. W takich przypadkach koszt obliczeń funkcji nie powinien być większy niż wzrost wydajności dzięki doborowi algorytmu.

Domeny aplikacji

Wybór algorytmu nie ogranicza się do pojedynczych dziedzin, ale może być zastosowany do dowolnego algorytmu, jeśli spełnione są powyższe wymagania. Domeny aplikacji obejmują:

trudne problemy kombinatoryczne: SAT , Mixed Integer Programming , CSP , AI Planning , TSP , MAXSAT , QBF and Answer Set Programming
aukcje kombinatoryczne
w uczeniu maszynowym problem jest znany jako metauczenie
projektowanie Oprogramowania
optymalizacji czarnej skrzynki
systemy wieloagentowe
optymalizacja numeryczna
algebra liniowa, równania różniczkowe
algorytmy ewolucyjne
problem z trasami pojazdów
Systemy energetyczne

Aby zapoznać się z obszerną listą literatury na temat wyboru algorytmu, odsyłamy do przeglądu literatury.

Warianty wyboru algorytmu

Wybór w Internecie

Wybór algorytmu online odnosi się do przełączania między różnymi algorytmami podczas procesu rozwiązywania. Jest to przydatne jako hiper-heurystyka . Natomiast wybór algorytmu offline wybiera algorytm dla danej instancji tylko raz i przed procesem rozwiązywania.

Obliczanie harmonogramów

Rozszerzeniem wyboru algorytmu jest problem szeregowania algorytmów na instancję, w którym nie wybieramy tylko jednego rozwiązania, ale wybieramy budżet czasowy dla każdego algorytmu na podstawie instancji. Takie podejście poprawia wydajność systemów wyboru, zwłaszcza jeśli cechy instancji nie są zbyt pouczające i prawdopodobny jest niewłaściwy wybór pojedynczego rozwiązania.

Wybór portfeli równoległych

Biorąc pod uwagę rosnące znaczenie obliczeń równoległych, rozszerzeniem wyboru algorytmu do obliczeń równoległych jest wybór portfela równoległego, w którym wybieramy podzbiór algorytmów do jednoczesnego działania w portfelu równoległym.

Linki zewnętrzne