Реалізація програми, що реалізує розв’язання задачі комівояжера за допомогою генетичного алгоритму

 

4.1 Проектування алгоритму програмного модуля

Схему генетичного алгоритму схематично можна представити таким чином:

1. Згенерувати випадковим чином набір початкових рішень, який називається популяцією, розміру P. Популяція є множиною бітових рядків для генетичного алгоритму і множиною символьних рядків для еволюційних алгоритмів. Кожен рядок представлений у закодованому вигляді одним з можливих рішень задачі (в загальному випадку далеко не оптимальним) і називається хромосомою. Хромосоми еволюціонують протягом множини ітерацій, які носять назву поколінь (або генерацій).

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

3. Виконати операцію селекції. Нова генерація формується шляхом вибору деяких батьків і нащадків згідно значенням функції пристосованості і знищення інших для залишення постійним розміру популяції.

4. Виконати операцію схрещування.

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

6. Якщо критерії зупинки не досягнуто, перейти до кроку 2, інакше закінчити роботу.

Загальна схема генетичного алгоритму наведена на рисунку 4.1 [7].

 

Рисунок 4.1 – Схема генетичного алгоритму

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

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

Отже алгоритм роботи програми наступний:

1. Генерація матриці вартостей проїзду між містами.

2. Отримання кількості ітерацій роботи програми n.

3. Генерація початкової популяції турів.

4. Визначення вартостей турів.

5. Сортування турів по вартості.

6. Схрещування.

7. Сортування турів по вартості.

8. Мутація.

9. Сортування турів по вартості.

10. Додавання до лічильника одиниці k = k + 1.

11. Перевірка лічильника; якщо k = n – п.6, інакше п.12.

12. Виведення результату.

 

4.2 Розробка програми розв'язку задачі комівояжера

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

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

Наведемо приклади основних функцій, які реалізовані в даному програмному модулі:

 

Рисунок 4.2 – Схема генетичного алгоритму

- функція, яка генерує матрицю вартостей проїзду між містами. При цьому враховується, що вартість переїзду з міста 1 в місто 2 дорівнює вартості переїзду з міста 2 в місто 1;

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

- функція, яка виконує випадкову зміну випадкової кількості генів в заданій кількості хромосом початкової популяції;

- функція, що виконує схрещування двох випадково вибраних хромосом у випадковій точці. Принцип роботи функції простий: нова хромосома формується до

точки розриву з елементів батьківської хромосоми 1, а після з елементів батьківської хромосоми 2. Інша дочірня хромосома формується аналогічним чином;

- функція перевірки хромосом на можливість схрещування у випадковій точці. Дві випадкові хромосоми до та після точки розриву можуть містити однакові елементи, що недопустимо при формуванні туру (кожне місто слід відвідати лише один раз).

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