Keliaujanèio pirklio uþdavinys

Darbas su programa

alt="Your browser understands the APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the APPLET> tag! 1 pav. Java programa realizuojanti SA agoritmà pirklio kelio optimizavimui. (programos kodas: pirklys.java)

1. Ðalia klaviðo cities laukelyje áraðyti norimà miestø skaièiø (maksimaliai programa palaiko 98 miestus, ávedus daugiau jokiø áspëjimø nebûna, taèiau programa veikia neteisingai). 2. Paspausti klaviðà cities. Tai padarius atsitiktinai sugeneruojami miestai. Kiekvienà kartà paspaudus sugeneruojamas vis kitas miestø iðdëstymas. 3. Galima pakeisti SA algoritmo parametrus N, M, T, a (þr. toliau programos parametrai) 4. Pauspaudus vienà ið pradinio marðruto generavimo klaviðø  (bubble, nearest, random) sugeneruojamas pradinis miestø apëjimo marðrutas ir pagal SA algoritmo pagalba bandoma já optimizuoti (þr. klaviðø paskirtis). minëti klaviðai tampa neaktyvûs. Vykdomas SA algoritmas, kol bus pasiektas maksimalus iteracijø skaièius. 5. Pabaigus optimizavimà klaviðai paleidþiantys SA (bubble, nearest, random) tampa aktyvûs.   Pastaba:  Java programa neveikia nes: Neávesti reikiami algortitmo parametrai, arba jie ávesti su klaidomis. Visi koeficientai yra teigiami. Ávedant trupmeninius skaièius vietoje "," (kablelio) naudokite "." (taðkas) Ávedëte per didelá iteracijø skaièiø ir programa uþgrobë daug kompiuterio resursø, dël to narðyklë neatsako á vartotojo komandas.

  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 turi paprastyai bûna tarp 1 ir 0.7. Nenaudokite koeficiento sveikai daliai atskirti nuo trupmeninës "," (kablelio), tam reikia naudoti "."(taðkas).

iter - nurodomas maksimalus teracijø 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à.

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à.

Arnoldas Bagdonas RM 0/1gr.,

Kauno Technologijos universitetas

Telekomunikacijø ir elektronikos fak.