Algoritmos Genéticos - Otimização de Sistemas Mecânicos

Prévia do material em texto

Programa de Po´s-Graduac¸a˜o em Engenharia Mecaˆnica
Universidade Federal de Uberlaˆndia
Otimizac¸a˜o de Sistemas Mecaˆnicos
Prof. Fran Se´rgio Lobato
fslobato@ufu.br - www.fslobato.eng.br
Nu´cleo de Modelagem, Controle e Otimizac¸a˜o de Processos
Faculdade de Engenharia Qu´ımica, Universidade Federal de Uberlaˆndia
Introduc¸a˜o aos Algoritmos Gene´ticos
1. Um Pouco de Histo´ria
Ate´ meados do se´culo XIX os pesquisadores acreditavam que a existeˆncia de cada espe´cie se devia a um ser
supremo ou que a teoria da gerac¸a˜o espontaˆnea era uma verdade absoluta. Foi apenas com o estudo baseado
em observac¸o˜es e experimentos que Charles Darwin (ver a Figura 1) propoˆs a teoria da selec¸a˜o natural. Como
resultado deste trabalho, Darwin publica o livro On the Origin of Species by Means of Natural Selection, o
qual influenciou as a´reas da Biologia, Botaˆnica, Zoologia, bem como aspectos relacionados com o pensamento
religioso, filoso´fico, pol´ıtico e econoˆmico da e´poca. Com a teoria desenvolvida por Darwin foi poss´ıvel propor
o princ´ıpio ba´sico da Gene´tica Populacional, isto e´, a variabilidade entre indiv´ıduos em uma populac¸a˜o de
organismos que se reproduzem sexualmente e´ produzida pela mutac¸a˜o e pela recombinac¸a˜o gene´tica. Esta
descoberta permitiu o desenvolvimento de simulac¸o˜es computacionais relacionados com sistemas gene´ticos por
volta de 1950.
Figura 1: Charles Darwin - Idealizador da Teoria da Selec¸a˜o Natural.
Foi John Holland (ver Figura 2(a)) o precursor no desenvolvimento das primeiras pesquisas relacionadas
a` simulac¸a˜o computacional de sistemas gene´ticos. Este estudo resultou, em 1975, na publicac¸a˜o do livro Adap-
tation in Natural and Artificial Systems, hoje considerado a B´ıblia dos Algoritmos Gene´ticos (AG). Mas foi
somente em 1989 com o estudo de David E. Goldberg (ver Figura 2(b)) que os AG se tornaram populares
entre os pesquisadores da a´rea de otimizac¸a˜o. A partir dos trabalhos que seguiram esta linha de pesquisa, os
AG tornaram-se a base fundamental para o desenvolvimento de novos algoritmos de otimizac¸a˜o baseados em
processos que acontecem na natureza e que hoje sa˜o tradicionalmente aplicados em diferentes campos da cieˆncia
e da engenharia.
2. Me´todos de Otimizac¸a˜o sem o uso de Derivadas
2.1 O Primeiro Me´todo Sem Derivadas Proposto
Em termos de otimizac¸a˜o, o primeiro algoritmo no contexto evolutivo, isto e´, sem o uso de informac¸o˜es
sobre o gradiente da func¸a˜o objetivo e das restric¸o˜es para a atualizac¸a˜o de candadatos a` soluc¸a˜o do problema
de otimizac¸a˜o, foi o Me´todo de Ordem Zero. Este consiste da gerac¸a˜o de candidatos de forma aleato´ria, isto
(a) John Holland. (b) David Goldberg.
Figura 2: Idealizadores dos tradicionais Algoritmos Gene´ticos.
e´, sem que nenhuma metodologia espec´ıfica seja empregada para esta finalidade. A ideia ba´sica por tra´s desta
estrate´gia de otimizac¸a˜o e´ gerar, de forma aleato´ria mas respeitando o domı´nio do vetor de varia´veis de projeto
(Equac¸a˜o (1)), candidatos a` soluc¸a˜o do problema. De posse destes candidatos, a func¸a˜o objetivo e´ avaliada. A
soluc¸a˜o e´ definida como o vetor que apresentar o melhor valor de func¸a˜o objetivo.
xki = x
l
i + r(x
u
i − xli) (1)
em que xli e x
u
i representam os limites inferior e superior para o vetor de varia´veis de projeto i (i=1,..., n),
respectivamente, r e´ um nu´mero aleato´rio pertencente ao intervalo [0 1], e xki e´ a k-e´sima iterac¸a˜o da varia´vel
de projeto i.
Em termos gerais, o Me´todo de Ordem Zero apresenta a seguinte estrutura:
¶ Definir os paraˆmetros de entrada: nu´mero de varia´veis de projeto, limites inferior e superior para as
varia´veis de projeto, func¸a˜o objetivo, nu´mero ma´ximo de iterac¸o˜es;
· Enquanto o nu´mero ma´ximo de iterac¸o˜es na˜o for alcanc¸ado:
¸ Gerar o vetor de candidatos a` soluc¸a˜o do problema de otimizac¸a˜o;
¹ Avaliar cada candidato com relac¸a˜o a` func¸a˜o objetivo;
º Fim Enquanto;
» Ao final do processo identificar a melhor soluc¸a˜o (vetor de varia´veis de projeto e respectivo valor de func¸a˜o
objetivo).
Para fins de apresentac¸a˜o desta metodologia considere o seguinte problema:
min f(x) = (x1 − 1)2 + (x2 − 1)2 + x21 (2)
−100, 0 ≤ x1 ≤ 100, 0 (3)
−100, 0 ≤ x2 ≤ 100, 0 (4)
A Tabela 1 apresenta os resultados obtidos considerando diferentes nu´meros de execuc¸o˜es (com semente
inicial para o gerador de nu´meros aleato´rios igual a zero). Os resultados apresentados nesta tabela ressaltam que
o aumento do nu´mero de execuc¸o˜es, como esperado, reduz o valor da func¸a˜o objetivo. E´ interessante observar
que quando aumenta-se esse valor de 102 para 103, o valor da func¸a˜o objetivo na˜o se altera. Isto se deve ao fato
de que o algoritmo na˜o consegue melhorar o valor da func¸a˜o objetivo, por isso esse valor e´ preservado. Ressalta-
se que em todas as execuc¸o˜es na˜o foi poss´ıvel, com a semente considerada nesta ana´lise e para o nu´mero de
Tabela 1: Influeˆncia do nu´mero total de execuc¸o˜es na qualidade da soluc¸a˜o no estudo de caso proposto.
Nu´mero de Execuc¸o˜es x1 x2 f
- 0,5 1 0,5
102 0,904579 3,258393 5,927706
103 0,904579 3,258393 5,927706
104 0,928222 0,612552 1,016863
105 0,892548 1,051621 0,810853
106 0,440368 1,249491 0,569358
execuc¸o˜es realizadas, obter um valor pro´ximo ao da soluc¸a˜o anal´ıtica [x1 x2 f ]=[0,5 1 0,5]. Neste caso, apesar
de simples, a metodologia na˜o foi capaz de obter um resultado satisfato´rio para este estudo de caso, considerado
trivial. A Figura 3 apresenta o histo´rio de execuc¸o˜es usando o Me´todo de Ordem Zero para o tratamento do
problema matema´tico proposto.
Figura 3: Histo´rio de execuc¸o˜es usando o Me´todo de Ordem Zero para o problema proposto.
De forma geral, a metodologia descrita apresenta as seguintes vantangens (Saramago, 1999): conceitu-
almente simples, fa´cil de implementar, e´ uma abordagem relativamente confia´vel, e´ capaz de trabalhar com
qualquer tipo de varia´veis (discretos, cont´ınuos, bina´rios e reais) e requerem apenas a avalic¸a˜o da func¸a˜o obje-
tivo no ponto de interesse. Por outro lado, este necessita de um elevado nu´mero de avaliac¸o˜es da func¸a˜o objetivo
e, por consequeˆncia, um elevado tempo de processamento, o que representa a sua principal desvantagem com
relac¸a˜o as outras te´cnicas de otimizac¸a˜o (Saramago, 1999). Assim, apesar da facilidade de aplicac¸a˜o deste
abordagem, a mesma na˜o pode ser utilizada para resolver problemas de grande complexidade, pois o esforc¸o
computacional requerido seria extremamente elevado.
3. Objetivos
Conforme observado na sec¸a˜o anterior, apesar das vantagens apresentadas pelo algoritmo puramente ale-
ato´rio, dificilmente algum problema mais complexo podera´ ser resolvido utilizando-se esta metodologia. Neste
contexto, o presente guia de estudos tem por objetivo apresentar, de forma resumida e pra´tica, os principais
conceitos relacionados com a concepc¸a˜o conceitual dos tradicionais Algoritos Gene´ticos, com eˆnfase na sua
formulac¸a˜o bina´ria e na sua aplicac¸a˜o em problemas com ou sem restric¸o˜es.
4. Algoritmos Gene´ticos
Os Algoritmos Gene´ticos (AG) sa˜o estrate´gias fundamentadas em mecanismos de selec¸a˜o natural e na
gene´tica de populac¸o˜es, cujo objetivo e´ a determinac¸a˜o da soluc¸a˜o de um problema de otimizac¸a˜o (Michalewicz,
1998). Estes algoritmos, reconhecidamente de busca global (pois sa˜o capazes de escapar de o´timos locais, o que
na˜o acontece com me´todos que fazer uso de informac¸o˜es sobre o gradiente da func¸a˜o objetivo e de suas restric¸o˜es),
geram um populac¸a˜o de candidatos fundamentados em determinados operadores gene´ticos de natureza aleato´ria
de modo a obter a populac¸a˜o mais evolu´ıda poss´ıvel (esta conte´m o candidato que apresenta a maior adpatac¸a˜o,
isto e´, o melhor valor de func¸a˜o objetivo). Apesar de aleato´rios, pode-se dizer quea busca pelo o´timo na˜o
representa um conjunto de tentativas puramente aleato´rias, mas de certa forma direcionadas, pois exploram
informac¸o˜es baseadas no histo´rico para encontrar novos candidatos a` soluc¸a˜o do problema de otimizac¸a˜o. De
forma geral, a atualizac¸a˜o da populac¸a˜o de candidatos e´ realizada atrave´s de um procedimento iterativo, onde
cada iterac¸a˜o e´ denominada, segundo a nomenclatura da gene´tica das populac¸o˜es, de gerac¸a˜o. Durante cada
gerac¸a˜o, os princ´ıpios de reproduc¸a˜o, mutac¸a˜o e selec¸a˜o sa˜o aplicados a uma populac¸a˜o de candidatos de modo
que esta possa ser atualizada, como acontece na natureza onde as espe´cies esta˜o em constante evoluc¸a˜o.
Antes de apresentar os operadores gene´ticos responsa´veis pela atualizac¸a˜o da populac¸a˜o, deve-se enfatizar
a nomenclatura que normalmente e´ encontrada na literatura especializada. A Tabela 2 apresenta a analogia
entre a gene´tica de populac¸o˜es e o problema de otimizac¸a˜o (Michalewicz, 1998).
Tabela 2: Analogia entre a gene´tica das populac¸o˜es e o problema de otimizac¸a˜o.
Linguagem Natural Problema de Otimizac¸a˜o
Cromossomo Vetor de varia´veis de projeto
Gene Unidade do cromossomo
Alelo Valor do gene
Populac¸a˜o Conjunto de cromossomos
Gerac¸a˜o Iterac¸a˜o
Aptida˜o Func¸a˜o Objetivo
A Figura 4 exemplifica o exposto acima (Saramago, 1999):
Figura 4: Relac¸a˜o entre cromossomos, genes e alelos (Adaptado de Saramago (1999)).
Nesta figura o cromossomo representa o vetor que conte´m as n varia´veis de projeto referentes ao problema
de otimizac¸a˜o, representadas, neste caso, por um conjunto de 5 nu´meros bina´rios (zero ou um). Cada gene
representa uma varia´vel de projeto e cada bina´rio representa um gene. Ja´ o conjunto de cromossomos forma a
populac¸a˜o de candidatos a` soluc¸a˜o do problema de otimizac¸a˜o. E´ importante ressaltar que a primeira versa˜o dos
AG foi implementado considerando a codificac¸a˜o bina´ria, isto e´, todo e qualquer nu´mero real era representado por
uma sequeˆncia de nu´meros bina´rios. Neste contexto, todo o desenvolvimento da metodologia sera´ fundamentada
nesta estrutura, apesar de hoje em dia os AG serem representados por codificac¸a˜o real. Isto se deve ao fato da
codificac¸a˜o bina´ria implicar em uma grande alocac¸a˜o de memo´ria, requerida para poder representar um nu´mero
real com muitas casas decimais. Assim, este tipo de representac¸a˜o e´ pouco empregada no contexto de otimizac¸a˜o
evolutiva.
Conforme comentado, os AG sa˜o procedimentos iterativos onde, a cada gerac¸a˜o, a populac¸a˜o e´ modificada
de acordo com a aplicac¸a˜o de determinados operadores, a saber, o operador de reproduc¸a˜o (processo no qual
cada cadeia e´ copiada levando em conta os valores da func¸a˜o objetivo); o operador de cruzamento (processo
no qual a combinac¸a˜o de partes de cada um de dois cromossomos gera um novo descendente) e o operador de
mutac¸a˜o (que representa a modificac¸a˜o aleato´ria ocasional (de baixa probabilidade) do valor de um alelo da
cadeia) (Saramago, 1999). O fluxograma descrito na Figura 5 apresenta a estrutura ba´sica dos AG.
Figura 5: Fluxograma ba´sico referente aos tradicionais AG (Adaptado de Saramago (1999)).
Antes de discutir os operadores citados, faz-se necessa´rio a apresentac¸a˜o da forma como cada varia´vel de
projeto sera´ representada, ja´ que o objetivo deste guia de estudos e´ destacar a primeira versa˜o dos tradicionais
AG proposta, isto e´, a com codificac¸a˜o bina´ria.
Todo e qualquer nu´mero real pode ser representado na forma bina´ria, isto e´, ao inve´s de usar a representac¸a˜o
real, pode-se escrever um nu´mero em termos de zero e da unidade. A conversa˜o de um nu´mero inteiro e´ realizada
da direita para a esquerda, isto e´, determina-se primeiro o algarismo das unidades (o que vai ser multiplicado
por 20), em seguida o segundo algarismo da direita (o que vai ser multiplicado por 21), e assim por diante.
A questa˜o chave, por incr´ıvel que parec¸a, e´ observar se o nu´mero e´ par ou ı´mpar. Em bina´rio, o nu´mero
par termina em 0 e o nu´mero ı´mpar termina em 1. Assim, determina-se o algarismo da direita pela simples
divisa˜o do nu´mero por dois (se o resto for 0 (nu´mero par) o algarismo da direita e´ 0; se o resto for 1 (nu´mero
ı´mpar) o algarismo da direita e´ 1). Por outro lado, e´ bom lembrar que, na base dez, ao se dividir um nu´mero
por dez, basta levar a v´ırgula para a esquerda. Analogamente na base dois, ao se dividir um nu´mero por dois,
basta levar a v´ırgula para a esquerda. Assim, para se determinar o segundo algarismo do nu´mero em bina´rio,
basta lembrar que ele e´ a parte inteira do nu´mero original dividido por dois, abandonando o resto.
Como exemplo pra´tico, deseja-se converter 25 de decimal para bina´rio. A Figura 6 apresenta o procedimento
geral para transformar um nu´mero decimal em um equivalente bina´rio.
Figura 6: Tranformac¸a˜o de um nu´mero decimal em um nu´mero bina´rio.
Neste caso, o nu´mero 25 pode ser representado como 11001, que pode ser reescrito na base 2 como (m=5,
e´ o nu´mero de bits considerados):
x =
m−1∑
i=0
am−1−i × 2i = 1× 20 + 0× 21 + 0× 22 + 1× 23 + 1× 24 = 25 (5)
em que a ≡[a0 a1 a2 a3 a4]=[1 1 0 0 1].
Esta transformac¸a˜o e´ necessa´ria para ilustrar o procedimento proposto no primeiro AG. Assim, todo nu´mero
real podera´ ser representado atrave´s da codificac¸a˜o bina´ria.
Para fins de aplicac¸a˜o dos operadores do AG, sera´ considerado a seguinte func¸a˜o matema´tica (Haupt &
Haupt, 1998; Saramago, 1999).
max f = −(β sin(4β) + 1, 1γ sin(2γ)) (6)
8 ≤ β, γ ≤ 10 (7)
Para este exemplo sera´ considerado 8 bits (m na Equac¸a˜o (5)) para a representac¸a˜o de cada varia´vel,
conforme proposto por Haupt & Haupt (1998); Saramago (1999). A seguir sa˜o apresentados os operadores
ba´sicos dos AG, bem como a forma como a populac¸a˜o inicial e´ gerada, como o crite´rio de parada pode ser
definido neste procedimento iterativo e como pode ser realizado o tratamento de restric¸o˜es de igualdade e
desigualdade.
4.1 Inicializac¸a˜o da Populac¸a˜o
Como em qualquer algoritmo de otimizac¸a˜o evolutivo, a populac¸a˜o e´ inicializada aleatoriamente (onde cada
varia´vel de projeto e´ delimitada pelo domı´nio especificado pelo usua´rio). Para essa finalidade, deve-se definir
o tamanho da populac¸a˜o, bem como a func¸a˜o objetivo (Equac¸a˜o (6)) e o respectivo domı´nio (Equac¸a˜o (7)).
Assim, considerando seis candidatos na populac¸a˜o tem-se a seguinte populac¸a˜o inicial (gerada aleatoriamente):
Tabela 3: Populac¸a˜o inicial para a func¸a˜o f .
Candidato
Representac¸a˜o Representac¸a˜o
f
Bina´ria Real
C1 [10000101 00100111] [9,04 8,31] 16,26
C2 [00001110 00001001] [8,11 8,07] -3,21
C3 [10010001 00000001] [9,14 8,01] 11,01
C4 [11000101 00101001] [9,55 8,32] 2,76
C5 [01111100 10101100] [8,98 9,35] 10,32
C6 [11100010 01001010] [9,77 8,58] -0,22
A transformac¸a˜o do primeiro cromossomo (candidato a` soluc¸a˜o do problema de otimizac¸a˜o) de bina´rio para
real pode ser realizada considerando a seguinte relac¸a˜o Saramago (1999):
ξ = liminf + ξ¯
limsup − liminf
2m − 1 (8)
em que ξ representa o vetor de varia´veis de projeto (β ou γ), ξ¯ representa o nu´mero bina´rio codificado para a
base 10, liminf e limsup representam os limites inferior e superior referentes ao vetor de varia´veis de projeto e
m e´ o nu´mero de bits considerados para a representac¸a˜o da codificac¸a˜o bina´ria.
Para o estudo de caso em questa˜o tem-se:
β¯ =
8−1∑
i=0
a8−1−i × 2i = 1× 20 + 0× 21 + 1× 22 + 0× 23 + 0× 24 + 0× 25 + 0× 26 + 1× 27 = 133 (9)
γ¯ =
8−1∑
i=0
a8−1−i × 2i = 1× 20 + 1× 21 + 1× 22 + 0× 23 + 0× 24 + 1× 25 + 0× 26 + 0× 27 = 39 (10)
em que a para β e γ sa˜o iguais a [10000101] e [00100111], respectivamente (conforme a primeira linha da Tabela
3).
Portanto, aplicando a Equac¸a˜o (8) obteˆm-se (liminf=[8 8], limsup=[10 10], m=8, β¯=133 e γ¯=39):β = 8 +
133(10− 8)
28 − 1 = 9, 04 (11)
γ = 8 +
39(10− 8)
28 − 1 = 8, 31 (12)
Com os valores de β e γ convertidos, a func¸a˜o objetivo (Equac¸a˜o (6)) pode ser avaliada para este candidato:
max f = −(9, 04 sin(4× 9, 04) + 1, 1× 8, 31 sin(2× 8, 31)) = 16, 26 (13)
Analogamente, os outros candidatos da populac¸a˜o tambe´m podem ser avaliados, conforme apresentado na
Tabela 3. A seguir, todos esses indiv´ıduos da populac¸a˜o sera˜o modificados atrave´s da aplicac¸a˜o dos operadores
gene´ticos de reproduc¸a˜o, cruzamento e mutac¸a˜o.
4.2 Reproduc¸a˜o
No operador de reproduc¸a˜o o candidato que apresenta o maior valor, em termos da func¸a˜o objetivo, tem a
maior chance de contribuir a` gerac¸a˜o seguinte (com pelo menos um descendente). Assim, quanto maior o valor
da func¸a˜o objetivo, maiores sa˜o as chances do candidato sobreviver no ambiente e reproduzir-se passando parte
de seu material gene´tico a gerac¸o˜es posteriores (Braga, 1998; Saramago, 1999). Para a aplicac¸a˜o deste operador
faz-se necessa´rio a determinac¸a˜o da probabilidade (pi, i=1, ..., 6), conforme a seguinte equac¸a˜o:
pi =
fi(β, γ)∑6
j=1 fj(β, γ)
i = 1, ..., 6 (14)
Assim, se o candidato for de baixa adequabilidade, o mesmo tem alta probabilidade de desaparecer da
populac¸a˜o. Por outro lado, o candidato for de alta adequabilidade, o mesmo tem grandes chances de permanecer
na populac¸a˜o.
Para a populac¸a˜o apresentada na Tabela 3, o somato´rio de todos os valores da func¸a˜o objetivo e´:
6∑
j=1
fj(β, γ) = 36, 92 (15)
Como citado anteriormente, a func¸a˜o objetivo (f(β, γ)) e´ o crite´rio que decide sobre a vida ou a morte de
cada cromossomo. O mecanismo para selec¸a˜o das melhores cadeias, ou seja, das mais adaptadas, e´ definido pelo
uso das probabilidades proporcionais, resultando os seguintes valores:
p1 =
16, 26
36, 92
= 0, 44 (16)
p2 =
−3, 21
36, 92
= −0, 09 (17)
p3 =
11, 01
36, 92
= 0, 30 (18)
p4 =
2, 76
36, 92
= 0, 07 (19)
p5 =
10, 32
36, 92
= 0, 28 (20)
p6 =
−0, 22
36, 92
= −0, 00 (21)
em que:
6∑
i=1
pi = 1 (22)
As probabilidades acumulativas (qi, i=1, ...,6) para cada cromossomo sa˜o dadas por:
qi =
i∑
j=1
pj , i = 1, ..., 6 (23)
Assim, tem-se os seguintes valores acumulativos:
q1 = p1 = 0, 44 (24)
q2 = p1 + p2 = 0, 44− 0, 09 = 0, 35 (25)
q3 = p1 + p2 + p3 = 0, 44− 0, 09 + 0, 30 = 0, 65 (26)
q4 = p1 + p2 + p3 + p4 = 0, 44− 0, 09 + 0, 30 + 0, 07 = 0, 72 (27)
q5 = p1 + p2 + p3 + p4 + p5 = 0, 44− 0, 09 + 0, 30 + 0, 07 + 0, 28 = 1, 00 (28)
q6 = p1 + p2 + p3 + p4 + p5 + p6 = 0, 44− 0, 09 + 0, 30 + 0, 07 + 0, 28 + 0, 00 = 1, 00 (29)
A seguir deve-se selecionar as cadeias que ira˜o contribuir para a gerac¸a˜o seguinte. Esta selec¸a˜o considera
um conjunto de nu´meros r, escolhidos aleatoriamente entre [0,1], em quantidade igual ao nu´mero de cadeias. A
ana´lise e´ feita atrave´s das seguintes opc¸o˜es:
• Se r < qi, enta˜o seleciona-se o i◦ cromossomo Ci;
• Por outro lado, se r > qi, enta˜o analisar o subsequente cromossomo, isto e´, i+1.
Vale ressaltar que alguns cromossomos podera˜o ser selecionados mais de uma vez, isto e´, os melhores sera˜o
copiados mais vezes, enquanto que os de menor probabilidade podera˜o ser eliminados da populac¸a˜o Saramago
(1999).
Para o estudo de caso em ana´lise, considere que foram gerados os seguintes nu´meros aleato´rios:
r = [0, 64 0, 08 0, 47 0, 88 0, 93 0, 70] (30)
A selec¸a˜o dos cromossomos e´ dada como segue. Primeiramente inicializa-se o processo testando o cromos-
somo 1. Assim, como r1=0,64>q1=0,44 → avalia-se o pro´ximo cromossomo. r1=0,64>q2=0,35 → avalia-se o
pro´ximo cromossomo. r1=0,64<q3=0,65 → seleciona-se o cromossomo C3.
Em seguida, avalia-se os outros candidatos:
• r2=0,08<q1=0,44 → seleciona-se o cromossomo C1;
• r3=0,47>q1=0,44 → avalia-se o pro´ximo cromossomo. r3=0,47>q2=0,35 avalia-se o pro´ximo cromossomo
r3=0,47<q3=0,65 → seleciona-se o cromossomo C3;
• r4=0,88>q1=0,44 → avalia-se o pro´ximo cromossomo. r4=0,88>q2=0,35 → avalia-se o pro´ximo cromos-
somo. r4=0,88>q3=0,65 → avalia-se o pro´ximo cromossomo. r4=0,88>q4=0,72 → avalia-se o pro´ximo
cromossomo. r4=0,88<q5=1,00 → seleciona-se o cromossomo C5;
• r5=0,93>q1=0,44 → avalia-se o pro´ximo cromossomo. r5=0,93>q2=0,35 → avalia-se o pro´ximo cromos-
somo. r5=0,93>q3=0,65 → avalia-se o pro´ximo cromossomo. r5=0,93>q4=0,72 → avalia-se o pro´ximo
cromossomo. r5=0,93<q5=1,00 → seleciona-se o cromossomo C5;
• r6=0,70>q1=0,44 → avalia-se o pro´ximo cromossomo. r6=0,70>q2=0,35 → avalia-se o pro´ximo cromos-
somo. r6=0,70>q3=0,65→ avalia-se o pro´ximo cromossomo. r6=0,70<q4=0,72 seleciona-se o cromossomo
C4.
Depois de selecionados, os cromossomos da˜o origem a uma nova populac¸a˜o representada como:
Tabela 4: Populac¸a˜o gerada a partir da aplicac¸a˜o do operador de reproduc¸a˜o.
Candidato
Representac¸a˜o Gerado do
f
Bina´ria Cromossomo
C
′
1 [10010001 00000001] C3 11,01
C
′
2 [10000101 00100111] C1 16,26
C
′
3 [10010001 00000001] C3 11,01
C
′
4 [01111100 10101100] C5 10,32
C
′
5 [01111100 10101100] C5 10,32
C
′
6 [11000101 00101001] C4 2,76
4.3 Cruzamento
O operador de cruzamento consiste de troca de material gene´tico de modo a promover a diversidade da
populac¸a˜o, isto e´, promover a explorac¸a˜o da regia˜o de busca. Na literatura, inu´meras sa˜o as formas para se
obter o cruzamento nos AG. Neste estudo sera´ adotado o seguinte procedimento. Seja um ponto k que define
a posic¸a˜o de cruzamento na cadeia de bits de cada cromossomo escolhido aleatoriamente na populac¸a˜o. A
quantidade de cromossomos a ser submetida ao processo de cruzamento e´ definida atrave´s da probabilidade
de cruzamento (pc), especificada pelo usua´rio entre [0,1] (por se tratar de uma probabilidade). Cada cadeia e´
quebrada no k-e´simo ponto e todas as informac¸o˜es do cromossomo i, a partir do ponto escolhido, sa˜o copiadas
para o cromossomo j e vice-versa, conforme esquematizado na Figura 7. O processo de escolha de quem sera´
compartilhado deve ser feito em pares, atrave´s da escolha via a gerac¸a˜o de nu´meros aleato´rios (ri). Quando na˜o
for poss´ıvel formar os pares um novo sorteio devera´ ser feito ate´ obter os pares necessa´rios para o cruzamento.
Por exemplo, se r1 for menor que a probabilidade pc, enta˜o o cromossomo C
′
1 sera´ selecionado.
Figura 7: Representac¸a˜o esquema´tica do operador de cruzamento (Adpatado de Saramago (1999)).
De maneira geral, o valor da probabilidade de cruzamento e´ tomada como sendo 0,25 (considerado neste
trabalho). Apo´s de ter feito isso, deve-se gerar um novo nu´mero aleato´rio para determinar a k-e´sima posic¸a˜o
onde duas novas cadeias sa˜o formadas pela troca de todos os caracteres compreendidos entre as posic¸o˜es k+1 e
m. Esta k-e´sima posic¸a˜o pode ser determinada atrave´s da seguinte relac¸a˜o Saramago (1999):
k = 1 + rand((m− 1)− 1) (31)
em que rand e´ um nu´mero aleato´rio gerado no intervalo compreendido entre 0 e 1 e m e´ o nu´mero de bits
considerados.
Em termos pra´ticos, a seguir este operador sera´ aplicado ao estudo de caso proposto. Assim, a nova
populac¸a˜o C
′
i (i=1, ..., 6) sera´ submetida ao operador de cruzamento. Para essa finalidade considera-se pc igual
a 0,25 e os seguintes nu´meros aleato´rios ri=[0,50 0,17 0,40 0,15 0,20 0,23], os quais nos revelam que [r1 > pc r2 <
pc r3 > pc r4 < pc r5 < pc r6 < pc]. Neste caso, os cromossomos com posic¸o˜es C
′
2 e C
′
4; C
′
5 e C
′
6 sa˜o selecionados
para o cruzamento. Agora, e´ so´ gerar um nu´mero aleato´rio para determinar a k-e´sima posic¸a˜o para a realizac¸a˜o
do cruzamento. Considerando rand igual a 0,7, o valor de k e´ k=1+0,7((16-1)-1)=1+0,7(15-1)=10,8. Assim,
considera-se o maior inteiro, isto e´, k e´ igual a 11. Da´ı,
C
′
2 − 1000010100100111 C
′
4 − 0111110010101100 (32)
Trocando os caracteres tem-se:
C′
2 − 1000010100101100 C
′
4 − 0111110010100111 (33)
Analogamente para o outro par:
C
′
5 − 0111110010101100 C
′
6 − 1100010100101001 (34)
Trocando os caracteres tem-se:
C
′
5 − 0111110010101001 C
′
6 − 1100010100101100 (35)
Apo´s a aplicac¸a˜o do operador cruzamento, a populac¸a˜o gerada e´ dada na Tabela 5. O subscrito
′′
representa
um novo candidado a` soluc¸a˜o do problema de otimizac¸a˜o.
Tabela 5: Populac¸a˜o gerada a partir da aplicac¸a˜o do operador de cruzamento.
Candidato
Representac¸a˜o
f
Bina´ria
C
′
1 [10010001 00000001] 11,01
C
′′
2 [10000101 00101100] 16,72
C
′
3 [10010001 00000001] 11,01
C
′′
4 [01111100 10100111] 11,02
C
′′
5 [01111100 10101001] 10,67
C
′′
6 [11000101 00101100] 3,10
4.4 Mutac¸a˜o
O operador de mutac¸a˜o consiste em uma modificac¸a˜o aleato´ria no valor de um alelo da cadeia (que forma o
gene e, por consequeˆncia, o cromossomo). Caso o alelo escolhido seja zero passa a ser um e vice-versa, conforme
esquematizado na Figura 8.
Figura 8: Representac¸a˜o esquema´tica do operador de mutac¸a˜o (Adpatado de Saramago (1999)).
Segundo Haupt & Haupt (1998), uma forma simples de se implementar esse operador e´ gerar pares (a, b)
aleato´rios onde a representa a linha e b representa a coluna da mudanc¸a do bit. Em termos pra´ticos para o estudo
de caso proposto para a aplicac¸a˜o dos operadores, sejam os pares (1,10) e (5,3), logo tem-se (o cromossomo C
′
2
na˜o sera´ objeto de mutac¸a˜o por apresentar o maior valor para a func¸a˜o objetivo):
• Par (1,10): escolhe-se o cromossomo 1 (C ′1, o qual sera´ modificado na posic¸a˜o de nu´mero 10, isto e´:
[1001000100000001 1001000101000001];
• Par (5,3): escolhe-se o cromossomo 5 (C ′′5 , o qual sera´ modificado na posic¸a˜o de nu´mero 3, isto e´:
[0111110010101001 0101110010101001].
Outra forma muito comum e de grande aplicabilidade consiste na selec¸a˜o aleato´ria de uma posic¸a˜o em
um cromossomo, a qual deve ser comparada com a probabilidade de mutac¸a˜o pm (escolhida pelo usua´rio como
sendo geralmente igual a 1%) para mudar o valor do bit. Neste caso, se for gerado um nu´mero aleato´rio entre
0 e 1 e este for menor que a probabilidade de mutac¸a˜o, sera´ realizada a mudanc¸a no bit do cromossomo,
caso contra´rio, o cromossomo permanece sem nenhuma modificac¸a˜o. Este operador tem um papel importante
e necessa´rio, porque a aplicac¸a˜o dos operadores de reproduc¸a˜o e de cruzamento podem resultar na perda de
material gene´tico potencialmente u´til. O operador de mutac¸a˜o protege os algoritmos gene´ticos contra perdas
irrepara´veis (Saramago, 1999). Tomada isoladamente, a mutac¸a˜o se constituiria na explorac¸a˜o aleato´ria do
espac¸o das cadeias. Utilizada com cuidado, juntamente com os outros dois operadores, protege-se o procedimento
da perda prematura de informac¸o˜es importantes (Braga, 1998).
Para a aplicac¸a˜o deste operador ao estudo de caso proposto sa˜o necessa´rios a gerac¸a˜o de 96 (16(nu´mero
de bits totais)×6(tamanho da populac¸a˜o)) nu´meros aleato´rios r entre [0,1]. Se r for menor que a probabilidade
pm=0,01 sera´ feita a mutac¸a˜o no bit correspondente. Assim, considere que foram gerados 96 nu´meros r entre
0 e 1 e que treˆs tiveram probabilidades menores que pm. Foram os seguintes nu´meros r=[r13=0,009<pm=0,01
r39=0,0025<pm=0,01 r83=0,0004<pm=0,01].
Considerando a populac¸a˜o atual como sendo dado pela Tabela 6 pode-se selecionar a posic¸a˜o onde deve-se
Tabela 6: Populac¸a˜o atual.
Candidato
Representac¸a˜o
f
Bina´ria
C
′
1 [10010001 00000001] 11,01
C
′′
2 [10000101 00101100] 16,72
C
′
3 [10010001 00000001] 11,01
C
′′
4 [01111100 10100111] 11,02
C
′′
5 [01111100 10101001] 10,67
C
′′
6 [11000101 00101100] 3,10
ocorrer a mutac¸a˜o, conforme ilustrado na Tabela 7.
Tabela 7: Selec¸a˜o da posic¸a˜o para aplicac¸a˜o do operador mutac¸a˜o.
Posic¸a˜o Cromossomo Probabilidade
13 C
′
1 0,009
39 C
′
3 0,0025
83 C
′′
6 0,0004
Submetendo os bits 13, 39 e 83 ao processo de mutac¸a˜o teˆm-se:
Tabela 8: Nova populac¸a˜o (apo´s a aplicac¸a˜o do operador mutac¸a˜o).
Cromossomo Representac¸a˜o Bina´ria
C
′
1 [10010001 00001001]
C
′′
2 [10000101 00101100]
C
′
3 [10010011 00000001]
C
′′
4 [01111100 10100111]
C
′′
5 [01111100 10101001]
C
′′
6 [11100101 00101100]
Apo´s a aplicac¸a˜o dos treˆs operadores tem-se encerrado a 1a gerac¸a˜o dos AG. Observa-se na Tabela 9 que
os valores da func¸a˜o objetivo referentes a cada candidato modificaram-se com relac¸a˜o a` populac¸a˜o inicial. cujo
valor do somato´rio de f aumentou:
6∑
i=1
fi(β, γ) = 58, 52 (36)
Observando as Tabelas 3 e 9 nota-se que a populac¸a˜o inicial melhorou no sentido de caminhar na direc¸a˜o
da maximizac¸a˜o da func¸a˜o objetivo, apo´s a aplicac¸a˜o dos treˆs operadores apresentados. Ale´m disso, observa-se
que o valor do somato´rio de fi(β, γ) passou de 36,92 para 58,52. Nesta primeira gerac¸a˜o, o ponto o´timo obtido
corresponde a`: [β γ f ]=[9,04 8,35 -16,72]. Com o decorrer do processo evolutivo, espera-se que a populac¸a˜o
possa evoluir no sentido de melhorar o valor da func¸a˜o objetivo.
Tabela 9: Populac¸a˜o ao final da 1a gerac¸a˜o (apo´s a aplicac¸a˜o dos treˆs operadores).
Cromossomo Representac¸a˜o Bina´ria β γ f
C
′
1 [10010001 00001001] 9,14 8,04 11,52
C
′′
2 [10000101 00101100] 9,04 8,35 16,72
C
′
3 [10010011 00000001] 9,15 8,00 10,68
C
′′
4 [01111100 10100111] 8,97 9,31 11,06
C
′′
5 [01111100 10101001] 8,97 9,33 10,63
C
′′
6 [11100101 00101100] 9,80 8,35 -2,09
4.5 Crite´rio de Parada
Em termos pra´ticos, inu´meras sa˜o as formas de se finalizar um procedimento iterativo. Dentre as mais
comuns pode-se citar: i) nu´mero ma´ximo de gerac¸o˜es (se um nu´mero finito de gerac¸o˜es e´ alcanc¸ado, o processo
evolutivo e´ finalizado); ii valor nume´rico da func¸a˜o objetivo menor que uma refereˆncia (quando se conhece a
soluc¸a˜o do problema, o procedimento evolutivo pode ser finalizado quando o valor computado pelo algoritmo de
otimizac¸a˜o for menor ou igual a esse valor); iii) erro absoluto e/ou relativo em termos do vetor de varia´veis de
projeto (se o vetor de varia´veis de projeto na˜o pode ser mais atualizado, o procedimento iterativo e´ finalizado);
iv) nu´mero de avaliac¸o˜es (ou chamadas) da func¸a˜o objetivo (se o nu´mero ma´ximo de avaliac¸o˜es da func¸a˜o
objetivo for ultrapassado, o procedimento iterativo e´ finalizado); v) tempo de processamento (se o tempo
ma´ximo permitido para a execuc¸a˜o do algoritmo for ultrapassado, o procedimento iterativo e´ finalizado) e vi)
intervenc¸a˜o humana (o procedimento iterativo e´ finalizado pelo pro´prio usua´rio sem que nenhum outro crite´rio
seja adotado). E´ importante ressaltar que as quatro primeiras formas sa˜o as mais empregadas para finalizar
todo e qualquer procedimento iterativo. Cabe enfatizar que o atendimento das u´ltimas duas na˜o implica que
a soluc¸a˜o do problema foi alcanc¸ada, na˜o sendo estas empregadas isoladamente para finalizar o procedimento
iterativo. Assim, pode-se propor um crite´rio h´ıbrido (mais que um dos apresentados ao mesmo tempo) para
finalizar o procedimento iterativo.
4.6 Tratamento de Restric¸o˜es de Igualdade e Desigualdade
Os problemas de otimizac¸a˜o sa˜o inerentemente constitu´ıdos por restric¸o˜es de igualdade/desigualdade, ad-
vindas de limitac¸o˜es operacionais e f´ısicas, de restric¸o˜es ambientais, entre outros. A grande maioria dos algo-
ritmos evolutivos que hoje esta˜o dispon´ıveis na literatura na˜o lidam diretamente com esses tipos de restric¸o˜es
(na˜o foram desenvolvidos, a priori, para lidar com restric¸o˜es), mas podem ser facilmente adequados. Para essa
finalidade, pode ser empregrado, por exemplo, o Me´todo da Penalidade Exterior (Vanderplaats, 1999) para o
tratamento de restric¸o˜es de igualdade e desigualdade. Basicamente,este me´todo consiste da definic¸a˜o da func¸a˜o
Pseudo-Objetivo (Φ(x, rp)), que consiste em transformar o problema original com restric¸o˜es em um similar sem
restric¸o˜es. Esta func¸a˜o e´ definida como (Vanderplaats, 1999):
Φ(x, rp) = f(x) + rpP (x) (37)
em que f(x) e´ a func¸a˜o objetivo original, x e´ o vetor de varia´veis de projeto, rp e´ o paraˆmetro de penalidade e
P (x) e´ a func¸a˜o penalidade, que e´ definida como:
P (x) =
m∑
j=1
(
max(0, gj(x))
)2
+
l∑
k=1
(hk(x))
2 (38)
onde m e l representam o nu´mero de restric¸o˜es de desigualdade e igualdade, respectivamente. Cabe ressaltar
que g(x) deve ser menor ou igual a zero para que essa abordagem possa ser aplicada. Caso g(x) for maior que
zero, primeiramente essa deve ser convertida em uma func¸a˜o equivalente menor que zero.
Nesta equac¸a˜o percebe-se que, quando as restric¸o˜es de igualdade ou desigualdade sa˜o violadas, esse valor
e´ ponderado pela poteˆncia e, na func¸a˜o Pseudo-Objetivo, essa e´ ponderada pelo fator rp, que amplifica o seu
efeito no valor da func¸a˜o objetivo original (f(x)). Assim, toda e qualquer violac¸a˜o em qualquer uma das
restric¸o˜es implica na penalizac¸a˜o da func¸a˜o objetivo. Segundo Vanderplaats (1999), quando rp tender a ∞ o
valor nume´rico da func¸a˜o Pseudo-Objetivo (sem restric¸o˜es) tende ao valor da func¸a˜o original (com restric¸o˜es).
Assim, diferentemente do que acontece com os me´todos cla´ssicos, onde esse valor na˜o pode ser, inicialmente
elevado (pois pode gerar, por exemplo, um problema mal condicionado), nos me´todos evolutivos esse valor pode
ser elevado desde o in´ıcio. Isto se deve ao fato dos me´todos evolutivos na˜o fazerem uso, como os me´todos
evolutivos, de informac¸o˜es sobre matrizes e suas inversas. Neste caso, em se tratando de me´todos evolutivos, o
valor de rp pode ser bem elevado (da ordem de 10
10, por exemplo).
5. Aplicac¸o˜es
5.1 Func¸o˜es Matema´ticas Cla´ssicas
Determine a soluc¸a˜o dos seguintes problemas de otimizac¸a˜o:
- Func¸a˜o f1:
min f(x) = x21 − 3x1x2 + 4x22 + x1 − x2 (39)
−100, 0 ≤ x1 ≤ 100, 0 (40)
−100, 0 ≤ x2 ≤ 100, 0 (41)
Resposta: x1=-0,713041; x2=-0,142376 e f=-0,285714.
- Func¸a˜o f2:
min f(x) = 10x41 − 20x21x2 + 10x22 + x21 − 2x1 + 5 (42)
−2.0 ≤ x1 ≤ 2.0 (43)
−2.0 ≤ x2 ≤ 2.0 (44)
Resposta: x1=1; x2=1 e f=4.
- Func¸a˜o f3:
min f(x) = 100(x2 − x21)2 + (1− x1)2 + 90(x4 − x23)2 + (1− x23)2+
+10, 1((x2 − 1)2 + (x4 − 1)2) + 19, 8(x2 − 1)(x4 − 1) (45)
0 ≤ x1 ≤ 2, 0 (46)
0 ≤ x2 ≤ 2, 0 (47)
0 ≤ x3 ≤ 2, 0 (48)
0 ≤ x4 ≤ 2, 0 (49)
Resposta: x1=1; x2=1; x3=1; x4=1 e f=0.
- Func¸a˜o f4:
min f(x) = (x1 − 1)2 + (x2 − 1)2 (50)
x1 + x2 − 1 ≤ 0 (51)
x1 ≥ 0 (52)
0 ≤ x1 ≤ 1 (53)
0 ≤ x2 ≤ 1 (54)
Qual e´ o efeito pra´tico do paraˆmetro de penalidade? Para responder esta pergunta, testar va´rios valores
para rp. Resposta: x1=0,5; x2=0,5 e f=0,5.
- Func¸a˜o f5:
min f(x) = (x1 − x2)2 + (x2 + x3 − 2)2 + (x4 − 1)2 + (x5 − 1)2 (55)
x1 + 3x2 = 0 (56)
x3 + x4 − 2x5 = 0 (57)
x2 − x5 = 0 (58)
−2 ≤ x1 ≤ 2 (59)
−2 ≤ x2 ≤ 2 (60)
−2 ≤ x3 ≤ 2 (61)
−2 ≤ x4 ≤ 2 (62)
−2 ≤ x5 ≤ 2 (63)
Qual e´ o efeito pra´tico do paraˆmetro de penalidade? Para responder esta pergunta, testar va´rios valo-
res para rp. Resposta: x1=-0,76744186; x2=0,25581395; x3=0,62790697; x4=-0,11627906; x5=0,25581395 e
f=4,09302325.
- Func¸a˜o f6:
min f(x) = x21 − 5x1 + x22 − 5x2 + 2x23 − 21x3 + x24 + 7x4 + 50 (64)
x21 − x1 + 2x22 + x23 + 2x24 − x4 − 10 ≤ 0 (65)
x21 + x1 + x
2
2 − x2 + x23 + x3 + x24 − x4 − 8 ≤ 0 (66)
2x21 + 2x1 + x
2
2 − x2 + x23 − x4 − 5 ≤ 0 (67)
0 ≤ x1 ≤ 2, 1 (68)
0, 5 ≤ x2 ≤ 2, 8 (69)
1, 5 ≤ x3 ≤ 3, 9 (70)
−2, 1 ≤ x4 ≤ 0 (71)
Qual e´ o efeito pra´tico do paraˆmetro de penalidade? Para responder esta pergunta, testar va´rios valores
para rp. Resposta: x1=0; x2=1; x3=2; x4=-1 e f=6.
5.2 Resoluc¸a˜o de Sistemas de Equac¸o˜es Alge´bricas
A presente sec¸a˜o tem por objetivo resolver sistemas de equac¸o˜es alge´bricas atrave´s da formulac¸a˜o e resoluc¸a˜o
de um problema de otimizac¸a˜o. Para esta finalidade sa˜o considerados dois estudos de caso.
- Estudo de Caso Matema´tico:
f1 = x
3 − 3xy2 − 1 = 0 (72)
f2 = 3x
2y − y3 = 0 (73)
cujas ra´ızes sa˜o: [1 0]; [-0,5
√
3/2] e [-0,5 -
√
3/2]. Como pode-se resolver este problema no contexto da otimiza-
c¸a˜o? Como podemos obter todas as ra´ızes?
- Estudo de Caso de Engenharia:
O modelo dinaˆmico de um reator biolo´gico e´ dado pelo sistema de equac¸o˜es diferenciais:[
dx1
dt
dx2
dt
]
=
[
f1(x1, x2)
f2(x1, x2)
]
=
[
(µ−D)x1
(sf − x2)D − µx1/Y
]
(74)
onde x1 representa a concentrac¸a˜o de biomassa, x2 representa a concentrac¸a˜o de substrato, a entrada manipulada
D=F/V (vaza˜o volume´trica/volume reator) e´ definida como taxa de diluic¸a˜o e as condic¸o˜es iniciais sa˜o definidas
genericamente como x1(0)=x1◦ e x2(0)=x2◦. Considerando que a taxa espec´ıfica de crescimento (µ) segue a lei
de Monod:
µ =
µmaxx2
km + x2
(75)
e que sa˜o conhecidos os seguintes paraˆmetros: µmax=0,53 h
−1, km=0,12 g/L, Y=0,4, sf=4 g/L e D=0,4 h−1,
deseja-se determinar a condic¸a˜o de estado estaciona´rio para este modelo. OBS: A condic¸a˜o de estado estaciona´rio
e´ definida quando as varia´veis de interesse, neste caso x1 e x2, na˜o mais dependem do tempo. Matematicamente,
o estado estaciona´rio e´ definido como:
dx1
dt
=
dx2
dt
= 0 (76)
Neste caso, tem-se um sistema de equac¸o˜es alge´bricos na˜o lineares que devem ser resolvidas simultanea-
mente.[
f1(x1, x2)
f2(x1, x2)
]
=
[
(µ−D)x1
(sf − x2)D − µx1/Y
]
=
[
0
0
]
(77)
cujas ra´ızes sa˜o: [0 4] e [1,452307692 0,3692307692].
5.3 Problemas de Estimac¸a˜o de Paraˆmetros
Encontrar os paraˆmetros (a e b) do modelo matema´tico y = a exp(−bx) de modo que o somato´rio da
diferenc¸a quadra´tica entre os pontos experimentais apresentados na Tabela 10 e os preditos pelo modelo seja a
menor poss´ıvel.
Tabela 10: Pontos experimentais para o problema de ajuste de curvas.
xexp 0 5 10 15 20 25
yexp 1 0,7099 0,5597 0,4428 0,3240 0,2510
E se o modelo fosse y = a+ bx? O que voceˆ espera que acontec¸a com a qualidade do ajuste?
6. Considerac¸o˜es Finais
O presente guia de estudos teve como objetivo apresentar os principais operadores envolvidos na aplicac¸a˜o
dos tradicionais Algoritmos Gene´ticos, bem como a sua aplicac¸a˜o em problemas cla´ssicos de otimizac¸a˜o, na
resoluc¸a˜o de sistemas de equac¸o˜es alge´bricas e na estimac¸a˜o de paraˆmetros. A partir deste material foi poss´ıvel
constatar que esta ferramenta configura-se como um interessante procedimento para a otimizac¸a˜o de sistemas
matema´ticos, com aplicac¸o˜es em engenharia e a´reas afins. Quanto a sensibilidade dos paraˆmetros considerados
por esta estrate´gia evolutiva, pode-se concluir que a qualidade de soluc¸a˜o obtida e´ func¸a˜o destes paraˆmetros e
que, para cada estudo de caso, deve-se avaliar a sua influeˆncia (em alguns casos mais relevante que em outros).
7. Atividades
1) Como observado na aula, a qualidade da soluc¸a˜o obtida pelos AG e´ func¸a˜o da especificac¸a˜o de seus
paraˆmetros. Neste contexto, e´ de grande importaˆncia que se realize uma ana´lise de sensibilidade dos paraˆmetros
considerados nos AG e se avalie a sua real influeˆncia sobre a qualidade da soluc¸a˜o. Para essa finalidade, avalie a
influeˆncia de alguns dos paraˆmetros dos AG apresentado em aula. Considere em sua ana´lise a func¸a˜o matema´tica
descrita a seguir.
min f(x) = x1 sin(4x1) + 1, 1x2 sin(2x2) (78)
0 ≤ x1 ≤ 10 (79)
0 ≤ x2 ≤ 10 (80)
Para ajudar na organizac¸a˜o dos resultados complete a Tabela 11, que depende da semente considerada para
inicializar o gerador de nu´mero aleato´rios do comando rand. OBS: Quando estiver sendo realizada a ana´lise
para um determinado paraˆmetro, os outros devera˜o permanecer constantes. Assim, considere o conjunto de
paraˆmetrosdefault : N=50, ngen=500, pc=0,9 e pm=0,1. Neste caso, por exemplo, na avaliac¸a˜o da influeˆncia
do nu´mero de indiv´ıduos da populac¸a˜o (N) na qualidade da soluc¸a˜o devera´ ser analisado diferentes valores
de N (conforme apresentado na Tabela 11). Os outros devera˜o permanecer constantes (use os valores default
definidos). Em termos pra´ticos, para a ana´lise de N , treˆs sera˜o os estudos de caso, a saber, o primeiro ([N=5,
ngen=500 pc=0,9 pm=0,1]); o segundo ([N=50, ngen=500 pc=0,9 pm=0,1]) e o terceiro ([N=100, ngen=500
pc=0,9 pm=0,1]). A mesma ana´lise devera´ ser realizada para os outros paraˆmetros. Para facilitar sua ana´lise,
plote gra´ficos que relacionem a func¸a˜o objetivo (eixo y) o paraˆmetro em ana´lise (eixo x). O que voceˆ pode
concluir com cada ana´lise?
Tabela 11: Avaliac¸a˜o da sensibilidade dos paraˆmetros dos AG no valor da func¸a˜o objetivo.
Semente
N nger
5 50 100 10 100 1000
0 000000000 000000000 000000000 000000000 000000000 000000000
1
2
3
4
5
6
7
8
9
Me´dia
Desvio Padra˜o
Semente
pc pm
0,5 0,7 0,9 0,01 0,05 0,1
0 000000000 000000000 000000000 000000000 000000000 000000000
1
2
3
4
5
6
7
8
9
Me´dia
Desvio Padra˜o
2) Para a ana´lise de um estudo de caso ine´dito, isto e´, voceˆ na˜o conhece a soluc¸a˜o do problema, o que voceˆ
deve fazer para se resguardar quanto ao resultado obtido?
REFEREˆNCIAS
Braga, C. G., 1998. O uso de algoritmos gene´ticos para aplicac¸a˜o em problemas de otimizac¸a˜o de sistemas mecaˆ-
nicos. Master’s thesis, Faculdade de Engenharia Mecaˆnica, Universidade Federal de Uberlaˆndia, Uberlaˆndia-
MG.
Haupt, R. L. & Haupt, S. E., 1998. Practical Genetic Algorithms. John Wiley § Sons, INC., first edition edition.
Michalewicz, Z., 1998. Evolutionary Computation for NonLinear Programming Problems.
Saramago, S. F. P., 1999. Me´todos de Otimizac¸a˜o Randoˆmica: Algoritmos Gene´ticos e Simulated Annealing.
FAMAT/UFU, Notas em Matema´tica Aplicada, Volume 6, SBMAC, Sa˜o Carlos - SP.
Vanderplaats, G. N., 1999. Numerical Optimization Techniques for Engineering Design. VR D INC. Colorado
Springs, USA, third edition edition.
	REFERÊNCIAS