استفاده از الگوریتم کلونی زنبور مصنوعی برای مشکل فروشنده سیار
Abstract
1- Introduction
2- Related work
3- The proposed model
4- Results and discussion
5- Conclusions
References
Abstract
The Artificial Bee Colony (ABC) algorithm is a swarm intelligence approach which has initially been proposed to solve optimisation of mathematical test functions with a unique neighbourhood search mechanism. This neighbourhood search mechanism could not be directly applied to combinatorial discrete optimisation problems. In order to tackle combinatorial discrete optimisation problems, the employed and onlooker bees need to be equipped with problem-specific perturbative heuristics. However, a large variety of problem-specific heuristics are available, and it is not an easy task to select an appropriate heuristic for a specific problem. In this paper, a hyper-heuristic method, namely a Modified Choice Function (MCF), is applied such that it can regulate the selection of the neighbourhood search heuristics adopted by the employed and onlooker bees automatically. The Lin-Kernighan (LK) local search strategy is integrated to improve the performance of the proposed model. To demonstrate the effectiveness of the proposed model, 64 Traveling Salesman Problem (TSP) instances available in TSPLIB are evaluated. On average, the proposed model solves the 64 instances to 0.055% from the known optimum within approximately 2.7 min. A performance comparison with other state-of-the-art algorithms further indicates the effectiveness of the proposed model.
Introduction
A computational optimisation methodology involves finding feasible solutions from a finite set of solutions, and identifying only the optimal solution(s). Swarm intelligence algorithms constitute a sub-class of computational optimisation methodology [1]. Swarm intelligence algorithms are developed based on emergence of collective behaviours pertaining to a population of interacting individuals in adapting to the local and/or global environments. Examples of swarm intelligence algorithms include Particle Swarm Optimisation (PSO) [2], Ant Colony Optimisation (ACO) [3], Bat Algorithm (BA) [4], Firefly Algorithm (FA) [5], Cuckoo Search Algorithm (CSA) [6], and bee-inspired algorithms [7–9]. Bees are highly organised social insects. Their survival relies on assigning an important task to each bee in a cooperative mode. The tasks include reproduction, foraging, and constructing hive. Within these tasks, foraging is one of the most important tasks, because the bee colony must ensure an undisrupted supply of food to survive. The food foraging behaviours of bees can be computationally realised as algorithmic tools to solve various optimisation problems. The Artificial Bee Colony (ABC) algorithm is one of the popular beeinspired algorithms. Proposed by Karaboga [7], it is inspired by the foraging behaviours of honey bees in a colony. In the ABC algorithm, a food source represents a possible solution to the optimisation problem in the search space, and the nectar amount of the food source represents the fitness of that solution. The ABC algorithm defines three types of bees: employed bees, onlooker bees, and scout bees. An employed bee looks for new food sources around the neighbourhood of the food source that it has previously visited. An onlooker bee observes dances and selects a food source to visit. It tends to select good food sources from those found by the employed bees. A scout bee searches for new food sources randomly. The mechanism of the ABC algorithm is as follows. The employed bees first perform a neighbourhood search nearby the food source in their memory (i.e. solution). Then, they go back to the hive and perform dances. The dances inform the onlooker bees about the fitness of each solution. Each onlooker bee observes and selects a food source to perform another neighbourhood search based on a probability proportional to the food source fitness (i.e. a roulette wheel selection). The onlooker bees tend to select good food sources from those found by the employed bees. The employed and onlooker bees perform neighbourhood search by perturbing an existing solution to produce a new solution.