基于改進(jìn)遺傳算法的計(jì)算機(jī)數(shù)學(xué)模型構(gòu)建研究

何慶　鐘維堅(jiān)　田風(fēng)　林鋒　唐蘇東

【摘要】? ? 面向網(wǎng)絡(luò)計(jì)算機(jī)中海量的數(shù)據(jù)信息，采取傳統(tǒng)匹配搜索遺傳算法進(jìn)行匹配點(diǎn)、非匹配點(diǎn)的遍歷，通常遍歷到無(wú)效度更高的非匹配點(diǎn)較多，很難在短時(shí)間內(nèi)找到與樣本相近的最佳匹配點(diǎn)。基于此，針對(duì)基本遺傳算法的無(wú)效遍歷、數(shù)據(jù)冗余弊端，結(jié)合最小二乘法、Bagging集成聚類(lèi)算法對(duì)原有遺傳算法作出改進(jìn)，建立起相似度匹配的計(jì)算機(jī)數(shù)學(xué)模型，確定高精度因子匹配的參數(shù)估算范圍和辨識(shí)度，改進(jìn)遺傳算法關(guān)聯(lián)矩陣編碼、解碼、交叉等集成學(xué)習(xí)與迭代環(huán)節(jié)，以擴(kuò)展樣本匹配的搜索空間與深度。

【關(guān)鍵詞】? ? 改進(jìn)遺傳算法? ? 計(jì)算機(jī)? ? 數(shù)學(xué)模型? ? 構(gòu)建

引言：

在企業(yè)工業(yè)化生產(chǎn)、計(jì)算機(jī)視覺(jué)處理數(shù)據(jù)匹配中，通常需要根據(jù)視覺(jué)數(shù)據(jù)因子、工作站的數(shù)量，設(shè)置n個(gè)樣本數(shù)據(jù)為初始聚類(lèi)中心，對(duì)多個(gè)相似對(duì)象進(jìn)行最小誤差求解，將不同對(duì)象分配至距離其最近的聚類(lèi)中心，來(lái)完成算法最優(yōu)解的搜索與匹配。因而面對(duì)傳統(tǒng)遺傳算法具有的無(wú)效遍歷更多、搜索深度不足等特征，本文提出基于Bagging集成聚類(lèi)的改進(jìn)遺傳算法，建立起企業(yè)裝配線的計(jì)算機(jī)平衡優(yōu)化數(shù)學(xué)模型，將雙目裝配線中的生產(chǎn)作業(yè)要素因子，合理分配到相應(yīng)的工作站之中，進(jìn)行種群聚類(lèi)分析的編碼、適應(yīng)度計(jì)算，得到每個(gè)個(gè)體的搜索與聚類(lèi)結(jié)果。

一、傳統(tǒng)遺傳算法的編碼、數(shù)據(jù)搜索與交叉操作執(zhí)行流程

傳統(tǒng)遺傳算法為美國(guó)密歇根大學(xué)J.? H.Holland教授，根據(jù)達(dá)爾文“自然選擇理論”提出的自適應(yīng)數(shù)據(jù)信息搜索/優(yōu)化技術(shù)，其初始群體編碼是由二進(jìn)制“0”和“1”字符組成的一連串字符串，將具有類(lèi)似特征的字符串組合為特定子集，并利用隨機(jī)搜索技術(shù)對(duì)多個(gè)字符串組成集合，進(jìn)行交叉、變異等的迭代遺傳操作，來(lái)確定全局最優(yōu)解。

因而該遺傳算法主要是對(duì)編碼后的控制參數(shù)，作出編碼串模式階次的群體矢量搜索。在完成某一空間數(shù)據(jù)參量的編碼后，先對(duì)群體P（t）展開(kāi)選擇、交叉、變異等遺傳算法運(yùn)算，再根據(jù)所求問(wèn)題的目標(biāo)函數(shù)（適應(yīng)度函數(shù)），進(jìn)行編碼字符串集群中個(gè)體的適應(yīng)度評(píng)估，得到下一代群體P（t+1）。傳統(tǒng)遺傳算法的編碼、數(shù)據(jù)搜索與交叉操作的簡(jiǎn)單執(zhí)行流程如下所示。

開(kāi)始程序;

t←0;

初始化種群P（t） 編碼;

