控制与决策  2020, Vol. 35 Issue (2): 309-318  
0

引用本文 [复制中英文]

郭广颂, 文振华, 郝国生. 基于灰支持向量回归机预测适应值的交互式集合进化计算[J]. 控制与决策, 2020, 35(2): 309-318.
[复制中文]
GUO Guang-song, WEN Zhen-hua, HAO Guo-sheng. Set-based interactive evolutionary computation with forecasting fitness by grey support vector regression[J]. Control and Decision, 2020, 35(2): 309-318. DOI: 10.13195/j.kzyjc.2018.0729.
[复制英文]

基金项目

国家自然科学基金项目(61673196);航空科学基金项目(2018ZD55008);河南省高等学校重点科研项目(18A120012)

作者简介

郭广颂(1978—), 男, 副教授, 硕士, 从事人机交互学习、进化优化等研究, E-mail: guogs78@126.com;
文振华(1976—), 男, 副教授, 博士, 从事航空发动机状态监测与故障诊断等研究, E-mail: zhenhuawen@zua.edu.cn;
郝国生(1972—), 男, 教授, 博士, 从事进化计算和大数据应用等研究, E-mail: hgskd1@jsnu.edu.cn

通讯作者

郭广颂, E-mail: guogs78@126.com

文章历史

收稿日期:2018-05-28
修回日期:2018-08-30
基于灰支持向量回归机预测适应值的交互式集合进化计算
郭广颂 1, 文振华 1, 郝国生 2     
1. 郑州航空工业管理学院 智能工程学院,郑州 450046;
2. 江苏师范大学 计算机科学与技术学院,江苏 徐州 221116
摘要:个体适应值的高精度预测和高效的进化策略对于提高进化优化算法性能至关重要.针对现有大规模种群交互式进化计算个体适应值估计误差较大以及传统进化策略搜索效率较低的问题, 提出一种基于灰支持向量回归机的个体适应值预测方法和大规模种群集合进化策略.建立基于灰支持向量回归机的适应值预测模型, 给出4种集合进化个体比较测度, 同时提出新的集合进化个体自适应交叉和变异概率.基于上述策略, 采用NSGA-Ⅱ范式设计一种交互式集合进化优化算法.将该算法应用于RGB颜色One-max优化问题, 以表明所提出个体适应值预测方法和集合进化策略的有效性.
关键词灰支持向量回归机    隐式性能指标    交互    适应值预测    集合进化    
Set-based interactive evolutionary computation with forecasting fitness by grey support vector regression
GUO Guang-song 1, WEN Zhen-hua 1, HAO Guo-sheng 2     
1. School of Intelligent Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450046, China;
2. College of Computer Science and Technology, Jiangsu Normal University, Xuzhou 221116, China
Abstract: Efficient forecasting fitness and evolutionary strategies are more critical for improving evolutionary algorithm optimization performance.Most current interactive evolutionary computation with large population has larger fitness estimation error and lower efficiency adopting the traditional evolutionary strategy.Accordingly, a fitness prediction method based on grey support vector regression and a set-based evolutionary strategy are proposed.Then, four comparative measures of set-based individuals evolution are defined, and adaptive crossover and mutation probability are proposed.Based on above strategies, a set-based interactive evolutionary algorithm is designed by using the powerful NSGA-Ⅱ algorithm for optimizing tacit indices problems.The proposed algorithm is applied to RGB color One-max optimization problem, and its outstanding performance is experimentally demonstrated.
Keywords: grey support vector regression(GSVR)    tacit indices    interactive    forecasting fitness    set-based evolution    
0 引言

20世纪30年代, 英国哲学家Michael Polanyi将一类以个人、团队、组织的行为经验、组织文化、习惯认识等形式存在且不能清晰表述和有效转移的知识称为隐式知识(也称隐性知识).由于隐式知识的量化指标不能用明确的函数表示, 隐式性能指标优化问题一直是心理学、管理学、人工智能等多领域内的研究难题. 20世纪90年代提出的基于启发式学习的交互式进化计算是解决该类问题的有效方法之一, 并获得广泛关注[1].应用交互式进化计算求解隐式指标优化问题需要解决两个基本问题: 1)如何有效提取隐式知识; 2)如何高质量求解隐式性能指标.

