An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması

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.

Keywords — 3-opt algorithm, asymmetric travelling salesman problem, evolutionary strategy algorithm, ruin and recreate algorithm, self-adaption 

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

Keywords

• 3-opt algorithm,asymmetric travelling salesman problem,evolutionary strategy algorithm,ruin and recreate algorithm,self-adaption

References

1. 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.