基于遺傳算法的綜合布線路徑布局研究

陳 超,陳振中

(1.江蘇卓易信息科技股份有限公司,江蘇 宜興 214200) (2.東華大學機械工程學院,上海 201620)

在5G技術和“互聯網+”的新興浪潮下,高速通訊網絡已成為現代化生活和辦公必不可少的內容. 作為通訊網絡的載體,綜合布線系統是當下智能化建筑內部通訊的中樞部分,綜合布線的穩定和合理化運行是建筑智能化的重中之重,也是其他系統智能化的前提條件[1-2]. 隨著數據網絡的飛速發展,網絡對布線的要求越來越高,而線纜的合理路徑規劃是保證智能化建筑整體性能和信號傳輸可靠性的重要前提.

相比于人工布線技術,智能優化布線技術具有較高的性價比. 由于實際中的布線施工需要考慮工期、質量、成本、安全等諸多因素[3-4],當前自動布線技術的優化算法尚不成熟,不能解決實際的需求. 計算機仿真技術的不斷發展,為解決傳統線纜布局質量不達標、布局效率低下、過于依賴設計人員的經驗等問題提供了新的途徑,其中線纜的布線設計在經歷了計算機輔助人機交互階段后,正在向自動化布局發展[5-6]. 近年來,國內外諸多學者開始將智能優化技術應用于綜合布線的決策中. Wang等[7]使用蟻群算法對影響綜合布線的指標約束進行了演化,對平面上的布線路徑優化進行了研究,一定程度上優化了整體布線的設計,有效地降低了成本. 杜海遙[8]研究了機電產品中基于斯坦納樹和粒子群算法的布線優化方法,對斯坦納樹模型進行了創新,將布線路徑問題轉變為斯坦納樹的問題進行求解并提出了符合實際布線的最小生成樹算法. 王樹玉[9]以DNA遺傳算法為基礎開發了綜合布線的輔助系統,針對頂點著色和最大獨立集等高端需求進行了研究,不僅能夠結合實際情況進行布線的統籌規劃,還得到多種解決方案. 國外對于遺傳算法的研究起步較早. 早在上個世紀,Srinivas[10]在研究多目標問題時,就首次提出了用遺傳算法解決多目標問題. 近來,Sabyasachi等[11]利用遺傳算法進行最優網絡拓撲的研究,建立穩定的網絡代理,進一步促進了智能優化算法的發展.

本文基于遺傳算法對綜合布線路徑的優化設計提出新的解決方法,并將其應用于某新建醫院智能化項目,以驗證其實際效果. 該方法可根據工期和成本的需求調節相應的權重,并結合仿真系統自動生成所需的合理布線路徑圖,實現了綜合布線的自動化設計.

1 綜合布線路徑規劃分析及優化模型的建立

本文根據實際工程需求,進行綜合布線的布局規劃. 在某施工平面圖中以X軸和Y軸進行點位的定位,模擬的路徑也是沿著X軸與Y軸衍生出來的網格進行布置,網格設定為正方形,所以無需考慮遠近端問題. 為方便后文中數學模型的定義,文中將X軸定義為i軸,Y軸定義為j軸. 如圖1所示,先將某個施工平面圖網格化,為便于觀察,降低了網格的密度,在實際操作中網格密度可根據需要進行調節.

由圖1可知,本文的優化路徑設計是根據圖中由英文和數字標識出的網格進行布置. 首先確定起始點,即弱電間的位置,為了便于觀察和理解,起始點將被固定在圖紙的中央底部位置,其余的終端點位將隨機生成,然后在約束條件下進行布線路徑的生成. 終端點位包含網絡點、監控點、音響點3種不同類型. 同時,為了符合實際,還將隨機生成障礙點,以模擬實際工程中不可穿越的立柱等障礙物.

本文的數學模型與一般的旅行商問題不同,本系統不是尋找一條經過所有點且每個點只被訪問一次的路徑問題,由于綜合布線的每一條線路都是獨立的,所以要分別考慮每一條線路的路徑,還要根據不同需求確定其權重. 為便于設計及區別點位名稱,將橫軸設定為i軸,豎軸設定為j軸,這樣即可準確地定位每一個點位在圖紙上的位置,i和j取值范圍分別為(0,I)和(0,J),以此保證模型的合理性. 其決策變量如下:

(1)

(2)

(3)

由于弱電間是固定位置,所以將起始點的數學模型設定在j軸最底端,即j=0,而i軸上的定位則根據網格的數量設置定位在中央,則:

xi0=yi0=zi0=1.

(4)

此外,還需設定其擁有相同的公共路徑,即至少兩個點位可同時使用的路徑,則:

(5)

(6)

(7)

則整個綜合布線路徑優化問題的數學模型即為:

最短路徑:

(8)

最大公共路徑:

(9)

為方便函數的建立,應將最大公共路徑由max問題改為min問題,也即公式前綴“max”改為“-min”,這樣就可合并兩個路徑的數學模型. 在兩種路徑方式前加入權重ω,且兩邊權重相加為1,則目標函數即為:

(10)

對上述函數還應加入約束條件,以保證路徑的生成能在正常范圍內,路徑優化系統能正常運作. 約束條件如下:

(1)路徑約束:

(11)

式中,公共路徑為兩種及以上的線纜都會通過的共同路徑,因此α、β、γ為獨立點位路徑的乘積.

(2)點位約束:

