Оператори схрещування

При n-точковому схрещуванні:

1. Випадково обираються n точок розриву, що приводить до розбиття вихідних векторів на n + 1 частин різної довжини.

2. Обмінюються у вихідних хромосомах ділянки з парними номерами, а ділянки з непарними залишаються без змін:

n-точкове схрещування може застосовуватися для бінарних, векторних і гомологічних числових хромосом.

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

1. Випадковим чином визначається точка в середині хромосоми. Ця точка називається точкою розриву (точкою схрещування, crossover point).

2. В обраній точці обидві хромосоми діляться на дві частини й обмінюються ними. У результаті утворюються два нащадки.

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

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

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

Однорідне схрещування (uniform crossover) генерує нащадка шляхом випадкової передачі йому генетичної інформації від батьків. Генерація нащадка виконується в такий спосіб.

Крок 1. Встановити лічильник бітів (генів) нащадка: j = 1.

Крок 2. Визначити хромосому з батьківської пари, що передасть значення свого j-го гена нащадкові: n = round(rand[0;1]), де rand[0;1] – випадково згенероване число в інтервалі [0;1]; round(А) – округлене значення числа А.

Крок 3. Виконати: h_j_п = h_jn, де h_j_п – значення j-го гена нащадка, h_jn – значення j-го гена n-го батька.

Крок 4. Виконати: j = j + 1.

Крок 5. Якщо j > L, де L – довжина хромосоми, тоді виконати перехід на крок 6. У противному випадку перейти на крок 2.

Крок 6. Кінець.

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

Крок 1. Випадковим чином задається маска схрещування, що представляє собою рядок з нулів та одиниць, довжини, що дорівнює довжині хромосом.

Крок 2. Формування першого нащадка.

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

Крок 3. Формування другого нащадка.

Якщо першого батька вважати другим, а другого – першим, то аналогічно кроку 2 можна одержати другого нащадка.

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

При порівняльному схрещуванні в хромосомах батьків порівнюються всі біти. Якщо на однакових позиціях обох батьків знаходяться однакові біти (0 і 0 або 1 і 1), то нащадкам присвоюються ті ж значення відповідних бітів. Якщо на однакових позиціях батьків розташовані гени із різними значеннями, тоді значення відповідних генів нащадків визначають за допомогою генератору випадкових чисел.

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

Нехай H₁ і H₂ – це два індивідууми в популяції, тобто дійсні вектори, від яких залежить цільова функція. Тоді нащадок H_п обчислюється за формулою H_п = H₁ + k ∙ (H₁ – H₂), де k – це деякий дійсний коефіцієнт (який може залежати від ||H₁ – H₂|| – відстані між векторами). У цій моделі мутація – це додавання до індивідуума випадкового вектора малої довжини. Якщо вихідна функція неперервна, то ця модель працює добре, а якщо вона ще й гладка, те – відмінно.

При діагональному схрещуванні для схрещування R батьків випадковим чином вибирається (R – 1) однакових точок схрещування в кожному з них. R нащадків отримують шляхом комбінування відповідних елементів батьків по діагоналі.

Крок 1. Вибрати випадковим чином R батьківських хромосом для схрещування.

Крок 2. Вибрати випадковим чином (R – 1) точок схрещування в хромосомах, розділивши тим самим кожну з них на R сегментів.

Крок 3. Встановити: r = 1.

Крок 4. Сформувати r-го нащадка.

Крок 4.1 Встановити: k = 1.

Крок 4.2. Сформувати k-ий сегмент r-го нащадка, взявши g-ий сегмент із k-ої хромосоми-батька, де

Крок 4.3. Виконати: k = k + 1.

Крок 4.4. Якщо k £ R, виконати перехід до кроку 4.2.

Крок 5. Виконати: r = r + 1.

Крок 6. Якщо r £ R, виконати перехід до кроку 4.

Крок 7. Кінець.

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

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Вибір батьківської пари	\|	Мутація

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.024 сек.