Por Rubelmar Neto*, professor da UEA com MBA em Data Science e Analytics. Doutorado em Ciências – Engenharia Metalúrgica.

A primeira vez que ouvi falar de computação evolutiva eu estava no início do curso de graduação em Engenharia, algo em torno de 2004. Quando tento lembrar onde foi, sinto minha memória um tanto quanto imprecisa, acredito que tenha lido Algoritmos Genéticos (AG) no título de alguma iniciação científica. Lembro de pensar ser algo relacionado à biologia (se tem “genético” no nome, parece óbvio ser da biologia, não?!). Na época, ainda não havia despertado meu amor pela programação. Como várias das melhores amizades que cultivo, meu relacionamento com a programação começara de forma conflituosa e duvidosa. Somente alguns anos depois, em 2006, após um acidente causado pelos excessos da juventude, que me deixaria andando de muletas por alguns meses, repensaria minha relação com a programação (motivado pelo absoluto tédio). Até esse momento, só de ouvir o nome “algoritmos”, sentia um frio na barriga e uma vontade desesperada de fugir para a Terra do Nunca (sim, eu gosto de Peter Pan, e vez ou outra, vou dar um jeito de deixar isso claro). Voltando ao que interessa, Algoritmos Genéticos, chamado pelo íntimos simplesmente de AG, o que seria? Lembro de me perguntar isso e lembro de responder que isso não era da minha conta. Neste ponto do relato, preciso informar que eu cursei Engenharia Mecânica na graduação e julgara que essas coisas de algoritmos eram para o povo de programação. Bem, o que posso dizer, se eu estou escrevendo um artigo sobre o tema, eu estava maravilhosamente equivocado! Afinal, eu era somente um jovem arrogante estudante de engenharia, daqueles insuportáveis que chegam em conclusões rápidas e erradas sobre temas diversos. Passados alguns anos, lá estava eu no Mestrado de Engenharia Mecânica, cursando uma disciplina chamada Otimização, vi novamente AG, sem maiores explicações, estava como um subcomando de uma função. Neste momento, caro leitor, preciso fazer um alerta, a palavra otimização chega quase a ser tão banalizada quanto a palavra amigo. Afinal, basta algumas horas no bar e dizemos que o mestre garçom é nosso grande amigo (se bem que já fiquei amigo de um garçom exatamente assim). Similar ao que acontece no bar, na engenharia e na matemática aplicada, já cansei de ver otimização em títulos de trabalhos que nem chegaram perto de otimizar algo. E por que diabos autores da exatas amam inserir otimização nos títulos? Fácil de entender, fica bonito! Resumindo muito, assumindo o risco de simplificar além do devido, otimização é uma área da matemática e da engenharia onde estamos interessados em obter o máximo ou o mínimo de algo. Por exemplo, digamos que você esteja com uma vontade incontrolável de se endividar, como você licitamente poderia cumprir o seu nobre objetivo? Simples! Vá para uma concessionária comprar um carro! Você chega lá e quer o melhor carro, certo? Só há um pequeno problema, o seu dinheiro é limitado! Então, você buscará comprar o melhor carro gastando o mínimo possível. Este é um belo e simples exemplo de otimização, você deseja maximizar a sua alegria e minimizar o seu custo. Sempre isso, maximizar ou minimizar (ou ambos). Onde AG entra nisso? AG é um dos métodos utilizados para solucionar problemas de otimização. E o que este método tem de especial? Bem, posso resumir em dois pontos principais. Primeiramente, AG é uma metáfora computacional inspirada na Teoria da Evolução do cientista aventureiro Charles Darwin, o que o torna muito legal (não!?).  John Henry Holland foi quem cunhou o termo “algoritmos genéticos” e apresentou a sua versão mais popular, em 1973¹. Mas, vale atentar que os primeiros algoritmos evolutivos, inspirados nos princípios Darwinianos, foram propostos nas décadas de 40 e 50².  O segundo ponto é que AG resolve problemas que os métodos clássicos simplesmente não conseguem resolver. Por exemplo, vamos imaginar o problema do Caixeiro Viajante, que consiste em visitar n cidades estabelecendo um trajeto que demore o mínimo de tempo quanto possível. Para o caso de 100 cidades, utilizando um computador com um processador top nos termos atuais, demoraríamos algo em torno de 2 milênios para chegar na melhor solução via força bruta, isto é, calculando todas as possibilidades.  Claro, utilizando um método como AG não precisaríamos de 2 mil voltas da Terra em torno do Sol para chegar em uma boa solução. Eu disse “boa solução” porque utilizando AG não temos garantia de otimalidade, ou seja, não temos garantia que a solução encontrada será de fato a melhor de todas, a desejada solução ótima. Mas, não desanime, garanto que será muito melhor utilizar AG do que chutar uma solução da sua linda cabeça. Também podemos usar AG para obter uma escala de cirurgias otimizadas em um hospital, evitando conflito de horários entre cirurgiões e minimizando, por exemplo, tempos elevados entre uma cirurgia e outra. Claro, a mesma lógica poderia ser utilizada para demais profissionais da área da saúde, otimizando escalas de plantões de enfermeiros, fisioterapeutas, farmacêuticos e etc. Você já ouviu falar do jogo Super Mario Bros da Nintendo? (Se você nunca nem ouviu falar, provavelmente estava morando dentro de uma caverna desde o nascimento!) Podemos usar AG em conjunto com Redes Neurais Artificiais para fazer o computador jogar Mario sozinho e cair no abismo muitas vezes! E? Após várias mortes, podemos ter um Mario mais sábio e sagaz conseguindo passar da fase sem cair no abismo uma única vez! Ou seja, conseguimos um Mario perseverante que aprende com os seus erros!

 A essa altura do campeonato, já entendemos que AG é o bonzão, mas, vamos seguir em frente, vamos tentar entender como ele faz o que faz e, consequentemente, entender mais desse rolê de computação evolutiva. Anteriormente, escrevi que AG é uma metáfora computacional, conheci esta expressão através de um autor brasileiro que gosto muito, o professor Leandro Nunes de Castro, autor do livro Computação Natural: Uma Jornada Ilustrada. O Prof. Castro usa esta expressão para explicar que tanto o AG como demais métodos da computação bioinspirada, tais como colônia de formigas, enxame de partículas, entre outros, não tem como finalidade reproduzir de forma fidedigna o fenômeno usado como inspiração. Estes métodos da computação bioinspirada são desenvolvidos a partir de alguns elementos principais do objeto de inspiração, não desejando modelar o fenômeno em si, sendo apenas metáforas computacionais (amo essa expressão, deu pra notar?). Para entender AG, sendo redundante, vamos começar do começo, isto é, do objeto de inspiração, a Teoria da Evolução, o que ela diz? Me desculpem amigos biólogos, vou simplificar bastante, ela diz que o animal mais forte é o que sobrevive. Na verdade, não diz isso! Se você lembrou isso é porque, provavelmente, você estava dando aquele cochilo gostoso durante a aula. A Teoria da Evolução diz que o animal mais adaptado é o que sobrevive, aquele que se ajustou melhor ao ambiente, e, portanto, este sobrevivente (sortudo ou não) será o que passará suas características aos seus descendentes. Só pensar em você dando de cara com uma onça no meio da floresta, no mano a mano quem você apostaria que sobrevive? Eu apostaria na onça todas as vezes, é um bicho sinistro que corre, nada e sobe em árvores muito melhor do que você! E por que nós somos mais numerosos que onças e leões? Simples! Muitos milhares de anos atrás, um dos nossos antepassados, um primata muito forte e corajoso, teve a brilhante ideia de descer das árvores e descer no braço com um leão! Bem, esse antepassado não passou os genes para nós porque ele não sobreviveu. E quem passou? Foi um amiguinho dele mais fraco e mais esperto que ao fugir do leão encontrou uma pedrinha no chão e, por puro acaso e desespero, resolveu jogar a pedra no leão e acertou. O leão deve ter pensado: “Que macaquinho chato! Vou caçar uma Zebra!”. E foi assim que a esperteza venceu a força  e os primatas mais inteligentes foram os que sobreviveram e passaram os genes adiante. Até que chegou em nós, primatas muitos fracos mas que sabem jogar xadrez! Chegamos no momento Eureka que tiveram alguns estudiosos como Holland, incorporar esse lance do indivíduo mais adaptado cruzar e passar os genes adiante. Em AG, no lugar do ambiente, ou um leão deixando a vida de um macaquinho mais difícil, existe o que chamamos de função de avaliação ou ajuste (Fitness), essa função que pode ser muitas coisas diferentes é o que irá determinar quão bom um indivíduo, cromossomo em AG, é. Após classificados a partir da função de avaliação, os melhores indivíduos serão selecionados e, tudo dando certo, irão gerar mais descendentes. Mas, importante ressaltar, os indivíduos ruins também irão gerar descendentes, só que menos. Afinal, quem nunca viu um pai chato e desagradável ter um filho muito gente boa! Claro, o filho pode ter puxado mais para a mãe, mas, pode ter herdado uma orelha bonita do pai, por exemplo. Esse é um conceito importante em AG, um indivíduo ruim pode ter algumas boas características, bons genes, que valem a pena passar adiante. E, por este motivo, cruzamos todo mundo com todo mundo (algo como o Carnaval do Rio de Janeiro). Para exemplificar e tornar mais didático o funcionamento dos Algoritmos Genéticos, vamos analisar a figura a seguir. Temos AG sendo utilizado para desenvolver um modelo preditivo. Modelo que prevê o que? Bem, vou deixar esse suspense no ar, mas vamos imaginar que poderia ser um modelo para prever se vai chover ou não, ou se um cliente vai ou não comprar um casa após a primeira visita ao imóvel, ou se uma pessoa vai infartar ou não antes do 40 anos com base nas suas características. Dizemos que nesse caso a nossa variável dependente, aquela que queremos prever, possui natureza categórica dicotômica (nome bonito, né?). Ou seja, apenas duas possibilidades: chove ou não chove, morre ou não morre e por aí vai. Neste exemplo, a função de avaliação, ou fitness function, é a acurácia do modelo, isto é, quantas vezes o modelo prevê corretamente se é uma coisa ou outra coisa, dividindo pelo número n de observações. O que significa dizer que quanto maior a acurácia, melhor será o indivíduo (cromossomo). E o que são as características ou genes do indivíduos? Os genes podem ser números reais, inteiros ou binários (0 ou 1). Neste caso, os genes são números reais compreendidos no intervalo entre -1 e 1 (são os coeficientes de um polinômio, não que seja importante entender isso agora). Como nós escolhemos o valor numérico do gene? Já adianto que vai ser difícil aceitar no seu coraçãozinho o que vou dizer, os genes são gerados aleatoriamente! Na verdade, são gerados pseudoaleatoriamente, já que a aleatoriedade plena ainda não foi possível de implementar computacionalmente. E devido à beleza do acaso, alguns indivíduos terão fitness melhores que outros. E por que isso? Bem, quem tem vários filhos, ou quem tem vários irmãos, sabe que cada filho ou irmão pode ser melhor que outro no desempenho de alguma atividade (fitness). E por quê? Você pode utilizar Deus aqui se quiser: PORQUE DEUS QUIS! (vou usar a sigla PDQ para representar isso!). Então, em AG, alguns indivíduos são melhores que outros, mesmo que os seus genes tenham sido gerados aleatoriamente, PDQ! Eu sei, é difícil aceitar isso, mas diria que isso é a “alma” dos AG, o poder da aleatoriedade! 

