吳靜

福州軟件職業(yè)技術(shù)學(xué)院智能產(chǎn)業(yè)學(xué)院， 福建 福州 350028

隨著科技進(jìn)步與現(xiàn)代技術(shù)的發(fā)展，傳統(tǒng)工程產(chǎn)品的功能豐富的同時(shí)，產(chǎn)品結(jié)構(gòu)也在不斷復(fù)雜化。復(fù)雜產(chǎn)品由于功能豐富、運(yùn)行控制能力強(qiáng)大等特點(diǎn)，被廣泛運(yùn)用于視頻會(huì)議、遠(yuǎn)程教學(xué)、網(wǎng)絡(luò)實(shí)時(shí)游戲等領(lǐng)域［1-2］。但是隨著市場(chǎng)競(jìng)爭(zhēng)的不斷加劇，企業(yè)之間就需要不斷提高設(shè)計(jì)質(zhì)量來滿足客戶要求。在產(chǎn)品更新迭代時(shí)，工程變更難以避免，復(fù)雜產(chǎn)品中一個(gè)零部件的設(shè)計(jì)變更就會(huì)影響其他零部件，產(chǎn)生變更傳播，影響整個(gè)產(chǎn)品，合理規(guī)劃產(chǎn)品的設(shè)計(jì)變更將有效地降低變更的影響［3-4］。也有相關(guān)研究就產(chǎn)品設(shè)計(jì)變更問題提出相應(yīng)的解決方法，如對(duì)設(shè)計(jì)中的任務(wù)重分配以及結(jié)構(gòu)變化的動(dòng)態(tài)配置等，但是大部分的方法在設(shè)計(jì)中的穩(wěn)定性和設(shè)計(jì)時(shí)間都不理想［5］。

胡浩等針對(duì)延時(shí)、帶寬、包丟失率約束、延時(shí)抖動(dòng)、費(fèi)用最小的多約束QoS 路由問題，提出一種多約束QoS 組播路由算法［6］。該算法結(jié)合蟻群算法、遺傳算法優(yōu)勢(shì)，進(jìn)行蟻群算法、遺傳算法融合，加快了算法收斂，仿真結(jié)果表明該算法具有一定的可行性、有效性。童杰偉針對(duì)蟻群算法自身缺陷，分析蟻群算法在解決路由問題中存在全局收斂能力差、路由選擇時(shí)間長(zhǎng)、易陷入局部最優(yōu)等問題，使用云模型對(duì)原有基本蟻群算法進(jìn)行優(yōu)化，從而將算法效率提高［7］。王松基于蟻群優(yōu)化算法設(shè)計(jì)多路徑路由算法，采用蟻群信息素同構(gòu)路由表，利用反饋信息再動(dòng)態(tài)調(diào)整達(dá)到不同需求優(yōu)化目標(biāo)［8］。張新華針對(duì)構(gòu)建含QoS 多源多播網(wǎng)絡(luò)及其與網(wǎng)絡(luò)功能虛擬化的結(jié)合，提出一種基于蟻群優(yōu)化的QoS 多源多播路由算法，并改進(jìn)多源多播網(wǎng)絡(luò)中虛擬網(wǎng)絡(luò)功能節(jié)點(diǎn)部署問題［9］。

鑒于此，我們首先建立多源設(shè)計(jì)變更傳播優(yōu)化模型，其次提出蟻群算法改進(jìn)方法，利用改進(jìn)蟻群算法來優(yōu)化變更傳播路徑，最后通過實(shí)例來驗(yàn)證方法的有效性。改進(jìn)蟻群算法的多源設(shè)計(jì)變更傳播路徑優(yōu)化研究對(duì)企業(yè)縮短研制周期和提高研制質(zhì)量具有一定的指導(dǎo)意義。

1 構(gòu)建改進(jìn)蟻群算法多源設(shè)計(jì)變更傳播路徑優(yōu)化模型

1.1 零部件連接重要度分析

復(fù)雜產(chǎn)品設(shè)計(jì)出現(xiàn)多個(gè)變更源頭會(huì)導(dǎo)致傳播路徑產(chǎn)生耦合現(xiàn)象，增加了傳播處理的復(fù)雜性。多源設(shè)計(jì)變更如圖1 所示，零部件V1、V4 和V9作為初始變更零部件，三者同時(shí)發(fā)生變更，三個(gè)零部件的變更沿著連接關(guān)系向其他零部件逐漸傳播。

圖1 多源設(shè)計(jì)變更

圖1 中顯示，雙向箭頭表示多源設(shè)計(jì)變更傳播會(huì)出現(xiàn)同一個(gè)零部件同時(shí)具備吸收變更和傳播變更的能力，即零部件在變更傳播過程中重復(fù)出現(xiàn)，說明傳播過程中出現(xiàn)耦合現(xiàn)象。針對(duì)此類問題，提出了一種新的多源設(shè)計(jì)變更傳播路徑方法，利用路徑傳播強(qiáng)度的不同，設(shè)計(jì)路徑選擇權(quán)重，以此構(gòu)建了有向加權(quán)的多源設(shè)計(jì)變更傳播路徑優(yōu)化模型。

模型構(gòu)建的首要步驟是構(gòu)建零部件網(wǎng)絡(luò)，利用LinkRank 算法對(duì)零部件的連接重要度進(jìn)行評(píng)估［10-12］。其次根據(jù)變更傳播的歷史數(shù)據(jù)來獲取網(wǎng)絡(luò)中節(jié)點(diǎn)的出入度，利用出入度來進(jìn)行零部件變更屬性分類。然后從歷史變更數(shù)據(jù)中提取出零部件在設(shè)計(jì)變更時(shí)的歷史操作時(shí)間，以同樣的方式計(jì)算傳播概率，最后通過不同變量評(píng)估出變更傳播強(qiáng)度，以傳播強(qiáng)度作為傳播選擇路徑的權(quán)重，構(gòu)建出完整的多源設(shè)計(jì)變更傳播路徑優(yōu)化模型。

零部件之間的連接重要度會(huì)直接影響變更的傳播，一般情況下，變更傳播更容易發(fā)生在連接較為緊密的零部件之間［13］。利用LinkRank 算法來對(duì)零部件連接重要度進(jìn)行評(píng)估，假設(shè)游走者從初始節(jié)點(diǎn)為0 的位置出發(fā)，到達(dá)節(jié)點(diǎn)i走了k步，那么下一步的行走中，從節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移概率為G，但是在有向加權(quán)網(wǎng)絡(luò)中，存在一定的概率出現(xiàn)無指向的節(jié)點(diǎn)，即只能夠接受傳播而無法傳遞傳播的懸掛節(jié)點(diǎn)，就會(huì)導(dǎo)致對(duì)路徑的分析出現(xiàn)誤差，為了解決以上問題，將傳播概率矩陣重新定義為：

式（1）中的表示節(jié)點(diǎn)i和其他節(jié)點(diǎn)連接邊的各邊權(quán)重之和，n表示存在的節(jié)點(diǎn)個(gè)數(shù)，α表示操作者重復(fù)點(diǎn)擊原始鏈接的概率。當(dāng)節(jié)點(diǎn)是懸掛節(jié)點(diǎn)時(shí)，ia值為1，若節(jié)點(diǎn)不是懸掛節(jié)點(diǎn)，ia為0。因此，LinkRank 可以定義為：

式（2）中iπ是向量Tπ的第i個(gè)元素，G ij是概率轉(zhuǎn)移矩陣G的元素，Lij的大小決定了零部件之間的連接重要度。

1.2 變更傳播指數(shù)和強(qiáng)度評(píng)估方案

為了更好地確定節(jié)點(diǎn)的變更屬性，需要計(jì)算出各節(jié)點(diǎn)之間的變更傳播指數(shù)，變更傳播指數(shù)的計(jì)算方法如式（3）所示。定義Co ut(i)代表節(jié)點(diǎn)i的出度，表示當(dāng)i發(fā)生變更時(shí)會(huì)影響的包括節(jié)點(diǎn)i在內(nèi)的所有節(jié)點(diǎn)個(gè)數(shù)。

式（3）中的Ci n(i)代表節(jié)點(diǎn)i的入度，表示會(huì)對(duì)節(jié)點(diǎn)i造成變更影響（Initial Change Impact，ICI）的節(jié)點(diǎn)個(gè)數(shù)，取值范圍為［-1，1］。傳播指數(shù)不同的取值代表著節(jié)點(diǎn)的不同屬性，具體如表1 所示。

表1 iC 所在區(qū)間及含義

從表1 中可以看出節(jié)點(diǎn)的變更屬性存在吸收者、攜帶者和擴(kuò)散者三種。當(dāng)iC取值在［-1，-0.1］時(shí)，表示為吸收者，越容易吸收變更；當(dāng)Ci的取值在區(qū)間［-0.1，0.1］內(nèi)，即取值趨于零時(shí)，節(jié)點(diǎn)的屬性為攜帶者；當(dāng)iC的取值在［0.1，1］時(shí)，節(jié)點(diǎn)屬性就偏向于擴(kuò)散者，越容易將變更傳播到下一個(gè)節(jié)點(diǎn)。

變更傳播強(qiáng)度（Change Propagation Intensity，CPI）是有向加權(quán)網(wǎng)絡(luò)模型中各節(jié)點(diǎn)之間的連接邊的權(quán)重，傳播強(qiáng)度的大小表示傳播的權(quán)重，對(duì)路徑選擇的影響較大。傳播強(qiáng)度的評(píng)估是通過傳播指數(shù)和傳播概率等變量來決定的，在變更傳播發(fā)生后，節(jié)點(diǎn)的傳播概率對(duì)路徑選擇的影響較大，并且傳播概率也關(guān)系著節(jié)點(diǎn)的可達(dá)性。設(shè)節(jié)點(diǎn)i到節(jié)點(diǎn)j的傳播概率為ijP，前提是節(jié)點(diǎn)之間必須是相鄰節(jié)點(diǎn)，否則傳播概率無意義，ijP可以通過式（4）計(jì)算得出。可以看出，傳播概率越大，變更傳播對(duì)邊的選擇性就越大。

式（4）中的P(vi)代表節(jié)點(diǎn)i表示的零部件發(fā)生變更的概率，P(vj)代表節(jié)點(diǎn)j表示的零部件發(fā)生變更的概率，兩者不相等，只有當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j不相鄰時(shí)，Pi j=Pji= 0。

此外，任務(wù)執(zhí)行時(shí)間的長(zhǎng)短影響著變更傳播路徑的選擇，時(shí)間越短的邊，變更傳播越容易選擇，零部件之間的連接重要度越小的邊，變更傳播選擇性也越大。因此，變更強(qiáng)度在4 個(gè)變量的影響下可以定義為：

式（5）中的w1是設(shè)計(jì)任務(wù)執(zhí)行時(shí)間的權(quán)重，w2是變更傳播指數(shù)的權(quán)重，w1+w2= 1。同時(shí)對(duì)Dj和Cj進(jìn)行歸一化處理，取值范圍為［0，1］。

1.3 基于改進(jìn)蟻群算法的模型求解方案

蟻群算法能利用個(gè)體之間相互傳遞信息素實(shí)現(xiàn)信息反饋與共享，尋優(yōu)過程中的較短路徑上的信息素濃度的增加會(huì)吸引越來越多的螞蟻，最終尋找出最優(yōu)解。然而在多源變更傳播過程中，多個(gè)變更源頭同時(shí)發(fā)生變更傳播，會(huì)出現(xiàn)傳播路徑重復(fù)的耦合現(xiàn)象，增加變更最優(yōu)路徑的選擇難度［14］。針對(duì)以上問題，提出了一種改進(jìn)的蟻群算法，引入引導(dǎo)因子優(yōu)化概率轉(zhuǎn)移策略，降低了傳統(tǒng)蟻群算法在行進(jìn)中盲目選擇路徑的概率，提高蟻群算法對(duì)目標(biāo)節(jié)點(diǎn)的預(yù)見性，加快了螞蟻搜索可行解的速度。設(shè)螞蟻當(dāng)前所在節(jié)點(diǎn)i到目標(biāo)節(jié)點(diǎn)E的長(zhǎng)度為iE，則引導(dǎo)因子為：

式（6）中，m表示螞蟻的總數(shù)，k表示當(dāng)前螞蟻的數(shù)量，N表示當(dāng)前的迭代次數(shù)，Nmax是最大的迭代次數(shù)。通過增加引導(dǎo)因子，從節(jié)點(diǎn)i到j(luò)的轉(zhuǎn)移概率可表示為：

式（7）中(t)表示的是當(dāng)前節(jié)點(diǎn)的引導(dǎo)函數(shù)，(t)為選擇下一個(gè)節(jié)點(diǎn)的引導(dǎo)函數(shù)，ηij作為啟發(fā)因子，表示螞蟻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的期望程度，并且ηij=1Iij。利用改進(jìn)蟻群算法優(yōu)化變更路徑選擇，同時(shí)在分析網(wǎng)絡(luò)中定義目標(biāo)函數(shù)和約束條件如下所示：

式（8）中的uρΔ 、vρΔ 和wρΔ 表示發(fā)生變更的初始節(jié)點(diǎn)造成的變更影響，iρ、jρ和lρ表示其所代表的節(jié)點(diǎn)對(duì)上一節(jié)點(diǎn)的傳播變更的接受能力，p、q和r表示初始變更節(jié)點(diǎn)傳播變更的步數(shù)，k表示節(jié)點(diǎn)的傳播步數(shù)總和。利用改進(jìn)蟻群算法的求解最優(yōu)路徑的步驟如圖2 所示。

圖2 最優(yōu)變更路徑搜索算法框架

從圖2 中信息得出，改進(jìn)蟻群算法搜索路徑的第一步是建立產(chǎn)品零部件網(wǎng)絡(luò)模型，每個(gè)節(jié)點(diǎn)都代表其所表示的零部件，節(jié)點(diǎn)之間的連接邊表示零部件之間的連接件。第二步是利用LinkRank算法評(píng)估各節(jié)點(diǎn)的邊連接重要度。第三步是通過獲取歷史變更數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行分析，并計(jì)算出每條邊的變更傳播概率，同時(shí)獲取零部件的設(shè)計(jì)耗費(fèi)時(shí)間，并根據(jù)庫(kù)中數(shù)據(jù)計(jì)算得出變更指數(shù)，最后結(jié)合LinkRank 算法計(jì)算得到節(jié)點(diǎn)的連接重要度，計(jì)算評(píng)估各邊的變更傳播強(qiáng)度。第四步是設(shè)定多個(gè)初始變更源頭，首先評(píng)估每個(gè)節(jié)點(diǎn)吸收變更量的能力，其次設(shè)置初始變更節(jié)點(diǎn)的ICI，最后利用改進(jìn)蟻群算法進(jìn)行路徑求解，得出最優(yōu)的變更傳播路徑。

2 多源變更傳播路徑優(yōu)化結(jié)果分析

2.1 路徑優(yōu)化算例仿真驗(yàn)證

仿真測(cè)試環(huán)境為：Intel（R）Core i5-8300H CPU，8GB 內(nèi)存，硬盤500GB。采用簡(jiǎn)單的算例進(jìn)行仿真驗(yàn)證，設(shè)置10 個(gè)零部件進(jìn)行算例分析，根據(jù)零部件之間的關(guān)聯(lián)關(guān)系構(gòu)造輸入數(shù)據(jù)，其中包括變更傳播影響矩陣、研制成本和時(shí)間。計(jì)算得出變更傳播強(qiáng)度，如表2 所示。數(shù)值為0 表示兩節(jié)點(diǎn)之間沒有發(fā)生變更傳播。

表2 變更傳播強(qiáng)度計(jì)算結(jié)果

從表2 中的計(jì)算結(jié)果可以看出，初始變更節(jié)點(diǎn)會(huì)根據(jù)不同的變更傳播概率將變更影響傳播給相鄰節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)的傳播概率和吸收能力的不同造成傳播強(qiáng)度不同，最小的傳播強(qiáng)度僅為0.086，最大的傳播強(qiáng)度為0.812。利用改進(jìn)蟻群算法來求解最優(yōu)路徑，將螞蟻數(shù)量設(shè)置為600 只，設(shè)置最大迭代次數(shù)為100 次，將信息素的重要度定義為1，啟發(fā)函數(shù)的重要度定義為2，定義信息素的揮發(fā)系數(shù)為0.5，設(shè)置兩個(gè)變更源頭，分別是零部件1 和零部件3，最后計(jì)算得到的最優(yōu)變更傳播路徑如圖3 所示。

