針對NSGA-II算法求解多目標(biāo)TSP問題的易出現(xiàn)未成熟收斂、計算時間復(fù)雜度高且穩(wěn)定性不夠等不足，通過設(shè)計面向多目標(biāo)TSP問題的新型定向交叉算子，并采用權(quán)重聚合方法將標(biāo)準(zhǔn)化后的多目標(biāo)空間轉(zhuǎn)化為單目標(biāo)空間，借助貪心策略重組基因來增加算法的收斂速度而減少交叉次數(shù)；與此同時，利用定向交叉思想，尋找多目標(biāo)空間上的邊界解來增強(qiáng)算法的分布性和對新空間的探索能力，最終實現(xiàn)算法優(yōu)化效率的提升。通過在多目標(biāo)TSP標(biāo)準(zhǔn)測試數(shù)據(jù)集上的仿真實驗，結(jié)果表明新型定向交叉能有效地均衡尋優(yōu)過程中收斂性與分布性，在優(yōu)化效率上明顯好于改進(jìn)前的算法。

【關(guān)鍵詞】多目標(biāo)TSP問題 定向交叉 NSGA-II 貪心策略 收斂性 分布性

1 新型定向交叉在NSGA-II求解多目標(biāo)TSP問題中的應(yīng)用

在2002年，Deb等學(xué)者在NSGA基礎(chǔ)上提出了快速帶精英策略的NSGA-II算法。主要改進(jìn)之處有：首先，設(shè)計了基于合并父代種群和子代種群的精英保留策略；其次，通過快速非支配排序策略降低算法計算復(fù)雜度；再者，采用擁擠距離策略代替適應(yīng)度共享策略來實現(xiàn)更具可操作性的非支配個體排序方法。

1.1 遍歷路徑的編碼

根據(jù)多目標(biāo)TSP優(yōu)化問題的特點，采用自然編碼方式，一條n個城市的遍歷路徑表示為，其中表示第i個城市的序號，取值為從1到n不重復(fù)的自然數(shù)。例如{1， 3， 6， 8， 5， 7， 4， 2， 9}，表示城市路線為{1-3-6-8-5-7-4-2-9-1}。

遍歷路徑是一個首尾相連的回路，因此會存在冗余路徑。例如路徑{1-3-6-8-5-7-4-2-9}和路徑{3-6-8-5-7-4-2-9-1}表達(dá)同一條路徑，所以在初始化和交叉過程中，為排除冗余路徑，在實現(xiàn)時始終保持城市1為首位，以便減小重復(fù)搜索，提高搜索效率，保證解集的覆蓋度。

1.2 不同優(yōu)化目標(biāo)的歸一化

多目標(biāo)TSP優(yōu)化問題不同于傳統(tǒng)的單目標(biāo)TSP優(yōu)化問題，擁有多個目標(biāo)函數(shù)，且往往相互沖突，無法同時達(dá)到最優(yōu)。與此同時函數(shù)值之間難以比較，所以導(dǎo)致很多在解決單目標(biāo)TSP優(yōu)化問題的有效算法，在面對多目標(biāo)TSP問題時難以發(fā)揮，為了解決這個問題，采用標(biāo)準(zhǔn)化的思想，將不同的目標(biāo)函數(shù)值，投影到0到1之間，從而進(jìn)行組合比較。

遍歷全連通圖，獲取每一個目標(biāo)的最大值和最小值FMax（j）和FMin（j），將兩城市之間不同代價距離映射到0到1之間。

1.3 新型定向交叉算子

交叉操作是進(jìn)化算法中最重要的遺傳操作之一，直接關(guān)系到算法優(yōu)化效率。針對NSGA-II算法求解多目標(biāo)TSP問題的易出現(xiàn)未成熟收斂、計算時間復(fù)雜度高且穩(wěn)定性不高等不足，通過設(shè)計面向多目標(biāo)TSP問題的新型定向交叉算子，交叉方向隨著迭代次數(shù)改變，快速生成目標(biāo)之間一定比例的解，并在此基礎(chǔ)上生成新的個體，將多目標(biāo)問題在交叉時轉(zhuǎn)化為單目標(biāo)問題，大大減少進(jìn)化算法中生成劣解后代數(shù)量，大幅提高運(yùn)算效率。

