遗传算法实例

1、遗传算法实例智能控制- 1 - 第一章遗传算法基本原理一、遗传算法基本概念遗传算法（ Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是由美国的J.Holland 教授 1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法是从代表问题可能潜在的解集的一个种群（ population ） 开始的，而一个种群则由经过基因

2、（gene）编码的一定数目的个体(individual) 组成。每个个体实际上是染色体(chromosome) 带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（ fitness ）大小选择（ sel

3、ection）个体，并借助于自然遗传学的遗传算子（ genetic operators）进行组合交叉（crossover）和变异（ mutation ） ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding） ，可以作为问题近似最优解。二、遗传算法运算过程遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估 )施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼进最优解

4、。遗传操作包括以下三个基本遗传算子(genetic operator): 选择 (selection) ；遗传算法- 2 - 交叉 (crossover) ；变异 (mutation) 。这三个遗传算子有如下特点: 个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。1、选择和复制从群体中选择优胜的个体，淘汰劣质个体的操作叫

5、选择。选择算子有时又称为再生算子(reproduction operator) 。选择的目的是把优化的个体(或解 )直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种:适应度比例方法、随机遍历抽样法、局部选择法、局部选择法。其中轮盘赌选择法（roulette wheel selection ）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。显然，概率反映了个体的适应度在整个群体的个体适应度总和中所占的比例.个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择

6、概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个0，1之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。2、交叉在自然界生物进化过程中起核心作用的是生物遗传基因的重组 (加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体

7、串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构遗传算法- 3 - 进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：个体 A：1 0 0 1 1 1 1 1 0 0 1 0 0 0新个体个体 B：0 0 1 1 0 0 0 0 0 1 1 1 1 1新个体3、变异变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。遗传算法导引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到

8、破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。(0，1)二值码串中的基本变异操作是：随机产生一个与基因数长度相同的(0，1)二值掩码，掩码中，值为1 所对应的染色体中基因发生取反变异。如下：掩码C：1 1 0 0 1 0 1 个体A：1 0 0 1 1 1 1 下划线的基因发生变异，变异后为：个体A ：0 1 0 1 0 1 0 遗传算法- 4 - 第二章遗传算法实例分析一、实例要求1sinsin,xyfx yxy22222,0.9exp0.99996exp10205555fx yxyxy. .10,10 x y，精度为 0.0001。寻找最大适应性及

9、相应的位置！种群 N=50；交换的位数统一选为n/2（即个体为数的一半） ，且位置随机；变异位数统一取为 4；Nc=20，28，36，44，交换的个数。Nm=1，5，10，15，变异的个数。二、实例分析与结果如题： 精度为小数点后 4位， 区间长度为 10- （-10） =20， 则应该将闭区间10,10分为4520 102 10等份。因为1751813107222 102262144，所以编码的二进制串长至少需要18 位，这里我们取个体基因数为18n。选择和复制个体时，采用轮盘法。交叉时，采用随机生成掩码，然后根据生成的掩码选择个体进行交叉。变异时，因为变异基因数为4，所以随机生成4 个0-

10、36 之间的数，根据生成的数对相对应的基因进行取反操作，即变异。1、第一个函数：对应于不同的交换个体数和变异个体，运行结果如下：Nc=20，Nm=1，100 代以后，x=-0.0927 ；y=0.0097；f=0.9986过程图如下图所示。遗传算法- 5 - 依次将 Nc=28，36，44和 Nm=5，10，15 代入程序中可得下表。f1 Nc=20 Nc=28 Nc=36 Nc=44 Nm=1 x=-0.0927 x=-0.5356 x=0.0706 x=-0.0801 y=0.0097 y=-0.0241 y=0.3862 y=-0.0386 f=0.9986 f=0.9528 f=0.9

11、745 f=0.9987 Nm=5 x=-0.0921 x=0.2771 x=-0.0584 x=0.2172 y=-0.1014 y=-0.0710 y=0.2696 y=0.1862 f=0.9969 f=0.9864 f=0.9874 f=0.9864 Nm=10 x=-0.3464 x=-0.2714 x=0.1175 x=-0.1390 y=-0.0825 y=-0.2784 y=0.1162 y=-0.0307 f=0.9790 f=0.9751 f=0.9955 f=0.9966 Nm=15 x=-0.2057 x=0.0000 x=0.1186 x=0.1541 y=0.065

12、1 y=0.0638 y=-0.1301 y=0.0725 f=0.9923 f=0.9993 f=0.9948 f=0.9952 010203040506070809010000.51次 数最大值0102030405060708090100-505次 数X0102030405060708090100024次 数y遗传算法- 6 - 2、第一个函数：对应于不同的交换个体数和变异个体，运行结果如下：Nc=20，Nm=1，100 代以后，x=5.2237；y=5.1459；f=0.9960过程图如下图所示。依次将 Nc=28，36，44和 Nm=5，10，15 代入程序中可得下表。f2 Nc=20

13、 Nc=28 Nc=36 Nc=44 Nm=1 x=5.2237 x=5.1347 x=5.0874 x=5.0694 y=5.1459 y=4.9105 y=5.1211 y=5.0323 f=0.9960 f=0.9951 f=0.9985 f=0.9993 Nm=5 x=5.5403 x=5.0136 x=4.6988 x=4.8971 y=4.8910 y=4.9266 y=5.1401 y=5.1253 f=0.9845 f=0.9993 f=0.9941 f=0.9983 Nm=10 x=5.1393 x=5.1988 x=5.3039 x=5.1513 y=4.6793 y=4.

14、9427 y=5.0640 y=4.9478 f=0.9935 f=0.9975 f=0.9948 f=0.9983 Nm=15 x=5.0874 x=4.7671 x=5.2585 x=4.8468 y=4.9231 y=5.2678 y=5.3560 y=4.7348 f=0.9989 f=0.9933 f=0.9900 f=0.9949 010203040506070809010000.51次 数最大值0102030405060708090100-10010次 数X0102030405060708090100-10010次 数y遗传算法- 7 - 附：源程序clear;Nc=44; %

15、交叉数Nm=15; % 变异数N=50; % 种群数量为 50L=18; % 二进制数串长度为18r=randint(N,L*2); % 随机获得数量为50的种群Pc=Nc/N; % 交叉率Pm=Nm/N; % 变异率NNm=4; % 变异基因数M=100; % 迭代 100代% 解码for k=1:1:M G(k)=k;for i=1:1:N U=r(i,:); m=0;n=0;for j=1:1:L m=U(j)*2(j-1)+m; n=U(j+18)*2(j-1)+n;end x(i)=-10+m*20/(218-1); % 将二进制解码为定义域范围内十进制 x_disp(k)=x(i)

16、; y(i)=-10+n*20/(218-1); y_disp(k)=y(i);%Fcn(i)=sin(x(i)*sin(y(i)/(x(i)*y(i); %适应度函数%Fcn(i)=x(i)*x(i); %测试用函数Fcn(i)=0.9*exp(-(x(i)+5)2+(y(i)+5)2)/10)+0.9996*exp(-(x(i)-5)2+(y(i)-5)2)/20); Fcn_disp(k)=Fcn(i);end% 复制 sum_Fcn=0; % 适应度累加和%Qk=zeros(N,1); %适应度概率累加%F=Fcn+1; %因为适应度函数有负数，将适应度相对最低值进行尺度变换for i

17、=1:1:N sum_Fcn=Fcn(i)+sum_Fcn; end%sum_Fcn=sum(Fcn);%for i=1:1:N% Pk(i)=Fcn(i)/sum_Fcn;遗传算法- 8 - % Qk(i)=sum(Pk(1:1:i);%end U2=zeros(N,2*L); % 用于储存复制后的第2代新种群for i=1:1:N p=rand*sum_Fcn; % 获得一个随机数 ad_Fcn=0; j=1;while (pad_Fcn)&(j=60) ad_Fcn=ad_Fcn+Fcn(j); j=j+1;end j=j-1; U2(i,:)=r(j,:);end% 交叉for i=1:2:N % 为防止出现奇数个交叉个体，每次以两个为单位，捆绑交叉 p=rand;if pPc Uy=randint(1,36);% 产生一个 36位的掩码， 0，1出现的概率各为50% 。即变异位数为Lfor j=1:1:36if Uy(j)=1; temp=U2(i+1,j); U2(i+1,j)=U2(i,j); U2(i,j)=temp;endendendend% 变异 i=1;while i=Nm h=randin