Monday, October 27, 2008

Bee Colony Optimization

The bee colony optimization algorithm is inspired by the behaviour of a honey bee colony in nectar collection. This biologically inspired approach is currently being employed to solve continuous optimization problems, training neural networks, mechanical and electronic components design optimization, combinatorial optimization problems such as job shop scheduling, the internet server optimization problem, the travelling salesman problem, etc.

Bee colony optimization in the job shop scheduling problem

Bee Colony Model for JSSP

The honey bees' effective foraging strategy can be applied to Job Shop Scheduling Problems.
A feasible solution in a Job Shop Scheduling Problem is a complete schedule of operations specified in the problem. We can think of each solution as a path from the hive to the food source. The figure on the right illustrates such an analogy
The makespan of the solution is analogous to the profitability of the food source in terms of distance and sweetness of the nectar. Hence, the shorter the makespan, the higher the profitability of the solution path.
We can thus maintain a colony of bees, where each bee will traverse a potential solution path. Once a feasible solution is found, each bee will return to the hive to perform a Waggle Dance. The Waggle Dance will be represented by a list of Elite Solutions (Chong et al., 2006), from which other bees can choose to follow another bee's path. Bees with a better makespan will have a higher probability of adding its path to the list of Elite Solutions, promoting a convergence to an optimal solution.
Using the above scheme, the natural honey bee's self organizing foraging strategy can be applied to the Job Shop Scheduling Problem.