吳亞龍，常文兵，徐振中，錢(qián)思霖

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

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

吳亞龍1，常文兵2，徐振中2，錢(qián)思霖2

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

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

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

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

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

1 理論與定義

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

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

1.2 粗糙集

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

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

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

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

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

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

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

其次，介紹該模型中的各個(gè)變量。

w_cij：取值為0或1，對(duì)于論域I中任意兩個(gè)樣本點(diǎn)i和j若w_cij，則i和j可以在同一個(gè)由條件屬性集劃分的近似等價(jià)類(lèi)中，反之，i和j無(wú)法被劃分到同一個(gè)條件屬性集的近似等價(jià)類(lèi)中；

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

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

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

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

w_dij,sld’,qik’,ssijd’,Qk’和上面類(lèi)似，不過(guò)是對(duì)于決策屬性集。

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

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

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

Lkk：取值為0或1，若Lkk=1，則kc中的近似等價(jià)類(lèi)k是kd中的近似等價(jià)類(lèi)k’的下近似集；

Yk：若kc中的近似等價(jià)類(lèi)k是下近似集，則Yk為下近似集k中樣本點(diǎn)的個(gè)數(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;

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

2 實(shí)例分析

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

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

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

2.2 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

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