基于改进遗传算法的计算机数学模型构建研究

何庆　钟维坚　田风　林锋　唐苏东

【摘要】    面向网络计算机中海量的数据信息，采取传统匹配搜索遗传算法进行匹配点、非匹配点的遍历，通常遍历到无效度更高的非匹配点较多，很难在短时间内找到与样本相近的最佳匹配点。基于此，针对基本遗传算法的无效遍历、数据冗余弊端，结合最小二乘法、Bagging集成聚类算法对原有遗传算法作出改进，建立起相似度匹配的计算机数学模型，确定高精度因子匹配的参数估算范围和辨识度，改进遗传算法关联矩阵编码、解码、交叉等集成学习与迭代环节，以扩展样本匹配的搜索空间与深度。

【关键词】    改进遗传算法    计算机    数学模型    构建

引言：

在企业工业化生产、计算机视觉处理数据匹配中，通常需要根据视觉数据因子、工作站的数量，设置n个样本数据为初始聚类中心，对多个相似对象进行最小误差求解，将不同对象分配至距离其最近的聚类中心，来完成算法最优解的搜索与匹配。因而面对传统遗传算法具有的无效遍历更多、搜索深度不足等特征，本文提出基于Bagging集成聚类的改进遗传算法，建立起企业装配线的计算机平衡优化数学模型，将双目装配线中的生产作业要素因子，合理分配到相应的工作站之中，进行种群聚类分析的编码、适应度计算，得到每个个体的搜索与聚类结果。

一、传统遗传算法的编码、数据搜索与交叉操作执行流程

傳统遗传算法为美国密歇根大学J.  H.Holland教授，根据达尔文“自然选择理论”提出的自适应数据信息搜索/优化技术，其初始群体编码是由二进制“0”和“1”字符组成的一连串字符串，将具有类似特征的字符串组合为特定子集，并利用随机搜索技术对多个字符串组成集合，进行交叉、变异等的迭代遗传操作，来确定全局最优解。

因而该遗传算法主要是对编码后的控制参数，作出编码串模式阶次的群体矢量搜索。在完成某一空间数据参量的编码后，先对群体P（t）展开选择、交叉、变异等遗传算法运算，再根据所求问题的目标函数（适应度函数），进行编码字符串集群中个体的适应度评估，得到下一代群体P（t+1）。传统遗传算法的编码、数据搜索与交叉操作的简单执行流程如下所示。

开始程序;

t←0;

初始化种群P（t） 编码;

评价种群P（t）编码;

如果不符合终止条件，则开始循环;

T←t+1;

从上一代种群P（t-1）中选择个体，形成新的群体P（t）;

种群P（T）通过交叉和变异进化;

种群P（T）的适应度计算;

评价组P（T）;

周期结束;

程序执行结束。

二、基于Bagging集成聚类的改进遗传算法

传统遗传算法在多个编码数据集群的搜索、交叉操作过程中，常常表现出无效遍历、数据冗余、搜索深度不足等问题，因而提出Bagging集成聚类算法，利用多个基学习器进行编码样本的综合学习，使聚类所有样本到聚类中心距离的平方和最小，由此得出每个集群个体的所属类别。

（一）Bagging并行式集成学习算法

Bagging是在统计学习采样技术的基础上，对多种不确定性样本进行统计、推断与学习的技术，具有多次抽样、并行集成的样本采集特征。如先给定样本容量为n的编码数据集群，从该集群中随机取出某一样本，放入Bagging采样数据集，再将该样本放回初始数据集，经过这样多次的随机抽样，重复抽样的过程为T次，得到涵盖v个样本的采样数据集，可记为Bagging样本Di=（x1，x2，…，xv），i=1，2，…，T。

针对以上T个采样出的训练样本集，选取多个基学习器对每个采样集的v个样本进行训练，再将以上多个基学习器的训练结果作出整合，输出为最终的Bagging并行式集成学习结果，完成Bagging算法的基本执行流程，具体集成学习结构如图1所示：

（二）Bagging与K均值聚类结合的遗传算法

集成聚类的遗传学习算法，是将Bagging集成学习算法、K均值聚类算法进行结合，生成K均值集成聚类算法，选定多个基学习器进行样本的训练学习，该机器训练学习流程属于无监督学习。也就是通常使用无标签的数据集、聚类准则函数，构建起用于聚类分析的准则函数：

（1）

具体集成聚类遗传算法的执行流程如图2所示。

