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

Computação Inspirada na Natureza

A Computação Inspirada na Natureza, inclui todas as estratégias desenvolvidas a partir de ou inspiradas em algum mecanismo biológico ou natural.

Como exemplos têm-se as redes neurais artificiais (Haykin, 1999), a computação evolutiva
(Bäck et al., 2000a,b), a inteligência coletiva (Bonabeau et al., 1999;
Kennedy et al., 2001), e os sistemas imunológicos artificiais (Dasgupta,
1999; de Castro & Timmis, 2002).

É importante destacar que os próprios aspectos cognitivos e do raciocínio humano representam mecanismos naturais de fundamental importância. Logo, a inteligência artificial simbólica (Russell & Norvig, 2003) e os sistemas nebulosos (fuzzy) (Pedrycz & Gomide, 1998), essencialmente relacionados a estes temas, também podem inserir-se no escopo
da computação natural.

Estas três sub-áreas da computação natural têm patrocinado a proposição de poderosas ferramentas computacionais para a solução de problemas complexos de engenharia e têm permitido a geração de novos paradigmas de computação (Paton, 1994; Yokomori, 2002; Paton
et al., 2003).

É importante salientar que se trata de uma linha de pesquisa promissora, não apenas porque resultados concretos e convincentes têm sido produzidos pela aplicação de ferramentas concebidas exclusivamente com base nos princípios da computação natural (Zimmermann, 1999; Dasgupta & Michalewicz, 1997), mas porque diversos aspectos da biologia podem ser melhor tratados tendo em mãos ferramentas computacionais apropriadas.

1. Computação evolucionária emprega conceitos de mutação, recombinação e seleção natural originados na neurociência.
2. Computação neural é inspirada nas estruturas neurais densamente interconectadas do sistema nervoso central.
3. Computação coletiva utiliza o comportamento coletivo de enxames de organismos provenientes da biologia.
4. Computação molecular se baseia em paradigmas de biologia molecular.
5. Computação quântica é fundamentada em física quântica para explorar paralelismo quântico.

O primeiro ramo da computação natural é também o mais antigo e bem consolidado. Com a descoberta de vários princípios e teorias sobre a natureza e o desenvolvimento de diversos modelos, pesquisadores de áreas como engenharia e computação perceberam que era possível
usar estes princípios, teorias e modelos para a implementação de sistemas computacionais com grande potencial de resolver problemas. A computação inspirada na natureza
compreende, principalmente: 1) redes neurais artificiais; 2) algoritmos evolutivos; 3) inteligência coletiva (swarm intelligence); 4) sistemas imunológicos artificiais; e 5) outros (modelos baseados
em crescimento e desenvolvimento celular, modelos culturais, etc.).

Um trabalho pioneiro da computação inspirada na biologia foi apresentado por McCulloch & Pitts (1943), introduzindo o primeiro modelo matemático (lógico) de um neurônio. Este modelo,
também conhecido como neurônio artificial, deu origem a uma linha de pesquisa denominada de redes neurais artificiais (Fausett, 1994; Bishop, 1996; Haykin, 1999; Kohonen, 2000).

Outra abordagem de computação motivada pela biologia surgiu em meados da década de 1960 com os trabalhos de I. Rechenberg (1973), H. P. Schwefel (1965), L. Fogel (Fogel et al.,
1966), e J. Holland (1975). Estes trabalhos deram origem à linha de pesquisa
conhecida atualmente como computação evolutiva, composta pelos algoritmos
evolutivos (Goldberg, 1989; Bäck et al., 2000a,b; Fogel, 1995; Bahnzaf et al.,
1998; Michalewicz, 1996; Mitchell, 1998; Beyer, 2001; Koza, 1992), que
usam idéias da biologia evolutiva para desenvolver algoritmos a serem empregados
em tarefas de busca e otimização.

A inteligência coletiva (swarm intelligence) possui duas principais frentes
de pesquisa: algoritmos baseados no comportamento coletivo de insetos sociais
(Bonabeau et al., 1999), e algoritmos baseados em comportamentos
sócio-cognitivos humanos (Kennedy e al., 2002). No primeiro caso, o comportamento
coletivo de formigas e outros insetos levou ao desenvolvimento de
algoritmos para a solução de problemas de otimização combinatória, agrupamento
de dados (clustering), robótica coletiva, e outros. Algoritmos baseados
em sócio-cognição são eficazes para a realização de buscas em espaços contínuos.

Os sistemas imunológicos artificiais possuem suas idéias extraídas do
sistema imunológico dos vertebrados e seus modelos teóricos (Dasgupta, 1999;
de Castro & Timmis, 2002; Timmis et al., 2003). É uma nova linha de pesquisa
que surgiu em meados da década de 1980. Suas aplicações vão desde a biologia
(p. ex. bioinformática) até a robótica (p. ex. navegação autônoma).

Outras técnicas emergentes decomputação inspirada na natureza são os algoritmos culturais, o algoritmo de simulated annealing, os sistemas baseados em crescimento e desenvolvimento,
os modelos baseados em células e tecidos e vários outros (Aarts & Korst, 1989; Paton, 1994; Paton et al., 2003; Kumar & Bentley, 2003; Kochenberger & Glover, 2003).