本站小編為你精心準(zhǔn)備了遺傳算法的TSP問題優(yōu)化方法分析參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要:針對傳統(tǒng)遺傳算法在巡回商旅問題優(yōu)化計(jì)算中存在的弊端———收斂速度慢，迭代次數(shù)多。在傳統(tǒng)遺傳算法基礎(chǔ)上，設(shè)計(jì)出一種加入人工選擇和定向突變的優(yōu)化改進(jìn)算法。該優(yōu)化算法通過人工方法保存具有有利變異個(gè)體和淘汰具有不利變異個(gè)體，有利變異個(gè)體進(jìn)行雜交和變異，從而提高遺傳算法的收斂速度，減少遺傳算法的迭代次數(shù)。同時(shí)針對遺傳算法易陷入局部最優(yōu)解的情況，在優(yōu)化算法中引入自適應(yīng)參數(shù)算法，針對遺傳算法的不同階段，實(shí)現(xiàn)雜交概率和變異概率的自適應(yīng)調(diào)節(jié)，防止算法陷入局部最優(yōu)解。最后，采用國際標(biāo)準(zhǔn)的tsp測試集(TSPLIB)對優(yōu)化算法的優(yōu)良性進(jìn)行驗(yàn)證，實(shí)驗(yàn)表明，對比其他算法，該優(yōu)化算法在TSP最優(yōu)解的質(zhì)量上提高10%左右。

關(guān)鍵詞:TSP;遺傳算法;人工選擇;定向突變;自適應(yīng)算法

1緒論

旅行商問題(TravelingSalesmanProblem，)是路徑規(guī)劃和組合優(yōu)化領(lǐng)域中著名的NP-hard問題［1，2］，網(wǎng)絡(luò)路由的大規(guī)模優(yōu)化［3］、超遠(yuǎn)距離泵送混凝土造價(jià)控制技術(shù)［4］、車輛路線設(shè)計(jì)［5］等均是典型的TSP。目前，求解TSP的算法可分為精確算法(exactalgorithm)和近似算法(approximationalgorithm)兩類。Wang等在分析基于智能算法的TSP求解方法優(yōu)缺點(diǎn)［6，7］的基礎(chǔ)上，指出遺傳算法受參數(shù)選擇和數(shù)據(jù)集分布結(jié)構(gòu)的影響最小，陷入局部最優(yōu)的概率最小。遺傳算法是以適應(yīng)度［8］為依據(jù)的逐代搜索過程。傳統(tǒng)的遺傳算法，往往存在諸多問題，如收斂速度慢，最優(yōu)解質(zhì)量差，容易陷入局部最優(yōu)等。針對傳統(tǒng)遺傳算法在旅行商問題求解中存在的弊端，本文對傳統(tǒng)遺傳算法的幾個(gè)步驟進(jìn)行優(yōu)化，提出改進(jìn)的遺傳算法———在原有的基礎(chǔ)上加入新型的進(jìn)化策略，從而提升最優(yōu)解的質(zhì)量，降低最優(yōu)解的誤差率，有效控制遺傳算法早熟收斂性。

2遺傳算法優(yōu)化改進(jìn)

2．1人工選擇法傳統(tǒng)遺傳算法［9］雜交過程的實(shí)現(xiàn)往往是從上一代種群中隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行雜交，對于雜交生成的子代，采取直接替代父代的方法，但是在替代的過程中存在子代的適應(yīng)度低于父代，出現(xiàn)劣勢個(gè)體的情況，使整個(gè)算法的收斂速度變慢，在遺傳代數(shù)一定的條件下，最終解的誤差率上升。針對上述情況，本文在傳統(tǒng)雜交過程和變異基礎(chǔ)上進(jìn)行優(yōu)化。我們對雜交生成的四個(gè)子代個(gè)體的適應(yīng)度進(jìn)行重新排序，選擇其中最優(yōu)秀的兩個(gè)個(gè)體進(jìn)入下一代種群，同時(shí)在變異過程中也進(jìn)行人工選擇，變異前后的兩個(gè)個(gè)體選擇出適應(yīng)度高的進(jìn)入下一代群體。人工選擇會使種群總體的進(jìn)化向著適應(yīng)度不斷提高的方向進(jìn)行，盡可能保證群體中的優(yōu)勢不會在變異過程中淘汰掉，使群體優(yōu)秀基因能夠遺傳下去，整個(gè)遺傳算法的收斂速度得到提高。

2．2定向突變法基因突變是生物產(chǎn)生新基因的根本途徑，是生物遺傳變異的根本來源。優(yōu)勢個(gè)體發(fā)生基因突變往往是有害的，它們所攜帶的優(yōu)勢基因往往會突變成劣勢基因，導(dǎo)致個(gè)體在遺傳過程失去了競爭優(yōu)勢，從而被淘汰掉。相反，劣勢個(gè)體發(fā)生基因突變帶來的是利多害少，突變之后的個(gè)體適應(yīng)度將會得到提高，使得個(gè)體具有更強(qiáng)的競爭力，整個(gè)群體的進(jìn)化也因此向著適應(yīng)度增加的方向進(jìn)行。因此，針對基因突變的特點(diǎn)，本文提出了一種新型的突變策略，即定向突變法。假設(shè)在初始群體遺傳到第X代的時(shí)候，此時(shí)群體的個(gè)體最大適應(yīng)度是F(x)max，最小適應(yīng)度是F(x)min，于是取整個(gè)群體的平均適應(yīng)度:在一定的突變概率P下，對于在第X代的任意個(gè)體的適應(yīng)度F(xi)來講，滿足下列公式:上述公式是定向突變法的核心，定向突變的實(shí)質(zhì)在于保護(hù)優(yōu)勢個(gè)體的優(yōu)勢基因，同時(shí)促進(jìn)劣勢個(gè)體進(jìn)行主動(dòng)突變。在整個(gè)突變的過程中，群體的基因多樣性不會因?yàn)閮?yōu)勢個(gè)體的保留而減少，因?yàn)榇嬖诹觿輦€(gè)體的突變，保證遺傳算子正常發(fā)揮進(jìn)化和重組效應(yīng)，從而提高群體的多樣性。