評(píng)價(jià)種群P（t）編碼;

如果不符合終止條件，則開(kāi)始循環(huán);

T←t+1;

從上一代種群P（t-1）中選擇個(gè)體，形成新的群體P（t）;

種群P（T）通過(guò)交叉和變異進(jìn)化;

種群P（T）的適應(yīng)度計(jì)算;

評(píng)價(jià)組P（T）;

周期結(jié)束;

程序執(zhí)行結(jié)束。

二、基于Bagging集成聚類(lèi)的改進(jìn)遺傳算法

傳統(tǒng)遺傳算法在多個(gè)編碼數(shù)據(jù)集群的搜索、交叉操作過(guò)程中，常常表現(xiàn)出無(wú)效遍歷、數(shù)據(jù)冗余、搜索深度不足等問(wèn)題，因而提出Bagging集成聚類(lèi)算法，利用多個(gè)基學(xué)習(xí)器進(jìn)行編碼樣本的綜合學(xué)習(xí)，使聚類(lèi)所有樣本到聚類(lèi)中心距離的平方和最小，由此得出每個(gè)集群個(gè)體的所屬類(lèi)別。

（一）Bagging并行式集成學(xué)習(xí)算法

Bagging是在統(tǒng)計(jì)學(xué)習(xí)采樣技術(shù)的基礎(chǔ)上，對(duì)多種不確定性樣本進(jìn)行統(tǒng)計(jì)、推斷與學(xué)習(xí)的技術(shù)，具有多次抽樣、并行集成的樣本采集特征。如先給定樣本容量為n的編碼數(shù)據(jù)集群，從該集群中隨機(jī)取出某一樣本，放入Bagging采樣數(shù)據(jù)集，再將該樣本放回初始數(shù)據(jù)集，經(jīng)過(guò)這樣多次的隨機(jī)抽樣，重復(fù)抽樣的過(guò)程為T(mén)次，得到涵蓋v個(gè)樣本的采樣數(shù)據(jù)集，可記為Bagging樣本Di=（x1，x2，…，xv），i=1，2，…，T。

針對(duì)以上T個(gè)采樣出的訓(xùn)練樣本集，選取多個(gè)基學(xué)習(xí)器對(duì)每個(gè)采樣集的v個(gè)樣本進(jìn)行訓(xùn)練，再將以上多個(gè)基學(xué)習(xí)器的訓(xùn)練結(jié)果作出整合，輸出為最終的Bagging并行式集成學(xué)習(xí)結(jié)果，完成Bagging算法的基本執(zhí)行流程，具體集成學(xué)習(xí)結(jié)構(gòu)如圖1所示：

（二）Bagging與K均值聚類(lèi)結(jié)合的遺傳算法

集成聚類(lèi)的遺傳學(xué)習(xí)算法，是將Bagging集成學(xué)習(xí)算法、K均值聚類(lèi)算法進(jìn)行結(jié)合，生成K均值集成聚類(lèi)算法，選定多個(gè)基學(xué)習(xí)器進(jìn)行樣本的訓(xùn)練學(xué)習(xí)，該機(jī)器訓(xùn)練學(xué)習(xí)流程屬于無(wú)監(jiān)督學(xué)習(xí)。也就是通常使用無(wú)標(biāo)簽的數(shù)據(jù)集、聚類(lèi)準(zhǔn)則函數(shù)，構(gòu)建起用于聚類(lèi)分析的準(zhǔn)則函數(shù)：

（1）

具體集成聚類(lèi)遺傳算法的執(zhí)行流程如圖2所示。

第一步，給出n個(gè)混合樣本，選取K個(gè)初始聚合中心Zj（I），j=1，2，...，K，其中I表示迭代次數(shù)。

第二步，利用Bagging集成學(xué)習(xí)算法采樣數(shù)據(jù)訓(xùn)練集，將原始數(shù)據(jù)集的隨機(jī)抽樣放回原處，重復(fù)抽樣過(guò)程T-1次，并獲得涵蓋v個(gè)樣本的總共T-1抽樣數(shù)據(jù)集，表示為Di=（x1，x2，…，xv），i=1，2，…，T-1。