實際操作中，將兩條父類染色體拆分為基因片段（包含兩個城市的集合），將多目標(biāo)參數(shù)按照一定比例結(jié)合，構(gòu)造基因片段之間的評價標(biāo)準(zhǔn)，用貪心的策略進(jìn)行重組，考慮到父類遍歷路徑片段的重復(fù)情況，重組時無法生成符合要求的合理遍歷路徑，在合成遍歷路徑時，再次運(yùn)用貪心策略，將未包含的路徑片段添加到合理遍歷路徑中。

下面，假設(shè)城市數(shù)量為5，目標(biāo)數(shù)量為2。例如兩條父類遍歷路徑分別為：{1-5-2-4-3}和{1-2-5-4-3}。首先，將其拆分為路徑片段：{（1-5）， （5-2）， （2-4）， （4-3）， （3-1）}和{（1-2）， （2-5）， （5-4）， （4-3）， （3-1） }；然后，將每一個路徑片段的單個目標(biāo)值f1，f2按照權(quán)重參數(shù)p∈[0，1]組合，生成新的目標(biāo)值f，即為f=f1*（p）+f2*（1-p）；根據(jù)新生成的f將以上路徑片段根據(jù)權(quán)重從小到大進(jìn)行排序，假如排序后得到的有序序列為： （1-5）， （5-2）， （2-5）， （2-4）， （4-3）， （4-3）， （3-1）， （3-1）， （1-2）， （5-4）；接著，采用貪心策略，從頭取出互不沖突的路徑片段，組合生成符合要求的合理遍歷路徑，即為{（1-5）， （5-2）， （2-4）， （4-3）， （3-1）}路徑片段集，對應(yīng)的遍歷路徑為{1-5-2-4-3}。在實驗中發(fā)現(xiàn)，解集兩端的延展性較差，所以給出1/3的迭代次數(shù)，進(jìn)行解集兩端的收斂，保證解集的完整性。

2 結(jié)束語

根據(jù)多目標(biāo)TSP優(yōu)化問題的特點，針對NSGA-II算法求解多目標(biāo)TSP問題的易出現(xiàn)未成熟收斂、計算時間復(fù)雜度高且穩(wěn)定性不高等不足，通過設(shè)計面向TSP問題的新型定向交叉算子，并采用權(quán)重聚合方法將標(biāo)準(zhǔn)化后的多目標(biāo)空間轉(zhuǎn)化為單目標(biāo)空間，借助貪心策略重組基因來增加算法的收斂速度而減少交叉次數(shù)；與此同時，利用定向交叉思想，尋找多目標(biāo)空間上的邊界解來增強(qiáng)算法的分布性和對新空間的探索能力，最終實現(xiàn)算法優(yōu)化效率的提升。最后通過在單目標(biāo)和多目標(biāo)TSP優(yōu)化問題的仿真實驗，驗證了新型定向交叉算子的有效性，大大地提高了NSGA-II算法求解多目標(biāo)TSP問題的效果。下一步將針對解集的完整性和分布性，進(jìn)一步優(yōu)化定向交叉算子的細(xì)節(jié)設(shè)計，進(jìn)一步提高交叉操作的適用性。

參考文獻(xiàn)

[1]陳國良，王煦法，莊鎮(zhèn)泉等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，2001.

[2]公茂果，焦李成，楊咚咚，馬文萍.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報，2009（02）：271-289.

[3]王輝.用遺傳算法求解TSP問題[J].計算機(jī)與現(xiàn)代化，2009（07）：12-15，25.

[4]雷玉梅.基于改進(jìn)遺傳算法的大規(guī)模TSP問題求解方案[J].計算機(jī)與現(xiàn)代化，2015（02）：34-39.

[5]游道明，陳堅.用蟻群算法解決多目標(biāo)TSP問題[J].小型微型計算機(jī)系統(tǒng)，2003，24（10）：1808-1811.

作者簡介

劉勝軍（1974-），男，安徽省和縣人。計算機(jī)專業(yè)碩士學(xué)位。主要研究方向為機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等。

耿煥同（1973-），男，安徽省績溪縣人。教授，博士生導(dǎo)師。主要研究方向為計算智能與約束多目標(biāo)優(yōu)化、氣象資料預(yù)處理。

作者單位

1.安徽中科大國禎信息科技有限責(zé)任公司 安徽省合肥市 230008

2.南京信息工程大學(xué)濱江學(xué)院 江蘇省南京市 210044