Algorytmy genetyczne - mutacja
Wprowadzenie do mutacji
Mówiąc prościej, mutację można zdefiniować jako małą, losową zmianę w chromosomie w celu uzyskania nowego rozwiązania. Służy do utrzymania i wprowadzania różnorodności w populacji genetycznej i jest zwykle stosowany z niskim prawdopodobieństwem -pm. Jeśli prawdopodobieństwo jest bardzo wysokie, GA zostaje zredukowana do wyszukiwania losowego.
Mutacja jest częścią AH, która jest związana z „eksploracją” przestrzeni poszukiwań. Zaobserwowano, że mutacja jest niezbędna do konwergencji GA, podczas gdy crossover nie.
Operatory mutacji
W tej sekcji opisujemy niektóre z najczęściej używanych operatorów mutacji. Podobnie jak operatory krzyżowania, nie jest to wyczerpująca lista i projektant GA może uznać kombinację tych podejść lub operator mutacji specyficzny dla problemu za bardziej przydatny.
Bit Flip Mutation
W tej mutacji odwracania bitów wybieramy jeden lub więcej losowych bitów i odwracamy je. Jest to używane w przypadku GA z kodowaniem binarnym.
Losowe resetowanie
Losowe resetowanie jest rozszerzeniem przerzucania bitów w reprezentacji liczb całkowitych. W tym przypadku losowa wartość ze zbioru wartości dopuszczalnych jest przypisywana do losowo wybranego genu.
Zamień mutację
W przypadku mutacji zamiany wybieramy losowo dwie pozycje na chromosomie i zamieniamy wartościami. Jest to powszechne w kodowaniach opartych na permutacji.
Mutacja mieszana
Mutacja mieszana jest również popularna w przypadku reprezentacji permutacji. W tym przypadku z całego chromosomu wybierany jest podzbiór genów, a ich wartości są losowo mieszane lub tasowane.
Mutacja inwersji
W mutacji inwersyjnej wybieramy podzbiór genów, jak w przypadku mutacji mieszanej, ale zamiast tasować podzbiór, po prostu odwracamy cały ciąg w podzbiorze.