用于求解TSP問(wèn)題的遺傳算法改進(jìn)

李慶　魏光村　高蘭　仇國(guó)華　肖新光

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

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

DOI：10. 11907/rjdk. 192387

中圖分類(lèi)號(hào)：TP301 ? 文獻(xiàn)標(biāo)識(shí)碼：A ??????????????? 文章編號(hào)：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