загрузка...
загрузка...
На головну

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

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

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

оператор -це мовна конструкція, що представляє один крок з послідовності дій або набору описів алгоритму.

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

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

2. Розглянемо основні оператори генетичних алгоритмів.

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

Існує велика кількість видів операторів репродукції. До них належать такі:

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

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

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

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

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

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

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

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

,

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

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

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

 ()

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

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

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

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

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

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

5.1. Простий (одноточковий) оператор кросинговеру. Перед початком роботи одноточечного оператора кросинговеру визначається так звана точка оператора кросинговеру, або розрізає точка оператора кросинговеру, яка зазвичай визначається випадково. Ця точка визначає місце в двох особин, де вони повинні бути «розрізані». Наприклад, нехай популяція Р складається з хромосом P1 и P2, Які виступають в якості батьків, Р ={ P1, P2}. Нехай перший другий батьки мають вигляд P1: 11111, P2: 00000. Виберемо точку оператора кросинговеру між другим і третім генами в P1, P2. Тоді, змінюючи елементи після точки оператора кросинговеру між двома батьками, можна створити два нових нащадка. У нашому прикладі отримаємо

Отже, одноточковий оператор кросинговеру виконується в три етапи:

1. Дві хромосоми А =  і В = вибираються випадково з поточної популяції.

2. Число k вибирається з {1,2, ..., n -1} також випадково. Тут L - довжина хромосоми, k - Точка оператора кросинговеру (номер, значення або код гена, після якого виконується розріз хромосоми).

3. Дві нові хромосоми формуються з А и В шляхом перестановок елементів згідно з правилом

= ,

= .

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

5.2. Двоточковий оператор кросинговеру. У кожній хромосомі визначаються дві точки оператора кроссинговер, і хромосоми обмінюються ділянками, розташованими між двома точками оператора кроссинговер. наприклад:

Відзначимо, що точка оператора кроссинговер в двоточковому операторі кросинговеру також визначається випадково. Існує велика кількість модифікацій двухточечного оператора кросинговеру. Розвитком двухточечного оператора кросинговеру є многоточечний або N-точковий оператор кросинговеру. Багатоточкове оператор кросинговеру виконується аналогічно Двоточковий, хоча велика кількість «розрізаних» точок може призвести до втрати «хороших» батьківських властивостей.

Приклад трехточечного оператора кросинговеру:

Тут точки оператора кросинговеру ділять хромосому на ряд будівельних блоків (в даному випадку 4). нащадок  утворюється з непарних блоків батька  і чітких блоків батька  . нащадок  утворюється відповідно з непарних блоків батька  і чітких блоків батька .

Тоді многоточечний оператор кросинговеру однакова.

5.3. Упорядкований оператор Кросинговер. Тут «розрізає» точка також вибирається випадково. Далі відбувається копіювання лівого сегмента в  . Інші позиції у  беруться з  в упорядкованому вигляді зліва направо, виключаючи елементи, які вже потрапили в  . наприклад:

отримання  може виконуватися різними способами. Найбільш поширений метод копіювання лівого сегмента з  , А далі аналіз  методом, зазначеним вище. тоді маємо  : (G A B E eC D F H).

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

Аналогічно можна отримати :

5.5. Циклічний оператор кросинговеру. Циклічний оператор кросинговеру виконує рекомендації згідно циклам, які існують при встановленні відповідності між генами першого і другого батьків. Наприклад, нехай популяція Рскладається з двох хромосом: Р = { и  }. Перший і другий батьки і їх нащадок мають вигляд:

При виконанні циклічного оператора кросинговеру  заповнюється, починаючи з першої позиції, і копіює елемент з першої позиції  . Елементу 1 в  відповідає елемент 5 в  . Отже, сформований перший шлях в циклі (1,5). Елементу 5 в  відповідає елемент 4 в  , Звідки другий шлях в першому циклі (1,5; 5,4). Продовжуючи далі, отримаємо, що елементу 4 в  відповідає елемент 1 в  . Отже, сформований перший цикл (1,5; 5,4; 4,1). Згідно з цим циклу елемент 5 переходить в п'яту позицію  , А елемент 4 - в четверту позицію.

