118
UNIVERSIDADE ESTADUAL DE MONTES CLAROS UNIMONTES Centro de Ciências Exatas e Tecnológicas CCET Departamento de Ciências da Computação DCC Curso de Sistemas de Informação Samuel Cruz Guimarães ESTUDO COMPARATIVO DAS METAHEURÍSTICAS DE ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS NA OTIMIZAÇÃO DOS RECURSOS DE REDE EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO UTILIZADO EM REDES IP/MPLS Montes Claros MG 2010

ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

Embed Size (px)

Citation preview

Page 1: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

UNIVERSIDADE ESTADUAL DE MONTES CLAROS – UNIMONTES

Centro de Ciências Exatas e Tecnológicas – CCET

Departamento de Ciências da Computação – DCC

Curso de Sistemas de Informação

Samuel Cruz Guimarães

ESTUDO COMPARATIVO DAS METAHEURÍSTICAS DE

ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS

APLICADAS NA OTIMIZAÇÃO DOS RECURSOS DE REDE

EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

UTILIZADO EM REDES IP/MPLS

Montes Claros – MG

2010

Page 2: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

Samuel Cruz Guimarães

ESTUDO COMPARATIVO DAS METAHEURÍSTICAS DE

ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS

APLICADAS NA OTIMIZAÇÃO DOS RECURSOS DE REDE EM

UM SISTEMA DE ENGENHARIA DE TRÁFEGO UTILIZADO EM

REDES IP/MPLS

Projeto Orientado de Conclusão de

Curso apresentado ao Departamento

de Ciências da Computação da

Universidade Estadual de Montes

Claros, como requisito parcial para a

conclusão do curso Sistemas de

Informação, orientado pelo professor

Dr. Nilton Alves Maia.

Montes Claros – MG

2010

Page 3: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

Dedico este trabalho à minha mãe Bete,

a pessoa que mais se esforçou para que

eu alcançasse esta vitória; não posso me

esquecer também de toda minha família,

amigos, minha companheira Vívian e

uma pessoa, que mesmo antes de chegar

neste mundo, tornou-se a mais

importante em minha vida e serviu de

motivação para conclusão deste trabalho,

meu filho, Caio Maurício.

Page 4: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

AGRADECIMENTOS

Em primeiro lugar, agradeço a Deus por mais essa graça concedida e por todo o

conforto recebido nos momentos de dificuldade.

Ao professor e orientador Dr. Nilton Alves Maia, que soube compartilhar toda sua

sabedoria e conhecimento, e a todos os demais professores, que durante todo o curso

contribuíram para que fosse possível a conclusão deste trabalho.

Agradeço também aos meus colegas de faculdade, que em muitos momentos, com suas

histórias de vida e superação, me ensinaram muito mais do que os próprios professores;

e por todos os momentos de amizade e companheirismo vividos durante todo esse

tempo.

Aos meus colegas da Credinor, principalmente ao meu supervisor Paulo Roberto e

colegas de setor, que sempre contribuíram para que fosse possível conciliar o trabalho e

os estudos.

Por fim, agradeço a toda minha família e amigos, em especial minha mãe Bete, minha

tia Dalva, meus irmãos Roney e Fabiana, minha companheira Vívian e meu esperado

filho, Caio Maurício.

Page 5: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

RESUMO

O aumento da demanda de transmissão de dados mistos (dados, voz e vídeo) através da rede

mundial de computadores, e a necessidade cada vez maior de atender a estas demandas de

forma compartilhada com a mesma qualidade de um serviço local, fazem-se necessária a

criação de novas configurações de transmissão destes dados. Diversos trabalhos buscam, das

mais diferentes formas, propor novas técnicas para melhorar a prestação dos serviços de

Internet, de forma a atender aos requisitos de Qualidade de Serviço (QoS) exigidos. Um

exemplo destes trabalhos é a tese de doutorado do Dr. Nilton Alves Maia, de 2006, intitulado

“Engenharia de Tráfego em Domínio MPLS Utilizando Técnicas de Inteligência

Computacional”, que propõe a criação de um sistema de Engenharia de Tráfego (TE)

utilizando MPLS, princípios de Computação Autonômica e técnicas de Inteligência

Computacional. Um dos módulos deste sistema de TE busca otimizar os recursos de rede. O

presente trabalho objetiva a criação de dois algoritmos de otimização baseados na

Computação Natural, mais especificamente nas heurísticas de Algoritmos Genéticos e

Colônia de Formigas, para que possam ser testados com os arquivos gerados pelo sistema de

TE proposto. Os algoritmos foram desenvolvidos no software MATLAB. Posteriormente, os

resultados dos testes dos dois algoritmos foram comparados entre si. Os resultados dos testes

mostraram que os dois algoritmos são eficientes para otimizar os recursos de rede. Mostrou

também que se torna inviável a utilização destes algoritmos para redes de topologias simples.

Para os parâmetros utilizados neste trabalho o algoritmo genético mostrou-se mais vantajoso

em relação ao algoritmo de colônia de formigas.

Palavras Chaves: Algoritmos Genéticos. Colônia de Formigas. Computação Evolutiva.

Computação Natural. Engenharia de Tráfego. Inteligência Coletiva. MATLAB. MPLS.

Otimização. QoS.

Page 6: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

ABSTRACT

The increased demand for transmission of mixed data (data, voice and video) through the

World Wide Web, and the increasing need to meet these demands that are shared with the

same quality of a local service, make it necessary to creation of new configurations of

transmission of data. Several works look, from different ways, propose new techniques to

improve the delivery of Internet services in order to meet the requirements of Quality of

Service (QoS) requirements. An example of this work is the doctoral thesis of Dr. Nilton

Alves Maia, of 2006, entitled "Engenharia de Tráfego em Domínio MPLS Utilizando

Técnicas de Inteligência Computacional", which proposes the creation of a Traffic

Engineering (TE) using MPLS , principles of Autonomic Computing and Computational

Intelligence techniques. One of the modules of this system of TE aims to optimize the

network resources. The present work aims to create two optimization algorithms based on

Natural Computation, more specifically in the heuristics of Genetic Algorithms and Ant

Colony, so they can be tested with the files generated by the system of TE proposed. The

algorithms were developed in the software MATLAB. Subsequently, the test results of the

two algorithms were compared between itself. The test results showed that both are efficient

algorithms to optimize network resources. He also showed it is not feasible to use these

algorithms for simple network topologies. For the parameters used in this study, the genetic

algorithm was more advantageous over the ant colony algorithm.

Keywords: Genetic Algorithms. Ant Colony. Evolutionary Computation. Natural Computing.

Traffic Engineering. Swarm Intelligence. MATLAB. MPLS. Optimization. QoS.

Page 7: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

LISTA DE FIGURAS

Figura 1: Exemplo de um domínio MPLS e seus componentes. .............................................. 20

Figura 2: Topologia de rede utilizando TE. .............................................................................. 21

Figura 3: Pseudocódigo básico da CE. ..................................................................................... 26

Figura 4: Representação do Espaço de Busca de uma Função e seus mínimos local e global. 29

Figura 5: Pseudocódigo de um AG. ......................................................................................... 35

Figura 6: Fluxograma que sintetiza um algoritmo genético. .................................................... 35

Figura 7: Representação de decodificação dos bits de um cromossomo binário em números

reais. .......................................................................................................................................... 37

Figura 8: Exemplo de seleção através do método da roleta. .................................................... 40

Figura 9: Exemplificação de um Cruzamento de um ponto. .................................................... 43

Figura 10: Exemplificação de um Cruzamento de dois pontos. ............................................... 43

Figura 11: Exemplificação de um Cruzamento uniforme. ....................................................... 44

Figura 12: Exemplo do caminho entre o ninho e a fonte de alimento usando duas pontes de

comprimento idênticas na experiência com formigas reais (GOSS et al., 1989). .................... 55

Figura 13: Exemplo do caminho entre o ninho e a fonte de alimento usando duas pontes de

comprimento diferentes na experiência com formigas reais (GOSS et al., 1989).................... 56

Figura 14: Pseudocódigo da metaheurística ACO. ................................................................... 59

Figura 15: Componentes do sistema de TE básico (MAIA, 2006). ......................................... 67

Figura 16: Componentes do sistema de TE proposto por MAIA (2006). ................................ 68

Figura 17: Interação entre os programas para a simulação do sistema de TE (MAIA, 2006). 71

Figura 18: Componente principal do Algoritmo Genético ....................................................... 75

Figura 19: Componente principal do algoritmo de colônia de formigas .................................. 80

Figura 20: Topologia I de simulação (MAIA, 2006)................................................................ 83

Figura 21: Topologia II de simulação (MAIA, 2006). ............................................................. 86

Figura 22: Evolução do AG na simulação I na topologia I. ..................................................... 92

Figura 23: Evolução do AG na simulação II na topologia I. .................................................... 93

Figura 24: Evolução do AG na simulação III na topologia I.................................................... 93

Figura 25: Evolução do AG na simulação IV na topologia I. .................................................. 93

Figura 26: Evolução do AG na simulação V na topologia I. .................................................... 94

Figura 27: Simulação do AG em cem execuções consecutivas na topologia I. ....................... 95

Figura 28: Evolução do ACS na simulação I na topologia I. ................................................... 96

Page 8: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

Figura 29: Evolução do ACS na simulação II na topologia I. .................................................. 96

Figura 30: Evolução do ACS na simulação III na topologia I. ................................................ 97

Figura 31: Evolução do ACS na simulação IV na topologia I. ................................................ 97

Figura 32: Evolução do ACS na simulação V na topologia I. .................................................. 97

Figura 33: Simulação do ACS em cem execuções consecutivas na topologia I. ..................... 98

Figura 34: Evolução do AG na simulação I na topologia II. .................................................. 100

Figura 35: Evolução do AG na simulação II na topologia II. ................................................ 100

Figura 36: Evolução do AG na simulação III na topologia II. ............................................... 100

Figura 37: Evolução do AG na simulação IV na topologia II. ............................................... 101

Figura 38: Evolução do AG na simulação V na topologia II. ................................................ 101

Figura 39: Simulação do AG em cem execuções consecutivas na topologia II. .................... 102

Figura 40: Evolução do ACS na simulação I na topologia II. ................................................ 104

Figura 41: Evolução do ACS na simulação II na topologia II. .............................................. 105

Figura 42: Evolução do ACS na simulação III na topologia II. ............................................. 105

Figura 43: Evolução do ACS na simulação IV na topologia II. ............................................. 105

Figura 44: Evolução do ACS na simulação V na topologia II. .............................................. 106

Figura 45: Simulação do ACS em cem execuções consecutivas na topologia II. .................. 107

Figura 46: Comparação dos menores fitness encontrados entre o AG e o ACS na 1ª simulação

................................................................................................................................................ 110

Figura 47: Comparação dos menores fitness encontrados entre o AG e o ACS na 2ª simulação

................................................................................................................................................ 110

Page 9: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

LISTA DE TABELAS

Tabela 1: Exemplo do operador de Mutação (taxa de mutação = 0,003) ................................. 45

Tabela 2: Lista de caminhos em condições de estabelecer LSP´s para as aplicações. ............. 69

Tabela 3: Exemplo de uma possível solução em condições de estabelecer as LSP´s para o

conjunto de aplicações. ............................................................................................................. 70

Tabela 4: Possíveis caminhos das aplicações na simulação da topologia I. ............................. 85

Tabela 5: Larguras de banda dos enlaces na topologia I. ......................................................... 85

Tabela 6: Características dos enlaces do domínio MPLS na topologia II. ............................... 87

Tabela 7: Necessidades e características das aplicações de dados, voz e vídeo ....................... 88

Tabela 8: Possíveis caminhos das aplicações na simulação da topologia II. ........................... 89

Tabela 9: Larguras de banda dos enlaces na topologia I. ......................................................... 90

Tabela 10: Tempo de execução do AG e fitness da melhor solução nas simulações na

topologia I. ................................................................................................................................ 94

Tabela 11: Tempo de execução do ACS e fitness da melhor solução nas simulações na

topologia I. ................................................................................................................................ 98

Tabela 12: Tempo de execução do AG e fitness da melhor solução nas simulações da

topologia II. ............................................................................................................................ 101

Tabela 13: Medidas da simulação do AG na topologia II. ..................................................... 103

Tabela 14: Tempo de execução do ACS e fitness da melhor solução nas simulações da

topologia II. ............................................................................................................................ 106

Tabela 15: Medidas da simulação do ACS na topologia II .................................................... 108

Tabela 16: Resultados da comparação entre AG e ACS ........................................................ 109

Page 10: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

LISTA DE ACRÔNIMOS E SIGLAS

ACO Ant Colony Optimization

ACS Ant Colony System

AG Algoritmos Genéticos

AIEC Algoritmo de identificação de enlaces críticos

AS Ant System

CAC Connection Admission Control

CAC Connection Admission Control

CAL Módulo responsável pela criação e ativação das LSP´s

CARQ Coletor das aplicações e requisitos de QoS

CBR Constant Bit Rate

CCF Classificador dos caminhos em famílias

CE Computação Evolutiva

CIR Coletor de informações da rede

CLPC Construtor de lista preliminar de caminhos mais curtos para as LSP´s

CPMT Coletor e processador de medições de tráfego

DAV Detector de aumento da vazão das aplicações

DiffServ Differenciated Services

DNA Deoxyribonucleic Acid

ECL Módulo responsável pela escolha dos caminhos para as LSP´s

FEC Forwarding Equivalence Classe

FIFO First In, First Out

FTP File Transfer Protocol

HTTP Hypertext Transfer Protocol

IANL Identificador de necessidade de LSP´s

IETF Internet Engineering Task Force

IG Índice de Geração

IntServ Integrated Services

IP Internet Protocol

ITU-T International Telecommunication Union – Telecom. Standardization Sector

KBps Kilobyte por segundo

LER Label Edge Router

LSP Label Switched Paths

LSR Label Switch Router

MBps Megabyte por segundo

MPLS Multi Protocol Label Switching

NAM Network Animator

NS2 Network Simulator

OAG Módulo de otimização utilizando algoritmos genéticos

QoS Quality of Service

RCPT Reconhecimento e classificação dos perfis de comportamento de tráfego das

Aplicações

Page 11: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

SI Swarm Intelligence

SIF Sistema de Inferência Nebulosa

SLA Service Level Agreement

SSS Simple Subpopulation Schemes

TCP Transfer Control Protocol

TE Traffic Engineering

UDP User Datagram Protocol

Page 12: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

SUMÁRIO

1. INTRODUÇÃO .................................................................................................................... 14

1.1. PROBLEMA ................................................................................................................. 15

1.2. JUSTIFICATIVA .......................................................................................................... 15

1.3. OBJETIVOS .................................................................................................................. 16

1.3.1. OBJETIVO GERAL ............................................................................................... 16

1.3.2. OJETIVOS ESPECÍFICOS .................................................................................... 17

1.4. ESTRUTURA DO TRABALHO .................................................................................. 17

2. FUNDAMENTAÇÃO TEÓRICA ....................................................................................... 18

2.1. QUALIDADE DE SERVIÇO (QoS) ............................................................................ 18

2.2. MPLS ............................................................................................................................. 19

2.3. ENGENHARIA DE TRÁFEGO ................................................................................... 20

2.4. OTIMIZAÇÃO .............................................................................................................. 21

2.4.1. MODELAGEM MATEMÁTICA PARA O PROBLEMA GERAL DE

OTIMIZAÇÃO ................................................................................................................. 22

2.5. COMPUTAÇÃO NATURAL ....................................................................................... 23

2.5.1. COMPUTAÇÃO EVOLUTIVA ............................................................................ 24

2.5.1.1. ALGORITMOS GENÉTICOS ........................................................................ 27

2.5.2. INTELIGÊNCIA COLETIVA ............................................................................... 52

2.5.2.1. COLÔNIA DE FORMIGAS ........................................................................... 53

3. MODELAGEM E DESENVOLVIMENTO ........................................................................ 66

3.1. ENGENHARIA DE TRÁFEGO EM DOMÍNIO MPLS UTILIZANDO TÉCNICAS

DE INTELIGÊNCIA COMPUTACIONAL (MAIA, 2006) ................................................ 66

3.2. MATLAB ...................................................................................................................... 71

3.3. IMPLEMENTAÇÃO DOS ALGORITMOS DE OTIMIZAÇÃO ................................ 72

3.3.1. ALGORITMO GENÉTICO ................................................................................... 73

3.3.2. ALGORITMO DE COLÔNIA DE FORMIGAS ................................................... 77

4. RESULTADOS OBTIDOS .................................................................................................. 82

4.1. TOPOLOGIAS UTILIZADAS ..................................................................................... 82

4.1.1. TOPOLOGIA I ....................................................................................................... 82

4.1.2. TOPOLOGIA II ...................................................................................................... 86

4.2. RESULTADOS DA IMPLEMENTAÇÃO DOS ALGORITMOS DE OTIMIZAÇÃO

PARA OS ARQUIVOS DO SISTEMA DE TE ................................................................... 91

4.2.1. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO GENÉTICO NA

TOPOLOGIA I ................................................................................................................. 92

4.2.2. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO DE COLÔNIA DE

FORMIGAS NA TOPOLOGIA I..................................................................................... 96

Page 13: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

13

4.2.3. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO GENÉTICO NA

TOPOLOGIA II ................................................................................................................ 99

4.2.4. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO DE COLÔNIA DE

FORMIGAS NA TOPOLOGIA II ................................................................................. 104

4.2.5. COMPARAÇÃO DA EXECUÇÃO DO ALGORITMO GENÉTICO COM O

ALGORITMO DE COLÔNIA DE FORMIGAS ........................................................... 109

5. CONCLUSÕES .................................................................................................................. 112

6. REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................... 115

Page 14: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

14

1. INTRODUÇÃO

A Internet, devido ao seu crescimento exponencial, cada vez mais, vem se

tornando uma realidade na vida das pessoas em todo o mundo. Em função da evolução

tecnológica e do surgimento de aplicações com novas demandas de desempenho e segurança,

exemplo das aplicações multimídia e em tempo real, como vídeo sob demanda,

videoconferência, voz sobre IP, computação em grupo de trabalho (controle de fluxo de

trabalho, tele-medicina), a necessidade do provimento de Qualidade de Serviço (QoS), pelas

operadoras de telecomunicações, tornou-se notória para o ambiente de aplicações distribuídas,

para que assim o usuário final usufrua os recursos compartilhados em rede, da mesma forma

como se estivessem executando as aplicações localmente.

Atualmente, o serviço oferecido aos usuários da Internet é o de melhor esforço

para a transmissão de dados, usando algoritmos para calcular o menor custo de transmissão,

porém, tal custo é calculado levando-se em conta apenas a extensão do caminho, sendo que

nenhuma consideração é feita sobre as outras métricas, assim sendo, não há qualquer

compromisso com requisitos de QoS. Em função da sua simplicidade original, o protocolo IP

apresenta algumas limitações ao provimento de QoS.

Devido a este novo paradigma das aplicações distribuídas, em que as redes têm

que se confrontar com a integração de variados tipos de serviços, além de também prover a

QoS, torna-se indispensável à utilização de novas políticas operacionais, mecanismos e

protocolos, que suportem, por exemplo, estratégias de diferenciação de serviços, adicionando

flexibilidade e eficiência à infra-estrutura de telecomunicações.

Existem várias propostas que objetivam adaptar a Internet atual para que esta

possa fornecer QoS, dentre os quais devemos destacar a Engenharia de Tráfego, o modelo de

Serviços Integrados (IntServ), o modelo de Serviços Diferenciados (DiffServ), Roteamento

Baseado em QoS e o Multi Protocol Label Switching (MPLS).

Ainda assim, por causa da elevada taxa de mudança das informações, tecnologias

e serviços e complexidade dos mesmos, os mecanismos atuais estão tornando-se ineficazes ou

impróprios para atender em sua totalidade os sistemas e serviços de rede. Isto faz com que

cada vez mais sejam estudadas alternativas para este novo paradigma dos sistemas

distribuídos, dentre elas podemos citar a utilização de diversas heurísticas da Computação

Page 15: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

15

Natural com o propósito de tratar essas complexidades, como os Algoritmos Genéticos,

Colônia de Formigas e os Sistemas Imunológicos Artificiais dentre outras.

1.1. PROBLEMA

As mudanças no cenário dos sistemas distribuídos tornaram o padrão utilizado

atualmente inviável para promover diversos serviços com a qualidade esperada pelo usuário.

Portanto, a utilização de um Sistema de Engenharia de Tráfego em domínio MPLS utilizando

técnicas de Inteligência Computacional e algoritmos para otimização dos recursos de rede

baseados nas heurísticas de Algoritmos Genéticos e Colônia de Formigas seria eficaz para

sustentar um tráfego misto e fornecer um serviço com QoS?

1.2. JUSTIFICATIVA

A crescente expansão dos sistemas e serviços de Internet, e sendo esses cada vez

mais complexos e poderosos, têm evidenciado a incapacidade que as ferramentas atuais

apresentam com relação a suportar tais sistemas e serviços de forma a garantir o desempenho

e a segurança necessários. Portanto, torna-se necessário o desenvolvimento de novas

tecnologias e abordagens que permitam aos sistemas de Internet uma interação mais eficiente

e que esses possam se adaptar as mudanças do tipo e intensidade do tráfego que transpõe a

rede. Se ajustar a situações passíveis de ocorrência ou, ainda, maximizar seu desempenho

automaticamente em virtude de condições observadas, utilizando-se de ferramentas e técnicas

que apresentem algum tipo de comportamento inteligente, passa a ser características cogentes

aos novos mecanismos e protocolos utilizados nos serviços e sistemas de rede. As

metaheurísticas inspiradas na natureza apresentam adaptabilidade, tolerância a falhas e

robustez a variações ambientais, sendo estas características muito desejáveis, e o que fez com

que ferramentas que compreendem tais abordagens passassem a ser muito estudadas e

utilizadas com o propósito de suprir as deficiências encontradas nas ferramentas atuais. Duas

dessas metaheurísticas, dentre as mais citadas na literatura, são os Algoritmos Genéticos e

Colônia de Formigas.

Page 16: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

16

Atualmente, os algoritmos de roteamento em uso na Internet, objetivam

minimizar métricas de caminhos mais curtos tais como número de saltos entre origem e

destino de um respectivo fluxo de dados. Levando em consideração QoS, nem sempre o

caminho mais curto é o caminho que apresenta o melhor conjunto de recursos necessários a

uma aplicação. Em grande parte das redes atuais, quando enlaces começam a apresentar

tendência de congestionamento, a alternativa mais comum para solução deste problema é o

aumento da capacidade dos mesmos. Devido ao novo paradigma das aplicações distribuídas,

em que as redes têm que se confrontar com a integração de variados tipos de serviços, com o

crescimento das redes e o crescimento da demanda de recursos por parte das aplicações, surge

a necessidade de uma abordagem mais eficiente e menos custosa de utilização da rede. Neste

sentido, técnicas de Engenharia de Tráfego (TE) passando a ser utilizadas, contribuem

significativamente com a evolução das redes de computadores. O resultado direto da ação da

TE é o estabelecimento de um balanceamento de carga nos enlaces de rede, de modo a reduzir

os congestionamentos e otimizar a utilização dos seus recursos. A TE deve apresentar algum

tipo de comportamento inteligente e autônomo, sendo capaz de adaptar-se as mudanças nas

condições da rede, fato este que justifica a utilização de heurísticas de Algoritmos Genéticos e

Colônia de Formigas.

Através do MPLS é possível alterar o roteamento de uma rede adicionando-se

novas rotas àquelas fixadas pelo roteamento IP padrão. O MPLS surge como elemento de

suporte a TE em redes baseadas no protocolo IP, uma vez que implementa o modelo de

roteamento explícito, onde os pacotes de dados são transmitidos em caminhos virtuais

denominados Label Switched Paths (LSPs), e usam um rótulo de tamanho fixo a partir do

qual o roteador decide por onde enviar os pacotes. A possibilidade de estabelecimento destes

caminhos virtuais facilita a implementação da TE.

1.3. OBJETIVOS

1.3.1. OBJETIVO GERAL

Desenvolver, avaliar e comparar algoritmos utilizando AG e Colônia de Formigas

