TY - GEN
T1 - A mini-swarm for the quadratic knapsack problem
AU - Xie, Xiao Feng
AU - LIU, Jiming
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34548776496&partnerID=8YFLogxK
U2 - 10.1109/SIS.2007.368045
DO - 10.1109/SIS.2007.368045
M3 - Conference proceeding
AN - SCOPUS:34548776496
SN - 1424407087
SN - 9781424407088
T3 - Proceedings of the 2007 IEEE Swarm Intelligence Symposium, SIS 2007
SP - 190
EP - 197
BT - Proceedings of the 2007 IEEE Swarm Intelligence Symposium, SIS 2007
T2 - 2007 IEEE Swarm Intelligence Symposium, SIS 2007
Y2 - 1 April 2007 through 5 April 2007
ER -