Loading AI tools
Da Wikipédia, a enciclopédia livre
O problema do caixeiro-viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2013) |
![]() | As referências deste artigo necessitam de formatação. (Fevereiro de 2013) |
A origem do nome «travelling salesman problem» é desconhecida. Não parece existir qualquer documento que prove o(a) autor(a) do nome do problema. Merril Flood, da Universidade de Princeton, um dos investigadores mais proeminentes nas primeiras aplicações do problema proferiu, no entanto, o seguinte comentário: «I don´t know who coined the peppier name "Traveling Salesman Problem" for Whitney's problem, [...]» (Applegate et al., cop. 2006, p. 2).
Nos anos de 1800, problemas relacionados com o PCV começaram a ser desenvolvidos por dois matemáticos: o escocês William Rowan Hamilton e o britânico Thomas Penyngton Kerkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena. O problema foi posteriormente estudado por Hassler Whitney e Merril Flood em Princeton. Exceptuando pequenas variações ortográficas, como traveling vs travelling ou salesman vs salesman's, o nome do problema ficou globalmente conhecido por volta do ano 1950 (Applegate et al., cop. 2006, p.2).
O problema do caixeiro-viajante (representado na Figura 1) consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial (Nilsson, 1982).
Dado um conjunto de n cidades ci e uma matriz de distâncias , onde , , , a tarefa passa por encontrar a permutação que faça com que a função objectivo (distância do circuito) , onde
,
atinja o seu mínimo.
O tamanho do espaço de procura aumenta exponencialmente dependendo de n, o número de cidades, uma vez que existem
circuitos possíveis (a posição inicial é arbitrária, e a ordem do circuito pode ser invertida).
Embora tenham sido desenvolvidos bons algoritmos de aproximação para o PCV, o problema continua a oferecer uma grande atracção para a aplicação de novos algoritmos, tais como os evolucionários. Isto deve-se, essencialmente, às seguintes razões:
A topologia de um PCV pode ser visualizada segundo uma representação contínua do problema:
Partindo de , uma permutação pode ser obtida através de uma ordenação das componentes do vector, que originam um novo vector de tal forma que . A nova ordem é interpretada como o circuito resultante da permutação (Bäck, 1996).
No domínio da teoria dos grafos, cada cidade é identificada com um nó (ou vértice) e as rotas que ligam cada par de nós são identicadas como arcos (ou arestas). A cada uma destas linhas estarão associadas as distâncias (ou custos) correspondentes. Desde que seja possível ir directamente de uma cidade para qualquer outra, o gráfico diz-se completo. Uma viagem que passe por todas as cidades corresponde a um ciclo Hamiltoniano, representado por um conjunto específico de linhas. A distância do ciclo é o somatório das distâncias das linhas presentes no mesmo.
Formalmente, o problema pode ser representado por um grafo G(V, E), com e custos , , referentes a cada uma das arestas. O objectivo, no caso de um grafo completo com n vértices (cidades) é encontrar o melhor circuito entre os possíveis.
Dependendo da importância que poderá ter o sentido das setas(arestas), entre nós(cidades), o PCV pode-se distinguir em simétrico ou assimétrico (Guedes, 2005).
Dependendo da importância que a direção das arestas que atravessam o grafo possam ter, distingue-se o PCV assimétrico do simétrico. Para formular o PCV assimétrico em m cidades, introduzem-se variáveis zero ou um:
Assim, e dado o facto de que a cada nó do grafo apenas pode corresponder e sair uma seta (Figura 2), um obtém uma atribuição clássica do problema. Estas restrições, contudo não são suficientes, uma vez que esta formulação permite a ocorrência de subcircuitos, ou seja, mesmo respeitando as condições impostas, considera-se a formação de aglomerados de cidades sem ligação. Por esta razão, a formulação do problema tem que possuir condições necessárias para remoção de subcircuitos. Assim, o problema é reformulado da seguinte forma:
Onde:
Para formular o PCV simétrico, um demonstra que a direcção atravessada é imaterial, de modo que = . Uma vez que a direcção não tem interesse, um pode considerar o gráfo onde existe apenas um arco, sem direcção, entre todos os pares de nós. Assim, é a variável de decisão onde j percorre todos os arcos E do grafo, sem direcção, e é o custo de percorrer cada troço. Para encontrar um circuito neste gráfo, um, deve seleccionar um subconjunto de arcos, tal que todos os nós estejam contidos exactamente em dois dos arcos seleccionados. Assim, o problema pode ser formulado como um problema 2-matching no gráfo com m(m-1)/2 zero-um variáveis, isto é, metade do número da formulação anterior. Tal como no caso assimétrico, os subcircuitos devem ser eliminados através de restrições de eliminação de subcircuitos. O problema pode então ser formulado como:
onde J(j) é o conjunto de todos os arcos, não direccionados, ligados ao nó j e E(K) é o subconjunto de todos os arcos, não direccionados, que ligam as cidades em qualquer subconjunto K não vazio apropriado de todas as cidades.
É evidente que o problema simétrico é um caso especial do assimétrico, mas experiências práticas demonstram que os algoritmos para o problema assimétrico, regra geral, desenvolvem mal no simétrico. Assim, este tipo de problemas requerem formulações especiais e tratamentos de soluções (Hoffman, 2000).
A solução do PCV pode ser determinada por diferentes métodos. Estes, podem ser agrupados em métodos exactos e heurísticos. Os primeiros têm por base procedimentos «branch-and-bound» (em inglês). , isto é, de enumeração implícita em árvore onde é necessário inserir um limite inferior, no leque de soluções do problema. Existem limites inferiores triviais, como por exemplo, o elemento mínimo das soluções encontradas. Contudo, este tipo de métodos demonstram muita dificuldade quando aplicados a problemas muito complexos, isto é, um PCV com muitas cidades, uma vez que a árvore de enumeração é muito extensa (Conway, 2003).
Os métodos heurísticos são procedimentos bastante particulares, o que os torna inflexíveis para a determinação de boas soluções para um outro problema ligeiramente diferente.
As heurísticas podem ser agrupadas em métodos de construção de circuitos e métodos de melhorias de circuitos.
Nestes métodos, o circuito é construído sequencialmente, isto é, os nós vão sendo inseridos faseadamente, mediante certas condições, sem que exista qualquer modificação posterior à inserção definida pelo processamento do algoritmo.
A construção do circuito pode ser elaborada através dos seguintes métodos:
Estes métodos procuram melhorar o circuito obtido através de algum outro método. Para tal, o método mais utilizado, elaborado por Lin e Kernighan em 1973, denomina-se por k-opt. Nesta proposta, k arcos são substituídos, no circuito, por outros k arcos com o objectivo de diminuir a distância total percorrida. Quanto maior for o valor de k, melhor é a precisão do método, mas maior é o esforço computacional.
Com a variação do valor k, no método de melhoria k-opt, a heurística de Lin e Kernighan aumentaria a sua eficiência quando comparada com o mesmo método utilizando um valor de k fixo. Desta forma, o método não fica mais simples, contudo passa a ser possível a aplicação do método a problemas mais abrangentes com resultados favoráveis.
Para além deste método, existem outros métodos de melhorias baseados em metaheurísticas do tipo simulated annealing e busca tabu. Estes, para além de se basearem no desenvolvimento k-opt, procuram uma solução que não a dada pelos métodos anteriores. No simulated annealing é utilizado um controlo de possibilidades de solução melhores partindo de piores, no início. Na busca tabu os movimentos considerados tabu, isto é, que não se podem efectuar, mesmo que melhorem a solução são temporariamente interditos com o objectivo de se alcançar soluções piores no início que no final poderão ser consideradas melhores (Laporte, 2002) e (Heslgaun, 2000), citados por (Cunha, 2002).
A rede neural periódica de Wang, do inglês Wang Recurrent Neural Network (WRNN), com o princípio Winner Takes All (WTA), pode ser aplicada para a resolução do PCV. Além disso, a utilização do princípio WTA nas soluções encontradas pelo WRNN faz com que as mesmas formem circuitos exequíveis. Como tal, este é um método de construção (WRNN) e de melhoria (WTA) de circuitos.
O número médio de iterações necessárias para a resolução do PCV utilizando o WRNN é de 4463, com o WRNN + WTA é de 41, isto em problemas que variam entre 3 x 3 e 20 x 20.
A WRNN é caracterizada por uma equação diferencial, que engloba uma função do tipo sigmóide. Os vários parâmetros incluídos nas equações afectam a convergência da rede, pois trata-se de factores penalizantes pelas violações às restrições do problema, de controlo para a minimização da função objectivo, entre outros. Esta formulação possui ainda um termo que avalia as violações às restrições do problema dando a indicação do cumprimento das mesmas, após um certo número de iterações. Depois de encontrados tais parâmetros, aplica-se o princípio WTA que pode ser dado através do seguinte algoritmo:
1) Determinar o número máximo de circuitos rmax e encontrar uma solução para o problema utilizando a técnica WRNN. Se o termo que avalia as restrições for satisfeito, segue-se para o passo 2, caso contrário encontra-se outra solução x.
2) Dada uma matriz de decisão, considera-se uma matriz , onde = x = ;
3) Escolhe-se uma linha k na matriz de decisão . Faz-se p = k, :
4) Encontra-se o maior elemento da linha k, . O valor deste elemento é dado por metade do somatório de todos os elementos da linha k:
Os outros elementos da linha k e da coluna l passam a ser nulos. Para que não exista a formação de sub circuitos os elmentos da coluna k têm, também, que ser nulos. Depois destas condições, faz-se e avança-se para o passo 5.
5) Se m < n, então faz-se m = m + 1 e retorna-se ao passo 4. Caso contrário, aplica-se a seguinte expressão:
A equação determina o custo do circuito, z.
6) Se z <zmin, faz-se zmin = z e x = . De seguida verifica-se se r <rmax pela equação r = r + 1. Se tal acontecer, inicia-se o procedimento do WRNN no passo 2, caso contrário finaliza-se o algoritmo.
Este procedimento pode ser aplicado tanto ao PCV simétrico como ao assimétrico (Siqueira, 2006).
Os algoritmos genéticos (AGs) são um dos vários métodos que se utilizam para a resolução de problemas complexos. Este método tem por base um processo iterativo sobre uma determinada população fixa, denominados por indivíduos, que representam as várias soluções do problema. Esta técnica advém do processo de evolução dos seres vivos demonstrada por Darwin.
Da mesma forma que os sistemas biológicos, ao longo da sua evolução, tiveram que se «moldar» às alterações ambientais para a sua sobrevivência, os AGs acumulam a informação sobre o ambiente com o intuito de se adptarem ao novo meio. Tal informação funciona como um sistema de triagem para a obtenção de novas soluções exequíveis.
O método dos algoritmos genéticos é muito utilizado devido à simplicidade de operação, eficácia pela determinação de um máximo global e aplicabilidade em problemas onde se desconhece o modelo matemático ou onde o mesmo se torna impreciso em funções lineares e não-lineares (Costa, 2003).
A formação de um algoritmo genético convencional desenvolve-se através dos seguintes passos:
Para o desenvolvimento do primeiro passo, deve-se ter em consideração que a representação tradicional de um algoritmo genético é feita por binários (zero-um). Esta representação, embora eficiente, torna-se cada vez mais limitada à medida que o número de restrições do problema cresce. Desta forma, convencionou-se a utilização de um vector, formado por números inteiros, para a representação de um cromossoma.
Qualquer que seja a representação escolhida, a mesma deve verificar uma associação correcta com as soluções do problema em estudo. Isto é, para cada solução deve existir um cromossoma associado, atribuído pelo AG, e vice-versa.
Para o PCV a representação que mais se adequa é a dos números inteiros. Tal facto, deve-se à possibilidade de obtenção de soluções, por sequência de três bits, além do número de cidades do problema.
Para a construção de uma população inicial de cromossomas (passo 2), o AG demonstra uma capacidade bastante alta. Pegando num exemplo de um PCV com n cidades, a tarefa de se obter k soluções exequíveis numa estrutura de k cromossomas, mediante a utilização da representação por números inteiros, tem o mesmo significado que a obtenção de k vectores com n números inteiros, de 1 a n e diferentes entre eles. Caso a obtenção da população inicial de cromossomas seja difícil, isto é, caso o problema tenha vários parâmetros e restrições, torna-se mais fácil e rápido a utilização de heurísticas simples.
A avaliação dos cromossomas num AG, faz-se considerando a capacidade de sobrevivência dos cromossomas. Num PCV, esta capacidade de sobrevivência é relativa ao valor da função objectivo, que por sua vez, é avaliada pelo cromossoma associado. Para um PCV com n igual a 5 cidades, por exemplo, a capacidade do cromossoma é avaliada consoante o custo D, referente à soma das distâncias ():
Assim, quanto menor o D, maior é o nível de aptidão do cromossoma.
O operador genético é o núcleo de um AG e o seu objectivo passa pela produção de novos cromossomas, com propriedades superiores relativamente aos que lhes deram origem.
Nos AG convencionais, os operadores genéticos mais utilizados são a mutação e o «crossover» (em inglês). (Figura 3). O primeiro consiste numa alteração de genes de um cromossoma consoante a função probabilidade. O crossover consiste na produção de um ou dois cromossomas filhos, denominados como offsprings, com base nas informações dos dois cromossomas pais. Este operador demonstra uma determinada eficiência consoante a representação utilizada. Salienta-se que caso a representação adoptada seja a binária, é normal a produção de soluções não exequíveis, como referido anteriormente.
Estes dois tipos de operadores, embora simples, têm a particularidade de não conseguirem dar uma resposta adequada quando confrontados com problemas de elevada complexidade.
Os parâmetros de um algoritmo genético que se devem ter em consideração, aquando da sua implementação, diferem entre autores. De uma maneira geral, os parâmetros são os seguintes:
Sendo o PCV um problema de optimização muito complexo, o AG convencional é um método relativamente ineficaz quando comparado com outras heurísticas desenvolvidas. Desta forma, o AG sofreu vários desenvolvimentos com o intuito de dar resposta às condições propostas pelos problemas. A este conjunto de algoritmos genéticos dá-se o nome de algoritmos genéticos não convencionais (Ochi, 1998).
O PCV tem um papel importante na optimização das colónias de formigas, «ant colony optimization (ACO)» (em inglês). , desde o primeiro algoritmo ACO, chamado «Sistema de Formigas», do inglês Ant System, até aos mais recentes.
O PCV foi escolhido por muitas razões:
Nos algoritmos ACO, as formigas são simples agentes que, no caso do PCV, constroem circuitos através do movimento entre cidades no grafo do problema. A solução construída pelas formigas é elaborada por trilhos de feromonas (artificiais) e pela disponibilidade de informação heurística, à priori. Quando o algoritmo ACO é aplicado, é associada uma força da feromona , onde é uma informação numérica que é modificada durante o algoritmo, e t é o contador das iterações.
Para o PCV simétrico, o algoritmo ACO caracteriza-se por . No assimétrico a igualdade pode ser desfeita por .
Inicialmente, cada uma das m formigas é colocada numa cidade, de forma aleatória, aplicando-se depois, de modo iterativo, uma regra de transição de estado para cada uma das cidades.
Uma formiga constrói um circuito da seguinte forma. Na cidade i a formiga escolhe uma cidade j que ainda não tenha visitado. Esta escolha é feita probabilisticamente segundo a força da feromona no arco entre as cidades i e j, e a informação heurística disponível localmente, que é função do comprimento do arco. As formigas, de um modo probabilístico, preferem as cidades que estejam mais próximas e ligadas por arcos com grande força de feromona. Para construir um solução exequível, cada formiga possui uma forma de memória limitada, chamada tabu list onde é guardada o corrente circuito parcial. A memória é utilizada para determinar, a cada passo da construção, o conjunto de cidades que têm ainda que ser visitadas e para garantir que é elaborada uma solução exequível. Adicionalmente, permite à formiga refazer o seu circuito, assim que esteja completo.
Depois de todas as formigas terem construído um circuito, as feromonas são actualizadas. Isto é tipicamente elaborado através da descida da força dos trilhos das feromonas, através de um factor constante, e depois é dada liberdade para que as formigas depositem as suas feromonas nos arcos que visitaram. A actualização dos trilhos é feita de tal forma que os arcos mais curtos, ou visitados por muitas formigas, recebem quantidades maiores de feromonas e por isso são escolhidas com uma maior probabilidade nas iterações posteriores (Figura 4). Neste sentido, a quantidade de feromonas representa o desejo instruído de escolher a próxima cidade j quando a formiga estiver na cidade i.
Os algoritmos ACO que melhor desempenho têm no PCV, melhoram os circuitos construídos pelas formigas através da aplicação de algoritmos de procura local. Estes algoritmos são na verdade algoritmos híbridos que combinam a construção da solução de modo probabilístico com algoritmos de procura local.
No aspecto geral, todos os algoritmos ACO para o PCV seguem o esquema de um algoritmo específico. Depois de iniciados o rasto de feromonas e alguns parâmetros, o circuito principal é repetido até que a condição seja conhecida e rescindida. No circuito principal, primeiro as formigas constroem circuitos exequíveis, depois os circuitos produzidos são melhorados pela aplicação de uma procura local, e finalmente, os rastos de feromonas são actualizados. De facto, a maior parte dos algoritmos ACO que melhor se desenvolvem nos problemas NP-difícil seguem este esquema algorítmico.
Por fim é de salientar que as meta-heurísticas ACO são mais generalizados que o esquema algorítmico dado anteriormente (Stützle, 1999).
Se pensarmos em um abordagem de força bruta, temos que avaliar todas as possíveis jornadas e retornar a melhor encontrada. Essa abordagem utiliza tempo O(n!).
Em programação dinâmica temos uma solução muito mais rápida, embora não polinomial.
A programação dinâmica reduz o número de possíveis combinações eliminando as que não poderão fazer parte de uma solução ótima do problema, dando assim origem a algoritmos mais eficientes.
A ideia básica é construir por etapas uma resposta ótima combinando respostas já obtidas para partes menores. Assim, é possível escolher subproblemas de modo que a informação vital seja recordada e levada a diante.
Precisamos saber todas as cidades visitadas, para que não repitamos nenhuma delas. Veja um subproblema apropriado:
Para um subconjunto de cidades que inclui e , seja o comprimento do caminho mínimo visitando cada nó em exatamente uma vez, começando em e terminando em .
Vamos expressar em termos de subproblemas menores. Precisamos começar em e terminar em ; qual devemos escolher como a penúltima cidade? Ela tem de ser algum , tal que o comprimento total seja a distância de até , ou seja , mais o comprimento da aresta final, . Temos de selecionar o melhor tal que:
Os problemas são ordenados por |S|: C({1},1) = 0: Para s = 2 até n: Para todos os subconjuntos S {1,2,...,n} de tamanho s e contendo 1: C(S,1) = : Para todo j S, i j: C(S,j) = min{C(S - {j},i) + d: i S, i j} Retornar min C({1,...,n},j) + d
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.