圖3 最優(yōu)變更傳播路徑

圖3中表明，由零部件1 作為初始變更節(jié)點(diǎn)，會(huì)首先變更傳播到零部件6，傳播強(qiáng)度為0.265，最終會(huì)將變更傳播到零部件5 和零部件7，傳播強(qiáng)度分別是0.352 和0.153；零部件1 也會(huì)將變更傳播到零部件10，傳播強(qiáng)度為0.086。變更源頭零部件3發(fā)生變更傳播時(shí)，會(huì)將變更傳播至零部件10，變更傳播強(qiáng)度為0.446，同時(shí)變更也會(huì)傳播到零部件4，傳播強(qiáng)度為0.187。由此可以看出，多源設(shè)計(jì)變更傳播帶來的影響最終會(huì)影響到多個(gè)零部件，變更傳播選擇的路徑傳播強(qiáng)度之和為1.489。算例仿真實(shí)驗(yàn)結(jié)果表明，提出的多源變更傳播路徑優(yōu)化模型和改進(jìn)蟻群算法具有有效性，并且傳播路徑中零部件沒有重復(fù)出現(xiàn)說明了該算法解決了不同源頭傳播帶來的路徑耦合問題。

2.2 多源設(shè)計(jì)變更傳播實(shí)例分析

實(shí)例分析采用的是直流電鉆行星齒輪箱來進(jìn)行零部件的設(shè)計(jì)變更，其中的零部件數(shù)有34 個(gè)。在進(jìn)行變更傳播最優(yōu)路徑選擇中，提取歷史數(shù)據(jù)計(jì)算得出變更傳播概率，并最終得出傳播概率矩陣如圖4 所示。

圖4 變更傳播概率矩陣

圖4中顯示，變更傳播概率矩陣是由34 階方陣構(gòu)成，每一個(gè)小方格都代表相應(yīng)節(jié)點(diǎn)變更傳播概率，顏色較深的小方格表示對(duì)應(yīng)節(jié)點(diǎn)的變更傳播概率較大，變更傳播就更容易經(jīng)過相應(yīng)節(jié)點(diǎn)，顏色越淺表示節(jié)點(diǎn)的變更傳播概率越小，變更傳播越不容易經(jīng)過相應(yīng)節(jié)點(diǎn)。通過以上結(jié)果分析，建立變更傳播分析網(wǎng)絡(luò)模型來驗(yàn)證其有效性，共有零部件34 個(gè)，102 個(gè)物理連接關(guān)系，假設(shè)零部件19、零部件21 和零部件8 作為多源初始變更零部件，運(yùn)用改進(jìn)蟻群算法求解得出的最優(yōu)傳播路徑以及變更傳播分析網(wǎng)絡(luò)如圖5 所示。

圖5 多源變更最優(yōu)傳播路徑

