Abstract—Travelling Salesman Problem (TSP) belongs to the class of NP-Complete problems. It has been proved that evolutionary algorithms are effective and efficient, with respect to the traditional methods for solving NP-Complete problems like TSP, with avoidance trapping in local minima areas. Artificial Bee Colony (ABC) is a new swarm-based optimization algorithm, which inspired by the foraging behavior of honey bees. In ABC, the neighborhood search strategy is employed in order to find better solutions around the previous ones.
The TSP represents the salesman who wants to visit a set of cities exactly once and finally turns back to the starting city. The objective is to determine the tour with minimum total distance.
To solve TSP using ABC algorithm, the position of a food source represents a possible tour and the nectar amount of a food source corresponds to the quality of the tour. In ABC model, the colony consists of three groups of bees: employed bees, onlookers and scouts.
Each employed bee goes to the food source area in her memory and determines a neighbor source, and then come back to the hive and begin dance in dance area. This dance is essential for colony communication, and contains three pieces of information regarding a flower patch: the direction in which it will be found, its distance from the hive and its quality rating (fitness). Provided that the nectar amount of the new selected source is higher than the previous one, the bee memorizes the new source position and forgets the old one. Otherwise she keeps the previous position in her memory. Each onlooker watches the dances of employed bees, and makes decision to choose the food source through the shared information from the dances. Then, some employed bees which found high quality solutions, are chosen as scouts. For each scout, some employed bees are determined to search for finding new food sources in the neighborhood of the solution of the scout.
Problem Representation
TSP can be represented as a graph πΊ=(π,πΈ), where π={1,2,...,π} is a set of nodes, and πΈ= π,π π,π π π} is the set of all connection edges between them. Each node represents a city, and each edge means the possible path between two related cities. The distance πππ is associated with edge (π,π) and represents the Euclidean distance from city π to city π “Eq. (1)”. The heuristic information is calculated before performing the main algorithm. So, the distances of all edges were calculated and saved.
πππ= sq((π₯π−π₯π)^2+(π¦π−π¦π)^2) -----1
Iteratively, after construction the solutions, the qualities of the gathered solutions are evaluated by the cost function, which is calculated by sum of the Euclidean distances of the consecutive edges within the our as “Eq. (2)”. Note that the πΆππ π‘π is corresponding to the ππππ.
No comments:
Post a Comment