visando a otimização do uso de enlaces de um domínio MPLS alimentado com tráfego misto

Page 17: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

17

(dados, voz e vídeo) que serão utilizarão os arquivos gerados no Sistema de Engenharia de

Tráfego proposto por MAIA (2006).

1.3.2. OJETIVOS ESPECÍFICOS

• Estudo de técnicas de otimização, assim como das heurísticas de AG e Colônia de

Formigas;

• Desenvolvimento e avaliação de algoritmos alternativos para o tráfego em enlaces

de um domínio MPLS alimentado com aplicações de dados, voz e vídeo,

utilizando as técnicas de otimização e heurísticas exploradas anteriormente;

• Implementação dos algoritmos desenvolvidos utilizando os arquivos do Sistema

de Engenharia de Tráfego proposto por MAIA (2006), simulação e análise dos

mesmos, e posterior estudo comparativo entre eles.

1.4. ESTRUTURA DO TRABALHO

Este projeto está organizado da seguinte forma: o presente capítulo faz uma

introdução do tema proposto bem como apresenta sua justificativa, seus objetivos e mostra

como o trabalho foi estruturado; o capítulo 2 apresenta a fundamentação teórica utilizada para

o desenvolvimento deste trabalho, abordando assuntos pertinentes ao Sistema de Engenharia

de Tráfego proposto por MAIA (2006) que serve de base para introdução, análise e testes dos

algoritmos que serão desenvolvidos neste trabalho, assim como assuntos referentes à

otimização e heurísticas utilizados por estes mesmos algoritmos; no terceiro capítulo é

apresentada a implementação do trabalho, descreve a metodologia utilizada nos algoritmos de

otimização; o capítulo 4 apresenta a implantação, testes, resultados obtidos e faz uma

comparação entre os algoritmos utilizados; e por fim o capítulo 5 traz as conclusões e

dificuldades encontradas e os trabalhos futuros.

Page 18: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

18

2. FUNDAMENTAÇÃO TEÓRICA

2.1. QUALIDADE DE SERVIÇO (QoS)

Resultado da necessidade de atender apenas a um tipo específico de tráfego, o de

dados, a rede IP oferece um único nível de serviço, conhecido como “melhor esforço” (best

effort): transmissão de datagramas, sem garantia de entrega, de preservação da seqüência de

envio, de limite no atraso fim-a-fim ou de banda (bps) disponível. Diversas aplicações atuais

exigem um nível de serviço superior, expresso pelo o que se convencionou chamar de

Qualidade de Serviço (QoS – Quality of Service). Com relação a QoS, a ITU-T (International

Telecommunication Union – Standardization Sector) introduziu a noção de desempenho de

rede (NP – Network Performance), englobando todas as funções de rede essenciais para

prover o serviço. A NP está definida na Recomendação E.800 (ITU-T, 1993) como a

habilidade de uma rede ou porção de rede em prover as funções relacionadas às comunicações

entre usuários. A NP é definida e tratada em termos de um conjunto de parâmetros de

elementos de rede particulares, envolvidos no fornecimento de um serviço, que são essenciais

para a eficiência e a eficácia desse fornecimento (GOZDECKI, JAJSZCZYK e

STANKIEWICZ, 2003). Já a IETF (Internet Engineering Task Force) entende o conceito de

QoS como sendo um conjunto de requisitos de serviço a serem satisfeitos pela rede enquanto

transportando um fluxo (CRAWLEY et al., 1998). Esta definição é praticamente equivalente à

noção de NP dada pela ITU-T, sendo também definida em termos de parâmetros. A presente

proposta enfoca o conceito de QoS conforme a visão da IETF, ou seja, uma vez acordado com

o usuário (ou cliente) um conjunto de requisitos de serviços, a rede (provedor) deve atender

tais requisitos enquanto estiver transportando os fluxos objeto desse acordo.

A QoS em redes é expressa ao menos pelo seguinte conjunto de parâmetros, que

são significativos para a maioria dos serviços baseados em IP: vazão, atraso fim-a-fim, jitter

(variação do atraso) e perda de pacotes (GOZDECKI, JAJSZCZYK e STANKIEWICZ,

2003). O atraso fim-a-fim é o tempo necessário para um pacote percorrer a rede, medido do

momento em que é transmitido pelo emissor até ser recebido pelo receptor. O jitter é a

variação no intervalo entre chegadas de pacotes, introduzida pelo comportamento aleatório do

atraso na rede. A variação do atraso pode provocar uma distorção na informação recebida. A

Page 19: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

19

perda de pacotes representa o percentual de pacotes que foram transmitidos na rede, mas não

alcançaram seu destino em um determinado período de tempo.

A vazão é o volume de dados movidos de um nó de rede para outro em um dado

período de tempo, também expressa em KBps ou MBps (OLIVEIRA, 2001).

2.2. MPLS

O MPLS (MultiProtocol Label Switching) é uma tecnologia de encaminhamento

de pacotes baseada em rótulos (labels) que funciona, basicamente, com a adição de um rótulo

nos pacotes de tráfego na entrada do domínio (chamados de roteadores de borda) e, a partir

daí, todo o encaminhamento pelo domínio passa a ser feito com base neste rótulo.

Comparativamente ao encaminhamento IP, o MPLS torna-se mais eficiente uma vez que

dispensa a consulta das tabelas de roteamento. O MPLS é indiferente ao tipo de dados

transportado, pelo que pode ser tráfego IP ou outro qualquer.

A informação em uma rede MPLS é processada e dividida em classes de serviço,

e os dados são encaminhados através de rotas estabelecidas anteriormente por essas classes,

sendo feito apenas comutação.

O MPLS permite que os operadores de uma determinada rede tenham alto

desempenho no desvio de tráfego de dados em situações críticas, tais como de falhas e

gargalos ou congestionamentos. O MPLS permite assegurar que a transmissão de

determinados pacotes tenham perdas ou atrasos imperceptíveis em função da capacidade de

uma gestão de tráfego mais eficaz, possibilitando assim maior qualidade dos serviços e

conseqüentemente maior confiabilidade.

O caminho por onde os pacotes irão passar numa rede MPLS são chamados LSPs

(Label Switching Paths). Ao entrar no domínio MPLS o pacote é associado a uma Classe de

Equivalência de Encaminhamento (FEC, Forwarding Equivalence Classe). O responsável por

inserir o LSP e atribuir a FEC é o LSR (Label Switch Router) ou dispositivo da borda de

entrada do domínio (Ingress LSR), também denominado Roteador de Borda (LER, Label

Edge Router). O LSP é utilizado como um índice em uma tabela que especifica o próximo

salto e um novo LSP. O LSR seguinte troca o rótulo antigo pelo rótulo novo e encaminha o

pacote para o próximo salto. A Figura 1 mostra os principais componentes que integram uma

arquitetura MPLS.

Page 20: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

20

Figura 1: Exemplo de um domínio MPLS e seus componentes.

2.3. ENGENHARIA DE TRÁFEGO

A Engenharia de Tráfego (TE) preocupa-se em otimizar a performance das redes.

Para tanto ela mede, modela, caracteriza e controla o tráfego. Seu objetivo principal, então, é

ajudar a prover operações eficientes e confiáveis em uma rede, enquanto otimiza o uso de

seus recursos e sua performance. Em redes do tipo Internet, seus principais objetivos, no que

se refere à engenharia de tráfego para melhoria de desempenho são, minimizar a perda de

pacotes, minimizar o atraso, minimizar a variação do atraso (jitter), diminuir a probabilidade

de bloqueio, maximizar a capacidade de transferência e atender aos SLA (Service Level

Agreement) propostos para as redes (BLACK, 2002). Pode se implementar TE manualmente

em redes pequenas ou usando técnicas automatizadas, como o MPLS que utiliza parâmetros

como atraso, jitter e largura de banda para fazer o roteamento.

Para exemplificar o funcionamento da Engenharia de Tráfego considere a

topologia mostrada na Figura 2. Em um domínio que não implementa TE, todos os pacotes

devem ser encaminhados pelo caminho T1, no caso, o mais curto, o que poderia resultar em

congestionamento. A existência de congestionamento pode provocar a degradação da QoS.

Em um domínio que implementa TE, os pacotes são balanceados entres os caminhos

existentes (T1 e T2 no caso), evitando assim congestionamentos e degradação da QoS.

Page 21: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

21

Figura 2: Topologia de rede utilizando TE.

A TE é hoje a principal aplicação do MPLS devido a possibilidade de controlar o

fluxo de tráfego na rede, com o objetivo de reduzir problemas de congestionamento e

conseguir uma utilização homogênea dos recursos disponíveis.

2.4. OTIMIZAÇÃO

Em termos gerais, a teoria de otimização é um corpo de resultados matemáticos e

métodos numéricos utilizados na busca e identificação dos melhores candidatos em uma

coleção de alternativas, sem a necessidade de enumerar-se explicitamente e avaliar todas as

possibilidades. Em outras palavras, consiste em encontrar os mínimos ou máximos de uma

função de várias variáveis, com valores dentro de uma determinada região do espaço

multidimensional.

A força dos métodos de otimização em determinar o melhor caso, sem a

necessidade real de testar todos os possíveis casos, provém do uso de conceitos matemáticos e

do custo reduzido na execução dos cálculos numéricos, utilizando procedimentos ou

algoritmos lógicos, claramente bem definidos e com o auxílio de computadores nestes

processos iterativos (BEZ, 2005).

A problemática de adequar um modelo matemático a uma situação real também

pode ser formulada como um problema matemático, quase sempre de otimização.

Page 22: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

22

Os problemas de otimização podem ser divididos em duas classes no que diz

respeito a restrições: a classe de problemas com restrição e a classe de problemas sem

restrição ou irrestritos. Os problemas de otimização irrestritos podem ser: unidimensionais ou

multidimensionais, lineares ou não-lineares, não convexos ou convexos, contínuos ou

descontínuos e diferenciáveis ou não-diferenciáveis. De acordo com as características

apresentadas, deve-se escolher o método adequado para resolução do problema. Tais

características não serão explanadas, pois este não é o foco principal deste trabalho. Podem-se

também dividir os métodos de otimização em duas famílias: a dos métodos determinísticos e a

dos métodos estocásticos.

Os métodos determinísticos são procedimentos que se baseiam na busca sucessiva

de pontos no espaço de otimização, necessitando para esta busca o conhecimento de um vetor

direção de decrescimento da função. O processo de busca do ótimo utiliza o ponto corrente

como ponto de partida para a determinação do ponto subsequente (ÁVILA et al., 2003).

Os métodos estocásticos são parte de uma classe de métodos que se baseiam em

mecanismos probabilísticos. Estes, ao contrário dos métodos determinísticos, não necessitam

de características como continuidade e diferenciabilidade, requisitadas pela maioria dos

métodos determinísticos. Por requererem um grande número de análises do problema, tendo

em vista a necessidade de explorar devidamente todas as regiões do universo de busca em que

está contida a solução ótima, estas técnicas tornaram-se mais populares com a evolução dos

computadores. As heurísticas de AG e Colônia de Formigas são exemplos de métodos

estocásticos de otimização.

2.4.1. MODELAGEM MATEMÁTICA PARA O PROBLEMA GERAL DE

OTIMIZAÇÃO

O problema geral de otimização pode ser descrito matematicamente pela seguinte

expressão:

( )

( )

s.a. ( )

Page 23: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

23

Onde f, gi e hj são funções definidas em n, S

n e x é um vetor de n

componentes x = (x1, x2, ..., xn). O problema a ser solucionado é a determinação dos valores

das variáveis xi que satisfaçam as restrições, buscando minimizar o valor da função f. A

função f (x) é chamada função objetivo; gi(x) e hj(x) são as restrições.

A formulação apresentada refere-se a um problema de minimização sujeito a um

conjunto de restrições.

2.5. COMPUTAÇÃO NATURAL

A computação natural é constituída por novas abordagens de computação

caracterizadas pela busca de uma maior proximidade com a natureza e altíssimo potencial de

solução de problemas complexos do mundo real. A computação natural pode ser vista como

uma versão computacional do processo de extração de ideias da natureza para o

desenvolvimento de sistemas artificiais, ou então a utilização de meios e mecanismos naturais

para realizar computação.

A computação natural pode ser dividida em três grandes áreas:

• Computação inspirada na biologia: utiliza a natureza como fonte de inspiração

para o desenvolvimento de novas técnicas de solução de problemas (Computação

evolutiva, Inteligência coletiva, Neurocomputação, Imunocomputação, etc.);

• Biologia inspirada na computação: trata-se basicamente de um processo de síntese

que objetiva criar formas, padrões e comportamentos similares àqueles

conhecidos na natureza. Além disso, algumas áreas visam o desenvolvimento de

organismos artificiais (Vida artificial e autômatos celulares, Geometria fractal,

etc.);

• Biocomputação ou Computação com mecanismos naturais: Trata-se de um novo

paradigma de computação que vem com o objetivo principal de substituir as

arquiteturas computacionais conhecidas atualmente por arquiteturas que utilizam

mecanismos naturais (Computação de DNA, Computação quântica, etc.).

Iremos destacar duas subáreas da Computação Inspirada na Biologia, a

Computação evolutiva e a Inteligência coletiva, devido ao grau de importância no

desenvolvimento deste trabalho.

Page 24: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

24

2.5.1. COMPUTAÇÃO EVOLUTIVA

A computação evolutiva (CE) é um ramo da ciência da computação que propõe

um paradigma alternativo ao processamento de dados convencional. Este novo paradigma,

diferentemente do convencional, não exige, para resolver um problema, o conhecimento

prévio de uma maneira de encontrar uma solução. A CE é baseada em mecanismos evolutivos

encontrados na natureza, tais como a auto-organização e o comportamento adaptativo

(FARMER et al., 1983), (GOLDBERG; HOLLAND, 1988). Estes mecanismos foram

descobertos e formalizados por Darwin em sua teoria da evolução natural, segundo a qual, a

vida na terra é o resultado de um processo de seleção, pelo meio ambiente, dos mais aptos e

adaptados, e por isto mesmo com mais chances de reproduzir-se. A diversidade da vida,

associada ao fato de que todos os seres vivos compartilham uma bagagem genética comum,

pelo menos em termos de seus componentes básicos, é um exemplo eloquente das

possibilidades do mecanismo de evolução natural. A CE tem sido muito aplicada em

problemas de otimização, em especial naqueles em que técnicas tradicionais de otimização

não são aplicáveis ou apresentam desempenho insatisfatório.

Historicamente, as primeiras iniciativas na área de CE foram de biólogos e

geneticistas interessados em simular os processos vitais em computador, o que recebeu na

época o nome de Processos Genéticos.

A CE está baseada em algumas ideias básicas que, quando implementadas,

permitem simular em um computador o processo de passagem de gerações da evolução

natural. As ideias que permitem esta simulação são as seguintes:

• A criação de uma população de soluções, possivelmente obtida na sua primeira

geração de modo aleatório, e na qual os indivíduos tenham registrado de modo

intrínseco os parâmetros que descrevem uma possível solução ao problema posto.

• A criação de uma entidade - chamada função de avaliação - capaz de julgar a

aptidão de cada um dos indivíduos. Essa entidade não precisa deter conhecimento

sobre como encontrar uma solução para o problema, mas apenas atribuir uma

“nota” ao desempenho de cada um dos indivíduos da população.

• E, finalmente, a criação de uma série de operadores que serão aplicados à

população de uma dada geração para obter os indivíduos da próxima geração.

Page 25: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

25

Estes operadores são baseados nos fenômenos que ocorrem na evolução natural.

Os principais operadores citados na literatura são: (i) seleção: permite escolher um

indivíduo ou um par deles para gerar descendência. Note-se que este operador

simula a reprodução assexuada (no primeiro caso) e a sexuada (no segundo) que

ocorrem na natureza. Obviamente, a prioridade da escolha recai sobre indivíduos

mais bem avaliados pela função de avaliação; (ii) recombinação: operador que

simula a troca de material genético entre os ancestrais que, por sua vez, determina

a carga genética dos descendentes; (iii) mutação: operador que realiza mudanças

aleatórias no material genético.

O conceito chave na CE é o de adaptação que unifica a abordagem quanto ao

método de solução: uma população inicial de soluções evolui, ao longo das gerações que são

simuladas no processo, em direção a soluções mais adaptadas, isto é, com maior valor da

função de avaliação, por meio de operadores de seleção, mutação e recombinação.

O conjunto de soluções iniciais pode ser aleatório ou pode ser obtido a partir de

técnicas convencionais para resolver instâncias mais simples do problema que está sendo

tratado. Por um lado, usando-se soluções inicialmente aleatórias, pode-se usar sempre o

mesmo algoritmo e os mesmos operadores. Por outro lado, adaptando o conceito de CE a um

problema específico e empregando soluções iniciais obtidas por métodos convencionais, é

necessário adaptar os operadores usuais da CE para o problema específico. Em compensação,

na pior das hipóteses, a solução encontrada é igual à melhor solução obtida anteriormente

pelas técnicas convencionais.

Para definir a função de avaliação é necessário encontrar uma maneira de

codificar as soluções para o problema que se quer resolver. O resultado dessa codificação

corresponde aos cromossomos na evolução natural e é chamado de genótipo. A partir desses

cromossomos, a função de avaliação deve ser capaz de determinar a qualidade de uma

solução.

As novas soluções podem ser geradas a partir de uma única solução (assexuada,

na natureza) ou a partir de duas soluções (na natureza, sexuada). Estabelecido um conjunto de

novas soluções (os descendentes), estas sofrem a ação dos operadores evolutivos, mediante os

quais, os descendentes passarão a ser diferentes dos ascendentes. Os melhores, de acordo com

a função de avaliação, terão uma descendência maior do que a dos pouco aptos. Na

reprodução sexuada, a troca de material genético - chamada de recombinação - leva um par de

Page 26: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

26

ascendentes a dar origem a um par de descendentes onde cada descendente herda partes

aleatoriamente escolhidas de cada ascendente. A mutação leva à mudança, também aleatória,

de uma parte da solução. No caso mais simples de cromossomos codificados em binário, a

mutação é a simples inversão de um bit. Tanto a recombinação quanto a mutação tendem a

ocorrer segundo uma dada probabilidade (que são parâmetros da técnica).

Tal processo, repetido, simula a passagem das gerações. Como o processo está

sendo simulado em um computador digital, o fator tempo pode ser comprimido sem perda de

qualidade.

Pode-se descrever o algoritmo básico da CE através do pseudocódigo apresentado

na Figura 3. Neste algoritmo pode-se perceber o comportamento básico dos algoritmos

evolutivos que consiste em buscar dentro da atual população aquelas soluções que possuem as

melhores características e tentar combiná-las de forma a gerar soluções ainda melhores,

repetindo este processo até que tenha se passado tempo suficiente ou que tenha obtido uma

solução satisfatória para nosso problema (LINDEN, 2006).

Como se pode perceber claramente dentro do algoritmo, os algoritmos evolutivos

são extremamente dependentes de fatores probabilísticos, tanto na fase de inicialização da

população quanto na fase de evolução, durante a seleção dos pais, principalmente.

Isso faz com que os seus resultados raramente sejam perfeitamente reprodutíveis.

Ademais, claramente os algoritmos evolutivos são heurísticas1 que não garantem a obtenção

do melhor resultado possível em todas as suas execuções (LINDEN, 2006).

Figura 3: Pseudocódigo básico da CE.

1 Heurísticas são algoritmos polinomiais que não têm garantia nenhuma sobre a qualidade da solução encontrada,

mas que usualmente tendem a encontrar a solução ótima ou ficar bem próximos dela (LINDEN, 2006).

t:=0 // Inicializamos o contador de tempo

Inicializa_População P(0) // Inicializamos a população randomicamente

Enquanto não terminar faça //condição de término: por tempo, por avaliação, etc.

Avalie_População P(t) //Avalie a população neste instante

P':=Selecione_Pais P(t) //Selecionamos sub-população que gerará nova geração

P'=Recombinação_e_mutação P' //Aplicamos os operadores genéticos

Avalie_População P' //Avalie esta nova população

P(t+1)=Selecione_sobreviventes P(t),P' //Selecione sobreviventes desta geração

t:=t+1 //Incrementamos o contador de tempo

Fim enquanto

Page 27: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

27

Diversas abordagens para a CE foram propostas, sendo que as principais

diferenças entre elas dizem respeito aos operadores genéticos empregados. As principais

abordagens propostas na literatura são: Algoritmos Genéticos, Estratégias Evolutivas e

Programação Evolutiva. Além destas tem-se a Programação Genética (KOZA, 1992) e os

Sistemas Classificadores (BOOKER et al., 1989). A seção que segue abrangerá maiores

informações a respeito dos Algoritmos Genéticos.

2.5.1.1. ALGORITMOS GENÉTICOS

Os Algoritmos genéticos (AG) foram desenvolvidos por John Holland e sua

equipe, na Universidade de Michigan, em 1975. Até esse momento o assunto abrange o

âmbito da genética, economia, teoria de jogos, pesquisa, reconhecimento de padrões e

inferência estatística, controle e otimização de funções e sistema nervoso central.

Originalmente, os AG estavam muito fortemente ligados a modelos de aprendizado

automático, como é demonstrada na ênfase dada por HOLLAND (1975) aos chamados

sistemas classificadores, que são um modelo de máquina de aprendizado usando AG. Só mais

tarde, é que GOLDBERG (1989) passa a utilizar a ideia de otimização como tema central na

teoria dos AG. Por esses motivos é que, ao contrário das abordagens de Estratégias Evolutivas

e Programação Evolutiva, os AG conceitualmente apresentam um escopo mais amplo do que

a simples otimização, sendo apresentados como um modelo para a aprendizagem de máquina

por HEITKOETTER & BEASLEY (1994).

Portanto, pode-se dizer que o objetivo original de HOLLAND (1975) não foi o de

desenvolver algoritmos para a solução de problemas específicos, mas sim estudar

formalmente os fenômenos de adaptação, naturais ou artificiais, com o propósito de importar

estes mecanismos de adaptação para ambientes computacionais.

Os AG são o ramo mais conhecido da CE e como tal são algoritmos de otimização

global, baseados nos mecanismos de genética e seleção natural (GOLDBERG, 1989),

(LINDEN, 2006). Os AG são um mecanismo de busca de soluções que utiliza combinações

de melhores soluções - melhores pais - de uma determinada geração, com objetivo de obter

novas soluções - filhos - para a geração seguinte, que devem apresentar resultados mais

eficientes para a função de avaliação, função esta que é a responsável por manter a geração

contínua de melhores soluções para o problema.

Page 28: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

28

A base de um algoritmo genético pode ser definida por: “um procedimento de

descoberta de bons blocos, seleção destes blocos e construção de novos blocos a partir destes,

onde a idéia principal é que cada novo bloco gerado a partir de outros bons blocos, será

melhor que os blocos geradores” (HOLLAND, 1975).

Os AG não estacionam pelo fato de encontrar uma única solução para o problema,

assim como na seleção natural, que só por que encontrou um indivíduo que é

instantaneamente o melhor de certo grupo não pára de procurar outros indivíduos ainda

melhores, já que as circunstâncias podem mudar de um lugar para o outro (LINDEN, 2006).

Assim sendo, LINDEN (2006) conclui que os AG não constituem um algoritmo

de busca da solução ótima de um problema, mas sim uma heurística que encontra boas

soluções a cada execução, mas não necessariamente a mesma todas as vezes.

Os AG empregam uma estratégia de busca paralela e estruturada, mas aleatória,

que é voltada em direção ao reforço da busca de pontos de "alta aptidão", ou seja, pontos nos

quais a função a ser minimizada (ou maximizada) tem valores relativamente baixos (ou altos)

(BRAGA et al., 2000). Portanto, apesar de aleatórios, eles não são caminhadas aleatórias não

direcionadas, pois exploram informações históricas para encontrar novos pontos de busca

onde são esperados melhores desempenhos.

A vantagem principal dos AG ao trabalharem com o conceito de população, ao

contrário de muitos outros métodos que trabalham com um só ponto, é que eles encontram

segurança na quantidade. Tendo uma população de pontos bem adaptados, a possibilidade de

alcançar um falso ótimo torna-se menor. Os AG conseguem grande parte de sua amplitude

simplesmente ignorando informação que não constitua parte do objetivo, enquanto outros

