galdenoro-tcc----bruno-grinholli-escher

Prévia do material em texto

Mutação Diferencial Condicional como 
proposta de otimização de Algoritmos 
Genéticos 
 
 
 
 
 
 
 
 
 
 
 
 
 
Autor : Bruno Grinholli Escher 
Orientador : Prof. Dr. Galdenoro Botura Jr. 
 
 
 
 
 
Sorocaba , 2008 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
2 
Sumário 
 
1 Resumo......................................................................................................................................6 
2 Abstract.....................................................................................................................................7 
3 Introdução ................................................................................................................................8 
4 Os Algoritmos Genéticos.........................................................................................................9 
 4.1. Idéia Básica – O Darwinismo.....................................................................9 
 Conceito de adaptação.....................................................................9 
 Exemplo clássico de adaptação.......................................................9 
 Darwin e o mecanismo evolutivo.....................................................10 
A seleção natural................................................................................11 
Neodarwinismo: ampliação da teoria de Darwin..........................11 
Mendel e a Genética.........................................................................11 
Copiando a Natureza........................................................................13 
Vantagens do AG...............................................................................15 
Algumas aplicações atuais.............................................................. 17 
4.2. TOPOLOGIA DOS AG.............................................................................. 20 
Seqüência clássica............................................................................20 
Intervalo e Codificação....................................................................21 
Reais ou Binários ?..............................................................................23 
Gerando a população inicial ..........................................................24 
O tamanho da população...............................................................25 
Avaliação dos indivíduos (fitness)....................................................27 
Inversamente ou diretamente?........................................................29 
 Classificação e separação dos melhores.......................................30 
Aplicação de operadores genéticos clássicos..............................34 
5. A MUTAÇÃO DIFERENCIAL CONDICIONAL 
5.1 Mutação Tradicional e Mutação diferencial......................................39 
5.2. A mutação diferencial condicionada..................................................41 
6. DESEMPENHO DE ALGORITMOS GENÉTICOS 
6.1. Como avaliar um AG ?...........................................................................43 
Velocidade de Evolução..................................................................44 
Linhagem.............................................................................................46 
Delta-Fit................................................................................................46 
IPQ........................................................................................................47 
IPQL.......................................................................................................48 
Variedade Orbital...............................................................................49 
Melhoria Efetiva...................................................................................52 
7. FERRAMENTAS EVOLUTIVAS 
7.1. Preferência ao oposto.............................................................................52 
7.2. Repressão a cópia...................................................................................54 
7.3. Inversão de Iguais....................................................................................55 
8. CONTROLE CLÁSSICO 
8.1. O que é controle......................................................................................57 
8.2. O que é controle em malha fechada..................................................57 
8.3. Controladores...........................................................................................57 
8.4. A planta.....................................................................................................61 
8.5. Características de um sistema em malha fechada............................62 
8.6. Medindo o desempenho do controlador ..........................................65 
8.7. Esforço de controle.................................................................................66 
8.8. Modelando a planta – o motor CC......................................................68 
 
 
 
 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
3 
9. O PID 
9.1. Características..........................................................................................70 
9.2. Formas de implementação do PID........................................................74 
9.3. Processo de sintonia de um PID.............................................................77 
Escolher critérios de desempenho...................................................77 
Identificação de processo................................................................77 
Aplicação de um método numérico..............................................78 
Método de Cohen-Coon...........................................................78 
Métodos de Ziegler-Nichols........................................................79 
Crítica aos métodos tabelados.................................................80 
10. APLICANDO OS AG NO CONTROLE CLÁSSICO 
10.1. Como representar um controlador em genes?.................................80 
10.2. Como avaliar um sistema em malha fechada..................................81 
10.3. Fitness : somar ou multiplicar ?..............................................................82 
10.4. Implementando o AG e o PID..............................................................83 
10.5. Inicialização............................................................................................83 
10.6. Geração..................................................................................................83 
10.7. Laço.........................................................................................................83 
10.8. Análise.....................................................................................................83 
10.9. Saída Típica comentada......................................................................84 
10.10. Considerações na elaboração do trabalho....................................87 
10.11. Primeira abordagem na avaliação...................................................87 
10.12. Índices IMEC, ITMEC, ITE, IER................................................................88 
11. RESULTADOS E DISCUSSÕES 
11.1. Com Diferencial e Oposto....................................................................91 
11.2. Mutação Tradicional e com Oposto...................................................93 
11.3. Com Diferencial mas sem Oposto.......................................................96 
11.4. Tradicional e sem oposto......................................................................98 
11.5. Comparação dos resultados.............................................................100 
12. CONCLUSÃO.....................................................................................................................101 
REFERÊNCIAS BIBLIOGRÁFICAS..............................................................................................102 
ANEXO I – A Ferramenta SciLab............................................................................................103ANEXO II – Script Completo da simulação..........................................................................105 
ANEXO III – Resposta de outros métodos de sintonia........................................................120 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
4 
 
ÍNDICE DE FIGURAS 
 
ILUSTRAÇÃO 1 – MARIPOSAS EM MANCHESTER........................................................................ 10 
ILUSTRAÇÃO 2 – PERFIL DA ASA ................................................................................................... 17 
ILUSTRAÇÃO 3 – CIRCUITO ELETRÔNICO.................................................................................... 17 
ILUSTRAÇÃO 4 – FUNÇÃO A MAXIMIZAR ................................................................................... 19 
ILUSTRAÇÃO 5 – FUNÇÕES DE PERTINÊNCIA FUZZY .................................................................. 19 
ILUSTRAÇÃO 6 – CRUZAMENTO ENTRE GENES........................................................................... 23 
ILUSTRAÇÃO 7 - GRÁFICO DA VELOCIDADE DO AG EM FUNÇÃO DO TAMANHO DA 
POPULAÇÃO .......................................................................................................................... 26 
ILUSTRAÇÃO 8 – FASES DO AG..................................................................................................... 28 
ILUSTRAÇÃO 9 - AS PRIMEIRAS FASES DO LAÇO DE GERAÇÕES DO AG............................. 28 
ILUSTRAÇÃO 10 - DISTRIBUIÇÃO DAS CHANCES DE SORTEIO NESSA POPULAÇÃO ........... 32 
ILUSTRAÇÃO 11 – CRUZAMENTO ENTRE INDIVÍDUOS ............................................................... 34 
ILUSTRAÇÃO 12 – MUTAÇÃO TRADICIONAL.............................................................................. 35 
ILUSTRAÇÃO 13 – GRÁFICO DE FITNESS POR GERAÇÕES ....................................................... 40 
ILUSTRAÇÃO 14 - USANDO A MUTAÇÃO DIFERENCIAL CONDICIONADA........................... 41 
ILUSTRAÇÃO 15 - USANDO A MUTAÇÃO TRADICIONAL SOMENTE ....................................... 42 
ILUSTRAÇÃO 16 – FITNESS EM FUNÇÃO DA GERAÇÃO ........................................................... 43 
ILUSTRAÇÃO 17 - SAÍDA TÍPICA DE UMA SIMULAÇÃO DE AG – GRÁFICO DE FITNESS EM 
FUNÇÃO DAS GERAÇÕES.................................................................................................... 45 
ILUSTRAÇÃO 18 – FITNESS POR GERAÇÃO COM DELTA-FIT .................................................... 47 
ILUSTRAÇÃO 19 – GRÁFICO DO IPQ E DO IPQL........................................................................ 48 
ILUSTRAÇÃO 20 – ÓRBITAS AO REDOR DO MELHOR INDIVÍDUO ........................................... 51 
ILUSTRAÇÃO 21 - USANDO A FERRAMENTA INVERSÃO ........................................................... 56 
ILUSTRAÇÃO 22 – SISTEMA EM MALHA ABERTA......................................................................... 58 
ILUSTRAÇÃO 23- SISTEMA COM LOOP........................................................................................ 58 
ILUSTRAÇÃO 24– ESTRUTURA DE UM SISTEMA DE MALHA FECHADA..................................... 59 
ILUSTRAÇÃO 25- INTERMITÊNCIA NO CONTROLE ON-OFF ...................................................... 61 
ILUSTRAÇÃO 26 -SISTEMA ESTÁVEL - REFERÊNCIA (AZUL) E SAÍDA (LARANJA) .................... 62 
ILUSTRAÇÃO 27 - SISTEMA INSTÁVEL - REFERÊNCIA (AZUL) E SAÍDA (LARANJA).................. 62 
ILUSTRAÇÃO 28 -SISTEMA MARGINALMENTE ESTÁVEL ............................................................. 63 
ILUSTRAÇÃO 29 - PRINCIPAIS CARACTERÍSTICAS NA RESPOSTA ............................................ 64 
ILUSTRAÇÃO 30- SAÍDAS EM UM SISTEMA TÍPICO DE CONTROLE........................................... 65 
ILUSTRAÇÃO 31- IAE : A PARTE HACHURADA É A ÁREA DO ERRO ENTRE SAÍDA (LINHA 
MAIS GROSSA) E A REFERÊNCIA (LINHA MAIS FINA) ....................................................... 66 
ILUSTRAÇÃO 32 – SISTEMA DE CONTROLE EM MALHA FECHADA ......................................... 67 
ILUSTRAÇÃO 33 – MODELANDO O MOTOR CC........................................................................ 68 
ILUSTRAÇÃO 34- AÇÃO DE CADA PARCELA DE CONTROLE DENTRO DO PID ................... 72 
ILUSTRAÇÃO 35- EFEITO DO CONTROLE PROPORCIONAL NA SAÍDA DA PLANTA............. 72 
ILUSTRAÇÃO 36- EFEITO DO CONTROLE INTEGRAL NA SAÍDA DO SISTEMA......................... 73 
ILUSTRAÇÃO 37- EFEITO DO CONTROLE DERIVATIVO NA SAÍDA DO SISTEMA .................... 73 
ILUSTRAÇÃO 38- ESTRUTURA DO FORMATO ISA DE PID ........................................................... 74 
ILUSTRAÇÃO 39- ESTRUTURA DO ALGORITMO SÉRIE ................................................................ 75 
ILUSTRAÇÃO 40- ESTRUTURA DO PID PARALELO ....................................................................... 75 
ILUSTRAÇÃO 41- DIFERENTES FORMAS DE IMPLEMENTAR O PID ............................................ 76 
ILUSTRAÇÃO 42- RELAÇÃO ENTRE OS PARÂMETROS DAS DIFERENTES FORMAS DE PID.... 76 
ILUSTRAÇÃO 43– MODELO FODT................................................................................................. 77 
ILUSTRAÇÃO 44 – GRÁFICOS TÍPICOS DE SAÍDA DO AG......................................................... 86 
ILUSTRAÇÃO 45 – SAÍDAS TÍPICAS PARA O AG IMPLEMENTADO COM DIFERENCIAL E 
OPOSTO................................................................................................................................... 93 
ILUSTRAÇÃO 46 – SAÍDAS DO AG IMPLEMENTADO COM DIFERENCIAL MAS SEM 
PREFERÊNCIA AO OPOSTO .................................................................................................. 98 
ILUSTRAÇÃO 47 – SAÍDAS PARA AG IMPLEMENTADO COM MUTAÇÃO TRADICIONAL E 
SEM PREFERÊNCIA AO OPOSTO.......................................................................................... 99 
ILUSTRAÇÃO 48- EXEMPLO DE APLICAÇÃO DO SCICOS – SISTEMA EM BLOCOS ............ 103 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
5 
ILUSTRAÇÃO 49- EDITOR DE SCRIPTS DO SCILAB .................................................................... 104 
ILUSTRAÇÃO 50- AMBIENTE DE EXECUÇÃO INICIAL ............................................................... 104 
ILUSTRAÇÃO 51 – SAÍDA DO MOTOR EM MALHA ABERTA ,ENTRADA EM 1VCC .............. 120 
ILUSTRAÇÃO 52 – DETALHE DO TEMPO MORTO APROXIMADO DO MOTOR .................... 121 
ILUSTRAÇÃO 53 – APROXIMAÇÃO DE C-C PARA O MOTOR COMO “CAIXA PRETA” ... 122 
ILUSTRAÇÃO 54 – SINTONIA USANDO C-C............................................................................... 123 
ILUSTRAÇÃO 55 – ESFORÇO DE CONTROLE NA SINTONIA POR C-C .................................. 124 
ILUSTRAÇÃO 56 – MAPA LGR DAS TRAJETÓRIAS DOS PÓLOS DE MALHA FECHADA NO 
PLANO ‘S’.............................................................................................................................. 125 
ILUSTRAÇÃO 57 – SAÍDA DO MOTOR USANDO Z-N................................................................ 126 
ILUSTRAÇÃO 58 – ESFORÇO DE CONTROLE USANDO Z-N COM FODT............................... 127 
 
 
ÍNDICE DE TABELAS 
 
