Problemos aktualumas ir tyrimų būklė pasaulyje ir Lietuvoje

Globaliojo optimizavimo algoritmai

Daug inžinerijos, fizikos, ekonomikos ir kitų sričių uždavinių gali būti sprendžiami kaip globaliojo optimizavimo uždaviniai. Matematiškai toks uždavinys formuluojamas kaip daugiamatės netiesinės tolydžiųjų kintamųjų funkcijos optimizavimas leistinoje srityje, kai nedaroma prielaida, kad funkcija yra unimodali, t.y. turinti tik vieną minimumą.

Kartais tikslo funkcija gali būti išreikšta analitiškai, ar netgi analitiškai išspredžiamas optimizavimo uždavinys. Tačiau praktinių uždavinių  tikslo funkcijos reikšmės paprastai būna apskaičiuojamos kompiuterinėmis programomis, kuriose sudėtingos sistemos modeliuojamos skaitiniais metodais. Tokiu atveju tikslo funkcijos savybes nustatyti sunku. Laikoma, kad tikslo funkcijos reikšmes suformuoja „juodoji dėžė“ – tikslo funkcijos kintamųjų (argumentų) reikšmės patenka į juodosios dėžės įėjimus, o jas naudodama juodoji dėžė suformuoja išėjimo reikšmę, kuri yra tikslo funkcijos reikšmė esant duotoms funkcijos kintamųjų reikšmėms. Esant tokiai situacijai daugelis detaliai teoriškai ištirtų globaliojo optimizavimo metodų (Törn, Žilinskas, 1989, Horst, Pardalos, Thoai, 2001) negali būti naudojami, pavyzdžiui intervalų aritmetika negali būti naudojama tikslo funkcijos rėžių nustatymui. Šiame projekte sudėtingų sistemų optimizavimui siekiama pritaikyti euristinius (Žilinskas, 2002), statistinius (Zhigljavsky, Žilinskas, 2007) ir hibridinius globaliojo optimizavimo algoritmus, realizuotus naudojant šakų ir rėžių metodą.

Globaliojo optimizavimo algortimų efektyvumui gerinti dažnai naudojamos lokaliosios paieškos perspektyviose srityse. Efektyvių netiesinio programavimo metodų panaudojimas lokaliajai paieškai „juodosios dėžės“ situacijoje nėra galimas dėl nežinomų tikslo funkcijos išvestinių ir ypač brangaus jų įvertinimo baigtiniais skirtumais. Dėl to tokiam tikslui naudojami lokaliosios paieškos algoritmai be išvestinių (Conn ir kiti, 1997). Viena iš žinomų tiesioginės paieškos be išvestinių algoritmus realizuojančių bibliotekų yra APPSPACK (Kolda, 2005). Nėra žinoma, kaip lokaliosios paieškos efektyvumas įtakoja globaliąją paiešką, pavyzdžiui ne visada globaliai tikslinga rasti lokaliojo optimumo taškus su dideliu tikslumu, nes tik globaliojo optimumo taškai yra svarbūs. Tai yra svarbu ištirti sprendžiant sudėtingų sistemų optimizavimo uždavinius.

Didelio našumo skaičiavimai ir grid technologijos globaliajam optimizavimui

Globaliojo optimizavimo uždaviniai yra sudėtingi algoritmų sudėtingumo teorijos prasme. Praktiniams uždaviniams spręsti reikia atlikti daug skaičiavimų. Sprendimo trukmė labai priklauso nuo uždavinio dimensijos. Visada yra didelių, šiuolaikiniais kompiuteriais neišsprendžiamų, praktinių uždavinių. Kai įprastų kompiuterių skaičiavimo pajėgumo neužtenka, gali padėti lygiagretieji didelio našumo kompiuteriai, kompiuterių klasteriai, GRID technologija sujungti kompiuteriai ir klasteriai. Tokioms technologijoms pritaikyti algoritmai gali būti plačiau taikomi – jais galima išspręsti didesnius praktinius uždavinius. Dėl to globaliojo optimizavimo algoritmų pritaikymas tokioms technologijoms yra labai aktualus.