对于第1个问题, 主要有两种研究策略:一是在边交互边进化方式下, 通过人-机交互接口直接提取隐式知识.这主要集中于适应值赋值方式的研究, 如采用模糊数[2]和区间数[3]等不确定数表达适应值, 反映用户的偏好特性; 为弥补数值类型适应值偏好知识表达的不足, 文献[4-5]结合用户浏览行为表达个性化需求.直接获取隐式知识计算量小, 方法简单, 但信息不确定性较大, 噪声含量较高.二是在进化过程中, 采用知识提取模型挖掘偏好信息, 间接获取隐式知识.文献[6]采用偏好网络拟合用户偏好, 估计个体适应值并引导搜索; 类似地, 文献[7]采用神经网络学习用户偏好, 估计适应值.间接获取隐式知识可以通过对偏好信息的深度挖掘提高算法的搜索能力, 但由于知识提取模型建模比较复杂, 估计误差无法测量, 依然会带来大量适应值噪声.深入挖掘用户行为模式的适应值估计/表达策略, 有望在更复杂的交互场景下获取隐式知识, 但从优化性能整体看, 仅依靠提高隐式知识提取力度提升算法性能仍有很大局限性.

对于第2个问题, 主要通过降低用户疲劳的高效进化策略实现.文献[2-3]采用大种群规模提高算法搜索能力, 但这种方法需要解决大量未评价个体适应值估计问题.对此, 采用代理模型执行进化可以降低用户工作量, 节省计算开销.文献[8]采用候选删除算法学习用户偏好, 代替用户评价个体.文献[9]构建个体精英集, 选择与精英集相似的个体类别直接用于遗传操作, 减轻用户负担.文献[10]在进化阶段通过逻辑推理模拟用户选择个体, 但该方法因用户提交信息过少, 会产生较大的适应值不确定性.将上述方法相结合, 在大规模种群下采用进化代理模型可以显著提高算法性能[3, 6].上述算法中, 如何设计种群进化策略至关重要, 由于代理模型会产生误差累积, 降低估计误差是一个难以解决的问题.此外, 目前研究极为活跃, 大多采用非被占优排序遗传算法(NSGA)的改进型NSGA-Ⅱ/Ⅲ实现的融入用户偏好多目标进化算法(MOEA), 也可以求解某些隐式性能指标优化问题[11].但该方法可视性较差, 难以优化复杂隐式性能指标.

实际上, 问题1)和问题2)的研究策略有着内在联系:充分有效地提取隐式知识是进化优化性能指标的基础, 高效的进化策略可以在深度提取隐式知识的同时实现性能指标优化.例如扩大种群规模和采用代理模型等方法均可以在完成进化优化的同时实现对已获知识的再利用和偏好信息的挖掘.

综上所述, 已有方法的劣势集中体现在: 1)已有方法大多采用传统遗传策略, 受进化搜索能力限制, 严重影响了优化效果; 2)已有方法在扩大种群规模和采用代理模型提高算法效率时, 需要对非用户评价个体估计适应值, 这会导致评价误差累积, 偏好方向改变.集合进化计算是近年新兴的一类进化算法, 已广泛应用于多目标优化问题[12-13].若将集合进化方法应用于大规模种群聚类进化, 则可进一步提高搜索效率; 同时, 采用代理模型重新评价已有大规模种群个体的估计适应值, 可以提高适应值精度.两者融合, 取长补短, 有望改进当前交互式进化优化算法性能.鉴于此, 本文提出基于灰支持向量机预测适应值的交互式集合进化计算(set-based interactive evolutionary computation with forecasting fitness by grey support vector regression, SetIEC-GSVR).该方法针对大规模种群, 通过灰支持向量机预测种群聚类内个体适应值, 并对种群实施集合进化策略, 直接求解隐式性能指标优化问题.将所提出方法应用于RGB颜色One-max优化问题, 从而验证了算法的有效性.

1 提出的方法 1.1 算法思想

首先, 采用大规模种群扩大搜索空间, 以有限用户评价个体为聚类中心对种群聚类; 然后, 对聚类内非聚类中心个体按融合个人浏览行为的个体相似性估计适应值, 并采用灰色支持向量回归模型进一步预测个体适应值, 构成集合进化个体; 最后, 采用集合进化策略在NSGA-Ⅱ范式下实现集合进化算法.为实现本文方法, 需要解决集合进化个体构建、个体适应值预测和集合进化策略设计等3个主要问题.

1.2 集合进化个体构建 1.2.1 个体相似度

不失一般性, 考虑优化问题

其中: xd维决策变量, S是其取值范围, f(x, t)是不能用显式函数表示的被优化隐式性能指标.记第t(t>0)代进化种群x(t)中的第i个个体为xi(t)(i=1, 2, …, N), N为种群规模, xi(t)的适应值为f(xi(t)), xi(t) ∈ x(t).

根据评价经验, 个体表现型相似性具有两个特征: 1)属性相似性, 即个体间属性越相似, 表现型也越接近; 2)非偶对称性, 即将比较个体与参照个体位置互换后, 个体表现型相似度不完全相同.基于相似性的上述特征, 记第t代种群为x(t)中的第i个个体为xi(t)(i=1, 2, …, N), 则xi(t)的表现型可表示为xi(t) = {xi1, xi2, …, xig|xir ∈ {l1r, l2r, …, lsr}}.其中: xir(r = 1, 2, …, g)为组成个体的r个属性; l1r, l2r, …, lsrxir的属性值.考虑两个个体xi(t)和xj(t), 设xj(t)是参照个体, xi(t)是比较个体, 基于认知的模糊性, 采用高斯函数μij描述个体xi(t)与xj(t)的属性间相似关系

(1)

其中σ(xj(t))是与用户浏览行为相关的参照个体xj(t)适应值的不确定度, 具体计算方法见文献[2].则xi(t)与xj(t)的表现型相似度为μij(xir)的平均值, 记为

(2)
1.2.2 灰支持向量机

基于支持向量回归机优异的函数逼近能力和灰色模型对有限时间序列数据的良好预测性, 文献[14]提出了一种新的用于数量有限的波动数据预测模型-----灰支持向量回归机, 该模型能有效减少信息不充分带来的决策损失.基于这一结论, 为提高适应值精度, 本节采用灰支持向量回归机预测种群聚类中非用户评价个体适应值.具体过程如下:

将个体精确数适应值f(xk(t))(xk(t) ∈ x(t))重新记为F0 =(f0(x1(t)), f0(x2(t)), …, f0(xN(t))), 构成个体适应值原始序列.则F0的1-AGO序列为F1 =(f1(x1(t)), f1(x2(t)), …, f1(xN(t))), 即

为了使原始数据在各个特征维度对目标函数的影响权重一致, 首先对原始序列归一化, 有

(3)

归一化后数据序列为F0'=(f0'(x1(t)), f0'(x2(t)), …, f0'(xN(t))).然后, 建立F0'的1-AGO序列F1'=(f1 '(x1(t)), f1 '(x2(t)), …, f1'(xN(t))), 即

以用户评价适应值为中心, 对F1'中数据聚类.设Nc为用户评价适应值数目, 从每一子类中随机选择75 %的数据(不含用户评价适应值数据)作为训练数据, 其余25 %的数据作为测试数据.于是训练样本集为DL = {(xi(t), f1'(xi)), i=1, 2, …, Ts }, Ts= 0.75(N-Nc); 测试样本集为DT = {(xi'(t), f1 '(xi')), i' = 1, 2, …, Te }, Te = 0.25(N -Nc).这样做可以保证数据均匀分布, 建立的模型更精确.将灰支持向量模型记为

(4)

其中: b为偏置项, ω为权重. 1-AGO变换项f1 '(xk(t))代表了个体适应值输入空间向高维特征空间的非线性映射.式(4)的意义是, 对于输入值f1 '(xk(t)), 灰支持向量模型可以通过回归函数精确预测出输出值f0'(xk+1(t)).式(4)中未知参数ωb使用Vapnik提出的ε不敏感损失函数, 由高维特征空间内的训练集估计, 即

(5)

综合考虑模型复杂度和ε不敏感带来的训练样本偏离程度, 引入非负松弛变量ξkξk*, 则式(5)可以写为

(6)

其中: 为控制模型的拟合精度; C为正则化常数, 控制对超出误差的样本的惩罚程度.式(6)可以用Lagrange乘子法求解, 有

(7)

其中αkαk*ηkηk*≥0, 是满足KKT条件的Lagrange乘子.由此可得对偶优化模型

(8)

其中 < ·, ·>代表向量内积.由于线性灰支持向量模型不能对非线性映射数据对(f1 '(xk(t)), f0 '(xk + 1(t)))获得可靠解, 这里选择核函数

代入式(8), 求得αkαk*b后, 灰支持向量回归机模型为

(9)

其中是对测试个体xi'(t)的1-AGO序列适应值f1 '(xi'(t))的灰支持向量机预测值.

适应值预测模型建立后, 根据测试数据集DT计算模型逼近误差:首先, 将DTf1'(xi'(t))按式(9)计算预测值; 然后, 将其恢复为原始序列刻度, 有

(10)

最后得到模型逼近误差为

(11)

σGSVR对优化结果的作用有两个:一是反映了优化质量, 即随着进化深入, 适应值预测精度逐渐提高, σGSVR趋于减小, 优化质量逐渐提高; 二是用于灰支持向量回归机模型更新, 即当σGSVR大于事先设定的阈值φGSVR时, 从DL(t)中重新选择训练数据, 然后根据新的训练数据更新模型.

1.2.3 非中心个体适应值预测

首先, 选择部分个体xi(t)(i=1, 2, …, Nc)作为聚类中心个体, 并由用户评价适应值f(xi(t)).然后, 按式(2)逐一计算种群中其他非中心个体xo(t)与各中心个体的相似度μ(xo(t), xi(t)), 将满足{μ(xo(t), xi(t)), o = 1, 2, …, N-Nc}的个体归为一类, 记为xi(t) = {xi(t)}, i ∈ {1, 2, …, Nc}.这样, 种群x(t)将分为Nc个子类, 记为x1(t), x2(t), …, xNc(t).最后, 在各个体子类内求取与各聚类中心相似度的加权平均值, 估计非中心个体xo(t)(xo(t) ∈ xi(t))的适应值

(12)

为降低适应值估计误差, 再按式(10)对f(xo(t))采用灰支持向量回归机预测, 得到用于后续进化的非中心个体最终适应值(xo(t)).种群个体聚类后, 形成的个体子类x1(t), x2(t), …, xNc(t)是一个个体集合, 基于集合进化思想, 很自然地可以将个体子类视为进化个体(集合进化个体).

1.3 集合进化策略 1.3.1 优化问题转化

通过选择合适的性能指标, 可将隐式性能指标优化转化为如下一般性集合决策变量优化问题:

(13)

其中: P(S)为决策空间S的幂集; X = {x1(t), x2(t), …, xNc(t)}为进化个体构成的种群; Fd(X)(d=1, 2, …, Id)为种群X的性能指标; Id为转化后优化问题的维数, 且远小于Nc.考虑隐式指标的特点, 对于转化后的优化问题, Pareto优化解集应具有如下3个特性: 1)对应的Pareto前沿应接近真实Pareto前沿, 即具有良好的逼近性; 2) Pareto前沿上的点在解空间中的差异性越大越好, 即具有较好的多样性; 3) Pareto前沿应具有较好的分布性.

