《基于煙花算法的倉儲物流機器人任務(wù)調(diào)度優(yōu)化設(shè)計實例》24000字

PAGE2基于煙花算法的倉儲物流機器人任務(wù)調(diào)度優(yōu)化設(shè)計實例目錄TOC\o"1-2"\h\u14815第1章緒論 1155711.1研究背景和意義 154271.2國內(nèi)外研究現(xiàn)狀 3252961.3論文研究內(nèi)容及技術(shù)路線 618035第2章倉儲物流系統(tǒng)研究 1010322.1路徑模型概述 10266182.2任務(wù)調(diào)度原理 1190902.4任務(wù)調(diào)度算法 14170232.5本章小結(jié) 196583第3章倉儲物流機器人任務(wù)調(diào)度實例 20155383.1引言 20190223.2倉庫實例建模分析 20113973.3智能算法對倉儲物流調(diào)度實例模型的求解分析 2322700第4章煙花算法及其改進策略 25163894.1煙花算法工作原理分析 2523039算法4.1煙花算法偽代碼 3086234.2煙花算法性能分析 31145164.3改進煙花算法對實例模型的求解 32237084.4遺傳算法對實例模型求解 33236624.5關(guān)于倉儲物流機器人調(diào)度的煙花算法改進策略 3426375第5章實驗方案與結(jié)果分析 397695.1實驗方案設(shè)計 39117605.2實驗參數(shù)設(shè)定 3948425.3實驗結(jié)果對比分析 419679第六章總結(jié)與展望 4554696.1總結(jié) 45272466.2展望 46第1章緒論1.1研究背景和意義隨著我國電商行業(yè)近年來的蓬勃發(fā)展，國內(nèi)物流行業(yè)的總體規(guī)模和物流總需求逐漸在這種發(fā)展的促進下日益增多。僅2019年我國社會物流總額就高達298.0萬億元，2019年全年的社會物流總額與2018年全年的社會物流總額相比增長近6%[1]。日益增長的物流需求意味著在貨物運輸過程中需要更快且更準確的將貨物送達目的地。傳統(tǒng)的倉庫管理系統(tǒng)是以人工規(guī)劃調(diào)度，人工分揀，機器輔助搬運為主，貨物通過入庫登記、入庫預(yù)檢、收貨檢驗、上架最終完成入庫操作，而后實行貨物保管，在接到訂單請求后又通過預(yù)分配、揀貨、集貨最終完成發(fā)貨。這其中涉及大量勞動力參與，由于是人力分揀搬運，通常還存在人為失誤的情況，這也最終導致傳統(tǒng)的倉庫管理系統(tǒng)容易發(fā)生安全事故，容易出現(xiàn)誤拿、錯放等失誤，且綜合效率不高。這些劣勢會很直接的影響客戶消費體驗，也極大的增加了企業(yè)的物流成本，成本增加而收益不變，企業(yè)的利潤也就相對減少。由此可見，傳統(tǒng)的倉儲模式在當前的物流行業(yè)發(fā)展環(huán)境下已經(jīng)很難適應(yīng)當今社會，于是倉儲物流智能化[2]應(yīng)運而生。圖1.12011-2019年我國社會物流總額倉儲物流智能化是指倉庫管理者運用計算機軟件和機器人代替?zhèn)鹘y(tǒng)的人力，使貨物管理信息化，貨物搬運無人化，提高貨物流通效率，增加貨物搬運過程中的準確率，降低企業(yè)物流成本，提高盈利。倉儲物流機器人是這類機器人的總稱，根據(jù)不同場景，倉儲物流機器人又可以分為搬運機器人，即：AGV(AutomatedGuidedVehicle,自動引導小車)和AMR(AutonomousMobileRobot,自主移動機器人)；分揀機器人、貨架機器人，即：機械臂、碼垛機器人和穿梭車RGV（RailGuidedVehicle）。本文研究中涉及的倉儲物流機器人是AGV和AMR這類用于移動搬運貨物的搬運機器人。與傳統(tǒng)倉庫管理系統(tǒng)中的搬運輔助工具相比，AGV和AMR這類用于移動搬運的機器人在倉管系統(tǒng)中有著無可比擬的優(yōu)勢：一是自動化。它們在搬運物料時可以實現(xiàn)全自動化運行，任務(wù)分配，響應(yīng)，調(diào)度都可以由控制系統(tǒng)統(tǒng)一管理，使得各個機器人之間可以共享信息。針對機器人集群中的信息共享及時調(diào)整任務(wù)分配并更改后續(xù)的任務(wù)調(diào)度策略選擇，以達到動態(tài)優(yōu)化的目的，節(jié)省系統(tǒng)資源開銷；二是使用成本低。在人力成本日漸增長的今天，機器人取代人力可大大減少倉庫運營管理的開支；三是效率高。機器人受控制系統(tǒng)統(tǒng)一調(diào)配，可以24小時不間斷進行作業(yè)；四是可靠性較高?？刂葡到y(tǒng)對于所有的機器人實時監(jiān)控，貨物運輸狀況一目了然，能很大程度上保證倉庫管理系統(tǒng)的穩(wěn)定性。五是適用性強。在一些潮濕，低溫，空間有限或其他極端情況下，人類長期工作很容易損害健康，而機器人卻可以通過改裝適應(yīng)各種環(huán)境。從二十世紀五十年代至今，各類功能不盡相同的倉儲物流機器人經(jīng)過長足的發(fā)展在智能倉儲中得到很好的應(yīng)用，在以亞馬遜，京東為代表的國內(nèi)外大型物流企業(yè)中都可以看見它們的身影，也有越來越多的生產(chǎn)車間采用倉儲物流機器人進行物料運輸。隨著這些普及，一些問題慢慢出現(xiàn)在人們眼前:（1）協(xié)同作業(yè)問題；當多個機器人同時工作時，系統(tǒng)如何實時調(diào)配任務(wù)，使得機器人之間不產(chǎn)生沖突，并且效率最大化。（2）路徑規(guī)劃問題；路徑規(guī)劃問題更多的是針對AMR,機械臂這類自由度較高的機器人，它們在運行過程中可能存在遇到障礙物的情況，而路徑規(guī)劃則是選擇一條避開障礙且路徑最短的路線，使機器人以最短的時間送達貨物。（3）調(diào)度問題；當系統(tǒng)接到多個任務(wù)時，怎樣把接到的任務(wù)按照一定的規(guī)則分配給多個機器人，使這些機器人在執(zhí)行任務(wù)過程中達到一定的優(yōu)化目標，如:消耗最少的時間，完成最多的任務(wù)等，并且在運行過程中不發(fā)生任務(wù)遺漏，鎖死等情況。在這些問題中，倉儲物流機器人的調(diào)度策略選擇對于機器人在運行中是否可以高效運行起著至關(guān)重要的作用。倉儲物流機器人調(diào)度問題，特別是AGV調(diào)度問題正逐漸成為生產(chǎn)調(diào)度領(lǐng)域的重要熱點研究之一[3]。本課題著重研究的就是倉儲物流機器人的調(diào)度問題，通過對倉儲物流機器人的任務(wù)調(diào)度過程進行分析，建立適當?shù)哪Ｐ停剿髑蠼馑惴?，最終在實例模型中解決倉儲物流機器人的調(diào)度問題。1.2國內(nèi)外研究現(xiàn)狀1.2.1國外研究現(xiàn)狀國外的倉儲物流機器人調(diào)度研究從20世紀80年代開始興起[4-7]，最初對于任務(wù)調(diào)度問題的求解，學者們認為可以將調(diào)度問題抽象成數(shù)學模型，通過數(shù)學模型對其進行描述，而后采用分支定界整數(shù)規(guī)劃及混合整數(shù)規(guī)劃來求解。Toshiyuki等[8]將無沖突路徑規(guī)劃和倉儲物流機器人分派問題描述為整數(shù)規(guī)劃問題通過精確求解的方式進行求解。Meersmans等[9]采用分支界定法與定向搜索算法求解自動化集裝箱碼頭不同類型物料處理設(shè)備的集成調(diào)度問題。Bilge等[10]將柔性制造系統(tǒng)(FlexibleManufacturingSystem,FMS)中制造系統(tǒng)中的機器調(diào)度問題和物料搬運中涉及到的AGV調(diào)度問題結(jié)合起來考慮，而后將這個混合問題表述成一個混合整數(shù)規(guī)劃問題，對于這個非線性的混合整數(shù)規(guī)劃問題，通過數(shù)學精確求解的方式求解。以上兩位學者都使用了數(shù)學精確求解的方式求解整數(shù)規(guī)劃問題，這種求解方法雖然一定可以獲得全局最優(yōu)解，但只限于解決小規(guī)模調(diào)度問題，隨著問題規(guī)模的增大，數(shù)學精確求解的計算量成指數(shù)倍增長，求解問題也就變得毫無可能。相比精確求解法，啟發(fā)式算法則有其獨特的優(yōu)勢。啟發(fā)式規(guī)則的建立是運用啟發(fā)式算法的基礎(chǔ)，Egbelu等[13]整理了在作業(yè)車間中產(chǎn)生的調(diào)度問題中涉及到的啟發(fā)式規(guī)則，這些規(guī)則包括運行時間最長/短、運送距離最長/短、隊列中剩余輸出空間最小/大、AGV閑置時間最短/長和最近/遠AGV等，最終得出這些規(guī)則對系統(tǒng)作業(yè)性能的影響。Jawahar等[14]則提出一種啟發(fā)式算法，他們研究生產(chǎn)過程中AGV調(diào)度系統(tǒng)運行和生產(chǎn)過程結(jié)合起來的問題，該啟發(fā)式算法采用操作時間、運輸時間等AGV分派的相關(guān)因素來解決指派沖突。Sabuncuoglu等[15]研究了柔性制造系統(tǒng)在交貨期不同時AGV調(diào)度規(guī)則的變化對機床工件調(diào)度會產(chǎn)生何種影響。Singh等[16]探究使用仿真模擬的方式解決調(diào)度問題，他們的研究采用自定義的調(diào)度規(guī)則，評估了進行物料分配的AGV調(diào)度問題中物料分配效率和均勻性的仿真性能。Kim等[17]對啟發(fā)式規(guī)則提出了他們的觀點——一種多屬性指標加權(quán)法，這種方法在解決考慮AGV空載路程和工件等待時間這兩項因素為主要因素時，被證明為有效的。Ulusoy等[18]則認為柔性制造系統(tǒng)包含AGV調(diào)度問題，也就是將柔性制造系統(tǒng)看作機床調(diào)度和AGV調(diào)度2個子問題，采用迭代啟發(fā)式方法結(jié)合滑動時間窗進行處理。還有一些學者則是采用建模與仿真方法進行求解。Cenk等[19]同樣認為柔性制造系統(tǒng)包含AGV調(diào)度問題和柔性機床，通過建立智能柔性制造系統(tǒng)對柔性機床和AGV進行同時在線調(diào)度。Nishi等[20]采用時間Petri網(wǎng)分解方法進行AGV調(diào)度與無沖突路徑規(guī)劃。而Giglio等[21]則將AGV的管理權(quán)分派給一個新的混合系統(tǒng)，這個系統(tǒng)由Petri網(wǎng)和多Agent系統(tǒng)共同組成，其中Petri網(wǎng)主要描述路徑，AGV行為和車間中的其他資源相互之間的關(guān)系，行為決策則由Agent系統(tǒng)負責。Yim等[22]針對柔性制造系統(tǒng)結(jié)合Petri網(wǎng)建立模型，將AGV的分派系統(tǒng)聯(lián)合Petri網(wǎng)共同控制AGV指派。采用模擬方法研究不同AGV分派規(guī)則對FMS運行的影響。Olatunde等[23]采用時間有色Petri網(wǎng)(TimedColouredPetriNet，TCPN)和混合啟發(fā)式搜索方法求解機床和AGV同時調(diào)度問題。Mousavi等[24-25]針對多目標AGV調(diào)度問題，對求解結(jié)果采用Flexsim仿真軟件進行驗證。Viharos等[26]采用離散事件仿真方法對機器人裝配系統(tǒng)中每臺工作站的裝配工序和AGV進行調(diào)度控制，使總的制造時間最短。1.2.2國內(nèi)研究現(xiàn)狀國內(nèi)關(guān)于倉儲物流機器人調(diào)度問題相關(guān)研究比國外要晚近30年[3]。國內(nèi)學者對于精確求解法，排隊論法等傳統(tǒng)分析方法研究較少，馬越匯等[27]采用混合整數(shù)規(guī)劃模型研究自動化集裝箱碼頭在考慮交通擁堵等不確定情況下的AGV調(diào)度與配置問題?；魟P歌等[28-29]將自動化集裝箱碼頭多載AGV調(diào)度問題描述為混合整數(shù)規(guī)劃模型，并使用數(shù)學精確求解的方法求解。管賢平等[30]研究提出一種多屬性任務(wù)調(diào)度方法，這種任務(wù)調(diào)度方法能動態(tài)調(diào)整權(quán)值，且可以避免調(diào)度目標發(fā)生鎖死現(xiàn)象。肖海寧等[31]在管賢平等人研究的基礎(chǔ)上增加在線實時調(diào)度的要素，提出柔性制造系統(tǒng)中AGV在線實時多屬性任務(wù)調(diào)度的方法，此方法通過啟發(fā)式調(diào)度規(guī)則有效防止系統(tǒng)鎖死的發(fā)生。黃一鈞[32]建立排隊論模型，以最小總成本為目標，求解AGV的最佳數(shù)量配置問題。金芳等[33]采用逗留時間和平均等待長度為指標，建立基于啟發(fā)式規(guī)則的調(diào)度算法，用于解決AGV調(diào)度中出現(xiàn)的N/M/1排隊模型。對于建模與仿真方法，國內(nèi)學者則有大量的研究，桑澤磊[34]運用合同網(wǎng)協(xié)議下的協(xié)商機制，建立以Agent系統(tǒng)為基礎(chǔ)的信息平臺，用以車間內(nèi)的AGV調(diào)度，該平臺的魯棒性和柔性較好，且能對環(huán)境擾動及時做出響應(yīng)，調(diào)度效率較高。經(jīng)建峰[35]則提出多AGV調(diào)度中，AGV相互之間自主交流的協(xié)商機制，給出各個AGV之間出現(xiàn)沖突時，解決沖突的途徑，進而建立一種分布式的AGV調(diào)度系統(tǒng)。李曉萌等[36]基于Agent系統(tǒng)結(jié)合協(xié)作學習、多級決策理論提出一套獨特的動態(tài)分布式調(diào)度策略，用以解決任務(wù)調(diào)度中多AGV的調(diào)度問題。任小龍[37]針對FMS中工件加工和AGV運送物料同步調(diào)度問題，以Petri網(wǎng)為基礎(chǔ)建立相關(guān)模型，用以研究任務(wù)調(diào)度，尋求更優(yōu)的AGV分派、規(guī)劃策略。李國飛[38]則以Petri網(wǎng)為基礎(chǔ)提出二次變遷Petri網(wǎng)分解方法，這種方法等價于將Petri網(wǎng)模型拆分成多個子網(wǎng)，每個子網(wǎng)對應(yīng)不同的AGV，同時為多個AGV求解不同時刻下Petri網(wǎng)變遷激活的順序，以獲得整體最優(yōu)路徑問題。柯冉絢等[39]基于Netlog軟件針對自動化集裝箱碼頭建模并進行仿真模擬獲得車道數(shù)、岸橋與AGV的最佳配比。李軍濤等[40]通過比較交叉環(huán)單向循環(huán)搬運系統(tǒng)在制定不同的調(diào)度規(guī)則時AGV的搬運效率，運用仿真模擬手段，找出更為優(yōu)質(zhì)的調(diào)度規(guī)則。楊武平[41]對工件派工規(guī)則和AGV調(diào)度這兩個問題形成的類組合策略優(yōu)化問題進行了研究，在模具智能車間背景下，通過Plant-Simulation求解了該問題。韓曉龍[42]采用em-plant建立仿真模型對自動化集裝箱港口中AGV數(shù)量配置及任務(wù)調(diào)度策略進行分析，提出了有效的解決方案。對于倉儲物流機器人調(diào)度問題而言，往往只用一類方法是很難解決實際問題的，雖然我們可以從仿真模擬實驗中建立的實際情況模型模擬現(xiàn)實中的情況，方便求解，但卻很難從仿真實驗中尋找到一般性規(guī)律；而傳統(tǒng)分析法容易發(fā)現(xiàn)規(guī)律，但卻難以求解。因此，對實際調(diào)度問題的研究，通常是先用傳統(tǒng)分析法尋求一般規(guī)律，再根據(jù)規(guī)律進行仿真模擬，最終得出優(yōu)化策略。總之，通過對國內(nèi)外研究現(xiàn)狀的了解，在倉儲物流機器人任務(wù)調(diào)度問題的研究上，國內(nèi)外學者都已經(jīng)取得了一定的進展，但隨著物流行業(yè)的飛速發(fā)展，物流需求的不斷提高，對倉儲物流機器人的調(diào)度效率要求也在漸漸提高。因此，在倉儲物流機器人調(diào)度問題上，提出一種可行且高效的調(diào)度算法十分必要。1.3論文研究內(nèi)容及技術(shù)路線論文通過搜集整理倉儲物流機器人調(diào)度問題的研究現(xiàn)狀，詳細分析并闡述倉儲物流中搬運機器人的主要任務(wù)，并根據(jù)其調(diào)度過程通過建立數(shù)學模型對實際的倉儲物流機器人任務(wù)調(diào)度問題加以描述。論文對煙花算法和其他各類智能算法的實現(xiàn)原理，算法步驟和算法優(yōu)缺點進行整理，結(jié)合倉儲物流機器人任務(wù)調(diào)度問題，提出一種基于煙花算法且適用于倉儲物流機器人任務(wù)調(diào)度的任務(wù)調(diào)度算法。該算法結(jié)合倉儲物流機器人任務(wù)調(diào)度特點，對煙花算法的算子進行改進，并驗證改進后的算法在解決一般性問題是否具備有效性。最后對實例問題進行實驗設(shè)計，通過實驗得出的實驗結(jié)果對得到的結(jié)果進行分析，分析得出改進后的煙花算法在解決倉儲物流機器人任務(wù)調(diào)度問題上具備一定優(yōu)勢，其算法收斂速度較快，得到的任務(wù)調(diào)度序列所耗費的總時間與其他算法、基本煙花算法相比更短一些，這意味著該算法在求解精度上同樣具備優(yōu)勢。論文的主要內(nèi)容包括:（1）研究倉儲物流機器人調(diào)度問題的類型及特點，對倉儲物流機器人調(diào)度任務(wù)基本流程，步驟進行介紹和分析。（2）通過研究煙花算法基本原理，算法步驟，實現(xiàn)過程，分析煙花算法在解決調(diào)度問題上具備的優(yōu)勢和不足，對于算法容易陷入局部最優(yōu)的缺陷，提出熄滅算子對煙花爆炸中產(chǎn)生的相對劣質(zhì)的煙花進行處理，篩選劣質(zhì)煙花產(chǎn)生火花中距離較近的火花，將其熄滅并重新爆炸產(chǎn)生新的火花。對于收斂速度方面，為提升其效率，優(yōu)化選擇算子的選擇策略，加快收斂速度。（3）結(jié)合煙花算法提出一種倉儲物流機器人調(diào)度算法。倉儲物流機器人任務(wù)調(diào)度問題是離散型問題，而煙花算法面向的是解空間連續(xù)的優(yōu)化問題，所以針對倉儲物流機器人任務(wù)調(diào)度問題的特點，對煙花算法中爆炸算子的爆炸范圍，子代數(shù)目等參數(shù)參與計算的方式進行重設(shè)計，同時為了有效增加種群的多樣性，將高斯變異火花用遺傳算法中的基因變異法替代。（4）通過對各種智能算法的了解、分析，結(jié)合倉儲物流機器人任務(wù)調(diào)度問題的背景設(shè)計仿真模擬實驗，仿真實驗選用矩陣計算更加高效的Matlab進行，將改進后的算法與遺傳算法相比較，驗證改進煙花算法對解決該問題具備優(yōu)勢，將改進后的煙花算法和改進前的相比較，驗證改進后算法的有效性，最終得出該算法擁有更快的收斂速度，在求解精度上也更具優(yōu)勢。1.3.1論文組織結(jié)構(gòu)第一章是全文的緒論，這部分主要是對論文的選題背景、論文研究的目的和選擇倉儲物流機器人任務(wù)調(diào)度研究作為選題的意義進行詳細介紹，通過研究國內(nèi)外專家學者在和倉儲物流機器人任務(wù)調(diào)度相類似的問題上的已有研究，提出研究倉儲物流機器人調(diào)度算法的必要性，最后對本文的組織結(jié)構(gòu)進行簡要的介紹，明確本文的研究內(nèi)容。第二章則聚焦倉儲物流系統(tǒng)，首先通過路徑模型概述，了解倉儲物流系統(tǒng)的類別，接著通過對任務(wù)調(diào)度原理的分析，得出倉儲物流機器人調(diào)度問題的特點，并探索任務(wù)調(diào)度的步驟。通過對倉儲物流調(diào)度問題的基本描述，建立倉儲物流機器人調(diào)度的基本模型，為后文中對倉儲物流機器人任務(wù)調(diào)度實例的相關(guān)研究打下堅實基礎(chǔ)。最后對專家學者們研究任務(wù)調(diào)度問題常用的一些智能算法進行簡單的介紹。第三章從倉儲物流機器人調(diào)度任務(wù)實例出發(fā)，對實例倉庫進行建模分析，將倉庫環(huán)境以節(jié)點網(wǎng)絡(luò)的形式展現(xiàn)出來，并對實例調(diào)度問題的優(yōu)化目標做出定義，而后又結(jié)合改進煙花算法和遺傳算法特點，提出兩種算法在倉儲物流機器人調(diào)度任務(wù)中需要進行哪些步驟，明確實例倉庫情形下任務(wù)調(diào)度各步驟中的工作內(nèi)容。第四章是對煙花算法的研究及改進，通過對煙花算法的原理，算法組成，算法步驟，算法優(yōu)缺點的介紹，分析出基本煙花算法在解決優(yōu)化問題中的不足，并提出改進方法，用增加熄滅算子的方式對劣質(zhì)煙花產(chǎn)生的近距離火花實施熄滅處理，增加劣質(zhì)火花對遠距離空間的探索范圍，提高煙花種群的多樣性，避免算法陷入局部最優(yōu)，增加算法的求解精度。最后通過測試函數(shù)對改進后的煙花算法有效性進行驗證。證明改進煙花算法確實有解決一般優(yōu)化目標問題的可行性。第五章主要以第三章所提出的實例模型為基礎(chǔ)，對煙花算法和遺傳算法兩種算法的對比實驗進行設(shè)計，確定仿真模擬實驗運行的各項參數(shù)，通過實驗得出仿真模擬數(shù)據(jù)，并對得出的數(shù)據(jù)進行簡要的分析和探討，最終得出改進煙花算法在倉儲物流機器人調(diào)度問題上有著收斂速度較快求解，精度較高的優(yōu)勢。

