A Generic Bee Colony Optimization Framework for Combinatorial Optimization Problems

摘要

Combinatorial Optimization Problems (COPs) appear in various types of industrial applications. Finding an optimum solution for COPs with large scale of data, constraints and variables is NP-hard. This paper proposed a generic Bee Colony Optimization (BCO) framework for COPs that mimics the foraging process and waggle dance performed by bees. The framework is designed and organized such that it is able to deal with different COPs and any enhancement on the framework will be applicable across all COPs. Besides mimicking the natural metaphor in a bee colony, the framework is enriched with elitism, local optimization and adaptive pruning. The BCO framework is tested on benchmark problems from Traveling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP). The results show that out of 229 benchmark problem instances, 203 or 88.65% of them record an average of deviation percentage from known optimum with less then 1%.