Proceedings of the 2016 eC 3rd Student Computer Science Research oSR Conference C Stu University of Primorska Press StuCoSReC Preface Proceedings of the 2016 3rd Student Computer Science Research Conference Dear reader, After two successful editions of the Student Computer Edited by Science Research Conference that were organized in Iztok Fister jr. and Andrej Brodnik Maribor and Ljubljana, here are the proceedings of the Reviewers and Programme Committee 3rd Student Computer Science Research Conference that Zoran Bosnić ■ University of Ljubljana, Slovenia is being hosted this year by the University of Primorska Borko Bošković ■ University of Maribor, Slovenia in Koper. Janez Brest ■ University of Maribor, Slovenia Andrej Brodnik ■ University of Primorska The present Conference has again attracted many and University of Ljubljana, Slovenia undergraduate and graduate students presenting their Mojca Ciglarič ■ University of Ljubljana, Slovenia research ideas. As in the past, there are contributions Jani Dugonik ■ University of Maribor, Slovenia from many Computer Science research areas and even Iztok Fister ■ University of Maribor, Slovenia some contributions from other research areas such as, Iztok Fister Jr. ■ University of Maribor, Slovenia for example, Mechatronics. This edition consists of 11 Goran Hrovat ■ University of Maribor, Slovenia papers that are divided into National and Internation- Andres Iglesias ■ Universidad de Cantabria, Spain al sessions. The National session consists of 4 papers, Branko Kavšek ■ University of Primorska, Slovenia while the International session consists of 7 papers. All Miklos Kresz ■ University of Szeged, Hungary Niko Lukač papers were reviewed by at least two members of the ■ University of Maribor, Slovenia Uroš Mlakar International Program Committee, who made comments ■ University of Maribor, Slovenia Peter Rogelj ■ University of Primorska, Slovenia that were sent back to authors in order to improve their Xin-She Yang ■ Middlesex University, United Kingdom papers. Aleš Zamuda ■ University of Maribor, Slovenia In a nutshell, The 3rd Student Computer Science Re- Published by search Conference 2016 once again confirms the main University of Primorska Press missions that were set up back in 2014 when we want- Titov trg 4, si-6000 Koper ed to establish a platform where Computer Science Editor-in-Chief students could come together, make new friends and Jonatan Vinkler connections, discuss their research projects and ideas and encourage each other on their way to becoming Managing Editor Alen Ježovnik Computer Scientists. Koper, 2016 isbn 978-961-6984-37-9 (pdf) www.hippocampus.si/isbn/978-961-6984-37-9.pdf isbn 978-961-6984-38-6 (html) www.hippocampus.si/isbn/978-961-6984-38-6/index.html © 2016 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 (3 ; 2016 ; Ljubljana) Proceedings of the 2016 3rd Student Computer Science Research Conference - StuCoSReC [Elektronski vir] / [edited by Iztok Fister and Andrej Brodnik]. - El. knjiga. - Koper : Univer- sity of Primorska Press, 2016 Način dostopa (URL): http://www.hippocampus.si/isbn/978- 961-6984-37-9.pdf Način dostopa (URL): http://www.hippocampus.si/isbn/978- 961-6984-38-6/index.html ISBN 978-961-6984-37-9 (pdf) ISBN 978-961-6984-38-6 (html) 1. Fister, Iztok, ml. 286799104 Contents Preface II National session ◆ Nacionalna sekcija Zaznavanje plagiatov s pomočjo n-gramov ◆ Žiga Leber, Luka Horvat, Patrik Kokol 5–8 Detekcija jezika v besedilih s šumom ◆ Tilen Škrinjar, Matej Trop, Filip Urh 9–13 Stiskanje slik z algoritmi po vzorih iz narave ◆ Gregor Jurgec, Iztok Fister 15–21 A GPGPU Implementation of CMA-ES ◆ Aleksandar Tošić, Matjaž Šuber 23–26 International session ◆ Mednarodna sekcija Building visual domain-specific languages using the semiotic approach: A case study on EasyTime 27–32 ◆ Iztok Fister jr., Iztok Fister A new population-based nature-inspired algorithm every month: Is the current era coming to the end? 33–37 ◆ Iztok Fister jr., Uroš Mlakar, Janez Brest, Iztok Fister Visualization of cycling training ◆ Dušan Fister, Iztok Fister jr., Iztok Fister 39–44 Izdelava klaviatur MIDI ◆ Primož Bencak, Dušan Fister 45–50 Greedy Heuristics for the Generalized Independent Cascade Model ◆ László Tóth 51–55 Hybrid Cuckoo Search for constraint engineering design optimization problems ◆ Uroš Mlakar 57–60 Weights Optimization in Statistical Machine Translation using Modified Genetic Algorithm ◆ Jani Dugonik 61–65 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October III StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October IV Zaznavanje plagiatov s pomo čjo n-gramov Žiga Leber Luka Horvat Patrik Kokol Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru 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, SI-2000 Smetanova ulica 17, SI-2000 Smetanova ulica 17, SI-2000 Maribor, Slovenija Maribor, Slovenija Maribor, Slovenija ziga.leber1@student.um.si luka.horvat@student.um.si patrik.kokol@student.um.si Marko Očko Univerza v Mariboru Fakulteta za elektrotehniko, računalništvo in informatiko Smetanova ulica 17, SI-2000 Maribor, Slovenija marko.ocko@student.um.si POVZETEK detekcijo plagiatov. V članku predstavimo postopek avtomatske detekcije plagi- atov s pomočjo n-Gramov in izboljšavo z algoritmom Stupid V praksi se pojavlja več načinov nelegitimne ponovne upo- Backoff. Algoritem deluje na podlagi primerjave povedi iz rabe besedila, ki jih lahko na grobo kategoriziramo v nasle- dokumenta z referenčnim korpusom. Iz rezultatov je razvi- dnji skupini. Plagiati, ki temeljijo na dobesednem kopira- dno, da izboljšan algoritem deluje bolje. Na koncu še po- nju, kjer so deli besedila v celoti prevzeti v originalni obliki. damo zaključke in naše mnenje. Te je praviloma najlažje zaznati. V drugo skupino sodijo plagiati, kjer so bili dobesedno kopirani segmenti besedila Ključne besede zamaskirani. V tem primeru plagiator namenoma prevzame tuje ideje in jih prepiše v svojem slogu brez omembe ori- Plagiati, n-grami, Stupid Backoff ginalnega avtorja. Pri takšni obliki so besede zamenjane s sinonimi, prav tako pa je pogosto zamenjan tudi njihov vr- 1. UVOD stni red. V teh primerih je posledično plagiat dosti težje Plagiat je objava del, ki se pripisujejo drugemu avtorju, brez zaznati [5, 1]. da bi citirali vir iz katerega smo jih pridobili. To predvsem velja v primeru, kjer lahko legitimno pričakujemo, da je delo V tem članku smo za uporabo plagiatov preizkusili metodo originalno. Dejanje je storjeno, z namenom pridobitve ko- opisano v [1]. Ta temelji na primerjavi večih povedi z refe- risti, kreditnih točk ali druge oblike dobička [4]. Pred 18. renčnim korpusom na podlagi n-gramov (zaporednih n ele- stoletjem v Evropi kopiranja oz. prepisovanja in posnema- mentov v dani sekvenci npr. zaporednih n besed v povedi). nja niso dojemali kot nemoralno ali prepovedano početje, Postopek smo dodatno izboljšali z uporabo algoritma Stupid temveč so celo spodbujali k posnemanju velikih mojstrov in Backoff. Delovanje metode preizkusimo za različne velikosti zgledovanju pri njih. V umetnosti je tudi danes težko dolo- n-gramov. Iz pridobljenih rezultatov je razvidno, da tako čiti, če gre za plagiat ali ne, saj se nekateri umetniki zgledu- originalna, kot referenčna metoda delujeta boljše pri nizkih jejo drug pri drugem, lahko pa tudi nezavedno vplivajo drug vrednostih n. Predlagan algoritem izboljša F1-mero za 0.44 na drugega. V znanosti žene plagiatorje želja po ugledu ali %. zaslužku brez lastnega truda, lahko pa pride do kraje in- telektualne lastnine tudi samo zaradi pomanjkanja svojega Članek je organiziran v naslednje odseke. V odseku 2 pred- znanja in sposobnosti [9]. Plagiatorstvo se še posebaj po- stavimo sorodna dela. Nato referenčno metodo in naše iz- javlja v sodobnem času, saj lahko preprosto dostopamo do boljšave opišemo v poglavju 3. Sledijo rezultati in diskusija del drugih avtorjev s pomočjo elektronskih virov. Zato so v odseku 4. Članek s kratkim povzetkom zaključimo v od- raziskovalci razvili veliko različnih postopkov za avtomatsko seku 5. 2. SORODNA DELA Trenutno obstaja že kar nekaj metod za ugotavljanje pla- giatov. Sistem PPChecker [6] razdeli sumljivo besedilo v manjše dele, kot so odstavki in povedi, ter nato posamezne manjše dele primerja z referenčnim korpusom. Problem te metode je, spreminjanje vrstnega reda besed v stavkih, kajti tega ta sistem ne bo zaznal. V Ferret [7] sistemu za detek- cijo plagiatov, se celoten testni dokument razdeli v različne StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 5 n-grame in potem se primerjajo število unikatnih ter ujema-kjer so N (.) n-grami. Če je vrednost C(si|d) nad določe- jočih n-gramov. Večje je ujemanje, večja je verjetnost priso- nim pragom, potem je si klasificiran kot plagiat. Z učenjem tnosti plagiata. Slabost tega pristopa je, da se išče podob- na označeni učni množici smo poiskali prag za določene n- nost oz. primerjava celotnega dokumenta in ne posameznih grame. manjših delov. Obstajajo tudi posebne metode pri katerih dejansko ne iščemo ujemanja celotnih stavkov oz. besedila, 3.2 Izboljšana metoda ampak samo ujemanje določenih besed. V Stamatatos-ovem Referenčna metoda za ugotavljanje plagiata uporablja n- [3] sistemu se uporablja iskanje ujemanje tako imenovanih grame fiksne velikosti in tako ne upošteva manjših n-gramov. prekinitvenih besed, ki so seznam frekvenčno zelo veliko- Pri večjih n-gramih zato pade učinkovitost algoritma, saj so krat uporabljenih besed v besedilu. Izkaže se, da lahko z možnosti enakih zelo majhne. Zato smo dodali pri ugota- ujema-njem teh prekinitvenih besed zelo dobro ugotavljamo vljanju vsebnosti algoritem Stupid Backoff [2] s katerim smo plagiate, tudi ko so besedila zelo spremenjena. začeli upoštevati tudi manjše n-grame. Sami smo se odločili, da bomo uporabili metodo, ki so jo Predlagan algoritem ima prva dva koraka enaka kot refe- uporabili v originalnem članku [1], to je uporaba srednje renčni, nato pa sledijo: poti med PPChecker in Ferret metodama. Namesto, da bi primerjali n-grame celotnega dokumenta, se dokument naj- prej razdeli na manjše dele, to je povedi, in nato se nad njimi 1. Referenčni dokument d razdelimo na vse n-grame pri ugotavlja ujemanje z referenčnim korpusom. čemer je n ∈ {1, 2, ..n}. 3. METODA 2. Vsak n-gram povedi si pri izbranem n testiramo vseb- Z naslednjimi metodami smo poskušali odgovoriti na vpra- nost z enačbo (2). Če je n-gram vsebovan prištejemo šanje, ali je poved si plagiat glede na dokument d iz korpusa. 1, drugače pa rekurzivno preverjamo manjše n-grame. Najprej smo implementirali referenčno metodo iz članka, nato pa smo jo poskusili izboljšati s pomočjo algoritma Stu- 3. Naredimo vsoto vsebnosti vseh n-gramov povedi, jo pid Backoff. normaliziramo in nato preverimo glede na prag, ali je poved plagiat ali ne. 3.1 Originalna metoda Imamo dokument r, za katerega sumimo, da je plagiat. r razdelimo na povedi si. Imamo tudi referenčni korpus D, ki (1, f (bi je sestavljeni iz dokumentov d. Torej nas zanima ali je po- C(bi i−k+1) > 0 i−k+1) = ved s 0.4C(bii−k+2), else i plagiat, ki izvira iz dokumenta d. Prepisane povedi so (2) lahko spremenjene oz. se je kopiral samo del povedi, posa- (1, f(bi) > 0 mezne prepisane besede pa so lahko v pomešanem vrstnem C(bi) = 0, else redu, kar pa oteži samo ugotavljanje plagiata. Ta problem smo rešili z uporabo n-gramov, kajti malo verjetno je, da se Pri čemer je bi bodo n-grami iz različnih dokumentov ujemali. Verjetnost i−k+1 iskan n-gram in f (bi i−k+1) frekvenca iskanega n-grama. seveda pada z višanjem n-ja. Ker pa so prepisane povedi se- stavljene iz delčkov besedila iz različnih delov originalnega dokumenta pa smo celotni dokument r razdeliti na n-grame 4. REZULTATI IN DISKUSIJA in ne na povedi. V sledečem podpoglavju opišemo zgradbo in obliko izbra- nega korpusa. Nato sledi podpoglavje v katerem podrobneje Postopek algoritma je naslednji: predstavimo eksperimentalne rezultate. 1. Dokument, ki vsebuje plagiate razdelimo na posame- 4.1 Korpus zne povedi si. Za potrebe testiranja algoritmov smo uporabili METER kor- pus, ki je zgrajen za analizo po-uporabe besedila. Na voljo 2. Poved si je razdeljena na n-grame, ki sedaj predsta- je v več različnih formatih, mi smo uporabili korpus v for- vljajo poved. matu XML. Podatki v korpusu so deljeni na dva dela. Prvi 3. Referenčni dokument d je razdeljen na n-grame brez del vsebuje 771 novic, ki jih je napisala Press Association predhodnega deljenja na povedi, saj lahko plagiat vse- (PA) in večinoma vsebuje članke o dogajanjih na sodiščih. buje različne dele originalnega besedila. Drugi del korpusa so članki različnih Britanskih novic [8]. Britanski članki so v korpusu razdeljeni na povedi, ki so nato 4. S primerjanjem n-gramov povedi si z dokumentom označeni z rewrite, verbatim ali new. Te oznake nam povedo, ugotovimo ali je poved plagiat, kot je opisano v na- ali je del povedi prepisan, povzet ali na novo napisan glede daljevanju. na referenčne PA članke. Za posamezno poved velja, da je plagiat, če je večji del besed označen kot prepisan ali pov- zet. Na splošno se uporablja enačba |s Za preverjanje plagiata, smo primerjali dobljene n-grame s iV ∪ siR| > 0.4|si| pri čemer s tistimi iz referenčnega besedila s pomočjo enačbe (1). iV in siR predstavljata število povzetih in prepisanih besed, si pa število vseh besed v povedi. Vse skupaj je v |N (si) ∩ N (d)| korpusu 3600 povedi Britanskih novic, od tega jih je po tem C(si|d) = (1) |N (s pravilu 61% označenih kot plagiat. i)| StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 6 4.2 Eksperimentalni rezultati dokumentu. Na podlagi eksperimenta smo določili optimalne vrednosti parametrov in preverili natančnost delovanja obeh metod. naša referenčna Eksperiment smo izvedli tako, da za vse n-grame, n ∈ [1, 5], izvedli izčrpno iskanje optimalnega praga, pri katerem je po- n prag F1-mera prag F1-mera ved klasificirana kot plagiat. Za izmero natančnost metod 1 0,65 0,7668 — — smo uporabili metrike preciznost, priklic in F1-mero. 2 0,40 0,7705 0,34 0,68 3 0,22 0,7641 0,17 0,66 Pri unigramih je priklic pri obeh metodah, za vse vrednosti 4 0,10 0,7581 — — praga pod 0,7, zelo visok (skoraj 1,0). Posledično zaznamo 5 0,04 0,7505 — — skoraj vse plagiate. Klub temu pa je preciznost nizka, saj je verjetnost, da se posamezna beseda iz povedi pojavi v Table 1: Primerjava rezultatov referenčnem dokumentu dokaj velika. Pri večjih n-gramih je priklic nižji, saj na stopnjo zaznavanja vpliva tudi zamenjan Z uporabo izboljšane metode se F vrstni red. Najboljši rezultat smo dobili pri bigramih pri 1-mera za vse n-grame ne- koliko izboljša. Učinek je najbolj očiten pri večjih n-gramih, pragu 0,25, kjer je vrednost F1-mere 0,76, kar je razvidno kjer je izboljšava skoraj 10 %. To je posledica dejstva, da tudi iz slike 1. v primeru, ko algoritem ne najde ustreznega n-grama upo- rabi naslednji (n-1)-gram. Ponovno imajo najboljšo F1-mero bigrami, vendar, kot lahko vidimo na sliki 2, trigrami ne za- 0.9 ostajajo za veliko. Najboljša F1-mera (0,77) je pri pragu 0,4, kar je za 0,44 % boljše od prejšnega rezultata (0,76). 0.8 Preciznost 0.7 0.9 0.6 0.00 0.25 0.50 0.75 0.8 Prag Preciznost 0.7 1.00 0.6 0.75 0.00 0.25 0.50 0.75 Prag 0.50 Priklic 1.00 0.25 0.75 0.00 0.25 0.50 0.75 0.50 Prag Priklic 0.8 0.25 0.6 0.00 0.25 0.50 0.75 Prag 0.4 0.8 F metrika 0.2 0.6 0.00 0.25 0.50 0.75 Prag 0.4 F metrika NGram 1 2 3 4 5 0.2 Figure 1: Rezultati za referenčno metodo 0.00 0.25 0.50 0.75 Prag Rezultati, ki smo jih dobili so v vseh primerih za približno NGram 1 2 3 4 5 12 % boljši od tistih iz [1]. Primerjava izboljšanih rezultatov s tistimi, ki jih je dosegla referenčna metoda je predstavljena Figure 2: Rezultati za izboljšano metodo v tabeli 1. V [1] so se, podobno kot pri nas, kot najboljši izkazali bigrami, vendar je v njihovem članku F1-mera 0,68, pri nas pa 0,76. Predvidevamo, da je to zato ker smo pri 5. ZAKLJU ČEK predprocesiranju odstranili vsa ločila. Posledično je število Dobili smo boljše rezultate, kot v referenčnem članku. Refe- vseh možnih besed v našem primeru dosti nižje, kar poveča renčno metodo smo dodatno izboljšali s pomočjo algoritma verjetnost, da se bo beseda v povedi pojavila v referenčnem Stupid Backoff. Pri izbiri n-jev med 2 in 5 za n-grame je StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 7 izboljšana metoda dosegla boljše rezultate. Na primer pri izbiri petgramov smo dobili 10% boljše rezultate. Pri izbiri bigramov pa so se ti izboljšali za 0,44 %. Ugotovili smo tudi, da je najbolj optimalna izboljšava bila pri n=5. 6. REFERENCES [1] A. Barrón-Cede˜ no and P. Rosso. Advances in Information Retrieval: 31th European Conference on IR Research, ECIR 2009, Toulouse, France, April 6-9, 2009. Proceedings, chapter On Automatic Plagiarism Detection Based on n-Grams Comparison, pages 696–700. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. [2] T. Brants, A. C. Popat, P. Xu, F. J. Och, and J. Dean. Large language models in machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 858–867, Prague, Czech Republic, June 2007. Association for Computational Linguistics. [3] S. E. Plagiarism detection using stopword n-grams. J. Am. Soc. Inf. Sci., 62: 2512–2527. doi: 10.1002/asi.21630, 2011. [4] T. Fishman. “we know it when we see it” is not good enough: toward a standard definition of plagiarism that transcends theft, fraud, and copyright. 2009. [5] B. Gipp. Citation-based plagiarism detection–idea, implementation and evaluation. 2009. [6] G. A. Kang N. Ppchecker: Plagiarism pattern checker in document copy detection. TSD 2006. LNCS, vol. 4188,pp. 661–667. Springer, Heidelberg, 2006. [7] M. Lyon C., Barrett R. A theoretical basis to the automated detection of copying between texts, and its practical implementation in the ferret plagiarism and collusion detector. Plagiarism: Prevention, Practice and Policies Conference, Newcastle, 2004. [8] S. L. P. Paul Clough, Robert Gaizauskas. Building and annotating a corpus for the study of journalistic text reuse. 3rd International Conference on Language Resources and Evaluation, 2002. [9] Wikipedia. Palgiatorstvo — Wikipedia, the free encyclopedia, 2016. [Online; accessed 25-Sept-2016]. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 8 Detekcija jezika v besedilih s šumom Tilen Škrinjar Matej Trop Filip Urh Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru 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 17 Smetanova 17 Smetanova 17 2000 Maribor, Slovenija 2000 Maribor, Slovenija 2000 Maribor, Slovenija skrinjar.tilen@gmail.com trop.matej@gmail.com filipurh@gmail.com POVZETEK tne novice, izobraževalne spletne strani, forumi ipd. Za razi- Večina besedil na internetu je slovnično nepravilnih (ozi- skovalce so najbolj zanimiva socialna omrežja in forumi, kjer roma vsebujejo šum), saj uporabniki pri komentiranju in na se izmenja največ mnenj o raznih produktih, filmih, glasbi, raznih forumih ne uporabljajo knjižnega jezika. V članku kar so še posebej zanimivi podatki za oglaševalce, vendar se predstavljamo pet metod za razpoznavo jezika iz besedil s pri razpoznavi besedil iz teh dveh kategorij pojavijo težave. šumom. Večina metod, ki se ukvarjajo s to problematiko, Ta besedila namreč pogosto vsebujejo okrajšave, "tage" ali imajo težave pri razpoznavi jezika, ki so kratka ali pa vse-pa so v celoti zapisana v SMS stilu in jih je nemogoče raz- bujejo napake. poznati z običajnimi postopki. Eksperimenti, ki smo jih izvedli nad testnimi množicami, so V sklopu te raziskave smo preučili in implementirali štiri pokazali, da so lahko omenjene metode dokaj uspešne pri predlagane metode, ki so poimenovane CBA (angl. Charac- identifikaciji jezikov. Naša metoda pa uspešnost poveča še ter Based identification Algoritm), ki temelji na znakih iz za 3.6 %. učnega korpusa, WBA (Word Based identification Algori- thm), ki temelji na besedah ter dva hibridna algoritma. Pri tem zaporedno ali pa paralelno izvedemo algoritma CBA in 1. UVOD WBA [3]. Z napredovanjem tehnologije, ki omogoča vedno hitrejše de- ljenje informacij med ljudmi, se je povečala količina tekstov- V drugem poglavju bomo na kratko predstavili nekaj podob- nih podatkov na internetu in v podatkovnih bazah. Zaradi nih del na področju identifikacije jezika. Nato bomo pred- tega je črpanje informacij iz takih podatkov postalo težavno, stavili naš učni korpus in identifikacijske metode, ki smo jih še posebej če mora to opravljati človek. Na to temo je bilo implementirali ter izboljšavo le-teh. V zadnjem podpoglavju opravljenih veliko raziskav, ki so stremele k avtomatični ek- bodo predstavljeni rezultati in primerjave uporabljenih me- strakciji podatkov iz teksta. Ponavadi pa moramo pri teh tod. metodah vnaprej vedeti, v katerem jeziku so informacije, ki jih analiziramo. Zaradi tega postane identifikacija jezika v nekem dokumentu zelo pomemben del analiznega procesa. 2. SORODNA DELA Zaradi pomembnosti veliko raziskovalcev preučuje avtoma- V članku [5] so za korpus uporabljali Wikipedio [2] in Euro-tično identifikacijo jezikov. Parl [1]. Za detekcijo jezika so uporabili trigrame, ki delujejo zelo dobro na daljših besedilih (skoraj 100%), pri kratkih Izziv predstavlja predvsem problem, kako prepoznati zelo pa detekcija pade pod 50% in metoda postane neuporabna. kratka sporočila, kakršna na primer uporabljamo na raznih Zanimivo je tudi, da je bila detekcija bolj uspešna z učno forumih ali v tekstovnih SMS sporočilih. Velika večina me- množico besedil iz Wikipedie, medtem ko je EuroParl kor- tod namreč temelji na statističnem modelu. Za izgradnjo pus ustvarjen za strojno učenje imel tudi do 90% napačno takšnega modela potrebujemo relativno dolgo testno bese- identifikacijo. dilo, če želimo jezik pravilno identificirati. V nasprotnem primeru algoritem ne zna odločiti, v katerem jeziku je te- V članku [7] so se ukvarjali z N-grami in razdaljo med re-stno besedilo. zultati. Iz učne množice ustvarijo znakovne in besedne N- grame, nato z enačbo za navzkrižno entropijo ali drugih Dandanes poznamo več kategorij podatkov, ki so lahko sple- enačb za razdalje izračunajo razdaljo med najboljšimi uč- nimi N-grami in testnim besedilom. Glede na razdaljo se iz- računa končna ocena, na podlagi katere se identificira jezik besedila. Najbolje je delovala metoda z navzkrižno entro- pijo, vse metode pa so imele verjetnost detekcije nad 90%. Drugi algoritmi so delovali na podlagi strojnega učenja [8] in na podlagi modela HMM (angl. Hidden Markov Models). Model se med drugim uporablja v razpoznavanju govora, biologiji, meteorologiji, ipd. Iz učne množice ustvarimo vek- torje besed in z njimi spreminjamo parametre modela. Re- StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 9 zultate so izmerili samo na petih jezikih in jih primerjali z Predlagana sta tudi dva hibridna algoritma, ki bi naj iz-N-grami spremenljive dolžine. Rezultati so dokaj podobni, boljšala natančnost zaznavanja jezika. Prvi hibridni pristop HMM model v nekaterih primerih deluje malo bolje. je sekvenčni in deluje tako, da najprej izvedemo algoritem CBA in če ta kot najboljši rezultat vrne enake frekvence za Algoritem za detekcijo jezika je tudi metoda z N-grami [4], več jezikov, izvedemo še WBA. V tem primeru upoštevamo kjer si ustvarimo profile jezikov in nato iz testnega besedila rezultate algoritma WBA. ustvarimo N-grame ter preverimo kateremu profilu se naj- bolj prilegajo. Ta metoda ima kar nekaj težav pri detekciji Druga hibridna metoda temelji na obeh algoritmih CBA in v primerjavi s prejšnjimi ne glede na dolžino besedila. WBA. Pri drugem hibridnem pristopu oba algoritma izve- demo paralelno in ko opravita izračune za vse jezike, se- V članku [6] so predlagali identifikacijo z odločitvenimi dre- štejemo posamezne frekvence po enačbi (2) in nato razpo-vesi. Eksperiment so izvedli le na dveh arabskih jezikih: znamo, za kateri jezik gre na podlagi postopka opisanega arabščini in perzijščini. Za oba jezika je metoda delovala pri CBA. zelo dobro. 3. METODE ZA IDENTIFIKACIJO JEZIKOV Sum = f reqCBA + f reqW BA (2) V tem podpoglavju bomo opisali metode, ki so jih razvili v članku [3]. Te metode smo tudi implementirali. Detekcija Naš doprinos je tretji hibridni algoritem, pri katerem smo poteka v več korakih. Najprej v program naložimo refe- uporabili drugačen izračun kot je pri ostalih algoritmih. Al- renčne profile za vse jezike, tj. učni korpus besed in znakov, goritem CBA smo polovično utežili, saj daje slabše rezultate. nato preberemo datoteko ali več datotek. Iz njih odstranimo Prilagodili smo algoritem WBA. Tu smo upoštevali vrstni nepotrebne znake, ki bi lahko vplivali na detekcijo in bese- red najpogostejših besed. Frekvence za besede se izračunajo dilo razrežemo na besede in znake. Nad temi podatki nato po enačbi (3): opravimo detekcijo. ( N − rank) /N, (3) Prvi algoritem se imenuje CBA (angl. Character Based identification Algorithm) in temelji na znakih v jeziku. Učni kjer rank predstavlja red pogostosti besede v določenem je- korpus uporablja zbirko predefiniranih znakov za vsak je- ziku, N pa število besed v učnem korpusu, ki pri vseh je- zik. Algoritem izračuna frekvenco vsakega znaka v bese- zikih znaša dvajset. Red najpogostejše besede se začne z 0 dilu. Nato sešteje vse frekvence po enačbi (1). Na koncu in se pri manj pogostejših besedah nadalje poveča za 1. Za klasificiramo besedilo glede na najvišjo frekvenco. primer vzamemo tri besede. Prva beseda se nahaja na pr- vem mestu, druga na petem, tretja pa na dvajsetem mestu najpogostejših besed v jeziku. Število vseh najpogostejših X Sum besed je dvajset. Za prvo besedo izračunamo frekvenco kot i = f requencyij (1) (20 - 0) / 20 = 1, za drugo (20 - 4) / 20 = 0.8 in za tretjo j=1 (20 - 19) / 20 = 0.05. Če skupaj strnemo metodo, dobimo naslednjo enačbo: Problem se pojavi, ko več jezikov deli skupni nabor učnih znakov in zaradi tega dobi isto frekvenco pri seštevku zna- kov. To rešimo tako, da sledimo posebnemu testnemu zapo- 1 redju za vsak jezik: Sum = ∗ f reqCBA + modF reqW BA, (4) 2 if max _ f req = slo _ f req and max _ f req 6= bos _ f req kjer se modFreqWBA izračuna po enačbi (3). then Return Slovenian else Pass to next test end if 4. EKSPERIMENT 4.1 Učni in testni korpus Kjer je max_freq največji seštevek vseh frekvenc, slove- Za učni korpus in testna besedila smo uporabili kodiranje nian_freq in bos_freq pa sta frekvenci za posamezen jezik. UTF-8, saj podpira največ znakov, ki jih vsebujejo testirani jeziki. Zaradi različnih jezikov smo sami definirali vrstni red jezi- kov. Algoritem ponavljamo v naslednjem zaporedju: hrva- V naši raziskavi smo se osredotočili na jezike, ki so si med ščina, srbščina (latinica), bosanščina, slovenščina, češčina, seboj podobni. Zaradi tega smo sestavili svoj učni in testni poljščina, slovaščina, makedonščina, bolgarščina. Ta način korpus. Potrebne informacije smo pridobili na svetovnem ni najboljši, saj lahko različne vhodne jezike identificiramo spletu. Pri učnem korpusu smo definirali besede in znake, različno dobro. ki zaznamujejo jezik. V članku [3] so za razpoznavo Uporabili dvajset najpogostejših besed za posamezen jezik in nekaj WBA (angl. Word Based identification Algorithm) je zelo znakov, na osnovi katerih se jezik razlikuje od drugih. Na podoben prejšnjemu algoritmu, le da deluje nad besedami enak način smo se tudi mi lotili izdelave korpusa. Ta vse- besedila, ki ga identificiramo. Besedilo razčlenimo na be- buje podatke za devet jezikov. Večina jezikov si je med se- sede in izračunamo frekvence za vsako besedo. Nadaljnja boj podobna, saj le-ta spadajo v skupino slovanskih jezikov. klasifikacija deluje enako, kot je opisano v metodi CBA. Razpoznavali smo naslednje jezike: bolgarščina, bosanščina, StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 10 češčina, hrvaščina, srbščina (latinica), makedonščina, polj- ščina, slovaščina in slovenščina. Bosanščina, hrvaščina in Tabela 1: Uspešnost metod v posameznem jeziku % srbščina so si med seboj zelo podobni, medtem ko se bol- Uspešnost metod % garščina precej razlikuje od ostalih jezikov. Testni korpus CBA WBA HA1 HA2 HA3 vsebuje kratka besedila do stopetdeset besed. Ta besedila Bolgarščina 100 100 100 100 100 niso sestavljena iz pravilno napisanih besedil, ampak vse- Bosanščina 80 4 80 4 4 bujejo napake, okrajšave, nepomembne znake in citate itd. Češčina 48 88 48 92 96 Za testni korpus smo uporabili petindvajset testnih besedil Hrvaščina 0 92 0 92 84 za posamezni jezik. Vsak testni primer je dolg nekaj stav- Srbščina (latinica) 0 16 0 16 40 kov. Besedila smo dobili iz različnih spletnih forumov, kot Makedonščina 0 100 0 100 96 so športni forum, elektrotehniški forum in ostali. Poljščina 72 100 72 100 100 Slovaščina 88 80 88 92 96 Slovenščina 72 88 72 88 96 4.2 Analiza in rezultati Vse metode, ki smo jih implementirali, smo nato tudi pre- izkusili na praktičnih primerih. Za vsak jezik smo ustvarili matriko klasifikacijskih napak in v njej prikazali dobljene rezultate. Naše rezultate smo poskušali primerjati z orodji za razpoznavo jezika, kot sta Google Prevajalnik in Prevajalnik Bing. Prvi ne prepoznava srbščine (latinica), drugi pa bosanščine in makedonščine. Zaradi tega primerjava rezultatov med orodji ni smiselna. Klasifikacijo smo opravili nad vsemi jeziki. V tabeli 3 in 4 so prikazani rezultati teh meritev. Tabela predstavlja ma- triko klasifikacijskih napak. Prikazani so jeziki testnega be- sedila in uporabljene metode. V eni celici so štiri vrednosti. Vsaka vrednost pripada eni od metod. Posebej so za vsako Tabela 2: Uspešnost metod v % metodo, po vrsti: CBA, WBA, HA1, HA2 in HA3. Za pri- Uspešnost metod % mer si vzemimo celico v zadnjem stolpcu in vrstici v tabeli CBA WBA HA1 HA2 HA3 4. Ta znaša 18/22/18/24. Prva vrednost 18 je število pra-Vsi jeziki 51.1 74.2 51.1 76 79.6 vilno razpoznanih besedil po algoritmu CBA, vrednost 22 je število razpoznanih besedil po metodi WBA, nadalje 18 po metodi HA1, 22 po metodi HA2 in 24 po naši metodi oziroma HA3. V tabeli 1 in tabeli 2 lahko zasledimo tudi uspešnost posameznih metod v jezikih in skupaj. Če pogledamo za primer zadnjo vrstico v tabeli 1, opazimo, da je najbolj pravilno klasificiral besedila naš algoritem - z 96 % natančnostjo, najslabše pa CBA in HA1 algoritem z 72 % natančnostjo. Iz rezultatov vidimo, da metode slabše de- lujejo med jeziki, ki so si podobni (srbščina, hrvaščina in bosanščina). Metoda CBA deluje odvisno od predefiniranih znakov. Vidimo, da so rezultati enaki pri metodi CBA in HA1. Razlog je v tem, da pri testih nismo dobili enakih frekvenc. Dobro deluje uravnotežena metoda HA2. V naši 5. ZAKLJU ČEK metodi smo bolj utežili metodo WBA, saj daje boljše re- zultate. CBA smo manj utežili. Zaradi teh dveh izboljšav V članku smo analizirali obstoječe metode pri zaznavanju smo dobili 3.6 % izboljšavo. Boljšo razpoznavo besedil smo jezika in predlagali svojo metodo. Algoritem, ki je deloval dobili pri češčini, slovaščini in slovenščini. na principu znakov, je slabo zaznaval jezike, saj je težko na- rediti nekakšen statistični model, ki bi prinesel dovolj razno- like vzorce v učni korpus. Več sreče smo imeli z besedami, kjer je algoritem zaznaval jezike precej bolje. Tudi hibridna metoda in naša metoda sta vračali boljše rezultate. Naš al- goritem deluje najbolje, saj smo pogostost pojavljanja besed v jeziku dodatno obtežili. Učni korpus, ki smo ga uporabili, je bil sestavljen iz več 100 besedil iz spleta, ki so bila pretvorjena v besedne in zna- kovne učne baze podatkov v obliki tekstovnih datotek. Na podlagi prejšnjih metod smo poskušali izboljšati detekcijo, ki se razlikuje na drugačen izračun od prejšnjih hibridnih metod. Ugotovili smo, da naša metoda deluje boljše kot druge hibridne metode, vendar pa je to odvisno od besedila, ki ga procesiramo. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 11 Tabela 3: Klasifikacija jezikov, prvi del Razpoznan razred (CBA, WBA, HA1, HA2, HA3) bg-BG bos-BOS cs-CZ hr-HR Lt-sr-SP bg-BG 25/25/25/25/25 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 razred bos-BOS 5/0/5/0/0 20/1/20/1/1 0/0/0/0/0 0/17/0/17/13 0/6/0/6/10 cs-CZ 0/0/0/0/0 0/1/0/0/0 12/22/12/23/25 0/0/0/0/0 0/0/0/0/0 hr-HR 1/0/1/0/0 11/1/11/1/ 0 0/0/0/0/0 0/23/0/23/21 0/1/0/1/4 Dejanski Lt-sr-SP 1/0/1/0/0 20/1/20/1/0 0/0/0/0/1 0/20/0/20/14 0/4/0/4/10 mk-MK 25/0/25/0/ 1 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 pl-PL 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 sk-SK 3/0/3/0/0 0/0/0/0/0 0/1/0/1/1 0/0/0/0/0 0/0/0/0/0 sl-SI 0/0/0/0/0 7/0/7/0/0 0/1/0/1/1 0/2/0/2/0 0/0/0/0/0 Tabela 4: Klasifikacija jezikov, drugi del Razpoznan razred (CBA, WBA, HA1, HA2, HA3) mk-MK pl-PL sk-SK sl-SI bg-BG 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 razred bos-BOS 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 0/1/0/0/1 cs-CZ 0/0/0/0/0 0/1/0/0/0 11/1/11/2/0 2/0/2/0/ 0 hr-HR 0/0/0/0/0 0/0/0/0/2 0/0/0/0/0 13/0/13/0/0 Dejanski Lt-sr-SP 0/0/0/0/0 0/0/0/0/9 0/0/0/0/0 4/0/4/0/0 mk-MK 0/25/0/25/24 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 pl-PL 0/0/0/0/0 18/25/18/25/25 7/0/7/0/0 0/0/0/0/0 sk-SK 0/0/0/0/0 0/4/0/1/0 22/20/22/23/24 0/0/0/0/0 sl-SI 0/0/0/0/0 0/0/0/0/0 0/0/0/0/0 18/22/18/22/24 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 12 6. REFERENCE [1] European parliament proceedings parallel corpus 1996-2011. http://www.statmt.org/europarl/. Accessed: 2016-05-23. [2] Wikipedia. https://www.wikipedia.org/. Accessed: 2016-05-23. [3] K. Abainia, S. Ouamour, and H. Sayoud. Robust language identification of noisy texts: Proposal of hybrid approaches. In 2014 25th International Workshop on Database and Expert Systems Applications, pages 228–232, Sept 2014. [4] W. B. Cavnar and J. M. Trenkle. N-gram-based text categorization. In In Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, pages 161–175, 1994. [5] R. M. Milne, R. A. O’Keefe, and A. Trotman. A study in language identification. In Proceedings of the Seventeenth Australasian Document Computing Symposium, ADCS ’12, pages 88–95, New York, NY, USA, 2012. ACM. [6] A. Selamat, N. C. Ching, and Y. Mikami. Arabic script web documents language identification using decision tree-artmap model. In Convergence Information Technology, 2007. International Conference on, pages 721–726, Nov 2007. [7] A. K. Singh. Study of some distance measures for language and encoding identification. In Proceedings of the Workshop on Linguistic Distances, LD ’06, pages 63–72, Stroudsburg, PA, USA, 2006. Association for Computational Linguistics. [8] A. Xafopoulos, C. Kotropoulos, G. Almpanidis, and I. Pitas. Language identification in web documents using discrete {HMMs}. Pattern Recognition, 37(3):583 – 594, 2004. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 13 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 14 Stiskanje slik z algoritmi po vzorih iz narave Gregor Jurgec Iztok Fister Univerza v Mariboru Univerza v Mariboru Fakulteta za elektrotehniko, računalništvo in Fakulteta za elektrotehniko, računalništvo in informatiko informatiko Smetanova 17, Maribor Smetanova 17, Maribor gregor.jurgec@gmail.com iztok.fister@um.si POVZETEK (npr. živali ali žuželk), ki rešujejo vsakodnevne probleme po- V članku predstavljamo postopek stiskanja slik na inova- razdeljeno in kolektivno [1]. S kombinacijo značilnosti obeh tiven način s pomočjo optimizacijskih algoritmov iz dveh družin lahko razvijemo hibridne algoritme, ki so sposobni različnih družin, tj. evolucijskih algoritmov in algoritmov reševanja tudi kompleksnejših optimizacijskih problemov. S na osnovi inteligence rojev. V naši raziskavi za reševanje hibridizacijo različnih delov algoritma dodamo osnovnemu problema stiskanja slik uporabljamo diferencialno evolucijo algoritmu domensko specifično znanje domene [4, 5]. in optimizacijo s kukavičjim iskanjem. Osnovna algoritma izboljšamo z adaptacijskimi in hibridizacijskimi metodami. V tem članku rešujemo problem stiskanja slik z izboljšanima Stiskanje slik izvedemo s pomočjo množice primitivnih ge- optimizacijskima algoritmoma diferencialne evolucije [10] in ometrijskih oblik trikotnikov. Razvita algoritma testiramo kukavičjega iskanja [11] sposobna generiranja slik, ki zase- na realnih primerih stiskanja slik in kakovost rezultatov sti- dajo manj prostora, ampak slabše kakovosti. Sliko predsta- skanja primerjamo med seboj. Z izboljšanima algoritmoma vljamo s trikotniki narisanimi na platno, ki so določeni s dobimo zelo dobre rezultate stisnjenih slik, saj podobnost koordinatami oglišč in barvo. Trikotniki so učinkoviti za to teh slik v primerjavi z izvornimi slikami v najslabšem pri- nalogo saj pokrivajo več slikovnih pik kot ena sama točka in meru presega 89,70 %, v najboljšem primeru pa dosežemo omogočajo prekrivanje in prosojnost barv v določeni regiji. 92,08 %. Naš cilj je, da bi bila izrisana slika čim bolj podobna ori- ginalni sliki. V tem članku se zgledujemo in nadgrajujemo Kjučne besede delo iz [13, 7], kjer s pomočjo trikotnikov in samo adaptivne diferencialne evolucije oziroma genetskega algoritma posku- evolucijski algoritmi, inteligenca rojev, diferencialna evolu- šajo zgraditi približen model slike. cija, kukavičje iskanje, stiskanje slik S tem delom želimo pokazati, da lahko z izboljšanima algo- 1. UVOD ritmoma na osnovi obnašanja kukavic in diferencialne evo- Z razvojem naprednih senzorjev za zajem slik visoke ločlji- lucije uspešno stisnemo izvorno sliko. Pri tem lahko ugo- vosti se povečuje velikost zajetih posnetkov. Pri tem pri- tovimo, da sta oba algoritma primerna za stiskanje slik s demo do problema shranjevanja slik, saj nestisnjene slike trikotniki, tj. na inovativen način in s pomočjo novih algo- zavzemajo ogromno prostora na spominskih medijih. Da ritmov, po vzoru iz narave. Tak način stiskanja slik lahko prihranimo prostor, uporabljamo različne optimizacijske al- postane dobra alternativa obstoječim algoritmom stiskanja goritme, ki stisnejo podatke na račun izgube informacij o slik. Seveda ti algoritmi potrebujejo še dodatne izboljšave, sliki. Za te izgube seveda želimo, da so čim manjše. Algo- vendar so se kot osnova izkazali zelo dobro, kar dokazujejo ritmi stiskanja slik iščejo podobnosti v podatkih, oz. sku- tudi rezultati v nadaljevanju. šajo podatke, zajete s senzorji, spraviti v čim kompaktnejšo obliko. Struktura članka v nadaljevanju je naslednja. Drugo po- glavje se ukvarja s podanimi splošnimi informacijami o ko- Glavna razlika med evolucijskimi algoritmi in algoritmi na diranju slik. V tretjem in četrtem poglavju predstavimo oba osnovi inteligence rojev je, da evolucijski algoritmi [4] pri op- izboljšana algoritma za stiskanje slik. Peto poglavje primerja timizaciji simulirajo naravno evolucijo z operatorji mutacije, rezultate stiskanja realnih slik z izboljšanima algoritmoma. križanja in selekcije [3], medtem ko delovanje algoritmov na osnovi inteligence rojev temelji na obnašanju bioloških vrst 2. KODIRANJE SLIKE V našem delu uporabljamo izgubni način stiskanja slik, ker imajo naše stisnjene slike nepravilnosti in so popačene. Naša slika je predstavljena z množico barvnih trikotnikov, narisa- nih na črno podlago, ki je iste velikosti kot originalna slika. Množica trikotnikov predstavlja sliko, podobno originalni. Vsak trikotnik je sestavljen iz treh točk s koordinatami x, y in barvo, s katero je obarvan, v barvnem prostoru rdeče- zeleno-modro-alfa (angl. Red, Green, Blue, Alpha, krajše RGBA). Zelo pomembno je, da uporabimo prosojnost tri- StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 15 kotnikov, s čimer dosežemo prekrivanje trikotnikov in s tem dobimo veliko različnih barv, ki sestavljajo sliko.   višinaSlike širinaSlike  P P R R ~ x∗ − i,j ~ xi,j   i=1 j=1  Množico barvnih trikotnikov, ki sestavljajo sliko, kodiramo      255 · višinaSlike · širinaSlike     v vektor na naslednji način: vektor ~ x = ( ~ T1, ~ T2, ~ T3, ..., ~ Tmax)   višinaSlike širinaSlike    P P G G  ~ x∗ − ~ x predstavlja množico trikotnikov ~ T f (~ x) = 100% · 1 −  i,j i,j  (1) i, ∀i ∈ {1, ..., max}, kjer   i=1 j=1    +  max določa število trikotnikov, ki sestavljajo sliko. Vsak od   255 · višinaSlike · širinaSlike     teh trikotnikov je kodiran v vektor ~ T višinaSlike širinaSlike    i = (x1, y1, x2, y2, x3, y3, P P B B   ~ x∗ − i,j ~ xi,j  R, G, B, A), ki je sestavljen iz celih števil, kjer pari x   i=1 j=1  i, yi, ∀i ∈ + {1, 2, 3} predstavljajo koordinatne točke oglišč trikotnika, 255 · višinaSlike · širinaSlike skalarji R, G, B barvo in A prosojnost trikotnika. 3. DIFERENCIALNA EVOLUCIJA Diferencialna evolucija (angl. Differential Evolution, krajše Slika 1 prikazuje množico prekrivajočih barvnih trikotnikov DE) rešuje optimizacijski problem z izboljševanjem posame- na črnem ozadju v zgodnji fazi delovanja optimizacijskih al- znih rešitev iz populacije. Iz obstoječih rešitev tvori posku- goritmov. sne rešitve (angl. candidate solution) z dodajanjem razlike naključno izbranih vektorjev (mutacijska strategija), te pa je potrebno vrednotiti. Vrednosti elementov vektorjev po- skusne rešitve, ki so izven definiranih območij popravimo na zgornje ali spodnje meje v operaciji popravljanja. Če je poskusna rešitev boljša od obstoječe, ta rešitev zamenja ob- stoječo v populaciji. Ta postopek ponavljamo za vsakega po- sameznika v populaciji rešitev v vsaki generaciji algoritma, dokler ni izpolnjen pogoj zaustavljanja [10]. Model diferen- cialne evolucije je prikazan na sliki 2. Slika 1: Osnovni prikaz slike s trikotniki. 2.1 Optimizacijski problem in kriterijska funkcija Optimizacija je postopek iskanja najboljših vhodnih para- metrov pri znanem modelu in znanih izhodnih parametrih [6, 4]. Optimizacijski problem P definiramo kot četvorko P = hI, S, f, cilj i, kjer pomenijo: I množico vseh nalog, S množico dopu- stnih rešitev problema, f kriterijsko funkcijo (angl. objec- tive function), s katero ocenjujemo kakovost rešitve, in cilj, s katerim povemo ali kriterijsko funkcijo maksimiziramo ali minimiziramo. Vrednosti kriterijske funkcije so lahko ska- larji ali v primeru več-kriterijskih problemov vektorji [9, 12]. Kriterijska funkcija v našem primeru primerja vsako isto le- žečo slikovno piko generirane slike s slikovno piko na origi- nalni sliki. Vsako slikovno piko primerjamo po vseh treh barvnih komponentah R, G, B. Vsoto razlik isto ležečih sli- kovnih pik pri vsaki od treh komponent delimo s produktom med višino in širino slike ter z vsemi možnimi odtenki vsake od barv RGB. Z rezultatom dobimo vrednost različnosti slik, ki ga odštejemo od ena in dobimo podobnost med slikama. To pomnožimo s 100 % in ta vrednost potem predstavlja po- dobnost najdene slike v primerjavi z originalno v odstotkih. Naš cilj je, da je podobnost čim večja in zato moramo našo kriterijsko funkcijo maksimizirati. Naša kriterijska funkcija f (~ x) je opisana z enačbo 1, kjer ~ x∗ predstavlja originalno, referenčno sliko, ~ x pa stisnjeno, gene- rirano sliko. Indeksa xi, ∀i ∈ {1, ...višinaSlike} in yj , ∀j ∈ {1, ...širinaSlike} določata trenutni položaj opazovane sli- kovne pike. Oznake R, G in B pa definirajo, v kateri kompo- nenti barve RGB se nahajamo. Konstanta 255 določa število različnih odtenkov barve. Slika 2: Model diferencialne evolucije StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 16 Psevdo-kod originalnega algorithma DE prikazuje algoritem 1. Pri tej izboljšavi gre za izbiro mutacijske strategije. Kombi- niramo med strategijo 0DE/rand/1/bin0 in 0DE/best/1/bin0. Algoritem 1 Algoritem DE Privzeto uporabljamo strategijo 0DE/rand/1/bin0. Verje- 1: inicializacija; tnost izbire strategije 0DE/best/1/bin0 v vsaki generaciji pri −−−−−−−−−−−−−−→ 2: najboljsaV rednost0 ← oceniVseResitve; vsakem posamezniku v populaciji je 10−5, ki smo jo dolo- 3: while pogojUstavljanjaIzpolnjen do čili po občutku skozi testiranja. Izbiro strategije in s tem 4: for i ← 1, N baznega vektorja uvedemo pred začetkom mutacije. p do 5: ~ xp ← generirajPoskusnoResitev(~ xt ( i i ); 0DE/best/1/bin0 če U (0, 1) < 10−5, 6: poskusnaVrednost ← oceniPoskusnoResitev(~ xp); i IzbiraStrategije = 0 7: if poskusnaVrednost > f(~ xt DE/rand/1/bin0 drugače. i ) then 8: ~ xt ← i ~ xp; i V zgornji enačbi predstavlja U (0, 1) naključno število iz in- 9: najboljsaVrednostt ← poskusnaVrednost; i tervala [0,1] iz uniformne porazdelitve. Vektor mutacije ~ m 10: end if i pri strategiji 0DE/best/1/bin0 izračunamo po enačbi: 11: end for 12: end while ~ m i = ~ xtbest + F · ~ xtr1 − ~ xtr2 , 3.1 Samoprilagajanje nadzornih parametrov kjer ~ xtbest označuje najboljšega posameznika v trenutni po- pulaciji, F je krmilni parameter, ~ xt v diferencialni evoluciji (jDE) r1 in ~ xtr2 pa sta naključno izbrana vektorja iz trenutne populacije, kjer r1 6= r2. Vektor V literaturi najdemo veliko različnih rešitev, kako nastaviti mutacije ~ mi pri privzeti strategiji 0DE/rand/1/bin0 izraču- nadzorna parametra F in Cr . Izbira primernih vrednosti namo po enačbi: nadzornih parametrov je odvisna od problema, ki ga rešu- jemo. Da se izognemo temu, so avtorji Brest in ostali v [2] ~ mi = ~ xtr1 + F · ~ xtr2 − ~ xtr3 . predlagali izboljšano verzijo algoritma DE, ki nadzorna pa- rametra F in Cr samo-prilagaja med samim izvajanjem. Po- 3.2.2 Ponastavitev posameznika imenovali so ga algoritem jDE. Vsak posameznik v popula- Da se izognemo lokalnemu optimumu, uporabimo mehani- ciji je razširjen z vrednostjo omenjenih parametrov, ki se zem ponastavitve posameznika (angl. random restart) z na- prilagajata in izboljšujeta skozi evolucijo in posledično iz- ključnimi vrednostmi elementov pri operaciji križanja. Kri- boljšata posameznike v poskusni populaciji. Nova nadzorna žanje je prikazano z naslednjo enačbo: parametra F p in C p izračunamo pred mutacijo, tako da i r i  x · U (0, 1) če U imata vpliv na operatorje DE in izračun poskusne rešitve v min,j + xmax,j − xmin,j j (0, 1) < Cr     trenutni generaciji, po enačbah:  ∨ jrand = j ∧ Uj (0, 1) < 10−5, ki,j = m  i,j če Uj (0, 1) < Cr ∨ jrand = j,     xti,j drugače. ( Fl + U1 (0, 1) · Fu če U2 (0, 1) < τ1, F p = i F G i drugače, Če je pri križanju v vsaki iteraciji dimenzije problema slu- ( U3 (0, 1) če U4 (0, 1) < τ2, čajno število U (0, 1) pod pragom 10−5, takrat celoten vektor C p r = i ~ C t k r i inicializiramo na začetne vrednosti in prekinemo križanje, i drugače, drugače pa na pozicijo, ki jo označuje indeks j, v vsaki ite- raciji kopiramo vrednost vektorja mutacije ~ mi ali vrednost kjer je Uj (0, 1) , j ∈ {1, 2, 3, 4} naključna uniformna vre- trenutnega posameznika ~ xti z istim indeksom. dnost iz intervala [0,1] ter τ1 in τ2 verjetnosti za spremembo parametrov F in Cr (tudi hitrosti učenja). Avtorji zanju predlagajo vrednosti τ 3.2.3 Razpršenost populacije in ponastavitev posa- 1 = τ2 = 0, 1. Vrednosti Fl = 0, 1 in Fu = 0, 9 zagotavljata, da je novi parameter F vedno na- meznikov ključno v intervalu [0.1, 1.0]. Novi parameter Cr pa zavzema Po selekciji izračunamo razpršenost populacije. Razpršenost vrednosti v intervalu [0,1] [13]. populacije služi kot merilo raznolikosti populacije. Izraču- namo jo s standardnim odklonom od povprečne vrednosti 3.2 Modificirana diferencialna evolucija kriterijske funkcije posameznikov v populaciji, ki ga izraču- Modificirana verzija diferencialne evolucije (krajše MoDE) namo po enačbi: za stiskanje slik vsebuje več prilagoditev in izboljšav. Naj- Np prej prilagodimo osnovni algoritem na obstoječ algoritem P f itnesi jDE, ki je opisan v prejšnjem poglavju. Nato razširimo jDE povprečje = i=1 , algoritem s strategijo 0DE/best/1/bin0, s katero dosežemo, Np da se posamezniki približujejo najboljši rešitvi, okrog katere kjer seštejemo vse vrednosti kriterijske funkcije posamezni- bi lahko bil globalni maksimum. V primeru, da pride do kov v populaciji in jih delimo s številom posameznikov N izgube raznolikosti v populaciji, uporabimo ponovno inicia- p . Povprečje uporabimo pri izračunu standardnega odklona v lizacijo večine posameznikov, s čimer raznolikost populacije enačbi: povečamo. v u Np u P 3.2.1 Kombiniranje mutacijskih strategij (povprečje − f itnes u i)2 t i=1 ’DE/rand/1/bin’ in ’DE/best/1/bin’ stdOdklon = . Np StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 17 Če je standardni odklon oziroma razpršenost populacije manjša od praga, ki ga določimo pri testiranju, ponastavimo 90 % najslabših posameznikov na začetne vrednosti in s tem po- večamo raznolikost populacije. 4. KUKAVIčJE ISKANJE V nadaljevanju predstavljamo osnovni algoritem s kukavi- čjim iskanjem [11] (angl. Cuckoo Search, krajše CS), kjer je vhod v algoritem začetna populacija, sestavljena iz posame- znikov inicializiranih z naključnimi vrednostmi elementov, ki predstavljajo rešitve. Izhod algoritma je najboljša reši- tev oz. najboljši posameznik glede na kriterijsko funkcijo. Osnovni algoritem vsebuje inicializacijo in glavno zanko, ki teče do pogoja ustavljanja. Za vsakega posameznika iz po- pulacije najprej generiramo novo rešitev z distribucijo Levy in jo ocenimo s kriterijsko funkcijo. Iz populacije izberemo naključnega posameznika, njegovo vrednost kriterijske funk- cije primerjamo z vrednostjo kriterijske funkcije potencialne nove rešitve in tega zamenjamo z novo rešitvijo v primeru, da je ta boljša. Sledi zamenjava najslabšega posameznika s posameznikom, ki ga dobimo z naključno inicializacijo po- sameznika v primeru, da je naključno generirano število iz intervala [0, 1] < pα. Na koncu vsake iteracije poiščemo in shranimo najboljšo rešitev v populaciji v globalno rešitev, ki je izhod algoritma. Model algoritma s kukavičjim iskanjem je prikazan na sliki 3. Psevdo-kod originalnega algorithma CS prikazuje algoritem 2. Algoritem 2 Algoritem CS 1: inicializacija; −−−−−−−−−−−−−−→ 2: najboljsaV rednost0 ← oceniVseResitve; 3: while pogojUstavljanjaIzpolnjen do 4: for i ← 1, Np do 5: ~ xp ← generirajPoskusnoResitev(~ xt i i ); 6: poskusnaVrednost ← oceniPoskusnoResitev(~ xp); i 7: j ← U(1, N rand p); 8: if poskusnaVrednost > najboljsaVrednosttjrand then 9: ~ xt ← j ~ xp; rand i Slika 3: Model algoritma s kukavičjim iskanjem 10: najboljsaVrednostt ← poskusnaVrednost; jrand 11: end if 12: if U(0, 1) < pα then algoritmom je v tem, da generiramo Np novih rešitev in ne 13: inicializacija(~ xtnajslabsi); izbiramo naključne rešitve za primerjavo z novo rešitvijo, 14: end if ampak primerjamo kar rešitve z istim indeksom. 15: shraniGlobalnoNajboljsoResitev; 16: end for 4.1.2 Hibridizacija z mutacijsko strategijo DE 17: end while Odkrite posameznike modificiramo po vzoru mutacijske stra- tegije DE [8]. Tu gre za neke vrste pristransko naključno 4.1 Modificirano kukavičje iskanje iskanje, kjer razliko naključno izbranih posameznikov pri- Modificirana verzija CS (krajše MoCS) vsebuje dve glavni štejemo rešitvi posameznika, ki ga trenutno zavračamo. Na- izboljšavi. Najprej razširimo algoritem CS z generiranjem ključne posameznike izberemo tako, da generiramo dve polji Np kukavičjih jajc v eni iteraciji, nato uvedemo hibridizacijo permutacij dolžine Np , nato izračunamo razliko vektorjev z z mutacijsko strategijo DE. istim indeksom in vsakokrat dobimo drugo razliko. Modifi- cirano naključno iskanje izrazimo z naslednjo enačbo: 4.1.1 Razširitev algoritma CS ~ xt+1 = ~ xt , i i + U (0, 1) × H (pα − ε) × ~ xtj − ~ xtk Najprej generiramo Np novih rešitev (kukavičja gnezda) in jih ocenimo s kriterijsko funkcijo. Vrednosti kriterijske funk- kjer sta ~ xtj in ~xtk naključno izbrana posameznika iz popula- cije novih rešitev primerjamo z vrednostmi kriterijske funk- cije, U (0, 1) funkcija, ki vrne naključno realno število z uni- cije rešitev iz trenutne populacije na vsakem indeksu od 1 formno porazdelitvijo iz intervala [0,1], H (pα − ε) je funk- do Np in nove rešitve zamenjamo z rešitvami iz trenutne cija Heaviside, s katero odločimo, ali zavržemo ali obdržimo populacije v primeru, da so te boljše. Razlika z osnovnim novega posameznika, katere rezultat je 0, če je pα − ε < 0 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 18 in 1, če je pα − ε ≥ 0, pα je parameter zamenjave, ε na- ključno število iz uniformne distribucije iz intervala [0,1] in Tabela 1: Izbrani najboljši parametri ~ xt Ime slike MoDE MoCS i je izbrani vektor iz populacije. Np Nt Np Nt Mandril 50 20 50 80 5. REZULTATI Lena 50 20 50 20 Testiranje algoritmov smo izvedli v dveh korakih. V prvem Viaduct 50 80 50 40 koraku smo poiskali najboljše parametre velikosti popula- cije in števila trikotnikov med izbranimi vrednostmi za sti- skanje vsake izmed izbranih slik pri 105 vrednotenjih. Ko Pri vsakem zagonu smo kombinirali vse možne kombinacije smo najboljše parametre našli, smo stiskanje s temi para- parametrov velikosti populacije in števila trikotnikov, s či- metri ponovili, le da smo v drugem koraku povečali število mer smo izvedli 20 neodvisnih zagonov algoritma za eno vrednotenj na 107 in tako dobili najboljše rezultate z izbra- sliko. Za vsako sliko smo postopek ponovili desetkrat, tj. nimi vrednostmi. Rezultate stiskanja slik predstavljamo v 200 neodvisnih zagonov. Ker imamo dva algoritma in tri nadaljevanju. slike, se je skupaj izvedlo kar 1200 neodvisnih zagonov algo- ritma. 5.1 Izbira slik in iskanje parametrov Najprej smo določili tri referenčne, originalne slike, ki smo Vsak algoritem krmilimo z nadzornimi parametri. Pri DE jih stiskali z našima algoritmoma. Zaradi zahtevnosti kri- smo izbrali začetne vrednosti za F = 0, 5 in Cr = 0, 9. Sama terijske funkcije smo vsako od slik pomanjšali na resolucijo nastavitev teh parametrov ne igra posebne vloge, saj ima naš 100x100. Raznolikost referenčnih slik, prikazanih na sliki 4, algoritem vključeno samo-prilagajanje teh parametrov. Ne- smo dosegli z izbiro dveh barvnih in ene sivinske slike. koliko drugače je pri CS, saj moramo nastaviti parameter zamenjave pα, ki je fiksen skozi celoten algoritem in smo ga v našem primeru nastavili na 0,25. Kot najboljše nastavljive parametre (tabela 1) smo izbrali tiste, ki so imeli največjo povprečno vrednost kriterijske funkcije in ne morebitne po- samezne najboljše rešitve z največjo vrednostjo kriterijske funkcije. Rezultati prvega dela testiranja, ko smo iskali najboljše pa- rametre za algoritma, so pokazali dobre rezultate, ki jih lahko še izboljšamo s povečanjem števila vrednotenj krite- rijske funkcije. Slika 5 prikazuje, kako uspešna sta bili naša algoritma pri stiskanju slik pri iskanju najboljših nastavlji- vih parametrih do 105 vrednotenj kriterijske funkcije. Slika 4: Izbrane slike za stiskanje. Izbira optimalnih parametrov algoritmov je zelo pomembna, saj ti vplivajo na pravilno delovanje algoritma, s tem pa na kakovost končnih slik in hitrost konvergence. Prav zaradi po- membnosti parametrov algoritmov smo najprej poiskali naj- boljše parametre vsakemu od algoritmov za stiskanje vsake slike posebej pri maksimalno 105 vrednotenjih kriterijske funkcije. Poudariti moramo, da smo kot ustavitveni pogoj Slika 5: Podobnost rezultatov algoritmov MoDE in v algoritmih vedno uporabili število vrednotenj kriterijske MoCS za stiskanje slik pri 105 vrednotenjih. funkcije, s čimer smo zagotovili poštenost meritev in rezul- tatov. Naslednja dva parametra sta bila še velikost popula- Iz slike 5 lahko razberemo, da so rezultati MoDE nekoliko cije, ki smo jo izbirali iz množice Np = {50, 100, 150, 200} , in boljši v primerjavi z MoCS za vsako sliko pri 105 vredno- število trikotnikov, uporabljenih pri stiskanju slik. Te smo tenjih. Za sliko Mandril je MoDE dosegel za 3,09 % večjo izbirali s pomočjo porazdelitve eksponentne funkcije: podobnost originalni sliki v primerjavi z MoCS, za sliko Lena 2,25 % in za sliko Viaduct 4,20 %. stT rikotnikov = 20 × 2x, za x = {0, 1, 2, 3, 4} , kjer smo dobili naslednja dopustna števila trikotnikov: Slika 6 prikazuje originalne in najboljše stisnjene slike iz pr- vega koraka testiranja z algoritmoma MoDE in MoCS. Iz stT rikotnikov = {20, 40, 80, 160, 320} . slik je razvidno, da v tej fazi testiranja stiskanja slik pri 105 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 19 Tabela 2: Rezultati podobnosti stisnjene slike in čas stiskanja z 107 vrednotenji. Ime slike MoDE MoCS Podobnost Čas stiskanja Podobnost Čas stiskanja Mandril 90,08 % 4h 41m 11s 89,70 % 8h 12m 45s Lena 91,92 % 4h 48m 35s 90,31 % 5h 43m 38s Viaduct 92,08 % 5h 51m 31s 90,56 % 6h 26m 24s vrednotenjih MoCS ne dosega tako dobrih rezultatov kot MoDE. Slika 7: Primerjava originalnih slik s stisnjenimi sli- kami z algoritmoma MoDE in MoCS z 107 vredno- tenji kriterijske funkcije. zaenkrat še niso primerni za naš problem stiskanja slik, saj ne dajejo rezultatov, ki bi bili sprejemljivi v praksi. Pričaku- jemo lahko, da bosta omenjena algoritma na podlagi doda- tnih izboljšav postala primerna tudi za te namene. Trenutno je stiskanje s temi algoritmi primerno za znanstvene namene in poskuse, ker lahko pokažemo, da so ti algoritmi po vzorih iz narave splošno namenski. Slika 6: Primerjava originalnih slik s stisnjenimi sli- kami z algoritmoma MoDE in MoCS z 105 vredno- Rezultati stisnjenih slik so po oceni naše kriterijske funk- tenji kriterijske funkcije. cije glede podobnosti z originalno sliko zelo dobri. Dosegajo podobnost do dobrih 92 %, kar se zdi zelo obetavno. Ko pogledamo stisnjene slike, pa lahko opazimo, da so na sli- 5.2 Stiskanje slik z 107 vrednotenji kriterijske kah vidni le robovi slike in da so barve poligonov, ki jih ti robovi omejujejo, podobne istemu področju originalne slike. funkcije Iz samih stisnjenih slik lahko brez težav razberemo, kateri Po izvedbi testiranja, s katerim smo dobili najboljše nastavi- originalni sliki pripada, same objekte pa je že težje prepo- tve parametrov, smo te uporabili pri časovno zahtevnejšem znati. testiranju stiskanja slik. Število vrednotenj kriterijske funk- cije smo povečali iz 105 na 107 in ustrezno nastavili najboljše parametre velikosti populacije Np in število trikotnikov NT , 6.1 Možnosti za izboljšave, nadgradnje kot jih prikazuje tabela 1. Obstaja več možnosti, s katerimi bi lahko uspešnost naših algoritmov še dodatno izboljšali. V naslednjih nekaj odstav- Rezultati, prikazani v tabeli 2, so bili veliko boljši kot pri kih predstavljamo samo nekatere izmed njih. stiskanju z 105 vrednotenji. Algoritem MoDE je tudi pri tem številu vrednotenj boljše stisnil vsako izmed slik, kot je Lotili bi se lahko pred-procesiranja slik, kjer slike razdelimo to storil algoritem MoCS. na več pod-slik in vsako od njih obdelamo neodvisno z algo- ritmom stiskanja. Glede na to, da smo pri sivinskih slikah Iz slike 7 je jasno razvidno, da je razvit algoritem MoDE dobili zelo dobre rezultate, bi lahko bila naslednja izboljšava boljši algoritem za stiskanje slik kot razvit algoritem MoCS. po vzoru sivinskih slik. Tukaj sliko razdelimo na tri barvne V stisnjenih slikah z algoritmom MoDE so jasno vidne linije ravnine RGB, vsako od njih obdelamo posebej in na koncu objektov in njihove barve. Pri stisnjenih slikah z algoritmom združimo rezultate nazaj v barvno sliko. MoCS so te linije nekoliko zabrisane in v primerjavi z MoDE so nekateri objekti združeni v enega samega. Algoritmi po vzorih iz narave se nenehno izpopolnjujejo in izboljšujejo s strani različnih raziskovalcev. Prav gotovo ob- 6. ZAKLJUčEK stajajo še kakšne izboljšave uporabljenih algoritmov v našem Razvili smo dva algoritma za stiskanje slik po vzorih iz na- delu, ki bi jih lahko prilagodili za naš problem stiskanja slik rave. Podrobno smo opisali nekatere od možnih izboljšav in tako izpopolnili uspešnost uporabljenih algoritmov. Ena algoritma DE in CS, ki pomagajo pri konvergenci algoritma. od izboljšav pri obeh algoritmih bi bila uporabiti dodatne Rezultati izboljšanih algoritmov dokazujejo, da ti algoritmi mehanizme za izogibanje lokalnemu optimumu. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 20 Velik problem pri stiskanju slik z algoritmi po vzorih iz narave je njihova časovna zahtevnost. Kot smo prikazali v članku, je ugotavljanje dobrih parametrov, testiranje in sti- skanje potekalo več dni. Če ne bi bili časovno omejeni, bi bilo zanimivo narediti več zagonov algoritmov nad skupino naj- boljših parametrov in bi tako lahko dobili drugačne, boljše parametre za stiskanje slik. Algoritem bi lahko nadgradili tako, da bi lahko slike stiskali v drugem barvnem modelu, kot sta recimo HSV ali CMYK. 7. REFERENCES [1] C. Blum and D. Merkle. Swarm Intelligence. Springer-Verlag, Berlin, 2008. [2] J. Brest, S. Greiner, B. Bošković, M. Mernik, and V. Žumer. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems. T. Evolut. Comput., 10(6):646–657, 2006. [3] C. Darwin. On the Origin of Species. Harvard University Press, London, 1964. [4] A. Eiben and J. Smith. Introduction to Evolutionary Computing. Springer-Verlag, Berlin, 2003. [5] I. Fister, M. Mernik, and J. Brest. Hybridization of Evolutionary Algorithms, Evolutionary Algorithms. InTech, 2011. [6] 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, Berlin, 2015. Springer-Verlag. [7] A. Izadi, V. Ciesielski, and M. Berry. Evolutionary non photo-realistic animations with triangular brushstrokes. In AI 2010: Advances in artificial intelligence, pages 283–292, Berlin, 2011. Springer-Verlag. [8] U. Mlakar, I. F. Jr., and I. Fister. Hybrid self-adaptive cuckoo search for global optimization. Swarm and Evolutionary Computation, pages –, 2016. [9] S. Sivanandam and S. Deepa. Introduction to genetic algorithms. Springer-Verlag, Heidelberg, 2008. [10] R. Storn and K. Price. Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim., 11(4):341–359, 1997. [11] X.-S. Yang and S. Deb. Cuckoo search via levy flights. In World Congress & Biologically Inspired Computing (NaBIC 2009), pages 210–214, IEEE Publication, 2009. [12] A. Zalzala and P. Fleming. Genetic algorithms in engineering systems. The institution of electrical engineers, London, UK, 1997. [13] A. Zamuda and U. Mlakar. Differential evolution control parameters study for self-adaptive triangular brushstrokes. Informatica, 39(2):105–113, 2015. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 21 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 22 A GPGPU Implementation of CMA-ES Aleksandar Tošić Matjaž Šuber Faculty of Mathematics, Natural Sciences and Faculty of Mathematics, Natural Sciences and Information Technologies Information Technologies University of Primorska University of Primorska aleksandar.tosic@upr.si matjaz.suber@student.upr.si ABSTRACT ES (Covariance Matrix Adaptation Evolution Strategy) is In the last decade, a lot of hope has been put into Gen- an evolutionary algorithm for non-linear or non-convex con- eral Purpose computing on Graphical Processing Units with tinuous optimization problems. It is considered as state-of- optimization algorithms being among the most researched the-art in evolutionary computation and has been adopted [10, 6, 12, 13]. Unfortunately, the shift in programming as one of the standard tools for continuous optimization. It paradigms and computation models makes implementation is based on the principle of biological evolution, where in of existing algorithms non-trivial. Some algorithms are sim- each iteration new candidate solutions are generated. ply not suitable for implementation on a single Instruction Multiple Data (SIMD) model. To overcome the tedious- Choosing the framework was relatively straight forward. Most ness of programming GPU’s a number of frameworks be- frameworks are not mature enough or proprietary, hence came available with Compute Unified Device Architecture we chose openCl. OpenCL (Open Computing Language) is (CUDA) [9] being the most popular proprietary and Open the first truly open and royalty-free programming standard Computing Language (OpenCL) [8] leading in the field of for general-purpose computations on heterogeneous systems. open-source frameworks. With the help of OpenCL we im- It allows programmers to preserve their expensive source plemented the Covariance Matrix Adaptation Evolution Strat- code investment and easily target multi-core CPUs, GPUs, egy (CMA-ES) [4] in a Metaheuristic Algorithms in Java and the new APUs. It improves the speed and responsive- (jMetal) framework [1, 2]. We tested both CPU and OpenCL ness of a wide spectrum of applications. OpenCL is defined implementations on different hardware configurations and with four models, namely Platform model, Execution model, problem sets available in jMetal. Additionally we explain Memory model, and Programming model [3]. The most im-the details of our implementation and show a comparison of portant beeing the execution model that deals with the load- computation results. ing and executing kernels on the GPU and Memory model, handling the allocation of GPU memory and the transfer of Keywords data between host memory and GPU memory. Covariance Matrix Adaptation Evolution Strategy(CMA), The main challenge is to adapt the kernels and memory Numerical Optimisation, Evolutionary Algorithm, GPGPU, models depending on the hardware specifications namely, jMetal, OpenCL work-group sizes, compute units, etc. In this paper present empirical results comparing the standard algorithm with 1. INTRODUCTION our GPGPU implementation. Additionally, we show results Computation on graphics processing units has received a lot comparing two platforms from different hardware manufac- of attention in the past. Mainly because of the availability turers to eliminate the potential bias of openCl implemen- of hardware that was driven mostly by the gaming industry tation. [7]. As more complex rendering engines were developed, the need to harness the GPU capabilities grew. Manufacturers gave more access and control over their hardware trough 2. IMPLEMENTATION frameworks. The main loop in the CMA-ES algorithm consists of three main parts and it runs until termination criterion is met. In this paper we present an implementation of a popular In the first part the algorithm samples new population of evolutionary inspired algorithm called CMA-ES. The CMA- solutions, for k = 1, ..., λ, in the second part it reorders the sampled solutions based on the fitness function and finally it updates the covariance matrix as described in [5]. The execution model defines how the OpenCL environment is configured on the host and how kernels are executed on the device. Before a host can request that a kernel is executed on a device, a context must be configured on the host that coordinates the host-device interaction and keeps track of the kernels that are created for each device. Each kernel contain a unit of code (function) which is executed on a StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 23 specific compute unit. This units are then grouped into one, All this actions are implemented in the init() method. two or three dimensional set, which are called work-groups. After the initialization process has finished the main loop of For the implementation we obtained the source code of the the algorith is executed as shown in algorithm 2. In each iterative CMA-ES algorithm from the jMetal Java based iteration of the main loop the SamplePopulation method framework for multi-objective optimization [1]. To speed-executes the OpenCL kernels with the OpenCL command up the algorithm we integrated OpenCL into the execution clEnqueueN DRangeKernel. When the SamplePopulation process. In the first part the algorithm selects the OpenCL method has finished the OpenCL device holds the current device with the largest number of compute units in addiction best solution found according to the fitness function which to the work group size. is implemented in the computeF itnessKernel. After that it initializes the OpenCL context with the OpenCL In the last phase of the main loop the algorithm executes clCreateContext command. The OpenCL context is re- all the kernels in the UpdateDistribution method, which up- quired for managing OpenCL objects such as command- dates the covariance matrix as described in [5]. When the queues, memory, program and kernel objects and for execut-number of evaluations is bigger than the predefined maxi- ing kernels on one or more devices specified in the context. It mum evaluation number, the host machine reads the best so- continues with creating the OpenCL command-queue with lution from the device memory, with the OpenCL command the command clCreateCommandQueue. clEnqueueReadBuf f er and outputs the result as shown in algorithm 2. The main loop of the CMA-ES algorithm is divided into kernels which are enqueued to the command-queue with the Algorithm 2 CMA-ES (OpenCL version) OpenCL clEnqueueN DRangeKernel command. This ker- 1: procedure execute() nels are than executed on the device. When the termina- 2: ... tion criterion is met, the host machine reads the best solu- 3: // Host: initialize variables tion from the device memory with the OpenCL command 4: // Host: initializes kernels and input arguments clEnqueueReadBuf f er and outputs the result. 5: // Host: send data to OpenCL device 6: init() Algorithm 1 CMA-ES (Sequential version) 7: ... 1: procedure execute() 8: // Host: main loop 2: ... 9: while counteval < maxEvaluations do 3: // initialize variables 10: // Host: execute kernels to sample population 4: init() 11: samplePopulation(); 5: ... 12: // Host: update counteval 6: while counteval < maxEvaluations do 13: counteval += (populationSize*populationSize); 7: // get a new population of solutions 14: // Host: execute kernels to update the covariance 8: population = samplePopulation() matrix 9: for i ∈ 0...populationSize do 15: updateDistribution(); 10: // evaluate solution 16: ... 11: evaluateSolution(population.get(i)); 17: // Host: read the best solution from the device 12: // update counteval 18: clEnqueueReadBuffer(...); 13: counteval += populationSize; 19: ... 14: // returns the best solution using a Comparator 20: // Host: store the best solution 15: storeBest(comparator); 21: resultPopulation.add(bestSolutionEver); 16: // update the covariance matrix 22: ... 17: updateDistribution(); 23: // Host: return the best solution 18: ... 24: return resultPopulation; 19: // store the best solution 20: resultPopulation.add(bestSolutionEver); 3. RESULTS 21: ... The tests were performed on two main hardware configu- 22: // return the best solution rations. Besides testing the performance improvement of 23: return resultPopulation; our GPU implementation, we tested the differences between Nvidia and ATI graphic cards. The first machine was equipped The analysis of the iterative CMA-ES algorithm has shown with an i7-3820 CPU clocked at 3.60 GHz coupled with a that the most time expensive steps are in the SamplePopu- GeForce GTX 650. The second configuration was an AMD lation method, in the inner for loop and in the UpdateDistri- FX-6300 clocked at 3500 MHz with a AMD Radeon R9 bution method. To speed-up the algorithm we implemented 280X. The details of both cards are shown in Table 1 eight OpenCL kernels, which encapsulate the logic of those methods. In order to execute this kernels on the device, The jMetal framework offers plentiful problems to test opti- the implementation firstly initializes these kernels and their mization algorithms. We have chosen four typical problems, input arguments with the OpenCL clSetKernelArg com- namely Rosenbrock, Sphere, Griewank, and Rastrigin. Each mand. After that it sends all the precomputed data from problem was tested on each hardware configuration and with the host to the device with the clCreateBuf f er command. different sample sizes. We measured the running time of the StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 24 Property GeForce GTX 650 AMD Radeon R9 280X Shading Units 384 2048 10 7 Nvidia GeForce 650gtx Memmory 1024 MB 3072 MB Intel i7-3820 10 6 GPU Clock 1058 MHz 850 MHz Memory Clock 1250 MHz 1500 MHz 10 5 Table 1: GPU hardware comparison 10 4 10 3 algorithm for each run and computed averages for each sam- Runtime in miliseconds 10 2 ple size. The results for tests ran on GeForce GTX 650 are shown in Table 2 10 1 Sample size Griewank Sphere Rosenbrock Rastrigin 10 0 10 6ms 6ms 6ms 7ms 0 1000 2000 3000 4000 5000 Problem Size 100 9ms 9ms 9ms 9ms 500 79ms 73ms 73ms 72ms 1000 226ms 232ms 231ms 225ms 2500 1274ms 1272ms 1278ms 1271ms Figure 1: Runtime comparison on logarithmic scale 5000 5260ms 5273ms 5270ms 5275ms Sample size Griewank Sphere Rosenbrock Rastrigin 10 31ms 26ms 28ms 25ms Table 2: Run times on Nvidia GeForce 650gtx 100 32ms 31ms 37ms 30ms 500 86ms 85ms 92ms 94ms 1000 219ms 216ms 232ms 221ms To illustrate the performance improvement we ran the same 2500 1090ms 1092ms 1102ms 1085ms tests on the Intel i7-3820 CPU. The results are shown in 5000 4119ms 4125ms 4140ms 4134ms Table 3 Sample size Griewank Sphere Rosenbrock Rastrigin Table 4: Run times on ATI Radeon R9-280x 10 11ms 11ms 11ms 12ms 100 108ms 112ms 110ms 113ms 500 856ms 881ms 879ms 886ms From Table 5 we can observe the performance of the CPU 1000 5428ms 5533ms 5588ms 5610ms implementation on the AMD CPU. Compared with the Intel 2500 123.39s 121.57s 153.94s 127.89s CPU we can clearly see that the AMD CPU is much slower, 5000 1208.84s 1184.37s 1188.17s 1265.53s which in turn explains the bottleneck in bandwidth between the GPU. The performance improvement of the GPU over Table 3: Run times on Intel i7-3820 CPU CPU on the AMD configuration is shown in Figure 2 plotted in logarithmic scale. Comparing Tables 2 and 3 we can observe the improvements Sample size Griewank Sphere Rosenbrock Rastrigin of the GPU implementation over the CPU. On larger prob- 10 17ms 17ms 17ms 17ms lems, the GPU implementation outperforms the CPU by a 100 152ms 130ms 140ms 139ms factor of 230. On smaller tests however, the improvements 500 1864ms 1824ms 1803ms 1871ms are not substantial. This was expected due to the fact the 1000 24128ms 24028ms 24106ms 24191ms kernels and the data need to be loaded from RAM to VRAM. 2500 232.52s 229.29s 223.91 234.76s In smaller problems the latency gives expression, while in the 5000 3416.5s 3446s 3431.2s 3445.2s case of larger problems it does not impact overall computa- tion time as much. The performance increase can also be observed in Figure 1 which was plotted in logarithmic scale. Table 5: Run times on AMD FX-6300 We perform the same tests on the second configuration using an AMD-FX-6300 and an ATI Radeon R9-280x GPU shown 4. CONCLUSION in Tables 4 The results on the ATI GPU are a bit surprising. Using an open source meta-heuristic algorithm framework The graphic card is generally one of the fastest currently we implemented a GPGPU version of CMA-ES algorithm on the market, yet, it seems the Nvidia outperformed it using openCL, which is also open source. We empirically on smaller problems. After profiling the execution using compared the computational results between the CPU and Jprofiler [11] we noticed the bottleneck was the AMD CPU, GPU version, which show improvement of the GPU over the which took much longer to load the kernels and data on to CPU version. Additionally we compared two different con- the GPU. On larger problems, where the actual computation figurations in an attempt to eliminate the possible bias of the takes longer, the slow bandwidth between CPU and GPU is framework towards certain manufacturers. Even though the not noticeable. configurations were not in the same price range and hence StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 25 The next step is to run the tests on hardware configurations 7 10 of the same price point. Additionally we are working on ATI Radeon r9 280x AMD FX-6300 upstreaming our implementation to the Jmetal framework. 6 10 7. REFERENCES [1] J. Durillo, A. Nebro, and E. Alba. The jmetal 5 10 framework for multi-objective optimization: Design and architecture. In CEC 2010, pages 4138–4325, Barcelona, Spain, July 2010. 4 10 [2] J. J. Durillo and A. J. Nebro. jmetal: A java framework for multi-objective optimization. Advances 3 10 in Engineering Software, 42:760–771, 2011. Runtime in miliseconds [3] B. Gaster, L. Howes, D. R. Kaeli, P. Mistry, and D. Schaa. Heterogeneous Computing with OpenCL. 2 10 2012. [4] N. Hansen. The cma evolution strategy: a comparing 1 10 review. In Towards a new evolutionary computation, 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 Problem Size pages 75–102. Springer, 2006. [5] N. Hansen. The CMA evolution strategy: A tutorial. Vu le, 102(2006):1–34, 2011. [6] M. Harris. Gpgpu: General-purpose computation on Figure 2: Runtime comparison on logarithmic scale gpus. SIGGRAPH 2005 GPGPU COURSE, 2005. [7] M. Macedonia. The gpu enters computing’s mainstream. Computer, 36(10):106–108, 2003. not directly comparable we show that the speedups obtained were in a reasonable margin. In best case our implementa- [8] A. Munshi. The opencl specification. In 2009 IEEE tion is over 800 times faster then the CPU implementation. Hot Chips 21 Symposium (HCS), pages 1–314. IEEE, We did not notice any improvement in case of smaller prob- 2009. lems mainly due the time penalty of transferring problem [9] C. Nvidia. Programming guide, 2008. data from RAM to vRAM. [10] M. Pharr and R. Fernando. Gpu gems 2: programming techniques for high-performance graphics and 5. ACKNOWLEDGMENT general-purpose computation. Addison-Wesley The authors would like to thank dr. Peter Korošec for ad- Professional, 2005. vising and guiding the research. [11] J. Shirazi. Tool report: Jprofiler. Java Performance Tuning, 2002. 6. FUTURE WORK [12] S. Tsutsui and P. Collet. Massively parallel The hardware used to perform tests was not directly com- evolutionary computation on GPGPUs. Springer, 2013. parable. The Intel configuration had a much better CPU [13] W. H. Wen-Mei. GPU Computing Gems Emerald while the AMD configuration had a state of the art GPU. Edition. Elsevier, 2011. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 26 Building visual domain-specific languages using the semiotic approach: A case study on EasyTime Iztok Fister Jr. Iztok Fister Faculty of Electrical Engineering and Computer Faculty of Electrical Engineering and Computer Science, University of Maribor Science, University of Maribor Smetanova 17, 2000 Maribor, Slovenia Smetanova 17, 2000 Maribor, Slovenia iztok.fister1@um.si iztok.fister@um.si ABSTRACT sults of competitors faster, more efficiently, and more accu- This paper presents the development and usage of the Easy- rately. In order to simplify working with the measuring sys- Time III Visual Domain-Specific Language (VDSL) for mea- tem for tracking the results, the EasyTime domain-specific suring time during sports competitions that enables users language was proposed for the Double Triathlon in 2009 [7]. to create the VDSL programs visually. Indeed, this new This version, based on a specific compiler/generator, was hybrid VDSL creating approach deals with semiotics‘ anal- developed for compiling an EasyTime source code into an ysis in place of building a meta-model. Thus, each visual abstract machine code. Modifying and widening the Easy- element, like an icon, is handled as a sign with its repre- Time domain-specific language demanded interventions di- sentation (form and shape), reference (object) and mean- rectly into the compiler/generator. Therefore, an improved ing (implementation of object). Each visual element is then version of EasyTime was proposed in [8, 11, 10, 9], where mapped into DSL language construct as defined by object EasyTime was defined formally as (domain analysis, ab- implementation. In general, this approach is suitable, when stract syntax, concrete syntax, formal semantics, and code Domain-Specific Language (DSL) using a Textual User In- generation), whilst a LISA [18] was used for building as a terface (TUI) is already implemented within a certain appli-suitable compiler/generator. In this paper, we move for- cation domain and, therefore, the developer can be focused ward in order to improve user experience and, thus, propose mainly on designing a Graphical User Interface (GUI). In EasyTime III Visual Domain-Specific modelling Language this study, the existing EasyTime DSL has been upgraded (VDSL). This explores the visual interface to simplify the to EasyTime III VDSL using the hybrid VDSL creation ap- programming tasks of the measuring system. This VDSL proach. Experiments of measuring time in an aquathlon addresses the shortcomings of its predecessor, i.e., simplify- have shown that the programming in EasyTime III is sim- ing its development. The users’ visual programming consists ple and efficient, whilst all other features of EasyTime DSL of constructing the user model. This model is then trans- are preserved within the new VDSL. lated into EasyTime DSL constructs. Indeed, a semiotics theory [12] is applied. Semiotics is the study of signs [2], Keywords where each sign consists of representation, object, and mean- ing. The meanings of the signs are defined explicitly in the domain-specific language, EasyTime, semiotics user model [5]. Thus, a meta-model step can be avoided by the traditional creation of DSMLs. This approach is, there-1. INTRODUCTION fore, also named as a hybrid VDSL creation. The VDSL was Until recently, measuring time during sports competitions tested on building the EasyTime III program for measuring was performed manually by timekeepers using time obtained time during the aquathlon competition. The obtained re- from stopwatches assigned to specific competitors accord- sults showed the power of the created visual tool that brings ing to their starting numbers. The rapid expansion of Ra- a great user experience on the one hand and simplified cre- dio Frequency IDentification (RFID) [6] technology has led ating the visual programs. into the development of various measuring devices. How- ever, measuring devices represent only one part of the story, The structure of the paper is as follows. Section 2 deals with because measuring times during sports competitions can- a description of the proposed EasyTime III VDSL. In Sec- not be achieved without a measuring system. This system tion 3, created VDSL was applied for building the EasyTime collates timed-events from different measuring devices into III VDSL program in measuring time during an aquathlon a central database that enables organisers to track the re- competition. The paper concludes with Section 4, which summarizes the performed work and outlines the possible directions for the future. 2. EASYTIME III VISUAL DSL The design of visual languages is a very complex process that, besides a knowledge of computer science, demands also the knowledge of areas like Psychology, Sociology, Anthro- pology, Linguistics, Design, and Engineering. For the devel- opment of EasyTime III VDSL, the following phases need StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 27 to be carried out: is based on logic and epistemology [2]. He defined the sign as anything that stands for something else, to somebody, in some respect or capacity. Nothing is a sign until it is in- • Concept analysis, terpreted by somebody. Peirce described signs as threefold • Visualization of features, structures consisting of: Representation, reference (object), and meaning (interpretation) (Figure 2). Two characteris- • Semiotic analysis, tics of these structures are valid: Firstly, a direct connection between a representation and reference need not necessarily • Code generation. exist. Secondly, a meaning is always a mediator between a representation and reference. That is, the sign does not ex- In the remainder of the paper all the mentioned phases are ist until some interpretation of representation is taken that described in detail. has some meaning for somebody. In other words, a sign re- quires the concurrent presence of all three characteristics. A concept analysis identifies the concepts and relations be- On the other hand, there can be many meanings to a sign. tween concepts. The analysis of a measuring time domain In our study, the Peircean structure of signs was taken into summarizes the results as proposed in [8] because VDSL EasyTime III addresses the same application-domain (i.e., measuring time) as the original EasyTime DSL. The concept analysis divides the concepts into features, and then these features into sub-features. However, the features and sub- features may be mandatory or optional. In order to denote the attitudes between concepts, features and sub-features, the concept analysis defines the following relations: • all : All features or sub-features are mandatory. • more-off : The feature may be either one of the sub- features from a set of sub-features or any combination of sub-features from the same set. • one-off : The feature may be one of the sub-features Figure 2: Structure of signs. from a set of sub-features but not any combination of sub-features from the same set. account in order to prescribe the unique meanings of them. Indeed, unique translation of signs can be achieved to Easy- Time domain-specific language constructs. In line with this, The concept diagram of the measuring time domain is de- semantic analysis is not needed for this translation. There- picted in Figure 1, from which it can be seen that the concept fore, this process of generating the EasyTime III VDSL was Race consists of seven features (i.e., Events, Transition area, named a hybrid approach, and it can be applied usefully Control points, Measuring time, Begin, End and Agents). when the textual DSL is already developed in this applica- tion domain and an upgrade to the visual interface needs 2.1 Visualization of features to be developed. The semiotics of EasyTime III can be de- During the visualization process, the features are mapped scribed with the structures as illustrated in Table 2, from into appropriate graphical interfaces, as presented in Ta-which it can be seen that each icon is represented by a cor- ble 2.1. The Table is interpreted as follows. Icons Ibegin and responding object. In our study, objects are represented as Iend denote the features Begin and End, respectively. Events C++ classes. The objects’ meanings are defined by the im- can be represented using icons Iswim , Ibike , and Irun and de- plementation code. The source code in EasyTime DSL is scribed the sub-features, as follows: Swimming, Cycling, and generated as a result of the implementation. Running. The feature Transition areas is identified by icon Ita , while Measuring devices are marked using icons Imd0 , For instance, an icon Ibegin is referenced with an object Imd1 , and Imd2 . Begin that is created by a parameter Laps which determines the number of laps. This object is responsible for generat- 2.2 Semiotics‘ analysis ing the EasyTime DSL language construct ”upd STARTx ”. Semiotics is the study of ’everything that can be taken as a Note that this character x denotes the integer value (also sign’ [17]. This is an interdisciplinary theory that comprises location counter, lc) necessary for distinguishing the dif-domains of meanings in a variety of other disciplines like ferent instances of the same variables because, in contrast, Psychology, Anthropology, Biology, Logic, Linguistics, Phi- the same names of the variables will be generated for dif- losophy, and even Software Engineering [4]. Modern semi-ferent control points. The variable lc is initialized during otics consists of two independent theories, as follows: Semi- race configuration. The icons Iswim, Ibike, Irun representing ology and semiotics. The former was developed in Switzer- the events are represented by objects Event (Algorithm 1) land by Ferdinand de Saussure [16], while the latter in North that are responsible for generating two DSL EasyTime lan-America by Charles Sanders Peirce [13]. De Saussure’s the-guage constructs ”dec ROUNDx ” and ”upd INTERx ” (Al- ory of signs originated from the language theory as a system gorithm 2). A class Event consists of three variables (type, of arbitrary signifying units. The Peircean theory of signs laps, lc) and three methods (constructor Event, initialize, StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 28 Race Transition Control Measuring Events Begin End Agents area points time number update decrement swimming cycling running start of laps finish time laps automatic manual Figure 1: Concept diagram of measuring time domain. Table 1: Translation of the application domain features to graphical elements. Application domain features Graphical elements Begin race Ibegin Events (Swimming, Cycling, Running) Iswim, Ibike, Irun Transition area Ita End race Iend Measuring time Imd0 , Imd1 , Imd2 Control points (start, number of laps, finish) square dots (control points) Agents (automatic, manual) square dots (measuring points) Algorithm 1 Definition of object ’Event’ Note that the other objects are represented and implemented 1: class Event { in a similar manner. 2: int type; // type of events Swim, Run, Bike 3: int laps; // number of laps 4: int lc; // index of generated variables 2.3 Code generation 5: Code generation is divided into: 6: Event(int Type, int Laps, int Lc); 7: void initialize(); 8: void generate(); 9: } • the source code generation, • the object code generation. generate). The variable type determines the type of event, i.e., Swim, Run, Bike, variable laps the number of laps that In the first phase, a visual representation of a real race the competitor needs to accomplish a specific discipline, and using the graphical elements (also user model) is mapped variable lc determines the instance of a specific variable. The into the EasyTime DSL source code while, in the second variable laps is a context information which is obtained by phase, this source code is compiled into object code using the user. The method Event constructs the object with ap- the LISA [18] compiler/generator. Semantic domains need propriate parameters, method initialize generates the spe-to be defined for translating the graphical elements into the cific EasyTime DSL code necessary to initialize the variables EasyTime DSL source code. In EasyTime III, two semantic within the scope, and the method generate generates the domains are defined (Table 3). Both domains are used for specific EasyTime DSL code appropriate for this event. A a proper calling of the objects represented in the Table 4 in detailed implementation of the mentioned methods can be the translation phase. The former (i.e., DEvent ) defines sub- seen in Algorithm 2. features of the feature Event, while the latter (i.e., DEvent ) sub-features of the feature Md. All the other parameters of Algorithm 2 Implementation of object ’Event’ the corresponding objects are of integer type. In the sec- 1: Event::Event(int Type, int Laps, int Lc) 2: type = Type; laps = Laps; 3: lc = Lc; Table 3: Semantic domains in EasyTime III. 4: } DEvent = {Swim, Bike, Run} Event Type ∈ DEvent 5: void Event::initialize() { DMd = {Md0 , Md1 , Md2 } Md Type ∈ DMd 6: gen(op init, var round, lc, laps); 7: gen(op init, var inter, lc, 0); 8: } 9: void Event::generate() { ond phase, the EasyTime DSL source code translated from 10: gen(op dec, var round, lc); the corresponding user visual model is generated into virtual 11: gen(op upd, var inter, lc); machine object code. The readers can obtain more informa- 12: } tion about this process in [8]. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 29 Table 2: Translation of the application domain concepts to semiotic signs. Icons Objects Meanings Ibegin Begin(Laps, Lc) ”(ROUNDx == %Laps) → upd STARTx ;” Iswim , Ibike , Irun Event(Event Type, Laps, Lc) ”dec ROUNDx ;” ”upd INTERx ;” Ita End(Lc) ”(ROUNDx == 0) → upd FINISHx ;” Begin(Laps, Lc) ”(ROUNDx == %Laps) → upd STARTx ; ” Iend End(Lc) ”(ROUNDx == 0) → upd FINISHx ;” Imd0 , Imd1 , Imd2 Md(Md Type, Mp, Ag, [Ip|Fn]) ”mp[%Mp] ← agnt[%Ag] {” | ”}” 3. MEASURING TIME IN AN AQUATHLON whilst the lower fields are where measuring devices have to COMPETITION USING EASYTIME III be situated. Each icon also includes a square dot that en- ables the control point to be connected with the measuring VDSL point. Moreover, the transition area icon, similar to the Aquathlon is a relatively young sport, the first National measuring device with two mats, includes two square dots. Competition being held in the USA in 1965. It belongs to a Connection has to be made by dragging the source control class of multi-sports, where the race consists of continuous point and dropping it into the destination measuring point two-stage disciplines involving swimming followed by run- or vice versa. Furthermore, the EasyTime III visual editor ning [14, 15]. Between both disciplines, however, a so-called also includes certain context dependent information, like the transition area exists, where the competitors who finish the number of laps, IP address of the measuring device, or an swimming prepare themselves for running. The time spent input file name. Zero laps on the swimming icon means in the transition area is added to the final result of each that the swimming will not be measured on this measuring specific competitor. Aquathlons are similar to triathlons. device. This information can be obtained by pressing the Triathlons, however, have cycling in addition to swimming right-hand mouse button. The measuring time during an and running. As a result, an aquathlon covers triathlon dis- aquathlon competition is configured as follows. The upper tances as well. For instance, a 1 km swim is followed by a 5 graphical editor field determines the race configuration (i.e., km run, etc. Distances vary depending upon the race venue start of race, swimming, transition area, running and fin- and race organisers. For building the EasyTime III visual ish of race), whilst the lower graphical editor field denotes programs, an EasyTime III visual editor was developed us- situated measuring devices (i.e., realised by a measuring de- ing the Qt [1, 3], where a lot of bindings with other languages vice with two measuring points). The connections between also exist, e.g., Java, Python, Ruby, etc. The visual program the control points and measuring points determine where the in an EasyTime III visual editor for measuring time during particular event has to be measured. For instance, the finish an aquathlon competition is illustrated in Figure 3. The vi-time of swimming has to be measured at measuring point sual editor is the graphical editor for describing the race to 1 (antenna mat 1), whilst the other three running events be measured. It consists of a graphical editor area, where (start time, intermediate times, and finish time) have to be the race should be described and a control area consisting measured at measuring point 2 (antenna mat 2). of the buttons necessary for editing. In fact, the buttons represent either the application domain features or miscel- 3.1 Source code generation for measuring time laneous controls devoted to managing the visual programs. These buttons are divided into three subsets representing: in an aquathlon competition Source code generation starts with translating the user vi- sual model (consisting of icons and links) into semiotics ob- • the race configuration, i.e., buttons for dragging the jects. Indeed, an area of central points CP and area of icons representing the control points (e.g., Ibegin, Iend, measuring points MP together with an adjacent matrix rep- Iswim, Ibike, Irun, Ita ) and dropping them into specific resenting connections between control and measuring points positions within the visual editor area, are generated. The results of this translation are illustrated in Table 4. It can be seen from the Table that the control • situated measuring devices, i.e., buttons for dragging points‘ area CP consists of six semiotics objects represent- the icons representing the measuring points (e.g., Imd1, ing two disciplines (e.g., swimming and running) embraced Imd2, Imd0) and dropping them into specific positions between Begin and End semiotics objects. The generated within the visual editor area, names of the variables in these semiotics objects are distin- • controls, namely the buttons necessary for opening, guished according to their location counter. For instance, all saving and erasing the visual programs, and generating variables referring to the first discipline are generated with the object code from the visual program. lc = 1, whilst the variables referring to the second disci- pline with lc = 2. There are two measuring points within an area MP, and four links where the time should be mea- Note that the graphical editor area consists of two fields sured. Note that the adjacent matrix LN designates the in which icons are placed sequentially. The upper is sen- connections between the control and measuring points. The sitive to the buttons designated control points, whilst the program presented in the Algorithm 3 is generated according lower to the buttons described measuring points. In fact, the to the race configuration. This generation is straightforward upper fields of icons determine the configuration of a race, when someone follows the code generation as defined by the StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 30 Race configuration BEGIN END SWIM RACE RACE START STOP RUN BIKE TA Measuring devices AUTO-1 AUTO-2 MANUAL Controls START 0 LAPS TA 10 LAPS STOP COPY SAVE AS... ERASE OPEN SAVE GENERATE 192.168.225.2 Figure 3: Visual program for measuring time in an aquathlon competition. Table 4: Result of algorithm ’config race’. CP = { Begin(0,1),Event (Swim, 0, 1),End (1),Begin(0,2),Event (Run, 10, 2),End (2) } MP = { Md (Auto-2,1,1,”192.168.225.2”), Md (Auto-2,2,1,”192.168.225.2”) } LN = { (3,1),(4,2),(5,2),(6,2) } Algorithm 3 Source code for measuring time during on so-called semiotics objects, the source code is then gener- aquathlon. ated, which can be translated into object code using the 1: 1 auto 192.168.225.2; existing compiler/generator. The proposed approach was 2: tested by the development of EasyTime III VDSL for mea- 3: START1 = 0; suring time during sports competitions and starting with 4: ROUND1 = 0; the concepts of an application domain obtained through do- 5: INTER1 = 0; 6: FINISH1 = 0; main analysis. These concepts serve as the basis for build- 7: START2 = 0; ing EasyTime III graphical user interfaces on the Qt based 8: ROUND2 = 10; visual editor. The visual program (also user model) built 9: INTER2 = 0; using this editor is then mapped into EasyTime DSL con- 10: FINISH2 = 0; structs. The result of this translation is the EasyTime DSL 11: source program. Translating this source program using the 12: mp1[1] → agnt[1] { 13: (ROUND1 == 0) → upd FINISH1; LISA compiler/generator generates an object AM code for 14: } the EasyTime measuring system. As a result, the developed 15: mp1[2] → agnt[1] { EasyTime III VDSL enables ordinary users (e.g., organis- 16: (ROUND2 == 10) → upd START2; ers of sports competitions) to create programs for measuring 17: (true) → upd INTER2; time application-domain visually. That is, instead of writing 18: (true) → dec ROUND2; the program in text editor, only ’point-and-click’ is needed 19: (ROUND2 == 0) → upd FINISH2; 20: } with the icons on the screen. With the proposed EasyTime III, the programming of a measuring system within visual environments is easier, faster, and more effective. meanings of the semiotics objects. Note that this code is functionally equivalent to the code written by the domain 5. REFERENCES expert manually. Later, EasyTime LISA compiler/generator [1] J. Blanchette and M. Summerfield. C++ GUI is used for object code generation [8]. programming with Qt 4. Prentice Hall PTR, 2006. [2] D. Chandler. Semiotics: The Basics. Routledge, New 4. CONCLUSION York, US, 2007. This paper proposes a new hybrid VDSL creation approach [3] M. Dalheimer. Programming with QT: Writing that is suitable when the DSL already exists in certain appli- portable GUI applications on Unix and Win32. cation-domain. In this manner, a programmer exploits exist- O’Reilly Media, Incorporated, 2002. ing DSL and focuses on designing a graphical user interface. [4] C. de Souza. The semiotic engineering of Thus, he/she avoids constructing the meta-model and, in human-computer interaction. MIT Press, Cambridge, line with this, the usage of the complex development frame- England, 2005. works, like Eclipse. The modelling step is, here, substituted [5] C. de Souza. Semiotic perspectives on interactive with semiotic analysis, where each visual element, like icon languages for life on the screen. Journal of Visual or link, is handled as a sign with its representation (object) Languages & Computing, 24(3):218 – 221, 2013. and meaning (implementation of the object). From these [6] K. Finkenzeller. RFID handbook: fundamentals and StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 31 applications in contactless smart cards, radio frequency identification and near-field communication. Wiley, 2010. [7] I. Fister Jr. and I. Fister. Measuring time in sporting competitions with the domain-specific language Easytime. Electrotechnical review, 78(1–2):36–41, 2011. [8] I. Fister Jr., I. Fister, M. Mernik, and J. Brest. Design and implementation of domain-specific language Easytime. Computer Languages, Systems & Structures, 37(4):151–167, 2011. [9] I. Fister Jr, T. Kosar, I. Fister, and M. Mernik. Easytime++: A case study of incremental domain-specific language development. Information Technology And Control, 42(1):77–85, 2013. [10] I. Fister Jr., M. Mernik, I. Fister, and D. Hrnčič. Implementation of Easytime formal semantics using a LISA compiler generator. Computer Science and Information Systems, 9(3):1019–1044, 2012. [11] I. Fister Jr., M. Mernik, I. Fister, and D. Hrnčič. Implementation of the domain-specific language Easytime using a LISA compiler generator. In Computer Science and Information Systems (FedCSIS), 2011 Federated Conference on, pages 801–808. IEEE, 2011. [12] C. Peirce. Collected papers of charles sanders peirce. volume 1–8, Cambridge, MA, 1931–1958. Harward University Press. [13] C. Peirce and V. Welby. Semiotic and significs: the correspondence between Charles S. Peirce and Lady Victoria Welby. UMI-books on demand. Indiana University Press, 1977. [14] S. Petschnig. 10 Jahre IRONMAN Triathlon Austria. Meyer & Meyer Verlag, 2007. [15] S. Rauter and M. Doupona Topič. Perspectives of the sport-oriented public in slovenia on extreme sports. Kinesiology, 43(1):82–90, 2011. [16] F. Saussure. Course in General Linguistics. Duckworth, 1976. [17] E. Umberto. A theory of semiotics. Advances in semiotics. Indiana University Press, 1976. [18] University of Maribor. Lisa 2.2. http://labraj.uni-mb.si/lisa/, 2013. Accessed 17 August 2016. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 32 A new population-based nature-inspired algorithm every month: Is the current era coming to the end? Iztok Fister Jr., Uroš Mlakar, Janez Brest, Iztok Fister Faculty of Electrical Engineering and Computer Science, University of Maribor Smetanova 17, 2000 Maribor, Slovenia iztok.fister1@um.si ABSTRACT and software. Thus, people were unable to test and de- Every month at least one new population-based nature-insp- velop their methods widely. However, some years after the ired algorithm has been released in literature. Until recently, creation of artificial neural networks, another discipline (or there were probably more than 200 algorithms of this kind alternative to artificial neural networks) was developed ac- in books, papers and proceedings. Many researchers dis- tively by the scientific community. The name of this dis- cuss that this research area is becoming flooded with new cipline, that was coined later, was Evolutionary compu- algorithms that are in fact the old algorithms in a new dis- tation. Evolutionary computation was based on the natu- guise. Potentially, such behavior could be leading into the ral evolution of species and respected the theory of Charles emergence of pseudoscience. In this paper, we try to find Darwin. Initially, the Evolutionary Algorithms (EAs) sim- some answers to the questions what lead authors to pro- ulated the operators of mutation and crossover, where the pose and develop the new nature-inspired algorithms and individuals to survive were selected according to their fit- what their benefits in doing so are. We propose ways in ness values. The fitness value was determined according to which to stop the emergence of new algorithms. In line with the evaluation of the fitness function that corresponded to this, we have found that proposing the new population-based the problem to be solved. Nevertheless, over the years the nature-inspired algorithms is actually similar to the swarm EAs were divided into the following kind of algorithms: Ge- intelligence behavior in nature, where the role of population netic algorithms [18], evolution strategies [1], genetic pro- members is acted by authors of the new algorithm with the gramming [16] and evolutionary programming [26]. The goal to publish a paper, thus promoting its algorithm and main differences between these sub-families were basically spreading it all over the world. in the representation of individuals, e.g., binary represen- tation was used by genetic algorithms, floating point repre- Keywords sentation by evolution strategies, finite state automata by evolutionary programming and programs in Lisp by genetic metaphors, nature-inspired algorithms, swarm intelligence programming. Additionally, it is important to mention that in the 80s other metaheuristics were also designed [23, 8, 9, 1. INTRODUCTION 10, 15]. The period when these methods appeared in the Approximately 50 years ago, the time emerged when scien- literature was a little bit calmer compared with nowadays. tists began applying algorithms solving the problems on dig- It was a time without the Internet and also access to the ital computers by mimicking the human brain widely. These papers was limited. Additionally, in these times people did methods were called Artificial neural networks [13]. Ar- not yet know the term Publish or perish [19, 2]. Scien- tificial neural networks were proposed in the 40s in the pre- tists should not have to be forced to publish for any price vious century, but it took some time before the community in order to their hold position at the university or scientific began to use them widely for scientific and first practical institute. But things were changed quickly. The years of 90s usage. These networks were really interesting methods and came rapidly. In this scientific area a new paradigm was pro- many scientists claimed that artificial neural networks would posed that incorporated the social behavior of many agents power the world in the near future. Artificial neural net- that guided them into complex behavior. The roots of this works were counted into pure artificial intelligence and now method, which is named Swarm intelligence, can be found there are many various types of these networks for solving in the dissertation of Marco Dorigo [4]. His method proposed particular tasks in theory and practice. That historical time the colonies of ants for solving discrete optimization prob- was also the time where people were limited with hardware lems. A little bit later, in 1995, Kennedy and Eberhart [14] applied the behavior of bird swarms and fish schools into an algorithm with the name Particle swarm optimiza- tion. These two methods were the beginners of the new community movement, i.e. the so-called swarm intelligence community. However, in the 90s and early 2000s the com- munity did not think that these two powerful algorithms were the stepping stones for the development of uncount- able nature-inspired algorithms and, potentially, the flood of algorithms that led into pseudoscience. In this paper, we StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 33 try to get answers to the following questions: 3.1 Current publishing era Without doubt we can say that this era, after the year 2000, • What is actually considered as a new nature-inspired led to the hard race between scientists and even institu- algorithm? tions. People that work in universities and institutes are forced to publish works that will achieve a lot of citations, • What motivates researchers to propose new algorithms? since good works with many citations help universities in global rankings. Better universities have attracted more, • What they have if they propose a new algorithm? better students. In line with this, they could obtain the • What is a generic recipe for proposing a new algo- government and industrial projects more easily. Projects rithm? mean money, while more students mean more tuition fees. Fortunately, this is not true for each country. For exam- • What are the implications of new algorithms? ple, there are no tuition fees for students of Government • How to stop the invasion of new algorithms? Institutions in Slovenia. Only, doctoral studies require stu- dents to pay a tuition fee that is actually not as high as it is • Is proposing new algorithms basically swarm intelli- abroad. In order to meet these goals universities could make gence behavior itself? pressure on researchers to publish more and better works. This manner is also connected with the term Publish or Insights on these questions will be highlighted in the remain- perish. However, to satisfy these goals is a little bit easier der of the paper. for mature and well-known researchers, while newbies have mostly enormous problems. For example, some students in 2. NATURE-INSPIRED ALGORITHMS China are even prepared to give a kidney for having a paper At the start, it is very hard to define exactly what the accepted in a journal with impact factor. Is not publish- population-based nature-inspired algorithms actually are. How- ing becoming similar to any fight sport (win at any price)? ever, there are many definitions and most of these definitions Let us leave politics and go back to our population-based say that population-based nature-inspired algorithms are a nature-inspired algorithms. So, after the year 2000 when kind of algorithms that are inspired by natural, biological Ant colonies and Particle Swarms became popular, inter- and even social systems, and are intended to solve problems esting and widely used algorithms, some researchers began in a similar way to what nature does. Even today, there thinking whether there was a possibility to develop or just are a few taxonomies that try to deal algorithms in different propose a new algorithm that should be based on any other groups. One of the taxonomies is a taxonomy published in inspiration from nature. If we look into our bioshpere, we 2013 by Fister et al. [5] where algorithms were split into 4 can easily find a lot of animal species, different trees, natural groups [5]: processes, social behaviors for developing the optimization algorithms. When researchers found an inspiration, they then needed to coin some operators that mimic the behavior • Swarm intelligence based algorithms, of their inspiration and, later, put this magic into the univer- • Bio-inspired that are not swarm intelligence based, sal recipe that was presented in the previous chapter. Most of the algorithms only used a different formula for moving • Physics and chemistry based and individuals and that was all the magic behind an algorithm. • Other algorithms. Paradigm was the same, but only some minor changes were incorporated in the developing of the brand new population- based nature-inspired algorithm. After developing, the time Algorithm 1 Generic pseudo-code of most of the has started for publishing the new algorithm. Usually, all re- population-based nature-inspired algorithms searchers need to validate their new algorithms on some well- 1: initialize individuals within bounds using a particular known benchmark functions or on some engineering prob- randomization generator lems. Of course, all algorithms have beaten other well- 2: evaluate all individuals known algorithms without any problem, although nobody 3: while termination criteria not met do cared if researchers used special benchmarks and tested on 4: move all individuals according to proposed formulas special dimensions and compared with basic well-known al- 5: evaluate all individuals gorithms and not with their improved versions. At the be- 6: find the best individuals ginning, they were successful and achieved good publications 7: end while in journals with nice impact factors and even at good con- 8: return the best individual and vizualize ferences. Until 2010, almost nobody had yet cared about new algorithms but, after 2010, many scientists began to Generic pseudo-code for most of the algorithms in this tax- doubt about the originality of works. However, it was too onomy, especially for the first and second group, is presented late. Nowadays, we are in 2016. According to the list in Algorithm 1. on Github (www.github.com/fcampelo/EC-Bestiary), we counted (as of 5 August 2016) that there are 101 nature- 3. THE NEW POPULATION-BASED inspired algorithms (Fig. 1). Anyway, there are many others NATURE-INSPIRED ALGORITHMS that are not on this list. The previous section gave readers a short overview of the population-based nature-inspired algorithms, while this sec- tion will be concentrated on the implications of the new population-based nature-inspired algorithms. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 34 Algorithm 2 Generic recipe for the new nature-inspired algorithm proposal 1: Watch TV, browse internet, go for a walk in nature in order to get inspiration for your new algorithm 2: while searching in progress do 3: if you get an idea about a new algorithm: 4: check if your proposed name is still free (browse via major search engines and databasess) 5: if name is free: 6: develop formulas 7: choose benchmark functions 8: run experiments 9: write and publish a paper 10: spread the word about your algorithm 11: else repeat until you find another inspiration bait for younger researchers, especially students. Students do not have a global view on a particular research area and, Figure 1: The emergence of new algorithms (accord- thus, they simply succumb to new algorithms. Many papers ing to Github repository EC-Bestiary.) that propose new algorithms are written in tempting style and it really attracts students. Moreover, even various re- searchers from other totally different research areas (geology, 4. MOTIVATION FOR THE DEVELOPMENT space exploration, leisure studies, etc.) sometimes use new OF THE NEW POPULATION-BASED algorithms for research. They do not care about roots, they NATURE-INSPIRED ALGORITHMS just want to solve their problems (no matter what method solves the problem). At the end, industry is the last thing In order to find what is actually the motivation behind the here. People from industry need a solution for their prob- development of a new algorithm, we should take a more lem. If they see that one algorithm is good for their problem global view. As many papers have already shown [21, 22, they take it. 25, 24], that the new algorithms are actually old algorithms in new disguises (similar as Spy character in Team Fortress 2 game) we should discover why researchers created a new 7. HOW TO STOP THE INVASION OF THE algorithm artificially and masked it within the new inspi- POPULATION-BASED NATURE-INSPIRED ration. We believe that motivation is connected with pub- ALGORITHMS? lishing and citations. This research area is really wide and offers excellent opportunities for publication. Along with We believe that the invasion of the new population-based this statement, publication also opens a pool for citations. nature-inspired algorithms could be stopped within the next Thus, one of the main motivations behind new algorithms five years. All trends in evolution are the same. At the be- is more or less the current publishing situation. ginning there is a high rise, when it comes to the top then it goes down slowly. At the moment the trend is not rising any more and many Editors and Reviewers are informed about 5. GENERIC RECIPE FOR PROPOSING this problem. Recently, many papers that show the prob- THE NEW POPULATION-BASED lems of this area have been released [22, 7, 6, 21, 5]. Some NATURE-INSPIRED ALGORITHM Journal Editorial Boards have even revised their rules and After studying some of the new population-based nature- they do not accept papers where questionable metaphors are inspired algorithms, we can simply propose a generic recipe presented [11]. By the same token, the Matthew effect [20, that captures all the ingredients of the successful creation 17] that depicts ”the rich tend to be richer” almost always of a new nature-inspired algorithm. The generic recipe is works. Hence, old and famous algorithms will always be presented in Algorithm 2. At the beginning, researchers are more powerful than artificially created algorithms. looking for an idea. While searching is in progress, when they get an idea, they need to reconcile the name of the new 7.1 Swarm intelligence behavior in the algorithm. If the name is still free, then the researchers need population-based nature-inspired algorithm to develop formulas, choose test functions, run experiments development and publish a paper. At the end, they also need to spread the word about the algorithm. This could be done easily by The definition of the swarm intelligence based algorithms various social networks. were outlined in the previous sections. The swarm intelli- gence based algorithms family are, these days, more popular and there are also many journals that are devoted to these 6. IMPLICATIONS OF THE NEW NATURE- kinds of algorithms. As a matter of fact, swarm intelligence INSPIRED ALGORITHMS based algorithms propose many individuals that execute Mostly, the new population-based nature-inspired algorithms simple actions and their behavioral actions leads into do not affect older researchers (however, there are some ex- a complex and decentralized system. Can we find any ceptions), while new algorithms of this kind are excellent parallel points with the process of new nature-inspired al- StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 35 Table 1: Parallel points between the definition of swarm intelligence and the process of creation of new nature-inspired algorithms. Definition of swarm intelligence New nature-inspired algorithm cre- ation many individuals many authors simple actions watching the inspiration in nature, giving a new name for the algo- rithm, developing a formula behavioral actions publishing a paper complex name motivates other individuals, new hybrid and adaptive variants decentralized algorithm is spread all over the world, impossible to stop spreading this algorithm – the same as viruses for example gorithm creation? The Table 1 shows point to point com- the research community will help drastically in preventing parison among these two processes. What is the most in- the emergence of new population-based nature-inspired al- teresting is that the process of new algorithm creation pos- gorithms on new proposal attempts and make this research sesses the behavior of swarm intelligence. Swarm intelli- area clean again. Finally, the evolution of everything has gence based algorithms consist of many individuals. On the not been finished in one night, but it took a lot of time. other hand, the process of population-based nature-inspired Eventually, it could also be the same for population-based algorithms is guided by many authors. Simple actions (for nature-inspired algorithms. example foraging in bees or pheromone tracking in ants or even home building by termites) are, in the process of new 9. REFERENCES algorithm creation, defined as simple actions where authors [1] H.-G. Beyer and H.-P. Schwefel. Evolution try to find an inspiration in nature, give their algorithm a strategies–a comprehensive introduction. Natural bombastic name and even develop a formula that will mostly computing, 1(1):3–52, 2002. guide an evolutionary process. Behavioral actions are, ba- [2] P. Clapham. Publish or perish. BioScience, sically, connected with publishing a paper in a journal or 55(5):390–391, 2005. at a conference, while complex behavior is connected with spreading the algorithm all over the world with the help [3] T. D. Cosco. Medical journals, impact and social of social media [12, 3] (Twitter, Facebook, Researchgate, media: an ecological study of the twittersphere. Academia, Google groups, etc.), search engines (Google, Ya- Canadian Medical Association Journal, hoo), emails (many authors send emails to others attached 187(18):1353–1357, 2015. with the source code and pdfs), mouth sharing (via confer- [4] M. Dorigo and T. Stützle. Ant colony optimization: ences and social meetings) and so on. Decentralized behav- overview and recent advances. Techreport, IRIDIA, ior is expressed as an algorithm that is spread all over the Universite Libre de Bruxelles, 2009. world and it is also impossible to stop it spreading. Espe- [5] I. Fister Jr., X.-S. Yang, I. Fister, J. Brest, and cially, new researchers take a new algorithm and create new D. Fister. A brief review of nature-inspired algorithms variants (mostly hybrid variants or apply this algorithm on for optimization. Elektrotehniški vestnik, industrial problems) and then, again, we obtain complex be- 80(3):116–122, 2013. havior. [6] S. Fong, X. Wang, Q. Xu, R. Wong, J. Fiaidhi, and S. Mohammed. Recent advances in metaheuristic 8. CONCLUSION algorithms: Does the makara dragon exist? The Journal of Supercomputing, pages 1–23, 2015. In this paper we took a view on the new population-based [7] S. Fong, R. Wong, and P. Pichappan. Debunking the nature-inspired algorithms‘ development. The new population- designs of contemporary nature-inspired computing based nature-inspired algorithms are released every month algorithms: from moving particles to roaming and, basically, they have nothing special and no novel fea- elephants. In 2015 Fourth International Conference on tures for science. Thus, the development of the new population- Future Generation Communication Technology based nature-inspired algorithms may be becoming very dan- (FGCT), pages 1–11. IEEE, 2015. gerous for science. We found that there are many social ten- sions that lead authors towards the new population-based [8] F. Glover. Future paths for integer programming and nature-inspired algorithm creation, especially the wish for links to artificial intelligence. Computers & operations quick paper publishing and citations on published papers. research, 13(5):533–549, 1986. Additionally, our research revealed that the process of the [9] F. Glover. Tabu search–part i. ORSA Journal on new population-based nature-inspired algorithm possesses computing, 1(3):190–206, 1989. the behavior of the swarm intelligence paradigm. Thus, it [10] F. Glover. Tabu search–part ii. ORSA Journal on would not be easy to stop the invasions of the new population- computing, 2(1):4–32, 1990. based nature-inspired algorithms in the near future (only [11] F. Glover and K. Sörensen. Metaheuristics. a systematic approach can help). However, awareness of Scholarpedia, 10(4), 2015. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 36 [12] N. Hall. The kardashian index: a measure of discrepant social media profile for scientists. Genome Biology, 15(7):1–3, 2014. [13] A. K. Jain, J. Mao, and K. M. Mohiuddin. Artificial neural networks: A tutorial. IEEE computer, 29(3):31–44, 1996. [14] J. Kennedy and R. Eberhart. Particle swarm optimization. In Neural Networks, 1995. Proceedings., IEEE International Conference on, volume 4, pages 1942–1948. IEEE, 1995. [15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simmulated annealing. Science, 220(4598):671–680, 1983. [16] J. R. Koza. Genetic programming: on the programming of computers by means of natural selection, volume 1. MIT press, 1992. [17] R. K. Merton et al. The matthew effect in science. Science, 159(3810):56–63, 1968. [18] M. Mitchell. An introduction to genetic algorithms. MIT press, 1998. [19] G. Parchomovsky. Publish or perish. Michigan Law Review, 98(4):926–952, 2000. [20] M. Perc. The matthew effect in empirical data. Journal of The Royal Society Interface, 11(98):20140378, 2014. [21] A. P. Piotrowski, J. J. Napiorkowski, and P. M. Rowinski. How novel is the ”novel” black hole optimization approach? Information Sciences, 267:191–200, 2014. [22] K. Sörensen. Metaheuristics–the metaphor exposed. International Transactions in Operational Research, 22(1):3–18, 2015. [23] K. Sörensen, M. Sevaux, and F. Glover. A history of metaheuristics. In ORBEL29–29th Belgian conference on Operations Research, 2015. [24] D. Weyland. A rigorous analysis of the harmony search algorithm: how the research community can be misled by a ”novel” methodology. International Journal of Applied Metaheuristic Computing, 1(2):50–60, 2010. [25] D. Weyland. A critical analysis of the harmony search algorithm–how not to solve sudoku. Operations Research Perspectives, 2:97–105, 2015. [26] X. Yao, Y. Liu, and G. Lin. Evolutionary programming made faster. IEEE Transactions on Evolutionary computation, 3(2):82–102, 1999. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 37 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 38 Visualization of cycling training Dušan Fister Iztok Jr. Fister Iztok Fister Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru Fakulteta za strojništvo Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, Smetanova 17, 2000 Maribor računalništvo in informatiko računalništvo in informatiko dusan.fister@student.um.si Smetanova 17, 2000 Maribor Smetanova 17, 2000 Maribor iztok.fister1@um.si iztok.fister@um.si ABSTRACT consumption), analysing daily weight and measuring aver- In the era of big data, a flood of information obtained from age sleep quality by measuring movement of the arm [5]. pervasive computing devices is being available. Using lat- est data mining technologies, lots of information can also All those properties, which became accessible to every ath- be processed. Since many of them do not present any sig- lete, lead to huge and complex online trackers, offering lots nificant meaning to users, information could be ranged in of data. But these data should be correctly interpreted in so-called significant classes, where these are selected accord- order to became useful information for an athlete. In line ing to their significance. This paper presents an analysis of with this, different applications for visualization in sports data obtained during the cycling training sessions made by have been emerged. For instance, the more frequently used wearable sports tracker and later visualization of their most visualization tasks are described in [7], but these are espe- significant parameters. Every sports training activity should cially suited for the team sports. The analysis of the cycling be presented in a simple, self-speaking and understandable data is well described in [3], while the advanced data-mining figure, from which it is possible to deduce difficulty, strain, approach in [6]. The cycling training sessions and its plan- effort, power, conditions and pace of the visualized sports ning can be seen in [4]. training session. This paper proposes visualization of cycling elements, where Keywords athlete’s data obtained from an archive of the activity data- sets are interpreted. Based on athlete’s effort, specific figures visualization, cycling, cycling elements, .TCX are built, from which it is possible to obtain the most signif- icant class information about the performed sports training 1. INTRODUCTION activity. A use of GPS sports trackers (trackers) for sports train- ing purposes in cycling is increased every day. More and The organization of the paper is as follows. In second chap- more athletes use trackers to measure, accompany and con- ter, basic elements of cycling training are described in de- trol data obtained during their trainings, as well as perform tails. Third chapter offers background and description of later analysis and online planning. Trackers are today em- proposed visualization, while the fourth chapter deals with bedded into sports-watches (e.g. Garmin Connect, Strava, results. The paper ends with conclusions and outlines the Movescount, Endomondo, Sports tracker, etc.) or mobile directions for future work. devices offering an upload of datasets with tracked data to the mentioned sports tracker producer websites. Every cy- 2. ELEMENTS OF CYCLING TRAINING clist collects his activity datasets in a so called calendar, AND VISUALIZATION BACKGROUND showing daily training sessions. In this paper, we are focused on visualization of cycling training datasets. Cycling datasets are, as mentioned in Sport-watches and mobile devices provide a brand-new ap- Chapter 1, created during a sports training session. Cycling proach of training, not only for cycling, but also for running, trackers usually record properties from the most significant swimming, canoeing, hiking, roller skating, skiing, fitness, class consisting of: and other sports. Some of the specialized trackers support additional functions, like summing the number of daily steps and predicting calories burnt (therefore measuring the daily • position, • distance, • duration, • velocity, • altitude, • temperature, • heart rate and StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 39 • power. Distance Duration Weather First six properties are recorded by tracker itself when wear- 200 km ing or carrying during the activity, while least two are pro- 5 h 15 min vided by wearing accessories. Heart rate monitor and power Velocity meter crank are today’s classic equipment for cyclists and are usually being used during the training. Data is com- monly recorded every second into special .GPX or .TCX 38 km/h 204 W dataset. This means that many useful information (e.g., Altitude different graphs, coefficients, average values, fatigue predic- tion, feeling and performance evaluation) can be extracted Power from the activity datasets when interpolating data through time. Tracker analysers usually compete against each other 3400 m 162 bpm good to provide most data for athletes. Therefore, more and more information are accessible when updating the tracker (ex- Heart rate Feeling tracting data is still in research). Figure 1: Visualization elements of the prototype. The results of analyser are forwarded to visualizer, whose main task is to interpret them. For specific athlete, data should be treated specifically, i.e., no generalization is de- sired. For correct interpreting, cyclist needs to collaborate of the cycling elements, as well as with an objective value. with visualizer’s personal dataset in order to properly range The curve representing the distance currently in bright red data for each athlete. One of the tasks of visualizer is teach- means that athlete almost reached the wished daily norm. ing himself in the matter of improving athlete’s performance. The number below means total distance cycled and serves Therefore, regular updates of personal dataset are crucial be- as supporting value of visualization. Speed meter represents fore the visualization. Correctly updated visualizer should velocity and is divided into three sections, presenting relax- then correctly predict cyclist’s efforts, no matter of age, ex- ation ride, tempo ride and competition ride. A deterministic periences or personal habits. Following values are specified value is added as well in order to prevent the misconception in personal dataset: of reading the velocity meter slope. The same applies to du- ration, altitude, heart rate and power meter element. Colors are automatically chosen and adjusted to athlete’s perfor- • daily norm of duration, mance. They vary between bright yellow, as low-effort, and • daily norm of distance, dark red, as high-effort (Fig. 3). • daily norm of altitude, Fig. 2 presents the flow of events and data graphically. Start- ing by cycling, process continues to uploading and analysing • minimum and maximum velocity of an athlete, of recorded data. Transformations from real to computer • minimum and maximum hearth rate and world are clearly seen as well as visualizing section with ap- propriate displaying results to cyclist. • Functional Threshold Power (FTP). First three properties depend on the athlete’s desire to what he wants to reach, while last three show his objective perfor- mance. FTP setting of power is a property, which describes display results athlete’s ability to produce the specific amount of power in Computer world one hour. upload Athlete activity Tracker’s WebSite For visualization figure, it is common to show athlete’s daily Real world feeling. Therefore, the cyclist should enter into personal dataset his/her feeling, or condition, on the day of train- ing. Thus, three different feeling badges can be selected, i.e., Analyzer good, bad and medium. Additionally, weather data can be downloaded from weather websites and added to visualiza- tion figure. In order to commence research and implemen- tation of automatic visualizer, the prototype was manually Visualizer schemed in the picture drawing studio (Fig. 1). Fig. 1 presents the prototype of visualization designed in Weather Personal figure editing studio that serves as a basis for automatic vi- report data file sualization. It is worth to mention that cycling parameters shown in prototype are untrue and biased, but purpose can be clearly seen from it. Figure should be read by the color Figure 2: Visualization process. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 40 As can be seen from Fig. 2, the visualization process is di- After obtaining result INTERPRET DISTANCE , which lies vided into three parts: in the interval [0,1] a color for the distance curve is selected. Ten colors are available for ranging the intensity of cycling elements. If the result of distance is INTERPRET DISTANCE = • completing the training session, 0.45, then the corresponding color in interval [0.4, 0.5] will be selected, i.e., bright orange as can be seen from Fig. 3. • uploading and processing data, as well as visualizing results, • informing cyclist. The first part is dedicated to the cyclist in real world. Af- ter completing his training, recorded data is transmitted to computer world in the second part. There, they are be- ing processed, visualized and displayed on the website as a result. In third part cyclist can inform himself about the training’s effort and therefore struggle even more next time. 3. CYCLING TRAINING ELEMENTS VISU- ALIZATION The visualization process is performed using a software suite ImageMagick and Ruby programming language [2]. Im- ageMagick is the open source text-mode editing software for pictures, which excellently collaborates with the Ruby language. This combination of software was applied in our Figure 3: Color table. study because of high adaptability, simplicity and integra- tion. Algorithm 1 presents the basic visualization process. Interpretation of altitude and duration is performed on the very similar way, while interpretation of heart rate and power Algorithm 1 Visualization principle is a bit more sophisticated. It should be mentioned, that it 1: Athlete uploads cycling activity dataset to tracker’s web- would be silly to interpret, for instance heart rate HR = site; 56 bpm on the training, because this can mean that cyclist 2: Analysis of uploaded dataset begins; did not actually move. To prevent appearance of such errors, 3: Analyser forwards extracted data to visualizer; we suggest to add besides the set of maximum values also the 4: Visualizer reads data and retrieves personal dataset; set of minimum values. Consequently, actual data should be 5: if Personal dataset should be updated then spread between minimum and maximum values, e.g. heart 6: Update personal dataset; rate should be drawn from interval HR ∈ [120, 180] bpm. 7: end if Accordingly, Eq. (1) transforms into Eq. (2): 8: Visualizer downloads actual weather report; 9: Visualizer interprets data to become information; 10: Visualizer generates a figure and forwards it to website; actual power − min power 11: Website presents the visualized figure of the training INTERPRET POWER = , (2) max power − min power activity session; where INTERPRET POWER ∈ [0, 1]. If the actual power Algorithm 1 presents the standard visualization process, tak- is lower than min power, the min power is taken into ac- ing into account both of the accessories (i.e., heart rate mon- count and actual power is disregarded. itor and power-meter) by default. It should be noted, that the visualization process is adjusted, when cyclist does not As a result, listed elements are colored in the appropriate use any of them and visualization figure is different than color and finally added (imported) into the primary figure. shown one (Fig. 1). 3.2 Visualization of velocity 3.1 Visualization of distance, altitude, dura- As seen in prototypical Fig. 1, velocity, weather and feeling tion, heart rate and power are not presented by color, as other elements. Therefore, a Let’s say, that analysis part has been completed and ex- different approach was studied for those elements. One of tracted data are ready to be interpreted. Interpretation ac- the most self-explaining principles of presenting velocity in tually means comparing extracted data from tracker and general is using a simple indicator with three background arc values obtained from personal dataset. An example shows colors. In fact, reading the slope of the indicator is the easi- the comparison for the distance element: est way to determine velocity and that is the reason for em- ploying it in our application. Background arc colors can be actual distance INTERPRET DISTANCE = , (1) pre-drawn and pre-imported into file to make whole process max distance easier, but indicator has to be programmed and processed where INTERPRET DISTANCE ∈ [0, 1]. at the moment of visualization, indeed. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 41 The scheme of velocity indicator consists of three mutu- report is parsed. To get proper weather report from web- ally connected points. Connections create so-called polygon, site it is also necessary to locate closest weather station to which has to be properly positioned and rotated to express activity position, what is still under research. wanted velocity. Position can be fixed, due to fixed color arc in primary figure, but rotation is a matter of two read Meanwhile, weather condition figures are drawn in advance, values, written in personal dataset - expected minimum and so only compositing of them to the right place is necessary to maximum value. Those extend the velocity range, e.g. 25 expose the weather conditions. If sunny weather is reported, km/h as the lowest velocity and 45 km/h as the highest ve- only sun is exposed and opposingly, cloudy weather is seen locity. As stated, those conditionals call for the automatized from figure, if clouds are described in METAR (Fig. 5): calculation of indicator’s tip position. In Ruby, program- ming of indicator and its movement was executed by simple mathematical equation, consisting of trigonometrical func- tions. First, the slope in degrees is calculated using following equation: SLOP E = Figure 5: Weather conditions. min velocity + max velocity actual velocity − · 9◦, 2 Fig. 5 shows basic weather conditions, which serve as the (3) first part in describing weather. Describing the wind, or second part, is more sophisticated. First, the direction and where actual velocity is parsed from .GPX, or .TCX file and magnitude are gathered from weather report. Next, the min velocity and max velocity read from personal dataset. length of the wind flag is initialized. Position of the wind 9◦ is used as section interval, meaning that 1 km/h presents flag tip and its end are calculated to continue the calcula- 9◦ in inaugural form and is updated if updating personal tion process and finally the line between them is outlined. dataset. To certainly specify wind direction, the wind flag’s ending tips are drawn (Fig. 6). The calculus part consists of many After calculating the needed slope, the tip’s position is be- trigonometrical function and is very long, therefore we ex- ing calculated using trigonometrical functions in following cluded it from paper. equations: x position = sin(SLOP E) · 202.5, (4) Wing flag’s tip Wing flag’s end y position = cos(SLOP E) · 202.5, (5) where 202.5 presents the length of the indicator from the center of color arc to the tip end in pixels (Fig. 4). Wing flag’s ending tip Figure 6: Describing wind. Three different magnitudes of wind are applicable in our work: • wind velocity from 0 km/h to 5 km/h: no wind flag, • wind velocity from 5 km/h to 15 km/h: one wind flag, • wind velocity from 15 km/h and above: two wind flags. Figure 4: Velocity indication. Visualizing feeling bases on the athlete’s manual input. Three 3.3 Visualization of weather and feeling different feelings are included in program, which vary from Visualization of weather is divided into two parts. First bad, medium and good (Fig. 7). As standardized, all three part presents the general weather conditions - sunny, rainy, figures are drawn into advance and imported into primary cloudy weather, while the second part deals with the magni- figure on the appropriate position after cyclist’s decision. tude and direction of wind. Data is downloaded and parsed from the aviation weather’s site, called Ogimet [1], which 4. RESULTS offers aviation weather reports, called METAR (Meteorolog- Results of cycling’s automatized visualizing are presented ical Aviation Report). The METAR is a simple, text-based graphically for three different training stages: weather report, from which weather conditions can be de- termined. For us, it is particularly important to be aware of clouds and possible wind blowing, therefore only little of • after-season relaxation, StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 42 Figure 7: Describing feeling. • mileage training and • competition. Result are constructed on a single cyclist, who had fulfiled his personal dataset based on his experiences and uploaded three different .TCX files to website. They have all been analysed and sent to our visualizer. It then generated three figures, which suppose to be shown in the athlete’s calendar of activities. 4.1 After-season relaxation Figure 9: Mileage training. strong yellow section to save his energy for the whole ride. The answer on the question, which asks why did the cyclist reach higher power in after-season relaxation than in mileage training is a bit complex. First, the power shown on the vi- sualization figure is not average, but normalized (NP). NP is a correction of average power, due to rapid changes in train- ing intensity and due to curvilinearly physiological responses [8]. In the first result, athlete probably did some intervals (escalating intensity) during the training to stretch his legs, which are rapid changes in intensity, and therefore improved his NP shown in the figure. Practically, rapid intervals on the training make NP higher. Oppose to first result, at this long ride, athlete did save with his energy and did no short intervals and no intensifying is observed from Fig. 9. 4.3 Competition Competition visualization is as at first seen very relaxational (Fig. 10). Athlete did only little more than twenty kilome- tres, getting the distance curve barely noticed. His ride last for only half an hour, identifying yellow color from duration Figure 8: After-season relaxation. element. But otherwise, athlete had struggled at most by other three results - his average heart rate was 182 bpm, Fig. 8 presents after-season relaxation training session. Cy- normalized power 294 watts and velocity 43.2 km/h. They clist did quite short training, what is seen from distance and are all in the red section, meaning that athlete surely com- duration. Its colors are orange, meaning that athlete only peted at the time trial. He chose flat course, having only did half of his maximum. Cyclist did rode slowly, with low few altitude, therefore getting his velocity very high. His pace, what can be also seen from his pulse. His power was feeling was bad, at strong south-west wind and some clouds, quite good, considering the flat ride (low altitude) and bad meaning that cyclist could drive even faster. feeling. Cyclist probably did a short, regenerative training in order to raise his feeling and performance for next day’s 5. CONCLUSION training, which will probably be much more difficult. In this paper, we presented a novel approach for visualizing most important cycling data. Accordingly, a visualizer in 4.2 Mileage training editing studio ImageMagick was implemented and controlled Mileage training is a long, distant training, seen from dis- by Ruby programming language. We practically executed tance and duration elements on Fig. 9. Cyclist did train our approach and showed, that it is possible to automatically more than 100 km more than in first result. Cyclist did generate expected figures. Results of the performed work much altitude, due to red colored altitude indication. The are, due to rapid visualizing (only five seconds per figure), weather on that way was cloudy, without wind. His feel- excellent. The precision of process is valuable and resolution ing was medium and his heart rate like expected - in the of figures is acceptable. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 43 6. REFERENCES [1] Ogimet METAR. http://www.ogimet.com, 2005. [Accessed: 2016-08-31]. [2] Dan Nguyen. Image manipulation. http://ruby. bastardsbook.com/chapters/image-manipulation/, 2011. [Accessed: 2016-08-25]. [3] I. Fister, D. Fister, and S. Fong. Data mining in sporting activities created by sports trackers. In Computational and Business Intelligence (ISCBI), 2013 International Symposium on, pages 88–91. IEEE, 2013. [4] I. Fister, S. Rauter, X.-S. Yang, and K. Ljubič. Planning the sports training sessions with the bat algorithm. Neurocomputing, 149:993–1002, 2015. [5] Garmin. Sleep tracking. http://www8.garmin.com/ manuals/webhelp/forerunner230/EN-US/ GUID-70D41BFB-2BB2-4933-BF95-47FF63140112.html, 2014. [Accessed: 2016-08-25]. [6] G. Hrovat, I. Fister Jr, K. Yermak, G. Stiglic, and I. Fister. Interestingness measure for mining sequential patterns in sports. Journal of Intelligent & Fuzzy Systems, 29(5):1981–1994, 2015. Figure 10: Competition. [7] M. Page and A. V. Moere. Towards classifying visualization in team sports. In International However, some cues remain for the improving the paper: Conference on Computer Graphics, Imaging and Visualisation (CGIV’06), pages 24–29. IEEE, 2006. • [8] Training Peaks. Normalized power, intensity factor and some graphical weather elements should be added, e.g. training stress score. symbol for rain, snow and fog, http://home.trainingpeaks. com/blog/article/normalized-power, • standardized visualization scheme should be transformed -intensity-factor-training-stress, 2005. into an adjusted one, if athlete does not own a heart [Accessed: 2016-08-31]. rate monitor, or power meter during the training, • the default feeling should be set to good by default and changed only after athlete’s intervention, • drawn symbols, which represent altitude, heart rate, weather symbols, power meter and feeling should be completely created in the ImageMagick studio (cur- rently they are drawn in advance and imported into primary figure), • automatic parse for weather should be implemented, • sports, like running, swimming and roller-blading should be added into visualization with their elements (Fig. 11) and • analyser should be implemented to read data from trackers. Figure 11: Running and roller-blading. The evaluation of cycling data visualization was satisfactory implemented. It is worth to continue research in this way, since it may help to many cyclists. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 44 Izdelava klaviatur MIDI Primož Bencak Dušan Fister Univerza v Mariboru Univerza v Mariboru Fakulteta za strojništvo Fakulteta za strojništvo Smetanova 17, Maribor Smetanova 17, Maribor primoz.bencak@student.um.si dusan.fister@student.um.si POVZETEK izvajalcev [9]. Formalno je bil sprejet leta 1983 in je vse do Glasba obstaja, odkar obstaja človek. Vedno je bila človeku danes v glasbeni industriji ostal najbolj uporabljan stan- prijazna sopotnica ali pa sredstvo za sprostitev, umiritev in dard. Omogoča medsebojno povezljivost različnih vmes- motivacijo. Skladno z glasbo in človekom se razvijajo, odra- nikov MIDI, ne da bi za to potrebovali dodatno strojno ščajo in spreminjajo tudi glasbeni instrumenti, ki ustvarja- opremo. MIDI je zapis informacij o tem, katera nota oz. nju glasbe dajejo poseben pečat. Zadnja leta na razvoj glas- tipka je pritisnjena, na kak način, in s kakšno silo. bene industrije vpliva predvsem elektronska industrija, zato se v tej študiji osredotočamo na izdelavo klaviatur, tj. glas- Ustvarjanje zvoka s pomočjo električne energije je vsekakor bila s tipkami, po glasbenem standardu MIDI (angl. Musical široko področje, ki sega daleč v zgodovino. V tem poglavju Instrument Digital Interface). Predlagane klaviature MIDI navajamo nekaj izvorov razvoja analognih in digitalnih sin- omogočajo povezljivost z računalnikom, zato so zasnovane tetizatorjev. Griffis je 1984 [4] patentiral vezje, ki signale na osnovi mikrokrmilnika podjetja Texas Instruments in mi- zvoka predvaja na stereo zvočnem analognem sintetizatorju. kroračunalnika Raspberry Pi. Slednja na račun vedno večje Elektronski sintetizator je leta 1988 patentiral Japonec Ka- integracije družno omogočata procesorsko moč osebnega ra- neoka [6], medtem ko je McDonald šest let kasneje predlagal čunalnika in neposredno povezljivost s strojno opremo. uporabo zvočnega sintetizatorja v vozilih [7]. Razvoj digi- talnega sintetizatorja sega že v leto 1990, ko je Gilmore pa- Ključne besede tentiral, t.i. direktni digitalni sintetizator [3]. Leta 1999 je Cook predlagal, t.i. orodje za sintezo zvoka (angl. Synthe- Mikrokrmilnik, mikroračunalnik, MIDI standard, klaviature, sis toolkit) in razložil pomen standarda MIDI za ustvarjanje sinteza zvoka zvoka [2]. Princip analognega in digitalnega sintetizatorja je omogočil razvoj številnih izpeljank sintetizatorjev, od kate- 1. UVOD rih je vredno podrobneje omeniti vzorčevalne, saj smo slednji Glasbo je mogoče ustvarjati na mnogo načinov. Do osemde- princip uporabili tudi mi. Pregled vseh izpeljank je zapisan setih let prejšnjega stoletja so bili posamezni sklopi zvokov v [8]. omejeni na določen glasbeni inštrument, v novejšem času pa se je pojavila ideja glasbene naprave s tipkami, ki lahko V sklopu našega projekta želimo izdelati preprost sintetiza- sintetizira (umetno predvaja) celotno paleto zvokov, celo ta- tor, tj. klaviature, ki posnemajo delovanje klavirja. Pripo- kšnih, ki jih s tradicionalnimi inštrumenti ne moremo dobiti. ročljivo je, da so klaviature uporabne za vajo in snemanje Ideja o sintetizatorju, tj. napravi, ki s pomočjo vnosnega zvoka, da ustrezajo standardu MIDI [1], [5] in da so čim modula (tipkovnice) zbira podatke o tem, kdaj in katera enostavnejše za uporabo. Praktično to pomeni, da morajo tipka je bila pritisnjena, ki se na podlagi teh podatkov od- delovati kot samostojna, baterijsko napajana naprava brez zove z določenim zvokom [10], je spremenila potek glasbene povezave z zunanjim svetom in morajo biti prenosne. V tem industrije. Od tedaj naprej glasbeniki in producenti iščejo primeru jih namreč lahko uporabimo tudi na koncertu, kar načine, kako sintetizatorju dodati nove zvoke, ali jih izbolj- je glavna motivacija našega dela. šati. Struktura članka v nadaljevanju je naslednja. Drugo po- Digitalni vmesnik glasbenih instrumentov, oz. krajše MIDI, glavje govori o problemu izdelave klaviatur MIDI, tretje po- je standard, ki je bil ustvarjen zaradi potrebe po medsebojni glavje opisuje postopek izdelave klaviatur in četrto predsta- kompatibilnosti med digitalnimi sintetizatorji različnih pro- vlja rezultate. Članek zaključimo s predstavitvijo možnih izboljšav našega dela v prihodnje. 2. SINTETIZATORJI ZVOKA IN KLAVIA- TURE MIDI Sintetizator zvoka uporabniku omogoča ustvarjanje in iz- vajanje najrazličnejših zvokov. Obstaja več vrst sintetiza- torjev, od najosnovnejših analognih do nekoliko kompleks- nejših digitalnih, npr. vzorčevalnih (angl. sampler), dodaj- nih (angl. additive) in odvzemnih (angl. subtract) sinte- StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 45 tizatorjev. V začetku šestdesetih let prejšnjega stoletja so se pojavili prvi zametki analognih sintetizatorjev zvoka. Ti so bazirali na osnovi analognih elektronskih komponent in so želen zvok generirali s sinusnim, pravokotnim, žagastim ali trikotnim generatorjem signala, kakor tudi pripadajočimi filtri ter generatorji šuma. Predstavljali so odskočno desko za razvoj naprednejših, digitalnih sintetizatorjev, ki so se pojavili z razvojem mikroprocesorjev in digitalnih vezij. V tem času se je pojavila ideja o digitalni sintezi zvoka in spo- znanju, da lahko veliko število dragih analognih komponent nadomestimo z računalniškim algoritmom. Ta lahko opi- suje barvo, višino, glasnost in trajanje zvoka digitalno. V glasbeni srenji se poleg navedenih pojavljajo tudi nekoliko zahtevnejši opisi zvoka in not, kot so: Slika 1: Zasnovane klaviature MIDI. • zavitost note (angl. pitch up, pitch down) - višina note se s časom spreminja, 2.1 Standard MIDI Da naprava ustreza standardu MIDI, mora upoštevati nekaj • transponiranje note - nota je zvišana ali znižana za sistemskih zahtev. Vsak instrument, ki je zmožen upravlja- določeno višino (npr. pol oktave) in nja s standardom MIDI, mora imeti oddajnik in sprejemnik. • zadrževanje note (angl. sustain) - ohranjanje zvenenja Vmesnik mora delovati na asinhronski (serijski) povezavi s note, četudi tipka ni več pritisnjena. hitrostjo 31.25 Kbit/s in prenaša tri bajte podatkov, tj. sta- tusni bajt, podatkovni bajt 1 in podatkovni bajt 2 (tabela 1). Naj omenimo še, da je iz poslanih podatkov za spremljavo Da dosežemo zavitost note, je potrebno poleg klaviaturske zvoka možno ustvarjati tudi osvetlitev in svetlobne efekte. tipke pritisniti tudi tipko, ki spreminja zavitost note, npr. navzgor. To pomeni, da mora uporabnik za določen čas, Zaradi njegovega enostavnega principa sintetiziranja zvoka v katerem nota spreminja višino navzgor držati dve tipki. in prenašanja not ga lahko enostavno implementiramo na Enak princip velja tudi za transponiranje in zadrževanje mikrokrmilnikih. Potrebno je poznati le nabor ukazov, ki so note. Da ju vklopimo, je potrebno za določen čas držati podani kot binarni zapisi števil, npr. zapis za aktivacijo in dve tipki, kar spretno zapisuje standard MIDI. Oktava je deaktivacijo note v tabeli 1. razdalja med osmimi zaporednimi toni (npr. med prvim in osmim tonom), pri čemer ima vsak višji ton dvakrat višjo 3. IZDELAVA KLAVIATUR MIDI frekvenco od nižjega tona. Izdelave klaviatur smo se lotili z načrtovanjem funkcij kla- viatur, ki so: Pojav prvih digitalnih sintetizatorjev je zaradi manjšega šte- vila elektronskih komponent omogočal cenejši pristop gene- riranja zvoka. A je poleg tega ta pristop omogočal tudi • predvajanje (reprodukcija) osnovnih zvokov, manjšo izbiro različnih tonov zvoka. Prav tako so se po- javljale neželene izgube pretvorbe iz analognega v digitalni • prenosljivost in avtonomija (baterijsko napajanje, vgra- format (in obratno). Dandanes analogne generatorje uspe- jen računalnik), šno zamenjujejo digitalni signalni procesorji (DSP) ter kon- • zanesljivo delovanje, trolne plošče s pripadajočimi prikazovalniki, kakovost zvoka pa presega zmožnosti tedanjih sintetizatorjev. Slednje upo- • čim enostavnejša izvedba, rabniku omogočajo spreminjanje nastavitev v realnem času in izbiro različnih zvokov, kakor tudi sporočajo informacijo • nizka latenca (čas med pritiskom na tipko in predva- o trenutnem stanju. Generiran signal je nato speljan do janjem zvoka) in ojačevalnika, ki signal ojači in pošlje do zvočnika. • predvajanje zvoka naj bo opravljena v ohišju klaviatur (vgrajena naj bosta tudi ojačevalec in zvočnik). Vzorčevalni sintetizatorji temeljijo na principu vnaprej shra- njenih posnetkov določenih zvokov. Ko program ali naprava zazna, da je bila pritisnjena tipka, jo nadomesti z zvokom, ki Prva alineja, tj. reprodukcija osnovnih zvokov predstavlja je shranjen v pomnilniku. Po tej klasifikaciji uvrščamo naše zmožnost predvajanja zvokov klavirja, kitare in bobnov. Pre- klaviature MIDI med vzorčevalnike (samplerje), saj naprava nosljivost ter avtonomija baterije (čas delovanja baterije, ka- zvoka ne sintetizira, ampak le predvaja (slika 1). Zvoki so teri znaša vsaj osem ur) omogočata, da lahko uporabnik sin- vnaprej posneti vzorci glasbil ali glasov in so shranjeni v po- tetizator uporablja tudi na koncertu. Tretja in četrta alineja mnilniku mikroračunalnika Raspberry Pi 2 z naloženim ope- sodelujeta z roko v roki, zato želimo sintetizator izdelati s racijskim sistemom Raspbian. Kakovost reproduciranega čim manj elementi, medtem ko se posledici pete alineje, tj. zvoka zato neposredno določa kakovost posnetega vzorca, zakasnitve (angl. latency) ne moremo izogniti. Zadnja ali- kar je njihova največja slabost. Prednost vzorčevalnih sin- neja podaja kompaktnost, oz. končno obliko sintetizatorja. tetizatorjev je v tem, da trošijo malo procesorske moči, saj je za predvajanje potrebno le prenesti podatke iz začasnega pomnilnika in jih povezati s pritisnjeno tipko. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 46 Postopek izdelave smo razdelili v več faz: 3.1 Izdelava vezij Načrtovanje vezij smo izvedli s programoma za načrtovanje tiskanin, tj. Eagle in Target3001!. Izdelali smo tri vno- • načrtovanje 3D-modela ohišja in klaviaturskih tipk v sne module, s skupaj 36 tipkami, kar omogoča glasbeni raz- programu SolidWorks, pon treh oktav. Širok razpon zvokov sicer ugodno vpliva na kakovost in uporabo klaviatur, vendar je potrebno ome- • načrtovanje elektronskih vezij, niti problem omejenega števila vhodno-izhodnih priključkov na mikrokrmilniku MSP430F5529. V skladu s tem smo • izdelava modela in jedkanje elektronskih vezij, pred mikrokrmilnik namestili 16-kanalni analogni multiple- kser HC4067. Slednji za šestnajst različnih vnosnih elemen- • sestavljanje fizičnega modela, klaviaturskih tipk in ele- tov (tipk ali potenciometrov) potrebuje samo štiri izhode in ktronskih vezij v celoto, en priključek za analogno-digitalno (A/D) pretvorbo. Doda- tni načrtovalski izziv je predstavljala nadzorna plošča, prek • programiranje, katere je moč nastavljati višino, glasnost ter zadrževanje not. Plošči smo prigradili tudi zaslon LCD. Zaradi različnih na- • testiranje in odpravljanje težav in pajalnih napetosti LCD prikazovalnika (5 V enosmerne na- petosti) in mikrokrmilnika (3.3 V enosmerne napetosti), smo • vrednotenje dela. uporabili invertersko vezje, tj. vezje ki generira negativno napetost. Invertersko vezje je priključeno na pulzno-širinski izhod mikrokrmilnika in na določen priključek prikazoval- Fazi načrtovanja 3D modela in tipk ter elektronskih vezij nika LCD, kjer ob pravilno nastavljeni širini pulza od 5 sta najpomembnejši izmed vseh. To pomeni, da smo jima VDC odšteje ravno potrebnih 1.7 VDC. Tako smo dosegli namenili posebno pozornost. Skrbno smo določili vse di- dvosmerno komunikacijo, kar smo morali predvideti že v na- menzije izdelka in material (slika 2 in slika 3). Klaviature črtovalski fazi. smo izdelali iz lesa, saj je bila to cenovno najugodnejša re- šitev. Cena izdelave ogrodja s pomočjo tiskalnika 3D, za Za zagotavljanje zanesljivosti smo kasneje zgradili še napa- katero smo se sprva sicer odločili, bi namreč večkrat prese- jalni modul, kakor tudi stereo ojačevalno vezje, osnovano na gla končne stroške lesa in spojnih elementov. Uporabili smo vezju LM386. Ugotovili smo namreč, da je glasnost avdio topolove vezane plošče debeline 8 mm, zato daje izdelek do- signala iz mikroračunalnika Raspberry Pi nizka in da je zato daten občutek trdnosti in estetske dovršenosti. gradnja ojačevalnega vezja neizogibna. Načrtovano vezjo (slika 4) smo nato natisnili na ploščo Vitro- plast. Vitroplast je plošča, izdelana iz polprevodniškega ma- teriala, na katero je nanesena tanka plast bakra. Natisnjeno vezje in ploščo Vitroplast smo nato nekajkrat vstavili v vroč plastifikator. S tem smo dosegli, da se je načrtovano vezje zapeklo na tanko površino bakra. Zapečeno vezje smo nato z mešanico klorovodikove kisline ter vodikovega peroksida zjedkali. Ob jedkanju se neuporabljena plast bakra odstrani, zato na plošči ostane zgolj odtis električnega vezja. Vezje smo nato očistili z redčilom ter nazadnje izvrtali še pred- videne luknje za spajanje elektronskih komponent. Slika 5 prikazuje jedkano in očiščeno vezje za tipkovnico. Slika 2: Zasnovano ohišje - spodnji del. Slika 4: Načrtovano vezje stereo ojačevalnika v programu Eagle. Slika 3: Zasnovano ohišje - zgornji del. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 47 Tabela 1: Kodiranje aktivacije in deaktivacije note. Statusni bajt Podatkovni bajt 1 Podatkovni bajt 2 Sporočilo 1000kkkk 0vvvvvvv 0ggggggg Aktivacija note 1001kkkk 0vvvvvvv 0ggggggg Deaktivacija note • drugi bajt nosi informacijo o višini note, npr. število 0 predstavlja noto C0, število 128 pa noto G10 in • tretji bajt nosi informacijo o glasnosti note pri čemer število 0 predstavlja minimalno glasnost in število 128 maksimalno glasnost. Vse tri bajte podatkov lahko prikažemo tudi tabelarično. Tabela 1 opisuje kodiranje toka podatkov, ki se pojavlja med prenosom MIDI. Aktivacija (angl. Note on) note je predsta- vljena vnaprej. Opisana je s statusnim bajtom, katerega prvi štirje biti predstavljajo binarno vrednost 1000, zadnji štirje Slika 5: Jedkano in očiščeno vezje ene izmed treh tipkovnic. pa kanal MIDI (črka k ). Namen kanala MIDI se skriva v is- točasnem snemanju, oz. predvajanju več skladb MIDI, zato 3.2 Sestavljanje klaviatur ima vsaka naprava rezerviran svoj kanal. Naprave, ki upo- rabljajo standard MIDI, namreč lahko medsebojno poljubno Sestavljanje klaviatur smo začeli s sestavljanjem lesenega povežemo. Za deaktivacijo (angl. Note off) se binarna vre- okvirja klaviatur. Ugotovili smo, da se tipkovnica težko dnost spremeni v 1001. Podatkovna bajta sta sestavljena prilagaja okvirju sintetizatorja, kar praktično nismo pre- iz note (črka n) in pritiska (črka p), oba variirata med vre- dvideli v načrtovalski fazi. Na levi strani čelne plošče smo dnostmi 0-127, kar sovpada z vrednostjo 27. namestili šest tipk, preko katerih lahko uporabnik spremi- nja nastavitve zvoka (zadrževanje note, višino, transponira- Postopek aktivacije note prikazuje algoritem 1, medtem ko nje,...). S pripadajočimi prikazovalniki LED (diodami) lahko postopek deaktivacije note algoritem 2. uporabnik spremlja trenutno stanje nastavitev. Pod tipkami se nahajajo trije potenciometri, ki skrbijo za spreminjanje Algoritem 1 Serijski prenos aktivacije note glasnosti, ojačanja vgrajenega ojačevalca in kontrasta LCD zaslona. Klaviaturam smo vgradili 1 W stereo ojačevalec ter Serial.Init(); //naloži modul serijske komunikacije dva zvočnika. Namestili smo tudi priklop za stereo izhod, Serial.Begin(9600); //začni s komunikacijo s hitrostjo ki ob preklopu klecnega stikala posreduje zvok iz vgrajenih 9600 bitov na sekundo zvočnikov v priklopljeno napravo. Za dodatno zaneljivost Serial.Write(144); //pošlji ukaz za aktivacijo note smo namestili še dva priklopa USB in sicer za baterijo in Serial.Write(48); //nota naj ima višino C4 mikroračunalnik (ali kakšni drugi shranjevalni medij). Serial.Write(50); //nota naj ima glasnost 50 Delay(500); //nota naj zveni 500 ms 3.3 Programiranje Za branje podatkov klaviatur smo uporabili mikrokrmilnik MSP430F5529 družine Texas Instruments. Program za mi- Algoritem 2 Serijski prenos deaktivacije note krokrmilnik je v celoti napisan v programskem jeziku C Serial.Write(128) //pošlji ukaz za deaktivacijo note v studiu IAR Embedded Workbench. Za ohranjanje pre- Serial.Write(48); //nota naj ima višino C4 glednosti programa in omogočitev kasnejše nadgradnje smo Serial.Write(50); //nota naj ima glasnost 50 program razdelili v številne knjižnice. Jedro programa tako predstavlja branje kanalov multiplekserja (tipk). Praktično to pomeni, da je glavna naloga mikrokrmilnika sprejemanje in obdelavo signalov. Algoritma 1 in 2 praktično prikazujeta serijski prenos podat- kov iz mikrokrmilnika na mikroračunalnik. Sprva se iniciali- Vsaka nota, ki jo predstavlja tipka, ima svojo lastno funkcijo zira povezava med obema, nato se pošlje ukaz za aktivacijo v programu. Po pritisku slednje, A/D pretvornik mikro- note, kateremu sledita višina in glasnost. Za izzvenjenje note krmilnika zazna spremembo napetosti in zaznane podatke mora mikrokrmilnik poslati ukaz za deaktivacijo note, sicer pošlje mikroračunalniku. Pošiljanje podatkov poteka v obliki se nota še vedno predvaja. treh bajtov preko serijskega prenosa: Mikroračunalnik prejete podatke interpretira. Interpretacija poteka s programom ttyMIDI, ki je prednaložen na mikro- • v prvem bajtu je shranjen podatek o aktivaciji note računalniku (slika 6). Program ttyMIDI najprej poskuša (npr. število 144(10) -> 010010001(2) nosi ukaz o pri- prepoznati pravilnost poslanega toka podatkov v skladu z tisku - aktivaciji note, medtem ko število 128(10) -> Alg. 1, šele nato v lupini po vrsticah izpiše poslane do- 10000000(2) o spustu - deaktivaciji), godke (slika 7). Poleg tega, program ustvarja navidezna StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 48 vrata MIDI, ki so potrebna za kasnejšo sintetizacijo zvoka niso popolne, saj jim zaradi neujemanja zaenkrat še nismo v programu Hydrogen. Vrata nadomeščajo fizični 5-pinski namestili pokrovov tipk (slika 9). Za tipke smo predvideli priključek MIDI, ki ga mikroračunalnik Raspberry Pi nima tisk 3D. vgrajenega. Čeprav na tržišču obstajajo specializirani pre- tvorniki MIDI na USB, ki bi ga lahko uporabili v našem projektu, vendar bi za povezavo z mikrokrmilnikom potre- bovali še kabel MIDI. Za uspešno predvajanje zvoka na mikroračunalniku je po- trebno konfigurirati Raspberry glasbeno (angl. audio) nad- zorno ploščo QjackCtl. Prva konfiguracija je nekoliko zaple- tena, je pa princip enak za vse sintetizatorske programe. Program Hydrogen je splošno namenjen za predvajanje zvo- kov bobnov, četudi omogoča spreminjanje barve zvoke, do- dajanje efekta odmeva, ipd. Program je zato možno upora- biti tudi za predvajanje nekaterih drugih glasbil. Velja ome- niti, da program Hydrogen ni edini program za sintetizacijo zvoka na operacijskem sistemu Raspbian, ampak obstaja še npr. Swami. Princip delovanja omenjenega temelji na t.i. zvočnih pisavah (angl. Soundfont), katere izberemo ob za- gonu programa. Soundfont je format zapisa vzorcev glasbil Slika 8: Končen, vendar ne končan izdelek. (za vsako noto je posnet zvok glasbila), ki jih vzorčevalni sintetizator poveže s poslanimi notami MIDI. Mikroračunal- niku smo za prijaznejšo uporabniško izkušnjo dodali tudi uporovni zaslon na dotik, ki omogoča upravljanje s prilože- nim pisalom (slika 7). Slika 9: Načrtovani pokrovi tipk, ki pa še niso bili natisnjeni. Kljub nepopolnemu izdelku smo klaviature lahko stestirali na operacijskem sistemu Raspbian in sistemu Windows (slika 10). Slika 6: Zaznavanje poslanih MIDI not v programu ttyMIDI na mikroračunalniku Rasbperry Pi. Ugotovili smo, da je s klaviaturami moč zaigrati kakršnokoli skladbo. Kakovost tipkovnice je solidna, delujejo vse tipke. Predvajan zvok je dovolj glasen, zato je ojačevalec primerno načrtovan, kakor tudi kakovost zvoka, ki je nekoliko odvisna tudi od oblike klaviatur. Tipki za transponiranje in zavi- janje note zadovoljivo upravičujeta svojo vlogo, saj lahko sintetizator predvaja tudi vmesne note. Slika 7: Mikroračunalnik Raspberry Pi 2 z zaslonom na do- tik. 4. TESTIRANJE KLAVIATUR Klaviature merijo 45 × 21 × 18 cm, tehtajo okrog 1300 g (brez baterije) in so napram velikim sintetizatorjem lahko prenosljive (slika 8). Težo bi z izbiro primernejšega materi- Slika 10: Zaznavanje poslanih not MIDI v programu Hairless ala lahko še dodatno zmanjšali. Klaviature trenutno sicer še MIDI Serial Bridge na osebnem računalniku. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 49 Zahvala Za pomoč pri izvedbi projekta, se iskreno zahvaljujem profe- sorju Alešu Hacetu s Fakultete za elektrotehniko, računalni- štvo in informatiko v Mariboru in asistentu Roku Pučku, ki sta mi pomagala pri programiranju mikrokrmilnika MSP430. Hvala tudi za priložnost gradnje klaviatur kot projektnega dela. 6. REFERENCE [1] MIDI Association. https://www.midi.org/. [Dostopano: 2016-09-2]. [2] P. R. Cook and G. Scavone. The synthesis toolkit (stk). In Proceedings of the International Computer Music Conference, pages 164–166, 1999. Slika 11: Nepregledno število žic. [3] R. P. Gilmore. Direct digital synthesizer driven phase lock loop frequency synthesizer, Oct. 23 1990. US Patent 4,965,533. 5. SKLEP [4] P. D. Griffis. Switching arrangement for a stereophonic Ugotovili smo težavo s prekomerno zakasnitvijo med priti- sound synthesizer, Oct. 23 1984. US Patent 4,479,235. skom tipke in dejanskim predvajanjem zvoka. Sumimo, da [5] J. Hass. Midi. http://www.indiana.edu/~emusic/ do tega prihaja zaradi slabe optimizacije programa mikro- etext/MIDI/chapter3_MIDI4.shtml, 2013. krmilnika. Problema se popolnoma že v osnovi ne da od- [Dostopano: 2016-08-31]. praviti, lahko se ga pa minimizira. Z nadaljnjo optimizacijo [6] Y. Kaneoka. Electronic sound synthesizer, Nov. 8 lahko dosežemo zakasnitev pod 30 ms, kar je veliko manj kot 1988. US Patent 4,783,812. trenutna, ki znaša 100-150 ms. [7] A. M. McDonald, D. C. Quinn, and D. C. Perry. Sound synthesizer in a vehicle, Dec. 6 1994. US Patent Prav tako bi bilo že v osnovi potrebno izbrati zaslon LCD, 5,371,802. ki deluje na napajalni napetosti mikrokrmilnika (3.3 VDC), [8] M. Russ. Sound synthesis and sampling. Taylor & s čimer bi dodatno prihranili prostor in nekaj priključkov na Francis, 2004. mikrokrmilniku. Odzivni čas zaslona je v primerjavi s ti- [9] Wikipedia. MIDI. stimi iz višjega cenovnega razreda visok in nam je v začetni https://en.wikipedia.org/wiki/MIDI, 2016. fazi povzročal nemalo težav z odzivnostjo klaviatur. Pro- [Dostopano: 2016-08-31]. blem smo odpravili z uvedbo prekinitev znotraj programa na mikrokrmilniku. Pojavljale so se tudi težave z zaslonom [10] Wikipedia. Sintetizator. na dotik, saj je bilo težko najti primerne gonilnike ter zaslon https://sl.wikipedia.org/wiki/Sintetizator, usposobiti. 2016. [Dostopano: 2016-08-22]. Da bi bile klaviature resnično prenosljive in uporabniku pri- jazne, bi bilo potrebno napisati grafični vmesnik, kateri bi se pojavil takoj ob zagonu. Ta bi moral interaktivno omogo- čati izbiro glasbila in njegovih parametrov. Najprimernejši programski jezik za uporabniški program bi po našem mne- nju bila Java, v kateri je relativno enostavno programirati in je kompatibilna z mikroračunalnikom Raspberry Pi. Za širšo paleto sintetiziranih zvokov predlagamo uporabo Soundfont-ov, katerih opus obsega zvoke klavirja, bobnov, kitare, trobente in nekaterih drugih. Prav tako želimo v nadaljevanju tudi za glasbeno spremljavo usposobiti pove- zljivost toka MIDI podatkov s svetlobnimi efekti osvetljave. Kot končno rešitev na množico kablov in priključkov (slika 11) bi predlagali gradnjo univerzalne matične plošče, kamor bi pritrdili vse zahtevane module in tako optimirali izrabo pro- stora. Prav tako bi prihranili na končnih stroških, saj bi s tem odpadli stroški številnih priključkov. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 50 Greedy Heuristics for the Generalized Independent Cascade Model László Tóth University of Szeged 13 Dugonics Squere Szeged, Hungary tlaszlo@inf.u-szeged.hu ABSTRACT in practice. In [2] Bóta et al. extended the model and in- In this paper we formulate optimization problems for the troduced the Generalized Independent Cascade Model. The Generalzed Independent Cascade Model, which is introduced initial state of this model does not consist of infected and by Bota et al. The purpose of these tasks is to define the size uninfected vertices, but introduces an a priori probability k which cause the greatest infection in a network. We show of infection for each vertex. Each vertex receives an a pos- that a greedy heuristic ensure the theoretically guaranteed teriori infection value by the end of the infection process. precision for the problems. Finally we investigate the our Because the infection process above is #P-complete, [2] in- methods with practical tests. troduces a number of approximation algorithms. In turn, the influence-maximization problem has not been defined Keywords for this more general case. Influence Maximization, Generalized Independent Cascade In this paper we define two infection-maximization prob- Model, Greedy Heuristics lems connected to the generalized model above. They are the positive and the negative problems. At the positive task Supervisor every elements of a social network have a probability val- Dr. Miklós Krész ues, so-called ’input’ values. These values are considered Department of Applied Informatics, if a element is part of the inintial infection set, the other University of Szeged, Hungary values is zero during the positive infection process. At the Contact: kresz@jgypk.szte.hu end of this the amount of the probability values of infected vertices mean the a posteriori value of the current process. 1. INTRODUCTION If we model a campain of a product we can take an affinity We usually think about medical science if we hear about analysis. The optimization problem for this task is to find the infection. It also appeared in the sociology in the early the expected value of the maximal number of the infected years of scientific modeling, then some sociologist start to elements. At the introduced negative task we assume that use Linear Threshold Model (in [5]) and try to model differ- a firm would like to increase the clients of ’churn incliation’ ent social effect. Therefore, economist discovered that the with help of a offered products. In this case every single ele- modified version of threshold model (Independent Cascade ments (clients) have another values, so-called ’uplift’ values Model, in [4]) is suitable to help research of business process. as the measure of the churn willingness. The method calcu- This model is the most important break-through the theory lates with uplift values of the elements if the they are part of of computation point of view. The infection spreads in so- the initial set, otherwise with the The related optimization cial networks the following way: we choose an initial infected problem is to find the minimal churn incliation. vertex set, and only those vertices spread the infection after this that became infected in the previous iteration. Every We also present solution methods based on greedy heuris- edge start from an infected vertex has a single chance for in- tics, and compare their results with each other. We prove fecting using its own infection probability. Kempe et al. [6] that a guaranteed approximation precision can be achieved defined the influence-maximization problem, where we look for these greedy algorithms. To guarantee efficiency from a the highest. This problem is NP-complete, but Kempe et practical point of view, we decrease the search space for the al. proved in [6] that applying a greedy algorithm gives a greedy methods using different approaches (e.g. selection guaranteed precision that results in good quality solutions based on vertex degree). In our test cases we compared this heuristics with help of generated graphs. 2. INFECTION MODELS The aim of this chapter is to introduce the main definition of our topic. The basic definitions and concepts related to graph theory are based on [10]. A simple graph is a G = (V, E) structure, where V is a finite vertex or vertex set, E is the edge set. There are probabilities on the edges and the infection is spread helping these values according to a given StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 51 rule. There are networks that are built of simple graphs At the beginning the vertices become active independently which contain directed edges with values. These networks of each other with their assigned probabilities. Thereafter, are used in infection models, which have several types. All the infection process of the IC model applies with a ran- of them have similar input structure which is built by a domly selected active set. In this process, each vertex gets a finite iterative process. During this process there are vertex value by function w∗ : V → [0, 1] on the vertices, which are sets that contain three type of vertices: infected, infectious, the a posteriori influence. The influence measure σ(·) which not infected yet (susceptible). We can consider two types of is the sum of output infection value can be given: process: progressive and non-progressive. The base of the X progressive infection models is that their vertices cannot be σ(w) = w∗(v) recovered if they had been infected. In turn, during the v∈V non-progressive process there is recovery. The models of paper [6] use progressive process. The infection models can There are several simulation that calculating this measure. be distinguished by the type of edge-values. The models can We consider the Complete Simulation (CS) according to pa- be stochastic infection models if edge-values are probabilities per [2] and we prove that theory of Kempe et al. is right (fractions between 0 and 1). These probabilities give the so- for the examined GIC. A required number of simulations called ‘effect of network’. After building a model we get can be defined to give certain measure of approximation () an infected vertex set A and the value of infection as the to σ(A) with a given probability (δ). The CS is a method expected value of infected vertices is σ(A). that gets a network G and a sample size k. The result of algorithm is the relative frequency of infection. Since this 2.1 Independent Cascade Model method is based on frequency counting, its precision and In this section we show a specialized infection model, the In- time complexity depends greatly on the size k. dependent Cascade Model (IC). It is introduced in paper [4]. Starting with an initially active set of vertices A0 ⊂ V (G). Proposition 1. If the GIC starting with A is simulated Let Ai ⊂ V (G) denote the set of vertices newly activated independently at least in iteration i. In iteration i + 1, every vertex u ∈ Ai has one chance to activate each of its inactive neighbors ln(2/δ)/(2w2av2) v ∈ V \ ∪0≤j≤iSj according to wu,v. These are usually prob- times, then the average number of activated vertices over ability values. If the attempt is successful, then v becomes these simulation is a (1±)-approximation to σ(A), with active in iteration i + 1. In this case the vertices are infected probability at least (1 − δ), if δ, ∈ (0, 1), and w independently. The vertices can infect a susceptible one at av is the average of the input weights. once in the current iteration. [6] The open question of the field is to compute the expected We remark that the Proposition 1. is not only true for GIC, number of infected vertex is #P-complete. There are rele- but for the infection process in general. vant researches for this question in papers [3] and [7]. Kempe and his colleagues gave approximate values with arbitrary accuracy for the number of infected elements with simula- 2.3 Infection Heuristics tion for this problem. Unfortunately, this simulation is very Although after the model generalization, Bóta et al. devel- costly. They defined the influence-maximization problem for oped simulations and heuristics which efficiency and accu- this model as well. They looked for the vertex set for which racy were not acceptable. As a consequence, other heuris- the expected value of the infected vertices is the highest. tics are worth to research. We looked for a unique heuristic The optimal solution for influence maximization can be effi- which can be accelerate existing methods. In our study we ciently approximated within a factor of (1 − 1/e − ), where used the analytic formula by Srivastrava et al. [9], which is e is the base of the natural algorithm and is any positive usually applied in binary infection models. This formula has real number. This is a performance guarantee slightly better been used for IC model before. We used it at first for GIC. than 63%. They proved that applying a greedy algorithm gives the guaranteed precision that results in good quality Let Au,t denote a probability that vertex u is infected at time solutions in practice. t. Furthermore let Bu,t denote another probability that ver- tex u is infected until time t. According to above Au,0 = 2.2 Generalized Independent Cascade Model w(u), so at time 0 the apriori infection will be given. In ad- Bóta et al. extended the IC and introduced the Generalized dition to Bu,t = Pt A j=0 u,j , therefore Au,t = Bu,t − Bu,t−1. (Independent) Cascade Model (GIC)1 [2]. The initial state of this model does not consist of infected and uninfected ver- Let Ni(u) denote the endpoints set of incoming edges of tices, but introduces an a priori probability (input infection vertex u, then we can calculate Bu,t simply: weight w) of infection for each vertex. At the end of the in- Y fection process, each vertex receives an a posterior infection Bu,t := 1 − (1 − Bu,t) · (1 − p(v, u) · Av,t−1) value (output infection weight (w∗)). v∈Ni(u) Formally, there is a given function wv : V → [0, 1] on the ver- We can approximate the a posteriori infection with B tices, which is the a priori measure of elements of network G. u,t be- cause the infection process is progressive. The accuracy can 1Bóta et al. used the Generalized Cascade technical term, be enhanced by increasing t. The basic idea of this heuristic but this name is already reserved by Kempe et al. [6] is to consider independently the effect of edge probabilities. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 52 3. INFLUENCE-MAXIMIZATION 3.2 Reducing the solution space At the original model a function σ(·) is given at the IC model To accelarate our methods we have to reduce the solution and we are looking for the set, for which the function is space. The elements of the initial set of vertices are from the maximal. For the general case a function w of probabilities set of which the elements have positive input probability at is given a priori and it is not obvious how we can maximize the positive case. At the negative case there are only those it. We defined two problems to analyze the function. They elements in the initial set which are smaller than the input are positive and negative influence maximization problem value. This reduction is useful because the excluded ele- connection with spreading of positive and negative effect. ments are not important at calculating the estimated proba- bility of the network. In this case the influence-maximization 3.1 Influence-maximization in the GIC problem is to find reduced set V an initial set A with given Because the influence-maximization problem has not been k elements, where these elements have maximal infection. defined for more general cases, we defined two infection- Formally let v ∈ V : maximization problems. Both problems have modified in- put probabilities. For the positive case we defined probabil- • Positive case: if wv > 0, then v ∪ V ∗ ity values, which are greater than zero on vertices of initial vertex set. It is zero on the other vertices. An example • Negative case: if wup v < wv, then v ∪ V ∗ for the positive case is product affinity, which is measured by the reaction of the clients for a product at the service We prove that we can get optimal value after the reduction. sector. An example for the negative infection maximization model is churn prediction. We measure the relationship be- Lemma 1. Let V ∗ denote elements of V , for which the tween the clients and the service provider. We would like to input infection w is positive at network G and case of GIC maximize the minimal churn. In this case there are the so model. Thus, infection function σG p (w) gets its optimal value called ‘uplift’ probability values, which are given at initial on the set A ⊆ V ∗. vertices of vertex set. These values are measured for the Lemma 2. Let V ∗ denote elements of V , for which value clients at the service providers. The vertices that are not in wup less than input infection w at network G and case of the initial vertex set can be measured by the original prob- GIC model. Thus, infection function σG n (wn) gets its opti- ability values. These values give the size of the client churn mal value on the set A ⊆ V ∗. at companies. The formally definitions of tasks are the next: Definition 1. (Positive influence maximization model) Hav- 4. SOLUTION METHODS ing a network G, where a set A ⊂ V . Let w function of Since Kempe et al. in [7] realized that approximation of the weights, and F a GIC model. Furthermore let wA optimum of the complex task can be given with arbitrary p,v the mod- ified input probability, where precision with the help of a greedy algorithm, it seems nat- ural to use it at the general case. We illustrate what type of acceleration can be used for the calculation. • ∀v ∈ A, wA p,v = wv • ∀v / ∈ A, wA 4.1 Greedy framework p,v = 0. In this section we introduce a theorem which can be used for the specified two tasks and we show the proof. To present Optimization task: Search set A with k elements, where our results, we need to introduce some concepts based on σp(A) = σ(wA p ) is maximal. [7]. We said that function f is submodular if it satisfies a natural ‘diminishing returns’ property: the marginal gain Thus elements of A get values according to w, another ele- from adding the same element to a superset of S. Formally, ments (V \ A) get zero. a submodular function satisfies Definition 2. (Negative influence maximization model) An f (S ∪ {v}) − f (S) ≥ f (T ∪ {v}) − f (T ), IC model which of input infection have a wA n,v modified input for all elements v and all pairs of sets S ⊆ T . And a function probability, where f monotone if adding an element to a set cannot cause f to decrease: • ∀v ∈ A, wA n,v = wup v , uplift probability f (S ∪ {v}) ≥ f (S). • ∀v / ∈ A, wA n,v = wv . The greedy method starts from an empty set. It repeatedly adds the vertex x to set A maximizing the marginal gain Optimization task: Search set A with k elements, where g(A ∪ {x}) − g(A) if having a submodular function g. [3] σn(A) = σ(w) − σ(wA n ) is maximal. In [8] Nemhauser et al. studied the monotone, submodular Thus elements of A get values according to an uplift func- functions: tion, another elements (V \ A) get values according to w. Theorem 1. Let σ(·) denote a non-negative, monotone, submodular function. Then the greedy algorithm (for k iter- At the campain of the products k clients are targeted for ations) adds an element with the largest marginal increase both cases. At the current infection process step all suscep- in σ(·) produces a k-element set A such that tible elements will be activated according to their edge and vertex probabilities. σ(A) ≥ (1 − 1/e) · max|B|=kσ(B) StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 53 Algorithm 1 Greedy Method In the given iteration, if X is the current solution, we con- 1: Start with A = ∅. sider the f ∗(v) value for all elemets of X ∈ V ∗. From these 2: while |A| ≤ k do we consider the greatest r elements, set V ˜. We use the 3: For each vertex x, use repeated sampling to greedy strategy only on set V ˜ and we consider the greatest approximate g(A ∪ {x}) marginal gain. We can choose from two different reduction 4: Add the vertex with largest estimate for method: g(A ∪ {x}) to A. 5: end while • 6: Output the set A of vertices. Degree: Function f ∗ gets values as following: Positive maximalization problem: For each vertex, adding the probabilities of outgoing edges. The sum is multi- plied by the input probability of the given vertex. The The function σ satisfies the conditions above if we consider method selects vertices which are the greatest accord- the IC model. Therefore Nemhauser et al. gave a suitable ing to these values. approximation. Our main result is that we showed that it is Negative maximalization problem: It is similar to posi- suitable for the GIC. So it is also true for the expected value tive one, but the product of values are subtracted from σ(wp,v) and σ(wn,v) in the case of the positive and negative uplift value of the given vertex. influence maximization problems. The process sets up a sequence for both cases and con- siders the greatest r elements. Let σ∗ denote σp and σn to facilitate the description of methods. As seen before σ∗ are monotone, submodular and • Modified Degree: Function f ∗ gets values as following: non-negative, we can use the greedy strategy for the general The process is similar to Degree. The difference is that model (Algorithm 2) the currently investegated vertex will be not in the next phase. Because of it, this is a dynamic calcula- Algorithm 2 Greedy Method for GIC tion. Initialization: A := ∅ After the above is executed the greedy method (Algorithm Iteration: 2) with V ˜ instead of V ∗. 1: while |A| ≤ k 2: A = A ∪ arg maxx∈V ∗\A σ∗(A ∪ {x}) 5. TEST RESULTS Output: A In this section we present the program, which was imple- mented for test. After that we show the details of the test If σ∗ is non-negative, monotone and submodular then the cases. At the end of the chapter we present the result for greedy strategy above ensures the guaranteed accuracy ac- analysis of GIC. cording to [8]. We proved the following theorems: 5.1 Test program Theorem 2. Let G be a network and let w denote input in- We created a scalable framework to analyze our theoreti- fluence function. Pick a set V ∗ contains elements for which cal solutions. As part of this framework we have a simu- w gives positive value. Then σG p (w) is non-negative, mono- lator, which generates edge- and vertex-probabilities, what ton and submodular on the set V ∗. we usually need to measure in real networks. We also use Theorem 3. Let G be a network and let wn = (w, wup) σ-approximations, a simulation and a heuristic generator. denote input influence function. Let pick a set V ∗ contains The uplift value were set up according to the input value. elements for which wup < w(v) gives positive value. Then We can generate the follows: σG n (w) is non-negative, monoton and submodular on the set V ∗. • edge probability • a priori infection probabilities of vertices The following proprosition is consequence of the theorems above and [8]. • uplift probabilities of vertices according to a priori in- fection probabilities Corollary 1. The Greedy Heuristic gives at least (1 − 1/e − )-aprroximation for the positive and negative infection max- imization problems if the model is GID. We can set the following: 4.2 Reduction methods • type of task (positive, negative) We decrease the search space for the greedy methods us- ing different approaches based on practical considerations. • heuristic mode (degree, modified degree) Based on the above, if the algorithm does not look for the solution on the whole search space, we lose the guaranteed • iteration, evaluation method (complete simulation, an- precision. Our expectation is that using the appropriate alytic formula heuristic [with parameter t]) strategy the result will be satisfying. The speed of the al- • a priori infected set size gorithm increase because of the greedy property after the reduction. Formally, the methods look like as following: • number of infection and evaluation iteration StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 54 5.2 Test Cases our problems. We reduced the search space with different In many test cases we investigated the main behavior of al- method to reach the required accuracy, and to accelerate our gorithms. We worked with about hundred graphs, which process. In the end we compared the results. In the future came from a word-association case study. In this graphs the we would like to build an efficient simulate annealing frame- vertices are words, and the directed connections are associa- work, then we will test our method on real graphs with real tion one of words to another. We also used graph generator churn value from databases of companies. (Forest Fire Model) to obtain graphs. [1] The vertex num- ber in these graphs is from hundred to thousand. The rate Although during the work a lot of theoretical compositions of those vertices where the uplift probability is greater than and methods have been introduced, but they have a rele- input probability is 25%. For other vertices the rate is 50%. vant role to play in everyday life. Nowadays the informa- In the first case, the increase of probabilities can be up to tion spreading and viral marketing are becoming more and 20%, at the other case, the decrease of probabilities can be more common terms. Economic agents realized that finding up to 60%. The other parameters can be seen on the next the relevant customers in connection with the given problem table. means financial potential. Solving such questions precisely and quickly can give unexpected positive results. Table 1: Parameterization variable value 7. ACKNOWLEDGEMENT p(u, v) 0, 1 I would like to express my gratitude to Dr. Miklós Krész, |V | 100, .., 1000 my supervisor for his enthusiastic encouragement and useful w remarks of this research work. v [0, 1]withunif ormdistribution k |V |·0, 05 This research was supported by National Research, Develop- ment and Innovation Office - NKFIH Fund No. SNN-117879. 5.3 Results After the infection model was built we used simulations on 8. REFERENCES our networks to evaluate them. We used it the whole so- [1] P. Bak, K. Chen, and C. Tang. A forest-fire model and lution space of the given network. Then, we applied our some thoughts on turbulence. Physics letters A, analytic formula (AF) heuristic with parameter t ≤ 5 for 147(5):297–300, 1990. the same networks, but we reduced the solution space help- [2] A. Bóta, M. Krész, and A. Pluhár. Approximations of ing with the introduced reduction method. We investigate the generalized cascade model. Acta Cybernetica, the average of results. If we use this heuristic, we need to 21(1):37–51, 2013. be careful about the parameters, because the accuracy will [3] W. Chen, C. Wang, and Y. Wang. Scalable influence be at the expense of efficiency. We need to find the balance. maximization for prevalent viral marketing in large-scale social networks. In KDD, 2010. Table 2: Results of positive problem testing [4] P. Domingos and M. Richardson. Mining the network method rate value of customers. In Proceedings of the Seventh whole solution space with Simulation 100% ACM SIGKDD International Conference on degree reduction with AF 95,51% Knowledge Discovery and Data Mining, KDD ’01, modif ied degree reduction with AF 96, 00% pages 57–66, New York, NY, USA, 2001. ACM. [5] M. Granovetter. Threshold models of collective behavior. American Journal of Sociology, Table 3: Results of negative problem testing 83(6):1420–1443, 1978. method rate [6] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing whole solution space with Simulation 100% the spread of influence through a social network. In degree reduction with AF 89,52% Proceedings of the Ninth ACM SIGKDD International modif ied degree reduction with AF 99, 14% Conference on Knowledge Discovery and Data Mining, KDD ’03, pages 137–146, New York, NY, USA, 2003. When we used the reduction, the run time was five times ACM. faster on average than the case of whole solution space. The [7] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing tables show results obtained from the mean value of different the spread of influence through a social network. networks. At the negative problem testing the values are Theory of Computing, 11(4):105–147, 2015. smaller than at the positive case because of the theoretical [8] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An background. At this point the difference is greater then at analysis of approximations for maximizing submodular positive, but the behavior of tasks are similar. The network set functions—i. Mathematical Programming, effect works in a different way from network which negative- 14(1):265–294, 1978. parameterized than a positive one and it can be detected [9] A. Srivastava, C. Chelmis, and V. K. Prasanna. The in. unified model of social influence and its application in influence maximization. Social Network Analysis and 6. CONCLUTIONS AND FUTURE WORKS Mining, 5(1):1–15, 2015. During our work we defined several problems for the influence- [10] D. B. West. Introduction to Graph Theory. Prentice maximization in generalized models. We worked on suit- Hall, 2005. able greedy framework, which gave guarantee precision for StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 55 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 56 Hybrid Cuckoo Search for constraint engineering design optimization problems Uroš Mlakar University of Maribor Smetanova 17 Maribor, Slovenia uros.mlakar@um.si ABSTRACT is organized as follows. In Section 2 some of related work, This paper investigates, how the hybrid self-adaptive Cuckoo mostly that of SI-based algorithms is presented. Section 3 is Search algorithm (HSA-CS) behaves, when confronted with dedicated to Cuckoo Search (CS) and the used self-adaptive constraint engineering design optimization problems. These hybrid Cuckoo Search algorithm, where an emphasis is on problems are commonly found in literature, namely: welded describing the main differences from the original CS. Section beam, pressure vessel design, speed reducer, and spring de- 4 deals with describing the design optimization problems, sign. The obtained results are compared to those found in and then in Section 5 the obtained results are presented. In literature, where the HSA-CS achieved better or comparable Section 6 the results obtained by the HSA-CS is compared to results. Based on results, we can conclude, that the HSA-CS those in the literature, and the paper is concluded in Section is suitable for use in real-life engineering applications. 7. Keywords 2. RELATED WORK design optimization, hybridization, cuckoo search, self-adaptation Since the HSA-CS belongs to the SI-based algorithms, it would only be reasonable to review the literature from this 1. INTRODUCTION point of view. Akay and Karaboga [1] presented an artificial There is a increasing rate in the research community for de- bee colony (ABC) algorithm, with a very simple constraint veloping new constrained optimization algorithms. There- handling method. This method is biased to choose feasi- fore suitable problems must be used, to show the effective- ble solutions rather than those, which are infeasible. Gan- ness, efficiency and convergence of these new algorithms. domi et al. [7] use a bat algorithm for solving constraint Such problems are usually mathematical problems like the optimization problems. Their results indicate that their CEC competition problems, but also engineering design op- method obtained better results, compared to those in lit- timization problems are adopted in the specialized litera- erature. Another ABC algorithm was proposed by Braje- ture. Many researchers have studied these problems, by ap- vic and Tuba [3]. The upgraded ABC algorithm enhances plying a wide range of different optimization methods such fine-tuning characteristics of the modification rate parame- as Quadratic Programming [5], Simulated Annealing [12], ter and employs modified scout bee phase of the ABC algo- Genetic Algorithms [9], and Swarm Intelligence [2, 3, 6, 7, rithm. Baykasoglu and Ozsoydan [2] presented an adaptive 1]. The listed algorithms are among the most used in the firefly, enhanced with chaos mechanisms. The adaptivity is literature. The design optimization problems usually have a focused on on the search mechanism and adaptive param- non-linear objective function and constraints, while the de- eter settings. They report that some best results found in sign variables are often a combination of discrete and con- literature, were improved with their method. Bulatović [4] tinuous. The hardest part of finding the optimal solution for applied the improved cuckoo search (ICS) for solving con- these problems is directly related to the constraints, which strained engineering problems, which produces better results are imposed on the problem. than the original cuckoo search (CS). Their improvements lie in the dynamic changing of the parameters of probability Since SI based algorithms are getting a lot of attention in and step size. Yang et al. [11] utilized a multi-objective CS the past couple of years, our aim was to test the behaviour (MOCS) for the beam design problem and disc brake prob- of a novel hybrid self-adaptive Cuckoo Search [8] (HSA-CS) lems. They conclude that the proposed MOCS is efficient on the design optimization problems. The rest of the paper on problems with complex constraints. 3. CUCKOO SEARCH Cuckoo search is a stochastic population-based optimization algorithm proposed by Yang and Deb in 2009 [10]. It belongs in the SI-based algorithm family, and it is inspired by the natural behaviour of some cuckoo species in nature. To trap the behavior of cuckoos in nature and adapt it to be suitable for using as a computer program the authors [10] idealized three rules: StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 57 • Each cuckoo lays one egg, and dumps it in a randomly 4. CONSTRAINED DESIGN OPTIMIZATION chosen nest, PROBLEMS • Nests with high-quality egg, will be carried over to the The following design optimization problems have been used next generations, in this study: welding beam, pressure vessel design, spring design, and speed reducer design. The used problems are • Any egg laid by a cuckoo, may be discovered by the thoroughly presented and formally defined in the remainder host bird with a probability of pa ∈ (0, 1). When an of this section. egg is discovered, the host bird may get rid of it or simply abandon the nest and build a new one. 4.1 Welding beam The goal of this problem is to design a welded beam subject Each solution in the population of the cuckoo search algo- to minimum cost, subject to some constraints. The prob- rithm corresponding to a cuckoo nest, represents the posi- lem consists of four design variables, with the objective is tion of the egg in the search space. This position can be to find the minimum fabrication cost, with constraints of mathematically defined: shear stress τ , bending stress σ, buckling load Pc, and end deflection on the beam δ. The mathematical model can be xi = {xi,j }, f or i = 1, . . . , N p and j = 1, . . . , D, (1) formulated as follows: where N p represents the population size, and D the dimen- sion of the problem to be solved. f (x) = 1.10471x21x2 + 0.04811 ∗ x3x4(14 + x2), (3) Generating new solutions in the CS is done by executing a random walk, with the use of the Levy flight distribution: subject to: xi = xi + αL(s, λ). (2) g0 : τ − 13600 ≤ 0, g1 : σ − 30000 ≤ 0, g2 : x1 − x4 ≤ 0, The term L(s, λ) determines the characteristic scale, and g3 : 0.10471x21+(0.04811x3x4(14+x2))−5 ≤ 0, g4 : 0.125−x1 ≤ 0, α > 0 denotes the scaling factor of the step size s. g5 : δ − 0.25 ≤ 0, g6 : 6000 − Pc ≤ 0, (4) 3.1 Hybrid self-adaptive Cuckoo Search where According to [8] the CS was modified by adding the following r x2 6000 M R mechanisms: balancing of the exploration strategies within τ = τ 2 + 2τ + τ 2, τ √ , τ , 1 1τ2 1 = 2 = 2R 2 2x J the CS, self-adaptation of the parameters, and population 1x2 r reduction. The used exploration employed by the HSA-CS x2 x2 x1 + x3 M = 6000(14 + ), R = 2 + ( )2, are: 2 4 2 √ x2 x1 + x3 504 ∗ 10e3 J = 2( 2x 2 1x2( ) + ( )2), σ = , • random long distance exploration, 12 2 x4x23 65856 ∗ 10e3 • stochastic short-distance exploration, and δ = , 3 ∗ 10e6x4x33 • stochastic moderate-distance exploration. q 3∗10e6 (12.039 ∗ 10e6p(x2x6)/36) x3 48∗10e6 P 3 4 c = (1 − ) (5) The listed strategies have an impact on how the trial solution 196 28.0 will be generated. The random long distance exploration is The design variables are bounded as: 0.1 ≤ x2, x3 ≤ 10, and implemented as the abandon operator. The second strategy 0.1 ≤ x1, x4 ≤ 2. improves the current solution by using a local random walk, with the help of Levy flights (Eq. 2). The last strategy 4.2 Pressure vessel design is borrowed from the DE algorithm. Additionally the last The idea of this problem is designing a compressed air stor- strategy adds a crossover operation to the CS algorithm. age design, with a working pressure of 1000 psi and and These execution of these strategies is controlled by a single minimum volume of 750 f t3. The problem is described us- parameter. ing four variables, which represent shell thickness, spherical head thickness, radius and length of the shell. The objective As was stated all parameters are fully self-adaptive, except of the problem is minimizing the manfuacturing cost of the the starting population size, which must be experimentally pressure vessel, and can be formulated as: defined. Additionally the strategy balancing probability, the abandon rate, and the elitist parameter (controls whether a random of best solution is taken as the basis trial vector cal- culation) are determined by the user. Lastly the population f (x) = 0.6224x1x3x4 +1.7781x2x23+3.1661x21x4+19.84x21x3, reduction is implemented by using a simple linear reduction. (6) subject to It was proven by the authors of the HSA-CS, that the biggest g impact on the results has the inclusion of multiple strategies, 0 : −x1 + 0.0193x3 ≤ 0, g1 : −x2 + 0.00954x3 ≤ 0, than followed by self-adaptation. Population reduction did 4 g2 : −πx23x4 − πx33 + 1296000 ≤ 0, g3 : x4 − 240 ≤ 0. not have a big impact on the results. For more information 3 about HSA-CS readers are referred to [8]. (7) StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 58 The bounds of the design variables are: 0.0625 ≤ x1, x2 ≤ average value for function evaluations found in literature. 99 ∗ 0.0625, and 10 ≤ x3, x4 ≤ 200. The parameters of HSA-CS were set according to the authors in [8], while the population size was varied as: N p = 30 for 4.3 Spring design welded beam, spring design, and speed reducer, while for pressure vessel N p = 50. Each experiment was replicated The spring design optimization problem deals with an opti- 50 times, thus the results reported here are the average of mal design of a tension spring. The problem consists of three those runs. variables, which are the number of spring coils, winding di- ameter, and wire diameter. The objective is to minimize the Table 1 holds the results of the experiments. For each prob- weight of the spring, subject to minimum deflection, surge lem the minimum (min), maximum (max), mean, median frequency, shear stress, and limits on the outside diameter. (md), and standard deviation (std) values are reported. Mathematically it can be formulated as: The results in Table 1 indicate that the HSA-CS was able to find the same solution for the welded beam and speed f (x) = (x3 + 2) ∗ x21 ∗ x2, (8) reducer problems in all 50 runs of the algorithm. On the contrary, the HSA-CS had trouble in converging towards a subject to the following constraints: single solution. x3 4x2 1 g 2x3 2 − x2x3 0 : 1− ≤ 0, g1 : + −1 ≤ 0, 71785x4 12566(x − x4) 5108x2 1 2x3 3 3 3 6. DISCUSSION 140.45x1 In this section we analyze the results from our experiments g2 : 1 − ≤ 0, g3 : (x1 + x2) − 1.5 ≤ 0 (9) x2x and compare them to those found in the literature. For this 2 3 purpose a Table 2 is provided, where results from literature The search space of design variables are limited as: 0.05 ≤ are gathered. It can be seen, that the HSA-CS achieved com- x1 ≤ 2, 0.25 ≤ x2 ≤ 1.3, and 2 ≤ x3 ≤ 15. petitive results if not better results on all test optimization problems. For the welded beam problem our method and 4.4 Speed reducer the method in [2] converged to a single solution, whereas This problem deals with a minimum weight design of a speed other methods were not as successful. It is also hard to reducer, subject to bending stress of the gear teeth, surface say, which method performed the best, since the findings stress, stresses in the shafts, and transverse deflections of in other papers are reported only to 6 digits. On the pres- the shafts. This problem is formulated with seven design sure vessel problem, the HSA-CS achieved similar results as variables, using the following mathematical definition: for the welded beam problem. Based on the mean value the only competitive method was again the one proposed f (x) = 0.7854x1x22(3.3333x23 + 14.9334x3 − 43.0934)− in [2]. HSA-CS acheived the best results for the speed re- 1.508x ducer. Again, like for the welded beam, the results were 1(x2 6 + x2 7) + 7.477(x3 6 + x3 7) + 0.7854(x4x2 6 + x5x2 7), (10) unanimous, converging to a single solution, which was also the smallest based on mean value. Good results were also subject to: obtained on the spring design problem, were the HSA-CS had the smallest std value over the 50 runs, while obtain- 27.0 397.5 g ing good results based on the mean value. We can conclude 0 : − 1.0 ≤ 0, g1 : − 1.0 ≤ 0, x1x2x x x2 2 3 1x2 2 3 the HSA-CS would be suitable for use in real-life constraint 1.93x3 1.93x3 optimization problems. g 4 5 2 : − 1.0 ≤ 0, g3 : − 1.0 ≤ 0, x2x3x4 x 6 2x3x4 7 q ( 745x4 )2 + 16.9 ∗ 10e6) 7. CONCLUSION x2x3 g4 : − 1.0 ≤ 0, This paper investigated the recently proposed HSA-CS al- (110x3) 6 gorithm, on four well known engineering design optimiza- q ( 745x5 )2 + 157.5 ∗ 10e6) tion problems with constraints. The problems at hand were: x2x3 g5 : − 1.0 ≤ 0, welded beam, pressure vessel design, speed reducer design, (85x3) 7 and spring design. The obtained results were compared to x2x3 5x2 x1 g the some state-of-the-art methods, were the HSA-CS per- 6 : − 1 ≤ 0, g7 : − 1 ≤ 0, g8 : − 1 ≤ 0, 40 x1 12x2 formed very well, thus we can conclude it would be suitable 1.5x6 + 1.9 1.1x7 + 1.9 for use in real-life engineering applications. g9 : − 1 ≤ 0, g10 : − 1.0 ≤ 0. (11) x4 x5 The search of the design variables is defined as: 8. REFERENCES (2.6, 0.7, 17.0, 7.3, 7.8, 2.9, 5.0)T ≤ x ≤ (3.6, 0.8, 28.0, 8.3, 8.3, 3.9, 5.5)T [1] Bahriye Akay and Dervis Karaboga. Artificial bee colony algorithm for large-scale problems and 5. RESULTS engineering design optimization. Journal of Intelligent The HCS-SA was applied to solve the design optimization Manufacturing, 23(4):1001–1014, 2012. problems, which were described in the previous section. To [2] Adil Baykaso˘ glu and Fehmi Burcin Ozsoydan. provide for a fair comparison with the literature, the number Adaptive firefly algorithm with chaos for mechanical of function evaluations was set to 50000, as advised in [2], design optimization problems. Applied Soft where the authors determined, that such a number is an Computing, 36:152–164, 2015. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 59 Table 1: Results obtained by the HSA-CS on the four design optimization problems. Problem min max mean md std Welded beam 1.724852309 1.724852309 1.724852309 1.724852309 0 Pressure vessel 6059.714 6410.087 6095.32 6059.714 88.270 Speed reducer 2996.218 2996.218 2996.218 2996.218 0 Spring design 0.01266523 0.0129087 0.01269661 0.01267089 5.402618 *10e−5 Table 2: Comparison with state-of-the-art. Welded beam Method min max mean std Gandomi et al [7] 1.7312 2.3455793 1.8786560 0.2677989 Akay et al.[1] 1.724852 – 1.741913 0.031 Brajevic et al. [3] 1.724852 – 1.724853 0.0000017 Baykasoglu et al. [2] 1.724852 1.724852 1.724852 0 This study 1.724852309 1.724852309 1.724852309 0 Pressure vessel Method min max mean std Gandomi et al [6] 6059.714 6495.347 6447.736 502.693 Akay et al.[1] 6059.714736 – 6245.308144 205.00 Brajevic et al. [3] 6059.714335 – 6192.116211 204 Baykasoglu et al. [2] 6059.71427196 6090.52614259 6064.33605261 11.28785324 This study 6059.714 6410.087 6095.32 88.270 Speed reducer Method min max mean std Gandomi et al [6] 3000.9810 3009 3007.1997 4.9634 Akay et al.[1] 2997.058412 – 2997.058412 – Brajevic et al. [3] 2994.471066 – 2994.471072 0.00000598 Baykasoglu et al. [2] 2996.372698 2996.669016 2996.514874 0.09 This study 2996.218 2996.218 2996.218 0 Spring design Method min max mean std Gandomi et al [7] 0.01266522 0.0168954 0.01350052 0.001420272 Akay et al.[1] 0.012665 – 0.012709 0.012813 Brajevic et al. [3] 0012665 – 0.012683 0.00000331 Baykasoglu et al. [2] 0.0126653049 0.0000128058 0.0126770446 0.0127116883 This study 0.01266523 0.0129087 0.01269661 5.402618*10e−5 [3] Ivona Brajevic and Milan Tuba. An upgraded artificial Applications, 22(6):1239–1255, 2013. bee colony (abc) algorithm for constrained [8] Uroš Mlakar, Iztok Fister Jr., and Iztok Fister. Hybrid optimization problems. Journal of Intelligent self-adaptive cuckoo search for global optimization. Manufacturing, 24(4):729–740, 2013. Swarm and Evolutionary Computation, 29:47 – 72, [4] Radovan R Bulatović, Goran Bošković, Mile M 2016. Savković, and Milomir M Gašić. Improved cuckoo [9] Shyue-Jian Wu and Pei-Tse Chow. Genetic algorithms search (ics) algorthm for constrained optimization for nonlinear mixed discrete-integer optimization problems. Latin American Journal of Solids and problems via meta-genetic parameter optimization. Structures, 11(8):1349–1362, 2014. Engineering Optimization+ A35, 24(2):137–159, 1995. [5] JZ Cha and RW Mayne. Optimization with discrete [10] Xin-She Yang and Suash Deb. Cuckoo search via lévy variables via recursive quadratic programming: Part flights. In Nature & Biologically Inspired Computing, 2—algorithm and results. Journal of Mechanisms, 2009. NaBIC 2009. World Congress on, pages Transmissions, and Automation in Design, 210–214. IEEE, 2009. 111(1):130–136, 1989. [11] Xin-She Yang and Suash Deb. Multiobjective cuckoo [6] Amir Hossein Gandomi, Xin-She Yang, and search for design optimization. Computers & Amir Hossein Alavi. Cuckoo search algorithm: a Operations Research, 40(6):1616 – 1624, 2013. metaheuristic approach to solve structural Emergent Nature Inspired Algorithms for optimization problems. Engineering with computers, Multi-Objective Optimization. 29(1):17–35, 2013. [12] Chun Zhang and Hsu-Pin Wang. Mixed-discrete [7] Amir Hossein Gandomi, Xin-She Yang, Amir Hossein nonlinear optimization with simulated annealing. Alavi, and Siamak Talatahari. Bat algorithm for Engineering Optimization, 21(4):277–291, 1993. constrained optimization tasks. Neural Computing and StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 60 Weights Optimization in Statistical Machine Translation using Modified Genetic Algorithm Jani Dugonik University of Maribor, Faculty of Electrical Engineering and Computer Science jani.dugonik@um.si ABSTRACT logical evolution. The GA algorithm repeatedly modifies a Translations in a statistical machine translations are gen- population of individual solutions by relying on bio-inspired erated on the basis of statistical models. These models are operators such as mutation, crossover and selection. weighted, and different models’ weights gives different trans- lations. The problem of finding a good translation can be The main goal of this paper was to build two SMT sys- regarded as an optimization problem. One way to find good tems for the language pair English-Slovenian, and to im- translations is to find optimal models’ weights. In this paper prove translation quality with finding optimal weights using we present the usage of the genetic algorithm with roulette a modified genetic algorithm. The used translation error wheel selection to find the optimal models’ weights. Exper- metric was bilingual evaluation understudy (BLEU) [19]. iments were performed using well-known corpora and the most used translation metric in the SMT field. We com- The remainder of the paper is organized as follows. Section 2 pared the modified genetic algorithm with the basic genetic presents related work. In the Section 3 we will describe some algorithm and the state-of-the-art method. The results show background of the problem and in Section 4 we will describe improvement in the translation quality and are comparable the basic and modified GA algorithms. Experiments are to the related state-of-the-art method. presented in Section 5. We conclude this paper with Section 6 where we give our conclusion. Keywords Genetic Algorithm, Statistical Machine Translation, Weight 2. RELATED WORK Optimization, Roulette Wheel Selection The ability to optimize models’ weights according to a trans- lation error metric has become a standard assumption in 1. INTRODUCTION SMT, due to the wide-spread adoption of Minimum Error Machine translation (MT) can ease the work of a translator. Rate Training (MERT) [16, 3]. Authors in [16] analyzed The most studied and used MT method is the statistical various training criteria which directly optimize translation machine translation (SMT) [2]. SMT is based on statistical quality. These training criteria make use of an automatic methods which were originally used for translating single evaluation metrics. They describe a new algorithm for ef- words (word-based translation). Now they have progressed ficient training an unsmoothed error count. The results in to the level of translating sequences of words called phrases the paper show that significantly better results can often (phrase-based translation). Currently the most successful be obtained if the final evaluation criterion is taken directly SMT systems are based on phrase-based translation [20]. into account as part of the training procedure. Translations in SMT are generated on the basis of statisti- cal models. Each model is weighted, and different models’ The problems with MERT can be addressed through the use weights provide various translations, which can be evaluated of surrogate loss functions. The Margin Infused Relaxed Al- by translation error metrics. The problem of finding a good gorithm (MIRA) [23, 10, 9, 8, 13] employs a structured hinge translation can be regarded as an optimization problem. loss and is an instance of online learning. In order to im- The optimization can be done with models’ weights. There prove generalization, the average of all weights seen during are various methods for solving this optimization problem learning is used on unseen data. D. Chiang in [10] took ad- and in this paper we used a genetic algorithm (GA) [18]. vantage of MIRA’s online nature to modify each update to It is based on a natural selection process that mimics bio- better suit SMT. The cost is defined using a pseudo-corpus BLEU which tracks the n-gram statistics of the model-best derivations from the last few updates. This modified cost matches corpus BLEU better than Add-1 smoothing but also makes cost time-dependent. As far as we know, there is only one published method for tuning SMT based on EAs. In [11] authors used a basic differential evolution algorithm to see how evolutionary al- gorithms behave in the field of statistical machine transla- tion. The results were comparable to the state-of-the-art StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 61 methods. represent the more similar texts, however, no machine trans- lations will attain a score of 1. 3. BACKGROUND The first ideas of SMT were introduced in 1949 [24]. SMT 4. GENETIC ALGORITHM was re-introduced in the late 1980s and early 1990s by re- Encoding of chromosomes is one of the problems, when you searchers at IBM’s Thomas J. Watson Research Center [6, are starting to solve problem with GA. Encoding very de- 5, 7] and has contributed to the significant resurgence in in- pends on the problem. Our problem is to find optimal mod- terest in MT. Nowadays it is by far the most widely studied els’ weights. In our algorithm, vector of weights is defined MT method. individual ~ x = x1, x2, ..., xD where D is the dimension of the problem. The dimension D is the number of models’ The idea behind SMT comes from information theory. A weights. text is translated according to the probability distribution p(e|f ) where a string e in the target language is the trans- The initial population is consisted of Np individuals and is lation of a string f in the source language. generated randomly between min and max values. As seen in Algorithm 1, the simplest form of GA involves three types One approach to model the probability distribution p(e|f ) of operators: crossover, mutation, and selection. is to apply Bayes Theorem: The crossover operator uses a crossover probability (Cr ) to cross over randomly selected individuals ~ s1 and ~ s2 from the population to form a new individual (~ x) using the following p(e|f ) = p(f |e) · p(e) (1) equation: where the translation model p(f |e) is the probability that the source string f is the translation of the target string e, (s1 rand() < Cr, and the language model p(e) is the probability of seeing that x j j = (3) target string e. This decomposition is attractive as it splits s2 else. j the problem into the two subproblems. Finding the best translation e∗ is done by searching among all possible trans- where j is a value between 1 and D and rand() returns a lations E for the translation with the highest probability real value between 0 and 1. If no crossover was performed, using the following equation: the offspring x is an exact copy of one of the parents. The mutation operator uses a mutation probability (F ) to e∗ = arg max p(e|f ) = arg max p(f |e) · p(e) (2) mutate new offspring at each position using the following e∈E e∈E equation: Performing this search efficiently is the work of a MT de- ( coder that uses the foreign string, heuristics and other meth- xj + rand1() rand2() < F, ods to limit the search space and at the same time keeping xj = (4) xj else. acceptable quality. This trade-off between quality and time usage can also be found in speech recognition. A text is typ- ically translated sentence by sentence, but even this is not where j is a value between 1 and D and randr(), r = {1, 2}, enough. In SMT models are based on n-grams, where a n- returns a real value between 0 and 1. After the crossover gram is a sequence of n items from a given sequence of text. and mutation the weights can fall out of the interval [min, The statistical translation models were initially word based, max ]. but significant advances were made with the introduction of phrase based models. Language models are typically approx- The selection operator selects solutions from the newly cre- imated by smoothed n-gram models, and similar approaches ated population and the current population. Solutions with have been applied to the translation models, but there is better fitness survives into the next generation g. The end additional complexity due to different sentence lengths and condition is a maximum number of generations(G). word orders in the languages. Therefore there are more ad- vanced models that deal with these additional complexity. 4.1 Roulette Wheel Selection Phrase and word penalty models ensures that the transla- Because the basic GA selects from all solutions (individuals) tions/phrases are not too long or too short. Lexical reorder- in the population, we decided to use the roulette wheel (RW) ing model conditions reordering on the actual phrases. By selection [1] to speed up the process. The basic part of the limiting the reordering, we can speed up the decoder as well selection process is to stochastically select from one genera- as increase the translation quality. The translation quality is tion to create the basis of the next generation. The require- considered to be the correspondence between a machine and ment is that the fittest individuals have a greater chance of professional human (reference) translation. One of the first survival than weaker ones. This replicates nature in that metrics to achieve a high correlation with human judgments fitter individuals will tend to have a better probability of is the BLEU metric, and it is the more popular metric in survival and will go forward to form the mating pool for SMT. The BLEU metric always output a real-valued num- the next generation. Weaker individuals are not without a ber between 0 and 1. This value indicates how similar are chance. In nature such individuals may have genetic coding the machine and reference translations. Values closer to 1 that may prove useful to future generations. StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 62 Algorithm 1 Genetic Algorithm 5.1 Corpus Preparation 1: Initialization In our experiments we used English and Slovenian JRC- 2: Evaluate the initial population ACQUIS Multilingual Parallel Corpora [21]. In this corpora 3: for g = 1 to G do the sentences are aligned which means the first sentence from 4: for i = 1 to N p do the English text is the translation of the first sentence from 5: Crossover the Slovenian text and so on. We split each corpus in three 6: Mutation parts: train, tuning, and test sets. The train set was used to 7: Place newly generated individual in a new popu- train our SMT systems and consisted of 6,500 sentences or lation 184,072 words in English set and 158,768 words in Slovenian 8: end for set. The tuning set was used to optimize the two SMT 9: Selection systems and consisted of 500 sentences or 13,526 words in 10: end for English set and 12,128 words in Slovenian set. The test set was used to evaluate our SMT systems and consisted of 3,000 sentences or 86,145 words in English set and 76,879 words in Slovenian set. MODELS' WEIGHTS 5.2 Building the SMT systems To successfully build the SMT system, seen in Figure 1, we created models from the training set, described in the pre- vious subsection, and Moses toolkit [15]. Moses toolkit is SOURCE an open-source toolkit for SMT which contains the SMT MOSES TARGET TEXT DECODER TEXT decoder and a wide variety of tools for training, tuning and applying the system to many translation tasks. Using Moses toolkit we created language and translation models. The language model was a 5-gram model with improve Kneser- Ney smoothing using IRST language modeling (IRSTLM) toolkit [12]. The translation model was built using grow- MODELS diag-final-and alignment from GIZA++ [17]. Our SMT sys- tems were extended with four advanced models: distortion, lexalized reordering, word, and phrase penalty models. This gave us six models. Figure 1: SMT system. 5.3 Optimization Settings The following settings were used for the optimizations of both SMT systems: D = 14, min = -1, max = 1, Np = Instead of iterating over all solutions, we chose 50 % of the 15, G = 70, F = 0.5 and Cr = 0.7. We can see the tuning population P which will then be recombined and mutated, as process in the Figure 2. Input to tuning methods are the seen in Algorithm 2. First we calculate sum of all individu- tuning set, models and models’ weights, and the output are als’ fitness values. Then we calculatet value = sum∗rand(), the new models’ weights. where rand() returns a random value between 0 and 1. Af- ter that, we iterate over all the population P, and calculate 5.4 Results value. When the new value is lower or equal than zero, we return the current individual. Our experiments were based on experiments in [3]. Authors compared the old and new implementations of MERT and Algorithm 2 Roulette Wheel Selection if they are similarly effective. They also measured the com- putation time. In our experiments we compared the basic 1: Calculate value GA with GA with Roulette Wheel Selection (GA 2: for i = 1 to N p do RW ). Each of the optimization method (MERT, GA, GA 3: ~ ind = P RW ) was ran i one time, as in [3], and compared to each other. All three 4: value = value − f ( ~ ind) methods were tuned on the same system using the same tun- 5: if value ≤ 0 then ing corpus, and the BLEU scores are shown in Table 1. As 6: return ~ ind we can see, the BLEU scores for GA 7: end if RW are better than the basic GA, and comparable with MERT. From the Table 2 8: end for we can see the tuning time for each method where GARW is 50 % faster as the basic GA, and comparable with MERT. 5. EXPERIMENTS In this section we will describe the corpus preparation, how 5.5 Discussion we built the two SMT systems, and the optimization set- Since the optimization is a part of the training, both of them tings. For each method (baseline, MERT, GA, GARW ) we are done offline which means the tuning time does not af- got a file containing weights. The two SMT systems used fect the actual translating. The actual translating is done these weights to translate the test set. The translated sets online and the time to translate text depends on the number were then evaluated using the BLEU metric, as shown in of words. But usually one sentence is translated in 1 sec- Table 1. ond. The GARW method is computationally faster because StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 63 TUNING SET GA NEW MODELS GARW MERT MODELS' WEIGHTS MODELS' WEIGHTS Figure 2: Tuning process. We successfully built two SMT systems using JRC-Acquis Table 1: BLEU scores on test corpora. corpora for Slovenian-English language pair. We implemented BLEU (%) ↑ System the basic GA and added the Roulette Wheel Selection to Slovenian → English English → Slovenian speed up the process. We showed that using the Roulette MERT 33.18 23.34 Wheel Selection the tuning time was shortened while still GA 32.15 23.39 maintaining the comparable translation quality. For further GARW 33.19 23.49 research we can use more advanced EAs, such as jDE [4], L-SHADE [22], nature-inspired algorithms [14] to improve the translation quality and shorten the tuning time. Table 2: Tuning time on tuning set. System Time (minutes) 7. REFERENCES MERT 97 [1] O. Al Jadaan, L. Rajamani, and C. Rao. Improved GA 182 selection operator for ga. Journal of Theoretical & GARW 91 Applied Information Technology, 4(4), 2008. [2] T. F. Albat. US Patent 0185235, Systems and Methods for Automatically Estimating a Translation Time, 2012. it makes 50 % less evaluations than the basic GA. The cur- [3] N. Bertoldi, B. Haddow, and J.-B. Fouet. Improved rent difference is 1.5 hours but with much more larger sets Minimum Error Rate Training in Moses. ACL, pages the difference could be in 10 hours or even days. The BLEU 160–167, 2009. score represents the similarity between the machine trans- [4] J. Brest, S. Greiner, B. Boskovic, M. Mernik, and lated text and human translated text. At this moment it is V. Zumer. Self-adapting control parameters in impossible to achieve a BLEU score of 100 % because that differential evolution: A comparative study on would mean that the two texts are identical. Even human numerical benchmark problems. IEEE Trans. translators can not produce the same translations. Thats Evolutionary Computation, 10(6):646–657, 2006. why every % counts and the difference 1 % is actually a good improvement in the translation quality. [5] P. Brown, J. Cocke, S. D. Pietra, V. D. Pietra, F. Jelinek, J. D. Lafferty, R. L. Mercer, and P. Roosing. A statistical approach to machine 6. CONCLUSIONS translation. Computational Linguistics, pages 79–85, StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 64 1990. Evolutionary Computation, CEC 2014, Beijing, [6] P. Brown, J. Cocke, S. D. Pietra, V. D. Pietra, China, July 6-11, 2014, pages 1658–1665, 2014. F. Jelinek, R. L. Mercer, and P. Roosing. A statistical [23] T. Watanabe, J. Suzuki, H. Tsukada, and H. Isozaki. approach to language translation. Association for Online large-margin training for statistical machine Computational Linguistics, pages 71–76, 1988. translation. EMNLP-CoNLL, pages 764–773, 2007. [7] P. Brown, S. D. Pietra, V. D. Pietra, and R. Mercer. [24] W. Weaver. Translation. Machine Translation of The mathematics of statistical machine translation: Languages, 1955. parameter estimation. Computational Linguistics, pages 263–311, 1993. [8] C. Cherry and G. Foster. Batch Tuning Strategies for Statistical Machine Translation. NAACL, 2012. [9] D. Chiang, K. Knight, and W. Wang. 11,001 new features for statistical machine translation. HLT-NAACL, pages 218–226, 2009. [10] D. Chiang, Y. Marton, and P. Resnik. Online large-margin training of syntactic and structural translation features. EMNLP, pages 224–233, 2008. [11] J. Dugonik, B. Bošković, M. S. Maučec, and J. Brest. The usage of differential evolution in a statistical machine translation. In 2014 IEEE Symposium on Differential Evolution, SDE 2014, Orlando, FL, USA, December 9-12, 2014, pages 89–96, 2014. [12] M. Federico, N. Bertoldi, and M. Cettolo. IRSTLM: an open source toolkit for handling large scale language models. In INTERSPEECH 2008, 9th Annual Conference of the International Speech Communication Association, pages 1618–1621, 2008. [13] E. Hasler, B. Haddow, and P. Koehn. Margin Infused Relaxed Algorithm for Moses. The Prague Bulletin of Mathematical Linguistics, pages 69–78, 2011. [14] I. F. Jr., X.-S. Yang, I. Fister, J. Brest, and D. Fister. A brief review of nature-inspired algorithms for optimization. CoRR, abs/1307.4186, 2013. [15] P. Koehn, H. Hoang, A. Birch, C. Callison-Burch, M. Federico, N. Bertoldi, B. Cowan, W. Shen, C. Moran, R. Zens, C. J. Dyer, O. Bojar, A. Constantin, and E. Herbst. Moses: Open source toolkit for statistical machine translation. ACL Demo and Poster Session, 2007. [16] F. J. Och. Minimum Error Rate Training for Statistical Machine Translation. ACL, pages 160–167, 2003. [17] F. J. Och and H. Ney. Improved Statistical Alignment Models. In ACL, pages 440–447, 2000. [18] A. Otman and A. Jaafar. Article:a comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. International Journal of Computer Applications, 31(11):49–57, October 2011. Full text available. [19] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu. BLEU: a method for automatic evaluation of machine translation. ACL, pages 311–318, 2002. [20] L. Specia. Fundamental and New Approaches to Statistical Machine Translation, 2010. [21] R. Steinberger, B. Pouliquen, A. Widiger, C. Ignat, T. Erjavec, D. Tufis, and D. Varga. The JRC-Acquis: A Multilingual Aligned Parallel Corpus with 20+ Languages. LREC, 2006. [22] R. Tanabe and A. S. Fukunaga. Improving the search performance of SHADE using linear population size reduction. In Proceedings of the IEEE Congress on StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 65 StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference Ljubljana, Slovenia, 12 October 66 StuCoSReC University of Primorska Press www.hippocampus.si isbn 978-961-6984-37-9 Not for resale 9 789616 984379 Document Outline Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016 (Front Cover) Colophone Preface Contents Žiga Leber, Luka Horvat, Patrik Kokol ◆ Zaznavanje plagiatov s pomočjo n-gramov Tilen Škrinjar, Matej Trop, Filip Urh ◆ Detekcija jezika v besedilih s šumom Gregor Jurgec, Iztok Fister ◆ Stiskanje slik z algoritmi po vzorih iz narave Aleksandar Tošić, Matjaž Šuber ◆ A GPGPU Implementation of CMA-ES Iztok Fister jr., Iztok Fister ◆ Building visual domain-specific languages using the semiotic approach: A case study on EasyTime Iztok Fister jr., Uroš Mlakar, Janez Brest, Iztok Fister ◆ A new population-based nature-inspired algorithm every month: Is the current era coming to the end? Dušan Fister, Iztok Fister jr., Iztok Fister ◆ Visualization of cycling training Primož Bencak, Dušan Fister ◆ Izdelava klaviatur MIDI László Tóth ◆ Greedy Heuristics for the Generalized Independent Cascade Model Uroš Mlakar ◆ Hybrid Cuckoo Search for constraint engineering design optimization problems Jani Dugonik ◆ Weights Optimization in Statistical Machine Translation using Modified Genetic Algorithm