面向客户个性化需求的交互式遗传算法

窦润亮， 郭均鹏， 田祥龙， 宗 超

(天津大学管理与经济学部， 天津 300072)

面向客户个性化需求的交互式遗传算法

窦润亮， 郭均鹏， 田祥龙， 宗 超

(天津大学管理与经济学部， 天津 300072)

针对交互式遗传算法(IGA)中的评价噪声问题，提出犹豫度的概念，建立犹豫度调整机制，并使用删除策略和修改策略来处理形成初始种群以及交叉、变异过程中产生的约束不满足个体.通过对汽车操控台的概念设计问题进行建模，建立人性化交互界面用以验证本论文提出的方法体系的先进性和合理性.实验表明，此求解算法能够有效的降低评价噪声，加速收敛，降低疲劳度，提高结果的满意度.

交互式遗传算法； 犹豫度； 评价噪声； 约束处理； 疲劳度

0 引 言

产品市场的竞争，使得产品设计与生产企业对客户个性化需求的重视程度日益提高，面向客户个性化需求的产品配置需要对客户的需求进行快速、准确响应.如何快速获取客户实时需求，建立产品优化设计的用户满意模型，并将之转换成相应产品的功能需求，是进行产品配置的首要环节[1-2].

遗传算法被广泛认为是解决此类问题最有效的方法之一.由于遗传算法不要求被优化的目标函数连续和可微，并且能在容许的时间内找到大规模优化问题的满意解，自提出以来便引起了国内外众多学者的广泛关注，在算法的应用和理论研究方面，国内诸多学者也进行深入研究，取得了丰硕的研究成果.Ozcelik等人提出一种遗传算法在工业路线设计中的应用，指出单元构成的重要性[3].Huang等人提出一种基于遗传算法的具有共性的多层次产品族设计优化问题，研制了一种多目标遗传算法的同步产品变异设计[4].此外，遗传算法与其他智能算法结合，拓展了遗传算法的适用范围.如遗传算法与人工神经网络结合[5]，邹昊飞等人基于两阶段优化算法的遗传算法人工神经网络，并建立相应的预测模型进行实证研究，结果表明该模型能较大提高神经网络的全局收敛能力和收敛速度[6].遗传算法与粒子群[7]、蚁群[8]等优化算法的结合等.宋莉波等人针对柔性工作车间调度问题，提出了一种基于混合遗传算法的求解方案，并在遗传进化的过程中增加基于混沌序列的邻域搜索功能, 以提高遗传算法的执行效率[9].

客户需求中技术类和非技术类需求普遍共存，而非技术类需求在算法上一般体现为隐性指标，对其响应需要与客户的频繁交互，传统的遗传算法已经对于解决隐性指标的优化问题不再适用，从而本文引入交互式遗传算法(interactive genetic algorithm，IGA).交互式遗传算法是一种将人的主观评价值作为个体适应度值的进化算法.特点是融入了人的智能，其个体的适应度值由用户指定而非通过函数，因而非常适合解决含隐式性能指标的优化问题，现已广泛应用于计算机图形学[10-11]、工业设计[12-14]、音乐创作[15]、自动控制与机器人技术[16]等多个领域.然而IGA也存在限制，由于用户通过人机界面指定个体的适应度，其频繁的交互易引起用户疲劳.因此，如何降低IGA中的用户疲劳度便成为重点的研究方向.降低IGA用户疲劳度的研究中，近年来的重点多集中在如何改进进化策略、提高适应值估算的效果[17-19]，但是从降低评价误差入手的研究目前仍然较少.Branke和Beyer等人认为普通遗传算法中的噪声主要产生于三方面: 决策变量，适应值的计算和优化问题本身[20-21]，而Jin和Di等人认为噪声对进化过程的影响表现为：学习效率低，难以保留学习的信息，决策变量空间的利用能力受限，种群适应度值未随进化代数的增加而提高[22,23].但是以上文献并没有注重探究用户在进化过程中评价的心理过程，以及用户的心理变化对于进化噪声的影响.考虑到交互式遗传算法是由人来评价个体的适应值，因此人的心理变化必然会对进化过程和结果产生影响，尤其是犹豫的感觉.一般优化进化算法中的噪声补偿策略主要有3种[21-23]:增大种群规模，增加采样次数,取采样的平均值，改进遗传算子.因此，重复采样技术提高个体适应度值是一般遗传算法噪声补偿的选择策略.而在交互式遗传算法中，大量重复地采样评价，必然造成人的疲劳，从而影响到进度的效果.因而上述补偿策略不适合于交互式遗传算法，必须针对其算法特点和噪声的特性研究降噪策略.针对于此，本文从研究用户的评价心理过程出发，提出了犹豫度概念，建立了犹豫度调整机制来降低噪声.

