This work presents a hierarchical evolutionary approach for constructing generalist algorithms from specialized models, applied to the Multidimensional Knapsack Problem (MKP), a classical NP-hard combinatorial optimization challenge. In the first phase, Genetic Programming (GP) was employed to evolve syntax trees and generate ten specialist algorithms, each trained on a homogeneous cluster of MKP instances obtained via K-Means, using multidimensional vector representations of the instances. These models achieved low relative errors, demonstrating effective local adaptation. In the second phase, the specialized algorithms were used as terminal nodes in a new evolutionary process that trained syntax trees on a diverse dataset comprising representative instances from all clusters. This architecture enabled the composite models to capture shared regularities across clusters and improve their generalization capability. The results show that the hierarchical algorithms not only outperform the specialists in several groups but also exhibit lower variability in performance. Notably, one of the composite models achieved a significant reduction in relative error across most test groups. These findings highlight the potential of hierarchical evolutionary learning as a strategy for generating robust, adaptive, and transferable solutions in NP-hard problems.

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

Generalist Algorithms Based on Automatic Algorithm Generation Applied to the Multidimensional Knapsack Problem

  • Cristian Inzulza,
  • Caio Bezares,
  • Franco Cornejo,
  • Victor Parada

摘要

This work presents a hierarchical evolutionary approach for constructing generalist algorithms from specialized models, applied to the Multidimensional Knapsack Problem (MKP), a classical NP-hard combinatorial optimization challenge. In the first phase, Genetic Programming (GP) was employed to evolve syntax trees and generate ten specialist algorithms, each trained on a homogeneous cluster of MKP instances obtained via K-Means, using multidimensional vector representations of the instances. These models achieved low relative errors, demonstrating effective local adaptation. In the second phase, the specialized algorithms were used as terminal nodes in a new evolutionary process that trained syntax trees on a diverse dataset comprising representative instances from all clusters. This architecture enabled the composite models to capture shared regularities across clusters and improve their generalization capability. The results show that the hierarchical algorithms not only outperform the specialists in several groups but also exhibit lower variability in performance. Notably, one of the composite models achieved a significant reduction in relative error across most test groups. These findings highlight the potential of hierarchical evolutionary learning as a strategy for generating robust, adaptive, and transferable solutions in NP-hard problems.