交互式遗传算法入门

1、1.3 交互式遗传算法交互式遗传算法也可称为人机交互进化优化算法，即在进化计算过程中，根据需要，人通过与计算机的交互，实现对进化过程的干预和引导，以解决传统遗传算法无法解决的如式(1.1)所示的一类隐式性能指标优化问题。由于人的参与，使得遗传算法得到了很好的扩展，不再简单依赖于适应度函数等，从而大大拓宽了传统遗传算法的应用领域。若无特殊说明，后续讨论均针对式(1.1)所示的问题进行研究。1.3.1 交互式遗传算法的起源、发展、原理1986年，Dawkins最早提出了交互式演化算法的思想，并用于生物图形的生成1。20世纪90年代初，日本学者Takagi在Dawkins算法思想的基础上，对交互式演

2、化算法从应用和理论研究等方面，开展了大量卓有成效的工作24，并逐渐引起了广大学者对交互式进化优化算法的关注。交互式进化优化算法主要有狭义和广义两种定义24。其中，狭义定义认为“交互式进化优化算法是一种以人的主观评价作为进化个体适应值的进化优化方法”。该定义把人的主观评价作为进化个体适应度赋值的依据;广义定义认为“交互式进化优化算法是一种有人机交互过程的进化优化方法，这种人机交互过程不仅仅是对个体进行适应度赋值，还包括其他更多的人对进化过程的干预，如优势个体的选择、交叉对的选择等”25。我们这里仅讨论狭义定义模式下的交互式进化优化算法，即交互式遗传算法，该算法形象表述如图1.2所示，流程如图1.

3、3所示。图1.2 交互式遗传算法示意图 图1.3 交互式遗传算法流程图从上述图示中可知，与传统遗传算法相比，交互式遗传算法可分割为两个模块:用户评价模块和种群进化模块。其中，用户评价模块即为传统遗传算法中适应值计算模块，主要通过人机交互，由用户给出进化个体适应值。具体地说，就是计算机将进化个体的表现型呈现给用户，如服装、工程设计草案、一段乐曲等，然后用户根据个人认知和偏好，通过交互界面以打分的形式给出进化个体适应值，代替传统遗传算法中基于显式适应度函数的适应值计算;种群进化模块由计算机完成传统进化过程，包括编码、解码、种群初始化、基于用户赋予的进化个体适应值的选择，以及相应的进化算子，如遗传算

4、法中的交又（重组）、变异算子。在每个进化代中，上述两个模块进行交互，并基于交互结果，实施进化操作，重复该过程，直至算法满足设定的终止条件，如找到满意解或达到设定的进化代数等。与传统遗传算法相比，交互式遗传算法在对进化个体的评价中融合了人的偏好、直觉、情感、心理特征等主观因素，使得该算法在依赖现有遗传算法的基础上，又有其白身的特点，主要体现在如下三个方面。个体适应值具有不确定性 交互式遗传算法建立在被优化变量空间向人的心理空间映射的基础上,人直接评价由个体基因型决定的个体表现型,从而为进化个体赋予适应值。在进化过程中,评价者会对评价对象逐渐获得更多的知识.,使得其认知不断发生变化。由于用户对个体

5、的评价建立在用户对被评价对象认知的基础上,那么认知的不确定性和渐进性,将使得进化个体适应值具有不确定性。个体评价过程具有难持久性 交互式遗传算法面向一类难以用精确定义的函数描述的优化问题，而直接由人评价优化方案的优劣。与传统遗传算法中计算机不知疲倦地计算进化个体适应值的过程相比，频繁的人机交互和大量的评价需求，将使得评价者极易疲労，用户评价疲劳将导致评价不可信，甚至不可用，使得算法不得不终止。在交互式遗传算法中，一般人参与评价的进化代数不多于30，显然，与传统選传算法相比，该进化过程较短暂，难以持久，且评价个体总数量有限。优化结果具有非唯一性 交互式遗传算法优化结果的非唯一性表现在如下两个方面

