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
- John Holland, Adaptacja w systemach naturalnych i sztucznych, University of Michigan Press , Ann Arbor, Michigan. 1975. ISBN 0-262-58111-6 .