结合隐式性能指标特点, 本节给出新的集合个体比较测度, 具体如下.

记第t代进化种群x(t)的第j个进化个体为xj(t) = {xj(t)} = {xj1(t), xj2(t), …, xjM(t)}, j ∈ {1, 2, …, Nc}.其中: xj(t)为中心个体, 其余个体适应值为f(xjp(t)), p = 1, 2, …, M - 1, M=|{xj(t)}|为进化个体xj(t)包含的个体数.

对于特性1), 采用超体积测度刻画[13]

(14)

其中: f(xj(t))为进化个体xj(t)的适应值向量, λ为勒贝格测度, zref为参考点.

在集合进化框架下, 进化个体是一个集合, 每个集合代表一个偏好解, 因此, 对于每一偏好解而言, 每个进化个体一定有一个最小值.这意味着, 对于一个种群而言, 每一偏好解都有一个最小值.由该种群在所有偏好解上的最小值构成的向量可以作为参考点, 即参考点zref的第j个分量为

(15)

对于特性2), 采用进化个体相似度信息熵刻画, 进化个体xj(t)的相似度信息熵为

(16)

由式(16)可知: xj(t)的中心个体xj(t)与其他进化个体的聚类中心相似度μ(xi(t), xj(t))越大, xj(t)与其他进化个体越相似, 种群多样性越差, F2(X)越小; 反之, F2(X)越大, 种群多样性越好.

对于特性3), 采用下式刻画:

(17)

其中: d(xj(t))为xj(t)的最小拥挤距离, d(xj(t)) = ; d*为种群进化个体平均拥挤距离, .式(17)用于计算xj(t)的分布性, 该值越小, 说明xj(t)的分布性越理想, 反之亦反.

1.3.2 集合进化个体比较

假设x1(t)、x2(t)为任意2个不同进化个体, 即x1(t)、x2(t)∈ P(S), 且x1(t)≠x2(t).利用上述测度函数, 可对种群进化个体进行非被占优排序.为了获得进化个体全序关系, 对于具有相同序值的进化个体, 进一步比较灰数测度, 有

(18)

式(18)将进化个体xj(t)的适应值视为区间灰数, 则xj(t)的评价不确定性可通过区间灰数灰度刻画, 即GF(X)越小, 进化个体的不确定性越小, 反之亦反.所以式(18)的比较结果更符合隐式指标优化特点.

1.3.3 自适应集合交叉和变异概率

交叉和变异操作对于提高Pareto最优解集的性能和算法搜索能力具有非常重要的作用[13].针对集合进化特点, 本小节将给出自适应集合交叉和变异操作算子.对于不同进化个体之间的交叉操作, 采用固定二进制交叉概率; 对于同一进化个体内部的交叉概率, 采用自适应交叉概率, 即

(19)

式(19)考虑了进化过程中交叉操作与集合进化个体多样性和不确定性变化之间的关系.即为了增强搜索能力, 进化个体的不确定性应与交叉概率成正比; 为了保留优势个体, 进化个体的多样性应与交叉概率成反比.交叉概率整体应随进化逐渐减小, 加强算法收敛性; 反之亦反.

集合进化个体的变异操作采用单点变异方式, 自适应变异概率由Pm1Pm2构成, 即

(20)
(21)

其中f(xjp(t))是进化个体xj(t)中待变异个体xjp(t)的适应值.

式(20)体现了变异操作与进化个体的多样性和收敛性的关系.即为了保留优势个体, 多样性和收敛性应与变异概率成反比, 反之亦反.