Сформуємо тепер другий цикл. Елемент 2 в  відповідає елементу 3 в  . Продовжуючи аналогічно, отримаємо другий (2,3; 3,9; 9,6; 6,8; 8,2) і третій (7,10; 10,7) цикли.

Отже, в  елемент 3 розташований в другому локусі, тобто на другій позиції, елемент 9 - в третьому, елемент 6 - в дев'ятому, елемент 8 - в шостому, елемент 2 - у восьмому, елемент 10 - в сьомому і елемент 7 - в десятому локусах. Циклічний оператор кросинговеру і його модифікації ефективно застосовуються для вирішення комбинаторно-логічних задач, задач на графах і гіперграфах і інших оптимізаційних задач.

5.6. Універсальний оператор кросинговеру. В даний час він популярний для вирішення різних завдань з теорії розкладів. Замість використання розрізає точки (точок) в універсальний оператор кросинговеру вводять двійкову маску, довжина якої дорівнює довжині заданих хромосом. Перший нащадок виходить складанням першого батька з маскою на основі наступних правил: (0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0). Другий нащадок виходить аналогічним чином. Для кожного елемента в ,  гени змінюються, як показано на наступному прикладі:

 - маска

Маска може бути задана або вибирається випадково з заданою вірогідністю або на основі генератора випадкових чисел. При цьому чергування 0 і 1 в масці відбувається з ймовірністю »50%. У деяких випадках використовується параметризованих універсальний оператор кросинговеру, де маска може вибиратися з ймовірністю для 1 або 0 вище, ніж 50%. Такий вид маски ефективний, коли хромосоми кодуються в двійковому алфавіті.

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

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

Розглянемо «Жадібний» оператор кросинговеру. Він може бути реалізований на двох і більше хромосомах, а в межі - на всій популяції. Наведемо алгоритм «жодного» оператора кросинговеру на прикладі знаходження шляху з мінімальною або максимальною вартістю на графі:

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

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

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

4. Процес триває аналогічно, до побудови хромосоми «нащадок». Якщо в процесі реалізації виникає цикл або глухий кут, то вибираються нерозглянуті гени з кращим значенням цільової функції.

Наприклад, нехай задано граф G = (X, U), X = {a, b, c, d, e} у вигляді матриці. Побудуємо популяцію Р, що складається з трьох батьківських хромосом Р = {P1, P2, P3}, де P1 : abcde; P2: Bdeca; P3 : Ebadc. Елементи визначають вартість шляху між будь-якими двома вершинами графа, а кожен ген в хромосомі кодується номером вершини графа:

Відповідно до алгоритму виберемо точку «жодного» оператора кросинговеру між генами b и c в хромосомі P1. Тепер вибір (b - c) даетзначеніе цільової функції, рівне 4 (див. матрицю), вибір (b - d) (В хромосомі P2) Визначає цільову функцію, зі значенням 3, а вибір (b - a) (В хромосомі P3) Визначає цільову функцію, рівну 15. При мінімізації цільової функції виберемо шлях (b - d). Продовжуючи, отримаємо шлях реалізації «жодного» оператора кросинговеру (рис.). Отже, хромосома нащадка Р ?: bdcae має сумарну цільову функцію, рівну 18: 3 + 1 + 6 + 8 = 18, а цільова функція батьків для P1 дорівнює 15 + 4 + 1 + 9 = 29, для P2 дорівнює 3 + 9 + 10 + 6 = 28 і для P3 дорівнює 2 + 15 + 7 + 1 = 25.

Мал. Приклад реалізації «жодного» оператора кросинговеру

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

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

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

5.8. Існують і інші методи вибору пар хромосом для схрещування. Наприклад, «близьке» спорідненість, «далеке» спорідненість, вибір на основі коду Грея і т.д.

