基于多目标动态规划的电热丝自动布线方法研究

摘要：针对柔性薄膜加热器电热丝布线过程繁琐，研究一种自动布线方法，能基于动态规划算法划分电热丝的排布阶段并对每一阶段做出布线决策，通过多目标优化获得电热丝在指定区域中的最大排布量及最优排布间隙，生成最优布线策略，并实现布线图的自动绘制。该布线方法能有效提高布线效率，降低布线误差，保证布线质量。

关键词：动态规划算法;多目标优化;自动布线

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-），女，江苏南京人，硕士，中国航空工业集团公司金城南京机电液压工程研究中心，从事主管工艺。