К) мутація

З погляду генетики будь–які випадково виникаючі стійкі зміни генотипу називаються мутаціями. Мутації можуть бути різного рівня: зачіпати геном (призводити до зміни кількості хромосом), окремі хромосоми (призводити до зміни порядку проходження генів або їхньої кількості) або окремі гени (при­зводити до зміни значення гена). У рамках теорії ГА під опера­цією мутації найчастіше розуміються саме генні мутації. Хромо­сомні мутації в рамках теорії ГА розглядаються як окремі види операцій перетворення: інверсія, транслокація, зсув і інші. Для виключення плутанини будемо розглядати ці операції як особ­ливий вид мутації. Геномні мутації складні в моделюванні й у ГА не використовуються.

Значення мутації полягає в можливому відтворенні важливих ком­понентів рішення, відсутніх у початковій популяції. Якщо в популяції жоден зі членів вихідної популяції не містить 1, наприклад, у першій позиції, то в процесі схрещування не можна одержати нащадка, що має цю властивість. Значення першого біта може змінитися лише вна­слідок мутації.

Операція мутації може застосовуватись до всіх хромосом по­пуляції або тільки до хромосом–нащадків отриманих в результаті схрещування, при цьому нова хромосома може заміщати бать­ківську (вихідну) або просто додаватися в популяцію.

Мутації можуть бути наступних видів:

одноточкова;

багатоточкова;

імовірнісна (по «масці»);

варіація;

інверсія;

транслокація;

інцест.

При одноточковій мутації в хромосомі–нащадку випадково змінюється одна позиція з урахуванням припустимих алельних значень (рисунок 9.11). При бінарному кодуванні однокрапкова му­тація зводиться до інвертування випадкової позиції. Імовірність мутації кожної окремо взятої позиції хромосоми визначається значенням коефіцієнта мутації. Звичайно К_мут1=0,005–0,05.

Рисунок 9.11 – Оператор одноточкової мутації

(мутація в 3–їй позиції)

У відмінності від одноточкової мутації при багатоточеч­ній мутації починаючи з випадкової позиції одночасно зміню­ються 2 і більш підряд розташовані позиції (максимальна кіль­кість одночасно змінюваних позицій визначається довжиною хромосоми)(рисунок 9.12).

Рисунок 9.12 – Оператор багатоточечної мутації

(мутували 2–ві позиції починаючи з 4–ої позиції хромосоми)

Рисунок 9.13 – Оператор імовірнісної мутації

(мутація відбулася в 2–ій позиції хромосоми)

Імовірнісна мутація полягає в зміні кожної позиції хромо­соми із заданою ймовірністю для кожної позиції по спеціальній масці (рисунок 9.13). Таким чином, крім імовірності застосування мутації до самого нащадка використовується ще ймовірність застосування мутації до кожної позиції хромосоми (для кожної позиції своя ймовірність). Такий вид мутації використовується якщо в процесі роботи ГА є можливість визначення найменш «якісних» ділянок хромосоми, інакше ні яких переваг даний вид мутації перед одноточковою та багатоточковою мутацією не має.

Рисунок 9.14 – Оператор варіації (мутація відбулася в 7–ий позиції хромосоми – молодшому розряді 2–го гена)

Варіація є різновидом імовірнісної мутації. При даному виді мутації зміні піддаються тільки молодші розряди генів, що при­зводить до незначного зсуву положення рішення–хромосоми в просторі пошуку (рисунок 9.14). Даний вид мутації доцільно засто­совувати на завершальних етапах роботи ГА для поліпшення рі­шень на околицях локальних екстремумів.

Рисунок 9.15 – Оператор інверсії (починаючи з 2–ої позиції хромо­соми порядок розташування 4–ьох біт змінився на зворотній)

Рисунок 9.16 – Оператор транслокації (ділянка хромосоми довжи­ною 3 біти перемістилася з 1–ої позиції на 5–у)

Інверсія – різновид хромосомної мутації. Дана операція поля­гає в зміні порядку проходження біт у хромосомі на зворотний (рисунок 9.15). Довжина змінюваної ділянки може бути змінена від 2 біт до довжини хромосоми, так само випадково визначається перша позиція змінюваної ділянки.

Транслокація – різновид хромосомної мутації, операція, що полягає в зміні положення (зсуві) окремої ділянки хромосоми в довільному напрямку (рисунок 9.16). Випадково визначається поча­ткова позиція ділянки, його довжина (від 1 біта до довжини хро­мосоми), величина й напрямок зсуву.

Інцест не є окремим видом мутації – це можлива стратегія за­стосування одного з видів мутації розглянутих вище, механізм самоадаптації оператора мутації. Він полягає в тому, що ймовір­ність мутації визначається для кожного нащадка на підставі генетичної близькості його батьків («близькі» і «далекі родичі»). Це призводить до дуже цікавого ефекту – при висо­кій розмаїтості генофонду популяції (перші кроки ГА) нас­лідки мутації будуть мінімальними, що дозволяє схрещуванню працювати без стороннього втручання. У випадку ж зниження розмаїтості, при «зупинці» алгоритму в локальному оптимумі, наслідки мутації стають більш відчутними, а при повному виро­дженні популяції (сходженні до локального оптимуму) алгоритм просто стає стахостичним, що збільшує ймовірність виходу популяції з локального оптимуму.

Прийнято вважати що схрещування в генетичному алгоритмі є основним пошуковим механізмом, а мутація дозволяє лише внести в процес деяку випадковість, що знижує ймовірність «застрягання» алгоритму в локальних рішеннях. Однак крім цієї метафори існує безліч інших. Наприклад, що схрещування – це механізм обмеженого перебору, що комбінує деякі бу­дівельні блоки в пошуку нових рішень; а мутація – це механізм генерації будівельного матеріалу. Із упевненістю можна ска­зати лише одне – досвід показує необхідність присутності обох механізмів в алгоритмі.