Computação Evolutiva

Alunos: Diego de Souza Silva, Cesar Augusto Silva de Carvalho, Wellington Pereira Gonçalves 

Computação Evolutiva

Computação Evolucionária (CE) é um ramo de pesquisa emergente da Inteligência Artificial que propõe um novo paradigma para solução de problemas inspirado na Seleção Natural (Darwin 1859).

Entende- se como (CE) um conjunto de técnicas de busca e otimização de soluções para um processo complexo com grande número de variáveis, que se inspiram na evolução natural das espécies (Indivíduos e populações competem entre si por recursos, sobrevivência e por parceiros, os mais bem-sucedidos nessa competição geram mais descendentes)

As técnicas incluem (Banzhaf 1998): Programação Evolucionária, Estratégias Evolucionarias, Algoritmo Genéticos e Programação Genética. A comunidade de inteligência artificial estão cada vez mais utilizando esses métodos para obter modelos de inteligência computacional(Barreto 1997)

Programação Evolutiva:

L. FOGEL et al. (1966) propuseram a programação evolutiva como uma técnica de simulação da evolução para desenvolver uma forma alternativa de inteligência artificial. O comportamento inteligente era visto como requerendo as seguintes habilidades, predizer um determinado ambiente e responder apropriadamente a este ambiente baseado na predição feita O ambiente foi considerado de forma genérica como sendo descrito por uma sequência de símbolos tomados a partir de um alfabeto finito. O problema evolutivo foi então definido como sendo a evolução de um algoritmo que pudesse operar na sequência de símbolos até então observada de tal forma a produzir um símbolo de saída que maximizaria o desempenho do algoritmo em relação ao próximo símbolo a ser apresentado, dada uma função de custo bem definida.

As Primeiras Técnicas de (PE)

  FOGEL et al. (1966) propuseram a programação evolutiva para operar com máquinas de estado finito da seguinte forma: Uma população de máquinas de estado finito está exposta ao ambiente, ou seja, à sequência de símbolos observados até o momento.

Como cada símbolo é apresentado à cada máquina pai, o símbolo de saída é observado (predito) e comparado ao próximo símbolo de entrada. A qualidade desta predição é medida utilizando-se uma dada função de custo (p.ex. erro absoluto, erro quadrático, etc.). Após a última predição ser feita, uma função de custo (payoff) para cada símbolo vai indicar o fitness de cada máquina. Máquinas “filhas” são geradas aplicando-se uma mutação aleatória em cada máquina pai e cada pai produz um único filho. Cinco tipos básicos de mutação são possíveis para a máquina de estado finito: Mude um símbolo de saída; mude uma transição de estado; adicione um estado; delete um estado existente; e mude o estado inicial.

Estratégias evolutivas:

Estratégia Evolutiva (ES – Evolution Strategy) é uma classe de algoritmos da Computação Evolucionária e surgiu para solucionar problemas de otimização de parâmetros contínuos ou discretos. Foi proposto por I. Rechenberg e H. P. Schwefel, na Alemanha, com a publicação de um livro em 1973 que fundamenta a Estratégia Evolutiva.

A característica principal da ES é a adaptação online dos parâmetros que regem o processo evolutivo. Como consequência, um algoritmo baseado em ES executa simultaneamente duas tarefas: a solução de um problema de otimização específico e a própria calibragem do algoritmo para resolver o problema em questão.

A Estratégia Evolutiva é a que mais se aproxima da teoria evolutiva de Lamarck. Essa teoria, publicada em, defende que as variações no meio ambiente levam o indivíduo a se adaptar buscando a perfeição, seguindo duas leis: a do uso e desuso e a da transmissão dos caracteres adquiridos. Nesse contexto, a Estratégia Evolutiva utiliza como operações a mutação auto adaptativa e a recombinação com operador de seleção determinístico no processo de busca da solução.

Algoritmos evolutivos:

Os algoritmos evolutivos como o próprio nome diz eles mantêm uma população que evoluem, de acordo com as regras de seleção e operadores, sendo esses operadores de busca.

De acordo com Fernando J. Os algoritmos evolutivos não podem ser estipulados como algoritmos de processos de busca aleatória, porque a evolução não é aleatória, eles são algoritmos simples, rápidos e poderosos, o processo de busca dos algoritmos pode ser feito por meio de seleção por roleta e por meio de seleção por torneio.

Onde a seleção por roleta significa que cada indivíduo da população é representado na roleta por seu índice de aptidão, sendo assim o indivíduo com maior aptidão é dado a ele uma porção maior da roleta e assim sucessivamente.

E o meio de seleção por torneio diz que n indivíduos são escolhidos aleatoriamente para formar uma subpopulação temporária, nesse grupo que foi formado o indivíduo selecionado vai depender de uma probabilidade pré-definida onde o algoritmo irá selecionar o melhor deles para ser o escolhido naquela subpopulação e não na população completa.

Programação Genéticas:

Programação Genética (PG) foi criada por John Koza (koza1992), para geração de programas de computador, é uma área muito promissora de pesquisa no ramo da inteligência artificial.

Podemos dizer que a (PG) é a evolução de um conjunto de programas com o objetivo de aprendizagem por indução (Banzhaf 1998). A ideia da programação genética é ensinar computadores a se programarem.

Ela segue quase que o modelo de algoritmos evolutivos mantendo uma população de programas e escolhendo os melhores para aplicação dos operadores genéticos na modificação e conversão para uma determinada solução.

Como a PG é relativamente complexa e variável, ela é estruturada em uma árvore de sintaxe abstrata composta por funções em seus nós internos e por terminais em suas folhas, ou seja, é definido pelo conjunto de funções terminais (Koza 1992).