Algoritmo Genético e Evolução

Prévia do material em texto

O Algoritmo Genético
O algoritmo genético é uma técnica de busca atra-
vés de configurações e foi originalmente formulado
usando os mecanismos da evolução e da genética natural.
Este algoritmo foi inventado por Holland na década de
70.
A evolução das espécies está determinada por um pro-
cesso de seleção que leva à sobrevivência dos indiv́ıduos
genéticamente melhor adaptados para superar os prob-
lemas do meio ambiente que geralmente são variáveis.
O conceito de geneticamente melhor adapta-
do tem um valor relativo porque depende do
fator problemático que existe no meio ambi-
ente. Por exemplo, supor que existe uma população de
gazelas com 3 caracteŕısticas genéticas e com duas pos-
sibilidades em cada caso: gazelas de pescoço curto ou
comprido, gazelas que correm muito ou pouco, e gazelas
que apresentam anticorpos para uma doença ou que não
apresentam esse anticorpo. Nesse contexto, se no meio
ambiente ocorrem vários anos de seca então sobrevivem
as gazelas de pescoço comprido porque elas são geneti-
camente melhor qualificadas para o problema cŕıtico ex-
istente no meio ambiente.
1
O aparecimento de um excesso de predadores e o aparec-
imento da doença podem levar a novas gerações, onde
deve existir uma população de gazelas constitúıdas basi-
camente de gazelas com pescoço comprido, com anticor-
pos para a doença e com grande capacidade para cor-
rer. Todas as outras caracteŕısticas desaparecem com a
morte daquelas gazelas que tinham essas caracteŕısticas
genéticas. Assim, as mudanças do meio ambiente
determinam, de maneira significativa, a mu-
dança na composição genética dos elementos
de uma população.
Os elementos da população genéticamente melhor qual-
ificados têm maior possibilidade de chegar a adultos e
gerar descendentes, transmitindo suas caracteŕısticas genéticas
para os descendentes e aumentando essas caracteŕısti-
cas genéticas na população. Neste processo, existe uma
componente aleatória muito importante na geração dos
indiv́ıduos da nova população. Por exemplo, uma gazela
que corre muito pode ser caçada.
Para que exista seleção devem existir in-
div́ıduos genéticamente diferentes. A diferença
genética entre os indiv́ıduos de uma população pode
ser explicada pela teoria de Darwin. Existe diversidade
genética pelos seguintes motivos:
2
1. Divisão e Duplicação de Células Reprodutivas:
A informação genética se encontra nos cromossomos
que, no caso da espécie humana, consistem em 23
pares de cadeias de cromossomos. Cada par de cro-
mossomos gêmeos trabalham de maneira conjunta
na determinação de uma caracteŕıstica genética. Um
cromossomo é constitúıdo por uma sequência de unidades
mais elementares chamadas de genes . Assim, em
cada elemento do cromossomo, chamado de gene, ex-
iste uma informação genética dominante que é conse-
quência da informação existente em cada cromosso-
mo gêmeo do par cromossômico. O tipo espećıfico
de informação existente no gene é chama-
do de alelo. Portanto, um gene está consti-
túıdo por 2 alelos, um alelo em cada cro-
mossomo gêmeo.
3
Geralmente, um dos alelos é dominante sobre o out-
ro e assim aparece o conceito de genótipo como
uma indicação dos tipos de alelos existentes e a in-
formação do alelo dominante. O genótipo, determi-
nado pelo tipo de gene, determina um fenótipo
que é a caracteŕıstica visual ou seletiva no indiv́ıduo.
Por exemplo, o tipo de sangue das pessoas (fenótipo)
é determinado por um tipo de alelo dominante (genótipo)
e como conseqüência aparecem pessoas com dois fenó-
tipos: pessoas de sangue Rh+ e Rh−. Por outro la-
do, o grupo sangúıneo é determinado por outro gene
onde, na espécie humana, existem 3 tipos de alelos
sendo que dois deles estão presentes numa pessoa es-
pećıfica. Assim, dependendo dos tipos de alelos pre-
sentes numa pessoa, aparecem os fenótipos de grupo
sangúıneo A, AB, B e universal. Logicamente, emb-
ora existam vários tipos de alelos na espécie humana
para definir o grupo sangúıneo, em uma pessoa par-
ticular existem somente dois tipos de alelos, um em
cada cromossoma gêmeo, e esses alelos podem ser do
mesmo tipo.
4
K2
K1
P1
P1
S2
S1
︸ ︷︷ ︸
?
6
�
� cromossomo
herdado do pai
cromossomo
herdado da mãe
alelo
alelo
gene
Dois cromossomos gêmeos.
5
Na divisão celular de uma célula reprodutiva, primeiro
acontece uma separação e duplicação dos cromosso-
mos gêmeos (e da cadeia cromossômica). Assim, por
exemplo, uma célula reprodutiva masculina gera 4
espermatozóides (gametas) sendo que um esperma-
tozóide representa uma meia célula que depois pode
se juntar com um ovulo (outra meia célula) para for-
mar o ser humano mais elementar, chamado de zig-
oto. Assim, o zigoto é a união de duas meias células
que se complementam e permitem recuperar, nova-
mente, os 23 pares de cromossomos gêmeos. A for-
ma em que a célula reprodutiva se separa
e se duplica representa a principal fonte
de diversidade genética e, nesse processo,
acontece o fenômeno chamado de recombi-
nação genética ou crossing over (crossover).
Outra fonte de diversidade genética, menos impor-
tante, é a reprodução sexuada formal, isto é, a união
de dois gametas de pessoas com caracteŕısticas genéticas
diferentes. Essas fontes de diversidade genética são
analisadas em separado.
6
2. O Fenômeno de Crossing Over (Recombinação Genética)
Quando dois cromossomos gêmeos se separam no
processo de divisão celular de uma célula reprodu-
tiva acontece o chamado fenômeno de crossing over
ou de recombinação genética. Por exemplo, a espécie
humana tem 23 pares de cromossomos onde exis-
tem dezenas de milhares de genes. Para ilustrar este
fenômeno centramos a análise num par de cromosso-
mos gêmeos, chamados A e B, de uma pessoa. Assim,
o cromossomo A foi herdado do pai e o cromossomo
B da mãe. Quando a célula reprodutiva se separa e se
duplica podemos imaginar que são gerados gametas
A e B exatamente como foram herdados dos pais.
Entretanto, foi descoberto que não é exatamente isso
que acontece na natureza. Na verdade, cada gameta
gerado tem parcelas do cromossomo A e B. Portan-
to, antes da separação, os cromossomos A e B se re-
combinam, trocando parcelas de genes de tamanho
variado numa forma que ainda não está claramente
explicada.
7
O resultado desse processo é a produção de gametas
que possuem parcelas dos cromossomos gêmeos A e B
numa forma diversificada e diferentes umas das out-
ras. Este fenômeno (crossing over) faz com
que sejam gerados gametas de caracteŕısti-
cas muito diferentes numa mesma pessoa.
A maneira de ilustração, supor que a cadeia cro-
mossômica do ser humano apresenta 100000 genes,
que em cada gene existem 2 tipos de alelos e exis-
tem 10.000 pontos prováveis de recombinação, então
é posśıvel gerar em torno de 210000 gametas difer-
entes, um número realmente grande e que mostra
a importância do fenômeno de crossing over na for-
mação da diversidade genética de uma espécie. Obvi-
amente, existem genes com alelos iguais o que diminui
o número de gametas diferentes e também não se con-
hece o número de pontos de recombinação. Entretan-
to, lembramos que o famoso número 264 já é absur-
damente grande.
8
3. A Reprodução Sexuada:
A reprodução sexuada é outra fonte de diversidade
genética entre os indiv́ıduos de uma espécie. A união
de dois gametas de pessoas diferentes contribui na
geração de zigotos de caracteŕısticas genéticas difer-
entes. Entretanto, dois zigotos de um mesmo
casal seriam genéticamente muito próximos
sem a presença do fenômeno de crossing
over. Portanto, a reprodução sexuada não é uma
grande fonte de diversidade genética. Logicamente,
o crossing over é um fenômeno que acontece com
espécies de reprodução sexuada mas é um fenômeno
que acontece no processo de divisão celular.
9
A análise apresentada é, obviamente, superficial porquenão foram analisados outros aspectos importantes
que acontecem na natureza. Na natureza existem
seres vivos unicelulares e de reprodução assexuada.
Também existem seres vivos que se desenvolvem so-
mente a partir dos gametas (meia célula) como acon-
tece em vários tipos de plantas. Existem também
fenômenos mais complexos na determinação das car-
acteŕısticas genéticas. Por exemplo, existe o fenômeno
conhecido como pleiotropia onde um simples gene
pode controlar simultaneamente várias caracteŕısti-
cas fenot́ıpicas, assim como o fenômeno de poligênia
onde uma simples caracteŕıstica fenot́ıpica é contro-
lado pela ação simultânea de vários genes. Final-
mente existem espécies com cadeias cromossômicas
menos complexas que a espécie humana. Assim, apare-
cem perguntas do tipo: Qual dos seres vivos são os
mais evolúıdos e/ou adaptados na natureza (na ter-
ra)?.
10
Existe ainda outra fonte de diversidade genética, con-
siderada secundária, chamada de mutação. A mutação
acontece na interação dos seres vivos com a natureza.
Assim, podem aparecer mudanças na estrutura de um
gene produzindo uma modificação da função do gene e
do correspondente fenótipo.
Holland analisou o fenômeno da evolução
natural das espécies e encontrou semelhanças
deste processo com o processo de solução de
problemas grandes e complexos. Assim, o algorit-
mo genético inventado por Holland gera uma seqüência
de populações (conjunto de configurações ou soluções)
usando os mecanismos de seleção, recombinação e mu-
tação como mecanismo de busca (operadores genéticos)
através do espaço de configurações de um problema com-
plexo.
11
Esta seção termina analisando a palavra crossover.
Crossover foi uma palavra usada por Holland para in-
dicar o fenômeno de crossing over, isto é, a recombinação
genética que acontece no processo de divisão celular de
células reprodutivas no organismo de um indiv́ıduo. As-
sim, do ponto de vista genético, crossover não tem relação
direta (tem relação indireta) com reprodução sexuada.
Existem publicações onde se traduz crossover como cruza-
mento e, ‘as vezes, cruzamento é interpretado como re-
produção sexuada sendo comum usar termos do tipo
“cruzamento de dois pais que geram dois descendentes
ou filhos”. Frases desse tipo não fazem sentido dentro do
contexto de crossover genético. Autores de livros moder-
nos evitam o uso da palavra crossover e usam a palavra
recombination que traduzido seria equivalente a recom-
binação. Portanto, no resto do livro é usada a
palavra recombinação (genética) como sendo
a tradução da palavra crossover ou, melhor
ainda, de recombination.
12
Algoritmo Genético e Seleção
Natural
Na natureza, os indiv́ıduos melhores qualificados ge-
neticamente têm maiores possibilidades de sobrevivência
quando os recursos são escassos e/ou quando mudam
as condições do meio ambiente. Melhor qualificado sig-
nifica melhor capacidade de sobrevivência e, em última
instância, esta qualidade ou capacidade é determinada
pelo conteúdo genético de cada indiv́ıduo. Como já foi
mencionado, a unidade básica de informação genética
é o gene. O conjunto de genes forma o cromossomo ou
conjunto de cromossomos que determina a qualidade de
um indiv́ıduo.
As mudanças e a diversificação do materi-
al genético constitui a essência da evolução.
Assim, pode-se dizer que a evolução é uma conse-
quência da ação conjunta da seleção natural e
dos mecanismos que produzem a diversidade
genética analisados anteriormente.
13
Na natureza, os indiv́ıduos competem por problemas
de alimentos, espaço, doenças e, também, de acasala-
mento produzindo um predomı́nio dos indiv́ıduos mais
qualificados. Portanto, somente os indiv́ıduos melhor qual-
ificados sobrevivem e se reproduzem repassando seus
genes melhor qualificados para as seguintes gerações. O
processo, repetido de seleção no meio de uma grande di-
versidade genética é a chave da evolução segundo Darwin
e seus seguidores, em outras palavras, sem essa grande
diversidade genética que existe entre os indiv́ıduos de
uma população, seria dif́ıcil o processo de evolução das
espécies.
14
O AG usa uma população de indiv́ıduos que são um
conjunto de configurações, para resolver um problema
de otimização complexo. Portanto, o AG faz seguinte:
1. Representa adequadamente uma configuração do
problema. A representação mais popular é a repre-
sentação em codificação binária onde são facilmente
simulados os operadores genéticos de recombinação
e mutação.
2. Avalia a função objetivo ou seu equivalente (fit-
ness value). Assim, as melhores configurações são
aquelas que apresentam funções objetivo de melhor
qualidade.
3. Faz seleção das configurações com direito a partic-
ipar na conformação das configurações da nova pop-
ulação.
4. Implementa o operador genético de recombinação.
5. Implementa o operador genético de mutação.
6. Deve-se especificar o tamanho da população, isto é,
o número de configurações em cada geração e taxas
de mutação e recombinação.
Uma vez especificados todos esses aspectos para um
problema espećıfico, então dizemos que foi implementa-
do um algoritmo genético básico (AGB).
15
Algoritmo Genético Básico
Nesta seção são analisadas, em detalhe, as principais
caracteŕısticas de um algoritmo genético básico (AGB).
Para ilustrar as caracteŕısticas fundamentais de um AGB
usamos um exemplo do problema da mochila.
Exemplo 7.1: O problema da mochila
Seja o problema da mochila para n = 12 mostrado a
seguir:
16
max z(x) = 3x1 + 2x2 + 8x3 + 4x4 + 6x5 + 4x6 + 12x7+
2x8 + 6x9 + 10x10 + 15x11 + 9x12
s.a.
5x1 + 4x2 + 4x3 + 2x4 + 4x5 + 6x6 + 10x7+
4x8 + 2x9 + 8x10 + 12x11 + 5x12 ≤ 36
xj ∈ {0, 1}, j = 1, . . . , 12.
Os vetores de trabalho podem ser facilmente identifi-
cados:
5 4 4 2 4 6 10 4 2 8 12 5
3 2 8 4 6 4 12 2 6 10 15 9
36≤Volume: a =
Custo: c =
Este exemplo deve ser usado para ilustrar a implemen-
tação do AGB.
17
Algoritmo Genético Elementar
Um algoritmo genético elementar realiza a seguinte
seqüência de operações:
1. Gera a população inicial após escolher o tipo de cod-
ificação.
2. Calcula a função objetivo de cada configuração da
população e, armazena e atualiza a incumbente (mel-
hor configuração encontrada durante o processo).
3. Implementa a seleção.
4. Implementa a recombinação.
5. Implementa a mutação e termina de gerar a popu-
lação da nova geração.
6. Se o critério de parada (ou critérios de parada) não
for satisfeito, repetir os passos 2 a 6.
O conjunto de passos de 2 a 5 é conhecido como ciclo
geracional.
18
Também é necessário mencionar que existe a seguinte
equivalência entre os termos usados na genética e no
problema de otimização matemática:
Problema de otimização ⇐⇒ genética
Solução (configuração) ⇐⇒ cromossomo
Variável ⇐⇒ gene
Solução (Valor das variáveis{0, 1}) ⇐⇒ alelo
A seguir são analisadas todas as etapas do AGB us-
ando exemplos ilustrativos.
19
O Problema da Codificação
A forma de implementar a codificação depende, entre
outros aspectos, da natureza das variáveis de decisão do
problema ou da forma de representar uma configuração
do problema. Existem problemas com variáveis binárias
(que são os mais simples de representar ou codificar),
com variáveis inteiras e com variáveis reais.
Os primeiros algoritmos genéticos usaram
basicamente codificação binária, ou seja, as
variáveis inteiras e reais de um problema são
transformadas, de alguma maneira, em codifi-
cação binária. Neste contexto, pode-se tentar
realizar codificação binária de vários tipos de
variáveis. Este problema é ilustrado através
de exemplos.
20
Problemas com Variáveis Binárias
Este caso é o mais trivial e a codificação é muito sim-
ples.
Exemplo 7.2: Realizar codificação binária de um
problema com 3 variáveis:x1, x2, x3 ∈ {0, 1}.
Neste caso trivial, onde as variáveis são naturalmente
binárias, uma configuração com codificação binária as-
sume a seguinte forma:
x1 x2 x3x =
e um caso particular assume a seguinte forma:
1 0 1x = ⇐= uma configuração
21
Problemas com Variáveis Inteiras
Este caso ainda é trivial e a codificação é relativamente
simples.
Exemplo 7.3: Realizar codificação binária de um
problema com 3 variáveis: x1, x2, x3 ∈ {0, 1, 2, 3, 4, 5, 6, 7}.
Neste caso, cada variável inteira pode ser represen-
tada por seu equivalente binário e ocupando três casas
binárias na codificação binária. Assim, uma configuração
t́ıpica assume a seguinte forma:
1 0 0 0 1 0 1 1 1
x1 x2 x3
⇑ ⇑ ⇑
x =
︸ ︷︷ ︸ ︸ ︷︷ ︸ ︸ ︷︷ ︸
que neste caso particular representa os números inteiros
x1 = 4, x2 = 2 e x3 = 7.
22
Neste tipo de codificação aparecem os primeiros
problemas que acontecem quando se deseja codificar
uma variável inteira como xj ∈ {0, 1, 2, 3, 4, 5}. Nesse
caso a proposta de codificação anteriormente mostra-
da apresenta problemas porque se são usadas 3 casas
binárias para representar xj então existe a possibilidade
de que, em algum momento posterior (após recombi-
nação ou mutação), xj assuma valores infact́ıveis como
6 e 7. Este problema é mais complicado quando se dese-
ja codificar variáveis reais variando num intervalo como,
por exemplo, xj ∈ [−3, 25 ; 6, 10]. Este problema foi
contornado usando uma estratégia diferente que é apre-
sentada na codificação de variáveis reais.
23
Problemas com Variáveis Reais
Este caso mais complexo é mostrado através de um
exemplo.
Exemplo 7.4: Realizar codificação binária para re-
solver o seguinte problema:
max f(x) = x sen(10πx) + 1
para−1 ≤ x ≤ 2, usando algoritmos genéticos. Pretende-
se encontrar a solução com uma aproximação de 6 d́ıgitos
significativos após a v́ırgula.
É um problema com uma única variável. Para o inter-
valo de x ∈ [−1, 2] e para uma aproximação de 6 d́ıgitos
após a v́ırgula, deve-se dividir o intervalo de variação
de x em 3 × 106 intervalos, em outras palavras, são
necessários 3×106 números binários. Portanto, são necessários
números binários com 22 bits porque:
2097152 = 221 < 3000000 < 222 = 4194304
24
Neste caso, cada número binário representa uma variável
x
′
de acordo com a seguinte relação:
x
′
= [b21 b20 . . . bo] =
21∑
i=0
bi2
i
e a variável original x é representada da seguinte forma:
x = −1, 0 +
3
222 − 1
x
′
onde 222 − 1 é o número de intervalos. Em geral, para
uma representação com n bits binários existem 2n − 1
intervalos porque:
20 + 21 + 22 + . . . + 2n = 2n − 1
Uma configuração t́ıpica, em codificação binária, pode
assumir a seguinte forma:
1000101110110101000111 =⇒ x = 0, 637197
O leitor já deve ter observado a grande dificuldade
de realizar codificação binária de variáveis reais quan-
do o número de variáveis reais cresce para centenas ou
milhares de variáveis. Aparecem evidentes problemas de
manipulação e de memória.
25
Problemas da Codificação Binária
A codificação binária de variáveis inteiras ou reais
apresenta diversos tipos de problemas. A principal
justificativa de realizar codificação binária de
variáveis inteiras ou reais é que a teoria básica
de algoritmos genéticos, especialmente na im-
plementação dos operadores genéticos de re-
combinação e mutação e as caracteŕısticas de
convergência, foi desenvolvida para a codifi-
cação binária. Outra justificativa óbvia é que a cod-
ificação binária imita os dois tipos de alelos existentes
num gene de um cromossomo. Entretanto a codificação
binária de variáveis não binárias apresenta muitos prob-
lemas. Esses problemas e as formas encontradas para
contornar esses problemas, pelo menos parcialmente, são
mostrados a seguir.
26
Quando variáveis inteiras são representadas em cod-
ificação binária aparecem vários problemas. Um desses
problemas, pouco analisado pelos especialistas, é mostra-
do usando o exemplo 7.3. Pretende-se realizar a codifi-
cação binária para a configuração (solução) com x1 = 4,
x2 = 2 e x3 = 7. A codificação binária dessa configu-
ração assume a seguinte forma:
1 0 0 0 1 0 1 1 1
x1 x2 x3
⇑ ⇑ ⇑
x = ⇐= codificação
binária︸ ︷︷ ︸ ︸ ︷︷ ︸ ︸ ︷︷ ︸
?
y
27
Uma alternativa de codificação de variáveis inteiras
consiste em representar cada variável inteira numa casa
decimal. Assim, a configuração anterior é representada
da seguinte forma:
4 2 7
x1 x2 x3
x = ⇐= codificação decimal.
Neste contexto, a codificação binária apresenta com-
portamentos at́ıpicos quando é implementado o operador
de recombinação e de mutação. Para a recombinação
supor, por exemplo, que a configuração mostrada deve
ser recombinada com outra configuração com valor de
x1 = 3 que corresponde a 011 na codificação binária e
que o ponto de recombinação é indicado pela seta na
codificação binária. Em outras palavras, o ponto de re-
combinação está no limite entre a primeira e segunda
casa binária de x1. Após a recombinação o valor de x1
passa de 4 para 7 numa das configurações e de 3 para 0
na outra configuração. Portanto, em relação a x1 acon-
teceu uma mutação violenta após a recombinação. Em
outras palavras, quando é realizada a recombinação de
configurações de variáveis inteiras representadas em cod-
ificação binária podem acontecer mutações violentas de
uma variável no ponto de recombinação.
28
Obviamente, se o ponto de recombinação for, por ex-
emplo, a fronteira entre x1 e x2 então não acontece este
problema. Entretanto, nesse caso, a implementação de
recombinação na codificação binária e na decimal seri-
am totalmente equivalentes. Portanto, uma alternativa
para a codificação binária de variáveis inteiras consiste
em realizar a codificação decimal que não apresenta os
problemas antes mencionados na implementação da re-
combinação e apresenta a grande vantagem de evitar
transformações de binário a decimal e vice-versa além
de usar menor memória.
29
A mutação também apresenta comportamen-
to at́ıpico na codificação binária de variáveis in-
teiras. Supor, por exemplo, que é implementada mu-
tação na codificação binária mostrada anteriormente na
posição indicada por •. Assim, a variável x3 passa de 7
para 4 após a mutação acontecendo, também, uma mu-
tação violenta. Pode-se concluir que existem vantagens
evidentes ao evitar a codificação binária de variáveis in-
teiras. Entretanto, deve-se redefinir o operador de mu-
tação. Existem várias formas de redefinir o operador de
mutação e a mais simples consiste em incrementar ou
diminuir numa unidade o valor corrente da variável in-
teira xj. Assim, por exemplo, se xj = 2, a mutação mu-
da o valor de xj para 1 ou para 3. Obviamente, deve-se
respeitar os limites de xj ao implementar essa nova mu-
tação. Eventualmente, pode ser necessário incrementar a
taxa de mutação para “compensar” a falta de mutações
violentas que acontecem na recombinação e mutação de
variáveis inteiras representadas em codificação binária
ou ainda, pode-se definir mutações duplas, triplas, etc.
Entretanto, mutações violentas não fazem sentido dentro
da lógica da evolução natural que é a base fundamental
dos algoritmos genéticos.
30
Para terminar de ilustrar as formas de codificação
binária e decimal de variáveis inteiras, sejam as configu-
rações P1 e P2 do exemplo 7.3 mostradas a seguir:
0 1 1 1 1 0 0 1 1
1 0 0 0 0 1 1 1 0
x1 x2 x3
⇑ ⇑ ⇑
P2 :
P1 :
︸ ︷︷ ︸ ︸ ︷︷ ︸ ︸ ︷︷ ︸
A figura 7.2 mostra as operações de recombinação e
de mutação realizadas para P1 e P2 para a codificação
binária e decimal. Os pontos de recombinação e de mu-
tação estão indicados na figura.
31
1 0 0 0 0 1 1 1 0 4 1 6
0 1 1 1 1 0 0 1 1 3 6 3
1 1 1 1 1 0 0 1 1 7 6 3
0 0 0 0 0 1 1 1 0 0 1 6
1 1 1 0 1 0 0 1 17 2 3
0 0 0 0 0 1 1 0 0 0 1 4
x1 x2 x3
4 1 6
3 6 3
4 6 3
3 1 6
4 5 3
3 1 7
P1 :
P2 :
P
′
1
:
P
′
2
:
P1 :
P2 :
P1 :
P2 :
P
′
1
:
P
′
2
:
P1 :
P2 :
?
?
t
t
t
t
ponto de recombinação
ponto de mutação⇓ recombinação
⇓ mutação
⇓ recombinação
mutação =⇒
Binário
Decimal
Figura 7.2: Codificação binária e decimal.
32
Um outro problema que aparece com a codificação
binária para representar variáveis inteiras (ou reais) é o
chamado penhasco de Hamming (Hamming cliffs). Este
problema está relacionado com o fato de que determi-
nados números inteiros consecutivos apresentam d́ıgitos
totalmente diferentes quando representados em sistema
binário. Assim, por exemplo, os inteiros consecutivos 15
e 16 assumem a seguinte forma em binário:
Inteiro Binário
15 01111
16 10000
Portanto, recombinação e mutação devem trocar todos
os d́ıgitos binários para fazer uma transição simples de 15
para 16 em variáveis inteiras. Este problema é contorna-
do pelos especialistas em representação binária usando
o chamado código Gray. Dois números inteiros consec-
utivos, quando representados em código Gray, diferem
em apenas um digito binário, eliminando o problema do
penhasco de Hamming. A tabela 7.1 mostra a equiv-
alência entre codificação binária e Gray onde é posśıvel
verificar a propriedade antes mencionada.
33
Tabela 7.1: Equivalência entre código Gray e
binário.
Inteiro Binário Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
34
Transformar a codificação binária em Gray, além de
exigir um esforço computacional adicional, requer con-
hecer as regras de transformação de Gray para binário
e vice-versa. Apresenta-se essas regras de transformação
em forma resumida.
Sejam a e b os arranjos em codificação binária e Gray,
respectivamente, então esses arranjos assumem a seguinte
forma:
b1 b2 b3 . . . bk
a1 a2 a3 . . . ak
b :
a :
⇐= Gray
⇐= Binário
35
Cada elemento do código Gray pode ser encontrado a
partir da codificação binária usando a relação:
bi =



