Gezgin Hırsız Problemi için Matematiksel Model ve Genetik Algoritma

Öz

Bu makalede, iyi bilinen iki kombinatoryal optimizasyon problemi, yani Gezgin Satıcı Problemi (GSP) ve Sırt Çantası Probleminin (SÇP) birleşimi olan Gezgin Hırsız Problemi (GHP) ele alınmıştır. Bu tür çok bileşenli optimizasyon problemlerinin çözülmesi sadece içerdiği katı optimizasyon problemleri nedeniyle değil, özellikle farklı bileşenler arasındaki karşılıklı bağımlılıklar nedeniyle de zordur. Bu problemin amacı, bir hırsızın tüm şehirleri ziyaret ettiği ve maksimum faydayı elde etmek için hangi şehirden hangi eşyanın alınması gerektiğini belirleyen bir toplama planını oluşturmaktır. Ele alınan problem için matematiksel model geliştirilmiş ve büyük boyutlu problemlerin önerilen matematiksel model ile çözülememesi nedeniyle iki farklı genetik algoritma geliştirilmiştir. Geliştirilen algoritmaların performansları farklı özelliklerdeki test problemleri kullanılarak test edilmiştir.

Anahtar Kelimeler

• Gezgin Hırsız Problemi
• Gezgin Satıcı Problemi
• Sırt Çantası Problemi
• Genetik Algoritma
• The Traveling Thief Problem
• The Traveling Salesman Problem
• The Knapsack Problem
• Genetic Algorithm

Mathematical Model and Genetic Algorithm for the Traveling Thief Problem

Abstract

In this article, two well-known combinatorial optimization problems are discussed, namely the Traveling Thief Problem (TTP), which is a combination of the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP). Deciphering such multicomponent optimization problems is difficult not only because of the strict optimization problems involved, but also because of the interdependencies between the different components in particular. The purpose of this problem is to form a collection plan, according to which a thief visits all cities and determines which items should be taken from which city in order to get the maximum benefit. A mathematical model has been developed for the problem under consideration, and two different genetic algorithms have been developed because large-sized problems cannot be solved with the proposed mathematical model. The performances of the developed algorithms were tested using test problems of different properties.

Keywords

• Gezgin Hırsız Problemi
• Gezgin Satıcı Problemi
• Sırt Çantası Problemi
• Genetik Algoritma
• The Traveling Thief Problem
• The Traveling Salesman Problem
• The Knapsack Problem
• Genetic Algorithm

Kaynakça

1. Klamroth, K., Mostaghim, S., Naujoks, B., Poles, S., Purshouse, R., Rudolph, G., Ruzika, S., Sayın, S., Wiecek, M.M., Yao, X., 2017. Multiobjective optimization for interwoven systems. Journal of MultiCriteria Decision Analysis 24, 71–81.
2. Bonyadi, M.R., Michalewicz, Z., Wagner, M., Neumann, F., 2019. Evolutionary Computation for Multicomponent Problems: Opportunities and Future Directions. Springer. pp. 13–30.
3. Michalewicz Z (2012) Quo vadis, evolutionary computation? On a growing gap between theory and practice. In: Advances in computational intelligence. Lecture notes in computer science, vol. 7311. Springer, Berlin, pp 98–121
4. Bonyadi M, Michalewicz Z, Barone L (2013) The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: Proceedings of the 2013 IEEE congress on evolutionary computation, Cancun, Mexico, pp 1037–1044
5. Polyakovskiy et al. (2014) Polyakovskiy S, Bonyadi MR, Wagner M, Michalewicz Z, Neumann F. A comprehensive benchmark set and heuristics for the traveling thief problem. In: Arnold DV, editor. Genetic and Evolutionary Computation Conference, GECCO ’14. New York: ACM; 2014. pp. 477–484.
6. Reinelt (1991) Reinelt G. TSPLIB: a traveling salesman problem library. INFORMS Journal of Computing. 1991;3(4):376–384. doi: 10.1287/ijoc.3.4.376.