Yra keletas žinomų priemonių šakų ir rėžių algoritmų  realizavimui didelio našumo skaičiavimo kompiuteriuose ir kompiuterių  klasteriuose, pavyzdžiui BOB (Le Cun, Roucairol, 1995), PICO (Eckstein ir kiti, 2000), PPBB (Tschoke, Polzer, 1996), PUBB (Shianno, Fujier, 1996). R. Čiegio grupėje sukurti dviejų svarbių algoritmų klasių šablonai, leidžiantys automatizuoti algoritmų lygiagretinimo procesą: tai „Šeimininkas–darbininkai“ ir pradinis „Šakų ir rėžių“ klasės algoritmų šablonai. Pastebėsime, kad šie šablonai yra labai efektyvūs ir plačiai naudojami net ir sudarant nuosekliuosius algoritmus. Duomenų lygiagretumo algoritmų sudarymui skirtas trečiasis įrankis – lygiagrečiųjų masyvų C++ biblioteka ParSol. Sukurti nauji skaičiavimo matematikos objektai – nuoseklieji ir lygiagretieji masyvai, vektoriai ir matricos. Ši biblioteka realizuota naudojant objektinio programavimo ir „Expressions templates“ technologiją.

Šablonų naudojimas programavime yra labai vertingas, kai realizuojame lygiagrečiuosius algoritmus. Šį metodą savo disertacijoje pasiūlė M. Cole (1989). Pagrindinė metodo idėja yra tai, kad šablone realizuojame bendrąją algoritmo struktūrą ir metodus, kurie daug kartų naudojami sprendžiant įvairius uždavinius. Čia kalbame apie algoritminius šablonus (skeleton-like templates), skirtingai nuo duomenų tipo šablonų, kurie apibrėžiami objektinio programavimo kalbose.

Šakų ir rėžių algoritmams bendrąją dalį sudaro srities dalijimas, apatinių ir viršutinių įverčių duotojoje srityje konstravimas, naujos srities parinkimo metodai. Jie realizuojami specialių šablonų forma. Ypatingai svarbią tokio įrankio dalį sudaro lygiagrečiųjų šakų ir rėžių algoritmų šablonų konstravimas.

Šiuo metu vyksta kokybiniai pokyčiai mikroprocesorių arhcitektūroje. Visuose kompiuterių segmentuose (asmeniniai kompiuteriai, darbo stotys, serveriai) pradedami naudoti kelių branduolių mikroprocesoriai. Kaip tik ši naujovė ir garantuos artimiausią dešimtmetį Moore dėsnio numatytą tendenciją, kad skaičiavimų sparta padidėja dvigubai kas 18 mėnesių. Prognozuojama, kad dabar maždaug tokiu greičiu didės branduolių skaičius mikroprocesoriuje. Todėl lygiagretusis programavimas, naujos tokio programavimo technologijos tampa vienu iš svarbiausių informacinių technologijų iššūkiu. Sudėtingų sistemų modeliavime reikia kurti modeliavimo įrankius, kurie gali būti vykdomi labai įvairios architektūros kompiuteriuose. Universalus įrankis turi efektyviai veikti paskirstytų resursų klasteriuose, kai kiekvieną mikroprocesorių sudaro dešimtys branduolių, taip pat gali būti naudojami heterogeniniai tinklyno (grid) resursai.

Savo projekte mes remiamės paradigma, pasiūlyta garsiajame Berkelio universiteto mokslininkų pranešime (Asanovic ir kiti, 2006). Jie apibrėžė pagrindines uždavinių klases, kurių lygiagretinimo struktūra yra panaši ir kurie bus svarbūs bent jau artimiausią dešimtmetį. Tada nauji šiuolaikiniai modeliavimo įrankiai turėtų būti orientuojami į vieną iš šių klasių. Be to, išnagrinėję kelis konkrečius vienos klasės algoritmus, galime prognozuoti lygiagrečiųjų kompiuterių architektūros efektyvumą tokios klasės uždavinių sprendimui. Šakų ir rėžių algoritmai yra išskirti į atskirą uždavinių klasę, kartu su dinaminio programavimo algoritmais.

