(R)evoluční hudba: genetické algoritmy, multiagentní systém a hudební kompozice

Daniel Kvak

Genetické algoritmy jsou souborem populačně orientovaných heuristik, které se využívají pro hledání série možných řešení. V praxi tyto postupy operují s populací jedinců (agentů), kde každý jednotlivec představuje potenciálně optimální řešení. Populace agentů je podmnožinou prohledávaného prostoru možných řešení. Na počátku dochází k inicializaci prvotní populace, a to buď stochasticky, nebo jinou heuristickou metodou. 1 Nejpoužívanější strategií je výběr ruletovým kolem, tato metoda ovšem často doplácí na předčasnou konvergenci. Pravděpodobnostní univerzální vzorkování vybírá stochasticky pouze první vzorek, další vzorky jsou vybírány s přihlédnutím k fitness hodnotě.

Každému agentovi je přiřazen parametr biologické zdatnosti (fitness), který vyjadřuje jeho vhodnost z hlediska kriteriální funkce. 2 ZELINKA, I. Evoluční výpočetní techniky: principy a aplikace. Praha: BEN, 2009. ISBN 80-7300-218-3. Hodnota fitness popisuje, zdali agent disponuje náležitými předpoklady pro zachování populace. V našem případě fitness definuje melodickou, harmonickou a hlasovou zdatnost. Stručně řečeno, tato referenční hodnota určuje jakýsi tónový atraktor. Harmonická zdatnost bere v úvahu souzvuk akordu, zatímco hlasová zdatnost měří, zda jsou tóny uvnitř uživatelem zadaného intervalu.

Genetické algoritmy lze, stejně jako jiné heuristiky inspirované přírodními jevy, klasifikovat jako iterativní algoritmy. Během iteračního procesu je část stávající populace nahrazena novou, přičemž jedinci s nejvyšší biologickou zdatností jsou zachováni. V tento moment nastává reprodukce agentů, během které dochází ke křížení a mutaci genetických operátorů (v tomto případě se jedná o změny genetického kódu, který sestává z bitové sekvence).

 

Optimalizace kriteriální funkce

Mutací agentů ovlivňujeme nejen kvalitu výstupních dat, ale především vstupní váhy naší sítě. Adaptaci vstupních hyperparametrů sledujeme pomocí grafu funkce, který označujeme názvem loss function (chybová, popř. kriteriální funkce). Graf si můžeme představit jakožto mapu všech možných existujících vah (a tedy i řešení), kdy naším cílem je najít globální minimum této funkce. V tomto extrému nabývá naše síť optimálních vstupních hodnot, s čímž se pojí i nejnižší možná chybovost. Pohyb po chybové funkci je definován jako konvergence k minimu téže funkce. Optimalizační proces jednotlivých agentů se nazývá gradientní sestup. 3 BURIAN, P. Webové a agentové technologie. Praha: Grada, 2012. Průvodce (Grada). ISBN 978-80-247-4376-9.

 

Vyjma umístění jediného optimálního řešení do výše popsaného prohledávacího prostoru mají genetické algoritmy širší úkol: nalézt více řešení, které bychom mohli označit za optimální, zajímavé, či dokonce neočekávané. Ve většině otázek přírodních věd by tento popis nedával smysl, ale z estetického hlediska neexistuje jediné optimum, nýbrž sada nových, zajímavých a neočekávaných řešení. 4 BENTLEY, P. J. Exploring Component-based Representations – The Secret of Creativity by Evolution? In: PARMEE, I. C. Evolutionary Design and Manufacture [online]. London: Springer London, 2000, s. 161–172 [cit. 2020-04-04]. DOI: 10.1007/978-1-4471-0519-0_13. ISBN 978-1-85233-300-3. Dostupné z: http://link.springer.com/10.1007/978-1-4471-0519-0 Můžeme ovšem argumentovat, že samotný proces hudební kompozice je v jistém smyslu simulace optimalizace k jedinému globálnímu minimu. V batesonovsko-mendelovské genetice užíváme výraz epistáze. Ta definuje situaci, kdy je působení jednoho genotypu nadřazeno jinému. Dominantní genotyp pak potlačuje projev jiného genu. 5 CORDELL, H. J. Epistasis: what it means, what it doesn’t mean, and statistical methods to detect it in humans. Human Molecular Genetics [online]. 11(20), 2463–2468 [cit. 2020-04-04]. DOI: 10.1093/hmg/11.20.2463. ISSN 14602083. Dostupné z: https://academic.oup.com/hmg/article-lookup/doi/10.1093/hmg/11.20.2463 Abychom tento problém parafrázovali pro naše užití: optimalizace k jedinému minimu by vedla k potlačení jiných řešení, což je v našem případě nežádoucí jev.

