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

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

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

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

1.1 遍歷路徑的編碼

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

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

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

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

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

1.3 新型定向交叉算子

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

實(shí)際操作中，將兩條父類染色體拆分為基因片段（包含兩個(gè)城市的集合），將多目標(biāo)參數(shù)按照一定比例結(jié)合，構(gòu)造基因片段之間的評(píng)價(jià)標(biāo)準(zhǔn)，用貪心的策略進(jìn)行重組，考慮到父類遍歷路徑片段的重復(fù)情況，重組時(shí)無(wú)法生成符合要求的合理遍歷路徑，在合成遍歷路徑時(shí)，再次運(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） }；然后，將每一個(gè)路徑片段的單個(gè)目標(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）}路徑片段集，對(duì)應(yīng)的遍歷路徑為{1-5-2-4-3}。在實(shí)驗(yàn)中發(fā)現(xiàn)，解集兩端的延展性較差，所以給出1/3的迭代次數(shù)，進(jìn)行解集兩端的收斂，保證解集的完整性。

2 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

作者簡(jiǎn)介

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

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

作者單位

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

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