在进行仿真实验时，本文选择汽车操控台的概念设计来进行实验.汽车的操控台形式多样，结构比较复杂，用户在评价时候通常带有很高的主观性，这是能突出交互式遗传算法强大优势的应用领域，而且目前的汽车产品大部分还是处在大批量生产阶段，没有成熟的产品定制模式，因此本文试图通过此方法，使得用户能够参与到汽车产品的设计中，同时相对于制造商，能充分利用企业自身的设计资源，达到大规模定制的目的.汽车操控台的复杂性特点，导致配置算法求解时，在形成染色体的过程中很容易产生不满足约束的个体，本文采用两种约束处理策略——删除策略和修改策略来解决约束问题.通过建立了汽车操控台的设计系统，验证此方法能够降低评价误差，降低用户疲劳度，提高算法结果的满意度.

1 相关理论基础

交互式遗传算法求解传统步骤如下：首先对需要优化的问题的所有参数进行编码，一个字符串代表一个染色体(每个染色体都表示一个可行解)，所有染色体的集合称为种群；然后以随机方式产生一群初始解，通过人来赋予个体适应值，根据适应值大小使用遗传算子(选择、交叉、变异)对本代中的染色体进行遗传进化操作，进入下一代种群，再由人来评价个体适应值，如此循环进化，直至得到满意解或者强制结束.

传统的交互式遗传算法如图1所示.

1.1 犹豫度的概念

交互式遗传算法区别于普通遗传算法的最大特点就是其个体的适应值不是由适应值函数求得，而是来自人的评价，因此，由于人的主观因素和疲劳度的增加，对于相同的个体在不同的评价阶段可能会有不同的适应值，即偏差，或噪声.

按照交互时间的长短，评价过程可以分为认知阶段、中间阶段以及疲劳阶段3个阶段[18].

在用户评价的认知阶段，由于对于目标个体还不明确或者是只对于部分属性明确，会使得评价结果与个体的真实适应值产生噪声.而此时噪声产生的主要原因是用户对于理想个体还不明确，而这种对于理想个体“迷茫”的感觉体现在用户心理就是“犹豫感”.因此，用户在评价个体时，会产生不同程度的犹豫感.当用户的理想个体还未明确，用户的犹豫感比较强；而当用户的理想个体明确之后，用户的犹豫感就会比较弱.对于第t代第i个个体xi(t)的犹豫感的强烈程度可用犹豫度hi(t)来表示

(1)

图1 传统IGA的算法流程

Fig. 1 Traditional IGA process

1.2 犹豫度调整机制的原理

将待解决的问题描述为如下形式

maxf(x)

s.t.x∈S

f(x)即是用户对于个体x评价的适应值，S是个体x的搜索空间.当产生噪声时，用户赋予个体xi的适应值f(xi)与其真实的适应值f’(xi)会有偏差，f(xi)≠f’(xi).对于偏差，当f(xi)f’(xi)时，称f+=f(xi)-f’(xi)为正偏差.正偏差f+和负偏差f-构成噪声的主要内容，因此，如何减少正负偏差就成为了降低噪声的关键之一.

(2)

其中d(xi(t),xj)的实际含义是两个个体xi(t)与xj之间的距离，即基因片段相似的程度.然后，应用此距离，得出与犹豫个体xi(t)距离较近的个体的集合

L(xi(t))={xj|d(xi(t),xj)≤d0,xj∈Ne}

(3)

