Problém obchodný cestujúci

No ale ja som tu nezačal debatu o pseudonáhodných generátoroch, to si tu vniesol tu ty. Pri 100 tisíc bodoch to nerozlíšiš, pretože generátor ma oveľa dlhšiu periódu. Nechápem o čom tu ty básniš dal som ti názov algoritmu, ktorý rieši 10-100 tisíc bodov, máš tu aj obrázok TSP art, ktorý je tak vyriešený. Tak čo vlastne ty tu spochybňuješ? Ja som urobil cely program a navrhol vlastnú metódu, ktorá je rýchla, tak o čom by si ma chcel poučiť?

Ja som nič nespochybňoval ani ťa nechcem poučovať. Prepáč, ak si to tak pochopil.

Tak som doprogramoval ďalšiu metódu pre použitie v programe(TSP Solver) LKH 3.0.10, zatiaľ najlepšia metóda výkon/dĺžka cesty + dorobil som modul pre TSP ART tak len niečo malé na ukážku, keďže tu sa nedajú pridávať veľké súbory

Blog článok ako si vytvoriť vlastný TSP Art v programe TSP Solver + niekoľko vytvorených TSP Artov v svg súboroch, ktoré si môžete naškálovať podľa potrieb.

https://robopol.sk/blog/tsp-art

Tak som vytvoril webovú verziu programu TSP Solver  verzia 1.0.4.  Ide zatiaľ o offline webovú aplikáciu, takže si inštalačný súbor môžete stiahnuť a vyskúšať omnoho lepšiu grafiku ako to bolo doposiaľ v tkiner aplikácii (python).

Aplikácia beží ako flusk server na PC, takže pozor na zatváranie konzoly - cmd. Viac informácii nájdete na: 

 https://robopol.sk/tsp-solver/index

Tono,

neviem, či ešte sleduješ toto vlákno, tak som celu aplikáciu urobil ako webovú a podarilo sa mi vytvoriť extrémne rýchly algoritmus, s optimálnou trasou je pri nesymetrických bodoch ma 4-5% dlhšiu trasu, pre symetrické je to 1-2%, napr. TSP Art. Metoda je schopná za 4 sekundy vyrátať 5000 bodov. Je to ohodne rýchlejšie ako najlepší algoritmus LKH 3.0.10, lenže ten nájde optimálnu trasu alebo pri veľkom počte bodov trasu do +1%, možno je na tom dokonca lepšie, nikto totiž nemá lepšiu metódu, ktorá by preverila presnosť na extrémnom počte čísiel.

pred 16 hodinami, robopol pridal:

neviem, či ešte sleduješ toto vlákno

Sledujem tvoje pokroky, ale podrobnejšie sa týmto problémom nezaoberám. V súčasnosti sa neviem na nič sústrediť.

Tak si znova o niečo pokročil. Webová aplikácia je dnes už takmer nutnosťou. Ak si chce niekto vyskúšať nejakú demo verziu, málo kto je ochotný niečo inštalovať, aj z bezpečnostných dôvodov. Kto má vážny záujem, alebo sa o problematiku hlbšie zaujíma, ten bude hľadať kontakt na autora.

Vyskúšať sa da metóda základná v javascripte https://www.poling.sk/TSP/index.html, mam offline verziu, kde využívam strojový kod cez numba a python a mam v nej sofistikovanejšie modely, napr. robopol algorithm precise, alebo LKH 3.0.10. V demo verzii offline programu, ktorý vyžaduje inštaláciu si môže napríklad ľubovoľnú fotku zmeniť na body a tie pospájať, v demo verzii je možnosť urobit 10 tisic bodov. ten výpočet trva par sekund. Mojim cielom j e poraziť ten LKH algoritmus, ktory najde najlepšiu trasu behom kratkeho času. Ja mam extrémne rýchly algoritmus ale nenajde optimalnu drahu pre velky počet bodov, zato je však neuveritelne rýchly a ešte ho škálujem, aby daval lepšie výsledky a to spustením ako multiproces, teda súčasne bude robit naraz viaceré alternatívy naraz, čo ho posunie o 1-2% k optimalnej trase. No dostať sa na optimálnu trasu bez použitia prístupov LKH je vyzva naročná.