métodos apoiam-se fortemente nesse tipo de informação, e em problemas nos quais a

informação necessária não está disponível ou se apresenta de difícil acesso, estes outros

métodos falham.

O conceito de máximo local (ou falso ótimo) acontece quando o algoritmo

converge para uma solução local e a explora até que encontre seu melhor valor, ignorando,

porém o restante do espaço de busca.

Page 29: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

29

Figura 4: Representação do Espaço de Busca de uma Função e seus mínimos local e global.

A Figura 4 retrata um exemplo onde o AG encontrou um mínimo local, também

conhecido como falso ótimo. O algoritmo convergiu para a região em vermelho, que

representa um máximo mínimo local, visto que para aquela região ela é a melhor solução,

porém não é melhor solução dentro do espaço de busca. A melhor solução do espaço de busca

é representada pela região verde. O fato do ótimo local ocorre quando o algoritmo tende a

buscar aquele ponto, ignorando as demais regiões, pois as soluções mais próximas são piores

(são os vales laterais ao pico, que representa a melhor solução local).

Ao utilizar os algoritmos genéticos para a solução de um problema, é importante

escolher os parâmetros adequados às necessidades do problema e aos recursos disponíveis.

Segundo BRAGA et al. (2000), os principais parâmetros são tamanho da

população, taxa de cruzamento, taxa de mutação e intervalo de geração.

O tamanho da população afeta o desempenho global e a eficiência dos AG. Com

uma população pequena o desempenho pode cair, pois deste modo a população fornece uma

pequena cobertura do espaço de busca do problema. Uma grande população geralmente

fornece uma cobertura representativa do domínio do problema, além de prevenir

convergências prematuras para soluções locais ao invés de globais. No entanto, para se

Solução Ótima

(mínimo global)

Resultado Falso

Ótimo

(mínimo local)

Page 30: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

30

trabalhar com grandes populações, são necessários maiores recursos computacionais, ou que o

algoritmo trabalhe por um período de tempo muito maior.

Uma taxa de cruzamento muito alta faz com que indivíduos com bons índices de

aptidão possam ser retirados a uma velocidade que supere a capacidade de gerar melhores

indivíduos. Por outro lado, se essa taxa for muito baixa, a busca pode estagnar.

Uma baixa taxa de mutação previne que uma dada posição fique estagnada em um

valor, além de possibilitar que se chegue em qualquer ponto do espaço de busca. Com uma

taxa muito alta, a busca se torna essencialmente aleatória.

O intervalo de geração controla a porcentagem da população que será substituída

para a próxima geração. Com um valor alto, a maior parte da população é substituída, o que

pode levar à perda de indivíduos de alta aptidão. Com um valor baixo, o algoritmo pode se

tornar muito lento, pois o número de gerações necessárias pode ser muito grande.

A partir de tudo que foi visto, GOLDBERG (1989) difere os AGs dos métodos

tradicionais de técnicas de busca e otimização em quatro aspectos principais:

• Os AG trabalham com uma codificação do conjunto de parâmetros e não com os

próprios parâmetros;

• Os AG trabalham com uma população de soluções candidatas simultaneamente, e

não com uma única solução;

• Os AG utilizam informações de custo ou recompensa, e não derivadas de funções;

• Os AG utilizam regras de transição probabilísticas e não determinísticas.

Os AG têm sido mais utilizados para solução de funções de otimização, nas quais

eles vêm se mostrando bastantes eficientes e confiáveis.

Porém, como é de se esperar, nem todos os problemas podem ter resultados

satisfatórios ou mesmo ser representados adequadamente para o uso de técnicas de AG.

Geralmente é necessário levantar as seguintes características relativas ao problema a ser

resolvido, antes de se tentar utilizar os AG:

• O espaço de busca (possíveis soluções) do problema em questão deve estar

delimitado dentro de certa faixa de valores.

• Deve ser possível definir uma função de aptidão (fitness) que nos indique quão

boa ou ruim é uma determinada resposta. Função esta que servirá de métrica para

a solução do problema.

Page 31: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

31

• As soluções devem poder ser codificadas de uma maneira que resulte

relativamente fácil a sua implementação no computador.

A literatura comumente cita que os AG podem ser utilizados para praticamente

todo tipo de problema, porém é sempre interessante considerar as características citadas acima

para que o desenvolvimento do processo não seja inviável ou mesmo atingir soluções

consideradas ruins.

Embora possam parecer simplistas do ponto de vista biológico, estes algoritmos

são suficientemente complexos para fornecer mecanismos de busca adaptativos, poderosos e

robustos.

2.5.1.1.1. CONCEITOS FUNDAMENTAIS DE GENÉTICA UTILIZADOS NOS AG

2.5.1.1.1.1. CROMOSSOMO OU INDIVÍDUO

Uma possível solução para o problema em questão, codificada, de acordo com um

modelo selecionado e com informações do problema a ser resolvido.

2.5.1.1.1.2. GENE

Parte de uma solução. Isto é, supondo um vetor [1, 3, 2] como uma solução

proposta para o problema, pode-se dizer que 3, que é variável deste vetor solução, é um gene,

ou seja, é o valor de uma determinada variável Xn, que faz parte de um conjunto de variáveis

da solução Si.

Page 32: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

32

2.5.1.1.1.3. FITNESS

O conceito de fitness demonstra o quão adaptável é um determinado individuo a

situação à qual ele está exposto. No caso dos AG representa o valor obtido pela função de

avaliação sobre aquele determinado indivíduo ou solução proposta.

2.5.1.1.1.4. FUNÇÃO DE AVALIAÇÃO OU FUNÇÃO DE FITNESS

É a função objetivo do problema em questão, que deve avaliar cada solução

proposta e determinar se será possível a sua permanência no grupo de soluções admissíveis

(ótimas) para o problema.

2.5.1.1.1.5. POPULAÇÃO

Conjunto de soluções propostas, presentes numa determinada etapa da execução

do AG. A população é composta por todo tipo de solução, tanto as admissíveis, quanto as

inadmissíveis.

2.5.1.1.1.6. CRUZAMENTO

Processo de “reprodução de indivíduos”, onde os indivíduos filhos (soluções

propostas pela geração seguinte) são construídos a partir de genes obtidos dos pais (soluções

propostas atuais).

Page 33: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

33

2.5.1.1.1.7. MUTAÇÃO

Processo de modificação aleatória ou guiada de um ou mais genes contidos em

uma determinada solução (cromossomo), que aplicada nos AG, visa evitar os problema de

mínimos locais e convergência rápida, diversificando os indivíduos da população corrente.

2.5.1.1.1.8. SELEÇÃO

Processo de separação dos indivíduos que possuem uma melhor resposta à função

de avaliação daqueles que não possuem boas avaliações, para que os melhores deem origem

aos indivíduos da geração seguinte.

2.5.1.1.1.9. POPULAÇÃO INICIAL

É o conjunto inicial de soluções para o problema, é o ponto de partida da

execução do AG, a partir destes indivíduos, aplicando os operadores genéticos, são gerados os

indivíduos das gerações futuras.

Geralmente esses indivíduos recebem valores aleatórios, mas caso o projetista

tenha um conhecimento considerável do problema a ser abordado ele pode fazer com que

estes indivíduos iniciais (população inicial) recebam uma gama de valores direcionados, ou

seja, recebem valores que não se apresentam absurdos ao contexto do problema.

2.5.1.1.1.10. CONDIÇÃO DE PARADA

Condição que deve ser satisfeita para que o algoritmo genético pare de executar,

condição esta, que deve ser determinada de acordo com o problema a ser resolvido.

Usualmente, esta condição é um número que representa a quantidade máxima de iterações

sobre as quais o AG deve ser executado.

Page 34: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

34

2.5.1.1.2. ESTRUTURA DO ALGORITMO

É necessário observar uma sequência de passos para a utilização de AG em

problemas de otimização e busca. Segundo BRAGA et al. (2000) um algoritmo genético deve

executar os passos apresentados a seguir:

1. Escolher um conjunto de cromossomos iniciais.

2. Repetir

2.1. Definir a nota de cada cromossomo.

2.2. Selecionar os cromossomos mais aptos.

2.3. Aplicar operadores de reprodução sobre os cromossomos

selecionados.

3. Até cromossomo adequado ser obtido ou serem realizadas N gerações.

O primeiro passo é a geração da população inicial. Em seguida deve ser realizada

a codificação ou representação, ou seja, deve ser determinado como os indivíduos serão

codificados. A codificação da informação em cromossomos é um ponto crucial dentro do AG,

e é, junto com a função de avaliação, o que liga o AG ao problema a ser resolvido. Durante o

processo evolutivo, a população é avaliada, sendo que para cada indivíduo é dada uma nota,

ou índice, refletindo sua habilidade de adaptação a um determinado ambiente.

O processo de seleção determina quais indivíduos da população podem participar

da fase de reprodução. Os indivíduos são selecionados de acordo com uma probabilidade dada

pelos índices ou notas de aptidão.

Os indivíduos escolhidos na fase de seleção participam da fase de reprodução, em

que podem ser combinados e modificados, produzindo os indivíduos da próxima geração.

Estas combinações e modificações são realizadas pelo conjunto de operadores

genéticos.

Depois de concluídas essas etapas, a nova geração formada é novamente

submetida à avaliação, e assim será feito até o ponto de parada do algoritmo.

De acordo com os passos vistos acima, o algoritmo genético em linhas gerais,

pode ser descrito pelo pseudocódigo da Figura 5.

Page 35: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

35

Figura 5: Pseudocódigo de um AG.

A Figura 6 abaixo modela exatamente a situação proposta no algoritmo.

Obviamente esta é somente uma visão de alto nível do algoritmo. O que ela esconde é a

complexidade do processo de obtenção de uma representação cromossomial que seja

adequada ao problema e de uma função de avaliação que penalize soluções implausíveis para

nosso problema e que avalie satisfatoriamente o grau de adequabilidade de cada indivíduo

como solução do problema em questão (LINDEN, 2006).

Figura 6: Fluxograma que sintetiza um algoritmo genético.

Define Pinicial

Define T = Tamanho(Pinicial)

Enquanto (condição de parada = falso)

Pf = Cruzamento_entre_individuos(Pi)

Pt = Mutação(Pi+Pf)

Pi+1 = Seleção (Pt,T)

Elimina(Pt – Pi+1)

Fim-Enquanto

Solução_Otima = Melhor_individuo (Pn)

Page 36: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

36

2.5.1.1.3. REPRESENTAÇÃO DOS CROMOSSOMOS

A representação cromossomial é de fundamental importância para os AG.

Basicamente ela consiste em uma maneira de traduzir a informação do nosso problema em

uma maneira viável de ser tratada pelo computador.

Cada pedaço indivisível desta representação é chamado de um gene por analogia

com os pedaços fundamentais que compõem um cromossomo biológico, como visto

anteriormente.

A representação ou formato de codificação dos cromossomos deve ser escolhido

cuidadosamente mediante a natureza do problema a ser resolvido, pois, a representação

cromossomial é completamente arbitrária, ficando sua definição de acordo com o gosto do

programador. É interessante apenas que algumas regras gerais sejam seguidas (LINDEN,

2006):

• A representação deve ser o mais simples possível;

• Se houver soluções proibidas ao problema, então elas não devem ter uma

representação;

• Se o problema impuser condições de algum tipo, estas devem estar implícitas

dentro da nossa representação.

A seguir serão elucidadas as abordagens de codificação existentes atualmente.

2.5.1.1.3.1. REPRESENTAÇÃO BINÁRIA

Normalmente a representação mais usada é a binária, isto é, um cromossomo nada

mais é do que uma sequência de bits e um gene é somente um bit. O que cada bit e/ou

conjunto de bits representa é inerente ao problema. Pode-se dizer que cada elemento do vetor

(cromossomo) denota a presença (bit 1) ou ausência (bit 0) de uma determinada característica.

A utilização desta representação implica na necessidade de uma função de

codificação. Esta função é responsável por transformar, os números reais para a representação

binária. Para realizar esta transformação, é necessário especificar: a faixa de operação de cada

um das variáveis do problema e a precisão numérica desejada.

Page 37: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

37

Estes dois parâmetros são responsáveis pela definição de quantos bits por variável

vamos usar. Usando k bits para uma variável mi que trabalha numa faixa [infi, supi], está-se

definindo que a precisão máxima desta variável é definida pela Equação (1) (LINDEN, 2006).

(1)

Seguindo a equação descrita acima, é possível construir o cromossomo, com

diversas variáveis reais, concatenando as strings que representam cada número, é comum para

cada número i que compõe o cromossomo, ki = ki + 1 = ... = kn, no entanto podem existir

situações em que isto não seja verdade, onde seja preciso números com precisões diferentes.

Quando é usada a representação binária é necessária a transformação do valor

binário em numérico, a fim de obter o valor do fitness. A Equação (2) pode ser utilizada para

calcular o mapeamento de um gene binário inteiro em um intervalo dos reais de ponto fixo a

fim de realizar o cálculo do fitness, considerando as mesmas constantes da Equação (1) e onde

xn corresponde ao valor binário a ser mapeado, convertido para a base decimal.

(2)

A seguir, a Figura 7 mostra um exemplo de decodificação de um número

(representado num cromossomo binário), para um número real, onde o primeiro número é

representado pelos primeiros 6 bits e o segundo, pelos 6 bits seguintes, e a faixa de cada um

deles [-2,2] e [0,1] respectivamente.

Figura 7: Representação de decodificação dos bits de um cromossomo binário em números reais.

O fato que acarreta em um consumo maior de tempo em problemas que

necessitam de uma boa precisão é a necessidade de se calcular o valor decimal da cadeia

binária que representa o cromossomo na técnica binária. Além de que nas cadeias binárias

existe a necessidade da conversão dos bits para um valor numérico. Outro problema é a

Page 38: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

38

presença de Hamming cliffs, que são grandes diferenças nas cadeias de bits que codificam

dois números inteiros próximos (GOLDBERG, 1989).

Segundo HERRERA et al. (1998), devido a estes problemas foram surgindo novas

técnicas de codificação dos cromossomos, diferentes da técnica clássica (binária) apresentada

por HOLLAND (1975).

2.5.1.1.3.2. REPRESENTAÇÃO REAL

Uma solução que foi proposta com o intuito de evitar a perda excessiva de tempo

para situações que necessitam de alta precisão foi a utilização de valores reais para se

representar os cromossomos, técnica esta que ficou conhecida como codificação real.

A codificação real é a forma de representar diretamente os parâmetros de um

problema de otimização, cria uma igualdade entre a representação interna do AG e o seu

significado no problema.

É uma representação, que, por utilizar diretamente os números em ponto-

flutuante, ela obtém o máximo de precisão numérica que o computador pode oferecer, sem

aumentar o tamanho do cromossomo.

Conforme HERRERA et al. (1998), o uso de parâmetros reais torna possível

cobrir um domínio bastante abrangente, mesmo para domínios desconhecidos, das variáveis, o

que é difícil de se conseguir trabalhando com as cadeias binárias, onde conforme o domínio

do problema vai aumentando a precisão vai caindo.

Outra vantagem em se utilizar parâmetros reais é a sua capacidade de explorar

gradualmente as funções com variáveis contínuas. Esta evolução gradual se aplica ao fato de

ligeiras mudanças nas variáveis corresponderem a ligeiras mudanças na função. Ou seja, é

interessante explorar gradualmente o domínio do problema, pois a solução obtida pode ser

melhor através de uma pequena mudança nos parâmetros. Já a codificação real não possui esta

opção de evoluir gradualmente.

Page 39: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

39

2.5.1.1.3.3. REPRESENTAÇÃO BASEADA EM ORDEM

É uma representação que delimita os valores dos genes de um cromossomo, a um

domínio discreto e específico do problema a ser resolvido.

Um exemplo clássico onde a representação em ordem é vista, é o problema do

caixeiro viajante (Travelling Salesman Problem)2, onde cada gene pode ser apenas uma das

cidades numeradas presentes no problema, e o cromossomo ou solução, é um caminho entre

estas cidades.

Este tipo de representação que será utilizada neste trabalho, onde cada gene do

cromossomo representará uma rota possível e o cromossomo representa uma possível LSP.

2.5.1.1.4. SELEÇÃO DE INDIVÍDUOS

A seleção dos indivíduos em um algoritmo genético é o processo responsável por

garantir, de uma maneira geral, uma melhoria na qualidade das soluções de cada geração do

algoritmo.

Existem diversas técnicas de seleção, segue abaixo a enumeração de algumas

delas, tidas como mais importantes.

2.5.1.1.4.1. MÉTODO DA ROLETA VICIADA

É o método mais comum de seleção utilizado nos AG, este método consiste em

distribuir as soluções de acordo com o seu fitness, numa roleta, onde as melhores soluções

têm maior probabilidade de serem escolhidas e as piores soluções podem ser escolhidas, pois

muitas vezes possuem características importantes para se garantir uma geração seguinte ainda

melhor.

2 Consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre

várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial (NILSSON, 1982).

Page 40: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

40

Figura 8: Exemplo de seleção através do método da roleta.

Durante a seleção a roleta é girada N vezes, selecionando n indivíduos para

participarem da fase de reprodução. Indivíduos com maiores notas, por possuírem áreas

maiores, têm maiores probabilidades de serem selecionados. Entretanto, a utilização da

função de avaliação para escolher os tamanhos das fatias da roleta nem sempre é a mais

adequada. Se a nota de um indivíduo for muito alta, este pode monopolizar a seleção, levando

a uma seleção prematura do algoritmo genético. Se por outro lado, os valores de aptidão dos

indivíduos forem muito próximos, as suas fatias nas roletas serão aproximadamente iguais.

Isto leva a possibilidade da seleção não favorecer os indivíduos mais aptos. Uma solução para

estes problemas é a utilização da técnica de ranking. Nesta técnica, a fatia é definida não pela

nota relativa de cada indivíduo, mas pela posição que eles ocupam no ranking de todas as

notas (BRAGA et al., 2000). Na técnica de ranking, a fatia de cada indivíduo é definida por

meio da escolha de um valor no intervalo entre 0,0 e 1,0. Desta forma, em ordem decrescente

de ranking, cada indivíduo, ocupa da área total da roleta que ainda não foi ocupada, uma fatia

proporcional ao valor escolhido.

2.5.1.1.4.2. MÉTODO DO TORNEIO

Este método busca uma convergência rápida, visto que dos n indivíduos/soluções

presentes em uma determinada geração da execução do algoritmo são escolhidos k indivíduos,

que disputam entre si, e sempre os indivíduos de melhor avaliação são preservados. Esta

técnica executa rápida convergência, no entanto ocorre com mais frequência dela caminhar

para um mínimo/máximo local.

Page 41: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

41

2.5.1.1.4.3. MÉTODO DE AMOSTRAGEM ESTOCÁSTICA UNIFORME

Neste método é construída uma linha, mapeando todos os indivíduos para

seguimentos contíguos, onde o tamanho de cada segmento é representado pelo fitness daquela

solução, os segmentos devem ser normalizados, de forma em que sua soma é 1. Em seguida, é

sorteado um número i entre 0 e

.

Então, os indivíduos que estão nas posições (

( )

)

são escolhidos pelo algoritmo de seleção para a aplicação dos operadores genéticos. Apesar

de ser parecido com o método da roleta viciada, este método de seleção evita o problema

ocasionado por um gerador de números aleatórios ineficiente.

2.5.1.1.5. OPERADORES GENÉTICOS

Os indivíduos escolhidos na fase de seleção participam da fase de reprodução, em

que podem ser combinados ou modificados, produzindo os indivíduos da próxima geração.

A construção de gerações futuras nos AG se dá através de dois operadores

genéticos fundamentais para a sua execução, cruzamento (ou crossover) e mutação.

2.5.1.1.5.1. CRUZAMENTO

O cruzamento é a utilização de soluções já existentes para dar origem à próxima

geração de soluções para a próxima geração, este processo juntamente com o processo de

seleção é responsável por manter constante a evolução das soluções.

A ideia principal do cruzamento é propagar as características positivas dos

indivíduos mais aptos da população através da troca de segmentos de informações entre os

mesmos, o que originará novos indivíduos.

Os indivíduos eleitos na etapa de seleção são embaralhados aleatoriamente

criando-se, desta forma, uma segunda lista, chamada lista de parceiros. Cada indivíduo

Page 42: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

42

selecionado será então cruzado com o indivíduo que ocupa a mesma posição na lista de

parceiros. Os cromossomos de cada par de indivíduos a serem cruzados são particionados em

um ou mais pontos, chamados pontos de corte, sorteados aleatoriamente. Um ponto de corte

constitui uma posição entre dois genes de um cromossomo. Um novo cromossomo é gerado

permutando-se a parte de um cromossomo com a mesma parte do outro cromossomo.

Cada indivíduo de n genes contém n-1 pontos de corte, e cada um desses pontos

corte é o ponto de separação entre cada um dos genes que compõem o material genético de

cada pai.

Ele é considerado o operador genético predominante por isso é aplicado com uma

probabilidade, taxa de cruzamento, maior que a taxa de mutação.

O cruzamento pode se tornar um pouco mais complexo, dependendo

principalmente da codificação dos cromossomos. Cruzamentos específicos feitos para

problemas específicos podem melhorar o desempenho dos algoritmos genéticos.

Existem diversas técnicas de cruzamento, as mais utilizadas são: cruzamento de

um ponto, de dois pontos e uniforme, que podem ser utilizados tanto em cromossomos com

codificação binária como em ponto flutuante. Porém existem operadores de cruzamento

específicos para uso com codificação em ponto flutuante, são os chamados operadores de

cruzamento aritméticos. Alguns exemplos de operadores de cruzamento aritméticos são:

média, média geométrica, aritmético e heurístico. Não é objetivo deste trabalho aprofundar-se

nestas técnicas de cruzamento aritméticos.

2.5.1.1.5.1.1. CRUZAMENTO DE UM PONTO

A operação deste operador é extremamente simples e foi o primeiro cruzamento

proposto por HOLLAND (1975). Depois de selecionados dois pais pelo módulo de seleção de

pais, um ponto de corte é selecionado. Depois de sorteado o ponto de corte, deve-se separar os

pais em duas partes: uma à esquerda do ponto de corte e outra à direita.

O primeiro filho é composto através da concatenação da parte esquerda do

primeiro pai e com a parte direita do segundo pai. O segundo filho é composto através da

concatenação das metades que sobraram (a metade esquerda do segundo pai com a metade à

direita do primeiro pai), esse tipo de operação pode ser visualizado na Figura 9.

Page 43: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

43

Existem vários esquemas que o crossover de um ponto não consegue preservar,

portanto, devemos cogitar a possibilidade de utilizar outros operadores de cruzamento para

que o AG não fique limitado na sua capacidade de processar esquemas.

Figura 9: Exemplificação de um Cruzamento de um ponto.

2.5.1.1.5.1.2. CRUZAMENTO DE DOIS PONTOS

Para melhorar a capacidade do processamento de esquemas, pode-se introduzir o

crossover de dois pontos. Seu funcionamento, que podemos ver na Figura 10, é similar ao do

crossover de um ponto, com a diferença que em vez de sortearmos um só ponto de corte,

sorteamos dois. O primeiro filho será então formado pela parte do primeiro pai externo aos

pontos de corte, e pela parte do segundo pai entre os pontos de corte e segundo filho será

formado pelas partes restantes.

Figura 10: Exemplificação de um Cruzamento de dois pontos.

Page 44: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

44

Obviamente a operação do crossover de dois pontos é ligeiramente mais

complexa do que a operação do seu equivalente de um só ponto, mas a diferença de

desempenho conseguida, em geral, faz com que o custo extra seja válido, pois o número de

esquemas que podem ser efetivamente transferidos aos descendentes usando-se este operador

aumenta de forma considerável.

2.5.1.1.5.1.3. CRUZAMENTO UNIFORME

Apesar dos cruzamentos de um e dois pontos serem capazes de combinar vários

esquemas, existem alguns esquemas que eles podem não ser capazes de manter. Por isto, foi

desenvolvido o cruzamento uniforme, que é capaz de combinar praticamente todo e qualquer

esquema existente.

O funcionamento do crossover uniforme, conforme mostrado na Figura 11,

