Optimization procedures for topological tasks/Apie optimizavimo proceduras topologiniuose uzdaviniuose.

Skeivalas, Jonas

1. Ivadas

Lietuvos nekilnojamojo turto kadastro zemelapiai sudaromi pagal valstybine koordinaciu sistema LKS 94. Kadangi kartografiniai duomenys skirtingos kokybes, zemes sklypu ribas zymintys taskai yra nevienodo tikslumo, nes zenklinami nuo skirtingu aukstesnes klases valstybinio geodezinio tinklo tasku. Skirtingais laikotarpiais, skirtingu darbu vykdytoju ir nevienodu tikslumu pazenklintas gretimu zemes sklypu ribas butina derinti ir optimizuoti. Nekilnojamojo turto kadastro zemelapiu sudarymo metodika reglamentuoja atitinkami Lietuvos Respublikos Vyriausybes nuostatai (Lietuvos Respublikos... 2002). Taigi atsiranda teorine ir praktine zemes sklypu ribu kadastro zemelapiuose bei kitose ukio srityse optimizavimo problema, kuria mokslo straipsniuose bandoma spresti taikant topologijos metodus bei genetinius algoritmus (Jonauskiene et al. 2011; Goldberg 1989; Shu-Guang 2008).

Optimizavimo uzdaviniuose taikant optimizavimo funkcijas tokiu funkciju minimumo egzistavimas is anksto nera numatomas, o genetinis algoritmas, spresdamas uzdavini iteraciniais metodais, nustato parametru reiksmes su kiek galima maziausiais nuokrypiais nuo nominaliuju verciu. Straipsnyje pateikiami metodai, kuriais taikant nustatoma, kad egzistuoja optimizavimo funkciju minimumas.

2. Teoriniu prielaidu analize

Nagrinesime teorini ir praktini atveji, kai atliekant fizinio proceso optimizavima taikomos funkcijos minimumo salyga neegzistuoja. Tai gali buti tiesiniu ar netiesiniu funkciju variantai, pvz., sprendziant optimizavimo problema zemes sklypu kadastriniuose zemelapiuose, kai optimizavimo salyga (Jonauskiene et al. 2011) yra

