BOINC - TSP

[Marty McFly]

http://bob.myisland.as/tsp/

Nový projekt zabývající se problémem obchodního cestujícího, který musí projet 48 amerických států nejkratší cestou a přitom se nesmí v každém městě stavit více než 1x... Hledá nejkratší z 6.20696x10^60 možných cest.

[LiborA]

tak moje zatím nejdelší jednotka trvala 0,03 sec. To ji mnohonásobně déle stahuji, než počítám

[Marty McFly]

Stejně tak i u mne...

http://bob.myisland.as/tsp/forum_thread.php?id=13 Tu se diskutuje o plánovaném prodloužení jednotek a jsou tam i další informace o záměrech autora projektu.

[Honza]

To je od zacatku problem.
Je potreba predelat WU template tak, aby v nem bylo vic nez jedna uloha.

[LiborA]

Po dlouhé době jsem opět spustil tento projekt a tak jsem trochu testoval a zkoumal. K mému překvapení je nejspíše tento projekt (po projití výsledků na webu) "zaujat" vůči INTEL+Windows. Můj AMD X2 4000+ je pouze mírně pomalejší než Intel Core 2 Quad Q6600 @ 2.40GHz (viz tato WU).
Ještě zajímavěji však vypadají výsledky Crunch3r a jeho linuxové mašiny s obstarožním Athlon XP 3000+. Naproti tomu Intel s P4 2800GHz na linuxu nemá tak zajímavé časy.

Velmi zajímavé je srovnání těchto počítačů:
1. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Gentoo Linuxu s 4 GB paměti - jednotka cca 33 min
2. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Windows Vista s 2 GB paměti - jednotka cca 56 min
3. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Windows Vista s 3 GB paměti - jednotka cca 54 min
4. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Windows Vista s 3 GB paměti - jednotka cca 54 min
5. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Windows XP Home s 2GB paměti - jednotka cca 43 min
6. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Windows XP Prof. s 2GB paměti - jednotka cca 57 min
7. Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz na Windows XP Prof. s 3GB paměti - jednotka cca 60 min

EDIT: na této jednotce se dokonce dva ty Quady pod Win XP "utkaly" mezi sebou (můj AMD X2 4000+ jim dělal třetího do party)

[LiborA]

V projektu se objevilo několik významných změn. Byl spuštěn nový algoritmus a s ním je spojena též nová aplikace. Nyní tedy projekt má dvě aplikace: Brute Force (MTughan) ve verzi 2.15 (resp. 2.16 pro Win64) a Genetic Algorithm ve verzi 1.03. Rozdíl vyplývá z názvů a kromě toho je za jednotky řešené "hrubou silou" fixní kredit, zatímco jednotky počítané GA jsou ohodnoceny podle flops. V preferencích projektu si každý může nastavit, zda chce počítat jednotky BF či GA.

Na této stránce si můžete prohlédnout zatím "nejúspěšnější" řešení pro oba způsoby řešení.

[Honza]

Hlavne je zajimave, ze Brute Force metodou se po tydnech prace doslo k nejlepsimu vysledku 36516 miles, zatimco novacek GA jiz dosahl delky 13766 miles.
Jinak GA je opravdu 64-bit, ne 32-bit posilany 64-bit hostu, jako treba SIMAP.

EDIT: Ga task mi bezi uz 3 hodiny a je na ~ 30%. Neni divu, ze dava lepsi vysledky.

[LiborA]

Při prolézání fóra projektu jsem narazil na odkaz na stránky známého Crunch3ra. Jak se zdá, tak se dost podílí na optimalizaci aplikace projektu.

[LiborA]

Hlavne je zajimave, ze Brute Force metodou se po tydnech prace doslo k nejlepsimu vysledku 36516 miles, zatimco novacek GA jiz dosahl delky 13766 miles.
Jinak GA je opravdu 64-bit, ne 32-bit posilany 64-bit hostu, jako treba SIMAP.

EDIT: Ga task mi bezi uz 3 hodiny a je na ~ 30%. Neni divu, ze dava lepsi vysledky.

Tak momentálně nejkratší trasa je 12180 mil

Mě počítá doma na AMD 64 2800 a na Linuxu 64b jednu GA jednotku zatím 11,5 h a mám spočteno 89,2%

[LiborA]

Markus se snaží implementovat Branch and Bound algoritmus pro omezení možných kombinací, které musí být zkontrolovány. Bližší zde.

[LiborA]

Je připravována nová aplikace GA pro Windows, bohužel se mu zatím nepodařilo ji správně sestavit, tak snad zítra.

EDIT: 7.1. - tak bohužel stále jsou problémy - aplikace "počítá" děsně pomalu, takže to není na oficiální spuštění, kdo však chce experimentovat, může si nastavit app_info.xml soubor a měly by být připraveny i testovací jednotky

[Pav Lucistnik]

Tak sem se zapojil do TSP, po dlouhe dobe novy projekt pro mne. Duvod - maji nativni FreeBSD aplikaci To je hodne vzacne mezi projekty.

Nafasoval sem dve Genetic Algorithm jednotky (nestihl sem dat no new work nez to stahlo tu druhou - mam dual core tady), odhad je 24 hodin, no potes, po 20 minutach je to na 1%, tak snad se to spocita.

Ty Brute Force jednotky sou kolem 30 minut co tak koukam na cizi pocitace, takze asi presedlam na ne.

Najoinoval sem boinc.cz team, snad je to ten spravny, nevyznam se v post-schizmaticke spleti ceskych narodnich teamu ...

[LiborA]

Najoinoval sem boinc.cz team, snad je to ten spravny, nevyznam se v post-schizmaticke spleti ceskych narodnich teamu ...

Jasně pokud chceš k nám , pokud chceš k Forestovy, tak pak musíš na Czech national team

[Pav Lucistnik]

Tak jedna GA jednotka mi spadla po hodine, druha zatim bezi. Uz mam i prvni uspesne dokoncenou BF jednotku, trvala skoro dve hodiny.

[LiborA]

TSP po opakujících se problémech se serverem chce přestěhovat server do nových prostor, což ovšem znamená placené připojení k netu a tak shání sponzory. Do konce měsíce by snad mohl být připraven nový server.