Princípios darwinianos inspiram algoritmos

Mecanismos que atuam na evolução por seleção natural dos seres vivos podem ajudar a descobrir soluções para problemas de diversos tipos, incluindo questões sobre a estrutura de redes de telecomunicação e, até, um problema eminentemente econômico: como otimizar o resultado de um leilão de concessão pública. É o que mostra a tese de doutorado “Algoritmos evolutivos para alguns problemas em telecomunicações”, defendida por Carlos Eduardo de Andrade no Instituto de Computação (IC) da Unicamp, e orientada pelo professor Flávio Keidi Miyazawa, do mesmo instituto, e Mauricio G. C. Resende, do Departamento de Planejamento e Otimização Matemática, da Amazon.com, nos Estados Unidos.

“Um algoritmo evolutivo é um método de resolução de problemas inspirado nos princípios darwinianos de evolução”, disse Andrade. “Em geral, um algoritmo evolutivo utiliza, como metáforas, os mecanismos biológicos de reprodução, mutação, recombinação e seleção natural através da aptidão. Tais mecanismos são simulados pelo algoritmo evolutivo, com o objetivo de resolver um problema específico. Existem diversas variações desses algoritmos, e nem sempre todos mecanismos evolutivos são usados. Algoritmos genéticos, em geral, fazem o uso completo das metáforas”.

A tese explica como possíveis soluções para um problema podem ser codificadas em “cromossomos” virtuais, cada um deles dotado de uma função de aptidão, uma medida de sua qualidade em relação ao problema tratado – por exemplo, qual a forma mais eficiente de conectar uma série de pontos numa rede. Assim como os cromossomos dos seres vivos, os virtuais contêm “alelos”, isto é, diferentes versões de um mesmo gene – ou, no caso, de uma mesma parte da solução.

“O passo evolutivo consiste em construir uma nova população, combinando os indivíduos da população atual, selecionando alelos deles para criar prole”, escreve Andrade em seu trabalho. “Um passo adicional, chamado ‘mutação’, é aplicado com baixa probabilidade, quando um alelo é escolhido e modificado ao acaso. A grande vantagem do algoritmo genético é combinar duas ou mais diferentes soluções”. Mais adiante, acrescenta: “Usando o conceito de operadores genéticos e hereditariedade, algoritmos genéticos são capazes de combinar partes de boas soluções mantê-las ‘vivas’”. [Leia a entrevista completa no Jornal da Unicamp]