Computação evolucionária – Wikipédia, a enciclopédia livre

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 programaçã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íduos 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 marcada 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.

Referências

  1. Fraser AS (1958). «Monte Carlo analyses of genetic models». Nature. 181 (4603): 208–9. Bibcode:1958Natur.181..208F. PMID 13504138. doi:10.1038/181208a0 
  2. Rechenberg, Ingo (1973). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis) (em German). [S.l.]: Fromman-Holzboog 
  3. Holland, John H. (1975). Adaptation in Natural and Artificial Systems. [S.l.]: University of Michigan Press. ISBN 0-262-58111-6 
  4. Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. [S.l.]: MIT Press. ISBN 0-262-11170-5 
  5. G. C. Onwubolu and B V Babu, «New Optimization Techniques in Engineering». Consultado em 17 de setembro de 2016 
  6. Jamshidi M (2003). «Tools for intelligent control: fuzzy controllers, neural networks and genetic algorithms». Philosophical Transactions of the Royal Society A. 361 (1809): 1781–808. Bibcode:2003RSPTA.361.1781J. PMID 12952685. doi:10.1098/rsta.2003.1225 

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

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