KARESEL ATAMA PROBLEMİ İÇİN BULANIK ADAPTİF ÇAPRAZLAMALI GENETİK ALGORİTMA ÖNERİSİ

Öz

Karesel atama problemi çok farklı alanlarda farklı tipleriyle karşılaşılabilen bir problem türüdür. Birbiri arasında akış olan faaliyet noktalarının birbiri arasında belirli mesafe olan lokasyonlara atanmasına dayanan ve akış ile mesafenin birlikte ele alınması gereken problemin, klasik çözüm yöntemleri ile çözümü oldukça zor olmakta ve çoğunlukla sezgisel algoritmalar ile uygun çözümler elde edilebilmektedir. Çok sık kullanılan sezgisel algoritmalarından biri ise Genetik Algoritma’dır. Genetik Algoritma rassallık içeren prosedürlere sahip, canlıların evrimini taklit eden oldukça başarılı bir yöntemdir. Algoritmanın en önemli prosedürlerinden bir tanesi ise çaprazlama işlemidir. Karesel atama problemi için literatürde sıklıkla pozisyon temelli çaprazlama tercih edilmektedir. Pozisyon temelli çaprazlamada kaç adet noktanın sabit kalacağı ve bu değerin nasıl belirleneceği önemli bir durumdur. Çalışmada, sabit tutulan nokta sayısını önceden belirli değerler ile ele alan klasik Genetik Algoritma yaklaşımları ile önerilen yöntem olan bulanık adaptif yaklaşım kıyaslanmıştır. Yapay zekanın bir türü olan Bulanık Mantık teorisinden faydalanan bulanık adaptif yaklaşım sayesinde algoritmanın çözüm esnasında elde ettiği bilgiler kullanılarak parametreler kontrol edilmekte ve algoritmanın arama yönü daha akıllı bir şekilde değişebilmektedir. Önerilen yöntemin etkinliğini değerlendirebilmek için literatürde yer alan karesel atama problem örneklerinden yararlanılmıştır. Sonuçların değerlendirilmesi ile Genetik Algoritma’da bulanık adaptif yaklaşımın etkinliği ortaya çıkmıştır.

Anahtar Kelimeler

• Karesel Atama Problemi
• Genetik Algoritma
• Bulanık Mantık
• Sezgisel Yaklaşımlar
• Probleme Özgü Yaklaşımlar

A Proposed Genetic Algorithm With Fuzzy Adaptive Crossover For Quadratic Assignment Problem

Abstract

The quadratic assignment problem is a type of problem that can be encountered in many different fields. The problem, which is based on the assignment of the points of activity which have flow between each other to locations with a certain distance between each other and where flow and distance has to be handled together, is very difficult to solve by classical solution methods and mostly suitable solutions can be obtained with heuristic algorithms. One of the most frequently used heuristic algorithms is Genetic Algorithm. Genetic Algorithm is a very successful method that simulates the evolution of living things with procedures involving randomness. One of the most important procedures of the algorithm is crossover. For the quadratic assignment problem, position-based crossover is often preferred in the literature. How many points will remain constant and how to determine this value is important for position based crossover. In this study, the classical Genetic Algorithm approaches, which treat the number of fixed points with predetermined values, are compared with the proposed method, fuzzy adaptive approach. By using the fuzzy adaptive approach which uses Fuzzy Logic theory which is a kind of artificial intelligence, the parameters are controlled by using the information obtained by the algorithm during the solution and the search direction of the algorithm can change more intelligently. In order to evaluate the effectiveness of the proposed method, the examples of quadratic assignment problems in the literature were utilized. With the evaluation of the results, the effectiveness of the fuzzy adaptive approach in Genetic Algorithm was revealed.

Keywords

• Quadratic Assignment Problem
• Genetic Algorithm
• Fuzzy Logic
• Heuristic Approaches
• Problem Specific Approaches

Kaynakça

