Caixeiro Viajante - Solução Utilizando a Heurística de Colônia de Formigas (Java)

Prévia do material em texto

Problemas Clássicos da 
Computação: Caixeiro Viajante 
(TSP)
Uma solução baseada na heurística da Colônia de Formigas (AC)
João Paulo de Menezes
Rodrigo de Deus Almeida
Sumário
• Introdução
• Heurística: Colônia de Formigas
• Desafios
• Metodologia
• Problemas
• Resultados e Conclusões
• Referências
PCC– João P. Menezes – Rodrigo D. Almeida 2
Introdução
Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, 
iniciando e encerrando sua viagem na ultima cidade*. Suponha, também, 
que não importa a ordem com que as cidades são visitadas e que de cada uma 
delas pode-se ir diretamente a qualquer outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna 
mínima a viagem total.
*Normalmente o problema consiste em terminar a viajem na cidade inicial
PCC– João P. Menezes – Rodrigo D. Almeida 3
Introdução
O problema do caixeiro é um clássico exemplo de problema de 
otimização combinatória. A primeira coisa que podemos pensar para resolver 
esse tipo de problema é reduzi-lo a um problema de enumeração: achamos 
todas as rotas possíveis e, usando um computador, calculamos o comprimento 
de cada uma delas e então vemos qual a menor. Porém, mesmo com o poder 
de processamentos dos computadores modernos, o custo computacional para 
enumerar todas as possíveis combinações segue uma ordem de proporção 
(n-1)!, ou seja, para um grafo de 25 cidades, serão necessários 1.15x1025 
de operações, logo o tempo necessário para processamento total seria de 470 
milhões de anos*.
* Considerando que o computador consiga realizar 42 milhões de operações por segundo. 
PCC– João P. Menezes – Rodrigo D. Almeida 4
Introdução
Na computação, quando problemas dessa categoria são apresentados, 
normalmente a solução é dada por meio de uma heurística, que é um grupo 
de estratégias de algoritmo que possuem as características:
• Um tempo de execução aceitável.
• Trazer a solução ótima ou provavelmente boa para o problema em todos os 
casos.
Existem diversas heurísticas capazes de trazer uma resposta relativamente 
boa para o caixeiro viajante, mas a que será tratada neste trabalho é a Colônia 
de Formigas.
PCC– João P. Menezes – Rodrigo D. Almeida 5
Heurísticas: Colônia de Formigas
• Colônia de formigas é uma heurística baseada em população e inspirada no 
comportamento forrageiro das formigas.
• Muitas espécies de formigas são quase cegas.
• A comunicação entre as formigas é realizada através de uma substância 
química denominada de feromônio.
• Em algumas espécies, o feromônio é usado para criar caminhos (trilhas de 
formigas).
PCC– João P. Menezes – Rodrigo D. Almeida 6
Heurísticas: Colônia de Formigas
PCC– João P. Menezes – Rodrigo D. Almeida 7
a) b)
c)
Heurísticas: Colônia de Formigas
• Ao caminhar, as formigas depositam no chão o feromônio, formando, deste 
modo, uma trilha de feromônios. 
• As formigas sentem o cheiro do feromônio, e quando elas têm que escolher 
um caminho, escolhem, com maior probabilidade, o caminho com maior 
quantidade de feromônio (cheiro mais forte).
• A trilha ajuda a formiga a achar o caminho de volta e as outras formigas a 
encontrar a fonte de alimentos.
PCC– João P. Menezes – Rodrigo D. Almeida 8
Heurísticas: Colônia de Formigas
• Ao caminhar, as formigas depositam no chão o feromônio, formando, deste 
modo, uma trilha de feromônios. 
• As formigas sentem o cheiro do feromônio, e quando elas têm que escolher 
um caminho, escolhem, com maior probabilidade, o caminho com maior 
quantidade de feromônio (cheiro mais forte).
PCC– João P. Menezes – Rodrigo D. Almeida 9
Heurísticas: Colônia de Formigas
• O Algoritmo trabalha em duas etapas: Descobrimento e Refinamento.
• Na etapa de Descobrimento, um número R de formigas são introduzidas no 
grafo. A rota descoberta por essa formiga é construída de forma totalmente 
aleatória.
• Na etapa de Refinamento, um número F de formigas são introduzidas no 
grafo por T vezes. A rota descoberta por essa formiga é construída baseada 
em uma função de peso para cada aresta selecionada.
• Ao final da execução, é retornado o caminho de menor custo encontrado.
PCC– João P. Menezes – Rodrigo D. Almeida 10
Heurísticas: Colônia de Formigas
• Sempre que uma formiga atravessa uma aresta, seu valor de feromônio é 
aumentada proporcionalmente a uma taxa definida.
• A toda rodada T de colônias de F formigas, a quantidade de feromônio é 
reduzida proporcionalmente a uma taxa definida.
PCC– João P. Menezes – Rodrigo D. Almeida 11
Desafios
• Encontrar uma relação funcional entre o Grafo e valores de R, F, T, α e β;
• Encontrar um bom valor de taxa de depósito e evaporação de feromônio nas 
arestas.
• Definir uma função equilibrada de seleção de arestas por formigas, de modo 
que evite uma convergência precoce e que permita uma descoberta mais 
ampla das possibilidades de caminho.
• “Harmonia dos parâmetros”.
R: Quantidade de formigas na primeira etapa (Descobrimento)
F: Quantidade de formigas na segunda etapa (Refinamento)
T: Quantidade de iterações da segunda etapa (Tempo)
PCC– João P. Menezes – Rodrigo D. Almeida 12
Metodologia
• A estratégia de implementação deste trabalho foi inspirada nos trabalhos 
realizado por FERREIRA (2008) e LACERDA (2008), nos quais optamos por 
utilizar parte de suas metodologias e adaptar parte do algoritmo para a 
variação do PCV que estamos trabalhando.
• A linguagem utilizada foi o Java (JDK 1.8).
PCC– João P. Menezes – Rodrigo D. Almeida 13
Metodologia
PCC– João P. Menezes – Rodrigo D. Almeida 14
DC das classes abstratas Formiga e Caminho
Metodologia
• A primeira etapa do algoritmo foi definida da seguinte forma:
para r = 1 até R
Cria uma nova formiga r (incio,fim)
enquanto a formiga r não construir completar o caminho
selecionaAProximaCidadeAleatoriamente
fim enquanto
se Lr < L* então
C* = Cr
reconpensaCaminho(Cr) * = Melhor caminho
senao L = Custo do Caminho
atualizeFeromonio(Cr)
fim senão C = Caminho
fim para
PCC– João P. Menezes – Rodrigo D. Almeida 15
Metodologia
A seleção da próxima cidade aleatória foi feita de seguinte forma:
numCidades → numCidadesRestantes
indiceDaProximaCidade → random(1..numCidades)
proximaCidade → buscaCidadePorIndice(indiceDaProximaCidade)
insereCaminho(buscaAresta(atual, proximaCidade))
atual → proximaCidade
removeRestantes(proximaCidade)
insereVisitados(proximaCidade)
De forma que random retorne um número aleatório de distribuição uniforme
PCC– João P. Menezes – Rodrigo D. Almeida 16
Metodologia
A segunda etapa do algoritmo foi definida da seguinte forma:
para t = 1 até T
para f = 1 até F
Cria uma nova formiga f (incio,fim)
enquanto a formiga r não construir completar o caminho
selecionaAProximaCidade
fim enquanto
se Lf < L* então
C* = Cf
reconpensaCaminho(Cf)
senão
AtualizeOsferomonios(Cf)
fim para
evaporaFeromonio()
fim para
PCC– João P. Menezes – Rodrigo D. Almeida 17
Metodologia: Atualização de Feromônio
• No feromônio τij associado a aresta (i,j) ocorre três eventos: 
1. A evaporação: Evita que o feromônio acumulado cresça indefinidamente e 
permite esquecer pobres decisões do passado da busca. 
2. O depósito de feromônio de todas as formigas que passaram sobre (i,j).
3. O bônus de feromônio depositado nas arestas pertencentes ao caminho 
que conseguiu “melhorar o melhor” caminho naquela instância. 
PCC– João P. Menezes – Rodrigo D. Almeida 18
Metodologia: Atualização de Feromônio
• A evaporação é definida como: 
τij = (1 – ρ) * τij
onde: 0 < ρ < 1 é a taxa de evaporação de feromônio.
PCC– João P. Menezes – Rodrigo D. Almeida 19
Metodologia: Atualização de Feromônio
• O depósito de feromônio é dadopor: 
τij = Q /Lf
onde: 
Q é uma constante (Taxa de depósito).
Lf = Custo total do caminho.
Foi observado no desenvolvimento do trabalho que:
Q α Custo das arestas do grafo
PCC– João P. Menezes – Rodrigo D. Almeida 20
Metodologia: Atualização de Feromônio
• O bônus de feromônio é dado por: 
τij = Q /Lf * B
onde: 
Q é uma constante (Taxa de depósito).
Lf = Custo total do caminho.
B é uma constante (Taxa de bonûs de feromônio).
PCC– João P. Menezes – Rodrigo D. Almeida 21
Metodologia: Escolha da Próxima Cidade
PCC– João P. Menezes – Rodrigo D. Almeida 22
1º Etapa
A
B
C
D
E
Caminho: A
Metodologia: Escolha da Próxima Cidade
PCC– João P. Menezes – Rodrigo D. Almeida 23
1º Etapa
A
B
C
D
E
Caminho: A - B
Metodologia: Escolha da Próxima Cidade
PCC– João P. Menezes – Rodrigo D. Almeida 24
1º Etapa
A
B
C D
E
Caminho: A – B - D
50%
Metodologia: Escolha da Próxima Cidade
PCC– João P. Menezes – Rodrigo D. Almeida 25
1º Etapa
A
B
C D
E
Caminho: A – B – D -C
Metodologia: Escolha da Próxima Cidade
PCC– João P. Menezes – Rodrigo D. Almeida 26
1º Etapa
A
B
C D
E
Caminho: A – B – D –C - E
Metodologia: Escolha da Próxima Cidade
PCC– João P. Menezes – Rodrigo D. Almeida 27
2º Etapa
A
B
C
D
E
?
Metodologia: Escolha da Próxima Cidade
• A probabilidade da formiga f que está na cidade i de escolher a cidade j é 
dada pela regra:
• onde:
• τij é feromônio associado a aresta (i,j); 
• α e β são parâmetros para determinar a influência do feromônio e da informação 
heurística; 
• Nk i é a vizinhança factível da formiga k (i.e., o conjunto das cidades ainda não 
visitadas pela formiga k).
PCC– João P. Menezes – Rodrigo D. Almeida 28
Metodologia: Escolha da próxima Cidade
• O valor ηij é inversamente proporcional a distância dij entre as cidades i e j:
• Em outras palavras, quanto maior a distância entre as cidades i e j, menor é a probabilidade 
dessa cidade ser escolhida.
PCC– João P. Menezes – Rodrigo D. Almeida 29
Metodologia: Escolha da próxima Cidade
O valor de Pkij é comparado a um valor aleatório R multiplicada por um fator de 
aceitação, onde 0 > R > 1:
SelecionaProximaCidade()
para j = 1 até cidadesRestantes
Calcule Pkij 
R → sorteio() * aceitação
se Pkij > R, então 
a cidade j é selecionada
retorno
fim se
fim para
aceitação → aceitação / A // Caso nenhuma cidade foi escolhida
PCC– João P. Menezes – Rodrigo D. Almeida 30
Metodologia: Escolha da próxima Cidade
• Aceitação: 
• Trata-se de um atributo de cada formiga, inicialmente definido, e que pode ter seu 
valor alterado caso nenhuma cidade seja escolhida durante um “escaneamento” das 
cidades vizinhas. 
• Sua função é aumentar as chances das arestas serem selecionada, reduzindo o número 
aleatório gerado, evitando um possível laço infinito caso nenhuma arestas possui Pkij 
menor que o número aleatório.
• A: Constante que representa a taxa da aceitação, sua função é aumentar as chances de Pkij 
ser maior que o número aleatório, reduzindo-o com um divisor. Sempre é utilizado no 
momento em que todas as arestas foram visitadas, mas nenhuma foi selecionada.
PCC– João P. Menezes – Rodrigo D. Almeida 31
Metodologia: Escolha da próxima Cidade
• Aceitação:
O valor inicial da aceitação deve ser proporcional ao número de arestas contidos no 
grafo para que haja uma melhor taxa de seleção de arestas, como representado no 
exemplo abaixo:
N = 100
PkA1 = (60 * 1/500) / (3)
PkA1 = 0,04
Ou seja, o valor de R deve ser < que 0,04 
para que a aresta A1 seja selecionada.
PCC– João P. Menezes – Rodrigo D. Almeida 32
C = 600 F = 11
Metodologia: Escolha da próxima Cidade
• Aceitação:
Quando a quantidade de arestas aumentam, a quantidade de feromônio total 
depositadas em todas as aresta também aumenta, interferindo no calculo de 
probabilidade de seleção de arestas.
N = 1000
PkA1 = (60 * 1/500) / (160)
PkA1 = 0,00075
O número de arestas é proporcional a 
quantidade de τ nos restantes das arestas 
tornando o número pequeno demais para ser 
selecionado com um R comum.
PCC– João P. Menezes – Rodrigo D. Almeida 33
C = 600 F = 11
Metodologia: Escolha da próxima Cidade
• Portanto com o sistema de redução do R por meio da variável aceitação funcionaria da 
seguinte forma:
• Um número decimal aleatório (0 < n < 1) seguindo um distribuição normal, terá o valor médio 
= 0,5, consideraremos que este valor será assumido em toda iteração.
• O multiplicador aceitação inicialmente terá o valor = 1.
• Logo, na primeira iteração, R = 0.5 * 1 = 0.5
• Para A1, 0,00075 > 0.5 é falso, portanto a aresta A1 não é selecionada.
• Caso nenhuma aresta seja selecionada nesta rodada, o valor da variável aceitação sofrerá 
redução por meio da taxa de redução A. (Considerando A = 10).
• A variável de aceitação assumira o valor de 1/10 = 0.1
• Desta forma, na segunda iteração, R = 0.5 * 0.1 = 0.05
• Mesmo com a redução do valor de R, a aresta A1 não será selecionada nessa iteração.
• Somente na iteração 3, na qual a aceitação será =0.001 poderá tornar o valor da P da aresta A1 
aceitável para a seleção (0,00075 > 0,0005). 
PCC– João P. Menezes – Rodrigo D. Almeida 34
Metodologia: Algoritmo A e Algoritmo B
• Um dos objetivos deste trabalho é implementar duas versões do algoritmo da colônia 
de formigas e realizar uma comparação estatística entre eles.
• A primeira versão denominada de algoritmo A é a versão tradicional do algoritmo, 
apresentada anteriormente.
• A segunda versão, denominada de algoritmo B é uma versão do algoritmo da colônia 
em que a seleção da cidade é feita pelo algoritmo da roleta viciada
PCC– João P. Menezes – Rodrigo D. Almeida 35
Metodologia: Algoritmo A e Algoritmo B
A1
40%
A2
5%
A3
5%
A4
10%
A5
20%
A6
20%
PCC– João P. Menezes – Rodrigo D. Almeida 36
0
2
4
6
8
10
12
A1 A2 A3 A4 A5 A6
Roleta Viciada: Exemplo
Metodologia: Algoritmo A e Algoritmo B
O valor de Pkij é somado com os valores de P
k das iterações anteriores, acumulando o valor na 
variável acumulo, que é comparada a um valor aleatório entre 0 e 1, se o acumulo for maior, a 
cidade j é selecionada: 
SelecionaProximaCidade()
R → random(0..1)
acumulo → 0
para j = 1 até cidadesRestantes
Calcule Pkij
acumulo → acumulo + Pkij
se acumulo > R, então 
a cidade j é selecionada
retorno
fim se
fim para
PCC– João P. Menezes – Rodrigo D. Almeida 37
Problemas
• O principal problema encontrado é justamente a definições das constantes G, B e A, 
taxas de crescimento e evaporação e proporção de R, F, T, α e β em relação ao grafo.
• Como o algoritmo de colônias de formigas possui um grande número de operações nas 
arestas do grafo, percebemos que esse algoritmo pode não tão eficientes com grafos 
que possuem um grande número de arestas, principalmente os grafos totalmente 
conectados, no qual a quantidade de arestas é igual a (N-1)2, onde N é igual ao numero 
de vértices no grafo.
PCC– João P. Menezes – Rodrigo D. Almeida 38
Problemas
Com um grande aumento na quantidade de arestas, o resultado do calculo da 
probabilidade da formiga f selecionar a cidade c torna cada vez menor, e mais trabalhoso 
de se tratar:
PCC– João P. Menezes – Rodrigo D. Almeida 39
?!??
Resultados e Conclusões
• Nesta sessão, iremos apresentar os resultados obtidos pelas duas versões do algoritmo em 
3 diferentes cenários: Um grafo de 50 vértices completos*, um grafo de 100 vértices 
completos** e um grafo de 200 vértices completos***.
• Será realizada uma comparação nos quesitos de custo e tempo de execução entre as duas 
versões do algoritmo.
• A máquinaque executou as instâncias do algoritmo possuía as seguintes configurações:
• Windows 10 64 bits
• Java build 1.8.0_65-b17
• Intel Core i5-3230M 2.60 GHz
• 6.0 GB de memória RAM
* Disponível em: https://goo.gl/enlK8a
** Disponível em: https://goo.gl/Lhup4i
*** Disponível em: https://goo.gl/rneJXF
PCC– João P. Menezes – Rodrigo D. Almeida 40
Resultados e Conclusões
Grafo de 50 vértices
• Parâmetros:
• α = 1
• Β = 2
• Taxa de Redução de Feromônio = 0.9
• Taxa de Bônus de Feronomio = 10
• Aceitação = 1
• A = 1.5
• N = numVertices * 100 = 50 * 100 = 5000
• F = numVertices * 1 = 50
• T = numVertices * 2 = 100
• Q = peso de uma aresta sorteada * numVertices
• Cidade inicial = 1
• Cidade final = 50
PCC– João P. Menezes – Rodrigo D. Almeida 41
50 Vértices - Custo
Algoritmo A Algoritmo B Diferença
3329,74 3285,9058 43,8342
3239,8071 3206,5024 33,3047
3442,649 3188,0059 254,6431
3442,649 3185,3755 257,2735
3239,8071 3159,57 80,2371
3239,8071 3241,056 -1,2489
3375,6985 3351,982 23,7165
3385,2966 3206,5024 178,7942
3206,5024 3351,982 -145,4796
3427,2634 3374,9062 52,3572
3233,6187 3426,6118 -192,9931
3479,2058 3445,5684 33,6374
3360,1423 3261,5059 98,6364
3233,6187 3262,7896 -29,1709
3239,8071 3321,4976 -81,6905
3268,7136 3353,385 -84,6714
3239,8071 3148,635 91,1721
3445,5684 3230,9766 214,5918
3239,8071 3188,0059 51,8012
3436,9868 3387,9766 49,0102
3239,8071 3319,3271 -79,52
Resultados e Conclusões
42
Custo Guloso: 4375.453
Resultados e Conclusões
43PCC– João P. Menezes – Rodrigo D. Almeida
Media 40,392
Desvio Padrão 120,674
Intervalo de Confiança 
(90%)
40,392 ± 42,13340087 =
-1,741...82,522
Custo – 50 Vértices
Podemos afirmar com 90% de confiança que os 2 algoritmos apresentam resultados iguais
50 Vértices – Tempo (Segundos)
Algoritmo A Algoritmo B Diferença
37,836 37,413 0,423
38,692 38,291 0,401
38,023 35,838 2,185
35,573 37,383 -1,81
37,482 37,085 0,397
38,909 39,018 -0,109
39,141 36,889 2,252
38,996 38,731 0,265
39,962 35,274 4,688
37,116 38,559 -1,443
40,127 38,885 1,242
38,538 38,55 -0,012
38,062 36,201 1,861
38,728 38,897 -0,169
39,842 38,843 0,999
37,06 37,691 -0,631
39,642 36,854 2,788
36,656 39,039 -2,383
36,559 38,529 -1,97
38,816 38,689 0,127
39,714 37,381 2,333
Resultados e Conclusões
44
Resultados e Conclusões
45PCC– João P. Menezes – Rodrigo D. Almeida
Media 0,544
Desvio Padrão 1,742
Intervalo de Confiança 
(90%)
0,544 ± 0,608 = 
-0,064 .. 1,153
Tempo – 50 Vértices
Podemos afirmar com 90% de confiança que os 2 algoritmos têm tempo de execução iguais
Resultados e Conclusões
Grafo de 100 vértices
• Parâmetros:
• α = 1
• Β = 2
• Taxa de Redução de Feromônio = 0.9
• Taxa de Bonus de Feronomio = 10
• Aceitação = 1
• A = 1.5
• N = 100
• F = 50
• T = 100
• Q = peso de uma aresta sorteada * numVertices
• Cidade inicial = 1
• Cidade final = 100
PCC– João P. Menezes – Rodrigo D. Almeida 46
Resultados e Conclusões
PCC– João P. Menezes – Rodrigo D. Almeida 47
100 Vértices - Custo
Algoritmo A Algoritmo B Diferença
3746,487 3510,7937 235,6933
3579,3628 3525,7686 53,5942
3627,6653 3511,9458 115,7195
2886,9202 3085,1958 -198,2756
3124,1846 3284,8406 -160,656
3122,3066 3447,0159 -324,7093
3336,9065 3158,7043 178,2022
3411,1519 3632,723 -221,5711
3221,0771 3318,703 -97,6259
3477,6768 3558,4475 -80,7707
Guloso = 5.187 
Resultados e Conclusões
48PCC– João P. Menezes – Rodrigo D. Almeida
Media -50,04
Desvio Padrão 186,856
Intervalo de Confiança 
(95%)
-50,04 ± 130,05 = 
-180,095 .. 80,015
Custo – 100 Vértices
Podemos afirmar com 95% de confiança que os 2 algoritmos apresentam resultados iguais
Resultados e Conclusões
PCC– João P. Menezes – Rodrigo D. Almeida 49
100 Vértices –Tempo (Segundos)
Algoritmo A Algoritmo B Diferença
361,476 330,448 31,028
346,783 365,561 -18,778
439,257 353,327 85,93
366,538 319,663 46,875
339,667 369,473 -29,806
346,562 373,53 -26,968
350,574 365,559 -14,985
289,493 376,707 -87,214
310,928 367,872 -56,944
295,098 334,943 -39,845
Resultados e Conclusões
50PCC– João P. Menezes – Rodrigo D. Almeida
Media -11,071
Desvio Padrão 51,583
Intervalo de Confiança 
(95%)
-11,071 ± 35,903 = 
-46,973 .. 24,832
Tempo – 100 Vértices
Podemos afirmar com 95% de confiança que os 2 algoritmos têm tempo de execução iguais
Resultados e Conclusões
Grafo de 200 vértices
• Parâmetros:
• α = 1
• Β = 2
• Taxa de Redução de Feromônio = 0.9
• Taxa de Bonus de Feronomio = 10
• Aceitação = 1
• A = 1.5
• N = 100
• F = 50
• T = 100
• Q = peso de uma aresta sorteada * numVertices
• Cidade inicial = 1
• Cidade final = 100
PCC– João P. Menezes – Rodrigo D. Almeida 51
Resultados e Conclusões
PCC– João P. Menezes – Rodrigo D. Almeida 52
200 Vértices - Custo
Algoritmo A Algoritmo B Diferença
4762,197 5272,0947 -509,8977
5330,798 5116,4604 214,3376
5220,34 5277,7046 -57,3646
5023,2427 5062,3916 -39,1489
5250,2056 5410,5693 -160,3637
5113,167 5339,3926 -226,2256
5.169 5367,096 -198,184
4770,221 5100,3955 -330,1745
Resultados e Conclusões
53PCC– João P. Menezes – Rodrigo D. Almeida
Media -130,70214
Desvio Padrão 201,4160282
Intervalo de Confiança 
(95%)
-130,702 ± 71,21131 = 
-201,913 .. -59,491
Custo – 200 Vértices
Podemos afirmar com 95% de confiança que o algoritmo A apresenta um resultado menor que o algoritmo B
Resultados e Conclusões
PCC– João P. Menezes – Rodrigo D. Almeida 54
200 Vértices –Tempo (Segundos)
Algoritmo A Algoritmo B Diferença
856,413 918,815 -62,402
954,923 952,659 2,264
829,313 913,585 -84,272
776,436 787,821 -11,385
834,037 764,908 69,129
765,264 904,152 -138,888
982,917 898,124 84,793
813,458 904,771 -91,313
Resultados e Conclusões
55PCC– João P. Menezes – Rodrigo D. Almeida
Media -23,2074
Desvio Padrão 70,97832327
Intervalo de Confiança 
(95%)
-23,2074 ± 25,094 
= 
-48,3014 .. 1,8866
Tempo – 200 Vértices
Podemos afirmar com 95% de confiança que os 2 algoritmos têm tempo de execução iguais
Resultados e Conclusões
• Embora realizado com uma amostra relativamente pequena, este experimento aponta 
que a modificação de algoritmo de seleção de cidades discutido não apresenta uma 
diferença significativa para grafos completos de 50, 100 e 200 vértices, utilizando os 
materiais e métodos descritos anteriormente.
PCC– João P. Menezes – Rodrigo D. Almeida 56
Referências Bibliográficas
FERREIRA, F.S, G.D.M, O.N.T; Colônia Evolucionária de Formigas: Uma Proposta Inicial 
Aplicada ao Problema do Caixeiro Viajante; PPGEE, DEEC, Universidade Federal do 
Pará, UFPA, 2008
JALE, J.S, DCP; Sistema de Formigas Aplicado ao Problema do Caixeiro Viajante, 
Universidade Federal Rural de Pernambuco, UFRP, SINAPE, 2010. 
LACERDA, E.G.M; A Otimização Colônia de Formigas, Departamento de Engenharia da 
Computação e Automação, UFRN, 2008.
PCC– João P. Menezes – Rodrigo D. Almeida 57