黃一學(xué),秦 克,羅 威,吳 盛,郝 佳,夏 琳

(1.中國艦船研究設(shè)計(jì)中心 一二室,湖北 武漢 430060;2.中國艦船研究設(shè)計(jì)中心 科技創(chuàng)新中心,湖北 武漢 430060;3.中國艦船研究設(shè)計(jì)中心 一○室,湖北 武漢 430060;4.北京理工大學(xué) 機(jī)械與車輛學(xué)院,北京 100081)

0 引言

艦船電力系統(tǒng)是艦船最關(guān)鍵的分系統(tǒng)之一,其主要功能是為全艦各類用電設(shè)備在不同工況下提供可靠的電力保障。艦船電力系統(tǒng)通過電纜將電源設(shè)備、變電設(shè)備、配電設(shè)備和用電設(shè)備連接成一個有機(jī)整體,根據(jù)運(yùn)行工況和用電設(shè)備的不同,分別實(shí)現(xiàn)正常供電、應(yīng)急供電、事故供電、監(jiān)測與控制以及故障隔離保護(hù)等功能。艦船電氣系統(tǒng)原理設(shè)計(jì)是艦船總體設(shè)計(jì)中的關(guān)鍵環(huán)節(jié),隨著CAD技術(shù)在設(shè)計(jì)中得到廣泛應(yīng)用,艦船電氣系統(tǒng)已經(jīng)完全擺脫了基于筆紙的設(shè)計(jì),設(shè)計(jì)方法和手段實(shí)現(xiàn)了數(shù)字化。

現(xiàn)代艦船電氣系統(tǒng)規(guī)模龐大、結(jié)構(gòu)復(fù)雜,導(dǎo)致艦船電力系統(tǒng)的設(shè)計(jì)周期長、設(shè)計(jì)變更頻繁[1]?；诩僀AD的設(shè)計(jì)方法在實(shí)踐應(yīng)用中暴露出設(shè)計(jì)速度慢、設(shè)計(jì)差錯率高、牽連變更工作量大等尖銳問題,這些問題已成為制約艦船設(shè)計(jì)工作進(jìn)一步提升效率的瓶頸。隨著人工智能技術(shù)快速發(fā)展,基于人工智能的設(shè)計(jì)技術(shù)越來越廣泛地應(yīng)用于裝備和產(chǎn)品的設(shè)計(jì)領(lǐng)域(如芯片設(shè)計(jì)和建筑設(shè)計(jì)),大大提高了設(shè)計(jì)能力和效率,節(jié)省了人力投入。智能化設(shè)計(jì)技術(shù)為解決電氣圖紙的設(shè)計(jì)提供了新的思路和手段[2]。

現(xiàn)階段,布局布線問題的主要目標(biāo)是在保證電氣線路原理正確的基礎(chǔ)上,使用盡可能小的圖紙面積、盡可能短的線路長度完成電氣圖紙的設(shè)計(jì)繪制,并盡可能兼顧工程技術(shù)人員閱讀習(xí)慣。

對于布局算法,目前主要有深度強(qiáng)化學(xué)習(xí)和對抗生成網(wǎng)絡(luò)兩條技術(shù)路徑。在深度強(qiáng)化學(xué)習(xí)方面,來自美國Google公司的研究人員對芯片布局這類問題進(jìn)行了大量研究,Google的研究人員[3]在Min-cut、Force-direction、Partitioning等算法的研究基礎(chǔ)上提出一種基于深度強(qiáng)化學(xué)習(xí)的芯片布局的規(guī)劃算法,該算法將芯片布局規(guī)劃問題作為一個強(qiáng)化學(xué)習(xí)問題,并應(yīng)用一種基于邊的圖卷積神經(jīng)網(wǎng)絡(luò)架構(gòu),能夠?qū)W習(xí)并表征芯片拓?fù)涞奶卣?最終通過大量訓(xùn)練解決芯片布局的自動化設(shè)計(jì)問題[4]。國內(nèi)上海交通大學(xué)研究人員[5]在上述研究基礎(chǔ)上按照芯片功能層級開展了進(jìn)一步的研究,提出一種稱為DeepPlace的聯(lián)合學(xué)習(xí)方法用于放置宏和標(biāo)準(zhǔn)單元,實(shí)現(xiàn)了端到端的布局任務(wù)的學(xué)習(xí)。在對抗生成網(wǎng)絡(luò)方面,加拿大西蒙菲莎大學(xué)的學(xué)者[6]對于建筑設(shè)計(jì)中的布局問題,提出一種生成器和鑒別器建立在關(guān)系架構(gòu)上的圖約束生成對抗網(wǎng)絡(luò)。他們通過將約束編碼到其關(guān)系網(wǎng)絡(luò)的圖結(jié)構(gòu)中來實(shí)現(xiàn)生成器和鑒別器的關(guān)系連接。該研究在可解釋性方面存在欠缺,因此來自加拿大的另一支研究團(tuán)隊(duì)[7]從圖論出發(fā),結(jié)合組合優(yōu)化與推理的場景,提出一系列的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用于對抗生成網(wǎng)絡(luò)的方法。對于布線算法,國內(nèi)天津大學(xué)的研究人員[8]提出一種協(xié)同進(jìn)化算法的船舶管道布線設(shè)計(jì)方法。該方法通過將工作空間劃分為三維網(wǎng)格單元,結(jié)合迷宮算法[9]、非支配排序遺傳算法Ⅱ[10]和協(xié)同進(jìn)化非支配排序遺傳算法[11-13],實(shí)現(xiàn)了一種可以在帕累托最優(yōu)解中提取最佳折衷管道的優(yōu)化程序。

綜上所述,針對布局和布線問題,現(xiàn)有研究已經(jīng)取得一定成果,但還存在兩個方面的挑戰(zhàn):①現(xiàn)有方法往往聚焦于獨(dú)立的布局或者布線問題,在布局和布線相互耦合的場景下,尚無一種一體化方法;②現(xiàn)有布局優(yōu)化算法多使用端到端的神經(jīng)網(wǎng)絡(luò)算法,其效果高度依賴數(shù)據(jù)數(shù)量與質(zhì)量,缺乏完整規(guī)則的支撐,無法避免布線失敗或錯誤,這些方法在芯片設(shè)計(jì)等一次設(shè)計(jì)、多次生產(chǎn)的應(yīng)用場景下具有一定應(yīng)用價值,但是在艦船電氣設(shè)計(jì)這種大規(guī)模設(shè)計(jì)、多次迭代、一次生產(chǎn)的應(yīng)用場景下難以應(yīng)用。為此,本文提出一種融合先驗(yàn)知識和深度神經(jīng)網(wǎng)絡(luò)的電氣布線方法。該方法首先對電氣圖紙的拓?fù)浣Y(jié)構(gòu)進(jìn)行分類,并分析其拓?fù)涮攸c(diǎn),總結(jié)形成了一套布局布線先驗(yàn)規(guī)則?；谠撓闰?yàn)規(guī)則,通過確定的流程和約束條件可以完成基本的布局布線。在此基礎(chǔ)上使用深度神經(jīng)網(wǎng)絡(luò)對布線和布局中的參數(shù)進(jìn)行微調(diào)和優(yōu)化,可以使圖紙的布局更加的合理和美觀。

1 布局方法與理論證明

1.1 方法概述

布局布線的基本過程可以概括為通過布局布線方法,從連接數(shù)據(jù)中構(gòu)建出一張電氣圖紙。在該過程中,連接數(shù)據(jù)描述了一個圖的所有節(jié)點(diǎn)及其拓?fù)溥B接關(guān)系,這些節(jié)點(diǎn)與布局過程中產(chǎn)生的所有對象(即下文中的子圖)構(gòu)成一個集合,該集合上的數(shù)學(xué)運(yùn)算則是布局布線的方法。因此布局布線問題可抽象為定義一種數(shù)學(xué)運(yùn)算,使其通過有限次運(yùn)算后,輸出一個包含電氣圖紙所有信息的元素且該元素屬于該集合。

根據(jù)上述抽象,集合上對運(yùn)算的封閉性是布局布線方法具有完備性的充要條件。其中布局布線方法具有完備性定義為可以通過有限條規(guī)則處理所有在布局布線問題中出現(xiàn)的對象。因此需要布局布線方法所對應(yīng)的數(shù)學(xué)運(yùn)算可以與該集合構(gòu)成原群。

下文將證明集合上對運(yùn)算的封閉性是布局布線方法完備性的充要條件。

假設(shè)在集合G上,某運(yùn)算+不封閉,則:

?A1,A2∈G,

A1+A2=B,

B?G。

而運(yùn)算+是定義在集合G上的,則元素B無法應(yīng)用+運(yùn)算。

對應(yīng)在布局問題中,數(shù)學(xué)運(yùn)算是先驗(yàn)規(guī)則的抽象,意味著在布線過程中產(chǎn)生了規(guī)則無法處理的對象。必要性得證。

假設(shè)在集合G上,某運(yùn)算+封閉,則:

?Ai,Aj∈G,

Ai+Aj=B。

B∈G。

則在該集合內(nèi),任意元素的數(shù)學(xué)運(yùn)算“+”產(chǎn)生的結(jié)果都在該集合G內(nèi),而運(yùn)算“+”是定義在該集合G上的。對應(yīng)在布局問題中,則是布線過程中所產(chǎn)生的所有對象都可以由有限條規(guī)則來處理,即完備性成立。充分性得證。

通過上述數(shù)學(xué)推導(dǎo)證明了布局布線方法所需的數(shù)學(xué)條件,下文將首先從技術(shù)實(shí)現(xiàn)的角度直觀介紹本文所提出的方法,并在后文中對先驗(yàn)規(guī)則進(jìn)行詳細(xì)介紹后,再對先驗(yàn)規(guī)則的數(shù)學(xué)依據(jù)再行推導(dǎo)。

方法的整體結(jié)構(gòu)如圖1所示,主要包括先驗(yàn)規(guī)則布局器和神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器兩個主要部分。

圖1 方法整體構(gòu)架圖

先驗(yàn)規(guī)則布局器根據(jù)先驗(yàn)規(guī)則、預(yù)設(shè)的布局參數(shù)和連接數(shù)據(jù)可以實(shí)現(xiàn)圖紙正確布局,旨在解決布局“有沒有”問題。先驗(yàn)規(guī)則規(guī)定了布局的流程和方法,布局參數(shù)則約束了各種元素間的間隔和布局的比例。神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器可以根據(jù)圖紙中的元件連接關(guān)系計(jì)算出相應(yīng)的布局參數(shù)。神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器在輸入拓?fù)涮卣骱?利用訓(xùn)練完成的神經(jīng)網(wǎng)絡(luò)計(jì)算得出布局所需的間距、布局比例等參數(shù),旨在解決布局“好不好”的問題。

為配合神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器的工作,方案中加入了連接矩陣壓縮器這一輔助部分來提取拓?fù)涮卣?。元件連接數(shù)據(jù)先通過連接關(guān)系轉(zhuǎn)化器轉(zhuǎn)換為連接關(guān)系矩陣,再使用連接矩陣壓縮器來進(jìn)行壓縮。連接矩陣壓縮器使用奇異值分解法進(jìn)行特征的提取壓縮。提取壓縮后的特征輸出至神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器計(jì)算得出布局參數(shù)。

先驗(yàn)規(guī)則布局器在布局時需要使用連接關(guān)系數(shù)據(jù)、元件屬性數(shù)據(jù)和布局參數(shù)3組數(shù)據(jù)。其中,連接關(guān)系數(shù)據(jù)描述各個元件之間的連接關(guān)系;元件屬性數(shù)據(jù)描述了每個元件的參數(shù)和屬性;布局參數(shù)則描述布局的比例和間距。這3個參數(shù)中,只有連接關(guān)系數(shù)據(jù)庫和元件屬性數(shù)據(jù)庫需要人工導(dǎo)入,布局參數(shù)是連接矩陣壓縮器和神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器利用連接關(guān)系數(shù)據(jù)計(jì)算得到的。

