A Mini-Swarm for the Quadratic Knapsack Problem
Xiaofeng Xie, Jiming Liu · 2007
The 0-1 quadratic knapsack problem (QKP) is a hard computational problem, which is a generalization of the knapsack problem (KP). In this paper, a mini-swarm system is presented. Each agent, realized with minor declarative knowledge and simple behavioral rules, searches on a structural landscape of the problem through the guided generate-and-test behavior under the law of socially biased individual learning, and cooperates with others by indirect interactions. The formal decomposition of behaviors allows understanding and reusing elemental operators, while utilizes the heuristic information on the landscape. The results on a collection of the QKP instances by mini-swarm versions are compared with that of both a branch-and-bound algorithm and a greedy genetic algorithm, which show its effectiveness