ло описано вище), а багатоточковий, коли формується кілька точок розриву (найчастіше дві). Крім того, в деяких реалізаціях алгоритму оператор мутації являє собою інверсію тільки одного випадково вибраного біта хромосоми.
1.4. Схема функціонування генетичного алгоритму
Тепер, знаючи як інтерпретувати значення генів, перейдемо до опису функціонування генетичного алгоритму. Розглянемо схему функціонування генетичного алгоритму в його класичному варіанті.
Ініціювати початковий момент часу t = 0. Випадковим чином сформувати початкову популяцію, що складається з k особин. p> Обчислити пристосованість кожної особини і популяції в цілому (також іноді звану терміном фіттнес). Значення цієї функції визначає наскільки добре підходить особина, описана даної хромосомою, для вирішення завдання. p> 1. Вибрати особина з популяції. p> 2. З певною ймовірністю (вірогідністю кросовера) вибрати другу особина з популяції і справити оператор кросовера.
3. З певною ймовірністю (вірогідністю мутації) виконати оператор мутації. p> 4. З певною ймовірністю (вірогідністю інверсії) виконати оператор інверсії.
5. Помістити отриману хромосому в нову популяцію
6. Виконати операції, починаючи з пункту 3, k разів. p> 7. Збільшити номер поточної епохи t = t +1. p> 8. Якщо виконалось умова зупинки, то завершити роботу, інакше перехід на крок 2 [13].
Розпишемо більш докладно наступні етапи:
1. Вибір батьківської пари.
Перший підхід найпростіший - це випадковий вибір батьківської пари ("панміксія"), коли обидві особини, які складуть батьківську пару, випадковим чином вибираються з всієї популяції, причому кожна особина може стати членом кількох пар. Незважаючи на простоту, такий підхід універсальний для вирішення різних класів завдань. Однак він досить критичний до чисельності популяції, оскільки ефективність алгоритму, що реалізує такий підхід, знижується із зростанням чисельності популяції. p> Другий спосіб вибору особин в батьківську пару - так званий селективний. Його суть полягає в тому, що "батьками" можуть стати тільки ті особини, значення пристосованості яких не менше середнього значення пристосованості по популяції, при рівній ймовірності таких кандидатів скласти шлюбну пару. Такий підхід забезпечує більш швидку збіжність алгоритму. Однак через швидкої збіжності селективний вибір батьківської пари не підходить тоді, коли ставитися завдання визначення декількох екстремумів, оскільки для таких завдань алгоритм, як правило, швидко сходиться до одного з рішень. Крім того, для деякого класу задач зі складним ландшафтом пристосованості швидка збіжність може перетворитися на передчасну збіжність до Квазіоптимальний рішенню. Цей недолік може бути частково компенсований використанням належного механізму відбору (про що буде сказано нижче), який би "Гальмував" занадто швидку збіжність алгоритму. p> Інші два способу формування батьківської пари, на які хотілося б звернути увагу, це інбридинг і аутбридинг. Обидва ці методу побудовані на формуванні пари на основі близького і далекого "спорідненості" відповідно. Під "Спорідненістю" тут розуміється відстань між членами популяції як в сенсі геометричного відстані особин у просторі параметрів. У зв'язку з цим будемо розрізняти генотипних і фенотипні (або географічний) інбридинг і аутбридинг. Під інбридингом розуміється такий метод, коли перший член пари вибирається випадково, а другим з більшою ймовірністю буде максимально близька до нього особина. Аутбридинг ж, навпаки, формує шлюбні пари з максимально далеких особин. Використання генетичних інбридингу і аутбридинга виявилося більш ефективним в порівнянні з географічним для всіх тестових функцій при різних параметрах алгоритму. Найбільш корисно застосування обох представлених методів для багатоекстремального завдань [14]. Проте два цих способу по-різному впливають на поведінку генетичного алгоритму. Так інбридинг можна охарактеризувати властивістю концентрації пошуку в локальних вузлах, що фактично призводить до розбиття популяції на окремі локальні групи навколо підозрілих на екстремум ділянок ландшафту, навпаки аутбридинг як раз спрямований на попередження збіжності алгоритму до вже знайденим рішенням, змушуючи алгоритм переглядати нові, недосліджені області. p> 2. Механізм відбору
Обговорення питання про вплив методу створення батьківських пар на поведінку генетичного алгоритму неможливо вести у відриві від реалізованого механізму відбору при формуванні нового покоління. Найбільш ефективні два механізми відбору елітний і відбір з витісненням. p> Ідея елітного відбору, загалом, не нова, цей метод заснований на побудові нової популяції тільки з кращих особин репродукційної групи, що об'єднує в собі батьків, їхніх нащадків і мутантів. В основному це пояснюють потенційною небезпекою передчасної збіжності, віддаючи перевагу пропорційному відбору. Швидка збіжність, що забезпечується елітним ві...
