Проста мутація

Проста мутація використовується для бінарних, гомологічних числових і векторних хромосом. Суть її полягає у внутригенній мутації. При цьому в хромосомі випадковим чином вибирається ген, а потім відбувається його випадкова зміна.

Алгоритм простої мутації для бінарних і гомологічних числових хромосом може складатися з наступних кроків.

Крок 1. Скопіювати батьківську хромосому в хромосому‑ нащадка.

Крок 2. Вибрати випадковим чином ген для мутації.

Крок 3. У заданому інтервалі припустимих значень гена вибрати нове значення гена, що не дорівнює поточному.

Для векторних хромосом проста мутація відбувається шляхом внесення змін у порядок елементів усередині обраного гена.

Крок 1. Скопіювати батьківську хромосому в хромосому‑ нащадка.

Крок 2. Вибрати випадковим чином ген для мутації.

Крок 3. Вибрати випадковим чином точку мутації усередині мутуючого гена.

Крок 4. Зробити обмін значеннями між розрядами мутуючого гена, що перебувають безпосередньо ліворуч і праворуч від точки мутації.

Відомий також модифікований оператор простої мутації, що називається точковою мутацією, який відрізняється тим, що в хромосомі мутує не один, а кілька генів із заданою ймовірністю. Такий оператор використовується для бінарних, гомологічних числових і векторних хромосом. Алгоритм даного оператору наведений нижче.

Крок 1. Скопіювати батьківську хромосому в хромосому‑ нащадка.

Крок 2. Встановити i = 1.

Крок 3. Випадковим чином згенерувати число xi з інтервалу [0;1).

Крок 4. Якщо число x_i виявляється меншим ймовірності мутації гену Р_мг, то виконати мутацію гена h_i.

Крок 5. Встановити i = i + 1.

Крок 6. Якщо i < (L + 1), де L – довжина хромосоми, то виконати перехід на крок 3.

Крок 7. Кінець.

Крім того, відома множина різних варіантів операторів мутації. Більшість із них використовують комбінації наступних ідей.

1. Так само як і схрещування, мутація може проводитися не тільки по одній випадковій точці. Можна вибирати деяку кількість точок у хромосомі для інверсії, причому їхнє число також може бути випадковим.

2. Піддається мутації відразу деяка група послідовних генів.

3. Спільне застосування випадкової мутації та часткової перебудови рішення алгоритмами локального пошуку. Застосування локального спуску дозволяє генетичному методу зосередитися тільки на локальних оптимумах. Множина локальних оптимумів може виявитися експоненціально більшим і на перший погляд здається, що такий варіант методу не буде мати великих переваг. Однак експериментальні дослідження розподілу локальних оптимумів свідчать про високу концентрацію їх у безпосередній близькості від глобального оптимуму. Це спостереження відоме як гіпотеза про існування “великої долини” для задач на мінімум або “центрального гірського масиву” для задач на максимум.

<== попередня сторінка	\|	наступна сторінка ==>
Мутація	\|	Мутація гомологічних числових хромосом

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.