第三步，在完成多個(gè)樣本歸類(lèi)時(shí)，取出未抽樣的w個(gè)樣本，形成另一個(gè)取樣集，記錄為DT=（x1，x2，…，xv），則可以將以上的樣本采樣數(shù)據(jù)集總和為：

（2）

第四步，使用多個(gè)K均值基學(xué)習(xí)器，在T樣本集上執(zhí)行單獨(dú)的聚類(lèi)訓(xùn)練。將初始聚類(lèi)類(lèi)別數(shù)設(shè)置為K，將初始訓(xùn)練集中的樣本數(shù)設(shè)置為z，建立K·z相關(guān)矩陣，并由基礎(chǔ)學(xué)習(xí)者對(duì)樣本進(jìn)行聚類(lèi)。記錄基學(xué)習(xí)器的不同樣本聚類(lèi)類(lèi)別投票的數(shù)據(jù)信息，如第i行和第j列的s數(shù)值，則表明存在有s個(gè)均值基學(xué)習(xí)器，對(duì)第i樣本歸類(lèi)為第j類(lèi)。

第五步，根據(jù)以上的K·z維關(guān)聯(lián)矩陣，依照投票法則進(jìn)行每個(gè)樣本聚類(lèi)類(lèi)別的表示，其中投票數(shù)最多的聚類(lèi)類(lèi)別為樣本類(lèi)別，若投票數(shù)相同則隨機(jī)選擇某一類(lèi)別，作為樣本最終的聚類(lèi)類(lèi)別。

第六步，計(jì)算不同樣本到聚合中心的距離D （xk，Zj（I））min={D（xk，Zj（I）），其中k=1 ，2，…，n，j=1，2，...，K，且xk∈wi。之后將得到的k個(gè)新的聚合中心，用

進(jìn)行表示。

第七步，判斷Zj（I+1）、Zj（I）之間的關(guān)系，若Zj（I+1）≠Zj（I）則將I+1的值賦給I，并返回第二步，否則結(jié)束算法。

圖2? ? Bagging與K均值集成聚類(lèi)遺傳算法的執(zhí)行流程

三、基于改進(jìn)遺傳算法的企業(yè)裝配線計(jì)算機(jī)平衡優(yōu)化數(shù)學(xué)模型

在企業(yè)裝配線產(chǎn)線生產(chǎn)過(guò)程中，通常圍繞工作站數(shù)、作業(yè)元素等的約束條件下，定義了裝配線生產(chǎn)率和平滑因子的優(yōu)化目標(biāo)，建立了裝配線多目標(biāo)計(jì)算機(jī)平衡優(yōu)化模型。

（一）裝配流水線的作業(yè)約束

假設(shè)I為企業(yè)裝配線作業(yè)元素的集合、J為工作站集合，設(shè)置裝配線生產(chǎn)速率為C，m、n分別為裝配線種群的工作站數(shù)目、作業(yè)元素個(gè)數(shù)，則Jk為第k個(gè)工作站的不同作業(yè)元素集合，k∈（1，M）。

因此，可設(shè)置企業(yè)裝配線的作業(yè)元素集合為x=[x1，x2，…，xn]，將所有滿足工作站數(shù)、作業(yè)元素等的約束條件的作業(yè)元素，整合為X=M·n的關(guān)系矩陣，表示不同作業(yè)元素在裝配工作站中的分配情況，其中X（i，k）∈X。若X（i，k）=0，則表示裝配線元素i未被分配到工作站k中;若X（i，k）=1，則表示裝配線元素i被分配到工作站k之中。之后設(shè)置Ppred為裝配線作業(yè)元素i的n×n維關(guān)系矩陣集合，Ppred（i，1）表示初始作業(yè)元素，Ppred（k，i）=1表示k為i的前序作業(yè)元素，Ppred（k，i）=0表示k為i的后序作業(yè)元素。那么在企業(yè)裝配線生產(chǎn)作業(yè)過(guò)程中，將每個(gè)作業(yè)元素i分配至單一的工作站，需要滿足以下的優(yōu)先關(guān)系條件：

不同裝配線工作站的作業(yè)元素分配、生產(chǎn)速率（作業(yè)總時(shí)間）等執(zhí)行公式如下所示：

（二）裝配線作業(yè)的優(yōu)化目標(biāo)

根據(jù)企業(yè)裝配線作業(yè)生產(chǎn)速率C、平滑因子S等的優(yōu)化目標(biāo)，定義工作站作業(yè)時(shí)長(zhǎng)的最大值為生產(chǎn)速率C，C=maxTk、k∈（1，M）;定義平滑因子為企業(yè)裝配線負(fù)荷利用率、人員利用率等平衡指標(biāo)，平滑因子

因而依據(jù)以上約束條件下的企業(yè)裝配線作業(yè)生產(chǎn)速率C、平滑因子S等優(yōu)化目標(biāo)，可以得出企業(yè)裝配線計(jì)算機(jī)平衡優(yōu)化的數(shù)學(xué)模型為：

（三）Bagging集成聚類(lèi)的改進(jìn)遺傳算法執(zhí)行流程

為了改進(jìn)與提升傳統(tǒng)遺傳算法，所存在的數(shù)據(jù)搜索深度、數(shù)據(jù)遍歷效率水平，主要利用Bagging集成聚類(lèi)算法，對(duì)原有利用隨機(jī)搜索技術(shù)的交叉、變異等迭代遺傳操作，作出遺傳算法種群聚類(lèi)、交叉分析的改進(jìn)。根據(jù)企業(yè)裝配線的計(jì)算機(jī)平衡優(yōu)化數(shù)學(xué)模型，將雙目裝配線中的生產(chǎn)作業(yè)要素因子，合理分配到相應(yīng)的工作站之中，進(jìn)行種群聚類(lèi)分析的編碼、適應(yīng)度計(jì)算，得到每個(gè)個(gè)體的搜索與聚類(lèi)結(jié)果，判定隨機(jī)配對(duì)的個(gè)體是否屬于同一種群聚類(lèi)，以此來(lái)確定全局最優(yōu)解。

記Spop為裝配線生產(chǎn)速率C、平滑因子S等種群的數(shù)目;pop（t）為第t代種群、G為遺傳代數(shù);Pc表示交叉概率、Pm表示變異概率。則Bagging集成聚類(lèi)的改進(jìn)遺傳算法執(zhí)行流程如下所示：

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

第二步，令t=0，根據(jù)設(shè)置的初始化種群Ppop（0），隨機(jī)產(chǎn)生種群Spop的多個(gè)個(gè)體數(shù)目量。

第三步，圍繞第t代種群P（t）的多個(gè)個(gè)體，進(jìn)行第t代種群適應(yīng)度的計(jì)算，計(jì)算得出裝配線作業(yè)生產(chǎn)速率C、平滑因子S等的適應(yīng)度參考值。

第四步，懲罰項(xiàng)。檢查每一代種群個(gè)體，是否滿足裝配線工作站數(shù)、作業(yè)元素等的約束條件。若不滿足以M固定值為主的工作站數(shù)量約束條件，則需要向多個(gè)種群個(gè)體添加相應(yīng)的適應(yīng)行懲罰項(xiàng)，例如設(shè)置適應(yīng)性參考值為500的極大值，淘汰掉那些不符合適應(yīng)度要求的個(gè)體。

第五步，根據(jù)作業(yè)生產(chǎn)速率C、平滑因子S等的適應(yīng)度參考值，進(jìn)行雙目標(biāo)并列選擇的操作，選出具有最優(yōu)適應(yīng)度參考值的種群個(gè)體，將其標(biāo)記為S=Spop/2，然后對(duì)多個(gè)最優(yōu)個(gè)體重組為第t+1代的新種群。

第六步，利用Bagging集成聚類(lèi)算法，進(jìn)行交叉與變異操作。依托Bagging集成聚類(lèi)算法，采用單點(diǎn)交叉、單點(diǎn)變異規(guī)則，在個(gè)體編碼字符串中設(shè)置交叉點(diǎn)、基因變異點(diǎn)，從對(duì)應(yīng)基因范圍內(nèi)取一數(shù)值代替原有種群個(gè)體值。

第八步，循環(huán)操作。若滿足工作站數(shù)為M的固定值約束，將t+1賦值給t，停止循環(huán)迭代計(jì)算;否則轉(zhuǎn)向第三步。

四、基于改進(jìn)遺傳算法的計(jì)算機(jī)平衡優(yōu)化模型的仿真實(shí)驗(yàn)分析

為對(duì)改進(jìn)后的bagging集成聚類(lèi)算法，進(jìn)行深度搜索、交叉計(jì)算能力的驗(yàn)證，本文以某以制造業(yè)的變速箱裝配線作業(yè)為例，設(shè)置變速箱裝配線工作站M=12、作業(yè)元素?cái)?shù)量n=27的優(yōu)先關(guān)系，具體如下圖所示。借助于MATLAB 2019b仿真模型，對(duì)該裝配線生產(chǎn)速率C、平滑因子S的計(jì)算進(jìn)行平衡優(yōu)化，具體計(jì)算機(jī)數(shù)學(xué)模型的參量設(shè)定如下：裝配線固定工作站M=12、作業(yè)元素?cái)?shù)量n=27，以及生產(chǎn)速率初始值C=130s、平滑因子種群數(shù)量S=200、交叉概率Pc=0.6、變異概率Pm=0.05、遺傳代數(shù)G=50。

當(dāng)在每組實(shí)驗(yàn)中分別設(shè)定參數(shù)T=5～7、v=60～80、K=3～5時(shí)（如表1所示），得到的裝配線生產(chǎn)速率C=120s、平滑因子S=18.3～18.4，具體優(yōu)化過(guò)程如圖3所示，優(yōu)化時(shí)對(duì)不同代種群的生產(chǎn)速率C、平滑因子S最優(yōu)值進(jìn)行記錄。

圖3? ? 基于Bagging改進(jìn)遺傳算法的生產(chǎn)速率C、平滑因子S優(yōu)化過(guò)程

表1? ? 仿真實(shí)驗(yàn)參數(shù)設(shè)定與結(jié)果分析

仿真實(shí)驗(yàn)設(shè)定參數(shù) 裝配線生產(chǎn)速率C/s 平滑因子S

未改進(jìn)遺傳算法 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可以得出，裝配線作業(yè)生產(chǎn)速率的優(yōu)化在5代以內(nèi)得到最優(yōu)值，平滑因子S分別在15代、40代后收斂，裝配生產(chǎn)速率C、平滑因子S的雙目標(biāo)均得到優(yōu)化。但由于在多次Bagging集成聚類(lèi)算法的平衡優(yōu)化過(guò)程中，得到的平滑因子S數(shù)值存在著變化性，因此可以認(rèn)為在不同參數(shù)設(shè)置下，平滑因子S優(yōu)化的搜索深度不同。從整體上看，在4次實(shí)驗(yàn)中分別設(shè)定不同參數(shù)背景下，最終平滑因子S=18.3～18.4優(yōu)于未改進(jìn)遺傳算法的最優(yōu)解，提高了裝配效率、減少了總空閑時(shí)間，該Bagging集成聚類(lèi)算法可用于對(duì)可行解進(jìn)行深度搜索。

參? 考? 文? 獻(xiàn)

[1] 余航.計(jì)算機(jī)數(shù)學(xué)建模中改進(jìn)遺傳算法與最小二乘法應(yīng)用[J].? 電子設(shè)計(jì)工程. 2020（01）：15-18.

[2] 陳軍紅.平面控制網(wǎng)的復(fù)數(shù)域最小二乘法估計(jì)研究[J].? 華中師范大學(xué)學(xué)報(bào)（自然科學(xué)版）. 2019（02）：181-188.

[3] 李鳳坤.改進(jìn)AHP-GA算法的多目標(biāo)配送路徑優(yōu)化[J].? 計(jì)算機(jī)系統(tǒng)應(yīng)用. 2019（02）：152-157.

[4] 丁立超，黃楓，潘偉.基于改進(jìn)混沌遺傳算法的炮兵火力分配方法[J].? 系統(tǒng)仿真技術(shù). 2021（01）：12-16.

[5] 鐘育彬，鄧文杰.基于復(fù)雜適應(yīng)度函數(shù)的因素遺傳算法[J].? 廣州大學(xué)學(xué)報(bào)（自然科學(xué)版）. 2020（05）：47-50.

[6] 葛曉梅，李世豪.基于改進(jìn)遺傳算法的多目標(biāo)車(chē)間布局優(yōu)化問(wèn)題研究[J].? 現(xiàn)代制造工程. 2021（03）：10-14+9.