Anais do I WORCAP, INPE, São José dos Campos, 25 de Outubro de 2001, p. 42 - 44
Algoritmo Genético Híbrido como Solução para Problemas Numéricos
Felipe Leonardo Lôbo Medeiros*, 1, Lamartine Nogueira Frutuoso Guimarães**, 2
(1)Inteligência Artificial
Laboratório Associado de Computação e Matemática Aplicada
Instituto Nacional de Pesquisas Espaciais (INPE)
(2)Divisão de Energia Nuclear
Instituto de Estudos Avançados (IEAv)
(*)Mestrado, Bolsa CAPES, e-mail: [email protected] (**) Orientador e-mail:
[email protected]
Resumo
Este trabalho propõe a utilização da técnica de Inteligência Artificial denominada algoritmo genético
híbrido, para solucionar o problema da determinação de estados estacionários de sistemas dinâmicos
lineares e não lineares, em função de parâmetros do próprio sistema. O desenvolvimento dos métodos
mutação heurística, mutação heurística não uniforme e epidemia também é proposto. O problema que se
quer resolver consiste em solucionar sistemas lineares e não lineares do tipo AX + B = 0, encontrando o
vetor X solução do sistema. Problemas deste tipo normalmente apresentam comportamento multi-modal,
com alto índice de mínimos e máximos locais. Algoritmos genéticos têm sido aplicados com eficiência a
problemas com tal comportamento. Bons resultados foram obtidos a partir de testes com dois modelos
dinâmicos de um gerador de vapor, dados por sistemas de ordem três e cinco da forma AX + B = 0.
Palavras-Chave: estados estacionários, sistemas dinâmicos, algoritmo genético híbrido, resultados
1-Introdução
As simulações de muitos artefatos científicos e de engenharia, são realizadas através de
representações matemáticas destes, dadas por sistemas de equações diferenciais ordinárias. Tais sistemas
necessitam de estados estacionários bem determinados, a partir dos quais, efeitos de transitórios possam
ser testados e avaliados. A determinação do estado estacionário de um sistema dinâmico linear ou não
linear baseia-se em solucionar o sistema matricial dado por AX + B = 0, o qual contém a dinâmica do
processo. Porém as soluções exatas ou aproximadas de diversos sistemas são impossíveis para exemplos
realísticos, devido ao tamanho do sistema e à complexidade de modelos não lineares ([3]). A utilização de
algoritmos genéticos surge como solução para tais problemas, pois têm sido aplicados com eficiência na
determinação de soluções aproximadas de sistemas de elevada ordem, e de sistemas que apresentam
comportamento multi-modal e/ou são não diferenciáveis ([5]).
2-Algoritmo Genético
Basicamente, algoritmo genético é um método de busca global que simula a teoria da evolução para
solucionar um determinado problema. Consiste em simular a evolução de uma população de indivíduos,
onde cada indivíduo representa uma possível solução do problema. Inicialmente, uma população é
formada através da criação aleatória dos seus indivíduos. Cada indivíduo é avaliado e recebe um valor
denominado valor de aptidão. O valor de aptidão representa o quão próxima da solução, está a possível
solução representada pelo indivíduo. Baseados nos valores de aptidão, são selecionados os indivíduos que
serão utilizados na etapa de reprodução. Na reprodução, novos indivíduos são obtidos a partir da
aplicação de operadores genéticos nos indivíduos selecionados. As gerações são criadas até que uma
condição de parada seja satisfeita. Uma condição de parada pode ser alcançar um determinado valor de
aptidão ou um número máximo de gerações. Um algoritmo genético híbrido será utilizado e elaborado
através da união de um algoritmo genético convencional com um método de busca local. Este método é
uma solução para os problemas multi-modais e consiste em dividir o espaço de busca em NP regiões, e
fazer com que um mesmo número de populações explore cada uma destas regiões (semelhante ao método
de formação de nichos [4]).
3-Metodologia
A aplicação de algoritmo genético exige a modelagem do problema ao qual será aplicado. A
modelagem consiste na especificação do indivíduo, função de aptidão, população ou populações, seleção,
operadores genéticos e métodos auxiliares como o método epidemia.
3.1-Indivíduo
Anais do I WORCAP, INPE, São José dos Campos, 25 de Outubro de 2001, p. 42 - 44
A obtenção do estado estacionário de um sistema dinâmico linear ou não linear baseia-se em
solucionar o sistema apresentado na forma matricial AX + B = 0, encontrando o vetor X solução do
sistema. Para o problema proposto, cada indivíduo representa um vetor X e é composto por uma estrutura
formada por um vetor de números reais e por um valor de aptidão. A representação segue as mesmas
características da representação real proposta por Michalewicz ([3]). O vetor é formado por N números
reais, e representa todos os componentes do vetor X, onde N é a ordem do sistema. O esquema de um
indivíduo indi é apresentado :
x2
x1
...
xN
Figura 1 – representação dos componentes do vetor X representado pelo indivíduo.
Valor de aptidão de indi = Fapi (indi)
Onde : indi representa um indivíduo. Os componentes xj , j=1, ..., N, representam os componentes do
vetor X, que é representado pelo indivíduo indi (i = 1, ..., TP). TP é o tamanho da população.
3.2-Populações
Um número NP de populações é utilizado com o objetivo de explorar NP regiões do espaço de busca.
Cada componente do indivíduo representa um parâmetro do sistema dinâmico, portanto possui um
domínio finito, isto é, um intervalo fechado de variação de valores. A divisão do espaço de busca consiste
em dividir o domínio de um componente xj (j = 1 , ... , N) do indivíduo em NP regiões. O componente
escolhido para pivô da divisão, é o componente do vetor X (representado pelo indivíduo) que possui o
maior domínio ([LI , LS]).
xk componente que apresenta o maior domínio [LI , LS].
R1 – [LI , ls1]
R2 – [li1 , ls2]
R3 – [li2 , ls3]
...
RNP – [liNP-1 ,LS ]
P2
P3
...
Figura 2 – representação da divisão do espaço de busca
P1
PNP
Onde : Ri representam cada região do espaço de busca. Pi (i = 1, ..., NP) representam as populações.
LI e LS representam os limites iniciais inferior e superior do domínio do componente xk. lir e lsr (r = 1, ...,
NP -1) representam os limites inferiores e superiores das regiões do espaço de busca.
3.3-Função de Aptidão
A função de aptidão elaborada para o problema proposto, é baseada na própria equação do sistema. A
possível solução representada por um indivíduo é a solução do sistema quando todas as componentes do
vetor S (onde S = AX + B) forem iguais a zero. A aproximação do vetor X representada pelo indivíduo é
utilizada na equação do sistema. O vetor S sofre uma interpretação pois, se cada componente do vetor S
se aproxima de zero indica que o vetor X, representado pelo indivíduo, se aproxima da solução do
sistema. Então, quanto menor o valor de aptidão, mais apto é o indivíduo.
Fapi (indi) =
n
∑
j =1
s
j
, onde S = AX + B e n é a ordem do sistema. Fapi (indi) representa o
valor de aptidão do indivíduo indi (i = 1, ..., TP).
S = [ s1
s2
s3
...
sn ]
3.4-Seleção
O método elitismo está sendo utilizado. Este método força o algoritmo genético a reter algum número
de melhores indivíduos a cada geração. A eficiência do algoritmo genético é garantida com a seleção,
pois os indivíduos mais aptos apresentam maior tendência a serem selecionados e a emitir seu código
genético pelas próximas gerações.
3.5-Operadores Genéticos
Os operadores genéticos são responsáveis pela reprodução da população. Estes simulam os
operadores genéticos existentes nos seres vivos. Três tipos de operadores serão utilizados : recombinação
genética geométrica ou crossover geométrico, mutação heurística e mutação heurística não uniforme.
3.5.1-Crossover Geométrico
Anais do I WORCAP, INPE, São José dos Campos, 25 de Outubro de 2001, p. 42 - 44
O crossover geométrico, proposto por Michalewicz ([2]), gera um novo indivíduo (filho) por meio de
dois indivíduos pais.
indk’ = { y1 , y2 , y3 , ... , yN } , k e k’ = 1, ..., N
Pais : indk = { x1 , x2 , x3 , ... , xN }
CrossoverGeométricoMichalewicz (indk , indk’) = {
x1 y1 , x2 y2 ,
x3 y3 , ... ,
xN y N }
Onde : N é a ordem do sistema neste caso.
3.5.2-Mutação Heurística e Mutação Heurística Não Uniforme
Estes operadores genéticos geram um novo indivíduo a partir de um indivíduo pai. A mutação
heurística consiste em adicionar ou subtrair um determinado valor v a um componente xi (i = 1, ..., N)
selecionado aleatoriamente no indivíduo. O valor v afetará o componente de acordo com o valor de
aptidão do indivíduo. Para um indivíduo pouco apto, o valor v deve ser alto para efetuar uma forte
alteração no componente xi representado no indivíduo. Para um indivíduo muito apto, o valor v deve ser
baixo com o objetivo de realizar apenas um ajuste fino no componente xi. A mutação heurística não
uniforme diferencia-se por efetuar a operação em todos os componentes do indivíduo pai.
4-Epidemia
O procedimento evita que a população permaneça em um mínimo local. O procedimento consiste em
verificar se a população tende a um mínimo local. Quando a população tende a um mínimo local,
verifica-se se o melhor indivíduo atual é mais apto que o melhor indivíduo armazenado anteriormente : se
for mais apto ele é armazenado substituindo o outro e a população é novamente gerada; se o melhor
indivíduo atual não for mais apto, a população é novamente gerada e o indivíduo armazenado
anteriormente é copiado para a nova população.
5-Desenvolvimento de um Protótipo e Testes
Um protótipo de um algoritmo genético foi elaborado e implementado seguindo as especificações
descritas na metodologia. Testes foram realizados com o objetivo de determinar as condições iniciais de
um modelo dinâmico de um gerador de vapor dado por um sistema de ordem cinco da forma AX + B = 0.
Este modelo foi proposto por Guimarães e Flores ([1]). Alguns resultados são apresentados :
N. de gerações
x2
x3
x4
x5
x1
Artigo
292.2475
282.2662
279.9821
275.8742
5.7566
Teste 1
292.055
281.972
279.664
275.514
5.72221
1528
Teste 2
292.16
282.13
279.834
275.706
5.74041
993
Tabela comparativa entre as aproximações (vetores X) do artigo e as encontradas nos testes 1 e 2.
Condição de parada : valor de aptidão < 0.01. As aptidões das aproximações de solução apresentadas
nos testes 1 e 2 são respectivamente : 0.00871879 e 0.00998337. Taxa de crossover e mutação iguais a
100% e 5% respectivamente. Número de populações (NP) igual a 6 e tamanho de cada população (TP)
igual a 200.
Obs. : O procedimento epidemia e as mutações heurística e heurística não uniforme foram utilizadas
em todos os testes. Resultados satisfatórios também foram obtidos utilizando-se apenas uma população.
6-Referências
[1] Guimarães, L.; Flores, P. T. Modelos Dinâmicos Simplificados de Gerador de Vapor como
Ferramenta de Ensino, CTA / IEAv / EAN-R, 1997.
[2] Melville, B. Steady-state Simulation of Large Nonlinear Systems, Mathematical Modeling in
Industry-A Workshop for Graduate Students, (1996).
[3] Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1996.
[4] Parthasarathy, P.; Goldberg, D.; Burns, S. Tackling Multimodal Problems in Hybrid Genetic
Algorithms, Department of General Engeneering, Umiversity of Illinnois, 2001.
[5] Tsutsui, S.; Fujimoto, Y. Forking Genetic Algorithm with Blocking and Shrinking Modes (fGA).
In: Proceedings of the Fifth Internacional Conference on Genetic Algorithms. University of
Illinois, 1993, 206-213.