استفاده از الگوریتم ژنتیک برای بهینه سازی مسئله فروشنده سیار
Abstract
I- Introduction
II- Genetic Algorithm
III- Travelling Salesman Problem
IV- Implementation
V- Results and Analysis Authors Figures
VI- Conclusion And Implication For Future Work
References
Abstract
Optimization problem is which mainly focuses on finding feasible solution out of all possible solutions. Travelling salesman problem belongs to this one. As it is not possible to find its solution in definite polynomial time that is why it is considered as one of the NP-hard problem. This paper utilizes the optimization capability of genetic algorithm to find the feasible solution for TSP. The algorithm starts with the calculation of Euclidean distance between the towns to be visited by the salesman. Initial chromosome pool is generated using value encoding. Then best fit chromosomes are selected by applying roulette wheel selection which then goes through m-point crossover. Now we apply interchange mutation on the offsprings generated before. Now this whole process is repeated until the convergence of genetic algorithm.
CONCLUSION AND IMPLICATION FOR FUTURE WORK
Heuristic methods and genetic approaches are the most appropriate ways to solve the travelling salesman problem. Multiple optimal solutions can be obtained for this problem by using various combinations of selection, crossover and mutation techniques. We have surveyed many approaches and many combinations of genetic operators for this problem and the used combination of genetic operators in this paper is the optimized one among them. For future extension of this work we can use multiple combinations of hybrid genetic operators. The approach used can be operated in diverse network optimization problems like vehicle navigation routing model, task scheduling models, Chinese postman problem and logistic networks.