A mini-swarm for the quadratic knapsack problem

Xiao Feng Xie*, Jiming LIU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

17 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 2007 IEEE Swarm Intelligence Symposium, SIS 2007
Pages190-197
Number of pages8
DOIs
Publication statusPublished - 2007
Event2007 IEEE Swarm Intelligence Symposium, SIS 2007 - Honolulu, HI, United States
Duration: 1 Apr 20075 Apr 2007

Publication series

NameProceedings of the 2007 IEEE Swarm Intelligence Symposium, SIS 2007

Conference

Conference2007 IEEE Swarm Intelligence Symposium, SIS 2007
Country/TerritoryUnited States
CityHonolulu, HI
Period1/04/075/04/07

Scopus Subject Areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A mini-swarm for the quadratic knapsack problem'. Together they form a unique fingerprint.

Cite this