Ініціалізація

Стандартні генетичні методи починають свою роботу з ініціалізації, тобто формування початкової популяції P₀ – кінцевого набору допустимих рішень задачі:

P₀ = {H₁, H₂, …, H_N},

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

H_j = {h_1j, h_2j, …, h_Lj} – хромосома, що складається з L генів;

min_i ≤ h_ij ≤ max_i, min_i і max_i – мінімальне й максимальне значення i-го параметра в розв'язуваній за допомогою генетичного методу задачі.

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

Найчастіше розмір початкової популяції вибирається в інтервалі 20–100 особин.

Стратегія створення початкової популяціїможе бути різною. Відомі наступні стратегії.

1. Стратегія “ковдри” – вихідна множина містить всі можливі варіанти рішень. Стратегія “ковдри” має наступні недоліки:

– у багатьох випадках неможливо здійснити повний перебір;

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

2. Стратегія “фокусування” – стартова множина рішень включає різновиди одного рішення.

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

Для більшості задач оптимізації неприйнятні стратегії “ковдри” (внаслідок проблематичності повного перебору) і фокусування (відсутня чітка залежність якості рішення від параметрів рішення).

3. Стратегія “дробовика” – генерується досить велика множина рішень. Дана стратегія може бути реалізована одним з трьох способів.

3.1. Рівномірне формування початкової популяції.

3.2. Випадкове формування початкової популяції.

3.3. Комплементарне формування початкової популяції, яке виконується за два кроки.

Крок 1. Сформувати випадковим чином першу половину початкової популяції.

Крок 2. Сформувати другу половину початкової популяції шляхом додавання хромосом, протилежних (одиниці заміняються нулями) хромосомам в першій половині популяції.

Відбір

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

Найпоширенішими є наступні оператори відбору:

– пропорційний відбір (пропорційно-імовірнісний відбір);

– відбір ранжируванням;

– турнірний відбір;

– відбір з використанням порогу.

<== попередня сторінка	\|	наступна сторінка ==>
Завдання цільової функції	\|	Пропорційний відбір

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

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