O cientista da computação, John Holland, em 1975, fez a proposta de criação dos algoritmos genéticos com base na Teoria da Evolução de Charles Darwin. A primeira utilização prática foi feita por David Goldberg, através da resolução de um problema complexo, envolvendo o controle de transmissão de gasoduto (HAUPT; HAUPT, 2004 apud NUNES; GUIMARÃES; CARVALHO, 2013).
Como podemos ver os algoritmos genéticos são utilizados para resolver problemas complexos de otimização e com muitas restrições, tais como: o clássico problema do caixeiro viajante, o planejamento de trajetória de robô, a otimização de Redes Neurais Artificiais, o escalonamento de horários, a escala de tarefas, o planejamento de expansão no setor elétrico (LEUNG;LIANG, 2003 apud NUNES; GUIMARÃES; CARVALHO, 2013) .
Os algoritmos genéticos, resultam em procedimentos que vão desde a inicialização de um valores das variáveis aleatoriamente e codificadas em cromossomos digitais que são submetidos a diversas manipulações genéticas (seleção, cruzamentos e mutação) por gerações até que evoluam para representar a melhor solução para o problema (SARKAR, 2010).
Podemos visualizar, na Tabela 01, a analogia entre algoritmos genéticos e o sistema de seleção natural (LINDER, 2008 apud NUNES; GUIMARÃES; CARVALHO, 2013).
Tabela 01 – Paralelo entre sistema de seleção natural e algoritmos genéticos
| Seleção Natural | Algoritmos Genéticos |
|---|---|
| cromossomo | indivíduo, string, cromossomo, árvore |
| gene | característica |
| alelo | valor |
| locus | posição |
| genótipo | estrutura |
| fenótipo | conjunto de parâmetros |
O mais simples dos algoritmos genéticos segue os passos: inicialização da população, entrada de dados nos cromossomos, seleção dos cromossomos saudáveis, recombinação entre os cromossomos selecionados (crossover), mutação seletiva (operadores), e repetir os passos seleção, recombinação e mutação até chegar no resultado ótimo (SARKAR, 2010). Vejamos um exemplo na Figura 01.
A inicialização da população é escolha da estrutura do cromossomo e seus valores. Podemos encontrar estruturas de cromossomos representados por vetores, matrizes, matrizes assimétricas, cubos, entre outros. Os valores dos genes podem ser binários, números inteiros e números decimais, sendo mais comum a representação binária (LINDER, 2008).
Figura 01 – Um exemplo gráfico do funcionamento dos algoritmos genéticos (TELES, 2011 apud NUNES; GUIMARÃES; CARVALHO, 2013)
Com base na Figura 01, vamos explicar como funciona cada procedimento dos algoritmos genéticos:
(a) A escolha da população inicial
A escolha da população inicial é algo que pode ser simples ou complexo depende do problema analisado. Este processo de escolha é totalmente aleatório e cada cromossomo representa uma possível solução (LINDER, 2008).
Alguns cientistas, acreditam que o ideal da primeira população é ter uma alta diversidade de material genético e esteja distribuído por todo o espaço de soluções (DEEPA, 2008). Entretanto, não existe garantias que ocorra uma distribuição por todo o espaço de soluções, pois o tamanho da população é finito (LINDER, 2008).
(b) A função de fitness
A função fitness ou de avaliação é projetada para cada problema e recebe como dados de entrada um cromossomo, tendo como saída um número ou uma lista de números que representa uma solução ótima que auxiliará na resolução do problema (FILITTO, 2008 apud NUNES; GUIMARÃES; CARVALHO, 2013).
(c) Seleção
A Seleção consiste no processo de escolha da população (pais) para realizar o crossover, sendo necessário dois cromossomos. Este processo simula o mecanismo de seleção natural de Charles Darwin, sendo os pais mais aptos (melhores selecionados) gerarão filhos melhores (resultados melhores) (LINDER, 2008).
Para auxiliar na seleção são utilizados métodos estatísticos para classificação, que são (LINDER, 2008):
- Seleção Proporcional: A seleção é realizada com base no valor relativo na avaliação dos cromossomos em relação aos demais;
- Seleção Baseada em Ordem: Consiste na classificação dos indivíduos com base na sua avaliação e depois é selecionado o de melhor rank na ordem decrescente.
- Método da Roleta Viciada: Consiste na busca linear através de uma “roleta virtual” na qual cada indivíduo recebe um pedaço proporcional à sua avaliação, sendo que o total não pode ultrapassar 100%.
- Seleção por torneio: Neste método, pais potenciais são selecionados e um torneio decide qual dos indivíduos será o vencedor.
(d) Crossover
Uma das principais características dos algoritmos genéticos é o crossover. Este operador, consiste no cruzamento de dois cromossomos pais que produz um cromossomo filho (DEEPA, 2008). Podemos encontrar diversos métodos para o operador crossover (LINDER, 2008):
- De um ponto: Sorteia-se um ponto de corte, onde o primeiro filho é composto pela concatenação da parte do primeiro pai à esquerda do ponto de corte com a parte do segundo pai à direita do ponto de corte e o segundo filho pelas partes restantes. Na Figura 01, temos um exemplo de utilização do crossover de um ponto.
- De dois pontos: Sorteia-se dois pontos de corte, o primeiro filho será formado pela parte do primeiro pai fora dos pontos de corte e, pela parte do segundo pai entre os pontos de corte e o segundo filho será formado pelas partes restantes.
- Uniforme (Partially Matched Crossover): Para cada gene é sorteado um número 0 ou 1. Se o valor sorteado for igual a 1, o primeiro filho recebe o gene da posição corrente do primeiro pai e o segundo filho o gene corrente do segundo pai. Por outro lado, se o valor sorteado for zero, as atribuições são invertidas.
- Baseado em Ordem (Order Crossover): Este método é uma forma melhorada do crossover uniforme. A partir do último corte em cada cromossomo, o método faz uma busca no cromossomo do outro indivíduo pai pelos genes que não estão na subcadeia herdada, preenchendo assim o cromossomo.
- Cíclico (Cycle Crossover): Sorteia-se uma posição no indivíduo chamado de Pai 1 para passar a sua tarefa para a mesma posição do Filho 2. Para garantir que não haja repetição de tarefas nesses novos indivíduos, identifica-se no Pai 2, a tarefa que foi selecionada no Pai 1, e transfere-se essa tarefa para o Filho 1, na mesma posição em que foi encontrada, formando assim um ciclo.
(e) Mutação
A mutação é a operação realizada após a operação crossover. Podemos encontrar diversas formas de operadores de mutação, tais como (LINDER, 2008):
- Radom Resetting: é escolhido um novo valor, aleatoriamente. a partir do conjunto de valores inteiros para cada posição.
- Creep Mutation: Esta forma acrescenta ou subtrai ao valor do gene um pequeno número inteiro aleatório.
- Mutação Uniforme: Os novos valores decimais são aleatoriamente escolhidos de forma uniforme.
- Mutação não-uniforme: Um valor é adicionado ao gene, escolhido aleatoriamente a partir de uma distribuição Gaussiana de média zeros e desvio padrão.
Pudemos perceber que os Algoritmos Genéticos são de fácil entendimento por fazer uma analogia fiel a seleção natural de Charles Darwin. E sua aplicação pode ser utilizada para resolver diversos problemas complexos.
Esperamos ter contribuído para estimular o interesse na área da Inteligência Computacional.
Referências
DEEPA, S. N. S. S. N. Introduction to Genetic Algorithms. Springer, 2008.
FILITTO, D. Algoritmos genéticos: Uma visão explanatória. Saber Acadêmico – Revista Multidiciplinar da Unesp, 2008.
HAUPT, R.; HAUPT, S. E. Practical Genetic Algorithms. Wiley, 2th edition, 2004.
LEUNG, K.; LIANG, Y. Adaptive elitist-population based genetic algorithm for multimodal function optimization. Genetic and Evolutionary Computation Conference, 2003.
LINDER, R. Algoritmos Genéticos. BRASPORT, 2008.
NUNES, R. D. S.; GUIMARÃES, N. C.; CARVALHO, C. L. d.. Planejamento de grade de horário em uma universidade brasileira usando algoritmos genéticos. In Proceedings of the X Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), page 10, Fortaleza-CE, Brazil, 2013.
SARKAR, D. E. E. A. Genetic Algorithm based online power network reconfiguration for voltage stability improvement. International Journal of Engineering Science and Technology, 2:4167–4174, 09 2010.
TELES, R. M. Um estudo de técnicas da inteligência artificial aplicadas na distribuição de recursos em áreas geográficas. Master’s thesis, UNIVERSIDADE FEDERAL DE GOIÁS, INSTITUTO DE INFORMÁTICA, abr 2011.