6、。一是用户评价的偏好导致优化结果具有一定个性。因为不同用户在对进化个体评价时基于其知识背景、文化趋向及个人喜好等诸多因素，这些因素最终表现为用户对个体的偏好。二是由于人在心理空间上可以区分的系统输出有一定限制，即很难区分两个表现型差异细微的个体，因此交互式遗传算法的优化解是一个区域优化区域，而不像传统遗传算法那样是一个或多个离散点。但对图像生成、乐曲创作、数据挖掘及其他复杂问题的优化来讲已经能够满足要求。综上所述，由于人的参与，使得交互式遗传算法相对于传统遗传算法具有难以比拟的复杂性和不确定性。下面，我们将从应用和理论方法研究上，阐述近年来交互式遗传算法的研究现状，以发现其存在的不足，进而确定

7、我们的研究内容，并给出解決方法。1.3.2 交互式遗传算法的研究现状IEEE Transactionson Evolutionary Computation等关于进化计算的国际学术期刊大量报道了交互式遗传算法的研究成果。Gneticand Evolutionary Computation Conference（遗传与进化计算会议）从2002年开始开设关于交互式进化计算的专题研讨会。而关于交互式遗传算法在各领域的应用成果也不断涌现，如Parmee等将交互式遗传算法与工业设计相结合，提出交互式优化设计系统，并与多目标优化、Agent决策支持等方法结合，广泛应用于桥梁设计、工业产品设计、概念软件设计

8、等26,27，进一步丰富了交互式遗传算法的理论与应用成果。交互式遗传算法是应实际优化问题需要而发展起来的一种进化优化方法，因此它自诞生之日起就具有鲜明的应用背景和广阔的应用前景。交互式遗传算法的应用主要集中在艺术、工程设计和教育等领域，下面将分别介绍交互式遗传算法在各领域的应用情况。图像处理与检索 交互式遗传算法广泛应用于图像处理和检索中。最早的应用是Dawkins的生物图形，他用L系统表示生物图形的递归过程，通过主观选择L系统的输出和基因变异绘制出类似生物的二维计算机图形1。Sims在遗传规划中由人评价数学方程生成的计算机图形，并不断进化该数学方程，从而使计算机图形更加美观28。Takeka

9、ta用交互式遗传算法调整3D设备中触觉感知器的参数，无需专业技术知识就可使触觉设备的参数满足使用者的要求29。Li等把交互式遗传算法用于图像色彩的转换，转换后的图像色彩能够满足用户情感和心理需要30。Rodri9uez等将交互式遗传算法应用于建筑物外观颜色的设计中，考虑用户评价疲劳，利用交互式遗传算法和神经网络相结合，构造用户对颜色的偏好模型31。Cho等把交互式遗传算法应用于基于内容的图像检索中，将人的直觉和情感与检索内容融合，搜索出用户满意的图片32。Miguel等将基于内容的图像检索与用户的相关反馈相结合，在混合交互式遗传算法的优化框架下，找到用户满意度高的图像33。语言和声音处理 Fo

10、rmiga等把交互式遗传算法用于文本到语言合成系统的单元权重调节中34。Sato等利用交互式遗传算法合成语音，通过进化影响语音的韵律参量改变音色，反映出平和、愤怒、快乐等情感35。Rho等基于用户相关反馈原理，设计音乐信息检索，给出根据用户满意程度进行排序的结果36。Takagi等将交互式遗传算法用于助听器的调整，根据用户对声音效果的评价在线调整助听器的各参数，直到用户满意为止37。另外，交互式遗传算法还用于音乐旋律和节奏的生成，创作个性化乐曲38。工业产品和艺术创作设计 任何设计过程都需要设计者的广泛参与，包括确定设计主题、评判设计产品或作品是否满足需求。在工业设计中，李圣清等通过交互式遗传

11、算法优化电路板中元器件的布局，使整体结构既美观又不影响电路的功能39。Kamalian等把交互式遗传算法用于微电机系统的设计，通过人评价微电机的结构特性设计其参数40。Ono等将交互式遗传算法和非交互式遗传算法相结合，进行二维编码条的装饰性设计41。Meghna等提出基于实例的少用户疲劳交互式遗传算法，并将其应用于地下水监控系统的设计42。Byren等将交互式遗传算法直接应用于产品设计的友好交互界面和交互工具的设计中，使得用户可以直接通过该界面与满意方案的编码进行交互，可有效减轻其评价负担43。Kowa11w等则研究如何在交互式遗传算法的框架下，更好地激发用户的创造性，以进行富有新意的设计44

12、。教育和娱乐 交互式遗传算法可以给使用者提供写作线索或灵感，还能够给学习者提供参考。交互式遗传算法已经成功地应用于3D计算机图形的辅助教育，使用者通过人机交互方式可以学习3D图形的绘制方法，掌握各种计算机绘图技巧45。交互式遗传算法可以激发使用者的创新思维，Kuriyama等开发了供少儿使用的写作支持系统46。此外，Goldberg等开发了不确定环境下的分布式创新与可扩展合作(distributed innovation and scalable co1laboration in uncertain set-things，DISCUS)产品设计系统，利用交互式遗传算法的优化结果不断激发人的创造

13、思维47。机器人控制 1992年，Lewis等将交互式遗传算法用于控制一个六腿机器昆虫48这是交互式遗传算法第一次用于控制工程。Suga等用交互式遗传算法训练机器人的表情和沟通能力，使机器人个性化并能够快速适应周围环境49。Moshaiov等用交互式遗传算法进行机器人路径规划，系统采用两层模型，底层用计算机直接计算路径长度，上层通过人的评价提供用户对机器人经过地点的偏好信息，从而实现个性化的路径规划50。交互式遗传算法在上述各领域的成功应用，彰显了算法的勃勃生机。另外，在应用过程中，人们发现交互式遗传算法核心问题的有效解决尤为必要，如个体适应值评价的不确定性、用户疲劳导致的评价过程的难持久性等

14、。因此，进一步研究交互式遗传算法理论与关键技术，有效解决其核心问题，从而进一步扩大交互式遗传算法的应用领域，具有重要的理论意义和实际应用价值。根据交互式遗传算法的特性，其理论方法研究主要可分为两类：一是研究进化个体适应值评价的不确定性；二是减轻用户评价疲劳，改进算法搜索性能的研究。交互式遗传算法中用户对进化个体的评价具有认知不确定性和随机不确定性，对这些不确定性的研究，可分为如下两类。将不确定性视为噪声信号 这些不确定性对进化个体适应值而言可视为噪声信号:_对于交互式遗传算法是个极大的扰动,甚至可能导致算法无法在用户疲劳时找到、術意解24 。 由于人的评价具有强烈的主观意识,因此在评价过程中难

15、以避免目标偏好的漂移甚至改变。为了尽可能保持用户偏好一致,Sastry等基于用户评价获得各个体偏序,程据偏序值基于多目标非占优思想,给出个体在种群中的全序,再基于支持向量机获得适应度函数的代理模型5',52。该算法考虑了维持用户评价标准的一致性问题,从而在收敛速度、搜索性能等各方面得到极大改进。但算法只是被动地维持评价備好,没有考虑其他干扰信号,如日标的不明确性对用户偏好的影响、评价疲劳对偏好的影响等。 Breukelaar 等给出了交互优化框架下多种优化策略的比较，基于色彩选择优化实例，说明了交互式遗传算法中存在的噪声问题，指出选择过程中用户评价偏好及疲労造成的噪声对算法性能有极大的

16、破坏性，因此在交互式遗传算法中，应考虑建立用户评价的噪声模型、去噪策略和用户监视策略等，并根据优化结果说明噪声模型与时问，以及用户心理空间和实际优化目标问的距离有关，同时说明用户在评价过程中若采取一些策略也会对算法性能有影响53。但其仅仅根据某个优化实例，给出定性结论，没有给出解决方法等。采用不确定数表示不确定性 除了上述处理进化个体评价不确定性的方法外，改变传统的采用精确数表示进化个体适应值的方法也是研究方向之一。实际上，用户对进化个体的认知具有模糊性和渐进性，再加上评价过程中多种因素的影响，使得评价结果具有随机性。这样一来，用具体数值表示进化个体适应值就不能很好地反映用户对评价对象认知的规