Vytvoření nové kompozice je pro genetické algoritmy nelehkým úkolem, jelikož výstupní soubor musí mimo jiné dodržovat set estetických a funkčních norem. Problémem těchto cílů je jejich vágní vymezení: naše přesvědčení inklinují k subjektivitě. Co to ovšem znamená v praxi? Vodítkem globálních heuristik může být multi-objektivita, která ovšem v mnohých případech nedokáže jednoznačně podmínit vyhledávací prostor a navazuje na problém tzv. předčasné konvergence. Tento termín popisuje stav, kdy řešení konverguje příliš brzy, a my tak uvázneme v suboptimálním řešení (tedy náš agent se nedostane do „údolí“ funkce). 6 YANG, X. Nature-inspired metaheuristic algorithms. 2nd ed. Frome: Luniver Press, 2010. ISBN 9781905986286.

 

Virtuální svět skladatelů a kritiků

Agentní model můžeme využít jako teoretickou validaci muzikologického přístupu k evoluční teorii hudby. Počítačová simulace může být navíc užitečná jako demonstrace vývoje hudebních teorií. Peter M. Todd v roce 1999 vytvořil model pracující na bázi agentů různé taxonomie: skladatelů a kritiků. 7 GRIFFITH, N. a P. M. TODD. Musical networks: parallel distributed perception and performace. Cambridge, Mass.: MIT Press, c1999. ISBN 978-0262071819. Zatímco skladatelé mají za úkol vytvářet melodie, kritici tyto melodie hodnotí a následně se rozhodují, s kým navážou reprodukci. Algoritmus využívá virtuální formu selektivního tlaku, aby podpořil evoluci vhodných skladatelů melodií. Tento model čerpá inspiraci z ptačího světa, kdy někteří pěvci používají melodie k přilákání partnera k páření.

V tomto modelu disponuje každý agent-skladatel setem not v rozsahu dvou oktáv. Agenti-kritici využívají Markovův řetězec, pomocí kterého hodnotí přechody mezi jednotlivými notami. Řetězec představuje matici o velikosti 24 × 24, přičemž každý prvek uvádí míru očekávání následující noty. Kritik po poslechnutí „skladby“ hodnotí, jestli byla skladba překvapující, a udělí jí hodnocení. Každý kritik si poslechne určité množství skladatelů a následně si vybere „partnera“ pro reprodukci.

Zajímavostí tohoto modelu je, že k dosažení vysokého skóre musí skladatel nejprve vzbudit očekávání, poté toto očekávání porušit. Existuje tedy neustálé napětí mezi předpokládanou posloupností a momentem překvapení, ale vysoce ohodnoceny jsou pouze neočekávané přechody. Tento selektivní proces zajišťuje, že do další generace postoupí genotyp reprezentující nejkvalitnější tónový atraktor. Taxonomie potomků je vybrána náhodně a třetina populace je následně odstraněna. 8 Tamtéž. Tento model názorně využívá Darwinův princip přežití silnějšího, tzv. survival of the fittest, díky čemuž může podpořit vývoj koherentních repertoárů melodií ve virtuálním světě agentů. Problémem tohoto modelu může být striktnost kritiků, kteří jen slepě následují set pravděpodobností a jejich výchylek užitím koeficientů Markovova řetězce. Proto si zkusme položit jinou otázku. Je možné navrhnout systém s inicializovaným očekáváním?

 

Virtuální svět hráčů a imitátorů

Cílem modelu, který navrhnul Eduardo Reck Miranda, je dokázat, že malá komunita interaktivních distribuovaných agentů, vybavených vhodnými motorickými, sluchovými a kognitivními schopnostmi, může ze sdíleného repertoáru vyvinout vlastní set melodií. V tomto případě nebudou melodie kódovány v genech agentů, ani nebude docházet k jejich reprodukci. 9 MIRANDA, E. R. At the Crossroads of Evolutionary Computation and Music: Self-Programming Synthesizers, Swarm Orchestras and the Origins of Melody. Evolutionary Computation [online]. 2004, 12(2), 137–158 [cit. 2020-04-05]. DOI: 10.1162/106365604773955120. ISSN 1063-6560. Dostupné z: http://www.mitpressjournals.org/doi/10.1162/106365604773955120

Motivací racionálních agentů je ve svých „vzpomínkách“ vytvářet repertoár melodií a navazovat sociální vztahy s jinými agenty ve virtuálním světě. Aby byl agent společenský, musí disponovat repertoárem, který je podobný repertoáru jeho vrstevníků. Míra společenského chování je proto posuzována z hlediska podobnosti repertoáru agentů. 10 Tamtéž, s. 148. Kromě schopnosti produkovat a slyšet zvuky se agenti rodí se základním instinktem: napodobují to, co slyší.

