1.5. Фітнес-функція

Наше деловое партнерство www.banwar.org

Як видно з основної блок-схеми ГА на рис.1.1 , Кожна особина популяції (потенційне рішення проблеми) оцінюється шляхом обчислення значення фітнес-функції. Слід зазначити, що в загальному випадку цільова функція (ЦФ) і фітнес-функція можуть відрізнятися. Цільова функція призначена для оцінки характеристик особи щодо кінцевої мети (наприклад, екстремумів). Фітнес-функція призначена, перш за все, для відбору особин для подальшої репродукції і тут важливі характеристики якості однієї особини щодо інших особин. Після декодування хромосоми, де виконується перетворення "генотип фенотип "(наприклад, двійковий код перетвориться в дійсне число), отримане значення далі використовується як аргумент для фітнес-функції. Далі для кожної особини популяції обчислюються значення фітнес-функції, які ранжирують ці особини відносно один одного в сенсі перспективності отримання з них хорошого рішення.

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

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

Розглянуті методи не будують неприпустимих рішень. Але це не завжди дає хороші результати. Наприклад, в тому випадку, коли оптимальні рішення лежать на кордоні допустимої області, зазначені методи можуть давати неоптимальні рішення. Одним з можливих варіантів подолання цієї проблеми є виконання процедури відновлення тільки для деякого підмножини рішень (наприклад, 10% особин).

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

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

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

В цілому на вибір (побудова) фітнес-функції впливають такі чинники:

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

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

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

Мал.1.10.

Схема взаємодії об'єктної моделі з ГА.