Algoritmo genético

Prévia do material em texto

O USO DE ALGORITMOS GENÉTICOS PARA DETERMINAR ZEROS DE FUNÇÕES 
NÃO LINEARES 
 
 Ediany Batista Silva 
Universidade Católica de Brasília 
Curso de Matemática 
 
RESUMO 
 
Os algoritmos genéticos utilizam conceitos provenientes do princípio de evolução natural para abordar uma série 
ampla de problemas, em especial de otimização. Robustos, genéricos e facilmente adaptáveis, consistem de uma 
técnica amplamente estudada e utilizada em diversas áreas. O cálculo de raízes de equações não lineares é um 
problema muito estudado em matemática computacional e, dentro de certas condições, bastante mal condicionado. 
Isso faz com que a implementação de algoritmos numéricos para determinar as raízes de equações algébricas e 
transcendentes traga consigo grandes problemas como a instabilidade numérica e cancelamento catastrófico, dentre 
outros. Além disso, os processo iterativos tradicionais não podem garantir a convergência para um problema em 
geral. O objetivo principal deste trabalho é estudar o comportamento dos algoritmos genéticos e aplicá-lo ao cálculo 
de raízes de equações não lineares. 
 
Palavras-chave: algoritmos genéticos; raízes de equações não lineares. 
 
1. INTRODUÇÃO 
 
Otimização, num sentido amplo significa melhorar o que já existe, ou seja, projetar o 
novo com mais eficiência e menor custo. A própria evolução da espécie pode ser vista como um 
processo de otimização: ao longo do tempo, os seres vivos se tornam cada vez mais adaptados a 
um meio ambiente em constante mudança. Atualmente, existe uma tendência de buscar modelos 
encontrados na natureza para representar métodos de otimização (Haupt, 1998). Tudo indica que 
os processos naturais relacionados aos seres vivos são bem concebidos e adaptam-se ao mundo 
científico. Algoritmos Genéticos fazem parte de uma família de modelos computacionais 
inspirados na evolução: algoritmos evolutivos – simulam processos naturais aplicando a soluções 
de problemas reais – surgidos então como novas alternativas para resolução de problemas 
complexos. 
Processo de otimização consiste em melhorar a performance, com o objetivo de alcançar 
um ou vários pontos ótimos. É desta forma que funcionam os Algoritmos Genéticos (AGs). Eles 
combinam a sobrevivência do mais adaptado, com uma troca de informações ao mesmo tempo 
aleatória e estruturada. Os AGs trabalham seguindo as seguintes etapas, que serão detalhadas na 
próxima seção. Primeiramente, é gerada uma população de palavras ou cromossomos (strings), 
que são seqüências de códigos, geralmente de forma binária, que representam determinados 
parâmetros. Durante o processo evolutivo esta população é avaliada e uma porcentagem será 
mantida podendo ainda sofrer modificações em suas características fundamentais através de 
cruzamento e/ou mutação, gerando descendentes para a próxima geração. Este processo, 
chamado de reprodução é repetido até que uma solução satisfatória seja encontrada. Então por 
este processo de seleção obtém-se os indivíduos melhores adaptados que neste caso seriam os 
valores que fornecem os pontos ótimos. Por isso podemos classificá-los como métodos 
randômicos de otimização, diferenciando das técnicas clássicas de otimização que podem 
apresentar algumas dificuldades numéricas e problema de robustez relacionadas com 
continuidade das funções, multimodalidade, existência de máximos e mínimos locais. 
Neste trabalho é apresentada uma aplicação do algoritmo genético para o cálculo de raízes 
de equações não lineares. Para isto, o problema de achar as raízes deve ser transformado num 
problema equivalente de máximos e mínimos, como mostrado na seção 3. 
 
2. ALGORITMO GENÉTICO 
 