式(21)体现了变异操作与进化个体适应值的关系.即为保护优势个体不被破坏, 适应值越大的个体, 被执行变异的概率越小.

综合式(20)和(21), 进化个体自适应变异概率Pm

(22)
1.4 算法描述

本文算法在NSGA-Ⅱ范式下实现, 具体方法是:首先, 对规模为N的父代种群x(t)采用1.3节集合占优关系进行选择、交叉和变异操作, 生成同等规模的临时种群Q(t); 然后, 将父代种群x(t)和临时种群Q(t)合并, 并对合并种群排序, 挑选前N个个体作为子代种群; 最后, 对子代种群等间距划分为Nc个单元, 从每个单元中随机选取1个个体, 共将Nc个个体推荐给用户.本文算法框图如图 1所示, 其中阴影部分为本文工作的创新之处.

图 1 算法框图

根据上述算法步骤, 下面分析本文方法的时间复杂度.在一次进化过程中, 涉及比较运算的操作及它们在最坏情况下的时间复杂度如下:

1) 转化后的目标函数有3个, 分别是超体积测度、分布性测度和延展性测度.其中, 计算超体积测度的时间复杂度为O(NcId+Id· Nclog Nc).计算多样性测度时, 需求每个目标上相似度信息熵, 因此其时间复杂度为O(Id· Nc).在计算分布性测度中的平均拥挤距离时, 计算d(xj(t))需进行Nc次比较, 共需计算Nc个d(xj(t)), 因此, 计算平均拥挤距离的时间复杂度为O(Nc2).

2) 由于目标函数个数为3, 非支配解排序的时间复杂度为O(3N2).

3) 具有相同Pareto序值个体的适应值计算及其排序时间复杂度分别为O(3Nclog(3Nc))和O(Nclog Nc).

4) 最优个体中解的适应值计算及其排序时间复杂度分别为O(Id· Nc2)和O(Nlog N).

5) 合并种群x(t)和Q(t)的非被占优解排序时间复杂度为O(Id(2Nc)2).

综上, 本文算法的时间复杂度为O(N·NcId), 随原目标函数的增多呈指数增长.

2 实例验证 2.1 问题描述

本文求解基于RGB颜色One-max优化问题. RGB颜色模式是一种工业颜色标准, 该模式通过对红(R)、绿(G)、蓝(B)三个颜色属性的变化以及它们的叠加得到各种颜色, 每一个颜色属性取值范围均为0 ~ 255. RGB颜色个体染色体采用二进制编码, 编码长度为24位, 其中, 前8位表示红色属性, 中间8位表示绿色属性, 最后8位表示蓝色属性, 每个颜色属性对应二进制编码范围为00000000 ~ 11111111.优化目标为事先设定的某种目标颜色, 通过进化优化, 用户可以获得与目标颜色匹配的颜色个体.

One-max优化问题的函数是一类特殊的二进制位函数, 优化目标是最大化该函数串位中包含基因值为“1”的基因位数量.显然, 基于RGB颜色的One-max优化目标是白色, 其RGB颜色属性为(255, 255, 255), 染色体编码为11111111 11111111 11111111, 并且这是一种可以采用交互式进化算法求解的隐式性能指标优化问题[15].由于RGB颜色空间在视觉上不均匀, 引入孟塞尔颜色空间来度量两个颜色对的相似性.相似距离定义为DNBS[16].当DNBS≤3.0时, 可以认为两颜色在最小可觉差之内.因此, 本文在进化系统中对目标颜色匹配有一定的宽限, 即在15代内, 若种群进化出与目标色相近的颜色, 则系统自动终止进化, 并输出最终结果.

2.2 实验设计

本系统选择无视觉缺陷的男女各5名在校大学生作为测试用户, 记为用户1 ~用户10.算法性能测试是以白色个体(255, 255, 255)为优化目标的One-max问题测试.

由于目前尚无采用集合进化策略的交互式进化优化方法, 本文将文献[6]“基于可能性条件偏好网络的交互式遗传算法(probabilistic conditional preference network assisted interactive genetic algorithm, PCPN-IGA)”和文献[9]“基于精英集选择进化个体的交互式遗传算法(interactive genetic algorithms with selecting individuals using elite set, IGA-SES)”这2种相关算法作为比较算法, 验证本文方法在搜索效率、优化质量、减轻用户疲劳等方面的有效性.

2.3 遗传操作及参数设置

