Caixeiro viajante
Por: jaty • 3/4/2015 • Relatório de pesquisa • 1.215 Palavras (5 Páginas) • 381 Visualizações
Trabalho de Avaliação
Disciplina: Técnicas Heurísticas
2º Ano – 1º Semestre 2014/2015
Realizado por: Ana Alvarenga
Nº 42502
Introdução
Este trabalho tem como objectivo apresentar a resolução de um problema proposto pelos professores da disciplina Técnicas Heurísticas.
Problema: Considere um grafo completo G = (X,A) com X = {x1, x2,…,xn}. A cada aresta {i,j} associa-se um custo Cij e a cada vértice i associa-se um lucro Li. Pretende-se determinar um ciclo elementar (não necessariamente Hamiltoniano) de custo mínimo, que comece e termine no vértice x1 e garantindo que a soma dos proveitos dos vértices visitados não seja inferior a uma constante predefinida B.
A ideia do problema está associado ao problema de caixeiro-viajante com um Lucro a cada cidade visitada, sair da cidade origem, percorrendo todas ou algumas cidades uma única vez voltando a origem, de forma a garantir um Lucro total mínimo e uma distância total mínima.
Se considerar que a distância ou custo entre a cidade i e j seja simétrica, isto é, dij = dji, o número total de soluções possíveis é (n-1)!/2. Para valores muito grande de n é quase impossível encontrar a solução ótima do problema, para isso foi proposta as técnicas Heurísticas que procuram encontrar soluções próximas da otimalidade em tempo computacional razoável.
a) Heurísticas propostas para resolução deste problema:
Heurísticas construtivas de Vizinho mais próximo que procura encontrar uma solução inicial, minimizar a função objectivo. Inicialmente tem uma rota inicial com vértice de origem e adiciona a cada passo o vértice ainda não visitado, cuja distância do último vértice visitado seja mínima. A solução é encontrada quando o somatório de todos os lucros dos vértices pertencentes a rota for igual ou maior que o lucro mínimo pré-estabelecido. A figura1 a seguir ilustra o algoritmo da heurística do vizinho mais próximo para o problema:
Heurísticas de melhoramento utilizada para melhorar uma solução, ou seja, tentar encontrar uma solução de melhor qualidade a partir de modificações efetuadas em outra solução. Estas modificações é uma forma de pesquisar vizinhança da solução. A palavra vizinhança refere-se a rotas que se encontram próximas no espaço de busca das soluções e podem ser encontrada através de um movimento.
Vizinhança 3-optimal
A ideia desta heurística é eliminar três arestas da solução e inserir novamente as três arestas de forma cruzada, ou seja, se as três arestas eliminadas são – (k1,k2), (j1,j2) e (i1,i2), são testados todas as combinações de ligações novas entre estas cidades.
Há um vizinho para cada três arestas válidas, logo o número de vizinhos é O(n^3). A figura2 a seguir ilustra o algoritmo 3-Optimal para o problema:
b) Simulated-annealing
É uma metaheurística para otimização que consiste em uma técnica de busca local probabilística, e se fundamenta em uma analogia com a termodinâmica.
Esta técnica começa sua busca a partir de uma solução inicial qualquer, o procedimento principal consiste em um loop que gera aleatoriamente, em cada iteração, um único vizinho s’ da solução corrente s. A cada geração de um novo vizinho s’ de s, é verificada a variação ? do valor da função objetivo, isto é, ? = f (s’) – f (s). A função objectivo neste caso corresponde a minimizar a distância (custo) total das cidades percorridas, sendo a rota é sair da cidade origem e voltar a cidade origem com um lucro total mínimo, ou seja a soma do lucro de cada vértice (cidade) que compõem a rota deve satisfazer o lucro mínimo pré-estabelecido.
Para este problema pode considerar-se a solução inicial encontrada pela heurística do vizinho mais próximo, gerar em cada iteração um vizinho da solução corrente e verificar a variação do valor da função objectivo.
A variação ? indica a qualidade da nova solução em relação a anterior. Se a ?<0, significa que a solução proposta é melhor e passa a ser solução corrente. Se a ? = 0, a
solução proposta é aceita com probabilidade e^(-?/T), T é a temperatura (parâmetro de controle), isto é, a solução proposta é aceita se com a geração do número aleatório de uma distribuição uniforme no intervalo [0,1] for menor ou igual a probabilidade.
No início do processo da busca local, a temperatura assume um valor muito alto, após um número fixo de iterações diminui gradativamente (aT), sendo (0 <a<1). O procedimento chega ao fim quando a temperatura aproxima de zero e nenhuma solução que piore o valor da melhor solução seja mais aceita.
c) Tabu search
É uma metaheurísticas que tem por finalidade encontrar uma melhor solução
...