1.3.2技術(shù)路線圖1.2技術(shù)路線圖

第2章倉儲物流系統(tǒng)研究2.1路徑模型概述隨著導航定位技術(shù)的不斷更新?lián)Q代以及信息通訊技術(shù)的飛速發(fā)展，倉儲物流機器人的導引方式越來越多樣化。如前所述，目前為止在實際應(yīng)用環(huán)境中主流的倉儲物流機器人按照引導方式可分為地磁導引，通過在物流機器人運行路徑上設(shè)置磁體引導機器人移動；導軌導引，通過在物流機器人運行路徑上設(shè)置導軌引導機器人移動；激光導引，通過在物流機器人運行路徑上設(shè)置激光制導裝置引導機器人移動；慣性導引，利用慣性引導機器人移動；地圖導引，在物流機器人管理系統(tǒng)中預(yù)先設(shè)置匹配的地圖引導機器人移動。引導方式還可以從路徑是否固定大體分為固定路徑與非固定路徑。根據(jù)現(xiàn)有的倉儲物流機器人通行規(guī)則和應(yīng)用環(huán)境等剛性需求，智能倉儲物流系統(tǒng)中路徑模型主要可分為四種情形[43]:（1）在一個智能倉儲物流系統(tǒng)中，任意時間段內(nèi)的任意一條通路只能允許一臺倉儲物流機器人通過，在這條通路上，機器人也只能沿著一個固定的方向前進，不能反向行駛，這種路徑模式被稱為單通路單向路徑模型。在這種路徑模型下，所有的通路都不存在對向沖突，是一種較為簡單的通路模型，但由于通路只能單項同行，前面的機器人在裝卸貨物時，后面的機器人只能等待，而路徑選擇方面也會受到非常大的限制，運輸效率相對其他路徑模式而言非常低下。（2）單通路雙向模型；顧名思義，這種路徑模型與單通路單向路徑模型相似，同樣對于任意的通路只讓一臺倉儲物流機器人通過，不同的是這種模型允許機器人反向行駛。這意味著可能出現(xiàn)兩臺機器人對向行駛的情況，這也是此類路徑模型下調(diào)度系統(tǒng)需要考慮的問題。由于機器人可以雙向行駛，在路徑選擇上更加自由，較單向通行的模型提升了運輸效率，相對的也使得運輸環(huán)境更加復(fù)雜，對調(diào)度系統(tǒng)的調(diào)度策略要求更高。（3）雙通路單向模型；現(xiàn)實生活中的道路交通基本使用的都是這種路徑模式，在該路徑模型中，每條道路都可以讓兩臺機器人同時通行，且通行的方向互為反向，如道路左側(cè)只允許向東，右側(cè)只允許向西。這樣的路徑模型較前兩種更加靈活，避免大部分的對向行駛沖突，運輸效率也因此提升不少。需要考慮的是在路口處，由于雙通道且單向允許通行的規(guī)則，組合情況較多，對調(diào)度能力的要求也更高。（4）雙通路雙向模型；雙通路雙向模型是四種通路模型中最為靈活的一種。靈活性的提升主要原因在于每條通路的兩條路徑都允許兩種方向的機器人通行，這極大的提升了道路的通行效率，而代價則是對調(diào)度能力的要求也大幅度提升。這里的調(diào)度能力涉及到的關(guān)鍵部分是動態(tài)調(diào)度部分，在處理多個執(zhí)行任務(wù)的機器人在同一通路發(fā)生對向沖突或是路口處的路徑選擇問題上，需要考慮多種情況，這對采用該路徑模型的調(diào)度系統(tǒng)運行效率來說是巨大的考驗。本文所使用的模型在通行方向上是雙向的，通路方向上則是單向的。2.2任務(wù)調(diào)度原理2.2.1任務(wù)調(diào)度問題分類根據(jù)倉儲物流機器人在執(zhí)行任務(wù)期間獲取信息的情況，可將倉儲物流機器人調(diào)度問題分為倉儲物流機器人靜態(tài)調(diào)度,倉儲物流機器人動態(tài)調(diào)度和倉儲物流機器人資源聯(lián)合調(diào)度:圖2.1三種任務(wù)調(diào)度過程示意圖（1）倉儲物流機器人靜態(tài)調(diào)度倉儲物流機器人靜態(tài)調(diào)度是指在某一靜態(tài)時刻，通過對倉儲物流機器人指派任務(wù)序列，解決倉儲物流機器人調(diào)度問題。靜態(tài)調(diào)度問題常見于基礎(chǔ)算法或基本模型的研究，為了體現(xiàn)算法有效性，模型的準確性，靜態(tài)調(diào)度可以直觀的反應(yīng)算法或模型變化帶來的性能指標變化。其常見的優(yōu)化目標包括:任務(wù)時間最短，倉儲物流機器人利用率最高，倉儲物流機器人數(shù)量最少，拖期延遲最小，物流成本最低等。其常見的約束則包括:倉儲物流機器人容量約束，倉儲物流機器人充電約束，任務(wù)順序約束，路徑方向約束等。（2）倉儲物流機器人動態(tài)調(diào)度倉儲物流機器人動態(tài)調(diào)度是指在考慮動態(tài)擾動，如任務(wù)變更、設(shè)備故障、沖突死鎖等問題下，通過對倉儲物流機器人進行實時任務(wù)指派，解決倉儲物流機器人調(diào)度問題。動態(tài)調(diào)度更接近實際生產(chǎn)中的情形，多適用于解決實際的問題。其常見的優(yōu)化目標包括:任務(wù)時間最短，倉儲物流機器人數(shù)量最少，搬運時間最短，倉儲物流機器人利用率最大，倉儲物流機器人負荷均衡，倉儲物流機器人最小行走時間等。其常見約束則包括:倉儲物流機器人容量約束，倉儲物流機器人充電約束，任務(wù)順序約束，路徑方向約束等。（3）倉儲物流機器人資源聯(lián)合調(diào)度倉儲物流機器人資源聯(lián)合調(diào)度多出現(xiàn)于生產(chǎn)制造系統(tǒng)當中一般為多目標優(yōu)化問題，資源聯(lián)合調(diào)度主要是指在倉儲物流機器人調(diào)度過程中需要考慮其他生產(chǎn)工序的資源產(chǎn)出或使用情況，然后根據(jù)這些情況對倉儲物流機器人實施任務(wù)指派，以達到任務(wù)調(diào)度期望達到的優(yōu)化目標。調(diào)度問題中最常見的幾類優(yōu)化目標包括：完成任務(wù)時間最短，消耗資源最少，資源利用率最大，懲罰成本最低，倉儲物流機器人負荷均衡，每個工件在隊列中等待時間最少等。而常見的優(yōu)化目標約束則包括:工件隊列中的緩沖量，工件工序約束，倉儲物流機器人容量約束，倉儲物流機器人充電約束，任務(wù)順序約束，路徑方向約束等。本文研究的倉儲物流機器人任務(wù)調(diào)度問題屬于倉儲物流機器人靜態(tài)調(diào)度問題，靜態(tài)調(diào)度問題可以通過仿真模擬對比實驗更準確的反應(yīng)本文提出算法的有效性。2.2.2任務(wù)調(diào)度步驟倉儲物流機器人任務(wù)調(diào)度系統(tǒng)主要工作步驟可分為三層:生成任務(wù)，分配任務(wù)，完成任務(wù)。其中，分配任務(wù)和完成任務(wù)稱為資源分配，在系統(tǒng)生成的任務(wù)全部完成之前，智能倉儲物流系統(tǒng)將會不間斷的進行任務(wù)的分配并指導倉儲物流機器人完成任務(wù)，直至系統(tǒng)不再生成新的任務(wù)。（1）生成任務(wù)。本文系統(tǒng)中由于不包含上位機系統(tǒng)，因此本文中所有實驗的任務(wù)均為人工生成。（2）分配任務(wù)。系統(tǒng)在分配任務(wù)時需要對未完成任務(wù)的目標地點和空閑的倉儲物流機器人情況進行實時的監(jiān)測，在系統(tǒng)生成新的任務(wù)后能夠立即根據(jù)目標地點將任務(wù)分配給空閑且狀態(tài)正常的倉儲物流機器人。分配任務(wù)的主要約束就是均衡性，在保證所有任務(wù)完成時間最短的前提下，實現(xiàn)任務(wù)的均衡分配。（3）完成任務(wù)。完成任務(wù)的過程為倉儲物流機器人從起始地點到達任務(wù)的目的地，即為路徑規(guī)劃過程。為了高效有序的完成任務(wù)，需要對倉儲物流機器人進行路徑規(guī)劃，而路徑規(guī)劃的合理性也影響著任務(wù)的分配。系統(tǒng)需要根據(jù)任務(wù)的具體分配情況來對倉儲物流機器人進行路徑規(guī)劃，保證倉儲物流機器人在無死鎖、無沖突的情況下完成任務(wù)，并也要根據(jù)任務(wù)的完成情況來對任務(wù)的分配進行調(diào)整，力求倉儲物流機器人完成任務(wù)時間最短。2.2.3基礎(chǔ)問題描述普通的倉儲物流布局由倉儲物流機器人，貨物存放區(qū)，貨物裝卸區(qū)組成，整個環(huán)境布局圖如圖2.2所示，藍色膠囊為倉儲物流機器人以及其起始區(qū)域，黃色方塊表示貨架，最下面是完成任務(wù)的卸貨區(qū)，兩個貨架之間的通道允許兩臺倉儲物流機器人并排通過，中間通道可允許兩臺倉儲物流機器人并排通過。圖2.2倉儲物流布局圖為了方便求解，本文將整個環(huán)境轉(zhuǎn)化為節(jié)點圖形式，倉儲物流機器人起始節(jié)點為一個節(jié)點。貨架每個貨物位置為一個節(jié)點，貨物裝卸區(qū)為一個節(jié)點，并且將倉儲物流機器人起始位置設(shè)為1號節(jié)點，貨物按順序編號2到n節(jié)點，裝卸區(qū)為最后一個節(jié)點。為了保證倉儲物流機器人調(diào)度系統(tǒng)的順暢運行，本文對調(diào)度過程做如下合理假設(shè):（1）倉儲物流機器人裝卸貨時間忽略不計；（2）倉儲物流機器人勻速行駛，不考慮轉(zhuǎn)彎或其他情況造成的減速；（3）每臺倉儲物流機器人可以搬運多個貨物，但不能超出最大載重量；2.4任務(wù)調(diào)度算法智能優(yōu)化算法能解決其他方法難以求解的復(fù)雜組合優(yōu)化問題，因而廣泛應(yīng)用于調(diào)度優(yōu)化方面，倉儲物流機器人調(diào)度中用到的智能優(yōu)化方法包括粒子群算法(ParticleSwarmOptimization,PSO)、遺傳算法(GeneticAlgorithm,GA)、差分進化算法(DifferentialEvolution,DE)、蟻群算法(AntColonyOptimization,ACO)等。（1）遺傳算法遺傳算法（GeneticAlgorithm，GA）的起源最早可以追溯到20世紀60年代初期，當時由Holland教授的學生在其博士論文中首次提出，論文主要探討該算法在博弈中如何應(yīng)用，但這類早期研究缺少指導性理論，也沒有計算工具作為支撐。直到1975年JohnHolland教授出版《自然系統(tǒng)和人工系統(tǒng)的適配》，于該書中對遺傳算法的算法原理，算法的基本方法及步驟進行系統(tǒng)闡述，推動遺傳算法的發(fā)展。遺傳算法本質(zhì)上是模仿生物的進化過程而得出的計算模型[44]，達爾文在生物進化論中提出自然選擇，而現(xiàn)代進化論中提出基因突變的概念，這兩大概念促成了遺傳算法的誕生，遺傳算法也因此成為一種探索最優(yōu)化問題的常用算法。遺傳算法流程如圖2.2所示。圖2.2遺傳算法流程圖通過流程圖可以看出，遺傳算法在求解問題時先將問題的解空間進行染色體編碼，使解和求解用的染色體成一一對應(yīng)關(guān)系，然后隨機產(chǎn)生初始種群，在對當前種群進行交叉、變異操作后，就可以得到新一代的染色體，而后通過計算每條染色體的適應(yīng)度值（目標函數(shù)的最優(yōu)值）來對新一代染色體做出評價，選出最優(yōu)質(zhì)的一部分子代成為下一代的父基因。為了防止以獲得的最優(yōu)解因為處在父代基因中被舍棄，我們會將父代基因中最優(yōu)的解和子代中所有基因相比較，取出其中最優(yōu)的一個基因，讓其必定可以遺傳到子代。這樣就得到歷史最優(yōu)解和子代基因的集合，只要對這個集合再進行上述操作，重復(fù)足夠的次數(shù)后，就能將解無限接近全局最優(yōu)解。遺傳算法在解決任務(wù)調(diào)度問題上具有一定優(yōu)勢，特別是對指派問題的求解上，由于指派問題的解空間一般是不連續(xù)的解空間，遺傳算法的基因序列可以很好的模擬指派任務(wù)的組別和序列，而通過遺傳算法與其他算法的結(jié)合，混合后的算法在擴展性上有著明顯的優(yōu)勢，魯棒性也較好。遺傳算法求解任務(wù)調(diào)度問題的不足主要在于遺傳算法的兩種算子較為復(fù)雜，交叉操作通過交換一對基因中部分基因?qū)崿F(xiàn)，交換后的兩個解和交換前的兩個解相比，在目標函數(shù)上很難體現(xiàn)其迭代規(guī)律，因此遺傳算法在收斂速度上并不具備很大的優(yōu)勢。變異操作本質(zhì)是為了增加解的范圍，防止陷入局部最優(yōu)，但在遺傳算法中變異基因受變異概率影響，其作用效果有限?？偠灾z傳算法在求解中，初始參數(shù)對算法求解情況影響較大，較好的參數(shù)設(shè)定可能提升算法效率，反之亦然。（2）粒子群算法粒子群算法是對自然界中鳥群覓食的過程進行模擬得出的智能算法，這種算法最早由J．Kennedy和R．C．Eberhart等人提出[45][47]。粒子群算法原理與大部分智能算法類似，首先產(chǎn)生初始解集合，然后通過適應(yīng)度值對粒子群中粒子的位置、速度進行改變，引導粒子向更優(yōu)區(qū)域飛行得到全局最優(yōu)解[46]。其算法流程圖如圖2.3所示。圖2.3粒子群算法流程圖在粒子群算法的迭代過程中，根據(jù)粒子群體中的不同個體得出的適應(yīng)度值，驅(qū)使粒子在解空間內(nèi)運動，所有的粒子都在朝極值位置移動，直到得出全局最優(yōu)解。該算法的步驟與參數(shù)設(shè)計都較為簡單，算法本身容易實現(xiàn)，能適用于大部分優(yōu)化求解問題，且在求解過程中算法收斂速度較快。但缺點也很明顯，由于算法全局搜索性不強的特點，容易陷入局部最優(yōu)，在求解離散問題時收斂速度過慢。（3）差分進化算法差分進化算法(DifferentialEvolution，DE)由Storn和Price于1995年首次提出[48-49]。主要用于求解實數(shù)優(yōu)化問題。該算法是一類基于群體的自適應(yīng)全局優(yōu)化算法，屬于演化算法的一種。該算法通過群體內(nèi)個體之間的相互合作與競爭產(chǎn)生的群體智能來指導優(yōu)化搜索的方向。該算法的基本思想是:從一個隨機產(chǎn)生的初始種群開始，通過把種群中任意兩個個體的向量差與另外的個體求和，若得到的新個體適應(yīng)度更優(yōu)，就用新個體代替舊個體，否則依然使用舊個體繼續(xù)執(zhí)行進化操作。以此方式不斷迭代，最終趨近全局最優(yōu)。圖2.4展示了差分進化算法的流程。圖2.4差分進化算法流程圖在基本的差分進化算法中，參數(shù)設(shè)置對算法本身的影響非常大，特別是變異算子中的變異率，該值設(shè)置過小會導致種群的多樣性降低，以至于陷入局部最優(yōu)，該值設(shè)置過大算法就很難收斂。在特定情況下，差分進化算法還可能出現(xiàn)算法停滯。（4）蟻群算法蟻群算法作為放生智能算法的一種，在20世紀90年代被提出。意大利學者Marco．Dorigo等人發(fā)現(xiàn)自然界中蟻群覓食的方式可以作為啟發(fā)式規(guī)則用于算法的求解[50-51]。蟻群覓食主要通過每一只螞蟻在尋找食物過程中在路徑下留下的信息素來傳遞信號，告訴其他螞蟻這條道路上的信息。根據(jù)每條路上的信息素濃度，后面經(jīng)過的螞蟻就會知道如何找到食物。信息素濃度越高，表示該路徑越優(yōu)質(zhì)，反之亦然。圖2.5展示了蟻群算法的算法流程。圖2.5蟻群算法流程圖蟻群算法在求解優(yōu)化問題具備一定的有效性，使用的概率搜索方式使算法更容易尋找到全局最優(yōu)解。由于使用的使正反饋機制作為信息傳遞方式，在算法初期收斂速度相比其他算法更慢，并且在初始時刻，信息素濃度相同的情況下螞蟻選擇路徑使完全隨機的，如果開始得到的為局部最優(yōu)解，在信息素反饋機制下，信息素濃度不斷增加，使算法陷入局部最優(yōu)。2.5本章小結(jié)首先通過路徑模型概述了解倉儲物流系統(tǒng)的類別，接著對任務(wù)調(diào)度原理的分析，得出倉儲物流機器人調(diào)度問題的特點，并探索任務(wù)調(diào)度的步驟。通過對倉儲物流調(diào)度問題的基本描述，建立倉儲物流機器人調(diào)度的基本模型，最后對調(diào)度問題常用的智能算法進行簡單的介紹，研究各個算法的算法原理及不足之處，為后面煙花算法的研究打下基礎(chǔ)，也為最終求解倉儲物流機器人任務(wù)調(diào)度問題做好鋪墊。

