Giga Mundo - Computação

Esta é a terceira e última parte de nossa introdução aos algoritmos genéticos. Desta vez, vamos discutir a respeito dos parâmetros que mais influenciam o sucesso de nosso algoritmo genético, como e por que efetuar o ajuste de fitness, o que é o elitismo, bem como apresentar algumas aplicações de algoritmos genéticos.

Caso você não tenha lido um dos outros dois artigos, os mesmos são:

Uma Introdução aos Algoritmos Genéticos - Parte 1

Uma Introdução aos Algoritmos Genéticos - Parte 2

Parâmetros Genéticos

Para o bom sucesso de um algoritmo genético, quatro parâmetros devem ser bem vigiados e testados:

• Tamanho da população: o tamanho da população afeta e muito o desempenho do algoritmo, pois, quanto maior é a população, maior é a a cobertura do espaço de busca que a mesma promove, entretanto, mais processamento, memória e outros recursos serão consumidos;
• Taxa de crossover (cruzamento): quanto maior for a taxa de cruzamento, mais rapidamente novas estruturas serão introduzidas, entretanto quando esta taxa é muito alta, pode provocar a perda de estruturas de alta aptidão, dificultando assim chegar na resposta de forma clara, rápida e precisa. Já quando a taxa de crossover for muito baixa, transforma-se em outro problema onde o algoritmo converge para a solução mais lentamente;
• Taxa de mutação: uma baixa taxa (porém, não nula!) de mutação pode auxiliar a não permitir que as informações em um cromossomo fiquem estagnadas, o que poderia dificultar para chegar na solução. Já taxas altas de mutação podem levar a índices muito altos de aleatoriedade nas informações;
• Intervalo de Geração: indica a porcentagem da população que pode ser substituída na próxima geração. Com valores baixos, ou seja, uma pequena parte da população sendo alterada a cada geração, pode-se demorar muito até chegar na solução. Já no caso de valores muito altos pode-se ocorrer a perda de estruturas de aptidão.

Ajuste de Fitness

O ajuste de fitness permite ajustar a pontuação calculada para cada cromossomo a fim de “zerar” a pontuação daqueles que são considerados os piores cromossomos, evitando, assim, que o mesmo seja selecionado pela “roda da roleta”.
Se tivermos uma pontuação em que grandess valores representam cromossomos mais apropriados para a solução, podemos fazer o ajuste de fitness simplesmente subtraindo o valor do pior cromossomo de todos (inclusive dele próprio, o que reduzirá sua contagem a zero).

Elitismo

Elitismo trata-se da repetição dos cromossomos com melhores resultados na próxima geração a fim de evitar que todos os bons cromossomos sejam alterados pelo crossover e pela mutação, desta forma, o uso de elitismo permite que o algoritmo convirja mais rapidamente para uma solução.
Da mesma forma que com os parâmetros genéticos, deve-se tomar cuidado com o uso de elitismo, pois quanto maior for o número de cromossomos a serem mantidos, maior a probabilidade de convergirmos para um máximo local.

Aplicações de algoritmos genéticos

Os algoritmos genéticos podem ser usados em praticamente todas as ocasiões onde pudermos codificar nossos parâmetros e empregar o método gerar-e-testar para encontrar uma possível solução ou mesmo melhoria em relação aos parâmetros trabalhados anteriormente.
Para melhor ilustrar isso, podemos imaginar um jogo (já que esta é primariamente a minha área ) de estratégia em tempo real onde os exércitos são comandados por comandantes (agentes inteligentes), porém cada unidade conserva suas habilidades para tomada de decisão. Desta forma, poderíamos combinar vários parâmetros a fim de determinar o cromossomo de cada unidade com características como força, coragem, lealdade, esperteza, raio de ajuda, etc.
Seguindo algumas restrições sobre algumas características para a criação de uma unidade e gerando os dados aleatoriamente, poderemos então criar exércitos onde cada unidade possui seu próprio comportamento, sua própria personalidade.
Eis que as próprias partidas seriam nosso treinamento e, a cada nova unidade criada, levar em consideração a pontuação obtida pelos cromossomos já criados, assim, aos poucos, teríamos unidades que vão se tornando mais inteligentes durante as batalhas.
Obviamente será necessário também algum treinamento em paralelo às partidas a fim de agilizar o processo de aprendizado, mas com certeza o resultado final será muito interessante!
Não somente em jogos de estratégia, mas em todos os jogos onde há tomada de decisões este tipo de algoritmo pode ser empregado, desde o cálculo de um pathfinding até a tomada de decisões sobre atacar, acelerar, mover uma peça no tabuleiro, etc.

Podemos empregar também em aplicações onde podemos testar, “treinar” o nosso sistema inicialmente. Criaríamos um número qualquer de cromossomos dispostos a tentar resolver o problema dado e após algumas gerações selecionaríamos aqueles com melhor desempenho.

Esperamos que esta série de artigos o tenha ajudado a compreender como funcionam e como implementar algoritmos genéticos.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]