Vani Suthamathi Saravanarajan1, Rung-Ching Chen1*, Christine Dewi1, 2, Long-Sheng Chen1

1 Department of Information Management, Chaoyang University of Technology, Taichung, Taiwan, R.O.C.
2 Faculty of Information Technology, Satya Wacana Christian University, Central Java, Indonesia

Download Citation: |
Download PDF


ABSTRACT

Unbound Knapsack Problems (UKP) are important research topics in many fields like portfolio and asset selection, selection of minimum raw materials to reduce the waste, and generating keys for cryptosystems. Given the uncertainty in data, capacity, and time constraints, users have to look at the possible combination of data to get maximum benefit. This paper uses UKP as a numerical model to represent different industrial combination problems. It applies Evolutionary Algorithms (EA) with Bound Constrained Strategy (BCS) to construct a search space and algorithm parameters for finding the optimal solution. Evolutionary Algorithms (EA) like Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) are designed based on reusable components for the algorithms to converge faster. Simulation for various objectives indicates that the GA and PSO can find the near-optimal solution in all cases. The execution time of GA and PSO for different goals and the variations in the algorithm parameters are measured. The measurement result shows the performance of GA and PSO is the same on an average for the differences in bounded constraints and parameter settings.


Keywords: Unbound knapsack problem, Constrained optimization, Genetic algorithm, Particle swarm optimization, Evolutionary algorithms.


Share this article with your colleagues

 


