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

Öz 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

Kaynakça

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.

Kaynak Göster

Bibtex @araştırma makalesi { cbayarfbe280728, journal = {Celal Bayar University Journal of Science}, issn = {1305-130X}, eissn = {1305-1385}, address = {}, publisher = {Celal Bayar Üniversitesi}, year = {2016}, volume = {12}, pages = {561 - 568}, doi = {10.18466/cbayarfbe.280728}, title = {An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması}, key = {cite}, author = {Karabulut, Korhan} }
APA Karabulut, K . (2016). An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması . Celal Bayar University Journal of Science , 12 (3) , 561-568 . Retrieved from https://dergipark.org.tr/tr/pub/cbayarfbe/issue/25998/280728
MLA Karabulut, K . "An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması" . Celal Bayar University Journal of Science 12 (2016 ): 561-568 <https://dergipark.org.tr/tr/pub/cbayarfbe/issue/25998/280728>
Chicago Karabulut, K . "An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması". Celal Bayar University Journal of Science 12 (2016 ): 561-568
RIS TY - JOUR T1 - An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması AU - Korhan Karabulut Y1 - 2016 PY - 2016 N1 - DO - T2 - Celal Bayar University Journal of Science JF - Journal JO - JOR SP - 561 EP - 568 VL - 12 IS - 3 SN - 1305-130X-1305-1385 M3 - UR - Y2 - 2021 ER -
EndNote %0 Celal Bayar Üniversitesi Fen Bilimleri Dergisi An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması %A Korhan Karabulut %T An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması %D 2016 %J Celal Bayar University Journal of Science %P 1305-130X-1305-1385 %V 12 %N 3 %R %U
ISNAD Karabulut, Korhan . "An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması". Celal Bayar University Journal of Science 12 / 3 (Aralık 2016): 561-568 .
AMA Karabulut K . An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması. Celal Bayar Univ J Sci. 2016; 12(3): 561-568.
Vancouver Karabulut K . An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması. Celal Bayar University Journal of Science. 2016; 12(3): 561-568.
IEEE K. Karabulut , "An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması", Celal Bayar University Journal of Science, c. 12, sayı. 3, ss. 561-568, Ara. 2016, doi:10.18466/cbayarfbe.280728

21631 12460

Arşiv
Sayıdaki Diğer Makaleler

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

Korhan Karabulut

Experimental Study and Mathematical Modeling on Thin Layer Microwave Drying of Zucchini (C. pepo) Slices

Hakan YOĞURTÇU

Photocatalytic Treatment of Baker’s Yeast Effluent Using UV Light and TiO2/ZnO Composite

Emine Yılmaz, Serap Fındık

Allocation and Scheduling of Work Orders for Trucks at a Freight Village / Bir Lojistik Köyde Yatay Taşıma Araçlarına İş Emirlerinin Atanması ve Çizelgelenmesi

Burak HATİPOĞLU, Emrah EDİS, Ece ŞENHAN, Özlem ARAZ, Rahime SANCAR EDİS

Meta-Heuristic Approach for Network Optimization Problem in Green Supply Chain Management / Yeşil Tedarik Zinciri Yönetiminde Ağ Optimizasyonu Problemine Meta-Sezgisel Yaklaşım

Seval ENE, Nursel ÖZTÜRK

Liquid Crystalline Cyclotriphosphazenes: Full Substitute Trimeric Derivative with 12-carbon-chain Mesogen Moiety

Derya DAVARCI

A Critical Approach to Lighting Control Systems in Terms of User Satisfaction / Aydınlatma Kontrol Sistemlerinin Kullanıcı Memnuniyeti Üzerindeki Etkisine Eleştirel Bir Bakış

Arzu CILASUN KUNDURACI, Tuğçe Kazanasmaz

Arsenic (III) Removal from Contaminated Water using Low-Cost Adsorbents: A Batch Adsorption Study

Şerif Targan

Determining Heart Attack Risk Ration Through AdaBoost / AdaBoost ile Kalp Krizi Risk Tespiti

Faruk BULUT

Developing a Computer Program for Slope Stability Analysis / Şev Stabilite Analizleri İçin Bir Bilgisayar Programının Geliştirilmesi

Tülin Çetin, Yusuf Erzin