采用Visual Basic 6.0软件, 分别基于本文方法、IGA-SES和PCPN-IGA三种算法开发相应系统. IGA-SES和PCPN-IGA均采用大规模种群进化, 遗传操作均采用规模为2的联赛选择, 种群规模N=100, 用户评价个体数Nc=12, 适应值范围是1 ~ 99之间的整数, 最大进化代数T=15.本文方法参数为:式(19)中取k1=k2=0.4, 式(20)和(21)中取k3=k4=0.5. IGA-SES和PCPN-IGA的主要遗传参数均为:单点交叉和变异概率分别为0.6和0.1.当用户评价个体相同数目占到一半以上, 或者虽然用户评价个体基因型有细微差异, 但用户对个体表现型满意, 或者算法已经达到最大进化代数时, 都认为算法进入收敛, 用户手动终止进化.

2.4 交互界面及操作

基于3种方法的进化优化系统人机交互界面如图 2所示[15].交互界面由3部分组成.第1部分是位于界面左半部的进化模块, 该模块呈现给用户12个个体(颜色块), 每个个体下方设置适应值输入文本框.同时, 系统通过个体下方滑动块记录用户对每个个体的评价时间, 用于计算适应值不确定度.为便于比较, 个体外围设置目标颜色块, 并显示与当前个体的距离值(DNBS).第2部分是位于界面右上部的进化参数和信息统计模块, 进化前用户可以通过拖动滚动条输入RGB颜色值, 设置目标颜色.此外, 该模块还显示进化开始时刻、当前进化代数、用户评价个体数、评价总耗时等统计信息.第3部分是位于界面右下部的命令按钮模块, 用户单击“开始”按钮, 系统初始化并产生初始种群; 用户评价个体后, 单击“下一步”按钮, 系统在后台完成聚类、适应值估计、集合进化等进化操作, 并生成下一代进化种群.循环该过程, 直到满足终止条件, 点击“结束”按钮终止进化.

图 2 交互界面
2.5 实验结果与分析

测试的主要目的是测试算法对固定目标的搜索能力和算法的优化性能, 该项目分为不限定耗时和限定耗时2个测试子项.

2.5.1 不限定耗时

要求10名用户在最大进化代数内不限定耗时, 分别用上述3种算法各运行1次, 总计30人次进化优化.本项目进行如下2个方面的测试.

1) 本文方法的进化策略测试.

采用如下5个性能指标测试本文方法的集合进化策略的有效性.

① H测度, 即式(14), H测度刻画了最好超体积, 该值越大越好.

② E测度, 即按式(16)计算并将结果归一化, E测度刻画了种群多样性, 该值越大种群多样性越好.

③ D测度, 即式(17), D测度刻画了所得Pareto前沿的延展性与理想延展性的距离, 该值越小越好.

④ I测度, 即式(18), I测度刻画了所得Pareto前沿的不确定度, 该值越小Pareto前沿越精确.

⑤ 最优进化个体非被占优解比例, 即最优进化个体中非被占优个体数目与最优进化个体规模的比例, 该比例越大说明最优进化个体中Pareto互不占优的概率越大, 选择压力越低; 反之亦反.

图 3给出了本文方法得到的Pareto前沿H、E、D和I测度箱图.可以看到: H测度分布范围在[0.8, 1]之间, 表明本文集合进化策略获得的Pareto前沿更接近真实Pareto前沿; E测度分布范围在[0.5, 0.9]之间, 表明本文集合进化策略能维持较好的种群多样性; D测度分布范围在[0.1, 0.3]之间, 表明本文集合进化策略能够维持种群的延展性; I测度分布范围在[0.3, 0.6]之间, 表明本文算法的Pareto前沿较为精确.这些测度反映出本文集合进化策略可以在维持种群延展和多样性的同时提高优化解的逼近性能.

图 3 本文算法测度箱图

记最优进化个体包含的个体个数为N', 其中, 非被占优解的个数为N'D, 则非被占优解比例为N'D/N'. 图 4给出所提方法N'D/N'随进化代数的变化曲线.由图 4可以看出: ① N'D/N'值随着进化代数逐渐上升, 这说明最优进化个体中非被占优解不断增加, 进化个体的质量不断提高; ② 最后得到的最优进化个体中N'D/ N'值大于0.6, 接近1, 这说明, 本文提出的集合进化策略能够在进化结束时, 最优进化个体中非被占优个体数量至少为60 %, 优化解质量已经很高.

图 4 本文算法非被占优解比例

另外, 根据式(11)统计本文算法的模型逼近误差, 其均值随进化代数变化曲线如图 5所示.由图 5可以看出, 模型逼近误差逐渐减小.这表明, 随着进化深入, 适应值预测精度逐渐提高, 适应值估计误差逐渐减小.另一方面, 算法采用更为精确的灰支持向量机预测适应值参与进化, 优化结果更符合人的偏好, 这也同时加速了模型逼近误差的减小趋势.通过上述分析可以看到本文方法的进化策略是有效的.

图 5 灰支持向量机模型逼近误差

2) 不同方法的性能比较.

3种方法的实验结果如图 6所示.由图 6可以看出本文方法明显优于对比方法, 具体表现为:

