通信论坛
64
Computer&Network
计算机与网络创新生活
整个种群进行定义;另一种思路是针对个体进行定义。
4收敛性分析
为了用泛函分析中的Banach不动点原理来证明改进的自适应遗传算法的收敛性。下面,首先介绍一下泛函分析中的一个重要定理-压缩映射原理。
2.1渐近收敛
Michalewicz给出了针对整个种群的一种渐近收敛的定
义。将所有可能的种群所组成的集合视为一个状态空间X,算

法在时刻的种群为
,那么,算法收敛性可以定义如下:


































满足:


定义

1

若算法在时刻的种群

4.1压缩映射原理[1]
定义3设X是一个非空集合,若d是一个映射,并且对于
,,并且
;
。满足:
当且仅当
;
到R的
则称算法收敛到。
经典的GA算法由于存在随机性,而不具有渐近收敛的性质。
①②③
2.2概率收敛
前面已经指出了遗传算法具有随机性,而且,由于在利用遗传算法求解问题时,往往并不知道适应度函数的最大值究竟是多少,因此当最优个体出现时,算法仍有可能会继续进行。而在实际应用中,人们总是希望算法收敛时能够得到最优解,所以,在定义其收敛性时应当考察在随机因素作用下算法收敛到最优解的能力。Rudolph给出了一种针对个体的收敛性定义:
定义2:设的最大值,
为第t代种群中所包含的个体的适应度值
在所有可能的个体所组成满足:
则称d为X上的度量,称(X,d)为度量空间。定理1在度量空间(X,d)中,对对
,有,有
是(X,d)中的序列,若存在
,则称序列
。
在(X,
;
定义4设(X,d)为度量空间,正整数N,使得
,有
为适应度函数
d)中收敛于x,x称为序列的极限,记为
定义5设(X,d)为度量空间,
的集合X中所取的最大值,若
是(X,d)中的序列,若对于
,有
,存在正整数N,使得对一切
则称算法收敛到最优解。
,则称序列
是(X,d)中的Cauchy序列;若其中
的每一个Cauchy序列都收敛,则称(X,d)为完备度量空间。
3一种改进的自适应遗传算法[2]
为了用于模型辨识,文献[2]提出了一种基于精英保留策略的自适应遗传算法。该算法采用了浮点数编码方法;选择算子采用非线性排序选择,采用非线性函数将队列序号映射为期望的选择概率;交叉算子则采用了两点交叉算子;为使算法快速收敛和抑制种群的早熟现象采用了改进的变异算子;改进的算法使群体中最大适应度的个体交叉率和变异率不为零,分别提高到0.6和0.01,使优良个体不处于一种停滞状态,从而使算法跳出局部最优解。
为保证每一代优良个体不被破坏采用了精英保留策略。如果下一代群体的最佳个体适应值小于当前群体最佳个体适应值,则将当前群体最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代,随机替代或替代最差的下一代群体中的相应数量个体。精英保留策略保证了当前的最优个体不会被交叉、变异等遗传运算破坏,它是群体收敛到优化问题最优解的一种基本保障。
定义6设(X,d)为度量空间,对于映射
,使得对
,满足:
,
则称f为压缩映射。
定理2(Banach压缩映射原理)设(X,d)为完备度量空间,
为一压缩映射,则f有且仅有一个不动点
并且对于
满足:
,
其中,。
4.2改进的自适应遗传算法收敛性分析
根据Banach压缩映射原理,如果能够找到一个合适的度量空间,使得自适应遗传算法遗传算子成为一个压缩映射,那么,就可以证明:任意选取初始群体于某个唯一的不动点法。
设P为自适应遗传算法的一个种群,其规模为n,即
,自适应遗传算法收敛
。下面具体分析改进的自适应遗传算
《计算机与网络》2012年第09期
及收敛速度慢的不足, 提出了一种改进的自适应遗传...直接影响算法 的收敛性, 交叉率 Pc 的大小决定新...一种改进的自适应遗传算法 3.2 实验结果分析 61 ...
一种改进的自适应遗传算法_专业资料。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法.针对传统遗传算法和自适应遗传算法存在“早熟”现象及收敛速度慢...
在对自适应遗传算法中选择、交叉、变异算子作用分析的基础上,提出一种新的自...仿真实验表明,新算法有效防止早熟,收敛速度更快,鲁棒性更好且拥有较强的寻优...
, : 摘要为克服标 准遗 传算法的未成熟收敛现象提高全局收敛性和收敛速度提出了 , , 一种改进的 自适 应遗传算法该算法分别根据配对个体的相似程度和种群 . ...
!! ! 一种改进的自适应遗传算法王摘 蕾,沈庭芝,...这是本文改进的自适应遗传算法收敛性的一个重 要保证...’+ % $& ’$ ’ )*+ 试验结果分析 对于图像...
一种改进的自适应遗传算法... 3页 5财富值 单亲遗传算法及其全局收敛... 5...2001 十进制遗传算法的收敛性分析黄友锐 ( 淮南工业学院电气工程系, 安徽 淮南 ...
一种改进的自适应遗传算法... 3页 5财富值 遗传算法的收敛性分析 4页 1财富...尤其 是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的...
基于自适应遗传算法的过... 5页 免费 一种改进的自适应遗传算... 3页 2下载...基于下鞅的性质和收敛定理分析算法的 收敛性,获得了收敛速度与遗传算法操作参数...
热门文档