Utilizando um Algoritmo Genético para Encontrar os Zeros de
uma Função Real
Amarildo de Vicente1, Rogério Luis Rizzi1
1
Colegiado do Curso de Matemática – Centro de Ciências Exatas e Tecnológicas da
Universidade Estadual do Oeste do Paraná
Caixa Postal 711 – 85.819-110 – Cascavel – PR – Brasil
{amarildo,rogerio}@unioeste.br
Resumo. Este trabalho mostra a utilização de um algoritmo genético para obter as
raízes de uma função real em um intervalo específico. Sua finalidade principal é
apresentar um processo alternativo aos métodos convencionais, destinado aos casos
em que a função em questão oferece algum tipo de dificuldade a tais métodos. A
característica mais importante deste processo é que ele não requer que a função seja
derivável. Alguns testes realizados mostraram um desempenho a altura do que era
esperado.
Palavras chaves. Minimização, Zeros de funções, Algoritmo Genético.
1. Introdução
Encontrar os zeros de uma função real é um dos mais antigos problemas da matemática.
Os casos mais simples, funções lineares, quadráticas e cúbicas, podem ser resolvidos
algebricamente, todavia, para um caso mais geral, não há um modo padrão (fórmula)
para resolução. Na maioria dos casos torna-se necessário recorrer a um método numérico
para tal fim. No decorrer do tempo, métodos e mais métodos foram sendo criados, na
tentativa de se encontrar aquele que fosse o ideal. Pode-se citar, por exemplo, o clássico
método de Newton-Raphson, que funciona da seguinte forma: Dado um ponto inicial x0,
gera-se um sequência de pontos x1, x2,..., através da fórmula de recorrência
xn+1 = xn – f(xn)/f ´(xn)
Dependendo da função f esta sequência de pontos pode convergir para uma raiz r da
equação f(x) = 0, inclusive de forma bastante rápida. Um fator importante neste método é
a escolha do ponto de partida x0. Este ponto pode ser decisivo para a convergência da
sequência de pontos gerada. Em geral, quanto mais próximo de r ele estiver, maior será a
chance de convergência.
Outro método bastante conhecido é o método da bisseção. Este método consiste em
escolher um intervalo inicial [a0, b0] contendo uma raiz da equação f(x) = 0 e, a partir daí,
dividir sucessivamente este intervalo ao meio, de forma apropriada, até que se cerque a
raiz num intervalo de comprimento infinitesimal. Este método funciona muito bem,
embora seja muito lento. Maiores detalhes podem ser visto em [BURDEN, FAIRES,
2003].
Assim como no método de Newton-Raphson, que requer um ponto de partida
arbitrário, o método da bisseção requer que se tome um intervalo inicial que contenha a
raiz procurada. Para um algoritmo genético (AG) uma tentativa inicial também é
necessária. A diferença é que os pontos tomados inicialmente devem ser aleatórios dentro
de um intervalo específico, que não necessariamente precisa conter a raiz procurada.
De um modo geral, um AG é empregado para resolver um problema de otimização
(ver [REIS, AKUTSU,.2002], [SILVEIRA, BARONE, 1998]). Neste trabalho está sendo
proposta a adaptação de um AG, a fim de que ele sirva para encontrar as raízes reais de
uma função.
2. Metodologia
Para conseguir a adaptação citada anteriormente, em primeiro lugar é necessário lembrar
que se a equação f(x) = 0 possui uma raiz real r então o seu gráfico intercepta o eixo Ox
no ponto x = r. Para ilustração considere-se as funções f(x) = x – 2 e h(x) = x2 – 4x + 3,
cujos gráficos estão ilustrados na Figura 1.
7
y
7
6
6
5
5
4
4
3
3
2
2
1
−1
−1
1
x
1
2
3
4
5
6
7
y
8
−1
−1
x
1
2
3
4
5
6
7
8
Figura 1 – Gráficos das funções f e h
Nota-se que a função f possui uma raiz r1 = 2 e que a função h possui duas raízes, r2
= 1 e r3 = 3. Ao se fazer as composições gof e goh, onde g(x) = |x|, obtém-se as funções
F(x) = |x – 2| e H(x) = |x2 – 4x + 3|. Pode-se notar que as raízes destas funções ainda são
as mesmas, porém, os gráficos sofrem uma mudança, caracterizada por uma reflexão em
torno do eixo Ox (ver Figura 2).
7
7
y
6
6
5
5
4
4
3
3
2
2
1
−1
−1
1
x
1
2
3
4
5
6
7
y
8
−1
−1
x
1
2
3
4
5
6
7
8
Figura 2 – Gráficos das funções |f| e |h|
Com esta composição de funções resolvem-se dois problemas: o primeiro é que
eliminam-se os valores negativos da função original, que são impróprios para trabalho
com AG (ver seção 3.3); o segundo é que no ponto onde se encontram as raízes aparecem
pontos de mínimo, que é o alvo do AG que será apresentado. Este trabalho não tem como
pretensão apresentar um método que ofereça rapidez para encontrar a raiz de uma função,
já que isto não é característico de um AG. O objetivo é apenas apresentar um processo
alternativo para este tipo de problema.
3. Algoritmos Genéticos
São algoritmos de pesquisa inspirados na genética e no processo de seleção natural. Eles
tornaram possível explorar um espaço de soluções potenciais para um problema mais
amplo do que a maioria dos métodos convencionais.
Muitos organismos evoluem por meio de dois processos primários: seleção natural
e reprodução sexual. O primeiro determina quais membros da população sobrevive para
reproduzir e o segundo assegura diversificação e recombinação entre os genes de seus
descendentes (ver [MELANIE, 1998]).
Os algoritmos genéticos são fundamentados no fato de que na Natureza, apenas os
melhores indivíduos de uma espécie conseguem se adaptar ao meio em que vivem,
reproduzir e formar novas gerações. Com o passar do tempo, estes indivíduos melhor
adaptados tendem a predominar sobre os indivíduos mais fracos até eliminá-los. Os
algoritmos genéticos simulam este processo de reprodução natural e, para tal, necessitam
de uma representação artificial (codificação) para as criaturas. Dependendo do problema
em questão, esta representação pode ser feita por meio de cadeia de caracteres (palavras),
vetor, matrizes, etc. Além da representação dos indivíduos, é necessário, também,
processos que imitem a troca de informações genéticas que ocorre durante o cruzamento
de duas espécies, bem como a evolução ocorrida por causa de mutações. Tomando-se
então uma população inicial de indivíduos, deve-se escolher alguns destes para que sejam
feitos cruzamentos e mutações, a fim de que uma nova população seja obtida. É preciso
lembrar, no entanto, que os indivíduos que vão gerar esta nova população devem ser
aqueles melhor adaptados ao meio. A escolha destes indivíduos é feita de modo aleatório,
mas de forma que os indivíduos melhor adaptados tenham mais chances de serem
contemplados. Portanto, é necessário também criar um processo de seleção para tal fim.
3.1. Codificação
Dado um problema cuja solução pretende-se buscar por meio de algoritmos genéticos,
torna-se necessário primeiramente criar as estruturas que vão representar os indivíduos
que, por sua vez, vão formar a população. Estes indivíduos são nada mais que um
conjunto de elementos da mesma espécie da solução do problema, como, por exemplo,
vetores de números reais para um problema de otimização de uma função real, caminhos
de mínimo custo para a solução de um problema de roteirização, etc. A forma como os
indivíduos são representados varia de problema para problema e também de acordo com
a criatividade do pesquisador. Para o caso de uma população de números reais, a forma
mais tradicionalmente utilizada é a representação binária. Cada indivíduo é representado
por uma cadeia de caracteres, que por analogia à genética, recebe o nome de
cromossomo, formada por 0’s e 1’s (zeros e uns).
Ao ser dado um número amam-1...a0,b1b2...bn na base binária, composto por n dígitos
na parte inteira e m dígitos na parte fracionária, sua representação na base 10 será o
número
am2m + am-12m-1 + … + a020 + b12-1 + b22-2 + … bn2-n
Assim, o cromossomo 001001,01, por exemplo, representa o número 9,25, já que
0·25 + 0·24 + 1·23 + 0·22 + 0·21 + 1·20 + 0·2-1 + 1·2-2 = 9,25. O número de bits da cadeia
(oito no exemplo dado) vai de acordo com a conveniência ou do interesse do
programador.
O processo inverso, isto é, passar da base decimal para a binária, pode ser feito
através das divisões sucessivas para a parte inteira e das multiplicações sucessivas para a
parte fracionária (ver [SPERANDIO et al., 2003]).
3.2. Cruzamento
Dados dois cromossomos, o cruzamento é o processo pelo qual um novo ser é gerado
através destes. A ideia é que este novo indivíduo herde as características genéticas de
seus genitores (que geralmente são os melhor adaptados ao meio) para constituir um
indivíduo à altura ou melhor. Com repetidos processos de cruzamento espera-se que o
espaço de pesquisa seja devidamente explorado, de forma que as futuras populações
convirjam para a solução do problema. Existem várias formas de se fazer o cruzamento
entre dois cromossomos. Uma forma simples, para o caso da cadeia de caracteres, é
escolher um ponto aleatório para os dois cromossomos genitores e permutar entre si os
caracteres situados após o ponto escolhido. Por exemplo, cruzando os cromossomos
110100 e 101111 a partir da 4a posição, resulta nos cromossomos 110111 e 101100
respectivamente.
Esquematicamente tem-se:
genitores
descendentes
1101|00
→
110111
1011|11
→
101100
Outro modo também simples é escolher dois pontos dos cromossomos, ao invés de
um único ponto, e permutar entre ambos a parte compreendida entre tais pontos. Por
exemplo, cruzando-se os cromossomos 11010010 e 01101001 entre a 2 a e a 5a posição,
resulta nos cromossomos 11101010 e 01010001, respectivamente. De um modo
esquematizado tem-se:
genitores
descendentes
01|101|001
→
01010001
11|010|010
→
11101010
Pode-se, alternativamente, escolher apenas um ou ambos os cromossomos gerados
para compor a nova população.
3.3. Seleção
A seleção é o processo pelo qual dois indivíduos são escolhidos para gerarem um novo
ser. Os indivíduos são escolhidos aleatoriamente na população e, a rigor, todos têm
oportunidade de serem escolhidos. Todavia, o processo deve dar privilégio àqueles
melhor adaptados, qualidade dos indivíduos que é medida pelo seu fitness, termo que em
um problema de otimização representa o nível da função objetivo para o indivíduo
considerado.
Uma forma comumente utilizada para fazer a escolha é a regra da roleta. Ela
consiste em tomar um círculo e atribuir um setor do mesmo a cada um dos indivíduos.
Estes setores correspondem numericamente aos percentuais que os fitness dos indivíduos
representam sobre o todo (soma dos fitness de todos os indivíduos da população). Assim,
numa população de cinco indivíduos i1, i2, ..., i5, com fitness 12, 15, 18, 30 e 45, na
mesma ordem, o setor da roleta correspondente a cada um deles seria de 10.0%, 12.5%,
15.0%, 25.0% e 37.5%, respectivamente (Figura 3).
Figura 3 - Setores relativos aos cinco indivíduos considerados
A ideia é girar então a roleta e tomar como indivíduo sorteado aquele ao qual pertencer o
setor da mesma que parar sobre um ponto previamente marcado. Evidentemente os
indivíduos que possuem uma maior fatia na roleta têm mais chances de serem
selecionados.
Existem muitas outras maneiras de se fazer a seleção (ver [MELANIE, 1998]). De
acordo com o problema deve-se adotar aquela que for mais conveniente.
Seja f a função que representa o fitness (adaptabilidade) dos indivíduos de uma
população. Se o objetivo do problema é procurar o máximo valor de f, então, pela regra
da roleta, a probabilidade de um indivíduo ser escolhido para reprodução pode ser
calculada por
p i =
f i
N
∑i =1
f i
onde i é um indivíduo da população, e N é o tamanho desta (no de indivíduos). Observe
que para que esta expressão faça sentido, é necessário que f(i) ≥ 0 ∀i e que f(i) > 0 para
algum i.
Com os processos descritos, fica estabelecido um ciclo que pode ser sintetizado
pelo esquema apresentado na Figura 4 abaixo.
População antiga
Cruzamentos e Mutações
Populaçãonova
Figura 4 – Esquema do funcionamento de um algoritmo genético
De forma resumida, um algoritmo genético bastante simples funciona de acordo
com as etapas a seguir.
Algoritmo 1
Dados iniciais:
K: Número de indivíduos da população.
N: Número de descendentes a serem gerados em cada geração.
M: Número máximo de gerações.
1. Gere uma população inicial com K indivíduos.
2. Calcule o fitness de cada indivíduo da população.
3. Para m = 1 até M faça:
4. Para n = 1 até N faça:
5. Selecione dois indivíduos da população (pais).
6. Faça o cruzamento entre eles gerando um novo indivíduo e aplique a ele
uma mutação se for necessário.
7. Calcule o fitness deste novo indivíduo.
8. Fim n.
9. Substitua alguns ou todos os elementos da população atual pelos indivíduos
gerados, formando uma nova população.
10. Fim m.
Os parâmetros K, N e M são tomados de forma arbitrária, e o desempenho devido a
eles depende do problema em questão. Obviamente esta escolha está também
condicionada às limitações do computador que está sendo utilizado.
4. Cálculo do Fitness para um Problema de Minimização
Em um AG, a escolha de pais que vão gerar novos descendentes é feita com base no
valor esperado de cada indivíduo da população (número esperado de filhos que deve
gerar) e, este valor esperado por sua vez, é calculado com base no fitness de cada um
destes indivíduos. Há uma diversidade muito grande de métodos para se fazer o cálculo
do valor esperado dos indivíduos. Neste contexto será utilizado o método da
proporcionalidade do fitness. Só que, como se trata de um problema de minimização, será
utilizada a proporcionalidade inversa, isto é, quanto menor for o fitness do indivíduo,
maior será a sua chance de ser escolhido. O processo utilizado para determinar a
probabilidade de um indivíduo i ser selecionado será
p i =
1/ f i
N
∑i=1 1/ f i
onde N é o tamanho da população e f(i) é o fitness do indivíduo i.
Outra questão que dever ser notada é que, como está sendo procurado um ponto de
mínimo, que no caso é a raiz da função f, poderemos ter uma divisão por zero na fórmula
anterior. Isto no entanto pode ser contornado facilmente, bastando para isto
acrescentaremos um valor c pequeno e positivo, à função| f|. Isto não muda seu ponto de
mínimo e resolve o problema mencionado.
5. Intervalo de Pesquisa
Ao se estipular uma quantidade de k bits para um número binário x não negativo,
contendo m dígitos na parte inteira e n dígitos na parte fracionária, o maior valor possível
para x é 2m – 2–n. Desta forma, os valores x possíveis de serem produzidos se encontram
no intervalo [0, 2m – 2–n]. Para distribuir estes valores em um intervalo de pesquisa
específico I = [a , b], basta aplicar a bijeção f(x) = a + (b – a)/( 2m – 2–n)x. Por exemplo, o
número binário y = 00110 corresponde ao número decimal x = 12. A imagem
aproximado de y no intervalo [-2, 2] é f(12) = -2 + (2 – (2))/(25 – 20)12 = – 0,4516.
O procedimento para achar as raízes de uma função f por meio de um AG, com
uma precisão ε, pode ser descrito como segue:
Algoritmo 2
Dados iniciais
f: função cujas raízes se deseja obter.
p: precisão a ser atingida pelas raízes na fase de isolamento.
ε: precisão final a ser atingida pelas raízes.
1. Construa a função F(x) = |f(x)| + c, onde c > 0 e pequeno.
2. Especifique um intervalo de pesquisa I = [a, b].
3. Aplique um AG para minimizar F(x) e guarde uma cópia de cada ponto que satisfaz a
precisão p. Estes pontos são candidatos a raízes.
4. Enquanto houver candidatos a raízes faça:
5. Selecione um destes pontos
6. Repita
7. Reduza gradativamente o intervalo de pesquisa em torno desta raiz.
8. Aplique o AG para minimizar F.
9. Até que a precisão ε seja atingida.
10. Fim enquanto.
Notas: Se a precisão exigida for muito grande, isto é, se ε for muito pequeno, o
procedimento acima pode ser demorado. Por este motivo este processo é mais
recomendado a funções para as quais os métodos tradicionais podem apresentar algum
tipo de insegurança (funções não deriváveis, funções descontínuas, funções com diversos
pontos de mínimo, etc.). Outro detalhe é que no final do passo 3 pode-se obter muitos
pontos, todos candidatos a uma mesma raiz (ver seção a seguir). Neste caso basta nos
preocuparmos com apenas um deles. Também é possível encerrar o processo no passo 3
se a precisão p for suficiente para satisfizer o interesse do pesquisador.
6. Testes computacionais
Considere-se a função f(x) = |e– x – x + l| e uma precisão ε = 0.0005. De acordo com o
Algoritmo 2, tomando-se c = 10-4, então a função a ser minimizada é F(x) = |e – x- x + l| +
10-4 . Executando-se o algoritmo acima com uma população de 40 indivíduos, 60
gerações, cromossomos com k = 10 bits (2 na parte inteira e 8 na parte fracionária),
precisão p = 0.05 e intervalo de pesquisa [0,10], foram encontrados, dentre outros mais
ou menos próximos, os seguintes pontos de mínimo (raízes aproximadas): 1.309873,
1.251222, 1.270772 e 1.290328. Note-se que à primeira vista estes pontos parecem
representar aproximações para uma mesma raiz. Fazendo-se então refinações sucessivas
no intervalo de pesquisa e empregando a precisão ε chega-se a raízes aproximadas,
dentre as quais r1 = 1.2788484 e r2 = 1.278485. Evidentemente r1 e r2 são aproximações
de uma mesma raiz para f. O último intervalo pesquisado foi [1, 1.5].
Seja a função h(x) = x5 + 3.6x4 + 6.33x3 + 13.35x2 + 9.32x - 4.2 e uma precisão ε =
0.0005. Da mesma forma como foi feito anteriormente, deve-se minimizar a função H(x)
= |x5 + 3.6x4 + 6.33x3 + 13.35x2 + 9.32x - 4.2 | + 10-4. Trabalhando-se com as mesmas
configurações do caso anterior foi possível encontrar, no intervalo [-10, 10], os seguintes
pontos candidatos (raízes aproximadas): -2.499580, -1.403983 e 0.300922. Note que há
três possíveis raízes neste intervalo. Fazendo-se um refinamento do intervalo de pesquisa
para cada uma deste valores, agora com precisão ε, chega-se às seguintes raízes: r1 =
-2.500014, r2 = -1.400037 e r3 = 0.300008. Os intervalos finais pesquisados para cada
uma destas raízes foram [-2.4, -2.5], [-1.4, -1.5] e [0, 0.5], respectivamente.
7. Conclusões
1. Conforme explicitado ao longo do texto, o objetivo do trabalho era apresentar um
método alternativo aos convencionais, destinado principalmente aos casos de funções que
oferecem algum tipo de dificuldade a estes métodos. Como poder ser observado, a função
f(x) = |e– x – x + l| pode ser enquadrada nestes casos, visto que ela não possui derivada no
ponto onde ocorre sua raiz. Mesmo com este problema o processo proposto funcionou
bem, de acordo com as expectativas. Evidentemente o processo funciona também para as
funções de composição mais simples, como a função h ilustrada na seção anterior.
2. Outro fato que não foi levado em consideração foi o tempo de processamento
consumido pelo processo. Embora seja sabido que, sob este aspecto ele não é competitivo
com os métodos convencionais, pode-se dizer que o tempo gasto nos exemplos
apresentados em um computador de 3.06 Ghz foi irrisório (cerca de 0,06 segundos).
8. Referências
BURDEN, R. L; FAIRES, D. J. Análise Numérica. Editora Pioneira Thomson Learning,
São Paulo, 2003. 740p.
GOLDBERG, David. Genetic Algorithms in Search, Optimization & Machine Learning.
Addison-Wesley, 1989. 121p.
MELANIE, M. An Introduction to Genetic Algorithms. Bradford Bood, 1996.
Disponível em “http://www.df.uba.ar/~marcos/Intro_to_GA_Mitchell.pdf”. Acesso
em 22/set/2010.
REIS, L. F. R.; AKUTSU, J. Estratégias Operacionais para Sistemas de Reservatórios
Via Algoritmos Genéticos (Ags). Revista Brasileira de Recursos Hídricos, Vol. 7, n. 2,
5-7, jul/set 2002. Disponível em
“http://www.abrh.org.br/novo/arquivos/artigos/v7/v7n3/v73_01estrategiasfinal.pdf”.
Acesso em 22/09/2010.
SILVEIRA, S. R.; BARONE, D. A. C. Jogos Educativos Computadorizados Utilizando a
Abordagem de Algoritmos Genéticos, IV Congresso RIBIE, Brasília, 1998.Disponível
em
“http://www.niee.ufrgs.br/eventos/RIBIE/1998/pdf/com_pos_dem/151.pdf”. Acesso
em 22/set/2010.
SPERANDIO, D.; MENDES, J. T.; SILVA, L. H. M. Cálculo Numérico: Características
Computacionais dos Métodos Numéricos. Ed. Prentice Hall, São Paulo, 2003.354p.