1. Основні поняття теорії графів для задачі комівояжера

Нехай G – неорієнтований граф. Геометрично граф можна представити як набір вершин (точок), певні пари яких з'єднані лініями. Наприклад, мережа доріг, що з'єднують міста Е1, Е2, Е3, Е4, Е5, можна представити у вигляді графа таким чином. Міста позначені крапками (вершинами), а дороги - неорієнтованими лініями (рис. 1.1).

Рисунок 1.1 – Неорієнтований граф

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

Рисунок 1.2 – Властивість зображення графа

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

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

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

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

Граф називається зв'язним, якщо між парою його вершин існує така послідовність елементів (дуг або ребер, або ж і дуг, і ребер), що будь-які сусідні елементи в цій послідовності мають загальну вершину. Очевидно, що будь-який сильно зв'язний граф є зв'язним. Зв'язний неорієнтований граф називається деревом, якщо він не має циклів. У дереві будь-які дві вершини зв'язані єдиним ланцюгом [6].

1.2 Формулювання і деякі властивості рішень задачі комівояжера

Комівояжер (подорожуючий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2, 1, 3 .. n і повернутися в перше місто. Відстані між містами відомі.

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

Щоб привести завдання до наукового формулювання, введемо деякі терміни. Міста пронумеровані числами jТ=(1,2,3..n). Тур комівояжера може бути описаний циклічною перестановкою t = (j₁, j₂, ..,j_n, j₁), слід зауважити, що всі j₁..j_n - різні номера міст; повторюваний на початку і в кінці j₁, показує, що перестановка зациклена. Відстані між парами вершин С_ij утворюють матрицю С.

Завдання полягає в тому, щоб знайти такий тур t:

(1.1)

.

Щодо математичного формулювання задачі комівояжера доречно зробити декілька зауважень.

1) У постановці С_ij означали відстані, тому вони повинні бути невід'ємними, тобто для всіх jТ [6]:

С_ij0; C_jj=∞. (1.2)

Остання рівність означає заборону петель в турі, тобто для всіх i, j:

С_ij=С_ji (1.3)

і задовольняти нерівність трикутника, тобто для всіх:

С_ij+С_jkC_ik. (1.4)

У математичній постановці йдеться про довільну матрицю. Зроблено це тому, що існує багато прикладних задач, які описуються основною моделлю, але всі умови (1.2) – (1.4) не задовольняють. Особливо часто порушується умова (1.3) (наприклад, якщо С_ij - не відстань, а плата за проїзд: часто в одну сторону квиток коштує певну ціну, а назад - інакшу). Тому будемо розрізняти два варіанти задачі комівояжера: симетричну задачу, коли умова (1.3) виконується, і несиметричну - в іншому випадку. Умови (1.2) – (1.4) за замовчуванням будемо вважати такими що виконуються.

2) У несиметричній задачі комівояжера всі тури t = (j₁, j₂, .., j_n, j₁) і t '= (j₁, j_n, .., j₂, j₁) мають різну довжину і повинні враховуватися обидва. Різних турів очевидно (n-1)! [6].

Зафіксуємо на першому та останньому місці в циклічній перестановці номер j₁, а номера, що залишилися, їх кількість рівна n-1 переставимо усіма (n-1)! можливими способами. В результаті отримаємо всі несиметричні тури. Симетричних турів буде у два рази менше, тому що кожен зарахований двічі: як t і як t'. Можна представити, що С складається тільки з одиниць і нулів. Тоді С можна інтерпретувати, як граф, де проведено ребро (i, j), якщо С_ij = 0 і ребро відсутнє, якщо С_ij = 1. Таким чином, якщо існує тур довжиною 0, то він пройде по циклу, який включає всі вершини по одному разу. Такий цикл носить назву гамільтонового циклу. Незамкнутий гамільтонів цикл називається гамільтоновим ланцюгом (гамільтонів шлях).

