遗传变异算子（精选六篇）
遗传变异算子 篇1
遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架,它不依赖于问题所属的具体领域,已广泛应用于函数优化[2]、自动控制[3]、机器人学[4]、图像处理[5]、遗传编码[6]、机器学习[7]等领域。
标准遗传算法存在的不足主要表现为:(1) 遗传算法的早熟现象(即很快收敛到局部最优解而不是全局最优解)是迄今为止最难处理的关键问题。(2)快要接近最优解时在最优解附近左右摆动,收敛较慢。
本文根据遗传算法的特点,改进遗传算法的变异算子,并结合局部搜索算法,给出一种融合遗传搜索和模式搜索的混合遗传算法,以提高算法的性能。实验仿真结果表明,改进后的算法在收敛速度、精度和稳定性方面均有明显的提高。
1 遗传算法原理
遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可以编成其他进制码)即基因,若干基因组成一个染色体(个体),许多染色体进行类似于自然选择、配对交叉和变异的运算,经过多次重复迭代直至得到最后的优化结果。标准遗传算法(也称为基本遗传算法或简单遗传算法,Simple Genetic Algorithm,简称SGA)只使用选择算子、交叉算子和变异算子,其遗传进化操作过程简单,是其它遗传算法的基本框架。
2 融合标准遗传搜索和模式搜索的混合遗传算法
2.1 算法的设计
本文提出的改进措施之一是:为防止早熟收敛,在进化过程中加速淘汰差的个体,增加解的多样性,将变异算子分为强制性变异算子和随机性变异算子,即当种群中的个体适应度低于某个值(强制性变异算子)时,强制该个体发生变异,若无满足条件的个体,则按随机性变异算子进行随机变异。
本文提出的另一个改进措施是:针对标准遗传算法全局搜索能力强而局部搜索能力弱的问题,把遗传算法和局部搜索算法有机地结合起来,是改进遗传算法性能的一个卓有成效的方法。这种混合型算法不仅模拟了生物种群的学习过程,而且事实上还模拟了种群的个体在其生命周期内具有学习行为这一生物现象。本文采用标准遗传搜索算法与模式搜索算法结合起来以优化搜索性能。模式搜索法[8]又称作“步长加速法”或“Hooke-Jeeves方法”,该算法主要由两种移动过程组成:探测移动和模式移动。探测移动时沿坐标轴方向的移动,模式移动则是沿相邻两个探测点连线方向上的移动。两种移动模式交替进行,目的是寻找函数值下降(上升)的最佳方向。在进化过程中,选取每代适应度最优的个体,以最优个体x为坐标原点交替进行模式移动和交叉移动,得到一个临时个体x’,如果x’的适应度优于x,则用x’取代x进入下一代种群。
融合标准遗传搜索和模式搜索的混合遗传算法。
①确定算法的初始参数(主要包括最大迭代次数、交叉算子、强制性变异算子、随机性变异算子)。
②确定编码方式。
③置k=0,随机产生初始种群undefined。
④计算每个个体适应度f(x1),…,f(xN),最优个体保留,其余N-1个由交叉产生。
⑤采用轮盘赌策略进行选择,令undefined,其中,PPi为累计概率,Pi为个体的选择概率,其计算公式为:undefined,其中,f(xi)为个体的适应度。共转轮N次(N为种群个体数),选取N个母体,每次转轮时,随机产生0到1之间的随机数r,当PPi-1≤r
⑥随机产生交叉点,单点交叉杂交得到N-1个中间个体。
⑦判断这N个中间个体中有无低于强制性变异算子约定的适应度的个体,有则转向⑧,无则转向⑨。
⑧将低于强制性变异算子约定适应度的个体进行变异。
⑨根据随机性变异算子约定概率对中间个体进行变异。
⑩从经变异后的N个中间个体中选取最优个体,以最优个体为坐标原点进行模式搜索,若能得到更优解,则以更优个体取代原个体进入下一代,反之则保留原个体。
(11)检验新的种群undefined是否满足停止准则,若满足则停止并输出结果,否则返回到④。
2.2 算法的收敛性分析
由本文给出的算法步骤可知,本算法是结合杰出者选择遗传算法和强制“劣汰”算法的混合遗传算法。
定理 “优胜劣汰”遗传算法是齐次马尔可夫链,且种群序列undefined;n≥0}以概率1收敛到满意种群集M*,即undefined
证明:对于任意undefined,当j≠i0时
undefined
而
undefined
于是undefined;n≥0}是齐次种群马尔可夫链。由
3 实验结果与分析
为对此改进算法性能进行测试,本文用几个经典寻优算法评价函数进行评测。测试平台:服务器DELL Power Edge 2650(双XEON CPU 2.4G,内存 1GB),操作系统Windows Server 2003,采用Matlab R2009b编程对表1中所列函数进行仿真测试。
设定种群规模为20,进化代数为100,对标准遗传算法SGA和本文给出的改进遗传算法MGA分别进行100次仿真实验测试,结果如表2所示。
以上六个函数为寻优算法的经典测试函数。Camel函数有6个极小点,其中有2个(-0.0898,0.7126)和(0.0898,-0.7126)为全局最小点。Griewank 函数和Rastrigin函数为高频多峰函数,搜索空间大,常规寻优方法很难奏效。 Schaffer函数最大值峰周围有一个圈脊,它们的取值均为0.990283,算法寻优很容易停滞在局部极大值。Schwefel's函数是一个典型的欺骗问题,有1个全局极小值点取值近似为-837.9658,在(420.9687,420.9687)处,距离另一个局部最优点很远,因此如果陷入局部最优就很难跳出。Rosenbrock函数特点是每个等高线是一个窄长弯曲的山谷,形状象香蕉,俗称香蕉函数,能有效的评价算法性能。从表2可以看出,改进后的遗传算法在收敛速度和稳定性方面比经典遗传算法都有了很大的提高。
4 结束语
最佳个体保留及强制性变异算子的引入模拟了自然界优胜劣汰的进化机制,加速了遗传算法的寻优过程,强制性变异机制也增加了染色体的多样性,防止早熟收敛。同时,标准遗传搜索法与模式搜索法均不需要计算导数,这两种寻优算法各有所长,将二者有机结合起来应用有效地提高了算法成功率。
参考文献
[1]陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[2]Bramlette M F.Initialization,Mutation and Selection Methods inGenetic Algorithms for Function Optimization[C].Proc ICGA 4,1991:100-107.
[3]Karr C L.Design of an Adaptive Fuzzy Logic Controller Using a Ge-netic Algorithm[C].Proc ICGA 4,1991:450-457.
[4]周明,孙树栋,彭炎午.基于遗传模拟退火算法的机器人路径规划[J].航空学报,1998,19(1):118-120.
[5]Talbi E,Bessière.P.A Parallel Genetic Algorithm for the GraphPartitioning Problem[C].Proceedings of ICS,1991:312-320.
[6]Michalewicz Z.Genetic Algorithms+Data Structures=EvolutionPrograms[C].Springer Verlag,1992.
[7]Goldberg D E.Genetic Algorithms in Search,Optimization and Ma-chine Learning[M].Addison Wesley Publishing Company,1989.
遗传变异探究与例解 篇2
基因突变包括DNA分子中碱基对的增添、缺失或改变，基因重因包括同源染体的非姐妹单体交叉互换、非同源染色体自由组合、DNA重组技术，染色体变异包括染色体结构和数目的变化。
基因突变的结果产生新的等位基因，基因重组的结果是形成新的基因型，染色体数目变异的结果往往是形成的物种。
例1 纯种甜玉米和纯种非甜玉米间行种植，收获时发现甜玉米果穗上有非甜玉米籽粒，而非甜玉米果穗上却无甜玉米籽粒。原因是（ ）
A. 甜是显性性状 B. 非甜是显性性状
C. 显性的相对性 D. 环境引起的变异
解析 纯种甜玉米和纯种非甜玉米间行种植就能进行相互传粉、授粉。非甜玉米上结的籽粒都是非甜的，非甜玉米胚珠的胚珠有两种受精的可能：一是自花传粉，得到的纯合非甜玉米籽粒；二是异花传粉，得到杂合的非甜籽粒。由此可确定非甜对甜是显性。甜玉米果穗上结的籽粉有甜的，也有非甜的。甜玉米植物上胚珠的受精也有两种可能：一种是自花授粉，得到的是纯合的甜玉米；另一种是异花传粉授粉，即非甜的花粉传给甜玉米，得到的是杂合的籽粒，表现型为非甜。由此也可以确定非甜对甜是显性。
答案 B
例2 下列现象属基因重组的是（ ）
A. 某自花传粉的植物一直开红花，偶尔一次开出一朵白花
B. 孟德尔用黄色圆粒豌豆自交子代出现绿色皱粒
C. 用二倍体西瓜育出四倍体西瓜和三倍体西瓜
D. 将抗虫基因插入到抗四环素基因中微生物表现出对四环素敏感的特性
解析 本题主要是考查三种变异的比较：A选项中纯合红花，突然出现白花是基因突变的结果；B选项中绿色皱粒的出现是因为黄色圆粒是杂合子，绿色皱粒的出现由于基因重组形成新的基因型的结果；C选项中染色体的数目发生了变化，属染色体变异；D选项对四环素敏感的特性的出现是产生了新的等位基因的结果，所以属基因突变。
答案 B
2. 可育与可遗传
可育是指生物体能正常进行有性生殖，可遗传是指生物的变异是由遗传物质的改变引起的。从染色体数目上看，可育必须是有成对的同源的染色体，并可平均分配给子代。只要是遗传物质发生了改变的均可遗传。发生可遗传变异的生物不一定可育。
例3 下列新类型的生物可育可遗传的是（ ）
A. 二倍体白菜和二倍体甘蓝杂交得异源二倍体白菜甘蓝
B. 用生长素处理得的无籽蕃茄
C. 用二倍体西瓜通过多倍体育种的方法得的三倍体无籽西瓜
D. 通过体细胞育种技术育出四倍体白菜甘蓝
解析 A选项二倍体白菜和二倍体甘蓝杂交得异源二倍体，细胞中无同源染色体，在减数分裂时联会紊乱，不可育；但由于遗传物质发生了改变故可传。B选项无籽性状不是蕃茄中的遗传物质变化引起的，故无籽性状不可遗传，但可育。C选项中三倍体无籽西瓜的遗传物质发生了改变故可遗传，但由于三倍体不能正常进行减数分裂，故不育。D选项中的四倍体白菜甘蓝属异源四倍，既能进行减数分裂，遗传物质又发生了改变，既可育又可遗传。
答案 D
3. 染色体组数的确定
不同情景下染色体组数判断的方法不同，根据不同的情景可确定如下的方法：
（1）依据减数第一次分裂过程中配对的染色体的数目判断；
（2）依据有丝分裂图象中同源染色体的数量判断；
（3）依据基因型来判断。开红花的某植物的基因型为RRRrrr可确定它的染色体的组数为6组。
例4 如图表示一些细胞中所含的染色体，据图回答（ ）
A B C D
写出ABCD图中染色体组的数目：
A： B： C： D：
解析 A图B图均为减数第一次分裂时期的图象，因而可依据同源染体体联会配对的数目来确定，故A中染色体的组数为2，B中染色组数为3。CD均为有丝分裂的图象，依据同源染色体的特征可知C中有三对同源染色体故染色体组数为2，同理D中染色体组数也为2。
4. 变异与育种
例5 在育种上既要得到更多的变异，又要使后代的变异性状较快地稳定。最好采用（ ）
A. 单倍体育种 B. 多倍体育种
C. 杂交育种 D. 诱变育种
解析 由题意很容易就可排除B、C两项。而单倍体育种只能缩短育种年限，迅速获得纯系植株，但不可能得到更多的变异。诱变育种是利用物理的（辐射诱变或激光诱变）或化学的（如亚硝酸）因素来处理植物，使它发生基因突变，创造变异类型，从中选择培育出优良品种，所以诱变育种可提高变异的频率，使后代的变异性状较快地稳定。
答案 D
1. 下列变异属可遗传的是（ ）
A. 水稻在水肥条件充足的条件下产量增大
B. 通过秋水仙素处理得的四倍体西瓜
C. 用生长素处理得到的无籽西瓜
D. 生长在向阳处的蒲公英的叶片呈全圆型
2. 下列关于人类遗传病的叙述，错误的是（ ）
A. 单基因突变可以导致遗传病
B. 染色体结构的改变可以导致遗传病
C. 近亲婚配可增加隐性遗传病的发病风险
D. 环境因素对多基因遗传病的发病无影响
3. 下列变异均是可遗传的变异，试述变异出现从来源上讲属哪一种变异：
A. 人类的红绿色盲
B. 黄圆豌豆田里结出绿色皱粒
C. 人工培育出的三倍体无籽西瓜
其中A属 变异，其中B属 变异，其中C属 变异。
4. 下图是表示以某种农作物①和②两个品种分别培育出④⑤⑥三个品种的过程。根据上述过程，回答下列问题：
[Ⅰ][Ⅱ][Ⅲ][Ⅳ][Ⅴ][①AABB][②aabb][⑥AAaaBBbb][⑤AAbb][④Ab][③AaBb]
（1）用①和②培育成⑤的过程所采用的方法I和Ⅱ分别称 ，其培育出⑤所依据的原理是 。
（2）由③培育出④的常用方法Ⅲ是 。由④育成⑤品种的方法V称 ，其优点是 。
（3）由③培育⑥的常用方法Ⅳ是 。其形成的⑥称 。
1. C 2. D
3. 基因突变、基因重组、染色体变异
4. （1）杂交自交基因重组
（2）花粉离体培养单倍体育种能缩短育种年限
遗传变异算子 篇3
遗传算法是通过模仿自然界中生物遗传和进化过程中的选择、交叉和变异机理,来寻找问题最优解的一种概率迭代搜索算法。选择算子,交叉算子和变异算子是遗传算法的三种基本遗传算子,这些参数的选择将直接影响算法的性能和搜索速度,所以选择合适的遗传算子是算法能高效地收敛到全局最优解的关键所在。全局最优解的收敛速度和群体多样性的维持之间的矛盾一直是遗传算法研究的热点。为加快算法收敛速度,就要使群体尽快向优良状态进化,而这又会缩小搜索空间,降低群体多样性,容易陷入局部极优。同时,为收敛到全局最优,就必须增加群体多样性,避免丢失有效基因。很多研究者提出一些方法来改善遗传算法的性能,但这些方法都没有很好地解决上述两者的矛盾。马均水[9]等使用一个大于通常变异概率的概率对个体执行变异操作,使群体脱离早熟,但没有考虑算法的收敛速度问题。孟佳娜[5]等提出的交叉算子加快了算法的收敛速度,但没有很好的解决群体多样性问题。本文使用自识别交叉算子加快算法收敛速度,使用自适应变异算子增加群体中个体的多样性 ,两种改进算子的结合很好地平衡了算法多样性和收敛速度的关系。
1 改进的遗传算法
1.1 自识别交叉算子
交叉算子的好坏直接影响遗传算法的收敛速度。在传统的遗传算法中,不管交叉的两个个体的相似性,采用固定的交叉率使两个个体进行交叉操作,结果父个体中的优良模式不能被遗传到下一代,导致了算法收敛速度的下降。
为保证父个体的良好模式保留到下一代,本文采用了自识别交叉算子 ,它根据个体间的相似度大小来决定是否进行交叉操作。假设有两个串A和B,对A和B的相似度定义如下:
undefined
其中l是A和B的最长公共子串的长度,n为染色体串长度。例如:串A=10110100 , 串B=01101110, 最长的公共子串是01101,长度为5,染色体长度n为8,所以A和B相似度为undefined。下面定义一阈值p:
undefined
其中G为总的进化代数,g为当前进化代数。只有当两个个体相似度s小于p时,两个个体才能进行交叉,交叉采用单点交叉。
本文用动态规划方法求两个串的最长公共子序列长度,具体代码如下:
1.2 基于海明距离的自适应变异算子
在遗传算法中,当群体进化到一定代数时,就可能丢失某些有效基因,而这些基因恰好是最优解包含的信息,这样交叉操作就不能搜索到最优解。为恢复群体中的有效基因,保持种群的多样性,在文献[5]的基础上,本文采用基于海明距离的自适应变异算子对个体进行变异,实验结果证明了它的有效性。海明距离定义如下:
Dij=undefined|bin-bjn| (3)
其中k为个体串的编码长度,bin为第i个个体的第n位基因的值。
当种群中各个体适应度趋于一致或局部最优时,就提高变异率;当群体适应度比较分散时,就降低变异率。同时,对于适应度高于群体平均适应度的个体,对应于较低的变异率,使该解得以保护进入下一代;而低于平均适应值的个体,相对应于较高的变异率,使该解被淘汰。在原有自适应变异率的基础上,依据海明距离对变异率pm重新定义如下:
undefined
其中,fmax为最大的个体适应度值;favg为每代群体的平均适应度值;f为要进行变异个体的适应度值;pm1为最大变异率;pm2为最小变异率;Hij为两个个体间的绝对海明距离;undefined为所有个体间的平均绝对海明距离;a和A为常数,本文取a=群体中最大可能绝对海明距离,A=2, pm1=0.2, pm2=0.001。
2 性能测试
2.1 测试函数
2.1.1 Camel函数
undefined
此函数有6个局部极小点,其中有两个(-0.0898,0.7126)和(0.0898,-0.7126)为全局最小点,最小值为-1.031628,自变量取值范围为-100
2.1.2 Shaffer’s函数
undefined
此函数有无限个局部极大点,其中只有一个(0,0)为全局最大,最大值为1。自变量取值范围为-100
2.2 测试结果与分析
本文分别采用传统遗传算法,文献[5]的算法以及改进算法对上述两个函数进行测试,并对结果作了详细分析。实验在vc++6.0环境下各自运行100次,群体规模为50,进化代数为100代。
从图(a)可以看到本文算法在15代就已经收敛,找到最优解,而其它两种算法收敛进程缓慢,很难达到最优解。从图(b)中可以看到,本文算法在55代达到收敛状态,而且之前收敛进程较其它两种算法迅速。由此得出本文算法与其它两种算法相比能以很快的速度跳离局部最优解,并以较高的概率收敛于全局最优解。
本文使用三种算法分别对测试函数运行100次后,就它们的平均适应度和最优适应度作了比较,结果如表1所示:
其中Aavg为群体的平均适应度,Abst为群体的最优适应度。
其中1、3、5、7、20、60、80、100为群体进化的代数。从表2中可以看到,随着进化代数的增加,本文算法的平均绝对海明距离明显大于文[5]算法的海明距离,并且本文算法在前几代中的海明距离变化幅度比较大,体现了本文变异算子维持群体多样性的优势。
3 结论与展望
标准遗传算法采用固定交叉率和变异率,收敛速度慢,容易陷入局部最优点。自识别交叉算子保留了父代的优良结构,加快了算法的收敛速度;自适应变异算子避免有效基因的丢失,增加了算法收敛于全局最优解的概率。实验证明改进算法稳定性好,运行效率高。今后研究和改进的方向是如何找到更好的交叉算子和变异算子使算法以更快的速度收敛于全局最优解。
摘要：为有效地解决遗传算法收敛速度和局部最优解的矛盾,本文提出了一种具有自识别交叉算子和基于海明距离的动态变异算子的遗传算法。自识别交叉算子保证父代的优良模式遗传到下一代,加快了算法的收敛速度;而动态变异算子扩大了搜索范围,增强了算法跳离局部最优解的能力。实验证明,两种改进算子的有效结合保证算法能以较快速度收敛于全局最优解。
关键词：遗传算法,自识别交叉算子,自适应变异算子,海明距离
参考文献
[1]HATTA K,WAKABAYASHI S,KOIDE T.Adaptation of ge-netic operators and parameters of a genetic algorithm based on the elite degree of an individual[J].Systems and Computers in Japan,2001;32(1):29-37.
[2]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安交通大学出版社,2002.
[3]段玉倩,贺家李.遗传算法及其改进[J].电力系统及其自动化学报,1998;10(1):39-52.
[4]J M Yang,C Y Kao.Integrating adaptive mutations and family competition into genetic algorithms as function optimizer[J].Soft Computing,2000.
[5]孟佳娜,王立宏.具有自识别能力的遗传算法求解旅行商问题[J].计算机工程与应用,2006;26(13):51-52.
[6]刘冀成,胡雅毅.带基因修复策略的自适应遗传算法[J].计算机应用,2006;26(6):1402-1405.
[7]KIVIJARYI J,FRANTI P,NEVALAINEN O.Self-adaptive genetic algorithm for clustering[J].Journal of Heuristics,2003,9(2):113-129.
[8]高玮.改进遗传算法之研究[P].计算机科学,2003;30(5):193-195.
[9]马均水等.改进遗传算法搜索性能的大变异操作[J].控制理论和应用,1998;15(3):404-407.
[10]彭丹平,林志毅,王江晴.求解TSP的一种改进遗传算法[J].计算机工程与应用,2006;26(13):91-93.
遗传变异算子 篇4
细菌觅食优化算法是由Passino于2002年提出来的一种仿生随机搜索算法，其生物学基础是人类肠道中的大肠杆菌在觅食过程中体现出来的智能行为[1]，是一种基于最值搜索的智能优化算法。细菌觅食优化算法具有仿生智能算法的局部搜索能力强、实现简单、能进行并行搜索等良好优点。目前，细菌觅食优化算法已经成为人工智能以及计算机科学的重要研究方向，并且已经在优化计算、图像处理、模式识别、系统仿真等领域得到了广泛应用。
细菌觅食优化算法在搜索过程中可能出现早熟收敛，而陷入局部最优的现象。为了改进细菌觅食优化算法的性能，避免算法早熟收敛，并加快收敛速度，可以将变异操作加入到细菌觅食优化算法中，得到基于变异算子的细菌觅食优化算法。本文将小波变异、高斯变异、混沌扰动、量子坍塌这四种变异算子引入到细菌觅食优化算法中，对其进行改进，提高算法的收敛速度和精度，也能很好地避免细菌觅食优化算法陷入局部最优。
1 细菌觅食优化算法的改进
1.1 细菌觅食优化算法
细菌觅食优化算法是基于Ecoli大肠杆菌在人体肠道内吞噬食物的行为，提出的一种新型仿生类算法，也是一种全局随机搜索算法[2]。细菌觅食优化算法包括趋化、复制、和迁徙三种操作。
1.1.1 趋化操作
大肠杆菌的运动是通过其表面的边毛来实现的。在细菌觅食优化算法中，鞭毛摆动对应着当前个体位置优劣的判断，并决定是否对其进行调整以及确定调整的依据、方式等问题。
设θi(j+1,k,l)表示个体i当前的位置，其中，j表示第j代趋化行为，k表示第k代复制行为，l表示第l代迁移行为。细菌觅食优化算法中的方向的调整按照公式(1)进行:
其中，φ(j)表示鞭毛摆动后确定的方向，C(i)表示前进步长。
1.1.2 复制操作
细菌的繁殖过程遵循自然界“优胜劣汰，适者生存”原则[3]。在细菌觅食优化算法中群体规模为S，在复制操作中，群体中需被淘汰的个数设为Sr=S/2。首先按细菌位置的优劣进行排序，然后将排在后面的Sr个个体删除，剩余的个体进行自身的复制，这样保证了细菌群体规模的稳定。
1.1.3 迁徙操作
细菌群体所依附的生存环境的变化将对其造成很大的影响，如温度的突然升高，水的冲刷作用或其他动物的影响等。在细菌觅食优化算法中，将预先给定变异的概率Ped，然后按照概率将细菌进行重新置位，对个体进行重新生成。
1.2 细菌觅食优化算法的改进
在以上介绍的基础细菌觅食优化算法上，为了改进细菌觅食优化算法的性能，避免算法早熟收敛，并加快收敛速度，本文将四种变异操作加入到细菌觅食优化算法中对细菌觅食优化算法进行了改进设计。
1.2.1 小波变异
引入小波变异对被选中的细菌xi进行变异[4]，使算法在增强种群多样性的同时，提高算法的搜索能力，变异公式如下:
式中，xmax,xmin分别为细菌的搜索空间的上限和下限;σ是小波函数值，xi+1为变异后细菌的状态。在本文中选择Morlet小波函数，其计算公式如下:
式中，Morrlet小波函数超过99%的能量包含在[-2.5,2.5]区间中[5]，所以-2.5≤θ≤2.5，而尺度参数a的计算公式如下:
式中，n是单调递增函数的形状参数，本文取5.0;g是a的上限值;edl是当前的迭代次数，Ned是最大的迭代次数。
1.2.2 高斯变异
高斯分布是概率论和数理统计中一个十分重要的分布，高斯变异就是在原有的个体上加上一个服从高斯分布的随机扰动项[6]。本文对被选中细菌进行高斯变异，充分利用被选中细菌的信息扰动，因此能使细菌跳出局部极值点的束缚并收敛于全局极值点，同时也提高了收敛速度。高斯变异算子定义如下:
其中，N(0,1)为服从均值为0、均方差为1的高斯分布。
1.2.3 混沌扰动
混沌是自然界广泛存在的一种非线性现象。它看似混沌，却有着精致的内在结构，具有随机性、遍历性及规律性等特点，对初始条件极度敏感，能在一定范围内按其自身规律不重复地遍历所有状态，利用混沌运动的这些性质可以进行优化搜索[7,8]。本文选取了一个典型的混沌系统Logistic映射[9]，迭代公式如下:
式中，当0<x0<1且不为0.25和0.75，μ=4时，Logistic完全处于混沌状态。混沌扰动就是将产生的混沌信号利用载波的形式引入到优化变量当中，使其呈现出混沌状态，与此同时把混沌的遍历范围扩大到优化变量的取值范围中。
1.2.4 量子坍塌
量子力学是20世纪最惊心动魄的发现之一，它为信息科学在下个世纪的发展提供了新的原理和方法[10]。此后，量子算法的研究成果，如Grover算法、量子智能算法等量子算法相继被提出。本文将细菌觅食优化算法和量子算法相结合，提出了一种基于量子坍塌的细菌觅食优化算法。此算法中首先将细菌位置进行优劣排序，然后选择保留位置较好的一半细菌，并将位置较差的一半细菌进行重新置位，对个体进行重新生成，公式如下:
式中，xSr+i,i=1,2,3，…为按细菌位置优劣进行排序后，排在后面的一半细菌，即位置较差的一半细菌。这样不仅可以有效地避免早熟收敛现象，而且有利于提高收敛的速度和稳定性。
2 数值仿真
2.1 测试函数
为了验证本文基于变异算子的细菌觅食优化算法的性能，通过数值仿真实验比较运用不同变异算子进行改进的细菌觅食优化算法的性能。本文采用2个单峰值基准测试函数和2个多峰值基准测试函数，对这4种算法进行性能测试。其中，函数1为Sphere单峰值函数;函数2为Rosenbrock单峰值函数;函数3为Rastrigrin多峰值函数;函数4为Ackly多峰值函数。
式(8)-式(11)中，p代表测试函数中的变量个数。
2.2 仿真结果及分析
本文算法参数的设置为:细菌位置位数为p=2(即测试函数中的变量个数)，细菌群规模为S=10(为便于以后的对半繁殖，一般取偶数)，趋化步数为Nc=100(用以衡量细菌寿命长度)，游动步数为Ns=4，繁殖次数为Nre=4，迁徙次数为Ned=4，迁徙概率为Ped=0.3，游动步长为runlengthunit=(xmax-xmin)×0.0001，其中xmax,xmin分别为细菌的搜索空间的上限和下限。
按上述参数进行实验，分别对每个测试函数进行仿真实验，实验结果如表1-4和图1-4所示，其中图1-4是对不同的测试函数进行各种变异操作后，最佳函数值进化的曲线。对于同一测试函数，可以直观地比较反映出基于各种变异算子的细菌觅食优化算法收敛速度的快慢以及最佳函数值的优劣。从以上表格数据以及仿真图像可以看出，对于单峰值的函数，对细菌觅食优化算法进行小波变异后，收敛速度明显加快，而且所取得的最佳函数值也较之基础算法和其他的算法有着明显的优势。对于多峰值的函数，无论从收敛速度，还是从最佳函数值来说，进行小波变异的细菌觅食优化算法仍然是最优的算法。对于像Ackly这样的多峰值函数，如果不进行变异操作，很有可能出现如图4所示的基础算法中收敛速度慢或者早熟收敛而陷入局部最优的现象。综合以上数值仿真结果可以看出，对细菌觅食优化算法进行小波变异或量子坍塌都可以不错地避免这种现象。
3 结束语
本文针对细菌觅食优化算法可能出现的早熟收敛而陷入局部最优及收敛速度慢的问题，对细菌觅食优化算法进行了改进，得到基于变异算子的细菌觅食优化算法，并对基于小波变异、高斯变异、混沌扰动、量子坍塌的细菌觅食优化算法进行数值仿真实验。从实验结果的对比可以看出，对于单峰值的函数，基于小波变异的细菌觅食优化算法能够有效地增强种群的多样性，避免陷入局部最优，提高算法的收敛速度及稳定性。对于多峰值的函数，对细菌觅食优化算法进行小波变异或量子坍塌都能够使算法有不错的收敛效果。
参考文献
[1]Passino K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control System Magazine,2002:52-67.
[2]尤梦丽,雷秀娟.改进的细菌觅食算法求解TSP问题[J].广西大学学报:自然科学版,2013,38(6):1437-1443.
[3]张璨,刘锋,李丽娟.改进的细菌觅食优化算法及其在框架结构设计中的应用[J].工程设计学报,2012,19(6):422-427.
[4]高东慧,董平平,田雨波,等.一种改进的小波变异粒子群优化算法[J].计算机工程,2012,38(21):145-147.
[5]程慕鑫,刘漫丹,夏伟.基于小波变异的改进粒子群算法[J].华东理工大学学报:自然科学版,2013,39(1):90-94.
[6]曲良东,何登旭.基于自适应高斯变异的人工鱼群算法[J].计算机工程,2009,35(15):182-184.
[7]黄岚,王康平,周春光,等.粒子群优化算法求解旅行商问题[J].吉林大学学报:理学版,2003,41(10):477-480.
[8]张国平,王正欧,袁国林.求解一类组合优化问题的混沌搜索法[J].系统工程理论与实践,2001,21(5):102-105.
[9]高尚,杨静宇.混沌粒子群优化算法研究[J].模式识别与人工智能,2006,19(2):266-270.
遗传变异算子 篇5
1.1初始化种群
在QDPSO中,直接采用量子位的概率幅作为粒子当前位置的编码,随机初始化量子粒子群中粒子的两个位置;产生初始种群为Pi:
设粒子当前搜索到的最优位置为Pil
整个种群目前搜索到的最优位置Pig为
如果量子粒子i的位置优于它对应的,则设置为当前位置为第i个粒子的新的两个位置并进行更新;粒子Pi上量子位幅角增量的更新位置算式为
粒子Pi上量子位概率幅增量的更新位置算式为
量子粒子更新后的两个新位置为
在QDPSO中,由于粒子的遍历空间每维均为[-1,1],将每个粒子占据的2个位置由单位空间I=[-1,1]n映射到优化问题的解空间。粒子上量子位的每个概率幅对应解空间的一个优化变量。记粒子Pj第i个量子位为,则相应的解空间变量为
1.2变异处理
为了增加种群多样性,首先给定变异概率Pm,对每个粒子赋值一个(0,1)之间随机数randi,若randi
2交叉变异因子机制的粒子群优化算法
基于交叉变异因子机制的粒子群优化算法的基本思想包括4部分:早熟判断机制的方法、Pareto最优解更新策略、基于交叉杂交算子和变异算子的改进机制。早熟判断方法是为早熟收敛而进行的判断;Pareto最优解更新策略是得到不断更新的最优解在临时储备器中的集合,为以后的交叉和变异个体选取做准备。交叉杂交是为了配对个体中随机选择杂交位置并进行杂交,杂交的目的是为了产生适应值更高的个体,从而使各代个体都向前进化;变异目的是改进算法的局部搜索能力并维持群体的多样性。
2.1 PSO的早熟现象及早熟判断机制
粒子群优化算法在搜索过程中,如果某粒子发现一个当前最优位置,其他粒子将迅速向其靠拢。如果该最优位置为一局部最优点,粒子群就无法在解空间内重新搜索,这就是所谓的“早熟收敛”现象。为解决这个问题,而引入早熟收敛判断机制。早熟收敛预防与处理的统一框架。
早熟收敛判断是早熟处理的基础。设粒子群的粒子数目为m,fi为第i个粒子的位置,favg为粒子群目前的平均位置,为粒子群的群体位置方差[2],定义为
其中是归一化定标因子,其作用是限制的大小。的取值采用如下算式
算式(13)表明,群体位置方差反映的是粒子群中所有粒子的“聚集”程度。越小,则粒子群的“聚集”程度就越大,若算法不满足结束条件,“聚集”将使群体失去多样性而陷入早熟状态,故当
2.2 Pareto最优解更新策略
Pareto最优解更新策略是在求解优化问题时设置了2个存储解的集合即最优解临时储备器Q1和Q2,并设定存储最优解的个数。经过迭代操作后,则将所得最优新解加入到最优解临时储备器中,然后比较新加入的解和存储器中的其他解,将次于新解的解从最优解临时储备器中删除,这种更新反复进行,得到更新的最优解的集合,为以后的交叉和变异做准备。
2.3交叉算子改进策略
交叉是随机抽取临时储备器Q1和Q2中的一个体进行配对,然后在配对个体中随机选择杂交位置进行杂交,交叉算子在算法中起着关键作用,它是产生新个体的主要方法。杂交的目的是为了产生适应值更高的个体,从而使各代个体都向前进化。交叉算子的设计和实现与所研究问题密切相关。
引理1:基于黄金分割(0.618法)交叉算子:黄金分割法是一种一维极小化问题的近似最优策略的搜索方法,即沿某一已知方向求目标函数的极小点法。它具有较强的局部搜索能力,利用近似最优策略构造交叉算子,可以很快跳出局部最优,交叉后的两个新体为
引理2:基于Fibonacci法的交叉算子:Fibonacci法是一种一维极小化问题的最优策略搜索算法,即沿某一已知方向求目标函数的极小点法。它同样也具有较强的局部搜索能力,利用最优策略构造交叉算子,可以很快跳出局部最优,交叉后的两个新体为
多点交叉算子在母体的基因串中随机设置多个交叉点,然后以一定概率在交叉点所分隔的基因段中进行段交换[3]。
引理3:基于数值计算方法的“取大”、“取小”交叉算子:这种交叉方法跟常规“一点”实数型交叉方法相比,在数值计算上显示了优越性。具体实施方法如下:
(1)按轮盘选择规则从临时存储器Q1、Q2中分别选出一条染色体Xi和Xj;
(2)由Xi和Xj按位“取大”运算产生一个字串C1;
(3)由Xi和Xj按位“取小”运算产生一个字串C2。
例如:选择的两条染色体为Xi:85078652,Xj:65140698
则由“取大”、“取小”运算产生的两个子串分别为
C1:85178698,C2:65040652
易知这种交叉方法使子代继承了双亲的同型基因。
2.4变异算子的改进策略
变异算子是改进算法的局部搜索能力,并维持群体的多样性,防止出现早熟现象。
引理4:基于最速下降法的变异算子:最速下降法具有计算速度快、方向性和局部搜索能力较强的优点,利用它的这一优点构造均匀变异算子[4],可以很快跳出局部最优。方法如下:记第i代P(i)的第j个染色体的第k个分量为Xijk,对其进行变异操作时,不再是二进制字符“1”、“0”之间的跳变,也不是[Sk,tk]内取随机数,其修正值为
改进的变异算子能够不断开拓问题解的新空间,增强算法的全局搜索能力。
2.5混合粒子群算法的实现
根据粒子群优化算法结构的开放性,把交叉算子、变异算子和粒子群算法结合起来,用交叉和变异来处理粒子群的早熟收敛问题。首先运行两个粒子群算法操作,只要有一个粒子群算法处于早熟收敛状态,就从各自的临时储存器中随机抽取一个个体进行交叉和变异处理,迭代N次后,把搜索到的最优解向量作为粒子群算法的全局最优解向量,从而引导粒子快速跳出局部最优,加快收敛速度,提高了算法的精度。
算法流程如下:
(1)对2个粒子群同时进行初始化:设定有关参数,初始化粒子群中粒子的位置。
(2)首先令每个粒子的最优位置pi为当前粒子所在的位置,并计算其对应的适应度;令全局最优位置pg为当前群体中具有最优适应度的粒子的位置。
(3)对于粒子群中的所有粒子执行如下操作:1)根据算式(1)和算式(2)更新粒子的位置;2)如果粒子i的位置优于它对应的当前位置,则pi设置为第i个粒子的新位置;把其中一个粒子群优化算法通过算式(1)、算式(2),得到全局最优解储存到临时储存器Q1,迭代N次,另一个粒子群通过算式(1)、算式(2)得到全局最优解储存到临时储存器Q2,迭代N次(Q最优解的个数远小于N)。
(4)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则执行步骤(5)。
(5)用Q1,Q2中的最优解来根据算式(3)计算群体适应度方差,并判断
(6)随机取出Q1,Q2中的个体,根据改进的交叉算子算式(4)进行个体交叉,把交叉得到的2个个体根据算式(1)和算式(2)更新粒子的位置;把迭代N次得到的结果放到各自的Q中,然后在各自的Q中选取一个个体根据变异算子算式(6)分别进行变异操作,迭代N次;把最后得到的最优解还存储在各自的储存器中并替换最差的最优解。
(7)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则执行步骤(8)。
(8)随机取出Q1,Q2中的个体,根据改进的交叉算子算式(5)进行个体交叉,把交叉得到的2个个体根据算式(1)和算式(2)更新粒子的位置;把迭代N次得到的结果放到各自的Q中,然后在各自的Q中选取一个个体根据变异算子算式(6)分别进行变异操作,迭代N次;把最后得到的最优解还存储在各自的储存器中并替换最差的最优解。
(9)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则执行步骤(10)。
(10)随机取出Q1,Q2中的个体,根据引理3的交叉算子进行个体交叉,把交叉得到的2个个体根据算式(1)和算式(2)更新粒子的位置;把迭代N次得到的结果放到各自的Q中,然后在各自的Q中选取一个个体根据变异算子算式(6)分别进行变异操作,迭代N次;把最后得到的最优解存储在各自的储存器中并替换最差的最优解。
(11)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则判断设定算法迭代次数是否小于设定的次数,如果是则执行步骤(3),否则执行步骤(12)。
(12)当满足条件后,取出Q1和Q2中的最优解进行对比,最后输出最优解。
3改进后混合算法的验证
利用这个改进混合粒子群算法用六峰值驼背函数[4]来验证。
六峰值驼背函数
该函数共有6个局部极小点,其中(-0.898,0.7126)和(0.898,-0.7126)为全局最小点,最小值为f(-0.898,0.7126)=f(0.898,-0.7126)=-1.031628。
对此函数利用数学分析中的单纯形搜索方法,随机产生初始点,计算极值结果如表1所示[5]。
这些点中最好的是-1.031621,最差的是-0.798968,均值是-0.9564460。
对改进的混合算法设计参数如下:混合粒子群算法和遗传算法各优化50次。两种算法种群都取20,限定代数500。混和粒子群参数:变异概率Pm=0.05。GA参数:变异概率Pm=0.05,交叉概率Pc=0.7,用改进后的混合粒子群算法,遗传算法[6]对六峰值驼背函数进行再次计算结果分别如表3和表2所示(在“最大”、“最小”法交叉时,都随机选取3位来操作)。
这些点中最好的是-1.0316,最差的是-1.0297,均值是-1.0352。
这些点中最好的是-1.03160,最差的是-1.01013,均值是-1.02723。与传统的单纯形搜索方法及遗传算法搜索结果相比,混合粒子群算法优势是明显的。其得到最优值更接近理论上的最优值。
摘要：针对量子粒子群优化算法在处理高维复杂函数时存在收敛速度慢、易陷入局部最优等缺点,提出了基于黄金分割法、最速下降法、Fibonacci法、“取大”、“取小”法的新算法,同时把遗传算法中交叉、变异算子引入量子粒子群算法中。
关键词：数值计算方法,量子粒子群算法,算子,黄金分割法,最速下降法
参考文献
[1]李士勇.求解连续空间优化问题的粒子群算法[J].电子学报,2007,40(35):50-52.
[2]Eberhart R C.Hu X.Human tremor analyis using particle swarmoptimization[C].In the Proceeding of the IEEE Congress onevolutionarycomputation(CEC 1999),Washinggon D C:IEEE Press,1999:1927-1930.
[3]金聪.启发式遗传算法及其应用[J].数值计算与计算机应用,2003,(1):30-35.
[4]吴仕勇.基于数值计算方法的遗传算法的优化研究[J].计算机工程与设计,2009,30(12):2966-3025.
[5]褚蕾蕾.计算智能的数学基础[M].北京:科学出版社,2002:14-32.
遗传变异算子 篇6
关键词：遗传算法,变异,收敛速度,种群数
0 引 言
遗传算法(Genetic Algorithm,GA)是一种宏观意义下的仿生算法,它模仿的机制是一切生命与智能的产生与进化过程,从一个初始种群出发,不断重复执行选择,杂交和变异的过程,使种群进化越来越接近某一目标。它通过模拟达尔文“优胜劣汰,适者生存”的原理激励好的结构;通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构,同时寻找更好的结构。经典遗传算法的求解步骤为:初始化种群;选择;交叉;变异;判断终止条件。由于它简单有效,具有很强的鲁棒性和通用性,所以被广泛应用于模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等多种领域[1]。
早熟和收敛时间过长是影响遗传算法效率的两个主要因素,而选择压力过大是导致早熟收敛的一个重要原因[2],为此不少学者对遗传算法做了改进[3,4,5],但仍存在一定局限性。在此对遗传算法个操作算子加以改进,通过对经典多极值测试函数的仿真研究表明,改进后的算法能够有效避免早熟且在种群规模较小的情况下具有较快的收敛速度。
1 改进操作算子的遗传算法
经典遗传算法的把变异作为一种辅助手段,认为变异只是一个背景机制,这一观点与生物学中的实际观察是相符的,但作为设计人工求解问题方法的思想,他正受到理论与实践两方面的挑战[6]。另外,从微观角度来讲,变异随时都有可能发生,如果突变向不好的方向进行,其“修复系统”立刻就能对其进行修复。基于以上两点,这里在选择与交叉算子中渗入不同的变异行为,且动态改进变异算子,使算法能快速达到全局最优。
1.1 初始化
为了改善初始群体的效能,提高模式的优良度,采取如下方法:先随机产生一个父染色体,对其进行一定次数(20次左右)的逐位精英选择高频变异,方法如下:例如染色体为01001,先把第一位变异为1,成为11001,若适应度提高,则此位以很大的概率p(如0.98)转换为1,否则以很小的概率(如0.01)转换为1,以此类推。接着产生具有一定规模的染色体种群,随机使其中每个染色体的某段基因与之前父染色体相应基因段保持一致。如:假设父染色体为00110,随机产生个体10101,若以第一和第二位基因与父染色体一致,则该个体变为:00101。该方法把较优秀的模式分散到各个染色体中,使它一开始就具有一定概率的优秀短模式,从而有效提高算法的寻优效率。
1.2 选择操作
经典遗传算法根据适者生存原则选择下一代个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。
然而基于适应度的概率选择机制如轮盘赌选择法在种群中出现个别或极少数适应度相当高的个体时,就可能导致这些个体在群体中迅速繁殖,经过少数迭代后占满了种群的位置。这样,遗传算法的求解过程就结束了,也即收敛了。但这样很有可能使收敛到局部最优解,即出现早熟现象[1]。为了从根本上避免早熟现象且加快收敛速度,采用基于高频精英变异的锦标赛选择法。其操作如下:假设竞赛规模为2,首先选取种群中第1和第2个个体X和Y
如:X=100101,Y=011110
从第1位开始比较适应值的大小,即当个体X与Y的第1位分别是1和0时,假设fitness(X)> fitness(Y),于是把Y的第1位由0高频变异为1,此时:
X=110101,Y=101110
此时,若fitness(X)< fitness(Y),则把Y的第1位由1高频变异为0。如此下去,最终得到的为选择出的个体,其中较高位(如第1至L/3位,其中L为染色体长度)变异率为0.8,其他位变异率为0.95,理由是较高位的个体即使适应度低也有可能在附近变异成适应度更高的个体。
然后选取种群中第2和第3个个体应用上法选择出第2个个体,这个过程重复进行,完成剩余个体的选择。这种算子在选择个体上就可以有方向性且极大地加快算法的收敛速度。
1.3 交叉操作
交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作,从而在下一代产生新的个体。它的目的是开发问题解空间中新的区域,寻找父个体已有的但未能合理组合的基因,尽量保证具有优良模式的个体不被交叉操作所完全破坏,同时增大种群的离散程度,产生新的搜索空间。所有交叉操作的一个共同特征是,不破坏两个父个体之间的公共串模式,允许继续搜索空间时保留好的模式[2]。
对于选中用于繁殖下一代的个体,随机地选择2个个体的相同位置,按交叉概率P在选中的位置实行交换。在选中的位置实行交换[1]。这个过程反映了随机信息交换,目的在于产生新的基因组合,也即产生新的个体。在交叉时,可实行单点交叉或多点交叉。
一点交叉是经典的交叉方法,它是对于给定的两个父个体,随机地选取1个交叉位置,然后相互交换两个个体交叉位置右边部分基因,形成2个子代,一点交叉能够搜索到的空间十分有限。多点交叉的破坏性可以促进解空间的搜索,而不是促进过早地收敛,因此搜索更加健壮[1]。这里在采取多点交叉的同时考虑父个体间的多样度。
当两个父个体的汉明距离较低,可能导致交叉操作无效。另外,由于交叉点随机产生,可能会导致交叉后新个体无变化,例如,两父个体分别为01100101和01011010,如果交叉点取值为第2位,则交叉后的两个新个体与父个体相同,交叉操作无效。在此采取交叉概率与汉明距离成正比的策略:两父体相似度高时交叉概率减小以避免无效操作,一旦在这种情况下进行交叉,首先保持具有高适应度的父个体不变,然后对低适应度个体或者交叉点左右具有相同子串的个体采取变异操作以增大它们之间的汉明距离,从而提高交叉操作的有效性。
1.4 变异操作
根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。
单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。
这里提出一种自适应快速收敛变异法:对每一个体采取从高位到低位逐位变异的策略。在寻优的早期主要是全局搜索,此时各变量二进制的高位应采用高变异率,低位采用低变异率。在寻优过程中不断调整各位的变异率,即高位变异率逐渐降低,低位变异率逐渐增加。到寻优后期,主要是局部优化,全局优化次之,此时各位变异率与早期相反,即低位变异率要比高位变异率大。在变异过程中采用概率精英保留策略,也就是每位变异后若适应值增加,则以高概率保留,否则放弃此位变异。实验证明,这种变异策略在种群规模较小的情况下能获得较满意的进化能力。
2 算法描述
算法描述为:
(1) 采用二进制编码,随机产生一个体,通过逐位高频精英变异,提高其适应度;
(2) 利用上述较优父染色体产生产生种群;
(3) 进行基于高频精英变异的锦标赛选择;
(4) 进行改进的交叉运算;
(5) 进行自适应变异运算;
(6) 是否到最大的遗传代数,如果达到,结束;否则转到步骤(3)。
3 仿真试验及结果分析
3.1 试验
为验证改进算法的效率,用经典遗传算法SGA和文中的加速收敛改进遗传算法相比较,其中SGA采用的遗传操作及相应参数为比例选择、单点交叉(交叉概率0.85)及基本位变异(变异概率0.05),种群规模为100,进化代数为100。两者都采用保留个体精英的方法。选择如下3个算例进行仿真计算。
(1) Camel函数
此函数有6个极小点,其中有2个(-0.089 8,0.712 6)和(0.089 8,-0.712 6)为全局最小点,最小值为-1.031 628,自变量的取值范围为 -100<x,y<100。
(2) Shubert函数
该函数有760个局部极小点,其中只有1个(-1.425 13,-0.800 32)为全局最小,最小值为186.730 9。自变量取值范围 -10<x,y<10。此函数极易陷入局部极小值186.34。
(3) Schaffer函数
该函数有无限个局部极大点,其中只有一个(0,0)为全局最大,最大值为1。自变量的取值范围为-100<x,y<100。该函数最大值峰周围有一个圈脊,它们的取值均为0.990 283,因此很容易停滞在局部极大值。
改进后算法的种群规模为20,进化代数为60。对两种算法进行100次随机仿真,试验结果如表1所示。
3.2 结果分析
从以上结果可以看出,SGA容易早熟收敛,而改进后的算法能很好地摆脱早熟,并能以很高的成功概率快速搜索到最优值。从各参数也可以看出,改进后的遗传算法在种群规模很小的情况下也具有很高的寻优效率。因此,这里提出的改进算子GA从全局收敛概率和平均进化代数来看,是成功的,它具有高效的全局以及局部搜索能力。
4 结 语
通过对算法各算子的改进,较好地解决了一般遗传算法收敛速度慢和全局寻优能力弱的缺点。实践表明,改进GA和标准GA相比,在花费更少的情况下具有更快的收敛速度和精度。
参考文献
[1]王小平,曹立明.遗传算法——理论,应用与软件实现[M].西安:西安交通大学出版社,2002.
[2]王忠,柴贺军,刘浩吾.关于遗传算法的几点改进[J].电子科技大学学报,2002,31(1):76-80.
[3]熊范伦,邓超.退火遗传算法及其应用[J].生物数学学报,2000,15(2):150-154.
[4]张毅,杨秀霞.一种基于能量熵的快速遗传算法研究[J].系统工程理论与实践,2005(2):123-128.
[5]金朝红.一种基于自适应遗传算法的神经网络学习算法[J].微计算机信息,2005,10(1):49-51.
[6]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2003.
[7]Qi Xiaofeng.Theoretical Analysis of Evolutionary Algo-rithms With an Infinite Population Size in Continuous SpacePart II:Analysis of the Diversification Role of Crossover[J].IEEE Transactions on Neural Networks,1994,5(1):120-129.
[8]陶林波.一种解决早熟收敛的自适应遗传算法设计[J].微计算机信息,2006,12(1):268-270.
[9]Introduction to Genetic Algorithms[EB/OL].http://www.rennard.org/alife/english/gavintrgb.html.
[10]Genetic Algorithm-Traveller in Space[EB/OL].http://arc.net.cn/wiki/pmwiki.php/R/GeneticAlgorithm.
相关文章：
空间变异01-17
生物变异01-17
变异算法01-17
语用变异01-17
2025年计算机网络实习报告 计算机网络专业实训模板(9篇)01-17
信息变异01-17
书籍变异设计01-17
加强大学生思想政治教育的途径研究01-17
掌握学生思想动态,开创思想政治教育新局面01-17
语言变异理论01-17
