面向客户定制产品开发的多目标优化算法设计

艾青松 许 强 刘 泉

武汉理工大学，武汉，430070

1 多目标优化进化算法概述

现代制造企业要高效率、低成本地设计和生产令客户满意的产品，就必须能够快速准确地获取客户的个性化需求，以最快的速度加以满足。然而，满足客户的需求并不是唯一的目标，还要考虑企业的生产设备、技术实力、制造能力、人员力量以及生产成本、生产周期和企业管理等其他因素，只有在满足客户需求且自身条件具备的前提下，才能在最短的时间内生产出让客户满意的商品，达到生产企业和客户之间的双赢。因此，基于客户需求信息的产品设计优化是一个多目标优化问题［1］。

近年来，有学者提出了多目标优化进化算法（evolutionary multi－objective optimization，EMO）［2］，该算法作为一种简单有效的全局搜索算法，具有较强的全局收敛能力和较强的鲁棒性，且不需要借助问题的特征信息（如导数等梯度信息）就可以有效求解大量非线性、不可微和多峰值的复杂优化问题。

进化算法是以达尔文的进化论思想为基础，通过模拟自然界生物进化准则逼近问题最优解的一类群体搜索算法［3］。生物进化是通过繁殖、变异、竞争和选择来实现的，而进化算法则主要通过选择 （selection）、重 组 （recombination）和 变 异（mutation）这三种操作来实现优化问题的求解或近似求解。进化算法的基本步骤一般为［3］：①初始化进化算法的停止条件，t＝1；②初始化种群大小，给每个个体赋予坐标值；③计算出每个个体的目标值并存入一个矩阵中；④进行⑤～⑥的循环进化，每轮进化后，t自动加1；⑤对种群进行选择操作，主要选择局部达到优化的个体作为优良个体，保存在外部种群中；⑥重组外部种群和内部种群，让它们进行交配和变异，并选择出优良个体保存在外部种群中；⑦当达到进化停止条件即t达到一定数值后，停止进化算法，取外部种群中的个体作为本次进化算法最终得到的优化个体。

简单地说，进化算法就是通过不断地选择、交配和变异，最终得到一系列优化个体，完成对多目标优化问题的优化工作。进化算法的具体实现方式多样，本文以粒子群优化算法（PSO）［4］为例进行深入研究。

粒子群优化算法将决策空间内的变量看成一个粒子，粒子以一定的速度和方向飞行。在飞行过程中，粒子追寻两个极值来更新自己的位置，即局部最优位置pbest和全局最优位置gbest。其进化方程如下［4］：

式中，i表示第i个粒子；j表示维数，也就是目标数；c1为调节粒子飞向局部最优位置的步长；c2为调节粒子飞向全局最优位置的步长，通常在［0，2］中取值；r1和r2为两个独立的随机数，在［0，1］中随机取值；t为停止条件，即粒子飞行次数，t越大，粒子飞行位置越密集，得到的pbest和gbest将越精确。

由式（1）可以看出，粒子群算法将进化算法的进化思路具体化为粒子的位置和速度变化，通过不断比较和更新pbest和gbest来实现全局优化。

然而，到目前为止多目标优化进化算法尚缺乏系统性研究，一些理论性问题有待进一步探讨。例如，算法只适合于低维目标优化，对高维优化效果很差；有些算法有优越的优化方法，但难以用于工程实际。基于客户需求信息的产品设计与优化也有其自身的特点，它一方面要求在客户给出需求信息后，企业能尽快作出反应，提出合适的方案供客户选择，缩短产品设计时间，提高整个项目效率。另一方面要求我们的算法得出的目标优化值均匀分布，在可行性空间里找到更多的优化解并保证每个解的有效性，避免重复解的出现，方便用户对目标优化值进行比较，最终选择出合适的产品设计方案。而目前的多目标优化进化算法未能很好地解决这些问题。所以，我们还需要对多目标优化进化算法进行研究，提出合适的、高效的优化算法。

基于此，本文对多目标优化进化算法进行研究，针对产品设计与优化过程中所要解决的问题，在现有多目标优化进化算法基础上，从优化算法的执行效率和优化结果的分布两方面进行了必要的改进，并分别进行实验仿真，通过与其他优化算法的对比分析，验证了改进算法的可行性、可靠性和优越性。

2 多目标优化进化算法的效率改进

进化算法通过不断选择和淘汰局部最优解而得到的全局最优解集所对应的最优前沿曲面应该包含所有目标的极值，它对任何一个目标都是公平的。如式（1）所示，粒子的飞行位置xij和速度vij在更新过程中没有偏向任何目标，只是盲目地朝着全局最优解收敛而已。而在实际的生产设计过程中，按照客户和企业的不同要求，目标之间往往是不公平的。假设某个目标对客户很重要，需要着重考虑该目标的优化值，即可以在一定范围内，通过牺牲其他目标来满足该目标的需求，那么，我们得到的“公平”最优前沿曲面就显得资源浪费，从产品开发的实际效率来讲，降低了算法的执行效率。

另外，本文的主要工作是设计一种多目标优化算法，并将其运用在基于客户需求的产品设计中，得出最优化解集，让客户选择其中一个解作为定制产品开发方案。如果得出的最优化解集过大，优化解过多，则一方面加大了客户的选择压力，不利于客户找出最适合的那个解；另一方面，客户还需要大量时间对优化解进行比较，选择出最合适的解，从产品开发效率来看，这也会降低项目设计阶段的效率。

基于以上两个问题，本文提出了侧重度系数概念，根据客户的选择，将每个目标的重要程度分等级，在进化算法运行过程中，通过重要度的比较，优先淘汰一些重要度很低的局部优化解。这样，一方面实现了最优前沿曲面按照客户的需求收敛，提高了算法执行效率；另一方面，也减少了最终得到的优化解个数，提高了客户定制产品设计阶段的效率。

定义1 侧重度系数λ。由目标之间相互重要程度信息转化而来的重要度参数称为侧重度系数。

本文定义的目标侧重度系数如表1所示。

表1 重要度信息衡量标准表

多目标优化问题目前在学术界已经统一成目标函数值极小问题［3-4］，所以，加入目标侧重度系数后，粒子的有效运动范围应该是让侧重度高的目标取值更小、更靠近目标极小值的范围，将该范围取名为侧重范围。如果把整个坐标系分成10等份，分别定义目标A对目标B的侧重度系数为0.90、0.75、0.60和0.50，则它们的侧重范围如图1所示。

图1 4种侧重度系数下的侧重范围

从图1中可以观察到侧重范围的大小，为了对粒子的位置是否合格做相应判断，我们需要计算出侧重范围的边界曲线函数。因为把坐标系等分成10份，每一份就是9°，所以图1中4个侧重范围的夹角分别为18°、45°、72°和90°。通过三角函数计算，得出4种侧重范围的边界曲线函数如表2所示。其中，侧重度系数为0.5即目标之间同等重要时，没有侧重范围，因而也就没有边界曲线。下面阐述加入侧重度系数的进化算法运行思路。

表2 4种侧重范围的边界曲线函数

在进化算法运行步骤⑤后面加入优良个体的再次选择环节，判断每个优良个体的位置是否在侧重范围内。如果在侧重范围内则进入下一步骤；否则淘汰该个体。其他步骤不变，依此循环进化，达到停止条件后即得到最优解。

设侧重区域为Ω，加入侧重度系数λ后的粒子群的优化方程变为

式（2）中，速度vij中有两个随机变量r1和r2存在，所以能让粒子在朝全局最优解收敛时，沿着不同的路径找到更多的pbest，而位置xij则必须限定在侧重范围内，这样收敛区域将变小，收敛效率变高。

我们运用改进算法对ZDT［5］问题进行优化，ZDT问题的数学方程如下：

查阅相关文献得知，ZDT问题的理想最优化曲面如图2所示。

定义目标f1对目标f2的侧重度系数为0.90，设定停止条件为t＝10 000，取c1＝c2＝1，则改进算法的优化仿真图见图3。

图2 测试问题ZDT的理想最优化曲面

图3 λ＝0.90的优化仿真图

为了方便对比分析，本文运用进化算法NSGA－2［1］对ZDT问题进行优化。设定停止条件为t＝10 000，交叉系数Pc为0.8，变异系数Pm为1／30，优化仿真图见图4。

从图3和图4中可以看出，加入侧重度系数后的进化算法能够让粒子有选择地收敛，减少了最优解的个数，提高了客户的选择效率。观察图形可知，改进算法达到了预期目标。

多目标优化领域中一般采用Deb等［5］提出的收敛性指标（convergence metric）对多目标优化算法的优化效果进行评判。为此，本文做了2组对比实验，在目标侧重度系数为0.9的条件下，将改进算法和目前流行的两种进化算法（NSGA－2算法［1］和 SPEA－2算法［6］）进行比较，得到数据如表3所示。

图4 NSGA－2算法对ZDT问题的优化仿真图

表3 不同停止条件下的多目标优化算法运行时间和收敛性指标值

从表3可以看出，当侧重度系数为0.9时，改进算法的运行时间明显短于NSGA－2算法和SPEA－2算法的算法时间，说明改进算法的优化效率更高。并且改进算法的收敛性指标值也小于NSGA－2算法和SPEA－2算法的收敛性指标值，而该指标值越小，说明算法得到的最优化曲面与图2中的理想最优化曲面的距离越近，算法更优越。

以上对多目标优化进化算法优化效率的改进研究表明，通过加入目标侧重度系数，缩小了最优解集，方便客户快速选择出适合项目的最优解。同时，采用改进算法对多目标优化问题进行优化后，得出的最优化粒子与理想的最优化曲面更接近，即优化效果更明显。

3 多目标优化进化算法的解分布改进

采用进化算法对多目标优化问题进行优化的过程中，很容易产生局部优化解过于集中的现象。这些高度集中的局部最优解占据了最优解集中的大量位置，排挤掉了一些偏僻和孤立的优化解，导致最优解多样性缺失，使进化算法陷入局部最优，学术界通常称该现象为早熟。如式（1）中，由于r1和r2两个独立随机数的存在，导致粒子的收敛方向不固定。如果在某一次收敛中得到的局部最优解大量集中，即xij变化不大，那么粒子将陷入局部最优的包围中，很难脱离出来，最终将局部收敛。

采用进化算法对多目标优化问题进行优化后，我们将得到一些接近于理想优化曲面的离散优化点，称它们为目标优化值。客户从众多目标优化值中选择出一个满意的优化值作为产品设计的最优目标值。如果两个目标优化值相隔过近，则它们没有比较的价值，称之为重复目标优化值，必须抛弃其中一个。所以，如何合理选择目标优化值，使它们相互之间有一定的距离，避免重复值的出现，是本文对进化算法改进的另一个出发点。即对于客户来说，要做到大部分目标优化值对他们的选择都有意义。

基于以上两个问题，本文提出了目标间距矩阵概念，根据客户自己的选择，确定每个目标的最小距离。在选择局部最优解和目标优化值时，检验它们之间的间距是否大于或等于最小距离。如果满足条件，则被选中，进行下一步操作；否则，淘汰该值。

定义2 目标间距矩阵。假设一个多目标优化问题中有m个目标需要优化，而这m个目标都有各自的最小距离，即要求第i个目标的目标值之间最小间隔Li个单位。那么，由这m个最小距离组成的矩阵L＝［L1L2L3… Lm］称为目标间距矩阵。

下面详细说明改进算法的执行过程。

假设在进化算法进行优良个体选择时有n个个体a1，a2，a3，…，an比较优秀，可以进入下一代进行交配。此时，我们将这n个个体进行排序，排序的规则是：先比较这n个个体的第一个目标值大小，按照从小到大的顺序排序；然后比较这n个个体的第二个目标值大小，按照从小到大的顺序排列；再比较这n个个体的第三个目标值大小，也按照从小到大的顺序排列。依照这个方法，对这n个个体总共进行m次排序，可以得到一个m行的排序队列，如图5所示。

图5 优良个体的排序序列

然后读取目标间距矩阵中每个目标的最小间距，对上述队列进行检查，如果相邻两个个体之间不满足该排序标准的目标的间距指标，则淘汰两个个体中的后一个个体。通过目标间距矩阵对这m个排序序列进行排查，淘汰一些间距过小的个体。然后再次考察这个序列，如果某个个体出现的次数等于m，则表示该个体胜出，作为优良个体进入下一代种群中；如果某个个体出现的次数小于m，则表示该个体被淘汰，不能作为优良个体进入下一代种群。

在进化算法的执行过程中，每次选择出种群优良个体后，都按照上述方法对优良个体进行再一次的选择，胜出者才能进入下一代种群中进行交配和变异。这样，通过往进化算法中加入目标间距矩阵，并对优良个体反复进行间距排查，能够避免局部最优解的高度集中，保证了最优解的多样性，防止算法早熟。同时，能够让最终得到的最优解集中的解趋于均匀分布，方便客户做对比分析，快速选择出定制产品的开发方案。

在粒子群优化算法中加入目标间距矩阵后的进化方程如下：

在式（4）中，每次粒子更新位置时都加上该目标的最小间距，即将该粒子沿着目标坐标轴平移最小间距的距离，这样来防止粒子位置的高度集中，以免陷入局部最优。

下面采用改进算法对现今流行的测试问题DTLZ［5］进行优化仿真实验，DTLZ数学表达式如下：

定义DTLZ问题的目标间距矩阵为L＝［0.05 0.05 0.05］，k＝3，｜xk｜＝5，停止条件为t＝10 000，取c1＝c2＝1，得到的优化仿真图见图6。

同样，运用进化算法SPEA－2对DTLZ问题进行优化，设定停止条件为t＝10 000，k＝3，｜xk｜＝5，交叉系数Pc为0.6，变异系数Pm为1／30，优化仿真图见图7。