整個系統(tǒng)在應(yīng)用時的原始輸入為待繪制圖紙的元件參數(shù)表格和線纜連接表格,其中元件參數(shù)表格主要包括元件的名稱、功率等屬性信息;線纜連接表格主要包括線纜自身的屬性信息以及線纜兩端所連接的元件信息。通過這兩個表格可以完整地描述整個圖紙中元件的拓?fù)潢P(guān)系。系統(tǒng)的輸出為布局信息,包括各個元件的位置和線纜的路徑點(diǎn)以及根據(jù)這些信息所繪制的CAD圖紙。

本方法分為兩個階段:第一階段為構(gòu)建模型和規(guī)則,利用歷史圖紙訓(xùn)練出圖紙參數(shù)預(yù)測模型,同時將圖紙參數(shù)預(yù)測模型和規(guī)則分別導(dǎo)入至神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器和先驗(yàn)規(guī)則布局器;第二階段為應(yīng)用,將待繪制圖紙的元件參數(shù)表格和線纜連接表格作為原始輸入導(dǎo)入至輸入預(yù)處理器處理,生成元件連接關(guān)系和元件屬性數(shù)據(jù)存入連接關(guān)系數(shù)據(jù)庫和元件屬性數(shù)據(jù)庫。先驗(yàn)規(guī)則布局器從連接關(guān)系數(shù)據(jù)庫和元件屬性數(shù)據(jù)庫檢索出元件連接數(shù)據(jù)和元件屬性數(shù)據(jù),從神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化器獲得優(yōu)化后的布局參數(shù),并利用這3組數(shù)據(jù)計(jì)算出圖紙布局,輸出至CAD軟件得到最終電氣圖紙。

1.2 方法實(shí)現(xiàn)

1.2.1 基礎(chǔ)子圖先驗(yàn)規(guī)則

本文將首先介紹樹狀圖、樹狀圖內(nèi)布局場景的分類并定義相關(guān)概念,后介紹規(guī)則設(shè)計(jì)的基本原則,最后再詳細(xì)闡述規(guī)則的內(nèi)容。

實(shí)際的電氣接線圖可以分為樹狀接線圖和非樹狀接線圖,樹狀的接線圖占90%以上,剩余的非樹狀接線圖通過工程方法可轉(zhuǎn)換為樹狀布線圖。因此,圖紙布置先驗(yàn)規(guī)則針對于樹狀圖進(jìn)行設(shè)計(jì)。如圖2所示為一樹狀接線圖示例。

圖2 樹狀接線圖

樹狀接線圖指的是圖形內(nèi)不包含回環(huán)的圖,其內(nèi)部存在串聯(lián)與并聯(lián)兩種連接方式,任何一張樹狀圖都可以通過串聯(lián)和并聯(lián)構(gòu)造出來。其中并聯(lián)連接方式歸納為一種“元件子圖并聯(lián)”,但串聯(lián)連接方式分為“元件串聯(lián)”與“元件子圖串聯(lián)”兩種場景,其中“元件”與“子圖”的定義如下:

(1)元件 元件在本文中指的是圖中最小的,不可再進(jìn)行拆分的節(jié)點(diǎn)。因?yàn)椴煌趫D紙中基本都有著相似的大小,所以可以將這類元件近似到一個相同的大小,便于布局布線算法處理。

(2)子圖 子圖描述的是經(jīng)過布局后的一部分元件或子圖形成的整體。在每個部分的元件布局完成之后,使用一個子圖來將這些元件和其布局形成一個整體。隨著布局的進(jìn)行,子圖和子圖、子圖和元件、元件和元件都會在布局完成后打包成一個整體,形成新的子圖。

綜上所述,3種布局場景(基礎(chǔ)布局場景)定義如下:

(1)元件串聯(lián)場景 在布局中,所布局的單元只包含元件且元件之間俱為串聯(lián)關(guān)系。

(2)元件子圖串聯(lián)場景 在布局中,所布局單元包含元件和子圖且元件和子圖之間俱為串聯(lián)關(guān)系。

(3)元件子圖并聯(lián)場景 在布局中,所布局的單元包含元件和子圖,且并聯(lián)連接到一個元件或子圖。

本方法結(jié)合實(shí)際布局布線場景,針對每種場景設(shè)計(jì)確定的布局布線流程,3種場景所對應(yīng)的三個布局布線流程即為先驗(yàn)規(guī)則。因?yàn)閳D紙的設(shè)計(jì)過程中存在布局和布線相互耦合的問題,所以如果針對全局考慮,兩者的耦合會導(dǎo)致優(yōu)化無法同時兼顧。因而,按照上述3種基礎(chǔ)布局場景,分別對各個場景設(shè)計(jì)側(cè)重于布局的規(guī)則或側(cè)重于布線的先驗(yàn)規(guī)則,進(jìn)而實(shí)現(xiàn)布局與布線的解耦。

先驗(yàn)規(guī)則本身遵循如下兩條原則:①保證線纜連接無相交(對應(yīng)布線問題);②在滿足線纜無相交的情況下,盡量降低每個元件所占用的圖紙面積(對應(yīng)布局問題)。接下來本文將闡述不同場景下的先驗(yàn)規(guī)則。