(1-xij)=(1-xi-1,j)(1-xi+1,j)(1-xi,j-1)(1-xi,j+1),

(12)

式中,具體點位的確定還應根據十字定位來約束,即該點位的位置應與網格圖中上下左右4個點位的乘積相一致.

由上文公式所得數學模型是非線性的,根據“0”和“1”的決策變量也明確了此問題為非線性整數規劃問題,這類問題通常是NP-HARD問題,目前并無有效的算法,所以仿真生成的布線路徑與理論上的最優路徑可能會有部分偏差. 這類問題的大型實例難以求解,只能尋求有效的啟發式算法.

2 模型的多目標遺傳算法優化設計

本文利用遺傳算法進行優化設計. 遺傳算法一般是基于目標函數的適應度值,由這個目標函數開始運算,并不需要其他類別的函數值信息,例如梯度等信息,因此面向大規模的、不連續的、高度非線性的多模態函數的優化,以及解決無解析表達式的目標函數等問題時通用性較強. 本文使用二進制編碼方式,選擇輪盤賭法進行遺傳算法的設計. 首先對染色體進行編碼,在實際操作中一條遺傳染色體可以代表一組可行解,在滿足題目約束的前提下,可初始化隨機產生N組可行解以作為初始種群,初始種群經交叉變異等過程逐漸產生最優解[12-13]. 算法的執行過程如圖2所示.

在定義基礎算法后,可確定遺傳算法的設計思路如下:

由于上述的數學模型為非線性函數,在設計優化模型程序時進行雙目標規劃,一個目標是求最大公共路徑,另一個目標是求全程路徑最小,在上文公式中統一為min開頭,即可使兩個目標的單調性一致. 由于該模型是雙目標規劃,處理雙目標問題時利用權重法使兩者統一,在優化模型程序中fitness計算即是根據上述函數進行的[14]. 具體步驟如下:

Step1初始化資源點集合F,其包含3類資源點,同時初始化地圖G,隨機生成起始點,定義算法的基本參數;

Step2建立初始種群,重復產生N=100個個體,選取其中適應度最好的個體加入種群,并按該方式建立個體個數為500的初始種群X;

Step3記錄當前資源點染色體中的數據,并依據歐式距離計算出該方案所占用的幾何距離,根據實際要求調整權重weight,轉變成適應度函數所需的變量;

Step4按照已確定的交叉參數Pe,在當前種群集合中隨機選取待交叉的個體集合Xe,隨機生成位置l,并進行染色體交叉操作,按照已確定的變異參數Pm,在當前種群集合中隨機選擇待變異的個體集合Xm;

Step5采用確定性的選擇策略,選取目標函數值最大的一部分個體進化到下一代,按照已確定的選擇概率Ps,在當前已有種群中選取適應度最低的一部分個體,并將其淘汰;

Step6經上述過程,種群已進化成新的一代,在達到最大進化代數之后,即可選擇出最優解,即適應度最高的個體,將其作為本模型的Pareto解.

3 工程仿真試驗

本系統的優化理念是以建筑的施工平面圖為基礎進行布線設計. 為進一步了解基于遺傳算法的工期費用綜合優化模型的求解過程,并驗證其有效性和可行性,本文以宜興某醫院智能化項目的工作層作為模型系統測試的對象. 該醫院工程的主體為鋼筋混凝土框架結構,總建筑面積約7.5萬m2,主樓除一樓大廳外,皆為相同建筑構造且形狀方正,因此可利用本系統進行布線路徑試驗.

根據上文的闡述,首先將施工平面圖網格化,為方便觀察、利于計算,將網格線按照16×16的樣式進行布置,如需改變精度,可以變更網格線的密度. 樓層結構中的立柱位置是已知的,但由于醫院結構的復雜性,許多障礙物如通風管道、設備支架等都是不可預估的,因此在測試時將障礙物設定為隨機定位,增加優化難度的同時,也更符合實際的情況. 首先定位起始點,弱電間位置一般在設計階段就已確定. 再明確各類終端的需求,這類終端可能是網絡語音點,也可能是監控點或廣播點,在此基礎上規劃出一條既能節省材料又能節省工期的最佳路線. 同時,也應考慮建筑物內無法穿越的障礙物,在實際的工程中這是不可避免的,因此綜合布線的路徑優化需能動態調整,才能滿足實際施工需要. 根據前文所述內容設計出來的所有主程序思路與具體步驟,在程序運行后會自動生成一個網格狀的坐標圖,并自動生成出發點和終點及障礙點等,如圖3所示.

在數學模型完善以及系統架構成型的基礎上按設計要求分配目標1和目標2的權重,進行系統測試,以此驗證最終效果. 分別修改權重參數為0.01、0.3、0.5、0.7、0.99,得出如圖4～圖8所示的路徑圖進行對比分析,并生成如圖9所示的Pareto圖.

從上述的仿真路徑圖可以看出,該路徑優化系統能達到預定的要求,根據工期和成本的權重分配可生成直觀有效的路徑布局圖,而Pareto圖也證明了其實際效果能滿足實際工程的需求.

4 結論

本文所建模型以工期和費用為優化問題,結合給定的數據和隨機的點位,同時考慮資源的優化均衡配置,基于遺傳算法進行了相應的遺傳參數設計. 而后,根據實際工程的參數,利用數據處理工具進行圖形和數值的仿真試驗,提高了綜合布線的整體施工效率,證明了遺傳算法在綜合布線路徑布局優化上的實用性和先進性.