从图6和图7对比来看，改进算法保证了每个粒子之间的距离，淘汰了很多重复解和近似解，使最优化解集中的粒子基本达到了均匀分布。观察图形得出，改进算法达到了预期目标，具有可行性。

图6 改进算法对DTLZ问题的优化仿真图

图7 SPEA－2算法对DTLZ问题的优化仿真图

为了评估多目标优化算法得到的最优解的均匀分布性能，优化领域中一般采用Schott提出的间距指标（Spacing Metric）［7］进行衡量。该指标值越小，代表解分布越均匀。通过改进算法、NSGA－2算法和SPEA－2算法的对比实验，得到的间距指标值如表4所示。

表4 多目标优化算法的间距指标

从表4中的数值来看，改进算法的间距指标值最小，基本接近于0，即解近似于均匀分布，而NSGA－2算法和SPEA－2算法的间距指标值略大，所以，改进算法具有一定的优越性。

通过仿真实验可以看出，改进算法可对最优解集映射到目标空间中粒子的解分布进行调控，即淘汰重叠粒子和近似粒子，使最终得到的粒子均匀分布，提升每个粒子在实际产品开发中的参考价值，从而减小了客户的选择压力，缩短了产品的开发周期，提高了客户的满意度。

4 多目标优化算法流程设计

本研究是针对客户定制产品设计与优化过程中的多目标优化算法展开的，在产品的设计阶段，需要考虑客户的需求信息，将这些信息加以分类、整理和转化，变成直观的数学表达式。同时，还需要考虑企业的实际生产条件，如生产设备、技术能力、人员分配和生产资源等，在进行产品生产时，需要兼顾自身的生产实际和经济效益。图8为所设计的多目标优化算法的流程图。

图8 改进多目标优化算法流程图

仿真实验结果说明了上述改进思路的可行性、可靠性和优越性，这里运用改进算法对ZDT问题进行仿真实验。

定义目标f1对目标f2的侧重度系数为0.75，设定停止条件为t＝10 000，取c1＝c2＝1，设定目标间距矩阵为L＝［0.02 0.02］，改进算法对ZDT问题的优化仿真图见图9。

从图9中可以看出，粒子在侧重度系数作用下进行了局部收敛，提高了优化效率，同时保持了相互之间的间距，保证了最优解的多样性。

定义NSGA－2算法和SPEA－2算法的停止条件为t＝10 000，交叉系数Pc为0.8，变异系数Pm为1／30。将它们分别对ZDT问题进行优化仿真，并计算出相关指标值与改进算法作对比分析，结果如表5所示。

图9 改进算法对ZDT问题的优化仿真图

表5 多目标优化算法对比实验结果

从表5中可以看出，改进算法在优化效率、收敛性和解的分布性方面均优于NSGA－2算法和SPEA－2算法，正好符合本文的研究目标。

5 结语

本文对客户定制产品设计与优化项目中需要用到的多目标优化算法进行了研究，在深入研究多目标优化进化算法的基础上，从优化算法的优化效率和最优解的目标空间分布两个方面对进化算法进行了改进，提高了多目标优化进化算法的运行效率，精简了最优解的数量，降低了客户的选择压力，同时，提高了每个最优解的实际价值，方便客户快速找到满足自身需求的产品设计方案。研究结果对整个产品设计与优化过程具有重要的意义。

［1］Deb K，Pratap A，Agarwal S，et al.A Fast and Elitist Multiobjective Genetic Algorithm：NSGA－II［J］.IEEE Trans.on Evolutionary Computation，2002，6（2）：182－197.

［2］王介生，王金城，王伟.基于粒子群算法的PID参数自整定［J］.控制与决策，2005，20（1）：73－76.

［3］方伟，孙俊，须文波.基于微分进化算子的量子粒子群优化算法及应用［J］.系统仿真学报，2008，20（24）：6740－6744.

［4］许昆，李智勇.改进的量子粒子群多目标优化算法［J］.计算机工程与设计，2009，30（1）：164－167.

［5］Deb K，Jain S.Running Performance Metrics for Evolutionary Multi－objective Optimization.Technical Report，No.2002004［R］.Kanpur：Indian Institute of Technology Kanpur，2002.

［6］Zitzler E，Laumanns M，Thiele L.SPEA2：Improving the Strength Pareto Evolutionary Algorithm［C］／／Giannakoglou K，Tsahalis D T，Papailiou K D，et al，eds.Evolutionary Methods for Design，Optimization and Control with Applications to Industrial Problems.Berlin：Springer－Verlag，2002：95－100.

［7］Sun Jun，Feng Bin，Xu Wenbo.A Global Search Strategy of Quantum－behaved Particle Swarm Optimization［C］／／IEEE Conference on Cybernetics and Intelligent Systems.Piscataway，NJ：IEEE Press，2004：111－116.