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

 

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

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

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

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

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

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

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

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

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

 

2.1 Етапи генетичного алгоритму

Представимо загальну схему базового генетичного алгоритму [5], як ітераційний процес, що складається з кількох етапів:

1) генерація початкової популяції;

2) створення нащадків:

а) вибір батьківської пари і здійснення схрещування;

б) внесення мутаційних змін у популяцію;

3) відбір і формування нового покоління;

4) якщо не виконується умова зупинки — перехід до п. 2.

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

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

 

2 (ген 1)

5 (ген 2)

4 (ген 3)

3 (ген 4)

6 (ген 5)

1 (ген 6)

 

Рисунок 2.1 - Загальний вигляд однієї хромосоми

 

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

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

Щоб створити кожне наступне покоління з нових хромосом, які носять назву нащадків їх формують методом схрещування (crossover чи crossingover) двох батьківських хромосом поточної популяції, або ж обирають їх випадковим чином – шляхом мутації (mutation) однієї з хромосом. Кожна нова популяція створюється у відповідності до функції fitnessfunction.

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

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

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