Ak by som to chcel mat ako online web aplikaciu, to vyžaduje, aby som si zakupil server, kde budem využivať CPU, GPU, alebo RAM servera, musel by tam bežať python a podobne.

Tak už sa bližim k optimalnym riešeniam, nejake kroky pomohli teraz je to takto: 

Robopol Algoritmus

V sekcii Metódy výber "Robopol algoritmu" predstavuje vylepšený prístup najbližšieho suseda, ktorý obsahuje optimalizačné kroky na dosiahnutie vysoko efektívnych výsledkov. Algoritmus je optimalizovaný na rýchlosť vďaka využitiu knižnice Numba, ktorá kompiluje Python kód do strojového kódu. To zabezpečuje výrazne rýchlejšie vykonávanie v porovnaní s optimálnou trasou, pričom presnosť závisí od počtu a rozloženia bodov. Navyše, v porovnaní s LKH 3.0.10 Robopol algoritmus jasne vyniká rýchlosťou. Algoritmus využíva maticu vzdialeností uloženú v RAM, pričom na spracovanie veľkých datasetov vyžaduje 16 GB pamäte.  Rýchlosť tohto algoritmu je unikátna, je vhodny na velké počty bodov, kde nepotrebujeme dosiahnuť optimalnu trasu, presnosť je niekde od+1% (od optimalnej trasy) pre maly počet bodov 100 bodov a potom to rastie a pre velke inštancie bodov >50 tisic to bude niekde 6-7%. Presnosť algoritmov bola testovaná na náhodne rozmiestnených bodoch. Ak sú však body symetricky rozložené, presnosť sa môže zlepšiť až o 2–3 %.

Robopol Algoritmus - Presný

Presný Robopol algoritmus (Robopol Precise) je rozšírením štandardnej verzie a poskytuje vyššiu presnosť. Pri menších datasetoch (100–200 bodov) so špecifickými nastaveniami, ako je max_segment_size=5 a vykonanie algoritmu viac ako 50-krát, dosahuje takmer optimálne riešenia s odchýlkou približne +0,5 % od optimálnej trasy. Pri datasetoch strednej veľkosti (1 000–2 000 bodov) sa dĺžka trasy mierne zvyšuje, pričom odchýlka od optimálnej trasy je približne 1–3 %. Pri veľmi veľkých datasetoch (>10 000 bodov) je presnosť citlivejšia na nastavenia parametrov, no vo všeobecnosti je dĺžka trasy približne o 4–5 % dlhšia ako optimálna.

Presnosť algoritmov bola testovaná na náhodne rozmiestnených bodoch. Ak sú však body symetricky rozložené, presnosť sa môže zlepšiť až o 2–3 %.

Čas prvej exekúcie

Stojí za zmienku, že prvé vykonanie Robopol algoritmu aj Presného Robopol algoritmu trvá dlhšie po načítaní stránky programu. Toto oneskorenie je spôsobené tým, že knižnica Numba počas prvej exekúcie kompiluje Python kód do strojového kódu, čím optimalizuje algoritmy pre ďalšie spustenia.

🚀 Nová verzia TSP Solver 1.0.5 je tu! 🚀

S radosťou oznamujeme vydanie najnovšej verzie nášho softvéru na riešenie problému obchodného cestujúceho - TSP Solver 1.0.5!

🎨 Čo je nové?

Kompletne prepracovaný dizajn s podporou tmavého režimu pre pohodlnú prácu aj v noci

Nové užívateľské rozhranie s intuitívnymi ovládacími prvkami a responzívnym dizajnom

Vylepšené nastavenia vizualizácie umožňujúce prispôsobiť farby, veľkosť bodov a hrúbku čiar

💪 Dramatické zlepšenie výkonu

Algoritmus Robopol Precise bol kompletne prepracovaný s podporou paralelných výpočtov

Až o 40% rýchlejšie výpočty pri zachovaní vysokej presnosti riešenia

Lepšie výsledky ako konkurenčné algoritmy pri menších sadách bodov (do 200)

🛠️ Ďalšie vylepšenia

Optimalizovaná práca s pamäťou pri veľkých sadách bodov

Vylepšená exportná funkcionalita

Nové možnosti vizualizácie výsledkov

Vyskúšajte novú verziu ešte dnes a presvedčte sa sami o vylepšeniach!