(1)元件串聯(lián)場景 該場景指的是在布局中,所布局的單元只包含元件且元件之間俱為串聯(lián)關(guān)系。因?yàn)楸緢鼍爸灰ＷC按順序進(jìn)行排列即可滿足線纜無交叉的原則(即布線問題較易解決,布局問題較難優(yōu)化),因此該場景的規(guī)則主要考量空間利用率(使用盡量小的圖紙面積布局下更多的元件)。綜上,本方案先根據(jù)設(shè)定的子圖長寬比計(jì)算出長寬節(jié)點(diǎn)數(shù)。由于計(jì)算出的長寬節(jié)點(diǎn)數(shù)不一定是整數(shù),首先對長寬節(jié)點(diǎn)數(shù)的浮點(diǎn)數(shù)向上取整,然后試探子塊的長寬節(jié)點(diǎn)數(shù)能否減少一個節(jié)點(diǎn),若不行,則使用向上取整之后的長寬節(jié)點(diǎn)數(shù)作為所需的長寬節(jié)點(diǎn)數(shù);可以,則使用減少后的長寬節(jié)點(diǎn)數(shù)。確定長寬節(jié)點(diǎn)數(shù)之后,將元件根據(jù)連接順序按照橫向S形排列,即可完成布局。如圖3a所示為5個元件串聯(lián)的布局案例示意圖,圖3b則是應(yīng)用此條規(guī)則的布局結(jié)果(長寬比取2∶3時),由于軟件所用繪圖庫無法使用中文,使用“元件”的拼音首字母縮寫“yj”來代替“元件”一詞,余同。

圖3 元件串聯(lián)場景圖

(2)元件子圖串聯(lián)場景 不同元件子圖的串聯(lián)布局經(jīng)過窮舉只存在一種情形,即最后一個子圖尺寸大,前面的元件為標(biāo)準(zhǔn)元件大小且大小相同。這種布局場景和上一場景類似(即布線問題較易解決,布局問題較難優(yōu)化),著重考慮提高空間利用率。根據(jù)串聯(lián)特點(diǎn),設(shè)計(jì)如下排布算法。首先,將最大的子圖放在最上方,并以子圖的寬度作為布局寬度,然后在子圖的下方按照縱向S形走線的布置方法布置元件,布置元件時保持布局寬度不變,僅改變布局高度來適應(yīng)不同的元件數(shù)量。如圖4a所示為5個元件與1個子圖串聯(lián)的布局案例的示意圖,圖4b則是應(yīng)用此條規(guī)則的布局結(jié)果。

圖4 元件子圖串聯(lián)場景圖

(3)元件子圖并聯(lián)場景 不同大小的子圖和元件的并聯(lián)合并場景如果單純追求空間利用率,利用諸如貪婪算法的布局算法,可能會出現(xiàn)線纜相交的問題,導(dǎo)致布線困難。為此,本場景下的規(guī)則將避免線纜相交置于最高優(yōu)先級(優(yōu)先解決布線問題,再考慮布局問題),其次再考慮布局的空間利用率。實(shí)際布局時:首先使用排序算法對需要并聯(lián)的元件和子圖進(jìn)行一次排序,然后按照先大后小的順序從左到右進(jìn)行布置,最后將與這些元件子圖同時連接的元件放在整個布局的下方正中央,即可完成元件子圖并聯(lián)場景的布局。如圖5a所示為1個元件與3個子圖并聯(lián)的布局案例的示意圖,圖5b則是應(yīng)用此條規(guī)則的布局結(jié)果。

圖5 元件子圖并聯(lián)場景圖

針對上述說明,從數(shù)學(xué)的角度對完備性進(jìn)行證明,具體證明過程如下所示:

一個無向簡單圖內(nèi)任意兩個頂點(diǎn)能被唯一的路徑所連通,則該圖是一棵樹。樹是沒有回路的連通圖,指定一個節(jié)點(diǎn)為樹的根,則該樹為有根樹。有根樹中的節(jié)點(diǎn)可以根據(jù)節(jié)點(diǎn)到根的距離分層。通過這種分層,可以定義節(jié)點(diǎn)的方向。對于樹中的任一節(jié)點(diǎn),有且僅有兩種與子節(jié)點(diǎn)的連接方式:與一個子節(jié)點(diǎn)相連、與多個子節(jié)點(diǎn)相連。而這兩種連接方式對應(yīng)到電氣布線分類中則稱為串聯(lián)和并聯(lián)。

因此,對于任意符合有根樹的樹狀接線圖,內(nèi)部有且僅有串聯(lián)和并聯(lián)兩種連接方式。故樹狀接線圖可以通過有限次元件的串聯(lián)和并聯(lián)構(gòu)成。

上述論證表明,通過串聯(lián)和并聯(lián)最小的基本單元可以構(gòu)建出一個完整的樹。在本文中,最小基本單元定義為子圖和元件,這些最小基本單元所構(gòu)成的集合稱為G,將串聯(lián)和并聯(lián)抽象為兩種運(yùn)算,因?yàn)榉椒ǖ耐陚湫远x與原群定義等價,所以通過證明集合G與這兩種運(yùn)算構(gòu)成原群可以證明本方法具有完備性。

首先基于抽象代數(shù)定義如下代數(shù)系統(tǒng),定義元件集合的數(shù)學(xué)符號為A,每個元件通過集合符號與下標(biāo)表示,子圖集合的數(shù)學(xué)符號為B,每個子圖通過集合符號與下標(biāo)表示,串聯(lián)數(shù)學(xué)運(yùn)算符號為+,并聯(lián)的數(shù)學(xué)符號為⊕,則上述規(guī)則可以歸納為3類運(yùn)算:

元件串聯(lián)的運(yùn)算定義為:

Am+An=Bj,

(1)

Am+Am-1+…+An=Bk。

(2)

元件子圖串聯(lián)的運(yùn)算定義為:

Bm+An=Bj,

(3)

Bm+Am+Am-1+…+An=Bk。

(4)

元件子圖并聯(lián)的運(yùn)算定義為:

Bm⊕Bn=Bj,

(5)

Am⊕An=Bk,

(6)

Bm⊕Bm-1⊕…⊕Bn⊕Am⊕
Am-1⊕…⊕An=Bl。

(7)

定義集合G:

G=A∪B,

(8)

A1,A2,A3…An∈A,

(9)

B1,B2,B3…,Bn∈B。

(10)

對于串聯(lián)運(yùn)算+,可以證明集合G關(guān)于+運(yùn)算具有封閉性:

