交互式遗传算法入门..docx

1.3交互式遗传算法交互式遗传算法也可称为人机交互进化优化算法，即在进化计算过程中，根据需要，人通过与计算机的交互，实现对进化过程的干预和引导，以解决传统遗传算法无法解决的如式(1.1)所示的一类隐式性能指标优化问题。由于人的参与，使得遗传算法得到了很好的扩展，不再简单依赖于适应度函数等，从而大大拓宽了传统遗传算法的应用领域。若无特殊说明，后续讨论均针对式(1.1)所示的问题进行研究。1.3.1交互式遗传算法的起源、发展、原理1986年，Dawkins最早提出了交互式演化算法的思想，并用于生物图形的生成[1]。20世纪90年代初，日本学者Takagi在Dawkins算法思想的基础上，对交互式演化算法从应用和理论研究等方面，开展了大量卓有成效的工作[24]，并逐渐引起了广大学者对交互式进化优化算法的关注。交互式进化优化算法主要有狭义和广义两种定义[24]。其中，狭义定义认为“交互式进化优化算法是一种以人的主观评价作为进化个体适应值的进化优化方法”。该定义把人的主观评价作为进化个体适应度赋值的依据;广义定义认为“交互式进化优化算法是一种有人机交互过程的进化优化方法，这种人机交互过程不仅仅是对个体进行适应度赋值，还包括其他更多的人对进化过程的干预，如优势个体的选择、交叉对的选择等”[25]。我们这里仅讨论狭义定义模式下的交互式进化优化算法，即交互式遗传算法，该算法形象表述如图1.2所示，流程如图1.3所示。图1.2 交互式遗传算法示意图图1.3交互式遗传算法流程图从上述图示中可知，与传统遗传算法相比，交互式遗传算法可分割为两个模块:用户评价模块和种群进化模块。其中，用户评价模块即为传统遗传算法中适应值计算模块，主要通过人机交互，由用户给出进化个体适应值。具体地说，就是计算机将进化个体的表现型呈现给用户，如服装、工程设计草案、一段乐曲等，然后用户根据个人认知和偏好，通过交互界面以打分的形式给出进化个体适应值，代替传统遗传算法中基于显式适应度函数的适应值计算;种群进化模块由计算机完成传统进化过程，包括编码、解码、种群初始化、基于用户赋予的进化个体适应值的选择，以及相应的进化算子，如遗传算法中的交又（重组）、变异算子。在每个进化代中，上述两个模块进行交互，并基于交互结果，实施进化操作，重复该过程，直至算法满足设定的终止条件，如找到满意解或达到设定的进化代数等。与传统遗传算法相比，交互式遗传算法在对进化个体的评价中融合了人的偏好、直觉、情感、心理特征等主观因素，使得该算法在依赖现有遗传算法的基础上，又有其白身的特点，主要体现在如下三个方面。个体适应值具有不确定性交互式遗传算法建立在被优化变量空间向人的心理空间映射的基础上,人直接评价由个体基因型决定的个体表现型,从而为进化个体赋予适应值。在进化过程中,评价者会对评价对象逐渐获得更多的知识.,使得其认知不断发生变化。由于用户对个体的评价建立在用户对被评价对象认知的基础上,那么认知的不确定性和渐进性,将使得进化个体适应值具有不确定性。个体评价过程具有难持久性交互式遗传算法面向一类难以用精确定义的函数描述的优化问题，而直接由人评价优化方案的优劣。与传统遗传算法中计算机不知疲倦地计算进化个体适应值的过程相比，频繁的人机交互和大量的评价需求，将使得评价者极易疲労，用户评价疲劳将导致评价不可信，甚至不可用，使得算法不得不终止。在交互式遗传算法中，一般人参与评价的进化代数不多于30，显然，与传统選传算法相比，该进化过程较短暂，难以持久，且评价个体总数量有限。优化结果具有非唯一性交互式遗传算法优化结果的非唯一性表现在如下两个方面。一是用户评价的偏好导致优化结果具有一定个性。因为不同用户在对进化个体评价时基于其知识背景、文化趋向及个人喜好等诸多因素，这些因素最终表现为用户对个体的偏好。二是由于人在心理空间上可以区分的系统输出有一定限制，即很难区分两个表现型差异细微的个体，因此交互式遗传算法的优化解是一个区域——优化区域，而不像传统遗传算法那样是一个或多个离散点。但对图像生成、乐曲创作、数据挖掘及其他复杂问题的优化来讲已经能够满足要求。综上所述，由于人的参与，使得交互式遗传算法相对于传统遗传算法具有难以比拟的复杂性和不确定性。下面，我们将从应用和理论方法研究上，阐述近年来交互式遗传算法的研究现状，以发现其存在的不足，进而确定我们的研究内容，并给出解決方法。1.3.2交互式遗传算法的研究现状IEEE Transactionson Evolutionary Computation等关于进化计算的国际学术期刊大量报道了交互式遗传算法的研究成果。GneticandEvolutionary ComputationConference（遗传与进化计算会议）从2002年开始开设关于交互式进化计算的专题研讨会。而关于交互式遗传