Computação evolucionária

Origem: Wikipédia, a enciclopédia livre.

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.

[editar] 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.

[editar] Idéias básicas

A CE possui as três seguintes idéias 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.

a) A 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.

b) A 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.

c) A 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.

[editar] Á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. Dentre estas se pode citar Formações de Cristais, Colônia de Formigas,... Além destes, também surgiram os primeiros estudos a respeito do Enxame de Partículas. Tal proposta também tem por base a natureza e a analogia é feita com bandos de pássaros, cardumes, enxames,...