多种群遗传算法的函数优化算法（附MATLAB代码）

最近小编终于重新拿起智能优化算法的圣经《MATLAB智能算法30个案例分析（第2版）》，每次读这本书都会有新的收获，今天要与大家分享的智能算法是多种群遗传算法。PS：文中代码来源于本书。

因为后面要介绍的多种群遗传算法的代码中使用到了谢菲尔德遗传算法工具箱中的函数，所以小编一步步演示如何将谢菲尔德遗传算法工具箱（文末百度云链接的压缩包中包含该工具箱）添加到本机的MATLAB环境中。

1.将工具箱文件夹复制到本地计算机中的工具箱目录下，路径为：matlabroot\toolbox，其中matlabroot为MATLAB的安装根目录。

2.将工具箱所在的文件夹添加到MATLAB的搜索路径中：在MATLAB主窗口上选择 主页->设置路径，在弹出的对话框中单击“添加文件夹”按钮，找到工具箱所在的文件夹(gatbx)，单击“选择文件夹”，然后点击下方的“保存”按钮保存搜索路径的设置，然后关闭对话框，具体操作下如图所示

3.在命令行窗口输入：v=ver('gatbx')，如果出现下图字样，则代表安装成功

接下来开始正式介绍多种群遗传算法。

01 | 遗传算法早熟问题

各位小伙伴在用遗传算法求解问题时，一定会遇到算法早熟的问题，其实不只是遗传算法，智能算法都会有这样的缺点，那么遗传算法的未成熟收敛与哪些方面有关呢？

1.选择操作中当群体中存在个别超常个体时（该个体的适应度比其他个体高得多），该个体在选择算子作用下将会多次被选中，下一代群体很快被该个体所控制，从而导致群体停滞不前。

2.交叉和变异操作发生的频度是受交叉概率Pc和变异概率Pm控制的，不同的Pc、Pm的取值可能会导致不同的计算结果。

3.群体规模对遗传算法的优化性能也有较大影响。

4.遗传算法常用的终止判据是，当迭代次数达到认为规定的最大遗传代数时，则终止进化。如迭代次数过少，进化不充分，也会造成未成熟收敛。为克服未成熟收敛，许多学者提出了自适应的交叉和变异。

02 | 多种群遗传算法概述

多种群遗传算法（multiple population GA，MPGA）在标准遗传算法（SGA）的基础上主要引入以下几个概念：

1）突破SGA仅靠单个群体进行遗传进化的框架，引入多个种群同时进化优化搜索；不同的种群赋予不同的参数控制，实现不同的搜索目的。

2）各个种群之间通过移民算子进行联系，实现多种群的协同进化；最优解的获取是多个种群协同进化的综合结果。

3）通过人工选择算子保存各种群每个进化代中的最优个体，并作为算法收敛的依据。

下图中，种群1~N的进化机制都是常规的SGA，采用轮盘赌选择、单点交叉和位点变异。

在MPGA中，每一个单独的SGA一般选择交叉概率Pc在0.7~0.9之间，变异概率Pm在0.001~0.05之间。

接下来要介绍MPGA的核心内容1——移民算子。移民算子究竟是如何将不同的种群联系起来的？其实上面的图片已经显示得比较清晰了，通过移民算子将种群2中最差的个体用种群1中最优的个体进行替换，将种群3中最差的个体用种群2中最优的个体进行替换，……，将种群N中最差的个体用种群N-1中最优的个体进行替换，将种群1中最差的个体用种群N中最优的个体进行替换。其实是一个环环相扣的替换过程。

移民算子代码如下所示：

1%% 移民算子
 2%输入Chrom：           cell类型，每个元胞单元为一个种群的编码（移民前）
 3%输入ObjV：            cell类型，每个元胞为一个种群所有个体的目标值（移民前）
 4%输出Chrom：           cell类型，每个元胞单元为一个种群的编码（移民后）
 5%输出ObjV：            cell类型，每个元胞为一个种群所有个体的目标值（移民后）
 6
 7function [Chrom,ObjV]=immigrant(Chrom,ObjV)
 8MP=length(Chrom);
 9for i=1:MP