圖5（a）是三個(gè)初始變更零部件的ICI 分別為60、80 和110 時(shí)的最優(yōu)變更傳播路徑，可以看出，當(dāng)出現(xiàn)多個(gè)初始變更零部件時(shí)，整個(gè)變更傳播過程就會(huì)受到極大的影響，在這種情況下，所受影響的零部件有15 個(gè)，影響覆蓋率達(dá)到44.1%。將變更傳播結(jié)果顯示為變更傳播分析網(wǎng)絡(luò)如圖5（c）所示，使用粗實(shí)線箭頭表示變更傳播路徑，結(jié)果表明，在這種情況下的變更傳播迭代了75 次，迭代完成之后得到最優(yōu)解為4.327。初始變更影響較大的情況下，變更傳播影響的零部件數(shù)較多，通過降低初始變更零部件的ICI 至50、70 和90，所得出的最優(yōu)變更傳播路徑如圖5（b）所示，此時(shí)受變更傳播影響的零部件為13 個(gè)，影響覆蓋率為38.2%，比前者降低了5.9%。將變更傳播以分析網(wǎng)絡(luò)的形式顯示如圖5（d）所示，傳播路徑用粗實(shí)線的箭頭來表示路徑方向，可以得出，變更傳播經(jīng)過68 次迭代得到最優(yōu)解2.795。以上結(jié)果表明，不同的ICI 的設(shè)置會(huì)導(dǎo)致最優(yōu)傳播路徑發(fā)生變化，影響覆蓋率也產(chǎn)生相應(yīng)的改變，初始變更影響的大小，直接影響了受變更傳播影響的零部件數(shù)，影響覆蓋率也就會(huì)得到相應(yīng)的改變，說明利用改進(jìn)蟻群算法針對(duì)復(fù)雜產(chǎn)品多源設(shè)計(jì)變更傳播路徑優(yōu)化具有有效性，并且改進(jìn)的蟻群算法在多源設(shè)計(jì)變更傳播最優(yōu)路徑搜索時(shí)具有普適性。

2.3 方法對(duì)比結(jié)果

將研究提出的算法與其他研究提出的多目標(biāo)遺傳算法［15］以及自適應(yīng)多目標(biāo)動(dòng)態(tài)調(diào)度算法進(jìn)行比較，分別利用三種不同算法在同樣的實(shí)驗(yàn)環(huán)境中進(jìn)行測(cè)試，結(jié)果如圖6 所示。

圖6 各算法變更風(fēng)險(xiǎn)比較

從圖6 中可以看出，三種算法都能夠快速地趨于穩(wěn)定，其中改進(jìn)蟻群算法達(dá)到穩(wěn)定的迭代次數(shù)為15 次，略優(yōu)于其他兩種算法。除此之外，從路徑變更穩(wěn)定之后的變更風(fēng)險(xiǎn)大小可以看出，改進(jìn)蟻群算法的變更風(fēng)險(xiǎn)明顯低于其他兩種算法。以上結(jié)果說明改進(jìn)蟻群算法在復(fù)雜產(chǎn)品路徑變更設(shè)計(jì)中，穩(wěn)定性高且風(fēng)險(xiǎn)小。

3 結(jié)論

對(duì)多源設(shè)計(jì)變更傳播路徑優(yōu)化進(jìn)行研究，可以有效地幫助設(shè)計(jì)人員找到最優(yōu)的傳播路徑，提高工作效率和產(chǎn)品質(zhì)量。研究提出復(fù)雜產(chǎn)品的有向加權(quán)網(wǎng)絡(luò)模型，以此構(gòu)建多源設(shè)計(jì)變更傳播路徑優(yōu)化模型，通過對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)優(yōu)化來提高算法對(duì)目標(biāo)節(jié)點(diǎn)的預(yù)見性，加快路徑搜索的速度，利用算例仿真來驗(yàn)證算法的有效性以及通過實(shí)例分析方法的可行性。算例仿真結(jié)果顯示，變更傳播的傳播強(qiáng)度之和為1.489，說明算法具有有效性，并能夠解決路徑耦合問題。實(shí)例結(jié)果表明，在ICI 設(shè)置較大時(shí)，有15 個(gè)零部件受變更傳播影響，其影響覆蓋率為44.1%，經(jīng)過多次迭代后，獲得最優(yōu)解為4.327；在ICI 設(shè)置較低時(shí)，受變更傳播影響的零部件減少為13 個(gè)，其影響覆蓋率降低了5.9%，這表明在多源設(shè)計(jì)變更傳播最優(yōu)路徑搜索時(shí)，改進(jìn)的蟻群算法具有一定的普適性、有效性。在路徑優(yōu)化的研究中僅僅考慮了零部件層次，變更的原因并沒有體現(xiàn)，從設(shè)計(jì)參數(shù)著手來得到設(shè)計(jì)變更的解決方案將是下一步的研究方向。在蟻群算法中，各參數(shù)取值與經(jīng)驗(yàn)、網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)，這雖為算法提供較大的解的空間，卻對(duì)算法的廣泛應(yīng)用造成限制。