The ant system applied to the quadratic assignment problem

УДК 519.161

т.н., доцент Зорін Ю.М., студент Жук А.М.

Національний технічний університету України

«Київський політехнічний інститут»

МУРАШИНІ АЛГОРИТМИ В РІШЕННІ

КВАДРАТИЧНОЇ ЗАДАЧІ ПРО ПРИЗНАЧЕННЯ

Abstract

Yuri Zorin, Assoc. Prof., PhD; Andrew Zhuk, student

The ant system applied to the quadratic assignment problem

In recent years there has been growing interest in algorithms inspired by the observation of natural phenomena to define computational procedures which can solve complex problems. In this paper there is introduced a distributed heuristic algorithm which was inspired by the observation of the behavior of ant colonies and is proposed its use for the Quadratic Assignment Problem. Finally the results obtained in solving some classical instances of the problem are compared with those obtained from other evolutionary heuristics to evaluate the quality of the system proposed.

Вступ

Квадратична задача про призначення (quadratic assignment problem, QAP) є однією з фундаментальних задач комбінаторної оптимізації в галузі оптимізації в математиці, відноситься до категорії проблем розміщення об'єктів.

Квадратична задача про призначення порядку n полягає у пошуку найкращого розміщення n об’єктів в n місцях. Вперше вона була сформульована Т’ялінгом Купмансом в 1957 році і з тих пір було визнано, що дана модель описує безліч різних реальних ситуацій; дана задача використовувалася в плануванні та будівництві університетських кампусів, в розміщенні відділів лікарень, мінімізації загальної довжини провідників на електронних схемах і т.д.

Постановка задачі

Математично задача виражається у трьох матрицях розмірністю n x n.

D=[d_ih] – матриця відстаней (між місцем i та місцем h);

F=[f_jk] – матриця потоку (між об’єктом j та об’єктом k);

C=[c_ij] – матриця вартості призначень (об’єкту j на місцем i).

Зазвичай матриці DтаFє цілочисельними та симетричними відносно головної діагоналі, а матриця Сігнорується, оскільки інформація в ній не вносить значних змін в складність алгоритму.

Назвемо перестановку P: i -> p(i) – конкретне призначення об’єкту j = p(i) місцю i (i = 1, ... ,n).

Вартість передачі даних (чи будь-чого іншого, в залежності від конкретної задачі) між об’єктами можна виразити як добуток відстані між місцями, на яких розміщені об’єкти, та потоком між двома об’єктами d_ih·f_p(i)p(h).

Суть задачі складається в тому, щоб знайти таку перестановку, при якій функція ціни буде мінімальна:

Для того щоб показати квадратичну природу даної задачі, переформулюємо її наступним чином: потрібно знайти таку матрицю перестановок Хрозмірністю п х п, елементи якої x_ij дорівнюють 1, якщо об’єкт j призначений на локацію i:

Елементи x_ij мають наступні обмеження:

Тобто, матриця має лише одну одиницю в кожному рядку та стовбці.

Побудова алгоритму

Для розв’язку поставленої задачі пропонується алгоритм Ant System (AS). Він використовує деякі характеристики поведінки, які спостерігалися в реальних умовах у колонії мурах. Таким чином, даний алгоритм визначає поняття «штучної мурахи».

Кожний штучний мураха є об’єктом із наступними властивостями:

· Коли мураха робить рішення призначити об’єкту j місце і, він залишає речовину, яка називається слід,(аналог феромонів) на зв’язку (i,j);

· Мураха вибирає яке місце призначити об’єкту з імовірністю, що є функцією від «потенційної доброякісності» та від щільності залишеного сліду на зв’язку (i,j);

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

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

Розглянемо спосіб обчислення потенційної доброякісності зв’язку (i,j), а також спосіб ініціалізації призначень (коли ще немає сліду). Дано дві матриці. Матриця відстаней Dта матриця потоку F. Введемо вектор D, в який запишемо суму в рядках матриці D, та вектор F – сума в рядках матриці F. Перший вектор називається вектором потенціалу відстані, а другий – вектором потенціалу потоку. Вектор потенціалу відстані визначає суму відстаней між кожним окремим місцем та всіма іншими, а вектор потенціалу потоку визначає загальний потік між кожним конкретним об’єктом та всіма іншими. Чим меншим є число d_i (потенціал відстані) в і-го місця, тим воно є більш барицентричним в мережі. Щодо потоку, то навпаки, чим більший значення f_j (потенціал потоку) об’єкту j, тим більш важливим є даний об’єкти в системі обміну потоків.

З двох векторів D та F потрібно отримати матрицю А, яка називається матрицею зв’язків

в якій елементи a_ij є добутком d_i·f_j.

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

Введемо таке поняття, як інтенсивність шляху t_ij(t+1), що належить зв’язку (i,j):

Де r - це коефіцієнт, що визначає постійність сліду (1 - r визначає випаровування), а Dt_ij^k – це густина сліду, залишена на зв’язку (i,j) k-м мурахою. В якості початкового значення t_ij(0) можна задати меле невід’ємне довільне значення.

Також введемо таке поняття, як бажаність зв’язку - h_ij. Запишемо її як одиницю, поділену на елементи матриці зв’язків: h_ij=1/a_ij.
Тепер можна записати функцію імовірності для кожної пари (i,j). Функція імовірності p_ij^k(t) показує імовірність вибору k-м мурахою зв’язку (i,j):

Параметри a та ß дозволяють визначати відносну важливість інтенсивності шляху перед бажаністю зв’язку. Таким чином імовірність є компромісом між бажаністю зв’язку та інтенсивністю шляху.

Експериментальні результати

В таблиці подані наступні дані:

1. Найкращий відомий результат;

2. Середній результат 500 різних розв’язків;

3. Найкращий результат, що вдалося досягнути з використанням даного алгоритму.

Висновки

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

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

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

Література

1. Vittorio Maniezzo, Alberto Colorni, Marco Dorigo, - Technical Report 94/28, IRIDIA, Universite Libre de Bruxelles, Bruxelles, Belgium

2. C.G.E.Boender, A.H.G. Rinnooy Kan, G.T. Timmer and L. Stougie. A Stochastic Method for Global Optimization, Mathematical Programming, 22, 125–140, 1982.