Os Algoritmos Genéticos representam uma família de modelos computacionais, onde seu 
funcionamento encontra inspiração em um dos mecanismos básicos da evolução da natureza. 
Portanto podemos fazer uma analogia entre evolução biológica e algoritmos genéticos. Estes 
algoritmos foram inicialmente desenvolvidos pelo professor John Holland, da Universidade de 
Michigan, nos Estados Unidos da América (Holland, 1975), em suas explorações dos processos 
adaptativos de sistemas naturais e suas possíveis aplicabilidades em projetos de softwares de 
sistemas artificiais. 
Os AGs podem se apresentar de duas formas: com parâmetros binários e com parâmetros 
reais. Neste trabalho utiliza-se a codificação binária. 
Assim como no seu desenvolvimento, o vocábulo dos algoritmos genéticos é baseado na 
genética natural. Fala-se sobre indivíduos (genótipos) de uma população. Estes indivíduos 
também são chamados de cromossomos. 
Cromossomos são compostos de unidades ou elementos, cada elemento equivale a um 
gene, dispostos em uma seqüência linear. Observe o esquema abaixo. 
 
 
 
 
 
 
 
 
 
 
 
 
Sendo n o número de variáveis (genes) e cada gene com um comprimento m. 
Como exemplo, considere uma função com duas variáveis f(x,y), então as variáveis serão 
representadas através de um cromossomo com dois gene, sendo m = 6, o número de alelos de 
cada gene. 
 
 
Cromossomo 
�
�
�
�
�
�
�
�
������
yx
011001101101 
 
cromossomo X1 X2 X3 X4 ... Xn 
 
gene 1 0 1 1 0 
 
alelo 
 
1 
 
Algoritmos genéticos são algoritmos iterativos, e a cada iteração a população é 
modificada, usando as melhores características dos elementos da geração anterior e submetendo-
as a três tipos básicos de operadores para produzir melhores resultados (Braga, 1998). Estes 
operadores são denominados: Seleção, Cruzamento e Mutação. 
Segundo Bittencourt (1998), O Algoritmo Genético básico realiza as seguintes funções: 
� inicializa a população de cromossomos (soluções); 
� avalia cada cromossomo da população; 
� cria novos cromossomos a partir da população atual (aplica mutação e cruzamento, 
substituindo os ascendentes pelos descendentes); 
� termina, se o critério de fim for alcançado, se não, reinicializa. 
 
Vejamos o diagrama das operações supracitadas: 
 
 
 
Os procedimentos aplicados serão detalhados na seqüência 
 
Definir: 
Função de Custo: F(xi) 
Variáveis de Projeto: (xi) 
 
 
Criar População 
 
Avaliar custo 
Seleção 
Cruzamento 
Mutação 
Teste de convergência 
Fim 
O primeiro passo para a aplicação de algoritmos genéticos a um problema qualquer é 
encontrar alguma representação cromossômica conveniente, cujo gene represente o espaço de 
busca do problema, com vetores binários de zeros e um (0,1), os quais são gerados 
aleatoriamente. O comprimento m do gene depende da precisão requerida para o problema 
(Haupt, 1998). 
Como exemplo, seja a seguinte função: f(x) = 3 + 10*sen(5*x) + 7*cos(4*x), cujo 
intervalo de interesse é (0,9). Então o espaço de busca, ou seja, o domínio da função tem 
amplitude I = 9 – 0 = 9. Utilizaremos precisão de duas casas decimais, portanto o intervalo deve 
ser dividido em I*10P subintervalos iguais, 9*102 = 900 pontos. Logo a seqüência binária deverá 
ter pelo menos 10 bits, pois 
 
512 = 29 < 900 < 210 = 1024 
 
A seguir é gerada uma população inicial de seis cromossomos obtida aleatoriamente, onde 
cada gene é um vetor binário de m bits, sendo m em função da precisão exigida (nesse caso 10-2) 
e da amplitude do intervalo que contém os pontos desejados (I = 9). 
 
C1 = 1010010000 
C2 = 0010100001 
C3 = 1000010001 
C4 = 0010010101 
C5 = 1000010101 
C6 = 1001101110 
 
2.1 Seleção 
 