Náš agent se skládá ze tří hlavních modulů: percepce, kognice a kontroly motoriky. Percepční modul monitoruje signály z dispečeru zpráv a identifikuje události, které se jej týkají, například akce vzaté z virtuálního světa a změny stavu. Modul kognice interpretuje vstup, který získá z percepčního modulu, vybere příslušné cíle, zkonstruuje a provede plány vedoucí ke splnění cílů a odešle příkazy k motorické jednotce. Motorická jednotka následně rozloží signály do série nízkoúrovňových příkazů, které odešle do jiných komponentů za pomoci generátoru příkazů. 11 RICKEL, J. a W. L. JOHNSON. Animated agents for procedural training in virtual reality: Perception, cognition, and motor control. Applied Artificial Intelligence [online]. 1999, 13(4–5), 343–382 [cit. 2020-04-05]. DOI: 10.1080/088395199117315. ISSN 0883-9514. Dostupné z: http://www.tandfonline.com/doi/abs/10.1080/088395199117315

Agenti disponují setem variabilních modulů:

1. Hlasovým syntetizátorem, který je implementován jako fyzický model lidského hlasového mechanismu.
2. Sluchovým aparátem, který využívá autokorelaci k analýze proneseného signálu.
3. Paměťovým zařízením, které popisuje vzpomínky agenta. Tyto vzpomínky můžeme z dnešního praktického pohledu definovat jako LSTM (Long Short-Term Memory) bloky. 12 Jedná se model speciálních paměťových buněk, které disponují forget bránou. Díky tomu se může příslušný neuron rozhodnout, které informace jsou relevantní a které může vypustit. Výstupní hodnoty neuronu mají vliv na vstupní hyperparametry (konkrétně synaptické váhy) sítě.
4. Normativním skriptem, který v pseudokódu vyjádříme takto:

 

Imitace je definována jako proces poslechnutí melodie a aktivace motorického systému k jeho reprodukci. Když říkáme, že agenti by měli vyvíjet sdílený repertoár melodií, máme na mysli, že percepční reprezentace v paměti agentů by měla být identická, ale motorická kontrola se může lišit. Důležitým předpokladem tohoto modelu je, že činnost vytváření melodií zahrnuje aktivaci určitých mechanismů hlasového motoru rozdílným způsobem. 13 MIRANDA, E. R. At the Crossroads of Evolutionary Computation and Music: Self-Programming Synthesizers, Swarm Orchestras and the Origins of Melody. Evolutionary Computation [online]. 2004, 12(2), 149 [cit. 2020-04-05]. DOI: 10.1162/106365604773955120. ISSN 1063-6560. Dostupné z: http://www.mitpressjournals.org/doi/10.1162/106365604773955120

 

Závěr

Zdá se, že genetické algoritmy pojí s kreativitou ve světě algoritmického generování zvláštní vztah. V této spojitosti se ovšem vyskytuje i řada komplikací, jelikož povaha kreativního obsahu je odlišná od jiných otázek přírodních věd: optimalizace musí zahrnovat estetické parametry, které lze jen obtížně vyjádřit matematickým modelem. Částečné řešení nalézáme v míře biologické zdatnosti agentů, jak můžeme sledovat v modelu Petera M. Todda. Tento model, pracující s agenty různé taxonomie: skladateli a kritiky, je schopen vytvářet smysluplná řešení, avšak je korelačně závislý na kvalitě učících dat a evaluaci pomocí Markovova řetězce.

Mimetický model, navržený Eduardem R. Mirandou, nabízí odlišný přístup ke genetickým algoritmům. Namísto reprodukce a křížení agenti disponují sdíleným repertoárem melodií a setem různých modulů, které slouží k analýze, autokorelaci a imitaci. Výhodou tohoto modelu je zanedbání agentů-kritiků, namísto toho jsou racionální agenti schopni odvozovat korelace přímo ze vstupních dat a předávat si tyto informace imitací sociálního chování.

Genetické algoritmy využíváme nejen tam, kde je požadovaná úloha příliš komplexní na to, aby byla popsána analytickými formulemi nebo hrubou silou, ale především v rámci multimodální optimalizace – tedy pokud hledáme více než jedno optimální řešení. Právě globálně orientované heuristiky s populací agentů nabízejí určitou teoretickou validaci muzikologického přístupu k teorii evoluční hudby. Tyto metody samozřejmě nabízejí pouze zanedbatelný přínos pro rozvoj muzikologie, to ovšem nemusí platit pro opačný směr.

 

Shrnutí

