一种基于小生境微粒群算法的参数窗口选择方法

李文启^{1, 2}，仇一鸣¹，武广³，汪镭¹，吴启迪¹

 (1. 同济大学 电子与信息工程学院，上海，200092;

2. 亚德诺半导体技术(上海)有限公司，上海，200021;

3. 上海电信科技发展有限公司，上海，200010)

摘要：针对半导体制造工艺参数窗口确定过程中要寻找多个极值点的问题，将小生境微粒群优化算法引入其中，通过构造适当的目标函数并结合工艺控制要求，提出一种参数窗口选择方法。在标准一维和二维多峰函数上的测试结果和实际生产验证结果表明：该算法是一种有效的参数窗口选择方法。

关键词：小生境微粒群；多峰函数寻优；工艺优化；参数窗口选择

中图分类号：TP391          文献标志码：A         文章编号：1672-7207(2011)S1-0159-06

A NichePSO algorithm based on method for parameter window selection

LI Wen-qi^{1, 2}, QIU Yi-ming¹, WU Guang³, WANG Lei¹, WU Qi-di¹

 (1. School of Electronics and Information Engineering, Tongji University, Shanghai 200092, China;

2. Analog Devices (Shanghai) Co. Ltd., Shanghai 200021, China;

3. Shanghai Telecom Science & Technology Development Co.Ltd., Shanghai 200010, China)

Abstract:   To effectively allocate the multiple optima of a multimodal model during parameter window selection in semiconductor manufacture field, NichePSO algorithm with properly constructed fitness function is introduced into the optima seeking process under the conditions of multimodal model and process control requirements. The NichePSO algorithm based on method presented in this paper is proven as an effective method for process parameter window selection by both production validation data and simulation results on standard one-dimensional and two-dimensional multimodal functions.

Key words: NichePSO; multimodal function optimization; process optimization; parameter window selection

在半导体制造过程中，统计学工艺控制方法(Statistical process control, 简称SPC)已经被广泛应用到各种参数的监测和控制中。为了保证工艺参数有足够宽的调整范围和保留足够大的波动裕量，参数规范上限(Upper specification limit, 简称USL，L_US)和规范下限(Lower specification limit, 简称LSL，L_SL)要足够宽且满足一定条件。一般来说，半导体生产工艺控制采用3σ或6σ水平，其中σ为参数采样数据的标准差；过程能力指标C_pk大于1.33或1.67^[1]。若采用3σ水平和C_pk大于1.67，则各指标之间的关系为：

≥1.67

即

              (1)

其中：，；n为数据个数。

任何产品在转入正式生产以前，所有输入参数的L_SL和U_SL都必须在工艺开发过程中确定，并在输出参数达到工艺要求的前提下满足式(1)，因此，参数窗口的宽度W必须大于规范中下限的宽度：

  (2)

在实际生产过程中，在大多数情况下一个输出参数Q由多个输入参数P决定，且Q的范围必须满足工艺要求Q＞R，或Q＜R或R₁＜Q＜R₂。本文以Q＞R为例，则输出参数Q必须满足：

        (3)

显然，输入参数窗口的确定和选择就是找到所有满足式(2)和式(3)的解域，然后从中选取使得所有输入参数都有尽可能大的范围的那个解域，这实质上是寻找一个与Q有关的多峰函数的全局或局部最优的解域问题。在单输入参数的情况下，可能有几段宽窄不同的范围使得输入参数P满足式(2)并且输出参数Q(P)满足式(3)，参数P的窗口W最好在最宽的那段中选取，如图1中的cd部分。通常先找出函数Q和条件R的所有交点，然后根据交点之间的点判断该区域是否满足条件Q＞R，从而得到满足条件的所有区间，然后取最大区间即可。有2个输入参数时，Q(P₁, P₂)为三维曲面，R是高度一定的平面。可以先在输入参数平面上找出Q=R的等高线，然后，根据每个等高线区域里的Q判断该区域是否符合条件Q＞R，这样就找到了所有符合条件的区域，然后从中取X和Y方向都尽可能宽的区域。在大多数实际情况中，并没有明确数学模型用来表示输入和输出参数间的关系，在确定和选择参数窗口时，工程师还只能通过分析实验数据并根据其工程经验来估计和判断，因此，一个实用的参数窗口选择方法显得非常必要。