«Близька спорідненість». Тут ймовірність вибору хромосом, які підлягають схрещуванню, запишеться так:

- Для першої хромосоми Рi

 , ()

де  - Ймовірність вибору хромосоми на основі близької спорідненості;

- Для другої хромосоми Pj ймовірність  задається користувачем.

потім обчислюється Хеммінгово відстань dist (Pi, Pj) Між обраними хромосомами поточної популяції. Розглянемо, наприклад, дві, кожна з яких задається конкретними значеннями семи змінних: х1, х2, х3, х4, х5, х6, х7; нехай в першому випадку ними будуть 0, 1, 0, 1, 1, 0, 1, а в другому 1, 1, 0, 1, 0, 0, 0. Запишемо дані сукупності значень х1, х2, ..., Х7 одну під інший:

х1 х2 х3 х4 х5 х6 х7
 -1

Обчислимо різницю між кожним елементом першого рядка і відповідним елементом другого рядка. Запишемо результати під другим рядком. Тепер обчислимо суму «абсолютних значень» отриманих результатів. Ця сума дорівнює 3. Кажуть, що відстань Хеммінга між зазначеними вище точками (або величинами) [0, 1, 0, 1, 1, 0, 1] і [1, 1, 0, 1, 0, 0, 0] одно 3:

?-1? + ?1? + ?1? = 1 + 1 + 1 = 3

У загальному випадку розглянемо дві хромосоми ( ,  , ...,  ) І (х1, х2, ..., Хn); узагальненим відстанню Хеммінга між цими двома хромосомами називається скаляр

p = |  - х1| + |  - х2| + ... + |  - хn |.

Хромосоми рекомендуються для схрещування, якщо хеммінгово відстань між ними dist (Pi, Pj)> R, де R - радіус схрещування, що задається особою, яка приймає рішення, або визначається як найближче менше ціле від різниці значень цільових функцій ЦФ (Pi) - ЦФ (Pj), Поділений на два.

ймовірності и  зростають на кінцевих стадіях роботи оператора кросинговеру.

«Дальнє» спорідненість визначається умовою

,

де  - Ймовірність вибору хромосом при «далекому спорідненість на початкових стадіях роботи генетичних алгоритмів, з урахуванням особливостей обчислюється для першої і другої хромосоми.

хромосоми Pi і Pj підлягають схрещування, якщо хеммінгово відстань між ними dist (Pi, Pj)> R. Імовірність и  зменшується на кінцевих стадіях пошуку оптимального рішення.

код Грея - Це двійковий код, послідовні значення якого відрізняються тільки одним двійковим розрядом. Код Грея може використовуватися для хромосом, представлених в двійковому вигляді. наприклад:

0 - 0000

1 - 0001

2 - 0011

3 - 0010

4 - 0110

5 - 0111 і т.д.

Таке кодування альтернативних рішень дозволяє вирішувати питання «збовтування» популяції; воно ефективно на початкових стадіях генетичного алгоритму.

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

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

Оператор мутації зазвичай складається з двох етапів:

1. У хромосомі А = (a1, a2, a3, ..., AL-2, aL-1, aL) визначаються випадковим чином дві позиції (наприклад, a2 и aL-1).

2. Гени, що відповідають обраним позиціях, переставляються, і формується нова хромосома А ? = (a1, aL-1, a3, ..., AL-2, a2 , aL).

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

тут  - Батьківська хромосома,  - Хромосома-нащадок після застосування одноточечного оператора мутації.

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

тут  - Батьківська хромосома,  - Хромосома-нащадок після застосування двухточечного оператора мутації.

Розвитком двухточечного оператора мутації є многоточечний (або n-точковий) оператор мутації. В цьому випадку відбувається послідовний обмін генів, розташованих правіше точок розрізу один з одним в порядку їх розташування. Ген, розташований правіше останньої точки розрізу, переходить на місце першого, наприклад:

