ii
eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra kybernetiky
Diplomová práce
Tvorba doprovodné hudební linky za vyuºití evolu£ních výpo£etních metod Bc. Karel Jalovec
Vedoucí práce:
Ing. Jan Drchal
Studijní program: Otev°ená informatika, navazující magisterský
Obor: Um¥lá inteligence
13. kv¥tna 2013
iv
v
Pod¥kování D¥kuji Martinu Kin£lovi za sestrojení programových knihoven na podporu mého projektu. Dále bych rád pod¥koval Ji°ímu Klémovi za cenné rady a mému vedoucímu práce Janu Drchalovi za podporu a trp¥livost.
vi
viii
Abstract In recent years, many interesting projects and research papers emerged in the eld of machine learning and music composition. The majority of these projects generated just simple, monophonic and short musical fragments (typically only several bars long). Only few of these projects dealt with composing complete pieces of music or their parts. These projects attempted to t in a genre de ned by a music database created manually (mostly jazz song databases were used). The aim of this thesis is to create a piece of software to generate music parts to accompany existing music pieces. Using evolutionary algorithms, this program can possibly discover interesting musical features in order to inspire musicians.
Abstrakt V posledních letech se v oblasti strojového u£ení a skládání hudby objevilo velké mnoºství zajímavých projekt· a odborných £lánk·. Z velké £ásti se v²ak jednalo o projekty generující pouze jednoduché, monofonní a krátké hudební úryvky (°ádov¥ n¥kolik takt·). Vzácn¥ji se strojov¥ komponovaly skladby nebo jejich úryvky tak, aby se ºánrov¥ podobaly databázi p°ipravené £lov¥kem (jednalo se p°edev²ím o jazz). Cílem práce je sestavit software, který generuje hudební doprovodné linky k jiº existujícím skladbám. Pouºití evolu£ních algoritm· umoº¬uje programu objevit zajímavé hudební postupy. Program tak m·ºe slouºit jako zdroj inspirace pro hudebníky.
ix
x
Obsah 1 Úvod 1.1 1.2 1.3
State of the art . . . . . . . . . . . . . . . D¥lení v sou£asnosti dostupného softwaru Popis pouºívaných technik . . . . . . . . . 1.3.1 Genetické algoritmy . . . . . . . . 1.3.2 Genetické programování . . . . . . 1.3.3 Neuronové sít¥ . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Popis aplikace jako celku . . . . . . . . . . . . . . . . . Paralelizace výpo£t· . . . . . . . . . . . . . . . . . . . Modul pro zpracování dat metodami shlukování . . . . 3.3.1 Reprezentace shluku . . . . . . . . . . . . . . . 3.3.2 Implementace algoritmu shlukování - k-medoid Datový formát MusicString . . . . . . . . . . . . . . . Popis individuála . . . . . . . . . . . . . . . . . . . . . 3.5.1 Genotyp . . . . . . . . . . . . . . . . . . . . . . Inicializace genetického algoritmu . . . . . . . . . . . . 3.6.1 Výpo£et matice vzdáleností . . . . . . . . . . . 3.6.2 Metrika pro výpo£et vzdálenosti dvou genotyp· 3.6.3 Shlukování a t°íd¥ní shluk· . . . . . . . . . . . Iterace evolu£ního algoritmu . . . . . . . . . . . . . . . 3.7.1 Vytvo°ení nové populace . . . . . . . . . . . . . 3.7.1.1 Selekce . . . . . . . . . . . . . . . . . 3.7.1.2 K°íºení . . . . . . . . . . . . . . . . . 3.7.1.3 Mutace . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
2 Analýza a návrh °e²ení 2.1
2.2 2.3 2.4
Popis pouºitých technik . . . . . . . 2.1.1 Shlukování obecn¥ . . . . . . 2.1.2 Pouºitý algoritmus shlukování Popis hlavních blok· aplikace . . . . B¥h aplikace . . . . . . . . . . . . . . Shrnutí . . . . . . . . . . . . . . . .
3 Realizace 3.1 3.2 3.3
3.4 3.5 3.6
3.7
xi
. . . . . .
. . . . . .
. . . . . .
1
1 2 3 3 5 7
11
11 12 15 16 17 17
19
19 20 22 23 23 24 25 27 31 32 32 33 34 35 35 37 39
xii
OBSAH
4 Testování 4.1 4.2 4.3
4.4
Kvalita implementovaného algoritmu shlukování (k-medoid) 4.1.1 Vliv selek£ního tlaku na velikost shluk· . . . . . . . Diverzita prototyp· shluk· . . . . . . . . . . . . . . . . . . Kvalita generovaných hudebních skladeb . . . . . . . . . . . 4.3.1 Jednodu²²í skladby . . . . . . . . . . . . . . . . . . . 4.3.1.1 Final Fantasy - To Zanarkand . . . . . . . 4.3.1.2 Final Fantasy - Adventure . . . . . . . . . . 4.3.2 Komplexní skladby . . . . . . . . . . . . . . . . . . . 4.3.2.1 Bon Jovi - Say it isn't so . . . . . . . . . . 4.3.2.2 Jazzový standard - Autumn leaves . . . . . 4.3.2.3 Aerosmith - Dream on . . . . . . . . . . . . Shrnutí výsledk· . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
41
41 42 43 46 46 46 47 49 49 51 51 53
5 Záv¥r
55
A Seznam pouºitých zkratek
61
B Kon gurace testovacího stroje
63
C Uºivatelská p°íru£ka
65
D Obsah p°iloºeného CD
71
Seznam obrázk· 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9
Schéma jednoduchého genetického algoritmu . P°íklad siln¥ typovaného stromu [21] . . . . . P°íklad k°íºení siln¥ typovaného stromu [21] . P°íklad mutace siln¥ typovaného stromu [21] . P°íklad Full metody generování strom· [21] . P°íklad Grow metody generování strom· [21] Abstraktní neuron [31] . . . . . . . . . . . . . P°íklady p°enosových funkcí [25] . . . . . . . P°íklad netriviální neuronové sít¥ [31] . . . . .
. . . . . . . . .
3 5 6 6 6 7 7 8 8
2.1 2.2 2.3 2.4
12 13 13
2.5 2.6 2.7 2.8
P°íklad hierarchického algoritmu shlukování [17] . . . . . . . . . . . . . . . . . P°íklad ideálního b¥hu algoritmu k-st°ed· [17] . . . . . . . . . . . . . . . . . . P°íklad uvíznutí algoritmu k-st°ed· [17] . . . . . . . . . . . . . . . . . . . . . P°íklad datového setu, se kterým mají základní algoritmy shlukování problém [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P°íklad ideálního spektrálního shlukování [18] . . . . . . . . . . . . . . . . . . P°íklad algoritmu COBWEB [18] . . . . . . . . . . . . . . . . . . . . . . . . . Struktura aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Struktura algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9
Vytvá°ení instance algoritmu shlukování . . . . . . . . . . . P°íklad notového ekvivalentu zápisu ve formátu MusicString Tabulka £íselných kód· vý²ek tón· [20] . . . . . . . . . . . . P°íklad popula£ního jedince evolu£ního algoritmu . . . . . . P°íklad slou£ení dvou po sob¥ jdoucích dob . . . . . . . . . P°íklad rozd¥lení doby . . . . . . . . . . . . . . . . . . . . . P°íklad obrácení dob v taktu . . . . . . . . . . . . . . . . . P°íklad jednobodového k°íºení . . . . . . . . . . . . . . . . . P°íklad dvoubodového k°íºení . . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
22 24 25 26 30 30 30 38 38
4.1 4.2 4.3 4.4 4.5 4.6
Distribuce jedinc· ve shlucích v závislosti na po£tu iterací . . . . . . Diverzita prototyp· (inicializace) - R.E.M. - Man on the moon . . . Diverzita prototyp· (inicializace) - Bon Jovi - Say it isn't so . . . . . Diverzita prototyp· (10 iterací) - R.E.M. - Man on the moon . . . . Diverzita prototyp· (10 iterací) - Bon Jovi - Say it isn't so . . . . . . Diverzita prototyp· (inicializace) - Final Fantasy 10 - To Zanarkand
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
42 43 43 44 44 45
xiii
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
14 14 15 16 17
xiv
SEZNAM OBRÁZK
4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17
Diverzita prototyp· (10 iterací) - Final Fantasy 10 - To Zanarkand P°íklad 1: Vygenerovaná hudební stopa - To Zanarkand . . . . . . . P°íklad 2: Vygenerovaná hudební stopa - To Zanarkand . . . . . . . P°íklad 3: Vygenerovaná hudební stopa - To Zanarkand . . . . . . . P°íklad 4: Vygenerovaná hudební stopa - Adventure . . . . . . . . . P°íklad 5: Vygenerovaná hudební stopa - Adventure . . . . . . . . . P°íklad 6: Vygenerovaná hudební stopa - Adventure . . . . . . . . . P°íklad 7: Vygenerovaná hudební stopa - Say it isn't so . . . . . . . P°íklad 8: Vygenerovaná hudební stopa - Say it isn't so . . . . . . . P°íklad 9: Vygenerovaná hudební stopa - Autumn leaves . . . . . . P°íklad 10: Vygenerovaná hudební stopa - Dream on . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
45 47 47 48 48 49 49 50 51 52 52
C.1 C.2 C.3 C.4 C.5 C.6 C.7 C.8
Na£tení vtupního souboru . . . . . . . Výb¥r hudební stopy . . . . . . . . . . Okno p°ehráva£e . . . . . . . . . . . . Inicializa£ní parametry . . . . . . . . . Parametry shlukování . . . . . . . . . Parametry vytvá°ení nových populací . Ohodnocení iniciální populace . . . . . Postup evolu£ního procesu . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
65 66 66 67 68 69 70 70
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
Seznam tabulek 1.1 1.2
Ukázka jednobodového k°íºení . . . . . . . . . . . . . . . . . . . . . . . . . . . Ukázka muta£ního operátoru . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 5
3.1 3.2
25
3.4
P°ehled symbol· ur£ujících délku hudební doby . . . . . . . . . . . . . . . . . P°ehled trvání inicializa£ního procesu s a bez vyuºití technik soub¥ºného programování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P°ehled trvání výpo£tu matice vzdáleností s a bez vyuºití technik soub¥ºného programování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pravd¥podobnosti výb¥ru k°íºících operátor· . . . . . . . . . . . . . . . . . .
32 37
4.1 4.2 4.3 4.4
Výsledky kvality shlukování - vliv velikosti populace . . . . . . . . . . . . . . Výsledky kvality shlukování - vliv volby interval· metriky . . . . . . . . . . . Výsledky kvality shlukování - vliv po£tu shluk· . . . . . . . . . . . . . . . . . P°ehled hodnot kriteriální funkce v inicializa£ním kroku pro vybrané skladby
41 41 42 46
3.3
xv
31
xvi
SEZNAM TABULEK
Kapitola 1
Úvod V posledních letech vzniklo velké mnoºství teoretických i praktických projekt· pouºívajících strojové u£ení pro ú£ely skládání hudebních d¥l. V¥t²ina t¥chto projekt· vyuºívá metody strojového u£ení bez moºnosti zásahu uºivatele. Mezi tyto metody je moºné za°adit neuronové sít¥, r·zné genetické algoritmy a metody genetického programování. Jediné kritérium vhodnosti generovaných hudebních stop je hodnotící ( tness) funkce navrºená programátorem, která ale uºivateli nedává volnost výb¥ru. Druhým extrémem je £ist¥ interaktivní p°ístup, který je ov²em náro£ný z £asového hlediska (hlavn¥ p°i pouºití algoritm· s velkými populacemi °e²ení). Cílem této práce je navrhnout algoritmus/program, který pracuje s velkými populacemi jedinc·. Ve velké populaci s vysokou diverzitou jedinc· je v¥t²í ²ance nalézt n¥jaký zajímavý hudební postup. To v²e p°i zachování výhod interaktivního ohodnocování a p°i sníºení £asu nutného k ohodnocení celé populace.
1.1
State of the art
Jedním z nejznám¥j²ích program· je GenJam [4] [5]. Tento program se p°edem nau£í charakteristické vlastnosti písn¥, kterou bude hrát. Po nau£ení je schopen za b¥hu improvizovat. Vyuºívá k tomu znalosti nau£ené p°edem a mikrofonní vstup (je tedy £áste£n¥ interaktivní). Dal²í takovýto program se jmenuje Impro-Visor [16]. Zde uºivatel pí²e vlastní skladby a má moºnost doplnit stávající skladbu za pomoci gramatik a predikce tak, jako by ji psal uznávaný jazzový hrá£. Na °ad¥ je program nazvaný MySong [34]. Tento program pomocí skrytých Markovských model· (HMM) generuje akordový doprovod ke zp¥vu. Posledním p°íkladem je NEAT Drummer [13]. Tento program pomocí neuronových sítí vytvá°í doprovodnou linku pro bicí nástroje. Podobných projekt· je celá °ada. Co v¥t²inu z nich spojuje je generování krátkých, monofonních úryvk·. Generování celých skladeb nebo doprovod· je ojedin¥lá záleºitost. Pouºité techniky jsou to, co naopak projekty rozli²uje. Je velice obtíºné stávající projekty exaktn¥ rozd¥lit do smysluplných skupin, které by vhodn¥ charakterizovaly jejich vlastnosti. P°esto je moºné alespo¬ rámcov¥ toto d¥lení nastínit [24]. 1
2
KAPITOLA 1.
1.2
ÚVOD
D¥lení v sou£asnosti dostupného softwaru
D¥lení dle typu pouºití • Variace na existující skladbu nebo motiv • Tvorba skladby podobající se p°edloze • Tvorba sól nebo improvizací k dané ²ablon¥ (je de nován rytmus a/nebo sled akord·)
D¥lení dle melodických a rytmických prvk· • Bere se v potaz rytmus i melodie sou£asn¥ • Bere se v potaz rytmus i melodie postupn¥ • Bere se v potaz pouze rytmus • Bere se v potaz pouze melodie
D¥lení dle pouºitých technik • Genetické algoritmy - [1] - Hudební linky jsou nej£ast¥ji reprezentovány jako °et¥zce nebo pole celých £ísel (pokud se auto°i snaºí extrahovat matematické vlastnosti skladeb nebo pokud se drºí speci kace tón· pro formát MIDI). • Genetické programování - [15] - Hudební linky jsou reprezentovány jako siln¥ typované stromy. Tato reprezentace je pro hudební linky velice vhodná, protoºe je uº na první pohled z°ejmá struktura skladby. Typováním uzl· stromu se de nuje hudební gramatika popisující pravidla pro tvorbu hudebních d¥l (vhodným navrºením této gramatiky lze £áste£n¥ popisovat r·zné hudební ºánry). • Markovské modely - [9] - Generování pravd¥podobnostními modely je vhodné p°i zaná²ení kreativity do algoritmu. • Neuronové sít¥ - [13], [22] - Neuronových sítí se pouºívá celá °ada typ·. Pro vyvíjení i ohodnocování lze pouºít sít¥ typu SOM a HSOM. Neuronová sí´ typu CPPN, trénovaná algoritmem NEAT se osv¥d£ila ke generování rytmiky hudebního doprovodu bicích nástroj·. Problémem v²ak z·stává fakt, ºe pro natrénování neuronových sítí je pot°eba rozsáhlá trénovací mnoºina. V porovnání s ostatními technikami i velké mnoºství £asu.
D¥lení dle zp·sobu ohodnocování vhodnosti generovaných skladeb • Interaktivní ohodnocování - Interaktivní zp·sob ohodnocování je technika, kdy vhodnost vygenerovaného °e²ení vyhodnocuje sám uºivatel. Jde o praktický zp·sob, pokud není k dispozici vhodná metrika. Tento postup je moºné zvolit i pokud je vhodné do procesu vytvá°ení °e²ení zanést osobní preference uºivatele. Nevýhodou je £asová náro£nost procesu ohodnocení.
1.3.
POPIS POUÍVANÝCH TECHNIK
3
• Automatizované ohodnocování - Je moºné vytvo°it tness funkci, která je schopná dob°e ohodnotit generované skladby. Navíc je moºné, p°i vhodném navrºení, zahrnout do této funkce i preference uºivatele, pop°ípad¥ pravidla jednotlivých ºánr·. Tato metoda v²ak p°edpokládá dobrou znalost hudební problematiky a hudebních pravidel pro jednotlivé ºánry. K ohodnocování °e²ení není nutný zásah uºivatele. • áste£n¥ interaktivní ohodnocování - Tento p°ístup je kombinací obou jiº zmín¥ných technik. áste£né interaktivní ohodnocování m·ºe mít mnoho podob a vyuºití. Pokud proces iterativn¥ vylep²uje °e²ení, je moºné uºivateli nabídnout manuální ohodnocení kaºdou n-tou iteraci. Dal²ím p°ístupem je brát ohodnocení uºivatele jako £áste£ný faktor a kombinovat ho s dostupnou evalua£ní funkcí.
1.3 1.3.1
Popis pouºívaných technik Genetické algoritmy
Genetické algoritmy jsou podmnoºinou t°ídy evolu£ních algoritm·. Genetické algoritmy vyuºívají analogie s biologickým procesem evoluce. V p°írod¥ existují populace s jedinci, kte°í mezi sebou bojují o právo se reprodukovat. Schopnost jedince p°eºít, p°izp·sobit se prost°edí, vybojovat si své místo ve spole£nosti £i schopnost najít partnera vhodného k rozmnoºení, je dána jeho genetickou výbavou. Z dlouhodobého hlediska mají v¥t²í ²anci na p°eºití jedinci s lep²í genetickou výbavou. Stejného principu vyuºívají i genetické algoritmy. Na rozdíl od standardních algoritm· nepracují s jedním °e²ením problému, ale s celou populací. Vygenerovaná °e²ení se postupem £asu zlep²ují s tím, jak postupuje evoluce dané populace. K vylep²ování dochází stejným zp·sobem jako v p°írod¥. Populace se obohacuje o nová °e²ení získaná reprodukcí jiº existujících °e²ení. Nov¥ generovaná °e²ení jsou podrobována mutacím pop°ípad¥ jsou vy°azena, kdyº nejsou dostate£n¥ vhodná. Typické schéma jednoduchého genetického algoritmu je uvedené na následujícím obrázku.
Obrázek 1.1: Schéma jednoduchého genetického algoritmu
4
KAPITOLA 1.
ÚVOD
Iniciální populace typicky sestává z náhodn¥ vygenerovaných °e²ení. Neº je moºné nad jedinci n¥jak usuzovat, je pot°eba ohodnotit jejich vhodnost. K tomu slouºí tzv. tness funkce. Tato funkce kaºdému jedinci ur£í jeho vhodnost k °e²ení problému. Na základ¥ hodnoty této funkce pak probíhá proces selekce. Selekcí je my²len proces výb¥ru jedinc·, kte°í se budou reprodukovat do nové populace. Metod, jak provád¥t selekci, je celá °ada. Zmíním tedy jen ty nejznám¥j²í.
• Náhodný výb¥r - jedinci ur£ení k reprodukci se vybírají náhodn¥, nezávisle na hodnot¥ jejich tness funkce. • O°ezávání - p°i této metod¥ jsou jedinci se°azeni podle hodnoty jejich tness funkce a podle ur£itého kritéria je populace rozd¥lena na dv¥ £ásti. ást s jedinci s nízkou tness je zahozena. ást s jedinci s vy²²ími hodnotami tness funkce je ur£ena k výb¥ru a k reprodukci podle n¥jakého deterministického £i stochastického pravidla. • Ruletové kolo - p°i tomto zp·sobu výb¥ru je sestrojena pomyslná ruleta, na které kaºdý jedinec dostane podíl adekvátní jeho podílu na celkové hodnot¥ tness funkce. • Turnajový výb¥r - vybrána je vºdy náhodn¥ podmnoºina populace s alespo¬ dv¥ma prvky. Teprve z této podmnoºiny se vybírá podle nejlep²í hodnoty tness funkce. Pojem, který se selekcí úzce souvisí je elitismus. Elitismem je zaji²t¥no, ºe jedinci s nadpr·m¥rn¥ vhodnou genetickou výbavou jsou do nové populace zahrnuti automaticky, aniº by museli podstupovat proces selekce. V moment¥, kdy selek£ní proces vybere rodi£e (jedince ur£ené k reprodukci) nastupují na °adu perturba£ní operátory. To jest k°íºení a mutace. K°íºení je analogický proces k reprodukci. V p°írod¥ si dva jedinci vym¥ní £ást svého genetického kódu. Stejn¥ tak tomu je v p°ípad¥ reprodukce jedinc· genetického algoritmu. Nejjednodu²²ím typem k°íºení je jednobodové k°íºení. P°i tomto zp·sobu se ur£í jeden bod v chromozomu rodi£e a chromozom se rozd¥lí na dv¥ £ásti. Jednu £ást si potom vym¥ní s druhým rodi£em. Tímto vzniknou dva jiní jedinci - potomci. Volbou vícebodového k°íºení je moºné k°íºit najednou i více neº dva jedince. Jednobodové k°íºení je ilustrováno na p°íkladu. Vybraní jedinci Potomci
1001100|1010 10011001101
1110100|1101 11101001010
Tabulka 1.1: Ukázka jednobodového k°íºení Takto pozm¥n¥ní jedinci podstupují proces mutace. Mutace je d·leºitá k udrºení diverzity populace. M·ºe se zdát, ºe k°íºení samotné vytvá°í dosti odli²né jedince, ale nemusí tomu tak nutn¥ být. Populace s chudou genetickou výbavou stagnuje a uvízne v lokálním optimu. Mutacemi se lehce pozm¥ní genetický kód individuála a tím se zv¥t²í diverzita v populaci a pravd¥podobnost, ºe se populace posune sm¥rem k lep²ímu °e²ení. Mutace je ukázána v tabulce 1.2. Takto nov¥ vybudovaná populace nahrazuje populaci p°ede²lou a vstupuje do dal²í iterace evolu£ní smy£ky. Evoluce probíhá, dokud není nalezen jedinec °e²ící daný problém, nebo neprob¥hne p°edem de novaný po£et iterací.
1.3.
5
POPIS POUÍVANÝCH TECHNIK
Jedinec Mutovaný jedinec
100'1'1001010 100'0'1001101
Tabulka 1.2: Ukázka muta£ního operátoru
1.3.2
Genetické programování
Genetické programování [23] je principiáln¥ velice podobné genetickým algoritm·m. Marginálním rozdílem je pouºití nelineárních chromozom· (typicky stromy nebo grafy). Ve v¥t²in¥ p°ípad· se jako chromozomy pouºívají siln¥ typované stromy popsané gramatikou. Siln¥ typovaný strom je strom sloºený z terminálních a neterminálních (funk£ních) uzl· s de novanou aritou. Terminální uzel je elementární výraz, který uº nemá a nem·ºe mít ºádné potomky. Neterminální uzel je funk£ní symbol de nované arity a jeho potomci mohou být jak terminální, tak neterminální uzly. K tomuto problému se vztahuje pojem uzav°enosti. To znamená, ºe jakýkoli funk£ní symbol, vyskytující se v mnoºin¥ funk£ních symbol· m·ºe jako parametr p°ijímat jakýkoli funk£ní symbol z mnoºiny funk£ních symbol·. P°íkladem m·ºe být siln¥ typovaný strom na obrázku 1.2.
Obrázek 1.2: P°íklad siln¥ typovaného stromu [21]
Popula£ní jedinci genetického programování, stejn¥ jako popula£ní jedinci genetického algoritmu podstupují proces selekce, k°íºení a mutace. Rozdíl je ve velikosti chromozom·. V p°ípad¥ genetického algoritmu mají chromozomy v²ech jedinc· typicky stejnou (nebo velice podobnou) velikost. Genetické programování tím, ºe vyvíjí stromy/grafy, m·ºe dosáhnout diametrálních rozdíl· ve velikosti chromozom· r·zných jedinc·. Proto je pot°eba upravit selek£ní mechanismus tak, aby preferoval °e²ení dle pot°eby (typicky se preferují men²í stromy/grafy p°ed t¥mi v¥t²ími). Mechanismus mutace a k°íºení probíhá velice podobn¥ jako u genetických algoritm·. Nyní v²ak jde o operace se stromy nebo s grafy. Typickým p°íkladem k°íºení je vým¥na podstrom·. Mohou být de novány r·zné pravd¥podobnosti k°íºení pro r·zné typy uzl·, tedy n¥které funk£ní symboly se mohou stát bodem k°íºení s vy²²í pravd¥podobností neº jiné, nebo naopak. Muta£ní operátor je, v kontextu strom·, nahrazení vybraného uzlu podstromem vygenerovaným stejným zp·sobem, jako iniciální populace strom·. P°íklady k°íºení a mutace jsou uvedeny na obrázcích 1.3 a 1.4.
6
KAPITOLA 1.
ÚVOD
Obrázek 1.3: P°íklad k°íºení siln¥ typovaného stromu [21]
Obrázek 1.4: P°íklad mutace siln¥ typovaného stromu [21]
V souvislosti s náhodným generováním podstrom· místo mutovaných uzl· vyvstává otázka algoritm· ke generování strom·. Nej£ast¥ji se pouºívají t°i p°ístupy.
• Full method Tato metoda vytvo°í strom, který má v²echny v¥tve stejn¥ dlouhé. P°íklad stromu vygenerovaného touto metodou je na obrázku 1.5. • Grow method Metoda vytvá°í stromy s délkou v¥tví omezenou konstantou, ale ne nutn¥ musí mít v²echny v¥tve stejnou délku. P°íklad stromu vygenerovaného touto metodou je na obrázku 1.6. • Ramped half-and-half P°ístup kombinující ob¥ vý²e uvedené metody, p°i£emº je kaºdou vý²e uvedenou metodou vygenerována polovina populace.
Obrázek 1.5: P°íklad Full metody generování strom· [21]
1.3.
POPIS POUÍVANÝCH TECHNIK
7
Obrázek 1.6: P°íklad Grow metody generování strom· [21]
1.3.3
Neuronové sít¥
Neuronové sít¥ jsou dal²ím p°íkladem evolu£ního výpo£etního modelu. Vznikly jako pokus o modelování nervového systému a jeho schopnosti zpracovávat informace. Nervový systém ºivého tvora je sloºen z obrovského mnoºství navzájem propojených bun¥k. Tyto bu¬ky tvo°í komplexní hierarchickou strukturu schopnou zpracovávat velké mnoºství dat. Z biologického pohledu je neuron komplexní jednotka schopná p°ijímat, zpracovávat a vysílat informace. Z pohledu po£íta£ové v¥dy jde o funkci (v¥t²inou pom¥rn¥ jednoduchou). Schéma jednoduchého abstraktního neuronu [31] je uvedeno na následujícím obrázku.
Obrázek 1.7: Abstraktní neuron [31]
Neuron p°ijímá informace z okolí pomocí vstup· (levá strana neuronu) a zpracovanou informaci posílá dál pomocí výstupu (pravá strana neuronu). Vstupní vektor X = [x1 , x2 , ..., xN ] je informace, kterou vektor p°ijímá od okolí. Váhový vektor W = [w1 , w2 , ..., wN ] modi kuje vstupní vektor. Vnit°ek neuronu si lze p°edstavit jako primitivní funkci, která je aplikována na vstupní vektor. R·zné modely um¥lých neuronových sítí se li²í p°edev²ím druhem pouºité aktiva£ní funkce. P°íklady, jak m·ºe p°enosová (aktiva£ní) funkce vypadat, jsou uvedeny na obrázku 1.8. Komplexní neuronová sí´ vzniká propojením takovýchto jednoduchých funk£ních blok·, které dohromady vytvá°í sloºit¥j²í funkce. Zp·sob propojení (topologie) má zásadní vliv na funkcionalitu sít¥. P°íklad netriviální neuronové sít¥ je uveden na obrázku 1.9. Z obrázku je patrné, ºe takováto sí´ se, jako celek, tvá°í, jako komplexní funkce Φ se t°emi vstupními parametry (x, y, z).
8
KAPITOLA 1.
ÚVOD
Obrázek 1.8: P°íklady p°enosových funkcí [25]
Obrázek 1.9: P°íklad netriviální neuronové sít¥ [31]
Práci um¥lé neuronové sít¥ je moºné rozd¥lit do dvou fází - u£ení a vybavování. U£ení neuronových sítí (v nejjednodu²²ím p°ípad¥) spo£ívá v modi kaci váhových vektor· jednotlivých neuron·. K tomu je pot°eba mnoºina trénovacích dat a jeden z velkého mnoºství u£ících algoritm·. U£ící algoritmy se dají rozd¥lit do dvou základních t°íd.
• U£ení s u£itelem Tento p°ístup funguje na základ¥ zp¥tné vazby. Síti je p°edloºen vzor. Výstup sít¥ je porovnán s kontrolním poºadovaným výstupem. Porovnáním je zji²t¥na odchylka a na základ¥ této odchylky jsou modi kovány parametry sít¥. Trénovací mnoºina je p°edkládána tak dlouho, dokud chyba sít¥ neklesne pod poºadovanou hranici. • U£ení bez u£itele (samoorganizace) P°i tomto zp·sobu u£ení není znám správný výstup sít¥. Sí´ si sama t°ídí vzorky podle jejich charakteristických vlastností. Po nau£ení z trénovací mnoºiny je moºné pouºít sí´ k vybavování. Neuronové síti je na vstup p°edloºen vzor a po propagaci vzoru skrz sí´ je na její výstupní vrstv¥ výstup v poºadovaném tvaru (zp·sob výstupu závisí na povaze problému).
1.3.
POPIS POUÍVANÝCH TECHNIK
9
Z vý²e uvedených pojm· a termín· je moºné de novat pojem model neuronové sít¥[31]. Model je de nován t°emi parametry:
• Strukturou jednotlivých uzl· (neuron·) • Topologií sít¥ • U£ícím algoritmem Na základ¥ modelu je moºné kategorizovat um¥lé neuronové sít¥. Toto d¥lení je moºné realizovat dle r·zných kritérií. V souvislosti s typem °e²ených úloh, typem vstupních dat a strukturou neuron· je moºné sít¥ d¥lit na klasi ka£ní[30][26] (diskrétní vstupní data, klasi kace dat do t°íd) a regresní[26] (reálná vstupní data, aproximace funkcí). Podle topologie lze rozd¥lit sít¥ na jednovrstvé[33] (single-layer) nebo vícevrstvé[32] (multi-layer), rekurentní[10] (recurrent) nebo dop°edné[11] (feed-forward). Od pouºité topologie se odvíjí i pouºitý u£ící algoritmus.
10
KAPITOLA 1.
ÚVOD
Kapitola 2
Analýza a návrh °e²ení Aplikace je vytvo°ena v jazyce Java (verze jdk 1.7.0_15). Tento jazyk byl vybrán z d·vodu existence vhodných knihoven umoº¬ujících vysokoúrov¬ovou práci s hudebním formátem MIDI. Konkrétn¥ je vyuºívána upravená verze knihovny JFugue [19] a její datový formát JFugue MusicString [20] je pouºitý jako interní datový formát této aplikace. Ke generování obrázk· notového zápisu byl pouºit program TuxGuitar (http://tuxguitar.herac.com.ar/).
2.1
Popis pouºitých technik
Na úvod budou p°edstaveny a od·vodn¥ny techniky pouºité v této práci. V následující £ásti jsou jednotlivé techniky podrobn¥ji vysv¥tleny. Práce se zam¥°uje na vyuºití £áste£n¥ interaktivního genetického algoritmu s vyuºitím mechanismu shlukování. V p°edchozím textu bylo uvedeno, ºe interaktivní ohodnocování je £asov¥ náro£ná (z hlediska uºivatele) operace. Z tohoto d·vodu je do programu zakomponován algoritmus shlukování, který rozd¥lí populaci individuál· (skladeb) na disjunktní podmnoºiny skladeb, v rámci podmnoºiny vzájemn¥ se podobajících. Z kaºdé podmnoºiny se následn¥ interaktivn¥ ohodnocuje pouze reprezentant podmnoºiny. Tím dojde ke zna£né redukci £asu nutného k ohodnocení celé populace. Nyní podrobn¥ji k jednotlivým technikám. Jednoduchý genetický algoritmus [12] je algoritmus simulující evolu£ní proces vyvíjením populace kandidátních °e²ení. Na úvod se algoritmu p°edloºí populace zpravidla náhodných °e²ení. Ve smy£ce se posléze prvky (individuály) ohodnotí pomocí tness funkce. Podle ohodnocení a selek£ní funkce se vyberou rodi£ovské individuály. Z rodi£ovských individuál· se pomocí perturba£ních operátor· (mutace a k°íºení) vytvo°í nová populace. Tato smy£ka probíhá dokud hodnota nejlep²ího individuála (ve smyslu nejlep²í hodnoty tness funkce) nep°ekro£í de novanou prahovou hodnotu nebo dokud není nalezeno vhodné °e²ení problému. Takto popsaný algoritmus je velice jednoduchý. Ke zlep²ení jeho výsledk· je moºné pouºít °adu vylep²ení podle typu °e²ené úlohy. Interaktivní genetický algoritmus provádí ohodnocování prvk· populace za asistence uºivatele, který manuáln¥ ohodnotí vhodnost inidividuál·. Algoritmus shlukování[7] je algoritmus pouºívaný p°eváºn¥ na vytvá°ení struktur v neanotovaných datech. Obecn¥ algoritmus na základ¥ de nované metriky seskupuje nebo rozd¥luje data do shluk·. Shluk je oblast s vysokou hustotou pravd¥podobnostního rozloºení. Cílem je 11
12
KAPITOLA 2.
ANALÝZA A NÁVRH EENÍ
rozd¥lit data do shluk· tak, aby kaºdý prvek pat°il práv¥ do jednoho shluku, prvky si byly podobné v rámci shluku a rozdílné mezi shluky. 2.1.1
Shlukování obecn¥
Shlukování je metoda strojového u£ení (bez u£itele), která se pouºívá p°eváºn¥ k objevování t°íd v neanotovaných datech. Cílem je rozd¥lit data do disjunktních podmnoºin - shluk· (oblastí s vy²²í hustotou pravd¥podobnostního rozd¥lení)[17]. Shluky jsou tvo°eny tak, aby si data v rámci shluku byla podobná, data v r·zných shlucích si nebyla podobná a aby kaºdý datový bod pat°il práv¥ do jednoho shluku. Vstupními parametry algoritm· shlukování jsou typicky trénovací data, vzdálenostní funkce (metrika) a optimaliza£ní kritérium. Neznámé parametry jsou po£et shluk· (t°íd) v datech, p°i°azení dat do shluk· (rozklad) a prototypy (typi£tí reprezentanti shluk·). Metody shlukování lze rozd¥lit na dva základní p°ístupy [17]:
• Nehierarchické shlukování Tvo°í rozklad p°ímo na základ¥ globálního kritéria optimality. • Hierarchické shlukování Vytvá°í hierarchické struktury v datech. Pouºívají pouze lokální kritérium optimality. P°íklad hierarchického shlukování si je moºné prohlédnout na obrázku 2.1. Lze je je²t¥ rozd¥lit podle sm¥ru vytvá°ení shluk·.
Shora dol· - aglomerativní Seskupuje data do v¥t²ích celk· - shluk·. Kaºdá instance je nejprve shlukem. Algoritmus iterativn¥ spojuje nejpodobn¥j²í shluky.
Zdola nahoru - divizivní Iterativn¥ d¥lí mnoºiny dat na men²í celky. K tomu pot°ebuje interní algoritmus shlukování.
Obrázek 2.1: P°íklad hierarchického algoritmu shlukování [17]
2.1.
POPIS POUITÝCH TECHNIK
13
Typickým a nejznám¥j²ím p°edstavitelem nehierarchického algoritmu shlukování je algoritmus k-st°ed· (k-means). Algoritmus funguje následujícím zp·sobem[17]:
00 1) 2) 3) 4)
Náhodn¥ inicializuj st°edy shluk· Kaºdý z p°íklad· p°i°a¤ k nejbliº²ímu st°edu P°epo£ítej st°edy shluk· Opakuj 2 a 3 dokud se m¥ní st°edy shluk·
P°íklad ideálního b¥hu algoritmu k-st°ed· si je moºné prohlédnout na obrázku 2.2. Zám¥rn¥ jde o ideální b¥h, protoºe jednou z vlastností tohoto algoritmu je citlivost na iniciální nastavení. K-st°ed· je p°íkladem hladového algoritmu. Hladový algoritmus zaru£uje konvergenci (v¥t²inou velice rychlou), ov²em ne vºdy ke globálnímu optimu. P°íklad konvergence k lokálnímu optimu je uveden na obrázku 2.3.
Obrázek 2.2: P°íklad ideálního b¥hu algoritmu k-st°ed· [17]
Obrázek 2.3: P°íklad uvíznutí algoritmu k-st°ed· [17]
14
KAPITOLA 2.
ANALÝZA A NÁVRH EENÍ
Algoritmy shlukování zmín¥né vý²e mají jednu zásadní nevýhodu. Tou je, ºe p°edjímají shluky ur£itého tvaru. Dokáºí se velice ²patn¥ vyrovnat s daty, které není moºné lineárn¥ odd¥lit. P°íklad datového setu[18], s kterým mají základní algoritmy shlukování problém je uveden na obrázku 2.4.
Obrázek 2.4: P°íklad datového setu, se kterým mají základní algoritmy shlukování problém [18]
e²ením je transformace p°íznakového prostoru a pouºití pokro£ilého algoritmu shlukování. Tato transformace je problémov¥ závislá. Algoritmus shlukování je ale uº problémov¥ nezávislý a probíhá v transformovaném prostoru. Tato metoda shlukování se jmenuje spektrální shlukování a lze ji za°adit mezi nehierarchické metody. P°íklad výsledku spektrálního shlukování je uveden na obrázku 2.5.
Obrázek 2.5: P°íklad ideálního spektrálního shlukování [18]
2.1.
POPIS POUITÝCH TECHNIK
15
Posledním algoritmem shlukování, který je zmín¥n, je algoritmus konceptuálního shlukování[18]. Tento algoritmus se pouºívá ke shlukování objekt· sdílejících n¥jakou vlastnost (jde o zobecn¥ní pojmu podobnosti). Tím, ºe generuje shluky na základ¥ vlastností, automaticky generuje i popis shluk· a hierarchie pojm·. Tedy je moºné tento algoritmus za°adit mezi hierarchické metody shlukování. Typickým p°edstavitelem konceptuálního shlukování je algoritmus COBWEB[37] a jeho p°íklad si je moºné prohlédnout na obrázku 2.6.
Obrázek 2.6: P°íklad algoritmu COBWEB [18]
2.1.2
Pouºitý algoritmus shlukování
Z vý²e zmín¥ných algoritm· shlukování se nejpouºiteln¥ji jeví algoritmus k-st°ed·[8]. P°ímé porovnání dvou hudebních stop, bez transformací a s vhodnou metrikou, není sloºitá operace. Problémem je, ºe k-st°ed· vybírá jako reprezentanty shluk· i datové body, které se v originálním datovém setu nevyskytují. Existuje v²ak modi kace algoritmu k-st°ed·, která tento problém °e²í. Touto modi kací je algoritmus k-medoid[36]. Tento algoritmus vybírá jako reprezentanta shluku takový bod, aby minimalizoval pr·m¥rnou vzdálenost ke v²em prvk·m shluku - medoid. Medoid je objekt, který je analogií k pr·m¥ru nebo centroidu, ale vºdy je to existující prvek nacházející se v datové mnoºin¥. Algoritmus k-medoid existuje ve více implementacích.
16
KAPITOLA 2.
ANALÝZA A NÁVRH EENÍ
Pro daný problém byla zvolena implementace PAM (Partitioning Around Medoids). Pseudokód algoritmu je následující:
1. 2. 3. 4. 5. 6. 7.
Náhodn¥ zvol k bod· jako medoidy Kaºdý zbylý bod p°i°a¤ k nejbliº²ímu medoidu (pomocí vhodné metriky). Pro kaºdý medoid M Pro kaºdý ne-medoid O Proho¤ M s O a spo£ti hodnotu konfigurace (p°es v²echny shluky). Vyber konfiguraci s nejniº²í cenou. Opakuj dokud dochází ke zm¥n¥ medoid·.
2.2
Popis hlavních blok· aplikace
Celkový návrh aplikace je zaloºen na architektu°e MVC [3]. Projekt sestává z n¥kolika £ástí: jádra (zaji²´uje hlavní funkcionalitu programu), gra ckého uºivatelského rozhraní (nastavování parametr· a promítání výsledk·), kontroléru (s jeho pomocí uºivatelské rozhraní ovládá chod jádra) a modulu shlukování (samostatná £ást zaji²´ující mechanismus shlukování). Strukturu si je moºné prohlédnout na obrázku 2.7.
Obrázek 2.7: Struktura aplikace
2.3.
2.3
17
B
H APLIKACE
B¥h aplikace
Práce s aplikací probíhá následovn¥: uºivatel si vybere soubor se vstupními daty (formát je omezen upravenou knihovnou JFugue) a nastaví parametry nutné pro chod algoritmu. Následn¥ dojde k vytvo°ení referen£ního individuála a iniciální populace. Iniciální populace se pomocí algoritmu shlukování rozd¥lí na n¥kolik podmnoºin (po£et je stanoven p°edem uºivatelem), které se set°ídí podle podobnosti s referen£ním individuálem. Pouze reprezentanti t¥chto podmnoºin jsou uºivateli nabídnuti k poslechu, coº redukuje £as pot°ebný k interaktivnímu ohodnocování celé populace (která m·ºe £ítat stovky aº tisíce individuál·). Uºivatel m·ºe podle svých preferencí set°ídit podmnoºiny manuáln¥. Nová populace se vytvá°í na základ¥ po°adí podmnoºin, aby re ektovala poºadavky a preference uºivatele. Dále probíhají iterace evolu£ního algoritmu nezávisle na uºivateli. Po stanoveném po£tu iterací je op¥t nabídnuta moºnost poslechu a ohodnocení. Uºivatel má moºnost b¥hem interaktivního ohodnocování vzniklé individuály exportovat. Algoritmus nekon£í svou £innost po xním po£tu iterací nebo po dosaºení ur£ité hodnoty tness funkce, jako standardní evolu£ní algoritmus, ale pokra£uje v £innosti tak dlouho, jak uºivatel poºaduje.
Obrázek 2.8: Struktura algoritmu
2.4
Shrnutí
V této kapitole byl uveden návrh aplikace, v hrubých rysech p°edstaven chod programu a základní £ásti, z kterých se aplikace skládá. Konkrétní implementace algoritm· je p°edm¥tem následující kapitoly.
18
KAPITOLA 2.
ANALÝZA A NÁVRH EENÍ
Kapitola 3
Realizace Tato kapitola se zabývá konkrétními implementa£ními podrobnostmi jednotlivých algoritm· a £ástí aplikace. Nejprve je popsána funkcionalita aplikace jako celku a poté její jednotlivé £ásti.
3.1
Popis aplikace jako celku
Jak uº bylo zmín¥no v p°edchozí kapitole, aplikace je zaloºena na návrhovém vzoru MVC[3]. Obsahuje celkem £ty°i komponenty. Jádro (výkonná £ást aplikace), modul pro shlukování (pomocná komponenta jádra), uºivatelské rozhraní (nastavování parametr· a prezentace výsledk·) a kontrolér, kterým je jádro informováno o akcích uºivatele. Funkcionalitu lépe nastíní kód, který se vykoná p°i spu²t¥ní aplikace.
//jádro je nezávislá, výkonná £ást aplikace Core core = new Core(...parametry...); //komponenta uºivatelského rozhraní MainWindow mainWindow = new MainWindow(...parametry...); //registrace komponent uºivatelského rozhraní, aby mohly být //jádrem aktualizovány core.addCoreObserver(mainWindow); //kaºdá komponenta uºivatelského rozhraní ovládající jádro pot°ebuje //jeho kontrolér mainWindow.registerController(core.getController()); Jádro je samostatná £ást aplikace. O své £innosti informuje komponenty uºivatelského rozhraní p°ímo. Má zaregistrované objekty typu CoreObserver. CoreObserver je rozhraní, které musí implementovat t°ída, aby se její instance mohly stát obsluºnými objekty jádra. V této chvíli je jádro schopné posílat informace do v²ech registrovaných CoreObserver objekt· a informovat je o svém stavu. Pokud má být objekt schopen jádro i ovládat, musí získat referenci na kontrolér obsahující obsluºné metody jádra. Komponenty uºivatelského rozhraní nem·ºou k jádru p°istupovat p°ímo, pouze pomocí kontroléru. 19
20
KAPITOLA 3.
3.2
REALIZACE
Paralelizace výpo£t·
Na °ad¥ míst programu je pro zvý²ení výpo£etního výkonu pouºit mechanismus soub¥ºného programování[35]. Paralelizovaného výpo£tu je v Jav¥ dosaºeno za pomoci frameworku Executor[28]. Tento framework udrºuje mnoºinu pracovních vláken[2] (thread pool). Vlákna jsou objekty implementující rozhraní Runnable[29] nebo Callable[27]. Ob¥ dv¥ uvedená rozhraní de nují funkcionalitu vláken s tím rozdílem, ºe Runnable nevrací po vykonání ºádný výsledek (nemá návratovou hodnotu). Vlákno typu Callable vrací výsledek daný typem generické t°ídy ur£ené p°i de nici t°ídy. Rozdíl mezi implementací rozhraní Runnable a Callable je vid¥t na následujícím fragmentu kódu.
• Callable
import java.util.concurrent.Callable; public class ObjektCallable implements Callable
{ public ObjektCallable(...parametry...){ //konstruktor } @Override public Genericky_typ call() throws Exception { //výkonný kód vlákna return výsledek; } } • Runnable
public class ObjektRunnable implements Runnable { public ObjektRunnable(...parametry...) { //konstruktor }
}
@Override public void run() { //výkonný kód vlákna }
Z kódu je vid¥t, ºe vlákno typu Runnable ukon£í svou £innost a nevrací ºádná data. Naproti tomu vlákno typu Callable po dokon£ení £innosti vrátí objekt typu Genericky _typ.
3.2.
PARALELIZACE VÝPOT
21
Pokud je problém d¥litelný na nezávislé podproblémy, je moºné vlákna pouºít pro soub¥ºný výpo£et. Nejprve je nutné vytvo°it seznam úloh, které má Executor zpracovat. Metoda invokeAll(List < Callable > taskList) zp·sobí spu²t¥ní Executor frameworku a vykonání v²ech úloh. Framework po vykonání práce vlákna vrací objekt F uture < N avratovy _typ >, z kterého je moºné dostat výsledek pomocí metody get(). Po ukon£ení práce frameworku je nutné zavolat metodu shutdown(), jinak by mohlo k dojít k problém·m s dealokací opera£ní pam¥ti (Executor bude neustále aktivní, i kdyº nevykonává ºádnou £innost).
//zji²t¥ní po£tu dostupných procesor· int processorsCount = Runtime.getRuntime().availableProcessors(); //inicializace Executor frameworku (parametrem je po£et vláken) ExecutorService exec_service = Executors.newFixedThreadPool(processorsCount); //vytvo°ení seznamu úloh (kaºdá úloha pob¥ºí v samostatném vlákn¥) List> tasks = new ArrayList>(); for (int i = 0; i < processorsCount; i++) { tasks.add(new Callable()); } //vykonání úloh List> results = null; try { results = exec_service.invokeAll(tasks); }catch (Exception e) { e.printStackTrace(); } //ukon£ení práce Executor frameworku exec_service.shutdown(); //získání výsledk· for (Future future : results) { try { Navratovy_typ result = future.get(); }catch (Exception e) { e.printStackTrace(); } } Zp·sob, jakým Executor framework vykonává svou £innost, je moºné °ídit voláním r·zných metod. Na výb¥r jsou metody
invokeAll(List taskList) invokeAny(List taskList) První vykoná v²echny úlohy v seznamu a vrátí výsledky v²ech úloh. Druhá vrátí výsledek první úsp¥²n¥ dokon£ené úlohy (tedy takové, která dob¥hne do konce a nezp·sobí výjimku).
22
3.3
KAPITOLA 3.
REALIZACE
Modul pro zpracování dat metodami shlukování
Aplikace obsahuje samostatný modul pro podporu zpracování dat metodami shlukování. Modul je navrºen a implementován s ohledem na nezávislost na typu vstupních dat. Sestává ze t°í hlavních £ástí. První z nich je tovární t°ída [14] (factory class) vytvá°ející instance implementovaných algoritm· shlukování. T°ída ClusteringFactory na základ¥ p°ijatého parametru (parametr je typu vý£et) vytvo°í instanci typu Clustering. T°ída Clustering je rozhraní (interface), které musí implementovat kaºdý algoritmus shlukování, aby jej t°ída ClusteringFactory mohla vytvo°it.
Obrázek 3.1: Vytvá°ení instance algoritmu shlukování
Druhou £ástí jsou samotné algoritmy shlukování. Aby se t°ída mohla stát algoritmem shlukování, musí, jak bylo zmín¥no vý²e, implementovat rozhraní Clustering. Rozhraní Clustering na°izuje t°íd¥ implementaci funkce cluster(). Tato funkce na základ¥ matice vzdáleností rozd¥lí data do ur£itého po£tu podmnoºin. Funkce p°ebírá pouze matici vzdáleností a ne celou populaci práv¥ proto, aby nebyla závislá na typu vstupních dat a na pouºité podobnostní funkci. To ale p°edpokládá, ºe je matice vzdáleností vypo£tena externím mechanismem. Parametr sigma ur£uje hranici podobnosti dvou prvk· (pokud to algoritmus ke svému b¥hu pot°ebuje). Parametr SelectionStrategy je vý£et de nující zp·sob výb¥ru prototyp· jednotlivých shluk·. Parametr Random je náhodný generátor. Ten se typicky vyuºívá k inicializa£ním ú£el·m. Po vykonání b¥hu funkce je vrácen seznam objekt· typu Cluster.
3.3.
MODUL PRO ZPRACOVÁNÍ DAT METODAMI SHLUKOVÁNÍ
23
Hlavi£ka funkce je uvedena v následujícím bloku kódu.
/** * Funkce vrací seznam shluk· * * @param distanceMatrix matice vzdáleností * @param clusterCount po£et shluk·, na který má být populace rozd¥lena * @param sigma hranice podobnosti prvk· * @param selectionStrategy strategie pro výb¥r prototypu shluku * @param random náhodný generátor * @return seznam shluk· */ public ArrayList cluster(double[][] distanceMatrix, int clusterCount, double sigma, ClusterRepresentantSelectionStrategyEnum selectionStrategy, Random random); T°etí a zárove¬ poslední £ástí modulu je t°ída Cluster. Jde o datovou t°ídu obsahující informace o jednotlivých shlucích vytvo°ených algoritmem shlukování. Obsahuje seznam prvk· tvo°ících shluk. Navíc obsahuje informaci o prototypu (reprezentantovi) shluku, kterého vybral algoritmus shlukování na základ¥ parametru selectionStrategy, zmín¥ného vý²e. 3.3.1
Reprezentace shluku
Datová t°ída Cluster obsahuje informace o shluku vytvo°eném pomocí algoritmu shlukování. Neobsahuje p°ímo individuály populace, ale nese pouze informaci o indexu prototypu shluku a seznam index· prvk·, které do daného shluku pat°í. Indexy se vytvá°í na základ¥ matice vzdáleností. Matice vzdáleností má velikost (velikostP opulace ∗ velikostP opulace) a v poli matice_vzdalenosti(i, j) se nachází hodnota vzdálenosti prvku i od prvku j. Pole na hlavní diagonále matice obsahují samé nuly, protoºe ty reprezentují vzdálenost prvku od sebe samého. Samotný i-tý °ádek matice vyjad°uje vzdálenosti i-tého prvku populace od v²ech ostatních prvk· v£etn¥ sebe samého. Tuto informaci lze vyuºít a o£íslovat individuály pomocí index· jejich °ádk·. T°ída Cluster dále poskytuje informace o velikosti shluku (po£tu prvk·, které se v n¥m nachází) a pokud je tato informace k dispozici, i vzdálenost prototypu shluku od referen£ního individuála. 3.3.2
Implementace algoritmu shlukování - k-medoid
D·vody pouºití a obecné vlastnosti algoritmu k-medoid jiº byly uvedeny vý²e. Nyní je prostor pro popis konkrétních implementa£ních podrobností. Jiº vý²e bylo také zmín¥no, ºe t°ída se m·ºe stát algoritmem shlukování v p°ípad¥, ºe implementuje rozhraní Clustering. Hlavi£ka t°ídy tedy vypadá následovn¥:
public class KMedoid implements Clustering { }
24
KAPITOLA 3.
REALIZACE
Drobnou zm¥nou v algoritmu (viz. pseudokód v sekci 2.1.2) je inicializace medoid·. V originálním algoritmu se vybírají náhodn¥. V této implementaci je konstantou stanoven po£et pokus· o náhodné nastavení iniciálních st°ed·. Tento mechanismus se snaºí zabránit algoritmu v uvíznutí v lokálním optimu (k uvíznutí m·ºe dojít z d·vodu hladovosti algoritmu, jak bylo zmín¥no vý²e u algoritmu k-st°ed·). Po£et je omezen konstantou:
NUMBER_OF_INIT_TRIALS Dále je nutné uvést zp·sob, jakým se po£ítá cena kon gurace daného rozkladu mnoºiny individuál·. Jde o velice jednoduchou metodu, která pouze po£ítá sou£et vzdáleností v²ech ne-medoid· k jejich p°id¥leným medoid·m. Pseudokód metody, která toto zaji²´uje je následující.
1. pro kaºdý medoid se£ti vzdálenosti ke v²em bod·m daného medoidu (skóre) 2. se£ti skóre v²ech medoid· Poslední £ástí, kterou je t°eba popsat, je mechanismus výb¥ru nových medoid·. V podstat¥ se metoda pokou²í nahradit kaºdý medoid kaºdým jemu p°íslu²ícím bodem a zjistit, jestli je takováto kon gurace lep²í (levn¥j²í). Pokud ano, aktualizuje medoid, jinak ponechá p°ede²lou kon guraci. Pokud algoritmus ve dvou po sob¥ jdoucích iteracích medoidy nezm¥ní, ukon£í b¥h a prohlásí aktuální kon guraci za rozklad mnoºiny individuál·. Metoda je popsána následujícím blokem kódu.
1. uloº aktuální konfiguraci medoid· 2. pro kaºdý medoid M 3. pro ka°dý ne-medoid O p°i°azený k M 4. proho¤ M a O a spo£ti cenu konfigurace 5. pokud je cena konfigurace men²í, neº aktuální 6. uloº konfiguraci
3.4
Datový formát MusicString
Jiº v úvodu bylo zmín¥no, ºe program vyuºívá pro reprezentaci °e²ení datový formát knihovny JFugue MusicString[20]. Tento formát je v podstat¥ textové vyjád°ení hudebního zápisu. Pro p°edstavu, jak tento formát vypadá, je uveden p°íklad (obrázek 3.2) °et¥zce s korespondujícím hudebním zápisem.
V1 I[PIANO] T92 G3i D3i Rq E3i C#4i Rq | G2i G2i Ri C5h C4i | G3i D3i Rq E3i C#4i Rq | G2i G2i Ri C5h C4i | G3i D3i Rq E3i C#4i Rq
Obrázek 3.2: P°íklad notového ekvivalentu zápisu ve formátu MusicString
3.5.
POPIS INDIVIDUÁLA
25
Na první pozici je v uvedeném zápisu MusicStringu identi kátor stopy pro formát MIDI. Dal²í v po°adí je identi kátor hudebního nástroje, který daný part zahraje. Za ním následuje hodnota tempa a pak uº samotné takty skladby. Ty jsou odd¥leny svislou £arou (znakem '|'). V kaºdém taktu je seznam mezerami odd¥lených dob. V kaºdé dob¥ je seznam tón·, které se v p°íslu²né dob¥ hrají. Tón sestává z n¥kolika £ástí. Nejprve je uvedena vý²ka tónu (nap°íklad G3). Vý²ku tónu je moºné uvést i v £íselné podob¥ podle speci kace knihovny JFugue. íselné kódy jednotlivých vý²ek tón· jsou na obrázku 3.3.
Obrázek 3.3: Tabulka £íselných kód· vý²ek tón· [20]
Na dal²í pozici se m·ºe nacházet modi kátor (posuvka). Základními modi kátory jsou znaky # (zvy²uje notu o p·ltón) a b (sniºuje notu o p·ltón). Posledním prvkem je trvání doby. Na této pozici se nachází jeden ze symbol· ur£ující trvání (p°ehled znak· pro doby trvání je uveden v tabulce 3.1). Délka trvání m·ºe být navíc modi kována te£kou. Te£ka znamená, ºe doba trvá jeden a p·l násobek uvedené délky. Tedy q. je doba trvání srovnatelná s q+i (Podle tabulky 3.1).
Délka trvání 1/1 1/2 1/4 1/8 1/16 1/32 1/64 1/128 Symbol w h q i s t x o Tabulka 3.1: P°ehled symbol· ur£ujících délku hudební doby
3.5
Popis individuála
Popula£ní evolu£ní algoritmy jsou zaloºeny na principu soub¥ºného prohledávání velké £ásti stavového prostoru. To je zaji²t¥no tím, ºe ne²lechtí pouze jedno °e²ení daného problému, ale celou mnoºinu t¥chto °e²ení, p°i£emº kaºdé °e²ení je jiné (v ideálním p°ípad¥). Tedy vyvíjí populaci °e²ení sloºenou z jedinc·. Jeden jedinec reprezentuje jedno °e²ení. Stejn¥, jako je v p°írod¥ podoba jedince de nována jeho genetickou výbavou, i zde je jedinec de nován genotypem. Genotyp je soubor v²ech gen· daného jedince. Jedinec je sloºen z mnoºiny gen· (genotypu), které ur£ují jeho vlastnosti - fenotyp. Fenotyp je mnoºina pozorovatelných vlastností jedince. Pro p°edstavu je struktura jedince evolu£ního algoritmu
26
KAPITOLA 3.
REALIZACE
ukázána na p°íkladu na obrázku 3.4. Genotypem je pole £íslic, geny jsou jednotlivé £íslice. Fenotypem je polynom s koe cienty tvo°enými geny v po°adí uvedeném v poli.
Obrázek 3.4: P°íklad popula£ního jedince evolu£ního algoritmu Implementace jedince je zaji²t¥na t°ídou Individual. Je to jednoduchá t°ída obsahující pouze dva parametry a sadu konstruktor·.
• Parametr Fenotype je jednoduchá datová t°ída obsahující pouze °et¥zec (String) ve formátu MusicString, který reprezentuje fenotyp jedince. • Parametr Genotype (reprezentující genotyp) je komplexn¥j²í a bude popsána pozd¥ji. Instanci individuála je moºné vytvo°it t°emi zp·soby. Pokud jde o b¥ºného jedince v populaci, lze vyuºít první konstruktor. Tento konstruktor p°ebírá sadu parametr· popsaných níºe. Jde-li o jedince vytvo°eného za ú£elem inicializace evolu£ního procesu, pak lze vyuºít druhý konstruktor zaji²´ující randomizaci jedince. V pr·b¥hu smy£ky evolu£ního procesu je vyuºit poslední konstruktor, který vytvo°í jedince z jiº existujícího genotypu. Tento konstruktor je vhodné pouºít p°i perturba£ních operacích evolu£ního algoritmu, kdy se genotyp modi kuje (k°íºí a mutuje) pomocí externích nástroj·. Tímto konstruktorem se posléze velice snadno vyrobí nový jedinec z modi kovaného genotypu.
3.5.
POPIS INDIVIDUÁLA
27
První dva konstruktory mají n¥kolik spole£ných parametr·.
• fenotype et¥zec ve formátu MusicString reprezentující fenotyp. Na jeho základ¥ je vytvo°en genotyp. • instrument Tento parametr ur£uje typ hudebního nástroje pro generovaného jedince (koresponduje s polem typu hudebního nástroje, jak bylo uvedeno v sekci o formátu MusicString). • trackID Parametr ur£uje identi kátor stopy formátu MIDI (koresponduje s polem identi kátoru stopy ve formátu MusicString). • genotypeStrategy Vý£tový parametr de nující typ genotypu, který bude pouºit pro individuál. • playedNotes Jde o hudební stopu, která slu£uje hrané tóny ze v²ech ostatních stop originální skladby. Pouºívá se pro ohodnocení kvality generované stopy. Konstruktor pro randomizaci jedince obsahuje navíc dal²í parametry. A to náhodný generátor random a stopu availableNotes. Tato stopa je vytvo°ena harmonickým detektorem obsaºeným v modi kované knihovn¥ JFugue. V podstat¥ jde o stopu hraných tón· a stupnic, která má od ltrované ur£ité tóny. Tóny jsou ltrovány výb¥rem uºivatele. Jak vypadá, jak se vytvá°í a randomizuje genotyp je uvedeno v následující sekci. 3.5.1
Genotyp
T°ída Genotype je rozhraní umoº¬ující vytvá°ení r·zných druh· genotyp·. Pokud t°ída implementuje rozhraní Genotype, je nucena implementovat následující mnoºinu funkcí.
public interface Genotype { //vytvo°í z genotypu p°íslu²ný fenotyp public Fenotype createFenotype(); //vytvo°í kopii genotypu public Genotype copy(); //zjistí velikost genotypu (nap°. po£et not stopy) public int size(); //porovnává dva genotypy public boolean equalsGenotype(Genotype otherGenotype); //získá tóny hrané v originální skladb¥ public LinkedList getPlayedNotesTrack();
}
//zjistí hodnotu fitness funkce daného genotypu public double getFeasibility();
28
KAPITOLA 3.
REALIZACE
Konkrétní implementace genotypu jedince je zaji²t¥na t°ídou NumberGenotype. Ke své implementaci tato t°ída vyuºívá dal²í dv¥ t°ídy, a to NumberGenotypeBar a NumberGenotypeBeat. NumberGenotype obsahuje dva d·leºité parametry.
• feasibility Reálné £íslo reprezentující hodnotu tness funkce • track Konstrukce reprezentující stopu. V sekci popisu formátu MusicString bylo uvedeno, ºe stopa sestává z takt·, takty sestávají z dob a doby z tón·. Podobná konstrukce je i parametr track. Jde o seznam takt· (NumberGenotypeBar). Kaºdý takt je seznamem dob (NumberGenotypeBeat) a kaºdá doba v sob¥ obsahuje informace o hraných tónech a dob¥ trvání. Vytvo°ení instance této t°ídy mají na starosti dva konstruktory. První konstruktor vytvá°í objekt z originální stopy a ºádným zp·sobem genotyp nemodi kuje. Druhý konstruktor zaji²´uje vytvo°ení randomizovaného genotypu. Randomizovaný genotyp se principiáln¥ konstruuje naprosto stejným zp·sobem jako b¥ºný genotyp. Navíc se ale na konci procesu vytvá°ení aplikují randomiza£ní operace. První metodou, kterou mají oba konstruktory spole£nou se vytvo°í konstrukce reprezentující genotyp. Jakým zp·sobem vytvá°ení genotypu probíhá je uvedeno v dal²ím textu. Dal²í spole£ná metoda vytvo°í podobnou konstrukci ze stopy hraných tón·. Konstruktor zaji²´ující randomizaci aplikuje randomiza£ní operátory. Poslední spole£ná metoda ohodnotí vhodnost genotypu jedince.
public NumberGenotype(Fenotype fenotype, FlatTrack playedNotes, String instrument, String trackID) { //inicializace genotypu initializeGenotype(fenotype.getFenotypeString(), instrument, trackID); //inicializace stopy hraných tón· initializePlayedNotes(playedNotes); //ohodnocení vhodnosti genotypu computeFeasibility(); } public NumberGenotype(Fenotype fenotypeTemplate, FlatTrack availableNotesTrack, FlatTrack playedNotes, Random random, String instrument, String trackID) { //inicializace genotypu initializeGenotype(fenotypeTemplate.getFenotypeString(), instrument, trackID); //inicializace stopy hraných tón· initializePlayedNotes(playedNotes); //randomizace genotypu randomize(random, availableNotesTrack); //ohodnocení vhodnosti genotypu computeFeasibility(); }
3.5.
POPIS INDIVIDUÁLA
29
Inicializace konstrukce reprezentující hudební stopu za£íná voláním metody initializeGenotype(), která zji²´uje dodate£né parametry. Na konci této metody se volá metoda createTrack(), která vytvo°í st¥ºejní konstrukci genotypu. Vstupní °et¥zec se rozd¥lí na jednotlivé takty, které se zpracovávají samostatn¥.
private void initializeGenotype(String fenotypeString, String instrument, String trackID) { //zjistí dodate£né parametry this.instrument = "I[" + instrument + "]"; this.trackID = trackID;
}
//ze zápisu MusicStringu vytvo°í genotyp createTrack(fenotypeString);
private void createTrack(String musicString) { //rozd¥l °et¥zec po taktech String[] bars = musicString.split("\\| "); //první takt obsahuje hlavi£ku (tu je nutné odstranit) bars[0] = bars[0].substring(bars[0].indexOf(" T") + 1); //pokud °et¥zec obsahuje tempo, uloº ho a vytvo° konstrukci taktu for (int barIndex = 0; barIndex < bars.length; barIndex++) { //extract tempo if necessary if (bars[barIndex].startsWith("T")) { bars[barIndex] = extractTempoFromBar(bars[barIndex], barIndex); }
}
}
//vytvo° konstrukci pro takt a vloº ho do seznamu track.add(new NumberGenotypeBar(bars[barIndex]));
Takto inicializovaný genotyp je t°eba ohodnotit tness funkcí. K tomu slouºí metoda
computeFeasibility(). Tato metoda prochází stopu takt po taktu a hodnotí vlastnosti
hraných tón·. Takt musí obsahovat alespo¬ dv¥ doby, aby se dal ohodnotit. Funkce zkoumá intervaly mezi tóny dob a doby trvání sousedních dob. Penalizuje velké skoky vý²ek tón· dvou sousedních dob. Pokud se st°ídají dlouhé a krátké doby, také dochází k penalizaci. Tento mechanismus zaji²´uje preferenci "rozumných" skladeb a penalizuje skladby s "divokými" rytmickými a melodickými zm¥nami. P°ede²lý postup popisoval vytvá°ení b¥ºného genotypu bez jakýchkoli zm¥n. Následující text popisuje randomizaci genotypu a randomiza£ní operace.
30
KAPITOLA 3.
REALIZACE
Tato metoda p°ebírá jako parametry náhodný generátor a FlatTrack stopu availableNotesTrack. Tato stopa rytmicky koresponduje s originální stopou. Je vytvo°ena harmonickým detektorem a tónovým ltrem tak, aby obsahovala pouze ur£ité (vhodné) tóny. Randomiza£ní operace poté originální stop¥ pozm¥ní rytmus a melodii. Modi kace jsou provád¥ny tak, aby shodné takty byly modi kovány stejným zp·sobem, nedojde tak k naru²ení p·vodní kompozice skladby. Aplikace randomiza£ních operací jsou nazna£eny na následujících p°íkladech.
• Slou£ení dvou po sob¥ jdoucích dob do jedné, p°i£emº jsou náhodn¥ zachovány tóny z první nebo druhé doby.
Obrázek 3.5: P°íklad slou£ení dvou po sob¥ jdoucích dob
• Rozd¥lení doby na dv¥ doby polovi£ní délky.
Obrázek 3.6: P°íklad rozd¥lení doby
• Obrácení po°adí dob v taktu.
Obrázek 3.7: P°íklad obrácení dob v taktu
• Set°íd¥ní dob v taktu podle nejniº²í nebo nejvy²²í noty, vzestupn¥ nebo sestupn¥ (T°ídí se pouze tóny, délky dob z·stávají zachovány). • Náhodné vybírání tón· z odpovídajícího taktu z FlatTrack stopy. Vybírá tedy pouze vhodné noty p°ipravené harmonickým detektorem a tónovým ltrem. Navíc je omezen ur£itým intervalem, aby výsledná stopa neobsahovala velké melodické skoky.
3.6.
3.6
INICIALIZACE GENETICKÉHO ALGORITMU
31
Inicializace genetického algoritmu
Po spu²t¥ní programu a nastavení v²ech parametr· uºivatelem dochází k inicializaci evolu£ního procesu. V první °ad¥ je t°eba sestavit referen£ní individuál. Tento jedinec se evolu£ního procesu neú£astní a z·stává konstantní po celou dobu tohoto procesu. Slouºí k ohodnocování vhodnosti shluk· vytvo°ených algoritmem shlukování. Referen£ní jedinec se vytvá°í ze vstupní hudební stopy a jeho genotyp se nijak nemodi kuje. Jde tedy pouze o p·vodní hudební stopu ve stejném formátu v jakém jsou jedinci populace.
MusicStringTrack selectedTrack = originalMusicStringSong .getTrack(originalMusicStringSong .getTrackIds().get(selectedTrackIndex)); Fenotype fenotype = new Fenotype(selectedTrack.toString()); String instrument = selectedTrack.getInstrument(); String trackID = selectedTrack.getChannelMusicString(); referenceIndividual = new Individual(fenotype, playedNotes, instrument, trackID, genotypeType); Po vytvo°ení referen£ního jedince dochází k vytvá°ení iniciální (náhodné) populace. Randomizace jedinc· této první populace probíhá zp·sobem, jak bylo popsáno v p°ede²lé sekci o genotypu jedince. Vytvá°ení populace má na starosti t°ída MelodyAndRhythmRandomPopulationInitializer. Jedním z parametr·, které tato t°ída p°ijímá je velikost populace, kterou má vytvo°it. Na základ¥ tohoto údaje a za pomoci soub¥ºného programování vytvo°í populaci ºádané velikosti. Pouºitím soub¥ºného programování do²lo k významnému sníºení £asových nárok· na výrobu iniciální populace. Hodnoty trvání inicializace populace s a bez vyuºití technik soub¥ºného programování si lze prohlédnout v tabulce 3.2. Kon gurace pouºitého stroje je uvedena v p°íloze B.
population = RandomPopulationFactory.createRandomPopulation( populationInitStrategy, populationSize, originalMusicStringSong, instrumentIndex, random, availableTrackID, new int[]{selectedTrackIndex}, genotypeType, toneFilter);
Velikost populace Sekven£ní vytvá°ení Soub¥ºné vytvá°ení 50 5,03 s 2,25 s 100 7,63 s 3,76 s 200 14,45 s 7,72 s Tabulka 3.2: P°ehled trvání inicializa£ního procesu s a bez vyuºití technik soub¥ºného programování
32
KAPITOLA 3.
3.6.1
REALIZACE
Výpo£et matice vzdáleností
Po vytvo°ení iniciální populace nastupuje na °adu algoritmus shlukování. Cílem je seskupit jedince s podobnými genotypy tak, aby bylo moºné ur£it jejich prototyp (reprezentanta). Vhodnost tohoto reprezentanta je ohodnocena uºivatelem. Jak bylo zmín¥no v p°ede²lém textu, algoritmus shlukování ke své £innosti vyºaduje matici vzdáleností. Po vytvo°ení iniciální populace je tedy nutné spo£íst matici vzdáleností. K urychlení tohoto výpo£tu byl op¥t pouºit mechanismus soub¥ºného programování. Matice vzdáleností je symetrická podle hlavní diagonály, pro dal²í zrychlení výpo£tu je tedy vhodné spo£íst pouze spodní nebo horní trojúhelníkovou £ást matice. Algoritmus zjistí po£et polí matice, které je nutné vypo£íst a rozd¥lí výpo£et mezi dostupné procesory. Výpo£et matice vzdáleností je pom¥rn¥ zdlouhavá operace a soub¥ºným programováním do²lo k výraznému zkrácení doby výpo£tu. Statistiky zrychlení výpo£tu jsou uvedeny v tabulce 3.3. Kon gurace pouºitého stroje je uvedena v p°íloze B.
Velikost populace Sekven£ní vytvá°ení Soub¥ºné vytvá°ení 50 9s 6s 100 32 s 18 s Tabulka 3.3: P°ehled trvání výpo£tu matice vzdáleností s a bez vyuºití technik soub¥ºného programování
3.6.2
Metrika pro výpo£et vzdálenosti dvou genotyp·
Výpo£et vzdálenosti dvou individuál· je v podstat¥ zji²t¥ní míry odli²nosti jejich genotyp·. V tomto p°ípad¥ se cyklem prochází celá skladba takt po taktu, dobu po dob¥, a po£ítá se relativní vzdálenost mezi tóny hrajícími v korespondujících pozicích. Vzhledem k tomu, ºe n¥které tóny spolu zn¥jí lépe neº jiné, musel být tento fakt zakomponován i do výpo£tu vzdálenosti. Z tabulky na obrázku 3.3 je patrné, ºe dva tóny ve vzdálenosti jedné oktávy jsou od sebe podle £íselných kód· vzdálené 12 jednotek (stejné tóny hrané tzv. "o oktávu níº nebo vý²"jsou harmonické, nap°. tóny C1 a C2). Z tohoto intervalu se odvíjí i výpo£et vzdálenosti. Vzorce pro výpo£et vzdálenosti jsou uvedeny níºe.
• MAXIMAL_DIFFERENCE_INTERVAL konstanta ur£ující maximální vzdálenost dvou dob, která se je²t¥ bere v potaz (dále zna£eno M) • SINGLE_OCTAVE_INTERVAL konstanta de nující rozsah jedné oktávy (dále zna£eno S)
3.6.
33
INICIALIZACE GENETICKÉHO ALGORITMU
Pn distance(a, b) =
i=0 distance(beata,i , beatb,i )
n∗M
(3.1)
Rovnice uvedená vý²e demonstruje iterativní pr·chod v²emi dobami ve skladb¥. Tedy suma vzdáleností p°es v²echny doby pod¥lená maximální moºnou vzdáleností dvou skladeb. To z d·vodu normalizace hodnot vzdálenosti do intervalu <0, 1>. Následující rovnice popisuje výpo£et vzdálenosti dvou samostatných dob, kde ta a tb jsou tóny hrané v korespondujících dobách dvou r·zných stop.
0, 0, distance(beata , beatb ) = |ta − tb |mod(S) M
A) B) C)
(3.2)
D)
• podmínka A: pokud ob¥ doby obsahují pouze tóny hrané v originální stop¥ • podmínka B: pokud alespo¬ jedna z dob obsahuje pomlku • podmínka C: pokud je vzdálenost dvou tón· men²í neº M • podmínka D: pokud je vzdálenost dvou tón· v¥t²í neº M 3.6.3
Shlukování a t°íd¥ní shluk·
Po výpo£tu matice vzdáleností je uº moºné jedince seskupit do shluk·. O to se stará algoritmus shlukování. Kód provád¥jící shlukování jedinc· je uveden v následujícím bloku kódu.
clusteredPopulation = clusteringAlgorithm.cluster( computeDistanceMatrix(population, metrics), clusterCount, sigma, clusterRepresentantSelectionStrategy, random); Funkce cluster() vrátí seznam shluk·. Tyto shluky je nutné set°ídit podle podobnosti s referen£ním jedincem. Tímto algoritmus nabídne vodítko uºivateli o kvalit¥ jedinc· a ten pak m·ºe shluky set°ídit dle svých preferencí. T°íd¥ní shluk· probíhá následujícím zp·sobem.
1. Pro v²echny shluky S 2. Spo£ti vzdálenost prototypu S od referen£ního individuálu 3. Set°i¤ shluky podle vzdálenosti od nejmen²í T°íd¥ní shluk· je poslední operací inicializa£ní fáze tohoto genetického algoritmu. Shluky jsou prezentovány uºivateli k poslechu a ohodnocení. Uºivatel m·ºe poslouchat a exportovat prototypy shluk·. Navíc shluky m·ºe dle svých preferencí t°ídit a tím ovliv¬ovat pr·b¥h evolu£ního procesu. Celý pr·b¥h inicializa£ní fáze si je moºné prohlédnout v následujícím bloku kódu.
34
KAPITOLA 3.
REALIZACE
public void initEvolutionProcess() { 1. Vytvo° referen£ní individuál z fenotypu a dal²ích parametr· 2. Vytvo° randomizovanou populaci 3. Vypo£ti matici vzdáleností pro populaci 4. Prove¤ shlukování 5. Set°i¤ shluky }
3.7
Iterace evolu£ního algoritmu
Po inicializaci algoritmu a vytvo°ení první náhodné populace je uºivatel vyzván k manuálnímu ohodnocení jedinc·. Ohodnocení jedinc· probíhá tak, ºe uºivatel dostane k poslechu prototypy shluk·. Ty set°ídí v po°adí od nejlep²ího k nejhor²ímu podle svých preferencí. Po uspo°ádání shluk· algoritmus provede uºivatelem stanovený po£et iterací evolu£ního procesu. Pokud zvolí více neº jednu iteraci, algoritmus bere v potaz po°adí shluk· podle podobnosti s referen£ním individuálem. Po provedení stanoveného po£tu iterací op¥t nabídne uºivateli moºnost ohodnocení. Níºe je uvedený zdrojový kód metody provád¥jící jednu smy£ku evolu£ního procesu.
private void singleIteration() { //vytvo° novou populaci z p°ede²lé dle po°adí shluk· population = populationSampler.samplePopulation(clusteredPopulation, population, random); //algoritmus shlukování clusteredPopulation.clear(); clusteredPopulation = clusteringAlgorithm.cluster( computeDistanceMatrix(population, metrics), clusterCount, sigma, clusterRepresentantSelectionStrategy, random); //t°íd¥ní shluk· podle podobnosti s referen£ním jedincem sortClusteredPopulationAccordingToReference(clusteredPopulation); } Z kódu je moºné vy£íst následující skute£nosti. Kód je velice podobný inicializa£ní £ásti. Dojde k vytvo°ení nové populace (tentokrát ne náhodné, ale jako p°edloha se pouºije populace vzniklá p°ede²lou iterací). Mechanismus vytvá°ení nové populace je popsán v následujícím textu. Nov¥ vzniklá populace je roz°azena do shluk· algoritmem shlukování a shluky jsou set°íd¥ny podle podobnosti s referen£ním jedincem (stejn¥ jako bylo uvedeno vý²e v sekci 3.6.3). Po t¥chto operacích se bu¤ provádí dal²í smy£ka evolu£ního procesu nebo jsou set°íd¥né shluky nabídnuty k poslechu a ohodnocení.
3.7.
ITERACE EVOLUNÍHO ALGORITMU
3.7.1
35
Vytvo°ení nové populace
Jak bylo zmín¥no v úvodu, popula£ní evolu£ní algoritmus k vytvá°ení nových populací pouºívá sadu operací. A to selekci (a s ní související elitismus), mutaci a k°íºení. Elitismus v tomto p°ípad¥ není pouºit, protoºe není moºné v takto subjektivním p°ípad¥ prohlásit n¥jakého jedince za striktn¥ vhodn¥j²ího neº jiné jedince. Selekce probíhá dvoustup¬ovým zp·sobem. Nejprve se ur£í, z kterého shluku se bude rodi£ovský jedinec vybírat a následn¥ se v rámci shluku vybírá podle hodnoty tness funkce, která je jedinci p°i°azena. Podrobnosti jsou uvedeny dále v textu. Stejn¥ tak jsou p°edm¥tem této sekce implementa£ní podrobnosti muta£ních a k°íºících operátor·. Vytvá°ení nové populace má na starosti t°ída NumberGenotypeProportionalSampler. Tato t°ída op¥t ke sníºení doby výpo£tu pouºívá techniku soub¥ºného programování. P°i ºádosti o vytvo°ení nové populace si metoda samplePopulation() spo£te, jak velkou populaci má vytvo°it a zjistí po£et dostupných procesor·. Velikost jednotlivých subpopulací po£ítá metoda computeSubPopulationSizes(). Její zdrojový kód je uveden v následujícím bloku.
private int[] computeSubPopulationSizes(int originalPopulationSize, int taskCount) { //vytvá°í pouze sudé hodnoty (jedinci se generují po dvojicích) int[] populationSizes = new int[taskCount]; int subPopulationSize = ((originalPopulationSize / taskCount) % 2 == 0) ? originalPopulationSize / taskCount : originalPopulationSize / taskCount + 1; Arrays.fill(populationSizes, subPopulationSize); //první úloha navíc dopo£ítává zbytek do celkové velikosti populace populationSizes[0] += originalPopulationSize - (subPopulationSize * taskCount); return populationSizes; } Tato metoda vytvo°í pole celých £ísel, které reprezentují velikosti subpopulací pro jednotlivá vlákna. Velikosti subpopulací musí být sudé hodnoty, protoºe jedinci vznikají vºdy po dvojicích. Pokud je celková suma hodnot niº²í, neº ºádaná velikost populace, první úloha dovytvo°í jedince navíc. Po výpo£tu velikosti subpopulací spustí NumberGenotypeProportionalSampler paralelní výpo£et, kdy kaºdé vlákno vytvo°í svou £ást populace. Tyto £ásti jsou slou£eny a vytvo°í novou populaci. Dále je popsána £innost jednoho vlákna a mechanismus, jakým vzniká subpopulace.
3.7.1.1 Selekce Jak jiº bylo uvedeno vý²e, selekce jedinc· probíhá dvoustup¬ov¥. Nejprve je pot°eba vybrat shluk, ze kterého je jedinec vybírán. V rámci shluku se jiº vybírá dle hodnot tness funkce jednotlivých jedinc· p°ítomných ve shluku. Kaºdý shluk dostane pravd¥podobnostní
36
KAPITOLA 3.
REALIZACE
interval dané velikosti. í°ka tohoto intervalu je dána jeho po°adím v seznamu (ur£eno uºivatelem) a jeho velikostí (shluk s v¥t²ím po£tem jedinc· dostává bonus a men²í shluky jsou penalizovány). Velikosti interval· vypo£ítává funkce computeClustersSelectionProbabilities(). Tato funkce jako vstupní parametry p°ijímá celkovou velikost populace a seznam shluk· set°íd¥ný uºivatelem. Nejprve je vygenerován vektor W , který obsahuje váhy shluk· podle jejich po°adí. První shluk (uºivatelem ozna£ený jako nejlep²í) dostane £íslo N (celkový po£et shluk·), poslední (nejhor²í) dostane hodnotu 1.
W = {N, N − 1, N − 2, ..., 2, 1}
(3.3)
Posléze se na základ¥ po£tu shluk· (N) spo£te koe cient denominator. Jde o sou£et °ady po°adových £ísel shluk· £íslovaných od jedné.
denominator =
N X i=1
i=
N ∗ (N + 1) 2
(3.4)
Z parametr· uvedených v 3.3 a 3.4 je moºné sestavit vektor koe cient· coef f icients. Kaºdému shluku je p°i°azena hodnota, která vypovídá o jeho po°adí v seznamu. Shluk Ci dostane tím vy²²í hodnotu coef f icientsi , £ím vý²e se v seznamu nachází (nejvy²²í hodnotu má shluk na první míst¥, ozna£ený jako nejlep²í).
coef f icientsi =
Wi denominator
(3.5)
Vektor coef f icients vypovídá pouze o po°adí shluk·, ale ne o jejich velikosti. Proto je pot°eba vytvo°it je²t¥ jeden vektor hodnot ratio, který obsahuje informaci o velikosti shluk·. Prvek vektoru ratioi ur£uje váhu shluku ci v závislosti na jeho velikosti.
ratioi =
|ci | population_size
(3.6)
Z vektor· coef f icients a ratio je uº moºné sestavit intervaly. Vektor intervals obsahuje pro kaºdý shluk ci ²í°ku jeho intervalu. í°ka intervalu se spo£te vzorcem uvedeným v rovnici 3.7. ratioi + coef f icientsi intervalsi = (3.7) 2 Pro snaz²í výpo£et je vhodn¥j²í tento vektor promítnout do rozmezí hodnot 0 a 1. Tedy je vytvo°en vektor probs, který má na první pozici hodnotu 0 a na poslední hodnotu 1. Hodnoty mezi prvním a posledním prvkem jsou vypln¥ny z vektoru intervals zp·sobem uvedeným v rovnici 3.8.
probsi+1 = probsi + intervalsi ; i ∈< 0, N − 1 >
(3.8)
3.7.
37
ITERACE EVOLUNÍHO ALGORITMU
P°íklad výpo£tu je uveden v následujícím bloku.
P opulation_size = 100 N =5 C = [15, 35, 25, 10, 15] W = [5, 4, 3, 2, 1] denominator = 15 5 4 3 2 1 coef f icients = [ , , , , ] 15 15 15 15 15 15 35 25 10 15 ratio = [ , , , , ] 100 100 100 100 100 intervals = [0.242, 0.308, 0.225, 0.12, 0.108]
(3.9)
probs = [0, 0.242, 0.55, 0.775, 0.895, 1] V p°íkladu 3.9 je vygenerován vektor probs. Ten °íká, ºe první shluk má p°i°azený interval (0, 0.242), druhý má interval (0.242, 0.55) a tak dále. Nyní sta£í vygenerovat náhodné £íslo v intervalu <0, 1> a sledovat, v kterém intervalu se toto £íslo nachází. Shluk, který má p°i°azen interval, kam spadá náhodn¥ vygenerovaná hodnota, je vybrán jako shluk pro výb¥r rodi£ovského jedince. Nyní, kdyº je ur£en shluk, ze kterého je vybírán rodi£ovský jedinec, je t°eba je²t¥ vybrat index jedince v rámci shluku. To se provádí na základ¥ hodnoty tness funkce kaºdého jedince. Nejprve je vybrán náhodný jedinec bez ohledu na hodnotu jeho tness funkce. Poté je vygenerováno £íslo z ur£itého rozsahu (v tomto p°ípad¥ je rozsah stanoven od 0 do 10). Toto £íslo reprezentuje po£et náhodných výb¥r·, p°i kterých je ponechán vºdy jedinec s nejlep²í hodnotou tness funkce. Vý²e uvedeným zp·sobem se v kaºdé iteraci vyberou dva rodi£ov²tí jedinci, z kterých jsou dále vygenerovány dva noví jedinci. Tato smy£ka probíhá tak dlouho, dokud není napln¥na subpopulace dané velikosti. Omezením je, ºe v dané iteraci nesmí být vybráni jako rodi£e dva stejní jedinci.
3.7.1.2 K°íºení V této práci byly implementovány £ty°i druhy k°íºících operátor·, a to jedno aº £ty°bodový k°íºící operátor. Kaºdý z t¥chto operátor· má p°i°azenou pravd¥podobnost, se kterou dojde k jeho výb¥ru a pouºití. Tabulka pravd¥podobnosti 3.4 výb¥ru jednotlivých k°íºících operátor· je uvedena v textu.
Operátor
Jednobodový Dvoubodový T°íbodový ty°bodový
Pravd¥podobnost 0.4 0.3 0.2 0.1
Tabulka 3.4: Pravd¥podobnosti výb¥ru k°íºících operátor·
38
KAPITOLA 3.
REALIZACE
Výb¥r po£tu k°íºících bod· má na starosti funkce selectCrossoverPointsCount(). Z daných pravd¥podobností jsou vytvo°eny intervaly. Kaºdému operátoru je následn¥ p°id¥len korespondující interval. Dále se vygeneruje náhodné £íslo a zkontroluje se, do kterého intervalu toto £íslo spadá. Následn¥ je vybrán ten k°íºící operátor, kterému je daný interval p°i°azen. Dal²ím krokem v procesu k°íºení je stanovit konkrétní k°íºící body. Vzhledem k reprezentaci hudebního zápisu jako seznamu takt· je p°irozené, ºe i výb¥r k°íºících bod· je provád¥n na úrovni takt·. Náhodn¥ je vybráno tolik index· takt·, kolik je stanoveno mechanismem uvedeným vý²e. Na základ¥ t¥chto bod· dojde op¥t k vytvo°ení interval·. To slouºí ke zjednodu²ení výpo£tu. K°íºení genotyp· pak probíhá jako vým¥na podseznam·. Pro ilustraci jsou p°iloºeny ukázky jednobodového a dvoubodového k°íºení na obrázcích 3.8 a 3.9. Pseudkód funkcí zaji²´ujících k°íºení je uveden v následujícím bloku.
1. 2. 3. 4. 5.
Vygeneruj náhodné £íslo v intervalu <0, 1> Zkontroluj, do jakého intervalu £íslo pat°í Vra´ k°íºící operátor p°i°azený k intervalu Náhodn¥ vyber tolik k°íºících bod·, kolik ur£uje operátor k°íºení Prove¤ vým¥nu podseznam· dvou genotyp·
Obrázek 3.8: P°íklad jednobodového k°íºení
Obrázek 3.9: P°íklad dvoubodového k°íºení
3.7.
ITERACE EVOLUNÍHO ALGORITMU
39
3.7.1.3 Mutace Mechanismem uvedeným v p°ede²lých dvou sekcích vzniknou dva nové genotypy dvou nových jedinc·. Dále jsou tyto genotypy s ur£itou pravd¥podobností modi kovány muta£ními operátory. P°íklad mutace genotypu jednoho z jedinc· je uveden v následujícím fragmentu zdrojového kódu.
private static final double MUTATION_PROBABILITY = 0.4; if (random.nextDouble() < MUTATION_PROBABILITY) { mutateTrack(newChildTrack1, oldPopulation.get(parentIndex1) .getGenotype() .getPlayedNotesTrack(), random); } Mutace nového genotypu probíhá na základ¥ rodi£ovského jedince a jeho stopy hraných tón·. Je to z toho d·vodu, aby bylo moºné pro nov¥ generovaný genotyp vybírat vhodné tóny a ne pouze zkou²et náhodné tóny z celého rozsahu moºných ton·. Mutace genotypu je sloºena z mnoºiny randomiza£ních operací, které byly uvedeny v sekci 3.5.1 o randomizaci genotypu za ú£elem vytvo°ení iniciální populace. Pro p°ipomenutí jde o následující operace:
• Slou£ení dvou po sob¥ jdoucích dob p°i zachování tón· z první nebo druhé doby. • Rozd¥lení doby na dv¥ doby polovi£ní délky. • T°íd¥ní dob v taktu • Obrácení po°adí dob v taktu • Modi kace vý²ek tón· na základ¥ stopy hraných tón· v originální skladb¥.
40
KAPITOLA 3.
REALIZACE
Kapitola 4
Testování 4.1
Kvalita implementovaného algoritmu shlukování (k-medoid)
Kvalitu algoritmu shlukování lze ohodnotit pomocí velkého mnoºství kritérií. V této práci bylo zvoleno kritérium P urity [6]. Toto kritérium ohodnocuje kvalitu shlukování hodnotami v intervalu <0, 1>, p°i£emº £ím vy²²í hodnotu kritérium vygeneruje, tím lépe si algoritmus shlukování vedl p°i svém b¥hu. Za ú£elem tohoto testování byly navrºeny pomocné t°ídy. Algoritmus dostane na vstup populaci jedinc·. Kaºdý jedinec má de nováno, ke kterému shluku pat°í. Dále je na vstupu matice vzdáleností vytvo°ená metrikou, která generuje vzdálenosti mezi jedinci populace. Jedinc·m ze stejného shluku p°i°adí náhodn¥ hodnotu z jednoho intervalu a jedinc·m z r·zných shluk· hodnotu z druhého intervalu. Cílem je ur£it, jaké mnoºství jedinc· bylo za°azeno do správných shluk·. Vliv velikosti populace, velikosti a hodnoty interval· a po£tu generovaných shluk· na hodnotu kritéria purity jsou p°edm¥tem testování.
Velikost populace 1000 500 50 Vzdálenost pro stejné shluky <0.01, 0.25> <0.01, 0.25> <0.01, 0.25> Vzdálenost odli²ných shluk· <0.3, 1.0> <0.3, 1.0> <0.3, 1.0> Po£et generovaných shluk· 5 5 5 Purity 0.84 0.82 0.88 Tabulka 4.1: Výsledky kvality shlukování - vliv velikosti populace
Velikost populace 1000 1000 1000 Vzdálenost pro stejné shluky <0.01, 0.25> <0,25, 0.5> <0.3, 1.0> Vzdálenost odli²ných shluk· <0.3, 1.0> <0.3, 0.7> <0.3, 1.0> Po£et generovaných shluk· 5 5 5 Purity 0.84 0.638 0.232 Tabulka 4.2: Výsledky kvality shlukování - vliv volby interval· metriky
41
42
KAPITOLA 4.
TESTOVÁNÍ
Velikost populace 1000 1000 1000 Vzdálenost pro stejné shluky <0.01, 0.25> <0.01, 0.25> <0.01, 0.25> Vzdálenost odli²ných shluk· <0.3, 1.0> <0.3, 1.0> <0.3, 1.0> Po£et generovaných shluk· 5 10 15 Purity 0.84 0.82 0.734 Tabulka 4.3: Výsledky kvality shlukování - vliv po£tu shluk· Tabulky 4.1, 4.2 a 4.3 p°edvádí výsledky algoritmu k-medoid (implementace PAM) pro r·zná nastavení parametr·. Hodnoty kritéria purity jsou pr·m¥rem z dvaceti b¥h· algoritmu. Z výsledk· je patrné, ºe velikost populace a po£et generovaných shluk· nemá na kvalitu shlukování zásadní vliv. Nejv¥t²í vliv na kvalitu shlukování má pouºitá metrika. P°i postupném prolínání interval· vzdáleností pro stejné a odli²né t°ídy prvk· algoritmus není schopen tyto prvky správn¥ rozli²it.
4.1.1
Vliv selek£ního tlaku na velikost shluk·
Cílem evolu£ních algoritm· je ²lechtit populaci jedinc· a postupn¥ populaci ve stavovém prostoru °e²ení problému p°esouvat sm¥rem k oblastem s lep²ími hodnotami kriteriální funkce. Tento jev se nazývá selek£ní tlak. Je to mechanismus, který "nutí" populaci se zlep²ovat. Na obrázku 4.1 je patrné, ºe uº po malém mnoºství iterací mají jedinci, bez zásahu uºivatele, tendenci p°esouvat se do prvního shluku (tedy do toho, který je nejblíºe referen£nímu °e²ení). Navrºená tness funkce tedy tento selek£ní tlak vytvá°í.
Obrázek 4.1: Distribuce jedinc· ve shlucích v závislosti na po£tu iterací
4.2.
4.2
DIVERZITA PROTOTYP SHLUK
43
Diverzita prototyp· shluk·
Hlavním cílem algoritmu shlukování je nabídnout uºivateli k ohodnocení takové jedince (skladby), které jsou navzájem co nejmén¥ podobné. Na obrázcích 4.2 a 4.3 jsou uvedeny ukázky notových zápis· vygenerovaných inicializa£ním procesem (prototypy nepodstoupily smy£ku evolu£ního procesu). Kaºdý obrázek obsahuje p¥t prototyp· v po°adí ur£eném algoritmem. P°esto, ºe jde jen prvních pár takt·, je pouhým okem je viditelné, ºe hudební linky jsou si podobné jen velice málo.
Obrázek 4.2: Diverzita prototyp· (inicializace) - R.E.M. - Man on the moon
Obrázek 4.3: Diverzita prototyp· (inicializace) - Bon Jovi - Say it isn't so
44
KAPITOLA 4.
TESTOVÁNÍ
Obrázky 4.4 a 4.5 zobrazují prvních n¥kolik takt· prototyp· po deseti iteracích evolu£ního procesu. Zde je jiº patrný vliv perturba£ních operátor·. Na obrázku 4.4 není tento vliv patrný natolik, jako na obrázku 4.5. Skladby se v prvních ²esti taktech p°íli² £i v·bec neli²í. Je to d·sledkem toho, ºe tyto £ásti ozna£ila kriteriální funkce jako vhodné a proto se projevují £ast¥ji, neº mén¥ vhodné motivy. Nicmén¥ prvních ²est takt· není vypovídajících a skladby se li²í v následujících, nevyobrazených £ástech.
Obrázek 4.4: Diverzita prototyp· (10 iterací) - R.E.M. - Man on the moon
Obrázek 4.5: Diverzita prototyp· (10 iterací) - Bon Jovi - Say it isn't so
4.2.
DIVERZITA PROTOTYP SHLUK
45
Následuje poslední ukázka diverzity prototyp· shluk·. Jde o pom¥rn¥ jednoduchou skladbu z po£íta£ové hry. Výsledek shlukování je uveden na obrázcích 4.6 a 4.7. Na tomto p°íkladu je jasn¥ vid¥t, ºe algoritmus shlukování opravdu generuje prototypy, které jsou odli²né. Zárove¬ je na obrázku 4.7 pozorovatelné zachovávání ur£itých motiv·, které kriteriální funkce ozna£í jako "dobré". Tento jev je moºné pozorovat nap°íklad ve druhém taktu, který je spole£ný pro £ty°i z p¥ti vygenerovaných stop.
Obrázek 4.6: Diverzita prototyp· (inicializace) - Final Fantasy 10 - To Zanarkand
Obrázek 4.7: Diverzita prototyp· (10 iterací) - Final Fantasy 10 - To Zanarkand Hodnota kriteriální funkce je závislá na velikosti genotypu. Velikost genotypu závisí na délce skladby. R·zné skladby proto mohou mít velice rozdílné hodnoty kriteriální funkce v závislosti na své délce. Hodnota dále závisí na vybrané stop¥, která podstupuje evolu£ní
46
KAPITOLA 4.
TESTOVÁNÍ
proces. Hodnoty kriteriální funkce typicky (ani v inicializa£ním kroku) nep°esahují hodnotu 0.5. P°íklad hodnot kriteriální funkce pro vybrané skladby je uveden v tabulce 4.4.
Skladba
Aerosmith - Dream on Bon Jovi - Say it isn't so R.E.M. - Loosing my religion
Shluk 1 Shluk 2 Shluk 3 Shluk 4 Shluk 5 0.03573 0.02784 0.12157
0.03814 0.03061 0.12440
0.04713 0.03339 0.13380
0.05031 0.05260 0.14085
0.05862 0.06557 0.15206
Tabulka 4.4: P°ehled hodnot kriteriální funkce v inicializa£ním kroku pro vybrané skladby
4.3
Kvalita generovaných hudebních skladeb
Následující sekce se jiº nezam¥°uje na kvalitu algoritmu shlukování, ale na kvalitu generovaných skladeb. D·raz je zde kladen na samotné generované hudební stopy a je diskutována vhodnost melodií vzhledem k originálním hudebním stopám, ze kterých jsou generovány. Ukázky pouºité v této sekci byly vybrány tak, aby byly postiºeny jak sloºité rytmické a melodické prvky, tak jednoduché hudební postupy. Mezi komplexní hudební skladby jsou zde po£ítány písn¥ se zpívaným doprovodem ur£ené k b¥ºnému poslechu. Jednoduché skladby jsou reprezentovány písn¥mi ur£enými k doprovodným ú£el·m (nap°íklad podkresová hudba k lm·m £i po£íta£ovým hrám). V²echny zde uvedené p°íklady jsou k dispozici v hudební podob¥ na p°iloºeném pam¥´ovém médiu. 4.3.1
Jednodu²²í skladby
Za ú£elem ilustrace funk£nosti programu byly, jako p°íklady jednodu²²ích skladeb, vybrány dv¥ podkresové písn¥ z po£íta£ové hry F inal F antasy . Jsou to skladby T o Zanarkand a Adventure. Jsou to pom¥rn¥ jednoduché hudební celky obsahující malý po£et stop. První skladba (T o Zanarkand) obsahuje pouze dv¥ stopy, které se navzájem dopl¬ují. Skladba Adventure obsahuje t°i stopy, ale pro p°ehlednost byla vynechána basová linka, která je velice jednoduchá a nemá na kvalitu vygenerované stopy p°íli² velký vliv. Od kaºdé této skladby jsou k dispozici t°i ukázky vygenerovaných stop. Obrázek má vºdy následující formát:
• První stopa je programem vygenerovaná hudební linka. • Druhá stopa je p°edloha pro vygenerovanou hudební linku. • T°etí stopa je doprovodná linka, která byla pouºita pro generování první stopy, ale nebyla p°ímou p°edlohou.
4.3.1.1 Final Fantasy - To Zanarkand Na obrázcích 4.8, 4.9 a 4.10 jsou vyobrazeny t°i p°íklady vygenerovaných hudebních stop. Z obrázk· je patrné, ºe vygenerované hudební linky (formát obrázk· je popsán v p°edcházející sekci) pom¥rn¥ dob°e zachovávají pravidla "p°íjemných" hudebních motiv·. Vý²ky tón· dvou
4.3.
KVALITA GENEROVANÝCH HUDEBNÍCH SKLADEB
47
sousedních dob nejsou v p°íli² velkém odstupu a nemají mezi sebou disharmonické intervaly. Stejn¥ tak i délky trvání sousedních dob jsou konzistentní. Vliv operátoru k°íºení na takto krátkých úryvcích není p°íli² patrný. Vliv muta£ních operátor· je naopak patrný ve vysoké mí°e. Nap°íklad na obrázku 4.8 je v taktu £íslo sedm dob°e viditelné rozd¥lení p·vodního tónu do t°ech tón· t°etinové délky. Zachovávání motiv· z p·vodní stopy je pom¥rn¥ dob°e patrné z obrázku 4.9, kde ve druhém taktu do²lo k rozd¥lení p·vodního tónu do t°ech r·zných tón·. Pátý a sedmý takt z·staly zachovány v p·vodní podob¥ a celý tak £íslo dev¥t se posunul o sedm p·ltón· níºe. Zachování rytmických prvk· je zase dob°e patrné z obrázku 4.10. Zde z·staly takty £íslo dva, t°i, sedm a dev¥t se stejným po£tem a délkami tón· jako v p·vodní skladb¥. Do²lo zde v²ak k posunu vý²ek tón·. Drobné nedostatky jsou vid¥t na obrázku 4.8 v t°etím a jedenáctém taktu a na obrázku 4.9 v osmém taktu, kde do²lo k pom¥rn¥ výraznému skoku ve vý²kách tón·.
Obrázek 4.8: P°íklad 1: Vygenerovaná hudební stopa - To Zanarkand
Obrázek 4.9: P°íklad 2: Vygenerovaná hudební stopa - To Zanarkand
4.3.1.2 Final Fantasy - Adventure Dal²í ukázkou je skladba Adventure z po£íta£ové hry F inal F antasy . Vygenerované hudební linky si je moºné prohlédnout na obrázcích 4.11, 4.12 a 4.13.
48
KAPITOLA 4.
TESTOVÁNÍ
Obrázek 4.10: P°íklad 3: Vygenerovaná hudební stopa - To Zanarkand
Obrázek 4.11 je zajímavý hned z n¥kolika d·vod·. Takty £íslo jedna a dev¥t jsou totoºné a je velká ²ance, ºe vznikly jako produkt k°íºení. Také takty t°i a £ty°i jsou, aº na drobnou obm¥nu, zp·sobenou mutací vý²ky jednoho tónu, totoºné. Stejn¥ tak takty dva a p¥t jsou rytmicky totoºné a li²í se pouze vý²kami tón·. Viditelný je zde i vliv doprovodné linky. Takty jedna aº p¥t doprovodné linky jsou patrn¥ p°edlohou takt·m jedna, t°i, £ty°i, sedm a dev¥t nov¥ vygenerované linky. P·vodní linka se nejspí²e stala p°edlohou takt·m dva, p¥t, ²est a osm, které mají sloºit¥j²í rytmickou strukturu. Navíc zde nejsou pozorovány, aº na £tvrtý tón druhého taktu, závratn¥j²í výkyvy ve vý²kách tón·. U pokusu na obrázku 4.12 se zdá, ºe se významn¥j²í £ástí podílela na vygenerování nové stopy doprovodná stopa, a ne stopa p°edlohy. Takty dva a p¥t se zdají být produktem p°edlohové stopy. Naopak ostatní takty více korespondují s doprovodnou linkou. Dva totoºné takty jedna a t°i, spole£n¥ s velice podobným taktem osm, patrn¥ vznikly modi kací taktu ²est doprovodné linky. V této stop¥ nejsou pozorovatelné ºádné zvlá²tní výkyvy vý²ek tón· nebo skok· v rytmice. Poslední pokus, vyobrazený na obrázku 4.13, vykazuje podobné vlastnosti, jako pokus na obrázku 4.12. Ani zde v²ak nejsou pozorována významná naru²ení rytmické ani melodické stránky hudební linky.
Obrázek 4.11: P°íklad 4: Vygenerovaná hudební stopa - Adventure
4.3.
KVALITA GENEROVANÝCH HUDEBNÍCH SKLADEB
49
Obrázek 4.12: P°íklad 5: Vygenerovaná hudební stopa - Adventure
Obrázek 4.13: P°íklad 6: Vygenerovaná hudební stopa - Adventure
4.3.2
Komplexní skladby
K vytvo°ení ukázek komplexních skladeb je pouºita skladba od skupiny Bon Jovi (jiº vý²e zmín¥ná skladba Say it isn0 t so). Dále je pouºit jazzový standard Autumn leaves. Jako poslední je vybrána píse¬ Dream on od skupiny Aerosmith. Z d·vodu velkého mnoºství stop v n¥kterých skladbách je, pro p°ehlednost, na jejich obrázcích zobrazena pouze vygenerovaná stopa spolu s originální stopou. Tam, kde je to moºné, jsou vyobrazeny v²echny hrané stopy.
4.3.2.1 Bon Jovi - Say it isn't so Vygenerované stopy spole£n¥ s originálními stopami jsou vyobrazeny na obrázcích 4.14 a 4.15. Jde o dv¥ r·zné £ásti dvou r·zných stop. Z obrázk· je dob°e viditelné, ºe program dokáºe vytvo°it, alespo¬ na první pohled, výraznou melodickou linku i z pom¥rn¥ monotónní stopy (pomocí ostatních stop skladby). Je zde vid¥t jak zachovávání originálních motiv·, tak vytvá°ení nových motiv·. Na obrázku 4.14 se projevuje zachovávání motiv· nap°íklad v taktu £íslo 24, který je v podstat¥ (aº na posun o 14 p·ltón· vý²e a vypu²t¥ní pátého a
50
KAPITOLA 4.
TESTOVÁNÍ
²estého tónu) totoºný jako v originální stop¥. Kreativita programu je vid¥t v taktech jedna, t°i a £trnáct, které jsou v²echny variací na úvodní motiv v prvním taktu originální stopy. V pokusu na obrázku 4.15 je zachován p·vodní motiv (aº na posun o 12 p·ltón·) v taktu £íslo 62. Nep°íznivým d·sledkem velkého po£tu stop ve skladb¥ je, ºe vygenerovaná melodická linka je mén¥ kompaktní neº u jednodu²²ích skladeb. Program má k dispozici mnoho moºností, jak volit vý²ky tón·, a to se nep°ízniv¥ podepisuje na "líbivosti" melodie. Problém se nejvíce projevuje v taktech, kde vý²ky tón· oscilují, jako nap°íklad v taktech 27 aº 29 na obrázku 4.14. Tento problém lze °e²it manuální úpravou vygenerované hudební stopy, protoºe nejde o p°íli² £astý jev. Co se tý£e rytmické stránky, je pozorovatelná tendence programu udrºovat u vygenerované stopy podobný rytmus jako u originální stopy. Tímto dochází k vytvo°ení doprovodné linky k originální stop¥, ale navíc je moºné originální stopu nov¥ vygenerovanou linkou nahradit a vytvo°it tak novou variaci na p·vodní píse¬.
Obrázek 4.14: P°íklad 7: Vygenerovaná hudební stopa - Say it isn't so
4.3.
KVALITA GENEROVANÝCH HUDEBNÍCH SKLADEB
51
Obrázek 4.15: P°íklad 8: Vygenerovaná hudební stopa - Say it isn't so
4.3.2.2 Jazzový standard - Autumn leaves V tomto p°ípad¥ je vyobrazena (obr. 4.16) pouze vygenerovaná linka (originální stopa obsahuje p°íli² sloºit¥ zapsaná opakování a bylo by nutné ji uvést celou). Kombinací kytarové a klavírní linky vznikla pom¥rn¥ kompaktní hudební stopa bez velkých skok· ve vý²kách tón·. Hudební motiv, který se zde projevil jako "dobrý", je viditelný v taktu £íslo ²estnáct. Tento motiv se v p·vodní stop¥ nevyskytuje a musel proto vzniknout jako produkt evolu£ního procesu. Zárove¬ je kriteriální funkcí pozitivn¥ ohodnocen, protoºe se vyskytuje ve více £ástech skladby i n¥kolikrát po sob¥. Co se tý£e melodie, je patrn¥j²í vliv klavírní linky originální písn¥ (ta slouºila jako p°edloha k vygenerování). Rytmická £ást této linky je tém¥° bez chyby. Délky dob dob°e korespondují s rytmikou p·vodní písn¥. Drobným problémem, jak jiº bylo zmín¥no u p°edchozích pokus·, jsou vý²ky tón·. Ty ob£as tvo°í disharmonické intervaly a tím i "nelibozvu£né" motivy. To je patrné nap°íklad v taktu £íslo 25, kde poslední tón spole£n¥ s p°edposledním vytvá°ejí nep°íli² p°íjemný postup. e²ením by op¥t byla drobná manuální úprava vygenerované hudební linky.
4.3.2.3 Aerosmith - Dream on Na obrázku 4.17 je výsledek posledního pokusu. Tato vygenerovaná linka je melodicky libozvu£ná po dobu prvních devíti takt·. V této £ásti dob°e dopl¬uje origináln¥ hrající stopu. Desátý takt obsahuje tóny, které vytvá°í disharmonické intervaly (konkrétn¥ jde o pátý a ²estý tón taktu). Dal²í takty jsou jiº nelibozvu£né jak melodicky, tak rytmicky. To z toho d·vodu,
52
KAPITOLA 4.
TESTOVÁNÍ
Obrázek 4.16: P°íklad 9: Vygenerovaná hudební stopa - Autumn leaves
ºe v dané pasáºi hraje najednou velké mnoºství nástroj· velice rozdílné motivy. Algoritmus v tu chvíli vybírá tony z velké mnoºiny, coº vede k nekompaktnosti a nelibozvu£nosti této £ásti vygenerované skladby.
Obrázek 4.17: P°íklad 10: Vygenerovaná hudební stopa - Dream on
4.4.
4.4
SHRNUTÍ VÝSLEDK
53
Shrnutí výsledk·
Pro implementaci práce byly pouºity metody strojového u£ení (konkrétn¥ £áste£n¥ interaktivní genetický algoritmus za podpory algoritmu shlukování), které spole£n¥ dokáºí generovat hudebn¥ zajímavé motivy, vhodné pro dal²í zpracování. Skladby je nutné po b¥hu programu dále manuáln¥ upravit a provést drobné korekce vý²ek tón·, pop°ípad¥ jejich délek. Z uvedených výsledk· vyplývá, ºe program se lépe hodí ke generování doprovodných linek k jednodu²²ím skladbám, které neobsahují velké mnoºství stop (optimální mnoºství jsou dv¥ aº p¥t stop). Pokud originální skladba obsahuje naopak jednu jedinou stopu s monotónní melodickou linkou, program není schopen vygenerovat melodicky bohatou stopu. Program nemá problém ani se sloºit¥j²ími skladbami. U nich v²ak hrozí riziko, ºe skladba nebude libozvu£ná v celé své délce. V takovém p°ípad¥ je vhodné provést více b¥h· programu s danou skladbou a výsledky poskládat do jedné, libozvu£né linky, která bude obsahovat z kaºdého b¥hu pouze vhodné £ásti.
54
KAPITOLA 4.
TESTOVÁNÍ
Kapitola 5
Záv¥r Tato práce popisuje pr·b¥h analýzy, návrhu, vývoje a testování aplikace generující hudební doprovody. Aplikace na£te data v podporovaném hudebním formátu (MusicXML, MusicString, GuitarPro, TuxGuitar) a p°evede je do interní reprezentace (formát JFugue MusicString). Uºivatel si z dostupných hudebních stop vybere jednu stopu, která podstupuje proces evoluce s pouºitím £áste£n¥ interaktivního genetického algoritmu s podporou shlukování. Algoritmus shlukování je zde pouºit, aby co nejvíce zkrátil £as nutný k interaktivnímu ohodnocení. Výsledkem tohoto evolu£ního algoritmu je vygenerovaná doprovodná linka, která m·ºe být pouºita k nahrazení originální stopy (vytvo°ení variace na danou píse¬), jako doprovod p·vodní písn¥, £i k doprovázení p·vodní hudební stopy. Moºným roz²í°ením aplikace by mohla být implementace dodate£ných algoritm· shlukování, pop°ípad¥ kriteriálních funkcí, aby bylo moºné porovnat jejich efektivitu. Dal²ím moºným roz²í°ením by mohlo být, na vyºádání uºivatele, umoºn¥ní p°ístupu nejen k prototyp·m shluk·, ale i ke v²em ostatním prvk·m konkrétních shluk·. Dále by bylo vhodné (kv·li £asové náro£nosti) automatizovat generování skladeb tak, aby bylo moºné na vstup programu vloºit více skladeb, které by byly zpracovány sekven£n¥. Mezivýsledky b¥h· by byly ukládány do adresá°ové struktury (kaºdá iterace by m¥la vlastní adresá°) a uºivatel by mohl pokra£ovat v b¥hu tou iterací, která se mu zdála nejvhodn¥j²í.
55
56
KAPITOLA 5.
ZÁV
R
Literatura [1] ALFONSECA, M. A Simple Genetic Algoritmh for Music Generation by means of Algorithmic Information theory. Evolutionary Computation, 2007. CEC 2007. 2007, s. 30353042. [2] BENE², M. Programování s vlákny, http://www.cs.vsb.cz/benes/vyuka/pte/texty/vlakna/index.html. [3] BERNARD, B. Úvod do architektury http://www.zdrojak.cz/clanky/uvod-do-architektury-mvc/.
26.4.2013.
MVC,
[4] BILES, J. A. GenJam: A Genetic Algorithm for Generating Jazz Solos. the 1994 International Computer Music Conference. 1994, s. 131137.
7.5.2009.
Proceedings of
[5] BILES, J. A. Genjam populi: Training an Iga via Audience-mediated Performance. In Proceedings of the 1995 International Computer Music Conference. 1995, s. 347348. [6] CHRISTOPHER D. MANNING, H. S. P. R. Introduction to chapter 16 - Flat clustering. Cambridge University Press, 2008.
Information Retrieval,
[7] MILANO, P. Úvod do algoritm· shlukování, 13.2.2013. http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html. [8] MILANO, P. Kmeans clustering algorithm, 20.4.2013. http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/kmeans.html. [9] FRANKEL-GOLDWATER, L. Computers Composing Music: An Artistic Utilization of Hidden Markov Models for Music Composition. Independent Study. 2005, s. 111. [10] GROSSBERG, S. Recurrent neural networks, http://www.scholarpedia.org/article/Recurrent_neural_networks.
2013.
[11] HAYKIN, S. Feedforward neural networks: An Introduction, 26.4.2013. http://media.wiley.com/product_data/excerpt/19/04713491/0471349119.pdf. [12] HOLLAND, J. H. Úvod do genetických algoritm·, http://www2.econ.iastate.edu/tesfatsi/holland.gaintro.htm.
13.2.2013.
[13] HOOVER, A. K. NEAT Drummer: Interactive Evolutionary Computation for Drum Pattern Generation. Technical Report TR-2007-03. 2007, s. 15. 57
58
LITERATURA
[14] HORD¥J£UK, V. Tovární t°ída (Factory), http://voho.cz/wiki/informatika/oop/navrhovy-vzor/factory/.
27.4.2013.
[15] JOHANSON, B. GP-Music: An Interactive Genetic Programming System for Music Generation with Automated Fitness Raters. In Third Annual Conference on Genetic Programming. 1998, s. 181186. [16] KELLER, R. M. Impro-visor - software ke generování jazzových sól, 15.5.2012. http://www.cs.hmc.edu/~keller/jazz/improvisor/. [17] KLéMA, J. Cluster analysis - formalism, algorithms, 2013. VUT - course AE4M33SAD - Strojové u£ení a analýza dat. [18] KLéMA, J. Cluster analysis - advanced and special algorithms, 2013. VUT - course AE4M33SAD - Strojové u£ení a analýza dat. [19] KOELLE, D. JFugue: http://www.jfugue.org/.
Java
API
for
Music
[20] KOELLE, D. Using the JFugue http://www.jfugue.org/jfugue-chapter2.pdf.
Programming,
9.2.2013.
MusicString,
9.3.2013.
[21] KUBALíK, J. Evolutionary algorithms: Genetic programming, http://cw.felk.cvut.cz/doku.php/courses/a4m33bia/start.
2013.
[22] LAW, E. H. H. Towards music tness evaluation with the hierarchical SOM. Evo'08 Proceedings of the 2008 conference on Applications of evolutionary computing. 2008, s. 443452. [23] LEP², M. Moderní metody optimalizace - Genetické programování, 2013. http://klobouk.fsv.cvut.cz/~leps/teaching/mmo/prednasky/prednaska12_GP.pdf. [24] MATIC, D. A genetic algorithm for composing music. Research. 2010, s. 157177.
Yugoslav Journal of Operations
[25] MILAN SORF, D. N. M. F. Úvod do neuronových sítí, 7.5.2013. http://cyber.felk.cvut.cz/gerstner/biolab/bio_web/teach/FunBio/neuron/neursite.html. [26] MOORE, A. W. Regression and Classi cation with Neural Networks, 2001. http://www.autonlab.org/tutorials/neural13.pdf. [27] ORACLE. Callable rozhraní pro práci s vlákny, 26.4.2013. http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/Callable.html. [28] ORACLE. Executors - framework pro soub¥ºné programování, 26.4.2013. http://docs.oracle.com/javase/tutorial/essential/concurrency/executors.html. [29] ORACLE. Runnable - rozhraní pro práci s vlákny, 26.4.2013. http://docs.oracle.com/javase/7/docs/api/java/lang/Runnable.html. [30] RASHID, S. F. Document and Content Analysis, 30.6.2011. Lecture 8 - Classi cation with Neural Networks.
59
LITERATURA
[31] ROJAS, R.
Neural Networks: A systematic introduction
. Springer, 1996.
[32] SCHMIDT, A. Multilayer Neural Network, http://www.teco.uni-karlsruhe.de/~albrecht/neuro/html/node18.html.
2000.
[33] SCHMIDT, A. A Single Layer Neural Network, http://www.teco.uni-karlsruhe.de/~albrecht/neuro/html/node17.html.
2000.
[34] SIMON, I. MySong: Automatic Accompaniment for Vocal Melodies, 13.2.2013. http://research.microsoft.com/en-us/um/people/dan/mysong/. [35] VOGEL, L. Java concurrency (multi-threading) - tutorial, http://www.vogella.com/articles/JavaConcurrency/article.html.
9.4.2013.
[36] WIKIPEDIA. K-medoids, 20.4.2013. http://en.wikipedia.org/wiki/K-medoids. [37] YUNI XIA, B. X. Conceptual Clustering Categorical Data with Uncertainty, 25.4.2013. http://cs.iupui.edu/~yxia/Publications/ICTAI07_COBWEB.pdf.
60
LITERATURA
P°íloha A
Seznam pouºitých zkratek HMM Hidden Markov Models SOM Self-Organizing Map HSOM Hierarchical SOM CPPN Compositional Pattern-Producing Network MIDI Musical Instrument Digital Interface NEAT NeuroEvolution of Augmenting Topologies MVC Model-View-Controller PAM Partitioning Around Medoids
61
62
PÍLOHA A.
SEZNAM POUITÝCH ZKRATEK
P°íloha B
Kon gurace testovacího stroje • OS: Windows 7 Professional, 64 bit • Procesor: Intel Core i5-3210M CPU - 2,50GHz • Opera£ní pam¥´: 4GB
63
64
PÍLOHA B.
KONFIGURACE TESTOVACÍHO STROJE
P°íloha C
Uºivatelská p°íru£ka Aplikaci není nutné instalovat. Sta£í ji spustit p°íkazem z p°íkazové °ádky
java -jar Music_generator.jar Po zavolání tohoto p°íkazu se otev°e okno (obr. C.1) vyzývající uºivatele k výb¥ru vstupního souboru ve vhodném formátu.
Obrázek C.1: Na£tení vtupního souboru
Podporované hudební formáty:
• *.gp3, *.gp4, *.gp5 • *.musicstring • *.xml
65
66
PÍLOHA C.
UIVATELSKÁ PÍRUKA
Po vybrání vstupního souboru je soubor zpracován a uºivateli se objeví výzva (obr. C.2) k výb¥ru hudební stopy, která podstupuje evolu£ní proces.
Obrázek C.2: Výb¥r hudební stopy
Pomocí kláves Ctrl, Shif t nebo pravým tla£ítkem my²i lze vybrat více hudebních stop najednou. Tla£ítkem P layer se vyvolá okno p°ehráva£e (obr. C.3), ve kterém je moºné vybrané stopy p°ehrát. Výb¥r hudební stopy se provádí pomocí tla£ítka Select tracks nebo dvojím kliknutím levého tla£ítka my²i na °ádek p°íslu²né stopy.
Obrázek C.3: Okno p°ehráva£e
67 Vybráním stopy je uºivatel p°esm¥rován do okna výb¥ru parametr· evolu£ního procesu. Toto okno sestává ze t°í záloºek. První záloºka Initialization (obr. C.4) obsahuje inicializa£ní parametry programu. Druhá záloºka Clustering (obr. C.5) obsahuje parametry shlukování a t°etí záloºka P opulation sampling (obr. C.6) obsahuje parametry pro generování nových populací. Na záloºce Initialization uºivatel m·ºe zvolit hudební nástroj, který generovanou stopu p°ehrává, inicializa£ní hodnotu pro náhodný generátor (vhodné pro reprodukci výsledk· pokus·), velikost populace evolu£ního algoritmu, algoritmus pro vytvá°ení iniciální populace, typ genotypu jedinc· populace a tónový ltr (pouºitý pro generování hudebních stop s tóny hranými v originální stop¥). Záloºka Clustering obsahuje parametry shlukování. Zde uºivatel m·ºe vybrat algoritmus shlukování a jeho parametry. Pokud to algoritmus ke svému b¥hu vyºaduje, uºivatel m·ºe zvolit po£et shluk·, které algoritmus shlukování generuje, hodnotu prahu podobnosti dvou jedinc·, metriku pro generování matic vzdáleností a metodu výb¥ru prototyp· shluk·. Na poslední záloºce uºivatel m·ºe vybrat algoritmus pouºitý pro vytvá°ení nových populací ve smy£ce evolu£ního procesu. Tla£ítkem Start evolution dojde k vytvo°ení iniciální populace a uºivateli jsou nabídnuty prototypy shluk· k ohodnocení (obr. C.7).
Obrázek C.4: Inicializa£ní parametry
68
PÍLOHA C.
UIVATELSKÁ PÍRUKA
Obrázek C.5: Parametry shlukování
V horní £ásti okna jsou parametry exportu prototyp· shluk·. Prvním parametrem je moºné vybrat, které stopy se exportují do souboru. Na výb¥r jsou následující moºnosti:
• ALL_BU T _ORIGIN AL - exportuje v²echny stopy, v£etn¥ generované, která nahradí originální stopu. • REP RESEN T AN T _ON LY - exportuje pouze generovanou stopu • REP RESEN T AN T _W IT H _SELECT ED_P ART - exportuje pouze generovanou stopu spolu s p·vodní stopou • ALL_T RACKS - exportuje v²echny stopy v£etn¥ té generované Dále je moºné vybrat jméno exportovaného souboru a jeho formát. Podporované formáty pro export jsou:
• *.gp5 (GuitarPro) • *.tg (TuxGuitar) • *.xml (MusicXML) • *.ly (Lilypond) • *.musicstring (JFugue 4 MusicString)
69
Obrázek C.6: Parametry vytvá°ení nových populací
V prost°ední £ásti okna je set°íd¥ný seznam shluk·. Kaºdý záznam p°edstavuje jeden shluk. ádek reprezentující shluk obsahuje informace o vzdálenosti prototypu shluku od referen£ního jedince, po£et jedinc· ve shluku a index prototypu. Prototyp·m a jejich shluk·m je moºné zm¥nit po°adí tím, ºe je uºivatel vybere pomocí levého tla£ítka my²i a pak pomocí tla£ítek na pravé stran¥ okna (U p a Down) zm¥ní jejich po°adí. Stejný postup lze aplikovat pomocí pravého tla£ítka a kontextového menu. Prototyp shluku je moºné p°ehrát vybráním °ádku prototypu a stiskem tla£ítka P lay , dvojitým kliknutím levého tla£ítka my²i na p°íslu²ný °ádek shluku nebo pomocí pravého tla£ítka my²i a kontextového menu P lay . Export prototypu probíhá pomocí tla£ítka Export nebo op¥t p°es pravé tla£ítko my²i výb¥rem menu Export. Uºivatel je poté dotázán na cestu k adresá°i, kam má být exportovaný soubor uloºen. Ve spodní £ásti okna uºivatel m·ºe nastavit, kolik iterací evolu£ního algoritmu prob¥hne mezi sou£asným a následujícím interaktivním ohodnocením populace. Tla£ítkem P erf orm iterations je spu²t¥na smy£ka evolu£ního procesu. Uºivatel je informován o postupu evoluce pomocí vyskakovacího okna (obr. C.8). V tomto okn¥ je moºné pomocí tla£ítka Interrupt proces evoluce p°eru²it, av²ak uºivatel musí po£kat, dokud nedob¥hne aktuáln¥ provád¥ná iterace.
70
PÍLOHA C.
UIVATELSKÁ PÍRUKA
Obrázek C.7: Ohodnocení iniciální populace
Obrázek C.8: Postup evolu£ního procesu
P°íloha D
Obsah p°iloºeného CD . --- examples
--- project ---------
-----------------
aerosmith_dream_on.gp4 bon_jovi_say_it_isnt_so.gp5 diverzita.zip Final Fantasy 10 - To Zanarkand v1.gp4 Final_Fantasy_Adventure.gp4 Jazz Excercises - Autumn Leaves v1.gp3 kvalita.zip rem_losing_my_religion.gp3
--- Music_generator.jar --- Music_generator.zip README.txt run_linux.sh run_windows.bat text --- jalovkar-thesis-2013.pdf --- jalovkar_thesis.zip
71