图1  输入参数、输出参数及工艺要求关系示例

Fig.1  Example of relationship among input parameters, output parameters and process requirement

标准微粒群算法(Particle swarm optimization，PSO)因其算法简单、高效已在单峰优化问题中得到广泛应用，但它只能得到1个极值点，对于具有多个近似或相等极值点的优化问题因为收敛问题而显得无能为力，因此，无法直接用来寻找Q和R的交点。Brits等^[2]提出的小生境微粒群算法(Niching particle swarm optimizer, NichePSO)则可以找出多峰函数的多个极值点，是多峰函数优化问题的有力工具，可以用来寻找Q和R的交点。本文作者把NichePSO引入参数窗口确定和选择中，结合工艺要求并构造适当的目标函数，提出了一种窗口选择方法，并在标准一维和二维多峰函数上进行了测试和生产验证。

1  小生境微粒群算法

1.1  标准微粒群算法

微粒群算法是由Kennedy和Eberhart提出的一种群体智能算法^[3-4]，最早因模拟鸟类寻觅食物过程而诞生。算法中的微粒被看作是没有体积和质量的粒子，粒子通过跟踪本身所找到的最优位置p_best和整个群体目前的最优位置g_best来更新自己的位置。标准微粒群算法的进化方程如下：

  (4)

         (5)

若仅考虑微粒的惯性和自身经验，则速度进化方程为：

    (6)

式中：ω为惯性权重；c₁和c₂为加速常数；r₁和r₂均为介于0~1之间的随机数；下标i表示微粒；k(1≤k≤D)表示微粒的维数；t表示代；p_{ik best}(t)表示第t代微粒i历史最优位置的k维分量，g_{k best}(t)表示种群历史最优位置的k维分量。另外，有V_ik(t+1)∈[-V_max, V_max], x_ik(t+1)∈[-x_max, x_max]，即微粒的位置和飞行速度不可超过其边界。

为了使微粒在开始时有较大的搜索范围，而计算接近结束时有较高的搜索精度，PSO算法通常采用惯性因子线性减小方法。其中惯性因子ω在0. 9~0.4之间随循环次数按式(7)逐渐减小：

           (7)

其中：I_max为算法最大循环次数。若微粒飞出边界，则按下式的变异算法重新随机地更新其位置：

          (8)

式中：β为小于0.5的正常数，r( )为0~1之间的随机数。

1.2  小生境微粒群算法

PSO算法非常适合解决单峰函数的寻优问题，但用于多峰函数时只能得到1个最优解，而且在有多个相等或近似最优值的情况下算法可能不收敛。Brits  等^[2]将小生境技术引入PSO 算法中，提出了NichePSO算法。在该算法中，若某一个微粒的适应值在连续几次迭代过程中变化小于δ，则以它为中心，以它与最近微粒的欧式距离为半径，随机产生一群微粒，形成一个小生境。在迭代过程中，进入小生境微粒群的粒子被吸收。当2个小生境的欧式距离小于其半径之和或小于μ时，就把它们行合并成一个新的小生境，通常参数μ和δ为很小的正数。NichePSO算法能同时得到全局最优值和局部最优值，特别适合多峰函数的优化问题。NichePSO算法的具体步骤为：

(1) 初始化主微粒群微粒的位置和速度。

(2) 主粒子群中粒子的位置和速度在迭代过程中按式(5)和(6)进行更新。

(3) 更新主粒子群中每个粒子的适应度。若某微粒的适应值在连续几次迭代后变化小于δ，则以它为中心，以离它最近微粒之间的距离为半径，随机生成一个子微粒群从而形成一个小生境。

(4) 对于每一个子微粒群：

1) 每个子微粒群中的微粒，按照GCPSO算法迭代^[4-5]。

2) 更新子微粒群中粒子的最优位置。

3) 更新子微粒群的半径。

(5) 如果符合合并条件，将2个小生境进行合并。

(6) 吸收从主微粒群进入小生境的微粒。

