遗传算法概述

工具箱下载地址

遗传算法（ genetic algorithm,GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。
在遗传算法中，染色体对应的是数据或数组，通常是由一维的串结构数据来表示，串上各个位置对应基因的取值。基因组成的串就是染色体，或者称为基因型个体（ individuals）。一定数量的个体组成了群体（ population）。群体中个体的数目称为群体大小（ population size），也称为群体规模。而各个个体对环境的适应程度叫做适应度（ fitness）。
遗传算法的基本步骤如下：

1.编码

GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点

2.初始群体的生成

随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始进化。

3.适应度评估

适应度表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同

4.选择

选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择体现了达尔文的适者生存原则

5.交叉

交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。

6.变异

变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值很小。

工具箱添加

用户可以通过网络下载 Sheffield工具箱，然后把工具箱添加到本机的 MATLAB环境中，工具箱的安装步骤如下：
（1）将工具箱文件夹复制到本地计算机中的工具箱目录下，路径为 matlabroot toolbox其中 matlabroot为 MATLAB的安装根目录。
（2）将工具箱所在的文件夹添加到 MATLAB的搜索路径中，有两种方式可以实现，即命令行方式和图形用户界面方式。
找到工具箱所在的文件夹（ gatbx），单击“OK”按钮，则工具箱所在的文件夹出现在
“ MATLAB search path”的最上端。单击“Save”按钮保存搜索路径的设置，然后单击“ Close”
按钮关闭对话框。
（3）查看工具箱是否安装成功。
使用函数ver查看 gatbx工具箱的名字、发行版本、发行字符串及发行日期，如果返回均为空，则说明安装未成功；如果返回了相应的参数，则表明工具箱安装成功，该工具箱就可以使用。

工具箱结构

遗传算法工具箱中的主要函数

遗传算法常用函数

1.创建种群函数— crbp功能：刨建任意离散随机种群。

调用格式：
1【Chrom, Lind, Basev】= crtbp（Nind, Lind）
2 【Chrom, Lind, Base v】=crtbp（Nind, Base）
3 【Chrom, Lind, Basev】= crtbp（Nind, Lind, Base）
格式①创建一个大小为Nind×Lind的随机二进制矩阵，其中，Nind为种群个体数，Lind为个体长度。返回种群编码 Chrom和染色体基因位的基本字符向量 Base v。
格式②创建一个种群个体为Nind，个体的每位编码的进制数由Base决定（Base的列数即为个体长度）。
格式③创建一个大小为Nind×Lind的随机矩阵，个体的各位的进制数由Base决定，这时输入参数Lind可省略（Base的列数即为Lind），即为格式②。
【用法举例】使用函数 crbp创建任意离散随机种群的应用举例
（1）创建一个种群大小为5，个体长度为10的二进制随机种群：

>>【Chrom, Lind, Basev】=crtbp（5,10）

（2）创建一个种群大小为5，个体长度为8，各位的进制数分别为{2,3,4,5,6,7,8,9}：

> 【Chrom, Lind, Base v】=crtbp（5， 8，【23 456789】）

2.适应度计算函数— ranking功能：基于排序的适应度分配。

调用格式：
① FitnV= ranking（0bjv
（2 Fitnv= ranking（Obj, RFun）
3 Fitnv= ranking（Obj, RFun, SUBPOP格式①是按照个体的目标值ObV（列向量）由小到大的顺序对个体进行排序的，并返回个体适应度值FtnV的列向量。
格式②中RFun有三种情况：
（1）若RFun是一个在【1,2】区间内的标量，则采用线性排序，这个标量指定选择的压差
（2）若RFun是一个具有两个参数的向量，则RFun（2）：指定排序方法，0为线性排序，1为非线性排序。
RFun（1）：对线性排序，标量指定的选择压差RFun（1）必须在【1,2】区间；对非线性排序，RFun（1）必须在【1， length（ObV）-2】区间；如果为NAN，则RFun（1）假设为2。
（3）若RFun是长度为 length（ObjV）的向量，则它包含对每一行的适应度值计算格式③中的参数ObjV和RFun与格式①和格式②一致，参数 SUBPOP是一个任选参数，指明在ObjⅤ中子种群的数量。省略 SUBPOP或 SUBPOP为NAN，则 SUBPOP=1.在ObV中的所有子种群大小必须相同。如果 ranking被调用于多子种群，则 ranking独立地对每个子种群执行。

3.选择函数— elect功能：从种群中选择个体（高级函数）

调用格式：
1 Selch= select（SEL F, Chrom, Fitnv）
2 Selch= select（SEL, F, Chrom, FitnV, GGAP）
3 Selch= select（SEL F, Chrom, FitnV, GGAP, SUBPOP）
SELF是一个字符串，包含一个低级选择函数名，如rws或sus Fitnv是列向量，包含种群 Chrom中个体的适应度值。这个适应度值表明了每个个体被选择的预期概率。
GGAP是可选参数，指出了代沟部分种群被复制。如果GGAP省略或为NAN，则GGAP假设为1.0。
SUBPOP是一个可选参数，决定 Chron中子种群的数量。如果 SUBPOP省略或为NAN，则 SUBPOP=1。 Chrom中所有子种群必须有相同的大小

4.交叉算子函数— recombin功能：重组个体（高级函数）。

