【正文】 成機(jī)制和最晚結(jié)束時(shí)間優(yōu)先規(guī)則，結(jié)果證明該算法解決 RCPSP 有效可行。 本文技術(shù)路線如圖 所示： 文 獻(xiàn) 綜 述模 擬 退 火 算 法 國(guó)內(nèi) 外 相 關(guān) 研 究蟻 群 算 法 國(guó) 內(nèi) 外相 關(guān) 研 究蟻 群 算 法及 其 改 進(jìn) 算 法蟻 群 算 法案 例 分 析模 擬 退 火 算 法模 擬 退 火 蟻 群 算 法( 融 合 最 大 最 小 螞 蟻系 統(tǒng) 改 進(jìn) )改 進(jìn) 算 法 介 紹算 法 性 能 測(cè) 試結(jié) 論 及 展 望 圖 技術(shù)路線圖 二、 文獻(xiàn)綜述 （一） 蟻群算法 1. 蟻群算法相關(guān)應(yīng)用 受螞蟻行為的啟發(fā)， Colomi 和 Dori 即等人于 1992 年提出 Ant System（ AS）的概念，研究成果經(jīng)應(yīng)用于傳統(tǒng)的旅行商問題（ TSP）上，取得了很好的效果。 第五章：模擬退火蟻群算法，由模擬退火算法入手對(duì)對(duì)蟻群算法進(jìn)行改進(jìn)，即將模擬退火算法與蟻群算法相結(jié)合，并對(duì)改進(jìn)的蟻群算法進(jìn)行測(cè)試，得出最有效的改進(jìn)模型。 第三章：蟻群算法，從蟻群算法產(chǎn)生及發(fā)展切入，研究蟻群算法基本模型，并應(yīng)用旅行商問題（ TSP）對(duì)其算法模型及實(shí)現(xiàn)流程描述，進(jìn)而對(duì)其目 前認(rèn)可程度較高的幾種改進(jìn)方式進(jìn)行介紹 ，其中最大最小螞蟻系統(tǒng)將在后續(xù)改進(jìn)中進(jìn)一步進(jìn)行融合。 （三） 技術(shù)路線 本文共六章，具體安排如下： 第一章：緒論，提出本文研究背景及意義，對(duì)全文框架進(jìn)行梳理。 蟻群算法基于正反饋機(jī)制反復(fù)迭代獲取最優(yōu)解，為保證其解的精確性在尋優(yōu)過(guò)程中由于信息素?fù)]發(fā)機(jī)制的存在，且初期信息素匱乏，收斂速度較慢；而模擬退火算法具有大范圍全 局搜索能力，由于對(duì)系統(tǒng)中反饋信息利用不夠，當(dāng)求解到一定范圍時(shí)往往做大量無(wú)為的冗余迭代。當(dāng)可行解集合中的點(diǎn)個(gè)數(shù)較少時(shí)，通過(guò)最直觀的窮舉法很容易得到最優(yōu)解；但倘若可行解集合中的有限點(diǎn)數(shù)目逐漸增多，此時(shí)如果仍采用完全枚舉、判別、比較、選擇的步驟，則無(wú)疑是十分困難和不可取的，所需要的時(shí)間和空間是龐大得驚人的 。 （二） 研究意義 在組合最優(yōu)化問題中，以 TSP 問題為例，最早也最自然的想法就是采用窮舉法。 針對(duì)蟻群算法這一研究熱點(diǎn)，目前對(duì)其基本算法的改進(jìn)大多數(shù)集中于信息素更新機(jī)制及參數(shù)選擇。為了解決這些難題， 20 世紀(jì) 90 年代起，一些更新的思想和算法逐漸形成。旅行商問題是目前研究最為廣泛的組合優(yōu)化問題之一。是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運(yùn)籌學(xué)中的一個(gè)經(jīng)典且重要的分支，所研究的問題涉及經(jīng)濟(jì)管理、信息科學(xué)、工程技術(shù)、交通運(yùn)輸、通信網(wǎng)絡(luò)等諸多領(lǐng)域。且經(jīng)測(cè)試該改進(jìn)算法的確優(yōu)于原始蟻群算法。 蟻群算法應(yīng)用 及改進(jìn)研究 學(xué) 院：經(jīng)濟(jì)與管理學(xué)院 專 業(yè)：建設(shè)管理 工業(yè)工程 小組成員： 夏侯雪 1432622（組長(zhǎng)） 戴家瑋 1432621 苗雁家 1432626 蔡惠欣 1432690 王雪瑩 1432693 指導(dǎo)老師：段永瑞 教授 2021 年 12 月 蟻群算法應(yīng)用及改進(jìn)研究 夏侯雪（組長(zhǎng)）戴家瑋 苗雁家 蔡惠欣 王雪瑩 指導(dǎo)老師：段永瑞 教授 【摘要】 組合最優(yōu)化問題（ COP）即給定的約束條件下，求出使目標(biāo)函數(shù)極?。ɑ驑O大）的變量組合問題，是運(yùn)籌學(xué)中的一個(gè)經(jīng)典且重要的分支，其經(jīng)典難題為旅行商問題（ TSP）。本研究以旅行商問題為出發(fā)點(diǎn)，對(duì)蟻群算法及其改進(jìn)方式進(jìn)行研究，將模擬退火算法與蟻群算法相結(jié)合， 并結(jié)合最大最小螞蟻系統(tǒng)思想，最終 提出模擬退火蟻群算法，對(duì)基本蟻群算法進(jìn)行改進(jìn)，提高解的質(zhì)量并加速蟻群算法收斂速度。 【關(guān)鍵詞】 蟻群算法 旅行商問題 公共自行車調(diào)度 模擬退火算法 最大最 小螞蟻系統(tǒng) 目錄 一、 緒論 ............................................................................................................ 6 （一） 研究背景 .............................................................................................. 6 （二） 研究意義 .............................................................................................. 6 （三） 技術(shù)路線 .............................................................................................. 7 二、 文獻(xiàn)綜述 ..................................................................................................... 8 （一） 蟻群算法 .............................................................................................. 8 1. 蟻群算法相關(guān)應(yīng)用 ................................................................................ 8 2. 國(guó)外蟻群算法改進(jìn)研究 ......................................................................... 8 3. 國(guó)內(nèi)蟻群算法改進(jìn)研究 ......................................................................... 9 （二） 模擬退火算法 ..................................................................................... 10 1. 國(guó)外模擬退火算法研究 ....................................................................... 10 2. 國(guó)內(nèi)模擬退火算法研究 ....................................................................... 10 （三） 小結(jié) ................................................................................................... 11 三、 蟻群算法 ................................................................................................... 12 （一） 蟻群算法產(chǎn)生與發(fā)展 .......................................................................... 12 1. 雙橋?qū)嶒?yàn) ............................................................................................ 12 2. 人工螞蟻 ............................................................................................ 14 3. 人工螞蟻系統(tǒng)特點(diǎn) .............................................................................. 17 （二） 蟻群算法基本模型 .............................................................................. 18 1. 螞蟻系統(tǒng)數(shù)學(xué)模型 .............................................................................. 19 2. 蟻群系統(tǒng)算法的實(shí)現(xiàn) .......................................................................... 20 （三） 后續(xù)系統(tǒng) ............................................................................................ 21 1. 蟻周系統(tǒng) ............................................................................................ 21 2. 蟻量系統(tǒng) ............................................................................................ 22 3. 蟻密系統(tǒng) ............................................................................................ 22 （四） 蟻群算法改進(jìn)算法 .............................................................................. 22 1. 精英螞蟻系統(tǒng) ..................................................................................... 23 2. 優(yōu)化排列螞蟻系統(tǒng) .............................................................................. 23 3. 最大最小螞蟻系統(tǒng) .............................................................................. 23 4. 最優(yōu)最差螞蟻系統(tǒng) .............................................................................. 24 5. 蟻群系統(tǒng) ............................................................................................ 25 （五） 雙（多）蟻群算法 .............................................................................. 26 1. 雙（多）蟻群算法介紹 ....................................................................... 26 2. 多種群蟻群算法 ——以旅行商問題（ TSP）為例 ................................. 27 四、 案例分析 —— 公共自行車調(diào)度問題 ............................................................ 29 （一） 問題提出 ............................................................................................ 29 （二） 方法選擇 ............................................................................................ 29 （三） 數(shù)學(xué)模型描述 ..................................................................................... 29 （四） 算法設(shè)計(jì) ............................................................................................ 31 （五） 算例分析 ............................................................................................ 32 五、 模擬退火蟻群算法 ..................................................................................... 35 （一） 模擬退火算法 ........................................................................