(7) 在主微粒群中寻找满足划分小生境标准的粒子，若有，则以该微粒为中心，以离它最近微粒之间的距离为半径建立新的小生境。

(8)重复步骤(2)~(7)，直到满足终止条件为止。

2  基于NichePSO算法的参数窗口选择方法

用NichePSO算法进行参数窗口选择还要有合适的目标函数以指导微粒的进化。由输入和输出参数关系式(3)构造如下目标函数：

               (9)

其中：Abs( )表示取绝对值。显然，Q上的点距离R越近，O_bj越小，Q和R的交点使得式(9)为0。

在一维情况下，基于NichePSO算法的参数窗口选择方法步骤为：

(1) 以式(9)为适应度函数用NichePSO算法求得Q与R的交点。如无交点，返回无交点信息并退出程序；否则转步骤(2)。

(2) 把所求得的交点和边界点一起按从小到大排序，并在每相邻的2点之间任取一点x_j并计算Q(x_j)是否大于R，若是，则保留该区间；否则直接舍弃。

(3) 计算所有保留的区间的宽度W，如果W＞10.02σ，则记为满足条件区间，如不满足条件区间，则返回相关信息并退出程序；否则到步骤4。

(4) 对所有满足条件的区间按宽度W排序，然后按顺序输出每个区间的端点和宽度，并标记宽度最大的区间为参数窗口的推荐区间。

在二维情况下，Q为一曲面，R一般为高度一定的平面。当Q和R相离或相切时，没有交点或者有有限个交点，则可以直接应用NichePSO算法求交点并判定为没有满足条件Q＞R的区域。当时Q和R相交时，交线上有无穷个交点，参数窗口选择方法的步骤为：

(1) 以式(9)为适应度函数，用NichePSO算法求得Q与R的部分交点。若无交点，则返回信息并退出程序；否则到步骤(2)。

(2) 计算所得交点之间距离，若任何一点与其最近一点的距离大于ε，则在以2点间的中心位置为圆心，以2点间距离为半径的区域(如与边界相交则以边界为限)用NichePSO算法再次寻找交点，直到所有交点与其近邻间的距离都小于ε为止。

(3) 按网格模型的等值线算法跟踪并连接所有交点^[6]。

(4) 在步骤(3)中得到的每个封闭区域中任取一点(x, y)并计算是否满足Q(x, y)＞R，若是，则保留该区域；否则舍弃。

(5) 计算所有保留区域在x和y方向的最大宽度W_x和W_y。若W_x＞10.02σ_x且W_y＞10.02σ_y，则记为满足条件区域；若不满足条件区域，则返回相关信息并退出程序。

(6) 输出每个满足条件的区域及其x和y方向的宽度W_ix和W_iy，由工程师根据区域的几何形状选取参数窗口。

在实际情况下，满足条件的区域大多为凸多边形，可以由算法直接标记x和y方向都最宽的区域为参数窗口的选择区域。　

3  算法测试

标准多峰函数F ₁~F₅具备了多峰函数的基本特 征^[4]，因此经常被用于对各种PSO算法的测试，在此也用它们测试基于NichePSO算法的参数窗口选择方法。

            (10)

  (11)

        (12)

           (13)

  (14)

对于F₁~F₄，取主微粒数为40，R=0.2，σ=0.008，最大循环次数为100；对于二维输入函数F₅，取微粒数为300，R=150，σ_x=σ_y=0.1，ε=0.3，最大循环次数为500，然后分别进行15次测试，得到如表1所示结果。微粒适应值的平均值和标准差表明所有微粒最后都收敛到了函数和R的交点附近；并且对于一维函数F₁~F₄，每次测试都找出了所有交点，算法输出结果如表2所示。

F₅是两维多峰函数。图2表明所有微粒最后都收敛到了F₅和R的交线附近。图3所示为算法找到的满足条件的区域，显然区域边界和图4中的交线是吻合的。表3所示为算法输出结果。在实际应用中，算法给出这样的区域边界对于工程师选取参数窗口来说已经足够。显然，对于二维函数F₅，当R取不同的值时，则得到一系列不同值的等高线，这对于参数的选取尤为重要。图5所示为当R取100和150时的2组等值线。用同样方法可以得到其他二维标准多峰函数的任意组等高线，如Quadric函数、Griewank函数、Rastrigin函数和Rosenbrock函数等。

表1  测试结果

Table 1  Test results

表2  F₁~F₄输出结果

Table 2  Outputs of F₁ to F₄

图2  微粒收敛后的位置(F₅)

Fig.2  Final positions of particles (F₅)

图3  F ₅＞150的区域

Fig.3  Areas of F ₅＞150

图4　F₅和R=150的图像

Fig. 4　Images of F₅ and R=150

4  实验分析和生产验证

某电源管理芯片的输出电压V_out与输入电压V_in和环境温度T_emp有关，在确定V_in和T_emp的测试规范范围时，把输入电压V_in和测试温度T_emp进行不同组合后进行15组试验，得到表4所示数据。测试机资源板提供的V_in的标准差为σ_vin=3 mV，测试台的温度标准差为σ_temp=0.6 ℃。对表4中数据插值后，取V_out的理想值R=2.0 V，较优值R₁=1.983 V和R₂=2.017 V，边界值R₃=1.967 V和R₄=2.033 V后，用本文的窗口选择方法对实验数据进行分析，算法输出满足条件区域宽度W_vin=3.2 V和W_emp=65 V，同时给出如图6所示的V_out等高线图。工程师根据等高线图选取输入参数窗口为V_in∈[2.75 V, 4.25 V]，T_emp∈[40 ℃，80 ℃]，如图6中虚线矩形区域所示。在该参数窗口中取V_in=3.5 V和T_emp=60 ℃进行实际生产验证，得到如表5所示的10个批次的良品数据。显然数据分布优于实验数据，这也说明该窗口选择方法是有效的。

图5  R为100和150时F₅的等值线

Fig.5  Contours of F₅ when R is 100 and 150

表3  F₅输出结果

Table 3  Test result summary of F₅

表4　实验组合和数据

Table 4  DOE matrix and data

表5  生产验证数据

Table 5  Production validation data

图6  实验分析结果

Fig.6  DOE analysis results

5  结语

NichePSO算法是解决多峰值函数优化问题的有力工具，为解决在寻找参数窗口过程中多峰函数的寻优问题，将其引入其中，结合具体的工艺要求并构造适当的目标函数，提出了一种参数窗口选择方法。对于一维问题，该方法可直接给出参数口；对于二维问题，则能提供所有满足条件区域的二维图形及其在X和Y方向的宽度。在标准多峰函数上的测试结果和生产验证数据表明该算法是有效的。

参考文献：

[1] Kubiak T M, Benbow D W. The certified six sigma black belt handbook[M]. 2nd ed. Milwaukee WI, USA: ASQ Quality Press, 2009.

[2] Brits R, Engelbrecht A P, van den Bergh F. A niching particle swarm optimizer[C]//Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning. Singapore, 2002: 692-696.

[3] Kennedy J, Eberhart R. Particle swarm optimization[C]// Proceedings of IEEE International Conference on Neural Networks. Perth: 1995: 1942-1948.

[4] 吴启迪, 汪镭. 智能微粒群算法研究及应用[M]. 南京: 江苏教育出版社, 2005: 14-30.
WU Qi-di, WANG Lei. Intelligent particle swarm optimization algorithm research and application[M]: Nanjing: Jiangsu Education Publishing House, 2005: 14-30.

[5] van den Bergh F, Engelbrecht A P. A new locally convergent particle swarm optimizer[C]//Systems, Man and Cybernetics. Hammamet, Tunisia: 2002: 6-11.

[6] 张显全, 刘忠平. 基于格网模型的等高线算法[J]. 计算机科学, 2005, 32(9): 199-201.
ZHANG Xian-quan, LIU Zhong-ping. An algorithm of contour lines based on regular grid[J]. Computer Science, 2005, 32(9): 199-201.

(编辑 陈灿华)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家自然科学基金资助项目(70871091, 61075064, 61034004)；教育部博士点基金资助项目(20100072110038)

通信作者：李文启(1973-)，男，内蒙古赤峰人，博士研究生，从事智能算法，半导体制造工艺优化和智能控制等研究；电话：021-23208266；E-mail: li_wenqi@yahoo.com