У термінах теорії графів симетричну задачу комівояжера можна сформулювати так: “Дано повну мережу з n вершинами, довжина ребра (i, j) = С_ij. Знайти гамільтонів цикл мінімальної довжини. У несиметричній задачі про комівояжера замість “цикл” слід вживати слово “контур”, а замість “ребра”–“дуги” або “стрілки”.

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

1.3 Постановка задачі комівояжера як завдання на графі

Формулювання задачі. Є деяка множина міст А={a₁,…,a_i,…,a_n}. Відстань між містами i та j – ρ(а_i, a_j). П – множина перестановок елементів А, перестановка, отже

, (1.5)

де

, . (1.6)

Якщо містам поставити у відповідність вершини графа, а дорогам що їх з’єднують – дуги, то в термінах теорії графів задача полягає у визначенні гамільтонового контуру мінімальної довжини (рис. 1.3).

Гамільтоновим контуром називається шлях, що проходить через усі вершини графа, у якого початкова вершина збігається з кінцевою. Тут під довжиною контуру розуміють не кількість дуг, що входять в контур, а суму їх довжин. Довжина відповідної дороги - вага ребра. Граф повинен бути повним, тобто в ньому повинні бути всі можливі ребра. Якщо ж граф не є повним, то його можна доповнити відсутніми ребрами з вагою рівною ∞ [6].

Рисунок 1.3 – Графічна інтерпретація розв’язку задачі комівояжера

1.4 Аналіз даних для задачі комівояжера

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

Вхідні дані:

• кількість міст, які розглядаються при розв’язанні задачі;

• вартість шляху між кожними двома містами, які мають між собою сполучення;

• кількість ітерацій на протязі яких буде здійснюватись пошук оптимального шляху.

Щодо кількості міст, які повинні розглядатися при розв’язанні поставленої задачі, то тут слід зауважити, що генетичний алгоритм, який буде застосований при розв’язані задачі про комівояжера найбільш ефективний коли кількість міст, які повинен відвідати комівояжер перевищує, принаймні, 100. Проте в даному курсовому проекті будемо розглядати варіанти задач в яких дана кількість становить кілька десятків – цей фактор зумовлений певними програмними обмеженнями, які будуть зауважені в наступних розділах.

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

Кількість ітерацій – один із основних показників, який характеризує точність остаточного результату. Загальновідома істина: “Чим більша кількість ітерацій – тим вища ефективність”. Тобто якщо кількість ітерацій буде прямувати до безкінечності – то похибка результату буде прямувати до нуля. В курсовому проекті обмежимось кількома сотнями ітерацій, що ефективно для декількох десятків міст.

Вихідні дані:

• вартість оптимального шляху;

• оптимальний шлях.

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

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

Таким чином, пошук розв’язку задачі про комівояжера в курсовому проектуванні здійснюється при використанні генетичного алгоритму, що повністю відповідає темі курсового проекту. Слід зауважити про ефективність даного алгоритму для розв’язання задач такого типу [5]. Саме за допомогою генетичного алгоритму в повній мірі буде знайдено ефективний розв’язок задачі, який не завжди можна знайти за допомогою стандартних алгоритмів, які використовуються під час розв’язання задачі про комівояжера. Серед таких методів є: метод гілок та меж [4], метод оціночної функції [2] та інші.

2 ОБҐРУНТУВАННЯ МЕТОДУ РОЗВ’ЯЗАННЯ ЗАДАЧІ КОМІВОЯЖЕРА

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

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

Особливістю генетичного алгоритму є акцент на використанні оператора "схрещення", який виконує операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі. "Батьком-засновником" генетичних алгоритмів вважається Джон Голланд (англ. John Holland), книга якого "Адаптація в природних і штучних системах" (англ. Adaptationin Naturaland Artificial Systems) є фундаментальною в цій сфері досліджень [7].

Задача кодується таким чином, щоб її вирішення могло бути представлено у вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується "генетичні оператори" (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation), створюючи таким чином наступне покоління осіб.

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

• знаходження глобального, або надоптимального вирішення;

• вичерпання числа поколінь, що надані на еволюцію;

• вичерпання часу, наданого на еволюцію.

Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих просторах пошуку.