TABELA 1 – EXEMPLO DE POPULAÇÃO EM AG ......................................................................... 31 
TABELA 2 – CHANCES DE SELEÇÃO BASEADO NO FITNESS..................................................... 32 
TABELA 3-TABELA DE SINTONIA NUMÉRICA DE PID POR COHEN-COON ............................. 78 
TABELA 4 – SINTONIA USANDO O MÉTODO DOS GANHOS ÚLTIMOS DE ZIEGLER-NICHOLS
.................................................................................................................................................. 79 
TABELA 5 – VALORES A SEREM USADOS NO MÉTODO Z-N DE MALHA ABERTA................... 79 
TABELA 6 – MÉDIA DAS SAÍDAS ENTRE DIFERENCIAL E TRADICIONAL (AMBAS COM 
PREFERÊNCIA AO OPOSTO).................................................................................................89 
TABELA 7 – MÉDIA DAS SAÍDAS ENTRE DIFERENCIAL E TRADICIONAL (SEM PREFERÊNCIA 
AO OPOSTO) .......................................................................................................................... 90 
TABELA 8 – MÉDIA DAS SAÍDAS ENTRE DIFERENCIAL COM E SEM PREFERÊNCIA AO 
OPOSTO................................................................................................................................... 90 
TABELA 9 – MÉDIA DAS SAÍDAS ENTRE MUTAÇÃO TRADICIONAL COM E SEM 
PREFERÊNCIA AO OPOSTO .................................................................................................. 90 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
6 
 
RESUMO 
 
Esse trabalho tem como objetivo apresentar o conceito da Mutação 
Diferencial Condicional, para a otimização da eficiência de algoritmos 
genéticos, quando comparado à mutação diferencial tradicional (ou 
‘incremental’) ou mesmo a mutação tradicional. 
 
A análise do desempenho foi realizada através da implementação de 
um controlador PID , tendo sido feita a comparação dos resultados 
desta abordagem com as outras formas de mutação existentes. 
 
Foram desenvolvidas ferramentas auxiliares para análise de 
desempenho do próprio algoritmo, e para auxiliar e melhorar a 
evolução das gerações. 
 
Os resultados obtidos mostraram que estatisticamente, o uso da 
Mutação Diferencial Condicional e das ferramentas auxiliares elevou o 
desempenho do algoritmo genético como um todo. 
 
 
 
 
 
 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
7 
Abstract 
 
This work have how its goal to show the Conditional Differential 
Mutation (also called ‘Triggered’ Differential Mutation) for the 
optimization of efficiency of genetic algorithm, when compared to the 
traditional differential mutation (or ‘creep’ mutation) or even the 
traditional mutation. 
The analysis of performance was done thought the 
implementation of a PID controller, and there was made the comparison 
among the results of this approach and the other already developed 
mutation kinds. 
It was developed auxiliary tools for the performance analysis of 
the genetic algorithm itself, and to keep and improve the evolution 
along the generations. 
The results showed that statistically, the usage of Conditional 
Differential Mutation and the auxiliary tools lifted up the performance of 
the whole genetic algorithm. 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
8 
Introdução 
 
Os controladores estão presentes na maioria das plantas industriais 
atualmente. Eles permitem que o sistema siga uma referência ou regime 
de funcionamento de modo automático, corrigindo automaticamente 
o sistema quando o mesmo se desvia da posição original. 
 
Para que isso ocorra (e de maneira segura), esses controladores 
precisam ter suas configurações escolhidas de maneira correta, 
levando em consideração o tipo de equipamento que estão 
controlando e qual o desempenho esperado para o mesmo. 
 
Porém essa escolha depende e muito da experiência daqueles que irão 
instalar o controlador, e se torna extremamente complicada em 
situações envolvendo atrasos na resposta, máquinas lentas ou de 
comportamento não-linear. 
 
Para isso, propõe-se neste trabalho a aplicação de Inteligência Artificial 
(IA) na forma de Algoritmos Genéticos para realizara sintonia destes 
controladores automaticamente e de maneira ótima. 
Isso permite que o implementador humano apenas defina qual a planta 
a usar (seu modelo), o desempenho do controle feito e o tipo de 
controlador desejado. O sistema com IA então procura qual o melhor 
conjunto de configurações deste controlador para que o sistema se 
comporte conforme estipulado pelo humano. 
 
Neste trabalho escolheu-se ajustar um controlador tipo PID, muito 
corrente no meio industrial, podendo ser encontrado em muitos 
equipamentos que permitem realimentação, como CLP’s e inversores 
de freqüência. 
 
A sintonia de controladores PID foi escolhida apenas como base para 
aplicação dos algoritmos genéticos. Não é objetivo deste trabalho 
apresentar um novo método de sintonia de PID, e sim um novo método 
dentro dos Algoritmos Genéticos. 
Apesar disso, os resultados das sintonias foram superiores aos métodos 
convencionais e os resultados destes, apresentados como apêndice. 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
9 
4. OS ALGORITMOS GENÉTICOS 
 
4.1. Idéia Básica – o Darwinismo [1] 
 
Conceito de adaptação 
 
Endente-se por adaptação a capacidade de sobrevivência e 
reprodução de uma espécie num determinado ambiente. 
Os camelos, por exemplo, são animais adaptados à vida no deserto. 
Assim, são portadores de uma série de características que permitem a 
sua sobrevivência e reprodução naquele ambiente, como : 
 
- Resistência a perda de água 
- Capacidade de utilização de água metabólica 
- Resistência a variações internas de temperatura 
- Patas adaptadas para caminhar na areia das dunas 
- Resistência a seca, podendo ficar vários dias sem água 
 
Exemplo clássico de adaptação 
 
Em Manchester na Inglaterra, em meados do século XIX, antes do 
processo de industrialização da cidade, era marcante o predomínio das 
mariposas claras em relação às mariposas escuras, ambas pertencentes 
à mesma espécie (Biston Betularia). 
A coloração clara constituía, na época, uma característica favorável, 
uma vez que permitia a camuflagem de mariposas claras nos claros 
troncos das árvores recobertas de liquens. Assim , era difícil a 
visualização por parte dos pássaros insetívoros, que então capturavam 
e devoravam as mariposas escuras, facilmente identificáveis. 
Após a industrialização da cidade, os liquens foram praticamente 
eliminados pela poluição ambiental, e a fuligem das fábricas tornou o 
ambiente (e as cascas das árvores) mais escuro. Nessa nova situação, 
as mariposas escuras passaram a se camuflar melhor, e dentro de 
algum tempo, constituíam o grupo predominante. 
 
Deste exemplo pode-se concluir que uma mesma característica, 
favorável em um ambiente, pode se tornar desfavorável em outro. 
O conceito de adaptação está intimamente ligado ao tipo de 
ambiente onde a espécie desenvolve suas atividades. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
10 
 
Ilustração 1 – Mariposas em Manchester [1] 
 
 Darwin e o mecanismo evolutivo 
 
Em 1859, o naturalista Charles Robert Darwin (1809-1882) expôs em seu 
livro A origem das Espécies suas idéias a respeito do mecanismo de 
transformação das espécies. 
 
Observações preliminares de Darwin 
 
Inicialmente, Darwin considerou observações a partir das quais concluiu 
algumas de suas idéias evolucionistas: 
 
