точках, запам'ятовуючи максимальне з них. /Td>
Недоліком цього методу є велика обчислювальна вартість. Зокрема, в задачі комівояжера потрібно прорахувати довжини більше 1030 варіантів шляхів, що абсолютно нереально. Однак, якщо перебір всіх варіантів за розумний час можливий, то можна бути абсолютно впевненим у тому, що знайдене рішення дійсно оптимально.
Другий популярний спосіб заснований на методі градієнтного спуску (рис. 7). При цьому спочатку вибираються деякі випадкові значення параметрів, а потім ці значення поступово змінюють, домагаючись найбільшої швидкості росту цільової функції. Досягнувши локального максимуму, такий алгоритм зупиняється, тому для пошуку глобального оптимуму будуть потрібні додаткові зусилля.
В
рис. 3 Метод градієнтного спуску
Градієнтні методи працюють дуже швидко, але з гарантують оптимальності знайденого рішення. Вони ідеальні для застосування в так званих унімодальних завданнях, де цільова функція має єдиний локальний максимум (він же - глобальний). Легко бачити, що завдання комівояжера унімодальної не є. tabletable border=0 cellpadding=0>
В
рис. 4
Типова практичне завдання, як правило, мультимодальна і багатовимірна, тобто містить багато параметрів. Для таких завдань не існує жодного універсального методу, який дозволяв би досить швидко знайти абсолютно точне рішення (рис. 8). /Td>
Однак, комбінуючи переборний і градієнтний методи, можна сподіватися отримати хоча б наближене рішення, точність якого буде зростати при збільшенні часу розрахунку. (Рис. 9)
В
рис. 5
Генетичний алгоритм являє собою саме такий комбінований метод (рис. 10). Механізми схрещування і мутації в якомусь сенсі реалізують переборну частина методу, а відбір кращих рішень - градієнтний спуск. На малюнку показано, що така комбінація дозволяє забезпечити стійко хорошу ефективність генетичного пошуку для будь-яких типів завдань. /Td>
рис. 10
Отже, якщо на деякій множині задана складна функція від кількох змінних, то генетичний алгоритм - це програма, яка за розумний час знаходить точку, де значення функції досить близько до максимально можливого. Вибираючи прийнятний час розрахунку, ми отримаємо одне з найкращих рішень, які взагалі можливо отримати за цей час [20].
В
2.5 Рішення завдання комівояжера.
Задача комівояжера є класичною оптимізаційної заду-чий. Суть її полягає в наступному. Дано безліч із п міст і матриця відстаней між ними або вартостей переїзду (залежно від інтерпретації). Мета комівояжера - об'їхати всі ці міста по найкоротшому шляху або з найменшими витратами на поїздку. Причому в кожному місті він має побувати один раз і свій шлях закінчити в тому ж місті, звідки почав.
Для вирішення пропонується наступне завдання: є п'ять міст, вартість переїзду між якими представлена ​​наступною матрицею:
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, що відображає послідовність відвідування міст. А значення цільової функції дорівнюватиме вартості всієї поїздки, обчисленої відповідно до вищенаведеної матрицею. В...