É um processo que será atribuído às cadeias que possuem o maior valor objetivo e, 
portanto uma probabilidade mais elevada de contribuir à geração seguinte, criando pelo menos 
um descendente. Quanto maior o valor da função objetivo, maior são as chances do indivíduo 
sobreviver no ambiente e reproduzir-se passando parte de seu material genético a gerações 
posteriores(Braga, 1998). 
Usando a probabilidade, expressa pela equação (2.1), tem-se que se o individuo for de 
baixa adequabilidade, tem alta probabilidade de desaparecer da população, caso contrário, os 
indivíduos terão grandes chances de permanecer na população. Sendo x um vetor com os valores 
da população inicial. 
 
)(
)(
xF
xfPi = , sendo �= )()( ixfxF (2.1) 
 
Para se calcular o valor da função de adaptação f(x), deve-se converter a seqüência binária 
(base 2) para base 10, ou seja, deve-se decodificar um cromossomo, dadas pelas equações (2.2) e 
(2.3). 
 
C = [b7b6...b2b1b0 a7a6...a2a1a0] (2.2) 
 
i
m
i
ibx 2
1
0
×=�
−
=
 e i
m
i
iay 2
1
0
×=�
−
=
 (2.3) 
 
Feito isso, temos que calcular o valor de x e y reais, dentro da região viável, com a 
seguinte equação: 
 
 
�
�
	
�
�
�
�
�
�
�
�
−
−
+=
�
�
�
�
�
−
−
+=
12
12
m
ii
i
m
ii
i
ab
yay
ab
xax
 (2.4) 
 
sendo: 
 
ai e bi - domínio das variáveis x e y. 
 
m - comprimento total do gene. 
 
Com a população inicial já definida, o próximo passo será o cálculo da função objetivo 
(adaptação). 
Utilizando o exemplo anterior, será mostrado o cálculo da função objetivo do primeiro 
cromossomo criado para a população inicial (C1). 
 
Seja C1 = 1010010000 
 
Passando para a base 10, utilizando as equações (2.2) e (2.3) 
 
i
m
i
ibx 2
1
0
×=�
−
=
= 1 x 29 + 0 x 28 + 1 x 27 + 0 x 26 +0 x 25 + 1 x 24 + 0 x 23 + 0 x 22 + 0 x 21 + 0 x 20 
 
i
m
i
ibx 2
1
0
×=�
−
=
 = 
 
Os valores reais de x dentro da região viável, são dados por: 
 
�
�
�
�
�
−
−
+=
12m
ii
i
ab
xax 
 
5.7713
12
093410 10 =�
�
�
�
�
−
−
+=x 
 
e o valor da função é: 
 
f(x) = 3 + 10*sen(5*x) + 7*cos(4*x) 
f(x) = 3 + 10*sen(5* 5.7713) + 7*cos(4* 5.7713) 
f(x) = -5.7099 
 
 
Os resultados para cada cromossomo da população inicial estão escritos no quadro abaixo: 
 
Cromossomos x f(x) 
1010010000 5.7713 -5.7099 
0010100001 1.4164 15.8734 
1000010001 4.6540 0.2334 
0010010101 1.3109 9.2224 
1000010101 4.6891 0.0372 
1001101110 5.4721 3.9541 
� )(xf 23.6106 
 
A função f(x) é o árbitro final que decide sobre a vida ou morte de cada cromossomo. O 
mecanismo para seleção das melhores cadeias, ou seja, as mais adaptadas, são definidas pelo uso 
das probabilidades proporcionais, dadas pela equação (2.1). 
 
p1 = -0.2418 
p2 = 0.6723 
p3 = 0.0099 
p4 = 0.3906 
p5 = 0.0016 
p6 = 0.1675 
 
sendo p1 + p2 + p3 + p4 + p5 + p6 = 1,00 
 
Considerando que as probabilidades acumulativas qi de cada cromossomo são dadas por: 
 
�=
=
i
j
ji Pq
1
 (2.5) 
 
Obtém-se os seguintes valores acumulativos: 
 
q1 = p1 = -0.2418 
q2 = p1 + p2 = -0.2418 + 0.6723 = 0.4305 
q3 = p1 + p2 + p3 = -0.2418 + 0.6723 + 0.0099 = 0.4403 
q4 = p1 + p2 + p3 + p4 = -0.2418 + 0.6723 + 0.0099 + 0.3906 = 0.8310 
q5 = p1 + p2 + p3 + p4 + p5 = -0.2418 + 0.6723 + 0.0099 + 0.3906 + 0.0016 = 0.8325 
q6 = p1 + p2 + p3 + p4 + p5 + p6 = -0.2418 + 0.6723 + 0.0099 + 0.3906 + 0.0016 + 0.1675= 1,0000 
 
A seguir deve-se selecionar as cadeias que irão contribuir para a geração seguinte. Esta 
seleção considera um conjunto de números r, escolhidos randomicamente entre [0,1], em 
quantidade igual ao número de cadeias. 
A análise é feita através das seguintes opções: 
Se r < q1, então se seleciona o 1º cromossomo (C1). 
Se r > q1, então se passa para o subseqüente e faz a análise novamente. 
Vale ressaltar que alguns cromossomos poderão ser selecionados mais de uma vez, ou 
seja, os melhores serão copiados mais vezes, enquanto que outros irão morrer. 
Utilizando o mesmo exemplo dado, considere que foram gerados os seguintes números 
randômicos: 
 
r1 = 0.1957 
r2 = 0.2632 
r3 = 0.7138 
r4 = 0.9776 
r5 = 0.6371 
r6 = 0.5459 
 
A seleção dos cromossomos é dada por: 
 
r1 = 0.1957 > q1 = -0.2418 � r1 = 0.1957 < q2 = 0.4305 
 
então seleciona C2 
 
r2 = 0.2632 > q1 = -0.2418 � r2 = 0.2632 < q2 = 0.4305 
 
então seleciona C2 
 
r3 = 0.7138 > q1 = -0.2418 � r3 = 0.7138 > q2 = 0.4305� r3 = 0.7138 > q3 = 0.4403 � r3 = 
0.7138 < q4 = 0.8310 
 
então seleciona C4 
 
r4 = 0.9776 > q1 = -0.2418 � r4 = 0.9776 > q2 = 0.4305� r4 = 0.9776 > q3 = 0.4403� r4 = 
0.9776 > q4 = 0.8310 � r4 = 0.9776 > q5 = 0.8325 � r4 = 0.9776 < q6 =1,0000 
 
então seleciona C6 
 
r5 = 0.6371 > q1 = -0.2418 � r5 = 0.6371 > q2 = 0.4305� r5 = 0.6371 > q3 = 0.4403 � r5 = 
0.6371 < q4 = 0.8310 
 
então seleciona C4 
 
r6 = 0.5459 > q1 = -0.2418 � r6 = 0.5459 > q2 = 0.4305� r6 = 0.5459 > q3 = 0.4403 � r6 = 
0.5459 < q4 = 0.8310 
 
então seleciona C6 
 
Depois de selecionados, os cromossomos dão origem a uma nova população. 
 
C1’ = 0010100001 � gerados de C2 
C2’ = 0010100001 � gerados de C2 
C3’ = 0010010101 � gerados de C4 
C4’ = 1001101110 � gerados de C6 
C5’ = 0010010101 � gerados de C4 
C6’ = 0010010101 � gerados de C4 
 
2.2 Cruzamento 
 
É um processo no qual a combinação em partes de cada um de dois cromossomos gera um 
novo descendente. 
Seja o ponto k que define a posição de cruzamento na cadeia de bits de cada cromossomo 
escolhido aleatoriamente. A quantidade de cromossomos a ser submetida ao processo de 
cruzamento é definida através da probabilidade de cruzamento pc, especificada pelo usuário. 
Cada cadeia é partida neste ponto k e todas as informações de um cromossomo (A), a partir do 
ponto escolhido, são copiadas para um outro cromossomo (B) e vice-versa. 
O processo de escolha de quem será cruzado deve ser feito em pares, sorteando números 
randômicos (ri) em [0,1]. Quando não for possível formar os pares um novo sorteio deverá ser 
feito até obter os pares necessários para o cruzamento. Por exemplo, se ri for menor que a 
probabilidade de cruzamento pc, pré estabelecida, então o cromossomo (C1’) será selecionado. 
O valor da probabilidade de cruzamento pc = 25% tem sido adotada como um valor 
padrão (Braga, 1998). 
Após ter feito isso, temos que gerar um novo número randômico para determinar a 
posição k, onde novas cadeias são formadas pela roca de todos os caracteres compreendidos entre 
as posições k+1 e m. Esta posição k é determinada pela seguinte fórmula: 
 
k = 1 + rand [(m-1)-1] (2.6) 
 
Será submetida ao cruzamento a última população de cromossomos selecionada. Sejam os 
seguintes números randômicos (ri) 
 
r1 = 0,27 C1’> pc 
r2 = 0,20 C2’< pc 
r3 = 0,15 C3’< pc 
r4 = 0,17 C4’< pc 
r5 = 0,19 C5’< pc 
r6 = 0,50 C6’> pc 
 
sendo selecionado para o cruzamento os cromossomos C1’ e C2’, C3’ e C5’. 
Agora, é só gerar um número randômico e utilizando a equação (2.6) determinar k, a 
posição de cruzamento. 
 
Seja rand = 0.45; então: 
 
k = 1 + 0,45 [ ( 10 - 1 ) - 1 ] = 4,6 
 
Como k é um número inteiro, então k = 5. Logo, 
 
C2’ - 0010100001 
C3’ - 0010010101 
 
Trocando os caracteres, tem-se: 
 
C2” - 0010000001 
C3” - 0010110101 
e 
 
C4’ - 1001101110 
C5’ - 0010010101 
 
Trocando os caracteres, tem-se: 
 
C4” - 0010001110 
C5” - 1001110101 
 
Assim, após a aplicação do operador cruzamento, a população é dada por: 
 
C1” - 0010100001 
C2” - 0010000001 
C3” - 0010110101 
C4” - 0010001110 
C5” - 1001110101 
C6’ - 00100101012.3 Mutação 
 
A mutação é uma modificação aleatória do valor de um alelo da cadeia. Caso o alelo 
escolhido seja zero passa a ser um e vice-versa. 
Seleciona randomicamente uma posição em um cromossomo, obedecendo a probabilidade 
de mutação pm e muda o valor deste bit. 
O processo de mutação é controlado por um parâmetro fixo pm, probabilidade de mutação, 
que é geralmente recomendada como 1% (Braga, 1998). Este operador tem um papel importante 
e necessário, porque a reprodução e o cruzamento podem perder material genético 
potencialmente útil. O operador de mutação protege os algoritmos genéticos contra perdas 
irreparáveis. Tomada isoladamente, a mutação se constituiria na exploração aleatória do espaço 
das cadeias. Utilizada com cuidado, juntamente com os outros dois operadores, protege-se o 
procedimento da perda prematura de informações importantes (Braga,1998). 
Para aplicar o operador mutação ao exemplo em estudo, considere a população atual uma 
matriz (m x n), então torna-se necessário gerar 60 números randômicos r entre [0,1]. Se r for 
menor que a probabilidade pm = 0,01 será feita a mutação no bit correspondente. Considere que 
foram gerados 60 números r entre 0 e 1 e que quatro tiveram probabilidades menores que pm. 
Foram os seguintes números r: 
 
r3 = 0,007 < pm = 0,01 
r16 = 0,009 < pm = 0,01 
r45 = 0,0036 < pm = 0,01 
 
Considerando a população atual, 
 
C1” - 0010100001 
C2” - 0010000001 
C3” - 0010110101 
C4” - 0010001110 
C5” - 1001110101 
C6’ - 0010010101 
 
Submetendo os bits 3, 16 e 45 ao processo de mutação têm-se: 
 
C1” - 0000100001 
C2” - 0010010001 
C3” - 0010110101 
C4” - 0010001110 
C5” - 1001010101 
C6’ - 0010010101 
 
Após a aplicação dos três operadores, encerra-se o ciclo da primeira geração. Assim, é 
interessante observar como está ocorrendo a evolução dos cromossomos da população inicial. 
 
Veja o quadro abaixo: 
 
Cromossomos x f(x) 
C1” - 0000100001 0.2903 15.7162 
C2” - 0010010001 1.2757 6.6126 
C3” - 0010110101 1.5924 19.9158 
C4” - 0010001110 1.2493 4.5975 
C5” - 1001010101 5.2522 8.1512 
C6’ - 0010010101 1.3109 9.2224 
� )(xf 64.2157 
 
Comparando os valores da população inicial com os valores da ultima população é 
possível observar que a população inicial melhorou no sentido de caminhar em direção a 
maximização da função após aplicar os três operadores, pois os valores de � )(xf passaram de 
23.6106 para 64.2157. Executando outras iterações espera-se uma adaptação ainda melhor da 
população. 
A cada passo do processo de evolução uma nova geração é criada a partir da população 
anterior, e esta última é atualizada. Para que o processo de evolução possa ser considerado 
eficiente é necessário que em cada geração nova geração tenda a ser melhor (mais adaptado) que 
suas anteriores (Lucas, 2002) 
 
2.4 Finalização 
 
A finalização não envolve o uso de nenhum operador genético: ela simplesmente é 
composta de um teste que dá fim ao processo de evolução caso o AG tenha chegado a algum 
ponto pré-estabelecido de parada. Os critérios para a parada podem ser vários, desde o número de 
gerações já criadas até o grau de convergência da população (por convergência entende-se o grau 
de proximidade da avaliação de cada indivíduo da população). 
 O grau de convergência é característica das populações dos AGs, e diz respeito a 
diferença entre a média de adaptação da geração atual e suas anteriores. A ascensão deste índice 
indica que o processo de evolução está efetivamente promovendo a melhora da média de 
adaptação da população, e sua estabilização em torno de um mesmo valor por muitas gerações 
normalmente indica que a população se estacionou em um determinado valor médio de 
adaptação, caso em que a continuação do processo de evolução se torna improdutiva (Lucas, 
2002). 
 
Uma observação deve ser feita. Como a maioria dos códigos computacionais para 
algoritmos genéticos costuma maximizar funções e caso de problemas de minimizar uma função, 
a função objetiva pode ser reescrita como: 
 
min f(x, y, ...) = max [-f(x, y, ...)] 
 
 
3. RAÍZES E EQUAÇÕES NÃO LINEARES 
 
 O cálculo das raízes de equações não lineares, em particular, a determinação dos zeros de 
polinômios é um dos problemas mais antigos da matemática numérica. Dentro de certas 
condições, o problema pode se apresentar como mal condicionado. Isto faz com que a 
implementação de algoritmos numéricos para determinar as raízes de equações algébricas e 
transcendentes traga consigo grandes problemas, como instabilidade numérica e cancelamento 
catastrófico, dentre outros (Lopes et al, 1999). Por isso, neste trabalho, propõe-se uma nova 
alternativa para a resolução dessa classe de problemas. 
 
Um método numérico muito utilizado, no cálculo de raízes de equações, é o método de 
Newton Raphson (MNR). Este é determinado de tal forma que monta-se também um processo 
iterativo, mas realiza buscas locais, ou seja, para que haja a convergência para uma raíz necessita-
se de um intervalo pré determinado que contenha a raíz, não sendo uma condição de fácil acesso, 
visto que o teorema de convergência do método garante a existência do intervalo, mas não como 
determiná-lo. 
 
Teorema: Sejam ', ff e "f , funções contínuas num intervalo [a, b], onde existe uma raiz 
ξ . Supor que 0)(' ≠xf para x ∈ [a, b]. Então existe um intervalo [ ] [ ]baba ,, ⊂ , contendo a 
raiz ξ , tal que se x0 ∈ [ ]ba , , a seqüência {xn} gerada pelo processo iterativo 
 
)
1 ('
)(
n
n
nn
xf
xf
xx −=+ 
converge para a raiz. 
 
Para a solução de problemas de equações não lineares através da utilização de Algoritmos 
Genéticos procuramos o máximo de uma função objetiva. Ou seja, a solução de f(x) = 0 será 
obtida através da função objetiva (ou função de mérito) escrita como: 
 
max1 =mF - )(xf (2.7) 
 
Na próxima seção apresentamos resultados numéricos, que mostram as vantagens e 
desvantagens de cada método. 
 
4. RESULTADOS NUMÉRICOS 
 
GAOT (Genetic Algorithms Optimization Toolbox) executa evoluções simuladas no 
software Matlab usando medições binárias e representações reais. Suas bases de representações 
são adicionadas no toolbox desse software. Essas implementações são muito flexíveis nas 
operações genéticas, seleção e terminação de funções bem como avaliação das funções que 
podem ser usadas. Esse programa foi desenvolvido pela Universidade da Carolina do Norte, 
EUA, Houck et al (1995). Portanto para representar os exemplos através dos AGs será utilizado o 
GAOT , sendo possível acompanhar a evolução graficamente. 
Então a seguir será feita a implementação do algoritmo genético para a obtenção de raízes 
de equações não lineares utilizando uma precisão de quatro casas decimais para as raízes. O 
conjunto de equações testadas são exemplos clássicos, que apresentam um elevado grau de 
dificuldade para a obtenção de raízes usando métodos tradicionais. 
 
A título de ilustração, será testado duas funções utilizando os dois métodos (MNR e AG): 
 
Exemplo 1: Seja f(x) = e-x - x 
 
� Newton Raphson: 
 
Considerando que f(x) possui uma raíz no intervalo [0,1], procura-se uma aproximação 
usando x0 = 0.5 e �= 0.006, apresenta uma aproximação de x = 0.5671 com 2 iterações. 
Sendo, 
1)( −−=′ − xexf 
tem-se o processo iterativo 
)
1 ('
)(
n
n
nn
xf
xf
xx −=+ � 11 +
−
+=
−
−
+ x
x
nn
e
xe
xx 
 
assim, 
10
0
0
01
+
−
+=
−
−
x
x
e
xe
xx = 0.5663 � |x1 - x0| = 0.0663 > 0.006 
11
1
1
12
+
−
+=
−
−
x
x
e
xe
xx = 0.5671 � |x2 – x1| = 0.0008 < 0.006 
 
� Algoritmo Genético: 
 
Seja f(x) = e-x - x e g(x) = -f(x)a função de adaptação ou funçãoobjetiva. 
 
 
 
Figura 4.1 Gráfico de f(x) Figura 4.2 Gráfico de g(x) 
 
Figura 4.3 População inicial Figura 4.4 Seleção dos cromossomos melhores 
adaptados 
 
 
 
Figura 4.5 Melhor solução após o ciclo 
evolutivo 
 
 
Logo a raiz da equação converge para x = 0.5671 
 
 
Exemplo 2: Seja f(x) = e(-x.^ 2) * cos ( x* 3.5 * pi) 
 
� Newton Raphson: 
 
Esse é um exemplo em que o MNR tem problema. De acordo com o método montou-se 
uma tabela de 3 linhas e 7 colunas. Na primeira linha temos a condição inicial xo. Na segunda 
linha o resultado r que ele apresenta e na terceira linha a quantidade de iteração n. 
 
x0 0.5300 0.5400 0.5500 0.5600 0.5700 0.5800 0.5900 
r 0.7143 0.1429 -0.1429 -3.2857 1.5714 1.0000 0.7143 
N 6 4 5 5 5 5 7 
 
Observe que as condições iniciais mudam muito pouco e as raízes mudam muito. Isto é 
chamado de instabilidade do método. 
 
� Algoritmo Genético: 
 
 
Figura 4.1 Gráfico da função f(x). Figura 4.2 Gráfico da função objetiva g(x) = - 
|f(x)|. 
 
 
Figura 4.3 População inicial. Figura 4.4 Seleção dos cromossomos melhores 
adaptados. 
 
 
 
Figura 4.5 Melhor solução. 
 
Logo a raiz da equação converge para uma raiz x = 2.9573 
 
Para melhor sistematização será apresentado mais duas equações utilizando o AG. 
 
Exemplo 3: Seja f(x) = x*e-x^2 
 
 
Figura 4.1 Gráfico da função f(x). Figura 4.2 Gráfico da função objetiva g(x) = - 
|f(x)|. 
 
 
Figura 4.3 População inicial. Figura 4.4 Seleção dos cromossomos melhores 
adaptados. 
 
 
Figura 4.5 Melhor solução. Figura 4.6 Performance do algoritmo genético 
durante a evolução (número gerações x melhor 
aproximação). 
 
Na figura 4.6 a linha vermelha representa a melhor solução e a linha amarela representa a 
evolução da população. 
 
Logo a raiz da equação x*e-x^2 converge para x = 0 
 
 
Exemplo 3: Seja f(x) = (x-10)*x + 23 - x0.4 
 
Figura 4.1 Gráfico da função f(x). Figura 4.2 Gráfico da função objetiva g(x) = - 
|f(x)|. 
 
Figura 4.3 População inicial. Figura 4.4 Seleção dos cromossomos melhores 
adaptados. 
 
 
Figura 4.5 Melhor solução. 
 
Logo a raiz da equação converge para x = 3.1094 
5. CONCLUSÃO 
 
O presente estudo propôs a utilização de um outro recurso para o cálculo de raízes de 
equações não lineares: através dos algoritmos genéticos, levando assim a compreensão dos 
princípios fundamentais dessa técnica de otimização randômica, bem como permitiu o 
entendimento dos mecanismos dos operadores genéticos. 
 
Para encontrar a raíz procurada, a técnica de transformar o problema da resolução de 
equações não lineares em problema de maximização por meio de função de mérito, demostrou 
nos bons resultados, a eficiência da metodologia. 
 
Em seguida, dois exemplos foram submetidos a resolução através de um dos métodos 
numéricos mais usados (MNR) e através do AG. Então feita uma comparação tem-se as seguintes 
observações: 
 
i) O M.N.R. é também um método eficiente, mas realiza buscas locais, ou seja, 
procura a raíz da função dentro de um intervalo pré-determinado, encontrando 
assim, uma raíz de cada vez. 
 
