Presentasjon av caseområdet

Alguns ramos distintos de pesquisa desenvolveram técnicas computacionais que construíram os chamados AEs. Os próximos tópicos abordarão alguns dos principais algoritmos e suas características.

3.3.1 Programação Evolutiva

A programação evolutiva foi proposta em [44] com o objetivo de utilizar os conceitos de evolução no desenvolvimento de Inteligência Artificial na qual cada indivíduo da população é representado por uma máquina de estados finitos (que processa uma sequência de símbolos). A função de aptidão é calculada através da comparação do valor da saída da máquina com a saída esperada para solução do problema. São características da programação evolutiva:

A reprodução é feita apenas por operadores de mutação, sendo que todos os indivíduos da população atual geram novos descendentes (reprodução assexuada);

A seleção de indivíduos para a próxima geração ocorre através da competição dos novos indivíduos com seus μ pais onde somente os indivíduos com maior fitness sobrevivem.

Este domínio total dos melhores indivíduos garante a sobrevivência dos k- melhores indivíduos, porém pode diminuir significativamente a diversidade de indivíduos, podendo estagnar em ótimos locais e/ou aumentar o tempo de convergência do algoritmo [38].

3.3.2 Estratégias Evolutivas

As estratégias evolutivas foram desenvolvidas com o objetivo de solucionar problemas de otimização de parâmetros. Nestes algoritmos um pai gera um único descendente (reprodução assexuada) e ambos competem pela sobrevivência. São características das estratégias evolutivas:

Cada gene no cromossomo representa uma dimensão do problema (com alelo representado em ponto flutuante);

Os cromossomos são compostos por dois vetores, um com valores para cada dimensão e outro com o desvio padrão desses valores;

A geração de um novo indivíduo é feita através da reprodução assexuada (operador de mutação), com distribuição de probabilidade Gaussiana, média zero e com desvio padrão do gene correspondente no pai;

Os indivíduos competem com os pais sobrevivendo apenas os melhores.

Segundo [38], o modelo original de Estratégia Evolutiva (EE) possui convergência lenta, sendo evoluído em outros modelos posteriores.

3.3.3 Algoritmos Genéticos

Os Algoritmos Genéticos (AGs) são uma das principais frentes de pesquisa em Algoritmos Evolutivos. Eles foram concebidos em 1960, por John Holland, com o objetivo inicial de estudar os fenômenos relacionados à adaptação das espécies e da seleção natural que ocorre na natureza, bem como desenvolver uma maneira de incorporar estes conceitos aos computadores.

A principal diferença dos AGs é a criação de descendente pelo operador de recombinação [38]. Além disso, a utilização de operadores de mutação e recombinação equilibra dois objetivos aparentemente conflitantes: o aproveitamento das melhores soluções e a exploração do espaço de busca.

A execução dos AGs pode ser resumida nos seguintes passos:

• Escolha da população inicial: normalmente formada por indivíduos criados aleatoriamente;

• Avaliação da população: através do cálculo do fitness;

• Obtenção da nova geração: aplicando-se sobre os indivíduos selecionados operações de recombinação e mutação;

• Seleção dos sobreviventes: através da escolha dos indivíduos com melhor fitness;

• Condição de parada: repetição dos passos de obtenção da nova geração e seleção dos sobreviventes até que uma solução aceitável seja encontrada, ou até que o número predeterminado de passos seja atingido, ou, ainda, até que o algoritmo não consiga mais melhorar a solução já encontrada.

3.3.4 Outros Algoritmos Evolutivos

Mais recentemente, diversos aspectos complexos em problemas de otimização e aprendizado de máquina têm sido pesquisados na Computação Evolutiva (CE). Esses estudos têm buscado o desenvolvimento de AEs mais eficientes [40] e seus conteúdos serão apenas citados nos tópicos abaixo.

• Programação Genética: técnica de geração automática de programas de computador criada por John Koza [45] e inspirada na teoria de AG. Em Programação Genética (PG) é possível criar e manipular software geneticamente, aplicando conceitos herdados da Biologia para gerar programas de computador automaticamente;

• Micro-AG: variações de AGs desenvolvidas para evoluir eficientemente soluções utilizando populações com poucos indivíduos. O primeiro trabalho envolvendo micro-AGs foi proposto por [46] e atualmente possui importância especial em projetos onde a disponibilidade de recursos computacionais é limitada;

• Algoritmos de Estimação da Distribuição: técnicas de aprendizagem automatizada de correlações entre as variáveis codificadas na solução do problema, gerando um ajuste no modelo de probabilidade dos indivíduos e tornando desnecessária a especificação de determinados parâmetros dos AEs Canônicos (como a taxa de mutação e de recombinação). Uma fonte para pesquisa destes algoritmos é encontrada em [47].

3.3.5 Técnicas de Seleção

O objetivo da seleção é escolher um ou mais indivíduos para gerar um ou mais descendentes para a próxima população do processo evolutivo. Assim, devido

à importância desta etapa na composição dos AEs, a escolha da estratégia adotada deve ser realizada com conhecimento das diferentes técnicas existentes. Assim, de uma maneira bastante sucinta, segue a descrição de algumas destas técnicas existentes na literatura:

• Seleção por torneio: um subconjunto da população com k indivíduos é sorteado e os melhores indivíduos desse grupo são selecionados para decidir qual irá reproduzir;

• Seleção em rank: utiliza as posições dos indivíduos, quando ordenados de acordo com o fitness, para determinar a probabilidade de seleção. Podem ser usados mapeamentos lineares ou não lineares para determinar a probabilidade de seleção;

• Seleção Boltzmann: estabelece uma pressão de seleção diferente à cada iteração ou geração do algoritmo genético. Inicialmente, este operador promove a reprodução de indivíduos com fitness baixo, permitindo assim manter a diversidade da população e evitar convergências prematuras, e posteriormente aumenta a pressão para enfatizar os indivíduos com fitness alto.