Analysis of crossover, mutation methods and rates of genetic algorithms applied on traveling salesman problem

Abstract

Tüm endüstrinin(otomotiv ve özellikle lojistik alanında) ve yazılım endüstrisinde ki hızlı gelişmelerle, artan müşteri talepleri ve üreticilerin arzları sayesinde optimizasyon her gün daha çok önem kazanmaktadır. Optimizasyonla kastımız, üretim zamanlarının düşürülmesi, ürün lojistiğinin artırılması veya taşıma maliyetlerinde yakıt tüketiminin düşürülmesi anlatılmak istenmektedir. Endüstrinin bu tarz optimizasyon talepleri ayrıca optimizasyon algoritmalarının/tekniklerinin gelişerek evrilmesine katkıda bulunmuştur. Bilgisayarların gelişimi ve hesap kabiliyetlerinin gelişmesiyle, klasik optimizasyon teknikleri de evrilmiştir. Evolutionary optimizasyon tekniklerinden olan Genetik algoritmalar ve genetik programlama, optimizasyon alanında ki yüklü talebe yanıt vermeye çalışmaktadır. Temel olarak, generik algoritmalar, biyolojik genetik ve Sir Charles Darwin'in genetik alanında ki çaprazlama ve mutasyon uygulamalarından türetilmiştir. Genetik algoritmaları kullanarak, zor problemlerin daha optimize edilmiş sonuçlarına daha kolay olarak ulaşma şansına sahip oluruz. Genel olarak, aynı doğada olduğu gibi, rastgele çözümler bularak/seçerek, bu sonuçlara çaprazlama ve mutasyon teknikleri uygulayarak daha optimize sonuçlar bulmayı hedefliyoruz. Rastgele sonuçları birbiri arasında, parçalı olarak anlamlı verilerini çaprazlama ve mutasyon uygulayarak, daha optimize edilmiş sonuçlara varmayı umuyoruz. Genellikle, optimize edilmiş sonuca, doğru ve daha iyi çaprazlama ve mutasyon oranları seçerek ulaşmayı deniyoruz. Diğer bir deyişle, parametreler için kötü oranlar seçmek, bizi çoğunlukla daha kötü ve ya optimize olmayan sonuçlara ulaştıracaktır. Bu çalışmamızda, öncelikle, genetik algoritmaların genel konseptlerini tanıtıyoruz, daha sonra ise daha derine inerek ve spesifik şekilde genetik algoritmaları kullanarak, ünlü Gezgin Satıcı Problemi'ne optimize çözümler arıyoruz. Bu çalışmamızda, genetik algoritmayı Türkiyenin coğrafi bölgelerine(Marmara, Ege ve karadeniz bölgelerindeki şehirler, toplam 32 şehir) uygulayarak bu şehirler arasında ki en kısa yolu bulmaya çalışıyoruz. Genetik algoritmayı uygularken, çaprazlama metodlarını, mutasyon metodlarını, çaprazlama ve mutasyon oranlarını değiştirerek, en optimize yolu bulmaya çalışıyoruz ve sonuç olarak bulunan optimize sonuçları tüm bu parametler için ayrı ayrı analiz edip ortaya koyuyoruz. Sonuçta ise, karşılaştırılmış sonuçları grafik üzerinde göstererek, her parametrenin sonuca ne denli etki ettiğini ortaya koyuyoruz. Bu araştırmayı yaparak, gerçek hayatta lojistik endüstrisinde de aktif olarak kullanılan use caseler için daha doğru parametrelerin seçimine katkıda bulunarak, şirketlerin daha iyi yakıt tasarrufu elde etmelerine katkı sağlamayı amaçlıyoruz.

With the rapid development of whole industry(automotive and especially logistics) and software industry, increasing demand by customers and supply by manifacturers led the optimization more and more important nowadays. By the word for optimization, we mean minimizing production times, maximizing product logictics per transportation or minimizing fuel usage/maximizing fuel saving/efficiency for transportation vehicles. By the demand of these optimizations by the industry, also led optimization algorithms/techniques to grow and evolve. With the evolution of computers and computation powers, classic optimization techniques also evolved. One of evolutinary optimization techniques, Genetic algorithms and genetic programming, corresponded to these heavy demand of optimization area. Basically, genetic algorithms evolved from genetics and applications of sir Charles Darwin, crossover and mutation principles. Using Genetic Algorithms, we have the ability to optimize our solutions for hard problems. Simply, finding/choosing random solutions to the problem and make crossover and mutations on these solutions as the nature does. Crossing over and mutate the parts of solutions by switching the meaningful data between solutions and hope to reach to the best optimized solution. Generally we reach to the optimized solution by finding and trying correct or better crossover and mutation rates. In other words, choosing bad rates for these parameters, most likely leads to worse optimization. In this work, firstly, we presented the genetic algorithms in general way and after that we go in deep and used genetic algorithms to find better optimized results for the famous Traveling Salesman Problem. We chose to apply genetic algorithms on geographical regions of Turkey(Marmara, Aegean and Black Sea regions, 32 cities in total) to find best or best optimized route to travel. While applying genetic algorithms, we modified crossover methods, mutation methods and crossover and mutation rates to reach to the best possible route and analysed final solutions for each used parameter/method and made a comparison between them. Finally, we presented the compared results on graphics to visualize the evolution for each presented parameter. By making these research, we aim to reach out the best or better parameters for real use cases used in the logistics industry to reach better fuel efficiency and reducing fuel costs.