包含交叉和变异操作的交互式遗传算法

郭广颂,王燕芳

(郑州航空工业管理学院机电工程学院,郑州450015)

包含交叉和变异操作的交互式遗传算法

郭广颂,王燕芳

(郑州航空工业管理学院机电工程学院,郑州450015)

传统交互式遗传算法在优化隐式性能指标时会使用户产生疲劳,影响优化质量与优化效率。为此,提出一种改进的交互式遗传算法。采用二元排序确定适应值评价的不确定度,根据评价序列的最大信息差异计算种群的收敛率,通过收敛率衡量种群进化状态,基于适应值不确定度和种群收敛率设计自适应交叉算子和变异算子,给出交叉概率和变异概率的计算公式,利用包含用户偏好信息的遗传策略引导进化,从而使进化结果更加客观。将该算法应用于服装进化设计系统,结果表明,与传统交互式遗传算法(T-IGA)相比,该算法可获取更多的满意解,提高了优化效率。

遗传算法;自适应交叉;变异概率;适应值;交互环境;不确定性

1 概述

交互式遗传算法(Genetic Algorithm,GA)是20世纪80年代在传统遗传算法的基础上提出的一种进化优化算法［1-2］。它与传统遗传算法的最大区别在于交互式遗传算法的个体适应值由人评价,这样可以将人的主观活动引入进化过程中,利用遗传进化对隐式性能指标或混合性能指标进行优化。由于该算法实现简单,能体现强烈的个性化需求,因此目前在图像识别、艺术设计、虚拟现实等领域获得了有效应用［2］。

由于个体适应值由人评价产生,因此适应值反映了人的主观偏好,而人的偏好会使适应值具有不确定性,不确定性增加,适应值的精确程度便会降低,进化优化效果将会变差。提高适应值精确程度,降低不确定性的直接方法是人在评价个体时投入更多的注意力,但这样无疑会造成人的疲劳,评价不确定性反而会增强。所以,提高适应值精度与降低人

的操作负担是互为矛盾的,这也是交互式遗传算法的一个研究难题。

目前,大致有2种思路解决这一问题:(1)通过建立合理的适应值赋值方式,改善人机交互环境,降低人的操作负担,提高适应值精度;(2)针对评价特点抽取个体适应值的不确定度,采用合适的代理模型代替用户估计进化个体的适应值,减轻用户疲劳。

对于思路(1),文献［3］提出离散适应值赋值方法,一定程度减轻了人的操作负担,但离散适应值本身精度较差,这种方法实质并未考虑降低评价的不确定性。文献［4-6］提出区间数和模糊数适应值赋值方法,相比精确数与离散数,区间数与模糊数可以较好地反映出评价过程的不确定性与渐进性,大大提高了适应值精度。但在进行适应值赋值操作时,区间数要进行适应值上限与下限的2次评价;模糊数要进行中心值与宽度的确定,这其实都增加了人的负担。相似的问题还存在于文献［7］。

对于思路(2),文献［8-11］提出多种交互式遗传算法的机器学习技术,通过代理模型预测评价结果,减少人的部分评价工作。机器学习技术拓展了算法搜索能力,减轻了操作负担,提高了算法性能。但这些代理模型是依据于不同的适应值赋值方式,提取有价值信息而建立,所以,适应值赋值方式的影响依然存在。

针对上述问题,本文提出一种新的交互式遗传算法。对进化个体的评价过程进行分析,依据二元排序方法获得评价的不确定度,基于该不确定度设计自适应交叉算子和变异算子。

2 算法分析与设计

2.1 适应值不确定度

若记第t代进化种群x(t)中的第i个进化个体为xi(t),i=1,2,…,N,N为种群规模,xi(t)的适应值为f(xi(t)),xi(t)∈x(t),则进化个体量测值f(x(t))构成的数值序列为:

因为f(xi(t))难以准确确定,所以f(xi(t))具有不确定性［8］。

