变异概率自适应调整的遗传算法算例
一：优化函数：()()*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= %编码长度为12位 %种群规模设为80，遗传算子分别为轮盘法选择，多点点交叉和多点自适应变异。 %交叉概率0.7，变异概率0.01 %最大进化代数为100代，保优操作。 %**********************%主函数***************************************** function main() global chrom lchrom oldpop newpop varible fitness popsize sumfitness %定义全局变量 global pcross pmutation temp bestfit maxfit gen bestgen global maxgen po pp mp np lchrom=12; %染色体长度 popsize=80; %种群大小 pcross=0.7; %交叉概率 pmutation=0.01; %变异概率 maxgen=100; %最大代数 po=0.1; %淘汰概率 pp=0.1; %保护概率 mp=floor(pp*popsize); %保护的个数 np=floor(po*popsize); %淘汰的个数 initpop; % 初始化种群 for gen=1:maxgen objfun; %计算适应度值 pp_po; %执行保优操作 select; %选择操作 selfmutation; %自变异操作 crossover; %交叉操作 end best bestfit % 最佳个体适应度值输出 bestgen % 最佳个体所在代数输出 figure gen=1:maxgen; plot(gen,maxfit(1,gen)); % 进化曲线 hold on; plot(bestgen,bestfit); xlabel('Generation'); ylabel('Fitness'); %********************** 产生初始种群 ************************************ function initpop() global lchrom oldpop popsize chrom for i=1:popsize chrom=rand(1,lchrom); % lchrom=12 染色体长度 for j=1:lchrom if chrom(1,j)<0.5 chrom(1,j)=0; else chrom(1,j)=1; end end oldpop(i,1:lchrom)=chrom; end %************************%计算适应度值************************************ function objfun() global lchrom oldpop fitness popsize chrom maxfit gen varible avgfiness savgfitness % a=0;b=3; a=0;b=10; for i=1:popsize chrom=oldpop(i,:); c=decimal(chrom); varible(1,i)=a+c*(b-a)/(2.^lchrom-1); %对应变量值 fitness(1,i)=varible(1,i)*sin(10*varible(1,i))+2; avgfitness=sum(fitness)/popsize; lsort; % 个体排序 maxfit(1,gen)=max(fitness); %求本代中的最大适应度值maxfit %************************二进制转十进制********************************** function c=decimal(chrom) global lchrom popsize c=0; for j=1:lchrom c=c+chrom(1,j)*2.^(lchrom-j); end %************************* 个体从小到大排序 ************************ function lsort() global popsize fitness oldpop for i=1:popsize j=i+1; while j<=popsize if fitness(1,i)>fitness(1,j) tf=fitness(1,i); % 适应度值 tc=oldpop(i,:); % 基因代码 fitness(1,i)=fitness(1,j); % 适应度值互换 oldpop(i,:)=oldpop(j,:); % 基因代码互换 fitnescs(1,j)=tf; oldpop(j,:)=tc; end j=j+1; end end %*************************保优操作***************************** function pp_po() global popsize oldpop np i=np+1; % np=floor(po*popsize); %淘汰的个数np while i<=popsize %将（np+1）～popsize的个体放在toldpop中，共（popsize-np）个 toldpop(j,:)=oldpop(i,:); j=j+1; i=i+1; end for i=1:(popsize-np) %从小到大顺序排列，将前面np个淘汰 oldpop(i,:)=toldpop(i,:); % 适应度是否也要互换？ end %*************************转轮法选择操作********************************** function select() global fitness popsize sumfitness oldpop temp mp np sumfitness=0; %个体适应度之和 for i=1:(popsize-np-mp) % 仅计算(popsize-np-mp)个个体的选择概率 sumfitness=sumfitness+fitness(1,i); end for i=1:(popsize-mp-np) % 仅计算(popsize-np-mp)个个体的选择概率 p(1,i)=fitness(1,i)/sumfitness; % 个体染色体的选择概率 end q=cumsum(p); % 个体染色体的累积概率（内部函数），共(popsize-np-mp)个 b=sort(rand(1,(popsize-mp))); % 产生(popsize-mp)个随机数，并按升序排列。mp为保护个体数 j=1; k=1; while j<=(popsize-mp) % 从(popsize-mp-np)中选出(popsize-mp)个个体，并放入temp(j,:)中； if b(1,j) temp(j,:)=oldpop(k,:); j=j+1; else k=k+1; end end j=popsize-np-mp+1; % 从统一挪过来的（popsize-np-mp）以后个体——优秀个体中选择for i=(popsize-mp+1):popsize % 将mp个保留个体放入交配池temp(i,:)，以保证群体数popsize temp(i,:)=oldpop(j,:); j=j+1; end %*********************%自适应变异操作************************************* function selfmutation() global i popsize lchrom pmutation temp newpop oldpop mp fitness avgfitness maxfitness m=lchrom*(popsize-mp); % 总的基因数 pm1=pmutation; pm2=0.005; a=0; b=10; for i=1:popsize chrom=oldpop(i,:); c=decimal(chrom); varible(1,i)=a+c*(b-a)/(2.^lchrom-1); %对应变量值 fitness(1,i)=varible(1,i)*sin(10*varible(1,i))+2; %目标函数 if(fitness(1,i)>=avgfitness) pmutatio = pm1-(pm1-pm2)*(fitness(1,i)-avgfitness)/(maxfitness-avgfitness); else pmutation = pm1; end end n=round(pmutation*m); % 变异发生的次数 for i=1:n % 执行变异操作循环 k=round(rand*(m-1))+1; %确定变异位置（四舍五入取整） j=ceil(k/lchrom); % 确定个体编号（取整） l=rem(k,lchrom); %确定个体中变位基因的位置（求余）if l==0 temp(j,lchrom)=~temp(j,lchrom); % 取非操作 else temp(j,l)=~temp(j,l); % 取非操作 end end for i=1:popsize newpop(i,:)=temp(i,:); %产生新的个体 oldpop(i,:)=newpop(i,:); end %**************************%交叉操作*************************************** function crossover() global temp popsize pcross lchrom mp n=floor(pcross*(popsize-mp)); %交叉发生的次数（向下取整） if rem(n,2)~=0 % 求余 n=n+1; % 保证为偶数个个体，便于交叉操作 end j=1; m=0; % 对(popsize-mp)个个体将进行随机配对，满足条件者将进行交叉操作（按顺序选择要交叉的对象） for i=1:(popsize-mp) p=rand; % 产生随机数 if p parent(j,:)=temp(i,:); % 选出1个父本 k(1,j)=i; j=j+1; % 记录父本个数 m=m+1; % 记录杂交次数 if(j==3)&(m<=n) % 满足两个父本(j==3)，未超过交叉次数(m<=n) pos=round(rand*(lchrom-1))+1; % 确定随机位数（四舍五入取整）for i=1:pos child1(1,i)=parent(1,i); child2(1,i)=parent(2,i); end for i=(pos+1):lchrom child1(1,i)=parent(2,i); child2(1,i)=parent(1,i); end i=k(1,1); j=k(1,2); temp(i,:)=child1(1,:); temp(j,:)=child2(1,:); j=1; end end end %*********************%最佳个体******************************************** function best() global maxfit bestfit gen maxgen bestgen bestfit=maxfit(1,1); gen=2; while gen<=maxgen if bestfit bestfit=maxfit(1,gen); bestgen=gen; end gen=gen+1; end 0102030405060708090100 024681012Generation F i t n e s s （2）运行结果 A.程序运行结果：最优适应值解为bestfit= 11.4862 最优个体所在代数bestgen= 33 B.程序运行结果图 图2 程序运行结果图 自适应遗传算法 自适应遗传算法 一.主要流程： 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步，进行迭代寻优过程。 第三章 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。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 代中的样本数为： 第!"卷第#期 纺织高校基础科学学报$%&’!"()%’##**+年,月-./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); 遗传算法编码及算子简介 遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块以逐渐逼近最优解。由此可见，必须把群体中的个体转化成按一定基因结构组成的染色体或个体，即编码。编码原则包括两条： 1.有积极积木块编码规则，即所定编码应当易于生成所求问题相关的短距和低阶的积木块。 2.最小字符集编码规则，即所定编码应用最小字符集以使问题得到自然的表示或描述。 规则一是基于模式定理和积木块假设；规则二提供了一种更为实用的编码规则。评估编码策略常采用的规范有： 1.完备性：问题空间中的所有点都能作为GA空间的点表现。 2.健全性：GA空间中的染色体能对应所有问题空间中的候选解。 3.非冗余性：染色体和候选解一一对应。 这些评估规范是独立于问题领域的普遍准则。对某个具体的应用领域而言，应该客观化地比较和评估该问题领域中所用的编码方法。应用遗传算法进行优化，首先将问题描述成串的形式，以模拟染色体。选择何种编码方式对算法的运行有很大的影响。现在，流行的观点认为二进制编码能在相同的范围内表示最多的模式，能充分地体现所谓的隐含并行性。但是，二进制编码方式的精度依赖于染色体的基因位数及设计变量的范围。因而对于高精度、多变量问题，n值需很大，降低遗传算法的收敛速度。另外，二进制编码不直接反映真实的设计空间。其它的编码方式还有：格雷码编码、浮点编码、树结构编码、参数动态编码和多维编码等。 遗传算法主要有选择、交叉和突变算子 选择算子 遗传算法使用选择算子或称复制算子来对种群中的个体进行优胜劣汰操作：选择算子使适应性高的个体在后代中生存的概率较大，而适应度低的个体生存的概率很小甚至被淘汰。遗传算法中的选择操作就是来确定如何从父代群体中按某种方法选取那些个体以传到下一代群体的一种遗传算法。选择操作是建立在群体中个体的适应度评价基础上的。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。在遗传算法中级很重要的作用。选择操作有多种方法，最常用的是轮盘赌法。在具体使用中，应根据问题求解的特点采用合适的方法或者混合使用。下面简单介绍各种选择算法： (1) 比例选择算法 基本思想是：各个个体被选中的概率与其适应度大小成正比，即适应度越高的个体被选中的概率也越大，反之则小。 (2) 最优选择算法 在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地产出新的个体。虽然随着群体的进化过程会产出越来越多的优良个体，但由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应度最好的个体。由于随机操作的原因，这种选择方法的误差比较大，有时甚至连适应度较高的个体也选择不上，由此会降低群体的平均适应度，对算法的运行效率、收敛性都有不利的影响。一般说来，适应度最好的个体要尽可能地保留到下一代群体中。为此可以使用最优保留策略进化模型，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等操 自适应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?【程序清单】? 遗传算法属于进化算法( 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 一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色 变异概率自适应调整的遗传算法算例 一：优化函数：()()*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.doczj.com/doc/6b12450160.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 % 初始化种群和变量 人工智能实验报告 遗传算法实验报告 一、问题描述 对遗传算法的选择操作，设种群规模为4，个体用二进制编码，适应度函数,x的取值区间为[0,30]。 若遗传操作规定如下： （1）选择概率为100%，选择算法为轮盘赌算法； （2）交叉概率为1，交叉算法为单点交叉，交叉顺序按个体在种群中的顺序； （3）变异几率为0 请编写程序，求取函数在区间[0,30]的最大值。 二、方法原理 遗传算法：遗传算法是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算法。与传统的优化算法相比，遗传算法具有如下优点：不是从单个点，而是从多个点构成的群体开始搜索；在搜索最优解过程中，只需要由目标函数值转换得来的适应值信息，而不需要导数等其它辅助信息；搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。遗传操作包括三个算子：选择、交叉和变异。选择用来实施适者生存的原则，即把当前群体中的个体按与适应值成比例的概率复制到新的群体中，构成交配池（当前代与下一代之间的中间群体）。选择算子的作用效果是提高了群体的平均适应值。由于选择算子没有产生新个体，所以群体中最好个体的适应值不会因选择操作而有所改进。交叉算子可以产生新的个体，它首先使从交配池中的个体随机配对，然后将两两配对的个体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因值按某一较小概率进行改变。从产生新个体的能力方面来说，交叉算子是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异算子只是产生新个体的辅助方法，但也必不可少，因为它决定了遗传算法的局部搜索能力。交叉和变异相配合，共同完成对搜索空间的全局和局部搜索。 三、实现过程 （1）编码：使用二进制编码，随机产生一个初始种群。L 表示编码长度，通常由对问题的求解精度决定，编码长度L 越长，可期望的最优解的精度也就越高，过大的L 会增大运算量。 （2）生成初始群体：种群规模表示每一代种群中所含个体数目。随机产生N个初始串结构数据，每个串结构数据成为一个个体，N个个体组成一个初始群体，N表示种群规模的大小。当N取值较小时，可提高遗传算法的运算速度，但却降低种群的多样性，容易引起遗传算法早熟，出现假收敛；而N当取值较大时，又会使得遗传算法效率降低。一般建议的取值范围是20—100。遗传算法以该群体作为初始迭代点； （3）适应度检测：根据实际标准计算个体的适应度，评判个体的优劣，即该个体所代表的可行解的优劣。本例中适应度即为所求的目标函数； （4）选择：从当前群体中选择优良（适应度高的）个体，使它们有机会被选中进入下一次迭代过程，舍弃适应度低的个体。本例中采用轮盘赌的选择方法，即个体被选择的几率与其适应度值大小成正比； （5）交叉：遗传操作，根据设置的交叉概率对交配池中个体进行基因交叉操作，形成新一代的种群，新一代中间个体的信息来自父辈个体，体现了信息交换的原则。交叉概率控制 遗传算法总结 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。 一、遗传算法流程图 算法开始 原问题参数集 染色体编码，产生初始种群 计算种群中个体的适应值 终止条件判断 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）自适应遗传算法讲解学习
第三章-遗传算法的理论基础
基于自适应交叉、变异遗传算法的PID整定
基于遗传算法的OFDM自适应资源分配算法MATLAB源码
遗传算法编码及算子简介
自适应Simpson积分算法MATLAB及C实现代码.docx
matlab自适应遗传算法
遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )
遗传算法的优缺点
遗传算法的流程图
变异概率自适应调整的遗传算法GA程序
自适应小生境遗传算法的性能分析
多方式进化遗传算法Matlab源代码
遗传算法实验报告(仅供参照)
遗传算法总结【精品毕业设计】(完整版)
自适应遗传算法
相关主题
文本预览