李慶　魏光村　高蘭　仇國華　肖新光

摘 要：TSP問題是一個著名的NP難問題，提出一種改進的遺傳算法用來解決該問題。為了處理傳統(tǒng)遺傳算法中出現(xiàn)的早熟、收斂速度慢、收斂結(jié)果不準確等問題，分別在選擇、交叉、變異3個階段對算法進行優(yōu)化。設(shè)計一個動態(tài)適應(yīng)度函數(shù);放棄輪盤賭策略，采用無放回式優(yōu)良個體多復(fù)制原則，防止優(yōu)良基因被破壞;按照群體適應(yīng)度值分布，動態(tài)改變交叉率及變異率;引入相似度概念，避免出現(xiàn)近親交配現(xiàn)象，影響種族進化;尋找并記憶優(yōu)良基因簇，加快收斂過程。實驗結(jié)果證明，改進遺傳算法的優(yōu)化性能提升了17.04%。

關(guān)鍵詞：TSP問題;遺傳算法;動態(tài)適應(yīng)度函數(shù);優(yōu)良個體多復(fù)制;相似度;優(yōu)良基因簇

DOI：10. 11907/rjdk. 192387

中圖分類號：TP301 ? 文獻標(biāo)識碼：A ??????????????? 文章編號：1672-7800（2020）003-0116-04

Improvement of Genetic Algorithm for Solving TSP Problem

LI Qing1， WEI Guang-cun1，2， GAO Lan1， QIU Guo-hua1， XIAO Xin-guang1

（1.College of Computer Science and Engineering， Shandong University of Science and Technology，Qingdao 266590，China;

2.Department of Informaion Engineering，Shandong University of Science and Technology，Taian 271019，China）

Abstract：TSP problem is a well-known NP-hard problem. This paper proposes an improved genetic algorithm to solve this problem. In order to solve the problems of premature ripening， slow convergence and inaccurate convergence results in traditional genetic algorithms， the algorithm is optimized in three stages： selection， crossover and mutation. This paper designs a dynamic fitness function， then abandons the roulette strategy and adopts the principle of non-return-type good multiple replication to prevent the destruction of good genes; and then dynamically changes the crossover rate and mutation rate according to the distribution of group fitness values. The concept of similarity is introduced to avoid the phenomenon of inbreeding and affect ethnic evolution. The algorithm finds and memorizes good gene clusters， and accelerates the convergence process to design a dynamic fitness function. It abandons the roulette strategy and adopts the principle of non-return-type good individual multiple replication to prevent good genes from being destroyed. According to the group fitness value distribution， the crossover rate and mutation rate are dynamically changed; the concept of similarity is introduced to avoid inbreeding that affects racial evolution. Finally， find and remember good gene clusters are found and remembered to speed up the convergence process. Experiments show that the optimization performance of the improved genetic algorithm is improved by 17.04%.

Key Words： TSP problem; genetic algorithm; dynamic fitness function; excellent individual multiple replication; the concept of similarity; good gene clusters