Keliaujanèio pirklio uþdavinys

Arnoldas Bagdonas RM 0/1gr.,

Kauno Technologijos universitetas

Telekomunikacijø ir elektronikos fak.

Turinys:

Problemos apraðymas

Sprendimas:

• Algoritmas

• Programos(algoritmo) parametrai

• Programos apraðymas

• Algoritmo tyrimas

Iðvados

Problemos apraðymas

Pirklys nori apeiti visus ðalies miestus apsilankydamas kiekviename ið jø tik po vienà kartà. Jis nori kuo maþiau pavargti, dël to jam reikia eiti kuo trumpesniu keliu. Reikia rasti algoritmà, kuris padëtø pirkliui surasti minëtà marðrutà.

Sprendimas

Programos parametrai

N - koeficientas, kuris apsprendþia T parametro kitimo greitá.  T reikðmë keièiama po N sistemos bûsenos pasikeitimø. Ðis koeficientas turi bûti sveikas skaièius, t.y. netrupmeninis.

M - koeficientas, kuris kaip ir N apsprendþia T parametro kitimo greitá. T.y. T reikðmë keièiama kas M sistemos bûsenos pasikeitimø, kurie sumaþina sistemos energijà arba optimizuojamàjá dydá, ðiuo atveju marðruto ilgá. Ðis parametras turi bûti sveikas skaièius, t.y. netrupmeninis.

T - koeficientas apsprendþiantis su kokia tikimybe reikia pereiti á blogesnæ (maþiau optimalià) bûsenà. 

a - koeficientas, nuo kurio priklauso T keitimo greitis, nauja T reikðmë gaunama senàjà dauginant ið a. Ðis koeficientas  paprastai bûna tarp 1 ir 0.7. Nenaudokite koeficiento sveikai daliai atskirti nuo trupmeninës "," (kablelio), tam reikia naudoti "."(taðkà).

iter - nurodomas maksimalus iteracijø skaièius. Patartina ðá skaièiø parinkti kuo maþesná, ir ávertinus turimo kompiuterio spartà atitinkamai já padidinti taip, kad skaièiavimai bûtø uþbaigiami per priimtinà laiko tarpà.

Programos apraðymas

Klaviðø paskirtis:

cities - atsitiktinai sugeneruojamos miestø koordinatës. Miestø skaièius nurodomas gretimame laukelyje.

Kiti klaviðai yra skirti pradinio marðruto generavimui:

random - sugeneruojamas atsitiktinis miestø apëjimo marðrutas.

nearest - pradedama nuo kokio nors miesto ir ieðkomas artimiausias, po to kitas artimiausias ir taip tæsiama, kol visi miestai aplankomi po vienà kartà.

bubble - pradedama nuo trijø atsitiktiniø miestø. Po to imamas naujas miestas ir ieðkoma, kurioje ankstesnius miestus jungianèioje kraðtinëje geriausia átraukti naujàjá miestà. Taip tæsiama, kol visi miestai bus átraukti á marðrutà.

Paspaudus vienà ið marðruto generavimo klaviðø (bubble, nearest, random) pradedamas vykdyti SA algortimas, surastas trumpausio marðruto ilgis rodomas deðinëje pusëje The best length laukelyje, sugeneruoto marðruto ilgis rodomas virð jo esanèiame laukelyje Old length, o algoritmas esamu laiko momentu parodo turimà marðruto ilgá laukelyje The curent lenght. Norint pamatyti SA surastà optimalø kelià reikia uþdëti varnelæ laukelyje SA, to nepadarius bus parodomas pradinis marðrutas.

iter laukelyje reikia nurodyti SA algortimo iteracijø skaièiø. Patartina pradëti nuo maþø reikðmiø, nes ávedus didelá skaièiø kompiuteris bus labai apkrautas ir gali sutrikti jo normalus darbas.

Pastaba:  þemëlapyje mëlynomis linijomis pavaizduojamas pradinis sugeneruotas marðrutas, raudona - SA surastas optimalus marðrutas. Taip pat maksimalus miestø skaièius yra ribotas - maksimaliai galimi 98 miestai.

2 pav. SA algoritmo adaptuoto pirklio uþdaviniui spræsti blokinë schema.

Algoritmo tyrimas:

