• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

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

      2017-04-14 15:33劉勝軍
      電子技術(shù)與軟件工程 2017年6期
      關(guān)鍵詞:收斂性

      針對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

      猜你喜歡
      收斂性
      帶弱阻尼Navier-Stokes方程拉回吸引子的收斂性
      群體博弈的逼近定理及通有收斂性
      行間AANA隨機(jī)變量陣列加權(quán)和的完全矩收斂性
      Lp-混合陣列的Lr收斂性
      WOD隨機(jī)變量序列的完全收斂性和矩完全收斂性
      END隨機(jī)變量序列Sung型加權(quán)和的矩完全收斂性
      END隨機(jī)變量序列Sung型加權(quán)和的矩完全收斂性
      END序列加權(quán)和的完全收斂性
      隨機(jī)Kuramoto-Sivashinsky方程數(shù)值解的收斂性
      行為ND隨機(jī)變量陣列加權(quán)和的完全收斂性
      404 Not Found

      404 Not Found


      nginx
      册亨县| 奉节县| 出国| 明星| 太原市| 子长县| 汶川县| 泰兴市| 电白县| 邵阳市| 惠来县| 景宁| 桂平市| 蒙自县| 徐闻县| 手机| 剑河县| 巨野县| 读书| 金寨县| 开封县| 平遥县| 曲阳县| 宝应县| 康马县| 雷州市| 陵川县| 临邑县| 永安市| 湖南省| 乐安县| 金华市| 兴隆县| 佛山市| 洛浦县| 昌乐县| 佛山市| 澄迈县| 顺平县| 临清市| 娄底市|