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

Exploring Initialization Strategies for Metaheuristic Optimization: Case Study of the Set-Union Knapsack Problem

Author

Listed:
  • José García

    (Escuela de Ingeniería de Construcción y Transporte, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362804, Chile)

  • Andres Leiva-Araos

    (Facultad de Ingeniería, Centro de Transformación Digital, Universidad del Desarrollo, Santiago 7610658, Chile)

  • Broderick Crawford

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • Ricardo Soto

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • Hernan Pinto

    (Escuela de Ingeniería de Construcción y Transporte, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362804, Chile)

Abstract

In recent years, metaheuristic methods have shown remarkable efficacy in resolving complex combinatorial challenges across a broad spectrum of fields. Nevertheless, the escalating complexity of these problems necessitates the continuous development of innovative techniques to enhance the performance and reliability of these methods. This paper aims to contribute to this endeavor by examining the impact of solution initialization methods on the performance of a hybrid algorithm applied to the set union knapsack problem (SUKP). Three distinct solution initialization methods, random, greedy, and weighted, have been proposed and evaluated. These have been integrated within a sine cosine algorithm employing k-means as a binarization procedure. Through testing on medium- and large-sized SUKP instances, the study reveals that the solution initialization strategy influences the algorithm’s performance, with the weighted method consistently outperforming the other two. Additionally, the obtained results were benchmarked against various metaheuristics that have previously solved SUKP, showing favorable performance in this comparison.

Suggested Citation

  • José García & Andres Leiva-Araos & Broderick Crawford & Ricardo Soto & Hernan Pinto, 2023. "Exploring Initialization Strategies for Metaheuristic Optimization: Case Study of the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 11(12), pages 1-20, June.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:12:p:2695-:d:1170756
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Yang, Xinan & Vernitski, Alexei & Carrea, Laura, 2016. "An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters," European Journal of Operational Research, Elsevier, vol. 252(3), pages 985-994.
    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. José García & José Lemus-Romani & Francisco Altimiras & Broderick Crawford & Ricardo Soto & Marcelo Becerra-Rozas & Paola Moraga & Alex Paz Becerra & Alvaro Peña Fritz & Jose-Miguel Rubio & Gino Astor, 2021. "A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 9(20), pages 1-19, October.
    2. Yanhong Feng & Haizhong An & Xiangyun Gao, 2018. "The Importance of Transfer Function in Solving Set-Union Knapsack Problem Based on Discrete Moth Search Algorithm," Mathematics, MDPI, vol. 7(1), pages 1-25, 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:11:y:2023:i:12:p:2695-:d:1170756. 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.