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

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.

An Evolutionary Strategy Algorithm for the Asymmetric Travelling Salesman Problem

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.

PDF

___

[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.
[8] 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.
[9] 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.
[10] 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.
[11] Rechenberg, I. Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis), 1971.
[12] Schwefel, H.S. Numerische Optimierung von Computer-Modellen (PhD thesis), 1974.
[13] Beyer, H.G.; Schwefel, H. P. Evolution Strategies: A Comprehensive Introduction. Journal Natural Computing 2002; 1(1), 3-52.
[14] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G. Record Breaking Optimization Results Using the Ruin and Recreate Principle. Journal of Computational Physics 2000; Volume 159, Issue 2, 139-171.
[15] Misevicius, A. Genetic algorithm hybridized with ruin and recreate procedure: application to the quadratic assignment problem. Knowledge-Based Systems 2003; 16(5), 261- 268.
[16] Burke, E.; Curtois, T.; Hyde, M.; Kendall, G.; Ochoa, G.; Petrovic, S., Vazquez-Rodriguez, J.A.; Gendreau, M. Iterated local search vs. hyper-heuristics: Towards general-purpose search algorithms, Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2010, Barcelona, Spain, July 18-23, 2010; IEEE Press, 2010.
[17] Nawaz, M.; Enscore, E. E.; Ham, I. A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. Omega 1983; 11, 91-95.
[18] Lin, S. Computer Solutions of the Traveling Salesman Problem. Bell System Technical Journal 1965; 44, 2245-2269.
[19] Herdy, M. Application of the 'evolutionsstrategie' to discrete optimization problems, PPSN I Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, October 01 - 03, 1990; Schwefel, H.P., Männer, R. Eds.; Springer-Verlag London, UK, 1991.
[20] Beyer, H.G. Some aspects of the 'evolution strategy' for solving TSP-like optimization problems, Proceedings of the Parallel Problem Solving from Nature 2, 1992; Männer, R., Manderick, B. Eds.; Elsevier, Amsterdam, 1992.