consiste em: para cada gene é sorteado um número (0 ou 1), se o sorteado for 1 (um), o

primeiro filho recebe o gene do primeiro pai e o segundo filho o gene do segundo pai, e se o

sorteado for 0 (zero), o primeiro filho recebe o gene do segundo pai e o segundo filho recebe

o gene do primeiro pai (LINDEN, 2006).

Figura 11: Exemplificação de um Cruzamento uniforme.

Uma característica interessante do crossover uniforme é que ao contrário dos seus

predecessores, que tendiam a quebrar esquemas de maior comprimento, esse tende a

conservar esquemas longos com a mesma probabilidade que preserva esquemas de menor

comprimento.

1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1

0 0 1 1 1 0 0 1

0 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1

Vetor de combinação

DESCENDENTES

PAIS

Page 45: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

45

2.5.1.1.5.2. MUTAÇÃO

A mutação é o processo de modificação aleatória e/ou guiada de um ou mais

genes de um ou mais indivíduos, e responsável pela introdução e manutenção da diversidade

genética da população (HOLLAND, 1975) ou mesmo restaurar características que se

perderam em outras operações, como, por exemplo, de cruzamento, tentando evitar que o

algoritmo tenha rápida convergência para um mínimo/máximo local. Assim, a mutação

assegura que a probabilidade de se chegar a qualquer ponto do espaço de busca nunca será

zero.

O operador de mutação é aplicado aos indivíduos com uma probabilidade dada

por uma taxa de mutação definida pelo projetista, taxa esta que é geralmente bem baixa, sendo

os valores comumente usados dentro da faixa de 0,001 a 0,02. O cromossomo tem todos seus

genes percorridos. Caso a taxa de mutação seja maior que o valor sorteado pelo gene então

este sofrerá mutação.

Tabela 1

Exemplo do operador de Mutação (taxa de mutação = 0,003)

Cromossomo

original Números Aleatórios

Novo

bit

Cromossomo

novo

0 1 1 1 0,653 0,001 0,287 0,373 0 0 0 1 1

1 1 1 0 0,721 0,432 0,004 0,84 - 1 1 1 0

1 0 1 0 0,002 0,076 0,934 0,471 0 0 0 1 0

Fonte própria

Pode acontecer de um cromossomo possuir vários genes alterados pela mutação

ou mesmo não apresentar nenhuma alteração, caso o valor sorteado seja sempre maior que a

taxa de mutação fornecida pelo projetista.

Considerando a codificação binária, o operador de mutação padrão simplesmente

troca o valor de um gene em um cromossomo (HOLLAND, 1992). Assim, se um gene

selecionado para mutação tem valor 1, o seu valor passará a ser 0 após a aplicação da

mutação, e vice versa.

No caso de problemas com codificação em ponto flutuante, os operadores de

mutação mais populares são a mutação uniforme, mutação gaussiana e mutação não-uniforme

Page 46: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

46

(MICHALEWICZ; SCHOENAUER, 1996). Porém, não é objetivo deste trabalho aprofundar-

se nestas técnicas de mutação.

2.5.1.1.5.3. INVERSÃO

HOLLAND (1975) cita um terceiro operador genético, a inversão. Esse operador

é considerado como secundário para os AG e foi criado com a finalidade de evitar que bons

esquemas se rompam durante o cruzamento.

O objetivo é reordenar a estrutura cromossômica para fortalecer o enlace entre

caracteres fixos de esquemas de grande comprimento de definição, antes de aplicar o

cruzamento.

Segundo VASCONCELOS et al. (1995) o efeito da inversão em um código

genético não é claro e nem de fácil entendimento como os operadores mutação e cruzamento.

Para DAVIS (1991), o operador de inversão traz consigo um custo computacional adicional

aos AG que o inviabiliza na prática. Assim sendo, este operador não será mais alvo de estudos

nesse trabalho, estando aqui apresentado apenas para completar a descrição dos operadores

genéticos.

2.5.1.1.6. CONSTRUÇÃO E CONVERGÊNCIA DAS GERAÇÕES

O desempenho de um algoritmo genético está diretamente ligado ao tamanho da

sua população, que não deve ser grande demais, por questões de desempenho ao realizar as

operações, mas também não deve ser pequena demais, pois deve obter uma boa diversidade

de soluções.

A construção das gerações num AG pode ocorrer de diversas formas, o algoritmo

pode estar programado para fazer com que o número de indivíduos seja constante em todas as

gerações, este número pode aumentar ou diminuir de acordo com uma determinada

necessidade, e além da questão tamanho da população, é possível guiar as gerações futuras,

criando superindivíduos, ou até mesmo realizando mortes/nascimentos de indivíduos de

Page 47: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

47

forma independentes, não somente esperando o fim de uma geração para surgirem novas

soluções.

Após a aplicação dos operadores genéticos, pode acontecer que os indivíduos de

uma nova geração não apresentem melhores resultados que o melhor da geração anterior. Se

isso ocorrer, o valor da função de aptidão cai do patamar que já havia alcançado. Outro

problema surge em gerações mais avançadas, onde a população contém várias cópias de bons

indivíduos. Se por acaso surgir um indivíduo melhor que os atuais, este corre o risco de não

ser selecionado, justamente pela grande probabilidade proporcionada aos indivíduos com mais

cópias.

2.5.1.1.7. CRITÉRIOS DE CONVERGÊNCIA

A convergência acontece de acordo com um critério pré-determinado. Se a

aptidão requerida é conhecida, pode-se trabalhar com a opção de um erro máximo admissível.

Desta forma, assim que os AG encontrarem um indivíduo que proporcione um erro menor que

o estipulado, finaliza-se o processo.

Outro método interessante de testar a convergência é através da diversidade

genética da população. Se os indivíduos estão muito parecidos entre si, ou seja, se a avaliação

da equação de mérito de cada indivíduo der resultados muito próximos, pode significar que

eles estejam na mesma região. Isto caracteriza a presença de um máximo ou mínimo da

função.

Um controle final deve ser feito de maneira obrigatória, pois não se pode ficar

simulando indefinidamente. Este controle pode ser realizado, por exemplo, estipulando um

número máximo de gerações admissível.

Todas estas metodologias possuem falhas. A convergência por diversidade

genética falha quando os AGs convergem para um mínimo local, ou seja, quando acontece

convergência prematura. Já o número máximo de gerações falha quando não se dá tempo

suficiente ao algoritmo para investigar todo o universo de busca. Uma metodologia inteligente

para ser adotada seria a utilização racional destas duas citadas. Por exemplo, se ao final do

processo evolutivo a diversidade genética ainda for elevada, pode-se permitir que o número

de gerações seja estendido.

Page 48: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

48

2.5.1.1.8. ELITISMO

Para melhorar a convergência dos AG foi desenvolvida uma técnica chamada

elitismo. O elitismo é a técnica mais utilizada para melhorar a convergência destes algoritmos.

Ele foi primeiramente introduzido por Kenneth De Jong, em 1975, e é uma adição aos

métodos de seleção que força os AG a reter certo número de "melhores" indivíduos em cada

geração (YEPES, 2000). Tais indivíduos podem ser perdidos se não forem selecionados para

reprodução ou se forem destruídos por cruzamento ou mutação.

Em outras palavras, o elitismo seleciona os melhores cromossomos de uma

população e transporta-os à geração seguinte. Esta técnica consiste basicamente em realizar o

processo de seleção em duas etapas:

a) Seleciona-se uma elite de r membros entre os melhores da população inicial, os

quais são incorporados diretamente na população final;

b) O restante da população final é obtida a partir dos (n - r) elementos restantes da

população inicial de tamanho n.

Em geral a elite tem um tamanho reduzido, com r = 1 ou 2 para um n = 50 por

exemplo.

O elitismo quase não altera o tempo de processamento, mas garante que a

desempenho do AG esteja sempre crescendo com o decorrer das gerações.

Visto que a maioria dos esquemas de avaliação de desempenho de um AG mede

apenas a adequação da melhor solução dentre todos os indivíduos, a manutenção do melhor

indivíduo da geração k na população da geração k+1 garante que o melhor indivíduo da

geração k+1 é pelo menos igual que o melhor indivíduo da geração k (no pior caso, em que

nenhum indivíduo melhor é criado).

O overhead de processamento é realmente muito pequeno, visto que já existe a

necessidade de determinar a avaliação de cada indivíduo para aplicação da seleção, logo basta

que armazenar o índice do melhor indivíduo e o módulo de população encarregar-se-á de

copiá-lo para a próxima geração. Quando essa técnica é utilizada, o algoritmo converge mais

rapidamente.

Como na natureza, os indivíduos mais aptos podem, além de reproduzir-se mais,

ter uma vida mais longa, muitas vezes sobrevivendo de uma geração para a outra e se

reproduzindo. O efeito negativo desta estratégia prende-se ao fato de que a população inicial

Page 49: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

49

pode convergir para uma população homogênea de superindivíduos (convergência

prematura), não explorando outras soluções.

O elitismo é utilizado da mesma forma, tanto na codificação real quanto na

codificação clássica.

2.5.1.1.9. ESCALONAMENTO

Entre os métodos de seleção mais utilizados está o da roleta. Este método de

seleção pode em alguns casos conduzir os AG para a convergência prematura. Isto acontece

porque, quando da criação dos indivíduos, geralmente eles possuem um valor de aptidão

baixo. Quando entre estes indivíduos aparece um com aptidão muito alta, pode acontecer que

muitas cópias dele sejam criadas. Isto é, ele ocupará uma área muito grande na roleta e,

consequentemente poderá ser selecionado muitas vezes. Se este indivíduo corresponder a um

mínimo ou máximo local, a probabilidade de se ficar preso nesta região será alta.

Para evitar este problema uma saída seria fazer o escalonamento da população,

que consiste em limitar o número de cópias de um mesmo indivíduo na próxima geração

(GOLDBERG, 1989).

2.5.1.1.10. VARIAÇÃO DINÂMICA DE PROBABILIDADES

A variação dinâmica de probabilidades tem o mesmo objetivo do escalonamento,

ou seja, evitar a convergência prematura. O que esta ferramenta faz é utilizar a medida de

diversidade genética da população para medir o grau de semelhança entre os indivíduos. Se o

grau de semelhança for alto, alteram-se as probabilidades de cruzamento e mutação.

Especificamente, reduz-se o cruzamento e aumenta-se a mutação, aumentando-se assim a

inserção de material genético novo na população. Se a situação for contrária, ou seja, se os

indivíduos estiverem muito dispersos, aumenta-se o cruzamento e reduz-se a mutação.

Os valores das probabilidades de cruzamento e mutação são modificados

observando diversidade genética mdg da população, ffmed que é o desempenho médio da

população e ffmax o melhor resultado da população, e estão expressos na Equação (3).

Page 50: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

50

(3)

Se mdg é próximo da unidade, significa que há pouca diversidade, e muita, quando

ele se aproxima de zero.

2.5.1.1.11. FORMAÇÃO DE NICHOS

Na natureza, define-se nicho como uma pequena parte do ambiente onde as

populações vivem relativamente isoladas. Por isso, acabam adquirindo características

próprias, formando subespécies. Este isolamento pode melhorar o processo de evolução.

Nos AG é possível utilizar o mesmo conceito. Pode-se trabalhar com

subpopulações, ocasionando assim o aparecimento e o desenvolvimento de características

próprias e novas. Isto é interessante, pois se estaria explorando melhor diferentes áreas do

universo de busca, aumentando assim o conhecimento a respeito do problema.

Existem técnicas bem conhecidas para a implementação desta ferramenta. As mais

utilizadas são a função de partilha (GOLDBERG, 1989) e o SSS (Simple Subpopulation

Schemes), proposto por SPEARS (1994).

A função de partilha mede o “grau de vizinhança”, ou seja, quantifica a

proximidade de um indivíduo em relação aos outros no universo de busca. Neste caso, o

operador de seleção analisaria o indivíduo por sua aptidão aparente, relativa somente à

aptidão de seus vizinhos, ou seja, de uma subpopulação local.

Já o SSS consiste em criar subpopulações desde o início do processo, de modo

que cada indivíduo da população receba uma “etiqueta” que indica a qual subpopulação

pertence. Da mesma forma que ocorre com a função partilha de Goldberg, os indivíduos são

selecionados de acordo com sua aptidão aparente.

Page 51: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

51

2.5.1.1.12. REDUÇÃO DO ESPAÇO DE BUSCA

À medida que o número de gerações vai sucedendo e que a população vai

melhorando, caminha-se na direção do objetivo. Para se encurtar este caminho, utiliza-se a

redução do espaço de busca.

Esta redução é feita do seguinte modo: primeiramente seleciona-se o melhor

indivíduo da população corrente. A partir deste indivíduo obtém-se uma nova população

fazendo pequenas perturbações aleatórias em suas variáveis, gerando assim novos indivíduos.

Com isto, passa-se a explorar somente a região onde está inserido o melhor indivíduo.

Deve-se tomar o cuidado de só começar a fazer as reduções do espaço de busca no

final do processo de gerações, quando a população já se organizou em torno do objetivo.

Se isto não for respeitado, o risco da convergência prematura será grande.

2.5.1.1.13. PROBLEMAS DE OTIMIZAÇÃO COM RESTRIÇÕES

A grande maioria dos problemas de otimização na prática, estão sujeitos as

restrições, restrições estas que podem ser de origem física, econômica, geográfica e etc.

O algoritmo genético deve ser capaz de lidar com as restrições, para a resolução

de um determinado problema, visto que a ausência das restrições ou o descumprimento delas

por parte do modelo de problema desenvolvido pode torná-lo inválido.

No ramo dos algoritmos genéticos problemas com restrições são denominados

problemas de otimização multi-objetivo, ou seja, além da função objetivo, todas as restrições

são tratadas como funções objetivo, fazendo que os indivíduos que não respeitem a todas elas,

sejam considerados como soluções inadmissíveis.

Num problema de otimização, as restrições são caracterizadas como restrições

rígidas (hard-constraints), que são as restrições que necessariamente devem ser obedecidas,

caso contrário o modelo é inválido, e as restrições suaves (soft-constraints), que

preferencialmente devem ser obedecida, no entanto a não obediência de uma restrição suave

não invalida uma solução do problema.

Page 52: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

52

2.5.2. INTELIGÊNCIA COLETIVA

O termo Inteligência Coletiva ou Swarm Intelligence (SI) foi empregado pela

primeira vez em 1988 por BENI (1988), para descrever um sistema robótico celular, no qual

agentes simples se organizaram através do conceito do vizinho mais próximo.

Uma definição mais geral, feita por BONABEAU et al. (1999), é: “Inteligência

Coletiva é qualquer tentativa de projetar algoritmos ou dispositivos distribuídos de resolução

de problemas inspirados no comportamento coletivo das colônias de insetos sociais e de

outras sociedades animais.”

Individualmente, os insetos sociais têm capacidade de memória limitada e são

capazes apenas de realizar tarefas simples. Entretanto, de acordo com HÖLLDOBLER &

WILSON (1994) e FRANKS (1989), o comportamento coletivo de uma colônia de insetos

sociais é capaz de prover soluções inteligentes a diversos problemas, como:

• Carregar grandes objetos;

• Formar pontes;

• Encontrar o caminho mais curto entre a fonte de alimento e o ninho;

• Criação e manutenção do ninho;

• Regular a temperatura do ninho com precisão de até 1°C;

• Dar preferência à fonte de comida mais rica disponível.

Um inseto social não tem conhecimento sobre como a tarefa que realiza afeta a

colônia. Suas ações são baseadas em decisões locais, utilizando-se de conhecimentos

primitivos e com resultados, geralmente, imprevisíveis. O comportamento inteligente da

colônia nasce como uma consequência da organização das tarefas e do cruzamento de

informações dos diversos insetos.

De acordo com GAERTNER (2004), cientistas estudam estes tipos de espécies

que se auto organizam para tentar entender como regras tão simples podem levar a um sistema

de comportamento tão complexo. Através de modelos abstratos que imitam esse tipo de

comportamento, diversas aplicações dotadas de Inteligência Coletiva são introduzidas no

nosso dia-a-dia.

A Inteligência Coletiva, na maioria das vezes, segue alguns princípios básicos:

Page 53: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

53

• É necessário certo número de agentes para que o sistema atue de forma

inteligente;

• Interações aleatórias entre os agentes são necessárias para mudar o sistema de

forma global.

Nas formigas, as interações entre os agentes são feitas de forma indireta, através

do feromônio. As abelhas, por outro lado, se comunicam através de uma forma de dança

rítmica, que indica, para as abelhas ociosas, a direção e a distância em que o alimento se

encontra. Quanto maior a duração e mais frequente a dança é feita, melhor é a fonte de

comida. Mesmo que as abelhas só vejam uma única dança antes de partirem rumo ao alimento

e, além do mais, tendo em vista a inexistência de um dispositivo que determine o controle

central da qualidade do alimento encontrado por todas elas, ainda assim os agentes coletivos

são capazes de perceber as diferenças no ambiente e aperfeiçoar a coleta de comida.

É também conhecido como sinergia esse comportamento de trabalho ou esforço

conjunto de vários subsistemas para realização de uma tarefa complexa. De forma genérica,

pode ser definido como o efeito resultante da ação de vários agentes, que atuam da mesma

forma, tendo valor da ação conjunta resultante mais significativo que a mera atuação

individual.

2.5.2.1. COLÔNIA DE FORMIGAS

As formigas são insetos sociais que possuem um complexo sistema de

organização e divisão de tarefas, tendo como função principal a garantia da sobrevivência do

formigueiro. Organismos aparentemente simples, formigas podem lidar com tarefas

complexas agindo coletivamente.

Em uma colônia de formigas, cada uma delas é um indivíduo independente agindo

sem a presença de uma autoridade ou outro indivíduo que coordene suas atividades. Esta

característica é apropriada para o desenvolvimento de um algoritmo distribuído. Isso porque,

cada indivíduo pode ser representado por um processo distinto e independente. Mesmo com

uma anarquia aparente, pela ausência de um controle centralizado, a colônia de formigas

possui uma organização, como se existisse um governo central.

Page 54: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

54

Os indivíduos (operários) de uma colônia de formigas (DORIGO, 1992),

normalmente, só realizam um conjunto de tarefas definido de acordo com determinadas

condições. Podemos citar como exemplo, entre as várias condições, a morfologia e a idade do

indivíduo. Pode-se dizer que é mais eficiente a divisão de trabalho entre os indivíduos da

colônia, onde diferentes atividades são realizadas, simultaneamente, por grupos de indivíduos

especializados, do que se as mesmas tarefas fossem realizadas por indivíduos não

especializados e de forma sequencial.

A capacidade de organização e de especialização encontrada nas colônias de

formigas soluciona vários dos seus problemas diários. Esses problemas incluem basicamente

encontrar comida, alimentar a população, dividir as tarefas eficientemente entre os indivíduos,

além de responder a mudanças externas entre outros.

Muitos desses problemas são semelhantes aos encontrados nas Engenharias ou na

Ciência da Computação. Uma das características mais importantes destes indivíduos é

capacidade de poder solucionar seus problemas de forma flexível e robusta.

A partir de estudos de Inteligência Coletiva desenvolveu-se uma metaheurística,

chamada de Ant Colony Optimization (ACO). Esta metaheurística, originada nos trabalhos de

DORIGO et al. (1991) que propôs o algoritmo Ant System (AS) para solucionar o Problema

do Caixeiro Viajante, é baseada no comportamento de colônia de formigas. A resolução de

problemas por uma colônia de formigas emerge da comunicação indireta de cada formiga com

o ambiente.

A metaheurística ACO inspirou-se numa experiência com formigas reais que

consistiu na submissão de uma colônia de formigas Iridomyrmex humilis a uma fonte de

alimento através de dois caminhos distintos (GOSS et al., 1989), um caminho utilizando duas

pontes de mesmo comprimento conforme exemplifica a Figura 12 e o outro caminho utilizava

duas pontes de comprimentos diferentes conforme ilustra a Figura 13.

Inicialmente, elas exploram, aleatoriamente, a área ao redor do formigueiro à

procura de comida. Enquanto se deslocam, depositam sobre o solo uma substância volátil

chamada feromônio (designação genérica de substâncias secretadas pelas formigas que

servem de meio de comunicação entre elas), que as auxilia a encontrar o caminho de volta ao

formigueiro. Desta forma, quando uma formiga estabelece uma trilha ou caminho entre a

fonte de alimento e o formigueiro, o caminho percorrido ficará marcado por um rastro desta

substância. As demais formigas à procura de alimento detectam a presença de feromônio no

solo e tendem a escolher o caminho com a maior concentração do mesmo, este processo

Page 55: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

55

descrito até agora é chamado de estigmergia (do inglês stigmergy)3. As formigas que

escolheram o caminho mais curto farão o percurso em menor tempo e o rastro de feromônio

será reforçado com uma frequência maior que nos caminhos mais longos. Assim, os caminhos

mais eficientes, ou seja, de menor distância percorrida, receberão maior quantidade de

feromônio e tenderão a serem os mais escolhidos. Por ser uma substância volátil, a

evaporação do feromônio evita que, com o tempo, um caminho que não esteja sendo mais

utilizado continue a influenciar a decisão das formigas. Por este processo de busca, formigas

são capazes de encontrar o menor caminho de uma fonte de comida para o seu ninho

(DORIGO & GAMBARDELLA, 1997).

A essência dos algoritmos ACO é a combinação de informações sobre a estrutura

do problema, conhecidas a priori e imutáveis, com as informações obtidas a partir dos

resultados gerados, conhecidas a posteriori e dinâmicas. Esta combinação de informações

ajuda na convergência dos resultados e torna o processo auto-catalítico, ou seja, se alimenta

dos próprios dados gerados. Outra grande vantagem dos algoritmos ACO é a facilidade com

que pode ser paralelizado computacionalmente.

Figura 12: Exemplo do caminho entre o ninho e a fonte de alimento usando duas pontes de comprimento idênticas na

experiência com formigas reais (GOSS et al., 1989).

3 São as formas de interações indiretas entre os indivíduos de uma colônia que ocorrem quando um deles

modifica de alguma forma o ambiente e, algum tempo depois, outro indivíduo responde a essa modificação.

Page 56: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

56

Figura 13: Exemplo do caminho entre o ninho e a fonte de alimento usando duas pontes de comprimento diferentes na

experiência com formigas reais (GOSS et al., 1989).

Podem-se determinar as seguintes características desta metaheurística:

• É um algoritmo não determinístico baseado em mecanismos presentes na

natureza, isto é, baseado no comportamento de formigas para determinação de

caminhos para procura eficiente de fontes de alimento;

• É um algoritmo paralelo e adaptativo, pois uma população de formigas move-se

simultaneamente, de forma independente;

• É um algoritmo cooperativo, pois cada formiga escolhe um caminho com base na

informação (feromônio) depositada por outras formigas que tenham selecionado

previamente o mesmo caminho.

De acordo com BONABEAU et al. (1999), os algoritmos baseados em Colônia de

Formigas são um dos mais bem sucedidos exemplos de Inteligência Coletiva e têm sido

aplicado em diversas classes de problemas combinatoriais, como, o problema do caixeiro

viajante, problema do quadrático de alocação, problema de agendamento (scheduling),

roteamento de veículos, roteamento de redes, coloração de grafos, etc. Enfim, qualquer

problema cujos componentes de solução possam ser modelados com um grafo completamente

conectado pode ser resolvido com grandes chances de sucesso pelos algoritmos de ACO.

Page 57: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

57

2.5.2.1.1. IMPLEMENTAÇÃO E MODELAGEM MATEMÁTICA

A ACO foi desenvolvida para tratar de problemas em que se deseja descobrir o

caminho de custo mínimo em um grafo G = (C, L, W), contanto que estes caminhos sejam

viáveis segundo as restrições (C, L, θ), definidas abaixo.

O grafo G = (C, L, W) e as restrições (C, L, θ), que juntos representam de

maneira geral um problema de otimização discreto, são definidos da seguinte forma

(DORIGO & CARO, 1999):

• C = {c1, c2,..., } é conjunto finito de nc componentes do problema, conjunto

de nós do grafo;

• L = { | ci , cj C} é o conjunto finito de possíveis arrestas entre os

elementos de C;

