یک الگوریتم ژنتیک جدید برای مسئله فروشنده دوره گرد متوازن رنگ شده مقیاس بزرگ
Abstract
1. Introduction
2. Colored balanced traveling salesman problem
3. NGA for CBTSP
4. Experiments and analysis
5. Conclusion and future works
Acknowledgments
References
Abstract
The paper gives an applicable model called colored balanced traveling salesman problem (CBTSP), it is utilized to model optimization problems with partially overlapped workspace such as the scheduling and deploying of the resources and goods. CBTSP is NP-hard problem, the traditional nature-inspired algorithms, such as genetic algorithm (GA), hill-climbing GA and simulated annealing GA, are easy to fall into local optimum. In order to improve it, the paper proposes a novel genetic algorithm (NGA) based on ITÖ process to solve CBTSP. First of all, NGA utilizes the dual-chromosome coding to represent solution of this problem, and then updates the solution by the crossover and mutation operator. During the process of crossover operator, the length of crossover can be affected by activity intensity, which is directly proportional to environmental temperature and inversely proportional to particle radius. The experiments verify that NGA can demonstrate better solution quality than the compared algorithms for large scale CBTSP.