Застосування генетичних алгоритмів для вирішення задачі комівояжера.. Методичні вказівки до лабораторної роботи з Системи штучного інтелекту. Робота № 400353

Перехід до торгівельного партнера Binance

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

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Електронні обчислювальні машини

Інформація про роботу

Рік:

2003

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

Системи штучного інтелекту

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Застосування генетичних алгоритмів для вирішення задачі комівояжера Методичні вказівки до лабораторної роботи № 3 з курсу: “Системи штучного інтелекту” для студентів Затверджено на засіданні кафедри “Електронних обчислювальних машин” Протокол № Від 2003 р. Львів 2003 Застосування генетичних алгоритмів для вирішення задачі комівояжера. Методичні вказівки до лабораторної роботи № 3 з курсу: “Системи штучного інтелекту” для студентів , 12 с. Укладач: Ємець В.Ф., професор, д.т.н. Сокіл В.М., асистент Юрчак І.Ю, доцент, к.т.н. Відповідальний за випуск: Кремінь В.Т., ст. викладач кафедри ЕОМ Рецензенти: Березко Л.О., доцент кафедри ЕОМ, к.т.н. Каркульовський В.І., доцент кафедри АСУ, к.т.н. 1. Мета роботи Створення програми, на основі генетичних алгоритмів для вирішення задачі комівояжера. 2. Теоретичні відомості В природі існує багато процесів, які шукають стабільні стани. Такі процеси можуть бути трактовані як природні оптимізаційні процеси. В останні тридцять років зроблено декілька проб, для розвитку оптимізаційних алгоритмів, що імітують природні оптимізаційні алгоритми. Такі спроби найефективніше втілені у наступних методах: Алгоритм відпалу металу (Simulated Annealling), що базується на процесі відпалу, запозичений з металургії Штучні нейронні мережі, що базуються на процесах, запозичених з роботи нервових клітин Еволюційні алгоритми, що базуються на біологічних еволюційних процесах Алгоритми, що моделюють еволюційні процеси носять назву еволюційних алгоритмів, і можуть бути поділені на декілька класів: Генетичні алгоритми(Holland 1975), Еволюційне програмування (Fogel 1962), Еволюційна стратегія (Bremermann 1965), Генетичне програмування(Koza 1992) Інші оптимізаційні алгоритми, що базуються на еволюційній теорії Дарвіна про походження видів Генетичні алгоритми Еволюційні алгоритми є дослідними алгоритмами, що імітують природні еволюційні процеси. Їхне застосування для розв”язання комбінаторно-оптимізаційних проблем є найпопулярнішою темою для наукових задач. В останній час було опубліковано багато праць та книжок на тему застосування еволюційних методів зостосування в різноманітних ділянках науки, таких як біологія, хімія, комп”ютерне проектування, криптографія, медицина, мікроелектроніка, розпізнавання образів, планування виробництва, робототехніка, телекомунікації та інших. Голанд (1975) розробив методику генетичних алгоритмів. В цих алгоритмах простір пошуків розв”язання проблеми є представлення як відбір особин. Таки особини проедставлені як набір знаків (або групами знаків), і часто називаються хромосомами. Метою використання генетичного алгоритму є знаходження особини з пошуком простору, яка представляє найкращий “генетичний матеріал”. Якості одиночної особини оцінюються за функцією пристосованя. Частина простору пошуків, яка є протестованою, називається популяцією. Переважно генетичні алгоритми виконуються наступним чином: На першому кроці відбору є випадкова початкова популяція і оцінювання її властивості. В подальшому, в кожній ітерації з популяції вибираються батьки. Батьки породжуюють нащадків, які додаються до популяції. Для всіх новостворених особин існує близка до нуля правдоподібність, що вони мають мутації, тобто що мають невеликі зміни частини їх генетичного матеріалу. В подальшому, деякі особини будуть усунені з популяції, згідно визначеного критерію селекції з метою приведення кількості популяції до її початкової кількості. Одна ітерація алгоритму приймається як генетація. Оператори, які визначають спосіб створення нащадків і процес мутації, називаються як оператори схрещування і оператори мутації. Мутація і схрещування мають різні ролі в генетичних алгоритмах. Мутація потрібна, щоб визначити нові потенційні можливості і допомогти алгоритму уникнути попадання у локальний мінімум. Схрещування повинно визначити середні властивості цілої популяції. Перед вибором відповідних операторів мутації та схрещування визначимо правдоподібність, що генетичний алгоритм знайде розв”язання близьке до оптимального в великів кількості рахунку ітерацій. Існують різні критерії закінчення генетичного алгоритму. Наприклад, встановлення верхньої межі кількості ітерацій. Однак, критерій останову повинен враховувати властивості особин в наступних генераціях генетичного алгоритму. Задача комівояжера (The Travelling Salesman Problem - TSP) Задача комівояжера у стандартній постановці виглядає так: є набір міст, потрібно відвідати найкоротшим шляхом всі міста, але кожне місто відвідується лише раз і повернутись до відправного пункту. Формально TSP можна вирішити наступним чином: Даними є: натуральні числа n ≥ 3 i маршрут C =(cij), де cij - ітераційний підрахунок, що циклічно змінюється. EMBED Equation.3 TSP є відносно старою проблемою. Вперше вона була сформульована Ейлером в 1759 році (але під іншою назвою), якій хотів розв”язати проблему шахового коня. Правильне розв”язання повинно містити шлях шахового коня по всіх 64 шахових клітинах, так щоб на кожній клітині поля кінь побував лише один раз. Термін ‘travelling salesman’ вперше був застосований в 1932 році у німецькій книзі, присвяченій вирішенню задачі комівояжера. Після багатьох років, проблема комівояжера дочекалась на багато способів розв”язання. Існує декілька причин цього. По перше TSP є дуже простим в описуванні, але важким у розв’язанні. Не знаємо жодного алгоритму, що розв’язує це завдання миттєво в баготовимірному часі. Цей недолік алгоритму, що розв’язує завдання багатовимірному часі є характерним для проблем, відомих під назвою NP – повних, для яких проблема комівояжера є класичним прикладом. По друге, TSP має застосування в багатьох різних проблемах, що зачіпають різного роду шляхи і пункти. По трете, по мірі отримання багато інформації на тему проблеми комівояжера, згодом її можна використовувати як свого роду тестову задачу, нові комбанаторні методи часто тестуються на TSP, з метою переконання в їх приктичній здатності. І зрештою велика кількість проблем, в яких маємо відповідно до завдань штучного інтелекту, призводять до знаходження найкращої permutacji n елементів. Представлення і оператори Відомо багато різних способів представлення здатних до розв”язування проблеми комівояжера за допомогою генетичних алгоритмів. Деякі з них як бінарі рішення чи маршрутне рішення використовують бінарні значення для представлення даного шляху. Хоча таке рішення є стандартом в світі генетичних алгоритмів, однак для задачі комівояжера проблемою є те, що оператори схрещуваня і мутації можуть давати погані наслідки. Для того мусимо залишити сформульовані оператори виправлень. Найкращим природнім способом представлення шляху є вигляд представлення. В цьому представленні n міст, які мають розмістити пункти відвідувань в n-елементний ланцюжок таким чином, що якщо і-те місто знаходиться в j-ій позиції за рахунком, це означає, що і-те місто відвідане як j-те. Таке представлення дозволяє сформулювати велику кількість різних операторів схрещування і мутації. Можна стверджувати, що на даний час більшість генетичних алгоритмів, що заходять приблизне розв”язання задачі комівояжера вживають таке представлення. Вагомою причиною для того є інтуїтивна простота і природність представлення, а також добрі наслідки, отримані при його застосуванні Бінарне представлення В бінарному представленні задачі комівояжера для n-міст, кожне місто закодовано у ланцюжок довжиною [log2 n] бітів. Одиночне рішення зрештою є ланцюжком, довжиною n*[log2 n] бітів. Наприклад, при шістьох містах кожне місто представлено ланцюжком довжиною у 3 біти Шлях 1-2-3-4-5-6 представлятиметься 000 001 010 011 100 101 Зауважимо, що існують 3-бітові ланцюжки. З них не кодують жодного міста: 110 і 111 Класичне схрещування (Classical Crossover) Оператор класичного схрещування був запропонований Голандом (1975). Нижще розглянемо для прикладу два шляхи, кожен з яких складаться з шістьох міст 000 001 010 011 100 101 101 100 011 010 001 000 Потім випадковим чином вибираємо точку схрещування, я якій кожен з ланцюжків буде поділено на дві частини. Припустимо наприклад, що точка схрещування вибрана між 9 та 10 бітом, тобто 000 001 010 | 011 100 101 101 100 011 | 010 001 000 З’єднавши дві різні частини кожного з ланцюжків, отримуємо нащадків 000 001 010 010 001 000 101 100 011 011 100 101 Які не представляють виправляючих шляхів. Щоб змінити створених нащадків потребуємо певного роду корегуючі алгоритми(repair algorithm). Загалом алгоритм має за мету трансформацію особин, що не належать до простору пошуків в особини, які до неї належать Класична мутація (Classical Mutation) Оператор класичної мутації також був запропонований Голандом, Neguje він один або декілька бітів особини до правдоподібної мутації, яка є наближеною до нуля. Наприклад розірвемо поновлений ланцюг, який представляє шлях 1-2-3-4-5-6 000 001 010 011 100 101 Припустимо, що 1 та 2 біт були вибрані для мутації. Вибрані біти поміняємо на протилежні. В наслідок цього отримуємо ланцюг 110 001 010 011 100 101 Який знов не представляє власний шлях. Згодом знов треба врахувати в скеровуючому алгоритмі Завдання до лабораторної роботи №3 Тема: Задача комівояжера Метою лабораторної роботи полягає у написанні програми, яка здатна вирішити задачу комівояжера. Маємо N міст. Потрібно визначити найкоротший шлях, при якому кожне місто відвідується лише один раз. Програма повинна на початку встановити довільне розташування міст (N>8) і і представити наступні кроки алгоритму: Нехай EMBED Equation.3 буде містами, а EMBED Equation.3 - відрізки між ними. Потрібно оптимізувати шлях таким чином, щоб EMBED Equation.3 і кожному EMBED Equation.3 відповідала лише одна EMBED Equation.3. EMBED Equation.3, де EMBED Equation.3 дорівнює 1, коли EMBED Equation.3 відповідає і (дорога проходить через місто) і дорівнює 0 в іншому випадку, EMBED Equation.3=const. Шлях може бути визначений ітераційно як EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Де EMBED Equation.3 є околом, що міститься всередині відрізків, відповідних міст, T=const, =const. Приклад дивіться за адресою HYPERLINK "http://nuweb.jinr.dubna.su/LNP/NEMO/tspN.html"http://nuweb.jinr.dubna.su/LNP/NEMO/tspN.html 3. Контрольні запитання Основна ідея генетичних алгоритмів. Області застосування генетичних алгоритмів. Відомі реалізації генетичних алгоритмів. Задачі оптимізації. Традиційні вирішення задачі комівояжера. Особливості вирішення задачі комівояжера за допомогою генетичних алгоритмів. Особливості програмної реалізації. 4. Лабораторне завдання Створити виконавчу програму, що спроможна вирішувати задачу комівояжера із застосуванням генетичних алгоритмів. Мова програмування вибирається за бажанням студента. Виконати завдання. Оцінити отримані результати. Оформити звіт. 5. Зміст звіту Мета роботи. Основні теоретичні відомості. Результат виконання індивідуального завдання. Висновок. 6. Список літератури Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine learning. Addison-Wesley, 1989. Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996. Батищев Д. И. Методы оптимального проектирования. - М.: Радио и связь, 1984. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно - генетических алгоритмов / Мужвуз. сборник, ВГТУ, Воронеж, 1994. Батищев Д.И., Гуляева П.А., Исаев С.А. Генетический алгоритм для решения задач невыпуклой оптимизации / Тез.докл. Междунар. конф. "Новые информационные технологии в науке, образовании и бизнесе", Гурзуф, 1997.

Методичні вказівки до лабораторної роботи Системи штучного інтелекту

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись