现代优化算法之遗传算法

偏执的太偏执、 2022-08-18 12:24 251阅读 0赞

之前两篇转载的文章：

[遗传算法入门到掌握（一）][Link 1]、[遗传算法入门到掌握（二）][Link 2]

对遗传算法的数学推导讲解得非常详细，同时我也附带了一份[遗传算法的C语言实现][C]，这篇文章将要运用遗传算法对一个多项式求最小值，要求在(-8,8)间寻找使表达式达到最小的x，误差为0.001。

但是那篇文章仅仅讲解了关于本例的遗传算法的规则，并没有详细的算法过程。

这篇文章简介一下遗传算法的具体算法过程，并且用MATLAB实现遗传算法的代码，该算法将解决[模拟退火][Link 3]一文中的例题。

## **遗传算法简介** ##

遗传算法（Genetic Algorithms，简称 GA）是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色 体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。其实现方法如下：

*  （1） 根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示 可行解域的每一解。
 *  （2） 对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适 应度函数应为非负函数。
 *  （3） 确定进化参数群体规模M 、交叉概率pc 、变异概率pc 、进化终止条件。

为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到最优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进化结束，也可能根据找出近似最优是否满足精度要求来确定。表1 列出了生物遗传概念在遗传算法中的对应关系。

表1 生物遗传概念在遗传算法中的对应关

<table> 
 <thead> 
  <tr> 
   <th align="center">生物遗传概念</th> 
   <th align="center">遗传算法中的作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">适者生存</td> 
   <td align="center">算法停止时，最优目标值的解有最大的可能被留住</td> 
  </tr> 
  <tr> 
   <td align="center">个体</td> 
   <td align="center">解</td> 
  </tr> 
  <tr> 
   <td align="center">染色体</td> 
   <td align="center">解的编码</td> 
  </tr> 
  <tr> 
   <td align="center">基因</td> 
   <td align="center">解中每一分量的特征</td> 
  </tr> 
  <tr> 
   <td align="center">适应性</td> 
   <td align="center">适应度函数值</td> 
  </tr> 
  <tr> 
   <td align="center">种群</td> 
   <td align="center">根据适应度函数值选取的一组解</td> 
  </tr> 
  <tr> 
   <td align="center">交配</td> 
   <td align="center">通过交配原则产生一组新解的过程</td> 
  </tr> 
  <tr> 
   <td align="center">变异</td> 
   <td align="center">编码的某一分量发生变化的过程</td> 
  </tr> 
 </tbody> 
</table>

## **模型及算法** ##

我们用遗传算法研究上次提到的问题。

*  种群大小：M=50
 *  最大代数：G=1000
 *  交叉率： pc=1 ，交叉概率为1 能保证种群的充分进化。
 *  变异率： pm=0.1 ， 一般而言，变异发生的可能性较小。

（1） 编码策略  
采用十进制编码，用随机数列ω1,ω2,…,ω102 作为染色体，其中 0<ωi<1（i=2,3,…,101）， ω1=0，ω102=1 ；每一个随机序列都和种群中的一个个体相对应，例如一个9 城市问题的一个染色体为

\[0.23，0.82，0.45，0.74，0.87，0.11，0.56，0.69，0.78\]

其中编码位置i代表城市i，位置i的随机数表示城市i在巡回中的顺序，我们将这些随 机数按升序排列得到如下巡回：

6→1→3→7→8→4→9→2→5

（2） 初始种群 本文中我们先利用经典的近似算法—改良圈算法求得一个较好的初始种群。即对于初始圈C=π1…πu−1πuπu\+1…πv−1πvπv\+1…π102，2≤u<v≤101，2≤πu<πv≤101，交换u与v之间的顺序，此时的新路径为：

π1…πu−1πvπv\+1…πu\+1πuπv\+1…π102

记Δf=(dπu−1πv\+dπuπv\+1)−(dπu−1πu\+dπvπv\+1)，若Δf<0，则以新的路经修改旧的路  
经，直到不能修改为止。

（3） 目标函数  
目标函数为侦察所有目标的路径长度，适应度函数就取为目标函数。我们要求

minf(π1,π2,…,π102)=∑i=1101dπiπi\+1

（4） 交叉操作  
我 们 的 交 叉 操 作 采 用 单 点 交 叉 。 设 计 如 下 ， 对 于 选 定 的 两 个 父 代 个 体f1=ω1ω2…ω102，f2=ω1ω2…ω102，我们随机地选取第t个基因处为交叉点，则经过交叉运算后得到的子代编码为s1 和s1， s1 的基因由f1的前t个基因和f2 的后102−t个基因构成， s2的基因由f2 的前t个基因和f1的后102−t个基因构成，例如：

f1=\[0,0.14,0.25,0.27,  ∥  0.29,0.54,…,0.19,1\]f2=\[0,0.23,0.44,0.56,  ∥  0.74,0.21,…,0.24,1\]

设交叉点为第四个基因处，则

s1=\[0,0.14,0.25,0.27,  ∥  0.74,0.21,…,0.24,1\]s2=\[0,0.23,0.44,0.56,  ∥  0.29,0.54,…,0.19,1\]

交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。

（5） 变异操作  
变异也是实现群体多样性的一种手段，同时也是全局寻优的保证。具体设计如下，按照给定的变异率，对选定变异的个体，随机地取三个整数，满足1<u<v<w<102，  
把u,v之间（包括u和v）的基因段插到w后面。

（6） 选择  
采用确定性的选择策略，也就是说选择目标函数值最小的M个个体进化到下一代，这样可以保证父代的优良特性被保存下来。

## **MATLAB 程序** ##

clc,clear
    load sj.txt %加载敌方100 个目标的数据
    x=sj(:,1:2:8);x=x(:);
    y=sj(:,2:2:8);y=y(:);
    sj=[x y];
    d1=[70,40];
    sj0=[d1;sj;d1];
    %距离矩阵d
    sj=sj0*pi/180;
    d=zeros(102);
    for i=1:101
    for j=i+1:102
    temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
    d(i,j)=6370*acos(temp);
    end
    end
    d=d+d';L=102;w=50;dai=100;
    %通过改良圈算法选取优良父代A
    for k=1:w
    c=randperm(100);
    c1=[1,c+1,102];
    flag=1;
    while flag>0
    flag=0;
    for m=1:L-3
    for n=m+2:L-1
    if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
    flag=1;
    c1(m+1:n)=c1(n:-1:m+1);
    end
    end
    end
    end
    J(k,c1)=1:102;
    end
    J=J/102;
    J(:,1)=0;J(:,102)=1;
    rand('state',sum(clock));
    %遗传算法实现过程
    A=J;
    for k=1:dai %产生0～1 间随机数列进行编码
    B=A;
    c=randperm(w);
    %交配产生子代B
    for i=1:2:w
    F=2+floor(100*rand(1));
    temp=B(c(i),F:102);
    B(c(i),F:102)=B(c(i+1),F:102);
    B(c(i+1),F:102)=temp;
    end
    -280-
    %变异产生子代C
    by=find(rand(1,w)<0.1);
    if length(by)==0
    by=floor(w*rand(1))+1;
    end
    C=A(by,:);
    L3=length(by);
    for j=1:L3
    bw=2+floor(100*rand(1,3));
    bw=sort(bw);
    C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
    end
    G=[A;B;C];
    TL=size(G,1);
    %在父代和子代中选择优良品种作为新的父代
    [dd,IX]=sort(G,2);temp(1:TL)=0;
    for j=1:TL
    for i=1:101
    temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
    end
    end
    [DZ,IZ]=sort(temp);
    A=G(IZ(1:w),:);
    end
    path=IX(IZ(1),:)
    long=DZ(1)
    toc
    xx=sj0(path,1);yy=sj0(path,2);
    plot(xx,yy,'-o')

计算结果为 40 小时左右。其中的一个巡航路径如图2 所示。

![这里写图片描述][20151220183101598]

[Link 1]: http://blog.csdn.net/u013007900/article/details/43523975
[Link 2]: http://blog.csdn.net/u013007900/article/details/43524005
[C]: http://blog.csdn.net/u013007900/article/details/43524261
[Link 3]: http://blog.csdn.net/u013007900/article/details/50351523
[20151220183101598]: /images/20220731/4f0d2c53d5af4aa98af3b66bac0cc629.png