自适应遗传算法的改进与应用_张国强
总第187期2010年第1期
舰船电子工程
Ship Elec tronic Engineering
V o l.30No.1
83
自适应遗传算法的改进与应用＊
张国强1) 彭晓明2)
(空军雷达学院研究生管理大队1) 武汉 430019)(空军雷达学院预警监视情报系2) 武汉 430019)
摘 要 为提高遗传算法的全局最优和快速收敛,在现有的一些自适应遗传算法的基础上,针对交叉概率和变异概率进行改进,提出了一种根据适应度值自动调整交叉概率和变异概率的新的自适应遗传算法。实验结果表明,该算法在收敛快速性和稳定性等方面都有了明显的改善,达到了预期效果。
关键词 遗传算法;自适应;自适应遗传算法
中图分类号 T P301.6
Im p rove me nt and A p plicatio n of an I m prove d A daptive Ge netic A lgo rithm
Zhang Guoqiang1) Peng Xiaoming2)
(Depa rtment of G raduate M anagement,A F RA1),W uhan 430019)
(Depa rtment o f Early W arning Surv eillance Intellig ence,AF RA2),Wuhan 430019)
A bstract A new adaptiv e genetic alg o rithm is presented o n the basic of the existing adaptive g ene tic alg o rithm to im-pro ve the cro ssve r probability a nd mutation pro bability.It bases the fitness v alue to adjust the c rossove r pr obability and mu-ta tion pro bability automa tically.Finally,some experiments sho w that the propo sed new alg o rithm is clearly improv ed in co n-v erg ent speed and stability and gets ex pectatio n effect.
Key Words g enetie algo rithm,adapta tio,adaptive g ene tic alg orithm
Class Nu mber T P301.6
1 引言
自适应遗传算法是具有比例选择,自适应交叉和变异操作的遗传算法的简称。针对不同的优化问题,简单遗传算法和一些改进的遗传算法的交叉概率和变异概率需要反复用实验来确定,而且不容易找到适用于所有问题的最佳值。而自适应遗传算法的交叉概率和变异概率是随适应度自动改变的,此方法能够采用相对某个解的最佳交叉概率和变异概率。自适应遗传算法不但能维持种群的多样性,而且还保证了遗传算法的收敛性[1]。
自适应遗传算法的缺点[2]:自适应遗传算法比较适用于进化的后期,对于进化的初期很不利。因为在进化初期,一些适应度较好的个体会处于一种几乎不变化的状态,从而导致种群中的其它个体很快被淘汰,加快了种群的收敛速度,但种群却很难收敛到全局最优解,最终出现早熟收敛。
2 自适应遗传算法的改进
1994年,Srinivas等人提出了一种根据适应度动态调整交叉概率P c和变异概率P m的自适应遗传算法(Adaptive Genetic Algorithm,AGA)[3]。在AGA 算法中,交叉概率和变异概率随着个体的适应度在种群平均适应度和最大适应度之间进行线性调整。当适应度越接近最大适应度时,交叉概率和变异概率越小;当适应度值接近或等于最大适应度值的个体时,交叉概率和变异概率接近或等于零。
任子武等人在S rinivas等提出的自适应遗传算法的基础上,提出一种改进的自适应遗传算法(Im pro ved Adaptive Genetic Alg orithm,IA-
＊收稿日期:2009年9月11日,修回日期:2009年10月11日作者简介:张国强,男,硕士研究生,研究方向:多媒体与虚拟现实技术。
84
张国强等:自适应遗传算法的改进与应用总第187期GA)[4]。IAGA算法为了保证每一代的优良个体
不被破坏,采用了精英保留策略,即如果下一代种
群的最优个体适应度值小于当前种群最优个体适
应度值,则将当前种群最优个体或者适应度值大于
下一代最优个体适应度值的多个个体直接复制到
一代,随机替代或替代最差的下一代种群中的相应
数量的个体。精英保留策略保证了当前的最优个
体不会被交叉、变异等遗传操作破坏。在IAGA算
法中,交叉概率P c和变异概率P m按如下公式进
行自适应调整。
P c=P c1-
(P c1-P c2)(f′-f a vg)
f max-f avg
f′≥f avg
P c1f′ (1) P m=P m1- (P m1-P m2)(f max-f) f max-f avg f≥f a vg P m1f (2) 在AGA算法中,当适应度值等于最大适应度值的时候,交叉概率和变异概率的值为零,容易产生局部最优解;在IAGA算法中,较差个体的变异能力较低,容易产生停滞现象。而精英保留策略虽然起到了保护和推广优秀个体的作用,但是其个体数目不宜过大,否则会使种群进化陷入停滞不前,造成局部收敛[5]。 为了克服这两种自适应遗传算法的不足之处,本文在Srinivas等人提出的AGA算法的基础上,结合任子武等人提出的IAGA算法,对自适应遗传算法的交叉概率和变异概率进行改进,提出了根据适应度值来动态调整交叉概率和变异概率的一种新的自适应遗传算法(New Adaptive Genetic Al-g orithm,NAGA)。交叉概率P c和变异概率P m按如下公式进行自适应调整。 P c=P c1(f avg-f′)+P c2(f′-f min) f a vg-f min f′ P c2(f avg-f′)+P c3(f′-f avg) f max-f avg f′≥f a vg (3) P m=P m1(f avg-f )+P m2(f-f min) f avg-f min f P m2(f avg-f)+P m3(f-f avg) f max-f a vg f≥f a vg (4) 式中:f max为种群最大的适应度值,f a vg为每代种群的平均适应度值,f min为种群的最小适应度值,f′为要交叉的两个个体中较大的适应度值,f为要变异个体的适应度值,P c1>P c2>P c3,P m1>P m2>P m3取(0,1)区间的值,可在优化过程中调整。 因此,根据本文提出的新的自适应遗传算法的交叉概率和变异概率的公式,可以得出交叉概率P c和变异概率P m随适应度值的变化情况,如图1所示。 图1 N A GA算法自适应交叉概率和变异概率 本文提出的改进的交叉概率和变异概率,是根据适应度值的集中程度,以种群为单位,自适应地变化整个种群的交叉概率P c和变异概率P m,采用种群的最大适应度值f max,最小适应度值f min和平均适应度值f a vg这三个变量来衡量种群适应度值的集中程度。使交叉概率P c和变异概率P m随着个体的适应度值在种群的最小适应度、平均适应度和最大适应度之间进行调整。 由式(1)可知,当要交叉的两个个体中较大的适应度值大于或等于平均适应度值时的自适应调整公式以及当要交叉的两个个体中较大的适应度值小于平均适应度值时,则认为交叉概率P c等于指定值。而本文的改进的交叉概率要随着个体的适应度值在种群的最小适应度、平均适应度和最大适应度之间进行调整。当要交叉的两个个体中较大的适应度值小于平均适应度值时,要交叉的两个个体中较大的适应度值应该在最小适应度值和平均适应度值之间调整。由此得到本文的交叉概率P c式(3)。同理由式(2)得到变异概率P m式(4)。 改进后的交叉概率和变异概率不但能够随适应度自动改变,而且使种群中最大适应度值的个体的交叉概率和变异概率不为零,这就相应地提高了种群中表现优良的个体的交叉概率和变异概率,使得它们不会处于一种近似停滞不前的状态,从而使算法跳出局部最优解。将个体的适应度与当代种群的平均适应度进行比较,在种群演化中有效地保留了优秀个体的模式,增强了较差个体的变异能力,使算法能跳出局部最优解,克服早熟的缺点。 3 仿真实验分析 为了比较本文算法(NAGA算法)的收敛速度,选取一个简单的单峰值函数(DeJong球函数)进行实验。将NAGA算法与AGA算法以及IA-GA算法的独立实验结果进行比较。待优化的函 (下转第159页) 2010年第1期舰船电子工程 159 如果要复现物体,则将绘制掩码设置为0×0就可以了。 5 结语 对于虚拟场景的仿真系统,虽然再现真实的环境、达到非常逼真的仿真效果是必要的,而对于用户来说,把自己所感兴趣、所要观察的物体突出的、直观的显示出来,则显得更加重要。本文的工作就是采用Multigen Creator 建模软件,建立了合理的舱室模型分层结构;然后,通过Vega 提供的仿真应用平台,对模型进行操作与管理,并实现目标对象的无遮挡显示。 参考文献 [1]李志文,韩晓玲.虚拟现实技术研究现状及未来发展 [J ].信息技术与信息化,2005(3):94～96 [2]任鸿翔,金一丞,王科伦.场景建模的层次结构[J ].中 国图象图形学报,2003(8):521～525 [3]王乘,周均清,李利军.Crea to r 可视化仿真建模技术 [M ].武汉:华中科技大学出版社,2005 [4]刘航,王春水,王积忠.基于Creato r /V ega 的虚拟场景 设计[J ].计算机仿真,2007,24(9):228～231 [5]王乘,周均清,李利军,等.V ega 实时三维视景仿真技术 [M ].武汉:华中科技大学出版社,2005 [6]MultiGen -Paradig m Inc .Vega Prog rammer s Guide (Ver -sion 3.7.1)[M ].USA :M ultiGen -Paradigm Inc ,2001 (上接第84页)数为: f (x i )=100-∑3 i =1 x 2 i (5) 其中,x ∈[-5.12,+5.12],此问题为极大值问题,该函数的极大值在(0,0,0)处为100。将各算法分别独立实验30次的结果平均值记录于表中,则实验结果比较如表1所示。 表1 各种遗传算法达到指定函数值的平均进化代数比较表优化函数值A GA 算法 IA G A 算法N A GA 算法 99.042.7199.574.6199.9268.1199.955711.6199.9913537.11.799.99516546.21.899.999 — 51.1 2.6 99.9995—53.83.8 注:“—”表示进化代数超过200代仍达不到指定值,即本次计算不收敛 由表1中的数据可以发现,NAGA 算法在收敛速度上有了明显提高。AGA 算产生了实验结果不收敛的现象;IAGA 算法虽然没有产生实验结果不收敛的现象,但是可以看出,当优化函数值接近最优值100时,NAGA 算法在30次实验中的平均进化代数为3.8,其实验结果明显优于其它两种算法因此,从表1的实验结果比较可知,NAGA 算法不仅具有较快的收敛速度,而且能得到更优越的解,它的性能比简单遗传算法和现有的一些自适应遗传算法均有一定改善。 4 结语 全局优化和快速收敛本来就是相互矛盾的,一种较好的算法就要综合考虑全局优化和快速收敛,选择一种实际效果较好的方法实验结果表明,本文提出的改进的自适应遗传算法(NAGA 算法)在提高收敛性能的同时,基本保持了遗传算法的运算速度,在快速收敛和全局最优之间获得了较好的平衡,从而保证了种群能够快速协调地进化。 参考文献 [1]Wang H ongjian ,Zhao Jie ,Bian Xinqian ,et al .A n im -pro ved path planner ba sed o n adaptiv e g enetic alg o rithm for autonomous underw ater vehicle [C ]∥P roceedings of the IEEE Internatio nal Co nfe rence on M echa tronics and A uto matio n ,2005,2:857～861 [2]王小平,曹立明.遗传算法—理论、应用与软件实现 [M ].西安:西安交通大学出版社,2002:9,14～15,25～28,68 [3]S RIN IV AS M ,PA T N A IL K L M .A daptive pro babili -ties of cro sso ver and muta tion in g enetic alg o rithms [J ].IEEE T ransactio n on Sy stem ,M an and Cy be rne tics ,1994,24(4):656～667 [4]任子武,伞冶.自适应遗传算法的改进及在系统辨识中 应用研究[J ].系统仿真学报,2006,18(1):41～66[5]黄康,许志伟,董迎晖.改进的遗传算法及其在多目标 优化设计中的应用[J ].机械设计,2005,22(9):735～738 自适应遗传算法 自适应遗传算法 一.主要流程： 1. 参数的初始化。设定遗传种群规模N ，阵元数M ，信源数P 等。 2. 编码。采用十进制编码方法。 3. 初始种群的产生。随机数生成。 4. 适应度函数的评价。选取 ()() R P ΘA )tr f = （1） 其中， H 1H )(A A A A P A -= （2） P A 是A 的投影矩阵，A 是阵列流型。 ∑==L i L 1 H 1XX R ) （3） R )是数据协方差矩阵的最大似然估计。 5. 选择。比例选择方法与精英选择方法结合使用，在当代种群中选择优良个体遗传到下一代。既保证了种群的多样性，也使最优个体得以保留。 1）比例选择方法（赌轮盘法）：每个个体被选中的概率与它的适应度函数值大小成正比，即适应度函数越高的个体被选中的概率也就越高。 2）精英选择方法：让种群中适应度函数值最高的个体不进行配对交叉，直接复制到下一代中。但是容易陷入局部最优解，全局搜索能力差。 6. 交叉。按照概率P c 对种群中个体两两配对，进行交叉操作。本文中选取算数交叉的方式。 算数交叉：是由两个个体的线性组合来产生新的个体，假设第t 代的两个个体为A (t)、B (t)，则算数交叉后产生的新个体是 ()()()()t t t A B A αα-+=+11 （4） ()()()()t t t B A B αα-+=+11 （5） 其中，α选取（0，1）之间的随机数。 交叉概率：使交叉概率随着遗传代数的增长，逐渐减小，目的是进化前期注重交叉运算，全局搜索能力强。 2.02cos *4.0+?? ? ??*=πK T P c （6） 其中，T 是进化代数，K 是总进化次数。 7. 变异。按照概率P m 对种群个体进行变异。本文中选取均匀变异的方式。 均匀变异：如某基因座上的基因值为X k ，其取值范围为[Umin,Umax],对其进行变异后的值为 )U -r(U +U =X min max min k （7） 其中，r 选取[0,1]之间的随机数。 变异概率：使变异概率随着遗传代数的增长，逐渐增加，目的是进化后期注重变异运算，局部搜索能力强。 005.02sin *045.0+?? ? ??*=πK T P m （8） 其中，T 是进化代数，K 是总进化次数。 8. 终止条件判断。若已达到设定的最大遗传代数，则迭代终止，输出最优解；若不满足终止条件，则返回第4步，进行迭代寻优过程。 第!"卷第#期 纺织高校基础科学学报$%&’!"()%’##**+年,月-./01/102312/45673.859:2;:082630<27/0:0= =============================================================2/ >?@’(#**+文章编号A !**,B C D +!E #**+F *#B *!,"B *+ 基于自适应交叉G 变异遗传算法的H I J 整定 王莉 E 中国矿业大学信电学院(江苏徐州##!**C F 摘要A 提出了一种带有自适应交叉G 变异算子的遗传算法(并把它应用到H I J 参数的整定当中’仿真结果表明(该方法提高了参数的优化性能(对控制系统具有良好的控制精度G 动态性能和鲁棒性’ 关键词A 自适应遗传算法LH I J L 参数优化 中图分类号A M H#"D 文献标识码A N *前言 H I J 控制算法以其原理简单G 鲁棒性好G 可靠性高等特点(在生产过程自动控制的发展历程中(成为历史悠久G 生命力最强的控制方式’虽然随着科学技术的发展涌现出许多新的控制方法(但是直到现在(H I J 控制由仍然广泛地应用于各类控制系统中’ 常用的H I J 参数整定方法主要由传统整定方法G 最优整定方法和智能整定方法’传统的整定方法包括稳定边界法E 临界比例度法F G 衰减曲线法G 动态特性法和O P Q R &Q S )P T U %&V 经验公式E O )公式法F 等’ 图!H I J 控制图 典型的H I J 控制图如图!所示’ 随着计算机技术和最优控制理论的 发展(出现了基于计算机的H I J 参数最 优整定方法’最优控制理论的应用(加上 计算机的高速运算能力(赋予了H I J 参 数优化等多变量最优化问题以新的生命 力(该方法是针对特定的系统建立数学 模型(运用各种数值解法按照一定的性能指标进行优化’近年来(随着智能控制理论的发展(专家系统G 模糊控制以及神经网络日益受到控制界的重视(出现了一些智能优化手段(主要由专家智能型H I J 参数自整定技术G 基于模糊推理的H I J 自寻优技术G 以及基于先进优化方法的其他智能整定技术W !(#X 等’本文中提出的基于改进遗传算法的H I J 参数整定( 利用遗传算法对优化问题本身没有什么特殊要求(既不要连续也不要求可微的优点(实现了H I J 参数的在线寻优’ K 收稿日期A #**+B *#B #* 作者简介A 王莉E !Y "Z B F (女(安徽省人(中国矿业大学信电学院(硕士研究生(主要从事控制理论与控制工程方面的研究’万方数据 基于遗传算法的OFDM自适应资源分配算法MATLAB源码 OFDM自适应资源分配问题（载波、功率等），是一个既含有离散决策变量，又含有连续决策变量的非线性优化模型，且含有较为复杂的非线性约束，因此适合采用智能优化算法进行求解。 function [BESTX1,BESTX2,BESTY,ALLX1,ALLX2,ALL Y]=GA2(K,N,Pm,H,BBB,P,N0) %% 本源码实现遗传算法，用于RA准则下的多用户OFDM自适应资源分配 %% 输入参数列表 % K 迭代次数 % N 种群规模，要求是偶数 % Pm 变异概率 % H 信道增益矩阵，K*N的矩阵，表示用户k在子信道n上的信道增益，无单位，取值范围0~1 % BBB 总带宽（Hz） % P 总功率（W） % N0 加性高斯白噪声功率谱密度（W/Hz） %% 输出参数列表 % BESTX1 K×1细胞结构，每一个元素是M×1向量，记录每一代的最优个体的第一分量 % BESTX2 K×1细胞结构，每一个元素是M×1向量，记录每一代的最优个体的第二分量 % BESTY K×1矩阵，记录每一代的最优个体的评价函数值 % ALLX1 K×1细胞结构，每一个元素是M×N矩阵，记录全部个体的第一分量 % ALLX2 K×1细胞结构，每一个元素是M×N矩阵，记录全部个体的第二分量 % ALL Y K×N矩阵，记录全部个体的评价函数值 %% 第一步 [KK,NN]=size(H); M=NN;%决策变量个数，子载波个数 farm1=zeros(M,N);%每一列是一个样本 for i=1:N farm1(:,i)=unidrnd(KK,M,1); end farm2=zeros(M,N);%每一列是一个样本 for i=1:N farm2(:,i)=RandSeq(M); end %输出变量初始化 ALLX1=cell(K,1); ALLX2=cell(K,1); ALL Y=zeros(K,N); BESTX1=cell(K,1); 遗传算法属于进化算法( Evolutionary Algorithms) 的一种, 它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子: 选择、交叉和变异. 。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法( GA)。算法中称遗传的生物体为个体( individual )，个体对环境的适应程度用适应值( fitness )表示。适应值取决于个体的染色体(chromosome),在算法中染色体常用一串数字表示，数字串中的一位对应一个基因 (gene)。一定数量的个体组成一个群体(population )。对所有个体进 行选择、交叉和变异等操作,生成新的群体,称为新一代( new generation )。遗传算法计算程序的流程可以表示如下［3］：第一步准备工作 (i)选择合适的编码方案，将变量(特征)转换为染色体(数字串，串长为m。通常用二 进制编码。 (2 )选择合适的参数，包括群体大小(个体数M)、交叉概率PC和变异概率Pm (3、确定适应值函数f (x、。f (x、应为正值。 第二步形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中，取已分析的可能滑裂 面组作为初始群体。 第三步对每一染色体(串)计算其适应值fi ,同时计算群体的总适应值。 第四步选择 计算每一串的选择概率Pi=fi/F 及累计概率。选择一般通过模拟旋转滚花轮 ( roulette ,其上按Pi大小分成大小不等的扇形区、的算法进行。旋转M次即可选出M个串来。在计算机 上实现的步骤是：产生［0,1］间随机数r，若r 第三章 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland 的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。 3.1 模式定理 不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。 定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。 以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。 引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n 个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容 定义3.2 模式H 中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。 显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 定义3.3 模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H δ。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。 模式的阶数和定义距描述了模式的基本性质。 下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令)(t A 表示第t 代中串的群体，以),,2,1)((n j t A j =表示第t 代中第j 个个体串。 1．选择算子 在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下： 设在第t 代种群)(t A 中模式所能匹配的样本数为m ，记为),(t H m 。在选择中，一个位串 j A 以概率/j j i P f f =∑被选中并进行复制，其中j f 是个体)(t A j 的适应度。假设一代中群体 大小为n ，且个体两两互不相同，则模式H 在第1+t 代中的样本数为： 自适应Simpson积分算法（MATLAB及C++实现代码） (计算数学课用) 在CSDN论坛中找到了却要金币，无奈之下自己写了一份。 对于类似问题，改一下积分函数和区间即可。 针对问题：数学上已经证明了 ∫ 4 1+x2 dx=π 1 成立，所以可以通过数值积分来求π的近似值。 试利用自适应Simpson算法计算积分近似值。 C++版：(直接复制粘贴在VC++6.0即可运行) /*用自适应Simpson积分方法计算积分值*/ #include function [xv,fv]=AdapGA(fitness,a,b,NP,NG,Pc1,Pc2,Pm1,Pm2,eps) %×?êêó|ò?′???·¨ L = ceil(log2((b-a)/eps+1)); x = zeros(NP,L); for i=1:NP x(i,:) = Initial(L); fx(i) = fitness(Dec(a,b,x(i,:),L)); end for k=1:NG sumfx = sum(fx); Px = fx/sumfx; PPx = 0; PPx(1) = Px(1); for i=2:NP PPx(i) = PPx(i-1) + Px(i); end for i=1:NP sita = rand(); for n=1:NP if sita <= PPx(n) SelFather = n; break; end end Selmother = round(rand()*(NP-1))+1; posCut = round(rand()*(L-2)) + 1; favg = sumfx/NP; fmax = max(fx); Fitness_f = fx(SelFather); Fitness_m = fx(Selmother); Fm = max(Fitness_f,Fitness_m); if Fm>=favg Pc = Pc1*(fmax - Fm)/(fmax - favg); else Pc = Pc2; end r1 = rand(); if r1<=Pc nx(i,1:posCut) = x(SelFather,1:posCut); nx(i,(posCut+1):L) = x(Selmother,(posCut+1):L); fmu = fitness(Dec(a,b,nx(i,:),L)); if fmu>=favg Pm = Pm1*(fmax - fmu)/(fmax - favg); else Pm = Pm2; matlab遗传算法工具箱函数及实例讲解（转引） 核心函数：? (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数?【输出参数】? ?pop--生成的初始种群?【输入参数】? ?num--种群中的个体数目? ?bounds--代表变量的上下界的矩阵? ?eevalFN--适应度函数? ?eevalOps--传递给适应度函数的参数? ?options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如? precision--变量进行二进制编码时指定的精度? F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度)? (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts.? ?termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs ,mutOps)--遗传算法函数?【输出参数】? x--求得的最优解? endPop--最终得到的种群? bPop--最优种群的一个搜索轨迹?【输入参数】? bounds--代表变量上下界的矩阵? evalFN--适应度函数? evalOps--传递给适应度函数的参数? startPop-初始种群? opts[epsilon prob_ops display]--opts(1:2)等同于initializega 的options参数，第三个参数控制是否输出，一般为0。如[1e-6 termFN--终止函数的名称,如['maxGenTerm']? termOps--传递个终止函数的参数,如[100]? selectFN--选择函数的名称,如['normGeomSelect']? selectOps--传递个选择函数的参数,如[0.08]? xOverFNs--交叉函数名称表，以空格分开，如['arithXover heuristicXover simpleXover']? xOverOps--传递给交叉函数的参数表，如[2 0;2 3;2 0]? mutFNs--变异函数表，如['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation']? mutOps--传递给交叉函数的参数表,如[4 0 0;6 100 3;4 100 3;4 0 0]?注意】matlab工具箱函数必须放在工作目录下?【问题】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0=x=9?【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08?【程序清单】? 最新最全的遗传算法工具箱Gaot_v5及说明 Gaot_v5下载地址：https://www.wendangku.net/doc/095781348.html,/mirage/GAToolBox/gaot/gaotv5.zip 添加遗传算法路径： 1、 matlab的file下面的set path把它加上，把路径加进去后在 2、 file→Preferences→General的Toolbox Path Caching里点击update Toolbox Path Cache更新一下，就OK了 遗传算法工具箱Gaot_v5包括许多实用的函数，各种算子函数，各种类型的选择方式，交叉、变异方式。这些函数按照功能可以分成以下几类： 主程序 ga.m提供了 GAOT 与外部的接口。它的函数格式如下： [x endPop bPop traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps, selectFn,selectOps,xOverFNs,xOverOps,mutFNs,mutOps) 输出参数及其定义如表 1 所示。输入参数及其定义如表 2 所示。 表1 ga.m的输出参数 输出参数 定义 x 求得的最好的解，包括染色体和适应度 endPop 最后一代染色体（可选择的） bPop 最好染色体的轨迹（可选择的） traceInfo 每一代染色体中最好的个体和平均适应度（可选择的） 表2 ga.m的输入参数 表3 GAOT核心函数及其它函数 核心函数： (1)function [pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始种群的生成函数 【输出参数】 pop--生成的初始种群 【输入参数】 num--种群中的个体数目 bounds--代表变量的上下界的矩阵 eevalFN--适应度函数 eevalOps--传递给适应度函数的参数 options--选择编码形式(浮点编码或是二进制编码)[precision F_or_B],如 precision--变量进行二进制编码时指定的精度 F_or_B--为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)function [x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,... termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)--遗传算法函数 【输出参数】 x--求得的最优解 endPop--最终得到的种群 bPop--最优种群的一个搜索轨迹 【输入参数】 变异概率自适应调整的遗传算法算例 一：优化函数：()()*sin 10*2,[1,2] f x x x x =+∈-+ A.变异概率自适应调整公式： B.遗传算法参数 （1）种群规模设为80，遗传算子分别为轮盘法选择，多点点交叉和多点自适应变异； （2）交叉概率0.7，变异概率0.01； （3）最大进化代数为100代，保优操作。 C.程序框图 图 1 程序流程框图 ()()12max 1max 1 ,,m m m avg avg m m avg P P f f P f f f f P P f f --?-≥?-=?? 二：程序及运行结果 （1）%变异概率自适应调整的GA程序 %优化函数为f=x*sin(10*x)+2，其中，-1= 自适应小生境遗传算法的性能分析1 李明林 （福州大学机械工程及自动化学院 福建福州 350002） E-mail：lml_006@https://www.wendangku.net/doc/095781348.html, 摘 要：本文提出一种改进的维持物种多样性的小生境实现技术——自适应小生境遗传算法。该算法以Mahfoud提出的确定性排挤策略为基础，采用数值编码，并结合算术交叉、非均匀变异和高斯变异、自适应变异概率。经过实验分析，验证了该算法能有效地、自适应地形成小生境进化环境，并具备相当的收敛速度和相当的求解精度。 关键词：小生境，自适应，遗传算法，多态优化，排挤 1 引言 作为一种模拟生物在自然环境中遗传和进化过程的自适应全局优化搜索算法，遗传算法以其明显优于传统优化算法的鲁棒性、自适应性、全局优化性和隐含并行性广泛地用于求解各种工程优化问题。近年来，人们特别关注发展用于多目标优化、多峰值函数优化与组合优化问题的小生境遗传算法[1]。 观察各种小生境的实现方法，可看出其共同点都是为了有效地维持群体的多样性。而其差别可归纳为两种基本类型：一种是将连续的、无限的搜索空间划分为离散的、有限的小生境区域；另一种则是对种群的适应度作适当的修整以抑制超级个体的复制概率来维持进化过程中的群体多样性。前一种类型以De Jong 提出的基于排挤机制（Crowding）的小生境实现方法为代表（1975），后一种类型以Goldberg等提出的基于共享机制（Sharing）的小生境技术为代表（1987）。在此基础上，各种各样的小生境技术不断出现。我们项目的研究主要是对一些有代表性的技术进行性能分析，为小生境遗传算法的实际工程应用提供有用的设计依据。 本文首先在深入理解Mahfoud提出的基于确定性排挤机制（Deterministic Crowding）的小生境思想的基础上，以实验的手段论证其思想的有效性和正确性。在实验过程中，不断修改程序的各个组成部分，并用于函数优化测试。最后发现一种程序组合具有较明显的特点。它可维持种群的多样性，而且可自适应形成大小、形状各异的小生境。因此将它称为自适应小生境遗传算法（简称SNGA）。 本文首先介绍确定性排挤机制的基本思想和算法结构，结合文献[2]的遗传算子编写了SNGA类库函数。其次结合三种较为典型的数值优化测试函数，对SNGA进行实验分析。最后对SNGA进行总结讨论。 2 确定性排挤机制和SNGA 1970年，Cavicchio提出了基于预选择机制（Preselection）的小生境技术，其基本思想是父代个体经过遗传操作后生成子代个体，父子个体相互竞争，适应度高的进入下一代群体中。DeJong于1975年一般化了Cavicchio的预选择机，在其博士论文提出了基于排挤机制（Crowding）的小生境技术。即：在父代群体中选取部分个体作为小生境主体，在新生子代群体中与小生境主体相似的个体不得进入下一代群体。他们声称这两种方法都可在群体中形成小生境的进化环境，并维持了群体的多样性。 1本课题得到福建省教育厅（JB04025）项目资助。 多方式进化遗传算法Matlab源代码 对于单种群进化，多方式进化是提高全局搜索能力和收敛速度的一种有效策略 该程序采用： 编码：二进制编码、实数编码（默认） 选择：非线性排名选择（主要表现在前期），锦标赛选择（主要表现在后期，含精英保留），由于单纯的转轮盘选择存在诸多弊端，这里没有采用 交叉：二进制编码采用多点交叉和均匀交叉，并逐步增大均匀交叉概率 实数编码采用离散交叉（前期）、算术交叉（中期）、AEA重组（后期） 变异：二进制编码采用随机变异 实数编码采用两种自适应变异和两种随机变异，且尽量采用前者 到位：适当的到位可以提高种群的多样性 function [X,MaxFval,BestPop,Trace]=fga(FUN,bounds,MaxEranum,PopSize,options,pCross,pMutation,pInversion) % [X,MaxFval,BestPop,Trace]=fga(FUN,bounds,MaxEranum,PopSize,options,pCross,pMutation,pInversion) % Finds a maximum of a function of several variables. % fga solves problem s of the form: % max F(X) subject to: LB <= X <= UB % BestPop - 最优的群体即为最优的染色体群 % Trace - 每代最佳个体所对应的目标函数值 % FUN - 目标函数 % LB - 自变量下限 % UB - 自变量上限 % eranum - 种群的代数,取50--500(默认200) % popsize - 每一代种群的规模；此可取50--200(默认100) % pcross - 交叉概率,一般取0.5--0.85之间较好(默认0.8) % pmutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1) % pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2) % options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编码,option(2)设定求解精度(默认1e-4) T1=clock; %检验初始参数 if nargin<2, error('FMAXGA requires at least three input arguments'); end if nargin==2, MaxEranum=100;PopSize=100;options=[1 1e-4];pCross=0.85;pMutation=0.1;pInversion=0.25;end if nargin==3, PopSize=100;options=[1 1e-4];pCross=0.85;pMutation=0.1;pInversion=0.25;end if nargin==4, options=[1 1e-4];pCross=0.85;pMutation=0.1;pInversion=0.25;end if nargin==5, pCross=0.85;pMutation=0.1;pInversion=0.25;end if nargin==6, pMutation=0.1;pInversion=0.25;end if nargin==7, pInversion=0.25;end if (options(1)==0|options(1)==1)&find((bounds(:,1)-bounds(:,2))>0) error('数据输入错误,请重新输入:'); end %s=sprintf('程序运行需要约%.4f 秒钟时间,请稍等......',(eranum*popsize/1000)); %disp(s); % 定义全局变量 global m n NewPop children1 children2 VarNum % 初始化种群和变量 遗传算法( GA , Genetic Algorithm ) ，也称进化算法。遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。 一.进化论知识 作为遗传算法生物背景的介绍，下面内容了解即可： 种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。 个体：组成种群的单个生物。 基因 ( Gene ) ：一个遗传因子。 染色体 ( Chromosome )：包含一组的基因。 生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。 遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。 简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。 二.遗传算法思想 借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。 举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中 论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日 摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由 遗传算法总结 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。 一、遗传算法流程图 算法开始 原问题参数集 染色体编码，产生初始种群 计算种群中个体的适应值 终止条件判断 N 选择 交叉 Y 变异 新种群 输出结果 算法结束 图1 遗传算法流程图 二、遗传算法的原理和方法 1）染色体编码 把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。 De Jong 曾提出了两条操作性较强的实用编码原则：编码原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案；编码原则二：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。 编码方法主要有以下几种：二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法、参数级联编码方法、多参数交叉编码方法。 2） 适应值计算 由解空间中某一点的目标函数值()f x 到搜索空间中对应个体的适应度函数值 (())Fit f x 的转换方法基本上有一下三种： a ． 直接以待解的目标函数值()f x 转化为适应度函数值(())Fit f x ，令 () (())=() f x Fit f x f x ?? -?目标函数为最大化函数 目标函数为最小化函数 b ． 对于最小值的问题，做下列转化max max () () (())0 C f x f x C Fit f x - 自适应遗传算法 一.主要流程： 1. 参数的初始化。设定遗传种群规模N ，阵元数M ，信源数P 等。 2. 编码。采用十进制编码方法。 3. 初始种群的产生。随机数生成。 4. 适应度函数的评价。选取 ()() R P ΘA tr f = （1） 其中， H 1H )(A A A A P A -= （2） P A 是A 的投影矩阵，A 是阵列流型。 ∑==L i L 1 H 1XX R （3） R 是数据协方差矩阵的最大似然估计。 5. 选择。比例选择方法与精英选择方法结合使用，在当代种群中选择优良个体遗传到下一代。既保证了种群的多样性，也使最优个体得以保留。 1）比例选择方法（赌轮盘法）：每个个体被选中的概率与它的适应度函数值大小成正比，即适应度函数越高的个体被选中的概率也就越高。 2）精英选择方法：让种群中适应度函数值最高的个体不进行配对交叉，直接复制到下一代中。但是容易陷入局部最优解，全局搜索能力差。 6. 交叉。按照概率P c 对种群中个体两两配对，进行交叉操作。本文中选取算数交叉的方式。 算数交叉：是由两个个体的线性组合来产生新的个体，假设第t 代的两个个体为A (t)、B (t)，则算数交叉后产生的新个体是 ()()()()t t t A B A αα-+=+11 （4） ()()()()t t t B A B αα-+=+11 （5） 其中，α选取（0，1）之间的随机数。 交叉概率：使交叉概率随着遗传代数的增长，逐渐减小，目的是进化前期注重交叉运算，全局搜索能力强。 2.02cos *4.0+?? ? ??*=πK T P c （6） 其中，T 是进化代数，K 是总进化次数。 7. 变异。按照概率P m 对种群个体进行变异。本文中选取均匀变异的方式。 均匀变异：如某基因座上的基因值为X k ，其取值范围为[Umin,Umax],对其进行变异后的值为 )U -r(U +U =X min max min k （7） 遗传算法入门（上）代码中的进化学说与遗传学说 写在之前 算法所属领域 遗传算法的思想解析 为什么要用遗传算法？ 科研现状 应用现状 遗传算法入门系列文章： （中篇）遗传算法入门（中）实例，求解一元函数最值（MATLAB版）（下篇）遗传算法入门（下）实例，求解TSP问题（C++版） 写在之前 说明：本想着用大量篇幅写一篇“关于遗传算法的基本原理”作为本系列入门的第一篇，但是在找寻资料的过程中，看到网络上有大量的关于遗传算法的介绍，觉得写的都挺好，所以本文我就简单写点自己的理解。 推荐几篇关于遗传算法的介绍性文章： 遗传算法详解（GA）（个人觉得很形象，很适合初学者） 算法所属领域 ? 相信每个人学习一门知识之前，都会想知道这门知识属于哪一门学科范畴，属于哪一类技术领域？ ? 首先对于这种问题，GA是没有绝对的归属的。算法的定义是解决问题的一种思想和指导理论。而遗传算法也是解决某一问题的一种思想，用 某一编程语言实现这种思想的程序具有很多特点，其中一个便是智能性和进化性，即，不需要大量的人为干涉，程序本身能够根据一定的条件自我筛选，最终得出令人满意的结果。所以按照这种特性，把它列为人工智能领域下的学习门类毫无疑问是可以的。遗传算法的思想是借鉴了达尔文的进化学说和孟德尔的遗传学说，把遗传算法说成是一门十足的仿生学一点都不过分。然而从应用的角度出发，遗传算法是求最优解问题的好方法，如信号处理中的优化、数学求解问题、工业控制参数最优解、神经网络中的激活函数、图像处理等等，所以把遗传算法说成优化范畴貌似也说的过去。为了方便理解，我们可以暂时将其定位为人工智能–智能优化，这也是很多书中描述遗传算法的惯用词汇。 遗传算法的思想解析 遗传算法（gentic algorithms简称GA）是模拟生物遗传和进化的全局优化搜索算法 ? 我们知道，在人类的演化中，达尔文的进化学说与孟德尔的遗传学说起着至关重要的理论指导。每个人作为一个个体组成一个人类种群，正是经历着物竞天择，才会让整个群体慢慢变的更好，即更加适应周围的环境。而每一代正是靠着基因交叉与变异才能繁衍出更加适应大自然规律的下一代个体。总之，在漫长的迭代进化中，一个不适应环境的群体，在物竞天择和交叉变异中慢慢变的适应了环境。 ? GA的思想完全模拟了生物的进化和遗传方式。我们在求解一个问题的最优解时，先人为的产生很多任意的解，组成一个解集（一个解是一个个体，一个解集是一个种群），这些解有好有坏。我们的最终目的是让这自适应遗传算法讲解学习
基于自适应交叉、变异遗传算法的PID整定
基于遗传算法的OFDM自适应资源分配算法MATLAB源码
遗传算法的优缺点
第三章-遗传算法的理论基础
自适应Simpson积分算法MATLAB及C实现代码.docx
matlab自适应遗传算法
遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )
最新最全的遗传算法工具箱及说明
变异概率自适应调整的遗传算法GA程序
自适应小生境遗传算法的性能分析
多方式进化遗传算法Matlab源代码
遗传算法解释及代码(一看就懂)
遗传算法应用论文
遗传算法总结【精品毕业设计】(完整版)
自适应遗传算法
遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )