基于tsp的蟻群算法參數(shù)選擇問題分析

ID:26809884

大?。?1.50 KB

頁數(shù):5頁

時間:2018-11-29

基于tsp的蟻群算法參數(shù)選擇問題分析_第1頁
基于tsp的蟻群算法參數(shù)選擇問題分析_第2頁
基于tsp的蟻群算法參數(shù)選擇問題分析_第3頁
基于tsp的蟻群算法參數(shù)選擇問題分析_第4頁
基于tsp的蟻群算法參數(shù)選擇問題分析_第5頁
資源描述:

《基于tsp的蟻群算法參數(shù)選擇問題分析》由會員上傳分享,免費在線閱讀,更多相關內(nèi)容在學術論文-天天文庫。

1、基于TSP的蟻群算法參數(shù)選擇問題分析摘要:根據(jù)目前針對社會性動物群體活動的實驗調(diào)查,發(fā)現(xiàn)其自組織行為廣泛存在,例如群體活動較為頻繁的螞蟻,在群體覓食過程中能夠找到蟻穴到食物的最短路徑,即蟻群算法。文章圍繞蟻群算法在TSP中的應用,就算法的參數(shù)選擇進行了深入的研究。最后通過對全文的研究工作進行了總結,并展望了其應用價值及后期還需繼續(xù)研究的問題。中國8/vie  關鍵詞:蟻群算法TSP最短路徑參數(shù)選擇  中圖分類號:TP183文獻標識碼:A:1007-9416(2016)12-0131-02  蟻群算法是一種用來在圖中尋找優(yōu)化路徑的機

2、率型算法。它由MarcoDorigo提出,它主要的依據(jù)就是螞蟻在覓食過程中能夠找到蟻穴到食物的最短路徑。螞蟻的視覺系統(tǒng)非常薄弱,幾乎可以說是瞎子,但是它們卻能發(fā)現(xiàn)食物與蟻穴之間最短的距離。生態(tài)學家的研究表明,螞蟻是借助信息素來實現(xiàn)這一點的。蟻群算法也越來越多被應用到實際的問題中,并且取得了較好的效果,例如調(diào)度問題、著色問題、求解旅行商問題(TSP),并在大規(guī)模集成電路設計,通信路由控制等諸多領域表現(xiàn)出較好的性能。本文在介紹蟻群算法的基本原理的基礎上,主要分析了蟻群算法參數(shù)的選擇策略問題?! ?蟻群算法的基本原理  1.1蟻群算法的

3、原理  蟻群算法是從自然界啟發(fā)中得到的一種新型的模擬進化算法,應用該算法求解TSP問題取得了較好的結果??茖W家發(fā)現(xiàn)雖然單個螞蟻無法掌握附近的地理信息,但整個蟻群卻可以找到一條從巢穴到食物源之間的最優(yōu)路線。經(jīng)過大量研究發(fā)現(xiàn):螞蟻在運動過程中,能夠留下一種稱之為信息素的物質(zhì),而且螞蟻在運動過程中能夠感知這種物質(zhì),并以此指導自己的運動方向,因此,由大量螞蟻組成的蟻群的集體行?楸惚硐殖鲆恢中畔⒄?反饋現(xiàn)象:某一路徑上單位時間走過的螞蟻越多,表明該路線的可用性越好,則后來者選擇該路徑的概率就越大。蟻群算法具有實現(xiàn)簡單、正反饋、分布式的優(yōu)點。

4、  人工蟻群和自然界蟻群的相似之處在于,兩者優(yōu)先選擇的都是含“信息素”濃度較大的路徑。這在兩種情況下,較短的路徑上都能聚集比較多的信息素,受到上述情況的啟發(fā),科研人員在此基礎上提出了蟻群算法,它不僅具有蟻群覓食行為中的信息傳遞功能,還具有自然界蟻群所沒有的記憶能力,即能夠保存已經(jīng)去過的地方和已經(jīng)走過的路徑,從而能夠更加智能的選擇下一地點和路徑,并且按照一定的規(guī)律總結出特有的算法進行最短路徑的選擇?! ?.2基于TSP問題的蟻群算法數(shù)學模型  TSP問題又稱為旅行商問題,是數(shù)學領域中著名問題之一。假設有一個旅行商人要拜訪M個城市,他

5、必須選擇所要走的路徑,路徑的限制是每個城市只能拜訪一次,而且最終要回到原來出發(fā)的城市。路徑的選擇目標是要求旅行商人怎樣才能得到最短的路徑,取得最佳的利益?! 「鶕?jù)信息素更新的策略不同,DorigoM曾給出了不同的蟻群算法模型,分別稱為ant-cycle模型,ant-quantity模型和ant-density模型。它們的差別在于循環(huán)中路徑的信息素的增量的求法不同?! ≡赼nt-quantity模型中:  其中,是信息素強度,它影響算法的收斂速度是指兩座城市之間的歐氏距離,是指第只螞蟻所走的路徑長度。ant-quantity和ant

6、-density是利用局部信息完成求解運算,ant-cycle是利用整體信息完成求解運算。通過實驗得到ant-cycle的模型比其他兩種模型效果好?! ?參數(shù)優(yōu)化策略  通過對蟻群算法基本原理及其數(shù)學模型的學習理解,可以使用MATLAB進行蟻群算法求解TSP最短路徑問題的仿真試驗工作,其主要任務是:根據(jù)城市的坐標,使用蟻群算法求解TSP最優(yōu)化問題,并繪制最佳結果的路徑圖,生成平均距離和最短距離統(tǒng)計圖?! ∷惴ㄖ械闹饕獏?shù)有:城市的個數(shù),城市的坐標(城市個數(shù)*2的矩陣),最大循環(huán)次數(shù)(即迭代的次數(shù)),螞蟻個數(shù),表征信息素重要程度的參

7、數(shù),表征啟發(fā)因子(期望)重要程度的參數(shù),信息素揮發(fā)系數(shù),信息素強度的系數(shù)(一般是一個常量),最佳路線的長度?! 崿F(xiàn)步驟為:第一步:變量初始化;第二步:循環(huán)開始,判斷變量是否達到最大迭代次數(shù),如果沒有達到,繼續(xù)下一步運行,否則,循環(huán)結束;第三步:將所有螞蟻隨機放到所有城市上;第四步:所有螞蟻按概率函數(shù)選擇下一座城市,完成各自的周游;第五步:記錄本次迭代最佳路線;第六步:更新信息素;禁忌表清零,回到第二步,達到停止條件時跳到第七步;第七步:輸出結果?! 》抡嬷胁捎米疃搪窂阶鳛閰⒖柬?,進行多目標測試得出結果,并由結果分析出蟻群算法中的

8、參數(shù)如何選擇優(yōu)化。  2.1缺省值的選擇  在實驗過程中,本文在進行參數(shù)選擇時,取城市個數(shù)為20,迭代次數(shù)為100,螞蟻個數(shù)為15,信息素重要程度為1,啟發(fā)因子重要程度為1,信息素揮發(fā)系數(shù)為0.15,信息素強度的系數(shù)為100,并設定20個城市坐標為

當前文檔最多預覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學公式或PPT動畫的文件,查看預覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