面向产品配置设计的改进交互式遗传算法

朱佳栋 苏少辉 陈 昌 刘桂英

杭州电子科技大学机械工程学院，杭州，310018

0 引言

随着大规模定制的飞速发展和新产品的不断涌现，产品配置作为实现大规模定制的一个重要手段，越来越受到企业的关注。产品配置的过程中，企业大多是先分解和分析用户的需求和偏好，再将其转化成为设计参数并作为产品配置的输入，使得用户不能积极地参与到产品配置过程，导致设计出来的产品不能完全满足用户的偏好和需求。

为在产品配置中更快和更有效地获取用户需求，同时降低成本、提高效率，人们将一系列互动进化计算（IEC）方法用于产品定制。TSENG等［1］提出的方法可以在有效缩短时间和降低设计成本的前提下，生产令用户满意的新产品。KIM等［2］、尤海峰［3］开发了一种能在产品定制中使用交互式遗传算法（interactive genetic algorithm，IGA）进行服装设计的系统。

虽然IGA可以有效地解决一些不能由函数来进行直接计算的隐性性能优化问题［4］，但是，IGA在使用中还存在着一个显著的问题——用户疲劳。目前，改善用户疲劳的方法有几种，如缩短评估的时间、减少进化代数、加速收敛算法等［5］。尽管这些方法可以在一定程度上减少用户疲劳，但忽视了不同用户有不同偏好的实际情况，不能有效地用于产品配置。本文根据IGA的特点，对IGA进行改进优化，减少用户疲劳，并在产品配置中可以更有效地获得用户偏好和需求。

1 产品配置

企业想要在激烈的市场竞争中站稳脚跟，就必须满足用户的不同需求，加快产品的创新，生产出能够满足不同用户的产品。因此，大规模定制的概念也随之产生，产品配置作为实现大规模定制的重要手段和方法，是为了在满足用户需求的同时，提高企业的效率，降低成本。

产品配置过程比较复杂，具体的流程如图1所示。产品配置的求解就是利用现有资源，根据用户的偏好需求，配置出符合用户要求的产品［6］。如何快速找出用户偏好的产品组件，并将它们配置成令用户满意的产品，这其中包括了如何处理组件的组装、使用和外观等多方面的问题。

图1 产品配置框架Fig.1 Product configuration framework

通过产品配置可以实现产品的多样化，从而满足不同的用户需求。产品配置是产品创新的一个重用手段，产品配置过程中，可以运用交互式遗传算法对用户需求进行处理。通过对产品的拆分和分类，运用IGA对产品的每个组件或模块进行分类编码，根据每个用户对产品的不同要求，配置出具有相应功能的产品。与此同时，IGA可以应用于配置结果的评价中，运用算法可以得到每个配置的结果，并将这些结果进行反馈。最终对这些配置结果进行评价，得到每个配置结果的适应度，通过适应度来识别配置结果符合用户需求的程度。

2 算法的优化设计

传统IGA的流程如图2所示，用户通过IGA来评价个体的适应值［7］，长时间、大量重复的评价必然会造成用户疲劳，因此需要对其进行优化和改进。首先，从用户对种群的认识角度来看，整个种群是逐渐从简单演变到复杂的，初始阶段的种群相对简单，因此用户获得关于种群的知识也相对简单，可以有效地避免由于用户对种群认知的局限而对进化的种群作出不准确的评价；其次，从产品配置的角度来看，用户也可以像设计师一样逐渐参与到产品配置过程中。

图2 交互式遗传算法流程图Fig.2 Interactive genetic algorithm flow chart

假设fn（x)是用户评估进化个体x的适应度，S为个体x的搜索空间，n表示种群进化的阶段，通过求适应度的最大值来优化算法：

max fn（x）x∈S

2.1 变异个体的改进设计

遗传算法中，变异体现为变量的改变，即把1变成0，或0变成1［8］，例如10位变量的第5位发生了翻转，从0111011010变异为0111111010。

为了让种群在进化的过程当中，在获得优良个体的基础上提高局部的搜索效率，并保持个体的差异性，防止发生提前收敛，对变异算子进行了改进。

种群中个体发生变异的概率

式中，pm为原始变异的概率；L为位串长度。

对于给定的均匀随机变量x∈［0，1］，如果x≤Pm（xi（t）），那么个体就产生变异，反之则不产生变异。

应保证整个种群在传统变异概率的期望次数（nLpm）与新的基因变异概率期望次数相同，即

在第s代种群选择、交叉所产生的结果当中，对选择的个体进行随机变异操作的表达式为

由于Pm(xi(t))≺1，所以相比传统变异方式，新变异方式减少了计算量。为了获得更合适的变异个体，通过引入黄金分割变异来得到最适变异个体［9］：

2.2 遗传操作的改进设计