遗传进化是一个马尔科夫链过程,每次进化结果都会为偏好提供新环境,所以,用户的偏好是波动的,保持偏好的一致性也是相对的。根据实际经验,对每一代个体逐一评价时,个体的排列顺序如果不同,同一个体的评价结果往往会发生变化,例如第一个被评价的个体大多结果偏低,这便是偏好波动的体现。基于这样的事实,可以对评价过程进行分析:在每一进化代中,个体适应值评价的实质是对个体的两两对比来确定某种偏好特征下的顺序,即是一个二元排序过程。具体地说,偏好对相邻2个个体的适应值影响是最大的,适应值评价是对相邻个体建立比较等级的过程,相邻个体的适应值是对满意解的相似程度的体现。依据评价次序,后评价的个体结果受前一个评价对象的影响最明显,当相邻2个个体差异较大时,偏好波动会比较大,评价的不确定性相应增加;反之,则偏好趋于一致,评价不确定性降低。可以认为评价过程是以相邻个体为单元的链式过程,相邻个体适应值评价是评价过程的最小环节。

对于相邻个体xi(t)和xi-1(t),f(xi(t))和f(xi-1(t))可以看作是对真实适应值fbest(x(t))的比较结果。如前所述,对于个体xi(t),f(xi(t))的不确定性受f(xi-1(t))的影响最大,f(xi(t))的不确定度由f(xi(t))本身和f(xi-1(t))决定。若令有界闭区间:

则fs(t)可以认为是f(xi(t))和f(xi-1(t))信息差异的数值覆盖,而信息差异可以反映评价的不确定性［12］。若记f(xi(t))的不确定度为(xi(t)),由于fs(t)为有界闭区间,则有:

则每一进化代的适应值不确定度记为:

且满足下式成立:

证明:

证毕。

式(4)表明适应值不确定度小于同代的最大信息差异,这也说明了人对相邻个体的评价在每一进化代内最为客观。

衡量进化的另一重要指标是收敛率［11］。若将种群f(xi(t))的收敛率记为δ(xi(t)),则有:

收敛率δ(xi(t))反映了每一进化代中相似个体的平均“拥挤”距离。随着进化不断深入,不同个体的适应值会逐渐接近,个体间的差异将逐渐减小,并且,θ(xi(t))≤δ(xi(t))。

从式(3)和式(5)可以看出,在进化初期用户对个体的认知程度较低,所以,θ(xi(t))和δ(xi(t))都比较大。随着进化过程加深,用户评价的个体数量不断增加,认知目标会逐渐清晰,评价不确定性相应减小,所以,θ(xi(t))和δ(xi(t))也逐渐减小。

2.2 自适应交叉和变异算子

θ(xi(t))和δ(xi(t))描述了适应值在种群进化过程中的变化,反映了个体适应值品质的不同方面,这为设计自适应交叉和变异操作提供了基础。

交叉算子的设计主要基于以下2个方面:(1)选择S函数作为操作函数。这是因为S函数具有平滑、单调和非线性等数学特性,这与进化优化特性一致［13-14］。(2)当评价的不确定性比较大时,采用较大的交叉概率增强新个体的数量;当评价的不确定性较小时,采用较小的交叉概率加快算法收敛。由此,设计交叉算子为:

其中,k1是调节系数。

变异操作同样会为算法带来新个体,变异算子的设计主要基于以下2个方面:(1)当评价的不确定性比较大时,为了增加种群的多样性,此时变异概率应该较大;当评价的不确定性较小时,采用较小的变异概率加快算法收敛。(2)在进化后期,为了保证算法收敛,应使变异概率降低。为此将变异概率限定在区间(0,0.5)内［15-16］。由此,设计变异算子为:

其中,k2是调节系数。

3 算法步骤

本文算法过程如下:

(1)设定种群进化控制参数,初始化进化种群x(t)。

(2)评价进化个体,给出个体适应值f(xi(t))。

