Surrogate Management Strategies for Accelerating Parallel Algorithm Portfolio Construction
Wiele algorytmów wymaga starannego doboru parametrów, od czego w dużym stopniu zależy ich efektywność, przy czym żadna pojedyncza konfiguracja nie zapewnia najlepszych wyników dla wszystkich typów problemów. Automatyczna konfiguracja algorytmów umożliwia systematyczne przeszukiwanie przestrzeni parametrów i znajdowanie konfiguracji optymalnych dla danego problemu. Automatyczne konstruowanie równoległego portfolio algorytmów (ACPP, ang. Automatic Construction of Parallel Portfolio) rozwija tę ideę poprzez konfigurowanie i równoległe uruchamianie wielu solverów, wykorzystując ich wzajemnie uzupełniające się zalety w celu poprawy zdolności do uogólniania. Pomimo postępów w rozwoju metod ACPP, istniejące podejścia traktują czas konstrukcji portfolio jako stały zasób. Nie wykorzystują również w pełni danych o wynikach algorytmów zbieranych podczas konfigurowania portfolio. Aby przezwyciężyć to ograniczenie, w proponowanym rozwiązaniu wykorzystujemy dane generowane podczas konstruowania portfolio do uczenia modeli zastępczych, które zastępują kosztowne ewaluacje, zmniejszając narzut obliczeniowy. Aby wybrać skuteczne modele zastępcze, porównujemy różne metody uczenia maszynowego, w tym modele z dziedziny analizy przeżycia do obsługi danych cenzurowanych. Zdolności predykcyjne tych modeli oceniamy na podstawie danych wygenerowanych przez solver LKH podczas rozwiązywania instancji problemu komiwojażera. Na koniec proponujemy kilka strategii zarządzania modelami zastępczymi i włączamy je do istniejących metod konstruowania portfolio. Uzyskane wyniki wykazują, że modele oparte na analizie przeżycia zapewniają lepszą jakość predykcji niż standardowe metody uczenia maszynowego. Proponowane strategie zarządzania modelami zastępczymi pozwalają znacznie skrócić czas konstruowania portfolio przy zachowaniu akceptowalnej efektywności jego działania na nieznanych wcześniej instancjach testowych.
Artykuł:
IEEE Transactions on Evolutionary Computation
Autorzy z PW:
Grzegorz Zakrzewski, Jacek Mańdziuk
Dyscyplina:
Rok wydania: