Abstract
Weighted superposition attraction algorithm (WSA) is a new generation population-based metaheuristic algorithm, which has been recently proposed to solve various optimization problems. Inspired by the superposition of particles principle in physics, individuals of WSA generate a superposition, which leads other agents (solution vectors). Alternatively, based on the quality of the generated superposition, individuals occasionally tend to perform random walks. Although WSA is proven to be successful in both real-valued and some dynamic optimization problems, the performance of this new algorithm needs to be examined also in stationary binary optimization problems, which is the main motivation of the present study. Accordingly, WSA is first designed for stationary binary spaces. In this modification, WSA does not require any transfer functions to convert real numbers to binary, whereas such functions are commonly used in numerous approximation algorithms. Moreover, a step sizing function, which encourages population diversity at earlier iterations while intensifying the search towards the end, is adopted in the proposed WSA. Thus, premature convergence and local optima problems are attempted to be avoided. In this context, the contribution of the present study is twofold: first, WSA is modified for stationary binary optimization problems, secondarily, it is further enhanced by the proposed step sizing function. The performance of the modified WSA is examined by using three well-known binary optimization problems, including uncapacitated facility location problem, 0–1 knapsack problem and a natural extension of it, the set union knapsack problem. As demonstrated by the comprehensive experimental study, results point out the efficiency of the proposed WSA modification in binary optimization problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Al-Sultan KS, Al-Fawzan MA (1999) A tabu search approach to the uncapacitated facility location problem. Ann Oper Res 86:91–103. https://doi.org/10.1023/A:1018956213524
Arulselvan A (2014) A note on the set union knapsack problem. Discrete Appl Math 169:214–218. https://doi.org/10.1016/j.dam.2013.12.015
Barcelo J, Hallefjord Å, Fernandez E, Jörnsten K (1990) Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing. OR Spectrum 12(2):79–88. https://doi.org/10.1007/BF01784983
Baykasoğlu A (2012) Design optimization with chaos embedded great deluge algorithm. Appl Soft Comput 12(3):1055–1067. https://doi.org/10.1016/j.asoc.2011.11.018
Baykasoğlu A, Akpinar Ş (2015) Weighted superposition attraction (WSA): a swarm intelligence algorithm for optimization problems—part 2: constrained optimization. Appl Soft Comput 37:396–415. https://doi.org/10.1016/j.asoc.2015.08.052
Baykasoğlu A, Akpinar Ş (2017) Weighted Superposition Attraction (WSA): a swarm intelligence algorithm for optimization problems—part 1: unconstrained optimization. Appl Soft Comput 56:520–540. https://doi.org/10.1016/j.asoc.2015.10.036
Baykasoğlu A, Ozsoydan FB (2015) Adaptive firefly algorithm with chaos for mechanical design optimization problems. Appl Soft Comput 36:152–164. https://doi.org/10.1016/j.asoc.2015.06.056
Baykasoğlu A, Ozsoydan FB (2018) Dynamic optimization in binary search spaces via weighted superposition attraction algorithm. Expert Syst Appl 96:157–174. https://doi.org/10.1016/j.eswa.2017.11.048
Baykasoğlu A, Şenol ME (2016a) Combinatorial optimization via weighted superposition attraction. In: International conference on operations research of the GOR, OR 2016, Hamburg
Baykasoğlu A, Şenol ME (2016b) Oppositon-based weighted superposition attraction algorithm for travelling salesman problems. In: Lm-Scm 2016 Xiv. International Logistics and Supply Chain Congress, Izmir, Turkey
Bhattacharjee KK, Sarmah SP (2014) Shuffled frog leaping algorithm and its application to 0/1 knapsack problem. Appl Soft Comput 19:252–263. https://doi.org/10.1016/j.asoc.2014.02.010
Bhattacharjee KK, Sarmah SP (2017) Modified swarm intelligence based techniques for the knapsack problem. Appl Intell 46(1):158–179. https://doi.org/10.1007/s10489-016-0822-y
Cornuejols ML, Nemhauser GL, Wolsey LA (1990) The uncapacitated facility location problem. In: Francis RL, Mirchandani P (eds) Discrete location theory. Wiley Interscience, New York
de Armas J, Juan AA, Marquès JM, Pedroso JP (2017) Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic. J Oper Res Soc. https://doi.org/10.1057/s41274-016-0155-6
Della Croce F, Salassa F, Scatamacchia R (2017a) An exact approach for the 0–1 knapsack problem with setups. Comput Oper Res 80:61–67. https://doi.org/10.1016/j.cor.2016.11.015
Della Croce F, Salassa F, Scatamacchia R (2017b) A new exact approach for the 0–1 collapsing knapsack problem. Eur J Oper Res 260(1):56–69. https://doi.org/10.1016/j.ejor.2016.12.009
Diallo MH, August M, Hallman R, Kline M, Slayback SM, Graves C (2017) AutoMigrate: a framework for developing intelligent, self-managing cloud services with maximum availability. Clust Comput 20(3):1995–2012. https://doi.org/10.1007/s10586-017-0900-x
Dorigo M, Maniezzo V, Colorni A (1991) Positive feedback as a search strategy. Politecnico di Milano, Italy, (Technical Report No: 91-016)
Drake JH, Hyde M, Ibrahim K, Ozcan E (2014) A genetic programming hyper-heuristic for the multidimensional knapsack problem. Kybernetes 43(9/10):1500–1511. https://doi.org/10.1108/K-09-2013-0201
Erlenkotter D (1978) A dual-based procedure for uncapacitated facility location. Oper Res 26(6):992–1009. https://doi.org/10.1287/opre.26.6.992
Feng Y, Wang GG, Deb S, Lu M, Zhao XJ (2017) Solving 0–1 knapsack problem by a novel binary monarch butterfly optimization. Neural Comput Appl 28(7):1619–1634. https://doi.org/10.1007/s00521-015-2135-1
Goldschmidt O, Nehme D, Yu G (1994) Note: on the set-union knapsack problem. Naval Res Log 41(6):833–842. https://doi.org/10.1002/1520-6750(199410)41:6%3c833:AID-NAV3220410611%3e3.0.CO;2-Q
Guner AR, Sevkli M (2008) A discrete particle swarm optimization algorithm for uncapacitated facility location problem. J Artif Evol Appl. https://doi.org/10.1155/2008/861512
Hale TS, Moberg CR (2003) Location science research: a review. Ann Oper Res 123(1):21–35. https://doi.org/10.1023/A:1026110926707
He Y, Xie H, Wong TL, Wang X (2018) A novel binary artificial bee colony algorithm for the set-union knapsack problem. Future Gener Comput Syst 78:77–86. https://doi.org/10.1016/j.future.2017.05.044
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Holmberg K (1999) Exact solution methods for uncapacitated location problems with convex transportation costs. Eur J Oper Res 114(1):127–140. https://doi.org/10.1016/S0377-2217(98)00039-3
Jaramillo JH, Bhadury J, Batta R (2002) On the use of genetic algorithms to solve location problems. Comput Oper Res 29(6):761–779. https://doi.org/10.1016/S0305-0548(01)00021-1
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, 4, 1942–1948, Perth, WA, Australia. https://doi.org/10.1109/icnn.1995.488968
Kiran MS (2015) The continuous artificial bee colony algorithm for binary optimization. Appl Soft Comput 33:15–23. https://doi.org/10.1016/j.asoc.2015.04.007
Laporte G, Nickel S, da Gama FS (2015) Location science. Springer, Berlin
Li ZK, Li N (2009) A novel multi-mutation binary particle swarm optimization for 0/1 knapsack problem. In: Proceedings of IEEE control and decision conference, 3042–3047, Guilin, China. https://doi.org/10.1109/ccdc.2009.5192838
Lin FT (2008) Solving the knapsack problem with imprecise weight coefficients using genetic algorithms. Eur J Oper Res 185(1):133–145. https://doi.org/10.1016/j.ejor.2006.12.046
Lister W, Laycock RG, Day AM (2010) A dynamic cache for real-time crowd rendering. In: Computer graphics forum
Liu Y, Liu C (2009) A schema-guiding evolutionary algorithm for 0–1 knapsack problem. In: Proceedings of IEEE computer science and information technology—spring conference, 160–164, Singapore, Singapore. https://doi.org/10.1109/iacsit-sc.2009.31
Özbakır L, Turna F (2017) Clustering performance comparison of new generation meta-heuristic algorithms. Knowl-Based Syst 130(2017):1–16. https://doi.org/10.1016/j.knosys.2017.05.023
Ozturk C, Hancer E, Karaboga D (2015) A novel binary artificial bee colony algorithm based on genetic operators. Inf Sci 297:154–170. https://doi.org/10.1016/j.ins.2014.10.060
Pisinger D, Saidi A (2017) Tolerance analysis for 0–1 knapsack problems. Eur J Oper Res 258(3):866–876. https://doi.org/10.1016/j.ejor.2016.10.054
Rajabioun R (2011) Cuckoo optimization algorithm. Appl Soft Comput 11(8):5508–5518. https://doi.org/10.1016/j.asoc.2011.05.008
Riondato M, Vandin F (2014) Finding the true frequent itemsets. In: Proceedings of the 2014 SIAM international conference on data mining (pp 497–505). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973440.57
Şahin G, Süral H (2007) A review of hierarchical facility location models. Comput Oper Res 34(8):2310–2331. https://doi.org/10.1016/j.cor.2005.09.005
Sevkli M, Guner A (2006) A continuous particle swarm optimization algorithm for uncapacitated facility location problem. In: Ant colony optimization and swarm intelligence, 316–323. https://doi.org/10.1007/11839088_28
Shah-Hosseini H (2008) Intelligent water drops algorithm: a new optimization method for solving the multiple knapsack problem. Int J Intell Comput Cybern 1(2):193–212. https://doi.org/10.1108/17563780810874717
Shi H (2006). Solution to 0/1 knapsack problem based on improved ant colony algorithm. In: Proceedings of IEEE international conference on information acquisition, 1062–1066, Weihai, China. https://doi.org/10.1109/icia.2006.305887
Storn R, Price K (1997) Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11(4):341–359. https://doi.org/10.1023/A:1008202821328
Su L, Zhou Y (2016) Tolerating correlated failures in massively parallel stream processing engines. In: Proceedings of IEEE conference in data engineering (ICDE), 517–528, Helsinki, Finland. https://doi.org/10.1109/icde.2016.7498267
Sun M (2006) Solving the uncapacitated facility location problem using tabu search. Comput Oper Res 33(9):2563–2589. https://doi.org/10.1016/j.cor.2005.07.014
Taylor R (2016) Approximations of the densest k-subhypergraph and set union knapsack problems. arXiv:1610.04935
Tsuya K, Takaya M, Yamamura A (2017) Application of the firefly algorithm to the uncapacitated facility location problem. J Intell Fuzzy Syst 32(4):3201–3208. https://doi.org/10.3233/JIFS-169263
Wang D, Wu CH, Ip A, Wang D, Yan Y (2008) Parallel multi-population particle swarm optimization algorithm for the uncapacitated facility location problem using openMP. In: Proceedings of IEEE world congress on computational intelligence, 1214–1218, Hong Kong, China. https://doi.org/10.1109/cec.2008.4630951
Yang XS (2008) Nature-inspired metaheuristic algorithms. Luniver Press
Yang XS (2010) A new metaheuristic bat-inspired algorithm. In: González J, Pelta D, Cruz C, Terrazas G, Krasnogor N (eds) Nature inspired cooperative strategies for optimization. Springer, Berlin. pp 65–74. https://doi.org/10.1007/978-3-642-12538-6_6
Zhou Y, Li L, Ma M (2016) A complex-valued encoding bat algorithm for solving 0–1 knapsack problem. Neural Process Lett 44(2):407–430. https://doi.org/10.1007/s11063-015-9465-y
Zhou Y, Bao Z, Luo Q, Zhang S (2017) A complex-valued encoding wind driven optimization for the 0–1 knapsack problem. Appl Intell 46(3):684–702. https://doi.org/10.1007/s10489-016-0855-2
Zou D, Gao L, Li S, Wu J (2011) Solving 0–1 knapsack problem by a novel global harmony search algorithm. Appl Soft Comput 11(2):1556–1564. https://doi.org/10.1016/j.asoc.2010.07.019
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Baykasoğlu, A., Ozsoydan, F.B. & Senol, M.E. Weighted superposition attraction algorithm for binary optimization problems. Oper Res Int J 20, 2555–2581 (2020). https://doi.org/10.1007/s12351-018-0427-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12351-018-0427-9