Computação evolucionária

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A computação evolucionária (CE, computação evolutiva, ou mesmo biologia evolucionária) é a otimização global inspirada na evolução biológica. Constitui uma família de algoritmos e é um ramo da inteligência computacional e da computação natural. Sistemas de CE resolvem problemas via populações, erro e acerto, meta-heurística, ou otimização estocástica. Um conjunto inicial de soluções candidatas é gerado e atualizado iterativamente: remoção das soluções menos desejadas, inserção de ruído. No jargão da área, uma população de soluções é sujeita à seleção natural ou seleção artificial e mutação, e portanto evolui e adapta, i.e. aumenta o fitness (função quantiza quão adaptada/desejada é a solução). A CE é popular na IC por resultar soluções otimizadas em um espectro largo de contextos, há muitas variantes e extensões para problemas e estruturas de dados específicas.


Histórico[editar | editar código-fonte]

A CE surgiu nos anos 1950 através da biologia e da genética. Nos anos 60, desenvolveu-se na programação evolucionária (Fogel), algoritmos genéticos (Holland), e estratégias de evolução (Rachenberg e Schwefel). Holland chegou a propor um quarto operador, a inversão, com pouca adoção. Nos anos 1990 elas foram unificadas como computação evolucionária e apareceu a progração genética. Nas últimas décadas, com o aumento expressivo do poder de computação, a CE pode ser mais amplamente aplicada, inclusive para a evolução de programas, solução de problemas multidimensionais, e novas concepções de meta-heurística.[1][2][3][4][5][6]

Algoritmo evolucionário (AE)[editar | editar código-fonte]

Um algoritmo evolucionários (AE) é um sistema de CEs caracterizados por 'seleção' e ('recombinação' e 'mutação') de populações. AEs são tipicamente estocásticos. Um AE pode ser implementado com as seguintes etapas:

  • Gere uma população inicial (e.g. aleatoriamente)
  • Repita os passos até o término:
    • Selecione os indivícuos mais aptos para reprodução (e.g. maior fitness)
    • Gere novos indivíduos a partir dos selecionados (e.g. via crossover e mutação)

Tipos específicos de AEs incluem: programação genética, programação evolucionária, programação de expressão gênica, evolução diferencial, neuroevolução, sistema de classificação aprendiz.

Algoritmo genético[editar | editar código-fonte]

Um algoritmo genético (AG) é um AE no qual a geração de novos indivíduos é especialmente parcada pela mutação e crossover, à semelhança do que ocorre com os genes na evolução natural. Um AG muitas vezes é também marcado pela evolução de soluções representadas como vetores multidimensionais e informações sobre o problema.

Algoritmos de CE que não são AEs[editar | editar código-fonte]

A CE abrange inteligência desenvolvidas pela evolução, não apenas o AE, em geral modelada como um algoritmo de otimização meta-heurística. Dentre estes algoritmos de CE constam: otimização por colônia de formigas (ACO), algoritmos imuno-inspirados, otimização por enxame de partícula e diversos outros modelos de inteligência de enxame.

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]