F = [summation](P - P') = [summation][increment of P] [right arrow] min, (1)

cia P-kadastriniu matavimu metu nustatyti sklypu plotai; P'-optimizuotieji plotai.

Zemes sklypu plotai nustatomi pagal ribozenkliu koordinates, taikant formules (Skeivalas, Alekniene 2004):

P = [1/2] [n.summation over (i=1)] [x.sub.i]([y.sub.i+1] - [y.sub.i-1]) = [1/2] [X.sup.T] [increment of [bar.Y]], (2)

arba P = [1/2] [n.summation over (i=1)] [y.sub.i]([x.sub.i-1] - [x.sub.i+1]) = [1/2] [Y.sup.T] [increment of [bar.X]], (3)

cia [x.sub.i], [y.sub.i]-tasku koordinates, X = [([x.sub.1],...,[x.sub.n]).sup.T], Y = [([y.sub.1],...,[y.sub.n]).sup.T], [bar.[increment of X]] = ([bar.[increment of [x.sub.1]]],...,[bar.[increment of [x.sub.n]]])T, [bar.[increment of Y]] = [([bar.[increment of [y.sub.1]]],...,[bar.[increment of [y.sub.n]]]).sup.T].

Optimizavimo procese taikant genetini algoritma, sklypu ribozenkliu koordinates keiciamos taip, kad optimizuotu plotu P' nuokrypiai [increment of P] nuo ismatuotu plotu P butu minimalus bei optimizuotu koordinaciu ir sklypu plotu nuokrypiai nuo ismatuotuju atitiktu norminius reikalavimus (Lietuvos Respublikos... 2002; Nekilnojamojo daikto... 2006).

Parodysime, kad funkcijos (1) min neegzistuoja, ir funkcijos optimizavimas gali buti nustatytas tik tam tikru reiksmiu intervalo. Funkcijos (1) minimumo sprendinys gaunamas is lygciu sistemos, sudarytos nustacius funkcijos F daliniu isvestiniu israiskas pagal visus argumentus, t. y. optimizuotas ploto P' koordinates [x.sub.i], [y.sub.i], jas prilyginus nuliui ir gauta lygciu sistema issprendus. Taigi galima rasyti:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Turime 2n lygciu sistema, kurioje nustatomu argumentu, t. y. optimizuojamu koordinaciu [x.sub.i], [y.sub.i] skaicius taip pat lygus 2n, bei visu lygciu laisvieji nariai lygus nuliui. Taigi lygciu sistema (4) yra homogenine sistema.

Lygciu sistema (4) matricu israiska:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

cia A-koeficientu prie nezinomuju [x.sub.i], [y.sub.i] kvadratine matrica, kai koeficientai yra sveikieji skaiciai, lygus 0, -1 arba + 1.

Homogenine sistema [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] turi sprendini [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], jeigu matrica A yra issigimusioji, t. y. kai jos determinantas det A = 0. Siuo atveju sprendiniu skaicius yra begalinis (Markuze 1990; Drozdov 1972). Sistemos (5) matrica A yra issigimusioji, nes jos det A = 0. Tai rodo salyga [c.sub.1][e.sub.1] +... + [c.sub.2n][e.sub.2n] = 0, kuri tinka esant visoms [c.sub.i] [not equal to] 0. Pastarojoje israiskoje vektoriai [e.sub.i] yra matricos A stulpeliu vektoriai. Matricoje A kiekvieno stulpelio koeficientu suma lygi nuliui, todel matricos A det A = 0.

Atlikus teorine analize akivaizdu, kad vienareiksmis optimizavimo funkcijos (1) minimumas neegzistuoja, nes daliniu isvestiniu lygciu sistemos (4) sprendinys yra nevienareiksmis, t. y. egzistuoja begalinis sprendiniu skaicius. Taikant genetini algoritma galima iteraciniais metodais nustatyti optimizavimo funkcijos parametru reiksmes su kuo maziausiais nuokrypiais nuo nominaliuju reiksmiu.

3. Isvados

Atlikus teorine analize galima teigti:

(1.) Siulomas patikimas teorinis metodas taikomoms optimizavimo funkcijoms tikrinti, ar egzistuoja ju minimumo taskas.

(2.) Parodyta, jog sprendziant kai kuriuos topologinius uzdavinius taikomas genetinis algoritmas iteraciniais metodais nustato optimizavimo funkcijos parametru reiksmes su kuo maziausiais nuokrypiais nuo nominaliuju arba projektiniu reiksmiu.

doi. 10.3846/13921541.2011.645340

Literatura

Drozdov, N. D. 1972. Lineinaja algebra v teoriji uravnivanija izmerenij. Moskva: Nedra. 214 s. (in Russian).

Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimisation and Machine Learning. New York: Addison-Wesley.

Jonauskiene, J.; Zakarevicius, A.; Aksamitauskas, V. C.; Sesok, D. 2011. Genetinio algoritmo taikymas zemes sklypu ribu topologijai optimizuoti nekilnojamojo turto kadastro zemelapyje, Geodesy and Cartography 37(2): 84-90. doi:10.3846/13921541.2011.597097

Lietuvos Respublikos nekilnojamojo turto kadastro nuostatai [Regulations of Real Property Cadastre of the Republic of Lithuania], Valstybes zinios 2002, 41-1539.

Markuze, J. J. 1990. Osnovy uravnitelnych vycislenij. Moskva: Nedra. 240 s. (in Russian).

Nekilnojamojo daikto ribu zymejimo nekilnojamojo turto kadastro zemelapyje ir kadastro zemelapio tikslinimo techniniai reikalavimai [Technical requirements for boundary marking the property objects in the real property cadastral map and revision of cadastral map]. 2006, Valstybes zinios 8-311.

Shu-Guang, Li. 2008. Genetic algorithm for solving dynamic simultaneous route and departure time equilibrium problem, Transport 23(1): 73-77. doi:10.3846/1648-4142.2008.23.73-77

Skeivalas, J.; Alekniene, E. 2004. Koordinaciu matavimo tikslumas, nustatant kadastriniu sklypu plotus, Geodezija ir kartografija [Geodesy and Cartography] 30(3): 71-74. doi:10.1080/13921541.2004.9636645

Jonas SKEIVALAS. Prof. Dr Habil. Vilnius Gediminas Technical University. Dept of Geodesy and Cadastre, Sauletekio al. 11, LT-10223 Vilnius, Lithuania. Ph +370 5 2744 703, Fax +370 5 2744 705, e-mail: jonas.skeivalas@vgtu.lt.

Author of 3 monographs and more than 150 research papers. Participated in many intern conferences and research visits to the Finish Geodetic Institute.

Research interests: processing of measurements with respect to tolerances, adjustment of geodetic networks.

Jonas Skeivalas

Geodezijos ir kadastro katedra, Vilniaus Gedimino technikos universitetas, Sauletekio al. 11, LT-10223 Vilnius, Lietuva

El. pastas jonas.skeivalas@vgtu.lt

Iteikta 2011 10 05; priimta 2011 11 21