Matlab遗传算法工具箱的使用

遗传算法（Genetic Algorithm，GA）是J.Holland教授1975年在其专著中首次发表，又经Goldberg、DeJong等研究总结形成的一种模拟进化算法，其基于生物进化和物种选择理论模拟自然界基因进化的过程与机理来实现最优值搜索。“适者生存”是遗传算法效仿的基本原理，算法通过模仿基因复制、交换、变异等过程使初始解最终逼近最优解。

1、遗传算法的基本概念

由于遗传算法的理念主要源于生物进化理论，所以算法中的许多专业概念与生物进化中的概念很相近，以下做简要说明。
（1）问题的解空间：利用遗传算法时，其最优解和次优解往往存在于同一个集合里，这便是解空间。
（2）种群与个体：遗传算法的解空间源于提供的多个原始解，他们的集合便形成种群，里面的每条原始解便为单个个体。在进行算法迭代时，种群的个体数不会发生变化，而个体会不断“进化”。
（3）染色体编码与基因组：在学习和推导过程里，需要将种群中的每个个体编码，以实现后期的个体选择、交叉和变异，编码形成的二进制串或格雷串便为个体的染色体，上面的数字称为个体基因，每一数字段称为基因组。
（4）适应度函数：适应度函数可以来判断个体与环境（问题）之间的契合性，选取有效适用度函数来判断个体与最优解之间的距离是遗传算法中最为重要的一步。
（5）选择：从种群选取优秀个体的一个过程，利用适应度函数来完成选择步骤。
（6）交叉：即模仿生物繁殖过程，使同源染色体互换位置，以形成两个更适应问题的新个体。
（7）变异：即在进化过程时对染色体上的编码数值采用取反处理以诞生新个体的过程。

2、遗传算法原理

基本遗传算法以一个种群或其中的个体为单位，使用遗传算子、选择算子、交叉算子和变异算子来完成学习和求解过程。这个过程可以表示为：
在这里插入图片描述
式中，C表示编码方法，E为适应度函数，P是初始种群，M为种群大小，φ是选择算子，τ为交叉算子，Ψ为变异算子，T是运算终止条件。

3、遗传算法程序实现

同生物自然进化相同，遗传算法将所有数据编码形成染色体，通过迭代不断选择、交叉和变异运算，从而得到问题的最优解。
在这里插入图片描述
（1）初始种群的生成
遗传算法实现过程中的初始种群诞生有两种形式：一是在对问题的解没有任何先验知识情况下的完全随机产生法；二是在之前经验中选择符合要求的个体组成初始种群，这样可以使初始种群更快达到最优解。
（2）适应度评估
适应度评估是通过适应度函数来实现，是个体是否遗传到下一代的依据。它是影响遗传算法性能最关键的因素之一，其需要结合问题本身进行因变量设计，并预先设定好个体适应度到预期因变量的转换规律。
（3）遗传操作算子
遗传算法包括选择、交叉、变异三种，其各自模仿生物基因的繁殖、交叉和突变过程，使算法产生较强的检索技能。
1）选择算子
选择即从当前群体中选择满足适应度的个体，使其直接或交叉后遗传至下一代种群里。选择完个体后，算法将随机决定该个体与谁进行交配。当其被选中概率较大时，其交配次数就会增加，反之将被舍弃。
2）交叉算子
即用两个父代个体产生新个体的过程。通过交叉不仅可以保留优秀基因，还可以产生包含更复杂基因的新个体，从而提高检索能力。因此，交叉算子是遗传算法的核心。
3）变异算子
为了避免出现问题的过早收敛，遗传算法利用基因链模仿基因突变现象，使得个体基因编码出现小规模翻转。变异属于局部搜索，其与另外两种算子一同确保了算法的有效性。

4、遗传算法的特点

遗传算法基于生物进化中“优胜劣汰，适者生存”的相关理论，不同于传统的枚举法、搜索算法等，有着自己独特的特点和优点。
（1）具有自适应、自组织和智能性
遗传算法在确定了初始的参数后便可以在进程中对信息进行自行搜索，以适应度值为筛选依据，对适应性更强的个体进行保留与遗传，并利用基因重组和变异操作获得更优后代。遗传算法这种特性可以自身发现环境特征和规律，有着极强的智能性，克服了传统算法中需要人事先主观描述问题特征的不足。
（2）以编码集为处理对象
遗传算法是直接针对研究的主体对象进行优化迭代，具有更广泛的应用领域。
（3）易于并行性
主要表现在其以种群为单位进行最优解搜寻，可以同时对多个解空间进行搜索和信息交换，这样可以大大加快的优化效率，并大大减少优化费用。
（4）无规则转换性
遗传算法是以概率调整的方式来调整算法的搜索的，虽然这种没有绝对转换规则的搜索看起来是盲目的，但概率的指引实际上已经使所发搜索有了明确方向。
（5）便捷性
遗传算法的原理、进化和计算流程都很规整明确，在实际应用中有着很强的便捷性。
遗传算法的以上这些特点不仅可以更容易的获得全局最优解，还更有利于处理大规模的复杂问题。

5、遗传算法工具箱的安装

遗传算法工具箱是利用MATLAB矩阵函数构建的一套通用工具，用于实现多种遗传算法方法。遗传算法工具箱（Genetic Algorithm Toolbox）是一组例程，主要用m文件编写，实现了遗传算法中最重要的功能。遗传算法工具箱的安装说明可以在MATLAB安装说明中找到。建议将此工具箱的文件存储在Matlab/toolbox主目录下名为genetic的目录中。
该工具箱中还有部分实例，例如：sga.m中实现了求解数值优化问题的单种群二进制编码遗传算法。mpga.m中实现了多目标遗传算法的求解动态控制的问题。

6、算法实例

选取测试函数为：
在这里插入图片描述
其中n表示问题的维数。对于这个例子，我们选择n＝20。

function ObjVal = objfun1(Phen)
ObjVal = sum((Phen .* Phen)')';

NIND = 40;           % 种群数
MAXGEN = 300;        % 最大迭代次数
GGAP = .9;           % 新个体
NVAR = 20;           % 变量数
PRECI = 20;          % 二进制精度
% 生成字段描述符
FieldD = [rep([PRECI],[1, NVAR]); rep([-512;512],[1, NVAR]);...rep([1; 0; 1 ;1], [1, NVAR])];
% 种群初始化
Chrom = crtbp(NIND, NVAR*PRECI);
% 重置
Best = NaN*ones(MAXGEN,1);	% 最优种群
gen = 0;			        % 代数
% 评价初始种群
ObjV = objfun1(bs2rv(Chrom,FieldD));
% 跟踪最佳个体并显示收敛
Best(gen+1) = min(ObjV);
plot(log10(Best),'ro');xlabel('generation'); ylabel('log10(f(x))');
text(0.5,0.95,['Best = ', num2str(Best(gen+1))],'Units','normalized');   
drawnow;        
% 代数循环while gen < MAXGEN,% 为整个群体分配适应值FitnV = ranking(ObjV);% 选择个体进行繁殖SelCh = select('sus', Chrom, FitnV, GGAP);% 重组选定个体（交叉）SelCh = recombin('xovsp',SelCh,0.7);% 对后代进行突变SelCh = mut(SelCh);% 评价后代，调用目标函数ObjVSel = objfun1(bs2rv(SelCh,FieldD));% 将后代重新插入当前种群[Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);% 代数＋1gen = gen+1;% 更新Best(gen+1) = min(ObjV);plot(log10(Best),'ro'); xlabel('generation'); ylabel('log10(f(x))');text(0.5,0.95,['Best = ', num2str(Best(gen+1))],'Units','normalized');drawnow;
end 
% GA结束