Будівельні блоки - Це тісно пов'язані між собою гени (частини альтернативних рішень), які небажано змінювати при виконанні генетичних операторів. З будівельних блоків (як із цеглинок при побудові будинку) можна створювати альтернативні оптимальні або Квазіоптимальний рішення.

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

При непарному числі точок нащадок виходить після обміну ділянками хромосом, розташованих між парними точками розрізу, наприклад:

Часто використовують оператори мутації, що використовують знання про розв'язуваної задачі. Реалізація таких операторів полягає в перестановці місцями будь-яких обраних генів в хромосомі, причому точка або точки мутації визначаються не випадково, а цілеспрямовано.

У позиційному операторі мутації дві точки розрізу вибираються випадково, а потім ген, що відповідає другій точці мутації, розміщується в позицію перед геном, відповідним першій точці, наприклад:

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

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

1. Хромосома В = (b1, b2, ..., BL,) вибираються випадковим чином з поточної популяції.

2. Два числа и  вибираються випадковим чином з безлічі {0,1,2, ..., L + 1}, причому вважається, що y1= Min { ,  } І y2= Max { ,  }.

3. Нова хромосома формується з В шляхом інверсії сегмента, який лежить праворуч від позиції y1 і зліва від позиції y2 в хромосомі В. Тоді після застосування оператора інверсії отримуємо:

В = (b1, ..., By1, by2-1, by2-2, ..., By1 + 1, by2, ..., BL).

Для одноточечного оператора інверсії запишемо

тут Р2 - Батьківська хромосома,  - Хромосома-нащадок після застосування оператора інверсії.

Наприклад, для двухточечного оператора інверсії отримаємо

тут  - Батьківська хромосома,  - Хромосома-нащадок після застосування двухточечного оператора інверсії.

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

5.11. Розглянемо оператор транслокации. оператор транслокации - Це мовна конструкція, що дозволяє на основі схрещування і інвертування з пари батьківських хромосом (або їх частин) створювати дві хромосоми нащадків. Іншими словами, він являє собою комбінацію операторів кросинговеру і інверсії. У процесі його реалізації випадковим чином проводиться один розріз в кожній хромосомі. При формуванні нащадка  береться ліва частина до розриву з батьків Р1 і інверсія правій частині до розриву з Р2. При створенні  береться ліва частина Р2 і інверсія правій частині Р1, Наприклад:

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

5.12. оператор транспозиції - Мовна конструкція, що дозволяє на основі перетворення і інвертування виділяється частини батьківської хромосоми створювати хромосому нащадка. наприклад:

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

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

Наведемо один їх прикладів його реалізації. Відзначимо, що оператор сегрегації, як правило, реалізується на деякій наборі хромосом. Нехай є популяція Р, Що складається з чотирьох батьківських:

Р = {P1, P2, P3, P4} P1 : (12345678); P2 : (24316587); P3 : (31425768); P4 : (87654321).

У кожній хромосомі виділимо будівельні блоки. Виділимо по два будівельних блоку: в P1 - 23 і 67, в P2 - 1 і 4, в P3 - 768 і 425 і в P4 - 54 і 87. Тоді, наприклад, нащадок  можна сформувати, взявши перші будівельні блоки з кожної батьківської хромосоми популяції. Так, варіант  буде представлений послідовністю (23176854) і є реальним вирішенням, а варіант  (67442587) є нереальним (неприпустимим). Очевидно, цей можна реалізувати різними способами в залежності від вибірки будівельних блоків або генів з хромосом.

5.14. опишемо оператор видалення. Це мовна конструкція, що дозволяє на основі видалення будівельних блоків з хромосом батьків (або їх частин) створювати хромосоми нащадків.

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

5.15.опишемо оператор вставки. Це мовна конструкція, що дозволяє на основі вставки будівельних блоків в хромосоми батьків створювати хромосоми нащадків.

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

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

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

Чисельність нової популяції

= + + + + + + + + ,

де

 - Чисельність нової популяції,

 - Чисельність популяції на попередньому кроці (поколінні) t,

