ads:
ALGORITMO EVOLUCIONÁRIO NÃO PARAMETRIZADO APLICADO AO
PROBLEMA DA OTIMIZAÇÃO DE RECARGAS DE REATORES
NUCLEARES
Gustavo Henrique Flores Caldas
TESE SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS
PROGRAMAS DE PÓS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS
NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE DOUTOR EM CIÊNCIAS
EM ENGENHARIA NUCLEAR.
Aprovada por:
Prof. Roberto Schirru, D.Sc.
Prof. Eduardo Gomes Dutra do Carmo, D.Sc.
Prof. Cláudio Márcio do Nascimento Abreu Pereira, D.Sc.
Dr. Celso Marcelo Franklin Lapa, D.Sc.
Dr. Sergio de Queiroz Bogado Leite, Ph.D.
RIO DE JANEIRO, RJ - BRASIL
JULHO DE 2006
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
CALDAS, GUSTAVO HENRIQUE FLORES
Algoritmo Evolucionário Não Parame-
trizado Aplicado ao Problema da Otimiza-
ção de Recargas de Reatores Nucleares
[Rio de Janeiro]
XV, p. , cm (COPPE/UFRJ,
D.Sc., Engenharia Nuclear, )
Tese - Universidade Federal do Rio de
Janeiro, COPPE
. FPBIL
. Algoritmos Evolucionários
. Otimização
. Recarga de Reatores Nucleares
I. COPPE/UFRJ II. Título ( série )
ii
ads:
Dona Dulce,
minha avozinha, que poderia muito bem ser chamada Dona Doce.
Incansável intercessora, a quem dedico este trabalho.
iii
Agradecimentos
A Deus,
que é fiel, apesar da minha infidelidade.
A Anna Stella Flores Caldas,
minha mãezinha querida, que já partiu; mas cujo exemplo ainda ecoa forte.
A Lúcia,
minha segunda mãe, que nunca vai admitir, mas adora me mimar.
A meu querido pai,
meu herói, quem botou o primeiro livro de cálculo na minha mão.
A Renata Alves de Souza,
a moça mais fascinante que existe, pelo seu amor e compreensão.
A Gisele,
minha irmã preferida!!! Exímia conhecedora da Língua Portuguesa,
com quem adoro passar o tempo.
A Elso,
meu cunhadão, que nunca me negou um único favor sequer.
A Ricardinho e Anninha,
as crianças mais graciosas que existem, porque me lembram de sempre batalhar por
um mundo melhor.
iv
A D. Rose e Sr. Antônio,
meus segundos pais, pela forma carinhosa com que sempre me tratam.
A Roberto Schirru,
orientador e amigo, pelo direcionamento, confiança e apoio.
Aos colegas do PEN,
pelo companheirismo e espírito de grupo.
A Simone, Jô e Tania,
que nunca mediram esforços para me ajudar nas mais variadas situações.
Aos colegas da CNEN,
que sempre demonstraram um apoio muito grande, motivando-me a prosseguir,
especialmente nos momentos mais críticos.
Aos meus amigos do orkut e MSN,
q contribuiram MUITO para q eu permanecesse vivo durante meu periodo de
enclausuramento. Vcs sao D+ !!!!! =]
Aos amigos
que, de uma forma ou de outra, contribuíram para a existência desta tese:
Júnior, Rosimar, Tuca, Wander, Renatinha, Rodney, Izabelli, Beatrice, Tarsila,
Ticiano, Tarso, Thais, Áureo, Orli, Bianca, Henrique, Iana, Elina, Nathalia,
Negra, Marcele, Carlinhos, Carol, Elton, Juliane, Ewerton, Rachael, Bebel, André,
Maurinho, Gidel, Carine, VHS, Foca, Priscila, Erika, Luciana, Bruna, Pancho,
Clhistynnine, Daniel, Júlia, Elaine, Samira, Patrícia, Bloblô, Amaral, Fire, Lire,
Amanda, Vicente, Fernandinha, Flávia, Geison, Kelly, Izabela, Taís, Miojo,
Laurentina, César, Luhem, Luiz Henrique, Luiza Helena, Luiz Felipe, Michelle,
Jéssiii, Neurotiko, Oz, Paulinha, Ruivo, Renatinho, Rian, Eric, Lucas, Toy Story,
Márcio, Bruna, Gabi, Danizinha, Victor, Thiago, Vinícius, Paolo, Wanderson,
v
João, William, Djanira, Marcelo, Alessandro, Sergio, Cláudia, Pedro, Mára,
Lééélio, Cláudia, João Márcio, Paulo, Pedro Saldanha, Eustério, Rossana, Evaldo,
Joana, Rogério, Sandra, Cristiane, Marcelo, Max, Josilto, Ricardo, Maria Helena,
Cláudio Márcio, Alan, Marcelo, Carlão, o pessoal da EBA, do Coral Jovem, do
Classe A, do MC. . .
. . . e muitos outros!!!
Valeu!!!!!
vi
Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários
para a obtenção do grau de Doutor em Ciências (D.Sc.)
ALGORITMO EVOLUCIONÁRIO NÃO PARAMETRIZADO APLICADO AO
PROBLEMA DA OTIMIZAÇÃO DE RECARGAS DE REATORES
NUCLEARES
Gustavo Henrique Flores Caldas
Julho/
Orientador: Rob erto Schirru
Programa: Engenharia Nuclear
Neste trabalho desenvolve-se um algoritmo evolucionário sem parâmetros, base
ado no PBIL, denominado FPBIL. Ademais, mostra-se, de forma rigorosa, como os
parâmetros do PBIL podem ser substituídos por mecanismos auto-adaptáveis que
surgem da forma radicalmente diferente pela qual a evolução é processada. Apesar
dessas vantagens, o FPBIL mostra-se compacto e relativamente modesto no uso de
recursos computacionais. O FPBIL é testado e, por fim, aplicado ao problema da oti
mização de recargas de reatores nucleares. Os resultados experimentais observados
são comparados aos de outros trabalhos e corroboram para afirmar a superioridade
do novo algoritmo.
vii
Abstract of Thesis presented to COPPE/UFRJ as a partial fulfillment of the
requirements for the degree of Doctor of Science (D.Sc.)
PARAMETERLESS EVOLUTIONARY ALGORITHM APPLIED TO THE
NUCLEAR REACTOR RELOAD OPTIMIZATION PROBLEM
Gustavo Henrique Flores Caldas
July/
Advisor: Roberto Schirru
Department: Nuclear Engineering
In this work an evolutionary algorithm with no parameters called FPBIL is devel
oped based on PBIL. Moreover, the analysis reveals rigorously how the parameters
from PBIL can be replaced by self-adaptable mechanisms which appear from the rad
ically different form by which the evolution is processed. Despite the advantages,
the FPBIL reveals itself compact and relatively modest in the use of computational
resources. The FPBIL is then tested and, at the end, applied to the nuclear reactor
reload optimization problem. The experimental results observed are compared to
those of other works and corroborate to affirm the superiority of the new algorithm.
viii
Sumário
Lista de Figuras p. xii
Lista de Tabelas p. xv
Introdução p.
O Algoritmo PBIL p.
. Estrutura do PBIL . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. O Algoritmo PBIL Original . . . . . . . . . . . . . . . . . . . . . p.
FPBIL: parameter Free PBIL p.
. O Algoritmo FPBIL . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Eliminando os Parâmetros α e β . . . . . . . . . . . . . . . . . . . p.
. Eliminando os Parâmetros P
M
e γ . . . . . . . . . . . . . . . . . . p.
. Eliminando o Parâmetro P . . . . . . . . . . . . . . . . . . . . . . p.
Comparação Entre os Algoritmos p.
. Considerações Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . p.
.. Código de Gray . . . . . . . . . . . . . . . . . . . . . . . . p.
.. Minimizando o Impacto sobre a Escolha da Aptidão . . . . p.
ix
.. Procedimento Geral . . . . . . . . . . . . . . . . . . . . . . p.
. Problemas Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
.. Quatro Picos . . . . . . . . . . . . . . . . . . . . . . . . . p.
... Representação . . . . . . . . . . . . . . . . . . . p.
... Aptidões Bruta e Padrão . . . . . . . . . . . . . p.
... Resultados . . . . . . . . . . . . . . . . . . . . . p.
.. Banana . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
... Representação . . . . . . . . . . . . . . . . . . . p.
... Aptidões Bruta e Padrão . . . . . . . . . . . . . p.
... Resultados . . . . . . . . . . . . . . . . . . . . . p.
.. PCV Rykel . . . . . . . . . . . . . . . . . . . . . . . . . p.
... Representação Random Keys . . . . . . . . . . . p.
... Aptidões Bruta e Padrão . . . . . . . . . . . . . p.
... Resultados . . . . . . . . . . . . . . . . . . . . . p.
FPBIL Aplicado ao Problema da Recarga Nuclear p.
. Descrição do Problema . . . . . . . . . . . . . . . . . . . . . . . . p.
. O Núcleo de Angra 1 e suas Simetrias . . . . . . . . . . . . . . . . p.
. Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
.. RECNOD . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
.. Representação das Configurações Nucleares . . . . . . . . . p.
. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Comparação com Outros Trabalhos . . . . . . . . . . . . . . . . . p.
x
Lista de Figuras
. Algoritmo PBIL original. . . . . . . . . . . . . . . . . . . . . . . . p.
. Algoritmo FPBIL. . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. Comportamento de P
c
. . . . . . . . . . . . . . . . . . . . . . . . . p.
. Distribuição de N. . . . . . . . . . . . . . . . . . . . . . . . . . . p.
. P como função de c e P
0
. . . . . . . . . . . . . . . . . . . . . . . p.
. Comportamento da aptidão ajustada. . . . . . . . . . . . . . . . . p.
. Gráfico de Q
T
(I ), função objetivo do problema quatro picos. . . p.
. Comparação entre o FPBIL e o PBIL. . . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL
∗
e o PBIL
∗
. . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL e o FPBIL
∗
. . . . . . . . . . . . . . . p.
. Comparação entre o PBIL e o PBIL
∗
. . . . . . . . . . . . . . . . . p.
. Detalhe do PBIL contra o PBIL
∗
. . . . . . . . . . . . . . . . . . . p.
. Evolução típica do vetor de probabilidades do FPBIL. . . . . . . . p.
. Evolução típica do vetor de probabilidades do PBIL. . . . . . . . p.
xii
. Gráfico de B(x, y), função objetivo do problema banana. . . . . . p.
. Curvas de nível de log
10
B(x, y). . . . . . . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL e o PBIL. . . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL
∗
e o PBIL
∗
. . . . . . . . . . . . . . . p.
. Detalhe do FPBIL
∗
contra o PBIL
∗
. . . . . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL e o FPBIL
∗
. . . . . . . . . . . . . . . p.
. Comparação entre o PBIL e o PBIL
∗
. . . . . . . . . . . . . . . . . p.
. Comparação entre os algoritmos FPBIL. . . . . . . . . . . . . . . p.
. Detalhe da figura . na página . . . . . . . . . . . . . . . . . p.
. Comparação entre os algoritmos FPBIL. . . . . . . . . . . . . . . p.
. Detalhe da figura . na página . . . . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL e o PBIL. . . . . . . . . . . . . . . . p.
. Detalhe do FPBIL contra o PBIL. . . . . . . . . . . . . . . . . . . p.
. Valores mínimos e máximos ao final de um número de execuções. . p.
. Comparação entre o FPBIL
∗
e o PBIL
∗
. . . . . . . . . . . . . . . p.
. Detalhe do FPBIL
∗
contra o PBIL
∗
. . . . . . . . . . . . . . . . . . p.
. Comparação entre o FPBIL e o FPBIL
∗
. . . . . . . . . . . . . . . p.
. Detalhe do FPBIL contra o FPBIL
∗
. . . . . . . . . . . . . . . . . p.
. Detalhe da figura . na página . . . . . . . . . . . . . . . . . p.
. Comparação entre o PBIL e o PBIL
∗
. . . . . . . . . . . . . . . . . p.
. Detalhe do PBIL contra o PBIL
∗
. . . . . . . . . . . . . . . . . . . p.
. Esquema do núcleo de Angra 1. . . . . . . . . . . . . . . . . . . . p.
xiii
. Elementos central, de quarteto e de octeto. . . . . . . . . . . . . . p.
. Evolução de A
b
(I ) para o teste 1. . . . . . . . . . . . . . . . . . . p.
. Melhores soluções ao final de cada geração do teste 1. . . . . . . . p.
. Evolução de A
b
(I ) para o teste 2. . . . . . . . . . . . . . . . . . . p.
. Melhores soluções ao final de cada geração do teste 2. . . . . . . . p.
. Evolução de A
b
(I ) para o teste 3. . . . . . . . . . . . . . . . . . . p.
. Melhores soluções ao final de cada geração do teste 3. . . . . . . . p.
. A melhor configuração de núcleo encontrada pelo FPBIL. . . . . . p.
. Núcleo construído a partir da figura .. . . . . . . . . . . . . . . p.
. Melhor resultado das diferentes técnicas. . . . . . . . . . . . . . . p.
xiv
Lista de Tabelas
. Valores de P (k) para os primeiros múltiplos de σ. . . . . . . . p.
. Definição da função aptidão A
1
. . . . . . . . . . . . . . . . . . . . p.
. Definição da função aptidão A
2
. . . . . . . . . . . . . . . . . . . . p.
. Representação binária de 3 cidades. . . . . . . . . . . . . . . . . . p.
. Representação binária das possíveis rotas. . . . . . . . . . . . . . p.
. Possíveis rotas. A maioria delas inválidas. . . . . . . . . . . . . . p.
. Rotas válidas utilizando a representação random keys. . . . . . . . p.
. Formato de entrada usado pelo RECNOD. . . . . . . . . . . . . . p.
. Random keys aplicado a I |Q. . . . . . . . . . . . . . . . . . . . . p.
. Random keys aplicado a I |O. . . . . . . . . . . . . . . . . . . . . p.
. Uma linha (de quarteto) da entrada de dados do RECNOD. . . . p.
. Uma linha (de octeto) da entrada de dados do RECNOD. . . . . . p.
. Nova entrada das configurações de núcleo para o RECNOD. . . . p.
. Soluções não penalizadas do teste 1 com C
B
(I ) ≥ 1.300. . . . . . p.
. Soluções não penalizadas do teste 2 com C
B
(I ) ≥ 1.300. . . . . . p.
. Soluções não penalizadas do teste 3 com C
B
(I ) ≥ 1.300. . . . . . p.
. Comparação do desempenho das diferentes técnicas. . . . . . . . . p.
. DEEP e Receita, a mais, em relação a otimização manual. . . . . p.
xv
Introdução
xistem problemas de interesse prático cuja complexidade é de tal or
dem que muitos dos algoritmos clássicos de busca sequer podem deles
tratar. P roblemas com espaços de busca descontínuos ou com múlti
plos máximos e mínimos locais, ou ambos simultaneamente, tornam
quaisquer algoritmos de busca baseados em gradiente, por exemplo, inadequados.
Com o surgimento dos algoritmos evolucionários, muitas barreiras caíram. Os
algoritmos genéticos [, ] são exemplos dos que se mostraram robustos o suficiente
para abordar, virtualmente, qualquer problema. A forma de representar potenciais
soluções utilizando-se vetores binários é o método de busca inspirado na adaptação
das espécies [] — que impõe um paralelismo implícito — e que torna possível a
exploração dos mais intrincados espaços de busca.
O PBIL [] (do inglês: “Popupation-Based Incremental Learning”) é um algo
ritmo evolucionário que surgiu como tentativa de imitar, de forma simplificada, o
comportamento dos Algoritmos Genéticos em uma fase adiantada de sua execução,
“em equilíbrio”. O resultado mostra, de forma inesperada, que o PBIL superou []
os algoritmos genéticos em praticamente todos os aspectos. O PBIL é mais rápido
e encontra resultados melhores [].
Existem diferentes variações [–] do PBIL, mas todas dependem da escolha de
parâmetros. Há, ainda, outras técnicas de busca sofisticadas, como o ANT-Q [] —
inspirado no comportamento de formigas, cujo desempenho se destaca em proble
mas combinatórios —; outra técnica é o PSO [] — inspirado no comportamento
de uma nuvem de aves, destacando-se em problemas numéricos —, porém ambas,
indistintamente, requerem parâmetros.
É importante ressaltar que um algoritmo que depende de algum parâmetro pode
ser muito eficiente para um conjunto particular de parâmetros, porém muito ineficaz
para algum outro conjunto. No caso do PBIL, por exemplo, variações na taxa de
aprendizado produzem comportamentos completamente diferentes []. Desse modo,
quanto menos parâmetros um algoritmo necessitar ajustar, menor o risco deste não
atingir todo o seu potencial em alguma situação específica.
O objetivo desta tese é propor um novo algoritmo evolucionário, baseado no
PBIL, denominado FPBIL, parameter Free PBIL, que é, ao mesmo te mpo, livre de
parâmetros, mais poderoso que as variações atuais do PBIL e comparável às melhores
técnicas de busca disponíveis; e, por fim, aplicá-lo ao problema da otimização de
recargas nucleares.
A otimização de recargas nucleares é um problema combinatório de extrema com
plexidade e de grande interesse da engenharia nuclear. Devido ao grande número de
combinações possíveis, mais o fato de ser o espaço de busca altamente fragmentado
e multimodal e, ainda, levando-se em consideração as várias restrições técnicas e ge
ométricas as quais precisam ser respeitadas, o problema da otimização de recargas
nucleares é um desafio para qualquer algoritmo de busca.
A motivação inicial do presente trabalho para o desenvolvimento do FPBIL era
tornar o PBIL o mais compacto e simples possível, de m odo que pudesse ser incor
porado facilmente ao código do sistema de programação genética [,] CGP lil-gp
.;. []. Era, também, a oportunidade de p ôr em prática o novo método de atu
alização do vetor de probabilidades, concebido no decorrer do curso de doutorado.
O objetivo da simplificação era fazer com que o sistem a de programação genética
co-evoluísse com o PBIL, permitindo um mecanismo mais adequado de manipulação
de constantes numéricas. Os primeiros resultados foram muito animadores, como
pode ser visto em []. Contudo uma análise mais pormenorizada da variação resul
tante do PBIL demonstrou possuir tal variação uma estrutura muito rica, digna de
atenção exclusiva.
Diante da constatação de tal r iqueza, concebe-se esse trabalho de modo a con
templar devidamente os vários aspectos da natureza do FPBIL, visando a tirar de
tal análise o melhor proveito possível.
Para isso, no capítulo , o algoritmo PBIL, tal como em [], é apresentado
juntamente com as estruturas que fundamentam e sustentam seu funcionamento.
Conceitos como espaço de busca, hipercubo, vetor de probabilidades, indivíduo,
população e geração são igualmente definidos.
A seguir, o capítulo descreve o algoritmo FPBIL, desenvolvido durante o curso
de doutorado. No decorrer do capítulo, mostra-se como cada um dos parâmetros do
PBIL é eliminado de forma profunda e simples. Em especial, o vetor de probabili
dades é atualizado de m aneira simples e direta; todavia, diferentemente do PBIL,
utilizando-se de toda a informação disponível em cada geração e, implicitamente, in
corporando um poderoso mecanismo que é semelhante a atualização usual do PBIL,
porém com parâmetros auto-ajustáveis. A forma radicalmente diferente da mutação
observada no FPBIL é fundamentada na distribuição de probabilidades inerente ao
próprio vetor de probabilidades, garantindo que a referida mutação seja aplicada
sob medida. Tais modificações tornam o FPBIL mais robusto e, ainda, possibilitam
que este adquira uma população de tamanho variável, também auto-ajustável, que
o torna mais eficiente.
Em se guida, no capítulo , o FPBIL é comparado com o PBIL . Para tanto são
selecionados três problemas de diferentes classes, todos bem conhecidos. São eles:
“quatro picos” — um problema altamente deceptivo, onde não é necessária a deco
dificação dos vetores binários; “banana” — um problema numérico cuja dificuldade
está na forma da superfície em que se deseja localizar o ponto de mínimo; e o “PCV
Rykel” — um problema combinatório que necessit a de um tipo de representação
especial, random keys. Os resultados são apresentados, analisados e comentados.
No Capítulo , o FPBIL é utilizado para maximizar o comprimento do ciclo 7 de
Angra 1, um caso particular do problema da otimização de recargas nucleares, que
já foi abordado sob a ótica de diferentes técnicas, sendo considerado um benchmark,
a nível nacional, da área. Vale ressaltar que em nenhum dos resultados o FPBIL faz
uso de heurísticas e, ainda assim, concorre com as melhores técnicas. Os resultados
são apresentados e comparados aos das mais bem-sucedidas abordagens.
Finalmente, o capítulo encerra o trabalho ressaltando as vant agens da nova
técnica e sugerindo possíveis aperfeiçoamentos.
O Algoritmo PBIL
este capítulo será apresentado o algoritmo PBIL, Population-Based In
cremental Learning. O PBIL é um algoritmo de busca extremamente
versátil e tem se mostrado superior aos algoritmos genéticos, tanto
em simplicidade quanto em eficiência e desempenho.
Inicialmente será examinada a estrutura geral relacionada a qualquer algoritmo
do tipo PBIL, seguida da apresentação do algoritmo PBIL original.
. Estrutura do PBIL
Com o PBIL, um subconjunto S
B
do espaço de busca B de um determinado
problema de otimização é explorado a partir de um hipercubo H
n
= [0, 1]
n
, de modo
que cada vértice de H
n
, ou seja, cada ponto de
ˇ
H
n
= {0, 1}
n
corresponda a um
ponto de S
B
. Essa correspondência é feita a partir de um mapeamento sobrejetivo
M
n
S
B
:
ˇ
H
n
−→ S
B
I ≡ (I
1
, I
2
, . . . , I
n
) −→ M
n
S
B
(I ),
(.)
com I
k
≡ I [k] ∈ {0, 1}. As escolhas de S
B
e n dependem do problema em questão.
Entretanto, mesmo com S
B
e n fixos, a escolha de M
n
S
B
geralmente não é única e
pode influenciar no desempenho do PBIL
.
O mapeamento precisa ser sobrejetivo a fim de representar tod o o conjunto S
B
.
A razão para isto é que a busca se dá em H
n
e, geralmente, diferentes M
n
S
B
produzem diferentes
topologias em H
n
.
A fim de ilustrar os diversos conceitos, considere o seguinte exercício de encontrar
o valor de x, no intervalo [0, 10] ⊂ R, que maximiza f(x) = x
2
. De imediato podemos
fazer a seguinte associação:
B = R.
S
B
e o valor de n irão depender da precisão com que se deseja a solução. Su
ponhamos que duas casas decimais sejam suficientes. Neste caso, os candidatos a
solução podem ser
S
B
= {0,00; 0,01; 0,02; . . . ; 10,00},
candidatos. Devemos, portanto, escolher n de modo que o número de vértices
de H
n
seja no mínimo . Precisamos, então, satisfazer 2
n
≥ 1001, o que equivale
a n 9,97. Podemos, portanto, escolher
n = 10.
M
10
[0,10]
pode ser implementada explorando-se simplesmente a representação bi
nária usual:
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) = 0,00
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1) = 0,01
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 1, 0) = 0,02
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 1, 1) = 0,03
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 1, 0, 0) = 0,04
.
.
.
M
10
[0,10]
(1, 1, 1, 1, 1, 0, 1, 0, 0, 0) = 10,00.
(.)
Neste caso, os elementos restantes de
ˇ
H
10
podem ser associados, por exemplo
,
ao número 10,00.
Embora válida, esta prática deve s er desencorajada pois, como será visto, pode confundir os
algoritmos PBIL e FPBIL.
Uma outra possibilidade é tornar M
10
[0,10]
bijetiva por meio de
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) =
10 · 0
1023
= 0,0000
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1) =
10 · 1
1023
∼ 0,0098
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 1, 0) =
10 · 2
1023
∼ 0,0196
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 0, 1, 1) =
10 · 3
1023
∼ 0,0293
M
10
[0,10]
(0, 0, 0, 0, 0, 0, 0, 1, 0, 0) =
10 · 4
1023
∼ 0,0391
.
.
.
M
10
[0,10]
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1) =
10 · 1023
1023
= 10,0000.
(.)
Neste caso, S
B
= {0,0000; 0,0098; 0,0196; . . . ; 10,0000}.
A diferença entre cada par de pontos R e S de H
n
gera o conjunto V
H
n
de
vetores sobre H
n
:
V
H
n
= {R − S |R, S ∈ H
n
},
(.)
cujas coordenadas estão em [−1, 1]. Pode-se então perceber que cada ponto P ∈
H
n
é equivalente ao vetor P − O ≡ P ∈ V
H
n
, onde O ≡ (0, 0, . . . , 0) pode ser
considerado como a origem de H
n
.
Considere agora um ponto P ∈ H
n
. Suas n componentes p
k
≡ P [k] ∈ [0, 1]
são apropriadas para representar probabilidades. Se, por exemplo, p
k
representar a
probabilidade de se sortear o número 1 em um espaço amostral Ω = {0, 1}, então P
representa uma distribuição de probabilidades sobre
ˇ
H
n
:
P :
ˇ
H
n
−→ [0, 1]
I −→ p = P (I ).
(.)
Mais especificamente, considere o vetor distância d
I
= I − P que vai de P até
I , cujas componentes d
I
k
são, em módulo, as distâncias entre P e os n hiperplanos
(I
1
, #, . . . , #), (#, I
2
, . . . , #), . . . , (#, #, . . . , I
n
) que se interceptam em I — com #
podendo substituir tanto um “0” quanto um “1”. P (I ) pode, então, ser expresso
simplesmente por:
P (I ) =
n
k=1
(1 − |d
I
k
|). (.)
Por exemplo, P
′
= (0,5; 0,1; 0,7; 1; 0) ∈ H
5
determina que a probabilidade de I
1
=
(1, 1, 1, 1, 1) ∈
ˇ
H
5
ser sorteado é P
′
(I
1
) = 0,5 · 0,1 · 0,7 · 1 · 0 = 0. Já para I
2
=
(0, 0, 0, 0, 0) ser sorteado a probabilidade é P
′
(I
2
) = 0,5 · 0,9 · 0,3 · 0 · 1 = 0, e para
I
3
= (1, 0, 0, 1, 0), a probabilidade é P
′
(I
3
) = 0,5 · 0,9 · 0,3 · 1 · 1 = 0,135. Observe
que qualquer ponto de
ˇ
H
5
com a forma (#, #, #, 0, #) ou (#, #, #, #, 1) nunca será
sorteado a partir de P
′
, significando que a presença das duas últimas componentes
de P
′
conferem probabilidades não nulas apenas a elementos de
ˇ
H
3
×{(1, 0)} ⊂
ˇ
H
5
.
Verifica-se, a partir da equação (.), que o ponto I ∈
ˇ
H
n
mais provável de ser
sorteado a partir de P é o vértice de H
n
mais próximo de P . O segundo ponto mais
provável de ser sorteado a partir de P é o segundo vértice de H
n
mais próximo de
P , e assim por diante. Também é notável o fato de que basta uma componente d
I
k
de I − P satisfazer |d
k
| = 1 para que P (I ) = 0, condição que é equivalente a
p
k
=
1, se I
k
= 0;
0, se I
k
= 1.
(.)
Em outras palavras, se p
k
= 0, por exemplo, então qualquer ponto de
ˇ
H
n
com I
k
= 1
terá probabilidade zero de ser sorteado, ou ainda, as probabilidades não nulas ficam
restritas ao conjunto
ˇ
H
k−1
×{0}×
ˇ
H
n−k
, que possui a mesma estrutura de
ˇ
H
n−1
: a
“ordem” de
ˇ
H é reduzida por 1. À medida que outras componentes de d
I
satisfazem
a equação (.), as probabilidades não nulas ficam restr itas a um número cada vez
menor de vértices —
ˇ
H de ordem cada vez mais reduzida — até o caso extremo em
que P ≡ I
i
, um vértice qualquer de H
n
, quando P (I
j
) = δ
ij
, ou seja, I
i
sempre
será o único sorteado.
A próxima seção mostra como o PBIL utiliza os pontos de H
n
a fim de tentar
localizar soluções ótimas em um espaço de busca B.
. O Algoritmo PBIL Original
O PBIL [] foi criado em porShumeet Baluja.Foi inspirado em seu trabalho
anterior com Ari Juels [] em uma tentativa de simular o comportamento dos algo
ritmos genéticos [] em “estado de e quilíbrio”, após repetidas aplicações do operador
crossover.
O algoritmo aqui referenciado por “PBIL original” teve sua publicação posterior
mente, em [], por seu criador, na qual problemas, comumente explorados
na literatura de algoritmos genéticos, são examinados por diferentes técnicas de
otimização, com o PBIL tendo o melhor desempenho em mais de % dos casos. O
algoritmo PBIL original é mostrado na figura . na próxima página.
Após os vértices de H
n
serem devidamente mapeados em um subconjunto S
B
do
espaço de busca, o PBIL funciona exatamente da mesma forma, independentemente
do problema em questão. Essa característica é que torna o PBIL versátil, de modo
que a condição necessária e suficiente para que um problema de otimização seja
abordado pelo PBIL é a existência de M
n
S
B
.
Embora o PBIL possa ser aplicado em praticamente qualquer caso, a sua uti
lização é recomendada somente em problemas mais complexos, quando as técnicas
tradicionais falham, c omo em problemas da classe NP, busca em espaços multimo
dais, descontínuos, et c.
No início de cada PBIL todos os pontos de S
B
devem ser tratados como poten
ciais soluções e P vértices de H
n
são, portanto, escolhidos aleatoriamente a partir
de uma distribuição de probabilidades uniforme. Essa distribuição uniforme de pro
babilidades nada mais é que P
0
= (0,5, 0,5, . . . , 0,5), o centro de H
n
. Esta é a linha
da figura . na página seguinte.
Na terminologia do PBIL, os P vértices I
k
de H
n
selecionados a partir de P
G
** *** Inicialização do Vetor de Pr obabilidades
for (j = 1 . . . n) P [j] = 0,5
** ***
while (not Cr itério_de_Término)
for (i = 1 . . . P)
for (j = 1 . . . n)
** *** Criação de I
i
a partir de P
if
random (0, 1) < P [j]
I
i
[j] = 1
else I
i
[j] = 0
** ***
Calcular A(I
i
)
Designar I
+
, o indivíduo mais apto
Designar I
−
, o indivíduo menos apto
for (j = 1 . . . n)
** *** Atualização de P na direção de I
+
P [j] = (1 − α) · P [j] + α · I
+
[j]
** ***
if (I
−
[j] = I
+
[j])
** *** Atualização de P na direção oposta a de I
−
P [j] = (1 − β) · P [j] + β · I
+
[j]
** ***
** *** Aplicação da Mutação em P
for (j = 1 . . . n)
if (random (0, 1) < P
M
)
if
random (0, 1) < 0,5
D
M
= 1
else D
M
= 0
P [j] = (1 − γ) · P [j] + γ · D
M
** ***
P: Tamanho da População (100).
α: Taxa de Aprendizado (0,1).
β: Taxa de Aprendizado Negativo (0,075).
P
M
: Probabilidade de Mutação (0,02).
γ: Taxa de Mutação (0,05).
Figura .: Algoritmo PBIL original.
(linhas – da figura .) formam uma “população” — a “geração” G — e são
chamados de “indivíduos”. O algoritmo PBIL consiste em, baseado nos indivíduos da
geração 0, construir P
1
, que dará origem a uma outra população — a geração 1. O
processo se repete, até que um indivíduo de uma geração qualquer seja considerado
bom o suficiente (linha da figura . na página precedente).
A medida do quanto um indivíduo é bom ou ruim é dada pela função “aptidão”
:
A:
ˇ
H
n
−→ R
+
I −→ A = A(I ).
(.)
Na maioria das vezes, entretanto, I não é avaliado diretamente, sendo necessária
uma composição A = M
n
S
B
◦A
′
, com A
′
: S
B
−→ R. Esta é a linha da figura ..
Pode-se escolher A de forma que A(I
i
) ≥ A(I
j
) implique em I
i
melhor que
ou tão bom quanto I
j
, tornando trivial a tarefa de designar o “indivíduo mais
apto”, I
+
e o “indivíduo menos apto”, I
−
(Linhas e da figura . na página
precedente).
A construção de P
G+1
a partir dos indivíduos da geração G é o processo mais
importante do PBIL. Qualquer ponto P
G+1
de H
n
diferente de P
0
gera uma dis
tribuição de probabilidades não-uniforme sobre
ˇ
H
n
. A estrat égia do PBIL é a de,
geração após geração, modificar essa distribuição de probabilidades tornando cada
vez mais provável o surgimento de I
†
, a solução ótima. No PBIL original, P
G+1
é
construído em duas fases.
Na primeira fase, são realizadas as seguintes operações (equivalentes as das linhas
A medida natural da qualidade de um indivíduo Q(I ) em um determinado problema de oti-
mização pode ser negativa. Neste caso, a aptidão deve ser qualquer transformação de Q que leve
a R
+
, preservando a relação de qual indivíduo é melhor que outro. Esta questão, apesar de não
causar nenhum efeito no PBIL, será indispensável para o FPBIL, apresentado no capítulo na
página .
– da figura .):
P
G+1/2
= P
G
+ α · (I
+
− P
G
) (.)
P
′
G+1
[j] =
P
G+1/2
[j] + β · (I
+
[j] − P
G+1/2
[j]) se I
+
[j] = I
−
[j]
P
G+1/2
[j] se I
+
[j] = I
−
[j]
(.)
ou seja, P
G
é inicialmente deslocado na direção de I
+
por uma fração α da distância
entre P
G
e I
+
. Em seguida, P
G+1/2
é alterado de modo que a projeção de P
G+1/2
no subespaço H
l
⊂ H
n
— formado pelas l coordenadas para as quais I
+
[j] =
I
−
[j] — seja afastada da projeção de I
−
, também em H
l
. Em H
l
, I
+
e I
−
são diametralmente opostos e temos I
+
[j] = 1 − I
−
[j], ou seja, aproximar-se
de I
+
é o mesmo que afastar-se de I
−
. Portanto, se olharmos de dentro desse
subespaço, observaremos P
G+1/2
sendo deslocado na direção oposta a I
−
por uma
fração β da distância entre P
G+1/2
e I
+
(e não I
−
). Uma vez que o vértice de
H
n
mais próximo de P
G+1
é o mais provável de ser escolhido, o PBIL original tenta
alcançar seu objetivo direcionando a distribuição de proba bilidades P
G+1
para o
melhor indivíduo disponível em G.
Na segunda fase, P
′
G+1
sofre uma “mutação”. Pela forma como os indivíduos
são criados a partir de P
G
, e como P
G+1
é construído em seguida; uma vez que
uma componente de P
G
atinge o valor 0 (ou 1), essa componente continuará sendo
0 (ou 1) até o final do algoritmo. Se, eventualmente, a solução ótima possuir a
correspondente componente com valor oposto ao 0 (ou 1) de P
G
, ela nunca será
encontrada em nenhuma geração posterior, a menos que algum mecanismo adjacente
seja capaz de alterar ocasionalmente as componentes de P
′
G+1
.
Tal mutação consiste em deslocar as componentes de P
′
G+1
aleatoriamente na
direção de 0 ou 1. Isto significa que cada componente P
′
G+1
[j] poderá, ou não,
sofrer o deslocamento (de acordo com a “probabilidade de mutação”), conforme a
expressão:
P
G+1
[j] = P
′
G+1
[j] + γ · (D
M
− P
′
G+1
[j]), (.)
ou seja, o deslocamento é na direção de D
M
(0 ou 1, aleatoriamente) com uma
amplitude igual à fração γ da distância entre P
′
G+1
[j] e D
M
(Linhas – da figura
. na página ).
Como pode ser verificado na figura . na página , o PBIL original necessita
de parâmetros para funcionar e parece não existir nenhuma evidência de que estes
sejam independentes de uma aplicação em particular — de fato, os valores da figura
. foram determinados experimentalmente de modo a maximizar o desempenho
médio do algoritmo em uma gama de diferentes aplicações. No próximo capítulo,
propõe-se uma variação do PBIL livre de parâmetros.
FPBIL: parameter Free PBIL
presente capítulo apresenta o algoritmo FPBIL, parameter Free Pop
ulation-Based Incremental Learning, desenvolvido durante o trabalho
de doutorado. Nota-se que o “p” de parameter não entra na na sigla
do algoritmo. O motivo é não sobrecarregar a nomenclatura nem difi
cultar demasiadamente sua pronúncia. O nome do algoritmo se encontra em língua
inglesa pelo fato de qualquer tentativa de adaptação desse para a língua portuguesa
resultar na descaracterização de sua relação com o PBIL.
O FPBIL é uma variação do PBIL que procura eliminar a necessidade dos pa
râmetros do PBIL modificando fundamentalmente alguns de seus princípios. O
resultado é um algoritmo mais eficiente, com um poder de busca superior e sem
parâmetros.
. O Algoritmo FPBIL
Como no algoritmo PBIL original, o FPBIL apresenta um vetor de probabili
dades P , com n componentes p
k
∈ [0, 1], a partir do qual os P indivíduos I
k
de
uma determinada geração são criados. A característica que os diferencia é que o
FPBIL procura utilizar mecanismos suficientemente genéricos para torná-lo livre de
parâmetros, especialmente pela forma como P é atualizado e como a mutação é
implementada. O algoritmo FPBIL é apresentado na figura . na página seguinte.
** *** Definição das Funções C
x
e D
x
D
x
≡ 1/(1 + x)
C
x
≡ D
−1
x
≡ 1/x − 1
** ***
** *** Inicialização do Vetor de Pr obabilidades, de P
0
e de d
for (j = 1 . . . n) P [j] = 0,5
P
0
= 7(1 + 1/n)
n
d = 1/3
** ***
while (not Cr itério_de_Término)
** *** Determinação de P
if (Flutuação em c)
P
0
= P
0
+ 1
if (∆c
G
< 1%)
d = 1/3
P = P
0
c = C
d
P = (int)P
0
(1 + 1/c)
c
(P
0
/7)
−c/n
** ***
for (i = 1 . . . P)
** Criação de I
i
a partir de P , como no PBIL original
Calcular A(I
i
)
for (j = 1 . . . n)
** *** Atualização de P
P [j] =
P
i=1
A(I
i
) · I
i
[j]
P
i=1
A(I
i
)
** ***
** *** Aplicação da Mutação em P
c = contagem dos casos (P [j] ≤ d ou P [j] ≥ 1 − d)
c
′
= contagem dos casos (P [j] ≤ D
C
d
−1
ou P [j] ≥ 1 − D
C
d
−1
)
if (c > C
d
) d = D
c+1
else if (c
′
< C
d
− 1) d = D
c−1
if (d > 1/3) d = 1/3
for (j = 1 . . . n)
if (P [j] < d) P [j] = d
if (P [j] > 1 − d) P [j] = 1 − d
** ***
Figura .: Algoritmo FPBIL: parameter Free PBIL.
. Eliminando os Parâmetros α e β
No algoritmo PBIL original, o vetor de probabilidades é atualizado sofrendo um
pequeno deslocamento que o aproxima do me lhor indivíduo e outro deslocamento
que o afasta do pior indivíduo. Em algumas variantes do PBIL, utiliza-se apenas
o melhor indivíduo, ou apenas o pior indivíduo, ou também, em substituição ao
melhor indivíduo, a média dos l melhores indivíduos:
Q
l
=
l
i=1
I
i
l
=
I
1
+ I
2
+ ··· + I
l
l
, (.)
procedendo a atualização de P
G
conforme
P
′
G+1
= P
G
+ χ · (Q
l
− P
G
). (.)
O fato é que para avaliar quem são os melhores e piores indivíduos, todos os indiví
duos devem ser avaliados, o que significa que todos os algoritmos PBIL desperdiçam
quase toda informação disponível sobre o espaço de busca.
Uma primeira tentativa de aproveitar toda a informação seria generalizar a ex
pressão (.) para l = P. Entretanto, lim
l→2
n
Q
l
= P
0
, o que resultaria em desloca
mentos para o centro de H
n
, independentemente de P
G
. A soma na equação (.)
pressupõe que não há repetição de nenhum indivíduo.
Uma segunda tentativa seria, portanto, tomar Q
P
=
P
i=1
I
i
/P, onde i, agora,
é a ordem em que os indivíduos são sorteados, podendo haver repetições de indi
víduos de acordo com a probabilidade desses serem sorteados. Porém, neste caso,
lim
P→∞
Q
P
= P
G
, o que resulta em P
′
G+1
= P
G
: nenhuma mo dificação de P
G
.
Talvez, por esta razão, não se costume empregar todos os indivíduos no processo de
atualização do vetor de probabilidades.
A regra segundo a qual o FPBIL atualiza seu vetor de probabilidades é
P
′
G+1
=
P
i=1
A
i
· I
i
P
i=1
A
i
, (.)
que é justamente uma média (permitindo a repetição de indivíduos) na qual uti
lizam-se todos os P indivíduos. A diferença é que esta média é ponderada pela
aptidão A
i
≡ A(I
i
) de cada indivíduo. A fim de poder apreciar a mudança causada
por esse detalhe, pode-se deduzir que
P
′
G+1
=
A
i
>A
A
i
· I
i
+
A
i
=A
A
i
· I
i
+
A
i
<A
A
i
· I
i
P
i=1
A
i
, (.)
onde A ≡
P
i=1
A
i
/P é a aptidão média da geração G. Somando e subtraindo os
termos
A
i
>A
A · I
l
e
A
i
<A
A · I
l
no numerador, é possível observar que
P
′
G+1
=
A ·
P
i=1
I
i
+
A
i
>A
(A
i
− A) · I
i
+
A
i
<A
(A
i
− A) · I
i
P · A
.
(.)
Multiplicando e dividindo esta expressão por
A
i
>A
(A
i
− A), temos:
P
′
G+1
=
P
i=1
I
i
P
+
1
P
A
i
>A
A
i
− A
A
· D, (.)
D ≡
A
i
>A
(A
i
− A) · I
i
+
A
i
<A
(A
i
− A) · I
i
A
i
>A
(A
i
− A)
. (.)
E já que
A
i
>A
(A
i
− A) =
A
i
<A
(A − A
i
), chega-se ao resultado:
P
′
G+1
=
P
i=1
I
i
P
+
1
P
A
i
>A
A
i
− A
A
· D, (.)
D ≡
A
i
>A
(A
i
− A) · I
i
A
i
>A
(A
i
− A)
−
A
i
<A
(A − A
i
) · I
i
A
i
<A
(A − A
i
)
. (.)
Para ajudar na interpretação do resultado, considere a seguinte notação:
r
O
i
c
i
w
i
=
c
i
w
i
· O
i
c
i
w
i
, (.)
que significa a média dos objetos O
i
, ponderada pelo peso w
i
, restrita à condição
c
i
. Caso w
i
= const, ∀i,
r
O
i
c
i
torna-se uma média simples e w
i
pode ser omitido.
c
i
também pode ser omitido caso a restrição esteja implícita. Até mesmo o índice
i pode ser omitido, como em A. A presença do “r” significa que a repetição de
objetos O
i
é permitida, caso contrário o mesmo é omitido. Por exemplo, a equação
(.) na página pode ser escrita simplesmente como P
′
G+1
=
r
I
i
i=1...P
A
i
, ou até
mesmo como P
′
G+1
=
r
I
i
i
A
i
, enquanto a maneira correta de escrever A seria,
pelo menos,
r
A. Assim, as equações (.) e (.) tornam-se
P
′
G+1
=
r
I
i
i
+ ξ · D (.)
D ≡
r
I
i
A
i
>A
A
i
−A
−
r
I
i
A
i
<A
A−A
i
, (.)
com
ξ =
1
P
A
i
>A
A
i
− A
A
. (.)
Neste ponto alguns comentários são cabíveis e necessários. Pr imeiramente, a
equação (.) possui uma estrutura seme lhante a da combinação das equações (.)
e (.) na página . Como
r
I
i
i
≈ P
G
, o vetor de probabilidades é atualizado
deslocando-se P
G
na direção de D por uma fração ξ da distância entre
r
I
i
A
i
>A
A
i
−A
e
r
I
i
A
i
<A
A−A
i
.
Durante a execução do FPBIL, P tr aça um caminho em H
n
enquanto duram
as gerações. A direção e intensidade de cada passo pode ser interpretada como
a velocidade com que P percorre este caminho. Como o caminho é percorrido
discretamente, uma possível representação da velocidade é
∂P
G
∂G
≡
P
G+1
− P
G
1
. (.)
No PBIL original, não é simples identificar a forma exata da velocidade ( mesmo
sem considerar a mutação), no entanto, a combinação das das equações (.) e (.)
resulta em
∂P
G
∂G
≈ f(α, β) ·(I
+
− I
−
). (.)
No FPBIL tem-se
∂P
G
∂G
≈ ξ · D. (.)
A vantagem em se utilizar D é que a direção do deslocamento não é baseada
apenas no melhor e no pior indivíduo, mas em toda a informação disponível sobre
o espaço de busca em uma geração (P indivíduos avaliados). Um outro detalhe
sobre D é que as médias não são simples, mas ponderadas pelas diferenças entre
as aptidões de cada indivíduo e a aptidão média, de modo que um indivíduo muito
ruim ou muito bom exerce mais influência do que outros com aptidões próximas a
da média.
É interessante notar que cada ponto P de H
n
pode ser associado a uma aptidão
média
P
A por meio de
P
A : H
n
−→ R
P −→
P
A =
2
n
i=1
A
i
· P (I
i
).
(.)
O motivo é que, a partir de P , cada indivíduo I
i
possui uma probabilidade P (I
i
)
de ser sorteado. Após P sorteios, o indivíduo I
i
é sorteado P
i
vezes. No limite em
que P torna-se muito grande, tem-se
P
A = lim
P→∞
A (.)
= lim
P→∞
P
j=1
A
j
P
= lim
P→∞
2
n
i=1
A
i
·
P
i
P
(.)
=
2
n
i=1
A
i
· P (I
i
). (.)
Em cada geração do FPBIL, tem-se A ≈
P
A e
ˇ
H
n
é aproximadamente divi
dido em duas regiões: a de indivíduos com aptidão superior a A e a de indivíduos
com aptidão inferior a A. Cada região é representada por um ponto:
r
I
i
A
i
>A
A
i
−A
,
para A
i
> A e
r
I
i
A
i
<A
A−A
i
, para A
i
< A, tais pontos são uma espécie de centros
de gravidade de cada região. Então P
G
é deslocado na direção de
r
I
i
A
i
<A
A−A
i
para
r
I
i
A
i
>A
A
i
−A
, a direção em que A aumenta. Tem-se, aproximadamente
, que
D ∝ grad
P
A, (.)
que resulta, aproximadamente, em
∂P
G
∂G
∝ ξ · grad
P
A. (.)
Evidentemente o PBIL segue uma estratégia mais direta; e mais arriscada. A
velocidade seguida pelo PBIL pode variar muito de direção até encontrar um indiví
duo bom o suficiente e, então, segue direto até ele, correndo um grande risco de ficar
“aprisionado” em um ótimo local (convergência prematura). Comparada à equação
(.) na página , a velocidade do FPBIL está sujeita a menores variações em sua
direção, já que é muito menos provável que A varie desordenadamente de geração
a geração, se comparada ao par I
+
e I
−
. Da mesma forma, é menos provável que o
FPBIL convirja prematuramente, uma vez que teria menos chance de chegar a uma
região de ótimo local.
Com relação a ξ, pode-se verificar que este exerce função semelhante a de α ou
β, relacionada com a intensidade do deslocamento sofrido por P . Enquanto α ou β
são constantes, ξ varia de acordo com a distribuição de aptidões de cada geração.
Para ser mais preciso, ξ é a metade do desvio absoluto médio, relativo à média, das
É imp ortante enfatizar que esta aproximação é um pouco exagerada, uma vez que não há prova
formal, mas é útil para uma melhor compreensão do método.
aptidões:
ξ =
1
P
A
i
>A
A
i
− A
A
(.)
=
1
A
1
P
A
i
>A
A
i
− A (.)
=
1
2
1
A
1
P
P
i=1
|A
i
− A|
(.)
=
1
2
δ
A
=
1
2
δ
r
(.)
O desvio absoluto médio (δ) é uma medida de dispersão de uma distribuição, da
mesma forma que o desvio padrão. δ
r
é somente uma maneira de expressar a mesma
dispersão em relação à média.
Deste modo, ξ apresenta um comportamento muito interessante. Considere, a
seguir, diferentes cenários
:
. Todos os indivíduos da população são ruins (δ
r
= δ
1
r
);
. Todos os indivíduos da população são bons (δ
r
= δ
2
r
);
. Os indivíduos da população são, em média, ruins, mas existem uns poucos
bons (δ
r
= δ
3
r
);
. Os indivíduos da população são, em média, bons, mas existem uns poucos
muito bons (δ
r
= δ
4
r
).
O que normalmente ocorre é que δ
3
r
> δ
4
r
> δ
1
r
> δ
2
r
, o que é muito apropriado. No
início de uma execução do FPBIL, geralmente os indivíduos possuem uma aptidão
muito ruim. Enquanto não surge nenhum indivíduo que se destaque (cenário ), ξ é
pequeno — o algoritmo não se arrisca a tom ar uma decisão sobre qual direção seguir.
Deve estar claro que a intenção aqui não é a de listar exaustivamente os possíveis cenários,
mas de destacar uns poucos cenários que marcam fases importantes da evolução da aptidão no
algoritmo.
Quando surgem os primeiros bons indivíduos (cenário ), ξ aumenta consideravel
mente. Conforme a média das aptidões sobe (cenário ), ξ diminue gradativamente
— é a hora de se preocupar com a convergência prematura. Finalmente quando a
solução ótima está próxima (cenário ), ξ se torna bem pequeno, certificando-se que
não haverá oscilação em torno da solução ótima, mas que esta será alcançada.
É obvio que este não somente é o tr anscorrer ideal do FPBIL, mas é, também,
o mais provável. Neste ponto, vale a pena ressaltar que a intensidade de cada passo
∂
G
P
G
não depende apenas de ξ, mas também do módulo de D.
Utilizando-se as equações (.) na página e (.) na pág ina anterior, nos
permite reescrever a equação (.) na página como
P
′
G+1
≈ P
G
+
1
2
ϑ(P
G
) · δ
r
· grad
P
G
A, (.)
que exibe toda a profundidade dos mecanismos implícitos na equação (.) na pá
gina , onde ϑ(P
G
) é uma função (positiva) que torna D ≈
ϑ(P
G
) · grad
P
G
A
,
possivelmente dependente da distribuição de probabilidades P
G
.
Combinando as características de ξ e D, o FPBIL segue uma estratégia que
merece, no mínimo, alguma atenção. Esta é a linha da figura . na página .
Mas existem outros detalhes do FPBIL que devem ser explanados.
. Eliminando os Parâmetros P
M
e γ
Um dos cuidados que devem ser tomados no ajuste dos parâmetros α e β do
PBIL original é não escolher valores muito próximos de 0, tampouco valores próxi
mos de 1. No primeir o caso o algoritmo é desnecessariamente demorado, enquanto
que no segundo a convergência é prematura. Por mais eficiente que seja o ajuste, en
tretanto, ainda é necessária a ação da mutação para minimizar ainda mais a chance
de covergência prematura, além de aumentar o poder de busca.
A função da mutação é dar uma “segunda oportunidade” às componentes de P
que atingem os valores 0 ou 1 equivocadamente. O PBIL original realiza esta tar efa
probabilisticamente (de acordo com P
M
) através de deslocamentos (proporcionais a
γ) aleatórios (D
M
, que é 0 ou 1) nas componentes de P .
O FPBIL segue uma estratégia mais direta, explorando o significado do vetor de
probabilidades. Em primeiro lugar, o algoritmo impede que qualquer componente
de P atinja os valores 0 ou 1. Deste modo sempre é possível o sorteio de qualquer
indivíduo de
ˇ
H
n
. Isto é feito restringindo-se cada componente p
k
de P ao intervalo
[d, 1 − d]. Como conseqüência, a probabilidade de se sortear qualquer indivíduo, a
partir de P estará sempre entre d
n
e (1 − d)
n
.
Surge, então, a questão de que valor d é mais apropriado. d = 0 é o mesmo
que não ter mutação e d = 0,5 transforma o FPBIL em uma busca aleatória. Para
solucionar essa questão será feita a seguinte hipótese: Das n componentes de P
′
G+1
,
as c que satisfazem p
k
≤ d (ou p
k
≥ 1 − d) estão no caminho correto para atingir
a melhor solução—significando que p
k
≤ d ⇒ I
†
[k] = 0 (e que p
k
≥ 1 − d ⇒
I
†
[k] = 1). d será escolhido de forma a maximizar a probabilidade p
1
de sorteio de
um indivíduo com as correspondentes c componentes corretas
p
1
≈ (1 − d)
c
(.)
ao mesmo tempo em que maximiza a probabilidade p
2
desse mesmo indivíduo possuir
uma outra componente correta a partir da probabilidade (componente correspon
dente em P
′
G+1
) mais desfavorável. Na pior das hipóteses, existirá uma componente
l tal que I
†
[l ] = 1 com p
l
d (ou I
†
[l ] = 0 com p
l
1 − d) de modo que
p
2
≈ d. (.)
A probabilidade final que se deseja maximizar é, portanto,
p(d) = p
1
p
2
≈ d(1 − d)
c
, (.)
bastando, para isso, encontrar a solução para p
′
(d
c
) = 0:
p
′
(d
c
) ≈ (1 − d
c
)
c
− cd
c
(1 − d
c
)
c−1
= 0 (.)
⇒ 1 − d
c
≈ cd
c
(.)
∴ d
c
≈
1
1 + c
. (.)
É simples; porém paradoxal quando se tenta estimar c. Saber c exatamente
significa saber qual é o indivíduo ótimo de antemão. A solução adotada é tal que os
valores de d são construídos iterativamente.
O algoritmo de mutação do FPBIL inicialmente adota d = d
2
= 1/3 — o
maior valor de d
c
diferente de 0,5. Após a atualização do vetor de probabilidades,
verifica-se quantas (c) componentes de P
′
G+1
satisfazem p
k
≤ d
2
(ou p
k
≥ 1 − d
2
).
Se c ≥ 3, d torna-se d
3
= 1/4. Se d = d
3
e c ≥ 4 (o número de componentes
de P
′
G+1
que satisfazem p
k
≤ d
3
(ou p
k
≥ 1 − d
3
)), d torna-se d
4
= 1/5, e assim
sucessivamente. Deste modo, é possível diminuir o valor de d gradualmente, à medida
que P aproxima-se de algum indivíduo de
ˇ
H
n
— I
†
, de preferência.
Mas existe um mecanismo que permite d aumentar também. Se, por exemplo,
d = d
5
= 1/6 mas c 6, verifica-se quantas (c
′
) componentes de P
′
G+1
satisfazem
p
k
≤ d
4
(ou p
k
≥ 1 − d
4
). Se c
′
< 5, d torna-se d
4
= 1/5. Se d = d
4
, c 5 e c
′
< 4
(o número de componentes de P
′
G+1
que satisfazem p
k
≤ d
3
(ou p
k
≥ 1 − d
3
)), d
torna-se d
3
= 1/4, e assim por diante, até que d atinja o valor d
2
= 1/3, o maior
permitido.
Após as contagens de c e c
′
e a atualização do valor de d, este encontra a sua real
função: trazer de volta a d (ou a 1 − d) quaisquer componentes de P
′
G+1
menores
que d ( ou maiores que 1 − d), transformando P
′
G+1
em P
G+1
. O procedimento da
mutação é ilustrado em diferentes situações nas figuras . a ..
Como pode ser observado, os vários valores de d funcionam como “portas” que se
abrem ou fecham dependendo das quantidades de pontos em “área proibida” (cinza
Figura .: Mutação : Cada ponto da figura representa uma componente de
P . Nesta situação, d = d
3
e, após a atualização de P , existem mais de pontos
na “área proibida” (área cinza escuro ), o que permite a abertura da “porta 3” (d se
torna d
4
). Em seguida, todos os pontos que ainda permanecem na “área pro ibid a”
(dois pontos, neste exemplo) são recuados para a a nova fronteira (correspondente
a d = d
4
).
Figura .: Mutação : Nesta situação, d = d
3
e, após a atualização de P , exis
tem apenas pontos na “área proibida” (área cinza escuro), o que não é suficiente
para a abertura da “porta 3”. Em compensação, existem pontos em áreas cinzas,
o que pe rmite que a “porta 2” permaneça aberta. Os pontos na “área proibida”
são recuados para a fronteira.
Figura .: Mutação : Nesta situação, d = d
3
e, após a atualização de P ,
apenas um ponto toca a fronteira da “área proibida”. Os pontos em áreas
cinzas permitem que a “porta 2” permaneça aberta. Como o únic o ponto em “área
proibida” encontra-se na fronteira, P não sofre modificação.
Figura .: Mutação : Nesta situação, d = d
3
e, após a atualização de P , o
único ponto na “área proibida” (área cinza escuro) não é suficiente para a abrir a
“porta 3”. Os pontos em áreas cinzas não são suficientes para manter a “porta
2” aberta. A “porta 2” é fechada (d se t orna d
2
) e todos os pontos em áreas cinzas
são recuados para a nova fronteira (correspondente a d = d
2
).
escuro) — c — e de pontos em “área proibida” e “área próxima” (cinza escuro e cinza
claro) — c
′
. Estas são as linhas – da figura . na página .
Até este ponto o FPBIL é capaz de atingir resultados superiores ao do PBIL
original, para P suficientemente grande. Mas ainda é possível eliminar este último
parâmetro e ao mesmo tempo tornar o FPBIL mais eficiente. Essa possibilidade
será explorada na seção a seguir.
. Eliminando o Parâmetro P
A escolha do tamanho da população está relacionada à dificuldade do problema
em mãos; um problema simples não necessita de uma população grande.
Existem vários aspectos de um problema que o torna mais difícil que outros.
Alguns aspectos intrínsecos, como tamanho e topologia do espaço de busca B; outros
introduzidos quando se utiliza o PBIL, como a escolha de M
n
S
B
.
O número total de elementos em
ˇ
H
n
é 2
n
, o que significa que mesmo existindo
um computador que possa avaliar 10
10
indivíduos por segundo (capacidade muito
além da existente atualmente, para a maioria das aplicações práticas), uma busca
exaustiva de
ˇ
H
n
para n 60, apenas, necessitaria de, pelo menos, anos, tempo
que só os mais pacientes (e saudáveis) seriam capazes de esperar. O que o PBIL faz
é direcionar a busca utilizando uma minúscula fração dos elementos de
ˇ
H
n
em cada
geração. Portanto é razoável empregar a relação
P = 2
n
w
(.)
com w > 1.
Uma característica interessante do PBIL é que, diferentemente de outros algo
ritmos baseados em populações, torna-se muito simples modificar o tamanho da
população em qualquer geração, bastando, para isso, modificar o número de indiví
duos sorteados à partir de P . Isso nos permite melhorar a eficiência do FPBIL.
Conforme as componentes de P se aproximam de d (ou 1 − d), a necessidade
de manter o mesmo tamanho da população diminui. Após c componentes de P
atingirem esta condição, seguindo a lógica da equação (.) na página precedente,
seria necessária uma população de apenas 2
n−c
w
indivíduos para dar conta das n − c
componentes restantes. Entretanto, este número deve ser multiplicado por um fator
f que garanta a reprodutibilidade das c componentes de P , consideradas corretas.
A probabilidade de sortear um indivíduo com c componentes “corretas” é (1−d)
c
,
o que significa que, em média, são necessários 1/(1 − d)
c
sorteios para garantir a
presença de um exemplar de tal indivíduo, mas às vezes é necessário um número
maior de sorteios (f = k · 1/(1 − d)
c
, com k > 1).
O tamanho da população no FPBIL, em cada geração, depende de c e possui a
seguinte expressão:
P
c
=
k
(1 − d)
c
· 2
n−c
w
. (.)
A escolha do valor de k será examinada mais adiante.
O valor de d, em qualquer geração será d
c
= 1/(1 + c) e, portanto, a equação
(.) pode ser reescrita como
P
c
= k
1 +
1
c
c
2
n−c
w
. (.)
A função ǫ(c) = (1 + 1/c)
c
é interessante pois lim
c→0
ǫ(c) = 1, lim
c→∞
ǫ(c) = e
e 1 < ǫ(c) < e para 0 < c < ∞. Isto nos permite relacionar w com P
0
simplesmente
por P
0
= k·2
n
w
. Eliminando w e rearrumando a equação (.), chega-se, finalmente,
a
P
c
= ǫ(c) · P
0
P
0
k
−
c
n
. (.)
A curva de P
c
é esboçada na figura . na página seguinte, juntamente com a curva
de ǫ(c) e com a curva que expressa o comportamento limite de P
c
: eP
0
(P
0
/k)
−
c
n
.
Com relação a k, verifica-se experimentalmente, como na figura . na próxima
página, que a distribuição da quantidade N de sorteios necessária para se conseguir
e
1
e
Figura .: Comportamento de P
c
.
Figura .: Distribuição de N.
um indivíduo com c componentes “corretas”, é uma exponencial decrescente, o que
significa que a densidade de probabilidade ρ(k ) de se sortear um indivíduo nessas
condições é, também, uma exponencial decrescente:
ρ(k) = ae
−bk
, (.)
onde k = N/N e N = 1/(1 − d)
c
é o número de sorteios, em média, necessários
para gerar tal indivíduo.
Resolvendo-se as equações
∞
0
ρ(k)dk = 1; (.)
k =
∞
0
k · ρ(k)dk =
N
N
= 1, (.)
chega-se à conclusão que a = b = 1 e, portanto, a variância de ρ(k) é
σ
2
=
∞
0
(k − 1)
2
· ρ(k)dk (.)
=
∞
0
k
2
· ρ(k)dk − 2
∞
0
k · ρ(k)dk +
∞
0
ρ(k)dk (.)
=
∞
0
k
2
e
−k
dk − 2 + 1. (.)
Esta última integral pode ser resolvida por partes:
∞
0
k
2
e
−k
dk = −k
2
e
−k
∞
0
+ 2
∞
0
ke
−k
dk (.)
= 0 + 2, (.)
o que significa que o desvio padrão σ também é 1.
Agora considere a integral
P (k) =
k
0
ρ(ζ)dζ. (.)
Ela representa a probabilidade de se sortear um indivíduo com c componentes “cor
Apesar do número N ser um inteiro na prática, nada impede de se trabalhar com a variável con-
tínua k e deixar o arredondamento para o final. Isso justifica o uso de densidades de probabilidade
e integrais. O mesmo raciocínio se aplica ao cálculo de P
c
.
retas” em N = k N = k/(1 − d)
c
tentativas — N é o fator que multiplica 2
n−c
w
na
equação (.) na página . Quanto maior o valor de k, menor a chance de falha.
A tabela . mostra alguns valores de P (k ) para os primeiros múltiplos do desvio
padrão σ.
Tabela .: Valores de P (k) para os primeiros múltiplos de σ.
m P (mσ)
1 0,6321205588
2 0,8646647168
3 0,9502129316
4 0,9816843611
5 0,9932620530
6 0,9975212478
7 0,9990881180
8 0,9996645374
9 0,9998765902
10 0,9999546001
Pode-se perceber que para k = 7σ = 7, a probabilidade de sortear um indivíduo
com c componentes “corretas” é aproximadamente 99,9 %. Portanto 7, o número da
perfeição, será o valor padrão de k. Esta é a linha da figura . na página .
Até agora, conseguimos aumentar a eficiência do FPBIL reduzindo o número
de avaliações desnecessárias, mas ainda temos que lidar com P
0
, que é agora o
responsável por fornecer poder de busca ao FPBIL. Quanto mais difícil o problema
a ser resolvido, maior este parâmetro deverá ser. Avaliar exatamente a dificuldade de
um determinado problema e relacionar cada nível de dificuldade a um P
0
específico
não é uma tarefa fácil.
Primeiramente deve haver um equilíbrio entre o sucesso do algoritmo e o número
de avaliações da aptidão — P
0
pode ser superestimado, fazendo com que o algoritimo
tenha sucesso, embora com um número de avaliações da aptidão desnecessariamente
grande. O valor ótimo de P
0
é o que possibilita que uma solução satisfatória seja
encontrada com o mínimo de avaliações da aptidão; e a única forma de conhecer
esse valor exatamente é experimentalmente.
A solução adotada pelo FPBIL é bem genérica e fundamentada na seguinte
observação. Em problemas simples, o número de componentes c de P consideradas
corretas cresce rapidamente e logo se aproxima de n. Quando o problema é mais
difícil, c cresce mais lentamente, sofrendo flutuações. O FPBIL simplesmente associa
o número de flutuações de c à dificuldade de um problema.
Neste ponto torna-se necessária uma definição precisa do que será chamado de
flutuação em c. Será computada uma flutuação em c sempre que este não crescer ou
decrescer diretamente, ou seja, sempre que c, como função de G atingir um ponto
de máximo, de mínimo ou simplesmente permanecer constante.
O FPBIL inicia com o menor P
0
possível: P
0
= P
n
, e, conforme as gerações
passam, P
0
é incrementado em 1 à cada flutuação sofrida por P.
Pode parecer arriscado iniciar a busca com “o menor P
0
possível”; também pode
parecer pouco o incremento de P
0
em apenas 1, contudo, observe a figura .. Ela
Figura .: P como função de c e P
0
. Do lado direito são mostradas as curvas de
nível correspondentes à superfície de P do lado esquerdo, o que ajuda a visualizar
que P atravessa um máximo, qua ndo c é pequeno.
mostra o comportamento de P conforme c e P
0
variam. A dependência de P com c
já foi evidenciada na figura . na página . Para facilitar a visualização de como
P varia com P
0
, podemos reescrever a equação (.) na página como
P
c
(P
0
) = ǫ(c)k
c
n
· P
n−c
n
0
, (.)
ou seja, P
c
(P
0
) varia como uma potência fracionária de P
0
. O menor valor que o
FPBIL admite para c é 2 (pois o maior valor permitido de d é 1/3). O comporta
mento de P, para valores pequenos de c, é próximo, então, de
P
2
(P
0
) = ǫ(2)k
2
n
· P
n−2
n
0
, (.)
que para n ≫ 2 se aproxima da reta
P(P
0
) = lim
n→∞
P
2
(P
0
) =
9
4
P
0
. (.)
O outro extremo é quando c ≈ n , quando P
c
(P
0
) ≈ k·ǫ(n) = P
n
, independentemente
de P
0
. Para qualquer outro valor de c, P
c
(P
0
) varia como uma raiz qualquer. Por
exemplo, quando c =
2
3
n, P
2
3
n
(P
0
) = ǫ(
2
3
n)k
2
3
·
3
√
P
0
— uma raiz cúbica.
Quando c é pequeno, independentemente da geração corrente, significa que P
está próximo de P
0
e o FPBIL ainda não tomou uma decisão firme de qual direção
seguir. Portanto, quanto mais tempo (gerações) permanecer esta situação, maior o
número de flutuações sofridas por c e maior a taxa com que P cresce (P ≈
9
4
P
0
) —
o FPBIL está procurando o parâmetro P
0
de acordo com a dificuldade do problema.
Imagine agora um ponto qualquer na superfície P
c
(P
0
) da figura . na página
anterior. Cinco situações podem acontecer:
c pode crescer diretamente Neste caso, não existe flutuação em c e, portanto,
P
0
não varia. Como conseqüência P decresce exponencialmente (base P
0
)
rumo à solução. Este é o caso ideal.
c pode sofrer flutuações sem, em média, variar Neste caso apenas P
0
cresce.
Como conseqüência P cresce como uma raiz qualquer de P
0
. Uma população
maior ajudará o FPBIL a decidir que direção P deverá seguir. Entretanto, se
esta situação se mantiver, pode significar que o algoritmo convergiu prematu
ramente.
c pode decrescer diretamente Neste caso também não existe flutuação em c.
Como conseqüência P cresce exponencialmente (base P
0
). O FPBIL está r e
tornando de um caminho errado e uma população crescendo nesta taxa ajudará
o FPBIL a corrigir o erro. Evidentemente, esta situação não perdura e acaba
por cair na próxima situação.
c pode decrescer em média, sofrendo flutuações Neste caso, c decresce en-
quanto P
0
cresce. Como conseqüência P continua crescendo.
c pode crescer em média, sofrendo flutuações Neste último caso, c e P
0
cres
cem. O que acontece com P vai depender dos valores de c e P
0
e da freqüência
das flutuações em c.
Como pode ser observado, o único risco que ocorre é se c crescer com P indo na
direção errada. Entretanto, o FPBIL possui mecanismos para minimizar essa possi
bilidade, a começar pela mutação que impede que c cresça desenfreadamente, mesmo
para pequenas populações. Entretanto, não existe como garantir que o algoritmo,
até este ponto, não convirja prematuramente.
O último recurso do FPBIL é retornar com P para o centro de H
n
e com d para
d
2
= 1/3 sempre que for detectada a convergência prematura.
Considere
c
G
=
1
G − G
i
+ 1
G
k=G
i
c
k
, (.)
que é a média dos valores de c desde a geração G
i
até a geração corrente G. G
i
é a
geração em que P e d são reinicializados. Inicialmente G
i
= 0 e c
G
cresce conforme
c cresce. À medida que aumentam as flutuações em c, este cresce mais lentamente,
o mesmo acontecendo com c
G
. Quando acontece de P tomar um caminho errado,
c praticamente pára de crescer e o algoritmo pode nunca encontrar uma solução
satisfatória.
Baseando-se nisso, o FPBIL monitora constantemente o valor de
∆c
G
= c
G
− c
G−1
, (.)
a variação de c
G
. Toda vez que ∆c
G
atinge valores próximos de 0, significa que
possivelmente o FPBIL ficou preso em um ótimo local. Embora seja sempre possível
escapar, na maioria das vezes a solução procurada é encontrada mais rapidamente
reinicializando-se P e d.
Essa alteração dos valores de P e d poderia ser considerada uma espécie de
mutação, entretanto é radical demais. A real intenção por de trás dessa operação é
reiniciar o FPBIL com cada vez maior poder de busca.
Quando, no início de uma geração G
k
qualquer, verifica-se que ∆c
G
< 1% (um
pouco mais que
1
2
◦
de inclinação), o FPBIL é reinicializado com uma importantíssima
diferença: P
0
será maior do que quando o algoritmo inicializou pela última vez.
Conseqüentemente, P dá um salto — graças à combinação de P
0
grande (inalterado)
com c pequeno (agora igual a 2) — fazendo com que seja cada vez menos provável
que o FPBIL erre o caminho. G
i
torna-se G
k
e o algoritmo continua — mais forte.
Utiliza-se c
G
— e não simplesmente c, por exemplo — por este variar mais
suavemente. Iniciando o FPBIL com P
0
= P
n
e incrementando P
0
em 1 à cada
flutuação de c são medidas que visam apenas contribuir com a eficiência do al goritmo.
Comparação Entre os
Algoritmos
finalidade deste capítulo é explicitar as diferenças na execução dos
algoritmos PBIL original e FPBIL, apresentados nos capítulos e
. Também serão examinados os algoritmos que serão chamados de
PBIL
∗
e FPBIL
∗
.
O PBIL
∗
é simplesmente o PBIL com população igual a 1.000, mantendo o
restante dos parâmetros inalterados. O FPBIL
∗
é o FPBIL sem reinicializações e
com P
0
fixo, igual a 1.000.
A comparação entre o FPBIL e o FPBIL
∗
, em particular, mede até que ponto as
reinicializações são realmente importantes ou se são um desperdício de computação
e o FPBIL, ao invés, deveria adotar a escolha do parâmetro P
0
.
Esses 4 algoritmos serão testados em 3 problemas de classes diferentes. São eles:
O problema quatro picos, que é multimodal, altamente deceptivo e os indivíduos
deste não necessitam ser decodificados, já que são avaliados diretamente sobre H
n
.
O problema banana, que é um problema clássico de minimização numérica conhecido
por dificultar a execução de algoritmos de otimização baseados em gradiente. E o
Problema do Caixeiro Viajante (PCV) Rykel, que é um problema combinatório
multimodal que exige um tipo diferente de representação denominado random keys,
que automaticamente incorpora as restrições impostas pelo problema.
O problema PCV Rykel tem uma importância especial neste trabalho, uma vez
que o problema da recarga nuclear, tratado no próximo capítulo, pertence a mesma
classe deste e, portanto, as mesmas técnicas e estratégias devem causar respostas
semelhantes em ambos.
. Considerações Iniciais
Antes de discutir as peculiaridades de cada problema teste, existem questões
comuns que se aplicam a todos os casos as quais serão sucintamente consideradas.
.. Código de Gray
No FPBIL (e no PBIL), uma região S
B
de interesse do espaço de busca é re
presentada por meio de vetores binários, os elementos de
ˇ
H
n
, significando que a
decodificação dos indivíduos — escolha de M
n
S
B
— t em influência sobre o desempe
nho do algoritmo.
Por exemplo, considere a função aptidão A
1
definida na tabela .. Pode-se per
ceber que o indivíduo mais apto é I
†
= 1000. Imagine (em uma situação hipotética)
que, com a exceção dele, todos os indivíduos são sorteados uma única vez. A partir
da equação (.) na página conclui-se que P
′
= (0,048; 0,884; 0,694; 0,599) e po
demos calcular P
′
(I ), que é a probabilidade do indivíduo I ser sorteado à partir
de P
′
, bem como a razão entre P
′
(I ) e P
0
(I ), sendo P
0
(I ) a probabilidade de
se sortear I ao acaso.
Compare esses valores com os corresp ondentes aos da função aptidão A
2
defi
nida na tabela . na página . Da mesma forma, I
†
= 1100 não participa da
atualização do vetor de probabilidades e todos os outros indivíduos são sorteados
uma única vez resultando em P
′
= (0,048; 0,878; 0,394; 0,476).
As duas funções aptidão são evidentemente diferentes. Entretanto, ambas po
dem ser funções aptidão do mesmo problema: o de encontrar o valor de x ∈ [0, 8]∩N
que maximiza a função f(x) = x
2
em que, a fim de evitar x fora do seu domínio,
Tabela .: Definição da funçã o aptidão A
1
e os valores de P
′
(I ) e de
P
′
(I )/P
0
(I ), onde P
′
é o vetor de proba bilid ades gerado a partir de todos
os indivíduos, com exceção de I
†
, admitindo que cada indivíduo é sorteado uma
única vez.
I A
1
(I ) P
′
(I ) P
′
(I )/P
0
(I )
0000 0 0,01353 0,216
0001 1 0,02018 0,323
0010 4 0,03067 0,491
0011 9 0,04575 0,732
0100 16 0,10348 1,656
0101 25 0,15435 2,470
0110 36 0,23456 3,753
0111 49 0,34985 5,598
1000 64 0,00068 0,011
1001 1 0,00101 0,016
1010 1 0,00153 0,024
1011 1 0,00229 0,036
1100 1 0,00517 0,083
1101 1 0,00772 0,123
1110 1 0,01173 0,188
1111 1 0,01749 0,280
Tabela .: Definição da funçã o aptidão A
2
e os valores de P
′
(I ) e de
P
′
(I )/P
0
(I ), onde P
′
é o vetor de proba bilid ades gerado a partir de todos
os indivíduos, com exceção de I
†
, admitindo que cada indivíduo é sorteado uma
única vez.
I A
2
(I ) P
′
(I ) P
′
(I )/P
0
(I )
0000 0 0,0370 0,592
0001 1 0,0336 0,538
0011 4 0,0219 0,350
0010 9 0,0241 0,386
0110 16 0,1727 2,764
0111 25 0,1570 2,512
0101 36 0,2410 3,855
0100 49 0,2650 4,241
1100 64 0,0132 0,212
1101 1 0,0120 0,193
1111 1 0,0078 0,126
1110 1 0,0086 0,138
1010 1 0,0012 0,019
1011 1 0,0011 0,018
1001 1 0,0017 0,027
1000 1 0,0018 0,030
penaliza-se f da seguinte forma:
f(x) =
x
2
, se x ≤ 8;
1, se x > 8.
(.)
A única diferença é que no primeiro caso, M
n
S
B
é a transformação natural de
números na base 2 para os correspondentes números na base 10, enquanto que no
segundo caso M
n
S
B
transforma a partir de vetores binários utilizando o código de
Gray
[]. Essa diferença aparentemente sem importância é a responsável p or
P
′
(I
†
) ser, aproximadamente, 20 vezes maior com a utilização do código de Gray,
o que é bem significativo.
O motivo para uma diferença tão acentuada resulta do fato de a função aptidão
na tabela . na página t er sido construída sob medida para falhar. Observe
que I
†
difere do segundo melhor indivíduo em todos os bits. A conseqüência dessa
“descontinuidade em
ˇ
H
n
” é que P
′
(I
†
) é menor mesmo que P
′
(I
−
), correspondente
ao pior indivíduo. A vantagem do código de Gray é que este representa números
consecutivos como vetores binários que diferem sempre por apenas um bit.
A se qüência Γ
n
do código de Gray com n bits pode ser construída recursivamente
a partir de
Γ
0
= ǫ; (.)
Γ
k+1
= 0Γ
k
, 1Γ
R
k
, (.)
onde ǫ é a “seqüência” vazia, 0Γ
k
é a seqüência anterior precedida do bit 0 e 1Γ
R
k
é
a seqüência anterior, em ordem reversa, precedida do bit 1.
O código de Gray recebe seu nome de Frank Gray, um físico que ficou famoso por ajudar a
planejar o método de transmissão de sinais de TV a cores. Gray criou o código para transmissão
analógica de dados digitais.
Por exemplo, para construir Γ
3
seguem-se os seguintes passos:
Γ
0
= ǫ; (.)
Γ
1
= 0, 1; (.)
Γ
2
= 00, 01, 11, 10; (.)
Γ
3
= 000, 001, 011, 010, 110, 111, 101, 100. (.)
A primeira coluna da tabela . na página corresponde a Γ
4
que é construída
facilmente a partir de Γ
3
acima.
Testes [] realizados comparando o desempenho do PBIL utilizando a codificação
binária natural e o código de Gray mostram que a utilização do código de Gray au
mentou o desempenho do algoritmo em 100% dos casos. Assim, todos os problemas
tratados neste trabalho utilizarão o código de Gray.
.. Minimizando o Impacto sobre a Escolha da Aptidão
Embora o FPBIL seja livre de parâmetros, este ainda depende da forma exata da
aptidão. Existem várias formas funcionais para A capazes de determinar a mesma
ordem A(I
−
) ≤ A(I
i
) ≤ A(I
j
) ≤ ··· ≤ A(I
+
) e cada uma delas pode gerar D e
ξ diferentes, o que resultaria em comportamentos igualmente diferentes. Considere
a análise das equações (.) e (.) na página em dois exemplos simples.
. Com a transformação A
′
i
= f · A
i
(f ∈ R), temos que D
′
= D e ξ
′
= ξ, ou
seja, a multiplicação da aptidão por um fator constante, não altera em nada o
comportamento do FPBIL.
. Já com a transformação A
′
i
= t + A
i
(t ∈ R); D
′
= D, porém
ξ
′
=
A
A + t
ξ, (.)
significando que se t ≫ A então ξ
′
≈ 0, ou seja, a adição da aptidão com um
termo constante, altera a intensidade dos passos do FPBIL, podendo tornar o
FPBIL impraticável para grandes valores de t.
O item sugere que uma boa prática pode ser o emprego da aptidã o A
′
i
=
A
i
− A(I
−
), garantindo que ξ nunca será menor que o necessário.
A equação (.) na página mostra que a escolha de aptidões com valores
exageradamente grandes podem resultar em ξ muito próximos de zero, quando δ →
0. Isso geralmente ocorre quando P se aproxima de um vértice de H
n
, atrasando
demasiadamente a convergência do FPBIL. Essa observação desencoraja o uso da
transformação A
′
i
= (A
i
)
n
(n ∈ N) para valores grandes de n, como tentativa
de aumentar as contribuições dos indivíduos A(I
−
) e A(I
+
) na equação (.) na
página .
Seguindo tais recomendações, adotou-se um procedimento genérico para se cons
truir a aptidão — baseado no procedimento empregado por Koza no algoritmo da
programação genética [] — descrito a seguir.
Chama-se de aptidão bruta, A
b
, a quantidade natural do problema que se deseja
maximizar ou minimizar, também chamada de função objetivo.
Por exemplo, se o objetivo de um problema é maximizar uma função f(x),
A
b
(I
i
) = f
x(I
i
)
, (.)
com x(I
i
) = M
n
S
B
(I
i
). Se em um outro problema o objetivo é minimizar o tempo
de execução de um processo,
A
b
(I
i
) = t(I
i
), (.)
com t(I
i
) = M
n
S
B
(I
i
), onde t(I
i
) é o tempo medido de um processo executado
com os parâmetros codificados em I
i
.
A partir da aptidão bruta, constrói-se a aptidão padrão, A
p
, que possui a caracte
rística de 0 ≤ A
p
(I
a
) < A
p
(I
b
) sempre que I
a
é melhor que I
b
, e, de preferência,
com A
p
(I
†
) = 0. A aptidão padrão construída a partir da equação (.) na página
anterior pode ser então
A
p
(I
i
) = A
máx
− A
b
(I
i
), (.)
onde A
máx
é uma estimativa de A(I
†
). Uma outra possibilidade seria
A
p
(I
i
) =
1
A
b
(I
i
)
, (.)
desde que A
b
(I
i
) > 0, ∀i. Já para a equação (.) na página precedente, a aptidão
padrão pode ser simplesmente
A
p
(I
i
) = A
b
(I
i
). (.)
Com a aptidão padrão, calcula-se a aptidão ajustada, A
a
, a partir de
A
a
(I
i
) =
1
1 + A
p
(I
i
)
. (.)
O comportamento da aptidão ajustada é ilustrado na figura .. Pode-se per
Figura .: Comportamento da aptidão ajustad a.
ceber que A
a
possui algumas propriedades interessantes. Em primeiro lugar, A
a
elimina o problema de ξ chegar muito próximo de zero, pois está limitada a [0, 1], in
dependentemente da escolha de A
b
. Em segundo lugar, a medida que os indivíduos
se tornam melhores (A
p
(I
i
) → 0), a diferença na aptidão de indivíduos próximos
torna-se mais acentuada, garantindo competitividade até o final.
Seguindo a recomendação de se ter A
′
i
= A
i
−A(I
−
), a função aptidão utilizada
em todos os problemas deste trabalho será
A(I
i
) =
A
a
(I
i
) − A
a
(I
−
G−1
), se A
a
(I
i
) − A
a
(I
−
G−1
) ≥ 0;
0, se A
a
(I
i
) − A
a
(I
−
G−1
) < 0,
(.)
onde A
a
(I
−
G−1
) é a aptidão ajustada do pior indivíduo da geração anterior.
A razão para se utilizar A
a
(I
−
G−1
) é que, para encontrar A(I
−
), é necessá
rio avaliar todos os indivíduos da geração, o que implica que, para seguir à risca
a recomendação de se ter A
′
i
= A
i
− A(I
−
), ou todos os indivíduos devem ser
avaliados duas vezes por geração ou todos os indivíduos de uma geração devem
ser armazenados em uma estrutura de dados. A solução adotada, além de econô
mica, não agride demasiadamente a recomendação original, visto que geralmente
A
a
(I
−
G−1
) ≈ A
a
(I
−
).
.. Procedimento Geral
Como o FPBIL e o FPBIL
∗
possuem populações de tamanho variável (e o PBIL
e o PBIL
∗
não), as comparações não foram feitas de geração em geração, e sim depois
de um mesmo número de avaliações da aptidão. O número de avaliações da aptidão
após G gerações é
0
P +
1
P + ··· +
G
P, que corresponde à soma dos tamanhos das
populações de cada geração.
Todos os algoritmos foram executados até atingir 1.000.000 avaliações da aptidão
e, a fim de estimar o melhor valor encontrado por um algoritmo após um determinado
número de avaliações da aptidão, os melhores valores ao final de cada geração são
computados e, então, por meio de splines, o valor no ponto desejado é interpolado.
Em todos os testes, são interpolados 10.000 pontos igualmente espaçados —
tanto em escala linear como em logarítmica — a partir dos quai s são calculados as
médias e os desvios. Adotou-se o critério de que para 0 avaliações da aptidão (1,
para a escala logarítmica), o melhor valor correspondente deve ser igual ao melhor
valor encontrado ao final da geração 0 — razão pela qual, nos gráficos, os valores
para o número de avaliações entre 0 (ou 1) e o tamanho da população da geração 0
praticamente não variam.
Nos problemas banana e quatro picos, as médias e os desvios apresentados nos
gráficos são calculados a partir de 100 execuções independentes de cada algoritmo.
Para o problema PCV Rykel, os algoritmos foram executados até que o desvio
relativo máximo fosse de 1%.
. Problemas Testes
.. Quatro Picos
Considere as duas funções definidas em
ˇ
H
100
:
Z(I ) = número de 0’s contíguos em I term inando na posição ; (.)
U(I ) = número de 1’s contíguos em I iniciando na posição ; (.)
onde, por exemplo, U(011 ···111) = 0, U(111 ···111) = 100, Z(111 ···110) = 1 e
Z(000 ···010) = 1. Considere também a função prêmio
P
Z(I ), U(I ); T
=
100 + T, se Z(I ) ≥ T e U(I ) ≥ T ;
0, caso contrário.
(.)
definida em {0, 1, 2, . . . , 100}
2
× {0, 1, 2, . . . , 50}. No problema quatro picos, o obje
tivo é maximizar a função
Q
T
(I ) = máx{Z(I ), U(I )}+ P
Z(I ), U(I ); T
. (.)
Observando o gráfico de Q
T
na figura ., percebe-se que o problema quatro
picos é altamente deceptivo. Existem duas regiões. Uma premiada, correspondente
100100 80 8060 6040 4020 2000
150
0
200
100
50
20
0
100
100
80
80
60
40
60
20
0
40
Figura .: Gráfico de Q
T
(I ), função objetivo do pr oblema quatro picos.
à superfície de cima, e outra não premiada, correspondendo à super fície de baixo.
Nenhum ponto da região não premiada (que aumenta com T ) fornece qualquer indi
cação da existência do prêmio, dando a falsa impressão da existência de apenas os
picos P
1
e P
2
— que correspondem a Q
T
(I ) = 100 — enquanto existem ainda os
picos P
3
e P
4
— correspondendo a Q
T
(I ) = 200, os ótimos globais.
No problema quatro picos, existe um total de
=.......
.. possíveis indivíduos. Uma vez que os primeiros indivíduos da região pre
miada são encontrados, alcançar o pico P
3
(ou P
4
) torna-se trivial. A dificuldade do
problema quatro picos depende do valor de T — dificuldade esta que aumenta com
T . No limite em que T = 0, a região não premiada desaparece, juntamente com os
picos P
1
e P
2
. No outro extremo, quando T = 50, a região premiada colapsa em um
único ponto: P
3
≡ P
4
. Verifíca-se, sem muita dificuldade, que a probabilidade de se
sortear ao acaso um indivíduo da região premiada é 1/2
2T
, tornando
D(T ) ≡ 2
2T
(.)
uma medida da dificuldade do problema de acordo com o parâmetro T .
Conclui-se, então, que D(T + 1) = 4 · D(T ), ou seja, a dificuldade quadruplica
quando T é acrescido de 1. Todos os testes do problema quatro picos, realizados
neste trabalho tiveram T = 30, correspondendo a uma dificuldade 20 vezes maior
que a máxima dificuldade utilizada em [], quando, dentre um total de 25 execuções,
o PBIL convergiu prematuramente (para um ótimo local) 20 vezes e os algoritmos
genéticos, entre 22 e 25 vezes.
... Representação
A forma como o problema quatro picos foi definido não permite muita liberdade
na escolha de representações distintas. Cada indivíduo é um vetor de 100 bits e,
como Q
T
é avaliada diretamente sobre
ˇ
H
100
, o código de Gray não é aplicável (nem
nenhum outro).
... Aptidões Bruta e Padrão
A aptidão bruta do problema quatro picos utilizada será simplesmente o valor
de Q
T
(I ):
A
b
(I
i
) = Q
T
(I
i
). (.)
Como se trata de um problema de maximização e A
p
(I
†
) = 200, a aptidão padrão
utilizada será
A
p
(I
i
) = 200 − Q
T
(I
i
). (.)
... Resultados
A figura . na página seguinte mostra o resultado da comparação entre o FPBIL
e o PBIL Original, onde estão plotadas as médias das melhores aptidões de cada
execução para cada algoritmo. Das 100 execuções, o PBIL não conseguiu alcançar a
região premiada em nenhuma delas, enquanto que o FPBIL a alcançou todas, tendo
Figura .: Comparação entre o FPBIL e o PBIL.
como pior resultado A
b
(I
i
) = 178.
Em seguida, o PBIL
∗
é comparado com o FPBIL
∗
. O resultado é mostrado na
figura . na próxima página, que indica um comportamento semelhante.
Comparando o FPBIL com o FPBIL
∗
, o FPBIL se mostra superior, conforme
indica a figura . na página seguinte. Uma diferença importante entre o FPBIL
e o FPBIL
∗
é que o FPBIL
∗
falha em alcançar a região premiada em 4 das 100
execuções, tendo como pior resultado A
b
(I
i
) = 65, não atingindo sequer os picos
P
1
e P
2
da região não premiada.
O PBIL contra o PBIL
∗
, mostrado na figura . na página indica que existe
pouca diferença entre os dois, embora a figura . na página indique o curioso fato
de que o aumento da população do PBIL não necessariamente implica o aumento
do desempenho para um número fixo de avaliações da função aptidão.
No problema quatro picos, a observação da evolução do vetor de probabilidade
Figura .: Comparação entre o FPBIL
∗
e o PBIL
∗
.
Figura .: Comparação entre o FPBIL e o FPBIL
∗
.
Figura .: Comparação entre o PBIL e o PBIL
∗
.
Figura .: Detalhe do PBIL contra o PBIL
∗
.
fornece uma visão muito peculiar sobre o funcionamento dos algoritmos. A figura .,
por exemplo, ilustra uma execução típica do FPBIL. Pode-se observar claramente
Figura .: Evolução típica do vetor de probabilidades do FPBIL.
que durante as 1.000.000 avaliações da aptidão houve 4 reinicializações. Depois da
segunda reinicialização, por volta da
a
geração, o FPBIL claramente atingiu o
ótimo global. Já o PBIL, conforme mostra a figura . na página seguinte, converge,
por volta da
a
geração, para P
2
. Também é interessante notar a ocorrência da
mutação no PBIL. A região branca indica que a correspondente componente do vetor
de probabilidades é exatamente 1. As várias manchas vermelhas ocorrem quando a
mutação atinge uma determinada comp onente, fazendo com que esta se aproxime
do valor 0.5.
Figura .: Evolução típica do vetor de probabilidades do PBIL.
.. Banana
O problema banana consiste em minimizar a função de Rosenbrock []:
B(x, y) = 100 (y − x
2
)
2
+ (1 − x)
2
. (.)
A partir da simples observação da expressão dessa equação conclui-se sem dificul
dade que o mínimo de B(x, y) ocorre para (x, y) = (1, 1). Também não é difícil
mostrar analiticamente que esse é o único ponto em que B(x, y) se torna invari
ante. Entretanto, observando o gráfico de B(x, y) na figura . na próxima página,
torna-se impossível chegar à mesma conclusão.
É um tanto evidente a existência do vale localizado em y = x
2
, mas visualizar
o ponto exato do vale onde B(x, y) é mínimo não é nada simples. A dificuldade
para tal visualização deve-se ao fator 100 que multiplica apenas (y − x
2
)
2
, deixando
o termo (1 − x)
2
de fora. Somente quando observado em escala logarítmica, como
na figura . na página é que torna-se aparente a região onde o mínimo está
Figura .: Gráfico de B(x, y), função objetivo do problema banan a.
localizado. A linha branca é uma curva de nível que evidencia o formato de banana,
que dá nome ao problema.
A função de Rosenbrock é classicamente utilizada para testar algoritmos de otimi
zação, justamente pela dificuldade que esta impõe, especialmente para os algoritmos
baseados em gradiente.
... Representação
O conjunto S
B
⊂ R que será codificado em vetores binários, para a utilização
dos algoritmos, é [−4,194.304; 4,194.304)
2
, com uma granulação de 0,000.001 em
ambas as variáveis x e y. Isto significa que cada variável necessita de 23 bits para
representar S
B
, resultando num total de
=.... possibilidades.
Mais formalmente, tem-se, com n = 2 · 23 = 46,
M
n
S
B
(I ) = (x, y), (.)
Figura .: Curvas de nível de log
10
B(x, y). A curva de cor branca, em forma
de banana, destaca a região azul em que se encontra o ponto de mínimo.
com
x = −4,194.304 +
G
1
(I )
1.000.000
; (.)
y = −4,194.304 +
G
2
(I )
1.000.000
, (.)
onde G
1
(I ) é a decodificação da primeira metade de I e G
2
(I ), da segunda, ambas
utilizando o código de Gray.
... Aptidões Bruta e Padrão
A aptidão bruta do problema banana utilizada neste trabalho é simplesmente o
valor de B(x, y):
A
b
(I
i
) = B(x, y) = B ◦ M
n
S
B
(I
i
). (.)
Como se trata de um problema de minimização e A
p
(I
†
) = 0, a aptidão padrão
utilizada será a própria aptidão bruta:
A
p
(I
i
) = B ◦ M
n
S
B
(I
i
). (.)
... Resultados
Comparando o FPBIL com o PBIL original, na busca pelo mínimo, no problema
banana, vê-se que a vantagem inicial do PBIL é superada em muito nas últimas
avaliações da aptidão (por um fator de aproximadamente 10
6
), como mostra a figura
.. O PBIL fica estagnado logo depois da
a
avaliação da aptidão, mas o valores
Figura .: Comparação entre o FPBIL e o PBIL.
B(x, y) encontrados pelo FPBIL continuam decrescendo a uma taxa contínua até o
final.
O FPBIL
∗
, porém, parece não diferir muito do PBIL
∗
, conforme ilustra a figura
. na página seguinte. Apenas uma leve vantagem do PBIL
∗
. Entretanto, nova
mente, o PBIL
∗
logo fica estagnado, enquanto o FPBIL
∗
demonstra possuir ainda
Figura .: Comparação entre o FPBIL
∗
e o PBIL
∗
.
um potencial para encontrar uma solução melhor. A figura . na próxima página
mostra esse detalhe.
O FPBIL também se mostra superior frente ao FPBIL
∗
no final da execução,
como se vê na figura . na página seguinte.
Por último, o PBIL é comparado com o PBIL
∗
, indicando que, neste caso, o au
mento da população fez a diferença, ainda que irrisória (comparada com a diferença
entre o PBIL e o FPBIL), como mostra a figura . na página .
Figura .: Detalhe do FPBIL
∗
contra o PBIL
∗
.
Figura .: Comparação entre o FPBIL e o FPBIL
∗
.
Figura .: Comparação entre o PBIL e o PBIL
∗
.
.. PCV Rykel
Um caixeiro viajante deve percorrer N cidades, retornando ao final à cidade de
origem, de modo que nenhuma cidade seja visitada mais de uma vez. Existem várias
rotas possíveis (para N > 2); na realidade váá ··· árias — com o número de á’s igual
a N — pois o número de rotas é (N − 1)! (fatorial, não ponto de exclamação!). O
problema do caixeiro viajante (PCV) consiste em encontrar a rota mais curta.
O PCV é um problema da classe NP, significando que não existe hoje
um
algoritmo de ordem polinomial que o resolva. A classe NP pode ser considerada
uma classe de complexidade computacional intermediária entre as classes P e EXP,
pois apenas a quantidade descomunal de combinações é responsável pela demanda
de tempo []; a avaliação de cada combinação geralmente é a parte mais fácil.
Pode ser que nunca venha a existir tal algoritmo. Quem solucionar essa questão será dono
de US$ 1,000,000.00 do Clay Mathematics Institute, já que o problema P versus NP é um dos
problemas do milênio [].
Rykel [] é um PCV assimétrico de cidades resultando num total de
................... ro
tas possíveis. Em um PCV assimétrico a distância de uma cidade A até uma outra
B pode ser diferente da distância de B até A, talvez modelando vias de uma única
mão. Embora os PCVs simé tricos e assimétricos compartilhem o mesmo número de
rotas, para o mesmo valor de N, a assimetria embaralha a topologia do espaço de
busca, resultando em PCVs mais complexos.
Uma diferença importante do PCV Rykel para os problemas anteriores é que
a restrição de que nenhuma cidade seja visitada mais de uma vez impede que as
rotas sejam codificadas em vetores binários de forma direta. As rotas devem ser
representadas de uma forma indireta.
... Representação Random Keys
Considere um PCV com 3 cidades, A, B e C. Três objetos necessitam de 2 bits
para serem representados em vetores binários, como mostra a tabela ., e uma rota
Tabela .: Representação binária de 3 cidades.
Representação Binária Cidade
00 A
01 B
11 C
10 ⋄
pode ser representada por um vetor binário de 6 bits. A tabela tabela . fornece as
duas rotas válidas possíveis. No caso de PCV simétrico estas duas teriam o mesmo
Tabela .: Representação binária d as possíveis rotas.
I Rota
000111 A→B→C
001101 A→C→B
comprimento.
O problema surge quando se tenta sortear uma rota a partir de um vetor de pro
babilidades. A tabela . ilustra algumas possibilidades, a maioria delas inválidas.
Tabela .: Possíveis rotas. A maioria delas inválidas.
I Rota
000000 A→A→A
001100 A→C→A
000110 A→B→⋄
101010 ⋄→⋄→⋄
111010 C→⋄→⋄
011100 B→C→A
010001 B→A→B
110001 C→A→B
A estratégia da representação random keys [] é representar não as cidades (ou
quaisquer que sejam os objetos), mas números — a chave — que, quando ordenados,
determinam a ordem em que as cidades devem ser arranjadas em uma rota
. Em
caso de empate, a ordem natural prevalece.
Os mesmos indivíduos da tabela . podem agora gerar rotas sempre válidas.
A tabela . na página seguinte mostra como. Primeiramente c ada indivíduo é
decodificado (utilizando o código de Gray, neste exemplo) em uma seqüência, do
tamanho do número de cidades participantes, de números inteiros — os dentes da
chave —, cada um associado a uma cidade de acordo com a ordem nat ural das
cidades. Em seguida, os dentes das chaves são ordenados. Como conseqüência, as
cidades associadas aos dentes de chave são juntamente reordenadas, gerando rotas
válidas.
O preço que se paga com a utilização da representação random keys é a perda
da bijetividade entre
ˇ
H
n
e o conjunto das rotas válidas, o que pode dificultar o
O modelo de listas [] é outra forma de representação desse tipo mas, como verificado em [],
é menos eficaz que o random keys.
Tabela .: Rotas válidas utilizando a representação random keys.
I Chave Chave ordenada Rota
000000 0
A
, 0
B
, 0
C
0
A
, 0
B
, 0
C
A→B→C
001100 0
A
, 2
B
, 0
C
0
A
, 0
C
, 2
B
A→C→B
000110 0
A
, 1
B
, 3
C
0
A
, 1
B
, 3
C
A→B→C
101010 3
A
, 3
B
, 3
C
3
A
, 3
B
, 3
C
A→B→C
111010 2
A
, 3
B
, 3
C
2
A
, 3
B
, 3
C
A→B→C
011100 1
A
, 2
B
, 0
C
0
C
, 1
A
, 2
B
C→A→B
010001 1
A
, 0
B
, 1
C
0
B
, 1
A
, 1
C
B→A→C
110001 2
A
, 0
B
, 1
C
0
B
, 1
C
, 2
A
B→C→A
aprendizado; bem como a ocorrência de empates, que reforçam sempre a ordem
natural das cidades.
Uma outra questão é que o número de bits representando cada dente da chave
pode ser qualquer um. Quanto menor o número de bits, maior o número de empates;
quanto maior o numero de bits, maior a perda de bijetividade e maior o t amanho
de P . Intuitivamente, um número de bits de valor intermediário deve ser a me lhor
escolha.
Para o PCV Rykel, neste trabalho, serão testados dentes de chave com respec
tivamente 6, 9 e 12 bits, r esultando em buscas sobre
ˇ
H
288
,
ˇ
H
432
e
ˇ
H
576
, respectiva
mente.
... Aptidões Bruta e Padrão
A aptidão bruta do PCV Rykel utilizada neste trabalho é simplesmente o
comprimento C
i
de cada rota correspontente ao indivíduo I
i
:
A
b
(I
i
) = C
i
. (.)
Como se trata de um problema de minimização, poder-se-ia ter A
p
(I
i
) = A
b
(I
i
).
Porém, como A
p
(I
†
) = 14.422 = 0, a aptidão padrão utilizada será
A
p
(I
i
) = C
i
− 14.422. (.)
... Resultados
O primeiro teste realizado com o PCV Rykel foi o de determinar um valor
razoável para o número de bits codificando cada dente da chave. Como são 48
cidades, o menor número de bits por dente capaz de gerar uma chave sem empates
é 6 — com 5 bits é possível gerar apenas 2
5
= 32 dentes diferentes. A figura
. mostra como o desempenho do FPBIL é influenciado por essa grandeza para
6 (mínimo), 12 (dobro do mínimo) e 9 (um valor intermediário) bits por chave.
Verifica-se que até cerca de 10
3
avaliações da função aptidão, os três casos possuem
Figura .: Comparação entre os algoritmos FPBIL para representações ran-
dom keys de, respectivamente, 6, 9 e 12 bits por dente de chave.
o mesmo comportamento. A figura . na página seguinte ilustra os mesmos dados
para os comprimentos de rota menores que 20.000. O pior desempenho certamente
Figura .: Detalhe da figura . na página anterior.
ocorre para 6 bits. Com 12 bits o FPBIL é um pouco melhor que com 9 até cerca
de 500.000 avaliações, quando o FPBIL com 9 bits passa a dominar. Esta situação
prevalece até o final, embora o FPBIL com 12 bits apresente um potencial de queda
razoável nas últimas avaliações.
O mesmo teste foi realizado com o PBIL. A figura . na próxima página mostra
o resultado. Até cerca de 10
4
avaliações da aptidão, o desempenho independe do
número de bits por dente das chaves. A figura . na página seguinte mostra mais
claramente os mesmos dados para os comprimentos de rotas menores que 20.000.
Observa-se, mais uma vez, que 6 bits por dente de chave produz o pior desempenho.
Entretanto, o PBIL com 12 bits parece manter uma leve vantagem em comparação
com o PBIL com 9 bits, embora a diferença entre esses casos seja menor que os
correspondentes desvios padrão.
A partir dos testes anteriores, parece razoável utilizar 9 bits por dente das chaves,
para as comparações entre o PBIL original e o FPBIL. É o que mostra a figura ..
Visto em detalhe na figura . na próxima página, o FPBIL mantém a vantagem
Figura .: Comparação entre o FPBIL e o PBIL.
durante quase toda a execução dos algoritmos, especialmente nas últimas 500.000
avaliações.
A figura . na página seguinte mostra os valores mínimos e máximos ao final de
um determinado número de execuções dos algoritmos. A rota mais curta encontrada
pelo FPBIL foi 14.674, apenas 1,75% maior que o ótim o global. Nota-se que o PBIL
apresenta uma maior dispersão em torno da média.
Neste ponto, vale ressaltar que a rota mais curta do PCV Rykel, cujo com
primento vale 14.422, não é facilmente encontrada por nenhm algoritmo de busca
de propósito geral. Por exemplo, os algoritmos genéticos só alcançam valores pró
ximos a 16.500 [] e os algoritmos baseados em colônias de formigas, desenhados
especificamente para encontrar as menores rotas, alcançam o valor ótimo somente
quando processados em paralelo, mesmo assim, apenas quando auxiliados de heurís
ticas []. A figura . na próxima página m ostra que o PBIL é capaz de alcançar
Figura .: Detalhe do FPBIL contra o PBIL.
Figura .: Valores mínimos e máximos ao final de um número de execuções.
valores p ouco abaixo de 15.000. O fato de o FPBIL encontrar rotas com compri
mento de 14.674 é uma conquista considerável.
Em seguida, o PBIL
∗
é comparado com o FPBIL
∗
. As figuras . e . apre
sentam os resultados. O FPBIL
∗
é superior, embora perca nas primeiras avaliações.
Figura .: Comparação entre o FPBIL
∗
e o PBIL
∗
.
Finalmente, os algoritmos FPBIL e FPBIL
∗
são comparados juntamente com o
PBIL e PBIL
∗
. As figuras . e . indicam que, embora o FPBIL perca para
um número intermediário de avaliações, este é melhor para até cerca de 300.000
avaliações e empata com o FPBIL
∗
no final de 10
6
avaliações. A figura . na
página confirma o empate e até mostra uma tendência do FPBIL em passar para
a liderança.
A comparação entre o PBIL e o PBIL
∗
, most rado nas figuras . e ., confirma
que o PBIL original não se torna necessariamente mais eficiente com o aumento da
população.
Figura .: Detalhe do FPBIL
∗
contra o PBIL
∗
.
Figura .: Comparação entre o FPBIL e o FPBIL
∗
.
Figura .: Comparação entre o PBIL e o PBIL
∗
.
Figura .: Detalhe do PBIL contra o PBIL
∗
.
Tem-se, portanto, que em todos os testes realizados, ficou comprovado o de
sempenho superior do FPBIL, evidenciando o grande potencial deste, na solução
de problemas de classes variadas. No próximo capítulo, o FPBIL será aplicado ao
problema da recarga nuclear.
FPBIL Aplicado ao Problema
da Recarga Nuclear
m dos problemas de grande interesse da engenharia nuclear diz respeito à
recarga nuclear. Trata-se de uma questão que, como se verá oportuna
mente, apresenta várias sutilezas e grande complexidade. O problema
da recarga nuclear será utilizado como último teste para o FPBIL neste
trabalho, e colocará à prova o seu desempenho. Este capítulo descreve como o FPBIL
pode ser aplicado ao problema e o compara, ao final, com as mais atuais e bem-su
cedidas técnicas de otimização.
. Descrição do Problema
Iniciada a operação da usina, a concentração de material físsil (
U) dos elemen
tos combustíveis começa a decrescer. Ao fim de um período de tempo, denominado
ciclo de operação, não é mais possível manter o reator crítico produzindo energia à
potência nominal. Os elementos combustíveis com baixas concentrações de
U são
substituídos por elementos combustíveis novos. Es tes, juntamente com os demais
elementos combustíveis remanescentes do ciclo anterior, comporão o núcleo do ciclo
subseqüente.
Chama-se otimização de recargas o processo de determinação do posicionamento
dos elementos combustíveis no reator, satisfazendo r estri ções técnicas e as impostas
pela própria geometria do núcleo, que torna melhor algum aspecto do funcionamento
da usina. Neste trabalho, a recarga será otimizada para m aximizar o comprimento
do ciclo 7 de Angra 1.
. O Núcleo de Angra 1 e suas Simetrias
O reator nuclear de A ngra 1 é um reator a água pressurizada (PWR) que utiliza
urânio enriquecido como combustível. Pastilhas de UO
são acondicionadas no inte
rior do revestimento, um tubo de Zircaloy- — uma liga de zircônio, estanho, ferro
e cromo — projetado para impedir o contato do UO
e dos produtos de fissão com
a água. Após a introdução das pastilhas, o revestimento é pressurizado com hélio e
selado, passando a constituir o que se denomina vareta combustível.
No núcleo do reator de Angra 1, há 28.435 varetas, distribuídas em 121 elementos
combustíveis. Cada um desses contém 235 varetas combustíveis, que são sustentadas
por uma estrutura composta de 20 tubos guias de barras de controle, 1 tubo de
instrumentação nuclear, 8 grades espaçadoras e 1 bocal em cada extremidade. A
figura . na próxima página mostra um esquema do núcleo de Angra 1.
Os eixos principais P
1
e P
2
dividem o núcleo em quatro quadrantes. Esses,
juntamente com os eixos diagonais D
1
e D
2
, dividem o núcleo em oito octantes. Po
de-se verificar que, geometricamente, o núcleo do reator é simétrico sob reflexões em
relação a cada um desses eixos. Conseqüentemente, a posição de cada elemento com
bustível localizado fora dos eixos possui outras 7 posições simétricas. Um elemento
combustível localizado em uma dessas posições é chamado de elemento de octeto. A
posição de cada elemento combustível localizado sobre apenas um dos eixos possui
outras 3 posições simétricas e cada um desses elementos combustíveis é chamado de
elemento de quarteto. Chama-se de elemento central o elemento combustível que
ocupa a posição sobre os 4 eixos simultaneamente. A figura . na página destaca
o elemento central, os elementos de quarteto e os elementos de octeto de um octante
de núcleo e fornece um sistema de coordenadas para localizá-los.
Figura .: Esquema do núcleo de Angra 1. Os quadrados representam os 121
elementos combustíveis. Em destaque se encontra 1/8 de núcleo, determinado
pelos eixos principais (P
1
, P
2
) e diagonais (D
1
, D
2
).
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(7,1)
(2,2)
(3,3)
(4,4)
(5,5)
(3,2)
(4,2)
(5,2)
(6,2)
(7,2)
(4,3)
(5,3)
(6,3)
(5,4)
(6,4)
Figura .: Elementos central, de quarteto e de octeto de um oitavo d e núcleo
e sistema de coordenadas para localizá-los.
Neste trabalho, o núcleo do reator será arranjado com simetria de 1/8 de núcleo,
significando que o arranjo de um octante será copiado nos demais, com elementos
combustíveis de mesmo tipo ocupando posições simétricas entre si.
. Metodologia
A exemplo dos trabalhos [, –] com os quais o FPBIL se rá comparado adi
ante, a concentração crítica de Boro C
B
(na etapa de queima do combustível nuclear
quando o Xenônio entra em equilíbrio) será o objeto de maximização do FPBIL, o
que corresponde [] a maximizar o comprimento do ciclo. Tod avia, existem restri
ções que precisam ser respeitadas.
A razão entre a densidade de potência linear máxima e a densidade de potência
linear média, no plano horizontal do núcleo do reator onde ocorre o pico local de
potência é denominada fator de pico de potência radial do núcleo (F
XY
). As especi
ficações técnicas das centrais nucleares restringem o valor máximo de F
XY
. No caso
de Angra 1, por exemplo, F
XY
deve ser, no máximo, 1,435.
Uma outra restrição é imposta pela geometria do núcleo. Com simetria de 1/8
de núcleo, um elemento de quarteto não pode trocar de lugar com um elemento
de octeto, simplesmente porque os números de posições simétricas de elementos de
quarteto e de octeto são diferentes. Da mesma forma, com simetria de 1/8 de núcleo,
o elemento central não pode mudar de lugar.
É evidente que um reator nuclear possui uma complexidade muito maior do que
poderia ser descrita neste texto, de modo que existem outras restrições que não serão
consideradas aqui — até porque os trabalhos com os quais o FPB IL será comparado
utilizam somente as mesmas duas restrições já citadas.
Neste trabalho, a restrição geométrica é resolvida automaticamente pela repre
sentação random keys de cada arranjo, enquanto a restrição técnica imposta a F
XY
é solucionada a partir da penalização da aptidão. Cada vetor binário é decodifi
cado em uma configuração de núcleo que é, então, processada pelo RECNOD, um
programa que simula um ciclo de operação de Angra 1.
.. RECNOD
A motivação para o desenvolvimento do RECNOD [] foi a busca por um código
de física de reatores bidimensional, a dois grupos de energia, mais rápido do que o
ANC [], de modo a reduzir os custos computacionais dos sistemas de otimização
de recargas.
O RE CNOD é um código nodal (de malha grossa) inspirado no trabalho de
Montagnini [], que utiliza uma variação do método de expansão de fluxo, criado
por Langenbuch [] no final dos anos . Segundo Montagnini, o seu código nodal
é capaz de produzir erros máximos na distribuição de potência inferiores a 1,5%.
Uma vez que o RECNOD não calcula o fator de pico de potência radial F
XY
,
este parâmetro foi substituído por p
rm
— a máxima potência média relativa dos
elementos combustíveis. Devido às discrepâncias entre as distribuições de potência
calculadas pelo RECNOD e pelo ANC, o valor 1,395 é adotado como o valor limiar
de p
rm
— devendo corresponder a 1,435 como limiar de F
XY
.
O RECNOD recebe como entrada a configuração de 1/8 de núcleo de uma forma
equivalente a mostrada na tabela .. O “Tipo” do elemento combustível é o número
Tabela .: Formato (equivalente) de entrad a das configurações de núcleo usado
pelo RECNOD.
P
i
P
i−1
Tipo
Central (1, 1) (1, 1) 4
Quartetos (2, 1) (3, 1) 4
(3, 1) (2, 2) 5
(4, 1) (7, 1) 2
(5, 1) (3, 3) 4
(6, 1) (6, 1) 2
(7, 1) (4, 4) 1
(2, 2) (5, 1) 4
(3, 3) (5, 5) 2
(4, 4) (2, 1) 6
(5, 5) (4, 1) 4
Octetos (3, 2) (5, 3) 6
(4, 2) (5, 2) 4
(5, 2) (5, 4) 5
(6, 2) (7, 2) 5
(7, 2) (4, 3) 6
(4, 3) (3, 2) 4
(5, 3) (6, 4) 2
(6, 3) (6, 2) 3
(5, 4) (6, 3) 3
(6, 4) (4, 2) 4
que o identifica na biblioteca de dados nucleares do RECNOD. P
i
é a posição que
o elemento combustível, que ocupava a posição P
i−1
no ciclo anterior, do tipo es
pecificado, ocupa no c iclo em análise (as posições são determinadas utilizando-se o
sistema de coordenadas da figura . na página ).
Como saída, o RECNOD informa a concentração crítica de Boro C
B
e as po
tências médias relativas dos elementos combustíveis — de onde se obtém p
rm
— a
partir dos quais a aptidão bruta é construída.
.. Representação das Configurações Nucleares
Conforme explicado na seção . na página , admitindo-se uma simetria de
1/8 de núcleo, o elemento central não muda de lugar e os elementos de quarte
tos e de octetos não podem trocar posições entre si. O resultado é um total de
!·!=.... possíveis configurações de núcleo.
Essas restrições são resolvidas com o simples uso da representação random keys.
Considere as duas -uplas ordenadas
Q =
(2, 1), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (2, 2), (3, 3), (4, 4), (5, 5)
; (.)
O =
(3, 2), (4, 2), (5, 2), (6, 2), (7, 2), (4, 3), (5, 3), (6, 3), (5, 4), (6, 4)
. (.)
Elas estabelecem uma ordem sobre as posições dos elementos de quarteto e de octeto.
Essa ordem será usada tanto pelo random keys como para o preenchimento do núcleo.
O exemplo a seguir ilustra o procedimento.
Q e O possuem 10 elementos, cada. O menor número de bits por dente de chave
que torna possível uma representação random keys sem empate é 4, valor adotado
neste exemplo.
Considere um indivíduo I , sorteado a partir de P , formado pela concatenação
de I |Q e I |O:
I = I |Q ⊕ I |O, (.)
com
I |Q = 1000001111010100111111100101010100101100; (.)
I |O = 1010101111110110111101100100110100001100 (.)
representando, respectivamente, os elementos de quarteto e de octeto. A tabela .
mostra como se constrói uma reordenação dos elementos de quarteto (sempre sem o
risco de repetições).
Tabela .: Random keys aplicado a I |Q, a primeira parte de I , responsável
pela representação dos elementos de quarteto.
I |Q 1000 0011 1101 0100 1111 1110 0101 0101 0010 1100
C 15 2 9 7 10 11 6 6 3 8
Q
(2, 1) (3, 1) (4, 1) (5, 1) (6, 1) (7, 1) (2, 2) (3, 3) (4, 4) (5, 5)
π
⊳
(C) 2 3 6 6 7 8 9 10 11 15
π
⊳
(Q)
(3, 1) (4, 4) (2, 2) (3, 3) (5, 1) (5, 5) (4, 1) (6, 1) (7, 1) (2, 1)
A chave C surge da decodificação de cada um dos seus 10 dentes de 4 bits
(utilizando o código de Gray, neste caso). A ordem dos dentes de C é, então,
relacionada com a de Q. Por fim, os elementos de Q são reordenados a partir de
π
⊳
, a permutação que arranja os dentes de C em ordem crescente. O mesmo é feito
para O, na tabela . na próxima página.
A partir de π
⊳
(Q) e π
⊳
(O), a entrada de dados do RECNOD é construída da
seguinte maneira: o elemento combustível que ocupava a posi ção correspondente
ao primeiro elemento de π
⊳
(Q) (o elemento combustível do tipo 4 que ocupava a
posição (3, 1), ver tabela . na página ) passa a ocupar a posição correspondente
ao primeiro elemento de Q (a posição (2, 1)). Esse primeiro passo gera a linha
mostrada na tabela . na próxima página.
O mesmo ocorre para um elemento de octeto. O elemento combustível que
Tabela .: Random keys aplicado a I |O, a segunda parte de I , responsável
pela representação dos elementos de octeto.
I |O 1010 1011 1111 0110 1111 0110 0100 1101 0000 1100
C 12 13 10 4 10 4 7 9 0 8
O
(3, 2) (4, 2) (5, 2) (6, 2) (7, 2) (4, 3) (5, 3) (6, 3) (5, 4) (6, 4)
π
⊳
(C) 0 4 4 7 8 9 10 10 12 13
π
⊳
(O)
(5, 4) (6, 2) (4, 3) (5, 3) (6, 4) (6, 3) (5, 2) (7, 2) (3, 2) (4, 2)
Tabela .: Uma linha (de quarteto) da entrada de dados do RECNOD.
P
i
P
i−1
Tipo
(2, 1) (3, 1) 4
ocupava a posição correspondente ao primeiro elemento de π
⊳
(O) (o elemento com
bustível do tipo 5 que ocupava a posição (5, 4), ver tabela . na página ) passa a
ocupar a posição correspondente ao primeiro elemento de O (a posição (3, 2)). Esse
passo gera a linha da tabela ..
Tabela .: Uma linha (de octeto) da entrada de dados do RECNOD.
P
i
P
i−1
Tipo
(3, 2) (5, 4) 5
Como o random keys é aplicado separadamente em I |Q e I |O, nunca um
elemento de quarteto será trocado por um de octeto. A restrição geométrica é
garantida.
A ordem estabelecida em Q e O não precisa ser a das equações (.) e (.) e
uma ordem diferente pode afetar o desempenho do FPBIL (ou de qualquer outro
algoritmo de busca). O motivo é que as escolhas de Q e O determinam o quanto
uma configuração nuclear se torna diferente como conseqüência da alteração de uns
Tabela .: Nova entrada das configurações de núcleo para o RECNOD.
P
i
P
i−1
Tipo
Central (1, 1) (1, 1) 4
Quartetos (2, 1) (3, 1) 4
(3, 1) (4, 4) 1
(4, 1) (2, 2) 5
(5, 1) (3, 3) 4
(6, 1) (5, 1) 4
(7, 1) (5, 5) 2
(2, 2) (4, 1) 4
(3, 3) (6, 1) 2
(4, 4) (7, 1) 2
(5, 5) (2, 1) 6
Octetos (3, 2) (5, 4) 5
(4, 2) (6, 2) 3
(5, 2) (4, 3) 6
(6, 2) (5, 3) 6
(7, 2) (6, 4) 2
(4, 3) (6, 3) 3
(5, 3) (5, 2) 4
(6, 3) (7, 2) 5
(5, 4) (3, 2) 4
(6, 4) (4, 2) 4
poucos bits em I . Dependendo das escolhas de Q ou O, um elemento combustível
que está “funcionando” bem próximo ao núcleo pode ser deslocado para a periferia
pela modificação de um único bit. Também existe a possibilidade de grupamentos
de elementos combustíveis, que “funcionam” bem quando juntos, serem desfeitos,
também, por uma pequena modificação em I .
Dessa forma, a ordem escolhida em Q e O tem o poder de tornar o espaço de
busca B mais (ou menos) suave. A busca de ordenações em Q e O que torna B
o mais suave possível é um problema relacionado muito interessante e muito mais
complexo do que aparenta. Neste trabalho, ess e problema não será considerado e Q
e O serão os mesmos das equações (.) e (.).
. Resultados
O RECNOD leva um tempo da ordem de 1 segundo para simular a queima
do combustível nuclear a partir de cada configuração de núcleo. Mesmo parecendo
pouco, com centenas de milhares de simulações (uma para cada avaliação da apti
dão), a execução do FPBIL pode durar por vários dias. Por conseqüência, apenas
uns poucos testes puderam ser realizados. A seguir são descritos três dest es testes
que se destacaram.
No primeiro teste, foram utilizados 6 bits por dente de chave na representação
random keys, resultando em indivíduos com 120 bits. A aptidão bruta utilizada foi
A
b
(I ) =
p
rm
(I ) se p
rm
(I ) > 1,395;
1
C
B
(I )
se p
rm
(I ) ≤ 1,395,
(.)
a mesma utilizada em []. Pode-se perceber que sempre que p
rm
(I ) > 1,395,
existe uma penalização, já que os valores de C
B
(I ) estão em torno de 1.000. Como
o objetivo é minimizar A
b
(I ), a aptidão padrão será igual à bruta,
A
p
(I ) = A
b
(I ). (.)
A evolução da aptidão bruta é mostrada na figura .. Como pode ser verificado,
Figura .: Evolução de A
b
(I ) para o teste 1.
a primeira configuração de núcleo não penalizada surgiu um pouco depois de 2.000
avaliações da aptidão e a melhor solução surge um pouco antes de 200.000 avaliações.
A figura figura . na próxima página mostra as melhores soluções ao final de cada
geração. A linha tracejada representa o limiar de 1.395. Todas as soluções acima
dessa linha são penalizadas. Nota-se que são poucas as soluções que se destacam.
A tabela . na página seguinte lista as soluções (não dominadas) não penalizadas
com C
B
(I ) ≥ 1.300, com destaque para a melhor solução.
Como pode ser verificado na equação (.) na página precedente, a penalização
funciona somente na direção de p
rm
(I ) e é muito acentuada — um salto da ordem
de 1.000.
Figura .: Melhores soluções ao final de cada geração do teste 1.
Tabela .: Soluções não penalizadas do teste 1 com C
B
(I ) ≥ 1.300.
Geração C
B
(ppm) p
rm
47 1307 1,373
145 1428 1,392
850 1328 1,391
O segundo teste utilizou uma aptidão bruta diferente:
A
b
(I ) =
C
B
(I ) se p
rm
(I ) ≤ 1,395;
C
B
(I )
2
e
−
p
rm
(I )−p
lim
ρ
se p
rm
(I ) > 1,395,
(.)
com p
lim
= 1,395 e ρ = p
lim
/2. Com isso, a descontinuidade entre a região penalizada
e a não penalizada é sempre C
B
(I )/2 e a penalização se dá, também, no sentido de
aumentar o valor de C
B
(I ). A aptidão padrão utilizada foi
A
p
(I ) = 15.000 − A
b
(I ). (.)
Dessa vez, foram utilizados 4 bits por dente de chave, resultando em indivíduos
com 80 bits. A evolução da aptidão bruta é ilustrada na figura . e a figura . na
Figura .: Evolução de A
b
(I ) para o teste 2.
próxima página mostra as melhores soluções ao final de cada geração. A distribuição
das soluções é visivelmente diferente da do teste anterior. A tabela . na página
lista as soluções (não dominadas) não penalizadas com C
B
(I ) ≥ 1.300, onde a
Figura .: Melhores soluções ao final de cada geração do teste 2.
melhor solução é destacada.
No terceiro e último teste apresentado neste trabalho, encontrou-se a melhor
solução com p
rm
(I ) ≤ 1,395. Para tanto, utilizou-se a mesma aptidão e o mesmo
número de bits por dente de chave do teste anterior. A evolução da aptidão bruta
é ilustrada na figura . e a figura . mostra as melhores soluções ao final de cada
geração.
Observa-se que nestes dois últimos testes, em particular, a aptidão bruta apre
senta uma tendência a continuar crescendo, significando que possíveis melhores so
luções podem ainda ser alcançadas com o uso do FPBIL. A tabela . na página
apresenta as soluções (não dominadas) não penalizadas com C
B
(I ) ≥ 1.300, com
destaque para a melhor solução.
A título de curiosidade, a melhor configuração de núcleo encontrada pelo FPBIL
é mostrada na figura ., onde os números correspondem aos tipos da tabela ..
Tabela .: Soluções não penalizadas do teste 2 com C
B
(I ) ≥ 1.300.
Geração C
B
(ppm) p
rm
198 1401 1,391
202 1406 1,383
203 1319 1,380
210 1303 1,394
234 1379 1,392
805 1454 1,370
822 1354 1,330
963 1416 1,390
968 1415 1,389
Figura .: Evolução de A
b
(I ) para o teste 3.
Figura .: Melhores soluções ao final de cada geração do teste 3.
Tabela .: Soluções não penalizadas do teste 3 com C
B
(I ) ≥ 1.300.
Geração C
B
(ppm) p
rm
90 1325 1,348
231 1336 1,376
249 1406 1,386
272 1364 1,395
285 1356 1,325
354 1333 1,393
686 1374 1,380
745 1329 1,374
760 1326 1,356
763 1310 1,388
798 1316 1,373
858 1554 1,381
987 1302 1,384
1078 1307 1,378
4
4
4
2
2
5
6
4
2
1
4
5
2
3
6
5
3
6
4
4
4
Figura .: A melhor configuração de núcleo encontrada pelo FPBIL.
Entretanto, as sutilezas de tal configuração podem ser melhor percebidas somente
quando o núcleo é mostrado por inteiro, como na figura . na página seguinte.
Uma característica clara desta configuração é que os elementos combustíveis dos
tipos 4, 5 e 6 são posicionados no interior e na periferia do núcleo, enquanto que os
de tipos 1, 2 e 3 preenchem a região intermediária.
. Comparação com Outros Trabalhos
O problema da recarga nuclear, mais especificamente a maximi zação do ciclo 7
de Angra 1, foi alvo de diferentes técnicas de otimização, tornando-se um benchmark
(a nível nacional). Esta seção destina-se a comparar o desempenho do FPBIL, frente
a essas outras técnicas. A tabela . mostra os dados e os cor respondentes valores
Tabela .: Comparaçã o do desempenho de diferentes técnicas aplicadas à
maximização do ciclo 7 de Angra 1.
Ano Autor C
B
(ppm) p
rm
a
Técnica Heur. Avaliações
– – 955 1,345 Manual [] – –
Chapot [] 1026 1,390 AG não 4.000
Machado, L. [] 1297 1,384 ANT-Q sim 200
Machado, M. [] 1242 1,361 PBIL_N não 6.000
Machado, M. [] 1305 1,349 PBIL_MO não 10.000
Lima [] 1424 1,386 RCCA sim 329.000
Presente Trabalho 1554 1,381 FPBIL não 430.364
a
F
XY
, para a otimização manual.
de C
B
e p
rm
são plotados na figura . na página seguinte.
Esses resultados são os melhores encontrados com as respectivas técnicas pelos
seus autores, de modo que as escolhas das funções objetivo e dos eventuais parâme
tros correspondentes às diferentes técnicas não tem necessariamente relações entre
si.
Uma característica interessante da solução encontrada pelo FPBIL é que, ape
sar do valor elevado de C
B
, p
rm
encontra-se razoavelmente abaixo de 1,395. Já a
solução encontrada pelo PBIL_MO (PBIL Multi_Objetivo) é a que encontra, como
esperado, um valor relativamente alto de C
B
ao m esmo tempo em que mantem p
rm
bem mais baixo. As soluções encontradas pelo PB IL_MO são na realidade frentes
de Pareto []. O resultado apresentado correspondendo a essa técnica é apenas o
ponto da frente de Pareto abaixo da linha p
rm
= 1,395 com maior valor de C
B
.
Figura .: Melhor resultado das diferentes técnicas.
Outra informação relevante com relação a maximização do ciclo 7 de Angra 1 é
a quantidade de Dias Efetivos à Plena Potência,
1 DEPP = 625 MWe · 24 h = 15.000 MWeh, (.)
que é a energia produzida em 24h com o reator funcionando à potência nomi
nal, 625MWe. Angra 1 consome aproximadamente 4ppm de boro solúvel a cada
DEPP [] e, portanto, é possível computar durante quantos DEPP Angra 1 conse
gue produzir energia para cada configuração nuclear diferente. Nesta mesma linha,
também é possível calcular o valor arrecadado com a venda de energia de um DEPP,
bastando, para tanto, multiplicar 1DEEP por
T = R$ 98,64/MWeh, (.)
que é a tarifa estabelecida pela ANEEL para o ano de []. Tem-se, portanto
que
1 DEPP → T · DEPP = R$ 1.479.600, 00, (.)
ou seja, cada dia, a mais, de geração de energia que uma configuração de núcleo
atinge, corresponde a um ganho de R$ 1.479.600, 00. A tabela . apresenta o
número de DEPP, a mais, em relação a otimização manual e a rece ita, a mais,
correspondente.
Tabela .: DEEP e Receita, a mais, em rela ção a otimização manual.
Técnica DEPP − DEPP
Manual
T · (DEPP − DEPP
Manual
) (em R$)
Manual 0,00 0,00
AG 17,75 26.262.900,00
ANT-Q 85,50 126.505.800,00
PBIL_N 71,75 106.161.300,00
PBIL_MO 87,50 129.465.000,00
RCCA 117,25 173.483.100,00
FPBIL 149,75 221.570.100,00
A solução encontrada pelo FPBIL corresponde a 149,75 DEEP a mais, compa
rando com a otimização manual — realizada por especialistas — o que representa
cerca de 5 meses à plena potência. Comparando com o segundo melhor resultado,
o FPBIL garante 32,5 DEEP a mais, uma economia de R$ 48.087.000,00. Se a com
paração for feita com o PBIL_MO (PBIL Multi_Objetivo), o segundo melhor re
sultado sem uso de heurísticas, o FPBIL obtém 62,25 DEEP a mais, economizando
R$ 92.105.100,00.
Conclusão
ode-se afirmar, em conclusão a este trabalho, que o FPBIL é um al
goritmo evolucionário, competitivo com as melhores técnicas atuais
de otimização, compacto, relativamente modesto no uso de recursos
computacionais — especialmente memória —, bem fundamentado, efi
ciente, robusto, auto-adaptável, simples e sem parâmetros.
O bom desempenho do FPBIL em problemas combinatórios ficou evidente com o
problema da recarga nuclear, avaliado e discutido no capítulo . Além disso, os testes
realizados no capítulo , mostram que o FPBIL também se destaca em problemas
numéricos e deceptivos.
Com relação ao algoritmo em si, o FPBIL é conceitualmente simples por ser
intuitivo e não requer conhecimento muito sofisticado; é compacto no sentido de
que pode ser programado com poucas linhas de código; e utiliza pouca memória,
uma vez que não há necessidade de armazenar os indivíduos de uma população em
alguma estrutura de dados.
A forma radicalmente diferente da mutação observada no FPBIL é fundamen
tada na distribuição de probabilidades inerente ao próprio vetor de probabilidades,
sendo, este último, atualizado com a utilização de toda a informação disponível em
cada geração. Tais modificações possibilitam ao FPBIL adquirir características auto
-ajustáveis — como o mecanismo de população de tamanho variável — que tornam
o algoritmo mais eficiente e mais robusto. Eficiente no sentido de que encontra solu
ções em menos tempo; robusto, significando que possui mais recursos para escapar
de ótimos locais.
Com relação ao fato de ser o FPBIL livre de parâmetros, é importante enfatizar
que se pode optar por abrir mão das reinicializações e ter P
0
como único parâmetro.
Esta pode ser uma alternativa plausível, mas sujeita a eventuais riscos. Por exemplo,
um problema pode ser mais fácil do que aparenta, causando desperdício de tempo;
ou mais difícil, resultando no fracasso da busca. A questão é que o processo de
ajuste de qualquer parâmetro implica em um tempo precioso de processamento que,
somado ao tempo de execução propriamente dito, conduz à utilização de mais tempo
que quaisquer tentativas do FPBIL, tal como proposto.
Com relação especificamente ao problema da recarga nuclear, existem questões
ainda abertas que, quando solucionadas, devem possibilitar uma busca mais pro
funda no correspondente espaço de busca. Uma dessas questões já foi considerada
no capítulo e diz respeito à determinação da ordem em que os elementos de quar
teto e de octeto devem ser inseridos no núcleo do reator, a partir da configuração
estabelecida pela representação random keys, de modo a suavizar ao máximo o es
paço de busca.
Uma outra questão, t ambém tratada no capítulo , está relacionada diretamente
à representação random keys, mais especificamente no que se refere ao número ideal
de bits por dente de chave. Deve haver um número ótimo, já que um número pe
queno de bits por dente de chave resulta em grande número de empates, enquanto
que um número grande desses bits destrói uma significativa parte da bijetividade
entre S
B
e
ˇ
H
n
, criando uma grande região de planície. Ambos os extremos mencio
nados dificultam a busca. Para agravar ainda mais a determinação do valor ideal do
número de bits por dente de chave, vale lembrar que diferentes valores dessa gran
deza produzem H
n
de tamanhos diferentes, o que também influencia na dificuldade
da busca por uma solução do problema.
Finalmente, uma outra questão importante a ser considerada é avaliar até que
ponto a utilização do có digo de Gray é mais vantajosa. Certamente os resultados
obtidos com o código de Gray são superiores, quando comparados aos obtidos com a
representação binária convencional. Todavia, intuitivamente, a representação biná
ria convencional deveria ser a melhor, uma vez que essa faz uma distinção muito clara
entre números pequenos e grandes — os grandes começam com 1’s e os pequenos,
com 0’s.
Uma possibilidade é que a representação binária convencional faça diferença no
início do algoritmo, quando os primeiros e últimos elementos podem ser separados
rapidamente; enquanto que o código de Gray faça diferença no final do algoritmo,
possibilitando um ajuste fino na or dem dos elementos, com a alteração de poucos
bits. Isto sugere que o processo de busca pode ser aperfeiçoado utilizando-se simul
taneamente os dois tipos de codificação.
Com a proposição do FPBIL, espera-se ter contribuído para questões teóricas e
práticas pertinentes, apresentando melhorias técnicas viáveis com uma contrapartida
econômica considerável, tanto em r elação a seu custo quanto a seu benefício.
Existem, entretanto, avanços que podem, ainda, ser incorporados ao FPBIL.
Depois de escapar de ótimos locais, o FPBIL costuma se aproximar mais lentamente
do ótimo global que outros algoritmos — como, por exemplo, o PBIL original.
Considerando o processo como um todo, o FPBIL leva vantagem, mas talvez seja
possível combinar o FPBIL com algum algoritmo de busca rápida, resultando em
um algoritmo ainda mais eficiente.
Outras melhorias, além das já citadas, podem surgir construindo-se um FPBIL
multiobjetivo — adaptando-se as técnicas de [] — ou, até mesmo, um FPBIL
paralelo — com base nas técnicas de []. Pode-se, ainda, tentar incorporar algum
tipo de heurística ao FPBIL — talvez alguma descrita em [], para o problema
específico da recarga nuclear. Trabalhos nessas direções provam que, com o emprego
dessas técnicas, costuma-se gerar soluções melhores.
Há ainda muito o que se fazer e pesquisar no que se refere aos sistemas de oti
mização. Devido a restrições de tempo e escopo, esse trabalho apenas propicia uma
breve discussão no campo dos algoritmos não parametrizados e reforça a necessidade
e a validade de se continuar estudando o assunto.
Referências
[] GOLDBERG, D. E. GENETIC ALGORITHMS in Search, Optimization and
Machine Learning. Reading, MA: Addison-Wesley, .
[] HOLLAND, J. H . Adaptation in Natural and Artificial Systems. Segunda Edição.
Massachusetts: MIT Press, .
[] DARWIN, C. R. On The Origin of Species by Means of Natural Selection. Lon
don: John Murray, .
[] BALUJA, S. Population-Based Incremental Learning: A Method for Inte
grating Genetic Search Based Function Optimization and Competitive Learn
ing. Pittsburgh, PA, . Disponível em: <http://citeseer.ist.psu.edu/
balujapopulation.html>.
[] BALUJA, S. An Empirical Comparison of Seven Iterative and Evolution
ary Function Optimization Heuristics. [S.l.], . Disponível em: <http://
citeseer.ist.psu.edu/balujaempirical.html>.
[] MACHADO, M. D. Um Novo Algoritmo Evolucionário com Aprendizado LVQ
para a Otimização de Problemas Combinatórios como a Recarga de Reatores Nu
cleares. Dissertação (Mestrado) — COPPE/UFRJ, Rio de Janeiro, .
[] BALUJA, S.; CARUANA, R. Removing the Genetics from the Standard Genetic
Algorithm. In: PRIEDITIS, A.; RUSSEL, S. (Ed.). The Int. Conf. on Machine
Learning . San Mateo, CA: Morgan Kaufmann Publishers, . p. –.
Disponível em: <http://citeseer.ist.psu.edu/balujaremoving.html>.
[] BALUJA, S.; DAVIES, S. Fast Probabilistic Modeling for Combinatorial Opti
mization. In: AAAI/IAAI. [s.n.], . p. –. Disponível em: <citeseer.
ist.psu.edu/balujafast.html>.
[] MACHADO, L.; SCHIRRU, R. The Ant-Q algorithm applied to the nuclear
reload problem. Annals of Nuclear Energy, v. , n. , p. –, .
[] KENNEDY, J.; EBERHART, R. Particle Swarm Optimization. In: Proceedings
of the IEEE International Conference on Neural Networks. [S.l.: s.n.], . p.
–.
[] BANZHAF, W. et al. Genetic Programming - An Introduction. San Francisco:
Morgan Kaufmamm Publishers, Inc., .
[] KOZA, J. R. Genetic Programming - On the Programming of Computers by
Means of Natural Selection. Cambridge: MIT Press, .
[] JANIKOW, C. Z.; WEESE, S. W. de. CGP lil-gp .;. User’s Manual. [S.l.].
[] CALDAS, G. H. F.; SCHIRRU, R. Híbrido de programação genética com vari
ante de PBIL. In: International Nuclear Atlantic Conference - INAC .
[S.l.: s.n.], .
[] JUELS, A.; BALUJA, S.; SINCLAIR, A. The Equilibrium Genetic Algorithm
and the Role of Crossover. Disponível em: <http://citeseer.ist.psu.edu/
juelsequilibrium.html>.
[] KNUTH, D. E. The Art of C omputer Programming. Pre-fascicle A. Stanford:
Addison-Wesley, .
[] GILL, P. E.; MURRAY, W.; WRIGHT, M. H. Practical Optimization. San
Diego: Academic Press, .
[] DEVLIN, K. Os Problemas do Milênio. Rio de Janeiro: Record, .
[] LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria da Computação.
Segunda edição. Porto Alegre: Bookman, .
[] TSPLIB - A Library of Traveling Salesman Problem And Related Problem
Instances. Disponível em: <http://nhse.cs.rice.edu/softlib/catalog/
tsplib/tsp/>.
[] BEAN, J. C. “Genetic Algorithms and Random Keys for Sequencing and Opti
mization”. ORSA Journal on Computing, v. , n. , .
[] SCHIRRU, R.; PEREIRA, C. M. N. A. [S.l.].
[] LIMA, A. M. M. de. Recarga de Reatores Nucleares Utilizando Redes Conectivas
de Colônias Artificiais. Tese (Doutorado) — COPPE/UFRJ, Rio de Janeiro, .
[] CHAPOT, J. L. C. Otimização Automática de Recargas de Reatores a Água
Pressurizada Utilizando Algoritmos Genéticos. Tese (Doutorado) — COPPE/
UFRJ, Rio de Janeiro, .
[] MACHADO, M. D. Algoritmo Evolucionário PBIL Multi_Objetivo Aplicado ao
Problema da Recarga de Reatores Nucleares. Tese (Doutorado) — COPPE/UFRJ,
Rio de Janeiro, .
[] LIU, Y. S. et al. ANC: A Westinghouse Advanced Nodal Computer Code. [S.l.],
.
[] MONTAGNINI, B. et al. “A well-Balanced Coarse Mesh Flux Expansion
Method”. Annals of Nuclear Energy, v. , n. , p. –, .
[] LANGENBUCH, S.; MAURER, W.; WERN ER, W. “Coarse Mesh Flux Expan
sion Method for Analysis of Space-Time Effects in Large Water Reactor Cores”.
Nuclear Science and Engineering, n. , p. –, .
[] Disponível em: <http://www.aneel.gov.br>.
Índice Remissivo
#,
α,
Cuidado no ajuste de,
A,
A
a
,
A
b
,
A
i
,
A,
P
A,
A
p
,
β,
Cuidado no ajuste de,
B,
c,
Flutuação em,
c
′
,
C
B
,
∆ c
G
,
c
G
,
d
I
,
d,
Ótimo,
d
c
,
∂P
G
∂G
,
δ,
δ
r
,
D,
d
I
k
,
D
M
,
F
XY
,
G,
γ,
H
n
,
ˇ
H
n
,
ˇ
H
Ordem de,
I
k
,
I ,
I
+
,
I
−
,
I
†
,
I [k ],
k,
M
n
S
B
,
O,
p
k
,
P,
P
0
,
P
c
,
p
rm
,
P ,
P
0
,
P (I ),
P [k],
S
B
,
ϑ(P
G
),
V
H
n
,
ξ, ,
Algoritmos
Evolucionários,
Genéticos, ,
ANC,
ANT-Q,
Aptidão,
Ajustada,
Propriedades,
Bruta,
padrão,
Procedimento para construção da,
Banana, o problema, –
Código
de Gray, –
RECNOD,
Central
Elemento,
Chave,
Ciclo de operação,
Concentração crítica de Boro,
Dente de chave,
DEPP,
Desvio absoluto médio,
Diagonais
Eixos,
Dias Efetivos à Plena Potência,
Eixos
Diagonais,
Principais,
Elemento
de octeto,
de quarteto,
Central,
Elementos combustíveis,
Espaço de Busca,
Estrutura do PBIL,
Evolucionários, algoritmos,
Fator de pico de potência radial do nú
cleo,
Flutuação em c,
FPBIL, , –
Atualização do vetor de probabili
dades, ,
Tamanho da população no,
Velocidade no, ,
FPBIL
∗
,
Função
Aptidão,
de Rosenbrock,
Genéticos
Algoritmos, ,
Geração,
Gray
Código de, –
Hipercubo,
Hiperplanos,
Indivíduo
Ótimo,
Mais apto,
Menos apto,
Indivíduos,
Máxima potência média relativa,
Motivação para o trabalho,
Mutação,
Funçao da,
No FPBIL,
Núcleo de Angra 1
Simetrias,
Octantes,
Octeto
Elemento de,
Ordem de
ˇ
H,
PBIL, , –
Atualização do vetor de probabili
dades,
Estrutura,
Mutação,
Original,
Terminologia,
Velocidade no,
PBIL
∗
,
PCV Rykel, –
População,
Escolha do tamanho da,
Potência média relativa, Máxima,
Principais
Eixos,
Problema
Banana, –
da recarga nuclear, –
PCV Rykel, –
Quatro picos, –
PSO,
Quadrantes,
Quarteto
Elemento de,
Quatro picos, –
Random keys, –
Chave,
Dente de chave,
Recarga nuclear
Problema da, –
RECNOD,
Representação random keys, –
Chave,
Dente de chave,
Rosenbrock
Função de,
Simetrias
do núcleo de Angra 1,
Terminologia do PBIL,
Vareta combustível,
Velocidade,
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
