ads:
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE - UFRN
CENTRO DE CIÊNCIAS EXATAS E DA TERRA - CCET
DEPARTAMENTO DE INFORMÁTICA E MATEMÁTICA APLICADA - DIMAp
PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO - PPgSC
DISSERTAÇÃO DE MESTRADO
ALGORITMO MEMÉTICO E VOCABULARY BUILDING: UMA APLICAÇÃO AO
PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
por
Jéssica Neiva de Figueiredo Leite
Natal - RN
Fevereiro/2006
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
II
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE - UFRN
CENTRO DE CIÊNCIAS EXATAS E DA TERRA - CCET
DEPARTAMENTO DE INFORMÁTICA E MATEMÁTICA APLICADA - DIMAp
PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO - PPgSC
ALGORITMO MEMÉTICO COM VOCABULARY BUILDING: UMA APLICAÇÃO AO
PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
Dissertação apresentada ao programa
de Pós-Graduação em Sistemas e
Computação da Universidade Federal
do Rio Grande do Norte como requisito
para obtenção do grau de Mestre em
Sistemas e Computação
Orientador: Prof. Dr. Dario José Aloise
Natal/RN
Fevereiro/2006
ads:
III
Dissertação de mestrado sob o título Algoritmo Memético e Vocabulary Building
aplicado ao Problema do Caixeiro Viajante Assimétrico, defendida por Jéssica Neiva
de Figueiredo Leite e aprovada em 20 de Fevereiro de 2006, em Natal-RN, pela
banca examinadora constituída pelos seguintes doutores:
_____________________________________
Prof. Dr. Dario José Aloise
Orientador – DIMAp /UFRN
_____________________________________
Prof. Dr. Marcos Negreiros
Examinador – UECE/CE
_____________________________________
Prof. PHD André Mauricio Cunha Campos
Examinador – DIMAp/UFRN
IV
Este trabalho é dedicado aos meus
pais Ana Maria e Francisco,
meus irmãos e ao meu noivo.
V
AGRADECIMENTOS
Quero primeiro agradecer a Deus por ter me dado tantas oportunidades de terminar
este curso. Por ter me dado força nas horas certas e por não ter me deixado
fraquejar. OBRIGADA!
Merece também enormes agradecimentos a minha família, em particular os meus
pais Ana Maria e Francisco das Chagas Figueiredo, que além de ter financiado este
sonho, que não era só meu e sim nosso, e por ter, apesar de tudo confiado desde o
início.
Ao meu noivo Jadson Araújo Costa, que sempre me deixava chateada por sempre
dizer as coisas certas, por sempre acreditar, por sempre me ajudar, por sempre ter
paciência, por sempre esperar e por sempre me confortar. Pelas viagens, pelas
horas de espera no laboratório e pelas ausências.
Ao meu grande orientador, que soube entender as minhas fraquezas e que apesar
de tudo não desistiu de mim. DARIO MUITO OBRIGADA!!!!
Ao meu novo e grande amigo, Alisson Costa que muito ajudou a realizar este
trabalho, nas muitas horas de laboratório, na troca de idéias e por ter estar
disponível sempre que precisei.
Aos meus amigos e colegas Marilyn e Heitor, que tornaram desde o início esta tarefa
menos árdua, que me fizeram sentir um pouco em casa morando em uma cidade
que quase não conhecia. Vocês me deram a tranqüilidade pra começar tudo isso.
E por último, mas não menos importante, gostaria de agradecer a todas aquelas
pessoas que fizeram parte da minha vida na UFRN e que de alguma forma
contribuíram para a realização deste sonho.
VI
Todas as coisas são relativas, depende de onde e
quando elas acontecem.
(Albert Einstein)
VII
RESUMO
O Problema do Caixeiro Viajante Assimétrico (PCVA) é um problema clássico de
Otimização Combinatória classificado como NP – Difícil. O mesmo tem sido
amplamente utilizado em novos estudos desta área, tornado se um benchmark. Sua
utilização neste trabalho se dá principalmente por este motivo.
Os Algoritmos Meméticos podem ser considerados como sendo uma evolução dos
Algoritmos Genéticos, pois introduz aos Algoritmos Genéticos um mecanismo de
busca local tendo sido empregado de forma bastante satisfatória em diversos outros
problemas.
Há algum tempo o pesquisador Fred Glover publicou uma estratégia denominada de
Vocabulary Building na Metaheurística Busca Tabu (Tabu Search). Apesar desta
técnica não ter atraído muito a atenção de outros pesquisadores, percebeu-se que
ela poderia ser introduzida em outros métodos populacionais como os Algoritmos
Genéticos e Meméticos. Este trabalho tem como objetivo utilizar esta estratégia nos
Algoritmos Meméticos, o que ainda não foi realizado, aplicando-a ao PCVA. O VB foi
implementado de duas formas diferente, por contração de vértices e por pool de
vocábulos.
Foram realizadas implementações do Vocabulary Building, do Algoritmo Memético
Clássico e do Algoritmo Memético com Vocabulary Building nas duas formas
diferentes utilizando as 27 instâncias assimétricas da TSPLIB. Os resultados
mostraram a eficiência dessa técnica, que atingiu no melhor caso, 0,066% em
relação ao ótimo de melhoria nas instâncias utilizadas nos testes. Assim, os
resultados comprovam que esta técnica pode ser implementada de forma
competitiva para resolução de outros problemas de otimização NP – difícil, assim
como pode ser introduzida em outras técnicas populacionais e evolucionárias.
Palavras-chave: Algoritmo Memético, Vocabulary Building, Problema do Caixeiro
Viajante Assimétrico.
VIII
ABSTRACT
The Asymmetric Travelling Salesman Problem (ATSP) is a classic problem of
Combinatorial Optimization, classified as NP - Hard. The same has been widely
used in new studies of this area, becoming one “benchmark”. Its use in this work if
gives mainly for this reason.
The Memetics Algorithms can be considered as being an evolution of the Genetic
Algorithms, therefore it introduces to the Genetic Algorithms a local mechanism of
search having been used of sufficiently satisfactory form in diverse other problems.
The researcher Fred Glover has some time published a strategy called of Vocabulary
Building in the Metaheurística Tabu Search. Despite this technique not to have very
attracted the attention of other researchers, perceived that it could be introduced in
other population methods as the Algorithms Genetics and Memetics. This work has
as objective to use this strategy in the Meméticos Algorithms, what it was still not
carried through, applying it the ATSP. The VB was implemented of two different
forms, for contraction of vertices and pool of vocables.
Implementations of the Vocabulary Building, the Classic Memetic Algorithm and the
Memetic Algorithm with Vocabulary Building in the two different forms using the 27
asymmetrical instances of the TSPLIB. The results had shown to the efficiency of
this technique that reached in the best case 0.066% in relation to the excellent one of
improvement in the instances used in the tests. Thus, the results prove that this
technique can be implemented of competitive form for resolution of other problems of
optimization NP – Hard, as well as can be introduced in others population and
evolutionary techniques.
Key-Words: Memetic Algorithms, Vocabulary Building, Asymmetric Travelling
Salesman Problems.
IX
Sumário
SUMÁRIO ...........................................................................................................................................IX
LISTA DE FIGURAS ......................................................................................................................... 11
LISTA DE TABELAS......................................................................................................................... 12
LISTA DE ABREVIATURAS OU SIGLAS..................................................................................... 13
INTRODUÇÃO................................................................................................................................... 15
1.1 MOTIVAÇÃO................................................................................................................................ 15
1.2 ORGANIZAÇÃO DA DISSERTAÇÃO ............................................................................................. 17
O PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO..................................................... 19
2.1 DEFINIÇÃO...................................................................................................................................... 19
2.2. COMPLEXIDADE COMPUTACIONAL.............................................................................................. 20
2.3 FORMULAÇÃO MATEMÁTICA DO PCV ......................................................................................... 21
2.4 MÉTODOS DE RESOLUÇÃO............................................................................................................. 22
2.4.1 MÉTODOS EXATOS........................................................................................................................ 22
2.4.2 MÉTODOS HEURÍSTICOS............................................................................................................... 23
2.4.2.1 METAHEURÍSTICAS.................................................................................................................... 24
2.4.3.1 Algoritmos Genéticos e Meméticos.................................................................................... 25
2.4.3.2 Scatter Search ....................................................................................................................... 29
2.4.3.3 Otimização por Colônia de Formigas................................................................................. 32
VOCABULARY BUILDING............................................................................................................. 34
3.1 INTRODUÇÃO.................................................................................................................................. 34
3.2 DEFINIÇÃO ...................................................................................................................................... 35
3.3 FORMAS DE VOCABULARY BUILDING UTILIZADAS ....................................................................... 38
3.3.1 POOL DE VOCÁBULOS ................................................................................................................... 38
3.3.1.1 Mecanismo de inserção do vocábulo em um indivíduo .................................................. 39
3.3.1.2 Mecanismo de combinação dos vocábulos ...................................................................... 41
3.3.1.3 Mecanismo de fragmentação do vocábulo ....................................................................... 42
3.3.1.4 Evolução do pool de vocábulos....................................................................................... 44
3.3.2 CONTRAÇÃO DE VÉRTICES ........................................................................................................... 45
3.4 HEURÍSTICA VOCABULARY BUILDING ......................................................................................... 48
CAPÍTULO 4 ........................................................................................................................................... 49
X
ALGORITMO MEMÉTICO APLICADO AO PROBLEMA DO CAIXEIRO VIAJANTE
ASSIMÉTRICO .................................................................................................................................. 49
4.1DEFINIÇÃO....................................................................................................................................... 49
4.2 APLICANDO O ALGORITMO MEMÉTICO AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO
............................................................................................................................................................... 51
3.2.1 POPULAÇÃO INICIAL E REPRESENTAÇÃO DOS INDIVÍDUOS .......................................................... 51
4.2.2 SELEÇÃO DOS MELHORES AGENTES ............................................................................................. 52
4.2.3 OPERADORES DE RECOMBINAÇÃO................................................................................................ 53
4.2.3.1 Strategic Arc Crossover (SAX)............................................................................................ 53
4.2.3.2 Crossover de dois pontos (Two Points Crossover) ......................................................... 53
4.2.4 MECANISMO DE BUSCA LOCAL..................................................................................................... 54
ALGORITMO MEMÉTICO E VOCABULARY BUILDING....................................................... 55
5.1 INTRODUÇÃO.................................................................................................................................. 55
5.2 O POOL DE VOCÁBULOS NO ALGORITMO MEMÉTICO ................................................................. 55
5.3 VOCABULARY BUILDING USANDO CONTRAÇÃO DE VÉRTICES NO ALGORITMO MEMÉTICO ..... 57
5.4 VOCABULARY BUILDING USANDO CONTRAÇÃO DE VÉRTICES E POOL DE VOCÁBULOS NO
ALGORITMO MEMÉTICO..................................................................................................................... 58
RESULTADOS COMPUTACIONAIS............................................................................................. 60
CONCLUSÃO, PRINCIPAIS CONTRIBUIÇÕES E TRABALHOS FUTUROS ....................... 65
7.1 CONCLUSÃO.................................................................................................................................... 65
7.2 PRINCIPAIS CONTRIBUIÇÕES ........................................................................................................ 66
7.3 TRABALHOS FUTUROS ................................................................................................................... 66
11
Lista de Figuras
FIGURA 1. REPRESENTAÇÃO DO PROBLEMA DO CAIXEIRO VIAJANTE SIMÉTRICO E
ASSIMÉTRICO, RESPECTIVAMENTE................................................................................................. 20
FIGURA 2. RESOLUÇÃO DO TSP PROPOSTO POR GEORGE DANTZIG, RAY FULKENSON E
SELMER JOHNSON. ...............................................................................................................................20
FIGURA 3. ESTRUTURA BÁSICA DE UM AG SIMPLES. ............................................................................27
FIGURA 4. CONJUNTO REFERÊNCIA BI-DIMENSIONAL........................................................................30
FIGURA 5. GENERALIZAÇÃO DA OTIMIZAÇÃO POR COLÔNIA DE FORMIGA. ................................33
FIGURA 6. POSSÍVEL REPRESENTAÇÃO DO CONJUNTO ELITE E DO POOL DE VOCÁBULOS 37
FIGURA 7. PROCESSO DE VOCABULARY BUILDING................................................................................ 38
FIGURA 8. PROCESSO DE INSERÇÃO DE UM VOCÁBULO EM UM INDIVÍDUO. .............................40
FIGURA 9. ILUSTRAÇÃO DO PROCESSO DE CONCATENAÇÃO......................................................... 42
FIGURA 10. PROCESSO DE FRAGMENTAÇÃO DO VOCÁBULO .........................................................44
FIGURA 11.IDENTIFICAÇÃO E NORMALIZAÇÃO DAS ARESTAS COMUNS ÀS SOLUÇÕES
MOSTRADAS.............................................................................................................................................46
FIGURA 12. SOLUÇÕES CONTENDO TRECHOS CONTRAÍDOS (ELIPSES MAIORES). ......................... 47
FIGURA 13. ATRAVÉS DE DOIS PONTOS CONSIDERADOS ÓTIMOS LOCAIS X E Y, POR
EXEMPLO, PODE-SE OBTER UM DESCENDENTE Z´, QUE ATRAVÉS DA BUSCA LOCAL
PODE CHEGAR A SER UM ÓTIMO LOCAL. ......................................................................................49
FIGURA 14. ESTRUTURA BÁSICA DE UM ALGORITMO MEMÉTICO...................................................50
FIGURA 15. REPRESENTAÇÃO DE UMA POSSÍVEL SOLUÇÃO PARA O PCV. ................................ 52
FIGURA 16. ESTRUTURA DO ALGORITMO MEMÉTICO COM VB UTILIZANDO POOL DE
VOCÁBULOS. ............................................................................................................................................ 56
FIGURA 17. ALGORITMO MEMÉTICO COM VB USANDO CONTRAÇÃO DE VÉRTICES.....................57
FIGURA 18. ALGORITMO MEMÉTICO COM VB USANDO CONTRAÇÃO DE VÉRTICES E POOL DE
VOCÁBULOS. ............................................................................................................................................ 59
12
Lista de Tabelas
TABELA 1. TEMPO PARA CALCULAR A MELHOR ROTA EM FUNÇÃO DE N CIDADES. ................ 21
TABELA 2. RESULTADOS OBTIDOS COM A IMPLEMENTAÇÃO DO VOCABULARY BUILDING.........61
TABELA 3. RESULTADOS OBTIDOS COM A IMPLEMENTAÇÃO DO ALGORITMO MEMÉTICO
CLÁSSICO. .................................................................................................................................................62
TABELA 4. RESULTADOS OBTIDOS COM A IMPLEMENTAÇÃO DO ALGORITMO MEMÉTICO COM
VOCABULARY BUILDING POR CONTRAÇÃO DE VÉRTICES.........................................................63
TABELA 5. RESULTADOS OBTIDOS COM A IMPLEMENTAÇÃO DO ALGORITMO MEMÉTICO COM
VOCABULARY BUILDING POR POOL DE VOCÁBULOS.................................................................. 64
13
Lista de Abreviaturas ou Siglas
ACO – Ant Colony Optimization
AG(s) – Algoritmo(s) Genético(s)
AM(s) – Algoritmo(s) Memético(s)
ATSP – Asymmetric Travelling Salesman Problem
ES – Estratégia Evolucionária
GA(s) – Genetic(s) Algorithm(s)
GRASP - Greedy Randomized Adaptive Procedure
MA(s) – Memetic(s) Algorithm(s)
Max – Maximização
Min – Minimização
NN – Nearest Neighbor
NP – Nondeterministic Polynomial Time
PCV – Problema do Caixeiro Viajante;
PCVA – Problema do Caixeiro Viajante Assimétrico
PR - Path Relinking
SAX – Strategic Arc Crossover
SEX – Strategic Edge Crossover
14
SJ - Simulated Jumping
SS – Scatter Search
TSP – Travelling salesman problem
VB – Vocabulary Building
15
Capítulo 1
Introdução
1.1 Motivação
Existem diversos problemas no mundo real que são de difícil solução. Estes
problemas são complexos principalmente pelo fato de que sua solução pode levar
muito tempo para que seja conhecida, mesmo sendo tratada computacionalmente.
Outro aspecto importante é a dificuldade de formalizar estes problemas na forma
computacional. Os problemas do mundo real são também, geralmente cobertos por
muitas restrições o que dificulta ainda mais a sua resolução.
Através da observação da natureza foram desenvolvidas algumas classes de
técnicas de computação, sendo uma delas conhecida como Computação
Evolucionária. Esta é uma área que abrange métodos computacionais inspirados na
Teoria da Evolução das Espécies e na Genética, essencialmente no conceito de
seleção natural. São algoritmos probabilísticos que fornecem um mecanismo de
busca de soluções baseados no principio da sobrevivência dos mais aptos. Nos
sistemas inspirados por este paradigma as instâncias ou possíveis soluções dos
problemas são representadas sob a forma de indivíduos em uma população, que
evoluem de acordo com regras predeterminadas de seleção e por alguns
operadores genéticos. Estes métodos têm se mostrado ao longo do tempo,
eficientes na resolução de problemas de otimização em diversas áreas. A primeira
abordagem deste tipo de procedimento, baseado na evolução
foi no início da década
de setenta para encontrar soluções aproximadas de uma classe de problemas NP-
Difícil (ver Rechenberg e Schwefel, em [38,41]), denominada de Estratégia
Evolucionária (ES).
Existem na literatura, três conjuntos principais de método de busca de soluções: os
Determinísticos, os Enumerativos e os Estocásticos. Os métodos determinísticos são
baseados no cálculo de derivadas ou em aproximações destas. Necessitam,
portanto, de alguma informação do vetor gradiente, seja procurando o ponto onde
16
ele se anula ou usando a direção para a qual aponta. Os métodos enumerativos
fazem uma varredura completa (busca exaustiva) de todas as possíveis soluções,
mas isto implica em um tempo excessivo de cálculo na maior parte dos problemas.
Enquanto que os métodos estocásticos utilizam um conjunto de ações que buscam o
ótimo de maneira aleatória, mas de forma orientada sem necessitar de qualquer
informação de derivadas ou sobre o comportamento do problema [2].
Estratégias estocásticas são de simples implementação e entendimento. Por
trabalharem com regras de probabilidade, têm menos chances de convergirem para
mínimos locais se comparadas com os métodos determinísticos.
As Estratégias Evolucionárias se destacam entre as técnicas estocásticas mais
conhecidas. Dentre estas técnicas têm se destacado aquelas baseadas em
população, como os Algoritmos Genéticos (AG´s). Desenvolvido por Holland em
meados da década de 60 e apresentados no livro Adaptation in Natural and Artificial
Systems [27].
Os AG’s são métodos de busca baseadas nas Teorias da Evolução citadas
anteriormente, nos quais as variáveis são representadas como genes em um
cromossomo (indivíduo). Combinam a sobrevivência dos mais aptos com a troca de
informação de uma forma estruturada, mas aleatória. O AG apresenta um grupo de
soluções candidatas (População) na região de soluções. Por seleção natural e pelos
operadores genéticos como mutação e cruzamento, os cromossomos com melhor
aptidão são encontrados. A seleção natural garante que os cromossomos mais
aptos gerem descendentes nas populações futuras. Usando um operador de
cruzamento, o AG combina genes de dois cromossomos pais (genitores)
previamente selecionados para formar dois novos cromossomos, os quais têm uma
grande possibilidade de serem mais aptos que os seus genitores.
Desde o aparecimento de seus fundamentos teóricos os AG´s têm experimentado
uma enorme evolução. Uma de suas formas bastante utilizada são os AG´s Híbridos
que utilizam operadores de busca local para fazer com que indivíduos de uma
população evoluam autonomamente para ótimos locais. Uma generalização desta
idéia foi apresentada por Moscato [34] através da criação do termo Algoritmo
17
Memético (AM) onde é previsto que indivíduos possam evoluir autonomamente
acrescentando unidades de informação culturais chamadas memes.
Trabalhos recentes têm mostrado que esta técnica está ganhando espaço entre os
métodos com melhor desempenho quando aplicados a problemas de otimização
combinatória. Uma quantidade considerável de operadores de recombinação, busca
local, mutação, etc., têm sido propostos. Alguns para problemas específicos, outros
para uso geral.
Em 1993, Fred Glover em [12] introduziu um conceito conhecido como Vocabulary
Building (VB) na já conhecida técnica Tabu Search (Busca Tabu). A idéia por trás
desta técnica é que uma boa solução seja quebrada em várias partes e que estas
partes possam ser reconstruídas através de alguns métodos, como por exemplo, o
método construtivo, e se transformem em fortes soluções para determinado
problema.
Baseado nisto, este trabalho tem como objetivo introduzir o Vocabulary Building
(implementado de duas formas diferentes ) nos Algoritmos Meméticos, já que nunca
foi feito antes, e testar a sua viabilidade na resolução de problemas NP - difícil,
utilizando como parâmetro o Problema do Caixeiro Viajante Assimétrico (PCVA), já
que o mesmo é considerado um problema desta classe e normalmente é utilizado
como benchmark na introdução de novas técnicas.
1.2 Organização da Dissertação
O restante desta dissertação está organizado da seguinte forma:
Capítulo 2: é dedicado ao Problema do Caixeiro Viajante Assimétrico (Asymmetric
Traveling salesman Problem – ATSP), e tem como objetivo principal conceituar e
apresentar os conceitos mais importantes, visto que estes serão utilizados durante
toda a dissertação. Este problema é tomado como referência para o estudo
documentado neste trabalho. Assim, neste capítulo, o problema é conceituado, sua
18
importância explicitada, e seus aspectos principais como complexidade, formulação
matemática e alguns de seus métodos tradicionais de resolução são apresentados.
Capítulo 3: tem por objetivo principal mostrar uma estratégia conhecida como
Vocabulary Building (VB), um dos principais objetivos deste trabalho. Estratégia esta
advinda do Scatter Search (SS) e Path Relinking (PR) que devido à sua natureza
percebeu-se que pode satisfatoriamente ser aplicada a algoritmos populacionais,
como é o caso do Algoritmo Genético e Memético. Este Capítulo começa com uma
revisão bibliografia sobre o assunto, que segundo o autor desta técnica, Fred Glover,
não tem sido lembrada ultimamente pelos pesquisadores da área de otimização
combinatória. Discute seus principais conceitos, seus paradigmas, sua
implementação e sua estrutura.
Capítulo 4: apresenta o Algoritmo Memético aplicado ao Problema do Caixeiro
Viajante Assimétrico, a forma como foi implementado neste trabalho, suas
particularidades e a forma como foi implementado neste trabalho.
Capítulo 5: é feita uma apresentação das características da aplicação do
Vocabulary Building no Algoritmo Memético e sua exemplificação no Problema do
Caixeiro Viajante Assimétrico, principal objetivo deste trabalho. Mostrar como a
mesma pode ser estendida para outros algoritmos populacionais.
Capítulo 6: mostra os resultados dos testes computacionais realizados no
Vocabulary Building, no Algoritmo Memético clássico e no Algoritmo Memético com
VB nas duas formas, utilizando as 27 instâncias do Problema do Caixeiro Viajante
Assimétrico, escolhidos da biblioteca TSPLIB.
Capítulo 7: é dedicado às conclusões deste trabalho, a principal contribuição, bem
como sugestões para pesquisas futuras.
19
Capítulo 2
O problema do Caixeiro Viajante
Assimétrico
2.1 Definição
O Problema do Caixeiro Viajante – PCV (do inglês Travelling Salesman Problem -
TSP) começou a ser estudado por volta de 1800, e tem desde então se consolidado
como um problema clássico de referência na análise de performance de heurísticas
na área de otimização combinatória. Tem atraído também a atenção de
pesquisadores de diversas outras áreas do conhecimento, pelo fato de inúmeros
problemas reais serem modelados como problemas do tipo caixeiro viajante ou suas
variantes.
O problema, na sua forma clássica, consiste em: dado um conjunto de cidades (e
um custo associado à viagem entre uma cidade e outra), encontrar uma rota de
distância mínima para o caixeiro viajante de forma que, partindo de uma cidade
passe por todas as demais somente uma vez e retorne à cidade de origem.
Formalmente, o PCV pode ser definido como: seja G = (V, A) um grafo um grafo
completo, onde V é um conjunto de n vértices e A é o conjunto de arcos ou arestas
que conectam cada par de cidades i e j ∈ V. A cada arco/aresta está associado um
custo c
ij
. O TSP consiste em encontrar a rota de menor custo, passando por cada
vértice uma única vez. No caso simétrico c
ij
= c
ji
para toda cidade i, j ∈ V, enquanto
que o caso assimétrico possui pelo menos um caso em que c
ij
≠ c
ji
(ver figura 1).
Problemas assimétricos são, em geral, mais difíceis de serem resolvidos do que os
simétricos.
20
Figura 1. Representação do problema do caixeiro viajante simétrico e assimétrico,
respectivamente.
Embora a definição do problema seja normalmente referenciada como sendo um
problema de minimização, o problema também pode ser encontrado na sua forma
de maximização.
A figura abaixo mostra uma das primeiras propostas de resolução de uma instância
do problema em 1954 por George Dantzig, Ray Fulkerson, e Selmer Johnson em
[11].
Figura 2. Resolução do TSP proposto por George Dantzig, Ray Fulkenson e Selmer Johnson.
2.2. Complexidade computacional
O modo mais direto de encontrar a solução para este problema seria testar todas as
permutações (combinações) possíveis e encontrar entre elas a mais curta.
E
A
B
D
C
3
2
4
2
1
4
5
1
2
E
A
B
D
C
E
A
B
D
C
3
2
4
2
1
4
5
1
2
5
E
A
B
D
C
3
2
4
2
1
4
5
1
2
5
E
A
B
D
C
3
2
4
2
1
4
5
1
2
21
Infelizmente, dado que o número de permutações é n! (fatorial, onde n é o número
de cidades) este método rapidamente se torna impraticável.
Sob a ótica da otimização este problema é classificado como sendo um problema de
decisão NP - Árduo [27], o que significa que este possui ordem de complexidade
exponencial. Em outras palavras, o esforço computacional para a sua resolução
cresce exponencialmente com o tamanho do problema (determinado pelo número de
pontos a serem visitados).
A tabela 1 exemplifica o esforço computacional ao se enumerar todas as soluções
possíveis e depois escolher a melhor delas, em um computador com capacidade de
processamento de 1 bilhão de adições por segundo.
n Rotas por segundo (n-1)! Tempo de resposta
5 250 milhões 24 insignificante
10 110 milhões 362 880 0,003 s
15 71 milhões 87 bilhões 20 min
20 53 milhões 1,2x10
17
73 anos
25 42 milhões 6,2x10
23
87 milhões de anos
Tabela 1. Tempo para calcular a melhor rota em função de n cidades.
2.3 Formulação matemática do PCV
A formulação matemática é a mesma para ambos os casos, apenas indicando a
função objetivo como sendo de Min (minimização) ou Max (maximização), conforme
o caso. Na literatura a formulação é normalmente referenciada usando uma função
de Min.
Função objetivo:
∑∑
= =
n
i
n
j
ijij
MIN
1 1
x.c
Sujeito a :
(1) ..., 1, ,1x
1
nj
n
i
ij
==
∑
=
(2) ..., 1, ,1x
1
ni
n
j
ij
==
∑
=
22
x
ij
∈ {0, 1} i, j = 1, ..., n (4)
A variável inteira x
ij
= 1 indica que a cidade j é visitada logo após a cidade i, caso
contrário x
ij
= 0. A variável n representa o número de cidades do problema, S é um
subconjunto do conjunto {1, 2,..., n}, e o símbolo "| |" denota a cardinalidade do
conjunto. A função objetivo representa a minimização do somatório das distâncias
entre as cidades da rota. As restrições (1) e (2) garantem que para cada cidade i ∈
V, há exatamente uma conexão de chegada e de partida para outra cidade. A
restrição (3) garante a não existência de sub-rotas (uma rota que não inclua todas as
n cidades) e a restrição (4) define x como variável binária.
Nos tópicos seguintes são apresentadas algumas técnicas já existentes para
encontrar uma boa solução ou uma solução aproximada para o PCV.
2.4 Métodos de resolução
Os métodos de resolução para o Problema do Caixeiro Viajante podem ser
classificados em Exatos e Heurísticos.
2.4.1 Métodos exatos
De acordo com Weber[25]
em termos de métodos exatos para a solução do PCV e
seus problemas descendentes, existem essencialmente, três abordagens: a
programação inteira mista, a programação dinâmica e branch and bound.
A classificação de algoritmos em termos de complexidade é feita utilizando-se o
conceito de limitação polinomial. Algoritmos polinomiais (ou pertencentes à Classe-
P) são aqueles em que o número de operações elementares necessárias para a
(3) S V, S ,1|| x
∑
∑
∈ ∈
∅≠⊂∀−≤
Si Sj
ij
S
23
obtenção da solução ótima de um dado problema é limitado, no pior caso, por uma
função polinomial do tamanho da entrada do problema. Os problemas para os quais
não se conhecem algoritmos polinomiais capazes de obter a solução exata para os
mesmos, são classificados como NP-Árduos, e são considerados complexos e de
difícil tratamento. O PCV é um exemplo típico de problema NP-Árduo. Portanto, os
algoritmos exatos são usados apenas em soluções de problema de pequeno porte.
Para problemas de maior porte, são utilizados métodos heurísticos polinomiais.
2.4.2 Métodos Heurísticos
Em decorrência da incapacidade dos métodos exatos, os métodos heurísticos (ou
heurísticas) compõem o principal foco de interesse para a resolução do PCV.
Heurísticas são procedimentos de solução que muitas vezes se apóiam em uma
abordagem intuitiva, na qual a estrutura particular do problema possa ser
considerada e explorada de forma inteligente, para a obtenção de uma solução
adequada [4]. Assim, na maioria dos casos as heurísticas propostas tendem a ser
bem específicas e particulares para um determinado problema. Não conseguem
produzir boas soluções para problemas com características, condicionantes ou
restrições pouco diferentes daquelas para as quais foram desenvolvidas [5].
Os procedimentos heurísticos para o Problema do Caixeiro Viajante podem ser
divididos em dois grupos: métodos de construção de rotas e métodos de melhorias
de rotas. Alguns autores consideram ainda um terceiro grupo, o dos compostos, em
que as heurísticas de construção e de melhoria de rotas são utilizadas de forma
conjunta. [26]
Muitos trabalhos foram desenvolvidos nas últimas décadas com o sentido de
melhorar os métodos heurísticos, sem, no entanto prejudicar a sua principal
característica, que é a flexibilidade. Estes trabalhos deram origem às estratégias
comumente conhecidas como metaheurística.
24
2.4.2.1 Metaheurísticas
Metaheurísticas são procedimentos heurísticos. Conduzem um operador de busca
local para a exploração de um espaço de busca para além do ótimo local, alem de
explorar características de boas soluções.
Conforme as características de busca, as metaheurísticas podem ser divididas em
duas classes: a primeira compreende os métodos que exploram apenas um
elemento de uma vizinhança a cada iteração e a segunda compreende os métodos
que exploram uma população de soluções a cada iteração (algoritmos
populacionais).
No primeiro caso, a vizinhança e a forma de explorá-la é alterada de acordo com a
estratégia da busca, sendo que somente um elemento da vizinhança é escolhido a
cada iteração. Esse tipo de varredura do espaço de soluções gera um caminho ou
trajetória de soluções, obtido pela transição de uma solução para outra de acordo
com os movimentos permitidos pela metaheurística. Dentro dessa classe de
métodos pode-se citar simulated annealing [31], Busca Tabu [13,12], GRASP
(Greedy Randomized Adaptive Procedure) [9], Redes Neurais [36] e, Simulated
Jumping (SJ) [1].
Em contraposição aos métodos acima citados, existem aqueles que exploram uma
população de soluções a cada iteração. Esses métodos constituem a segunda
classe de metaheurísticas e suas estratégias de busca são capazes de explorar
várias regiões do espaço de soluções a cada vez. Dessa forma, ao longo das
iterações não se constrói uma trajetória única de busca, pois novas soluções são
obtidas através da combinação de soluções anteriores. Nessa classe estão os
Algoritmos Genéticos [24], Algoritmos Meméticos [34], Scatter Search [18] e
Otimização por Colônia de Formigas (Ant Colony Systems - ACO) [43].
25
2.4.3.1 Algoritmos Genéticos e Meméticos
Algoritmos Genéticos
O termo Algoritmo Genético (AG) do inglês Genetic Algorithm (GA) se refere a uma
família de modelos computacionais inspirados na teoria da evolução de Darwin. Os
AG´s começaram a ser estudados na década de 60 por John Holland da
universidade de Michigan [37].
Estes algoritmos modelam uma solução para um problema específico em uma
estrutura de dados que lembra a estrutura de um cromossomo e aplicam operadores
que re-combinam estas estruturas preservando informações críticas. Assim cada
cromossomo representa uma possível solução de um problema de otimização. Uma
implementação do algoritmo genético começa com uma população (geralmente
randômica) de cromossomos, que são então avaliadas de forma que cromossomos
que representam uma "melhor" solução tenham maiores chances de serem
selecionados e consequentemente reproduzirem, fazendo com que seu material
genético de boa qualidade permaneça nas próximas gerações. A definição de uma
solução melhor ou pior é tipicamente relacionada à população atual e às restrições
do problema.
Uma das vantagens do algoritmo genético é a simplificação que eles permitem na
formulação e solução de problemas de otimização. AG's normalmente trabalham
com descrições de entrada formadas por cadeias de bits de tamanho fixo.
Entretanto, podem trabalhar com cadeias de bits de tamanho variável, como por
exemplo, AG's usados para Programação Genética. AG's possuem um paralelismo
implícito decorrente da avaliação independente de cada uma dessas cadeias de bits,
ou seja, pode-se avaliar a viabilidade de um conjunto de parâmetros para a solução
do problema de otimização em questão. O AG pode ser aplicado a problemas de
otimização complexos, NP - Árduos, como o "caixeiro viajante", que envolvem um
grande número de variáveis e, consequentemente, espaços de soluções de
dimensões elevadas. Além disso, em muitos casos onde outras estratégias de
otimização falham na busca de uma solução, os AG's convergem. São
26
numericamente robustos, ou seja, não são sensíveis a erros de arredondamento no
que se refere aos seus resultados finais.
Existem três tipos de representação possíveis para os cromossomos: binária, inteira
ou real. A essa representação se dá o nome de alfabeto do AG. De acordo com a
classe de problema que se deseje resolver pode-se usar qualquer um dos três tipos.
Como já mencionado, uma implementação de um algoritmo genético começa com
uma população, geralmente randômica, de cromossomos (candidatos a solução de
um determinado problema de otimização). Cada uma das soluções candidatas são
avaliadas. Cada uma delas obtém um custo (fitness) que dirá se esta é uma boa
solução ou não. Assim os cromossomos que obtiverem o melhor fitness, em relação
à população corrente, terão maior probabilidade de se reproduzirem.
A função objetivo de um problema de otimização é construída a partir dos
parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da
solução em relação a um conjunto de parâmetros. Os parâmetros podem ser
conflitantes, ou seja, quando um aumenta o outro diminui. O objetivo é encontrar o
ponto ótimo. A função objetivo permite o cálculo da aptidão bruta de cada indivíduo,
que fornecerá o valor a ser usado para o cálculo de sua probabilidade de ser
selecionado para reprodução.
Os principais conceitos em algoritmos genéticos são:
• Cromossomo (genótipo): cadeia de bits que representa uma solução possível
para o problema;
• Gene: representação de cada parâmetro de acordo com o alfabeto utilizado
(binário, inteiro ou real);
• Fenótipo: cromossomo codificado;
• População: conjunto de pontos (indivíduos) no espaço de busca;
• Geração: iteração completa do AG que gera uma nova população;
• Aptidão: saída gerada pela função objetivo para um indivíduo da população;
27
Figura 3. Estrutura básica de um AG simples.
O algoritmo genético básico envolve alguns passos básicos: geração da população
inicial, avaliação da população, aplicação de operadores genéticos e geração de
uma nova população.
• Geração da população inicial: Gera-se randomicamente uma população inicial
de cromossomos de forma randômica (para que as possíveis soluções não
sofram qualquer influência do meio exterior);
• Avaliação da população: Deve-se encontrar o valor associado ao
desempenho de cada cromossomo, relacionado ao sistema de interesse. A
avaliação da resposta de cada cromossomo é o resultado mais importante no
procedimento do algoritmo genético e diz quão apto está cada indivíduo da
população e se este pode ou não gerar bons indivíduos;
• Aplicação de operadores genéticos: Nesta etapa do algoritmo, operadores de
seleção, crossover e mutação são aplicados aos cromossomos (indivíduos)
da população;
início
População inicial
Avaliação
Fim
Solução encontrada
?
sim
seleção
crossover
mutação
Nova população
não
início
População inicial
Avaliação
Fim
Solução encontrada
?
sim
seleção
crossover
mutação
Nova população
não
28
Aplicações Reais
Os AG's possuem uma larga aplicação em diversas áreas científicas, entre as quais
podem ser destacadas:
• Síntese de circuitos analógicos: para certa entrada e uma saída desejada,
por exemplo, tensão, o AG gera a topologia, o tipo e o valor dos componentes
do circuito;
• Síntese de protocolos: determinação de quais funções do protocolo devem
ser implementadas em hardware e quais devem ser implementadas em
software para que certo desempenho seja alcançado;
• Programação Genética: gera a listagem de um programa, numa determinada
linguagem especificada, para que um determinado conjunto de dados de
entrada forneça uma saída desejada;
• Gerenciamento de redes: supervisão do tráfego nos links e das filas nos
"buffers" de roteadores para descobrir rotas ótimas e para reconfigurar as
rotas existentes no caso de falha de algum link;
• Computação Evolutiva: gera programas que se adaptam a mudanças no
sistema ao longo do tempo;
• Otimização evolutiva multi-critério: otimização de funções com múltiplos
objetivos que sejam conflitantes;
• Problemas de otimização complexos: problemas com muitas variáveis e
espaços de soluções de dimensões elevadas; exemplo: problema do caixeiro
viajante;
• Ciências biológicas: modela processos biológicos para o entendimento do
comportamento de estruturas genéticas;
• Autômatos auto-programáveis;
29
Algoritmos Meméticos
Nos algoritmos meméticos há a introdução de mais um operador, o de busca local.
Isso faz com que o algoritmo genético padrão se transforme no que pode ser
chamado de Algoritmo Memético ou Algoritmo Genético Híbrido [34].
Este mecanismo permite que o algoritmo evolua além da evolução genética. Permite
que um outro tipo de informação, cultural, seja transportado através da comunicação
entre os indivíduos e não pela recombinação. Além disso, genes são transmitidos
através de gerações, enquanto os memes (unidade replicante da informação
cultural) podem ser transmitidos sem que uma geração seja transcorrida. Assim a
informação contida nos memes pode passar para vários outros indivíduos da
população atual.
Na literatura, os algoritmos meméticos
têm se mostrado bastante eficientes na
resolução de uma vasta gama de aplicações do mundo real. Mas, nem todos os
problemas podem ter resultados satisfatórios ou mesmo serem representados
adequadamente para o uso de Algoritmos Genéticos e Meméticos.
2.4.3.2 Scatter Search
Esta é uma técnica de otimização desenvolvida por Fred Glover em 1977
apresentadas em [14]. Estudos recentes têm demonstrado as vantagens práticas de
se utilizar este método em um enorme leque de problemas, tanto os problemas
clássicos da literatura especializada quanto os do mundo real.
O Scatter Search (SS) contrasta com outras técnicas de otimização, como o
algoritmo genético, por fornecer princípios de construção das soluções utilizando
estratégias alternativas à randomização. O scatter search opera sobre um conjunto
de soluções, o conjunto referência, e combinando estas soluções cria outras. Assim,
novas soluções são criadas a partir de uma combinação de duas soluções do
conjunto inicial [21]. Mais precisamente, a figura abaixo cima mostra uma forma de
obter o conjunto referência. Nesta figura se assume que o conjunto referência
30
original se refere a um conjunto de soluções denominados de A, B e C. Depois da
cominação de A e B a solução 1 é criada, mais precisamente um número de
soluções só segmento de reta definido por A e B são criadas; contudo somente uma
solução, neste caso a solução 1, será introduzida no conjunto referência (não será
discutido neste Capítulo quais critérios são utilizados para esta escolha).
Figura 4. Conjunto referência bi-dimensional.
Esta técnica não produz soluções por mecanismos de recombinação, mas escolhe
soluções candidatas para entrar no conjunto referência fornecida pela aplicação de
alguma heurística. Ao contrário de uma população em algoritmos genéticos o
conjunto de soluções do scatter search é relativamente pequeno [32].
Em algoritmos genéticos duas soluções são escolhidas aleatoriamente na população
e utiliza-se um mecanismo de recombinação para gerar um ou mais descendentes.
No scatter search são escolhidos dois ou mais elementos de referência de forma
sistemática para se criar novas soluções. Desde que o número seja de dois a cinco
elementos no conjunto. Caso contrário seria necessário um processo altamente
seletivo para a escolha destes indivíduos na população.
Resumidamente, pode-se assumir que esta técnica tem três procedimentos
principais [21].
31
1. Geração. Geram-se um conjunto de vetor solução inicial através de
procedimentos heurísticos, designados para o problema e escolhe-se um
conjunto das melhores soluções para servirem de “conjunto referência”;
2. Criação. Criam-se novos pontos consistindo de combinações lineares de
um subconjunto do “conjunto referência” atual. As combinações lineares
são escolhidas para produzir pontos, dentro e fora das regiões convexas
medidas pelas soluções de referência;
3. Extração. Extrai-se um conjunto das melhores soluções criadas na etapa 2
para serem usadas como pontos iniciais para uma nova aplicação dos
processos heurísticos da etapa 1;
No algoritmo Scatter Search (SS) estas etapas são repetidas até alcançar um
limite especificado de iteração.
Assim, a implementação do SS necessita de cinco métodos:
• Um método para gerar uma coleção de diversas soluções utilizando uma
solução arbitraria como entrada;
• Um método de melhoria para transformar uma solução em uma ou mais
soluções. Se nenhuma melhoria ocorrer, a solução de saída será a mesma
solução de entrada;
• Um método para construir e ajustar o conjunto, segundo uma referência
escolhida entre as melhores soluções;
• Um método de geração de um subconjunto que opere sobre o conjunto
referência com o intuito de produzir novas soluções para servirem de base
para formar novas soluções;
• Um método de combinação das soluções, para que, dado um conjunto de
soluções, através desse método novas soluções possam ser geradas;
O scatter search tem sido aplicado, assim como o algoritmo genético, a uma enorme
quantidade de problemas e tem se mostrado eficiente na resolução destes. Tendo
desempenho comparável ao de outros métodos evolucionários de resolução para
32
famosos problemas de otimização. Por isso tem se estabelecido como um dos
principais métodos de computação evolucionária.
2.4.3.3 Otimização por Colônia de Formigas
Otimização por Colônia de Formigas, do inglês Ant Colony Optimization (ACO), foi
proposta por Dorigo e Caro em [7] e é uma evolução dos Sistemas de Formigas
proposto por Dorigo em [8]. Esta técnica tem sido bastante utilizada para resolver
problemas de roteamento como o do Caixeiro Viajante.
Esta técnica é baseada no convívio social das formigas na natureza. Pois, as
formigas são insetos que possuem complexo sistema de organização e divisão de
tarefas para garantir a sobrevivência do formigueiro. O método de otimização se
baseia especificamente na forma como as formigas resolvem seu problema de
comida.
Inicialmente as formigas percorrem aleatoriamente as regiões ao redor do
formigueiro em busca de alimento. Cada formiga enquanto percorre seu caminho
deixa um rastro de uma substância chamada de feromônio, deixando desta forma
um rastro no chão. As formigas que vem depois percebem esta substância e tendem
a escolher, portanto, o caminho que mais concentração de feromônio tiver. Assim
esse caminho de feromônio informa não só às formigas sobre o caminho de volta,
mas também qual o melhor caminho a percorrer. Assim, no problema de otimização,
cada formiga é capaz de encontrar uma solução completa para o problema; contudo
a melhor solução é aquela obtida através do cruzamento de diversas soluções.
33
Figura 5. Generalização da Otimização por Colônia de Formiga.
Em resumo, o algoritmo da colônia de formiga é uma metaheurística que se baseia
no modo como as formigas encontram seu alimento,
citado anteriormente. Uma
população de agentes (formigas) pode ser utilizada para a resolução de problemas
de otimização combinatória. O ACO é uma técnica da área denominada inteligência
coletiva (Swarm inteligence) [4].
34
Capítulo 3
Vocabulary Building
3.1 Introdução
O Vocabulary Building (VB) foi utilizado pela primeira vez por Fred Glover em 1992
em [20]. No ano de 1995 ele usou este termo, em [17] e [18], para descrever um
método de construção de solução em Busca Tabu, técnica que descende do Scatter
search.
Em 1995 o Vocabulary Building é também utilizado em [39] e [30] para resolver
problemas de roteamento de veículos. Neles o VB foi utilizado como técnica para
diversificar, intensificar e paralelizar a busca local. Esta técnica tornou a busca local
mais robusta, pois converge para uma solução mais próxima da melhor solução
conhecida. Esta técnica mostrou diversas vantagens, uma delas se refere ao fato de
ser relativamente fácil projetar uma busca local que encontre localmente boas
soluções. Em segundo, o VB demonstrou ser uma técnica que pode ser aplicada a
muitos problemas de roteamento, por exemplo, incluindo algumas restrições como;
• Janela de tempo para a entrega;
• Veículos diferentes (custo do uso por quilômetro, a capacidade do volume, a
capacidade de carregamento);
• Restrições nas rotas (comprimento máximo, quebras de veículos, clientes
que não podem ser alcançados por nenhum veículo);
Em terceiro lugar, esta técnica pode facilmente ser utilizada em sistemas paralelos
com um número arbitrário dos processadores (não dependendo do tamanho do
problema).
Em 1997 [16] Glover utilizou o conceito de Vocabulary Building em uma
Metaheurística conhecida como Scatter Search, que difere dos métodos
35
evolucionários, tais como algoritmos genéticos, por fornecer princípios de construção
de trajetos [16].
Em 1998 Scholl at al, publicou “Pattern Based Vocabulary Building for Effectively
Sequencing Mixed-Model Assembly Lines”. Embora esta técnica tenha sido utilizada
com sucesso nos trabalhos citados anteriormente esta técnica não tem chamado a
atenção dos pesquisadores da área de otimização há algum tempo [19].
O Vocabulary Building cria combinações estruturadas não somente pela utilização
de elementos primitivos de vizinhança, mas também pela construção de elementos
mais complexos. Esta técnica tem este nome devido à analogia com o processo de
união de palavras em frases que podem gerar progressivamente em sentenças e
parágrafos úteis, onde as construções valiosas em cada nível podem ser tanto
visualizadas como representas por “palavras em uma ordem mais elevada” [16].
Em [16] Fred Glover introduziu estratégias de construção de vocábulos em uma
técnica conhecida como “Surrogate Constraint”. Nesse artigo, Glover não chegou a
utilizar Vocabulary Building. Ele apenas citou que as técnicas ali descritas tinham
uma relação com o processo de construção de vocábulos. Tal relação é devido ao
fato de que a estratégia de “Surrogate Constraints” procura identificar elementos que
satisfazem a restrições complexas que foram originadas a partir da combinação de
restrições mais elementares (por exemplo, restrições originais do problema). Aplicou
suas idéias ao problema de coloração de vértices (Covering Problems) e no
Problema do conjunto independente (independente set problem), problemas
clássicos da otimização combinatória, onde fornece uma estrutura que segundo ele
“podem ser utilizadas em outras aplicações”. Estas estratégias foram mais tardes
publicadas em [16].
3.2 definição
O Vocabulary Building opera criando um conjunto de fragmentos de soluções,
chamados vocábulos, que são sucessivamente montados, desmontados e
36
modificados para produzir novos fragmentos, que são finalmente transformados em
uma possível solução. Por exemplo, pode-se considerar como sendo um desses
fragmentos parte de um cromossomo do algoritmo genético.
O Vocabulary Building aplica ao conjunto de vocábulos os ganhos da decomposição
de boas soluções e a possibilidade de transformá-la em uma solução melhor através
de alguns métodos de construção de soluções. Este conceito pode ser utilizado em
aplicações onde um valor agregado a cada uma dessas soluções, a função-objetivo,
é o critério de decisão para julgar quão boa é uma solução [15]. Assim, a motivação
por trás do Vocabulary Building é tirar vantagem destes contextos onde uma solução
parcial pode frequentemente gerar boas soluções completas. Uma estratégia de
procurar boas soluções parciais, ou seja, bons vocábulos podem ajudar na
construção de uma boa solução completa.
Esses fragmentos são extraídos de soluções previamente geradas, que podem ser
escolhidas ao acaso ou, como forma de garantir a sua qualidade, podem ainda
serem retirados de soluções elite.
No problema dos conjuntos independentes de vértices, uma maneira de aplicar este
conceito seria fragmentar soluções criando sub-problemas. Vocábulos seriam
então
selecionados e armazenados em um conjunto chamado de “pool”. O objetivo seria
encontrar os maiores conjuntos independentes dentro deste pool, a fim de identificar
novos candidatos para o conjunto independente Máximo [15]. Aplicado ao problema
do Caixeiro Viajante, pode-se considerar uma solução como sendo uma rota a ser
percorrida pelo caixeiro e um vocábulo como sendo parte desta rota a ser
transformada em uma outra rota através de métodos construtivos, como por
exemplo, o método do “vizinho mais próximo”. Um dos passos mais importantes do
processo se dá na escolha de quais vocábulos serão utilizados e de como eles
serão gerados.
37
Figura 6. Possível representação do conjunto elite e do pool de vocábulos
Esta estratégia é altamente aplicável a uma vasta gama de procedimentos
metaheurísticos. Tanto para os procedimentos com memória adaptativa como para
modelos evolucionários e populacionais.
Em geral, o Vocabulary Building deve confiar em métodos destrutivos tanto quanto
nos construtivos, pois é preciso gerar bons fragmentos através da decomposição
das soluções. Um método destrutivo nada mais é do que essencialmente quebrar
boas soluções para gerar novos fragmentos. Onde os métodos construtivos serão
aplicados para gerar novas soluções completas.
Observe a figura abaixo, que mostra o ciclo do processo realizado pelo Vocabulary
Building. Além dos métodos construtivos (constrói as novas soluções) e destrutivos
(descompõe as soluções transformando-as em fragmentos ou vocábulos) um outro
aspecto importante é como filtrar, ou seja, escolher os melhores fragmentos do pool
de fragmentos e as melhores soluções das populações atuais.
Pool de VocábulosConjunto Elite Pool de VocábulosConjunto Elite
38
Figura 7. Processo de Vocabulary Building.
3.3 Formas de Vocabulary Building utilizadas
Neste trabalho, a idéia de Vocabulary Building foi explorada de duas formas
distintas. Foi utilizado um pool de vocábulos, que vai se transformando ao longo das
iterações; além disso, foi utilizado um mecanismo de criação de vocábulos que se
utiliza da contração de vértices.
3.3.1 Pool de vocábulos
Inicialmente um pool de vocábulos é gerado contendo trechos de tamanho igual a
dois (equivalente a uma aresta). A cada vocábulo criado associa-se um contador
que funciona como se fosse uma medida de sua fitness. Este contador servirá para
indicar a qualidade da atuação do vocábulo. Caso o vocábulo ao ser inserido em um
indivíduo completo melhore sua fitness, o seu contador é incrementado, indicando
que ele representa um trecho de boa qualidade e pode ser utilizado outra vez. Neste
trabalho a geração do pool de vocábulos foi realizada de forma aleatória. Contudo,
outras estratégias podem ser utilizadas para esse propósito.
filtro
Soluções
completas
Fragmentos de
soluções
Decomposição
Construção
filtro
filtro
filtro
39
Em cada iteração é realizada a aplicação dos vocábulos em cada um dos indivíduos
contidos no conjunto elite. Neste trabalho, considera-se como conjunto elite o grupo
de indivíduos que possuem a melhor fitness; outras estratégias para a composição
do conjunto elite são passiveis de serem utilizadas, embora apenas a estratégia
citada acima tenha sido implementada e testada neste trabalho. A cardinalidade
desse conjunto é um dos parâmetros do algoritmo apresentado que foi mantido com
valor igual a quatro.
A aplicação dos vocábulos em um indivíduo é feita da seguinte forma:
1. Verificar o resultado da inserção de cada vocábulo, isoladamente, no
indivíduo em questão;
2. Retornar o indivíduo resultante da melhor inserção;
3.3.1.1 Mecanismo de inserção do vocábulo em um indivíduo
O procedimento de inserção já citado é realizado da seguinte forma: inicialmente a
aresta contendo os dois vértices interligados por ela que são identificados no
vocábulo são retirados do grafo. Depois da retirada da aresta é feita a inserção do
vocábulo entre os demais vértices do grafo. Os resultados de tais inserções são
armazenados e a combinação que resultar na melhor solução será então mantida. A
Figura 8 mostra o processo de aplicação do vocábulo em um indivíduo que ira fazer
parte da nova população.
Os pontos de cor mais escura são os vértices contidos no vocábulo. Então na figura
“a” são mostradas as arestas a serem retiradas para que ocorra a exclusão dos
vértices contidos no vocábulo e as arestas marcadas de vermelho serão retiradas.
Na figura “b” de vermelho encontra-se a aresta a ser excluída do grafo para que os
vértices que estavam isolados sejam inseridos no grafo entre um outro ponto. O
mesmo é mostrado nas figuras “c” e “d”, ate que todas as opções sejam testadas e
nenhuma aresta necessite mais ser retirada, como mostra a figura “e”.
40
Figura 8. Processo de inserção de um vocábulo em um indivíduo.
Após a realização do procedimento de inserção de um vocábulo Y em um indivíduo
X, faz-se a atualização do primeiro. A atualização se dá da seguinte forma:
Passo 1: se com a inserção do vocábulo Y o indivíduo X melhorou a sua
fitness, então o contador de Y é incrementado em uma unidade. Caso
contrário o contador de Y é decrementado também em uma unidade.
Passo 2: se a fitness de Y chegou a 0 (zero) então vá para o Passo 2.a; caso
contrario vá para o Passo 2.b
Passo 2.a: se o tamanho de Y é igual ao mínimo possível (para esse
trabalho o mínimo é igual a dois – representação de uma aresta) então
vá para o Passo 2.a.a; caso contrário vá para o Passo 2.a.b;
Passo 2.a.a: dentro de uma probabilidade P uma aresta do
indivíduo é adicionada ao vocábulo e uma aresta deste é
descartada (a aresta adicionada é uma das que estão
adjacentes ao vocábulo, dentro do indivíduo); caso contrário o
vocábulo Y é substituído por um vocábulo aleatório.
Passo 2.a.b: fragmentar o vocábulo Y em dois outros
vocábulos, Y1 e Y2 e fazer com que seus contadores sejam
iguais ao valor máximo permitido (neste trabalho este valor
máximo é igual a quatro);
Passo 2.b: se o contador do vocábulo chegou ao máximo permitido
então o vocábulo Y será combinado com algum outro vocábulo do
pool. Faz-se o contador do vocábulo resultante igual ao valor inicial
(nesse trabalho, igual a dois).
a) e)d)c)b)
Vocábulo
a) e)d)c)b)
Vocábulo
a) e)d)c)b)
Vocábulo
41
3.3.1.2 Mecanismo de combinação dos vocábulos
O processo de combinação tem como objetivo obter bons vocábulos a partir de dois
outros vocábulos de alta qualidade. Isso ocorre para que se possa verificar o
desempenho de mais de um vocábulo atuando juntos.
Esse processo se dá através da concatenação da seqüência de vértices de dois
vocábulos e pode ocorrer de duas formas diferentes:
1. Concatenação por aglutinação: procura-se no pool o vocábulo de maior
contador que seja compatível com Y. Um vocábulo A é compatível com um
vocábulo B se o ultimo vértice de A coincide com o primeiro vértice de B, ou
vice versa; no primeiro caso, a seqüência de vértices do vocábulo resultante é
igual à concatenação de A com B’, sendo B’ igual B menos o seu primeiro
vértice;
2. Concatenação por justaposição: faz-se a concatenação direta da seqüência
de vértices de Y com o vocábulo de maior contador do pool. Sejam dois
vocábulos A e B sem vértices em comum. Se custo(ultimo[A], primeiro[B] ) <
custo(ultimo[B], primeiro[A]) então concatenamos a seqüência de A com a
seqüência de B; caso contrario, concatenamos a seqüência de B com a
seqüência de A.;
Ao realizar o processo de concatenação, a informação necessária para que os
vocábulos originais possam ser recuperados deve ser salva. Esta informação é
organizada na forma de uma árvore, que indica como e onde o vocábulo será
separado, caso seu contador chegue ao valor zero, para que os vocábulos que o
originaram possam voltar a existir isoladamente no pool. Um vocábulo originado
pela concatenação de dois outros é chamado de vocábulo composto.
A figura a seguir demonstra o processo de concatenação implementado neste
trabalho. Os vocábulos mostrados à esquerda vão sucessivamente se combinando e
originando novos vocábulos (compostos); esses por sua vez são utilizados em um
novo processo de combinação.
42
Figura 9. Ilustração do processo de concatenação.
Os pares de vocábulos mais à esquerda não possuem nenhum elemento em
comum; portanto, faz-se a concatenação por justaposição. Caso seja necessário
recuperar os vocábulos originais, precisa-se fragmentar o vocábulo composto a
partir da terceira posição da sua lista de vértices, de forma que os vocábulos obtidos
não tenham nenhum vértice em comum. Assim sendo, armazena-se esta informação
em uma estrutura de dados (nó) e faz–se com que esse nó passe a ser a raiz da
árvore de quebra do vocábulo composto resultante (conforme ilustrado na figura).
Os números contidos na árvore de quebra dizem respeito local onde o cromossomo
será quebrado caso seja necessário retornar à sua forma anterior, informa se a
concatenação ocorreu por justaposição (j) ou por aglutinação (a).
3.3.1.3 Mecanismo de fragmentação do vocábulo
O processo de fragmentação do vocábulo visa devolver vocábulos de boa qualidade
ao pool. Um vocábulo é considerado como sendo de boa qualidade quando, por ter
conseguido melhorar vários indivíduos da população, obteve um valor de contador
maior do que o valor inicial.
Vocábulo composto
Vocábulo composto
Á
rvore de
quebra
Á
rvore de
quebra
:
A
b
#
:
c
d
#
:
e
f
#
:
g
A
#
.
e
f
g
A
#
b
c
d
4 a
3 j
3 j
.
A
b
c
d
#
3 j
.
e
f
g
A
#
3 j
Vocábulo composto
Á
rvore de
quebra
43
O processo de concatenação utiliza dois vocábulos de boa qualidade para formar
um novo vocábulo composto. Ao longo das iterações, esse novo elemento pode se
mostrar pouco ou nada eficiente (contador igual à zero); nesse caso, é interessante
recuperar os vocábulos originais (de boa qualidade) e descartar o vocábulo
composto. Para isso, utiliza-se a informação contida no nó raiz da árvore de quebra
deste último vocábulo. Esse processo, denominado de fragmentação, pode ocorrer
de duas maneiras distintas, dependendo da informação contida no nó raiz da árvore
de quebra do vocábulo. As seqüências de vértices dos vocábulos resultantes são
cópias de partes do vocábulo composto a ser fragmentado.
1. Fragmentação de vocábulos justapostos: o primeiro vocábulo é formado pela
seqüência contida entre o vértice inicial e o vértice anterior ao indicado pelo
nó raiz da árvore de quebra. O segundo vocábulo é formado pela seqüência
contida entre o vértice indicado pelo nó raiz da árvore de quebra e o vértice
final;
2. Fragmentação de vocábulos aglutinados: o primeiro vocábulo é formado pela
seqüência contida entre o vértice inicial e o vértice indicado pelo nó raiz da
árvore de quebra, inclusive. O segundo vocábulo é formado pela seqüência
contida entre o vértice indicado no nó raiz da árvore de quebra (inclusive) e o
vértice final;
A figura 10 demonstra o processo de fragmentação implementado neste trabalho.
Os vocábulos mostrados mais à esquerda vão se fragmentando e originando os
vocábulos mais à direita.
44
Figura 10. Processo de fragmentação do vocábulo
3.3.1.4 Evolução do pool de vocábulos
Ao longo das iterações, o pool de vocábulos vai sofrendo modificações que ocorrem
à medida que as operações de combinação, fragmentação e atualização são
realizadas. Essas operações fazem com que o pool de vocábulos seja enriquecido,
contendo elementos ainda não contemplados pela busca ou elementos com os quais
se obteve melhoras.
Tal enriquecimento se deve aos seguintes fatores:
1. Utilização de arestas presentes em indivíduos de alta qualidade da
população;
2. Utilização de arestas aleatórias visando a alcançar a diversificação da busca;
3. Utilização, em conjunto, de trechos que demonstraram serem úteis;
A estratégia Vocabulary Building baseia-se na idéia de se tentar identificar trechos e
combinações destes que sejam interessantes para o processo de busca. A
estratégia de pool de vocábulos apresentado neste trabalho incorpora a idéia de
vocabulary building através da amostragem da qualidade de trechos, feita através do
procedimento de inserção. De acordo com a qualidade aferida na amostra, pode-se
descartar ou reutilizar um vocábulo. Com isso, a busca é feita levando-se em conta o
Árvore de
quebra
Árvore de
quebra
Vocábulo composto
Vocábulo composto
Vocábulo composto
:
A
b
#
:
c
d
#
:
e
f
#
:
g
A
#
.
e
f
g
A
#
b
c
d
4 a
a
3 j
3 j
.
A
b
c
d
#
3 j
.
e
f
g
A
#
3 j
Árvore de
quebra
45
fator “medida de influência” [15], ficando mais focada nas regiões do espaço de
busca que se encontram ao redor dos vocábulos de alta qualidade.
3.3.2 Contração de Vértices
O Path Relinking (PR) é uma técnica de otimização que opera com uma população
de soluções (método evolucionário). PR emprega procedimentos para criar novos
caminhos entre soluções existentes e geram através delas os indivíduos de uma
nova geração. O Vocabulary Building opera de maneira similar, diferindo apenas no
fato de que não é preciso operar sobre soluções completas; a idéia é que se possa
utilizar trechos de soluções, combinado-os entre si e com soluções completas. Em
ambas as técnicas os resultados das combinações são explorados em busca de
melhores soluções.
Dois dos principais aspectos que caracterizam uma determinada implementação de
PR ou VB são:
1. A forma como a combinação é realizada;
2. O modo como os resultados das combinações são explorados;
As técnicas de PR e VB são muito flexíveis, consistindo apenas de um conjunto de
idéias (e não de um algoritmo pré-determinado, tal como a técnica de Simulated
Annealing). Assim sendo, o pesquisador fica livre para utilizar a regra de
combinação que considere mais adequada. Mais de uma regra pode ser utilizada;
contudo, a estratégia padrão consiste em utilizar somente uma regra. Quando mais
de uma regra é utilizada, elas são aplicadas isoladamente umas das outras.
Em [21], Glover cita um dos primeiros trabalhos envolvendo estratégias de solução
baseadas em combinação de regras de decisões [22]. Comenta também que a
abordagem utilizada neste último foi motivada pela suposição de que a informação a
respeito da atratividade de diversas escolhas é capturada de forma diferente por
regras diferentes. Supõe também que essa informação pode ser explorada mais
46
efetivamente por meio de mecanismos de combinação de regras do que pela
estratégia padrão de selecionar uma regra por vez (isoladamente das outras).
A contração de vértices implementada nesse trabalho utiliza a idéia proposta por
Glover, apresentando um mecanismo de combinação que se utiliza de um conjunto
de soluções para construir vocábulos e, posteriormente, realizar um processo de
montagem para obter soluções completas (nesse caso ciclos Hamiltonianos). Como
regras básicas, são utilizadas heurísticas construtivas.
O mecanismo proposto funciona da seguinte forma:
1. Cada heurística construtiva produz um determinado conjunto de soluções.
Considerando-se todas as soluções (produzidas por todas as heurísticas),
identifica-se as arestas que estão presentes em todas elas;
2. Com o conjunto de arestas em mãos, identificamos e concatenamos trechos
que são formados por arestas consecutivas (normalização). De posse desses
trechos, cria-se um grafo auxiliar no qual cada trecho é representado por um
único vértice (contração - ver figura abaixo);
Figura 11.Identificação e normalização das arestas comuns às soluções mostradas.
47
Na Figura 11, são apresentadas quatro rotas completas para o TSP
(pertencentes ao conjunto elite). A partir delas, foram identificadas as arestas
que estão presentes em todas elas. Em seguida, as arestas consecutivas são
consideradas como sendo um só trecho (cada trecho está circulado com uma cor
diferente).
Figura 12. Soluções contendo trechos contraídos (elipses maiores).
3. A matriz de custos [a
ij
] desse grafo auxiliar é calculada da seguinte forma
(sendo [g
ij
] a matriz de custos do grafo original):
a. a
ij
= g
ij
; se i e j não representam trechos (i e j são vértices comuns, que
não fazem parte de nenhuma aresta identificada pelo mecanismo
descrito acima);
b. a
ij
= g
fim(i), j
; se i representa um trecho e j representa um vértice comum.
fim(i) equivale ao último vértice do trecho representado por i;
c. a
ij
= g
i, ini(j)
; se i representa um vértice comum. ini(j) equivale ao primeiro
vértice do trecho j;
d. a
ij
= g
fim(i), ini(j)
; se i e j ambos representam trechos;
A transformação descrita acima é equivalente à que é apresentada em [44] e [23].
48
4. Com a matriz de custos definida, criamos um conjunto de soluções para esse
grafo auxiliar (nesse trabalho isso foi feito através de métodos construtivos e
busca local);
5. Faz-se a “tradução” das soluções produzidas com o grafo auxiliar para
soluções viáveis com o grafo original. Isso é feito simplesmente com a
expansão dos nós que representam os trechos identificados anteriormente.
Esse conjunto de soluções é chamado de “População Auxiliar”;
6. Faz-se busca local na População Auxiliar;
7. Insere-se a melhor solução da População Atual na População Auxiliar;
8. Exclui-se o pior indivíduo da População Auxiliar e substitui-se a População
Atual pela População Auxiliar;
A idéia por trás desse mecanismo é a suposição de que cada heurística percebe de
uma maneira diferente a importância de uma determinada aresta para a construção
de uma solução ótima. Essa suposição está intimamente relacionada com aquela
feita por Glover (citada acima). Dessa forma, cada heurística toma decisões próprias
e valida as que foram tomadas pelas demais heurísticas (as decisões tomadas se
referem a usar ou não uma determinada aresta).
3.4 Heurística Vocabulary Building
Conforme visto anteriormente, duas formas de Vocabulary Building foram
implementadas. A primeira delas, o pool de vocábulos, foi implementada em
conjunto com um Algoritmo Memético, explanado no próximo capítulo. A segunda
forma, que se utiliza da contração de vértices, foi implementado isoladamente e em
conjunto com o Algoritmo Memético. Esses métodos também foram implementados
ao mesmo tempo em um Algoritmo Memético.
Aqui, são apresentados os resultados relativos ao processo de Vocabulary Building
com contração de vértices, implementado isoladamente. O algoritmo consiste em
aplicar o processo de VB com contração de vértices a cada iteração (sendo o
número de iterações definido pelo usuário). A cada iteração, o processo é aplicado
sobre a população resultante da iteração anterior.
49
Capítulo 4
Algoritmo Memético aplicado ao Problema do
Caixeiro Viajante Assimétrico
4.1Definição
O Algoritmo Memético – AM (do inglês Memetic Algorithm - MA) é uma heurística
populacional que, assim como os algoritmos genéticos é baseada na evolução das
espécies. Tem sido bastante utilizada para resolver problemas de otimização
combinatória. Foi apresentado por Moscato em [34]. É considerada como sendo
uma evolução dos algoritmos genéticos. O algoritmo memético é inspirado na idéia
de meme de Dawkins [6] onde, em contraste com o conceito de genes os memes
são tipicamente adaptados na população e só depois transmitem sua informação
para as próximas gerações.
Figura 13. Através de dois pontos considerados ótimos locais X e Y, por exemplo, pode-se
obter um descendente z´, que através da busca local pode chegar a ser um ótimo local.
De acordo com Moscato e Normam em [35], a “evolução memética” pode ser
comparada a um algoritmo genético com um mecanismo de busca local refinado.
Então, um AM pode ser pensado como sendo simplesmente um mecanismo
especial de busca local sobre um algoritmo genético num subespaço de soluções,
50
como esta exemplificado na Figura 5, acima [35]. Geralmente a recombinação e a
mutação são utilizadas como mecanismo de busca de soluções fora de ótimos
locais. Esses mecanismos podem danificar as soluções, o que pode ser corrigido por
um método de busca local.
Como os AMs são considerados uma evolução dos AGs, nada mais natural que o
primeiro tenha inúmeras semelhanças com o segundo, uma delas é a sua estrutura
básica como é mostrado na Figura 6. Embora os indivíduos que formam a população
dos algoritmos meméticos sejam chamados de “agentes”.
Figura 14. Estrutura básica de um Algoritmo Memético.
Aspectos de implementação de um Algoritmo Memético:
• População inicial: é criada uma população inicial de agentes representando
as soluções atuais dentro do espaço de soluções do problema;
- Inicio
Gerar população inicial;
Otimizar população (realizar busca local);
Avaliar População;
Enquanto (não atender as condições de parada) Fazer
Elitismo;
Nova População =Ø;
Enquanto (Nova População não estiver completa) Fazer
Selecionar os pais;
Aplicar operadores de recombinação e mutação;
Inserir descendentes na Nova População;
Fim enquanto
Otimizar população (realizar busca local);
Avaliar Nova População;
População Atual = Nova População;
Fim enquanto
- Fim
51
• Geração: população atual em um determinado instante de tempo;
• Função de avaliação: mede a qualidade das soluções existentes em uma
população;
• Recombinação: este termo descreve a troca de informação entre dois
agentes. Difere do cruzamento no sentido de que não é necessário haver dois
agentes para que ocorra a recombinação;
• Mutação: mudança aleatória nos memes para garantir a diversidade da
população;
Neste Capítulo será apresentada uma implementação do AM para o PCVA. Uma
outra implementação pode ser encontrada em [3].
4.2 Aplicando o Algoritmo Memético ao Problema do
Caixeiro Viajante Assimétrico
3.2.1 População inicial e representação dos indivíduos
Uma população pode ser inicializada de forma aleatória, através da utilização de
alguma heurística construtiva ou com uma combinação dos dois métodos.
Neste trabalho a população inicial foi gerada através da Heurística conhecida como
“Heurística do Vizinho mais próximo” (Nearest Neighbor - NN). Aplicando esta
heurística ao PCV tem-se: começa a rota da cidade de origem e adiciona à rota a
cidade mais próxima da ultima cidade adicionada, o tour é concluído quando todas
as cidades são adicionadas. Outra heurística utilizada foi a heurística chamada de
“Heurística da inserção mais barata”, onde o tour começa com uma sub-rota, que
pode ser obtida através do método vizinho mais próximo, envolvendo apenas
algumas cidades e incluir uma nova cidade na sub-rota em uma vizinhança onde sua
inserção seja a mais barata . Foi observado que em algumas instâncias a heurística
do “vizinho mais próximo” se mostrou melhor e em outras a “inserção mais barata”
obteve melhores soluções, então as duas heurísticas contribuíram cada uma com
52
50% (cinqüenta por cento) dos indivíduos da população. Além disso, em testes
realizados utilizando somente um dos métodos, foram obtidos resultados de menor
qualidade.
Figura 15. Representação de uma possível solução para o PCV.
Os indivíduos da população (rotas) são estruturados como sendo um vetor de n
posições, onde cada solução é uma combinação entre as cidades da rota, ou seja,
uma possível solução. Cada vetor possui uma função de aptidão, a fitness, que na
figura acima está representada pelo símbolo #. Este valor é determinado pelo custo
total do tour representado por cada um dos vetores da população inicial.
4.2.2 Seleção dos melhores agentes
A idéia principal de um operador de seleção em um algoritmo genético é oferecer
aos melhores agentes da população corrente, preferência para o processo de
reprodução, permitindo que estes indivíduos possam passar as suas características
às próximas gerações. Isto funciona como na natureza, onde os indivíduos
altamente adaptados ao seu ambiente possuem naturalmente mais oportunidades
para reproduzir do que aqueles indivíduos considerados mais fracos [42]. Neste
trabalho a seleção dos indivíduos foi feita por ranking, ou seja, os indivíduos de uma
população são ordenados de acordo com a sua ordem em um ranking onde as
posições são determinadas pelo valor da fitness de cada indivíduo.
A C B E D #A C B E D #A C B E D #
A
BE
D C
A
BE
D C
A
BE
D C
A
E B
CD
Possível Solução
Cidade de origem
A C B E D #A C B E D #A C B E D #A C B E D #A C B E D #A C B E D #A C B E D #
A
BE
D C
A
BE
D C
A
BE
D C
A
BE
D C
A
BE
D C
A
BE
D C
A
BE
D C
A
E B
CD
A
E B
CD
Possível Solução
Cidade de origem
53
4.2.3 Operadores de recombinação
Percebeu-se que a qualidade das soluções em um algoritmo populacional dá-se
também pela forma como suas populações são obtidas ao longo das gerações.
Assim os métodos de recombinação são instrumentos úteis apara a obtenção de
novos agentes. Um operador de recombinação permite a troca de material genético
entre dois agentes, assim como permite que um outro agente seja obtido através da
Permutação de seus vértices sem a necessidade de mais de um agente para isso.
Existe uma vasta quantidade de operadores de recombinação, mas este trabalho só
contemplará os dois que aqui foram utilizados em instâncias da TSPLIB para o PCV
a serem testados com a busca local. São eles:
1. SAX (Strategic Arc Crossover): que é um melhoramento do SEX,
originalmente proposto por Moscato para o TSP simétrico em [35].
2. Crossover de dois pontos (Two Points Crossover);
Devido ao fato de que os dois mecanismos apresentaram desempenho semelhante
o mecanismo conservado na implementação foi o de dois pontos.
4.2.3.1 Strategic Arc Crossover (SAX)
Este mecanismo de recombinação descende do SEX (Strategic Edge Crossover)
apresentado por Moscato em [35] que é um melhoramento do método Enhanced
Edge Recombination [28,29]. O SAX é uma adaptação do SEX para o caso
assimétrico. O objetivo deste operador é criar um filho que tenha o maior número
possível de arcos provenientes de seus pais [3].
4.2.3.2 Crossover de dois pontos (Two Points Crossover)
Este é um operador de recombinação utilizado após a seleção dos indivíduos pais.
Este método de recombinação é caracterizado pela troca de material genético entre
os dois indivíduos selecionados com o objetivo de gerar um novo descendente.
54
Esta recombinação ocorre da seguinte maneira, dois pontos de quebra do
cromossomo são escolhidos, a partir desses pontos realiza-se a troca de material
cromossômico entre os indivíduos.
4.2.4 Mecanismo de busca local
A busca local neste trabalho foi testada com dois tipos de vizinhanças [40]. Dada
uma permutação P = {p
1
, p
2
,..., p
i-1
, p
i
, p
i+1
,..., p
j
,..., p
n-1
, p
n
} de cidades, a vizinhança
de P é definida por:
1. {p
1
, p
2
,..., p
i-1
, p
j
, p
i+1
,..., p
i
,..., p
n-1
, p
n
}, para i = 1.. n-1 e j = i+1 .. n;
2. {p
1
, p
2
,..., p
i-1
, p
i+1
,..., p
j
, p
i
,..., p
n-1
, p
n
}, para todo i = 1.. n-1 e j = i+1 .. n;
Para cada uma dessas vizinhanças foram testados os métodos de “melhoria
iterativa” e “descida mais rápida” [40].
55
Capítulo 5
Algoritmo Memético e Vocabulary Building
5.1 Introdução
Como já foi dito anteriormente, o Vocabulary Building (VB) é uma instância do Path
Relinking (PR). Sendo este último um método evolucionário, tem-se que o
Vocabulary Building deve atuar sobre uma população de soluções. Caso a
população utilizada não sofra modificações periódicas (além das causadas pelo VB),
o conjunto de soluções rapidamente converge para um ponto do espaço de busca
cuja qualidade não é muito alta. Para se chegar a essa conclusão, observou-se o
processo de busca do algoritmo VB com contração de vértices em uma
implementação onde uma população “estática” era utilizada. Para evitar a
convergência prematura do algoritmo para um ótimo local, seria necessária a
utilização de técnicas que promovessem a diversificação.
Na literatura, o Algoritmo Memético tem se mostrado um dos mais eficazes métodos
evolucionários encontrados para a resolução de problemas de otimização
combinatória. Essa é uma técnica cuja flexibilidade permite a inserção de novos
elementos no processo de busca. Além disso, o Memético fornece uma população
que se modifica ao longo das iterações. Essas modificações são feitas no sentido de
se obter soluções cada vez melhores. Assim, as populações encontradas durante a
busca do Memético podem sem exploradas pelos procedimentos de Vocabulary
Building apresentados. O problema da convergência prematura do Vocabulary
Building é resolvido pela constante atualização da população pelos operadores que
fazem parte do Algoritmo Memético. Nos próximos tópicos, serão mostradas de que
maneiras as duas formas de VB foram introduzidas no Algoritmo Memético.
5.2 O pool de vocábulos no Algoritmo Memético
Existe uma cooperação entre o pool de vocábulos e o Algoritmo Memético, no
sentido de que o pool busca melhorar a população e a população fornece elementos
56
que permite a melhora e diversificação do pool, o que consequentemente permite a
diversificação da população (a convergência iterativa da população de soluções é
aproveitada pelo VB para atualizar o pool de vocábulos).
No presente trabalho, o processo de introdução do pool de vocábulos na população
de agentes é feito antes do laço de formação da nova população. Modificando o
Algoritmo Memético mostrado no capítulo anterior, temos o seguinte pseudocódigo:
Figura 16. Estrutura do Algoritmo Memético com VB utilizando pool de vocábulos.
- Inicio
Gerar população inicial;
Otimizar população (realizar busca local);
Avaliar População;
Enquanto (não atender as condições de parada) Fazer
Elitismo;
Para (cada agente do conjunto elite) Fazer
Aplicar o pool de vocábulos;
Otimizar agente (realizar busca local);
Fim Para
Elitismo;
Nova População =Ø;
Enquanto (Nova População não estiver completa) Fazer
Selecionar os pais;
Aplicar operadores de recombinação e mutação;
Inserir descendentes na Nova População;
Fim enquanto
Otimizar população (realizar busca local);
Avaliar Nova População;
População Atual = Nova População;
Fim enquanto
- Fim
57
5.3 Vocabulary Building usando contração de vértices no
Algoritmo Memético
A técnica de VB com contração de vértices utilizada no presente trabalho é inspirada
nas heurísticas apresentadas em [44] e [23]. Além disso, também é inspirada na
idéia de múltiplas soluções–guia, apresentado em [15] no contexto de Path
Relinking.
Em seguida é mostrado o pseudocódigo do Algoritmo Memético com VB usando
contração de vértices:
Figura 17. Algoritmo Memético com VB usando Contração de Vértices
- Inicio
Gerar população inicial;
Otimizar população (realizar busca local);
Avaliar População;
Para (iteração de 1 ate número de iterações) Fazer
Enquanto (não atender as condições de parada) Fazer
Elitismo;
Nova População =Ø;
Enquanto (Nova População não estiver completa) Fazer
Selecionar os pais;
Aplicar operadores de recombinação e mutação;
Inserir descendentes na Nova População;
Fim enquanto
Otimizar população (realizar busca local);
Avaliar Nova População;
População Atual = Nova População;
Fim enquanto
Construir e montar vocábulos;
Fim Para
-
Fim
58
Nos dois primeiros trabalhos citados acima, utiliza-se a solução do problema da
alocação linear para definir quais seqüências de vértices serão contraídas. O
procedimento aqui proposto utiliza regras diferentes para fazer essa seleção:
utilizam-se soluções geradas por diversas heurísticas, as quais “votam” em que
arestas devem ser contraídas; uma solução “vota” nas arestas que a compõem.
5.4 Vocabulary Building usando contração de vértices e
Pool de Vocábulos no Algoritmo Memético
Tendo sido mostradas anteriormente as interações do Algoritmo Memético com cada
uma das técnicas propostas, este tópico cobrirá o Algoritmo Memético em que são
utilizadas ambas as técnicas ao mesmo tempo. Com base nos resultados
computacionais apresentados posteriormente, pode-se perceber que há uma
sinergia entre os dois métodos propostos. Segue o pseudocódigo:
59
Figura 18. Algoritmo Memético com VB usando Contração de vértices e pool de vocábulos.
- Inicio
Gerar população inicial;
Otimizar população (realizar busca local);
Avaliar População;
Para (iteração de 1 ate número de iterações) Fazer
Enquanto (não atender as condições de parada) Fazer
Elitismo;
Para (cada agente do conjunto elite) Fazer
Aplicar o pool de vocábulos;
Otimizar agente (realizar busca local);
Fim Para
Elitismo;
Nova População =Ø;
Enquanto (Nova População não estiver completa) Fazer
Selecionar os pais;
Aplicar operadores de recombinação e mutação;
Inserir descendentes na Nova População;
Fim enquanto
Otimizar população (realizar busca local);
Avaliar Nova População;
População Atual = Nova População;
Fim enquanto
Construir e montar vocábulos;
Fim Para
- Fim
60
Capítulo 6
Resultados Computacionais
Um dos principais problemas da Otimização Combinatória é o Problema do Caixeiro
Viajante. O PCV tem sido vastamente utilizado em testes computacionais de novas
estratégias de otimização, sendo considerado um “benchmark”. Isso se dá, devido à
sua complexidade, facilidade de implementação e aplicabilidade.
Devido às limitações encontradas pelas heurísticas na resolução de problemas de
complexidade NP – Difícil como o PCV, as pesquisas têm sido direcionadas ao
estudo das Metaheurísticas com o objetivo de sua performance. Neste trabalho o
enfoque foi dado à Metaheurística Algoritmo Memético que também é conhecido
como, Algoritmo Memético Híbrido.
Neste capitulo serão apresentados os resultados obtidos com a implementação do
Vocabulary Building, do Algoritmo Memético e do Algoritmo Memético com
vocabulary Building nas suas duas formas. Foram feitos testes nas 27 instâncias
assimétricas do TSPLIB, que foram escolhidas devido à sua complexidade, e por
serem menos utilizadas em testes de novas heurísticas. Foram feitas 20 execuções
e 1000 iterações para cada uma delas. A TSPLIB tem sido utilizada como parâmetro
para comparar os testes realizados com o PCV. Cada uma das instâncias
representa um problema real cuja solução ótima é conhecida. Por exemplo, a
instância Br17 diz respeito à um problema com uma rota de 17 cidades.
As heurísticas foram implementadas na linguagem C++. Os testes foram realizados
em uma máquina Pentium IV 1.4 GHz e 128Mb de RAM.
A tabela 2, a seguir demonstra os resultados obtidos com a implementação da
técnica de Vocabulary Building em todas as instâncias assimétricas da TSPLIB – O
método utilizado encontra-se no Capítulo 3.
61
Pode-se perceber, pelos resultados contidos na tabela abaixo, que a heurística
Vocabulary Building pode não ser uma boa estratégia quando utilizada fora do
contexto de uma Metaheurística. Para as menores e maiores instâncias ela
conseguiu chegar à solução ótima em todas as execuções, mas para as instâncias
de médio porte ela não conseguiu obter o mesmo resultado. Este aspecto
encontrado pela implementação do VB pode se tornar objeto de estudos futuros.
Instância
Gap
Inicial Ótimo/Tentativas
Gap(%)
Tempo Médio de
CPU
Tempo médio para o
Ótimo
br17
0,000 20 0,000 0,000 0,000
ftv33
2,799 20 0,000 1,000 1,000
ftv35
1,358 6 0,407 3,000 0,000
ftv38
1,307 0 0,588 4,000 -
p43
0,125 0 0,125 1,000 -
ftv44
3,182 0 1,137 5,000 -
ftv47
0,450 0 0,375 6,000 -
ry48p
1,317 0 1,317 3,000 -
ft53
5,214 0 3,481 6,000 -
ftv55
2,923 0 1,907 8,000 -
ftv64
2,991 0 1,613 10,000 -
ft70
1,464 0 1,464 22,000 -
ftv70
3,043 0 1,744 12,000 -
ftv90
2,343 0 0,528 24,000 -
ftv100
1,808 0 1,603 29,000 -
ftv110
2,656 0 2,656 41,000 -
ftv120
4,663 0 3,616 44,000 -
kro124p
4,330 0 1,746 59,000 -
ftv130
3,078 0 3,078 51,000 -
ftv140
2,231 0 2,231 65,000 -
ftv150
2,068 0 2,068 78,000 -
ftv160
0,596 0 0,596 86,000 -
ftv170
0,944 0 0,944 111,000 -
rbg323
0,000 20 0,000 3,000 3,000
rbg358
0,000 20 0,000 2,000 2,000
rbg403
0,000 20 0,000 5,000 5,000
rbg443
0,000 20 0,000 7,000 7,000
Média
1,885 4,667 1,231 25,407 2,571
Tabela 2. Resultados obtidos com a implementação do Vocabulary Building.
A tabela 3 abaixo apresenta os resultados obtidos com a implementação realizada
neste trabalho do Algoritmo Memético Clássico. Os testes mostraram que somente o
Algoritmo Memético Clássico não apresentaram bons resultados para as instâncias
assimétricas. Assim como o Vocabulary Building, o Memético puro conseguiu chegar
ao ótimo em todas as execuções realizadas nas pequenas instâncias, como o br17,
62
e nas maiores como rbg323, rbg358, rbg403 e rbg443. Mas para as instâncias de
médio porte o ótimo não foi alcançado em nenhuma das 20 execuções.
Instância
Gap
Inicial Ótimo/Tentativas
Gap(%)
Tempo Médio de
CPU
Tempo médio para o
Ótimo
br17
0,000 20 0,000 0,000 0,000
ftv33
6,675 0 6,675 13,000 -
ftv35
0,928 0 0,928 14,000 -
ftv38
1,307 0 1,307 15,000 -
p43
0,113 0 0,113 17,000 -
ftv44
3,906 0 3,906 19,000 -
ftv47
0,619 0 0,619 20,000 -
ry48p
1,858 0 1,858 21,000 -
ft53
9,269 0 9,269 12,000 -
ftv55
2,923 0 2,923 25,000 -
ftv64
2,991 0 2,991 32,000 -
ft70
1,464 0 1,464 39,000 -
ftv70
3,385 0 3,385 37,000 -
ftv90
2,343 0 2,343 56,000 -
ftv100
2,069 0 2,032 66,000 -
ftv110
2,656 0 2,656 79,000 -
ftv120
5,125 0 5,125 93,000 -
kro124p
4,840 0 4,319 69,000 -
ftv130
3,078 0 3,078 108,000 -
ftv140
2,231 0 2,231 122,000 -
ftv150
2,068 0 2,068 39,000 -
ftv160
0,596 0 0,596 155,000 -
ftv170
0,944 0 0,944 177,000 -
rbg323
0,000 20 0,000 3,000 3,000
rbg358
0,000 20 0,000 2,000 2,000
rbg403
0,000 20 0,000 5,000 5,000
rbg443
0,000 20 0,000 7,000 7,000
Média
2,274 3,704 2,253 46,111 3,400
Tabela 3. Resultados obtidos com a implementação do Algoritmo Memético Clássico.
A tabela 4 mostra os resultados computacionais realizados com o Vocabulary
Building por contração de vértices introduzido na Metaheurística Algoritmo
Memético. Em somente uma das instâncias o ótimo não foi alcançado a instância
ft70. Esta estratégia de implementação obteve os melhores resultados conseguidos
nesta pesquisa. Para todas as instâncias a média de execuções em que o ótimo foi
alcançado é de 15,630 e ficando a uma média de somente 0,066% do ótimo,
devendo ser considerada também a distância entre esta média e a media obtida pela
população inicial que é de 1,814%. Nas menores e maiores instâncias o ótimo foi
alcançado em todas as execuções realizadas.
63
Instância
Gap
Inicial Ótimo/Tentativas
Gap(%)
Tempo Médio de
CPU
Tempo médio para o
Ótimo
br17
0,000
20 0,000
0,000 0,000
ftv33
1,555
20 0,000
0,500 0,500
ftv35
1,107
16 0,027
120,300 88,938
ftv38
1,275
14 0,039
173,650 133,000
p43
0,155
19 0,001
118,650 107,632
ftv44
3,506
14 0,186
225,050 176,143
ftv47
0,532
20 0,000
10,500 10,500
ry48p
1,680
10 0,282
160,850 32,000
ft53
4,713
20 0,000
36,350 36,350
ftv55
2,758
20 0,000
40,500 40,500
ftv64
2,887
20 0,000
104,200 104,200
ft70
1,464
0 0,616
742,750 -
ftv70
2,933
19 0,010
149,800 128,684
ftv90
2,153
17 0,057
180,200 93,647
ftv100
2,019
16 0,067
266,850 138,188
ftv110
2,656
18 0,020
389,950 317,000
ftv120
4,995
13 0,083
765,100 529,077
kro124p
3,684
2 0,136
647,450 211,500
ftv130
3,078
12 0,056
787,400 435,667
ftv140
2,231
11 0,062
1074,600 738,727
ftv150
2,068
7 0,067
1440,750 876,000
ftv160
0,596
18 0,015
380,500 227,500
ftv170
0,935
16 0,056
1325,000 1079,563
rbg323
0,000
20 0,000
3,000 3,000
rbg358
0,000
20 0,000
2,000 2,000
rbg403
0,000
20 0,000
5,000 5,000
rbg443
0,000
20 0,000
7,000 7,000
Média
1,814
15,630 0,066
339,181
212,397
Tabela 4. Resultados obtidos com a implementação do Algoritmo Memético com Vocabulary Building por
contração de vértices.
Na última tabela apresentada neste capítulo são mostrados os resultados obtidos
com introdução do Vocabulary Building por pool de vocábulos no Algoritmo
Memético. Diferente dos resultados mostrados anteriormente com a contração de
vértices, em apenas algumas instâncias o ótimo foi alcançado. Com a média de
aproximação do ótimo em 1,623%. A média de obtenção do ótimo caiu de 15,630
execuções onde o ótimo foi obtido para 3,741%. Mas mesmo esses piores
resultados se comparados ao Algoritmo Memético clássico mostram que a
estratégias de Vocabulary Building utilizadas aqui são mais competitivas.
64
Instância
Gap
Inicial Ótimo/Tentativas
Gap(%)
Tempo Médio
de CPU
Tempo médio para
o Ótimo
br17
0,000 20 0,000 0,000 0,000
ftv33
2,644 1 2,644 110,000 0,000
ftv35
1,290 0 0,950 170,000 -
ftv38
1,307 0 1,307 180,000 -
p43
0,107 0 0,107 190,000 -
ftv44
4,133 0 3,410 200,000 -
ftv47
0,619 0 0,619 210,000 -
ry48p
1,394 0 0,950 215,000 -
ft53
7,280 0 4,451 230,000 -
ftv55
2,923 0 2,923 240,000 -
ftv64
2,991 0 2,991 275,000 -
ft70
1,464 0 1,464 300,000 -
ftv70
3,385 0 2,000 305,000 -
ftv90
2,343 0 1,900 395,000 -
ftv100
2,069 0 1,678 450,000 -
ftv110
2,656 0 2,656 500,000 -
ftv120
5,125 0 2,401 550,000 -
kro124p
4,101 0 2,709 441,000 -
ftv130
3,078 0 3,078 605,000 -
ftv140
2,231 0 2,231 685,000 -
ftv150
2,068 0 2,068 740,000 -
ftv160
0,596 0 0,335 830,000 -
ftv170
0,944 0 0,944 870,000 -
rbg323
0,000 20 0,000 3,000 3,000
rbg358
0,000 20 0,000 2,000 2,000
rbg403
0,000 20 0,000 5,000 5,000
rbg443
0,000 20 0,000 7,000 7,000
Média
2,028 3,741 1,623 322,519 2,833
Tabela 5. Resultados obtidos com a implementação do Algoritmo Memético com Vocabulary Building por
pool de vocábulos.
65
Capítulo 7
Conclusão, Principais Contribuições e
Trabalhos Futuros
7.1 Conclusão
Diversas estratégias metaheurísticas têm sido desenvolvidas e aplicadas ao
Problema do Caixeiro Viajante (PCV), por se tratar de um dos principais modelos de
problemas NP – difícil encontrado na literatura. Diversos pesquisadores utilizam este
problema para comprovar a eficiência e testar novos algoritmos.
O Vocabulary Building foi desenvolvido por Fred Glover em 1992 em [20]. No ano de
1995 ele usou este termo, em [17] e [18], para descrever um método de construção
de solução em Busca Tabu, técnica que descende do Scatter search. Em 1995 em
[30] e [33] para resolver problemas de roteamento de veículos. Esta técnica tornou a
busca local mais robusta, pois converge para uma solução mais próxima da melhor
solução conhecida.
O objetivo principal dessa dissertação é explorar o conceito de Vocabulary Building e
introduzi-lo em algoritmos populacionais, neste caso, o Algoritmo Memético.
Segundo o próprio Fred Glover, em comunicação privada, esta técnica não foi ainda
muito explorada pelos pesquisadores da área de otimização. Foram feitos testes nas
27 instâncias assimétricas da TSP-LIB.
Foram realizados testes no Vocabulary Building (pool de vocábulos), no Algoritmo
Memético puro e no Algoritmo Memético com Vocabulary Building em suas duas
formas apresentadas, pool de vocábulos e contração de vértices.
Estes resultados comprovam que o Vocabulary Building, quando introduzido nos
Algoritmos Meméticos conseguem obter resultados consideravelmente melhores do
66
que os obtidos pelo Memético clássico. Mesmo os piores resultados obtidos pelo VB
são consideravelmente melhores do que os resultados obtidos com o AM.
7.2 Principais Contribuições
O Vocabulary Building, se mostrou ser uma técnica bastante competitiva em relação
às demais e que pode ser implementada em diversas outras estratégias de
otimização combinatória. Como o VB ainda não havia sido amplamente explorado
em trabalhos anteriores, a principal contribuição dessa dissertação é o estudo sobre
este tema. Até então, o VB havia sido mostrado apenas como uma idéia. Aqui foram
apresentadas duas formas de implementação do BV o que não havia sido publicado
ainda.
Dessa forma o presente trabalho trouxe inúmeras contribuições ao estudo do
Algoritmo Memético e do Vocabulary Building principalmente.
7.3 Trabalhos Futuros
O Vocabulary Building se mostrou bastante eficiente quando introduzido o Algoritmo
Memético para a resolução do Problema do Caixeiro Viajante por isso sua eficiência
pode ser testada para outras heurísticas que se utilizam de um conjunto de
soluções, como as heurísticas populacionais e os métodos evolucionários.
Outras implementações podem ser feitas ainda com base no trabalho apresentado
nesta dissertação com o objetivo de melhorar ainda mais seus resultados, visto que
as estruturas aqui apresentadas são extremamente simples.
1. Novas estratégias de busca local;
2. Utilizar novos métodos construtivos na construção da população inicial e para
a construção da população do Vocabulary Building;
3. Utilizar métodos para estruturar a população de forma que esta forneça
melhores indivíduos do que montada de forma aleatória;
4. Implementar formas de manutenção da diversificação;
67
5. Incluir estratégias de inserção de novos vocábulos no pool de vocábulos,
como por exemplo, montar uma lista ou utilizar uma lista Tabu de arestas
68
Referências bibliográficas
[1] AMIN, S. “Simulated Jumping.” Annals of Operations Research 86, 23-38.
(1999)..
[2] AVILA, Sergio, et al. Otimização: conceitos básicos, ferramentas e aplicações.
Florianópolis, Brasil.
[3] BURIOL, L S "A New Memetic Algorithm for the Asymmetric Traveling Salesman
Problem", Paulo M. França and Pablo Moscato. Journal of Heuristics, vol. 10:5, pgs.
483-506, 2005.
[4] CUNHA, C. B., et al. Uma contribuição para o problema de roteirização de
veículos com restrições operacionais. São Paulo: EPUSP, Departamento de
Engenharia de Transportes. 22p. (Tese de Doutoramento).
[5] CUNHA, C. B., et al. EXPERIMENTOS COMPUTACIONAIS COM
HEURISTICAS DE MELHORIAS PARA O PROBLEMA DO CAIEXEIRO
VIAJANTE. Trabalho apresentado no XVI Congresso da Anpet – Associação
Nacional de Pesquisa e Ensino em Transportes. Publicado nos anais do
evento. Natal, outubro de 2002.
[6] DAWKINS, R. The Selfish Gene. Oxford: Oxford University Press, 1976.
[7] DORIGO, M. & CARO, G. DI - The Ant Colony Optimization Meta-Heuristic. In D.
Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization,
McGraw-Hill, p.11-32. (1999).
[8] DORIGO, M. - Optimization, Learning and Natural Algorithms. Ph.D.Thesis,
Politecnico di Milano Italy. (1992).
[9] FEO, T, RESENDE, M. "A greed randomized adaptative search procedure for
maximum independent set." Operations Research 42, 860-879. (1994)..
[10] FIECHTER, C. N. “A Parallel Tabu Search Algorithm for Large Traveling
Salesman Problems.” Discrete Applied Mathematics 51, 243-267. (1994).
[11] GEORGE B. et al. Solution of a large-scale traveling-salesman problem. Operations
Research, 2:393*410, 1954..
[12] GLOVER, F., LAGUNA, M. Tabu Search, chapter in Modern Heuristic
Techniques for Combinatorial Problems, C. Reeves, ed., Blackwell Scientific
Publishing, 1993, pp. 71-140.
69
[13] GLOVER, F. e M. LAGUNA. "Tabu Search". Colin Reeves (ed.), em Modern
Heuristic Techniques. Blackwell Scientific Publications, Oxford, Blackwell,
70-150. (1993).
[14] GLOVER, F. "Heuristics for Integer Programming Using Surrogate Constraints."
Decision Sciences 8 (1), 156-166. (1977)..
[15] GLOVER, F. M. LAGUNA and R. MARTI. Fundamentals of Scatter Search and
Path Relinking Control and Cybernetics, vol. 39, no. 3 pp. 653-684 (2000)
[16] GLOVER, F. "Surrogate Constraints," Operations Research, Vol. 16, No. 4,
(July-August 1968), 741-749.
[17] GLOVER, F. Tabu Search and Adaptive Memory Programming - Advances,
Applications and Challenges," in Interfaces in Computer Science and
Operations Research, Barr, Helgason and Kennington (eds.) Kluwer
Academic Publishers, pp. 1-75. 1996.
[18] GLOVER, F. Ejection Chains, Reference Structures and Alternating Path
Methods for Traveling Salesman Problems," Discrete Applied Mathematics,
65, 223-253, 1996.
[19] GLOVER F. (comunicação pessoal privada).
[20] GLOVER F. "New Ejection Chain and Alternating Path Methods for Traveling
Salesman Problems," Computer Science and Operations Research, pp. 449-
509, 1992.
[21] GLOVER, F. M. Laguna, Tabu Search, Hardcover, 1998.
[22] GLOVER, F. “PARAMETRIC COMBINATIONSN OF LOCAL JOB SHOP
RULES,” CHAPTER IV, on Reaserch Memorandum no. 117 GSIA Carnegie
Melon university, pittsburg, 1963, PA
[23] GLOVER, F; G. GUTIN, A. YEO, and A. ZVEROVICH."Construction Heuristics
for the Asymmetric TSP," European Journal of Operational Research,
volume 129, pp. 555-568, 2001 (with G. Gutin, A. Yeo, and A. Zverovich).
[24] GOLDBERG, D. E. Genetic Algorithms in Search, Optimization, and Machine
Learning. (1989)..
[25] GRACIOLLI, Odacir D. Otimização de Roteiros de Veículos Coletores de
Resíduos Sólidos de Serviços de Saúde. Dissertação de Mestrado. Curso
de Pós-Graduação em Engenharia de Produção.Universidade Federal de
Santa Catarina, Florianópolis, SC. 1994;
70
[26] HELSGAUN, K. An effective implementation of the Lin-Kernigham Traveling
Salesman Heuristic, European Journal of Operational Research, 2000,
v.126, p.106-130.
[27] HOLLAND, J. H. Adaptation in Natural and Artificial Systems. Ann
Arbor:University of Michigan Press, 1975.
[28] KARP, R. M. "Probabilistic Analysis of Partitioning Algorithms for the Traveling
Salesman Problem in the Plane." Math. Operational Research 2, 209-224.
(1977)..
[29] KARP, R. M"A Patching Algorithm for the Nonsymmetric Traveling Salesman
Problem." SIAM J. Comput. 8, 561-573. (1979)..
[30] KELLY, J.P. and J. Xu "Tabu Search and Vocabulary Building for Routing
Problems," Graduate School of Business Administration, University of
Colorado at Boulder. (1995).
[31] KIRKPATRICK, S, GELLAT, D.C., and VECCHI, M.P. “Optimization by
Simulated Annealing”. Science, 220:671_680, 1983.
[32] LAGUNA M. In Handbook of Applied Optimization, P. M. Pardalos and M. G. C.
Resende (Eds.), Oxford University Press, pp. 183-193. (2002).
[33] LOPEZ, L., M.W. Carter and M. Gendreau "The Hot Strip Mill Production
Scheduling Problem: A Tabu Search Approach," Centre de recherche sur les
transports, Université de Montréal. (1996).
[34] MOSCATO, P. “On Evolution, Search, Optimization, Genetic Algorithms, and
Martial Arts: Towards Memetic Algorithms.” Technical Report, Caltech
Concurrent Computation Program, C3P Report 826. (1989).
[35] MOSCATO, P. and Norman, M. G. “A Memetic Approach for the Traveling
Salesman Problem Implementation of a Computational Ecology for
Combinatorial Optimization on Message-Passing Systems,” in Parallel
Computing and Transputer Applications, (M. Valero, E. Onate, M. Jane, J. L.
Larriba, and B. Suarez, eds.), (Amsterdam), pp. 177–186, IOS Press, 1992.
[36] POTVIN, J. Y. “The Traveling Salesman Problem: A Neural Network
Perspective.” ORSA Journal on Computing 5, 328-348. (1993).
[37] PROJETO ISIS, disponível em: http://www.geocities.com/igoryepes/ .
[38] RECHEMBERG, I. “Evolution strategy: Optimization of technical systems by
means of biological evolution”, Fromman-Holzboog, Stuttgart, 1973.
71
[39] ROCHAT, Y. and E. Taillard "Probabilistic Diversification and Intensification in
Local Search for Vehicle Routing," Journal of Heuristics, Vol. 1, No. 1,
147-167. (1995)..
[40] RIBEIRO, C. C. Metaheurísticas. Rio de Janeiro: Escola Brasileira de
Computação, 1998. (Notas de aula).
[41] SCHWEFEL, H.P. “Numerical optimization of Computer models”, John Wiley &
Sons Ltd., Chichester, 1981.
[42] SCHNEIDER, André M. Algoritmo Adaptativo Genético para companhamento
da Trajetória de Alvos Móveis. - Dissertação de Mestrado - Porto
Alegre: Instituto de Informática - Universidade Federal do rio Grande do
Sul, 1998.
[43] STÜTZLE, T. e M. Dorigo. “ACO Algorithms for the Traveling Salesman
Problem.” To appear in K. Miettinen, M. Mäkelä, P. Neittaanmäki e J.
Periaux, (eds), Evolutionary Algorithms in Engineering and Computer
Science: Recent Advances in Genetic Algorithms, Evolution Strategies,
Evolutionary Programming, Genetic Programming and Industrial
Applications, John Wiley & Sons. (1999).
[44] YEO A. Large exponential neighbourhoods for the TSP, Preprint, Department of
Maths and CS, Odense University, Odense, Denmark, 1997.
72
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