∵Am+An=Bj,

Bm+An=Bk,

Bj,Bk∈B∈G。

因此集合G關(guān)于+運(yùn)算具有封閉性。

對于并聯(lián)運(yùn)算⊕,也可證明集合G關(guān)于運(yùn)算⊕具有封閉性:

∵Bm⊕Bn=Bj,

Bm⊕An=Bk,

Am⊕An=Bl

Bj,Bk,Bl∈B∈G。

因此集合G關(guān)于⊕運(yùn)算具有封閉性。故集合G關(guān)于上述兩運(yùn)算分別構(gòu)成原群。其中m,n,i,j,k,l均為正整數(shù)下標(biāo)。

1.2.2 參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)

上述先驗(yàn)規(guī)則可以實(shí)現(xiàn)完備的自動化布局布線,但在空間利用率方面存在提升空間。由于布局參數(shù)控制圖紙中各個部分的間距和比例,對布局參數(shù)進(jìn)行優(yōu)化可以提高空間利用率。神經(jīng)網(wǎng)絡(luò)優(yōu)化方法在很多參數(shù)優(yōu)化場景中顯示出較好的優(yōu)化效果[14],但是其訓(xùn)練需要大量的數(shù)據(jù)和算力,這些實(shí)際困難阻擋了端到端神經(jīng)網(wǎng)絡(luò)在本場景中的應(yīng)用[15]。

為了提高空間利用率,本文在前述方法的基礎(chǔ)上引入了神經(jīng)網(wǎng)絡(luò)優(yōu)化方法,通過神經(jīng)網(wǎng)絡(luò)優(yōu)化方法可以根據(jù)實(shí)際布局拓?fù)涮卣髡{(diào)整布線參數(shù)。如圖6所示,本方法首先將圖紙拓?fù)涮卣餍畔⑥D(zhuǎn)換為連接關(guān)系矩陣,然后通過奇異值分解提取該矩陣的特征作為輸入向量交由神經(jīng)網(wǎng)絡(luò)進(jìn)行計(jì)算,最后經(jīng)過前向傳播得到布局參數(shù)。下文將分別介紹連接關(guān)系矩陣、奇異值分解和神經(jīng)網(wǎng)絡(luò)的技術(shù)細(xì)節(jié)。

圖6 神經(jīng)網(wǎng)絡(luò)優(yōu)化方法示意圖

連接關(guān)系矩陣是圖紙拓?fù)涞木仃囆问?。對于一個由n個元件組成的圖紙,生成n×n的零矩陣,每個元件對應(yīng)矩陣的一行與一列。如果圖紙中兩個元件直接相連,則將矩陣中兩個元件對應(yīng)的行列所確定的兩個元素置為1(因?yàn)槊總€元件對應(yīng)一個行與一個列,所以兩個元件可以確定出兩個對稱坐標(biāo)的元素)。遍歷所有連接,并據(jù)此將矩陣中相應(yīng)的元素置1后,即可獲得連接關(guān)系矩陣。如圖7所示例子為一個具有5個元件的拓?fù)浼捌溥B接關(guān)系矩陣。

圖7 接拓?fù)渑c連接關(guān)系矩陣的轉(zhuǎn)換關(guān)系

利用奇異值分解提取拓?fù)涮卣鞯姆椒梢越档蜕窠?jīng)網(wǎng)絡(luò)的處理難度[16]。該方法在連接關(guān)系矩陣輸入到神經(jīng)網(wǎng)絡(luò)之前,使用奇異值分解該矩陣,舍棄掉較小奇異值及其對應(yīng)的酉向量從而提取連接關(guān)系矩陣中主要特征。取舍比例按照下述方法推導(dǎo)。對496張電氣圖紙的元件數(shù)量進(jìn)行統(tǒng)計(jì)(詳細(xì)統(tǒng)計(jì)數(shù)據(jù)見后文3.4節(jié)實(shí)驗(yàn)部分)得到平均每張圖紙中含有約250個元件,對應(yīng)連接關(guān)系矩陣平均大小為一個250行250列的實(shí)對稱矩陣。根據(jù)現(xiàn)有研究成果,取前10%到20%的奇異值可以同時兼顧信息保留和壓縮效率[17]。根據(jù)現(xiàn)有圖紙統(tǒng)計(jì)數(shù)據(jù),圖紙中的元件數(shù)量上限約為330個,由于現(xiàn)有圖紙統(tǒng)計(jì)數(shù)據(jù)樣本具有一定的局限性,需留取一定的元件數(shù)量裕度。因此,取圖紙?jiān)?shù)量上限為400個(連接關(guān)系矩陣尺寸為400×400)滿足極端情況后,按照10%的下限取值為40個奇異值作為輸入?yún)?shù)。該取值在平均元件數(shù)量250個(連接關(guān)系矩陣尺寸為250×250)時對應(yīng)的比例為16%,也能滿足壓縮效率上的需求。

神經(jīng)網(wǎng)絡(luò)包含4個隱藏層,隱藏層神經(jīng)元數(shù)量(32,64,256,128),使用了ReLu激活函數(shù)、tanh激活函數(shù)和Sigmoid激活函數(shù),神經(jīng)網(wǎng)絡(luò)的具體結(jié)構(gòu)和參數(shù)如圖8所示。神經(jīng)網(wǎng)絡(luò)訓(xùn)練超參數(shù)如表1所示。

表1 神經(jīng)網(wǎng)絡(luò)訓(xùn)練超參數(shù)設(shè)置

圖8 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與參數(shù)示意圖

輸入?yún)?shù)經(jīng)神經(jīng)網(wǎng)絡(luò)前向傳播計(jì)算后,輸出子圖的長寬比和最佳間距兩個布局參數(shù)。神經(jīng)網(wǎng)絡(luò)可以在后文所述的節(jié)點(diǎn)迭代過程中多次調(diào)用,例如一個包含一些元件的子圖如果希望得到自己的長寬比例和最佳間距比,也可以在自己內(nèi)部調(diào)用該神經(jīng)網(wǎng)絡(luò)來進(jìn)行預(yù)測。通過該神經(jīng)網(wǎng)絡(luò)的優(yōu)化可提高圖紙的空間利用率。

