Мутация (генетичен оператор)

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето
Емблема за пояснителна страница Тази статия е за термина от биоинформатиката. За други значения вижте Мутация (пояснение).

Мутация (на английски: mutation) в областта на генетичните алгоритми е термин, с който се означава генетичен оператор, използван за поддържане на генетичното разнообразие от едно поколение на популацията на генетичен алгоритъм до следващото. Представлява метафора на биологичната мутация в областта на биоинформатиката. Под действието на мутацията една или повече стойности на ген в хромозомата се изменят в сравнение с началното състояние. Така едно решение на генетичния алгоритъм може напълно да се различава от предишното решение. Следователно, използвайки мутация, генетичният алгоритъм може да достигне до по-добро от текущото си решение. Мутацията се проявява, съгласно вероятност за мутация, определена от потребителя, която в общия случай би трябвало да бъде зададена ниска. При твърде висока вероятност за мутация, процедурата по търсене на решение ще се изроди до обикновено случайно търсене (random search).

Класическият пример за генетичния оператор мутация изисква вероятност от промяна на един бит в представяната като двоичен низ хромозома. Например, ако хромозомата представлява двоичен низ от вида 1 0 1 1 0 0 0 0 1 1 в най-простия си вид мутацията се състои само в промяната на стойността (toggle) на един от битовете (гените):

1  0  1  1  0  0  0  0  1  1
1  0  1  1  0  1  0  0  1  1

Всеки от битовете е с една и съща вероятност да бъде обект на мутация.

Типичен метод за имплементиране на мутацията, наречен с термина „точкова мутация“ (single point mutation), е генерирането на случайна променлива за всеки бит в хромозомата; тази случайна променлива носи информация дали даден конкретен бит да бъде обект на замяна или не. Други методи са суапа („размяна“, swap), вмъкването (insert), инверсията (inversion) и плаващата точкова мутация (floating point mutation). Когато генетичният код е с рестрикции, както е при задачите с пермутации, операторът мутация се свежда до инверсии, суапове (swaps) и разбърквания (scrambles).

Операторът мутация действа върху една родителска хромозома.

Целта на мутацията в генетичните алгоритми е запазването и вкарването на генетично разнообразие. Мутацията позволява на алгоритъма да избегне попадането в локален минимум, като не позволява популацията от хромозоми да започват твърде много да приличат помежду си, което причинява забавяне или дори прекъсване на еволюционния процес. С това се обяснява и факта, че повечето системи с генетични алгоритми избягват да вземат само най-приспособените индивидите (т.е. тези с най-добра фитнес функция) от една популация при генерирането на следващата популация, а вместо това правят случайна (или полуслучайна) извадка с по-висок тегловен коефициент за по-приспособените индивиди.[1]

Видове мутации[редактиране | редактиране на кода]

За всички видове мутации по-долу, нека е дадена начална хромозома във вида:

0 1 2 3 4 5 6 7 8 9
1. Суап или „размяна на местата“ (swap)
Нека бъдат избрани на случаен принцип два бита от двоичния низ на хромозомата:
0 1 2 3 4 5 6 7 8 9
След прилагане на мутация от вид суап, двата бита си разменят местата и хромозомата добива новия вид:
0 1 2 9 4 5 6 7 8 3
2. Инверсия (inversion)
Нека бъдат избрани на случаен принцип два бита от двоичния низ на хромозомата:
0 1 2 3 4 5 6 7 8 9
След прилагане на мутация от вид инверсия, низът между двата бита се обръща и хромозомата добива новия вид:
0 1 2 7 6 5 4 3 8 9
3. Вмъкване (insert)
Нека бъдат избрани на случаен принцип два бита от двоичния низ на хромозомата:
0 1 2 3 4 5 6 7 8 9
След прилагане на мутация от вид вмъкване, вторият бит се залепва за първия, измествайки с един останалите битове в хромозомата. Хромозомата добива новия вид:
0 1 8 2 3 4 5 6 7 9
4. Разбъркване (scramble)
Нека бъдат избрани на случаен принцип два бита от двоичния низ на хромозомата:
0 1 2 3 4 5 6 7 8 9
При мутацията от вид разбъркване битовете в подниза, образуван от двата случайно избрани бита (включително и тях), се разбъркват. Хромозомата добива новия вид:
0 1 2 6 3 5 4 7 8 9

Вижте също[редактиране | редактиране на кода]

Източници[редактиране | редактиране на кода]

  1. XI. Crossover and Mutation. // Marek Obitko. Посетен на 7 април 2011.