2．3自適應(yīng)參數(shù)算法傳統(tǒng)遺傳算法在遺傳過程當(dāng)中，雜交概率Pc和變異概率Pm是始終不變的。通過理論分析可知，當(dāng)處在種群迭代的早期，個(gè)體之間的差異性很大，種群的多樣性非常豐富，因此對于此時(shí)的交叉概率和變異概率來說，其取值可以變得相對小一些。隨著迭代次數(shù)的增多，種群之間的差異性減少，多樣性也隨之減少，將會導(dǎo)致算法的結(jié)果會陷入局部最優(yōu)解，并且影響到算法的收斂速度，此時(shí)本文需要增大變異概率Pm和交叉概率Pc。因此本文引入自適應(yīng)［10，11］參數(shù)K1和K2，通常自適應(yīng)參數(shù)算法寫成:Fmax代表了群體當(dāng)中的最大適應(yīng)度值，F(xiàn)avg代表了群體當(dāng)中的平均適應(yīng)度值。由上式可知，群體最大適應(yīng)度和平均適應(yīng)度差值越大，Pc和Pm的值相應(yīng)會越小，而K1和K2在這個(gè)過程代表著自適應(yīng)調(diào)節(jié)力度的大小。通過自適應(yīng)參數(shù)算法的引入，在遺傳過程根據(jù)實(shí)際情況及時(shí)調(diào)整Pm和Pc，遺傳算法將具有更好的靈活性，收斂速度提高，并且陷入局部最優(yōu)解的可能性降低。

3性能分析與實(shí)驗(yàn)結(jié)果

基于上述分析，采用C語言對求解TSP問題的改進(jìn)遺傳算法進(jìn)行設(shè)計(jì)實(shí)現(xiàn)，為了驗(yàn)證算法的正確性和有效性，本文選取了國際標(biāo)準(zhǔn)的TSPLIB測試集中的兩組數(shù)據(jù)，將本文算法求解得到的最優(yōu)路線與文獻(xiàn)［12］中得到的最優(yōu)解進(jìn)行比對，結(jié)果如下圖1，圖2所示。由以上兩組對比可知，在最優(yōu)路線的求解上，本文算法相比較于文獻(xiàn)［12］中的算法具有一定優(yōu)勢，驗(yàn)證了本文算法的優(yōu)勢性。

4結(jié)語

本文針對TSP問題的求解在傳統(tǒng)遺傳算法的基礎(chǔ)上引入人工選擇，定向突變，和自適應(yīng)參數(shù)算法，設(shè)計(jì)出一套優(yōu)化算法。優(yōu)化算法具有快速的收斂能力，能大幅改善種群的質(zhì)量，極大程度降低所得解的誤差率，并能動(dòng)態(tài)調(diào)節(jié)雜交概率參數(shù)和變異概率參數(shù)，防止算法陷入局部最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，與其他四種算法進(jìn)行比較，本文算法在解的誤差率上具有很大優(yōu)勢。當(dāng)然，本文提出的算法還需要做進(jìn)一步的優(yōu)化工作。在種群規(guī)模迅速擴(kuò)大的時(shí)候，算法的運(yùn)行時(shí)間也會變長，程序會容易陷入局部最優(yōu)解當(dāng)中，這些都需要在以后的研究工作中加以改進(jìn)。

參考文獻(xiàn):

［1］張芳琴．改進(jìn)遺傳算法在TSP組合優(yōu)化問題中的應(yīng)用［J］．高師理科學(xué)刊，2014，34(05):1-4．

［2］杜立智，陳和平，符海東．NP完全問題研究及前景剖析［J］．武漢工程大學(xué)學(xué)報(bào)，2015，37(10):73-78．

［3］徐津．基于遺傳免疫粒群優(yōu)化的網(wǎng)絡(luò)擁塞控制方法［D］．鄭州大學(xué)，2012．

［4］馬行耀．遺傳算法用于超遠(yuǎn)距離泵送混凝土造價(jià)控制技術(shù)分析［J］．混凝土，2018(05):94-97．

［5］李珍萍，胡娩霞，吳凌云．基于遺傳算法的成品油二次配送車輛路徑問題研究［J］．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識，2018，48(09):189-198．

［8］張大科，錢謙．一種新型自適應(yīng)遺傳算法在多峰函數(shù)優(yōu)化中的應(yīng)用［J］．軟件導(dǎo)刊，2018，17(06):85-87+91．

［9］鄧先習(xí)．遺傳算法求解TSP問題的研究與改進(jìn)［D］．沈陽:東北大學(xué)信息科學(xué)與工程學(xué)院，2008．

［12］于瑩瑩，陳燕，李桃迎．改進(jìn)的遺傳算法求解旅行商問題［J］．控制策，2014，(8):1483-1488．

作者：陳洋卓 李青青 羅天揚(yáng) 朱林丹 肖奇 單位：湘潭大學(xué)信息工程學(xué)院