Porównanie dwóch algorytmów genetycznych

9

Mam dwie implementacje algorytmu genetycznego, które powinny zachowywać się jednakowo. Jednak z powodu ograniczeń technicznych, których nie można rozwiązać, ich moc wyjściowa nie jest dokładnie taka sama, biorąc pod uwagę te same dane wejściowe.

Nadal chciałbym pokazać, że nie ma znaczącej różnicy w wydajności.

Mam 20 przebiegów z tą samą konfiguracją dla każdego z dwóch algorytmów, używając różnych początkowych nasion liczb losowych. Dla każdego przebiegu i generowania minimalny błąd przydatności najlepszy osobnik w populacji odnotowano. Algorytm wykorzystuje elitarny mechanizm zabezpieczający, więc sprawność najlepszej osoby spada monotonicznie. Bieg składa się z 1000 pokoleń, więc mam 1000 wartości na bieg. Nie mogę uzyskać więcej danych, ponieważ obliczenia są bardzo drogie.

Który test powinienem zastosować? Łatwym sposobem byłoby prawdopodobnie porównanie błędu tylko w końcowych generacjach (ponownie, którego testu użyłbym tutaj)? Można jednak pomyśleć o ogólnym porównaniu zachowania konwergencji.

nisc
źródło
Tylko jako wyjaśnienie: czy nie jest tak, że algorytm genetyczny losowo szuka rozwiązania, więc jest mało prawdopodobne, aby początkowy segment jakiegokolwiek badania dał jakieś wartościowe rozwiązanie? Co dokładnie rozumiesz przez „minimalny błąd w populacji”? Jeśli masz na myśli minimalną różnicę między znaną prawdziwą wartością a jakimkolwiek rozwiązaniem spośród 1000 wartości w przebiegu, to czy nie jest to stronnicze wskazanie wyniku przebiegu? W końcu w praktyce akceptowałbyś ostateczne rozwiązanie w każdym biegu i odrzucałbyś wszystko, co go poprzedza, prawda?
whuber
Przez błąd rozumiem w zasadzie 1 / fitness, więc mówię o wartości najlepszego człowieka w pokoleniu. Zarejestrowałem wartość sprawności najlepszej osoby dla każdego pokolenia. Mam więc 1000 * 20 * 2 liczb, z których każda odpowiada „kondycji” najlepszego osobnika w danym pokoleniu danego biegu.
nie
Wydaje

Odpowiedzi:

9

Testowanie algorytmów stochastycznych może być dość trudne!

Pracuję w biologii systemów i istnieje wiele symulatorów stochastycznych dostępnych do symulacji modelu. Testowanie tych symulatorów jest trudne, ponieważ dowolne dwie realizacje z jednego modelu będą zazwyczaj różne.

W dsmts obliczyliśmy (analitycznie) oczekiwaną wartość i wariancję konkretnego modelu. Następnie wykonujemy test hipotez, aby ustalić, czy symulator różni się od prawdy. Rozdział 3 instrukcji obsługi zawiera szczegółowe informacje. Zasadniczo wykonujemy test t dla średnich wartości i test chi-kwadrat dla wariancji.

W twoim przypadku porównujesz dwa symulatory, więc zamiast tego powinieneś po prostu użyć t-testu z dwoma próbkami.

csgillespie
źródło
Jak miałbym korzystać z informacji z wszystkich pokoleń?
nisc
Najprostszym sposobem jest wykonanie wielu testów, tj. Testowanie na każdym pokoleniu, a następnie użycie korekcji Bonferroni lub fdr.
csgillespie
Porównując dla każdego pokolenia, musiałbym testować na poziomie istotności 1/1000 * 0,05? Czy to nie jest trochę trudne?
nie
To prawda, ale robisz też wiele testów - nie możesz mieć wszystkiego;) Możesz uszeregować wartości p, użyć ich jako przewodnika, aby dowiedzieć się, gdzie mogą wystąpić błędy.
csgillespie
1
Zamiast korekcji bonferroni, zawsze możesz użyć mocniejszego holm bonferroni. Zobacz moją odpowiedź tutaj: stats.stackexchange.com/questions/575/…
Henrik
4

Być może mógłbyś zmierzyć średnią różnicę między dwoma przebiegami tego samego algorytmu do średniej różnicy między dwoma przebiegami z różnych algorytmów. Nie rozwiązuje problemu, jak zmierzyć tę różnicę, ale może być łatwiejszym do rozwiązania problemem. Poszczególne wartości szeregów czasowych byłyby uwzględniane w obliczeniach różnic, zamiast być traktowane jako pojedyncze punkty danych, które należy oceniać względem siebie (nie sądzę też, aby ta konkretna różnica na n-tym etapie była tym, co naprawdę chcesz składać oświadczenia o).

Aktualizacja Dotyczące szczegółów - dobrze, które funkcje szeregu czasowego są zainteresowane, poza końcowym błędem? Chyba masz trzy różne pytania do rozwiązania:

  1. Co stanowi dla ciebie podobieństwo, tj. Co masz na myśli, mówiąc, że nie wierzysz, że obie metody są różne?
  2. Jak to obliczyć - można odpowiedzieć po 1 i
  3. Jak możesz sprawdzić, czy istnieją znaczące różnice między dwiema metodami?

W pierwszym poście powiedziałem tylko, że odpowiedź na (1) prawdopodobnie nie uwzględnia indywidualnych różnic w każdym z 1000 pokoleń. I radzę wymyślić wartość skalarną dla każdej serii czasowej lub przynajmniej podobieństwo między szeregami czasowymi. Dopiero wtedy dochodzisz do rzeczywistego pytania statystycznego (o którym wiem najmniej ze wszystkich trzech punktów, ale poradzono mi, aby użyć sparowanego testu t w podobnym pytaniu, które właśnie zadałem, mając wartość skalarną na element).

użytkownik979
źródło
brzmi rozsądnie, jakieś szczegóły?
nisc