1.2.3 節(jié)點(diǎn)迭代法

因?yàn)椴季植季€場景具有隨機(jī)性,同時考慮到在布局過程中,所需要布局的元件數(shù)量不確定,布局的結(jié)構(gòu)層數(shù)也不確定,所以方案引入了節(jié)點(diǎn)迭代法來遍歷并布局所有元件。該方法可以自行根據(jù)元件連接關(guān)系來迭代調(diào)用并確定元件布局。節(jié)點(diǎn)迭代法可以簡單概括為“自上而下迭代,自下而上布局”。算法偽代碼如圖9所示。為了降低內(nèi)存占用,方案選擇了深度優(yōu)先的搜索策略。

圖9 節(jié)點(diǎn)迭代法偽代碼

實(shí)際節(jié)點(diǎn)迭代法運(yùn)行流程如圖10所示,從父節(jié)點(diǎn)(初始節(jié)點(diǎn))開始,判斷父節(jié)點(diǎn)(初始節(jié)點(diǎn))和與其連接的節(jié)點(diǎn)是否符合基礎(chǔ)布局場景。若符合,使用相應(yīng)布局場景的規(guī)則進(jìn)行布局;否則,從該節(jié)點(diǎn)的第一個子節(jié)點(diǎn)開始,繼續(xù)判斷是否符合基礎(chǔ)布局場景,即按照深度優(yōu)先算法進(jìn)行搜索,直到符合基礎(chǔ)布局場景。完成布局后將該部分元件和子圖替換為布局完成的子圖。當(dāng)一個節(jié)點(diǎn)下的所有元件都布局完成,那它一定符合基礎(chǔ)布局場景,因此也可以被布局成一個完整的子圖。最終可以得到完整的、包含所有元件的圖紙布局。當(dāng)完成布局任務(wù)之后,按照連接關(guān)系連線,完成電氣布線圖的繪制。

圖10 節(jié)點(diǎn)迭代運(yùn)行流程圖

2 流程推演與實(shí)例仿真

2.1 布局過程推演說明

下面通過樣例說明上述方法生成電氣布線圖的過程。樣例包含一個由8個元件組成的電氣拓?fù)浣Y(jié)構(gòu)(如圖11a)。

圖11 復(fù)雜場景布局步驟示意圖1

方法運(yùn)行時從“元件1”開始判斷。發(fā)現(xiàn)“元件1”及其下面的結(jié)構(gòu)并不符合基礎(chǔ)布局場景;因此,探索“元件1”的子節(jié)點(diǎn),發(fā)現(xiàn)子節(jié)點(diǎn)“元件2”及其下面的結(jié)構(gòu)也不符合基礎(chǔ)布局場景;繼續(xù)探索“元件2”的子節(jié)點(diǎn),這個時候識別到“元件2”的第一個子節(jié)點(diǎn)“元件4”及其下面的節(jié)點(diǎn)符合基礎(chǔ)布局場景中的“元件串聯(lián)場景”。調(diào)用“元件串聯(lián)場景”的規(guī)則將“元件4”及其下面的3個元件的布局計(jì)算出來,并將這4個元件替換成一個包含了其本身信息以及布局信息的子圖,這樣整個圖形的拓?fù)洳季志腿鐖D11b所示。

當(dāng)“子圖1”替換到了整個圖形中之后,將“元件5”與規(guī)則匹配,發(fā)現(xiàn)“元件5”是一個單節(jié)點(diǎn),并無串并聯(lián)關(guān)系,無需處理。

當(dāng)“元件2”的子節(jié)點(diǎn)被全部處理完之后,結(jié)束當(dāng)前層級的搜索,返回“元件2”發(fā)現(xiàn)“元件2”及其下面的元件和子圖符合基礎(chǔ)布局場景中的“元件子圖并聯(lián)場景”。應(yīng)用“元件子圖并聯(lián)場景”規(guī)則將“元件2”及其下面的一個子圖和一個元件的布局計(jì)算出來,并將這部分也替換成“子圖2”,如圖12a所示。

圖12 復(fù)雜場景布局步驟示意圖2

當(dāng)“元件2”及其下面的部分被替換為“子圖2”之后,與上述方式類似,“元件1”及其下面的子圖和元件也可以應(yīng)用“元件子圖并聯(lián)場景”規(guī)則進(jìn)行布局。至此,成功完成一個包括8個節(jié)點(diǎn)的串并聯(lián)拓?fù)涞碾娐返牟季?如圖12b所示。最后按照連接關(guān)系將元件用線纜連接起來即可。由于先驗(yàn)規(guī)則在布局過程中已經(jīng)充分考慮到線纜布置并進(jìn)行了恰當(dāng)?shù)囊?guī)劃和取舍,可直接用直線和折線進(jìn)行連接,就可以完成布線的任務(wù)。最終效果圖如圖13所示。

圖13 復(fù)雜場景布局結(jié)果示意圖

2.2 實(shí)例仿真

布局布線任務(wù)完成之后,即可根據(jù)輸出的布局布線數(shù)據(jù)調(diào)用CAD二次開發(fā)軟件接口進(jìn)行圖紙繪制。調(diào)用過程按照如下步驟進(jìn)行,首先在數(shù)據(jù)庫中搜索出每個元件名稱對應(yīng)的元件CAD器件庫,然后按照布局布線數(shù)據(jù)中的布局坐標(biāo)將每個元件繪制在CAD的圖紙上,最后再根據(jù)元件間連接關(guān)系連接線路,繪圖效果如圖14和圖15所示。圖14a展示的是應(yīng)急充放電匯流排的電路組成與連接關(guān)系,圖14b為應(yīng)用本文所述方法計(jì)算出的布局布線示意圖,圖15a為最終調(diào)用CAD軟件接口生成的工程圖紙,圖15b則說明了工程圖紙與示意圖中元件的對應(yīng)關(guān)系。