-Os organismos vivos produzem grande quantidade de unidades 
reprodutivas; no entanto, o número de indivíduos permanece mais ou 
menos constante. Concluiu então, que na Natureza deveria haver uma 
forte competição, uma luta pela vida, na exploração dos recursos 
oferecidos pelo ambiente, tais como disponibilidade de alimento, 
espaço, luminosidade,etc. 
 
-Os organismos de uma população natural são diferentes entre si, 
apresentando variações na forma e no comportamento. Essas 
variações podem ser transmitidas de uma geração parra outra. 
 
Charles Darwin partiu da Inglaterra, a bordo do navio HMS Beagle em 
dezembro de 1831 e retornou em outubro de 1836.Nessa viagem, ele 
percorreu entre outros lugares, a costa oeste da América do Sul, 
algumas ilhas dos mares do Sul (especialmente Galápagos), o Brasil e o 
estreito de Magalhães. 
 
 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
11 
 A seleção natural 
 
Alicerçado em suas observações preliminares, Darwin considerou que 
certas características poderiam contribuir para a sobrevivência e 
reprodução de certos indivíduos num determinado ambiente, 
constituindo-se, portanto, comovariações “favoráveis”. 
Indivíduos portadores de variações “desfavoráveis” por sua vez, teriam 
grandes dificuldades de sobreviver e seriam gradativamente extintos 
desse ambiente. 
Assim , diferenças individuais já existentes entre os indivíduos de uma 
mesma espécie seriam selecionadas naturalmente pelo ambiente. 
Então o ambiente, como fator de seleção, tenderia a : 
 
-Fixar os indivíduos portadores de variações favoráveis 
-Eliminar os portadores de variações desfavoráveis 
 
Dessa maneira a Natureza iria, ao longo das gerações, “aprimorando” a 
espécie e “contribuindo” com a sua adaptação a um determinado 
ambiente. 
 
 Neodarwinismo: ampliação da teoria de Darwin 
 
Apenas no século XX, com o redescobrimento dos trabalhos de Mendel 
e com o aprofundamento do conceito de genes, foi possível determinar 
os principais responsáveis pela variedade nos seres vivos: as mutações e 
as recombinações gênicas (vindas do Cruzamento entre os genes dos 
pais, gerando um DNA novo, passado ao filho). 
O neodarwinismo constitui uma ampliação das idéias de Darwin, 
explicando as causas da variedade de seres vivos, mesmo que dentro 
da mesma espécie. 
As mutações e recombinações gênicas aumentam a variedade 
genética de uma população, enquanto que a seleção natural diminui 
essa variedade, a medida que “filtra” apenas os mais adaptados, 
dando preferência de sobrevivência a estes e extinguindo os demais. 
 
 Mendel e a Genética 
 
Genética é o ramo da Biologia que estuda o mecanismo de transmissão 
das características de uma espécie passadas de uma geração para 
outra. É a ciência da hereditariedade. 
 
As características de uma espécie são condicionados pelos genes, 
estruturas hereditárias presentes nos cromossomos do núcleo da célula. 
O gene é definido como um pedaço DNA cromossômico capaz de 
determinar a síntese de uma proteína.O tipo de proteína a ser 
formulada depende do código estabelecido pela seqüência de bases 
que esse gene possui. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
12 
Cada cromossomo pode abrigar inúmeros genes. O local onde cada 
gene se situa (o “endereço” do gene) é chamado lócus gênico. 
Lócus vem do latim locus que significar “lugar” , e seu plural é escrito 
loci, “lugares”. 
 
Um gene pode assumir diversos valores, e para cada um desses valores 
existe uma característica do indivíduo que os contêm. 
Por exemplo,a cor dos olhos na raça humana é definida por um gene. 
Quando esse gene tem um valor , os olhos do indivíduo são claros. 
Quando apresenta outro valor, apresenta olhos castanhos ou negros. 
 
Realizando cruzamentos entre ervilha-de-cheiro (Pisum sativum) durante 
cerca de oito anos, o padre Gregor J. Mendel (1822-1884) constatou 
que as características estudadas manifestavam-se nas ervilhas 
descendentes segundo regras matemáticas que ele estipulou, e de 
acordo com as ervilhas-pais usadas no cruzamento. Mendel foi 
portanto, o primeiro a associar a hereditariedade (bem como suas 
regras) à informações contidas nas células do próprio indivíduo. 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
13 
 COPIANDO A NATUREZA - OS ALGORITMOS GENÉTICOS [2],[3] 
 
O Algoritmo Genético (AG) é uma ferramenta de Inteligência Artificial 
(IA) para otimizar estruturas, cujo princípio de funcionamento é inspirado 
nas teorias de evolução de Charles Darwin. 
 
A teoria por ele proposta indica que dentro de uma população, os 
indivíduos mais bem adaptados ao meio têm maior chance de 
sobrevivência, e os mais fracos aos poucos desaparecerão, geração 
após geração, da população, até que a maior parte dela se pareça 
muito com o(s) indivíduo(s) mais forte(s). 
 
 
A idéia central da IA é fazer com que elementos artificiais (por exemplo, 
os computadores) consigam resolver problemas. 
O que o AG faz é representar as possíveis respostas do problema na 
forma de indivíduos com um código genético (DNA) , o meio ambiente 
é o problema a ser resolvido e sua adaptação é chamada de fitness, 
que é a medida numérica dessa adaptação. 
 
Quando é dito “DNA” dentro do AG, deve ser entendido como 
estruturas dentro da programação capazes de guardar dados de forma 
ordenada e posicionada dentro da memória. 
A forma mais básica de estrutura dentro da programação usual são os 
vetores e matrizes. 
 
Assim como as teorias naturais de Darwin, o AG não trabalha com um 
único indivíduo, e sim com uma população inteira de possíveis soluções. 
 
Assemelha-se muito a um processo de seleção dentro de uma empresa. 
Uma quantidade grande de possíveis contratados se apresenta, e 
mediante um padrão (perfil), alguns são selecionados e os demais 
descartados. Depois, mais triagens são feitas deixando o perfil cada vez 
mais exigente até que apenas um ou dois candidatos resta para 
contratação. 
O que o AG faz é exatamente o acima descrito, tendo como “perfil” o 
quão próximo da solução do problema o candidato está. 
 
Exemplo de aplicação – encontrando raízes de uma equação 
 
Por exemplo,se é necessário resolver uma equação do segundo grau, 
achando suas raízes : 
 
Y=ax²+bx+c 
 
É sabido que as raízes de uma equação são todos os valores que, 
quando substituídos na equação original, anulam sua imagem (no caso, 
os valores de X que fazem Y=0). 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
14 
É evidente que podem ser encontradas através da fórmula de 
Bháskara, todavia para equações polinomiais de graus maiores ou 
equações envolvendo termos transcendentais (como seno, cosseno, 
exponenciais ou logaritmos) fórmulas prontas ou métodos analíticos se 
tornam impraticáveis ou mesmo nem existem. 
 
Sendo uma equação polinomial de grau 2, sabe-se que é possível 
encontrar 2 raízes (mesmo que sejam iguais), chamadas X1 e X2. 
Uma abordagem em algoritmos genéticos poderia representar essa 
solução como um genoma de 2 genes, X1 e X2: 
 
 [ X1 | X2 ] 
 
É gerada uma população grande e aleatória de indivíduos, com X1 e 
X2 completamente diversos. 
Todavia, alguns quando substituídos resultarão em um valor mais 
próximo de zero do que outros. Pode-se dizer, portanto, que esses são os 
mais bem adaptados ao problema (equação) e com certeza passarão 
para próxima geração. 
 
Então, ao final de N gerações, existirá um indivíduo cujo DNA contém X1 
e X2 tais que, quando substituídos na equação, retornem zero ou um 
valor muito próximo (neste problema de achar raízes, o quão próximo 
de zero é a medida do ‘fitness’ do indivíduo). 
 
Exemplo : a equação y=x ² - 2x +1 : 
 
Resolvendo por Bháskara encontramos as raízes X1=+1 e X2= -1. 
Logo, se fosse preciso resolver essa equação usando algoritmos 
genéticos, seria possível representar essa solução exata como o 
indivíduo “ideal”, tendo o seu DNA representado pelo vetor: 
 
[ +1 | -1 ] 
 
É claro que a priori esse indivíduo ideal não é conhecido, sendo este o 
motivo original que levou ao AG como meio de resolução da equação. 
Mas, apesar de não ser conhecido, sabe-se que quanto mais próximos 
desse ideal (desconhecido) os indivíduos estiverem, mais próximo de 
zero serão os valores de Y correspondentes. 
 
Essa forma indireta de medir o quão próximo do ideal e´uma outra 
possível definição de fitness. 
 
Um indivíduo cujo DNA seja [ 2, 0] por exemplo, teria 
X1= 2 e X2=0 
Cujas imagens na equação original são 
Y(X1)=+1 e Y(X2)=+1 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
15 
Ou seja, o par de valores [2, 0] está mais longe de ser uma solução do 
que o par [1, -1] (solução ideal). Como se deseja encontrar as raízes da 
equação, quanto mais próximos de zero forem os valores Y(X1) e Y(X2), 
tanto melhor é esse par [X1,X2] ou melhor é a qualidade da solução 
proposta. Isso pode ser traduzido , por exemplo , como 
 
Qualidade = Y(X1)² + Y(X2)² 
 
Essa “qualidade” mede na verdade a adaptação do indivíduo cujo 
DNA é [X1, X2] e já foi apresentada nas páginas acima como “fitness”. 
 
 VANTAGENS DO AG [2]Pela maneira como funcionam, os AG reúnem as seguintes vantagens: 
- Generalidade : Os AG simulam a natureza em um de seus mais fortes 
aspectos : a adaptabilidade; Visto que a representação e a avaliação 
das possíveis soluções são as únicas partes (do total de operações 
implementadas em um AG) que obrigatoriamente requisitam 
conhecimento prévio do problema abordado e suas restrições,basta a 
alteração destas para portá-los a outros casos. A função de um 
programador de AG não é de que forma chegar a uma solução, mas 
sim como essas soluções deveriam se parecer. 
 