https://robopol.sk/tsp-solver/index

#TSPSolver #OptimalizáciaTrasy #NováVerzia #Algoritmy #ParalelnéVýpočty

Tak som konecne dohnal LKH algoritmus a aj predbehol v rýchlosti a kvalite riešeni, nasadil som na to AI a navrhli sme spolu dalsi algoritmus, ktorý ho pochoval (vyuziva dostupne jadra CPU, na masivne paralelne vypočty v strojovom kode): 

stiahnut sa da software zdarma aj vyskusat na nahodnych bodoch: https://robopol.sk/tsp-solver.html

Robopol Refined - beast - drtič kosti

Metóda "Robopol Refined" predstavuje ďalšie vylepšenie navrhnuté s cieľom potenciálne zlepšiť riešenia nájdené metódou "Robopol Algorithm - Precise" použitím stratégie Iterovaného Lokálneho Vyhľadávania (Iterated Local Search - ILS). ILS je obzvlášť efektívne pri úniku z lokálnych optim, v ktorých by štandardné optimalizačné algoritmy mohli uviaznuť.

Táto metóda začína s vysoko kvalitným počiatočným riešením, zvyčajne vygenerovaným pomocou metódy "Robopol Algorithm - Precise". Následne vstupuje do iteračného cyklu:

Perturbácia (Porucha): Aktuálne najlepšie riešenie je zámerne modifikované pomocou významného "otrasového" mechanizmu, konkrétne kroku Double Bridge (špecifický 4-opt krok). Toto pomáha vyhľadávaniu vyskočiť z oblasti lokálneho minima.

Lokálne Vyhľadávanie: Perturbované riešenie je následne intenzívne re-optimalizované pomocou rovnakých heuristík lokálneho vyhľadávania ako v metóde "Precise" (ako napr. 2-opt a adaptívne presuny segmentov).

Akceptácia: Ak je novo optimalizované riešenie lepšie ako aktuálne najlepšie známe riešenie, je akceptované ako nová referenčná hodnota (benchmark).

Tento cyklus perturbácie a re-optimalizácie sa opakuje pre špecifikovaný počet iterácií, ktorý je riadený parametrom ils_iterations (nachádza sa v Nastaveniach Metód - Method Settings). Vyšší počet iterácií umožňuje rozsiahlejšie prehľadávanie priestoru riešení, ale zvyšuje výpočtový čas.

V porovnaní s metódou "Robopol Algorithm - Precise" si metóda "Robopol Refined" vo všeobecnosti vyžaduje viac výpočtového času kvôli opakovaným cyklom perturbácie a optimalizácie. Avšak toto rozšírené vyhľadávanie ponúka vyššiu pravdepodobnosť nájdenia kvalitnejších riešení, najmä pre zložité alebo rozsiahle inštancie problému, kde by metóda "Precise" mohla konvergovať k suboptimálnemu lokálnemu minimu. Navyše, keďže ILS fáza iteratívne vylepšuje trasu, používatelia môžu zistiť, že pri použití metódy "Robopol Refined" môžu znížiť počiatočné parametre používané základnou logikou "Robopol Precise" (ako napríklad num_runs alebo startMax). ILS cykly dokážu často kompenzovať aj menej optimalizované počiatočné riešenie, čo môže viesť k dobrým výsledkom blízko optimálnej trasy aj pri rýchlejších počiatočných nastaveniach. Konečný zisk v presnosti závisí od štruktúry problému a počtu vykonaných ILS iterácií.

Nove verzia 1.07 podporuje aj hľadanie ciest priamo na mapách - zadaním priamo adries

https://robopol.sk/tsp-solver.html 

#TSPSolver #OptimanizaciaTrasy #Logistika #Doprava #Algoritmy #NováVerzia #Robopol #CestnáVzdialenosť #RoutePlanning #TSP

tak teraz je cela aplikácia dostupná aj na novej domene https://tspsolver.robopol.sk/    kde funguje síce na slabsom hardware ale funguje, co je hlavne.  Dalej je to optimalizovane aj cez mobil a teda trasy sa DAJU poslat na mobil do navigácie priamo. Viac informácii je na https://robopol.sk/tsp-solver.html

Program už zvládne ovládať aj AI