基于混合整数规划的装配间隙决策优化方法

吴亚龙，常文兵，徐振中，钱思霖

(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