XII. Проблема за Търговския Пътник

За Проблема

Проблема за търговския пътник (TSP) бе споменат в една от предишните глави. Все пак повторени, дадени са градове и разстоянията между тях. Търговския пътник трябва да ги посети всичките, но без да пътува твърде много. Задачата е да се намери последовател ност от градове, така че да се намали разстоянието за пътуване. С други думи, намиране на минимален Хамилтонов път пълен граф с N възли.

Реализация

Използва се популация от 16 хромозома. За кодиране на тези хромоми се използва кодиране на пермутации - в главата за кодиране може да бъде открито, как да се кодират пермутациите на градовете за TSP. TSP е разрешен в пълен граф (т.е. всеки възел е свързан с всички останали) с дъги за разстоянието. Съществено е че след добавяне или изтриване на град е необходимо да се създадат нови хромозими и ре стартира целия генетичен алгоритъм.

Може да се избира типа на кръстосване и мутация. Ще бъде обяснено какво означават това.

Кръстосване

Една точка - копира се част от първата хромозома и останалото се взема в същата последователност каквато е във втория родител
Две точки - две части от първия родител се копират, а останалото по между им се взема в същата последователност каквато е във втория родител
Без - ням кръстосване, потомството е точно копие на родителите

Мутация

Обикновена случайна - няколко градове се избират и разменят
Случайна, само подобряваща - няколко града се избит и разменят по случаен принцип, само ако подобряват решението (повишават жизнеспособността)
Систематизирана, само подобряваща - градовете се избират и разменят систематично само ако подобряват решението (повишават жизнеспособността)
Случайна подобряваща - същото както "случайна, само подобряваща", но преди това се извършва "случайна, нормална" мутация
Систематизирана подобряваща - същото както "систематизирана, само подобряваща", но преди това се извършва "случайна, нормална" мутация
Без - няма мутация

Пример

Следния апелт показва GA за TSP. Бутона "Change View" сменя изгледа от цялата популация към най-доброто решение и обратното. Може да се добавят и премахват градове на графиката. След добавяне или изтриване произволно трасе ще се появи защото се създава нова популация с нови хромозоми. Също се отбелязва че се решава TSP в пълен граф.
Опитайте да стартирате GA с различно кръстосване и мутация, забележете как се променя изпълнението (и скоростта - добавете повече градове за да го видите) на GA.

Тук има аплет, но вашия browser не поддържа Java. Ако желаете да видите аплета, моля проверете изисквания за browser.