文档介绍:计算智能
人工智能-遗传算法
第1页
计算智能是信息科学和生命科学相互交叉前沿领域,是当代科学技术发展一个主要表达。计算智能包括神经网络、含糊逻辑、进化计算和人工生命等领域,它研究和发展反应了当代科学技术多学科交叉与集成主要发信息交换思想。交叉有单点交叉、两点交叉、还有一致交叉、次序交叉和周期交叉。单点交叉是最基本方法,应用较广。它是指染色体切断点有一处,例:
人工智能-遗传算法
第14页
(3)变异(Mutation Operator)
变异运算用来模拟生物在自然遗传环境中因为各种偶然原因引发基因突变,它以很小概率随机地改变遗传基因(表示染色体符号串某一位)值。在染色体以二进制编码系统中,它随机地将染色体某一个基因由1变为0,或由0变为1。
人工智能-遗传算法
第15页
若只有选择和交叉,而没有变异,则无法在初始基因组合以外空间进行搜索,使进化过程在早期就陷入局部解而进入终止过程,从而影响解质量。为了在尽可能大空间中取得质量较高优化解,必须采取变异操作。
人工智能-遗传算法
第16页
17
设自变量 x 介于0~31,求其二次函数最大值,即:
max f(x) = x2, x∈ [0, 31]
3、遗传算法示例-- f(x) = x2 极大值问题
500
1000
0
31
x
f (x)
当然,利用简单代数运算,很轻易求出该问题解。现在改用遗传算法求解,遗传算法通常包含下述内容:
人工智能-遗传算法
第17页
18
(1)编码
遗传算法首先要对实际问题进行编码,用字符串表示问题。这种字符串相当于遗传学中染色体。每一代所产生字符串个体总和称为群体。为了实现方便,通常字符串长度固定,字符选0或1。
本例中,利用5位二进制数表示x值,采取随机产生方法,假设得出拥有四个个体初始群体,即:01101,11000,01000,10011。x值对应为13,24,8,19。
个体编号
初始群体
xi
适应度f(xi)
f(xi)/∑f(xi)
f(xi)/f
Mp
1
2
3
4
01101
11000
01000
10011
13
24
8
19
169
576
64
361
1
2
0
1
总计∑f(xi)
平均值f
最大值
最小值
1170
293
576
64
4
1
2
0
人工智能-遗传算法
第18页
19
(2)计算适应度
衡量字符串(染色体)好坏指标是适应度,它也就是遗传算法目标函数。
本例中适应度比较简单,用x2计算。
表中还列出了当前适应度总和∑f(xi)及平均值f,即:
∑f(xi) = f(x1) + f(x2) + f(x3) + f(x4) = 1170
f = ∑f(xi) /4 = (293)
f(x1)/f=169/293=...
个体编号
初始群体
xi
适应度f(xi)
f(xi)/∑f(xi)
f(xi)/f
Mp
1
2
3
4
01101
11000
01000
10011
13
24
8
19
169
576
64
361
1
2
0
1
总计∑f(xi)
平均值f
最大值
最小值
1170
293
576
64
4
1
2
0
人工智能-遗传算法
第19页
20
(2)计算适应度
表中第6列 f(xi)/f 表示每个个体相对适应度,它反应了个体之间相对优劣性。如2号个体 f(xi)/f 值最高(),为优良个体,3号个体最低(),为不良个体。
个体编号
初始群体
xi
适应度f(xi)
f(xi)/∑f(xi)
f(xi)/f
Mp
1
2
3
4
5
6
7
1
2
3
4
01101
11000
01000
10011
13
24
8
19
169
576
64
361
1
2
0
1
总计∑f(xi)
平均值f
最大值
最小值
1170
293