ii) Ainda no M.N.R a condição de que para realizar a iteração é necessário um x0 
dentro do intervalo determinado, não é uma condição de fácil verificação, visto 
que o Teorema garante a existência do intervalo, mas não como determiná-lo. 
 
iii) Já o método AG mostrou bastante eficiente, não apresentando problema de mau 
condicionamento ou instabilidade numérica. Mas, segundo (Pérez, 2000), os AGs 
não trabalham sobre o domínio do problema, mas sim sobre representações de 
seus elementos. Tal fator impõe ao seu uso uma restrição: para resolver um 
problema é necessário que o conjunto de soluções viáveis para este possa ser de 
alguma forma codificada em uma população de indivíduos. 
 
iv) O fato também dos AGs não utilizarem funções de derivação é uma vantagem, 
pois evita cancelamento catastrófico. 
 
v) Observou-se em relação aos AGs a necessidade de tomar cuidado com o intervalo 
de busca, caso exista mais de uma raíz, pois haverá convergência para alguma das 
raízes dependendo dos valores que a população representar. A fase de isolamento 
necessária nos métodos clássicos de obtenção de raízes (Método de Newton 
Raphson) continua sendo importante. 
 
Considerando os aspectos observados através da comparação feita entre os dois métodos 
(MNR e AG) é possível concluir que o MNR continua sendo um método eficiente para resolução 
de uma larga escala de problemas, mas existem casos em que o M.N.R é falho como foi mostrado 
no exemplo 2. Por isso a obtenção de raízes de equações não lineares utilizando AGs se torna 
bastante eficaz por não apresentar problema de mal condicionamento ou de instabilidade 
numérica. 
 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
BRAGA, C. G. O uso de Algoritmos Genéticos para aplicação de Otimização de Sistemas 
Mecânicos. Dissertação de mestrado, Universidade Federal de Uberlândia, 1998. 
 
HAUPT, Randy L. e Haupt Sue E. Practical Genetic Algorithm. New York: John Wiley & Sons, 
Inc., 2002. 
 
HOLLAND, J. H. Adaptation in Natural and Artificial Systems. Ann Arbor: University of 
Michigan Press, 1975. 
 
BITTENCOURT, M. L. Applying c++ templates to the development of finite element classes. 
Computers & Structures (submetido), 1998. 
 
LUCAS, C. Diogo. Algoritmos Genéticos: uma Introdução. 2002. 
 
PÉREZ SERRADA, A. Una introducción a la computación evolutiva. Disponível via WWW em 
http://geocities.com/igoryepes/spanish.zip. (Setembro de 2000). 
 
HOUCK, J.A. Joines e M.G. Kay. A Genetic Algorithm for Function Optimization: 
a Matlab Implementation. NCSU-IE Technical Report,1995.