Multi-objective traveling salesman problem: an ABC approach
- PDF / 4,098,337 Bytes
- 19 Pages / 595.224 x 790.955 pts Page_size
- 20 Downloads / 264 Views
Multi-objective traveling salesman problem: an ABC approach Indadul Khan1 · Manas Kumar Maiti2 · Krishnendu Basuli3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Using the concept of swap operation and swap sequence on the sequence of paths of a Traveling Salesman Problem(TSP) Artificial Bee Colony (ABC) algorithm is modified to solve multi-objective TSP. The fitness of a solution is determined using a rule following the dominance property of a multi-objective optimization problem. This fitness is used for the selection process of the onlooker bee phase of the algorithm. A set of rules is used to improve the solutions in each phase of the algorithm. Rules are selected according to their performance using the roulette wheel selection process. At the end of each iteration, the parent solution set and the solution sets after each phase of the ABC algorithm are combined to select a new solution set for the next iteration. The combined solution set is divided into different non-dominated fronts and then a new solution set, having cardinality of parent solution set, is selected from the upper-level non-dominated fronts. When some solutions are required to select from a particular front then crowding distances between the solutions of the front are measured and the isolated solutions are selected for the preservation of diversity. Different standard performance metrics are used to test the performance of the proposed approach. Different sizes standard benchmark test problems from TSPLIB are used for the purpose. Test results show that the proposed approach is efficient enough to solve multi-objective TSP. Keywords Multi-objective traveling salesmen problem · Artificial bee colony algorithm · Swap operation · Pareto optimal solution · Performance metric
1 Introduction Most of the real-life problems involve multiple conflicting goals, which leads to multi-objective optimizations, e.g., optimization of the profit of a company as well as the customer satisfaction; optimization of transportation time as well as transportation cost of a transport company; etc. In a multi-objective optimization problem (MOOP), as the Indadul Khan
[email protected] Manas Kumar Maiti [email protected] Krishnendu Basuli [email protected] 1
Department of Computer Science, Chandrakon Vidyasagar Mahavidyalaya, Paschim-Medinipur, West Bengal, 721201, India
2
Department of Mathematics, Mahishadal Raj College, Mahishadal, Purba-Medinipur, West Bengal, 721628, India
3
Department of Computer Science, West Bengal State University, Barasat, Kolkata, West Bengal, 700126, India
objective functions are generally conflicting in nature, the concept of optimality does not hold; rather the concept of pareto optimality takes place. Two solutions are called pareto optimal if each solution is better than the other with respect to at least one objective. One solution is said to be better than another one if it is better or equal with respect to all the objectives and strictly better with respect to at least
Data Loading...
