A generic bee colony optimization framework for combinatorial optimization problems

• Main Author: Wong, Li Pei
• Other Authors: He Bingsheng
• Format: Theses and Dissertations
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
• Online Access: https://hdl.handle.net/10356/48091
• Institution: Nanyang Technological University

Combinatorial optimization is one of the areas that has been studied intensively in computer science and operations research. Solving a Combinatorial Optimization Problem (COP) is NP-hard [55] and it involves finding a set of feasible solutions with the least-cost in a discrete search space [90]. It becomes complicated when the COP being solved is with large scale data, constraints and variables. The significance of COPs can be found in various types of industrial applications. Examples include finding an optimized scan chains route in integrated chips testing and job scheduling in manufacturing industries. This thesis presents a generic Bee Colony Optimization (BCO) framework for solving different COPs. The framework realizes computationally the collective intelligence shown in bee foraging behaviour. In a bee colony, bees are sent out of their beehive and travel across different locations to discover and to collect food. When a bee found a food source, it would perform waggle dance upon flying back to its hive. Its intension is to recruit more bees towards the newly discovered food source. Waggle dance operates as an important communication tool among bees. This collective intelligence shown in the bee foraging behaviour is modelled algorithmically as a generic framework to solve different COPs. The generic BCO framework is designed using the object-oriented approach. A set of domain independent and abstract classes are defined. The domain independent classes implement the bee foraging behaviour and the abstract classes act as an interface to interact with domain specific classes. To solve a COP with the proposed framework, the implementation of domain specific tasks as defined in the abstract classes needs to be supplied to the framework. Besides the advantage of solving different COPs, the proposed BCO framework can be modified or enhanced flexibly and the effect of the enhancement will be applicable across all different COPs being solved.