CAJ | 학술논문

针对旅行推销员问题的遗传算法进行大规模运算需要耗费很多时间,而且易造成局部最优的问题,通过改进典型遗传算法的交叉算子,提出一种改进的遗传算法,动态调整交叉和变异概率以降低染色体近亲繁殖的可能,有效地控制了进化过程。与其他算法相比,不仅有效地提高了算法的收敛速度,并且获得了更好的性能。用中国100个城市的TSP问题对提出的算法进行实验验证。实验结果表明,改进后的遗传算法相对于其他遗传算法具有更强的全局寻优性能和更少的收敛时间。
침대여행추소원문제적유전산법진행대규모운산수요모비흔다시간,이차역조성국부최우적문제,통과개진전형유전산법적교차산자,제출일충개진적유전산법,동태조정교차화변이개솔이강저염색체근친번식적가능,유효지공제료진화과정。여기타산법상비,불부유효지제고료산법적수렴속도,병차획득료경호적성능。용중국100개성시적TSP문제대제출적산법진행실험험증。실험결과표명,개진후적유전산법상대우기타유전산법구유경강적전국심우성능화경소적수렴시간。
The large-scale operation of genetic algorithm of traveling salesman problem (traveling salesman problem, TSP) requires a lot of time, and is easy to make into local optimum. Performance of the typical genetic algorithm (GA) in solving the traveling salesman problem is not ideal. Through the improvement of the typical of crossover operator of genetic algorithm, and in order to solve TSP problem, this paper proposes an improved genetic algorithm, which dynamically adjusts the probabili- ties of crossover and mutation in order to reduce the possible chromosomal inbreeding coefficient, and effectively controls the evolutionary process. Compared with other algorithms, this algorithm effectively improves the speed of convergence and obtains better performance. This algorithm is verified on the TSP problem in 100 cities in China. The results show that the improved genetic algorithm has better global searching performance and uses less convergence time