第3章倉儲物流機器人任務(wù)調(diào)度實例3.1引言上一章本文對倉儲物流系統(tǒng)的路徑模型，任務(wù)調(diào)度原理，任務(wù)描述和基本的任務(wù)調(diào)度模型及算法進行詳細的描述，本章節(jié)主要針對倉儲物流機器人任務(wù)調(diào)度實例進行實例問題描述，建立實例模型并將其轉(zhuǎn)化為數(shù)學模型，最后結(jié)合該問題的優(yōu)化目標對模型的輸入輸出給出清晰定義。3.2倉庫實例建模分析3.2.1實例倉庫現(xiàn)狀任務(wù)調(diào)度實例中的倉庫是某物流公司的成品倉庫，該倉庫于2013年建成，年出庫量約為3萬余件，最大靜態(tài)庫存量5000件，業(yè)務(wù)范圍主要涉及該公司的三類產(chǎn)品，通過該倉庫外發(fā)或儲存。本文主要探討該倉庫的成品存放區(qū)，對于該區(qū)域內(nèi)的成品貨物出入庫過程中，倉儲物流機器人的任務(wù)調(diào)度問題。倉庫左邊為倉儲物流機器人調(diào)度區(qū)，中間貨物存放區(qū)共計擁有100個貨架，沿橫向中軸線兩側(cè)擺放，每側(cè)共計5排貨架，貨架兩邊都可以擺放貨物，每排貨架共有五個貨位。在倉儲物流機器人需要搬運貨物時，首先從倉儲物流機器人調(diào)度區(qū)行駛前往目標貨架，通過機械臂將貨架上的貨物取出放在倉儲物流機器人上，倉儲物流機器人取到貨物則繼續(xù)前往下個目標貨架，直至載滿系統(tǒng)分配的任務(wù)，最終駛向裝卸區(qū)。倉庫平面圖如圖3.1所示。

