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

陳 超,陳振中

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

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

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

本文基于遺傳算法對綜合布線路徑的優(yōu)化設(shè)計提出新的解決方法,并將其應(yīng)用于某新建醫(yī)院智能化項目,以驗證其實際效果. 該方法可根據(jù)工期和成本的需求調(diào)節(jié)相應(yīng)的權(quán)重,并結(jié)合仿真系統(tǒng)自動生成所需的合理布線路徑圖,實現(xiàn)了綜合布線的自動化設(shè)計.

1 綜合布線路徑規(guī)劃分析及優(yōu)化模型的建立

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

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

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

(1)

(2)

(3)

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

xi0=yi0=zi0=1.

(4)

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

(5)

(6)

(7)

則整個綜合布線路徑優(yōu)化問題的數(shù)學(xué)模型即為:

最短路徑:

(8)

最大公共路徑:

(9)

為方便函數(shù)的建立,應(yīng)將最大公共路徑由max問題改為min問題,也即公式前綴“max”改為“-min”,這樣就可合并兩個路徑的數(shù)學(xué)模型. 在兩種路徑方式前加入權(quán)重ω,且兩邊權(quán)重相加為1,則目標(biāo)函數(shù)即為:

(10)

對上述函數(shù)還應(yīng)加入約束條件,以保證路徑的生成能在正常范圍內(nèi),路徑優(yōu)化系統(tǒng)能正常運作. 約束條件如下:

(1)路徑約束:

(11)

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

(2)點位約束:

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

(12)

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

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

2 模型的多目標(biāo)遺傳算法優(yōu)化設(shè)計

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

在定義基礎(chǔ)算法后,可確定遺傳算法的設(shè)計思路如下:

由于上述的數(shù)學(xué)模型為非線性函數(shù),在設(shè)計優(yōu)化模型程序時進(jìn)行雙目標(biāo)規(guī)劃,一個目標(biāo)是求最大公共路徑,另一個目標(biāo)是求全程路徑最小,在上文公式中統(tǒng)一為min開頭,即可使兩個目標(biāo)的單調(diào)性一致. 由于該模型是雙目標(biāo)規(guī)劃,處理雙目標(biāo)問題時利用權(quán)重法使兩者統(tǒng)一,在優(yōu)化模型程序中fitness計算即是根據(jù)上述函數(shù)進(jìn)行的[14]. 具體步驟如下:

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

Step2建立初始種群,重復(fù)產(chǎn)生N=100個個體,選取其中適應(yīng)度最好的個體加入種群,并按該方式建立個體個數(shù)為500的初始種群X;

Step3記錄當(dāng)前資源點染色體中的數(shù)據(jù),并依據(jù)歐式距離計算出該方案所占用的幾何距離,根據(jù)實際要求調(diào)整權(quán)重weight,轉(zhuǎn)變成適應(yīng)度函數(shù)所需的變量;

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

Step5采用確定性的選擇策略,選取目標(biāo)函數(shù)值最大的一部分個體進(jìn)化到下一代,按照已確定的選擇概率Ps,在當(dāng)前已有種群中選取適應(yīng)度最低的一部分個體,并將其淘汰;

Step6經(jīng)上述過程,種群已進(jìn)化成新的一代,在達(dá)到最大進(jìn)化代數(shù)之后,即可選擇出最優(yōu)解,即適應(yīng)度最高的個體,將其作為本模型的Pareto解.

3 工程仿真試驗

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

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

在數(shù)學(xué)模型完善以及系統(tǒng)架構(gòu)成型的基礎(chǔ)上按設(shè)計要求分配目標(biāo)1和目標(biāo)2的權(quán)重,進(jìn)行系統(tǒng)測試,以此驗證最終效果. 分別修改權(quán)重參數(shù)為0.01、0.3、0.5、0.7、0.99,得出如圖4～圖8所示的路徑圖進(jìn)行對比分析,并生成如圖9所示的Pareto圖.

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

4 結(jié)論

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