Kombinatorinio optimizavimo uždaviniai ir jų sprendimo algoritmai (1)
Pramonėje, komercinėje veikloje ir daugelyje kitų veiklos sričių dažnai keliami uždaviniai, susiję su veiklos efektyvumu. Pavyzdžiui, architektas nori žinoti kaip suprojektuoti gamyklos patalpas, kad atstumai tarp įrenginių būtų kuo mažesni, laivų planuotojas nori suprojektuoti laivo patalpas taip, kad jos būtų kuo efektyviau panaudojamos gabenant krovinius. Telekomunikacijų specialistai nori žinoti kaip siusti signalą kanalais, kad klaidos tikimybė būtų kuo mažesnė. Visuotinio transporto strategai nori žinoti kaip sudaryti autobusų, traukinių tvarkaraščius, kad keleivių pervežimas būtų kuo efektyvesnis. Taip pat gamyklose labai svarbu paskirstyti operacijas laike taip, kad bendras gamybos laikas būtų kuo mažesnis, nes papildomas gamybos laikas reiškia bereikalingas papildomas sąnaudas (1 pav.). Šviesoforų signalų sinchronizacija, taip pat įvairiu kitų srautų valdymas ir daugybė kitokių gyvenimiškų uždavinių.
Prisijunk prie technologijos.lt komandos!
Laisvas grafikas, uždarbis, daug įdomių veiklų. Patirtis nebūtina, reikia tik entuziazmo.
Sudomino? Užpildyk šią anketą!
Pastaba. Mūsų Visatos amžius yra 1,3×1010 metų arba 1,8×1016 sekundžių arba 1,8×1025 nanosekundžių.
Kombinatorinis optimizavimas – palyginus su kitomis jauna matematikos atšaka. Išsivysčiusi XX a. antroje pusėje kartu su skaičiuojamosios technikos raida ir sparčiai besivystanti iki šių dienų. Lietuvoje dar mažai paplitusi, tačiau jau žengianti pirmuosius žingsnius.
Visus kombinatorinio optimizavimo uždavinių sprendimo metodus - algoritmus galima būtų suskirstyti į tris pagrindines grupes: tiksliuosius, euristinius ir metaeuristinius (2 pav.).
Tikslieji algoritmai garantuoja uždavinio optimalaus sprendinio radimą. Tačiau bendru atveju beveik visų kombinatorinio optimizavimo uždavinių, tiksliųjų sprendimo algoritmų vykdymo laikas auga eksponentiškai, didėjant uždavinio apimčiai (žr. 1 lentelę). Euristiniu laikomas toks optimizavimo uždavinio sprendimo metodas, kuriuo siekiama rasti aukštos kokybės, bet nebūtinai optimalų sprendinį per priimtiną skaičiavimų laiką. Tai yra pagrindinis euristinių algoritmų skirtumas nuo anksčiau minėtų tiksliųjų metodų. Šios rūšies algoritmai remiasi tam tikrų taisyklių, kurios vadinamos euristikomis, pritaikymu sprendžiant konkretų kombinatorinio optimizavimo uždavinį. Tokios taisyklės šiuo atveju nurodo sprendimą, kurį reikia priimti konkrečiose situacijose, o šio sprendimo pasirinkimas gali padėti gauti geresnį sprendinį. Euristiniai algoritmai yra pritaikomi tik tam tikriems konkretiems uždaviniams su tam tikrais apribojimais ar prielaidomis. Metaeuristinius metodus apibrėžiame kaip tam tikro aukšto abstrakcijos lygio nurodymų rinkinius. Priešingai nei euristinių algoritmų, tokių nurodymų paskirtis yra formaliai aprašyti kurios nors klasės uždavinių sprendimo idėją, principą. Taigi, sąvoka „metaeuristinis algoritmas“ yra talpesnė nei „euristinis metodas“. Kombinatorinio optimizavimo uždaviniams spręsti naudojami šie metaeuristiniai algoritmai: lokalioji paieška, iteratyvioji lokalioji paieška, tabu paieška, genetiniai algoritmai, godžiosios randomizuotos adaptyvios paieškos procedūros (GRASP), atkaitinimo modeliavimas, skruzdėlių kolonijų elgsenos imitavimo algoritma, paieška kintamose aplinkose, bičių kolonijų elgsenos imitavimo algoritmai ir kt. (3 pav.)Įvairių optimizavimo uždavinių sprendimo algoritmuose galima pritaikyti praktiškai visų minėtų metaeuristinių nurodymų idėjas. Tai būtų pagrindinis metaeuristinių metodų pranašumas prieš kokiam nors vienam konkrečiam uždaviniui spręsti tinkamus euristinius algoritmus. Norint rasti geresnės kokybės sprendinius, dėl metaeuristinių metodų universalumo, dažnai galime apjungti kelių skirtingų rūšių metaeuristinių algoritmų idėjas. Todėl šiuo metu metaeuristiniai algoritmai ir įvairios jų ir kelių metaeuristinių metodų idėjų kombinacijos, pavyzdžiui genetiniai algortimai ir lokalioji paieška, tabu paieška ir atkaitinimo modeliavimas ir kt., yra pagrindiniai tyrinėjimų objektai, kuriais siekiama sukurti algoritmus, kuo efektyviau sprendžiančius kombinatorinio optimizavimo uždavinius, t.y. per tam tikrą skaičiavimų laiką gauti optimalius ar jiems artimus sprendinius.
Matematikos ir gamtos mokslų fakulteto (buvusio Fundamentaliųjų mokslų fakulteto)
Taikomosios matematikos katedros
doc. Narimantas Listopadskis