基于混合整數規劃的裝配間隙決策優化方法

吳亞龍，常文兵，徐振中，錢思霖

(1.河南柴油機重工有限責任公司，洛陽 471000； 2.北京航空航天大學可靠性與系統工程學院，北京 100000)

基于混合整數規劃的裝配間隙決策優化方法

吳亞龍1，常文兵2，徐振中2，錢思霖2

(1.河南柴油機重工有限責任公司，洛陽 471000； 2.北京航空航天大學可靠性與系統工程學院，北京 100000)

為建立基于粗糙集的混合整數規劃模型，研究柴油發動機裝配間隙參數和整機質量等級之間的關系。首先數據預處理采用多重插補并進行相關性分析，運行主成分分析法進行處理。其次建立基于粗糙集的混合整數規劃模型，最后與基于粗糙集的K均值聚類分析方法比較，得出基于粗糙集的混合整數規劃模型的決策系統精度更高。

混合整數線性規劃；裝配間隙參數；數據預處理

柴油發動機的裝配是影響柴油機質量的關鍵性因素，傳統研究只是從機械原理對柴油機的裝配間隙進行優化研究。熊小龍等[1]應用Topsis方法，為柴油機裝配質量的評估提供了定量分析的方法，并通過算例實驗驗證該評價方法的有效性和可行性，隨著數據挖掘算法的發展和柴油機制造等數據的大量積累，使得利用數據挖掘建立起裝配間隙參數和整機質量等級之間的關系成為了可能。數據挖掘技術是從大量的并且結構復雜的數據中發現隱含的、有價值并最終演變為能被人理解的知識的過程[2]。

粗糙集是用來刻畫不完整性和不確定性之間的數學工具，并通過對于上近似和下近似給定一個可變精度來尋求數據之間的關系。國內學者郭春花[3]等擴展了粗糙集理論的應用范圍，但是粗糙集對于數據集中噪聲信息和錯誤信息較敏感，因此本文將對噪聲數據抵抗能力較強的線性規劃模型相結合，建立基于粗糙集的混合整數規劃模型，經實驗分析，該模型具有較高的精度。本文首次以線性模型對粗糙集概念和理論進行描述，是對于粗糙集理論的進一步發展。

1 理論與定義

1.1 數據預處理

數據主要包括：柴油機裝配間隙參數數據和柴油機整機質量等級數據，其中裝配間隙參數數據主要包括主軸孔曲軸和主軸承座孔的配合間隙參數、齒輪孔和軸承的配合間隙參數等，對于樣本數據的缺失值，本文采取多重插補的方法，并對數據相關性分析，數據集中屬性之間的強相關性會影響數據挖掘模型的效果和效率，因此根據主成分分析法對數據進行降維處理。

1.2 粗糙集

粗糙集理論是由波蘭學者在1982年提出，它是一種刻畫不完整性和不確定性的數學工具。粗糙集理論的核心思想是對于不確定數據進行推理或是通過對于上近似和下近似給定一個可變精度來尋找數據之間的關系。

在信息系統IS= (I, A)中，其中I為論域，A為屬性集，I和A均為非空有限集合。當該系統滿足條件：A=C∪D和C∪D≠?. 時，稱這樣的信息系統為決策系統：其中DS=( I,C∪D)，C為條件屬性集，D為決策屬性集。

1.3 基于混合整數規劃的粗糙集模型

本文中克服粗糙集模型對于噪聲數據抵抗能力弱的方法是將粗糙集模型與對噪聲數據抵抗能力較強的線性規劃模型相結合。Zhang等提出了一種基于粗糙集的多目標線性規劃方法來解決數據挖掘領域的分類問題。Chen等在Zhang的研究的基礎上對其提出的模型進行了改進，并應用改進的基于粗糙集的多目標線性規劃模型對蛋白質相互作用的熱點進行了預測。建立基于混合整數規劃的粗糙集優化模型，以往被認為非線性的粗糙集模型，在本文中首次以線性模型進行描述，也是本文的一個創新點。

基于混合整數規劃的粗糙集模型是利用混合整數規劃實現粗糙集中屬性集對于論域的劃分過程，目的是提高基于粗糙集的決策系統精度，在該模型中設置最大化確定區域中的樣本數目作為規劃模型的目標函數，模型的屬性集中屬性的篩選過程和屬性集對論域的劃分過程均以目標函數最大化為目的。