Tyrinëjant algoritmà paaiðkëjo, jog priklausomai nuo parinktø algortimo parametrø N, M, a ir T gaunami gana skirtingi rezultatai (þr. 1-3 lenteles). Siekiant sumaþinti laiko sànaudas, ðiame ekspermente buvo uþsiduotas maksimalus iteracijø skaièius lygus 10000.

 1 lentelë. Pastovus parametras T (visi kiti kintantys)

 2 lentelë. Pastovus parametras N (visi kiti kintantys)

 3 lentelë. Pastovus parametras M (visi kiti kintantys)

 Pastaba: vid. ilgis   tai ávairiø algoritmo realizacijø su skirtingais parametrais rastø optimaliø sprendiniø (trumpiausiø keliø) vidurkis.

 Kaip matome gaunami rezultatai labiausiai priklauso nuo T: kuo T maþesnis, tuo geresni rezultatai. Taèiau, kai T maþas galima pakankamai ilgai laukti optimalaus sprendinio ir nesulaukti, nes paprasèiausiai sistema gali bûti tokioje bûsenoje, ið kurios á optimalià pereinama per þymiai aukðtesnës energijos bûsenà.

Kitas parametras  yra N, nuo jo labai priklauso temperatûros maþëjimo greitis, arba blogo sprendinio priëmimo tikimybës maþëjimas. Jei ðis parametras yra maþas, tai temperatûra greièiau maþëja ir á aukðtesnës energijos bûsenas pereinama vis reèiau ir reèiau.

Analogiðkas parametro M vaidmuo, tik jis turi didesnæ átakà prie maþesniø T reikðmiø, kai pakeitimai daromi vis daþniau á maþesnës energijos bûsenà.

 Nors SA algoritmas yra gana paprastas, taèiau já galima patobulinti: parinkti optimalias T, M, N ir a reikðmes. Taip pat algoritmà galima patobulinti parinkus geresná pradiná marðrutà. Vienas ið galimø algoritmø yra  toks pradedama nuo bet kurio laisvai pasirinkto miesto, po to einama á jam artimiausià, po to vël á artimiausià. Taip tæsiama, kol neliks miestø, kuriuose dar nebuvome apsilankæ. Po to einama vël á pradiná miestà. Tai yra artimiausio miesto algortimas. Algoritmo efektyvumas taip pat priklauso nuo to kokie sistemos pakeitimai naudojami sukeièiama tik dviejø gretimø miestø apëjimo tvarka, sukeièiama atsitiktinai parinktø miestø apëjimo tvarka ir pan. Nuo to, mano nuomone, taip pat labai priklauso gaunami rezultatai.

 Parametrø optimizavimo tikslingumà galima pailiustruoti taip:

 a)      Parenkamas atsitiktinis pradinis miestø apëjimo marðrutas (jo ilgis 6012 kilometrø), parametrai T=500, N=200, M=10, a=0.99. Per 3 valandas darbo (maksimalus iteracijø skaièius nebuvo ribotas) algoritmas surado optimalø 3012 kilometrø ilgio sprendiná.

b)      Parenkamas pradinis miestø apëjimo marðrutas panaudojant artimiausio miesto algoritmà (jo ilgis 3082 kilometrø), parametrai T=20, N=200, M=10, a=0.99. Per 30 minuèiø darbo (maksimalus iteracijø skaièius nebuvo ribotas) algoritmas surado optimalø 2996 kilometrø ilgio sprendiná.

Iðvados: 

1. SA algoritmas leidþia surasti optimalø marðrutà, taèiau tam reikia daug laiko - algoritmas turi "perþiûrëti" labai daug sistemos bûsenø.

2. Norint gauti tuos paèius rezultatus per trumpesná laikà, reikia optimizuoti algortimo parametrus. Jø optimizavimo nenagrinësiu, nes tai atskiras ir sudëtingas darbas reikia rasti keturiø-ðeðiø argumentø (priklausomai nuo SA realizavimo) funkcijos (N,M,T,a, miestø keitimo tvarka, L) geriausià rezultatà duodanèià reikðmæ. Taip pat reikia nepamirðti, jog tokios sudëtingos funkcijos optimizavimas reikalaus daug laiko ir kiekvienu atveju gali bûti vis kitoks (t.y. vienam atvejui rasti optimalûs parametrai kitu atveju gali visiðkai netikti).