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

Year 2016, Volume: 12 Issue: 3, 561 - 568, 25.12.2016

Korhan Karabulut

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

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