ads:
André Vargas Abs da Cruz
Algoritmos Evolutivos com Inspiração Quântica
para Problemas com Representação Numérica
Tese de Doutorado
Tese apresentada ao Programa de Pós–graduação em Sis-
temas de Apoio à Decisão do Departamento de Engenharia
Elétrica da PUC-Rio como requisito parcial para obtenção Do
título de Doutor em Sistemas de Apoio à Decisão
Orientadores: Prof. Marco Aurélio C. Pacheco
Prof. Marley M. B. R. Vellasco
Rio de Janeiro
Março de 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
André Vargas Abs da Cruz
Algoritmos Evolutivos com Inspiração Quântica
para Problemas com Representação Numérica
Tese apresentada ao Programa de Pós–graduação em Sis-
temas de Apoio à Decisão do Departamento de Engenharia
Elétrica do Centro Técnico Científico da PUC-Rio como req-
uisito parcial para obtenção Do título de Doutor em Sistemas
de Apoio à Decisão. Aprovada pela Comissão Examinadora
abaixo assinada.
Prof. Marco Aurélio C. Pacheco
Orientador
Departamento de Engenharia Elétrica — PUC-Rio
Prof. Marley M. B. R. Vellasco
Orientador
Departamento de Engenharia Elétrica — PUC-Rio
Prof. Carlos Roberto Hall Barbosa
Pontifícia Universidade Católica do Rio de Janeiro
Prof. Karla Tereza Figueiredo Leite
Universidade Estadual do Rio de Janeiro
Prof. Leandro dos Santos Coelho
Pontifícia Universidade Católica do Paraná
Prof. Renato Portugal
Laboratório Nacional de Computação Científica
Prof. Valmir C. Barbosa
Universidade Federal do Rio de Janeiro
Prof. José Eugênio Leal
Coordenador Setorial do Centro Técnico Científico —
PUC-Rio
Rio de Janeiro, 05 de Março de 2007
ads:
Todos os direitos reservados. É proibida a reprodução total ou
parcial do trabalho sem autorização da universidade, do autor e
do orientador.
André Vargas Abs da Cruz
Graduou-se em Engenharia de Computação na Pontifícia Univer-
sidade Católica do Rio de Janeiro. Mestrado na área de Sistemas
de Apoio à Decisão no Departamento de Engenharia Elétrica da
Pontifícia Universidade Católica do Rio de Janeiro.
Ficha Catalográfica
Abs da Cruz, André V.
Algoritmos Evolutivos com Inspiração Quântica para
Problemas com Representação Numérica / André Vargas
Abs da Cruz; orientadores: Marco Aurélio C. Pacheco; Mar-
ley M. B. R. Vellasco. — Rio de Janeiro : PUC-Rio, Depar-
tamento de Engenharia Elétrica, 2007.
v., 109 f: il. ; 29,7 cm
1. Tese (doutorado) - Pontifícia Universidade Católica
do Rio de Janeiro, Departamento de Engenharia Elétrica.
Inclui referências bibliográficas.
1. Engenharia Elétrica – Tese. 2. Computação Evolu-
tiva. 3. Algoritmos Genéticos. 4. Algoritmos Culturais. 5.
Algoritmos com Inspiração Quântica. I. Pontifícia Universi-
dade Católica do Rio de Janeiro. Departamento de Enge-
nharia Elétrica. II. Título.
CDD: 510
À minha esposa Luciana
Agradecimentos
Ao CNPq e à PUC-Rio pelos auxílios concedidos, sem os quais este trabalho
não poderia ter sido realizado.
Aos meus orientadores Prof. Dr. Marco Aurélio C. Pacheco e Prof
a
. Dr
a
.
Marley M. B. R. Vellasco, pelo estímulo e parceria na realização deste trabalho.
Aos meus colegas e amigos da PUC-Rio e do ICA.
Aos amigos Dilza Sczwarcman, Douglas Mota Dias, Omar Paranaíba e Wil-
son Freitas pela paciência ao ouvir longas conversas sobre física quântica e com-
putação evolutiva.
Aos meus familiares e amigos que de uma forma ou de outra me estimularam
e ajudaram.
Aos meus pais, pela educação, os exemplos e o apoio que me foram dados ao
longo de toda a minha vida.
À minha esposa Luciana, pelo amor, carinho, generosidade e compreensão.
Resumo
Abs da Cruz, André V.; ; . Algoritmos Evolutivos com Inspiração
Quântica para Problemas com Representação Numérica. Rio de
Janeiro, 2007. 109p. Tese de Doutorado — Departamento de Engen-
haria Elétrica, Pontifícia Universidade Católica do Rio de Janeiro.
Desde que foram propostos como método de otimização, os algoritmos evoluti-
vos têm sido usados com sucesso para resolver problemas complexos nas mais
diversas áreas como, por exemplo, o projeto automático de circuitos e equipa-
mentos, planejamento de tarefas, engenharia de software e mineração de dados,
entre tantos outros. Este sucesso se deve, entre outras coisas, ao fato desta classe
de algoritmos não necessitar de formulações matemáticas rigorosas a respeito do
problema que se deseja otimizar, além de oferecer um alto grau de paralelismo no
processo de busca. No entanto, alguns problemas são computacionalmente cus-
tosos no que diz respeito à avaliação das soluções durante o processo de busca,
tornando a otimização por algoritmos evolutivos um processo lento para situa-
ções onde se deseja uma resposta rápida do algoritmo (como por exemplo, pro-
blemas de otimização online). Diversas maneiras de se contornar este problema,
através da aceleração da convergência para boas soluções, foram propostas, en-
tre as quais destacam-se os Algoritmos Culturais e os Algoritmos Co-Evolutivos.
No entanto, estes algoritmos ainda têm a necessidade de avaliar muitas soluções
a cada etapa do processo de otimização. Em problemas onde esta avaliação é
computacionalmente custosa, a otimização pode levar um tempo proibitivo para
alcançar soluções ótimas. Este trabalho propõe um novoalgoritmo evolutivopara
problemas de otimização numérica (Algoritmo Evolutivo com Inspiração Quân-
tica usando Representação Real – AEIQ–), inspirado no conceito de múltiplos
universos da física quântica, que permite realizar o processo de otimização com
um menor número de avaliações de soluções. O trabalho apresenta a modelagem
deste algoritmo para a solução de problemas benchmark de otimização numé-
rica, assim como no treinamento de redes neurais recorrentes em problemas de
aprendizado supervisionado de séries temporais e em aprendizado por reforço
em tarefas de controle. Os resultados obtidos demostram a eficiência desse algo-
ritmo na solução destes tipos de problemas.
Palavras–chave
Computação Evolutiva. Algoritmos Genéticos. Algoritmos Culturais.
Algoritmos com Inspiração Quântica.
Abstract
Abs da Cruz, André V.; ; . Quantum-Inspired Evolutionary Algo-
rithms for Problems based on Numerical Representation. Rio de
Janeiro, 2007. 109p. PhD Thesis — Department of Engenharia Elétrica,
Pontifícia Universidade Católica do Rio de Janeiro.
Since they were proposed as an optimization method, the evolutionary algo-
rithms havebeen successfully used for solving complexproblems in severalareas
such as, for example, the automatic design of electronic circuits and equipments,
task planning and scheduling, software engineering and data mining, among
many others. This success is due, among many other things, to the fact that
this class of algorithms does not need rigorous mathematical formulations re-
garding the problem to be optimized, and also because it offers a high degree of
parallelism in the search process. However, some problems are computationally
intensive when it concerns the evaluation of solutions during the search process,
making the optimization by evolutionary algorithms a slow process for situations
where a quick response from the algorithm is desired (for instance, in online op-
timization problems). Several ways to overcome this problem, by speeding up
convergence time, were proposed, including Cultural Algorithms and Coevo-
lutionary Algorithms. However, these algorithms still have the need to evalu-
ate many solutions on each stip of the optimization process. In problems where
this evaluation is computationally expensive, the optimization might take a pro-
hibitive time to reach optimal solutions. This work proposes a new evolutionary
algorithm for numerical optimization problems (Quantum-Inspired Evolution-
ary Algorithm for Problems based on Numerical Representation – QIEA–),
inspired in the concept of quantum superposition, which allows the optimization
process to be carried on with a smaller number of evaluations. The work presents
the modelling for this algorithm for solving benchmark numerical optimization
problems, and for training recurrent neural networks in supervised learning and
reinforcement learning. The results show the good performance of this algorithm
in solving these kinds of problems.
Keywords
Evolutionary Computation. Genetic Algorithms. Cultural Algorithms.
Quantum–Inspired Computing.
Sumário
1 Introdução 13
1.1 Motivação 13
1.2 Objetivos 15
1.3 Contribuições 15
1.4 Descrição do Trabalho 16
1.5 Organização do Trabalho 18
2 Fundamentos 19
2.1 Mecânica Quântica 19
2.2 Um Exemplo de um Sistema Físico Quântico – O Modelo da Partí-
cula na Caixa 24
2.3 Computação Quântica 26
2.4 Algoritmos com Inspiração Quântica 28
2.5 Algoritmos Evolutivos com Inspiração Quântica – Representação
Binária 31
2.6 Algoritmos Culturais 34
2.7 Neuro–Evolução 37
3 Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R 39
3.1 O Modelo de Algoritmo Evolutivo com Inspiração Quântica e Repre-
sentação Real 39
3.2 Usando o Modelo da Partícula na Caixa com o AEIQ-R 51
3.3 Analogia entre o AEIQ-R e os Algoritmos Culturais 52
3.4 Modelo Neuro-Evolutivo – Aprendizado Supervisionado 54
3.5 Modelo Neuro-Evolutivo – Aprendizado por Reforço 58
4 Estudos de Caso 60
4.1 Otimização de Funções 60
4.2 Neuro-Evolução 72
5 Conclusões e Trabalhos Futuros 82
5.1 Aprendizado Online 84
5.2 Sistemas Multi-Agentes 85
Referências Bibliográficas 87
Lista de figuras
2.1 Diagrama do sistema físico hipotético da “partícula na caixa” 24
2.2 Gráfico mostrando os níveis de energia e a forma das funções
de onda para n = 1, n = 2 e n = 3. 26
2.3 Gráfico da função densidade de probabilidade para o sistema da
“partícula na caixa” quando n = 1 27
2.4 Representação gráfica das probabilidades de se observar os
valores 0 e 1 para um
q-bit
qualquer 32
2.5 Pseudo–código do algoritmo evolutivo com inspiração quântica
usando representação binária. 34
2.6 Pseudo–código do algoritmo cultural. 35
2.7 Diagrama da estrutura geral do algoritmo cultural. 36
3.1 Listagem completa do algoritmo evolutivo com inspiração quân-
tica usando representação real. 40
3.2 Exemplo de um gene quântico do AEIQ– . 42
3.3 Genes de uma população quântica usando pulsos quadrados
como função densidade de probabilidade. 45
3.4 Funções cumulativas de probabilidade associadas aos genes de
uma população quântica. 46
3.5 Diagrama completo do Sistema Evolutivo com Inspiração Quântica 50
3.6 Diagrama de um modelo de partícula na caixa para uso no
AEIQ–. 51
3.7 Diagrama do modelo de partícula na caixa para uso no AEIQ–
após a atualização do gene quântico. 53
3.8 Diagrama mostrando uma rede neural recorrente. Este diagrama
não mostra as ligações dos
biases
. 55
3.9 Modelo de Aprendizado Supervisionado usando o AEIQ–. 56
3.10 Modelo de Aprendizado por Reforço usando o AEIQ–. 58
4.1 Esforço computacional para otimização da função f
sphere
. 67
4.2 Esforço computacional para otimização da função f
griewank
. 68
4.3 Gráfico de desempenho para uma função não separável usando
taxas de atualização diferentes. 70
4.4 Gráfico de desempenho para uma função separável usando
taxas de atualização diferentes. 71
4.5 Representação gráfica do problema do carro na montanha. 75
4.6 Variação da velocidade (linha vermelha) e da posição (linha azul)
no problema do carro na montanha. 77
4.7 Exemplo do problema do pêndulo invertido. 77
4.8 Ângulo do pêndulo com relação ao tempo. 80
4.9 Ângulo do pêndulo e velocidade do carro com relação ao tempo. 81
5.1 Diagrama de um foguete sem estabilizadores. 84
5.2 Modelo de aprendizado multi-agentes usando o AEIQ– . 86
5.3 Mapa 3D da função f
1
. 91
5.4 Mapa 3D da função f
2
. 92
5.5 Mapa 3D da função f
3
. 93
5.6 Mapa 3D da função f
4
. 94
5.7 Mapa 3D da função f
5
. 95
5.8 Mapa 3D da função f
6
. 96
5.9 Mapa 3D da função f
8
. 97
5.10 Mapa 3D da função f
9
. 98
5.11 Mapa 3D da função f
10
. 99
5.12 Mapa 3D da função f
11
. 100
5.13 Mapa 3D da função f
12
. 101
5.14 Mapa 3D da função f
13
. 102
5.15 Mapa 3D da função f
14
. 103
5.16 Mapa 3D da função f
sphere
. 104
5.17 Mapa 3D da função f
ackley
. 105
5.18 Mapa 3D da função f
griewank
. 106
5.19 Mapa 3D da função f
rastrigin
. 107
5.20 Mapa 3D da função f
schwefel
. 108
5.21 Mapa 3D da função f
rosenbrock
. 109
Lista de tabelas
2.1 Números da lista a ser ordenada distribuídos pelos múltiplos
universos do modelo com inspiração quântica 30
2.2 Números da lista após uma primeira ordenação realizada em
cada um dos 4 universos 30
2.3 Matriz de universos após a interferência diagonal 30
2.4 Matriz de universos após a interferência vertical 30
2.5 Probabilidades de observação de cada um dos possíveis esta-
dos do indivíduo quântico. 33
3.1 Exemplo de indivíduos que formam uma população quântica
Q(t) em uma geração t qualquer. 44
4.1 Configuração do AEIQ– para comparação com evolução dife-
rencial e enxame de partículas. 62
4.2 Resultado comparativo entre o AEIQ–, o algoritmo de evolução
diferencial e o de enxame de partículas com 1000 avaliações de
função. 62
4.3 Resultado comparativo entre o AEIQ–, o algoritmo de evolução
diferencial e o de enxame de partículas com 10000 avaliações
de função. 63
4.4 Tabela que indica a melhora percentual média ao se usar o
AEIQ–, comparando-o com o segundo melhor algoritmo, em
relação às características das funcões de teste. 63
4.5 Configuração 1 do AEIQ– para comparação com programa-
ção evolutiva clássica, programação evolutiva rápida, algoritmos
genéticos convencionais e o algoritmo evolutivo com inspiração
quântica usando representação binária. 65
4.6 Configuração 2 do AEIQ– para comparação com programa-
ção evolutiva clássica, programação evolutiva rápida, algoritmos
genéticos convencionais e o algoritmo evolutivo com inspiração
quântica usando representação binária. 65
4.7 Resultado comparativo entre o AEIQ– , o AEIQ–B (QEA), pro-
gramação evolutiva rápida (FEP), programação evolutiva clás-
sica (CEP) e algoritmos genéticos convencionais (GA). Os itens
com a designação “n.d.” indicam que o dado não está disponível. 65
4.8 Parâmetros do AEIQ– para aprendizado supervisionado. 73
4.9 Resultados do Treinamento da Rede Neural usando
Backpropa-
gation
. 73
4.10 Resultados do Treinamento da Rede Neural usando o AEIQ– . 74
4.11 Parâmetros do AEIQ– usados para o problema do carro na
montanha. 76
4.12 Resultados para o problema do carro na montanha. 76
4.13 Parâmetros usados para o problema do pêndulo invertido. 78
4.14 Parâmetros do AEIQ– usados para o problema do pêndulo
invertido. 79
Lista de tabelas
12
4.15 Parâmetros usados para o problema do pêndulo invertido. 80
1
Introdução
1.1
Motivação
Os problemas de otimização numérica são uma importante área de pesquisa,
tendo aplicações em problemas como otimização de plantas industriais, mistura
de produtos, refino, otimização de carteiras, mineração de dados e diversos outros
(Back97, Michalewicz94).
Os algoritmos evolutivos têm sido uma importante ferramenta para a solução
destes tipos de problemas. Estes métodos de otimização apresentam um bom grau
de paralelismo durante o processo de busca, são facilmente adaptáveis a diversos
tipos de problemas e têm bom desempenho em problemas de otimização ruidosos,
descontínuos, não-diferenciáveis ou multimodais (Back97).
Os algoritmos evolutivos podem ser divididos em várias classes. Novas clas-
ses e novas técnicas dentro de cada uma das classes têm sido constantemente de-
senvolvidas. Alguns tipos de algoritmos evolutivos são:
– Algoritmos Genéticos (Back97, Michalewicz94)
– Programação Genética (Koza92)
– Evolução Diferencial (Storn95)
– Algoritmos Culturais (Reynolds94, Reynolds04)
– Programação Evolutiva (Yao99)
Apesar de serem utilizados com sucesso em diversos problemas de otimiza-
ção, os algoritmos evolutivos apresentam, em algumas ocasiões, características que
podem prejudicar o seu desempenho. Como estes algoritmos necessitam avaliar di-
versas vezes se as soluções encontradas por ele são adequadas, problemas onde
essa avaliação seja computacionalmente custosa podem tornar proibitivo o uso dos
algoritmos evolutivos. Além disso, os algoritmos evolutivos podem ter dificuldades
para otimizar funções quando o cromossomo apresenta genes com problemas de
epistasia (quando a “qualidade” de um gene é dependente de um outro gene).
Neste sentido, os algoritmos genéticos com inspiração quântica
(Narayanan96, Han02, Han04) representam um dos mais recentes avanços na
Capítulo 1. Introdução
14
área de computação evolutiva. Estes algoritmos se baseiam em idéias inspiradas na
física quântica, em particular no conceito de superposição de estados, apresentando
melhor desempenho em diversos tipos de aplicações. Mais especificamente, o
algoritmo evolutivo com inspiração quântica usando representação binária (AEIQ–
B) (Han02) foi usado com sucesso em problemas de otimização combinatorial,
apresentando resultados superiores em relação aos algoritmos genéticos conven-
cionais em termos de tempo de convergência (e, conseqüentemente, em termos
do número de avaliações necessárias para se atingir bons resultados). O algoritmo
genético com inspiração quântica para otimização do problema do caixeiro-viajante
(Narayanan96) também apresenta bons resultados quando comparado com os
algoritmos evolutivos convencionais.
No entanto, nenhum dos algoritmos evolutivos com inspiração quântica pre-
encheram uma lacuna importante: a otimização de problemas numéricos. Apesar do
AEIQ–B poder ser utilizado para otimização neste tipo de problemas e apresentar
alguns resultados satisfatórios (Han04), em geral, o uso de genes com codificação
real, aliado a operadores específicos para esse tipo de codificação, produz resulta-
dos superiores, mais consistentes de experimento para experimento e com maior
precisão numérica (especialmente em domínios grandes, onde a codificação binária
requer uma representação proibitivamente longa) (Michalewicz94).
Um exemplo de problema onde os algoritmos evolutivos tradicionais não
apresentam bom desempenho é na otimização de pesos para redes neurais. Por ne-
cessitarem realizar, em muitos casos, um número elevado de avaliações da fun-
ção objetivo, os algoritmos genéticos tradicionais têm, em geral, um desempe-
nho inferior aos algoritmos de aprendizado tradicionais usados em redes neurais
(Yao99a, Ilonen03). Além disso, na área de redes neurais, normalmente necessita-
se fazer diversas seqüências de aprendizado, devido ao fato de que a topologia ideal
da rede neural não é, geralmente, conhecida à priori (Haykin99).
Um outro ponto importante é que, com exceção dos algoritmos culturais
(Reynolds94, Reynolds04), os algoritmos evolutivos não mantêm, normalmente,
conhecimento normativo sobre o espaço de busca de forma não-pontual. Em outras
palavras, os algoritmos evolutivos não armazenam informações sobre as regiões
mais promissoras do espaço de busca, a não ser através dos próprios indivíduos que
formam a população em uma determinada geração. Esta informação armazenada
nos próprios indivíduos é pontual e não pode ser compartilhada diretamente entre
os indivíduos.Ao contrário, nos algoritmos culturais, esta informação é guardada no
espaço de crenças e é diretamente compartilhada entre os indivíduos. Além disso,
a informação não é pontual, mas representada por intervalos dentro do espaço de
buscas que, ao longo do processo evolutivo, irá indicar as regiões mais promissoras
do espaço de buscas. Este tipo de informação pode, como no caso dos algoritmos
Capítulo 1. Introdução
15
culturais, melhorar o desempenho do algoritmo evolutivo consideravelmente. Esta
informação também pode ser usada como semente em problemas de otimização
online (onde a função que se quer otimizar varia ao longo do tempo), ao invés de
(ou além de) usar um conjunto de indivíduos para este fim.
1.2
Objetivos
Deste modo, baseado na discussão anterior, o objetivo principal desta tese é
propor um novo modelo de algoritmo evolutivo, inspirado em paradigmas da física
quântica, com as seguintes características:
– Rápida Convergência – Como a avaliação das soluções potenciais é, em
geral, a responsável pela maior parte do tempo computacional gasto com o
processo de otimização, deseja-se que o novo modelo seja capaz de realizar
a otimização com um número menor de chamadas à função de avaliação do
problema em questão;
– Escalabilidade – Em muitos problemas, o número de variáveis de entrada
da função que se deseja otimizar é grande. Neste sentido, deseja-se que o
algoritmo de otimização seja robusto com relação à dimensionalidade do
problema, ou seja, que o aumento do número de variáveis não produza um
aumento exponencial no esforço computacional ao se aumentar o número de
variáveis da função que está sendo otimizada;
– Conhecimento Normativo – É interessante que o algoritmo de otimização
seja capaz de armazenar conhecimento com relação às regiões promissoras
do espaço de busca. Este conhecimento pode ser usado durante o processo
de otimização convencional e em problemas de otimização online (onde a
função que está sendo otimizada varia continuamente ao longo do tempo sem,
no entanto, sofrer mudanças bruscas);
– Aprendizado Compartilhado – Como uma conseqüência do conhecimento
normativo, é interessante que este conhecimento possa ser compartilhado
entre os indivíduos da população que está sendo evoluída.
1.3
Contribuições
Em função dos objetivos apresentados na seção anterior, este trabalho se
concentrou na definição de um novo modelo de algoritmo evolutivo com inspiração
quântica que ofereça as seguintes características:
– Representação específica para problemas de otimização numérica (represen-
tação por números reais);
Capítulo 1. Introdução
16
– Maior velocidade de convergência quando comparado com algoritmos gené-
ticos convencionais;
– Menor complexidade computacional com relação ao número de variáveis
(dimensões) do problema que se quer otimizar;
– Mecanismos de compartilhamento de conhecimento entre indivíduos da po-
pulação;
Além disso, este trabalho apresenta outras contribuições:
– Desenvolvimento de um ambiente de testes para o AEIQ– usando a ferra-
menta MATLAB 7.0 nos ambientes Windows XP e Linux;
– Análise comparativa do desempenho do AEIQ– com outros algoritmos
evolutivos tradicionalmente usados em problemas de otimização;
– Análise do desempenho do algoritmo com relação à dimensionalidade do
problema que se quer otimizar;
– Desenvolvimento de um algoritmo de treinamento de redes neurais recorren-
tes usando o AEIQ– para problemas de previsão de séries temporais e para
problemas de controle;
– Desenvolvimento de um ambiente de testes para o algoritmo de treinamento
de redes neurais recorrentes usando a ferramente MATLAB 7.0 nos ambientes
Windows XP e Linux;
– Análise comparativa do desempenho das redes neurais treinadas com o
AEIQ– com outros algoritmos de treinamento de redes neurais e de apren-
dizado por reforço.
1.4
Descrição do Trabalho
Este trabalho apresenta uma nova representação para os algoritmos genéticos
com inspiração quântica. Esta representação, baseada em números reais, é uma
poderosa ferramenta para a otimização de problemas numéricos e se mostra mais
eficiente do que os algoritmos genéticos convencionais que usam o mesmo tipo
de representação para otimizar funções matemáticas. Além disso, o algoritmo
também se mostra mais eficiente na otimização de problemas numéricos do que
o algoritmo evolutivo com inspiração quântica que usa representação binária. Entre
outras propriedades importantes deste modelo está a sua capacidade de convergir
rapidamente para uma boa solução usando poucos indivíduos na sua população.
Isto reduz drasticamente o número de avaliações necessárias para a otimização, o
Capítulo 1. Introdução
17
que é um importante fator de desempenho quando o modelo está sendo usado em
problemas onde a avaliação consome muito tempo de processamento.
Além de apresentar o novo modelo, este trabalho também descreve uma série
de testes realizados: alguns testes de otimização utilizando funções benchmark para
otimização numérica, onde se pretende comparar o desempenho do algoritmo pro-
posto com outros modelos de otimização inspirados na evolução natural, incluindo
métodos já consagrados e métodos mais recentes; e alguns testes no treinamento de
redes neurais (neuroevolução) recorrentes para previsão de séries temporais (apren-
dizado supervisionado) e para tarefas de controle (aprendizado por reforço).
Em especial, com relação ao uso do algoritmo para o treinamento de redes
neurais, deseja-se mostrar que, ao contrário dos métodos de descida por gradiente,
usados tradicionalmente para realizar o treinamento destas redes, e que se baseiam
na otimização de uma única rede, o método de neuroevolução proposto é capaz
de otimizar os pesos sinápticos de várias redes neurais ao mesmo tempo. Com
isto, é possível diminuir a ocorrência de problemas de estagnação do processo de
aprendizado por aprisionamento em mínimos locais, sem incorrer nos problemas
tradicionais do uso de algoritmos evolutivos para otimização de pesos sinápticos
já que, com o uso dos algoritmos evolutivos com inspiração quântica, o número de
indivíduos que precisam ser avaliados para se atingir uma solução ótima é reduzido.
Em outras palavras, com o uso de algoritmos evolutivos com inspiração quântica,
pode-se acelerar o aprendizado ao mesmo tempo em que se evita uma convergência
prematura para soluções sub-ótimas.
O método de neuroevolução proposto também apresenta outros benefícios que
não estão diretamente ligados ao fato do algoritmo ter inspiração quântica. Estes
benefícios se tornam evidentes, principalmente, quando se usa estes algoritmos
para o treinamento de redes neurais totalmente recorrentes (fully recurrent neural
networks), o que permite contornar problemas encontrados em métodos tradicionais
de treinamento baseados em métodos de descida por gradiente para este tipo de rede
tais como (Blanco01):
– Aprendizado Recorrente em Tempo Real (Real Time Recurrent Learning -
RTRL) – este modelo tem como principal desvantagem o alto custo compu-
tacional para executar cada iteração;
– Retropropagação pelo Tempo (Backpropagation Through Time – BTT) – este
modelo tem como principal desvantagem a necessidade de se saber o tamanho
da seqüência de entrada à priori.
Finalmente, o modelo apresentado neste trabalho permite, entre outras coisas,
a definição automática da topologia da rede neural final. Isto inclui, não só o número
de processadores em cada camada, como também o número total de camadas que
Capítulo 1. Introdução
18
compõem a rede neural. Além disso, devido à sua característica probabilística, o
treinamento por algoritmos evolutivos com inspiração quântica evita a ocorrência
de super-treinamento da rede neural, eliminando a necessidade do uso de conjuntos
de validação para o processo de aprendizado.
Este trabalho tem como metas:
– Demonstrar que o novo modelo proposto tem um desempenho melhor do
que os algoritmos evolutivos clássicos em diversos problemas de otimização
numérica;
– Demonstrar a aplicabilidade e as vantagens deste novo modelo no aprendi-
zado supervisionado de redes neurais em problemas de previsão e controle;
– Apresentar discussões sobre as características principais deste novo modelo e
os resultados obtidos nos estudos de caso.
1.5
Organização do Trabalho
Este trabalho está dividido da seguinte forma:
– No capítulo 2 é apresentado um resumo dos fundamentos teóricos necessários
para a compreensão deste trabalho;
– No capítulo 3 o modelo proposto de algoritmo evolutivo com inspiração
quântica e representação real é apresentado em detalhes;
– O capítulo 4 mostra os resultados obtidos em diversos estudos de caso;
– O capítulo 5 apresenta discussõessobre o modelo e os resultados encontrados,
e aponta direções para trabalhos futuros.
2
Fundamentos
2.1
Mecânica Quântica
2.1.1
Introdução
Quando a luz incide sobre uma superfície de metal, elétrons são arrancados
desta mesma superfície. Este problema não pode ser perfeitamente explicado pela
mecânica clássica devido a três fatores (Green01):
– Não importa o quão baixa é a intensidade da luz, os elétrons são arrancados
instantaneamente da superfície do metal. De acordo com a física clássica, os
elétrons precisariam acumular durante um certo tempo a energia necessária
para escapar da superfície do metal, já que a luz deveria ter sua energia
distribuída uniformemente ao longo da onda;
– Existe uma freqüência de corte para o feixe incidente de luz, abaixo da qual
nenhum elétron é emitido. De acordo com as leis de Maxwell, a energia
transportada pela luz depende apenas da amplitude da onda eletromagnética
e não da freqüência;
– Se a energia cinética máxima dos elétrons emitidos for relacionada através
de um gráfico com a freqüência da luz incidente, uma linha reta será obtida.
Como a energia deveria estar relacionada apenas com a amplitude da onda, de
acordo com as leis de Maxwell, não deveria existir uma relação linear entre
freqüência e energia.
A explicação para estes fenômenos foi proposta em 1900 por Planck
(Planck01, Green01) ao abandonar o conceito clássico para o comportamento da
luz apenas como uma onda eletromagnética. Planck demonstrou que, se a energia
da luz estiver concentrada em pacotes (ou quanta) de energia E = hν (onde ν é a
freqüência da luz e h é a constante de Planck), os problemas descritos anteriormente
podem ser, então, facilmente explicados. Através desta explicação, a luz passa a ter,
em determinadas situações, um comportamento de uma partícula (chamada fóton).
Capítulo 2. Fundamentos
20
2.1.2
Funções de Onda
A idéia de que a luz se comporta em alguns casos como uma onda e em alguns
casos como uma partícula leva imediatamente à questão sobre se o fóton tem outras
propriedades comuns às partículas. Como energia e massa estão relacionadas pela
equação E = mc
2
, o fóton (que se move com a velocidade da luz c) tem uma massa
relativística m = hν/c
2
. Portanto, como o fóton tem massa e velocidade, também
deve ter um momento p = mc = hν/c = h/λ, onde λ é o comprimento de onda da
luz.
De maneira inversa, assim como os fótons têm um momento característico
h/λ, outras partículas (por exemplo, um elétron), que também têm um momento
característico, devem possuir um comprimento de onda relacionado a este momento
λ = h/p. Se uma partícula tem um comprimento de onda característico, então deve
ser possível representar este comprimento de onda matematicamente da mesma
maneira que uma onda é representada, ou seja, usando-se uma função de onda. Na
física clássica, uma onda estacionária com comprimento de onda λ, propagando-se
na direção positiva do eixo x, pode ser representada pela equação 2-1 (Green01).
ψ(x) = exp(i2πx/λ) = cos(2πx/λ) + i sin(2πx/λ) (2-1)
Onde i =
√
−1. Substituindo λ = h/p, obtém-se a equação (2-2).
ψ(x) = exp(ipx/) (2-2)
Onde = h/2π. A partir da função de onda, é possível determinar a probabilidade
de que a partícula esteja em um determinado ponto do espaço ao se tentar observá-
la. A densidade de probabilidade para a localização de uma partícula com função
de onda ψ deve ser o quadrado da amplitude da função de onda, ou seja, |ψ|
2
(Gillespie73, Green01). Em uma dimensão, uma partícula, representada pela função
de onda ψ(x), terá uma densidade de probabilidade de ser encontrada no intervalo
x + dx igual a:
|ψ(x)|
2
dx = ψ
∗
ψdx (2-3)
Onde ψ
∗
representa o conjugado complexo de ψ. Em três dimensões, a densidade
de probabilidade da partícula é |ψ(r)|
2
(onde r é um vetor de três dimensões
(x, y, z)). Isto significa que a probabilidade de se encontrar a partícula no elemento
infinitesimal de volume dτ = dxdydz no ponto r é |ψ(r)|
2
dτ. A integral deste valor
sobre todo o espaço onde a partícula pode ser encontrada fornece a probabilidade
de se encontrar esta partícula em algum lugar do espaço: conseqüentemente, este
valor deve ser igual a 1 (equação 2-4).
∞
−∞
|ψ|
2
dτ = 1 (2-4)
Capítulo 2. Fundamentos
21
As funções de onda introduzem um conceito importante e pouco intuitivo:
a relação entre a função de onda e a localização da partícula é, por natureza,
probabilística (Green01). Em um feixe de luz, por exemplo, a função de onda
está espalhada por toda a frente de onda de forma homogênea mas, quando se
tenta detectar os fótons, nota-se que os mesmos chegam de forma imprevisível ao
detector, com uma densidade de probabilidade proporcional à intensidade do feixe
de luz ou proporcional ao quadrado da amplitude da onda. Em outras palavras, o
valor das propriedades da partícula que podem ser representadas por funções de
onda (por exemplo, a posição da partícula) não pode ser conhecido à priori; sem
efetivamente medir a propriedade que se deseja, tudo que se pode afirmar sobre esta
propriedade é que ela tem diferentes probabilidades de assumir diferentes valores
quando for observada. Assim, antes de se observar através de algum instrumento,
por exemplo, a posição de um elétron confinado dentro de alguma região do espaço,
o máximo que se pode determinar é a probabilidade de observá-lo em alguma região
deste espaço de confinamento.
As funções de onda devem obedecer algumas propriedades. Estas proprieda-
des são:
1. ψ deve ser finita;
2. ψ deve ser contínua;
3. ψ deve ser derivável duas vezes;
4. ψ deve ser integrável em todo o espaço.
2.1.3
Operadores Hermitianos
As informações contidas nas funções de onda são as únicas de que se pode
dispor a respeito de um sistema físico microscópico. Como já foi visto, é possível
manipular estas funções de onda de modo a se obter a distribuição de probabilidade
espacial do sistema físico representado por esta função. No entanto, esta informação
espacial não é a única que se deseja obter sobre o sistema físico. Deseja-se também
ser capaz de medir quantidades como o momento, a energia e o momento angular de
uma partícula. Apesar da função de onda não poder ser medida diretamente, todas
essas propriedades mecânicas podem ser medidas diretamente e são chamadas,
na mecânica quântica, de observáveis (em inglês, observables) (Gillespie73). Os
observáveis são representados matematicamente por operadores. Alguns exemplos
de observáveis são a posição e o momento de uma partícula.
Um operador é um objeto matemático que age sobre uma função
transformando-a em outra função. Um exemplo é o operador
ˆ
∂
x
, que realiza a
Capítulo 2. Fundamentos
22
operação de “diferenciar com respeito a variável x”. Este operador transforma uma
função f(x) em sua derivada.Neste trabalho, todos os operadores serão distinguidos
de outros objetos matemáticos através do uso de um sinal ˆ sobre o operador.
Apesar de, em geral, os operadores transformarem uma função em outra, em
alguns casos especiais um operador pode transformar uma função nela mesma. Um
exemplo é o operador
ˆ
∂
x
que transforma a função e
αx
em αe
αx
, ou seja, a mesma
função multiplicada por uma constante α. A função que é transformada nela mesma
é chamada de autofunção (ou autovetor) e a constante multiplicativa introduzida
pelo operador é chamada de autovalor.
Os conceitos de autofunção e autovalorsão extremamente importantes na me-
cânica quântica. Isto se deve ao fato de que todos os observáveis são representados
por operadores, sendo que os autovalores, os quais podem ser encontrados atra-
vés da aplicação de um operador a uma função, são os únicos valores que podem
efetivamente ser observados ao se fazer uma medida. Em outras palavras, qualquer
medição de um observáveldeveencontrar um dos possíveisautovaloresdo operador
(Gillespie73). Por exemplo, os níveis de energia de um átomo são autovalores do
operador de energia; qualquer medida realizada para se determinar o nível de ener-
gia de um átomo deve encontrar um desses autovalores. No entanto, é importante
destacar que, mesmo na mecânica quântica, os valores possíveis para os autovalo-
res de um operador não precisam, necessariamente, ser discretos, ou seja, é possível
que para certos observáveis, os autovaloresdo operador correspondente formem um
conjunto contínuo.
Os operadores que representam quantidades observáveis devem respeitar
duas restrições: linearidade e hermiticidade. Um operador
ˆ
A é linear quando, para
quaisquer valores constantes α e β, e para quaisquer funções de onda ψ(x) e φ(x), a
equação 2-5 for válida.
ˆ
A(αψ(x) + βφ(x)) = α
ˆ
Aψ(x) + β
ˆ
Aφ(x) (2-5)
Um operador
ˆ
A é hermitiano se, para quaisquer funções de onda ψ(x) e φ(x),
a equação 2-6 for válida.
∞
−∞
ψ
∗
(x)
ˆ
Aφ(x)dx =
∞
−∞
ˆ
Aψ
∗
(x)φ(x)dx (2-6)
Duas importantes conseqüências advêm destas restrições (Gillespie73): a
primeira é que os autovalores de um operador hermitiano são números reais;
a segunda é que as autofunções de um operador hermitiano correspondentes a
autovalores diferentes, são ortogonais.
Supondo-se então que um observável A é representado por um operador
ˆ
A
e que uma função de onda ψ é uma autofunção de
ˆ
A com autovalor α (ou seja,
ˆ
Aψ = αψ), então o sistema tem um valor definido α para o observável A. Uma
Capítulo 2. Fundamentos
23
medida de A irá resultar no valor α com probabilidade 1. Por outro lado, se a função
de onda ψ não for uma autofunção de
ˆ
A, então uma medida de A pode produzir
qualquer um de diferentes autovaloresdo operador
ˆ
A com diferentes probabilidades.
O valor esperado de um observável A, denotado por < A >, é definido pela equação
2-7.
< A >=
ψ
∗
ˆ
Aψdτ (2-7)
De modo a simplificar a notação matemática, pode-se usar a notação de
Dirac para estes problemas (Green01). Neste caso, a função de onda ψ passa a
ser representada pelo símbolo |ψ (chamado ket). O conjugado complexo ψ
∗
da
função de onda é representado pelo símbolo ψ| (chamado bra). As integrais do tipo
φ
∗
ψdτ são representadas pelo símbolo φ|ψ (é importante notar que este símbolo
implica na integração da função, ou seja, φ|ψ =
φ
∗
ψdτ). Portanto, uma função
de onda ψ está normalizada se ψ|ψ = 1.
A principal característica que se deseja ressaltar com relação às funções de
onda e aos operadores, é a possibilidade de se representar as funções de onda como
uma expansão por autofunções. Em outras palavras, além de serem ortogonais, as
autofunções de um operador hermitiano formam uma base ortonormal completa
que permite escrever qualquer função de onda para o sistema físico como uma
superposição (combinação linear) destas autofunções. Ou seja, se um operador
ˆ
A possui um conjunto de autofunções |ψ
i
com autovalores α
i
(ou seja,
ˆ
A|ψ
i
=
α
i
|ψ
i
), então qualquer função de onda φ válida para o sistema pode ser representada
pela superposição de autofunções |ψ
i
conforme mostrado na equação 2-8.
φ =
i
c
i
|ψ
i
(2-8)
Onde c
∗
i
c
i
(ou |c
i
|
2
é a probabilidade de se medir o autovalor α
i
. Isto significa que,
ao fazer uma medida de um estado quântico, a função de onda é projetada em
uma das autofunções que formam a base ortonormal e o autovalor correspondente
a esta autofunção é o valor observado. Em outras palavras, a função de onda
pode ser escrita como uma combinação linear dos autovetores associados à um
determinado operador.Os coeficientes associados aos autovetoresnesta combinação
linear permitem determinar a probabilidade de que a função de onda seja projetada
sobre cada um dos autovetores quando a observação for realizada. Vale ressaltar
que, como |c
i
|
2
representa a probabilidade de um autovalor ser observado, e como a
base ortonormal é completa,
i
|c
i
|
2
= 1.
2.2
Capítulo 2. Fundamentos
24
Um Exemplo de um Sistema Físico Quântico – O Modelo da Partícula na
Caixa
Esta seção tem como objetivo mostrar um exemplo de um sistema físico quân-
tico hipotético (hipotético no sentido de não ser possível reproduzir as condições
ideais nas quais o experimento deve ser realizado) de modo a ilustrar os conceitos
da mecânica quântica apresentados anteriormente. Além disso, o sistema físico aqui
apresentado será usado, posteriormente, como um modelo físico que permite imple-
mentar o algoritmo genético com inspiração quântica apresentado neste trabalho.
Considere-se uma partícula (um elétron por exemplo) confinada dentro de
uma caixa cujas paredes têm um potencial infinito. Em outras palavras, não é
permitido que a partícula saia de dentro da caixa onde a mesma está confinada.
Além disso, o movimento desta partícula está limitado a uma dimensão (o sentido
da largura da caixa). Um diagrama deste modelo pode ser visto na figura 2.1 (nesta
figura, V = ∞ indica a região de potencial infinito).
V(x) = ∞ V(x) = ∞
Figura 2.1: Diagrama do sistema físico hipotético da “partícula na caixa”
Para o problema unidimensional (ou seja, a partícula pode se mover apenas
sobre o eixo x), pode-se usar a equação de Schrödinger independente do tempo
(Green01) para calcular a função de onda. Esta equação pode ser escrita como em
2-9.
−
2
2m
d
2
ψ(x)
dx
2
+ V(x)ψ(x) = Eψ(x) (2-9)
Onde é a constante de Planck reduzida, m é a massa da partícula, ψ(x) é a função
de onda estacionária da partícula (esta é a função que se deseja encontrar), V(x)
determina o valor da energia potencial em função da posição e E é a energia da
partícula.
Supondo-se que se deseja encontrar a função de onda para uma partícula em
uma situação onde as barreiras de potencial estejam posicionadas, respectivamente,
em x = 0 e x = L, pode-se considerar que a equação anterior, dentro do intervalo
[0, L] para x assume a forma mostrada em 2-10, já que o potencial dentro dessa
região é igual a zero.
Capítulo 2. Fundamentos
25
−
2
2m
d
2
ψ(x)
dx
2
= Eψ(x) (2-10)
Esta equação diferencial é bem conhecida e sua solução é da forma:
ψ(x) = A sin(kx) + Bcos(kx) (2-11)
E =
k
2
2
2m
(2-12)
Nestas equações, A e B podem ser quaisquer números complexos e o número k
deve ser um número real (já que a energia E deve ser um número real). De modo
a definir a solução específica para este problema, deve-se determinar as condições
de contorno e encontrar os valores de A e B que satisfaçam essas condições. Como
já foi mencionado anteriormente, a equação deve garantir que a função de onda
seja contínua ao longo de todo o eixo real. Como a partícula não pode estar na
região em que a barreira de potencial é infinita, deduz-se que, quando x tende a
0 ou quando x tende a L, a probabilidade |ψ(x)|
2
de encontrar uma partícula nesta
região deve tender a zero. Isto está de acordo com a intuição física já que, ao se
aproximar da barreira de potencial, a repulsão sobre a partícula aumenta. Assim,
ψ(0) = ψ(L) = 0. De acordo com a equação 2-11, para que ψ(0) = 0 o termo com
o cosseno deve desaparecer (já que sin(0) = 0 e cos(0) = 1) e, portanto, B deve ser
igual a zero. Já para a situação em que x = L, ψ(L) = Asin(kL) = 0. Para o caso
não–trivial em que A 0, sin(kL) = 0 somente se k = nπ/L, onde n ∈ N
+
.
Finalmente, para se encontrar o valor de A, deve-se lembrar que a função de
onda deve ser normalizada, conforme mostrado na equação 2-4.
1 =
∞
−∞
|ψ(x)|
2
dx = |A|
2
L
0
sin
2
(kx)dx = |A|
2
L
2
(2-13)
Rearranjando a equação anterior tem-se:
|A| =
2
L
(2-14)
Assim, A pode ser qualquer número complexo cujo valor absoluto |A| seja igual a
√
2/L. Como diferentes valores de A produzem o mesmo estado físico, e para fins
de simplificação, define-se A =
√
2/L.
Substituindo-se estes valores nas equações 2-11 e 2-12 chega-se as equações:
ψ
n
(x) =
2
L
sin
nπx
L
(2-15)
E
n
=
n
2
2
π
2
2mL
2
=
n
2
h
2
8mL
2
(2-16)
Onde n ∈ N
+
. O valor de n determina o número de ciclos da senóide, como
pode ser visto na figura 2.2.
A função de onda deve ser estacionária e, por este motivo, o número n deve
ser inteiro e maior do que zero. Isto, juntamente com a equação 2-16, explica porque
Capítulo 2. Fundamentos
26
0
4
8
12
16
20
24
28
0 0.25 0.50 0.75
n = 1
n = 2
n = 3
Figura 2.2: Gráfico mostrando os níveis de energia e a forma das funções de onda
para n = 1, n = 2 e n = 3.
os níveis de energia da partícula são discretos.
Por sua vez, a função densidade de probabilidade p(x) para este sistema físico
é dada pela equação:
p(x) = |ψ(x)|
2
=
2
L
sin
2
nπx
L
(2-17)
O gráfico desta equação quando n = 1 é mostrado na figura 2.3.
O resultado observado neste gráfico é o mesmo esperado intuitivamente. A
partícula tem mais probabilidade de ser observada na parte central da caixa do que
nas bordas da mesma (onde a distância da barreira de potencial infinito começa a
ser menor).
2.3
Computação Quântica
Um computador quântico é um dispositivo que faz uso direto de certos fenô-
menos da mecânica quântica para realizar operações com dados. Estes fenômenos
permitem construir, em teoria, computadores que obedecem novas leis mais permis-
sivas de complexidade computacional(Spector04). O termo “computação quântica”
é, portanto, usado para descrever processos computacionais que se baseiam nestes
fenômenos específicos e que são, assim, capazes de diminuir o esforço e a com-
plexidade para se resolver determinados problemas. A principal perspectiva que se
abre com o uso de computadores quânticos em relação ao seu poder de processa-
Capítulo 2. Fundamentos
27
L
2
L
Figura 2.3: Gráfico da função densidade de probabilidade para o sistema da “partí-
cula na caixa” quando n = 1
mento é o fato de que “as possibilidades contam, mesmo que elas nunca venham a
acontecer” (Spector04).
Em um computador clássico, o bit é a menor unidade de informação, podendo
assumir os valores 0 ou 1. Em um computador quântico, a unidade de informação
básica, chamada de q-bit, pode assumir os estados |0, |1 ou uma superposição
dos dois estados. Esta superposição de dois estados é uma combinação linear dos
estados |0 e |1 e pode ser representada pela equação 2-18.
|ψ = α |0 + β |1 (2-18)
Onde |ψ é o estado do q-bit e, conforme discutido na seção anterior, |α|
2
e |β|
2
são
as probabilidades de que os estados 0 ou 1 sejam observados quando o q-bit for
medido.
Ao ser observado, o bit quântico será trazido para o nível clássico e o estado
observado será o valor 0 ou 1. Esta superposição de estados oferece um grau
de paralelismo incomparável aos computadores quânticos que, se bem explorado,
permite que estes computadores realizem tarefas praticamente impossíveis de serem
realizadas em computadores clássicos. Um exemplo de uma tarefa deste tipo é
a fatoração inteira de grandes números. Neste problema, deseja-se encontrar os
dois números primos cujo produto seja igual a um número x fornecido. Esta
tarefa pode levar milhões de anos para ser resolvida em computadores clássicos
usando os algoritmos conhecidos mais sofisticados. Em um computador quântico,
no entanto, a mesma tarefa levaria apenas alguns segundos para ser concluída. Uma
discussão mais detalhada sobre o funcionamento dos computadores quântico pode
ser encontrada em (Rieffel00).
Capítulo 2. Fundamentos
28
2.4
Algoritmos com Inspiração Quântica
Embora a computação quântica ofereça uma boa promessa em termos de
capacidade de processamento, dois problemas impedem, atualmente, que a mesma
se torne uma ferramenta útil: a dificuldade de se implementar um computador
quântico e a dificuldade de se criar algoritmos que tirem proveito da capacidade
de processamento destes computadores. Deste modo, as pesquisas na área de
computação quântica se concentram, atualmente, em dois pontos:
– Desenvolvimento de novos algoritmos que sejam mais eficientes nos com-
putadores quânticos do que os algoritmos equivalentes para computadores
clássicos;
– Desenvolvimento de um hardware que torne viável o uso dos computadores
quânticos.
No entanto, no artigo (Moore95), uma nova abordagem é proposta. Ao invés
de desenvolver novos algoritmos para computadores quânticos ou de tentar viabili-
zar o uso destes, a idéia de computação com inspiração quântica é apresentada. O
objetivo desta nova abordagem é criar algoritmos clássicos (capazes, portanto, de
serem executados em computadores clássicos) que tirem proveito dos paradigmas
da física quântica, de forma a melhorar o desempenho dos mesmos na resolução de
problemas.
Uma metodologia para a formulação inicial de um algoritmo com inspiração
quântica também é apresentada em (Moore95). Esta metodologia consiste dos
seguintes passos:
1. O problema deve ter uma representação numérica ou, caso não tenha, um
método para sua conversão em representação numérica deve ser empregado;
2. A configuração inicial deve ser determinada;
3. Uma condição de parada deve ser definida;
4. O problema deve poder ser dividido em sub-problemas menores;
5. O número de universos (ou estados de superposição) deve ser identificado;
6. Cada sub–problema deve ser associado a um dos universos;
7. Os cálculos nos diferentes universos devem ocorrer de forma independente;
8. Alguma forma de iteração entre os múltiplos universos deve existir. Esta
interferência deve, ou permitir encontrar a solução para o problema, ou
Capítulo 2. Fundamentos
29
fornecer informação para cada sub-problema em cada universo ser capaz de
encontrá-la.
Um exemplo de um algoritmo com inspiração quântica é o “Algoritmo de
Ordenação com Inspiração Quântica” (Moore95), baseado no algoritmo de “orde-
nação por seleção”. Este algoritmo é usado para resolver o problema de ordenação
numérica onde deseja-se ordenar uma lista com n elementos em ordem ascendente
ou descendente. O algoritmo funciona da seguinte maneira:
1. Denomina-se a lista que se quer ordenar por L
1
(esta lista deve conter pelo
menos dois elementos) e inicializa-se uma segunda lista L
2
sem nenhum
elemento;
2. Encontra-se o menor elemento (caso se esteja ordenando de forma ascen-
dente) em L
1
e após remover este elemento da lista L
1
acrescenta-se o mesmo
à lista L
2
;
3. Repete-se o passo anterior até que L
1
esteja vazia. L
2
contém agora todos os
elementos em ordem crescente.
Quando implementado de maneira eficiente, o tempo de execução deste
algoritmo é da ordem de
1
2
N(N − 1) (Knuth73), onde N é o tamanho inicial de L
1
.
Por exemplo, caso se queira ordenar uma lista com 16 valores, serão necessários,
em média, 120 buscas à lista vezes para encontrar o menor elemento. Usando
elementos inspirados na física quântica, este algoritmo pode ser melhorado da
seguinte maneira (Moore95) (usa-se aqui, como exemplo, uma lista L
1
contendo
16 elementos L
1
= (16, 14, 12, 3, 8, 4, 15, 7, 11, 6, 2, 5, 1, 10, 9, 13):
1. Fixar n = número de elementos na lista = 16;
2. Fixar u = número de superposições (universos) necessárias =
√
n = 4;
3. Fixar l = número de elementos da lista em cada universo = u = 4;
4. Divide-se a lista L
1
em 4 partes: os primeiros quatro números são colocados
no universo 1, os próximos 4 números são colocados no universo 2, e assim
por diante. Desta forma, para este exemplo, pode-se construir a tabela 2.1
com os universos e os elementos que estão armazenados em cada um deles:
5. Usa-se o algoritmo de ordenação por seleção em cada um dos universos,
separadamente. Deste modo, obtém-se a tabela 2.2.
Capítulo 2. Fundamentos
30
u
0
16 14 12 3
u
1
8 4 15 7
u
2
11 6 2 5
u
3
1 10 9 13
Tabela 2.1: Números da lista a ser ordenada distribuídos pelos múltiplos universos
do modelo com inspiração quântica
u
0
3 12 14 16
u
1
4 7 8 15
u
2
2 5 6 11
u
3
1 9 10 13
Tabela 2.2: Números da lista após uma primeira ordenação realizada em cada um
dos 4 universos
6. Realiza-se uma interferência diagonal: os universos são rearranjados
pegando-se as diagonais que têm, como primeiro elemento, os números da
primeira coluna da matriz. Estes elementos são reordenados e reposicionados
na matriz. Em outras palavras, o primeiro universo irá conter os elementos
da diagonal principal (3, 7, 6, 13), o segundo universo irá conter os elementos
formados pela diagonal que se inicia na primeira coluna da segunda linha
(4, 5, 10, 16), o terceiro universo irá conter os elementos formados pela
diagonal que se inicia na primeira coluna da terceira linha (2, 9, 14, 15) e,
finalmente, o quarto universo irá conter os elementos formados pela diagonal
que se inicia na primeira coluna da quarta linha (1, 12, 8, 11). A matriz obtida
por essa interferência diagonal é novamente processada pelo algoritmo de
ordenação, separadamente por universo. Assim, forma-se a tabela 2.3.
u
0
3 6 7 13
u
1
4 5 10 16
u
2
2 9 14 15
u
3
1 8 11 12
Tabela 2.3: Matriz de universos após a interferência diagonal
7. Em seguida, realiza-se a interferência vertical, onde cada coluna da matriz de
universos é ordenada e transposta. Com isto, obtém-se a tabela 2.4.
u
0
1 2 3 4
u
1
5 6 8 9
u
2
7 10 11 14
u
3
12 13 15 16
Tabela 2.4: Matriz de universos após a interferência vertical
Capítulo 2. Fundamentos
31
8. Checa-se o último valor do universo u
i
e verifica-se se é menor ou igual ao
primeiro valor de u
i+1
para i = 0, 1, . . . , n − 1. Caso não seja, repete-se os
passos 6 e 7 novamente até que esta condição seja satisfeita.
O tempo de execução deste algoritmo é da ordem de
√
N[N + 2(
√
N − 1)]
(Moore95). Portanto, uma lista com 16 elementos precisará, em média, de 88 buscas
na lista usando-se a ordenação por seleção, o que é significativamente menor do que
o número de buscas (120) necessárias para a execução do algoritmo sem inspiração
quântica.
No artigo (Moore95), também é apresentado um algoritmo com inspiração
quântica para determinar a solução para o problema do 15-puzzle. Uma explicação
mais detalhada sobre estes algoritmos e sobre os algoritmos com inspiração quân-
tica pode ser encontrada em (Moore95).
2.5
Algoritmos Evolutivos com Inspiração Quântica – Representação Binária
O algoritmo evolutivo com inspiração quântica usando representação binária,
que neste trabalho será designado pela sigla AEIQ–B (Quantum–Inspired Evoluti-
onary Algorithm – QEA na sigla original), foi proposto inicialmente em (Han00).
Neste modelo, o algoritmo evolutivo proposto é também caracterizado por um cro-
mossomo, uma função de avaliação e uma dinâmica populacional. Entretanto, ao
invés de uma representação binária convencional, este algoritmo usa uma represen-
tação especial que simula um cromossomo formado por q-bits. Esta representação
é feita da seguinte forma: um q-bit é formado por um par de números (α, β), como
na equação 2-19.
α
β
(2-19)
Onde |α|
2
+ |β|
2
= 1. O valor dado por |α|
2
indica a probabilidade de que o q-bit terá
o valor 0 quando for observado e o valor |β|
2
indica a probabilidade de que o q-bit
terá o valor 1 quando for observado. Pode-se visualizar graficamente esta relação
entre α e β, conforme mostrado na figura 2.4.
A partir da definição do q-bit acima, pode-se definir um indivíduo quântico
formado por m q-bits, conforme a equação 2-20.
α
1
α
2
... α
m
β
1
β
2
... β
m
(2-20)
De forma semelhante à mostrada na equação 2-19, |α
i
|
2
+ |β
i
|
2
= 1 onde
i = 1, 2, 3, ..., m.
Capítulo 2. Fundamentos
32
|α|
2
|β|
2
Figura 2.4: Representação gráfica das probabilidades de se observar os valores 0 e
1 para um q-bit qualquer
Deste modo, cada indivíduo quântico representa uma superposição de indiví-
duos formados por m genes. Seja, por exemplo, um indivíduo quântico formado por
3 q-bits com os valores mostrados na equação 2-21.
1
√
2
1
√
2
1
2
1
√
2
1
√
2
√
3
2
(2-21)
Para se calcular a amplitude de probabilidade (o módulo da amplitude de probabi-
lidade ao quadrado é igual à probabilidade se observar o estado) do estado |000,
multiplica-se as amplitudes de probabilidade de se observar os estados 0 em cada
um dos bits (α
1
, α
2
e α
3
). Para calcular a amplitude de probabilidade de se observar
o estado |001, multiplica-se as amplitudes de probabilidade de se observar estes
bits (α
1
, α
2
e β
3
). Estendendo-se isto para as outras possibilidades de observação
dos estados, a superposição dos mesmos pode ser representada pela equação 2-22.
1
4
|000+
√
3
4
|001+
1
4
|010+
√
3
4
|011+
1
4
|100+
√
3
4
|101+
1
4
|110+
√
3
4
|111
(2-22)
Este resultado significa que, cada um dos possíveis estados deste indivíduo, tem a
probabilidade de ser observado mostrada na tabela 2.5.
O AEIQ–B, proposto em (Han00), é definido como na figura 2.5. Neste
algoritmo, Q(t) é uma população com um ou mais indivíduos quânticos. No passo
Capítulo 2. Fundamentos
33
Estado Probabilidade
000
1
16
001
3
16
010
1
16
011
3
16
100
1
16
101
3
16
110
1
16
111
3
16
Tabela 2.5: Probabilidades de observação de cada um dos possíveis estados do
indivíduo quântico.
de inicialização, estes indivíduos são inicializados de modo que os valores α
i
e β
i
(onde i = 1, 2, 3, ··· , j e j é o comprimento do indivíduo quântico) sejam iguais
a
1
√
2
. Isto significa que, na geração inicial, todos os genes dos indivíduos terão a
mesma probabilidade de gerarem os estados 0 ou 1.
A atualização da população, conforme indicado no algoritmo da figura 2.5, é
realizada pelo operador q − gate, o qual é definido como a matriz de rotação dada
pela equação 2-23.
U(∆θ
i
) =
cos(∆θ
i
) −sin(∆θ
i
)
sin(∆θ
i
) cos(∆θ
i
)
(2-23)
Esta matriz deve ser usada para multiplicar cada uma das colunas do indivíduo
quântico, ou seja, os valores α
i
e β
i
são tratados como um vetor bidimensional e são
rotacionados usando a matriz especificada. Em outras palavras, considerando-se o
indivíduo quântico Q(t) = {(α
1
, β
1
), (α
2
, β
2
), ··· , (α
i
, β
i
), } (onde i = 1, 2, 3, ··· , j e
j é o comprimento do indivíduo quântico), a atualização deste indivíduo é feita de
acordo com a equação 2-24.
(α
i
, β
i
) = U(∆θ
i
)
α
i
β
i
(2-24)
Onde i = 1, 2, 3, ··· , j. Os valores de ∆θ são definidos através de uma tabela, de
modo que esta matriz de rotação seja capaz de modificar os valores de α
i
e β
i
aumentando as chances de que os indivíduos com as melhores avaliações sejam
observados.
Finalmente, a estrutura B(t) é usada para armazenar os melhores indivíduos
gerados pelo algoritmo ao longo do processo evolutivo. Os últimos dois passos
do algoritmo servem para armazenar os melhores indivíduos gerados na população
atual com os melhores indivíduos criados nas gerações anteriores.
Este algoritmo com representação binária foi usado com sucesso em proble-
mas de otimização combinatorial (Han00, Han02) e detecção de faces (Jang04),
apresentando resultados superiores aos algoritmos genéticos convencionais em ter-
Capítulo 2. Fundamentos
34
iniciar
t ← 0;
inicializa Q(t)
gera P(t) observando estados de Q(t)
avalia P(t)
armazena as melhores soluções de P(t) em B(t)
enquanto não ocorrer condição de parada
t ← t + 1
gera P(t) observando estados de Q(t − 1)
avalia P(t)
atualiza Q(t) usando q-gate
armazena as melhores soluções de B(t − 1) e P(t) em B(t)
armazena a melhor solução b de B(t)
fim
fim
Figura 2.5: Pseudo–código do algoritmo evolutivo com inspiração quântica usando
representação binária.
mos de tempo de convergência e qualidade das soluções encontradas. Uma descri-
ção mais detalhada deste algoritmo pode ser encontrada em (Han00, Han02).
2.6
Algoritmos Culturais
Os algoritmos culturais são um tipo de algoritmo evolutivo que complemen-
tam a metáfora adotada pelos algoritmos genéticos tradicionais. Ao invés de usar
apenas analogias dos conceitos de genética e de seleção natural, os algoritmos cul-
turais são baseados também em teorias sociais e arqueológicas que modelam a evo-
lução cultural. Estas teorias indicam que a evolução cultural pode ser vista como
um processo de herança que ocorre em dois níveis: o nível micro-evolutivo e nível
macro-evolutivo (Reynolds94).
No nível micro-evolutivo, os indivíduos são descritos em termos de carac-
terísticas comportamentais (que podem ser socialmente aceitáveis ou não). Estas
características são passadas de geração para geração usando uma série de opera-
dores. No nível macro-evolutivo, os indivíduos são capazes de gerar "mappas" ou
descrições gerais de suas experiências. Os mappas individuaispodem ser agrupados
através do uso de um conjunto de operadores (genéricos ou específicos para o pro-
blema). Os dois níveis evolutivos compartilham uma ligação através da qual podem
se comunicar.
O objetivo do uso deste modelo em dois níveis é aumentar a velocidade
de convergência do processo de otimização e permitir uma melhor resposta do
algoritmo para uma gama maior de problemas.
Capítulo 2. Fundamentos
35
2.6.1
Componentes de um Algoritmo Cultural
Os algoritmos culturais operam em dois espaços: o espaço de população,
que modela as características comportamentais no nível micro-evolutivo, e o es-
paço de crenças, que modela os mappas de experiência no nível macro-evolutivo
(Reynolds04). Inicialmente, os indivíduos no espaço de população são avaliados
através do uso de uma função de desempenho obj(). Uma função de aceitação acpt()
é então usada para determinar quais indivíduos do espaço de população irão influ-
enciar o espaço de crenças. As características comportamentais destes indivíduos
serão usadas para modificar as crenças existentes dentro do espaço de crenças, atra-
vés de uma função de atualização updt(). Em seguida, as crenças que formam o
espaço de crenças são usadas para influenciar a evolução da população através de
uma função de influência infl(). Finalmente, alguns indivíduos da população são se-
lecionados para a população da geração seguinte através de uma função de seleção
sel(). As figuras 2.6 e 2.7 mostram, respectivamente, o algoritmo cultural em forma
de pseudo–código e de um diagrama da estrutura geral de relacionamento entre os
espaços de população e de crenças.
iniciar
t = 0;
inicializa espaço de crenças B
t
e população P
t
;
repetir
obj(P
t
);
updt(B
t
,acpt(P
t
));
infl(B
t
, P
t
);
t = t + 1;
P
t
⇐sel(P
t−1
);
até que condição de parada alcançada;
fim
Figura 2.6: Pseudo–código do algoritmo cultural.
O espaço de crenças do algoritmo cultural é a região onde o conhecimento é
armazenado. As cinco categorias básicas de conhecimento cultural, de acordo com
(Reynolds04), são:
– Conhecimento Normativo – um conjunto de faixas de valores promissores
dentro do espaço de busca que fornece padrões para os comportamentos
individuaisserem ajustados. O conhecimento normativoguia os indivíduos na
direção das regiões promissoras, caso estes indivíduos já não estejam dentro
destas regiões;
– Conhecimento Situacional – fornece um conjunto de “casos exemplares” que
são úteis para a interpretação de experiências individuais específicas. Este
Capítulo 2. Fundamentos
36
Espaço de
Crenças
Populaçao
sel()
obj()
updt()
acpt()
infl()
Figura 2.7: Diagrama da estrutura geral do algoritmo cultural.
tipo de conhecimento leva os indivíduos na direção dos melhores casos. Nos
algoritmos genéticos convencionais (etambém em várias implementaçõesdos
algoritmos culturais) este conhecimento é representado pelo melhor indivíduo
da população;
– Conhecimento Topográfico – este conhecimento foi originalmente proposto
para melhorar o conhecimento do processo de otimização sobre as estruturas
locais do espaço de busca. O espaço de buscas é dividido em células e
cada célula armazena o melhor indivíduo que está dentro dos seus limites.
O conhecimento topográfico leva os indivíduos na direção dos melhores
indivíduos locais;
– Conhecimento do Domínio – este tipo de conhecimento diz respeito ao
domínio do problema que está sendo otimizado. Em geral, consiste em
hibridizar, com o algoritmo cultural, alguma heurística particular ao problema
que se quer otimizar;
– Conhecimento Histórico – o conhecimento histórico é usado, principalmente,
em sistemas de aprendizado online. Ele é usado para armazenar o melhor
indivíduo encontrado pelo algoritmo cultural antes de uma mudança na
topologia da função de avaliação.
Os algoritmos culturais foram usados com sucesso em diversas áreas
(Rychtyckyj03), como análise de fraudes em seguros de automóveis, precificação
de estratégias para automóveisem um ambiente multi-agente e mineração de dados.
Capítulo 2. Fundamentos
37
2.7
Neuro–Evolução
A neuro-evolução é um modelo híbrido que explora a potencialidade de
duas diferentes áreas inspiradas em processos biológicos: Redes Neurais Artificiais
(RNA) e Algoritmos Genéticos (AG). A idéia básica da neuro-evolução é buscar,
automaticamente, a melhor configuração para uma rede neural usando algoritmos
genéticos. Em outras palavras, a neuro-evolução combina a capacidade de gene-
ralização e aproximação de funções das redes neurais artificiais com um método
eficiente de busca paralela. O objetivo dos algoritmos genéticos é melhorar os al-
goritmos de aprendizado, automatizando, total ou parcialmente, o processo de con-
figuração da rede neural, bem como o processo de treinamento e atualização dos
pesos da mesma.
Para a neuro-evolução funcionar, não é necessário que o sistema satisfaça
nenhuma restrição em particular: o mesmo pode ser contínuo e parcialmente obser-
vável. No que concerne os métodos de aprendizado por neuro-evolução, a única exi-
gência é que os mesmos possam, de alguma forma, ter as suas soluções candidatas
avaliadas relativamente umas às outras. Se o problema é suficientemente regular, de
modo que o mesmo possa ser resolvido, e a representação do fenótipo
1
é suficien-
temente poderosa, então estes métodos de aprendizado serão, muito provavelmente,
capazes de encontrar uma solução.
As abordagens possíveis para os sistemas neuroevolutivosdiferem uma da ou-
tra, basicamente, pelo modo como as mesmas codificam os pesos e a topologia das
redes neurais nos cromossomos. Os cromossomos podem codificar qualquer infor-
mação relevante para a parametrização da rede neural, incluindo os pesos sinápticos,
o número de camadas escondidas, a topologia da rede, a taxa de aprendizado, etc. A
escolha do esquema de codificação tem um papel significativo na formação do es-
paço de buscas, no comportamento do algoritmo de busca e em como os genótipos
devem ser transformados nos fenótipos (representação direta ou indireta).
No modelo descrito em (Gomez97) somente os pesos sinápticos são codifica-
dos, mantendo fixa a topologia e o número de neurônios da rede neural. Já os mo-
delos SANE (Symbolic, Adaptive Neuroevolution) (Moriarty97), NEAT (Neuroevo-
lution of Augmenting Topologies) (Stanley02) e ESP (Enforced Sub–Populations)
(Gomez03) otimizam, além dos pesos sinápticos, a topologia e o número de neurô-
nios da rede neural. Além disso, neste último trabalho, diversas aplicações de
neuro–evolução em problemas de controle são apresentadas, com resultados pro-
missores tanto com relação à capacidade de evoluir corretamente como com relação
1
Em biologia, o genótipo de um organismo vivo é constituído pelos genes e pela configuração
dos mesmos, enquanto que o fenótipo é a expressão física do genótipo como, por exemplo, a cor dos
olhos de uma pessoa.
Capítulo 2. Fundamentos
38
ao desempenho do processo de otimização.
As principais desvantagens destes modelos estão relacionadas ao fato de que,
ao usar modelos evolutivos baseados somente em uma população de indivíduos, o
aprendizado do sistema pode ser muito lento, devido ao fato de que o espaço de bus-
cas é mapeado pontualmente (cada indivíduo representa um único ponto no espaço
de buscas). Isto pode retardar o processo de aprendizado e, conseqüentemente, tor-
nar o aprendizado inviável em alguns sistemas que devem operar em tempo real ou
que necessitem de atualizações online. Além disso, por se tratarem de algoritmos
de busca global, os mesmos são mais ineficientes do que os algoritmos de busca
baseados em gradiente. Finalmente, o número de pesos de uma rede neural cresce
quadraticamente com o número de entradas. Isto implica no uso de indivíduos mais
longos e, conseqüentemente, uma população maior para que a otimização seja bem-
sucedida. O uso mais promissor de algoritmos genéticos para o treinamento de redes
neurais foi feito usando-se os mesmos para encontrar os pesos iniciais da rede neu-
ral e posteriormente, através de um outro algoritmo, realizar o aprendizado propria-
mente dito (Skinner95). Este processo se mostrou eficiente pois o uso de algoritmos
genéticos supre a deficiência que os algoritmos baseados em gradiente apresentam
para fazer uma busca global eficiente (evitando mínimos locais), permitindo que os
algoritmos de aprendizado das redes neurais façam a busca local de forma rápida
(Skinner95).
O próximo capítulo detalha o funcionamento do algoritmo evolutivo com
inspiração quântica e representação real, o seu uso para treinamento de redes neurais
e também mostra como o modelo hipotético da partícula na caixa pode ser usado
para simular este algoritmo.
3
Algoritmos Evolutivos com Inspiração Quântica e Represen-
tação Real – AEIQ–R
Conforme mencionado nos capítulos 1 e 2, os problemas de otimização numé-
rica são um importante assunto de pesquisa e oferecem desafios nas mais diversas
áreas como, por exemplo, otimização de plantas industriais, controle, síntese de fil-
tros digitais, treinamento de redes neurais e diversas outras aplicações. O uso de
algoritmos evolutivos com inspiração quântica nesta classe de problemas de oti-
mização pode, potencialmente, oferecer inúmeras vantagens. Mas, como acontece
com outros tipos de algoritmos evolutivos (sendo os algoritmos genéticos o exem-
plo mais comum), a representação binária não é, necessariamente, a mais adequada
para este tipo de problema, por apresentar algumas particularidades que restringem
a capacidade de otimização do algoritmo. Com o objetivo de contornar este pro-
blema, este trabalho apresenta um modelo com inspiração quântica que usa uma
representação baseada em números reais, sendo, portanto, mais adequada para os
problemas de otimização numérica. Além de oferecer uma representação mais ade-
quada, o modelo apresentado neste trabalho, denominado Algoritmo Evolutivo com
Inspiração Quântica e Representação Real – AEIQ–, tem as seguintes vantagens,
em relação aos algoritmos genéticos tradicionais e ao AEIQ–B:
– Menor tempo para convergência;
– O conhecimento sobre o problema que está sendo otimizado é armazenado
diretamente nos cromossomos quânticos;
– Populações com poucos indivíduos; capacidade de convergir de forma efici-
ente, mesmo com populações com poucos indivíduos.
3.1
O Modelo de Algoritmo Evolutivo com Inspiração Quântica e Representa-
ção Real
O interesse principal deste trabalho é desenvolver um modelo completo,
que permita utilizar uma representação numérica em um algoritmo de otimização
com inspiração na física quântica. Ao contrário do AEIQ–B, descrito na seção
2.5, deseja-se que este algoritmo permita representar uma superposição de estados
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
40
contínuos. Por este motivo, a abordagem usando funções de onda é usada como
inspiração para o desenvolvimento do algoritmo.
É importante frisar que, no caso de algoritmos com inspiração quântica, a
superposição dos estados é apenas simulada, ou seja, o algoritmo é executado em
um computador convencional (daí a denominação "inspiração quântica").
As próximas seções deste capítulo apresentam o algoritmo completo do
modelo proposto neste trabalho, bem como uma descrição detalhada de cada um
dos passos do algoritmo, da representação dos indivíduos com inspiração quântica,
dos operadores evolutivos e outros detalhes importantes referentes ao processo de
otimização.
3.1.1
O Algoritmo Evolutivo com Inspiração Quântica com Representação Real
A figura 3.1 mostra a listagem completa do algoritmo evolutivo com inspira-
ção quântica com representação real (AEIQ–).
iniciar
1. t ← 1
2. Gerar população quântica Q(t) com N indivíduos com G genes
3. enquanto (t <= T)
4. E(t) ← gerar indivíduos clássicos usando indivíduos quânticos
5. se (t=1) então
6. C(t) ← E(t)
7. senão
8. E(t) ← recombinação entre E(t) e C(t)
9. avaliar E(t)
10. C(t) ← K melhores indivíduos de [E(t) + C(t)]
11. fim se
12. Q(t + 1) ← Atualiza Q(t) usando os N melhores indivíduos de C(t)
13. t ← t + 1
14. fim enquanto
fim
Figura 3.1: Listagem completa do algoritmo evolutivo com inspiração quântica
usando representação real.
Este algoritmo será explicado detalhadamente nas subseções a seguir.
3.1.2
A População Quântica
Da mesma forma que o algoritmo genético com inspiração quântica usando
representação binária (AEIQ–B) necessita de uma população de indivíduos que
representem a superposição dos possíveis estados que o indivíduo clássico pode
assumir ao ser observado, o AEIQ– também necessita de uma população com a
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
41
mesma funcionalidade. No entanto, esta representação deve respeitar a condição de
que o conjunto de estados observáveis deve ser contínuo, e não discreto como no
caso do AEIQ–B .
Para se conseguir esse objetivo, a população quântica Q(t), em um instante
t qualquer do processo evolutivo, é formada por um conjunto de N indivíduos
quânticos q
i
(i = 1, 2, 3, .., N). Cada indivíduo quântico q
i
desta população é
formado por G genes g
ij
(j = 1, 2, 3, ..., G) que, por sua vez, são formados por
funções que representam uma densidade de probabilidade. Os indivíduos quânticos
podem ser representados pela equação 3-1.
q
i
→ [g
i1
= p
i1
(x), g
i2
= p
i2
(x), ..., g
iG
= p
iG
(x)] (3-1)
Onde i = 1, 2, 3, ..., N, j = 1, 2, 3, ..., G e as funções p
ij
representam as
funções densidade de probabilidade. Esta função densidade de probabilidade é
usada pelo AEIQ– para gerar os valores para os genes dos indivíduos clássicos.
Em outras palavras, a função p
ij
(x) representa a densidade de probabilidade de se
observar um determinado valor para o gene quântico quando a superposição do
mesmo for colapsada. De fato, a função p
ij
(x) pode ser definida como mostra a
equação 3-2.
p
ij
(x) = ψ
∗
ij
(x)ψ
ij
(x) (3-2)
Onde ψ
ij
(x) representa a função de onda associada ao gene quântico j do
indivíduo i da população quântica e ψ
∗
ij
(x) representa o conjugado complexo desta
mesma função de onda. A função densidade de probabilidade deve respeitar a
propriedade de normalização conforme mostrado na equação 3-3.
ψ
ij
(x)
∗
ψ
ij
(x)dx =
p
ij
(x)dx = 1 (3-3)
É importante ressaltar que a função densidade de probabilidade deve ser inte-
grável na região do domínio dentro do qual as variáveis que se quer otimizar podem
assumir valores. Isto permite calcular a distribuição cumulativa de probabilidade
e assim usar a distribuição de probabilidade para se gerar valores para os genes
clássicos.
Uma das funções mais simples que se pode usar como função densidade de
probabilidade é o pulso quadrado. Esta função pode ser definida pela equação 3-4.
p
ij
(x) =
1
U
ij
−L
ij
se L
ij
≤ x ≤ U
ij
0 caso contrário
(3-4)
Onde L
ij
é o limite inferior e U
ij
o limite superior do intervalo no qual
o gene j do i–ésimo indivíduo quântico pode assumir valores (colapsar) quando
observado. Esta equação respeita a propriedade de normalização mencionada na
equação 3-3. Além disso, corresponde a uma distribuiçãode probabilidade que pode
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
42
ser facilmente utilizada em algoritmos computacionais, já que a mesma corresponde
a uma distribuição uniforme no intervalo [L
ij
, U
ij
].
Um exemplo de umgene quântico formado por um pulso quadrado é mostrado
na figura 3.2. Neste exemplo, os limites L
ij
e U
ij
da função p
ij
(x) estão definidos
como −1 e 1 respectivamente.
0
0.25
0.50
0.75
−2 −1 0 1 2
Figura 3.2: Exemplo de um gene quântico do AEIQ– .
O passo 2 do algoritmo da figura 3.1 consiste, portanto, em gerar um conjunto
de N indivíduos quânticos formados por genes que, por sua vez, são formados por
funções p
ij
(x). Para o caso em que p
ij
(x) é um pulso quadrado, pode-se representar
o gene quântico armazenando-se os valores dos limites inferior e superior para
cada gene, ou armazenando a posição do ponto central do pulso quadrado e a
largura do mesmo. Por exemplo, considerando um indivíduo quântico q
i
formado
por dois pulsos quadrados g
i1
(x) e g
i2
(x), e supondo que estes dois pulsos quadrados
têm uma largura igual a 2 e estão posicionados de tal modo que o seu centro
está localizado nas posições −0.5 e 0.5 respectivamente, o cromossomo quântico
pode ser representado, caso se esteja usando largura e centro como valores para os
genes, por q
i
=
(
µ
i1
= −0.5, µ
i2
= 0.5, σ
i1
= 2, σ
i2
= 2
)
, onde µ
i1
e µ
i2
indicam o
centro e σ
i1
e σ
i2
representam a largura dos dois pulsos quadrados respectivamente.
Obviamente a altura desses pulsos deve ser calculada de modo que a propriedade
de normalização da função densidade de probabilidade formada pela soma desses
pulsos quadrados seja respeitada. Assim, a altura dos pulsos quadrados deve ser tal
que a área total dos mesmos seja igual a 1, e pode ser calculada usando-se a equação
3-4. No exemplo dado, cada pulso terá, portanto, uma altura igual a 0.5.
Ao usar o pulso quadrado, pode-se usar, pelo menos, duas estratégias dife-
rentes de inicialização dos mesmos: na primeira, cria-se pulsos quadrados com uma
largura igual a (U
ij
− L
ij
)/N (onde N é o número de indivíduos quânticos) e com
seus centros distribuídos uniformemente ao longo de todo o domínio das variáveis;
na segunda, cria-se todos os pulsos com o limite inferior e superior igual ao limite
inferior e superior do domínio, respectivamente, sob o qual se deseja otimizar a
função objetivo. Como exemplo para a primeira estratégia, pode-se considerar um
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
43
problema com duas variáveis x e y, ambas no intervalo [−100, 100]. Considerando
também que a função densidade de probabilidade é representada por um pulso qua-
drado e que a população quântica inicial Q(0) tem 5 indivíduos quânticos, pode-se
representar estes indivíduos quânticos que formam a população inicial da seguinte
maneira:
Q(0) =
q
1
= [(µ = −80, σ = 40);(µ = −80, σ = 40)]
q
2
= [(µ = −40, σ = 40);(µ = −40, σ = 40)]
q
3
= [(µ = 0, σ = 40);(µ = 0, σ = 40)]
q
4
= [(µ = 40, σ = 40);(µ = 40, σ = 40)]
q
5
= [(µ = 80, σ = 40);(µ = 80, σ = 40)]
Neste caso, o a posição central de cada pulso foi determinada, de modo que os
mesmos ficassem uniformemente distribuídos pelo domínio de cada variável. Além
disso, a altura de cada pulso deveser tal que a área total de cada um deles seja igual a
1. Assim sendo, a altura de cada pulso neste exemplo deve ser igual a 1/40 = 0.025.
Já no caso da segunda estratégia, os indivíduos quânticos seriam representa-
dos como:
Q(0) =
q
1
= [(µ = 0, σ = 200);(µ = 0, σ = 200)]
q
2
= [(µ = 0, σ = 200);(µ = 0, σ = 200)]
q
3
= [(µ = 0, σ = 200);(µ = 0, σ = 200)]
q
4
= [(µ = 0, σ = 200);(µ = 0, σ = 200)]
q
5
= [(µ = 0, σ = 200);(µ = 0, σ = 200)]
Neste caso, a altura de cada pulso será igual a 1/200 = 0.005.
3.1.3
Observação dos Indivíduos Quânticos
Após a inicialização da população quântica no passo 2, mostrado anterior-
mente, o algoritmo entra no laço principal do processo evolutivo. Este laço será
executado por um determinado número T de gerações e é formado por várias tare-
fas.
O passo 4 é um dos mais importantes do algoritmo. É neste momento que
se executa o processo de observação do estado quântico para se gerar indivíduos
clássicos, ou seja, indivíduos cujos genes são números reais dentro do intervalo
válido do domínio. Para se executar esta observação, usam-se as funções densidade
de probabilidade p
ij
(x) e um gerador uniforme de números aleatórios no intervalo
[0, 1]. Para cada gene é realizada uma observaçãoatravés do seguinte procedimento:
1. Gera-se um número aleatório r no intervalo [0, 1];
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
44
2. Identifica-se o ponto x tal que, dado que P
ij
(x) =
p
ij
(x)dx, x = P
−1
ij
(r);
3. x é o valor observado para o gene j do indivíduo clássico i.
Este processo, a princípio, implica que o número de indivíduos clássicos ge-
rados é igual ao número de indivíduos quânticos. No entanto, isto não é, necessari-
amente, verdade. O número de indivíduos clássicos pode ser igual ou maior ao nú-
mero de indivíduos quânticos, bastando que, ao se gerar os indivíduosclássicos, não
se dê preferência a certos indivíduos quânticos no processo de observação, afinal,
os indivíduos quânticos não são, a princípio, avaliados como os indivíduos clássi-
cos e, portanto, não podem ser considerados melhores ou piores uns que os outros.
Em outras palavras, deve-se garantir que nenhum indivíduo quântico seja preterido
ou privilegiado em relação aos outros no que diz respeito ao número de vezes que
o mesmo será usado para o processo de observação (geração dos indivíduos clás-
sicos). Uma opção, usada neste trabalho, consiste em garantir que o número de
indivíduos clássicos seja um múltiplo inteiro do número de indivíduos quânticos.
Assim, dado que o número de indivíduos quânticos é igual a N e supondo-se que o
número de indivíduos clássicos seja igual a N
c
, define-se N
c
= kN, onde k ∈ −{0}
indica quantos indivíduos clássicos serão gerados por cada indivíduo quântico.
É importante ressaltar que, o número de indivíduos quânticos não deve ser
maior do que o número de indivíduos clássicos (N ≤ N
c
). Esta restrição se deve
ao fato de que os indivíduos clássicos serão usados para atualizar os indivíduos
quânticos posteriormente, o que será explicado em detalhes adiante, na seção 3.1.4.
Como exemplo do processo de geração de indivíduos clássicos, pode-se
considerar uma população quântica formada por dois indivíduos,cada um composto
por 2 genes que usam pulsos quadrados como função densidade de probabilidade.
A configuração destes indivíduos é dada na tabela 3.1 e a representação gráfica dos
mesmos é mostrada na figura 3.3.
Indivíduo Genes
q
1
g
11
= (−µ
11
= 5, σ
11
= 20), g
12
= (µ
12
= 0, σ
12
= 20)
q
2
g
21
= (µ
21
= 5, σ
21
= 20), g
22
= (µ
22
= 5, σ
22
= 20)
Tabela 3.1: Exemplo de indivíduos que formam uma população quântica Q(t) em
uma geração t qualquer.
A função P
ij
(x) (função cumulativa de probabilidade), associada a cada um
dos genes quânticos mostrados anteriormente, pode ser facilmente representada por
equações de retas, já que as funções p
ij
(x) são constantes dentro dos intervalos
onde o valor das mesmas é diferente de 0. A figura 3.4 mostra as funções P
ij
(x)
associadas às funções densidade de probabilidade p
ij
(x) mostradas, anteriormente,
na figura 3.3.
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
45
−20 −15 −10 −5 0 5 10 15 20
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
g
11
−20 −15 −10 −5 0 5 10 15 20
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
g
12
−20 −15 −10 −5 0 5 10 15 20
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
g
21
−20 −15 −10 −5 0 5 10 15 20
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
g
22
Figura 3.3: Genes de uma população quântica usando pulsos quadrados como
função densidade de probabilidade.
De posse das funções P
ij
(x) é possível efetuar a geração dos indivíduos clássi-
cos propriamente dita (passo 4 do algoritmo). Esta observação é feita através de um
processo aleatório, descrito anteriormente. Este processo aleatório é determinado
pela função de onda de cada gene do indivíduo quântico. Assim, para cada gene
j de cada indivíduo quântico i, deve-se gerar um número aleatório r
ij
no intervalo
[0, 1]. Com este número pode-se, então, gerar o valor observado para o gene j de
cada indivíduo clássico. De fato, o cálculo dos indivíduos clássicos é extremamente
simples quando se usa um pulso quadrado para representar os genes que formam o
indivíduo quântico, já que a função cumulativa de probabilidade pode ser represen-
tada pela equação de uma reta, quando se usa pulsos quadrados. Dado o número r
ij
gerado aleatoriamente, e usando-se a equação da reta y(x) = ax+b, pode-se calcular
o valor do gene clássico usando-se a equação 3-5.
x
mj
= r
mj
∗ σ
ij
+
µ
ij
−
σ
ij
2
(3-5)
Onde x
mj
é o j-ésimo gene do m-ésimo indivíduo clássico que se está gerando, r
mj
é o número aleatório sorteado para o gene do indivíduo que está sendo observado, e
µ
ij
e σ
ij
são a posição do centro e a largura do pulso quadrado que está sendo usado
para observar o gene clássico.
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
46
−20 −15 −10 −5 0 5 10 15 20
0
0.2
0.4
0.6
0.8
1
P
11
(x)
−20 −15 −10 −5 0 5 10 15 20
0
0.2
0.4
0.6
0.8
1
P
12
(x)
−20 −15 −10 −5 0 5 10 15 20
0
0.2
0.4
0.6
0.8
1
P
21
(x)
−20 −15 −10 −5 0 5 10 15 20
0
0.2
0.4
0.6
0.8
1
P
22
(x)
Figura 3.4: Funções cumulativas de probabilidade associadas aos genes de uma
população quântica.
Para tornar o processo mais claro, considere o exemplo de uma população
quântica como a mostrada na figura 3.3. Considere também que, para este exemplo,
deseja-se gerar uma população clássica com 4 indivíduos. Deste modo, o número
de indivíduos N
c
= kN → k = N
c
/N é tal que k = 2 e, portanto, cada
indivíduo quântico será usado para gerar dois indivíduos clássicos. Supondo-se
que o gerador de números aleatórios forneceu 2 números diferentes para gerar os
dois genes do primeiro indivíduo clássico – {0.1, 0.8} – e, usando-se a equação 3-5
(x
11
= 0.1∗20+ (−5+ 10) e x
12
= 0.8∗20+ (0+ 10)), o indivíduo clássico observado
é, portanto, {−13, 6}.
Neste ponto existe a possibilidade de se realizar uma operação de recombi-
nação entre os indivíduos da população nova (geração atual) e da população antiga
(geração anterior), equivalente ao passo 8 do algoritmo da figura 3.1. O uso desta
função de recombinação é interessante para permitir o aproveitamento do material
genético já presente na população clássica, melhorando a capacidade do algoritmo
explorar regiões próximas dentro do espaço de busca. Neste trabalho, é usada uma
operação de recombinação similar a que é usada no algoritmo de evolução diferen-
cial, descrito em (Storn95).
Em seguida, os indivíduos da população nova são avaliados (passo 9 do
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
47
algoritmo da figura 3.1) pela função de avaliação que se deseja otimizar. Apesar
de ser possível, não é, provavelmente, conveniente usar operações de mutação nos
indivíduos novos ou antigos, já que os indivíduos quânticos, por si só, já introduzem
um efeito aleatório (exploration) nas populações sendo evoluídas.
Com a nova população clássica gerada, deve-se tomar uma decisão sobre
como substituir os indivíduos de uma eventual população pré-existente (passo 10
do algoritmo da figura 3.1). De fato, a estratégia de substituição dos indivíduos da
população da geração anterior pelos indivíduos criados na nova geração deve ser
usada a todo momento, com exceção da primeira geração, onde não existe uma
população anterior. Existem várias abordagens possíveis para abordar esta etapa do
algoritmo. Estas abordagens podem ser:
1. Substituir todos os indivíduos da população antiga pelos indivíduos da popu-
lação nova (equivalente a ausência de elitismo e steady–state dos algoritmos
genéticos convencionais);
2. Substituir todos os indivíduos da população antiga pelos indivíduos da popu-
lação nova, mas preservando o melhor indivíduo da população nova (equiva-
lente ao elitismo dos algoritmos genéticos tradicionais);
3. Substituir os n piores indivíduos da população antiga pelos n melhores
indivíduos da população nova (equivalente ao steady-state dos algoritmos
genéticos tradicionais;
4. Substituir os n piores indivíduos da população antiga por n indivíduos quais-
quer da população nova.
Cada uma dessas abordagens apresenta vantagens e desvantagens. A opção
1 diminui o tempo de processamento pois elimina a necessidade de ordenação dos
indivíduos da população antiga e da população nova. No entanto, esta abordagem
tende a introduzir muito ruído, já que os indivíduos da população antiga são com-
pletamente substituídos e a avaliação do melhor indivíduo pode piorar significati-
vamente, dependendo do problema que se deseja otimizar. A opção 2 resolve este
problema preservando o indivíduo mais apto da população clássica na população
nova. A opcão 3, apesar de exigir a ordenação dos elementos da população antiga e
da população nova, apresenta a alternativa mais conservadora de busca, sem provo-
car grandes alterações na população que está sendo evoluída. Finalmente, a opção 4
combina o conservadorismo da opção 3, mantendo os indivíduos mais bem avalia-
dos na população em evolução, mas diminuindo o tempo de processamento por não
necessitar avaliar todos os N
c
indivíduos da população nova.
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
48
3.1.4
Atualização da População Quântica
Finalmente, após a geração dos indivíduos clássicos, é necessário atualizar os
indivíduos da população quântica (passo 12 do algoritmo da figura 3.1). Este pro-
cedimento depende, até certo ponto, do tipo de função densidade de probabilidade
que se definiu para usar nos genes quânticos. Em geral, este processo deve:
– Reduzir o espaço de busca da função que se quer otimizar. No AEIQ–
isto é feito reduzindo-se o tamanho da região onde a função densidade de
probabilidade (genes quânticos) tem probabilidade diferente de 0;
– Mapear as regiões mais promissoras do espaço de busca. Isto deve ser feito
aumentando-se a probabilidade de se observar um determinado conjunto de
valores para o gene clássico nas proximidades dos indivíduos mais bem-
sucedidos da população clássica.
Fica claro que, na primeira geração, por não se ter encontrado ainda as regiões
mais promissoras do espaço de busca, o tamanho do domínio para a função que se
quer otimizar deve ser o maior possívelpara que todas as regiões do espaço de busca
sejam mapeadas. Em outras palavras, supondo-se que se deseja otimizar uma função
f(x) no intervalo x ∈ [−100, 100], os genes de todos os indivíduosquânticos devem,
preferencialmente, estar definidos de tal forma que todos os valores possíveis dentro
do intervalo [−100, 100] tenham chance de serem observados. Para o caso em que
a função densidade de probabilidade é um pulso quadrado, estes valores devem
ter, idealmente, a mesma chance de serem observados. Obviamente que, no caso
de se ter informações a priori sobre regiões mais promissoras, pode-se redefinir
as funções densidade de probabilidade de tal modo que os indivíduos quânticos
ofereçam maiores chances de que genes na região mais promissora do espaço de
busca sejam observados com mais freqüência do que em outras regiões.
Supondo-se, então, que uma função densidade de probabilidade com a forma
de pulso quadrado foi usada para os genes quânticos e, para garantir que as duas
condições citadas acima sejam satisfeitas, pode-se considerar o seguinte processo
de atualização dos genes quânticos:
1. Modificar a largura dos pulsos de modo que o espaço de buscas seja reduzido;
2. Modificar a posição dos pulsos de modo que o ponto central dos mesmos
coincida com o valor dos genes de um conjunto de indivíduos da população
clássica.
Mais uma vez é possível adotar diversas estratégias para realizar cada uma das
duas tarefas descritas anteriormente. Para o passo 1, pode-se usar um decaimento
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
49
exponencial da largura dos pulsos quadrados, um decaimento linear ou, ainda, um
processo similar ao usado em algoritmos de estratégia evolutiva chamado “regra do
1/5” (Michalewicz94). A regra do 1/5 faz com que a modificação de largura dos
pulsos seja executada de forma homogênea para todos os genes quânticos e para
todos os indivíduos quânticos. A heurística usada para determinar se a largura do
gene será aumentada ou diminuída é a seguinte (Michalewicz94): se menos de 20%
da população clássica criada na geração atual tiver uma avaliação melhor do que na
geração anterior, a largura do gene é reduzida; se esta taxa for maior do que 20%,
a largura do gene é aumentada; caso a taxa seja exatamente igual a 20%, nenhuma
alteração é feita. Matematicamente, isto pode ser representado pela equação 3-6.
σ
ij
=
σ
ij
· δ ϕ < 1/5
σ
ij
/δ ϕ > 1/5
σ
ij
ϕ = 1/5
(3-6)
Onde σ
ij
é a largura do j-ésimo gene do i-ésimo indivíduo quântico em Q(t),
δ é um valor arbitrário, em geral no intervalo ]0, 1[ e ϕ é a taxa que indica quantos
indivíduos da nova população clássica foram melhores do que os indivíduos da
população clássica na geração anterior.
Esta operação de redimensionamento da largura dos genes da população quân-
tica pode ser feita em cada geração ou pode usar um intervalo de tempo maior (por
exemplo, a cada 5 gerações). Intervalos menores para o redimensionamento ace-
leram o processo de convergência, mas podem levar o algoritmo a ficar preso em
mínimos locais. Por outro lado, intervalos grandes podem evitar que o aprisiona-
mento aconteça, mas podem retardar o processo de otimização.
O argumento para o uso desta regra se baseia na seguinte heurística: se menos
de 20% dos indivíduos da população clássica gerada tiverem melhorado de uma
geração para outra, é provávelque o algoritmo esteja fazendo a busca em uma região
muito grande e, neste caso, pode ser interessante reduzir o espaço de buscas; se mais
de 20% dos indivíduos tiverem melhorado de uma geração para outra, é provável
que o algoritmo esteja fazendo a busca em uma região muito pequena (e portanto
achando, facilmente, indivíduos com avaliações melhores) e o mesmo deve tentar
ampliar a região de busca; a taxa de 20% é considerada ideal e, portanto, nenhuma
alteração é feita caso essa taxa seja medida.
Já no passo 2 da atualização dos genes quânticos, o processo pode ser definido
em termos de quais indivíduos da população clássica serão usados para atualizar
os pulsos da população quântica. Pode-se escolher os indivíduos mais aptos, os
indivíduos menos aptos, um conjunto aleatório de indivíduos ou usar um processo
de roleta para selecionar quais os indivíduos que farão parte do pool de indivíduos
clássicos que serão usados para atualizar os indivíduos quânticos. Após escolher
quais indivíduos serão usados (o número de indivíduos clássicos escolhidos deve
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
50
ser igual ao número de indivíduos quânticos e, portanto, o número de indivíduos
clássicos não pode ser menor do que o número de indivíduos quânticos), o centro
dos pulsos de cada indivíduo quântico deve ser modificado em relação ao valor de
cada gene quântico. Em geral, pode-se usar um cálculo que desloque o centro dos
pulsos na direção do ponto indicado pelo gene do indivíduo clássico. Por exemplo,
supondo-se que o centro do gene quântico na geração t seja dado por µ
ij
(t) e o valor
do gene clássico seja dado por x
ij
, então, pode-se calcular a nova posição do gene
quântico na geração t + 1, através da equação µ
ij
(t + 1) = µ
ij
(t) + λ(x
ij
− µ
ij
), onde
λ indica o percentual que se quer deslocar o centro do gene quântico na direção do
gene clássico.
Todos esses passos do algoritmo devem ser repetidos por um número T de
gerações, de acordo com o que foi mostrado na figura 3.1.
Além do algoritmo definido na figura 3.1, é possível definir um diagrama
que mostra como as partes que constituem o modelo se relacionam entre si. Este
diagrama pode ser visto na figura 3.5.
Indivíduo
Quântico
q
1
(t)
População
Clássica
C(t)
Função de
Avaliação
Gene
Quântico
g
1
Gene
Quântico
g
2
Gene
Quântico
g
n
Operadores
Quânticos
População
Quântica
Q(t)
Indivíduo
Quântico
q
2
(t)
Indivíduo
Quântico
q
n
(t)
Figura 3.5: Diagrama completo do Sistema Evolutivo com Inspiração Quântica
Este diagrama mostra que a populaçãoquântica Q(t) é composta de indivíduos
quânticos que, por sua vez, são formados por genes quânticos. Esta população
quântica é usada para gerar uma população clássica que é avaliada e usada para
modificar os indivíduos da população quântica em um processo iterativo.
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
51
3.2
Usando o Modelo da Partícula na Caixa com o AEIQ-R
Conforme mostrado no capítulo 2, é possível idealizar um modelo de uma
partícula confinada em uma caixa com barreiras de potencial infinito e calcular a
função de onda para este sistema físico. Nesta seção, pretende-se mostrar como é
possível usar este modelo hipotético para simular um gene quântico do AEIQ–.
Para isto, deve-se supor que, para cada gene quântico que se deseja repre-
sentar, deve-se confinar uma partícula (por exemplo, um elétron) em um poço com
barreiras de potencial infinito. Se estas barreiras de potencial infinito forem posicio-
nadas em relação a um referencial qualquer, que permita relacionar a posição desta
barreira com os limites do domínio da função que se quer otimizar, pode-se, então,
usar a função de onda para a posição do elétron como o gene quântico.
Como exemplo,pode-se imaginar que se deseja otimizaruma função qualquer
de duas variáveis x e y e que estas variáveis podem assumir valores no intervalo
[−100, 100]. O AEIQ– que se pretende usar para otimizar esta função tem dois
indivíduos quânticos, cada um com dois genes quânticos. Neste caso, pode-se criar
um conjunto de 4 poços de potencial com um elétron confinado (um para cada gene
quântico, conforme mencionado anteriormente) e com um nível energético tal que o
valor de n (através do qual é possível definir o número de picos da função de onda,
conforme explicado no capítulo 2) seja igual a 1. As barreiras de potencial infinito
devem ser, caso se deseje que as funções densidade de probabilidade associadas
a cada elétron se estendam por todo o domínio do problema na geração inicial,
posicionadas de modo que, em relação a algum referencial pré-definido, as mesmas
estejam na posição −100 e 100. Um exemplo de um elétron preso entre barreiras de
potencial, sendo utilizado como gene quântico, pode ser visto na figura 3.6.
0 25 50 75 100−25−50−75−100
Figura 3.6: Diagrama de um modelo de partícula na caixa para uso no AEIQ–.
Nesta figura pode-se ver, além das barreiras de potencial nas posições −100
e 100, a função densidade de probabilidade associada à função de onda desta partí-
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
52
cula. O fato desta função de onda ser uma senóide faz com que a probabilidade de
que as posições próximas às barreiras de potencial tenham menos chance de serem
observadas ao se medir a posição do elétron. Isto, no entanto, não oferece proble-
mas. É sempre possível definir as barreiras de potencial em posições além das fron-
teiras do domínio, de modo a permitir que as chances das posições mais próximas
às bordas tenham maiores chances de serem observadas, descartando-se os genes
clássicos que venham a ser, eventualmente, observados fora do domínio. Uma outra
opção consiste em criar vários indivíduos quânticos diferentes, posicionando-se as
barreiras de potencial ao longo do domínio (por exemplo, poderia-se usar três indi-
víduos quânticos com as barreiras de potencial nos intervalos [−200, 0], [−100, 100]
e [0, 200]).
Para se gerar os indivíduos clássicos, basta observar a posição do elétron
dentro de cada um dos poços de potencial. Em outras palavras, a observação da
posição do elétron dentro da caixa é equivalente ao processo de observação da
população quântica no AEIQ– descrito na seção anterior. Com os valores obtidos
para a posição do elétron nessas observações, é possível ter indivíduos que possam
ser avaliados da maneira tradicional. Ou seja, é possível, de fato, substituir a parte
com inspiração quântica do algoritmo, por um sistema físico que possa fornecer o
efeito quântico desejado.
Após a geração dos indivíduos clássicos e a avaliação dos mesmos, a atualiza-
ção dos indivíduos quânticos é realizada. Esta atualização consiste, basicamente, em
alterar o posicionamento e a distância entre as barreiras de potencial. Por exemplo,
pode-se imaginar que, após as avaliações dos indivíduos clássicos, identifique-se
que o indivíduo mais bem avaliado tem o gene relativo à variável x igual a 25. Além
disso, define-se que, a cada geração, a largura do gene quântico deva ser igual a
60% da largura na geração anterior (neste caso, portanto, a nova largura será igual a
120). Assim, a nova configuração do gene quântico será aquela na qual as barreiras
de potencial estejam localizadas na posição −35 e 85, como mostrado na figura 3.7.
Portanto, através deste exemplo, verifica-se que é possível usar as proprieda-
des e características de um modelo quântico hipotético como um método de im-
plementar os genes quânticos do AEIQ– . Deseja-se assim tornar mais clara a
relação entre o algoritmo implementado e os elementos da física quântica nos quais
o mesmo algoritmo se inspira.
3.3
Analogia entre o AEIQ-R e os Algoritmos Culturais
Uma importante característica do AEIQ– faz com que o mesmo tenha um
comportamento semelhante ao apresentado pelos algoritmos culturais: as funções
densidade de probabilidade usadas para representar os genes dos indivíduos quânti-
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
53
0 25 50 75 100−25−50−75−100
Figura 3.7: Diagrama do modelo de partícula na caixa para uso no AEIQ– após a
atualização do gene quântico.
cos em Q(t) representam uma forma de conhecimento normativo (esta forma de co-
nhecimento é explicada no capítulo 2). Em outras palavras, este tipo de informação
guarda semelhanças funcionais com o modelo de espaço de crenças dos algoritmos
culturais. As principais diferenças entre os dois algoritmos estão no fato de que, nos
algoritmos culturais, o espaço de crenças é usado para influenciar a avaliação dos
indivíduos da população e influenciar também, indiretamente a geração de novos
indivíduos. Além disso, os indivíduos da população, por sua vez, atuam no espaço
de crenças modificando a sua forma. Já no caso do AEIQ–, a população quântica
(que nesta comparação teria uma funcionalidade equivalente ao espaço de crenças)
gera novos indivíduos para a população clássica, influenciando diretamente a cria-
ção dos novos indivíduos. De maneira análoga, os indivíduos da população clássica
atuam na população quântica, alterando a forma e posição dos genes quânticos.
Além de guiar melhor o processo de otimização, da mesma maneira que nos
algoritmos culturais, esta característica sugere uma importante possibilidade do uso
do AEIQ–: como o conhecimento normativo fica armazenado no indivíduo quân-
tico, este indivíduo pode ser utilizado para tarefas de otimização onde seja impor-
tante alimentar a população inicial com algum tipo de conhecimento. Um exemplo
deste tipo de tarefa de otimização é o aprendizado online. Mais especificamente,
pode-se imaginar o seguinte cenário: supondo que se deseja otimizar a fila de em-
barque de produtos em um porto através do planejamento do uso dos equipamentos
e dos píeres que compõem o porto. Uma primeira otimização é feita e uma solução
é produzida pelo algoritmo. Em seguida, pequenas alterações no cenário do porto
(por exemplo, a quebra de um equipamento) fazem com que uma nova otimização
seja necessária. Obviamente, o fato da mudança no cenário não ter sido drástica,
faz com que a solução encontrada na otimização anterior, apesar de não ser mais a
melhor possível, seja, provavelmente, uma solução acima da média em termos de
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
54
avaliação. Em um algoritmo genético convencional, pode-se usar o melhor (ou os
melhores) indivíduoencontrado para alimentar a população inicial da nova tarefa de
otimização. Com o AEIQ– , pode-se usar, não só os indivíduos da população clás-
sica final, como também os indivíduos quânticos finais (sendo que os pulsos estão,
provavelmente, com a largura próxima de zero e, portanto, devem ser aumentados
antes de reiniciar o processo). Desta forma, a realimentação do processo evolutivo
deixará de ser pontual e passará a englobar toda uma região promissora com res-
peito à solução procurada, de maneira similar aos espaços de crença nos algoritmos
culturais. A principal diferença entre a população quântica e o modelo de espaço
de crenças é que o conhecimento normativo é tratado de maneira probabilística no
primeiro modelo e de maneira uniforme no segundo.
3.4
Modelo Neuro-Evolutivo – Aprendizado Supervisionado
O AEIQ– podeser utilizado para otimizar qualquer tipo de funçãonumérica.
Em geral, os resultados obtidos pelo algoritmo são superiores aos obtidos pelos
algoritmos genéticos clássicos com relação ao tempo de convergência do processo
de otimização (alguns resultados do uso deste modelo para a otimização deste
tipo de problemas são mostrados no capítulo 4). Além de apresentar este melhor
desempenho em diversas situações, o modelo aqui proposto se destaca também nos
processos neuro-evolutivos, devido ao fato de não apresentar problemas de super-
treinamento, não necessitar de um conjunto de dados para validação e por ser capaz
de realizar o aprendizado de forma online, conforme mencionado anteriormente.
O modelo aqui proposto usa o AEIQ– para treinar uma rede neural recor-
rente (FRNN – Fully-Recurrent Neural Network), otimizando os pesos e a topologia
da mesma, de modo a minimizar o erro na saída, aprendendo, assim, a reconhecer
os padrões de entrada fornecidos.
A rede neural recorrente é uma rede que tem realimentação nas suas liga-
ções, da saída dos processadores para as entradas dos mesmo, além das ligações
das entradas para os processadores e dos processadores para as saídas, como nas
redes multilayer perceptron (Haykin99). Este tipo de rede apresenta bons resulta-
dos em problemas de previsão de séries (Haykin99) e em problemas de controle
(Gomez03), pelo fato de que as realimentações introduzem um efeito de memó-
ria nestas redes (Gomez03). A figura 3.8 mostra um diagrama de uma rede neural
recorrente com duas entradas, três processadores e uma saída (os biases não são
mostrados para não sobrecarregar o diagrama).
Outra importante característica de uma redeneural recorrente é que, através da
manipulação dos pesos, em particular ao se zerar alguns deles, é possível redefinir
a topologia da rede neural, e até mesmo reduzir a rede recorrente a uma rede
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
55
Saída
Realimentação
Entradas
Figura 3.8: Diagrama mostrando uma rede neural recorrente. Este diagrama não
mostra as ligações dos biases.
multilayer perceptron. Por exemplo, na rede mostrada na figura 3.8, caso todos os
pesos das entradas para o primeiro neurônio sejam zero e caso todos os pesos de
realimentação sejam iguais a zero, a rede irá se transformar numa rede multilayer
perceptron com duas entradas, dois processadores na camada escondida e um
processador de saída.
O cromossomo clássico usado para fazer o treinamento desta rede contém
todos os pesos necessários para todas as conexões da rede neural que se quer treinar.
O cálculo do número de genes necessários para o cromossomo que representa os
pesos da rede neural pode ser feito através da equação 3-7:
num_genes = N
e
× N
p
+ N
2
p
+ N
p
(3-7)
Onde N
e
indica o número de entradas e N
p
indica o número de processadores. O
primeiro termo desta equação calcula o número de pesos necessários para realizar
as ligações entre as entradas e os processadores. O segundo termo, calcula o número
de pesos necessários para realizar as ligações recorrentes entre os processadores e o
último termo é o número de biases necessários (um para cada processador).
Assim, o indivíduo quântico necessário para gerar os indivíduos clássicos,
deve ser inicializado de modo que a função densidade de probabilidade permita que
os valores dos genes clássicos observados estejam dentro de uma faixa aceitável
como pesos para uma rede neural. Neste trabalho, em todos os estudos de caso
mostrados no capítulo 4, o domínio usado para os pesos está no intervalo [−1, 1].
Cada cromossomo clássico gerado deve, naturalmente, ser avaliado. Esta
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
56
Dados de
Entrada
Rede Neural
Recorrente
Saída
Erro
Algoritmo
Evolutivo
com Inspiração
Quântica
Valor
Esperado
Pesos
Figura 3.9: Modelo de Aprendizado Supervisionado usando o AEIQ–.
avaliação é feita construindo-se a rede neural recorrente com os pesos determinados
pelo indivíduo clássico. Os padrões de entrada são então apresentados e a saída
obtida pela rede é comparada com as saídas desejadas. Esta comparação permite
que se faça o cálculo do erro médio, que pode ser usado como o valor da avaliação
do indivíduo clássico em questão.
Na figura 3.9 é mostrado um diagrama de blocos, que ilustra o funcionamento
do modelo de aprendizado supervisionado para redes neurais recorrentes usando o
AEIQ–.
O número de neurônios e a topologia de uma rede neural são dois importantes
parâmetros na configuração da mesma. Em geral, a topologia deve ser determinada
empiricamente ou pela experiência pessoal do usuário. Quando se usa algoritmos
como o backpropagation (Haykin99) para realizar o treinamento das redes, este
parâmetro pode afetar seriamente o desempenho das mesmas. Processadores em
excesso podem fazer com que a rede memorize o conjunto de treinamento ao invés
de aprender a função que mapeia as entradas nas saídas, resultando em uma má
capacidade de generalização por parte da mesma. Por outro lado, o uso de poucos
processadores pode retardar o processo de aprendizado ou até mesmo inviabilizá-lo.
Para se contornar este problema, o modelo de treinamento usando o AEIQ–
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
57
usa um método de aprendizado descrito em (Gomez03). Neste método, um
operador especial chamado lesion é utilizado durante o processo de aprendizado.
Este operador funciona da seguinte forma: quando a evolução pára de progredir por
um certo número de gerações (este número de gerações η é definido pelo usuário),
a melhor rede encontrada é reavaliada, removendo cada um de seus neurônios, um
por vez. Se a avaliação desta nova rede não piorar mais do que um determinado
nível após a remoção do neurônio i, pode-se considerar que este neurônio não é
importante para a rede e o mesmo é removido. Se nenhum neurônio puder ser
removido, isto pode significar que a rede está precisando de mais neurônios para
aprender corretamente. Sendo assim, mais um neurônio é inserido na rede, com
todos os pesos inicialmente iguais a zero. A inserção de neurônios é feita com peso
igual a zero, para que isso não altere a avaliação dos indivíduos imediatamente
(zerar os pesos da entrada e da saída de um neurônio equivale a remover o neurônio
da rede). Além disso, conforme já foi mencionado anteriormente, dado que a rede
neural recorrente pode se transformar em uma rede com múltiplas camadas, conclui-
se que, além do número de neurônios, o número de camadas da rede neural também
será otimizado automaticamente, de acordo com os pesos que forem encontrados
para determinadas ligações entre os processadores.
Através do uso deste operador e da capacidade do processo de treinamento de
encontrar a topologia mais adequada automaticamente, espera-se que o AEIQ–
seja capaz de otimizar os pesos da rede neural com um tempo computacional muito
menor, já que através deste método de aprendizado, não é necessário realizar o
processo de identificação do número ideal de processadores da rede, o que exige um
esforço computacional relativamente alto em relação ao processo de aprendizado da
rede como um todo.
Finalmente, é importante destacar que, o fato de se usar o AEIQ– como
método de treinamento, torna desnecessário o uso de um conjunto de dados para
validação da rede neural. De acordo com (Bishop95), devido ao fato de as redes
bayesianas usarem distribuições de probabilidade para a determinação dos pesos, a
otimização dos valores ideais para os coeficientes de regularização (os coeficientes
de regularização são usados para minimizar a ocorrência de super-treinamento) da
rede pode ser feita sem a necessidade do uso de conjuntos de validação. Como
o AEIQ– também usa distribuições de probabilidade para encontrar estes pesos,
pode-se concluir que este método de aprendizado também não necessita do uso
destes conjuntos de validação para o aprendizado.
3.5
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
58
Modelo Neuro-Evolutivo – Aprendizado por Reforço
Nesta seção, pretende-se apresentar um modelo de aprendizado por reforço,
onde se usa redes neurais para aprender a realizar tarefas de controle e para as quais
o reforço só é fornecido quando o agente alcança o estado final ou o estado de falha.
Neste caso, o objetivo é treinar a rede para que a mesma seja capaz de levar um
determinado sistema de um estado a outro (por exemplo, equilibrar um pêndulo,
regular a temperatura de um ambiente, entre outros casos).
Ao contrário do modelo de aprendizado supervisionado, neste caso não exis-
tem dados de saída para comparação e cálculo do erro, mas sim um estado (ou um
conjunto de estados) finais que se deseja alcançar. A rede neural então lê o estado
inicial deste sistema, e dá uma resposta na sua saída. Essa resposta é usada pelo
atuador para mudar o estado do sistema que então será usado como nova entrada
para a rede neural. Esse processo é repetido sucessivamente até que a rede neural
consiga levar o sistema ao estado final desejado ou que um certo número de passos
seja executado. O diagrama da figura 3.10 resume o funcionamento deste modelo.
Estado
Inicial
S(0)
Rede
Neural
Recorrente
Novo
Estado
S(t + 1)
Estado
Final
S(T)
AEIQ–
Reforço
Novo estado
para a rede
Pesos
Avaliação
Figura 3.10: Modelo de Aprendizado por Reforço usando o AEIQ–.
Neste diagrama, pode-se observar que, a partir de um estado inicial, a rede
neural é usada para gerar uma saída que indica qual ação o sistema deve tomar. Esta
ação muda o estado corrente do sistema e este novo estado é usado como entrada
Capítulo 3. Algoritmos Evolutivos com Inspiração Quântica e Representação
Real – AEIQ–R
59
para a mesma rede neural. Uma nova saída é gerada e desta forma o processo
é repetido continuamente até que um certo número limite de passos tenha sido
executado ou até que o sistema atinja o estado final desejado. O sistema é então
avaliado pelo AEIQ– (em geral, usando-se o número de passos necessários para
se atingir o objetivo) que, por sua vez, através do processo de evolução, gera um
novo conjunto de pesos para a rede neural. Estes novos pesos são então usados para
repetir o processo de controle novamente.
Este modelo de aprendizado usa o mesmo método de treinamento apresentado
na seção anterior. Assim, o algoritmo de aprendizado também é capaz de definir a
topologia e o número de neurônios necessários para a rede neural.
4
Estudos de Caso
Neste capítulo são apresentados diversos resultados em ensaios realizados
com o AEIQ–. Estes ensaios foram realizados com os objetivosprincipais de com-
parar o desempenho do AEIQ– com outros algoritmos tradicionais de otimização
numérica global e medir o desempenho do AEIQ– aplicado à neuro-evoluçãom
tanto em problemas de aprendizado supervisionado (previsão de séries), quanto
aprendizado por reforço. Além disso, deseja-se medir a influência dos parâmetros
usados no AEIQ– no processo de otimização.
Para o teste de desempenho em otimização de funções e o teste de influência
dos parâmetros, foi selecionado um conjunto de funções de benchmark tradicional-
mente usadas para medir o desempenho de algoritmos de otimização. Este conjunto
de funções foi escolhido também em função da disponibilidade de resultados de
cada um dos algoritmos com os quais se desejou realizar uma comparação de de-
sempenho.
Para o teste do aprendizado supervisionado, um problema de previsão de va-
zões em bacias hidrográficas foi selecionado, para permitir a fácil comparação com
um treinamento supervisionado utilizando o algoritmo mais usado, o backpropaga-
tion (Haykin99).
Finalmente, para o teste do aprendizado por reforço, dois problemas tradicio-
nais da área de controle foram usados. Nestes dois problemas, os resultados obtidos
pelo AEIQ– também são comparados com outros métodos baseados em aprendi-
zado por reforço.
4.1
Otimização de Funções
Os testes de desempenho de otimização foram realizados de modo a permitir a
comparação de resultados do AEIQ– com outros algoritmos de otimização global
tradicionais baseados em evolução. Os algoritmos usados para comparação são:
– Algoritmos Genéticos Tradicionais com Representação Real
– Algoritmos Genéticos com Inspiração Quântica e Representação Binária
– Programação Evolutiva
Capítulo 4. Estudos de Caso
61
– Programação Evolutiva Rápida
– Enxame de Partículas
– Evolução Diferencial
Além dos parâmetros já descritos no capítulo 3, o AEIQ– usado nesta seção
também exige que alguns parâmetros extras sejam configurados. Em particular, para
a tarefa de recombinação, é necessário especificar a taxa na qual a recombinação
ocorre. O AEIQ– implementado usa recombinação aritmética (Michalewicz94)
entre os indivíduos gerados e os indivíduos da população anterior. Este operador
sorteia um número r no intervalo [0, 1] e gera dois indivíduos novos, p
1
e p
2
, a
partir dos genitores p
1
e p
2
de acordo com a equação:
p
1
= rp
1
+ (1 −r)p
2
(4-1)
p
2
= rp
2
+ (1 −r)p
1
(4-2)
Com relação ao processo de substituição dos indivíduos da população clássica
a cada geração (passo 10 do algoritmo descrito no capítulo 3), decidiu-se optar
pela solução mais tradicional de usar uma técnica de steady-state, que consiste em
manter parte da população da geração anterior na nova população gerada. Neste
trabalho, esta técnica elimina os n piores indivíduos e os substitui por n novos
indivíduos gerados. Assim, apesar da população clássica ter um tamanho maior do
que n, apenas n indivíduos são avaliados a cada geração do algoritmo (com exceção
da primeira, onde a população clássica é criada). Este conjunto de indivíduos que é
substituído a cada geração é chamado de gap e será representado pela letra γ.
Finalmente, durante o processo de atualização dos indivíduos quânticos
utilizando-se os indivíduos clássicos (passo 12 do algoritmo descrito no capítulo
3), decidiu-se usar uma taxa de atualização que determina a probabilidade que um
determinado gene quântico tem de ser atualizado pelo gene clássico de referência.
Em outras palavras, deve-se definir a probabilidade de um gene quântico ter sua
posição modificada a cada geração. Por exemplo, uma taxa de 85% indica que, em
média, 15% dos genes de um indivíduo quântico não terão seus centros e larguras
modificados em uma geração. Esta taxa será representada pela letra ζ.
4.1.1
Comparação com Evolução Diferencial e Enxame de Partículas
A comparação com evolução diferencial e enxame de partículas é feita a par-
tir de resultados retirados de (Tasgetiren05) e (Tasgetiren05A), respectivamente. O
objetivo deste teste é analisar o desempenho do AEIQ– quando comparado com
dois importantes algoritmos de otimização global. Os resultados são comparados
executando-se dois experimentos diferentes, com um número total de avaliações
Capítulo 4. Estudos de Caso
62
igual a 10
3
e 10
4
. Os dois experimentos são necessários para permitir a identifi-
cação de métodos que convirjam muito rapidamente para um mínimo local e que
apresentem resultados melhores em poucas gerações, mas que não consigam levar
a otimização adiante quando se aumenta o número de avaliações totais. Cada fun-
ção é testada com 30 variáveis de entrada. As funções usadas para comparação são
descritas no Anexo 1, onde são também apresentados os respectivos gráficos para
as funções com duas variáveis.
O conjunto de parâmetros de configuração do AEIQ– usado nestes testes,
foi selecionado através de alguns experimentos para determinar a melhor configu-
ração, usando-se a função f
1
como avaliação. Em outras palavras, a parametrização
utilizada não é, necessariamente, a melhor parametrização para cada uma das fun-
ções otimizadas. Isto foi feito devido ao fato do conjunto de funções de teste ser
muito extenso. A parametrização do AEIQ– é mostrada na tabela 4.1. Os resulta-
dos obtidos realizando-se um total de 10
3
e 10
4
avaliações são mostrados nas tabelas
4.2 e 4.3 respectivamente. Estas tabelas mostram o erro médio obtido após 25 roda-
das em relação ao mínimo global conhecido da função, o desvio padrão dos erros
obtidos e a diferença percentual entre o valor obtido pelo melhor algoritmo com o
valor obtido pelo segundo melhor algoritmo.
Função Densidade de Probabilidade Pulso Quadrado
Número de Indivíduos Quânticos 5
Número de Indivíduos Clássicos 10
Gap γ 5
Taxa de Recombinação 66%
Intervalo de Atualização da População Quântica 10 gerações
Taxa de Atualização dos Indivíduos Quânticos ζ 16.6%
Tabela 4.1: Configuração do AEIQ– para comparação com evolução diferencial e
enxame de partículas.
Evolução Diferencial Enxame de Partículas AEIQ–
Erro Médio Desvio Padrão Erro Médio Desvio Padrão Erro Médio Desvio Padrão Perc.
f
1
5.440E + 04 7.208E + 03 2.331E + 04 4.886E + 03 2.286E + 04 3.813E + 03 1.95%
f
2
8.592E + 04 1.742E + 04 6.041E + 04 1.203E + 04 3.570E + 04 5.594E + 03 40.90%
f
3
1.009E + 09 2.390E + 08 4.970E + 08 1.517E + 08 3.553E + 08 7.095E + 07 28.51%
f
4
9.984E + 04 1.864E + 04 6.810E + 04 1.521E + 04 4.627E + 04 8.760E + 03 32.06%
f
5
2.395E + 04 2.631E + 03 1.876E + 04 3.792E + 03 2.546E + 04 3.381E + 03 26.32%
f
6
2.600E + 10 9.428E + 09 6.354E + 09 2.852E + 09 5.501E + 09 1.846E + 09 13.42%
f
8
2.121E + 01 6.801E − 02 2.118E + 01 7.595E − 02 2.119E + 01 6.070E − 02 0.03%
f
9
4.045E + 02 2.9405E + 01 3.398E + 02 2.191E + 01 3.072E + 02 1.957E + 01 9.59%
f
10
4.696E + 02 3.163E + 01 3.521E + 02 2.498E + 01 3.039E + 02 5.469E + 01 13.69%
f
11
4.554E + 01 1.282E + 00 4.580E + 01 1.448E + 00 4.186E + 01 1.821E + 00 8.08%
f
12
1.515E + 06 2.018E + 05 1.240E + 06 1.803E + 05 2.691E + 05 9.929E + 04 78.31%
f
13
2.283E + 05 1.061E + 05 1.376E + 04 1.158E + 04 1.192E + 01 5.993E + 01 99.91%
f
14
1.416E + 01 1.483E − 01 1.408E + 01 1.523E − 01 1.389E + 01 1.832E − 01 1.37%
Tabela 4.2: Resultado comparativo entre o AEIQ–, o algoritmo de evolução
diferencial e o de enxame de partículas com 1000 avaliações de função.
Capítulo 4. Estudos de Caso
63
Evolução Diferencial Enxame de Partículas AEIQ–
Erro Médio Desvio Padrão Erro Médio Desvio Padrão Erro Médio Desvio Padrão Perc.
f
1
1.279E + 04 2.628E + 03 1.025E + 03 6.393E + 02 1.232E + 01 7.060E + 00 99.88%
f
2
4.919E + 04 9.254E + 03 1.554E + 04 4.128E + 03 1.097E + 04 1.878E + 03 29.41%
f
3
3.268E + 08 8.828E + 07 7.558E + 07 3.554E + 07 2.456E + 07 5.439E + 06 67.50%
f
4
5.082E + 04 8.594E + 03 2.227E + 04 5.343E + 03 2.052E + 04 3.078E + 03 7.86%
f
5
1.047E + 04 1.345E + 03 1.026E + 04 3.720E + 03 9.323E + 03 1.379E + 03 9.19%
f
6
1.656E + 09 8.344E + 08 2.504E + 07 2.063E + 07 8.364E + 04 8.323E + 04 99.67%
f
8
2.109E + 01 5.957E − 02 2.106E + 01 5.543E −02 2.107E + 01 6.080E − 02 0.04%
f
9
2.761E + 02 2.175E + 01 1.040E + 02 2.698E + 01 1.533E + 02 2.069E + 01 32.18%
f
10
3.349E + 02 2.614E + 01 1.962E + 02 4.852E + 01 1.780E + 02 2.698E + 01 9.27%
f
11
4.285E + 01 9.645E − 01 3.651E + 01 3.835E + 00 3.333E + 01 3.142E + 00 8.70%
f
12
7.100E + 05 1.365E + 05 1.234E + 05 7.206E + 04 7.219E + 04 3.421E + 04 41.50%
f
13
4.005E + 03 1.868E + 03 2.492E + 01 5.348E + 00 1.026E + 01 1.137E + 00 58.82%
f
14
1.390E + 01 1.323E − 01 1.358E + 01 2.131E − 01 1.321E + 01 2.183E − 01 2.77%
Tabela 4.3: Resultado comparativo entre o AEIQ–, o algoritmo de evolução
diferencial e o de enxame de partículas com 10000 avaliações de função.
Os resultados usando 10
3
avaliações foram, em média, 23.2% melhores, en-
quanto que os resultados usando 10
4
avaliações foram, em média, 30.95% melhores
do que os resultados dos outros algoritmos. A tabela 4.4 mostra em termos percen-
tuais, o quão melhor o AEIQ– foi em relação ao segundo melhor algoritmo (a
maioria das comparações foi feita com o PSO), em relação às características das
funções usadas como teste (unimodal, multimodal, separável, não-separável, rota-
cionada e não-rotacionada). É importante destacar que o resultado obtido com rela-
ção a separabilidade das funções não é representativo, já que apenas duas funções
do conjunto de teste são separáveis. De qualquer modo, os resultados são colocados
na tabela para fins de ilustração.
10
3
avaliações 10
4
avaliações
Unimodal 15.42% 42.76%
Multimodal 28.04% 23.53%
Separável 5.77% 33.85%
Não-Separável 26.35% 30.42%
Rotacionada 10.32% 17.64%
Não-Rotacionada 31.22% 39.26%
Tabela 4.4: Tabela que indica a melhora percentual média ao se usar o AEIQ–,
comparando-o com o segundo melhor algoritmo, em relação às características das
funcões de teste.
Estes resultados mostram que, ao se aumentar o número de avaliações per-
mitidas para o algoritmo em funções unimodais, o desempenho do mesmo melhora
consideravelmente. Isto sugere que o algoritmo tem um bom comportamento com
relação à buscas locais. Por outro lado, o algoritmo apresenta uma pequena perda de
desempenho quando as funções são multimodais. Ainda assim, o seu desempenho
é bem superior quando funções multimodais estão sendo otimizadas. Isto reforça a
sua característica de ser um algoritmo de busca global. Comparando-se também os
resultados obtidos com 10
3
e 10
4
avaliações, pode-se notar que, em geral, ao permi-
Capítulo 4. Estudos de Caso
64
tir que o AEIQ– faça mais avaliações, o seu desempenho melhora com relação aos
outros algoritmos. Isto sugere que o AEIQ– usa, quando bem configurado, uma
estratégia de busca mais conservadora, evitando convergências prematuras para mí-
nimos locais. Este comportamento pode ser controlado através da manipulação do
valor que determina de quantas em quantas gerações a largura dos pulsos deve ser
modificada. Os resultados apresentados nesta subseção serão discutidos em mais
detalhes na subseção 4.1.4.
4.1.2
Comparação com o AEIQ-B, Programação Evolutiva Clássica, Programa-
ção Evolutiva Rápida e Algoritmos Genéticos Convencionais
A comparação com a programação evolutiva clássica (Classical Evolutionary
Programming - CEP), programação evolutiva rápida (Fast Evolutionary Program-
ming - FEP) e com o AEIQ–B é feita a partir de resultados tirados de (Yao99) (CEP
e FEP) e (Han04) (AEIQ–B). Os resultados usando algoritmos genéticos foram, por
sua vez, obtidos usando-se o software GACOM, desenvolvido no ICA. Os resulta-
dos são comparados da seguinte forma: para cada função são executados testes com
um número total de avaliações previamente definido e com um número de experi-
mentos igual a 50. Cada função é testada com 30 variáveis de entrada. As funções
usadas para comparação são descritas no anexo 2, onde são também apresentados
os respectivos gráficos para as funções com duas variáveis.
Foram usados dois conjuntos de configurações diferentes para o AEIQ–
neste teste, já que o número de funções de teste é mais reduzido. Estas configurações
são mostradas nas tabelas 4.5 e 4.6 e foram determinadas através de testes. A
principal diferença na parametrização está nas taxas de recombinação e na taxa
de atualização dos indivíduos quânticos. Durante os testes, foi observado que para
funções separáveis, estas duas taxas podem ter valores menores enquanto que, para
funções não-separáveis, estas duas taxas devem ter valores maiores. A configuração
1 foi usada nas funções f
griewank
, f
schwefel
e f
rosenbrock
, enquanto que a configuração
2 foi usada nas funções f
sphere
, f
ackley
, f
rastrigin
. Os resultados da otimização são
mostrados na tabela 4.7.
O algoritmo genético convencional foi executado usando-se os operadores de
mutação uniforme e não-uniforme (Michalewicz94), os operadores de cruzamento
aritmético e uniforme. Os operadores de mutação foram usados com uma taxa de
10%, enquanto que os operadores de cruzamento foram usados com uma taxa de
80%. O método de seleção usado foi a roleta e também foi usado um operador de
steady-state com um gap de 20%.
Os resultados apresentados mostram que o AEIQ– obteve um resultado
nitidamente superior ao dos outros algoritmos utilizados. O resultado foi, em média,
Capítulo 4. Estudos de Caso
65
Função Densidade de Probabilidade Pulso Quadrado
Número de Indivíduos Quânticos 5
Número de Indivíduos Clássicos 100
Gap γ 99
Taxa de Recombinação 66%
Intervalo de Atualização da População Quântica 10 gerações
Taxa de Atualização dos Indivíduos Quânticos ζ 66.6%
Tabela 4.5: Configuração 1 do AEIQ– para comparação com programação evolu-
tiva clássica, programação evolutiva rápida, algoritmos genéticos convencionais e o
algoritmo evolutivo com inspiração quântica usando representação binária.
Função Densidade de Probabilidade Pulso Quadrado
Número de Indivíduos Quânticos 5
Número de Indivíduos Clássicos 100
Gap γ 99
Taxa de Recombinação 3.33%
Intervalo de Atualização da População Quântica 1 geração
Taxa de Atualização dos Indivíduos Quânticos ζ 3.33%
Tabela 4.6: Configuração 2 do AEIQ– para comparação com programação evolu-
tiva clássica, programação evolutiva rápida, algoritmos genéticos convencionais e o
algoritmo evolutivo com inspiração quântica usando representação binária.
Função AEIQ–B FEP CEP GA AEIQ– Perc.
f
sphere
Média 1.8E − 04 5.7 − 04 2.2E − 04 4.71E + 00 1.99E − 06 98.99%
Aval.= 150000 Desvio Padrão 1.3E − 04 1.3E − 04 5.9E − 04 n.d. 9.50E −06 n.d.
f
ackley
Média 2.5E − 03 1.8E − 02 9.2 4.71E − 01 4.26E − 05 98.3%
Aval.= 150000 Desvio Padrão 8.1E − 04 2.1E − 03 2.8 n.d. 1.39E −04 n.d.
f
Griewank
Média 3.6E − 02 1.6E − 02 8.6E − 02 1.03E + 00 9.42E − 06 99.94%
Aval.= 200000 Desvio Padrão 3.2E − 02 2.2E − 02 0.12 n.d. 1.55e − 05 n.d.
f
Rastrigin
Média 3.9E − 02 4.6E − 02 89.0 4.40E − 01 1.65E − 11 100.00%
Aval.= 500000 Desvio Padrão 1.9E − 01 1.2E − 02 23.1 n.d. 3.39E −12 n.d.
f
Schwefel
Média 3.8E − 04 14.987 4652.3 1.77E + 00 8.13E − 09 100.00%
Aval.= 900000 Desvio Padrão 3.0E − 09 52.6 634.5 n.d. 0 n.d.
f
Rosenbrock
Média 11.73 5.06 6.17 14.15E + 00 2.52 78.52%
Aval.= 2000000 Desvio Padrão 18.36 5.87 13.61 n.d. 4.43 n.d.
Tabela 4.7: Resultado comparativo entre o AEIQ– , o AEIQ–B (QEA), progra-
mação evolutiva rápida (FEP), programação evolutiva clássica (CEP) e algoritmos
genéticos convencionais (GA). Os itens com a designação “n.d.” indicamque o dado
não está disponível.
Capítulo 4. Estudos de Caso
66
95.95% melhor do que os resultados observados no segundo melhor algoritmo.
Em particular, na comparação com estes algoritmos, o AEIQ– obteve valores
finais muito mais consistentes, o que pode ser observado comparando-se os desvios
padrões obtidos. Estes resultados são discutidosem mais detalhes na subseção 4.1.4.
4.1.3
Testes de Esforço Computacional
Esta série de experimentos se propõe a identificar a razão na qual o esforço
computacional de otimização pelo AEIQ– cresce quando se aumenta o número
de variáveis do problema que se deseja otimizar. Para se alcançar este objetivo, os
experimentos foram realizados da seguinte maneira:
– Foram selecionadas duas funções diferentes para otimizar: uma unimodal,
com variáveis separáveis (f
sphere
– fácil), e outra multimodal, com variáveis
não-separáveis (f
griewank
– difícil);
– Definiu-se o melhor conjunto de parâmetros para otimizar cada uma das
funções com 10 variáveis;
– Definiu-se um valor-alvo para a função que se quer otimizar;
– Executou-seo algoritmo até alcançar o valor-alvo definido. A execução é feita
20 vezes e o valor médio do número de avaliações necessárias para alcançar
o valor-alvo é calculado;
– Aumentou-se o número de variáveis de modo a se obter resultados para as
funções com 10, 50, 100, 250, 500, 1000 e 2000 variáveis. Para cada um des-
tes testes, calcula-se a média de avaliações necessárias em 20 experimentos
para alcançar o mesmo valor-alvo.
As funções utilizadas para teste foram a f
sphere
e a f
griewank
e o valor alvo utili-
zado para as duas funções foi 1 (o mínimo global destas funções é 0). Estas funções
foram escolhidas, por se tratarem de duas funções com características diferentes.
A primeira é unimodal e separável, enquanto que a segunda é multimodal e não-
separável. A parametrização da função não é alterada ao longo do teste, de modo
a evitar a influência positiva desta parametrização nos testes com maior número de
variáveis. Em outras palavras, uma parametrização mal feita para o problema com
10 variáveis e uma parametrização melhor executada para o problema com 2000
variáveis pode produzir uma distorção no resultado. As figuras 4.1 e 4.2 mostram
os resultados obtidos neste teste.
Estes gráficos sugerem que, para as duas funções apresentadas e para um
conjunto de até 2000 variáveis, o esforço computacional cresce, aproximadamente,
de forma linear com o número de variáveis. Em outras palavras, a complexidade
Capítulo 4. Estudos de Caso
67
0 200 400 600 800 1000 1200 1400 1600 1800 2000
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
x 10
5
Número de Variáveis
Número de Avaliações
Teste de Esforço Computacional
Função Sphere
Figura 4.1: Esforço computacional para otimização da função f
sphere
.
computacional do algoritmo para estas funções e para o número de dimensões
utilizadas é, aproximadamente, O(n). Este teste sugere que o AEIQ– não tenha,
talvez, uma complexidade exponencial na otimização de problemas. Em outras
palavras, a complexidade do AEIQ– não parece ser do tipo O(a
n
). Um exame
analítico desta propriedade e uma extensão dos testes aqui realizados podem ajudar
a determinar se esta propriedade é válida para qualquer função que se deseja
otimizar ou para que grupos de funções esta propriedade é válida.
4.1.4
Discussão dos Resultados
Desempenho
Com relação ao desempenho do AEIQ– quando comparado aos outros
algoritmos, pode-se observar que, no geral, o desempenho do algoritmo apresentado
aqui é superior aos métodos tradicionalmente usados. O primeiro ponto importante
é o fato de que o AEIQ– obteveum desempenho muito superior ao AEIQ–B para a
otimização dos problemas de otimização numérica aqui mostrados. Isto demonstra a
importância de um algoritmo com uma representação específica para números reais.
Capítulo 4. Estudos de Caso
68
0 200 400 600 800 1000 1200 1400 1600 1800 2000
0
0.5
1
1.5
2
2.5
3
x 10
5
Número de Variáveis
Número de Avaliações
Teste de Esforço Computacional
Função Griewank
Figura 4.2: Esforço computacional para otimização da função f
griewank
.
Comparado com o AEIQ–B , o AEIQ– obteve, pelo menos, um resultado duas
ordens de grandeza menor e, em alguns casos, como no teste com a função f
rastrigin
,
o AEIQ– obteve um resultado nove ordens de grandeza menor. Os resultados
na comparação com os dois algoritmos de programação evolutiva também foram
expressivamente melhores para todas as funções examinadas.
Os resultados comparativos com a evolução diferencial e o enxame de partí-
culas também mostraram um desempenho superior do AEIQ–. Apesar de alguns
resultados não terem sido tão expressivamente superiores em alguns dos problemas,
como foram na comparação com o AEIQ–B e com os algoritmos de programação
evolutiva, é importante ressaltar que a otimização das 14 funções foi feita com a
mesma parametrização. Mesmo assim, na maioria dos problemas, o AEIQ– ob-
teve um desempenho maior do 20% quando comparado com os outros algoritmos.
Com relação ao aspecto do desempenho, a questão principal consiste em de-
terminar por qual motivoo AEIQ– tem um bom desempenho em problemas de oti-
mização. Uma das possíveis razões é o fato de que a população quântica, à medida
que o processo evolutivo avança, é capaz de descrever, cada vez melhor, as regiões
mais promissoras do espaço de busca. Deve-se lembrar que as funções densidade
de probabilidade que representam os genes quânticos são reposicionadas durante o
Capítulo 4. Estudos de Caso
69
processo evolutivo na direção dos indivíduos mais promissores da população clás-
sica. Além disso, ao terem suas larguras modificadas, essas funções especializam o
gene quântico, fazendo com que o mesmo convirja, conforme o número de gerações
tende a infinito, para um valor único no espaço de buscas. Este processo funciona de
forma similar às técnicas de hill-climbing, só que de maneira mais sofisticada. Em
conjunto com a população clássica, os indivíduos quânticos podem fornecer valores
aproximados de avaliação para toda uma região do espaço de busca. Obviamente,
este valor aproximado apresenta um erro muito grande quando os genes quânticos
têm uma largura muito grande (por exemplo, no início do processo de otimização,
quando as funções densidade de probabilidade cobrem todo o espaço de busca) e
um erro cada vez menor à medida que a largura dos genes diminui. Este erro tende
a zero à medida que o número de gerações tende a infinito. Em outras palavras,
a população quântica do AEIQ– é capaz de descrever schemata diretamente, ao
contrário dos algoritmos genéticos convencionais, onde os indivíduos representam,
unicamente, pontos no espaço de busca. Os schematarepresentam todo um conjunto
de indivíduos e, deste modo, a avaliação deste conjunto de indivíduos, observados
a partir destes schemata, pode fornecer, não somente a avaliação exata de um ponto
no espaço de busca, como também uma aproximação da avaliação em uma deter-
minada região deste mesmo espaço. Esta habilidade de avaliar regiões do espaço
de busca, ao invés de avaliar apenas pontos, pode permitir que o algoritmo identifi-
que mais rapidamente as regiões promissoras deste espaço, acelerando o tempo de
convergência.
Parametrização
Um outro aspecto importante a ser discutido diz respeito aos parâmetros do
AEIQ– e o impacto dos mesmos no processo evolutivo. Não existe um valor
ou uma fórmula "mágica"para se definir esses valores, sendo a experimentação o
processo mais adequado para se identificar os valores ideais. No entanto, algumas
observações importantes podem ser feitas a respeito dos vários parâmetros que
definem o AEIQ–.
Em primeiro lugar, deve-se ressaltar a importância do parâmetro relacionado
à recombinação dos indivíduos clássicos e à taxa de atualização dos genes quân-
ticos. Em geral, nos testes preliminares, realizados para se determinar a melhor
configuração a ser usada nas comparações, a parametrização mais bem-sucedida se
observou quando as duas taxas eram mantidas iguais. Isto, no entanto, não é um
argumento para descartar a possibilidade de se usar valores diferentes para estes pa-
râmetros (nos testes com evolução diferencial e enxame de partículas foram usados
valores diferentes para estas taxas). De qualquer modo, é importante destacar que
esta parametrização está intimamente relacionada ao grau de epistasia (ou o grau de
Capítulo 4. Estudos de Caso
70
separabilidade das variáveis) da função que se quer otimizar. Funções cujas variá-
veis são separáveis (uma função é separável se, por exemplo, puder ser escrita como
f(x, y) = g(x) + h(y) ou f(x, y) = g(x)h(y) ou, em outras palavras, se a correlação
entre as variáveis for baixa) podem ser otimizadas com taxas de recombinação bai-
xas. Deste modo, poucas variáveis são mudadas em cada recombinação. Por outro
lado, funções cujas variáveis não são separáveis (correlação alta entre as variáveis)
são melhor otimizadas quando se usa taxas de recombinação elevadas. Isto faz com
que diversas variáveis sejam alteradas simultaneamente. A figura 4.3 mostra as cur-
vas de desempenho para uma mesma função (f
griewank
) com variáveis não separáveis
quando se usa uma taxa de recombinação para a população clássica e uma taxa de
atualização ζ para a população quântica iguais a 3.33% e quando se usa taxas iguais
a 66.66%. Já a figura 4.4 mostra a curva de desempenho para uma função (f
sphere
)
com variáveis separáveis usando as mesmas taxas com valores iguais a 3.33% e
66.66%.
0 200 400 600 800 1000 1200
0
1
2
3
4
5
6
x 10
5
Avaliações
Curva de Desempenho
Taxa de Atualização de 3.33%
Taxa de Atualização de 66.66%
Figura 4.3: Gráfico de desempenho para uma função não separável usando taxas de
atualização diferentes.
Tamanho das Populações
Com relação ao número de indivíduos que formam a população quântica,
deve-se levar em consideração que um número muito pequeno pode levar o algo-
ritmo a uma convergência prematura. Isto acontece devido ao fato de que os poucos
pulsos que formam a população acabam convergindo rapidamente para uma região
de mínimo local, ficando presos nesta região indefinidamente. Por outro lado, um
Capítulo 4. Estudos de Caso
71
0 200 400 600 800 1000 1200
−2
0
2
4
6
8
10
12
14
16
x 10
4
Avaliações
Curva de Desempenho
Taxa de Atualização de 66.66%
Taxa de Atualização de 3.33%
Figura 4.4: Gráfico de desempenho para uma função separável usando taxas de
atualização diferentes.
número grande de indivíduos quânticos pode fazer com que a convergência do pro-
cesso de otimização seja mais demorada do que o necessário, já que as funções
densidade de probabilidade vão cobrir grandes regiões do espaço de busca. Um
bom valor inicial para esta parametrização está em torno de 5 indivíduos quânticos
com uma função densidade de probabilidade por gene.
Nos testes realizados para determinação dos melhores parâmetros, observou-
se que o tamanho da população clássica (população observada) não é crítico para
o algoritmo. Poucos indivíduos por geração são, em geral, suficientes para que o
algoritmo convirja. Muitos indivíduos observados não geram uma grande melhoria
na evolução e aumentam, desnecessariamente, o número de avaliações necessárias.
Deste modo, sugere-se que sejam usados poucos indivíduos nesta população.
Com relação ao tamanho γ do gap, sugere-se usar valores no intervalo
[N/2, N − 1], onde N é o total de indivíduos clássicos da população. Aqui também
sugere-se iniciar a parametrização com valores pequenos para o gap de modo a não
aumentar o esforço computacional desnecessariamente.
O valor que indica quantas gerações devem se passar até que a taxa de
melhoria do algoritmo (explicada na regra do 1/5 no capítulo 3) seja verificada é
muito importante para o bom desempenho da otimização. Este valor, no entanto,
também deve ser encontrado através de um processo de experimentação. Cada
função que se deseja otimizar terá um comportamento diferente com relação a
este parâmetro. Valores pequenos para este parâmetro farão com que a largura dos
pulsos seja modificada muito rapidamente. Em alguns casos, isto pode fazer com
Capítulo 4. Estudos de Caso
72
que o tempo que o algoritmo tem para explorar o entorno de um determinado ponto
não seja suficiente para o mesmo encontrar o percentual adequado de mutações
desejadas, acelerando, eventualmente, a convergência para um mínimo local. Por
outro lado, valores grandes para este parâmetro farão com que o algoritmo perca
muito tempo explorando regiões do espaço de busca com o mesmo tamanho.
Finalmente, com relação ao percentual com que a largura do pulso devevariar,
o valor usado em todos os experimentos neste trabalho é igual a 0.9 (ou seja, cada
vez que a largura dos pulsos tem que ser atualiza, eles irão aumentar ou diminuir
10%). Este é um valor empírico determinado experimentalmente mas, nos testes
realizados para determinação dos melhores parâmetros para o algoritmo, observou-
se que valores elevados (acima de 0.85) produzem os melhores resultados.
4.2
Neuro-Evolução
Nesta seção são descritos os resultados obtidos em problemas de otimização
de pesos de uma rede neural recorrente (neuro-evolução). Foram realizados testes
de aprendizado supervisionado, usando-se um problema de previsão de séries
temporais, e testes de aprendizado por reforço, usando-se um conjunto de problemas
benchmark de controle.
4.2.1
Aprendizado Supervisionado
Para testar o AEIQ– em problemas de previsão de séries, usou-se uma base
de dados de vazão média semanal na bacia hidrográfica do Paranaíba. Esta base
contém 8 atributos com informações sobre a vazão média nos 3 dias anteriores à
previsão (3 atributos), a vazão atual (1 atributo), a previsão acumulada de chuvas
para os próximos 7 dias (1 atributo) e as medições realizadas em um posto fluvio-
métrico nos 3 dias anteriores (3 atributos). Os parâmetros usados para a otimização
da rede neural são mostrados na tabela 4.8. A rede inicial utilizada no processo evo-
lutivo com o AEIQ– tem, além das 8 entradas descritas anteriormente, 16 proces-
sadores e uma saída (associada ao processador 1). Os processadores usam a função
sigmóide logística como função de ativação.
O número de genes igual a 400 corresponde ao número necessário para
representar uma rede neural com 128 pesos das 8 entradas para um conjunto de
16 neurônios (8 × 16 = 128), 256 pesos das realimentações (16 × 16 = 256) e 16
biases dos neurônios. O intervalo η é o número de gerações que devem se passar
para verificar se o operador lesion (definido no capítulo 3, e responsávelpor eliminar
neurônios quando o erro não diminuir consideravelmente, ao se tentar retirar este
neurônio) deve ser usado. Neste caso, a cada 10 gerações o algoritmo verifica se
Capítulo 4. Estudos de Caso
73
Número Inicial de Genes 400
Tipo de Rede Recorrente
Número de Entradas da Rede 8
Número Inicial de Processadores 16
Função de Ativação logsig
Número de Indivíduos na População Quântica 5
Número de Indivíduos na População Clássica 10
Gap γ 5
Taxa de recombinação 0.5
Taxa de Atualização dos Genes Quânticos ζ 0.5
Número de Gerações 250
Total de Experimentos 30
Intervalo de Atualização da População Quântica 5 gerações
Número de Gerações η para Verificação
do Número de Neurônios na Camada Escondida 10 gerações
Percentual Máximo de Queda de Desempenho
ao Remover Neurônio 10%
Tabela 4.8: Parâmetros do AEIQ– para aprendizado supervisionado.
deve retirar ou acrescentar um neurônio. Um neurônio é retirado quando o erro não
se degradar mais do que 10% quando um neurônio for retirado.
Os resultados obtidos foram comparados com os resultados de (ICA05). Os
resultados apresentados em (ICA05) foram gerados usando-se uma rede neural mul-
tilayer perceptron com uma camada escondida. Foram avaliadas 21 configurações
diferentes para esta rede (variando o número de neurônios na camada escondida
de 1 a 21) com o objetivo de determinar a melhor configuração para a rede neural.
Para cada uma destas configurações, foram executadas 2500 épocas de treinamento
(totalizando 52500 épocas) e a verificação do erro para validação foi feita a cada
5 épocas. Foram usados 4 anos de dados para treinamento, 1 ano para validação e
1 ano para teste. O melhor resultado obtido em (ICA05) é mostrado na tabela 4.9.
Deve-se observar que os pesos finais, usados para o cálculo do erro com os dados de
teste, são os pesos para os quais o processo de treinamento encontrou o menor erro
de validação. Deste modo, os pesos utilizados não são, necessariamente, os pesos
encontrados na última época do processo de treinamento.
Melhor Topologia 16 neurônios
Erro de Treinamento 12.62%
Erro de Teste 8.66%
Número Total de Épocas 52500
Tabela 4.9: Resultados do Treinamento da Rede Neural usando Backpropagation.
Os resultados com o treinamento realizado pelo AEIQ– são mostrados na
tabela 4.10.
Capítulo 4. Estudos de Caso
74
Melhor Topologia 10 neurônios
Erro de Treinamento 9.26%
Erro de Teste 8.62%
Número Total de Épocas 5000
Tabela 4.10: Resultados do Treinamento da Rede Neural usando o AEIQ– .
É importante ressaltar que, mesmo sem usar um conjunto de validação durante
o treinamento do AEIQ–, os dados referentes ao período usado como validação
no backpropagation não foram utilizados. Como se pode verificar pelos resultados,
a melhor topologia encontrada pelo algoritmo usa 6 neurônios a menos do que
a encontrada usando backpropagation. Os resultados obtidos em termos de erro
percentual são semelhantes mas, com relação ao número de épocas, o resultado
apresentado pelo AEIQ– é muito superior. O número total de épocas usado pelo
AEIQ– é calculado considerando-se que cada avaliação feita pelo algoritmo é uma
época.
Além do resultado em termos de número de épocas, deve-se levarem conside-
ração o resultado em termos do tempo computacional para a execução do algoritmo.
Em testes realizados em um computador Pentium IV 3.0GHz, o tempo médio para
o cálculo de 10000 épocas para o AEIQ– é da ordem de 160 segundos. Para o
backpropagation, o tempo médio é da ordem de 1090 segundos, ou seja, aproxima-
damente 6 vezes maior do que o AEIQ–.
4.2.2
Problemas de Aprendizado por Reforço
Carro na Montanha
O experimento do carro na montanha (Moore91) pode ser descrito da seguinte
forma (Figueiredo03): um carro deve subir até o topo de uma montanha; entretanto,
o carro não possui a potência necessária para vencer a força da gravidade. Dessa
forma, para alcançar o seu objetivo,o carro precisa inicialmente se moverno sentido
contrário ao alvo para poder adicionar a aceleração da gravidade à sua própria
aceleração.
O problema possui duas variáveis de estado contínuas: a posição do carro
x
t
∈ [−1.2, 0.5] e sua velocidade v
t
∈ [−0.07, 0.07]. Além disso, o motor do carro
pode aplicar sobre o mesmo 3 ações discretas: uma impulsão para a esquerda (F =
-1), para a direita (F = 1) e ficar parado (F = 0). A dinâmica do sistema é descrita
pelas equações 4-3 e 4-4.
v
t+1
= min(0.07, max(−0.7, v
t
+ 0.001F
t
− 0.0025 cos(3x
t
))) (4-3)
Capítulo 4. Estudos de Caso
75
x
t+1
= min(0.5, max(−1.2, x
t
+ v
t+1
)) (4-4)
A montanha é definida pela equação 4-5 e a figura 4.5 representa a mesma
graficamente.
f(x) = sin(3x) (4-5)
−1.2 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
Figura 4.5: Representação gráfica do problema do carro na montanha.
Neste problema, a rede neural tem 2 entradas (posição e velocidade do carro).
A configuração inicial utilizada tem 5 neurônios na camada escondida, uma saída
associada ao primeiro processador e usa a função sigmóidecomo função de ativação
dos processadores. Para este problema, os parâmetros listados na tabela 4.11 foram
usados para o AEIQ–.
A função de avaliação consiste na soma do número de passos necessários
para que o carro atinja o topo da montanha à partir de duas posições iniciais
diferentes (x
0
= −1.2 e x
0
= −0.5), com velocidade inicial igual à zero. Após a
fase de aprendizado, foram gerados 1000 casos com posições e velocidades iniciais
aleatórias e o valor médio do número de passos necessários para alcançar o topo
da montanha foi calculado. Para fins de medida de desempenho, este resultado foi
comparado com os modelos Neuro-Fuzzy Hierárquicos (RL-NFHB e RL-NFHP),
Neural Q-Learning, CMAC Q-Learning e FQL, mostrados em (Figueiredo03) na
tabela 4.12. É importante destacar que, nos modelos usados para comparação, o
treinamento foi feito com posições e velocidades iniciais aleatórias e o conjunto de
ações possíveis na saída é diferente (F = −10, −5, −1, 0, 1, 5, 10).
Estes resultados mostram uma pequena melhoria de desempenho em relação
ao número de passos por parte do AEIQ– , mesmo aprendendo a partir de apenas
dois casos iniciais diferentes e tendo apenas 3 ações possíveis como resultado.
Capítulo 4. Estudos de Caso
76
Número Inicial de Genes 40
Tipo de Rede Recorrente
Número de Entradas da Rede 2
Número Inicial de Processadores 5
Função de Ativação logsig
Número de Indivíduos na População Quântica 3
Número de Indivíduos na População Clássica 6
Gap γ 3
Taxa de recombinação 0.5
Taxa de Atualização dos Genes Quânticos ζ 0.5
Número de Gerações 200
Total de Experimentos 5
Intervalo de Atualização da População Quântica 5 gerações
Número de Gerações η para Verificação
do Número de Neurônios na Camada Escondida 2 gerações
Percentual Máximo de Queda de Desempenho
ao Remover Neurônio 10%
Tabela 4.11: Parâmetros do AEIQ– usados para o problema do carro na montanha.
Método Número Médio de Passos na Fase de Teste
Neural Q-Learning 2189
CMAC Q-Learning 85
FQL 61
RL-NFHB 71
RL-NFHP 69
AEIQ– 62
Tabela 4.12: Resultados para o problema do carro na montanha.
Deve-se ressaltar, no entanto, que o AEIQ– e os modelos neuro-fuzzy usam
conceitos diferentes de aprendizado por reforço.
O gráfico da figura 4.6 mostra a variação da velocidade e da posição do carro
para a condição inicial x
0
= −0.5 e v
0
= 0 (pior caso).
Pêndulo Invertido
O problema do pêndulo invertido é um benchmark clássico para sistemas de
controle. O problema consiste em um carro motorizado com um pêndulo apoiado
sobre a sua parte superior. Este pêndulo gira em torno de um eixo fixo no carro
e o veículo desliza sobre um trilho em cima de uma superfície plana. Em geral,
o problema é formulado de modo que o motor do carro esteja sempre acelerado
em algum sentido. Somado ao fato do pêndulo estar invertido, isto faz com que
o problema seja intrinsecamente instável. A figura 4.7 mostra um exemplo de um
carro com um pêndulo invertido.
A formulação matemática do problema (Koza92) é dada pelas equações 4-6,
Capítulo 4. Estudos de Caso
77
0 10 20 30 40 50 60 70 80 90 100
−1
−0.5
0
0.5
Figura 4.6: Variação da velocidade (linha vermelha) e da posição (linha azul) no
problema do carro na montanha.
l
θ
Figura 4.7: Exemplo do problema do pêndulo invertido.
Capítulo 4. Estudos de Caso
78
4-7, 4-8 e 4-9.
¨x =
F − µ
c
sgn
(
˙x
)
+
N
i=1
˜
F
i
M +
N
i=1
˜m
i
(4-6)
¨
θ
i
= −
3
4l
i
¨xcosθ
i
+ g sinθ
i
+
µ
pi
˙
θ
i
m
i
l
i
(4-7)
˜
F
i
= m
i
l
i
˙
θ
2
i
sinθ
i
+
3
4
m
i
cosθ
i
µ
pi
˙
θ
i
m
i
l
i
+ gsinθ
i
(4-8)
˜m
i
= m
i
1 −
3
4
cos
2
θ
i
(4-9)
Onde x é a posição do carro no trilho, θ
i
é o ângulo do pêndulo i (para
problemas onde se usa mais de um pêndulo) com o eixo vertical, F é a força aplicada
ao carro, l
i
é a metade do comprimento do pêndulo, g = 10m/s
2
, M é a massa do
carro, m
i
é a massa do i-ésimo pêndulo sobre o carro, µ
c
é o coeficiente de atrito do
carro com o trilho e µ
pi
é o coeficiente do i-ésimo pêndulo com o eixo no qual ele
está preso.
Os valores usados para o problema são os mesmos utilizados em (Gomez03)
e são mostrados na tabela 4.13.
Parâmetro Valor
x [−2.4, 2.4]m
θ [−0.209, 0.209]rad
F [−10, 10]
l 0.5m
M 1kg
m 0.1kg
Tabela 4.13: Parâmetros usados para o problema do pêndulo invertido.
A parametrização do AEIQ– é mostrada na tabela 4.14.
O valor de 26 para o número inicial de genes é equivalente a uma rede neural
com 5 neurônios na camada escondida. A configuração inicial desta rede, portanto,
tem 4 entradas (posição, velocidade, ângulo do pêndulo com o eixo vertical e
velocidade angular do pêndulo), 5 neurônios na camada escondida e uma saída.
O tempo é discretizado em unidades de 0.01 segundos. Todos os valores
usados como entrada na rede neural são normalizados entre -1 e 1. A saída da rede
é mapeada do domínio [−1, 1] para o domínio [−10, 10]. A tarefa de controlar o
pêndulo é considerada bem-sucedida quando o controle é capaz de manter o pêndulo
equilibrado por mais de 100000 unidades de tempo (1000 segundos). A função de
avaliaçãoconsisteno número de unidades de tempo em que o carro conseguemanter
o pêndulo equilibrado (e, portanto, este é um problema onde se quer maximizar a
função de avaliação). Quando o ângulo do pêndulo é maior do que 0.209 radianos
ou a posição do carro for maior do que os limites definidos para x o algoritmo
Capítulo 4. Estudos de Caso
79
Número Inicial de Genes 50
Tipo de Rede Recorrente
Número de Entradas da Rede 4
Número Inicial de Processadores 5
Função de Ativação logsig
Número de Indivíduos na População Quântica 5
Número de Indivíduos na População Clássica 10
Gap γ 5
Taxa de recombinação 0.5
Taxa de Atualização dos Genes Quânticos ζ 0.5
Número de Gerações 250
Total de Experimentos 5
Intervalo de Atualização da População Quântica 3 gerações
Número de Gerações η para Verificação
do Número de Neurônios na Camada Escondida 10 gerações
Percentual Máximo de Queda de Desempenho
ao Remover Neurônio 10%
Tabela 4.14: Parâmetros do AEIQ– usados para o problema do pêndulo invertido.
considera que o controlador falhou em manter o pêndulo equilibrado. Foram feitos
50 experimentos selecionando-se as condições iniciais para o problema de forma
aleatória dentro das faixas de valores definidas na tabela 4.13. Esta configuração é a
mesma usada em (Gomez03) e, a partir dela, é possível comparar os resultados com
diversos outros métodos. Os métodos usados em (Gomez03) e que são usados aqui
para fins de comparação são:
– Q-Learning com MLP (Q-MLP);
– Sarsa(λ) com Aproximador de Função baseado em Casos (SARSA-CABA);
– Sarsa(λ) com Aproximador de Função CMAC (SARSA-CMAC);
– Neuro–Evolução Simbiótica e Adaptativa (SANE);
– Neuro–Evolução Convencional (CNE);
– Neuro–Evolução de Topologias Crescentes (NEAT);
– Subpopulações Evolutivas (ESP).
Os resultados comparativos são mostrados na tabela 4.15.
Os resultados preliminares mostram a maior eficiência do AEIQ– com
relação aos outros algoritmos. O algoritmo encontrou o melhor indivíduo com 4
neurônios na camada escondida. A figura 4.8 mostra o uso da melhor rede neural
em um teste de generalização (os resultados usados para comparação (Gomez03)
não fazem considerações sobre a capacidade de generalização da rede). Este gráfico
mostra a variação do ângulo do pêndulo para uma posição inicial aleatória, diferente
das posições usadas para o treinamento, para as 10000 primeiras unidades de tempo.
Capítulo 4. Estudos de Caso
80
Método Número Médio de Avaliações
Q-MLP 2056
SARSA-CMAC 540
SARSA-CABA 965
CNE 352
SANE 302
NEAT 743
ESP 289
AEIQ– 210
Tabela 4.15: Parâmetros usados para o problema do pêndulo invertido.
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
−0.25
−0.2
−0.15
−0.1
−0.05
0
0.05
0.1
0.15
0.2
0.25
Tempo
Ângulo
Figura 4.8: Ângulo do pêndulo com relação ao tempo.
A figura 4.9 mostra o mesmo gráfico mas, além do ângulo, também é mos-
trado a velocidade horizontal do carro.
Todos os resultados mostrados nos problemas de benchmark sugerem que o
AEIQ– é um algoritmo com ótimo potencial de uso em vários tipos de aplicações,
oferecendo melhor desempenho em termos do número de avaliações e, em vários
casos, resultados superiores em termos do melhor valor encontrado. No entanto,
ainda existe a necessidade de se realizar diversos experimentos que comprovem o
bom desempenho do algoritmo nos mais diversos tipos de aplicação.
Capítulo 4. Estudos de Caso
81
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
−1.5
−1
−0.5
0
0.5
1
1.5
Tempo
Velocidade
Ângulo
Figura 4.9: Ângulo do pêndulo e velocidade do carro com relação ao tempo.
5
Conclusões e Trabalhos Futuros
Este trabalho apresentou a proposta de um novo modelo de otimização, inspi-
rado nos conceitos da física quântica de superposição de estados e funções de onda,
capaz de oferecer: uma maneira de representar variáveis numéricas de forma direta;
melhor desempenho na otimização; escalabilidade; capacidade de armazenamento
de conhecimento sobre regiões do espaço de busca; e capacidade de aprendizado
compartilhado. Foi apresentado um algoritmo evolutivo com inspiração em física
quântica que usa uma representação para números reais (AEIQ–), em contrapar-
tida ao algoritmo apresentado em (Han04) que usa uma representação binária para
um algoritmo evolutivo com inspiração quântica.
Também foi apresentado um modelo neuro-evolutivo, utilizando o AEIQ–
para o treinamento dos pesos de uma rede neural recorrente. Este modelo
permite, não só o treinamento da rede, como também a otimização da topologia
da mesma, através da variação do número de processadores e da distribuição destes
processadores em camadas, fazendo-se a manipulação dos pesos da rede neural.
Com relação à capacidade de representar variáveis numéricas de forma direta
mostrou-se que, através do uso de funções de onda, foi possível construir uma
analogia contínua ao modelo quântico de estados discretos. Tambémfoi apresentado
um modelo físico hipotético capaz de simular o funcionamento do AEIQ–.
Com relação a maior velocidade de convergência foram apresentados, no ca-
pítulo 4, diversos estudos de caso de otimização numérica. Estes estudos de caso
mostraram a importância de se usar uma representação específica para números re-
ais ao se tratar problemas de otimização numérica. A comparação de resultados
com o AEIQ– na otimização deste tipo de problemas mostrou a melhor capaci-
dade deste algoritmo no tratamento desta classe de problemas. Além disso, quando
comparado a outros algoritmos de otimização, o AEIQ– mostrou ser consistente
na otimização de problemas e mostrou ser capaz de produzir bons resultados em
diversos tipos de funções, com diferentes características.
Para demonstrar a escalabilidade do algoritmo foram mostrados diversos
resultados que mostram a capacidade do algoritmoAEIQ– em otimizar problemas
com até 1000 variáveis sem, no entanto, ter um crescimento exponencial no esforço
computacional necessário para se atingir um determinado resultado. Apesar de não
Capítulo 5. Conclusões e Trabalhos Futuros
83
serem testes conclusivos, estes sugerem a necessidade de uma investigação mais
detalhada já que, um algoritmo com complexidade não-exponencial é interessante
para a otimização de problemas com grande dimensionalidade.
Para explicar o desempenho do algorimo foram apresentadas diversas hipóte-
ses, em particular, a hipótese de que a população quântica se comporta como uma
representação direta dos melhores schemata que representam os melhores indiví-
duos da população. Uma outra hipótese apresentada sugere que o armazenamento
de conhecimento normativo, sob a forma de funções densidade de probabilidade ou
funções de onda pode, indiretamente, determinar valores aproximados de avaliação
para diferentes regiões do espaço de busca e, assim, ser responsável pelo melhor
desempenho do algoritmo. Além disso, este tipo de conhecimento pode, eventu-
almente, ser compartilhado em um sistema de aprendizado multi-agentes e uma
investigação mais detalhada precisa ser realizada nesta área.
Como trabalhos futuros é possível destacar alguns pontos importantes, que
podem trazer novas possibilidades de aplicação para o algoritmo:
– Implementação de outros operadores de algoritmos genéticos clássicos com
o objetivo de tentar melhorar a capacidade de otimização do AEIQ– ;
– Testes de desempenho usando-se outros tipos de função densidade de proba-
bilidade, diferentes de um pulso quadrado (por exemplo, distribuições nor-
mais);
– Testes do modelo neuro-evolutivo para classificação de padrões;
– Novos testes em previsão de séries usando neuro–evolução;
– Novos experimentos em problemas de controle, principalmente com relação
à capacidade de generalização da rede neural encontrada pelo algoritmo;
– Investigação mais detalhada da complexidade computacional do algoritmo
proposto;
– Investigação mais detalhada da capacidade de se usar a população quântica
como uma forma de conhecimento compartilhado.
Além desses testes, também se inclui nos próximos passos a inserção de novas
formas de conhecimento similares aos usados em algoritmos culturais (como por
exemplo o conhecimento topográfico) e a utilização do AEIQ– para a resolução
de outros tipos de problemas, descritos nas seções a seguir.
Capítulo 5. Conclusões e Trabalhos Futuros
84
5.1
Aprendizado Online
Sistemas de aprendizado online são aqueles onde a tarefa que se deseja
aprender ou otimizar é não-estacionária, ou seja, a configuração do problema varia
com o tempo (Saad98). A idéia por trás do uso de algoritmos evolutivos para
aprendizado online é usar as melhores soluções, encontradas até o momento anterior
a esta mudança de configuração do problema, para alimentar a população inicial que
será usada durante o aprendizado da nova configuração do problema. A expectativa
é que as pequenas mudanças provocadas na configuração do problema provoquem
também pequenas mudanças nas soluções consideradas ótimas. O uso do AEIQ–
para aprendizado online tem, deste modo, um potencial promissor: os pulsos que
formam o indivíduo quântico representam, ao invés de apenas pontos no espaço
de busca, toda uma região promissora do espaço de buscas. Ao usar estas regiões
como realimentação para o AEIQ–, espera-se conseguir um aprendizado online
mais eficiente.
Para se experimentar este modelo, propõe-se utilizar um simulador de dinâ-
mica de vôos chamado JSBSim (Jsbsim). O objetivo é fazer com que o sistema seja
capaz de controlar em tempo real um foguete sem estabilizadores verticais, como o
mostrado na figura 5.1.
Figura 5.1: Diagrama de um foguete sem estabilizadores.
Nesta figura, CG é o centro de gravidade do foguete, CP é o centro de pressão
e α e β representam os ângulos de inclinação do foguete com o eixo horizontal.
Neste tipo de foguete existem apenas duas forças atuando sobre o mesmo: o
empuxo gerado pelos propulsores do foguete e o arrasto exercido pela atmosfera
sobre o centro de pressão do foguete. O controle deste tipo de foguete oferece
um grande desafio, devido ao fato da ausência dos estabilizadores verticais fazer
com que o centro de pressão do foguete fique localizado acima do seu centro
Capítulo 5. Conclusões e Trabalhos Futuros
85
de gravidade, tornando o sistema naturalmente instável, de maneira similar ao
problema do pêndulo invertido. No entanto, ao contrário do pêndulo invertido, este
problema oferece um grau de complexidade muito maior pois, à medida que o
foguete se movimenta, diversas variáveis relacionadas à configuração do ambiente
se alteram (como, por exemplo, a densidade do ar, o peso do foguete, etc), exigindo
que o sistema se adapte rapidamente à nova configuração do ambiente.
5.2
Sistemas Multi-Agentes
De acordo com (Franklin96), um agente autônomo é um sistema que está
situado e é parte de um ambiente, e que é capaz de perceber este ambiente e agir
sobre ele no decorrer do tempo em busca de um determinado objetivo. O mesmo
artigo cita quatro pontos chaves que diferenciam um agente de um programa:
– Reação ao ambiente: o agente é capaz de reagir a mudanças no ambiente;
– Autonomia: exerce controle sobre suas próprias ações;
– Orientado a um objetivo: suas ações não são simples respostas ao ambiente;
– Temporalmente contínuo: um agente é um processo em contínua execução.
Quando diversos agentes interagem de forma colaborativa ou competitiva, os
mesmos podem formar um sistema multi-agente. Em geral, os agentes que formam
este tipo de sistema não têm disponíveis todos os dados ou todos os métodos
necessários para se alcançar um objetivo e, deste modo, precisam colaborar entre
si para alcançá-lo. Além disso, existe pouco ou nenhum controle central nestes
sistemas responsávelpor gerenciar os agentes (nos casos de interações competitivas,
não existe nenhum tipo de controle central entre os agentes que estão competindo).
O aprendizado de sistemas multi-agentes constitui um importante aspecto
desta área de pesquisa. O uso do AEIQ– para este aprendizado pode ser feito
baseado no modelo mostrado na figura 5.2.
A idéia é que o indivíduo quântico funcione como um espaço que armazene
conhecimento normativo sobre o aprendizado e que este conhecimento seja com-
partilhado entre os agentes. Além disso, a população clássica é dividida em sub-
populações e cada uma dessas subpopulações evolui o conhecimento de cada um
dos agentes. A expectativa é que o compartilhamento do conhecimento e a sepa-
ração das subpopulações seja capaz de produzir a especialização dos agentes e a
capacidade de cooperação dos mesmos na realização da tarefa.
Para a experimentação deste modelo, propõe-se utilizar um sistema chamado
Robocode (Robocode). Este sistema consiste em uma arena onde um conjunto de
robôs, similares a tanques de combate, simulam uma disputa. Cada vez que um dos
Capítulo 5. Conclusões e Trabalhos Futuros
86
Indivíduos
Quânticos
Subpopulação
Clássica 1
Subpopulação
Clássica 2
Subpopulação
Clássica N
Agente 1 Agente 2 Agente 1
Figura 5.2: Modelo de aprendizado multi-agentes usando o AEIQ– .
robôs é atingido por outro, o mesmo é eliminado da competição. O último robô a
ficar na arena é o vencedor da disputa. O sistema permite a definição de times e os
agentes que formam os times devem colaborar entre si para ganhar a disputa. Além
disso, existem diversos algoritmos disponíveis, desenvolvidos para o controle dos
robôs (inclusivealgoritmos desenvolvidos com o uso de programação genética), que
permitem a comparação dos resultados diretamente.
Referências Bibliográficas
[Back97] Back, T.; Fogel, D. B. ; Michalewicz, Z., editors. Handbook of Evolu-
tionary Computation. Institute of Physics Publishing, 1997. 1.1
[Bishop95] BISHOP, C. M.. Neural Networks for Pattern Recognition. Oxford
University Press, 1995. 3.4
[Blanco01] BLANCO, A.; DELGADO, M. ; PEGALAJAR, M. C.. A real-coded ge-
netic algorithm for training recurrent neural networks. Neural Networks,
14:93–105, 2001. 1.4
[Figueiredo03] FIGUEIREDO, K.. Novos modelos neuro-fuzzy hierárquicos
com aprendizado por reforço para agentes inteligentes. PhD thesis,
Pontifícia Universidade Católica do Rio de Janeiro, 2003. 4.2.2, 4.2.2
[Franklin96] FRANKLIN, S.; GRAESSER, A.. Is it an agent, or just a program?:
A taxonomy for autonomous agents. In: INTELLIGENT AGENTS III.
AGENT THEORIES, ARCHITECTURES AND LANGUAGES (ATAL’96),
volumen 1193, Berlin, Germany, 1996. Springer-Verlag. 5.2
[Gillespie73] GILLESPIE, D. T.. A Quantum Mechanics Primer – An Elemen-
tary Introduction to the FormalTheory of Non-Relativistic Quantum Me-
chanics. Open University Set Book, 1973. 2.1.2, 2.1.3, 2.1.3
[Gomez97] GOMEZ, F.; MIIKKULAINEN, R.. Incremental evolution of complex
general behavior. In: ADAPTIVE BEHAVIOR, volumen 5, p. 317–342,
1997. 2.7
[Gomez03] GOMEZ, F.. Robust Non–Linear Control through Neuroevolution.
PhD thesis, The University of Texas at Austin, 2003. 2.7, 3.4, 3.4, 4.2.2,
4.2.2, 4.2.2
[Green01] GREEN, N. J. B.. Quantum Mechanics 1: Foundations. Oxford
Science Publications, 2001. 2.1.1, 2.1.2, 2.1.2, 2.1.2, 2.1.3, 2.2
[Han00] HAN, K.; KIM, J.. Genetic quantum algorithm and its application to
combinatorial optimization problem. In: PROCEEDINGS OF THE 2000
Referências Bibliográficas
88
CONGRESS ON EVOLUTIONARY COMPUTATION, volumen 2, p. 1354–
1360, 2000. 2.5, 2.5, 2.5
[Han02] HAN, K.; KIM, J.. Quantum-inspired evolutionary algorithm for a
class of combinatorial optimization. In: IEEE TRANS. EVOL. COMPUT.
6, p. 580–593, 2002. 1.1, 2.5
[Han04] HAN, K.-H.; KIM, J.-H.. Quantum–inspired evolutionary algorithms
with a new termination criterion, h
e
gate and two–phase scheme. IEEE
Transactions on Evolutionary Computation, 8, 2004. 1.1, 4.1.2, 5
[Haykin99] HAYKIN, S.. Neural Networks – A Comprehensive Foundation.
Prentice Hall, 2 edition, 1999. 1.1, 3.4, 3.4, 4
[ICA05] Projeto de previsão de vazões, 2005. 4.2.1
[Ilonen03] ILONEN, J.; KAMARAINEN, J.-K. ; LAMPINEN, J.. Differential
evolution training algorithm for feed-forward neural networks. Neural
Processing Letters, 17:93–105, 2003. 1.1
[Jang04] JANG, J.-S.; HAN, K.-H. ; KIM, J.-H.. Face detection using quantum-
inspired evolutionaryalgorithm. In: PROCEEDINGS OF CONGRESS ON
EVOLUTIONARY COMPUTATION, volumen 2, p. 2100–2106, 2004. 2.5
[Jsbsim] http://jsbsim.sourceforge.net/. 5.1
[Knuth73] KNUTH, D. E.. Searching and Sorting. Addison Wesley, 1973. 2.4
[Koza92] Koza, J. R., editor. Genetic Programming: on the programming of
computers by means of natural selection. MIT Press, 1992. 1.1, 4.2.2
[Michalewicz94] MICHALEWICZ, Z.. Genetic algorithms + data structures =
evolution programs (2nd, extended ed.). Springer-Verlag New York, Inc.,
New York, NY, USA, 1994. 1.1, 3.1.4, 4.1, 4.1.2
[Moore91] MOORE, A. W.. Variable resolution dynamic program-
ming:efficiently learning action maps in multivariate real-valued state-
spaces. In: PROCEEDINGS OF THE EIGHTH INTERNATIONAL CONFE-
RENCE ON MACHINE LEARNING, p. 333–337, 1991. 4.2.2
[Moore95] MOORE, M.; NARAYANAN, A.. Quantum-inspired computing,
1995. 2.4, 2.4, 2.4, 2.4
[Moriarty97] MORIARTY, D. E.. Symbiotic Evolution of Neural Networks in
Sequential Decision Tasks. PhD thesis, The University of Texas at Austin,
1997. 2.7
Referências Bibliográficas
89
[Narayanan96] NARAYANAN, A.; MOORE, M.. Quantum inspired genetic
algorithms. In: INTERNATIONAL CONFERENCE ON EVOLUTIONARY
COMPUTATION, p. 61–66, 1996. 1.1
[Planck01] PLANCK, M.. On the law of distribution of energy in the normal
spectrum. Annalen der Physik, 4:553, 1901. 2.1.1
[Reynolds94] REYNOLDS, R. G.. An introduction to cultural algorithms. In:
PROCEEDINGS OF THE 3RD ANNUAL CONFERENCE ON EVOLUTIO-
NARY PROGRAMMING, p. 131–139, 1994. 1.1, 2.6
[Reynolds04] REYNOLDS, R. G.; PENG, B.. Cultural algorithms: Modeling of
how cultures learn to solve problems. In: PROCEEDINGS OF THE 18TH
IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL
INTELLIGENCE (ICTAI 2004), 2004. 1.1, 2.6.1, 2.6.1
[Rieffel00] RIEFFEL, E.; POLAK, W.. An introduction to quantum computing
for non–physicists, 2000. 2.3
[Robocode] http://robocode.sourceforge.net/. 5.2
[Rychtyckyj03] RYCHTYCKYJ, N.; OSTROWSKI, D.; SCHLEIS, G. ; REY-
NOLDS, R. G.. Using cultural algorithms in industry. In: PROCEEDINGS
OF IEEE SWARM INTELLIGENCE SYMPOSIUM, Indianapolis, Indiana,
2003. IEEE Press. 2.6.1
[Saad98] Saad, D., editor. On–line Learning in Neural Networks. Cambridge
University Press, 1998. 5.1
[Skinner95] SKINNER, A.; BROUGHTON, J. Q.. Neural networks in computa-
tional material science: Training algorithms. Modelling and Simulation in
Material and Engineering, 3:371–390, 1995. 2.7
[Spector04] SPECTOR, L.. Automatic Quantum Computer Programming – A
Genetic Programming Approach. Springer, 2004. 2.3
[Stanley02] STANLEY, K. O.; MIIKKULAINEN, R.. Evolving neural networks
through augmenting topologies. In: EVOLUTIONARY COMPUTATION,
2002. 2.7
[Storn95] STORN, R.; PRICE, K.. Differential evolution - a simple and efficient
adaptive scheme for global optimization over continuous spaces. Techni-
cal Report TR-95-012, 1995. 1.1, 3.1.3
Referências Bibliográficas
90
[Tasgetiren05] TASGETIREN, M. F.; GENCYLMAZ, G.; LIANG, Y.-C. ; EKER, I..
A differential evolution algorithm for continuous function optimization.
In: CONGRESS ON EVOLUTIONARY COMPUTATION, 2005. 4.1.1
[Tasgetiren05A] TASGETIREN, M. F.; GENCYLMAZ, G.; LIANG, Y.-C. ; EKER,
I.. Global optimization of continuous functions using particle swarm
optimization. In: CONGRESS ON EVOLUTIONARY COMPUTATION,
2005. 4.1.1
[Yao99] YAO, X.; LIU, Y. ; LIN, G. M.. Evolutionary programming made faster.
IEEE Trans. Evolutionary Computation, 3:82–102, 1999. 1.1, 4.1.2
[Yao99a] YAO, X.. Evolving artificial neural networks. In: PROCEEDINGS OF
THE IEEE, volumen 87, p. 1423–1447, 1999. 1.1
Anexo 1
Funções para Medida de Desempenho
Função Sphere Deslocada
f
1
(x) =
D
i=1
z
2
i
+ bias
1
z = x −o, x = [x
1
, x
2
, ··· , x
D
]
−100
−50
0
50
100
−100
−50
0
50
100
−2
0
2
4
6
x 10
4
Função f
1
Figura 5.3: Mapa 3D da função f
1
.
– Unimodal
– Deslocamento da origem
– Separável
– Escalonável
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
1
(x
∗
) = bias
1
= −450
Referências Bibliográficas
92
Função Schwefel Deslocada
f
2
(x) =
D
i=1
i
j=1
z
j
2
+ bias
2
z = x −o, x = [x
1
, x
2
, ··· , x
D
]
−100
−50
0
50
100
−100
−50
0
50
100
−2
0
2
4
6
8
x 10
4
Função f
2
Figura 5.4: Mapa 3D da função f
2
.
– Unimodal
– Deslocamento da origem
– Não-separável
– Escalonável
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
2
(x
∗
) = bias
2
= −450
Referências Bibliográficas
93
Função Elíptica Rotacionada e Deslocada
f
3
(x) =
D
i=1
10
6
i−1
D−1
z
2
i
+ bias
3
z = (x − o) · M, x = [x
1
, x
2
, ··· , x
D
]
−100
−50
0
50
100
−100
−50
0
50
100
0
1
2
3
4
x 10
10
Função f
3
Figura 5.5: Mapa 3D da função f
3
.
– Unimodal
– Deslocamento da origem
– Rotacionada
– Não-separável
– Escalonável
– M é uma matriz ortogonal qualquer pré-definida
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
3
(x
∗
) = bias
3
= −450
Referências Bibliográficas
94
Função Schwefel 1.2 Deslocada com Ruído
f
4
(x) =
D
i=1
i
j=1
z
j
2
∗
(
1 + 0.4|N(0, 1)|
)
+ bias
4
z = x −o, x = [x
1
, x
2
, ··· , x
D
]
−100
−50
0
0
50
100
0
1
2
3
4
5
x 10
4
Função f
4
Figura 5.6: Mapa 3D da função f
4
.
– Unimodal
– Deslocamento da origem
– Não-separável
– Escalonável
– Ruído aleatório
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
4
(x
∗
) = bias
4
= −450
Referências Bibliográficas
95
Função Schwefel 2.6
f
5
(x) = max{|A
i
x − B
i
|} + bias
5
A é uma matriz DxD, onde a
ij
são números inteiros aleatórios no intervalo
[−500, 500], det(A) 0, A
i
é a i-ésima linha de A.
B
i
= A
i
∗ o, o é um vetor Dx1, onde o
i
é um número aletório no intervalo
[−100, 100].
−200
−100
0
100
200
−200
−100
0
100
200
−1
0
1
2
3
4
x 10
4
Função f
5
Figura 5.7: Mapa 3D da função f
5
.
– Unimodal
– Não-separável
– Escalonável
– Ótimo global na borda do domínio
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
5
(x
∗
) = bias
5
= −310
Referências Bibliográficas
96
Função Rosenbrock Deslocada
f
6
(x) =
D
i=1
100
z
2
i
− z
i+1
2
+
(
z
i
− 1
)
2
+ bias
6
z = x − o + 1, x = [x
1
, x
2
, ··· , x
D
]
78
79
80
81
82
−52
−50
−48
−46
0
1000
2000
3000
4000
Função f
6
Figura 5.8: Mapa 3D da função f
6
.
– Multi-modal
– Deslocamento da origem
– Não-separável
– Escalonável
– Esta função tem um vale muito estreito entre o mínimo local e o mínimo
global
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
6
(x
∗
) = bias
6
= 390
Referências Bibliográficas
97
Função Ackley Rotacionada e Deslocada
f
8
(x) = −20 exp
−0.2
1
D
D
i=1
z
2
i
− exp
1
D
D
i=1
cos
(
2πz
i
)
+ 20 + e + bias
8
z = (x − o) · M, x = [x
1
, x
2
, ··· , x
D
]
M é uma matriz de transformação linear com um número de condição igual a
100.
−40
−20
0
20
40
−40
−20
0
20
40
−140
−135
−130
−125
−120
−115
Função f
8
Figura 5.9: Mapa 3D da função f
8
.
– Multi-modal
– Deslocamento da origem
– Rotacionada
– Não-separável
– Escalonável
– Ótimo global na borda do domínio
– x ∈ [−32, 32]
D
, Ótimo global: x
∗
= o, F
8
(x
∗
) = bias
8
= −140
Referências Bibliográficas
98
Função Rastrigin Deslocada
f
9
(x) =
D
i=1
z
2
i
− 10cos
(
2πz
i
)
+ 10
+ bias
9
z = x −o, x = [x
1
, x
2
, ··· , x
D
]
−5
0
5
−5
0
5
−350
−300
−250
−200
Função f
9
Figura 5.10: Mapa 3D da função f
9
.
– Multi-modal
– Deslocamento da origem
– Separável
– Escalonável
– Grande número de ótimos locais
– x ∈ [−5, 5]
D
, Ótimo global: x
∗
= o, F
9
(x
∗
) = bias
9
= −330
Referências Bibliográficas
99
Função Rastrigin Deslocada e Rotacionada
f
10
(x) =
D
i=1
z
2
i
− 10cos
(
2πz
i
)
+ 10
+ bias
10
, [−5, 5]
D
z = (x − o) · M, x = [x
1
, x
2
, ··· , x
D
]
M é uma matriz de transformação linear com um número de condição igual a
2.
−5
0
5
−5
0
5
−400
−300
−200
−100
0
100
Função f
10
Figura 5.11: Mapa 3D da função f
10
.
– Multi-modal
– Deslocamento da origem
– Rotacionada
– Não-Separável
– Escalonável
– Grande número de ótimos locais
– x ∈ [−5, 5]
D
, Ótimo global: x
∗
= o, F
10
(x
∗
) = bias
10
= −330
Referências Bibliográficas
100
Função Weierstrass Deslocada e Rotacionada
f
11
(x) =
D
i=1
20
k=0
0.5
k
cos
2π3
k
(
z
i
+ 0.5
)
− D
20
k=0
0.5
k
cos
2π3
k
· 0.5
+ bias
11
z = (x − o) · M, x = [x
1
, x
2
, ··· , x
D
]
M é uma matriz de transformação linear com um número de condição igual a
5.
−0.5
0
0.5
−0.5
0
0.5
90
92
94
96
98
Função f
11
Figura 5.12: Mapa 3D da função f
11
.
– Multi-modal
– Deslocamento da origem
– Rotacionada
– Não-Separável
– Escalonável
– Função contínua mas diferenciável apenas em alguns pontos
– x ∈ [−0.5, 0.5]
D
, Ótimo global: x
∗
= o, F
11
(x
∗
) = bias
11
= 90
Referências Bibliográficas
101
Função Schwefel 2.13
f
12
(x) =
D
i=1
(
A
i
− B
i
(
x
))
2
+ bias
12
A
i
=
D
j=1
a
ij
sinα
j
+ b
ij
cosα
j
B
i
(x) =
D
j=1
a
ij
sin x
j
+ b
ij
cos x
j
, i = 1, ··· , D
−4
−2
0
2
4
−4
−2
0
2
4
−2
0
2
4
6
x 10
4
Função f
12
Figura 5.13: Mapa 3D da função f
12
.
– Multi-modal
– Deslocamento da origem
– Não-Separável
– Escalonável
– x ∈ [−π, π]
D
, Ótimo global: x
∗
= α, F
12
(x
∗
) = bias
12
= −460
Referências Bibliográficas
102
Função Griewank e Rosenbrock Expandida e Deslocada
Considerando-se as funções:
F8 - Função Griewank : F8(x) =
D
i=1
x
2
i
4000
−
D
i=1
cos
x
i
√
I
+ 1
F2 - Função Rosenbrock : F2(x) =
D−1
i=1
100
x
2
i
− x
i+1
2
+
(
x
i
− 1
)
2
f
13
(x) = F8(F2(z
1
, z
2
)) + F8(F2(z
2
, z
3
)) + ··· + F8(F2(z
D−1
, z
D
))+
F8(F2(z
D
, z
1
)) + bias
13
z = x − o + 1, x = [x
1
, x
2
, ··· , x
D
]
−2
−1.5
−1
−2
−1.5
−1
−130
−120
−110
−100
−90
−80
Função f
13
Figura 5.14: Mapa 3D da função f
13
.
– Multi-modal
– Deslocamento da origem
– Não-separável
– Escalonável
– x ∈ [−5, 5]
D
, Ótimo global: x
∗
= o, F
13
(x
∗
) = bias
13
= −130
Referências Bibliográficas
103
Função F6 Expandida, Rotacionada e Deslocada
Considerando-se a função:
F(x, y) = 0.5 +
sin
2
x
2
+ y
2
− 0.5
1 + 0.001
x
2
+ y
2
2
f
14
(x) = F(z1, z2) + F(z
2
, z
3
) + ··· + F(z
D−1
, z
d
) + F(z
D
, z
1
) + bias
14
z = (x − o) · M, x = [x
1
, x
2
, ··· , x
D
]
M é uma matriz de transformação linear com um número de condição igual a
5.
−90
−80
−70
−60
−50
−40
−30
−20
−10
0
−300
−299.5
−299
−298.5
−298
Função f
14
Figura 5.15: Mapa 3D da função f
14
.
– Multi-modal
– Deslocamento da origem
– Não-separável
– Escalonável
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= o, F
14
(x
∗
) = bias
14
= −300
Anexo 2
Funções para Medida de Desempenho
Função Sphere
f
sphere
(x) =
D
i=1
x
2
i
−100
−50
0
50
100
−100
−50
0
50
100
0
0.5
1
1.5
2
x 10
4
Função f
30
Figura 5.16: Mapa 3D da função f
sphere
.
– Unimodal
– x ∈ [−100, 100]
D
, Ótimo global: x
∗
= 0, f
sphere
(x
∗
) = 0
Referências Bibliográficas
105
Função Ackley
f
ackley
(x) = −20 exp
−0.2
1
D
D
i=1
x
2
i
− exp
1
D
D
i=1
cos
(
2πx
i
)
+ 20 + e
−40
−20
0
20
40
−40
−20
0
20
40
0
5
10
15
20
Função f
31
Figura 5.17: Mapa 3D da função f
ackley
.
– Multi-modal
– x ∈ [−32, 32]
D
, Ótimo global: x
∗
= 0, f
ackley
(x
∗
) = 0
Referências Bibliográficas
106
Função Griewank
f
griewank
(x) =
1
4000
D
i=1
x
2
i
−
D
i=1
cos
x
i
√
i
+ 1
−10
−5
0
5
10
−10
−5
0
5
10
0
0.5
1
1.5
2
2.5
Função f
32
Figura 5.18: Mapa 3D da função f
griewank
.
– Multi-modal
– x ∈ [−600, 600]
D
, Ótimo global: x
∗
= 0, f
griewank
(x
∗
) = 0
Referências Bibliográficas
107
Função Rastrigin
f
rastrigin
(x) =
D
i=1
x
2
i
− 10 cos
(
2πx
i
)
+ 10
−10
−5
0
5
10
−10
−5
0
5
10
0
20
40
60
80
100
Função f
33
Figura 5.19: Mapa 3D da função f
rastrigin
.
– Multi-modal
– x ∈ [−5.12, 5.12]
D
, Ótimo global: x
∗
= 0, f
rastrigin
(x
∗
) = 0
Referências Bibliográficas
108
Função Schwefel 2.26
f
schwefel
(x) = −
D
i=1
x
i
sin
|x
i
|
+ 12569.5
−500
0
500
−500
0
500
−1000
−500
0
500
1000
Função f
34
Figura 5.20: Mapa 3D da função f
schwefel
.
– Multi-modal
– x ∈ [−500, 500]
D
, Ótimo global: x
∗
= 420.9687, f
schwefel
(x
∗
) = 0
Referências Bibliográficas
109
Função Rosenbrock
f
rosenbrock
(x) =
D−1
i=1
100
x
i+1
− x
2
i
2
+
(
x
i
− 1
)
2
−40
−20
0
20
40
−40
−20
0
20
40
0
2
4
6
8
10
x 10
7
Função f
35
Figura 5.21: Mapa 3D da função f
rosenbrock
.
– Multi-modal
– x ∈ [−30, 30]
D
, Ótimo global: x
∗
= 1, f
rosenbrock
(x
∗
) = 0
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