ai se i = 1
De binário para Gray
ai−1 ⊕ ai se i > 1
(1)
e na transformação de Gray para binário, pode-se usar
a relação:
ai =
i⊕
j=1
bj De Gray para binário (2)
O operador ⊕ tem a seguinte regra:
0 ⊕ 0 = 0 0 ⊕ 1 = 1 ⊕ 0 = 1 1 ⊕ 1 = 0
36
Exemplo 7.5: Transformar o número 5 da codificação
binária para a codificação Gray.
A codificação binária de 5 é a seguinte: 101. Os ele-
mentos da codificação Gray, podem-se obter assim:
Para i = 1 =⇒ b1 = 1
Para i = 2 =⇒ b2 = 1 ⊕ 0 = 1
Para i = 3 =⇒ b3 = 0 ⊕ 1 = 1
Portanto, a codificação Gray equivalente é a seguinte:
111 ⇐= código Gray.
37
Exemplo 7.6: Transformar o número 5 do código Gray
para a codificação binária.
A codificação Gray de 5 é a seguinte: 111. Pode-se
obter os elementos da codificação binária da seguinte
forma:
Para i = 1 =⇒ a1 = 1
Para i = 2 =⇒ a2 = 1 ⊕ 1 = 0
Para i = 3 =⇒ a3 = 1 ⊕ 1 ⊕ 1 = 0 ⊕ 1 = 1
Portanto, a codificação binária equivalente é a seguinte;
101 ⇐= codificação binária.
38
Alternativas de Codificação
Existem problemas que apresentam variáveis de difer-
entes tipos: binárias e/ou inteiras e reais. Nesse caso ex-
istem quatro propostas:
1. Implementar codificação binária de todas as variáveis.
Nesse caso, uma configuração t́ıpica seria uma cadeia
de bits binários geralmente muito grande.
2. Implementar codificação “natural” onde cada variável
é representada por uma única casa no vetor que rep-
resenta uma configuração, isto é, uma variável binária
é representada por uma casa binária, uma variável
inteira por uma casa decimal e uma variável real
também como um único elemento. Neste caso o taman-
ho do vetor de codificação é igual ao número de
variáveis do problema.
3. Implementar codificação binária das variáveis binárias
e inteiras e, adicionalmente, calcular o valor exato das
variáveis reais através de um problema subsidiário.
4. Implementar codificação binária para as variáveis
binárias e codificação decimal para as variáveis
inteiras e, adicionalmente, calcular o val-
or exato das variáveis reais através de um
problema subsidiário.
39
Em engenharia elétrica, especialmente em
sistemas de potência, praticamente todos os
pesquisadores escolheram a terceira alternati-
va. Nossa experiência mostra que é mais inter-
essante usar a quarta alternativa em lugar da
terceira alternativa, quando o problema apre-
senta variáveis inteiras e reais como acontece
com o problema de planejamento de sistemas
de transmissão.
A escolha de uma das quatro alternativas de codi-
ficação é crucial na formulação do algoritmo genético
porque repercute de maneira determinante nas outras
etapas do algoritmo genético especialmente no aspecto
relacionado com a robustez, a confiabilidade e o esforço
computacional do algoritmo genético desenvolvido. Es-
colher a terceira ou quarta alternativa implica resolver
um problema subsidiário para conhecer os valores exatos
das variáveis reais que são usados para verificar a factibil-
idade da configuração e/ou para encontrar o valor da
função objetivo. Esse problema subsidiário geralmente
é um problema de PL ou um problema de fluxo de car-
ga em sistemas elétricos de potência. Portanto, resolver
esses problemas subsidiários consome praticamente to-
do o esforço computacional do algoritmo genético de-
senvolvido com esta alternativa mas, em compensação,
são conhecidos os valores exatos das variáveis reais.
40
A escolha das duas primeiras alternativas praticamente
não foi explorada embora sejam as alternativas mais nat-
urais de acordo com a lógica da teoria sobre algoritmos
genéticos. Os motivos não estão muito claros mas po-
dem ser mencionados dois deles: (1) praticamente todas
as configurações geradas seriam infact́ıveis pois muitas
restrições seriam violadas e (2) na primeira alternati-
va os vetores usados para representar as configurações
seria muito grande e na segunda alternativa, deve-se re-
definir o operador de mutação para variáveis reais de
uma maneira muito eficiente. A grande vantagem
dessas alternativas é que não precisa resolver
subproblemas subsidiários. Em outras palavras,
não é necessário resolver problemas de PL ou de fluxo de
carga apenas, deve-se verificar a violação das restrições
para cada configuração da população.
41
Finalmente, existe a proposta formal de implemen-
tar a codificação respeitando “as caracteŕısticas de cada
variável ou problema”, isto é, a codificação deve ser
realizada respeitando a natureza do problema
e do tipo e forma das variáveis. Portanto, uma
variável binária deve ser representada como
um número binário, uma variável inteira como
um número inteiro, uma variável real como
um número real, um arco com a identificação
de um arco, um vértice com a identificação
do vértice, etc. Nesse contexto, deve-se redefinir os
operadores genéticos de recombinação e de mutação ou,
melhor ainda, deve-se definir novos operadores genéticos
que sejam compat́ıveis com os tipos de variáveis e com a
natureza do problema. Esses operadores genéticos inven-
tados para cada tipo de problema não necessariamente
tem um equivalente na evolução natural mas mantém
o esṕırito e a lógica da evolução natural. Esse tipo de
algoritmos são conhecidos como algoritmos evolutivos e
o algoritmo genético é um caso particular. Em outras
palavras, um algoritmo genético que usa uma estrutura
de dados eficiente e redefine novos operadores genéticos
dependentes do tipo de problema se transforma num al-
goritmo evolutivo. Assim, a proposta é um con-
vite para explorar a segunda das quatro al-
ternativas de codificação anteriormente men-
cionadas.
42
Determinação da Função Objetivo e
Manipulação de Infactibilidades
O valor da função objetivo,ou seu equivalente, define
a qualidade de uma configuração. Neste caso, geralmente
a literatura de algoritmos genéticos usa a função
objetivo ou seu equivalente porque nem sem-
pre é posśıvel usar o valor normal da função
objetivo e, deve-se usar um equivalente que de alguma
maneira permita identificar a qualidade de uma configu-
ração ou, melhor ainda, fazer uma comparação quan-
titativa das configurações de uma população. Deve-se
mencionar também que o valor da função objetivo é us-
ado para implementar adequadamente o operador de se-
leção e alguns métodos de seleção não trabalham com os
valores absolutos da função objetivo, apenas interessa a
diferença entre os diferentes valores das funções objetivo
das configurações da população. Esta discussão deve ser
retomada ao analisar o operador de seleção.
43
A determinação da função objetivo está diretamente
relacionada com as infactibilidades de uma configuração.
Uma vez escolhida uma codificação para um problema
espećıfico podem acontecer vários casos de infactibili-
dade que dependem da forma em que é especificada a
codificação, da natureza do problema e dos operadores
genéticos escolhidos ou projetados. Assim, podem acon-
tecer os seguintes casos após escolher um tipo
de codificação: (1) qualquer configuração gerada sem-
pre é fact́ıvel e os operadores genéticos geram também
configurações fact́ıveis, (2) as configurações geradas na
população inicial são sempre fact́ıveis mas os operadores
genéticos destroem essa factibilidade e, (3) as configu-
rações inicialmente geradas são fact́ıveis e infact́ıveis e
os operadores genéticos, obviamente, mantêm essa car-
acteŕıstica.
44
No primeiro caso, que raramente acontece
em problemas reais, não existe ponto em discussão
e pode acontecer, por exemplo, no problema do caix-
eiro viajante com operadores genéticos adequadamente
desenvolvidos. No segundo caso, que pode acon-
tecer com o problema da mochila que gera uma
população inicial usando algoritmos heuŕısticos rápidos,
deve-se encontrar uma forma de contornar as configu-
rações infact́ıveis geradas pelos operadores genéticos. As-
sim, pode-se eliminar as configurações infact́ıveis geradas
ao implementar uma heuŕıstica rápida para transformar
em fact́ıveis as configurações infact́ıveis geradas ou pe-
nalizar a função objetivo com as infactibilidades. O ter-
ceiro caso acontece com o problema de plane-
jamento de sistemas de transmissão e nesse caso
as infactibilidades devem ser manipuladas usando a mes-
ma estratégia do segundo caso.
45
A escolha de uma das três estratégias pro-
postas para manipular as infactibilidades de-
pendem do tipo de problema. Existem prob-
lemas onde raramente são geradas configu-
rações (candidatas) infact́ıveis como acontece com
o problema de alocação ótima de bancos de capacitores
em sistemas de distribuição radial e, nesse caso, a mel-
hor estratégia pode ser eliminar essas configurações in-
fact́ıveis geradas. No outro extremo estão os prob-
lemas de planejamento, como o problema de plane-
jamento de sistemas de transmissão, onde raramente as
configurações encontradas são fact́ıveis e, ainda mais,
é muito dif́ıcil usar heuŕısticas simples para transformar
configurações infact́ıveis em fact́ıveis. Nesse caso, a mel-
hor estratégia pode ser considerar todas as configurações
como sendo “fact́ıveis” e penalizar as infactibilidades na
função objetivo. Esta estratégia é usada no problema de
planejamneto de sistemas de transmissão.
46
Penalizar a função objetivo é uma estratégia
muito usada em otimização clássica. O méto-
do de barreiras é uma dessas técnicas e, nesse caso, o
parâmetro de penalização é crucial no desempenho desse
tipo de algoritmo. Esse fator não pode ser muito grande
porque eliminaria todas as configurações infact́ıveis e,
também, não pode ser muito pequeno porque pode levar
o processo a convergir em configurações infact́ıveis. é t́ıpi-
co usar parâmetros que variam durante o processo de
otimização iniciando o processo com valores pequenos e
aumentando o valor do parâmetro durante o processo de
otimização.
Para o problema da mochila, por exemplo, pode-se
aceitar configurações fact́ıveis e infact́ıveis e modificar a
função objetivo da seguinte forma:
max z(x) = cx − αSinf
onde α é o parâmetro de penalização e Sinf é a infactibil-
idade encontrada da seguinte forma:
Sinf = b −
n∑
j=1
ajxj
47
A função objetivo ou seu equivalente deve
preservar a seletividade entre as configurações,
isto é, deve ter capacidade de identificar as
configurações de melhor qualidade. Portanto, a
função objetivo deve permitir uma clara diferenciação
entre as diferentes configurações da população para facil-
itar a seleção. Também, é frequente padronizar a função
objetivo para assumir valores entre 0 e 1.
48
Exemplo 7.7: Diferentes formas de escolher
a “função objetivo”:
Para o problema da mochila mostrado no exemplo 7.1
encontre três formas alternativas de escolher a “função
objetivo” (função objetivo verdadeira ou um equivalente).
É gerada uma população inicial de 4 configurações
fact́ıveis, muito pequena em aplicações reais, em forma
aleatória e são mostradas a seguir:
0 0 1 0 0 0 1 0 0 1 1 0
0 1 1 0 0 0 1 1 0 0 0 1
0 1 0 1 1 0 0 1 0 1 1 0
1 1 1 1 1 1 0 0 1 1 0 0
P4 :
P3 :
P2 :
P1 :
b
′
= 34
b
′
= 29
b
′
= 34
b
′
= 35
Recurso
usado
45
33
39
43
f.o.
População inicial: 4 configurações fact́ıveis.
49
Neste caso, uma alternativa é usar o valor ver-
dadeiro da função objetivo que denominamos de
z(x). Outra alternativa consiste em padronizar a função
objetivo para valores entre 0 e 1, aproveitando o val-
or máximo da função objetivo que, neste caso, é igual
a z(x) = 81 que acontece quando todos os valores dos
xj = 1. Outra alternativa consiste em subtrair um
valor constante K do valor verdadeiro da função ob-
jetivo. Esta estratégia de modificar o valor da função
objetivo é chamado de janelamento (windowing) e pode
ser usada por vários motivos sendo o principal deles a
necessidade de preservar a seletividade da função objeti-
vo. As três alternativas são apresentadas na Tabela 7.2
para K = 30.
Tabela 7.2: Diferentes tipos de função de adaptação
I II III
Configuração z(x) z1(x) =
z(x)
z(x)
z2(x) = (z(x) − K)
P1 43 0,53 13
P2 39 0,48 9
P3 33 0,41 3
P4 45 0,55 15
50
Na tabela anterior foi usado um K = 30.
Em geral, K é uma constante escolhida levando em
conta a função objetivo da configuração de pior quali-
dade. Assim, no exemplo, foi escolhido um K que é 0,9
vezes a função objetivo de pior qualidade. Agora, existe
a seguinte pergunta interessante: Qual das 3 alternati-
vas de função de adaptação apresenta a melhor seletivi-
dade?.
A função de adaptação tipo III apresenta
uma melhor seletividade quando comparada com
as outras duas alternativas. A discussão deste tópico é re-
tomada ao analisar o operador de seleção.
51
O Operador de Seleção
A seleção é o operador genético que permite selecionar
as configurações da população corrente que devem par-
ticipar da formação da nova população. Portanto o op-
erador de seleção termina após decidir o número
de descendentes que deve ter cada configu-
ração da população corrente. Assim, por exemplo,
algumas configurações podem gerar vários descendentes
e outras podem ser eliminadas do processo por serem
consideradas de pobre qualidade. Existem várias formas
ou tipos de seleção e são apresentadas as mais impor-
tantes mostrando as vantagens e desvantagens de cada
alternativa de seleção.
52
A Seleção Proporcional
A forma mais conhecida para implementar a
seleção é a técnica chamada de seleção propor-
cional. Nesta proposta, cada configuração tem direito
de gerar um número de descendentes que é proporcional
ao valor de sua função de adaptação.O número de de-
scendentes é encontrado usando a relação:
No. de descen. =
função de adapt.
media da função objet.
=⇒ Ndi =
zi(x)
zm(x)
zm(x) =
1
n
n∑
i=1
zi(x)
e portanto:
Ndi = n
zi
n∑
i=1
zi(x)
(3)
em que Ndi é o número de descendentes da configuração
i, zi(x) é o valor da função de adaptação, n é o número de
configurações participando da seleção (tamanho da pop-
ulação) e zm(x) é o valor médio das funções de adaptação
das n configurações da população.
53
A relação (3) encontra valores dos Ndi não inteiros o
que não faz sentido porque o número de descendentes
deve ser um número inteiro. Este problema, t́ıpi-
co da seleção proporcional, é resolvido usando
a roleta (roulete wheel selection scheme). Conceitual-
mente, o esquema da roleta consiste em dividir uma
roleta circular em setores proporcionais ao número de
descendentes que corresponde a cada configuração. A
continuação, deve-se operar a roleta n vezes e, em cada
operação, é escolhido um descendente para aquela con-
figuração que é identificado pelo setor circular ganhador
da roleta. Assim, a roleta resolve o problema de número
não inteiro de descendentes obtido de (3) e, adicional-
mente, introduz uma componente aleatória no processo
quando opera a roleta.
54
As seguintes observações são importantes em relação
ao esquema de seleção proporcional:
O esquema da seleção proporcional tem duas partes
fundamentais e com funções muito espećıficas: (1)
determinação do número de descendentes que é pro-
porcional ao valor da função de adaptação e obtido
usando (3), onde os valores encontrados são não in-
teiros, e (2) integralização desses valores não inteiros
usando a roleta.
Variantes da seleção proporcional e alguns
outros tipos de seleção modificam uma dessas
partes. Entretanto, existem outros méto-
dos de seleção que são radicalmente difer-
entes e não apresentam nenhuma dessas
partes.
55
O uso adequado da relação (3) implica que
os valores dos zi(x) devem ser todos posi-
tivos para o problema de maximização ou
todos negativos para o problema de min-
imização porque não faz sentido, neste caso, en-
contrar o valor médio de números positivos e neg-
ativos. Na verdade, o problema padrão para usar a
seleção proporcional é um problema de maximização
e com valores dos zi(x) não negativos. Portanto, se
o problema de maximização apresenta funções de
adaptação de uma população que são positivos e
negativos então, deve-se realizar uma transformação
das funções de adaptação para que todos eles as-
sumam valores não negativos. Tipicamente se in-
crementa uma constante K para transfor-
mar os valores negativos em positivos. O ca-
so inverso acontece com problemas de minimização
que apresenta funções de adaptação positivos e, nesse
caso, deve-se subtrair uma constante K das funções
de adaptação para que assumam valores negativos.
56
Na teoria básica de algoritmos genéticos o
problema é de maximização e os valores
dos zi(x) são positivos. Quando o problema for
de minimização, como no problema de planejamen-
to de sistemas de transmissão, deve-se realizar uma
transformação do problema para um equivalente de
maximização sempre que seja usada a seleção propor-
cional ou um esquema de seleção que use a primeira
parte da seleção proporcional. Outra alternativa con-
siste em manter a forma de minimização e transfor-
mar os valores das funções de adaptação em neg-
ativos em caso necessário como foi mencionado no
item anterior.
57
Exemplo 7.8:: Seleção proporcional.
Para o problema da mochila apresentado no exemplo
7.4, implementar a primeira parte da seleção propor-
cional usando as funções de adaptação I e III.
Pode-se verificar facilmente que o valor médio das funções
de adaptação tipo I é igual a zm1(x) = 40 e para o tipo
III é igual a zm2(x) = 10. Portanto, usando (3), pode-se
montar a tabela 7.3.
Tabela 7.3: Número de descendentes usando a seleção
proporcional.
Configuração Tipo I Tipo III
P1 1,075 1,3
P2 0,975 0,9
P3 0,825 0,3
P4 1,125 1,5
Total 4,000 4,0
58
Da tabela 7.3, pode-se observar que a estratégia Tipo
I apresenta um número de descendentes muito próxi-
mos especialmente quando comparados com os resulta-
dos da estratégia III. Nesse caso, pode-se afirmar que
a estratégia III apresenta uma melhor sele-
tividade quando comparada com a estratégia I. Assim,
na seleção proporcional, a seletividade que é a principal
caracteŕıstica do operador de seleção é altamente depen-
dente dos valores absolutos das funções de adaptação.
A seleção proporcional deve ser terminada
usando a roleta onde a cada configuração é atribuida
uma parcela da roleta proporcional ao número de de-
scendentes usando a seguinte relação:
2π(
1
n
)Ndi ⇐⇒ 360(
1
n
)Ndi (4)
isto é, pode-se dividir a roleta em graus ou radianos.
59
Exemplo 7.9: Completando a seleção proporcional.
Terminar de implementar a seleção proporcional para
a população com função de adaptação tipo III do exem-
plo anterior.
Usando (4) e os resultados da tabela 7.3, pode-se en-
contrar o setor circular da roleta que corresponde a cada
configuração, mostradas a seguir:
P1 =⇒ 1,3
4
360 = 117o
P2 =⇒ 0,94 360 = 81
o
P3 =⇒ 0,34 360 = 27
o
P4 =⇒ 1,54 360 = 135
o
É posśıvel melhorar a distribuição dos setores circu-
lares da roleta, dividindo os valores anteriores por 360
e encontrando um arco total unitário. Essa idéia elimi-
na a necessidade de “montar” uma roleta convencional,
permitindo montar o esquema da roleta no computa-
dor usando apenas um vetor onde é armazenada toda
a informação e um gerador de números aleatórios no
intervalo [0, 1]. Todas essas propostas alternativas são
apresentadas na figura 7.3.
60
Uma vez montada a roleta, deve-se gerar aleatoria-
mente um número entre 0 e 360. Esse número permite
identificar uma região da roleta e a configuração que
corresponde a essa região que deve ter direito a gerar
um descendente. O processo anterior se repete n vezes
para terminar a seleção. No caso da roleta padroniza-
da, deve-se gerar números aleatórios no intervalo [0, 1] e
identificar a configuração que corresponde a esse número
gerado.
61
Usando a roleta padronizada, pode-se terminar o pro-
cesso de seleção do exemplo anterior. O resultado desse
processo é o seguinte:
No. aleatório gerado Configuração escolhida
(entre 0 y 1)
0,42 2
0,18 1
0,64 4
0,96 4
O processo de seleção termina com a seguinte dis-
tribuição de número de descendentes:
Configuração No. de descendentes
P1 1
P2 1
P4 2
62
A seleção proporcional apareceu juntamente com a
teoria básica dos algoritmos genéticos, isto é, foi a primeira
proposta para implementar o operador de seleção. Poste-
riormente, foi observado experimentalmente de que esta
proposta de seleção apresenta dois grandes prob-
lemas: (1) nas fases iniciais do processo podem aparecer
problemas de superseletividade devido ‘a presença de al-
gumas superconfigurações com direito a gerar muitos de-
scendentes eliminando, prematuramente, a informação
genética presente nas outra configurações da população
e produzindo uma convergência prematura do algorit-
mo para um ótimo local. Por outro lado, nas fases finais
do processo, existe o problema de perda de seletividade
porque quase todas as configurações são de qualidade
semelhante e com direito a gerar um descendente desa-
parecendo a seletividade no processo. As novas propostas
de seleção tentam contornar, de alguma maneira, os dois
problemas anteriores.
63
Formas Alternativas da Seleção
Proporcional
Como foi mencionado anteriormente, a seleção pro-
porcional apresenta problemas com a manipulação ad-
equada de superconfigurações nas fases iniciais do pro-
cesso e de falta de seletividade nas fases finais do proces-
so. Também foi mencionado que a seleção proporcionalapresenta duas partes claramente diferenciadas, sendo
que a primeira consiste em encontrar um número de de-
scendentes proporcional ao valor da função de adaptação
e a segunda parte integraliza o número de descendentes
usando a roleta. Nesse contexto, foram propostas for-
mas alternativas da seleção proporcional que tenta con-
tornar um ou os dois problemas da seleção proporcional
tradicional, modificando uma ou as duas partes inte-
grantes da seleção proporcional. Como essas propostas
implicam pequenas mudanças na seleção proporcional
então são chamadas de formas alternativas da seleção
proporcional. São consideradas formas alterna-
tivas da seleção proporcional os seguintes: (1)
seleção estocástica do reśıduo, (2) seleção de-
termińıstica e, (3) seleção com limitante su-
perior do número máximo de descendentes.
64
Seleção Estocástica do Reśıduo
(stochastic remainder technique)
Esta proposta simplesmente modifica a segunda parte
da implementação da seleção proporcional, isto é, o tra-
balho da roleta. A mudança consiste em realizar uma
seleção determińıstica da parte inteira do número de de-
scendentes e transferir para a roleta somente a parte fra-
cional do número de descendentes. Quando a população
é grande, esta proposta é praticamente equivalente à se-
leção proporcional tradicional em relação à qualidade da
seletividade. Entretanto, o esforço computacional pode
diminuir de maneira significativa porque a roleta é usada
apenas para terminar o processo de seleção. Obviamente,
esta proposta não resolve os dois problemas t́ıpicos da
seleção proporcional tradicional.
65
Exemplo 7.10: Seleção estocástica do reśıduo.
Implementar a seleção estocástica do reśıduo para um
problema de maximização com uma população de 4 con-
figurações e as seguintes funções de adaptação: 43, 39,
33 e 45.
O seguinte quadro mostra o processo de seleção:
Configuração f(x) Nd Seleção Seleção aleatória
determińıstica usando a roleta
1 43 1, 3 1 0, 3
2 39 0, 9 − 0, 9
3 33 0, 3 − 0, 3
4 45 1, 5 1 0, 5
Portanto, a parte determińıstica seleciona duas
configurações e a roleta deve selecionar as out-
ras duas configurações usando a parte fracional do
número de descendentes e após duas operações da role-
ta, provavelmente, serão escolhidas as configurações 2 e
4 completando o processo de seleção.
66
Seleção Determińıstica
Esta proposta simplesmente elimina o trabalho
da roleta e encontra, em forma determińıstica, o número
de descendentes num processo de dois passos: (1)
faz seleção determińıstica da parte inteira do número de
configurações como na proposta anterior e, (2) termina
a seleção usando a parte fracional do número de descen-
dentes e priorizando as configurações que apresentam
maior parte fracional.
Esta proposta apresenta um desempenho praticamente
equivalente que as duas propostas anteriores de seleção
proporcional quando a população é relativamente grande.
Entretanto existe um ganho em esforço computacional
porque é eliminada a roleta e o consequente trabalho
de geração de números aleatórios. Neste caso, também a
proposta não resolve os dois problemas t́ıpicos da seleção
proporcional tradicional. A eliminação da compo-
nente aleatória desta proposta de seleção faz
com que a seleção determińıstica se afaste um
pouco da lógica básica dos algoritmos genéticos.
67
Exemplo 7.11: Seleção determińıstica.
Implementar a seleção determińıstica para a popu-
lação do exemplo 7.10.
O seguinte quadro mostra o processo de implemen-
tação da seleção determińıstica:
Configuração f(x) Nd Parte Parte N
′
d Total de
inteira fracionária descendentes
P1 43 1, 3 1 0, 3 0 1
P2 39 0, 9 0 0, 9 1 1
P3 33 0, 3 0 0, 3 0 0
P4 45 1, 5 1 0, 5 1 2
68
Seleção Proporcional Limitando o
Número Máximo de Descendentes
Esta proposta consiste em limitar o número
máximo de descendentes que pode ter uma con-
figuração, isto é, nenhuma configuração pode ter dire-
ito a gerar um número de descendentes maior que um
limite especificado. Esta proposta elimina parcialmente
o problema de aparecimento de superconfigurações nas
fases iniciais do processo. Assim, por exemplo, se for
especificado um número máximo de descendentes igual
a 3 e uma superconfiguração tem direito a gerar 5 de-
scendentes, usando a relação (4), então essa configuração
deve gerar somente 3 configurações, aumentando a possi-
bilidade de que outras configurações menos promissoras
participem do processo de seleção e sejam selecionadas.
A proposta de limitar o número máximo de
descendentes pode ser incorporada nas três
propostas de seleção proporcional analisadas.
69
Seleção Usando Escalonamento
Linear (scaling mechanism)
Esta proposta de seleção tenta atenuar os
dois principais problemas da seleção propor-
cional tradicional, isto é, o aparecimento de
superconfigurações nas fases iniciais do pro-
cesso e a perda de seletividade nas fases finais
do processo.
A idéia fundamental consiste em realizar uma
transformação linear das funções de adaptação
para melhorar a seletividade do processo quan-
do é usada a relação (3). Assim, quando a dispersão dos
valores das funções de adaptação é grande com a pre-
sença de superconfigurações, a transformação linear pro-
duz novos valores das funções de adaptação com menor
dispersão, melhorando a seletividade. Por outro lado,
quando a dispersão dos valores das funções de adaptação
é pequena com a presença de configurações muito ho-
mogêneas, a transformação linear produz novos valores
das funções de adaptação mais dispersos, melhorando
também a seletividade.
70
Portanto, a proposta fundamental do escalon-
amento linear é realizar uma transformação
linear das funções de adaptação antes de usar
a relação (3) para melhorar a seletividade e o
restante do processo de seleção é implementado exata-
mente igual à seleção proporcional. Em outras palavras,
a seleção usando escalonamento linear é um processo
de seleção que usa transformação linear das funções de
adaptação mais seleção proporcional. Assim, após a trans-
formação linear, o processo de seleção pode ser termina-
do usando uma das seis propostas de seleção propor-
cional analisados anteriormente.
71
A transformação das funções de adaptação é realizada
usando a seguinte relação:
f
′
= af + b
onde f é o valor da função de adaptação original, f
′
é o valor da função de adaptação transformada e, a e
b, são constantes que devem ser calculadas escolhendo
dois pontos da transformação linear. é t́ıpico escolher os
seguintes critérios para definir os pontos:
O maior valor dos f
′
, que corresponde à função de
adaptação transformada de melhor qualidade, deve
ser igual ao valor médio das funções de adaptação
multiplicado por uma constante kt. São valores t́ıpi-
cos de kt ∈ [1, 2 ; 2, 0]
O valor médio em ambas as populações permanecem
constantes. Com essas informações é posśıvel encon-
trar as constantes a e b para realizar a transformação.
72
Exemplo 7.12: Escalonamento linear.
Implementar a seleção usando escalonamento linear
para um problema de maximização com uma população
de 4 configurações e cujas funções de adaptação são as
seguintes: 40, 60, 80 e 360.
No exemplo, pode-se verificar a presença de uma su-
perconfiguração com função de adaptação de 360 em
uma população que apresenta valor médio de 135. Pretende-
se implementar seleção usando escalonamento linear es-
colhendo um valor de kt = 1, 6, isto é, um valor máximo
de função de adaptação transformada igual a 216. Assim,
temos as seguintes relações lineares:
Quando f = 360 =⇒ f
′
= 216 =⇒ 216 = 360a + b
Quando f = 135 =⇒ f
′
= 135 =⇒ 135 = 135a + b
Resolvendo o sistema anterior, pode-se encontrar os
valores de a = 0, 36 e b = 86, 4. Assim, a relaçãode
transformação assume a seguinte forma:
f
′
= 0, 36 f + 86, 4
A diferença entre o número de descendentes, usando
a função de adaptação original e transformada, pode ser
verificada no seguinte quadro:
73
Configuração f(x) Nd f
′
(x) N
′
d
P1 40 0, 30 100, 8 0, 75
P2 60 0, 44 108, 0 0, 80
P3 80 0, 60 115, 2 0, 85
P4 360 2, 66 216, 0 1, 60
No quadro anterior, pode-se verificar que
as funções de adaptação que estavam acima
da media foram diminúıdos e aqueles que es-
tavam abaixo da media foram aumentados,
diminuindo o desvio padrão das funções de
adaptação e melhorando a distribuição de de-
scendentes. O leitor pode verificar que acontece o con-
trário, com um aumento do desvio padrão, quando as
funções de adaptação estão muito próximas o que pode
ser facilmente verificado resolvendo novamente o exem-
plo para uma população com as seguintes funções de
adaptação: 200, 205, 210, 215.
74
O processo de seleção deve ser terminado
usando qualquer dos esquemas de seleção pro-
porcional anteriormente apresentados. Apenas
foi alterada a distribuição do número de descendentes.
Finalmente, pode-se verificar que esta estratégia contor-
na em parte os dos principais problemas da seleção pro-
porcional, diminuindo o poder das superconfigurações
que aparecem nas fases iniciais do processo e aumentan-
do a dispersão das funções de adaptação quando elas
são muito homogêneas, o que acontece nas fases finais
do processo do algoritmo genético.
75
Seleção Usando Ordenamento (rank
based selection)
Nesta proposta o número de descendentes que cor-
responde a cada configuração depende de uma seleção
ordenada (ranking) das configurações em ordem decres-
cente dos valores das funções de adaptação para o proble-
ma de maximização e, em ordem invertida para o proble-
ma de minimização. No ordenamento linear, o número de
descendentes que corresponde a cada configuração varia
linearmente e em forma decrescente com sua localização
no ordenamento (problema de maximização). Portan-
to, o valor da função de adaptação é usado
apenas para fazer o ordenamento. Em outras
palavras, não é crucial o valor absoluto de uma função
de adaptação, interessa conhecer se esse valor é melhor
ou pior que as outras.
76
Esta proposta é significativamente diferente
da seleção proporcional. Na verdade, esta pro-
posta elimina a primeira parte da estratégia
da seleção proporcional que consiste em determi-
nar o número de descendentes usando a relação (3) que
é substitúıda por uma distribuição de descendentes de-
terminado por um ordenamento linear previamente es-
pecificado. No ordenamento linear, o número de
descendentes também é não inteiro e, portan-
to, o processo de seleção deve ser terminado
usando a roleta ou uma proposta equivalente que
substitua a roleta.
77
Em relação ao esquema de ordenamento linear, deve-se
fazer as seguintes observações:
A seleção baseada em ordenamento linear
elimina os dois problemas existentes na se-
leção proporcional, isto é, o problema de
aparecimento de superconfigurações ou de
configurações homogêneas. Este fato decorre
da lógica da seleção por ordenamento onde não in-
teressa os valores absolutos das funções de adap-
tação, e sim, a diferença entre elas. Por exemplo, a
melhor configuração de uma população de
quatro configurações com funções de adap-
tação de 40, 60, 80 e 360 teria um número
de descendentes exatamente igual quando
as funções de adaptação assumem os val-
ores de 110, 120, 130 e 150 ou quando as-
sumem os valores de 105, 108, 111 e 112.
78
Do item anterior, pode-se concluir que o número
de descendentes que corresponde a uma
população de configurações é calculado uma
única vez usando os parâmetros de ordena-
mento linear que devem ser especificados.
Em outras palavras, se os parâmetros escolhidos de-
terminam que a melhor configuração tem direito a
gerar 3,5 descendentes, a segunda melhor 3,2 descen-
dentes, etc., então, esse número de distribuição de de-
scendentes pode permanecer inalterado durante todo
o processo. Em cada iteração do algoritmo genético a
única tarefa consiste em fazer o ordenamento e iden-
tificar qual configuração é a melhor, qual a segunda,
etc. Esta forma de trabalho, além de eliminar os dois
problemas da seleção proporcional, permite a imple-
mentação da seleção com menor esforço computa-
cional. Logicamente é posśıvel mudar os parâmetros
de ordenamento linear.
79
A seleção por ordenamento elimina a ne-
cessidade de transformar um problema de
minimização em um equivalente de maxi-
mização ou da presença de valores da função
de adaptação positivos ou negativos. Entre
um tipo de problema e outro apenas, deve-se inverter
o ordenamento. Este fato é uma consequência dire-
ta de que a seleção por ordenamento linear dispensa
a relação (3) para determinar o número de descen-
dentes.
Como o número de descendentes é não in-
teiro então, deve-se usar a roleta ou equiv-
alente para terminar o processo de seleção.
80
A função de designação linear que permite encontrar
o número de descendentes para cada configuração deve
satisfazer algumas propriedades teóricas. Assim, seja α(x)
a função de designação linear, então ela deve cumprir as
seguintes propriedades:
1. α(x) ∈ R para x ∈ [0, 1].
2. α(x) ≥ 0
3.
∫ 1
0 α(x)dx = 1
Seja a forma geral de α(x) = co − c1x. Então temos
que:
∫ 1
0 α(x)dx = 1 =⇒
∫ 1
0 (co − c1x)dx =