1. Abdel-Basset, M., Manogaran, G., Rashad, H., ve Zaied, A. N. H. (2018). A comprehensive review of quadratic assignment problem: variants, hybrids and applications. Journal of Ambient Intelligence and Humanized Computing, 1-24.
2. Ahuja, R. K., Orlin, J. B., ve Tiwari, A. (2000). A greedy genetic algorithm for the quadratic assignment problem. Computers & Operations Research, 27(10), 917-934.
3. Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2), 154-160.
4. Burkard, R. E., Karisch, S. E., ve Rendl, F. (1997). QAPLIB–a quadratic assignment problem library. Journal of Global optimization, 10(4), 391-403.
5. Chmiel, W. (2019). Evolutionary algorithm using conditional expectation value for quadratic assignment problem. Swarm and Evolutionary Computation, 46, 1-27.
6. Christofides, N., ve Benavent, E. (1989). An exact algorithm for the quadratic assignment problem on a tree. Operations Research, 37(5), 760-768.
7. Cicirello, V. A. (2006). Non-wrapping order crossover: An order preserving crossover operator that respects absolute position. In Proceedings of the 8th annual conference on Genetic and evolutionary computation (1125-1132). ACM.
8. Drezner, Z. (2005). Compounded genetic algorithms for the quadratic assignment problem. Operations Research Letters, 33(5), 475-480.

9. Eiben, Á. E., Hinterding, R., ve Michalewicz, Z. (1999). Parameter control in evolutionary algorithms. IEEE Transactions on evolutionary computation, 3(2), 124-141.
10. El-Baz, M. A. (2004). A genetic algorithm for facility layout problems of different manufacturing environments. Computers & Industrial Engineering, 47(2-3), 233-246.
11. Gülsün, B., Tuzkaya, G., ve Duman, C. (2009). Genetik algoritmalar ile tesis yerleşimi tasarımı ve bir uygulama. Doğuş Üniversitesi Dergisi, 10 (1) 2009, 73-87
12. Herrera, F., ve Lozano, M. (2003). Fuzzy adaptive genetic algorithms: design, taxonomy, and future directions. Soft computing, 7(8), 545-562.
13. Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
14. Koopmans, T. C., ve Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, 53-76.
15. Lalla-Ruiz, E., Expósito-Izquierdo, C., Melián-Batista, B., ve Moreno-Vega, J. M. (2016). A hybrid biased random key genetic algorithm for the quadratic assignment problem. Information Processing Letters, 116(8), 513-520.
16. Larranaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., ve Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129-170.
17. Lawler, E. L. (1963). The quadratic assignment problem. Management science, 9(4), 586-599.
18. Lim, M. H., Yuan, Y., ve Omatu, S. (2000). Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem. Computational Optimization and Applications, 15(3), 249-268.
19. Liu, J., ve Lampinen, J. (2005). A fuzzy adaptive differential evolution algorithm. Soft Computing, 9(6), 448-462.
20. Maniezzo, V., ve Colorni, A. (1999). The ant system applied to the quadratic assignment problem. IEEE Transactions on knowledge and data engineering, 11(5), 769-778.Moscato, P. (1989). On genetic crossover operators for relative order preservation. C3P Report, 778.
21. Niknam, T. (2010). A new fuzzy adaptive hybrid particle swarm optimization algorithm for non-linear, non-smooth and non-convex economic dispatch problem. Applied Energy, 87(1), 327-339.
22. Potvin, J. Y. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63(3), 337-370.
23. Pulat, M., ve Kocakoç, İ. D.(2017). Gezgin Satıcı Probleminin Çözümünde Kullanılan Genetik Algoritmanın Parametrelerinin İncelenmesi. Uluslararası İktisadi ve İdari İncelemeler Dergisi, 21-36. Özel Sayı.
24. Shi, Y., ve Eberhart, R. C. (2001). Fuzzy adaptive particle swarm optimization. In Evolutionary Computation, 2001. Proceedings of the 2001 Congress on (1, 101-106). IEEE.
25. Syswerda, G. (1991). Schedule Optimization Using Genetic Algorithms. In Davis, L. (ed.) Handbook of Genetic Algorithms, 332–349. New York: Van Nostrand Reinhold.
26. Taillard, É. (1991). Robust taboo search for the quadratic assignment problem. Parallel computing, 17(4-5), 443-455.
27. Tate, D. M., ve Smith, A. E. (1995). A genetic approach to the quadratic assignment problem.”, Computers & Operations Research, 22(1), 73-83.
28. QABLIB- http://anjos.mgi.polymtl.ca/qaplib/ Erişim tarihi: 12.08.2019.