Genetic Algorithm

2021-08-24 数学建模算法, 遗传算法 Comments

遗传算法是借鉴生物界的进化规律(适者生存,优胜劣汰)的遗传机制，演化而来的随机全局搜索和优化算法。它是由美国教授于1975年首先提出的，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的区间限定，具有内在的隐并行性和更好的全局寻优能力，采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应的调整搜索方向，不需要确定的规则，遗传算法这些性质已被人们广泛的应用于组合优化机器学习信号处理，自适应控制和人工生命的领域，他是现代有关智能计算中的关键技术。

1 遗传算法的介绍

1.1 遗传算法的优点与不足：

优点
- 不是从单个点，而是从多个点构成的，而是从多个点构成的群体开始搜索。
- 在搜索最优解过程中，只需要由目标函数转化过来的适应值信息，而不需要导数等其他值辅助信息。
- 搜索过程不宜陷入局部最优点。
不足：
- 编码不规范及编码存在表示的不准确性。
- 单一的遗传算法不能全面的将优化问题得约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。
- 遗传算法的效率通常比其他传统的算法效率低。
- 遗传算法容易出现过早收敛得情况。
- 遗传算法对算法得精度、可信度、计算复杂性等方面、还没有有效的定量分析方法。

1.2 遗传算法基本步骤如下：

1、在一定编码条件下，随机产生初始种群。
2、用相应解码方法，将编码后的个体转化为问题空间的决策变量，并求得个体的适应值。
3、按照个体适应值大小，从种群中选出适应值较大的个体构成交配池。
4、用交叉和变异两个遗传算子对交配池中的个体进行操作，并形成新一代种群。
5、反复执行步骤2-5，直至满足收敛判据为止。

1.3 遗传算法的运行决定

编码串长度、种群大小、交叉和变异概率

编码串长度：由由优化问题所求的求解精度所决定。
种群大小：种群大小表示种群所含的个体数量；
- 种群较小时，可提高遗传算法的运行速度，但降低群体多样性，可能找不到最优解。
- 种群较大时，又会增加计算量，使遗传算法的运行效率降低。
- 一般取种群数目为20-100。
交叉和变异概率：
- 交叉概率控制着交叉操作的频率，由于交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常区较大值，但取值过大可能会破坏群体优良模式。一般取0.4-0.99.
- 变异概率也是影响新个体产生的一种因素，变异概率小，产生新个体少；变异概率大，又会使遗传算法变成随机搜索。一般变异概率取0.0001-0.1
遗传算法通常收敛判据；规定遗传代数，连续几次得到最优个体的适应值没有变化或变化很小。

1.4 遗传算法得主要应用领域

2 遗传算法的基本原理

遗传算法是一种基于自然选择和一种遗传变异等生物进化机制的全局性概率搜索算法，它在形式上也是一种迭代方法.它从选定的初始解出发，通过不断迭代，逐步改进当前解，直至最后搜索到最优解或满意解。在进化计算中，迭代计算过程采用了模拟生物体的进化机制，从一组解出发，采用类似于自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成有更好性能指标的，下一代解的群体。
Ga有较强的全局优化能力，是一种自适应的智能的搜索技术，其主要应用领域是复杂的非线性优化问题，选择、交叉和变异是遗传算法的三个主要操作者。

2.1 编码

解空间向Ga空间映射称之为编码，它是连接问题与算法的桥梁。本问题中设计变量均为连续变量，为克服二进制编码在进行连续函数离散时产生的映射误差和方便处理各约束条件，采用浮点数编码方法，染色体长度与设计变量维数相同。

设计变量为：

$X=[x_1,x_2,...,x_n]$

染色体为：

$V=[v_{k1},v_{k2},...,v_{kn}] \quad k=(1,2,...,m)$

2.2 适应度评价函数

度量个体适应度的函数称之为适应度函数。实际工程3优化问题一般都有一定的约束条件，惩罚技术时求解约束优化问题。在遗传算法中，惩罚技术用来在每代的种群中保持部分不可行解，使用遗传算法搜索可以从可行域和不可行域两边来达到最优解。

对于非线性数学规划问题：

$min \quad f(x)\\ s.t.\quad g_i(X)\ge0 \quad (i=1,2,...,m)$

本题中按照外点发构造惩罚函数：

$\phi(X,r^{k})=f(x)+r^{k}{\sum_{\mu=1}^m min[g_\mu (X),0]^2}$

式子中。$r^k$为惩罚因子，是一个单调递增正值序列，$r^{k+1}=er^k$，许多计算经验表明，若区$r^0=1$，和$e=5\sim 10$，可以取到满意的结果。

2.3 选择算子

选择操作建立对个体的适应度进行评价的基础上，选择操作的目的是把优化的个体直接遗传到下一代，或通过配对交叉产生新的个体再遗传到下一代。比例选择是最常用的选择算子，它是一种回放式随机采样方式。设群体规模为$m$，个体$i$，的适应度为$F$，则个体$i$，被选中的概率$p_i$为：

$P_{is}=F_i/\sum_{i=1}^m F_i$

适应度函数数值越高的染色体被选中的概率越大。

