Computação evolucionária: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 00h55min de 21 de março de 2018

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, consequentemente, reproduzir-se.

Histórico

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 e solução de problemas multidimensionais.^[1]^[2]^[3]^[4]^[5]^[6]

Idéias básicas

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

Á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 Formações de Cristais, Colônia de Formigas e 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.

Geração Evolucionaria dos Computadores.

Geração zero (século XVII)

Elementos puramente mecânicos e “dedicados”. Dentre as principais máquinas dessa geração, citamos:

Calculadora de Pascal: O filósofo, físico e matemático francês Blaise

Pascal criou uma máquina (a Pascaline) para ajudá-lo nos negócios do pai. A pascaline foi a primeira máquina de calcular mecânica, com base em rodas e engrenagens para realizar somas e subtrações.

Calculadora de Leibnitz o filósofo e matemático alemão von Leibnitz introduziu o conceito de realizar multiplicações e divisões através de adições e subtrações sucessivas. Sua máquina era capaz de realizar as 4 operações básicas, mas era muito suscetível a erros.

Placa Perfuradora: Joseph Marie Jacquard introduziu o conceito de armazenamento de informações em placas perfuradas, para controlar uma máquina de tecelagem. Causou bastante desemprego na época Arithmometer: a primeira calculadora realmente comercializada com sucesso. Ela fazia multiplicações com o mesmo princípio da calculadora de Leibnitz e com a assistência do usuário efetuava as divisões.

Máquina Diferencial de Babbage: O matemático Babbage construiu um modelo para calcular tabelas de funções (logaritmos, funções trigonométricas, etc.) sem a intervenção de um operador humano, que chamou de Máquina das diferenças; Sua única operação era a adição, mas realizava um largo número de funções úteis pela técnica de diferenças finitas.

continua...

http://www.dca.ufrn.br/~lmarcos/courses/DCA800/pdf/Apresentacao_historico.pdf

Ver também

Ligações externas

↑ Fraser AS (1958). «Monte Carlo analyses of genetic models». Nature. 181 (4603): 208–9. Bibcode:1958Natur.181..208F. PMID 13504138. doi:10.1038/181208a0
↑ Rechenberg, Ingo (1973). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis) (em German). [S.l.]: Fromman-Holzboog
↑ Holland, John H. (1975). Adaptation in Natural and Artificial Systems. [S.l.]: University of Michigan Press. ISBN 0-262-58111-6
↑ 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
↑ G. C. Onwubolu and B V Babu, «New Optimization Techniques in Engineering». Consultado em 17 September 2016 Verifique data em: |acessodata= (ajuda)
↑ 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

[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 September 2016 Verifique data em: |acessodata= (ajuda)

[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

[1]

[2]

[3]

[4]

[5]

[6]

@@ Linha 1: / Linha 1: @@
 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 [[Charles Darwin|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, consequentemente, reproduzir-se.
-==História==
+== Histórico ==
+A CE surgiu nos anos 1950 através da biologia e da genética.
-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.
+Nos anos 60, desenvolveu-se na [[programação evolucionária]] (Fogel), [[algoritmos genéticos]] (Holland),
-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]].
+e [[estratégias de evolução]] (Rachenberg e Schwefel).
-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.
+Holland chegou a propor um quarto operador, a inversão, com pouca adoção.
-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.
+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 [[POO|programas]] e solução de problemas multidimensionais.<ref>{{cite journal |author=Fraser AS |title=Monte Carlo analyses of genetic models |journal=Nature |volume=181 |issue=4603 |pages=208–9 |year=1958 |pmid=13504138 |doi=10.1038/181208a0 |ref=harv|bibcode=1958Natur.181..208F }}</ref><ref>{{cite book |last=Rechenberg |first=Ingo |year=1973 |title=Evolutionsstrategie&nbsp;– Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis) |publisher=Fromman-Holzboog|language = German}}</ref><ref>{{cite book |last=Holland |first=John H. |year=1975 |title=Adaptation in Natural and Artificial Systems|publisher=[[University of Michigan Press]]|isbn = 0-262-58111-6}}</ref><ref>{{cite book |last=Koza|first=John R. |year=1992 |title=Genetic Programming: On the Programming of Computers by Means of Natural Selection|publisher=[[MIT Press]] |isbn=0-262-11170-5}}</ref><ref>G. C. Onwubolu and  B V Babu, {{cite web|url=https://www.springer.com/in/book/9783540201670|title=New Optimization Techniques in Engineering|publisher=|accessdate=17 September 2016}}</ref><ref>{{cite journal |author=Jamshidi M |title=Tools for intelligent control: fuzzy controllers, neural networks and genetic algorithms |journal=[[Philosophical Transactions of the Royal Society A]] |volume=361 |issue=1809 |pages=1781–808 |year=2003 |pmid=12952685 |doi=10.1098/rsta.2003.1225 |ref=harv|bibcode=2003RSPTA.361.1781J }}</ref>
 ==Idéias básicas==