蟻群算法的改進研究與應用碩士學位論文(已修改)

　

【正文】 中圖分類號： O224 論文編號： 學科分類號： 密　　級： 公 開 安徽理工大學碩 士 學 位 論 文蟻群算法的改進研究與應用作者姓名： 弓 英 瑛 專業名稱： 應 用 數 學 研究方向： 優化理論與應用 導師姓名： 許 峰 教 授 導師單位：安徽理工大學理學院答辯委員會主席： 論文答辯日期： 年 月 日安徽理工大學研究生處 年 月 日A Dissertation in Applied MathematicsResearch and Application of Improved Ant Colony AlgorithmCandidate:Gong Yingying Supervisor:Xu FengSchool of ScienceAnhui University of Science and Technology, Shungeng Road, Huainan, 232001, 獨 創 性 聲 明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。據我所知，除了文中特別加以標注和致謝的地方以外，論文中不包含其他人已經發表或撰寫過的研究成果，也不包含為獲得 安徽理工大學 或其他教育機構的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。學位論文作者簽名：___________ 日期： 年 月 日學位論文版權使用授權書本學位論文作者完全了解 安徽理工大學 有保留、使用學位論文的規定，即：研究生在校攻讀學位期間論文工作的知識產權單位屬于 安徽理工大學 。學校有權保留并向國家有關部門或機構送交論文的復印件和磁盤，允許論文被查閱和借閱。本人授權安徽理工大學可以將學位論文的全部或部分內容編入有關數據庫進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。（保密的學位論文在解密后適用本授權書）學位論文作者簽名： 簽字日期： 年 月 日導師簽名： 簽字日期： 年 月 日 摘要摘 要蟻群優化算法是一種群體智能算法，是自然界中螞蟻群落在尋找食物過程的模擬，是一種新興的智能進化算法，是專門解決離散的棘手的問題，在許多應用中，充分展示了其優點，在算法的改進方面也取得了很好的成果。與積極的反饋、自組織、分布式、強健、易與其他算法相結合的優勢，蟻群算法往往陷入局部最優解，收斂速度慢，對初始解的要求比較高。從理論上講，適當轉換后改進的蟻群算法可以使任何組合優化問題得到更快地解決。本文在蟻群算法和模擬退火算法的基礎上對他們進行混合改進，并考慮目標函數梯度的因素，促使算法快速全局收斂；另外，在夾角優化方面也作了相關改進，考慮方向夾角對算法的影響程度，都得到了很好的結果。根據蟻群算法的特點，本文提出了基于目標函數梯度的模擬退火蟻群算法和夾角優化的蟻群算法。數值分析和實驗表明：改進的新算法不僅具有原算法的優點，而且提高了算法的速度。新算法應用于旅行商及路徑規劃問題，新算法的優越性得到了驗證。本文所做工作如下：1. 簡要介紹了蟻群算法的產生背景意義及研究現狀，歸納論文所研究的內容與意義。2. 簡要介紹了蟻群算法的基本原理、算法步驟及流程，最后分析了算法的優缺點等。3. 首先簡要介紹了模擬退火算法的基本原理和算法的過程，然后介紹了一種基于目標函數的梯度模擬退火蟻群算法的基本原理和算法流程，最后給出新算法對問題優化的實驗結果。4. 首先簡要介紹路徑規劃問題，然后介紹夾角優化的蟻群算法的基本原理和算法流程，最后給出新算法對路徑規劃問題優化的結果。圖 13 表 1參 33關鍵詞：蟻群算法；模擬退火算法；梯度；夾角優化分類號：O224IAbstractAbstractAnt colony algorithm is a kind of swarm intelligence optimization algorithm. It is a new intelligent evolutionary algorithm which is a similar to the process of ant munities in search of food in nature. And it is an ideal method for solving difficult discrete problems. It fully demonstrated its advantages in many applications and obtained good results in terms of improved colony algorithm has the advantage of positive feedback, selforganization, distributed, robust, easy to bine with other algorithms. But often trapped in local optimal solution, convergence is slow, the initial solution is relatively high. Theoretically, It will more quickly resolve any binatorial optimization problems, if the ant colony algorithm to make the appropriate changes. This article has been improved on hybrid ant colony algorithm and simulated annealing algorithm bines. It takes into account the objective function gradient of this factor so that global convergence to getting better. In addition, It also made related improvements in the angle optimization. For example, it takes into account the influence of the angle between the direction of the algorithm and the results have been very good.This paper put forward algorithm which is simulated annealing and ant colony hybrid algorithm based on the gradient of objective function and ant colony algorithm in the angle numerical analysis and experiment show that the improved new algorithm not only possesses the advantages of the original algorithm, but also improve the running speed of the algorithm. Applied to the problem of TSP and path planning, The superiority of the new algorithm is verified.The paper contains following tasks:1. This paper briefly introduces the background and significance of research status of ant colony algorithm, and it also describes the content and significance of the study.2. Briefly introduces the basic principles of ant colony algorithm flow algorithm, it also introduces the advantages and disadvantages of the algorithm and so on.3. First introduces the basic principle and algorithm flow of simulated annealing algorithm, Then introduces the basic principles and the algorithm flow of simulated annealing and ant colony hybrid algorithm based on the gradient of objective function, Finally, we gave the experimental results on the new algorithm for solving problems of the TSP .4. First, a brief introduction path planning problem, Then introduces the basic principles and the algorithm flow of ant colony algorithm in the angle optimization, Finally, we gave the experimental results on the new algorithm for solving problems of the path planning. Figure 13 table 1 reference 33　Keywords: ant colony algorithm, simulated annealing algorithm, gradient, angle optimizationChinese books catalog: O224IX目錄目 錄摘 要 IAbstract II插圖或附表清單 VIII引 言 IX1緒 論 1 蟻群算法生成背景和意義 1 蟻群算法的研究現狀 1 論文的研究意義和內容 2 論文的研究意義 2 論文的主要內容 22 蟻群算法的原理及過程 4 蟻群算法的基本原理 4 蟻群算法的算法流程 6 蟻群算法的優缺點 93基于目標函數梯度的模擬退火蟻群算法 11 模擬退火