Студопедия — ОБҐРУНТУВАННЯ МЕТОДУ РОЗВ’ЯЗАННЯ ЗАДАЧІ КОМІВОЯЖЕРА
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






 

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

Генетичний алгоритм (англ. 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]. На противагу “стандартним” алгоритмам генетичний алгоритм дозволяє відхилятись від вищезазначеної вимоги та дозволяє ефективно знаходити глобальний мінімум.


 







Дата добавления: 2015-09-15; просмотров: 1629. Нарушение авторских прав; Мы поможем в написании вашей работы!



Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

ТРАНСПОРТНАЯ ИММОБИЛИЗАЦИЯ   Под транспортной иммобилизацией понимают мероприятия, направленные на обеспечение покоя в поврежденном участке тела и близлежащих к нему суставах на период перевозки пострадавшего в лечебное учреждение...

Кишечный шов (Ламбера, Альберта, Шмидена, Матешука) Кишечный шов– это способ соединения кишечной стенки. В основе кишечного шва лежит принцип футлярного строения кишечной стенки...

Принципы резекции желудка по типу Бильрот 1, Бильрот 2; операция Гофмейстера-Финстерера. Гастрэктомия Резекция желудка – удаление части желудка: а) дистальная – удаляют 2/3 желудка б) проксимальная – удаляют 95% желудка. Показания...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

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

Машины и механизмы для нарезки овощей В зависимости от назначения овощерезательные машины подразделяются на две группы: машины для нарезки сырых и вареных овощей...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия