基于多目標動態規劃的電熱絲自動布線方法研究

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

關鍵詞：動態規劃算法;多目標優化;自動布線

0 ?引言

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

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

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

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

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

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

2 ?布線結構的特征提取

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

圖1（a）為縱向串聯布線結構，X向的電熱絲排布起主導作用。圖1（b）為橫向分層并聯布線結構，Y向的電熱絲排布起主導作用，且并聯組數為2。

3  多目標動態規劃算法實現電熱絲的自動布線

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

3.1 構建算法模型

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

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

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

式中l為已排布電熱絲的長度，j為發熱膜橫向排布剩余長度，xi表示起主導作用的Y向電熱絲排布數量。只有在既滿足電熱絲排布長度值最大又滿足發熱膜上排布剩余長度最小時得到的xi值才是該動態規劃解決布線問題的最優解。

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

表示每一階段中狀態與狀態變量的對應關系。在排布電熱絲的過程中，每排入一段新的電熱絲就是生成一個新的子問題，也就是動態規劃求解問題時對子階段的劃分。在串聯的布線結構中，狀態的階段劃分為：xi=xi+1

而在并聯的布線結構中，階段劃分體現為：

xi=xi+2n，其中n為并聯組數。

相應的狀態轉移方程為：

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

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

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

2c

l（xi0）

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

3.2 布線算法

電熱絲自動布線算法主要由動態規劃計算得出電熱絲的最大排布量xi與最優的排布間距f，并根據這兩個關鍵參數值表示出布線結構中陣列元對應的坐標形式，最終得到符合要求的布線設計圖。計算步驟如下：

3.2.1 動態規劃求解xi最優解

①根據用戶定義確定電熱絲排布結構，對于串聯或是并聯的排布方式設定相對應的初始值，令xi=xi0。

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

③多目標動態規劃求解最優值關鍵在于求解目標函數T（xi）=max（l（xi））得出Pareto最優解集，再通過目標函數T（xi）=min（j（xi））收斂Pareto解集從而得出布線的最優策略。以橫向分層并聯布線為例，在每個子階段，由

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

④由于是并聯布線，設定

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

mr≤xi≤mr+2n

取xi=mr，由

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

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

3.2.2 以最優策略為依據，實現電熱絲的自動布線

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

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

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

4 ?布線結果分析

4.1 布線效率分析

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

4.2 布線精度分析

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

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

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

5 ?結論

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

參考文獻：

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

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

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

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