, , , , , , ,  - Нащадки, отримані в результаті застосування операторів кросинговеру, мутації, інверсії, транслокації, транспозиції, сегрегації, видалення, вставки.

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

1. Елітна схема редукції. До групи видалення з популяції включаються такі хромосоми, як  і тільки ті нащадки, для яких виконується умова:

(  ) (  ) (ЦФ (  )> ЦФ (  )), Де k = ,

де  - Нащадки (рішення), отримані після застосування генетичного оператора (ГО).

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

· випадковий вибір,

· Вибір «кращих» і «гірших»,

· «Близьке» спорідненість,

· «Дальне» спорідненість,

· На основі коду Грея для бінарних хромосом,

· На основі відстані Хеммінга,

· На основі «турніру».

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

За аналогією з оператором репродукції відомі наступні модифікації оператора редукції:

1) равновероятностних відбір з ймовірністю

 (S) = .

де N - розмір популяції;

2) пропорційний відбір з ймовірністю

 (S) = .

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

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

Часто в генетичних алгоритмах задається параметр W (P), Який керує цим процесом. так, Np(1 W (P)) елементів в популяції Р, Обраних випадково, могум «вижити» в наступній генерації. тут Np - Розмір популяції. величина W (P) = 0 означає, що ціла попередня популяція переміщається в нову популяцію в кожній генерації. При подальшій реалізації алгоритму кращі або відібрані елементи з батьків і нащадків будуть вибиратися для формування нової популяції.

В інженерних задачах використовуються різні механізми і моделі цього процесу. Наведемо кілька з них:

· М1 - витіснення (crowding factor). Цей механізм визначає спосіб і порядок заміни батьківських хромосом з генерації t хромосомами нащадками після генерації t + 1. Механізм реалізований таким чином, що прагне видаляти «схожі» хромосоми з популяції і залишати відрізняються.

· М2 - поділ (sharing). Цей механізм вводить залежність значення цільової функції хромосоми від їх розподілу в популяції і пошуковому просторі. Це дозволяє копіям батьківських хромосом або близьких до них не з'являтися в популяції.

· М3 - введення ідентифікаторів (tagging). Спеціальним хромосомами присвоюються мітки. Оператори генетичних алгоритмів застосовуються тільки до поміченим хромосомами.

Відзначимо, що оператор редукції є окремим випадком оператора рекомбінації.

5.18. Важливим поняттям при реалізації генетичних операторів є ймовірність, яка визначає, який відсоток загального числа генів в популяції змінюється кожної генерації. Для оптимізаційних задач ймовірність оператора кросинговеру зазвичай приймають в межах (0,6?0,99); ймовірність оператора мутації - 0,6; інверсії - (0,1?0,5); транслокации - (0,1?0,5); транспозиції - (0,1?0,5); сегрегації - (0,6?0,99); видалення - (0,6?0,99); вставки - (0,6?0,99).

література

1. 1.Рутковская Д. І др.Нейронние мережі, генетичні алгоритми та нечіткі системи: Пер. з пол. І.Д. Рудинского. М.: Гаряча лінія-Телеком, 2004.-452с.

2. Романов В.П. Інтелектуальні інформаційні системи в економіці: Учеб. посібник / В.П. Романов .; Під ред. д.е.н., проф. Н.П. Тіхомірова.-М .: Видавництво Іспит, 2003.-496 с.

3. Корнєєв В.В. та ін. Бази даних. Інтелектуальна обробка інформації. - М.: "Нолидж", 2000. - 352 с www / Know ledge. ru

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетичні алгоритми / Под ред. В.М. Курейчіка.- 2-е изд. испр. і доп.-М.: ФИЗМАТЛИТ. 2006-320 с.




Попередня   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   Наступна

Засоби вилучення нової інформації | розділ 9 | Основні терміни та визначення | запит Відповідь | Системи обробки зв'язкових текстів | Компонент розуміння висловлювання компонент генерації висловлювання | розділ 10 | Основи теорії генетичних алгоритмів | Приклади розв'язання задач | Рішення завдання комівояжера |

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