• W é o conjunto de pesos associados, ou a C ou a L, ou a ambos. Por exemplo, a

distância dij das arestas (i, j) L;

• (C, L, θ) é o conjunto finito de restrições atribuídas aos elementos de C e L,

com θ indicando que mudanças de restrição poderão ocorrer ao longo do tempo. Por exemplo,

determinar que cada nó possa ser visitado uma única vez;

• Os estados do problema são definidos por seqüências s = <a1, a2,..., ak,...>,

com ai = ck C, k = 1,..., nc;

• Caso c1 seja o último componente do estado s1, então um estado s2 é dito

vizinho a s1, se somente se, c2 C | ( L) (s2 = <s1, c2>);

• Caso a sequência s = <a1, a2,..., ak>, (ai, ai+1) L, seja viável por satisfazer

as restrições (C, L, θ), então esta sequência constituirá uma solução viável do problema

abordado;

• S é conjunto de todas as soluções viáveis do problema;

• A cada solução viável está associado um custo J() dado em função dos

custos J( , θ) das arrestas , ou dos custos J(ci, θ) dos componentes ci C, ou de

ambos.

Em um algoritmo ACO, as formigas constroem soluções para o problema

representado por G e de forma incremental. Cada formiga k parte de uma solução parcial

k(1) composta de um único elemento pertencente a C, e segue adicionando novos elementos

Page 58: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

58

a k(h) até alcançar uma solução viável . A notação k(h) representa a solução atual parcial

construída em h passos pela formiga k, logo composta por h elementos pertencentes a C. Os

componentes candidatos à adição em k(h) são aleatoriamente selecionados a partir de uma

vizinhança apropriadamente definida em torno do último elemento de k(h). Esta escolha

aleatória e feita aplicando-se uma política de decisão que faz uso de informações locais

relacionadas aos vértices e/ou conexões visitadas. Após construir, ou enquanto constrói, a

solução viável , a formiga deposita feromônio sobre os componentes e/ou arestas visitadas,

segundo a qualidade da solução encontrada, ou que vem sendo encontrada. Este feromônio

depositado pela formiga é o que influenciará a construção da solução dos demais.

O método de otimização baseado em colônia de formigas leva em conta as

seguintes considerações (DORIGO & CARO, 1999):

1. A meta de uma formiga é a busca por soluções viáveis de custo J()

mínimo;

2. Uma formiga k tem uma memória Mk que armazena o caminho até então

percorrido. A memória pode ser usada para: (i) construir soluções viáveis; (ii) avaliar a

solução encontrada; e (iii) retornar pelo mesmo caminho percorrido;

3. Uma formiga k no estado sr = <sr-1, i> pode mover-se para qualquer nó j,

contanto que este nó pertença à vizinhança Ni do nó i em que se encontra. Além disso, a

viabilidade com o estado sr deve ser mantida. Ou seja, j deve pertencer a sendo

= {j |

(j Ni) (<sr, j> S)};

4. Uma formiga k sobre o nó i seleciona o nó j segundo uma regra de

decisão probabilística;

5. Pode-se atribuir um estado inicial a uma formiga k, assim como uma ou

mais condições ek de parada;

6. As formigas partem de seus respectivos estados iniciais em direção a um

estado vizinho viável, e assim sucessivamente, até que pelo menos uma condição de parada ek

seja alcançada por alguma formiga k;

7. À medida que se move do nó i para seu vizinho j, a formiga pode atualizar a

trilha de feromônio ij sobre a aresta (i, j). Este processo denomina-se atualização de

feromônio passo-a-passo (online step-by-step pheromone update);

8. Uma vez construída uma solução, a formiga pode, ao retornar pelo caminho

inverso ao percorrido, atualizar a trilha de feromônio. Este processo denomina-se atualização

de feromônio com atraso (online delayed pheromone update).

Page 59: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

59

Para SOCHA & DORIGO (2008), o ACO consiste de três algoritmos que formam

a construção do ScheduleActivities (agendamento de atividades). O pseudocódigo que

descreve a metaheurística ACO está descrito na Figura 14.

Figura 14: Pseudocódigo da metaheurística ACO.

2.5.2.1.2. CONSTRUÇÃO DE SOLUÇÕES (CONSTRUCT ANT SOLUTIONS)

Um conjunto de m formigas artificiais constroem soluções a partir de elementos

de um conjunto finito de soluções disponíveis em C = {cij}; i = 1, ... ,n; j = 1, ... ,|Di|. A

construção das soluções começa com uma solução parcial vazia sp = Ø. Então, a cada passo

da construção, a solução parcial atual sp é estendida pela adição de um componente da solução

viável a partir do conjunto de vizinhos viáveis N(sp) C. O processo de construção de

soluções pode ser considerado como um caminho para a construção do grafo G (C, L). Os

caminhos permitidos em G são implicitamente definidos pelo mecanismo de construção da

solução que define o conjunto N(sp) com relação a uma solução parcial s

p.

A escolha de um componente da solução N(sp) é feito probabilisticamente em

cada etapa da construção com base na informação de feromônio e na informação heurística.

As regras exatas para a escolha probabilística de componentes da solução variam entre as

diferentes versões da ACO.

2.5.2.1.3. AÇÕES GLOBAIS (DAEMON ACTIONS)

Uma vez que as soluções foram construídas, e antes de atualizar os valores de

feromônio, muitas vezes, algumas ações específicas de problemas podem ser necessárias.

Estas são chamadas Ações Globais ou DaemonActions, e podem ser usadas para implementar

Iniciar parâmetros, iniciar rastros de feromônio

Agendar Atividades

Construção de Soluções

Ações Globais [Opcional]

Atualização dos Feromônios

Fim do Agendamento

Page 60: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

60

um problema específico e/ou ações centralizadas, o que não pode ser realizado por uma única

formiga. Essa fase é opcional. As ações globais mais utilizadas consistem na aplicação de

uma busca local para a construção de soluções: as soluções localmente otimizadas são então

utilizadas para decidir quais os valores de feromônio para atualização.

2.5.2.1.4. ATUALIZAÇÃO DOS FEROMÔNIOS (UPDATE PHEROMONES)

Essa etapa envolve tanto o depósito de feromônio, quanto a evaporação de

feromônio. As formigas podem depositar feromônio após cada passo da construção, o que

acontece na fase de construção da solução. No entanto, a formiga também pode depositar

feromônio após construir uma solução completa, o que pode ser feito nesta terceira fase do

algoritmo. Além disso, para evitar uma convergência muito precoce do ACO, ou que ele fique

preso em um ótimo local, o feromônio depositado deve evaporar ao longo do tempo. Essa

atividade também é realizada nesta etapa e através dela obtemos um efeito de diversificação.

Diferentes algoritmos de ACO utilizam diferentes maneiras de atualização do

feromônio.

2.5.2.1.5. COMPARAÇÃO ENTRE FORMIGAS REAIS E FORMIGAS ARTIFICIAIS

As formigas “artificiais” criadas por Dorigo possuem semelhanças e diferenças

com relação às formigas “reais” encontradas na natureza. Para DORIGO e CARO (1999),

entre as semelhanças encontradas, destacam-se:

• Cooperação: tanto na natureza quanto no mundo virtual as formigas cooperam

entre si através da deposição e remoção do feromônio;

• Modificações no ambiente: o feromônio depositado pelas formigas atua nas duas

realidades, modificando o ambiente e, consequentemente, fixando o aprendizado

gerado pelas formigas;

• Objetivos: as formigas virtuais ou reais partilham alguns objetivos em comum,

como encontrar o caminho mais curto;

Page 61: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

61

• Inteligência / Coletividade: nas duas realidades, a inteligência é obtida através da

coletividade, pois o comportamento individual é insuficiente ou aleatório;

• Comportamento estocástico: a forma probabilística é característica as duas

realidades.

Entretanto, existem várias diferenças entre as formigas reais e as criadas por

Dorigo. As principais são:

• Tipo de Movimento: nas formigas reais, os movimentos são contínuos, enquanto

nas artificiais são discretos;

• Memória: as formigas reais não possuem uma estrutura de memória como no caso

das virtuais, que as impeça de realizar movimentos.

• Feromônio: o depósito de feromônio no mundo artificial ocorre com base na

qualidade da solução encontrada.

2.5.2.1.6. ANT SYSTEM

O algoritmo S-ACO, Simple-ACO ou AS, foi o primeiro algoritmo baseado no

comportamento de formigas a ser desenvolvido por Marco Dorigo, na década de 1990

(DORIGO e STÜTZLE, 2004). Ele adaptou o comportamento das formigas reais para a

obtenção da solução, por meio de grafos para o problema do caixeiro viajante. Embora o seu

desempenho não seja suficiente para competir com os melhores algoritmos propostos para

resolver o TSP, ele é usado como ponto de partida para a formulação de outros algoritmos

ACO.

Inicialmente, na construção da solução, m formigas são distribuídas pelos nós

possíveis seguindo algum critério pré-estabelecido, e todos os caminhos (i, j) G são

inicializados com a mesma quantidadeij > 0 de feromônio. A quantidade inicial de

feromônio (0) é constante para todos os arcos ou arestas. Em seguida, cada formiga k (k =

1,...,m) seleciona o próximo nó, dentre os possíveis, para ser visitado.

As probabilidades nas quais ocorrem as decisões para uma formiga k percorrer

a conexão ij, são dadas pela Equação (4) (DORIGO e STÜTZLE, 2004)

Page 62: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

62

[ ] [ ]

∑ [ ] [ ]

(4)

Onde, e são parâmetros para indicar respectivamente a relevância do

feromônio e da informação heurística.ij é a quantidade de feromônio na aresta ij, ij é o

inverso de dij que é o “custo” ou atratividade da aresta ij e o conjunto dos próximos nós

viáveis.

O AS não realiza nenhuma ação global, nem busca local. Assim a próxima fase,

após a construção da solução, é a atualização de feromônio, que envolve tanto o incremento

do feromônio, quanto a sua evaporação e é realizado por todas as formigas. A atualização e

definida pela Equação (5).

( ) ( ) ( ) ∑ ( )

(5)

Sendo ( )

( ), onde, t representa a interação atual, é um parâmetro

para controlar a taxa de evaporação do feromônio, m o número de formigas, Q é uma

constante do projeto (geralmente igual a 1), Lk(t) é o custo do caminho percorrido pela

formiga.

Todos os procedimentos citados até aqui serão repetidos a cada iteração e quando

o critério de parada for alcançado a heurística AS retorna a melhor solução encontrada até o

instante.

Como se pode notar há vários parâmetros que devem ser ajustados para alcançar

um melhor desempenho com AS, obtendo um bom equilíbrio entre intensificação e

diversificação.

O deve ser maior que 0 (zero). Sendo seu valor alto, isto significa que o

feromônio é muito importante e as formigas tenderão a escolher caminhos percorridos mais

vezes no passado, no entanto, sendo este alto demais pode provocar a estagnação precoce do

algoritmo num máximo/mínimo local. Se o valor for baixo, a construção tende a se comportar

de maneira semelhante a uma construção gulosa aleatória (DORIGO et al., 1996).

Por sua vez, o valor de reflete o grau de importância da informação heurística,

que se pode dizer ser inversa em relação ao valor de . Um valor muito baixo provocaria

Page 63: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

63

estagnação precoce do algoritmo e um valor alto demais o aproxima de uma construção

gulosa. O ajuste deste parâmetro é importante para se obter uma boa diversificação.

Normalmente, m=n, ou seja, a quantidade de formigas é igual à quantidade de

componentes do problema (por exemplo, número de cidades no problema do caixeiro

viajante). Um número maior de formigas eleva o desempenho do algoritmo, porém, aumenta

o tempo de processamento.

O valor de deve ser ajustado de forma que 0 < 1, pois, do contrário, haverá

um acumulação ilimitada de feromônio, prejudicando a busca por todo o espaço de soluções.

Por fim, propõe-se inicializar o feromônio de todas as arestas por

,

onde Lnn é o custo de uma construção puramente gulosa aleatória e n é quantidade de

componentes do problema.

2.5.2.1.7. ANT COLONY SYSTEM

O Ant Colony System (ACS) foi proposto com o intuito de ser uma melhoria do

Ant System. Ele possui as seguintes características que fazem com que essa melhoria de

desempenho aconteça:

• Utiliza um critério de seleção mais agressivo;

• A evaporação e o depósito de feromônio são alterados somente nos circuitos de

melhor qualidade;

• Cada vez que uma formiga percorre um determinado caminho, ela remove parte

do feromônio nele depositado, aumentando assim a exploração de caminhos

diferentes.

Estas alterações possibilitaram execuções com tempos computacionais menores,

além de encontrar soluções factíveis ótimas e apresentar prova de convergência. Estas razões

determinaram sua escolha para a implementação no problema de otimização do corrente

trabalho.

Uma das modificações do ACS em relação ao AS é um novo critério de seleção,

chamado pseudo-aleatório proporcional, no qual o parâmetro q0 controla se a formação das

soluções será de forma probabilística ou de forma gulosa. A cada iteração é sorteado um

número q aleatório, caso q q0, então a Equação (6) será utilizada como critério de seleção,

Page 64: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

64

caso contrário, será utilizado o mesmo critério de seleção do AS, descrito na Equação (4). Os

parâmetros q e q0 são números entre 0 e 1.

[ ]

[ ]

(6)

A parametrização do valor de q0 busca valores em torno da melhor solução ou

define a exploração de soluções alternativas. O parâmetro q0 determina a importância relativa

da investigação versus a exploração (DORIGO e GAMBARDELLA, 1997). Se q q0,

procede-se uma investigação na qual o elemento com a maior combinação de feromônio e

informação heurística é escolhido. Caso contrário, se q > q0, a exploração de um novo

elemento é determinado proporcionalmente à sua distribuição probabilística

(ABACHIZADEH e TAHANI, 2009). Assim como no AS, um valor alto de α, que é o

parâmetro de controle de influência de feromônio, tende a aumentar a importância

probabilística do conhecimento acumulado. E o valor do parâmetro β influencia a importância

da característica do problema com o controle da informação heurística.

O processo de deposição e evaporação do feromônio no ACS foi modificado em

relação ao AS, de modo que a matriz de feromônio seja atualizada de forma global e local. A

atualização local atua junto à construção das soluções, onde uma parcela de feromônio é

reduzida permitindo a exploração de regiões não consideradas e diminuindo a tendência à

estagnação do algoritmo. Segundo ELLABIB et al. (2003), a fase final do algoritmo AS (fase

de evaporação) é substituída, no ACS, pela atualização local do feromônio, com a diferença

de ser aplicada durante a construção das soluções. Portanto podemos dizer que cada vez que

um caminho é percorrido por uma formiga, ele se torna ligeiramente menos desejável para as

demais. A forma de atualização local do feromônio pode ser visto na Equação (7).

( ) (7)

Onde, é um parâmetro para controlar a taxa de evaporação do feromônio e 0 é o

valor inicial dos feromônios das arrestas, sendo que os valores destes parâmetros são

definidos assim como no algoritmo AS.

Page 65: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

65

A atualização global se faz a cada iteração do algoritmo, e a mesma se processa

tanto com a evaporação quanto com o depósito de feromônio, que são aplicados somente à

melhor solução, ou ao melhor percurso que as formigas encontraram. A aresta correspondente

à melhor solução recebe um reforço de feromônio (DORIGO e GAMBARDELLA, 1997). A

atualização global é dada pela Equação (8). De acordo com DORIGO e GAMBARDELLA

(1997), a atualização global do ACS evita a lenta convergência dos resultados, concentrando

as buscas na vizinhança da melhor solução.

( ) (8)

O valor do feromônio para a melhor solução da iteração é calculado por

, onde, é o custo do circuito da melhor solução da iteração

ou o melhor valor da função objetivo.

Como se pode notar, o ACS utiliza todos os parâmetros utilizados no AS e outros

mais para atender as suas características específicas. As recomendações para os ajustes dos

parâmetros em comum entre estes dois algoritmos são as mesmas observadas no AS.

Page 66: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

66

3. MODELAGEM E DESENVOLVIMENTO

Este capítulo apresentará o Sistema de Engenharia de Tráfego proposto por MAIA

(2006), mostrará em que componente, dentre os que fazem parte deste sistema de TE, será

introduzido os algoritmos de otimização desenvolvidos neste trabalho. Este capítulo também

apresenta a ferramenta utilizada para construção dos algoritmos. Será apresentado também o

desenvolvimento desses algoritmos de otimização baseados nas heurísticas estudadas de

Algoritmos Genéticos e Colônia de Formigas.

3.1. ENGENHARIA DE TRÁFEGO EM DOMÍNIO MPLS UTILIZANDO TÉCNICAS

DE INTELIGÊNCIA COMPUTACIONAL (MAIA, 2006)

A proposta defendida por MAIA (2006) objetivava desenvolver um sistema de

Engenharia de Tráfego, capaz de sustentar tráfego misto (dados, voz, vídeo) com QoS na

rede, utilizando MPLS, princípios de Computação Autonômica e técnicas de Inteligência

Computacional.

Foram criados algoritmos para descoberta dos caminhos, criação, ativação,

monitoração e re-roteamento das LSP’s. Desenvolveu-se também um algoritmo para controle

de admissão de conexão (CAC - Connection Admission Control) utilizando reconhecimento e

classificação dos perfis de comportamento de tráfego das aplicações, outro algoritmo para

otimização dos recursos da rede utilizando AG, e ainda um algoritmo para realizar a

identificação dos enlaces críticos e sinalizar a necessidade de ampliação de suas capacidades

de forma proativa.

A otimização dos recursos da rede foi planejada para ser efetuada periodicamente.

A meta da otimização é fazer com que as LSP’s que atendem as aplicações, utilizem os

melhores caminhos possíveis, efetuando um re-roteamento caso seja preciso. Pois, um

caminho que num determinado momento é escolhido como a melhor opção para o

estabelecimento de uma LSP, pode deixar de sê-lo dependendo do dinamismo da rede.

O sistema proposto é distribuído já que cada roteador de borda toma decisões por

si só, pois cada um contém uma unidade de TE; e é adaptativo por se ajustar as condições e

alterações da rede.

Page 67: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

67

Conforme mostrado na Figura 15, cada unidade de TE é formada pelos seguintes

componentes (MAIA, 2006):

• Coletor das aplicações e requisitos de QoS (CARQ);

• Coletor de informações da rede (CIR);

• Coletor e processador de medições de tráfego (CPMT);

• Construtor de lista preliminar de caminhos mais curtos para as LSP´s (CLPC);

• Classificador dos caminhos em famílias (CCF);

• Identificador de necessidade de LSP´s (IANL);

• Sistema de Inferência Nebulosa (SIF);

• Módulo responsável pela escolha dos caminhos para as LSP´s (ECL);

• Módulo responsável pela criação e ativação das LSP´s (CAL).

Figura 15: Componentes do sistema de TE básico (MAIA, 2006).

A Figura 16 apresenta os componentes do TE após as inclusões dos módulos

propostos no trabalho de MAIA (2006). O DAV para detecção da vazão de tráfego das

aplicações prioritárias e re-roteamento das LSP’s; o CAC para controle de admissão de

conexão; o RCPT para reconhecimento e classificação dos perfis de comportamento de

tráfego das aplicações; o OAG para otimização dos recursos de rede e o AIEC para

identificação de enlaces críticos.

Page 68: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

68

Figura 16: Componentes do sistema de TE proposto por MAIA (2006).

O sistema de TE proposto sem o módulo de otimização viabiliza o fornecimento

de QoS fim-a-fim, porém não garante que os recursos de rede sempre estejam sendo utilizados

da melhor forma possível.

Para melhor entendimento, considere o seguinte exemplo: em um domínio MPLS,

uma LSP é criada para encaminhar um tráfego de dados, naturalmente, esta LSP utiliza o

menor caminho livre. Em seguida, mais LSP’s são criadas para atender outras demandas de

tráfego, todos atendendo as necessidades de QoS. Após algum tempo, o tráfego de dados da

primeira LSP criada é encerrado, deixando o menor caminho novamente disponível. Como as

outras LSP’s continuam atendendo as necessidades de QoS até o momento o sistema, neste

caso, não realiza o re-roteamento, apesar do sistema não utilizar da forma mais otimizada os

recursos de rede. Sendo assim, o desempenho do sistema seria prejudicado, admitindo-se a

possibilidade de situações semelhantes ocorrerem com frequência.

Desta forma, para evitar que situações parecidas com a descrita acima aconteçam,

o módulo de otimização deverá periodicamente efetuar a otimização dos recursos da rede.

Para que a otimização possa ser realizada é necessário que o OAG tenha um conhecimento

prévio de quais são as aplicações que estão utilizando o domínio MPLS naquele momento e

suas respectivas LSP’s. Num sistema de TE sem otimização, durante o atendimento de uma

determinada solicitação de LSP, é verificada a situação da rede e feita a seleção dos caminhos

Page 69: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

69

mais curtos que estão em condições de atender a necessidade de QoS da aplicação. O caminho

escolhido é aquele que possui o menor valor de custo nebuloso. No caso do sistema de TE

com otimização o objetivo não é a obtenção de um conjunto de ótimas soluções individuais,

mas a melhor solução possível para o grupo de aplicações (MAIA, 2006).

O componente ECL é o responsável por preparar a tabela de soluções válidas e a

codificação genética para utilização do OAG. A tabela de soluções válidas é montada

numerando os caminhos em condições de estabelecer LSP’s. A Tabela 2 apresenta uma tabela

hipotética de soluções válidas. A codificação genética é a escolha aleatória de um caminho

para cada LSP para formar uma possível solução. A Tabela 3 mostra um exemplo de possível

solução.

Tabela 2

Lista de caminhos em condições de estabelecer LSP´s para as aplicações

Aplicação Número do caminho

para a LSP

Vazão desejada

(MBps)

Custo

Nebuloso

Caminhos

possíveis

Vídeo0 1 2 80 8_9_10_12

2 2 90 8_11_12

Vídeo1 1 2,1 70 8_12

2 2,1 80 8_9_10_12

3 2,1 90 8_11_12

http0/ftp0 1 2,2 70 8_12

2 2,2 80 8_9_10_12

3 2,2 90 8_11_12

ftp1 1 0,4 70 8_12

2 0,4 80 8_9_10_12

3 0,4 90 8_11_12

Voz 1 0,128 70 8_12

2 0,128 80 8_9_10_12

3 0,128 90 8_11_12

ftp2 1 0,128 50 9_10_12

2 0,128 120 9_8_11_12

ftp3 1 0,128 30 10_12

2 0,128 140 10_9_8_11_12

ftp4 1 0,128 20 11_12

2 0,128 140 11_8_12

Fonte: MAIA (2006)

Page 70: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

70

Tabela 3

Exemplo de uma possível solução em condições de estabelecer as LSP´s para o conjunto

de aplicações

Vídeo0 Vídeo1 http0/ftp0 ftp1 Voz ftp2 ftp3 ftp4

1 1 2 2 2 1 1 1

Fonte: MAIA (2006)

Este sistema de TE proposto em MAIA (2006) utiliza o software simulador de

redes Network Simulator (ns2) para realizar suas simulações. O ns2 é uma ferramenta

poderosa para configurar simulações complexas e também para comparação de resultados de

pesquisas. Estão implementados no ns2 os protocolos IP, TCP, UDP, FTP, HTTP, além dos

protocolos de roteamento. Junto com o ns2 é distribuído um software para animação da

simulação, o nam (network animator), que pode ser executado após o término da simulação

para a sua visualização.

Para possibilitar a simulação deste sistema de TE foi necessário o

desenvolvimento de um conjunto de programas que se interagem e implementam os módulos

do sistema descritos acima. A Figura 17 apresenta um diagrama que mostra a interação entre

os programas do sistema proposto.

O programa CFLAG.CPP é o responsável pela implementação do módulo de

otimização dos recursos de rede. O CFLAG.CPP utilizará os algoritmos desenvolvidos neste

trabalho. Este programa controla e habilita o momento em que o algoritmo de otimização será

iniciado, é ele também que fornece os arquivos com todas as informações sobre os caminhos

possíveis para utilização no algoritmo de otimização.

O sistema de TE proposto por MAIA (2006) utiliza um AG no seu módulo de

otimização, portanto, o objetivo deste trabalho é desenvolver um novo AG e um algoritmo de

