求解流水車間設備維護調度問題的量子遺傳混合算法應用研究綜述目錄TOC\o"1-3"\h\u24895求解流水車間設備維護調度問題的量子遺傳混合算法應用研究綜述 1230701.1混合算法流程設計 137091.2量子遺傳混合算法關鍵技術處理 284781.3混合算法中禁忌搜索算法的技術處理 4296821.4混合算法中的數據處理 4198401.4.1預防性設備維護調度中編碼過程 4133471.4.2預防性設備維護調度中解碼方式 5107561.4.3適應度函數 6327591.5量子遺傳混合算法實驗及結果 6308571.5.1算法性能試驗 6317431.5.2生產應用試驗 81.1混合算法流程設計本章節的設計初衷是為了在整個算法運行過程中量子遺傳算法可以在全局搜索中展現出其較強的優勢并且能夠快速得出相應的優質解，而禁忌搜索算法在上述算法過程中無法觸及的局部搜索里將一些陷入局部最優的解重新進行生成計算，從而更好的將一些被淘汰的解重新利用。如下圖1.1為整個混合算法的流程圖，如圖可知上半部分為與下半部分的搜索是逐步進行的。圖1.1量子遺傳混合算法流程圖算法開始之前要對整個種群開始初始化得到一個種群合集Q(t0)，其中包含的基因表達式為，種群基因開始時都為，依次相加之和的表達式為：（1.1）Sk是一個長度包含k種情況的二進制串（x1，x2…xm）下一步進行種群的測量以獲得滿足該式的解，的含義是產生的代子群里面第個的解，其表達方式是一個長度為的字符串。在整個循環開始穩步運行之后，種群就逐漸向著優質解開始收斂。在此過程中需要注意的是，當產生一個優質解的時候一定要與前面產生的目標值相互對比，如果優質解小于目標值，則當前值不發生改變，反之將優質解記錄保存為下次循環中的目標值。1.2量子遺傳混合算法關鍵技術處理（1）量子位編碼編碼的操作方式是先隨機選取一段量子位染色體，其表達式可以由這樣子的一對復數構成；量子態可用表示，在此過程中復數滿足這樣的條件，以此類推，當一段有m長度的染色體其表達式可以由此推出即：，且該式滿足，在這種新的編碼方式中單個量子位既能夠表示一個量子位也能表示多個，該編碼方式可以有效將染色體數量優化，去除一些劣質的染色體，并且不會影響到整個種群的總體狀態。其次該編碼方案可以獲得較好的收斂性。（2）量子旋轉門量子旋轉門的提出是因為在種群進化的過程中，部分染色體會發生一些相互影響的現象造成染色體的部分失效，因此為避免該現象在整個操作過程中出現，使用了量子旋轉門來改變部分染色體的相位導致幅值[47]發生變化，即：（1.2）量子位更新方式如下式1.3所示：（1.3）其中，為第個量子位，為旋轉角。（3）測量染色體在對所有的種群個體進行染色體的測量獲取對應的解。測量方法是在一個區間范圍中隨機生成一個數值，若數值大于θ結果為0，反之為1.（4）計算適應度在設置適應度函數時，設置的適應度函數與目標函數之間存在反比的關系。然后在染色體的解碼時，染色體要符合相應規定的限制條件，在此基礎上記錄染色體計算其對應的適應度值，從而將調度方案予以確定。（5）終止策略在整個算法運行過程中，將迭代次數設置為停止算法運行過程的主要條件，即當算法運行至規定的次數時終止算法，并將算法所求得的有效解進行表達。在此過程中如若出現有效解提前達到所提供的閾值時，算法過程可以提前結束。1.3混合算法中禁忌搜索算法的技術處理混合算法中禁忌算法的主要的控制參數有迭代次數且禁忌表長度已知。1.初始解此處的初始解是混合量子遺傳算法經過求解運算之后產生的優質解。2.通過鄰域函數生成候選解候選解的產生方法是在一個隨機過程中產生一個參數使這個參數比固定值大，則此時所產生的編碼會以正函數比例放大，反之就會縮小，利用這個原理多次的循環產生多個解作為備選。3.藐視準則在第2步驟中得到的備選解與第1步產生的初始解對比，如果備選解比初始解優異，那將該解進行記錄并作為新的初始解，反之則在備選解中挑選3個優質解中的1個作為新的初始解并記錄。如此循環該過程，當整個循環快結束時停止該操作，反之就繼續進行以上所提的循環操作。1.4混合算法中的數據處理1.4.1預防性設備維護調度中編碼過程利用算法將調度問題進行解決優化最為關鍵的是在算法的實現過程中所使用的染色體可以完美的表達出解決問題所包含的優異解[48]。在這個過程中良好的染色體編碼以及解碼就顯得尤為重要，這樣子的目的是將車間調度問題所包含的解的范圍與染色體有效的結合建立逐一對應的關系。在這個過程中，第一步是要將問題中所對應的染色體進行編碼，編碼之后會產生優解，對上述產生的解再進行解碼之后就能求出符合實際需要的優質解[49]。因此，本章節所采用的解碼過程如下所示：本章節利用文獻[40]提出的編碼解碼方案方案，采用5層編碼方式，其中前三位編碼屬于自然選擇，后兩位則進行2進制方式編碼，方式如下：X=[i，j，k，p，c]（1.4）式中i零件順序，j工藝順序，k可用機械設備，p此時存在預防維護，c機器停機概率。實例4×4如表1.1：表1.14×4問題的加工工時及設備選擇工件工序可選設備及加工時間(h)M1M2M3M4113421223042111002210333320311202212334121002032135424如圖1.2所排布的染色體的表達，在第3行中（4,3,1,1,0）表示，零件4在進行第3項工藝路線是在設備1上，此時設備處于停機保養狀態，機器沒有出現任何失效狀態。圖1.24×4染色體表達1.4.2預防性設備維護調度中解碼方式本章節的解碼方法是[29]：依據前3個自然選擇出的編碼序列確定所對應的機器以及工藝路線；將所有工件按照加工能力現狀進行分批并且對分批后的零件編號排序；按照最后一個基因插入與之時間長度對應的序列；實時準備故障出現時候的工作狀態；更新機器的使用現狀，重新返回步驟（1）。在整個解碼過程中還是需要滿足上述章節（3-11）至（3-17）提到的相關約束條件，只有在滿足這個的基礎上生成的解才是能被作為有效解進行運算的，反之將會被作為無效解予以淘汰。1.4.3適應度函數適應度函數是將目標函數進行變化得出適應度函數，即目標函數與適應度函數存在反比的關系，當適應度函數的值是最大時，此時此刻目標函數的值即為最小值也是我們所需要的最優解，具體的函數表達式如下所示：（1.5）其中等式左側為標記基因i的適應度，右側則是（3-4）所表達的函數式。1.5量子遺傳混合算法實驗及結果1.5.1算法性能試驗本章節選用表1.2所列舉的函數進行仿真實驗的比較分析。遺傳算法的參數分別為：種群體量、變異概率、交叉概率、災變概率以及最大迭代次數分別為20、0.01、0.8、0.3、100。為對實驗結果進行有效對比，混合遺傳算法參數為：種群規模、迭代次數、分別為20、100，旋轉角策略（1.2）所述。量子遺傳混合算法參數設置為：種群規模、迭代次數、分別為20、100，旋轉角策略（1.2）與（1.3）所述。圖1.3Sphere函數收斂曲線對比圖1.4Rastrigin函數收斂曲線對比圖1.5Schaffer函數收斂曲線對比測試函數數據如下表所示：表1.2測試對比測試函數函數表達式算法最小值止步代數SphereQGA-TSGA-TS0.04550.74862523GA0.385735Rastrigin’sQGA-TSGA-TS1.18751.19237543GA2.510554SchafferQGA-TSGA-TS0.00000.000085GA0.00185本章節中的種群規模設置為20，由表1.2結果顯示，本章節所提出的混合量子遺傳算法無論是在求得的最小值，還是到迭代所運行的止步代數都會比其他算法優異一些。在上百次的運行迭代后，混合量子遺傳算法與混合遺傳算法都已經收斂停止。在研究過程中發現，混合量子遺傳算法的迭代次數可以設置在40至100之間，此時算法正常運行，也不會導致由于算法收斂速度過快產生的算法終止。在這幾種算法中，最優解最大的是遺傳算法，因此無法得到最好的效果，屬于提前終止收斂。因此在比較上述的三種算法的基礎上得知，量子遺傳算法能夠更好的得出優質解。對于本文所要解決的車間調度問題，混合的量子遺傳算法能夠更好的顯示出其優秀可行性。在此過程中，存在的算法耗時問題，對于整個車間調度而言，調度時間是一個比較龐大的時間范圍，而且還要考慮一定的經濟性，所以本算法綜合而言還是能夠有效解決車間設備預防維護的調度問題，對于一些存在的耗時可以忽略不計，不影響全局的整個調度計劃。1.5.2生產應用試驗生產實例是對武漢市人天包裝機械有限公司的實際調研發現，該廠機械加工小組加工任務中存在5種不同類型的工件，當前訂單下需要的設備為：1臺臥式車床，1臺立式車床，1臺數控銑床，2臺數控鏜床，1臺鉆床，1臺加工中心。表1.3設備及加工能力設備編號設備類型加工能力M1立式車床粗車M2臥式車床粗車、精車M3數控銑床粗銑、精銑、M4加工中心精車、精銑、鉆M5數控鏜床高精度孔加工M6數控鏜床高精度孔加工M7鉆床孔加工對于此次訂單中所涉及的相關產品加工的細則如下表1.4所示。表1.4設備加工時間工件種類批量工序可選機器和加工時間（h）M1M2M3M4M5M6M712211.4223.4002.32.483.5200001.32.122.2531.281.37002.82.783.1941.311.39002.82.642.665001.361.41.41.212.3822511.671.490001.253.5223.262.80001.113.823003.523.53.83.741.15400003.10032712.712.650003.41.062002.452.52.93.723.8131.931.270005.031.6643.813.230001.61511.791.8321.591.850002.12.383001.331.30005331002.882.93.102.2422.663.020003.172.9833.193.20002.813.19生產計劃部將該訂單生產計劃批次分為如下表1.5所示：表1.5工件數量工件種類工件批量批次數量子批編碼子批數量1222111211225436465667327379899943031010111012105333131114111511以下是通過對武漢人天包裝機械有限公司的調研可知的數據，其中7臺設備的故障、維護以及產生的費用等相關數據如下：表1.6設備時間參數表設備編號未進行預防維護的情況預防性維護情況故障間隔（h）故障報修用時（h）維護間隔（h）預防性維護時間（h）故障間隔（h）故障維護時間（h）M153.53.6350.596.43.6M251.22.04280.47942.04M362.63.2420.55107.13.2M4603.2420.55105.53.2M568.32.48350.6133.22.48M675.53.76380.7595.83.76M755.45.2300.478.45.2表1.7設備費用明細M1M2M3M4M5M6M7加工費用（元/h）4545120120606050預防維護費用（元/h）240240780780180180350故障維修費用（元/h）86086026802680155015502300表1.8設備維修記錄冊日期設備編號維護時間維護時長（分鐘）故障分析解決對策平均維護間隔（分鐘）備注2020/8/3M18:2728溫度過高加冷卻液352020/8/3M29:1612刀具損壞更換刀具222020/8/3M29:3023導軌偏移修正導軌142020/8/3M410:726主軸磨損更換主軸312020/8/3M511:219膠圈老化更換膠圈26……以上表1.3~表1.8均在武漢人天包裝機械有限公司實際測得。本次加工計劃利用Weibull分布[42]描述設備所產生的故障頻率。其中相關參數如表1.9可的：表1.9設備故障間隔的服從威爾發布的參數設備編號尺度參數形狀參數M1141.421.88M2101.022M3972.73M491.211.86M589.82M689.82M791.31.91設備M1至M7的Weibull分布擬合圖依次如圖1.6：圖1.6設備威爾分布擬合圖圖1.7為該生產計劃，在未進行預防性維護的甘特圖。整個加工過程中最大加工用時238.45小時，出現21次故障，設備故障所維修總用時高達69.84小時。圖1.7未預防維護設備的甘特圖圖1.8是采用用第3章節中混合遺傳算法進行預防性維護后的調度方案所產生的加工甘特圖。最大用時223.65小時，機器進行30次預防保養，耗時16.3小時，出現15次設備故障，維修總用時48.84小時。圖1.8基于混合遺傳算法的甘特圖圖1.9是該生產計劃使用量子遺傳混合算法進行預防性維護后的調度方案所產生的加工及故障甘特圖。在該過程中最大加工用時191.5小時，設備進行了26次預防性維護，耗時13.93小時，出現12次設備故障，由于設備故障所進行的維護總用時39.56小時。圖1.9基于量子遺傳混合算法的甘特圖表1.10加工時間和費用詳情M1M2M3M4M5M6M7未進行預防性維護加工時長（h）236.71238.45201.62201.57163.25183.2180.62維修時長（h）11.48.169.69.61.967.5215.6總維修費（元）126833.6總加工費（元）99943合計（元）226776.6GA-TS算法加工