REFERENCES

  1. Chai, R., Savvaris, A., Tsourdos, A., Chai, S., Xia, Y. 2020. Stochastic spacecraft trajectory optimization with the consideration of chance constraints, IEEE Trans. Control Syst. Technol., 28, 1550–1559, https://doi.org/10.1109/TCST. 2019.2908938.

  2. Chaturvedi, S., Pragya, P., Verma, H.K. 2016. Comparative analysis of particle swarm optimization, genetic algorithm, and krill herd algorithm, IEEE Int. Conf. Comput. Commun. Control. IC4, 2015, 3–9, https://doi.org/10.1109/IC4.2015.7375552.

  3. Chen, X., Ong, Y.S., Lim, M.H., Tan, K.C. 2011. A multi-facet survey on memetic computation, IEEE Trans. Evol. Comput., 15, 591–607, https://doi.org/10.1109/TEVC.2011.21327 25.

  4. Coello, C.C.A., Brambila, S.G., Gamboa, J.F., Tapia, M.G.C., Gómez, R.H. 2019. Evolutionary multiobjective optimization: open research areas and some challenges lying ahead, Complex Intell. Syst., 6, 221–236, https://doi.org/10.1007/s40747-019-0113-4.

  5. Corus, D., Oliveto, P.S. 2018. Standard steady state genetic algorithms can hillclimb faster than Mutation-Only Evolutionary algorithms, IEEE Trans. Evol. Comput., 22, 720–732, https://doi.org/10.1109/TEVC.2017.2745715.

  6. Deplano, I., Yazdani, D., Nguyen, T.T. 2019. The offline group seat reservation knapsack problem with profit on seats, IEEE Access, 7, 152358–152367, https://doi.org/10.1109/ ACCESS.2019.2948322.

  7. Digabel, S.L., Wild, S.M. May, 2015. A taxonomy of constraints in Simulation-Based optimization, no. [Online]. Available: http://arxiv.org/abs/1505.07881.

  8. Han, C., Zhang, P., Wang, W., Wang, Y., Zhang, Z. 2019. Delay-Optimal Joint processing in Computation-Constrained Fog radio access networks, IEEE Access, 7, 58857–58865, https://doi.org/10.1109/ACCESS.2019.2913147.

  9. Harman, E., Singh, P., Avneet Kaur, E. 2015. Statistical analysis of velocity update rules in particle swarm optimization, Int. J. Artif. Intell. Appl. Smart Devices, 3, 11–22, https://doi.org/10.14257/ijaiasd.2015.3.2.02.

  10. Hellwig, M., Beyer, H.G. 2019. Benchmarking evolutionary algorithms for single objective real-valued constrained optimization – A critical review, Swarm Evol. Comput., 44, 927–944, https://doi.org/10.1016/j.swevo.2018.10.002.

  11. Hsu, C.C., Yu, C.Y. 2004. Design of optimal controller for interval plant from signal energy point of view via evolutionary approaches, IEEE Trans. Syst. Man, Cybern. Part B Cybern., 34, 1609–1617, https://doi.org/10.1109/TSMCB. 2004.826396.

  12. Jiang, H., Chen, R.C., Liu, Q.E., Huang, S.W. 2019. Fuzzy rules reduction based on sparse coding, International Journal of Applied Science and Engineering, 16, 215-227.

  13. Juarez-Castillo, E., Acosta-Mesa, H.G., Mezura-Montes, E. 2017. Empirical study of bound constraint-handling methods in Particle Swarm Optimization for constrained search spaces, 2017 IEEE Congr. Evol. Comput. CEC 2017 - Proc., 604–611, https://doi.org/10.1109/CEC.2017.7969366.

  14. Li, S., Li, X., Wang, X., Liu, J. 2019. Usage-Constrained sensor selection, 65, 4392–4410.

  15. Marius, O., Nicolae, P., Koprinkova, P., Yancho, T. 2017. Genetic algorithm for system modeling, Proc. 9th Int. Conf. Electron. Comput. Artif. Intell. ECAI, 2017-January, 1–4, https://doi.org/10.1109/ECAI.2017.8166517.

  16. Michalewicz, Z., Deb, K., Schmidt, M., Stidsen, T. 2000. Test-case generator for nonlinear continuous parameter optimization techniques, IEEE Trans. Evol. Comput., 4, 197–214, https://doi.org/10.1109/4235.873232.

  17. Nguyen, T.T., Yao, X. 2012. Continuous dynamic constrained optimization-the challenges, IEEE Trans. Evol. Comput., 16, 769–786, https://doi.org/10.1109/TEVC.2011.2180533.

  18. Salomon, R. 1998. Evolutionary algorithms and gradient search: similarities and differences, IEEE Transactions on Evolutionary Computation, 2, 45–55, https://doi.org/10.1109/4235.728207.

  19. Satapathy, S.C., Naik, A., Parvathi, K. 2013. A teaching learning based optimization based on orthogonal design for solving global optimization problems, Springerplus, 2, 1–12, https://doi.org/10.1186/2193-1801-2-130.

  20. Sun, Q., Yang, G., Wang, X., Chen, Y.H. 2020. Regulating Constraint-Following bound for uncertain mechanical systems: An indirect control approach, IEEE Access, 8, 70193–70203, https://doi.org/10.1109/ACCESS.2020.2981623.

  21. Sun, Y., Yen, G.G., Yi, Z. 2019. IGD Indicator-Based Evolutionary algorithm for Many-Objective Optimization problems, 23, 173–187.

  22. Yuan, B., Li, B., Chen, H., Yao, X. 2015. A new evolutionary algorithm with structure mutation for the maximum balanced biclique problem, IEEE Trans. Cybern., 45, 1040–1053, https://doi.org/10.1109/TCYB.2014. 2343966.

  23. Zhu, H., Alonso-Mora, J., 2019. Chance-Constrained Collision avoidance for MAVs in dynamic environments, IEEE Robot. Autom. Lett., 4, 776–783, https://doi.org/10.1109/LRA.2019.2893494.


ARTICLE INFORMATION

Received: 2020-08-29

Accepted: 2020-09-26
Available Online: 2021-03-01


Cite this article:

Saravanarajan, V.S., Chen, R.-C., Dewi, C., Chen, L.-S. 2021. Solving unbounded knapsack problem using evolutionary algorithms with bound constrained strategy. International Journal of Applied Science and Engineering, 18, 2020205. https://doi.org/10.6703/IJASE.202103_18(1).002

  Copyright The Author(s). This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are cited.

Other people also read ...