Generalist Algorithms Based on Automatic Algorithm Generation Applied to the Multidimensional Knapsack Problem
摘要
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.