Algoritmo Memético para o Problema do Caixeiro Viajante

Prévia do material em texto

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/2006Dissertation 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-MeioAtividades-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 destapesquisa, 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 deencontrar 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
,
−≤≤⊆−≤∑
∈
nSVSSx
Svv
ij
ji
)1.3(∑
≠
=
ji
ijij xczMinimizar
)2.3(),...,1(1:
1
nixàSujeito
n
j
ij ==∑
=
)5.3();,...,1,(}1,0{ jinjixij ≠=∈
∑
=
==
n
i
ij 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
ij
j
n
ij
j
jiij niyy
1 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 maispró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ííciocio
N
1
N
2
N
3
 
 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. 
Noalgoritmo, é 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