Embed Size (px)
Citation preview
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE TECNOLOGIA
PROGRAMA DE ENGENHARIA DE PRODUÇÃO
ALGORITMO MEMÉTICO COM INFECÇÃO VIRAL: UMA APLICAÇÃO AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
por
FÁBIO FRANCISCO DA COSTA FONTES
LICENCIADO EM MATEMÁTICA, UFRN, 2001.
DISSERTAÇÃO SUBMETIDA AO PROGRAMA DE ENGENHARIA DE PRODUÇÃO DA UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE COMO PARTE DOS
REQUISITOS NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE
MESTRE EM CIÊNCIAS EM ENGENHARIA DE PRODUÇÃO
DEZEMBRO, 2006
© 2006 FÁBIO FRANCISCO DA COSTA FONTES TODOS OS DIREITOS RESERVADOS.
O autor, aqui designado, concede ao Programa de Engenharia de Produção da Universidade Federal do Rio Grande do Norte permissão para reproduzir, distribuir, comunicar ao público, em papel ou meio eletrônico, esta obra, no todo ou em parte, nos termos da Lei.
Assinatura do Autor: _________________________________________ APROVADO POR: ___________________________________________________________ Prof. Dario José Aloise, D.Sc. – Orientador, Presidente ___________________________________________________________ Prof. Otoniel Marcelino de Medeiros, D.Sc. – Membro Examinador ___________________________________________________________ Prof. Plácido Rogério Pinheiro, D.Sc. – Membro Examinador Externo
ii
FONTES, FÁBIO FRANCISCO DA COSTA
ALGORITMO MEMÉTICO COM INFECÇÃO VIRAL: UMA APLICAÇÃO AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO [Rio Grande do Norte] 2006.
xii, 72 p. 29,7 cm (UFRN/PEP, Mestrado, Engenharia de Produção, 2006).
Tese de Mestrado - Universidade Federal do Rio Grande do Norte, Programa de Engenharia de Produção.
1. Pesquisa Operacional. 2. Algoritmos Evolutivos. 3.Infecção Viral. 4. Caixeiro Viajante Assimétrico. I. UFRN/PEP II. Título (série).
iii
CURRICULUM VITAE
Fábio Francisco da Costa Fontes, filho de Francisco Fontes de Andrade e de
Terezinha da Costa Fontes, nascido no dia 01 de Setembro de 1976, na cidade
de Natal, Estado do Rio Grande do Norte.
Titulação
• Licenciado em Matemática pela Universidade Federal do Rio Grande do Norte –
UFRN, no ano de 2001.
• Especialista em Técnicas e Ferramentas de Apoio à Decisão pelo Departamento de
Informática e Matemática Aplicada – DIMAP, da Universidade Federal do Rio
Grande do Norte – UFRN, no ano de 2003.
Atuação em Grupos de Pesquisa
• Nome do Grupo: Heurísticas e paralelismo para problemas de otimização e de
bioinformática.
Instituição: Pontifícia Universidade Católica do Rio de Janeiro - PUC/RJ -
Departamento de Informática.
iv
Dedico este trabalho a todos aqueles que direta ou indiretamente contribuíram para a
minha formação acadêmica. Desde os meus professores do primário que apesar de serem
pouco valorizados na hora de sua remuneração, faziam seu trabalho com muito amor e
dedicação, passando pela minha família que sempre procurou deixar bem claro que a
melhor forma de crescermos financeiramente e como cidadãos de bem, conscientes dos
nossos direitos, seria através da educação, e chegando até aos meus professores acadêmicos
que se dispunham, através do conhecimento adquirido ao longo de décadas, a manter viva e
com qualidade a Universidade Pública deste querido Brasil.
v
AGRADECIMENTOS
Agradeço Inicialmente a Deus por ter me abençoado com saúde, sabedoria e muita
força de vontade para conquistar mais esta importante etapa da minha vida. Agradeço também
a Nossa Senhora que acredito estar sempre intercedendo por mim junto a Deus.
Agradeço ao meu Pai, Francisco Fontes, que apesar de ter partido desta vida quando
eu tinha apenas 9 anos, conseguiu deixar inúmeros exemplos de como deve agir um pai, um
filho, um irmão, um esposo e um homem. Agradeço a minha Mãe, Terezinha, minhas Tias
Geralda e Irene, aos meus irmãos Denes e Fernanda e ao meu Avô Antônio, por sermos
sempre tão unidos, nunca deixando faltar em nosso lar muito amor, carinho, educação e
respeito ao próximo. Agradeço também a minha namorada, Adriana Carla, por estar sempre
ao meu lado, apesar das minhas ausências nas horas de estudos e pesquisas, pelo seu amor,
por ser parte da minha família e permitir-me fazer parte da sua boa família.
Agradeço aos meus familiares: tios, tias, primos e primas, e a todos os meus amigos
pela convivência tão harmoniosa que possuímos, fundamentais para encher a nossa alma de
alegria. Aos novos amigos que conquistei no mestrado por terem enriquecido as nossas aulas
com informações e bom humor, espero sempre manter a amizade. Em especial agradecer a
Marcos Galvão e Werner que contribuíram para que nossas aulas de Pesquisa Operacional
fossem horas de trocas de bons conhecimentos, a Solange pela ajuda no Abstract e,
principalmente, o Alisson Guedes, por ter me ajudado a programar as idéias desenvolvidas
neste trabalho.
Agradeço aos meus anjos da guarda que conseguem aparecer em locais diversos, em
momentos importantes, através de pessoas incríveis e conseguem cumprir seu papel de
proteger-me. Obrigado a Marcelo Nunes e Benício Basílio, pois sem os dois eu não teria
conseguido conciliar o estudo no mestrado com o trabalho.
Agradeço a todos que fazem parte do PEP, por terem me proporcionado um ensino de
excelência neste mestrado.
E por fim, porém tão importante quanto todos citados anteriormente, gostaria de
agradecer ao meu Orientador prof. Dr. Dario José Aloise, por ter sido um Orientador
incansável, orientando-me até nas manhãs de domingo e cobrando resultados do trabalho até
em meus sonhos. Como ser sociável eu fico contente em ter conquistado mais um amigo e
como orientando espero que tenha ficado a altura do meu Orientador.
vi
Resumo da Dissertação apresentada à UFRN/PEP como parte dos requisitos necessários para
a obtenção do grau de Mestre em Ciências em Engenharia de Produção.
ALGORITMO MEMÉTICO COM INFECÇÃO VIRAL: UMA APLICAÇÃO AO
PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
FÁBIO FRANCISCO DA COSTA FONTES
Dezembro/2006
Orientador: Dario José Aloise
Curso: Mestrado em Ciências em Engenharia de Produção
A Otimização Combinatória é uma área fundamental para empresas que buscam vantagens
competitivas nos diversos setores produtivos, e o Problema do Caixeiro Viajante Assimétrico,
o qual se classifica como um dos mais importantes problemas desta área, devido a ser um
problema da classe NP-difícil e também por possuir diversas aplicações práticas, tem
despertado interesse de pesquisadores no desenvolvimento de Metaheurísticas cada vez mais
eficientes para auxiliar na sua resolução, como é o caso do Algoritmo Memético, o qual é um
algoritmo evolutivo que se utiliza dos operadores genéticos em combinação com um
procedimento de busca local. Este trabalho explora a técnica de Infecção Viral em um
Algoritmo Memético, onde a infecção substitui o operador de mutação por conseguir uma
rápida evolução ou extinção de espécies (KANOH et al., 1996), proporcionando uma forma
de aceleração e melhoria da solução. Para isto se desenvolveu quatro variantes de Infecção
Viral aplicadas no Algoritmo Memético para resolução do Problema do Caixeiro Viajante
Assimétrico, onde o agente e o vírus passam por um processo de Simbiose, as quais
favoreceram a obtenção de um algoritmo evolutivo híbrido e computacionalmente viável.
Palavras-Chave: Otimização Combinatória, Problema do Caixeiro Viajante Assimétrico,
Algoritmo Memético, Infecção Viral.
vii
Abstract of Dissertation presented to UFRN/PEP as fullfilment of requirements to the degree
of Master of Science in Production Engineering
MEMETIC ALGORITHM WITH VIRAL INFECTION: AN APPLICATION TO THE
ASSIMETRIC TRAVELLING SALESMAN PROBLEM
FÁBIO FRANCISCO DA COSTA FONTES
December/2006
Dissertation Supervisor : Dario José Aloise
Program: Master of Science in Production Engineering
The Combinatorial Optimization is a basic area to companies who look for competitive
advantages in the diverse productive sectors and the Assimetric Travelling Salesman Problem,
which one classifies as one of the most important problems of this area, for being a problem
of the NP-hard class and for possessing diverse practical applications, has increased interest
of researchers in the development of metaheuristics each more efficient to assist in its
resolution, as it is the case of Memetic Algorithms, which is a evolutionary algorithms that it
is used of the genetic operation in combination with a local search procedure. This work
explores the technique of Viral Infection in one Memetic Algorithms where the infection
substitutes the mutation operator for obtaining a fast evolution or extinguishing of species
(KANOH et al, 1996) providing a form of acceleration and improvement of the solution . For
this it developed four variants of Viral Infection applied in the Memetic Algorithms for
resolution of the Assimetric Travelling Salesman Problem where the agent and the virus pass
for a symbiosis process which favored the attainment of a hybrid evolutionary algorithms and
computational viable.
Keywords: Combinatorial Optimization, Assimetric Travelling Salesman Problem, Memetic
Algorithms, Viral Infection.
viii
SUMÁRIO
LISTA DE TABELAS...................................................................................................xi
LISTA DE FIGURAS ...................................................................................................xi
LISTA DE ALGORITMOS .......................................................................................xii
Capítulo 1 - INTRODUÇÃO........................................................................................1
1.1 - CONTEXTUALIZAÇÃO ..............................................................................................1
1.2- OBJETIVOS DA PESQUISA .........................................................................................4
1.2.1- Gerais...................................................................................................................4
1.2.2- Específicos ...........................................................................................................4
1.3- RELEVÂNCIA DA PESQUISA .....................................................................................4
1.3.1- Relevância Teórica ...............................................................................................4
1.3.2- Relevância Prática: ...............................................................................................5
1.4 – ORGANIZAÇÃO DA DISSERTAÇÃO........................................................................5
Capítulo 2 – REVISÃO TEÓRICA ...........................................................................7
2.1 – OTIMIZAÇÃO COMBINATÓRIA...............................................................................7
2.1.1 – O Problema do Caixeiro Viajante (PCV).............................................................9
2.1.2 – Aplicações Práticas do PCV ................................................................................9
2.1.3 – Variantes do PCV .............................................................................................11
2.2 – COMPLEXIDADE DE PROBLEMAS .......................................................................14
2.2.1 – Formulação Matemática do PCVA e complexidade...........................................14
2.3 – HEURÍSTICAS ...........................................................................................................15
2.3.1 – Heurísticas Construtivas....................................................................................15
2.3.1.1 – Vizinho Mais Próximo ...............................................................................16 2.3.1.2 – Inserção Mais Próxima...............................................................................17 2.3.1.3 – Inserção Mais Distante ...............................................................................17 2.3.1.4 – Inserção Mais Barata ..................................................................................17
ix
2.3.1.5 – Inserção Pelo Maior Ângulo .......................................................................18 2.3.1.6 – Método das Economias ..............................................................................18 2.3.1.7 – Heurística de Christofides ..........................................................................19 2.3.1.8 – Heurística GKS ..........................................................................................20
2.3.2 – Heurísticas de Busca Local ...............................................................................20
2.3.2.1 – Melhoria Iterativa.......................................................................................21 2.3.2.2 – Descida Mais Rápida..................................................................................21 2.3.2.3 – Método das k-substituições ou k-opt ...........................................................21
2.4 – METAHEURÍSTICAS ................................................................................................22
2.4.1- Analogia com Métodos Físicos ...........................................................................22
2.4.2 - Estratégias de Cálculos com Intensificação da Busca Local ...............................23
2.4.3 –Analogia com Processos Naturais ......................................................................25
2.4.4 – Métodos Híbridos (Algoritmo Memético) .........................................................27
Capítulo 3 – ALGORITMOS EVOLUTIVOS E INFECÇÃO VIRAL.........28
3.1 - ALGORITMOS EVOLUTIVOS ..................................................................................28
3.1.1 - Algoritmo Genético ...........................................................................................29
3.1.1.1 - O Cromossomo ...........................................................................................30 3.1.1.2 – A Seleção ...................................................................................................31 3.1.1.3 – O Cruzamento ............................................................................................34 3.1.1.4 – A Mutação .................................................................................................39
3.1.2 - Algoritmo Memético .........................................................................................41
3.1.2.1 – A Busca Local............................................................................................42 3.1.2.2 – A Geração ..................................................................................................42
3.2 - INFECÇÃO VIRAL.....................................................................................................43
3.2.1 – O Vírus .............................................................................................................44
3.2.2 – A População de Vírus .......................................................................................44
3.2.3 – A Infecção ........................................................................................................45
3.3 - O ALGORITMO MEMÉTICO COM INFECÇÃO VIRAL..........................................45
3.3.1 - Implementação 1 ...............................................................................................46
3.3.1.1 - A Infecção ..................................................................................................47 3.3.1.2 - A Simbiose .................................................................................................49
3.3.2 – Implementação 2...............................................................................................51
3.3.3 – Implementação 3...............................................................................................52
x
3.3.4 - Implementação 4 ...............................................................................................55
Capítulo 4 - EXPERIMENTAÇÃO .........................................................................57
4.1 - METODOLOGIA ........................................................................................................57
4.1.1 - Universo e Amostra ...........................................................................................58
4.1.2 - Coleta de Dados.................................................................................................58
4.1.3 - Tratamento dos Dados .......................................................................................58
4.2 – RESULTADOS E DISCUSSÕES................................................................................58
Capítulo 5 – CONCLUSÕES E RECOMENDAÇÕES......................................64
5.1 - CONCLUSÃO .............................................................................................................64
5.2 - RECOMENDAÇÕES PARA FUTURAS PESQUISAS ...............................................64
REFERÊNCIAS BIBLIOGRÁFICAS....................................................................66
xi
LISTA DE TABELAS
Tabela 3. 1 – Mapa de Adjacência do Edge Recombination Crossover .................................38
Tabela 4. 1 – Resultados da Implementação AMIV 1 x Algoritmo Memético Clássico .........60
Tabela 4. 2 – Resultados da Implementação AMIV 2 x Algoritmo Memético Clássico .........61 Tabela 4. 3 – Resultados da Implementação AMIV 3 x Algoritmo Memético Clássico..........62 Tabela 4. 4 – Resultados da Implementação AMIV 4 x Algoritmo Memético Clássico..........63
LISTA DE FIGURAS
Figura 1. 1 - A cadeia de Valor...............................................................................................2
Figura 2. 1 – Unidade Móvel de Pistoneio ............................................................................13
Figura 2. 2 - Esquema de funcionamento do método K-opt...................................................22
Figura 2. 3 - Esquema de funcionamento da Metaheurística VNS.........................................25
Figura 3. 1 - Representações do Cromossomo ......................................................................30
Figura 3. 2 - Representação Ordinal .....................................................................................31
Figura 3. 3 – Roleta de cromossomos representados pela porcentagem de fitness .................32
Figura 3. 4 - Fluxograma do método de seleção por torneio com tamanho igual a 2 para um
problema de minimização .............................................................................................33
Figura 3. 5 – Crossover de 1 ponto .......................................................................................34
Figura 3. 6 – Crossover de 2 pontos......................................................................................35
Figura 3. 7 – Operador Clássico de Mutação ........................................................................40
Figura 3. 8 - Representações do Agente................................................................................42
Figura 3. 9 - Exemplo de um vírus para um cromossomo de representação real ....................44
Figura 3. 10 – Processo de Transcrição.................................................................................48
Figura 3. 11 - Aumento do Vírus ..........................................................................................49
xii
Figura 3. 12 – Processo de Transdução.................................................................................51
Figura 3. 13 – Normalização da população variável de vírus.................................................52
LISTA DE ALGORITMOS
Algoritmo 2. 1 – Algoritmo Vizinho Mais Próximo..............................................................16
Algoritmo 2. 2 – Algoritmo Inserção Mais Próxima .............................................................17
Algoritmo 2. 3 – Algoritmo Inserção Mais Barata ................................................................18
Algoritmo 2. 4 – Algoritmo Inserção Pelo Maior Ângulo .....................................................18
Algoritmo 2. 5 – Algoritmo Método das Economias.............................................................19
Algoritmo 2. 6 – Algoritmo de Christofides..........................................................................20
Algoritmo 2. 7 – Algoritmo GKS .........................................................................................21
Algoritmo 3. 1 – Algoritmo Genético Clássico .....................................................................29
Algoritmo 3. 2 – Algoritmo Memético Clássico ...................................................................41
Algoritmo 3. 3 – Algoritmo Genético Com Infecção Viral....................................................43
Algoritmo 3. 4 – Algoritmo Memético Com Infecção Viral 1 ...............................................46
Algoritmo 3. 5 – Heurística de Inserção Arbitrária ...............................................................47
Algoritmo 3. 6 – Algoritmo Infecção....................................................................................48
Algoritmo 3. 7 – Simbiose 1.................................................................................................50
Algoritmo 3. 8 – Algoritmo Memético Com Infecção Viral 2 ...............................................52
Algoritmo 3. 9 – Algoritmo Memético Com Infecção Viral 3 ...............................................53
Algoritmo 3. 10 – Simbiose 2...............................................................................................54
Algoritmo 3. 11 – Simbiose 3...............................................................................................55
1
Capítulo 1
Introdução
Este capítulo apresenta a importância da Otimização Combinatória diante do cenário
competitivo existente nas indústrias, exemplificando situações da cadeia de valor na qual o
uso de Metaheurísticas vem se tornando uma alternativa cada vez mais viável na obtenção de
uma vantagem competitiva através de minimização do tempo, mão-de-obra e insumos. Tal
cenário funciona como uma motivação para o desenvolvimento deste trabalho, justificando,
assim, as necessidades da pesquisa com os objetivos a serem alcançados e sua importância
social, econômica e científica.
Para maior clareza do assunto, o capítulo foi dividido nos seguintes tópicos:
contextualização, objetivos da pesquisa, relevância da pesquisa e organização da dissertação,
sendo este último uma descrição de como as informações foram distribuídas ao longo desta
dissertação.
1.1 - Contextualização
A economia mundial hoje está forçando as empresas a buscarem vantagens
competitivas através do tempo. A cadeia de valor (Figura 1.1), que é o conjunto de atividades,
que acontecem dentro de uma empresa, com a finalidade de esta realizar seus negócios,
necessita que suas atividades estejam muito bem organizadas e interligadas, para que a
vantagem de tempo que, por exemplo, obtém-se na produção, não seja perdida na venda ou
distribuição, assim como a aquisição de insumos não atrase o início da fabricação, entre
outros.
2
Infra-estrutura empresarial
Gerenciamento de recursos humanos
Desenvolvimento de tecnologias
Aquisição de insumos
Logística interna
Operações Logística externa
Marketing e vendas
Prestação de
serviços
Ativida-des-Meio
Atividades-fim
Fonte: (Adaptado de Porter & Millar, 1985 apud Laurindo).
Figura 1. 1 - A cadeia de Valor
Nas empresas, a agilidade nas vendas e na distribuição procura realizar o desejo dos
clientes em um curto tempo, oferecendo-lhes, no momento da compra, não apenas o fator
preço, mas também o tempo no qual o produto adquirido estará em suas mãos. Na aquisição
de insumos, o fator primordial não deve ser apenas o fornecedor que oferece o menor preço,
mas aqueles que consigam atender aos pedidos dentro dos prazos mínimos, oferecendo
sempre matéria-prima de qualidade. Logisticamente falando, a facilidade de se fazer negócios
significa que os fornecedores atendam aos compromissos e as entregas cheguem ao local e
hora acertados (STALK apud MONTGOMERY e PORTER, 1998).
Fator importante também na economia de tempo acontece durante a produção, quando
o ambiente oferece uma seqüência ótima de matéria-prima entre células de manufatura. Este
recurso consegue não só economia de tempo, mas economia de mão-de-obra (menos gasto
com pessoal).
No desenvolvimento tecnológico, procuram-se equipamentos que executem trabalhos
repetitivos com maior perfeição e menores desperdícios de tempo, por exemplo, na
otimização do funcionamento de equipamentos automáticos de perfuração, soldagem, etc.
O gerenciamento de recursos humanos procura distribuir tarefas, visando minimizar
sem sobrecarregar pessoal e equipamentos, pois os produtos finais têm prazos a serem
cumpridos.
Por estes e outros exemplos, e conscientes de que não basta apenas fabricar mais e
melhor que seus concorrentes, e sim que estes produtos sejam fabricados com gastos mínimos
Margem
3
e estejam acessíveis às pessoas em tempos cada vez menores, é que estudos na área de
Otimização Combinatória merecem uma maior atenção.
A Otimização Combinatória funciona como uma alternativa na busca de melhores
resultados para vários problemas práticos, como: alocação de centros de distribuição; corte e
empacotamento; escalonamento de tarefas; roteamento de veículos, tráfico aéreo, etc. Um
célebre problema nesta área é o que aborda o assunto de minimização de rotas hamiltonianas,
conhecido como problema do caixeiro viajante (PCV). O enunciado diz que um caixeiro
viajante tem que visitar n cidades diferentes, iniciando e encerrando sua viagem na cidade de
partida e passando por todas as outras uma única vez, não importando a ordem com que as
cidades são visitadas.
O PCV está classificado como um problema de Otimização Combinatória pertencente
à classe dos problemas NP-difíceis, o que significa dizer que, apesar do uso de computadores
de última geração, não se pode determinar a solução exata para problemas de grande porte
(problemas práticos) em um tempo computacional viável.
Devido a isso é que, desde a década de 70, tem havido cada vez mais interesse pelo
estudo de métodos Heurísticos, isto é, algoritmos que buscam encontrar boas soluções
próximas à solução ótima e em um tempo extremamente rápido (polinomial).
Esse esforço de pesquisa levou ao surgimento, na década de 90, das heurísticas
inteligentes, denominadas de Metaheurísticas, que resolvem os problemas de otimização
combinatória NP-difícil de uma maneira mais flexível e para problemas de porte ainda
maiores e com mais precisão, além de exigir pouco esforço computacional. Pois utilizam
procedimentos de buscas em vizinhanças que evitam uma parada prematura em ótimos locais,
direcionando a busca para uma solução aproximada, tão boa quanto possível do ótimo global
desejado no problema proposto. Dentre estas, destacam-se: os Métodos Seqüenciais
(Simulated Annealing, Busca Tabu, GRASP, entre outros), e os Populacionais (Colônia de
Formigas; Otimização por Nuvem de Partículas; Algoritmo Genético (AG); entre outros).
O Algoritmo Genético, inspirado na teoria da evolução de Charles Darwin, é um
algoritmo probabilístico desenvolvido com a finalidade de ser aplicado em problemas
diversos de Otimização Combinatória. Alguns autores como (NAKAHARA e SAGAWA,
1986 apud KANOH et al., 1996), propõem que, na teoria da evolução, o material genético
pode ser transferido de um indivíduo para outro através de vírus, ou seja, um vírus carregando
material genético pode infectar e transportar informações genéticas de um indivíduo para
4
outro. No caso da Memética, a evolução de uma população ocorre não apenas através dos
operadores genéticos, mas também através da evolução cultural (busca local), ou seja, um
indivíduo pode tornar-se forte ao longo de sua geração. Analogamente, o vírus memético tenta
passar informações (características importantes) ao longo de gerações. Este trabalho propõe o
uso da infecção viral no algoritmo memético.
1.2- Objetivos da Pesquisa
1.2.1- Gerais
Esta pesquisa tem por objetivo propor e avaliar o uso de infecção viral em um
algoritmo evolutivo (Algoritmo Memético) para a resolução de problemas de Otimização
Combinatória NP-difícil. O Problema do Caixeiro Viajante Assimétrico através de instâncias
disponibilizadas na TSPLIB1 é utilizado para validação da proposta.
1.2.2- Específicos
Para atingir-se o objetivo maior deste trabalho, faz-se necessário passar por algumas
etapas, consideradas essenciais, que são os objetivos específicos:
• Desenvolver e aplicar o Algoritmo Memético com infecção viral ao Problema do
Caixeiro Viajante Assimétrico;
• Desenvolver um método de Infecção Viral que faz uso de uma população fixa de
vírus e de uma população variável de vírus;
• Desenvolver um método de Infecção Viral que faz uso de um processo de
Simbiose, no qual o agente do Algoritmo Memético e o vírus obtêm benefícios
após interagirem;
• Comparar os resultados obtidos nas implementações desenvolvidas com os obtidos
pelo Algoritmo Memético;
1.3- Relevância da Pesquisa
1.3.1- Relevância Teórica
1 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
5
Científica: Este estudo colabora com o enriquecimento da literatura sobre Metaheurísticas
com infecção viral, as quais são algoritmos heurísticos inteligentes que podem ser usados em
problemas diversos. Em especial este trabalho aborda o Problema do Caixeiro Viajante
Assimétrico que é um problema de roteamento pertencente aos problemas de Otimização
Combinatória da classe NP - difícil.
Acadêmica: Sua contribuição acadêmica tem relevância significativa; seguindo a
classificação da Associação Brasileira de Engenharia de Produção (ABEPRO2), este trabalho
está dentro da Programação Matemática na área de Pesquisa Operacional. No Conselho
Nacional de Desenvolvimento Científico e Tecnológico (CNPq3), o mesmo enquadra-se na
Pesquisa Operacional, que pertence à área do conhecimento de Engenharias. No Programa de
Engenharia de Produção da Universidade Federal do Rio Grande do Norte (PEP/UFRN4), ele
foi desenvolvido na área de Tecnologias de Gestão da Produção e Operações, mais
especificamente na linha de Pesquisa Operacional.
1.3.2- Relevância Prática:
Esta pesquisa tem fundamental importância, não apenas nas empresas que exploram a
logística e transporte/entrega de mercadorias, pois o PCV aparece em diversas outras
situações práticas, como:
Programação de operações de máquinas em manufatura; programação de transporte
entre células de manufatura; otimização do movimento de ferramentas de corte; otimização de
perfurações de furos e inserção de componentes eletrônicos em placas de circuito impresso;
na solução de problemas de seqüenciamento de DNA; na solução de problemas de
programação e distribuição de tarefas em plantas; análise de estruturas de cristais na
cristalografia por Raios-X; etc.
1.4 – Organização da Dissertação
Esta dissertação esta organizada em 5 capítulos, a saber:
O capítulo 1 consta da introdução da dissertação, em que se esclarecem as
necessidades teóricas e práticas desta pesquisa, mostrando os objetivos que se deseja alcançar 2 www.abepro.org.br 3 www.cnpq.br 4 www.pep.ufrn.br
6
e também, como está documentado ao longo dos capítulos, o conhecimento construído neste
trabalho;
O capítulo 2 descreve o conceito de Otimização Combinatória com seus principais
problemas e suas áreas de aplicações. Relata também formulações para o PCVA, bem como
as principais Heurísticas e Metaheurísticas utilizadas para a resolução deste problema.
O Capítulo 3 relata as características dos algoritmos evolutivos: Algoritmo Genético e
Memético. Descreve as implementações do Algoritmo Memético com Infecção Viral
desenvolvido neste trabalho.
O capítulo 4 apresenta a metodologia utilizada e os resultados obtidos após se
aplicarem os algoritmos desenvolvidos às instâncias do PCVA, existentes na TSPLIB, além
das discussões geradas com os resultados.
Por fim, o capítulo 5 relata as conclusões obtidas após toda a experiência da pesquisa,
descrevendo as metas atingidas, recomendando áreas de aplicações práticas para o trabalho
desenvolvido e sugerindo trabalhos futuros.
7
Capítulo 2
Revisão Teórica
Este capítulo apresenta uma revisão sucinta dos principais problemas de Otimização
Combinatória, justificando o uso do Problema do Caixeiro Viajante através da sua
complexidade, aplicações práticas e pela quantidade de suas variantes. Descreve também as
principais Heurísticas Construtivas e de Refinamento utilizadas no problema do Caixeiro
Viajante Assimétrico e, por fim, relata as principais Metaheurísticas em suas classificações
quanto à analogia com métodos físicos, estratégias de cálculos com intensificação da busca
local, analogia com processos naturais e métodos híbridos.
Para se conseguir uma estrutura clara e coesa, este capítulo foi dividido nos tópicos:
Otimização Combinatória, Complexidade de Problemas, Heurísticas e Metaheurísticas.
2.1 – Otimização Combinatória
Na Matemática Discreta, dado um conjunto finito, estudam-se os arranjos,
grupamentos, ordenações ou seleções de uma coleção de subconjuntos deste conjunto, que em
geral, constituem um conjunto finito dotado de estruturas particulares. Um exemplo seria o
problema da existência de um Ciclo Hamiltoniano em um dado grafo, o qual pode ser
resolvido pela permutação de vértices (BOAVENTURA NETO, 2006).
Porém, quando se pretende obter o melhor arranjo, grupamento, ordenação ou seleção,
entra-se no campo da Otimização Combinatória (CAMPELLO e MACULAN, 1994).
Assim, dado um conjunto de itens E={1.2,...,n}, onde cada ítem possui um custo
associado; e, uma série de restrições que devem ser respeitadas, o Problema de Otimização
Combinatória (POC) consiste em escolher dentre os subconjuntos viáveis (F⊆ 2E) aquele que
8
apresenta o menor custo ou maior lucro (S*∈F, tal que c(S*)≤ c(S),∀S∈F), dependendo se
no problema deseja-se minimizar ou maximizar (c(S*)≥ c(S)) a função objetivo (c:F �ℜ),
onde c(S) representa a soma dos custos (lucros) dos elementos de cada subconjunto S.
Alguns exemplos clássicos de POC são:
• O Problema da Mochila (Knapsack Problem): dada uma lista de objetos com custos
associados (preço, importância, etc), e uma mochila (caixa, contêiner, etc) com o seu
limite de capacidade, o desafio é escolher os objetos a serem carregados dentro da
mochila e que satisfaçam a restrição de capacidade da mesma, otimizando o valor do
carregamento realizado.
• O Problema do Número Cromático em Grafos: nesse problema, o objetivo é colorir
todos os vértices com o menor número possível de cores, de modo que os vértices
adjacentes não tenham a mesma cor.
• O Problema de p-medianas: Em um problema de localização, deseja-se estabelecer os
locais onde serão sediadas facilidades (fábricas, depósitos, hospitais, escolas, etc.) para
atender, da melhor maneira possível, a um conjunto espacialmente distribuído de
pontos de demanda. O problema de p-medianas é um problema clássico de
localização. O objetivo é determinar os locais de p facilidades (denominadas
medianas) em uma rede de n nós, de modo a minimizar a soma das distâncias entre
cada nó de demanda e a mediana mais próxima.
• Problema de Escalonamento (Scheduling Problem): Dado um conjunto de tarefas a
serem realizadas e dispondo-se de vários recursos (máquinas, homens, etc) que podem
realizar tais tarefas, o problema consiste em identificar a forma como os recursos
devem ser alocados as tarefas, tal que, o conjunto de tarefas seja executado no menor
tempo possível.
• Problema de Corte: Neste problema, deseja-se encontra a melhor maneira de cortar um
material (placa de metal, tecido, espuma, etc.) de forma que o desperdício seja
mínimo.
• O problema do Caixeiro Viajante (PCV): a ser visto com detalhes (aplicações,
variantes, complexidade, etc) na próxima seção.
• Etc.
9
2.1.1 – O Problema do Caixeiro Viajante (PCV)
O Problema do Caixeiro Viajante (PCV) é um exemplo clássico de um POC, talvez o
mais celebrado nesta área (CAMPELLO e MACULAN, 1994). Seu enunciado diz que um
caixeiro viajante tem que visitar n cidades diferentes, iniciando e encerrando sua viagem na
primeira cidade, não importando a ordem em que as cidades são visitadas. Neste problema,
PCV, tem-se como restrição que o caixeiro não pode passar por uma cidade mais de uma vez
e que deve encerrar sua viagem na cidade de origem. Os subconjuntos (soluções viáveis) são
as possíveis rotas que o caixeiro viajante pode seguir. Os custos associados a estes
subconjuntos são as distâncias percorridas entre as cidades ou os tempos, etc.
2.1.2 – Aplicações Práticas do PCV
Um dos motivos para que o PCV seja um problema tão importante na área de
otimização combinatória é devido à sua grande aplicação prática, que surge não apenas em
problemas de roteamento, mas também em problemas práticos diversos, como:
• Programação de transporte entre células de manufatura: No arranjo físico celular,
os recursos transformados são pré-selecionados para movimentar-se para uma parte
específica da operação (ou célula), na qual todos os recursos necessários a atender suas
necessidades imediatas de processamento se encontram (SLACK, CHAMBERS &
JOHNSTON, 2002). A célula pode ser montada para funcionar como arranjo físico
por processo (por exemplo, uma célula que realiza apenas o processo de pintura de
peças) e como arranjo físico por produto (por exemplo, uma célula que realiza apenas
a confecção das bancadas de um automóvel). Portanto, para se produzir o objeto
desejável por completo, num menor tempo possível, deve-se determinar uma
seqüência ótima entre as células.
• Otimização de perfurações de furos em placas de circuitos impressos; Durante a
confecção de placas de circuito impresso, são realizadas centenas de furos para
soldagem dos componentes eletrônicos. O equipamento de perfuração realiza vários
furos de mesmo diâmetro e, como não existe uma ordem de precedência, o ideal será
encontrar uma seqüência de furos que minimize o tempo de processamento. Este
problema pode ser formulado como um PCV. Também se deve lembrar que numa
placa de circuito impresso realizam-se furos de diferentes diâmetros, ou seja, após a
máquina realizar uma série de furos, o equipamento de perfuração é mudado para
10
realizar outra série de furos, portanto a atividade é composta por uma seqüência de
PCV.
• A Inserção de Componentes Eletrônicos em Placas de Circuito Impresso: Para
inserir automaticamente os componentes eletrônicos nos furos das placas de Circuito
Impresso, é utilizada uma máquina de inserção (RABAK e SICHMAN, 2001). Cada
máquina deve efetuar n tarefas, sendo necessários ajustes entre o término de uma
operação e início de outra, os quais consomem tempo (tempo de setup). Segundo
(LAPORTE, 1992) e (LAWLER et. al., 1985), o problema de encontrar uma
seqüência apropriada de inserção dos componentes na placa, de forma a otimizar o
tempo de processamento (tempo de execução mais tempo de setup), pode ser
modelado como um PCV.
• Mapeamento Físico de DNA: O DNA é composto das bases (Adenina-A, Citosina-C,
Guanina-G e Timina-T); porém o número destas bases é extremamente grande, e as
máquinas existentes só conseguem seqüenciar até mil bases, ou seja, não conseguem
seqüenciar uma molécula inteira. Então, o DNA é quebrado em pedaços menores,
chamados clones, e estes, em pedaços de mil bases. Após conseguirem-se os
resultados dos clones, basta remontá-los em sua ordem original para que, juntos dêem
o consenso da molécula de DNA; porém esta tarefa não é tão simples, pois não se sabe
de que região da molécula original cada clone vem. O mapeamento de cada clone em
sua respectiva região de origem no DNA é conhecido como o problema do
mapeamento físico de DNA, o qual pode ser formulado como um Problema do
Caixeiro Viajante. (CERQUEIRA e STELZER, 2005).
• O Problema da Fiação do Computador: Em um computador, existem diversos
módulos, cada um com um número de pinos. Necessita-se conectar um subconjunto
destes pinos com os fios, de tal maneira que nenhum pino tenha mais de dois fios
unidos a ele, garantindo que o comprimento do fio seja minimizado.
• Análise de estruturas de cristais na cristalografia por Raios-X: Usa-se a difração
por raio-X para determinar a estrutura dos cristais ou moléculas. Nesta técnica, faz-se
incidir um feixe de Raios-X difratados numa placa fotográfica. Os padrões de difração
são constituídos por padrões de pontos na placa e podem-se extrair conclusões sobre a
estrutura do cristal, através das posições e intensidades destes pontos. Um detector
mede a intensidade dos Raios-X, refletidos do material, saindo de várias posições. Em
11
alguns experimentos, o detector deve realizar até 3000 deslocamentos para fazer as
medidas. Como o percurso realizado pelo detector na obtenção das medidas não possui
uma seqüência obrigatória, ou seja, pode-se realizar o percurso desejado, então se deve
minimizar o tempo de análise, escolhendo-se um percurso mínimo entre os pontos de
medida.
• Etc.
2.1.3 – Variantes do PCV
Considerando Cij o custo para um caixeiro viajante seguir de uma cidade i para uma
cidade j, se Cij = Cji, ∀ i, j ∈N, ou seja, se o custo de i para j for o mesmo de j para i temos
um Problema do Caixeiro Viajante Simétrico (PCVS); porém se Cij ≠Cji, ∀ i, j ∈N,
temos Problema do Caixeiro Viajante Assimétrico (PCVA) (CAMPELLO e MACULAN,
1994). Se o problema é simétrico e satisfaz a desigualdade triangular Cij + Cjk ≥ Cik, ∀ i, j, k
∈N, temos o Problema do Caixeiro Viajante Euclidiano (PCVE)
O amplo uso do PCV Simétrico ou Assimétrico na resolução de diversos problemas
reais se deparou em alguns momentos com algumas características novas, o que acabou por
inseri-las na formulação do PCV, proporcionando o surgimento de algumas variantes.
O Problema do Caixeiro Viajante Múltiplo (PCVM), também conhecido por
problema de roteamento de veículos (PRV), consiste em, dados vários caixeiros ou veículos,
estabelecer e organizar um itinerário eficiente para cada; ou seja, r itinerários para os veículos
realizarem entregas de mercadorias, todos com origem e destino no mesmo vértice. O objetivo
geral é minimizar o custo total de transporte no atendimento aos clientes (cidades); isto é,
minimizar custos fixos, custos operacionais e o número de veículos envolvidos no transporte.
Este tipo de problema vem recebendo bastante atenção de pesquisadores, como é mostrado
em (GOLDEN e ASSAD, 1988).
O Problema do Caixeiro Viajante com Janelas de Tempo (PCVJT) consiste no
problema em que os atendimentos de cada cliente devem obedecer a intervalos de tempo
(janelas), ou seja, a chegada a cada cliente deve atender às restrições de tempo pré-
estabelecidas (horário). Neste caso, o problema é também interpretado como um problema de
escalonamento (BOAVENTURA NETTO, 2006).
O Problema de Orientação (PO) é uma variante do PCV (RAMESH, YOON e
KARWAN, 1992), também conhecido pelas denominações: Problema do Caixeiro Viajante
12
Coletor de Prémios (Prize Collecting Traveling Salesman Problem - PCTSP) (BALAS 1989;
BALAS 1995; RAMESH, YOON e KARWAN, 1992; VALENTIM 1998); Problema da Rota
Orientada (Orienteering Tour Problem - OTP) (RAMESH, YOON e KARWAN, 1992) e,
Problema do Caixeiro Viajante Seletivo (Selective Traveling Salesman Problem – STSP)
(LAPORTE e MARTELO 1990, GENDREAU, LAPORTE e SEMET, 1998).
No PCTSP, o caixeiro viajante recebe um prêmio a cada cidade que ele visita e paga
uma penalidade a cada cidade que deixar de visitar. Como se deseja partir de uma cidade,
visitar as outras cidades que formam o percurso uma única vez e retornar para a cidade de
origem (BALAS 1989; BALAS 1995; VALENTIM 1998), deve-se minimizar o custo do
percurso e a soma das penalidades, de forma a garantir um ganho que justifique o esforço
empreendido. Dentre as variantes do PCTSP, algumas são o Multiobjective Vending Problem
(MVP) (KELLER, 1985) e o Travelling Salesman Subtour Problem with Specified Nodes
(SN-TSSP) (RENAUD e BOCTOR, 1998).
O Problema de Orientação – OTP originou-se de uma modalidade de esporte na
qual equipes competem entre si para encontrar uma rota com máxima premiação, onde em
cada ponto desta rota (cidades) existe uma premiação e após uma equipe atingir aquele ponto
e obter sua pontuação, as outras equipes que chegarem ao mesmo ponto terão uma pontuação
menor, ou seja, aquela equipe que realizar o trajeto em menor tempo irá somar mais pontos
que suas sucessoras e, portanto, será a vencedora. No OTP a rota é um caminho fechado, pois
o percurso termina na cidade de origem.
No STSP existe um bônus em cada cidade, porém o caixeiro não pode ultrapassar um
limite estabelecido de cidade, ou seja, deve-se visitar no máximo um numero x de cidades, de
forma a obter-se um máximo de bônus.
No Problema de Otimização do Emprego da Unidade Móvel do Pistoneio (POE-
UMP) a UMP, que é um veículo coletor de óleo (Figura 2.1), parte da Estação de Tratamento
de Óleo (ETO), segue por n poços escolhidos para pistoneio numa seqüência determinada,
realizando este processo de pistoneio5 e retorna à ETO somente ao final da jornada diária.
5 No processo de pistoneio móvel, o princípio de funcionamento é introduzir no poço de petróleo
um copo de pistoneio que submerge em torno de 30 metros no óleo e é puxado através do cabo acionado pelo
guincho para o tanque da UMP, que tem capacidade de 5m³. Esta operação é repetida até que se alcance um nível
do poço em que não haja mais óleo para ser extraído (ALOISE et al., 2001).
13
Como existe um caminhão tanque que recolhe (suga) o óleo do tanque da UMP sempre que
este tem armazenado uma boa quantidade, isto permite que o tanque da UMP nunca encha
completamente, sendo possível tratar a UMP, no problema, como um veículo com capacidade
de armazenamento de tamanho infinito (NEVES, 2000). Segundo (ALOISE, BARROS e
NEVES, 2000) este problema poderia ser chamado de problema da coleta orientada PCO, o
qual é classificado como uma variante do Problema de Orientação, pois apresenta as mesmas
características do problema do caixeiro viajante seletivo com exceção dos tempos de
montagem, operação e desmontagem da UMP em cada vértice (poço).
Figura 2. 1 – Unidade Móvel de Pistoneio
No Problema do Caixeiro Viajante Branco e Preto (PCVBP), considerando um
grafo G (orientado ou não), de maneira que o conjunto de vértices associados está dividido em
brancos e pretos, o objetivo é, além de seguir as mesmas restrições do PCV e encontrar o
menor circuito hamiltoniano, partindo arbitrariamente de um vértice branco ou preto, ainda
obedecer às restrições adicionais de cardinalidade e comprimento. Na restrição de
cardinalidade, o número de vértices brancos entre dois vértices pretos consecutivos não pode
ser superior a um número inteiro positivo Q, e na restrição de comprimento, a distância entre
dois vértices pretos consecutivos não deve exceder um número positivo L. (MACIEL,
MARTINHON e OCHI, 2005).
Estes poucos exemplos de variações do PCV, junto com as suas aplicações práticas e
os principais problemas existentes na Otimização Combinatória, servem para mostrar a
grande importância que esta área tem e o quanto ela é utilizada nos mais diversos campos da
ciência, passando pela computação (mineração de dados), aeronáutica (minimização do
consumo de combustível nas turbinas de motores em aeronaves), biologia (alinhamento de
DNA e proteínas), telecomunicações (Synchronous Optical NETwork - SONET), física
(estados de energia mínima), logística (minimização de rotas), estatística (análise de dados),
14
economia (matrizes de entrada/saída), química (empacotamento de aminoácidos),
administração (distribuição de tarefas) , etc.
2.2 – Complexidade de Problemas
A obtenção de uma solução exata para os problemas de otimização combinatória, em
geral, não é uma tarefa fácil, pois a enumeração completa de todas as soluções viáveis de um
problema poderá conduzir à solução ótima em um número finito de passos; porém de tal
ordem de grandeza, que o computador mais avançado levaria séculos no processo de cálculo
(CAMPELLO e MACULAN, 1994). Assim, métodos exatos de enumeração implícita têm
sido cada vez mais explorados no sentido de diminuir substancialmente o número dessas
soluções viáveis. Por outro lado, métodos heurístico/metaheurísticos, que fornecem soluções
próximas do ótimo, vêm sendo desenvolvidos e aplicados nessas situações. Mais
recentemente, pesquisas envolvendo uma combinação de métodos exatos e metaheurísticos
encontram-se em evidência, buscando obter melhores resultados na resolução de problemas
de grande porte para problemas de otimização combinatória NP-difíceis6.
2.2.1 – Formulação Matemática do PCVA
Na programação inteira, que segundo (CAMPELLO e MACULAN, 1994) é um dos
campos mais férteis da otimização combinatória, consegue-se modelar diversos problemas
com as variáveis de decisão assumindo apenas valores inteiros. No caso do problema do
caixeiro viajante assimétrico, a primeira formulação foi proposta por (DANTZIG,
FULKERSON e JOHNSON, 1954), que definiram ser a variável binária xij (i≠j) igual a 1 se e
somente se o arco (vi, vj) for usado na solução ótima e 0, caso contrário.
Formulação:
6 http://astarte.csr.unibo.it/matheuristics2006/
)4.3()12;(,1,
−≤≤⊆−≤∑∈
nSVSSxSvv
ij
ji
)1.3(∑≠
=ji
ijij xczMinimizar
)2.3(),...,1(1:1
nixàSujeiton
jij ==∑
=
)5.3();,...,1,(}1,0{ jinjixij ≠=∈
∑=
==n
iij njx
1
)3.3(),...,1(1
15
As restrições (3.2) e (3.3) garantem que, para cada vértice, há somente uma aresta de
entrada e uma de saída. A restrição (3.4) garante a eliminação de sub-rotas. Outras
formulações surgiram como, por exemplo, a de (GAVISH e GRAVES, 1978), que
propuseram as seguintes restrições para eliminação de sub-rotas:
Nesta, as restrições correspondem a um problema de fluxo em redes e as variáveis yij ,
que representam a ordem em que as arestas são visitadas assumem valores inteiros na solução
ótima. Com esta nova formulação, conseguiu-se reduzir as (2n -2) restrições de (3.4) para
(n²+3.n) restrições. Entretanto, o número de passos necessários para a obtenção da solução
ótima do PCV ainda cresce exponencialmente com o número de variáveis, o que torna o
problema intratável computacionalmente e pertencente à classe de problemas NP-difíceis.
Para resolução dos problemas NP-difíceis de dimensões significativas, que é o caso da
maioria dos problemas práticos, utilizam-se Heurísticas e Metaheurísticas, algoritmos que
conseguem achar uma solução próxima à exata em um tempo computacional viável.
As seções a seguir apresentam algumas dessas Heurísticas e Metaheurísticas com
vistas à sua aplicação ao Problema do Caixeiro Viajante Assimétrico.
2.3 – Heurísticas
Segundo (BARR et al., 2001), Métodos Heurísticos, também chamados algoritmos
aproximativos, procedimentos inexatos, algoritmos incorretos, ou simplesmente heurísticos
são usados para identificar boas soluções aproximadas para cada problema em menos tempo
que os algoritmos exatos (quando este existir).
2.3.1 – Heurísticas Construtivas
As Heurísticas de métodos construtivos iniciam, sem nenhum resultado, a solução de
um problema e constroem passo a passo uma solução viável. Apresentam algoritmos gulosos,
os quais, devido a enxergarem apenas o que está mais próximo do objetivo desejado, são
∑ ∑≠=
≠=
==−n
ijj
n
ijj
jiij niyy1 2
,...,2,1
njenixny ijij ,...,3,2,...,2,1,)1( ==−≤
jienjiyij ≠=≥ ,...,2,1,,0
16
também chamados de algoritmos míopes. Quando se trata de solucionar o PCV, as variações
desta classe de algoritmo, que se apresentam com maior destaque, são: o vizinho mais
próximo, a inserção mais próxima, a inserção mais distante, a inserção mais barata, a inserção
pelo maior ângulo e o método das economias. Outros algoritmos, também de grande
importância, são: o algoritmo de Christofides, que segue os conceitos dos métodos baseados
na árvore geradora de peso mínimo e o GKS que, segundo (GLOVER et al, 1999), é uma
heurística que oferece melhores resultados na resolução de problemas assimétricos do caixeiro
viajante, se comparado com os ditos gulosos.
2.3.1.1 – Vizinho Mais Próximo
Desenvolvida por (BELMORE e NEMHAUSER, 1988), consiste em, dado um grafo
G = (V,A), partir de um vértice inicial e construir uma solução escolhendo, a cada iteração, o
vértice mais próximo do último vértice escolhido para compor a solução. Este processo é
realizado até que se tenha visitado todos os vértices (Algoritmo 2.1).
Este algoritmo é de ordem O(n²) e o ciclo Hamiltoniano obtido sofre forte influência
da escolha do vértice inicial. Esta influência é eliminada repetindo o procedimento n vezes,
tomando a cada vez um vértice diferente, onde o algoritmo resultante será de ordem O(n³)
(CAMPELLO e MACULAN, 1994).
Algoritmo 2. 1 Algoritmo Vizinho Mais Próximo
Fonte: (CAMPELLO E MACULAN, 1994).
Quanto às heurísticas de inserção, que originalmente foram desenvolvidas por
(ROSENKRANTZ, STEARNS e LEWIS, 1977), no contexto do (PCVS), o processo será
1 Algoritmo VP (G = (N, M)) [Tour em G] 2 Início
3 Ler {G = (N, M) com N = {1, 2,.... n} e ci j ,∀ i, j ∈ N}; 4 H:={1};
5 x0 := 0; 6 N:=N \ {1 }; 7 i := 1 ;
8 Enquanto N ≠ ∅ fazer
9 Início
10 Escolher j∈ N tal que ci j = mínimo {c i k} ;
11 H := H ∪ { j }; 12 x0 : = x0 + ci j ; 13 N := N \ {j}; 14 i := j ; 15 Fim;
16 Escrever (H:= H∪ {1}, x0 := x0 + cj 1 }; 17 Fim.
17
manter em um grafo um ciclo em cada iteração e inserir a próxima cidade no ciclo, de forma
ótima.
2.3.1.2 – Inserção Mais Próxima
Nesta heurística, o ciclo é iniciado com apenas um vértice e a cada iteração este ciclo
vai aumentando, parando no momento em que é formado um ciclo Hamiltoniano (Algoritmo
2.2). Esta Heurística é de Ordem O(n³).
Algoritmo 2. 2
Algoritmo Inserção Mais Próxima
Fonte: (RIBEIRO, C. C., 2002).
2.3.1.3 – Inserção Mais Distante
Esta Heurística, também de Ordem O(n³), difere da anterior no passo 1 do algoritmo,
onde nesta deve-se encontrar o vértice k fora do ciclo corrente, cuja aresta de menor
comprimento que o liga a este ciclo é máxima.
Este procedimento acaba por se tornar mais eficiente que a Heurística de inserção mais
próxima, porque os primeiros poucos pontos mais distantes esboçam um perfil geral do ciclo,
que será refinado posteriormente (BENTLEY, 1992).
2.3.1.4 – Inserção Mais Barata
Este procedimento é uma simples melhoria das Heurísticas anteriores, pois, ao invés
de separar os passos 1, onde se seleciona o novo nó que irá incorporar ao circuito a cada
iteração, e 2, no qual se seleciona a posição onde este nó entrará no circuito, acabou-se por
fazer a escolha da melhor combinação destes passos em conjunto (Algoritmo 2.3). Isso
forneceu uma Heurística que apresenta melhores soluções; porém o tempo de processamento
é cerca de n vezes maior ( RIBEIRO, C. C., 2004).
Passo 0: Inicializar o ciclo com apenas um vértice. Passo 1: Encontrar o vértice k fora do ciclo corrente cuja aresta de menor comprimento que o liga a este ciclo é mínima. Passo 2: Encontrar o par de arestas (i,k) e (k,j) que ligam o vértice k ao ciclo, minimizando cik + ckj - cij Inserir as arestas (i,k) e (k,j) e retirar a aresta (i,j). Passo 3: Retornar ao passo 1.
18
Algoritmo 2. 3
Algoritmo Inserção Mais Barata
Fonte: (RIBEIRO, C. C., 2002).
2.3.1.5 – Inserção Pelo Maior Ângulo
Desenvolvida por (NORBACK e LOVE, 1979), esta Heurística se inicia com um ciclo
composto por todos os nós que formam a envoltória convexa do grafo, e vão-se inserindo
neste ciclo os nós internos a esta envoltória, cujo ângulo entre as arestas seja máximo,
parando no momento em que se obtém um ciclo hamiltoniano (Algoritmo 2.4).
Algoritmo 2. 4
Algoritmo Inserção Pelo Maior Ângulo
Fonte: (RIBEIRO, C. C., 2002).
2.3.1.6 – Método das Economias
Esta Heurística foi inicialmente proposta por (CLARKE e WRIGHT, 1963) para o
Problema de Roteamento de Veículos. Sua idéia básica é partir da pior situação possível, a
qual seria a escolha arbitrária de um vértice-base do grafo completo e construir ciclos de
tamanho 2 deste vértice para cada um dos (n – 1) restantes. A fusão de dois ciclos é realizada
Passo 0:
Inicializar o ciclo com apenas um vértice.
Passo 1:
Encontrar o vértice k fora do ciclo corrente e o par de arestas (i,k) e (k,j) que ligam o vértice k ao ciclo, minimizando
cik + ckj - cij
Passo 2:
Inserir as arestas (i,k) e (k,j) e retirar a aresta (i,j).
Passo 3:
Retornar ao passo 1.
Passo 0:
Inicializar o ciclo com a envoltória convexa dos nós do grafo.
Passo 1:
Inserir cada um dos nós não pertencentes à envoltória convexa aplicando uma heurística de inserção: encontrar o vértice k fora do ciclo corrente e o par de arestas (i,k) e (k,j) que ligam o vértice k ao ciclo, tal que, o ângulo formado pelas arestas (i,k) e (k,j) seja máximo.
Passo 2:
Retornar ao passo 1.
19
a cada iteração, com base no conceito de economia, que seria a conexão direta deles através
da aresta (i, j) e remoção das arestas (1, i) e (j, 1), obtendo com isto uma economia de sij = c1i
+ cj1- cij (Algoritmo 2.5). Este procedimento se repete até obter um ciclo hamiltoniano.
Segundo (CAMPELLO e MACULAN, 1994), esta Heurística é de ordem O(n². log2
n); porém, se com o intuito de eliminar a influência do vértice-base, realizar o procedimento
considerando os (n – 1) vértices restantes como vértice inicial, esta heurística será de ordem
O(n³. log2 n).
Algoritmo 2. 5
Algoritmo Método das Economias
Fonte: (RIBEIRO, C. C., 2002).
2.3.1.7 – Heurística de Christofides
Esta Heurística segundo (CAMPELLO e MACULAN, 1994) é de ordem O(n³) e é um
método baseado na árvore geradora de peso mínimo, o qual segue o raciocínio de que,
eliminando-se qualquer aresta de uma rota, obtém-se uma árvore geradora (Algoritmo 2.6).
Portanto a árvore geradora mínima de um grafo constitui um limite inferior para o Ciclo
Hamiltoniano ótimo. A Heurística de Christofides, além do conceito de Matching Perfeito
Mínimo, ainda utiliza alguns ajustes em uma operação chamada atalho, para transformação da
árvore geradora mínima em uma rota.
Algoritmo 2. 6
Algoritmo de Christofides
Passo 0: Escolher um vértice base inicial Passo 1: Construir subciclos de comprimento 2 pelo vértice base e por cada um dos n-1 nós restantes. Passo 2: Calcular as economias sij = c1i + cj1 - cij e ordená-las em ordem decrescente. Passo 3: A cada iteração, maximizar a distância economizada sobre a solução anterior, combinando-se dois subciclos (um chegando e outro saindo do nó 1) e substituindo-os por uma nova aresta: percorrer a lista de economias e realizar as trocas que mantêm uma rota iniciando no vértice 1 e passando pelos demais nós, até obter um ciclo hamiltoniano.
Passo 0:
Encontre a árvore geradora mínima T
Passo 1:
Encontre o Matching perfeito mínimo M no grafo completo
Passo 2:
Encontre um caminho Euleriano
Passo 3:
aplique a operação de atalho até obter o ciclo Hamiltoniano.
20
2.3.1.8 – Heurística GKS
Esta Heurística foi desenvolvida por (GLOVER et al, 1999), baseando-se na
Heurística Karp-Steele patching para resolução de problemas do caixeiro viajante
assimétricos, sendo também responsável por produzir ciclos de boa qualidade para algumas
instâncias do PCV.
Através da resolução do Problema da Alocação Linear sobre a matriz de distâncias da
instância a ser resolvida, gera-se um conjunto (ciclo-fator) de sub-ciclos em que, ao longo das
iterações da GKS, estes sub-ciclos se unem, até formarem um ciclo único de peso mínimo
(Algoritmo 2.7).
Algoritmo 2. 7
Algoritmo GKS
Fonte: (GLOVER et al, 1999).
2.3.2 – Heurísticas de Busca Local
Quanto às Heurísticas de refinamento, a solução inicial é obtida, tanto aleatoriamente,
como através de um método construtivo e, utilizando-se modificações nos elementos da
solução corrente, consegue-se melhorá-la. O processo ocorre através de uma busca local
realizada na vizinhança da solução onde, encontrando-se um ponto como melhor solução, este
passará a ser a nova solução.
A busca local não está livre de terminar no primeiro ótimo local encontrado; porém ela
pode fornecer uma solução de qualidade. Dentre os fatores que vão favorecer uma melhor
solução estão: a solução inicial utilizada, a vizinhança escolhida e a estratégia de busca
empregada (algoritmo busca local com melhoria iterativa, com descida mais rápida, método
das k-substituições ou k-opt e etc).
Passo 0:
Construa um ciclo-fator F de peso Mínimo
Passo 1:
Feito o exame dos diferentes ciclos em F, escolha um par de arcos tal que, remendando (isto é, removendo os arcos escolhidos e adicionando outros dois arcos que unam ambos os ciclos) obtenhamos um ciclo fator (com um ciclo a menos) de peso mínimo (dentro da estrutura de remendar)
Passo 2:
Repita o passo 1 até que o ciclo fator atual esteja reduzido a um único ciclo. Use este ciclo como uma solução aproximada para o PCV.
21
2.3.2.1 – Melhoria Iterativa
Neste procedimento de busca, a cada iteração seleciona-se a primeira solução
encontrada na vizinhança, mais refinada que a solução corrente.
2.3.2.2 – Descida Mais Rápida
Para este procedimento, realiza-se, para solução corrente, uma busca em toda a sua
vizinhança e escolhe-se a melhor solução aprimorante da região pesquisada.
Em (RIBEIRO, C. C., 2004), existem alguns exemplos de vizinhança para o problema
do caixeiro viajante, que podem ser utilizados nos dois procedimentos acima.
Um primeiro exemplo mostrado seria: dada uma solução
),...,,...,,,,...,( 111 njiii πππππππ +−= , a vizinhança é obtida através da troca da posição
(permutação) de duas cidades consecutivas. Então, a vizinhança ficaria:
}{ 1,...,1),...,,,,...,()( 1111 −=∴= +− niN niii ππππππ .
Outra vizinhança seria conseguida através da troca da posição de duas cidades
quaisquer onde, para a mesma solução ),...,,...,,,,...,( 111 njiii πππππππ +−= , teríamos:
}{ nijniN niiji ,...,1;1,...,1),...,,...,,,,...,()( 1112 +=−=∴= +− πππππππ
Uma terceira vizinhança para a solução ),...,,,...,,,,...,( 1111 njjiii ππππππππ ++−= ,
seria obtida através da inserção de uma cidade em uma posição qualquer, ficando:
}{ nijniN njijii ,...,1;1,...,1),...,,,,...,,,...,()( 11113 +=−=∴= ++− ππππππππ .
2.3.2.3 – Método das k-substituições ou k-opt
Segundo (CAMPELLO e MACULAN, 1994), este algoritmo tenta todas as
substituições de k arestas, sendo o melhor Ciclo Hamiltoniano obtido ao final do processo
denominado k-ótimo. Uma Heurística que se baseia na aplicação desta técnica é a de (LIN e
KERNIGHAN, 1973).
Pensando-se em um circuito hamiltoniano, o qual é uma solução para o PCV, a
vizinhança com este método é obtida quando escolhendo-se k arestas quaisquer, elimina-as e
substitui-as por outras k arestas, de modo a formar um novo circuito hamiltoniano de menor
custo.
22
Um esquema de funcionamento deste procedimento está detalhado na Figura 2.2,
representando uma substituição do tipo 3-opt.
Dada uma solução inicial H
Remover k elementos da solução H, obtendo uma solução não viável H’
Construir todas as soluções viáveis contendo H’
Escolher a melhor dentre as soluções encontradas
Esta solução passará a ser a nova solução H na iteração seguinte
Figura 2. 2 - Esquema de funcionamento do método k-opt
A busca local também pode ser utilizada como uma heurística subordinada, pois serve
às Metaheurísticas, aprimorando na vizinhança a solução que estas obtêm.
2.4 – Metaheurísticas
É um processo iterativo ou de refinamento de solução de problemas, que organiza e
direciona heurísticas subordinadas, pela combinação de diferentes conceitos, podendo
manipular uma solução completa, incompleta ou um conjunto de soluções, tentando evitar
parada prematura em ótimo local. O processo de achar uma boa solução consiste em aplicar a
cada passo uma heurística subordinada que tenha sido projetada para cada problema particular
e, como uma tentativa para escapar de ótimos locais, algumas delas permitem controlar a
deterioração das soluções para diversificar a busca (NORONHA, ALOISE e SILVA, 2001).
2.4.1- Analogia com Métodos Físicos
Simulated Annealing é uma variante da técnica de busca local, que se baseia nos
resultados da termodinâmica, onde as soluções viáveis dos problemas de Otimização
23
Combinatória são tratados como estados de sistemas físicos e seus custos à energia desses
estados.
Annealing - corresponde a um processo térmico em que um cristal liquefeito, sob altas
temperaturas, atinge o ponto de solidificação através de uma lenta e gradativa diminuição de
sua temperatura, e o sistema, conseqüentemente atinge um estado de energia mínima.
No Simulated Annealing, as altas temperaturas possibilitam a escolha de soluções
ruins, evitando com isto a parada em ótimos locais e, ao longo das iterações, sob o controle de
determinados parâmetros, a temperatura vai diminuindo e, com ela, a possibilidade de
aceitação de soluções ruins, o que favorece as chances de encontrar um ótimo global.
2.4.2 - Estratégias de Cálculos com Intensificação da Busca Local
Busca tabu
O método Busca Tabu foi proposto por (GLOVER, 1986), sendo uma Metaheurística
de melhoramento local que faz uso de memórias para proibir ou selecionar determinados tipos
de movimentos.
Após escolhido um movimento dentro de uma vizinhança, o mesmo passa a pertencer
a uma lista tabu (lista proibida), permanecendo nesta lista até que os parâmetros pré-definidos
sejam cumpridos. Lembrando que retirar um movimento de uma lista tabu para reutilizá-lo
como solução não significa que estará formando ciclos, pois a lista tabu será diferente a cada
iteração do algoritmo.
Este algoritmo também faz uso de uma memória de longo prazo, onde são
armazenadas as soluções elites (soluções mais utilizadas), servindo para um processo de
intensificação, pois se pode usar um movimento que tenha fornecido boas respostas, ou um
processo de diversificação, para fazer uso de movimentos pouco utilizados, os quais
favoreçam a fuga de ótimos locais.
Multi-Start
No procedimento Multi-Start são geradas várias soluções iniciais aleatoriamente, e
através do procedimento de busca local são encontrados mínimos locais para cada solução
inicial, utilizando-se como resposta o melhor mínimo local.
24
Como as soluções iniciais são geradas aleatoriamente, o algoritmo está sujeito a fazer
uso de soluções boas ou ruins.
GRASP
A Metaheurística GRASP (Greedy Randomized Adaptive Search Procedures) foi
proposta por (FEO e RESENDE, 1989). Na sua forma padrão, é implementada como um
algoritmo Multi-Start onde, em cada iteração, é gerado, a partir de Heurísticas Construtivas,
um ponto inicial; numa segunda fase (Busca Local), determina-se um ótimo local. Após cada
iteração, é guardado o melhor ótimo local encontrado dentre todas as iterações, sendo
considerado o ótimo global, o melhor ótimo local.
Por ser um algoritmo que se utiliza de pontos iniciais gerados a partir de heurísticas
construtivas e, conseqüentemente, de uma probabilidade de serem, em sua maioria, boas
soluções, esta Metaheurística apresenta bons resultados na busca da solução ótima.
VND e VNS
A Metaheurística VNS (Variable Neighborhood Search) - Pesquisa em Vizinhança
Variável foi proposta por (MLADENOVIC e HANSEN, 1997).
Nesta Metaheurística, utiliza-se um conjunto finito de vizinhanças pré-definidas, onde
se realiza uma busca local em uma primeira vizinhança e, quando não ocorrer mais melhoria
da solução, parte-se para uma outra vizinhança. Na vizinhança seguinte, não se encontrando
melhoria, segue-se pelas outras vizinhanças; e, naquela em que se encontrar uma melhor
solução, retorna-se à primeira vizinhança e inicia-se todo o processo. O algoritmo encerra-se
quando se utilizam todas as vizinhanças e não se encontra uma melhor do que a incumbente.
O uso de várias vizinhanças contribui para encontrar a solução ótima, pois no uso de
apenas uma vizinhança o resultado pode ser comprometido caso a mesma seja inadequada.
Quanto à Metaheurística VND (Variable Neighborhood Descent) – Descida em
Vizinhança Variável, a mudança de vizinhança é realizada durante a busca local, ou seja,
depois de encontrado um ótimo local na primeira vizinhança, testa-se este ótimo nas outras
vizinhanças; caso se encontre uma melhor solução, retorna-se para a vizinhança inicial e
novamente se começa o processo com este novo valor inicial.
25
Procedimento:
1. Enquanto melhorar a solução usar a vizinhança 1, senão passar para as vizinhanças 2,...,n;
2. Quando em alguma vizinhança intermediária encontra-se uma melhor solução, volta-se para a vizinhança 1 e recomeça-se o processo.
InInííciocioN1
N2
N3
Figura 2. 3 - Esquema de funcionamento da Metaheurística VNS
2.4.3 - Analogia com Processos Naturais
Colônia de Formigas (Ant Colonies)
A Metaheurística colônia de formigas é baseada em uma população de agentes que
simulam o comportamento das formigas para resolver um problema de otimização.
As formigas, durante seu deslocamento, deixam um rastro de uma substância chamada
feromônio, que as auxilia a seguirem o melhor trajeto entre o formigueiro, uma fonte de
alimento e o retorno ao formigueiro, ou para contornar obstáculos. Isto é, através de uma
comunicação química, as formigas, gradativamente, seguem o percurso mais utilizado, e
conseqüentemente com maior concentração de feromônio.
No algoritmo, é escolhida para cada formiga uma cidade inicial; e, a cada passo, as
formigas escolhem probabilísticamente a próxima cidade a visitar. A probabilidade de escolha
da cidade a ser visitada está diretamente ligada à quantidade de feromônio existente na cidade.
Portanto, nas primeiras iterações, como nenhuma cidade ainda foi visitada, diferentes
percursos serão feitos pelas várias formigas; mas, com o aumento das iterações, as cidades
mais visitadas, ou seja, com melhores soluções, terão uma maior migração das formigas,
concluindo-se o algoritmo com aquela cidade com maior índice de feromônio, sendo um
ótimo global.
26
Importante destacar que, neste algoritmo, não é realizado um movimento de uma
formiga por cada iteração (um único agente), mas é realizado por todas as formigas, em cada
iteração, um movimento diferente. Portanto, em uma iteração, todas as formigas se deslocam
(população de agentes), podendo, para algumas delas, o destino ser semelhante ou não.
Otimização por Nuvem de Partículas
A Otimização por nuvem de partículas (Particle Swarm Optimization - PSO) foi
inicialmente desenvolvida por (KENNEDY e EBERHART, 1995), como um algoritmo que
simula o comportamento de um bando de pássaros em revoada.
O algoritmo possui uma população de partículas, com posições e velocidades em um
espaço de problema n dimensional, de forma aleatória, com distribuição uniforme. Durante
cada iteração, as partículas percorrem o espaço de busca do problema. Em cada iteração, o
algoritmo guarda a melhor solução encontrada por cada partícula (pbest) e a melhor solução
encontrada entre todas as partículas (gbest). Assim como os pássaros, que se comunicam e
acabam seguindo em uma mesma direção, a nuvem de partículas no algoritmo tende a seguir
na direção da melhor solução do problema.
Algoritmo Genético
É um modelo computacional que adaptou a teoria da evolução natural das espécies
para resolução, predominantemente, de problemas que são modelados como problemas de
otimização. A população de indivíduos é representada por um conjunto de possíveis soluções
para determinado problema. Através de operadores de seleção, cruzamento e mutação, geram-
se novas descendências de populações, e somente os indivíduos mais aptos (melhores
soluções) sobrevivem.
Maiores detalhes sobre o algoritmo genético e os operadores genéticos serão
explanados no capítulo 3.
27
2.4.4 – Métodos Híbridos (Algoritmo Memético)
Nos métodos híbridos, os algoritmos são compostos de uma fase de busca global, onde
se faz uso de uma Metaheurística baseada em processos naturais, e de uma fase de busca local
(aprendizado cultural individual – evolução memética).
Em (GLOVER e LAGUNA, 1997), relata-se que o relacionamento do Algoritmo
Genético com a Busca Tabu cria combinações híbridas potencialmente úteis, e em (COELHO
e MARIANI, 2005), apresenta-se um algoritmo memético que utiliza em sua busca global
uma técnica de otimização por nuvem de partículas e na busca local, um método conhecido
por Hooke-Jeeves.
Em (COELHO, 2003), a metodologia híbrida, que apesar de controvérsias também é
conhecida por algoritmos meméticos, apresenta a maior dificuldade quanto à escolha do
momento de parar o procedimento de busca estocástica para iniciar o procedimento de busca
determinística.
Nos próximos capítulos, serão mais detalhadas as características de um clássico
algoritmo memético, também conhecido como Algoritmo Genético Híbrido (MOSCATO,
1989, 1999), o qual utiliza na sua busca global a Metaheuristica Algoritmo Genético acrescida
de uma busca local após cada geração de indivíduos.
28
Capítulo 3
Algoritmos Evolutivos e Infecção Viral
Este capítulo começa por descrever os Algoritmos Evolutivos conhecidos por
Algoritmo Genético e Algoritmo Memético, procurando fazer, para ambos, uma relação com
os processos de evolução natural; também cita as principais características e tipos de
operadores de seleção, cruzamento e mutação, adequados para quando se pretende solucionar
o Problema do Caixeiro Viajante Assimétrico. Relata também o processo de Infecção Viral,
justificando o uso do vírus na evolução do Algoritmo Genético e Memético, através da
atuação do vírus genético e memético na população de seres humanos, culminando, portanto,
numa estrutura adequada de um Algoritmo Memético com Infecção Viral.
Visando relatar os dados numa seqüência lógica, o capítulo está distribuído nos
seguintes tópicos: Algoritmos Evolutivos, Infecção Viral e o Algoritmo Memético com
Infecção Viral.
3.1 - Algoritmos Evolutivos
Segundo (RIBEIRO FILHO, G, 2001), o termo “Algoritmos Evolutivos” vem sendo
usado para descrever quaisquer procedimentos iterativos baseados em seleção e variação de
populações.
Estes algoritmos trabalham com um conjunto de estruturas que representam soluções
cuja finalidade é a sobrevivência do mais apto. Somente aquelas estruturas mais adaptadas
dentro do conjunto conseguem evoluir, através de operadores genéticos, para novas gerações
de populações, as quais fornecem melhores soluções.
29
Hoje, os Algoritmos Evolutivos formam uma classe de algoritmos muito estudada,
com muitas variações e aplicações bem sucedidas na resolução de problemas em várias áreas
da ciência (MICHALEWICZ, 1996; MICHALEWICZ e FOGEL, 2000, apud RIBEIRO
FILHO, G, 2001). Dentre suas variações, existe o Algoritmo Genético, que se utiliza de
transições probabilísticas para a evolução da população de soluções.
3.1.1 - Algoritmo Genético
O algoritmo genético, inspirado na teoria da evolução das espécies de Charles Darwin
(DARWIN, 1859), foi proposto por John Holland (HOLLAND, 1975), com o objetivo inicial
de simular matematicamente os fenômenos de adaptação, naturais ou artificiais, visando
importar estes mecanismos, com todas as características e vantagens do processo, para
ambientes computacionais. O algoritmo, o qual utiliza os conceitos de genes, cromossomos,
cruzamento, mutação e seleção (Algoritmo 3.1), recebeu um grande impulso, quanto à sua
aplicação, a partir de 1980, sendo utilizado em diversas áreas de aplicação científica.
Os grandes responsáveis pela forte utilização do Algoritmo Genético foram: a
popularização dos computadores, o aparecimento de sistemas cada vez mais rápidos e
potentes e a grande versatilidade e excelência de resultados apresentados pelo algoritmo
diante deste cenário.
Algoritmo 3. 1
Algoritmo Genético Clássico
Na primeira linha do algoritmo 3.1, está representada a população inicial do algoritmo.
Esta população é composta de soluções que podem ser geradas aleatoriamente, ou através de
uma Heurística construtiva.
1: P � População Inicial; 2: avaliar P; 3: enquanto condição não satisfeita faça 4: P’ � Seleção( P ); 5: P � Cruzamentos( P’ ); 6: P � Mutações ( P ); 7: avaliar P; 8: fim enquanto 9: Solução � Melhor indivíduo( P );
30
3.1.1.1 - O Cromossomo
Cada indivíduo da população inicial é representado por um cromossomo (Figura 3.1),
os quais podem ter uma representação binária, inteira (símbolos) ou real, dependendo da
classe de problema que se deseja resolver. Cada cromossomo é constituído de vários genes.
Figura 3. 1 - Representações do Cromossomo
Pensando-se no problema do caixeiro viajante, três codificações constantemente
usadas para representar um cromossomo seriam: a ordinal, a de adjacência (adjacency) e a de
caminho (path).
Na codificação ordinal, desenvolvida por (GREFENSTETTE et al., 1985), usa-se
uma lista de referência (caminho canônico) para construir um cromossomo que representa
uma rota desejada. Para representar, por exemplo, o caminho corrente (1 5 2 6 4 3 8 7) nesta
codificação, utilizando-se como caminho canônico (1 2 3 4 5 6 7 8) obter-se-á o cromossomo
(1 4 1 3 2 1 2 1), pois:
Se pega a primeira cidade do caminho corrente ( 1 ), verifica-se sua posição no caminho
canônico ( 1ª ); retira-se a cidade do caminho canônico e coloca-se sua posição no
cromossomo de representação ordinal;
Em seguida pega-se a segunda cidade do caminho corrente ( 5 ); verifica-se sua posição no
caminho canônico ( 4ª ); retira-se a cidade do caminho canônico e coloca-se sua posição no
cromossomo de representação ordinal;
Realiza-se este processo, até obter-se o cromossomo por completo (Figura 3.2).
Gene
5 2 3 6 1 7 4
1 0 0 1 1 1 0
B A C E F D G
Representação binária:
Representação simbólica:
Representação real:
31
Figura 3. 2 - Representação Ordinal
Na Codificação de Adjacência, o caminho é representado por uma lista de n cidades,
onde a cidade j ocupa a posição i no cromossomo se existe uma vizinhança da cidade i para j
no caminho (POTVIN, 1996). Por exemplo, o cromossomo (2 4 8 3 9 7 1 5 6) codifica o
caminho (1 2 4 3 8 5 9 6 7), onde a cidade 2 ocupa a posição 1 no cromossomo devido à
vizinhança (1,2) estar no caminho, bem como a cidade 4 ocupa a posição 2 devido à
vizinhança (2,4) estar no caminho, e assim sucessivamente.
Na codificação de caminho, a forma mais utilizada de representação do cromossomo
para o PCV, o número da cidade é associado a cada gene do cromossomo, sendo a solução
dada pela seqüência em que tais genes aparecem no cromossomo. Como exemplo, considere o
cromossomo (2 5 3 7 1 8 4 6), que representa a rota (2 5 3 7 1 8 4 6), ou seja, o cromossomo
representa a ordem na qual as cidades são visitadas.
Na segunda linha do algoritmo 3.1, consta avaliar a população; isto significa que cada
cromossomo gerado traz no código genético o seu nível de aptidão (fitness), e a avaliação
mostrará o quanto cada indivíduo será apto para reproduzir-se e gerar bons descendentes para
gerações futuras. Num cromossomo que representa uma rota do caixeiro viajante, o fitness
poderia ser a distância percorrida, o tempo gasto no percurso, etc.
Cada iteração significa a geração de uma nova população, a qual é formada pelos
descendentes da população que acabou de extinguir-se (população da iteração anterior).
3.1.1.2 – A Seleção
A Seleção é baseada na aptidão dos indivíduos, pois quanto melhor um indivíduo se
adaptar ao seu meio ambiente, maior será sua chance de sobreviver e gerar descendentes
Caminho Corrente Caminho Canônico Cromossomo de Re-
presentação Ordinal
1 5 2 6 4 3 8 7 1 2 3 4 5 6 7 8 1
1 5 2 6 4 3 8 7 2 3 4 5 6 7 8 1 4
1 5 2 6 4 3 8 7 2 3 4 6 7 8 1 4 1
1 5 2 6 4 3 8 7 3 4 6 7 8 1 4 1 3
1 5 2 6 4 3 8 7 3 4 7 8 1 4 1 3 2
1 5 2 6 4 3 8 7 3 7 8 1 4 1 3 2 1
1 5 2 6 4 3 8 7 7 8 1 4 1 3 2 1 2
1 5 2 6 4 3 8 7 7 1 4 1 3 2 1 2 1
32
(DARWIN, 1859). Portanto, na operação de seleção, são escolhidos os indivíduos para se
reproduzirem.
No Algoritmo Genético tradicional desenvolvido por (HOLLAND, 1975), era
utilizada a seleção pelo método da roleta, onde os indivíduos mais aptos possuem uma maior
probabilidade de serem selecionados. Com a evolução do algoritmo, foram desenvolvidos
novos métodos de seleção, os quais favoreceram o desempenho do mesmo. Alguns dos
métodos de seleção são:
i) Seleção Proporcional a Adaptação (roleta)
Como dito anteriormente, a probabilidade de um indivíduo ser selecionado é proporcional ao
seu valor de aptidão diante de toda a população pois, neste método, segundo (GOLDBERG,
1989), cada indivíduo é representado como uma fatia em uma roleta (Figura 3.3),
proporcional à sua adaptação. A cada giro da roleta, um indivíduo é selecionado, tendo maior
chance aqueles que possuem as maiores fatias (maior percentagem).
8%
20%
42%
30%
cromossomo1
cromossomo2
cromossomo3
cromossomo4
Figura 3. 3 – Roleta de cromossomos representados pela porcentagem de fitness
ii) Seleção por Nivelamento Linear (linear ranking selection):
Neste método, desenvolvido por (BAKER, 1989), os indivíduos são inicialmente ordenados
de acordo com o valor de fitness. A seguir, estes valores de fitness são alterados de acordo
com a posição relativa de cada indivíduo. Ao melhor indivíduo é dado um valor de fitness s
entre 1 e 2; e para o pior indivíduo, um valor 2 – s. Os demais cromossomos têm o valor de
fitness linearmente distribuído entre o melhor e o pior, baseado em suas posições relativas, e
pela interpolação:
)1(
))1(2()(
−
−−=
N
sisif
33
Onde i = 1 corresponde ao pior elemento. Se s for 2, o pior cromossomo não tem chance de se
reproduzir.
iii) Seleção por Nivelamento Exponencial (exponential ranking selection):
Este método de seleção difere do anterior pelo fato de as probabilidades de seleção de cada
indivíduo seguirem uma função exponencial. Nele, o melhor cromossomo recebe um valor de
fitness 1, enquanto que o segundo recebe um valor s de 0,99, o terceiro recebe s2 e o restante,
s(n-1). Os valores de fitness relacionados precisam ser divididos por sua média para dar o
número esperado de filhos.
iv) Seleção por Torneio (tournament selection):
Apresentado por David Goldberg (GOLDBERG e DEB, 1991) para Algoritmos Genéticos,
onde um grupo de n indivíduos (tipicamente dois) são aleatoriamente escolhidos para
competir em um torneio; o que possuir melhor medida de fitness é selecionado para
reproduzir-se (Figura 3.4).
Fonte: (NEVES, 2000) Figura 3. 4 - Fluxograma do método de seleção por torneio com tamanho igual a 2 para um problema de minimização
Sim Sim
Não Não
Colocar todos os membros da população em uma fila
Escolher X1 e X2 ao acaso
Escolher X3 e X4 ao acaso Se Vazio ?
F(X1) < F(X2)
Selecione X1
Selecione X2
F(X3) < F(X4)
Selecione X3
Selecione X4
Emparceiramento
Nova População
34
v) Seleção Boltzmann (Boltzmann Selection)
O método de seleção conhecido por Boltzmann (GOLDBERG, 1990; PRÜGEL-BENNETT e
SHAPIRO, 1994), utiliza a idéia do Simulated Annealing; em um momento inicial, a alta
temperatura gera uma pressão de seleção na qual os indivíduos com baixo valor de fitness
conseguem ser selecionados; com o passar do tempo, esta temperatura baixa, gerando uma
pressão de seleção na qual somente os indivíduos com auto valor de fitness são selecionados.
vi) Seleção por Truncamento (truncation selection):
Neste método, dado um valor de limiar T, a seleção é feita apenas entre os T melhores
indivíduos. A probabilidade de seleção destes indivíduos é a mesma para todos.
3.1.1.3 – O Cruzamento
No operador genético conhecido por Cruzamento (Crossover), os indivíduos
selecionados (pais) gerarão, através de um processo de combinação, descendentes (filhos) os
quais terão boas chances de possuir melhores fitness que seus antecedentes.
Existem diversos processos de crossover, mas os principais são:
• Crossover de 1 ponto: utilizado pelo Algoritmo Genético Tradicional é o mais
simples; combina as características de dois cromossomos pais, pré-selecionados para
formar dois filhos. Escolhe-se aleatoriamente uma posição de corte para cada
cromossomo pai e recombina-se a parte esquerda de um cromossomo com a direita do
outro. Fazendo-se isto para os dois cromossomos, ter-se-á como conseqüência dois
novos cromossomos (Figura 3.5).
Figura 3. 5 – Crossover de 1 ponto
• Crossover de 2 pontos: Este tipo de crossover geralmente oferece melhores
resultados que o crossover de 1 ponto (BEASLEY, BULL e MARTIN, 1993). Porém
deve-se estar atento para que a adição deste segundo ponto não reduza a performance
35
do algoritmo. Neste processo, são escolhidos aleatoriamente dois pontos de corte para
os cromossomos pais e permutam-se as informações contidas entre eles, gerando dois
novos cromossomos (Figura 3.6).
Figura 3. 6 – Crossover de 2 pontos
Quando se trata do PCVA, como é o caso deste estudo, deve-se atentar para alguns
detalhes de grande importância durante o processo de crossover, pois quando se utiliza a
representação ordinal para codificar o cromossomo, consegue-se, através de dois
cromossomos pais, gerar descendentes viáveis (POTVIN, 1996). Porém, quando a codificação
do cromossomo é feita através da representação de adjacência ou de caminho, ocorrerá a
geração de algumas rotas inviáveis devido à repetição de algumas cidades.
Visando solucionar este problema, diversos processos de crossover foram propostos.
Uns foram desenvolvidos para utilização no PCV, cujo cromossomo é codificado na
representação de adjacência; e outros, para a de caminho. Dentre eles, alguns são:
Partially-Mapped Crossover (PMX)
O operador PMX proposto por (GOLDBERG e LINGLE, 1985) - para o cruzamento
de cromossomos de representação por caminho constrói descendentes através da seleção
aleatória de dois pontos de corte para ambos os pais e, em seguida, realiza-se a troca entre os
pontos de corte de ambos, concluindo-se os descendentes com o preenchimento adequado dos
genes fora dos pontos de corte. Por exemplo:
Dado os cromossomos P1=(1 2 3 | 4 5 6 7 | 8 9) e P2=(4 5 2 | 1 8 7 6 | 9 3), já representados
com os pontos de corte:
Primeiro, os segmentos que estão entre os pontos de corte são trocados:
D1=(x x x | 1 8 7 6 | x x)
D2=(x x x | 4 5 6 7 | x x )
36
Esta troca define os seguintes mapeamentos entre os valores:
4↔1 5↔8 6↔7 7↔6
Preenchem-se os trechos que faltam, utilizando-se os elementos originais de cada pai dado,
evitando a repetição de cidades:
D1=(x 2 3 | 1 8 7 6 | x 9)
D2=(x x 2 | 4 5 6 7 | 9 3 )
Conclui-se, utilizando o mapeamento gerado pela troca feita entre os pontos de corte:
D1=(4 2 3 | 1 8 7 6 | 5 9)
D2=(1 8 2 | 4 5 6 7 | 9 3 )
Cycle Crossover (CX)
O operador CX, proposto por (OLIVER, SMITH e HOLLAND, 1987), constrói
descendentes para cromossomos de representação por caminho, de modo que cada cidade e a
sua posição venham de um dos pais. Isto funciona da seguinte maneira:
Sejam os dois cromossomos abaixo:
P1 = (1 2 3 4 5 6 7 8 9)
P2 = (4 1 2 8 7 6 9 3 5)
O primeiro descendente é produzido pegando-se o primeiro elemento do primeiro pai (neste
caso, 1). A cidade correspondente à posição 1 no segundo pai é a cidade 4; portanto deve-se
colocá-la também no primeiro descendente, na mesma posição em que ela se encontra no
primeiro pai. Desta forma, teremos inicialmente um cromossomo com a seguinte forma:
D1=(1 x x 4 x x x x x)
Por sua vez, a escolha da cidade 4 implica a escolha da cidade 8 (que é a cidade situada na
posição 4 do segundo pai). Seguindo esta regra, as próximas cidades a serem escolhidas são a
3 e a 2.
D1=(1 2 3 4 x x x 8 x)
Deve-se notar que, após escolher a cidade dois, a próxima cidade que deve ser incluída é a 1,
que já se encontra no cromossomo D1.
37
Portanto devem-se pegar as próximas cidades do segundo pai. Repetindo-se esta operação
para o segundo descendente, tem-se finalmente:
D1=(1 2 3 4 7 6 9 8 5)
D2=(4 1 2 8 5 6 7 3 9)
Order Crossover (OX)
Este operador, proposto por (DAVIS, 1985), fornece geralmente resultados muito
melhores que os dois processos citados anteriormente (POTVIN, 1996). Ele, o qual também é
utilizado para cromossomos de representação por caminho, gera descendente através da
escolha de dois pontos de cortes para os pais.
Inicialmente, o processo gera um filho, repetindo o trecho entre o ponto de corte de
um dos pais. Em seguida, completará o restante do cromossomo com os genes do outro pai,
na ordem em que neste aparecem, a partir do segundo ponto de corte, e evitando a formação
de cromossomos inválidos. Posteriormente, o outro filho, que repete o trecho entre os pontos
de corte do outro pai, é gerado seguindo o mesmo processo. Como exemplo, considere os
cromossomos abaixo, com os pontos de corte já definidos:
P1=(1 2 3 | 4 5 6 7 | 8 9)
P2=(4 5 2 | 1 8 7 6 | 9 3)
Repete-se o trecho entre os pontos de corte do P1:
D1=(x x x | 4 5 6 7 | x x)
A seqüência do segundo pai, partindo do segundo ponto de corte é (9 3 4 5 2 1 8 7 6) onde,
removendo os pontos (4 5 6 7), que já existem, ficaria (9 3 2 1 8), que seria colocado no filho
a partir do segundo corte:
D1= (2 1 8 | 4 5 6 7 | 9 3)
Realizando em seguida o processo para o segundo filho, o resultado será:
D2= (3 4 5 | 1 8 7 6 | 9 2).
Alternate Edge crossover
Este operador, segundo (POTVIN, 1996), é apenas de interesse histórico. Utilizado em
cromossomos de representação por adjacência, ele tem apresentado resultados desanimadores,
38
como relatados em (GREFENSTETTE et al., 1985). Entretanto, o mesmo é uma boa
introdução aos outros operadores do tipo preservar-adjacência.
Seu processo de funcionamento procede-se da seguinte forma: inicia-se selecionando
uma adjacência (i, j) aleatoriamente em um pai. Então, a rota é estendida selecionando a
adjacência (j, k) no outro pai. A rota é estendida progressivamente desta maneira,
selecionando alternativamente adjacências dos dois pais. Quando uma adjacência introduz um
ciclo, a nova adjacência é selecionada em aleatório (e não é herdado dos pais).
Edge Recombination Crossover (ER)
Neste operador, proposto por (WHITLEY, STARKWEATHER e FUQUAY, 1989)
para ser utilizado principalmente em cromossomos de representação por adjacência, os
descendentes devem ser construídos exclusivamente a partir das adjacências presentes nos
dois pais. Isto é feito com o auxílio de um mapa de adjacências, criado a partir das rotas dos
dois pais. Este mapa fornece, para cada cidade c, todas as outras cidades conectadas a ela,
tanto no primeiro, quanto no segundo pai. Obviamente que, para cada cidade c, existem pelo
menos duas e no máximo quatro cidades relacionadas a ela neste mapa de adjacência.
Considerando como exemplo os cromossomos de representação por adjacência:
(4 1 2 8 7 5 9 6 3) e (2 4 8 3 9 7 1 5 6),
cujo mapa de adjacência será o apresentado na Tablea 3.1, a geração de um cromossomo filho
seguirá o seguinte processo:
Tabela 3. 1
Mapa de adjacência do Edge Recombination Crossover
A cidade Tem adjacência com
1 2, 4, 7
2 1, 3, 4
3 2, 4, 8, 9
4 1, 2, 3, 8
5 6, 7, 8, 9
6 5, 7, 8, 9
7 1, 5, 6, 9
8 3, 4, 5, 6
9 3, 5, 7, 6
39
Escolhendo-se como cidade inicial, para o cromossomo filho, a primeira cidade do primeiro
cromossomo pai (cidade 4), tem-se como opções de cidades para seguir posteriormente, as
cidades (1, 2, 3, 8).
A cidade 1 tem como opções de cidades para seguir posteriormente (2, 7);
A cidade 2 tem (1, 3);
A cidade 3 tem (2, 8, 9); e
A cidade 8 tem (3, 5, 6);
Deve-se escolher a cidade que tem a menor opção de cidades para seguir posteriormente.
Neste exemplo, existem duas opções. Escolhendo-se a cidade 2, tem-se:
A cidade 1 tem como opção de cidade para seguir posteriormente ( 7 ); e
A cidade 3 tem (8, 9).
Escolhe-se a cidade 1.
Escolhe-se a cidade 7, a qual tem como opções de cidades para seguir posteriormente:
A cidade 5, cujas opções de cidades para seguir posteriormente são (6, 8, 9);
A cidade 6 tem (5, 8, 9) e a cidade 9 tem (3, 5, 6).
Escolhendo-se a cidade 5, as opções de cidade para seguir posteriormente são:
A cidade 6, cujas opções de cidades para seguir posteriormente são (8, 9);
A cidade 8 tem (3, 6) e a cidade 9 tem (3, 6).
Escolhendo-se a cidade 6, as opções de cidade para seguir posteriormente são as cidades 8 e
9, onde ambas têm a cidade 3 como opção de seguir posteriormente.
Escolhendo-se a cidade 8, terá como conseqüência a escolha da cidade 3 e, posteriormente,
finaliza-se o cromossomo filho com a escolha da cidade 9.
Após este processo, o cromossomo gerado será ( 4 2 1 7 5 6 8 3 9).
3.1.1.4 – A Mutação
Quanto ao operador genético de Mutação, sua função é gerar perturbações aleatórias
no processo de busca, visando com isto introduzir diversidade em populações homogêneas, de
forma que se evite uma prematura convergência da população.
40
Um operador clássico de mutação é o que gera uma alteração aleatória no código
genético do indivíduo através da mudança de valores em um ou em dois genes (Figura 3.7).
Figura 3. 7 – Operador Clássico de Mutação
Assim como no crossover, a mutação também necessita de algumas adaptações para
tratar o PCV, sem que sejam gerados cromossomos inviáveis. Ao contrário do operador
clássico de mutação, que introduz pequenas perturbações no cromossomo, os operadores de
mutação para o PCV, frequentemente, modificam extremamente a rota original (POTVIN,
1996). Alguns desses operadores são classificados como:
i - SWAP: Duas cidades são selecionadas aleatoriamente e suas posições são trocadas;
ii - INVERSÃO DE POSIÇÃO (POSITION INVERSION – PI): Neste operador, dois pontos
de corte são selecionados em aleatório no cromossomo e a posição dos genes, entre esses
pontos de corte, são invertidas;
iii - LOCAL HILL-CLIMBING: Este operador é basicamente uma Heurística de troca de
vizinhança k-opt. No processo Inversão de Posição, apenas uma troca 2-opt é realizada
(POTVIN, 1996), e neste processo a troca entre os genes é realizada para um número fixo de
iterações, ou até um ótimo local ser encontrado.
iv - ROTAÇÃO A ESQUERDA (ROTATION LEFT MUTATION – RLM) E ROTAÇÃO A
DIREITA (ROTATION RIGHT MUTATION – RRM): Os operadores de rotação à esquerda
e de rotação à direita, simplesmente deslocam o cromossomo, um número aleatório de
posições para a esquerda ou para a direita, respectivamente.
41
3.1.2 - Algoritmo Memético
Segundo (WAIZBORT, 2003), a idéia inicial de memes, apresentada por Richard
Dawkins na década de 70, é que eles são, basicamente, idéias, ou informações armazenadas
no cérebro e reproduzidas de mente para mente através da aprendizagem; sendo responsáveis
pelo desenvolvimento do cérebro humano, da indústria de ferramentas, da cultura e da
sociedade. Isto significa que a evolução dos indivíduos se dá não apenas pela reprodução dos
seres mais aptos, mas também pelo acúmulo de experiências que um indivíduo absorve ao
longo de sua existência e repassa as gerações futuras.
O método híbrido apresentado por Moscato em (MOSCATO, 1989), mais conhecido
por Algoritmo Memético (Algoritmo 3.2), funciona como uma variante do Genético, pois se
utiliza dos mesmos operadores genéticos e ainda apresenta o conceito de “evolução cultural”,
onde a adaptabilidade de um indivíduo pode ser modificada no decorrer de sua existência
dentro da população (MENDES, 1999). Alguns fatores populacionais, como por exemplo, as
experiências pessoais e as trocas de informações com outros indivíduos da população podem
fazer com que aquele que nasceu geneticamente pouco favorecido consiga se tornar mais
adaptado (evoluir) ao longo da sua vida e até transmitir essas experiências aos seus
descendentes.
Algoritmo 3. 2
Algoritmo Memético Clássico
Este método tem-se apresentado na literatura como uma Metaheurística muito
eficiente na resolução de problemas na área de Otimização Combinatória, pois, se comparado,
por exemplo, ao Algoritmo Genético, consegue realizar uma busca mais rápida para
problemas com um grande conjunto-solução, fornecendo conseqüentemente, melhores
resultados.
1: P � População Inicial;
2: Busca Local ( P );
3: avaliar ( P );
4: enquanto condição não satisfeita faça
5: P’ � Seleção( P );
6: P � Cruzamentos( P’ );
7: P � Mutações ( P );
8: Busca Local ( P );
9: avaliar ( P );
10: fim enquanto
42
3.1.2.1 – A Busca Local
Algoritmos Meméticos (AM´s) são como uma evolução dos AG´s que utilizam uma
busca local nos seus operadores de forma a agilizar a execução (NORONHA, ALOISE e
SILVA, 2001). Porém, nos casos de grandes instâncias, deve-se atentar para o uso de bons
operadores de busca local, devido ao tamanho da vizinhança associada. Uma das formas de
contornar esse problema é o emprego de técnicas para redução de vizinhança (GARCIA et
al.), ou o uso de técnicas que acelerem o processo de busca na vizinhaça.
A busca local realizada na vizinhança dos indivíduos de uma população é uma procura
visando encontrar melhores indivíduos e com isto transformar a população em indivíduos que
seriam mínimos locais. Então, esta busca no Algoritmo Memético seriam as experiências que
fazem os indivíduos evoluir dentro de uma geração.
3.1.2.2 – A Geração
A população de um Algoritmo Memético, para um dado instante do tempo, é
conhecida por geração e sempre constituída de agentes (Figura 3.8), os quais representam as
soluções atuais de determinado problema, dentro do espaço de soluções deste, sendo cada
agente constituído de memes e do fitness, onde este último representa o nível de aptidão.
Figura 3. 8 - Representações do Agente
Como se pode observar, o Algoritmo Memético Clássico utiliza alguns termos
diferentes do Algoritmo Genético para representação da solução de um problema; porém,
como dito anteriormente, faz uso dos mesmos operadores genéticos, utilizando-se também,
quando se trata do Problema do Caixeiro viajante Assimétrico, para os operadores de
cruzamento e mutação, dos mesmos processos citados para se evitar a formação de rotas
inviáveis.
Agente:
Meme
5 2 3 6 1 7 #
Fitness
43
3.2 - Infecção Viral
Alguns autores como Nakahara e Sagawa propõem que, na teoria da evolução, o
material genético pode ser transferido de um organismo para outro através de vírus (KANOH
et al., 1996); ou seja, um vírus carregando material genético pode infectar um organismo e
reescrever o gene do organismo alvo (LARTIGUE).
Na memética, a qual estuda os memes, certos grupos de memes podem agir como
vírus meméticos, ou seja, como padrões de informações que são transmitidas entre os
indivíduos ao longo de gerações, por serem considerados bons memes; ou seja, por serem
memes que mantêm alguns padrões considerados necessários a uma sociedade.
A infecção viral surge no contexto dos algoritmos evolutivos substituindo o operador
de mutação (Algoritmo 3.3), por conseguir uma rápida evolução ou extinção de espécies. Em
(KANOH et al., 1996), a aplicação do Algoritmo Genético com Infecção Viral aplicado ao
Problema de Restrição de Satisfação resultou em um decréscimo no tempo de busca se
comparado ao Algoritmo Genético.
Algoritmo 3. 3
Algoritmo Genético Com Infecção Viral
Fonte: (GUEDES, LEITE e ALOISE, 2005).
Alguns problemas na literatura vêm sendo solucionados através de Algoritmo
Genético com infecção viral, o qual tem fornecido bons resultados. Como exemplos, têm-se:
aplicações em Sistemas de Navegação de Carros (KANON e NAKAMURA, 2000), Problema
1. [Inicialização] Gerar uma população inicial de n cromossomos, aleatoriamente, e determinar a fitness de cada cromossomo. Gerar uma população inicial de vírus, aleatoriamente;
2. [Infecção] Aplicar o operador de infecção nos melhores indivíduos da população.
3. [Geração da Nova população] Criar uma nova população através da aplicação das seguintes etapas:
a) [Seleção] Selecionar dois cromossomos-pais da
população atual de acordo com sua fitness;
b) [Crossover] Fazer o cruzamento dos pais para formar
novos indivíduos (filhos).
4. [Avaliar nova população] Calcular a fitness de cada cromossomo da população recém gerada;
5. [Teste de parada] Se condição de parada satisfeita: finalizar retornando a melhor solução encontrada. Caso contrário, voltar ao passo 2.
44
do Caixeiro Viajante Simétrico (GUEDES, LEITE e ALOISE, 2005), Problema de Restrição
de Satisfação (KANOH et al., 1996), Problema da Mochila (LARTIGUE), Problema de
Quadro de Horários (KANOH, KONDO e SUGIMOTO, 2002), etc. E segundo (KANOH,
KONDO e SUGIMOTO, 2002) o uso da Infecção viral no Algoritmo Genético melhora a taxa
de busca do algoritmo.
3.2.1 – O Vírus
O vírus seria uma solução parcial que, ao infectar um indivíduo, reescreve o material
genético deste, aumentando ou diminuindo seu valor de fitness. Considerando-se o problema
do Caixeiro Viajante, onde o cromossomo representa uma rota completa, um vírus seria o
trecho (pedaço) de uma rota (Ver Figura 3.9).
Assim como na genética, onde o vírus necessita de um organismo para interagir, e na
memética, onde os vírus memes necessitam de mentes para serem repassados, não se
perdendo ao longo de gerações, também nos algoritmos evolutivos um vírus só atuará na
evolução de uma geração se existir um cromossomo ou um agente (no caso do Algoritmo
Memético) onde ele possa hospedar-se, visto que o mesmo sempre será um trecho de uma
solução e nunca uma solução completa de determinado problema.
Assim como o indívíduo possui o seu valor de fitness, o vírus traz consigo uma taxa de
infectividade, que varia de acordo com a qualidade daquele vírus.
Figura 3. 9 - Exemplo de um vírus para um cromossomo de representação real
3.2.2 – A População de Vírus
O Algoritmo Genético com Infecção Viral mantém, além da população de
cromossomos, uma população extra, denominada população de vírus, gerada aleatoriamente,
Cromossomo:
Vírus: 3 7 *
5 2 3 6 1 7 4 #
Fitness
Taxa de Infectividade
45
ou a partir de parâmetros pré-definidos. Em alguns algoritmos, a geração da população de
vírus baseia-se no problema abordado.
Em (KANOH e NAKAMURA, 2000), utilizou-se o algoritmo genético com infecção
viral para resolver um problema de seleção de rotas; desejava-se partir de um ponto inicial e
chegar-se, pelo menor percurso, a um ponto final de um dado mapa. A população de vírus foi
gerada selecionando-se, aleatoriamente, uma área retangular no espaço situado entre o ponto
inicial e o ponto final do problema, retirando-se desta área pequenos trechos de rotas.
3.2.3 – A Infecção
O Vírus é selecionado para infectar um indivíduo de acordo com a sua infectividade.
A um vírus com uma alta taxa de infectividade será mais provável infectar um indivíduo do
que um vírus com uma baixa taxa de infectividade (LARTIGUE).
O ato de infectar um cromossomo é chamado de transcrição (Figura 3.10). Este
processo consiste em o vírus modificar o cromossomo infectado, de forma que esse contenha
um trecho idêntico ao representado pelo agente infectante, e fazer os ajustes necessários para
a manutenção da viabilidade do indivíduo receptor da carga viral (GUEDES, LEITE e
ALOISE, 2005).
Após a infecção, a taxa de infectividade aumenta ou diminui, como resultado de
reescrever um cromossomo de um indivíduo com um vírus, e conseguir aumentar ou
diminuir, respectivamente, a fitness do cromossomo.
3.3 - O Algoritmo Memético com Infecção Viral
Nesta pesquisa, desenvolveu-se uma nova variante para o Algoritmo Memético, que é
um Algoritmo Memético com Infecção Viral, para aplicação no Problema do Caixeiro
Viajante Assimétrico. Foram propostas quatro Implementações. Duas delas trabalham com
uma população fixa e uma população variável de vírus ; as outras duas utilizam-se de um
melhor aprimoramento durante o processo de substituição de vírus na sua população fixa.
Nestas propostas, o operador de mutação do algoritmo é substituído pela infecção viral, onde
o vírus da população fixa e o agente passam por um processo de simbiose, ocorrendo no
vírus: uma substituição de gene (transdução), ou um aumento do número de genes, ou
diminuição do número de genes.
46
3.3.1 - Implementação 1
Esta implementação diferencia-se das seguintes pela sua população variável de vírus.
Para gerar-se esta população, identificam-se as arestas que estão presentes em todos os
agentes da geração atual. Os pares de vértices que formam estas arestas serão os vírus da
população variável (Algoritmo 3.4). Conseqüentemente, os vírus desta população terão um
tamanho dois. É sempre uma população variável, devido a cada geração, à quantidade de
arestas presentes em todos os agentes poder ser diferente. Além da produção de uma
população variável de vírus, é produzida também uma população fixa de vírus, a qual, neste
estudo, foi obtida aleatoriamente.
Algoritmo 3. 4
Algoritmo Memético Com Infecção Viral 1
Na obtenção de uma geração inicial de agentes, um agente é produzido utilizando-se a
Heurística GKS (GLOVER et al., 1999); para cada um dos agentes restantes há uma
probabilidade em 50% de que estes sejam produzidos pelo método do Vizinho Mais Próximo
e 50%, pelo método da Inserção Arbitrária (Algoritmo 3.5). Esta Heurística de Inserção
Arbitrária foi conseguida alterando-se o passo 1 da Heurística de Inserção Mais Próxima
(Algoritmo 2.2).
1 -Início 2 Produzir uma geração inicial de Agentes 3 Produzir uma população fixa de Vírus 4 Avaliar a fitness dos agentes da Geração 5 Busca Local para cada agente da geração 6 Repetir 7 Nova Geração = conj. vazio 8 elitismo 9 Infecção com a população fixa de vírus 10 Repetir 11 Selecionar um conjunto de pais na Geração 12 Cruzar os pais de modo a que se reproduzam 13 Ate que a nova geração esteja completa 14 Identificar as arestas que se repetem em todos os Agentes 15 Produzir uma população variável de Vírus com essas arestas 16 Infecção com a população variável de vírus 17 Avaliar a fitness dos filhos gerados 18 Busca Local em alguns agentes 19 Até que o critério de parada seja atendido 20 -Fim
47
Algoritmo 3. 5
Heurística de Inserção Arbitrária
A forma de representação utilizada para os agentes do algoritmo foi a codificação de
caminho, que é a forma mais empregada de representação quando se trata do PCV, onde o
número de cada cidade é associado a cada meme, sendo a solução dada pela seqüência em que
tais memes aparecem no agente. O nível de aptidão (fitness) de cada agente, para esta forma
de codificação, representa o comprimento da solução parcial.
A função de avaliar a fitness é responsável por medir a qualidade da solução
representada por cada agente da geração.
Para este Algoritmo, utilizou-se a busca local do tipo descida mais rápida numa
vizinhança onde: dada a solução ),...,,,...,,,,...,( 1111 njjiii ππππππππ ++−= , obtém-se uma
vizinhança para esta solução através da inserção de uma cidade iπ , em uma posição qualquer.
Ficando:
}{ nijniV njijii ,...,1;1,...,1),...,,,,...,,,...,()( 1111 +=−=∴= ++− ππππππππ .
Inicialmente, a busca local é realizada para todos os agentes da população, permitindo
que, para geração dos primeiros descendentes, o algoritmo partirá somente de mínimos locais.
Para as gerações seguintes, a busca local é realizada apenas em alguns indivíduos, pois, caso
contrário, o algoritmo ficaria com um tempo de convergência elevado.
No Elitismo, que um processo de seleção, alguns dos agentes com melhores fitness,
pertencentes à geração atual, farão, automaticamente, parte da nova população de indivíduos.
Isto evita que o algoritmo perca o melhor resultado obtido a cada geração.
3.3.1.1 - A Infecção
Na Infecção com a população fixa, aqueles agentes com melhores fitness, pertencentes
à geração atual, serão infectados por todos os vírus dessa população e, após este processo, os
Passo 0: Inicializar o ciclo com apenas um vértice. Passo 1:
Escolher qualquer vértice K fora do ciclo corrente. Passo 2: Encontrar o par de arestas (i,k) e (k,j) que ligam o vértice k ao ciclo, minimizando cik + ckj - cij
Inserir as arestas (i,k) e (k,j) e retirar a aresta (i,j). Passo 3:
Retornar ao passo 1.
48
quatro agentes que apresentarem os melhores fitness também farão parte da nova geração de
indivíduos (Algoritmo 3.6).
A infecção com população de vírus variável ocorre depois que a nova população é
completada. Nesse procedimento, aqueles agentes com melhores fitness, pertencentes à nova
geração, serão infectados por todos os vírus da população variável (Algoritmo 3.4).
Algoritmo 3. 6
Algoritmo Infecção
Para realizar-se o processo de transcrição neste trabalho, foi feita uma lista com os
memes do agente a ser infectado, retirando-se os existentes no vírus (evita a formação de
descendentes com memes repetidos) e mantendo-se a ordem de precedência com que eles
aparecem no agente. Em seguida, o vírus é testado entre cada par desses memes da lista,
escolhendo-se como posição para incluí-lo aquela em que o agente resultante terá um maior
fitness (Figura 3.10).
Figura 3. 10 – Processo de Transcrição
1 5 7 2 3 6 8 4
1 7 1 7
5 2 3 6 8 4 5 2 3 1 7 6 8 4
1 Infecção
2 Selecione os melhores indivíduos
3 Para cada um destes melhores indivíduos faça
4 Transcrição com cada vírus
5 Se individuo aumentou o fitness
6 Taxa de infectividade do vírus aumenta
7 Simbiose
8 Senão
9 Taxa de infectividade do vírus diminui
10 Simbiose
11 Fim se
12 Aceita-se os 4 melhores indivíduos na nova população
13 Fim para
14 Fim
49
3.3.1.2 - A Simbiose
Na Biologia, é apresentado o termo Simbiose sempre que ocorre uma associação entre
dois indivíduos em que ambos recebem benefícios. Neste trabalho, utilizou-se este conceito
devido à associação entre o vírus da população fixa e o agente beneficiar ambos, gerando, no
agente, descendentes com melhores fitness e, no vírus, possíveis alterações no seu material
genético.
A alteração no material genético do vírus se dá devido ao fato de que, ao longo da
evolução de gerações, esses sofrerão alterações nos seus tamanhos. Eles podem adquirir
partes do material genético do agente (aumento do tamanho), abandonar partes do seu
material genético (diminuição do tamanho), ou simplesmente substituírem parte do seu
material genético pelo material genético do agente.
Na geração da população fixa de vírus, eles terão sempre um tamanho mínimo pré-
definido e se, durante a evolução das gerações, determinados vírus mantiverem-se como bons
agentes infectantes, eles poderão chegar até um tamanho máximo.
Então, quando um vírus da população fixa infectar um agente e atingir sua taxa de
infectividade máxima, ele incorpora um dos memes do agente que está ao seu lado (Figura
3.11) e, com isso, transforma-se num novo vírus; portanto, terá uma taxa de infectividade
igual à inicial. Já quando o vírus infectar um agente, porém diminuir o valor de fitness do
indivíduo, sua taxa de infectividade diminui. Chegando esta taxa a um valor nulo, e o vírus
não estando no seu tamanho mínimo, este abandonará um meme de uma de suas extremidades
(aquele de maior custo) e, com isto, poderá retornar a um vírus existente anteriormente. Ao
final desse processo, o vírus passa a ter a sua taxa de infectividade igual ao valor máximo.
Figura 3. 11 - Aumento do Vírus
Este processo de aumentar e diminuir o vírus não entra num ciclo sem saída devido à
população de agentes estar se modificando a cada iteração. Um vírus que não foi bom para
uma determinada geração poderá, em gerações futuras, tornar-se muito bom. O fato de um
vírus sofrer contínuos aumentos e diminuições não é algo preocupante: o vírus só aumenta
quando consegue melhorar indivíduos da população, o que é um efeito obviamente desejado.
5 2 3 6 1 7 8 4 5 2 3 6 1 7 8 4
50
O vírus da população variável não necessita de taxa de infectividade, visto que a sua
existência na geração seguinte está condicionada à repetição de arestas em todos os agentes da
nova geração. Conseqüentemente, esses vírus não passarão pelo processo de Simbiose.
Ainda no processo de Simbiose, pode acontecer o fato de o vírus estar no seu tamanho
mínimo e, por não ter feito boas infecções, também possuir uma taxa de infectividade nula,
sendo necessária a sua eliminação. Como a população de vírus possui uma quantidade fixa,
para que um deixe de existir, outro deve ser gerado. O procedimento a seguir (Algoritmo 3.7)
mostra que, ao se chegar a essa situação, existem duas possibilidades para a geração de um
novo vírus. Optou-se por criar um número aleatório. Estando este dentro de certa
probabilidade pré-definida, o vírus poderá ser gerado por um processo de Transdução ou ser
gerado aleatoriamente. Caso o vírus passe pelo procedimento de Transdução, o vírus gerado
passará a ter uma taxa de infectividade igual à inicial; se o vírus foi gerado aleatoriamente, a
sua taxa de infectividade inicial terá um valor nulo.
Algoritmo 3. 7
Simbiose 1
1 Simbiose 2 Se ((taxa de infectividade > 0) e (taxa de infectividade < máxima)) então 3 Sair da Simbiose 4 Fim Se 5 Se( taxa de infectividade = máxima) então 6 Se (vírus < tamanho máximo) então 7 Aumentar o Vírus 8 Taxa de infectividade é igual à inicial 9 Fim Se 10 Senão 11 Se (vírus > tamanho mínimo) então 12 Diminuir o vírus 13 Taxa de infectividade é máxima 14 Senão 15 Se (nº aleatório estiver dentro de uma certa probabilidade) então 16 Transdução 17 Taxa de infectividade é igual à inicial 18 Senão 19 Gera-se outro vírus aleatoriamente 20 Taxa de infectividade é nula 21 Fim Se 22 Fim Se 23 Fim Se 24 Fim
51
Segundo (GUEDES, LEITE e ALOISE, 2005), a transdução (Figura 3.12), é um
procedimento que caracteriza a analogia de infecção viral nos seres vivos, onde o vírus se
modifica para melhor adaptar-se ao ambiente. No Algoritmo em estudo, o vírus de tamanho
mínimo e taxa de infectividade nula descarta uma de suas partes e copia para si um meme do
último agente por ele infectado.
Figura 3. 12 – Processo de transdução
Somente após o processo de Infecção com a população de quantidade fixa é que o
Algoritmo Memético desenvolvido seleciona, dentre todos os agentes da geração atual, um
conjunto de pais, para que, no operador de cruzamento, eles se reproduzam, gerando
descendentes que completarão a nova população de indivíduos.
Para o operador genético de seleção, optou-se, neste trabalho, pelo método de
Nivelamento Linear (Linear Ranking Selection) proposto por (BAKER, 1989).
Por estar-se desenvolvendo uma Metaheurística para o Problema do Caixeiro Viajante,
houve a preocupação de evitar, no processo de cruzamento, a formação de rotas inválidas. Por
isto utilizou-se o Order Crossover (OX), o qual foi proposto por (DAVIS, 1985), e que se
apresenta com bons resultados na literatura.
3.3.2 – Implementação 2
Esta implementação diferencia-se da anterior por realizar, antes da produção de uma
população variável de vírus, não apenas a identificação das arestas que se repetem em todos
os agentes da geração atual, mas também o processo de Normalização (Algoritmo 3.8).
No processo de Normalização, o que ocorre é: depois de identificado o conjunto de
arestas, identificam-se e concatenam-se, neste conjunto, trechos que são formados por arestas
adjacentes. O novo conjunto formado consistirá dos trechos concatenados e dos não
concatenados, e representarão a nova população variável de vírus (Figura 3.13).
5 2 3 6 1 7 8 4 5 2 3 6 1 7 8 4 5 2 3 6 1 7 8 4
52
Figura 3. 13 – Normalização da população variável de vírus.
Portanto, a população variável de vírus será constituída por elementos de diferentes
tamanhos, visto que agora é composta de trechos que podem ter três ou mais nós e não apenas
de pares de vértices, como na implementação 1.
No restante desta implementação, segue-se o processo semelhante ao apresentado na
implementação 1.
Algoritmo 3. 8
Algoritmo Memético Com Infecção Viral 2
3.3.3 – Implementação 3
Nesta implementação, não se trabalha mais com a população variável de vírus,
existindo apenas a população fixa (Algoritmo 3.9).
4 6 2 8 2 58 1
1 5 9 3 9 3
7 4 8 1 7 4 6
1 -Início 2 Produzir uma geração inicial de Agentes 3 Produzir uma população fixa de Vírus 4 Avaliar a fitness dos agentes da Geração 5 Busca Local para cada agente da geração 6 Repetir 7 Nova Geração = conj. vazio 8 elitismo 9 Infecção 10 Repetir 11 Selecionar um conjunto de pais na Geração 12 Cruzar os pais de modo a que se reproduzam 13 Ate que a nova geração esteja completa 14 Identificar as arestas que se repetem em todos os Agentes 15 Normalização 16 Produzir uma população variável de Vírus
17 Infecção com a população variável de vírus 18 Avaliar a fitness dos filhos gerados 19 Busca Local em alguns agentes 20 Até que o critério de parada seja atendido 21 -Fim
53
Algoritmo 3. 9
Algoritmo Memético Com Infecção Viral 3
A produção da população inicial de agentes e a população inicial de vírus seguem os
mesmos processos anteriores. A busca local continuou sendo do tipo descida mais rápida
numa vizinhança onde: dada a solução ),...,,,...,,,,...,( 1111 njjiii ππππππππ ++−= , obtém-se
uma vizinhança para esta solução, através da inserção de uma cidade iπ , em uma posição
qualquer. Ficando:
}{ nijniV njijii ,...,1;1,...,1),...,,,,...,,,...,()( 1111 +=−=∴= ++− ππππππππ
Sendo que, inicialmente, a busca local é realizada para todos os agentes da população
e, posteriormente, apenas em alguns indivíduos.
Por não existir a população variável de vírus, o processo de infecção (Algoritmo 3.6)
dá-se apenas com a população fixa de vírus.
Outra característica da Implementação 3 ocorre durante o processo de Simbiose
(Algorimto 3.10), pois, quando o vírus encontra-se com uma taxa de infectividade nula e um
tamanho mínimo, ele é substituído por um outro vírus, o qual pode ser gerado de duas formas
distintas:
• Transdução (conforme citado anteriormente);
1 -Início
2 Produzir uma geração inicial de Agentes
3 Produzir uma população inicial de Vírus
4 Avaliar a fitness dos agentes da Geração
5 Busca Local para cada agente da geração
6 Repetir
7 Nova Geração = conj. vazio
8 elitismo
9 Infecção
10 Repetir
11 Selecionar um conjunto de pais na Geração
12 Cruzar os pais de modo a que se reproduzam
13 Ate que a nova geração esteja completa
14 Avaliar a fitness dos filhos gerados
15 Busca Local em alguns agentes
16 Até que o critério de parada seja atendido
17 -Fim
54
• Identificam-se as arestas existentes em todos os agentes da população atual e
escolhe-se aleatoriamente uma dessas arestas para que o seu par de vértices
seja o novo vírus.
Lembrando que a escolha entre as duas opções é feita a partir de um número aleatório,
o qual estando dentro de uma probabilidade pré-definida, o vírus poderá ser gerado pela
primeira ou pela segunda opção.
Se o operador de Transdução for aplicado, o vírus passa a ter infectividade igual à
inicial. Caso contrário, sua infectividade passa a ser nula.
Algoritmo 3.10
Simbiose 2
O processo de identificação das arestas que se repetem em todos os agentes é
semelhante ao utilizado no (algoritmo 3.4), sendo que, naquele, os pares de vértices de todas
as arestas identificadas foram utilizados como vírus da população variável, enquanto que,
1 Simbiose
2 Se ((taxa de infectividade > mínima) e (taxa de infectividade < máxima)) então
3 Sair da Simbiose
4 Fim Se
5 Se( taxa de infectividade = máxima) então
6 Se (vírus < tamanho máximo) então
7 Aumentar o Vírus
8 Taxa de infectividade é mínima
9 Fim Se
10 Senão
11 Se (vírus > tamanho mínimo) então
12 Diminuir o vírus
13 Taxa de infectividade é máxima
14 Senão
15 Se (nº aleatório estiver dentro de uma certa probabilidade) então
16 Transdução
17 Taxa de infectividade é igual à inicial
18 Senão
19 Identifica-se as arestas que se repetem em todos os agentes
20 Escolhe-se aleatoriamente como vírus o par de vértices de uma das arestas identificadas
21 Taxa de infectividade é nula
22 Fim Se
23 Fim Se
24 Fim Se
25 Fim
55
neste algoritmo, após identificadas as arestas, apenas uma é escolhida aleatoriamente para que
seu par de vértices faça parte da população fixa de vírus. Como apenas um vírus deixou de
existir por não ser um bom vírus (taxa de infectividade mínima), somente um vírus poderá ser
gerado; caso contrário, a população deixaria de ter uma quantidade fixa de vírus.
3.3.4 - Implementação 4
Esta última Implementação diferencia-se da Implementação 3 por realizar, durante o
processo de Simbiose (Algoritmo 3.11), a Normalização com as arestas identificadas.
Algoritmo 3.11
Simbiose 3
1 Simbiose
2 Se ((taxa de infectividade > mínima) e (taxa de infectividade < máxima)) então
3 Sair da Simbiose
4 Fim Se
5 Se( taxa de infectividade = máxima) então
6 Se (vírus < tamanho máximo) então
7 Aumentar o Vírus
8 Taxa de infectividade é mínima
9 Fim Se
10 Senão
11 Se (vírus > tamanho mínimo) então
12 Diminuir o vírus
13 Taxa de infectividade é máxima
14 Senão
15 Se (nº aleatório estiver dentro de uma certa probabilidade) então
16 Transdução
17 Taxa de infectividade é mínima
18 Senão
19 Identificar as arestas que se repetem em todos os agentes
20 Normalização
21 Escolhe-se aleatoriamente como vírus um dos trechos
22 Taxa de infectividade é mínima
23 Fim Se
24 Fim Se
25 Fim Se
26 Fim
56
O processo de identificação das arestas que se repetem em todos os agentes e o
processo de Normalização são semelhantes ao utilizado no (algoritmo 3.8). Naquele, todos os
trechos foram utilizados como vírus da população variável, enquanto que nesta
Implementação, após determinados os trechos, apenas um é escolhido (aleatoriamente) para
fazer parte da população fixa de vírus. A diferença entre esse algoritmo e o (Algoritmo 3.10) é
que, naquele, o vírus gerado terá um tamanho mínimo dois, pois corresponde a um par de
vértices de uma determinada aresta, enquanto que, nesse novo método, o vírus pode
corresponder a um trecho de três ou mais vértices. Portanto, cada vez que um novo vírus for
gerado, após passar pela Normalização, poderá ter um tamanho diferente do tamanho mínimo.
57
Capítulo 4
Experimentação
Este capítulo descreve de forma detalhada a metodologia utilizada ao longo desta
dissertação, descrevendo os dados coletados e sua implementação, culminando em resultados
quantificáveis, presentes ao longo das tabelas nele contidas. Esses resultados serviram para
apresentar as discussões quanto à eficácia da Infecção Viral no Algoritmo Memético.
Procurando relatar a seqüência de atividades da pesquisa de uma forma lógica, quanto
ao período dos acontecimentos, este capítulo está dividido em dois tópicos, sendo o primeiro a
Metodologia e o segundo, os Resultados e Discussões.
4.1 - Metodologia
A pesquisa desenvolvida neste trabalho é de natureza aplicada, pois segundo (SILVA
e MENEZES, 2001), na pesquisa aplicada, pretende-se gerar conhecimento para aplicação
prática na solução de problemas específicos; e esta dissertação contribuiu para a otimização
do Problema do Caixeiro Viajante Assimétrico, garantindo com isto que os setores produtivos
que buscam minimizar percursos, sejam eles na logística ou na perfuração de placas de
circuito impresso, possam reduzir seus gastos. No que se refere à forma de abordagem, esta
pesquisa é quantitativa; quanto aos seus objetivos, é exploratória.
Esta pesquisa foi exploratória em seu momento inicial, pois foi necessário um
levantamento bibliográfico, visando buscar um maior embasamento teórico. Por não se
realizar um estudo de campo que, segundo (VERGARA, 2000), é a investigação realizada no
local onde ocorre ou ocorreu um fenômeno, no caso em estudo, poderiam ter sido rotas que
ligam várias cidades; este levantamento bibliográfico se utilizou dos dados obtidos em
bibliotecas de instâncias do Problema do Caixeiro Viajante.
58
A pesquisa é quantitativa na sua fase de implementação, quando os dados obtidos
durante o levantamento bibliográfico foram apresentados de maneira quantificável, na forma
de variáveis; através de estudos em laboratório, foram feitas as devidas simulações em
computador.
4.1.1 - Universo e Amostra
O ambiente em estudo foi composto por instâncias da TSPLIB, encontradas no
endereço eletrônico:
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.
Foram feitos testes com as 27 instâncias assimétricas da TSPLIB: br17, ftv33, ftv35,
ftv38, p43, ftv44, ftv47, ry48p, ft53, ftv55, ftv64, ft70, ftv70, ftv90, ftv100, ftv110, ftv120,
kro124p, ftv130, ftv140, ftv150, ftv160, ftv170, rbg323, rbg358, rbg403 e rbg443.
4.1.2 - Coleta de Dados
No período de levantamento bibliográfico, coletou-se para cada instância do Problema
do Caixeiro Viajante Assimétrico a quantidade de cidades e a solução ótima.
4.1.3 - Tratamento dos Dados
Através da linguagem C++, os algoritmos foram implementados para realizar as
devidas simulações com as instâncias coletadas. Os Testes foram realizados em uma máquina
Pentium 4 HT de 2,8 GHz e 512 de memória RAM.
Estes resultados servirão para comparar as implementações do Algoritmo Memético
com Infecção Viral contra o Algoritmo Memético Clássico e verificar, nas diferentes
situações, quando ocorre uma melhor eficiência do vírus no algoritmo.
4.2 – Resultados e Discussões
Foram realizadas 10 execuções de 1 minuto para cada problema da TSPLIB,
contabilizando-se os resultados e números de gerações obtidos na média com este tempo.
Nos quatro algoritmos apresentados, a população de agentes foi composta de 20
indivíduos e a população fixa de vírus composta de 80 vírus.
59
A taxa de elitismo foi de 20%, como a população de agentes possui 20 indivíduos;
então, a cada geração, os 4 melhores agentes passam automaticamente para a nova população.
A taxa de infecção também foi de 20%, ou seja, a cada geração, os 4 melhores agentes
da população atual são infectados.
Os parâmetros utilizados para o vírus foram:
• Tamanho inicial do vírus: 2;
• Taxa de Infectividade inicial do vírus: 2;
• Taxa de Infectividade máxima do vírus: 4.
A taxa de crossover foi de 80% e a taxa de transdução de 60%.
O operador de busca local utilizado foi o de “relocação”, também conhecido como
“inserção” (FUNKE, GRÜNERT e IRNICH, 2005). A busca foi feita em 4 agentes.
A seguir, verificam-se os resultados nos testes computacionais:
As tabelas abaixo (Tabelas 4.1 a 4.4), demonstram os resultados obtidos com as
implementações dos algoritmos Memético Clássico e Memético com Infecção Viral, fazendo
uma comparação da performace entre os mesmos.
60
Tabela 4. 1
Resultados da Implementação AMIV 1 x Algoritmo Memético Clássico
Instância
Ótimos / Tentativas
[AM] Gap(%) [AM]
No. Médio de
Gerações [AM]
Ótimos / Tentativas
[AMIV] Gap(%) [AMIV]
No. Médio de
Gerações [AMIV]
br17 10 0,000 0,000 10 0,000 0,000 OK ftv33 5 2,636 2080,100 5 2,636 277,000 OK ftv35 1 1,174 3338,300 1 0,991 475,200 OK ftv38 0 1,190 3556,900 0 1,170 480,800 OK p43 0 0,130 3331,600 0 0,110 449,700 OK
ftv44 0 4,712 3172,500 0 4,117 431,200 OK ftv47 0 0,602 2979,100 0 0,552 406,200 OK
ry48p 0 1,734 2982,100 0 1,513 402,800 OK ft53 0 6,911 2708,500 0 5,983 365,900 OK
ftv55 0 2,674 2556,800 0 2,799 343,800 * ftv64 0 2,958 2172,500 0 2,936 293,600 OK ft70 0 1,464 1967,900 0 1,464 259,000 OK
ftv70 0 3,205 1949,400 0 3,149 259,000 OK ftv90 0 2,223 1405,300 0 1,792 189,000 OK
ftv100 0 2,069 1209,100 0 1,678 163,200 OK ftv110 0 3,867 1231,000 0 2,206 166,900 OK ftv120 0 2,579 1061,300 0 2,656 145,500 *
kro124p 0 4,663 938,900 0 5,125 129,100 * ftv130 0 3,078 823,200 0 3,078 115,100 OK ftv140 0 2,169 729,300 0 2,198 101,600 * ftv150 0 2,068 658,300 0 2,068 91,600 OK ftv160 0 0,596 587,600 0 0,335 81,900 OK ftv170 0 0,944 528,800 0 0,944 75,300 OK
rbg323 10 0,000 0,000 10 0,000 0,000 OK rbg358 10 0,000 0,000 10 0,000 0,000 OK rbg403 10 0,000 0,000 10 0,000 0,000 OK rbg443 10 0,000 0,000 10 0,000 0,000 OK Média 2,074 1,987 1554,389 2,074 1,833 211,237
61
Tabela 4. 2
Resultados da Implementação AMIV 2 x Algoritmo Memético Clássico
Instância
Ótimos / Tentativas
[AM] Gap(%) [AM]
No. Médio de
Gerações [AM]
Ótimos / Tentativas
[AMIV] Gap(%) [AMIV]
No. Médio de
Gerações [AMIV]
br17 10 0,000 0,000 10 0,000 0,000 OK ftv33 5 2,636 2080,100 5 2,636 334,300 OK ftv35 1 1,174 3338,300 1 0,991 578,200 OK ftv38 0 1,190 3556,900 0 1,170 590,600 OK p43 0 0,130 3331,600 0 0,110 553,600 OK
ftv44 0 4,712 3172,500 0 3,769 535,800 OK ftv47 0 0,602 2979,100 0 0,552 507,500 OK
ry48p 0 1,734 2982,100 0 1,513 500,000 OK ft53 0 6,911 2708,500 0 5,725 460,200 OK
ftv55 0 2,674 2556,800 0 2,799 435,500 * ftv64 0 2,958 2172,500 0 2,855 376,100 OK ft70 0 1,464 1967,900 0 1,464 351,200 OK
ftv70 0 3,205 1949,400 0 3,226 341,600 * ftv90 0 2,223 1405,300 0 1,792 254,900 OK
ftv100 0 2,069 1209,100 0 1,678 222,400 OK ftv110 0 3,867 1231,000 0 1,982 225,300 OK ftv120 0 2,579 1061,300 0 2,620 201,200 *
kro124p 0 4,663 938,900 0 4,949 180,900 * ftv130 0 3,078 823,200 0 3,047 160,600 OK ftv140 0 2,169 729,300 0 2,140 142,300 OK ftv150 0 2,068 658,300 0 2,015 130,900 OK ftv160 0 0,596 587,600 0 0,335 115,500 OK ftv170 0 0,944 528,800 0 0,944 109,800 OK
rbg323 10 0,000 0,000 10 0,000 0,000 OK rbg358 10 0,000 0,000 10 0,000 0,000 OK rbg403 10 0,000 0,000 10 0,000 0,000 OK rbg443 10 0,000 0,000 10 0,000 0,000 OK Média 2,074 1,987 1554,389 2,074 1,789 270,681
62
Tabela 4. 3
Resultados da Implementação AMIV 3 x Algoritmo Memético Clássico
Instância
Ótimos / Tentativas
[AM] Gap(%) [AM]
No. Médio de
Gerações [AM]
Ótimos / Tentativas
[AMIV] Gap(%) [AMIV]
No. Médio de
Gerações [AMIV]
br17 10 0,000 0,000 10 0,000 0,000 OK ftv33 5 2,636 2080,100 5 2,659 44,000 * ftv35 1 1,174 3338,300 1 1,195 73,400 * ftv38 0 1,190 3556,900 0 1,131 72,400 OK p43 0 0,130 3331,600 0 0,125 64,700 OK
ftv44 0 4,712 3172,500 0 4,042 61,500 OK ftv47 0 0,602 2979,100 0 0,586 56,900 OK
ry48p 0 1,734 2982,100 0 1,618 56,500 OK ft53 0 6,911 2708,500 0 6,407 51,700 OK
ftv55 0 2,674 2556,800 0 2,761 46,500 * ftv64 0 2,958 2172,500 0 2,936 37,000 OK ft70 0 1,464 1967,900 0 1,464 33,400 OK
ftv70 0 3,205 1949,400 0 3,328 32,300 * ftv90 0 2,223 1405,300 0 1,792 22,800 OK
ftv100 0 2,069 1209,100 0 1,678 19,500 OK ftv110 0 3,867 1231,000 0 2,621 22,500 OK ftv120 0 2,579 1061,300 0 2,656 16,900 *
kro124p 0 4,663 938,900 0 4,861 14,800 * ftv130 0 3,078 823,200 0 3,017 13,000 OK ftv140 0 2,169 729,300 0 2,231 11,800 * ftv150 0 2,068 658,300 0 2,068 10,600 OK ftv160 0 0,596 587,600 0 0,335 9,900 OK ftv170 0 0,944 528,800 0 0,944 8,900 OK
rbg323 10 0,000 0,000 10 0,000 0,000 OK rbg358 10 0,000 0,000 10 0,000 0,000 OK rbg403 10 0,000 0,000 10 0,000 0,000 OK rbg443 10 0,000 0,000 10 0,000 0,000 OK Média 2,074 1,987 1554,389 2,074 1,869 28,926
63
Tabela 4. 4
Resultados da Implementação AMIV 4 X Algoritmo Memético Clássico
Instância
Ótimos / Tentativas
[AM] Gap(%) [AM]
No. Médio de
Gerações [AM]
Ótimos / Tentativas
[AMIV] Gap(%) [AMIV]
No. Médio de
Gerações [AMIV]
br17 10 0,000 0,000 10 0,000 0,000 OK ftv33 5 2,636 2080,100 5 2,636 140,300 OK ftv35 1 1,174 3338,300 1 1,195 260,200 * ftv38 0 1,190 3556,900 0 1,052 287,000 OK p43 0 0,130 3331,600 0 0,096 255,200 OK
ftv44 0 4,712 3172,500 0 4,042 246,100 OK ftv47 0 0,602 2979,100 0 0,586 289,800 OK
ry48p 0 1,734 2982,100 0 1,585 206,500 OK ft53 0 6,911 2708,500 0 5,915 247,500 OK
ftv55 0 2,674 2556,800 0 2,761 142,100 * ftv64 0 2,958 2172,500 0 2,887 183,200 OK ft70 0 1,464 1967,900 0 1,446 112,600 OK
ftv70 0 3,205 1949,400 0 3,246 129,600 * ftv90 0 2,223 1405,300 0 1,913 145,500 OK
ftv100 0 2,069 1209,100 0 1,678 137,300 OK ftv110 0 3,867 1231,000 0 2,411 83,600 OK ftv120 0 2,579 1061,300 0 5,042 91,400 *
kro124p 0 4,663 938,900 0 2,431 141,000 OK ftv130 0 3,078 823,200 0 3,078 50,900 OK ftv140 0 2,169 729,300 0 2,211 37,400 * ftv150 0 2,068 658,300 0 2,041 41,300 OK ftv160 0 0,596 587,600 0 0,440 43,500 OK ftv170 0 0,944 528,800 0 0,918 36,800 OK
rbg323 10 0,000 0,000 10 0,000 0,000 OK rbg358 10 0,000 0,000 10 0,000 0,000 OK rbg403 10 0,000 0,000 10 0,000 0,000 OK rbg443 10 0,000 0,000 10 0,000 0,000 OK Média 2,074 1,987 1554,389 2,074 1,837 122,548
Nas tabelas acima, temos para cada instância: o número de vezes que o ótimo foi
alcançado; o valor do GAP final obtido (média entre as 10 execuções); o número médio de
gerações (média entre as 10 execuções) para o Algoritmo Memético Clássico (AMC) e cada
um dos 4 procedimentos de Infecção Viral (AMIV) desenvolvidos.
As 4 tabelas mostram o melhor desempenho e rapidez do Algoritmo Memético com
Infecção Viral em relação ao Algoritmo Memético Clássico. Note-se que o número de
gerações, com o mesmo tempo computacional, do AMIV foi bem menor do que o do AMC.
O tempo de execução total para as quatro tabelas, usando 1 minuto foi de:
Tempo de execução total = 27(instâncias) x 10 x 1 x 4 = 1080 min = 18 horas.
64
Capítulo 5
Conclusões e Recomendações
Neste capítulo são apresentadas as conclusões dos experimentos realizados com os
dois algoritmos: Memético Clássico e Memético com Infecção Viral. Além disso, são feitas
algumas recomendações para futuras pesquisas.
5.1 - Conclusão
Os resultados obtidos mostraram a qualidade superior do Algoritmo Memético com
Infecção Viral em relação ao Algoritmo Memético Clássico, o que valida a utilização desta
Metaheurística Híbrida para resolução de Problemas de Otimização Combinatória NP-
dificeis.
Este trabalho também apresentou um aperfeiçoamento do processo de infecção viral,
pois agora, os vírus, não apenas modificam o material genético dos cromossomos, mas, com a
simbiose, eles também sofrem alterações no seu material genético.
5.2 - Recomendações para Futuras Pesquisas
Ao longo do desenvolvimento deste projeto, foram observadas algumas semelhanças
com a idéia do Vocabulary Building idealizada por Fred Glover no início da década de 90,
pois a metodologia da técnica é obter melhores soluções a partir de soluções parciais ou
vocábulos (GUEDES e ALOISE, 2006). A grande diferença é que no Vocabulary Building os
trechos podem concatenar-se até formarem uma rota completa, enquanto que na Infecção
Viral, o vírus necessita de um indivíduo (rota completa) para interagir, nunca formando uma
65
solução completa a partir da concatenação com outros vírus. Talvez o uso do Vocabulary
building na geração da população de vírus já forneça uma boa população, diminuindo com
isto o processo de diminuição e aumento do vírus.
Uma nova abordagem em evidência na Otimização Combinatória é a Matheuristics,
onde a exploração do modelo matemático do problema, pela Programação Matemática, em
algumas das etapas do algoritmo heurístico, consegue melhorar o desempenho deste. Em
(ALOISE e HANSEN, 2006), utilizou-se esta técnica para resolver o problema de dividir em
M classes, ou conjuntos, um dado conjunto de N pontos no espaço euclideano, a fim de que a
soma das distâncias de cada ponto ao centro de seu conjunto seja minimizada. Esta idéia
(Matheuristics), pode ser utilizada, por exemplo, durante o processo de transcrição viral, onde
o processo de busca realizado pelo vírus para encontrar uma melhor posição para infectar o
agente seja feito por vários vírus num mesmo instante, e não apenas por um, permitindo, em
alguns casos, que um agente sofra mais de uma infecção. Esta busca poderia utilizar-se de um
método exato.
66
Referências Bibliográficas
ALOISE, D.; HANSEN, P. Heuristic aspects of exact algorithms for minimum sum-of-
squares clustering. In: MATHEURISTICS 2006 1ST WORKSHOP ON MATHEMATICAL
CONTRIBUTIONS TO METAHEURISTICS. 27-30 August 2006. University of Bologna
Residential Center Bertinoro (Forlì - Cesena), Italy.
ALOISE, D. J.; BARROS, C. A.; NEVES, J. A. Um Algoritmo Genético para uma Variante
do Problema de Orientação. In: CONGRESO LATINO AMERICANO EN
INVESTIGACION DE OPERACIONES. 4-8 set 2000. Cidade do México, México.
ALOISE, Dario José et al. Um algoritmo grasp reativo aplicado ao problema da unidade
móvel de pistoneio (poe-ump). In: 33º SIMPÓSIO BRASILEIRO DE PESQUISA
OPERACIONAL. 2001. Campos do Jordão. São Paulo.
BAKER, J. E. An analysis of the the effects of selection in genetic algorithms. 1989. Tese
(PhD thesis) - Graduate Schol of Vanderbilt University. Nashiville, Tennessee.
BALAS, E. The prize collecting traveling salesman problem, networks 19, 1989. p. 621-636.
BALAS, E. The prize collecting traveling salesman problem: II. Polyhedral results, networks
25, 1995. p. 199-216.
BARR, R. S. et al. Guidelines for Designing and Reporting on Computational Experiments
with Heuristic Methods, 2001.
BEASLEY, D.; BULL, D.R.; MARTIN, R.R. An overview of genetic algorithms 2. Research
topics. University Computing 15 (4), 1993. p. 170-181.
BELMORE, M; NEMHAUSER, G. L. The Travelling Salesman Problem: A Survey.
Operations Research, v. 16, p. 538-558, 1988.
BENTLEY, J. J. Fast Algorithms for Geometric Traveling Salesman Problems. ORSA
Journal on Computing, v. 4. n. 4, 1992. p. 387-411.
BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria, modelos, algoritmos. São Paulo:
Edgard Blücher, 2006.
CAMPELLO, R. E.; MACULAN, N. Algoritmos e heurísticas: desenvolvimento e avaliação
de performance. Rio de Janeiro: EDUFF, 1994.
67
CARLOS, Luiz Amorim. Computação evolutiva. Mini-curso. In: ERMAC. 2002.
CERQUEIRA, F. R.; STELZER, R. B. P. Algoritmos genéticos aplicados a Mapeamento
físico de DNA. Revista Educação e Tecnologia, Ano 1, n. 1, Abr/Set. 2005.
CLARKE, G.; WRIGHT, J. W. Scheduling of Vehicles from a Central Depot to a Number of
Delivey Points. Operations Research, v. 12, 1963.p. 568-581.
COELHO, Leandro dos Santos. Fundamentos, Potencialidades e Aplicações de Algoritmos
Evolutivos: Notas em Matemática Aplicada 2. São Carlos, SP: SBMAC, 2003. 103 p.
COELHO, L. S., MARIANI, V. C. Concepção Híbrida de Otimização por Nuvem de
Partículas Aplicada ao Problema de Weber. Centro de Ciências Exatas e de Tecnologia,
Pontifícia Universidade Católica do Paraná. 2005.
DANTZIG, G. B.; FULKERSON, D. R.; JOHNSON, S. M. Solutions of a Large Scale
Travelling Salesman Problem. Operations Research, v. 12, 1954. p. 393-410.
DARWIN, Charles. On The Origin of Species, 1st edition, Harward University Press, MA,
1859.
DAVIS, L., Applying Adaptive Algorithms to Epistactic Domains. In: Proceedings of the Int.
Joint Conf. on Artificial Intelligence (IJCAI'85), Los Angeles, CA, 1985. p. 162-164.
EBERHART, R. C.; KENNEDY, J. A new optimizer using particle swarm theory. In:
Proceedings of the Sixth International Symposium on Micro Machine and Human Science,
Nagoya, Japan, p. 39-43. 1995.
FEO, T. A.; RESENDE, M. G. C. Greedy Randomized Adaptive Search Procedures. Journal
of Global Optimization, 6, 1989. p 109-133.
FUNKE, B.; GRÜNERT, T.; IRNICH, S. Local Search for Vehicle Routing and Scheduling
Problems: Review and Conceptual Integration. Journal of Heuristics, vol. 11, 2005. p. 267-
306.
GARCIA, V. J. et al. Algoritmo Memético Paralelo Aplicado a Problemas de
Seqüenciamento em Máquina Simples. Universidade Estadual de Campinas – UNICAMP.
Campinas, SP.
GAVISH, B.; GRAVES, S. C. The Travelling Salesman Problem and Related Problems,
Wording Paper GR-078-78, Massachusetts Institute of Technology - MIT, USA, Operations
Research Center, 1978.
68
GENDREAU, M., LAPORTE, G.; SEMET, F. A tabu search heuristic for the undirected
selective traveling salesman problem, Europen Journal of Operation Research, v 106, 1998. p.
539-545.
GLOVER, F. Future Paths for Integer Programming and Links to Artificial Intelligence.
Computers and Operations Research, v. 13, 1986. p. 533-549.
GLOVER, F.; LAGUNA, M. TABU SEARCH. Boston: Kluver academic Publishers. 1997.
GLOVER, F. et al. Construction Heuristics for the Asymmetric Tsp. European Journal of
Operational Research, 1999.
GOLDBERG, D. E.; LINGLE, R. Alleles, Loci and the Traveling Salesman Problem. In:
Proceedings of the First Int. Conf. on Genetic Algorithms (ICGA'85), Carnegie-Mellon
University, Pittsburgh, PA. 1985.p. 154-159.
GOLDBERG, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning.
Addison-Wesley. 1989.
GOLDBERG, D. E. A note on Boltzman tournament selection for genetic algorithms and
population oriented simulated annealing. Complex Systems, v. 4, p.445-460, 1990.
GOLDBERG, D. E.; DEB, K. A comparative analysis of selection schemes used in genetic
algorithms. In: RAWLINS, G. (Ed.), Foundations of Genetic Algorithms. San Francisco, CA:
Morgan Kaufmann, 1991.
GOLDEN, B. L.; ASSAD, A. A. Vehicle routing methods and studies. Amsterdam:
North-Holland, 1988.
GREFENSTETTE et al. Genetic Algorithms for the Traveling Salesman Problem. In:
Proceedings of the First Int. Conf. on Genetic Algorithms (ICGA'85), Carnegie-Mellon
University, Pittsburgh, PA, 1985. p. 160-168.
GUEDES, A. C. B. ; ALOISE, D. J. . Uma metaheurística baseada em construção de
vocábulos para o Problema do Caixeiro Viajante Assimétrico. In: IX Simpósio de Pesquisa
Operacional e Logística da Marinha, 2006, Rio de Janeiro. Anais, 2006.
GUEDES, A. C. B.; LEITE, J. N. F.; ALOISE, D. J. Um algoritmo genético com infecção
viral para o problema do caixeiro viajante. PublICa 1, 2005. p.16 – 24.
HOLLAND, J.H. Adaptation in natural and artificial systems . Michigan: MIT Press, 1975.
69
KANOH, H. et al. Solving Constraint Satisfaction Problems by a Genetic Adopting Viral
Infection. In: IEEE. 1996.
KANOH, H.; NAKAMURA, N. Route Guidance with Unspecified Staging Posts Using
Genetic Algorithm for Car Navigation Systems. In IEEE Intelligent Transportation Systems.
Dearbom (MI), USA. 2000.
KANOH, H., KONDO, M.; SUGIMOTO, M. Solving Timetabling Problems Using Genetic
Algorithms Based on Minimizing Conflict Heuristics. In: CIMNE, Barcelona, 2002.
KELLER, C. P. Multiobjective routing through space and time: the MVP and TDVP
problems. 1985. Tese (Ph.D. Thesis) - University of Western Ontario.
KENNEDY, J.; EBERHART, R. C. Particle swarm optimization. In: Proceedings of the IEEE
International Conference on Neural Networks IV, Perth, Australia, 1995. p. 1942-1948.
LAPORTE, G.; MARTELLO, S. The selective traveling salesman problem. Discrete Applied
Mathematics 26, 1990. p. 193-207.
LAPORTE, G. The Traveling Salesman Problem: An Overview of Exact and Approximate
Algorithms. European Journal of Operational Research 59 (2), 1992. p. 231-247.
LARTIGUE, J. W. Viral Infection: An Alternative Method for Solving the Knapsack Problem
Through Evolutionary Programming. Auburn University.
LAURINDO, Fernando José Barbin. Tecnologia da Informação como Suporte às Estratégias
Empresariais. Depto de Engenharia de Produção da EPUSP
LAWLER, E. L. et al. The Traveling Salesman Problem. John Wiley & Sons, Chichester.
1985
LIN, S.; KERNIGHAN, B. W. An Effective Heuristic Algorithm for the Traveling Salesman
Problem. Oper. Res, n. 21, 1973. p. 498-516.
MACIEL, A. C. M., MARTINHON, C. A.; OCHI, L. S. Heurísticas e Metaheurísticas para o
Problema do Caixeiro Viajante Branco e Preto. In: XXXVII SBPO, 2005, Gramado/RS
MENDES, A. S. Algoritmos Meméticos Aplicados aos Problemas de Sequenciamento em
Máquinas. 1999. Dissertação (Mestrado) - Faculdade de Engenharia Elétrica e de
Computação, Universidade Estadual de Campinas – UNICAMP. p 91. Campinas, SP.
MICHALEWICZ Z. Genetic algorithms + data structures = evolution programs. Berlin:
Springer Verlag, 1996. p. 387.
70
MICHALEWICZ Z.; FOGEL D. B. How to solve it: modern heuristics. Berlin: Springer
Verlag, 2000. 467p.
MLADENOVIC, N.; HANSEN, P. Variable neighborhood search. Computers Oper. Res. 24,
1997. p. 1097–1100.
MOSCATO, P. On Evolution, Search, Optimization, Genetic Algorithms, and Martial Arts:
Towards Memetic Algorithms. Technical Report, Caltech Concurrent Computation Program,
C3P Report 826. 1989.
MOSCATO, P. Memetic Algorithms: A Short Introduction. 1999. In: D. Corne, M. Dorigo e
F. Glover (eds.), New Ideas in Optimization. Washington: McGraw-Hill.
NEVES, Josemir Araújo. Uma aplicação de algoritmo genético na otimização do emprego da
unidade móvel de pistoneio. 2000. 94p. Dissertação (Mestrado em Sistemas e Computação) –
Universidade Federal do Rio Grande do Norte, Rio Grande do Norte.
NORBACK, J. P., LOVE, R.F. Heuristic for the Hamiltonian Path Problem in Euclidean Two
Space. J. Oper. Res. Soc. n. 30, 1979. p. 363-368.
NORONHA, T. F.; ALOISE, D. J.; SILVA, M. M. Uma Abordagem sobre Estratégias
Metaheurísticas. REIC. Revista eletrônica de iniciação científica, http://www.sbc.org.br/reic,
v. 1, 2001.
OLIVER, I. M.; SMITH, D.J.; HOLLAND, J.R.C. A Study of Permutation Crossover
Operators on the Traveling Salesman Problem. In: Proceedings of the Second Int. Conf. on
Genetic Algorithms (ICGA'87), Massachusetts Institute of Technology, Cambridge, MA,
1987. p. 224-230.
POTVIN, Jean-Yves. Genetic Algorithms for the Traveling Salesman Problem. Centre de
Recherche sur les Transports - Université de Montreal. Montréal – Québec - Canadá. 1996.
PRÜGEL-BENNETT, A.; SHAPIRO, J. L. An analysis of genetic algorithms using statistical
mechanics, Physical Review Letters 72, n. 9, p. 1305-1309, 1994.
RABAK, C. S.; SICHMAN J. S. Otimização do Processo de Inserção Automática de
Componentes Eletrônicos Empregando a Técnica de Times Assíncronos, Pesquisa
Operacional v. 21, n. 1, p. 39-59, 2001.
RAMESH R.; YOON, Y.S.; KARWAN, M.H. An Optimal Algoritm for the orienteering Tour
Problem. (ORSA) Journal on Computing, v. 4, n. 2. 1992. p 155-165.
71
RENAUD, J.; BOCTOR, F. F. An efficient composite heuristic for the symmetric generalized
traveling salesman problem. European Journal of Operations Research. v. 108. 1998. p. 571-
584.
RIBEIRO, C.C. Metaheurísticas. 2002. Curso XI Escola Brasileira de Computação - versão
original - 1998. Disponível em: <http://www-di.inf.puc-
rio.br/~celso/grupo/metaheuristicasPUC-ebc98.ppt>. Acesso em : 15 dez. 2005.
RIBEIRO, C.C. Introdução aos Modelos e Métodos de Otimização em Pesquisa Operacional:
Parte III – Heurísticas. Operador Nacional do Sistema Elétrico, 2004. Disponível em:
<http://www-di.inf.puc-rio.br/~celso/grupo/OtimizacaoONS-parte3.pdf>. Acesso em: 10 fev.
2006.
RIBEIRO FILHO, G. Melhoramentos No Algoritmo Genético Construtivo e Novas
Aplicações em Problemas de Agrupamento. 2001. Tese (Doutorado em Computação
Aplicada). Instituto Nacional de Pesquisas Espaciais - INPE, São José dos Campos. p. 129.
ROSENKRANTZ, D. J., STEARNS, R. E.; LEWIS, P. M. An Analysis of Several Heuristics
for the Travelling Salesman Problem. Siam J. Comput., v. 6, 1977. p. 563-581.
SILVA, E. L.; MENEZES, E. M. Metodologia da pesquisa e elaboração de dissertação.
Florianópolis, 2001
SLACK, N.; CHAMBERS, S.; JOHNSTON, R. Planejamento e Controle Just in Time. In:
___. Administração da Produção. 2ª Edição. São Paulo: Atlas, 2002. cap. 15, p.481-510.
STALK, George Jr. Tempo: A Próxima Fonte de Vantagem Competitiva. In: Montgomery,
C.A. & Porter, M.E. Estratégia - A Busca da Vantagem Competitiva. Rio de Janeiro: Campus,
1998. p. 336.
VALENTIM, M. A. X. Uma Metaheurística Genética Não-Convencional para uma
Generalização do Problema do Caixeiro Viajante. 1998. Dissertação (Mestrado) -
Departamento de Ciência da Computação, Instituto de Matemática. UFF.
VERGARA, S. C. Projetos e relatórios de pesquisa em administração. São Paulo: Atlas,
2000.
WAIZBORT, R. Dos Genes Aos Memes: A Emergência do Replicador Cultural. Episteme,
Porto Alegre, n. 16, jan./jun. 2003. p. 23-44.
72
WHITLEY, D.; STARKWEATHER, T.; FUQUAY, D. Scheduling Problems and Traveling
Salesmen: The Genetic Edge Recombination Operator. In: Proceedings of the Third Int. Conf.
on Genetic Algorithms (ICGA'89), George Mason University, Fairfax, VA. 1989. p. 133-140.