cox −
c1
2
x2


1
0
= 1
=⇒ co−
c1
2
= 1 =⇒ c1 = 2(co−1) =⇒ α(x) = co−2(co−1)x
(5)
A exigência de que α(x) ≥ 0 limita o valor de co para
o intervalo: 1 ≤ co ≤ 2.
81
Exemplo 7.13: Seleção por ordenamento.
Implementar a seleção usando ordenamento linear para
um problema de maximização com uma população de 4
configurações e cujas funções de adaptação são as seguintes:
43, 39, 33 e 45.
Ordenamos as configurações pela qualidade das funções
de adaptação. Assim, temos: P1 = 45, P2 = 43, P3 = 39
e P4 = 33, Usamos a função de designação com co = 2
escolhido arbitrariamente no intervalo permitido de co.
Então separamos o intervalo de variação de x em quatro
parcelas que é o tamanho da população.
Seja α1 a fração que corresponde à melhor configu-
ração, P1, então temos:
α1 =
∫ 0,25
0 α(x)dx =
∫ 0,25
0 (2−2x)dx = [2x−x
2]0,250 =
7
16
De maneira similar, pode-se encontrar os outros val-
ores dos αi e o número de descendentes que corresponde
a cada configuração e os resultados são mostrados no
seguinte quadro:
82
Configuração f(x) αi Nd = 4αi
P1 45 7/16 1, 75
P2 43 5/16 1, 25
P3 39 3/16 0, 75
P4 33 1/16 0, 25
Total 4, 0
Logicamente, os valores dos αi depende ex-
clusivamente do parâmetro co escolhido que
pode permanecer constante durante todo o
processo e assim, pode-se armazenar os αi des-
de o ińıcio do processo ou melhor ainda os valores
dos Ndi = n αi que é o número de descendentes que
corresponde a cada configuração. Portanto, em cada it-
eração do algoritmo genético, deve-se apenas fazer o or-
denamento.
83
Seleção Usando Torneio (tournament
selection)
Esta proposta de seleção é muito atrativa porque é sig-
nificativamente diferente da seleção proporcional. Nes-
ta estratégia, os descendentes são escolhidos
realizando n jogos sendo n o tamanho da pop-
ulação. Em cada jogo são escolhidos aleatori-
amente k configurações e a configuração gan-
hadora do jogo é aquela que tem função de
adaptação de melhor qualidade. O valor de k
é geralmente pequeno, tipicamente k ∈ {2, 3, 4, 5}. Após
n jogos se termina o processo de seleção.
84
Este tipo de seleção é atrativo porque é com-
putacionalmente muito rápido e, também, porque
a estratégia é a mesma para problemas de
maximização e minimização, apenas o critério
de função de adaptação de melhor qualidade
é diferente. Outra vantagem do método é que
eliminaos dois problemas existentes na se-
leção proporcional tradicional porque a seleção
depende apenas dos valores relativos das funções
de adaptação. Finalmente, o processo encon-
tra um número de descendentes inteiro e, por-
tanto, dispensa o uso da roleta. Embora muito
simples, este método é rápido e eficiente.
Na literatura especializada existem ainda outros méto-
dos de seleção. Por exemplo, existe o método genitor
que faz somente uma substituição parcial da população.
Neste contexto, aparece o conceito de elitismo que tenta
preservar as configurações de melhor qualidade.
85
Manipulação de Problemas de
Minimização
Esta parte da análise do algoritmo genético
só faz sentido quando é usado um método de
seleção que usa a relação (3), isto é, os méto-
dos de seleção proporcional e escalonamento
linear. Na teoria básica de algoritmos genéticos geral-
mente é apresentado um problema de maximização com
funções de adaptação positivos onde é posśıvel usar a
relação (3) sem problemas. Este tipo de problema é im-
plicitamente considerado como um problema na forma
padrão para algoritmos genéticos. Portanto, se um prob-
lema de maximização apresenta funções de adaptação
negativos então esses valores são transformados em pos-
itivos, isto é, são padronizados. Por outro lado, se um
problema é de minimização então o problema é transfor-
mado em um problema de maximização, isto é, também
é padronizado. Entretanto, a relação (3) funciona sem
problemas quando o problema é de minimização e os
valores das funções de adaptação são todos negativos
não sendo necessária nenhuma transformação.
86
Quando um problema é de minimização pode ser us-
ada uma das seguintes alternativas:
1. Manter a estrutura de problema de minimização e
transformar as funções de adaptação em negativos,
caso seja necessário, subtraindo uma constante K
de todas as funções de adaptação. Assim, os valores
transformados assumem a seguinte forma:
f
′
(x) = f(x) − K
2. Transformar o problema de minimização em um prob-
lema de maximização usando a seguinte relação:
Minimizar f(x) ⇐⇒ maximizar (1/f(x)) = z(x).
Esta proposta é usada em várias publicações e, em-
bora não seja totalmente equivalente apresenta de-
sempenho satisfatório em aplicações práticas.
3. Transformar o problema de minimização em um prob-
lema de maximização usando a seguinte relação:
Minimizar f(x) ⇐⇒ maximizar [K − f(x)] = z(x)
Esta proposta é uma consequência direta da pro-
priedade min f(x) ⇐⇒ −[max − f(x)]. Se o
problema de minimização apresenta funções de adap-
tação positivos (não está padronizado) então −f(x)
apresenta valores negativos então, deve-se acrescen-
tar uma constante K para que o problema transfor-
mado se encontre na forma padronizada.
87
Exemplo 7.15: Padronizando um problema de mini-
mização.
Usar as três propostas anteriormente apresentadas para
padronizar o seguinte problema de minimização:
Configuração f(x) ⇐= (min.)
1 43
2 39
3 33
4 45
Para a primeira proposta, mantendo o problema co-
mo sendo de minimização, escolhemos o parâmetro K =
48. Para o segundo caso não é necessário escolha de
parâmetro e para o terceiro caso escolhemos o parâmetro
K = 50.
88
A escolha do parâmetro K é realizada de maneira ade-
quada, isto é, deve-se contornar o problema que origina a
escolha de um parâmetro e também manter ou garantir
a seletividade. O seguinte quadro mostra as três pro-
postas de tratamento de um problema de minimização
para realizar a seleção.
Configuração f(x) Primeira alternativa Segunda alternativa
Minimização Maximização
f
′
(x) Nd z(x) Nd
1 43 -7 0,7 0,0232 0,92
2 39 -11 1,1 0,0256 1,01
3 33 -17 1,7 0,0303 1,20
4 45 -5 0,5 0,0222 0,87
Total 160 -40 4,0 0,1013 4,00
89
Recombinação
As configurações escolhidas no processo de seleção de-
vem ser submetidas ao operador de recombinação. No
algoritmo genético, a recombinação consiste
em trocar parcelas de duas configurações para
formar duas novas configurações candidatas.
Em outras palavras, duas configurações can-
didatas são geradas com parcelas de duas con-
figurações geradoras. Essas novas configurações ger-
adas devem ainda ser submetidas ao operador de mu-
tação para que se transformem em configurações da nova
população ou geração. O operador de recombinação (re-
combination ou crossing over) tenta simular o fenômeno
de crossing over na genética. Entretanto, o leitor deve ter
observado que a recombinação dos algoritmos genéticos
é diferente do crossing over: no primeiro caso duas con-
figurações geradoras são recombinadas gerando duas con-
figurações descendentes que estão formadas por parcelas
(subcadeias) das configurações geradoras e, no segundo
caso, dois cromossomos gêmeos se separam e se duplicam
mas acompanhados de um processo de recombinação
genética, isto é, os cromossomos gêmeos se recombinam,
separam e duplicam gerando quatro descendentes.
90
No primeiro caso duas unidades (configurações) se re-
combinam e formam outras duas unidades entanto que,
no segundo caso, uma unidade (formada por dois cro-
mossomos gêmeos) se recombina, duplica e separa for-
mando quatro meias unidades. Entretanto, pode-se afir-
mar que ambos os processos tentam simular o processo
de diversidade genética, isto, produzem descendentes de
caracteŕısticas diferentes. Obviamente, a recombinação
dos algoritmos genéticos é uma imitação grosseira do
crossing over na genética natural.
Existem vários tipos de recombinação e a
diferença entre eles está no número de pon-
tos de recombinação. Assim, esses tipos de recombi-
nação são conhecidos como recombinação de um ponto,
de dois pontos, multiponto e uniforme. Nem sempre, to-
das as configurações são submetidas a recombinação. A
taxa de recombinação determina, em forma aleatória, se
duas configurações selecionadas devem ser submetidas a
recombinação.
91
Recombinação de um Simples Ponto
(single point recombination)
É a mais simples forma de recombinação e
consiste em escolher um único ponto para faz-
er recombinação. Supor que uma configuração tem k
elementos ou casas binárias. Então, uma vez escolhidas
as duas configurações para implementar a recombinação,
deve-se gerar em forma aleatória um número entre 1 e
(k − 1) e, esse número indica o ponto de recombinação.
A parcela que está na direita de ambas as configurações
são trocadas para formar as duas novas configurações
candidatas. As configurações que devem ser submetidas
a recombinação são escolhidas aleatoriamente do conjun-
to de configurações selecionadas que ainda tem direito a
gerar descendentes.
92
Para que as configurações selecionadas sejam submeti-
das a recombinação, deve-se gerar um número aleatório
p ∈ [0, 1]. Se p é menor que a taxa de recombinação ρc
então, deve-se proceder ‘a recombinação; em caso con-
trário as duas configurações selecionadas não são recom-
binadas.
Neste processo de recombinação, novamente, estão pre-
sentes três decisões de caráter aleatório: (1) as duas con-
figurações que devem ser submetidas a recombinação
são escolhidas aleatoriamente, (2) o ponto de recombi-
nação é escolhido aleatoriamente e, (3) deve-se gerar um
número aleatório p que determina se as configurações
selecionadas devem ser submetidas a recombinação. As-
sim, como no caso da seleção, algumas das decisões an-
teriores podem ser substitúıdas por decisões de caráter
determińıstico como, por exemplo, recombinar as mel-
hores configurações com direito a gerar descendentes.
93
Exemplo 7.16: Recombinação de um ponto.
Implementar a recombinação de um ponto para as
configurações selecionadas no problema da mochila do
exemplo 7.5. Considere uma taxa de recombinação de
ρc = 1, 0.
Em forma aleatória são escolhidos os seguintes pares.
{P1 comP4} e {P2 com P4}
1. P1 e P4 são submetidas a recombinação para gerar
duas configurações candidatas. é gerado um número
aleatório p = 8 ∈ {1, 11}. Portanto, a recombinação
gera as seguintes configurações candidatas:
ponto de recombinação
?
⇓ recombinação
0 0 1 0 0 0 1 0 1 1 0 0
1 1 1 1 1 1 0 0 0 1 1 0
0 0 1 0 0 0 1 0 0 1 1 0
1 1 1 1 1 1 0 0 1 1 0 0
P
′
2 :
P1 :
′
P4 :
P1 :
b
′
= 24
b
′
= 45
b
′
= 34
b
′
= 35
Recurso
usado
36
52
45
43
f.o.
Recombinação entre P1 e P4.
94
Deve-se observar que a configuração candidata P
′
1
está infact́ıvel porque 45 > 36 (a restrição está vio-
lada).
2. P2 e P4 são submetidas a recombinação para gerar
duas configurações candidatas. É gerado o número
aleatório p = 3 ∈ {1, 11}. Portanto, a recombinação
gera as seguintes configurações candidatas:
ponto de recombinação
?
⇓ recombinação
0 0 1 1 1 0 0 1 0 1 1 0
0 1 0 0 0 0 1 0 0 1 1 0
0 0 1 0 0 0 1 0 0 1 1 0
0 1 0 1 1 0 0 1 0 1 1 0
P
′
4 :
P3 :
′
P4 :
P2 :
b
′
= 34
b
′
= 34
b
′
= 34
b
′
= 34
Recurso
usado
45
39
45
39
f.o.
Recombinação entre P2 e P4.
Neste caso as duas configurações candidatas são fact́ıveis.
95
Outros Tipos de Recombinação
A diferença entre a recombinação de um
ponto e os outros tipos de recombinação con-
siste simplesmente na escolha do número de
pontos de recombinação. No outro extremo está a
recombinação uniforme que consiste em uma recombi-
nação bit por bit. É intuitivamente evidente que a mel-
hor estratégia de recombinação deve ser o tipo de re-
combinação multiponto com um número de pontos de
recombinação que deve depender do número de elemen-
tos de uma configuração. Deve-se lembrar que a recom-
binação na genética tem um número elevado de pontos
de recombinação mas distante de ser uma recombinação
uniforme.
96
Para o exemplo anterior, uma recombinação de dois
pontos é realizada da seguinte forma:
1 0 0 0 0 1 1 1 0
0 1 1 1 1 0 0 1 1
1 0 0 1 1 1 1 1 0
0 1 1 0 0 0 0 1 1
? ?
pontos de recombinação
⇓ depois da recombinação
97
Mutação (mutation)
Na codificação binária o operador de mu-
tação simplesmente troca o valor de uma variável
de 0 para 1 ou vice-versa. Nos trabalhos ini-
ciais sobre algoritmos genéticos, a mutação
sempre foi considerada um operador secundário.
Entretanto, este ponto de vista está mudan-
do especialmente quando se trata de resolver
problemas reais de grande porte.
98
A taxa de mutação ρm indica a probabili-
dade de que uma posição ou casa binária seja
modificada. Na análise teórica e nas propostas origi-
nais, sugere-se que a mutação deve ser tentada bit por
bit, casa por casa, e portanto a decisão de mutar uma
posição deve ser independente da decisão realizada em
outras posições binárias de uma configuração. Assim, su-
por que é escolhida uma taxa de mutação de ρm = 0, 05,
então cada bit de uma configuração é submetido a mu-
tação com esta probabilidade. Desta forma, é gerado um
número aleatório p ∈ [0, 1] e se esse número é menor
que ρm = 0, 05 então é realizada a mutação. Na im-
plementação da mutação também existe necessidade de
gerar números aleatórios introduzindo, novamente, uma
componente aleatória na implementação do algoritmo
genético.
99
A implementação prática da mutação em problemas
com populações grandes e configurações com elementos
muito grandes, como acontece, particularmente, quan-
do é usada a codificação binária, pode exigir um es-
forço computacional significativo na implementação da
mutação bit por bit. Assim, por exemplo, um proble-
ma com uma população de 200 configurações e com
configurações de 1000 elementos binários implicaria ger-
ar 200000 números aleatórios e tentativas de mutação.
Neste tipo de casos, pode-se implementar a
mutação de uma forma mais rápida e pratica-
mente equivalente. Por exemplo, pode-se de-
terminar o número de mutações mais provável
e distribuir aleatoriamente essas mutações nas
configurações da população.
100
Exemplo 7.17: Mutação.
Implementar a mutação das configurações candidatas
obtidas após a recombinação no exemplo 7.16, usando
uma taxa de mutação de ρm = 0, 05 e terminar de gerar
as configurações da nova população.
Na forma prática de implementar a mutação,
deve-se fazer 0, 05(4)(12) = 2, 4 mutações, is-
to é, 2 mutações. Assim, são escolhidos dois
números aleatórios entre 1 e 48, gerando-se
os números 6 e 23. Portanto, deve-se mutar a sex-
ta posição da primeira configuração e a décima primeira
posição da segunda configuração. As novas configurações
candidatas, após a mutação assumem a seguinte forma:
0 0 1 1 1 0 0 1 0 1 1 0
0 1 0 0 0 0 1 0 0 1 1 0
0 0 1 0 0 0 1 0 1 1 1 0
1 1 1 1 1 0 0 0 0 1 1 0
P
′
4 :
P
′
3 :
P
′
2 :
P
′
1 :
b
′
= 34
b
′
= 34
b
′
= 36
b
′
= 39
Recurso
usado
45
39
51
48
f.o.
Configurações após a mutação.
101
No caso particular do problema da mochila,
com o tipo de codificação escolhida, tanto a
recombinação assim como a mutação podem
gerar configurações infact́ıveis. Neste tipo de
casos existem as seguintes alternativas: (1) trans-
formar as configurações infact́ıveis em fact́ıveis usando
uma heuŕıstica rápida, (2) eliminar as configurações in-
fact́ıveis ou, (3) considerar todas as configurações co-
mo sendo “fact́ıveis” e penalizar aquelas infact́ıveis na
função objetivo. Para gerar a nova população é escol-
hida a primeira alternativa e para eliminar a infactibil-
idade, deve-se passar uma variável com valor 1 para 0
até retomar a factibilidade.
102
A variável que deve passar de 1 para 0 é aquela que tiv-
er a menor relação
cj
aj
. Assim, na configuração candidata
P
′
1 passamos x2 = 1 para x2 = 0 e retomamos a factibil-
idade. Portanto, termina o processo de geração da nova
população constitúıda pelas seguintes configurações:
0 0 1 1 1 0 0 1 0 1 1 0
0 1 0 0 0 0 1 0 0 1 1 0
0 0 1 0 0 0 1 0 1 1 1 0
1 0 1 1 1 0 0 0 0 1 1 0
P4 :
P3 :
P2 :
P1 :
b = 34
b = 34
b = 36
b = 35
Recurso
usado
45
39
51
46
f.o.
Configurações apoś eliminar as infactibilidades.
103
Quando a codificação for de outro tipo, difer-
ente da codificação binária então, deve-se de-
senvolver estratégias equivalentes de mutação
levando em conta a natureza do problema,
do tipo de codificação escolhida e a essência
da mutação na genética natural, isto é, pe-
quenas mudanças no conteúdo genético mas
que produzem um genótipo que não existia
com o conseqüente aparecimento de um novo
fenótipo.
104
Ciclo Geracional
É chamado de ciclo geracional o conjunto de processos
de seleção, recombinação e mutação que permitem en-
contrar as configurações da nova geração ou população
a partir da população corrente. Assim, o ciclo geracional
é controlado pelo programa de controle do algoritmo
genético.
105
Programa de Controle do Algoritmo
Genético
É o conjunto de parâmetros que define o tamanho da
população, a taxa de recombinação e a taxa de mutação
e que define, em forma significativa, o comportamen-
to do algoritmo genético. Este conjunto de parâmetros
é chamado de programa de controle do algoritmo genético.
Valores t́ıpicos recomendados pela literatura especializa-
da são os seguintes:
Tamanho da população: np ∈ [30 ; 200].
Taxa de recombinação: ρc ∈ [0, 5 ; 1, 0].
Taxa de mutação: ρm ∈ [0, 001 ; 0, 050].
106
Critério de Parada
Existem vários critérios de parada que podem ser im-
plementados. Assim, pode-se parar o algoritmo genético
quando:
Foi executado um número especificado de gerações.
A incumbente (melhor solução encontrada) assume
um valor pelo menos de igual qualidade que um valor
previamente especificado.
A incumbente não melhora durante um número es-
pecificado de gerações.
As configurações da população ficam muito homogêneas,
isto é,