第一步，给出n个混合样本，选取K个初始聚合中心Zj（I），j=1，2，...，K，其中I表示迭代次数。

第二步，利用Bagging集成学习算法采样数据训练集，将原始数据集的随机抽样放回原处，重复抽样过程T-1次，并获得涵盖v个样本的总共T-1抽样数据集，表示为Di=（x1，x2，…，xv），i=1，2，…，T-1。

第三步，在完成多个样本归类时，取出未抽样的w个样本，形成另一个取样集，记录为DT=（x1，x2，…，xv），则可以将以上的样本采样数据集总和为：

（2）

第四步，使用多个K均值基学习器，在T样本集上执行单独的聚类训练。将初始聚类类别数设置为K，将初始训练集中的样本数设置为z，建立K·z相关矩阵，并由基础学习者对样本进行聚类。记录基学习器的不同样本聚类类别投票的数据信息，如第i行和第j列的s数值，则表明存在有s个均值基学习器，对第i样本归类为第j类。

第五步，根据以上的K·z维关联矩阵，依照投票法则进行每个样本聚类类别的表示，其中投票数最多的聚类类别为样本类别，若投票数相同则随机选择某一类别，作为样本最终的聚类类别。

第六步，计算不同样本到聚合中心的距离D （xk，Zj（I））min={D（xk，Zj（I）），其中k=1 ，2，…，n，j=1，2，...，K，且xk∈wi。之后将得到的k个新的聚合中心，用

进行表示。

第七步，判断Zj（I+1）、Zj（I）之间的关系，若Zj（I+1）≠Zj（I）则将I+1的值赋给I，并返回第二步，否则结束算法。

图2    Bagging与K均值集成聚类遗传算法的执行流程

三、基于改进遗传算法的企业装配线计算机平衡优化数学模型

在企业装配线产线生产过程中，通常围绕工作站数、作业元素等的约束条件下，定义了装配线生产率和平滑因子的优化目标，建立了装配线多目标计算机平衡优化模型。

（一）装配流水线的作业约束

假设I为企业装配线作业元素的集合、J为工作站集合，设置装配线生产速率为C，m、n分别为装配线种群的工作站数目、作业元素个数，则Jk为第k个工作站的不同作业元素集合，k∈（1，M）。

因此，可设置企业装配线的作业元素集合为x=[x1，x2，…，xn]，将所有满足工作站数、作业元素等的约束条件的作业元素，整合为X=M·n的关系矩阵，表示不同作业元素在装配工作站中的分配情况，其中X（i，k）∈X。若X（i，k）=0，则表示装配线元素i未被分配到工作站k中;若X（i，k）=1，则表示裝配线元素i被分配到工作站k之中。之后设置Ppred为装配线作业元素i的n×n维关系矩阵集合，Ppred（i，1）表示初始作业元素，Ppred（k，i）=1表示k为i的前序作业元素，Ppred（k，i）=0表示k为i的后序作业元素。那么在企业装配线生产作业过程中，将每个作业元素i分配至单一的工作站，需要满足以下的优先关系条件：

不同装配线工作站的作业元素分配、生产速率（作业总时间）等执行公式如下所示：

（二）装配线作业的优化目标

根据企业装配线作业生产速率C、平滑因子S等的优化目标，定义工作站作业时长的最大值为生产速率C，C=maxTk、k∈（1，M）;定义平滑因子为企业装配线负荷利用率、人员利用率等平衡指标，平滑因子

因而依据以上约束条件下的企业装配线作业生产速率C、平滑因子S等优化目标，可以得出企业装配线计算机平衡优化的数学模型为：

（三）Bagging集成聚类的改进遗传算法执行流程

为了改进与提升传统遗传算法，所存在的数据搜索深度、数据遍历效率水平，主要利用Bagging集成聚类算法，对原有利用随机搜索技术的交叉、变异等迭代遗传操作，作出遗传算法种群聚类、交叉分析的改进。根据企业装配线的计算机平衡优化数学模型，将双目装配线中的生产作业要素因子，合理分配到相应的工作站之中，进行种群聚类分析的编码、适应度计算，得到每个个体的搜索与聚类结果，判定随机配对的个体是否属于同一种群聚类，以此来确定全局最优解。

记Spop为装配线生产速率C、平滑因子S等种群的数目;pop（t）为第t代种群、G为遗传代数;Pc表示交叉概率、Pm表示变异概率。则Bagging集成聚类的改进遗传算法执行流程如下所示：

第一步，设置包括Spop、G、C、S、M、Pc、Pm、T、v、K等的初始值。

第二步，令t=0，根据设置的初始化种群Ppop（0），随机产生种群Spop的多个个体数目量。

第三步，围绕第t代种群P（t）的多个个体，进行第t代种群适应度的计算，计算得出装配线作业生产速率C、平滑因子S等的适应度参考值。

第四步，惩罚项。检查每一代种群个体，是否满足装配线工作站数、作业元素等的约束条件。若不满足以M固定值为主的工作站数量约束条件，则需要向多个种群个体添加相应的适应行惩罚项，例如设置适应性参考值为500的极大值，淘汰掉那些不符合适应度要求的个体。

第五步，根据作业生产速率C、平滑因子S等的适应度参考值，进行双目标并列选择的操作，选出具有最优适应度参考值的种群个体，将其标记为S=Spop/2，然后对多个最优个体重组为第t+1代的新种群。

第六步，利用Bagging集成聚类算法，进行交叉与变异操作。依托Bagging集成聚类算法，采用单点交叉、单点变异规则，在个体编码字符串中设置交叉点、基因变异点，从对应基因范围内取一数值代替原有种群个体值。

第八步，循环操作。若满足工作站数为M的固定值约束，将t+1赋值给t，停止循环迭代计算;否则转向第三步。

四、基于改进遗传算法的计算机平衡优化模型的仿真实验分析

为对改进后的bagging集成聚类算法，进行深度搜索、交叉计算能力的验证，本文以某以制造业的变速箱装配线作业为例，设置变速箱装配线工作站M=12、作业元素数量n=27的优先关系，具体如下图所示。借助于MATLAB 2019b仿真模型，对该装配线生产速率C、平滑因子S的计算进行平衡优化，具体计算机数学模型的参量设定如下：装配线固定工作站M=12、作业元素数量n=27，以及生产速率初始值C=130s、平滑因子种群数量S=200、交叉概率Pc=0.6、变异概率Pm=0.05、遗传代数G=50。

当在每组实验中分别设定参数T=5～7、v=60～80、K=3～5时（如表1所示），得到的装配线生产速率C=120s、平滑因子S=18.3～18.4，具体优化过程如图3所示，优化时对不同代种群的生产速率C、平滑因子S最优值进行记录。

图3    基于Bagging改进遗传算法的生产速率C、平滑因子S优化过程

表1    仿真实验参数设定与结果分析

仿真实验设定参数 装配线生产速率C/s 平滑因子S

未改进遗传算法 130 19.71

T=5、v=60、K=3 120 18.36

T=5、v=80、K=5 120 18.27

T=7、v=60、K=5 120 18.43

T=7、v=80、K=3 120 18.41

从图3、表1可以得出，装配线作业生产速率的优化在5代以内得到最优值，平滑因子S分别在15代、40代后收敛，装配生产速率C、平滑因子S的双目标均得到优化。但由于在多次Bagging集成聚类算法的平衡优化过程中，得到的平滑因子S数值存在着变化性，因此可以认为在不同参数设置下，平滑因子S优化的搜索深度不同。从整体上看，在4次实验中分别设定不同参数背景下，最终平滑因子S=18.3～18.4优于未改进遗传算法的最优解，提高了装配效率、减少了总空闲时间，该Bagging集成聚类算法可用于对可行解进行深度搜索。

参  考  文  献

[1] 余航.计算机数学建模中改进遗传算法与最小二乘法应用[J].  电子设计工程. 2020（01）：15-18.

[2] 陈军红.平面控制网的复数域最小二乘法估计研究[J].  华中师范大学学报（自然科学版）. 2019（02）：181-188.

[3] 李凤坤.改进AHP-GA算法的多目标配送路径优化[J].  计算机系统应用. 2019（02）：152-157.

[4] 丁立超，黄枫，潘伟.基于改进混沌遗传算法的炮兵火力分配方法[J].  系统仿真技术. 2021（01）：12-16.

[5] 钟育彬，邓文杰.基于复杂适应度函数的因素遗传算法[J].  广州大学学报（自然科学版）. 2020（05）：47-50.

[6] 葛晓梅，李世豪.基于改进遗传算法的多目标车间布局优化问题研究[J].  现代制造工程. 2021（03）：10-14+9.