Mutacja (algorytm genetyczny) - Mutation (genetic algorithm)

Mutacja to operator genetyczny używany do utrzymania różnorodności genetycznej z jednego pokolenia populacji chromosomów algorytmu genetycznego do następnego. Jest to analogiczne do mutacji biologicznej . Mutacja zmienia jedną lub więcej wartości genu w chromosomie ze stanu początkowego. W mutacji rozwiązanie może się całkowicie zmienić w stosunku do poprzedniego rozwiązania. W związku z tym GA może znaleźć lepsze rozwiązanie za pomocą mutacji. Mutacja występuje podczas ewolucji zgodnie z prawdopodobieństwem mutacji definiowanym przez użytkownika. Prawdopodobieństwo to powinno być ustawione na niskim poziomie. Jeśli jest ustawiony zbyt wysoko, wyszukiwanie zmieni się w prymitywne wyszukiwanie losowe.

Klasyczny przykład operatora mutacji obejmuje prawdopodobieństwo, że dowolny bit w sekwencji genetycznej zostanie odwrócony ze swojego pierwotnego stanu. Powszechna metoda implementacji operatora mutacji obejmuje generowanie zmiennej losowej dla każdego bitu w sekwencji. Ta zmienna losowa mówi, czy dany bit zostanie odwrócony. Ta procedura mutacji, oparta na biologicznej mutacji punktowej , nazywana jest mutacją jednopunktową. Inne typy to mutacje inwersyjne i zmiennoprzecinkowe. Kiedy kodowanie genów jest restrykcyjne, jak w przypadku problemów z permutacją, mutacje to zamiany, inwersje i mieszanie.

Celem mutacji w GA jest wprowadzenie różnorodności do badanej populacji. Operatory mutacji są używane w celu uniknięcia lokalnych minimów poprzez zapobieganie nadmiernemu zbliżaniu się populacji chromosomów do siebie, a tym samym spowolnieniu lub nawet zatrzymaniu zbieżności do globalnego optimum. To rozumowanie prowadzi również większość systemów AH do unikania brania tylko najsilniejszych z populacji w generowaniu następnej generacji, ale raczej do wybierania losowego (lub półlosowego) zestawu z wagą w kierunku tych, którzy są lepiej przygotowani.

W przypadku różnych typów genomu odpowiednie są różne typy mutacji:

  • Mutacja ciągu bitowego
Mutacja ciągów bitów następuje poprzez przerzucanie bitów w losowych pozycjach.
Przykład:
1 0 1 0 0 1 0
1 0 1 0 1 1 0
Prawdopodobieństwo mutacji bitu wynosi , gdzie jest długością wektora binarnego. W ten sposób osiągany jest wskaźnik mutacji na mutację i osobnika wybranego do mutacji.
  • Odwróć bit

Ten operator mutacji pobiera wybrany genom i odwraca bity (tj. jeśli bit genomu wynosi 1, jest zmieniany na 0 i odwrotnie).

  • Granica

Ten operator mutacji losowo zastępuje genom dolną lub górną granicą. Może to być używane do genów całkowitych i pływających.

  • Niejednolite

Prawdopodobieństwo, że ilość mutacji spadnie do 0 z następną generacją, jest zwiększane przez użycie niejednorodnego operatora mutacji. Zapobiega stagnacji populacji we wczesnych stadiach ewolucji. Dostraja rozwiązanie w późniejszych stadiach ewolucji. Ten operator mutacji może być używany tylko w przypadku genów całkowitych i pływających.

  • Mundur

Operator ten zastępuje wartość wybranego genu jednolitą wartością losową wybraną pomiędzy górną i dolną granicą określoną przez użytkownika dla tego genu. Ten operator mutacji może być używany tylko w przypadku genów całkowitych i pływających.

  • Gaussa

Operator ten dodaje do wybranego genu jednostkę o rozkładzie gaussowskim o losowej wartości. Jeśli wykracza poza dolną lub górną granicę określoną przez użytkownika dla tego genu, nowa wartość genu jest obcinana. Ten operator mutacji może być używany tylko dla genów całkowitych i pływających.

  • Kurczyć

Operator ten dodaje losową liczbę wziętą z rozkładu Gaussa ze średnią równą oryginalnej wartości każdej zmiennej decyzyjnej charakteryzującej wejściowy wektor macierzysty.

Zobacz też

Bibliografia

Bibliografia