Eş Maliyetli Küme Kapsama Problemi İçin Adaptif Gözlem Ağırlıklandırmaya Dayalı Bir Yerel Arama Algoritması Önerisi

Year 2021, , 1149 - 1159, 20.11.2021

Osman Pala

https://doi.org/10.21076/vizyoner.875219

Abstract

Gerçek hayatta işletmelerin karşılaştığı birçok problemin modellenebildiği eş maliyetli küme kapsama problemi, temel bir matematiksel problemdir. Problemde, veri setinde yer alan gözlemlerin tamamını barındıracak şekilde en az sayıda küme seçilmesi amaçlanmaktadır. Tam sayılı programlama şeklinde ifade edilen problemin çözümünde, klasik ve kesin sonuç veren yöntemlerin yetersiz kalması nedeniyle çeşitli iteratif yaklaşımlar kullanılmaktadır. Bu yaklaşımlardan biri ise yerel arama algoritmalarıdır. Çalışma kapsamında problemin kendi yapısına uygun ve gözlemleri adaptif ağırlıklandırmaya dayalı bir yerel arama algoritması önerilmiştir. Adaptif yapı kullanılarak oluşturulan değişkenler için, optimizasyon sürecinde elde edilen çıktılar girdi parametreleri olarak ele alınmıştır. Bu sayede yerel arama yaklaşımının daha akıllı hale getirilmesi amaçlanmıştır. Önerilen adaptif metot, örnek eş maliyetli küme kapsama problemlerinin çözümünde kullanılmış ve performansı literatürde yer alan diğer adaptif yöntemlerle kıyaslanmıştır. Sonuçlar incelenerek, geliştirilen metodun etkinliği ortaya konmuştur.

Keywords

Eş Maliyetli Küme Kapsama Problemi, Yerel Arama Algoritması, Adaptif Parametre

A Local Search Algorithm Proposal Based on Adaptive Row Weighting for Unicost Set Covering Problem

Abstract

The Unicost Set Covering Problem is a basic mathematical problem with which many problems faced by businesses in real life can be modeled. In the problem, it is aimed to select the least number of clusters to contain all of the observations in the data set. In the solution of the problem expressed in the form of integer programming, various iterative approaches are used due to the inadequacy of classical and exact methods. One of these approaches is local search algorithms. Within the scope of the study, a local search algorithm suitable for the problem's own structure and based on adaptive weighting of the observations is proposed. For the variables created using the adaptive structure, the outputs obtained during the optimization process are considered as input parameters. In this way, it is aimed to make a smarter local search approach. The proposed adaptive method is used in solving the examples of unicost set covering problem and its performance is compared with other adaptive methods in the literature. By examining the results, the efficiency of the developed method is revealed.

Keywords

Unicost Set Covering Problem, Local Search Algorithm, Adaptive Parameter

References