(3)依据式(3)和式(5)计算个体适应值的不确定度θ(xi(t))和收敛率δ(xi(t))。

(4)按轮赌法选择个体。

(5)按式(6)和式(7)进行交叉和变异操作,产生子代种群x(t),令t=t+1。

(6)判断进化结果是否达到满意程度,若满足,转步骤(7);否则,转步骤(2)。

(7)输出最优进化个体,算法终止。

4 实验结果与分析

4.1 实验参数设定

本文实验对象是服装进化设计系统。该系统用18 Byte二进制串对染色体编码。上衣由二进制串的前5 Byte表示,款式由6 Byte～10 Byte表示,颜色由11 Byte～14 Byte表示,裙子的颜色由15 Byte～18 Byte表示。上衣和裙子款式各有32套,名称分别是从0～31的整数,对应于二进制编码的十进制值［9-10］。表1给出了服装颜色与款式的编号。

表1 服装颜色与款式编号

为了说明本文算法性能,算法的比较对象是传统交互式遗传算法(T-IGA)。本文算法和T-IGA均采用轮赌法选择算子。T-IGA采用单点交叉和单点变异,交叉概率和变异概率均为固定值,根据经验, T-IGA的交叉和变异概率如表2所示。个体适应值评价范围是0～100,最大进化代数为20,种群规模为8。当进化已经收敛或人对进化结果满意时,手动终止种群进化。在式(6)和式(7)中,参数k1=k2=10。

表2 T-IGA的交叉概率和变异概率

4.2 结果分析

分别对本文算法和传统交互式遗传算法,按设定参数独立运行20次,对比性能指标包括进化代数、满意解数目和耗时等,其中,满意解是指每代中精确数适应值最高和次高的个体。2种算法的进化代数统计如图1所示。

图1 2种算法进化代数统计

由图1可以看到,本文算法的进化代数较少。算法获得满意解的统计情况如图2所示,可以看出,本文算法获得的满意解数目较多。主要原因是采用基于适应值不确定度和收敛率的自适应交叉变异操作使种群多样性增强,算法可以利用的信息也更多,这也说明了采用二元排序分析适应值的有效性。

图2 2种算法满意解数对比

结合图1和图2可以看出,本文算法可以在较少的进化代内获得较多的满意解数目,这加快了算法收敛速度,显示了较好的进化优化能力。最后,统计算法的耗时情况为T-IGA算法为9 min 26 s;本文算法为7 min 44 s。由于本文算法的进化代数少,因此每次实验的耗时也比较少。而耗时减少意味着缩短了人的操作时间,自然有效降低了人的操作负担。

5 结束语

本文提出一种包含交叉和变异操作的交互式遗传算法。与同类算法相比,其创新点主要体现在如下3个方面:(1)利用二元排序分析个体适应值的不确定性,从相邻个体适应值中抽取适应值不确定度;(2)采用收敛率衡量种群的收敛情况;(3)采用不确定度和收敛率设计自适应交叉算子和变异算子。将算法应用于服装进化设计系统,结果表明,该算法在获得满意解和缩短耗时等方面能取得较好的效果。今后将继续研究交互式遗传算法优化过程中适应值的变化规律,并依据适应值变化规律探寻提高算法性能的方法。

［1]Takagi H.Interactive Evolutionary Computation:Fusion of the Capabilities of EC Optimization and Human Evolution［J］.Proceedings of the IEEE,2001,89(9): 1275-1296.

［2]Takagi H,Ohsaki M.Interactive Evolutionary Computation Based Hearing Aid Fitting［J］.IEEE Transactions on Evolutionary Computation,2007,11(3):414-427.

［3]Ohsaki M,Takagi H,Ohya K.An Input Method Using Discrete Fitness Values for Interactive GA［J］.Journal of Intelligent&Fuzzy Systems:Applications in Engineering and Technology,1998,6(1):131-145.