-Paralelismo explícito – como cada indivíduo existe isoladamente e é 
avaliado (fitness) individualmente, é fácil transportar o AG para uma 
plataforma computacional com multiprocessamento. 
 
-Busca subjetiva : uma vez que o AG não trabalha com os parâmetros 
em si, mas com o DNA todo, os que tiverem segmentos de genes 
favoráveis serão perpetuados. Assim, os AG otimizam a solução do 
problema unindo subjetivamente fragmentos de DNA favoráveis em 
indivíduos diferentes, fazendo uma sobreposição de ‘suspeitas’ ou 
candidatos ‘promissores’. 
 
-Facilidade no uso de restrições : É possível adicionar diversas restrições 
durante a avaliação dos indivíduos, bastando incluí-las na seção do 
código que trata o fitness. Essas restrições podem ter pesos diferentes e 
aplicações diferentes. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
16 
Assim como na Natureza, ocorrem interações genéticas entre os 
indivíduos da população, de modo que : 
 
1-candidatos com desempenho mediano possam unir as suas 
 partes fortes para gerar um terceiro indivíduo ainda mais forte 
 
2-candidatos com desempenho ruim de alguma forma alterem 
 seu DNA na tentativa de assim se tornarem melhores 
 
3-candidatos bons possam se manter na população 
 
Essas interações são respectivamente, cruzamento , mutação e cópia, 
que funcionam de modo idêntico às suas correspondentes na Natureza. 
Porém no lugar das proteínas Adenina, Guanina, Tiamina e Citosina do 
DNA, tem-se valores numéricos (0.14, 2.1,etc.). 
 
Se fosse desejado encontrar o valor máximo da parábola do exemplo 
anterior, o fitness com certeza não seria o mesmo, pois desta vez é 
desejado maximizar o valor de Y(X) ,e não anulá-lo como no exemplo. 
Daí pode ser tomada a noção de que o fitness está diretamente ligado 
ao problema a ser resolvido e com o tipo de solução que se pretende 
encontrar. Na verdade, é mais realista dizer que o fitness nasce, emerge 
do problema, tal seu grau de ligação com ele.E isso fica evidente com 
os exemplos anteriores. 
 
Requisitos mínimos para aplicar os AG na resolução de problemas: 
 
- Identificar quais informações são necessárias para resolver o 
problema e quais são as informações a obter do mesmo a fim de 
solucioná-lo 
 
- Encontrar uma representação para essas informações na forma 
de genes (vetores ou matrizes , sejam numéricas ,alfanuméricas 
ou booleanas) 
 
- Um modo de simular as possíveis soluções geradas, de forma 
seqüencial, a saber uma simulação em “batelada” (Batch). 
 
 
- Método de avaliação de quão boas são as soluções encontradas 
(fitness) 
 
Todos esses passos devem ser feitos iterativamente por um programa 
maior , até que a solução encontrada tenha desempenho suficiente 
para o programador. 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
17 
 
 ALGUMAS APLICAÇÕES ATUAIS [2],[4],[9] 
 
Otimização de Perfis (aerodinâmica de aviões-caça, carros de corrida). 
 
Pode-se representar o perfil de uma asa de avião dentro de um AG 
definindo um DNA com 3 valores : 
 
-Ângulo frontal da asa 
-Ângulo de saída da asa 
-Comprimento inferior da asa 
 
Conforme desenho abaixo 
 
 
Ilustração 2 – Perfil da asa 
 
E esses valores podem ser otimizados de acordo com critérios como 
força de arraste, força de sustentação a uma velocidade final,etc. 
 
Geração de circuitos eletrônicos [11] 
 
No design de circuitos para casamento de impedâncias ou com outras 
características elétricas, pode-se montar uma rede de elementos 
passivos ligados entre si, conforme a figura abaixo: 
 
 
Ilustração 3 – Circuito eletrônico 
 
Cada elemento desses pode ser um indutor, um capacitor ou resistor. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
18 
De acordo com o que cada um for, e com os valores, eles terão um 
comportamento frente a uma tensão de entrada Vin, gerando uma 
tensão de saída Vout. 
Define-se, para um determinado Vin, qual será o Vout desejado. 
A partir daí, pode-se representar cada uma dos elementos passivos 
como um DNA de 5 genes, cada um contendo um número complexo. 
Sabendo que um resistor pode ser expresso na forma complexa como 
 
R = R i+ 0 j 
Os capacitores , como C = 0 i - Xc j 
E os indutores, como L = 0 i + XL j 
 
Onde Xc e XL são os valores da reatância capacitiva e indutiva 
respectivamente, pode-se guardar cada um desses números complexos 
em um gene, dentro do DNA de 5 genes: 
 
[ Z1 Z2 Z3 Z4 Z5] 
 
E simulando cada um deles em um simulador de eletrônica (por 
exemplo, o SPICE) pode-se separar os que tiverem Vout mais próximos 
do Vout desejado, quando excitados na entrada com Vin. 
 
Resolução de equações transcendentais [9] 
 
Seja a equação 






−





= 32
x
sin
x
sin
ey Equação 1 
 
Cujo gráfico é conforme a Figura 4. 
Deseja-se saber o ponto de máximo global da mesma dentro do 
intervalo -10 a 10. 
Existe um X tal que Y(x) é o maior valor dentro deste intervalo. 
Pode-se codificar os indivíduos em um DNA com 2 genes: 
[ X1 X2] onde X1 é representa a unidade ou a parte inteira de X 
 e X2 representa a parte fracionária de X. 
Por exemplo, X=4,3 resulta em X1=4 e X2=3 
 
A simulação é feita usando 
X=X1 + X2/10 
Fitness = Y(X) 
 
 
 
 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
19 
Otimização de Funções de Pertinência em lógica nebulosa (Fuzzy) [7] 
 
Sem entrar em detalhes dentro da lógica fuzzy, basta saber que ela 
realiza inferências e operações lógicas com valores imprecisos ou com 
graus de certeza difusos, bem como valores lingüísticos como “quente”, 
“razoavelmente quente”,etc. 
E para isso ela usa funções chamadas “funções de pertinência”, que 
retornam ao programa o quanto um determinado valor (por exemplo, 
de temperatura) se encaixa nos conjuntos lingüísticos definidos (por 
exemplo, conjunto das temperaturas ‘quentes’, ‘frias’, ‘mornas’,etc). 
Essas funções (no formato tradicional) tem a forma de triângulos, onde 
altura e ângulo de abertura desses pode ser otimizadas (fig. 5) 
 
Uma possível aplicação de AG sobre essa estrutura seria codificar esses 
triângulos em DNA’s com 3 genes: 
 
[ Altura Ângulo de abertura Ponto Central ] 
[ “A” “H” “Xo” ] 
 
 
Ilustração 4 – Função a maximizar 
 
 
Ilustração 5 – Funções de pertinência fuzzy 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
20 
 
4.2. TOPOLOGIA DOS ALGORITMOS GENÉTICOS 
 
Por topologia pode-se entender a forma como o AG é organizado, qual 
o formato e a seqüência das etapas dentro dele. 
 
 Seqüência clássica [2],[12],[10] 
 
A seqüência clássica de iteração – chamada também de Loop de 
Gerações ou Laço de gerações – é a base de todos os AG atuais, e 
segue o modelo: 
 
1 - Geração da população inicial, definindo intervalo e 
 codificação 
2 - Avaliação dos indivíduos através de uma função (fitness) 
3 - Classificação e separação dos melhores 
4 - Aplicação de operadores genéticos (OPGEN) 
5 - Geração atual (filhos) substitui a anterior (pais) 
6 - Repetem-se os passos de 2 a 5 até atingir o objetivo 
 
Como objetivo ou critério de parada, pode-se definir : 
-Número máximo de iterações (gerações) 
- Valor mínimo de fitness 
 
Neste trabalho adotou-se como critério o número de iterações. 
Para cada uma das etapas acima existem inúmeras maneiras de 
implementação,cada uma delas apresentando uma característica 
que se adéqua melhor ao tipo de problema a ser resolvido pelo 
AG.Uma escolha errada ao formatar uma etapa, e o desempenho 
global do AG pode ser comprometido, tanto na rapidez com a qual ele 
encontra a solução como no quão próximo ele consegue chegar da 
solução ideal. 
 
As seis etapas acima serão estudadas e algumas de suas variantes 
explanadas adiante. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
21 
INTERVALO E CODIFICAÇÃO [10][2][14]] 
 
Esta é a parte mais importante, pois é aqui que é definida a 
representação dos indivíduos, quantos genes cada um irá ter e o que 
será guardado dentro desse gene (números, valores booleanos tipo SIM 
e NÃO, valores tipo caractere representando uma direção como ‘N’,’S’, 
etc.). 
 
É aqui que será decidido como o AG irá ajudar a resolver o problema 
proposto. Se o programador não encontra uma maneira de representar 
as variáveis do problema na forma de genes, não adianta nem mesmo 
seguir com as demais etapas, pois quais genes elas iriam tratar? 
 
Primeiro, é preciso atentar para que tipo de informação será guardado 
nos genes. Que informações são relevantes para resolver o problema? 
 
No exemplo da parábola , apenas duas informações eram necessárias 
para resolver o problema : X1 e X2. Portanto, foi escolhido um DNA 
contendo esses dois genes. 
 
Considere o famoso Problema do Caixeiro Viajante (PCV), onde é 
necessário escolher o itinerário do caixeiro de modo que ele cumpra as 
cidades no menor tempo. Suponha também que ele precise percorrer 
quatro cidades : A, B, C e D. 
A informação necessária para uma solução é a ordem em que essas 
cidades são visitadas. Pode-se representar uma solução com um DNA 
de 4 genes : 
 
G1 G2 G3 G4 
 
Onde G1 é o primeiro gene, representa a 1ª. cidade a ser visitada. 
 G2 é o segundo gene, representa a segunda cidade, visitada 