图 6 算法性能比较

① 在搜索时间方面, 本文方法耗费的时间最少, 提高了搜索效率.原因在于本文方法采用集合进化策略和NSGA-Ⅱ算法引擎, 可以使种群分布更为均匀, 多样性更好, 提高了算法搜索效率.采用自适应交叉和变异操作更加强了算法的收敛性.虽然用于集合进化个体耗时较长, 但整体搜索时间相对于对比算法要短.

② 在进化代数方面, 本文方法进化代数最少, 这不仅提高了搜索效率, 还减轻了用户疲劳.原因在于本文方法采用基于用户浏览行为的个体相似度估计个体适应值, 同时采用灰支持向量回归机对适应值进一步预测, 提高了适应值精度, 所以进化方向更符合人的偏好, 算法收敛较快.

③ 在优化解与目标解距离对比方面, 本文方法的优化解距离最小, 说明优化解质量最高.原因在于本文方法采用一系列改进策略提高了算法整体优化性能, 对于求解复杂隐式性能指标优化问题表现出良好的计算性能.

表 1给出了3种方法的搜索结果均值及完全匹配用户数统计.将表 1中数据进行显著性水平为0.05的Mann-Whitney U检验, 在评价个体数、搜索个体数两项指标上, 本文方法的数量最少, 且与对比方法差异显著.在最优解数量上, 本文方法的数量虽然与对比方法差异不显著, 但仍是最多的.这表明, 本文方法可以在相对最少的评价数量(包括进化代数)下, 获得最多的满意解.这反映出本文算法的优化效率最高.本文方法的搜索个体数量较少主要因为进化代数较少.由于对比方法也是相同种群规模的大规模种群进化, 进化代数越多, 搜索个体数也越多.可见, 对比方法的搜索个体数较多并不能说明搜索能力优于本文方法.在获得完全匹配解用户数量上, 本文方法有3个, IGA-SES有2个, PCPN-IGA只有1个.这说明, 对于颜色匹配这一复杂隐式性能指标优化问题, 大多数用户最终获得的仍是近似解, 但本文方法能获得完全匹配解的用户数最多.通过上述分析可以看到本文方法的搜索性能最好.

表 1 算法搜索结果及完全匹配用户数
2.5.2 限定耗时

要求10名用户在最大进化代数内限定耗时, 分别用上述3种算法各运行1次, 统计算法搜索效率均值(搜索效率=用户评价的互异个体数/用户评价个体总数)如表 2所示.

表 2 算法不同时间内找到互异个体数目比例 

通过限定耗时, 可以在相同的算法时间复杂度下比较优化性能.由表 2可以看出, 3种方法的搜索效率均随限定耗时增加而增加, 这表明, 算法时间复杂度对优化性能具有约束性影响.另外, 相比于本文方法, 两种对比方法的搜索效率在5 min耗时限定和10 min耗时限定的差异不明显.这说明, 本文方法的时间复杂度比对比方法高, 两种对比方法在5 min的耗时限定内即可实现完全进化优化, 本文方法则耗时较多.尽管如此, 由表 2可以看出, 在3种限定耗时内, 本文方法的搜索效率都是最高的, 这说明, 在算法复杂度有严格要求时, 本文方法依然能够达到优于对比方法的计算效果.原因在于, 采用集合进化策略虽然复杂度有所增加, 但搜索效率明显增强, 整体上仍能提高算法优化性能.

综合上述测试及实验结果分析, 本文方法的进化策略可以有效求解隐式性能指标优化问题, 在优化质量、减轻用户疲劳和搜索效率等方面均显著优于对比方法, 所以本文方法明显提高了算法优化性能.

3 结论

本文对个体表现型适应值采用灰支持向量回归机预测, 提高了估计准确性; 对大规模种群集合进化个体进行逼近性、延展性、多样性和不确定性测度比较, 获得了Pareto最优解; 同时, 采用自适应集合交叉和变异策略, 提高了优化效率.最后, 在RGB颜色One-max问题上验证了算法性能.

将集合进化思想融入交互式进化计算是一种尝试, 该方法通过获得Pareto最优解发现优化问题的潜在特性, 为用户在海量数据中推荐个性化方案.但融合集合进化的交互式进化计算面临如下难题: 1)为获得大规模估计适应值个体的均匀Pareto前沿, 需要保持种群在决策空间的多样性, 这对个体密度计算提出了挑战; 2)由于隐式性能指标评价具有不确定性, 这会有多个不同的Pareto最优解对应着相同目标值, 从而导致用户偏好的Pareto最优解不可行的情况发生.上述难题在考虑目标个数大于3的情形下表现尤为突出, 所以, 对于高维隐式性能指标优化问题开发针对性集合进化策略是下一步要研究的内容.