［4]Gong Dunwei,Guo Gangsong,Lu Li.Adaptive Interactive Genetic Algorithms with Interval Fitness of Evolutionary Individuals［J］.Progress in Natural Science,2008,18(3): 359-365.

［5]Sun Xiaoyan,Gong Dunwei.Interactive Genetic Algorithms with Individual’s Fuzzy and Stochastic Fitness［J］.Chinese Journal of Electronics,2009,18(4):619-624.

［6]Gong Dunwei,Yuan Jie,Sun Xiaoyan.Interactive Genetic Algorithms with Individual’s Fuzzy Fitnesss［J］.Computers in Human Behavior,2011,27(5):1482-1492.

［7]胡晓辉,陈俊莲,张晓颖.改进的区间值模糊集交互式遗传算法［J］.计算机工程与应用,2010,46(28): 51-53.

［8]孙晓燕,任 洁,巩敦卫.基于半监督学习的变种群规模区间适应值交互式遗传算法［J］.控制理论与应用, 2011,28(5):610-618.

［9]巩敦卫,任 洁,孙晓燕.区间适应值交互式遗传算法神经网络代理模型［J］.控制与决策,2009,24(10): 1522-1530.

［10]孙晓燕,巩敦卫.自适应分区多代理模型交互式遗传算法［J］.控制与决策,2009,24(2):170-180.

［11]巩敦卫,陈 健,孙晓燕.新的基于相似度估计个体适应值的交互式遗传算法［J］.控制理论与应用,2013, 30(5):558-566.

［12]邓聚龙.灰理论基础［M］.武汉:华中科技大学出版社,2003.

［13]郭广颂,崔建锋.基于进化个体适应值灰度的自适应交互式遗传算法［J］.计算机应用,2008,28(10):2525-2528.

［14]郭广颂,何琳琳.基于区间适应值灰度的交互式遗传算法［J］.计算机工程,2009,35(14):233-235.

［15]郭广颂,李秀娟.基于离散适应值灰度的交互式遗传算法［J］.计算机工程与应用,2010,46(24):225-228.

［16]郭广颂,赵绍刚.基于个体适应值灰模型的交互式遗传算法［J］.计算机工程,2010,36(3):209-212.

编辑 刘 冰

Interactive Genetic Algorithm Containing Crossover and Mutation Operation

GUO Guangsong,WANG Yanfang
(School of Mechatronics Engineering,Zhengzhou Institute of Aeronautical Industry Management,Zhengzhou 450015,China)

The traditional interactive Genetic Algorithm(GA)can make user fatigue on optimizing the implicit performance index which affects the optimization quality and optimization efficiency.It is necessary to enhance the performance of interactive GA in order to apply it to complicated optimization problems successfully.The uncertainty of individual fitness is calculated based on the evaluation difference between the adjacent individuals;the convergence rate is abstracted according to the biggest information differences in evaluation sequence which reflecting the convergence of evolutionary population.Based on these,the probabilities of crossover and mutation operation of evolutionary individuals are presented.It makes the results more objective by guiding the evolutionary strategy through user preference information,and it allows a better exploration of the searching space and gives better findings compared with the traditional interactive GA(T-IGA).

Genetic Algorithm(GA);adaptive crossover;mutation probability;fitness value;interactive environment;uncertainty

郭广颂,王燕芳.包含交叉和变异操作的交互式遗传算法［J］.计算机工程,2015,41(3):182-185.

英文引用格式:Guo Guangsong,Wang Yanfang.Interactive Genetic Algorithm Containing Crossover and Mutation Operation［J］.Computer Engineering,2015,41(3):182-185.

1000-3428(2015)03-0182-04

:A

:TP399

10.3969/j.issn.1000-3428.2015.03.035

河南省基础与前沿技术研究计划基金资助项目(122300410295)。

郭广颂(1978-),男,副教授、硕士,主研方向:智能控制;王燕芳,副教授、硕士。

2014-03-17

:2014-05-07E-mail:guogs78@126.com