基于满意域和禁忌域的交互式遗传算法.pdf

第3 4 卷第2 期 2 0 0 5 年3 月 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y V 0 1 ．3 4N o ．2 M a r ．2 0 0 5 文章编号1 0 0 0 1 9 6 4 2 0 0 5 0 2 0 2 0 4 0 5 基于满意域和禁忌域的交互式遗传算法 郝国生，巩敦卫，史有群，王莉 中国矿业大学信息与电气工程学院，江苏徐州2 2 1 0 0 8 摘要针对交互式遗传算法中用户易疲劳问题，提出求同算子与求异算子，基于此给出搜索空间 的划分及演化方法，提出基于满意域和禁忌域的交互式遗传算法，该方法可以引导遗传算法在不 断缩小的空间中产生新个体，从而提高收敛速度，减少进化代数，达到减轻用户疲劳的目的．利用 此方法进行服装设计的实验结果表明，该方法可以有效解决用户疲劳问题． 关键词交互式遗传算法；满意域和禁忌域；基因意义单元；求同算子与求异算子 中图分类号T P1 8文献标识码A I n t e r a c t i v eG e n e t i cA l g o r i t h mB a s e do n L a n d s c a p eo fS a t i s f a c t i o na n dT a b o o s H A OG u o - s h e n g ，G O N GD u n w e i ，S H IY o u - q u n ，W A N GL i S c h o o lo fI n f o r m a t i o na n dE l e c t r i c a lE n g i n e e r i n g ，C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ， X u z h o u ，J i a n g s u2 2 1 0 0 8 ，C h i n a A b s t r a c t T h ec o n c e p to fl a n d s c a p eo fs a t i s f a c t i o na n dt a b o o sa r eg i v e na i m i n go nt h ep r o b l e mo f u s e rf a t i g u ei ni n t e r a c t i v eg e n e t i ca l g o r i t h m I G A ．T h ec o m m o no p e r a t o ra n dd i s t i n c to p e r a t o ra r e p r o p o s e d ，a n dt h em e t h o d o l o g yo fs e a r c hs p a c ep a r t i t i o na n de v o l u t i o ni sp r e s e n t e d ．T h ei n t e r a c t i v e g e n e t i ca l g o r i t h mb a s e do nl a n d s c a p eo fs a t i s f a c t i o na n dt a b o o si sp u tf o r w a r d ．T h ea l g o r i t h mc a n p r o d u c en e wi n d i v i d u a l si nc o n t i n u a l l ys h r i n k i n gs p a c e ．H e n c e ，t h ec o n v e r g e n c ei ss p e e d e d ，t h e e v o l u t i o nt i m ei sr e d u c e da n du s e rf a t i g u ei sa l l e v i a t e d ．T h ee x p e r i m e n t a lr e s u l t sf r o mf a s h i o nd e s i g n s h o wt h a tt h i sm e t h o di Se f f i c i e n t ． K e yw o r d s i n t e r a c t i v eg e n e t i ca l g o r i t h m ；l a n d s c a p eo fs a t i s f a c t i o na n dt a b o o s ；g e n eu n i to fs e n s e ； c o m m o no p e r a t o ra n dd i s t i n c to p e r a t o r 交互式遗传算法 I G A 是一种基于人的主观 评价得到进化个体适应值的遗传算法 G A [ 1 ] ，它 通过交互获得个体适应值，以充分体现用户的偏好 和情感[ 2 ] ．由于交互式遗传算法将人的智能评价与 遗传算法有机结合，不需要建立被优化系统的显式 性能指标函数，因此大大扩充了遗传算法的应用范 围．白2 0 世纪9 0 年代被提出以来，交互式遗传算 法已成功地应用到服装设计、乐曲创作、语言处理 与韵律控制、知识获取与数据挖掘等领域[ 2 嵋] ． 在交互式遗传算法中，对个体适应度的赋值由 人 用户 来完成，与无疲劳的计算机相比人具有易 疲劳的特点，又由于人机交互界面和系统输出特性 的限制，所以进化种群的规模不能太大，进化代数 不能太多，一般进化种群规模不超过1 0 ，进化代数 不超过2 0 D ] ． 目前，影响交互式遗传算法广泛应用的主要障 碍是当进化代数较多时，用户容易疲劳，这已经成 为限制交互式遗传算法进一步扩大应用范围的瓶 颈[ 1 J ] ．针对这一问题，本文提出了基于满意域和禁 忌域的交互式遗传算法．该算法的思路是在进化 收稿日期2 0 0 4 一0 2 1 6 基金项目国家自然科学基金项目 6 0 3 0 4 0 1 6 作者简介郝[ 驰4 1 9 7 2 一 ，男，河北省万全县人，硕士研究生，从事进化计算、并行计算方面的研究． 万方数据 第2 期 郝国生等基于满意域和禁忌域的交互式遗传算法2 0 5 过程中，一方面基于历史信息将搜索空间划分为满 意域、禁忌域和未知域，另一方面利用搜索空间划 分引导遗传搜索的进行．该方法不仅利用了历代的 最优和最差个体，而且利用了个体的编码．服装设 计应用证明了该方法的高效率． 1求同算子与求异算子 本节首先给出基因意义单元定义，然后给出求 同算子与求异算子的定义及相关概念． 1 ．1 基因意义单元 定义1设个体基因编码为C ，C 。⋯C 。，其中若 干位编码组合代表个体的一个属性．我们称能且只 能代表一个含义的基因编码段为一个“基因意义单 元”，将个体编码的第i 个基因意义单元记为U 。． 设U I 编码长度为m ，采用K 进制或字符集位 串，则u i 的取值就有K “种． 显然在各基因意义单元相互独立时，搜索空间 S 是U i 的广义笛卡尔积，即S U ，X U 。⋯X U 。， 其中n 是S 中个体的基因意义单元数目． 用户在交互式遗传算法中对个体进行评价，度 量个体的表现型与情感空间的距离，而个体的表现 型，决定于由各个基因意义单元取值组合而成的个 体的基因型．用户在历代选择最优个体，必然含有 用户满意的基因意义单元取值．同理，用户在历代 选择最差个体，也必然包含着用户不满意的基因意 义单元取值． 1 ．2 求同算子 定义2 把用于求不同个体的同一基因意义 单元含有共同取值的方法称为求同算子，记作o ． 称参与求同的个体数目为求同数． 对长度为1 ，取值为二进制串的同一基因意义 单元的2 种取值a 和b ，a Q b 所有可能及结果如表 1 所示． 表1求同算子作用于二进制串结果 T a b l e1R e s u l to fc o m m o no p e r a t o r so nb i n a r ys t r i n g 其中，* 表示取值不同． 对于个体基因编码求同，例如 0 1 0 0 1 ⋯⋯ C 1 0 0 1 o 0 1 0 1 0 ⋯⋯ 1 0 0 1 0 1 * * * ⋯⋯ 1 0 0 1 ，其中 表示一个基因意义单元． 1 ．3 求异算子 定义3把用于求不同个体同一基因意义单 元含有不同取值的方法称为求异算子．记作“O ”． 在a b 中，称a 为被求异值，b 为求异值． 对长度为l ，取值为二进制串的同一基因意义 单元的2 种取值a 和b ，a O b 所有可能及结果如表 2 所示． 表2 求异算子作用于二进制串结果 T a b l e2R e s u l to fd i s t i n c to p e r a t o ro nb i n a r ys t r i n g a01 10 b 0101 a O b ** 10 显然，求同算子和求异算子运算的单位是基因 意义单元． 2 满意域和禁忌域的定义、创建及演化 2 ．1满意域和禁忌域的定义 定义4 在搜索空间s 中，称由用户满意的个 体P “所组成的集合s “为满意域，由不满意的个体 P 。所组成的集合S 。为禁忌域，满意域和禁忌域之 外的集合为未知域S 。，即S 。- - - - S S b S ，． 显然，满意域、禁忌域和未知域是搜索空间的 一个划分．在遗传搜索过程中，上述划分是动态变 化的在进化代数t 一0 时，所有个体适应值都未 知，满意域和禁忌域中个体数目均为0 ，未知域占 据整个搜索空间；随着用户不断筛选出最优、最差 和较差个体，满意域和禁忌域不断扩大，而未知域 不断缩小；在进化的结束阶段，满意域中非最优个 体不断被淘汰，而未知域中的个体不断被用户筛选 到禁忌域中，此时满意域和未知域不断缩小，禁忌 域不断扩大． 交互式遗传算法的过程，就是局部最优解不断 逼近全局最优解，而局部最差解和较差解不断被淘 汰的过程． 2 ．2 求同群 求同数对于求同结果有较大的影响．表3 是对 编码长度为1 2 ，基因意义单元长度为2 的二进制 编码个体进行求同操作时求同数分别取2 和3 的 结果．显然，a 1 0 a 2 的基因意义单元广义笛卡尔积 对应个体数目为2 2 4 ，而a l o a 2 0 a 3 对应个体数 目为2 4 1 6 ． 为了建立、更改满意域和禁忌域，需要求同算 子多次按不同的求同数作用于最优和最差个体，以 确定各基因意义单元取值．设求同算子1 3 ． n ≥2 次 作用于进化个体的求同数为m i i - - l ，2 ，⋯，n ，则 称这多次求同为求同群．有2 种特殊类型的求同 群收缩性求同群和扩张性求同群．收缩性求同群 主要用于满意域，通过一定的淘汰规则对某些求同 万方数据 2 0 6中国矿业大学学报 第3 4 卷 结果淘汰，使满意域趋于收缩；扩张性求同群主要 用于禁忌域，通过衍生规则保留求同结果，使禁忌 域趋于扩张． 表3 不同求同数的求同结果 T a b l e3R e s u l to fd i f f e r e n tn u m b e ro fc o m m o no p e r a t o r a l a 2 a 3 1 0 0 1 O O 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 a l o a 2 1 0 0 1 0 0 * * 0 1 0 1 a l o a 2 0 a 3 1 0 0 1 * * * * 0 1 0 1 2 ．3 满意域的创建及演化 满意域演化的过程是求同算子作用于历代最 优个体逐渐确定全局最优个体各基因意义单元取 值的过程． 当进化代数第1 次达到满意域求同数时，求同 算子作用于历代最优个体，得到各基因意义单元取 值，此时满意域创建，其包含的个体数目为各基因 意义单元的广义笛卡尔积包含的记录数． 满意域的演化过程分为2 个主要阶段，即个体 数目增长阶段和减小阶段．随着进化代数的增加， 满意域中个体数目增多，属于满意域增长阶段．随 后基因意义单元的新值淘汰旧值，当新增进化个体 数目小于被淘汰的数目时，满意域开始进入减小阶 段．但在减小阶段，由于变异算子的作用，进化跳出 局部最优束缚，会出现短暂的增长情况． 满意域的演化采用收缩性求同群．淘汰规则 是当满意域中同一基因意义单元取值不惟一时， 则以最近取值作为用户满意的取值，因为最近的更 能反映用户最新的偏好． 显然，满意域演化过程中，其减小的速度与求 同数有关，求同数越大，减小的速度越慢．但由于淘 汰规则作用于满意域，其总的趋势是不断减小． 综上所述，满意域的演化过程有以下3 个特 点1 逐步逼近最优解；2 规模先增加后减小； 3 总的趋势是不断减小． 2 ．4 禁忌域的创建及演化 禁忌域是对历代最差个体进行求同以及对同 一代的最优和最差个体求异的结果． 在进化代数第1 次达到禁忌域求同数时，求同 算子作用于历代最差个体，得到各基因意义单元取 值，此时禁忌域创建，其包含的个体数目为各基因 意义单元的广义笛卡尔积包含的记录数． 禁忌域的演化过程是单调增加，即未知域个体 和满意域个体不断进入禁忌域的过程．这种增加源 于两个运算1 求异算子作用于同代的最差个体 P 。和最优个体P “，即P 。④P b ；2 求同算子作用于 历代最差个体P 。 t 1 ，P 。 t 2 ，⋯⋯，即P 。 t 1 O P 。 t 。 o ⋯⋯．这2 个运算可以得到禁忌域更多的 基因意义单元取值，从而可以确定更多的禁忌域个 体． 禁忌域的演化采用扩张性求同群．其衍生规则 是在基因意义单元取值满足禁忌域与满意域的交 集为空集的前提下，求同结果累积补充禁忌域． 禁忌域增长速度与4 个因素有关1 历代最 差个体相同基因意义单元取不同值的数目，该值越 大，禁忌域增长得越快；2 求异开始代数，该值越 小，禁忌域增长得越快；3 同代最差个体和最优个 体之问的差异，差异越大，禁忌域增长得越快；4 求同数，求同数越小，禁忌域增长得越快． 但随着进化代数的增加，在选择和交叉算子作 用下，较优个体以指数速度快速占据种群中的大部 分[ 8 1 ．所以在进化后期，上述因素1 对禁忌域增长 的贡献会越来越小． 综上所述，禁忌域的演化过程的特点是不断增 长． 2 ．5 满意域和禁忌域在进化过程中的作用 满意域和禁忌域在进化过程中主要有以下作 用 1 满意域通过对禁忌域的影响间接限制非优 势个体的产生，禁忌域直接限制非优势个体的产 生，两者对遗传算法都产生了引导作用，使遗传算 法逐步逼近最优解． 2 满意域和禁忌域提高了遗传算法的“求精 能力”．可以通过逐步提高变异概率以保证遗传算 法的“求泛能力”C 9 ] ． 3 禁忌域的增长速度，可以作为进化速度的 一个指标．禁忌域增长得越快，遗传算法进化的速 度越好，在保证最优个体不丢失的前提下，进化的 性能也越好． 4 满意域和禁忌域有助于自适应地分层进 化．当某代所有个体某基因意义单元取值都相同 时，可以采用分层进化的方法，只对取值不完全相 同的部分编码段进化． 3 基于满意域和禁忌域的交互式遗传算法 模型及实现 基于满意域和禁忌域的交互式遗传算法模型 如图1 所示． 该模型主要由用户评估、系统记录最优最差个 体、遗传操作、检索、建立或更改搜索空间的划分等 组成． 万方数据 第2 期郝国生等基于满意域和禁忌域的交互式遗传算法2 0 7 图l基于满意域和禁忌域的I G A 模型 F i g ．1 M o d e lo f 。l a n d s c a p eo fs a t i s f a c t i o n a n dt a b o o sb a s e dI G A 当进化代数达到求同数的整数倍时，系统根据 历代最优个体和最差个体更改满意域、禁忌域和未 知域；在以后的进化过程中，对搜索空间划分的主 要操作有1 在生成新个体时，检索搜索空间的划 分，防止禁忌域中的个体进入新种群；2 进入下一 代之前，记录本代最优和最差个体，求同算子和求 异算子作用于历代最优和最差个体，完成对搜索空 间划分的更改． 由于新个体来源于满意域和未知域且满意域 不断缩小而禁忌域空间不断扩大，所以新个体产生 的空间会越来越小，遗传操作目标性更强，收敛速 度更快． 上述模型中，满意域和禁忌域的实现方法是 通过对历代最优和最差个体求同以及对同一代最 差和最优个体求异，得到相应的基因意义单元取 值，其广义笛卡尔积的记录就是对应于满意域和禁 忌域中的个体． 4 应用 我们以服装设计为例，验证基于满意域和禁忌 域的交互式遗传算法的效率及性能． 4 ．1 背景概述 交互式遗传算法主要用于适应值函数的表达 式不能显式给出的领域．服装设计的目标是给出 “好的设计”，然而，不同的人对“好的设计”有不同 的标准，所以得到一个统一显式表示的适应值函数 是不可能的，因此无法用传统的遗传算法进行服装 设计． 我们用V i s u a lF o x P r o8 ．0 初步建立了服装辅 助设计系统，用于验证基于满意域和禁忌域交互式 遗传算法的效率及性能． 将服装分为袖子、领口和腰身共3 部分．每一 部分用4 位二进制表示，其中2 位表示款式，另2 位表示颜色．编码共有6 个基因意义单元，每个长 度为2 ，搜索空间大小为2 1 2 4 0 9 6 ．交互式遗传算 法服装设计辅助系统将根据用户偏好和情绪从 4 0 9 6 个候选服装设计中选出“最好的设计”． 4 ．2 参数设置 设置满意域和禁忌域的求同数均为2 ． 求异开始条件的设定采用阈值．该阈值可以有 2 种1 百分比阈值．即同一代最优与最差个体取 相同值的基因意义单元占个体编码基因意义单元 总数的百分比；2 进化代数阈值．这里采用百分比 阈值，该阈值太大会增加用户疲劳，太小则可能会 丢失最优解．这里取值为3 3 ．3 3 ％． 种群规模取为8 ，交叉概率取值为0 ．5 ，变异概 率取值为0 ．1 ． 进化结束的条件可以设置为进化代数阈值，也 可以由用户手动终止．用户手动终止的好处是一方 面用户随时可以中断实验，而不必等待进化到规定 代数，另一方面，用户可以记录找到最优解所需要 的进化代数．这里设置为用户手动终止． 4 ．3 适应值赋值方法 T a k a g i 提出用离散适应值代替连续适应值以 减轻用户的心理压力[ 10 。．这里设置适应值取值范 围为o ～10 0 0 ，最小进制为5 0 ，因此，用户对服装 可以在2 0 个等级中进行评价． 用户对定性描述的理解比定量的理解更准确 些．因此，我们针对不同范围内的定量值给出相应 的定性描述．从图2 中可以看到，第5 个个体的评 价值是9 0 0 ，定性描述为“最漂亮”，而第1 个个体 的评价值是0 ，定性描述为“最不好看”． 图2 适应值赋值方法 F i g ．2M e t h o do fe v a l u a t i o nf o rf i t n e s s 4 ．4 性能分析 在实验过程中，用户在第1 代和第2 代选择的 最差个体编码都具有“黄色短裙”的表现型特征，由 此确定禁忌域中个体基因编码取值为 * * * * * * * * 1 0 1 0 ，从而，搜索空间缩小为 原来的9 3 ．7 5 ％ 2 1 22 8 ／z 1 2 ．其效率是相当可观 的． 为了验证该方法的效率，我们进行了比较实 验．将该方法与标准交互式遗传算法分别运用于服 万方数据 中国矿业大学学报第3 4 卷 装设计，进行比较． 两组实验都采用比例选择，取相同的交叉和变 异策略及概率，并且都采用上一代最优个体保留策 略，结束条件设为用户手动停止．记录下找到次最 优解时进化的代数，每种方法实验5 次．结果如表 4 所示． 表4 基于满意域和禁忌域的I G A 与标准I G A 比较 T a b l e4C o m p a r i s o nb e t w e e ns t a n d a r dI G Aa n d l a n d s c a p eo fs a t i s f a c t i o na n dt a b o o sb a s e dI G A 12345平均 标准I G A 3 84 32 53 83 53 5 ．8 基于满意域和禁忌域的I G A 1 31 01 291 41 1 ．6 进化代数 图3 满意域和禁忌域变化曲线 F i g ．3 T r e a dg r a p ho fs a t i s f a c t i o na n dt a b o o sl a n d s c a p e 从图3 可以看出满意域和禁忌域的演化情况 1 满意域的个体数目在第2 代迅速增长，而在第 五代时就很快收敛到局部最优解．在后来个体数目 有所增长，但没有超过第2 代的个体数目．2 禁忌 域始终不断增长．但越到后来，其增长速度越慢． 5 结束语 针对交互式遗传算法中用户易疲劳问题，本文 提出求同算子与求异算子，基于此给出搜索空间的 划分及演化方法，提出基于满意域和禁忌域的交互 式遗传算法，该方法可以引导遗传算法在不断缩小 的空间中产生新个体，从而提高收敛速度，减少进 化代数，达到减轻用户疲劳的目的．利用此方法进 行服装设计的实验结果表明该方法可以有效解决 用户疲劳问题． 需要说明的是，本文对搜索区域划分的方法也 适用于传统的遗传算法．不同基因意义单元组合成 新个体产生新的效果对用户评价影响的情况，以及 禁忌域的仓Ⅱ建和演化主要依靠历代的最差个体，每 代所有非最优个体都包含有禁忌信息，选择多少个 非最优个体，以及如何从这些个体中提取禁忌信 息，以加速收敛速度，都是我们需要进一步研究的 问题． 参考文献 [ 13 T a k a g i H ．I n t e r a c t i v ee v o l u t i o n a r yc o m p u t a t i o n F u s i o no ft h ec a p a b i l i t i e so fE Co p t i m i z a t i o na n d h u m a ne v o l u t i o n [ C ] ．S a nD i e g o P r o c e e d i n g so ft h e I E E E ．2 0 0 1 ．1 2 7 5 1 2 9 6 ． [ 2 ] K i mHS ，C h oSB ．A p p l i c a t i o no fi n t e r a c t i v eg e n e t i c t of a s h i o nd e s i g n [ J ] ．E n g i n e e r i n gA p p l i c a t i o n so f A r t i f i c i a lI n t e l l i g e n c e ，2 0 0 0 ，1 3 6 6 3 5 - 6 4 4 ． [ 3 3T o k u iN ．I b aH ，M u s i cc o m p o s i t i o nw i t hi n t e r a c t i v e e v o l u t i o n a r yc o m p u t a t i o n [ C ] ．M i l a n P r o c e e d i n g so f t h e3 r dI n t e r n a t i o n a lC o n f e r e n c eo nG e n e r a t i v eA r t ， 2 0 0 0 ．2 1 5 2 2 6 ． [ 4 ] M o r i t aT ，I h aH ，I s h i z u k aM ．G e n e r a t i n ge m o t i o n a l v o i c ea n db e h a v i o r e x p r e s s i o nb y i n t e r a c t i v e e v o l u t i o n a r y c o m p u t a t i o n[ C ] ．Y o k o h a m a P r o c e e d i n g so f t h e6 2 n d A n n u a lM e e t i n go fJ a p a n S o c i e t yf o rI n f o r m a t i o nP r o c e s s i n g ，2 0 0 1 ．4 5 4 6 ． [ 5 ] 1 w a s a k iT ，K i m u r aA ，T o d o r o k iY ，e ta 1 ．I n t e r a c t i v e v i r t u a la q u a r i u mE c ] ．G i f u P r o c e e d i n g so ft h e 5 t h A n n u a lC o n f e r e n c eo ft h eV i r t u a lR e a l i t yS o c i e t yo f J a p a n ，2 0 0 0 ．1 4 1 1 4 4 ． [ 6 ] O h s a k iM ，T a k a g iH ，O h y aK ．A ni n p u tm e t h o d u s i n gd i s c r e t ef i t n e s sv a l u e sf o ri n t e r a c t i v eG A [ J ] ． I n t e l l i g e n c eF u z z yS y s t e m ，1 9 9 8 ，6 6 1 3 1 1 4 5 ． [ 7 3T a k a g iH ，U n e m iT ，T e r a n oT ．P e r s p e c t i v eo n i n t e r a c t i v ee v o l u t i o n a r yc o m p u t i n g [ J ] ．A r t i f i c i a l I n t e l l i g e n c e ，1 9 9 8 ，1 3 5 6 9 2 - 7 0 3 ． [ 8 3 王正志，薄涛．进化计算[ M ] ．长沙国防科技大学 出版社，2 0 0 0 ．4 2 1 0 0 ． [ 9 ] 李敏强．遗传算法的基本理论及其在知识发现中的应 用研究[ D ] ．天津天津大学管理学院，2 0 0 0 ． [ 1 0 ] T a k a g iH ，O h y aK ，O h s a k iM ．I m p r o v e m e n to f i n p u ti n t e r f a c ef o ri n t e r a c t i v eg e n e t i ca l g o r i t h m sa n d i t se v a l u a t i o n [ c ] ．Z u k a v M e t h o d o l o g i e sf o rt h e C o n c e p t i o n ，D e s i g n ，a n dA p p l i c a t i o no fI n t e l l i g e n t S y s t e m sp r o c e e d i n g s ，19 9 6 ．4 9 0 - 4 9 3 ． 责任编辑姚志昌 万方数据