Colônia de Formigas que serão utilizados neste módulo.

Page 71: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

71

Figura 17: Interação entre os programas para a simulação do sistema de TE (MAIA, 2006).

3.2. MATLAB

O MATLAB é um ambiente de desenvolvimento que integra análise numérica,

cálculo com matrizes, processamento de sinais e criação de gráficos. Os comandos do

MATLAB são muito semelhantes à forma como se escrevem expressões algébricas, tornando

mais simples seu uso. Podem ser incorporadas as rotinas pré-definidas, pacotes para cálculos

específicos, pois esse ambiente possui bibliotecas conhecidas como toolboxes que permite

cálculos específicos para diversas áreas como Redes Neurais Artificiais, Lógica Nebulosa,

processamento de sinais, etc. (MAIA, 2006).

Page 72: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

72

O MATLAB quando carregado apresenta duas janelas, a Janela de Comando

(Command Windows) e Janela Gráfica (Graphic Windows). A Janela de Comando é ativada

quando se inicializa o MATLAB, e o prompt padrão é exibido na tela. MATLAB pode ser

usado como um shell interativo de matemática. Sequências de comandos podem ser guardadas

em um arquivo de texto, tipicamente utilizando o MATLAB Editor, como um script ou

encapsulado em uma função, alargando os comandos disponíveis.

3.3. IMPLEMENTAÇÃO DOS ALGORITMOS DE OTIMIZAÇÃO

Nesta seção serão apresentados os métodos utilizados para implementação dos

algoritmos de otimização, assim como os valores utilizados como parâmetros dos mesmos.

Para o problema proposto por este trabalho, o algoritmo de otimização têm por

objetivo otimizar os recursos de rede no sistema de TE proposto por MAIA (2006). O

algoritmo apontará, dentre os caminhos possíveis de serem estabelecidas LSP’s, os

“melhores” caminhos que atendam os requisitos de QoS de cada aplicação. Para tanto, estes

algoritmos deverão minimizar a soma, para todos os caminhos candidatos e para todas as

LSP’s, do produto entre o custo nebuloso da cada caminho candidato e a vazão de tráfego de

cada LSP. O problema pode ser formulado matematicamente através da função objetivo

apresentada na Equação (9). A vazão desejada pela aplicação prioritária i é representada por

λi. O custo nebuloso aij indica o grau de adequação do caminho candidato j para encaminhar o

tráfego da LSP i. Se o valor do custo nebuloso é baixo então a sua adequação será alta e vice-

versa (MAIA, 2006).

∑ ∑

(9)

A função objetivo está sujeita a algumas restrições, sendo que algumas destas são

tratadas no CFLAG.cpp. Apenas uma restrição é utilizada no algoritmo de otimização, esta

está descrita abaixo:

(10)

Page 73: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

73

onde:

= Largura de banda disponível no caminho candidato j;

G = Conjunto de caminhos disponíveis.

Os algoritmos de otimização utilizarão os arquivos ARQCAMIN.tr, FLUXOS.tr e

MEDENREP.tr que são fornecidos pelo CFLAG.cpp. São nestes arquivos que estão contidas

todas as informações, a respeito da topologia utilizada e das aplicações, de que necessitam os

algoritmos para calcular a função objetivo e para obedecer às restrições que o problema está

sujeito.

Nas seções seguintes serão apresentadas as formas de implementação de cada um

dos algoritmos de otimização que são alvos de estudo deste trabalho, sendo os mesmos,

Algoritmos Genéticos e Colônia de Formigas.

3.3.1. ALGORITMO GENÉTICO

Como visto anteriormente, os AG são algoritmos baseados na genética e na

seleção natural, e utilizam os princípios fundamentais destas duas áreas para definir seus

parâmetros e métodos.

A Tabela 3, apresentada na seção 3.1, nos mostra uma possível solução ou

possível LSP para o sistema de TE, esta mesma representação exemplifica um cromossomo

utilizado no AG. Cada gene desse cromossomo representa um caminho possível para a

aplicação em questão.

O fitness de cada cromossomo é calculado através da função de avaliação

representada matematicamente pela Equação (9).

O algoritmo utiliza uma população de quarenta indivíduos, ou seja, a cada geração

são instituídos 40 “novos” cromossomos e estes são então submetidos aos operadores

genéticos. A população inicial é definida de forma aleatória seguindo a tabela de soluções

válidas. No presente trabalho, o AG desenvolvido utiliza como critério de parada o número de

gerações, que no caso é igual a vinte. Assim sendo ao final de vinte iterações o algoritmo

cessa sua execução e retorna a melhor solução encontrada até o momento.

A Figura 18 apresenta o componente principal do AG, nele está o controle

responsável por habilitar o início do algoritmo, a leitura dos arquivos repassados pelo sistema

Page 74: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

74

de TE com todas as informações necessárias, a declaração das variáveis e constantes, a

chamada dos procedimentos iniciais, o loop que controla o número de gerações, as chamadas

dos demais procedimentos responsáveis por implementar os operadores genéticos e por fim a

gravação do arquivo com a solução ótima encontrada e a apresentação dos resultados.

function AG_for_TE()

% AG for TE

%

% Este algoritmo implementa um Algoritmo Genético

% para o arquivos *.tr gerados pelo sistema de TE proposto por MAIA(2006).

% Autor: Samuel Cruz Guimarães

% Histórico: Iniciado em 03/2010

% Finalizado em 12/2010

close all;

clear all;

clc;

% Verifica situacao do arquivo habilag.tr.

fid1 = fopen('habilag.tr','r');

Saida = fscanf(fid1,'%d %d');

fclose(fid1);

Saida = Saida';

habilag = Saida;

% Verifica a situacao do recurso compartilhado.

% res = 0 ==> liberado.

% res = 1 ==> bloqueado.

res = lecontrole;

fprintf('\nAguardando autorizacao para ativar AG ........');

while ((habilag(:,2) && ~res) < 1)

% Verifica situacao do arquivo habilag.tr.

fid1 = fopen('habilag.tr','r');

Saida = fscanf(fid1,'%d %d');

fclose(fid1);

Saida = Saida';

habilag = Saida;

% Verifica a situacao do recurso compartilhado.

% res = 0 ==> liberado.

% res = 1 ==> bloqueado.

res = lecontrole;

end

libera = 0;

bloqueia = 1;

% Bloqueia o acesso ao recurso compartilhado.

acesso(bloqueia);

% Desativa o campo ativaag

% Este campo sera ativado novamente pelo CFLAG quando for necessario

% executar novamente o AG

habilag(:,2) = 0;

fid = fopen('habilag.tr','w');

fprintf(fid,'%d %d',habilag);

fclose(fid);

%Inicia a contagem do tempo de execução

tic;

fprintf('\nAlgoritmo Genético iniciado.............\n');

Page 75: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

75

Figura 18: Componente principal do Algoritmo Genético

%Número de cromossomos

qcrom = 40;

%Número de gerações criadas pelo AG

MaxGer = 20;

%Indice de gerações(elitismo)

IG = 0.9;

%Indice de mutação

IndMut = 0.02;

%Vetor auxiliar para geração dos gráficos

vet_menores = zeros(MaxGer, 2);

%Carrega os arquivos ARQCAMIN.tr, FLUXOS.tr E MEDENREP.tr

%e gera um tabela de caminhos e das larguras de banda dos enlaces

[tabcam, larguras_bandas] = carrega_arquivos('arqcamin.tr','fluxos.tr','medenrep.tr');

%Gera uma tabela com a qtde de caminhos por aplicação

%e a qtde de aplicações

[aplic_cam, qaplic] = NumAplicacoes(tabcam);

%Carrega a população inicial

crom = PopInicial(aplic_cam,qaplic,qcrom,tabcam,larguras_bandas);

% disp('Primeiros cromossomos:');

% disp(crom);

%Executa a função de Avaliação

[vet_result, vet_porcentInv, total_porcent] = ExeFunFitness(qaplic,qcrom,crom,tabcam);

%Executa os operadores genéticos para todas as gerações

for exe = 1:MaxGer

%Executa a função de Elitismo

[vet_elite, vet_pais1] = Elite(vet_result,IG,qcrom);

%Executa a função de Seleção

vet_pais2 = Selecao(vet_pais1,qcrom,IG,total_porcent,vet_porcentInv);

%Executa a função de Cruzamento

NCrom = Cruzamento(qaplic,qcrom,IG,vet_pais2,vet_elite,crom,tabcam,larguras_bandas);

%Executa a função de Mutação

crom = Mutacao(NCrom,qcrom,IG,qaplic,IndMut,aplic_cam,tabcam,larguras_bandas);

%Armazena dados para gerar Gráficos

vet_menores(exe, 1) = min(vet_result(:,1));

vet_menores(exe, 2) = max(vet_result(:,1));

%Executa a função de Avaliação

[vet_result, vet_porcentInv, total_porcent] =

ExeFunFitness(qaplic,qcrom,crom,tabcam);

end

[menor_Zx, ind_solotima] = min(vet_result(:,1));

% Grava a melhor solucao no arquivo SOLOTIMA.TR que sera lido depois

% pelo CFLAG.

fid = fopen('solotima.tr','w');

fprintf(fid,'%d',ind_solotima);

fclose(fid);

% Informa ao CFLAG que o AG esta sendo finalizado.

habilag(:,1) = 1;

habilag(:,2) = 0;

fid = fopen('habilag.tr','w');

fprintf(fid,'%d %d',habilag);

fclose(fid);

% Libera o acesso ao recurso compartilhado.

acesso(libera);% End of AG

%Encerra a contagem e exibe o tempo de execução

termino = toc;

Page 76: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

76

A cada geração do AG, como se pode notar no algoritmo acima, o primeiro

procedimento realizado é o calculo do custo (fitness) de cada cromossomo presente na

população, a função responsável por esse procedimento é a ExeFunFitness.

De posse do custo de todos os cromossomos, a próxima etapa consiste em realizar

um elitismo, que como descrito neste trabalho, consiste em selecionar uma quantidade de

cromossomos com o menor custo e preservá-los para a geração seguinte, assim garante-se

que, caso não seja criado um indivíduo mais apto na geração seguinte, a melhor solução desta

geração será igual à da geração anterior. Usando este mecanismo estamos influenciando a

intensificação do algoritmo na zona do espaço de busca próximo as melhores soluções de

cada geração. A constante que controla a quantidade de cromossomos que serão mantidos

pelo elitismo é o IG, que neste trabalho foi inicializado em 0,9. Deve-se atentar para o valor

desta constante, pois um valor baixo pode levar o algoritmo para uma convergência

prematura. Esta constante deve possuir um valor entre 0 e 1 (0 IG 1) indicando qual o

percentual da população irá participar dos operadores genéticos, o restante da população será

preservada. No algoritmo deste trabalho, a população possui quarenta indivíduos e o IG é

igual a 0,9, portanto quatro indivíduos da população serão preservados, o que corresponde a

10% do total da população. Os outros trinta e seis indivíduos seguirão pelo restante dos

procedimentos.

O próximo procedimento é o operador de seleção. Nele trinta e seis indivíduos são

selecionados, dentre os possíveis, de forma probabilística levando-se em consideração o

inverso do custo de cada cromossomo, ou seja, quanto menor o seu custo maior a

probabilidade do cromossomo ser selecionado.

O procedimento seguinte é responsável pelo cruzamento dos cromossomos

selecionados no procedimento anterior. Neste procedimento são escolhidos de forma

seqüencial pares de cromossomos que serão chamados de cromossomos pais. O método de

cruzamento escolhido para o desenvolvimento do AG neste trabalho foi o cruzamento de um

ponto, que já teve o seu funcionamento descrito neste mesmo trabalho. Após a realização dos

cruzamentos os cromossomos resultantes são denominados de cromossomos filhos e são

encaminhados para a próxima etapa do AG.

A próxima etapa consiste em submeter os cromossomos ao operador de mutação.

A constante que controla o índice de mutação do algoritmo foi denominada IndMut e foi

inicializada em 0,02. Assim sendo, é gerado um número aleatório entre 0 e 1 para cada gene

de todos os cromossomos, caso este número seja inferior a constante IndMut o gene em

Page 77: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

77

questão é alterado para outro valor, dentre os possíveis. O operador de mutação contribui para

a diversificação dos indivíduos, evitando assim uma convergência prematura e garantindo a

possibilidade de grande parte do espaço de busca ser representado.

Após a operação de mutação, os cromossomos escolhidos no elitismo são

reinseridos na população de cromossomos e assim concluímos toda uma geração do AG. Os

cromossomos resultantes consistem numa nova geração de indivíduos. Estes mesmos

procedimentos se repetirão até que o critério de parada seja satisfeito, e após o término de

todas as gerações, a melhor solução encontrada até o momento é repassada para o sistema de

TE que tomará as decisões cabíveis.

Outra importante função presente neste algoritmo é a responsável por testar se as

soluções criadas consistem em uma solução válida, levando-se em consideração a restrição

apresentada na Equação (10). Portanto, sempre que uma nova solução é proposta esta é

testada pela função, sendo a mesma utilizada após a criação dos cromossomos da população

inicial, após o operador de cruzamento e após o operador de mutação.

3.3.2. ALGORITMO DE COLÔNIA DE FORMIGAS

Este algoritmo é inspirado na organização das formigas em suas colônias, mais

especificamente, na maneira como elas se organizam e se comunicam para encontrar

alimento.

A Tabela 3, que apresenta uma possível representação de um cromossomo no caso

do AG, no algoritmo de Colônia de Formigas, representa os passos percorridos por um

formiga entre sua colônia e uma fonte de alimentos.

O algoritmo de Colônia de Formigas escolhido para ser implementado neste

trabalho é o ACS. Os parâmetros iniciais deste algoritmo serão os mais próximos possíveis

dos do AG, para que o desempenho dos dois possa ser comparado mais facilmente e com

maior propriedade. Após os primeiros testes, os valores destes parâmetros poderão ser

revistos buscando uma maior equivalência entre os algoritmos, levando-se em conta o tempo

de processamento e as soluções encontradas. Sendo assim, o número de formigas foi

inicializado com o mesmo número de cromossomos do AG, igual a quarenta. O número de

iterações do ACS também é igual ao número de gerações do AG, vinte no total, e este também

é o parâmetro utilizado como critério de parada.

Page 78: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

78

A Figura 19 apresenta a principal parte do algoritmo de Colônia de Formigas.

Podemos observar o controle que habilita o início do algoritmo, a leitura dos arquivos que

contêm as informações necessárias, a declaração das variáveis e constantes, os procedimentos

iniciais, o laço que controla as iterações e o restante dos procedimentos, e a gravação do

resultado obtido, estrutura esta muito semelhante a do AG, diferenciando-se basicamente

pelos procedimentos diretamente responsáveis pela otimização.

function ACS_for_TE()

% % ACS for TE

% %

% % Este algoritmo implementa um algoritmo de Colônia de Formigas (Ant Colony System -

ACS)

% % para o arquivos *.tr gerados pelo sistema de TE proposto por MAIA(2006).

% % Autor: Samuel Guimarães

% % Histórico: Iniciado em 03/2010

% % Finalizado em 12/2010

close all;

clear all;

% Verifica situacao do arquivo habilag.tr.

fid1 = fopen('habilag.tr','r');

Saida = fscanf(fid1,'%d %d');

fclose(fid1);

Saida = Saida';

habilag = Saida;

% Verifica a situacao do recurso compartilhado.

% res = 0 ==> liberado.

% res = 1 ==> bloqueado.

res = lecontrole;

fprintf('\nAguardando autorizacao para ativar AG ........');

while ((habilag(:,2) && ~res) < 1)

% Verifica situacao do arquivo habilag.tr.

fid1 = fopen('habilag.tr','r');

Saida = fscanf(fid1,'%d %d');

fclose(fid1);

Saida = Saida';

habilag = Saida;

% Verifica a situacao do recurso compartilhado.

% res = 0 ==> liberado.

% res = 1 ==> bloqueado.

res = lecontrole;

end

libera = 0;

bloqueia = 1;

% Bloqueia o acesso ao recurso compartilhado.

acesso(bloqueia);

% Desativa o campo ativaag

% Este campo sera ativado novamente pelo CFLAG quando for necessario

% executar novamente o AG

habilag(:,2) = 0;

fid = fopen('habilag.tr','w');

fprintf(fid,'%d %d',habilag);

fclose(fid);

Page 79: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

79

%Inicia a contagem do tempo de execução

tic;

fprintf('\nAlgoritmo Ant Colony System iniciado.............\n');

%Qtde de formigas

m = 40;

%Número de iterações

Num_iteracoes = 20;

%Coeficientes

alpha = 1;

rho = 0.1;

beta = 5;

q0 = 0.2;

%Carrega os arquivos ARQCAMIN.tr, FLUXOS.tr E MEDENREP.tr

%e gera um tabela de caminhos e das larguras de banda dos enlaces

[tabcam, larguras_bandas] = carrega_arquivos('arqcamin.tr','fluxos.tr','medenrep.tr');

%Gera uma tabela com a qtde de caminhos por aplicação

%e a qtde de aplicações

[aplic_cam, qaplic] = NumAplicacoes(tabcam);

%Tabelas e variavéis Auxiliares

auxtau = max(aplic_cam(2,:));

tau = zeros(auxtau,qaplic);

ants = zeros(m,qaplic);

probs = tau;

custo = tau;

aux_passo = 2;

vet_result = zeros(m,2);

vet_max_min = zeros(Num_iteracoes,2);

melhor = zeros(1,qaplic+2);

%Alimenta tabela de feromônio

[tau,tau0] = IniciandoFeromonios(tabcam,qaplic,tau,aplic_cam);

%Alimenta tabela de custos

custo = IniciandoCustoRotas(tabcam,aplic_cam,custo,qaplic);

%Define o primeiro passo de todas as formigas

ants = IniciandoFormigas(m,aplic_cam,ants);

for iteracao = 1:Num_iteracoes

for form = 1:m

form_inviavel = true;

larguras_bandas(:,4) = larguras_bandas(:,3);

while form_inviavel

for passo = aux_passo:qaplic

%Calcula as probabilidades do próximo passo

probs =

CalcularProbabilidades(q0,probs,passo,tau,alpha,beta,custo,aplic_cam);

%Escolhe o proximo passo da formiga

ants = SelecionaProximoPasso(ants,probs,passo,form,aplic_cam);

end

%Testa se a solução é válida

form_inviavel =

testa_validade_solucao(ants(form,:),tabcam,larguras_bandas,passo);

end

for passo = aux_passo:qaplic

%Realiza a atualização local dos feromônios

tau = AtualizacaoLocalFeromonio(tau,rho,passo,form,tau0,ants);

end

end

aux_passo = 1;

%Calcula o fitness das formigas

vet_result = CalcularCustoFormigas(vet_result,ants,tabcam,m,qaplic);

vet_max_min(iteracao,1) = min(vet_result(:,1));

vet_max_min(iteracao,2) = max(vet_result(:,1));

[val,ind] = min(vet_result(:,1));

if (val<=melhor(2) | iteracao==1) %#ok<OR2>

melhor(2) = val;

melhor(1) = ind;

melhor(3:qaplic+2) = ants(ind,:);

end

Page 80: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

80

Figura 19: Componente principal do algoritmo de colônia de formigas

Inicialmente, são criadas e iniciadas as tabelas de feromônio e de custo dos

caminhos, partindo de uma solução puramente gulosa, criada aleatoriamente. O feromônio

inicial, 0, é definido por

, onde Lnn é o custo da solução gulosa e n é quantidade de

aplicações. Em seguida, inicia-se a construção dos caminhos das formigas, é escolhido

aleatoriamente o primeiro passo de cada uma das formigas, dentre os possíveis. A partir de

então, entramos no laço que controla as iterações do algoritmo.

Para cada uma das formigas, é calculada a probabilidade de escolha do próximo

passo. Probabilidade esta calculada pela Equação (4) caso q seja menor que q0, caso contrário

a probabilidade é calculada pela Equação (6). Sendo q um número entre 0 e 1 sorteado

aleatoriamente, e q0 uma constante para escolha da equação de probabilidade, que neste

trabalho é igual a 0,2. Os demais parâmetros das equações, a relevância do feromônio e da

informação heurística, são respectivamente = 1 e = 5.

De posse dessas probabilidades, selecionamos o próximo passo das formigas num

processo semelhante ao de seleção do AG, método da roleta. Em seguida efetua-se a

atualização local de feromônio, que consiste em diminuir o feromônio das arestas que

acabaram de ser selecionadas, tornando-as assim mesmo atraentes para as próximas formigas

e evitando uma estagnação do algoritmo numa parte do espaço de busca global. A atualização

local de feromônio é realizada de acordo com a Equação (7), onde o parâmetro para controlar

a taxa de evaporação do feromônio é = 0,1.

%Realiza a atualização global dos feromônios

tau = AtualizacaoGlobalFeromonio(tau,ants,melhor,qaplic,rho);

end

menor_Zx = melhor(2); %#ok<NASGU>

ind_solotima = melhor(1);

Grava a melhor solucao no arquivo SOLOTIMA.TR que sera lido depois

pelo CFLAG.

fid = fopen('solotima.tr','w');

fprintf(fid,'%d',ind_solotima);

fclose(fid);

% Informa ao CFLAG que o AG esta sendo finalizado.

habilag(:,1) = 1;

habilag(:,2) = 0;

fid = fopen('habilag.tr','w');

fprintf(fid,'%d %d',habilag);

fclose(fid);

% Libera o acesso ao recurso compartilhado.

acesso(libera);% End of AG for ARQSOL.tr

%Encerra a contagem e exibe o tempo de execução

termino = toc;

Page 81: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

81

Após a escolha de todos os passos, para todas as formigas, calcula-se então o

custo de todos os caminhos percorridos pelas formigas através da Equação (9). O caminho

que apresentar o menor custo é selecionado e armazenado como melhor solução até o

momento. Nas iterações futuras as melhores soluções encontradas serão comparadas com a

melhor solução armazenada, caso a solução encontrada possua menor custo esta substituirá a

solução armazenada.

O procedimento seguinte consiste em efetuar a atualização global de feromônio,

que obedece a Equação (8). Tal procedimento aumenta a quantidade de feromônio presente

nas arestas que constituem o melhor caminho para aquela iteração. Assim as arestas presentes

no melhor caminho encontrado passam a ser mais atraentes para as formigas nas próximas

iterações.

Assim como no AG, deve ser destacada a utilização de uma função para testar a

validade das soluções propostas levando-se em consideração a Equação (10). A cada tentativa

de mudança da solução a mesma é testada para saber se consiste numa solução viável, assim

sendo, a cada tentativa de selecionar o próximo passo para uma formiga o caminho percorrido

por ela até o momento e testado por esta função de validade.

Os procedimentos que acabaram de ser descritos são repetidos por todas as

iterações, e ao final delas, a melhor solução será aquela que se encontra na variável auxiliar

que armazena a melhor solução encontrada até o momento. Assim como no AG a melhor

solução encontrada é repassada para o sistema de TE que tomará as decisões cabíveis.

Page 82: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

82

4. RESULTADOS OBTIDOS

Neste capítulo serão apresentados os resultados obtidos pelos algoritmos de

otimização dos recursos de rede na utilização dos mesmos no sistema de TE proposto por

MAIA (2006). As avaliações utilizam os arquivos gerados pelo sistema de TE, o algoritmo é

habilitado, carrega tais arquivos, executa a otimização e retorna o resultado com a melhor

solução encontrada. Os principais indicadores utilizados nas avaliações foram o tempo de

processamento dos algoritmos de otimização e o valor da função objetivo da solução

encontrada pelos mesmos.

4.1. TOPOLOGIAS UTILIZADAS

Foram utilizadas neste trabalho duas topologias diferentes para simulação, as

mesmas topologias utilizadas no trabalho de MAIA (2006) e com os mesmos objetivos. A

primeira topologia é mais simples, portanto, mais fácil de avaliar seu comportamento durante

a simulação. A segunda topologia é mais complexa e se assemelha mais com uma situação

real.

4.1.1. TOPOLOGIA I

Esta primeira topologia forma um domínio MPLS contendo cinco nós (LSR’s),

além de outros dezesseis nós, sendo metade nós de origem e a outra metade nós de destino das

aplicações. A topologia I está apresentada na Figura 20. A disciplina de escalonamento

utilizada nas filas dos LSR’s foi a FIFO (First In, First Out).

Page 83: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

83

Figura 20: Topologia I de simulação (MAIA, 2006).

Os parágrafos que se seguem detalham esta topologia segundo MAIA (2006).

As oito aplicações (Video0, Video1, ftp0, ftp1, ftp2, ftp3, ftp4 e Voip) são

conectadas aos respectivos destinos, através do domínio MPLS. As aplicações estão

conectadas aos LSR’s através de enlaces de 10 MBps e atraso de 1 ms.

O domínio MPLS na topologia I possui três caminhos alternativos, os quais são

necessários para realizar a TE. Os cincos LSR’s (8, 9, 10, 11 e 12) estão conectados através de

enlaces de longa distância (e consequentemente alto atraso). Os caminhos foram configurados

com as seguintes características:

• Caminho 1: é a sequência de LSR’s 8-9-10-12, que possui um atraso mínimo de

90 ms.

• Caminho 2: é o caminho direto 8-12, que possui um atraso mínimo de 70 ms. Esse

caminho é o mais curto, portanto seria o escolhido naturalmente pelos protocolos

de roteamento padrão. Este caminho é candidato a se transformar num ponto de

congestionamento.

• Caminho 3: representado pela sequência de LSR´s 8-11-12, que possui um atraso

mínimo de 90 ms.

Page 84: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

84

A sequência de LSR’s de cada caminho pode ser alterada dependendo do LSR’s

de entrada no domínio MPLS.

A quantidade de fontes de tráfego foi definida de maneira a se verificar o

comportamento da rede e os efeitos da implementação da TE em uma situação controlada.

O sistema foi testado utilizando aplicações de voz, dados e vídeo. Para gerar os

tráfegos das aplicações de voz foram utilizadas fontes de dados constantes (CBR). Os tráfegos

das aplicações de vídeo foram obtidos com a utilização de traces reais. No caso das

aplicações de dados foram utilizadas fontes FTP e traces reais HTTP. As fontes FTP foram

configuradas com pacotes de tamanho de 1000 Bytes. As aplicações possuem as seguintes

necessidades e características:

• Vídeo0: Vazão média 2 MBps e atraso máximo 150ms.

• Video1: Foi adotada a vazão de 1.1 MBps. A aplicação foi cadastrada com atraso

máximo de 150ms;

• Dados (http0/ftp0 e ftp1): Não foram consideradas exigências, sendo que os

pacotes são encaminhados pelo menor caminho. Foi injetado tráfego HTTP obtido

de trace real no nó 2. Além disso, foram configuradas cinquenta fontes de dados

(FTP), sendo vinte originando-se no nó 2, e trinta originando-se no nó 3. O

momento da ativação destas fontes durante as simulações foi aleatório.

• Dados (ftp2, ftp3 e ftp4): Destinam-se a gerar tráfego de fundo nos caminhos 1 e

3. Foram configuradas três fontes de dados (FTP) originando-se nos LSR’s 9, 10 e

11. Estes dados destinam-se respectivamente aos nós 18, 19 e 20. O momento da

ativação destas fontes foi aleatório.

• Voz: vazão média 128 KBps e atraso máximo 150 ms.

Foi realizada uma simulação do sistema de TE utilizando a topologia I. Os

arquivos provenientes desta simulação foram utilizados para os testes com os algoritmos de

otimização. Os algoritmos de otimização processam tais arquivos e geram duas tabelas com as

informações necessárias para execução da otimização. Na primeira tabela temos as

informações sobre os possíveis caminhos para todas as aplicações. A Tabela 4 apresenta estes

caminhos obtidos na simulação. A segunda tabela gerada pelos algoritmos, representada na

Tabela 5, contém as informações sobre as larguras de banda em cada enlace da topologia,

informações estas utilizadas para que a restrição apresentada na Equação (10) possa ser

tratada.

Page 85: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

85

Tabela 4

Possíveis caminhos das aplicações na simulação da topologia I

Aplicação Caminho Vazão

Desesjada (MBps)

Custo Fuzzy

Prioridade Nó de

Origem Nó de

Destino Caminho

1 1 0,140 22,50 0 4 17 4 8 12 17 NaN NaN 1 2 0,140 19,52 1 4 17 4 8 11 12 17 NaN 1 3 0,140 18,83 2 4 17 4 8 9 10 12 17 2 1 1,848 5,73 0 1 14 1 8 12 14 NaN NaN 2 2 1,848 22,50 1 1 14 1 8 11 12 14 NaN 2 3 1,848 22,50 2 1 14 1 8 9 10 12 14 3 1 0,400 30,00 0 3 16 3 8 12 16 NaN NaN

3 2 0,400 30,00 1 3 16 3 8 11 12 16 NaN 3 3 0,400 30,00 2 3 16 3 8 9 10 12 16 4 1 0,256 30,00 0 2 15 2 8 12 15 NaN NaN

4 2 0,256 30,00 1 2 15 2 8 11 12 15 NaN 4 3 0,256 30,00 2 2 15 2 8 9 10 12 15 5 1 2,058 17,90 0 0 13 0 8 12 13 NaN NaN 5 2 2,058 16,97 1 0 13 0 8 11 12 13 NaN 5 3 2,058 15,96 2 0 13 0 8 9 10 12 13 6 1 0,128 30,00 0 7 20 7 11 12 20 NaN NaN 7 1 0,128 30,00 0 5 18 5 9 10 12 18 NaN

8 1 0,128 30,00 0 6 19 6 10 12 19 NaN NaN Fonte própria

Tabela 5

Larguras de banda dos enlaces na topologia I (Continua)

Nó de Origem Nó de Destino Largura de Banda

0 8 10

1 8 10

2 8 10

3 8 10

4 8 10

8 9 4

9 10 4

10 12 4

8 12 2,5

8 11 4

11 12 4

7 11 10

5 9 10

6 10 10

12 13 10

12 14 10

Page 86: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

86

(Conclusão)

Nó de Origem Nó de Destino Largura de Banda

12 15 10

12 16 10

12 17 10

12 18 10

12 19 10

12 20 10

Fonte própria

4.1.2. TOPOLOGIA II

Esta segunda topologia de domínio MPLS é composta por dezesseis LSR’s, sendo

que destes, dez são LSR’s de borda, denominados LER’s. O restante são LSR’s internos,

responsáveis por encaminhar os pacotes para o próximo salto. A Figura 21 traz a

representação desta topologia. Assim como na topologia I, a disciplina de escalonamento

utilizada nas filas dos LSR’s foi a FIFO.

Figura 21: Topologia II de simulação (MAIA, 2006).

Page 87: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

87

Igualmente à topologia I, as aplicações tanto na origem, como no destino estão

conectadas aos LSR’s do domínio através de enlaces de 10 MBps e atraso de 1 ms. A Tabela

6 mostra as características dos enlaces que compõem o domínio MPLS na topologia II.

Tabela 6

Características dos enlaces do domínio MPLS na topologia II

LSR de origem LSR de destino Largura de banda

(MBps) Atraso mínimo

(ms)

14 15 4,80 30

14 16 4,00 20 14 20 6,00 30 15 21 6,00 20 16 20 8,00 20 17 16 6,00 20 17 18 6,00 10 17 19 8,00 30 17 25 6,00 10 18 26 6,00 10 19 20 6,00 20 19 23 7,00 20 19 24 5,00 20 19 25 7,00 40

20 21 6,00 20 20 22 6,00 10 20 23 8,00 10

21 22 5,00 20 22 29 6,00 10 23 22 6,00 20 23 24 6,00 10 23 28 4,80 20 23 29 6,00 20 25 24 6,00 30 24 27 4,50 30 24 28 4,50 10 25 26 6,00 30

25 27 6,00 10 26 27 6,00 10 27 28 6,00 80

Fonte própria

A exemplo do que foi realizada na topologia I, o sistema de TE foi simulado na

topologia II utilizando aplicações de voz, dados e vídeo. Para gerar os tráfegos das aplicações

Page 88: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

88

de voz foram utilizadas fontes de dados constantes (CBR). Os tráfegos das aplicações de

vídeo foram obtidos com a utilização de traces reais. No caso das aplicações de dados foram

utilizadas fontes FTP e traces reais HTTP, sendo que o momento da ativação destas fontes

durante as simulações foi aleatório. As fontes FTP foram configuradas com pacotes de

tamanho de 1000 Bytes. A Tabela 7 apresenta as necessidades e características das aplicações

utilizadas nas avaliações da função de TE.

Tabela 7

Necessidades e características das aplicações de dados, voz e vídeo

Aplicação Origem Destino Vazão (MBps) Atraso (ms) Prioridade

dados (ftp0) 0 49 - - 0 dados (ftp1) 1 33 - - 0

vídeo0 2 51 2.20 < 150 0

vídeo1 3 50 1.20 < 150 5 dados (ftp2) 4 37 - - 0 dados (ftp3) 31 36 - - 0 dados (ftp4) 32 46 - - 0

voz0 5 48 0.128 < 150 5 voz1 6 47 0.128 < 150 5

dados (ftp5) 7 34 - - 0 vídeo2 8 44 1.20 < 150 5 vídeo3 9 43 1.20 < 150 0

voz2 11 41 0.128 < 150 5 dados (ftp6) 10 42 - - 0

voz3 12 40 0.128 < 150 5 dados (ftp7) 13 39 - - 0 dados (ftp8) 30 45 - - 0

Fonte: MAIA (2006)

Igualmente à topologia I, foi realizada uma simulação do sistema de TE utilizando

a topologia II. Os arquivos gerados durante esta simulação serviram de base para os testes

com os algoritmos de otimização. As mesmas duas tabelas geradas pelo algoritmo de

otimização para a topologia I, também são geradas para a topologia II, com base nos arquivos

provenientes do sistema de TE. Na primeira tabela temos as informações sobre os possíveis

caminhos para todas as aplicações, esta está representada na Tabela 8.

Page 89: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

89

Tabela 8

Possíveis caminhos das aplicações na simulação da topologia II

(Continua)

Aplicação Caminho Vazão

Desesjada (MBps)

Custo Fuzzy

Prioridade Nó de

Origem Nó de

Destino Caminho

1 1 0,512 16,38 0 12 40 12 14 20 22 29 40 NaN NaN

1 2 0,512 8,21 1 12 40 12 14 20 23 29 40 NaN NaN

1 3 0,512 23,50 2 12 40 12 14 15 21 22 29 40 NaN

2 1 0,128 28,00 0 11 41 11 14 20 22 29 41 NaN NaN

2 2 0,128 20,50 1 11 41 11 14 20 23 29 41 NaN NaN

2 3 0,128 19,18 2 11 41 11 14 15 21 22 29 41 NaN

3 1 0,128 30,00 0 5 48 5 17 25 27 48 NaN NaN NaN

3 2 0,128 22,34 1 5 48 5 17 18 26 27 48 NaN NaN

3 3 0,128 17,82 2 5 48 5 17 19 25 27 48 NaN NaN

4 1 1,200 30,00 0 9 43 9 14 20 22 29 43 NaN NaN

4 2 1,200 29,50 1 9 43 9 14 20 23 29 43 NaN NaN

4 3 1,200 22,50 2 9 43 9 14 15 21 22 29 43 NaN

5 1 0,128 12,30 0 6 47 6 17 25 27 47 NaN NaN NaN

5 2 0,128 22,50 1 6 47 6 17 18 26 27 47 NaN NaN

5 3 0,128 19,70 2 6 47 6 17 19 25 27 47 NaN NaN

6 1 1,200 22,50 0 8 44 8 14 20 22 44 NaN NaN NaN

6 2 1,200 20,50 1 8 44 8 14 16 20 22 44 NaN NaN

6 3 1,200 22,50 2 8 44 8 14 15 21 22 44 NaN NaN

7 1 2,300 8,07 0 2 51 2 17 25 24 28 51 NaN NaN

7 2 2,300 5,12 1 2 51 2 17 16 20 23 28 51 NaN

7 3 2,300 7,03 2 2 51 2 17 19 23 28 51 NaN NaN

8 1 2,128 30,00 0 4 37 4 17 16 20 21 37 NaN NaN

8 2 2,128 30,00 1 4 37 4 17 19 20 21 37 NaN NaN

8 3 2,128 30,00 2 4 37 4 17 19 23 20 21 37 NaN

9 1 2,128 28,00 0 32 46 32 18 17 25 24 28 46 NaN

9 2 2,128 27,00 1 32 46 32 18 26 25 24 28 46 NaN

9 3 2,128 26,00 2 32 46 32 18 26 27 24 28 46 NaN

10 1 1,128 30,00 0 1 33 1 17 25 26 33 NaN NaN NaN

10 2 1,128 30,00 1 1 33 1 17 18 26 33 NaN NaN NaN

10 3 1,128 30,00 2 1 33 1 17 19 25 26 33 NaN NaN

11 1 2,208 30,00 0 31 36 31 18 17 16 20 21 36 NaN

11 2 2,208 30,00 1 31 36 31 18 17 19 20 21 36 NaN

11 3 2,208 30,00 2 31 36 31 18 17 25 19 20 21 36

12 1 2,132 13,02 0 13 39 13 14 20 22 39 NaN NaN NaN

12 2 2,132 13,01 1 13 39 13 14 16 20 22 39 NaN NaN

12 3 2,132 13,04 2 13 39 13 14 15 21 22 39 NaN NaN

13 1 2,128 19,00 0 7 34 7 14 16 17 25 26 34 NaN

13 2 2,128 19,00 1 7 34 7 14 20 19 25 26 34 NaN

13 3 2,128 18,00 2 7 34 7 14 20 23 19 25 26 34

14 1 2,132 15,10 0 10 42 10 14 20 22 29 42 NaN NaN

Page 90: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

90

(Conclusão)

Aplicação Caminho Vazão

Desesjada (MBps)

Custo Fuzzy

Prioridade Nó de

Origem Nó de

Destino Caminho

14 2 2,132 15,20 1 10 42 10 14 20 23 29 42 NaN NaN

14 3 2,132 15,30 2 10 42 10 14 15 21 22 29 42 NaN

15 1 2,208 23,34 0 0 49 0 17 25 27 49 NaN NaN NaN

15 2 2,208 25,00 1 0 49 0 17 18 26 27 49 NaN NaN

15 3 2,208 5,56 2 0 49 0 17 19 25 27 49 NaN NaN

16 1 2,208 13,98 0 30 45 30 15 21 20 23 28 45 NaN

16 2 2,208 15,46 1 30 45 30 15 21 22 20 23 28 45

16 3 2,208 12,34 2 30 45 30 15 21 22 23 28 45 NaN

17 1 1,517 15,65 0 3 50 3 17 25 27 50 NaN NaN NaN

17 2 1,517 7,02 1 3 50 3 17 18 26 27 50 NaN NaN

17 3 1,517 28,00 2 3 50 3 17 19 25 27 50 NaN NaN

Fonte própria

A segunda tabela, representada na Tabela 9, contém as informações sobre as

larguras de banda em cada enlace da topologia, informações estas utilizadas para que a

restrição apresentada na Equação (10) possa ser tratada.

Tabela 9

Larguras de banda dos enlaces na topologia I (Continua)

Nó de Origem Nó de Destino Largura de Banda

7 14 10 8 14 10 9 14 10

10 14 10 11 14 10 12 14 10 13 14 10 30 15 10 14 15 4,8 14 16 4 14 20 6 15 21 6 16 20 8 0 17 10 1 17 10 2 17 10 3 17 10 4 17 10 5 17 10 6 17 10

17 16 6 17 18 6 17 19 8 31 18 10 32 18 10 17 25 6 18 26 6

Page 91: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

91

(Conclusão)

Nó de Origem Nó de Destino Largura de Banda

19 20 6 19 23 7 19 25 7 20 21 6 20 22 6 20 23 8 21 36 10 21 37 10 21 22 5 19 24 5 22 39 10 23 22 6 22 29 6 23 24 6 25 24 6 24 27 4,5 24 28 4,5 23 29 6 25 26 6 26 33 10 26 34 10 25 27 6 26 27 6 27 28 6 27 47 10 27 48 10 27 49 10 27 50 10 28 51 10 28 45 10 28 46 10 23 28 4,8 29 40 10 29 41 10 29 42 10 29 43 10 22 44 10

Fonte própria

4.2. RESULTADOS DA IMPLEMENTAÇÃO DOS ALGORITMOS DE

OTIMIZAÇÃO PARA OS ARQUIVOS DO SISTEMA DE TE

Conforme já mencionado neste trabalho, o objetivo dos algoritmos de é otimizar

os recursos de rede em um domínio MPLS. Esta otimização foi planejada para ser efetuada

periodicamente. Um caminho que num determinado momento é escolhido como a melhor

opção para o estabelecimento de uma LSP, pode deixar de sê-lo dependendo das alterações

ocorridas na rede. A otimização objetiva fazer com que as LSP’s que atendem as aplicações,

Page 92: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

92

utilizem os melhores caminhos possíveis; se preciso for, re-rotear as aplicações criando novas

LSP’s que continuem atendendo as necessidades de QoS, porém de maneira mais otimizada.

Nas simulações efetuadas no sistema de TE proposto por MAIA (2006), o

algoritmo de otimização é chamado e executado na quarta simulação da topologia.

Nas seções seguintes serão vistos os resultados obtidos nas simulações do sistema

de TE nas topologias I e II, utilizando os arquivos gerados nestas simulações e os algoritmos

desenvolvidos neste trabalho.

4.2.1. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO GENÉTICO NA

TOPOLOGIA I

Após a realização da simulação do sistema de TE proposto por MAIA (2006)

utilizando a topologia I, os arquivos ARQCAMIN.tr, FLUXOS.tr e MEDENREP.tr gerados

são então utilizados para simular a otimização do Algoritmo Genético.

A princípio foram realizadas cinco simulações com o AG utilizando os arquivos

citados acima. Da Figura 22 à Figura 26 são apresentados os gráficos com os menores e

maiores valores da função objetivo para cada geração do AG. Lembrando que os parâmetros

utilizados nestas simulações são os descritos na seção 3.3.1. A Tabela 10 apresenta o tempo

de execução e o custo dos resultados de cada uma das simulações.

Figura 22: Evolução do AG na simulação I na topologia I.

Page 93: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

93

Figura 23: Evolução do AG na simulação II na topologia I.

Figura 24: Evolução do AG na simulação III na topologia I.

Figura 25: Evolução do AG na simulação IV na topologia I.

Page 94: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

94

Figura 26: Evolução do AG na simulação V na topologia I.

Tabela 10

Tempo de execução do AG e custo da melhor solução nas simulações na topologia I

Simulação Tempo de Execução (ms) Custo da

Solução Ótima I 789.65 77.2709

II 713.41 77.2709

III 597.49 77.2709

IV 661.98 77.2709

V 665.04 77.2709 Fonte própria

Como se pode notar nos gráficos e pelos resultados da Tabela 10, nas simulações

I, II, III e V, o menor resultado da função objetivo encontrado pelo AG já na população

inicial, é igual ao fitness da solução ótima encontrada pelo algoritmo ao final de sua execução.

Apenas na simulação IV a premissa apresentada acima é falsa, sendo que o menor custo dos

seus cromossomos da população inicial foi igual a 77,3689, após a execução foi encontrado o

custo para sua solução ótima igual a 77,2709, que é igual ao das demais simulações.

A fim de verificar se estes resultados descritos acima permaneceriam sem

alterações, foi realizada uma nova simulação. Essa próxima simulação consiste em executar o

AG por cem vezes consecutivas e comparar o fitness da população inicial com o fitness da

solução apresentada como ótima pelo algoritmo em todas as execuções. A Figura 27 apresenta

os resultados desta simulação.

Page 95: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

95

Figura 27: Simulação do AG em cem execuções consecutivas na topologia I.

No primeiro gráfico da Figura 27 observa-se o custo das melhores soluções

encontradas na população inicial em todas as cem execuções do algoritmo. O segundo gráfico

traz o custo das melhores soluções encontradas ao final das execuções do AG. Pode-se notar

que na grande maioria das simulações, já na população inicial encontramos alguma solução

com custo igual ao custo da melhor solução apresentada ao final da execução. Em apenas

nove simulações esta situação não é observada, e nota-se também que nestas mesmas

simulações o AG otimiza os resultados, chegando então a mesma solução das demais

simulações. Em todas as simulações o AG encontrou o mesmo custo para a solução ótima,

sendo este igual a 77,2709. No terceiro gráfico podemos observar a variação do tempo de

execução do AG para todas as simulações, sendo que a média destes tempos foi igual a

624,3873 ms.

Page 96: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

96

4.2.2. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO DE COLÔNIA DE

FORMIGAS NA TOPOLOGIA I

As simulações do algoritmo ACS utilizam os mesmos arquivos usados para

implementar o AG. Utilizam também a mesma sistemática, foram realizadas cinco simulações

com o ACS utilizando os arquivos (.tr) gerados pelo sistema de TE.

Da Figura 28 à Figura 32 são apresentados os gráficos com os menores e maiores

valores da função objetivo para cada iteração do algoritmo. Os parâmetros utilizados nestas

simulações estão descritos na seção 3.3.2 e são os mais próximos possíveis aos do AG. A

Tabela 11 apresenta o tempo de execução e o custo dos resultados de cada uma das

simulações do ACS na topologia I.

Figura 28: Evolução do ACS na simulação I na topologia I.

Figura 29: Evolução do ACS na simulação II na topologia I.

Page 97: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

97

Figura 30: Evolução do ACS na simulação III na topologia I.

Figura 31: Evolução do ACS na simulação IV na topologia I.

Figura 32: Evolução do ACS na simulação V na topologia I.

Page 98: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

98

Tabela 11

Tempo de execução do ACS e custo da melhor solução nas simulações na topologia I

Simulação Tempo de Execução (ms) Custo da

Solução Ótima I 1336.60 77.2709

II 1423.13 77.2709

III 1469.61 77.2709

IV 1536.18 77.2709

V 1391.15 77.2709 Fonte própria

Como pode ser visualizado nos gráficos acima, o algoritmo ACS apresenta

resultados semelhantes aos da simulação do AG. Em três simulações (II, III e V) não houve

otimização, considerando que não há alteração dos valores dos menores custos da solução

encontrada entre a primeira e a última iteração. Nas outras duas simulações (I e IV) notamos

que os valores diferentes que foram encontrados estão muito próximos dos valores

encontrados na maioria das iterações, e observamos também uma rápida convergência para o

valor tido como ótimo pelo algoritmo.

Figura 33: Simulação do ACS em cem execuções consecutivas na topologia I.

Page 99: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

99

Assim como nos testes com AG, os arquivos do sistema de TE foram submetidos

a outra simulação. Nesta o ACS é executado cem vezes consecutivas e os resultados da

comparação entre os valores mínimos dos custos encontrados na primeira iteração com os

valores mínimos dos custos da última iteração. Assim poderemos avaliar se o comportamento

do ACS se manterá como observado acima. A Figura 33 apresenta os resultados dessa nova

simulação.

Neste teste pode-se notar, na Figura 33 que em todas as simulações o ACS

encontrou na primeira iteração uma solução com o mesmo valor do custo encontrado na

última iteração.

Assim como na simulação do AG, em todas as simulações o ACS encontrou o

mesmo custo para a solução ótima igual a 77,2709. O que mais destoa entre os dois

algoritmos de otimização utilizados neste trabalho, é o tempo de execução, como pode ser

visto comparando os resultados da Tabela 10 aos resultados da Tabela 11. Outro fato que

evidencia esta diferença é o tempo médio de execução do ACS encontrado nesta segunda

simulação, sendo este tempo médio igual a 1475,20 ms, o que corresponde a mais de duas

vezes o tempo médio encontrado na simulação com AG. A variação dos tempos de execução

do ACS nesta última simulação pode ser observada no terceiro gráfico presente na Figura 33.

4.2.3. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO GENÉTICO NA

TOPOLOGIA II

A implementação do AG na topologia II segue os mesmos modelos de testes

utilizados na simulação da topologia I.

Os arquivos gerados durante a simulação do sistema de TE utilizando a topologia

II são utilizados para realizar cinco simulações com o AG. Da Figura 34 à Figura 38 são

