Oznaka poročila: ARRS-RPROJ-ZP-2010-1/122 ZAKLJUČNO POROČILO O REZULTATIH RAZISKOVALNEGA PROJEKTA A. PODATKI O RAZISKOVALNEM PROJEKTU 1. Osnovni podatki o raziskovalnem projektu Šifra projekta Z2-1246 Naslov projekta Optimizacija pakiranja, natovarjanja in prevoza elementov montažnih objektov Vodja projekta 22314 Peter Korošec Tip projekta Zt Podoktorski projekt - temeljni Obseg raziskovalnih ur 3.400 Cenovni razred B Trajanje projekta 02.2008 - 01.2010 Nosilna raziskovalna organizacija 106 Institut "Jožef Stefan" Raziskovalne organizacije - soizvajalke Družbeno- ekonomski cilj 13. Splošni napredek znanja - RiR financiran iz drugih virov (ne iz splošnih univerzitetnih fondov - SUF) 2. Sofinancerji1 1. Naziv Naslov 2. Naziv Naslov 3. Naziv Naslov B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROJEKTA 3. Poročilo o realizaciji programa raziskovalnega projekta2 Raziskovalna hipoteza V današnjem svetu je tempo življenja vedno hitrejši in s tem tudi hitrost napredka. Zatorej je tudi želja po doseganju čim boljših rezultatov v čim krajšem času vedno večja. Iz tega razloga prihaja računalništvo v industriji do vedno večje veljave. Razvoj računalnikov je primarno usmerjen v večjedrne in porazdeljene sisteme, ki omogočajo večjo računalniško moč, vendar pod pogojem, da imamo ustrezno programsko okolje, ki zna vso to moč tudi izkoristiti. Odločili smo se, da bomo izbrali kvalitetni zaporedni optimizacijski algoritem, ki ima inherentne^ paralelizacijske lastnosti in en težak problem razvrščanja montažnih objektov. Želja je bila, hitro in učinkovito rešiti ta problem, tako, da bi čim bolj izkoristili najmodernejšo računalniško opremo. Opis raziskav Raziskave so potekale na dveh področjih in sicer na razvoju vzporednega optimizacijskega algoritma, ki nam bo omogočil izkoristiti ves računalniški potencial ter na področju implementacije simulatorja izbranega problema. Pri razvoju vzporednega optimizacijskega algoritma smo se najprej osredotočili na pregled algoritmov in njihove kvalitete. Ugotovili smo, da ima »Diferencialni pristop s stigmergijo mravelj« vse potrebne kvalitete in smo ga kot takega tudi izbrali za nadaljnji razvoj. Seveda smo sam algoritem predhodno dodobra preizkusili tako na testnih problemih, kot na različnih realnih problemih. Ker obstaja kar nekaj splošnih pristopov k izvedbi vzporedne verzije algoritma, smo se odločili za usposabljanje v tujini, kjer sem lahko v kratkem času izvedel največ informacij potrebnih za samo realizacijo. Tromesečno usposabljanje je potekalo na Univerzi v Salzburgu, Odseku za računalništvo, v Avstriji (orig. Universität Salzburg, Fachbereich Computerwissenschaften). Na omenjeno univerzo sem odšel na povabilo prof. dr. Mariana Vajteršica, s katerim sem sodeloval že v času doktorskega študija. Glavni namen obiska je bilo sodelovanje v okviru preliminarnih raziskav na paralelizaciji hevrističnih optimizacijskih algoritmov. Izkazalo se je, da sem v tem času uspešno opravil paralelizacijo izbranega metahevirstičnega optimizacijskega algoritma. Seznanjen sem bil z dvema osnovnima pristopoma k paralelizaciji algoritmov; z deljenim in ločenim pomnilnikom. Eksperimentalno delo sem opravil na visoko zmogljivi računalniški gruči, ki mi je omogočala testiranje tako vzporednih (deljen pomnilnik) kot porazdeljenih (ločen pomnilnik) rešitev. Zaradi izjemnih rezultatov sem imel ob koncu mojega obiska tudi vabljeno predavanje z naslovom "Numerical Optimization with Parallelized Ant Colony Approach", kjer sem predstavil moje dosedanje delo, vključno z rezultati paralelizacije, ki sem jo opravil v času usposabljanja. Rezultat resnično uspešnega sodelovanja je članek z naslovom »A shared-memory and distributed-memory ant-stigmergy algorithm for numerical optimization«, ki je bil poslan v SCI revijo »Parallel Computing«. S samim raziskovanjem tematike paralelizacije sem nadaljeval tudi po končanem usposabljanju, ki je pripeljalo do več mednarodnih objav. Skozi ves čas razvoja algoritma smo imeli v mislih tudi dve implementaciji, ki bi lahko pripeljali do še hitrejšega izvajanja algoritma. To sta implementacija v FPGA in grafičnem okolju. Pri prvem je značilno, da lahko poljubno računalniško kodo realiziramo s strojno opremo, s čimer lahko bistveno pohitrimo samo delovanje. Pri drugem, pa lahko izkoristimo izredno računalniško moč najsodobnejših grafičnih procesorjev. Današnji grafični procesorji imajo do 1,600 jeder, kar bi omogočilo velike pohitritve za zelo majhno ceno. Razviti algoritmi so temu primerno realizirani in jih je potrebno le še prevesti v ustrezno obliko, ki bo omogočala samo izvajanje na omenjenih napravah. Drugo področje tega projekta je bila definicija in sama implementacija 3D simulatorja. Problem sam še nikoli ni bil v taki obliki raziskan in zato ga je bilo potrebno definirati ter implementirati. V sodelovanju s podjetjema Trimo d.d. in Domel d.d. smo definirali problem, ki temelji na njihovih realnih potrebah pri prevozu izdelkov različnih oblik. Tako smo npr. simulirali nalaganje na prevozno sredstvo s pomočjo OpenGl tehnologije in s tem omogočili tudi vizualni vpogled v samo dogajanje. Pri izvedbi simulatorja smo posebno pozornost namenili detekciji trkov in upoštevanju težišča pri nalaganju izdelkov različnih oblik. Pri preizkusih smo uporabljali le osnovne geometrijske like kot so kocka, kvader, piramida, valj, stožec, krogla in upoštevali pri izračunu težišča enotno porazdelitev mase. Seveda v realnem svetu temu ni tako in bomo morali v prihodnje pridobiti realni problem in ga temu primerno reševati. Izkazalo se je, da se sama simulacija v zaporedni obliki izvaja relativno počasi in se kot v prejšnjem primeru ponuja možnost implementacije na grafičnem procesorju, ki bi omogočilo znatno pohitritev izvajanja in s tem reševanja problema. Znotraj tega področja smo se ukvarjali tudi s problemom samega prevoza in učinkovite izrabe prevoznih sredstev, ki so lahko na razpolago. Torej smo iskali najbolj učinkovit način, kako z omejeno količino prevoznih sredstev, pri katerih ne morejo vsa prevažati ves tovor, prepeljati ves tovor iz točke A v točko B kar se da hitro. Tudi s tega področja smo objavili več mednarodnih objav. V nadaljnjem delu vidimo predvsem možnosti implementacije tako optimizacijskega algoritma, kot simulatorja v grafičnem okolju, ki nam nudi veliko računsko moč pri zelo majhnih stroških. Ključne ugotovitve - Izvajanje optimizacijskih algoritmov v vzporedni obliki (bodisi z deljenim ali ločenim pomnilnikom) lahko drastično pohitri optimizacijski postopek. Ob primerni izvedbi, je lahko tudi sama evaluacija rešitve časovno nezahtevna in še vedno dobimo visok faktor pohitritve. Ta pristop je lahko uporabljen na poljubnih numeričnih optimizacijskih problemih. - 3D simulacija realnega načina izvajanja nalaganja je zelo kompleksen problem. Za končno realizacijo bi bilo potrebno natančno določiti zunanje mere vseh izdelkov in še bolj pomembno določiti težiščne točke vseh izdelkov in v nekaterih primerih verjetno celo več »stičnih« točk, ki bi se vse morale dotikati podlage. Le s tem bi lahko zagotovili stabilnost vseh naloženih izdelkov. Na samo težišče seveda vpliva tudi način pakiranja izdelkov, v kolikor imamo opravka s takim načinom prevoza izdelkov. - Optimizacija bodisi v zaporedni ali vzporedni obliki lahko kvalitetno pripomore k izboljšanju nalaganja in prevoza izdelkov. Znanstvena spoznanja - Izbrani algoritem Diferencialni pristop s stigmergijo mravelj je izpolnil vsa pričakovanja pri razširitvi iz zaporednega v vzporedni pristop. Torej so se vsa predvidevanja o potencialih paralelizacije izkazala za resnična. - S prehodom iz zaporedno v vzporedno izvedbo algoritma smo uspeli pri pristopu z deljenem pomnilnikom doseči učinkovitost pohitritve glede na število uporabljenih jeder/procesorjev s preko 80 % izkoristkom (pri osmih procesorjih in časom evaluacije rešitve 42,5 ps), kar je zelo spodbuden rezultat. Če smo število procesorjev zmanjšali ali pa povečali čas evaluacije rešitve, smo se takoj približali linearni pohitritvi. Pri pristopu z ločenim pomnilnikom smo po pričakovanjih dosegli nekoliko slabše rezultate. Npr. pri osmih procesorjih je bil potreben čas evaluacije 0,18 ms, da smo dosegli 55 % učinkovitost. Vendar bi tukaj radi poudarili, da že računsko najpreprostejše evaluacije/simulacije, ki jih srečamo v realnem življenju, potrebujejo nekaj sekund (kot je primer pri trenutni verziji našega simulatorja). V kolikor pa pogledamo simulacije, kjer je potrebno računati kakšne kompleksne postopke, kjer se npr. uporabljajo metode končnih elementov in podobno, pa hitro pridemo do nekaj ur. To nam da zelo drugačen vidik našega rezultata. Naj povemo, da smo že pri času evaluacije 0,71 ms dosegli 80 % izkoristek. S tem smo pokazali, da sta oba pristopa primerna za uporabo pri realnih problemih. - Kljub temu, da je bil čas evaluacije le nekaj sekund, se je izkazalo, da trenutna verzija še ni primerna za realno uporabo. Simulator bo potrebno še nadgraditi tako s kvalitetnega stališča, kot same hitrosti izvajanja. S stališča kvalitete je potrebna nadgradnja za uporabo z objekti, ki nimajo enakomerno razporejene mase ali pa zahtevajo večtočkovni stik s podlago. Glede hitrosti izvajanja, uporaba vzporednega pristopa pri samem optimizacijskem algoritmu vsekakor pomaga, vendar imamo občutek, da bi lahko dodobra izkoristili grafično okolje in njegovo računsko moč za hitrejše ovrednotenje rešitev. Rezultati in učinki raziskovalnega projekta Največ vidnih rezultatov in učinkov se pokaže v obliki objav (najpomembnejše izmed njih so tudi predstavljene v točkah 6. in 7.). Veliko člankov je bilo v tem času poslanih na SCI revije v recenzijo, vendar do tega trenutka še nismo prejeli odgovorov recenzentov. Prav tako bomo kot rezultat uspešnega usposabljanja prijavili mednarodno sodelovanje med Slovenijo in Avstrijo, pri čemer si želimo naše začeto delo tudi nadaljevati. Seveda bodo sami učinki raziskav v realnem življenju, vidni šele v prihodnjih projektih z industrijo, kjer jim bomo lahko zaradi raziskav, narejenih v okviru tega projekta, nudili predvsem hitrejšo in s tem kvalitetnejšo realizacijo različnih optimizacijskih problemov. S tem bomo lahko hitro in kvalitetno pripomogli k njihovi višji konkurenčnosti na svetovnem trgu. 4. Ocena stopnje realizacije zastavljenih raziskovalnih ciljev3 V skladu s projektnim načrtom je bil(a): - uspešno zaključena celotna Faza I, kjer se je opredelil problem in naredila analiza stanja - uspešno zaključena celotna Faza II, kjer se je definiral problem pakiranja in natovarjanja ter izvedel 3D simulator - uspešno zaključena celotna Faza III, kjer so bili izvedeni izbrani metahevristični optimizacijski algoritmi in so bili primerjani na izbranih testnih problemih - opravljena aktivnost iz IV.1, kjer je bil integriran optimizacijski algoritem in 3D simulator v enotno programsko okolje - opravljen del aktivnosti iz IV.2, kjer so bili trenutno dosegljivi podatki le v 2D obliki in jih bo potrebno šele prevesti v ustezno 3D obliko, ki bo omogočala zaznavanje nehomogenosti izdelkov in ustrezne izračune, ki so potrebni pri 3D simulatorju - uspešno opravljena Faza V., pridobivanje specialnih znanj v tujini - opravljena aktivnost iz VI.1 v obliki vzporedne izvedbe optimizacijskega algoritma - opravljen del aktivnosti iz VI.2, kjer se je pripravila vzporedna izvedba optimizacijskega algoritma na prenos v strojno obliko, ni pa še prišlo do samega prenosa, ker smo imeli idejo, da bi celoten optimizator prenesli v strojno obliko. Glede na zastavljene načrte in cilje lahko trdimo, da smo uspeli v večji meri realizirati večino zastavljenih raziskovalnih ciljev, preostali del pa je še v realizaciji. Smo pa nekatere zastavljene načrte tudi presegli, ker smo imeli občutek, da bodo le ti na koncu prinesli večji pomen temu projektu. Tu predvsem mislimo, na bolj intenzivno testiranje tako zaporednih kot vzporednih izvedb algoritmov na različnih realnih problemih, saj smo se želeli prepričati, da bo sam pristop z optimizacijo uporaben tudi v kasnejših projektih. Prav tako smo izvedli dve različici vzporednih optimizacijskih algoritmov in ju temeljito preskusil. 3D simulator je bil izveden tudi v grafični obliki s pomočjo OpenGl tehnologije, kar nam kot razvijalcem in uporabnikom omogoča mnogo boljši pregled nad samim dogajanjem pri optimizaciji in seveda tudi boljšo vizualno oceno rešitve. 5. Utemeljitev morebitnih sprememb programa raziskovalnega projekta4 6. Najpomembnejši znanstveni rezultati projektne skupine5 Znanstveni rezultat 1. Naslov SLO Porazdeljen večnivojski pristop s stigmergijo mravelj uporabljen pri oblikovanju električnega motorja ANG The distributed multilevel ant-stigmergy algorithm used at the electric-motor design Opis SLO Članek predstavlja optimizacijsko metodo uporabljeno pri oblikovanju električnega motorja. Cilj optimizacije je najti vrednosti geometričnih parametrov, ki bi tvorile rotor in stator z minimalnimi izgubami moči. Zaradi časovno potratnega ovrednotenja rešitve je zaporedna oblika algoritma časovno neučinkovita. V ta namen smo razvili novo, učinkovito porazdeljeno izvedbo MASA algoritma. Pokazali smo, da smo s porazdeljenim računanjem drastično zmanjšali čas računanja brez opaznega zmanjšanja kvalitete dobljenih rešitev. ANG This article presents an optimization method used at the electric-motor design. The goal of the optimization was to find the geometrical parameter values that would generate the rotor and the stator geometries with minimum power losses. Due to a time-consuming solution evaluation the sequential algorithm is inefficient in terms of time. For this reason, a new, efficient distributed implementation of the MASA is presented. In addition, we have shown that with distributed computing the computation time can be drastically reduced without any noticeable reduction in the quality of the solution. Objavljeno v KOROŠEC, Peter, SILC, Jurij. The distributed multilevel ant-stigmergy algorithm used at the electric-motor design. Eng. appl. artif. intell. [Print ed.], 2008, vol. 21, no. 6, 941-951, JCR IF (2008): 1,397. Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 21585191 2. Naslov SLO Uporaba stigmergije za reševanje numeričnih optimizacijskih problemov ANG Using stigmergy to solve numerical optimization problems Opis SLO V tem članku predlagamo obetaven optimizacijski algoritem imenovan, Večnivojski pristop s stigmergijo mravelj (MASA), ki izkorišča stigmergijo za optimizacijo večparametrskih funkcij. Učinkovitost algoritma smo ocenili v primerjavi z diferencialno evolucijo, ki je ena izmed vodilnih stohastičnih metod za numerično optimizacijo, pri reševanju numeričnih optimizacijskih problemov. Primerjava je izvedena z uporabo nekaj pogosto uporabljenih testnih funkcij z dodanim šumom. ANG In this paper we propose a promising optimization algorithm, referred to as the Multilevel Ant Stigmergy Algorithm (MASA), which exploits stigmergy in order to optimize multi-parameter functions. We evaluate the performance of the MASA and Differential Evolution - one of the leading stochastic method for numerical optimization - in terms of their applicability as numerical optimization techniques. The comparison is performed using several widely used benchmark functions with added noise. Objavljeno v KOROŠEC, Peter, SILC, Jurij. Using stigmergy to solve numerical optimization problems. Comput. inform., 2008, vol. 27, no. 3, 377-402, JCR IF (2008): 0,492. Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 21826087 3. Naslov SLO Visoko dimenzijska optimizacija realnih parametrov z uporabo diferencialnega pristopa s stigmergijo mravelj ANG High-dimensional real-parameter optimization using the differential ant- stigmergy algorithm Opis SLO V članku je predstavljen algoritem, Diferencialni pristop s stigmergijo mravelj (DASA), za globalno optimizacijo visoko dimenzijskih cenovnih funkcij z zveznimi parametri. DASA je prekosil primerjani diferencialno evolucijski algoritem v konvergenci na vseh testnih funkcijah in pridobil tudi boljše rešitve na nekaterih izmed njih. Izkazalo se je, da DASA lahko uporabimo pri zahtevnih optimizacijskih problemih v realnem življenju. DASA je eden od prvih ACO algoritmov, ki je predlagan za globalno optimizacijo visoko dimenzionalnih problemov z zveznimi parametri. ANG The purpose of this paper is to present an algorithm, called Differential Ant- Stigmergy Algorithm (DASA), for global optimization of high-dimensional real-parameter cost functions. The DASA outperformed the included differential evolution type algorithm in convergence on all test functions and also obtained better solutions on some test functions. The DASA may find applications in challenging real-life optimization. The DASA is one of the first ACO-based algorithms proposed for global optimization of the high- dimensional real-parameter problems. Objavljeno v KOROŠEC, Peter, SILC, Jurij. High-dimensional real-parameter optimization using the differential ant-stigmergy algorithm. Int. j. intell. comput. cybern. (Print), 2009, vol. 2, no. 1, 34-51. Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 22592039 4. Naslov SLO Na stigmergiji temelječ algoritem za zvezno optimizacijo preverjen v simuliranem realnem okolju ANG A stigmergy-based algorithm for continuous optimization tested on real-life- like enviornment Opis SLO Članek predstavlja rešitev, kako globalno optimirati zvezne funkcije z uporabo Diferencialnega pristopa s stigmergijo mravelj (DASA). Uporabljen je pri optimizaciji z zveznimi parametri, veliko dimenzijami ter majhnim številom ovrednotenj funkcije. Uspešnost DASA je ocenjena na nizu 25-ih testnih funkcij, ki so bile uporabljene na CEC'2005 specialni sekciji o optimizaciji z zveznimi parametri. Poleg tega je ne-parametrična statistična primerjava z enajstimi trenutnimi vrhunskimi algoritmi pokazala uspešnost in učinkovitost DASA. ANG This paper presents a solution to the global optimization of continuous functions by the Differential Ant-Stigmergy Algorithm (DASA). It is applied to the high-dimensional real-parameter optimization with low number of function evaluations. The performance of the DASA is evaluated on the set of 25 benchmark functions provided by CEC'2005 Special Session on Real Parameter Optimization. Furthermore, non-parametric statistical comparisons with eleven state-of-the-art algorithms demonstrate the effectiveness and efficiency of the DASA. Objavljeno v KOROŠEC, Peter, ŠILC, Jurij. A stigmergy-based algorithm for continuous optimization tested on real-life-like enviornment. Lect. notes comput. sci., 2009, vol. 5484, 675-684. Tipologija 1.01 Izvirni znanstveni članek COBISS.SI-ID 22568743 5. Naslov SLO Aplikacija diferencialnega pristopa s kolonijo mravelj na realnih zveznih optimizacijskih problemih ANG Applications of the differential ant-stigmergy algorithm on real-world continuous optimization problems Opis SLO V tem poglavju smo predstavili tako imenovani Diferencialni pristop s stigmergijo mravelj (DASA), ki je nov pristop k problemu optimizacije z zveznimi parametri. Poglavje začnemo z opisom DASA, ki mu sledijo tri študije primerov, ki kažejo uporabo predlaganega pristopa za optimizacijo v realnem svetu. Na koncu sklenemo z razpravo o dobljenih rezultatov. Pokazali smo, da lahko z DASA učinkovito rešujemo različne kompleksne realne optimizacijske probleme. ANG In this chapter we will present so-called Differential Ant-Stigmergy Algorithm (DASA), a new approach to the continuous optimization problem. The chapter starts with the DASA description followed by three case studies which show real-world application of the proposed optimization approach. Finally, we conclude with discussion of the obtained results. We have shown that the DASA is capable of efficiently solving different complex real-world optimization problems. Objavljeno v KOROŠEC, Peter, ŠILC, Jurij. Applications of the differential ant-stigmergy algorithm on real-world continuous optimization problems. V: SANTOS, Wellington Pincheiro dos (ur.). Evolutionary computation. Vukovar: In-Teh, 2009, 199-218. 1.16 Samostojni znanstveni sestavek ali poglavje v monografski Tipologija publikaciji COBISS.SI-ID 23111975 7. Najpomembnejši družbeno-ekonomsko relevantni rezultati projektne skupine6 Družbeno-ekonomsko relevantni rezultat 1. Naslov SLO Metahevristični pristop k problemu razvrščanja nalaganja ANG Metaheuristic approach to loading schedule problem Opis SLO V članku je predstavljena primerjava dveh metahevrističnih pristopov pri reševanju problema razvrščanja nalaganja z omejitvami. Primerjali smo Brez-parametrično evolucijsko iskanje in Pristop s stigmergijo mravelj. Problem nalaganja prevoza je NP-težek in se uporablja v različnih situacijah resničnega življenja z visoko frekvenco nakladanja in razkladanja, kot so skladišča in pristanišča. ANG The paper presents a comparison of two metaheuristic approaches in solving a constrained loading scheduling problem. We compared Parameter-less Evolutionary Search and Ant-Stigmergy Algorithm. The transportation loading problem is NP-hard, and is applicable to different real-life situations with high frequency of loading and unloading operations; like in depots, warehouses and ports. Šifra B.03 Referat na mednarodni znanstveni konferenci Objavljeno v PAPA, Gregor, KOROŠEC, Peter. Metaheuristic approach to loading schedule problem. V: MISTA 2009 : proceedings of the 4th Multidisciplinary International Conference on Scheduling: theory and applications, 10th - 12th August 2009, Dublin, Ireland. [S. l.: s. n.], 2009, 616-626. Tipologija 1.08 Objavljeni znanstveni prispevek na konferenci COBISS.SI-ID 22815015 2. Naslov SLO Razvrščanje prevoza z omejitvami ANG Constrained transportation scheduling Opis SLO V članku je predstavljena primerjava dveh metahevrističnih pristopov pri reševanju problema razvrščanja prevoza z omejitvami. Primerjali smo Brez- parametrično evolucijsko iskanje in Pristop s stigmergijo mravelj pri reševanju problema razporeda. Problem razvrščanja prevoza je NP-težek in se uporablja v različnih situacijah resničnega življenja, kot so skladišča in pristanišča. ANG This paper presents a comparison of two metaheuristic approaches in solving a constrained transportation scheduling problem. We compared Parameter- less Evolutionary Search and Ant Stigmergy Algorithm in solving the schedule optimization problem. The transportation scheduling problem is NP- hard, and is applicable to different real-life situations; like in depots, warehouses and ports. Šifra B.03 Referat na mednarodni znanstveni konferenci Objavljeno v PAPA, Gregor, KOROŠEC, Peter. Constrained transportation scheduling. V: FILIPIČ, Bogdan (ur.), ŠILC, Jurij (ur.). Bioinspired optimization methods and their applications : proceedings of the Third International Conference on Bioinspired Optimization Methods and their Applications, BIOMA 2008, 13-14 October 2008, Ljubljana, Slovenia. Ljubljana: Jožef Stefan Institute, 2008, 141-147. Tipologija 1.08 Objavljeni znanstveni prispevek na konferenci COBISS.SI-ID 22077223 3. Naslov SLO Porazdeljen algoritem, ki temelji na mravljah, za numerično optimizacijo ANG A distributed ant-based algorithm for numerical optimization Opis SLO V članku je predstavljen nov porazdeljen pristop, ki je uporaben za numerične optimizacijske probleme. Pristop temelji na stigmergiji opaženi pri mravljah, kjer posredno usklajevanje med mravljami vodi postopek iskanja v smeri optimalne rešitve. Posredno usklajevanje nudi visoko stopnjo vzporednosti in s tem enostavno porazdeljeno izvajanje. Za komunikacijo med procesi se uporablja MPICH2 knjižnica. Ovrednotenje cenovne funkcije je pomemben del numerične optimizacije in je običajno realiziran kot črna- skrinjica. Zato smo algoritem analizirali glede na čas ovrednotenja. ANG This paper presents a new distributed approach. The approach is based on ant-stigmergy metaheuristics where indirect coordination between ants drives the search procedure towards the optimal solution. Indirect coordination offers a high degree of parallelism and therefore a straightforward implementation. For communication between processes a MPICH2 for Windows library is used. The cost function evaluation is an important part of numerical optimization and is usually realized as black-box simulator. Therefore, an algorithm analysis according to simulator's time complexity is discussed. Šifra B.03 Referat na mednarodni znanstveni konferenci Objavljeno v KOROŠEC, Peter, ŠILC, Jurij. A distributed ant-based algorithm for numerical optimization. V: GMAC'09 ... [et al.]. 2009 ACM/IEEE International Conference on Automatic Computing & co-located Workshops, Barcelona, Spain, June 15-19, 2009. Danvers: ACM, 2009, 37-43. Tipologija 1.08 Objavljeni znanstveni prispevek na konferenci COBISS.SI-ID 22757159 4. Naslov SLO Numerična optimizacija z vzporednim pristopom kolonije mravelj ANG Numerical Optimization with Parallelized Ant Colony Approach Opis SLO V tem vabljenem predavanju sem predstavil nedavno predlagan pristop, ki temelji na koloniji mravelj imenovan, Diferencialni pristop s stigmergijo mravelj. Še več, da bi pospešil izvajanje algoritma, sem razpravljal o vzporednih izvedbah z uporabo Multi-Processing (pristop z deljenim pomnilnikom) in Message Passing Interface (pristop z ločenim pomnilnikom) pristopa. Predavanje sem zaključil z nekaj primeri uporabe v raznih realnih aplikacijah. ANG In this invited talk, a recently proposed Ant-Colony based approach, called Differential Ant Stigmergy Algorithm, was presented. Furthermore, to speed- up the algorithm's execution, a parallelized versions using Multi-Processing (shared memory approach) and Message Passing Interface (distributed memory approach) was discussed. The talk ended with some examples of real-world applications. Šifra B.04 Vabljeno predavanje Objavljeno v KOROŠEC, Peter. Numerical optimization with parallelized ant colony approach : invited talk, Salzburg, Universität Salzburg, Fachbereich Computerwissenschaften, 10 Dec. 2008 Tipologija 3.14 Predavanje na tuji univerzi COBISS.SI-ID 22343463 5. Naslov SLO Zlati znak Jožefa Stefana ANG The Jožef Stefan Golden Emblem Prize Opis SLO Zlati znak Jožefa Stefana se enkrat na leto podeljuje za najbolj odmevna doktorska dela v Sloveniji s področja naravoslovno-matematičnih, tehniških, medicinskih in biotehniških ved. ANG The Jožef Stefan Golden Emblem Prize is once a year granted for the most outstanding contributions made to science in the Doctoral Dissertation in the field of natural sciences in Slovenia Šifra E.01 Domače nagrade Objavljeno v Objavljeno v raznih elektronskih in tiskanih medijih (kot so Delo, interno glasilo IJS Novice, ...). Prav tako je bil izveden intervju za Radio Slovenija. Nobena objava nima COBISS zaznamka. Tipologija 1.22 Intervju COBISS.SI-ID 00000000 8. Drugi pomembni rezultati projetne skupine7 9. Pomen raziskovalnih rezultatov projektne skupine- 9.1. Pomen za razvoj znanosti- SLO_ Metahevristične optimizacijske metode so sodobne metode za reševanje kompleksnih problemov, ki jih ne moremo reševati s klasičnimi pristopi, saj jih bodisi ne znamo fizikalno in matematično opisati ali pa so računsko prezahtevni. Pogosto je njihov prostor rešitev nelinearen in večmodalen. Obravnavane so bile metode, ki se zgledujejo po dveh naravnih pojavih, evoluciji in stigmergiji, in so se v teoriji in praksi že izkazale kot zelo učinkovite za reševanje določenih (NP-težkih) optimizacijskih problemov. Problem pakiranja in natovarjanja se je reševal kot problem splošnega 3D nahrbtnika. To je nov prispevek k znanosti, saj so do sedaj znani le redki poskusi reševanja 3D ortogonalnega nahrbtnika. Prav tako se je razvil 3D simulator, ki omogoča ovrednotenje posameznih rešitev in s tem omogočil razvoj in izbiro primernega optimizacijskega algoritma. S prenosom pridobljenih znanj in izkušenj s področja optimiranja in simulacij v industrijsko okolje se je in še bo prispevalo k razvoju metahevrističnih metod za optimizacijo pakiranja, natovarjanja in prevoza elementov montažnih objektov. Ekstra poudarek je bil dan razvoju in testiranju zaporednih in novo razvitih vzporednih algoritmov na različnih realnih problemih. S tem se je dodatno izpopolnilo tudi samo področje sodobnih metahevrističnih optimizacijskih metod. ANG Metaheuristic optimization methods are modern heuristic methods applicable to complex optimization problems that are difficult or even impossible to be solved by using traditional well-understood approaches for different reasons: either we have not enough knowledge to describe the problem with a mathematical or a physics model, the problem is computationally too complex, or the problem's solution space is too large or highly multimodal. Methods that imitate two natural principles, evolution and stigmergy, whose efficiency have been already proved as very efficient for solving complex, mainly NP-hard, optimization problems, were discussed. The problem of packaging and loading was solved as a general 3D knapsack problem. This was a new contribution to the science, because there are only a few attempts of solving 3D orthogonal knapsack problem. Also a 3D simulator was developed, which was used to simulate individual solutions. This enabled us to develop and evaluate the proper optimization method. With the transfer of gained knowledge and experiences from the field of optimization and simulations into the industrial environment, it will be contributed to the development of metaheuristic methods for optimization of packaging, loading and transportation of pre-fabricated building elements. The extra emphesis was given to the development and testing of sequential and newly developed parallel algorithms on different real-world problems. With this a field of modern metaheuristic optimization methods was additionally improved. 9.2. Pomen za razvoj Slovenije10 SLO_ Optimizator, kot glavni vidni rezultat tega projekta, omogoča podjetjem znižati stroške pakiranja, skladiščenja in transporta. Cena skladiščenja izdelkov in njihovega prevoza od proizvajalca do naročnika se bo pomembno znižala in s tem se bo povečala konkurenčnost podjetja. V splošnem pa smo dobili orodje, ki bo znalo hitro in optimalno umestiti predmete nepravilnih oblik v nek omejen prostor. Kot vemo sta čas in prostor - ne samo za industrijo, temveč tudi za širšo družbo - zelo dragocena in s tem orodjem bomo pripomogli k večjemu izkoristku obeh. Izsledki projekta bodo lahko neposredno uporabni tudi pri reševanju podobnih problemov na področjih natovarjanja ladijskih kontejnerjev (luke), upravljanje letalskega tovora (letališča), natovarjanje palet, upravljanje skladišč ipd. Verjetno še bolj pomembno pa je dejstvo, da smo pridobili znanja in rešitve, ki nam omogočajo izkoriščati najnovejšo tehnologijo. Le ta bodo pripomogla k hitremu in kvalitetnemu reševanju različnih optimizacijskih problemov, ki jih pa v naši družbi in še posebej industriji ne manjka. ANG_ Optimizer, as the main visible result of this project enables companies to lower the costs of packaging, storage and transportation. The price of products storage and their transportation from manufacturer to customer will be significantly decreased and consequently the competitiveness of the company will increase. In general we got a tool, which will be able to quickly and optimally install objects of irregular shapes in some bounded space. As we know, time and space - not only for industry, but for the society in general - are very expensive and with this tool, we will contribute to a greater use of both. The outcome of the project could be directly used at solving similar problems on the fields of container ship loading (harbors), plane cargo management (airports), pallet loading, warehouse management, etc. Probably even more important is the fact that we gained knowledge and solutions, which will enable us to take advantage of new computer technology. They will contribute to fast and quality solving of different optimization problems, which can be found in our society and especially in industry. 10. Samo za aplikativne projekte! Označite, katerega od navedenih ciljev ste si zastavili pri aplikativnem projektu, katere konkretne rezultate ste dosegli in v kakšni meri so doseženi rezultati uporabljeni Cilj F.01 Pridobitev novih praktičnih znanj, informacij in veščin Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.02 Pridobitev novih znanstvenih spoznanj Zastavljen cilj DA NE Rezultat 1 JL Uporaba rezultatov 1 6 F.03 Večja usposobljenost raziskovalno-razvojnega osebja Zastavljen cilj oJ DA J NE Rezultat 1 ^ Uporaba rezultatov 6 F.04 Dvig tehnološke ravni Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.05 Sposobnost za začetek novega tehnološkega razvoja Zastavljen cilj ü DA J NE Rezultat 6 Uporaba rezultatov 1 6 F.06 Razvoj novega izdelka Zastavljen cilj DA NE Rezultat 1 J Uporaba rezultatov 1 6 F.07 Izboljšanje obstoječega izdelka Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.08 Razvoj in izdelava prototipa Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.09 Razvoj novega tehnološkega procesa oz. tehnologije Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.10 Izboljšanje obstoječega tehnološkega procesa oz. tehnologije Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.11 Razvoj nove storitve Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.12 Izboljšanje obstoječe storitve Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.13 Razvoj novih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj DA J NE Rezultat 1 6 Uporaba rezultatov 6 F.14 Izboljšanje obstoječih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.15 Razvoj novega informacijskega sistema/podatkovnih baz Zastavljen cilj DA J NE Rezultat 6 Uporaba rezultatov 6 F.16 Izboljšanje obstoječega informacijskega sistema/podatkovnih baz Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.17 Prenos obstoječih tehnologij, znanj, metod in postopkov v prakso Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.18 Posredovanje novih znanj neposrednim uporabnikom (seminarji, forumi, konference) Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.19 Znanje, ki vodi k ustanovitvi novega podjetja ("spin off") Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.20 Ustanovitev novega podjetja ("spin off") Zastavljen cilj da One Rezultat 6 Uporaba rezultatov 6 F.21 Razvoj novih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.22 Izboljšanje obstoječih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj DA J NE Rezultat 1 6 Uporaba rezultatov 1 6 F.23 Razvoj novih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.24 Izboljšanje obstoječih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj DA J NE Rezultat 1 6 Uporaba rezultatov 6 F.25 Razvoj novih organizacijskih in upravljavskih rešitev Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 6 F.26 Izboljšanje obstoječih organizacijskih in upravljavskih rešitev Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 6 F.27 Prispevek k ohranjanju/varovanje naravne in kulturne dediščine Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 1 6 F.28 Priprava/organizacija razstave Zastavljen cilj O DA J NE Rezultat 1 6 Uporaba rezultatov 6 F.29 Prispevek k razvoju nacionalne kulturne identitete Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.30 Strokovna ocena stanja Zastavljen cilj Oda One Rezultat 6 Uporaba rezultatov 1 6 F.31 Razvoj standardov Zastavljen cilj Oda ne Rezultat 1 6 Uporaba rezultatov 1 6 F.32 Mednarodni patent Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.33 Patent v Sloveniji Zastavljen cilj DA NE Rezultat 6 Uporaba rezultatov 6 F.34 Svetovalna dejavnost Zastavljen cilj DA NE Rezultat 1 6 Uporaba rezultatov 1 6 F.35 Drugo Zastavljen cilj DA NE Rezultat 1 d Uporaba rezultatov 6 Komentar 11. Samo za aplikativne projekte! Označite potencialne vplive oziroma učinke vaših rezultatov na navedena področja Vpliv Ni vpliva Majhen vpliv Srednji vpliv Velik vpliv G.01 Razvoj visoko-šolskega izobraževanja G.01.01. Razvoj dodiplomskega izobraževanja O o o o G.01.02. Razvoj podiplomskega izobraževanja o o o o G.01.03. Drugo: o o o o G.02 Gospodarski razvoj G.02.01 Razširitev ponudbe novih izdelkov/storitev na trgu O O O O G.02.02. Širitev obstoječih trgov o o o o G.02.03. Znižanje stroškov proizvodnje o o o o G.02.04. Zmanjšanje porabe materialov in energije O O O O G.02.05. Razširitev področja dejavnosti o o o o G.02.06. Večja konkurenčna sposobnost o o o o G.02.07. Večji delež izvoza o o o o G.02.08. Povečanje dobička o o o o G.02.09. Nova delovna mesta o o o o G.02.10. Dvig izobrazbene strukture zaposlenih O O O O G.02.11. Nov investicijski zagon o o o o G.02.12. Drugo: o o o o G.03 Tehnološki razvoj G.03.01. Tehnološka razširitev/posodobitev dejavnosti O O O O G.03.02. Tehnološko prestrukturiranje dejavnosti O O O O G.03.03. Uvajanje novih tehnologij o o o o G.03.04. Drugo: o o o o G.04 Družbeni razvoj G.04.01 Dvig kvalitete življenja o o o o G.04.02. Izboljšanje vodenja in upravljanja o o o o G.04.03. Izboljšanje delovanja administracije in javne uprave O O O O G.04.04. Razvoj socialnih dejavnosti O o o o G.04.05. Razvoj civilne družbe o o o o G.04.06. Drugo: o o o o G.05. Ohranjanje in razvoj nacionalne naravne in kulturne dediščine in identitete O O O O G.06. Varovanje okolja in trajnostni razvoj O O O O G.07 Razvoj družbene infrastrukture G.07.01. Informacijsko-komunikacijska infrastruktura O O O O G.07.02. Prometna infrastruktura o o o o G.07.03. Energetska infrastruktura o o o o G.07.04. Drugo: o o o o G.08. Varovanje zdravja in razvoj zdravstvenega varstva O O O O G.09. Drugo: o o o o Komentar 12. Pomen raziskovanja za sofinancerje, navedene v 2. točki11 1. Sofinancer Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. 5. Komentar Ocena 2. Sofinancer Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. Komentar Ocena 3. Sofinancer Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Sifra 5 1 2 3 4. 5. Komentar Ocena C. IZJAVE Podpisani izjavljam/o, da: • so vsi podatki, ki jih navajamo v poročilu, resnični in točni • se strinjamo z obdelavo podatkov v skladu z zakonodajo o varstvu osebnih podatkov za potrebe ocenjevanja, za objavo 6., 7. in 8. točke na spletni strani http://sicris.izum.si/ ter obdelavo teh podatkov za evidence ARRS • so vsi podatki v obrazcu v elektronski obliki identični podatkom v obrazcu v pisni obliki • so z vsebino zaključnega poročila seznanjeni in se strinjajo vsi soizvajalci projekta Podpisi: Peter Korošec in podpis vodje raziskovalnega projekta zastopnik oz. pooblaščena oseba RO Kraj in datum: Ljubljana 18.4.2010 Oznaka poročila: ARRS-RPROJ-ZP-2010-1/122 1 Samo za aplikativne projekte. Nazaj 2 Napišite kratko vsebinsko poročilo, kjer boste predstavili raziskovalno hipotezo in opis raziskovanja. Navedite ključne ugotovitve, znanstvena spoznanja ter rezultate in učinke raziskovalnega projekta. Največ 18.000 znakov vključno s presledki (približno tri strani, velikosti pisave 11). Nazaj 3 Realizacija raziskovalne hipoteze. Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 4 Samo v primeru bistvenih odstopanj in sprememb od predvidenega programa raziskovalnega projekta, kot je bil zapisan v predlogu raziskovalnega projekta. Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 5 Navedite največ pet najpomembnejših znanstvenih rezultatov projektne skupine, ki so nastali v času trajanja projekta v okviru raziskovalnega projekta, ki je predmet poročanja. Za vsak rezultat navedite naslov v slovenskem in angleškem jeziku (največ 150 znakov vključno s presledki), rezultat opišite (največ 600 znakov vključno s presledki) v slovenskem in angleškem jeziku, navedite, kje je objavljen (največ 500 znakov vključno s presledki), izberite ustrezno šifro tipa objave po Tipologiji dokumentov/del za vodenje bibliografij v sistemu COBISS ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Navedeni rezultati bodo objavljeni na spletni strani http://sicris.izum.si/. PRIMER (v slovenskem jeziku): Naslov: Regulacija delovanja beta-2 integrinskih receptorjev s katepsinom X; Opis: Cisteinske proteaze imajo pomembno vlogo pri nastanku in napredovanju raka. Zadnje študije kažejo njihovo povezanost s procesi celičnega signaliziranja in imunskega odziva. V tem znanstvenem članku smo prvi dokazali... (največ 600 znakov vključno s presledki) Objavljeno v: OBERMAJER, N., PREMZL, A., ZAVAŠNIK-BERGANT, T., TURK, B., KOS, J.. Carboxypeptidase cathepsin X mediates ß2 - integrin dependent adhesion of differentiated U-937 cells. Exp. Cell Res., 2006, 312, 2515-2527, JCR IF (2005): 4.148 Tipopologija: 1.01 - Izvirni znanstveni članek COBISS.SI-ID: 1920113 Nazaj 6 Navedite največ pet najpomembnejših družbeno-ekonomsko relevantnih rezultatov projektne skupine, ki so nastali v času trajanja projekta v okviru raziskovalnega projekta, ki je predmet poročanja. Za vsak rezultat navedite naslov (največ 150 znakov vključno s presledki), rezultat opišite (največ 600 znakov vključno s presledki), izberite ustrezen rezultat, ki je v Šifrantu raziskovalnih rezultatov in učinkov (Glej: http://www.arrs.gov.si/sl/gradivo/sifranti/sif-razisk- rezult.asp), navedite, kje je rezultat objavljen (največ 500 znakov vključno s presledki), izberite ustrezno šifro tipa objave po Tipologiji dokumentov/del za vodenje bibliografij v sistemu COBISS ter napišite ustrezno COBISS.SI-ID številko bibliografske enote. Navedeni rezultati bodo objavljeni na spletni strani http://sicris.izum.si/. Nazaj 7 Navedite rezultate raziskovalnega projekta v primeru, da katerega od rezultatov ni mogoče navesti v točkah 6 in 7 (npr. ker se ga v sistemu COBISS ne vodi). Največ 2.000 znakov vključno s presledki. Nazaj 8 Pomen raziskovalnih rezultatov za razvoj znanosti in za razvoj Slovenije bo objavljen na spletni strani: http://sicris.izum.si/ za posamezen projekt, ki je predmet poročanja. Nazaj 9 Največ 4.000 znakov vključno s presledki Nazaj 10 Največ 4.000 znakov vključno s presledki Nazaj 11 Rubrike izpolnite/prepišite skladno z obrazcem "Izjava sofinancerja" (http://www.arrs.gov.si/sl/progproj/rproj/gradivo/), ki ga mora izpolniti sofinancer. Podpisan obrazec "Izjava sofinancerja" pridobi in hrani nosilna raziskovalna organizacija - izvajalka projekta. Nazaj Obrazec: ARRS-RPROJ-ZP/2010 v1.00a 97-A7-00-09-F7-D4-13-2A-32-94-93-1E-32-47-9E-1F-09-36-21-6A