文档介绍：第5章计算智能(2) Computational Intelligence
进化计算
人工生命
2
进化计算包括:
遗传算法(ic algorithms,GA)
进化策略(evolutionary strategies)
进化编程(evolutionary programming)
遗传编程(ic programming)
人类不满足于模仿生物进化行为,希望能够建立具有自然生命特征的人造生命和人造生命系统。
人工生命是人工智能和计算智能的一个新的研究热点。
3
遗传算法
遗传算法是模仿生物遗传学和自然选择机理,通过人工方式所构造的一类优化搜索算法,是对生物进化过程进行的一种数学仿真,是进化计算的最重要的形式。
遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。
进化计算和遗传算法借鉴了生物科学中的某些知识,这也体现了人工智能这一交叉学科的特点。
4
遗传算法的基本机理
霍兰德的遗传算法通常称为简单遗传算法(SGA)。现以此作为讨论主要对象,加上适应的改进,来分析遗传算法的结构和机理。
编码与解码
适应度函数
遗传操作
遗传算法
5
将问题结构变换为位串形式编码表示的过程叫编码;而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体,有时也叫个体。
遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。
7
二进制编码的最大缺点之一是长度较大,对很多问题用其他主编码方法可能更有利
符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。
例如,对于TSP问题,采用符号编码方法,按一条回路中城市的次序进行编码,一般情况是从城市w1开始,依次经过城市w2 ,……, wn,最后回到城市w1,我们就有如下编码表示:
由于是回路,记wn+1= w1。它其实是1,……,n的一个循环排列。要注意w1, w2,……, wn是互不相同的。
8
体现染色体的适应能力,对问题中的每一个染色体都能进行度量的函数,叫适应度函数(fitness function)
对优化问题,适应度函数就是目标函数。TSP的目标是路径总长度为最短,路径总长度可作为TSP问题的适应度函数:
9
简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作,以达到更高的效率。
选择操作也叫复制(reproduction)操作,根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。
一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小。
10
交叉操作
交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体,将两者的部分码值进行交换
假设有八位长的二个体,产生一个在1到8之间的随机数c,假如现在产生的是3,将P1和P2的低三位交换
1
0
0
0
1
1
1
0
1
1
0
1
1
0
0
1
P1
P2
1
1
0
0
0
1