Головна

Рішення завдання комівояжера

  1. GІІ. Викладаєте проблему групі. Разом з усіма виробляєте рішення на основі консенсусу. Виконуєте будь-яке рішення групи.
  2. I. ЗАВДАННЯ АРТИЛЕРІЇ
  3. I. Мета і завдання дисципліни
  4. II. Основні завдання та їх реалізація
  5. III. 12.2. Мислення і вирішення завдань
  6. VII. Шматки ТА ЗАВДАННЯ
  7. А) Рішення в змішаній формі

Завдання комівояжера є класичною оптимізаційної завданням. Суть її полягає в наступному. Дано безліч з n міст і матриця відстаней між ними або вартостей переїзду (залежно від інтерпретації). Мета комівояжера - об'їхати всі ці міста по найкоротшому шляху або з найменшими витратами на поїздку. Причому в кожному місті він повинен побувати один раз і свій шлях закінчити в тому ж місті, звідки почав.

Для вирішення пропонується наступне завдання: є п'ять міст, вартість переїзду між якими представлена ??наступною матрицею:

Г1 Г2 Г3 Г4 Г5

Місто 1 0 4 6 2 9

Місто 2 4 0 3 2 9

Місто 3 6 3 0 5 9

Місто 4 2 2 5 0 8

Місто 5 9 9 9 8 0

Для вирішення завдання застосуємо наступний генетичний алгоритм. Рішення представимо у вигляді перестановки чисел від 1 до 5, що відображає послідовність відвідування міст. Значення цільової функції дорівнюватиме вартості всієї поїздки, обчислень відповідно до вищенаведеної матрицею. Одним з оптимальних рішень задачі є послідовність 12345 вартістю 29. З першого міста в другій вартість дорівнює 4 з другого в третій - 3, з третього до четвертого - 5, з четвертого до п'ятого - 8, з п'ятого в п'ятий - 9. Таким чином, 4 + 3 + 5 + 8 + 9 = 29.

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

В якості оператора схрещування виберемо більш витончену процедуру, схожу на двоточковий оператор схрещування. Нехай є дві батьківські перестановки (1/234/5) і (3/452/1). Випадково і равновероятно вибираються дві точки розриву. Для прикладу візьмемо ситуацію, коли перша точка розриву знаходиться між першим і другим елементами перестановки, а друга точка - між четвертим і п'ятим: (1/234/5), (3/452/1). На першому етапі перестановки обмінюються фрагментами, укладених між точками розриву: (* / 452 / *), (* / 234 / *). На другому етапі замість зірочок вставляються відповідні числа з вихідної батьківської перестановки, починаючи з другого числа. В даному випадку в першій перестановці (1/234/5) таким початковим числом є 3, а за ним йде 4, яке є в новій перестановці, і ми його пропускаємо, також пропускаємо число 5, переходимо на початок перестановки і вибираємо число 1. У підсумку замість (* / 452 / *) отримуємо (34521), аналогічно з (/ 3/452/1) і (* / 234 / *) отримуємо (52341).

Оператор мутації буде являти собою випадкову перестановку двох чисел в хромосомі, і скопіювати випадково по рівномірному закону. Наприклад, ймовірність мутації дорівнює 0,01. Розмір популяції виберемо рівним 4. Вихідна популяція представлена ??в таблиці 5.

Таблиця 5

 № рядка  код  Значення цільової функції  Імовірність участі в процесі розмноження
 32/122 (0,26)
 32/122
 29/122 (0,23)
 29/122

Нехай для схрещування було обрано такі пари: (1,3) і (2,4). В результаті були отримані нащадки, представлені в таблиці 6.

Таблиця 6

 № рядка  батьки  нащадки  Значення цільової функції для нащадків
 1 (1)  1 | 23 | 45  5 | 43 | 12
 2 (3)  5 | 43 | 12  1 | 23 | 54
 3 (2)  2 | 143 | 5  4 | 312 | 5мутація 13254
 4 (4)  4 | 312 | 5  2 | 143 | 5

Нехай для нащадка (12354) спрацював оператор мутації, і обмінялися місцями числа 2 і 3. В даному випадку рядок (12354) змінилася і прийняла значення (13254). Популяція першого покоління після відсікання «гірших» особин в результаті роботи оператора редукції прийняла вигляд, представлений в таблиці 7.

Таблиця 7

 № рядка  код  Значення цільової функції  Імовірність участі в процесі розмноження
 28/111 29/115
 28/111 28/115
 29/111 29/115
 28/111 28/115

Нехай для отримання другого покоління були обрані наступні пари рядків: (1, 4) і (2, 3). В результаті були отримані нащадки, показані в таблиці 8.

