XI. Кръстосване и Мутация

Въведение

Кръстосването и мутацията са двете основни операции на GA. Изпълнението на GA много зависи от тях. Типа и изпълнението на операциите зависи от кодирането и от проблема също.

Има много начини по които да се извърши кръстосване и мутация. В тази глава има няколко примера и предложения как да се направи за няколко кодирания.

Двоично Кодиране

Кръстосване

Единична точка на кръстосване - избира се една точка на кръстосване, двоичния низ от началото на хромозомата до точката на кръстосване е копие от единия родител, останалата е копие от втория родител

11001011+11011111 = 11001111
Кръстосване в две точки - избирате се две точки на кръстосване, двоичния низ от началото на хромозомата до първата точка на кръстосване е копие от първия родител, частта от първата точка на кръстосване до втората точка на кръстосване е копие от втория родител и останалото е копие от първия родител

11001011 + 11011111 = 11011111
Еднородно кръстосване - битове произволно се копират от първия и от втория родител

11001011 + 11011101 = 11011111
Аритметично кръстосване - някоя аритметична операция се извършва за получаване на новото потомство

11001011 + 11011111 = 11001001 (AND)

Мутация

Инвертиране на бит - избрания бит се инвертира

11001001 => 10001001

Кодиране на Пермутации

Кръстосване

Кръстосване в една точка - избира се една точка на кръстосване, one crossover point is selected, до тази точка пермутацията се копира от първия родител, след това втория родител се сканира и ако номерата все още не са в потомството се добавят
Забележка: има повече начини за представяне останалото след точката на кръстосване
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Мутация

Смяна на реда - два числа се избират и се разменят

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Кодиране по Стойност

Кръстосване

Всички кръстосвания от двоично кодиране може да бъдат използвани

Мутация

Добавяне на малки числа (за кодиране на реални стойности) - към избраната стойност се добавя (или изважда) малко число

(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)

Кодиране в Дърво

Кръстосване

Кръстосване на дърво - и в двата родителя се избира една точка на кръстосване, родителите се разделят в тази точка на кръстосване и си разменят частта под точката за кръстосване за да представят новото потомство

Мутация

Смяна номера на операция - избраните възли се сменят