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.
cromossomo
X1
X2
gene
X3
X4
...
Xn
1 0 1 1 0
alelo
1
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 101101011001
x
y
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 submetendoas 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:
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
Os procedimentos aplicados serão detalhados na seqüência
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.
Pi =
f ( x)
, sendo F ( x) =
F ( x)
f ( xi )
(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)
x=
m −1
i =0
bi × 2 i e y =
m −1
i =0
ai × 2 i
(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:
x = ai + x
bi − a i
2m − 1
b −a
y = ai + y i m i
2 −1
(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)
x=
m −1
i =0
bi × 2 i = 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
x=
m −1
i =0
bi × 2 i =
Os valores reais de x dentro da região viável, são dados por:
x = ai + x
x = 0 + 341
bi − ai
2m − 1
9−0
= 5.7713
210 − 1
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
1010010000
0010100001
1000010001
0010010101
1000010101
1001101110
f (x)
x
5.7713
1.4164
4.6540
1.3109
4.6891
5.4721
f(x)
-5.7099
15.8734
0.2334
9.2224
0.0372
3.9541
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:
qi =
i
j =1
Pj
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
(2.5)
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
0.7138 < q4 = 0.8310
r3 = 0.7138 > q2 = 0.4305
r3 = 0.7138 > q3 = 0.4403
r3 =
r4 = 0.9776 > q1 = -0.2418
r4 = 0.9776 > q2 = 0.4305 r4 = 0.9776 > q3 = 0.4403
0.9776 > q4 = 0.8310 r4 = 0.9776 > q5 = 0.8325 r4 = 0.9776 < q6 =1,0000
r4 =
então seleciona C4
então seleciona C6
r5 = 0.6371 > q1 = -0.2418
0.6371 < q4 = 0.8310
então seleciona C4
r5 = 0.6371 > q2 = 0.4305
r5 = 0.6371 > q3 = 0.4403
r5 =
r6 = 0.5459 > q1 = -0.2418
0.5459 < q4 = 0.8310
r6 = 0.5459 > q2 = 0.4305
r6 = 0.5459 > q3 = 0.4403
r6 =
então seleciona C6
Depois de selecionados, os cromossomos dão origem a uma nova população.
C1’ = 0010100001
C2’ = 0010100001
C3’ = 0010010101
C4’ = 1001101110
C5’ = 0010010101
C6’ = 0010010101
gerados de C2
gerados de C2
gerados de C4
gerados de C6
gerados de C4
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
r2 = 0,20
r3 = 0,15
r4 = 0,17
r5 = 0,19
C1’> pc
C2’< pc
C3’< pc
C4’< pc
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’ - 0010010101
2.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
C1” - 0000100001
C2” - 0010010001
C3” - 0010110101
x
0.2903
1.2757
1.5924
f(x)
15.7162
6.6126
19.9158
C4” - 0010001110
C5” - 1001010101
C6’ - 0010010101
f (x)
1.2493
5.2522
1.3109
4.5975
8.1512
9.2224
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
f (x) 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 necessitase 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 f , f 'e f " , funções contínuas num intervalo [a, b], onde existe uma raiz
ξ . Supor que f '( x) ≠ 0 para x ∈ [a, b]. Então existe um intervalo [a , b ] ⊂ [a, b] , contendo a
raiz ξ , tal que se x0 ∈ [a, b ] , a seqüência {xn} gerada pelo processo iterativo
x n +1 = x n −
f ( xn )
f '( x n )
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:
Fm1 = max - f (x)
(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,
f ′( x) = −e − x − 1
tem-se o processo iterativo
f ( xn )
e−x − x
x n +1 = x n −
x n +1 = x n + − x
f '( x n )
e +1
assim,
e − x0 − x 0
e − x0 + 1
e − x1 − x
x 2 = x1 + − x1 1
e +1
x1 = x 0 +
= 0.5663
|x1 - x0| = 0.0663 > 0.006
= 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ção objetiva.
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
r
N
0.5300
0.7143
6
0.5400
0.1429
4
0.5500
-0.1429
5
0.5600
-3.2857
5
0.5700
1.5714
5
0.5800
1.0000
5
0.5900
0.7143
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.