调用格式：
1 NewChrom= recombin （REC F, Chrom）
2 NewChrom= recombin（REC F, Chrom, Recopt）
3 NewChrom= recombin（REC F, Chrom, RecOpt, SUBPOP）
recombin完成种群 Chrom中个体的重组，在新种群 NewChron中返回重组后的个体。
Chrom和 New Chrom中的一行对应一个个体。
RECF是一个包含低级重组函数名的字符串，例如 ecdis或 XoVsP。
RecEpt是一个指明交叉概率的任选参数，如省略或为NAN，将设为缺省值。
SUBPOP是一个决定 Chrom中子群个数的可选参数，如果省略或为NAN，则 SUBPOP为1。 Chrom中的所有子种群必须有相同的大小。

5.变异算子函数—mut功能：离散变异算子。

调用格式：Newchroa=mt（ older.m,P,BaeV Old Chrom为当前种群，Pm为变异概率（省略时为0.7/Lind）， Base指明染色体个体元素的变异的基本字符（省略时种群为二进制编码）。

6.重插入函数— . reins功能：重插入子代到种群调用格式：

1Chrom= reins（Chrom, Selch）
2 Chrom reins（Chrom, Selch, SUBPOP）
3 Chrom= reins （Chrom, SelCh, SUBPOP, InsOpt, ObjVCh）
【Chrom, Objvch】=reinsChrom, SelCh, SUBPOP, Insopt, ObjVCh, ObjVSel）
reins完成插入子代到当前种群，用子代代替父代并返回结果种群。 Chron为父代种群SelCh为子代，每一行对应一个个体SUBPOP是一个可选参数，指明 Chron和SlCh中子种群的个数。如果省略或者为NAN，则假设为1.在 Chrom和SlCh中每个子种群必须具有相同大小。
InsOpt是一个最多有两个参数的任选向量。
InsOpt（1）是一个标量，指明用子代代替父代的方法。0为均匀选择，子代代替父代使用均匀随机选择。1为基于适应度的选择，子代代替父代中适应度最小的个体。如果省略Ins Opt（1）或 InsOpt（1）为NAN，则假设为0。
Ins Opt（2）是一个在【0,1】区间的标量，表示每个子种群中重插入的子代个体在整个子种群中个体的比率。如果 Ins Opt（2）省略或为NAN，则假设 Ins Opt（2）=1.0。
ObⅤCh是一个可选列向量，包括 Chrom中个体的目标值。对基于适应度的重插入， ObjvCh是必需的。
Obj vSel是一个可选参数，包含 SelCh中个体的目标值。如果子代的数量大于重插入种群中的子代数量，则 Objvsel是必需的。这种情况子代将按它们的适应度大小选择插入.

7.实用函数—bs2rv功能：二进制到十进制的转换。

调用格式：Phen=b2rv（ Chrom, Field）
bs2rv根据译码矩阵 Field将二进制串矩阵 Chrom转换为实值向量，返回十进制的矩阵。

8.实用函数—rep功能：矩阵复制。

调用格式：MatOut=rep（atIn,REN函数rep完成矩阵Matn的复制，REPN指明复制次数，返回复制后的矩阵 MatOut.REPN包含每个方向复制的次数，REPN（1）表示纵向复制次数，REPN（2）表示水平方向复制次数

遣传算法工具箱应用举例

clc
clear all
close all
%% 画出函数图
figure(1);
hold on;
lb=1;ub=2; %函数自变量范围【1,2】
ezplot('sin(10*pi*X)/X',[lb,ub]);   %画出函数曲线
xlabel('自变量/X')
ylabel('函数值/Y')
%% 定义遗传算法参数
NIND=40;        %个体数目
MAXGEN=20;      %最大遗传代数
PRECI=20;       %变量的二进制位数
GGAP=0.95;      %代沟
px=0.7;         %交叉概率
pm=0.01;        %变异概率
trace=zeros(2,MAXGEN);                        %寻优结果的初始值
FieldD=[PRECI;lb;ub;1;0;1;1];                      %区域描述器
Chrom=crtbp(NIND,PRECI);                      %初始种群
%% 优化
gen=0;                                  %代计数器
X=bs2rv(Chrom,FieldD);                 %计算初始种群的十进制转换
ObjV=sin(10*pi*X)./X;        %计算目标函数值
while gen<MAXGENFitnV=ranking(ObjV);                               %分配适应度值SelCh=select('sus',Chrom,FitnV,GGAP);              %选择SelCh=recombin('xovsp',SelCh,px);                  %重组SelCh=mut(SelCh,pm);                               %变异X=bs2rv(SelCh,FieldD);               %子代个体的十进制转换ObjVSel=sin(10*pi*X)./X;             %计算子代的目标函数值[Chrom,ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群X=bs2rv(Chrom,FieldD);gen=gen+1;                                             %代计数器增加%获取每代的最优解及其序号，Y为最优解,I为个体的序号[Y,I]=min(ObjV);trace(1,gen)=X(I);                            %记下每代的最优值trace(2,gen)=Y;                               %记下每代的最优值
end
plot(trace(1,:),trace(2,:),'bo');                            %画出每代的最优点
grid on;
plot(X,ObjV,'b*');   %画出最后一代的种群
hold off
%% 画进化图
figure(2);
plot(1:MAXGEN,trace(2,:));
grid on
xlabel('遗传代数')
ylabel('解的变化')
title('进化过程')
bestY=trace(2,end);
bestX=trace(1,end);
fprintf(['最优解:nX=',num2str(bestX),'nY=',num2str(bestY),'n'])