Mes siūlome naujus globaliojo optimizavimo algoritmus, tinkamus juodosios dėžės uždavinių sprendimui. Jie remiasi šakų ir rėžių metodu ir realizuojami naudojant šablonų biblioteką. Sukurta paprasčiausia lygiagrečiojo šablono versija, kuri leido automatškai generuoti lygiagretųjį algoritmą, kai turime nuosekliąją algoritmo versiją. Šablonas kuriamas naudojant objektinio programavimo technologiją, taigi jis nesunkiai išplečiamas ir gali būti perkeltas į įvairias skaičiavimo terpes. Mūsų nuomone šiai uždavinių klasei neegzistuoja garantuotų receptų, leidžiančių bet kokiam uždaviniui parinkti optimalų algoritmo parametrų ir taisyklių rinkinį. Tokia situacija tipiška, kai modeliuojame realias sudėtingas sistemas, apie kurias turime tik dalinę informaciją (juodosios dėžės principas). Todėl labai svarbu garantuoti, kad įrankio vartotojas galėtų modifikuoti pagrindinius algoritmus (pasirinkti įvairius taisyklių rinkinius ir apibrėžti savo metodus, pvz. srities rėžio skaičiavimo taisyklę ar sričių perrinkimo tvarką) arba panaudoti specialią informaciją (pvz. specializuotą lokaliosios paieškos metodą). Lygindami siūlomą įrankį su jau egzistuojančiais Šakų ir rėžių algoritmų šablonais ir bibliotekomis, pastebėsime, kad jie visi apibrėžia pagrindinius algoritmo metodus. Pagrindiniai skirtumai atsiranda naudojamose technologijose ir realizuotų metodų skaičiuje. Tai ypač svarbu, kai kalbame apie lygiagrečiųjų algoritmų šablonus. Pasikeitus lygiagrečiųjų kompiuterių architektūrai ir programavimo technologijoms, senesnieji įrankiai tapo neefktyviais, taip pat būtina realizuoti naujus algoritmų teorijos pasiekimus ir iš karto numatyti galimybę įrankį vystyti, atsižvelgiant į tolimesnes kompiuterių architektūros tendencijas, bei algoritmų teorijos pasiekimus.

Sijynų  optimizavimo uždaviniai

Iki šiol nėra programinės įrangos pamatų sijynų schemoms optimizuoti. Esamos analizės ir projektavimo programos šiems statybos inžinerijos optimizavimo uždaviniams netinka. Bandyta optimizuoti sijynų  schemas variantinių skaičiavimų pagrindu („Matrix Software“ įdiegta technologija) bei lokaliosios optimizacijos metodais, tačiau ir ši technologija pasirodė esanti nepakankama sudėtingų sijynų atveju. Ši lokaliosios optimizacijos technologija apima mūsų baigtinių elementų programą sijynams analizuoti ir jų jautrumui skaičiuoti (FEPG), lokaliosios optimizacijos sprendiką ir sąsają su analizės ir projektavimo paketu „MatrixFrame“ (kuriamas ir platinamas „Matrix Software“, Nyderlandai ir „Matrix Software Baltic“, Lietuva). Sukaupta praktinė technologijos naudojimo patirtis parodė, kad polių išdėstymo po sijynais uždavinys yra stipriai netiesinis, daugiaekstremis ir itin jautrus polių pozicijų pokyčiams uždavinys. Nėra jokio visiškai patikimo būdo globaliajam sprendiniui gauti. Iš kitos pusės, globaliosios optimizacijos metodai reikalauja milžiniškų kompiuterio išteklių ir specializuotų efektyvių algoritmų. Neseni mūsų rezultatai rodo, kad viena galimų išeičių – lygiagrečiųjų globaliosios optimizacijos algoritmų taikymas kompiuterių klasteriuose.

Perdangų  laikančiųjų konstrukcijų optimizavimas

Strypinių  struktūrų topologijos uždaviniai yra sprendžiami iš esmės dviem skirtingais būdais: pradedant nuo kontinualios struktūros ir, vienaip ar kitaip išimant medžiagą iš tam tikrų  kontinuumo dalių, išgryninama struktūros diskretinė schema (M. Bendsoe ir N. Kikuchi mokyklų darbai; išleistos ir tyrimų rezultatus apibendrinančios monografijos). Dažniausiai taikomi gradientiniai optimizacijos metodai. Kitas būdas – tam tikrais sumetimais į kontinuumą įvedus mazgų rinkinį, jie jungiami visais įmanomais variantais ir pasirinktų kriterijų netenkinantys strypai šalinami (J. Arora, F. Kocer ir jų mokinių darbai). Dažniausiai taikomi genetiniai algoritmai. Abiem atvejais turimas topologijos optimizavimo uždavinys; o jei antrame būde dar keisti mazgų skaičių ir jų padėtis – kartu ir geometrijos optimizavimo uždavinys.

Abiem atvejais erdviniams strypinių sistemų optimizavimo uždaviniams iki šiol nėra patikimų technologijų ir programinių įrankių, kuriuos būtų galima taikyti inžinerinėje praktikoje.