圖14 應(yīng)急充放電匯流排布局圖

圖15 應(yīng)急充放電匯流排CAD工程圖

3 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)論

3.1 先驗(yàn)規(guī)則布局實(shí)驗(yàn)

該部分實(shí)驗(yàn)使用技術(shù)手段屏蔽了布局參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)及連接矩陣壓縮器,使用人工指定的布局參數(shù)對先驗(yàn)規(guī)則布局器進(jìn)行測試。

實(shí)驗(yàn)實(shí)際選取某民用艦船的部分圖紙?jiān)O(shè)計(jì)工作作為測試樣本,所選的7張圖紙中,布局布線都未出現(xiàn)錯誤。在更大測試樣本上,496張圖紙的布局布線都沒有出現(xiàn)錯誤。

在使用先驗(yàn)規(guī)則進(jìn)行布局的過程中,面積比和線長比兩個參數(shù)可以描述算法布局與人工布局參數(shù)差異[18]。其中:面積比為算法布局的圖紙面積比人工布局的圖紙面積;線長比為算法布局的走線長度比人工布局的走線長度。表2所示的實(shí)驗(yàn)結(jié)果為所選的實(shí)驗(yàn)樣本經(jīng)過本方法布局后在面積與線長方面與人工布局的差距。根據(jù)表2中的數(shù)據(jù),在僅使用先驗(yàn)規(guī)則布局的情況下,所選7張測試圖紙的平均面積比為1.635,即使用先驗(yàn)規(guī)則布局的圖紙面積比人工布局的圖紙面積大63.5%;平均線長比為1.325,即使用先驗(yàn)規(guī)則布局的布線長度比人工布局的布線長度大32.5%。

表2 先驗(yàn)規(guī)則布局實(shí)驗(yàn)結(jié)果

該實(shí)驗(yàn)表明,基于先驗(yàn)規(guī)則的布局方法可以有效解決船舶電氣設(shè)計(jì)中的布線布局問題,但是該方法實(shí)際占用圖紙面積超過人工布局63.5%、實(shí)際規(guī)劃線長超過人工布線32.5%,在布局布線的空間利用率方面和人工布局布線相比還存在差距。

3.2 參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)訓(xùn)練實(shí)驗(yàn)

在神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程中,可能會無法收斂,因此設(shè)計(jì)如下實(shí)驗(yàn)驗(yàn)證本文所述參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)是否能夠正常收斂且收斂速度與傳統(tǒng)端到端神經(jīng)網(wǎng)絡(luò)是否存在區(qū)別。

參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)的訓(xùn)練使用了一個擁有1 984個樣本的數(shù)據(jù)集。選取樣本中1 488個樣本作為訓(xùn)練集,496個樣本作為驗(yàn)證集,每次隨機(jī)選取40個樣本作為一個batch來進(jìn)行訓(xùn)練。在訓(xùn)練過程中,誤差函數(shù)在經(jīng)過約17萬次的迭代后收斂。如圖16所示的誤差函數(shù)的變化曲線展示的是驗(yàn)證集上的誤差函數(shù)的變化趨勢,其中橫坐標(biāo)表示迭代次數(shù),縱坐標(biāo)表示損失函數(shù)值。

圖16 神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中損失函數(shù)的收斂趨勢

圖16中,灰色線條表示傳統(tǒng)端到端神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中損失函數(shù)的變化過程,藍(lán)色線條表示引入奇異值分解壓縮的參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中損失函數(shù)的變化過程。對比兩曲線,在本文所提出的參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)已經(jīng)收斂時,傳統(tǒng)端到端神經(jīng)網(wǎng)絡(luò)尚未收斂。通過基于奇異值分解的壓縮之后,神經(jīng)網(wǎng)絡(luò)的收斂速度[19]相比端到端神經(jīng)網(wǎng)絡(luò)的收斂速度有顯著提升。

3.3 末端優(yōu)化實(shí)驗(yàn)

本實(shí)驗(yàn)中所闡述的末端優(yōu)化方法主要由兩部分組成:①參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò);②基于奇異值分解的連接矩陣壓縮器。本實(shí)驗(yàn)旨在驗(yàn)證這些優(yōu)化方法在提升圖紙空間利用率方面所能起到的效果。

本實(shí)驗(yàn)中解除了前文中3.1節(jié)所述的實(shí)驗(yàn)對布局參數(shù)優(yōu)化神經(jīng)網(wǎng)絡(luò)和連接矩陣壓縮器的屏蔽。在加入了末端優(yōu)化算法處理之后,用與前文中3.1節(jié)同樣的方法和定義記錄相同圖紙實(shí)驗(yàn)數(shù)據(jù),如表3所示,其中面積比為算法布局的圖紙面積比人工布局的圖紙面積;線長比為算法布局的走線長度比人工布局的走線長度,面積優(yōu)化率與線長優(yōu)化率均是針對前文中3.1節(jié)所展示的實(shí)驗(yàn)結(jié)果(后文用原圖紙面積與原線長指代)進(jìn)行計(jì)算的,面積優(yōu)化率指引入末端優(yōu)化方法后減少的圖紙面積占原圖紙面積的百分比;線長優(yōu)化率指引入末端優(yōu)化方法后減少的線長占原線長的百分比。

表3 末端優(yōu)化實(shí)驗(yàn)結(jié)果

表3中7張圖紙面積比的平均值為1.275、線長比的平均值為1.209、面積優(yōu)化率的平均值為21.44%、線長優(yōu)化率的平均值為8.53%。

與前文中3.1節(jié)的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對比,7張圖紙面積比的平均值從1.635下降到了1.275,下降了21.99%;線長比的平均值從1.325下降到了1.209,下降了8.79%。在空間利用率方面,經(jīng)過末端優(yōu)化算法優(yōu)化之后的圖紙面積比人工布局的面積平均大27.57%,布線長度平均大20.90%。

