ads:
Universidade de Pernambuco
Escola Politécnica de Pernambuco
Departamento de Sistemas e Computação
Programa de Pós-Graduação em Engenharia da Computação
Danilo Ferreira de Carvalho
Roteamento em Redes Ópticas Transparentes
Utilizando Otimização por Colônias de Formigas
Dissertação de Mestrado
Recife, 10 de julho de 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
UNIVERSIDADE DE PERNAMBUCO
DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA DA COMPUTAÇÃO
DANILO FERREIRA DE CARVALHO
Roteamento em Redes Ópticas Transparentes
Utilizando Otimização por Colônias de Formigas
Dissertação apresentada como requisito parcial
para a obtenção do grau de Mestre em Engenharia
da Computação
Prof. Dr. Carmelo José Albanez Bastos Filho
Orientador
Recife, 10 de julho de 2008
ads:
CIP – CATALOGAÇÃO NA PUBLICAÇÃO
Carvalho, Danilo Ferreira de
Roteamento em Redes Ópticas Transparentes Utilizando
Otimização por Colônias de Formigas / Danilo Ferreira de Car-
valho. – Recife: PPGEC da UPE, 2008.
90 f.: il.
Dissertação (mestrado) – Universidade de Pernambuco. Pro-
grama de Pós-Graduação em Engenharia da Computação, Recife,
BR–PE, 2008. Orientador: Carmelo José Albanez Bastos Filho.
1. Computação inteligente. 2. ACO. 3. PSO. 4. Clã-PSO.
5. Comunicações ópticas. 6. RWA. I. Bastos Filho, Carmelo José
Albanez. II. Título.
A meu pai, que sonhou comigo a conclusão
desse mestrado, porém está hoje presente
apenas em meu coração para ver esse
sonho concluído, dedico esta vitória.
Agradecimentos
Antes de tudo aos meus pais, Roberto e Neurinete Carvalho, pelo carinho, amor e atenção
que sempre tiveram por mim e pelos ensinamentos de vida que me proporcionaram,
fazendo de mim o que eu sou hoje.
Às minhas irmãs, Priscila e Melissa Carvalho, presenças constantes em minha vida,
pela alegria e compreensão que sempre me deram.
À Renata Medeiros, que me auxiliou diretamente tanto na parcela emocional quanto
na intelectual dessa dissertação.
Ao professor Carmelo José Albanez Bastos Filho, que contribuiu e continua con-
tribuindo diretamente para minha formação, proporcionando-me conhecimento e me gui-
ando nos estudos realizados.
A João Murilo e Manoel Heleno, meus antigos supervisores e amigos, pelo incentivo
para que eu iniciasse o curso, mesmo quando precisei deixar a Equipe de Fronteiras.
A todos os professores do Departamento de Sistemas e Computação da Universidade
de Pernambuco, por me instruírem da melhor forma no decorrer do mestrado.
Aos colegas Anthony, Bernardo, César, Diogo, George, Petrônio, Thyago e Wesnaida
e a todos os outros colegas de curso, pelos momentos vivenciados, pelos conhecimentos
compartilhados, pelos auxílios nos trabalhos, enfim, pelo companheirismo na luta para
conseguir concluir nosso objetivo comum.
A Daniel Chaves do Grupo de Fotônica da UFPE, pelo auxílio na utilização da ferra-
menta para simulações em redes ópticas.
Sumário
LISTA DE FIGURAS . . .............................. vi
RESUMO . . . . . .................................. ix
ABSTRACT . . . .................................. x
1 INTRODUÇÃO . . . .............................. 1
1.1 Utilização de redes ópticas . . . ....................... 1
1.2 O problema de roteamento e alocação de comprimento de onda . . . . . . . 2
1.3 Motivação e objetivos . . . . . . ....................... 2
1.4 Aplicação de inteligência de enxames . . . . . ................ 3
1.4.1 Algoritmos de formigas . . . . . ....................... 3
1.5 Organização desta monografia . . ....................... 4
2 OTIMIZAÇÃO POR COLÔNIAS DE FORMIGAS . . . . ......... 5
2.1 O Ambiente de uma Colônia de Formigas . . ................ 5
2.2 O Experimento das Duas Pontes e o Modelo Desenvolvido por Deneubourg 6
2.3 Modelo artificial para formigas . ....................... 8
2.3.1 Ambiente . . .................................. 8
2.3.2 Mecanismos .................................. 9
2.3.3 Definição do algoritmo de ACO para busca do menor caminho em um grafo 11
3 ALGORITMODEBUSCAUTILIZADOPARASELEÇÃO PARAMÉTRICA
DOACO..................................... 15
3.1 Otimização por enxames de partículas . . . . ................ 15
3.1.1 Origem do Modelo de Partículas ....................... 15
3.1.2 O Algoritmo PSO . .............................. 16
3.2 Diferentes formas: modelos de velocidade . . ................ 21
3.2.1 Fator de inércia . . .............................. 21
3.2.2 Coeficiente de constrição . . . . ....................... 22
3.3 Troca de informação .............................. 22
3.4 Variação das estruturas sociais: topologias . . ................ 24
3.5 Otimização por enxames de partículas baseada em clãs . . ......... 26
3.5.1 O conceito do clã de partículas . ....................... 26
3.5.2 Eleição do líder . . .............................. 27
3.5.3 A conferência de líderes . . . . . ....................... 27
3.5.4 O retorno de informação para cada clã . . . . ................ 29
3.5.5 Experimentos . . . .............................. 29
3.6 Resultados das simulações . . . . ....................... 31
3.6.1 Rosenbrock .................................. 31
3.6.2 Rastrigin . . .................................. 33
3.6.3 Griewank . . .................................. 34
3.6.4 Comparação entre as topologias de clusters e de clãs . . . . ......... 37
4 ROTEAMENTO E ALOCAÇÃO DE CANAIS ÓPTICOS TRANSPAR-
ENTES . . . . .................................. 40
4.1 Caracterização do problema . . . ....................... 40
4.1.1 Roteamento e Alocação de Comprimentos de Onda (RWA, Routing and
Wavelength Assignment)............................ 42
4.2 Roteamento .................................. 43
4.2.1 Roteamento fixo . . .............................. 43
4.2.2 Roteamento fixo-alternativo . . . ....................... 44
4.2.3 Roteamento adaptativo . . . . . ....................... 45
4.2.4 Algoritmos de roteamento . . . . ....................... 45
4.3 Algoritmos de alocação de comprimentos de onda . . . . . ......... 47
4.3.1 O Problema de alocação de comprimentos de Onda . . . . ......... 47
4.3.2 Formulação do problema . . . . ....................... 48
4.3.3 Heurísticas de alocação . . . . . ....................... 49
4.4 Roteamento utilizando técnicas de computação inteligente . ......... 50
5 NOVO ALGORITMO DE RWA BASEADO EM ACO PARA REDES ÓP-
TICAS . . . . .................................. 52
5.1 Modelo baseado na distância do enlace . . . . ................ 52
5.1.1 Otimização dos parâmetros . . . ....................... 54
5.1.2 Análise da variação do tempo de busca (T
busca
)................ 57
5.2 Modelo adaptado à redes ópticas ....................... 61
5.2.1 Modelo óptico . . . .............................. 61
5.2.2 Simulações e resultados . . . . . ....................... 64
6 CONCLUSÕES E TRABALHOS FUTUROS ................ 73
6.1 Conclusões . .................................. 73
6.2 Trabalhos Futuros . .............................. 75
APÊNDICE A PSS - PSO SIMULATION SHELL . . . . . . ......... 77
A.1 A ferramenta .................................. 77
APÊNDICE B LISTA DE PUBLICAÇÕES . . . ................ 81
ANEXO A BOX PLOT .............................. 82
A.1 O boxplot ................................... 82
REFERÊNCIAS . .................................. 85
Lista de Figuras
Figura 2.1: Experimentodasduaspontes realizado porDeneubourg (DENEUBOURG;
ARON; GOSS, 1990) usando (a) r = l
l
/l
s
= 1 e (b) r = l
l
/l
s
= 2. . . . 6
Figura 2.2: Esquemado experimentorealizado por Deneubourg(DENEUBOURG;
ARON; GOSS, 1990) para demonstrar o modo como as formigas são
induzidas pela concentração de feromônio. . . . . . ......... 7
Figura 2.3: Modelos de grafos baseados no experimento das duas pontes. . . . . 9
Figura 2.4: Uma formiga artificial construindo uma solução. . . ......... 10
Figura 3.1: Representação do comportamento de duas partículas: (a) no instante
t e (b) no instante t + 1.......................... 17
Figura 3.2: Representação do comportamento de uma vizinhança de partículas
no instante t. .............................. 18
Figura 3.3: Estruturaspadrão: (a) Topologiaestrela usada com gbest e (b) Topolo-
gia anel usada com lbest (adaptados de (BRATTON; KENNEDY,
2007)). . . . .............................. 23
Figura 3.4: Topologia focal. . . . . . ....................... 25
Figura 3.5: Topologia Von Neumann. ....................... 25
Figura 3.6: Topologia de quatro grupos que faz uso de informantes estáticos já
definidos no início da simulação (adaptado de (ENGELBRECHT,
2005)). . . . .............................. 25
Figura 3.7: Partículas organizadas em grupos menores, denominados clãs. . . . . 26
Figura 3.8: Eleição dos líderes de cada clã. . . . . . ................ 27
Figura 3.9: Troca de informação realizada na conferência global de líderes na
topologia de clãs. . . . . . ....................... 28
Figura 3.10: Trocade informação realizada na conferência local de líderesna topolo-
gia de clãs. . .............................. 28
Figura 3.11: Fluxo de informação dentro de cada clã após a conferência. . . . . . 29
Figura 3.12: Simulação com a função Rosenbrock usando clãs com conferência
global. . . . .............................. 31
Figura 3.13: Simulação com a função Rosenbrock usando clãs com conferência
local. .................................. 32
Figura 3.14: Simulação com a função Rastrigin usando clãs com conferência global. 33
Figura 3.15: Simulação com a função Rastrigin usando clãs com conferência local. 33
Figura 3.16: Simulação com a função Griewank usando clãs com conferência global. 35
Figura 3.17: Simulação com a função Griewank usando clãs com conferência local. 35
Figura 3.18: Comparação entre as topologias de grupos e de clãs para a função
Rosenbrock. .............................. 37
Figura 3.19: Comparação entre as topologias de grupos e de clãs para a função
Rastrigin. . . .............................. 38
Figura 3.20: Comparação entre as topologias de grupos e de clãs para a função
Griewank. . . .............................. 39
Figura 4.1: Rede WDM com comprimentos de onda {λ
0
,λ
1
,λ
2
,λ
3
} e três light-
paths C1, C2eC3 definidos. . . . . . . ................ 41
Figura 4.2: Diagrama de uma rede óptica WDM mostrando duas rotas diferentes
utilizando λ
1
e λ
2
. ........................... 42
Figura 4.3: Rota fixa entre os nós 0 e 4 definida através do menor custo. . . . . . 44
Figura 4.4: Rotas fixas alternativas entre os nós 0 e 4. . . . . . . ......... 44
Figura 4.5: Rotas achada por roteamento adaptativo entre os nós 0 e 1. . . . . . . 45
Figura 4.6: Exemplo de rede contendo diferentes informações que poderão ser
utilizadas nas funções de custo dentro do algoritmo de menor custo. . 46
Figura 4.7: Fluxograma do algoritmo baseado em Figura de ruído. . . . . . . . . 48
Figura 4.8: Grafo de coloração de comprimentos de onda construído para uma
dada rede. . . .............................. 49
Figura 5.1: Fluxograma do processo de otimização usando PSO para encontrar
os parâmetros α e β da equação 5.1. . . ................ 55
Figura 5.2: Fluxograma da simulação ACO x Dijkstra para uma chamada. . . . . 56
Figura 5.3: Estrutura da rede NSFNet dos EUA utilizada nas simulações. . . . . . 57
Figura 5.4: Variação do erro pelo tempo de busca usando valores 4N;3, 5N;3N e
2, 5N número de iterações usadas pelas formigas na procura de cada
rota dentro da rede NSFNet. ...................... 58
Figura 5.5: Variação do erro pelo tempo de busca usando valores 2N;1, 5N e1N
número de iterações usadas pelas formigas na procura de cada rota
dentro da rede NSFNet.......................... 59
Figura 5.6: Estrutura da rede de teste de menor porte utilizada na segunda etapa
das simulações com variação de T
busca
. ................ 60
Figura 5.7: Variação do tempo de busca usando valores 2N;1, 5N e1N número
de iterações usadas pelas formigas na procura de cada rota dentro da
rede de teste. .............................. 60
Figura 5.8: Enlace óptico contendo os dispositivos considerados nas simulações. 62
Figura 5.9: Curva de convergência do PSO com estrutura global aplicado à rede
de teste utilizando o ACO padrão. . . . ................ 65
Figura 5.10: Curva de convergência do PSO com estrutura local aplicado à rede de
teste utilizando o ACO padrão. . . . . . ................ 65
Figura 5.11: Comparação entre os valoresde probabilidadede bloqueio conseguidas
pelos algoritmos de roteamento com a variação de carga utilizando o
ACO padrão aplicado à rede de teste. . ................ 66
Figura 5.12: Curva de convergência do PSO com estrutura global aplicado à rede
NSFNet utilizando o ACO padrão. . . . ................ 67
Figura 5.13: Curva de convergência do PSO com estrutura local aplicado à rede
NSFNet utilizando o ACO padrão. . . . ................ 67
Figura 5.14: Comparação entre os valoresde probabilidadede bloqueio conseguidas
pelos algoritmos de roteamento com a variação de carga utilizando o
ACO padrão aplicado à rede NSFNet. ................. 68
Figura 5.15: Curva de convergência do PSO com estrutura global aplicado à rede
de teste utilizando o ACO proposto. . . ................ 69
Figura 5.16: Curva de convergência do PSO com estrutura local aplicado à rede de
teste utilizando o ACO proposto. . . . . ................ 69
Figura 5.17: Comparação entre os valoresde probabilidadede bloqueio conseguidas
pelos algoritmos de roteamento com a variação de carga utilizando o
ACO proposto aplicado à rede de teste. ................ 70
Figura 5.18: Curva de convergência do PSO com estrutura global aplicado à rede
NSFNet utilizando o ACO proposto. . . ................ 71
Figura 5.19: Curva de convergência do PSO com estrutura local aplicado à rede
NSFNet utilizando o ACO proposto. . . ................ 71
Figura 5.20: Comparação entre os valoresde probabilidadede bloqueio conseguidas
pelos algoritmos de roteamento com a variação de carga utilizando o
ACO proposto aplicado à rede NSFNet. ................ 72
Resumo
A necessidade de melhorar os serviços de telecomunicações tem crescido rapidamente, e
isso se dá pela importância que as redes de telecomunicações, juntamente com a Internet,
tomaram dentro da sociedade atual. Esse crescimento eleva a necessidade de melhorias e
pesquisas relacionadas à área de comunicações. Essa dissertação retrata a necessidade de
melhorar o desempenho de processos que constituem essas comunicações, mais especifi-
camente na área de comunicações ópticas transparentes.
Técnicas de Computação Inteligente (CI, Computational Intelligence) são aqui es-
tudadas para tornar possível a aplicação das mesmas a um problema inerente às redes
ópticas WDM (Wavelength Division Multiplexing) chamado de roteamento e alocação de
comprimento de ondas (RWA, Routing and Wavelength Assignment).
Devido à dificuldade em considerar efeitos diversos da camada física durante o pro-
cesso de RWA, torna-se o objetivo principal dessa dissertação utilizar a técnica de com-
putação inteligente baseada em colônias de formigas (ACO, Ant Colony Optimization)
para criar um novo algoritmo de roteamento e aplicá-lo ao problema de RWA, podendo
assim levar em consideração diversos efeitos dentro desse processo.
Algoritmos de CI são em geral simples, porém possuem requisitos específicos, como
parâmetros a serem utilizados. Para elevar o desempenho do algoritmo de ACO, foi uti-
lizada uma técnica baseada em Inteligência Computacional de Enxames (CSI, Compu-
tational Swarm Intelligence) para buscar e definir quais os melhores valores a serem as-
sumidos pelos parâmetros do ACO. A técnica aplicada foi a Otimização por Enxames de
Partículas (PSO, Particle Swarm Optimization), que é uma técnica de otimização recente.
A técnica de PSO foi estudada e melhorada, gerando uma nova abordagem denomi-
nada otimização por enxames de partículas baseada em clãs. Essa nova abordagem tornou
possível o algoritmo de PSO convergir para soluções de alta qualidade rapidamente, e
ao mesmo tempo evitar que o enxame se detenha em mínimos locais. A idéa por trás
dessa abordagem proposta está em aliar a rapidez da estrutura de partículas global (gbest,
baseada na comunicação global) à qualidade das soluções encontradas pela estrutura local
(lbest, baseada na comunicação usando diferentes vizinhanças) em um só algoritmo.
Com os parâmetros definidos, diversos experimentos foram realizados utilizando o
ACO para roteamento chegando a resultados satisfatórios, que mostram a viabilidade da
aplicação do algoritmo de ACO proposto no problema de RWA para redes ópticas.
Palavras-chave: Computação inteligente, ACO, PSO, Clã-PSO, Comunicações ópticas,
RWA.
xiii
Abstract
Transparent Optical Networks Routing Using Ant Colony Optimization
The development of better telecommunication services has been increasing very fast.
This may be explained by the associated importance to telecommunication networks and
Internet for modern society. Consequently, it requires many new researches and improve-
ments in this communication area. This dissertation addresses this area, especially the
sub-area of optical networks.
Some Computational Intelligence (CI) techniques are studied in this work in order to
make possible their application in an Wavelength Division Multiplexing (WDM) optical
network problem called RWA (Routing and Wavelength Assignment).
Some physical layer effects during the RWA process are very sorely considered. Be-
cause of this, the main goal of this work is to make use of the CI technique Ant Colony
Optimization (ACO) in order to create a novel routing algorithm and apply it on the RWA
problem. This decision affords the algorithm to consider physical layer effects in RWA
process.
CI algorithms are generally simple, but they have specific requirements such as a
number of parameters to be settled. In order to improve the performance of the ACO
algorithm, we use another CI technique called Particle Swarm Optimization (PSO). The
latter technique searches for the best values to be used by the ACO parameters.
After a careful comprehensive study of the PSO technique, a novel approach called
Clan PSO was proposed. This new approach makes it possible to reach good solutions
quicker than the standard PSO and to avoid local optima. The idea of the new approach is
to combine the global structure of gbest (based on global communication) and the good
quality solutions of lbest (based on different neighborhood communication).
After the definition of the parameters, several experiments were carried out making
use of the ACO routing algorithm. These experiments produced satisfactory results that
demonstrated how useful our contribution is and its capacity to be applied in optical net-
works.
Keywords: Computational Intelligence, ACO, PSO, Clan-PSO, Optical Communication,
RWA.
Capítulo 1
Introdução
A necessidade de melhorar os serviços de telecomunicações tem crescido rapidamente.
Isso se dá pela importância que as redes de telecomunicações, juntamente com a Internet,
tomaram dentro da sociedade atual. Há um crescimento exponencial na quantidade de
usuários de serviços de Internet, o que eleva a demanda de tráfego. Esse aumento da uti-
lização naturalmente gera uma cobrança por qualidade do serviço oferecido. Em média, o
tráfego na internet dobra a cada 6 meses, exigindo assim estudos de melhores alternativas
para disponibilizar maiores taxas de transmissão por usuário. O que antes era um grande
conjunto de limitados usuários de conexões dialup com capacidade de 28 − 56 kb/s,em
praticamente uma década passou a ser uma cobertura quase que totalmente orientada a
usuários de modens ADSL na ordem de 1 Mb/s (RAMASWAMI; SIVARAJAN, 2002).
Sistemas online se tornamcada vez mais complexos, exigindo um suporte ainda maior
das redes de telecomunicações. O que inicialmente eram sistemas de utilização interna
para bancos, lojas, supermercados e hospitais, passaram a ter extensão mundial. Pessoas
de todo o mundo tem acesso a sistemas de bancos que realizam uma gama de transações
em tempo real. Universidades estão interligadas por sistemas acadêmicos de biblioteca
virtual acessados por alunos do mundo todo, além de ministrar cursos online em tempo
real para estudantes de todo o mundo. Toda grande empresa necessita de alta velocidade
de conexão para conduzir seus negócios entre diferentes cidades, estados e até países,
o que novamente demanda uma rede de alta capacidade. Portanto, características como
capacidade de carga, velocidade de transmissão e extensão física da rede, tornaram-se
necessidades básicas para sistemas que anteriormente tinham escopo local. Foi dentro da
perspectiva de suprir estas demandas que as redes ópticas transparentes foram concebidas.
2
1.1 Utilização de redes ópticas
Como afirmado anteriormente, nos dias de hoje as grandes empresas tendem a buscar
redes com alta velocidade e conexões físicas que interliguem não só um conjunto de fil-
iais, mas todas as empresas existentes, para que dessa forma o gerenciamento seja feito
globalmente e em tempo real. À luz dessas premissas, as redes de comunicação ópticas
de alta velocidade são consideradas a tecnologia mais apta a atender a demanda de banda
requerida (RAMASWAMI; SIVARAJAN, 2002). Esse tipo de rede provê uma infraestru-
tura capaz de oferecer serviços com: (i) alta velocidade de transmissão (com canais de
até 40 Gb/s, por exemplo), (ii) percorrer grandes distâncias (conectar diferentes cidades
e até países), e (iii) manter a qualidade de serviço alta.
A transmissão em sistemas ópticos é geralmente realizada através de fibra óptica, e
tem evoluído bastante através dos anos devido ao aumento da produção e do domínio de
aplicação das fibras ópticas. A fibra óptica é fabricada basicamente utilizando silica, um
material de grande abundância no planeta, o que baixa o custo associado à fabricação de
fibra (AMAZONAS, 2002). Nas últimas décadas, a capacidade de transmissão das fibras
tem aumentado sensivelmente, assim como a extensão alcançada pelos caminhos ópticos,
esses fatos reforçam a importância do o uso de fibra óptica (RAMASWAMI; SIVARA-
JAN, 2002)(AMAZONAS, 2002). Outras vantagens do uso de fibra óptica são a imu-
nidade a diferentes tipos de interferência, assim como a maior segurança da informação
que trafega na fibra (RAMASWAMI; SIVARAJAN, 2002)(AMAZONAS, 2002).
O crescimento do uso de sistemas ópticos têm aumentado gradativamente por conta
desses diversos fatores a favor das fibras ópticas, gerando uma demanda grande por estu-
dos e projetos em redes ópticas dentro das grandes empresas de telecomunicações. Essas
empresas têm migrado todo o seu sistema anterior para sistemas ópticos, indicando que
esse tipo de aplicação será utilizada por vários anos à frente.
É refletindo dentro das informações colocadas acima que empresas e pesquisadores de
toda a comunidade científica buscamutilizar a eficácia dos sistemas ópticos em aplicações
reais.
3
1.2 Oproblemaderoteamentoe alocaçãode comprimento
de onda
Um processo inerente às redes ópticas WDM (Wavelength Division Multiplexing)éo
roteamento e alocação de comprimento de ondas (RWA, Routing and Wavelength Assign-
ment), que compõe o núcleo de todo o controle de um sistema de redes ópticas (RA-
MASWAMI; SIVARAJAN, 2002)(ZANG; JUE; MUKHERJEEE, 2000). O RWA tem a
tarefa de definir qual será o caminho óptico (lightpath) e o comprimento de onda usado
para uma dada chamada. Dado um conjunto de conexões (enlaces) entre nós, um caminho
óptico é definido por uma rota que une dois nós origem e destino, e um comprimento de
onda que possa ser alocado para utilização dessa conexão. A escolha do lightpath pode
ser realizada considerando diversos fatores que constituem o estado atual da rede: con-
gestionamento, quantidade de comprimentos de onda livres, ruídos nos enlaces ópticos,
entre outros.
1.3 Motivação e objetivos
A aplicação de algoritmos de roteamento mais comuns existentes na literatura, em geral,
não levam em consideração vários efeitos da camada física durante o processo de rotea-
mento e alocação de comprimento de onda. O objetivo principal dessa dissertação é criar
um novo algoritmo de roteamento e aplicá-lo ao problema de RWA utilizando a técnica de
computação inteligente baseada em colônias de formigas. Pois ao se utilizar propriedades
associadas à equação de indução das formigas pode-se fazer uma adaptação que permita a
inserção de diversos fatores que influenciam no roteamento, e assim, aplicar a nova abor-
dagem de ACO às redes ópticas inserindo as penalidades oriundas dos efeitos da camada
física.
Após a elaboração da nova equação de indução das formigas, objetiva-se também
realizar a otimização dos parâmetros que irão compor a equação para se obter o melhor
desempenho na aplicação às redes ópticas. Essa otimização será realizada através de
um algoritmo inteligente de otimização baseado em Inteligência de Enxames (SI, Swarm
Intelligence).
4
1.4 Aplicação de inteligência de enxames
O estudo sobre o comportamento de grupos pertencentes à natureza tem inspirado o
homem a desenvolver técnicas de exploração e busca baseadas na coletividade simples
oriunda desses mesmos grupos. Sistemas baseados em modelos desse tipo já são uti-
lizados com sucesso para solucionar problemas reais de alta complexidade (ENGEL-
BRECHT, 2005).
Dentro de um mesmo grupo de indivíduos (enxame), há uma interação com o intuito
de solucionar o problema de conhecimento global dentro do enxame. Para toda iteração,
cada indivíduo tenta se aproximar mais de uma solução melhor do que a que ele já encon-
trou e propaga essa sua informação para os outros componentes do grupo, passando sua
experiência para os outros e, assim, solucionando o problema com mais eficiência do que
o faria se estivesse sozinho.
Em sua definição mais formal, um enxame pode ser considerado um grupo de agentes
móveis que realizam uma espécie de comunicação e cooperação entre eles dentro de um
mesmo ambiente. Inteligência de Enxames (SI, Swarm Intelligence) aponta para um am-
biente formado com o objetivode solucionar problemas através da interação entre agentes
do tipo apresentado anteriormente. Partindo do mesmo princípio, diz-se que Inteligência
Computacional de Enxames (CSI, Computational Swarm Intelligence) utiliza inteligência
de enxames para elaborar algoritmos e modelos computacionais inspirados no ambiente
e seus agentes.
1.4.1 Algoritmos de formigas
Diferentes modelos que utilizam a idéia descrita na seção acima foram criados tomando
como base o comportamento social de animais e insetospertencentes à natureza. Sistemas
bio-inspirados já se tornaram algo comum nesse meio, originando algoritmos baseados
em formigas, abelhas, pássaros, peixes, entre outros. A estrutura desses algoritmos é sim-
ples, o que os torna absolutamente funcionais é a maneira como é realizada a comunicação
dentro do grupo, é o comportamento social dos indivíduos que rege o funcionamento do
enxame na busca pela melhor solução. Assim, fica evidente que a parte mais importante
desse processo é a interação entre os agentes, ou seja, a cooperação que existe entre os
mesmos.
5
Modelar ambientes simplescontendo indivíduosque cooperam entre si tornou-se uma
fórmula altamente capaz de obter soluções para problemas de alta complexidade, em geral
problemas de otimização. Um exemplopara esse tipo de modelo é o utilizado na Otimiza-
ção por Enxames de Partículas (PSO, Particle Swarm Optimization), onde cada indivíduo
se move direcionado pela experiência do seu melhor vizinho e pela sua própria experiên-
cia. Dessa forma, todos os indivíduos podem convergir para um ponto comum.
Baseado em formigas, o modelo de otimização por colônias de formigas (ACO, Ant
Colony Optimization) utiliza um simples processo de deposição de feromônio por parte
das formigas, que alteram o ambientede forma que as outras formigas do grupo percebam
a concentração de feromônio e sejam induzidas a seguir pelos caminhos que contiverem
a maior concentração. Essa indução é feita probabilisticamente, o que cria diversidade
na escolha feita por cada formiga. A partir disso, surge um ambiente propício para o
problema do melhor caminho dentro de um conjunto de alternativas que pode ser repre-
sentada por uma rede de comunicação mapeada em um grafo não-direcionado.
1.5 Organização desta monografia
Esta dissertação está organizada como se segue. O capítulo 2 contém a descrição da meta-
heurística baseada em colônias de formigas, suas propriedades e processos relacionados
que levam a colônia a achar o menor caminho dentro de uma rede de comunicações. No
capítulo 3 é apresentada a técnica de PSO, que será utilizada na otimização dos parâ-
metros da equação de indução do ACO, assim como uma nova variação chamada PSO
baseado em clãs. O capítulo 4 descreve uma descrição detalhada do problema de RWA
abordado nessa dissertação. O capítulo 5 apresenta toda a formulação e desenvolvimento
do novo algoritmo de ACO proposto juntamente com os resultados de sua aplicação às re-
des ópticas. No capítulo 6 são apresentadas as conclusões sobre trabalho realizado nessa
dissertação, e também os planos de possíveis trabalhos futuros.
6
Capítulo 2
Otimização por Colônias de Formigas
Utilizando os mecanismos de organização e comunicação das colônias, Marco Dorigo
propôs em 1996 um novo paradigma de otimização conhecido como “Otimização por
Colônias de Formigas” (ACO, Ant Colony Optimization) (DORIGO; MANIEZZO; COL-
ORNI, Feb 1996) (DORIGO; CARO; GAMBARDELLA,1999) (DORIGO; BONABEAU;
THERAULAZ, 2000) (KENNEDY; EBERHART, 2001). Esta técnica é inspiradano com-
portamento de colônias de formigas e esse capítulo irá descrever como colônias de formi-
gas reais inspiraram um modelo de colônias artificiais.
2.1 O Ambiente de uma Colônia de Formigas
A natural capacidade de comunicação indireta de uma simples formiga leva a colônia a
se tornar um sistema organizado capaz de realizar tarefas específicas (BONABEAU; DO-
RIGO; THERAULAZ, 1999) (KENNEDY; EBERHART, 2001). Procurar por comida é a
tarefaprincipal realizada por uma colônia, pela necessidade natural de sobrevivência. Para
chegar a fontes de comida, uma colônia deve possuir a capacidade de auto-organização.
As formigas que compõem a colônia iniciam uma procura aleatória nas áreas ao redor
do formigueiro (ninho). Dessa forma, as formigas selecionam caminhos sem considerar
informações prévias. Ao encontrar a fonte de comida, as formigas analisam a quantidade
e a qualidade da comida, e logo em seguida retornam para o formigueiro carregando parte
da comida encontrada. Retornando pelo mesmo caminho utilizado na viagem de ida,
cada formiga deixa no caminho uma substância chamada de feromônio (DENEUBOURG;
ARON; GOSS, 1990), que tem como objetivo modificar o ambiente. Essa substância
7
serve como guia, aumentando a probabilidade de outras formigas tomarem como escolha
esse mesmo caminho.
O uso de feromônio descreve uma forma indireta de comunicação, chamada de stig-
mergia (GRASSé, 1959), em colônias verdadeiras estudadas por biólogos. Em outras
palavras, muitos fenômenos observados em colônias de insetos (como formigas), podem
ser explicados a partir de modelos simples que consideram apenas comunicação através
de stigmergia. Fazendo uso dessa característica, a colônia consegue uma alta capacidade
de organização.
Como dito anteriormente, as formigas, ao contrário dos seres humanos, não se co-
municam através de métodos visuais ou acústicos, e sim via rastro de feromônio. Este
tipo de rastro é usado por muitas espécies de formigas, como a Lasius niger ou a formiga
Argentina Iridomyrmex humilis (GOSS et al., 1989), para marcar caminhos no chão.
Percebendo o rastro de feromônio, as formigas de uma colônia podem seguir os ca-
minhos encontrados por outras formigas, enquanto procuram por comida. Esse tipo de
comunicação é a principal parte da técnica de ACO.
Utilizando regras estocásticas baseadas em controle através de stigmergia, formigas
são capazes de achar o caminho mais curto entre dois pontos (como entre o formigueiro e
uma fonte de comida) que pertençam ao ambiente da colônia. Inspirada nessa informação
e utilizando um grafo para representar o ambiente da colônia, é possível modelar formi-
gas capazes de, movendo-se dentro do grafo, achar o caminho mais curto entre dois nós
específicos.
2.2 O Experimento das Duas Pontes e o Modelo Desen-
volvido por Deneubourg
Percorrendo caminhos entre o formigueiro e a comida, formigas são induzidas pelo rastro
de feromônio depositado por outras e tendem a escolher, probabilisticamente, caminhos
contendo grandes concentrações de feromônio.
Deneubourg (DENEUBOURG; ARON; GOSS, 1990) (GOSS et al., 1989) realizou
um experimento com duas pontes conectando um formigueiro a uma fonte de comida,
como mostrado na Figura 2.1. No experimento, variou-se a taxa r = l
l
/l
s
, onde l
l
e l
s
eram os tamanhos do desvio mais longo e do desvio mais curto, respectivamente.
8
Ninho Comida
60º
15 cm
l
s
l
l
(a) Primeiro teste
Ninho Comida
1
2
l
s
l
l
(b) Segundo teste
Figura 2.1: Experimento das duas pontes realizado por Deneubourg (DENEUBOURG;
ARON; GOSS, 1990) usando (a) r = l
l
/l
s
= 1 e (b) r = l
l
/l
s
= 2.
No primeiro teste, Figura 2.1(a), o experimento foi realizado com desvios do mesmo
tamanho (r = 1). No início do experimento as formigas estão livres para escolher um
desvio para chegar à comida. Embora na fase inicial ocorram escolhas aleatórias, even-
tualmente todas as formigas fazem uso do mesmo desvio. Neste caso foi constatado que
as formigas não têm preferência na escolha, portanto elas selecionam um dos desvios
com a mesma probabilidade. Ao realizar um grande número de testes da mesma forma,
percebeu-se que as formigas usavam cada um dos caminhos praticamente a mesma quan-
tidade de vezes.
Uma razão diferente entre o tamanho dos dois desvios foi utilizada no segundo ex-
perimento mostrado na Figura 2.1(b). Neste caso foi adotado r = 2, tornando o desvio
mais longo duas vezes maior do que o mais curto (GOSS et al., 1989). Ao iniciar o
experimento, as formigas selecionam os desvios aleatoriamente como no primeiro expe-
rimento. Isso é claramente esperado, pois, para as formigas, os dois desvios têm a mesma
aparência (ambos sem concentração de feromônio). Então, pode-se esperar que inicial-
mente, metade das formigas, em média, escolham l
l
e o restante escolha l
s
. A grande
diferença entre os experimentos é que as formigas que escolheram l
s
chegam à comida
antes das formigas que escolheram l
l
. Por conta desse fato, as formigas que chegam
mais rapidamente à comida, retornarão ao formigueiro mais rapidamente do que as outras
que escolheram l
l
. Portanto, a concentração de feromônio em l
s
aumenta, polarizando
a decisão das formigas que estão saindo em busca de comida a favor desse desvio. A
9
princípio, o aumento da concentração de feromônio em l
s
poderia guiar todas as formigas
a escolherem o caminho mais curto (l
s
), porém o experimento demonstra que nem todas as
formigas usam l
s
. Uma pequena porcentagem das formigas acaba usando o caminho mais
longo (l
l
). Isso pode ser interpretado como uma capacidade de exploração de caminhos
inerente à colônia.
Um terceiro experimento foi realizado e seu arranjo experimental é mostrado na Fi-
gura 2.2. Esse experimento fez uso dos mesmos desvios l
l
e l
s
utilizados no segundo
experimento. Inicialmente, o movimento das formigas foi observado durante um inter-
valo de 30 minutos tendo como possível caminho apenas l
l
. Ao final desse intervalo, o
caminho mais curto foi adicionado ao ambiente e uma nova observação foi iniciada, dessa
vez tendo os dois caminhos (l
l
e l
s
) como possíveis escolhas para as formigas. Notavel-
mente, l
s
só foi escolhido esporadicamente, e a colônia ficou presa em l
l
. Isso é explicado
pela alta concentração de feromônio adquirida pelo caminho mais longo durante os 30
minutos iniciais do experimento, pelo reforço de feromônio adquirido no mesmo após
os 30 minutos, e também pela baixa evaporação de feromônio nos dois caminhos. Uma
maior taxa de evaporação de feromônio pode evitar convergências pré maturas para um
caminho sub-ótimo, assim tendo a possibilidade de descobrir um caminho ainda mais
curto.
Ninho Comida
Ninho Comida
30 min
Figura 2.2: Esquema do experimento realizado por Deneubourg (DENEUBOURG;
ARON; GOSS, 1990) para demonstrar o modo como as formigas são induzidas pela con-
centração de feromônio.
Para descrever o experimento das duas pontes mostrado anteriormente, Deneubourg
propôs um modelo estocástico simples (DENEUBOURG; ARON; GOSS, 1990) (GOSS
et al., 1989). Nesse modelo foi estipulada uma taxa ψ de formigas por segundo, onde cada
10
formiga usa uma velocidade constante v (em cm/s) para atravessar a ponte, e deposita
uma unidade de feromônio no caminho utilizado. Para atravessar l
s
e l
l
, uma formiga irá
precisar de t
s
= l
s
/v e t
l
= r · t
s
segundos, respectivamente.
A probabilidade p
ia
(t) de uma formiga localizada no ponto i ∈{1, 2} na Figura 2.1(b)
escolher o caminho a ∈{s, l}, no instante t é mostrada como função da concentração de
feromônio ϕ
ia
(t) no caminho. Por exemplo, a probabilidade p
is
(t) de escolher o menor
caminho é dada por:
p
is
(t) =
(t
s
+ ϕ
is
(t))
α
(t
s
+ ϕ
is
(t))
α
+ (t
s
+ ϕ
il
(t))
α
, (2.1)
com p
is
(t) + p
il
(t) = 1, onde ϕ
is
(t)eϕ
il
(t) são as concentrações de feromônio no tempo t
do caminho mais curto e do caminho mais longo, respectivamente.
Neste modelo a concentração de feromônio em um caminho é proporcional ao número
de formigas que já fizeram uso deste caminho. As formigas presentes nesse modelo de-
positam feromônio tanto na viagem de ida quanto na de volta, e não é considerada a
evaporação de feromônio (BECKERS; DENEUBOURG; GOSS, 1993).
2.3 Modelo artificial para formigas
Baseando-se no experimento das duas pontes realizado por Deneubourg (Section 2.2),
percebe-se que as colônias de formigas podem encontrar o caminho mais curto entre dois
pontos em um dado ambiente. Fazendo uso dessa mesma informação, é possível mapear
o ambiente de uma colônia de formigas em um grafo (isto é, formado por várias “pontes”)
e projetar as formigas reais como agentes artificiais realizando a tarefa de procurar pelo
caminho mais curto entre dois nós (por exemplo, formigueiro e comida).
2.3.1 Ambiente
O grafo mostrado na Figura 2.3(a) é baseado no experimento da Figura 2.1(b). Considere
a seguinte situação: o grafo possui dois nós (1 e 2) que representam o formigueiro e a
fonte de comida, respectivamente. O arco mais longo (l
l
)ér vezes maior que o mais curto
(l
s
), e o tempo nesse caso será considerado discreto (t = 1, 2,...). A cada unidade de
tempo, formigas usam uma velocidade constante mover-se em direção a um nó vizinho.
Os arcos utilizados (visitados) recebem uma unidade de feromônio para cada uma das
formigas que passam por eles.
11
1
2
(a) Primeiro modelo
de grafo
1
2
3
(b) Segundo modelo de grafo
Figura 2.3: Modelos de grafos baseados no experimento das duas pontes.
Baseando-se em probabilidades, as formigas escolhem qual nó será utilizado através
de
p
is
(t) =
[ϕ
is
(t)]
α
[ϕ
is
(t)]
α
+ [ϕ
il
(t)]
α
(2.2)
para o caminho mais curto (l
s
), e
p
il
(t) =
[ϕ
il
(t)]
α
[ϕ
is
(t)]
α
+ [ϕ
il
(t)]
α
(2.3)
para o mais longo (l
l
).
A atualização do rastro de feromônio para os dois caminhos (l
l
e l
s
) está definida de
acordo com as equações 2.4 e 2.5, respectivamente:
ϕ
is
(t) = ϕ
is
(t − 1) + p
is
(t − 1) · m
i
(t − 1) + p
js
(t − 1) · m
j
(t − 1) , (2.4)
ϕ
il
(t) = ϕ
il
(t − 1) + p
il
(t − 1) · m
i
(t − 1) + p
jl
(t − r) · m
j
(t − r) . (2.5)
onde i é o nó atual e j o próximo nó, e m
i
(t) é o número de formigas no nó i no instante
de tempo t. A equação que define m
i
(t)é
m
i
(t) = p
js
(t − 1) · m
j
(t − 1) + p
jl
(t − r) · m
j
(t − r) . (2.6)
Nota-se que esse modelo utiliza o tempo discreto, ou seja, usa a diferença direta entre
o instante de tempo atual e o passado (t e t − 1).
Figura 2.3(b) apresenta outrarepresentação do experimentomostradona Figura 2.1(b).
Todos os arcos têm o mesmo tamanho, então o caminho mais longo usa dois arcos {1, 3},
12
e {3, 2}, e o mais curto usa somente um {1, 2}. Essa estrutura permite uma fácil imple-
mentação para realização de simulações com grafos utilizando tempo discreto e vários
nós.
Estruturas mais complexas como o grafo da Figura 2.4 trazem vários problemas ao
algoritmo de ACO. O primeiro problema surge nos loops que ocorrem dentro do grafo.
Isso pode ser visto como conseqüência da deposição do rastro de feromônio na viagem de
ida e sua atualização (reforço do rastro). Os caminhos tendem a se tornar mais atraentes,
prendendo uma grande quantidade de formigas a um mesmo caminho. A forma mais
simples de solucionar esse problema é remover o mecanismo de deposição de feromônio
na viagem de ida.
Figura 2.4: Uma formiga artificial construindo uma solução.
Aqui, percebe-se oprincipal mecanismo dos algoritmos inspirados em formigas: fazer
uso das características das formigas reais, permitindo que as formigas pertencentes ao
algoritmo possam memorizar caminhos parciais que foram percorridos e o custo associ-
ado a eles. Seguido dessa capacidade de armazenamento, alguns comportamentos foram
adicionados: capacidade de construir soluções (caminhos mais curtos); análise de qual-
idade da solução; e deposição proporcional de feromônio (a qualidade da solução deter-
mina a quantidade de feromônio a ser depositada). A evaporação de feromônio também
foi adicionada ao ambiente com o intuito de evitar a convergência para caminhos sub-
ótimos (DORIGO; STüTZLE, 2004).
2.3.2 Mecanismos
A forma padrão do algoritmo de ACO envolve diversos mecanismos dentro do ambiente
criado pela colônia artificial (DORIGO; STüTZLE, 2004). Esta seção tem como objetivo
13
apresentar e analisar esses mecanismos. A partir das definições de cada mecanismo, torna-
se mais fácil a compreensão do ambiente e do comportamento de cada formiga dentro
dele.
2.3.2.1 Movimento das formigas artificiais
No algoritmo de ACO existem duas formas de movimento realizadas pelas formigas ar-
tificiais: o movimento à frente, onde as formigas escolhem através probabilisticamente
qual caminho utilizar; e o movimento para trás, que acontece a partir do momento em que
a formiga chega na fonte de comida e deve retornar para o ninho.
Para cada arco (i, j) de um grafo G = (N, A) existe uma quantidade de feromônio,
a partir de agora representada por τ
ij
, chamada de rastro de feromônio artificial. Con-
siderando uma formiga k localizada no nó i, a mesma terá uma probabilidade p
k
ij
de esco-
lher o nó j como próximo nó, tomando como base a concentração de feromônio τ
ij
(SIM;
SUN, 2003). Essa probabilidade é definida por:
p
k
ij
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
[τ
ij
]
α
l∈N
k
i
[τ
il
]
α
, se j ∈ N
k
i
;
0, se j N
k
i
;
(2.7)
onde N
k
i
é o conjunto de nós vizinhos da formiga k no momento em que está posicionada
no nó i. Esse conjunto de nós vizinhos é formado por todos os nós conectados a i que
ainda não foram visitados pela formiga k. Isto evita que a formiga fique dando voltas
dentro do grafo.
2.3.2.2 Deposição de feromônio
A escolha realizada por cada formiga durante o movimento à frente (viagem de ida) é
induzida pela quantidade de feromônio depositada nos caminhos a serem escolhidos.
Quanto maior a concentração de feromônio no caminho, maior a probabilidade do mesmo
ser escolhido. Esse feromônio é depositado durante o movimento para trás (caminho de
volta). Cada formiga memoriza o caminho traçado até a fonte de comida, então retorna
ao ninho depositando uma quantidade feromônio Δτ no caminho utilizado. A deposição
feita por uma formiga k é:
τ
ij
← τ
ij
+Δτ
k
, (2.8)
14
onde a quantidade de feromônio Δτ
k
depositado durante a viagem de volta.
Esta quantidade pode ser proporcional à qualidade da solução achada. Esse tipo de
comportamentoé inspirado nas formigasda espécie Lasius niger (BECKERS; DENEUBOURG;
GOSS, 1993), que ao retornarem de fontes de comida mais atraentes tendem a marcar o
caminho com mais feromônio do que as que vêm de fontes mais escassas.
Cada formiga artificial registra a seqüência de arcos utilizados para chegar à fonte de
comida, assim como os custos associados a cada um. Portanto, para valorizar a qualidade
do caminho achado, a deposição de feromônio é inversamente proporcional ao custo do
caminho (conjunto de arcos).
2.3.2.3 Evaporação
A partir do momento em que todas as formigas estão em movimento, uma grande quanti-
dade de feromônio é depositada e percebida por cada uma delas. Portanto, a cada iteração
do algoritmo, é necessário diminuir a intensidade de feromônio nos arcos com o intuito
de aumentar a diversidade de escolha das formigas. Essa diversidade permite que a colô-
nia artificial não tenda a convergir para caminhos sub-ótimos, e também permite que a
colônia se adéqüe dinamicamente à possíveis alterações do ambiente.
A diminuição da concentração total de feromônio na rede se dá através da aplicação
do mecanismo de evaporação definido por:
τ
ij
← (1 − ρ) ·τ
ij
, ∀(i, j) ∈ A (2.9)
onde ρ éataxa de evaporação, sendo ρ ∈ (0, 1].
A Equação 2.9 define a evaporação como sendo a retirada de uma quantidade propor-
cional à concentração de feromônio em cada arco do grafo (HALLOY et al., 2006). Esse
processo pode não ter grande influência em colônias reais (DENEUBOURG; ARON;
GOSS, 1990), mas aplicado à colônias artificiais é de grande utilidade.
2.3.3 Definição do algoritmo de ACO para busca do menor caminho
em um grafo
O algoritmo de ACO pode ser utilizado para achar caminhos curtos em redes, fazendo uso
dos mecanismos definidos na sub-seção 2.3.2. Esses mecanismos utilizam parâmetros
15
importantes como: quantidade de formigas por grupo, número de passos do algoritmo,
entre outros. Nesta seção, apresentamos os detalhes dos mecanismos do algoritmo.
O algoritmo de ACO faz uso desses mecanismos para definir os seus próprios pro-
cessos. Nesta seção serão utilizados algoritmos de fácil entendimento para descrição de
tais processos. Esses processos consideram dados já inicializados, como quantidade de
formigas por grupo, número de passos do algoritmo, entre outros.
2.3.3.1 Construção da solução
O pseudo-código mostrado no Algoritmo 1 define os passos realizados pela colônia para
chegar a uma solução, ou seja, define rota de menor custo entre um par origem-destino.
Para esse algoritmo, o custo de cada arco representa a distância de um nó para outro, no
caso prático, o tamanho de um enlace.
A colônia é composta por diversos grupos contendo a mesma quantidade de formigas
(
numeroDeFormigasPorGrupo). Os grupos de formigas percorrerão o grafo para achar
o caminho utilizando uma quantidade de passos (
numeroDePassos) pré-definida. As
linhas 5, 6 e 7 mostram a composição de cada grupo da colônia, onde serão lançadas
formigas até que o grupo atinja o tamanho especificado. Cada formiga sempre é lançada
no nó
noOrigem com o intuito de chegar ao nó noDestino. Cada formiga se move do
nó atual para o próximo através do método anda() (ver linha 9) que encapsula a memo-
rização dos nós já visitados, assim como a regra de decisão. No momento em que uma
formiga k chega a seu destino (
noDestino), a mesma é lançada de volta ao seu ponto de
partida (
noOrigem). Nesse processo de retorno, a formiga deposita a quantidade de fero-
mônio calculada em relação à qualidade do caminho encontrado. O caminho encontrado
por k é armazenado em
caminhoDaFormiga, e caso seja melhor que o já encontrado por
toda a colônia, esse caminho se tornará a solução corrente
caminhoSolucao até que outra
formiga encontre caminho melhor. A formiga k será “morta” (isto é, removida) para que
outra nova formiga tome seu lugar no grupo e seja lançada.
A linha 20 do Algoritmo 1 mostra a chamada para o processo de evaporação que
acontece a cada passo realizado por toda a colônia.
16
2.3.3.2 Regra de decisão para escolha do próximo nó
No momento em que uma formiga k chega a um nó i ela deve tomar uma decisão que
a levará para o próximo nó j. Como padrão, essa escolha é feita tomando como base a
concentração de feromônio nos arcos formados a partir de i.
Para o problema de menor caminho entre um par origem-destino, pode-se levar em
conta a distância do caminho achado entre esses dois nós. Assim, a regra de decisão
usada pela formiga será:
p
k
ij
=
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
r ·
[τ
ij
]
α
[d
ij
]
β
, se j ∈ N
k
i
;
0, se j N
k
i
;
(2.10)
onde d
ij
é o valor da distância entre o nó onde a formiga k está localizada e o possível
próximo nó j,er é um valor aleatório entre 0 e 1. Dessa forma, o custo associado a
cada link também induzirá a formiga a escolher seu próximo nó. O fator r tem o papel de
inserir diversidade na decisão, mantendo a capacidade de exploração das formigas.
Essa decisão é tomada através de um processo chamado Regra De Decisão apresen-
tado no Algoritmo 2.
Algoritmo 2: Método como a formiga decide o próximo nó a ser visitado.
Saída: Próximo nó a ser visitado ou um erro de decisão
// formiga sem possíveis próximos nós
se
nosPossiveis.vazio() = Verdadeiro então1
retorna ERRO_DE_DECISAO2
fim3
proximoNo ← nosPossiveis [0]4
arcoEscolhido ← grafo [noAtual ][nosPossiveis [0]]5
para i = 1 até nosPossiveis.tamanho() faça6
arcoAtual ← grafo [noAtual ][nosPossiveis [i]]7
se calculaInducao(arcoAtual) > calculaInducao(arcoEscolhido) então8
arcoEscolhido ← arcoAtual9
proximoNo ← nosPossiveis [i]10
fim11
fim12
retorna proximoNo13
17
Considerando uma formiga k localizada no nó i, a mesma fará a análise de quantos
nós j são possíveis de escolher a partir de i. Caso essa análise resulte em uma quantidade
vazia de nós (linhas 1,2e3)aformiga se encontra num “dead end”, e retorna um erro de
decisão. Se o número de nós não é vazio, a formiga calcula a capacidade de indução de
cada um deles, retornando o nó de maior valor de indução.
2.3.3.3 Deposição e evaporação de feromônio
O processo de deposição de feromônio acontece quando a formiga realiza a viagem de
volta. Durante esse retorno, cada formiga deposita uma quantidade de feromônio propor-
cional ao custo do caminho achado. O Algoritmo 3 descreve o processo de deposição.
Algoritmo 3: Método usado por cada formiga para depositar feromônio no caminho
durante a viagem de volta.
Entrada: Caminho onde será depositado o feromônio
para i = 0 até
caminho.tamanho() faça1
arco ← caminho [i]2
arco.feromonio ← arco.feromonio + (unidadesDeFeromonio /3
caminho.custo )
fim
4
Cada arco do caminho recebe a mesma quantidade de feromônio, sendo essa quanti-
dade adicionada à concentração já existente no arco.
Na linha 20 do Algoritmo 1 acontece a chamada do processo de evaporação. Esse
processo acontece após o movimento de todas as formigas da colônia e retira uma porcen-
tagem da concentração de feromônio de cada arco do grafo como mostra o Algoritmo 4.
Algoritmo 4: Método como o feromônio é evaporado de cada arco do grafo.
para i = 0 até grafo.numeroDeNos faça1
para j = 0 até grafo.numeroDeNos faça2
se grafo [i][j].existe() então3
arco ← grafo [i][j]4
arco.feromonio ← arco.feromonio ∗ (1− taxaDeEvaporacao )5
fim6
fim7
fim8
18
Na linha 5 acontece a retirada de uma parte de feromônio de cada arco. Essa porcen-
tagem retirada é referente à
taxaDeEvaporacao.
Fica evidentea simplicidade desse principais processos realizados dentro do algoritmo
de ACO, como proposto por Dorigo (DORIGO; MANIEZZO; COLORNI, Feb 1996).
Nota-se que a tarefa de uma formiga sozinha é bastante simples, porém se comunicando
dentro de uma colônia, são capazes de resolver problemas de difícil solução.
19
Algoritmo 1: Colônia se movimentando dentro do grafo em busca do caminho de
menor custo.
Entrada: Um par (origem, destino)
Saída: Caminho de menor custo
enquanto
passo <= numeroDePassos faça1
// varre cada grupo da colônia
para n = 0 até
colonia.tamanho() faça2
// varre cada formiga do grupo
para k = 0 até
grupo.tamanho() faça3
grupoAtual ← colonia [n]4
// preenche grupo de formigas
se
grupoAtual.tamanho() < numeroDeFormigasPorGrupo então5
lancaFormigaPraFrente(n, noOrigem, noDestino)6
fim7
formiga ← grupoAtual [k]8
// movimento da formiga
formiga.anda()9
// formiga chega ao destino
se
formiga.noAtual = noDestino então10
lancaFormigaPraTras(n, k)11
caminhoDaFormiga ← formiga.caminho12
// melhor caminho achado
se
caminhoDaFormiga.custo < caminhoSolucao.custo então13
caminhoSolucao ← caminhoDaFormiga14
fim15
mataFormiga(formiga)16
fim17
fim18
fim19
evaporaFeromonio()20
passo ← passo +121
fim22
retorna caminhoSolucao23
20
Capítulo 3
Algoritmo de busca utilizado para
seleção paramétrica do ACO
O algoritmo ACO faz uso de diversosparâmetros que influenciamdiretamentena sua con-
vergência. Definir qual a melhor combinação de parâmetros pode ser uma tarefa de alta
complexidade. Dessa forma, fazer uso de uma técnica inteligente de busca para encontrar
essas combinações é uma decisão bastante adequada. Nesse capítulo é apresentada uma
nova variação (isto é, Otimização por enxames de partículas com clãs) para uma técnica
de busca já conhecida, assim como os resultados obtidos a partir dessa variação.
3.1 Otimização por enxames de partículas
Nesta seção, a técnica de computação inteligente utilizada, denominada Otimização por
Enxames de Partículas (Particle Swarm Optimization, PSO), para seleção é apresentada.
O algoritmo de PSO é inspirado no comportamento social de grupos, sendo bastante apli-
cado a problemas de otimização e busca.
3.1.1 Origem do Modelo de Partículas
Partículas são, em sua forma mais básica, entidades capazes de realizar simples movi-
mentos. A idéia de utilizar partículas trabalhando de forma simples, porém em conjunto,
foi inicialmente utilizada por Reeves em 1983 (REEVES, 1983) para renderizar imagens
em animações de computador, tentando simular artificialmente um ambiente natural. Em
conjunto, as partículas eram capazes de representar formas e comportamentos interes-
21
santes, como nuvens e explosões. Esse trabalho foi de grande valia para a Lucasfilm,
empresa na qual Reeves fez real aplicação de seu sistema de partículas. Em simulações
gráficas, as partículas desse sistema possuíam atributos que as tornavam mais reais, tais
como cor, forma específica, textura diferente, e até tempo de vida. Além de atributos rela-
cionados com a aparência, cada partícula era capaz de se comportar de forma diferente
para cada uma das necessidades de uso. Sistemas como esse são muito utilizados para
tornar a geração de efeitos especiais cada vez mais realista.
Em 1987, Reynolds (REYNOLDS, 1987) incorporou um processo coletivo ao sistema
de Reeves. As partículas, sozinhas, realizam movimentos independentes em relação ao
conjunto. Dessa forma, Reynolds adicionou orientação às partículas e um tipo de comuni-
cação entre as partículas pertencentes a um mesmo grupo. Com o uso de regras de grupo
simples como tratamento de colisão, orientação coletiva, noção de vizinhança e proximi-
dade relativa entre as partículas, a construção de ações mais complexas, como o vôo de
um grupo de pássaros, se tornou bem mais realista.
Kennedy e Eberhart (KENNEDY; EBERHART, 1995), a partir do experimento de
Reynolds, desenvolveram uma pesquisa com o intuito de modelar ambientes sociais, ou
seja, a coletividade entre agentes pertencentes a um grupo que segue o mesmo obje-
tivo. Decorrente desta iniciativa, um algoritmo chamado de Otimização por Enxames
de Partículas (Particle Swarm Optimization, PSO) foi proposto.
PSO se tornou uma técnica bastante utilizada para solucionar problemas de otimiza-
ção envolvendo funções não-lineares em espaços de busca contínuos. Essa técnica foi
inspirada no ambiente naturalmente criado por grupos de pássaros, e o comportamento
social dos bandos. A idéia básica do PSO é simular a busca realizada por pássaros com
o intuito de encontrar algo que pertence a uma dada área específica, e assim utilizar a
inteligência coletiva proveniente da capacidade de comunicação dentro do grupo.
Nesse algoritmo, cada partícula representa uma solução em um espaço de busca de n
dimensões. Todas as partículas fazem uso de um mecanismo específico de comunicação,
tornando-as capazes de achar uma solução comum ao grupo.
3.1.2 O Algoritmo PSO
Nas implementações mais comuns do PSO, as partículas se movem em um espaço de
busca orientadas pela atração em relação à melhor solução achada por elas, individual-
22
mente, e pela atração em relação à melhor solução achada pela partícula pertencente ao
grupo ou vizinhança que obteve maior sucesso no histórico de busca (ENGELBRECHT,
2005) (BRATTON; KENNEDY, 2007). É denominada vizinhança a parte do enxame com
que uma determinada partícula está apta a comunicar-se, ou seja, o grupo que servirá de
guia para a mesma.
O enxame se desloca dentro do espaço de busca através da atualização dos valores
relativos à velocidade e à posição de suas partículas (KENNEDY, 2005).
Considerando o tempo discreto, a atualização das velocidadese posições ocorre a cada
iteração do algoritmo. É a combinação de velocidade e sucesso que guia cada partícula no
processo de otimização. Esse valor reflete tanto o conhecimento individual da partícula
quantoo conhecimento social pertencente à sua vizinhança. A forma básica de atualização
da velocidade no PSO é mostrada abaixo
−→
v
id
(t + 1) =
−→
v
id
(t) + c
1
1
−→
p
id
(t) −
−→
x
id
(t)
+ c
2
2
−−→
p
gd
(t) −
−→
x
id
(t)
, (3.1)
onde o vetor
−→
v
id
(t) representa a velocidade da partícula i na dimensão d no instante t,ou
seja, o valor da velocidade no instante atual. A posição da partícula no instante t + 1é
atualizada a partir da seguinte equação:
−→
x
id
(t + 1) =
−→
x
id
(t) +
−→
v
id
(t + 1) . (3.2)
Nota-se que o vetor de velocidade
−→
v
id
(t + 1) influencia diretamente na direção que a
partícula tomará em cada iteração, fazendo com que a mesma seja capaz de chegar a
diferentes regiões do espaço de busca.
O conhecimento adquirido pela partícula de acordo com sua própria experiência é re-
presentado na equação (3.1) por c
1
1
−→
p
id
(t) −
−→
x
id
(t)
. Denominada componente cognitivo,
esse termo representa o quanto, a partir de sua posição atual
−→
x
id
(t), a partícula está distante
de sua melhor posição já encontrada
−→
p
id
(t).
A experiência de toda uma vizinhança é representada pela componente social, que
aparece na equação (3.1) como c
2
2
−−→
p
gd
(t) −
−→
x
id
(t)
e corrige a velocidade da partícula
i em relação à melhor posição encontrada dentro de sua vizinhança (
−−→
p
gd
(t)). Para uma
vizinhança com o tamanho de todo o enxame, esse termo representa a correção da ve-
locidade da partícula em relação a todo o grupo. Nesse caso, a partícula terá noção da
melhor posição global dentro do grupo, e portanto, ajustará sua posição em relação a todo
o enxame.
23
c
1
e c
2
são constantes positivas chamadas de constantes de aceleração. Esses valores
são usados para balancear a influência do componente cognitivo e do componente social.
Esse balanceamento define o quanto o enxame tenderá a realizar busca em amplitude e
em profundidade.
Junto às constantes de aceleração estão dois valores
1
e
2
, que são números entre 0 e
1 gerados aleatoriamente por uma distribuição uniforme.
3.1.2.1 Representação Gráfica
Para melhor entender o funcionamento do PSO, representar-se-ão os efeitos da equação
de velocidade (3.1) em um plano de duas dimensões. Pontos representarão as partícu-
las, e vetores representarão os fatores que influenciam o movimento de cada uma. Na
Figura 3.1, são mostradas duas partículas (A e B) pertencentes a um certo grupo maior de
partículas que buscam otimizar uma função num espaço de busca definido por um inter-
valo de 0 a 30 para cada dimensão e com ótimo em (0, 0). Os vetores em cada partícula
representam a influência da velocidade anterior e dos componentes cognitivo e coletivo
da equação de velocidade.
O movimento das partículas A e B nos instantes t e t+1 está mostrado na Figura 3.1(a)
e na Figura 3.1(b), respectivamente.
A(t)
B(t)
melhor individual A
melhor do grupo
melhor individual B
ponto ótimo
(a)
melhor individual A
melhor do grupo
melhor individual B
ponto ótimo
A(t+1)
B(t+1)
(b)
Figura 3.1: Representação do comportamento de duas partículas: (a) no instante t e (b)
no instante t + 1.
Em cada partícula o vetor tracejado representa a velocidade que levará a partícula a
24
mudarsua posição em relação ao melhor do grupo (componentesocial), o cheio representa
o quanto a partícula tenderá à sua própria melhor posição já encontrada (componente
cognitivo), e o pontilhado representa a velocidade anterior utilizada pela partícula para se
deslocar.
No primeiro instante (t) está clara uma maior tendência, tanto de A quanto de B,em
mover-se em direção ao melhor do grupo, então, para as duas partículas, a velocidade
que será calculada
−→
v
id
(t + 1) terá como maior influência a componente social. Portanto, a
nova posição de ambas as partículas se aproximará da melhor posição achada pelo grupo,
como mostra a Figura 3.1(b). Note que, na Figura 3.1(b), a melhor posição individual de
cada partícula foi alterada, essa mudança virá a influenciar no próximo movimento, pois
o grau de influência da componente cognitiva mudará.
Durante a movimentação, as partículas sempre se direcionam influenciadas tanto pela
experiência individual quanto pela experiência do grupo, ou seja, se ajustam tendendo
a pontos pertencentes à reta que liga a melhor posição achada pela partícula à melhor
posição achada pelo grupo. Dessa forma, à medida que calculam e utilizam suas no-
vas velocidades, as partículas mudam de posição tomando a direção do ótimo da função
naturalmente.
No algoritmo de PSO podem ser definidos grupos ou vizinhanças de partículas que se
comunicam entre si, porém compõem um só enxame. A Figura 3.2 ressalta o movimento
num instante t de duas vizinhanças de partículas pertencentes a um grupo maior, com
destaque para a influência do componente social dentro de cada vizinhança.
Consideremos que a vizinhança 1, composta pelas partículas A, B e C, tem como
melhor posição do grupo a melhor posição já achada pela partícula A. As partículas B
e C seguem a melhor posição conseguida por sua vizinhança, que nesse caso é a melhor
posição individual de A. Como utilizadas anteriormente na Figura 3.1, as setas tracejadas
representam a influência social do grupo, que na Figura 3.2 é a própria vizinhança. Ao
mesmo tempo é mostrado o ajuste individual de A, representado pela seta cheia.
A segunda vizinhança (vizinhança 2) contém as partículas D, E e F. Como na vizi-
nhança 1, uma partícula, nesse caso D, segue sua melhor posição já achada para realizar
o ajuste individual. Ao mesmo tempo é feito o ajuste de E e F para com a melhor posição
conseguida na vizinhança, ou seja, a melhor posição individual de D.
Os exemplos das Figuras 3.1 e 3.2 deixam clara a possibilidade de ajuste de cada
25
ponto ótimo
melhor da vizinhança 1 melhor da vizinhança 2
A
C
D
F
B
vizinhança 1
E
vizinhança 2
Figura 3.2: Representação do comportamento de uma vizinhança de partículas no instante
t.
uma em relação à experiência própria e à coletiva da vizinhança. Tendo em mente esses
conceitos, os parâmetros utilizados no PSO e suas definições serão descritos na seção
seguinte, que é seguida pela seção que descreve o funcionamento do algoritmo.
3.1.2.2 Parâmetros e definições utilizados no PSO
O algoritmo de PSO faz uso de parâmetros que controlam o funcionamento do algoritmo.
São parâmetros do PSO: número de dimensões do problema, limites do espaço de busca,
o número de partículas, a definição da vizinhança, a quantidade de iterações, o limite de
velocidade das partículas, e os valores das acelerações usadas nos coeficientes cognitivo
e social. Nessa seção são apresentados esses parâmetros e suas influências dentro do
algoritmo.
• Espaço de busca: é definido pela combinação do número de dimensões que o
problema possui e o intervalo de busca de cada uma delas. Representa o conjunto
de todas as possíveis soluções cujos valores em cada dimensão podem variar dentro
de um intervalo pré-definido. Cada partícula i assume uma posição
−→
x
i
(t) =
(
x
i1
(t), x
i2
(t),...,x
iD
(t)
)
, ∀x
id
∈{min(x
d
), max(x
d
)}|d ∈{1, 2,...,D} ,
(3.3)
onde D é o número de dimensões do problema, e min(x
d
)emax(x
d
) são os limites
do intervalo de busca para a dimensão d.
26
• Tamanho do enxame: é a quantidade de partículas usada pelo algoritmo para re-
alizar a busca. Quanto maior o enxame maior será o espaço varrido por iteração,
porém aumentará o custo computacional. Estudos não exaustivos estipularam que
30 partículas são suficientes para achar soluções satisfatórias em funções de relativa
complexidade em espaços de busca abaixo de 30 dimensões com uma quantidade
pequena de iterações, melhorando assim o custo computacional.
• Vizinhança: define a rede social de conexões de cada partícula. É dentro dessa
rede que há a troca de informações, permitindo a atuação do componente social da
equação de velocidade. Quanto menor a vizinhança menor a troca de informações,
e, portanto, menor será a velocidade de convergência do algoritmo. Porém, fazendo
uso de pequenas vizinhanças, pode-se evitar convergência pré-matura para um mí-
nimo local, conseguindo soluções de melhor qualidade.
• Número de iterações: o número de iterações deve permitir a convergência do algo-
ritmo para soluções satisfatórias. Dessa forma, a quantidade de iterações utilizada
depende diretamente da complexidade do problema. Utilizar iterações em demasia
em problemas de fácil solução apenas eleva o custo computacional, pois a solução
será achada nas primeiras iterações.
• Limite de velocidade (V
max
): dado um espaço de busca, determina-se o limite de
velocidade como sendo o módulo de um valor entre o limite inferior e superior do
intervalo de busca. Portanto, as velocidades para cada dimensão assumem valores
de acordo com a seguinte equação:
−→
v
id
(t + 1) =
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
−→
v
id
(t + 1), se |
−→
v
id
(t + 1)| < V
max
V
max
, se |
−→
v
id
(t + 1)|≥V
max
e
−→
v
id
(t + 1) ∈ R+
−V
max
, se |
−→
v
id
(t + 1)|≥V
max
e
−→
v
id
(t + 1) ∈ R
∗
−
, (3.4)
onde d ∈{1, 2,...,D},e
−→
v
id
é calculada usando a equação (3.1). O valor de V
max
é de extrema importância para o algoritmo de PSO, visto que esse valor controla a
granularidade da busca. Valores altos de V
max
fazem com que o algoritmo aumente
sua capacidade de realizar busca em amplitude, enquanto valores baixos aumen-
tam a capacidade de realizar busca em profundidade (EBERHART; SIMPSON;
DOBBINS, 1996). Não limitar a velocidade pode levar as partículas ao estado de
explosão (overflight).
27
• Aceleração (c
1
e c
2
): estas constantes controlam a influência dos termos cognitivo
e social. A constante c
1
controla quanto a partícula irá considerar sua própria ex-
periência, e c
2
o quanto a partícula levará em consideração a experiência de sua
vizinhança. Dessa forma se c
1
c
2
, a partícula será influenciada muito mais pela
sua própria experiência, e se c
2
c
1
muito maior será a influência da experiên-
cia da vizinhança. Portanto, uma abordagem comum é considerar c
1
≈ c
2
para
balancear a influência cognitiva e social.
3.1.2.3 Processo de execução do algoritmo
A busca realizada pelo algoritmo de PSO requer uma quantidade específica de passos,
como mostra o Algoritmo 5.
Algoritmo 5: Enxame de partículas atualizando posição e informação cognitiva e
social em busca de soluções.
Saída: Melhor posição encontrada pelo enxame
inicializaEnxame()
1
enquanto passo <= numeroDePassos faça2
para cada partícula do enxame faça3
atualizaVelocidadeEPosicao()4
calculaFitness()5
atualizaMemoria()6
fim7
fim8
retorna melhorPosicaoEncontrada9
Os eventos entre as linhas2e6têmextrema importância para o algoritmo, portanto
uma descrição mais detalhada se torna necessária:
1. A linha 2 indica que a cada iteração todas as partículas do enxame são utilizadas;
2. Cada partícula tem sua velocidade e posição atualizada;
3. Após a atualização de posição, cada partícula calcula o valor da função objetivo
(fitness) relativo à sua nova posição;
28
4. A partir do valor de fitness encontrado, cada partícula atualiza sua memória para
fazer uso e disponibilizar posteriormente sua experiência ao grupo.
Os métodos atualizaVelocidadeEPosicao() e atualizaMemoria() regem o
comportamento das partículas no funcionamento do algoritmo. O primeiro calcula a nova
posição a ser ocupada pela partícula fazendo uso da equação de velocidade, como mostra
o Algoritmo 6.
Algoritmo 6: Posição de uma partícula sendo atualizada tomando como base a
equação de velocidade.
para cada dimensão faça1
novaVelocidade ← velocidadeAtual +c
1
∗ r
1
∗ (melhorPosicaoIndividual −2
posicaoAtual ) + c
2
∗ r
2
∗ (melhorPosicaoDaVizinhanca − posicaoAtual )
novaPosicao ← posicaoAtual + velocidade3
fim4
Analisando a linha 1 do Algoritmo 6, nota-se que a cada iteração do algoritmo PSO
(Algoritmo5), toda partícula do enxame terá calculado cada termo x
id
de suanovaposição.
Portanto, fica claro que além de tornar um problema mais complexo, a quantidade de di-
mensões influencia diretamente na complexidade do algoritmo, e, conseqüentemente, no
seu custo computacional.
O Algoritmo 7 apresenta o processo como cada partícula atualiza suas informações a
cada iteração do algoritmo para um problema de minimização.
Algoritmo 7: Pseudo-código do método de atualização de informação da partícula.
se fitnessAtual < melhorFitnessIndividual então1
melhorFitnessIndividual ← fitnessAtual2
fim3
se fitnessAtual < melhorFitnessVizinhanca então4
melhorFitnessVizinhanca ← fitnessAtual5
fim6
Atualizando suas informações, as partículas do enxame reorganizam suas experiên-
cias. Como se trata de um problema de minimização, para a partícula o menor fitness éo
melhor. Dessa forma, as partículas analisam se sua nova posição melhorou em relação à
anterior, assim como analisam se essa mesma nova posição é melhor do que a encontrada
29
pela vizinhança.
3.2 Diferentes formas: modelos de velocidade
Variações na forma básica do PSO foram propostas para melhorar o desempenho do al-
goritmo quanto à velocidade de convergência e à qualidade das soluções encontradas.
Essas variações alteram diretamente a forma como a velocidade da partícula é calculada.
Nesta seção, serão mostrados dois mecanismos de atualização de velocidade amplamente
utilizados: (i) baseado no fator de inércia e (ii) que utiliza o coeficiente de constrição.
3.2.1 Fator de inércia
Introduzido por Shi e Eberhart (SHI; EBERHART, 1998), o fator de inércia é um meca-
nismo que tem como função controlar a capacidade de realização de busca em amplitude
e em profundidade no decorrer das iterações. Basicamente ele controla a contribuição da
velocidade anterior no próximo passo de cada partícula. O fator de inércia foi inserido na
equação (3.1) como segue:
−→
v
id
(t + 1) = ω
−→
v
id
(t) + c
1
1
−→
p
id
(t) −
−→
x
id
(t)
+ c
2
2
−−→
p
gd
(t) −
−→
x
id
(t)
, (3.5)
onde ω é o fator de inércia.
Se ω ≥ 1, as velocidades irão aumentar seus valores com o decorrer das iterações, ou
seja, as partículas estarão acelerando para chegar a V
max
e realizando, assim, uma busca
em amplitude mais acentuada. Para ω<1, as partículas desaceleram, aumentando a
capacidade de realizar busca em profundidade.
Geralmente, à medida que as iterações ocorrem, o valor de ω é diminuído. Dessa
forma o enxame inicia realizando mais busca em amplitude e vai, aos poucos, diminu-
indo a busca em amplitude e aumentando a busca em profundidade. Um exemplo de
decrescimento de ω é o linear, e normalmente utiliza valores de 0, 9 até 0, 4 (NAKA
et al., 2001)(RATNAWEERA; HALGAMUGE; WATSON, 2002)(SUGANTHAN, 1999)
(YOSHIDA et al., 1999):
ω(t) =
(
ω(0) − ω(n
t
)
)
(n
t
− t)
n
t
+ ω(n
t
) , (3.6)
onde n
t
é a quantidade de iterações, ω(0) e ω(n
t
) são o valor inicial e final do fator de
inércia e ω(t) é o valor do fator de inércia na iteração t.
30
3.2.2 Coeficiente de constrição
Para evitar overflight no espaço de busca, Clerc desenvolveu uma abordagem onde um
coeficiente de constrição χ é aplicado às velocidades (CLERC; KENNEDY, 2002). A
equação de atualização de velocidade foi alterada, originando:
−→
v
id
(t + 1) = χ[
−→
v
id
(t) + c
1
1
(
−→
p
id
(t) −
−→
x
id
(t)) + c
2
2
(
−−→
p
gd
(t) −
−→
x
id
(t))] , (3.7)
onde
χ =
2κ
2 − ϕ −
ϕ
2
− 4ϕ
,ϕ= c
1
1
+ c
2
2
. (3.8)
Sob as condições ϕ ≥ 4eκ ∈ [0, 1], essa abordagem garante a convergência natural
do enxame. Fazendo uso desses valores, o coeficiente de constrição χ assume um valor
entre 0 e 1, induzindo uma redução de velocidade a cada iteração.
O parâmetro κ, na equação (3.8), é quem controla diretamente a relação entre busca
em amplitude e busca em profundidade do enxame. Valores κ ≈ 1 são usados com o
intuito de prover um alto grau de busca em amplitude, mas com convergência lenta. Para
se conseguir uma rápida convergência usando busca em profundidade, valores baixos de
κ são utilizados (κ<1).
Tanto o fator de inércia, quanto o coeficiente de constrição realizam balanceamento
entre as formas de busca e, ao mesmo tempo, melhoram o tempo de convergência e a
qualidade da solução encontrada. Uma comparação de desempenho entre as abordagens
com fator de inércia e coeficiente de constrição (EBERHART; SHI, 2000) (BRATTON;
KENNEDY, 2007) mostrou que o PSO utilizando o fator de constrição possui convergên-
cia mais rápida do que a abordagem com fator de inércia. Entretanto, a abordagem com
coeficiente de constrição tem grande tendência a atingir ótimos locais em funções multi-
modais.
3.3 Troca de informação
Um enxame tem seu próprio mecanismo de comunicação capaz de distribuir a infor-
mação sobre as melhores posições achadas no processo de busca (ENGELBRECHT,
2005) (SUTTON et al., 2006). Essa informação é de extrema importância para atualizar o
31
estado do enxame (velocidade e posição), e é disseminada tomando como base o modelo
de estrutura usado pelas partículas do enxame.
Mesmoalterando o modo de atualizar as velocidades (verSeção 3.2),oalgoritmopode
funcionar ainda melhor explorandoo mecanismo de troca de informação. Como mostrado
na equação (3.1), a troca de informação influencia as partículas durante o cálculo da
velocidade. Os mecanismos de comunicação entre partículas mais comuns são o global e
o local.
Partículas podem trocar informações globalmente através de uma estrutura totalmente
conectada chamada de topologia em estrela mostrada na Figura 3.3(a). Essa topologia
usa uma vizinhança de tamanho igual ao do enxame, e um mecanismo global de comuni-
cação conhecido como gbest para trocar informação. Usando gbest, as partículas podem
disseminar informação rapidamente dentro do enxame. Isso é análogo a uma grande co-
munidade onde todas as decisões tomadas são conhecidas instantaneamente por todos os
membros. Cada partícula que compõe essa topologia é atraída para a melhor solução
achada por todo o enxame.
(a) (b)
Figura 3.3: Estruturas padrão: (a) Topologia estrela usada com gbest e (b) Topologia anel
usada com lbest (adaptados de (BRATTON; KENNEDY, 2007)).
Um mecanismo de troca de informação baseado em vizinhanças locais é conhecido
como lbest. As partículas só trocam informação com os membros de sua própria vizi-
nhança. A estrutura utilizada por esse mecanismo é chamada de topologia em anel e sua
forma está apresentada na Figura 3.3(b). Diferentes regiões do espaço de busca podem ser
32
exploradas ao mesmo tempo, porém as informações de sucesso oriundas dessas regiões
demoram mais tempo para serem enviadas a todas as outras partículas. Cada partícula se
comunica com suas n vizinhas, e tentam seguir a melhor das vizinhas se movimentando
mais perto da melhor solução achada dentro da vizinhança. A idéia de vizinhança não é
espacial, as partículas são indexadas e se comunicam com as n partículas de índice mais
próximo. Essa estrutura de comunicação permite encontrar soluções de maior qualidade
para problemas multi-modais do que a totalmente conectada (ENGELBRECHT, 2005).
J. Kennedy e R. Mendes em (KENNEDY; MENDES, 2002) analisaram alguns aspec-
tos de várias topologias baseadas em vizinhança, dando margem para idéias que giram
em torno de mudar o ambiente do enxame. P. N. Suganthan em (SUGANTHAN, 1999)
propôs variações no tamanho da vizinhança a medida em que as iterações aconteciam.
Isso indica que a melhoria de desempenho no algoritmo de PSO depende diretamente das
interações dinâmicas entre partículas dentro do enxame.
3.4 Variação das estruturas sociais: topologias
A interação social entre as partículas dentro do enxame pode ser vista como uma rede
populacional que possui membros e conexões. Considerando essa analogia, a estrutura
formada pelos membros pode ser definida como uma topologia, onde os membros são
as partículas que podem trocar informação com as outras de acordo com uma determi-
nada regra. Baseado na experiência obtida, as partículas se movem com o intuito de se
tornarem cada vez mais parecidas com suas melhores vizinhas. Partículas que pertencem
a uma mesma vizinhança se comunicam entre si para transmitir a experiência de sucesso
conseguida durante o processo de busca. Então, todas as partículas se moverão para o
ponto que está marcado como o melhor naquele momento. O fluxo de informação entre
as partículas depende do grau de conectividade e das vizinhanças na topologia.
Utilizando uma topologia fortemente conectada, todos os membros irão procurar o
mesmo ponto dentro do espaço de busca. Isso significa que o enxame é levado a con-
vergir mais rápido para uma solução com um número de iterações razoável. Porém, uma
convergência muito rápida pode causar a estagnação das partículas em mínimos locais.
Por outro lado, para topologias mais distribuídas, o problema de mínimos locais pode ser
evitado, mas um número maior de iterações será necessário para varrer todo o espaço de
33
busca. Topologias que utilizam agrupamentos de partículas têm sido consideradas para
balancear o comportamento das abordagens gbest e lbest.
Diferentes tipos de estruturas foram desenvolvidas para alterar o modo como a infor-
mação flui dentro do algoritmo de PSO (EBERHART; SIMPSON; DOBBINS, 1996)(KE-
NNEDY, 1999)(KENNEDY; MENDES, 2002)(MENDES et al., 2002). A seguir serão
descritas três estruturas bastante utilizadas:
• Estrutura em roda ou focal (wheel): nessa estrutura, mostrada na Figura 3.4,
uma única partícula serve como foco de informação para o resto da vizinhança. A
partícula foco compara o desempenho das restantes e ajusta sua posição através da
melhor partícula vizinha. Caso ela melhore sua posição, essa melhoria é transmitida
para toda a vizinhança que a tem como foco.
Figura 3.4: Topologia focal.
• Von Neumann: as conexões são feitas formando uma espécie de grade de partícu-
las. Esse tipo de topologia está mostrada na Figura 3.5, e mostrou-se melhor do
que outras estruturas sociais em diversos problemas de otimização (KENNEDY;
MENDES, 2002)(PEER; BERGH; ENGELBRECHT, 24-26 April 2003).
• Quatro grupos (four clusters): consiste em conectar grupos de partículas (MEN-
DES; KENNEDY; NEVES, 2003). Cada grupo possui uma partícula chamada de
informante, responsável por propagar a informação do grupo para os vizinhos. O
número de informantes em cada agrupo é exatamente o número de grupos vizinhos.
Por exemplo, se um grupo possui duas partículas informantes, este se comunica
com dois outros grupos. Essa estrutura é mostrada na Figura 3.6.
34
Figura 3.5: Topologia Von Neumann.
Figura 3.6: Topologia de quatro grupos que faz uso de informantes estáticos já definidos
no início da simulação (adaptado de (ENGELBRECHT, 2005)).
Note que os informantes de um grupo são estáticos, eles permanecem os mesmos du-
rante todo o processamento do algoritmo de PSO. Por exemplo, na Figura 3.6 as partículas
em cinza de cada um dos quatro grupos serão seus informantes em todas as iterações do
algoritmo. Usando essa estrutura, a informação que flui é a de um informante para outro.
Dessa forma, informação de grande qualidade oriunda de outras partículas demorará para
ser transmitida para os outros grupos. Isso pode aumentar a quantidade de iterações.
35
3.5 Otimização por enxames de partículas baseada em
clãs
Nesta seção será descrita uma nova topologia baseada no comportamento de clãs de indi-
víduos. Assim como as descritas na seção anterior, essa topologiatenta melhorar o desem-
penho do PSO alterando o modo como as partículas se comunicam. As seções seguintes
detalham a topologia, assim como os processos de comunicação utilizados. Os experi-
mentos envolvendo a topologia de Clãs produziram resultados melhores em relação às
topologias já existentes, que foram utilizadas como comparativo nos experimentos. Esses
resultados originaram a publicação da abordagem proposta na conferência IEEE World
Congress on Computational Intelligence, WCCI 2008 (CARVALHO; BASTOS-FILHO,
2008).
3.5.1 O conceito do clã de partículas
Clãs são grupos de indivíduos, ou tribos, unidos por um parentesco baseado em uma li-
nhagem ou meramente simbólico. Alguns clãs apenas estipulam um ancestral em comum
para se tornar o símbolo do clã, e todo indivíduo pertencente ao clã terá esse símbolo
como guia. O significado social de um clã pode ser visto como uma pequena parte de
uma sociedade maior.
Inspirado pela entidade descrita acima e fazendo uso de sua característica de liderança,
uma nova topologia para partículas foi proposta a fim de melhorar o desempenho do
algoritmo de PSO (CARVALHO; BASTOS-FILHO, 2008). Como parte da topologia, o
clã é formado por partículas utilizando uma estrutura totalmente conectada para trocar
informação (gbest). Figura 3.7 ilustra uma estrutura contendo um exemplo com quatro
clãs (A, B, C e D) de cinco partículas.
Para cada iteração, cada clã realiza uma buscae define a partícula que chegou a melhor
posição de todo o clã.
3.5.2 Eleição do líder
O processo de marcar o melhor dentro do clã é exatamente o mesmo de estipular um
símbolo para o clã para servir como guia. É o mesmo que delegar o poder de liderar os
36
B
1
5
4
3
2
D
1
2
3
4
5
C
5
1
2
4
3
A
2
3
4
5
1
Figura 3.7: Partículas organizadas em grupos menores, denominados clãs.
outros indivíduos do grupo. Figura 3.8 pode ser utilizada para representar esse processo
de eleição. Todos os líderes marcados (eleitos) possuem cor cinza. Usando a notação X
i
para representar a partícula i do clã X, os líderes na Figura 3.8 são: A
3
, B
5
, C
5
e D
1
.
D
1
2
3
4
5
1
A
2
3
4
5
1
B
1
4
3
2
5
C
1
2
4
3
5
Figura 3.8: Eleição dos líderes de cada clã.
Ao utilizar o mecanismo de troca de informação global dentro de cada clã, o processo
de eleição usa a informação oriunda do gbest para eleger diretamente o líder. Assim,
nenhum processamento extra é necessário para delegar o líder.
A topologia de clãs é um ambiente social formado por vários clãs e, portanto, por
diferentes líderes. Analisando esse fato, uma questão interessante pode surgir: “Qual o
líder que merece ser seguido por todos os clãs?”.
37
3.5.3 A conferência de líderes
A questão acima pode ser respondida da seguinte forma: “A partícula que chegou à me-
lhor posição!”, mas isso tornaria a topologia de clãs em uma simples estrutura totalmente
conectada que apenas possui o mecanismo de troca de informação dividido em dois pas-
sos. Portanto, todos os líderes não precisam só decidir qual deles é o melhor, eles também
precisam ajustar suas posições se baseando no melhor dos líderes. Isso é feito executando
um novo PSO utilizando o conjunto de líderes eleitos como um enxame.
Como a conferência faz uso do ambiente natural criado entre partículas e enxame, a
mesma pode utilizar gbest ou lbest como mecanismo de troca de informação.
Por exemplo,supondo que o melhor líder é a partículaC
5
. Quando a conferência acon-
tece, todos os outros líderes irão ajustar suas posições através da melhor posição achada
por C
5
. Isso ocorre quando a conferência usa o mecanismo de troca de informação global,
como mostrado na Figura 3.9. Isso melhora a capacidade de busca em profundidade dos
líderes.
D
C
B
A
3
1
5
5
Figura 3.9: Troca de informação realizada na conferência global de líderes na topologia
de clãs.
Por outro lado, utilizando o mecanismo de troca de informação local mostrado na
Figura 3.10, os líderes se comunicarão com vizinhos específicos, evitando assim con-
vergência pré-matura.
O processo de conferência usa apenas os líderes de cada clã para realizar uma nova
busca. Para poucos clãs, esse processo não envolve muito mais processamento por conta
do pequeno tamanho do grupo de líderes. Então, o algoritmo terá sua complexidade
38
D
C
B
A
1
5
5
3
Figura 3.10: Troca de informação realizada na conferência local de líderes na topologia
de clãs.
mantida.
Esse tipo de aplicação depende do ambiente do problema a ser resolvido. Nas seções
mais adiante serão mostradas diferentes resultados de simulações utilizando a topologia
totalmente conectada (gbest) e também a topologia em anel (lbest) na realização do pro-
cesso de conferência.
3.5.4 O retorno de informação para cada clã
Após o processo da conferência de líderes, cada líder retornará para seu próprio clã. As
novasinformações adquiridas na conferência serãopropagadas amplamente dentro do clã.
Esse fluxo de informação é representado na Figura 3.11 pelas linhas cheias entre o líder
do clã e as outras partículas que compõem o clã.
Essa ação irá guiar indiretamente todas as partículas para a melhor posição achada
dentro de toda a topologia. Dessa forma, todo o enxame obterá uma convergência natural
para o melhor ponto achado.
Fazendo uso do ambiente criado em torno dos clãs para a disseminaçãode informação,
os líderes externos não influenciarão diretamente o clã ao qual eles não pertencem, então
a capacidade de busca em amplitude original de cada clã será preservada.
39
B
1
4
3
2
D
2
3
4
5
A
2
4
5
1
C
1
2
4
3
1
5
3
5
Figura 3.11: Fluxo de informação dentro de cada clã após a conferência.
3.5.5 Experimentos
Para a realização dos experimentos, funções de teste foram escolhidas para avaliar o de-
sempenho da nova topologia proposta.
3.5.5.1 Funções de teste
Cinco funções foram usadas para realizar as simulações e estão descritas em (3.9), (3.10),
(3.11), (3.12), e (3.13). A Tabela 3.1 mostra espaço de busca, intervalo de inicialização,
número de dimensões usadas e o ponto ótimo de cada função. Todas as cinco funções são
problemas de minimização. Duas dessas funções (Rosenbrock e Schwefel 1.2) são pro-
blemas uni-modais simples, e as outras três (Rastrigin, Griewank e Ackley) são funções
multi-modais de alta complexidade que contém múltiplos mínimos locais.
A primeira função, Rosenbrock, possui um mínimo global localizado numa região de
formato arqueado. Essa região onde se encontra o mínimo é fácil de ser encontrada, mas a
partir dela a convergência para o mínimo global é bastante difícil. Essa função é definida
como se segue:
F
Rosenbrock
(x) =
n−1
i=1
(
100(x
i+1
− x
2
i
)
2
+ (1 − x
i
)
2
)
. (3.9)
A segunda função, Rastrigin, é uma função multi-modal que induz a busca em míni-
mos locais distribuídos como saltos senoidais. A definição dessa função é:
F
Rastrigin
(x) = 10n +
n
i=1
(
x
2
i
− 10cos(2πx
i
)
)
. (3.10)
40
A terceira e quarta funções são Griewank e Ackley. Essas funções são multi-modais
de alta complexidade e possuem muitos mínimos locais. Suas definições são:
F
Griewank
(x) = 1 +
n
i=1
x
2
i
4000
−
n
i=1
cos
(
x
i
√
i
)
, (3.11)
F
Ackley
(x) = −20 · exp(−0.2
1
n
·
n
i=1
x
2
i
)
− exp
(
1
n
·
n
i=1
cos(2πx
i
)
)
+ 20 + e. (3.12)
A quinta e última função é Schwefel 1.2, que é um simples problema uni-modal e
definida como:
F
Schwefel
(x) =
n
i=1
(
i
j=1
x
j
)
2
. (3.13)
Tabela 3.1: Espaço de busca, intervalo de inicialização, número de dimensões e ótimo de
cada função de teste utilizada.
Função Espaço de busca Inicialização Dimensões Ótimo
Rosenbrock −30 ≤ x
i
≤ 30 15 ≤ x
i
≤ 30 30 1, 0
D
Rastrigin −5, 12 ≤ x
i
≤ 5, 12 2, 56 ≤ x
i
≤ 5, 12 30 0, 0
D
Griewank −600 ≤ x
i
≤ 600 300 ≤ x
i
≤ 600 30 0, 0
D
Ackley −32 ≤ x
i
≤ 32 16 ≤ x
i
≤ 32 30 0, 0
D
Schwefel 1.2 −100 ≤ x
i
≤ 100 50 ≤ x
i
≤ 100 30 0, 0
D
3.5.5.2 Arranjo experimental
Foi utilizada a forma do PSO que faz uso do fator de constrição em todas as simulações
realizadas. Para compor o fator de constrição (χ) foram usados os valores: κ = 1, c
1
=
2, 05 e c
2
= 2, 05 (ϕ ≥ 4), e todas as simulações foram realizadas utilizando 30 partículas.
Foi realizada uma variação no tamanho dos clãs, mas o número total de partículas no
enxame foi mantido.
Após30 simulações usando omesmo número de clãs, as médias das curvasde evolução
de cada simulação foram traçadas e armazenadas. O grau de convergência associado a
41
cada diferente distribuição de clãs pode ser estimado comparando cada curva de evolução
através de um gráfico.
Os enxames de cada simulação foram inicializados, para cada dimensão, numa área
afastada da região onde o ótimo da função está localizado. Isso permite uma análise de
convergência justa entre cada topologia utilizada nos experimentos.
3.6 Resultados das simulações
Resultados dos experimentos envolvendo todas as cinco funções de teste são descritos
nessaseção. Informações detalhadas sobre os resultadosdas três primeiras funções (Rosen-
brock, Rastrigin e Griewank) são apresentados nas próximas sub-seções 3.6.1, 3.6.2, e
3.6.3.
3.6.1 Rosenbrock
Figura 3.12 e Figura 3.13 mostram a curva de convergência da melhor média de fitness
encontrado na função Rosenbrock para 3 diferentes tamanhos de clã. Cada figura repre-
senta o uso, na conferência de líderes, do mecanismo de troca de informação global e
local, respectivamente.
Figura 3.12: Simulação com a função Rosenbrock usando clãs com conferência global.
Na Figura 3.12, foi também incluída a topologia em estrela (gbest). Essa topologia foi
incluída, pois corresponde ao caso de 1 clã com 30 partículas ou 30 clãs com 1 partícula,
42
portanto deve entrar nessa comparação.
Nas primeiras 5000 iterações, os enxames de diferentes configurações obtiveramapro-
ximadamente o mesmo resultado. Esse fato indica que os enxames estão localizados na
região mais problemática do espaço de busca da função Rosenbrock. As configurações
3-, 6- e 10-clãs conseguiram sair dessa região mais rapidamente do que a topologia gbest
(configuração 1-clã). A configuração com 3 clãs conseguiu o melhor valor de fitness com
o passar das iterações utilizando conferência global.
Figura 3.13 apresenta as curvas de convergência utilizando conferência local. Nesta,
a topologia em anel também foi utilizada por corresponder à configuração com 30 clãs de
1 partícula.
Figura 3.13: Simulação com a função Rosenbrock usando clãs com conferência local.
A configuração 3-clãs obteve praticamente os mesmos resultados que a 6-clãs, e as
duas foram melhores que a topologia lbest (configuração 30-clãs).
Tabela 3.2 apresenta os resultados de todas as configurações com clãs utilizando tanto
conferência do tipo global quanto local. A coluna Configuração contém os valores usa-
dos para compor a estrutura das partículas (tipo de conferência, número de clãs e número
de partículas por clã). A coluna Fitness contém o valor de fitness conseguido após dois
números específicos de iterações (5000 e 10000 para a função Rosenbrock).
Utilizando a topologia de clãs com conferência global, após 5000 iterações o enxame
composto de 3 clãs conseguiu um fitness F = 10, 78602. Esse valor é menor do que
a metade do conseguido por gbest (F = 23, 31243). Essa taxa é mantida após 10000
43
Tabela 3.2: Média de fitness para a função Rosenbrock após 5000 e 10000 iterações
usando conferência global e local.
Configuração
da topologia
Fitness
5000 iterações 10000 iterações
Config. Clãs Partículas Média Desvio padrão Média Desvio padrão
Global
1 30 23, 31243 29, 058 8, 26316 16, 680
3 10 10,78602 12,980 3,28551 3,493
6 5 18, 0103 23, 810 8, 02928 17, 706
10 3 23, 06002 31, 92 15, 50264 28, 149
Local
3 10 22, 48756 27, 038 6,97792 13,205
6 5 19,47569 23,330 7, 84296 13, 617
10 3 43, 31156 34, 417 12, 97416 21, 429
30 1 31, 08434 30, 853 14, 20547 22, 446
iterações, onde foi conseguido F = 3, 28551 para a configuração com 3 clãs, e F =
8, 26316 para gbest.
Com a conferência do tipo local, as configurações 3-, 6- e 10-clãs obtiveram melhores
resultados quando comparadas à topologia lbest (30 clãs). Passadas 5000 iterações, a
configuração com 6 clãs atingiu F = 19, 47569 e a configuração com 3 clãs chegou a F =
22, 48756. Essas duas abordagens de clã conseguiram melhores valores de fitness do que
a abordagem puramente local que atingiu F = 31, 08434. Porém, após 10000 iterações
a configuração 3-clãs conseguiu o melhor valor (F = 6, 97792) seguida pela abordagem
com 6 clãs (F = 7, 84296). A configuração 10-clãs obteve F = 12, 97416. Todas as
configurações baseadas em clãs atingiram melhores resultados do que a topologia lbest
(F = 14, 20547).
3.6.2 Rastrigin
A análise da curva de convergência da função Rastrigin para cada uma das configurações
com clãs usando conferência global está apresentada na Figura 3.14, e usando conferência
local na Figura 3.15.
44
Figura 3.14: Simulação com a função Rastrigin usando clãs com conferência global.
Na Figura 3.14, as configurações com 3, 6 e 10 clãs convergiram mais rápido do que a
topologia gbest. Essas três configurações obtiveram curvas de convergência equivalentes,
atingindo valores de fitness próximos.
A análise das configurações que abordam conferência local na Figura 3.15 mostra que
a topologia lbest converge mais lentamente que as configurações baseadas em clãs.
Figura 3.15: Simulação com a função Rastrigin usando clãs com conferência local.
Após uma quantidade de iterações, os resultados da topologia lbest tendem a um valor
constante. Diferentemente, com o aumento do número de iterações os resultados são me-
lhorados quando se usa a configuração com 3 clãs. Essa configuração obteve um melhor
45
desempenho ao longo das iterações. Os resultados dos experimentos utilizando os dois
tipos de conferência estão mostrados na Tabela 3.3.
Tabela 3.3: Média de fitness para a função Rastrigin após 5000 e 10000 iterações usando
conferência global e local.
Configuração
da topologia
Fitness
5000 iterações 10000 iterações
Config. Clãs Partículas Média Desvio padrão Média Desvio padrão
Global
1 30 53, 76086 15, 394 53, 76086 15, 394
3 10 16,25285 5,338 10,35125 4,321
6 5 20, 77329 5, 261 15, 13877 6, 197
10 3 19, 28359 9, 861 14, 51142 11, 325
Local
3 10 9,99068 4,360 5,01146 4,015
6 5 16, 96074 4, 118 10, 5037 4, 026
10 3 24, 205 6, 730 17, 6504 5, 481
30 1 42, 6643 8, 425 42, 5422 8, 383
Após5000 iterações, a topologiagbest atingiu um valorde fitnesspior (F = 53, 76086)
do que as configurações com clãs usando conferência global. O melhor valor de fitness
conseguido foi F = 16, 25285 pela configuração com 3 clãs. Esse valor foi melhor do que
os achados pelas outras configurações. Após 10000 iterações a topologia gbest manteve o
mesmo valor de fitness (F = 53, 76086). As configurações com clãs usando conferência
global melhoraram seus fitness para valores melhores do que a avaliação anterior. Mais
uma vez a configuração com 3 clãs atingiu o melhor valor de fitness (F = 10, 35125).
Os valoresde fitness calculados usando clãs com conferência local demonstramo quão
rápida é a convergência nesse caso. As configurações com clãs atingiram resultados satis-
fatórios quando comparadas com a topologia lbest pura. A configuração 3-clãs conseguiu
o melhor valor de fitness após 5000 e 10000 iterações (F = 9, 99068 e F = 5, 01146).
Esses valores são extremamente melhores do que os encontrados pela topologia lbest
(F = 42, 6643 and F = 42, 5422).
Os resultados obtidos pelas simulações com a função Rastrigin mostram que, para
essa função, a conferência local se comporta melhor do que a global.
46
3.6.3 Griewank
A análise dessa função é um pouco diferente das outras. Nessa função, o algoritmo de
PSO possui uma rápida convergência para a região do mínimo, portanto poucas iterações
são necessárias para chegar a esse lugar no espaço de busca. Por conta dessa convergência
prematura, a curva de convergência será traçada até 2000 iterações.
Figura 3.16 e Figura 3.17 mostram a curva de convergência de cada configuração
com clãs usando conferência global e local, respectivamente. Como nas outras funções,
as topologias gbest e lbest foram usadas na comparação de resultados para cada tipo de
conferência.
Figura 3.16: Simulação com a função Griewank usando clãs com conferência global.
Para a conferência de tipo global, todas as curvas de convergência obtidas a partir das
configurações com clãs foram melhores do que a topologia global pura gbest. A partir
da iteração de número 400, as abordagens com clãs convergiram para valores de fitness
melhores do que o encontrado por gbest, mostrando a melhoria em relação à topologia
global pura.
Nos resultados obtidos usando conferência local (ver Figura 3.17) todas as configura-
ções tiveram um grau de convergência alto, de forma que com 500 iterações já obtiveram
valores satisfatórios de fitness. Essa rápida convergência se dá por conta da parcela de
troca de informação global sempre existente em cada clã, diferentemente da abordagem
local pura. No entanto, a partir da milésima iteração a abordagem local pura lbest con-
vergiu para valores melhores de fitness, por conta do melhor desempenho da troca local
47
Figura 3.17: Simulação com a função Griewank usando clãs com conferência local.
de informação em problemas multi-modais.
Os resultados na Tabela 3.4 fazem uso de números diferentes de iterações (200 e 600)
para mostrar valores importantes de fitness na análise da curva de convergência. Esses
valores são menores em relação à análise das outras funções, mas isso ocorre por conta
da rápida convergência peculiar da função Griewank.
Tabela 3.4: Média de fitness para a função Griewank após 200 e 600 iterações usando
conferência global e local.
Configuração
da topologia
Fitness
200 iterações 600 iterações
Config. Clãs Partículas Média Desvio padrão Média Desvio padrão
Global
1 30 1, 06806 0, 0537 0, 03402 0, 0376
3 10 1, 09424 0, 0778 0, 02214 0, 0451
6 5 1, 08760 0, 0854 0,01107 0,0135
10 3 1,03716 0,0465 0, 01353 0, 0205
Local
3 10 1,20251 0,1032 0, 01179 0, 0149
6 5 1, 38511 0, 1961 0,01140 0,0164
10 3 1, 76830 0, 3229 0, 01827 0, 0168
30 1 6, 08725 1, 4890 0, 68589 0, 1661
48
Analisando a Tabela 3.4 para a conferência global, vê-se que, após 200 iterações, o
melhor valor de fitness foi conseguido pela configuração com 10 clãs (F = 1, 03716).
Após 600 iterações a configuração 6-clãs atingiu F = 0, 01107, que para essa iteração
foi o melhor valor encontrado, seguido pelas outras abordagens de clã e por último a
topologia global pura. Inicialmente, a abordagem com 10 clãs conseguiu melhor valor
de fitness, pois tem uma maior número de clãs e, portanto, explora um maior número de
regiõesdo espaço de buscamais rapidamente. Porém com 6 clãs, se tem um maior número
de partículas por clã trocando informações, o que refina a busca de cada clã, levando o
enxame para uma melhor solução.
Os resultados das simulações com conferência local mostrados na Tabela 3.4 acusam
que, após 200 iterações, os melhores valores de fitness foram conseguidos pelas confi-
gurações com clãs. A melhor entre elas foi a 3-clãs com F = 1, 20251, seguida pela
6-clãs com F = 1, 38511 e pela 10-clãs com F = 1, 76830, e a topologia lbest conseguiu
F = 6, 08725. Com o decorrer de 600 iterações, as configurações com clãs também con-
seguiram valores de fitness melhores, sendo o mais satisfatório o encontrado pela 6-clãs
(F = 0, 01140). Ao utilizar 3 clãs, o enxame passa a ter mais troca global de informação,
o que acelera sua convergência. Já utilizando 6 clãs, o enxame balanceia, através da
conferência local, a troca global e local de informação, chegando a melhores soluções.
Claramente se nota uma qualidade maior nas soluções encontradas pelas abordagens
locais para a função Griewank e Rastrigin. A análise comparativa entre a abordagens
com clã usando conferência local, e a topologia lbest são de grande valia para demonstrar
a capacidade proposta pela topologia de clãs. Capacidade essa que permite ao enxame
conseguir uma rápida convergência, devido a sua comunicação global dentro de cada
clã, e atingir soluções com maior qualidade para funções que exigem comunicação local
(Griewank e Rastrigin, por exemplo) usando a conferência de tipo local.
3.6.4 Comparação entre as topologias de clusters e de clãs
Nessa seção será apresentada a comparação de desempenho da topologia de quatro gru-
pos (ENGELBRECHT, 2005) com a topologia de clãs (CARVALHO; BASTOS-FILHO,
2008). Para criar um ambiente compatível entre essas duas topologias, foram usados 3
clãs em comparação com 3 clusters.
Figura 3.18 apresenta as curvas de convergência para função Rosenbrock usando a
49
topologia de clãs com conferência global e local, e a topologia com 3 clusters.
Figura 3.18: Comparação entre as topologias de grupos e de clãs para a função Rosen-
brock.
As curvas de convergência da topologia de clusters e de clãs usando conferência local
são equivalentes. Porém, a topologia de clãs usando conferência global conseguiu melhor
grau de convergência em relação à topologia de clusters, no decorrer das iterações. Os
resultados para todas as funções de teste são mostrados na Tabela 3.5. A coluna Simu-
lação mostra a função e a topologia usada para realizar a simulação. A coluna Fitness é
a mesma das Tabelas 3.2, 3.3 e 3.4.
Os valores de fitness conseguidos pela topologia de clusters foram F = 21, 09623 e
F = 6, 47014 para 5000 e 10000 iterações, respectivamente. Os valores atingidos pela
topologia de clãs usando conferência local foram similares aos conseguidos através da
topologia de clusters, sendo F = 22, 48756 e F = 6, 97792. Contudo, a topologia de clãs
usando conferência global chegou à valores muito melhores do que as outras duas em
análise (F = 10, 78602 e F = 3, 28551 para 5000 e 10000 iterações, respectivamente).
Como mostrado na Figura 3.19, as curvas de convergência da função Rastrigin são
claramente melhores para a topologia de clãs, tanto usando conferência global quanto
local. No decorrer das iterações, as duas abordagens com clãs conseguiram valores de
fitness muito mais satisfatórios do que a topologia baseada em clusters.
Tabela 3.5 mostra que após 5000 iterações, a topologia de clãs usando tanto conferên-
cia global (F = 16, 25285) quanto local (F = 9, 99068) obtiveram melhores resultados do
50
Tabela 3.5: Resultados da comparação entre as topologias de clusters e de clãs.
Função Topologia
Fitness
Média Desvio padrão Média Desvio padrão
Simulação 5000 iterações 10000 iterações
Rosenbrock
Clusters 21, 09623 33, 560 6, 47014 13, 888
Clãs-Global 10,78602 12,980 3,28551 3,493
Clãs-Local 22, 48756 27, 038 6, 97792 13, 205
Rastrigin
Clusters 43, 34758 12, 249 43, 21492 12, 574
Clãs-Global 16, 25285 5, 338 10, 35125 4, 321
Clãs-Local 9,99068 4,360 5,01146 4,015
Schwefel 1.2
Clusters 99, 6774 158, 551 6, 09582 15, 086
Clãs-Global 2,96e-05 3,6e-05 2,01e-13 3,9e-13
Clãs-Local 1,71e-01 0, 176 8,4e-06 1,7e-05
Simulação 200 iterações 700 iterações
Ackley
Clusters 20, 13967 0, 108 19, 90257 0, 055
Clãs-Global 17,34014 6,500 16,20549 7,844
Clãs-Local 19, 47019 3, 657 18, 92163 5, 141
Simulação 200 iterações 600 iterações
Griewank
Clusters 4, 79560 2, 3951 0, 41650 0, 2854
Clãs-Global 1,09424 0,0778 0, 02214 0, 0451
Clãs-Local 1, 20251 0, 1032 0,01179 0,0149
que a topologia baseada em clusters (F = 43, 34758). A topologia de clusters manteve
praticamente o mesmo valor de fitness após 10000 iterações (F = 43, 21492), enquanto
a topologia de clãs conseguiu F = 10, 35125 usando conferência global e F = 5, 01146
usando local. Fazendo uso de conferência local, a topologia baseada em clãs atingiu um
desempenho altamente satisfatório. Para a função Rastrigin, a topologia de clãs convergiu
para o ótimo mais rápido do que a topologia de clusters.
Como para as outras funções, a comparação entra clãs e clusters envolvendo a função
Griewank foi favorável à topologia baseada em clãs. Figura 3.20 mostra o quão rápida
51
Figura 3.19: Comparação entre as topologias de grupos e de clãs para a função Rastrigin.
é a convergência usando a topologia de clãs. O enxame baseado em clãs obteve melhor
desempenho quando usou conferência local (ver Figura 3.20). Os valores contidos na
Tabela 3.5 mostram que o ambiente criado pela topologia de clãs usando conferência
local e global levam todo o enxame para a região do ótimo usando um pequeno número
de iterações (F = 1, 09424 após 200 iterações e F = 0, 01179 após 600 iterações).
Figura 3.20: Comparação entre as topologiasde grupos e de clãs para a função Griewank.
Fica clara a superioridade da topologia de clãs sob a topologia de clusters. Isso se dá
pelo processo de eleição de líderes associado à conferência realizada pelos líderes eleitos.
Essas vantagens podem ser listadas como:
52
• Informante estático x líder dinâmico: na topologia de clusters, o informante de
cada grupo é estático, assim ele pode ser a melhor partícula do grupo, passando a
melhor informação para os outros grupos; ou ser uma partícula ruim, propagando
informação de má qualidade. O processo de eleição, pertencente à topologia de
clãs, define dinamicamente a cada iteração qual das partículas de um clã é a melhor
para propagar seu sucesso ao restante do enxame, acelerando assim a convergência
do algoritmo;
• Conferência global: permite ao enxame definir se pretende acelerar mais ainda sua
convergência trocando informações globalmente entre líderes;
• Conferência local: possibilidade de realizar mais exploração em profundidade
atravésde uma propagação local de informação,melhorandoa qualidade da solução
encontrada pelo enxame.
Essas qualidades mostram que fazendo uso da capacidade natural de disseminação
de informação vinda do algoritmo de PSO associada a diferentes formas de comunicação,
como a abordagembaseada em Clãs apresentada de forma original aqui, se pode melhorar
a velocidade e qualidade de busca do algoritmo.
53
Capítulo 4
Roteamento e Alocação de Canais
Ópticos Transparentes
4.1 Caracterização do problema
Com o crescimento da demanda de tráfego de dados na internet e a evolução dos sistemas
de comunicações, tornou-se necessário o desenvolvimento de algoritmos de roteamento
mais eficientes voltados para redes de telecomunicações de alta capacidade. O processo
de roteamento interfere drasticamente no desempenho de uma rede. Para cada chamada
que venha ocorrer na rede, deve-se definir uma rota (caminho) entre os nós de origem e
destinoque possua o menor custo. Esse processo é chamado de roteamento. O roteamento
pode ser bastante complexo, devido à existência de diversos fatores que dificultam a busca
por rotas satisfatórias.
A maior parte dos algoritmos de roteamento atuais envolvem o uso de processos que
se baseiam em métricas pré-definidas para achar um caminho entre nós origem e destino.
A rota escolhida pelo algoritmo deveser capaz de obter uma alta qualidade de transmissão
e evitar a quantidade de problemas causados por penalidades oriundas da camada física.
Alguns exemplos de algoritmos de roteamento utilizados são: o de menor caminho (DI-
JKSTRA, 1959), menor atraso (ALI; KAMOUN, Nov 1993), maior relação sinal-ruído
(principalmente para o caso das redes ópticas transparentes) (MARTINS-FILHO et al.,
20-23 Sept. 2003), entre outros.
Do ponto de vista prático, uma melhoria válida é tornar o processo de roteamento
adaptativo em tempo real. Dessa forma, o processo deve ser capaz de se adequar a
54
possíveis alterações, como queda de links e redução, ou aumento, no tamanho da rede
(número de nós). Paralelamente, o processo deve manter uma qualidade de serviço (QoS,
Quality of Service) previamente estipulada. Em geral, a qualidade de serviço é associ-
ada à taxa de erro por bit (BER, Bit Error Rate), à perda de pacotes ou à quantidade de
requisições de chamadas não atendidas.
Estendendo o problema de roteamento para redes ópticas, diferentes fatores passam a
interferir na atuação e na precisão do algoritmo de roteamento. Fatores como os efeitos
degradantes da camada física não podem ser desprezados sob pena do caminho óptico não
atingir a QoS estipulada. Esses efeitos, juntamente com o grau de liberdade gerado no
problema de alocação de canais, tornam o sistema de gerenciamento bastante complexo.
Em redes ópticas transparentes que utilizam Multiplexaçãopor Comprimento de Onda
(WDM, Wavelength Division Multiplexing), a comunicação é realizada fazendo uso dos
canais existentesnosenlaces, formando assimum caminho óptico(lightpath) (MUKHER-
JEE, 1997)(CHLAMTAC; GANZ; KARMI, Jul 1992).
Nessas redes, os dados são transmitidos entre os nós de origem e de destino no
domínio óptico, e sem conversão para o domínio eletrônico. Para que não seja necessária
esse tipo de conversão, o nó de origem deve ser capaz de estabelecer uma conexão con-
tínua na camada óptica até o nó de destino. Além disso, em redes que não admitem
conversão de comprimento de onda nos nós, um mesmo comprimento de onda deve ser
atribuído em todos os enlaces de fibra que formam o caminho. Assim, não haverá conflito
de canal com outros lightpaths que compartilham estes enlaces. Um único comprimento
de onda é reservado para essa conexão desde o nó de origem até o nó de destino. Esse
comprimento de onda será liberado em todos os enlaces da rota assim que a conexão for
encerrada.
Figura 4.1 mostra uma rede WDM composta por quatro nós com enlaces ópticos con-
tendo quatro possíveis comprimentos de onda {λ
0
,λ
1
,λ
2
,λ
3
}. Três lightpaths C
1
, C
2
e C
3
estão definidos ligando os nós 0 e 2,1e3,e0e3,respectivamente.
Os lightpaths C1eC2 têm em comum o enlace (1, 2), porém utilizam comprimentos
de onda diferentes, λ
0
para C
1
e λ
1
para C2. Note que o lightpath C3 faz uso de todos os
enlaces da rede, ou seja, possui enlaces em comum com C1eC2 em toda a sua extensão.
Porém C3 utiliza o comprimento λ
3
, podendo assim estabelecer sua rota independente de
C1eC2.
55
Nó 0
λ
0
λ
1
λ
2
λ
3
Nó 1 Nó 2 Nó 3
Comprimentos
de onda
Enlace (0,1) Enlace (1,2) Enlace (2,3)
lightpath C2lightpath C1 lightpath C3
Figura 4.1: Rede WDM com comprimentos de onda {λ
0
,λ
1
,λ
2
,λ
3
} e três lightpaths C1,
C2eC3 definidos.
A Figura 4.2 mostra uma rede onde dois lightpaths são alocados por diferentes rotas.
O primeiro deles, representado por A na Figura 4.2, liga o nó 0 ao 5 utilizando ao todo
quatro enlaces ópticos e fazendo uso de um comprimento de onda (λ
1
). Na mesma figura
é mostrado um segundo lightpath (B) que cria uma rota entre os nós 2 e 5 utilizando outro
comprimento de onda disponível (λ
2
).
Representação de um nó de borda
Representação de um nó de núcleo para roteamento
Light path usando o comprimento λ
1
Light path usando o comprimento λ
2
0
1
2
3
4
5
6
A
B
Figura 4.2: Diagrama de uma rede óptica WDM mostrando duas rotas diferentes uti-
lizando λ
1
e λ
2
.
As duas rotas da Figura 4.2 possuem enlaces em comum, porém utilizam compri-
mentos de onda distintos. Analisando as rotas A e B pode-se perceber que cada uma
utiliza apenas um comprimento de onda (λ
1
para A e λ
2
para B) em todos os enlaces
56
das rotas traçadas. Essa é uma característica dos sistemas que serão abordados nesta dis-
sertação. Serão consideradas redes que não apresentam conversores de comprimento de
ondas, portanto deve-se definir um caminho que use o mesmo comprimento de onda em
todos os enlaces do lightpath. Essa limitação é chamada de restrição de continuidade de
comprimento de onda (wavelength-continuity constraint).
Sendo os lightpaths a base desta arquitetura de rede, torna-se crucial encontrá-los da
forma mais eficiente. Torna-se então de extrema importância a determinação das rotas,
como também a atribuição de um comprimento de onda (λ) para cada caminho. Du-
rante todo o decorrer desse processo, geralmente há a tentativa de otimizar o desempenho
segundo alguma métrica definida, como por exemplo: congestionamento, o número de
comprimentos de onda disponíveis ou o custo dos enlaces. Este problema é conhecido
como o problema de roteamento e atribuição de comprimentos de onda (RWA, Routing
and Wavelength Assignment), e será descrito na seção seguinte.
4.1.1 Roteamento e Alocação de Comprimentos de Onda (RWA, Rout-
ing and Wavelength Assignment)
Diretamente ligado ao desempenho da rede óptica transparente está o processo de rotea-
mento juntamente com a alocação de comprimentos de onda. Dado um conjunto de
conexões, o problema de escolher caminhos e alocar um comprimento de onda para
cada chamada é chamado de RWA. Caso não seja possível definir um caminho para uma
chamada, então a mesma é bloqueada. Em um algoritmo de RWA existe a preocupação
em minimizar a quantidade de chamadas bloqueadas dentro da rede, ou seja, minimizar
a probabilidade de bloqueio. Essa probabilidade pode ser estimada pela relação entre o
número de chamadas bloqueadas e a quantidade total de chamadas realizadas.
Existemduas formas típicas de gerar chamadas para teste em uma rede óptica: a forma
estática e a dinâmica (GERSTEL; KUTTEN, 8-12 Jun 1997). Ao utilizar tráfego estático,
todas as conexões são conhecidas previamente e o problema é definir os lightpaths para
essas conexões de forma a otimizar a utilização dos recursos da rede, tais como número
de comprimentos de onda ou quantidade de enlaces ópticos. O problema de RWA para
tráfego estático é conhecido como Estabelecimento de Lightpath Estático (SLE, Static
Lightpath Estabilishment).
Para o uso de tráfego dinâmico, a escolha de um lightpath é feita para cada nova
57
chamada gerada, e após um tempo de uso definido de forma aleatória seguindo uma dis-
tribuição estatística, o caminho utilizado é desalocado. Na literatura esse problema é
mencionado como Estabelecimento de Lightpath Dinâmico (DLE, Dynamic Lightpath
Estabilishment), e o objetivo aqui é definir caminhos e comprimentos de onda com a fim
de minimizar a probabilidade de bloqueio, ou seja, maximizar o número de conexões
aceitas pela rede óptica.
O problema de RWA tem extrema importância dentro de um projeto de redes ópticas
eficiente. Solucionar esse problema de forma otimizada permite que uma maior quanti-
dade de clientes sejam atendidos pelo sistema óptico. Dessa forma, para casos de grande
congestionamento na rede, poucos clientes terão suas conexões interrompidas. Porém,
resolver o problema de roteamento e alocação combinados é algo complexo.
Chlamtac, Ganz e Karmi (CHLAMTAC; GANZ; KARMI, Jul 1992) mostraram que,
devido a sua complexidade computacional, o problema RWA é classificado como sendo
NP-completo, e puderam assim demonstrar a equivalência desse problema ao problema
de coloração de grafos.
Existem outras abordagens que tentam reformular o problema utilizando outros mo-
delos, como em (RAMASWAMI; SIVARAJAN, Oct 1995). Algumas abordagens procu-
ram simplificar o problema dividindo-o em duas partes distintas: o sub-problema de
roteamento e o sub-problema de alocação (BANERJEE; MUKHERJEE, Jun 1996)(KEN-
NINGTON et al., 2003)(ALANYALI; AYANOGLU, Oct 1999).
4.2 Roteamento
Existemdiversasformas de realizar o processo de roteamento. Nessa seção serão descritas
as formas de roteamento mais utilizadas: fixo, fixo-alternativo e adaptativo (CHAN;
YUM, 12-16 Jun 1994)(HARAI; MURATA; MIYAHARA, 7-12 Apr 1997) (LI; SO-
MANI, Oct 1999)(RAMAMURTHY; MUKHERJEE, Jun 2002).
4.2.1 Roteamento fixo
A forma mais simples para definir uma rota é utilizar um caminho fixo para um dado
par origem-destino. Esse tipo de roteamento faz uso de algoritmos que são capazes de
definir sempre a mesma rota para cada par origem-destino diferente. Uma forma comum
58
de implementar este tipo de roteamento é utilizar tabelas de roteamento preenchidas pelo
algoritmode menor custo como Dijkstra (DIJKSTRA, 1959). Assim, é criada uma lista de
rotas pré-determinadas considerando o menor custo entre nós de origem e destino. Uma
rota pré-definida entre os nós0e4émostrada na Figura 4.3. Toda chamada gerada entre
o par (0, 4) terá como retorno essa mesma rota.
0
40
3
1
2
4
10
5
20
15
30
25
35
Figura 4.3: Rota fixa entre os nós 0 e 4 definida através do menor custo.
Embora esse tipo de abordagem seja bastante simples, o desempenho do algoritmo é
geralmente ruim, resultando em uma probabilidade de bloqueio alta.
Outro ponto negativo é o fato de que o roteamento fixo não é capaz de lidar com
problemas como falhas de enlaces ou nós. Na Figura 4.3, se o enlace entre os nós 0 e 1,
ou o entre os nós 1 e 4 falhar, ou um mesmo comprimento de onda não estiver livre nos
dois links, a chamada para o par (0, 4) será bloqueada. Para lidar com esse tipo de falha,
o modelo de roteamento deve considerar rotas alternativas pré-definidas, ou ser capaz de
encontrá-las dinamicamente.
4.2.2 Roteamento fixo-alternativo
Para obter rotas alternativas para cada chamada que venha a acontecer, cada nó na rede
deverá ter uma tabela de roteamento com uma lista de possíveis rotas fixas para cada par
origem-destino. Essa tabela deve colocar cada rota em ordem, dando prioridade à rota
de menor custo. Um conjunto de rotas alternativas entre um par (s, d) é composto por
qualquer rota que não possua enlaces em comum com a rota de menor custo da tabela do
nó origem. Na Figura 4.4 são mostradas duas rotas para um mesmo par (0, 4). A primeira
delas utiliza os enlaces passando pelos nós 0,1e4(menor caminho), já a segunda é uma
rota alternativa que utiliza os enlaces passando pelos nós 0, 2 e 4.
59
0
40
3
1
2
4
10
5
20
15
30
25
35
Rota 1
Rota 2
Figura 4.4: Rotas fixas alternativas entre os nós 0 e 4.
Para cada chamada de um par (s, d), o nó de origem s testa todas as rotas possíveis
na ordem da tabela até achar uma em que um comprimento de onda esteja livre. Caso
não haja nenhuma rota livre na tabela, a chamada é bloqueada. A rota de menor custo
é sempre a primeira na tabela de roteamento. A ordem de prioridade para o resto da
tabela de rotas alternativas é dada, geralmente, pelas rotas que utilizem o menor número
de saltos (melhor descrito na Seção 4.2.4.1), ou seja, o lightpath é acionado na rota com
a menor quantidade de nós intermediários. O uso desse tipo de roteamento diminui sig-
nificativamente a probabilidade de bloqueio, quando comparada ao roteamento fixo. Esse
processo serve como base para definir um certo grau de tolerância a falhas em processos
de roteamento.
4.2.3 Roteamento adaptativo
Esta classe de algoritmos de roteamento se baseia no estado atual da rede. Esse estado é
definido pela quantidade de conexões em uso e parâmetros da camada física, e o rotea-
mento é realizado utilizando os caminhos de menor custo.
Um exemplo de abordagem para esse tipo de roteamento é considerar o custo 1 as-
sociado a cada caminho livre na rede, e aos caminhos em uso associar custo infinito. O
caminho de menor custo entre um nó de origem s e um de destino d é determinado cada
vez que uma chamada é realizada. Na Figura 4.5 uma chamada do nó 0 para o nó 1 é
realizada e a rota escolhida é mostrada.
Partindo do nó 0 há dois links em uso (até o nó 1 e até o nó 3) e apenas um livre (até o
60
0
1
3
1
2
4
1
1
1
1
Figura 4.5: Rotas achada por roteamento adaptativo entre os nós 0 e 1.
nó 2), portanto a conexão livre até o nó 2 foi usada. Saindo do nó 2 a conexão usada foi a
com o nó 4, pois estava livre. Finalmente se chega ao nó 1 através da conexão com o nó
4.
Usando roteamento adaptativo, uma chamada só é bloqueada caso não exista rota al-
guma disponível entre o nó de origem e o de destino. Utilizar esse processo adaptativo de
roteamento tem a vantagem de diminuir consideravelmente a probabilidade de bloqueio,
porém necessita de protocolos de controle mais complexos para atualizar constantemente
as tabelas de roteamento.
4.2.4 Algoritmos de roteamento
4.2.4.1 Menor custo
Nessa abordagem toda a rede é marcada com os custos associados a cada enlace. Dessa
forma cada roteador tem a capacidade de definir qual será o caminho de menor custo para
uma dada chamada. A cada nova chamada a tabela de roteamento gerada pelos roteadores
(analisando os menores custos) é analisada para que a rota seja definida.
A topologia de rede é representada por um grafo G(V, E), onde os vértices V repre-
sentam os nós da rede, e os arcos E representam os enlaces. Cada enlace E está associado
com uma função de custo w
i, j
que determina o custo associado a cada enlace.
Ao final da execução do algoritmo de menor custo, como o Dijkstra (DIJKSTRA,
1959), cada roteador terá uma tabela de roteamento contendo todas as informações neces-
sárias para definir um caminho entre um par origem-destino.
Para redes ópticas WDM, as informações do enlace contém características peculiares
das redes WDM, como número de comprimentos de onda disponíveis e o total de com-
primentos existentes no enlace. Caso o enlace esteja com todos os comprimentos de onda
61
ocupados, esse será marcado para não ser utilizado no próximo roteamento.
Um exemplo com todas essas informações na rede está mostrado na Figura 4.6, onde
as informações são descritas em cada arcos como: (distância física do enlace, compri-
mentos de onda disponíveis, total de comprimentos de onda).
5
4
3
2
1
0
5
(10,4,10) (10,4,10)
(10,4,10)
(20,4,10) (20,4,10)
(20,2,4) (20,2,4)
(20,4,8) (20,4,8)
Figura 4.6: Exemplo de rede contendo diferentes informações que poderão ser utilizadas
nas funções de custo dentro do algoritmo de menor custo.
Diferentes funções de custo podem ser utilizadas para influenciar na escolha da rota.
Para um dado enlace (i, j) ∈ E de um grafo G(V, E), w
ij
denota o custo a ser utilizado,
como a distância física ou o atraso de propagação do enlace; λ
a
ij
denota o número de
comprimentos de onda disponíveis no enlace no momento em que as informações são
coletadas; e λ
T
ij
representa o número total de comprimentos de onda no enlace. Voltando
para a rede da Figura 4.6, teríamos as informações como: (w
ij
, λ
a
ij
, λ
T
ij
) em cada enlace da
rede. Algumas funções de custo bastante utilizadas são:
• Baseada em saltos(Hops): escolhe o lightpath que tiver o menor número de saltos,
ou seja, menor quantidade de enlaces compondo o caminho. Usar uma quantidade
pequena de saltos aumenta as chances de encontrar um comprimento de onda uti-
lizado nos enlaces intermediários, e, portanto, reduz a probabilidade de bloqueio.
• Distância: aqui é a função de custo w
ij
= d
ij
, ∀(i, j) ∈ E, onde d
ij
representa a
distância física do enlace. O uso dessa função resultará em caminhos com a menor
distância (SP, Shortest Path).
62
• Comprimentos de onda disponíveis: nesse caso w
ij
assume:
w
ij
=
⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎩
−log
⎛
⎜
⎜
⎜
⎜
⎝
1 −
1
λ
a
ij
⎞
⎟
⎟
⎟
⎟
⎠
, se λ
ij
> 1, ∀(i, j) ∈ E
1, se λ
ij
= 1, ∀(i, j) ∈ E
(4.1)
onde
1
λ
a
ij
é a medida de resistência do enlace para estabelecer uma chamada. Quanto
maior a quantidade de comprimentos de onda disponíveis, menor será a resistência
oferecida. Portanto, −log
⎛
⎜
⎜
⎜
⎜
⎝
1 −
1
λ
a
ij
⎞
⎟
⎟
⎟
⎟
⎠
retorna uma medida de pré-disposição do en-
lace para atender a uma chamada. Este tipode roteamento é chamado de roteamento
baseado no menor valor de resistência (LRW, Least Resistance Weight).
• Total de comprimentos e comprimentos disponíveis: neste caso w
ij
assume:
w
ij
= −log
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1 −
⎛
⎜
⎜
⎜
⎜
⎜
⎝
1 −
λ
a
ij
λ
T
ij
⎞
⎟
⎟
⎟
⎟
⎟
⎠
λ
a
ij
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
, ∀(i, j) ∈ E (4.2)
onde a probabilidade p de um comprimento de onda vir a ser utilizado é dada por:
p =
⎛
⎜
⎜
⎜
⎜
⎜
⎝
1 −
λ
a
ij
λ
T
ij
⎞
⎟
⎟
⎟
⎟
⎟
⎠
(4.3)
Com isso, a probabilidade de todos os comprimentosde onda virem a ser utilizadosem um
dado instante é p
λ
a
ij
. Então a probabilidade de pelo menos um comprimento de onda estar
disponível nesse mesmo instante é (1 − p
λ
a
ij
). Pela natureza de minimização do algoritmo
de Dijkstra, usa-se −log(1 − p
λ
a
ij
). Essa é uma forma dinâmica de função de custo, visto
que λ
a
ij
pode mudar a cada instante.
4.2.4.2 Figura de ruído
Na tentativa de melhorar o desempenho em cima do algoritmo de menor caminho, ou-
tros modelos de algoritmos foram propostos com o intuito de minimizar a probabilidade
de bloqueio. Martins-Filho et al. em (MARTINS-FILHO et al., 20-23 Sept. 2003),
propuseram um novo algoritmo baseado nas penalidades associadas à camada física, in-
cluindo diversos fatores como: acúmulo de ruído e ganho, saturação dos amplificadores,
e ganhos e perdas relacionados ao próprio lightpath. Esse modelo se baseia na seleção
inicial de rotas com as penalidades mínimas, então realiza o cálculo da BER para checar
a QoS.
O processo realizado pelo algoritmo está descrito no fluxograma da Figura 4.7.
63
Chamadas
Seleciona
comprimento de onda
Seleciona lightpath
Calcula BER
Comprimento de
onda disponível?
Sim
Bloqueia
chamada
Não
BER < limite definido?
Sim
Não
Figura 4.7: Fluxograma do algoritmo baseado em Figura de ruído.
Parauma dada chamada, o algoritmoaloca o primeiro comprimentode onda disponível
entre o par origem-destino, e calcula a melhor rota (menor figura de ruído). A partir do
resultado, estima-se a taxa de erro por bit. O algoritmo só bloqueia a chamada caso não
haja comprimento de onda disponível, ou se a BER calculada estiver abaixo do aceitável,
garantindo assim uma qualidade de serviço previamente definida para a operação da rede.
4.3 Algoritmos de alocação de comprimentos de onda
A alocação pode ser realizada para o caso estático, onde o problema está em alocar um
comprimentode onda para cada lightpathutilizado de modo que dois lightpathsdiferentes
não utilizem o mesmo comprimento de onda (MUKHERJEE, 1997); e dinâmico, onde se
faz uso de diferentes heurísticas de alocação.
4.3.1 O Problema de alocação de comprimentos de Onda
Um comprimento de onda distinto deve ser alocado para cada lightpath, podendo dois ou
mais lightpaths dividirem um mesmo enlace óptico. A quantidade de lightpaths passando
64
por um mesmo enlace óptico caracteriza o congestionamento nesse mesmo enlace.
No caso estático, o problema é o de alocar a menor quantidade de comprimentos de
onda para serem utilizados por uma quantidade de lightpathsque venham a ser habilitados
pelas chamadas.
Para o caso dinâmico, ao invés de minimizar a quantidade de comprimentos de onda,
tenta-se minimizar a probabilidade de bloqueio a partirde um número fixo de comprimen-
tos de onda que podem ser utilizados. Esse tipo de abordagem requer o uso de heurísticas
para minimizar o bloqueio. Essas heurística podem ser aplicadas tanto ao caso estático
quanto ao dinâmico.
4.3.2 Formulação do problema
Dado um par origem-destino, um caminho será escolhido para essa conexão. Comprimen-
tos de onda devemser alocadospara cada lightpath, de forma que qualquer dois lightpaths
que congestionem um mesmo enlace óptico usem comprimentos de onda distintos. Isso
define alocação de comprimento de onda para uma dada conexão requerida.
Uma forma bastante utilizada para resolver esse problema é modelando-o como um
problema de coloração de grafos (MUKHERJEE, 1997)(CHLAMTAC; GANZ; KARMI,
Jul 1992). Esse modelo define que ao alocar comprimentos de onda de uma maneira
que minimize o número de comprimentos usados (cores), mas levando em consideração
a restrição de continuidade de comprimento de onda, reduz o problema de alocação a um
problema de coloração de grafo descrito como:
1. Construir um grafo auxiliar G(V, E), de modo que cada lightpath contido na rede
seja representado por um nó no grafo G. Haverá um arco não direcionado entre
dois nós do grafo G se os lightpaths correspondente passarem por um enlace óptico
comum (ver exemplo da Figura 4.8).
2. Colorir os nós do grafo G de modo que não haja dois nós adjacentes com a mesma
cor, nesse caso, o mesmo comprimento de onda λ.
A Figura 4.8 mostra um exemplo com oito lightpaths numerados de 0 a 7 numa rede
que possui apenas três comprimentos de onda.
Os lightpaths 0, 1 e 3 são concorrentes, logo não podem fazer uso do mesmo compri-
mento de onda, portanto utilizam λ
1
, λ
0
e λ
2
, respectivamente. O mesmo acontece para
65
5
6
7
λ
0
λ
0
λ
0
λ
1
λ
1
λ
2
λ
1
λ
2
4
3
2
1
0
Figura 4.8: Grafo de coloração de comprimentos de onda construído para uma dada rede.
os lightpaths 4, 5 e 6, e também para os pares 1 e 6, e 2 e 4. O lightpath 7 se encontra
isolado, portanto aloca o primeiro comprimento da lista (λ
0
).
Como dito anteriormente (ver Seção 4.1.1), esse problema é classificado como NP-
completo, e há uma grande dificuldade em determinar o número mínimo de cores a serem
utilizadas para colorir o grafo G. Contudo, existem algoritmos seqüenciais eficientes de
coloração de grafo que minimizam o número de cores usadas (MATULA; MARBLE;
ISAACSON, 1972).
4.3.3 Heurísticas de alocação
Existe um grande conjunto de heurísticas propostas para resolver o problema de alocação
de comprimentos de onda (CHLAMTAC; GANZ; KARMI, 23-27 Apr 1989)(BIRMAN;
KERSHENBAUM, 2-6 Apr 1995)(ZHANG; QIAO, 12-15 Oct 1998). Nessa seção serão
descritas algumas dessas heurísticas utilizadas na literatura, entre elas estão: alocação
aleatória, First-Fit, Least-Used e Most-Used.
• Alocação aleatória de comprimento de onda: para cada rota a ser definida, procura-
se em toda a rede os comprimentos de onda disponíveis, formando um conjunto de
comprimentos disponíveis. Com esse conjunto formado, um comprimento de onda
a ser usado dentro desse conjunto é escolhido através de um processo aleatório que
utiliza uma distribuição uniforme.
• First-Fit: nessa abordagem todos os comprimentos de onda disponíveis são nu-
66
merados e organizados em uma lista. Na procura por comprimentos de onda, um
comprimento de onda de baixo número tem prioridade sobre um com número mais
alto. Dessa forma, o primeiro comprimento de onda disponível será escolhido. Essa
abordagem não requer informação global. Em comparação à alocação aleatória, o
custo computacional do First-Fit é menor, pois não há necessidade de varrer todo
o conjunto de comprimentos de onda para cada rota definida. A principal idéia por
trás dessa abordagem está em agrupar todos os comprimentos de onda em uso nos
lugares mais baixos do conjunto de todos os comprimentos de onda. Dessa forma
a busca por comprimentos de onda disponíveis será cada vez mais rápida. Essa
heurística é bastante utilizada devido ao seu bom desempenho em termos de proba-
bilidade de bloqueio, assim como sua baixa complexidade e custo computacional.
• Least-Used: essa abordagem seleciona o comprimento de onda que é menos usado
pela rede, com isso consegue balancear a carga sobre os comprimentos de onda.
Como as rotas que utilizam uma grande quantidade de enlaces usarão um mesmo
comprimento de onda durante muito tempo, essa abordagem acaba por priorizar as
chamadas que farão uso de quantidades menores de enlaces, pois os comprimentos
que serão utilizados por rotas menores passarão menos tempo sendo alocados (usa-
dos). Essa abordagem requer armazenamento de informação adicional, e também
mais custo computacional. Sendo assim, essa heurística não é muito utilizada na
prática.
• Most-Used: essa heurística realiza a operação contrária a Least-Used, ou seja, aloca
o comprimento de onda mais usado na rede. Essa abordagem tem desempenho su-
perior à Least-Used (SUBRAMANIAM; BARRY, 8-12 Jun 1997), mas o custo
computacional e o armazenamento de informação são bastante similares. Essa
heurística também possui melhor desempenho do que a Fisrt-Fit, realizando um
trabalho melhor em agrupar conexões em comprimentos de onda de ordem mais
baixa, conservando a capacidade extra na busca por comprimentos menos utiliza-
dos.
Nessa dissertação serão utilizados apenas modelos com redes de fibra única, onde
se aplicam as heurísticas descritas anteriormente. Porém existem heurísticas propostas
para aplicação em redes multi-fibra, dentre elas estão: Min-Product, que agrupa em fi-
67
bras os comprimentos de onda utilizados, minimizando o número de fibras necessárias na
rede (JEONG; AYANOGLU, 24-28 Mar 1996); Least-Loaded, escolhe o enlace mais car-
regado pertencente à rota definida e usa o primeiro comprimento de onda disponível desse
enlace (KARASAN; AYANOGLU, 18-22 Nov 1996); e MAX-SUM, que considera todos
os possíveis lightpaths na rede, e tenta maximizar a capacidade dos caminhos restantes
após o estabelecimento dos lightpaths, assumindo que a matriz de tráfego é conhecida
previamente e que a rota para cada chamada já está selecionada (BARRY; SUBRAMA-
NIAM, 16-21 Feb 1997)(SUBRAMANIAM; BARRY, 8-12 Jun 1997).
4.4 Roteamento utilizando técnicas de computação inte-
ligente
Os algoritmos de roteamento comumente utilizados não são adaptáveis o suficiente ao
ponto de se adequar a novas condições de rede e achar uma solução que considere uma
grande diversidade de efeitos, tais como ocupação, ruídos e variações na topologia da
rede. Para viabilizar um processo mais eficiente em tempo real, artifícios pertencentes à
computação inteligente podem ser empregados para minimizar o esforço computacional
e melhorar o desempenho em redes de comunicação. Entre as técnicas de computação in-
teligente mais utilizadas estão: Otimização por Colônias de Formigas (ACO, Ant Colony
Optimization) (BONABEAU et al., 1998), (CARO; DORIGO, 1998), (NGO; JIANG;
HORIGUCHI, 16-19 Nov. 2004), (SIM; SUN, 2003), (SCHOONDERWOERD; HOL-
LAND; BRUTEN, 1997), Algoritmos Genéticos (GA, Genetic Algorithms) (BISBAL,
2004), Redes Neurais de Hopfield (HNN, Hopfield Neural Networks) (BISBAL, 2004),
(RAUCH; WINARSKE, Apr 1988), (ZHANG; THOMOPOULOS, 1989), e algoritmos
híbridos realizando combinações de diferentes técnicas (YUAN; ZHAN; YAN, 2003),
(LE et al., 2005).
Existem vários trabalhos que utilizam processos baseados em ACO para achar o
menor caminho numa rede de telecomunicações ou mesmo para atualizar diretamente as
tabelas de roteamento em redes de troca de pacotes (SIM; SUN, 2003), (SCHOONDER-
WOERD; HOLLAND; BRUTEN, 1997). Fazendo uso dessa técnica, é desejável realizar
adaptações com o intuito de adicionar parâmetros que aproximem a técnica do problema
em questão. Detalhes sobre como foi aplicada a técnica de ACO para roteamento em re-
68
des ópticas transparentes serão descritos no capítulo seguinte, assim como os resultados
obtidos.
69
Capítulo 5
Novo Algoritmo de RWA Baseado em
ACO para Redes Ópticas
Em pesquisas recentes, diversos modelos baseados na inteligência coletiva de formigas
foram propostos para solucionar problemas de otimização, como o problema do caixeiro
viajante assimétrico (DORIGO; GAMBARDELLA, 1997), de coloração de grafos (IS-
RAEL A. WAGNER MICHAEL LINDENBAUM, 2000), roteamento de veículos (DO-
RIGO; CARO; GAMBARDELLA,1999) e roteamento em redes de comunicações(CARO;
DORIGO, 1998)(NGO; JIANG; HORIGUCHI, 16-19 Nov. 2004)(SIM; SUN, 2003)
(SCHOONDERWOERD; HOLLAND; BRUTEN, 1997).
Schoondenwoerd(SCHOONDERWOERD; HOLLAND; BRUTEN, 1997)propôs um
algoritmo de roteamento para redes de telefone usando agentes baseados em formigas.
Nesse algoritmo, as tabelas de roteamento são atualizadas a todo instante pelo feromô-
nio depositado pelas formigas. Bonabeau et al. (BONABEAU et al., 1998) melhorou o
desempenho do algoritmo proposto por Schoondenwoerd inserindo o princípio de pro-
gramação dinâmica e Ngo (NGO; JIANG; HORIGUCHI, 16-19 Nov. 2004) utilizou esse
mesmo algoritmo em redes ópticas WDM.
As formas comuns de roteamento em redes ópticas não são capazes de considerar
efeitos da camada física. Tomando como base essa informação, um novo algoritmo de
RWA é proposto com o intuito de utilizar a técnica de ACO para realizar o roteamento.
A apresentação dessa abordagem de ACO será mostrada nesse capítulo, assim como os
resultados referentes à aplicação da mesma em duas redes de teste.
70
5.1 Modelo baseado na distância do enlace
Uma formiga artificial pode ser implementada como um simples programa capaz de ex-
plorar e simular o processo de deposição e percepção de feromônio dentro de uma rede
representada por um grafo (ver capítulo 2). Cada formiga é inicializada no nó origem s
e explora a rede em busca do nó destino d. Basicamente, as formigas são guiadas pela
concentração de feromônio já existente no enlace para achar um caminho ótimo entre o
par (s, d) dentro de um intervalo de tempo de busca discreto T
busca
. Quando uma formiga
encontra o nó destino d, esta retorna ao nó origem s seguindo o mesmo caminho utilizado
na ida, porém na direção contrária, depositando feromônio. Dessa forma, pode-se definir
uma colônia como uma estrutura que possui vários grupos de formigas que irão buscar os
caminhos e memorizá-los.
O algoritmo de ACO que será analisado nessa dissertação, gera periodicamente gru-
pos contendo n formigas com uma freqüência de criação f
c
. As simulações usam uma
quantidade de chamadas N
chamadas
. Para cada chamada diferente, n formigas irão procurar
caminhos e definir a melhor rota para o par (s, d) da chamada usando T
busca
iterações.
Abaixo seguem as definições dos parâmetros usados no algoritmo:
• T
busca
: quantidade de iterações máxima permitida em que as formigas se movi-
mentam na rede com o intuito de definir o melhor caminho para um par (s, d). As
formigas devem ter iterações suficientes para chegar no nó destino, portanto o valor
para T
busca
deve ser no mínimo a quantidade de nós existentes na rede.
• N
chamadas
: número de chamadas na rede de comunicações usadas para realizar uma
simulação completa do algoritmo. Cada chamada é gerada com pares origem-
destino aleatórios dentro da rede.
• T
c
: define o intervalo entre a criação de cada grupo de formigas. A criação segue a
freqüência f
c
= 1/T
c
.
• n: a quantidade de formigas criadas e colocadas na rede a cada intervalo de tempo
T
c
. Essa quantidade varia de acordo com a necessidade do ambiente, ou seja, com
o tamanho da rede utilizada.
• Q: quantidade constante de unidades de feromônio depositadas no caminho pela
formiga durante o retorno ao nó de origem. Geralmente assume valores entre 1 e
71
100 (DORIGO; MANIEZZO; COLORNI, Feb 1996).
Utilizar apenas o conjunto de fatores acima pode levaro algoritmo a uma convergência
pré-matura, ou seja, a um estado de estagnação. Nesse estado, todas as próximas formigas
irão escolher um caminho ótimo achado previamente, erradicando a capacidade de encon-
trar novos e melhores caminhos. A forma mais comum de evitar estagnação é modelar as
formigas de modo que elas não se limitem a decidir baseadas apenas na concentração de
feromônio.
Com esse propósito, a equação que induz cada formiga a escolher um enlace envolve
a concentração de feromônio e uma função de custo (SIM; SUN, 2003). Por exemplo,
uma formiga escolhe utilizar um enlace fazendo uso de uma função composta por um
parâmetro associado ao enlace e o feromônio já depositado no mesmo enlace por formigas
anteriores. Simplificando a regra de decisão dada nocapítulo 2 pela equação 2.10, tem-se:
P
k
ij
= r · [Ph
ij
]
α
· [n
ij
]
β
∀j ∈ N
k
i
(5.1)
onde P
k
ij
mede o quanto a formiga k será induzida a escolher o enlace entre o nó i eonó
j, N
k
i
é o conjunto de nós vistos pela formiga k a partir do nó i, Ph
ij
é a quantidade de
feromônio no enlace (ij), n
ij
é a função custo relacionada ao enlace (ij)er é um número
aleatório entre0e1gerado por uma distribuição uniforme.
A função n
ij
é chamada de visibilidade e pode estar relacionada com características
do enlace como, por exemplo: distância, atraso de propagação e taxa de erro (SIM; SUN,
2003). Considerando a minimização da distância, tem-se:
n
ij
=
1
d
ij
∀j ∈ N
k
i
(5.2)
onde o custo d
ij
será a distância física do enlace. A visibilidade serve como outro indi-
cador que irá induzir a formiga em sua escolha.
Também para evitar estagnação, é usado o processo de evaporação com o intuito de
moderar a influência da experiência passada das formigas (ver capítulo 2). Esse processo
insere um fator chamado de fator de evaporação (), definido como = (1−ρ) que repre-
senta a taxa de feromônio que será evaporado dos enlaces da rede ao final de cada iteração,
sendo ρ a taxa de evaporação variando entre0e1(para mais detalhes ver equação 2.9).
72
5.1.1 Otimização dos parâmetros
Os parâmetros envolvidos na equação 5.1 são de extrema importância para o desempenho
do algoritmo de ACO. Os parâmetros α e β indicam a importância relacionada à con-
centração de feromônio Ph
ij
e à função n
ij
na indução da escolha feita pelas formigas,
respectivamente. Valores corretos de α e β levam a colônia a convergir eficientemente
para caminhos menores dentro de uma rede. Assim como α e β, valores para a taxa de
evaporação também influenciam no desempenho do algoritmo, pois indicarão o quanto
as formigas levarão em conta a experiência prévia de toda a colônia. Na literatura, foram
instituídos intervalos bem definidos para esses valores, sendo eles: α ∈ [0 : 5], β ∈ [0 : 5]
e podendo variar entre0e1(DORIGO; MANIEZZO; COLORNI, Feb 1996).
A técnica de busca PSO foi usada com a finalidade de obter os melhores valores para
os parâmetros α, β e taxa de evaporação da equação 5.1. Cada partícula (solução) define
os valores para esses três parâmetros que representarão sua posição com três dimensões.
Utilizando esses parâmetros, as mesmas executam uma simulação usando o algoritmo
de ACO para realizar o roteamento e comparar o resultado com o algoritmo de menor
caminho de Dijkstra. Essa comparação gera uma taxa de erro que será associada ao fitness
da partícula. Ao final do processo a melhor solução encontrada, ou seja, a que obtiver
menor quantidade de erros em relação ao algoritmo de menor caminho é considerada a
melhor solução.
Para realizar essa busca, o algoritmo de PSO foi implementado utilizando a topologia
baseada em clãs descrita no capítulo 3 seção 3.5. A forma baseada no coeficiente de cons-
trição foi utilizada para calcular as velocidades e ajustar as posições de cada partícula, e
os valores atribuídos às constantes foram: κ = 1, c
1
= 2, 05 e c
2
= 2, 05. Foram utilizadas
30 partículas divididas em 3 clãs utilizando conferência global, onde se conseguiu, com
menos de 100 iterações do PSO, convergência para 0% de erro usando N
chamadas
= 10000
na simulação ACO.
A Figura 5.1 apresenta o fluxograma do processo de otimização. Nota-se que a função
objetivo usada pelas partículas é uma simulação de ACO, como mencionado anterior-
mente.
O fluxograma usado para o cálculo de cada rota no algoritmo de ACO está mostrado
na Figura 5.2, e é descrito da seguinte forma:
1. Inicialmente, um par origem-destino é definido de forma aleatória. A partir do nó
73
Inicializa enxame
Inicializa as posições de
cada partícula
Realiza simulação de ACO
para cada partícula (solução)
Ajusta a posição das
partículas
Define as novas posições
Termino das iterações?
Não
Seleciona e armazena
a melhor partícula
do enxame
Sim
Realiza simulação de ACO
para cada partícula (solução)
Atualiza experiência de
cada partícula
Figura 5.1: Fluxograma do processo de otimização usando PSO para encontrar os parâ-
metros α e β da equação 5.1.
origem, são lançadas as formigas em busca do nó destino. Tomando como base a
equação de indução, cada formiga escolhe seu próximo nó a ser visitado e se move
para o mesmo. Nesse ponto, podem ocorrer duas ações diferentes: formigas podem
já ter encontrado o nó destino ou ainda estar realizando a busca.
2. Caso formigas encontrem o nó destino, a rota utilizada por cada uma delas para
chegar a este nó será armazenada. A partir desse momento, cada uma destas formi-
gas realizará a viagem de volta ao nó origem (return trip), depositando feromônio
na rota utilizada. Após a viagem de volta, cada uma destas formigas (que já encon-
traram um caminho) será morta e não mais fará parte da colônia. Com o intuito de
manter o tamanho da colônia, uma nova formiga é lançada a partir do nó origem
para cada formiga morta, para assim recompor o tamanho da colônia e continuar a
busca por uma rota até o nó destino.
3. Será analisado o tempo de busca após a recomposição da colônia ou se nenhuma
formiga tiver chegado ao nó destino. Se ainda houver tempo para a busca, ocorrerá
74
Define par ( , ) aleatóriosd
Lança formigas de ida em s
Fim do tempo de busca?
Alguma formiga
chegou no destino?
Não
Executa algoritmo
de Dijkstra para ( )s,d
Sim
Seleciona melhor
rota armazenada
Armazena rota achada
por ACO
Escolhe próximo nó e move
cada formiga
Não
Evapora
Deposita feromônio
na rota achada
Mata formiga que
achou a rota
Lança formiga de volta
Compara com a rota
achada por Dijkstra
Rotas de mesmo custo?
Sim
Termina
Erro na escolha da rota
Não
Sim
Inicia
Lança formiga de ida em s
Acerto na escolha da rota
Figura 5.2: Fluxograma da simulação ACO x Dijkstra para uma chamada.
o processo de evaporação na rede. Esse processo diminui, de acordo com a taxa de
evaporação utilizada, a quantidade de feromônio em todos os enlaces. Então, o
processo de busca continuará.
4. Quando finalizado o tempo de busca, será feita a comparação entre cada rota ar-
mazenada, e a melhor entre elas será selecionada. Para comprovar que o algoritmo
de ACO encontrou a menor rota, é realizada a comparação com o resultado do al-
goritmo de menor caminho de Dijkstra para o mesmo par origem-destino. Caso as
rotas tenham o mesmo custo (nesse caso, a mesma distância), é considerado que o
ACO acertou na escolha da rota, caso contrário é considerado como erro.
75
5. Dada uma quantidade de chamadas N
chamadas
, a taxa de erro tx
erro
é dada por:
tx
erro
=
erro
N
chamadas
. (5.3)
No fluxograma mostrado pela Figura 5.1, a partícula que conseguir a menor taxa de
erro será a mais forte dentro do enxame. Fazendo uso dessa relação comofunção objetivo,
valores para α, β e que minimizam essa taxa foram encontrados.
Para a realização das simulações usando o algoritmo de ACO dentro da busca rea-
lizada pelo PSO, foi utilizada a topologia de rede americana NSFNet e uma topologia
regular de 8 nós, mostradas nas Figuras 5.3 e 5.6. A rede NSFNet se caracteriza pela
complexidade gerada pelos nós existentes e pelas conexões formadas entre os mesmos.
Os valores associados a cada arco das redes representam a distância física entre os nós ad-
jacentes medida em quilômetros. Note que os comprimentosdos enlaces foram reduzidos
para que as redes possam ser analisadas como redes metropolitanas.
1
2
3
0
4
5
6
7
8
9
10
11
12
13
26
27
30
42
76
35
22
100
25
24
55
72
22
21
65
35
45
25
48
51
28
Figura 5.3: Estrutura da rede NSFNet dos EUA utilizada nas simulações.
A cada iteração cada partícula realizou uma simulação ACO, usando T
busca
= 4 · N,
onde N é a quantidade de nós da rede usada. Nesse caso, para NSFNet tem-se N = 14 e
T
busca
= 4 · 14 = 56, e para a rede regular de 8 nós T
busca
= 4 · 8 = 32. Esses valores de
T
busca
permitem à colônia realizar buscas satisfatórias em cada rede.
Nas simulações ACO feitas por cada partícula, para cada chamada realizada, a colô-
nia sai em busca de um destino específico. Porém algumas formigas podem se perder
dentro da rede durante a busca e serem mortas. Em outras palavras, as formigas acabam
em pontos sem saída, passando a não ter mais utilidade para a colônia. Dependendo da
quantidade de nós da rede e da complexidade da topologia, o número de formigas que irão
76
se perder pode ser alto. Considerando esse fato, uma colônia composta por 50 formigas
foi utilizada.
Novos grupos de formigas são inseridos na rede de acordo com a freqüência de cri-
ação f
c
. O valor usado nas simulações foi f
c
= 1, o que faz com que novos grupos sejam
inseridos a cada iteração. Dessa forma, a rede estará ocupada por formigas durante toda
a busca. Portanto, a cada iteração de T
busca
,novasn formigas serão inseridas na rede até
completar o tamanho da colônia, que nesse caso é 50. O valor usado é n = 5, portanto a
cada iteração 5 formigas serão inseridas. Quando a colônia estiver completa (50 formi-
gas), à medida que formigas forem sendo mortas por se perderem ou por encontrarem um
caminho, novas formigas serão inseridas para complementar a colônia conservando assim
seu tamanho. Cada formiga realiza a deposição de feromônio com um valor de Q = 1, ou
seja, uma unidade de feromônio por deposição.
As buscas realizadas pelo algoritmo de PSO chegaram a valores para o fator de eva-
poração em torno de 0, 6, α 1, 9eβ 0, 6 para as duas redes utilizadas. Esses valores
previnem estagnação em ambas as redes.
5.1.2 Análise da variação do tempo de busca (T
busca
)
Tomando como base os parâmetros α, β e dos indivíduos mais fortes encontrados pelo
PSO para a rede NSFNet, foi realizada uma análise de desempenho do algoritmo de ACO
com os seguintes parâmetros: α = 1, 96447, β = 0, 59280 e = 0, 64192.
Variou-se o tempo de busca T
busca
baseando-se na quantidade de nós N da rede, para
que dessa forma fosse possível avaliar a quantidade de erros à medida que o tempo de
busca diminui. Para isso foram coletadas as taxas de erro de 30 simulações contendo
100000 chamadas cada, para cada valor específico de T
busca
.
O valor utilizado na busca feita pelo PSO foi T
busca
= 4N, então, para a análise reali-
zada nessa seção, foi-se diminuindo o valor de T
busca
para que pudesse ser definido, para
cada uma das redes, um limite mínimo aceitável de tempo de busca em relação à taxa de
erro.
5.1.2.1 Simulações com a rede NSFNet
A média dos valores relativos às melhores soluções achadas pela busca com o algoritmo
de PSO foi utilizada em simulações envolvendo, inicialmente, a rede NSFNet (ver Fi-
77
gura 5.3), e seus resultados estão apresentados em boxplot nas Figuras 5.4 e 5.5.
Figura 5.4: Variação do erro pelo tempo de busca usando valores 4N;3, 5N;3N e2, 5N
número de iterações usadas pelas formigas na procura de cada rota dentro da rede NSFNet.
As variações no valor adotado por T
busca
são proporcionais à quantidade de nós da
rede (N = 14). Como mostrado na Figura 5.4, usando T
busca
= 4N, foi mantida a taxa
de erro entre 0, 0%e0, 002% com um outlier de valor 0, 004% e média de 0, 00164%.
Usando T
busca
= 3, 5N, obteve-se média de 0, 00288%, com uma variação entre 0, 0% e
0, 006%. Para T
busca
= 3N, os valores variaram entre 0, 008% e 0, 013% com outliers em
0, 004 e 0, 017, proporcionando uma taxa de erro média de aproximadamente 0, 01045%.
As simulações com T
busca
= 2, 5N obtiveram uma taxa de erro média de 0, 02337% e
limites inferior e superior em 0, 015% e 0, 033%, respectivamente.
Na Figura 5.5 estão mostrados os resultados das simulações para T
busca
= 2N, T
busca
=
1, 5N e T
busca
= 1N. As taxas de erro de 50% das amostras para T
busca
= 2N variaram
entre 0, 05% e 0, 09%, com uma média igual a 0, 07133%. Para T
busca
= 1, 5N foi obtida
uma média de 0, 28518%, e as amostras com variações entre 0, 258% e 0, 319%. Com
T
busca
= 1N obteve-se uma média de 1, 24002% dentro de uma variação entre 1, 163% e
1, 299% com um outlier em 1, 119.
A Tabela 5.1 mostra os principais dados relacionados à análise feita utilizando a rede
NSFNet.
Observando a Tabela 5.1 nota-se que o algoritmo de ACO, embora esteja usando pa-
râmetros otimizados para uso com T
busca
= 4N, garante uma taxa de erro mínima para
78
Figura 5.5: Variação do erro pelo tempo de busca usando valores 2N;1, 5N e1N número
de iterações usadas pelas formigas na procura de cada rota dentro da rede NSFNet.
Tabela 5.1: Análise dos resultados referentes aos box plots de cada T
busca
para a rede
NSFNet.
T
busca
Média Mediana Limite inferior Limite superior
4N 0, 00164% 0, 001% 0, 0% 0, 002%
3,5N 0, 00288% 0, 003% 0, 0% 0, 006%
3N 0, 01045% 0, 01% 0, 008% 0, 013%
2,5N 0, 02337% 0, 023% 0, 015% 0, 033%
2N 0, 07133% 0, 07% 0, 05% 0, 09%
1,5N 0, 28518% 0, 281% 0, 258% 0, 319%
1N 1, 24002% 1, 236% 1, 163% 1, 299%
valores de T
busca
≥ 3N. Considerando que uma taxa de erro aceitável deve estar na or-
dem de 10
−2
, o valor T
busca
= 2N obteve resultados razoáveis. A taxa de erro encontrada
utilizando 2N iterações de busca ficou em torno de 0, 07133%.
O mesmo tipo de análise foi feita aplicando os valores achados pelo algoritmo de
PSO a uma rede de menor porte, como mostra a segunda parte do experimento descrito
na seção seguinte.
79
5.1.2.2 Simulações com a rede de teste
A rede utilizada na segunda parte do experimento possui uma complexidade menor do
que a NSFNet. A rede contém 8 nós ao todo, um número bem menor do que o da rede
da primeira parte do experimento. Essa rede possui outro fator importante que diminui
sua complexidade: é formada por conexões simétricas, o que permite a existência de
dois diferentes caminhos para um mesmo par (s, d) com o mesmo custo associado. A
Figura 5.6 mostra a topologia da rede usada na segunda etapa do experimento.
0
1
3
2
4
5
67
70
120
120
120120
60 60
60 60
70
70
70
Figura 5.6: Estrutura da rede de teste de menor porte utilizada na segunda etapa das
simulações com variação de T
busca
.
Para essa rede, os valores de T
busca
≥ 2N conseguiram 0% de erro em todas as 30
simulações realizadas. Portanto, apenas os valores abaixo estão mostrados na análise em
boxplot da Figura 5.7.
Utilizando T
busca
= 1, 5N obteve-se média de taxa de erro de 9, 808988e − 5%, e o
mínimo de variação nos resultados das simulações, ficando todas com praticamente 0, 0%
de erro. Para T
busca
= 1N nota-se uma variação maior, sendo esta entre 0, 032981% e
0, 050961%, com média igual a 0, 041133%. Esses resultados estão listados na Tabela 5.3.
Para essa rede, valores de T
busca
≥ 1, 5N garantem uma taxa de erro mínima, podendo
ser considerado o valor mínimo de T
busca
(T
busca
≥ 1N) satisfatório, visto que ao utilizar
esse valor foi conseguida uma taxa de erro de média 0, 041133%, ou seja, ainda na ordem
de 10
−2
. Isso se dá pela simetria da rede, que aumenta a quantidade de opções de menor
custo, fazendo com que a colônia necessite de menos iterações de busca para convergir.
80
Figura 5.7: Variação do tempo de busca usando valores 2N;1, 5N e1N número de itera-
ções usadas pelas formigas na procura de cada rota dentro da rede de teste.
Tabela 5.2: Análise dos resultados referentes aos box plots de cada T
busca
para a rede de
teste da Figura 5.6.
T
busca
Média Mediana Limite inferior Limite superior
4N 0, 0% 0, 0% 0, 0% 0, 0%
3,5N 0, 0% 0, 0% 0, 0% 0, 0%
3N 0, 0% 0, 0% 0, 0% 0, 0%
2,5N 0, 0% 0, 0% 0, 0% 0, 0%
2N 0, 0% 0, 0% 0, 0% 0, 0%
1,5N 9, 808988e −05% 0, 0% 0, 0% 0, 001%
1N 0, 041133% 0, 04% 0, 033% 0, 051%
Vale salientar que o algoritmo ACO aplicado a essa rede de teste utiliza os valores de
parâmetros encontrados pelo PSO para uma rede bem mais complexa (NSFNet) e para
um T
busca
= 4N. Isso indica que os parâmetros encontrados pelo PSO para redes de
complexidade e estrutura maior, podem ser usados pelo algoritmo ACO em aplicações
com redes de complexidade igual ou inferior, obtendo desempenhos melhores ou iguais.
81
5.2 Modelo adaptado à redes ópticas
5.2.1 Modelo óptico
Para melhor solucionar o problema de roteamento, pode-se realizar algumas adaptações,
e incluir uma quantidade desejada de parâmetros que levam em consideração efeitos da
camada física no plano de controle de roteamento. A melhor alternativa para minimizar o
esforço computacional e melhorar o desempenho destas redes é adaptar a forma original
de aplicação do ACO ao problema proposto inserindo os efeitos necessários (ver Capí-
tulo 4).
Para as redes ópticas, além de definir qual a melhor rota, deve-se definir o compri-
mento de onda a ser utilizado, o que caracteriza o problema de RWA. Porém, para se
obter uma melhor maneira de solucioná-lo, esse problema é subdividido em duas partes:
roteamento e alocação, como explicado no capítulo 4. Em nossa abordagem, o problema
de RWA será considerado separadamente, porém a partir do roteamento realizado pelo
algoritmo de ACO, a heurística de indução facilitará a alocação que virá a ser realizada.
Essa alocação irá utilizar o algoritmo First-Fit também já descrito no capítulo 4.
Considerando a forma da equação (5.1), o uso da visibilidade n
ij
será alterado com
o intuito de englobar um importante fator a ser considerado nos enlaces que formam um
caminho óptico: a quantidade de comprimentos de onda disponíveis. Dessa forma, tem-
se:
Δλ
ij
=
λ
T
ij
− λ
U
ij
λ
T
ij
, (5.4)
onde λ
U
ij
é o número de comprimentos de onda ocupados no enlace (ij)eλ
T
ij
total de
comprimentos de onda existentes no mesmo enlace.
Levando em conta o novo fator Δλ
ij
descrito na equação (5.4), a forma adaptada da
equação de indução (5.1) se torna:
P
k
ij
= r ·
(Ph
ij
)
α
· (Δλ
ij
)
γ
(d
ij
)
β
∀j ∈ N
k
i
, (5.5)
onde agora considera-se Δλ
ij
, que é a quantidade de comprimentos de onda disponíveis
no enlace (i, j), e γ, que é a importância associada a esse fator. Como o objetivo é o de
maximizar a quantidade de comprimentos de onda disponíveis, Δλ
ij
é multiplicado pela
concentração de feromônio Ph
ij
, induzindo assim as formigas a optarem por caminhos
(i, j) com disponibilidade mais alta.
82
5.2.1.1 Efeitos e parâmetros considerados nas simulações
Cada enlace óptico que compõe a rede é formado por dispositivos que geram ruídos e
efeitos. Para a realização das simulações será utilizada a configuração do enlace óptico
usado em (CHAVES, 2008), mostrado na Figura 5.8.
TX RX
a
b
c
d
e
f
g
h
Figura 5.8: Enlace óptico contendo os dispositivos considerados nas simulações.
O enlace mostrado na Figura 5.8 é formado por: transmissor (TX), switch, multi-
plexador, amplificador óptico de potência (booster), fibra óptica, pré-amplificador óptico,
demultiplexador e receptor (RX).
Para manter a qualidade de sinal num sistema de comunicações óticas, deve-se prezar
pela relação sinal-ruído óptica (OSNR, Optical Signal to Noise Ratio), que representa a
razão entre a potência do sinal óptico (P
sinal
) e a potência de ruído óptico (P
ruido
) (RA-
MASWAMI; SIVARAJAN, 2002). Sua definição é dada por:
OSNR = 10log
P
sinal
P
ruido
. (5.6)
Assim, quanto maior essa relação, melhor será a qualidade do sinal entregue pelo canal
de comunicação.
Pode-se medir a a relação sinal-ruído de entrada (OSNR
in
) através das potências do
sinal e ruído na entrada P
in
e N
in
, respectivamente. Para uma dada rota composta de i
enlaces, os dispositivos entre b e h são repetidos i−1 vezes até que o sinal óptico alcance
o receptor no nó destino.
Entre os pontos b e h, considera-se o ruído por crosstalk adicionado na saída do
switch. Esse ruído se dá na transmissão de sinais através de canais WDM quando um
sinal acaba adicionando uma pequena parcela de potência no outro, gerando interferên-
cia (RAMASWAMI; SIVARAJAN, 2002). Nesse caso, o switch adiciona essa parcela de
potência devidoao não isolamento ideal do dispositivo. A potência de ruído produzida por
esse efeito, em cada comprimento de onda λ, é dada por (RAMASWAMI; SIVARAJAN,
2002):
N
Sw
(λ) = ε
M+1
j=1
P
Sw
j
(λ) , (5.7)
83
onde P
Sw
j
é a potência óptica do sinal presente na porta de entrada j utilizando o compri-
mento de onda λ, ε representa o fator de isolação e M + 1 o total de sinais que aparecem
nas portas de entrada do switch utilizando o mesmo comprimento de onda do sinal que se
propaga.
Os pontos c e g, representam a entrada do multiplexador e a saída do demultiplexa-
dor, respectivamente. Considera-se esses dispositivos apenas atenuam os sinais que se
propagam no domínio óptico.
Durante o trajeto do sinal de dados na fibra óptica, há perdas de parte do sinal prove-
nientes da própria fibra. Dependendo da distância percorrida, o sinal pode sofrer uma
quantidade de perdas que o tornem fraco demais e não seja mais recebido daforma correta
pelo receptor. Nesse caso se faz uso de amplificadores ópticos para aumentar a distância
alcançada pelo sinal transmitido pela fibra. O tipo mais comum de amplificador óptico é
o a fibra dopada com Érbio (EDFA, Erbium Dopped Fiber Amplifier) (RAMASWAMI;
SIVARAJAN, 2002)(C.; A.; R., 1999). Apesar de tornar o sinal forte para aumentar
seu alcance, os amplificadores geram diferentes efeitos (RAMASWAMI; SIVARAJAN,
2002). Estes efeitos inserem ruídos que podem ser listados como: Ruído de Emissão
Espontânea Amplificada (ASE, Amplified Spontaneous Emission), saturação de ganho e
saturação de ruído ASE. Nos pontos d e f, são considerados tanto o ruído adicionado pelos
amplificadores ópticos, quanto o efeito de saturação de ganho.
Na saída do enlace (ponto h), tem-se a potência óptica de saída do sinal P
out
calculada
como:
P
out
=
G
Amp
1
e
−αd
G
Amp
2
L
Mx
L
Dx
(L
Sw
)
2
· P
in
, (5.8)
onde G
Amp
1
e G
Amp
2
são os ganhos de cada amplificador, L
Sw
é a perda relativa ao switch
(mesma valor para os dois que compõem o enlace), L
Mx
a do multiplexador e L
Dx
ado
demultiplexador.
Também na saída tem-se o ruído N
out
, e o cálculo é feito como se segue:
N
out
=
G
Amp
1
e
−αd
G
Amp
2
L
Mx
L
Dx
(L
Sw
)
2
· N
in
+
G
Amp
1
e
−αd
G
Amp
2
L
Mx
L
Dx
L
Sw
· ε
M+1
j=1
P
Sw
1, j
(λ) (5.9)
+
G
Amp
1
e
−αd
G
Amp
2
L
Dx
L
Sw
·
hv(λ)B
o
2
F
Amp
1
+
F
Amp
2
e
−αd
G
Amp
1
+ ε
M+1
j=1
P
Sw
2, j
(λ) ,
onde h é a constante de Planck, v(λ) é a freqüência do sinal no comprimento de onda λ e
F
Amp
1
e F
Amp
2
são os fatores de ruído dinâmico de cada amplificador.
84
A potência de saída do sinal depende dos ganhos e perdas presentes na propagação
do sinal através do enlace, assim como N
out
inclui as potências dos ruídos adicionadas
em cada ponto descrito anteriormente (CHAVES, 2008). A relação entre P
out
e N
out
de-
termina a relação sinal-ruído de saída OS NR
out
. Dessa forma, um limiar da OS NR de
saída pode ser estabelecido, garantindo assim a QoS das chamadas estabelecidas na rede
(OSNRQoS).
Os valores dos parâmetros utilizados nas simulações das seções seguintes estão apre-
sentados na Tabela 5.3.
Tabela 5.3: Parâmetros da simulação em redes ópticas.
Parâmetros Valor Descrição
P
in
0dBm Potência do sinal de entrada por canal.
P
sat
19dBm Potência de saturação óptica de saída do amplificador.
F
Amp
5db Fator de ruído dinâmico do amplificador.
OSNR
in
40dB Relação-sinal-ruído óptica de entrada.
OSNR
QoS
23dB Relação-sinal-ruído óptica para o critério de QoS.
W 16 Número de comprimentos de onda num enlace óptico.
α 0, 2db/km Coeficiente de perda da fibra.
L
Mux
3dB Perda no multiplexador.
L
Demux
3dB Perda no demultiplexador.
L
Switch
3dB Perda no switch.
−40dB Fator de isolamento do switch.
5.2.2 Simulações e resultados
Buscas utilizando PSO foram realizadas com o intuito de definir os melhores valores para
α e β, na equação padrão e α, β e γ na equação proposta. Como função objetivo, foi usada
uma simulação considerando o sistema óptico descrito anteriormente com 45 Erlangs
de carga na rede e 16 comprimentos de onda em cada enlace (W = 16). Esses valores de
carga e W podem ser considerados satisfatórios para análise de probabilidade de bloqueio,
pois tornam a rede carregada o suficiente para dificultar significamente a minimização de
bloqueios. Para os experimentos realizados nessa seção utilizou-se a rede de teste com 8
85
nós da Figura 5.6 e a rede NSFNet mostrada na Figura 5.3.
Cada busca utilizando PSO requer um longo tempo de execução por conta da quan-
tidade de chamadas da função objetivo. Como a função objetivo é o resultado de uma
simulação ACO integrada ao simulador de redes ópticas descrito e utilizado por Chaves
em (CHAVES, 2008), o número de chamadas utilizadas na simulação influencia no au-
mento do tempo de execução. Dessa forma, cada simulação utilizou 5000 chamadas para
calcular e retornar a probabilidade de bloqueio encontrada, para ser atribuída ao fitness de
cada partícula.
Na execução do PSO, a partículaque obtivera menor probabilidade de bloqueio estará
localizada na melhor posição do espaço de busca e, portanto, representará os melhores
valores para cada parâmetro (α e β para a abordagem padrão e α, β e γ para a proposta).
Valores relativos aos outros parâmetros do ACO foram determinados tomando como base
as informações dadas anteriormente. A taxa de evaporação utilizada foi = 0, 67 e
o tempo de busca T
busca
= 2N. O valor adotado para o tempo de busca foi escolhido
baseando-se nos resultados oriundos da análise do tempo de busca (ver seção 5.1.2) e
devido à necessidade de minimizar o tempo de execução do PSO.
Também visando diminuir o tempo de execução do algoritmo de busca, foi utilizado o
limite de 500 iterações do algoritmo de PSO, e para a comunicação das partículas no PSO
foram utilizadas as estruturas global (estrela) e local (anel) com enxames de 20 partículas.
Foi utilizada a forma do PSO que faz uso do fator de constrição e os valores atribuídos às
constantes foram: κ = 1, c
1
= 2, 05 e c
2
= 2, 05.
Utilizando os valores ótimos definidos, foram realizadas simulações em cada uma
das redes variando a carga de 20 a 60 Erlangs com passo de 5 Erlangs. O algoritmo
de ACO para roteamento foi comparado com o de menor caminho de Dijkstra (SP), o de
menor número de saltos e o de menor resistência (maior número de comprimentosde onda
disponíveis) (LRW). Os detalhes desses experimentos e seus resultados serão mostrados
nas seções seguintes.
5.2.2.1 Roteamento utilizando ACO padrão
Inicialmente, foi feito o uso do PSO com estrutura global na busca pelos valores mais
eficientes de α e β. A Figura 5.9 mostra um gráfico Iterações versus Probabilidade de
bloqueio que caracteriza a curva de convergência do algoritmo aplicado à rede de teste da
86
Figura 5.6.
Figura 5.9: Curva de convergência do PSO com estrutura global aplicado à rede de teste
utilizando o ACO padrão.
Nas primeiras iterações, o PSO convergiu rapidamente para uma probabilidade de
bloqueio de 0, 036 e ficou estacionado nesse valor durante aproximadamente 100 itera-
ções. Saindo dessa região, o enxame chegou a uma melhor solução com probabilidade de
bloqueio de 0, 0348; não obtendo melhorias até o fim das iterações.
Também aplicada à rede de teste da Figura 5.6, foi realizada a busca pelos mesmo pa-
râmetros α e β utilizando também a forma de comunicação local. A curva de convergência
do algoritmo está mostrada na Figura 5.10.
Utilizando comunicação local, obteve-se uma convergência com passos menores em
relação à do PSO global, mostrada na Figura 5.9. Nas primeiras 100 iterações, o algo-
ritmo convergiu para valores de probabilidade de bloqueio de 0, 04113; 0, 0392; 0, 03887;
até chegar em 0, 03387; sendo esse valor mantido como o melhor do enxame durante
pouco mais de 200 iterações. Entre 200 e 350 iterações, a melhor solução do enxame va-
riou de 0, 03287 a 0, 03253; para finalmente chegar a 0, 03093; que foi a melhor solução
encontrada ao final de 500 iterações.
Comparando as curvas de convergência das Figuras 5.9 e 5.10, fica claro que a busca
utilizando comunicação local obteve uma melhor solução. Portanto, foi utilizada me-
lhor solução dessa abordagem para realizar a comparação de desempenho no roteamento
aplicado à rede de teste.
87
Figura 5.10: Curva de convergência do PSO com estrutura local aplicado à rede de teste
utilizando o ACO padrão.
A melhor solução utilizada foi α = 0, 897725 e β = 3, 39438. O tempo de busca
do ACO utilizado na simulação foi T
busca
= 4N. Os gráficos mostrados na Figura 5.11
apresentam as probabilidadesde bloqueio que cada umdos algoritmos obtiveramvariando
a carga na rede.
Figura 5.11: Comparação entre os valores de probabilidade de bloqueio conseguidaspelos
algoritmos de roteamento com a variação de carga utilizando o ACO padrão aplicado à
rede de teste.
A partir de 25 Erlangs de carga até o final da simulação nota-se que o ACO chegou
a valores de probabilidade de bloqueio menores do que a abordagem baseada em menor
88
caminho (SP). Entre 30 e 45 Erlangs, o ACO obteve valores de probabilidade de bloqueio
praticamente idênticos ao algoritmo baseado em saltos e também ao de menor resistência
do enlace (LRW). Já a partir de 50 Erlangs o desempenho do ACO ficou abaixo do LRW
e do algoritmo baseado em saltos.
O roteamentopor ACOpadrão pode ser comparado diretamente aoroteamento baseado
no menor caminho, pois utiliza o mesmo custo como base (distância). Porém, o ACO
obteve desempenho superior ao SP. Isso se dá pela diversidade de escolha que existe no
processo de seleção da rota realizado pelo ACO. Na rede aqui utilizada (ver Figura 5.6),
existem rotas de mesma distância que utilizam enlaces distintos para conectar um mesmo
par origem-destino. Tomando como exemplo o par (3, 1) dessa rede de teste, nota-se
facilmente duas rotas com a mesma quantidade de enlaces e também mesma distância
associada: a rota passando pelos nós {3, 0, 1} e a rota que passa por {3, 2, 1}. Devido
a esse fato, o ACO acaba por diversificar sua escolha entre essas rotas diferentes, vari-
ando assim as rotas utilizadas para um mesmo par origem-destino. Dessa forma, o ACO
aumenta o número de comprimentos de onda livres, pois não sobrecarrega os comprimen-
tos de uma mesma rota, balanceia o uso destes em diferentes rotas para um mesmo par
origem-destino. Como a probabilidade de bloqueio também está associada à escolha do
comprimento de onda livre, o ACO conseguiu obter probabilidades de bloqueio menores
em relação ao SP para os valores de carga acima de 25 Erlangs.
É notado na Figura 5.11 que para o menor valor de carga (20 Erlangs) o ACO obteve
um valor de probabilidade de bloqueio maior do que o algoritmo de menor caminho (SP).
Quanto menor a carga na rede, mais rotas sub-ótimas irão existir, aumentando portanto
a probabilidade de serem escolhidas pela colônia. Isso indica que a mesma diversidade
que leva a colônia a evitar caminhos sub-ótimos, pode também levá-la a escolher essas
mesmas soluções. Para valores de carga mais altos (55 e 60 Erlangs) todos os algoritmos
testados chegam a valores mais próximos de probabilidade de bloqueio, pois o número de
soluções viáveis passa a ser bastante limitado, o que os leva a selecionar a mesma solução.
Para a rede NSFNet, o PSO utilizando comunicação local obteve uma melhor con-
vergência, como pode ser notado comparando-se as curvas de convergência mostradas
nas Figuras 5.12 e 5.13.
Como mostra a Figura 5.12, com pouco mais de 250 iterações o PSO já havia con-
vergidopara amelhor solução encontrada que obteveumaprobabilidadedebloqueioigual
89
Figura 5.12: Curva de convergência do PSO com estrutura global aplicado à rede NSFNet
utilizando o ACO padrão.
a0, 03253.
Figura 5.13: Curva de convergência do PSO com estrutura local aplicado à rede NSFNet
utilizando o ACO padrão.
Utilizandocomunicação local, o PSO convergiumaislentamente para a melhor solução
(ver Figura 5.13), porém obteve uma probabilidade de bloqueio de 0, 03153.
Foi utilizada a melhor solução encontrada pelo PSO com comunicação local, que
possui α = 1, 85072 e β = 3, 13164, para a comparação de desempenho dos algoritmos
de roteamento aplicado à rede NSFNet.
90
Figura 5.14: Comparação entre os valores de probabilidade de bloqueio conseguidaspelos
algoritmos de roteamento com a variação de carga utilizando o ACO padrão aplicado à
rede NSFNet.
Para a simulação de roteamento na rede NSFNet, o ACO obteve o mesmo desempenho
do SP, desempenho esse muito abaixo do conseguido pelos algoritmos baseado em saltos
e LRW. Devido a complexidade e assimetria da rede NSFNet, existe apenas uma rota de
menor caminho que liga um par origem-destino. Dessa forma, o ACO não pôde fazer uso
da diversidade natural criada pela colônia na escolha da rota a ser seguida, passando a es-
colher sempre o mesmo caminho para um dado par origem-destino. O algoritmo baseado
em saltos obteve um bom desempenho, pois utiliza o menor número de enlaces para ligar
um par origem-destino. Esse fato aumenta a probabilidade de obter um mesmo compri-
mento de onda livre nos enlaces escolhidos, e por conseqüência minimiza a probabilidade
de bloqueio. Já o LRW define a rota a ser seguida baseando-se diretamente na quantidade
de comprimentos de onda disponíveis, o que por si só já minimiza muito a probabilidade
de bloqueio.
5.2.2.2 Roteamento utilizando ACO proposto
Utilizando a estrutura global, foi realizada uma busca usando PSO para encontrar os mel-
hores valores de α, β e γ aplicados à rede de teste da Figura 5.6. A curva de convergência
contendo os valores das probabilidades de bloqueio conseguidas durante as iterações do
algoritmo de busca está apresentada na Figura 5.15.
91
Figura 5.15: Curva de convergência do PSO com estrutura global aplicado à rede de teste
utilizando o ACO proposto.
No início de sua execução, o algoritmo variou a probabilidade de bloqueio entre
0, 01927 a 0, 01727. Com 200 iterações, o algoritmo chegou a 0, 0164; e logo depois
atingiu 0, 0156; que foi o menor valor de probabilidade de bloqueio encontrado ao final
de 500 iterações.
Ao utilizar a comunicação local, obteve-se a curva de convergência mostrada na Fi-
gura 5.16.
Figura 5.16: Curva de convergência do PSO com estrutura local aplicado à rede de teste
utilizando o ACO proposto.
92
A estrutura local do PSO obteve uma convergência similar à obtida pela mesma estru-
tura no experimento com o ACO padrão aplicado à rede de teste (ver Figura 5.10). Sua
curva de convergência é constituída de uma variação mais contínua de probabilidade de
bloqueio. Nas primeiras 200 iterações chegou a 0, 01733 com passos menores em relação
à convergência da estrutura global. Da mesma forma decaiu até 0, 01573 onde ficou até o
fim da execução do algoritmo.
A busca que obteve a melhor solução foi o PSO que utilizou a comunicação global,
como pode-se notar na curva de convergência da Figura 5.15. É importante frisar que os
menores valores de probabilidade de bloqueio encontrados pelo PSO aplicado ao ACO
proposto (0, 0156 e 0, 01573) são praticamente a metade da menor probabilidade de blo-
queio conseguida pelo PSO otimizando o ACO padrão (0, 0348 e 0, 03093), o que in-
dica uma vantagem satisfatória no uso do ACO proposto. Portanto, os valores da melhor
solução achada foram utilizados na comparação entre os algoritmos de roteamento.
A melhor solução encontrada foi α = 3, 65563; β = 1, 05867e γ = 2, 66109. Aplicado
à rede de teste, a probabilidade de bloqueioconseguida peloACOproposto com a variação
de carga, juntamente com os outros algoritmos de roteamento usados nas comparações
aqui realizadas, está apresentada na Figura 5.17.
Figura 5.17: Comparação entre os valores de probabilidade de bloqueio conseguidaspelos
algoritmos de roteamento com a variação de carga utilizando o ACO proposto aplicado à
rede de teste.
Os resultados apresentados na Figura 5.17 mostram que de 20 a 35 Erlangs o ACO
93
proposto obteve um melhor desempenho em relação a todosos outros algoritmosde rotea-
mento usados na comparação. A partir de 45 Erlangs, o ACO proposto atingiu valores de
probabilidade de bloqueio equivalentes ao algoritmo baseado em saltos e ao LRW, valo-
res esses na ordem de 10
−2
mesmo para cargas acima de 45 Erlangs. Essa melhora em
relação ao ACO padrão (ver Figura 5.11) se dá pelo fato de o ACO proposto considerar
como custo não só a distância dos enlaces, mas também a quantidade de comprimentos
de onda livres em cada um deles.
Para a busca pelos melhores valores de α, β e γ na rede NSFNet, também foram
utilizadas as estruturas global e local do PSO. As Figuras 5.18 e 5.19 apresentam as
curvas de convergência da execução de cada PSO.
Figura 5.18: Curva de convergência do PSO com estrutura global aplicado à rede NSFNet
utilizando o ACO proposto.
Houve uma variação de probabilidade de bloqueio pequena nas primeiras 225 itera-
ções, onde se obteve valores entre 0, 02867 e 0, 02727. Porém, de 225 até o final da
execução do algoritmo, houveram quedas bruscas chegando a 0, 0248 e 0, 02193, que foi
o menor valor encontrado.
A convergência do PSO utilizando comunicação local (Figura 5.19) diminuiu grada-
tivamente o valor de probabilidade de bloqueio nas primeiras 200 iterações, convergindo
para 0, 021. Note que esse valor já é menor do que o melhor encontrado pela execução do
PSO com estrutura global. O algoritmo passou cerca de 150 iterações considerando essa
a melhor solução, até que convergiu para um valor menor de 0, 01967.
94
Figura 5.19: Curva de convergência do PSO com estrutura local aplicado à rede NSFNet
utilizando o ACO proposto.
Dentre as duas execuções do PSO (global e local), a abordagem local obteve valores
menores de probabilidade de bloqueio. Portanto, a melhor solução encontrada por essa
execução foi utilizada na comparação variando a carga na rede envolvendo os algoritmos
de roteamento.
Os valores dos parâmetros obtidos pela melhor solução foram α = 3, 04819; β =
0, 798236 e γ = 4, 28508, também utilizando = 0, 660827. A simulação utilizou
T
busca
= 4N e a comparação com os outros algoritmos de roteamento está mostrada na
Figura 5.20.
A Figura 5.20 mostra claramente que os algoritmos SP e ACO obtiveram comporta-
mento similar, porém o ACO proposto, por levar em consideração a quantidade de com-
primentos de onda livres, obteveum ganho de desempenho se comparado ao ACO padrão.
Pode-se dizer que a equivalência entre ACO e SP se deu por conta da singularidade das
rotas existentes na rede NSFNet, assim como para o ACO padrão (ver Figura 5.14). Para
um dado par origem-destino, existe sempre apenas uma rota que possui a menor distân-
cia, o que induziu o algoritmo de ACO a escolher a rota de menor caminho, mesmo esse
levando também em consideração a quantidade de comprimentos de onda livres. O bom
desempenho relativo ao algoritmo baseado em saltos e ao LRW pode ser explicado da
mesma forma descrita anteriormente, quando foi aplicado o ACO padrão à rede NSFNet.
95
Figura 5.20: Comparação entre os valores de probabilidade de bloqueio conseguidaspelos
algoritmos de roteamento com a variação de carga utilizando o ACO proposto aplicado à
rede NSFNet.
96
Capítulo 6
Conclusões e trabalhos futuros
6.1 Conclusões
A proposta do trabalho realizado nessa dissertação explora um importante fator rela-
cionado aos sistemas ópticos: algoritmos de roteamento e alocação de comprimento de
onda (RWA, Routing and Wavelength Assignment). Algoritmos de RWA exploram o es-
tado atual da rede para definir o melhor lightpath. Esse processo pode ser altamente
complexo quando se considera efeitos ópticos oriundos da camada física.
Considerar efeitos da camada física em redes ópticas nos leva a criar um ambiente
complexo composto por uma grande quantidade de variáveis a serem consideradas, tor-
nando os algoritmos de roteamento simples absolutamente obsoletos. Nessas circunstân-
cias, o algoritmo proposto nessa dissertação foi modelado para ser capaz de incorporar
diversos parâmetros e definir um lightpath baseado nos custos associados a estes parâme-
tros.
O trabalho proposto sugere que problemas complexos envolvendo diversos parâme-
tros a serem considerados podem ser solucionados utilizando técnicas de Computação
Inteligente (CI, Computational Intelligence). O estudo e aprimoramento dessas técnicas
demonstram que o maior desafio não está no problema e sim na arte de usar tais técni-
cas. Está na capacidade de visualizar o que cada técnica tem de melhor a oferecer para
contribuir na solução do problema.
Para o processo de roteamento,inicialmente foi implementada a técnica de otimização
por colônias de formigas (ACO, Ant Colony Optimization) utilizando sua forma básica,
limitando-se a considerar apenas um custo associado a cada enlace na rede. Cada formiga
97
da colônia escolhe o próximo nó a ser visitado através de uma heurística que considera
como custo a distância associada aos possíveis enlaces a serem escolhidos e a concen-
tração de feromônio já existente no enlace. Diversos fatores como taxa de evaporação,
unidades de feromônio a serem depositadas e tamanho da colônia influenciam no desem-
penho do algoritmode ACO. Além desses parâmetros já citados, cada um dos dois custos,
feromônio e distância, estão associados à valores α e β, respectivamente, que medem a
influência de cada custo na decisão das formigas. Os valores de α e β são constantes e
definidos previamente.
A necessidade de definir valores para esses parâmetros que otimizem o desempenho
do ACO acabou por gerar um novo problema de otimização. Com esse problema em
mãos, uma outra técnica de computação inteligente foi utilizada para buscar e definir os
valores ótimos para α, β e os outros parâmetros envolvidos: a técnica de otimização por
enxames de partículas (PSO, Particle Swarm Optmization). O PSO encontrou valores
satisfatórios para cada um dos parâmetros envolvidos, elevando assim o desempenho do
ACO.
O PSO aplicado à busca pelos melhores valores de cada parâmetro do ACO chegava
a soluções de alta qualidade, no entanto o algoritmo necessitava de uma grande quanti-
dade de iterações para convergir a uma solução ótima. Estudos sobre a técnica de PSO
demonstraram que utilizar topologias mais bem elaboradas, como a baseada em clusters,
levam as partículas a convergir mais rapidamente para uma solução ótima. Com isso, foi
desenvolvida uma nova topologia baseada em clãs de partículas, que acelera significati-
vamente a convergência do enxame de partículas em relação às topologias já existentes.
A topologia de clãs explora o modo como as partículas se comunicam durante a busca,
dando a opção de troca de informação global ou local entre os clãs. A divisão do enxame
em clãs envolve interessantes processos que permitem mesclar a busca em amplitude da
comunicação local com a busca em profundidade da comunicação global. Dessa forma,
a topologia baseada em clãs é capaz de se adequar a diferentes tipos de problemas de
otimização. Assim, utilizando a topologia baseada em clãs, pode-se obter soluções de
alta qualidade e ao mesmo tempo diminuir o tempo de busca do algoritmo de PSO.
Ao utilizar os parâmetros otimizados no ACO padrão, foi possível determinar a rota
de menor distância entre um dado par origem-destino com 100% de acerto. Com isso,
ficou evidente que a técnica de ACO era apropriada para ser aplicada ao problema de
98
roteamento em análise, porém há a necessidade de determinar quais os melhores valores
para cada parâmetro usado pelo ACO.
A partir do momento em que se definiu o que a técnica de ACO tinha a oferecer
para o problema em questão, tornou-se possível a busca por uma solução considerando
as variáveis que compõem o problema principal desse trabalho, bem como a importância
relacionada a cada uma delas.
Ao utilizar técnicas de computação inteligente, é possível tornar um sistema estático e
não adaptativo em um de mesmo cunho, porém dinâmico e adaptativo. Fatores que teriam
que ser observados previamente podem ser alterados a qualquer momento, provando as-
simque o sistemase adapta. Aplicar um algoritmo de otimização por colônias de formigas
em problemas de roteamento envolvendo redes ópticas demonstra ser bastante interes-
sante e valioso.
Devido à complexidade associada ao problema de RWA, o uso de algoritmos de busca
como o PSO é imprescindível para encontrar os melhores valores dos parâmetros a serem
utilizados. Assim, para cada nova abordagem (novos efeitos a serem considerados) uma
nova busca por valores de parâmetros otimizados deve ser realizada. Assim, o algoritmo
seria capaz de, havendomudanças na rede, ouseja, tendonovosefeitossendoadicionados,
se adaptar e resolver com a mesma eficiência.
Ao aplicar ACO no problema de RWA, foram obtidos resultados relevantes em relação
aos algoritmos comumente utilizados, como o de menor caminho (SP), menor número de
saltos e baseado na quantidade de comprimentos de onda livres nos enlaces (LRW). Na
aplicação da forma padrão do ACO à rede de teste com 8 nós, considerando apenas a
distância como custo, foram conseguidos resultados melhores que o SP e equivalentes
aos outros dois algoritmos de roteamento usados na comparação (baseado em saltos e
LRW). Mesmo aumentando a carga nas redes de teste utilizadas, conseguiu-se valores de
probabilidade de bloqueio bastante favoráveis ao ACO devido à diversidade de escolha
inerente a esse algoritmo bio-inspirado. Para a rede NSFNet, o ACO padrão obteve um
desempenho praticamente igual ao SP eao mesmotempo inferior em relação ao algoritmo
baseado em saltos e ao LRW. O comportamento praticamente idêntico do ACO e do SP
era esperado devido ao fato de os dois algoritmos considerarem como custo apenas a
distância dos enlaces.
O ACO demonstrou que pode ser utilizadocom mais de um custo associado à equação
99
de indução das formigas, ou seja, na escolha realizada pelos agentes que determinam a
rota podem ser levados em consideração mais de um custo. Isso foi demonstrado nos
experimentos envolvendo a heurística de indução proposta nessa dissertação, onde se adi-
cionoua quantidade de comprimentos livresà equação de indução. A abordagem proposta
obteve resultados melhores em relação ao ACO padrão, diminuindo ainda mais a proba-
bilidade de bloqueio encontrada quando se variou a carga na rede de teste com 8 nós,
obtendo um desempenho melhor do que os outros algoritmos utilizados na comparação.
Para a rede NSFNet, os resultados obtidos pelo ACO proposto foram similares aos do SP,
pois a rede em questão possui apenas uma rota de menor caminho para cada par origem-
destino. Esse fato faz com que a diversidade do ACO em relação à escolha do menor
caminho passe a não ter influência, levando o algoritmo a selecionar sempre a mesma
e única rota de menor caminho para um dado par origem-destino. Aplicado à essa rede
(NSFNet), o ACO propostoobtevedesempenho superior em relação ao ACO padrão. Esse
fato se deu por conta do novocusto associado à equação deindução: a quantidade de com-
primentos de onda livres em cada enlace. Esse novo custo levou a colônia de formigas
a decidir baseando-se não apenas na distância do enlace, mas também na quantidade de
comprimentos de onda livres do mesmo.
O fato de o ACO sercapaz de incorporar e considerar diversoscustos ao mesmo tempo
para realização do roteamento torna essa técnica bastante válida no processo de RWA.
Essa capacidade permite utilizar efeitos da camada física das redes ópticas na escolha da
rota, proporcionando assim escolhas de rotas ainda mais específicas.
Dessa forma, pode-se concluir que o trabalho proposto resulta em uma importante
contribuição dentro da área de roteamento em redes ópticas transparentes e em com-
putação inteligente, através de uma interessante variação no algoritmo de PSO que pode
ser estendido para diversas propostas de trabalhos futuros.
6.2 Trabalhos Futuros
Se analisados, algoritmos de inteligência de enxames (SI, Swarm Intelligence) demon-
stram possuir uma alta simplicidade em suas estruturas, porém o modo como é feita a
comunicação dentro do ambiente é o termômetro do desempenho do algoritmo. Cada in-
divíduo deve se comunicar com os outros, ou ao menos com uma parte específica deles.
100
Sendo assim, a cada iteração do algoritmo todos os indivíduos devem realizar um tipo de
comunicação com outros, ou até mesmo com todo o grupo.
No algoritmo de ACO proposto, um estudo para otimizar essa comunicação pode ser
realizado, diminuindo assim o tempo que as formigas necessitam para convergir para
uma solução (lightpath) satisfatória. Dentro desse estudo, um melhoria de desempenho
do ACO proposto surgiria inserindo o conceito de tabelas de roteamento à estrutura do
algoritmo. Com isso, as formigas não teriam a necessidade de buscar sempre uma melhor
rota, seriam apenas agentes que atualizariam as tabelas de roteamento da rede.
O algoritmo de ACO proposto demonstra ser capaz de incorporar diversos outros fa-
tores que influenciam no RWA, portanto deve-se incorporar novos parâmetros que con-
tribuam na decisão das formigas pela escolha pelo melhor lightpath. Dessa forma, novos
experimentos envolvendo outros efeitos da camada física devem ser realizados, para que,
através de seus resultados, possam surgir melhorias na qualidade dos lightpaths encontra-
dos pelo algoritmo, diminuindo assim a probabilidade de bloqueio.
Outro ponto importante é a análise do modo como a colônia gera diversidade de esco-
lha entre caminhos achados durante a busca. Um maior estudo da geração dessa diversi-
dade pode vir a contribuir significativamente no desempenho do ACO.
Inserir novos efeitos acaba por aumentar o número de dimensões no problema de
otimização dos parâmetros e, portanto, aumentando também o espaço de busca. Para isto,
pode-se encontrar os valores otimizados para cada novo parâmetro inserido na equação
de indução utilizando a técnica de PSO proposta nesse trabalho (baseada em clãs). Dessa
forma, mesmo com um espaço de busca aumentado, os valores otimizados seriam encon-
trados de forma mais rápida, acelerando assim os experimentos envolvendo essas novas
abordagens.
Outras configurações de simulação envolvendo o problema de RWA podem ser reali-
zadas com o intuito de analisar e estender a aplicação do algoritmo de ACO.
101
APÊNDICE A
PSS - PSO Simulation Shell
O uso da técnica de PSO tornou-se fator de extrema importância e, portanto, de uso
contínuo durante o trabalho realizado nessa dissertação. Inicialmente a forma básica do
PSO era o bastante para a realização de buscas e simulações. Porém, com o estudo mais
abrangente da técnica, veio a necessidade de comparar e testar suas diferentes variações.
Com isso, surge a necessidade de implementar um software de simulação mais completo,
que contenha as formas básicas do PSO e suas variações. Além de ser capaz de realizar
simulações envolvendo diferentes modelos de atualização de velocidade das partículas,
esse software deve também realizar experimentos usando as diferentes topologias já exis-
tentes. No núcleo da ferramenta já estão implementados os modelos de atualização de
velocidade e tolopogias padrão, porém a ferramenta deve ser capaz de incorporar novos
esquemas de atualização de velocidade e também novas topologias. Assim, surge a idéia
do PSS - PSO Simulation Shell que aparece como uma ferramenta acadêmica para a uti-
lização de PSO em problemas de otimização.
A.1 A ferramenta
A Figura A.1 mostra um diagrama contendo as funcionalidades incorporadas por padrão
no núcleo do PSS.
Já implementados no PSS estão os os algoritmos de PSO mais comuns: com fator de
inércia, utilizando coeficiente de constrição e a forma básica. Há também a possibilidade
de utilizar uma abordagem que faz uso de um fator de dispersão em cada partícula pro-
posta em 2008 por Xingjuan Cai (CAI et al., 2008) que é válida apenas para o modelo
102
Algorithms
Basic
Inertia
Constricted
Dispersion
Yes
No
Topologies
Global (estrela)
Local (anel)
Cluster
Clan
Conferência global
Conferência local
Conferência
Functions
Ackley
Goldstein Price
Griewank
Rastrigin
Rosenbrock
Schwefel 1.2
Schwefel 2.6
Six-hump camel back
Sphere
Figura A.1: Esquema das opções já existentes no simulador PSS.
baseado no fator de inércia.
O conjuntode topologiasé formado pelas quatro estruturas que usamos em simulações
durante essa dissertação: global (estrela), local (anel), baseada em clusters e baseada em
clãs. A topologia baseada em clãs possui ainda dois tipos de conferência: global e local,
que definem a topologia por completo.
Funções de teste com diferentes comportamentos foram incorporadas ao PSS para a
realização de testes de convergência, entre elas estão: Ackley, Goldstein Price, Griewank,
Rastrigin, Rosenbrock, Scwefel 1.2, Scwefel 2.6, Six-hump camel back e esfera (Sphere).
Além das funcionalidades básicas mostradas na Figura A.1, o PSS está apto a ser
estendido, podendo incorporar implementações de qualquer variação de PSO, incluindo
variações do esquema de atualização de velocidade, novas topologias e diferentes funções
objetivo.
A tela principal do PSS possui cinco divisões bem definidas. Para o melhor entendi-
mento do funcionamento do PSS, cada divisão foi numerada como mostra a Figura A.2,
e serão descritas em seguida de acordo com suas funções no simulador.
A parte 1 da tela principal do PSS (ver Figura A.2) contém os campos que definem o
algoritmo de PSO que será utilizado. Inicialmente o algoritmoé escolhido entre as formas
mais difundidas: forma básica, utilizando fator de inércia e com coeficiente de constrição.
Caso seja escolhida a abordagem que utiliza fator de inércia (Inertia), deve-seescolher
103
1
2
3
4
5
Figura A.2: Tela principal do PSS.
também qual será o intervalo de variação desse fator. O número de iterações que será
utilizado no processo de busca também está definido no campo Time steps.
Na parte numerada com 2 na Figura A.2, aparecem os campos ligados à escolha da
topologia a ser utilizada e dos parâmetros associados a construção da mesma. É aqui
que se define a quantidade de partículas que a topologia irá utilizar. Caso seja esco-
lhida uma topologia baseada em clusters ou clãs, deve-se definir também a quantidade de
clãs/clusters a serem usados. Para o caso da topologia com clãs há também a escolha do
tipo de conferência a ser utilizada, podendo ser global ou local. Há também a opção de
inserir o modelo de PSO com dispersão à topologia, tendo portanto que definir a variação
de dispersão (C
up
e C
low
).
A parte 3 da Figura A.2 apresenta um conjunto de funções de teste a serem escolhidas
para execução das simulações envolvendo os diversos tipos de PSO. Após a escolha da
função objetivo, deve ser definido o espaço de busca que será utilizado durante a simu-
lação. Existem campos específicos a serem preenchidos que definem número de dimen-
sões, intervalo de busca, intervalo de inicialização das partículas e valor máximo para a
104
velocidade das partículas.
A escolha dos valores para cada um desses campos definirá o espaço de busca onde as
partículas se moverão em busca de soluções para otimizar a função escolhida.
A parte 4 da Figura A.2 é responsável por apresentar o movimento das partículas du-
rante o processo de otimização. Um plano é definido com dois eixos x e y que representam
as duas dimensões de mais alta ordem das partículas. Utilizar essa representação gráfica
torna mais fácil o entendimento do movimento das partículas no processo de busca. Os
pontos em cinza representam as posições visitadas por cada partícula (rastro) e o ponto em
vermelho representa a melhor solução encontrada pelo enxame até a iteração atual. Ex-
clusivamente para casos de simulações que utilizam a topologia baseada em clãs, existe
ainda o rastro deixado pelas partículas líderes que são representados pelos pontos em
verde.
O acompanhamento do processo é mostrado na parte 5 da Figura A.2. Essa parte é
utilizada para mostrar o progresso da busca que está sendo realizada, assim como os valo-
res de x, y e fitness da melhor partícula do enxame na iteração atual. Tanto o movimento
do enxame quanto o progresso da busca são atualizados a cada iteração do processo. O
botão Start iniciauma busca caso os campos estejam corretamente preenchidos, e o botão
Cancel suspende o processo de busca.
Com o término da busca, o botão Generate chart fica habilitado, podendo assim ser
gerado a curva de convergência relativa ao processo de busca realizado. A Figura A.3
apresenta um exemplo contendo a curva de convergência relativa a uma busca utilizando
como função objetivo a função Griewank.
O PSS se tornou uma ferramenta bastante utilizada durante o desenvolvimento do tra-
balho realizado nessa dissertação, visto que foi feito um grande número de experimentos
envolvendo diferentes tipos de PSO e variações de topologias. Com a facilidade de criar e
incorporar novas topologias e abordagens de PSO ao PSS, pode-se acelerar o desenvolvi-
mento de novas variações de PSO.
105
Figura A.3: Exemplo de curva de convergência gerada após o término de um processo de
busca para a função Griewank.
106
APÊNDICE B
Lista de Publicações
• Autores: LINS, A. J. C. C. ; CALDAS, B. ; BASTOS FILHO, C. J. A. ; CAR-
VALHO, D. F. ; PACHECO, D. F. ; LIMA NETO, F. B.
Título: A Novel Approach for Wavelength Assignment in Optical Links Based on
Modified Genetic Algorithm
I Simpósio Brasileiro de Inteligência Computacional, 2007, Florianópolis/SC
• Autores: CARVALHO, D. F. ; BASTOS FILHO, C. J. A.
Título: Clan Particle Swarm Optimization
2008 IEEE Congress on Evolutionary Computation (IEEE CEC 2008) within
2008IEEE World Congresson Computational Intelligence (WCCI2008), 2008,
Hong Kong
• Autores: BASTOS FILHO, C. J. A. ; CARACIOLO, M. P. ; MIRANDA, P. B. C. ;
CARVALHO, D. F.
Título: Multi Ring PSO
SBRN’2008 (the 10th Brazilian Symposium on Neural Networks), 2008, Sal-
vador/BA
• Autores: BASTOS FILHO, C. J. A. ; CARACIOLO, M. P. ; MIRANDA, P. B. C. ;
CARVALHO, D. F.
Título: Multi-Ring Dispersed Particle Swarm Optimization
8th International Conference on Hybrid Intelligent Systems, 2008, Barcelona,
Espanha
107
ANEXO A
Box Plot
Entender e fazer uso de um conjunto de dados é um fator essencial dentro de um processo
científico. Dessa forma, uma análise esclarecedora desses dados é imprescindível para
demonstrar a importância dos mesmos.
Normalmente, utiliza-se medidas como: média, moda, mediana, variância (desvio
padrão) e quartis. Medidas como estas, tentam descrever de forma rápida e concisa a
importância associada à distribuição de dados, tornando possível a análise de múltiplos
conjuntos de dados mutuamente.
Um conjunto de dados é normalmente apresentada através de tabelas e gráficos. Grá-
ficos têm a capacidade de dizer muito sobre os dados em análise e também possuem
a vantagem de serem interpretados rapidamente, tornando o entendimento mais fácil e
dinâmico. Surge então o boxplot que é uma forma gráfica para expressar uma distribuição
de dados.
A idéia de usar um gráfico baseado em barras não só para comparação entre diferentes
distribuições de dados, mas também para mostrar medidas como mediana, média, moda,
desvio padrão e limites de tolerância através de marcas no próprio gráfico surgiu com o
trabalho de Haemer em 1948 (HAEMER, 1948).
A.1 O boxplot
O boxplot se tornou uma forma vastamente utilizada para apresentar cinco das principais
medidas relacionadas à uma distribuição de dados: o menor e o maior valor dentro da
distribuição, o quartil mais baixo e mais alto, e a mediana. O boxplot une todas essas me-
108
didas numa só representação gráfica originando um modo mais fácil e rápido de comparar
diferentes distribuições de dados.
A Figura A.1 mostra o modelo definindo cada medida e sua representação no boxplot.
Uma caixa (box) é utilizada para indicar a posição do mais alto e mais baixo quartil; o inte-
rior dessa caixa indica o intervalo denominado inter-quartil, que é a área definida entre os
dois quartis (mais alto e mais baixo) e é constituído pelos dados entre 25% e 75% da dis-
tribuição. As linhas chamadas de whiskers são estendidas aos valores extremos contidos
na distribuição, ou para valores múltiplos como 1, 5 do intervalo inter-quartil (FRIGGE;
HOAGLIN; IGLEWICZ, 1989) para assim remover os outliers extremos. Os outliers
podem ser representados individualmente por símbolos, representação essa chamada de
schematic plot (TUKEY, 1977).
Quartil mais alto
Quartil mais baixo
Mediana
Máximo
Mínimo
Média
Figura A.1: Modelo de representação em boxplot.
Finalmente, a caixa é cortada por uma linha horizontal que marca a mediana da dis-
tribuição. O comprimento e o preenchimento da caixa, o uso e a indicação dos outliers,e
a extensão da linha de intervalo dependem de como os dados serão representados.
Abaixo serão descritas as vantagens relacionadas ao uso do boxplot:
• cinco diferentes medidas estatísticas são apresentadas através de uma forma grá-
fica de fácil entendimento, que torna visível diferentes informações através de uma
rápida análise;
• informação de extrema importância mostrada de forma simples;
109
• possibilidade de comparação entre diferentes distribuições de dados mostradas lado
a lado em um mesmo gráfico;
• toda explicação do comportamento de uma distribuição sintetizada num só gráfico.
A Figura A.2(a) mostra uma extensão direta da idéia de Haemer, que foi a primeira
forma de boxplot utilizada (SPEAR, 1952). A forma que se tornou a mais comum dentro
da literatura está mostrada na Figura A.2(b) proposta em 1977 por Tukey(TUKEY, 1977).
Outras formas vieram a surgir após os trabalhos descritos acima, e estão mostradas nas
Figuras A.2(c) e A.2(d).
(a) (b) (c) (d)
Figura A.2: Diferentes formas de representação em boxplot.
110
Referências
ALANYALI, M.; AYANOGLU, E. Provisioning algorithms for WDM optical networks.
Networking, IEEE/ACM Transactions on, [S.l.], v.7, n.5, p.767–778, Oct 1999.
ALI, M.; KAMOUN, F. Neural networks for shortest path computation and routing in
computer networks. Neural Networks, IEEE Transactions on, [S.l.], v.4, n.6, p.941–
954, Nov 1993.
AMAZONAS, J. R. A. Projeto de sistemas de comunicações ópticas. 1st.ed. [S.l.]: Ed-
itora Manole, 2002.
BANERJEE, D.; MUKHERJEE, B. A practical approach for routing and wavelength as-
signment in large wavelength-routed optical networks. Selected Areas in Communica-
tions, IEEE Journal on, [S.l.], v.14, n.5, p.903–908, Jun 1996.
BARRY, R.; SUBRAMANIAM, S. TheMAX SUM wavelength assignment algorithm for
WDM ring networks. Optical Fiber Communication. OFC 97., Conference on, [S.l.],
p.121–122, 16-21 Feb 1997.
BECKERS, R.; DENEUBOURG, J.-L.; GOSS, S. Modulation of trail laying in the ant
Lasius niger (Hymenoptera: formicidae) and its role in the collective selection of a food
source. Journal of Insect Behavior, [S.l.], v.6, n.6, p.751–759, November 1993.
BIRMAN, A.; KERSHENBAUM, A. Routing and wavelength assignment methods in
single-hop all-optical networks with blocking. INFOCOM ’95. Fourteenth Annual
Joint Conference of the IEEE Computer and Communications Societies. Bringing
Information to People. Proceedings. IEEE, [S.l.], p.431–438 vol.2, 2-6 Apr 1995.
BISBAL, D. Dynamic Routing and Wavelength Assignment in Optical Networks by
111
Means of Genetic Algorithms. Photonic Network Communications, [S.l.], v.7, p.43–
58(16), 2004.
BONABEAU, E.; DORIGO, M.; THERAULAZ, G. Swarm Intelligence: from natural
to artificial systems. [S.l.]: Oxford, 1999.
BONABEAU, E.; HENAUX, F.; GUÉRIN,S.; SNYERS, D.; KUNTZ, P.; THERAULAZ,
G. Routingin TelecommunicationsNetworks with Ant-LikeAgents. In: ALBAYRAK, S.;
GARIJO, F. J. (Ed.). Intelligent Agents for Telecommunication Applications — Pro-
ceedings of the Second International Workshop on Intelligent Agents for Telecom-
munication (IATA’98). [S.l.]: Springer-Verlag: Heidelberg, Germany, 1998. (Lecture
Notes in Computer Science, v.1437).
BRATTON, D.; KENNEDY, J. Defining a Standard for Particle Swarm Optimization. In:
SWARM INTELLIGENCE SYMPOSIUM, 2007. SIS 2007. IEEE, 2007, Honolulu, HI.
Anais... [S.l.: s.n.], 2007. p.120–127.
C., B. P.; A., O. N.; R., S. J. Erbium-Doped Fiber Amplifiers. [S.l.]: Academic Press,
1999.
CAI, X.; CUI, Z.; ZENG, J.; TAN, Y. Dispersed particle swarm optimization. Inf. Pro-
cess. Lett., Amsterdam, The Netherlands, The Netherlands, v.105, n.6, p.231–235, 2008.
CARO, G. D.; DORIGO, M. AntNet: distributed stigmergetic control for communica-
tions networks. 1998.
CARVALHO, D. F.; BASTOS-FILHO, C. J. A. Clan Particle Swarm Optimization.
In: WCCI 2008 PROCEEDINGS (2008 IEEE WORLD CONGRESS ON COMPUTA-
TIONAL INTELLIGENCE, INCLUDING 2008 IEEE CONGRESS ON EVOLUTION-
ARY COMPUTATION (CEC 2008)), 2008, Hong Kong, China. Anais... [S.l.: s.n.],
2008.
CHAN, K.-M.; YUM, T. Analysis of least congested path routing in WDM lightwave
networks. INFOCOM ’94. Networking for Global Communications. 13th Proceed-
ings IEEE, [S.l.], p.962–969 vol.2, 12-16 Jun 1994.
112
CHAVES, D. Algoritmos rápidos de IRWA para redes totalmente ópticas. 2008. Dis-
sertação (Mestrado em Ciência da Computação) — Federal University of Pernambuco,
Recife, Brazil.
CHLAMTAC, I.; GANZ, A.; KARMI, G. Purely optical networks for terabit commu-
nication. INFOCOM ’89. Proceedings of the Eighth Annual Joint Conference of the
IEEE Computer andCommunications Societies. Technology: Emerging or Converg-
ing, IEEE, [S.l.], p.887–896 vol.3, 23-27 Apr 1989.
CHLAMTAC, I.; GANZ, A.; KARMI, G. Lightpath communications: an approach to
high bandwidth optical wan’s. Communications, IEEE Transactions on, [S.l.], v.40,
n.7, p.1171–1182, Jul 1992.
CLERC, M.; KENNEDY, J. The particle swarm - explosion, stability, and convergence in
a multidimensional complex space. IEEE-EC, [S.l.], v.6, p.58–73, Feb. 2002.
DENEUBOURG, J.-L.; ARON, S.; GOSS, S. The self-organizing exploratory pattern of
the argentine ant. Journal of Insect Behavior, [S.l.], v.3, p.159–169, 1990.
DIJKSTRA, E. W. A note on two problems in connection with graphs. Numerische
Mathematik, Berlin, v.1, p.269–271, 1959.
DORIGO, M.; BONABEAU, E.; THERAULAZ, G. Ant algorithms and stigmergy. Fu-
ture Generation Comp. Syst, [S.l.], v.16, n.8, p.851–871, 2000.
DORIGO, M.; CARO, G. D.; GAMBARDELLA, L. M. Ant Algorithms for Discrete
Optimization. Artificial Life, [S.l.], v.5, n.2, p.137–172, 1999.
DORIGO, M.; GAMBARDELLA, L. M. Ant Colony System: A cooperative learning ap-
proach to the traveling salesman problem. IEEE Trans. on Evolutionary Computation,
[S.l.], v.1, n.1, p.53–66, 1997.
DORIGO, M.; MANIEZZO, V.; COLORNI, A. Ant system: optimization by a colony of
cooperating agents. Systems, Man, and Cybernetics, Part B, IEEE Transactions on,
[S.l.], v.26, n.1, p.29–41, Feb 1996.
DORIGO, M.; STüTZLE, T. Ant Colony Optimization. [S.l.]: Bradford Book, 2004.
113
EBERHART, R. C.; SHI, Y. Comparing Inertia Weights and Constriction Factors in Par-
ticle Swarm Optimization. In: CONGRESS ON EVOLUTIONARY COMPUTATION
CEC00, 2000., 2000, La Jolla Marriott Hotel La Jolla, California, USA. Proceedings...
IEEE Press, 2000. p.84–88.
EBERHART, R.; SIMPSON, P.; DOBBINS, R. Computational intelligence PC tools.
San Diego, CA, USA: Academic Press Professional, Inc., 1996.
ENGELBRECHT, A. P. Fundamentals of Computational Swarm Intelligence. [S.l.]:
John Wiley & Sons, 2005.
FRIGGE, M.; HOAGLIN, D. C.; IGLEWICZ, B. Some Implementations of the Boxplot.
The American Statistician, [S.l.], v.43, n.1, p.50–54, Feb 1989.
GERSTEL, O.; KUTTEN,S. Dynamic wavelengthallocation in all-optical ring networks.
Communications, 1997. ICC 97 Montreal, ’Towards the Knowledge Millennium’.
1997 IEEE International Conference on, [S.l.], v.1, p.432–436 vol.1, 8-12 Jun 1997.
GOSS, S.; ARON, S.; DENEUBOURG, J.; PASTEELS, J. Self-organized shortcuts in the
Argentine ant. Naturwissenschaften, [S.l.], v.76, n.12, p.579–581, December 1989.
GRASSé, P.-P. La reconstruction du nid et le coordinations inter-individuelleschez Belli-
cositermes natalensis et Cubitermes sp. La théorie de la stigmergie : essai d’interpretation
du comportement des termites constructeurs. Insectes Sociaux, [S.l.], v.6, p.41–81, 1959.
HAEMER, K. W. Range-Bar Charts. The American Statistician, [S.l.], v.2, n.2, p.23,
April 1948.
HALLOY, J.; DENEUBOURG, J. L.; MILLOR, J.; AME, J. M. Individual discrimination
capability and collective decision-making. Journal of Theoretical Biology, [S.l.], v.239,
p.313–323, Nov. 2006.
HARAI, H.; MURATA, M.; MIYAHARA, H. Performance of alternate routing methods
in all-optical switching networks. INFOCOM ’97. Sixteenth Annual Joint Conference
of the IEEE Computer and Communications Societies. Proceedings IEEE, [S.l.], v.2,
p.516–524 vol.2, 7-12 Apr 1997.
114
ISRAEL A. WAGNER MICHAEL LINDENBAUM, A. M. B. ANTS: agents, networks,
trees, and subgraphs. In: 2000. Anais... unknown, 2000. v.16, p.915–926.
JEONG, G.; AYANOGLU, E. Comparison of wavelength-interchanging and wavelength-
selective cross-connects in multiwavelength all-optical networks. INFOCOM ’96. Fif-
teenth Annual Joint Conference of the IEEE Computer Societies. Networking the
Next Generation. Proceedings IEEE, [S.l.], v.1, p.156–163 vol.1, 24-28 Mar 1996.
KARASAN, E.; AYANOGLU, E. Effects of wavelength routing and selection algorithms
on wavelength conversion gain in WDM optical networks. Global Telecommunications
Conference, 1996. GLOBECOM ’96. ’Communications: The Key to Global Pros-
perity, [S.l.], v.1, p.299–305 vol.1, 18-22 Nov 1996.
KENNEDY, J. Small worlds and mega-minds: effects of neighborhood topology on par-
ticle swarm performance. Evolutionary Computation, 1999. CEC 99. Proceedings of
the 1999 Congress on, [S.l.], v.3, p.–1938 Vol. 3, 1999.
KENNEDY, J. Why does it need velocity? In: SWARM INTELLIGENCE SYMPO-
SIUM, 2005. SIS 2005. PROCEEDINGS 2005 IEEE, 2005. Anais... [S.l.: s.n.], 2005.
p.38–44.
KENNEDY, J.; EBERHART, R. C. Particle swarm optimization. In: IEEE INT. CONF.
ON NEURAL NETWORKS, 1995, Piscataway, NJ. Proceedings... IEEE Service Cen-
ter, 1995. p.1942–1948.
KENNEDY, J.; EBERHART, R. C. Swarm intelligence. San Francisco, CA, USA: Mor-
gan Kaufmann Publishers Inc., 2001.
KENNEDY, J.; MENDES, R. Population Structure and Particle Swarm Performance. In:
CONGRESS ON EVOLUTIONARYCOMPUTATION CEC2002, 2002., 2002. Proceed-
ings... IEEE Press, 2002. p.1671–1676.
KENNINGTON, J.; OLINICK, E.; ORTYNSKI, A.; SPIRIDE, G. Wavelength Routing
and Assignment in a Survivable WDM Mesh Network. Oper. Res., Institute for Opera-
tions Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA,
v.51, n.1, p.67–79, 2003.
115
LE, V. T.; JIANG, X.; NGO, S.-H.; HORIGUCHI, S. Dynamic RWA Based on the Com-
bination of Mobile Agents Technique and Genetic Algorithm in WDM Networks with
Sparse Wavelength Conversion. In: IPDPS, 2005. Anais... IEEE Computer Society,
2005.
LI, L.; SOMANI, A. Dynamic wavelength routing using congestion and neighborhood
information. Networking, IEEE/ACM Transactions on, [S.l.], v.7, n.5, p.779–786, Oct
1999.
MARTINS-FILHO, J.; BASTOS-FILHO, C.; ARANTES, E.; OLIVEIRA, S.; COELHO,
L.; OLIVEIRA, J. de; DANTE, R.; FONTANA, E.; NUNES, F. Novel routing algo-
rithm for transparent optical networks based on noise figure and amplifier saturation. Mi-
crowaveand Optoelectronics Conference, 2003.IMOC2003.Proceedingsof the 2003
SBMO/IEEE MTT-S International, [S.l.], v.2, p.919–923 vol.2, 20-23 Sept. 2003.
MATULA, D. W.; MARBLE, G.; ISAACSON, J. D. Graph Coloring Algorithms. In:
READ, R. C. (Ed.). Graph Theory and Computing. [S.l.]: Academic Press, Inc., 1972.
p.109–122.
MENDES, R.; CORTEZ, P.; ROCHA, M.; NEVES, J. Particle swarms for feedforward
neural network training. Neural Networks, 2002. IJCNN ’02. Proceedings of the 2002
International Joint Conference on, [S.l.], v.2, p.1895–1899, 2002.
MENDES, R.; KENNEDY, J.; NEVES, J. Watch thy neighbor or how the swarm can
learn from its environment. In: SWARM INTELLIGENCE SYMPOSIUM, 2003. SIS
’03. PROCEEDINGS OF THE 2003 IEEE, 2003. Anais... [S.l.: s.n.], 2003. p.88–94.
MUKHERJEE, B. Optical Communication Networks. New York: McGraw-Hill, 1997.
NAKA,S.; GENJI,T.; YURA, T.; FUKUYAMA, Y. Practical distributionstate estimation
using hybrid particle swarm optimization. Power Engineering Society Winter Meeting,
2001. IEEE, [S.l.], v.2, p.815–820 vol.2, 2001.
NGO, S.-H.; JIANG, X.; HORIGUCHI, S. Adaptive routing and wavelength assignment
using ant-based algorithm. Networks, 2004. (ICON 2004). Proceedings. 12th IEEE
International Conference on, [S.l.], v.2, p.482–486 vol.2, 16-19 Nov. 2004.
116
PEER, E.; BERGH, F. van den; ENGELBRECHT, A. Using neighbourhoods with the
guaranteed convergence PSO. Swarm Intelligence Symposium, 2003. SIS ’03. Proceed-
ings of the 2003 IEEE, [S.l.], p.235–242, 24-26 April 2003.
RAMAMURTHY, R.; MUKHERJEE, B. Fixed-alternate routing and wavelength conver-
sion in wavelength-routed optical networks. Networking, IEEE/ACM Transactions on,
[S.l.], v.10, n.3, p.351–367, Jun 2002.
RAMASWAMI, R.; SIVARAJAN, K. Routing and wavelength assignment in all-optical
networks. Networking, IEEE/ACM Transactions on, [S.l.], v.3, n.5, p.489–500, Oct
1995.
RAMASWAMI, R.; SIVARAJAN, K. N. Optical networks: a practical perspective. San
Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2002.
RATNAWEERA, A.; HALGAMUGE, S. K.; WATSON, H. C. Particle Swarm Optimiza-
tion with Self-Adaptive Acceleration Coefficients. In: FSKD, 2002. Anais... [S.l.: s.n.],
2002. p.264–268.
RAUCH, H.; WINARSKE, T. Neural networks for routing communication traffic. Con-
trol Systems Magazine, IEEE, [S.l.], v.8, n.2, p.26–31, Apr 1988.
REEVES, W. T. Particle Systems - a Technique for Modeling a Class of Fuzzy Objects.
ACM Trans. Graph., New York, NY, USA, v.2, n.2, p.91–108, 1983.
REYNOLDS, C. W. Flocks, herds and schools: a distributed behavioral model. In: SIG-
GRAPH ’87: PROCEEDINGS OF THE 14TH ANNUAL CONFERENCE ON COM-
PUTER GRAPHICS AND INTERACTIVE TECHNIQUES, 1987, New York, NY, USA.
Anais... ACM, 1987. p.25–34.
SCHOONDERWOERD, R.; HOLLAND, O.; BRUTEN, J. Ant-like agents for load bal-
ancing in telecommunications networks. In: AGENTS ’97: PROCEEDINGS OF THE
FIRST INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS, 1997, New
York, NY, USA. Anais... ACM Press, 1997. p.209–216.
SHI, Y.; EBERHART, R. A modified particle swarm optimizer. In: EVOLUTIONARY
COMPUTATION PROCEEDINGS, 1998. IEEE WORLD CONGRESS ON COMPUTA-
117
TIONAL INTELLIGENCE., THE 1998 IEEE INTERNATIONAL CONFERENCE ON,
1998, Anchorage, AK. Anais... [S.l.: s.n.], 1998. p.69–73.
SIM, K. M.; SUN, W. H. Ant colony optimization for routing and load-balancing: survey
and new directions. IEEE Transactions on Systems, Man, and Cybernetics, Part A,
[S.l.], v.33, n.5, p.560–572, 2003.
SPEAR, M. E. Charting Statistics. [S.l.]: McGraw-Hill Book Company, INC., 1952.
SUBRAMANIAM, S.; BARRY, R. Wavelength assignment in fixed routing WDM net-
works. Communications, 1997. ICC 97 Montreal, ’Towards the Knowledge Millen-
nium’. 1997 IEEE International Conference on, [S.l.], v.1, p.406–410 vol.1, 8-12 Jun
1997.
SUGANTHAN, P. Particle swarm optimiser with neighbourhood operator. Evolutionary
Computation, 1999. CEC 99. Proceedings of the 1999Congresson, [S.l.], v.3, p.–1962
Vol. 3, 1999.
SUTTON, A. M.; WHITLEY, D.; LUNACEK, M.; HOWE, A. PSO and multi-funnel
landscapes: how cooperation might limit exploration. In: GECCO 2006: PROCEED-
INGS OF THE 8TH ANNUAL CONFERENCE ON GENETIC AND EVOLUTION-
ARY COMPUTATION, 2006, Seattle, Washington, USA. Anais... ACM Press, 2006.
v.1, p.75–82.
TUKEY, J. W. Exploratory Data Analysis. [S.l.]: Addison-Wesley, 1977.
YOSHIDA, H.; FUKUYAMA, Y.; TAKAYAMA, S.; NAKANISHI, Y. A particle swarm
optimization for reactive power and voltage control in electric power systems considering
voltage security assessment. Systems, Man, and Cybernetics, 1999. IEEE SMC ’99
Conference Proceedings. 1999 IEEE International Conference on, [S.l.], v.6, p.497–
502 vol.6, 1999.
YUAN, Y.-W.; ZHAN, H.-H.; YAN, L.-M. An Adaptative QoS Route Selection Algo-
rithm Based on Genetic Approach in Combination with Neural Network. In: SECOND
INT. CONF. ON MACHINE LEARNING AND CYBERNETICS, 2003. Proceedings...
IEEE Service Center, 2003. p.69–73.
118
ZANG, H.; JUE, J.; MUKHERJEEE, B. A review of routing and wavelength assign-
ment approaches for wavelength-routed optical WDM networks. 2000.
ZHANG, L.; THOMOPOULOS, S. C. A. Neural Network Implementation of the Shortest
Path Algorithm for Traffic Routing in Communication Networks. In: IEEE INTERNA-
TIONAL JOINT CONFERENCE ON NEURAL NETWORKS (3RD IJCNN’89), 1989,
Washington DC. Anais... IEEE, 1989. v.II, p.II–591.
ZHANG, X.; QIAO, C. Wavelength assignment for dynamic traffic in multi-fiber WDM
networks. Computer Communications and Networks, 1998. Proceedings. 7th Inter-
national Conference on, [S.l.], p.479–485, 12-15 Oct 1998.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