10    [MaxO,maxI]=max(ObjV{i});  % 找出第i种群中最优的个体
11    next_i=i+1;                % 目标种群（移民操作中）
12    if next_i>MP;next_i=mod(next_i,MP);end
13    [MinO,minI]=min(ObjV{next_i});          %  找出目标种群中最劣的个体
14    %% 目标种群最劣个体替换为源种群最优个体
15    Chrom{next_i}(minI,:)=Chrom{i}(maxI,:);
16    ObjV{next_i}(minI)=ObjV{i}(maxI);
17end

接下来要介绍MPGA的核心内容2——人工选择算子

人工选择算子就是保存N个种群每个进化代中的最优个体，然后这N个最优个体组成一个新的种群——精华种群。

精华种群不进行选择、交叉、变异等遗传操作，保证进化过程中各种群产生的最优个体不被破坏和丢失。同时，精华种群也是判断算法终止的依据，这里采用最优个体最少保持代数作为终止判据。这种判据充分利用了遗传算法在进化过程中的知识积累，较最大遗传代数判据更为合理。

其实这个最优个体最少保持代数作为终止判据翻译过来就是：如果连续MAXGEN代解没有进化，则算法停止迭代。

人工选择算子代码如下所示：

1%% 人工选择算子
 2%输入Chrom：           cell类型，每个元胞单元为一个种群的编码（移民前）
 3%输入ObjV：            cell类型，每个元胞为一个种群所有个体的目标值（移民前）
 4%输入MaxObjV：         Double类型，每个种群当前最优个体的目标值（选择前）
 5%输入MaxChrom：        Double类型，每个种群当前最优个体的编码（选择前）
 6%输入MaxObjV：         Double类型，每个种群当前最优个体的目标值（选择后）
 7%输入MaxChrom：        Double类型，每个种群当前最优个体的编码（选择后）
 8
 9function [MaxObjV,MaxChrom]=EliteInduvidual(Chrom,ObjV,MaxObjV,MaxChrom)
10
11MP=length(Chrom);  %种群数
12for i=1:MP
13    [MaxO,maxI]=max(ObjV{i});   %找出第i种群中最优个体
14    if MaxO>MaxObjV(i)
15        MaxObjV(i)=MaxO;         %记录各种群的精华个体
16        MaxChrom(i,:)=Chrom{i}(maxI,:);  %记录各种群精华个体的编码
17    end
18end

书中用MPGA求解一个复杂二元函数的最值问题，函数为：

目标函数的代码如下：

1%% 目标函数
2function obj=ObjectFunction(X)
3%% 待优化的目标函数
4% X的每行为一个个体
5col=size(X,1);
6for i=1:col
7    obj(i,1)=21.5+X(i,1)*sin(4*pi*X(i,1))+X(i,2)*sin(20*pi*X(i,2));
8end

03 | MATLAB代码链接（后台回复“多种群遗传算法”提取代码）

gatbx文件夹为谢菲尔德遗传算法工具箱

MPGA与SGA求解上述二元函数的代码在第二个文件夹中

链接：https://pan.baidu.com/s/14rgLAeXx01BO7OI8DXce5A 

提取码：qfrm 

小编总结一下，其实多种群遗传算法就相当于多个标准遗传算法的结合体，只不过需要通过移民算子将这些个标准的遗传算法联系起来；

如果没有移民算子，各种群之间失去了联系，MPGA将等同于用不同控制参数进行多次SGA计算，从而失去了MPGA的特色

然后通过人工选择算子保存各种群每个进化代中的最优个体；

最后以最优个体最少保持代数作为终止判据（PS：这里所说的最优个体指的是全局最优个体）。

最后，小编祝大家明天520快乐！

友情提示

代码的有效期只有7天，如需代码，请微信公众号后台联系小编，或者微博私信小编，微博ID：随心390。小编会第一时间回复您。

微博：随心390

长按识别二维码关注我们