O Impacto do Processamento Paralelo na Otimização de Projeto

Index
O IMPACTO DO PROCESSAMENTO PARALELO NA OTIMIZAÇÃO DE PROJETO NEUTRÔNICO DE
REATOR ATRAVÉS DE ALGORITMO GENÉTICO
1,2
Cláudio M. N. A. Pereira,
1
Celso M. F. Lapa e
1
Antônio C. A. Mol
1
Comissão Nacional de Energia Nuclear - IEN/DIRE e DICH
Caixa Postal 68550, Ilha do Fundão s/n, 21945-970, Rio de Janeiro, Brasil
[email protected], [email protected] e [email protected]
2
Universidade Federal do Rio de Janeiro - COPPE/PEN
Caixa Postal 68509, 21945-970, Rio de Janeiro, Brasil
[email protected]
RESUMO
Atualmente, diversos problemas de otimização encontrados na engenharia nuclear vêm sendo
solucionados através de algoritmos genéticos (AGs). A robustez de tais algoritmos, no entanto, está
fortemente ligada à natureza de seu processo de busca que baseia-se "populações" de candidatos à
solução do problema, fato este que implica em elevado custo computacional no processo de
otimização. A utilização de AG torna-se ainda mais crítica quando o processo de avaliação de um
candidato à solução é computacionalmente custoso. Problemas desta natureza são comuns na
engenharia nuclear, e como exemplo, pode-se citar a otimização de projetos de reatores, onde
códigos neutrônicos que consomem elevado tempo de CPU precisam ser executados. Com o objetivo
de investigar o impacto da utilização da computação paralela na solução, através de AG, de um
problema de otimização em projeto neutrônico, desenvolveu-se um algoritmo genético paralelo
(AGP) sob o paradigma do Modelo de Ilhas. Exaustivos experimentos, envolvendo mais de 1500
horas de processamento em computadores pessoais de 550 MHz, foram feitos para que se pudesse
comparar o AG convencional com o AGP. Tais experimentos demonstram a superioridade do AGP,
não só no que se refere ao tempo de execução, mas também ao resultado da otimização.
Keywords: neutronic design, parallel computation, genetic algorithms.
I. INTRODUÇÃO
Com o surgimento de computadores com maior
capacidade processamento e memória, diversas técnicas
computacionais de software puderam sair de um escopo
puramente acadêmico para o mundo real, proporcionando
aplicações práticas de grande valor, nas diversas áreas do
conhecimento. A exemplo disto, pode-se citar a
Computação Evolucionária (CE), que engloba poderosas
técnicas de otimização, aplicáveis à problemas de difícil
solução através de métodos tradicionais, mas que, em
contrapartida, demanda alto custo computacional.
Atualmente, já são observadas diversas aplicações
práticas bem sucedidas da CE na área nuclear [1-6].
Existem, entretanto, problemas, cujo custo computacional
associado à avaliação de um único candidato a solução, por
si só, já é elevado. Nestes casos, a utilização da CE ainda
esbarra no limite da capacidade de processamento dos
computadores comuns geralmente disponíveis. Muitas
vezes, devido à não aplicabilidade de outras técnicas, ainda
assim, a CE é utilizada. Mesmo que com certo prejuízo com
relação aos resultados da otimização, há ganhos que
justifiquem tal aplicação.
Uma das formas de sobrepor tal restrição com
relação a aplicação de técnicas de CE, é a utilização de
computação paralela. Neste trabalho, é investigado o
impacto da aplicação da computação evolucionária paralela
a um problema clássico da engenharia nuclear, envolvendo
alto custo computacional – a otimização do projeto
neutrônico de um reator. Para isto, desenvolveu-se um
Algoritmo Genético [7] (uma técnicas popular da CE)
Paralelo (AGP) sob o paradigma do Modelo de Ilhas [8],
para execução distribuída em rede local de computadores.
Exaustivos experimentos, envolvendo mais de 1500 horas
de processamento em computadores pessoais de 550 MHz
da rede local do Instituto de Engenharia Nuclear (CNEN),
foram feitos com objetivo de comparar a performance do
AGP proposto com a do algoritmo genético tradicional nãoparalelo (AGT). Os resultados obtidos apontam para uma
evidente superioridade do AGP sobre AGT, não apenas em
termos do tempo despendido no processo de otimização,
mas também na qualidade dos resultados obtidos.
Index
II. ALGORITMO GENÉTICO: MODELO DE ILHAS
III. O PROBLEMA PROPOSTO
Algoritmos genéticos (AGs) são técnicas de
otimização inspiradas nos mecanismos de seleção natural e
evolução das espécies. Baseiam-se na evolução de
populações de candidatos à solução do problema a ser
otimizado. Tal evolução se dá de tal forma que os
candidatos mais adaptados se mantenham e se recombinem
entre si, gerando populações mais adaptadas a cada geração.
A avaliação do nível de adaptação do candidato é função
dos objetivos e restrições do problema de otimização
considerado.
A cada geração o AG precisa calcular o nível de
adaptação de toda a população, o que torna o processo de
otimização bem mais demorado, quando comparado com a
otimização via técnicas tradicionais. Os AGs destacam-se,
entretanto, por sua robustez na otimização em escopo global
e aplicabilidade a problemas onde não se tem conhecimento
a priori do espaço de busca.
Em problemas onde a avaliação de um candidato à
solução já implica em elevado custo computacional, os AGs
podem ter sua aplicação comprometida, em parte, ou
totalmente. Uma forma de sobrepor essa dificuldade é a
paralelização do AG. Como a avaliação de cada candidato
de uma população é independente, estas poderiam ser feitas
ao mesmo tempo.
Os modelos de AGs paralelos (AGPs), no entanto,
vão além da simples paralelização do processo de avaliação
dos candidatos (modelo Mestre-Escravo). Usufrui-se
também do paralelismo para se obter modelos mais robustos
e eficazes, destacando-se dois deles: o modelo Celular e o
Modelo de Ilhas. Por necessitar de pouca comunicação
entre processadores, este último é o que melhor se adapta
em arquiteturas computacionais distribuídas, como uma
rede de computadores.
No Modelo de Ilhas, AGs independentes são
alocados, cada um em um processador (ilha). Os AGs
evoluem paralelamente, trocando informação através do
processo (operador) de migração, onde indivíduos de uma
ilha migram para outra, com intuito de promover uma
evolução global com maior diversidade do espaço de busca.
Tal aumento de diversidade, devido à colaboração entre as
ilhas, possibilita ganhos nos resultados da otimização. Neste
trabalho, utilizou-se a topologia em anel, onde o melhor
indivíduo migra para a ilha subseqüente, conforme
esquematizado na Fig. 1.
Como o principal objetivo deste trabalho é analisar
os ganhos referentes à utilização de computação paralela,
escolheu-se um problema anteriormente abordado [1], na
ocasião, submetido à aplicação de um algoritmo genético
tradicional (AGT). O problema abordado é um projeto
simplificado do núcleo de um reator hipotético com 3 zonas
de enriquecimento e cuja célula característica é composta
apenas de moderador, revestimento e combustível,
conforme Figura 2.
Ilha
1
Ilha
N
Ilha
2
Ilha
4
Ilha
3
Figura 1. O Modelo de Ilhas.
R2
R1
R3
Fuel
Cladding
h
Re
∆c
Rf
Moderator
(a)
(b)
Figura 2. (a) O Reator, (b) Célula Típica.
Objetivando-se projetar um reator para operar com
um dado fluxo de nêutrons, crítico, submoderado e com
fator de pico mínimo, permite-se que sejam variados os
valores dos enriquecimentos das 3 zonas, o passo da rede, o
diâmetro do combustível, a espessura do revestimento e os
materiais do combustível e do revestimento, nas faixas
dadas na Tabela 1.
TABELA 1. Faixas dos Parâmetros da Otimização
Parâmetro
Rf (cm)
∆r (cm)
∆m (cm)
E1 (%)
E2 (%)
E3 (%)
Combustível
Revestimento
Mínimo
Máximo
0,508
1,27
0,0254
0,254
0,0254
0,762
2,0
5.0
2,0
5.0
2,0
5.0
{UO2, Urânio metal}
{Zircaloy, Al, Aço-304
Bits
7
7
7
7
7
7
1
2
Onde Rf é o raio do combustível, ∆r é a espessura do
revestimento, ∆m é a espessura da camada de moderador,
ou seja, é o raio equivalente (que é função do passo) menos
o raio externo do revestimento; E1, E2 e E3, os
enriquecimentos das três diferentes zonas.
Matematicamente, o problema de otimização acima
descrito pode ser escrito como:
Index
Minimizar:
fm (Rf,∆r,∆m,E1,E2,E3,mf,mc)
(1)
Sujeito a
:
φ(Rf,∆r,∆m,E1,E2,E3,mf,mc) = φ0;
(2)
0.99 ≤ keff (Rf,∆r,∆m,E1,E2,E3,mf,mc) ≤ 1.01;
(3)
dk eff
>0;
dVm
(4)
Rfmin ≤ Rf ≤ Rfmax;
(5)
∆rmin ≤ ∆r ≤ ∆rmax;
(6)
∆mmin ≤ ∆m ≤ ∆mmax;
(7)
E1min ≤ E1 ≤ E1max;
(8)
E2min ≤ E2 ≤ E2max;
(9)
E3min ≤ E3 ≤ E3max;
(10)
Combustível = {UO2, U-metal};
(11)
Revestimento = {Zircaloy, Al, Stainless-304};
(12)
Onde fm é o fator de pico médio no reator; φ e φ0 são os
fluxos
térmicos
médios,
obtidos
e
esperados,
respectivamente e Vm é o volume do moderador. Os subíndices min e max referem-se aos limites inferiores e
superiores da faixa de variação das respectivas variáveis.
IV. MODELAGEM GENÉTICA DO PROBLEMA
A modelagem genética aqui utilizada, ou seja, a
codificação do genótipo e concepção da função de
avaliação (objetivo), é a mesma apresentada por Pereira
[1], portanto, esta seção não se estenderá em detalhes.
Genótipo. O genótipo concatena a codificação binária
direta de cada um dos parâmetros da otimização, cujas
faixas e número de bits associados são apresentados na
Tabela.
Função de avaliação. A função de avaliação, f, utilizada é
dada pelo fator de pico médio, deduzido de penalizações
aplicadas quando alguma restrição deixa de ser satisfeita. A
importância de cada restrição está relacionada a um fator r,
que pondera a penalização de acordo com os interesses da
otimização. Assim sendo, função de penalização pode ser
escrita conforme Eq. 13.

f m ,



f m + r1.ÄÄeff ,




f m + r2 .ÄÄö



Ä'k eff
,
f m + r3 .
ÄVm


f =

f m + r1.ÄÄeff + r2 .ÄÄö



Ä'k eff

f m + r1.ÄÄeff + r3 . ÄVm ,



Ä'k eff
,
f m + r2 .ÄÄ+ r3 .
ÄVm



f + r .ÄÄ + r .ÄÄ+ r . Ä'k eff ,
3
 m 1 eff 2
ÄVm
Äkeff ≤ 0.01; Äö ≤ 0.01ö 0 ;
Ä'k eff
>0
ÄVm
Äkeff > 0.01; Äö ≤ 0.01ö 0 ;
Ä'k eff
>0
ÄVm
Äkeff ≤ 0.01; Äö > 0.01ö 0 ;
Ä'k eff
>0
ÄVm
Äkeff ≤ 0.01; Äö ≤ 0.01ö 0 ;
Ä'k eff
<0
ÄVm
Äkeff > 0.01; Äö > 0.01ö 0 ;
Ä'k eff
>0
ÄVm
Äkeff > 0.01; Äö ≤ 0.01ö 0 ;
Ä'k eff
<0
ÄVm
Äkeff ≤ 0.01; Äö > 0.01ö 0 ;
Ä'k eff
<0
ÄVm
Äkeff > 0.01; Äö > 0.01ö 0 ;
Ä'k eff
<0
ÄVm
(13)
Onde r1, r2 e r3 são constantes de penalização para as
restrições de keff,, φ e submoderação, respectivamente.
V. APLICAÇÃO E RESULTADOS
Os cálculos neutrônicos envolvidos no processo de
otimização foram realizados com auxílio do código
Hammer [9], onde o reator é modelado conforme descrição
anterior. Na plataforma computacional utilizada –
computadores pessoais de 550MHz – a avaliação de um
candidato à solução leva cerca de 1,25 segundos, impondo
limitações no processo de otimização, levando à fixação do
número de gerações dos experimentos em 500. Para efeito
de ilustração, a execução de um AG, com uma população de
400 indivíduos (que não é muito grande) levaria mais do
que 69 horas.
Nos experimentos realizados, utilizou-se o sistema
ProGenIS ("Programmable Genetic Island System") [10],
desenvolvido no próprio Instituto de Engenharia Nuclear.
Este sistema é uma ferramenta para a implementação de
AGPs segundo o modelo de ilhas [8], e permite, ao usuário,
a definição de topologias e estratégias de migração, além da
escolha dos parâmetros genéticos tradicionais.
Utilizando-se a topologia em anel e migração do
melhor indivíduo de 10 em 10 gerações, foram realizados
vários experimentos, alterando-se parâmetros genéticos
como taxa de cruzamento, taxa de mutação e semente de
randomização. Em todas as ilhas foi utilizada estratégia de
elitismo para preservação da melhor solução.
Aqui são apresentados resultados comparativos AGP
x AGT, onde fixou-se o número total de avaliações a cada
geração (população total), ou seja, são comparados os
resultados obtidos pelo AGT com população de N
indivíduos, com os obtidos pelo AGP com N/50 ilhas de 50
indivíduos. As ilhas são executadas de forma distribuída em
4 computadores (Pentium 550MHz) da rede local do
Index
Instituto. No caso do AGT, este foi implementado, também,
utilizando-se o ProGenIS, no entanto, com uma única ilha
(cada ilha é exatamente um AG tradicional).
A Tabela 1 apresenta os resultados obtidos em 70
experimentos (10 para cada valor fixo de população, P),
onde variou-se as sementes de randomização e as taxas de
cruzamento e mutação.
1 .3400
AGT
1 .3200
f
TABELA 1. Valores de f para 500 Gerações
Exper.
1
2
3
4
5
6
7
8
9
10
Média
Tempo (h)
P=50
AGT
1,2895
1,3596
1,4138
1,3432
1,3662
1,2879
1,3164
1,3404
1,3541
1,3256
1,3397
8,7
P=100
AGT
AGP
1,3612 1,3565
1,3057 1,3249
1,3737 1,3249
1,3737 1,2847
1,3308 1,3666
1,3097 1,2795
1,3149 1,2825
1,3090 1,3523
1,3002 1,3066
1,3032 1,3627
1,3282 1,3241
17,4
8,7
P=200
AGT
AGP
1,3578 1,3322
1,3065 1,2799
1,3057 1,3378
1,3287 1,2835
1,2889 1,2810
1,3020 1,2796
1,3082 1,2784
1,3367 1,3034
1,3214 1,2989
1,3328 1,3170
1,3189 1,2992
34,7
8,7
P=400
AGT
AGP
1,2849 1,2993
1,2791 1,2793
1,3169 1,2776
1,3235 1,2996
1,3204 1,2824
1,3102 1,2804
1,3352 1,2788
1,3084 1,2808
1,2993 1,2990
1,.3463 1,2839
1,3124 1,2861
69,4
17,4
No caso do AGP, note que, enquanto o número de
ilhas é igual ou inferior ao número de computadores
disponíveis, o tempo médio aproximado de execução do
AGP não se altera com o aumento do quantidade de ilhas.
Isto deve-se à pouquíssima comunicação de dados
necessária entre os computadores no modelo de ilhas,
implicando, neste caso de estudo, em um aumento
desprezível no tempo total da otimização. No caso do
experimento com 8 ilhas, foram executadas 2 ilhas em cada
computador, portanto o tempo de execução é
aproximadamente o dobro. No entanto, se houvessem 8
computadores disponíveis, provavelmente o tempo de
execução seria na faixa de 8,7h. Ao contrário disso, no AGT
o tempo despendido no processo de otimização, aumenta
proporcionalmente com o aumento da população,
impossibilitando a utilização de populações maiores, fato
este que, em determinados casos, poderia vir a prejudicar a
solução do problema.
Além do ganho óbvio com relação ao tempo do
processo de otimização, observam-se ganhos nos resultados
da otimização. Isso ocorre devido ao aumento da
diversidade no processo de busca, promovida pelo Modelo
de Ilhas, conforme mencionado por Cantú-Paz [8].
A Figura 3 ilustra esses ganhos através de um gráfico
comparativo entre o AGT e o AGP, onde o valor médio (em
10 experimentos) de f obtido para diferentes populações é
plotado.
São comparados os resultados obtidos pelo AGT com
populações de N indivíduos, onde N={50, 100, 200 e 400}
contra os obtidos pelo AGP com M (M=N/50) ilhas de 50
indivíduos cada, onde M={1, 2, 4 e 8}.
AGP
1 .3300
1 .3100
1 .3000
1 .2900
1 .2800
50
100
150
200
250
300
350
400
População
Figura 3. Comparação dos Resultados Médios Obtidos.
Embora não seja o objetivo principal deste artigo,
apenas para efeito de ilustração, a melhor configuração de
parâmetros encontrada é exibida na Tabela 2.
TABELA 2. Parâmetros Ótimos Propostos pelo AGP
Objetivos
Fator de pico
Fluxo
keff
Parâmetros
Rf (cm)
∆r (cm)
∆m (cm)
E1 (%)
E2 (%)
E3 (%)
Combustível
Revestimento
* Fluxo é normalizado na fonte
Valor
1,290
8,7 x 10-5 *
1,001
Valor
0,730
0,186
0,756
2,685
2,826
4,882
U-metal
Aço-304
VI. CONCLUSÕES
Primeiramente, este trabalho mostra que, através de
computação paralela de baixo custo (utilizando-se de redes
comuns de computadores pessoais), pode-se resolver
eficazmente, através da CE, problemas de otimização cuja
solução não-paralela (também por meio da CE) é
impraticável.
Além disso, observou-se no caso estudado,
ratificando conclusões anteriormente publicadas [11-12],
que, para um número de gerações limitado, o modelo de
ilhas promove maior diversidade no processo de busca,
proporcionando um melhor aproveitamento de populações
Index
maiores e, consequentemente, levando a resultados
melhores.
Como futuros trabalhos, pretende-se aplicar AGP a
outros importantes problemas da engenharia nuclear, como,
por exemplo, a otimização de recarga de combustível
nuclear e a otimização de políticas de manutenção e testes
em sistemas de centrais nucleares, entre outros, de forma
que se possa obter soluções de problemas mais complexos e
reais.
REFERÊNCIAS
[1] Pereira, C. M. N. A., Schirru, R. E Martinez, A. S.
Basic Investigations Related to Genetic Algorithms in
Core Designs, Annals of Nuclear Energy, 26 (3), pp. 173193, 1999.
[2] Lapa, C. M. F., Pereira, C. M. N. A., Mol, A. C. A.
Maximization of a Nuclear System Availability through
Maintenance Scheduling Optimization Using Genetic
Algorithm. Nuclear Engineering and Design 196, pp. 219231, 2000.
[3] Schirru, R., Martinez, A. S., Pereira C. M. N. A.,
Domingos, R. P., Machado, M. D. e Machado, L.
Intelligent Soft Computing in Nuclear Engineering in
Brazil, Progress in Nuclear Energy,35 (3-4), pp. 367-391,
1999.
[4] Schirru, R., Pereira, C. M. N. A. e Martinez, A. S.
Genetic Algorithms Applied to Nuclear Power Plant
Operation, In: Da Ruan (ed), Fuzzy Systems and Soft
Computing in Nuclear Engineering, Springer-Verlag, pp.
335-350, 1999.
[5] Pereira, C. M. N. A. e Schirru, R. E Martinez, A. S.
Otimização em Projetos de Reatores Nucleares Baseada
em Rede Neural e Algoritmo Genético, XI Encontro
Nacional de Física de Reatores, pp. 334-339, 1997.
[6] Schirru, R., Pereira, C. M. N. A., Chapot, L. E
Carvalho, F. A Genetic Algorithm Solution for
Combinatorial Problems – The Nuclear Core Reload
Problem Example, XI Encontro Nacional de Física de
Reatores, pp. 357-360, 1997.
[7] Goldberg, D. E., Genetic Algorithms in Search,
Optimization and Machine Learning, Addison-Wesley,
1989.
[8] Cantú-Paz, E. Efficient and Accurate Parallel Genetic
Algorithms. Kluwer Academic Publishers, 2000.
[9] Suich, J. E. and Honec, H. C., The HAMMER System
Heterogeneous Analysis by Multigroup Methods of
Exponentials and Reactors, Savannah River Laboratory,
Aiken South Carolina, 1967.
[10] Pereira C. M. N. A. ProGenIS: Programable Genetic
Island System - Uma ferramenta genérica para
desenvolvimento de Algoritmos Genéticos Paralelos
utilizando o Modelo de Ilhas: Apresentação do Sistema e
Estado de Desenvolvimento Atual. SETER-07/01, IEN,
2001.
[11] Lin, S.-C, Investigating Parallel Genetic Algoritms
on Job Shop Scheduling Problems. In Angeline et al.
(Eds.), Evolutionary Programming VI (pp. 383-393),
Berlin, Springer, 1997.
[12] Sampaio, P. A. B., Pereira, C. M. N. A., Lapa, C. M.
F., Lapa, N. S., Mol, A. C. A., Jospin, R. J., e Nery D. E. S.,
Computação de alto desempenho no Instituto de
Engenharia Nuclear, XII Encontro Nacional de Física de
Reatores, 2000.
ABSTRACT
Nowadays, many optimization problems found in
nuclear engineering has been solved through genetic
algorithms (GA). The robustness of such methods is
strongly related to the nature of search process which is
based on populations of solution candidates, and this fact
implies high computational cost in the optimization process.
The use of GA become more critical when the evaluation
process of a solution candidate is highly times consuming.
Problems of this nature are common in the nuclear
engineering, and an example is the reactor design
optimization, where neutronic codes, which consume high
CPU time, must be run. Aiming to investigate the impact of
the use of parallel computation in the solution, through GA,
of a reactor design optimization problem, a parallel genetic
algorithm (PGA), using the Island Model, was developed.
Exhaustive experiments, involving more then 1500
processing hours in 550 MHz personal computers, have
been done, in order to compare the conventional GA with
the PGA. Such experiments have demonstrating the
superiority of the PGA not only in terms of execution time,
but also, in the optimization results.