apresentados os gráficos com os menores e maiores valores da função objetivo para cada

geração do AG. Os parâmetros aqui utilizados são os mesmos da simulação da topologia I e,

portanto, os mesmos descritos na seção 3.3.1. A Tabela 12 apresenta o tempo de execução e o

custo dos resultados de cada uma das simulações.

Page 100: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

100

Figura 34: Evolução do AG na simulação I na topologia II.

Figura 35: Evolução do AG na simulação II na topologia II.

Figura 36: Evolução do AG na simulação III na topologia II.

Page 101: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

101

Figura 37: Evolução do AG na simulação IV na topologia II.

Figura 38: Evolução do AG na simulação V na topologia II.

Tabela 12

Tempo de execução do AG e custo da melhor solução nas simulações da topologia II

Simulação Tempo de

Execução (ms) Custo da

Solução Ótima

I 2373.98 442.8506 II 2288.76 445.2533 III 2428.79 442.8506 IV 2307.78 442.6739 V 2353.93 444.6202

Fonte própria

Page 102: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

102

Diferentemente do que foi observado nas simulações com a topologia I, agora sim

se pode observar nos gráficos das simulações a evolução do AG. Como se pode notar no

primeiro gráfico de cada simulação, o AG vai convergindo para o mínimo da função objetivo,

ou seja, os valores do fitness das soluções encontradas diminuem constantemente ao longo das

gerações. Nos gráficos que trazem os valores máximos do fitness das soluções podemos

enxergar a mesma tendência de convergência.

Algo relevante de ser notado nos gráficos que trazem os valores mínimos dos

custos é a ação do elitismo utilizado no AG. Ele garante que no pior dos casos, a melhor

solução da geração atual será igual à melhor solução da geração anterior. Com isso pode-se

notar que em nenhum dos gráficos há aumento do fitness de uma geração para a sua

subsequente.

Figura 39: Simulação do AG em cem execuções consecutivas na topologia II.

Page 103: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

103

Na Tabela 12 pode-se observar a baixa variação, entre as simulações, dos tempos

de execução e dos fitness das melhores soluções. O desvio padrão dos tempos de execução é

igual a 55,5183 ms, enquanto o desvio padrão do fitness é igual a 1,1982.

Seguindo o modelo de simulações utilizado para a topologia I, foi realizada a

simulação de executar por cem vezes consecutivas o AG para os arquivos da topologia II. A

Figura 39 apresenta os resultados desta simulação.

É visível a diferença entre estes gráficos acima e os gráficos desta mesma

simulação para a topologia I. Podemos notar diversos valores tanto para o custo da população

inicial como para o custo da solução encontrada, o que não aconteceu com esse algoritmo na

simulação da topologia I. A Tabela 13 traz os dados das medidas observadas nesta simulação.

Tabela 13

Medidas da simulação do AG na topologia II

Medida Valor

Média dos Tempos de Execução (ms) 2293,9173

Desvio Padrão dos Tempos de Execução 98,5033

Menor Tempo de Execução (ms) 2011,9378

Maior Tempo de Execução (ms) 2565,2454

Média dos Fitness 445,4298

Desvio Padrão dos Fitness 2,8404

Menor Fitness 441,5450

Número de ocorrências do menor Fitness 7

Maior Fitness 456,0627

Média da diminuição do Fitness entre a primeira e a última geração

11,2269

Fonte própria

É importante ressaltar o baixo desvio padrão apresentados tanto para os tempos

de execução como para os fitness. Outra importante informação da Tabela 13 é a média dos

fitness, nela podemos observar a proximidade deste valor com o menor fitness encontrado. A

média da diminuição do fitness comprova mais uma vez a convergência do AG para a solução

ótima.

Page 104: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

104

4.2.4. RESULTADOS DA IMPLEMENTAÇÃO DO ALGORITMO DE COLÔNIA DE

FORMIGAS NA TOPOLOGIA II

Nesta implementação também foram utilizados os mesmos modelos de testes

utilizados nas implementações anteriores.

Os arquivos gerados durante a simulação do sistema de TE utilizando a topologia

II são utilizados para realizar cinco simulações com o ACS. Da Figura 40 à Figura 44 são

apresentados os gráficos com os menores e maiores valores da função objetivo para cada

geração do AG. Os parâmetros aqui utilizados são os mesmos da simulação da topologia I e

estão descritos na seção 3.3.2.

Figura 40: Evolução do ACS na simulação I na topologia II.

Page 105: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

105

Figura 41: Evolução do ACS na simulação II na topologia II.

Figura 42: Evolução do ACS na simulação III na topologia II.

Figura 43: Evolução do ACS na simulação IV na topologia II.

Page 106: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

106

Figura 44: Evolução do ACS na simulação V na topologia II.

A Tabela 14 apresenta o tempo de execução e o custo dos resultados de cada uma

das simulações.

Tabela 14

Tempo de execução do ACS e custo da melhor solução nas simulações da topologia II

Simulação Tempo de

Execução (ms) Custo da

Solução Ótima

I 14599.08 443.9450

II 12391.04 445.3677 III 12478.29 444.1582 IV 13493.81 441.5450 V 14034.94 446.1792

Fonte própria

Primeiramente, o que podemos observar nestas simulações é a grande diferença

entre os gráficos do AG, presentes na seção 4.2.3, e do ACS presentes acima. Os gráficos do

AG mostram os resultados da função num declínio, pois a cada geração seus cromossomos

são melhorados e graças ao elitismo utilizado em momento algum a função objetivo irá

ascender. Já os gráficos do ACS mostram-se bastante irregulares, com altos e baixos

constantes, isto evidencia a procura por soluções pelo espaço de busca. O ACS não possui

nenhum tipo de elitismo, por isso o crescimento da função objetivo em algumas iterações.

Page 107: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

107

A solução ótima do AG é considerada como a melhor solução encontrada na

última geração do algoritmo. No caso do ACS, ele possui uma variável que armazena a

melhor solução encontrada até o momento, portanto a cada iteração a melhor solução

encontrada e comparada com esta variável, aquela que for melhor será armazenada nesta

mesma variável.

Levando-se em consideração o que foi descrito acima, pode-se fazer outra

observação com relação aos gráficos dos valores mínimos do ACS. Podemos notar nas

simulações I, III e V que os melhores fitness foram encontrados até a quinta iteração, na

simulação II foi encontrado na sétima iteração e na simulação IV a melhor solução foi

encontrada na décima primeira iteração. Deste modo, concluímos que a convergência do ACS

se dá principalmente nas suas primeiras iterações e que praticamente todos os resultados

encontrados permaneceriam sem alteração caso o ACS empregasse apenas metade das

iterações utilizadas.

Figura 45: Simulação do ACS em cem execuções consecutivas na topologia II.

Page 108: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

108

Outro fato importante observado nesta simulação pode ser visualizado na Tabela

14, onde constatamos que o tempo de execução do ACS é bem superior ao tempo de execução

do AG. Um dos fatores que podem justificar esta observação está exposto no parágrafo

precedente. Como foi dito na seção 3.3.2 os parâmetros utilizados no ACS foram os mais

próximos possíveis dos do AG, isto para facilitar a comparação de desempenho entre os dois.

Com isso o ACS pode estar sendo “super parametrizado”, o que faria com que fosse

demandado um processamento desnecessário. Por exemplo, se diminuíssemos a quantidade de

iterações ou a quantidade de formigas, pode ser que encontrássemos os mesmos resultados

encontrados nesta simulação, ou próximos o suficiente que compensasse o ganho obtido no

tempo de execução.

Para equiparar as simulações realizadas neste trabalho, o ACS também foi

submetido a uma simulação que executa tal algoritmo por cem vezes consecutivas, e

apresenta na Figura 45 os gráficos com os resultados desta simulação.

Os gráficos apresentados nesta figura assemelham-se bastante aos gráficos obtidos

nesta mesma simulação com o AG que podem ser vistos na Figura 39. Podemos notar uma

variação dos valores tanto do custo da população inicial como do custo da solução encontrada.

As medidas desta simulação são apresentadas na Tabela 15.

Tabela 15

Medidas da simulação do ACS na topologia II

Medida Valor

Média dos Tempos de Execução (ms) 12962,5564

Desvio Padrão dos Tempos de Execução 765,0863

Menor Tempo de Execução (ms) 11017,6997

Maior Tempo de Execução (ms) 15545,9401

Média dos Fitness 445,5371

Desvio Padrão dos Fitness 2,1824

Menor Fitness 441,5450

Número de ocorrências do menor Fitness 1

Maior Fitness 450,5024

Média da diminuição do Fitness entre a primeira e a última geração

10,4723

Fonte própria

Page 109: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

109

Assim como observado na simulação do AG a média dos fitness se aproxima

bastante do menor fitness encontrado. A média da diminuição do fitness comprova a

otimização realizada durante as simulações. O que também observamos através da Tabela 15

é o mesmo que foi observado nas simulações I, II, III, IV e V desta mesma seção, que é o alto

tempo de execução do ACS se comparado com o AG. Enquanto o ACS possui uma média de

quase treze segundos de execução o AG possui uma média de pouco mais de dois segundos, e

os fitness encontrados nas duas simulações se equiparam.

4.2.5. COMPARAÇÃO DA EXECUÇÃO DO ALGORITMO GENÉTICO COM O

ALGORITMO DE COLÔNIA DE FORMIGAS

Para finalizar os testes de implementação do AG e do ACS, foram realizadas duas

novas simulações executando cada um dos algoritmos por cem vezes consecutivas, os

resultados entre a execução dos dois algoritmos foram comparados, isto pode ser visto na

Tabela 16, e os resultados da função objetivo dos dois algoritmos foram sobrepostos em um

mesmo gráfico para cada simulação, estes estão apresentados na Figura 46 e na Figura 47.

Tabela 16

Resultados da comparação entre AG e ACS

Medida Valor do AG 1ª Simulação

Valor do ACS 1ª Simulação

Valor do AG 2ª Simulação

Valor do ACS 2ª Simulação

Média dos Tempos de Execução (ms) 2177,2792 13922,6516 2133,8527 12828,5467

Desvio Padrão dos Tempos de Exec. 75,7769 913,544 96,8698 733,7781

Menor Tempo de Execução (ms) 2018,4067 11831,7202 1967,5809 11712,0302

Maior Tempo de Execução (ms) 2353,3640 16202,7410 2408,3095 16009,4581

Média dos Fitness 446,055 445,3532 446,166 445,3676

Desvio Padrão dos Fitness 3,3239 2,0626 3,0951 2,1695

Menor Fitness 441,5450 441,7582 441,5450 441,5450

Número de ocorrências do menor Fitness

1 5 1 1

Maior Fitness 457,6897 450,7412 455,3885 450,7441

Média da diminuição do Fitness entre a primeira e a última geração

10,4429 12,2989 10,8613 11,9686

Fonte própria

Page 110: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

110

Figura 46: Comparação dos menores fitness encontrados entre o AG e o ACS na 1ª simulação

Figura 47: Comparação dos menores fitness encontrados entre o AG e o ACS na 2ª simulação

Page 111: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

111

Nesta comparação podemos observar as vantagens e desvantagens de cada um dos

algoritmos em relação ao outro. A vantagem do AG sobre o ACS é a média dos tempos de

execução, onde o tempo de execução do ACS é aproximadamente seis vezes maior que o do

AG. Já a vantagem do ACS sobre o AG, apesar de pequena, é a média e o desvio padrão do

fitness menores. Nos gráficos pode-se observar esta vantagem do ACS, a linha vermelha, que

representa a função do ACS, fica mais concentrada numa região enquanto a linha azul, que

representa a função do AG, fica mais dispersa, com alguns picos muito distantes da melhor

solução encontrada em todas as execuções.

Page 112: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

112

5. CONCLUSÕES

Este trabalho propôs desenvolver dois algoritmos de otimização baseados nas

heurísticas de Algoritmo Genético e Colônia de Formigas. Esses algoritmos foram

desenvolvidos para otimizar os recursos de rede em um domínio MPLS utilizando o sistema

de TE proposto por MAIA (2006). Os algoritmos recebem os arquivos gerados pelo sistema

de TE contendo todas as informações a respeito da topologia utilizada e das aplicações que

possuem LSP’s criadas no domínio MPLS. Com base nas informações contidas nestes

arquivos o algoritmo deve encontrar uma solução contendo os melhores caminhos que cada

aplicação deve utilizar. Para encontrar estes melhores caminhos o algoritmo deve minimizar a

soma do produto entre o custo nebuloso da cada caminho candidato e a vazão de tráfego de

cada LSP.

Os algoritmos foram testados em duas topologias diferentes, uma mais simples (I)

e outra complexa (II). Os parâmetros utilizados para avaliação de desempenho dos algoritmos

foram o tempo de execução e o custo da solução encontrada. Primeiramente foram feitas

cinco simulações em cada uma das topologias onde cada algoritmo era executado uma única

vez e os resultados apresentados, em seguida, devido ao fato de não encontrar resultados

satisfatórios para avaliar os algoritmos na topologia I apenas com a primeira simulação, foi

proposto uma nova simulação que consistia em executar cada um dos algoritmos por cem

vezes consecutivas, em cada uma das topologias. Por último foram realizados mais duas

simulações que executava os algoritmos cem vezes consecutivas para os arquivos da

topologia II e os resultados encontrados de cada algoritmo foram comparados entre eles.

Para a topologia I pode-se concluir com os resultados obtidos tanto com o AG

como o ACS, que o algoritmo de otimização está sendo pouco proveitoso para o sistema de

TE, já que, para a maior parte das simulações, desde a primeira geração é encontrado o

resultado tido como solução ótima ao final da execução. Com isso consegue-se concluir que a

topologia I possui um número muito pequeno de soluções válidas e levando-se em

consideração que a população inicial dos algoritmos é gerada de maneira aleatória

(respeitando apenas as restrições do problema), e levando-se em conta também que os

algoritmos de otimização necessitam de uma demanda de processamento, a utilização de um

algoritmo de otimização não será vantajoso para esta topologia simples. O próprio sistema de

Page 113: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

113

TE já possui implementado no CFLAG a criação de uma tabela de soluções válidas de

maneira aleatória, portanto, para a topologia I seria mais vantajoso utilizar esta tabela para

buscar a melhor solução que nela contêm e não utilizar um algoritmo de otimização.

Diferentemente da topologia I, para a topologia II observa-se a necessidade do

algoritmo de otimização. Como podemos notar nas simulações realizadas com o AG e com o

ACS, os algoritmos estão realmente otimizando as soluções, por exemplo, na simulação

descrita na seção 4.2.5 podemos ver na Tabela 16 a média da diminuição dos fitness entre a

primeira e a última geração de cada execução do algoritmo, o que comprova a convergência

dos algoritmos para as soluções ótimas. Os dois algoritmos mostraram-se eficientes, sempre

encontrando soluções muito próximas da ótima.

Este trabalho propunha fazer uma comparação entre os dois algoritmos

desenvolvidos e testados, AG e ACS. Neste sentido, a definição dos parâmetros nos dois

algoritmos foram os mais próximos possíveis e também foram realizadas simulações idênticas

com os dois algoritmos. A Tabela 16 apresenta os resultados de duas simulações com cada um

dos algoritmos, simulação esta que consistia em executar cem vezes consecutivas o algoritmo.

Consegue-se definir as vantagens e desvantagens da cada algoritmo baseados nos dados desta

tabela e das demais simulações realizadas neste trabalho. O AG mostrou-se mais eficiente no

que diz respeito ao tempo de execução, o AG foi aproximadamente seis vezes mais rápido que

o ACS. O ACS, por sua vez, mostrou-se um pouco mais eficiente quando tratamos dos custos

das soluções encontradas, pois apresentou menor média e menor desvio padrão dos custos das

soluções encontradas.

Fundamentado nas simulações efetuadas o nos resultados obtidos conclui-se que o

AG é mais eficiente para otimizar os recursos de rede em um domínio MPLS utilizando o

sistema de TE proposto por MAIA(2006), pois, apesar de ter apresentado uma pequena

desvantagem no que diz respeito ao fitness das soluções, apresentou uma grande vantagem no

que diz respeito ao tempo de execução.

Este trabalho apresentou resultados satisfatórios, porém mudanças podem ser

realizadas nos algoritmos buscando maior eficiência dos mesmos e novos testes podem ser

realizados utilizando outros parâmetros de avaliação. Pensando nisso pode-se propor as

seguintes trabalhos futuros:

• Alterar os parâmetros inicias dos algoritmos, como número de

cromossomos e formigas, números de gerações e iterações, buscando o equilíbrio

Page 114: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

114

entre tempo de execução e resultados obtidos, pois os algoritmos podem estar

“super parametrizados”, como visto na seção 4.2.4.

• Alterar os operadores genéticos do AG, como, por exemplo, a Seleção e

o Cruzamento.

• Inserir os algoritmos desenvolvidos no sistema de TE, para que os

mesmo possam ser testados junto à simulação do sistema e utilizar outros

parâmetros para avaliar a eficiência dos algoritmos de otimização, como os

indicadores de desempenho da rede.

Page 115: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

115

6. REFERÊNCIAS BIBLIOGRÁFICAS

ABACHIZADEH, M.; TAHANI, M., An ant colony optimization approach to multiobjective

optimal design of symmetric hybrid laminates for maximum fundamental frequency and

minimum cost. Structural and Multidisciplinary Optimization, vol. 37, 2009.

ÁVILA, S. L. et al. Otimização – Conceitos Básicos, Ferramentas e Aplicações. Revista de

Automação e Tecnologia da Informação, Florianópolis, v.2, n.1, 2003.

BENI, G. The concept of cellular robotic systems. In Proceedings 1988 IEEE Int. Symp. On

Intelligent Control, 1988.

BEZ, E. D. Procedimento de Representação de Soluções em Otimização Global: Aplicação

em Modelos de Interação Espacial. Tese (Doutorado em Engenharia de Produção),

Universidade Federal de Santa Catarina, Florianópolis, 2005.

BLACK, U. MPLS and Label Switching Networks, Second Edition, Upper Saddle River:

Prantice Hall, 2002.

BONABEAU, E.; DORIGO, M.; THÉRAULAZ, G. From Natural to Artificial Swarm

Inteligence. Oxford University Press, 1999.

BOOKER, L. B., GOLDBERG, D. E. & HOLLAND, J. H. Classifier Systems and Genetic

Algorithms. Artificial Intelligence, vol. 40, 1989.

BRAGA, A. P.; LUDENIR, T. B.; CARVALHO, A. C. P. L. F. Redes Neurais Artificiais –

Teoria e aplicações. LTC, 2000.

CRAWLEY E.; NAIR R., RAJAGOPALAN, B.; SANDICK, H. A framework for qosbased

routing in the internet. RFC 2386, agosto 1998. Disponível em:

http://www.rfcarchive.org/getrfc.php?rfc=2386. Acesso em: Outubro de 2009.

DAVIS, L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.

DORIGO, M. Optimization, Lerning and Natuaral Algorithms. Ph.D Thesis, Politécnico de

Milario, 1992.

Page 116: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

116

DORIGO, M.; CARO, G. The ant colony optimization meta-heuristic. In: CORNE, D.;

DORIGO, M.; GLOVER, F. New ideas optimization. Londres, Reino Unido: McGraw-Hill,

1999.

DORIGO, M.; GAMBARDELLA, L. M. Ant colony system: A cooperative learning

approach to the traveling salesman problem. IEEE Transactions on Evolutionary

Computation, vol.1, nº 1, 1997.

DORIGO, M.; MANIEZZO, V.; COLORNI, A. Ant system: Optimization by a colony of

cooperatings agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996.

DORIGO, M.; MANIEZZO, V.; COLORNI, A. Positive feedback as a search strategy,

Technical Report 91-016, Dipartimento di Elettronica e Informazione, Politecnico di Milano,

1991.

DORIGO, M.; STÜTZLE T. Ant colony optimization. MIT Press, Cambridge, 2004.

ELLABIB, I.; BASIR, O. A. E CALAMAI, P. A new Ant Colony System updating strategy

for Vehicle Routing Problem with Time windows. MIC2003: The Fifth Metaheuristics

International Conference, 2003.

FARMER, J. D.; TOFFOLI, T.; WOLFRAM, S. Cellular Automata: Proceedings of an

Interdisciplinary Workshop at Los Alamos. New Mexico, North-Holland, Amsterdam, 1983.

FRANKS, N. R. Army Ants: A Collective Intelligence. Scientific American, vol. 7, 1989.

GAERTNER, D. Natural Algorithms for Optimization Problems. Final Year Project Report,

2004.

GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine Learning.

Addison Wesley, 1989.

GOLDBERG, D. E.; HOLLAND, J. H. Genetic algorithms and machine learning:

Introduction to the special issue on genetic algorithms. Machine Learning, 1988.

GOSS, S.; ARON, S.; DENEUBOURG, J. L.; PASTEELS, J. M. Self-organized shortcuts in

the Argentine ant. Naturwissenschaften, v. 76, 1989.

Page 117: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

117

GOZDECKI, J.; JAJSZCZYK, A.; STANKIEWICZ, R. Quality of Service Terminology in

IP Networks. In: IEEE Communications Magazine, vol. 41, n.3, março 2003.

HEITKOETTER, J., BEASLEY, D. The hitch-hiker's guide to evolutionary computation: a

list of frequently asked questions (FAQ). 1994. Disponível em:

ftp://rtfm.mit.edu:/pub/usenet/news.answers/ai-faq/genetic. Acesso em: Outubro de 2009.

HERRERA, F.; LOZANO, M.; VERDEGAY, J. L. Tackling Real-Coded Genetic

Algorithms: Operators and Tools for Behavioural Analysis. Artificial Intelligence Review. v.

12, 1998.

HOLLAND, J. H. Adaptation in Natural and Artificial Systems. The MIT Press, 1992.

HOLLAND, J. H. Adaptation in Natural and Artificial Systems. The University of Michigan

Press, 1975.

HÖLLDOBLER, B.; WILSON, E. O. Journey to the Ants. Bellknap Press/Harvard

University Press, 1994.

KOZA J. R. Genetic programming: on the programming of computers by means of natural

selection. MIT Press, 1992.

LINDEN, R. Algoritmos Genéticos: Uma importante ferramenta da Inteligência

Computacional. Rio de Janeiro: Brassport, 2006.

MAIA, N. A. Engenharia de Tráfego em Domínio MPLS Utilizando Técnicas de Inteligência

Computacional. 2006. 192 f. Tese (Doutorado em Engenharia Elétrica) – Programa de Pós-

Graduação em Engenharia Elétrica, Universidade Federal de Minas Gerais, Belo Horizonte,

2006. Disponível em:

http://www.ppgee.ufmg.br/defesas/855D.PDF?PHPSESSID=3b42ed5f702704217569eb18f0

ac91a9. Acesso em: Setembro de 2009.

MICHALEWICZ, Z., SCHOENAUER, M. Evolutionary Algorithms for Constrained

Parameter Optimization Problems. Evolutionary Computation, vol. 4, no. 1, 1996.

NILSSON, N. J. Principals of artificial intelligence. New York: Birkhauser, 1982.

OLIVEIRA, S. S. de. Análise de tráfego na integração de redes IP e ATM usando simulação.

Dissertação de Mestrado. Programa de Pós-Graduação em Ciência da Computação/UFSC,

Page 118: ALGORITMOS GENÉTICOS E COLÔNIA DE FORMIGAS APLICADAS  EM UM SISTEMA DE ENGENHARIA DE TRÁFEGO

118

2001.

SOCHA, K.; DORIGO, M. Ant colony optimization for continuous domain. European

Journal of Operational research, 2008.

SPEARS, W. M. Simple Subpopulation Schemes, Proceedings of Evolutionary Programming

Conference. World Scientific, International Edition, 1994.

VASCONCELOS, J. A., SALDANHA, R. R., KRӒHENBÜHL, L., NICOLAS, A.

Algoritmo Genético Aplicado à Otimização em Eletromagnetismo. Primeiro Congresso

Brasileiro de Eletromagnetismo, Florianópolis, 1995.

YEPES, I. Uma incursão aos algoritmos genéticos. 2000. Disponível em:

http://www.geocities.com/igoryepes/. Acesso em: Setembro de 2009.