após a primeira 
E assim sucessivamente. Cada gene pode assumir os valores A,B, C ou D 
(obviamente não ao mesmo tempo), resultando em um indivíduo, por 
exemplo : 
 
B C D A 
 
Onde aqui a rota do caixeiro seria B���� C����D����A 
Como é possível observar nos exemplos anteriores, não só o formato do 
DNA muda, como também o tipo de valor que seus genes assumem. 
 
No caso do Caixeiro, foi usado um gene do tipo caractere, guardando 
uma letra, representando a cidade. No caso da parábola, os genes 
continham valores numéricos que representavam as possíveis raízes da 
equação de segundo grau proposta. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
22 
 
O intervalo em que cada valor pode variar (no caso de números reais) 
ou o conjunto de símbolos/caracteres (como de ‘A’ a ‘Z’, “Sorocaba, 
Itu, Iperó”,etc. no caso de genes não numéricos) também é relevante, 
mas depende de como o AG irá lidar com eles. 
Por exemplo, no caso da parábola, poder-se-ia fixar X1 e X2 variando 
entre -5 e 5, onde acredita-se ser o intervalo em que esteja a solução. 
Ou no caso do caixeiro, o conjunto de cidades poderia ser maior, 
contendo todas as cidades intermediárias, bastando que ele chegasse 
em um determinado lugar ou cumprisse o itinerário. 
Nesse caso, fica mais fácil realizar operações como cruzamento, cópia 
e mutação quando usamos letras e não há cadeias de caracteres 
(strings) a serem tratadas. 
 
Uma representação possível (somente em caso de genes numéricos), é 
guardar a informação no gene na forma de uma porcentagem. 
Por exemplo, se o intervalo fosse de 0 a 150 para um determinado gene, 
quando este estivesse valendo 0,75, significaria que seu valor está a 75% 
do intervalo ou seja, de 112,5 unidades. 
Esse tipo de representação, fixando o gene entre 0 e 1 (0 para o menor 
valor do intervalo e 1 para o valor máximo do intervalo ou seja, 100%), é 
muito útil pois pode-se normalizar toda a programação e preparar 
diversas ferramentas e operações sabendo já de antemão que, não 
importa qual o problema a ser solucionado ou o intervalo escolhido, 
qualquer gene estará sempre entre 0 e 1.Isso permite que qualquer 
alteração (no problema original , intervalo ou mesmo no cálculo do 
fitness) dispense alterar o restante do código, tentando readequar 
comparações, subtrações,etc. aos novos números gerados. 
 
Se é usada uma codificação exageradamente complexa (por 
exemplo, com genes redundantes ou em excesso), ou incompleta 
demais para representar uma solução-candidata (por exemplo, 
faltando informações) podemos comprometer, respectivamente, o 
tempo de execução e a convergência para uma solução. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
23 
REAIS OU BINÁRIOS ? [2],[10] 
 
Existem duas vertentes dentro da representação do problema na forma 
de genes : 
Uma usando genes contendo números reais e trabalhando 
aritmeticamente com eles; Computacionalmente isso se traduz em 
vetores de N posições, cada uma contendo um número real, do tipo 
FLOAT ou DOUBLE. 
 
E outra usando genes binários e tratando-os de forma binária. 
 
 
Ilustração 6 – Cruzamento entre genes 
 
 
• Usar números reais aproxima muito mais o programa e o 
programador da realidade do problema tratado; É mais fácil 
rastrear o funcionamento do programa e visualizar 
imediatamente o significado de um gene ou DNA. 
• É melhor pois é mais próxima da linguagem natural do ser 
humano e da realidade fracionária da natureza. 
• Representação por números reais (ponto flutuante) é mais 
adequada em problemas de otimização com variáveis sobre 
domínio contínuo; 
• Em particular em grandes domínios onde a representação binária 
requer um longo cromossoma: 
• Ex: 100 variáveis, [-500,500], 4 casas decimais = 2400 bits 
• Representação por reais é mais rápida na execução (não há 
decodificação nem tratamento bit a bit); 
• Representação por reais oferece maior desempenho pode ser 
melhorado com operadores específicos ao problema; 
• Na representação por reais, dois pontos próximos um ao outro no 
espaço de representação, estão também próximos no espaço do 
problema;
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
24 
 
 
No AG clássico, um conjunto (no caso de programas, uma matriz) de 
indivíduos é gerado, jogando um valor aleatório em cada gene, de 
modo a criar uma população bem diversificada. 
 
Novamente vê-se o quão importante é projetar o gene (quando for do 
do tipo numérico) entre 0 e 1. Isso permite padronizar toda a 
programação do script , que irá tratar sempre números dentro de um 
intervalo definido. 
 
As funções que geram números aleatórios implementadas nas 
linguagens tradicionais de programação (como C, Pascal , Delphi,etc.) 
o fazem entre 0 e 1. 
 
Deste parágrafo em diante – para simplificação – sempre que for 
mencionado número “aleatório” subentendam-se valores gerados por 
algoritmos das linguagens de programação atuais que, como se sabe, 
são chamados pseudo-aleatórios (são funções que geram seqüências 
periódicas muito longas, e que para a maioria das aplicações podem 
ser consideradas aleatórias). 
 
Caso o gene seja do tipo alfanumérico, podem ser usadas duas 
abordagens: 
 
1º) No caso de genes contendo letras, cria-se uma lista ordenada, e 
guarda-se no vetor-DNA do indivíduo o valor do índice onde pode ser 
encontrado o caractere desejado. 
 
2º) Com genes representando textos (strings) usa-se o mesmo recurso da 
lista ordenada, mas em cada posição existe um texto. 
 
Como exemplo, seja a lista : 
 
[“Sorocaba” , “Itu” , “Votorantim”, “Salto”]. 
 
Pode-se dizer que “Itu” está na segunda posição nessa lista, ou seja, tem 
índice 2. O mesmo vale para “Sorocaba”, índice 1. 
 
Se fosse desejado traçar a menor rota entre essas cidades, ao invés de 
guardar todos esses textos para cada indivíduo, guarda-se somente os 
índices correspondentes. 
 
[1 4 2 3] pode representar [“Sorocaba”, “Salto”, “Itu”,”Votorantim”] 
 
Desde que durante os cálculos de distância o programa use esses 
índices paraidentificar qual é a cidade referida. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
25 
Isso permite inclusive o uso de DNA’s híbridos, onde cada lócus no vetor 
representa um dado de tipo diferente. 
O primeiro lócus pode ser um número puro, que representa algum valor 
numérico do problema, e um segundo lócus bem ao lado pode – 
apesar de também ser um número – fazer referência a dados do tipo 
string, através dessa tática de usá-lo como índice de uma lista. 
 
A qualidade da rotina de geração de números aleatórios (ou 
randômicos) é muito exigida nos AG. Durante a geração da população 
inicial e depois, durante as operações genéticas entre os indivíduos, 
essas rotinas são chamadas consecutivamente, e uma grande 
dependência dos ciclos do relógio ou um período curto de repetição 
podem criar populações muito homogêneas e semelhantes. 
 
Voltando ao tópico principal, a geração da população inicial 
geralmente se dá na forma de matriz, com duas abordagens possíveis: 
 
Cria-se uma matriz com “N” vetores , tantos quanto forem os indivíduos. 
Em cada vetor dessa matriz está o “vetor-DNA” do indivíduo e logo 
depois um lócus contendo o valor do fitness desse indivíduo, 
 
[ G1 , G2 , G3 , G4 , ......., Gn | Fitness ] 
 
 Vetor-DNA 
Do indivíduo 
 
G1, G2,… Gn são os genes do indivíduo G.Nessa formação o fitness do 
indivíduo faz parte da mesma matriz do DNA. 
 
Ou então , tem-se a segunda opção : guardar os vetores-DNA em uma 
matriz e o fitness em um vetor separado: 
 
 
Essa variação torna mais fácil as operações genéticas, já que ao 
contrário da primeira, não é necessário se preocupar em não misturar os 
valores de fitness com os valores dos genes durante o cruzamento, 
mutação,etc. Porém ao ordenar os indivíduos,deve-se ordenar as duas 
matrizes (DNA e fitness) ao mesmo tempo, o que pode ser 
inconveniente. 
 
Fit-G 
Fit-H 
Fit-I 
Fit-J 
G1 G2 G3 ...........Gn 
H1 H2 H3 ...........Hn 
I1 I2 I3 .............In 
J1 J2 J3 .............Jn 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
26 
 O tamanho da população 
 
A quantidade de indivíduos gerada e mantida durante as gerações 
depende muito de como serão feitas as etapas do algoritmo genético, 
que tipos de operadores genéticos serão usados e como serão 
implementados cada um deles. 
 
Populações pequenas implicam em baixa diversidade genética e 
poucos resultados possíveis ao escolher aleatoriamente os indivíduos 
para serem cruzados, copiados e mutados. Conforme será visto 
adiante, isso retarda a convergência do AG, levando muito mais 
gerações para atingir o resultado. 
 
Por sua vez, populações muito grandes esbarram no tempo muito 
grande de processamento, já que cada indivíduo deve ser simulado ou 
calculado, avaliado e depois eles devem ser ordenados em ordem 
decrescente de desempenho (fitness). 
Esse comportamento pode ser traduzido na figura 7: 
 
 
Ilustração 7 - Gráfico da velocidade do AG em função do tamanho da população 
 
 
 
Encontrar essa faixa ideal vem de experiência com AG ou com 
tentativa e erro até definir um tamanho ideal de população, ao menos 
o mínimo para que seja encontrada uma solução ótima em um tempo 
razoável. 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
27 
 AVALIAÇÃO DOS INDIVÍDUOS (fitness) 
 
A parte fundamental depois da codificação é a maneira como avaliar 
quais são os melhores indivíduos da geração atual dentro do loop de 
gerações do AG. 
 
Já foi dito que uma codificação muito grande ou pequena 
compromete o desempenho do algoritmo. Porém, ter uma codificação 
bem feita é inútil se não existe uma maneira inteligente e planejada de 
se classificar os indivíduos, separando os melhores dos piores. É 
necessário definir quais aspectos da solução são preferidos ou, caso 
haja mais de um, qual a prioridade ou “peso” de cada um deles. 
 
