Задача коммивояжера и её реализация

          Будь-який мурашиний  алгоритм, незалежно від модифікацій, можна представимо в наступному вигляді

• Поки (умови виходу не виконуются)

1. Створюємо мурах

2. Пошук розв’язку
3. Оновлюємо феромон
4. Додаткові дії {опціонально}

    Тепер розглянемо кожен крок в циклі  більш детально:

    1.Створюємо  мурах

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

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

    2. Пошук розв’язку

    Імовірність переходу з вершини i у вершину j визначається за наступною формулою

      

    Де  - рівень феромону, - евристична відстань, а і - константні параметри.

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

    3. Оновлення феромону

    Рівень  феромона оновлюється за наведеною  формулою

    

    Де  - інтенсивність випаровування, Lk (t) - ціна поточного вирішення для k-ого мурашки, а Q - параметр, що має значення ціни оптимального рішення, тобто - феромон, відкладається k-им мурахою, що використовує ребро (i, j).

    4. Додаткові дії

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

    Якщо  розглядати мурашиний алгоритм для розв’язку задачі комівояжера, то моделювання поведінки мурах пов'язано з розподілом феромонів на стежці - це ребра графа в задачі комівояжера. При цьому вірогідність включення ребра в маршрут окремого мурашки пропорційна кількості феромонів на цьому ребрі, а кількість відкладання феромона пропорційна довжині маршруту. Чим коротше маршрут, тим більше феромона буде відкладено на його ребрах, отже, більша кількість мурашок буде включати його в синтез власних маршрутів. Моделювання такого підходу, що використовує лише додатній зворотний зв'язок, призводить до передчасної збіжності - більшість мурашок рухається по локальним оптимальним маршрутом. Уникнути цього можна, моделюючи від’ємний зворотний зв'язок у вигляді випаровування феромону. При цьому якщо феромон випаровується швидко, то це призводить до втрати пам'яті колонії і втрати хороших рішень, з іншого боку, великий час випаровування може призвести до отримання стійкого локального оптимального рішення.

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

    1. Мурахи мають власну «пам'ять». Оскільки кожне місто може  бути відвідане тільки один  раз, то у кожного мурахи  є список вже відвіданих міст - список заборон. Позначимо через J_i,k список міст, який повинен відвідати мураха k, що знаходиться в місті i.

    2. Мурахи мають «зір» - евристичне  бажання відвідати місто j, якщо мураха знаходиться в місті i. Будемо вважати, що видимість обернено пропорційна відстані між містами

    

    3. Мурахи мають «нюх» - вони можуть  вловлювати слід феромона, який  підтверджує бажання відвідати  місто j з міста i на підставі  досвіду інших мурах. Кількість  феромону на ребрі (i, j) у момент часу t позначимо через

        На цій підставі ми можемо  сформулювати ймовірнісно-пропорційне  правило, що визначає ймовірність  переходу k-ого мурахи з міста  i в місто j:

                                              (1.2) 

    Де  α, β - параметри, що задають ваги слідів феромона. При α = 0 алгоритм перетворюється на жадібний алгоритму (буде обраний найближче місто). Зауважимо, що вибір міста є імовірнісним, правило (1.5.1) лише визначає ширину зони міста j; в загальну зону всіх J_i,k міст кидається випадкове число, яке і визначає вибір мурахи. Правило (1.5.1) не змінюється в ході алгоритму, але в двох різних мурах значення ймовірності переходу будуть відрізнятися, тому що вони мають різний список дозволених міст.

    5. Пройшовши ребро (i, j), мураха відкладає на ньому деяку кількість феромону, яка повинно бути пов'язано з оптимальністю зробленого вибору. Нехай Tk (t) є маршрут, пройдений мурахою k до моменту часу t, Lk (t) - довжина цього маршруту, а Q - параметр, що має значення порядку довжини оптимального шляху. Тоді кількість феромону, що відкладається може бути задана у вигляді

    

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

    

    де  m - кількість мурашок в колонії.

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

    Додаткова модифікація алгоритму може складатися у введенні так званих "елітних" мурашок, які посилюють ребра найкращого маршруту, знайденого з початку роботи алгоритму. Позначимо через T* найкращий поточний маршрут, через L* - його довжину. Тоді якщо в колонії є e елітних мурашок, то ребра маршруту отримають додаткову кількість феромону.

    

    РОЗДІЛ  ІI. СТВОРЕННЯ СЕРЕДОВИЩА ДЛЯ РОЗВ'ЯЗКУ ЗАДАЧІ КОМІВОЯЖЕРА

    2.1 Технічне завдання

          Загальні  відомості

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

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

    Тому  дана проблема на сучасному етапі  розвитку суспільства має не саме останнє по значущості місце. 

