Obchodný cestujúci - algoritmy
V nadväznosti na články v minulosti venované tejto problematike bude tento článok venovaný zisteniam a porovnaniam niektorých vybraných algoritmov TSP (traveling salesman problem). V krátkosti sa jedná o zistenie, čo najkratšej možnej cesty pre spojenie rôznych bodov, tak aby obchodný cestujúci navštívil všetky miesta a vrátil sa na začiatok svojej cesty. Problém TSP však nerieši len najkratšiu trasu pre cestovateľov, ale nájde široké uplatnenie hlavne v strojárstve, pri optimalizácii trasy stroja, ktorý niečo ukladá, alebo napr. CNC strojov, rôznych robotov a pod. Totiž ak stroj vykonáva pri vyrezávaní, vysekávaní, ukladaní zbytočne dlhú trasu zvyšujú sa náklady na výrobok, zvyšuje sa čas na tieto úkony.Z tohto dôvodu existujú rôzne programy a algoritmy, ktoré viac či menej úspešne riešia problematiku TSP. Medzi tie známe patrí simulované žíhanie, algoritmus horolezca (climbing hill algorithm), algoritmus najbližšieho suseda, genetické algoritmy.
Medzi tie menej známe, ktoré sú postavené na znalostiach lineárneho programovania patrí Concorde TSP. Concorde TSP nájde exaktne najkratšiu cestu (aspoň to tak autori tvrdia) za naozaj rozumný čas.
V článku ďalej nájdete program (v pythone) pre porovnanie niektorých dostupných algoritmov + nejaké vylepšenia.
Program, algoritmus v pythone zdarma
Tento program porovnáva niektoré vybrané metódy medzi sebou s tým, že vykreslí graf spojníc a vypíše aj pole jednotlivých spájaných bodov a celkovú dĺžku. Pri spustení sa zadáva počet generovaných bodov, počet cyklov simulovaného žíhania. Odporúčame nepresiahnuť hranicu 2000 bodov/ 1000 iterácii (simulovaného žíhania), lebo sa čas významne predĺži, nakoľko algoritmy nie sú optimalizované na veľké počty bodov (ani nie su stavané na takéto počty). Nakoniec bežné metódy nedávajú dobré výsledky pri viac ako 500 bodov ich efektivita výrazne klesá.
Poznámka:
Pre pokračovanie vo výpočte (iných metód) treba v programe zavrieť aktuálne vykreslený graf.
Zdrojový kód:
V Pythone: traveling_salesman_problem_2.py
exe súbor: traveling_salesman_problem_2 .exe (spustiteľný súbor bez nutnosti inštalácie Pythonu)
Poznámka pre Python súbor: Vyžaduje knižnicu matplotlib, ta sa nainštaluje napísaním do príkazového riadka po inštalácii pythonu:
pip install matplotlib
Vyhodnotenie algoritmov
Základné algoritmy pracujú celkom dobre do 10-12 bodov. Simulované žíhanie, genetické algoritmy, horolezec, najbližší sused, aj genetický algoritmus nájdu optimálnu trasu, alebo blízko optimálnej. Po hodnote 15 bodov dominuje so základných algoritmov najmä algoritmus najbližšieho suseda. V programe je navyše optimalizovaný a urobí všetky alternatívy zo všetkých náhodných bodov ( prejde všetky varianty, kde stotožní počiatok s každým generovaným bodom), čím sa zlepší okolo 10-20% oproti náhodnej jednej cesty z náhodného bodu (počiatok). Tento optimalizovaný najbližší sused predčí tie zvyšné dostupné algoritmy o stovky %. To sa prejaví pri viac ako 20,30 bodov. Teda záver je ten, že najlepší dostupný algoritmus (z tých jednoduchých) je algoritmus najbližšieho suseda a generovať počiatok z viacerých počiatočných bodov. Tu však treba napísať, že ak napr. použijeme simulované žíhanie po sebe 2000-3000 krát (čo si vyžiada dlhší čas), tak žíhanie sa priblíži k optimalizovanej ceste najbližšieho suseda.Dovolím si tvrdiť, že cesta sa od tej dokonalej, optimálnej nebude líšiť o viac ako 10-20% celkovej cesty.
Obr.1 Príklad porovnania na malej vzorke.
Obr.2 Príklad ručného optimalizovania najbližšieho suseda, vymazané cesty, ktoré sa krížia.
Na obr. č.2 je ručne optimalizovaná najlepšia cesta algoritmom najbližšieho suseda a to v zmysle zásad popísaných v minulých dieloch. Táto cesta je veľmi blízko dokonalej cesty, zhruba 1-2% sa od nej môže líšiť.
Samozrejme, že to ručné optimalizovanie by sa dalo nejak do-programovať, avšak algoritmus najbližšieho suseda, ak to urobíme tak, že to preženieme všetkými počiatočnými bodmi začne byť zhruba pri 200 bodoch a viac neefektívne. Preto optimalizovať algoritmus najbližšieho suseda nemá prakticky význam, keďže existujú na trhu lepšie algoritmy ako je Concorde TSP.
Dal by sa však postaviť algoritmus na lepšej báze ako na báze najbližšieho suseda. Možno taký algoritmus by bol rýchlejší pri vyššom počte bodov ako concorde TSP, pričom by sa od dokonalej trasy neodchýlil o viac ako 1%. Možno v budúcnosti ak budem mať čas a chuť vytvoriť taký algoritmus.
Ďalší príklad porovnania metód z programu:
obr.3 porovnanie s vylepšenou metódou najbližšieho suseda
Na obr.3 vidíte progres medzi simulovaným žíhaním a vylepšenou metódou najbližšieho suseda (optimalizovanou). Táto metóda nájde optimálne riešenie, resp. blízko optimálneho riešenia do cca 35-50 bodov. Záleží od rozmiestenia. Na obrázku je vyznačené , že ak zrušíme kríženie, tak spojnicami, červenou farbou dostaneme optimálnu cestu.
Concorde TSP
website: https://www.math.uwaterloo.ca/tsp/concorde.html
Tento algoritmus je postavený na metódach lineárneho programovania a matematických prác z 20 storočia. Nejdem rozvádzať popis týchto metód, viac nájdete na stránke autorov, alebo si môžete pozrieť video o týchto metódach a Concorde TSP:
https://www.youtube.com/watch?v=tChnXG6ulyE
Krátky návod na obsluhu:
edit -->Add random nodes / náhodne vygenerujete body, počet bodov
edit -->Mouse mode --> Create mode/ naklikáte body, ktoré chcete spojiť
solve - vyrieši cestu
v poznámkovom bloku si vytvorte súbor a napíšte v takomto formáte údaje:
prvý riadok je počet bodov, ďalšie udávajú súradnice bodu x y
V Concorde TSP otvorte tento súbor, nedávajte mu žiadnu koncovku. Concorde naimportuje body. Ak dáte uložiť po výpočte doplní do toho súboru aj aj údaje cesty. Môžete si aj ponastavovať heuristiky rôzne a pod.
Obr.4 Riešenie Concorde na ľavej strane s riešením ručne, rozdiel v dĺžke trasy cca 1%.
Na obr.4 je vykreslený príklad použitia metód z minulých dielov a práce Concorde TSP. Rozdiel naozaj malý, pretože Concorde aj popísané zásady spájania vedú na rovnaké výsledky, pričom počítať ma výhodu v tom preveriť rôzne spojenia lokálnych riešení. To znamená, že rovnako zásady aj Concorde nerieši naraz celú cestu, ale jej časti a potom ich prepojí. Popísané metódy v minulých dieloch sú teda správne a účinné.
Pre zaujímavosť som našiel v Concorde TSP niektoré malé úseky, kde sa dala nájsť lepšia cesta, napr.:
obr.4 Oprava malej časti riešenia Concorde TSP v nejakom príklade.
Concorde TSP nebude dokonalý a vo väčšom súbore rôznych dát nájdeme malé nedokonalosti (príklad obr.4). Na to dokonca postačuje ľudské oko.