Problemas típicos onde os AG entram são os de otimização, que 
envolvem maximizar ou minimizar uma determinada grandeza ou valor 
do problema. 
 
Como exemplo de minimização, pode-se pensar no problema do 
caixeiro viajante (PCV), onde é necessário definir a melhor rota entre as 
cidades por onde ele pode passar - ainda sim passando por todas pela 
qual ele deve passar. Essa “melhor rota” pode ser a que leva o menor 
tempo, ou a que percorre a menor distância (supondo que tempo não 
seja problema). 
 
Como maximização, pode-se usar como exemplo o número de caixas 
dentro de um container, arranjando-as da melhor maneira possível. Isso 
ajuda diminuindo o custo dos fretes e o volume de cada pedido a ser 
entregue. 
 
Então, uma vez que está definido qual o objetivo (maximizar ou 
minimizar), monta-se uma função (ou uma rotina) que usa os 
parâmetros do indivíduo (genes do DNA) para simular seu 
comportamento. 
Esse “comportamento” pode ser uma saída do sistema simulado, como 
tensão em um ponto do circuito (supondo que a simulação é 
eletrônica), a resistência aerodinâmica (supondo que é um ensaio de 
fluidos, dentro da otimização de um perfil de asa de avião) ou mesmo 
uma tabela, se é feita a adaptação de uma curva a um conjunto de 
pontos. 
Para isso é importante que o programa usado para simular seja capaz 
de realizar simulações em lote ou batelada (Batch simulation, em 
inglês), sem que seja necessário a intervenção do programador 
ordenando cada uma das simulações manualmente. O programa 
portanto, deve ser capaz de, a partir de uma lista de indivíduos, gerar 
automaticamente uma lista de resultados, simulando um de cada vez. 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
28 
 
Ilustração 8 – Fases do AG 
 
Pela figura acima pode-se perceber as fases intermediárias que 
compõem a geração da população inicial e avaliação dos indivíduos. 
A simulação em batelada (lotes) toma um DNA de cada vez da matriz 
de indivíduos, como em uma lista – e também como lista retorna o 
resultado de cada um deles. 
 
É importante destacar que o tempo de simulação e a resolução ou 
precisão da mesma depende do problema a ser resolvido pelo AG. 
Especificar intervalos muito grandes de simulação e/ou uma precisão 
muito alta, sem ser necessário, com certeza irá gerar um AG muito lento 
e pouco prático, já que o tempo total de cada loop de geração do AG 
é a soma do tempo de cada uma das seis etapas já mencionadas. 
 
Por exemplo, na equação de 2º grau anterior, pode-se definir como 
simulação a substituição dos valores de X candidatos a solução para 
encontrar os valores de Y(X). 
 
 
Ilustração 9 - As primeiras fases do laço de gerações do AG 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
29 
Na figura acima se pode perceber a distinção entre as primeiras fases 
do loop de gerações de um AG. 
Primeiro, separa-se um indivíduo para a análise. Passa-se então a fase 
de contextualização, onde esses números guardados no DNA passam a 
ter um sentido prático, a fazer parte de uma equação ou modelo 
matemático a ser simulado. 
Então, calculando o valor da expressão (caixa amarela na figura), é 
encontrado o valor de Y(X1) e Y(X2) – que é a simulação desse modelo. 
 
Claro que esse é um exemplo de simulação de uma equação, mas a 
idéia central não muda para projetos complexos; Para a simulação de 
uma asa , pode-se colocar como genes o ângulo de entrada do perfil, 
o ângulo de saída e o comprimento da asa. Substitui-se esses valores 
nas equações de dinâmica e modelagem de fluidos (contextualização) 
e finalmente simula-se (rodando o interpretador de elementos fluidos 
por exemplo). 
 
Inversamente ou diretamente ? 
 
Ao simular um indivíduo, será retornado um ou mais valores dessa 
simulação. 
Se ao crescer esse valor , o indivíduo perde desempenho (piora em 
relação aos demais), pode-se dizer que seu fitness é inversamente 
proporcional a essa grandeza simulada. 
Mas se ele se comporta melhor, tendo um comportamento mais 
competitivo,então seu fitness é dito diretamente proporcional a essa 
grandeza gerada pelo simulador. 
Pode parecer um conceito trivial, mas influencia diretamente na 
programação do AG. 
 
Um fitness “F” inversamente proporcional a uma grandeza “G” pode ser 
calculado por : 
 
 F = 1 / G ou F= 1/ (nG) Equação 2 
 
 se é desejado acentuar mais a penalização sobre essa grandeza, 
aumentando ‘n’ e assim diminuindo ‘F’ e desfavorecendo os indivíduos 
que a possuem. 
 
O mesmo vale para fitness diretamente proporcional , onde pode ser 
usado: 
 
 F= G ou F= nG Equação 3 
 onde ‘n’ é um fator que incentiva a presença dessa grandeza G entre 
os indivíduos; 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
30 
 Classificação e separação dos melhores 
 
Uma vez que cada um dos indivíduos tenha uma “nota” ou fitness de 
acordo com o desempenho do seu DNA, é chegada a hora de separá-
los e classificá-los, para que “os melhores prossigam e passem seu DNA 
adiante, e os piores sejam descartados ou forçados a tentar se 
adaptar” – Charles Darwin 
 
A classificação é simples : apenas ordena-se os indivíduos com base em 
seu fitness, rearranjando a ordem das linhas na matriz de indivíduos de 
acordo com a classificação, formando um ‘ranking’ de DNA’s. 
Para isso um simples algoritmo de ordenação de listas é suficiente. 
 
Na separação dos melhores podem ser feitas duas abordagens: 
 
Tradicional – onde os indivíduos são sorteados de acordo com seu 
fitness [10] 
 
Elitista – onde os piores são descartados e somente os melhores irão 
receber as operações genéticas a fim de produzir descendentes[2]. 
 
Vendo cada um mais de perto 
 
Na Tradicional, o método feito tem seu funcionamento inspirado no 
sistema de rifas; Aquele que compra mais números, tem também mais 
chance de ser sorteado. Assim, indivíduos com um fitness avantajado 
terão mais chances de serem sorteados para gerar descendentes. 
 
Existem vários problemas implícitos nesse sistema. 
Um deles é que, mesmo tendo um fitness irrisório, indivíduos mal-
adaptados ainda tem chances (mesmo que remotas) de serem 
sorteados e tomar um lugar na matriz de indivíduos da geração 
seguinte, bem como participar das operações genéticas e gerar 
descendentes e perpetuar e misturar na matriz genes ruins que pelo 
Darwinismo já deveriam estar extintos. 
Considerou-se que esse método de seleção é na média, desfavorável a 
sobrevivência dos mais adaptados, indo contra a evolução da 
população. 
Ele se parece em muito com as roletas de cassino, por isso também é 
chamado em várias literaturas de método R-W (Roulette-Wheel ou Roda 
de Roleta). 
Outra desvantagem é que, tendo mais “bilhetes” para serem sorteados, 
indivíduos com fitness várias vezes maiores que a média (super-
indivíduos) geram muito mais filhos. Em poucas gerações a população 
será monótona, e os filhos nada mais serão que cópias ligeiramente 
diferentes dos pai, estagnando a evolução do conjunto. 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
31 
Se um dos ‘pais’ tem um fitness muito maior que os demais, pelo R-W 
praticamente todos os filhos serão cópias do pai, ou variações dele, 
fazendo com que as populações póstumas orbitem em torno desse 
máximo, com uma variação genética mínima. 
 
Em suma, esse comportamento é altamente indesejável, pois 
- Diminui drasticamente a velocidade de evolução, fazendo 
com que o AG leve muito mais gerações para atingir o 
mesmo objetivo 
- Sendo os indivíduos a maioria iguais, todas as possíveis 
mudanças para melhor desta população estão 
depositadas nas mutações. Entende-se que isso aproxima o 
algoritmo muito mais de uma busca randômica do que de 
um AG Clássico. 
- Reduz drasticamente o patrimônio genético da 
população,pois aparecem muitas cópias dos mesmos 
pais.Toda vez que a variabilidade genética é reduzida, o 
espaço de busca é reduzido junto,podendo eliminar 
possíveis soluções que nele estariam. 
- Sendo a escolha randômica, ainda resta a probabilidade 
de um dos melhores da geração não ser escolhido por não 
ser “sorteado” pelo processo. 
 
 
Como exemplo , suponha a seguinte população: 
 
Indivíduo Fitness 
A 18 
B 3 
C 0,6 
D 4 
E 0,3 
F 0,5 
G 3 
H 2 
Tabela 1 – Exemplo de população em AG 
 
Se for usado o sistema R-W, calcula-se a soma de todos os fitness: 
 
Soma-fitness = 18+3+0,6+4+0,3+0,5+3+2 = 31,4 
 
Então é possível calcular quanto cada indivíduo representa na soma, 
dividindo seu fitness pela soma total, por exemplo 
 
Indivíduo A = 18 / 31,4 = 57,3 % 
 
Montando a terceira coluna da tabela seguinte. 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
32 
Agora, é possível distribuir os “bilhetes” para cada indivíduo. Na 
verdade, é feito um fitness acumulado (última coluna da tabela 
seguinte), e dado assim um intervalo (range) para cada indivíduo de 
acordo com seu fitness original. 
 
É gerado um número (como em um sorteio) e o indivíduo que contiver 
esse número dentro do seu range será escolhido para gerar 
descendentes. 
 
Indivíduo Fitness % Fitness Total % acumulado 
A 18 57,3 % 57,3 % 
B 3 9,6% 66,9 % 
C 0,6 2 % 68,9 % 
D 4 12,7% 81,6 % 
E 0,3 1% 82,6 % 
F 0,5 1,6% 84,2 % 
G 3 9,6% 93,8 % 
H 2 6,4 % 100 % 
Tabela 2 – Chances de seleção baseado no fitness 
 