其中Ne是已评价过的个体的集合，d0是反映两个体之间距离的临界值，预先设定.通过计算该集合中个体的平均适应值

驱动形式 ..................................................................后置后驱

(4)

来得出犹豫个体xi(t)的近似真实适应值f’(xi(t))，最后，利用此值调整用户赋予个体xi(t)的适应值

f(xi(t))=f′(xi(t))

通过此过程，可以找出用户产生犹豫的个体，并且通过计算与其相似个体的平均适应值来得出其近似的真实适应值f’(xi(t)), 然后调整其适应值，从而减少正负偏差，加速算法的进行，减少用户疲劳度.

本文以客户对于理想个体是否明确作为认识阶段的分界点：当客户对于理想个体不明确时，还处在认识阶段，此时在用户评价个体时应用犹豫度调整机制；当客户对于理想个体明确了之后，便进入稳定阶段，此时不再应用犹豫度调整机制.

1.3 约束不满足个体的处理

针对复杂产品特性，应用交互式遗传算法进行配置求解时，很容易由于不满足约束条件而产生不合理的个体，因此，约束不满足问题也是困扰交互式遗传算法的一个大问题.针对于此，本文应用两种处理策略：删除策略和修改策略.如图2所示.

1)删除策略是指将不满足约束的个体直接删除，不在交互界面中显示.由于初始种群的生成是从大规模的种群中筛选出来的，因此大规模初始种群生成时可以使用删除策略，将不满足约束的个体直接删除，而不会使得优秀基因减少.而进化阶段由于交互界面的限制，种群较小，如果将不满足约束的个体直接删除，可能会是某些优秀的基因消失，不利于进化.因此，删除策略只在生成初始种群时应用.

2)修改策略是指在进化过程中，对于交叉、变异形成的不满足约束的个体，将其数量控制在一定范围之内(但不在交互界面中显示，其适应度默认为平均值)，对于超出范围的个体进行修改.之所以将不满足约束的个体保留一定数量，是因为不满足约束的个体可能包含有具有优势的基因.修改是指根据事先建立好的约束数据库中储存的各种约束，按照IF-THEN规则将其不满足约束的部件或模块改成满足约束的部件或模块.修改策略应用在种群的进化过程中.

图2 约束不满足个体的处理

2 基于犹豫度调整机制的IGA

结合犹豫度调整机制和约束不满足个体的处理方法，本文对于传统的IGA进行了一些改进，提出基于犹豫度调整机制的IGA.

2.1 算法步骤

1)在初始阶段，如果客户目标个体的某些属性已有确定的偏好，则系统会询问并确定其偏好，从而锁定基因类型，加速收敛.

2)初始种群的生成.针对复杂产品，如果种群规模较小，很容易陷入局部收敛，而若种群规模较大，则会大大增加客户的疲劳度.本文提出一种折中的方法：随机生成一个较大规模的种群，并对其进行交互评价，然后按适应值排序，取适应值高的前n个个体，并且在其余个体中随机选出m个个体，共同组成初始种群.这个步骤的原理是如果只选择适应值高的个体，可能会造成存在于适应值低的个体中的优秀基因流失，而这个步骤可以有效的解决这个问题.

3)将遗传进化分为两阶段：目标个体不明确阶段和目标个体明确阶段.在目标个体不明确阶段，对于客户的交互评价实施犹豫度调整机制，减少认识阶段的噪声，从而加速收敛.在目标个体明确阶段，不再实施犹豫度调整机制，并提供手动配置功能，方便用户自主配置.

4)对于约束不满足的个体处理，在初始种群的生成阶段，实施删除策略；对于进化阶段的新种群的生成，实施修改策略.

2.2 算法流程图

如图3所示.

图3 基于犹豫度调整机制的IGA流程图

Fig.3 IGA process based on hesitation degree adjusting mechanism

3 仿真实验

3.1 系统的建立

本文建立了汽车操控台的概念设计系统，以此来验证算法的性能.

