(19)國家知識產(chǎn)權(quán)局(12)發(fā)明專利有限公司11203GO6N3/006(2023.0群混合算法求解旅行商問題.計算機仿真.2016,(11),第274-279.審查員高莘堯一種基于貪婪自適應蟻群算法的任務調(diào)度方法一種基于貪婪自適應蟻群算法的任務調(diào)度效率因子和可自適應調(diào)整的揮發(fā)系數(shù)來加快蟻利用前后調(diào)度結(jié)果的信息來有針對性的調(diào)節(jié)揮2由下面兩個公式將得到的路徑信息轉(zhuǎn)化為蟻群算法中路在(1)式中的代表初始時刻f時貪婪算法提供的最優(yōu)方案所包含的任一兩個前后相的最優(yōu)方案路徑距離值Lenbest(f)和其余每一個非最優(yōu)方案路徑距離值Lenow(f)相比得到，將所有螞蟻的起始點隨機放置于各個待配送節(jié)點；總路徑距離值該螞蟻的禁忌表中清除；2)計算螞蟻k在時刻t時從當前節(jié)點i到下一節(jié)點j的轉(zhuǎn)移概率,按輪盤賭的方式3為當前時刻螞蟻k所在節(jié)點，節(jié)點j表示待選始化定義；公式(3)通過將所有可行下一節(jié)點的信息素和啟發(fā)式因子值轉(zhuǎn)化為被選擇的概Load,否則當資源剩余量不能滿足任一未配送節(jié)點時則觸發(fā)約束條件返回配送中心；當螞蟻K出發(fā)后再次回到配送中心時，若此時禁忌表尚未清空則重新派出一只螞蟻在共享螞蟻K的禁忌表后，隨機選擇一個禁忌表中的剩余節(jié)點，加上該點到配送中心的距離t+1時刻表示上面出現(xiàn)過的任一時刻t的下一時刻，此時螞蟻K已經(jīng)完成節(jié)點選擇和可行方案的構(gòu)建；(5)式中表示t+1時刻方案m中任意兩個前后相連節(jié)點i和jTm(t+1)(i,j)是t+1時刻方案由于采用了螞蟻間接力的方法來破除在約束條件下對一個物流任務調(diào)度問題的求解，4)記錄當前最優(yōu)方案，對最優(yōu)方案的路徑進行信息素的全局更新，然后清空所有節(jié)點4迭代產(chǎn)生的最優(yōu)方案及路徑值len(t+1);在下一時刻t+2將會使用公式(7)得出本次全局更新的揮發(fā)系數(shù)p(t+1),然后使用公式(8)對本次所有方案中的最優(yōu)路徑的信息素進行全局刻本次迭代的最優(yōu)方案m中前后相連節(jié)點i和j路徑信息素的全局更新值，該值為新的殘留系數(shù)1-p(t+1)和t+1時刻路徑間局部更新后的信息素值的乘積與已被初始化的此處實例為物流資源調(diào)度，設置了一個配送中心和若干個待配送客戶節(jié)點，下面簡稱在每組方案的起始路線選擇時會依次指定除配送中心外的其余節(jié)點作為該路線的第二個5群算法的優(yōu)點是不需要復雜的數(shù)學模型和繁雜的參數(shù)設計就可以處理非常復雜的組合最[0005]本發(fā)明是創(chuàng)造了貪婪自適應蟻群算法(GSA-ACO),通過引入貪婪算法來加速蟻群算法的初始化速度，加入效率因子和可自適應調(diào)整的揮發(fā)系數(shù)來加快蟻群算法的尋優(yōu)速是限制蟻群算法在大規(guī)模資源調(diào)度問題中實際應用的障礙。而貪婪算法可在0(n)的時間復2/6頁2/6頁6[0007]算法中的自適應是指引入對算法參數(shù)中揮發(fā)系數(shù)的自適應調(diào)整和在啟發(fā)式因子公式中引入效率因子。通過引入對信息素揮發(fā)系數(shù)基于前后調(diào)度結(jié)果的提升幅度進行分析的自適應調(diào)整機制來解決運行時出現(xiàn)的優(yōu)化停滯或者困于局部最優(yōu)解的問題。在出現(xiàn)優(yōu)化停滯時增大揮發(fā)系數(shù)擴大搜索范圍來跳出當前最優(yōu)，優(yōu)化速度慢時降低揮發(fā)系數(shù)來快速尋優(yōu)。目前的啟發(fā)式因子公式一般只是考慮距離因素，在這里本算法提出了效率因子加入到啟發(fā)式因子公式中來彌補節(jié)點路徑選擇的粗疏性。效率因子是在選擇下一節(jié)點時結(jié)合該節(jié)點執(zhí)行時間，傳輸時間和執(zhí)行載體的當前狀態(tài)這三類信息得到的因式，本質(zhì)上是為了平衡整體運行效率。兩處調(diào)整機制讓蟻群算法在面對優(yōu)化停滯時有了明確的優(yōu)化方向，解決了迭代方向不明確的問題。[0008]本發(fā)明還提出了蟻群中螞蟻接力調(diào)度的新方法。傳統(tǒng)蟻群算法以一只螞蟻的模擬結(jié)果來得出一個可行的最終解，但對于一個復雜任務調(diào)度問題而言，在約束條件下一只螞蟻一次迭代無法得到整個任務的最終解，這時需要將幾只螞蟻的成果互補作為一組可行方案。目前有人提出將兩只螞蟻分為一組同時進行路徑選擇的方法，但是一組螞蟻需要同步選擇下一節(jié)點，這就帶來了互相干擾尋優(yōu)和節(jié)點重復選擇需要回退的問題。而且很多時候兩只螞蟻也未必可以完成任務。在這里引入了螞蟻間進行接力的新方法，如果一只螞蟻在約束條件下未能清空禁忌表就已經(jīng)因為約束條件終止調(diào)度了，則再派出一只螞蟻通過共享上一螞蟻的禁忌表來繼續(xù)完成任務，若禁忌表仍未被清空再派出下一只螞蟻，直至禁忌表被清空。再將得到的多個互補的調(diào)度結(jié)果合并為一組可行方案。[0009]上述三項改進解決了蟻群算法對約束條件下大規(guī)模任務調(diào)度不適用的難題。例如在大型集群調(diào)度的資源調(diào)度利用率問題中，常規(guī)蟻群算法就很難落地應用，原因在于迭代運行速度慢，節(jié)點選擇不確定性強且單螞蟻路徑很難滿足各類約束條件。另外該算法的通用性很強，各項改進都可以對目前各類蟻群算法的變種進行有益的補充和優(yōu)化。[0014]步驟4、開始執(zhí)行蟻群算法，結(jié)合自適應調(diào)整機制最終給出最優(yōu)方案。[0015]整個算法的流程圖在圖4中給出。附圖說明[0016]圖1物流問題示意圖[0017]圖2貪婪算法得出的可行解示意圖[0018]圖3蟻群算法得出的最優(yōu)解示意圖具體實施方式[0020]以下結(jié)合實例與附圖對本發(fā)明進行詳細說明。[0021]本發(fā)明的實施方式僅以解決物流資源調(diào)度難題為例，但算法本身廣泛適用于各類帶約束的任務調(diào)度問題。如圖1所示該模型設置了一個配送中心和若干個待配送客戶節(jié)點7實例中設置為100t,所以不可能只由一輛車就能完成所有的配送任務，故一個可行解中必這里的物流調(diào)度問題可以轉(zhuǎn)化為在考慮汽車載重的情況下在一個圖中遍歷所有節(jié)點尋找這些方案為蟻群算法的初始化和迭代時的節(jié)點得出一條可行路徑。這里的解決方案是在每組方案的起始路線[0030]在(1)式中的代表初始時刻f時貪婪算法提供的最優(yōu)方案所包含的任一兩個前法設置的所有節(jié)點路徑間的初始信息素，此處設置的值為0.01,因為在實例中節(jié)點間的路8[0031]在(2)式中代表初始時刻f時其余非最優(yōu)方案中包含的任一兩個前后相聯(lián)節(jié)得到，故每條非最優(yōu)方案的ξ值隨著本方案的路徑距離不同而各不相同。值的設置是[0032]初始化后得到的各節(jié)點間路徑的初始信息素值將會在蟻群算法節(jié)點選取時由概距離值會加上該初始節(jié)點到配送中心的距離。接下來為每只螞蟻設置各自的初始禁忌表，[0037]在這里螞蟻k指代該步驟中出現(xiàn)的所有需要選擇節(jié)點的螞蟻，t時刻為任一時刻，節(jié)點i為當前時刻螞蟻k所在節(jié)點，節(jié)點j表示待選擇的下一節(jié)點。公式中J(i)是t時刻在i[0038]公式(4中!是指t時刻i節(jié)點待選擇的下一節(jié)點j的啟發(fā)式因子值，表示i、j9小于Load,,否則當資源剩余量不能滿足任一未配送節(jié)點時則觸發(fā)約束條件返回配送中心。的已知信息和優(yōu)化需求還可以設置更多參數(shù)來進一步[0040]當螞蟻K出發(fā)后回到配送中心時，若此時禁忌共享螞蟻K的禁忌表后，隨機選擇一個禁忌表中的剩余節(jié)點，加上該點到配送中心的距離殘留系數(shù)，△Tm(t+1)(i,j)是t+1時刻該方案經(jīng)過的任一兩個相連節(jié)點i和j之間路徑的信息[0044]由于采用了螞蟻間接力的方法來破除在約束條件下(此處為汽車載重量)對一個[0048]t+1時刻我們得到每一個方案后，我們對其路徑間的信息素進行了局部更新，并最終得出本次迭代產(chǎn)生的最優(yōu)方案的路徑值len(t+1)。在下一時刻t+2將會使用公式(7)得出本次全局更新的揮發(fā)系數(shù)，然后使用公式(8)對本次最優(yōu)方案的路徑的信息素進行全局更新。[0049]如公式(7)所示，Len(t)為t時刻的全局最優(yōu)路徑距離值，len(t+1)為t+1時刻得到的本次迭代最優(yōu)路徑距離值。Lenbest(+2)是Len(t+1)、len(后t+2時刻后蟻群算法更新的新全局最優(yōu)路徑距離值。這里的信息素揮發(fā)系數(shù)p(t+1)的值是通過對比前后最優(yōu)路徑的提升幅度來進行自適應調(diào)整。本次最優(yōu)路徑提升得越多，揮發(fā)系數(shù)p(t+1)就同比減小，因為同比降低揮發(fā)系數(shù)p(t+1)可以更好聚焦該路徑進行尋優(yōu)；提升越小甚至沒有提升時，揮發(fā)系數(shù)p(t+1)就相對增大，因為增加揮發(fā)系數(shù)可以擴大蟻群的搜索空間。這樣就解決了實際調(diào)度中運用蟻群算法遇到的迭代次數(shù)過多或者困于局部最優(yōu)解的問題。[0050]公式8中的τ;;(t+2表示t+2時刻本次迭代的最優(yōu)方案中任一路徑的前后相連節(jié)點i和j的路徑信息素的全局更新值。值為殘留系數(shù)1-p(t+1)和t+1時刻路徑間局部更新后的信[0052]反復重復上述迭代蟻群算法中的步驟1至4,直至迭代次數(shù)達到設置好的上限NCmx即50次后輸出最后求得的最優(yōu)路徑。得到的調(diào)度方案如示意圖3所示，該調(diào)度方案可以用于指導實際物流調(diào)度中調(diào)度方案的設計。從圖2和圖3兩個示意圖的對比中我們可以看出是否精心設計調(diào)度方案會對最終的執(zhí)行結(jié)果帶來很大的差距。如果能采用改進的蟻群算法得出最優(yōu)化方案來最終執(zhí)行，不僅可以明顯提高物流公司調(diào)度過程中的資源利用率，避免資源浪費，還可以提升客戶的體驗，最終可以為物流公司帶來良好的經(jīng)濟和社會效益。[0053]以上實施例僅為本發(fā)明的示例性實施例，不用于限制本發(fā)明，本發(fā)明的保護范圍由權(quán)利要求書限定。本領(lǐng)域技術(shù)人員可以在本發(fā)明的實質(zhì)和保護范圍內(nèi)，對本發(fā)明做出各種修改或等同替換，這種修改或等同替換也應視為落在本發(fā)明的保護范圍內(nèi)。OO0