Mutacja w algorytmie ewolucyjnym

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Mutacja - operator przeszukiwania przestrzeni rozwiązań za pomocą algorytmu ewolucyjnego. Polega na losowej zmianie wartości niektórych (lub wszystkich) genów reprezentujących osobnika. Ma ona za zadanie zwiększyć różnorodność osobników w populacji, czyli zapobiegać przedwczesnej zbieżności algorytmu oraz eksplorować przestrzeń rozwiązań. Mutacja zachodzi z pewnym przyjętym prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania - niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie drugorzędne, szczególnie w przypadku długich chromosomów. Może być zarówno operatorem lokalnym (jak w algorytmach genetycznych), jak i operatorem globalnym (jak w strategiach ewolucyjnych).

W algorytmie genetycznym, zależnie od metody kodowania genotypu, może wyglądać następująco:

  • W przypadku chromosomów kodowanych binarnie losuje się zazwyczaj dwa geny i zamienia się je miejscami bądź np. neguje pewien wylosowany gen.
  • W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje.
  • W przypadku genotypów zakodowanych liczbami rzeczywistymi wprowadza się do przypadkowych genów losowe zmiany o danym rozkładzie - najczęściej normalnym.