Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması
Loading...
Date
2016
Authors
KORHAN KARABULUT
Journal Title
Journal ISSN
Volume Title
Publisher
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
Abstract
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.
Description
ORCID
Keywords
Bilgisayar Bilimleri- Yazılım Mühendisliği-Bilgisayar Bilimleri- Teori ve Metotlar, Bilgisayar Bilimleri, Yazılım Mühendisliği, Bilgisayar Bilimleri, Teori Ve Metotlar
Fields of Science
Citation
[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.
WoS Q
Scopus Q
Source
Celal Bayar Üniversitesi Fen Bilimleri Dergisi
Volume
12
Issue
3
Start Page
561
End Page
568
Collections
