Pytanie Algorytmy aproksymacji testów jednostkowych


Pracuję nad biblioteką algorytmów aproksymacji open source dla wykresów i sieci, wykorzystując jako bazę kilka popularnych pakietów Pythona. Głównym celem jest objęcie aktualnych algorytmów aproksymacyjnych dla problemów NP-Complete nad wykresami i sieciami. Powodem tego jest 1) Nie widziałem ładnego (nowoczesnego) skonsolidowanego pakietu, który obejmuje to i 2) byłoby to miłe narzędzie pedagogiczne do poznawania algorytmów aproksymacyjnych w problemach optymalizacji NP-Hard.

W budowaniu tej biblioteki używam testów jednostkowych do sprawdzenia poprawności (jak każdy właściwy programista). Jestem nieco ostrożny w testach jednostkowych, ponieważ z samej swojej natury algorytmy aproksymacyjne mogą nie zwracać poprawnego rozwiązania. Obecnie ręcznie rozwiązuję niektóre małe instancje, a następnie upewniam się, że zwracany wynik pasuje do tego, ale nie jest to pożądane ani skalowalne w sensie implementacji.

Jaki byłby najlepszy sposób na algorytmy aproksymacji testów jednostkowych? Generuj losowe instancje i upewnij się, że zwrócone wyniki są mniejsze niż granica gwarantowana przez algorytm? Wydawałoby się, że ma fałszywe alarmy (test właśnie miał szczęście, że czas nie jest gwarantowany dla wszystkich przypadków poniżej granicy).


12
2017-09-12 16:55


pochodzenie


Jeśli wygenerujesz "przypadkowe instancje" dla problemów NP-zupełnych, to jak rozpoznasz prawdziwą odpowiedź w celu przetestowania granic? IMHO nadal musisz ostrożnie wybierać swoje przypadki testowe. Wybierz przypadki, w których możesz, jako człowiek, znaleźć prawdziwą odpowiedź, ale to może, ale nie musi, okazać się trudne, lub przynajmniej wykonywać algorytm aproksymacji. Takie przypadki mogą być generowane programowo, aby były wystarczająco duże, aby były realistyczne. Po prostu nie powinny losowy. - Ray Toal
Rozszerzając komentarz @Ray Toal, istnieją pewne rodzaje trudnych problemów, które są łatwe, jeśli wygenerujesz problem; np. faktoring pq jest trudne, chyba że już wiesz str i q ponieważ je wygenerowałeś. Czy podobną zasadę można zastosować do problemów z wykresem / siecią? - Tom Zych
+1 Tom to dokładnie to, co mam na myśli, programowo generując znane przypadki. Trochę się waham, aby dodać odpowiedź w tej chwili, ponieważ nie jestem autorytetem w tej dziedzinie; może ktoś może przyjść, kto ma tutaj doświadczenie. Właśnie próbowałem umieścić czerwoną flagę wokół słowa "losowy". - Ray Toal


Odpowiedzi:


Musisz tutaj oddzielić dwie kwestie. Jakość Twoich algorytmów aproksymacyjnych i poprawność implementacji tych algorytmów.

Testowanie jakości algorytmu aproksymacji zwykle nie nadaje się do metod testowania jednostkowego wykorzystywanych w tworzeniu oprogramowania. Na przykład trzeba wygenerować losowe problemy, które są reprezentatywne dla rzeczywistych rozmiarów problemów. Być może trzeba będzie wykonać pracę matematyczną, aby uzyskać górną / dolną granicę, aby ocenić jakość algorytmów dla nierozwiązywalnych dużych instancji. Lub użyj zestawów testów problemów, które mają znane lub najlepiej znane rozwiązania i porównaj wyniki. Ale w każdym razie testowanie jednostkowe nie pomogłoby ci w poprawie jakości algorytmów aproksymacyjnych. Tutaj pomoże Twoja wiedza w dziedzinie optymalizacji i matematyki.

