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

1. 2.2. Завдання про покриття Задано безліч елементів і безліч підмножин цієї множини . Необхідно...
2. 2.3.1. Упорядковане представлення.

2.2. Завдання про покриття

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

Очевидно, тут рішення можна також представити двійковим вектором

, де

, Якщо підмножина входить в покриття;

, якщо не входить в покриття;

і при цьому

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

2.3. завдання комівояжера

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

Відстані між містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

завдання комівояжера

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

Тур комівояжера може бути описаний циклічною перестановкою , Причому всі - попарно різні; повторюваний на початку і в кінці номер міста , Показує, що перестановка циклічна. Простором пошуку рішень цього завдання є безліч перестановок міст. Будь-яка проста (одиночна) перестановка міст дає рішення, яке є повним туром з міст. Оптимальним рішенням є перестановка, яка дає мінімальну вартість туру. Очевидно, розмірність простору пошуку для несиметричною завдання дорівнює . Відомо, що ця задача є NP - повної, тобто переборного. Вона має численні практичні додатки, в яких число "міст" може бути досить великим. Наприклад, при виробництві складних деталей завдання свердління отворів може мати сотні і тисячі "міст". При виробництві НВІС виникають завдання (наприклад, щодо внесення домішок в напівпровідник) з числом "міст" близько мільйона. За останні десятиліття розроблено досить багато алгоритмів вирішення цього завдання, що дають субоптимальное рішення. В останнє десятиліття ця задача є базовою для дослідження ГА в області комбінаторної оптимізації.

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

Для вирішення ЗК за допомогою генетичних алгоритмів розроблені спеціальні методи представлення (кодування) рішень і відповідні проблемно-орієнтовані генетичні оператори [ 2 , 3 , 4 ]. В основному використовуються три способи подання туру при вирішенні ЗК з використанням ГА: 1) уявлення порядку; 2) уявлення сусідства; 3) уявлення шляхів. Для кожного з цих уявлень розроблені свої "генетичні" оператори. Оператор мутації відносно легко визначити на цих уявленнях у вигляді одиночної перестановки сусідніх міст в турі. Тому в подальшому ми, в основному, розглянемо оператори кросинговеру.

2.3.1. Упорядковане представлення.

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

Розглянемо його на конкретному прикладі туру = (1-2-4-3-8-5-9-6-7), для якого впорядкований список = (1 2 3 4 5 6 7 8 9). Тоді даний тур при цьому упорядкованому списку представляється наступним списком посилань = (1 + 1 2 1 4 1 3 1 1), який інтерпретується наступним чином. Тут жирним курсивом виділено поточний покажчик в списку .

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

тур = (1), базовий список = (2 3 4 5 6 7 8 9), покажчик = (1 + 1 2 1 4 1 3 1 1).

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

В результаті отримуємо:

поточний тур = (1-2), = (3 4 5 6 7 8 9) і покажчик в e зсувається на третю позицію = (1 + 1 2 1 4 1 3 1 1). Наступний номер списку е дорівнює 2, тому ми беремо і видаляємо 2-й місто з поточного базового списку і додаємо його в тур і пересуваємо покажчик по . маємо:

поточний тур = (1-2-4), = (3 5 6 7 8 9), = (1 + 1 2 1 4 1 3 1 1).

Продовжуючи цей процес, в результаті декодування по даному коду = (1 + 1 2 1 4 1 3 1 1), базового списку = (1 2 3 4 5 6 7 8 9) буде побудований тур = (1-2-4-3-8-5-9-6-7).

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

Наприклад, для батьків

= (1 1 2 1 | 4 1 3 1 1) і = (5 1 5 5 | 5 3 3 2 1),

які відповідають турам

= (1-2-4-3-8-5-9-6-7) і = (5-1-7-8-9-4-6-3-2),

маємо наступних нащадків при схрещуванні

= (1 1 2 1 5 3 3 2 1) і = (5 1 5 5 4 1 3 1 1),

які представляють тури

= (1-2-4-3-9-7-8-6-5) і = (5-1-7-8-6-2-9-3-4).

Очевидно, що часткові тури зліва від точки кросинговеру не змінюються, в той же час часткові тури праворуч від неї розриваються випадковим чином (зберігаючи коректність рішення). На жаль, машинні експерименти за рішенням ЗК на основі цього подання рішень з використанням класичного кросинговеру показують посередні результати [ 4 ].