Призначення та цілі створення  програми

Основними цілями та призначеннями при розробці даного середовища були:

• програмна реалізація алгоритмів для розв’язку задачі комівояжера;
• графічне представлення роботи алгоритмів.

 

    Вимоги  до системи

    Вимоги  до функціонування програмного  продукту:

    1) Програма повинна дозволяти задавати користувачеві необхідну кількість міст у вигляді матриці відстаней.

    2) Створення нових матрицей відстаней.

    3) Програма повинна мати можливість заданя матриці шляхом відкриття існуючої:

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

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

      4) Мати можливість збереження створених матриць:

          - для збереження пропонується каталог з програмою;

          - заданя ім’я для файлу.

    5) Візуально та зрозуміло представляти результати своєї роботи для

кінцевого користувача 

Вимоги  до ергономіки та технічної  естетики.

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

Вимоги  до транспортабельності  АС.

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

Вимоги  до програмного забезпечення.

Програмний продукт повинен бути сумісним з операційною системою MicrosoftWindows 2000/XP/Vista/7. 

Вимоги  до надійності.

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

Склад робіт по розробці програмного продукту

    Етапи розробки АС:

    Розгляд всіх можливих методів, які дозволять  розв’язати дану задачу. Строк виконання: 1 тиждень.

    Обрання та узгодження із керівником середовища програмування та мови програмування  вищого рівня. Строк виконання: 1 тиждень від початку виконання робіт.

    Програмна реалізація алгоритмів. Строк виконання: 2 тижні від початку виконання робіт.

    Розробка  візуальної частини програмного  продукту та узгодження його із керівником. Строк виконання: 4 тижні від початку  виконання робіт.

    Розробка  та відлагодження програмного продукту. Строк виконання: 2 тижні від початку четвертого етапу розробки АС.

    2.2 Проект програмного  продукту

    Інтерфейс програми складається з одного робочого вікна. Робоча область має такі компоненти:

• головне меню програми складається з «Файл» та «Справка», які в свою чергу мають підпункти:
• «Файл» - «Нова матриця», «Відкрити», «Зберегти»;
• «Справка» - «О програмі»;
• компонент для візуального (графічного) представлення результату роботи алгоритму;
• текстові поля для відображення кінцевої довжини туру та оптимального шляху;
• поля для введення, які реалізують матрицю відстаней для міст;

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

    Запуск  програми: при якомі відбувається створення компоненту Image та задання его розмірів

    procedure TForm1.FormCreate(Sender: TObject);

    begin

      Image1.Picture.Bitmap:=nil;

      Image1.Picture.Bitmap := TBitmap.Create;

      Image1.Picture.Bitmap.Width := Image1.Width;

      Image1.Picture.Bitmap.Height := Image1.Height;

    end;

    Вибір кількості міст: реалізується компонентом ComboBox за допомогою такою процедури

    procedure TForm1.ComboBox1Change(Sender: TObject);

    var

      i,j:byte;

    begin

      for i:=1 to NN do

      begin

        ObjLabel('Label1',i).Visible:=False;

        ObjLabel('Label2',i).Visible:=False;

        for j:=1 to NN do

          ObjEdit('Edit',i,j).Visible:=False;

      end;

      N:=StrToInt(ComboBox1.Text);

      for i:=1 to N do

      begin

        ObjLabel('Label1',i).Visible:=True;

        ObjLabel('Label2',i).Visible:=True;

        for j:=1 to N do

          ObjEdit('Edit',i,j).Visible:=True;

      end;