A Binary Fisherman Search Procedure for the 0/1 Knapsack Problem
详细信息 查看全文
- 关键词：Fisherman search procedure ; 0/1 knapsack problem ; Modified discrete shuffled frog ; leaping algorithm ; Simplified binary harmony search algorithm ; Soccer league competition algorithm
- 刊名：Lecture Notes in Computer Science
- 出版年：2016
- 出版时间：2016
- 年：2016
- 卷：9868
- 期：1
- 页码：447-457
- 全文大小：504 KB
- 参考文献：1.Bhattacharjee, K.K., Sarmah, S.P.: Shuffled frog leaping algorithm and its application to 0/1 knapsack problem. Appl. Soft Comput. 19, 252–263 (2014)CrossRef
2.Eusuff, M., Lansey, K., Pasha, F.: Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng. Optim. 38, 129–154 (2006)MathSciNet CrossRef
3.Pan, Q.K., Wang, L., Gao, L., Li, J.: An effective shuffled frog-leaping algorithm for lot-streaming flow shop scheduling problem. Int. J. Adv. Manufact. Technol. 52, 699–713 (2011)CrossRef
4.Kong, X., Gao, L., Ouyang, H., Li, S.: A simplified binary harmony search algorithm for large scale 0–1 knapsack problems. Expert Syst. Appl. 42, 5337–5355 (2015)CrossRef
5.Wang, L., Yang, R., Xu, Y., Niu, Q., Pardalos, P.M., Fei, M.: An improved adaptive binary harmony search algorithm. Inf. Sci. 232, 58–87 (2013)MathSciNet CrossRef
6.Wan-li, X., Mei-qing, A., Yin-zhen, L., Rui-chun, H., Jing-fang, Z.: A novel discrete global-best harmony search algorithm for solving 0-1 knapsack problems. Discrete Dyn. Nat. Soc. 2014, 12 (2014)
7.Moosavian, N., Roodsari, B.K.: Soccer league competition algorithm: a novel meta-heuristic algorithm for optimal design of water distribution networks. Swarm Evol. Comput. 17, 14–24 (2014)CrossRef
8.Moosavian, N.: Soccer league competition algorithm for solving knapsack problems. Swarm Evol. Comput. 20, 14–22 (2015)CrossRef
9.Alejo-Machado, O.J., Fernández-Luna, J.M., Huete, J.F., Morales, E.R.C.: Fisherman search procedure. Prog. Artif. Intell. 2, 193–203 (2014)CrossRef
10.Eshelman, L.J.: The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination. In: Rawlins, G.J.E. (ed.) Foundations of Genetic Algorithms, pp. 265–283. Morgan Kaufmann Publishers, San Mateo (1991). ISBN: 1-55860-170-8
11.Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32, 2271–2284 (2005)MathSciNet CrossRef MATH - 作者单位：Carlos Cobos (20)
Hernán Dulcey (20)
Johny Ortega (20)
Martha Mendoza (20)
Armando Ordoñez (21)
20. Information Technology Research Group (GTI), Universidad del Cauca, Popayán, Colombia
21. Intelligent Management Systems Group, Foundation University of Popayán, Popayán, Colombia - 丛书名：Advances in Artificial Intelligence
- ISBN：978-3-319-44636-3
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence and Robotics
Computer Communication Networks
Software Engineering
Data Encryption
Database Management
Computation by Abstract Devices
Algorithm Analysis and Problem Complexity - 出版者：Springer Berlin / Heidelberg
- ISSN：1611-3349
- 卷排序：9868
文摘
The 0/1 Knapsack Problem is a widely studied problem of binary discrete optimization that has applications in a number of diverse, real-world applications. From existing algorithms for solving this problem, the three best meta-heuristics in the state of the art were selected, namely: Modified discrete shuffled frog-leaping, Soccer league competition, and Simplified binary harmony search. These algorithms were compared with a new binary algorithm of fisherman search procedure. In order to perform this comparison, instances of the 0/1 knapsack problem with low and medium dimensionality (100 and 200 items) were used. Medium instances have three levels of complexity (uncorrelated, weakly correlated, and strongly correlated). Used instances were generated previously by other authors (in order to avoid bias). The results were analyzed using three criteria: success rate in reaching the global optima, execution time, and number of fitness function evaluations. The results enable it to be seen that the proposed algorithm is the best meta-heuristic for solving these types of 0/1 knapsack problem.