Poprawność twojego wdrożenia polega na tym, że testy jednostkowe będą naprawdę użyteczne. Możesz tutaj używać problemów związanych z zabawkami i porównywać znane wyniki (rozwiązywać ręcznie lub weryfikować przez ostrożne, krok po kroku debugowanie w kodzie) z tym, co generuje twój kod. Posiadanie niewielkich problemów jest nie tylko wystarczające, ale również pożądane, aby testy przebiegały szybko i mogły być uruchamiane wiele razy podczas cyklu programowania. Tego typu testy gwarantują, że ogólny algorytm osiąga prawidłowy wynik. Znajduje się gdzieś pomiędzy testem jednostkowym a testami integracyjnymi, ponieważ testujesz dużą część kodu jako czarną skrzynkę. Ale stwierdziłem, że tego typu testy są niezwykle użyteczne w dziedzinie optymalizacji. Jedną z rzeczy, które polecam robić dla tego typu testowania jest usunięcie całej losowości w twoich algorytmach poprzez ustalone nasiona dla generatorów liczb losowych. Testy te powinny zawsze przebiegać w deterministyczny sposób i dać dokładnie taki sam wynik w 100% przypadków. Polecam również testowanie jednostkowe w modułach niższego poziomu waszych algorytmów. Wyizoluj tę metodę, która przypisuje wagi do łuków na wykresie i sprawdź, czy są przypisane prawidłowe wagi. Wyizoluj funkcję obliczania wartości funkcji celu i test jednostki. Dostajesz mój punkt widzenia.

Kolejną kwestią, która ogranicza oba te plasterki, jest wydajność. Nie można wiarygodnie sprawdzić wydajności przy małych problemach z zabawkami. Bardzo pożądane jest również dokonanie zmiany, która znacząco obniża wydajność dla działającego algorytmu. Gdy masz już działającą wersję swoich algorytmów, możesz utworzyć większe problemy testowe, w których mierzysz wydajność i automatyzujesz testy wydajności / integracji. Możesz uruchamiać je rzadziej, ponieważ zajmie to więcej czasu, ale przynajmniej powiadomi Cię wcześniej o nowych wąskich gardłach wydajności podczas refaktoryzacji lub nowych funkcji dodawanych do algorytmów


3
2017-09-12 18:10





Sprawdzenie poprawności produkowanych rozwiązań jest oczywistym pierwszym krokiem.

Dodatkowo może być jeden kąt natarcia testowanie regresji wykorzystanie wystąpień, dla których znane jest oczekiwane przybliżone rozwiązanie (np. uzyskane przez ręczne wykonanie algorytmu lub zastosowanie innej implementacji tego samego algorytmu przez kogoś innego).

Istnieją również repozytoria przypadków problemów ze znanymi (optymalnymi) rozwiązaniami, takimi jak TSPLIB w przypadku problemów podobnych do TSP. Być może można to wykorzystać.

Jeśli znane są górne granice dla danego algorytmu, generowanie wielu przypadkowych instancji i weryfikowanie heurystycznych rozwiązań w górnych granicach może okazać się przydatne. Jeśli to zrobisz, zachęcam cię do tego, aby odtwarzane były powtórzenia (np. Zawsze używając tego samego generatora liczb losowych i materiału siewnego).

Ostatnia uwaga: w przypadku niektórych problemów całkowicie przypadkowe instancje są dość łatwe do znalezienia dobrych, przybliżonych rozwiązań. Asymetryczny TSP z równomiernie i niezależnie wybranymi obciążnikami łukowymi jest jednym z takich przykładów. Wspominam o tym, ponieważ może to wpłynąć na twoją strategię testowania.


2
2017-09-12 17:31





Zwykle jest coś, co można sprawdzić - na przykład, że algorytm zawsze zwraca rozwiązania, które spełniają ich ograniczenia, nawet jeśli nie są optymalne. Powinieneś także umieszczać kontrole sprawdzające przy każdej możliwej okazji - będą one specyficzne dla twojego programu, ale mogą sprawdzić, czy pewna ilość jest zachowana, lub że coś, co powinno wzrosnąć, lub w najgorszym przypadku to samo nie zmniejsza się, lub że niektóre z rzekomych lokalnych optimum jest naprawdę lokalnym optimum.

Biorąc pod uwagę tego rodzaju kontrole i kontrole na granicach, które już wspomniałeś, preferuję przeprowadzanie testów na bardzo dużej liczbie losowo generowanych małych problemów, z losowymi nasionami dobranymi w taki sposób, że jeśli zawiedzie w przypadku problemu 102324, możesz powtórzyć to niepowodzenie debugowania bez przechodzenia przez problemy 102323 przed nim. Przy dużej liczbie problemów zwiększasz szansę, że podstawowy błąd spowoduje błąd wystarczająco oczywisty, aby nie wykonać czeku. Przy niewielkich problemach zwiększasz szansę, że będziesz w stanie znaleźć i naprawić błąd.


1
2017-09-12 18:37