Genetické algoritmy jsou heuristické postupy, které napodobují principy evoluční biologie při hledání optimálního řešení v komplexním prostředí. Dynamika těchto metod ve spojení s vysokou imitační schopností multiagentních systémů tvoří silné výpočetní paradigma, které nachází své využití především v kreativních oborech. Tato práce se věnuje praktické implementaci optimalizačních metod pro generování melodií a odkrývá mechanismy selektivního procesu.

 

Resumé

Genetic algorithms are heuristic procedures imitating the principles of evolutionary biology in search of an optimal solution in a complex environment. The dynamics of these methods combined with the high imitation ability of multiagent systems creates a strong computing paradigm utilized mostly in creative fields. This paper deals with the practical implementation of optimization methods for generating melodies and reveals the mechanisms of the selection process.

 

 

Klíčová slova

evoluční hudba, evoluční muzikologie, multiagentní systém, genetické algoritmy, biologická zdatnost

 

Přehled zdrojů

Obrazové přílohy:

Obr. 3: Rosenbrock function. Wikipedia [online]. 2009. Dostupné z: https://en.wikipedia.org/wiki/Rosenbrock_function

 

Seznam použité literatury:

BURIAN, Pavel. Webové a agentové technologie. Praha: Grada, 2012. Průvodce (Grada). ISBN 978-80-247-4376-9.

GRIFFITH, Niall a Peter M. TODD. Musical networks: parallel distributed perception and performace. Cambridge, Mass.: MIT Press, c1999. ISBN 978-0262071819.

VOLNÁ, Eva. Introduction to Soft Computing. London: Bookboon, 2013. ISBN 978-87-403-0391-9.

VOLNÁ, Eva. Umělá inteligence: rozpoznávání vzorů v dynamických datech. Praha: BEN – technická literatura, 2014. ISBN 9788073005146.

YANG, Xin-She. Nature-inspired metaheuristic algorithms. 2nd ed. Frome: Luniver Press, 2010. ISBN 9781905986286.

ZELINKA, Ivan. Evoluční výpočetní techniky: principy a aplikace. Praha: BEN, 2009. ISBN 80-7300-218-3.

 

Elektronické zdroje:

BENTLEY, Peter J. Exploring Component-based Representations – The Secret of Creativity by Evolution? In: PARMEE, I. C.: Evolutionary Design and Manufacture [online]. London: Springer London, 2000, s. 161–172 [cit. 2020-04-04]. DOI: 10.1007/978-1-4471-0519-0_13. ISBN 978-1-85233-300-3. Dostupné z: http://link.springer.com/10.1007/978-1-4471-0519-0

CORDELL, H. J. Epistasis: what it means, what it doesn’t mean, and statistical methods to detect it in humans. Human Molecular Genetics [online]. 11(20), 2463–2468. DOI: 10.1093/hmg/11.20.2463. ISSN 14602083. Dostupné z: https://academic.oup.com/hmg/article-lookup/doi/10.1093/hmg/11.20.2463

FIEBRINK, Rebecca a Baptiste CARAMIAUX. The Machine Learning Algorithm as Creative Musical Tool. Handbook on Algorithmic Music [online]. Oxford: Oxford University Press, 2016. Dostupné z: https://www.researchgate.net/publication/309631691_The_Machine_Learning_Algorithm_as_Creative_Musical_Tool

MILLER, Geoffrey F. a Peter M. TODD. Exploring Adaptive Agency I: Theory and Methods for Simulating the Evolution of Learning. Connectionist Models [online]. Elsevier, 1991, s. 65–80. DOI: 10.1016/B978-1-4832-1448-1.50013-5. ISBN 978-1-4832-1448-1. Dostupné z: https://linkinghub.elsevier.com/retrieve/pii/B9781483214481500135

MIRANDA, Eduardo Reck. At the Crossroads of Evolutionary Computation and Music: Self-Programming Synthesizers, Swarm Orchestras and the Origins of Melody. Evolutionary Computation [online]. 2004, 12(2), 137–158. DOI: 10.1162/106365604773955120. ISSN 1063-6560. Dostupné z: http://www.mitpressjournals.org/doi/10.1162/106365604773955120

RICKEL, Jeff a W. Lewis JOHNSON. Animated agents for procedural training in virtual reality: Perception, cognition, and motor control. Applied Artificial Intelligence [online]. 1999, 13(4–5), 343–382. DOI: 10.1080/088395199117315. ISSN 0883-9514. Dostupné z: http://www.tandfonline.com/doi/abs/10.1080/088395199117315

TODD, Peter M. A Connectionist Approach to Algorithmic Composition. Computer Music Journal [online]. 1989, 13(4). DOI: 10.2307/3679551. ISSN 01489267. Dostupné z: https://www.jstor.org/stable/3679551?origin=crossref

Strany 19-25/2020