文档介绍：遗传算法
1
一、遗传算法概述(1)
遗传算法(ic Algorithm,GA)是一类建立在自然选择和群体遗传学机理基础上的通用问题求解算法,具有广泛的适应性。
遗传算法是Holland在20世纪60年代末提出的,当时并未受到重视。
2
基本思想
使用模拟生物和人类进化的方法求解复杂的优化问题,因而也称为模拟进化优化算法。将择优与随机信息交换结合在一起。在每一代中,使用上一代中最好的,即最适应环境的位或片段,形成新的人工生物集。
一、遗传算法概述(2)
3
应用领域
早期应用研究主要围绕组合优化问题以及复杂的函数优化问题求解,以后它的研究应用迅速扩大,遍及科学、工程、商业等领域:
NP完全问题神经网络权值
机器学习并行处理知识发现
一、遗传算法概述(3)
4
二、遗传算法中的基本概念(1)
形式化描述
GA=(P(0), N, l, s, g, p, f, t)
其中:P(0)=(P1(0),P2(0),…,Pn(0)),表示初始种群;
N表示种群中含有个体的个数;
l表示二进制串的长度;
s表示选择策略;
g表示遗传算子(选择算子Qr、杂交算子Qc和变异算子Qm);
p表示遗传算子的操作概率(选择概率pr、杂交概率Pc和变异概率Pm);
f是适应度函数;
t是终止准则。
5
用遗传算法求解问题时,必须在目标问题实际表示与遗传算法染色体结构之间建立联系,即确定编码和解码运算。
霍兰德提出的遗传算法采用二进制编码来表现个体的遗传基因型,它使用的编码符号0和1组成,因此实际的遗传基因型是一个二进制符号串。
四、遗传编码(1)
优点: 在于编码、解码操作简单,交叉、变异等遗传操作便于实现,而且便于用模式定理进行理论分析等。
缺点: 不便于反映所求问题的特定知识,对于一些连续函数的优化问题等,由于遗传算法的随机特征而使得其局部搜索能力较差;
对于一些多维、高精度要求的连续函数的优化,二进制编码存在着连续函数离散化时的映射误差;
个体编码串较短时,可能达不到精度要求;
个体编码串的长度较长时,虽然能提供精度,会使算法的搜索空间急剧扩大。
8
1、二进制编码
在二进制编码中,首先要确定二进制字符串的长度l ,串长l取决于变量的定义域及计算所需的精度。
例:变量x的定义域[-2,5],要求其精度为10-6,则需要将[-2,5]分成至少7000000个等长小区域,而每个小区域用一个二进制表示。于是串长至少等于23。
4194304=222<7000000<223=8388608
这样,计算中的任何一个二进制串(b22b21…b0)都对应[-2,5]中的一个点。
四、遗传编码(2)
解码过程:
将二进制串(b22b21…b0)按下式转换成为1个十进制整数:
xl=∑bi*2i
按下列计算对应变量x的值:
x=-+xi*7/(223-1)
i=0
22
9
遗传算法将问题空间表示为染色体位串空间,为了执行适者生存的原则,必须对个体位串的适应性进行评价。
适应值函数构成了个体的生存环境。
根据个体适应值可以决定它在此环境下的生存能力。
一般来说,好的染色体位串结构具有比较高的适应值,即可以取得较高的评价,具有较强的生存能力。
五、适应值函数(1)
10