Proceedings of the 2015 eC 2nd Student Computer Science Research oSR Conference C Stu University of Primorska Press StuCoSReC Preface Proceedings of the 2015 2nd Student Computer Science Research Conference Dear reader, in front of you are the proceedings of The 2nd Student Edited by Computer Science Research Conference (StuCoReC) 1. Iztok Fister jr. and Andrej Brodnik The conference started its journey among Slovenian Reviewers and Programme Committee higher education institutions and it is this time hosted Zoran Bosnić ■ University of Ljubljana, Slovenia by the Jožef Stefan International Postgraduate School. Borko Bošković ■ University of Maribor, Slovenia Janez Brest Furthermore, the conference expanded its program to ■ University of Maribor, Slovenia Andrej Brodnik ■ University of Primorska invite even a broader audience and therefore includ- and University of Ljubljana, Slovenia ed the national session for master and undergraduate Mojca Ciglarič ■ University of Ljubljana, Slovenia students to present their work. Consequently on the Jani Dugonik ■ University of Maribor, Slovenia conference were presented three contributions in the Iztok Fister ■ University of Maribor, Slovenia national session and seven contributions in the interna- Iztok Fister Jr. ■ University of Maribor, Slovenia tional session. The authors come from all three Slove- Matjaž Gams ■ Jozef Stefan Institute, Slovenia nian universities, or more precisely from their faculties Tao Gao ■ North China Electric Power University, China with the Computer Science program and from Szeged Andres Iglesias ■ Universidad de Cantabria, Spain University. All papers were reviewed by at least two Branko Kavšek ■ University of Primorska, Slovenia Miklos Kresz members of the international programme committee ■ University of Szeged, Hungary Niko Lukač who made comments that were sent back to authors to ■ University of Maribor, Slovenia Uroš Mlakar ■ University of Maribor, Slovenia further improve their papers Vili Podgorelec ■ University of Maribor, Slovenia The topics of presented contributions prove the variety Peter Rogelj ■ University of Primorska, Slovenia of research done by students. On one side we have pure- Xin-She Yang ■ Middlesex University, United Kingdom Aleš Zamuda ly theoretical topics in algorithm theory and then ex- ■ University of Maribor, Slovenia Borut Žalik ■ University of Maribor, Slovenia panding to very applied research in bioinformatics and linguistics. Quite a number of contributions are in the Published by area of engineering and also HCI. University of Primorska Press Titov trg 4, si-6000 Koper Let us wrap up the preface with an observation that Editor-in-Chief the conference does serve its purpose to bring togeth- Jonatan Vinkler er student researchers to exchange their experiences and ideas, and to establish future contacts. See you on The Managing Editor 3rd Student Computer Science Research Conference! Alen Ježovnik Koper, 2015 isbn 978-961-6984-01-0 (pdf) www.hippocampus.si/isbn/978-961-6984-01-0.pdf isbn 978-961-6984-02-7 (html) www.hippocampus.si/isbn/978-961-6984-02-7/index.html © 2015 Založba Univerze na Primorskem CIP - Kataložni zapis o publikaciji Narodna in univerzitetna knjižnica, Ljubljana 004(082)(0.034.2) STUDENT Computer Science Research Conference (2 ; 2015) StuCoSReC [Elektronski vir] : proceedings of the 2015 2nd Student Computer Science Research Conference / [edited by Iztok Fister and Andrej Brodnik]. - El. knjiga. - Koper : University of Primorska, 2015 Način dostopa (URL): http://www.hippocampus.si/isbn/978- 961-6984-01-0.pdf Način dostopa (URL): http://www.hippocampus.si/isbn/978- 961-6984-02-7/index.html ISBN 978-961-6984-01-0 (pdf) ISBN 978-961-6984-02-7 (html) 1. Gl. stv. nasl. 2. Fister, Iztok, ml. 281595648 1 http://labraj.feri.um.si/stucosrec2015/ Multikonferenca Informacijska družba 2015 Information Society 2015 Predgovor Foreword Multikonferenca Informacijska družba (http://is.ijs.si) In its 18th year, the Information Society Multicon- je z osemnajsto zaporedno prireditvijo osrednji srednje- ference (http://is.ijs.si) remains one of the leading evropski dogodek na področju informacijske družbe, conferences in Central Europe devoted to information računalništva in informatike. Letošnja prireditev traja society, computer science and informatics. In 2015 tri tedne in poteka na Fakulteti za računalništvo in it is extended over three weeks located at Faculty of informatiko in Institutu »Jožef Stefan«. computer science and informatics and at the Institute Informacijska družba, znanje in umetna inteligenca se “Jožef Stefan”. razvijajo čedalje hitreje. V vse več državah je dovoljena The pace of progress of information society, knowledge samostojna vožnja inteligentnih avtomobilov, na trgu and artificial intelligence is speeding up. Several coun- je moč dobiti čedalje več pogosto prodajanih avtomobi- tries allow autonomous cars in regular use, major car lov z avtonomnimi funkcijami kot »lane asist«. Čedalje companies sell cars with lane assist and other intelli- več pokazateljev kaže, da prehajamo v naslednje civili- gent functions. It seems that humanity is approaching zacijsko obdobje, hkrati pa so konflikti sodobne družbe another civilization stage. At the same time, society čedalje težje razumljivi. conflicts are growing in numbers and length. Letos smo v multikonferenco povezali dvanajst odlič- The Multiconference is running in parallel sessions nih neodvisnih konferenc. Predstavljenih bo okoli 300 with 300 presentations of scientific papers at twelve referatov v okviru samostojnih konferenc in delavnic, conferences, round tables, workshops and award cer- prireditev bodo spremljale okrogle mize in razprave ter emonies. The papers are published in the conference posebni dogodki kot svečana podelitev nagrad. Refe- proceedings, and in special issues of two journals. One rati so objavljeni v zbornikih ultikonference, izbrani of them is Informatica with its 38 years of tradition in prispevki pa bodo izšli tudi v posebnih številkah dveh excellent research publications. znanstvenih revij, od katerih je ena Informatica, ki se ponaša z 38-letno tradicijo odlične znanstvene revije. The Information Society 2015 Multiconference consists Multikonferenco Informacijska družba 2015 sestavljajo of the following conferences: naslednje samostojne konference: Intelligent Systems Inteligentni sistemi Cognitive Science Kognitivna znanost Data Mining and Data Warehouses Izkopavanje znanja in podatkovna skladišča Collaboration, Software and Services in Information Sodelovanje, programska oprema in storitve v infor- Society macijski družbi Education in Information Society Vzgoja in izobraževanje v informacijski družbi Facing Demographic Challenges Soočanje z demografskimi izzivi Cognitonics Kognitonika SPS EM-Health Workshop Delavnica »SPS EM-zdravje« Workshop »Smart Cities and Communities as a Delavnica »Pametna mesta in skupnosti kot razvoj- Development Opportunity for Slovenia« na priložnost Slovenije« 2nd Computer Science Student Conference, PhD Druga študentska konferenca s področja računalni- Students štva in informatike za doktorske študente 2nd Computer Science Student Conference, Students Druga študentska konferenca s področja računalni- 8th International Conference on Informatics in štva in informatike za vse študente Schools: Situation, Evolution, and Perspective . ISSEP15 - Osma mednarodna konferenca o infor- The Multiconference is co-organized and supported matiki v šolah: razmere, evolucija in perspektiva. by several major research institutions and societies, Soorganizatorji in podporniki konference so različne among them ACM Slovenia, i.e. the Slovenian chapter raziskovalne institucije in združenja, med njimi tudi of the ACM, SLAIS and the Slovenian Engineering ACM Slovenija, SLAIS in Inženirska akademija Slove- Academy. In the name of the conference organizers we nije. V imenu organizatorjev konference se zahvalju- thank all societies and institutions, all participants for jemo združenjem in inštitucijam, še posebej pa udele- their valuable contribution and their interest in this žencem za njihove dragocene prispevke in priložnost, event, and the reviewers for their thorough reviews. da z nami delijo svoje izkušnje o informacijski družbi. For 2013 and further, the award for life-long outstand- Zahvaljujemo se tudi recenzentom za njihovo pomoč ing contributions will be delivered in memory of Don- pri recenziranju. ald Michie and Alan Turing. The life-long outstanding V 2015 bomo tretjič podelili nagrado za življenjske contribution to development and promotion of infor- dosežke v čast Donalda Michija in Alana Turinga. mation society in our country is awarded to Dr. Jurij Nagrado Michie-Turing za izjemen življenjski prispevek Tasič. In addition, a reward for current achievements k razvoju in promociji informacijske družbe bo prejel was pronounced to Dr. Domnu Mongusu. The informa- StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October III prof. dr. Jurij Tasič. Priznanje za dosežek leta je pripa- tion strawberry is pronounced to the web application dlo dr. Domnu Mongusu. Že petič podeljujemo nagradi “Supervizor, while the information lemon goes to lack »informacijska limona« in »informacijska jagoda« za of informatization in the national judicial system. Con- najbolj (ne)uspešne poteze v zvezi z informacijsko gratulations! družbo. Limono je dobilo počasno uvajanje informati- zacije v slovensko pravosodje, jagodo pa spletna aplika- cija »Supervizor«. Čestitke nagrajencem! Nikolaj Zimic, Programme Committee Chair Matjaž Gams, Organizing Committee Chair Nikolaj Zimic, predsednik programskega odbora Matjaž Gams, predsednik organizacijskega odbora StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October IV Contents Preface II Multikonferenca Informacijska družba 2015: predgovor III Information Society 2015: Foreword III National session ◆ Nacionalna sekcija Izdelava ogrodja robota s pomočjo 3D tiskalnika ◆ Primož Bencak, Dusan Fister and Riko Šafarič 7–11 Nastavljanje parametrov regulatorja z optimizacijskimi algoritmi ◆ Dusan Fister, Riko Šafarič, Iztok Jr. Fister and Iztok Fister 13–17 Analiza sentimenta z uporabo emotikonov in besednih zvez ◆ Tadej Jerovšek, Martin Kraner, Tadej Ganza, Tomaž Cebek and Borko Bošković 19–23 International session ◆ Mednarodna sekcija MySQL Database On-line Update Technology Based on JSP ◆ Xiaocheng Du, Tao Gao and Yaoquan Yang 25–29 Towards the Development of a Parameter-free Bat Algorithm ◆ Iztok Fister Jr., Iztok Fister and Xin-She Yang 31–34 Using trees to speed up the Floyd-Warshall algorithm ◆ Marko Grgurovič 35–38 3D walk through the references of Dutch women writers ◆ Jernej Grosar, Jure Demšar and Narvika Bovcon 39–42 Budget travelling through virtual reality ◆ Žiga Kerec, Marko Balažic, Jure Demšar and Narvika Bovcon 43–45 Comparison of DE strategies for Gray-Level Multilevel Thresholding ◆ Uroš Mlakar and Iztok Fister 47–51 Processing of next-generation sequencing (NGS) data with MapReduce and HADOOP cluster 53–56 ◆ Nándor Póka and Miklós Krész Developing a web application for DNA data analysis ◆ Aleksandar Tošić 57–60 Personalization of intelligent objects ◆ Aleksandar Tošić, Aleksandar Todorović, Tanja Štular, Nejc Radež, Tadej Krivec, 61–64 Tjaž Brelih, Neli Kovšca, Anja Rudež, Aleš Papič, Vladan Jovičić and Marko Palangetić StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October V StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 6 Izdelava ogrodja robota s pomo čjo 3D tiskalnika Primož Bencak Fister Dušan Riko Šafarič Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru Fakulteta za strojništvo Fakulteta za strojništvo Fakulteta za elektrotehniko, Smetanova 17, Maribor Smetanova 17, Maribor računalništvo in informatiko primoz.bencak@ dusan.fister@ Smetanova 17, Maribor student.um.si student.um.si riko.safaric@um.si POVZETEK izmed naših ciljev je sestaviti primerno ogrodje za mobil- V tem članku predstavljamo izdelavo mobilnega robota, ki nega robota. Zaradi čimvečje popularnosti 3D nanašanja in je zmožen prevoziti čim dlje v robotskem labirintu, sesta- tiskanja nas je zanimalo, ali lahko s to tehnologijo ustvarimo vljenem iz manjših kvadratnih gradnikov - polj. 3D tiskanje dovolj kakovostno ogrodje, ki bo po zahtevanih lastnostih predstavlja revolucionarno metodo konstruiranja vsakdanjih primerljivo tistim, ki so izdelane po bolj konvencionalnem objektov z metodo nanašanja materiala. Uporaba te metode načinu. 3D tiskanje je začelo svoj razvoj že v zgodnjih de- se je začela širše uveljavljati šele v zadnjih letih, čeprav je vetdesetih letih prejšnjega stoletja [9]. Tehnologija je na- princip tiskanja znan že dobrih trideset let. Dandanes si predovala celo do te mere, da so s 3D tiskalnikom natisnili jo z nekaj inženirske žilice lahko privošči vsakdo. Enostav- prototip avtomobila Audi [7]. nost te metode omogoča konstruiranje poljubnih gradnikov, zato smo se odločili preizkusiti to metodo za konstruiranje Za izdelavo konstrukcije robota smo v naši študiji upora- ogrodja mobilnega robota. bili odprtokodni 3D tiskalnik Mendel podjetja RepRap, ki je na tržišču na voljo v obliki kompleta naredi sam (angl. do-it-yourself). S samo konstrukcijo 3D tiskalnika se nismo Kjučne besede ukvarjali, saj je bilo to delo pred nami že opravljeno. Naš tehnologija dodajanja, 3D tiskanje, hitra izdelava prototipov del je zajemal načrtovanje in tiskanje samega ogrodja robota. Načrtovanje ponavadi poteka v katerem od strojniških pro- 1. UVOD gramov, kjer uporabnik želeno ogrodje izriše, določi končne Robot je običajno elektro-mehanska naprava, ki jo vodi ra- mere in s pomočjo preprostih pretvorniških programov risbo čunalniški program. Deluje v okolju, ki ga je s pomočjo pretvori v tiskalniku razumljiv program. Za izris smo upo- akcij, za katere je pooblaščen, sposoben tudi spreminjati. rabili program SolidWorks [10], medtem ko za pretvorbo v Izvaja ponavljajoče se akcije, ki jih je prej izvajal človek. G-kodo program Slic3r [6]. Slednjega pri tem izpodriva predvsem pri nevarnih opravi- lih, npr. lakiranju avtomobilov v avtomobilski industriji, Struktura članka v nadaljevanju je naslednja. Poglavje 2 izvajanju poskusov v vesolju, ipd. govori o problemu izdelave ogrodja robota s pomočjo 3D ti- skalnika. V poglavju 3 opišemo postopek izdelave ogrodja Načrtovanje robota je zapleten projekt, saj vključuje znanja robota na 3D tiskalniku. Preizkus izdelanega ogrodja je opi- iz različnih domen, tj. elektrotehnike, strojništva, računalni- san v poglavju 4. Članek zaključimo s poglavjem 5, kjer štva, ipd. Orientirani na mobilne robote domače izdelave po- nakažemo možne izboljšave našega dela v prihodnje. znamo številne alternativne pristope izdelave ogrodja. Naj- pogosteje izbiramo med uporabo plastične posode ali plastič- 2. 3D TISKANJE nih plošč [4], Lego kock [1], lesenih konstrukcij ali celo pre- 3D tiskalnik je mehatronska naprava, ki omogoča izdelavo delavo ogrodja modelov avtomobilčkov, ipd. Za robote in- tridimenzionalnih objektov s pomočjo nanosa posameznih dustrijske izdelave taka ogrodja ne pridejo v poštev, nosilno slojev gradiva (angl. additive manufacturing) [5]. Razvit je funkcijo največkrat opravlja lahko aluminijasto ogrodje, ki bil kot nadgradnja običajnega 2D tiskalnika, ki pa podpira ostalim gradnikom omogoča trdno oporo. tiskanje v treh dimenzijah. 3D tiskalnik je dobrodošel pri- pomoček inženirjev, arhitektov, oblikovalcev in ostalih teh- Labirint, ki ga robot mora prevoziti, ima postavljene stene, noloških navdušencev. v katere se ne sme zaleteti in med katerimi manevrira. Eden Tradicionalni pristop izdelave raznih izdelkov iz polizdelkov je potekal z odnašanjem (substrakcijo) gradiva. Nov, revo- lucionarni pristop pa deluje po principu dodajanja (adicije) gradiva [8]. Tako lahko sedaj s 3D tiskalnikom izdelamo iz- delke, ki jih prej sploh ni bilo moč izdelati [2]. Prednost take izdelave je tudi v tem, da ni odpadkov, saj porabimo samo toliko materiala, kolikor ga je v končnem izdelku. Izdelki so tako cenejši, konkurenčnejši in tudi ekološko prijaznejši. Sprva so bili 3D tiskalniki namenjeni tiskanju manj zahtev- StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 7 nih oblik ali prototipov za izdelke, ki so jih potem izdelovali Ugotovili smo, da 3D tisk ponuja veliko prednosti pred osta- z drugo tehnologijo. Dandanes pa se vse bolj nagibajo k limi oblikami načrtovanja in izdelave, zato smo jo tudi upo- temu, da je določen izdelek že v celoti izdelan s 3D tiskalni- rabili v naši študiji. Postopek izdelave je sestavljen iz petih kom. V dobrih tridesetih letih svojega razvoja smo odkrili faz [11]: marsikaj novega. Novosti so predvsem v različnih materi- • načrtovanje 3D modela v programu SolidWorks, alih, s katerimi lahko izdelke enostavno tiskamo (slika 1). • prenos 3D modela v Slic3r, • prevajanje G-kode (angl. G-code), • optimizacija nastavitev temperature grelca in pozicije 3D modela, • predgretje in 3D tisk. Načrtovanje 3D modela smo izvedli v razvojnem orodju So- lidWorks (slika 2), ki je zelo cenjen med inženirji in obliko- valci, saj ponuja vrsto različnih načinov risanja. Za samo konstruiranje je sicer potrebno nekaj predznanja, ki pa ga Slika 1: Izdelek tiskanja. ni težko usvojiti. 3D tiskalnik je sestavljen iz različnih elektronskih in strojnih elementov. Najpomembejši so: Gradnjo 3D modela smo začeli z osnovnim likom – pravoko- • iztiskalna šoba (angl. extruder nozzle): skrbi za bri- tnikom, ki smo mu prirezali stranice. Z orodjem Extruded zganje tekočega gradiva - filamenta (nanašalnega vla- Boss/Base smo pravokotniku določili še tretjo dimenzijo - kna), višino, ter dobili kvader. V sredini kvadra smo izrezali od- prtino kvadratne oblike, namenjeno tiskanemu vezju. Na • koračni motorji: zagotavljajo premikanje v ravnini X- koncu smo dodali še nosilce za LED diode, nosilec za 9V ba- Y in osi Z, terijo, ter luknjo za stikalo. Končnemu modelu smo določili še dimenzije ter model shranili v datoteko *.STL. Bistveno • grelec: utekočini filament in skrbi za vzdrževanje tem- pri načrtovanju 3D modela je, da se držimo nekaj osnovnih perature, napotkov, ki pripomorejo k boljšemu končnemu izdelku, tj.: • grelna mizica, • dimenzije končnega izdelka morajo biti v skladu z razse- • napajalni del z elektronskim vezjem. žnostjo našega 3D tiskalnika, Omenjeni sestavni deli opredeljujejo tiskalnik kot mehatron- • izogibamo se konstrukciji mostičkov, tj. delov, kjer bi sko napravo. Čeprav je tiskalnik statična naprava uporablja naša ekstruderska šoba filament vlekla po zraku in ne številne aktuatorje gibanja. Ti skrbijo za premikanje izti- po prejšnjem sloju, skalne šobe, ki iztiska predhodno utekočinjen filament. Ute- kočinja ga reguliran grelec, ki poleg grelne mizice predstavlja • če bo naš model imel izvrtine (luknje), morajo biti osnovo za kakovostno izdelano ogrodje. Iztiskalno šobo po- dimenzije na modelu večje od dejanskih, sicer jih mo- ganja dodatni električni motor. Šoba predstavlja izmed vseh ramo povrtavati, gradnikov najobčutljivejši del. • izogibamo se pretankim stenam (nizka trdnost), hkrati pa tudi nepotrebno debelim (čas tiskanja se zelo po- Koračni motorji opravljajo dve funkciji. Poleg premikanja daljša, porabimo več gradiva). šobe skrbijo tudi za merjenje položaja, kar je glavna značil- nost koračnih motorjev. Zaradi tega jih odlikuje enostavna uporaba, vendar po drugi strani omejuje visok vrtilni mo- Datoteko izvozimo v formatu *.STL (Lithography), ki iz- ment in visoka vrtilna frekvenca. V kolikor motor doseže risan trodimenzialni model zapiše kot množico trikotnikov. katero ob obeh lastnosti, pride do izpada iz koraka, kar pre- Datoteka *.STL je namenjena za pretvorbo v tiskalniku razu- pozna elektronsko vezje in gibanje ustavi. mljivo obliko, G-kodo. G-koda predstavlja numerični zapis modela, razumljivega numerično krmiljenim strojem (angl. 3. IZDELAVA OGRODJA ROBOTA numerical control, krajše NC) [3]. Pretvorbo opravi preprost Za 3D tisk smo se odločili, ker ima nekaj prednosti pred program Slic3r, ki vsebuje navodila za: ostalimi metodami izdelave ogrodja robota. Da bi izdelali • premikanje šobe po tiskalni površini [2], uporabno ogrodje, ki zadošča našim potrebam, smo se mo- rali osredotočiti na bistvene lastnosti, ki jih ogrodje mora • uporabo kombinacije koordinat in slojev (angl. layer), imeti, tj.: po katerem se premika, • trdnost, • količino gradiva, ki se bo uporabil pri tiskanju, • teža, • nastavitve temperature iztiskalne šobe in grelne mi- • zahtevnost izdelave, zice, • čas izdelave. • način 3D tiskanja, ipd. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 8 Slika 2: Razvojno orodje Solidworks za 3D-tiskanje. Ročno lahko nastavimo tudi način zapolnitve medrobnega medtem ko se preostali sloji tiskajo hitreje. Vzrok za daljše prostora, spreminjamo delež le-tega in podamo navodila za tiskanje prvega sloja je v zapolnitvi prostora oz. večji ka- premikanje šobe po določenem vzorcu, morebiti izberemo kovosti končnega izdelka. Na ta način je spodnji del, ki se način satje(angl. honeycomb) ali premočrtno (angl. recti- dotika ogrevalne mizice na otip gladek ter svetleč. Primer linear) gibanje. Različne nastavitve vplivajo na končno tr- programa v G-kodi prikazuje algoritem 1 [12]. doto izdelka in na količino porabljenega filamenta (slika 3). Končno datoteko z vsemi nastavitvami nato prenesemo na Algoritem 1 G-koda 3D tiskalnik, ki prične s tiskanjem. Po uspešno naloženem 1: M107 ; izklop ventilatorja 2: M104 S205 ; nastavi temperaturo 3: G28 ; pojdi na koordinatno izhodišče (0,0) 4: G1 Z5 F5000 ; dvig ekstruderske šobe Naprava mora biti priklopljena na stabilno električno omrežje, saj v primeru izpada energije, s tiskom ne moremo nadalje- vati in moramo začeti znova. Čas tiska je pogojen s hitrostjo koračnih motorjev, še bolj kot s tem, pa z razsežnostjo in debelino sten našega izdelka. Za naše ogrodje je tiskalnik porabil okoli tri ure. Po koncu tiskanja je potrebno poča- kati, da se ogrevana podloga ohladi na okoli 50◦C, saj takrat predmet najlaže ločimo od podloge. Končan izdelek je ta- koj trd na otip in pripravljen na nadaljnjo obdelavo (npr. barvanje). Pri morebitnem dodatnem povrtavanju ali bru- Slika 3: 3D-tiskanje. šenju moramo biti zelo pazljivi, saj ima tako PLA kot ABS filament, nizko temperaturo tališča. Pri nepravilni obdelavi programu se izvajanje le-tega ne prične takoj. Sprva se začne lahko izdelek trajno deformiramo in nepopravljivo poškodu- predgretje šobe in grelne mizice, kar ponavadi traja do 10 jemo. minut. Šoba se potem premakne v izhodiščno lego na ko- ordinate (0,0), ki je referenčna točka za G-kodo. Program- 4. POSKUSI IN REZULTATI ski stavek je sestavljen iz digitalnih besed (16-bitna dolžina Na poti do uspešne izdelave ogrodja smo se srečali z neka- niza), ki vsebujeta ukaz in ukazni parameter. terimi težavami. Luknje na natisnjenem objektu niso bile Tabela 1: Predstavitev G-kode enako velike kot tiste, ki smo jih načrtovali v SolidWorks-u. Zahtevale so dodatno obdelavo s pilo. Vzrok za ta pojav Naslov Vrednost Naslov Vrednost Naslov Vrednost je natančnost koračnih motorjev, ki ne morejo natisniti po- G 01 X 800 Y 360 polne izvrtine, saj jo ustvarijo kot množico tankih črt, zlo- BESEDA BESEDA BESEDA ženo drugo ob drugi. Natančnost izdelave izvrtine je odvisna od ločljivosti koračnega motorja. Ker 3D tiskalnik nima nobenih senzorjev, ki bi preverjali trenutno lego na koordinatni mreži (površini za tiskanje), Dodaten problem predstavlja tvorba mostičkov. Tiskanje ampak pravilno pozicioniranje šobe zagotavlja koračni mo- objekta poteka od spodnjega sloja proti zgornjemu, kar po- tor, je zelo pomembno, da mize, na kateri je 3D tiskalnik meni, da mora spodnji sloj biti vedno enak ali večji od zgor- ne premikamo. Prvi sloj tiskalnik tiska nekoliko več časa, njega. Primer pravilnega načrtovanja je prikazan na sliki 4a, StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 9 (a) Pravilno načrtovanje (b) Nepravilno načrtovanje Slika 4: Primerjava dobrega in slabega načrtovanja. kjer spodnji sloj v vsakem primeru služi kot opora zgornjemu predvsem pri končnem času, ki ga potrebujemo za celotno - ta se lahko nanaša na spodnjega. Slika 4b je primer ne- izdelavo - potrebna sta zgolj modeliranje in tiskanje. Ker je pravilnega načrtovanja objektov. Spodnji sloj ne služi kot tiskalnik avtonomna naprava, človeku ni potrebno biti pri- trdna opora celotni strukturi, vendar le delu. Posledico tega soten, kar izdelovalni čas dodatno skrajša. Filamenti so na predstavlja tiskanje filamenta v zrak, zaradi česar objekta voljo v različnih barvah, zato izdelka ni potrebno barvati, ni moč uporabiti. prav tako pa v večini primerov odpade tudi brušenje. Na ta način namreč odpade velik del časa, ki bi ga sicer potre- Težavo predstavlja tudi odvijanje filamenta s tulca. Zaradi bovali, da bi izdelek naprej načrtovali (opravljanje meritev), teže navitja filamenta, ga motor ne zmore vleči enakomerno, primerno mehansko obdelali ter v nekaterih primerih tudi kar preprosto rešimo z ročnim odvijanjem vsakih nekaj mi- pobarvali. Za omenjeno metodo niso potrebne ročne spre- nut. V nasprotnem primeru iztiskalna šoba ne dobiva dovolj tnosti, ki v primeru rokovanja z obdelovalnimi stroji v veliki filamenta, kar pomeni, da sloji objekta niso enakomerno na- meri vplivajo na kakovost izdelka. Namesto več naprav po- nešeni. Ogrodje, ki smo ga izdelali, je namenjenu mobil- trebujemo samo računalnik in tiskalnik. Za pot od ideje do končnega izdelka smo porabili okoli štiri ure, izmed katerih je več kot dobra polovica časa pripadala samo tiskanju. Ob izbiri konvencialne metode gradnje ogrodja iz lesa primer- ljive oblike je potrebno: • poiskati primeren kos s pravšnjo trdoto in kakovostjo, • prenesti mere na obdelovanec, • izrezati ogrodje z namizno žago, • izvrtati luknje, • pobrusiti površino in Slika 5: Končna izvedba mobilnega robota. • ogrodje prebarvati. nemu robotu, čigar naloga je vožnja skozi labirint (slika 5). Na ogrodje sta na zadnjem delu pritrjena modificirana servo motorčka, nad motorčkoma pa se nahaja držalo za 9V ba- Celotni postopek časovni okvir izdelovanja ogrodja s kon- terijo. V sredini je okvir, v katerem je nameščeno vezje vencialno metodo tako drastično poveča. Rrobot, prikazan robota, ki ga nadzoruje mikrokrmilnik PIC18F25K22, pod- na sliki 5, skupaj z devet voltno (blok) baterijo tehta le 352 jetja Microchip. Zaradi dobrega razmerja med močjo ser- gramov. Čeprav je ogrodje sorazmerno veliko, pa je vzrok za vomotorčkov in nizko težo, robot dosega zadovoljive hitro- malo težo v razporeditvi filamenta po volumnu. Notranjost sti, ki pa so pogojene s kapaciteto baterije. Na prednjem sten namreč v našem primeru ni bila zapolnjena stoodsto- delu in levi strani mobilnega robota, sta nameščena dva in- tno, saj smo na ta način privarčevali tudi s filamentom. frardeča senzorja oddaljenosti, SHARP GP2Y0A41SK0F. S senzorjema robot zaznava oddaljenost od ovir. Na podlagi 5. SKLEP izhodnih vrednosti senzorjev, se mikrokrmilnik, ki smo ga V članku smo predstavili izdelavo ogrodja za robota s po- prej sprogramirali v programskem orodju MikroC, ustrezno močjo 3D tiska. S končnim izdelkom smo dosegli želene odzove z vrtenjem osi koračnim motorjem. rezultate. Ogrodje je namreč dovolj trdno, da se tudi ob močnejši tlačni obremenitvi ne poruši. Uporaba ogrodja v 4.1 Diskusija okolju s povišano temperaturo predstavlja splošno težavo pri Prednost gradnje ogrodja s 3D tiskalnikom v primerjavi s večini postopkov nanašanja materiala, saj je temperaturna tistimi, izdelani iz bolj konvencionalnih materialov vidimo obstojnost takih materialov omejena na nižje temperature. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 10 Ta vpliv lahko zmanjšamo z uporabo grelne mizice, vendar ga v celoti ne moremo odpraviti. Nadaljno težavo predstavlja natančnost tiskalnika. Z zmanj- ševanjem premera iztiskalne šobe bi jo lahko povečali, prav tako z zamenjavo koračnih motorjev za servomotorje in na- mestitvijo natančnih dajalnikov položaja. Ti ukrepi pa so povezani s povečanimi stroški tiskanja. 6. REFERENCES [1] D. Baum and R. Zurcher. Definitive Guide to Lego Mindstorms, volume 2. Apress, 2003. [2] B. Berman. 3-d printing: The new industrial revolution. Business Horizons, 55(2):155 – 162, 2012. [3] P. Bézier. Numerical control. 1970. [4] G. Caprari, P. Balmer, R. Piguet, and R. Siegwart. The autonomous micro robot “alice”: a platform for scientific and commercial applications. In Micromechatronics and Human Science, 1998. MHS’98. Proceedings of the 1998 International Symposium on, pages 231–235. IEEE, 1998. [5] C. K. Chua and K. F. Leong. 3D Printing and Additive Manufacturing : Principles and Applications (with Companion Media Pack) Fourth Edition of Rapid Prototyping. World Scientific Publishing Co., Singapore, 2015. [6] G. Hodgson. Slic3r manual, 2015. [7] H. Lipson and M. Kurman. Fabricated: The New World of 3D Printing. John Wiley and Sons, New York, 2013. [8] R. I. Noorani. Prototyping: Principles and Applications. John Wiley and Sons, New York, 2006. [9] G. Ratajc. Priprava tridimenzionalnega modela za tiskanje s 3D-tiskalnikom. Diplomsko delo : Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, 2005. [10] D. Systémes. Solidworks help, 2015. [11] M. Vaezi, H. Seitz, and S. Yang. A review on 3d micro-additive manufacturing technologies. The International Journal of Advanced Manufacturing Technology, 67(5-8):1721–1754, July 2013. [12] Wikidot. G-code guide, 2015. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 11 StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 12 Nastavljanje parametrov regulatorja z optimizacijskimi algoritmi Dušan Fister Riko Šafarič Iztok Jr. Fister Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru Fakulteta za strojništvo Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, Smetanova 17, Maribor računalništvo in informatiko računalništvo in informatiko dusan.fister@student.um.si Smetanova 17, Maribor Smetanova 17, Maribor riko.safaric@um.si iztok.fister1@um.si Iztok Fister Univerza v Mariboru Fakulteta za elektrotehniko, računalništvo in informatiko Smetanova 17, Maribor iztok.fister@um.si POVZETEK in PD-regulatorjev, do najkompleksnejšega PID-regulatorja. Vsak regulacijski sistem za optimalno delovanje zahteva pra- V kraticah imen teh regulatorjev pomeni I-člen integriranje vilno nastavitev vhodnih parametrov. Uporabnik tega sis- in D-člen diferenciranje napake. Da zagotovimo pravilno tema strmi k temu, da bo njegov sistem deloval čim bolj op- nastavljen regulator, moramo pravilno nastaviti vsak posa- timalno. Za industrijske robote to pomeni, da sistem zago- mezen člen posebej. Robot optimalno deluje šele, ko so glede tavlja varnost in funkcionalnost. Velikokrat uvrščamo funk- na njegove zahteve dela optimalno nastavljeni vsi členi re- cionalnost pred varnost, kar povzroča nevšečnosti v praksi. gulatorja. Enačba (1) matematično prikazuje regulacijske Sami želimo robotu optimalno nastaviti regulacijske parame- člene in njegove nastavljive parametre, tj. tre tako, da bo zagotavljal tako varnost kot tudi funkcional- nost. Čeprav je naš robot miniaturna različica industrijskega robota, tudi ta za pravilno delovanje zahteva dovolj kakovo- u = KP (yzel − ydej) + KI (yzel − ydej) + KD(yzel − ydej) , stne nastavitve regulacijskih parametrov. Cilj naše študije je (1) za iskanje optimalnih regulacijskih parametrov razviti algo- ritem po vzoru obnašanja netopirjev in ga uspešno uporabiti kjer yzel predstavlja želeno referenčno vrednost, medtem ko v praksi. ydej dejansko vrednost prenihaja. Naš uporabljen regulator, opisan z enačbo (1), sestoji iz izključno PI-člena, kar pomeni, Kjučne besede da D-člen v našem primeru odpade. regulacije, mehatronika, optimizacijski algoritmi Najpreprostejši način nastavljanja parametrov je ročno na- 1. UVOD stavljanje, ki pa zahteva izkušenega tehnika in obilo po- trpežljivosti. Obstajajo različne avtomatske metode nasta- Optimizacijske algoritme uporabljamo za povečanje produk- vljanja, kjer največkrat v te namene uporabljamo optimiza- tivnosti, storilnosti, kakovosti in hitrosti dela robotskih stro- cijske algoritme po vzoru iz narave. Korenine teh algoritmov jev. Vsak robot mora skozi dobo obratovanja delovati zane- segajo v leto 1871, ko je Charles Darwin objavil znanstveno sljivo, varno ter funkcionalno. Pričakovati je, da bo robot delo o naravni selekciji [1]. Ta je navdihnila Alana Turinga zaradi povečanja produktivnosti deloval karseda hitro, ven- pri razvoju t.i. genetskega iskanja, ki uporablja Darwinovo dar zaradi tega ne bo ogrožal varnosti ljudi v njegovi bli- evolucijsko teorijo pri reševanju optimizacijskih problemov žini. Pomembni faktor za delovanje robotskih mehanizmov [14]. Leta 1988 je John Holland algoritem s selekcijo in mu- predstavlja regulator, tj. element, ki zmanjšuje napako, tacijo poimenoval genetski algoritem, kar se je ohranilo vse oz. razliko med želeno in dejansko vrednostjo. Poznamo do danes [7]. Podrobnejši zgodovinsko pregled je naveden več vrst regulatorjev, od najpreprostejšega P-regulatorja, ki v [4]. omogoča le ojačanje napake, do nekoliko kompleksnejših PI- Z robotom SCARA (angl. Selective Compliance Assem- bly Robot Arm) [12], prikazanim na sliki 1, se je prvi za- čel ukvarjati Albin Jagarinec. Leta 2005 je uspešno razvil adaptivni regulator [8], medtem ko je leto kasneje Marko Kolar preizkusil algoritem z mehko logiko [11]. Jure Čas se je ukvarjal z zveznim nevronskim sliding-mode regulato- rjem [15], medtem ko je Tomaž Slanič iskal optimalne na- stavitve parametrov omenjenega robota z genetskim algo- ritmom [13]. V tem prispevku opisujemo avtomatsko nasta- StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 13 Osnovni parametri za izračun modela robota so dolžine l, mase m in težiščni vztrajnosti momenti J posameznih osi ter gonil, medtem ko dodatni členi predstavljajo položaj q, hitrost ˙ q in pospešek osi ¨ q. Optimizacijski problem je definiran kot OP = {I, S, f, goal }, kjer I predstavlja množico vseh nalog x ∈ I, ki se lahko po- javijo na vhodu, S je množica dopustnih rešitev x ∈ S in f kriterijska funkcija. goal določa, ali kriterijsko funkcijo mi- nimiziramo ali maksimiziramo. Vhod v optimizacijski pro- blem je podan z dvema dvojicama parametrov: x = {Kp1, Kp2, Kv1, Kv2} , (3) kjer parametra Kp1 in Kp2 označujeta velikost proporcio- nalnega dela (P-člena) prve oz. druge osi, ter Kv1 oz. Kv2 velikost integralnega dela (I-člena) prve oz. druge osi. Med optimizacijskim postopkom pri znanem modelu in zna- nem izhodu iščemo optimalne vhodne spremenljivke [2]. Pri tem izhodne spremenljivke razvrstimo v tri različne katego- Slika 1: Dvoosni robot. rije, tj.: • Over vljanje parametrov PI-položajnega regulatorja na dvoosnem i - dejanski prenihaj posamezne osi, robotu SCARA z algoritmom po vzoru obnašanja netopir- • Essi - statični pogrešek posamezne osi in jev (angl. Bat Algorithm, krajše BA) [18]. Slednji obljublja enostavno implementacijo algoritma za reševanje realnega • T imei - nastavitveni čas posamezne osi. problema in hkrati ponuja hitro konvergenco rešitev. Gre za novejšega predstavnika algoritmov iz družine inteligence Vse tri izhodne spremenljivke pridobivamo neposredno iz rojev (angl. Swarm Intelligence), ki za svoje delovanje upo- kartice DSP-2 Roby, medtem ko jih na računalniku dodatno rabljajo biološko-socialno obnašanje insektov (npr. roji če- obdelamo in uporabljamo za vrednotenje kakovosti vhodnih bel, družine mravelj, ipd.) oz. živali (npr. jate ptic, rib, podatkov. Ti predstavljajo osnovo za vrednotenje kakovosti ipd.) [10]. poljubnega odziva na stopnično funkcijo. Robotu tako po- dajamo navodila za delo, npr. premakni obe osi za določen kot. Robot poskuša doseči najhitrejši premik ob upošteva- 2. REGULACIJSKA PROGA nju zahtevanega prenihaja, minimalnega statičnega pogre- Glavnino regulacijske proge predstavlja dvoosni robot SCA- ška in minimalnega nastavitvenega časa. Zahtevan prenihaj RA, ki pooseblja gibanje človeške roke okoli rame in ko- vnese uporabnik programa pred začetkom optimizacije. molca, za kar skrbita dva enosmerna motorja. H glavni gredi vsakega motorja je prigrajen tudi inkrementalni merilnik po- Vrednotenje, oz. ocenjevanje odziva in posledično kakovosti ložaja, ki služi kot dajalnik povratnega signala. Za učin- izhodnih podatkov (posredno vhodnih) izvaja ocenjevalna kovito gibanje sklopa skrbita gonilnika motorjev, ki zdru- funkcija (angl. objective function), prikazana v enačbi (4): žujeta položajni regulator, komparator in smerni diskrimina- tor za identifikacijo signalov iz inkrementalnega dajalnika ter fi = E1i·(1−|Pi − Overi|)+E2i·(1−T imei)+E3i·(1−Essi), ojačevalnik referenčnega signala. Slednjega določa vmesnik (4) med računalnikom in robotom, katerega imenujemo DSP- 2 Roby kartica [16]. Razvita je bila na UM, FERI in je ki jo maksimiziramo. Zaradi medsebojno mehanske skloplje- neposredno povezana z računalnikom, od koder pridobiva nosti dvoosnega robota večkriterijske optimizacije ne mo- zahtevane podatke in kamor pošilja povratne informacije. remo vršiti. Zato uporabimo uteženo vsoto kriterijev, ki Optimizacija zato v celoti teče na računalniku. utežijo posamezen parameter tako, da na koncu znaša maksi- malna vrednost (popolni odziv) ocenjevalne funkcije fi = 1. Bližje enici torej smo, kakovostnejše rezultate pridobivamo. 2.1 Model robota Regulacijska proga robota je nelinearna, saj model robota 3. ALGORITEM PO VZORU OBNAŠANJA zapišemo kot člen drugega reda [17]. Pomeni, da običajni NETOPIRJEV metodi nastavljanja regulatorja, npr. Bodejeva metoda [9] in krivulja lege korenov [3] pri načrtovanju nista več upo- Algoritem po vzoru obnašanja netopirjev (angl. Bat Algori- rabni Enačba (2) predstavlja model robota. thm, krajše BA) je novejši predstavnik optimizacijskih algo- ritmov po vzoru iz narave. Nastal je leta 2010 pod okriljem a1+2a2cos(q2) a3+a2cos(q2) matematika Xin-She Yanga. Algoritem temelji na sposob- τ J mot1 m1 n1 + = n1 n1 · τ a a nosti navigacije netopirjev v popolni temi. Netopirji pred- mot2 3 +a2 cos(q2 ) J 3 +J3o n m2 n2 + 2 n2 (2) stavljo eno redkih bioloških vrst, ki se v naravi orientirajo s  −a  2 ˙ q2(2 ˙ q1+ ˙ q2)sin(q2) ¨ q1 n a b ¨ q e pomočjo t.i eholokacije. Pojav označuje periodično oddaja- + 2 + 1 · 1 + ¨ q  2  = 2 a2sin(q2) ˙ q1 c d ¨ q2 f nje kratkih ultrazvočnih pulzov, odbijajočih se od plena ali n2 StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 14 ovire in merjenjem časa odmeva. Posledično lahko ob znani Algoritem 1 Algoritem na osnovi obnašanja netopirjev hitrosti potovanja zvoka po zraku določimo oddaljenost od Vpis: Populacija netopirjev xi = (xi1, . . . , xiD)T za i = 1 . . . N p, plena ali ovire. M AX F E. Izpis: Najboljša rešitev xbest in njena vrednost fmax = Obnašanje netopirja lahko zapišemo z matematičnim mode- max(f (x)). lom, ki temelji na naslednjih osnovnih pojmih: 1: init bat(); 2: eval = vrednoti novo populacijo; 3: fmax = išči najboljšo rešitev(xbest ); • dejanski frekvenci oddajanja Qi, 4: while termination condition not met do 5: for i = 1 to N p do • dejanski hitrosti leta v(t) in 6: y = generiraj novo rešitev(x i i); 7: if rand(0, 1) < ri then • dejanskemu položaju netopirja x(t), 8: y = izboljšaj najboljšo rešitev(xbest ) i 9: end if { lokalno iskanje } 10: fnew = vrednoti novo rešitev(y); medtem ko naključni let netopirja zapišemo kot kombinacijo 11: eval = eval + 1; 12: if f treh enačb: new ≤ fi and N(0, 1) < Ai then 13: xi = y; fi = fnew; Q 14: end if { shrani najboljšo rešitev pogojno } i = Qmin + (Qmin − Qmin ) · β, (5) 15: fmax =išči najboljšo rešitev(xbest ); 16: end for v(t+1) = v(t) + x(t) − x(t) · Q 17: end while i i i best i, (6) x(t+1) = x(t) + v(t), (7) i i i Slednji ima najvišjo vrednost ocenjevalne funkcije in pred- stavlja trenutno najboljšo globalno rešitev. Jedro algoritma kjer Qmax in Qmin predstavljata zgornjo in spodnjo mejo predstavlja globalna zanka, ki se izvaja dokler ne presežemo frekvence inicializiranih ob zagonu, krmilni parameter β je maksimalnega števila iteracij, oz. dovolj kakovostne predpi- naključno število generirano v intervalu [0, 1] in x(t) trenu- best sane rešitve. V tej zanki iz vsakega posameznika generiramo tna najboljša rešitev. novo rešitev s pomočjo preiskovanja. Glede na verjetnost, da emisija pulzov pade pod določeno mejo če je ta dovolj blizu Proces iskanja v algoritmu BA je odvisen od dveh procesov, rešitve pa nadaljujemo tudi na proces izkoriščanja, imeno- tj. preiskovanja (angl. exploration) in izkoriščanja (angl. vanega tudi lokalno iskanje. Novo pridobljeno rešitev shra- exploitation). Preiskovanje je močnejše zlasti ob začetku op- nimo le, če je glasnost oddajanja ultrazvočnih pulzov dovolj timizacije, ko so položaji posameznikov razmetani naključno majhna, kar pomeni, da se netopir nahaja blizu plena. V po preiskovalnem prostoru. Izkoriščanje pomeni, da začne nasprotnem primeru rešitev zavržemo. preiskovalni proces izboljševati najdeno rešitev običajno z metodami lokalnega iskanja. Vsak posameznik se pri pre- Algoritem išče optimalne parametre za nastavitev regula- iskovanju prostora giba v smeri trenutne najboljše rešitve, torja v omejenem definicijskem območju, ki preprečuje ne- kar v naravi pomeni, da netopir oddaja ultrazvočne pulze stabilno delovanje robota. Po vsakem izračunanem premiku visokih glasnosti Ai, ki posledično potujejo dlje. Te pulze novo nastale parametre vpiše v regulator ter počaka na izvr- oddaja le nekajkrat v sekundi, npr. osem do desetkrat, kar šitev le-teh. Kriterijska funkcija vsako dvojico parametrov definiramo s parametrov emisija pulzov ri. Ko netopir opazi ovrednoti ter rezultat posreduje algoritmu. Vsako ovredno- plen, se mu začne približevati, glasnost začne upadati, med- tenje zaradi mehanskih omejitev traja natančno deset se- tem ko emisija pulzov raste. V tej fazi začne preiskovalni kund, zato za nas hitrost izvajanja algoritma ni pomembna. algoritem preiskani prostor rešitev izkoriščati. Matematično Vsekakor pa s povečevanjem števila posameznikov ter ge- obstajata torej dva računska postopka za opis obeh kom- neracij premo sorazmerno povečujemo tudi čas potreben za ponent preiskovalnega proces, tj. preiskovanje je zapisano optimizacijo. v enačbah (5)-(7), medtem ko izkoriščanje sledi zapisu v enačbi (8): 4. REZULTATI xnovi = xstari + · ¯ A(t). (8) V tem poglavju predstavljamo rezultate pridobljene na re- alni laboratorijski aplikaciji. Zaradi stohastičnosti algoritma Glasnost Ai in emisija pulzov ri se sicer v originalnem al- je posnetih več odzivov na stopnično funkcijo, čeprav se v goritmu spreminjata, vendar se je za potrebe naše optimi- praksi uporablja le osnovno testiranje, ko deluje robot brez zacije izkazalo najbolje, da oba parametra nastavimo fiksno prenihaja. Rezultati so bili posneti s pomočjo orodja MA- in s tem uravnavamo mejo med procesoma preiskovanja in TLAB/Simulink ter vmesniške kartice DSP-2 Roby. Prika- izkoriščanja. S tem dosežemo nekoliko nižjo konvergenco zani rezultati veljajo za dvoosnega robota (n = 2). Krmilni v začetnih generacijah. Oba parametra sta v originalnem parametri algoritma BA so bili nastavljeni med eksperimenti algoritmu odvisna od funkcijskih predpisov, ki pa začetno na naslednje vrednosti: vrednost parametra v nekaj generacijah fiksirata na kon- stantne vrednosti, zato se parametra v poznejših generaci- • število posameznikov Np = 10, jah obnašata podobno, kot če bi ju fiksirali. Vse omenjene enačbe lahko strnemo v optimizacijski algoritem, katerega • število iteracij ngen = 10, psevdokod je prikazan v algoritmu 1. Algoritem začnemo z • emisijo pulzov ri = 0.1, inicializacijo naključnih posameznikov. Populacijo ovredno- timo ter poiščemo posameznika z najkakovostnejšo rešitvijo. • glasnost oddajanja pulzov Ai = 0.9 in StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 15 • faktor skaliranja (frekvenca) Qi = {0.5, 1.5}. zaostruje uporabo aplikacije. Predpostavili smo, da mora biti algoritem in njegova uporaba enostavna in funkcionalna, V sklopu eksperimentalnega dela smo ozvedli tri teste, ki kar pa nekoliko slabša kakovost posameznih rezultatov. V se med seboj razlikujejo po različnih vrednostih zahtevanih oči bode tudi podnihaj, ki se pojavi takoj po dosegu zah- prenihajev: tevane vrednosti in dodatno dodeljuje manevrski prostor za finejšo obdelavo. • prvo testiranje: P1 = 0 %, P2 = 0 %, 4.2 Drugo testiranje • drugo testiranje: P1 = 10 %, P2 = 10 % in Drugo testiranje predstavljata tabela 2 in slika 3. Testira- nje je bilo izvedeno za zahtevana prenihaja P • 1 = 10 % in tretje testiranje: P1 = 15 %, P2 = 25 %. P2 = 10 %. Nastavljanje parametrov se za ta režim v praksi ne uporablja več, mi smo ga uporabili kot dodaten optimi- Vsa testiranja so prikazana tabelarično in grafično. zacijski problem za podkrepitev rezultatov. 4.1 Prvo testiranje Prvo in najosnovnejše testiranje je prikazano v tabeli 1 in Tabela 2: Drugo testiranje sliki 2. Vsaka tabela in slika na kratko opisujeta dogajanje Izmerjeni rezultati 1. os 2. os po končani optimizaciji, vhodni podatki v realni laborato- Vrednost ocenjevalne funkcije f rijski sistem sta optimizirani dvojici. Velja omeniti tudi za- i 0.9739 0.9854 Vrednost prenihaja Overi 0.10733 0.10237 nimivost aplikacije, katero predstavlja povratni gib robota, Vrednost statičnega pogreška Essi 0.00579 0.00113 izveden s preprostim P-regulatorjem za gib nazaj na ničelno Vrednost nastavitvenega časa T imei 0.714 0.444 točko. Tabela 2 kaže končne rezultate drugega testiranja. Razvidno Tabela 1: Prvo testiranje je, da je v tem primeru nekoliko kakovostneje nastavljena Izmerjeni rezultati 1. os 2. os druga os. O tem priča višja vrednost ocenjevalne funkcije. Vrednost ocenjevalne funkcije fi 0.96516 0.98324 Tudi prenihaja sta v veliki meri natančno načrtana, ma- Vrednost prenihaja Overi 0.0187 0 ksimalna napaka znaša zgolj 0.7 %. Statični pogrešek je Vrednost statičnega pogreška Essi 0.00058 0.00544 nekoliko ohlapneje načrtan v primerjavi s prvim primerom. Vrednost nastavitvenega časa T imei 0.906 0.504 Ta sicer znaša precej manj za drugo os, medtem ko se je za prvo os enormno povečal. Nastavitveni čas je v obeh primerih krajši, kar dodatno izboljšuje vrednost ocenjevalne Testiranje je bilo dokaj uspešno izvedeno, kar dokazuje tudi funkcije. visoka vrednost povprečne ocenjevalne funkcije. Prenihaj prve osi je bil nastavljen nekoliko nenatančno, medtem ko je prenihaj druge osi natančno zadel zahtevano nastavitev. Statični progrešek je pomemben del robotove natančnosti. Višjo natančnost je dosegel s prvo osjo, saj ta beleži nižjo stopnjo napake. Nastavitveni čas je parameter, ki pove kako robot zaniha blizu rešitve. Daljši kot je nastavitveni čas, slabša je kakovost parametrov. Določa ga ozko tolerančno območje, tj. hitreje kot se robot ustali v tem območju, krajši nastavitveni čas ga odlikuje. Slika 3: Drugo testiranje Grafično predstavljen odziv dopolnjuje kakovost tabelarično predstavljenih rezultatov. Odziv je iz grafičnega stališča ka- kovostneje optimiziran kot prvi, največ k temu pripomore krajši nastavitveni čas. Iz fizikalnega stališča je treba ome- niti, da so začetna eksperimentalna testiranja krmilnih pa- rametrov potekala prav na tem režimu delovanja - P1 = 10 Slika 2: Prvo testiranje % in P2 = 10 %. Pomeni, da so ti parametri najugodnejši za opisovano testiranje, medtem ko za druga testiranja ne veljajo več v popolni meri. To pa je prednost in obenem Iz slike 2 je razvidno, da se je robot uspešno premaknil za slabost nastavljanja krmilnih parametrov. kot dva radiana, vendar v okolici nekoliko zanihal in povzro- čil dolg nastavitveni čas, kar se sklada s tabelo 1. Z doda- tnim eksperimentalnim nastavljanjem krmilnih parametrov 4.3 Tretje testiranje bi lahko nastavitveni čas drastično izboljšali, vendar oteže- Tretje testiranje poosebljata tabela 3 in slika 4, zahtevana vali preprosto uporabo naše aplikacije. Poleg tega bi bilo kombinirana prenihaja znašata P1 = 15 % in P2 = 25 potrebno nekajkrat ponastaviti spekter možnih števil iz ka- %. Tabelarični rezultati tretjega testiranja prinašajo glede terih pridobivamo posamezne člene dvojic parametrov in jih na vrednost ocenjevalne funkcije pozitivne lastnosti, ven- čimbolj približati k optimalnim nastavitvam, kar dodatno dar zahtevajo glede na natančnost načrtanega prenihaja in StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 16 Tabela 3: Tretje testiranje 6. REFERENCES Izmerjeni rezultati 1. os 2. os [1] C. Darwin. R.(1859): On the origin of species by Vrednost ocenjevalne funkcije fi 0.95527 0.97839 means of natural selection. Murray. London, 1871. Vrednost prenihaja Overi 0.16721 0.25872 [2] A. E. Eiben and J. E. Smith. Introduction to Vrednost statičnega pogreška Essi 0.00202 0.00027 Vrednost nastavitvenega časa T ime evolutionary computing. Springer Science & Business i 1.222 0.606 Media, 2003. [3] W. R. Evans. Control system synthesis by root locus trajanja nastavitvenega časa prve osi dodatno optimizacijo. method. American Institute of Electrical Engineers, Kakovostno so načrtani vsi izhodni podatki za drugo os. Transactions of the, 69(1):66–69, 1950. Pojav dolgega nastavitvenega časa in posledično nižje oce- [4] D. Fister. Načrtovanje samonastavljivega regulatorja 2 DOF robota s pomočjo BA algoritma. Diplomsko delo : Univerza v Mariboru, Fakulteta za strojništvo, 2015. [5] I. Fister, D. Strnad, X.-S. Yang, and I. Fister Jr. Adaptation and hybridization in nature-inspired algorithms. In Adaptation and Hybridization in Computational Intelligence, pages 3–50. Springer, 2015. [6] I. Fister Jr, D. Fister, and X.-S. Yang. A hybrid bat algorithm. arXiv preprint arXiv:1303.6310, 2013. Slika 4: Tretje testiranje [7] D. E. Goldberg and J. H. Holland. Genetic algorithms and machine learning. Machine learning, 3(2):95–99, njevalne funkcije prikazuje tudi slika 4. Čeprav je druga os 1988. uspešno nastavljena, zaradi velikega prenihaja in vztrajno- [8] A. Jagarinec. Adaptivni regulator z mehko logiko za stnih mas vpliva na prvo os. Znano je namreč, da sta obe osi dvoosni SCARA mehanizem. Diplomsko delo : medsebojno mehansko sklopljeni, kar posledično zmanjšuje Univerza v Mariboru, Fakulteta za elektrotehniko, kakovost pridobljenih podatkov druge osi. računalništvo in informatiko, 2005. [9] L. H. Keel and S. P. Bhattacharyya. A bode plot characterization of all stabilizing controllers. 5. SKLEP Automatic Control, IEEE Transactions on, Z našo aplikacijo smo hoteli pokazati, da so optimizacijski 55(11):2650–2654, 2010. algoritmi po vzoru iz narave, konkretneje algoritem BA, pri- [10] J. Kennedy, J. F. Kennedy, R. C. Eberhart, and merni za nastavljanje parametrov regulatorjev. Algoritem Y. Shi. Swarm intelligence. Morgan Kaufmann, 2001. BA, ki je znan zaradi svoje enostavne implementacije ter [11] M. Kolar. Vodenje SCARA robota z mehko logiko. hitre konvergence, poleg zvezne optimizacije matematičnih Diplomsko delo : Univerza v Mariboru, Fakulteta za modelov ponuja oporo tudi takim vrstam problemov. Četudi elektrotehniko, računalništvo in informatiko, 2005. regulator v vseh treh primerih ni bil optimalno nastavljen, [12] H. Makino, N. Furuya, K. Soma, and E. Chin. izstopajo namreč rezultati prve osi, smo bili objektivno z Research and development of the scara robot. In dobljenimi rešitvami zadovoljni. Vsekakor bi s povečanjem Proceedings of the 4th International Conference on števila posameznikov v populaciji ter števila iteracij lahko Production Engineering, pages 885–890, 1980. pričakovali kakovostnejše rezultate, vendar bi po drugi strani povečali potreben optimizacijski čas. [13] T. Slanič. Genetski regulator za dvoosnega SCARA robota. Diplomsko delo : Univerza v Mariboru, Rezultati poskusov so pokazali, da najbolj izstopa dolg na- Fakulteta za elektrotehniko, računalništvo in stavitveni čas prve osi, saj ta predstavlja nosilno oporo tudi informatiko, 2006. drugi osi. S hitrim spreminjanjem položaja in vztrajnostnih [14] A. M. Turing. Intelligent machinery, a heretical momentov pa slednja vpliva na prvo, kar predstavlja glavno theory. The Turing Test: Verbal Behavior as the mehansko težavo. Težavo bi lahko rešili z manjšanjem regu- Hallmark of Intelligence, page 105, 1948. lacijskega I-člena, oz. ponovno optimizacijo z ožjim nabo- [15] J. Čas. Izdelava zveznega nevronskega sliding-mode rom razpoložljivih vrednosti tega člena (Kv regulatorja za teleoperiranje SCARA robota. 1). Diplomsko delo : Univerza v Mariboru, Fakulteta za V prihodnje želimo algoritem BA hibridizirati s strategijami elektrotehniko, računalništvo in informatiko, 2006. diferencialne evolucije in tako izboljšati rezultate optimiza- [16] M. Čurkovič. Vgrajeni sistemi DSP/FPGA v sistemih cije [6]. Trenutno so v teku tudi testiranja genetskega al- vodenja. Magistrsko delo Univerza v Mariboru, goritma (GA), optimizacije z roji delcev (PSO) in diferenci- Fakulteta za elektrotehniko, računalništvo in alne evolucije (DE). Dodatno izboljšavo predstavlja adapta- informatiko, 2010. cija krmilnih parametrov, kjer postopek ročnega nastavlja- [17] R. Šafarič and A. Rojko. Inteligentne regulacijske nja parametrov avtomatiziramo ter s tem eliminiramo pred- tehnike v mehatroniki. Univerza v Mariboru, Fakulteta časno konvergenco v lokalne optimume [5]. Prav ta lastnost za elektrotehniko, računalništvo in informatiko, 2005. predstavlja glavno težavo omenjenega algoritma, saj optimi- [18] X.-S. Yang. A new metaheuristic bat-inspired zacija teče dokler izboljšujemo trenutno najboljšo najdeno algorithm. In Nature inspired cooperative strategies for rešitev. optimization (NICSO 2010), pages 65–74. Springer, 2010. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 17 StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 18 Analiza sentimenta z uporabo emotikonov in besednih zvez Tadej Jerovšek Tadej Ganza Fakulteta za elektrotehniko Fakulteta za elektrotehniko računalništvo in informatiko računalništvo in informatiko Smetanova ulica 17, 2000 Smetanova ulica 17, 2000 Maribor Maribor Maribor, Slovenija Maribor, Slovenija tadej.jerovsek@student.um.sitadej.ganza@student.um.si Tomaž Cebek Martin Kraner Borko Bošković Fakulteta za elektrotehniko Fakulteta za elektrotehniko Fakulteta za elektrotehniko računalništvo in informatiko računalništvo in informatiko računalništvo in informatiko Smetanova ulica 17, 2000 Smetanova ulica 17, 2000 Smetanova ulica 17, 2000 Maribor Maribor Maribor Maribor, Slovenija Maribor, Slovenija Maribor, Slovenija tomaz.cebek@student.um.si martin.kraner1@student.um.si borko.boskovic@um.si POVZETEK Splošni pojmi V članku smo obravnavali analizo sentimenta kratkih sporo- Therory čil popularnega spletnega družbenega omrežja Tweeter1, oz. Languages ”tweetov”. Sentimentalno analizo smo izvajali nad lematizi- Experimentation ranimi besedami sporočila z uporabo ustaljenih metod. Ker so sporočila kratka (omejena na 140 znakov), je sentiment težko oceniti. Da bi dobili več informacij, smo v algoritem 1. UVOD vključili emotikone (“hashtag“), ter bazo fraz in besednih Ljudje v digitalni dobi vse pogosteje objavljajo svoje misli zvez, ki pri analizi po besedah dajejo napačen rezultat. Po- in kaj počnejo na javnih spletnih mestih. Med temi informa- sebej smo analizirali sentiment besedila in emotikonov in ga cijami podajo svoje mnenje glede določenih dogodkov, izdel- nato s pomočjo uteži združili v eno končno oceno. Pred- kov, politikov in podobno. Analiza sentimenta se ukvarja z stavljen algoritem smo primerjali z algoritmom iz literature ekstrakcijo teh informacij, kar omogoča hitro in lahko ugota- v večih kategorijah, kot so samo analiza besedila, analiza vljanje mnenja velikega števila ljudi glede določene tematike. z emotikoni ter naša izboljšana rešitev. Dobljeni rezultati Primer tega so lahko tudi možnosti zmage na volitvah, kar kažejo, da je naš algoritem dosegel za 1,35% boljšo oceno se v času volitev na medijih “prodaja“ kot med. metrike F1. Pri tem je več pristopov, ki pa v veliki večini temeljijo na besedilni analizi. Slabost tega pristopa je, da je praktično Kategorije in opisi teme nemogoče ugotoviti informacije, ki bi jih v naravnem govoru H.4 [Information Systems Applications]: Miscellane- sporočevalec podal s telesnim govorom. Tako kaj hitro na- ous; H.3.1 [Information Storage and Retrieval]: Con- pačno razvrstimo sentiment, ko govorec uporabi sarkazem tent Analysis and Indexing—Linguistic processing ali kakšno drugo retorično obliko. ; I.2.7 [Artificial intelligence]: Natural Language Proces- sing—Language parsing and understanding, Text analysis Kot dopolnilo klasičnemu pisanju je profesor Scott Fahlman leta 1982 poskusil uporabiti prva emotikona ”:-)”in ”:-(”. S tema je predlagal, da bi pisec izražal razliko med resno mi- slijo, ali šalo. Ta koncept je hitro postal zelo priljubljen 1Dostopno na spletnem naslovu http://www.tweeter.com in se je razširil po celotnem svetovnem spletu, kjer danes emotikoni predstavljajo splošen koncept izražanja. Zaradi uporabe emotikonov, je mogoče iz kratkih sporočil iz- vedeti precej bolj podrobno informacijo o sentimentu kakor iz klasičnih besedilnih sporočil, vendar je na tem področju malo poudarka. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 19 talna vrednost. Tabela 1: Označevanje emotikonov Simbol Določen sentiment Vrednost xS >.> :# Negativno -1 Za iskanje smo uporabili regularne izraze (angl. regular :’( :@ :[ Negativno -1,5 expresion). Najprej smo uredili emotikone tako, da smo l8Ô >:-) >//< Pozitivno 1 najprej imeli najdaljše, nato pa jih zaporedno dodajali v :-) ♥ ♥ :D Pozitivno 1,5 regularni izraz. S tem smo zagotovili, da se v primeru, da <:3( ) >—ˆ-*< Neznano (odstranjeno) / se začnejo na enako črko, najdejo tudi krajši. Najdene emo- tikone smo omejili tudi glede na predhodni znak. Veliko emotikonov je namreč sestavljenih tako, da se lahko zame- 2. SORODNA DELA nja tudi del normalne besede kot emotikon. To smo rešili V članku [6] je predstavljen model, ki združuje ročno ozna- tako, da smo za pogoj postavili, da mora biti emotikon na čene podatke s šumnimi podatki o emotikonih. Uporabili so začetku vrstice, ali mora biti predhodni znak del drugega model učen na ročno označenih podatkih, za glajenje pa so emotikona, ali pa mora biti predhodni znak nečrkovni. bili uporabljeni šumni podatki. ”((: DD)|(: D)|(: \))|(: S))” V [4] so sentiment izačunavali iz tweetov in forum sporočil, Primer regularnega izraza za iskanje emotikonov. kjer so imeli slovar besed z označenimi sentimenti ter tudi ročno označene določene emotikone. Sentiment so določali Za ocenjevanje sentimenta emotikonov v sporočilu, smo poi- glede na odstavke, kjer so sentiment utežili s prisotnimi emo- skali njihove ocene sentimenta v bazi, ter nato sešteli njihove tikoni tako, da je sentiment emotikona prevladal nad senti- vrednosti. To nam je omogočilo natančnejši izračun verje- mentom besedila (pozitivno ali negativno glede na razliko tnosti sentimentalne vrednosti in prav tako izločiti sporočila med sentimentom besedila in sentimentom emotikonov). z enakomernim pozitivnim in negativnim sentimentom oz., odstraniti nevtralna sporočila. 3. POSTOPEK ANALIZE V tem poglavju opisujemo naš algoritem za analizo senti- Za namene sentimentalne analize smo pripravili korpus, kjer menta. Najprej bomo opisali obdelavo emotikonov, saj smo so bili vsi emotikoni odstranjeni, da smo se izognili napakam le te uporabili v koraku pridobivanja besedil s Twitterja. pri lematizaciji oz. določevanju sentimenta besedila. Nato sledi opis algoritma za predobdelavo in analizo senti- menta. Na koncu podajamo še uporabljen način združevanja 3.2 Pridobivanje tweetov sentimentalnih analiz v skupno oceno. Sama sporočila družabnega omrežja Twitter smo pridobivali s pomočjo programskega vmesnika (angl. API), ki je na- 3.1 Izgradnja baze sentimentalno označenih menjen za razvijalce. Vmesnik deluje po arhitekturi REST emotikonov (angl. Representational State Transfer) preko spletnega pro- tokola HTTP (angl. Hypertext Transfer Protocol) kjer se V namen izboljšane analize sentimenta smo ustvarili bazo podatki prenašajo v formatu JSON. Za to komunikacijo smo emotikonov, ki imajo označen sentiment. Našli smo 6 ob- uporabili programsko knjižnico CoreTweet [10]. Zaradi ome- stoječih baz, ki se nahajajo na spletu [3, 7, 8, 9, 11, 12]. jitev obstoječih orodij za analizo slovenskega jezika smo se Uporabili smo format XML, zaradi potrebe po čim lažji omejili samo na tweete angleškega jezika. prenosljivosti. Združili smo vseh šest baz, pri čemer smo podvojene emotikone odstranili. Vse baze niso imele ozna- Izbrali smo 150 tweeter uporabnikov, ki dokaj pogosto upo- čenih sentimentalnih vrednosti, zato smo vse emotikone v rabljajo emotikone in od vsakega pridobili 200 najnovejših bazi tudi ročno označi, pri čemer smo uporabili za negativni sporočil (omejitev API-ja). Vsa pridobljena sporočila smo sentiment naslednje vrednosti: -1,5 in -1,0, za emotikone, združili v en korpus in dobili 30.000 različnih sporočil, te ki se ne morejo pojavit v kontekstu s pozitivnim sentimen- smo s pomočjo postopka opisanega v prejšnjem poglavju fil- tom -1,5 in za emotikone s pozitivnim sentimentom, 1,5 in trirali tako, da smo obdržali le tista, ki so dejansko vsebo- 1,0. Primer označenih emotikonov je naveden v tabeli 1. vala emotikone z nezanemarljivimi sentimentalnimi utežmi. Dobili smo 3.041 sporočil, ki so vsebovala emotikone. Sen- Iz obstoječih baz smo dobili 1411 emotikonov, katere smo timent teh sporočil so ločeno ocenili 4 ljudje, avtorji tega ročno označili. Iz te baze smo odstranili 465 emotikonov, ki članka, študenti na magistrskem študiju računalništva. Te ne nosijo sentimentalne vrednosti. Odstraniti smo še emo- vrednosti smo nato združili v eno referenčno oceno. tikone, katerih se ne da uporabit v korpusih od Twitterja. Problem namreč nastane pri emotikonih, ki se pričnejo z znakom ”@”, saj se tako označujejo osebe, na katere se pisec 3.3 Lematizacija besedila sklicuje v tweetu, s čimer smo odstranili nadaljnjih 31 emo- Enolična določitev sentimentalne ocene besedila je le možna, tikonov. V končni bazi smo tako dobili 919 emotikonov, ki če lahko večini posameznih besed znotraj besedila določimo so bili primerni za korpuse iz Twitterja in so nosili ročno sentimentalno oceno ne glede na sklanjatev. Postopku spre- označen sentiment. minjanja besede nazaj v osnovno obliko imenujemo lemati- zacija oz. krnjenje in besede, ki jih dobimo leme oz. krni. V okviru tega dela smo se osredotočili le na sporočila, ki vse- bujejo emotikone. V vseh sporočilih smo iskali emotikone in Ker smo želeli biti neodvisni od spletne povezave smo se od- odstranili tista sporočila, ki niso vsebovala emotikonov, ali ločili za programsko knjižnico za opravljanje tega postopka so vsebovala emotikone katerim se ni dala določiti sentimen- po imenu LemmaGen [5]. Knjižnica tudi v določenih prime- StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 20 Tabela 2: Lematizacija z LemmaGen. Tabela 3: Tipični primeri kako uporabimo emoti- Izvorna beseda Lematizirano Brez opozoril kone za prikaz sentimenta. don’t do+not do not Poved Emotikon Sentiment Don’t Do+not Do not I love my work :-D Okrepitev pozitiven they’re theybe they be The movie was bad :-D Negacija pozitiven :-D I got a promotion Samo sentiment pozitiven - - I love my work Negacija negativen rih opozori na besede oz. besedne zveze na katere moramo The movie was bad - - Okrepitev negativen paziti s opozorilnim znakom +. S tem želi povedati, da je I got a promotion - - Samo sentiment negativen bila to samo ena beseda oz. besedna zveza pred lematizacijo. To informacijo uporabimo za bolj uspešno oceno sentimenta. Nekateri primeri teh besednih zvez so navedeni v tabeli 2. Tabela 4: Pravilnost sentimenta. Pričakovan Ocenjen Pravilnost 3.4 Opravljanje sentimentalne analize besedila > 0,5 > 0,5 Pravilen Sentimentalno analizo besedila smo opravili s pomočjo dveh < -0,5 < -0,5 Pravilen orodij za analizo besedila. Prvo izmed takšnih orodij, je > 0,5 < 0,5 Nepravilen OpenNLP [1]. To orodje smo uporabili za določanje tipa < -0,5 > 0,5 Nepravilen besed, uporabljenih v tweetih (angl. Part-of-Speech taging). > -0,5 in < 0,5 / Neupoštevan Drugo orodje, s katerim smo si pomagali pri opravljanju sen- timentalne analize besedila, je SentiWordNet (SWN) [2]. Sentimentalno analizo smo tako opravili, da smo s pomo- 3.4.1 Združevanje sentimenta besedila in emotiko- čjo OpenNLP določili tip besede (npr. pridevnik, glagol...), ker pa OpenNLP omogoča več možnosti klasifikacije, kot pa nov SWN smo morali klasifikacije OpenNLP združiti v skupine, Združevanje obeh vrednosti sentimenta smo opravili kot je ki so se ujemale s tipi besed, ki jih SWN pozna. opisano v [4]. Za združevanje smo predpostavili 6 tipičnih situacij, kot prikazuje tabela 3. V tem koraku smo imeli na voljo posamezne besede in tip posamezne besede. S pomočjo teh podatkov je SWN vr- Kot je prikazano v tabeli 3 smo združili vrednosti sentimenta nil vektor pozitivnega in negativnega sentimenta iskane be- emotikona in besedila glede na ustrezno situacijo. Situacijo sede. Ker pa enačba vektorja SWN dovoljuje tudi izračun smo določili glede na določeno vrednost sentimenta besedila, objektivnega sentimenta (angl. objective), smo lahko dolo- ter emotikona. V kolikor sta oceni besedila in emotikonov čili tudi objektivnost posameznih besed, kot prikazuje na- enako predznačeni, vrednost sentimenta okrepimo. V ko- slednja enačba: likor sta različno predznačeni, vrednost analize sentimenta besedila negiramo. V primeru, da analiza besedila ne poda vrednosti sentimenta, pa vzmamemo samo vrednost analize emotikonov. Kot dodatno izboljšavo smo tudi tukaj uvedli 1 = pozi + negi + obji. (1) prag minimalne vrednosti sentimenta za posamezno klasifi- kacijo. V tej enačbi pozi pomeni pozitivni sentiment i -te besede, negi negativni sentiment i -te besede, ter obji prikazuje objektivni sentiment i -te besede. Na te vrednosti se bomo 4. REZULTATI EKSPERIMENTA v nadaljevanju sklicevali kot na 3-dimenzionalni vektor. Najprej smo ročno označili sentimentalne vrednosti vseh twe- etov. Učinkovitost smo ocenili s primerjavo ocenjenega sen- Sentiment posameznega tweeta smo določili s povprečnimi timenta ter izračunanega. V primerjavi ustreznosti smo vrednostmi vektorjev besed, ki so se pojavile v tweetu. Kot ignorirali zaokrožitveno napako, ob ročno določitvi smo se izboljšavo smo določili prag izrazitosti sentimenta, ki je po- omejili na 5 različnih vrednosti: {-1,5; -1; 0; 1; 1,5} med- treben da smo besedo vključili v izračun vrednosti pozitiv- tem ko so se izračunane vrednosti lahko pojavijo kjerkoli nega in negativnega sentimenta tweeta. Prag sentimenta v tem intervalu. Iz tega razloga smo preverjali ujemanje smo izračunali z opazovanjem absolutne razdalje med pozi sentimenta v predznaku (pozitiven/negativen). Rezutati so in negi i -te besede. V kolikor vrednost ni prekoračila praga, prikazali 97,28% uspešnost po metriki F1. Ob pregledu, smo upoštevali le njeno objektivno vrednost. smo opazili, da uporabniki uporabljajo besedne zveze s ka- terimi svoj sentiment bolj izrazito izražajo. Iz stališča stroja Pridobljeni vektor smo nato normalizirali s pomočjo števila te besede kot tudi njihove kombinacije ne nosijo velikega po- besed, ki so bile uporabljene pri izračunu posamezne vredno- mena, vendar iz stališča uporabnika pa prikazujejo visok na- sti sentimenta. Končni sentiment besedila smo nato dobili bor informacij. Izbrali smo 43 tovrstnih besednih zvez, ki so tako, da smo od vrednosti pozitivnega sentimenta odšteli se pojavljale v našem naboru tweetov. Tem besednim zve- vrednost negativnega sentimenta. Ker pa se ta vrednost zam smo določili sentimentalno vrednost, katero smo dodali nahaja na intervalu med [-1, 1] medtem, ko se vrednosti predhodno izračunani vrednosti. Po ponovnem pregledu so za emotikone nahajajo na intervalu [-1,5, 1,5] smo morali rezultati prikazali 98,63% uspešnost s čimer smo število ne- končno vrednost skalirati z 1,5. Tako smo dobili interval, pravilno razvrščenih tweetov zmanjšali skoraj za polovico. kjer vrednosti večje od 0, pomenijo pozitiven sentiment, vre- dnosti nižje od 0 pa pomenijo negativen sentiment. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 21 Tabela 5: Tabela uspešnosti zaznave sentimenta. Tabela 6: Tabela rezultatov metrik. Sentiment besedla Metoda [4] Naša metoda Sentiment besedla Metoda [4] Naša metoda TP 447 1181 1191 A 0,2994 0,7910 0,7977 FP 175 40 17 P 0,7186 0,9672 0,9859 FN 760 26 16 R 0,3703 0,9785 0,9867 TN 111 246 269 F1 0,4888 0,9728 0,9863 Σ 1493 1493 1493 5. ZAKLJU ČEK 4.1 Primerjava algoritmov V prispevku smo predstavili algoritem za analizo sentimenta V našem eksperimentu bomo primerjali naši algoritem z al- nad objavami na Twitterju. Ta vsebuje več korakov, ki goritmom iz [4]. Ker smo uporabili drugačen korpus kakor vključuje sentimenta besedila in emotikonov. Ta smo zdru- avtorji omenjenega članka, smo implementirali tudi njihov žili v skupno oceno, nato pa smo za primere, kjer obe analizi algoritem, da smo lahko primerjali uspešnost. Za vsako iz- sentimenta dajeta napačno razpoznavo, dodali še popravke med metod smo izračunali natančnost, preciznost, priklic in ocene v obliki razpoznavanja besednih zvez, ki spremenijo metriko F1. vrednost združene ocene za absolutno vrednost. Analiza sentimenta besedila je dala najslabše rezultate, analiza z Po vrsti smo preiskusili naslednje algoritme: emotikoni je uspešnost več kot podvojila. Dodatno smo pri- kazali popravljanje združene ocene z besednimi zvezami, s čimer smo pridobili dodatna 1,35% uspešnosti po metriki 1. Metoda iz članka brez emotikonov (analiza sentimenta F1. besedila) 2. Metoda iz članka z emotikoni 3. Naša metoda z emotikoni in besednimi zvezami V eksperimentu smo uporabili bazo 1493 ročno označenih tweetov, ločeno s strani 4-ih oseb (avtorjev članka), oz. v dveh prehodih, katera smo nato povprečili. Rezultate oznak smo potem združili v eno referenčno oceno sentimenta. Naša uspešnost napram samemu sentimentu besedila in osnovni metodi [4] je prikazana v slikah 1, 2, 3, 4 ter tabelah 5 in 6. V osnovi smo z analizo samega sentimenta besedila dobili boljše rezultate kakor v [4], kar kaže, da so naša sporočila bila nekoliko bolj jasna za analizo brez emotikonov. Pri tem smo uporabili vrečo besed, kakor v primerjanem delu. Slika 1: Natančnost klasificiranih kratkih sporočil. Pri analizi s filtriranjem z emotikoni smo dobili podobne re- zultate kakor v [4], vendar ne moremo narediti primerjave zaradi različnih korpusov. Naši rezultati so bili par odstot- kov slabši, saj ljudje na Twitterju emotikone uporablajo iz navade, ne z namenom sporočanja svojega počutja. Kljub temu smo delež pravilno klasificiranih več kot podvojili s predlagano metodo. Do sedaj opisane metode so narobe klasificirale 199 sporo- čil (11,3%). Metodi iz [4] namreč ocenjujeta sentiment na podlagi vreče besed, kjer se pa informacija besednih zvez izgubi. Kot nadaljnjo izboljšavo smo poskusili omogočiti pravilno klasifikacijo z informacijo le teh. V napačno raz- poznanih smo nato iskali besedne zveze s katerimi smo pri samem označevanju sklepali na nasprotno vrednost senti- menta. Te smo nato uporabili za popravljeno klasifikacijo, pri čemer vsaka besedna zveza spremeni vrednost analize sentimenta za določeno vrednost. Pri tem smo uspeli 199 napačno razpoznanih tweetov znižali na 168 napačno raz- poznanih tweetov. Slika 2: Metrika F1 za uspešnost razpoznav senti- menta z različnimi metodami. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 22 6. VIRI [1] Apache Software Foundation. OpenNLP. http://https://opennlp.apache.org, Maj 2015. [2] S. Baccianella A. Esuli, in F. Sebastiani. Sentiwordnet 3.0: An enhanced lexical resource for sentiment analysis and opinion mining. V Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC’10), Valletta, Malta, Maj 2010. European Language Resources Association (ELRA). [3] Computeruser.com. Emoticon list. http://www.computeruser.com/resources/ dictionary/emoticons.html, Maj 2015. [4] A. Hogenboom D. Bal F. Frasincar M. Bal F. de Jong, in U. Kaymak. Exploiting emoticons in sentiment analysis. V Proceedings of the 28th Annual ACM Symposium on Applied Computing, SAC ’13, strani 703–710, New York, NY, USA, 2013. ACM. [5] M. Juršič I. Mozetič T. Erjavec, in N. Lavrač. LemmaGen: Multilingual lemmatisation with induced ripple-down rules. Journal of Universal Computer Science, 16(9):1190–1214, Maj 2010. http://www.jucs.org/jucs_16_9/lemma_gen_ Slika 3: Primerjava preciznosti metod za razpoznavo multilingual_lemmatisation. sentimenta z emotikoni [6] K. Liu W. Li, in M. Guo. Emoticon smoothed language models for twitter sentiment analysis. AAAI Conference on Artificial Intelligence, 2012. [7] T. Marks. Smileyworld emoticons, characters, wallpapers, games, blogs. http://www.windweaver.com/emoticon.htm, Marec 2012. [8] Msgweb.nl. List of emoticons in MSN Messenger. http: //www.msgweb.nl/en/MSN_Images/Emoticon_list, Maj 2015. [9] Pc.net. Text-based emoticons. http://pc.net/emoticons/, Maj 2015. [10] T. Sakurai in Y. Sato. Coretweet. http://coretweet.github.io, Maj 2015. [11] M. Thelwall K. Buckley G. Paltoglou D. Cai, in A. Kappas. Sentiment strength detection in short informal text. J. Am. Soc. Inf. Sci. Technol., 61(12):2544–2558, Dec. 2010. [12] Wikipedia, the free encyclopedia. List of emoticons. http://en.wikipedia.org/wiki/List_of_emoticons, April 2015. Slika 4: Primerjava priklica algoritmov za razpo- znavo sentimenta z emotikoni. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 23 StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 24 MySQL Database On-line Update Technology Based on JSP DU Xiaocheng1 GAO Tao1, 2, * YANG Yaoquan1 1. Department of Automation, North China Electric Power University, Baoding 071003, Hebei Province, China 2. Knowledge Engineering and Discovery Research Institute, Auckland University of Technology, Auckland 1010, New Zealand Email: gaotao863@163.com Abstract With the booming of the network technology, JSP (Java Server Pages) has been widely applied, and it is playing an increasingly important role. This paper introduces the technology of JSP, and expounds the concrete process of MySQL database connection technology by JDBC (Java Data Base Connectivity); finally it presents the methods of operating MySQL database on-line based on JSP. Keywords JSP, MySQL, JDBC, On-line Update MySQL began as a low-end alternative to more powerful 0 Introduction proprietary databases, it has gradually evolved to support higher-scale needs as well. It is still most commonly used Today, the development of network technology is in small to medium scale single-server deployments. constantly changing, and it has become the main theme JDBC is a Java database connectivity technology in our lives and society. Almost every area of human (Java Standard Edition platform) from Oracle Corporation. life is changed due to network. JavaServer Pages (JSP) This technology is an API for the Java programming is a technology that helps software developers create language that defines how a client may access a database. dynamically generated web pages based on HTML, It provides methods for querying and updating data in a XML, or other document types. JSP is similar to PHP, database. JDBC is oriented towards relational databases. A but it uses the Java programming language. JSP allows JDBC-to-ODBC bridge enables connections to any Java code and certain pre-defined actions to be ODBC-accessible data source in the JVM host interleaved with static web markup content, such as environment. JDBC allows multiple implementations to HTML, with the resulting page being compiled and exist and be used by the same application. The API executed on the server to deliver a document. The provides a mechanism for dynamically loading the correct compiled pages, as well as any dependent Java Java packages and registering them with the JDBC Driver libraries, contain Java byte code rather than machine Manager. The Driver Manager is used as a connection code. Like any other Java program, they must be factory for creating JDBC connections. executed within a Java virtual machine (JVM) that This paper is mainly focus on the combining interacts with the server's host operating system to technology between MySQL database and JSP by JDBC provide an abstract, platform-neutral environment. for the database data online updates, and thus to optimize MySQL is a popular choice of database for use in the data flow in web network technology. web applications, and is a central component of the widely used LAMP open source web application 1 The JSP Technology software stack. MySQL can be built and installed manually from source code, but this can be tedious so The fundamental part of JSP (Java Server Pages) is a it is more commonly installed from a binary package simplified design of Servlet. It is proposed by Sun unless special customizations are required. Though Microsystems and also many companies involved for the * Contact Author: Tao Gao, Email: gaotao863@163.com StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 25 establishment of a dynamic web technology standards [1]. Java program segment (Script let) and JSP tags is inserted into a traditional web HTM file to form a JSP file which expands the Html function by java syntax. JSP is easy to be used, fully object-oriented, platform-independent and secure, with all the characteristics of the need of Internet system design. Java code is not required to be complete or self-contained within a single script let block. It can straddle markup content, provided that the page as a whole is syntactically correct. The JSP syntax adds additional tags, called JSP actions, to invoke built-in functionality. Additionally, the technology allows for the creation of custom JSP tag libraries that act as extensions to the standard JSP syntax. A JavaServer Fig1. The frame of JDBC Pages compiler is a program that parses JSPs, and transforms them into executable Java Servlets. A 2.3 The Process of JDBC Programming program of this type is usually embedded into the The public class ‘DBManager’ of Java is as follows. application server and run automatically the first time a JSP is accessed, but pages may also be precompiled for better performance, or compiled as a part of the build process to test for errors. 2 Combination of JSP and MySQL Data Base 2.1 JDBC Technology JDBC (Java Database Connectivity) is a Java API [2] to execute a SQL statement, and program can be connected to a relational database by JDBC API. The query and update of the database can be achieved by using the Structured Query Language [3] [4]. 2.2 The Structure of JDBC In order to make cross-platform use of JDBC program, the appropriate drivers are need which can combine different database provide vendors. The frame of JDBC structure is shown in Figure.1 [5] [6]. By the JDBC driver conversion, the same program written in JDBC API can run on different database systems. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 26 ‘CallableStatement’ instance can be created by ‘prepareCall()’ method. (4) To execute the SQL statements Statement interface provides three methods for executing SQL statements:  execute(): perform any SQL statement.  executeUpdate(): mainly used to perform DML and DDL statements.  executeQuery(): execute the query. (5) To operate the result set Results of the SQL query will return a ‘ResultSet’ object, the program can use the object to obtain the query results as follows:  first(), next(), last(): to move the record pointer.  get(): the method to obtain the record pointer to the value of a particular line or column. (6) To retake the database resources After the operation, all JDBC objects should be close to release JDBC resources, the closing order is reversed to the declaration order as: The process of JDBC programming contains six steps (with MySQL for example) (1) To load the database driver Before connecting to the database, first thing is to Take the ‘table’ form for example, the implement is as load the database drive to connect the Java Virtual follows: Machine, which can be achieved by the static method of ‘java.lang.Class’ class: forName (String className) for implementation. The method to load the MySQL drive is as: . (2) Connection of database Connection of the database is achieved by the ‘DriverManager’ which defines the protocol of connection between the database, the sub-protocol and data source identification: (3) To create the statement object To execute the SQL statements, the java.sql.Statement instance should be obtained, which can be divided into the following three types:  Perform static SQL statements. The function ‘createStatement()’ is used to establish the ‘Statement’ instance.  Execute dynamic SQL statements. The ‘PreparedStatement’ instance can be created by ‘prepareStatement()’ function.  Perform a database stored procedure. The StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 27 4 Conclusions This paper introduces how to use JSP combined with SQL statements to achieve the processes about online adding, online changing and deleting operations for the database data to implement the MySQL database online update, which makes the database more convenient for 3 MySQL Database Online Update common using. 3.1 Online Adding 5 Acknowledgments Online adding operations can be achieved by ‘insert into’ statement, and it is used to insert data to This work is supported by National Natural Science the specified table. The syntax of ‘insert into’ Foundation of China (No. 71102174 and No. 51306058), statement is as follows: insert into table values (value1, value2 ...) the Fundamental Research Funds for the Central Taking the ‘table’ as an example, the specific Universities (No. 2014QN46), the Hebei Science and method is as follows: Technology Support Project (No. 15212204D), the Tianjin Science and Technology Support Project (No. 15ZCZDNC00130), and the State Scholarship Fund for Visiting Scholar by the China Scholarship Council (No. 201406735004). References 3.2 Online Deleting Online delete can be achieved by ‘delete from’ [1] Emmanuel Cecchet, Julie Marguerite and Willy statement. The syntax of the statement is as follows: Zwaenepoel. C-JDBC: Flexible Database Clustering ‘delete from’ table where ‘field name = record name’. Middleware. USENIX Annual Technical Conference For example, named ‘table’, field named ‘id’, the Freenix track, June 2004. specific method is as follows: [2] P. Chen, E. Lee, G. Gibson, R. Katz and D. Patterson. Recording name is the data to be deleted. RAID: High-Performance, Reliable Secondary 3.3 Online Changing Storage. ACM Computing Survey, volume 26, n2, pp. According to ‘add’ and ‘delete’ SQL 145-185, 1994. implementations, the operation of changing the database-related data is as follows: [3] P. Furtado. Efficiently Processing Query-Intensive Databases over a Non-dedicated Local Network. In: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), IEEE Computer Society, 2005. [4] Bradford W. Wade, Donald D. Chamberlin. IBM Relational Database Systems: The Early Years. IEEE Annals of the History of Computing, vol.34, no. 4, pp. 38-48, 2012. The number of ‘value’ is related to the data account. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 28 [5] W.C. McGee. The Information Management [6] Ergsten, Hans. JavaServer Pages (3rd Edition ed.). System (IMS) Program Product. IEEE Annals of O'Reilly Media. 2002. the History of Computing, vol. 31 no. 4, pp. 66–75, 2009. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 29 StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 30 Towards the Development of a Parameter-free Bat Algorithm Iztok Fister Jr., Iztok Fister Xin-She Yang University of Maribor Middlesex University Faculty of Electrical Engineering and Computer School of Science and Technology Science The Burroughs Smetanova 17, 2000 Maribor London, United Kingdom iztok.fister1@um.si ABSTRACT stochastic nature-inspired methods are among the promis- The bat algorithm is a very simple and efficient nature- ing kind of optimization algorithms. This family consists inspired algorithm belonging to the swarm intelligence fam- of the following algorithms: genetic algorithms [7], genetic ily. Recent studies showed its potential in solving the con- programming [11], evolution strategies [1], evolutionary pro- tinuous and discrete optimization problems and many re- gramming [5], differential evolution [14], particle swarm op- searchers have applied bat algorithm to solve real-world prob- timization [9], firefly algorithm [18], bat algorithm [19] and lems. However, empirical studies showed that the main is- dozens of others [4]. sue of most algorithms is the setting of control parameters. An algorithm such as the bat algorithm typically has a few The bat algorithm (BA)is one of the latest algorithms in the parameters, and it is very time-consuming to find its best swarm intelligence (SI) domain. Due to its simplicity, it is parameter combination. Here, we propose a new parameter- a very efficient as well. The original BA works with five pa- free bat algorithm variant without the need for control pa- rameters that represent a potential problem for users which rameters. Initial experiments on basic benchmark functions usually may not know how to specify their values properly. showed the potential of this new approach. Therefore, this paper introduces a new parameter-free or pa- rameterless BA (PLBA) that eliminates this drawback and then proposes techniques for a rational and automated pa- Keywords rameter setting on behalf of the user. This study is based bat algorithm, control parameters, optimization on the paper of Lobo and Goldberg [12]. 1. INTRODUCTION The structure of the remainder of the paper is as follows. As the world is becoming a global village, advances in tech- Section 2 presents a description of the original BA. In Sec- nologies means that new challenges are emerging. Better tion 3, a design of the parameter-free or parameterless BA and greener products are needed for companies to have a (also PLBA) is presented. Experiments and results are dis- competitive edge. Thus, the optimization of product designs cussed in Section 4. The paper concludes in Section 5 where and manufacturing processes become ever-more important. the directions for the future work are also outlined. It is expected that artificial intelligence is among the most promising developments for the next 20 years. Many artifi- 2. BAT ALGORITHM cial intelligence tasks can be achieved by optimization and The origin of the BA development can date back to the machine learning techniques. year of 2010 when Xin-She Yang in [19] proposed the new nature-inspired algorithm that mimics the phenomenon of One of the most important tasks for many productions is echolocation by some species of bats for the optimization how to improve the production of products and services for process. This algorithm can integrate the characteristics of the market, which requires the optimal design and the op- many algorithms such as particle swarm optimization (PSO) timal use of resources. Until recently, many methods have algorithm [9] and simulated annealing (SA) [10]. Primarily, been used to help designers and developers to solve such op- BA was developed for continuous optimization, but many re- timization problems. Some methods are pure mathematical, cent papers showed the potential of the algorithm in solving while others are combined with computer sciences. In line discrete optimization problems. In a nutshell, this algorithm with this, optimization algorithms play a big role. Recently, is widespread in many areas of optimization and industrial applications [8,13,15–17]. Yang proposed the following rules which mimics the bat behavior: • All bats use echolocation to sense the distance to target objects. • Bats fly with the velocity vi at position xi, the fre- quency Qi ∈ [Qmin, Qmax] (also the wavelength λi), the rate of pulse emission ri ∈ [0, 1], and the loudness StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 31 Ai ∈ [A0, Amin]. The frequency (and wavelength) can of the current best solution is performed according to the be adjusted depending on the proximities of their tar- following equation: gets. x(t) = xbest + A(t)N (0, 1), (2) i • The loudness varies from a large (positive) A0 to a minimum constant value A where N (0, 1) denotes the random number drawn from a min. Gaussian distribution with a zero mean and a standard de- viation of one. In addition, is the scaling factor and A(t) is i These three rules mimics the natural behavior of bats, while the loudness. The improvement is controlled by a parame- the full basic pseudo-code is presented in Algorithm 1. ter ri. It is worth pointing that the parameter balances the exploration and exploitation components of the BA search Algorithm 1 Bat algorithm process, where exploitation is governed by Eq. 1 and ex- ploitation by Eq. 2. Input: Bat population xi = (xi1, . . . , xiD)T for i = 1 . . . N p, M AX F E. The evaluation function models the characteristics of the Output: The best solution xbest and its corresponding value problem to be solved. The archiving of the best solution fmin = min(f (x)). 1: init bat(); conditionally is similar to that used in SA, where the best 2: eval = evaluate the new population; solution is taken into the new generation according to a 3: f probability controlled by the parameter Ai in order to avoid min = find the best solution(xbest ); {initialization} 4: while termination condition not met do getting stuck into a local optimum. 5: for i = 1 to N p do 6: y = generate new solution(xi); 2.1 Control parameters in the bat algorithm 7: if rand(0, 1) < ri then and their bottlenecks 8: y = improve the best solution(xbest ) Control parameters guide algorithms during the search space 9: end if { local search step } and may have a huge influence on the quality of obtained 10: fnew = evaluate the new solution(y); solutions. In summary, the BA is controlled by the following 11: eval = eval + 1; control parameters: 12: if fnew ≤ fi and N(0, 1) < Ai then 13: xi = y; fi = fnew; 14: end if { save the best solution conditionally } • the population size NP , 15: fmin =find the best solution(xbest ); 16: end for • loudness Ai, 17: end while • pulse rate ri, The BA is a population-based algorithm, where the popu- • minimum frequency Qmin and lation size is controlled by a parameter Np. The main loop of the algorithm (lines 4-16 in Algorithm 1) starts after the • maximum frequency Qmax . initialization (line 1), the evaluation of the generated solu- tions (line 2) and determination of the best solutions (line 4). It consists of the following elements: As we can see, the BA has five control parameters that can be difficult for users to set a proper combination of con- trol parameter settings that are the most suitable for the • generating a new solution (line 6), particular problem. Though some algorithms have fewer parameters such as differential evolution [14] that employs • improving the best solution (lines 7-9), only three basic control parameters. However, the parame- • ter tuning can be a time-consuming task for all algorithms. evaluating the new solution (line 10), On the other hand, there are also some other robust self- • saving the best solution conditionally (lines 12-14), adaptive [3] BA variants that can modify the values of con- trol parameters during the run. • determining the best solution (line 15). The main task for us is to develop a parameterless variant of the bat algorithm. The generation of a new solution obeys the following equa- tion: 3. DESIGN OF A PARAMETERLESS BAT Q(t) = Q i min + (Qmax − Qmin )N (0, 1), ALGORITHM v(t+1) = vt , (1) i i + (xt i − xbest )Q(t) i In order to develop a new parameterless BA (PLBA), the influence of control parameters was studied and extensive x(t+1) = x(t) + v(t+1), i i i studies revealed that some algorithm parameters can be ef- fectively set. For example, the parameter Qi ∈ [Qmin , Qmax ] where N (0, 1) is a random number drawn from a Gaussian determines the magnitude of the change and settings of pa- distribution with a zero mean and a standard deviation of rameters Qmin and Qmax depend on the problem of interest. one, and Q(t) ∈ [Q(t) , Q(t) However, the rational setting of this parameter can be ap- i min max ] is the frequency determining the magnitude of the velocity change. The improvement proximated with the lower xLb i and upper xUb i bounds of the StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 32 particular decision variables as follows: x(Ub) − x(Lb) Q(t) = i i · N (0, 1), (3) i Np where N (0, 1) has the same meaning as in Eq. (1). For example, when the x(Lb) = −100.0 and x(Ub) = 100.0, the i i frequency is obtained in the interval Q(t) ∈ [0, 2]. i The rationality for setting the values of parameters ri and Ai are obtained, based on the following consideration. Param- eter ri controls the exploration/exploitation components of the BA search process. The higher the value, the more the process is focused on the exploitation. However, the higher r Figure 1: Summary of the comparison analysis. i also means that the modified copies of the best solution are multiplied in the population. As a result, the premature ent population sizes Np. convergence to the local optimum can occur. The appropri- ate value of this parameter is ri = 0.1, as revealed during The results are also statistically evaluated using the Fried- the extensive experimental work. man’s non-parametric statistical tests [2, 6]. These results are shown in Table 3 where the ranks, confidence intervals Similar consideration is valid also for parameter Ai; i.e., the with significance level α = 0.05, and dagger signs denoting lower the parameter, the less time the best current solution the significance difference are summarized. is preserved in the new generation. Therefore, the rational selection of this parameter is A Table 3: Friedman’s statistical tests. i = 0.9 that preserves the Alg. Np Rank CI Sign. 90% of each best solutions and ignores the remaining 10%. BA 100 4.7 [3.28,6.12] † PL-1 10 1.36 [-0.06,2.78] † The population size is also a crucial parameter in the BA. A PL-2 20 2.24 [0.82,3.66] † lower population size may suffer from the lack of diversity, PL-3 40 3.56 [2.14,4.98] † while a higher population size may cause slow convergence. PL-4 80 4.74 [3.32,6.16] † However, the rational setting of the population size depends PL-5 160 5.88 [4.46,7.30] † on the problem of interest. Therefore, this parameter is PL-6 320 6.98 [5.56,8.40] varied in the interval Np ∈ [10, 1280] in the proposed PLBA PL-7 640 7.66 [6.24,9.08] such that each population size multiplied by two in each run PL-8 1280 7.88 [6.46,9.30] ‡ starting with Np = 10. In this way, eight instances of the PLBA is executed and a user selects the best results among The same results are also presented graphically in Fig. 1, the instances. where ranges and confidence intervals are shown as points and lines, respectively. Two algorithms are significantly dif- 4. EXPERIMENTS ferent, if their confidence intervals do not overlap. From The purpose of our experimental work was to show that the Fig. 1, it can be seen that the population size has a signif- results of the proposed PLBA are comparable if not bet- icant influence on the results of the PLBA. The higher the ter than the results of the original BA. In line with this, the population size, the better the results. Interestingly, using original BA was compared with the PLBA using the rational the PLBA with population sizes Np = 640 and Np = 1, 280 selected parameter setting, i.e., Q significantly outperformed the results of the original BA. i was calculated according Eq. (3) (e.q., Qi ∈ [0.0, 2.0]), pulse rate and loudness were fixed as r 5. CONCLUSION i = 0.1 and Ai = 0.9, while the population size was varied in the interval N p = {10, 20, 40, 80, 160, 320, 640, 1280}. Population-based nature-inspired algorithms can be a pow- In contrast, the original BA was run using the following pa- erful tool for solving the hard optimization problems. How- rameters: Np = 100, ri = 0.5, Ai = 0.5 and Qi ∈ [0.0, 2.0] ever, these kinds of algorithms can depend crucially on the as proposed in Fister et al. [3]. good parameter setting. Unfortunately, finding the proper parameter setting for a specific problem of interest is not Experiments were run on the benchmark suite consisting of easy and can pose challenges for users. In this paper, a pa- five functions (Fig. 1). Here, the domains of parameters rameterless BA (also PLBA) algorithm has been proposed were limited into the interval [−10, 10] by functions, while in order to avoid these issues. the dimensions of functions D = 10 were applied during this preliminary work. The optimization process of functions The PLBA sets parameters either by guessing their rational was stopped after 10,000 fitness/function evaluations. Each values, such as setting the parameters pulse rate ri, loud- algorithm was run 25 times. ness Ai, minimum Qmin and maximum Qmax frequencies, or by searching for their proper values experimentally, such The results of the comparative study are summarized in Ta- as setting the population size Np. The results of the pro- ble 2, where the mean values and standard deviations are posed PLBA are comparable with the results of the original given for each algorithm. The BA in Table 2 denotes the BA by solving the benchmark suite of five well-known func- original BA while PL-i the parameter-less BA using differ- tions. A statistical analysis of the results has showed that StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 33 Table 1: Summary of the benchmark functions. Tag Function Definition Domain f n n 1 Ackley’s f (x) = −20 exp(−0.2 1 x2) − exp( 1 cos(2πx n i=1 i n i=1 i)) + 20 + e [−10, 10] f n 2 Griewank f (x) = 1 + 1 x2 − n cos( xi √ ) [−10, 10] 4000 i=1 i i=1 i f3 Rastrigin f (x) = 10n + n (x2 − 10 cos(2πx i=1 i i)) [−10, 10] f4 Sphere f (x) = n x2 i=1 i [−10, 10] (100(x2−x f n i j )2 +(1−xj )2 )2 5 Whitley f (x) = n − cos(100(x2 − x i=1 j=1 4000 i j )2 + (1 − xj )2) + 1 [−10, 10] Table 2: Experimental results. Alg. Np f1 f2 f3 f4 f5 BA 40 1.11e+01±8.66e-01 2.76e-01±2.70e-01 1.70e+02±3.92e+01 7.79e+01±2.53e+01 3.21e+04±1.95e+04 PL-1 10 1.15e+01±8.91e-01 3.96e-01±2.68e-01 2.18e+02±4.61e+01 9.65e+01±3.33e+01 4.87e+04±2.47e+04 PL-2 20 1.13e+01±1.15e+00 3.63e-01±2.94e-01 1.72e+02±5.09e+01 7.80e+01±2.82e+01 4.65e+04±2.65e+04 PL-3 40 1.06e+01±7.11e-01 2.52e-01±2.59e-01 1.46e+02±4.47e+01 6.56e+01±2.00e+01 3.03e+04±1.27e+04 PL-4 80 1.01e+01±7.59e-01 1.79e-01±1.64e-01 1.27e+02±3.58e+01 5.49e+01±1.88e+01 1.90e+04±1.26e+04 PL-5 160 9.68e+00±8.44e-01 1.07e-01±3.24e-02 1.24e+02±3.59e+01 4.58e+01±1.58e+01 1.63e+04±7.32e+03 PL-6 320 9.42e+00±7.32e-01 1.16e-01±3.82e-02 1.01e+02±2.25e+01 3.67e+01±1.17e+01 1.16e+04±3.95e+03 PL-7 640 8.76e+00±9.29e-01 1.02e-01±2.45e-02 9.28e+01±2.45e+01 3.16e+01±1.38e+01 9.08e+03±3.49e+03 PL-8 1280 8.57e+00±8.62e-01 1.02e-01±2.08e-02 9.22e+01±2.63e+01 3.23e+01±1.07e+01 1.08e+04±4.40e+03 the proposed PLBA can achieve comparable results as those IEEE International Conference on, volume 4, pages obtained by the original BA. Such findings encourage us to 1942–1948. IEEE, 1995. continue with this work in the future. As the first goal, [10] S Kirkpatrick, CD Gelatt Jr, and MP Vecchi. we would like to develop also a variant of a parameterless Optimization by simulated annealing. Science, cuckoo search algorithm. We will also investigate the effect 220(4598), 1983. of the population size further in various applications. [11] John Koza. Genetic Programming 2 - Automatic Discovery of Reusable Programs. MIT Press, Cambridge, USA:, 1994. 6. REFERENCES [12] Fernando G. Lobo and David E. Goldberg. An [1] Thomas Bäck. Evolutionary Algorithms in Theory and overview of the parameter-less genetic algorithm. In Practice: Evolution Strategies, Evolutionary Proceedings of the 7th Joint Conference on Programming, Genetic Algorithms. Oxford University Information Sciences. (Invited paper), pages 20–23, Press, Oxford, UK:, 1996. 2003. [2] Janez Demšar. Statistical comparisons of classifiers [13] Navaneethakrishna Makaram and Ramakrishnan over multiple data sets. J. Mach. Learn. Res., 7:1–30, Swaminathan. A binary bat approach for December 2006. identification of fatigue condition from semg signals. [3] Iztok Fister Jr., Simon Fong, Janez Brest, and Iztok In Swarm, Evolutionary, and Memetic Computing, Fister. A novel hybrid self-adaptive bat algorithm. pages 480–489. Springer, 2014. The Scientific World Journal, 2014, 2014. [14] Rainer Storn and Kenneth Price. Differential [4] Iztok Fister Jr, Xin-She Yang, Iztok Fister, Janez evolution–a simple and efficient heuristic for global Brest, and Dušan Fister. A brief review of optimization over continuous spaces. Journal of global nature-inspired algorithms for optimization. optimization, 11(4):341–359, 1997. Elektrotehniški vestnik, 80(3):116–122, 2013. [15] Anass Taha, Mohamed Hachimi, and Ali Moudden. [5] Lawrence Jerome Fogel, Alvin J. Owens, and Adapted bat algorithm for capacitated vehicle routing Michael John Walsh. Artificial Intelligence through problem. International Review on Computers and Simulated Evolution. John Willey & Sons, Inc., New Software (IRECOS), 10(6):610–619, 2015. York, USA:, 1966. [16] TP Talafuse and EA Pohl. A bat algorithm for the [6] Milton Friedman. A comparison of alternative tests of redundancy allocation problem. Engineering significance for the problem of m rankings. Ann. Optimization, (ahead-of-print):1–11, 2015. Math. Statist., 11(1):86–92, 03 1940. [17] Jinfeng Wang, Xiaoliang Fan, Ailin Zhao, and [7] David E. Goldberg. Genetic Algorithms in Search, Mingqiang Yang. A hybrid bat algorithm for process Optimization and Machine Learning. Addison-Wesley planning problem. IFAC-PapersOnLine, Longman Publishing Co., Inc., Boston, USA:, 1989. 48(3):1708–1713, 2015. [8] Andrés Iglesias, Akemi Gálvez, and Marta Collantes. [18] Xin-She Yang. Firefly algorithm. In Nature-Inspired Global-support rational curve method for data Metaheuristic Algorithms, pages 79–90. Luniver Press, approximation with bat algorithm. In Artificial London, UK:, 2008. Intelligence Applications and Innovations: 11th IFIP [19] Xin-She Yang. A new metaheuristic bat-inspired WG 12.5 International Conference, AIAI 2015, algorithm. In Nature inspired cooperative strategies for Bayonne, France, September 14-17, 2015, Proceedings, optimization (NICSO 2010), pages 65–74. Springer, volume 458, page 191. Springer, 2015. 2010. [9] James Kennedy and Russell Eberhart. Particle swarm optimization. In Neural Networks, 1995. Proceedings., StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 34 Using trees to speed up the Floyd-Warshall algorithm Marko Grgurovič UP DIST University of Primorska marko.grgurovic@famnit.upr.si ABSTRACT in such networks is a classic problem in algorithmic graph A classic problem in algorithmic graph theory is to find theory. Two of the most common variants of the problem are shortest paths, and a common variant is the all-pairs short- the single-source shortest path (SSSP) problem and the all- est path problem (APSP). We consider non-negatively weighted pairs shortest path problem (APSP). In the SSSP variant, APSP. Due to its simplicity and efficiency, the Floyd-Warshall we are tasked with finding the path with the least total algorithm is frequently used to solve APSP in practice. length from a fixed node s ∈ V to every other node in the network. Similarly, the APSP problem asks for the shortest We propose a combination of the Floyd-Warshall algorithm path between every pair of nodes u, v ∈ V . In this paper we with a hourglass-like tree structure, which reduces the num- will focus exclusively on the APSP variant of the problem. ber of path combinations that have to be examined. Only those path combinations that provably cannot change the The asymptotically fastest APSP algorithm for dense graphs values in the shortest path matrix are omitted. The result- runs in O(n3 log log3 n/ log2 n) time [2]. For non-negative ing algorithm is simple to implement and uses no fancy data arc length functions and for sparse graphs, there exist asymp- structures. totically fast algorithms for worst case inputs [10, 12, 11], and algorithms which are efficient average-case modifications In empirical tests, the new algorithm is faster than the Floyd- of Dijkstra’s algorithm [6, 3, 9]. In fact, it turns out that Warshall algorithm for random complete graphs on 256 − any SSSP algorithm can be asymptotically sped up in the 4096 nodes by factors of 3.5 − 4.8x. When we inspect the average-case setting when solving APSP [1]. number of path combinations examined compared to the Floyd-Warshall algorithm, they are reduced by a factor of In practice, the Floyd-Warshall algorithm is frequently used, 12 − 90x. All code was written in C. along with variations of Dijkstra’s algorithm when the graph is sparse. One can also approach APSP through funny ma- Categories and Subject Descriptors trix multiplication, and practical improvements have been F.2.2 [Theory of Computation]: Nonnumerical Algorithms devised to this end through the use of sorting [8]. There exist and Problems many optimizations for the Floyd-Warshall algorithm, rang- ing from better cache performance [13], optimized program- generated code [4], to parallel variants for the GPU [5, 7]. General Terms Algorithms, Theory In spite of intensive research on efficient implementations of the Floyd-Warshall algorithm, the authors are not aware Keywords of any improvement to the number of path combinations Dynamic programming, shortest path examined by the algorithm. In this paper, we propose a modification of the Floyd-Warshall algorithm that combines 1. INTRODUCTION it with a hourglass-like tree structure, which reduces the Let N = (V, A, ) be a directed network where we refer to number of paths that have to be examined. Only those path V = {v combinations that provably cannot change the values in the 1, v2, ..., vn} as the set of nodes and A as the set of arcs (directed edges). To simplify notation we will write shortest path matrix are omitted. The resulting algorithm |V | = n and |A| = m. The function : A → is simple to implement, uses no fancy data structures and R maps arcs to (possibly negative) lengths. Finding shortest paths in our tests is faster than the Floyd-Warshall algorithm for random complete graphs on 256 − 4096 nodes by factors ranging from 2.5−8.5x. When we inspect the number of path combinations examined however, our modification reduces the number by a staggering factor of 12 − 90x. 2. ALGORITHM The simplest improvement over Floyd-Warshall involves the use of a tree, denoted as OUTk, which is the shortest path tree containing paths that begin in node vk and end in some StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 35 node w ∈ V \ {vk}, but only go through nodes in the set Arc lengths were represented using floating-point numbers {v1, ..., vk−1}. In order to reconstruct the shortest paths, the in both cases. Floyd-Warshall algorithm needs to maintain an additional matrix, which specifies the path structure. In our algorithm We performed two sets of experiments, one on random com- this information is essential, since the path structure is used plete graphs, and one on random sparse graphs. In both during the execution. We augment the Floyd-Warshall algo- cases, we measured two quantities: number of path combi- rithm with a matrix L[i][j] which specifies the penultimate nations examined, and actual running time. Since the results node on the shortest path from i to j. This suffices for re- are numbers that range from very small to very large in both constructing the shortest path tree for all paths going out cases, we display the results as a percentage of the Floyd- of k as follows: create n trees {T1, ..., Tn}, now go through Warshall algorithm, which is always 100% in the plots, but j = 1 to n and place Tj as the child of TL[k][j]. This takes is not drawn explicitly. O(n) time. The first set of experiments was for the input of random We then have the following algorithm: complete graphs of varying sizes. The results are shown in Figure 1. The second set of experiments was for the input of Algorithm 1 Single-tree Algorithm. a random graph of 1024 nodes whose number of arcs varied 1: procedure from 10 − 80% where 100% = n2. To make the compari- Single-Tree(W ) 2: Initialize L, a n × n matrix, as L[i][j] := i. son between Floyd-Warshall and the modified versions fairer 3: for k := 1 to n do in the second set of experiments, we augmented the Floyd- 4: Construct OUT Warshall algorithm with a simple modification, that allowed k . 5: for i := 1 to n do it to skip combinations i, k where W [i][k] = ∞, which re- 6: Stack := empty duced the running time and number of path combinations 7: Stack.push(v examined. The results of the second set of experiments are k ) 8: while Stack = empty do shown in Figure 2. 9: vx := Stack.pop() 10: for all children v 4. CONCLUSIONS j of vx in OUTk do 11: if W [i][k] + W [k][j] < W [i][j] then In the proposed algorithm, we can observe a significant re- 12: W [i][j] := W [i][k] + W [k][j] duction in terms of path combinations examined (see left 13: L[i][j] := L[k][j] plot of Figure 1) . This quantity dominates the algorithm’s 14: Stack.push(v asymptotic running time and, as observed, decreases com- j ) 15: end if pared to the cubic algorithm when inputs grow larger. It 16: end for might be possible to obtain sub-cubic asymptotic bounds in 17: end while the average-case model. Despite this reduction in path com- 18: end for binations examined, the actual time savings shown in the 19: end for right plot of Figure 1 are more modest. A variety of factors 20: end procedure contribute to this disparity, ranging from cache performance to implementation details that have not been thoroughly optimized. Regardless, the speedups remain significant for For the sake of brevity, we omit proofs. We can augment practical applications, and future work could improve this Algorithm 1 with another tree. The second tree is similar further. The experiments on sparse graphs in Figure 2 show to OUTk, except that it is the incoming shortest path for a reduction in path combinations examined as the graph be- vk. Strictly speaking, this is not a tree1, but we can reverse comes sparser, but the effect on the running time seems to the directions of the arcs, which turns it into a tree with be minor. vk as the root. The augmented algorithm is referred to as Hourglass (as opposed to Single-tree). Overall, the Single-tree algorithm is the simplest to imple- ment and offers good performance. The Hourglass algorithm 3. EMPIRICAL RESULTS has the potential to be even faster, but would likely require Our implementations were written in C and compiled with a better implementation. It is also worthwhile to note that gcc using flags -std=c99 -O3. We ran the experiments on the additional space requirements for the Single-tree algo- an Intel i7-2600 CPU running on Windows 7. All tests were rithm are very modest, as most applications would typically ran 20 times and averaged. require storing the path reconstruction matrix regardless. The input graphs were pseudorandomly generated. For com- 5. REFERENCES plete graphs, this meant assigning each arc an indepen- [1] A. Brodnik and M. Grgurovič. Speeding up shortest dently uniformly distributed random length in the range path algorithms. In K.-M. Chao, T. sheng Hsu, and (0, 1). Sparse graphs were generated by starting with an D.-T. Lee, editors, ISAAC, volume 7676 of Lecture empty graph on 1024 nodes and adding a desired number of Notes in Computer Science, pages 156–165. Springer, arcs, which were chosen independently according to the uni- 2012. form random distribution, and assigned an independently [2] T. M. Chan. More algorithms for all-pairs shortest uniformly distributed random length in the range (0, 1). paths in weighted graphs. SIAM J. Comput., 1 39(5):2075–2089, 2010. The hourglass name comes from placing this structure atop the OUT [3] C. Demetrescu and G. F. Italiano. Experimental k tree, which gives it a hourglass-like shape, with vk being the neck. analysis of dynamic all pairs shortest path algorithms. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 36 Figure 1: The left plot shows the percentage of path combinations examined by the two modifications of Floyd-Warshall, when compared to the original algorithm (which is always at 100%, not shown), for the input of complete graphs of various sizes. The right plot shows the difference in execution time, compared to the original algorithm. 15 Single-tree 40 Single-tree Hourglass Hourglass 35 s e n tio 10 tim a 30 g inb inn m 7.5 n o 25 c ru fo of 5 % 20 % 4 3 15 2 1 0 10 28 29 210 211 212 28 29 210 211 212 graph size (nodes) graph size (nodes) Figure 2: The left plot shows the percentage of path combinations examined by the two modifications of Floyd-Warshall, when compared to the original algorithm (which is always at 100%, not shown), for the input of a graph with 1024 nodes and various arc densities. The right plot shows the difference in execution time, compared to the original algorithm. 6 Single-tree 21 Single-tree Hourglass Hourglass 20 s 5 e n tio tim a 19 g in 4 b inn m n o 18 c ru of 3 of % 17 % 2 16 1 15 10 20 30 40 50 60 70 80 10 20 30 40 50 60 70 80 graph density (100% = n2 arcs) graph density (100% = n2 arcs) StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 37 ACM Transactions on Algorithms, 2(4):578–601, 2006. [4] S.-C. Han, F. Franchetti, and M. Püschel. Program generation for the all-pairs shortest path problem. In Proceedings of the 15th international conference on Parallel architectures and compilation techniques, PACT ’06, pages 222–232, New York, NY, USA, 2006. ACM. [5] P. Harish and P. J. Narayanan. Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14th international conference on High performance computing, HiPC’07, pages 197–208, Berlin, Heidelberg, 2007. Springer-Verlag. [6] D. Karger, D. Koller, and S. J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22(6):1199–1217, 1993. [7] G. J. Katz and J. T. Kider, Jr. All-pairs shortest-paths for large graphs on the GPU. In Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, GH ’08, pages 47–55, Aire-la-Ville, Switzerland, Switzerland, 2008. Eurographics Association. [8] J. J. McAuley and T. S. Caetano. An expected-case sub-cubic solution to the all-pairs shortest path problem in R. CoRR, abs/0912.0975, 2009. [9] Y. Peres, D. Sotnikov, B. Sudakov, and U. Zwick. All-pairs shortest paths in O(n2) time with high probability. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 663–672, Washington, DC, USA, 2010. IEEE Computer Society. [10] S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47–74, January 2004. [11] S. Pettie and V. Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput., 34(6):1398–1431, June 2005. [12] M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46(3):362–394, May 1999. [13] G. Venkataraman, S. Sahni, and S. Mukhopadhyaya. A blocked all-pairs shortest-paths algorithm. J. Exp. Algorithmics, 8, Dec. 2003. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 38 3D walk through the references of Dutch women writers Jernej Grosar Assist. Jure Demšar Assist. Prof. Dr. Narvika Faculty of Computer and Faculty of Computer and Bovcon Information Science, Information Science, Faculty of Computer and University of Ljubljana University of Ljubljana Information Science, Večna pot 113 Večna pot 113 University of Ljubljana Ljubljana, Slovenia Ljubljana, Slovenia Večna pot 113 gosar.jernej@gmail.com jure.demsar@fri.uni-lj.si Ljubljana, Slovenia narvika.bovcon@fri.uni- lj.si ABSTRACT 2. PROJECT The goal in this project was to create visualization of connec- 2.1 The institutional framework and the con- tions in interactive 3D world between Dutch female writers cept of the project in years between 1790 and 1914. In this world, writers are This project was realized as a seminar work at the Intro- represented by houses and windmills, and player can disco- duction to Design class at the Faculty of Computer and ver these connections by travelling between them. Information Science, University of Ljubljana, under the su- pervision of Assist. Prof. Dr. Narvika Bovcon and Assist. Jure Demšar. It was a part of an international collabora- Categories and Subject Descriptors tion with HERA project "Travelling texts 1790-1914: The H.5.1 [Multimedia Information Systems]: Artificial, au- transnational reception of women’s writing at the fringes of gmented and virtual realities Europe". The students were given the task to create an interactive General Terms 3D space that would contain the network of quotations of Visualization Dutch women writers. The concept behind this type of pre- sentation of data from the field of literary history was quite experimental for both disciplines that were put in dialogue in this project, i. e. the literary studies and the computer Keywords games development, however, the middle ground that allo- Women writers, Dutch, 3D walk, visualization, virtual re- wed for a successful collaboration was found in new media ality, Digital Humanities, spatialized reading, interdiscipli- art approaches that research virtual spaces beyond the use nary collaboration, Unity3D for gaming. The concept of ”spatialized reading” was pro- posed in the form of a script that guided the user’s walk through the 3D space from one object to the next. 1. INTRODUCTION The field of Digital Humanities has been a territory of expe- The project was inspired by various examples of 3D spa- rimental collaborations between different disciplines for the ces used in conjunction with language or artworks and by last thirty years, with especially intense developments in adventure computer games with 3D text and graphic ele- the last decade. However, the possibilities to pose research ments. In the project The Legible City [1] the interface is questions, the answers to which are possible only now with in the form of a bicycle, which enables riding through the the use of new information technologies, and the creation computer generated space, where instead of buildings in the of media hybrids as representation and visualization tech- city there are letters which make up text. ArsDoom [2] is niques are far from being exhausted. The paper will present a patch of the first person shooter game Doom, where the a case of interdisciplinary collaboration, an attempt at a scene is modelled as the space of the new media art festival digital humanities project that connects and displaces the Ars Electronica and the objects in the space are artworks, in- traditional conceptions of text, map and space. stead of shooting, one can paint with a brush. Srečo Dragan and Computer Vision Laboratory made The Virtual Jako- pic Gallery (1998) [3] as a 3D web gallery written in VRML language. If you look back, it won’t be there anymore [4] is a 3D computer generated space that is created based on what the user has already seen and what not; objects in space are letters. 2.2 Realization The main goal for the students was to create the visualiza- tion of the connections between Dutch women writers in the StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 39 Figure 1: House and windmill representing two writers along with quote on the top. years between 1790 and 1914 - how they referenced or quo- right. A mini map on the left side of the screen shows ted each other in letters that they wrote to their friends or where the player is (the blue square on the mini map in to other writers, in newspaper articles or in books. Because Figure 3) and where houses are (the yellow and red circles). of the limited time for realization of the project, only a few The quote, the instructions and the position of the indica- writers and connections between them were used. tors on the mini map are changed when a new connection is discovered, showing the position of the new house. The visual representation of the connections between Dutch women writers has been created as a 3D computer “game” The reading of quotes is temporal and corresponds to the with the help of the Unity3D game engine. This gaming user’s movement through 3D space. The quote is shown on engine has been chosen because it is easy to use and one can the screen for as long as the user takes to walk to the next very quickly create landscape and logic behind it. However, house. The map of the connections between the writers is in our project the gaming experience is reduced to walking not disclosed in the form of a diagram, instead it shows al- in space, finding the objects and reading the quotations (Fi- ways just the two writers connected by the quote that is gure 1), and of course the contemplation of the connections being read at this moment. The map is revealed temporally thus represented. In this 3D space there are two types of and dependent on the user’s reading. In this way the con- interactive objects: the writers are represented by the hou- templation of the text is put in the foreground. If the entire ses, if they had mentioned other writers in their work, or by network of connections would be shown and all the quotes windmills (Figure 2), if they have only been mentioned by would be present in the space at the same time, the spatial others. relations between them would have to be determined in a completely different way, so that they would carry meaning. The user discovers the connections between the women wri- ters by traveling between the houses. As he/she approaches The landscape of this game has been designed to look like a house so that he/she is close enough to it, the quote by this a typical Dutch landscape with water channels, bridges and writer (that is the one represented by the house), in which boats. Houses and windmills that represent Dutch women she mentioned another writer, is shown on the upper side of writers have also been chosen for this reason, so that a homo- the screen. There are only two writers (houses) shown in this genous image of the landscape is achieved. House and wind- virtual world at the same time – the one that has referenced mill models had been taken from website http://tf3dm.com/ the other and the one that has been referenced. When a (uploaded by user “3dregenerator”), other objects, which writer that has no connections (has not mentioned another appear in landscape, are part of the standard assets in Unity3D writer) is visited, the player moves back to a previous one development program. To use this objects one can simply that has another connection (Figure 3) and only then the apply them by "painting" them on the landscape. The hei-new connection to a new writer is shown. The connections ght map for landscape has been created in Adobe Photoshop and the successive appearance of the houses and windmills as a gray scale image and later applied to this virtual world. are ordered by the length of the continuous path that con- For illumination of the landscape, directional light has been nects the writers by their references, that means that the used, placed above the landscape. chain of connections that connects the most writers that had mentioned others is shown first. 2.3 Technical aspect of the project As mentioned earlier, Unity3D gaming engine has been used There are also instructions at the bottom of the screen for for realization of this project. This engine uses scripts for easier traveling and navigation. The instruction about which manipulation with game objects which can be written in house or windmill should be visited next appears on the JavaScript or C# programming languages. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 40 Figure 2: One of many windmills representing writers. Figure 3: Player has already visited windmill. In this project three different scripts have been used. First 3. CONCLUSIONS script, written in JavaScript, is the main script of this pro- The project of this kind involves the expertise of collabo- ject and contains almost all of the game logic. It is used for rators from different disciplines, where one of the problems manipulation of the quotes and instructions shown on the that surface is also how to find a common language to com- screen as well as for showing and hiding houses and wind- municate what is important for each of them. This entails mills. It is attached to first person controller (the object communicating the way, how each of the collaborators has which moves around and is controlled by player) and is tri- to prepare the necessary materials with which the other di- ggered when this controller comes to the predetermined di- scipline has to work, and also explaining, what are the goals stance from the house or windmill - the area which object and standards of each of the collaborators that have to be collider covers. met in the project. Our collaboration was successful, the 3D visualization of connections between Dutch women writers Other two scripts are written in C# and they control but- that has been presented in this paper will be exhibited at tons in main menu and teleportation of the player which the conference related to the Women Writers database in makes the interaction easier and enables player to quickly Letterkundig Museum in Hague in September 2015. return from windmill to the house. When player enters te- leportation area, he/she is teleported back to the vicinity of 4. ACKNOWLEDGMENTS the house that he/she came from to this windmill, instead The project was realized in collaboration with the HERA of walking all the way back. project "Travelling Texts 1790-1914: The Transnational Re- ception Of Women’s Writing At the Fringes of Europe". StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 41 The presentation concept for Dutch literary field focusing 5. REFERENCES on women writers and the selection of quotations was pre- [1] Web source. Jeffrey Shaw: The Legible City (1989). pared by Prof. Dr. Suzan Van Dijk, Huygens Institute http://www.jeffrey-shaw.net/html_main/show_work. for the History of Netherlands. The concept and script for php?record_id=83#. ”spatialized reading” was prepared by Narvika Bovcon and [2] Web source. Orhan Kipcak, Reini Urban: ArsDoom Assist. Prof. Dr. Aleš Vaupotič from the Research Center (1995). http://www.gamescenes.org/2009/11/ for Humanities at the University of Nova Gorica. The pro- interview-orphan-kipcak-arsdoom-arsdoom-ii-1995. ject was realized in 2015 at the Faculty of Computer and html. Information Science, University of Ljubljana. [3] Web source. Franc Solina: Virtual technology and remote observation over the Internet for art applications (2000). http://eprints.fri.uni-lj.si/52/. [4] Web source. Narvika Bovcon, Barak Reiser, Aleš Vaupotič, coding Igor Lautar: If you look back, it won’t be there anymore (2005). http://black.fri.uni-lj. si/datadune/x_dd_binder_crop_optim_redu.pdf. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 42 Budget travelling through virtual reality Žiga Kerec Marko Balažic Faculty of computer and Faculty of computer and information science, Univeristy information science, Univeristy of Ljubljana of Ljubljana Večna pot 113 Večna pot 113 1000 Ljubljana, Slovenia 1000 Ljubljana, Slovenia ziga.kerec@gmail.com marko.balazic@gmail.com Jure Demšar Narvika Bovcon Faculty of computer and Faculty of computer and information science, Univeristy information science, Univeristy of Ljubljana of Ljubljana Večna pot 113 Večna pot 113 1000 Ljubljana, Slovenia 1000 Ljubljana, Slovenia jure.demsar@fri.uni-lj.si narvika.bovcon@fri.uni- lj.si ABSTRACT as part of class’s required seminar and was later on pre- This paper consists of information about an application de- sented at Ljubljana Flow festival in June 2015. This festival veloped for Ljubljana’s Flow festival. We decided to develop is connected to the alternative art scene and is open to con- a virtual reality app, due to the fast growing market and in- temporary technological experiments such as building map- teresting end results. The Application was built in Unity3D ping projections and travelling through 3D virtual world. - free professional game engine software, and it represents a The initial idea consisted of a simple path leading people journey through an abstract landscape. The Application is through different visual representations of an abstract vir- developed for Android mobile operating system and can be tual world that would trigger corresponding emotions. The viewed through Google’s budget friendly solution for virtual whole experience is backed up with suitable background mu- reality - Google Cardboard. sic and audio effects. The final product can be broken down to 4 different sections, the first one being a welcome scene Keywords with a trigger to start the second scene or the main part of the application, as shown in Figure 1. Objects that appear Virtual reality, Android, Unity3D in all scenes are designed in low-poly technique, which gives them a sharp and abstract look. 1. INTRODUCTION Virtual reality (VR) is one of the fastest growing markets in computer science industry today. All major companies are either creating or acquiring products and ideas that are bound to be the next big thing. One of the greatest draw- backs of VR technology is pricing of the products capable of presenting virtual 3D world. This problem was overcome recently when Google released a contraption called Google Cardboard. Google Cardboard is a low-budget VR head- set, its biggest asset is its low price, which makes it very accessible for us students and various of our projects. The idea for a VR app was born during the Introduction to Design class at the Faculty of Computer and Information Science, University of Ljubljana. The product was created Figure 1: Start scene with trigger to start the main part of application. In this paper we present how we conceptualized and built the virtual reality app for the Flow festival. In Section 2 we present some related work and the tools required to build and run the application. In third section we present the narrative and imagery that shape the user experience on his/her travel in our virtual world. We conclude this paper with findings and possible future work. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 43 2. RELATED WORK AND GAME ENGINE loud noises. Unity3D is a very popular game development engine devel- oped and maintained by a company called Unity Technolo- gies. The engine is especially popular among indie game developers, mainly because it is free, and the games or ap- plications made with Unity3D are easily ported on a number of different platforms – from Microsoft Windows, Android, iOS to Playstation [1]. Its main intention is game design, however Unity already proved as a good tool for various types of applications, e.g. urban studies [2] and virtual re- ality [3]. In their application Wang et al. [3] used Unity to simulate a quite complex study environment – a whole building complex in which students can study. As Unity proved as a good tool for simulating complex virtual real- ity environments we choose it as the tool for visualizing our much simpler environment. Figure 3: Brighter yellow section, comes right after 3. THE VIRTUAL WORLD mythical forrest. Our applications offers a unique travelling experience into a different dimension. As our virtual word is in 3D we After this dark emotional part, we should begin to see the used Blender to model the objects surrounding the inter- light at the end of the forest, and as the journey evolves dimension traveller (user of the application). Blender is a we should eventually reach the next, brighter scene (Figure free professional and open-source 3D computer graphics soft- 3). In this scene we should feel a bit happier and relaxed, ware. All models used in the application were built from the therefore it is backed up with different style of music. Again ground up. One of the most important pieces of software is we are travelling through thick fog, this time in bright yellow Android software development kit (SDK), which allowed us colour, and are surrounded by colourful islands. We added to transfer game/animation from Unity3D software to An- flowers (Figure 4) and other motives that gave a warmer droid phones for testing and later on Google Play Store for feeling to the entire section. Last and final sector takes place general use. mainly in a tube. This is a tube with animated textures of black and white stripes that cause us to loose our sense of The main part of the VR application consists of three visu- speed and location. At the end of a long and twisted tube ally and emotionally very different scenes. Here we describe, (Figure 5), we fall down the white cliff and stop right at the how we have designed the three parts (we discuss the selec- bottom, on top of red spikes. tion of narrative elements, of colours, lights, of the speed of camera travelling) to achieve the corresponding user experi- ence for each of them. Figure 4: Flower hill, last part of the second sector. The whole space was designed from the ground up and it is Figure 2: First section in the main scene. Dark put together with dozen objects, crafted in Blender software. mythical forrest, with thick fog and trees hovering We of course incorporated more objects, that are duplicated over the path. and just slightly altered for different visual effect. The fog was added for the purpose of masking the sense of space First stage in the main scene was meant to be a mythical and for not noticing empty background behind the last line forest, a dark and lonely place, where we should feel a bit of objects. cramped. As we are travelling down the path we are sur- rounded with trees hovering over us (Figure 2). The whole 4. CONCLUSION scene is filled with thick white fog and an occasional light Virtual reality has come a long way in the last few years, but bulb levitating in the sky. To back up the unpleasant feel- there is still many ground to cover. Powerful pieces of hard- ing, we added a flock of crows flying over the scene, making ware are still not as accessible to general public and small StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 44 Figure 5: Tube with animated textures. development studios, as budget friendly solutions such as Google Cardboard, that are great for developers to start ex- ploring the world of Virtual Reality, even tho mobile smart- phones are (still) not powerful enough for more sophisticated and realistic effects. This is exactly the target platform for our application. Budget friendly platform and an applica- tion with intermediate graphics complexity for optimal re- sults on almost any modern Android phone. Virtual reality certainly should and will be the thing that will shape the future of computer graphics and gaming. 5. REFERENCES [1] R. H. Creighton. Unity 3D Game Development by Example: A Seat-of-Your-Pants Manual for Building Fun, Groovy Little Games Quickly. Packt Publishing Ltd, 2010. [2] A. Indraprastha and M. Shinozaki. The investigation on using unity3d game engine in urban design study. Journal of ICT Research and Applications, 3(1):1–18, 2009. [3] S. Wang, Z. Mao, C. Zeng, H. Gong, S. Li, and B. Chen. A new method of virtual reality based on unity3d. In Geoinformatics, 2010 18th International Conference on, pages 1–5. IEEE, 2010. StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 45 StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 46 Comparison of DE strategies for Gray-Level MultiLevel Thresholding Uroš Mlakar Iztok Fister University of Maribor University of Maribor Smetanova 17 Smetanova 17 Maribor, Slovenia Maribor, Slovenia uros.mlakar@um.si iztok.fister@um.si ABSTRACT class variance or various entropy measures. Many heuristic In this paper we investigate the impact of different mutation methods have gained a lot of attention recently, since ex- strategies in differential evolution applied to the problem haustive methods are usually computationally inefficient. of gray-level multilevel thresholding. Four different strate- gies are compared, namely rand/1, best/1, rand to best/1, In this paper we investigate the influence of different muta- and current to best/1. These strategies are tested on four tion strategies on the quality of segmentation by using the standard test images taken from literature. The quality of between-class variance as the objective function proposed by segmented images was compared on the basis of the PSNR Otsu [5]. The rest of the paper is organized as follows. In metric, which showed that the best performing strategy was Section 2 some of related work is presented in the area of current to best/1 based on the mean PSNR value, but in multilevel thresholding. In Section 3, image segmentation the case of best result found, the rand/1 strategy performed and the Otsu crietrion are described, while in Section 4 the best. When comparing the mean and best objective values, differential evolution algorithm (DE), along with 4 muta- the best/1 strategy outperformed the others. tion strategies are presented, which have been used for this study. In Section 5 we define the metric, which was used to Keywords assess the quality of the segmentation and present the ex- perimental results. In Section 6 we will conclude this paper Multilevel thresholding, Otsu criterion, evolutionary algo- with some findings. rithm, differential evolution 2. RELATED WORK 1. INTRODUCTION Many works has been done for multilevel thresholding using Image segmentation is a process of dividing an image into evolutionary algorithms. Some of these algorithms can be disjoint sets, which share similar properties such as intensity found in [7] and [4]. Alihodzic et al. [1] introduced a hybrid or color. Image segmentation is usually the first step for bat algorithm with elements from the differential evolution many high-level methods, such as feature extraction, image and artificial bee colony algorithms. Their result show their recognition, and classification of objects. Simply put, image algorithm outperforms all other in the study, while signifi- segmentation is a process of dividing an image into regions, cantly improving the convergence speed. Bhandari et al. [2] which are used as input for further specific applications. Im- investigated the suitability of the cuckoo search (CS) and the age thresholding is one of the most used and simplest seg- wind driven optimization algorithm for multilevel threshold- mentation techniques, which performs image segmentation ing using Kapur’s entropy as the objective function. The based on values contained in the image histogram. In the algorithms were tested on a standard set of satellite images case of separating an image into two classes, the process is by using various number of thresholds. They concluded that called bilevel thresholding, but when separating the image both algorithms can be efficiently used for the multilevel into several regions we deal with multilevel thresholding. thresholding problem. Duraisamy et al. [3] proposed a novel The selection of optimal threshold values is crucial, since particle swarm optimization (PSO) algorithm maximizing the results of good segmentation are a good foundation for the Kapur’s entropy and the between-class variance. Their applications, which further process the segmented images. algorithm has been tested on 10 images, and the results compared with a genetic algorithm. The PSO proved better Multilevel thresholding can be regarded as an optimization in terms of solution quality, convergence, and robustness. process, usually maximizing certain criteria like between- Zhang et al. [8] presented an artificial bee colony algorithm (ABC), for the problem of multilevel thresholding. They compared their algorithm to PSO and GA, where their con- clusions were that the ABC is more rapid and effective, using the Tsallis entropy. 3. IMAGE SEGMENTATION For the purpose of multilevel threshold selection the Otsu criterion was selected as the objective function. It operates on the histogram of the image, maximizing the between-class StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 47 variance. For a bilevel thresholding problem is this formally r1, r2 and r3. indexes are mutually different and differ- defined as: ent from i. They are selected uniformly within the range {1, 2, ..., N p}. The scale factor F is defined within the range σ2B(t∗) = max σ2B(t), (1) 1≤t≤L [0, 2]. The mutant vector mi is obtained by adding a scaled vector difference to a third vector. where The trial vector ti is then generated using the crossover rate σ2B = ω0ω1(µ1 − µ0)2, (2) Cr and a corresponding vector xi from the population as: with ω0 and ω1 being probabilities of class occurrence and µ0 and µ1 the mean values of each class. mi,j if rand(0, 1) ≤ Cr or j = jrand, This problem is easily expandable to a multilevel problem ti,j = (8) xi,j otherwise. as: σ2B(t∗1, t∗2, ..., t∗n−1) = max σ2B(t1, t2, ..., tn) 1≤t As can be seen from Eq. 8, the crossover rate C 1 q}.Each of them represents an in-social care support. Cochrane database of systematic terval where function di( x) is greater then some q. One can reviews, pages 1–11, 2008. prove that this will result into a single interval and not the union of disconnected intervals. [4] B. Qiu and H. B. Gooi. Web-based SCADA display Also, we define the sequence of intervals recursively as: systems (WSDS) for access via Internet. IEEE Transactions on Power Systems, 15(2):681–686, 2000. [ x 0 , y 0] = [0 , 100] [5] B. Qiu, H. B. Gooi, Y. Liu, and E. K. Chan. Internet-based SCADA display system. IEEE [ z , b ] = ∅ Computer Applications in Power, 15(1):14–19, 2002. [ x n− 1 , yn− 1] if ∩ki=1 [ adi,zn− 1 di,zn− 1 n, yn] = [ x [6] V. Rialle, C. Ollivet, C. Guigui, and C. Hervé. What n− 1 , zn− 1] otherwise Do family caregivers of Alzheimer’s disease patients where z desire in smart home technologies? Contrasted results n− 1 = xn− 1+ yn− 1 2 In the limit: of a wide survey. Methods of Information in Medicine, 47(1):63–69, 2008. lim [ xn, yn] [7] Tošić Aleksandar, Radež Nejc, Lukunič Primož, Cuder n→∞ Sašo, Krivec Tadej, Štular Tanja, Jovičić Vladan, and we will get the desired point. Brodnik Andrej. PAHIMA pametna hiša malina. International Electrotechnical and Computer Science 7. CONCLUSION Conference, 23, 2014. [8] G. Zecevic. Web based interface to SCADA system. Home automation has proven it will grow into a new mar- POWERCON ’98. 1998 International Conference on ket in the future. There is a growing amount of suppliers Power System Technology. Proceedings (Cat. of custom periphery unity that can be controlled by users No.98EX151), 2, 1998. remotely. Some solutions even implement standards multi- ple standards. The current state standardization is still far StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference Ljubljana, Slovenia, 6 October 64 StuCoSReC University of Primorska Press www.hippocampus.si isbn 978-961-6984-01-0 Not for resale 9 789616 984010 Document Outline Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2015 2nd Student Computer Science Research Conference. Koper: University of Primorska Press, 2015 (Front Cover). Colophone Preface Multikonferenca Informacijska družba 2015 - Predgovor Information Society 2015 - Foreword Contents Primož Bencak, Dusan Fister and Riko Šafarič ◆ Izdelava ogrodja robota s pomočjo 3D tiskalnika Dusan Fister, Riko Šafarič, Iztok Jr. Fister and Iztok Fister ◆ Nastavljanje parametrov regulatorja z optimizacijskimi algoritmi Tadej Jerovšek, Martin Kraner, Tadej Ganza, Tomaž Cebek and Borko Bošković ◆ Analiza sentimenta z uporabo emotikonov in besednih zvez Xiaocheng Du, Tao Gao and Yaoquan Yang ◆ MySQL Database On-line Update Technology Based on JSP Iztok Fister Jr., Iztok Fister and Xin-She Yang ◆ Towards the Development of a Parameter-free Bat Algorithm Marko Grgurovič ◆ Using trees to speed up the Floyd-Warshall algorithm Jernej Grosar, Jure Demšar and Narvika Bovcon ◆ 3D walk through the references of Dutch women writers Žiga Kerec, Marko Balažic, Jure Demšar and Narvika Bovcon ◆ Budget travelling through virtual reality Uroš Mlakar and Iztok Fister ◆ Comparison of DE strategies for Gray-Level Multilevel Thresholding Nándor Póka and Miklós Krész ◆ Processing of next-generation sequencing (NGS) data with MapReduce and HADOOP cluster Aleksandar Tošić ◆ Developing a web application for DNA data analysis Aleksandar Tošić, Aleksandar Todorović, Tanja Štular, Nejc Radež, Tadej Krivec, Tjaž Brelih, Neli Kovšca, Anja Rudež, Aleš Papič, Vladan Jovičić and Marko Palangetić ◆ Personalization of intelligent objects