参考文献
[1]
郭广颂, 郝国生. 隐式指标优化问题交互式进化求解理论与方法[M]. 郑州: 郑州大学出版社, 2016: 1-24.
(Guo G S, Hao G S. Interactive evolutionary theory and methods solving optimization problem with implicit indices[M]. Zhengzhou: Zhengzhou University Press, 2016: 1-24.)
[2]
郭广颂, 陈良骥, 文振华, 等. 基于进化个体模糊适应值估计的交互式遗传算法[J]. 控制与决策, 2018, 33(9): 1559-1566.
(Guo G S, Chen L J, Wen Z H, et al. An interactive genetic algorithms based on estimation of individuals' fuzzy fitness[J]. Control and Decision, 2018, 33(9): 1559-1566.)
[3]
孙晓燕, 陈姗姗, 巩敦卫, 等. 基于区间适应值交互式遗传算法的加权多输出高斯过程代理模型[J]. 自动化学报, 2014, 40(2): 172-184.
(Sun X Y, Chen S S, Gong D W, et al. Weighted multi-output gaussian process-based surrogate of interactive genetic algorithm with individual's interval fitness[J]. Acta Automatica Sinica, 2014, 40(2): 172-184.)
[4]
郭广颂, 陈良骥. 基于熵极大化准则的非用户赋适应值交互式遗传算法[J]. 电子学报, 2017, 45(12): 2997-3004.
(Guo G S, Chen L J. An interactive genetic algorithms based on maximum entropy principle with individuals' fitness not assigned by user[J]. Acta Electronica Sinica, 2017, 45(12): 2997-3004. DOI:10.3969/j.issn.0372-2112.2017.12.023)
[5]
Kuzma M, Andrejkov G. Predicting user's preferences using neural networks and psychology models[J]. Applied Intelligence, 2016, 44(3): 526-538. DOI:10.1007/s10489-015-0717-3
[6]
孙晓燕, 朱利霞, 陈杨. 基于可能性条件偏好网络的交互式遗传算法及其应用[J]. 郑州大学学报:工学版, 2017, 38(6): 1-5.
(Sun X Y, Zhu L X, Chen Y. Probabilistic conditional preference network assisted interactive genetic algorithm and its application[J]. Journal of Zhengzhou University: Engineering Science, 2017, 38(6): 1-5.)
[7]
Allysson A A, Matheus P, Italo Y. An architecture based on interactive optimization and machine learning applied to the next release problem[J]. Automated Software Engineering, 2017, 24(3): 623-649. DOI:10.1007/s10515-016-0200-3
[8]
Zahra Sheikhi Darani, Marjan Kaedi. Improving the interactive genetic algorithm for customercentric product design by automatically scoring the unfavorable designs[J]. Human-centric Computing and Information Sciences, 2017, 7(1): 7-38. DOI:10.1186/s13673-017-0088-3
[9]
巩敦卫, 陈健. 基于精英集选择进化个体的交互式遗传算法[J]. 电子学报, 2014, 42(8): 1538-1544.
(Gong D W, Chen J. Interactive genetic algorithms with selecting individuals using elite set[J]. Acta Electronica Sinica, 2014, 42(8): 1538-1544. DOI:10.3969/j.issn.0372-2112.2014.08.012)
[10]
Hisao Ishibuchi, Takahiko Sudo, Yusuke Nojima. Interactive evolutionary computation with minimum itness evaluation requirement and oline algorithm design[J]. Springer Plus, 2016, 192(5): 1-19.
[11]
Bi X, Wang C. A niche-elimination operation based NSGA-Ⅲ algorithm for many-objective optimization[J]. Applied Intelligence, 2018, 48(1): 118-141. DOI:10.1007/s10489-017-0958-4
[12]
Gong Dunwei, Sun Jing, Miao Zhuang. A set-based genetic algorithm for interval many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 47-60. DOI:10.1109/TEVC.2016.2634625
[13]
季新芳, 张凤, 王彩君, 等. 区间参数高维多目标集合进化优化方法[J]. 控制与决策, 2018, 33(12): 2213-2217.
(Ji X F, Zhang F, Wang C J, et al. Optimizing many-objective problems with interval parameters using set-based evolutionary algorithms[J]. Control and Decision, 2018, 33(12): 2213-2217.)
[14]
Tsaur Ruey-Chyn, Chan Shu-Feng. Grey support vector regression model with applications to China tourists forecasting in taiwan[J]. International Journal of Information and Management Sciences, 2014, 25: 121-138.
[15]
Gong Dunwei, Yuan Jie. Impact of individuals' fitness expressions on interactive genetic algorithms' performances[C]. International Conference on Chinese Control and Decision. Shanghai: IEEE, 2009: 2463-2468.
[16]
Gong Y H. Advancing content-based image retrieval by exploiting image color and region features[J]. Multimedia System, 1999, 7(6): 449-457. DOI:10.1007/s005300050145