www.eprace.edu.pl » algorytmy-genetyczne » Wyniki badań » Badanie 5. Dynamiczne sterowanie parametrami algorytmu.

Badanie 5. Dynamiczne sterowanie parametrami algorytmu.

W sekcji 2.1 opisano problem przedwczesnej zbieżności i utraty materiału genetycznego. W klasycznych metodach genetycznych za ewolucję rozwiązań odpowiada głównie krzyżowanie, zaś różnorodność zapewnia mutacja. Prawdopodobieństwo krzyżowania jest z reguły bliskie lub równe 1, natomiast ustalenie prawdopodobieństwa mutacji sprawia twórcom algorytmów więcej problemów. Zwykle przyjmuje niewielkie wartości, lecz optymalna wartość prawdopodobieństwa mutacji może zależeć od wielu czynników. W przypadku stosowanej mutacji typy inwersja, skuteczność mutacji w dostarczaniu materiału genetycznego zależy od rozmiaru problemu - im więcej miast, tym mniejszy jest wpływ pojedynczej inwersji na różnorodność podpopulacji. Obrazują to typowe przebiegi różnorodności dla dwóch różnych problemów (Rys. 5.7a, 5.8a). Na wykresie 5.8a różnorodność spada do zera wkrótce po uruchomieniu algorytmu.

Przetestowano trzy różne sposoby dynamicznego wpływania na różnorodność - dwie polityki restartu podpopulacji (por. 2.3.2) oraz zaproponowany przez autora Regulator Trójpołożeniowy dla Mutacji (RTdM).

1.  Restart Div - restart następuje, gdy różnorodność podpopulacji osiągnie wartość 0.005.

2.  Restart Impr - restart następuje, gdy przez 50 kolejnych generacji nie zachodzi poprawa najlepszego rozwiązania w podpopulacji.

3.  RTdM - regulator co generację przeprowadza test, czy aktualny stan różnorodności mieści się zakresie (targetDiversity - ε, targetDiversity + ε). Jeśli nie, odpowiednio zwiększa lub zmniejsza prawdopodobieństwo mutacji.

Poniżej przedstawiono zaproponowany przez autora Regulator Trójpołożeniowy dla Mutacji:

Pobierz parametry targetDiversity, IowerBound, ε
if (currentDiversity > targetDiversity + ε) then
mutationProbability = max((mutationProbability / 1.01), IowerBound)
else if (currentDiversity < targetDiversity - ε) then
mutationProbability = min((mutationProbability * 1.01), 1.0)
end if
Oznaczenia:

  • currentDiversity - aktualna wartość różnorodności w danej podpopulacji

  • targetDiversity - docelowa wartość różnorodności

  • mutationProbability - aktualne prawdopodobieństwo różnorodności

  • IowerBound - dolna granica prawdopodobieństwa mutacji

  • ε - margines

    Dzięki tej metodzie twórca algorytmu nie musi "martwić się" o określenie wielkości mutacji, jeśli wie, jakiej różnorodności oczekuje podczas jego przebiegu. Niepokojącą konsekwencją tej metody jest ingerowanie w "naturalny" przebieg różnorodności. Także nakład obliczeniowy związany z obliczaniem różnorodności oraz korekcją parametrów może potencjalnie wydłużać działanie algorytmu.

    W tabeli przyjęto skrócone oznaczenia: t - docelowa różnorodność, LB - dolna granica prawdopodobieństwa mutacji w procentach. Wyniki przedstawia tabela 5.6.

    Tablica 5.6: Wpływ sterowania mutacją na względną różnicę jakości - D.

    Instancja RTdM t=0,01 LB=3 RTdM t=0,01 LB=5 RTdM t=0,02 LB=0 RTdM t=0.02 LB=3 RTdM t=0.02 LB=5 RTdM t=0.02 LB=7 RTdM t=0.02 LB=10 RTdM t=0.04 LB=3 RTdM t=0.04 LB=5 Restart Div. Restart Imp.
    eil51 5.68 4.23 5.82 5.92 4.23 4.51 4.51 4.93 5.35 4.18 4.04
    berlin52 6.02 4.95 8.97 3.17 4.95 5.88 5.84 6.53 6.23 4.22 4.95
    st70 5.36 4.24 7.70 6.31 6.13 4.36 8.47 6.70 4.44 5.42 4.00
    eil76 8.48 7.17 9.41 7.58 6.32 7.17 7.47 6.10 7.06 7.58 6.06
    pr76 6.32 3.83 4.72 5.12 3.88 4.69 6.09 5.51 3.14 5.80 3.59
    rat99 9.89 10.36 9.07 10.11 9.22 8.79 8.26 7.55 9.46 9.43 8.62
    kroAlOO 7.31 8.28 8.66 7.91 9.14 8.21 8.40 6.16 4.82 8.86 9.10
    kroBlOO 6.87 8.13 7.58 7.99 6.18 6.15 6.79 6.23 6.14 7.42 6.07
    kroClOO 7.17 7.81 9.91 8.67 7.69 6.86 6.73 9.29 6.96 8.11 9.97
    kroDlOO 10.01 7.17 7.50 7.94 6.28 7.40 5.43 6.84 7.04 8.43 7.53
    kroElOO 7.18 5.92 5.97 6.98 7.70 5.00 7.36 5.24 5.58 8.35 5.07
    rdlOO 10.31 11.05 8.27 10.33 7.92 8.28 8.53 7.76 6.93 9.79 8.58
    eillOl 8.65 8.43 6.42 7.69 6.01 7.00 7.98 8.17 7.34 8.71 9.16
    linl05 5.96 7.04 4.12 5.46 8.04 5.10 6.50 5.11 6.59 5.92 9.82
    prl07 6.29 6.28 7.77 9.72 5.41 7.38 6.56 5.84 8.11 7.33 6.60
    prl24 2.93 7.09 6.60 6.60 4.99 4.18 2.75 5.54 6.93 6.76 5.34
    bierl27 8.43 7.69 7.12 7.31 5.99 5.73 6.76 13.12 9.20 9.35 11.66
    chi 30 8.67 8.25 7.10 7.10 5.97 6.54 5.78 11.20 10.35 11.55 8.66
    prl36 8.83 8.41 7.56 7.56 8.72 6.87 8.27 20.55 31.83 12.73 9.55
    prl44 4.66 5.27 3.56 3.56 5.80 6.43 4.91 30.88 34.68 12.43 5.72
    chl50 10.09 7.80 8.43 8.43 10.04 8.81 10.44 49.78 60.72 15.61 12.81
    kroA150 8.01 8.92 7.61 7.61 9.26 8.46 8.24 52.87 54.42 14.48 10.10
    kroB150 10.33 7.82 9.27 9.27 8.08 9.30 9.67 36.33 53.27 10.26 10.27
    ul59 11.08 13.48 11.77 11.77 11.41 12.09 7.94 69.75 60.80 16.82 15.90
    Średnia 7.69 7.48 7.54 7.51 7.06 6.88 7.07 16.17 17.39 9.15 8.05

    Użyte usprawnienie daje dobre wyniki. Dla parametru t o wartości 0.01 lub 0.02 algorytm osiągnął lepsze wyniki (7.69, 7.48, 7.54, 7.51, 7.06, 6.88, 7.07), niż bez użycia sterowania (7.90). Również całkowity czas wykonania był znacznie krótszy (rys. 5.6).

    Okazało się także, że zezwolenie na całkowitą likwidację mutacji (LB=0) nie daje tak dobrych wyników, jak utrzymanie mutacji na minimalnym poziomie. Widać to szczególnie na przykładzie instancji o mniejszych rozmiarach.



    Rysunek 5.6: Zależność sumarycznego czasu obliczeń od częstości migracji.

    Oznaczenia: t - docelowa różnorodność, LB - minimalny poziom mutacji (w procentach)

    Rysunek 5.7: Wpływ regulacji prawdopodobieństwa mutacji na różnorodność na przykładzie instancji lin105.


    (a) Różnorodność bez zastosowania regulacji. Instancja lin105.



    (b) Regulacja prawdopodobieństwem mutacji w podpopulacjach. Instancja lin105.



    (c) Różnorodność po zastosowaniu regulacji. Instancja lin105.

    Rysunek 5.8: Wpływ regulacji prawdopodobieństwa mutacji na różnorodność na przykładzie instancji ch150.



    (a) Różnorodność bez zastosowania regulacji. Instancja ch150.



    (b) Regulacja prawdopodobieństwem mutacji w podpopulacjach. Instancja ch150.



    (c) Różnorodność po zastosowaniu regulacji. Instancja ch150.



    komentarze

  • Copyright © 2008-2010 EPrace oraz autorzy prac.