摘要：針對柔性薄膜加熱器電熱絲布線過程繁瑣，研究一種自動布線方法，能基于動態(tài)規(guī)劃算法劃分電熱絲的排布階段并對每一階段做出布線決策，通過多目標優(yōu)化獲得電熱絲在指定區(qū)域中的最大排布量及最優(yōu)排布間隙，生成最優(yōu)布線策略，并實現(xiàn)布線圖的自動繪制。該布線方法能有效提高布線效率，降低布線誤差，保證布線質(zhì)量。

關(guān)鍵詞：動態(tài)規(guī)劃算法;多目標優(yōu)化;自動布線

0 ?引言

柔性薄膜加熱器可以為半導(dǎo)體設(shè)備制造廠和半導(dǎo)體集成電路元器件生產(chǎn)廠提供管道外圍加熱。該類加熱器由發(fā)熱膜、電極、絕緣層和保溫層組成。其中發(fā)熱膜中的電熱絲是加熱器的核心，而電熱絲的排布是影響加熱器發(fā)熱作用的重要因素之一。

當前，設(shè)計員通過計算每片發(fā)熱膜上的電熱絲阻值、寬度，經(jīng)多次嘗試與修改才可完成電熱絲布線并繪制符合要求的設(shè)計圖。在參數(shù)不同但布線結(jié)構(gòu)相同的情況下，重復(fù)勞動的布線工作還會耗費過多時間與人力，也無法保證每片發(fā)熱膜上電熱絲總阻值與設(shè)計值之間的誤差最小化，直接影響加熱器的工作效率。

管路中用于直管外圍加熱的柔性薄膜加熱器需求量最大，且發(fā)熱膜形狀最規(guī)整，所以本文以直管外圍的加熱器設(shè)計為對象，針對發(fā)熱膜中電熱絲的布線效率以及布線質(zhì)量，研究基于多目標動態(tài)規(guī)劃算法實現(xiàn)電熱絲自動布線的方法。

1 ?電熱絲布線的問題描述

電熱絲的布線屬于布局問題，電熱絲的布線除要求布局最優(yōu)化外更注重管件整體加熱的均勻性，其問題可描述為在一個確定的區(qū)域中均勻地排布電熱絲，使其發(fā)熱效率無限逼近設(shè)計值時獲得最優(yōu)布線結(jié)果。用數(shù)學模型表達為求解n元向量（x1，x2，…xn），滿足

其中n元向量表示電熱絲的排布量及排布間隙，r為電熱絲的電阻值，R為該區(qū)域電阻的總設(shè)計值。

2 ?布線結(jié)構(gòu)的特征提取

電熱絲在該柔性加熱器中的布線形式分為橫縱向布線、串并聯(lián)布線、分層或單層布線及其組合布線方式。對于結(jié)構(gòu)特征的提取是確定自動布線算法模型的第一步。

圖1（a）為縱向串聯(lián)布線結(jié)構(gòu)，X向的電熱絲排布起主導(dǎo)作用。圖1（b）為橫向分層并聯(lián)布線結(jié)構(gòu)，Y向的電熱絲排布起主導(dǎo)作用，且并聯(lián)組數(shù)為2。

3  多目標動態(tài)規(guī)劃算法實現(xiàn)電熱絲的自動布線

動態(tài)規(guī)劃算法最優(yōu)化的原理是通過將待解的問題拆分為若干子問題，并按順序求解子階段，從而得到最優(yōu)化的決策[1]。如倪宏坤等[2]基于動態(tài)規(guī)劃的原理采用分支界限算法解決了關(guān)鍵輸電斷面快速識別的問題。本文依據(jù)實際的布線要求，結(jié)合動態(tài)規(guī)劃的基本思想求解多目標最優(yōu)化的電熱絲布線方法。

3.1 構(gòu)建算法模型

在加熱器的設(shè)計中，將整個管件外圍根據(jù)溫度場的不同分割成數(shù)個相互連接的區(qū)域，對每片區(qū)域有其相對應(yīng)的設(shè)計要求，其用戶參數(shù)的定義為：發(fā)熱膜長度a、發(fā)熱膜寬度b、邊距c、并聯(lián)組數(shù)n、電壓v、功率p、電阻率ρ、線寬系數(shù)d、薄膜厚度t、面積占比e。

依據(jù)P=得出該區(qū)域內(nèi)設(shè)計要求的電阻值R，再根據(jù)電阻定律和已知的用戶參數(shù)確定該區(qū)域內(nèi)排布電熱絲的總長度L及電熱絲的寬度W。其數(shù)學表達式為：

依據(jù)提取的布線結(jié)構(gòu)特征，若Y向的電熱絲排布起主導(dǎo)作用，暫且忽略X向的電熱絲排布。每排入一段Y向電熱絲，對應(yīng)著電熱絲排布長度以及X向剩余排布長度的變化。傳統(tǒng)的單目標動態(tài)優(yōu)化無法解決此問題，需采用多目標優(yōu)化的方式最大程度降低誤差值。其目標函數(shù)表示為T（xi）={max（l（xi）），min（j（xi））}

式中l(wèi)為已排布電熱絲的長度，j為發(fā)熱膜橫向排布剩余長度，xi表示起主導(dǎo)作用的Y向電熱絲排布數(shù)量。只有在既滿足電熱絲排布長度值最大又滿足發(fā)熱膜上排布剩余長度最小時得到的xi值才是該動態(tài)規(guī)劃解決布線問題的最優(yōu)解。

該動態(tài)規(guī)劃算法的狀態(tài)xi由排布結(jié)構(gòu)決定。若為橫向布線，則狀態(tài)xi表示布局中Y向電熱絲的數(shù)量;若為縱向布線，則表示X向電熱絲的排布數(shù)量。狀態(tài)變量定義為l以及j，其函數(shù)模型為：dfs（int xi，double l，double j），進而得出求解布線問題的狀態(tài)定義式為：dp[xi] ={l， j}

表示每一階段中狀態(tài)與狀態(tài)變量的對應(yīng)關(guān)系。在排布電熱絲的過程中，每排入一段新的電熱絲就是生成一個新的子問題，也就是動態(tài)規(guī)劃求解問題時對子階段的劃分。在串聯(lián)的布線結(jié)構(gòu)中，狀態(tài)的階段劃分為：xi=xi+1

而在并聯(lián)的布線結(jié)構(gòu)中，階段劃分體現(xiàn)為：

xi=xi+2n，其中n為并聯(lián)組數(shù)。

相應(yīng)的狀態(tài)轉(zhuǎn)移方程為：

dp[xi]=max（l[xi+1]，l[xi]）

dp[xi]=min（j[xi+2n]，j[xi]）

此方程用于轉(zhuǎn)換狀態(tài)xi，得到對應(yīng)的j與l的值，并以此作為狀態(tài)能否進入下一階段的依據(jù)，所以在遞推的過程中必須有臨界條件加以約束。初始條件由狀態(tài)xi的初始值決定，記為j（xi0），l（xi0）。當電熱絲排布量增大，剩余長度接近于2c時達到j(luò)值的邊界狀態(tài);當已排布電熱絲的長度接近甚至等于總長度L時，達到排布長度l的邊界狀態(tài)，構(gòu)成的狀態(tài)變量約束條件為：

2c

l（xi0）

根據(jù)該約束條件并在滿足無后效性的要求下對劃分的每一個子階段做出決策：加入進行排布或被舍去。實現(xiàn)自動布線的關(guān)鍵點就是在決策集合中取得最優(yōu)策略，即取得最優(yōu)解xi。此外，排布間距值f（相鄰兩條電熱絲的中心距）隨xi值變化而變化，f值對于確定結(jié)構(gòu)特征中的陣列元有重要意義，取得狀態(tài)xi值的最優(yōu)解時，要同時取得f值的最優(yōu)解。

3.2 布線算法

電熱絲自動布線算法主要由動態(tài)規(guī)劃計算得出電熱絲的最大排布量xi與最優(yōu)的排布間距f，并根據(jù)這兩個關(guān)鍵參數(shù)值表示出布線結(jié)構(gòu)中陣列元對應(yīng)的坐標形式，最終得到符合要求的布線設(shè)計圖。計算步驟如下：

3.2.1 動態(tài)規(guī)劃求解xi最優(yōu)解

①根據(jù)用戶定義確定電熱絲排布結(jié)構(gòu)，對于串聯(lián)或是并聯(lián)的排布方式設(shè)定相對應(yīng)的初始值，令xi=xi0。

②計算當前階段xi值下對應(yīng)的排布間距f值。由于電熱絲均勻布滿全局，則f=（a-2c-W）/（xi-1）。

③多目標動態(tài)規(guī)劃求解最優(yōu)值關(guān)鍵在于求解目標函數(shù)T（xi）=max（l（xi））得出Pareto最優(yōu)解集，再通過目標函數(shù)T（xi）=min（j（xi））收斂Pareto解集從而得出布線的最優(yōu)策略。以橫向分層并聯(lián)布線為例，在每個子階段，由

得出已排布的電熱絲長度l，若滿足l不大于總長度L的邊界條件，將其值與對應(yīng)的xi值存入數(shù)組longarr{}中，并以xi=xi+1的方式轉(zhuǎn)移至下一子階段進行迭代計算，直到l>L時停止。此時，從數(shù)組longarr{}中獲取l為最大時對應(yīng)的排布數(shù)量xir值。

④由于是并聯(lián)布線，設(shè)定

則滿足目標函數(shù)T（xi）=max（l（xi）的Pareto解集設(shè)為：

mr≤xi≤mr+2n

取xi=mr，由

