基于改進蟻群算法的多源設(shè)計變更傳播路徑優(yōu)化

吳靜

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

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

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

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

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

1.1 零部件連接重要度分析

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

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

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

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

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

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

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

1.2 變更傳播指數(shù)和強度評估方案

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

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

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

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

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

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

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

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

1.3 基于改進蟻群算法的模型求解方案

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

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

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

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

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

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

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

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

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

表2 變更傳播強度計算結(jié)果

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

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

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

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

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

圖4 變更傳播概率矩陣

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

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

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

2.3 方法對比結(jié)果

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

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

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

3 結(jié)論

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