Таблиця 8

 № рядка  батьки  нащадки  Значення цільової функції для нащадків
 | 123 | 45  | 214 | 35
 | 214 | 35  | 123 | 45
 | 21 | 435  | 13 | 452
 | 13 | 254  | 21 | 354

Популяції другого покоління після відсікання гірших особин набрала вигляду, показаного в таблиці 9.

Таблиця 9

 № рядка  код  Значення цільової функції  Імовірність участі в процесі розмноження
 1 (1)  29/114
 2 (2)  28/114
 3 (3)  29/114
 4 (н)  28/114

Таким чином, після двох ітерацій значення цільової функції для кращого вирішення змінилося з 29 на 28, середнє значення змінилося з 30,5 до 28,75, а загальна якість з 122 до 114. Спостерігається поліпшення популяції.

Завдання 1.Провести пошук мінімуму одновимірної функції f (x) = x2-16х +5 за допомогою генетичних алгоритмів. Описати 2 популяції. Генотип алгоритму являє собою рядок з 5 біт. Розмір популяції - 4. Наприклад, рядок 01011 відповідає числу х = 11, а f (x) = -50. Використовувати одноточковий кросовер. Мутація полягає в інверсії одного з бітів рядка, що обирається випадково. Елітизм необхідно використовувати.



1. генетичні алгоритми - Це нова галузь досліджень, яка з'явилася в результаті робіт Д. Холланда і його колег. Генетичні алгоритми, описані Д. Холландом, запозичують у своїй термінології багато з природною генетики. Далі будуть наведені технічні тлумачення термінів з біології і генетики, які використовуються в теорії і практиці генетичних алгоритмів. Вперше генетичні алгоритми були застосовані до таких наукових проблем, як розпізнавання образів і оптимізація. Генетичний алгоритм являє собою адаптивний пошуковий метод, заснований на селекції кращих елементів в популяції, подібно еволюційної теорії Ч. Дарвіна.

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

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

Мета генетичних алгоритмів полягає в тому, щоб:

· Абстрактно і формально пояснювати адаптацію процесів в природній системі і інтелектуальної дослідницької системі;

· Моделювати еволюційні процеси для ефективного вирішення оптимізаційних задач науки і техніки.

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

Генетичні алгоритми відрізняються від інших оптимізаційних і пошукових процедур наступним:

· Працюють в основному не з параметрами завдання, а з закодованим безліччю параметрів;

· Здійснюють пошук не шляхом поліпшення одного рішення, а шляхом використання відразу декількох альтернатив на заданій множині рішень;

· використовують цільову функцію, А не її різні збільшення для оцінки якості прийняття рішень;

· Застосовують не детерміновані, а імовірнісні правила аналізу оптимізаційних завдань.

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

2. Наведемо деякі поняття і визначення з теорії генетичних алгоритмів. Всі генетичні алгоритми працюють на підставі початкової інформації, в якості якої виступає популяція альтернативних рішень Р. популяція Рt= {P1, P2, ..., Рi, ..., РNp} Є безліч елементів Рi , t= 0,1,2 ... - номер генерації генетичного алгоритму, Np - розмір популяції. кожен елемент Рi цієї популяції, як правило, являє собою одну або кілька хромосом або особин, або індивідуальностей (альтернативних упорядкованих або невпорядкованих рішень). Хромосоми складаються з генів Рt= {g1, g2, ..., Gv} (Елементи, частини закодованого рішення), і позиції генів в хромосомі називаються лоції або локус для однієї позиції, тобто ген - піделементи (елемент в хромосомі), локус - Позиція в хромосомі, аллель - Функціональне значення гена.

Гени можуть мати числові або функціональні значення. Зазвичай ці числові значення беруться з деякого алфавіту. Генетичний матеріал елементів зазвичай кодується на основі двійкового алфавіту {0,1}, хоча можна використовувати літерні, а також десяткові та інші алфавіти. Прикладом закодованої хромосоми довжини дев'ять на основі двійкового алфавіту може служити хромосома Рt= (001001101).

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

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

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

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

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

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

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

3. При вирішенні практичних завдань з використанням генетичних алгоритмів зазвичай виконують чотири попередніх етапи:

· Вибір способу подання рішення;

· Розробка операторів випадкових змін;

· Визначення способів «виживання» рішень;

· Створення початкової популяції альтернативних рішень.

Розглянемо деякі особливості виконання цих етапів.

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

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

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

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

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



Попередня   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   Наступна

Актуальність проблеми | Засоби створення інтелектуальних додатків | Засоби вилучення нової інформації | розділ 9 | Основні терміни та визначення | запит Відповідь | Системи обробки зв'язкових текстів | Компонент розуміння висловлювання компонент генерації висловлювання | розділ 10 | Основи теорії генетичних алгоритмів |

© um.co.ua - учбові матеріали та реферати