1)编码模式.本系统用二进制来对操控台进行编码.如图4所示，一条染色体(即一个产品)总体分为6个部分，分别对应操控台的五大模块和颜色模块.每一部分又进一步分为若干基因，每一个基因的二进制代码均代表一个具体的实例.图4中中控台的编码001001001即代表“第一类GPS导航、DVD音响系统、6寸液晶显示屏”的实例.

图4 编码模式

Fig.4 Coding pattern

2)约束的处理.对于操控台的约束本文采用IF-THEN的结构来表示，如表1所示.在产生初始种群的过程中，如果所产生的个体不满足约束，那么直接删除此个体，此即删除策略；在进化过程中如果所产生的个体不满足约束，那么保留一定数量的不满足约束个体，以免优秀基因流失，对于超出数量的不满足约束个体按照约束规则进行修改，修改方法为用满足约束的基因替换不满足约束的基因.

表1 操控台的部分约束

3)参数设置.初始大规模种群数量N0=45，初始种群中的n=6，m=3考虑到用户评价每一代的时间和显示器大小的限制，将每一代种群数量定为ng=9，截止进化代数G0=25，交叉与变异概率分别为0.8和0.07，约束修改策略中保留不满足约束个体数量为2，适应值取0到100的整数.犹豫度调整机制中合适的阀值h0和d0通过实验来确定：在不同的h0和d0的数值下，系统独立运行10次并取平均值，运行情况如表2和表3所示，可以看出当d0=0.7和h0=1.1时系统运行的时间最短，评价的代数也最少，然后通过分析其收敛性，如图5和图6，其中，纵坐标fitness是指每一代种群的平均适应值，横坐标generation指的是系统运行的代数，四条曲线分别代表不同h0和d0取值下的每代平均适应值的走势，可以看到当d0=0.7和h0=1.1时收敛性也最好，因此可以确定h0和d0取值分别为1.1和0.7.

表2 不同h0的系统运行情况(d0=0.7)

图5 不同取值的h0对系统的收敛性的影响

d0测试次数平均代数平均评价个体数平均运行时间0．41023．8214．286min52s0．51022．3200．779min18s0．61020．1180．972min25s0．71018．7168．369min46s0．81019．9179．171min12s0．91021．2190．876min08s

图6 不同取值的d0对系统收敛性的影响

4)交互界面.本系统使用人性化的交互界面，提高客户评价效率的同时减少疲劳度.如图7所示，每一代种群数量为9，且同时显示“目前最优个体”和“上代最优个体”两个个体以供参考.在交互过程中，当客户对于理想个体明确之后，可以点击“目标个体明确”按钮来终止犹豫度调整机制.

图7 操控台定制设计系统交互界面

Fig.7 Console customization system interface

3.2 对比实验

为了研究此方法对于IGA的贡献，将传统IGA(TIGA)与基于犹豫度调整机制的IGA(HAM-IGA)对比，独立运行20次.这两种方法的运行性能如表4所示，HAM-IGA的平均进化代数只占TIGA的77.6%，运行时间缩短了21.5%，达到了加速收敛的效果，从而减少了用户的疲劳度.

此后，进行了两种方法的收敛性分析，如图8所示，其中，纵坐标fitness指的是每一代种群的平均适应值，横坐标generation指的是系统运行的代数，两条曲线分别代表TIGA和HAM-IGA这两种方法下的每代平均适应值的走势.从中可以看出，HAM-IGA比TIGA收敛性能要好，尤其是在前期(大概8,9代)效果非常明显，通过分析HAM的应用对于系统运行的影响，如表5所示，发现平均在8.3代之前，应用HAM-IGA的系统都在使用HAM，因此证明HAM确实能够有效降低评价噪声，从而加速收敛.此外，应用HAM的阶段是用户对于目标个体不明确阶段，而停止使用HAM是在用户对于目标个体明确阶段，这两个阶段的评价每代评价时间相差将近一倍，这说明当用户对于目标个体明确之后，会有目的的来进行评价，从而减少每个个体的评价时间.

