[發(fā)明專利]一種基于反向?qū)W習(xí)的蟻群算法優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 202010549642.2
• 申請日: 2020-06-16
• 公開（公告）號: CN111695668A
• 公開（公告）日: 2020-09-22
• 發(fā)明（設(shè)計(jì)）人: 許釗雄;張兆軍;李軒宇
• 申請（專利權(quán)）人: 江蘇師范大學(xué)
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明涉及一種基于反向?qū)W習(xí)的蟻群算法優(yōu)化方法，用于求解旅行商問題。該算法的改進(jìn)主要包括以下幾點(diǎn)：1，在初始路徑求出后，對初始路徑中每個(gè)城市的序號進(jìn)行反向，構(gòu)造反向路徑；2，將初始路徑和反向路徑分別按照長度從小到大排序，取其中的部分路徑構(gòu)成一組新的路徑；3，設(shè)置一個(gè)迭代閾值，如果當(dāng)前的迭代次數(shù)未達(dá)到迭代閾值時(shí)，對新的一組路徑進(jìn)行信息素更新；否則，則對初始路徑進(jìn)行信息素更新。本發(fā)明對基本蟻群算法的信息素更新方面做了改進(jìn)，在迭代前期，引入反向?qū)W習(xí)構(gòu)造反向路徑，并參與信息素更新，有利于擴(kuò)大螞蟻的搜索范圍，避免螞蟻陷入局部極值，平衡了解空間的探索和開發(fā)。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)技術(shù)領(lǐng)域，涉及一種基于反向?qū)W習(xí)的蟻群算法優(yōu)化方法。

背景技術(shù)

隨著科學(xué)技術(shù)的發(fā)展，優(yōu)化方法在人工智能、電子科學(xué)、交通運(yùn)輸、公共管理等領(lǐng)域得到了廣泛的應(yīng)用。國內(nèi)外許多專家學(xué)者從自然中得到啟發(fā)，通過模擬自然現(xiàn)象和生物行為，提出了一系列優(yōu)化算法，其中包括：人工勢場法、模擬退火算法、遺傳算法、粒子群算法以及蟻群算法等。其中，人工勢場法缺乏全局信息，容易出現(xiàn)局部極值；模擬退火算法的收斂速度較慢，性能對參數(shù)較為敏感；遺傳算法計(jì)算量大，且搜索速度較慢；粒子群算法容易出現(xiàn)早熟收斂，局部尋優(yōu)能力較差；蟻群算法存在搜索時(shí)間過長、易陷入局部最優(yōu)解等缺陷。

蟻群算法是通過模擬自然界中真實(shí)螞蟻的覓食行為而提出的一種啟發(fā)式搜索算法。根據(jù)研究發(fā)現(xiàn)，螞蟻在尋找食物的過程中，會(huì)在其經(jīng)過的路徑上釋放信息素。信息素能被其它螞蟻所感知，并且會(huì)影響其它螞蟻接下來的路徑選擇。路徑越短，釋放的信息素就越多。信息素濃度越高，螞蟻選擇該路徑的概率就越大，而其他路徑上的信息素濃度隨著時(shí)間的推移而逐漸消減。最終，螞蟻會(huì)找到一條從蟻巢到食物源的最短路徑。

蟻群算法包括兩個(gè)主要步驟：路徑構(gòu)建和信息素更新。在構(gòu)建解過程中，通過隨機(jī)比例規(guī)則，逐步建立優(yōu)化問題的解；在信息素更新過程中，依據(jù)螞蟻所構(gòu)造的解，修改空間內(nèi)的信息素濃度。憑借其具有較強(qiáng)的魯棒性、分布式并行計(jì)算、易與其他算法相結(jié)合等優(yōu)點(diǎn)，蟻群算法已經(jīng)成功應(yīng)用于旅行商問題、車輛路徑規(guī)劃問題、背包問題、連續(xù)函數(shù)尋優(yōu)等多個(gè)領(lǐng)域。旅行商問題是一個(gè)經(jīng)典的組合優(yōu)化問題，簡單描述為：求旅行商遍歷完所有城市且每個(gè)城市只經(jīng)過一次的最短路徑。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種基于反向?qū)W習(xí)的蟻群算法優(yōu)化方法，用于求解旅行商問題。該算法通過引入反向?qū)W習(xí)算法構(gòu)造反向路徑，在信息素更新階段，選擇反向路徑中部分效果較好的路徑參與信息素更新，增加算法對解空間的探索，有利于算法跳出局部極值。

本發(fā)明采用的技術(shù)方案是：一種基于反向?qū)W習(xí)的蟻群算法優(yōu)化方法，包括如下步驟：

S1：初始化蟻群算法參數(shù)，輸入旅行商問題節(jié)點(diǎn)坐標(biāo)；

S2：將每只螞蟻隨機(jī)放入任意一個(gè)節(jié)點(diǎn)中作為起始節(jié)點(diǎn)；

S3：每只螞蟻從起始節(jié)點(diǎn)開始，按照狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)移動(dòng)節(jié)點(diǎn)，直到遍歷完所有節(jié)點(diǎn)，得到初始路徑；

S4：設(shè)定一個(gè)迭代閾值R，判斷當(dāng)前迭代次數(shù)是否大于閾值R，若是則跳轉(zhuǎn)至S6，否則對初始路徑中每個(gè)城市的序號進(jìn)行反向，構(gòu)造反向路徑；

S5：將初始路徑和反向路徑按照其路徑長度進(jìn)行排序，分別取其中部分路徑構(gòu)成一組新的路徑；

S6：按照信息素更新公式，對路徑進(jìn)行信息素更新；

S7：判斷是否達(dá)到最大迭代次數(shù)，若是則停止搜索，輸出全局最優(yōu)路徑，否則跳轉(zhuǎn)至S2進(jìn)行下一次迭代；

進(jìn)一步地，所述步驟S3的狀態(tài)轉(zhuǎn)移規(guī)則具體為：

螞蟻在進(jìn)行路徑構(gòu)建時(shí)，主要受信息素濃度和啟發(fā)信息兩個(gè)因素的影響。在t時(shí)刻，螞蟻k從當(dāng)前節(jié)點(diǎn)i移動(dòng)到下一個(gè)節(jié)點(diǎn)j的狀態(tài)轉(zhuǎn)移概率為