É sorteado um número ao acaso, entre 0 e 100 ; Por exemplo , 70. 
O número 70 está fora do intervalo do indivíduo A , que vai de 0 a 57,3. 
Também está fora do intervalo de B, que vai de 57,3 a 66,9. 
Ele só entrará no intervalo do indivíduo ‘D’, que está entre 68,9 e 81,6. 
Logo , será o indivíduo ‘D’ que , nesse sorteio, irá gerar descendentes. 
 
56%
10%
2%
13%
1%
2%
10%
A
B
C
D
E
F
G
H
 
Ilustração 10 - Distribuição das chances de sorteio nessa população 
 
Percebe-se nesse exemplo, que qualquer número entre 0 e 57,3 irá 
escolher o indivíduo A, o que o torna um “super-indivíduo”. 
Depois de vários sorteios, certamente boa parte da geração seguinte 
será de cópias idênticas ou muito semelhantes a esse indivíduo A. 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
33 
Outro risco implícito é o de o indivíduo A não ser escolhido, 
simplesmente pelos números ‘sorteados’ não compreenderem seu 
intervalo; A chance é pequena, mas ainda é possível. Perder-se-ia um 
excelente indivíduo que poderia ser a solução do problema tratado 
pelo AG. 
 
No sistema Elitista, geram descendentes somente os que tiverem 
melhores fitness. 
 
Os ‘N’ melhores de cada geração são escolhidos e copiados em uma 
matriz a parte, na íntegra. 
 
A matriz contendo os seus descendentes vem das operações de 
cruzamento, mutação e cópia entre eles. 
Assim, considera-se que está sendo favorecida a sobrevivência dos mais 
adaptados, gerando indivíduos cada vez melhores. 
 
A primeira ação a tomar no Elitismo é classificar a população em ordem 
decrescente de fitness: 
 
Indivíduo Fitness 
A 18 
D 4 
B 3 
G 3 
H 2 
C 0,6 
F 0,5 
E 0,3 
 
O programador define então qual é o limiar (critério) de corte: 
 
 - Se é a posição do indivíduo na tabela (escolhem-se os ‘N’ primeiros). 
 - Se é um valor de fitness (como a ‘nota de corte’ em um vestibular). 
 
Escolhendo por posição os 4 primeiros por exemplo, tem-se : 
 
Indivíduo Fitness 
A 18 
D 4 
B 3 
G 3 
 
E serão estes que através de operações genéticas (cruzamento, cópia 
e mutação) irão compor seus descendentes para a próxima geração. 
Os demais que ficaram abaixo do corte, fica a cargo do programador 
escolher o destino deles. Eles podem ser descartados (deixando de 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
34 
fazer parte do sistema) ou podem ser mutados de forma mais agressiva 
e recombinados na tentativa de gerar algum indivíduo aproveitável. 
 
Esse método Elitista também é chamado de método SORT, pois é feito 
uma classificação dos indivíduos (em inglês, sorting) para escolhê-los. 
 
 APLICAÇÃO DE OPERADORESGENÉTICOS CLÁSSICOS [2] 
 
Agora que já estão definidos quais indivíduos irão gerar descendentes, é 
esta a parte do script onde eles irão interagir para gerá-los. 
 
Essa interação é feita através dos operadores genéticos (‘opgen’), 
agindo sobre o DNA dos indivíduos-pais para gerar indivíduos-filhos 
supostamente melhores. 
 
Como prática e regra, copia-se o melhor indivíduo dentre os ‘pais’ pré-
selecionados na íntegra para a geração seguinte, garantindo que ela 
será pelo menos tão boa (fitness tão alto) quanto a geração anterior. 
Essa é uma condição fundamental para a convergência do AG, e vem 
diretamente de sua inspiração natural – na Natureza isso acontece de 
fato, forçando sempre a evolução do conjunto. 
 
Estes operadores se baseiam na genética de Gregorius Mendel, 
conforme mencionado em tópicos anteriores. São eles: 
 
- Cruzamento (cross-over) - onde o DNA do filho será composto por 
uma parte de cada pai. 
Nesse caso, 2 indivíduos daqueles selecionados na etapa anterior serão 
sorteados ao acaso para serem os ‘pais’ através do cruzamento entre 
seus genes. 
 
 
Ilustração 11 – Cruzamento entre indivíduos 
 
Evidente que em genes com apenas 2 loci,não existe outra maneira de 
combiná-los a não ser cruzando-os na metade um do outro, conforme 
figura acima. 
Porém nos demais casos, onde existem DNA’s com mais de 2 posições, 
a posição onde ocorrerá o entrelaçamento dos genes pode ser 
aleatória (como na Natureza, e como feito neste trabalho) ou pré-
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
35 
definida, tomando uma porcentagem de genes de um pai e o restante 
do outro indivíduo-pai. 
Por interagir 2 indivíduos dessa maneira, são gerados 2 descendentes 
em cada cruzamento. 
 
- Mutação - o filho recebe o DNA do pai, mas em algumas posições 
desse DNA ele é alterado aleatoriamente para outro valor. 
Neste caso, apenas 1 indivíduo dentre os pré-selecionados será 
escolhido ao acaso para sofrer a mutação, em uma posição 
igualmente aleatória.Conseqüentemente apenas 1 filho é gerado nessa 
operação. 
 
 
Ilustração 12 – Mutação Tradicional 
 
- Cópia – o filho é uma cópia idêntica do pai 
 
Assim como na mutação, apenas 1 indivíduo dentre os pré-
selecionados será sorteado para ser copiado. Portanto, apenas 1 filho é 
gerado dessa operação. 
 
 
Qual operador genético usar ? 
 
É tradicional na elaboração dos AG criar um laço de repetição na hora 
de gerar os indivíduos-filhos da nova geração. Neste laço, é escolhido 
aleatoriamente um ou dois indivíduos, e ao acaso selecionar qual o 
opgen a usar. 
Essa escolha não é puramente randômica; No começo do AG são 
definidas TAXAS de probabilidade para cada opgen, de modo idêntico 
ao sistema R-W já descrito. 
Quanto maior a taxa de cruzamento, maior será a chance desse opgen 
ser escolhido durante a geração de descendentes.Isso se aplica aos 
outros dois opgens, obviamente. 
 
É comum manter a taxa de cruzamento bem maior do que as demais, 
forçando esse tipo de geração de filhos. Isso é feito pois dentre os 
opgens usados, o cruzamento é aquele que mais diferentes indivíduos 
gera, contribuindo para a diversidade genética e com grandes 
chances de unir os melhores genes de cada pai. 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
36 
Os outros opgen apenas tentam explorar os pontos fortes já existentes 
no indivíduo-pai, ou tentam alterar os pontos negativos do mesmo 
(através da mutação, por exemplo). 
 
Pode-se considerar o cruzamento como um tipo de mutação 
extremamente agressiva, pois ao contrário desta última, costuma alterar 
pelo menos metade dos genes do indivíduo-filho de uma só vez. Na 
mutação, apenas 1 gene dentro do DNA é alterado. 
 
John Koza [12] costuma defender a seguinte proporção nas taxas de 
opgen: 90 % cruzamento, 9 % de cópia e 1% de mutação. 
 
Com taxa de cruzamento muito baixas,muitas rodadas ficam mesmo 
sem nenhuma alteração. 
Esse fato fica agravado com populações menores, e é mascarado em 
grandes populações, pois existem tantos genes diferentes que qualquer 
cruzamento se torna equivalente a uma mutação.E mais, uma mutação 
maciça já que, ao contrário da mutação convencional , mais de um 
gene é alterado de uma só vez. 
 
Uma quantidade exorbitante de cruzamentos também não é desejável, 
já que o patrimônio genético fica várias gerações rodando em torno 
dos indivíduos já existentes.Isso na prática se reflete como uma menor 
velocidade de convergência, fazendo com que o fitness caminhe 
lentamente até o melhor possível dentro desse patrimônio.Todavia, não 
é garantido que o AG irá encontrar o ótimo global dentro do número 
de gerações determinado (ou mesmo que ele chegue a encontrar um 
dia esse máximo) devido à baixa variabilidade genética – risco esse 
agravado em pequenas populações. 
 
As cópias são a parte do AG que mantém a curva monotônica e 
crescente, garantindo que a geração seguinte seja pelo menos tão 
boa quanto a anterior.A ausência dessa taxa faz com que o AG se 
torne instável e não-monotônico, como a figura já mostrada. 
 
Taxas excessivamente altas de cópia mantém a curva de fitness f(g) 
(onde ‘g’ é a geração) ainda monotônica e crescente.Porém deixa 
toda a tarefa de melhora de fitness a cargo das ínfimas taxas de 
mutação e cruzamento. E para pequenas populações, pequenas taxas 
de cruzamento NÃO representam melhora significativa, uma vez que o 
patrimônio genético sempre acaba oscilando ao redor do que já existe. 
 
Donde podemos concluir que para populações pequenas, a mutação 
é muito importante, e altas taxas de cópia podem simplesmente 
estagnar o processo evolutivo.Por sua vez, grandes taxas de cruzamento 
resultam em uma desaceleração no fitness, e comprometem a 
capacidade primordial do AG de encontrar os máximos globais. 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
37 
Usar grandes taxas de mutação (para garantir variedade),baixas taxas 
de cópias (para garantir estabilidade) e baixos índices de cruzamento 
(para não desacelerar o processo) 
parecem uma boa alternativa.Todavia, isso recai em uma busca 
estocástica ou uma variante da “busca tabu”, e não mais temos os AG 
como foco. 
 
As três taxas distribuídas igualmente (33%) apresentam bons resultados. 
 
Então encontramos os papéis de cada operador genético (opgen): 
 
Cópia � garante a estabilidade do sistema, e garante uma geração 
seguinte com fitness pelo menos igual ao melhor da geração 
anterior.Sem cópia, o sistema não retém os bons resultados atingidos, e 
simplesmente não converge.Taxas muito altas,entretanto, diminuem 
sensivelmente a velocidade de convergência ,e fazem com que sejam 
necessárias várias gerações (mais da metade, em geral) para que 
alguma mutação ou cruzamento alterem algum dos poucos indivíduos 
que não foram copiados da geração anterior. 
 
