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

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

0 ?引言

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

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

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

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

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

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

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

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

圖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  多目標(biāo)動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)電熱絲的自動(dòng)布線

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

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

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

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

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

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

該動(dòng)態(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），進(jìn)而得出求解布線問題的狀態(tài)定義式為：dp[xi] ={l， j}

表示每一階段中狀態(tài)與狀態(tài)變量的對(duì)應(yīng)關(guān)系。在排布電熱絲的過程中，每排入一段新的電熱絲就是生成一個(gè)新的子問題，也就是動(dòng)態(tài)規(guī)劃求解問題時(shí)對(duì)子階段的劃分。在串聯(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，得到對(duì)應(yīng)的j與l的值，并以此作為狀態(tài)能否進(jìn)入下一階段的依據(jù)，所以在遞推的過程中必須有臨界條件加以約束。初始條件由狀態(tài)xi的初始值決定，記為j（xi0），l（xi0）。當(dāng)電熱絲排布量增大，剩余長(zhǎng)度接近于2c時(shí)達(dá)到j(luò)值的邊界狀態(tài);當(dāng)已排布電熱絲的長(zhǎng)度接近甚至等于總長(zhǎng)度L時(shí)，達(dá)到排布長(zhǎng)度l的邊界狀態(tài)，構(gòu)成的狀態(tài)變量約束條件為：

2c

l（xi0）

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

3.2 布線算法

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

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

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

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

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

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

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

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

mr≤xi≤mr+2n

取xi=mr，由

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

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

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

①確定Y向電熱絲排布的陣列元。以橫向布線為例，若電熱絲串聯(lián)排布，則每條Y向電熱絲為陣列元，用 xi與f值表示該條電熱絲兩端點(diǎn)坐標(biāo)并連接成線，記為V1;若為并聯(lián)排布，則每2n條Y向電熱絲為陣列元，以同樣的方法表示出各個(gè)端點(diǎn)坐標(biāo)，連接成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ù)分別對(duì)陣列元V與陣列元H作陣列布線。然而在電熱絲布線的設(shè)計(jì)中并不是每一段電熱絲都能通過提取陣列元的特征進(jìn)行排布。那么對(duì)于無法陣列排布的電熱絲進(jìn)行補(bǔ)全，最終完成電熱絲的自動(dòng)布線。

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

4.1 布線效率分析

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

4.2 布線精度分析

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

與上述方法相比，自動(dòng)布線算法不僅對(duì)每一段電熱絲長(zhǎng)度都有準(zhǔn)確的計(jì)算，更是通過排布階段的劃分模擬了排入每一段電熱絲直到均勻布滿全局的實(shí)際過程。

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

5 ?結(jié)論

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

參考文獻(xiàn)：

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

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

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

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