CapÃtulo 1 : Computação evolutiva

O termo "computação evolutiva" refere-se tanto a uma área de inteligência artificial e computação suave no campo da ciência da computação que estuda vários algoritmos de otimização e uma família de algoritmos para otimização global que são inspirados pela evolução biológica. Para falar mais tecnicamente, eles pertencem à família de solucionadores de problemas de tentativa e erro de base populacional que têm um sabor de otimização metaheurística ou estocástica.

O processo de computação evolutiva começa por gerar um conjunto preliminar de soluções possíveis, que é então iterativamente melhorado. A fim de desenvolver cada nova geração, primeiro removemos soluções menos desejáveis usando um processo estocástico e, em seguida, fazemos ajustes aleatórios minuciosos. Na linguagem da biologia, uma população de soluções potenciais é "mutada" depois de ser exposta à seleção natural (ou mesmo à seleção artificial). Como consequência disso, a população acabará por evoluir para crescer em aptidão, ou seja, a função de aptidão que o algoritmo selecionou para representar a aptidão.

Como resultado de sua capacidade de fornecer soluções altamente ótimas em uma variedade diversificada de contextos de problemas, as abordagens de computação evolutiva estão se tornando mais proeminentes no campo da ciência da computação. Existem muitas outras versões e extensões disponíveis, cada uma das quais é adaptada a uma família específica de problemas ou estrutura de dados. No campo da biologia evolutiva, a computação evolutiva também é usada ocasionalmente na forma de um método experimental in silico para investigar vários aspetos dos processos evolutivos gerais.

A ideia de imitar processos evolutivos para resolver problemas remonta a uma época anterior à invenção dos computadores e inclui exemplos como a proposta de Alan Turing, em 1948, de uma técnica conhecida como busca genética. O principal objetivo de Holland era utilizar algoritmos genéticos para pesquisar a adaptação e descobrir como ela pode ser reproduzida, em contraste com as outras técnicas, que estavam em grande parte focadas em encontrar soluções para os problemas. Uma técnica de seleção artificial foi usada para alterar populações de cromossomos, cada um representado como cordas de bits. Este procedimento selecionado para certos bits 'alelos' incluídos dentro da cadeia de bits. As interações entre cromossomas foram uma das muitas abordagens utilizadas para replicar a recombinação do ADN que ocorre naturalmente entre vários tipos de animais. Os algoritmos genéticos de Holland monitoravam populações enormes, enquanto os sistemas anteriores só podiam rastrear uma única criatura ótima de cada vez (fazendo com que os descendentes competissem com seus pais) (tendo muitos organismos competindo a cada geração).

Na década de 1990, surgiu um novo método de computação evolutiva que mais tarde seria conhecido como programação genética. John Koza foi uma das muitas pessoas que apoiaram esta linha de pensamento. Dentro desse tipo de algoritmo, o que estava evoluindo era realmente um programa que havia sido criado em uma linguagem de programação de alto nível (houve algumas tentativas anteriores já em 1958 de usar código de máquina, mas tiveram pouco sucesso). Os programas que Koza usou foram chamados de Lisp S-expressions, e você pode conceituar essas expressões como árvores compostas de sub-expressões. Este modelo possibilita programas de comercialização de subárvores, o que é semelhante à mistura de material genético. O grau em que um programa é capaz de realizar com sucesso uma tarefa pré-determinada lhe rende uma pontuação, e essa pontuação é então empregada em um processo de seleção artificial. O conceito de programação genética tem sido usado com sucesso em várias áreas, incluindo planejamento, indução de sequências e reconhecimento de padrões.

Embora suas contribuições não tenham necessariamente caído em um dos principais ramos históricos do assunto, um grande número de pessoas adicionais desempenhou um papel no desenvolvimento da computação evolutiva ao longo de sua história. Nils Aall Barricelli desenvolveu as primeiras simulações computacionais da evolução em 1953, utilizando algoritmos evolutivos e abordagens de vida artificial. Os resultados iniciais destas simulações foram publicados em 1954.

Na maioria das vezes, os métodos de otimização metaheurística estão envolvidos em estratégias de computação evolutiva. O domínio pode ser dividido nas seguintes categorias::

Modelagem baseada em agente

Otimização de colónias de formigas

Sistemas imunitários artificiais

Vida artificial (ver também organismo digital)

Algoritmos culturais

Evolução diferencial

Desenvolvimento ou evolução em duas fases

