Journals / Celal Bayar Üniversitesi Fen Bilimleri Dergisi / 2016 / Cilt: 12 - Sayı: 3

An Evolutionary Strategy Algorithm for the Asymmetric Travelling Salesman Problem

Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması

Pages
561–568
Publication Date
2022-10-12
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

It is shown that, the proposed algorithm is an effective method to solve the asymmetric travelling salesman problem.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Travelling salesman problem is one of the best known NP-hard problems.
📊
Key Findings & Data:An evolutionary strategy algorithm for solving the asymmetric travelling salesman problem is proposed in this paper.
💡
Conclusion & Impact:It is shown that, the proposed algorithm is an effective method to solve the asymmetric travelling salesman problem.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

Abstract

Travelling salesman problem is one of the best known NP-hard problems. It attracts many researchers, since it can be used to model many practical problems even in its most basic form. Asymmetric travelling salesman problem allows adding situations like one way roads, traffic congestion, that are especially common in large cities to the problem definition. For this reason, it is used to model real life problems where symmetry does not always hold. An evolutionary strategy algorithm for solving the asymmetric travelling salesman problem is proposed in this paper. The evolutionary strategy algorithm uses ruin and recreate algorithm to generate new solutions. In this algorithm, a given number of solution components are selected randomly and removed from the solution. In the next stage, removed solution components are reinserted into the solution in such a way that minimizes the fitness value. The ruin size, which is an important parameter for the ruin and recreate algorithm, hence also for the evolutionary strategy algorithm, is updated using the self-adapting feature of the evolutionary strategy algorithm. Self-adaption allows the algorithm to learn the parameter values that produce good results and change these values according the requirements in the current state of the search. 3-opt algorithm is used in the local search phase in order to further improve the newly generated solutions. TSPLIB problem instances which are the most widely used problem set in the literature has been used to test the performance of the developed algorithm and the results are presented. The developed algorithm is able to find the optimum solutions most of the time, and in cases it cannot find the optimum values, the percent deviation from the optimum values is at most 1%. It is shown that, the proposed algorithm is an effective method to solve the asymmetric travelling salesman problem.

Özet

Gezgin satıcı problemi NP-zor sınıfındaki en bilinen problemlerden birisidir. En temel hali bile birçok pratik problemin modellenmesi için kullanılabildiği için üzerinde birçok akademik çalışma yapılmaktadır. Asimetrik gezgin satıcı problemi özellikle büyük şehirlerde ortaya çıkan tek yönlü yollar, trafik sıkışıklığı gibi durumları da problem tanımına eklenebilmesine izin verir. Bu nedenle, simetrinin her zaman geçerli olmadığı gerçek hayat problemlerinin modellenmesinde yaygın olarak kullanılmaktadır. Bu çalışmada asimetrik gezgin satıcı probleminin çözümü için bir evrimsel strateji algoritması önerilmektedir. Geliştirilen evrimsel strateji algoritması yeni çözümlerin üretilmesi için boz ve yeniden yap algoritmasını kullanmaktadır. Bu algoritmada belirlenen sayıda çözüm bileşeni rasgele seçilerek çözümden çıkartılır. Sonraki adımda, çıkartılan bileşenler uygunluk değerini en küçük yapacak biçimde çözüme tekrar eklenir. Boz ve yeniden yap algoritması, dolayısı ile evrimsel strateji algoritması için önemli bir parametre olan bozma boyutu, evrimsel stratejisi algoritmasının özuyarlama özelliği kullanılarak güncellenmektedir. Özuyarlama özelliği algoritmanın iyi sonuç üreten parametre değerini öğrenmesini ve arama süresince aramanın o anki durumunun gerektirdiği biçimde değiştirilmesini sağlamaktadır. Elde edilen yeni çözümlerin daha da iyileştirilmesi için yerel arama aşamasında 3-opt algoritması kullanılmaktadır. Geliştirilen evrimsel strateji algoritmasının başarımının test edilmesi için literatürde en çok kullanılan problem kümesi olan TSPLIB kütüphanesi problemleri kullanılmış ve elde edilen sonuçlar sunulmuştur. Geliştirilen algoritma problemlerin optimum değerlerini çoğu zaman elde etmiş, elde edemediği durumlarda da optimum değerden sapma en çok %1 olarak gerçekleşmiştir. Geliştirilen algoritmanın asimetrik gezgin satıcı probleminin kısa sürede etkin biçimde çözülmesi için kullanılabilecek bir yöntem olduğu gösterilmiştir.

🔖

Cite This Article

KARABULUT, K. (2022). An Evolutionary Strategy Algorithm for the Asymmetric Travelling Salesman Problem. Celal Bayar Üniversitesi Fen Bilimleri Dergisi, Cilt: 12 - Sayı: 3, 561–568. https://ajindex.com/articles/472441

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (12)

  1. Abraham, A.P. The Traveling Salesman Problem: Applications, Formulations and Variations. In Combinatorial Optimization, Volume 12, The traveling salesman problem and its variations; Gutin, G; Punnen, A, Eds.; Springer US: Boston, 2002; 1-28
  2. Rodríguez, A.; Ruiz, R. The effect of the asymmetry of road transportation networks on the traveling salesman problem. Computers & Operations Research 2012; 39, Issue 7, 1566-1576
  3. Freisleben, B.; Merz, P. A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems, Proceedings of the IEEE Conference on Evolutionary Computation, Nagoya, 1996; IEEE Press, 1996
  4. Merz, P.; Freisleben, B. Genetic local search for the TSP: new results, Proceedings of the IEEE International Conference on Evolutionary Computation, Indianapolis, 1997; IEEE Press, 1997
  5. Nagata, Y.; Soler, D. A new genetic algorithm for the asymmetric traveling salesman problem. Expert Systems with Applications 2012; 39, Issue 10, 8947-8953
  6. Nagata, Y.; Kobayashi, S. Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem, Proceedings of the 7th international conference on genetic algorithms, Michigan State University, East Lansing, MI, July 19-23, 1997; Morgan Kaufmann Publishers Inc. San [7] Xing, L.N.; Chen, Y.W.; Yang, K.W.; Hou, F; Shen, X.S.; Cai, H.P. A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem. Engineering Applications of Artificial Intelligence 2008; 21, 1370-1380
  7. Chen, Y.W.; Zhu, Y.J.; Yang, G.K.; Lu, Y.Z. Improved extremal optimization for the asymmetric traveling salesman problem, Physica A: Statistical Mechanics and its Applications 2011; 390, Issues 23-24, 4459-4465
  8. Bai, J.; Yang, G.K.; Chen, Y.W.; Hu, L.S.; Pan, C.C. A model induced max-min ant colony optimization for asymmetric traveling salesman problem. Applied Soft Computing 2013; 13, Issue 3, 1365-137
  9. Osaba, E.; Yang, X.S.; Diaz, F.; Lopez-Garcia, P.; Carballedo, R. An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems. Engineering Applications of Artificial Intelligence 2016; 48, 59-71
  10. Rechenberg, I. Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis), 1971
  11. Schwefel, H.S. Numerische Optimierung von Computer-Modellen (PhD thesis), 1974
  12. Beyer, H.G.; Schwefel, H. P. Evolution Strategi