Algorytm genetyczny: Wyższa częstość mutacji prowadzi do niższego czasu pracy

Question

Wdrożyłem algorytm genetyczny, aby rozwiązać udoskonalony problem Travelling Salesman (ciężar krawędzi zmienia się wraz z porą dnia). Obecnie jestem oceny różnych parametrów mojej symulacji i natknąłem się na korelacji nie mogę wytłumaczyć sobie:

Wyższy wskaźnik mutacja prowadzi do mniejszej czasie wykonywania. Osobiście zakładam, że jest inaczej, ponieważ wyższy wskaźnik mutacji powoduje więcej operacji. (25% Współczynnik mutacji jest o 12% szybszy niż 5%)

Najlepsze wyniki osiąga się, gdy współczynnik mutacji wynosi 8% (5% jest lepsze niż 10%, a 25% działa najgorzej (z wyjątkiem 0%)) A niższa wartość fitness jest lepsza.

Ilość iteracji jest ustawiony przez parametr generacji, który jest ustawiony na 10000 we wszystkich przypadkach testowych.

Każdy przypadek testowy jest wykonywany 10 razy.

Moja implementacja (w Pythonie) mutacji wygląda następująco:

def mutate(self,p): 
    for i in self.inhabitants: 
     r = random() 
     if r <= p: 
      i.mutate() 

p jest tempo mutacji

Mutacja wygląda to

def mutate(self): 
    r1 = randint(0,self.locations.size()-1) 
    r2 = randint(0,self.locations.size()-1) 
    self.locations.swap(r1,r2) 

Dlaczego wyższy mutację stopa prowadzi do szybszego czasu realizacji?

Edit: I faktycznie prowadził te same testy na moim Raspberry Pi (który jest 9 razy wolniej), a to prowadzi do tego samego rezultatu:

Answer 1

każdym cyklu i mutacji ma prawdopodobieństwa P _i zapewnienia akceptowalnego roztworu, a czas potrzebny do oceny cyklu jest T _i. Zarówno wzrost, jak i szybkość mutacji zwiększają się zarówno w zwiększaniu, jak i zmniejszaniu. Oczekiwany czas działania algorytmu jest zatem sumą oczekiwanej liczby cykli wymaganych do znalezienia odpowiedzi. Wyższa częstość mutacji zwiększa wielkość każdego z terminów, ale zmniejsza liczbę terminów do sumy. Istnieje optymalna stopa mutacji, która minimalizuje tę sumę.

Answer 2

Niemożliwe jest wiedzieć nie widząc swój pełny kod, ale następujący wydaje się prawdopodobne:

Gdy tempo mutacji jest niższa potem, po kilku pokoleniach, populacja staje się bardziej jednorodna niż to robi kiedy mutację stawka jest wyższa.Pod założeniem, że używasz pewnej odmiany próbkowania koła ruletki, bardziej jednorodna populacja oznacza, że ​​każde "zakręcenie" koła ruletki trwa średnio dłużej niż wtedy, gdy masz bardziej zróżnicowaną populację (gdzie stosunkowo niewielu członków zdominuje dystrybucję dopasowania, a zatem są wybierane po zeskanowaniu mniejszej liczby członków populacji).

Aby mieć pewność, można użyć narzędzia do profilowania, takiego jak cProfile, aby zobaczyć, gdzie dokładnie przebiegają cykle procesora.