As técnicas para a estimativa de distribuições

Algoritmos evolutivos

Programação evolutiva

Estratégia de evolução

Programação da expressão genética

Algoritmo genético

Programação genética

Evolução gramatical

Modelo de evolução aprendível

Sistemas de classificação de aprendizagem

Algoritmos meméticos

Neuroevolução

Otimização de enxames de partículas

Auto-organização, incluindo o uso de mapas auto-organizados, bem como aprendizagem competitiva

Inteligência de enxame

O campo da computação evolutiva contém um subcampo conhecido como algoritmos evolutivos. Os algoritmos evolutivos são um subcampo da computação evolutiva porque, em geral, envolvem apenas técnicas que implementam mecanismos evolutivos inspirados na evolução biológica. Esses mecanismos evolutivos incluem reprodução, mutação, recombinação, seleção natural e sobrevivência do mais apto. As soluções candidatas para a questão da otimização atuam como membros de uma população, e a função de custo é responsável por determinar o ambiente em que as soluções "vivem" (ver também função de aptidão). Depois de submeter repetidamente a população aos operadores acima mencionados, a evolução da população acabará por ocorrer.

Há dois fatores principais em ação neste processo que, juntos, fornecem a base dos sistemas evolutivos: Recombinação A variedade essencial e, portanto, a capacidade de originalidade são produzidas através de mutação e cruzamento, enquanto a seleção funciona como uma força motriz para melhorar a qualidade genética.

A estocasticidade pode ser vista em muitas facetas de um processo evolutivo como este. Os bits de informação que foram alterados como resultado da recombinação e mutação são selecionados aleatoriamente. Por outro lado, os operadores de seleção podem ser determinísticos ou estocásticos, dependendo da situação. No segundo cenário, as pessoas que têm uma aptidão mais elevada têm uma maior probabilidade de serem escolhidas do que as pessoas que têm uma aptidão mais baixa, mas, na maioria dos casos, mesmo os indivíduos menos aptos têm a chance de se tornar pais ou viver.

A teoria dos sistemas dinâmicos está ligada aos algoritmos genéticos porque eles são usados para fazer previsões sobre os estados futuros de um sistema. Estas previsões podem ser usadas para modelar sistemas biológicos e biologia de sistemas. Algoritmos genéticos dão metodologias de modelagem. Este é apenas um método dramático de chamar a atenção para a natureza ordenada, bem controlada e altamente organizada do desenvolvimento em biologia; no entanto, pode ser enganoso.

Apesar disso, a aplicação de algoritmos e informática, em particular a teoria computacional, é também crucial para o processo de compreensão da própria evolução; Isto é verdade mesmo quando a semelhança com sistemas dinâmicos é ignorada.

O valor desta teoria é que ela reconhece que não existe uma regulação central do desenvolvimento; em vez disso, o crescimento de organismos é a consequência de interações locais tanto no interior como entre as células. Os conceitos que parecem levar a uma aparente semelhança entre os processos que ocorrem no interior das células e o funcionamento de baixo nível dos computadores atuais são os que nos parecem ser as teorias mais promissoras sobre os paralelos de desenvolvimento de programas.

O paralelo entre a computação e a interação entre sistemas de herança e estrutura biológica, que se acredita revelar um dos desafios mais sérios na compreensão dos primórdios da vida, também está incluído nesta comparação.

Autómatos evolutivos.

A lista de investigadores atualmente em atividade é inerentemente fluida e não pretende ser exaustiva. Em 2007 foi publicado um estudo que analisou a rede da comunidade.

Kalyanmoy Deb

Kenneth A De Jong

Pedro J. Fleming

David B. Fogel

Stephanie Forrest

David E. Goldberg

João Henrique Holanda

Theo Jansen

João Koza

Zbigniew Michalewicz

Melanie Mitchell

Pedro Nordin

Riccardo Poli

Ingo Rechenberg

Hans-Paul Schwefel

A seguir está uma lista das conferências mais importantes no campo da computação evolutiva:

A Association for Computing Machinery's Genetic and Evolutionary Computation Conference (GECCO), Convenção sobre Computação Evolutiva realizada pelo IEEE (CEC), EvoStar é uma organização guarda-chuva que engloba quatro conferências separadas: EuroGP, EvoApplications, EvoCOP e EvoMUSART, Finding Solutions to Problems in Nature that Are Parallel (PPSN).

{Fim do CapÃtulo...