Embed Size (px)
Citation preview
UNIVERSIDADE DO ESTADO DE SANTA CATARINA - UDESC
CENTRO DE EDUCAÇÃO SUPERIOR DO ALTO VALE DO ITAJAI - CEAVI
DEPARTAMENTO DE SISTEMAS DE INFORMAÇÃO
RICARDO GRUNITZKI
SIMULADOR WEB PARA O ALGORITMO DE OTIMIZAÇÃO GLOBAL PARTICLE
SWARM OPTIMIZATION COM PESO INERCIAL VARIANDO EM FUNÇÃO DA
DIVERSIDADE
IBIRAMA - SC
2012
RICARDO GRUNITZKI
SIMULADORWEB PARA O ALGORITMO DE OTIMIZAÇÃO GLOBAL PARTICLE
SWARM OPTIMIZATION COM PESO INERCIAL VARIANDO EM FUNÇÃO DA
DIVERSIDADE
Trabalho de Conclusão apresentado ao Curso de
Sistemas de Informação, da Universidade do
Estado de Santa Catarina, como requisito parcial
para obtenção do grau de bacharel em Sistemas de
Informação.
Orientador: Fernando dos Santos
Coorientador: Jarbas Cleber Ferrari
IBIRAMA - SC
2012
RICARDO GRUNITZKI
SIMULADOR WEB PARA O ALGORITMO DE OTIMIZAÇÃO GLOBAL PARTICLE
SWARM OPTIMIZATION COM PESO INERCIAL VARIANDO EM FUNÇÃO DA
DIVERSIDADE
Trabalho de Conclusão de Curso apresentado como requisito parcial para obtenção do grau de
Bacharel em Sistemas de Informação oferecido pelo Centro de Educação Superior do Alto Vale
do Itajaí da UDESC.
Banca Examinadora
Orientador: _______________________________________________________________
MSc. Fernando dos Santos
Universidade do Estado de Santa Catarina UDESC - CEAVI
Membro: ________________________________________________________________
Dr. Milton Roberto Heinen
Universidade do Estado de Santa Catarina UDESC - CCT
Membro: _______________________________________________________________
MSc. Osmar Oliveira Braz Junior
Universidade do Estado de Santa Catarina UDESC - CEAVI
Ibirama, SC - (29/11/2012).
Dedico este trabalho aos meus pais, Marco e
Claudete, e a todos os amigos que compreenderam a
minha ausência neste período.
“Não é o que você faz, mas quanto amor
você dedica ao que faz que realmente importa.”
-Madre Tereza de Calcutá
RESUMO
GRUNITZKI, Ricardo. Simulador web para o algoritmo de otimização global particle
swarm optimization com peso inercial variando em função da diversidade. 2012. 79 f.
Trabalho de Conclusão de Curso (Bacharel em Sistemas de Informação – Área: Inteligência
Artificial) - Universidade do Estado de Santa Catarina. Ibirama, 2012.
Este trabalho apresenta a especificação e o detalhamento da implementação de um
simulador web para o algoritmo de otimização global Particle Swarm Optimization.Com o
simulador pode-se acompanhar o comportamento do algoritmo nos principais problemas de
otimização ou a partir de uma função qualquer definida pelo usuário. Além de possibilitar a
alteração dos parâmetros do algoritmo, este trabalho ainda propõe uma estratégia para a
variação do peso inercial, a qual varia em função da diversidade entre todas as partículas do
enxame. A performance desta função foi avaliada através de 9 funções teste implementadas no
simulador e comparadas com os resultados obtidos pela implementação de Jiao, Lian e Gu
(2008). Os resultados obtidos comprovaram que a função diversidade apresenta eficiência
significativamente superior à proposta comparada.
Palavras-chave: Particle Swarm Optimization, Função Teste, Função Diversidade,
Simulador, Aplicativo Web.
ABSTRACT
GRUNITZKI, Ricardo. Web simulator for the global optimization algorithm particle
swarm optimization with inertia weight varying by diversity. 2012. 79 f. Work Course
Conclusion (Bacharel em Sistemas de Informação – Area: Artificial Intelligence) -
Universidade do Estado de Santa Catarina. Ibirama, 2012.
This work presents the specification and implementation of a web simulator for the
global optimization algorithm Particle Swarm Optimization. With the simulator it is possible to
track the behavior of the algorithm in the main optimization problems or from any function
defined by the user. The simulator allows the user to change the parameters of the algorithm.
This work also proposes an alternative strategy for varying the inertial weight according to the
diversity of all particles in the swarm. The performance of this function was evaluated by nine
fitness functions implemented on the simulator and compared to the results obtained by the
implementation of Jiao, and Gu Lian (2008). The results proved that the diversity function has
significantly higher efficiency compared to the proposal.
Key-words: Particle Swarm Optimization, Fitness Function, Diversity Function,
Simulator, Web Application.
LISTA DE ABREVIATURAS
AJAX Asynchronous Javascript and XML
API Application programming interface
CHAP Common Hybrid Agent Platform
CSRF Cross site request forgery
DWR Direct Web Remoting
GWT Google web toolkit
HTML Hypertext markup language
JSF Java Server Faces
JRE Java runtime environment
PSO Particle Swarm Optimization
XHTML Extensible hypertext markup language
LISTA DE SÍMBOLOS
pbest Melhor posição conhecida pela partícula.
gbest Melhor posição conhecida pelo enxame.
lbest Melhor posição conhecida por uma vizinhança topológica.
LISTA DE FIGURAS
Figura 1 - Representação gráfica da função generalizada de Rastrigin em três
dimensões ................................................................................................. 24
Figura 2 - Representação gráfica da função esférica em três dimensões ....................... 24
Figura 3 - Representação gráfica da função de Griewank em três dimensões ............... 25
Figura 4 - Representação gráfica da função de Rosenbrock em três dimensões ............ 26
Figura 5 - Representação gráfica da função de Schewefel em três dimensões .............. 26
Figura 6 - Representação gráfica da função de Ackley em três dimensões ................... 27
Figura 7 - Representação gráfica da função ruidosa em três dimensões. (a) com ruído
igual a 0, (b) com ruído igual a 1 ............................................................... 28
Figura 8 - Representação gráfica da função de Levy em três dimensões ...................... 28
Figura 9 - Representação gráfica da função f(x,y)=sen(x)*cos(y)*50+50 .................... 30
Figura 10 - DWR alterando o conteúdo de uma lista após chamada Javascript............. 31
Figura 11 - Applet PsoVis minimizando a função de Rosenbrock. ............................... 34
Figura 12 - Particle Swarm Optimization Visualization maximizando um espaço
tridimensional ........................................................................................... 35
Figura 13 - Curva de variação do peso inercial para a função diversidade .................... 40
Figura 14 - Fluxo de funcionamento do PSO com a função densidade ......................... 41
Figura 15 - Diagrama de casos de uso do sistema ........................................................ 44
Figura 16 - Protótipo visual para o sistema PSOView.................................................. 48
Figura 17 - Diagrama de pacotes de classe .................................................................. 49
Figura 18 - Diagrama de classes do pacote function ............................................... 50
Figura 19 - Pacote de classes MathEvaluator ........................................................ 51
Figura 20 - Pacotes de classes core ........................................................................... 52
Figura 21 - Pacote de classes bean ............................................................................. 53
Figura 22 - Diagrama de sequencia para UC02 Visualizar Otimização ........................ 54
Figura 23 - Diagrama de sequência para UC03 Criar Função ...................................... 56
Figura 24 - Estrutura do Projeto PSOView .................................................................. 57
Figura 25- PSOView minimizando a função de Ackley ............................................... 64
Figura 26 - Tela inicial do simulador PSOView .......................................................... 65
Figura 27 - Lista de funções teste implementadas ........................................................ 65
Figura 28 - Campo de entrada para a função matemática ............................................. 66
Figura 29 - Simulador desenhando a função durante a inserção da expressão .............. 66
Figura 30 - Parâmetros de configuração da função teste .............................................. 67
Figura 31 - Possíveis configurações para o gráfico da função. (a) sem parâmetros, (b)
com todos os parâmetros ........................................................................... 67
Figura 32 - Parâmetros de configuração do PSO.......................................................... 68
Figura 33 - Fim do processo de otimização ................................................................. 68
Figura 34 - Dialogo de resultados da otimização ......................................................... 69
Figura 35 - Opções de idioma disponíveis no PSOView .............................................. 69
Figura 36 - Aplicação no Idioma inglês dos EUA ........................................................ 70
LISTA DE QUADROS
Quadro 1 - Operadores disponíveis na biblioteca Math Evaluator ............................... 32
Quadro 2 - Exemplo de utilização da biblioteca Math Evaluator ................................. 33
Quadro 3 - Comparação entre PSOVis e PSO Visualization ........................................ 36
Quadro 4 - Regras de negócio da aplicação ................................................................ 42
Quadro 5 - Requisitos Funcionais da aplicação............................................................ 43
Quadro 6 - Requisitos não Funcionais da aplicação ..................................................... 44
Quadro 7 - UC01 - Alterar idioma ............................................................................... 45
Quadro 8 - UC02 - Visualizar otimização .................................................................... 46
Quadro 9 - UC03 - Criar função .................................................................................. 47
Quadro 10 - Método construtor da classe PSO ............................................................ 59
Quadro 11 - Implementação da função diversidade. .................................................... 60
Quadro 12 - Código fonte de classe PSOViewAjax ..................................................... 61
Quadro 13 - Código fonte da função fncOnLoad() ................................................. 61
Quadro 14 - Código fonte do método drawVisualization()................................ 62
Quadro 15- Código fonte do método updateDataPoints ..................................... 63
Quadro 16 - Código fonte do método drawParticles ........................................... 64
Quadro 17 - Comparação entre PSOView e trabalhos correlatos ................................. 73
LISTA DE TABELAS
Tabela 1 - Comparativo entre a função de Jiao, Lian e Gu (2008) e a função diversidade
............................................................................................................................ 71
SUMÁRIO
1 INTRODUÇÃO .................................................................................................. 15
1.1 PROBLEMA ..................................................................................................... 16
1.2 OBJETIVOS ...................................................................................................... 16
1.2.1 Objetivo geral .............................................................................................. 17
1.2.2 Objetivos específicos .................................................................................... 17
1.3 JUSTIFICATIVA .............................................................................................. 17
1.4 METODOLOGIA .............................................................................................. 18
1.5 PRINCIPAIS CONTRIBUIÇÕES...................................................................... 19
1.6 ESTRUTURA DO TRABALHO ....................................................................... 19
2 FUNDAMENTAÇÃO TEÓRICA ..................................................................... 20
2.1 SWARM INTELLIGENCE ............................................................................... 20
2.2 PARTICLE SWARM OPTIMIZATION ............................................................ 20
2.2.1 Peso inercial ................................................................................................. 21
2.2.2 Distribuição de números randômicos ......................................................... 22
2.3 FUNÇÕES TESTE ............................................................................................ 23
2.3.1 Função Generalizada de Rastrigin ............................................................. 23
2.3.2 Função Esférica ........................................................................................... 24
2.3.3 Função de Griewank ................................................................................... 24
2.3.4 Função de Rosenbrock ................................................................................ 25
2.3.5 Função de Schewefel.................................................................................... 26
2.3.6 Função de Ackley ........................................................................................ 27
2.3.7 Função Ruidosa ........................................................................................... 27
2.3.8 Função de Levy ............................................................................................ 28
2.4 PRIMEFACES................................................................................................... 29
2.5 GRAPH3D ........................................................................................................ 29
2.6 DIRECT WEB REMOTING .............................................................................. 30
2.7 MATH EVALUATOR ...................................................................................... 32
2.8 TRABALHOS CORRELATOS ......................................................................... 33
2.8.1 PsoVis ........................................................................................................... 33
2.8.2 Particle Swarm Optimization Visualization ............................................... 35
2.8.3 Comparativo ................................................................................................ 36
3 DESENVOLVIMENTO..................................................................................... 39
3.1 FUNÇÃO DIVERSIDADE ................................................................................ 39
3.2 ESPECIFICAÇÃO............................................................................................. 41
3.2.1 Requisitos ..................................................................................................... 42
3.2.2 Casos de Uso ................................................................................................ 44
3.2.3 Protótipos Visuais ........................................................................................ 47
3.2.4 Diagrama de Classes.................................................................................... 48
3.2.5 Diagramas de Sequência ............................................................................. 53
3.3 IMPLEMENTAÇÃO ......................................................................................... 56
3.3.1 Técnicas Utilizadas ...................................................................................... 56
3.3.2 Estrutura do Projeto ................................................................................... 57
3.3.3 Implementação do PSO ............................................................................... 58
3.3.4 Implementação Javascript .......................................................................... 60
3.4 OPERACIONALIDADE ................................................................................... 64
3.5 COMPARATIVO DAS ESTRATÉGIAS........................................................... 70
4 CONCLUSÕES .................................................................................................. 72
4.1 DIFICULDADES ENCONTRADAS ................................................................. 74
4.2 EXTENSÕES .................................................................................................... 74
REFÊRENCIAS ........................................................................................................ 76
15
1 INTRODUÇÃO
Na natureza existem várias espécies que se beneficiam da sociabilidade, pois a vida
em grupos sociais aumenta a probabilidade de acasalamento, facilita a caça e coleta de
alimentos, reduz a probabilidade de ataque por predadores e permite a divisão do trabalho
(ZUBEN; ATTUX, 2008). Baseados nas vantagens que certos indivíduos possuem ao viver
coletivamente no mundo real, pesquisadores desenvolveram ferramentas computacionais
para a solução de problemas e estratégias de coordenação e controle, ao que chamam de
Swarm Intelligence.
Técnicas de inteligência computacional com fundamentos baseados no Swarm
Intelligence realizam uma analogia à natureza, onde indivíduos integrantes de uma
população interagem localmente uns com os outros e também com seu meio ambiente. Tal
princípio fundamenta o algoritmo otimização por enxame de partículas (particle swarm
optimization ou PSO).
Proposto inicialmente por Eberhart e Kennedy em 1995, o algoritmo de otimização
por enxame de partículas é um algoritmo estocástico com características heurísticas de busca
randômica, que relaciona conceitos da psicologia social e inteligência computacional
(KENNEDY; EBERHART, 2001).
Desde então, muitos esforços tem sido investidos na obtenção do melhor
entendimento das propriedades de convergência do PSO. Esses estudos concentram-se
principalmente na compreensão dos parâmetros básicos de controle do PSO, como os
coeficientes de aceleração, peso inercial, tamanho de população, topologia de vizinhança e
distribuição da população inicial (VAN DEN BERGH; ENGELBRECHT; 2006).
Em função de o algoritmo apresentar um conceito simples, sendo de fácil
implementação e possuindo poucos parâmetros de ajuste, têm sido encontradas inúmeras
aplicações para o PSO. Dentre essas aplicações destacam-se a resolução de problemas com
restrições, problemas de minimização ou maximização, problemas com múltiplas soluções,
monitoramento dinâmico e otimização de pesos e arquiteturas de redes neurais. (SHI, 2004).
A necessidade de aprimoramento das estratégias de algoritmos estocásticos com
heurísticas inteligentes está baseada no melhor conhecimento a respeito dos processos, o que
provoca o surgimento de modelos fenomenológicos cada vez mais complexos, assim como
do acesso às informações, que devem ser correlacionadas e interpretadas. Nesse contexto a
utilização de algoritmos determinísticos é inviabilizada, diante de sua dificuldade quanto à
16
convergência a uma solução global e dependência dos critérios de inicialização (THOMAS;
REED, 2009).
As propostas de aprimoramento nos algoritmos estocásticos devem ser
experimentadas para validar seus benefícios. Neste sentido, é importante o uso de algum
simulador, onde seja possível avaliar o comportamento em diferentes situações. Ferramentas
de simulação consistem na utilização de técnicas matemáticas em computadores, com o
intuito de imitar o funcionamento de praticamente qualquer tipo de operação do mundo real.
Permitem a experimentação da realidade através de um modelo e assim, avaliar como as
variáveis irão se comportar no sistema idealizado (HARRELL et al.; 2002).
O simulador proposto neste trabalho visa oferecer um ambiente de testes flexível,
acessível, independente de plataforma e recursos adicionais para avaliar o comportamento e
desempenho do PSO nos mais diversos problemas de minimização. O trabalho ainda propõe
uma estratégia alternativa para o peso inercial, chamada função diversidade.
1.1 PROBLEMA
Existem hoje publicados um número crescente de artigos que apresentam estratégias
de implementação do PSO, expondo sempre suas vantagens em termos de eficiência e
confiabilidade na resolução de funções teste e ou problemas específicos relacionados à
ciência da computação e engenharia. Diante deste quadro, observa-se uma grande
dificuldade em visualizar os efeitos destas estratégias no processo de otimização do PSO. As
ferramentas de simulação existentes não são flexíveis o bastante e ainda requerem a
instalação de recursos adicionais. Cabe argumentar se realmente existe uma maneira de
representar o funcionamento do PSO nas mais diversas situações, e sem a necessidade de
instalar recursos adicionais.
1.2 OBJETIVOS
Neste tópico serão definidos o objetivo geral e específicos que se deseja atingir com
este trabalho.
17
1.2.1 Objetivo geral
O objetivo geral deste trabalho é possibilitar a visualização do processo de
otimização do algoritmo inteligente Particle Swarm Optimization nos mais diversos
problemas de otimização.
1.2.2 Objetivos específicos
a) Desenvolver uma aplicação web, que permita visualizar o processo de otimização do
algoritmo sem a necessidade de instalar recursos adicionais no cliente.
b) Desenvolver uma estrutura flexível para a construção de funções teste.
c) Propor um algoritmo que, não seja uma estratégia genérica ótima, mas que se mostre
eficiente e confiável para a maioria dos casos de otimização em que ele possa ser
aplicado.
1.3 JUSTIFICATIVA
Diante da evolução científica e do melhor conhecimento a respeito dos processos
assim como do acesso das informações, os pesquisadores tem construído modelos cada vez
mais eficientes em representar um fenômeno, uma cinética de reação ou uma relação
mesmo que complexa entre variáveis. O contra ponto dessa evolução é que estes modelos
apresentam uma complexidade cada vez maior, já que cada vez mais eles buscam
aproximar-se do modelo real. Esta alta complexidade inviabiliza a utilização de algoritmos
determinísticos deixando espaço para os algoritmos estocásticos, que se utilizam de
heurísticas cada vez mais inteligentes nas suas estratégias de resolução destes modelos.
Mesmo quando estes modelos fenomenológicos são descartados, estratégias de correlação
de dados como as redes neurais podem também apresentar dificuldades quanto à
determinação de sua melhor arquitetura e estimação dos seus pesos sinápticos ótimos.
Um simulador web, independente de plataforma ou recursos adicionais, possibilita
ao usuário a análise visual do comportamento do algoritmo, permitindo melhor observar a
influência dos parâmetros do PSO durante o processo de otimização. Além de servir como
uma ferramenta didática no aprendizado de inteligência de enxames. Já a flexibilidade na
construção de funções teste permite avaliar a eficiência do processo de busca nos mais
distintos espaços solução.
18
1.4 METODOLOGIA
A utilização de métodos quantitativos está associada à investigação experimental ou
quase experimental o que pressupõe a observação de fenômenos, a formulação de hipóteses
explicativas desses mesmos fenômenos, o controle de variáveis, a seleção aleatória dos
sujeitos de investigação (amostragem), a verificação ou rejeição das hipóteses mediante uma
escolha rigorosa de dados, posteriormente sujeitos a uma análise estatística e uma utilização
de modelos matemáticos para testar essas mesmas hipóteses (SIMÕES; PAIVA, 2004).
No processo de investigação do desempenho de um algoritmo de otimização,como o
PSO, é necessário realizar uma avaliação sistemática da influência das variáveis e
possibilidades de heurísticas do mesmo, no sentido de que a abordagem seja mais completa
possível. Segundo Resendeet al. (1995), recentemente a necessidade de uma ciência
empírica rigorosa dos algoritmos vem sendo enfatizada, testando heurísticas através de uma
grande variedade de problemas, realizando uma avaliação estatística do desempenho desses
algoritmos, definindo em quais circunstâncias ela será relativamente boa ou ruim.
Quando se realiza uma pesquisa exploratória o objetivo é familiarizar-se com um
assunto ainda pouco conhecido, tornando-se apto a construir hipóteses. Como qualquer
exploração, a pesquisa exploratória depende da intuição do explorador. Por ser um tipo de
pesquisa muito específica, quase sempre ela assume a forma de um estudo de caso (GIL,
2008).
Um procedimento eficiente na realização de uma pesquisa exploratória é a busca
sistematizada de informações sobre o tema na forma de uma consulta a fontes bibliográfica,
esta permite melhor redefinir os limites de exploração da pesquisa, formular e abortar
hipóteses.
Com o intuito de conhecer melhor as heurísticas já implementadas, bem como as
alterações que se mostraram potencialmente eficientes na solução dos mais diversos
problemas, foi realizada uma pesquisa bibliográfica de caráter exploratório que se
concentrou nas publicações que fazem uso do peso inercial, nas suas mais diversas formas,
como também heurísticas que fazem uma melhor avaliação da geração inicial dos números
randômicos, relevantes em si tratando de um algoritmo estocástico.
19
1.5 PRINCIPAIS CONTRIBUIÇÕES
Este trabalho traz duas principais contribuições, a função diversidade e o simulador.
O simulador proporciona um ambiente web para a visualização do processo de otimização
do algoritmo inteligente PSO, independente de plataforma ou instalação de recursos
adicionais. Além de trazer nove famosos problemas de otimização já implementados, o
simulador ainda permite a criação de casos de teste customizáveis a partir de expressões
matemáticas.
A função diversidade é uma alternativa para a variação do peso inercial do PSO. Esta
estratégia utiliza a distância euclidiana média entre todas as partículas do enxame e a melhor
partícula global para controlar a relação exploração convergência durante o processo de
busca.
1.6 ESTRUTURA DO TRABALHO
O conteúdo deste trabalho está divido em quatro capítulos. O capítulo 2 apresenta a
contextualização de inteligência de enxames (seção 2.1), do algoritmo de otimização global
PSO (seção 2.2) e os fatores que influenciam no seu desempenho, as principais funções teste
(seção 2.3), as bibliotecas utilizadas no desenvolvimento do simulador (seções 2.4 à 2.7) e
os trabalhos correlatos (seção 2.8).
O capítulo 3 apresenta o desenvolvimento da função diversidade (seção 3.1), a
especificação e operacionalidade do simulador PSOView (seções 3.2 à 3.4) e um
comparativo com os resultados obtidos da função diversidade (seção 3.5). Já o capítulo 4
apresenta as conclusões do trabalho, bem como as dificuldades encontradas (seção 4.1) e
extensões para trabalhos futuros (4.2).
20
2 FUNDAMENTAÇÃO TEÓRICA
Este capítulo tem como objetivo contextualizar a fundamentação teórica necessária
para compreender o funcionamento do PSO e as tecnologias utilizadas na construção do
simulador.
2.1 SWARM INTELLIGENCE
O termo swarm intelligence foi proposto no fim da década de 80, quando se referia a
sistemas robóticos compostos por uma coleção de agentes simples em um ambiente
interagindo de acordo com regras locais (KENNED; EBERHART, 2001). De forma
genérica o termo Swarm (enxame) refere-se a qualquer coleção estruturada de indivíduos
capazes de interagir.
A inteligência de enxame inclui qualquer tentativa de projetar algoritmos ou
dispositivos distribuídos de solução de problemas, inspirados no comportamento coletivo de
insetos sociais e outras sociedades animais (BONEBEAU et al., 1999).
A teoria sobre swarm intelligence sugere que mentes e culturas são afetadas por suas
interações sociais de forma que sistemas compostos por agentes pouco inteligentes e com
capacidade individual limitada, possam ser capazes de apresentar comportamentos coletivos
inteligentes ao interagirem entre si e com o meio ambiente. (WHITE; PAGUREK, 1998).
Sob o ponto de vista da psicologia social a inteligência é fruto da cultura bem como
das interações sociais. De acordo com Allport (1985, p. 3), psicologia social é: “Uma
tentativa de entender e explicar como o pensamento, sentimento, e comportamento dos
indivíduos são afetados pela presença atual, imaginaria ou implícita de outros”.
2.2 PARTICLE SWARM OPTIMIZATION
O algoritmo inteligente otimização por enxame de partículas é uma técnica de
computação evolucionária desenvolvida por Eberhart e Kennedy em 1995, inspirada no
comportamento social de espécies biológicas como aves e peixes. É uma técnica baseada em
inteligência computacional que não é afetada pelo tamanho ou não linearidade do problema,
podendo convergir para uma solução ótima em muitos problemas onde métodos mais
analíticos falham na convergência (DELVALLE et al., 2008).
21
O PSO utiliza uma população chamada de enxame, onde cada indivíduo dentro do
enxame é denominado partícula. Segundo Jiao, Lian e Gu (2008), uma partícula i em uma
iteração k se desloca através do espaço solução com dois atributos: (1) a posição atual dentro
de um espaço de busca N-dimensional k k k k
i 1 n NX = (x ,..., x ,...x ) do problema, com
min k max
n n nx x x para todo n [1, N] , onde min
nx e max
nx são os limites da coordenada n; (2)
sua velocidade, representada vetorialmente por k k k k
i 1 n NV = (v ,..., v ,..., v ) nesse mesmo espaço
N-Dimensional do problema.
A cada iteração a velocidade e posição de todas as partículas são atualizadas de
acordo com dois melhores valores encontrados durante a busca. O primeiro é o melhor valor
encontrado pela partícula até o momento, chamado pbest. Outro melhor valor que é
encontrado pelo PSO é o melhor valor encontrado até o momento por qualquer indivíduo da
população, este melhor valor global é chamado gbest. Quando uma partícula torna parte de
uma vizinhança topológica o melhor valor é um valor local e é chamado lbest. Segundo Jiao,
Lian e Gu (2008) após encontrar os dois melhores valores, a posição e velocidade das
partículas são obtidas pelas equações 1 e 2:
i i 1 1 i i 2 2 g iV (k+1) = wV (k) +c r (P (k) - X (k)) +c r (P (k) - X (k)) (1)
i i IX (k+1) = X (k) + V (k+1) (2)
Onde 1r e 2r , são números randômicos gerados aleatoriamente no intervalo entre [0,1]
e 1c e 2c são respectivamente chamados de parâmetro cognitivo e social. O termo
k k
1 1 i ic r (P - X ) representa a distância entre a partícula i e sua melhor posição até a k-ésima
interação. Este termo dispersa a busca em várias regiões do espaço solução de maneira a
encontrar o mínimo global do problema. Já o termo k k
2 2 g ic r (P - X ) representa a distância entre
a partícula i e a melhor posição encontrada pela população até a k-ésima iteração. Por fim, o
parâmetro w, introduzido por Shi e Eberhart (1998) tem como finalidade melhorar as
habilidades de exploração do algoritmo no âmbito de busca, reduzindo a importância do
controle da velocidade máxima (POLI et al., 2007).
2.2.1 Peso inercial
Embora as primeiras pesquisas reconheçam que alguma forma de amortecimento da
dinâmica da partícula era necessária, a razão para isso não foi compreendida. Mas quando o
22
PSO foi implementado sem restrição de velocidade, esta acaba divergindo dentro de poucas
iterações (POLI et al., 2007).
No intuito de melhorar o desempenho do algoritmo PSO, Shi e Eberhart, (1998)
introduzem um parâmetro denominado peso inercial. O objetivo efetivo do parâmetro é
desempenhar o papel de equilibrar busca global e local, isso porque para diferentes
problemas deve haver diferentes equilíbrios entre habilidade de busca global e habilidade de
busca local.
Nesse trabalho pioneiro, o peso inercial foi implementado fixo apresentando
melhores resultados para valores no intervalo de [0.9, 1.2]. No entanto, os autores
apresentam indícios de que a estratégia que apresenta o peso inercial decrescente, de acordo
com o número de iterações, é bastante promissora.
Clerc (1999) institui o fator de constrição com o objetivo de promover a
convergência da velocidade, sem a necessidade de predeterminação de velocidade máxima.
No entanto, Eberhart e Shi (2000) concluíram que o fator de constrição pode ser considerado
um caso especial de peso inercial uma vez que os parâmetros desse fator estão conectados
aos demais parâmetros do PSO.
De forma prática, a implementação do peso inercial -kiter
iw = w *(1,0008) torna o
algoritmo mais eficiente porque valores altos para w implicam em grandes incrementos de
velocidade por iteração o qual possibilita a exploração de novas áreas em busca de uma
melhor solução. No entanto, pequenos valores de peso inercial implicam promover pequenas
atualizações de velocidade promovendo um ajuste fino da área de busca local (CHATERJEE
e SIARRY, 2004).
2.2.2 Distribuição de números randômicos
Uma discussão pertinente a respeito de algoritmos estocásticos diz respeito à
dispersão da população inicial no espaço de busca. Algoritmos como o PSO funcionam
muito bem para problemas que possuem pequena área de busca com baixa dimensão, mas
como o espaço de busca pode ser N-dimencional o desempenho se deteriora e muitas vezes,
converge prematuramente para um resultado ruim (LIU et al., 2007).
No caso de funções multimodais, onde podem haver muitos mínimos locais, a
performance do algoritmo pode ser prejudicada por uma má distribuição da população no
espaço de busca, tornando-o pouco hábil em localizar potenciais soluções (GROSAN et al.,
2005). Uma parte desta dificuldade pode ser minimizada selecionando uma distribuição bem
23
organizada de números randômicos (ABRAHAM et al., 2009; SHI e EBERHART, 1999;
RICHARDS e VENTURA, 2003).
Usualmente a geração de números randômicos é realizada por uma função que usa a
distribuição uniforme de probabilidade na geração desses números. Gehlhaar e Foge (1996)
demonstram que a distribuição uniforme das partículas nem sempre pode ser boa para o
estudo empírico de diferentes algoritmos, passando uma impressão errada do desempenho
dos mesmos.
Pant et al. (2007), realizaram um estudo onde são testadas outras estratégias de
distribuição de números randômicos, como a distribuição exponencial, log normal e
gaussiana, concluindo que estas são igualmente competentes e em muitos casos melhores
que a distribuição uniforme.
2.3 FUNÇÕES TESTE
No estudo de algoritmos de otimização é comum a realização de comparações entre
diferentes algoritmos usando uma série de funções teste. As características das funções teste
são as mais diversas, no entanto, em síntese a maior parte delas pode ser implementada no
espaço n dimensional, exigindo do algoritmo a estimação de n parâmetros. Além disso,
muitas delas são multimodais o que dificulta a otimização pelo excesso de mínimos locais,
tornando-as eficientes para avaliar o desempenho dos algoritmos de otimização nas mais
diversas situações. A seguir são apresentadas as principais funções teste utilizadas na
literatura junto de suas principais características.
2.3.1 Função Generalizada de Rastrigin
A função generalizada de Rastrigin definida por
2
1
1
( ,..., ) ( 10cos(2 ) 10)n
n i i
i
f x x x x
é um típico exemplo de função multimodal não
linear. Essa função foi inicialmente proposta por Rastringin em 1989 como uma função de
duas dimensões, e em seguida generalizada por Mühlenbein et al. (1991). Essa função é um
problema bastante difícil devido ao grande espaço de busca e ao grande número de mínimos
locais, como pode ser observado na Figura 1. Sob a forma generalizada o problema pode
apresentar n dimensões, com ótimo global em (0,0,...)nx , onde a função assume o valor
zero.
24
Figura 1 - Representação gráfica da função generalizada de Rastrigin em três dimensões
Fonte: Autor (2011)
2.3.2 Função Esférica
A função esférica é uma função contínua, estritamente convexa e unimodal, como
pode ser observado na Figura 2, sendo que usualmente não apresenta muita dificuldade para
os algoritmos de otimização. A função esférica é definida por: 2
1
1
( ,..., ) ( )n
n i
i
f x x x
sendo
tipicamente implementada no espaço de busca 5.12 5.12nx com mínimo global em
(0,0,...)nx assumindo para esse ponto o valor zero.
Figura 2 - Representação gráfica da função esférica em três dimensões
Fonte: Autor (2011)
2.3.3 Função de Griewank
A função de Griewank , proposta inicialmente por Griewank (1981) tem sido
bastante explorada como função teste em algoritmos de otimização global, sendo definida
25
por: 2
1
1 1
1( ,..., ) 1 cos
4000 1
nni
n i
i i
xf x x x
i
. Este problema pode ser implementado
em n dimensões, apresentando um grande número de mínimos locais, sendo que este número
cresce exponencialmente com n (LOCATELLI, 2003). Tipicamente, a função de Griewank é
definida na literatura com espaço de busca 600 600ix , para 30n apresentando ótimo
global em (0,0,...)nx , onde a função assume o valor zero. O comportamento dessa função
pode ser observado na Figura 3.
Figura 3 - Representação gráfica da função de Griewank em três dimensões
Fonte: Autor (2011)
2.3.4 Função de Rosenbrock
A função de Rosenbrock, definida por 1
2 2 2
1 1
0
( ,..., ) 100( ) ( 1)n
n i i i
i
f x x x x x
, é
um clássico problema de otimização. Inicialmente proposta por Rosenbrock (1960) e
posteriormente generalizada para n variáveis. Esta função tem como característica a
presença de muitos mínimos locais e uma suave variação nas vizinhanças do mínimo global,
tornando o processo de busca árduo para os algoritmos de otimização. A função de
Rosenbrock geralmente é definida pela literatura com o espaço de busca 100 100ix ,
para 30n , como demonstra a Figura 4, a função apresenta mínimo global em zero, quando
(1,1,...)nx .
26
Figura 4 - Representação gráfica da função de Rosenbrock em três dimensões
Fonte: Autor (2011)
2.3.5 Função de Schewefel
Originalmente proposta por Schewefel (1981) e definida por
1
1
( ,..., ) sinn
n i i
i
f x x x x
, esta função apresenta como dificuldade o fato de que o seu
gradiente não é orientado ao longo do seu eixo devido à interação entre suas variáveis, desta
forma os algoritmos que utilizam o gradiente convergem muito lentamente. Normalmente
implementada no espaço n dimensional com intervalo de busca de 500 500nx , com
mínimo global definido por (420.9698, ,420.9698) 0f . A Figura 5 apresenta as
características da função de Schewefel.
Figura 5 - Representação gráfica da função de Schewefel em três dimensões
Fonte: Autor (2011)
27
2.3.6 Função de Ackley
A função de Ackley definida por
2
1
1 1
1 1( ,..., ) 20 20exp 0.2 exp cos(2 )
n n
n i i
i i
f x x e x xn n
, é um problema de
minimização, proposto inicialmente por Ackley (1987), e em seguida generalizado por Bäck
(1996). Sua característica principal é possuir um termo exponencial que cobre sua superfície
com vários mínimos locais, como pode ser observado pela Figura 6. Tipicamente a função
de Ackley é implementada no espaço de busca 32 32nx com mínimo global em
(0,0,...)nx assumindo para esse ponto o valor zero.
Figura 6 - Representação gráfica da função de Ackley em três dimensões
Fonte: Autor (2011)
2.3.7 Função Ruidosa
A função ruidosa definida por 1
4
1
0
( ,..., ) 1 rand[0,1]n
n i
i
f x x i x
, tem como
característica a adição de um ruído randômico uniformemente distribuído na função. Devido
à presença do ruído a função alterna de tempo em tempo, consequentemente o mínimo
global da função também se modifica, fazendo com que o algoritmo retome a exploração
global. Essa característica aleatória atribuída ao mínimo global da função pode ser
observada pela , onde a função é representada com valores randômicos diferentes.
Geralmente implementada no espaço amostral de 1.28 1.28nx , com mínimo global em
(0,0,...)nx assumindo para esse ponto o valor 0 rand[0,1] (ABRAHAM et al., 2009).
28
Figura 7 - Representação gráfica da função ruidosa em três dimensões. (a) com ruído igual a 0, (b) com ruído
igual a 1
(a)
(b)
Fonte: Autor (2011)
2.3.8 Função de Levy
A função de Levy definida por:
5 5
2 2
1 2 1 2 1 2
i=1 j=1
f(x , x ) = i.cos((i-1).x +1) . j.cos((j+1).x + j) + (x +1,42513) + (x + 0,80032) , é
uma função de duas variáveis que, como representa a Figura 8, apresenta no espaço de busca
delimitado por 2[ 10 10]nx aproximadamente 760 mínimos locais e um mínimo global
localizado em 1x = -1,3068 e 2x = -1,4248, onde a função assume 176,14
(PARSOPOULOS; VRAHATIS, 2002).
Figura 8 - Representação gráfica da função de Levy em três dimensões
Fonte: Autor (2011)
29
2.4 PRIMEFACES
De acordo com Prime (2012), PrimeFaces é uma biblioteca de componentes para
Java Server Faces- JSF de código fonte aberto. Luckon et al. (2010) afirma que além de ser
uma das mais completas foi também uma das primeiras a estar totalmente convertida para o
JSF 2.0.
Boekel (2011) afirma que o padrão JSF , utiliza o conceito de componentes para a
criação de interfaces de sistemas web. As taglibs do JSF permitem ao desenvolver trabalhar
com um maior índice de abstração já que encapsulam o uso de tags HTML. Deste modo a
criação de elementos nas páginas web se torna muito mais fácil. Por exemplo, o uso das
tags<table>, <tr> e <td> para construção de tabelas pode ser substituído pelo
componente <h:panelGrid>o qual encapsula toda a mecânica das tags HTML. Boekel
(2011) ressalta que o JSF possui uma API que encapsula o uso de AJAX, permitindo aos
componentes fazer requisições assíncronas ao servidor.
Seguindo esta linha de componentes surgiu o framework PrimeFaces buscando
enriquecer o uso do JSF. O PrimeFaces oferece seus próprios componentes baseados na API
padrão do JSF, além de facilitar o uso de AJAX em aplicações web (BOEKEL, 2011).
De acordo com Prime (2012), todos os seus componentes foram construídos para
trabalhar com AJAX por padrão, logo não é necessário nenhum esforço extra por parte do
desenvolvedor para realizar chamadas assíncronas ao servidor. Além disso, o PrimeFaces dá
suporte a criação de funcionalidades que fazem uso do Ajax Push, o qual permite ao servidor
enviar dados ao navegador do usuário sem que este tenha feito uma requisição.
2.5 GRAPH3D
O componente Graph3D é um gráfico de visualização interativo para desenhar dados
em um gráfico tridimensional. Com ele é possível mover o gráfico e aplicar zoom com
simples movimentos do mouse (CHAP; 2012). A Figura 9 apresenta o gráfico de uma
função tridimensional construída pelo Graph3D.
30
Figura 9 - Representação gráfica da função f(x,y)=sen(x)*cos(y)*50+50
Fonte: Chap (2012)
Segundo Chap (2012), o componente foi desenvolvido para suportar gráficos com até
10.000 pontos sem perder qualidade. É possível executar gráficos gerados pelo componente
em todos os navegadores modernos, sem necessidade de requisitos adicionais. Chap (2012)
ainda afirma que Graph3D foi testado nos seguintes navegadores: Firefox 3.6, Safari 5.0,
Google Chrome 6.0, Opera 10.6 e Internet Explorer 9.
Este componente é parte integrante da biblioteca CHAP links, cuja aplicação é a
visualização baseada em web para exibição de gráficos, redes e cronogramas (CHAP, 2012).
Todos os componentes da biblioteca são desenvolvidos como Google Charts para Javascript
e GWT. Atualmente o projeto é mantido por Almante1, empresa de pesquisa holandesa
especializada em tecnologia da informação e comunicação. O código fonte está
disponibilizado no repositório GitHub2 sob licença Apache 2.0, a qual permite a modificação
e redistribuição dos fontes, desde que atenda suas condições de uso.
2.6 DIRECT WEB REMOTING
Direct Web Remoting (DWR) é uma biblioteca open source escrita em Java, que
permite construir de forma simples e prática aplicações web dinâmicas e interativas
empregando AJAX. Assim, o DWR permite executar via Javascript códigos e funções Java
localizados no servidor como se estivessem rodando no navegador(DIRECT, 2012).
De acordo com DIRECT (2012), a biblioteca possuí uma série de recursos como
chamadas em lote, vinculação de praticamente qualquer estrutura de dados entre Java e
1http://www.almende.com/home 2http://www.almende.github.com/chap-links-library/graph3d.html
31
Javascript, tratamento de exceções, proteção CSRF e integração com várias tecnologias do
lado servidor como Spring e Guice. A Figura 10 apresenta um esquema de funcionamento
do DWR.
Figura 10 - DWR alterando o conteúdo de uma lista após chamada Javascript
Fonte: Direct (2012)
Seguindo o fluxo da troca de mensagens entre o navegador e o servidor web, nota-se
como fica transparente a iteração entre Java e Javascript. No instante em que a função
eventHandler() é executada no navegador, esta acessa um código Java gerenciado pelo
DWR, e por meio de uma função de retorno atualiza o conteúdo da página.
O funcionamento do DWR se dá através da criação dinâmica de arquivos Javascript
baseados em classes Java. O código gerado utiliza Ajax para dar a impressão de que tudo
está acontecendo no navegador, enquanto, na realidade o servidor está executando e o DWR
organizando o fluxo dos dados (DIRECT, 2012). O DWR é composto por duas partes
principais:
a) Um Servlet Java executando no servidor que processa os pedidos e envia as respostas
para o navegador.
b) Código Javascript executando no navegador responsável por enviar solicitações e
atualizar as páginas.
Como Direct (2012) relata, a partir da versão 2.0 a biblioteca DWR permite o uso de
Ajax reverso, possibilitando ao servidor o envio de dados de forma assíncrona para os
navegadores. O DWR suporta três métodos para envio de dados ao navegador: Piggyback,
Polling e Comet. O Polling é a solução mais trivial dentre as demais, este realiza requisições
em intervalos de tempo regulares para verificar se há atualizações para o cliente. Já o Comet
32
permite ao servidor enviar mensagens aos clientes no apenas no momento em que houver
uma atualização. Por fim, o Piggyback mantem as atualizações no servidor e as envia para o
cliente apenas no momento em que o cliente faz uma requisição.
2.7 MATH EVALUATOR
A biblioteca Math Evaluator é parte integrante do projeto GraphingCalculator, cuja
finalidade é criar uma calculadora fonte aberta, multi-plataforma, desktop gráfica com
funcionalidades semelhantes a uma calculadora TI-83(GRAPHING, 2012).O projeto está
hospedado no ambiente de desenvolvimento colaborativo para código aberto Google Project
Hosting.
Segundo Graphing (2012), a biblioteca Math Evaluator permite resolver
expressões matemáticas armazenadas em objetos do tipo String. A expressão pode conter
operadores aritméticos básicos, funções trigonométricas, funções logarítmicas e variáveis. O
Quadro 1 apresenta a lista de operações permitidas pela biblioteca.
Quadro 1 - Operadores disponíveis na biblioteca Math Evaluator
Operação Operador
Adição +
Subtração -
Multiplicação *
Divisão /
Resto da divisão %
Seno sin()
Cosseno cos()
Tangente tang()
Cossecante acos()
Secante asin()
Cotangente atang()
Quadrado sqr()
Raiz quadrada sqrt()
Logaritmo base 10 log()
Logaritmo ln()
Exponencial exp()
Expoente ^ Fonte: Graphing (2012)
Com o conhecimento das operações suportadas pela biblioteca a construção de uma
equação é feita de forma prática. O Quadro 2 apresenta o trecho de código que resolve a
equação .
33
Quadro 2 - Exemplo de utilização da biblioteca Math Evaluator
... IEvaluator evaluator = new MathEvaluator(); int x = 3; int y = 2; evaluator.setExpression("sin(x)^2+cos(y)+2"); evaluator.addVariable("x", x); evaluator.addVariable("y", y); System.out.println("Resultado: " + evaluator.getValue()); ...
Fonte: Autor (2012)
Como mostra o exemplo, a utilização é bastante simples, no entanto, a biblioteca
deixa a desejar quanto à validação da expressão. Da forma em que está implementada, caso
ocorram erros na expressão, não há qualquer forma de tratamento para a exceção ou
tratamento para a mensagem de erro.
2.8 TRABALHOS CORRELATOS
Atualmente existem poucos trabalhos desenvolvidos voltados para a
visualização do processo de otimização do algoritmo de otimização global PSO. A seguir
serão apresentadas as duas ferramentas com este fim mais utilizadas no meio acadêmico,
seguido por uma comparação entre elas.
2.8.1 PsoVis
O PsoVis é uma ferramenta para a visualização do processo de otimização do
algoritmo inteligente PSO. Seu objetivo é ajudar a entender o funcionamento do PSO em
geral, permitindo variar os parâmetros do algoritmo e acompanhar seu comportamento de
forma visual (PSOVIS, 2005).
A aplicação possui cinco funções teste pré-definidas, sendo elas: Rastrigin,
Rosenbrock, Griewank, Sphere e Schaffer f6. Apesar de não permitir a inclusão de novas
funções o sistema permite alterar o espaço solução das existentes. A Figura 11 apresenta a
interface visual do PsoVis (PSOVIS, 2005).
34
Figura 11 - Applet PsoVis minimizando a função de Rosenbrock.
Fonte: Psovis (2005)
De acordo com Psovis (2005), a ferramenta possuí duas implementações do
algoritmo PSO, Constriction e Standard. Apenas a implementação Standard permite alterar
seus parâmetros, sendo eles: peso inercial inicial e final, coeficiente cognitivo e social,
velocidade máxima, número de partículas, número e número máximo de iterações. Como
configurações de função, o PsoVis permite exibir o mínimo global da função, definir o
intervalo de atualização entre as iterações além de interromper e pausar o processo de
otimização. Por fim, a cada iteração os resultados são exibidos na área “Optimization
Progress”, indicado pela letra A na Figura 11.
O laboratório ModLab da Goethe University Frankfurt3, mantém o PsoVis. O
laboratório também é responsável por desenvolver ferramentas de software para aplicação
em bio e quimioinformática. A aplicação está disponível na web em forma de applet no
portal do laboratório. Uma limitação desta ferramenta é que necessita instalação do JRE e da
API Java 3D no computador do usuário.
3 www.uni-frankfurt.de/english/
A
35
2.8.2 Particle Swarm Optimization Visualization
O Particle Swarm Optimization Visualizationou PSO Visualization é uma applet
Java relativamente simples e trivial, que demonstra visualmente um enxame de partículas a
procura de um valor máximo em uma paisagem 3D (PSO VISUALIZATION, 2004). Esta
ferramenta utiliza a implementação adaptative do PSO e requer JRE instalado para executar.
Figura 12 - Particle Swarm Optimization Visualization maximizando um espaço tridimensional
Fonte: Pso Visualization (2004)
A cada execução, a applet gera um novo ambiente de busca aleatório tridimensional,
onde um enxame fixo de doze partículas se movimenta em busca do máximo global, ao
encontrá-lo a execução é interrompida. O enxame ainda pode ser divido em até quatro
vizinhanças topológicas. A execução pode ser efetuada de uma só vez ou passo a passo,
porém, o número máximo de iterações é fixado em 100, e caso o PSO não encontre uma
solução a execução é interrompida.
A visualização das partículas no espaço de busca é simulada por diferentes cores que
exibem a posição atual e anterior das partículas. Vetores entre as partículas representam o
caminho por ela percorrido entre a anterior e atual iteração. Os botões Up, Down, Left e
Right movimentam o espaço de busca (não é permitido mover através do mouse). Por fim,
abaixo dos botões de movimentação são apresentados os resultados da otimização com
número máximo de iterações, máximo global da função, máximo global encontrado pelo
PSO e um campo informando se o máximo foi encontrado ou não.
36
Atualmente o PSO Visualization está hospedado e mantido pela empresa Project
Computing4.A última atualização foi feita em 2004 e o código fonte está disponível junto à
applet (PSO VISUALIZATION, 2004).
2.8.3 Comparativo
No intuito de realizar uma comparação entre as principais ferramentas de
visualização de otimização existentes, alguns recursos do PSOVis e PSO Visualization
foram identificados. O Quadro 3 apresenta um comparativo entre as ferramentas e os
recursos que elas atendem.
Quadro 3 - Comparação entre PSOVis e PSO Visualization
Recurso PSOVis PSO Visualization
Criar função teste
Alterar limites inferiores e superiores da função X
Exibir eixos da função X
Exibir grade da função X
Exibir gráfico com perspectiva isométrica5
Exibir gráfico com sombra
Exibir gráfico com proporção6
Visualizar função em 3D X X
Girar gráfico X X
Aproximar gráfico
Exibir movimentação das partículas X X
Alterar o intervalo de atualização da posição das
partículas X
Alterar os parâmetros do PSO X
Cross-Browser X X
Requer Java 3D instalado X
Requer JRE instalado X X
Permite pausar ou interromper a otimização X
Permite executar passo a passo X
Diferencia a melhor solução do enxame. X X
Exibe o mínimo global da função X
Multi-idioma
Estratégia de implementação do peso inercial Constriction
Standard Standard
Fonte: Autor (2012)
4 http://www.projectcomputing.com/resources/psovis/index.html 5 Perspectiva isométrica é o processo de representação tridimensional em que o objeto se situa num sistema de três eixos coordenados (axonometria). Estes eixos, quando perspectivados, fazem entre si ângulos de 120°:
6Relação proporcional entre altura e largura da imagem.
37
As ferramentas são muito semelhantes, ambas são implementadas em plataforma
Java e disponibilizadas em forma de applet. No entanto, o processo de otimização do
PSOVis busca o mínimo global da função, enquanto o PSO Visualization busca o máximo.
Quanto as funções teste implementadas o PSOVis, apresenta cinco conhecidos problemas de
otimização, ao contrário do PSO Visualization, que apresenta cenários tridimensionais
aleatórios.
Apesar da semelhança, a ferramenta PSOVis apresenta uma série de parâmetros os
quais o PSO Visualization não permite modificar. A interface visual do PSOVis ainda
possibilita ao usuário uma série de funcionalidades como a exibição dos eixos e grade da
função, os quais não estão disponíveis no PSO Visualization.
Ambas as ferramentas funcionam bem nos principais navegadores, Chrome, Firefox,
Internet Explorer, Safari e Opera. Porém, necessitam do JRE instalado na máquina para
funcionar. O PSOVis por sua vez, ainda necessita da API Java 3D para funcionar.
A diversidade, representada pela distância euclidiana entre todas as partículas do
enxame, vem sendo fortemente utilizada para melhorar a capacidade de exploração global
do PSO. Já que em problemas multimodais, o algoritmo pode sofrer com a convergência
prematura, pesquisadores têm investido fortemente em aplicações da diversidade no
algoritmo para amenizar este problema. A seguir apresentam-se os principais trabalhos
relacionados à função diversidade encontrados na literatura.
Zhan et al. (2009) em seu trabalho realiza o cálculo da diversidade das partículas do
enxame através de uma função que mede a distância euclidiana entre todas as partículas, e
utiliza o resultado para tomada de decisão em um estimador de estado evolucionário que
atua sobre o peso inicial combinando exploração, aproveitamento, convergência e jumping
out7. As escolha por algum destes estados é dada por meio de uma classificação Fuzzy. Os
autores realizam testes exaustivos com funções multimodais, no intuito de comprovar a
eficiência da estratégia.
Riget e Vesterstrom (2002) fazem uso de uma função diversidade baseada na
distância euclidiana entre todas as partículas para tentar superar o problema de convergência
prematura. Neste trabalho o vetor que atualiza a velocidade pode assumir a característica de
atrair as partículas quando a diversidade for alta, e de repelir as partículas quando a
7 Técnica utilizada pelo PSO para escapar de mínimos locais que assume posições fora do ponto de
convergência para um determinado número de partículas do enxame.
38
diversidade for baixa, alternando assim entre exploração e aproveitamento. A conclusão dos
autores é de que a estratégia implementada é hábil na busca global das soluções. Lein e
Mohan (2006) assim como Radha e Singh (2007) utilizam estratégias semelhantes em seus
trabalhos.
Olorunda e Engelbrecht (2008) investigam algumas definições de diversidade de
enxames na literatura, com o objetivo de determinar a utilidade destas medidas na
quantificação da exploração e aproveitamento do PSO. Segundo os autores, todas as
estratégias investigadas apresentam alguma incoerência ao relacionar diversidade de enxame
e velocidade das partículas. Contudo, concluem que a investigação do comportamento da
medida da diversidade do enxame na evolução do PSO mostra-se promissora, merecendo
que trabalhos futuros explorem melhor sua utilização.
39
3 DESENVOLVIMENTO
Este capítulo apresenta a proposta de variação do peso inercial para PSO chamada
função diversidade, e a especificação, desenvolvimento e operacionalidade do simulador
proposto PSOView.
3.1 FUNÇÃO DIVERSIDADE
Esta seção apresenta a proposta de estratégia para variação do peso inercial, chamada
função diversidade.
Estratégias de variação do peso inercial estão diretamente relacionadas à eficiência
do PSO no seu processo de busca. Um valor de peso inercial baixo aumenta as habilidades
de convergência do algoritmo, enquanto um valor alto proporciona uma maior exploração do
espaço solução. Deste modo, é fundamental que a variação deste parâmetro seja coordenada
por uma heurística eficiente.
Fatores como a dimensão do problema e tamanho do espaço solução influenciam
diretamente na relação exploração/convergência do algoritmo. Deste modo, estratégias que
utilizam o número de iterações como a de Jiao, Lian e Gu (2008), podem ser eficientes mas
não tão eficazes. Pois mesmo em problemas com baixa dimensão e espaço solução
relativamente pequeno, o algoritmo levará um número elevado de iterações para convergir
par uma solução, já que o peso inercial diminui em relação ao fator iteração.
Aumentar as habilidades de convergência e exploração do algoritmo nos mais
distintos problemas e configurações motivou esta pesquisa. Observando as iterações iniciais
do algoritmo percebe-se a alta dispersão entre as partículas, enquanto ao fim do processo de
busca as partículas estão bastante densas. Logo, utilizar o fator diversidade na estratégia de
variação se mostrou uma boa opção, ao contrário das estratégias como de Jiao, Lian e Gu
(2008) permite que o algoritmo após um processo de convergência para uma mínimo local
retorne a explorar o espaço solução na busca do mínimo global.
Neste trabalho, considerou-se diversidade, a distância euclidiana média entre todas as
partículas do enxame e a melhor partícula global até então encontrada. A Equação 3
apresenta o cálculo da diversidade. Este cálculo representa o somatório ponderado das
diferenças entre todas as partículas do enxame e a melhor partícula global, divido pela
quantidade de partículas do enxame.
40
2
1 1
1.
.
S Nk
i g
i k
D x pS
(3)
Onde D representa a diversidade encontrada, S o tamanho da população do enxame, N a
dimensão do problema, k
ix uma partícula k do enxame egp a melhor partícula até então
encontrada.
Após o cálculo da diversidade, para facilitar a utilização do peso inercial, realiza-se
uma normalização por meio da Equação (4).
min
minmáx
D Di
D D
(4)
Onde, Dmin = 10-3
sendo definido como densidade mínima, Dmax é a maior diversidade
encontrada ao longo das iterações e i um valor entre 0 e 1. Em seguida, aplica-se o valor
encontrado em i na Equação (5).
0.86( ) 0,4.e iw i (5)
Esta equação irá retornar o valor do peso inercial, sendo este um valor entre 0,4 e 0,9.
Considera-se este intervalo assumindo que 0,4 garante uma boa taxa de convergência e 0,9
boa taxa de exploração. A Figura 13 ilustra a curva de variação do peso inercial em função
da diversidade.
Figura 13 - Curva de variação do peso inercial para a função diversidade
Fonte: Autor (2012)
Aplicando-se a função diversidade no cálculo do peso inercial se obtêm um valor
próximo de 0,4 sempre que as partículas estiverem muito próximas do melhor global e
próximo de 0,9 sempre que estiverem muito dispersas. Nota-se na Figura 13 que a variação
do w não é linear, isto se dá para garantir que o algoritmo não sofra com a convergência
prematura.
41
Sua aplicação no PSO é feita no mesmo momento que as demais estratégias de
variação do peso inercial. A Figura 14 demonstra o fluxo de funcionamento do PSO e sua
relação com a diversidade.
Figura 14 - Fluxo de funcionamento do PSO com a função densidade
Fonte: Autor (2012)
Durante as iterações PSO após o cálculo das soluções das partículas calcula-se a
função diversidade, representada pelo retângulo em destaque na Figura 14. Em seguida
atualiza-se a nova posição e velocidade de todas as partículas do enxame, com o peso
inercial calculado em função da diversidade.
3.2 ESPECIFICAÇÃO
Esta seção apresenta de forma detalhada os requisitos, casos de uso e
protótipos visuais levantados para o simulador bem como seus diagramas de classe e
sequência.
act UC02 - Criar Função
Criar enxame
inicial
Velocidade e
posição inicial
aleatória
Defini-se melhor
local e global
inicial
Calcula soluções
encontradas
Atualiza posição
e v elocidade
Novo melhor local/
global é melhor?Atualiza melhor
local/global
Critério de parada?Solução melhor
global
Calcula a
div ersidade e
atualiza o peso
inercial
Início
Fim
[Não]
[Sim]
[Não]
[Sim]
42
3.2.1 Requisitos
O simulador proposto neste trabalho deve oferecer um ambiente de testes completo,
flexível e multi-idioma, para avaliar o desempenho do PSO nas mais diversas situações.
Deve ainda possibilitar o ajuste dos parâmetros do algoritmo e função teste. Quanto às
funções teste, deve-se ainda possibilitar selecionar uma função pré-definida, ou construir
uma nova a partir de uma expressão matemática. O sistema deve ser executado diretamente
em um navegador web sem a necessidade de instalação de recursos ou bibliotecas adicionais.
A visualização do gráfico, deve permitir ao usuário sua interação com o sistema durante
todo o processo de otimização a fim de melhor adequar a sua visualização. Ao fim do
processo, o simulador deve fornecer ao usuário os principais resultados do processo. O
simulador ainda deverá oferecer ao usuário a implementação da estratégia de diversidade,
proposta neste trabalho, para fins de comparação com estratégias de variação de peso
inercial já conhecidas, como a de Jiao, Lian e Gu (2008).
A partir destas necessidades, o Quadro 4 apresenta a lista de regras de negócio
identificadas para o sistema. Cada regra de negócio está vinculada a pelo menos um
requisito funcional dos quais são listados no Quadro 5.
Quadro 4 - Regras de negócio da aplicação
Regra Descrição
RN-01 O sistema terá as seguintes funções implementadas: Ackley, Alpine, Griewank,
Rastrigin, Rosenbrock, Schaffer's f6, Schwefel, Sphere e Tripod.
RN-02 Os seguintes parâmetros poderão ser ajustados: Limitante superior e inferior.
RN-03 As seguintes funções e operações poderão ser utilizadas na construção da
equação: +, -, *, /, %, ^, sin(), cos(), tang(), acos(), asin(), tan(), sqrt(), sqr(),
ln(), exp() e log().
RN-04 Apenas poderão ser utilizadas variáveis x e y.
RN-05 A visualização deverá ser em 3 dimensões.
RN-06 Os seguintes eventos serão permitidos: aproximar, distanciar e girar em todos
os sentidos.
RN-07 Serão estratégias de implementação do peso inercial: função de Jiao, Lian e Gu
(2008) e função diversidade (proposta neste trabalho).
RN-08 Os seguintes parâmetros do algoritmo poderão ser ajustados: número máximo
de iterações, número de partículas do enxame, coeficientes cognitivo e social,
peso inercial inicial e final e critério de parada (erro).
RN-09 Os seguintes idiomas estarão disponíveis: Português do Brasil e Inglês dos
EUA.
RN-10 O idioma padrão deverá ser Português do Brasil.
Fonte: Autor (2012)
43
O Quadro 5 apresenta os requisitos funcionais identificados para o sistema. A lista
relaciona cada requisito funcional com sua(s) regra(s) de negócio, quando ele a(s) possui.
Quadro 5 - Requisitos Funcionais da aplicação
Requisito Descrição Regras de
negócio
RF-01 O sistema deve permitir selecionar uma função pré-existente. RN-01;
RF-02 O sistema deve permitir ajustar os parâmetros da função. RN-02;
RF-03 O sistema deve permitir criar funções. RN-03; RN-04;
RF-04 O sistema deve permitir visualizar funções. RN-05; RN-06;
RF-05 O sistema deve permitir exibir os eixos da função. RN-05; RN-06;
RF-06 O sistema deve permitir exibir a grade da função
RF-07 O sistema deve permitir exibir o gráfico com perspectiva
isométrica.
RF-08 O sistema deve permitir exibir o gráfico da função com sombra.
RF-09 O sistema deve permitir ou não manter a proporção entre os
eixos x e y da função.
RF-10 O sistema deve permitir escolher a estratégia de implementação
do peso inercial.
RN-07;
RF-11 O sistema deve permitir ajustar os parâmetros do algoritmo de
otimização
RN-08;
RF-12 O sistema deve permitir executar a otimização da função.
RF-13 O sistema deve permitir a movimentação das partículas do
enxame durante a otimização
RF-14 O sistema deve permitir definir o intervalo de tempo entre as
movimentações do enxame no gráfico.
RF-15 O sistema deve permitir visualizar os resultados da otimização
da função.
RF-16 O sistema deve permitir alterar o idioma. RN-09; RN-10;
Fonte: Autor (2012)
O Quadro 6 apresenta a lista de requisitos não funcionais identificados para este
sistema.
44
Quadro 6 - Requisitos não Funcionais da aplicação
Requisito Descrição
RNF-01 O sistema deve executar em plataforma web.
RNF-02 O sistema deve executar nos navegadores Chrome 2.0, Firefox 3.6 e Internet
Explorer 9.0.
RNF-03 O sistema deve utilizar HTML5, Javascript e Graph3D para visualização das
funções.
RNF-04 O sistema utilizará arquitetura em camadas.
RNF-05 O sistema deve utilizar Java para executar no lado do servidor.
RNF-06 O sistema deve executar no servidor GlassFish 3.1.2.
RNF-07 O sistema deve utilizar a biblioteca Math Evaluator para construção das
funções.
RNF-08 O sistema deve utilizar a biblioteca de componentes ricos PrimeFaces 3.4.
RNF-09 O sistema deve utilizar o framework DWR 3.1 para comunicação AJAX
Fonte: Autor (2012)
3.2.2 Casos de Uso
Para o sistema PSOView foram identificados os casos de uso apresentados no
diagrama da Figura 15.
Figura 15 - Diagrama de casos de uso do sistema
Fonte: Autor (2012)
uc Casos de Uso
PSOView
Usuário
(from Atores)
UC02 - Visualizar
Otimização
UC03 - Criar Função
UC01 - Alterar Idioma
«extend»
45
Os casos de uso UC01, UC02 estão diretamente relacionados com o ator Usuário,
pois podem ser diretamente acionados. Ao contrário do UC03 o qual é entendido e
opcionalmente invocado pelo UC02.
Para o sistema PSOView, identificou-se apenas um ator, denominado Usuário. O ator
Usuário é qualquer pessoa que de fato tem acesso web a aplicação e a operacionaliza.
Uma funcionalidade muito simples, mas que é um diferencial contra as demais
ferramentas de otimização que utilizam o PSO, é a possibilidade de alterar o idioma do
sistema, capturada pelo UC01. O Quadro 7 apresenta a descrição deste caso de uso.
Quadro 7 - UC01 - Alterar idioma
UC01 Alterar Idioma
Descrição O usuário altera o idioma da aplicação.
Atores Usuário.
Pré-Condições O usuário ter acessado a aplicação.
Pós-Condições Idioma do sistema alterado.
Requisitos RF-16; RN-09; RN-10.
Fluxo Principal
1. O sistema PSOView apresenta ao Usuário as opções de idioma.
2. O Usuário seleciona o idioma desejado no sistema PSOView.
3. O sistema PSOView altera o idioma e apresenta ao Usuário.
Fonte: Autor (2012)
A principal funcionalidade deste sistema é a otimização de função teste. Desta forma,
o ator Usuário poderá ajustar os diversos parâmetros tanto da função quanto do algoritmo
para assim, observar de forma visual o processo de otimização. O Quadro 8 apresenta este
recurso com maiores detalhes.
46
Quadro 8 - UC02 - Visualizar otimização
UC02 Visualizar Otimização
Descrição O usuário otimiza uma função no sistema PSOView.
Atores Usuário.
Pré-Condições O usuário ter acessado a aplicação.
Pós-Condições Função teste otimizada.
Requisitos
RF-01; RF-03; RF-04; RF-05; RF-06; RF-07; RF-08; RF-09; RF-10;
RF-11; RF-12; RF-13; RF-14; RF-15; RN-01; RN-05; RN-06; RN-07;
RN-08; RN-11.
Fluxo Principal
1. O sistema PSOView apresenta as opções de configuração ao
Usuário.
2. O Usuário configura os parâmetros e a função a ser otimizada no
sistema PSOView.
3. O sistema PSOView valida os parâmetros, constrói a função e
apresenta ao Usuário.
4. O Usuário define os parâmetros de execução do algoritmo de
otimização no sistema PSOView.
5. O sistema PSOView valida os parâmetros, executa o algoritmo de
otimização e apresenta os resultados ao Usuário.
6. O Usuário visualiza as etapas do processo de busca até o
algoritmo satisfazer o critério de parada no sistema PSOView.
Fluxo Alternativo
2.1 Função definida pelo usuário selecionada
2.1.1 <Extend> UC-03 Criar Função.
6.1. Manipular Visualização
6.1.1. Usuário ajusta a posição da equação no sistema PSOView.
6.1.2. O sistema PSOView apresenta a equação ajustada ao
Usuário.
Exceções
3.1. Parâmetros da Função Inválidos
3.1.1. O sistema PSOView informa o(s) parâmetro(s)
inválido(s) da função ao Usuário.
3.1.2. O Usuário retorna para o passo 2 no sistema PSOView.
5.1. Parâmetros do Algoritmo inválidos.
5.1.1. O sistema PSOView informa o(s) parâmetro(s)
inválido(s) do algoritmo.
5.1.2. O Usuário retorna para o passo 4 no sistema PSOView.
Fonte: Autor (2012)
O Quadro 9 apresenta uma funcionalidade que pode ser opcionalmente executada
pelo UC02. Este recurso do sistema permite ao Usuário criar funções teste a partir de uma
47
expressão matemática. Além da expressão esta funcionalidade ainda permite alterar as
configurações de domínio da função.
Quadro 9 - UC03 - Criar função
UC03 Criar Função
Descrição Função teste criada a partir de uma expressão.
Atores Usuário.
Pré-Condições O usuário seleciona a função definida pelo usuário.
Pós-Condições Função teste criada.
Requisitos RF-01; RF-02; RF-03; RN-01; RN-02; RN-03; RN-04.
Fluxo Principal
1. O sistema PSOView apresenta o campo para o Usuário inserir a
expressão.
2. O Usuário informa a expressão e a envia ao sistema PSOView.
3. O sistema PSOView valida, constrói e exibe a função ao Usuário.
Exceções
3.1. Função Inválida
3.1.1. O sistema PSOView apresenta a mensagem de erro ao
Usuário.
3.1.2. O Usuário confirma a visualização da mensagem no
sistema PSOView.
3.1.3. O sistema PSOView retorna para o Usuário a execução.
Fonte: Autor (2012)
3.2.3 Protótipos Visuais
Para o sistema PSOView, projetou-se uma interface web que permita ao usuário
fazer uso de todos os recursos do sistema em uma única página. A Figura 16 apresenta o
protótipo desenvolvido na ferramenta de prototipação iPlotz.
48
Figura 16 - Protótipo visual para o sistema PSOView
Fonte: Autor (2012)
A interface é bastante simples e intuitiva. No lado esquerdo estão dispostos todos os
parâmetros e configurações referentes às funções testes. O lado direito apresenta todos os
parâmetros e configurações referentes ao algoritmo PSO, além dos botões Iniciar e
Resultados. Já a parte central da interface, possui o objeto que apresentar de forma visual a
função e o algoritmo em execução. Por fim, o cabeçalho é composto na sua esquerda pelo
logotipo do sistema, e a direita pelas opções de idiomas disponíveis.
3.2.4 Diagrama de Classes
Esta seção apresenta os diagramas de classes do sistema PSOView. Para uma melhor
visualização, as classes apresentados a seguir exibem apenas seus atributos .No entanto,
deduz-se existirem todos os métodos assessores necessários. O modelo de classes foi
organizado em oito pacotes distintos. A Figura 17 apresenta o diagrama de pacotes de
classes com as respectivas dependências entre os pacotes.
49
Figura 17 - Diagrama de pacotes de classe
Fonte: Autor (2012)
O funcionamento do sistema está concentrado em quatro pacotes principais, são eles:
function, core, bean e dwr. O pacote function, como mostra a Figura 18,
contém as classes e a interface que tornam a estrutura da aplicação flexível para criar
funções teste, sendo elas definidas por meio de uma expressão ou não.
50
Figura 18 - Diagrama de classes do pacote function
Fonte: Autor (2012)
A interface IFunction possui os métodos acessores que são implementados pela
classe Function. Os métodos getYlow() getYup, setYlow(double ylow) e
setYup(double yup) são os métodos acessores para o atributo que armazena os limites
superiores e inferiores da função. Já os métodos getDescricao() e
setDescricao(String descricao)acessam a String que contém a descrição da
função. O método eval(Particle p) por sua vez, possui a assinatura para o método
que irá calcular o valor da solução de um Particle, retornando-o em um tipo double.
A classe abstrata Function possui os atributos descricao, yLow e YLow
além da implementação de seus respectivos métodos acessores listados na interface
IFunction. Esta classe é estendida pela classe UserDefined e demais classes
existentes no pacote test. As classes PSOBean e PSO utilizam esta classe para definir o
tipo função teste que pode ser otimizado pelo sistema.
A classe UserDefined implementa o método eval(Particle p) permitindo
a criação de funções definidas pelo usuário por meio de uma expressão matemática. O
pacote MathEvaluator contém as classes responsáveis por calcular o valor de uma
class function
Serializable
Function
- descricao: String = ""
- yLow: double = 0d
- yUp: double = 0d
+ equals(Object) : boolean
+ getDescricao() : String
+ getYLow() : double
+ getYUp() : double
+ hashCode() : int
+ setDescricao(String) : void
+ setYLow(double) : void
+ setYUp(double) : void
«interface»
IFunction
+ eval(Particle) : double
+ getDescricao() : String
+ getYLow() : double
+ getYUp() : double
+ setDescricao(String) : void
+ setYLow(double) : void
+ setYUp(double) : void
Serializable
UserDefined
- evaluator: MathEvaluator = new MathEvaluator()
+ eval(Particle) : double
+ getEvaluator() : IEvaluator
+ setEvaluator(MathEvaluator) : void
+ UserDefined(String)
Serializable
java.util.Observer
bean::PSOBean
java.util.Observable
Serializable
core::PSO
Serializable
test::Ackley
Serializable
test::Alpine
Serializable
test::Griewank
Serializable
test::Rastrigin
Serializable
test::Rosenbrock
Serializable
test::Schaffer
Serializable
test::Schwefel
Serializable
test::Sphere
Serializable
test::Tripod
0..*
Otimiza
-funcao1
1..*
Mantém
-function1..*
1Util iza-pso
1..*
51
expressão matemática. A Figura 19 apresenta as classes do pacote MathEvaluator e sua
relação com a classe UserDefined. Todas as classes do pacote MathEvaluator
formam retirados da biblioteca Math Evaluator.
Figura 19 - Pacote de classes MathEvaluator
Fonte: Autor (2012)
A classe MathEvaluator implementa os métodos contidos na interface
IEvaluator, entre eles os métodos acessores do atributo expression o qual contém a
String com a expressão matemática que será calculada pelo método getValue(),cujo
retorno é um tipo Double. A classe ainda permite utilizar variáveis na construção de
expressões, as quais são armazenadas no HashMap variables junto ao seu respectivo
valor.
Ainda na Figura 17, o pacote core armazena todas as classes responsáveis por
implementar a estrutura do algoritmo PSO. A Figura 20 apresenta as classes que compõem o
pacote core e sua relação com os demais pacotes.
class MathEv aluator
«interface»
IEv aluator
+ DEGREES: int = 2 {readOnly}
+ GRADIANS: int = 3 {readOnly}
+ RADIANS: int = 1 {readOnly}
+ addVariable(String, Double) : void
+ getAngleUnits() : int
+ getExpression() : String
+ getValue() : Double
+ getVariable(String) : Double
+ setAngleUnits(int) : void
+ setExpression(String) : void
Serializable
MathEv aluator
- angleUnits: int = IEvaluator.RADIANS
- expression: String = null
- node: Node = null
- operators: Operator ([]) = null
- variables: HashMap = new HashMap()
MathEv aluator::Node
+ nLeft: Node = null
+ nLevel: int = 0
+ nOperator: Operator = null
+ nParent: Node = null
+ nRight: Node = null
+ nString: String = null
+ nValue: Double = null
MathEv aluator::Operator
- op: String
- priority: int
- type: int
Function
Serializable
function::UserDefined
- evaluator: MathEvaluator = new MathEvaluator()
1
Assume
+nOperator
1..*1
Contém
-variables
1..*
1
Contém
#operators
1..*
1Util iza
-evaluator 1..*
52
Figura 20 - Pacotes de classes core
Fonte: Autor (2012)
A classe Particle possuí a estrutura para representar uma partícula do enxame. O
atributo posicao armazena um vetor de double com o valor das coordenadas da
partícula. Já o atributo velocidade armazena a velocidade de cada coordenada do
atributo posicao. Por fim, o atributo fitness registra o refinamento da partícula.
A Interface Swarm possui a assinatura dos dois métodos fundamentais para o
funcionamento do algoritmo PSO. Estes métodos são implementados pela classe PSO, onde
o método run() executa o algoritmo e o método updateW(int type) atualiza o peso
inercial em função da estratégia definida. Dentre os diversos atributos da classe, que são em
sua maioria parâmetros de configuração do algoritmo PSO e serão detalhados na seção de
implementação, destaca-se o funcao e enxame. Sendo que o primeiro representa a função
teste que será otimizada e o segundo o enxame de partículas do algoritmo. Neste trabalho, o
algoritmo foi estruturado para otimizar problemas tridimensionais. Porém a estrutura tanto
da função teste quanto do algoritmo está implantada para resolver problemas em um espaço
n dimensional.
Implementou-se o padrão Observer entre PSO e PSOBean para garantir que a cada
atualização do vetor posição das partículas do enxame, seja possível atualizar as novas
posições no gráfico do navegador durante a execução do PSO. Assim, o PSO estende os
métodos da classe Observable os quais notificam a classe PSOBean que implementa o
class core
Serializable
Particle
- fitness: Double
- posicao: double ([])
- velocidade: double ([])
java.util.Observable
Serializable
PSO
- bestEnxame: List<Particle>
- c1: double = 1.2
- c2: double = 1.2
- dmax: double = 0d
- dmin: double = 0.0001
- enxame: List<Particle>
- eps: double = 0.001
- fstar: double ([])
- funcao: Function
- gBest: Particle
- inertialFunction: int = 1
- kiter: int = 1
- lBest: Particle
- n: int
- ncall: int = 0
- niter: int = 100
- nps: int = 4
- npt: int
- random: Random = new Random()
- vMax: double
- w: double
- wf: double = 0.2
- wi: double = 0.9
«interface»
Swarm
+ run() : void
+ updateW()(int) : void
Serializable
java.util.Observer
bean::PSOBean
- ajax: PSOAjax = null
- contador: int = 0
- currentExpression: String = "x*y"
- currentLanguage: String
- delay: int = 80
- dwrId: String
- expressions: List<String>
- function: Function
- functions: List<Function>
- language: List<String>
- pso: PSO
Serializable
function::Function
- descricao: String = ""
- yLow: double = 0d
- yUp: double = 0d
0..*
Otimiza
-funcao
1
1..*
Mantém
-function 1..*
1
Util iza-bestEnxame
1..*
1
Util iza-enxame
1..*
1
Mantém-pso
1..*1
Util iza+gBest
1..*
1
Util iza+lBest
1..*
53
método update() da interface Observer. Este método é responsável por executar uma
ação sempre que o PSO notificá-lo que ocorreu uma atualização.
Além do pacote core, a classe PSOBean do pacote bean ainda se comunica com
outros dois pacotes, são eles: converter e dwr. A Figura 21 apresenta o pacote de classes
bean e sua relação com os demais.
Figura 21 - Pacote de classes bean
Fonte: Autor (2012)
A classe FunctionConverter do pacote function é responsável por fazer a
conversão dos Objects do tipo Function para String e vice e versa. Este conversor
é utilizado pelo PSOBean quando os objetos Function são transmitidos para as páginas
XHTML.
Finalmente a classe PSOAjax do pacote dwr possui todos os métodos responsáveis
por executar requisições AJAX síncronas e assíncronas da classe PSOBean e arquivos
JavaScript localizados no cliente. Esta implementação foi necessária para permitir a
comunicação entre o Javascript e servidor, durante o processo de construção do gráfico e
atualização da posição das partículas.
3.2.5 Diagramas de Sequência
Esta seção apresenta os diagramas de sequência identificados para o sistema
PSOView afim de ilustrar a colaboração entre os objetos ao longo do tempo. São
class bean
Serializable
java.util.Observer
PSOBean
- ajax: PSOAjax = null
- contador: int = 0
- currentExpression: String = "x*y"
- currentLanguage: String
- delay: int = 80
- dwrId: String
- expressions: List<String>
- function: Function
- functions: List<Function>
- language: List<String>
- pso: PSO
Converter
Serializable
conv erter::FunctionConv erter
- psoBean: PSOBean
java.util.Observable
Serializable
core::PSO
Serializable
dwr::PSOAjax
- wc: WebContext {readOnly}
1
Util iza
-psoBean
9..*
1
Contém-ajax
1
1
Mantém -pso
1..*
54
apresentados os diagramas de sequência para os casos de uso visualizar otimização e
construir função.
3.2.5.1 Visualizar Otimização
Para o caso de uso UC02 visualizar otimização identificou-se o diagrama de
sequencia ilustrado pela Figura 22. Ao acessar o sistema PSOView, os objetos psoBean e
psoAjax são instanciados. Em seguida, com a função teste seleciona e parâmetros do PSO
informados, o sistema realiza a validação dos parâmetros e o Usuário executa a otimização.
Nesse momento o objeto pso é instanciado com dimensão fixa 2, número de partículas que
irão compor a critério de parada e função teste informadas pelo Usuário. Em seguida o
método run() do pso o laço de repetição da otimização.
Figura 22 - Diagrama de sequencia para UC02 Visualizar Otimização
Fonte: Autor (2012)
sd UCR 02 - Visualizar Otimização
formDados
psoBean
:PSOBean
Usuário
(from Atores)
pso :PSO
psoAjax
:PSOAjax
loop processo de otimização
[niter > kiter OR erro < soma]
acessa o sistema()
psoBean= PSOBean()
psoAjax= PSOAjax()
informa os parâmetros do PSO()
parâmetros validados()
executa a otimização()
optimize()
pso= PSO(2, npt, function)
run()
atualizarPosicao()
calculaRefinamento()
notifyObserers()update(pso, arg)
updateDataPoints(positions, sleep)
drawParticles(positions)
atualizaMelhorPosicao()
calculaErro()
exibe os resultados()
55
No início do processo de otimização a posição das partículas do enxame é atualizada
pelo método atualizaPosicao(), caso seja a primeira iteração a posição inicial é
definida de forma aleatória. Após a atualização o método
calculaRefinamento()calcula a solução de cada partícula. Em seguida o método
notifyObservers() notifica o observador psoBean que há uma atualização no
enxame. O psoBean por sua vez executa o método update() o qual recebe por
parâmetro o objeto pso e envia o vetor positions com as posições do enxame junto ao
intervalo de atualização sleep para o objeto psoAjax. O psoAjax por sua vez realiza
uma requisição Ajax reverso para o método Javascript drawParticles()enviado o
vetor positions. O método drawParticles() por sua vez desenha a posição das
partículas no gráfico da função. Em seguida o objeto pso atualiza o valor da melhor solução
do enxame pelo método atualizaMelhorPosicao() e efetua o calculo do erro pelo
método calculaErro(). Este laço se repete enquanto o erro da iteração for maior que
definido ou o número de iterações for menor que o número máximo informado.
Após o termino da execução do método run() os resultados da otimização são
informados ao usuário.
3.2.5.2 Construir função
Para o caso de uso UC03 Construir Função, identificou-se o diagrama de
sequência ilustrado pela Figura 23. No instante em que o usuário informa a expressão para o
sistema, o objeto psoBean por meio de seu método validateExpression() valida a
expressão e caso verdadeiro, cria um objeto funcaoDefinida a qual irá calcular o valor
da função para todos os pontos que irão compor o gráfico. Estes pontos são representados
por objetos do tipo Particle. Em seguida o sistema retorna para o usuário a visualização
da função.
56
Figura 23 - Diagrama de sequência para UC03 Criar Função
Fonte: Autor (2012)
3.3 IMPLEMENTAÇÃO
Nesta seção apresentam-se os itens mais importantes do desenvolvimento do
simulador bem como a implementação da estratégia de variação do peso inercial do PSO em
função da diversidade.
3.3.1 Técnicas Utilizadas
A ferramenta foi desenvolvida em linguagem de programação Java, com auxílio do
ambiente de desenvolvimento integrado NetBeans 7.2.1 e JDK 1.7. O sistema operacional
utilizado foi Windows 7.
A interface gráfica foi desenvolvida com o framework JSF e componentes da
biblioteca de componentes ricos PrimeFaces 3.4. Utilizou-se como tema para layout o
componente hot-sneaks versão 1.0.8 do PrimeFaces.
Para executar as requisições AJAX reverso e requisições AJAX efetuadas por
arquivos Javascript, utilizou-se a biblioteca DWR versão 3.1RC1.
A aplicação desenvolvida e testada para rodar no servidor GlassFish versão 3.1.
necessitando de algumas configurações adicionais para permitir execução de requisições
AJAX tipo Comet.
sd UCR 03 - Construir Função
formDados
funcaoDefinida
:UserDefined
psoBean
:PSOBean
Usuário
(from Atores)
particula :Particle
seleciona a função()
exibe a entrada da expressão()
informa a expressão()
validateExpression()
funcaoDefinida= UserDefined(curretExpression) :UserDefined
particula= Particle(2)
eval(particula)
boolean()Double()
drawVisualization()
57
Para construção gráfica das funções utilizou-se como base a biblioteca Javascript
Graph3D, sofrendo adaptações para se adequar ao problema proposto. O cálculo das
expressões matemáticas foi feito através da biblioteca Math Evaluator. Como ambiente de
testes utilizou-se os principais navegadores, sendo eles: Google Chrome versão 22.0.1,
Mozilla Firefox 15.0.1, Internet Explorer 9, Opera 12.02 e Safari 6.
3.3.2 Estrutura do Projeto
Antes de apresentar a implementação do projeto se faz necessário compreender a
estrutura em que o projeto Java Web foi desenvolvido. Para facilitar o desenvolvimento do
simulador foi desenvolvida a estrutura apresentada pela Figura 24.
Figura 24 - Estrutura do Projeto PSOView
Fonte: Autor (2012)
A pasta Páginas Web contém a página xhtml do sistema, além de um diretório
de pastas. Deste diretório, a pasta META-INF contém o arquivo contexto.xml, o qual
armazena entre outros dados o contexto da aplicação. A pasta WEB-INF possui todos os
arquivos xml de configuração do sistema, como: dwr.xml, faces-config.xml,
glassfish-web.xml e web.xml.Por fim, a pasta resources contém um de diretório
de pastas para armazenar os arquivos .css, .js e imagens do sistema em geral. Os
arquivos javascript serão melhor abordados no decorrer deste trabalho.
58
O Pacotes de Códigos-fonte além de armazenar todas as classes e pacotes
de classes descritos do item 3.2.4, ainda armazena os arquivos de idiomas do sistema. O
pacote br.udesc.psoview.internationalization contém os arquivos de
idioma do sistema, i18n_pt_BR.properties e i18n_en_US.properties são
armazenam as propriedades tanto em português e inglês respectivamente.
O Pacotes de Testes por sua vez armazena os casos de testes criados com o
JUnit para testar o algoritmo PSO durante sua implementação. Ainda possui casos de teste
para as expressões matemáticas calculadas pelo MathEvaluator.
A pasta Bibliotecas armazena todas as bibliotecas utilizadas pelo sistema. São
bibliotecas utilizadas pelo sistema: primefaces-3.4.jar, hot-sneaks-1.0.8,
dwr3_rc1.jar, commons-logging-1.1.1.jar e javax.faceds.jar. Já o
pacote Bibliotecas de Testes armazena as bibliotecas JUnit utilizadas nos casos
de teste.
Por fim, o pacote Arquivos de Configuração centraliza todos os arquivos de
configuração .xml do sistema, inclusive referência para os arquivos citados na pasta WEB-
INF.
3.3.3 Implementação do PSO
O algoritmo de otimização global PSO, utilizado para minimização de função neste
trabalho, teve sua implementação baseada na estratégia proposta por Jiao, Lian e Gu (2008).
Para adaptar o pseudocódigo proposto a linguagem de programação Java utilizada
neste trabalho, desenvolveu-se uma estrutura que permitisse utilizar o algoritmo em um
espaço n dimensional e não apenas tridimensional como é utilizado no simulador PSOView.
O pacote de classes core descrito no seção3.2.4 apresenta com detalhes o relacionamento
entre as classes PSO, Particle e Function, responsáveis pelo funcionamento do
algoritmo.
Seguindo a estrutura proposta, a definição da dimensão em que o algoritmo irá
funcionar deve ser obrigatoriamente definida no método construtor da classe PSO. O Quadro
10 apresenta a implementação do método construtor.
59
Quadro 10 - Método construtor da classe PSO
Fonte: Autor (2012)
O método recebe três parâmetros, n, npt e function os quais representam
respectivamente a dimensão, quantidade de partículas do enxame e função teste a ser
otimizada. Além de inicializar estes parâmetros, todos os objetos do tipo Particle são
instanciados neste momento em função dos parâmetros informados.
Ao instanciar um objeto do tipo Particle deve-se informar obrigatoriamente a
dimensão em que está partícula irá operar. Desta forma instanciam-se os vetores posicao
e velocidade com n referentes à dimensão do problema em que irão se movimentar.
De posse de todos os seus atributos instanciados, para que o algoritmo inicie
processo de otimização basta que seja executado o método run().Durante sua execução o
refinamento de cada partícula é calculado pelo método eval() da função teste.
Este método abstrato da classe abstrata Function possui uma implementação
diferente para cada função teste. Enviando uma partícula por parâmetro ao método, este irá
calcular o fitness da partícula em função do tamanho de seu vetor posição. Desta
forma se a função permitir sua representação em um espaço n dimensional, quem irá definir
a dimensão do problema será a partícula e não a função.
O atributo w da classe PSO representa o peso inercial atual do algoritmo. Este peso é
alterado de acordo com a estratégia de implementação definida. O algoritmo possui duas
opções de função. A estratégia proposta por Jiao, Lian e Gu (2008) e a função diversidade
proposta neste trabalho. O Quadro 11 apresenta a implementação da função diversidade.
public PSO(int n, int npt, Function function) { funcao = function; this.n = n; this.npt = npt; lBest = new Particle(n); lBest.setFitness(null); gBest = new Particle(n); gBest.setFitness(null); fstar = newdouble[nps]; vMax = ((this.funcao.getYUp() - this.funcao.getYLow()) / 2); for (int i = 0; i <nps; i++) { fstar[i] = 10000d; } for (int i = 0; i < npt; i++) { Particle p = new Particle(n); enxame.add(p); p = new Particle(n); bestEnxame.add(p); } enxame = bestEnxame;
}
60
Quadro 11 - Implementação da função diversidade. private void wDiversity2() {
double s1 = 0; double dg = 0; double fi; for (int i = 0; i < npt; i++) { for (int j = 0; j < n; j++) { s1 += Math.pow((enxame.get(i).getPosicao()[j] - gBest.getPosicao()[j]), 2); } dg += Math.sqrt(s1); s1 = 0; } dg /= this.npt; if (dg < dmin) { dmin = dg; } elseif (dg > dmax) { dmax = dg; } fi = ((dg - dmin) / (dmax - dmin)); w = 0.4 * Math.exp(0.86 * fi);
}
Fonte: Autor (2012)
A implementação da função diversidade segue todos os princípios mencionados na
seção 3.1.
3.3.4 Implementação Javascript
Este tópico apresenta como ocorreu à implementação da interface gráfica da função
teste e atualização do enxame de partículas no gráfico.
Para desenhar o gráfico da função em uma página xhtml, utilizou-se a biblioteca
Javascript Graph3D.Esta biblioteca permite criar uma superfície tridimensional a
partir de um conjunto de pontos. Além de construir, ainda implementa rotinas para
aproximar e girar a superfície em todas as direções. A biblioteca utiliza recursos do HTML5
como a tag canvas.
No entanto, como a construção da função é dinâmica, o conjunto de pontos que
compõem a função também é dinâmico, alterando de acordo com a interação do usuário.
Para permitir o carregamento dinâmico do conjunto de pontos a partir de um código
Javascript, sem a necessidade recarregar a página, utilizaram-se os recursos
disponibilizados pela biblioteca DWR. A classe PSOViewAjax implementa os métodos que
serão acessados via código Javascript. O Quadro 12 apresenta os métodos
implementados pela classe.
61
Quadro 12 - Código fonte de classe PSOViewAjax
publicclass PSOViewAjax implements Serializable { privatefinal WebContext wc; public PSOViewAjax() {...} private PSOBean getPSOBean() {...} public float[][] graphPoints() {...} public void changeYlow(float low) {...} public void changeyUp(float up) {...} public void changeDelay(int delay) {...} public void updateDataPoints(Object positions, int sleep) throws
InterruptedException {...} }
Fonte: Autor (2012)
O método graphPoints()é responsável por criar um conjunto de pontos que
serão utilizados na construção da função. O método percorre os eixos da função teste, dentro
de seus limitantes superior e inferior e retorna um vetor do tipo float com 2500 pontos.
Cada ponto é composto por coordenadas x, y e z. A quantidade de pontos interfere
diretamente no nível de detalhes do gráfico e consequentemente no desempenho do sistema.
Definiu-se em 2500 o número de pontos, pois atende as necessidades do sistema com
desempenho relativamente bom.
Antes de iniciar a construção do gráfico, foi necessário definir algumas
configurações tanto para a biblioteca DWR quanto para a API Graph3D. O Quadro 13
apresenta a função fncOnLoad(), a qual é carregada pelo método onload do
componente <h:form> da página index.html e define as configurações necessárias.
Quadro 13 - Código fonte da função fncOnLoad()
function fncOnLoad() { dwr.engine.setActiveReverseAjax(true); dwr.engine.setNotifyServerOnPageUnload(true, true); dwr.engine.setErrorHandler(null); dwr.engine.setAsync(false); google.load('visualization', '1'); google.setOnLoadCallback(drawVisualization); drawVisualization(); }
Fonte: Autor (2012)
62
Os quatro primeiros parâmetros dizem respeito à biblioteca DWR, seguidos dos
parâmetros utilizados pela API Javascript do Googlejsapi.js, a qual é utilizada
pela API Graph3D. Finalmente, a função drawVisualization() é invocada para
construir o gráfico. Este método está armazenado no arquivo psoView.js, e sua
implementação é dada pelo Quadro 14.
Quadro 14 - Código fonte do método drawVisualization()
//Função responsável por desenhar o gráfico da função teste. function drawVisualization() { //Inicializa o objeto e define suas colunas. data = new google.visualization.DataTable(); data.addColumn('number', 'x'); data.addColumn('number', 'y'); data.addColumn('number', 'z'); initPoints(); //Busca o vetor posição no bean gerenciável e o adiciona no objeto data. var vetorPosicoes = []; PSOViewAjax.graphPoints({ callback : function(ret) { vetorPosicoes = ret; }, async : false }); for ( var x = 0; x < vetorPosicoes.length; x++) { data.addRow([vetorPosicoes[x][0], vetorPosicoes[x][1], vetorPosicoes[x][2] ]); } // Opções da superfície. options = { width : "500px", height : "450px", style : "surface", showPerspective : perspective.input.prop('checked'), showGrid : showGrid.input.prop('checked'), showShadow : shadow.input.prop('checked'), keepAspectRatio : keepAspectRatio.input.prop('checked'), verticalRatio : 1, showAxes : showAxes.input.prop('checked') }; // Instancia o gráfico na tela. graph = new links.Graph3d(document.getElementById('desenho')); // Desenha o gráfico. graph.draw(data, options, points); }
Fonte: Autor (2012)
Inicialmente, cria-se um objeto com a estrutura que armazenará o conjunto de
pontos, chamado data. Após instanciado, é feita uma requisição AJAX ao método
graphPoints() da classe PSOViewAjax, adicionando o conteúdo do seu retorno ao
63
objeto data. O parâmetro Async: false, torna a requisição síncrona, desta forma a
execução Javascript aguarda o término da requisição AJAX para prosseguir com a
execução do código. Em seguida são definidos alguns parâmetros de configuração no
atributo options.
Ao instanciar o objeto graph, este recebe por parâmetro o elemento canvas no
qual será desenhado o gráfico. Por fim, o método graph.draw(data, options,
points) desenha o gráfico na tela com o uso dos recursos da API Graph3D.
Os objetos data, points e graph são de escopo global e estão declarados no
arquivo psoView.js. Para permitir visualizar as partículas se movimentando, necessitou-
se alterar o método graph.draw(data, options, points). Este método foi
modificado para poder inserir um terceiro parâmetro, o qual armazena as posições das
partículas. Quando o parâmetro points está vazio o gráfico é desenhado sem pontos.
No instante em que a otimização é iniciada, a cada atualização do enxame de
partículas a classe observável PSO notifica seu observador PSOViewBean que há
atualizações disponíveis. Este por sua vez reenvia a atualização para a classe
PSOViewAjax, a qual irá enviar uma requisição AJAX reverso ao navegador, com a nova
posição do enxame. O Quadro 15 apresenta o método responsável por enviar as atualizações
ao navegador.
Quadro 15- Código fonte do método updateDataPoints
Public void updateDataPoints(Object positions, int sleep) throws InterruptedException { Thread.sleep(sleep); Util util = new Util(wc.getScriptSession()); util.addFunctionCall("drawParticles", positions); }
Fonte: Autor (2012)
O método possui dois parâmetros, positions o qual armazena o vetor com as
posições do enxame, e sleep cuja função é deixar o método inativo pela quantidade de
milissegundos definida pelo usuário. A execução do método é bastante simples, para o
contexto DWR da sessão armazenado no objeto wc do tipo WebContext envia-se uma
chamada a função Javascript drawParticles passando o objeto positions por
parâmetro. O Quadro 16 apresenta com detalhes a implementação do método.
64
Quadro 16 - Código fonte do método drawParticles
function drawParticles(particles) { initPoints(); for ( var i = 0; i < particles.length; i++) { points.addRow([ particles[i][0], particles[i][1], particles[i][2] ]); } graph.redraw(data, points); }
Fonte: Autor (2012)
Esta função Javascript limpa o objeto points e insere as posições das partículas do
enxame nele. Feito isso, solicita ao método graph.redraw(data, points) para
redesenhar a nova posição do enxame em cima do conjunto de pontos do gráfico (data). O
resultado deste método pode ser observado pela Figura 25.
Figura 25- PSOView minimizando a função de Ackley
Fonte: Autor (2012)
Observa-se que as partículas são representadas por esferas de cor rosa, com efeito
gradiente interno branco. A cada atualização, função e partícula são redesenhadas, porém,
este processo é tão rápido que fica imperceptível ao usuário, passando-o a impressão de que
as partículas estão literalmente se movimentando no gráfico, enquanto tudo é redesenhado.
3.4 OPERACIONALIDADE
Esta sessão detalha a operacionalidade das situações descritas nos casos de uso, bem
como a interação entre usuário e simulador.
Ao acessar o sistema PSOView com qualquer navegador compatível, será exibida a
tela inicial do sistema. Esta é a única tela do sistema, e contém todas as funcionalidades
necessárias para executar os casos de uso UC01, UC02 e UC03. A Figura 26 apresenta a tela
inicial.
65
Figura 26 - Tela inicial do simulador PSOView
Fonte: Autor (2012)
Por padrão, o sistema já apresenta uma função teste ao usuário com configurações
predefinidas no idioma português do Brasil. Para alterar a função teste que se deseja
otimizar basta clicar sobre a função atual que o sistema apresentará uma lista com todas as
funções teste implementadas, inclusive a função definida pelo usuário. A Figura 27
apresenta a lista do sistema com as funções teste implementadas.
Figura 27 - Lista de funções teste implementadas
Fonte: Autor (2012)
Ao selecionar uma função qualquer, o sistema irá redesenhar automaticamente o
gráfico da função com as configurações predefinidas. O usuário ainda pode construir a sua
própria função a partir de uma expressão matemática. Para que isto se torne possível basta
selecionar a função Definida pelo Usuário.
66
Ao selecionar está função aparecerá na tela um campo para inserir a expressão
matemática. Por padrão, esta função já vem com a expressão x+y implementada. Para
construir a função basta clicar no caixa de texto Expressão e efetivamente construir
função.
Por definição as variáveis que representam os eixos x e y são respectivamente
representadas por x e y. A caixa de texto auxilia o usuário durante a construção da função
por meio de um auto completar sugerindo as expressões matemáticas suportadas. A Figura
28 apresenta o campo Expressão e suas funcionalidades.
Figura 28 - Campo de entrada para a função matemática
Fonte: Autor (2012)
Enquanto o usuário escreve a expressão da função, o simulador automaticamente
desenha a função assim que encontrar uma expressão válida. A Figura 29 apresenta esta
funcionalidade.
Figura 29 - Simulador desenhando a função durante a inserção da expressão
Fonte: Autor (2012)
Com a função definida, o usuário pode alterar algumas configurações desta função.
Os parâmetros de configuração referem-se ao tamanho dos limitantes e opções de
visualização. A Figura 30 apresenta os parâmetros de configuração disponíveis.
67
Figura 30 - Parâmetros de configuração da função teste
Fonte: Autor (2012)
Os parâmetros yUp e yLow referem-se aos limitantes dos eixos x y da função.
Alterando estes parâmetros o simulador automaticamente redesenhará a função com os
novos parâmetros. Já o parâmetro delay altera intervalo entre as movimentações do
enxame, podendo este ser alterado durante a otimização. Por fim, os parâmetros Eixos,
Grade, Perspectiva, Sombra e Aspecto, não interferem na execução da otimização,
apenas na visualização do gráfico da função. Ao clicar em uma opção, o gráfico será
redesenhado com a nova configuração, inclusive durante a otimização. A Figura 31
apresenta as possíveis configurações de exibição para as funções.
Figura 31 - Possíveis configurações para o gráfico da função. (a) sem parâmetros, (b) com todos os parâmetros
(a) (b)
Fonte: Autor (2012)
Depois de configurar os parâmetros da função, deve-se ajustar os parâmetros de
configuração do algoritmo de otimização. O simulador é bastante flexível, e permite o ajuste
68
de nove parâmetros distintos. A Figura 32 apresenta os parâmetros de configuração do
algoritmo.
Figura 32 - Parâmetros de configuração do PSO
Fonte: Autor (2012)
Todos os parâmetros já vêm com valores predefinidos, estes valores tomam como
base o trabalho de Jiao, Lian e Gu (2008). O parâmetro Função, refere-se a estratégia de
implementação do peso inercial. O sistema apresenta duas estratégias implementadas, a
proposta por Jiao, Lian e Gu (2008) e a diversidade, descrita neste trabalho. Para cada
estratégia, se pode ajustar qualquer um dos oito parâmetros restantes.
Finalmente, clicando no botão Executar, caso os parâmetros informados sejam
válidos o sistema inicia o processo de otimização. A cada iteração o sistema atualiza a
posição do enxame na função teste. Ao término da execução a mensagem de término de
otimização é exibida e a função apresenta o gráfico da função com a solução encontrada. A
Figura 33 ilustra esta funcionalidade.
Figura 33 - Fim do processo de otimização
Fonte: Autor (2012)
69
Para visualizar os demais resultados do processo de otimização, basta clicar no botão
Resultados. Esta ação fará com que uma caixa de dialogo apareça na tela com os
detalhes da solução encontrada. A Figura 34 apresenta a caixa com resultados da otimização.
Figura 34 - Dialogo de resultados da otimização
Fonte: Autor (2012)
Como resultado, o sistema traz apenas os dados mais relevantes da otimização.
Sendo os valores de x, y e z a posição da melhor partícula global do enxame. Iterações
representa a quantidade total de iterações do PSO para encontrar a solução, Chamadas da
função representa o número total de chamadas da função objetivo e W final refere-se
ao peso inercial final do processo.
Como recurso adicional, o sistema ainda permite adequar a posição do gráfico a fim
de melhorar a visualização da função. Para fazer uso deste recurso basta utilizar os recursos
do mouse. A rolagem aproxima ou afasta o gráfico dentro dos limitantes permitidos pelo
sistema. Já para mudar a posição do gráfico, basta pressionar o gráfico com o botão direito e
arrastar para a posição desejada.
Outro recuso interessante do sistema é a possibilidade de alterar o idioma da
aplicação descrito pelo UC01. O sistema apresenta os ícones dos idiomas disponíveis acima
do item Parâmetros do PSO, como mostra a Figura 35.
Figura 35 - Opções de idioma disponíveis no PSOView
Fonte: Autor (2012)
Por padrão o idioma da aplicação é português do Brasil, mas para alterar para Inglês
dos EUA basta clicar sobre o ícone do idioma que a aplicação irá alterar automaticamente. A
Figura 36 apresenta a aplicação no idioma inglês dos EUA.
70
Figura 36 - Aplicação no Idioma inglês dos EUA
Fonte: Autor (2012)
De forma geral, a utilização do simulador é bastante simples, a interface apesar de
prática e intuitiva, ainda apresenta alguns recursos para facilitar a sua utilização. Para todos
os campos ou parâmetros existe uma mensagem que descreve brevemente o que significa ou
faz cada ação ou parâmetro. Durante a execução da otimização uma tag AjaxStatus
posicionada no canto superior esquerdo ilustra ao usuário que o sistema está em execução.
Ao termino da execução este indicador de atividade é oculto.
3.5 COMPARATIVO DAS ESTRATÉGIAS
No intuito de avaliar a eficiência da função diversidade no PSO, utilizou-se os 9
conhecidos problemas de otimização implementados no simulador PSOView. Apesar de
possuírem as mais diversas características, espaço, solução e grau de multimodalidade
apenas a função de Tripod não possui nenhum ponto de mínimo global localizado em 0,
sendo este situado em -1. Todos os testes foram executados 5 vezes no simulador PSOView
com dimensão fixa em 2.
O mesmo teste é realizado com a estratégia de variação do peso inercial proposta por
Jiao, Lian e Gu (2008), a qual utiliza o número de iteração para variar o valor de w. Neste
trabalho o autor sugere um valor entre [1.0001, 1.005] para o parâmetro u da equação a
-kiter
iw = w *( )u . Este parâmetro determina se o algoritmo irá diminuir o peso inercial mais
rapidamente ou não. Desta forma, 1.0001 proporciona maior exploração enquanto 1.005
proporciona maior convergência. Nos testes realizados utilizou-se u=1.005. Como as
funções teste estão em um espaço bidimensional, este valor garante boas taxas de exploração
e convergência nesta situação (JIAO; LIAN; GU, 2008). Para todos os casos de teste
utilizou-se um número máximo de iterações igual a 2000, coeficientes cognitivo e social
igual a 2.0, erro de parada em 10-3
e enxame com 40 partículas.
Para cada função e estratégia avaliou-se o melhor resultado das 5 execuções e
também o resultados médio obtido para a solução encontrada e número de iterações. Os
71
resultados dos testes podem ser observados pela Tabela 1, Onde ES representa o espaço
solução, M o valor do mínimo global da função e Iter. o número de iterações.
Tabela 1 - Comparativo entre a função de Jiao, Lian e Gu (2008) e a função diversidade
Função ES M
Jiao, Lian e Gu (2008) Diversidade
Melhor Médio Melhor Médio
Resultado Iter. Resultado Iter. Resultado Iter. Resultado Iter.
Ackley -32/32 0 4,26E-04 138 2,18E-03 142,8 7,60E-04 70 2,22E-03 67,8
Alpine -5,12/5,12 0 3,47E-04 102 2,07E-03 99,2 9,16E-04 46 1,68E-03 56,2
Griewank -600/600 0 3,95E-02 2000 1,92E-01 2000 2,71E-02 2000 1,11E-01 1621,2
Rastrigin -5,12/5,12 0 9,95E-01 2000 1,99E+00 2000 2,07E-04 503 1,59E+00 1700,6
Rosenbrock -100/100 0 9,29E-04 188 1,88E+01 916,6 9,78E-05 109 1,58E-03 99,2
Schaffer -600/600 0 9,74E-03 159 3,33E-02 530,4 9,72E-03 2000 9,78E-03 485,2
Schwefel -500/500 0 -8,38E+02 155 -7,43E+02 1267,8 9,72E-03 112 2,07E-02 846,8
Sphere -5,12/5,12 0 1,71E-04 105 3,86E-04 103 4,65E-05 29 2,93E-04 39,4
Tripod -100/100 -1 -9,99E-01 158 -5,99E-01 887,4 -1,00E+00 58 -5,99E-01 52,4
Fonte: Autor (2012)
Em 6 das 9 funções teste a função diversidade encontrou uma solução melhor que a
proposta de Jiao, Lian e Gu (2008). Para os demais casos a diferença entre as soluções é
muito pequena, os melhores resultados estão sublinhados na Tabela 1. Na comparação é
notável o número reduzido de iterações na função diversidade. Para os resultados médio, a
função diversidade demonstrou resultados ainda melhores, obteve solução mais adequada
para 7 funções.
72
4 CONCLUSÕES
Todos os objetivos propostos neste trabalho foram cumpridos, o simulador se
mostrou uma ferramenta eficiente e flexível para visualização do processo de minimização,
servindo até mesmo como uma ferramenta didática no ensino de Swarm Intelligence. Já a
proposta de variação do peso inercial, se mostrou bastante promissora, apesar de demandar
maiores esforços na compreensão de seu desempenho em problemas com espaço n-
dimensional.
Todas as tecnologias utilizadas para desenvolver o simulador se mostraram bastante
eficientes. Em geral, o simulador apresenta uma interface gráfica intuitiva e amigável,
permitindo a utilização de todos os recursos do simulador em qualquer navegador
compatível com HTML5 em uma única tela. Outro grande diferencial é a independência de
plataforma ou qualquer outro recurso adicional como JRE ou Java3D.
A possibilidade de criar funções teste a partir de expressões matemáticas se mostrou
bastante eficiente, pois permite ao usuário criar, visualizar e minimizar seus próprios
problemas de otimização de maneira rápida e intuitiva.
Como grande parte do que vem sendo publicado a respeito do PSO é em inglês, a
possibilidade de alterar o idioma do simulador para o inglês é garantia de uma maior
probabilidade de popularização no meio acadêmico.
A estratégia de variação do peso inercial se mostrou superior a estratégia de Jiao,
Lian e Gu (2008) para problemas de minimização com 2 dimensões, pois foi capaz de
encontrar soluções melhores e com números de iterações consideravelmente menor que os
da estratégia comparada. No entanto, para problemas onde o espaço solução é maior, o
algoritmo apresentou desempenho inferior. Fato que leva a crer que a função diversidade
precisa aprimorar sua habilidade de escapar de mínimos locais.
O Quadro 17 apresenta os recursos utilizados na comparação do simulador PSOView
com os trabalhos correlatos.
73
Quadro 17 - Comparação entre PSOView e trabalhos correlatos
Recurso PSOVis PSO
Visualization PSOView
Criar função teste X
Alterar limites inferiores e superiores
da função X
X
Exibir eixos da função X X
Exibir grade da função X X
Exibir gráfico com perspectiva
isométrica8
X
Exibir gráfico com sombra X
Exibir gráfico com proporção9 X
Visualizar função em 3D X X X
Girar gráfico X X X
Aproximar gráfico X
Exibir movimentação das partículas X X X
Alterar o intervalo de atualização da
posição das partículas X
X
Alterar os parâmetros do PSO X X
Cross-Browser X X X
Requer Java 3D instalado X
Requer JRE instalado X X
Permite pausar ou interromper a
otimização X
Permite execução passo a passo X
Diferencia a melhor solução do
enxame. X X
Exibe o mínimo global da função X
Multi-idioma X
Estratégia de implementação do peso
inercial
Constriction
Standard Standard
Jiao, Lian e Gu
(2008)
Diversidade Fonte: Autor (2012)
Em comparação com os trabalhos correlatos o simulador se mostrou superior na
maioria dos recursos comparados, perdendo apenas em alguns detalhes dos quais destacam-
se: a execução passo a passo e pausa do processo de otimização, diferenciação da melhor
partícula global, exibição do mínimo global da função, entre outros.
8 Perspectiva isométrica é o processo de representação tridimensional em que o objeto se situa num sistema de
três eixos coordenados (axonometria). Estes eixos, quando perspectivados, fazem entre si ângulos de 120°:
9Relação proporcional entre altura e largura da imagem.
74
4.1 DIFICULDADES ENCONTRADAS
No decorrer do desenvolvimento deste trabalho muitas dificuldades foram
encontradas. Porém, com esforço e dedicação, todas puderam ser superadas. Entre todas
destacam-se a construção do gráfico da função, implementação do AJAX reverso,
implementação da arquitetura do PSO e a construção da função definida pelo usuário.
Durante as tentativas de representar o gráfico da função em uma tag canvas,
inúmeras bibliotecas de terceiros foram utilizadas durante os testes, mas apenas a Graph3D
se mostrou customizável o bastante para atender as necessidades do simulador.
Encontrar uma técnica capaz de atualizar a posição das partículas do enxame do PSO
no navegador do usuário durante a execução da otimização, mostrou-se uma tarefa bastante
árdua. Inicialmente tentou-se utilizar técnicas nativas do JSF e PrimeFaces, apenas o
PrimeFaces poderia atender a está necessidade, com a utilização do componente PrimePush.
No entanto, esta estratégia necessitaria de um servidor Jetty, o que inviabilizaria sua
implementação no simulador. Para atender a esta necessidade utilizou-se a técnica AJAX
reverso disponibilizada pela biblioteca DWR, a qual se mostrou bastante eficiente na
resolução do problema.
Desenvolver uma estrutura orientada a objetos para atender as necessidades do PSO
e da função tornou-se uma tarefa bastante custosa. Havia a necessidade de utilizar a estrutura
tanto nas classes Java quanto nos arquivos Javascript. Porém, a estrutura desenvolvida
mostrou-se bastante flexível, permitindo a implementação do PSO e função em um espaço
n-dimensional de forma transparente, requerendo apenas a correta implementação das
funções teste.
Por fim, a construção de funções definidas pelo usuário no início do projeto parecia
ser um desafio. Todavia, após encontrar a biblioteca Math Evaluator este processo ficou
simples em nível de implementação, necessitando apenas construir as rotinas necessárias
para validar as equações informadas pelo usuário.
4.2 EXTENSÕES
Para construir um simulador ainda mais completo e flexível caberia à implementação
de algumas rotinas adicionais, entre elas destacam-se:
a) Permitir ao sistema executar funções teste em um espaço n-dimensional;
75
b) Aprimorar os mecanismos que auxiliam na construção da função definida
pelo usuário;
c) Avaliar a função diversidade em problemas com espaço n-dimensional;
d) Inserir o idioma alemão ao simulador, já que é notável o número de
publicações nesta língua;
e) Desenvolver rotinas que permitam pausar, interromper e executar passo a
passo a otimização;
f) Permitir que o sistema armazene as funções definidas pelo usuário quando
necessário.
76
REFÊRENCIAS
ABRAHAM, P.; PANT, M.; THANGARAJ, R. Particle Swarm Optimization: Performance
Tuning and Empirical Analysis. Foundations of Computer Intelligence. Berlin, v.3, p.
101-128. 2009.
ACKLEY, D. H. A connectionist machine for genetic hill climbing. Boston: Kluwer
Academic Publishers, 1987.
ALLPORT, A. The historical background of social psychology. In: G. LINDZEY & E.
ARONSON (Eds.). Handbook of social psychology. New York: Anais…New York:
Random House, v.1, ed. 3. p.1-46, 1985.
BÄCK, T. Evolutionary algorithms in theory and practice. Oxford, Oxford University
Press, 1996.
BOEKEL, R. V. Por dentro do PrimeFaces 2.2. Java Magazine. Edição 93, 2011.
BONABEAU, E.; DORIGO, M.; THÉRAULAZ, G. Swarm intelligence: from natural to
artificial systems. Oxford, Oxford University Press, 1999.
CHAP Links Library. Versão 1.2. Rotterdom, Holand: Almend BUNC, 2012. Disponível
em: http://chap.almende.com. Acesso em: 05 out. 2012.
CHATERJEE, A.; SIARRY, P. Nonlinear Inertia Weight Variation for Dynamic Adaptation
in Particle Swarm Optimization. Computers e Operations Research, v. 33, p. 859-871,
2004.
CLERC, M. The swarm and the queen: towards a deterministic and adaptive particle
swarm optimization. Proc. I999 ICEC, Washington, DC, p. 1951 - 1957, 1999.
DEL VALLE, Y.; VENAYAGAMOORTHY, G. K.; MOHAGHEGHI, S.; HERNANDEZ,
J. C.; HARLEY, R. G. Particle Swarm Optimization: Basic Concepts, Variants and
Applications in Power Systems. IEEE Transactions One Evolutionary Computational, v.
12, n. 2, 2008. Disponível em: <http://ieeexplore.ieee.org>. Acesso em: 20 jun. 2008.
DIRECT Web Remoting. Versão 3.1.rc1, 2012. Disponível em:
<www.directwebremoting.org/dwr/index.html>. Acesso em: 25 out. 2012.
EBERHART, R. C.; SHI, Y. Comparing Inertial Weights and Constriction Factors in
Particle Swarm Optimization. In: PROCEEDINGS OF THE IEEE CONGRESS ON
EVOLUTIONARY COMPUTATION (CEC), 2000. p. 84-88. Anais eletrônicos...
Disponível em:<http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=870279>. Acesso
em: 20 out. 2011.
GIL, A. C. Como Elaborar Projetos de Pesquisa. 5. Ed. São Paulo: Atlas, 2008.
77
GRAPHING Calculator. Versão 3.0. Ben McCormick, Egor Poblaguev, 2012 Disponível
em: <www.code.google.com/p/graphingcalculator>. Acesso em: 15 out. 2012.
GRIEWANK, A. O. Generalized Decent for Global Optimization. Journal
of Optimization Theory and Applications. 34, p. 11-39, 1981.
GROSAN, C., ABRAHAM, A., NICOARA, M.: Search Optimization Using Hybrid
Particle Sub-Swarms and Evolutionary Algorithms. International Journal of
Simulation Systems, Science & Technology, UK 6(10&11), p. 60-79, 2005.
HARRELL, C. R.; MOTT, J. R. A.; BATEMAN, R.E.; BOWDEN, R. G.; GOGG, T. J.
Simulação otimizando os sistemas. ed. 1. São Paulo: IMAM e Belge Simulação, 2002.
JIAO, B.; LIAN, Z.; GU, X. A dynamic inertia weight particle swarm optimization
algorithm. Chaos Solitons & Fractals. ed. 37. p.698-705, 2008. Disponível em:
http://www.sciencedirect.com . Acesso em: 15 jan. 20011.
KENNEDY, J., EBERHART, R. C., SHI. Y. Swarm Intelligence. United States of
America: Elsevier, 2001.
LENIN, K; MOHAN, M.R. Attractive and Repulsive Particle Swarm Optimization for
Reactive Power Optimization. Journal of engineering and Applied Science. p. 288-292.
2006.
LIU, H.; ABRAHAM, A.; ZHANG, W. A Fuzzy AdaptiveTurbulent Particle Swarm
Optimization. International Journal of Innovative Computing and applications, p. 39-
47, 2007.
LOCATELLI, M. A note on the Griewank test function. Journal of Global Optimization.
ed. 25. p. 169–174, 2003.
LUCKOW, D. H; MELO, A. A. Programação Java para a Web. São Paulo: Novatec,
2010.
PANT, M., RADHA, T., SINGH, V.P. Particle Swarm Optimization: Experimenting the
Distributions of Random Numbers. In: 3RD INDIAN INTERNATIONAL CONFERENCE
ON ARTIFICIAL INTELLIGENCE India. Anais… India: IICAI, p. 412-420 2007.
PANT, M; THANGARAJ, ABRAHAM, R. Particle Swarm Optimization: Performance
Tuning and Empirical Analysis. Foundations of Computer Intelligence, v. 3. SCI203, p.
101-128, 2009.
PARSOPOULOS, K. E.; VRAHATIS, M. N. Recent Approaches to Global Optimization
Problems through Particle Swarm Optimization. Natural Computing, v. 1, p. 235-306,
2002.
POLI, R.; KENNEDY, J.; BLACKWELL, T. Particle Swarm Optimization: An overview.
Swarm Intelligence. v. 1. p. 33-57, 2007.
78
PRIME Faces User Guide. Versão 3.4. Optimus Prime: Prime Faces, 2012. Disponível em:
<http://primefaces.googlecode.com/files/primefaces_users_guide_3_3.pdf>. Acesso em: 03
out. 2012.
PSOVIS: Modlab. Versão 1.0. [S.I.], 2005. Disponível em: <www.gecco.org.chemie.uni-
frankfurt.de/PsoVis/index.html>. Acessado em: 16 out. 2012.
PSO Visualization. Versão 1.0. Kent Fritch, 2004. Disponível em:
<www.projectcomputing.com/resources/psovis>. Acesso em: 16 out. 2012.
MÜHLENBEIN, H.; SCHOMISCH BORN, D. J.The Parallel Genetic Algorithm as
Function Optimizer. Parallel Computing, ed. 17, p. 619-632, 1991.
OLORUNDA, O; ENGELBRECHT, A. P. Measuring exploration/exploitation in particle
swarms using swarm diversity. IEEE Congress on Evolutionary Computation. p.1128-
1134, 2008.
RADHA, M. P; SINGH, V. P. A Simple Diversity Guided Particle Swarm Optimization.
IEEE In: CONGRESS ON EVOLUTIONARY COMPUTATION, 2007.
RESENDE, M. G. C.; STEWART, W. R.; KELLY, J. P.; GOLDEN, B. L.; BARR, R. S.
Designing and Reporting on Computational Experiments with Heuristic Methods. Journal
of Heuristics, ed. 1. p. 9-32, 1995.
RICHARDS, M.; VENTURA, D. Dynamic sociometry in particle swam optimization. In:
PROCEEDINGS OF THE SIXTH INTERNATIONAL CONFERENCE ON
COMPUTATIONAL INTELLIGENCE AND NATURAL COMPUTING. North
Carolina. Anais… North Carolina. p. 1.557-1560, 2003.
RIGET, J.; VESTERSTROM, J. S. A diversity-guided particle swarm optimizer – the
ARPSO. In: EVALIFE TECHNICAL REPORT n. 02. 2002.
ROSENBROCK, H. H. An automatic method for finding the greatest or least value of a
function. The Computer Journal, p. 175-184. 1960.
SCHWEFEL, H. P. Numerical Optimization of Computer Models. John Wiley & Sons,
1981.
SHI Y.; EBERHART R. A modified particle swarm optimizer. Proc. IEEE Int.
Conf on Evolutionary Computation , p.69-73, 1998.
SHI Y.; EBERHART R. Empirical Study of Particle Swarm Optimization. Proceedings of
the IEEE Congress on Evolutionary Computation. p. 1945-1950, 1999.
SHI, Y. Particle Swarm Optimization. Eletronic Data Systems, Inc. Kokomo, IN 46902,
USA, IEEE Neural Networks Society, 2004.
SIMÕES, C.; PAIVA, J. Metodologias de Investigação em Educação. Lisboa: Fundação
Calouste Gulbenkian, 2004.
79
THOMAS, N., REED, M. A hybrid algorithm for continuous optimization. In: IEEE
CONGRESS ON EVOLUTIONARY COMPUTATION Trondheim. Anais… Trondheim:
IEEE 2009, p. 2584-2589, 2009.
VAN DEN BERGH, F.; ENGELBRECHT, A.P. A Study of Particle Swarm Optimization
Particle Trajectories. Information sciences ed. 176 p. 937-971, 2006. Disponível em:
www.elsevier.com/locate/ins>. Acesso em: 15 set. 2011.
WHITE, T.; PAGUREK, B.; Towards Multi-Swarm Problem Solving in networks. In:
PROCEEDINGS THIRD INTERNATIONAL CONFERENCE ON MULTI-AGENT
SYSTEMS. ICMAS ’98, p. 333-340, 1998.
ZHAN, Z-H.; ZHANG, J; LI, Y; CHUNG, H.S-H. Adaptive particle swarm optimization.
IEEE Transactions on Systems Man, and Cybernetics - Part B: Cybernetics, v. 39.. p. 1362-
1381, 2009.
ZUBEN, F. J. V.; ATTUX, R. R. F. Inteligência de Enxame. São Paulo: Unicamp, 2008.
