IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i11p1233-d564032.html
   My bibliography  Save this article

Quantum-Inspired Differential Evolution with Grey Wolf Optimizer for 0-1 Knapsack Problem

Author

Listed:
  • Yule Wang

    (College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

  • Wanliang Wang

    (College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract

The knapsack problem is one of the most widely researched NP-complete combinatorial optimization problems and has numerous practical applications. This paper proposes a quantum-inspired differential evolution algorithm with grey wolf optimizer (QDGWO) to enhance the diversity and convergence performance and improve the performance in high-dimensional cases for 0-1 knapsack problems. The proposed algorithm adopts quantum computing principles such as quantum superposition states and quantum gates. It also uses adaptive mutation operations of differential evolution, crossover operations of differential evolution, and quantum observation to generate new solutions as trial individuals. Selection operations are used to determine the better solutions between the stored individuals and the trial individuals created by mutation and crossover operations. In the event that the trial individuals are worse than the current individuals, the adaptive grey wolf optimizer and quantum rotation gate are used to preserve the diversity of the population as well as speed up the search for the global optimal solution. The experimental results for 0-1 knapsack problems confirm the advantages of QDGWO with the effectiveness and global search capability for knapsack problems, especially for high-dimensional situations.

Suggested Citation

  • Yule Wang & Wanliang Wang, 2021. "Quantum-Inspired Differential Evolution with Grey Wolf Optimizer for 0-1 Knapsack Problem," Mathematics, MDPI, vol. 9(11), pages 1-21, May.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:11:p:1233-:d:564032
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/11/1233/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/11/1233/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jourdan, L. & Basseur, M. & Talbi, E.-G., 2009. "Hybridizing exact methods and metaheuristics: A taxonomy," European Journal of Operational Research, Elsevier, vol. 199(3), pages 620-629, December.
    2. Yangjun Gao & Fengming Zhang & Yu Zhao & Chao Li, 2018. "Quantum-Inspired Wolf Pack Algorithm to Solve the 0-1 Knapsack Problem," Mathematical Problems in Engineering, Hindawi, vol. 2018, pages 1-10, June.
    3. Vasquez, Michel & Vimont, Yannick, 2005. "Improved results on the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 165(1), pages 70-81, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wilbaut, Christophe & Hanafi, Said, 2009. "New convergent heuristics for 0-1 mixed integer programming," European Journal of Operational Research, Elsevier, vol. 195(1), pages 62-74, May.
    2. Verbiest, Floor & Cornelissens, Trijntje & Springael, Johan, 2019. "A matheuristic approach for the design of multiproduct batch plants with parallel production lines," European Journal of Operational Research, Elsevier, vol. 273(3), pages 933-947.
    3. Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
    4. Yuji Nakagawa & Ross J. W. James & César Rego & Chanaka Edirisinghe, 2014. "Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models," Management Science, INFORMS, vol. 60(3), pages 695-707, March.
    5. Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
    6. Laura Calvet & Rocio de la Torre & Anita Goyal & Mage Marmol & Angel A. Juan, 2020. "Modern Optimization and Simulation Methods in Managerial and Business Economics: A Review," Administrative Sciences, MDPI, vol. 10(3), pages 1-23, July.
    7. Framinan, Jose M. & Ruiz, Rubén, 2010. "Architecture of manufacturing scheduling systems: Literature review and an integrated proposal," European Journal of Operational Research, Elsevier, vol. 205(2), pages 237-246, September.
    8. Ghasemi, Mojtaba & Ghavidel, Sahand & Aghaei, Jamshid & Gitizadeh, Mohsen & Falah, Hasan, 2014. "Application of chaos-based chaotic invasive weed optimization techniques for environmental OPF problems in the power system," Chaos, Solitons & Fractals, Elsevier, vol. 69(C), pages 271-284.
    9. Yannick Vimont & Sylvain Boussier & Michel Vasquez, 2008. "Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem," Journal of Combinatorial Optimization, Springer, vol. 15(2), pages 165-178, February.
    10. Ruiz-Meza, José & Montoya-Torres, Jairo R., 2022. "A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines," Operations Research Perspectives, Elsevier, vol. 9(C).
    11. Kannan Govindan, 2016. "Evolutionary algorithms for supply chain management," Annals of Operations Research, Springer, vol. 242(2), pages 195-206, July.
    12. Guido, Rosita & Groccia, Maria Carmela & Conforti, Domenico, 2018. "An efficient matheuristic for offline patient-to-bed assignment problems," European Journal of Operational Research, Elsevier, vol. 268(2), pages 486-503.
    13. A Volgenant & I Y Zwiers, 2007. "Partial enumeration in heuristics for some combinatorial optimization problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(1), pages 73-79, January.
    14. Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong, 2019. "Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 35-48.
    15. Saïd Hanafi & Christophe Wilbaut, 2011. "Improved convergent heuristics for the 0-1 multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 183(1), pages 125-142, March.
    16. Deane, Jason & Agarwal, Anurag, 2012. "Scheduling online advertisements to maximize revenue under variable display frequency," Omega, Elsevier, vol. 40(5), pages 562-570.
    17. Elnaz Ghorbani & Tristan Fluechter & Laura Calvet & Majsa Ammouriova & Javier Panadero & Angel A. Juan, 2023. "Optimizing Energy Consumption in Smart Cities’ Mobility: Electric Vehicles, Algorithms, and Collaborative Economy," Energies, MDPI, vol. 16(3), pages 1-19, January.
    18. Davoudkhani, M. & Mahé, F. & Dourmad, J.Y. & Gohin, A. & Darrigrand, E. & Garcia-Launay, F., 2020. "Economic optimization of feeding and shipping strategies in pig-fattening using an individual-based model," Agricultural Systems, Elsevier, vol. 184(C).
    19. Villegas, Juan G. & Prins, Christian & Prodhon, Caroline & Medaglia, Andrés L. & Velasco, Nubia, 2013. "A matheuristic for the truck and trailer routing problem," European Journal of Operational Research, Elsevier, vol. 230(2), pages 231-244.
    20. Wilbaut, Christophe & Salhi, Saïd & Hanafi, Saïd, 2009. "An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 199(2), pages 339-348, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:11:p:1233-:d:564032. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.