文档介绍：第四章计算智能
l 信息科学与生命科学的相互交叉、渗透和促进是现代科学技
术发展的一个显著特点
l 代表:生物信息学/计算智能
l 计算智能涉及神经计算、模糊计算、进化计算和人工生命等
l 创造、发明和发现是千万科技开拓者的共同品性和永恒追求
l 人类所有发明几乎都有其自然界的配对物
l 计算智能及其与人工智能的区别
(Bezdek,1992)计算智能取决于制造者提供的数值数据,
而不依赖于知识;人工智能则应用知识精品
第一节、进化计算
l 生物群种生存遵循“物竞天择、适者生存”的进化准则
l 进化过程的结果反映在个体结构上:染色体包含若干基
因,相应的变现性和基因型的联系体现了个体的外部特性
与内部机理的逻辑关系。生物通过个体的选择、交叉和变
异来适应自然环境
l 计算机方式:
染色体—个体;适应能力—个体数值
l 如何模仿生物来建立功能强大的算法,将其运用于复杂的
优化问题---成为研究热点
l 进化计算
包括遗传算法、进化策略、进化规划和遗传规划等
一、遗传算法
l 1975,Holland在其著作“Adaptation in natural
and artificial systems ”中首次提出遗传算法,现
已发展至较为成熟的阶段
l 基本概念
染色体(chromosome):细胞中的丝状化合物
基因(gene):DNA(脱氧核糖核酸)或RNA(核糖
核酸)长链结构中占有一定位置的基本遗传单位
基因座(locus):遗传基因在染色体中所占据的位置
等位基因(allele):同一基因座可能有的全部基因
基因型(genotype):某种生物所特有的基因及其构
成形式称为该生物的基因型
表现型(phenotype):某生物在环境中呈现出的相应性状成为
该生物的表现型
基因组(genome):一个细胞核中所有染色体所携带的遗传信
息的全体称为一个基因组
l 求函数最大值的优化问题
(求函数最小值也类同)
(1)描述
(2)关系图
其中为决策变量,
ì max f(X) X = [x1,x2 ,L,x n ]'
ï 为目标函数
í. X Î R f(X)
ï U是基本空间
î R Í U
满足约束条件的解X称为可行解,集合R称为可行解集
l 概念的实例解释
l 基本遗传算法
(simple ic algorithm,Goldberg)
仅适用选择、交叉和变异算子,是其它遗传算
法的基础和基本框架
(一)基本遗传算法的要素
(1)染色体编码方法
固定长度的二进制符号串表示群体中的个体,等位基因
{0,1},初始群体中各个体的基因值可采用均匀分布的随
机技术产生。
(2)个体适应度评价
以个体适应度成正比的概率确定每个个体遗传到下一代群
体中的机会多少,预先确定好由目标函数值到个体适应度
之间的转换规则
(3)遗传算子
选择运算:比例
交叉运算:单点交叉
变异运算:基本位变异或均匀变异
(4)运行参数
群体大小:20~100
终止进化代数:100~500
交叉概率:~
变异概率:~
l 运行参数对遗传算法的求解结果和效率有一定的影响
l 目前尚无合理选择它们的理论依据
l 须反复试算确定
基本遗传算法描述
l 定义为一个8元组
SGA=(C,E,P0,M,Φ, Γ,Ψ,T)
式中C:个体的编码方法
E:个体适应度评价函数
P0:初始群体
M:群体大小
Φ:选择算子
Γ:交叉算子
Ψ:变异算子
T:遗传算法终止条件
Initialize P(0)
t=0
While(t<=T) do
for i=1 to M do
Evaluate fitness of P(t)
end for
for i=1 to M do
Select operation to P(t)
end for
for i=1 to M/2 do
Crossover operation to P(t)
end for
for i=1 to M do
Mutation operation to P(t)
end for
for i=1 to M do
P(t+1)=P(t)
end for
t=t+1
End while
(二)基本遗传算法的实现
1、个体适应度评价
l 个体适应度的大小确定该个体被遗传到下一代群体中的概
率
l 要求:适应度必须为非负
方法1:对求目标函数最大值的优化
(实际优化问题中的目标函数值有