基于改進蟻群算法的多源設計變更傳播路徑優化

吳靜

福州軟件職業技術學院智能產業學院， 福建 福州 350028

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

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

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

1 構建改進蟻群算法多源設計變更傳播路徑優化模型

1.1 零部件連接重要度分析

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

圖1 多源設計變更

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

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

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

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

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

1.2 變更傳播指數和強度評估方案

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

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

表1 iC 所在區間及含義

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

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

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

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

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

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

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

式（6）中，m表示螞蟻的總數，k表示當前螞蟻的數量，N表示當前的迭代次數，Nmax是最大的迭代次數。通過增加引導因子，從節點i到j的轉移概率可表示為：

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

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

圖2 最優變更路徑搜索算法框架

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

2 多源變更傳播路徑優化結果分析

2.1 路徑優化算例仿真驗證

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

表2 變更傳播強度計算結果

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

圖3 最優變更傳播路徑

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

2.2 多源設計變更傳播實例分析

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

圖4 變更傳播概率矩陣

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

圖5 多源變更最優傳播路徑

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

2.3 方法對比結果

將研究提出的算法與其他研究提出的多目標遺傳算法［15］以及自適應多目標動態調度算法進行比較，分別利用三種不同算法在同樣的實驗環境中進行測試，結果如圖6 所示。

圖6 各算法變更風險比較

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

3 結論

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