最后，进行HAM-IGA与TIGA的满意度对比，首先将系统的最终结果分为三类：第一类是由于没有在规定代数能发现最优个体，而由系统强制停止；第二类是由于用户感到非常疲劳，不愿去找最优个体，而选择比较满意的个体(cool one)；第三类是成功找到了最优个体，如图9所示，其中，横坐标指的是以上三类情况，纵坐标代表每一类情况在所有测试结果中所占的比例，从图中可以看出，第一类和第二类的情况HAM-IGA比TIGA分别少40%和62.5%，而对于第三类情况，HAM-IGA比TIGA提高了100%，由此可以看出，HAM有效的提高了IGA的成功率，提高了用户的满意度.

表4 HAM-IGA与TIGA的性能对比

表5 HAM的应用对于系统运行的影响

图8 HAM-IGA与TIGA的收敛性比较

图9 HAM-IGA与TIGA满意度对比

4 结束语

本文在交互式遗传算法的领域提出犹豫度的概念，根据此概念建立了犹豫度调整机制，用于补偿由于用户犹豫产生的评价噪声，从而改善交互式遗传算法的首要问题——用户疲劳度问题.然后选择汽车操控台的概念设计作为实验对象，根据汽车操控台的复杂性特点，采用两种约束处理方法——删除策略和修改策略以改善交互式遗传算法的约束满足问题.最后，基于此方法建立汽车操控台概念设计系统，并通过多次试验，分析试验结果，发现此方法能够有效的降低评价过程中，尤其是评价前期中的评价噪声，从而减少用户的评价代数和评价时间，避免由于长时间的评价而产生的用户疲劳，同时此方法能够明显的提高用户对于系统结果的满意度.在后续的研究中，将继续深入研究犹豫度的概念，完善犹豫度调整机制，更加有效地减少评价噪声，以提高用户的满意度.

[1]唐加福, 汪定伟, 刘士新, 等. 产品优化设计的用户满意模型[J]. 管理科学学报, 2003, 6(3): 46-51. Tang Jiafu, Wang Dingwei, Liu Shixin, et al. Study on relationships between manager’s behavior and managerial performance[J]. Journal of Management Sciences in China, 2003, 6(3): 45-51.(in Chinese)

[2]经有国， 但 斌， 张旭梅， 等. MC 半结构化客户需求信息表达与处理方法[J]. 管理科学学报， 2011， 14(1)： 78-85. Jing Youguo, Dan Bin, Zhang Xumei, et al.X Expressing and processing approach for semi-structured customer needs under mass customization[J]. Journal of Management Sciences in China, 2011， 14(1)： 78-85. (in Chinese)

[3]Ozcelik F, Sarac T. A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings[J]. International Journal of Production Research， 2012, 50(15): 4025-4037.

[4]Huang G Q, Li L, Schulze L. Genetic algorithm-based optimization method for product family design with multi-level commonality[J]. Journal of Engineering Design， 2008， 19(5)： 401-416.

[5]Haq A N, Ramanan T R. A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling[J]. International Journal of Production Research， 2010， 48(14)： 4217-4231.

[6]邹昊飞, 夏国平, 杨方廷. 基于两阶段优化算法的神经网络预测模型[J]. 管理科学学报, 2006, 9(5): 28-35. Zou Haofei, Xia Guoping, Yang Fangting. Neural network forecasting model using multi-stage optimization approach based on GMDH and genetic algorithm[J]. Journal of Management Sciences in China, 2006, 9(5): 28-35. (in Chinese)

[7]Kuo R J. Integration of genetic algorithm and particle swarm optimization for investment portfolio optimization[J]. Applied Mathematics & Information Sciences， 2013, 7(6): 2397-2408.

[8]Gao Zhijun. A genetic ant colony algorithm for routing in CPS heterogeneous network[J]. International Journal of Computer Applications in Technology, 2013， 48(4)： 288-296.

[9]宋莉波, 徐学军, 孙延明, 等. 一种求解柔性工作车间调度问题的混合遗传算法[J]. 管理科学学报， 2010, 13(11): 49-54. Song Libo, Xu Xuejun, Sun Yanming, et al. A hybrid genetic algorithm for flexible job shop scheduling problem[J]. Journal of Management Sciences in China, 2010, 13(11): 49-54.(in Chinese)

[10]Yoon D M, Kim K J. 3D Game Model and Texture Generation using Interactive Genetic Algorithm[C]. WASA’12 Proceedings of the Workshop at SIGGRAPH Asia, Singapore, 2012: 53-58.

[11]Munteanu C, Morales F C, Ruiz-Alzola J. Speckle reduction through interactive evolution of a general order statistics filter for clinical ultrasound imaging[J]. IEEE Trans. on Biomedical Engineering, 2008, 55(1): 365-369.

[12]Brintrup A M, Ramsden J, Takagi H, et al. Ergonomic chair design by fusing qualitative and quantitative criteria using interactive genetic algorithms[J]. IEEE Trans. on Evolutionary Computation, 2008, 12(3): 343-354.

[13]Nathan-Roberts D, Liu Yili. Investigation of RelativeMobile Phone Size Preference Using Interactive Genetic Algorithms[C]. Proceedings of the Human Factors and Ergonomics Society Annual Meeting, San Diego: 2010: 1807-1811.

[14]Bandte O, Malinchik S. A broad and narrow approach to interactive evolutionary design: An aircraft design example[J]. Applied Soft Computing, 2009, 9(1): 448-455.

[15]Zhu H, Wang S F, Wang Z. Emotional music generation using interactive genetic algorithm[C]. Int Confon Computer Science and Software Engineering, Wuhan, 2008: 345-348.

[16]Babbar-Sebensa M, Minskerb B S. Interactive genetic algorithm with mixed initiative interaction for multi-criteria ground water monitoring design[J]. Applied Soft Computing, 2012， 12: 182-195.

[17]Wang L H. A comparison of three fitness prediction strategies for interactive genetic algorithms[J]. Journal of Information Science and Engineering, 2007, 23(2): 605-616.

[18]Sun Xiaoyan, Gong Dunwei, Zhang Wei. Interactive genetic algorithms with large population and semi-supervised learning[J]. Applied Soft Computing, 2012, 12: 3004-3013.

[19]Babbar-Sebensa M, Minskerb B S. Interactive genetic algorithm with mixed initiative interaction for multi-criteria ground water monitoring design[J]. Applied Soft Computing, 2012, 12: 182-195.

[20]Branke J, Schmidt C. Sequential Sampling in Noisy Environments[M]//Lecture Notes in Computer Science, Berlin: Springer, 2004: 202-211.

[21]Beyer H G. Actuator noise in recombinant evolution strategies on general quadratic fitness models[C]//Proceedings of Genetic and Evolutionary Computation Conf(GECCO2004), Seattle: Springer, 2004: 654-665.

[22]Jin Yaochu, Branke Jürgen. Evolutionary optimization in uncertain environments: A survey[J]. IEEE Transactions on Evolutionary Computation, 2005, 9(3): 303-317.

[23]Di Pietro A, While L. Applying evolutionary algorithms to problems with noisy, time-consuming fitness functions[C]. Proceedings of the 2004 Congress on Evolutionary Computation, Portland: [s.n.], 2004: 1254-1261.

Interactive genetic algorithm based on customer demand

DOURun-liang,GUOJun-peng,TIANXiang-long,ZONGChao

Collage of Management and Economics, Tianjin University， Tianjin 300072， China

s: To solve the problem of evaluation noise in the interactive genetic algorithm (IGA), the concept of hesitancy degree is put forward, hesitancy degree adjustment mechanism is set up, and the deletion strategy and modification strategy are applied to handle the unsatisfied individuals generated in the process of initial population generation, crossover and mutation. By emulating the concept design of car console, the interactive interface with humanization is established to validate the advance and rationality of the method system brought forward in the paper. The experiment shows that the IGA can effectively reduce the evaluation noise, speed up the convergence, lower the fatigue degree and increase users’ satisfaction about the result.

interactive genetic algorithm; hesitancy degree; evaluation noise; constraint handling; fatigue degree

2013-07-16；

2015-11-04.

国家自然科学基金资助项目(71201115).

窦润亮(1977—)， 男， 天津人， 博士， 副教授. Email： drl@tju.edu.cn

F49

A

1007-9807(2016)01-0024-11