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