2.4 交叉算子

首先定义交叉操作的概率 $P_c$ ，一般建议取值范围为0.4-0.99。然后按照概率 $P_c$ ，把两个父代个体的部分结构加以交换重组而生成新的个体。浮点数编码方法表达的个体在进行交叉时一般是进行算数交叉。假设在两个个体 $X_A^t$，$X_B^t$，之间进行算数交叉，则交叉运算后所产生的两个新个体是：

$\begin{cases} X_A^{t+1}=aX_B^t+(1-a)X_A^t \\ X_B^{t+1}=aX_A^t+(1-a)X_B^t \end{cases}$

式子中，$a$为交叉参数，$a\in(0,1)$ 。它可以是一个常数，此时称之为均匀算数交叉；也可以是一个由此进化代数所决定的变量，此时称非均匀算数交叉。

2.5 变异算子

变异算子是实数编码编遗传算法中起到重大作用。在实数编码时，变异算子不在像二进制编码时仅仅是简单的恢复群体中多样性的损失，它她已经成为一个主要的搜索算子。定义参数 $P_m$ ，作为变异操作的概率，建议取值范围为0.01-0.1。采用非均匀变异：设个体 $X=x_1x_2···x_k···x_l$，其中变异点的新基因为：

$X^{'}_k= \begin{cases} x_k+(U^k_{max}-x_k)(1-r^{b(1-G/T)}) \quad Random(0,1)=1 \\ x_k-(x_k-U^k_{min})(1-r^{b(1-G/T)}) \quad Random(0,1)=0 \end{cases}$

式中，$Random(0,1)$ 表示以均等的概率从 $0,1$ 中任取其一；$r$为$[0,1]$范围内符合均匀分布的一个随机数；$G$ 为当前代数；$T$为终止代数；$b$为调整变异步长的参数，随进化代数 $G$ 而动态变化。

2.6 终止代数

经过选择、交叉和变异操作就能得到一个新的种群，上述步骤经过给定的循环次数后，遗传算法终止，并将当前种群中最佳的个体作为所求问题的最优解输出。对于终止代数，建议取值范围为100-500。

遗传算法工具箱

3.1 ga.m函数

ga.m函数是Matlab遗传算法工具箱和外部接口，在实际优化过程中，编写好目标函数，设定参数，调用ga.m便可实现优化。

3.2 算子函数

算子函数包含交叉算子和变异算子，算子函数提供了遗传算法搜索机制，通过算子函数，在原来基础上产生新的种群。

交叉算子：function[child1,child2]=crossover(parent1,parent2,bounds,params).
变异算子：function[child]=mutation(parent,bounds,params)。

二者不同的是，交叉算子由两个父代产生两个新的子代，而变异算子则是由一个父代产生一个新的子代。

3.3 选择函数

选择函数：function[newPop]=slectFuntion(oldPop,options),决定哪些个体进入下一代。

newPop是被选中的新种群；
oldPop是当前种群；
options是其他可选参数向量； * roulette.m * normGeomSelsct.m * tourn.m

3.4 初始化函数和终止函数

遗传算法工具箱给出了 innitializega.m 和 initializeoga.m 两个种群初始优化函数和 maxGenTerm.m 、optMaxGenTerm.m 两个终止函数。

遗传算法工具箱已经在多维变量优化、非线性规划、参数优化和动态系统最优控等一系列领域有了很好的应用。

4 遗传算法在Matlab中实现

4.1 编码

遗传算法不对优化问题的实际决策变量进行操作，所以应用遗传算法首要问题是通过编码来将决策变量表示成串结构数据。采用最常用的二进制编码方案，即通过二进制数构成的符号串来表示一个个体，用下面的 encoding 函数来实现编码并产生初始种群：

function[bin_gen,bits]=encoding(min_var,max_var,scale_var,popsize)
  bits=ceil(log2((max_var-min_var)./scale_var));
  bin_gen=randint(popsize,sum(bits));
end

在上面代码中，首先根据决策变量的下界(min_var)、上界(max_var)及其搜索精度(scale_var)来确定表示各决策变量的二进制串的长度bits，然后随机产生一个种群大小为 popsize 的初始种群 bin_gen 。编码后的实际搜索精度为 scale_dec (max_var-min_var)/(2^bits-1) ，该精度会在解码时用到。

4.2 解码

编码后的个体构成的种群 bin_gen 必须经过解码以转换成原问题空间的决策变量构成的种群 var_gen ，才能计算相应的适应值。用下面代码实现。

function[var_gen,fitness] = decoding (funname,bin_gen,bits,min_var,max_var)
    num_var=lenth(bits);
    popsize=size(bin_gen,1);
    scale_dec=(max_var-min_var)./(2.^bits-1);
    bits=[o bits];
    for i=1:num_var
      bin_var(i)=bin-gen(:,bits(i):bits(i+1));
      var(i)=sum(ones(popsize,1)*2.^(size(bin_var(i),2)-1:-1:0).*bin_var(i),2).*scale_dec(i)+min_var(i)
    end
    var_gen=[var(1,:)];
    for i=1:popsize
      fitness(i)=eval(funname,'(var_gen(I,:))');
    end

解码函数的关键在于先由二进制数求得对应的十进制数 $D$ ，并根据下式得出实际决策变量值 $X$ ：

1	X=D*scale_dec+min_var

4.3 选择

选择过程是利用解码后求得的各个适应值的大小，淘汰一些较差的个体而选出一些比较优良的个体，以进行下一步交叉变异操作。选择算子的程序如下：

funcion[evo_gen,best_indiv,max_fitness] = selection(old_gen,fitness)
popsize = length(fitness);
[max_fitness,index1] = max(fitness);
[min_fitness,index2] = min(fitness);
best_indiv = old_gen(index1,:);
index = [1;popsize];
index(index1)= 0 ;
index(index2)= 0 ;
index=nonzeros(index);
evo.gen = old-gen(index,:);
evo_fitness = fitness(index,:);
evo_popsize = popsize - 2;
ps=evo_fitness/sum(evo_fitness);
pscum = cumsum(ps);
r = rand(1,evo_popsize);
selscted = sum(pscum*ones(1,evo_popsize)<ones(evo_popsize,1)*r)+1;
evo_gen = evo_gen(selscted,:);

在该算子中，采用最优保存策略和比例保存法相结合的思路，即首先找出当前群体中适应值最高和最低的个体，将最佳个体 best_indiv 保留并用其替换最差个体，为保证当前最佳个体不被交叉、变异操作所破坏，允许其不参与交叉和变异直接进入下一代，然后将剩下的个体 evo_gen </font > 按照比例法进行操作。所谓比例选择法，也叫轮盘赌算法，是指个体被选中的概率和该个体的适应值大小成正比。将两种方法结合的目的是：在遗传操作中，不仅能不断提高群体的平均适应值，而且能保证最佳适应值不减小。

4.4 交叉

下面采用单点交叉的方法来实现交叉算子，即按选择概率 pc 在两两配对的个体编码串 cpairs 中随机设置一个交叉点 cpoints ，然后在该点互相交换两个配对个体的部分基因，从而形成两个新的个体，交叉算子程序如下：

function new_gen = crossover (old_gen,pc)
  [nouse,mating] = sort(rand(size(old_gen,1),1));
  mat_gen = old_gen(mating,:);
  pairs = size(mat_gen,1)/2;
  bits = size(mat_gen,2);
  cpairs = rand(pairs,1)<pc;
  cpoints = randint(pairs,1,[1,bits]);
  cpoints = cpairs.*cpoints;
  for i=1:pairs
    new_gen([2*i-1 2*i],:) = [mat_gen([2*i-1 2*i],1:cpoints(i))mat_gen([2*i 2*i-1],cpoints(i)+1:bits)];
  end

4.5 变异

对于二进制的基因串而言，变异操作就是按照变异的概率 pm 随机选择变异点 mpoints ，在变异点将其取反即可。变异算子的实现过程如下；

funtion new_gen = mutation(old_gen,pm)
  mpoints = find(rand(size(old_gen))<pm);
  new_gen = old_gen;
  new_gen(mpoints) = 1-old_gen*(mppints);

5 简单一元函数优化实例

用遗传算法计算下面函数的最大值：

$f(x)=x sin(10\pi x)+2.0 \qquad x\in [-1,2]$

选择二进制编码，种群个体数量为 $40$ ，每个种群长度为 $20$ ，使用代沟为 $0.9$ ，最大遗传代数为 $25$ 。

代码：

clear;clc
figure(1)
fplot('variable.*sin(10*pi*variable)+2.0',[-1,2])
nind=40;
maxgen=25;
preci=20;
GGAP=0.9;
trace=zeros(2,maxgen);
fieldD=[20;-1;2;1;0;1;1];
chrom=crtbp(nind,preci);
gen=0;
variable=bs2rv(chrom,fieldD);
objv=variable.*sin(10*pi*variable)+2.0;
while gen<maxgen
    FitnV=ranking(-objv);
    selch=select('sus',chrom,FitnV,GGAP);
    selch=recombin('xovsp',selch,0.7);
    selch=mut(selch);7
    variable=bs2rv(selch,fieldD);
    objvsel=variable.*sin(10*pi*variable)+2.0;
    [chrom,objv]=reins(chrom,selch,1,1,objv,objvsel);
    gen=gen+1;
    [Y,I]=max(objv),hold on;
    plot(variable(I),Y,'bo');
    trace(1,gen)=max(objv);
    trace(2,gen)=sum(objv)/length(objv);
end
variable=bs2rv(chrom,fieldD);
hold on;grid;
plot(variable',objv','b*');
figure(2)
plot(trace(1,:)');
hold on;
plot(trace(2,:)','-');grid;
legend('解的变化','种群均值变化')
disp(['输出最大值为',num2str(Y)])

下图展示的是经过多次遗传，得出的最优良子代汇聚结果：

下图是每代得到的结果：

本文链接： http://tuoxiao.github.io/2021/08/24/Mathematical_modeling/11GA/

TuTo

天地与我并生，万物与我为一。