Orquestração Musical Usando um Sistema Imunitário Artificial

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Orquestração Musical Usando um Sistema Imunitário Artificial José Miguel Lima de Abreu Mestrado Integrado em Engenharia Eletrotécnica e de Computadores Orientador: Rui Penha Coorientador: Marcelo Caetano 27 de Outubro de 2015 Resumo Neste trabalho pretendeu-se implementar e avaliar o uso de algoritmos inspirados por processos biológicos na resolução de problemas de orquestração musical. Neste contexto, define-se a orquestração musical assistida por computador como sendo um problema de otimização combinatória em que o objetivo reside na combinação de registos tímbricos de instrumentos diferentes de maneira a que o resultado final se aproxime, ou mesmo se iguale, a um timbre designado pelo utilizador. A resolução deste problema manualmente acarreta um elevado conhecimento musical pelo que, através do uso de ferramentas computacionais, pretende-se auxiliar o utilizador nesta tarefa de combinação de registos tímbricos. Implementações prévias para a resolução deste tipo de problemas apresentam algumas limitações no que toca à diversidade de soluções produzidas e à abordagem do timbre sonoro como fenómeno multidimensional. Neste trabalho foi inicialmente desenvolvida uma implementação de um algoritmo genético que foi posteriormente aplicada a um modelo teórico do problema de orquestração. O mesmo modelo foi também aplicado a um sistema imunitário artificial para comparação e análise dos resultados obtidos e validação do modelo teórico desenvolvido. Devido ao uso de um sistema imunitário artificial, o sistema de orquestração proposto oferece várias soluções ótimas simultaneamente, colmatando um dos principais problemas nas abordagens prévias ao problema de orquestração. Os resultados obtidos foram submetidos a uma avaliação percetiva utilizando um teste de escuta. Os dados da avaliação permitiram concluir que o sistema desenvolvido apresenta um bom desempenho na orquestração de sons musicais, com algumas limitações. Os dados permitiram também concluir que as funções desenvolvidas para a classificação de aptidão das soluções refletem razoavelmente bem a similaridade entre sons. Resultados preliminares deste trabalho foram apresentados no 1oCongresso Doutoral em Engenharia realizado na Faculdade de Engenharia da Universidade do Porto [1]. i ii Abstract This work aimed to implement and evaluate the use of algorithms inspired by biological processes in musical orchestration problems. In this context computer-aided musical orchestration is defined as a combinatorial optimization problem in which the objective is to combine different timbral records of different instruments such that the end result approaches a designated timbral record. The manual resolution of this problem requires a high musical knowledge. Computational tools pretend to aid the user in this task of combining timbral records. Previous implementations to the resolution of this kind of problems have some limitations regarding the diversity of the solution set and the approach to the timbre as a multidimensional phenomenon. In this work it was initially developed an implementation of a genetic algorithm which was subsequently applied to a theoretical model of the orchestration problem. The same model was applied to an artificial immune system for comparison and analysis of the results and validation of the developed theoretical model. Due to the use of an artificial immune system the proposed orchestration system offers several optimum solutions simultaneously, addressing one of the main problems of the previous approaches to the orchestration problem. The results obtained were subjected to a perceptual evaluation using a listening test. The data from the evaluation allowed to conclude that the system developed has, with some limitations, a good performance in the orchestration of musical sounds. The obtained data allowed also to conclude that the developed functions used to classify the aptitude of the solutions reflect reasonably well the similarity between sounds. Preliminary results of this work were presented at the 1st Doctoral Congress in Engineering held at Faculty of Engineering of University of Porto [1]. iii iv Agradecimentos Com a finalização deste trabalho termino uma longa jornada iniciada 5 anos atrás quando me inscrevi pela primeira vez na Faculdade de Engenharia da Universidade do Porto no Mestrado de Engenharia Eletrotécnica e de Computadores. Nestes 5 anos expandi o meu conhecimento numa área que sempre gostei e para além disso adquiri novas amizades que irão permanecer ao longo da minha vida. Foram certamente os melhores anos que já vivi. Em primeiro lugar, gostaria de agradecer aos meus pais por me terem facultado a possibilidade de estudar numa das melhores universidades deste país e por terem estado sempre ao meu lado, apoiando-me nos bons e nos maus momentos. Sei que os sacrifícios foram muitos e espero um dia poder retribuir. Sei também que sem eles certamente não estaria neste momento a escrever este texto. Um muito obrigado. Agradeço também aos restantes elementos da minha família por todo o apoio e incentivo incessável. Em segundo lugar, agradeço aos meus colegas de casa no Porto pela amizade e pelos bons momentos que vivemos. Foram anos muito felizes onde foram criadas memórias que irão permanecer para toda a vida. Ao Franco, Hugo, Ivo e Meira um muito obrigado pela amizade, pelo apoio e pelos bons momentos que passamos todos juntos. Em terceiro lugar, não poderia deixar de agradecer aos meus colegas de faculdade que partilharam esta jornada comigo. Obrigado Garcia, Guilherme, Iria, Pereira, Tó e Zulu pelos bons anos, desejo tudo de bom e muita sorte quer a nível profissional quer a nível pessoal. Espero que as vossas amizades me acompanhem pelo resto da minha vida. Finalmente, um agradecimento especial a todos os docentes que acompanharam a minha jornada nesta faculdade. Um agradecimento especial também aos meus orientadores pela paciência e disponibilidade que tiveram ao longo da realização deste trabalho. Obrigado a todos. José Miguel Lima de Abreu v vi “Music expresses that which cannot be put into words and that which cannot remain silent.” Victor Hugo vii xiv LISTA DE TABELAS Abreviaturas e Símbolos AG Algoritmo Genético RMS Root Mean Square RWC Real World Computing SIA Sistema Imunitário Artificial SWIPE Sawtooth Waveform Inspired Pitch Estimator WAV Waveform Audio File Format xv Capítulo 1 Introdução 1.1 Contexto O processo criativo e a capacidade de inovação são caraterísticas inerentes de todos os seres humanos e uma das qualidades mais importantes da nossa espécie distinguindo-nos das máquinas e dos algoritmos que são, na sua maioria, regidos por regras e determinismo. Estas mesmas máquinas fazem atualmente parte do nosso quotidiano, logo, torna-se natural o surgimento de interesse em aplicações que facilitem o processo criativo e que, talvez num futuro próximo, substituam o fator humano na totalidade dotando efetivamente uma máquina de criatividade. Igualmente importante, e difícil, à criação de originalidade é a capacidade de reconhecimento da mesma. Ambas partilham de aspetos que estão ligados a perceções sensoriais e que são dificilmente expressos em medidas objetivas dificultando uma formalização detalhada destes processos no domínio computacional. Assim, e apesar da constante evolução no mundo tecnológico e científico, a criação artística continua a ser uma área fortemente dominada pela criatividade humana existindo um interesse cada vez maior em explorar a ligação entre arte e ciência. No caso da criação musical, a investigação decorrente em torno de computação e síntese sonora têm vindo a providenciar aos compositores, musicólogos e entusiastas ferramentas poderosas para a manipulação e geração de diversos sons musicais, desde simples tons ou notas até peças complexas e partituras. Com a evolução do poder computacional disponível para os utilizadores deste tipo de ferramentas, a interação com os mesmos têm vindo a tornar-se cada vez mais diminuta, podendo este ser apenas responsável por especificar os parâmetros iniciais e julgar o resultado final. No entanto, e apesar da elevada capacidade de processamento disponível atualmente, vários problemas surgem na implementação destes sistemas, especialmente no julgamento autónomo dos parâmetros estéticos dos resultados produzidos. 1.2 Especificação Nesta área de investigação podem ser especificados dois domínios diferentes e independentes que diferem quanto à complexidade do resultado produzido e aos parâmetros iniciais fornecidos: 1 2Introdução o domínio de geração musical e o domínio de manipulação musical. As técnicas presentes nestes domínios utilizam diferentes algoritmos para atingir os resultados pretendidos, residindo em cada uma delas um objetivo comum: produzir o maior número possível de resultados que, por um lado, sejam úteis ao utilizador e que, por outro lado, apresentem características únicas, numa tentativa parca de simular o processo criativo utilizando uma aplicação computacional. O domínio de geração musical apresenta técnicas de síntese sonora e composição algorítmica. Ambas são utilizadas para a geração de novos sons, composições ou músicas e diferem essencialmente na complexidade do resultado produzido: Na síntese sonora o resultado é um conjunto de sons individuais, enquanto que, na composição algorítmica o resultado é uma peça musical ou partitura. Neste domínio são ainda incluídas técnicas de orquestração musical assistida por computador, que pode ser definida como a tarefa de combinar registos tímbricos de instrumentos diferentes, de maneira a que o resultado final se aproxime, ou mesmo se iguale, a um timbre designado pelo compositor [3]. Por outro lado, o domínio de manipulação musical incluí técnicas de sound morphing emashup que são utilizadas na manipulação de sons ou músicas existentes e permitem a um determinado utilizador alterar um som ou música de maneira a obter uma nova variação dos mesmos, ou mesmo combinar vários sons num só, assim como combinar diferentes partes de músicas numa só. No caso de sound morphing, um ou mais sons iniciais são combinados dando origem a um novo som, enquanto que no mashup várias músicas são combinadas para produzir uma nova música. 1.2.1 Orquestração Musical A orquestração relaciona-se com a técnica de compor peças musicais para uma orquestra musical. A prática desta técnica necessita que o compositor conheça as propriedades dos diferentes instrumentos que compõem a orquestra e as sonoridades que advêm de cada um. No contexto deste trabalho considera-se a orquestração musical como um problema combinatório em que se pretende organizar determinados instrumentos de forma a obter um registo tímbrico específico. Para tal, recorreu-se a ferramentas computacionais para auxiliar este processo de organização de forma a autonomizar o funcionamento do mesmo. Nos problemas de orquestração musical assistida por computador pretende-se aproximar um determinado registo tímbrico de um som utilizando combinação de registos tímbricos de outros sons. O registo tímbrico que se pretende aproximar é especificado pelo compositor e os sons que podem ser utilizados na combinação pertencem ao leque de sons produzidos pelos instrumentos tipicamente presentes numa orquestra musical. A resolução deste problema manualmente acarreta um elevado conhecimento musical. Efetivamente um compositor com pouca experiência na resolução deste tipo de problemas não sabe, à partida, qual será o timbre resultante da combinação de um som com outro, e mesmo compositores com elevada experiência encontram por vezes dificuldades em obter um registo tímbrico específico. Para além da experiência necessária, a orquestração musical é também um processo iterativo, sendo que, na maior parte das vezes o compositor acrescenta sucessivamente instrumentos, de forma a obter um registo tímbrico uniforme e que seja 1.2 Especificação 3 Som 1 Som 2 . . . Som N Som Orquestrado ≈ Som Objetivo Figura 1.1: Orquestração musical assistida por computador: a tarefa de combinar registos tímbricos de diferentes instrumentos de forma a que o resultado final se aproxime a um timbre designado próximo do objetivo. Na figura 1.1 apresenta-se um diagrama com os objetivos da orquestração musical assistida por computador. A sonoridade de cada instrumento numa orquestra é única, apresentando características sonoras que variam conforme o instrumento e conforme o estilo de interpretação realizado pelo músico. A variedade de sons que cada instrumento consegue produzir é de tal forma alta, que se torna praticamente impossível a um compositor reter todas estas variações. É este o principal problema quando se pretende orquestrar um som manualmente. Por vezes, um determinado registo tímbrico até pode ser aproximado razoavelmente bem através de orquestração manual. No entanto, neste processo de aproximação uma grande parte das combinações possíveis não são consideradas podendo ser assim descartadas soluções com uma similaridade maior com o objetivo. A orquestração musical com recurso a ferramentas computacionais pretende auxiliar o compositor nesta tarefa de combinação de registos tímbricos de forma a aproximar um registo tímbrico objetivo. Neste tipo de ferramentas o julgamento das combinações é feito autonomamente, sendo que o compositor apenas necessita de avaliar as soluções produzidas, colmatando-se o principal problema da orquestração manual através da pesquisa automática de soluções próximas do objetivo. Com este processo de pesquisa, e com o elevado poder computacional disponível atualmente, é possível percorrer eficientemente as diversas possibilidades existentes quando são considerados os diversos instrumentos de uma orquestra e as sonoridades criadas por cada um. Tais sistemas, apesar de serem eficientes no processo de pesquisa, não o são, por vezes, no processo de julgamento das soluções obtidas. Efetivamente várias considerações sobre o timbre como fenómeno sonoro multidimensional devem ser levadas em conta na especificação de funções que avaliem a similaridade entre sons. 4Introdução 1.2.2 Computação Inspirada por Processos Biológicos As técnicas de criação musical com recurso a ferramentas computacionais apresentam em comum um vasto espaço de soluções possíveis que devem ser julgadas e selecionadas autonomamente pelo sistema, apresentando como resultado um conjunto restrito de soluções que tenham utilidade ao utilizador. Devido ao grande número de parâmetros que podem ser considerados na criação dos elementos musicais, algoritmos tradicionais de pesquisa não são particularmente eficientes na resolução destes problemas. Esta lacuna pode ser colmatada através do recurso a algoritmos de otimização ligados à área da inteligência computacional. Estes algoritmos oferecem um mecanismo que permite percorrer simultaneamente o espaço de soluções existente, oferecendo ao mesmo tempo uma rápida velocidade de convergência para valores ótimos. As soluções propostas por estes algoritmos são melhoradas a cada iteração, sendo que os resultados convergem para um conjunto de valores que maximizam ou minimizam determinadas funções de avaliação, responsáveis por quantificar a utilidade dos mesmos. Efetivamente a definição destas funções de avaliação é o problema de maior envergadura neste tipo de sistemas por não ser ainda claro como é que o julgamento dos parâmetros estéticos pode ser automatizado [4]. Uma descrição mais detalhada do funcionamento destes algoritmos é feita no capítulo 3. A aplicação destes algoritmos no domínio da criação musical impulsionou uma abordagem informatizada ao processo de composição e síntese sonora. Mais recentemente, e utilizando modelos analíticos que descrevem diferentes elementos musicais, tornou-se possível a implementação de ferramentas automatizadas que assistem o processo de composição musical. Ao nível da síntese sonora foram propostas implementações que utilizam algoritmos genéticos [5] e sistemas imunitários artificiais [6]. Utilizando estes algoritmos, foram também propostas implementações de composição algorítmica recorrendo a algoritmos genéticos [7] [8], sistemas imunitários artificiais [9] e mapas auto organizáveis [10] [11] [12]. A variedade de ferramentas que podem ser criadas com estes algoritmos é praticamente ilimitada. Em [8] por exemplo, Biles propõem o GenJam (genetic jammer), uma aplicação de composição algorítmica interativa com capacidade de improvisar solos de Jazz recorrendo a um algoritmo genético. O GenJam é capaz de produzir solos autonomamente, assim como interagir com o compositor ou banda através da resposta a sons produzidos por estes. Outra aplicação de composição algorítmica recorrendo também a algoritmos genéticos é proposta no Vox Populi [7]. Nesta aplicação um número pré-definido de acordes é gerado e evoluído de forma a maximizar um critério de avaliação baseado em fatores físicos relevantes à perceção sonora. Os acordes gerados podem ser posteriormente utilizados pelo compositor numa progressão musical. A variedade de algoritmos existentes que são inspirados por processos biológicos, o seu bom desempenho em problemas de otimização com um grande número de parâmetros e o elevado poder computacional disponível atualmente têm vindo a contribuir assim no desenvolvimento de ferramentas cada vez mais poderosas na resolução de problemas que eram previamente exclusivos do domínio humano e criativo. Com estas novas abordagens, a composição musical e a síntese sonora englobam uma perspetiva em que o espaço de combinações possíveis é praticamente ilimi- 1.3 Objetivos 5 tado, dependendo em última instância do compositor a mestria dos elementos produzidos por estas ferramentas na criação de novas e inovadoras composições artísticas. Por fim é importante realçar que, apesar da boa eficácia destes algoritmos em problemas de otimização multidimensional, uma correta formalização teórica das características do problema a abordar patenteia a fundação mais importante para a obtenção de soluções úteis ao utilizador. 1.3 Objetivos Neste trabalho implementou-se e avaliou-se o uso de algoritmos inspirados por processos biológicos em problemas de orquestração musical. Inicialmente foi feita uma implementação de um algoritmo genético, tendo em conta as diferentes características sonoras que devem ser consideradas na avaliação de sons musicais. Foi posteriormente desenvolvido um modelo teórico, fundamentando o problema da orquestração numa perspetiva analítica. Este modelo foi aplicado num algoritmo genético de forma a demonstrar a sua validade, precedido de uma exploração e aplicação num sistema imunitário artificial inspirado na aiNet [13]. Após a aplicação deste modelo nos dois algoritmos propostos, foi feita uma comparação analítica e subjetiva dos resultados obtidos de forma a determinar as principais vantagens e possíveis limitações da utilização destes algoritmos e do modelo proposto. Uma introdução mais aprofundada aos conceitos de orquestração é feita no capítulo 2, onde são detalhados os principais desafios deste tipo de problema e são revistas as soluções já desenvolvidas. São também introduzidos alguns fundamentos teóricos que constam no modelo de orquestração desenvolvido. Resultados preliminares do trabalho desenvolvido foram apresentados no 1oCongresso Doutoral em Engenharia realizado na Faculdade de Engenharia da Universidade do Porto. A participação envolveu a escrita de um artigo [1] e a realização de um poster cujo conteúdo refletiu o trabalho desenvolvido até à data de realização deste congresso. 1.4 Estrutura Este documento contém mais 6 capítulos. No capítulo 2, é feita uma revisão aos conceitos de orquestração, apresentadas as implementações existentes e resumidas as vantagens e limitações de cada uma. No capítulo 3, são descritos os princípios da computação inspirada por processos biológicos e são introduzidos algoritmos baseados nesta linha de pesquisa. No capítulo 4, é descrito o modelo teórico desenvolvido para o problema de orquestração musical. No capítulo 5, apresenta-se a solução desenvolvida e a arquitetura do sistema de orquestração. No capítulo 6, são apresentados os resultados obtidos nos testes de escuta às soluções obtidas. Por fim, no capítulo 7, é feita a conclusão e descritos os principais aspetos que podem ser melhorados no sistema desenvolvido. 6Introdução Capítulo 2 Orquestração Musical Atualmente existe uma grande variedade de ferramentas computacionais que auxiliam compositores no processo de criação e exploração musical. A maior parte destas ferramentas providencia estruturas primitivas que são depois combinadas pelo compositor num nível crescente de complexidade até ser atingido o resultado final pretendido. Este processo, apesar de se basear em métodos computacionais para a criação das estruturas primitivas, apresenta uma grande componente manual, deixando à responsabilidade do compositor a combinação e integração das diferentes estruturas e dos seus registos tímbricos. A manipulação das estruturas primitivas por meios computacionais é uma área cada vez mais explorada e mais recentemente as evoluções em inteligência artificial, e em particular na área de computação evolutiva, oferecem mecanismos que permitem lidar com um grande número de parâmetros e soluções. Este tipo de algoritmos foi já aplicado com sucesso na resolução de problemas em áreas como engenharia, biologia e economia, e foi proposto em diversas implementações de criação musical, incluindo problemas de orquestração. 2.1 Definição O objetivo da orquestração musical com recurso a ferramentas computacionais é o de auxiliar o utilizador na tarefa de combinar autonomamente os registos tímbricos de diferentes instrumentos de forma a que o resultado final se aproxime, ou mesmo se iguale, a um timbre designado pelo utilizador. A complexidade deste método pode ser melhor percebida tendo em conta que uma orquestra é composta por um grande número de instrumentos diferentes, com características únicas e sonoridades que dependem do estilo musical e do músico que as interpreta. Estes fatores, quando combinados, geram um espaço de sonoridades praticamente ilimitado que pode ainda ser estendido se considerarmos os fatores sonoros que advêm do posicionamento dos instrumentos na orquestra e os fenómenos acústicos do local físico em que a orquestra se encontra [3]. Na prática, apenas um reduzido número destas combinações são relevantes ao utilizador que pretende obter um registo sonoro específico. Nesses casos o problema de orquestração deve ter em 7 14 Computação Inspirada por Processos Biológicos refinamento de soluções. Do ponto de vista criativo, estes algoritmos oferecem ferramentas poderosas na resolução de problemas com um grande espaço de soluções possíveis e apresentam resultados diversificados através do uso de incerteza no processo de otimização. 3.1 Computação Evolutiva O ramo da computação evolutiva engloba um conjunto de métodos inspirados na teoria de evolução de Darwin tendo sido propostos pela primeira vez nos anos 50 ([28], [29], [30]). Nestas abordagens propostas o conceito de evolução é utilizado como meio de otimização das soluções, sendo que cada problema é resolvido através da evolução dos indivíduos de uma espécie por meios de reprodução e mutação. Apesar da facilidade de integração destes algoritmos na resolução de diversos tipos de problemas, existem três componentes importantes que devem ser definidos tendo em conta o problema a lidar: a representação dos indivíduos, a função de avaliação (fitness) e os operadores genéticos a utilizar na otimização. A representação dos indivíduos é feita utilizando um vetor de valores que modelam as características presentes nesse indivíduo. Estes valores representam o material genético de cada indivíduo, ou seja o seu genótipo, manifestado sobre a forma de um fenótipo que corresponde aos valores das diferentes características que esse indivíduo possui. Dependendo do algoritmo a ser usado, esta representação pode ser feita através de um vetor de valores binários, valores reais ou máquinas de estado, e a sua correta escolha na resolução de um problema influencia tanto a qualidade da solução obtida como a velocidade com que o sistema converge para valores ótimos sendo também diretamente responsável pelo espaço de armazenamento ocupado pela população. Após correta representação dos indivíduos é necessário determinar a qualidade de cada um, utilizando para isso funções de fitness que são responsáveis por quantificar numericamente a semelhança das características que cada indivíduo apresenta em relação a um determinado objetivo. Estas funções dependem em larga escala do problema que se pretende abordar e das características avaliadas, devendo ser implementadas tendo em conta a qualidade e resolução pretendidas nas soluções. O último componente a definir é responsável pela evolução dos indivíduos da população constituindo um conjunto de operadores que atuam sobre o genótipo de cada um. Estes operadores simulam geralmente os mecanismos de evolução genética existentes na natureza e realizam operações de mutação, cruzamento e seleção para introduzir diversidade e aumentar a média da qualidade da população. O funcionamento intrínseco envolve parâmetros aleatórios incluindo probabilidades que afetam o número de mutações e o processo de cruzamento e seleção. A escolha dos operadores genéticos neste tipo de sistemas influencia tanto a velocidade com que as soluções evoluem como a diversidade dos indivíduos apresentados na solução. Uma classe particular destes algoritmos, denominados de algoritmos genéticos, é apresentada na secção seguinte constituindo uma abordagem ao panorama da computação evolutiva que foi introduzida por Holland em 1975 [30]. Os algoritmos genéticos são provavelmente a técnica mais 3.1 Computação Evolutiva 15 disseminada na resolução de problemas complexos utilizando computação evolutiva devido aos resultados satisfatórios que apresentam perante um grande número de problemas. 3.1.1 Algoritmos Genéticos Baseados no processo de seleção natural, estes algoritmos otimizam os indivíduos da população através de seleção, mutação e cruzamento das características de cada um, gerando a cada iteração uma nova população que partilha aspetos com a anterior. As características de cada indivíduo são codificadas geralmente sobre a forma de um genoma binário e idealmente apenas os melhores indivíduos de cada geração são designados para cruzamento, mantendo-se assim as características com uma melhor avaliação e introduzindo novas variações na população através de mutações. É esperável que, conforme o número de iterações aumente, a população evolua no sentido de prosperar o valor médio da avaliação dos indivíduos, imitando-se assim o processo de seleção natural em que os indivíduos mais aptos predominam na evolução de uma espécie [31]. A representação dos indivíduos da população pode ser feita usando, como já foi referido, um genoma binário em que as características de cada indivíduo são representadas sobre a forma de um vetor binário, ou utilizando um genoma com um vetor de valores reais. A escolha da representação a utilizar varia conforme o tipo de problema a resolver e deve ser tomada em conta na implementação destes sistemas. Um exemplo do fluxo de execução deste tipo de algoritmos pode ser visualizado no algoritmo 3.1. Algoritmo 3.1: Algoritmo genético clássico Entrada:ns,itern,pc,pm Saída: P P←− inicializa nsindivíduos aleatoriamente; enquanto número de iterações < iternfaça calcula valor de avaliação de cada indivíduo; seleção; cruzamento com probabilidade pc; mutação com probabilidade pm; P←− atualiza nova população; fim 3.1.1.1 Avaliação A avaliação de cada indivíduo é feita recorrendo a funções de avaliação que quantificam a aptidão desse indivíduo. Estas funções atribuem um valor numérico à aptidão que reflete a qualidade da solução representada por esse indivíduo, tomando em conta as suas características codificadas no genoma desse indivíduo. 16 Computação Inspirada por Processos Biológicos 3.1.1.2 Seleção A geração de uma nova população deve ser feita tendo como objetivo a prosperidade do valor médio de aptidão dos indivíduos, para tal, a cada iteração são inicialmente escolhidos os indivíduos que farão parte desta tendo por base a população anterior sobre a qual é aplicada um operador de seleção. O operador de seleção é utilizado nestes algoritmos para determinar quais os indivíduos que irão constituir a próxima geração e geralmente baseia-se num esquema denominado de roulette wheel. Neste esquema é atribuída uma probabilidade de sobrevivência a cada indivíduo que é proporcional à sua avaliação em relação ao somatório da avaliação global da população em que este se insere, desta maneira indivíduos mais aptos apresentam uma probabilidade mais alta de continuarem a pertencer à população enquanto esta evolui. Devido ao não determinismo deste esquema são por vezes utilizadas variações que mantém automaticamente um ou mais indivíduos ao longo das gerações, prevenindo-se assim a possibilidade de perder os indivíduos mais aptos de cada geração devido ao roulette wheel. Estas variações denominam-se de seleção elitista e constituem um conjunto de mecanismos utilizados no operador de seleção. Entre os mecanismos propostos, para além do roulette wheel, encontram-se: Seleção por ranking Esquema semelhante ao roulette wheel, com a diferença de que em vez da probabilidade de seleção ser proporcional ao valor de avaliação, neste esquema é proporcional à posição em que o indivíduo se encontra na população (que está ordenada por valor de avaliação). Seleção por diversidade São selecionados os Nindivíduos mais diversos da população. Seleção bi-classista São selecionados os N psmelhores indivíduos e os N(1−ps)piores indivíduos, com psarbitrário. Seleção aleatória São selecionados aleatoriamente Nindivíduos da população. Neste caso a seleção pode também ser elitista caso um ou mais dos melhores indivíduos sejam automaticamente selecionados. Para além da aplicação no operador de seleção, estes mecanismos podem também ser utilizados na seleção dos indivíduos designados para os processos de mutação e cruzamento, assim como outras variações específicas para determinadas implementações encontradas na literatura destes algoritmos. 3.1.1.3 Cruzamento Já na operação de cruzamento o objetivo é aumentar a qualidade dos indivíduos através do cruzamento das características das soluções consideradas mais aptas na iteração atual. O operador de cruzamento apresenta como principal objetivo o de subir os picos da superfície de fitness através da combinação das características dos indivíduos envolvidos. Geralmente são escolhidos um certo número de indivíduos e o genoma de cada um é recombinado com o genoma de um parceiro dando origem a um ou dois novos indivíduos que apresentam características em comum com os 3.1 Computação Evolutiva 17 seus descendentes. Devido a esta operação os melhores indivíduos contribuem, a cada iteração, para o aumento da média de aptidão da população correspondendo a um aumento na qualidade das soluções obtidas. Este operador apresenta diversas variações na sua implementação sendo que a utilizada mais frequentemente nestes algoritmos é a de cruzamento de um ponto. Nesta variação são selecionados dois indivíduos e a partir da combinação das características de cada um são originados dois novos indivíduos com um genoma constituído pela junção de segmentos do genoma dos indivíduos originais. A determinação dos segmentos é feita através da escolha aleatória de um ponto de corte originando quatro segmentos que são posteriormente combinados e integrados no genoma de dois novos indivíduos. Considere-se, por exemplo, os seguintes indivíduos selecionados para cruzamento e respetivos segmentos determinados: xi={0,1,1,0,1,1,1,0,0} xj={1,0,1,0,0,1,0,1,1} Utilizando cruzamento de um ponto, os genomas dos novos indivíduos serão: x0 i={1,0,1,0,1,1,1,0,0} x0j={0,1,1,0,0,1,0,1,1} Tal como na mutação, o cruzamento do material genético deve respeitar a validade da representação no espaço de pesquisa, restringindo a posição em que o corte é efetuado de maneira a que uma determinada característica não apresente valores errados. Para além do cruzamento de um ponto, foram também propostos: Cruzamento de dois pontos Neste tipo de cruzamento são escolhidas duas posições para o corte dos segmentos, originando três segmentos em cada indivíduo. Cruzamento uniforme Os valores do genoma dos novos indivíduos são escolhidos de um dos dois genomas originais segundo uma determinada probabilidade. Neste caso a combinação de valores por oposição à utilização de segmentos origina indivíduos com uma maior diversidade de características devido à operação de cruzamento não depender da posição dos valores no genoma. Em termos de desempenho não existe nenhuma diferença significativa entre as abordagens propostas. No entanto, algumas são particularmente eficientes numa determinada classe de problemas. Sucintamente, a aplicação de um algoritmo genético na resolução de um problema complexo é um processo adaptativo que deve ter em conta tanto as características que constituem uma solução desejada como o processo que melhor se adequa para as obter. Para além dos mecanismos utilizados para a evolução da população, a avaliação das mesmas é a componente que mais contribui na eficácia destes algoritmos deduzindo-se assim a importância de uma correta implementação destas funções num sistema de computação evolutiva. 18 Computação Inspirada por Processos Biológicos 3.1.1.4 Mutação Para aumentar a diversidade e qualidade dos indivíduos são usadas operações de mutação e cruzamento que operam sobre o genoma de cada um. Na operação de mutação são introduzidas alterações aleatórias no genoma originando modificações nas características que constituem cada indivíduo, estas alterações podem ser vantajosas ou não mas contribuem significativamente para o aumento do espaço de combinações abrangidas pelo algoritmo no processo de pesquisa. O operador de mutação é responsável pela exploração de novas regiões promissoras da superfície de fitness. Esta operação ocorre geralmente com uma probabilidade baixa e corresponde a uma inversão do valor de um gene num ponto aleatório do genoma do indivíduo. Assumindo como exemplo um indivíduo com o seguinte genoma binário: xi={0,1,1,0,1,1,1,0,0} Uma mutação possível seria: x0 i={0,1,0,0,1,1,1,0,0} É importante referir que a operação de mutação, quando ocorre, deve ter em conta a validade do novo indivíduo, ou seja, o novo genoma originado da mutação não deve conter uma representação que seja inválida ao espaço de pesquisa. Este controlo pode ser efetuado quer através de restrições no operador de mutação, quer através de funções que validem posteriormente os novos indivíduos originados por esta operação. Devido à aleatoriedade deste operador garante-se a introdução de características inovadoras na população ao longo do processo de evolução. 3.2 Sistemas Imunitários Artificiais O sistema imunitário biológico é constituído por um conjunto de células, moléculas e órgãos que atuam colaborativamente no processo de manutenção do equilíbrio dinâmico interno de um ser vivo [32]. A complexidade destes sistemas é patente na variedade das caraterísticas que emergem deste, desde a capacidade de distinção de elementos externos ao sistema até ao processo de adaptação e aprendizagem por meios iterativos e evolutivos, incluindo também mecanismos de comunicação entre os vários componentes imunitários que despoletam a ativação ou inibição destes últimos. Esta complexidade inerente dos sistemas imunitários é necessária para a correta realização do seu objetivo primário: proteger o correspondente sistema biológico de substâncias infeciosas que podem prejudicar o normal funcionamento do mesmo [33]. Para a realização dessa proteção o sistema imunitário utiliza mecanismos de imunidade inata e imunidade adaptativa. A imunidade inata baseia o reconhecimento de elementos externos através de informação herdada geneticamente pelo indivíduo e apresenta uma resposta constante e imediata permitindo uma rápida deteção destes elementos. Este mecanismo não apresenta características adaptativas que permitam uma aprendizagem no reconhecimento de novos elementos 3.2 Sistemas Imunitários Artificiais 19 externos. No entanto, oferece um contributo significativo na tarefa de discriminação entre elementos pertencentes ou desconhecidos ao indivíduo. Já na imunidade adaptativa é utilizado um processo iterativo que melhora sucessivamente a resposta a elementos externos através de evoluções nas células responsáveis pelo reconhecimento, permitindo a deteção e aprendizagem de novos elementos não abrangidos pelo mecanismo da imunidade inata. As células que constituem este mecanismo são denominadas de linfócitos e podem ser divididas em células do tipo B e tipo T. Ambas desenvolvem recetores nas suas membranas celulares que são capazes de identificar e de se combinar com moléculas que tenham uma forma ou características semelhantes à do recetor, esta semelhança corresponde ao grau de afinidade e faz parte integrante destes sistemas o objetivo de aumentar este valor através de adaptação e evolução dos recetores presentes nos linfócitos. A geração destes recetores é feita aleatoriamente sendo que o processo de seleção dos mesmos é realizado por um mecanismo de seleção clonal responsável por escolher os recetores que apresentem características particulares, passíveis de possuírem um elevado grau de afinidade com um determinado elemento [34]. Os elementos detetados pelos recetores presentes nos linfócitos variam quanto ao tipo de célula a que estes pertencem: no caso das células do tipo B os recetores destinam-se à identificação de elementos não pertencentes ao indivíduo, enquanto que, no caso das células do tipo T os recetores existentes são responsáveis pela identificação de elementos internos ao sistema imunitário especializados na interação com elementos desconhecidos. As moléculas que são identificadas pelos recetores destas células definem-se como substâncias antigénicas e cada uma apresenta diversos epítopos, correspondentes às regiões sobre as quais os recetores se combinam. A identificação de antigénios pelas células de tipo B opera através da utilização de anticorpos. Os anticorpos são proteínas produzidas e segregadas por estas células em resposta a uma deteção de um elemento antigénio. Estas proteínas reconhecem e combinam-se com um determinado antigénio sendo usadas no sistema imunitário como meio de sinalização entre as diferentes partes responsáveis pela remoção do antigénio. Cada célula do tipo B produz anticorpos diferentes com afinidade destinada a um antigénio específico. As células de tipo T apresentam uma função mais específica no sistema imunitário e são alvo de um processo constante de otimização e maturação consoante o encontro de novos antigénios. O funcionamento destas células colmata o processo despoletado quando os anticorpos se combinam com um determinado antigénio, induzindo a proliferação de novas células capazes de remover o antigénio detetado. As células de tipo T apresentam também características de memorização das respostas aos antigénios detetados permitindo uma evolução gradual na eficácia deste mecanismo. A imunidade inata e imunidade adaptativa operam em conjunto no funcionamento do sistema imunitário num processo complexo e dependente de vários mecanismos que foram inicialmente formalizados em meados do século 20. Inicialmente proposta por Burnet [34], a teoria da seleção clonal é atualmente aceite como a melhor explicação de como o sistema imunitário responde à invasão de elementos externos. Em conjugação com a teoria da maturação de afinidade é possível definir os principais mecanismos necessários ao funcionamento de um sistema imunitário adaptável e evolutivo. 20 Computação Inspirada por Processos Biológicos 3.2.1 Seleção Clonal e Maturação de Afinidade A teoria de seleção clonal proposta por Burnet [34] postula a ideia que, de entre as células pertencentes ao sistema imunitário, apenas aquelas com capacidade para reconhecer antigénios irão proliferar e as restantes serão suprimidas por um mecanismo de seleção. A seleção clonal atua sobre as células B e T, promovendo ou suprimindo a diferenciação de clones destas células segundo o grau de afinidade que apresentam perante antigénios [32]. Durante este processo de clonagem é possível a ocorrência de erros arbitrários, resultando em mutações que influenciam o valor de afinidade com o antigénio reconhecido. Algumas destas mutações originam células com um elevado grau de afinidade, proporcionando ao sistema imunitário uma resposta mais especializada para determinados antigénios. Segundo o mecanismo de seleção clonal, os clones que apresentam um elevado grau de afinidade para com um determinado antigénio serão selecionados e diferenciados em células de memória para referência futura enquanto os restantes serão suprimidos, promovendo-se assim apenas a maturação de células com utilidade ao sistema. Desta maneira, o sistema imunitário evolui o seu mecanismo de defesa iterativamente, adaptando-se a novos antigénios previamente desconhecidos assim que estes são detetados. Através de memorização, uma resposta mais rápida pode ser efetuada quando um antigénio já conhecido é detetado por este sistema. Utilizando esta teoria, De Castro e Zuben propõem em [35] um algoritmo de aprendizagem e otimização baseado nas técnicas de seleção clonal denominado CLONALG. Inicialmente, CLONALG gera um certo número de anticorpos aleatórios, correspondendo cada um a uma solução possível do problema a otimizar. Através de seleção, clonagem e mutação os anticorpos existentes são iterativamente melhorados de forma a otimizar a população existente. 3.2.2 Seleção Negativa A seleção negativa é utilizada no sistema imunitário para a deteção e supressão de células cujos recetores reconhecem erradamente elementos internos como antigénios. Este mecanismo inspirou o desenvolvimento de algoritmos aplicados principalmente na deteção de anomalias e padrões. Assim, tal como no sistema imunitário são suprimidas células com recetores que reconhecem elementos internos, nestes algoritmos as soluções que pertençam a um determinado conjunto são descartadas [36]. 3.2.3 Teoria do Perigo A Teoria do Perigo, proposta por Matzinger em [37], define a resposta imunitária como um processo reativo que é ativado quando é detetado dano nas células do indivíduo. A deteção de dano, e consequente ativação de mecanismos de resposta, é feita através da existência de sinais de auxílio que são segregados por células suprimidas devido a causas não naturais. As aplicações desta teoria incluem principalmente mecanismos de deteção de anomalias, como por exemplo vírus informáticos, transações eletrónicas forjadas ou falhas de hardware [38]. 3.2 Sistemas Imunitários Artificiais 21 3.2.4 aiNet A aiNet (artificial immune network) proposta por De Castro e Von Zuben em [13], é baseada num sistema imunitário artificial combinando o algoritmo CLONALG [35] com a teoria da rede imunitária [39]. Nesta abordagem, os diferentes anticorpos constituem uma rede imunitária em que a clonagem e seleção de cada um é feita proporcionalmente ao seu valor de aptidão e dependendo da interação desse anticorpo com a rede imunitária [40]. Nesta implementação é utilizado também um limiar do grau de afinidade para determinar as células a suprimir em cada iteração. Os resultados do algoritmo criado permitem reduzir a redundância na descrição de estruturas de dados, incluindo a distribuição espacial e relações entre agrupamentos (clusters). A técnica de clustering é especialmente útil em tarefas de exploração de padrões incluindo segmentação de imagem, classificação automática de padrões e data mining. Uma descrição mais detalhada do funcionamento deste algoritmo é apresentada na secção 5.5. 22 Computação Inspirada por Processos Biológicos Capítulo 4 Formalização A complexidade do problema de orquestração musical está patenteada na variedade de interações multidisciplinares necessárias para uma correta formalização analítica deste. Desde a definição de uma função objetivo que capture as características percetivas dos fenómenos sonoros, até à implementação de um algoritmo inspirado por processos biológicos que otimize o espaço combinatório existente, vários aspetos devem ser considerados, tanto numa perspetiva científica e pragmática como numa perspetiva artística e criativa. A definição formal deste problema foi feita com base no trabalho desenvolvido por Carpentier em [18], [17] e [3], sendo descrita neste capítulo. Inicialmente é feita uma apresentação teórica do problema de orquestração e uma breve descrição da base de dados sonora utilizada, seguindose uma enumeração dos descritores utilizados na caracterização e distinção dos diferentes sons presentes na base de dados. Por fim são apresentadas funções de combinação e funções de avaliação de similaridade entre sons. As funções de combinação são responsáveis por calcular os novos valores dos descritores de uma determinada combinação de sons, já as funções de avaliação de similaridade são responsáveis por estimar a similaridade entre uma combinação e um som objetivo. Através da utilização deste conjunto de funções avaliam-se assim as soluções propostas pelos algoritmos de pesquisa. 4.1 Modelo Teórico da Orquestração Musical O objetivo da orquestração musical com recurso a ferramentas computacionais é o de auxiliar o utilizador na tarefa de combinar autonomamente os registos tímbricos de diferentes instrumentos de forma a que o resultado final se aproxime, ou mesmo se iguale, a um timbre designado pelo utilizador. Nestes problemas pretende-se encontrar uma combinação de sons que, quando reproduzidos simultaneamente, se assemelhem o mais possível a um som objetivo pré-especificado. Os sons que podem ser utilizados para as combinações englobam as notas reproduzidas pelos diferentes instrumentos encontrados tipicamente numa orquestra musical. O problema de orquestração 23 30 Formalização O cálculo do espetro é feito em decibéis sendo que para a análise dos picos espetrais é selecionada apenas uma gama de valores entre o máximo absoluto do espetro e -35 dB desse valor. Um exemplo do espetro de um som é apresentado na figura 4.4, com o limite da gama de valores selecionados assinalado na linha a tracejado. A correspondente gama de valores selecionados é apresentado na figura 4.5 e os picos espetrais identificados são apresentados na figura 4.6. 0 0.5 1 1.5 2 x 104 −160 −140 −120 −100 −80 −60 −40 −20 0 Spectrum frequency (Hz) magnitude Figura 4.4: Espetro em decibéis e limite da gama de valores selecionados para o cálculo de picos espetrais a tracejado Para cada gama de valores selecionados do espetro são analisados e identificados os picos que apresentam um valor de amplitude mais alto. A identificação de picos é feita através de comparação dos múltiplos valores do espetro correspondente. Um determinado máximo local é considerado pico se a diferença de amplitudes entre os valores mínimos que o antecedem e precedem forem mais altos que um valor de limiar. Este valor de limiar corresponde a 5% da distância entre o máximo e o mínimo absoluto da gama de valores selecionados do espetro. São identificados no máximo 25 picos espetrais em cada som. Uma identificação dos picos espetrais do espetro da figura 4.4 é apresentada na figura 4.6. Estes picos são utilizados na seleção de sons que podem fazer parte da solução do problema de orquestração. Efetivamente no algoritmo desenvolvido são inicialmente identificados nTpicos espetrais do som objetivo e é de seguida feita uma pesquisa na base de dados por sons que apresentem pelo menos um pico em comum com o objetivo. Os sons que apresentem picos em comum são selecionados para fazerem parte do espaço de pesquisa. O critério de seleção baseia-se num valor relativo em relação à frequência do pico do som objetivo (2.5%). Se o som objetivo apresentar, por exemplo, um máximo espetral na frequência de 1000Hz, então são selecionados para o 4.3 Descritores 31 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 x 104 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.5: Gama de valores selecionados do espetro apresentado na figura 4.4 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 x 104 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.6: Picos espetrais identificados processo de pesquisa sons que apresentem máximos espetrais entre 975 e 1025 Hz, aplicando-se este processo aos restantes picos presentes no som objetivo. Nas figuras 4.7,4.8 e4.9 pode ser observado um exemplo deste processo de seleção. O espetro de um som objetivo é apresentado na 32 Formalização figura 4.7. Este espetro apresenta picos espetrais nas frequências 500, 2500 e 4000 Hz. Na figura 4.8 é apresentado um espetro de um som selecionado para o processo de pesquisa. Este som foi selecionado por apresentar um pico espetral em comum com o som objetivo na frequência 500 Hz. Já na figura 4.9 é apresentado um espetro de um som que não foi selecionado para o processo de pesquisa por não apresentar picos espetrais em comum com o som objetivo. 1000 2000 3000 4000 5000 6000 0 5 10 15 20 25 30 35 X: 500 Y: 20 Spectrum frequency (Hz) magnitude X: 2500 Y: 30 X: 4000 Y: 10 Figura 4.7: Espetro de um som objetivo Após a seleção dos sons que apresentem picos espetrais em comum com o som objetivo é construído um vetor com a contribuição de cada som nos picos do som objetivo. Este vetor permite avaliar a similaridade entre o espetro de diferentes sons e o som objetivo através da comparação da posição em que os picos espetrais se encontram. Assim, para cada som selecionado para o processo de pesquisa é associado um vetor de tamanho nTcujos valores representam a contribuição para cada pico, caso aplicável. Cada contribuição corresponde ao valor da amplitude do pico desse som que é comum ao pico do som objetivo, ou zero caso não exista um pico em comum. Sejam {fT n}as frequências dos picos do som objetivo e seja sium som da base de dados com picos espetrais {fi j}e correspondentes amplitudes {aij}, então o vetor de contribuições construido será: PT si(n) =    aijse,(1+δ)−1≤fi j/fT n≤1+δ 0 em caso contrário (4.7) Em que δé o valor relativo de seleção, igual a 2.5%. Este vetor de contribuições é construído para cada som da base de dados selecionado e reflete a semelhança espetral entre o espetro desse 4.3 Descritores 33 1000 2000 3000 4000 5000 6000 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.8: Espetro de um som selecionado para o processos de pesquisa. O som apresenta um pico espetral em comum com o som objetivo (500 Hz) 1000 2000 3000 4000 5000 6000 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.9: Espetro de um som não selecionado para o processo de pesquisa. O som não apresenta nenhum pico espetral em comum com o som objetivo 34 Formalização som e o espetro do som objetivo. Reflete também a contribuição que cada som providencia para uma determinada zona do espetro. Como exemplo considere-se um som objetivo com picos espetrais nas frequências fTe um som da base de dados com picos espetrais nas frequências fie correspondentes amplitudes ai, tal que: fT={500,2000,3500,4000} fi={500,1000,3500,4000,5000} ai={30,25,15,20,10} Então o vetor de contribuições construido será igual a: PT si={30,0,15,20}(4.8) Este processo de construção do vetor de contribuições pode ser observado nas figuras 4.10, 4.11 e4.12. Na figura 4.10 são apresentados os picos espetrais de um som objetivo. Os picos espetrais de um som selecionado para o processo de pesquisa são apresentados na figura 4.11 e o seu respetivo vetor de contribuições é apresentado na figura 4.12. 1000 2000 3000 4000 5000 6000 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.10: Espetro de um som objetivo 4.3 Descritores 35 1000 2000 3000 4000 5000 6000 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.11: Espetro de um som selecionado para o processos de pesquisa 1000 2000 3000 4000 5000 6000 0 5 10 15 20 25 30 35 Spectrum frequency (Hz) magnitude Figura 4.12: Contribuição do som da figura 4.11 tendo em conta o som objetivo da figura 4.10 36 Formalização 4.3.5 RMS O RMS (Root Mean Square), ou valor eficaz, representa a potência média de um sinal. Neste trabalho, o seu cálculo é feito no domínio das frequências, recorrendo ao teorema de Parseval, resultando em que: RMS =s∑ m X[m] N 2 (4.9) Sendo que X[m]é a transformada discreta de Fourier do sinal a analisar e No número de amostras que esse sinal contem. 4.3.6 Energia O valor de energia de cada sinal x[n]é utilizado na combinação de sons e é calculado utilizando: E=∑ n |x[n]|2(4.10) 4.3.7 Frequência Fundamental A estimação da frequência fundamental de cada som permite auxiliar o algoritmo de pesquisa a reduzir o espaço de pesquisa. Este processo de estimação foi feito utilizando o SWIPE [44]. O SWIPE (Sawtooth Waveform Inspired Pitch Estimator) é um algoritmo de estimação da frequência fundamental de sons que estima a frequência fundamental de um som como sendo a frequência fundamental de uma onda triangular, cujo espetro melhor se aproxima do espetro do sinal de entrada. Após o valor da frequência fundamental ser calculado é possível diminuir o tamanho do espaço de pesquisa através da restrição de que os sons presentes neste espaço devem ter uma frequência fundamental mais alta que a frequência do primeiro pico do som objetivo. Reduz-se assim o número de combinações possíveis que o algoritmo de pesquisa deve analisar. 4.4 Funções de Combinação A combinação de diferentes sons originam novas características que devem ser estimadas e comparadas com o som objetivo. Uma ilustração da tarefa a realizar pelas funções de combinação pode ser encontrada na figura 4.13: a partir de um conjunto de descritores de sons individuais conseguir encontrar o valor dos descritores do correspondente som orquestrado. Assumindo que os registos tímbricos de cada som são combinados num único então o espetro resultante será uma soma das componentes espetrais de cada som que compõem essa combinação normalizados segundo a sua energia [17]. Partindo dessa suposição é possível deduzir as seguintes equações que correspondem aos estimadores dos valores das características do som orquestrado ceo,eeoeiso, composto por lsons diferentes com valores de centróide espetral igual a cei, valores de espalhamento espetral igual a eei, valores de amplitude de picos espetrais iguais a peie energia 4.4 Funções de Combinação 37 Descritores Som 1 Descritores Som 2 . . . Descritores Som N Funções de Combinação Descritores Som Orquestrado Figura 4.13: Funções de combinação total igual a ei: ceo= l ∑ i eicei l ∑ i ei (4.11) eeo=v u u u u u t l ∑ i ei(ce2 i+ee2 i) l ∑ i ei −ce2 o(4.12) iso=20log10 l ∑ i 1 l∑ j pei(j)!(4.13) A estimação dos picos espetrais da combinação é feita através da comparação dos valores da contribuição de cada som nas frequências de interesse. Partindo dos vetores de contribuições dos diferentes sons é feito o cálculo do valor máximo de amplitude para cada frequência. O vetor de picos espetrais da combinação orquestrada é então: PT o(n) = max i∈lPT si(1),max i∈lPT si(2),...(4.14) Como o espetro é calculado em decibéis a utilização do máximo é uma boa aproximação do espetro combinado, no caso dos picos espetrais [17]. Um exemplo do resultado da combinação do espetro de dois sons pode ser observado nas figuras 4.15,4.16 e4.17. 38 Formalização 4.4.1 Avaliação das Funções de Combinação Para validar as funções de combinação descritas foram realizados testes em que um determinado número de sons foram combinados e as suas características medidas. Compararam-se as características medidas para cada combinação com as características calculadas utilizando as funções de combinação. Os resultados obtidos confirmam as funções de combinação como uma boa aproximação dos valores reais das características de uma combinação de sons. Foram realizados testes para a combinação de 2, 3 e 4 sons diferentes, tendo sido cada um dos testes repetido 1000 vezes utilizando sons diferentes. Os valores de erros relativos são apresentados na tabela 4.1 e representam o quão bem as funções de combinação são uma aproximação do valor real dos descritores de um som combinado, ou seja, quanto mais baixo o valor de erro melhor é a aproximação. Assim, uma combinação de sons origina um novo conjunto de descritores e, a partir das funções de combinação, este novo conjunto de descritores pode ser calculado sabendo apenas à partida quais os sons que compõem essa combinação. Neste teste mediu-se a qualidade das funções de combinação através da comparação de valores reais dos descritores de uma combinação (medidos através da combinação manual dos sons e posterior cálculo dos descritores) e de valores estimados pelas funções de combinação (obtidos através da aplicação destas funções). O valor de erro relativo para o centróide espetral, espalhamento espetral e intensidade sonora foi calculado da seguinte forma: admitindo por exemplo um valor de centróide espetral calculado utilizando as funções de combinação cec, e respetivo valor medido cem, então o erro relativo será: e=1−min(cec,cem) max(cec,cem)(4.15) Já no caso dos picos espetrais comparou-se o vetor de picos espetrais construído pelas funções de combinação e o vetor de picos espetrais medido. A comparação foi feita utilizando a distância cosinusoidal (cosine similarity) entre os dois vetores. Assim, e assumindo um vetor de picos espetrais construído pelas funções de combinação pec, e um vetor de picos espetrais medido pem, então o erro relativo será: e=1−cos(pec,pem)(4.16) 2 Sons 3 Sons 4 Sons Centróide Espetral 7.9% (9.1%) 8.3% (8.6%) 7.8% (7.4%) Espalhamento Espetral 10.2% (9.6%) 9.9% (8.8%) 10.0% (8.6%) Intensidade Sonora 2.2% (1.8%) 2.4% (1.7%) 2.8% (1.8%) Picos Espetrais 0.4% (1.9%) 0.2% (1.0%) 0.3% (1.0%) Tabela 4.1: Erro relativo entre características calculadas utilizando as funções de combinação e características medidas da combinação. Em parênteses o desvio padrão do erro relativo. Como pode ser observado, os valores de erro relativo obtidos são significativamente baixos, validando as funções de combinação como uma boa aproximação para o cálculo dos valores das características de uma combinação de sons. 4.5 Funções de Avaliação 39 Descritores Som Orquestrado Descritores Som Objetivo Funções de Avaliação Valor de Aptidão (fitness) Figura 4.14: Funções de avaliação 4.5 Funções de Avaliação Após serem definidas as características utilizadas para diferenciar cada som é necessário a definição de funções que atribuam uma distância numérica entre os diferentes sons. O objetivo das funções de avaliação é ilustrado na figura 4.14: a partir de um conjunto de valores de descritores de um som orquestrado e de um conjunto de valores de descritores de um som objetivo atribuir um valor real que quantifique a similaridade entre estes dois sons. No caso do centróide espetral, do espalhamento espetral e da intensidade sonora é utilizado o desvio absoluto, normalizado segundo o valor da característica do objetivo. Assim, se ceo,eeoeisoforem as características da combinação orquestrada, ceT,eeTeisTas características do som objetivo, então a distância entre estes dois sons é calculada usando: Dce T=|ceo−ceT| ceT (4.17) Dee T=|eeo−eeT| eeT (4.18) Dis T=|iso−isT| isT (4.19) Quanto aos picos espetrais é utilizada a distância cosinusoidal entre o vetor de picos espetrais do som objetivo e o vetor de picos espetrais do som orquestrado. A utilização desta distância permite atribuir um valor numérico à similaridade destes dois vetores, sendo que quanto menor for este valor, mais semelhantes serão os vetores. Esta distância é calculada com: DP T=1−cos(PT o,PT T)(4.20) Estes quatro valores quantificam um vetor multidimensional que avalia a distância de uma combinação ao som objetivo segundo os diferentes descritores escolhidos. Para a utilização dos algoritmos de pesquisa é necessário que estes valores sejam assimilados num único que representa a aptidão (fitness) dessa combinação. Esta combinação de valores é feita atribuindo pesos a cada descritor e somando os valores resultantes. Após refinamento sucessivo no valor dos pesos foram 46 Implementação 2. Uma nota E5, da dinâmica mezzo forte, do instrumento clarinete 3. Uma nota G5, da dinâmica piano, do instrumento flauta Índice Ficheiro ... ... 10 /Violino/Forte/C5.wav ... ... 350 /Violoncelo/Mezzo/F5.wav ... ... 1275 /Clarinete/Mezzo/E5.wav ... ... 1414 /Flauta/Piano/G5.wav ... ... Tabela 5.1: Exemplo de índices e nomes de ficheiros da base de dados 5.3 Pré-Processamento Utilizar todos os sons disponíveis como soluções válidas para o problema de orquestração iria aumentar em grande escala a dimensão do espaço de pesquisa existente. Para reduzir o tamanho deste espaço de pesquisa é feito um pré-processamento sobre o som objetivo, extraindo-se as componentes espetrais mais importantes. Após ser feita a identificação do valor de frequência destas componentes a base de dados é filtrada, sendo selecionados apenas sons que apresentem alguma componente espetral em comum com o som objetivo, tal como já foi referido na secção 4.3.4. Para além desta seleção por componente espetrais em comum, é feita uma posterior seleção em que apenas são selecionados sons com frequência fundamental mais alta que a do valor de frequência do primeiro pico do som objetivo. Esta seleção foi também já referida na secção 4.3.7. São estes sons selecionados que constituem a lista de índices válidos que o algoritmo de pesquisa pode utilizar. Restringe-se assim por um lado o espaço de combinações possíveis e por outro o número de instrumentos que podem constituir a solução. 5.4 Algoritmo Genético Foram desenvolvidas duas implementações diferentes deste algoritmo neste trabalho. Ambas as implementações foram especificadas tendo em conta as limitações do problema de orquestração e ambas utilizam as funções de avaliação e de similaridade introduzidas no capítulo 4. Estes algoritmos foram utilizados para a obtenção de soluções orquestradas através da combinação de sons presentes na base de dados construída. A primeira implementação desenvolvida modela o comportamento clássico do algoritmo genético: uma população de indivíduos é inicializada aleatoriamente e evoluída segundo processos 5.4 Algoritmo Genético 47 de seleção, cruzamento e mutação. Nesta implementação não existe nenhuma restrição na constituição da população, podendo existir mais que um indivíduo com as mesmas características. Efetivamente o comportamento desta primeira implementação desenvolvida é a de convergir para uma única solução ótima. O algoritmo desta implementação é descrito no algoritmo 5.1. Algoritmo 5.1: Algoritmo genético desenvolvido: Versão 1 Entrada:ns,itern,pc,pm Saída: P inicializa nsindivíduos aleatoriamente; enquanto número de iterações < iternfaça calcula fitness de cada indivíduo; ordena população por fitness decrescente; Pe←− guarda os nemelhores indivíduos (elitismo); seleciona nsindivíduos por roulette wheel; efetua cruzamento uniforme nos nsindivíduos selecionados com probabilidade pc; Pm←− efetua mutação nos indivíduos cruzados com probabilidade pm; atualiza nova população P= [Pe;Pm]; fim Já na segunda implementação desenvolvida existe um controlo sobre a população na medida em que cada indivíduo da população é único. A cada iteração é inicialmente feita uma filtragem por indivíduos repetidos, sendo eliminados os indivíduos duplicados. Desta maneira o algoritmo não converge para uma única solução ótima e, através do uso de elitismo, é possível a convergência para vários valores ótimos dependendo do número de indivíduos guardados pelo elitismo ao longo das iterações. Este comportamento simula parcamente uma das principais vantagens do sistema imunitário artificial: a possibilidade de convergência para vários valores ótimos. O algoritmo desta implementação é descrito no algoritmo 5.2. Algoritmo 5.2: Algoritmo genético desenvolvido: Versão 2 Entrada:ns,itern,pc,pm Saída: P inicializa nsindivíduos aleatoriamente; enquanto número de iterações < iternfaça elimina indivíduos duplicados; calcula fitness de cada indivíduo; ordena população por fitness decrescente; Pe←− guarda os nemelhores indivíduos (elitismo); seleciona nsindivíduos por roulette wheel; efetua cruzamento uniforme nos nsindivíduos selecionados com probabilidade pc; Pm←− efetua mutação nos indivíduos cruzados com probabilidade pm; atualiza nova população P= [Pe;Pm]; fim Apesar destas diferenças, o funcionamento intrínseco dos dois algoritmos é o mesmo: A cada iteração é inicialmente calculado o valor de avaliação dos indivíduos da população utilizando as 48 Implementação funções de avaliação definidas no capítulo 4. Após este cálculo é feita uma seleção de indivíduos para cruzamento utilizando o esquema de roulette wheel descrito em [45]. Estes indivíduos são sujeitos a operações de cruzamento que, com uma determinada probabilidade, interpolam o valor dos índices de dois indivíduos, originando dois novos indivíduos. Após a operação de cruzamento ser realizada a população é alterada através de operações de mutação que, também com uma determinada probabilidade, alteram ou eliminam valores de índice do vetor de cada indivíduo. Os algoritmos permitem também a utilização de elitismo ao longo das gerações, guardando um certo número de indivíduos mais aptos conforme o resto da população é alterada. 5.4.1 Operadores Genéticos Os operadores genéticos de seleção, cruzamento e mutação foram implementados nos algoritmos desenvolvidos. Através de comparação de resultados o método de funcionamento dos mesmos foi sucessivamente refinado, tendo em conta as restrições que o problema de orquestração coloca. Descrevem-se de seguida o funcionamento de cada um dos operadores genéticos implementados. 5.4.1.1 Seleção A seleção dos indivíduos destinados a gerarem descendência é feita através do método de roulette wheel proposto em [45]. Neste método é escolhido um indivíduo aleatoriamente da população, que é selecionado para cruzamento com uma probabilidade de fi/fmax, sendo fio valor de aptidão do indivíduo escolhido, e fmax o valor máximo de aptidão da população atual. Caso o indivíduo não seja selecionado o processo é repetido novamente escolhendo-se um novo indivíduo aleatório. Através de sucessivas seleções cria-se assim uma nova população com os indivíduos selecionados que irá apresentar uma constituição dominada por indivíduos com valores de aptidão mais altos. Ou seja, indivíduos mais aptos apresentam uma maior probabilidade de serem selecionados para cruzamento podendo um mesmo indivíduo ser mais que uma vez selecionado. Na figura 5.3 ilustra-se o funcionamento do esquema clássico da roulette wheel. É atribuída uma probabilidade de seleção a cada indivíduo dependendo do seu valor de aptidão. É de seguida calculado um número aleatório entre 0 e 1, correspondente à posição da roleta a ser selecionada. Como indivíduos mais aptos ocupam um espaço maior na roleta então estes indivíduos irão apresentar uma tendência maior a serem selecionados. 5.4.1.2 Cruzamento O operador de cruzamento implementado cruza dois indivíduos selecionados aleatoriamente com probabilidade pc. O cruzamento é uniforme, sendo que os novos indivíduos contém aleatoriamente índices de um dos indivíduos pais. Ou seja, caso xiexjsejam dois indivíduos selecionados para cruzamento com: xi={i1,i2,i3,i4,i5} xj={i6,i7,i8,i9,i10} 5.4 Algoritmo Genético 49 37% Figura 5.3: Ilustração do funcionamento clássico do esquema de roulette wheel Então, dois possíveis descendentes serão: x0 i={i6,i2,i3,i9,i5} x0j={i1,i7,i8,i4,i10} 5.4.1.3 Mutação A mutação é feita com probabilidade pmem posições aleatórias do vetor de índices, sendo o novo valor escolhido aleatoriamente como zero ou um índice válido. Ou seja caso uma determinada posição no vetor de índices tenha sido selecionada para mutação então o correspondente valor será, substituído por um valor de índice diferente ou substituído por o valor zero sendo a escolha do novo valor feita aleatoriamente. Caso xiseja um indivíduo tal que: xi={i1,i2,i3,i4,i5} Uma possível mutação seria: x0 i={i1,i6,i3,i4,i5} 50 Implementação 5.5 Sistema Imunitário Artificial Uma alternativa ao uso de algoritmos genéticos recai sobre a escolha de um sistema imunitário artificial. Estes últimos algoritmos baseiam-se no funcionamento do sistema imunitário dos vertebrados tendo sido inicialmente descritos na secção 3.2. As diferenças entre estes algoritmos e os algoritmos genéticos residem essencialmente nos operadores genéticos. Enquanto que no algoritmo genético os indivíduos sofrem mutação a uma taxa constante, no sistema imunitário esta taxa varia, sendo proporcional à aptidão de cada indivíduo. Assim, indivíduos mais aptos sofrem uma menor taxa de mutação enquanto que indivíduos pouco aptos sofrem uma maior taxa. Para além desta diferença, realça-se o facto de que nos sistemas imunitários artificiais não existe cruzamento entre indivíduos, realizando-se assim a otimização de indivíduos através de apenas mutação. Em termos de resultados fornecidos por este algoritmo é importante destacar que, contrariamente aos algoritmos genéticos, o sistema imunitário artificial não converge para uma única solução. Pelo contrário, uma das principais vantagens do uso deste sistema recai sobre o facto de que várias soluções ótimas são exploradas simultaneamente, fornecendo ao utilizador uma diversidade maior no conjunto de soluções e colmatando assim uma das principais desvantagens dos algoritmos genéticos. 5.5.1 aiNet e opt-aiNet A aiNet é um algoritmo que modela um sistema imunitário artificial e foi desenvolvida inicialmente para propósitos de compressão e agregação de dados [13]. Os autores deste algoritmo desenvolveram também uma versão, denominada de opt-aiNet, que apresenta como principal aplicação a resolução de problemas de otimização multi dimensionais [35]. Neste sistema, uma população de anticorpos (considerados como candidatos à solução) é evoluída através de processos de expansão clonal, mutação e posterior seleção. A opt-aiNet mantém ao longo da execução um conjunto de anticorpos que apresentam uma melhor aptidão em relação aos restantes anticorpos da população. As características mais marcantes da opt-aiNet são: •Determinação automática do tamanho da população; •Combinação de pesquisa local com pesquisa global; •Definição de critérios de convergência; •Capacidade de localizar e manter vários máximos locais. Estas características distinguem o sistema imunitário artificial opt-aiNet do algoritmo genético que, no seu comportamento clássico, não é capaz de localizar vários máximos. Efetivamente esta é a característica mais importante nestes sistemas. Através da utilização de um algoritmo que forneça vários máximos locais, é possível a implementação de um sistema de orquestração capaz de fornecer várias soluções úteis ao utilizador. Para compreender melhor o funcionamento do algoritmo opt-aiNet segue-se uma breve explicação da terminologia utilizada pelos autores deste algoritmo: 5.5 Sistema Imunitário Artificial 51 Célula Indivíduo da população. Cada célula corresponde a uma solução possível e é representada sob a forma de um vetor com valores reais mapeados num espaço euclidiano; Fitness Aptidão de uma célula em relação a uma função objetivo que se pretende otimizar. O valor de fitness de cada célula corresponde ao valor da função objetivo recorrendo aos valores presentes na célula; Afinidade Distância euclidiana entre duas células; Clone Copia idêntica de uma determinada célula. Os clones sofrem mutação para introduzir variação na população. Algoritmo 5.3: Algoritmo opt-AiNet Entrada:Nc,σs Saída: C inicializa um conjunto Cde células aleatoriamente; enquanto critério de convergência não é atingido faça calcula fitness de cada célula; gera Ncclones para cada célula; cada clone sofre mutação proporcional ao valor de fitness da célula original; calcula fitness de cada célula incluindo os novos clones; para cada célula selecione o clone mais apto e descartam-se os restantes; calcula valor médio de fitness da população; se valor médio de fitness maior que o da iteração anterior então continua; senão suprime células que apresentem uma afinidade mais baixa que σs; introduz uma percentagem dde células criadas aleatoriamente; fim fim O algoritmo inicia a sua execução criando um conjunto de células com valores aleatórios. De seguida, é iniciado um ciclo em que são inicialmente calculados os valores de fitness de cada célula. Após este calculo é iniciado um processo de clonagem das células da população. Estes clones sofrem uma mutação proporcional ao seu valor de fitness, sendo que o processo de mutação realiza-se segundo a seguinte expressão: c0=c+αN(0,1)(5.1) α=1 βexp(−f∗)(5.2) Onde c0é uma célula cque sofreu mutação, N(0,1)é uma variável aleatória Gaussiana com média igual a zero e desvio padrão igual a um, βé um parâmetro que controla o decaimento da função 52 Implementação exponencial inversa (geralmente β=100), e f∗é o valor de fitness do indivíduo normalizado segundo o intervalo [0,1]. Após serem feitas estas operações de clonagem e mutação sobre os clones, são calculados os novos valores de fitness de todas as células e seus respetivos clones que sofreram mutação. Para cada célula é selecionado o clone mais apto ou selecionada a célula original, caso nenhum clone seja mais apto que a célula original. Posteriormente à seleção das células mais aptas é formada uma nova população contendo as células selecionadas. O valor médio de fitness desta nova população é calculado e, caso este valor seja diferente do valor obtido na iteração anterior então retoma-se a execução a partir do início do ciclo, caso contrário realiza-se uma operação de supressão na população. A operação de supressão é realizada quando o valor médio de fitness da população não evolui e corresponde a uma eliminação de células que apresentem um valor de afinidade baixo, nomeadamente, são eliminadas células com afinidade mais baixa que a especificada pelo limiar de supressão σs. Ou seja, são eliminadas células que se encontram próximas no espaço de pesquisa, representando soluções semelhantes. As células restantes após esta operação ser efetuada denominam-se de células de memória. Após ser feita a supressão são introduzidas na população uma percentagem dde novas células criadas aleatoriamente. Estas operações permitem por um lado controlar o tamanho da população, e por outro manter os máximos locais com apenas uma célula evitando desperdício de recursos. Para além disso, através da introdução de novas células evita-se a estagnação do algoritmo em máximos locais e contribui significativamente para a exploração do espaço de pesquisa. 5.5.2 Implementação do Algoritmo opt-aiNet Para a aplicação do algoritmo opt-aiNet no sistema de orquestração desenvolvido foi necessária a sua transposição para um algoritmo capaz de lidar com valores discretos na codificação das células. Para tal operação foi necessário alterar o funcionamento do processo de mutação uma vez que na implementação original este processo estava concebido para células com valores reais. O novo processo de mutação implementado utiliza a expressão da exponencial inversa para determinar a probabilidade de mutação que uma célula irá apresentar. Após este cálculo ser feito o vetor de índices que codifica a solução é percorrido e, para cada valor de índice, é calculado um número aleatório entre 0 e 1. Caso o número aleatório seja mais baixo que a probabilidade de mutação previamente calculada então esse valor de índice é alterado para um novo valor, sendo a escolha do novo valor feita aleatoriamente. A função exponencial inversa utilizada é a seguinte: pm=exp(−γf∗)(5.3) Com γgeralmente igual a 1.2. Este valor de γgera o gráfico apresentado na figura 5.4, correspondente à probabilidade de mutação segundo o valor de fitness normalizado. 5.6 Aplicação 53 Quanto à operação de supressão o funcionamento intrínseco é o mesmo que o do opt-aiNet, nomeadamente são calculados os valores de afinidade entre as diferentes células sendo suprimidas aquelas que apresentem um valor de afinidade inferior a σs. Os valores de afinidade no caso do problema de orquestração correspondem a um vetor com as distâncias relativas entre os valores dos diferentes descritores. Estas distâncias relativas são calculadas entre os valores obtidos através da aplicação das equações 4.11,4.12 e4.13. 0 0.2 0.4 0.6 0.8 1 0.4 0.5 0.6 0.7 0.8 0.9 1 Probability of Mutation normalized fitness pm Figura 5.4: Probabilidade de mutação segundo o valor de fitness normalizado, com γigual a 1.2 5.6 Aplicação Apresenta-se nesta secção a aplicação desenvolvida para a resolução do problema de orquestração musical. Tendo em conta as várias restrições, e utilizando os algoritmos de pesquisa previamente descritos desenvolveu-se uma aplicação em MATLAB (R2014a, The MathWorks, Natick, Massachusetts, United States) com diferentes módulos, incluindo uma pequena interface gráfica para visualizar os resultados obtidos. Foi também utilizada uma framework de processamento de áudio digital, a MIRToolbox [46]. Esta ferramenta oferece várias funções de processamento de áudio, incluindo o cálculo do espetro e pesquisa automática por máximos locais nesse espetro. Os módulos desenvolvidos foram especificados tendo em conta a interoperabilidade entre os diferentes algoritmos de pesquisa propostos: o algoritmo genético e o sistema imunitário artificial. A aplicação desenvolvida lida com o problema da orquestração musical como um problema de otimização combinatória em que as diferentes combinações representam as diferentes orquestrações possíveis. As combinações são representadas por um vetor de valores inteiros representando 54 Implementação os diferentes instrumentos e notas musicais que contém essa combinação. Várias operações de pré-processamento são efetuadas sobre os sons presentes na base de dados de forma a otimizar o espaço de pesquisa existente e reduzir consequentemente o número de iterações necessárias para a obtenção de soluções ótimas. Os resultados obtidos pelo algoritmo de pesquisa são apresentados numa interface gráfica e guardados em ficheiros .WAV para o uso posterior pelo utilizador. Descreve-se de seguida a estrutura da aplicação desenvolvida. 5.6.1 Estrutura Os diferentes módulos constituintes da aplicação desenvolvida são apresentados na figura 5.5. Base de Dados Extração de Descritores Algoritmo de Pesquisa Avaliação de Aptidão Combinação de Sons Interface Gráfica Figura 5.5: Módulos da aplicação desenvolvida e suas dependências Inicialmente o sistema inicia a execução através da especificação, por parte do utilizador, da base de dados a utilizar, do som objetivo que se pretende orquestrar e do número máximo de sons que podem ser utilizados nessa orquestração. Após esta especificação inicial o sistema extrai as características do som objetivo descritas na secção 4.3. A partir das características do som objetivo são selecionados, de entre os ficheiros presentes na base de dados, aqueles cuja relevância é maior para a resolução do problema de orquestração. Esta seleção é feita, primeiramente, sobre a frequência fundamental de cada som, descartando sons que apresentem frequência fundamental mais baixa que o valor de frequência do primeiro pico espetral do som objetivo, e em seguida, sobre o espetro de cada som, descartando sons que não apresentem picos espetrais em comum com o som objetivo. Estas operações de seleção e pré-processamento foram já descritas na secção 5.3. Após serem selecionados os sons que irão fazer parte do espaço de pesquisa o fluxo de execução é passado para o algoritmo de pesquisa que, através de sucessivas iterações, calcula o ou os indivíduos mais aptos correspondentes a soluções de maior relevância. A relevância de cada 5.6 Aplicação 55 indivíduo é avaliada segundo as funções de avaliação apresentadas na secção 4.5, sendo utilizadas pelo algoritmo de pesquisa para quantificar numericamente a qualidade de um determinado indivíduo. Assim que o algoritmo de pesquisa termina a sua execução os indivíduos resultantes são combinados criando-se assim os sons orquestrados. Esta combinação é feita através da soma linear dos sons constituintes da solução sendo utilizado um Phase Vocoder [47] para a igualização da duração de cada som. A necessidade da utilização de um Phase Vocoder fundamenta-se pelo facto de que os sons da base de dados apresentam durações temporais diferentes sendo que, através da utilização deste tipo de algoritmos é possível alterar a duração de um som sem modificar a sua altura nem dinâmica, tornando-se assim especialmente útil para igualizar a duração temporal de cada som da base de dados. O resultado final é um conjunto de ficheiros de som representando a orquestração das diferentes soluções. Terminando o fluxo de execução encontra-se uma pequena interface gráfica desenvolvida para a rápida visualização dos resultados obtidos. Esta interface apresenta os resultados obtidos, permite a reprodução dos sons resultantes e apresenta também o conjunto de instrumentos utilizados para a orquestração do resultado. 5.6.2 Funcionamento Os principais módulos da aplicação desenvolvida e suas dependências encontram-se ilustrados na figura 5.5. O funcionamento dos diferentes módulos da aplicação desenvolvida é de seguida apresentado, assim como as funções mais importantes realizadas por cada um. 5.6.2.1 Base de Dados Este módulo é responsável pelo processamento e seleção dos sons que irão fazer parte do espaço de pesquisa. Para tal apresenta funções que percorrem uma determinada lista de ficheiros, especificada pelo utilizador, selecionando aqueles cuja relevância para o problema de orquestração é maior. Este módulo é também responsável por guardar as características extraídas de cada som pertencente à base de dados, assim, este cálculo de extração é necessário ser feito apenas uma vez. A forma como este módulo guarda estas características é feita através da utilização de ficheiros anexos a cada som contendo o valor dessas características. Dessa forma quando se pretende obter as características de um determinado som apenas é necessário ler o ficheiro anexo. Por exemplo, quando um novo ficheiro de som (.WAV) é introduzido na base de dados o sistema calcula o valor das características desse ficheiro e guarda o correspondente resultado num ficheiro anexo (.MAT). Este ficheiro anexo será depois utilizado para ler rapidamente as características do ficheiro de som correspondente. Na figura 5.6 ilustra-se a organização dos ficheiros na base de dados. 62 Avaliação e Resultados Som Objetivo Car Horn Synth Wind Harp Sistema Imunitário Artificial -0.019032 -0.010264 -0.016615 Algoritmo Genético -0.029667 -0.020635 -0.033281 Tabela 6.1: Valores de aptidão dos melhores sons orquestrados obtidos pelos diferentes algoritmos para 3 sons objetivo Devido ao comportamento do algoritmo genético de convergência para uma solução única foram realizados diversos ciclos de execução tendo sido obtidas várias soluções diferentes enquanto que, utilizando o sistema imunitário artificial, apenas num ciclo de execução se obteve um máximo de 10 soluções diferentes. É importante realçar que as soluções obtidas pelo algoritmo genético apresentam um valor de aptidão mais baixo do que as obtidas pelo sistema imunitário artificial, deduzindo-se assim que as soluções obtidas pelo algoritmo genético serão teoricamente piores do que aquelas obtidas pelo sistema imunitário artificial. Uma comparação entre os valores de aptidão obtidos com o algoritmo genético e com o sistema imunitário artificial é apresentada na tabela 6.1. Na tabela referida disponibilizam-se os valores de aptidão obtidos para diferentes sons objetivo utilizando os dois algoritmos de pesquisa desenvolvidos. Os valores de aptidão de uma orquestração são sempre negativos e quanto mais próximos de zero estiverem mais similar com o objetivo a orquestração teoricamente será. Como pode ser observado pelos valores da tabela os resultados obtidos pelo sistema imunitário artificial apresentam valores de aptidão mais altos do que aqueles obtidos pelo algoritmo genético. Verifica-se assim que o novo algoritmo de pesquisa proposto apresenta para além de uma diversidade maior no conjunto de soluções, uma eficiência maior na obtenção das mesmas. Para avaliar as soluções obtidas no que toca à similaridade percetiva foi desenvolvido um teste de escuta em que se pediu aos utilizadores uma quantificação da similaridade entre as soluções orquestradas e os sons objetivos. Este teste permitiu avaliar a qualidade das soluções obtidas pelo sistema desenvolvido. As soluções avaliadas foram obtidas utilizando apenas o sistema imunitário artificial como algoritmo de pesquisa. Este algoritmo retorna, dependendo do som objetivo, uma população com uma média de 50 indivíduos, tendo sido selecionados os 10 melhores para o teste de escuta desenvolvido. Todos os sons objetivo foram orquestrados utilizando 5 como o valor máximo de sons diferentes que podem compor uma orquestração. Quanto à similaridade objetiva esta foi avaliada utilizando os valores de aptidão das soluções recorrendo ás funções de fitness descritas previamente. Outro aspeto avaliado diz respeito à diversidade das soluções obtidas. Para tal considerouse diversidade objetiva como o número de sons diferentes entre duas orquestrações diferentes. O cálculo da diversidade objetiva foi feito da seguinte forma: considerando duas orquestrações compostas por nsons que apresentem em comum ksons, então a diversidade objetiva será: div =1−k n(6.1) 6.2 Estrutura 63 Desta forma a diversidade objetiva será um valor entre 0 e 1, correspondendo o valor 0 a valores baixos de diversidade (todos os sons em comum) e o valor 1 a valores altos de diversidade (nenhum som em comum). Como todos os sons orquestrados apresentam uma limitação de 5 sons diferentes então nserá sempre igual a 5 para os sons objetivo utilizados. Para cada orquestração individual aplicou-se a equação 6.1, comparando-a com as restantes orquestrações do conjunto de 10 orquestrações retornadas pelo algoritmo de pesquisa. O valor final de diversidade objetiva de um conjunto de orquestrações corresponde ao valor médio da classificação da diversidade objetiva desse conjunto. No teste de escuta desenvolvido pediu-se também aos utilizadores que avaliassem a diversidade percetiva entre os sons orquestrados. A diversidade percetiva compreende o quão diferentes entre si são um conjunto de 10 orquestrações para um dado som objetivo e depende do utilizador que realiza o teste de escuta a classificação desta diversidade. De tal forma, conseguiu-se avaliar se os diferentes sons orquestrados apresentam diversidade percetiva entre si. Os resultados finais permitiram validar o novo algoritmo de pesquisa proposto: o sistema imunitário artificial. Este algoritmo para além de apresentar uma boa eficiência na obtenção de soluções apresenta também uma vantagem significativa em relação ao algoritmo genético no que toca à diversidade das soluções propostas. Esta diversidade patenteia a principal vantagem no sistema de orquestração desenvolvido comparativamente a implementações prévias. 6.2 Estrutura Para o desenvolvimento do teste de escuta foi utilizada a framework BeaqleJS [49]. Esta ferramenta oferece suporte nativo para testes semelhantes aos pretendidos, tendo sido adaptada para o teste de escuta desenvolvido. No teste desenvolvido é apresentado ao utilizador um som objetivo e um conjunto de sons orquestrados. O utilizador deve ouvir tanto o som objetivo como cada som orquestrado e avaliar a similaridade percetiva entre o som objetivo e os sons orquestrados. Esta avaliação é feita numa escala de “Muito Diferente” a “Muito Semelhante”, sendo a opção “Muito Diferente” destinada a sons completamente díspares e a opção “Muito Semelhante” destinada a sons praticamente iguais. O utilizador deve também quantificar a diversidade percetiva entre os sons orquestrados utilizando para isso a mesma escala com opções de “Muito Diferente” a “Muito Semelhante”, sendo a opção “Muito Diferente” destinada a sons muito diversos entre si e a opção “Muito Semelhante” destinada a sons muito semelhantes entre si. Para cada som objetivo foram selecionados um conjunto de 10 sons orquestrados, tendo sido utilizados 10 sons objetivos totalizando assim 100 sons orquestrados que foram avaliados segundo a sua similaridade percetiva com o objetivo e segundo a sua diversidade percetiva. Os sons orquestrados são apresentados ao utilizador de uma forma aleatória. Um exemplo da interface do teste de escuta desenvolvido pode ser visualizado na figura 6.1 e na figura 6.2. O teste de escuta desenvolvido foi disponibilizado online numa página dedicada1. Foram enviados pedidos de colaboração para diversas pessoas, tendo sido obtidos 18 resultados. Os resultados 1http://paginas.fe.up.pt/~ee10146/test/ 64 Avaliação e Resultados Figura 6.1: Interface do teste de escuta desenvolvido: mensagem inicial obtidos foram processados utilizando o MATLAB e são apresentados na secção seguinte. 6.3 Resultados Obtidos Apresentam-se de seguida os resultados do teste de escuta efetuado utilizando 10 sons objetivos com 10 orquestrações para cada som objetivo. A escala utilizada varia de 1 a 5, sendo o valor 1 atribuído à opção “Muito Diferente”, o valor 2 à opção “Diferente”, o valor 3 à opção “Razoavelmente Semelhante”, o valor 4 à opção “Semelhante” e o valor 5 à opção “Muito Semelhante”. Os dados recolhidos foram processados utilizando o MATLAB, e em cada figura apresentam-se os valores médios obtidos e os correspondentes desvios padrão assinalados na linha contínua. As orquestrações estão ordenadas por ordem decrescente de aptidão sendo que a primeira orquestração apresenta a melhor aptidão e a décima orquestração apresenta a pior aptidão. 6.3 Resultados Obtidos 65 Figura 6.2: Interface do teste de escuta desenvolvido: escolha da similaridade e diversidade Na base de dados sonora utilizada encontram-se presentes sons de instrumentos de cordas e sopro. Como cada som da base de dados corresponde a uma nota de um instrumento então o conteúdo espetral desses sons será bastante harmónico e a combinação de diferentes sons resultará num espetro composto por componentes harmónicas. Este facto permite supor que sons objetivo que apresentem um espetro com componentes harmónicas irão apresentar melhores resultados na orquestração do que sons que não apresentem essa harmonicidade por ser mais fácil encontrar combinações de instrumentos que assemelhem esse espetro. Como tal, e devido ao facto do sistema desenvolvido não considerar a evolução temporal dos sons objetivo, a escolha 66 Avaliação e Resultados Som Objetivo Variação Temporal Harmonicidade Car Horn Não Baixa Synth Não Alta Tbreed Não Baixa Ahh Não Alta Wind Harp Não Alta Didgeridoo Não Alta Elephant Sim Baixa Frog Sim Baixa Girl Scream Sim Baixa Gong Sim Baixa Tabela 6.2: Sons objetivo utilizados no teste de escuta dos sons objetivo a utilizar no teste de escuta foi feita tendo em conta a exploração destes dois aspetos. Assim, escolheu-se sons com bastante harmonicidade como por exemplo sons de instrumentos musicais (“Wind Harp” e “Didgeridoo”) e sons com pouca harmonicidade (“Car Horn”, “Elephant”, “Frog” e “Gong”). Foram também escolhidos sons que apresentam variação temporal e sons estáticos. Na tabela 6.2 apresentam-se os sons utilizados no teste de escuta acompanhados por uma pequena descrição em que se enumera quais os sons que apresentam variação temporal e o seu correspondente grau de harmonicidade. Na tabela 6.3 apresentam-se os valores médios de classificação do conjunto de orquestrações e correspondentes referências das figuras contendo a classificação média de cada orquestração. A classificação média varia entre 1 a 5, sendo que quanto maior este valor melhor foi a classificação da similaridade percetiva. Ou seja valores mais altos de classificação média indicam orquestrações com uma similaridade percetiva mais alta. Como pode ser observado na tabela, a orquestração “Frog” (ver figura 6.11) apresenta os valores mais baixos de classificação média. A razão destes valores prende-se pelo facto de que o som objetivo utilizados nesta orquestração varia temporalmente, não apresentando por isso um comportamento estático. Como já foi referido previamente, o sistema de orquestração desenvolvido não considera a evolução temporal do timbre na orquestração de sons, devendo-se a esse facto os baixos valores de aptidão desta orquestração. Apesar de o sistema desenvolvido não considerar a evolução temporal dos sons objetivo nos resultados obtidos verificam-se boas classificações para os sons “Girl Scream”, “Elephant” e “Gong”, sons estes que apresentam variação temporal. Este facto evidencia que a utilização de valores médios para a caracterização de cada som pode por vezes originar boas orquestrações, mesmo não considerando a evolução temporal. As orquestrações resultantes apresentam alguma semelhança com os sons objetivo, segundo os resultados obtidos. O valor de aptidão das orquestrações utilizadas no teste de escuta são apresentados na tabela 6.5. Realça-se mais uma vez que os valores de aptidão de uma determinada orquestração são sempre negativos e quanto mais próximos de zero estiverem mais similar a orquestração teoricamente será com o som objetivo. Ou seja, teoricamente quanto maior o valor de aptidão melhor será a orquestração. O valor mais alto de aptidão corresponde à orquestração “Synth”. No entanto, este 6.3 Resultados Obtidos 67 Som Objetivo Classificação Média Figura Car Horn 2.8889 6.4 Synth 1.8395 6.5 Tbreed 2.1667 6.6 Ahh 2.2901 6.7 Wind Harp 2.4320 6.8 Didgeridoo 2.2037 6.9 Elephant 2.4074 6.10 Frog 1.1914 6.11 Girl Scream 2.7716 6.12 Gong 2.4320 6.13 Tabela 6.3: Avaliação da similaridade percetiva média das orquestrações submetidas ao teste de escuta valor não reflete a maior similaridade percetiva obtida no teste de escuta. Pelo contrário, a orquestração “Synth” apresenta dos valores mais baixos obtidos no teste. Na realidade, pode-se concluir que os valores de aptidão obtidos refletem de algum modo a similaridade entre sons. No entanto, não refletem na totalidade esta similaridade. Na verdade, excetuando a orquestração “Frog”, as restantes orquestrações apresentam valores de aptidão da mesma ordem de grandeza, concluindose que a resolução das funções de aptidão não é muito alta. Para corroborar este facto verifica-se que, nos resultados obtidos, apesar de as orquestrações estarem ordenadas por valor decrescente de aptidão, não se verifica uma variação nas classificações obtidas que comprovem que valores mais altos de aptidão correspondem a orquestrações melhores (ver figuras 6.4 a6.13). A orquestração com melhor classificação no teste de escuta foi a “Car Horn” (ver figura 6.4). A razão desta boa classificação prende-se pelo facto de que o som objetivo desta orquestração é constituído por duas séries harmónicas, correspondendo a duas notas musicais diferentes. De tal forma, torna-se fácil encontrar combinações de instrumentos que se assemelhem a este som objetivo. Tal como nas outras orquestrações verifica-se que o conjunto de orquestrações obtidas apesar de estar ordenado por aptidão, não está ordenado por similaridade percetiva, segundo os resultados obtidos. Esta é mais uma razão que confirma que a resolução das funções de aptidão não é muito alta. As restantes orquestrações apresentam valores semelhantes de similaridade percetiva. Um dos participantes do teste de escuta referiu que algumas das orquestrações apresentam diferenças em termos de altura. Este comentário fornece mais uma justificação para a diversidade que o conjunto de orquestrações apresenta, existindo orquestrações que têm uma altura diferente da que o som objetivo. Outro comentário de um dos participantes referiu que, no geral, as orquestrações submetidas a teste não permitem reconhecer o som objetivo. Este comentário permite concluir que a subjetividade do teste de escuta desenvolvido não permite uma avaliação objetiva das orquestrações submetidas a avaliação. Efetivamente os desvios padrão dos dados obtidos são significativamente altos, deduzindo-se que não existe concordância entre os participantes quanto à classificação das orquestrações. 68 Avaliação e Resultados 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 Diversity Figura 6.3: Resultados do teste de escuta: diversidade percetiva Os resultados da avaliação da diversidade percetiva podem ser visualizados na figura 6.3. Nesta figura é utilizada uma escala de 1 a 5, correspondendo o valor 1 a valores altos de diversidade percetiva e o valor 5 a valores baixos de diversidade percetiva. O valor médio da classificação é próximo de 3, podemos por isso afirmar que os resultados obtidos no teste de escuta confirmam que o sistema produz orquestrações diversas entre si para um mesmo som objetivo. É de notar que as orquestrações foram obtidas através de uma única execução da aplicação, oferecendo assim ao utilizador um conjunto diverso de orquestrações que podem depois ser refinadas ou combinadas. A diversidade objetiva dos sons avaliados no teste de escuta é apresentada na tabela 6.4. Nesta tabela os valores foram obtidos utilizando a equação 6.1 e representam numa escala de 0 a 1 quão diversos são os sons de cada conjunto de orquestrações. Valores altos de diversidade objetiva correspondem a diversidade alta. Os dados presentes na tabela corroboram os dados obtidos no teste de escuta, nomeadamente os valores de diversidade subjetiva. Na tabela referida pode-se verificar que a diversidade objetiva das orquestrações utilizadas no teste de escuta apresentam valores altos, correspondendo a uma diversidade alta de sons. Ou seja, o conjunto de sons orquestrados apresentam uma baixa inter-similaridade entre si, corroborando os dados de diversidade percetiva obtidos no teste de escuta. No geral, e após considerar os resultados obtidos no teste de escuta, podemos afirmar que as funções de aptidão implementadas não refletem na totalidade a similaridade entre sons mas são uma boa aproximação a esta similaridade, tal como esperado. Efetivamente, as funções de aptidão utilizadas foram desenvolvidas em implementações anteriores de um sistema de orquestração tendo sido apenas adaptadas para este trabalho sendo que a sua validade foi já verificada [18]. 6.3 Resultados Obtidos 69 Diversidade Som Objetivo Média Desvio Padrão Car Horn 0.7822 0.1576 Synth 0.8444 0.1333 Tbreed 0.8178 0.1518 Ahh 0.8400 0.1380 Wind Harp 0.8000 0.1529 Didgeridoo 0.6356 0.1658 Elephant 0.8578 0.1315 Frog 0.7822 0.1518 Girl Scream 0.8489 0.1351 Gong 0.8222 0.1542 Tabela 6.4: Valores médios de diversidade objetiva e desvios padrões dos sons utilizados no teste de escuta Considerando os valores de aptidão da tabela 6.5, verifica-se que a similaridade percetiva depende da ordem de grandeza do valor de aptidão, sendo que para valores da mesma ordem de grandeza nem sempre se verifica uma similaridade percetiva mais alta para valores de aptidão mais altos. Para além disso, verifica-se que vários fatores influenciam uma boa orquestração. Nomeadamente, o facto de haver variação no timbre do som objetivo e o conteúdo espetral do mesmo, influenciam a similaridade das orquestrações obtidas utilizando o sistema desenvolvido. Na realidade verificase que sons que apresentem variação tímbrica no tempo irão apresentar orquestrações piores e sons que apresentem um conteúdo espetral formado por componentes harmónicas irão apresentar orquestrações melhores. No que toca à diversidade podemos afirmar que a aplicação desenvolvida providencia soluções diversas e únicas, oferecendo a este sistema uma vantagem significativa em relação a implementações prévias. 70 Avaliação e Resultados 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 Test ID 1 − Car Horn Figura 6.4: Resultados do teste de escuta: som objetivo “Car Horn” 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 Test ID 2 − Synth Figura 6.5: Resultados do teste de escuta: som objetivo “Synth” 6.3 Resultados Obtidos 71 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 Test ID 3 − Tbreed Figura 6.6: Resultados do teste de escuta: som objetivo “Tbreed” 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 Test ID 4 − Ahh Figura 6.7: Resultados do teste de escuta: som objetivo “Ahh” 78 Conclusões e Trabalho Futuro Em segundo lugar, e como foi descrito no capítulo 6, vários aspetos influenciam a definição de uma boa orquestração. Como a evolução temporal do timbre não foi considerada na implementação do sistema desenvolvido é natural que sons que apresentem variação temporal originem orquestrações piores do que sons que não apresentam essa variação. Esta é uma das principais dificuldades na implementação deste tipo de sistemas, não tendo sido endereçada nem nesta implementação nem na implementação que serviu de base ao sistema desenvolvido [18]. Existe contudo uma implementação que já é capaz de lidar com a evolução temporal do timbre [50]. Para além desta limitação, sons que apresentem um conteúdo espetral formado por componentes harmónicas apresentam orquestrações com um grau de similaridade mais alto. Efetivamente, como a base de dados sonora é formada por notas de instrumentos musicais e os correspondentes sons apresentam componentes harmónicas, é natural que sons que apresentem essa mesma harmonicidade não sejam difíceis de orquestrar. Finalmente, a utilização de um sistema imunitário artificial fornece ao sistema desenvolvido uma mais valia na diversidade e qualidade das soluções obtidas. Implementações prévias utilizaram um algoritmo genético para obter as soluções orquestradas. Este tipo de algoritmo foi também utilizado inicialmente neste trabalho tendo sido obtidos resultados com valores de aptidão mais baixos do que aqueles que foram obtidos através da utilização de um sistema imunitário artificial. Através de uma única execução do algoritmo é possível o retorno de várias soluções ótimas que se encontram próximas do som objetivo. Esta mais valia marca mais um ponto importante que destaca o sistema desenvolvido das implementações prévias. Os resultados obtidos por este algoritmo apresentaram boas classificações no teste de escuta desenvolvido, justificando o uso deste algoritmo em futuras implementações de sistemas de orquestração musical. A escolha do algoritmo opt-aiNet como algoritmo de pesquisa prendeu-se pelo facto dos bons resultados que este apresenta em problemas multidimensionais. Este algoritmo foi significativamente alterado na implementação utilizada neste sistema, no entanto, o funcionamento intrínseco continuou o mesmo. Estas alterações foram realizadas tendo em conta as restrições do problema de orquestração e resultaram num algoritmo capaz de otimizar um espaço de pesquisa discreto que apresenta bons resultados, comparativamente ao algoritmo genético utilizado. Este algoritmo pode ser futuramente utilizado noutro tipo de problemas com restrições semelhantes ao problema da orquestração musical. No geral, o sistema desenvolvido apresenta um bom desempenho na orquestração de sons musicais. As funções de fitness implementadas refletem eficientemente a similaridade entre orquestrações e os sons objetivo, tornando-se assim numa boa medida a utilizar nos algoritmos de pesquisa. Os descritores escolhidos não refletem na totalidade a descrição de cada som, mas são no entanto suficientes para uma orquestração razoável. Como descrito no capítulo 6a similaridade percetiva das orquestrações, que foi obtida através de testes de escuta, apresenta bons valores para as orquestrações testadas. Isto é, os utilizadores consideraram que a maior parte das orquestrações refletem de alguma forma o som objetivo. Os resultados deste trabalho, para além de terem sido disponibilizados na página web dedicada 7.2 Trabalho Futuro 79 ao tema1, foram também parcialmente apresentados no 1oCongresso Doutoral em Engenharia realizado na Faculdade de Engenharia da Universidade do Porto. A participação envolveu a escrita de um artigo [1] e a realização de um poster cujo conteúdo refletiu o trabalho desenvolvido até à data de realização deste congresso. 7.2 Trabalho Futuro O sistema de orquestração desenvolvido apresenta um bom desempenho na orquestração de sons musicais, no entanto, vários aspetos necessitam de ser melhorados para uma possível utilização desta ferramenta por músicos profissionais e compositores. Efetivamente, nesta fase o sistema desenvolvido apresenta diversas lacunas que impossibilitam um melhor aproveitamento das potencialidades da orquestração com recurso a ferramentas computacionais. A principal lacuna do sistema desenvolvido é a consideração do timbre como fenómeno estático que não evolui com o tempo. Tal como foi descrito no capítulo 2, o timbre é um fenómeno multidimensional que evolui com o tempo, no entanto, para simplificar o desenvolvimento do sistema proposto foi necessário descartar a evolução temporal do timbre, utilizando-se apenas valores médios na caracterização de cada som. Esta consideração impossibilita ao sistema desenvolvido quer a orquestração de sons que apresentem uma variação temporal quer a utilização na base de dados de sons que também apresentem essa variação. Por exemplo, sons de instrumentos de percussão não podem ser utilizados na base de dados por apresentarem exatamente essa variação. A colmatação desta lacuna ofereceria ao utilizador um potencial muito maior por permitir a orquestração de praticamente qualquer som existente. Outra lacuna existente no sistema é o facto de não haver nenhum controlo sobre o processo de orquestração. Nomeadamente, não existe nenhum mecanismo que permita ao utilizador especificar, por exemplo, quais os instrumentos que quer que façam parte no processo de orquestração, ou especificar uma determinada dinâmica que deva ser usada, ou até especificar um número máximo e mínimo de instrumentos que devem fazer parte da solução. Da forma como o sistema se encontra desenvolvido atualmente tais restrições não são possíveis. Efetivamente, o sistema desenvolvido preza pela completa autonomia no processo de orquestração, sendo que o utilizador apenas é capaz de especificar o número máximo de sons diferentes que podem fazer parte das soluções orquestradas. Assim, o controlo sobre o processo de orquestração é praticamente nulo da parte do utilizador. Futuramente, a adição de um mecanismo que permita controlar minimamente o processo de orquestração poderia aumentar em grande escala a utilidade do sistema, especialmente para um utilizador que pretenda obter um som orquestrado de entre um leque de restrições. Outra possível melhoria seria a adição de mais descritores na caracterização de cada som, podendo esta adição resultar numa melhoria dos resultados do sistema. Inicialmente, no desenvolvimento deste sistema estavam a ser utilizados 3 descritores para a caracterização de cada som: centróide espetral, espalhamento espetral, picos espetrais. Com a adição de um quarto descritor (intensidade sonora), verificou-se uma melhoria significativa na qualidade dos resultados obtidos. 1http://paginas.fe.up.pt/~ee10146/#thesis 80 Conclusões e Trabalho Futuro Assim é expetável que a adição de mais descritores possa aumentar a qualidade dos resultados à custa de um maior custo computacional no cálculo da aptidão de cada solução. No que toca aos resultados obtidos, uma comparação com soluções propostas por utilizadores humanos seria uma mais valia para a comparação da qualidade das soluções propostas pelo sistema. Neste teste seria pedido a um certo número de compositores que orquestrassem um som tendo como referência o som objetivo. De igual maneira a aplicação seria utilizada para orquestrar o mesmo som objetivo e as soluções obtidas quer pelos compositores quer pelo sistema seriam comparadas. Desta forma seria possível comparar a qualidade e utilidade das soluções propostas pelo sistema. Finalmente, a criação de uma interface gráfica mais apelativa poderia aumentar a facilidade de interação com o sistema por parte dos utilizadores. Na forma atual, o utilizador necessita de correr um script MATLAB fornecendo a localização da base de dados, a localização do som objetivo e o número máximo de sons que podem estar presentes nas soluções. A substituição deste script por uma interface gráfica em que o utilizador escolheria os diversos parâmetros numa forma muito mais intuitiva melhoraria a usabilidade do sistema. A interface gráfica apresentada no final da execução (ver figura 5.9) pode também ser melhorada de forma a permitir ao utilizador, por exemplo, a edição manual dos índices das soluções ou a permitir a combinação de soluções. 7.3 Agradecimentos O projeto Media, Arts and Technologies (MAT), NORTE-07-0124-FEDER-000061, é financiado pelo Programa Operacional Regional do Norte (ON.2 – O Novo Norte), sobre o Quadro de Referência Estratégica Nacional (QREN), através do Fundo Europeu de Desenvolvimento Regional (FEDER), e por fundos nacionais, através da agência de financiamento Portuguesa, Fundação para a Ciência e a Tecnologia (FCT). Referências [1] José Abreu, Marcelo Caetano, e Rui Penha. Musical Orchestration Using Biological Principles. Em 1st Doctoral Congress in Engineering, 2015. [2] John Grey. Multidimensional Perceptual Scaling of Musical Timbres. The Journal of the Acoustical Society of America, 61(5):1270–1277, 1977. [3] Grégoire Carpentier, Gérard Assayag, e Emmanuel Saint-James. Solving the Musical Orchestration Problem using Multiobjective Constrained Optimization with a Genetic Local Search Approach. Journal of Heuristics, 16(5):681–714, 2010. [4] Philip Galanter. The Problem with Evolutionary Art Is ... Em Cecilia Di Chio, Anthony Brabazon, Gianni Di Caro, Marc Ebner, Muddassar Farooq, Andreas Fink, Jörn Grahl, Gary Greenfield, Penousal Machado, Michael O’Neill, Ernesto Tarantino, e Neil Urquhart, editores, Applications of Evolutionary Computation, volume 6025 de Lecture Notes in Computer Science, páginas 321–330. Springer Berlin Heidelberg, 2010. [5] Marcelo Caetano, Jônatas Manzolli, e Fernando Von Zuben. Interactive Control of Evolution Applied to Sound Synthesis. Em The Florida AI Research Society Conference, páginas 51– 56, 2005. [6] Marcelo Caetano, Jônatas Manzolli, e Fernando Von Zuben. Application of an Artificial Immune System in a Compositional Timbre Design Technique, volume 3627 de Lecture Notes in Computer Science, páginas 389–403. Springer Berlin Heidelberg, 2005. [7] Artemis Moroni, Jônatas Manzolli, Fernando Von Zuben, e Ricardo Gudwin. Vox Populi: An Interactive Evolutionary System for Algorithmic Music Composition. Leonardo Music Journal, 10:49–54, 2000. [8] John Biles. GenJam: A Genetic Algorithm for Generating Jazz Solos. Em Proceedings of the International Computer Music Conference, páginas 131–131. International Computer Music Association, 1994. [9] Maria Navarro, Marcelo Caetano, Gilberto Bernandes, Leandro Castro, e Juan Corchado. Automatic Generation of Chord Progressions with an Artificial Immune System. Em Proceedings of EVOMUSART 2015, 2015. [10] Otavio Carpinteiro. A Self-Organizing Map Model for Analysis of Musical Time Series. Em Neural Networks, 1998. Proceedings. Vth Brazilian Symposium on, páginas 140–145, Dec 1998. [11] Pedro de León e José Inesta. Musical Style Identification using Self-Organising Maps. Em Web Delivering of Music, 2002. WEDELMUSIC 2002. Proceedings. Second International Conference on, páginas 82–89. IEEE, 2002. 81 82 REFERÊNCIAS [12] Markus Frühwirth e Andreas Rauber. Self-Organizing Maps for Content-Based Music Clustering, páginas 228–233. Springer, 2002. [13] Leandro Castro e Fernando Von Zuben. aiNet: An Artificial Immune Network for Data Analysis, chapter 12, páginas 231–259. Idea Group Publishing, 2001. [14] Stephen McAdams, Suzanne Winsberg, Sophie Donnadieu, Geert De Soete, e Jochen Krimphoff. Perceptual Scaling of Synthesized Musical Timbres: Common Dimensions, Specificities, and Latent Subject Classes. Psychological Research, 58(3):177–192, 1995. [15] David Psenicka. SPORCH: An Algorithm for Orchestration Based on Spectral Analyses of Recorded Sounds. Em Proceedings of International Computer Music Conference (ICMC), página 184, 2003. [16] Thomas Hummel. Simulation of Human Voice Timbre by Orchestration of Acoustic Music Instruments. Em Proceedings of the International Computer Music Conference (ICMC), página 185, 2005. [17] Grégoire Carpentier, Damien Tardieu, Jonathan Harvey, Gérard Assayag, e Emmanuel SaintJames. Predicting Timbre Features of Instrument Sound Combinations: Application to Automatic Orchestration. Journal of New Music Research, 39(1):47–61, 2010. [18] Gregoire Carpentier. Approche Computationnelle de L’Orchestration Musciale-Optimisation Multicritère sous Contraintes de Combinaisons Instrumentales dans de Grandes Banques de Sons. Tese de doutoramento, Universite Pierre et Marie Curie-Paris VI, 2008. [19] Damien Tardieu e Xavier Rodet. An Instrument Timbre Model for Computer Aided Orchestration. Em Applications of Signal Processing to Audio and Acoustics, 2007 IEEE Workshop, páginas 347–350. IEEE, 2007. [20] Silvano Martello e Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., New York, NY, USA, 1990. [21] Stephen Handel. Timbre Perception and Auditory Object Identification. Hearing, páginas 425–461, 1995. [22] Marcelo Caetano e Xavier Rodet. Musical Instrument Sound Morphing Guided by Perceptually Motivated Features. Audio, Speech, and Language Processing, IEEE Transactions on, 21(8):1666–1675, Aug 2013. [23] John Grey e John Gordon. Perceptual Effects of Spectral Modifications on Musical Timbres. The Journal of the Acoustical Society of America, 63(5):1493–1500, 1978. [24] Carol Krumhansl. Why is Musical Timbre so Hard to Understand. Structure and perception of electroacoustic sound and music, 9:43–53, 1989. [25] Jochen Krimphoff, Stephen McAdams, e Suzanne Winsberg. Caractérisation du Timbre des Sons Complexes.II. Analyses Acoustiques et Quantification Psychophysique. J. Phys. IV France, 04(C5):625–628, 1994. [26] Anne Caclin, Stephen McAdams, Bennett Smith, e Suzanne Winsberg. Acoustic Correlates of Timbre Space Dimensions: A Confirmatory Study Using Synthetic Tones. The Journal of the Acoustical Society of America, 118(1):471–482, 2005. REFERÊNCIAS 83 [27] Perfecto Herrera, Xavier Serra, e Geoffroy Peeters. Audio Descriptors and Descriptor Schemes in the Context of MPEG-7. Proceedings of the 1999 ICMC, Beijing, China, 1999. [28] Alex Fraser. Simulation of Genetic Systems by Automatic Digital Computers. II. Effects of Linkage on Rates of Advance Under Selection. Australian Journal of Biological Science, 10:492–499, 1957. [29] Hans Bremermann. The Evolution of Intelligence: The Nervous System as a Model of Its Environment. University of Washington, Department of Mathematics, 1958. [30] John Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975. [31] Melanie Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1996. [32] Leandro De Castro e Fernando Von Zuben. Artificial Immune Systems: Part I - Basic Theory and Applications. Universidade Estadual de Campinas, Tech. Rep, 210, Dec 1999. [33] Frank Burnet. Clonal Selection and After, páginas 63–85. Marcel Dekker Inc, 1978. [34] Frank Burnet. The Clonal Selection Theory of Acquired Immunity. University Press Cambridge, 1959. [35] Leandro Castro e Jon Timmis. An Artificial Immune Network for Multimodal Function Optimization. Em Evolutionary Computation, 2002. CEC ’02. Proceedings of the 2002 Congress on, volume 1, páginas 699–704, May 2002. [36] Gustav Nossal. Negative Selection of Lymphocytes. Cell, 76(2):229–239, 1994. [37] Polly Matzinger. Tolerance, Danger, and the Extended Family. Annual review of immunology, 12(1):991–1045, 1994. [38] Uwe Aickelin e Steve Cayzer. The Danger Theory and Its Application to Artificial Immune Systems. arXiv preprint arXiv:0801.3549, 2008. [39] Niels Jerne. Towards a Network Theory of the Immune System. Em Annales d’immunologie, volume 125, páginas 373–389, 1974. [40] Carlos Coello e Nareli Cortés. Solving Multiobjective Optimization Problems Using an Artificial Immune System. Genetic Programming and Evolvable Machines, 6(2):163–190, 2005. [41] Masataka Goto, Hiroki Hashiguchi, Takuichi Nishimura, e Ryuichi Oka. RWC Music Database: Popular, Classical and Jazz Music Databases. Em ISMIR, volume 2, páginas 287–288, 2002. [42] Geoffroy Peeters. A large set of audio features for sound description (similarity and classification) in the CUIDADO project. Relatório técnico, IRCAM, 2004. [43] Harry Olson. The Measurement of Loudness. Audio Magazine, páginas 18–22, 1972. [44] Arturo Camacho. SWIPE: A Sawtooth Waveform Inspired Pitch Estimator for Speech and Music. Tese de doutoramento, University of Florida, 2007. 84 REFERÊNCIAS [45] Adam Lipowski e Dorota Lipowska. Roulette-wheel Selection via Stochastic Acceptance. Physica A: Statistical Mechanics and its Applications, 391(6):2193–2196, 2012. [46] Olivier Lartillot e Petri Toiviainen. A Matlab Toolbox for Musical Feature Extraction from Audio. Em International Conference on Digital Audio Effects, páginas 237–244, 2007. [47] Dan Ellis. A Phase Vocoder in Matlab. http://labrosa.ee.columbia.edu/ matlab/pvoc/, 2002. Acedido: 13-07-2015. [48] Malcolm Slaney. Auditory Toolbox. Relatório técnico 45, Apple Computer, Inc., 1994. [49] Sebastian Kraft e Udo Zölzer. BeaqleJS: HTML5 and JavaScript based Framework for the Subjective Evaluation of Audio Quality. Em Linux Audio Conference. Karlsruhe, Germany, 2014. [50] Philippe Esling, Grégoire Carpentier, e Carlos Agon. Dynamic Musical Orchestration Using Genetic Algorithms and a Spectro-Temporal Description of Musical Instruments, volume 6025 de Lecture Notes in Computer Science, páginas 371–380. Springer Berlin Heidelberg, 2010.