Scholarlink

<p>The Bin Packing Problem (BPP) is a well-known NP-hard problem with numerous real-world applications. This study focuses on minimizing waste and maximum lateness in a one-dimensional version of the BPP, which is particularly relevant in industrial contexts. The goal is to develop a constructive heuristic algorithm that can be adapted to various situations. We model the BPP as a Deterministic Markov Decision Process with discrete state and action spaces, where policies are represented by arithmetic expressions involving state variables. This approach allows for a clearer explanation of the decision process, in contrast to other methods like neural networks. To evolve these policies, we use Genetic Programming (GP). Trained on a set of BPP instances, the resulting policies are effective for solving new, unseen instances. In the experimental study, we explore different GP settings, including varying sets of symbols. The results reveal valuable insights about the importance of state variables, indicating that a smaller selection of them may yield the best results. The evolved policies are compared with an exact method from the literature, achieving similar outcomes but with significantly less computational time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Genetic programming policies for bin packing in the framework of deterministic Markov decision process

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月16日

查看全文
  • Jesús Quesada,
  • Francisco J. Gil-Gala,
  • Marko Durasević,
  • María R. Sierra,
  • Ramiro Varela

摘要

The Bin Packing Problem (BPP) is a well-known NP-hard problem with numerous real-world applications. This study focuses on minimizing waste and maximum lateness in a one-dimensional version of the BPP, which is particularly relevant in industrial contexts. The goal is to develop a constructive heuristic algorithm that can be adapted to various situations. We model the BPP as a Deterministic Markov Decision Process with discrete state and action spaces, where policies are represented by arithmetic expressions involving state variables. This approach allows for a clearer explanation of the decision process, in contrast to other methods like neural networks. To evolve these policies, we use Genetic Programming (GP). Trained on a set of BPP instances, the resulting policies are effective for solving new, unseen instances. In the experimental study, we explore different GP settings, including varying sets of symbols. The results reveal valuable insights about the importance of state variables, indicating that a smaller selection of them may yield the best results. The evolved policies are compared with an exact method from the literature, achieving similar outcomes but with significantly less computational time.