Генетичні алгоритми. Механізм генетичної спадковості

ГЕНЕТИЧНІ АЛГОРИТМИ (ГА)

ГА – велика група методів випадкового глобального пошуку та багатопараметричної оптимізації.

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

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

В природі механізм генетичної спадковості влаштований так. У кожній клітині живої істоти міститься вся генетична інформація. Вона записана у вигляді набору молекул ДНК. Кожна молекула ДНК- це ланцюжок, який складається з молекул нуклеотидів чотирьох типів (A, T, C, G). Інформацію несе порядок проходження нуклеотидів у ДНК. Таким чином, генетичной код істоти – це просто дуже довгий рядок символів, де повторюються всього 4 літери. Молекула ДНК оточена оболонкою. Таке утворення називається хромосомою. Кожна природжена властивість істоти кодується певною частиною, що називається геном цієї властивості. Різні значення гена називаються його аллелями. При розмноженні відбувається взаємодія ДНК двох істот-предків і утворюється ДНК істоти-нащадка. Основний спосіб взаємодії – кросинговер (схрещування). При кросинговері ДНК істот-предків поділяються на дві частини, а потім обмінюються цими частинами. При спадковості можливі мутації, у результаті яких можуть змінитися деякі гени у одного з істот-предків. Змінені гени передаються істоті-нащадку і додають йому нові властивості. Якщо ці властивості корисні, вони здебільшого збережуться в даному виді – при цьому відбудеться стрибкоподібне підвищення пристосованості виду.

Таким чином, відмінна риса еволюційних моделей – ітераційність, виконання генетичних
циклів (Популяція 1 → Еволюція → Селекція → Репродукція → Популяція 2) і використання елементів випадку при пошуку, тобто коли моделюється пристосування популяції живих істот до навколишнього середовища.

У простому ГА початкове покоління хромосом формується випадковим вибором значень кожного гена в кожній хромосомі. Для представлення хромосоми можна використовувати структури типу фрейму з слотами-генами.

Далі починається етап еволюції. На кожному витку цього етапу формуються хромосоми нового покоління за допомогою операторів вибору предків, кросинговера, мутації, селекції. Імовірність вибору хромосоми залежить від значення відповідної їй цільової функції (функції корисності) f(s). У ГА кросинговер відповідає за передачу ознак предків нащадкам. Кросинговер використовується стосовно пари предків і включає розривання хромосом в одній або декількох позиціях і рекомбінацію фрагментів, що утворилися. У результаті з’являються пари хромосом нащадків. Мутація є вторинним процесом. Зміна тільки в одній позицій генотипу може призвести до значних змін у фенотипі. Далі виконується селекція на основі цільової функції, що у ГА на всіх етапах еволюції залишається незмінною.

Щодо ГА використовують термінологію, прийняту в генетиці. Генотип (набір генів, що характеризує ті чи інші ознаки істоти) – це конкретний набір змінних параметрів, що визначають розв’язання задачі. Фенотип (сукупність зовнішніх і внутрішніх ознак істоти) – це готова система (конструкція, структура). Пристосованість істоти залежить від якості фенотипу, що в свою чергу визначається генотипом і може оцінюватись для кожної хромосоми за допомогою відповідної цільової функції f(s). Таким чином, адаптація проходить і на рівні генотипу (для всього виду істот) і на рівні фенотипу (для окремої істоти).

З позиції задач багатовимірної оптимізації ГА представляє собою комбінацію методів. Механізм схрещування і мутації є аналогом переборних алгоритмів, а селекція – аналогом добору кращих рішень (напр. градієнтний спуск). Це дозволяє підвищити ефективність ГА для будь-яких типів задач оптимізації.

При використанні традиційних алгоритмів багатопараметричного пошуку виникає ряд труднощів:

-  різке збільшення обчислювальних витрат і часу пошуку при збільшенні числа змінних параметрів;

-  локальний характер алгоритмів пошуку, пов’язаний з необхідністю обчислення похідних цільової функції на кожному кроці пошуку;

-  можливість „зависання” алгоритму в околиці одного з локальних екстремумів;

-  низька перешкодозахищеність алгоритму;

-  низька ефективність пошуку при наявності „ярових” ситуацій.

Привабливість ГА полягає саме в тім, що вони значною мірою позбавлені зазначених недоліків.