基于灰狼算法的多目標車間調(diào)度優(yōu)化研究目錄TOC\o"1-3"\h\u30501引言 1284111、問題描述及模型 2265181.1作業(yè)車間調(diào)度問題 2319001．2問題模型 390812、改進灰狼算法 455762.1灰狼算法簡介 4292.2改進策略 4234322.2.1編碼和解碼 480542.3pareto排序 883972.4算法流程 916253、實驗及結(jié)果分析 9261613.1數(shù)據(jù)對比 10280713.2Pareto解集對比 1163954、結(jié)束語 1228108參考文獻 12摘要:群智能算法是一種模擬自然界中動物群體的種群機制和各種社會行為的優(yōu)化計算方法，這類算法因?qū)λ蟮膯栴}無具體要求，實現(xiàn)起來也很方便，在各種優(yōu)化問題中得到了廣泛的應(yīng)用。在群智能算法中，關(guān)鍵點是如何在算法中兼顧全局與局部搜索，鑒于此，學者進行了很多的研究，提出的辦法很多。灰狼優(yōu)化算法是一種新型群智能算法，本發(fā)明控制參數(shù)較少、收斂速度較快，等等，在尋優(yōu)能力上具有十分優(yōu)異的性能，所以在優(yōu)化問題中得到了廣泛的應(yīng)用。關(guān)鍵詞:車間調(diào)度；灰狼算法；動態(tài)權(quán)重引言優(yōu)化問題是指在某種約束條件下的問題，尋找最佳方案，使得給定對象達到最優(yōu)的問題類型。在社會各領(lǐng)域始終存在，內(nèi)容涉及交通規(guī)劃，工程設(shè)計，生產(chǎn)調(diào)度等、模型預(yù)測控制等等。優(yōu)化問題解決方法可以分為兩類：一類是傳統(tǒng)優(yōu)化方法，另一類是現(xiàn)代智能優(yōu)化。傳統(tǒng)的優(yōu)化方法，主要是指某些數(shù)學方法。這種方式一般都需要很高的題目，比如，要求問題可化為凸優(yōu)化問題，且此類方法多適用于計算復雜度較低的小規(guī)模組合優(yōu)化問題，否則，搜索最優(yōu)解的持續(xù)時間將成倍增加，造成了求解上的極大不便?，F(xiàn)代智能優(yōu)化的方法有進化算法，群智能算法。此類算法能迅速得到該問題的近優(yōu)解，且對問題本身沒有過多的約束，能較好解決那些用傳統(tǒng)優(yōu)化方法難以處理的難題，例如車間調(diào)度問題。這樣的問題是很大的，計算復雜度較高，對解的時間提出了要求，難以用傳統(tǒng)的優(yōu)化算法尋求全局最優(yōu)解。群智能算法的問世，為此類問題的解決提供了一種新途徑。近幾年受仿生學啟發(fā)，研究人員通過對自然界動物群體種群機制及多種社會行為的觀察，各種群智能算法的設(shè)計，例如，蟻群算法，粒子群算法等、飛蛾撲火算法等等。Mirjalili等于2014年模擬灰狼群體社會行為，提出一種灰狼優(yōu)化算法，本算法具有算法框架結(jié)構(gòu)簡潔，效率高、參數(shù)設(shè)置方便、全局與局部搜索能力相對平衡，且該算法收斂迅速，魯棒性強，精度較高，在求解交通規(guī)劃，圖像分割等問題中得到了廣泛的應(yīng)用、電力系統(tǒng)及其他方面的現(xiàn)實問題。但是與此同時灰狼優(yōu)化算法普遍存在算法簡單的問題、容易落入局部最優(yōu)的缺點，其主要原因在于，3個最優(yōu)個體對算法具有極強引導性，剩余普通個體對最優(yōu)個體依賴性過強所致。如果最優(yōu)個體能夠找到全局最優(yōu)解，那么剩下的個體就可以追隨最優(yōu)的個體向全局最優(yōu)收斂；但是如果最優(yōu)個體則會在迭代中陷入局部最優(yōu)，剩下的個體則很可能追隨最優(yōu)個體，落入局部最優(yōu)的泥潭，致使算法停滯不前，很難收斂于全局。鑒于這些缺陷，該文對經(jīng)典的灰狼算法進行了改進，最后，將改進算法應(yīng)用到柔性作業(yè)車間調(diào)度問題的求解中，同時為灰狼優(yōu)化算法求解實際調(diào)度問題提供一種新思路與計算模式。1、問題描述及模型1.1作業(yè)車間調(diào)度問題作業(yè)車間存在的問題可以用一個詞來形容，在一批次訂單中，有n種不同類型的工件要處理，記入{J1、J2、...、Jn}中；共m機，記入{M1、M2、...、Mm}；工件i過程可以用集合Oi來表示{Oi1、Oi2、...、Oij}；每道工序都能隨意選擇機器，同時又能達到加工要求，在實際加工車間里，因使用頻率較高、年限等因素不同時，在機器上在加工過程中功率及加工時間都不一樣，因此，本論文考慮使最大加工時間，機械負載達到最小、和以加工能耗作為研究對象的作業(yè)車間調(diào)度問題。1．2問題模型(1)條件假設(shè)①同一臺機器同一時刻只能加工一個工件;②同一工件的同一道工序在此時只能在一臺機器上加工;③任意工件的工序在加工開始后不能中止;④不同工件之間不存在先后順序;⑤同一工件的工序之間有加工先后關(guān)系，必須在前置工序完成后才能加工;⑥在零時刻所有工件都可開始加工。(2)數(shù)學模型構(gòu)建MinMakespan=MaxMakespann（1）MinTM=MinEdi=式（1）~（3）是目標函數(shù)，式（1）顯示，最小完工時間是根據(jù)最晚完工加工機器的相應(yīng)時間來確定；式（2）指示裝置的負荷，對于它全部機件加工時間總和；式（3）表示這批工件加工的能耗。對于上述目標函數(shù)，給出了本課題研究過程的約束條件：{F0?(3)參數(shù)定義相關(guān)參數(shù)以含義如表1所示。表1相關(guān)變量及含義變量含義變量含義n工件數(shù)量oj工件i的第j道工序m機器總數(shù)sj工序Оij的開始時間i,h工件號F;工序Оij的結(jié)束時間j,k工序號Makespan;工件i的完工時間z機器號Makespan最大完工時間T工序Оij，在機器zj工序Оij是否在機器z上上加工所花時間加工，是為1;否則為0P機器z的加工功率num;工件i的工序總數(shù)2、改進灰狼算法2.1灰狼算法簡介灰狼算法是由MIRJALILI等1提出的一種模擬灰狼的社會等級和狩獵行為的啟發(fā)式算法，它主要把灰狼群按適應(yīng)度的大小順序劃分為α和β、δ和ω等4種類型，并分別用α和β來表示、δ指導ω狼捕獵時尋找獵物，由此得到最優(yōu)解。D=CX(t)?XX(t+1)=Xp式中，A=2ar-a(7)C=2r2(8)式子t是迭代的次數(shù)：X（t）是灰狼目前所在的地方：X。對于獵物地點：A、C是單獨的協(xié)同系數(shù)；r,r2是一個隨機數(shù)，它在[0,1]之間：α的值隨迭代次數(shù)增加而線性遞減最后趨于0。打獵時，它在很大程度上取決于各個有領(lǐng)導能力α和β的大小、δ狼給出了一個引導，ω狼則是向獵物生存的地方尋找，然后對種群位置進行更新，它的數(shù)學模型是：{Da={X1=XaX(t+1)=X1+X2式子Xα,Xβ,Xδ、δ狼現(xiàn)在位置：Dα,Dβ、Dδ是剩余個體與α,β和δ狼之間的間距；X是灰狼目前所在的地方。2.2改進策略2.2.1編碼和解碼文中柔性作業(yè)車間數(shù)據(jù)是通過工序序列、處理機器序列、和處理時間序列的組成。首先抽取訂單的各個順序，采用以工序為單位對ROV進行升序編碼，按加工工序進行工序編碼生成，然后生成隨機數(shù)[0,1]，符合加工工序的編碼數(shù)量，按隨機數(shù)大小排列ROV升序，獲得初始化加工工序編碼如圖1。圖1工序的編碼方式工序編碼中反復出現(xiàn)的數(shù)字，表示工件的n個工序，利用所產(chǎn)生的加工機器矩陣及時間矩陣，可得到到達此工序的可選擇加工設(shè)備，以及在此裝置上加工的時間。表2首次顯示了該表首列工序編碼2，指示第二個工件的第一道工序，它的可選加工機器有機器3臺，機器5臺，相應(yīng)加工時間為5、4。表2工序的解碼方式工序編號21615OijO21O11O61O1num,O5mum,z3/51/5/61/543/6T5/44/6/21/125/52.2.2混合交叉的搜索策略針對傳統(tǒng)灰狼算法不能迅速收斂的問題，算法易陷入局部最優(yōu)解。提出一種混合交叉的搜索策略（mixed--crosssearchstrategy,MSS），介紹了遺傳算法混合交叉原理，從而提高了種群多樣性。這種策略能夠使整個空間被完全搜索到，同時，該算法后期能較快地收斂，避免落入局部最優(yōu)解。MSS策略以三個階段為重點進行了完善，在初始化種群階段、獵物搜索階段、和狼群更新階段。初始化種群：對給定搜索區(qū)域而言，對于灰狼種群，使用均勻分布初始化方式：Xij=(ui式子N是灰狼種群初始數(shù)量；X、（t）={x1、x2、x3...、x；}是迭代t次之后灰狼i所在的地方。同時當某一工序相應(yīng)于若干臺加工機器，本文引入一個選擇系數(shù)Q，隨機數(shù)超過Q的時候，隨機挑選本工序加工機器；否則，選擇當前流程加工時間最長的加工機器進行加工。獵物搜索階段：原始GW0算法搜索獵物時，下次迭代之后的確切位置是由α、β和δ狼所處的Xα、Xβ和Xδ來確定的，但只服從α和β、δ3只帶領(lǐng)狼指引尋找，在領(lǐng)導狼落入局部最優(yōu)解的時候，狼群卻陷入了局部最優(yōu)解。將遺傳算法混合交叉原理引入MSS策略，有效增強算法搜索能力，灰狼個體的搜索范圍表達式為：Di=[Xi?式子Xi（t）是灰狼當前位置坐標；Xi-cwo（t+1）是使用原始GW0算法算出的候選灰狼坐標。以公式（13）計算出來的值為半徑，將鄰域半徑內(nèi)狼群混合交叉，對鄰域內(nèi)狼群適應(yīng)度進行了再計算，適應(yīng)度最大者為候選地點，其坐標表示為Xi-Mss。狼群更新階段:通過對比傳統(tǒng)GWO算法生成的候選灰狼坐標Xi?GWO(t+1)以及采用MSS策略生成的灰狼坐標Xi(t+1)={Xi?cos算法每次迭代一次，均生成了傳統(tǒng)GW0和使用MSS策略進行甄別的候選灰狼，通過篩選出適應(yīng)度較好的個體，能較好地幫助群體尋找到較適合自己的候選灰狼，為了提高算法效果。2.2.3非線性參數(shù)策略在GW0算法中，當A>1，種群執(zhí)行全局搜索；當A<1，種群進行局部搜索。這說明參數(shù)a設(shè)置的好壞直接影響算法的搜索性能。傳統(tǒng)GWO算法的參數(shù)α隨著迭代的進行從2線性下降到0，不能適應(yīng)搜索過程繁雜，為此，該文提出非線性參數(shù)策略，此策略能較好地調(diào)節(jié)全局搜索與局部搜索，有效地維護種群多樣性。要能找出最好的功能如圖2，文中研究了非線性函數(shù)的求解問題，其目標是使加工的最大時間最小，種群大小定為100只，選取系數(shù)Q取0.6迭代50次，結(jié)果見圖3。圖2參數(shù)a變換過程圖3非線性函數(shù)對比圖經(jīng)比較得知，當前期設(shè)定參數(shù)α后，以使群體能夠在領(lǐng)導狼指導下，盡量全局搜索，α的獲得盡量大，以及算法搜索中，后期，以實現(xiàn)算法的迅速收斂，盡量讓α下降得快一些，最后，可以用下列函數(shù)來表達參數(shù)α:a=2-2×3。2.2.4動態(tài)權(quán)重搜索策略在常規(guī)GW0算法的設(shè)定下，候選者灰狼位置只受α狼作用，這種方法將使當α狼落入局部最優(yōu)解后，群體尋優(yōu)能力下降，使得算法搜索時收斂速度較慢，以確保早期狼群具有多樣性，文中給出了動態(tài)權(quán)重的搜索策略，在早期的搜索過程中，使狼群受到α,β,δ狼的綜合作用，加強種群的多樣性，提高搜索能力，避免陷入局部最優(yōu)：搜索后期增加α狼權(quán)重和減少β,δ狼權(quán)重，使算法能較快地收斂，它的表達式可以用這樣的方式表達：X(t+1)=q1X1+式中，參數(shù)之間的約束關(guān)系應(yīng)滿足：q1≥q2≥q3與搜索過程相伴的是種群內(nèi)α,β、δ狼權(quán)重從最初的[1?3、1?3、1?3]到算法迭代后期的[0.5,0.3,0.2]再到[1,0,0]，為了提高局部搜索的能力，使得算法收斂速度快。為此，在q1,q2,q3上分別設(shè)計非線性函數(shù)：q1=cosuq2={136en≤5013為了進一步限制函數(shù)的功能，文中介紹了角度與T在Gen由0變?yōu)镸ax_Gen的情況下，針對余弦函數(shù)，正弦函數(shù)等性質(zhì)，設(shè)計角度u,T等函數(shù)，確保文中參數(shù)變化范圍。u=4πarccos13綜上所述,給出灰狼中a、β、δ狼權(quán)重q1/q2/q3在迭代過程中的變化過程,如圖4所示。圖4權(quán)重系數(shù)的變化過程2.3pareto排序針對多目標優(yōu)化問題，通常采用加權(quán)處理，以pareto解表示，在過去學者們的大量研究工作中，利用與自身問題相結(jié)合的方法賦權(quán)，帶有主觀性且權(quán)重賦值不一致將給最終結(jié)果帶來較大差別，影響了最優(yōu)解精確獲得。因此，本論文使用pareto解集進行最大處理時間的計算、處理和裝置的負荷和能源消耗得到了優(yōu)化，通過外部存儲，將每一次迭代之后的解集進行保存，計算非支配解集，得到最優(yōu)解。2.4算法流程MSS-GWO算法主要過程見圖5。主要環(huán)節(jié)如下：第一步：設(shè)種群規(guī)模為N、選擇系數(shù)為Q、迭代次數(shù)為Max_Gen；第二步，用隨機系數(shù)Q來完成種群初始化，第三步：判斷迭代次數(shù)是否到達，有，跳到第八步，否則，計算所述初始化種群適應(yīng)度，按它們的適應(yīng)度大小排列，紀錄Pareto最優(yōu)解，將最佳3個個體分別依次分配到狼α,β和δ中：步驟四：對當前種群權(quán)重系數(shù)和其他參數(shù)進行更新：第五步：判斷其種群的大小，是則用灰狼算法得到它的候選狼，否則，調(diào)制第三步，第六步：基于候選狼算出一個新的鄰域，同時在鄰域中混合交叉?zhèn)€體，甄別新候選狼，第七步：將灰狼算法得到的候選狼和混合交叉候選狼進行比較，篩選適應(yīng)度較高之后的候選狼更新種群，更換外部解集；第八步，算法完成，得到最終解集。圖5算法流程圖3、實驗及結(jié)果分析為檢驗文中提出MSS策略效果，利用Python對文中所提算法進行了驗證，計算環(huán)境采用CPU:5600X和16G內(nèi)存，實驗驗證包括仿真數(shù)據(jù)的測試與比較和具體實例的Pareto解集分析兩個方面。3.1數(shù)據(jù)對比仿真測試的數(shù)據(jù)來源是MK01MK07實例，這里面包括不同的總數(shù)、各種加工機器的總數(shù)、不同工序數(shù)作業(yè)車間試驗數(shù)據(jù)在，多機因為使用年限的原因、種類不一等等原因，分別相應(yīng)于不同加工功率及空載功率見表3。從而利用實例，對文中所提MSS-GW0算法進行了比較、傳統(tǒng)GWO算法，和文獻[9]采用的FNSGA算法，對文中所提算法進行了可行性驗證。表3機器型號機器功率表功率M1M2M3M4M5M6M7M8M9M10加工功率Ppz2.0空載功率Pz0.4本文中算法的迭代次數(shù)為100，初始化種群數(shù)為200，隨機系數(shù)Q設(shè)置為0.6。比較情況見表4。表4算法對比表測試―

數(shù)據(jù)―工件和

工序數(shù)MSS-GwoGWoFNSGAMKO1(10,6)(42.0,149.0,369.7)(48.0,162.0,352.5)(50,383.5)MKO2(10,6)(35.0,147.0,313.2)(37.0,146.0,314.)(40,469.7)MK03(15,8)(197.0,918.0,2723.6)(203.0,967.0,2894.8)(262,3429)MKO4(15,8)(83.0,347.0,1072.6)(86.0,349.0,1071.1)(90,1103.7)MKO5(15,4)(188.0,682.0,1351.0)(187.0,697.0,1377.0)(197,1378.7)MKO6(10,15)(107.0,372.0,1284.4)(111.0,388.0,1295.5)(128,2074.5)MKO7(20,5)(147.0,641.0,1346.0)(170.0,635.0,1390.7)(196,1935.5)表（44.0,163.0,348.2）分別表示MK01算例在MSS-GW0算法中得到的最小處理時間為44，機械負荷為163，加工能耗為348.2，通過比較另外幾組算例的算法，得知，文中設(shè)計的MSS-GWO算法實現(xiàn)了最大加工時間，機械負載的最小化、和加工能耗比文獻所用FNSGA大大提高，同時，與雙目標優(yōu)化目標相比較，文中對三個目標作了優(yōu)化；與傳統(tǒng)的GW0算法相比，對實際車間加工過程中加工時間這個關(guān)鍵數(shù)據(jù)，算法維持較優(yōu)解的存在，實際加工生產(chǎn)過程中，車間效率能夠得到有效提升。3.2Pareto解集對比就Pareto解集而言，以MK02算例為例，比較了文獻中Pareto解集和文中所用MSS-GWO策略，畫出前沿對比圖；同時，比較了GWO算法在Pareto解集上的渲染，如圖6、圖7，由圖可知，同一算例之下，本論文設(shè)計出的策略在總體上維持著較好的表現(xiàn)，第一，得到的解集在數(shù)量上要多一些，多樣性得到維護；第二，算法搜尋中最優(yōu)解問題，總體因文獻解集而定；最后，在對實際加工和生產(chǎn)過程最小化最大加工時間方面都保持著很大的優(yōu)越性，由此，本論文設(shè)計算法具有較好搜索性能。圖6兩目標對比圖圖7多目標Pareto解集對比圖圖8MK02算例調(diào)度方案4、結(jié)束語針對車間的柔性調(diào)度，文中由考慮車間使最大加工時間，機械負載最小化、并從加工能耗等主要指標入手，構(gòu)造了優(yōu)化目標數(shù)學模型。同時，給出混合交叉原理下MSS-GWO調(diào)度策略，同時，為使該算法能得到較好的Pareto解集合，開展非線性函數(shù)設(shè)計研究，最后，在車間普通MK系列數(shù)據(jù)集上驗證算法，實驗證明，文中所提混合交叉原理MSS-GW0策略能很好地解決車間多目標優(yōu)化。后續(xù)的研究仍會緊緊圍繞車間調(diào)度這一問題展開，吸收了其他算法的長處，開展車間動態(tài)調(diào)度問題研究，使車間調(diào)度問題得到較好求解。參考文獻[1]孫新宇.改進灰狼算法求解多目標柔性作業(yè)車間調(diào)度問題[J].軟件工程,2022,25(11):15-18+14.DOI:10.19644/ki.issn2096-1472.2022.011.004.[2]王玉芳,曾亞志,蔣亞飛.基于自適應(yīng)灰狼優(yōu)化算法的柔性作業(yè)車間調(diào)度問題[J].現(xiàn)代制造工程,2022(07):1-10.DOI:10.16731/ki.1671-3133.2022.07.001.[3]張其文,王超.一種求解柔性作業(yè)車間調(diào)度問題的改進灰狼優(yōu)化算法[J].蘭州理工大學學報,2022,48(03):103-109.[4]劉微,蘭圖,孫梓華,楊碩,馬騰飛.混合狼群算法在動態(tài)車間調(diào)度中的應(yīng)用[J].吉林師范大學學報(自然科學版),2021,42(04):66-73.DOI:10.16862/ki.issn1674-3