圖3.1實例倉庫平面布局圖

對于本章的實驗?zāi)Ｐ?，我們可以參照第二章的方法，將倉庫環(huán)境轉(zhuǎn)化為節(jié)點模型，整體模型由倉儲物流機器人，貨架，裝卸區(qū)組成，所有的通道都支持倉儲物流機器人雙向通過。在節(jié)點地圖中每個倉儲物流機器人的路徑都只存在三種情況:起點到任務(wù)地點，任務(wù)地點到下一個任務(wù)地點，任務(wù)地點到終點。而如果將其中的任務(wù)地點到下一任務(wù)地點提取出來，所有的倉儲物流機器人任務(wù)——任務(wù)路徑的總和就是所有的任務(wù)地點的串聯(lián)。這樣就把一個多車輛調(diào)度問題轉(zhuǎn)化成為一個TSP問題，而通過建立節(jié)點與節(jié)點之間的距離表可以將此問題進一步簡化。3.2.2數(shù)學模型構(gòu)建通過對實例倉庫現(xiàn)狀的分析，得出解決倉儲物流機器人任務(wù)調(diào)度問題目標在于如何縮短任務(wù)完成的總時間，對完成任務(wù)總時間的求解涉及到的參數(shù)，變量如下：（1）集合N=1,2,…,n:所 M:貨物節(jié)點集合 P:倉儲物流機器人的集合（2）參數(shù) p:倉儲物流機器人編號 k:第k臺機器人為完成任務(wù)時長最長的機器人 Aij:節(jié)點i到節(jié)點j之間的路段 tij:機器人通過A W：倉儲物流機器人的最大載重量 wi（3）決策變量X倉儲物流機器人在完成任務(wù)的同時要保證路徑最短，即完成任務(wù)時間最短，且在完成任務(wù)過程中不得超過最大載重量。通過以上分析及調(diào)度問題模型建立，可得出目標函數(shù)為:minT=i∈Nj∈Ntijxkij s.t.i∈Nj∈Np∈Ptijp∈Pxpij=1j∈M p∈Pxpijwi≤Wi∈M 式（3-1）為目標函數(shù)，第k臺倉儲物流機器人完成任務(wù)的時間最短,式（3-2）表示第k臺倉儲物流機器人是所有倉儲物流機器人中任務(wù)時長最長的一臺，式（3-3）表示所有的任務(wù)都對應(yīng)一個倉儲物流機器人，即所有的任務(wù)都被完成了，式（3-4）表示所有的倉儲物流機器人都不超過其最大載重量。3.3智能算法對倉儲物流調(diào)度實例模型的求解分析智能優(yōu)化算法要解決的一般是最優(yōu)化問題。最優(yōu)化問題可以分為（1）求解一個函數(shù)中，使得函數(shù)值最小的自變量取值的函數(shù)優(yōu)化問題和（2）在一個解空間里面，尋找最優(yōu)解，使目標函數(shù)值最小的組合優(yōu)化問題。典型的組合優(yōu)化問題有：旅行商問題（TravelingSalesmanProblem，TSP），加工調(diào)度問題（SchedulingProblem），0－1背包問題（KnapsackProblem），以及裝箱問題（BinPackingProblem）等。經(jīng)典的優(yōu)化算法有很多，按照搜索域的大小可分為：局部搜索算法，全局搜索算法；按照規(guī)劃問題的靜動態(tài)可分為：靜態(tài)規(guī)劃，動態(tài)規(guī)劃；按照優(yōu)化目標是否線性可分為：線性規(guī)劃，非線性規(guī)劃；按照求解規(guī)則可分為：智能算法，數(shù)學精確求解法。而智能算法又包括遺傳算法，粒子群算法等仿生算法。求解特定的最優(yōu)化問題，并不是所有的優(yōu)化算法都能起到很好的效果，而是需要具體問題具體分析。本文提到的算法都是從局部搜索算法中發(fā)展而來，所謂局部搜索算法是指利用貪婪思想在函數(shù)的領(lǐng)域進行求解搜索，當算法找到一個更優(yōu)值時，就放棄前一個值。這種搜索方法在沒有其他極值干擾的情況下效率很高，但出現(xiàn)其他極值時就容易陷入局部最優(yōu)。而現(xiàn)有的智能算法對算法的策略進行改進，使其通過多個算子同時進行局部搜索，強制移動解的位置等類似的方法使搜索域擴大，提高算法發(fā)現(xiàn)全局最優(yōu)值的概率。智能算法在求解過程中使用的解空間一般為連續(xù)解空間，而倉儲物流機器人調(diào)度問題的解空間則是離散解空間，針對這個問題一般有兩種解決途徑，一是通過映射將離散解空間編碼，使其成為相對連續(xù)的解空間，然后直接用算法進行求解，二是對算法進行調(diào)整，使其能夠?qū)﹄x散解空間進行求解。在調(diào)度問題中，解空間可以看作一個任務(wù)節(jié)點矩陣，需要注意的是由于所有的任務(wù)必須完成，所以解空間不能有重復(fù)的或者遺漏的任務(wù)，也就是說，倉儲物流調(diào)度問題的解空間實質(zhì)上是一個任務(wù)列表的MTSP問題，而不同解之間的距離可以看成任務(wù)列表的差異程度。根據(jù)求解過程分析，結(jié)合算法特點，提出算法基礎(chǔ)步驟如下:步驟1:初始化解空間；步驟2:計算當前解集中各個解的適應(yīng)度值。步驟3:篩選出優(yōu)秀的子代解；步驟4:增加變異解；步驟5:保留優(yōu)秀子代；步驟6:判斷是否滿足終止條件，滿足則終止不滿足則轉(zhuǎn)至步驟2；步驟7:通過累計概率值進行輪盤賭操作，對適應(yīng)度好的個體提供更大的被選中概率；步驟8:輸出最優(yōu)序列，算法終止；

