| Popis: |
1900'lü yıllardan beri, gezgin satıcı problemi (TSP), NP-hard optimizasyon problemlerine ait oldugu icin en çok çalışılan optimizasyon problemlerinden biri olmuştur. TSP'nin ana fikri, Hamilton döngüsünün yaratılması için her şehir (düğüm) sadece bir kez ziyaret edilerek toplam mesafeyi en aza indirilmesidir. Başka bir deyişle, gezgin satıcı müşteri siparişlerini ilk şehir (düğüm) ile başlatarak ve her müşteriyi sadece bir kez ziyaret ederek ve başlayacak olan düğüme dönerek teslim ettiğinde, tüm bu süreç, seyahat edilen toplam mesafenin minimum olmasını sağlar. TSP'lerin klasik matematiksel yöntemler kullanılarak çözülmesi zordur. Günümüzde bile TSP problemlerini bu yöntemlerle çözen bilgisayarlar çok zaman almaktadır. Bu nedenle, gezgin satıcı problemi için birçok verimli optimizasyon algoritmaları, her zaman akademik önerilere odaklanmıştır. TSP'nin çoğu, gerçek zamanlı olarak tatmin edici çözümler sağlayan meta-sezgisel yöntemler ile çözülmüştür. Meta-sezgisel algoritmaları, hayvanların ve böceklerin karıncalar, arılar, balıklar, kuş sürüleri ve memeliler gibi bir çok çeşitli davranış yasalarının ilhamından icat edildi ve geliştirildi.Bu tez beş meta-sezgisel yöntemine odaklanmaktadır: Gri Kurt Optimizasyonu, Balina Optimizasyon Algoritması, Tavuk Sürüsü Optimizasyonu, Karga Arama Algoritması ve Parçacık Sürü Optimizasyonu. Uygulama problemi TSPLIB'den seçildi. Bu tez aynı zamanda daha basit bir algoritmanın bile iyi bir çözüme ulaşabileceğini göstermektedir. TSP'yi çözmek veya meta-sezgisel çözüme başlamak için birincil algoritma olarak önerilebilecek olan muhtemelen en iyi sonucu üretecek yöntemler Balina Optimizasyon Algoritması ve Gri Kurt Optimizasyonudur. Bu tür çalışmaların temel amacı, büyük ölçekli TSP'yi uygun zamanda ve diğer birçok gerçek yaşam problemini çözmek için kullanılabilecek etkin ve etkili optimizasyon algoritmalarının geliştirilmesidir. Since the 1900s the travelling salesman problem (TSP) has been among the most widely studied optimization problems which belong to the NP-hard optimization problems. The main idea of TSP is that a Hamiltonian cycle will be created in a way that every city (node) will be visited once and only once leading the travelled total distance to be minimized. In other words the problem is when the salesman delivers customer orders by beginning with an initial city (node) then visiting every customer only once, and returning to the node that begin with, all that process should lead the travelled total distance to be the minimum cost tour. TSPs are difficult to be solved using classical mathematical methods. Even with nowadays computers solving TSP with these methods takes very plenty of time. Therefore, many efficient optimization algorithms for the TSP have been focused for academic proposes all the times. Most of the TSP are now solved by meta-heuristic methods, that provides a satisfactory solutions in real-time. Meta-heuristic algorithms were invented and developed from the inspiration of various behavior laws of animals and insects such as ants, bees, fish schools, bird flocks and mammals.This thesis focuses on five meta-heuristic methods: Grey Wolf Optimizer, Whale Optimization Algorithm, Chicken Swarm Optimization, Crow Search Algorithm and Particle Swarm Optimization Algorithm. The problem for application was selected from TSPLIB. This thesis also shows that even a simpler algorithm can achieve quite good value of the solution. Probably the best implemented solutions were Whale Optimization Algorithm and Grey Wolf Optimizer which can be recommended as primary algorithm to solve the TSP or to start with the meta-heuristic solution. The main purpose of these kind of studies is the development of efficient and effective optimization algorithms that could be used to solve large scale TSP in appropriate time and many other real life problems. 71 |