17、律，而强行要求用户给出具体的适应值会加速人评价的疲劳。这正是本书即将讨论的第一部分内容，将在第24章对上述策略进行详细阐述。其次，关于用户评价疲劳问题。由于交互式遗传算法需要人参与进化过程并给出进化个体适应值，与计算机计算相比，人评价具有易疲劳性，使得交互式遗传算法一般只能采用小的种群规模和少的进化代数，从而影响了算法的捜索性能。因此，減轻用户评价疲劳、改进算法性能一直是交互式遗传算法理论方法研究的重点和热点24，目前国内外的研究主要包括如下三个方面。基于代理模型的适应值估计 利用进化个体适应值的估计值代替人的评价，.减少人评价进化个体的数量，从而減轻人的疲劳。Biles和周勇等采用人工神经网

18、络学习人的智能评价，并在适当时机用神经网络估计进化个体的适应值，减少人对进化个体评价的次数54，55。Sastry等在对用户评价进行排序的基础上，利用支持向量机构造用户认知的代理模型，并在后续进化中应用其实现交互式遗传算法的大种群规模进化51。Rodriguez在建筑图外观颜色设计系统中，利用神经网络构建适应度模型，以拟合用户认知，从而减轻用户疲劳31。加快算法收敛 通过加快算法收敛以降低进化代数来减轻人的疲劳。王上飞等采用支持向量机重构父代种群的个体，以扩大优良父代个体的范围，从而加快算法收敛，减轻人的疲劳56。胡静等将粗糙集理论应用于进化过程中的信息提取，以提高算法的收敛速度57。蒋姗姗等

19、通过对前几代进化种群遗传操作的结果进行归纳计算，得到人的特异性偏好，并以此指导选择、交叉和变异等进化操作，从而加快算法的收敛速度58。增强算法局部搜索 通过缩小搜索区域提高算法的局部搜索能力。巩敦卫等在进化种群满足一定条件时将搜索区域缩小，并在缩小后的区域上重新生成进化种群，以提高算法的局部搜索能力59。郝国生等将搜索区域划分为满意域、禁忌域和未知域，通过将求同算子和求异算子作用于进化个体，从而进化上述区域，最终使得满意域不断减小，从而提高算法的局部搜索能力60。综上所述，我们可以看出，在短短的二十年时间里，虽然交互式遗传算法的应用和理论方法研究均取得了长足进展，但仍存在大量问題需要进一步解决

20、。1.3.3 交互式遗传算法存在的不足交互式遗传算法的已有研究尚存在如下四点不足。1)对交互式遗传算法评价的不确定性研究不够到日前为止，已有交互式遗传算法解决隐式性能指标优化问题时，用户给出的进化个体适应值均为具体数值(连续或者离散数)，这不符合人的认知规律，不能有效处理交互式遗传算法中存在的模糊、随机等不确定性信息。2)对交互式遗传算法用户认知模型的构建和应用研究不够为了解决用户疲劳问题，常常采用构造用户认知代理模型的方法，该方法首先获取一定量的用户对进化个体的评价知识，再利用机器学习的方法对该认知知识建模，最后将该模型视为个体适应度函数，利用其估计进化个体适应值，代替用户对部分或者全部进化个体进行评价，显然，该过程本质是一个知识获取和机器学习的过程。在已有研究成果中，研究重点均在于利用若干进化过程中的数据采用监督学习机制，构建认知模型，没有考虑如何提取知识，以及采用哪类机器学习方法学习已获得的知识更有效等问题。3)在考虑评价不确定性的情况下，对减轻用户疲劳的方法研究不够如前所述，利用区间数表示进化个体适应值后，用户仍需确定两个区间端点，大量的人机交互将极易导致用户疲劳。同样的，如果采用其他不确定数表示进化个体适应值，仍需考虑减轻用户疲劳的策略。若仍考虑采用构建认知代理模型的策略，则与传统的精确数模型将有较大的差别，新模型如何实现?这些目前都还处于研究的起始阶段