Algoritmos Genéticos

Matemática + Biologia = Algoritmos Genéticos

Sistemas Inteligentes

A Inteligência Computacional é uma área da ciência que busca, através de técnicas inspiradas na Natureza, Procura desenvolver sistemas inteligentes que imitam aspectos do comportamento humano, tais como: aprendizado, percepção, raciocínio, evolução e adaptação.

Problemas de Otimização Combinatória

A Otimização Combinatória é um ramo da ciência da computação que estuda problemas de otimização em conjuntos.

Problemas de otimização, na sua forma geral, têm como objetivo a maximização ou minimização (determinação de máximo ou mínimo) de uma função definida sobre um certo domínio. Os problemas de otimização combinatória apresentam um conjunto finito de candidatos a solução; além disso, em geral pode – se listar os seus elementos e também testar se um dado elemento pertence a esse conjunto. No entanto, a idéia ingênua de testar todos os elementos deste domínio na busca da melhor solução mostra-se inviável na prática, mesmo para instâncias de tamanho moderado.

Todos os problemas de otimização combinatória surgem naturalmente em aplicações práticas, tais como o projeto de redes de telecomunicação, o empacotamento de objetos em containeres, o roteamento de veículos, etc. Outras áreas de aplicação incluem a estatística (análise de dados), a economia (matrizes de entrada/saída), a física (estados de energia mínima), a biologia molecular (alinhamento de DNA e proteínas, inferência de padrões), etc.

Como exemplos clássicos de problemas de otimização combinatória podemos citar o problema do caixeiro viajante, o problema da mochila e o problema da floresta de Steiner.

Existem muitas classificações possíveis para o problema de otimização, e algumas delas apresentarão métodos exatos e eficientes de resolução. Outras levarão à necessidade de métodos não-exatos (heurística), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade intratável.

A utilização dos Algoritmos genéticos tem – se mostrado uma técnica poderosa na busca de soluções para estes problemas. Este artigo abordará essa técnica de busca, que foi inspirada na teoria da Evolução.

Um Breve Histórico

Até meados do século 19, os naturalistas acreditavam que cada espécie havia sido criada separadamente por um ser supremo (divindade criadora) ou através de geração espontânea. Os trabalhos do naturalista Carolus Linnaeus sobre a classificação biológica de organismos despertaram o interesse pelas similaridades entre certas espécies, intuitivamente acreditou – se na existência de uma relação entre elas.

Outros trabalhos influenciaram os naturalistas em direção à teoria da seleção natural, tais como os de Jean Baptiste Lamark, que sugeriu uma teoria evolucionária no "uso e desuso" de órgãos; e de Thomas Robert Malthus, que propôs que doenças e escassez de alimentos eram efeitos, provocados pelo meio ambiente, que limitavam o crescimento populacional.

Depois de mais de 20 anos de observações e experimentos, Charles Darwin apresentou em 1858 sua teoria de evolução através de seleção natural, paralelamente com outro naturalista inglês Alfred Russel Wallace. No ano seguinte, Darwin publica o seu On the Origin of Species by Means of Natural Selection com a sua teoria completa, sustentada por muitas evidências colhidas durante suas viagens a bordo do Beagle (Cão de origem inglesa do tipo sabujo, de porte médio, onde até hoje é usado em caça à lebre e à raposa).

“Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será sua chance de sobreviver e gerar descendentes.”

(DARWIN, 1859)

Este trabalho influenciou de forma avassaladora o futuro não apenas da Biologia, Botânica e Zoologia, mas contribuiu com grande influência sobre o pensamento religioso, filosófico, político e econômico da época. A teoria da evolução e a computação nasceram praticamente na mesma época: O matemático Charles Babbage, um dos fundadores da computação moderna e amigo pessoal de Darwin desenvolveu sua máquina analítica em 1833. Ambos provavelmente estariam surpresos e orgulhosos com a ligação entre estas duas áreas.

Por volta de 1900, o trabalho de Gregor Mendel, desenvolvido em 1865, sobre os princípios básicos de herança genética em conjunto com as idéias de Darwin e Wallace sobre a seleção natural, deram origem ao princípio básico da Genética Populacional.

“A variabilidade entre indivíduos em uma população de organismos que se reproduzem é produzida pela mutação e pela recombinação genética”

Este princípio foi desenvolvido durante os anos 30 e 40, por biólogos e matemáticos de importantes centros de pesquisa. Nos anos 50 e 60, muitos biólogos começaram a desenvolver simulações computacionais de sistemas genéticos. Entretanto, foi John Holland quem iniciou os primeiros desenvolvimentos concretos sobre o tema, Holland publicou em 1975 seu livro Adaptation in Natural and Artificial Systems, hoje considerado a Bíblia de Algoritmos Genéticos.

“Algoritmos genéticos são modelos matemáticos computacionais que imitam os mecanismos da Evolução natural para resolver problemas de otimização”

(JOHN HOLLAND, 1970)

Pode – se dizer que a matemática e biologia se uniram para viver felizes para sempre, desde então, os algoritmos genéticos vêm sendo largamente aplicados com sucesso em diversos problemas de otimização e aprendizado de máquina.

Os componentes Básicos dos Algoritmos Genéticos

• Um problema para ser resolvido pelo algoritmo;

• Um método para codificar soluções do problema através de cromossomos;

• Uma função de avaliação que mede quão bem, cada solução é capaz de resolver o problema;

• Um método para criar a população inicial de cromossomos;

• Um conjunto de parâmetros para o algoritmo genético;

• Um conjunto de operadores que atuam no processo de reprodução;

Cromossomos