第一步：定義模型的集合和參數。

I：由樣本組成的論域；kc：根據條件屬性集對論域進行劃分的近似等價類的集合；kd：根據決策屬性集合對論域進行劃分的近似等價類的集合；C：條件屬性集；D：決策屬性集；N：條件屬性集的最小支持數；β：可變精度；ac：條件屬性集的相似度閾值；ad：決策屬性集的相似度閾值；M：任意大數；Xci：各個樣本在各條件屬性下的取值；Xdi：各個樣本在各決策屬性下的取值。

其次，介紹該模型中的各個變量。

w_cij：取值為0或1，對于論域I中任意兩個樣本點i和j若w_cij，則i和j可以在同一個由條件屬性集劃分的近似等價類中，反之，i和j無法被劃分到同一個條件屬性集的近似等價類中；

slc：取值為0或1，對于條件屬性集中的屬性c若slc=1,則該屬性c被選擇為新的條件屬性參與對論域的劃分，否則屬性c選擇與否對決策規則的建立影響很小，從條件屬性集中被剔除；

qik：取值為0或1，對于論域I中的任意樣本點i和由條件屬性集對論域進行劃分得到的近似等價類集合kc中的任意一個近似等價類k，若qik=1樣本點i在近似等價類k中，反之，樣本點i不屬于近似等價類k；

ssijc：取值為0或1，對于論域I中的任意兩個樣本點i和j，以及條件屬性集中的任意屬性c，若ssijc=1，則樣本點i和j在屬性c上的取值滿足對應的相似度閾值ac；

Q：由條件屬性集對論域進行劃分得到的近似等價類k中的樣本點的個數；

w_dij,sld’,qik’,ssijd’,Qk’和上面類似，不過是對于決策屬性集。

eikk’：取值為0或1，對于論域I中的任意樣本點i和條件屬性集的近似等價類k以及決策屬性集的近似等價類k’，若eikk=1，則樣本點i既屬于條件屬性集的近似等價類k又屬于決策屬性集的近似等價類k’；

Ekk’：既屬于條件屬性集的近似等價類k又屬于決策屬性集的近似等價類k’的樣本個數；

fk：取值為0或1，若fk =1，則條件屬性集的近似等價類k中的樣本點個數滿足最小支持度閾值，近似等價類k可以成為下近似集，反之，近似等價類k不滿足成為下近似集的條件；

Lkk：取值為0或1，若Lkk=1，則kc中的近似等價類k是kd中的近似等價類k’的下近似集；

Yk：若kc中的近似等價類k是下近似集，則Yk為下近似集k中樣本點的個數。

第二步：建立(MILP)數學規劃模型。

Subject to：

w_cij≤ssijc+(1-slc),i∈I,j∈I,c∈C;ssijc≥1-slc,i∈I,j∈I,c∈C;

N×fk≤N+(Qk-N);card(I)×Lkk′≤card(I)+(Ekk′-Qk×β),k∈kc,k′∈kd;Lkk′≤fk,k∈kc,k′∈kd;

第三步：計算該模型的決策系統精度。

2 實例分析

2.1 數據預處理

本文原始數據是16缸柴油機樣本集，其中共包含29臺柴油機樣本，對于原始數據進行缺失值處理和通過相關性分析基于主成分分析的降維處理后得到15個主成分，并將降維后的柴油機裝配間隙參數數據集和柴油機整機質量等級數據集進行集成，得到直接應用到后續挖掘模型的最終數據集。

表1 數據集

2.2 實驗分析

在實證研究中，該模型時在AMPL/CPLEX軟件中實現并進行求解的，在實現過程中還需要對模型的若干參數值進行設定：

第一，下近似集合的最小支持數N=3。第二，可變精度β=0.9。第三，任意大數M=999。第四，條件屬性集對柴油機數據集劃分的初始條件q11=1。第五，由條件屬性集的相似度閾值組成的列表：ac=[0.0495,0.0369,…,0.099]其中c=15表示經降維處理后的柴油機裝配間隙參數數據集的主成分的個數。第六，設置條件屬性集劃分論域的近似等價類的個數k=10。