Voltemos para o gráfico, nesta aplicação, cada indivíduo da primeira geração possui 16 genes, números reais compreendidos entre -1 e 1, e os genes de um mesmo indivíduo, apesar de serem números diferentes, foram representados utilizando uma mesma cor. Por exemplo, todos os genes do Cronos foram representados utilizando vermelho, enquanto que para os genes de Reia foi utilizado o verde. E para que se dar esse trabalho? Após várias gerações, eu queria poder analisar aquele que se tornaria o melhor indivíduo, aquele com maior valor de fitness, e entender como ele foi formado e quem eram os seus ancestrais, ou seja, de quem ele teria herdado os genes. Eu queria entender se o melhor indivíduo seria descendente ou não do melhor indivíduo da primeira geração. Naquela ideia que conversamos antes, será que um pai chato pode gerar um filho gente boa?  Para sanar a minha curiosidade, o que eu fiz foi aplicar uma metáfora dentro da outra (algo meio Inseption, entendedores entenderão!). Como assim? Me inspirei nos testes de ancestralidade, aqueles que identificam de onde vieram os seus ancestrais. No meu caso, como eu já imaginava, todo mundo cruzou com todo mundo, meus antepassados vieram da Europa, África, América e Oriente Médio. Sou bem misturado! E, conforme vocês vão ver nessa rodada de AG, misturar é bom! Para tornar mais fácil e divertida a identificação dos indivíduos, utilizei nomes da Mitologia Grega. Aqui tem uma historinha interessante, Mitologia Grega foi a minha segunda opção. Na primeira vez, eu havia usado os nomes de anjos, primeiros homens e acabava na geração do Enzo e da Valentina. Porém, compartilhei a aplicação com uma amiga, a professora Renata Onety, e ela não ficou feliz com o resultado. Pois, na rodada de AG que compartilhei, Lúcifer e o Arcanjo Miguel acabavam cruzando, e a Renata, sendo cristã, achou que não passava uma mensagem legal. Então, até segunda ordem, continuarei utilizando a Mitologia Grega. A Geração 1 é composta pelos Titãs, a Geração 2 apresenta a primeira geração dos deuses do olimpo, a Geração 3 contém a segunda geração dos deuses do olimpo (praticamente, todos sendo filhos do danadinho Zeus). Por fim, a última geração, a Geração 4, é composta pelos semideuses. Nesta rodada de AG, podemos visualizar, por exemplo, que Zeus, indivíduo da Geração 2, foi formado a partir de Reia e Crio da Geração 1. E como Reia a Crio foram selecionados para formar Zeus? E como escolher quantos genes de cada um Zeus herdaria? A resposta das duas perguntas é a mesma: aleatoriedade! Tanto a seleção dos pais quanto o número de genes herdados de cada pai é feito de forma aleatória. Porém, nos utilizados de algumas estratégias computacionais para privilegiar na seleção pais com fitness maiores, conforme mencionei anteriormente. Também podemos notar outra coisa em Zeus, ele apresenta um gene cinza. Escolhi cinza para representar as mutações. Esse gene mutante não foi herdado de nenhum pai da geração anterior, é um novo gene, novamente um número aleatório entre -1 e 1. O curioso aqui é que esse percentual de genes mutantes, assim como no mundo natural, não pode ser elevado, tendo que ficar algo próximo de 5%. Por quê? PDQ! Mas a lógica aqui é que se o percentual de mutação for elevado, vamos perdendo as características (genes) que tornaram um indivíduo melhor que outro, vamos perdendo informação ao longo das gerações. É como se nascesse um gato sem o rabo e não conseguisse mais se equilibrar em cima do muro! Ah! Ia esquecendo! E como que escolhemos qual gene sofrerá mutação? A essa altura vocês já devem imaginar. Sim, é feito também de forma aleatória! Algo que também preciso chamar a atenção é que nem sempre os filhos são frutos de cruzamento, eles podem ser clones de um dos pais selecionados, o que podemos visualizar com Hefesto da Geração 3 que, com exceção de um gene mutante, é um clone de Clímene da Geração 2. E como que escolho com vai haver ou não cruzamento na formação de um filho? Bem, você já sabe a resposta! Em AG, após a formação dos primeiros indivíduos de forma aleatória, ocorrerão sempre os mesmos passos: seleção, cruzamento, mutação e elitismo (este último sendo opcional). Elitismo nada mais é do que selecionar o pior indivíduo da geração atual e substituí-lo pelo melhor indivíduo da geração atual. Sendo implementado o elitismo, nunca a melhor solução será perdida, não havendo degeneração da solução. No exemplo mostrado aqui, após 4 gerações, temos nesta rodada que a Diana (Mulher Maravilha) foi o melhor indivíduo da geração dos semideuses. Sendo a Diana um clone da Atena, tendo apenas um gene mutante a mais, sendo esta mutação responsável pela evolução. Por vezes, podemos ter 100 ou 1000 gerações sem nenhuma evolução, até que um novo cruzamento ou uma nova mutação resulte de um indivíduo mais apto. Usei o termo rodada por algumas vezes, pois a cada nova rodada do algoritmo, devido a toda essa aleatoriedade embutida, podemos ter Kratos ou Áquiles como o melhor indivíduo, ou até mesmo Cronos (Geração 1) como melhor indivíduo final (sendo implementado Elitismo).

Claro, existem outros métodos computação evolutiva tais como Evolução Diferencial ou Sistemas Imunológicos Artificiais, mas a lógica central de evoluir ao longo de gerações permanece, somente as regras ou operadores de cruzamentos e/ou mutações são modificados. No caso particular de AG, me peguei muitas vezes pensando: “Mas como diabos isso funciona?!”. Depois de muito pensar, aceitei que funciona justamente porque funciona no mundo natural, porque a Teoria da Evolução funciona. E por que esta última funciona? Novamente, PDQ!

¹HOLLAND, John H. Genetic algorithms and the optimal allocation of trials. SIAM journal on computing, v. 2, n. 2, p. 88-105, 1973.

²EIBEN, Agoston E.; SMITH, James E. Introduction to evolutionary computing. Springer-Verlag Berlin Heidelberg, 2015.

Rubelmar Neto é professor da Escola Superior de Tecnologia da Universidade do Estado do Amazonas (EST/UEA). Possui MBA em Data Science e Analytics pela Universidade de São Paulo (USP) e Doutorado em Ciências na área de Engenharia Metalúrgica, também pela (USP).