Vartotojo instrukcija ir tyrimų medžiaga

Vartotojo instrukcija ir tyrimų medžiaga

"Kuprinės (knapsack)" uždavinys (dar kitaip vadinamas "vagies" uždaviniu) formuluojamas sekančiai: reikia maksimizuoti bendrą imamų objektų vertę, esant ribotam svoriui. Jo sprendimui čia naudojami apytiksliai algoritmai vadinami MonteKarlo (Monte Carlo), randomizuotos heuristikos (randomized heuristics) ir "gobšios" heuristikos (greedy heuristics) vardais. Plačiau uždavinys ir jo sprendimo metodai aprašytas [2] knygoje.

Šis uždavinys aprendžiamas GMJ paketo kontekste. Plačiau apie jį galite sužinoti GMJ sistemos vartotojo ir programuotojo vadove. Metodo parinkimo funkcijos (sprendimo funkcijos) sudarymo metodika pateikta [1] knygoje.

Žemiau pateiktas šio uždavinio konfigūravimo langas:

Savybių (Property) laukuose reikia nurodyti svorio apribojimą (Total Weight), kurio ribos yra tarp 10 ir 10000 ir duomenų failo URL (URL of data file). Atkreipkite dėmesį, kad duomenų failas turi būti tame pačiame serveryje iš kur buvo paleistas paketas. Jei svoris ar URL yra nurodyti neteisingai, lauko fonas pasikeičia į raudoną.

Matavimų (Dimensions) laukuose, reikia nurodyti sprendimo funkcijos taškų kitimo ribas ir pirmojo taško reikšmę.

Duomenų failas turi būtinai tenkinti tokius reikalavimus:

Pimoje eilutėje yra stulpelių pavadinimai;
Visose kitose eilutėse atskirti vienas nuo kito tarpais ar tabuliacijos simboliu turi būti tokie laukai:
- Objekto svoris (double),
- Objekto kaina (double),
- Objektų kiekis (integer),
- Objekto pavadinimas (string);
Failo gale neturi būti tuščių eilučių.

Buvo atlikti bandymai su realiais parduotuvės "Norveda", prekiaujančios firminiais "HITACHI" elektriniais įrankiais, duomenimis. Varijuojant metodais, iteracijų skaičiais ir maksimaliu "kuprinės" svoriu gauti sekantys rezultatai:

Metodas	Iteracijų skaicius	Maksimalus svoris	Itercijos nr.	Funkcijos reikšmė	MonteCarlo	Randomized Heuristics	Greedy Heurictics
Mig1	1000	100	535	-66790	1,23	9,297	1,641
			854	-65920	2,576	9,548	8,733
			907	-65660	1,605	9,211	7,882
		1000	932	-488650	0,038	5,4	2,059
			735	-495230	0,047	3,296	0,445
			342	-488710	0,367	9,478	2,953
	500	100	152	-68940	1,237	9,533	6,913
			276	-66340	0,419	9,482	4,172
			269	-70360	4,334	9,528	5,683
		1000	463	-493640	0,103	7,129	1,504
			201	-487240	1,205	5,844	0,093
			439	-483170	2,542	6,819	0,634
Bayes	1000	100	851	-67640	2,731	8,574	9,539
			514	-65090	0,082	5,091	8,761
			595	-67490	1,265	9,508	2,819
		1000	741	-498850	0,473	9,947	0,644
			906	-504300	0,008	7,536	3,259
			949	-505170	0,073	8,612	0,198
	500	100	408	-65850	5,089	7,438	6,707
			213	-66890	0,018	8,213	5,339
			438	-66340	1,244	8,521	8,446
		1000	253	-495000	0,373	8,679	4,233
			37	-499860	0,417	5,745	0,239
			187	-502260	0,012	7,656	1,138

Pagal šiuos rezultatus galima daryti išvadą, kad tikimybiniu požiūriu sekančio objekto paėmimo strategijos pagal naudingumą yra issidėsčiusios tokia tvarka: Randomized Heuristics, Greedy Heuristics, Monte Carlo.

Kitos išvados:

Skaičiavimų iteracijų skaičių galima sumažinti iki 300 nes toliau funkcijos reikšmė pagerėja ne daugiau 3%.
Jei užduotas bendras svoris viršija visų objektų svorį, sprendimo funkcijos taško koordinatės pasiskirsto panašiai taip: 7:7:0.1. Tai paaiškinama tuo, kad patogiau yra imti visus daiktus iš eilės nesirenkant, nei ieškant geriausio.
Jei užduotas bendras svoris labai mažas (10 kg.), sprendimo funkcijos taško koordinatės pasiskirsto visiškai atsitiktinai ir su gana dideliais skirtumais. Taip matyt yra dėl optimizavimo funkcijos įpatumų. Tačiau geriausias rezultatas pasiekiamas, kai koordinačių pasiskirstymas yra panašiai: 1:1:4. Taip ir turėtų būti, nes imama nedaug objektų, todėl dažniausiai geriausia imti daiktą su didžiausia heuristika.

Literatūra: ( ftp://optimum.mii.lt/pub , ftp://pit.ktu.lt/pub/optimum )

Jonas Mockus, Baysian Heuristic Approach to Discrete and Global Optimization,195-199 psl. (book.ps)
Jonas Mockus, A Set of Examples of Global and Discrete Optimization..., 54-56 psl. (stud.ps)