Mutação � Garante a variedade genética da população.É responsável 
pelos saltos qualitativos do fitness.De maneira geral, a mutação acelera 
o processo evolutivo.Porém taxas muito altas levam o AG a se 
comportar como uma busca aleatória, diminuindo novamente a 
velocidade de convergência .Taxas muito baixas levam o sistema à 
estagnação, pois não há patrimônio genético suficiente para gerar 
novos indivíduos somente por cruzamentos.Há uma boa resposta em 
taxas de mutação entre 20 e 40 % (empírico). 
 
Cruzamentos � Também tem como função aumentar a variedade 
genética do grupo, porém ao contrário da função Mutação, não o faz 
de modo aleatório.Na verdade, esse operador realiza uma mutação 
orientada, partindo da premissa que os filhos gerados de pais fortes 
serão tão ou mais fortes que seus progenitores – o que se mostra real em 
boa parte das vezes. 
Em populações com uma variedade genética grande, o cruzamento 
funciona como uma mutação muito mais agressiva,já que a maior 
parte dos genes (pelo menos a metade) é substituída de uma só 
vez.Também deve ter sua taxa controlada para evitar estagnação,já 
que muitoscruzamentos em uma mesma geração tendem a aumentar 
a freqüência de certos genes, diminuindo a variabilidade genética e 
conseqüentemente, a velocidade de evolução. 
 
 
 
 
 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
38 
Em pseudo-código, essa parte do AG poderia ser descrita como: 
 
Para ‘i’ entre 1 e ‘total_de_escolhidos’ faça 
 
 Pai_1  aleatório() * total_de_escolhidos 
 Pai_2  aleatório() * total_de_escolhidos 
 
 Opgen  aleatório() * 100 
 Se ‘opgen’ está entre 0 e TAXA_CRUZAMENTO então 
 
 Pos_corte  aleatório() * TAMANHO_DNA 
 
 Filho_1  corte(Pai_1 , Pos_corte) 
+corte(Pai_2,TAMANHO_DNA - Pos_corte) 
 Filho_2  corte(Pai_2 , Pos_corte) 
+corte(Pai_1,TAMANHO_DNA - Pos_corte) 
 
 
 Fim_se 
 
 Se ‘opgen’ está entre TAXA_CRUZAMENTO e TAXA_COPIA então 
Posição  aleatório() * TAMANHO_DNA 
Novo_valor  aleatório() 
 Filho_1  muda_gene(Pai_1 , Posição , novo_valor) 
 Fim_se 
 
 Se ‘opgen’ está entre TAXA_COPIA e 100 então 
 
 Filho_1  Pai_1 
 
 Fim_se 
 
Nova_geração (i)  Filho_1 
Se ‘Filho_2’ é diferente de 0 então 
Nova_geração (i+1)  Filho_2 
I  i +1 
 Fim_se 
 
Fim_para 
 
 
 
Esse laço se repete até que toda a matriz de indivíduos da nova 
geração esteja completa. 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
39 
5. A MUTAÇÃO DIFERENCIAL CONDICIONAL 
 
5.1. Mutação Tradicional e Mutação Diferencial 
 
Na mutação tradicional, um determinado indivíduo, quando escolhido 
para ser mutado, tem um dos seus genes substituído por um outro valor 
randômico, gerado ao acaso. Essa operação tende a gerar alguns 
picos isolados ao redor da população, mas em menor número que o 
cruzamento, pois ele muda um gene de cada vez, e sem nenhuma 
orientação (heurística). 
 
Muitas vezes, a população chega ao redor de um ponto ótimo, um vale 
ou um pico do espaço de busca, e não consegue atingir o topo ou o 
fundo desse pico ou vale. 
 
O AG não consegue pois a diferença entre o pico/fundo é geralmente 
muito pequena, da ordem de décimos ou centésimos. Qual operador 
genético seria capaz de alterar o DNA do melhor indivíduo somente 
alguns décimos , só o suficiente para atingir o máximo global ? 
 
O cruzamento, troca muitos genes de uma vez, sendo assim pouco 
provável que exista um outro indivíduo com o gene ideal , alguns 
décimos maior ou menor , para efetuar a troca. Também é pouco 
provável que o AG sorteie a posição exata daquele gene para efetuar 
a troca. 
 
A cópia não resolve nada. Apenas continua mantendo o melhor 
indivíduo onde já está. 
 
A mutação parece uma boa candidata, já que altera um gene de 
cada vez. Todavia, existe um porém : é necessário uma certa “sorte” 
para que , ao gerar um número completamente aleatório, ele seja 
exatamente alguns centésimos maior que o melhor indivíduo. 
E se for, a posição onde será inserido esse gene randômico também é 
igualmente randômica. 
 
Isso faz com que, uma vez ao redor desse pico ou vale, o AG fique 
estagnado orbitando ao redor deles, sem nunca atingi-los, apenas 
aguardando o momento em que ocorrerá um fato raro em que a 
mutação ou cruzamento irá causar essa variação de décimos. 
No gráfico de fitness por gerações, isso representa os trechos onde a 
curva se mantém horizontal, sem nenhuma alteração, como na figura a 
seguir: 
 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
40 
 
Ilustração 13 – Gráfico de fitness por gerações 
 
Para contornar esse problema, foi pensada a mutação diferencial. 
 
O raciocínio básico é adicionar um valor pequeno ao gene sorteado 
para sofrer mutação, e assim variá-lo um mínimo possível, apenas para 
que seja levemente diferente do seu original, ou seja 
 
 Gene  Gene + dG Equação 4 
 
Onde ‘dG’ é uma variação decimal ou centesimal a ser acrescida e/ou 
subtraída – sim, pois há problemas em que um aumento no valor do 
gene seja prejudicial. 
 
Esse tipo de mutação é chamada de ‘CREEP’ ou “escorregamento”. 
 
Uma alternativa é multiplicar-se o valor do gene por um número 
aleatório próximo a 1 (para mais ou para menos). 
 
Este operador é aplicado no caso da representação real e não gera 
grande perturbação nas populações. Isto permite que seja usado com 
taxas de mutação mais elevadas. 
O efeito da mutação em creep auxilia na busca local (exploitation ou 
“aprofundamento”) pois parte da idéia de que se um cromossomo está 
perto de um valor ótimo uma pequena alteração pode levá-lo ao 
ótimo. 
 
Mas resta a pergunta ? Trocar a mutação tradicional por diferencial 
sempre ? 
Realizando diversas simulações, percebe-se que usando somente a 
mutação diferencial a população não cresce (evolui) como deveria, 
pois novos genes não são criados – o cruzamento cria novos DNA’s, mas 
não novos genes – são apenas ligeiramente diferidos, não o suficiente 
para contribuir a todo momento com a evolução. O opgen capaz de 
criar genes com valores inteiramente novos é a mutação tradicional. 
 
Além das ferramentas de análise de desempenho e ferramentas 
evolutivas, a principal novidade deste trabalho é a indicação da 
mutação diferencial condicionada ou Triggered (disparada por gatilho). 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
41 
MUTAÇÃO DIFERENCIAL CONDICIONADA 
 
A mutação tradicional cria genes com valores inteiramente novos. 
Porém , como já foi discutido anteriormente , durante as gerações 
muitas dessas mutações não são efetivas, ou seja, não melhoram o 
fitness da população, apesar de aumentar o patrimônio genético da 
mesma (o que pode levar a uma evolução mais tarde em um 
cruzamento , por exemplo). 
 
Aparecem então grandes períodos de ‘marasmo’, uma inatividade 
evolutiva, mantendo a curva de fitness horizontal. 
 
A mutação diferencial (creep) tem como característica o 
aprofundamento da busca local, explorando regiões bem próximas do 
ponto original. Isso certamente retorna (ainda que pequenas) melhorias 
no fitness do indivíduo mutado. 
 
A fim de eliminar ou ao menos minimizar esses períodos de estagnação 
evolutiva, surge então a proposta do autor em usar a mutação 
diferencial condicional, cuja proposta é usar a abordagem diferencial 
nas mutações somente quando a evolução se mostrar estagnada por 
mais de um determinado número de gerações.Assim que esse marasmo 
é quebrado e a curva volta a crescer, as próximas mutações voltarão a 
ser do modo tradicional. 
 
Vendo o gráfico da derivada do fitness em relação às gerações (fig.15 em 
baixo),vemos que com essa abordagens temos bem mais picos de 
mudança do que as abordagens tradicionais (figura 14, em baixo). 
 
 
Ilustração 14 - Usando a mutação diferencial condicionada 
Mutação Diferencial Condicional como proposta de otimização de Algoritmos Genéticos 
42 
 
 
Ilustração 15 - Usando a mutação tradicional somente 
 
É possível perceber que depois de um certo começo das gerações, a 
população na população com mutação tradicional entra em 
estagnação, ficando assim a maior parte do tempo, apenas 
desperdiçando tempo de processamento. 
Já na figura com uso de mutação diferencial (no caso, a 
condicionada), percebe-se muito mais picos no gráfico de delta-fit 
(variação do fitness) e um crescimento mais constante. 
Usando um pseudo-código, poder-se-ia montar um exemplo do 
segmento de código responsável pela mutação: 
 
Se ‘Maior_fit(g)’=‘Maior_fit(g-1)’= ‘Maior_fit(g-2)’ então 
 
 Gene  gene + ( aleatorio() – aleatorio() ) /100 
Fim_se 
 
Senão, faça 
 
 Gene  aleatorio() 
Fim_senão 
 
No código acima, ‘Maior_fit’ representa uma lista contendo o maior 
fitness de cada geração, indexada por ‘g’ ; Se houver uma estagnação 
por mais de 3 gerações , ele irá usar a mutação diferencial, que no caso 
aparece somando e subtraindo dois valores randômicos, para que haja 
a possibilidade de haver um resultado negativo que diminua o gene. 
Também essa subtração está dividida por 100, pois nesse caso deseja-se 
alterar os centésimos do gene.