НОУ ІНТУЇТ | лекція | Генетичні алгоритми для задач комбінаторної оптимізації

1. 2.1. Питання про укладанні рюкзака

Наша команда-партнер Artmisto

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

2.1. Питання про укладанні рюкзака

Це завдання має наступну неформальну просту постановку [ 4 , 5 ]. Є рюкзак об'ємом і різних предметів. кожен предмет має відомий обсяг і вартість . У рюкзак можна покласти ціле число різних предметів. Потрібно упакувати рюкзак так, щоб повна вартість укладених предметів була максимальною, а їх загальний об'єм не перевищував заданий обсяг . Форма предметів тут не враховується.

Формальна постановка задачі: для даної множини ваг , вартостей і обсягу треба знайти бінарний вектор

і при цьому має виконуватися умова:

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

Як фітнес-функції в найпростішому випадку можна взяти

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

Дане завдання відноситься до класу задач з обмеженнями, при вирішенні яких застосовуються такі підходи [ 4 , 5 ]: 1) введення в фітнес-функцію додаткового штрафу; 2) використання алгоритмів "відновлення" некоректних рішень.

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

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

   Тут для всіх трьох випадків .

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

   У цьому випадку в якості фітнес-функції використовується

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

   При цьому використовуються два основних способи вибору об'єкта:

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

   Розглянемо один з можливих варіантів алгоритму декодування, який заснований на кодуванні рішення вектором цілих чисел, так званому "упорядкованому поданні" (ordinal representation), докладно описаному в розділі 3.3.2. Тут кожна хромосома кодується вектором цілих чисел, де -я компонента вектора - є ціле число в діапазоні від 1 до . "Впорядковане уявлення" використовує для посилань (базовий) список предметів . вектор фактично містить покажчики на базовий список . Декодування вектора здійснюється шляхом вибору відповідного предмета з поточного списку і видалення його з базового списку. Наприклад, при базовому списку предметів поточний вектор декодируется в наступну послідовність предметів: 4, 3, 6, 1,2, 5. Першим в рюкзак включається четвертий елемент списку - 4, який усувається з . Далі в рюкзак включається третій елемент з поточного списку . Потім включається 6 - четвертий елемент поточного і т.д. Детальніше опис цього подання і виконання кросинговеру на ньому описано в розділі 2.3.2. В даному методі хромосома може інтерпретуватися як стратегія (порядок) включення предметів в рішення. Відзначимо, що основною перевагою даного кодування хромосоми є те, що на ньому працює одноточковий кроссинговер. Тобто для двох допустимих рішень -батьків кроссинговер породжує також допустиме рішення-нащадок. Оператор мутації при даному поданні виконується шляхом заміни -го гена (целочисленной компоненти вектора) на випадкове ціле число з діапазону .

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

Питання про укладанні рюкзака в різних варіантах має численні практичні додатки. Наприклад, до неї можна звести оптимізацію завантаження транспорту і т.п.