不同阶段，种群的复杂性不同。与传统的交互式遗传算法相比，通过添加参数N来表示新的进化阶段。虽然算法过程会变得复杂，却更具有方向性。随着演变的不断进行，用户可以对不同阶段的产品配置有更好的了解，也会有更好的评价。

对于遗传操作，随着新模块的出现，将分为两个步骤：

（1）选择在每个种群最后阶段具有高度适应的进化个体，并且由

（2）选择新的基因型模块。新基因型模块的等位基因适应度不固定，因此通过第一步选择的个体来判断用户偏好。系统将搜索相似偏好的用户，并根据步骤（1）的评估值来产生等位基因。

经过上述步骤后，最后一代进化个体与随机选择的基因型模板一一对应，并且相应产生新阶段的第一代群体。

2.3 改进后的算法流程图

由算法流程图（图3）可以看到，相比于传统的IGA，本文所提算法的控制参数是根据不同进化阶段进行设置的；该算法比传统IGA更容易确定终止的进化代数，体现了遗传算法的核心特征。此外，当进入新阶段时，系统将搜索具有相似偏好的用户以实现多用户的协作演进，来减轻用户疲劳，提高局部搜索效率。

图3 改进后的算法流程图Fig.3 Improved algorithm flow chart

3 应用实例

由于不同用户对产品的需求不同，因此以多功能液压千斤顶产品配置为例［10］，对改进后的算法进行应用验证。

3.1 编码

合适的编码对算法运算求解有着比较大的影响，根据用户需求，将多功能千斤顶产品配置的编码大致设定为四个部分：起重质量；起重行程；是否有照明系统；最大举升高度。

根据多功能液压千斤顶的三维图及用户的需求，将配置要求用二进制编码表示出来。起重质量的编码为0000、0001、0010、…；起重行程的编码为0000、0001、…；是否有照明系统的编码为01、10；最大举升高度的编码为00000、00001、00010。每个个体的编码共有15位，多功能千斤顶的基因编码如图4所示。

图4 多功能液压千斤顶基因编码图Fig.4 Multi-functional hydraulic jack gene coding map

3.2 参数设置

为了更好地找到最优个体，每一代的规模既不能太大，也不能太小，太大使搜索空间变大，导致用户容易产生疲劳；太小容易局部收敛。所以本文选择种群大小Ns=5，令同一阶段的交叉概率为0.8，突变概率为0.09；令跨阶段的交叉概率为1，突变概率为0。进化终止条件如下：种群终止的阶段数为5，在终止阶段之前，若有用户满意的个体产生，则用户可终止种群的进化。

3.3 实验

通过上述编码和参数设置，对其产品配置进行实验，通过实验来检验改进IGA是否符合要求。

3.3.1 适应度函数

将用户的评价分为三种：符合（3分）、一般（2分）、不符合（1分），再将每一位用户的评价相加，得出总分数。当总结果相同时，可以通过应用共识度标准来得出适应度［11］。

设共识度为G，则可以得到

3.3.2 实验结果

为了检验所提出的算法，根据用户1的需求偏好：起重质量为3 t，起重行程为250 mm，需要照明系统，最大举升高度为400 mm，得到配置结果，如表1所示。

用户2的需求偏好：起重质量为2 t，起重行程为350 mm，无照明系统，最大举升高度为500 mm，配置结果如表2所示。

表1 用户1配置结果Tab.1 User 1 configuration results

表2 用户2配置结果Tab.2 User 2 configuration results

通过用户评价，对新旧IGA算法的进化代、评估的个体数目、评估的时间以及适应度进行比较，结果数据如表3所示。

表3 传统的交互式遗传算法与新的交互式遗传算法的比较Tab.3 Comparison of traditional interactive genetic algorithm with new interactive genetic algorithm

比较和分析新旧IGA的运算结果，对它们的平均进化代比较可知，传统IGA高于新IGA；其次，对于平均评价的个体数目，传统IGA也高得多。

通过用户评价得出个体适应度，并令X轴表示进化代，Y轴表示进化个体在每一代的适应度，可得到图5所示的结果。

图5 进化个体适应度的比较Fig.5 Evolution of individual fitness

比较两种IGA可知，在产品配置中，新IGA可以大大缩短用户评价产品配置结果的时间，更快配置出令用户满意的产品，减少用户疲劳。随着进化代的不断增加，配置出产品结果的适应度也不断提高，相应的用户满意度也随之提高。将新IGA运用到产品配置中，可以有效地提高企业的生产效率并降低生产成本，增强了企业的市场竞争力。

4 结语

改进的交互式算法可以根据进化阶段，将个体分成不同的遗传单元，通过具有相似偏好的用户来进行多用户协同配置设计，可以较好地减少用户疲劳，还可以快速方便地获得用户要求，配置出令用户满意的产品。但是，所提出的算法进行的实验较少，在后续的研究中，还需要通过更多的实验进行测试和研究，进而完善算法，从而更好地满足不同用户的需求。