第4章煙花算法及其改進策略4.1煙花算法工作原理分析煙花算法最初是由譚營教授在2010年提出的一種非生物種群群體智能優(yōu)化算法[52-54]。該算法是一種并行式尋優(yōu)算法，模擬煙花爆炸的過程，這種組合優(yōu)化算法在求解復(fù)雜的優(yōu)化問題上性能良好[55]。煙花算法的基本步驟與其他的智能算法，包括仿生算法的步驟大致一樣，先根據(jù)初始解確定初始種群，接著對初始種群進行爆炸操作，產(chǎn)生下一代煙花的候選者，經(jīng)過變異篩選，選出適應(yīng)度值較優(yōu)的一部分火花作為下一代煙花，多次迭代最終得出最優(yōu)解。4.1.1煙花算法的組成煙花算法主要由爆炸算子，變異算子以及選擇策略三部分組成，在爆炸算子和變異算子中通過映射規(guī)則將產(chǎn)生的越界火花映射回解空間。煙花算法的變異算子屬于高斯變異算子，變異過程如圖4.1所示。圖4.1高斯變異流程圖高斯變異操作實際上是利用高斯分布概率函數(shù)產(chǎn)生一個隨機數(shù)，用產(chǎn)生的隨機數(shù)對原本的火花進行一定程度的位移，以達到增加種群多樣性的目的。通過爆炸算子和變異算子的操作，特別是變異算子，產(chǎn)生的火花可能會出現(xiàn)超出解空間的情況，這是因為變異根據(jù)高斯分布概率產(chǎn)生的隨機數(shù)進行，這就有可能產(chǎn)生非常大或非常小的數(shù)字。對于這類火花，因為其攜帶一定的信息，不能將其直接舍去。所以需要對其進行映射操作，將保存下的信息利用起來。隨后，運用篩選策略在新的煙花種群中選出下一代煙花。篩選操作包含兩個步驟，首先根據(jù)精英選擇策略將質(zhì)量最好的煙花保留到下一代，再根據(jù)基于距離的選擇策略選擇剩余的煙花。煙花算法的框架如圖4.2所示。圖4.2煙花算法框架圖4.1.2煙花算法實現(xiàn)原理煙花算法是將煙花在空中爆炸的過程應(yīng)用于解空間的探索模式，在此基礎(chǔ)上增加特定的選擇策略而形成的智能算法[54]，煙花算法在爆炸后產(chǎn)生大量火花，對這些火花進行變異后，選擇一部分適合的火花作為下一代煙花保存下來，這就完成了一次迭代，當?shù)螖?shù)達到設(shè)定值，或是求得的解達到求解精度要求時，煙花算法就輸出當前最優(yōu)解并終止算法。這個過程主要包括以下基本的步驟[55]:(1)初始化參數(shù)并產(chǎn)生初始解，根據(jù)初始解生成初始煙花種群。(2)對當前的種群中所有個體計算其適應(yīng)度值(3)對每個煙花個體進行爆炸算子操作，爆炸的參數(shù)根據(jù)初始設(shè)定的參數(shù)和適應(yīng)度值計算得到。爆炸后產(chǎn)生的火花和爆炸前適應(yīng)度最優(yōu)的煙花共同組成新的種群。(4)將新的種群根據(jù)變異概率選擇少量火花進行變異操作，用以增加種群的多樣性(5)根據(jù)選擇策略對當前種群進行篩選，并計算出所選的種群中最優(yōu)的適應(yīng)度值，若該值滿足求解精度要求或達到迭代的最大值，則算法終止，否則返回第二步。煙花算法的爆炸算子設(shè)計中，為了避免算法過早收斂于局部最優(yōu)值，進行爆炸的煙花遵循著一定的規(guī)律，即優(yōu)質(zhì)的煙花在爆炸過程中能產(chǎn)生更多的火花，且火花較為集中，而劣質(zhì)的煙花在爆炸過程中產(chǎn)生的火花則非常稀疏，并且分布的范圍更廣。從圖4.3可以看出，兩種質(zhì)量的煙花在自然界中爆炸也基本遵循這個規(guī)律。圖4.3爆炸火花質(zhì)量示意圖產(chǎn)生爆炸火花的數(shù)量如公式（4-1）所示。QUOTESi=M?ymax?f(Xi)+εi=1N(y式中 ymax M ——限制火花產(chǎn)生數(shù)量的常數(shù) ε ——為避免出現(xiàn)除零操作，增加的機器最小量在爆炸算子產(chǎn)生火花時，為了避免產(chǎn)生的火花太多或太少而影響算法的性能，需要對計算得出的煙花數(shù)目Si加上一定的限制條件，如公式（4-2）所示。QUOTESi=roundα?M,Si<α?Mroundβ?M,式中 α ——用于確定最少火花數(shù)的常數(shù) β ——用于確定最大火花數(shù)的常數(shù) round() ——對括號中的數(shù)進行四舍五入取整煙花算法在求解過程中為了保證能有效收斂到最優(yōu)值，適應(yīng)度越好的煙花應(yīng)當更加注重局部搜索，即優(yōu)質(zhì)煙花的爆炸半徑應(yīng)當適當縮小，而對于適應(yīng)度差的煙花，只有擴大其搜索半徑，才更有可能找到局部最優(yōu)值所在的位置，即需要擴大劣質(zhì)煙花的爆炸半徑，以達到全局搜索的目的。因此，每個煙花的爆炸半徑可由公式（4-3）表示。QUOTEAi=A?f(Xi)?ymin+εi=1N(f(式中 A ——控制煙花爆炸半徑的參數(shù) ymin 爆炸產(chǎn)生的煙花可以隨機出現(xiàn)在母代煙花的Ai范圍內(nèi)，通過調(diào)整M和A，即可實現(xiàn)對子代搜索范圍的調(diào)整，高效的求解算法取決對搜索范圍的控制，不同情形下，使用不同的搜索策略，能有效提高對該問題的求解速度和精度。為了避免算法陷入局部最優(yōu)，就要使煙花種群增加多樣性，不能只在初始種群附近搜索。煙花算法采用的是高斯變異，變異算子主要將一個服從高斯分布的隨機數(shù)與煙花的位置坐標相乘，得到的新坐標即為高斯變異后的煙花位置坐標。其方法如公式（4-4）（4-5）所示。QUOTExik=xik?e xik=xLB,k+x式中 xik ——煙花i e ——高斯分布函數(shù)的值 xLB,k xUB,k 公式（4-4）表示若煙花i被選為變異個體，則需要對其隨機k個維度進行變異，即將k個維度的值分別乘以一個服從高斯分布函數(shù)的值，而這個值可能非常大，也可能非常小，所以變異后的k個維度可能出現(xiàn)越界情況，于是（4-5）提供了將越界數(shù)據(jù)映射到該維度中可行域中的方式。煙花算法中每一代種群進過爆炸算子、變異算子的操作后，得到的新一代火花個體，計算所有的個體適應(yīng)度值，將適應(yīng)度最優(yōu)的個體保留作為下一次迭代的母本之一，其余的個體保留的規(guī)則按照輪盤賭的方式進行，概率由該個體的適應(yīng)度值和最優(yōu)個體的適應(yīng)度值的比值決定，即適應(yīng)度越好的個體越由概率被選中，但不是必定選中輪盤賭概率如公式（4-6）所示。QUOTEPi=fifmax 其中fi表示輪盤賭決定是否保留火花個體的適應(yīng)度值，fmax表示這一代火花個體中適應(yīng)度最好，即已經(jīng)被確定保留的火花個體的適應(yīng)度值。煙花算法的流程如圖4.4所示。圖4.4煙花算法流程圖算法4.1煙花算法偽代碼算法4.1煙花算法偽代碼1：初始化相關(guān)參數(shù)2：生成M個初始解，即初始煙花集合Parent_X3：計算Parent_X的適應(yīng)度值集合Parent_X_Fitness4：if最大迭代次數(shù)T>迭代次數(shù)ido5：for母代煙花個體PiinParent_Xdo6：計算母代煙花個體Pi的爆炸產(chǎn)生的子代火花數(shù)量S7：計算母代煙花個體Pi的爆炸范圍A8：while產(chǎn)生子代火花個數(shù)j<Sido9：子代火花集合Candidate_X[j]=rand(0,Ai)10：j=j+111：endwhile12：endfor13：for子代火花中高斯變異火花Xido14：產(chǎn)生變異維度隨機數(shù)k15：xik16：endfor17：for子代火花集合Candidate_Xido18：計算Candidate_Xi的適應(yīng)度值保存至集合Candidate_X_Fitness中19：endfor20：保留最優(yōu)適應(yīng)度值對應(yīng)的子代火花21：for除最優(yōu)適應(yīng)度值外的火花do22：ifPi23：保留該煙花24：endif25：endfor26：i=i+127：endif4.2煙花算法性能分析煙花算法在求解各類復(fù)雜問題中都表現(xiàn)優(yōu)異，如CPU性能優(yōu)化，電網(wǎng)電力配送，垃圾郵件檢測算法，施肥問題等。煙花算法適用于組合優(yōu)化問題，特別是在復(fù)雜問題處理上具有良好的性能，該算法不但具備現(xiàn)有智能算法的種種優(yōu)點，還有以下特色[54]：瞬時性。煙花算法在初始解集合的基礎(chǔ)上生成初代煙花，通過爆炸算子和變異算子產(chǎn)生新一代火花，火花根據(jù)一定的規(guī)則選擇出適合的火花作為下一代煙花，未被選擇的火花就此消失，這便是煙花算法所具備的瞬時性。分布并行性。在算法迭代時，母煙花在可行域內(nèi)爆炸，同時在解空間中的不同區(qū)域進行搜索，這個過程時多個煙花并行的，且每一代煙花都是如此迭代，因此算法具有分布并行性。爆發(fā)性。煙花算法在爆炸算子的操作下，會產(chǎn)生多個火花，而初始煙花一般選擇多個，每個煙花所產(chǎn)生的火花在下一代迭代時又會產(chǎn)生更多的火花，在火花數(shù)目限制范圍內(nèi)，火花是呈指數(shù)倍增長的，這也體現(xiàn)出煙花算法的爆發(fā)性。簡單性。煙花算法在迭代中逐漸接近全局最優(yōu)值，這個過程比較簡單，每個煙花通過設(shè)定好的參數(shù)在周圍產(chǎn)生火花，選擇小部分火花變異后，留下一部分，就完成了一次迭代。可擴充性。煙花算法中每個煙花表示一個解，解的維度可根據(jù)問題的需要求解的變量個數(shù)確定，也就是說煙花算法不僅可以求解二維解空間問題，這種求解能力可以擴展到任意維度的解空間對應(yīng)的問題中。多樣性。種群的多樣性決定一個智能算法是否容易在優(yōu)化問題中陷入局部最優(yōu)解，當種群的多樣性越大，個體的分布越廣，找到最優(yōu)解的可能性越大，同時不會對算法效率造成太大影響。煙花算法在多樣性方面具備一定的優(yōu)勢，主要體現(xiàn)在：a．爆炸算子設(shè)計。在爆炸算子設(shè)計中，煙花會根據(jù)其適應(yīng)度值對爆炸后產(chǎn)生的火花范圍，火花數(shù)量進行初步的限制。適應(yīng)度較差的煙花產(chǎn)生的火花相比適應(yīng)度好的更少，范圍更大，這也是除了變異算子外，煙花算法擁有多樣性，具備全局搜索能力的關(guān)鍵原因。b．高斯變異是煙花算法中第二個增加種群多樣性的操作，高斯變異將爆炸算子中產(chǎn)生的火花通過高斯分布函數(shù)產(chǎn)生的隨機數(shù)進行位置的移動，這種移動通過高斯分布概率控制，移動后的火花不僅可以覆蓋整個解空間，甚至可能超出解空間，于是在變異后，煙花算法采用一定規(guī)則將超出解空間的火花映射回解空間內(nèi)。這種覆蓋全域的操作是主要增加種群多樣性的原因。(7)適應(yīng)性。煙花算法通過計算煙花們的適應(yīng)度值來衡量求出的解的優(yōu)劣，這種特性決定煙花算法不需要被求解問題必須為顯示表達問題，因此煙花算法可以適用于多數(shù)優(yōu)化問題的求解。由煙花算法的特性可見，煙花算法在求解倉儲物流機器人任務(wù)調(diào)度問題上是非常適用的。4.3改進煙花算法對實例模型的求解煙花算法在求解過程中使用的解空間一般為連續(xù)解空間，而倉儲物流機器人調(diào)度問題的解空間則是離散解空間，針對這個問題一般有兩種解決途徑，一是通過映射將離散解空間編碼，使其成為相對連續(xù)的解空間，然后直接用算法進行求解，二是對算法進行調(diào)整，使其能夠?qū)﹄x散解空間進行求解。本文采用的是第二種方法，要將煙花算法改造成求解離散解空間的算法，最主要的是調(diào)整爆炸算子和變異算子，根據(jù)爆炸算子的概念我們知道，爆炸算子是為了將每一代的信息通過距離這一數(shù)值傳遞到下一代煙花中，這樣通過多代信息的啟發(fā)，最終可以慢慢接近全局最優(yōu)解。在調(diào)度問題中，解空間可以看作一個任務(wù)節(jié)點矩陣，需要注意的是由于所有的任務(wù)必須完成，所以解空間不能有重復(fù)的或者遺漏的任務(wù)，也就是說，倉儲物流調(diào)度問題的解空間實質(zhì)上是一個任務(wù)列表的MTSP問題，而不同解之間的距離可以看成任務(wù)列表的差異程度，因此，本文將煙花算法的爆炸算子計算出的爆炸后的位移半徑做了取整處理，將其映射為任務(wù)列表中交換位置的任務(wù)數(shù)量，變異算子相比爆炸算子就簡單很多，將高斯分布函數(shù)得出的函數(shù)值進行邊界檢驗，然后取整，將取整后的數(shù)看作任務(wù)列表中交換位置的任務(wù)數(shù)量。通過對煙花算法的求解過程分析，結(jié)合煙花算法的改進策略，得出改進煙花算法的步驟包括以下10步:步驟1:參數(shù)初始化，設(shè)置最大迭代次數(shù)T，篩選參數(shù)F，煙花初始種群個數(shù)N，爆炸數(shù)量限制參數(shù)a和b，爆炸火花數(shù)量控制參數(shù)M，爆炸范圍控制參數(shù)A，；步驟2:根據(jù)4.1對倉庫調(diào)度模型解空間的可行域分析，隨機初始化N個煙花位置。步驟3:運用爆炸算子計算初代煙花生成的新個體及新個體的適應(yīng)值；步驟4:通過熄滅算子熄滅部分火花，并再次生成等量與熄滅個數(shù)的新火花；步驟5:按照變異概率隨機選擇需要變異的火花，進行變異操作，得到高斯變異火花，將其加入子代集合中；步驟6:對所有子代集合中個體的適應(yīng)度值進行計算并排序；步驟7:通過累計概率值進行輪盤賭操作，對適應(yīng)度好的個體提供更大的被選中概率；步驟8:將當前適應(yīng)度最好煙花的和其他輪盤賭得出的子代煙花保存至下一代；步驟9:判斷算法終止條件是否達成，達成則轉(zhuǎn)至步驟10，沒有達成轉(zhuǎn)至步驟3；步驟10:終止算法并輸出最優(yōu)任務(wù)調(diào)度序列。4.4遺傳算法對實例模型求解遺傳算法在求解調(diào)度問題有著一定的優(yōu)勢，一般優(yōu)化問題在使用遺傳算法進行求解時都需要先將優(yōu)化目標的解先進行編碼，得到編碼后的基因才能開始算法。而調(diào)度問題本質(zhì)上就是一串不重復(fù)的數(shù)字代碼，所以在使用遺傳算法求解調(diào)度問題時可以直接將調(diào)度的任務(wù)序列作為基因使用，這樣既方便計算，也不用在得到最優(yōu)值后還要進行解碼。對于倉儲物流機器人任務(wù)調(diào)度問題，遺傳算法的求解步驟分為以下九個步驟:步驟1:參數(shù)初始化，設(shè)定迭代次數(shù)T、種群規(guī)模N、交叉概率c以及變異概率m；步驟2:生成N個初代基因，并計算每個基因的適應(yīng)度值；步驟3:利用交叉概率局決定參與交叉的初代基因；步驟4:通過累計概率進行輪盤賭，從步驟3得出的初代基因種群中選擇出兩個初代基因進行交叉；步驟5:判斷子代是否達到種群規(guī)模，沒達到則轉(zhuǎn)至步驟3，達到規(guī)模則轉(zhuǎn)至步驟6；步驟6:通過變異概率判子代變異的數(shù)量，并隨機挑選出合適數(shù)量的子代進行變異操作；步驟7:對子代基因種群計算其適應(yīng)度值，將適應(yīng)度最好的個體直接加入下一代，剩下的N-1個子代由輪盤賭概率選擇出；步驟8:判斷算法終止條件達成與否，若條件達成，轉(zhuǎn)至步驟9，若沒有達成則轉(zhuǎn)至步驟3；步驟9:終止算法并將最優(yōu)任務(wù)調(diào)度序列輸出。遺傳算法的交叉規(guī)則一般分為兩種，一種是部分匹配交叉法，一種是順序交叉法，部分匹配交叉法是從兩個父代基因中取位置長度都相同的一段基因，將他們位置交換，剩下的根據(jù)匹配關(guān)系進行逐一替換，替換過后需要對兩段基因都進行沖突檢測，防止一段基因中有兩個相同的基因位。而順序交叉法就簡單很多，即從一個父代基因隨機選擇一段編碼放到子代的對應(yīng)位置，剩下的由另一個父基因按順序?qū)⒉恢貜?fù)的基因放入子代的空位中。這種方法操作容易，且不需要進行基因沖突檢測。因此在最終的實驗里，本文所編寫的遺傳算法代碼中采用的是順序交叉法進行交叉操作。4.5關(guān)于倉儲物流機器人調(diào)度的煙花算法改進策略由于煙花算法在爆炸過程中產(chǎn)生的火花會受到爆炸數(shù)量和爆炸幅度的限制，質(zhì)量較差的火花爆炸范圍大，爆炸數(shù)量少，在隨機產(chǎn)生位移的階段，可能會出現(xiàn)火花都集中在上一代劣質(zhì)煙花附近，從而難以達到劣質(zhì)煙花的探索目的，降低整個種群的多樣性。因此，可以在爆炸過程中，引入熄滅算子，針對適應(yīng)度較差的個體，限制其在近距離范圍內(nèi)產(chǎn)生的火花數(shù)量，這樣不但可以提高劣質(zhì)煙花的搜索效率，也可以減少整個迭代過程中的無效計算量。4.5.1引入熄滅算子基本煙花算法在求解一般優(yōu)化問題和各類組合優(yōu)化問題時，其收斂速度和尋優(yōu)能力都表現(xiàn)良好，但在煙花算法的爆炸算子中，爆炸得出的劣質(zhì)煙花因為其爆炸數(shù)量和范圍受煙花本身的適應(yīng)度影響，只會產(chǎn)生少量火花，而這些火花時該算法提升尋優(yōu)能力的關(guān)鍵，一旦生成的火花太過接近煙花本身，劣質(zhì)煙花提升尋優(yōu)能力的功能就無法發(fā)揮。最終導致算法陷入局部最優(yōu)。為了避免劣質(zhì)煙花有可能不產(chǎn)生遠距離煙花的問題，本文引入熄滅算子，針對劣質(zhì)煙花的產(chǎn)生的火花進行篩選，將距離過近的火花熄滅，并重新產(chǎn)生火花。篩選的距離標準使用歐氏距離來衡量。劣質(zhì)煙花的評價標準按照種群適應(yīng)度平均值來設(shè)定，而熄滅火花的范圍則通過母代煙花的爆炸半徑和子代火花適應(yīng)度與最優(yōu)火花適應(yīng)度差值的比值來確定，這樣既能保證優(yōu)質(zhì)火花不被熄滅，也可以提供更好的探索能力。篩選操作如公式（4-7）所示。QUOTEri=Ai?F?ymax?f(xi)f(x 式中 ri—— f(i)——i煙花的適應(yīng)度值 ymax Ai F——熄滅算子參數(shù)算法4.2熄滅算子偽代碼算法4.2熄滅算子偽代碼1：初始化相關(guān)參數(shù)，載入母代煙花Parent_X2：篩選出適應(yīng)度低于F的較差煙花Xi3：計算X的適應(yīng)度值集合X_Fitness，記最優(yōu)適應(yīng)度值為X_Fitness_max4：for所有較差煙花do5：ifri=6：移除子代火花Xi7：重新由母代煙花Parent_X生成一個子代火花8：endif9：endfor4.5.2改進算法有效性驗證對于改進后的煙花算法，是否能在求解優(yōu)化問題中快速收斂，得到精度較高的解，是算法是否具有有效性的關(guān)鍵。為了驗證改進后的煙花算法的有效性，本文選取了常見的CEC測試函數(shù)，通過對這些函數(shù)的求解，驗證有效性的問題。實驗環(huán)境為MatlabR2014b,處理器為InternetCoreI7,內(nèi)存4G，操作系統(tǒng)為Windows10的計算機。表4.1為改進煙花算法的參數(shù)。表4.1改進煙花算法參數(shù)設(shè)定參數(shù)名參數(shù)值煙花數(shù)8最大迭代次數(shù)1*10^3最大計算次數(shù)5*10^4解空間維度16（1）ACKLEY函數(shù)Ackley函數(shù)是常用于測試優(yōu)化算法求解性能的測試函數(shù)，其函數(shù)圖形如圖4.5所示，可以看到該函數(shù)的全局最小值處于中心位置，在周圍有大量的局部極值，對于爬山算法而言，大量的局部極值提高算法陷入局部最優(yōu)的概率，這也是此函數(shù)成為測試函數(shù)的主要原因。它的函數(shù)表達式為:QUOTEfx=?a?exp?b1di=1圖4.5Ackley函數(shù)改進煙花算法對Ackley函數(shù)求解情況如圖4.6所示。圖4.6改進煙花算法對Ackley函數(shù)求解情況（2）GRIEWANK函數(shù)Griewank函數(shù)也是測試優(yōu)化算法性能的常用測試函數(shù)之一，其特點是局部極小值分布廣泛，而這種分布是具有一定規(guī)律的，規(guī)律分布的極小值會引導算法陷入局部最優(yōu)，以檢驗算法的完備性。函數(shù)表達式如（4-9）所示。QUOTEfx=i=1dxi24000?i=1圖4.6Griewank函數(shù)改進煙花算法對Griewank函數(shù)求解情況如圖4.7所示。圖4.7改進煙花算法對Griewank函數(shù)求解情況從以上兩個測試函數(shù)的實驗結(jié)果可以看出，改進煙花算法在求解最優(yōu)化問題時能快速收斂，且最終能得到精度較高的最優(yōu)值。證明了改進煙花算法用于解決倉儲物流機器人任務(wù)調(diào)度問題的可行性。

第5章實驗方案與結(jié)果分析5.1實驗方案設(shè)計本章節(jié)實驗方案設(shè)計主要基于前文第三章中給出的倉儲物流機器人任務(wù)調(diào)度實例模型進行，為了驗證改進煙花算法的性能，在Matlab平臺設(shè)計實驗對比改進煙花算法和遺傳算法的性能。實驗首先將倉庫實例平面地圖通過距離比例和貨架所在相對位置轉(zhuǎn)化成節(jié)點地圖，轉(zhuǎn)化后的節(jié)點地圖中包含貨架節(jié)點100個，通過對所有節(jié)點相對位置的計算，形成節(jié)點距離表，該表包括所有節(jié)點兩兩的距離關(guān)系，倉儲物流機器人出發(fā)點、卸貨地點和所有節(jié)點的距離關(guān)系。這樣可以減少Matlab在計算適應(yīng)度值時所耗費的時間，由于適應(yīng)度值的計算在算法的比較中不是決定性的差異指標，所以減少這部分的計算時間可以讓對比更加明顯，結(jié)果更加清晰。任務(wù)目標確定則采用隨機生成的任務(wù)節(jié)點，分別在不同規(guī)模下設(shè)計多組實驗驗證改進煙花算法的高效性。（1）第一組對比實驗考察改進煙花算法、遺傳算法在不同任務(wù)規(guī)模下的收斂情況和算法得到的最優(yōu)的調(diào)度策略。由于貨架節(jié)點總量為100個，實驗將任務(wù)規(guī)模從10個到100個每間隔20做一次對比實驗。（2）第二組對比試驗考察改進煙花算法、基本煙花算法在相同任務(wù)規(guī)模下的收斂情況和和算法得到的最優(yōu)的調(diào)度策略。為了控制變量，設(shè)置任務(wù)規(guī)模為50個任務(wù)時，進行多次對比試驗。5.2實驗參數(shù)設(shè)定第一組對比試驗中，通過對任務(wù)規(guī)模的調(diào)整，考察改進煙花算法和遺傳算法的運算情況。表5.1是第一組實驗中兩種算法的初始參數(shù)設(shè)定。其中N表示種群規(guī)模，在煙花算法中表示初始煙花的數(shù)量，在遺傳算法中表示初始染色體的數(shù)量。T表示迭代次數(shù)，即最大循環(huán)的次數(shù)。變異概率M由迭代次數(shù)T決定，迭代次數(shù)越多，變異概率越低。遺傳算法中的參數(shù)包括交叉概率C，表示基因在每次交叉操作中，有C的概率發(fā)生。改進煙花算法中的參數(shù)包括爆炸數(shù)量系數(shù)S，爆炸半徑系數(shù)A和火花數(shù)量系數(shù)a，b。爆炸數(shù)量系數(shù)S表示控制爆炸產(chǎn)生的子代火花數(shù)量的參數(shù)，通過調(diào)整此參數(shù)可以控制煙花產(chǎn)生的子代火花的大致數(shù)量。爆炸半徑系數(shù)A，表示控制爆炸產(chǎn)生的子代火花范圍的參數(shù)，通過調(diào)整此參數(shù)可以控制煙花產(chǎn)生的子代火花的大致范圍?；鸹〝?shù)量系數(shù)a，b表示火花的數(shù)量最少不少于a個，最多不超過b個。表5.1第一組實驗參數(shù)設(shè)定算法參數(shù)名參數(shù)值-迭代次數(shù)T1000-種群規(guī)模N-改進煙花算法爆炸數(shù)量系數(shù)S10爆炸半徑系數(shù)A15火花數(shù)目系數(shù)a0.3火花數(shù)目系數(shù)b0.6遺傳算法交叉概率C0.8變異概率M(T-t)/T第二組對比試驗中通過對相同參數(shù)設(shè)定下的仿真模擬，考察基礎(chǔ)煙花算法和改進煙花算法的求解情況，表5.2是第二組實驗中兩種算法的初始參數(shù)設(shè)定。其中N表示種群規(guī)模，在煙花算法中表示初始煙花的數(shù)量，在第二組實驗中將其固定為50。T表示迭代次數(shù)，即最大循環(huán)的次數(shù)。變異概率M由迭代次數(shù)T決定，迭代次數(shù)越多，變異概率越低。爆炸數(shù)量系數(shù)S表示控制爆炸產(chǎn)生的子代火花數(shù)量的參數(shù)，通過調(diào)整此參數(shù)可以控制煙花產(chǎn)生的子代火花的大致數(shù)量。爆炸半徑系數(shù)A，表示控制爆炸產(chǎn)生的子代火花范圍的參數(shù)，通過調(diào)整此參數(shù)可以控制煙花產(chǎn)生的子代火花的大致范圍。火花數(shù)量系數(shù)a，b表示火花的數(shù)量最少不少于a個，最多不超過b個。表5.2第二組實驗參數(shù)設(shè)定參數(shù)名參數(shù)值迭代次數(shù)T1000種群規(guī)模N50爆炸數(shù)量系數(shù)S10爆炸