Computação Evolucionária

1) Introdução

A computação evolucionária é um ramo da ciência da computação que tem por base os mecanismos evolutivos encontrados na natureza. Esses mecanismos estão diretamente relacionados com a teoria da evolução de Darwin, onde ele afirma que a vida na Terra é o resultado de um processo de seleção, feito pelo meio ambiente, em que somente os mais aptos e adaptados possuirão chances de sobreviver e, conseqüentemente, reproduzir-se.

Computação Evolucionária emprega conceitos de mutação, recombinação e seleção natural originados na neurociência.

Algoritmos evolucionários, algoritmos neurais e algoritmos de comportamento coletivo são atualmente implementados em computadores convencionais.

Computação evolucionária é caracterizada por se inspirar no processo de evolução natural. A principal metáfora de computação evolucionária relaciona a evolução natural com uma estratégia de tentativa e erro para resolução de problemas. Nesta abordagem, o ambiente representa o problema, o individuo é um candidato a solução e a função de adaptabilidade avalia a qualidade de cada solução. O processo evolucionário deve gerar resultar nas melhores soluções.

É uma área de pesquisa interdisciplinar que compreende diversos paradigmas inspirados no princípio Darwiniano da evolução das espécies. O atual estágio de pesquisa considera, entre outros, os seguintes paradigmas:

1. Algoritmos Genéticos (Genetic Algorithms - GA)
2. Programação Genética (Genetic Programming - GP)
3. Hardware Evolucionário (Evolvable Hardware - EH)
   

Outros paradigmas (não apresentados no diagrama da página anterior) incluem:

1. Programação Evolucionária (Evolutionary Programming - EP);
2. Algoritmos Evolucionários (Evolutionary Algorithms -EA);
3. Estratégias de Evolução (Evolution Strategies - ES); e
4. Sistemas Classificadores (Classifier Systems - CFS).

2) História

Os primeiros passos dados na área da Computação Evolucionária (CE) foram de biólogos e geneticistas. Estes tinham interesse em simular os processos vitais de um ser humano em um computador.

Dentre os cientistas destacam-se os nomes de Barricelli, Fraser, Martin e Cockerham. Na década de 60, um grupo de cientistas, em que o nome de Holland se destaca, iniciaram um estudo em que era implementada uma população de n indivíduos onde cada um possuía seu genótipo e estava sujeito a operações de seleção, recombinação e mutação.

Tal estudo foi modelado e passou a ser conhecido como algoritmo genético. Holland chegou a propor um quarto operador, a inversão. Entretanto ele não obteve destaque na comunidade científica, não vindo a ser muito utilizado. Uma das primeiras aplicações na área de CE foi relacionada a algoritmos genéticos. Bagley, em 1967, utilizou em uma parte de sua dissertação Algoritmos Genéticos para desenvolver sistemas classificadores.

3) Características básicas

A CE possui três características básicas: criação de uma população de soluções, criação de uma função de avaliação e criação dos operadores de seleção, recombinação e mutação.

1. Criação de uma população de soluções: é necessário que haja uma população inicial de soluções possível para o problema proposto. Essa população pode ser gerada aleatoriamente ou através de alguma técnica. Cada indivíduo dessa população terá registrado em si os parâmetros que descrevem a sua respectiva solução para o problema.
2. Criação de uma função de avaliação: a função de avaliação terá o trabalho de julgar a aptidão de cada indivíduo da população. Ela não precisará deter o conhecimento de como encontrar a solução do problema. Somente precisará julgar a qualidade da solução que está sendo apresentada por aquele indivíduo. A função é definida através da codificação das soluções para o problema para que se possa avaliar se o indivíduo está ou não apto.
3. Criação dos operadores seleção, recombinação e mutação: é necessário gerar novas populações para que se encontre o mais apto. Essas são chamadas de gerações e são obtidas através da aplicação de três operadores: seleção, recombinação e mutação. Na seleção escolhem-se os indivíduos mais aptos para gerarem descendentes. Essa reprodução pode ocorrer de duas formas: um indivíduo gera a descendência ou um par de indivíduos geram a descendência. O primeiro caso simula uma reprodução assexuada e o segundo uma reprodução sexuada. É importante destacar que os descendentes serão diferentes de seus antecedentes. Na recombinação ocorre a troca de material genético entre o par de antecedentes definindo assim a carga genética dos descendentes. Dessa forma, cada descendente desse par herdará uma parte do material genético de seus antecedentes escolhidos de forma aleatória. E na mutação ocorrem mudanças aleatórias no material genético do indivíduo. Dessa forma o indivíduo estará mais apto dentro daquela população. A simulação da passagem de gerações ocorre na repetição deste ciclo, ou seja, a cada iteração.

4) Áreas da computação evolucionária

Os estudos relacionados a CE não pararam. Outras áreas surgiram e ganharam importância no meio científico.

Recentemente, novas concepções de meta-heurísticas emergiram e todas diretamente relacionadas com a CE, por exemplo:

1. Formações de Cristais
2. Colônia de Formigas
3. Enxame de Partículas

Tais propostas também têm uma forte motivação física ou biológica tais como bandos de pássaros, cardumes, enxames, entre outros.

Fonte: Wikipedia