Головна

генетичні оператори

  1. Арифметичні і логічні оператори
  2. арифметичні оператори
  3. векторні оператори
  4. Генетичні закономірності мінливості
  5. Генетичні методи отримання активних продуцентів АБ
  6. генетичні чинники

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

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

генетичний операторза аналогією з оператором алгоритму - засіб відображення одного безлічі на інше. Іншими словами, це конструкція, що представляє один крок з послідовності дій генетичного алгоритму. Розглянемо основні оператори генетичних алгоритмів.

Оператор репродукції (селекція) - Це процес, за допомогою якого хромосоми (альтернативні рішення), що мають більш високе значення цільової функції (з «кращими» ознаками), отримують більшу можливість для відтворення (репродукції) нащадків, ніж «гірші» хромосоми. Елементи, вибрані для репродукції, обмінюються генетичним матеріалом, створюючи аналогічних або різних нащадків. Існує велика кількість видів операторів репродукції:

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

- Селекція на основі заданої шкали.Тут популяція попередньо сортується від «кращої» до «гіршою» на основі заданого критерію. Кожному елементу призначається певне число і тоді селекція виконується згідно з цим числом.

- Елітна селекція.В цьому випадку вибираються кращі (елітні) елементи на основі порівняння значень цільової функції. Далі вони вступають в різні перетворення, після яких знову вибираються елітні елементи. Процес триває аналогічно до тих пір, поки продовжують з'являтися елітні елементи.

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

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

- «Випадковий вибір хромосом;

- Вибір хромосом на основі значень цільової функції.

При випадковому виборі хромосом частота R освіти батьківських пар не залежить від значення цільової функції хромосом  і повністю визначається чисельністю популяції N:

,

де ? - коефіцієнт селекції, який приймає залежно від умов зовнішнього середовища значення 1 ... 4.

Інший спосіб реалізації оператора репродукції пов'язаний з використанням значень цільової функції. Існують дві основні стратегії.

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

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

 (2)

де ЦФ - цільова функція, ОР - це оператор репродукції, що моделює природний процес селекції, Рr(ОР) - ймовірність вибору хромосом для репродукції.

Друга стратегія реалізується так: частина хромосом вибирається випадковим чином, а друга - з ймовірністю на основі виразу (2).

якщо

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

Крім описаних, існує велика кількість інших методів селекції, які можна умовно класифікувати на три групи.

До першої групи віднесемо імовірнісні методи.

до другої - Детерміновані методи.

До третьої - Різні комбінації методів з першої і другої груп. Побудова нових операторів репродукції безперервно триває.

Наведемо тепер оператори кросинговеру (схрещування).оператор кроссинговера- це мовна конструкція, що дозволяє на основі перетворення (схрещування) хромосом батьків (або їх частин) створювати хромосоми нащадків. Існує величезна кількість операторів кросинговеру, так як їх структура в основному і визначає ефективність генетичних алгоритмів. Коротко розглянемо основні оператори кросинговеру, відомі в літературі, і їх модифікації.

Структура генетичних алгоритмів | Простий (одноточковий) оператор кросинговеру


Максімаксний критерій | Критерій песимізму-оптимізму (критерій Гурвіца) | Критерій недостатнього підстави (критерії Лапласа) | Критерій минимакса жалю (минимаксного ризику) (критерії Севіджа) | ЕВОЛЮЦІОННОНОЕ МОДЕЛЮВАННЯ | Еволюція природних і штучних систем | еволюція Дарвіна | Еволюції Ламарка, де Фріза, Поппера і синтетична теорія еволюції | Еволюція складних систем | Визначення і поняття генетичних алгоритмів |

© 2016-2022  um.co.ua - учбові матеріали та реферати