計算得出當前發(fā)熱膜橫向剩余長度j值，在滿足j>2c的條件下，將其值與對應(yīng)的xi值存入數(shù)組restarr{}中，并以xi=xi+2n轉(zhuǎn)移至下一階段進行迭代計算，直到j(luò)≤2c時停止。

⑤從數(shù)組restarr{}中獲取j最小時對應(yīng)的排布數(shù)量xi值，即可得到最大排布量xi及對應(yīng)的排布間距最優(yōu)值f，生成排布的最優(yōu)策略。

3.2.2 以最優(yōu)策略為依據(jù)，實現(xiàn)電熱絲的自動布線

①確定Y向電熱絲排布的陣列元。以橫向布線為例，若電熱絲串聯(lián)排布，則每條Y向電熱絲為陣列元，用 xi與f值表示該條電熱絲兩端點坐標并連接成線，記為V1;若為并聯(lián)排布，則每2n條Y向電熱絲為陣列元，以同樣的方法表示出各個端點坐標，連接成2n條線段記為V2。

②確定X向電熱絲排布的陣列元。若為串聯(lián)排布，電熱絲呈“幾”字形排布，每條Y向電熱絲與其左右相鄰電熱絲之間構(gòu)成兩條上下平行的水平線段，按位置的不同將其分別記為陣列元H1，H2;若為并聯(lián)排布，以相同方法構(gòu)成上下各n條水平線段，記為H3，H4。

③由電熱絲最大排布量xi與最優(yōu)排布間距f確定陣列數(shù)與陣列間距，調(diào)用陣列函數(shù)分別對陣列元V與陣列元H作陣列布線。然而在電熱絲布線的設(shè)計中并不是每一段電熱絲都能通過提取陣列元的特征進行排布。那么對于無法陣列排布的電熱絲進行補全，最終完成電熱絲的自動布線。

4 ?布線結(jié)果分析

4.1 布線效率分析

傳統(tǒng)的人工布線方法步驟繁瑣且耗時過長，其中繪制布線圖耗費時長占比最重。本文采用的自動布線方法只需用戶輸入相應(yīng)參數(shù)便能以最優(yōu)策略自動布線并出圖，整個出圖過程只需十數(shù)秒時間。另外，該布線算法已形成完整框架，對于不同結(jié)構(gòu)，不同參數(shù)的布線要求無需重復(fù)設(shè)計，顯著提升電熱絲布線效率。

4.2 布線精度分析

當前設(shè)計人員在橫向分層并聯(lián)布線時，忽略X向電熱絲長度，并假設(shè)Y向電熱絲長度li皆為li=b-2c的情況下估算得出排布量i。顯然，此法會導(dǎo)致布線結(jié)果中電熱絲長度l與設(shè)計要求總長度L之間的差值增大，導(dǎo)致電阻值誤差增大，影響加熱器的發(fā)熱效果。

與上述方法相比，自動布線算法不僅對每一段電熱絲長度都有準確的計算，更是通過排布階段的劃分模擬了排入每一段電熱絲直到均勻布滿全局的實際過程。

根據(jù)表1中的用戶參數(shù)，運用自動布線算法對于橫向串聯(lián)、縱向串聯(lián)、橫向分層并聯(lián)以及橫向單層并聯(lián)四種結(jié)構(gòu)的布線結(jié)果如表2所示。從表中可知各布線結(jié)果中電熱絲實際排布長度l與對應(yīng)設(shè)計長度L值的相對誤差，進而得出該算法所得結(jié)果的平均相對誤差§為：§=1.575%。

5 ?結(jié)論

本文針對柔性薄膜加熱器中電熱絲布線過程繁瑣且重復(fù)勞動耗時長的問題，提出了基于多目標動態(tài)規(guī)劃的自動布線方法。該方法應(yīng)對不同的布線結(jié)構(gòu)，運用動態(tài)規(guī)劃的思想，通過多目標優(yōu)化獲取到排布的最優(yōu)解，并以此為依據(jù)自動繪制布線設(shè)計圖，進而實現(xiàn)了電熱絲的自動布線。該方法不僅為設(shè)計人員省去了重復(fù)繁瑣的繪圖過程，大幅度提高了布線效率，更降低了布線誤差，有效保證了布線的質(zhì)量。

參考文獻：

[1]廖慧芬，邵小兵.動態(tài)規(guī)劃算法的原理及應(yīng)用[J].中國科技信息，2005（21）：42.

[2]倪宏坤，徐玉琴.基于動態(tài)規(guī)劃原理分支界限算法的關(guān)鍵輸電斷面搜索方法[J].華北電力大學學報（自然科學版），2009，36（04）：11-15.

[3]常遠.基于動態(tài)規(guī)劃的并聯(lián)混合動力動車組能量管理策略研究[J].內(nèi)燃機與配件，2019（08）：114-119.

作者簡介：丁嬙（1993-），女，江蘇南京人，碩士，中國航空工業(yè)集團公司金城南京機電液壓工程研究中心，從事主管工藝。