該模型的輸入為經過降維處理后的柴油機裝配間隙參數數據集的主成分數據，柴油機的整機質量等級數據以介紹的預先設定的參數。模型的輸出包括：模型對輸入的各主成分的篩選結果、根據條件屬性集對論域的劃分結果、下近似集的求解結果和確定區域中柴油機樣本個數的計算結果等。

由經過降維處理的柴油機裝配間隙參數組成的條件屬性集共包含15個主成分屬性，基于混合整數線性規劃和粗糙集的柴油機裝配間隙參數決策模型可以實現對屬性集中屬性的進一步篩選，以剔除那些對決策系統精度影響不大的屬性，其篩選結果由變量slc表示，本案例中模型對條件屬性集中屬性的篩選結果為：

表2 模型對條件屬性集中屬性的篩選結果

若對應屬性c的sl值為1則該屬性被選擇，反之，若對應屬性c的sl值為0，則證明該屬性在設定的相似度閾值下對整個決策系統的精度影響是可以忽略的，可以將該屬性剔除以進一步簡化屬性集。上述結果表示，本實證研究案例中的15個柴油機裝配間隙參數的主成分均被選擇。

條件屬性集對論域的劃分結果的求解是整個決策模型計算過程中的重要一步，同時也是后續柴油機裝配間隙參數組合優選過程實現的先決條件，本實證研究案例中條件屬性集對論域的劃分結果由sc矩陣來表示，其結果為：

在本實證研究案例中，sc矩陣為一個20*10的矩陣，29代表原始數據集中的29臺某廠某型號的16缸柴油機樣本，10代表模型預先設定的10個近似等價類，若某一臺柴油機樣本在某一個預先設定的近似等價類中，則矩陣中元素的取值為1，否則為0。

該結果代表根據條件屬性集對論域劃分的每一個近似等價類中柴油機樣本的個數，模型中預設的近似等價類的個數為10個，但其中有一個近似等價類中未被分配任何樣本，并且有一個近似等價類中的樣本個數未達到預先設定的最小支持數，所以可以作為下近似集的只有8個。

本實證研究案例中E矩陣為一個10*3矩陣，其中10行代表模型預先設定的由條件屬性集劃分論域的近似等價類的個數，3列代表決策屬性集對論域劃分的等價類的個數。

基于K均值聚類方法被提出建立數學模型研究裝配間隙參數與柴油機整機質量等級之間的關系，表3顯示了兩種數學模型的決策系統精度。

表3 模型對比結果表

3 結論

裝配間隙參數和柴油機整機質量等級之間的關系可以通過數據挖掘的方法得以實現，本文通過建立基于粗糙集的混合整數線性規劃模型來尋求裝配間隙參數和整機裝配質量等級之間的關系，粗糙集在應用上最大的限制就是對于噪聲數據的敏感，混合整數線性規劃可以很好地克服該點，并且相比基于粗糙集的K均值聚類算法，基于粗糙集的混合整數線性規劃具有更高的精度。該模型可以對柴油機的裝配具有一定的指導意義。

[1] 熊小龍，王建國，馮洲鵬. 柴油機裝配質量評估的TOPSIS方法[J]. 柴油機，2014，(03)：124-125.

[2] 劉業政.基于粗糙集數據分析的智能決策支持系統研究[D].合肥：合肥工業大學，2002.

[3] 郭春花.基于鄰域粗糙集和距離判別的信用風險評級[J].重慶理工大學學報(自然科學)，2013，(02)：79-80.

Optimization method of assembly gap decision based on mixed integer programming

WU Ya-long1, CHANG Wen-bing2, XU Zhen-zhong2, QIAN Si-lin2

(1.Henan Diesel Heavy Industries Co., Ltd., Luoyang 471000, China; 2.School of Reliability and Systems Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100000, China)

In order to establish a hybrid integer programming model based on rough set, the relationship between the assembly gap of diesel engine and the quality of the whole machine is studied. First, the data preprocessing adopts multiple interpolation and correlation analysis, and the principal component analysis method is used to deal with it. Secondly, a hybrid integer programming model based on rough set is established. Finally, compared with the K-means clustering analysis method based on rough set, the decision system of mixed integer programming model based on rough set is higher.

Mixed integer linear programming; Assembly gap parameter; Data preprocessing

2017-04-29

TP18

A

1674-8646(2017)14-0174-03