Os AG s˜ao heur´ısticas de busca que copiam de certo modo o comportamento da evolu¸c˜ao natural assim como definida por Darwin (2003). ´E um m´etodo muito utilizado para a procura de solu¸c˜oes para problemas de otimiza¸c˜ao por sua grande flexibilidade.
Assim como na biologia, v´arias solu¸c˜oes podem ter um gen´otipo (sua representa¸c˜ao) com v´arios tra¸cos herd´aveis. Estes tra¸cos s˜ao transmitidos de gera¸c˜ao a gera¸c˜ao. Quando um tra¸co ´e herdado v´arias vezes, tem-se um sinal de que este seja uma tra¸co positivo para o problema em quest˜ao. Com o passar do tempo alguns indiv´ıduos n˜ao sobrevi- vem e outros d˜ao origem `a nova gera¸c˜ao, com alguns tra¸cos que estar˜ao provavelmente repetidamente presentes, a qual espera-se ter maior aptid˜ao.
Em seus estudos iniciais, Darwin n˜ao sabia exatamente como as varia¸c˜oes ocorriam entre as gera¸c˜oes. Este problema foi resolvido pela gen´etica moderna, que criou a base te´orica para explicar os processos gen´eticos, como muta¸c˜oes e recombina¸c˜ao, que levam a variar mais substancialmente o gen´otipo dos novos indiv´ıduos. As muta¸c˜oes podem gerar op¸c˜oes de explora¸c˜ao da solu¸c˜ao, que n˜ao seriam exploradas apenas pelo cruzamento.
Como o gen´otipo leva sempre a um fen´otipo, e uma sele¸c˜ao natural atua sobre este, espera-se que os melhores indiv´ıduos tenham maior chance de sobreviver para as pr´oximas gera¸c˜oes. A representa¸c˜ao esquem´atica de um AG est´a na Figura 3.1.
No algoritmo, uma popula¸c˜ao que ´e representada por cadeias de caracteres, chamadas de cromossomos, formam os indiv´ıduos, que n˜ao s˜ao nada mais do que poss´ıveis solu¸c˜oes para um problema. Com o processo evolutivo, melhores solu¸c˜oes passam a ser geradas com o tempo. Um pseudoc´odigo simplificado de um AG pode ser descrito como no
1
Figura 3.1: Representa¸c˜ao Esquem´atica de um Algoritmo Evolutivo
Algoritmo 3.1.
Algoritmo 3.1: AG
Entrada: Popula¸c˜ao de indiv´ıduos, Fun¸c˜ao Objetivo Resultado: Indiv´ıduo
enquantocrit´erio de parada n˜ao ´e satisfeito fa¸ca 1
Lista dos Pais ← Sele¸c˜ao(Popula¸c˜ao de Indiv´ıduos, Fun¸c˜ao Objetivo); 2
Popula¸c˜ao ← Reprodu¸c˜ao(Lista de Pais); 3
Popula¸c˜ao ← Muta¸c˜ao(Popula¸c˜ao); 4
fim 5
retornaO melhor indiv´ıduo analisado durante o processo; 6
A fun¸c˜ao-objetivo cont´em uma fun¸c˜ao capaz de analisar a qualidade de um indiv´ıduo e por isso ´e necess´aria para que a lista dos pais seja gerada levando em considera¸c˜ao a qualidade destes indiv´ıduos. Assim, esses indiv´ıduos que provavelmente s˜ao de boa qualidade geram uma nova popula¸c˜ao que passar´a pelo mesmo processo.
Estes tipos de algoritmos tˆem v´arias fun¸c˜oes musicais, ´area normalmente denominada M´usica Evolutiva (ME). As ´areas de maior aten¸c˜ao em ME s˜ao composi¸c˜ao e design de som. Naquela, a fun¸c˜ao-objetivo pode ser a similaridade com um determinado compo- sitor ou estilo, podendo-se assim evoluir pe¸cas `a maneira de um compositor ou estilo
espec´ıfico, como feito por Biles (1994). Quando o trabalho ´e desenvolvido no sentido de um estilo particular de composi¸c˜ao, ´e mais f´acil definir crit´erios que levar˜ao ao ob- jetivo proposto. J´a em trabalhos com a necessidade de composi¸c˜oes mais criativas ou inovadoras, a cria¸c˜ao de um algoritmo ´e mais desafiadora.
Na ´area de design de som, a t´ecnica j´a tem a sua efic´acia comprovada para sintetizar sons a partir de sons alvos ou desenvolver novos sons (Johnson 2003). O gen´otipo dos indiv´ıduos pode ser feito pelos parˆametros que definem os sons. Nos casos em que se precisa achar sons parecidos com um certo instrumento tradicional, a proximidade com o dado instrumento pode ser a fun¸c˜ao-objetivo. J´a para o procura de novos sons ´e mais dif´ıcil a rela¸c˜ao com fun¸c˜oes objetivo e a avalia¸c˜ao humana ´e a norma (Woolf 1999).
A melhor escolha dos operadores gen´eticos, da forma de representa¸c˜ao, fun¸c˜ao de avalia¸c˜oes, assim como outros pontos da implementa¸c˜ao dependem muito do ramo de aplica¸c˜ao do algoritmo e uma an´alise dos experimentos realizados presentes na literatura ´e fundamental para o desenvolvimento de um algoritmo deste tipo.
Talvez uma das mais intrigantes perguntas a serem respondidas antes de determinar como criar um AE para CA ´e como determinar a qualidade de uma solu¸c˜ao e, caso esta determina¸c˜ao seja feita por um mentor humano, como evitar um gargalo de fitness, ou seja, o tempo gasto para avaliar v´arias solu¸c˜oes que pode atrapalhar ou at´e impedir o mentor de fazer uma avalia¸c˜ao justa das solu¸c˜oes. Al´em disso, ´e importante definir quais ser˜ao as solu¸c˜oes iniciais, que podem ser diversas por´em n˜ao musicais, ou musicais e n˜ao criativas. Em muitos casos a defini¸c˜ao do problema n˜ao ´e coerente, o que faz o algoritmo convergir para solu¸c˜oes “corretas”que n˜ao atendem ao objetivo inicial.
AG s˜ao sistemas muito complexos e dif´ıceis de analisar. V´arios resultados puramente emp´ıricos s˜ao encontrados na literatura, sendo `as vezes inconsistentes para a compara¸c˜ao entre m´etodos para a mesma aplica¸c˜ao. Por´em o entendimento de como os AE funcionam sempre pode ser obtido por an´alise de alguns estudos pr´evios que s˜ao ´uteis para poupar tempo consideravelmente no desenvolvimento de novos sistemas.
Nas pr´oximas subse¸c˜oes ser˜ao analisadas quais quest˜oes precisam de resposta para o desenvolvimento de sistemas de CA baseados em AG.