Application of Pigeon Inspired Optimization for Multidimensional Knapsack Problem
DOI:
https://doi.org/10.24002/ijieem.v2i1.3841Keywords:
metaheuristics, multidimensional knapsack problem, pigeon inspired optimization, swarm intelligenceAbstract
The multidimensional knapsack problem (MKP) is a generalization of the classical knapsack problem, a problem for allocating a resource by selecting a subset of objects that seek for the highest profit while satisfying the capacity of knapsack constraint. The MKP have many practical applications in different areas and classified as a NP-hard problem. An exact method like branch and bound and dynamic programming can solve the problem, but its time computation increases exponentially with the size of the problem. Whereas some approximation method has been developed to produce a near-optimal solution within reasonable computational times. In this paper a pigeon inspired optimization (PIO) is proposed for solving MKP. PIO is one of the metaheuristic algorithms that is classified in population-based swarm intelligent that is developed based on the behavior of the pigeon to find its home although it had gone far away from it home. In this paper, PIO implementation to solve MKP is applied to two different characteristic cases in total 10 cases. The result of the implementation of the two-best combination of parameter values for 10 cases compared to particle swarm optimization, intelligent water drop algorithm and the genetic algorithm gives satisfactory results.References
Balev, S., Yanev, N., Freville, A., Andonov, R. (2008). A Dynamic Programming Based Reduction Procedure for the Multidimensional 0-1 Knapsack Problem. European Journal of Operational Research, 186 (1), 63-76.
Banati, H. & Bajaj, M. (2011). Firefly Based Feature Selection Approach. International Journal of Computer Science Issues, 8(4), 473-480.
Basset, M.A., Doaa, E.-S., Faris, H., Mirjalili, S. (2019). A Binary Multi-Verse Optimizer for 0-1 Multi-dimensional Knapsack Problems with Application in Interactive Multimedia Systems. Computers & Industrial Engineering, 132, 187-206.
Basset, M.A., El-Shahat, D., El-Henawy, I., Sangaiah, A.K. (2018). A Modified Flower Pollination Algorithm for the Multi-dimensional Knapsack Problem: Human-Centric Decision Making. Soft Computing, 22, 4221-4239.
Battiti, R. & Tecchiolli, G. (1994). The reactive tabu search. ORSA Journal on Computing, 6, 126-140.
Berberler, M.E., Guler, A., Nuriyev, U.G. (2013). A Genetic Algorithm to Solve the Multi-dimensional Knapsack Problem. Mathematical and Computational Applications, 18(3), 486-494.
Bertsimas, D. & Demir, R. (2002). An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problem. Management Science, 48, 550-565.
Bolaji, A.L., Babatunde, B.S., Shola, P.B. (2017). Adaptation of Binary Pigeon-Inspired Algorithm for Solving Multidimensional Knapsack Problem. Soft Computing: Theories and Applications, 743-751.
Bolaji, A.L., Okwonu, F.Z., Shola, P.B., Balogun, B.S., Adubisi, O.D. (2020). A Modified Binary Pigeon-Inspired Algorithm for Solving the Multi-dimensional Knapsack Problem. Journal of Intelligent Systems, 30(1), 90-103.
Chen, W.-N., Zhang, J., Chung, H.S.H., Zhong, W.-L., Wu, W.-G., Shi, Y.-H. (2010). A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems. IEEE Transactions on Evolutionary Computation, 14(2), 278-300.
Chih, M. (2015). Self-Adaptive Check and Repair Operator-Based Particle Swarm Optimization for the Multidimensional Knapsack Problem. Applied Soft Computing, 26, 378-389.
Chu, P.C. & Beasley, J.E. (1998). A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4, 63-86.
Dammeyer, F. & Voβ, S. (1993). Dynamic Tabu List Management Using the Reverse Elimination Method. Annals of Operations Research, 41(2), 29-46.
Deng, Y. & Duan H. (2016). Control Parameter Design for Automatic Carrier Landing System via Pigeon-Inspired Optimization. Nonlinear Dynamics, 85, 97-106.
Dou, R. & Duan, H. (2016). Pigeon Inspired Optimization Approach to Model Prediction Control for Unmanned Air Vehicles. Aircraft Engineering and Aerospace Technology: An International Journal, 88 (1), 108-116.
Duan, H. & Li, C. (2014). Target Detection Approach for UAVs via Improved Pigeon-Inspired Optimization and Edge Potential Function. Aerospace Science and Technology, 39, 352-360.
Duan, H. & Qiao, P. (2014). Pigeon Inspired Optimization: A New Swarm Intelligence Optimizer for Air Robot Planning. International Journal of Intelligent Computing and Cybernetics, 7, 24-37.
Fingler, H., Caceres, E.N., Mongelli, H., Song, S.W. (2014). A Cuda Based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29, 84-94.
Freville, A. & Plateau, G. (1986). Heuristics and Reduction Methods for Multiple Constraints 0-1 Linear Programming Problems. European Journal of Operational Research, 24, 206-215.
Gilmore, P.C. & Gomory, R. (1966). The Theory and Computation of Knapsack Functions. Operations Research, 14(6), 1045-1074.
Glover, F. & Kochenberger, G.A. (1996). Critical Event Tabu Search for Multidimensional Knapsack Problem. Meta-heuristics, Springer, 407-202.
Haddar, B., Khemakhem, M., Hanafi, S., Wilbaut, C. (2016). A Hybrid Quantum Particle Swarm Optimization for the Multidimensional Knapsack Problem. Engineering Applications of Artificial Intelligence, 55, 1-13.
Hembecker, F., Lopes, H.S., & Godoy Jr., W. (2007). Particle Swarm Optimization for the Multidimensional Knapsack Problem. Proceedings of the Eighth International Conference on Adaptive and Natural Computing Algorithms, 4431, 358-365.
Ke, L., Feng, Z., Ren, Z., Wei, X. (2010). An Ant Colony Optimization Approach for the Multidimensional Knapsack Problem. Journal of Heuristics, 16(1), 65-83.
Khuri, S., Back, T., & Heitkotter, J. (1994). The Zero/One Multiple Knapsack Problem and Genetic Algorithms. Proceedings of the ACM Symposium on Applied Computing (SAC’94).
Kong, M., & Tian, P. (2006). Apply the Particle Swarm Optimization to the Multi-dimensional Knapsack Problem, In: Rutkowski, L., Tadeusiewicz, R., Zadeh, L., Zurada, J. (Eds.), Artificial Intelligence and Soft Computing–ICAISC 2006, Vol 4029 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1140-1149.
Kong, M., Tian, P., Kao, Y. (2008). A New Ant Colony Optimization Algorithm for the Multidimensional Knapsack Problem. International Journal of Applied Metaheuristic Computing, 3(4), 43-63.
Ktari, R. & Chabchoub, H. (2013). Essential Particle Swarm Optimization Queen with Tabu Search for MKP Resolution. Computing, 95(9), 897-921.
Lai, X., Hao, J.-K., Glover, F., Lu, Z. (2018). A Two Phase Tabu Evolutionary Algorithm for the 0-1 Multi-dimensional Knapsack Problem. Information Sciences, 436-437.
Leung, S.C., Zhang, D., Zhou, C., Wu, T. (2012). A Hybrid Simulated Annealing Meta-heuristic algorithm for the Two-Dimensional Knapsack Packing Problem. Computer and Operations Research, 39(1), 64-73.
Manzini, R., Speranza, M.G. (2012). Coral: An Exact Algorithm for the Multi-dimensional Knapsack Problem. INFORMS Journal of Computing, 24(3), 399-415.
Martello, S. & Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Chicester: John Wiley & Sons Ltd.
Martins, J.P., Longo, H., Delbern, A.C. (2014). On the Effectiveness of Generic Algorithms for the Multidimensional Knapsack Problem. Proceedings of the 2014 conference companion on Genetic and evolutionary computation companion, ACM, 73-74.
Palit, S., Sinha, S.N., Molla, M.A., Khanra, A., Kule, M. (2011). A Cryptanalytic Attack on the Knapsack Cryptosystem using Binary Firefly Algorithm. Second International Conference on Computer and Communication Technology, 428-432.
Rezoug, A., Boughaci, D., Rezoug, A. (2015). Stochastic Local Search Combined with Simulated Annealing for the 0=1 Multi-dimensional Knapsack Problem. Symposium on Complex Systems and Intelligent Computing (CompSIC).
Senyu, S. & Toyada, Y. (1967). An Approach to Linear Programming With 0-1 Variables. Management Science, 15(4), 196-207.
Shah-Hosseini, H. (2009). The Intelligent Water Drops Algorithm: A Nature-inspired Swarm-based Optimization Algorithm. International Journal of Bio-Inspired Computation, 1, 71-79.
Shih, W. (1979). A Branch and Bound Method for the Multiconstraint Zero-one Knapsack Problem. Journal of the Operational Research Society, 15, 196-207.
Tisna, A., F.D., Abusini, S., Andar, A. (2013). Hybrid Greedy-Particle Swarm Optimization-Genetic Algorithm and Its Convergence to Solve Multidimensional Knapsack Problem 0-1. Journal of Theoritical and Applied Information Technology, 58(3), 522-528.
Vasquez, M. & Hao, J.-K. (2001). Une Approche hybride pur le sac a dos multi-dimensionnel en variales 0-1. Operations Research, 35(4), 415-438.
Vasquez, M. & Vimont, Y. (2005) Improved Results on the 0-1 Multi-dimensional Knapsack Problem. European Journal of Operational Research, 165(1), 70-81.
Vimont, Y., Boussier, S., Vasquez, M. (2008). Reduced Cost Propagation in an Efficient Impicit Enumeration for the 0-1 Multi-dimensional Knapsack Problem. Journal of Combinatorial Optimization, 15(2), 165-178.
Wan, N.F. & Nolle, L. (2009). Solving a Multi-dimensional Knapsack Problem Using a Hybrid Particle Swarm Optimization Algorithm. Proceedings of the 23rd European Conference on Modelling and Simulation, ECMS 2009.
Weingartner, H.M., & Ness, D.N. (1967). Methods for the Solution of the Multi-dimensional 0/1 Knapsack Problem. Operation Research, 15(1), 83-103.
Zhang, X., Wu, C., Li, J., Wang, X., Yang, Z., Lee, J.-M., Jung K.-H. (2016). Binary Artificial Algae Algorithm for Multidimensional Knapsack Problem. Applied Soft Computing, 43, 583-595.
Downloads
Published
How to Cite
Issue
Section
License
The copyright of the received article shall be assigned to the journal as the publisher of the journal. The intended copyright includes the right to publish the article in various forms (including reprints). The journal maintains the publishing rights to the published articles.
This work is licensed under a Creative Commons Attribution 4.0 International License