在經(jīng)過末端優(yōu)化算法優(yōu)化之后,算法的布線水平已經(jīng)接近人工,綜合考慮到算法布線的布線速度和布線正確率,本算法已經(jīng)能夠勝任大部分場景下的自動化布線任務(wù)。

3.4 布局布線速度分布實(shí)驗(yàn)

在布局布線工作中,布局布線的速度也是影響工作效率的一個重要因素,但是布線速度不僅和算法的運(yùn)算速度相關(guān),還與圖紙中元件的數(shù)量相關(guān)聯(lián)。因此,本實(shí)驗(yàn)旨在收集本算法在不同元件數(shù)量下的布局布線速度,同時也探究布線速度與元件數(shù)量之間的關(guān)系。

實(shí)驗(yàn)隨機(jī)選取了496張不同元件數(shù)量的圖紙進(jìn)行布局布線速度測試,得到了如下的布局布線速度分布曲線,以及近似的布局布線速度與元件數(shù)量的關(guān)系曲線。

圖17展示了所選取的496張圖紙中元件數(shù)量情況,測試用圖紙中的元件數(shù)量全部在400個以內(nèi)。圖18展示了所選取的圖紙中布局布線時間所需時間長度的分布,經(jīng)統(tǒng)計(jì),99.1%圖紙都能在10秒內(nèi)完成布局布線的計(jì)算,速度為普通人工布線速度的300倍。圖19展示了圖紙的布局時間與元件數(shù)量的關(guān)系,通過線性回歸擬合發(fā)現(xiàn)布局布線的時間與圖紙中所包含的器件近似呈二次函數(shù)關(guān)系,因此隨著元件數(shù)量的增加,布局布線的時間也會變長。

圖17 布局樣本元件數(shù)量分布圖

圖18 布局布線所需時間分布

圖19 布局布線速度與元件數(shù)量關(guān)系圖

3.5 實(shí)驗(yàn)結(jié)論

經(jīng)過上述4組實(shí)驗(yàn),可得出以下實(shí)驗(yàn)結(jié)論。本文所提方法能夠有效解決艦船電氣圖紙的布局布線場景中可靠性低、合理性低和布局效率低的問題。在布局可靠性方面,能夠保證相關(guān)元件連接關(guān)系正確;在布局合理性方面,空間利用率已經(jīng)接近人工布線的水平;在布局速度方面,布局速度為人工布局速度的300倍。

與其他相似領(lǐng)域的算法對比,本算法可以通過數(shù)學(xué)推導(dǎo)證明其完備性,能夠保證布局布線的正確性。在上述496張圖紙數(shù)據(jù)集中的驗(yàn)證,成功率為100%。相較于RePlAce 99.27%的成功率、RL graph placement method 99.83%的成功率,在大規(guī)模電氣設(shè)計(jì)領(lǐng)域,由于人工核查難度大、耗時長,本方法的所提供的完備性布線方法具有更高的應(yīng)用價值。

在工程實(shí)踐應(yīng)用過程中,本文所述方案工程落地門檻低,神經(jīng)網(wǎng)絡(luò)部分模塊可以在算力有限,樣本有限的情況下較快地收斂,方案整體對算力要求不高。

需要說明的是,在本文的前期調(diào)研中,發(fā)現(xiàn)現(xiàn)階段國內(nèi)船舶電氣圖紙的自動化設(shè)計(jì)領(lǐng)域研究相對較少,大部分研究集中在三維的路徑規(guī)劃領(lǐng)域,與本文所針對技術(shù)問題存在偏差。同時經(jīng)過調(diào)研,國外可能有類似的自動化設(shè)計(jì)技術(shù),但由于涉及到軍事應(yīng)用,并未找到公開的技術(shù)報道和論文。因此本文選擇了人工布線作為主要的技術(shù)對比對象。

4 結(jié)束語

本文的主要貢獻(xiàn)在于提出了一種可應(yīng)用于工程實(shí)踐的艦船電氣圖紙自動布局布線的方法。本文所提出的方法主要存在以下的優(yōu)點(diǎn):①布局布線可靠性高,對于符合條件的連接場景,可以確定地完成布局布線任務(wù)并且不會發(fā)生布線交叉或布線失敗;②資源占用低,充分利用奇異值分解的方法提取特征,降低神經(jīng)網(wǎng)絡(luò)的運(yùn)算復(fù)雜程度;③運(yùn)行速度快,99.1%圖紙可以在10s內(nèi)完成布局和布線任務(wù)。同時本文所提出的方法也為其他復(fù)雜場景下利用神經(jīng)網(wǎng)絡(luò)執(zhí)行優(yōu)化任務(wù)提出了一個可行的方法。

本文所論述的方法雖然已經(jīng)能夠基本實(shí)現(xiàn)自動化的布局布線,但是在空間利用率上與人工布線之間還存在約20%的差距。未來的研究可以聚焦于以下3個方面的改進(jìn):①總結(jié)并使用更為細(xì)致的先驗(yàn)規(guī)則,可以優(yōu)化一部分因?yàn)橐?guī)則粗糙導(dǎo)致的布局短板;②增加神經(jīng)網(wǎng)絡(luò)訓(xùn)練的數(shù)據(jù)樣本數(shù)量,并相應(yīng)的增加神經(jīng)網(wǎng)絡(luò)內(nèi)部隱藏層節(jié)點(diǎn)數(shù)量,提高神經(jīng)網(wǎng)絡(luò)所能學(xué)習(xí)到的特征數(shù)量;③引入其他優(yōu)化方法來對布局參數(shù)進(jìn)一步優(yōu)化以取得局部最優(yōu)解。如果繼續(xù)細(xì)化場景先驗(yàn)規(guī)則,換用更大規(guī)模的神經(jīng)網(wǎng)絡(luò)和樣本數(shù)更多的訓(xùn)練數(shù)據(jù)集的話,進(jìn)一步縮小算法布線和人工布線之間的空間利用率的差別。