• 
    

    
    

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

      采用基于遺傳算法的文化基因算法求解TSP問題

      2016-02-22 18:54:25譚立狀贠國瀟張家華
      科技視界 2016年5期
      關(guān)鍵詞:蟻群全局遺傳算法

      譚立狀+贠國瀟+張家華

      【摘 要】為更好地求解旅行商問題,本文提出了一種基于遺傳算法的文化基因算法。將2-opt作為局部搜索算子,融入到遺傳算法中,以加快遺傳算法的收斂速度和提高解的局部搜索能力。遺傳算法具有全局搜索的能力,2-opt具有局部搜索的特點,嵌入2-opt局部搜索的遺傳算法力圖在全局和局部搜索中達到平衡和融合,使之更有效地解決TSP問題。為檢測算法的性能,將該算法用于解決標準的TSP測試問題,并將測試結(jié)果與標準的遺傳算法及蟻群、粒子群等其它一些優(yōu)秀的算法的實驗結(jié)果做了比較,數(shù)值實驗結(jié)果證明了算法的有效性。

      【關(guān)鍵詞】遺傳算法;2-opt;文化基因算法;TSP問題

      3 實驗測試

      為了測試基于遺傳算法的文化基因算法在解決TSP問題方面的表現(xiàn),本文從TSP標準問題測試庫中提取了10個測試問題,將本文提出的算法用于求解這10個問題,并將算法的執(zhí)行結(jié)果與當(dāng)前其它一些優(yōu)秀的智能算法的運行結(jié)果進行了比較。

      在測試過程中,算法采用輪盤賭選擇和精英個體保留機制,單點順序交叉,基本位變異,終止代數(shù)為500,群體大小為200,交叉概率為0.9,變異概率為0.09。在Matlab環(huán)境下,算法對每個測試問題獨立進行10次。在相同的終止迭代條件下,表1給出了幾種算法所求得的最短路徑的平均值。以eil51、bier127、rat195、kroB200為例,圖5形象展示了算法在這些測試問題上獨立運行10次的結(jié)果。

      圖5 算法在4個測試問題上的求解結(jié)果

      從表1和圖5可以看出,相較于遺傳算法,本文提出的基于遺傳算法的文化基因算法所求得的路徑更短,可見融入2-opt局部搜索技術(shù)對于提高算法的性能是非常有效的。與當(dāng)前其它一些優(yōu)秀的算法,包括模擬退火、粒子群算法、蟻群算法相比,在這些測試問題上,基于遺傳算法的文化基因算法均表現(xiàn)了較好的性能,所求得的結(jié)果都優(yōu)于其它算法。如圖5所示,與其它算法相比,本文提出的算法還具有較好的穩(wěn)定性,魯棒性較強,對問題的敏感性較弱,比較適合解決此類TSP問題。

      4 總結(jié)

      遺傳算法在求解TSP問題時往往存在著求解質(zhì)量不是很高、容易陷入局部最優(yōu)等一系列問題。為了克服這些缺陷,本文提出了一種基于遺傳算法的文化基因算法。算法在求解過程中,將2-opt作為局部搜索算子,嵌入到遺傳算法中,以加快遺傳算法的收斂速度和提高局部搜索能力。遺傳算法具有全局搜索的能力,2-opt具有局部搜索的特點,嵌入2-opt局部搜索的遺傳算法力圖在全局和局部搜索中達到平衡和融合,使之更有效地解決TSP問題。

      為檢測算法的性能,將該算法在10個標準TSP測試問題上進行了測試,并將測試結(jié)果與標準的遺傳算法及蟻群、粒子群等其它一些優(yōu)秀的算法的實驗結(jié)果進行了對比,數(shù)值實驗結(jié)果表明,本文提出的算法在求解的質(zhì)量、穩(wěn)定性上均表現(xiàn)了較好的性能,算法的整體表現(xiàn)要優(yōu)于其它算法。可見融入局部搜索技術(shù)的全局搜索算法對于解決TSP問題是一條有效的途徑。探索其它更高效的局部搜索算法,將這些局部搜索技術(shù)有效地融合到遺傳算法、蟻群算法中,以更好地解決TSP問題將是作者今后進一步的研究工作。

      【參考文獻】

      [1]于瑩瑩,陳燕,李桃迎.改進的遺傳算法求解旅行商問題[J].控制與決策,2014, 29(8):1483-1488.

      [2]高海昌,馮博琴,朱利.智能優(yōu)化算法求解TSP 問題[J].控制與決策,2006,21(3): 241-247.

      [3]冀俊忠,黃振,劉椿年.一種快速求解旅行商問題的蟻群算法[J].計算機研究與發(fā)展,2009,46(6):968-978.

      [4]劉朝華,張英杰,章兢,等.蟻群算法與免疫算法的融合及其在TSP 中的應(yīng)用[J].控制與決策,2010,25(5):695-700.

      [5]Yannis Marinakis, Magdalene Marinaki. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J]. Computers and Operations Research, 2010, 37(3): 432-442.

      [6]Darrell Whitley, Doug Hains, Adele Howe. A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover[C]// Proc. of the 11th Int Conf. on Parallel Problem Solving from Nature. Berlin:Springer Heidelberg, 2010, 6283: 566-575.

      [7]Zakir H Ahmed. Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator[J]. Int J of Biometrics and Bioinformatics, 2010, 3(6): 96-105.

      [8]Murat Albayrak, Novruz Allahverdi. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J]. Expert Systems with Applications, 2011, 38(3): 1313-1320.

      [9]譚艷艷. 基于分解的多目標進化算法研究及應(yīng)用[D].西安電子科技大學(xué),西安,2013.

      [10]N. Noman, H. Iba. Accelerating differential evolution using an adaptive local search[J]. IEEE Trans. on Evol. Comput., 2008, 12(1): 107-125.

      [11]Yan-Yan Tan, Yong-Chang Jiao, Hong Li and Xin-kuan Wang. MOEA/D-SQA: a multi-objective memetic algorithm based on decomposition[J]. Engineering Optimization, 2012, 44(9): 1095-1115.

      [12]李宏.求解幾類復(fù)雜優(yōu)化問題的進化算法及其應(yīng)用[D].西安電子科技大學(xué),西安,2009.

      [13]P. Moscato. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms[J]. Caltech Concurrent Computation Program, C3P Report, 826, 1989.

      [14]劉漫丹.文化基因算法(Memetic Algorithm)研究進展[J].自動化技術(shù)與應(yīng)用, 2007,26(11):1-4.

      [15]Krasnogor N, Smith J. A tutorial for competent memetic algorithms: model, taxonomy, and design issues[J]. IEEE Transactions on Evolutionary Computation, 2005, 9(5): 474-488.

      [責(zé)任編輯:楊玉潔]

      猜你喜歡
      蟻群全局遺傳算法
      Cahn-Hilliard-Brinkman系統(tǒng)的全局吸引子
      量子Navier-Stokes方程弱解的全局存在性
      游戲社會:狼、猞猁和蟻群
      基于自適應(yīng)蟻群的FCM聚類優(yōu)化算法研究
      基于奇異值差分譜分析和蟻群算法的小波閾值降噪
      落子山東,意在全局
      金橋(2018年4期)2018-09-26 02:24:54
      基于自適應(yīng)遺傳算法的CSAMT一維反演
      一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
      基于遺傳算法和LS-SVM的財務(wù)危機預(yù)測
      基于改進的遺傳算法的模糊聚類算法
      佳木斯市| 侯马市| 九龙县| 北安市| 诏安县| 衡南县| 临夏县| 紫云| 柳州市| 德阳市| 芦山县| 卫辉市| 太康县| 马山县| 乌拉特中旗| 大同市| 会泽县| 威海市| 沧州市| 鸡东县| 富阳市| 南宫市| 望奎县| 福鼎市| 西吉县| 红安县| 桃源县| 荥阳市| 廉江市| 海阳市| 宜兴市| 瑞安市| 衡山县| 临夏县| 东乌| 浦北县| 宜章县| 固安县| 三河市| 邯郸市| 吉木乃县|