• Aickelin, U. (2002). An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society, 53(10), 1118-1126.
• Al-Sultan, K.S., Hussain, M.F. ve Nizami, J.S. (1996). A genetic algorithm for the set covering problem. Journal of the Operational Research Society, 47(5), 702-709.
• Bautista, J. ve Pereira, J. (2007). A GRASP algorithm to solve the unicost set covering problem. Computers & Operations Research, 34(10), 3162-3173.
• Beasley, J.E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the operational research society, 41(11), 1069-1072.
• Beasley, J.E. ve Chu, P.C. (1996). A genetic algorithm for the set covering problem. European journal of operational research, 94(2), 392-404.
• Cai, S., Su, K. ve Sattar, A. (2011). Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial Intelligence, 175(9-10), 1672-1696.
• Caprara, A., Fischetti, M. ve Toth, P. (1999). A heuristic method for the set covering problem. Operations research, 47(5), 730-743.
• Caprara, A., Toth, P. ve Fischetti, M. (2000). Algorithms for the set covering problem. Annals of Operations Research, 98(1-4), 353-371.
• Chvatal, V. (1979). A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3), 233-235.
• Crawford, B., Soto, R., Suárez, M.O., Paredes, F. ve Johnson, F. (2014). Binary firefly algorithm for the set covering problem. In 2014 9th Iberian Conference on Information Systems and Technologies (CISTI) (pp. 1-5). IEEE.
• Crawford, B., Soto, R., Monfroy, E., Astorga, G., García, J. ve Cortes, E. (2018). A meta-optimization approach to solve the set covering problem. Ingeniería, 23(3), 274-288.
• Crawford, B., Soto, R., Olivares, R., Embry, G., Flores, D., Palma, W. ve Rubio, J. M. (2020). A binary monkey search algorithm variation for solving the set covering problem. Natural Computing, 19, 825–841
• Feo, T.A. ve Resende, M. G. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations research letters, 8(2), 67-71.
• Gao, C., Yao, X., Weise, T. ve Li, J. (2015). An efficient local search heuristic with row weighting for the unicost set covering problem. European Journal of Operational Research, 246(3), 750-761.
• Garey, M.R. ve Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York.
• Hodges, J.L. ve Lehmann, E.L. (1962). Rank methods for combination of independent experiments in analysis of variance. The Annals of Mathematical Statistics, 33(2), 482-497.
• Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian journal of statistics, 65-70.
• Jaramillo, A., Rubio, Á.G., Crawford, B., Soto, R., Paredes, F. ve Castro, C. (2018). Comparing the Black Hole and the Soccer League Competition Algorithms Solving the Set Covering Problem. Polibits, 57, 5-17.
• Lan, G., DePuy, G.W. ve Whitehouse, G.E. (2007). An effective and simple heuristic for the set covering problem. European journal of operational research, 176(3), 1387-1403.
• Lanza-Gutierrez, J.M., Crawford, B., Soto, R., Berrios, N., Gomez-Pulido, J.A. ve Paredes, F. (2017). Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization. Expert Systems with Applications, 70, 67-82.
• Lorena, L.A.N. ve de Souza Lopes, L. (1997). Genetic algorithms applied to computationally difficult set covering problems. Journal of the Operational Research Society, 48(4), 440-445.
• Musliu, N. (2006, June). Local search algorithm for unicost set covering problem. International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems içinde (302-311). Springer, Berlin, Heidelberg.
• Mücevher, M.H. ve Erdem, R. (2018). X kuşağı akademisyenler ile y kuşağı öğrencilerin birbirlerine karşı algıları. Süleyman Demirel Üniversitesi Vizyoner Dergisi, 9(22), 60-74.
• Naji-Azimi, Z., Toth, P. ve Galli, L. (2010). An electromagnetism metaheuristic for the unicost set covering problem. European Journal of Operational Research, 205(2), 290-300.
• 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.
• Ohlsson, M., Peterson, C. ve Söderberg, B. (2001). An efficient mean field approach to the set covering problem. European Journal of Operational Research, 133(3), 583-595.
• OR-Library. (2020). Erişim adresi, http://people.brunel.ac.uk/~mastjjb/jeb/info.html, (24.08.2020).
• Rahoual, M., Hadji, R. ve Bachelet, V. (2002). Parallel ant system for the set covering problem. International Workshop on Ant Algorithms içinde (262-267). Springer, Berlin, Heidelberg.
• Saygılı, M. ve Özer, Ö. (2020) Sağlık çalışanlarında ekip çalışması tutumlarının incelenmesi. Süleyman Demirel Üniversitesi Vizyoner Dergisi, 11(27), 444-454.
• Solar, M., Parada, V. ve Urrutia, R. (2002). A parallel genetic algorithm to solve the set-covering problem. Computers & Operations Research, 29(9), 1221-1235.
• Usul, H. ve Uyar, G.F. (2012). Algılanan hizmet kavramının muhasebeci seçimine etkisi. Süleyman Demirel Üniversitesi Vizyoner Dergisi, 4(7), 65-72.
• Wang, R.L. ve Okazaki, K. (2007). An improved genetic algorithm with conditional genetic operators and its application to set-covering problem. Soft computing, 11(7), 687-694.
• Wang, Y., Ouyang, D., Zhang, L. ve Yin, M. (2017). A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. Science China Information Sciences, 60(6), 062103.
• Yagiura, M., Kishida, M. ve Ibaraki, T. (2006). A 3-flip neighborhood local search for the set covering problem. European Journal of Operational Research, 172(2), 472-499.
• Yelbay, B., Birbil, Ş.İ. ve Bülbül, K. (2015). The set covering problem revisited: an empirical study of the value of dual information. Journal of Industrial Management and Optimization. 11(2),575–594.