Caixeiro viajante

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