<p>Many real-world problems involve complex combinatorial optimization challenges that are often interconnected. Traditional approaches solve these problems in isolation, requiring significant computational effort and expert knowledge. Moreover, heuristics designed for one problem are rarely reusable for others. This paper introduces a novel hybrid heuristic transfer framework that enables the adaptation and reuse of learned heuristics across different optimization problems. The framework consists of three key phases: (1) Learning, where heuristics are evolved using a Dual-Tree Genetic Programming approach applied to a source problem; (2) Knowledge Transfer, which leverages instance-based and feature-based selection mechanisms to identify and adapt the most effective heuristics for a target problem; and (3) Optimization, where a hybrid offline-online heuristic selection mechanism is employed. The offline phase integrates Neural Networks (NNs) to model relationships within problem instances, capturing intricate dependencies and enhancing generalization. The online phase dynamically adapts heuristic selection based on statistical similarity between source and target problem instances. We evaluate the framework using two generalizations of classic combinatorial problems: the Multi-Capacity Bin Packing Problem (MCBPP) and the Multi-Dimensional Knapsack Problem (MKP). Experimental results demonstrate that heuristics learned from a small set of MCBPP instances significantly improve solutions for MKP, outperforming state-of-the-art methods in most cases while reducing computational cost. The proposed approach advances heuristic learning and transferability, offering a scalable solution for complex optimization problems.</p>

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

A hybrid heuristic transfer framework for combinatorial optimization: dual-tree genetic programming and neural networks for bin packing and knapsack problems

  • Ayad Turky,
  • Nasser R. Sabar,
  • Andy Song

摘要

Many real-world problems involve complex combinatorial optimization challenges that are often interconnected. Traditional approaches solve these problems in isolation, requiring significant computational effort and expert knowledge. Moreover, heuristics designed for one problem are rarely reusable for others. This paper introduces a novel hybrid heuristic transfer framework that enables the adaptation and reuse of learned heuristics across different optimization problems. The framework consists of three key phases: (1) Learning, where heuristics are evolved using a Dual-Tree Genetic Programming approach applied to a source problem; (2) Knowledge Transfer, which leverages instance-based and feature-based selection mechanisms to identify and adapt the most effective heuristics for a target problem; and (3) Optimization, where a hybrid offline-online heuristic selection mechanism is employed. The offline phase integrates Neural Networks (NNs) to model relationships within problem instances, capturing intricate dependencies and enhancing generalization. The online phase dynamically adapts heuristic selection based on statistical similarity between source and target problem instances. We evaluate the framework using two generalizations of classic combinatorial problems: the Multi-Capacity Bin Packing Problem (MCBPP) and the Multi-Dimensional Knapsack Problem (MKP). Experimental results demonstrate that heuristics learned from a small set of MCBPP instances significantly improve solutions for MKP, outperforming state-of-the-art methods in most cases while reducing computational cost. The proposed approach advances heuristic learning and transferability, offering a scalable solution for complex optimization problems.