基于混合整數(shù)規(guī)劃的裝配間隙決策優(yōu)化方法

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

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

基于混合整數(shù)規(guī)劃的裝配間隙決策優(yōu)化方法

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

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

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

混合整數(shù)線性規(guī)劃；裝配間隙參數(shù)；數(shù)據(jù)預(yù)處理

柴油發(fā)動機(jī)的裝配是影響柴油機(jī)質(zhì)量的關(guān)鍵性因素，傳統(tǒng)研究只是從機(jī)械原理對柴油機(jī)的裝配間隙進(jìn)行優(yōu)化研究。熊小龍等[1]應(yīng)用Topsis方法，為柴油機(jī)裝配質(zhì)量的評估提供了定量分析的方法，并通過算例實驗驗證該評價方法的有效性和可行性，隨著數(shù)據(jù)挖掘算法的發(fā)展和柴油機(jī)制造等數(shù)據(jù)的大量積累，使得利用數(shù)據(jù)挖掘建立起裝配間隙參數(shù)和整機(jī)質(zhì)量等級之間的關(guān)系成為了可能。數(shù)據(jù)挖掘技術(shù)是從大量的并且結(jié)構(gòu)復(fù)雜的數(shù)據(jù)中發(fā)現(xiàn)隱含的、有價值并最終演變?yōu)槟鼙蝗死斫獾闹R的過程[2]。

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

1 理論與定義

1.1 數(shù)據(jù)預(yù)處理

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

1.2 粗糙集

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

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

1.3 基于混合整數(shù)規(guī)劃的粗糙集模型

本文中克服粗糙集模型對于噪聲數(shù)據(jù)抵抗能力弱的方法是將粗糙集模型與對噪聲數(shù)據(jù)抵抗能力較強的線性規(guī)劃模型相結(jié)合。Zhang等提出了一種基于粗糙集的多目標(biāo)線性規(guī)劃方法來解決數(shù)據(jù)挖掘領(lǐng)域的分類問題。Chen等在Zhang的研究的基礎(chǔ)上對其提出的模型進(jìn)行了改進(jìn)，并應(yīng)用改進(jìn)的基于粗糙集的多目標(biāo)線性規(guī)劃模型對蛋白質(zhì)相互作用的熱點進(jìn)行了預(yù)測。建立基于混合整數(shù)規(guī)劃的粗糙集優(yōu)化模型，以往被認(rèn)為非線性的粗糙集模型，在本文中首次以線性模型進(jìn)行描述，也是本文的一個創(chuàng)新點。

基于混合整數(shù)規(guī)劃的粗糙集模型是利用混合整數(shù)規(guī)劃實現(xiàn)粗糙集中屬性集對于論域的劃分過程，目的是提高基于粗糙集的決策系統(tǒng)精度，在該模型中設(shè)置最大化確定區(qū)域中的樣本數(shù)目作為規(guī)劃模型的目標(biāo)函數(shù)，模型的屬性集中屬性的篩選過程和屬性集對論域的劃分過程均以目標(biāo)函數(shù)最大化為目的。

第一步：定義模型的集合和參數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

第二步：建立(MILP)數(shù)學(xué)規(guī)劃模型。

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;

第三步：計算該模型的決策系統(tǒng)精度。

2 實例分析

2.1 數(shù)據(jù)預(yù)處理

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

表1 數(shù)據(jù)集

2.2 實驗分析

在實證研究中，該模型時在AMPL/CPLEX軟件中實現(xiàn)并進(jìn)行求解的，在實現(xiàn)過程中還需要對模型的若干參數(shù)值進(jìn)行設(shè)定：

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

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

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

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

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

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

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

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

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

基于K均值聚類方法被提出建立數(shù)學(xué)模型研究裝配間隙參數(shù)與柴油機(jī)整機(jī)質(zhì)量等級之間的關(guān)系，表3顯示了兩種數(shù)學(xué)模型的決策系統(tǒng)精度。

表3 模型對比結(jié)果表

3 結(jié)論

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

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

[2] 劉業(yè)政.基于粗糙集數(shù)據(jù)分析的智能決策支持系統(tǒng)研究[D].合肥：合肥工業(yè)大學(xué)，2002.

[3] 郭春花.基于鄰域粗糙集和距離判別的信用風(fēng)險評級[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，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