【深度学习】遗传算法

决策树和随机森林建立了输入和输出的非线性的映射模型，决策树判断决策的规则树，随机森林建立了组合的学习框架。

而所谓的遗传算法，则是一类借鉴生物界的进化规律设计的算法，用于模拟自然进化搜索最优解。

一、遗传算法

  遗传算法(Genetic Algorithm, GA )是一种进化算法（即群优化算法：在解空间内同时生成多个个体组成群体，寻找最优解问题），其基本原理是仿效生物界中的“物竞天择，适者生存“的演化法则，它最初由美国Michigan大学的J.Holland教授于1967年提出。

  遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。因此，第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉和变异(保证解空间的多样性，避免偏移最优解)，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding)，可以作为问题近似最优解。

二、遗传算法概述

  遗传算法有三个基本操作：选择(Selection)、交叉(Crossover）和变异(Mutation)。

2.1 选择

  选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。根据各个个体的适应度值（适应度值高则被选中的概率高，并非一定能被选中；而适应度值低的也可能会被选中，只是被选中的概率较小罢了），按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大。

2.2 交叉

  通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性（保留了父辈的特征）。将群体中的各个个体随机搭配成对，对每一个个体，以交叉概率交换它们之间的部分染色体。

2.3 变异

  对种群中的每一个个体，以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。同生物界中一样，（与交叉相比）变异发生的概率很低，变异为新个体的产生提供了机会。

三、遗传算法的基本步骤

3.1 编码

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

3.2 初始群体的生成

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

  初始种群数量的选取对后续的计算和优化影响极大，太少则需要迭代次数较多，较大则可能出现相邻数据出现部分重叠，出现重复计算。一般用经验值来设定初始种群数量。

3.3 适应度评估

  适应度表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。所过所需问题对应的目标函数与工具箱深度函数不同，可对其进行一定的预处理。

3.4 选择

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

3.5 交叉

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

3.6 变异

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

3.7 总结

  将各个步骤总结如下图：

四、遗传算法工具箱

  目前主流的遗传算法工具箱有gadst、gatbx、gaot等，下面主要以 gaot为例 进行讲解。先介绍遗传算法工具箱各自的特点：

  （1）MATLAB内嵌遗传算法工具箱: gadst，封装上层级较高，底层的函数方法无法查阅。代码复用性较高。

  （2）Sheffield大学遗传算法工具箱: gatbx

  （3）北卡罗来纳大学遗传算法工具箱: gaot

  工具箱的调用方式是非常相似的。

  北卡罗来纳大学遗传算法工具箱可查看每一个步骤的原理，重点函数解读如下：

  optimtool：matlab自带工具箱函数，具体调用界面如下。因为可调参数都很直观，故不展开讲解。

4.1 initializega

  Initializega：初始化种群，调用命令如下：

pop = initializega(populationSize,variableBounds,evalFN,evalOps,options)

  以下附上各参数含义的解释：

4.2 ga

  Ga：迭代优化的混合函数。

[x,endPop,bPop,traceInfo] = ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)

  其中，适应度函数 如下：

function [sol, fitnessVal] = fitness(sol, options)
x = sol(1);
fitnessVal = x + 10*sin(5*x)+7*cos(4*x); 
end

  主函数 如下，为了方便理解给每一行代码都加上了注释。

%% 实现遗传算法优化的过程。绘制给定函数曲线、执行遗传算法优化并显示结果。同时还绘制了迭代进化曲线，用于观察优化过程中平均适应度和最佳适应度的变化情况。
%% I. 清空环境变量
clear all;% 清除当前工作空间中的所有变量
clc;% 清除命令窗口中的内容
%% II. 绘制函数曲线
x = 0:0.01:9;% 创建一个从0到9，步长为0.01的向量作为自变量x的取值范围
y =  x + 10*sin(5*x)+7*cos(4*x); % 根据给定的函数表达式计算因变量y的值
figure;% 创建一个新的图形窗口
plot(x, y);% 绘制自变量x和因变量y之间的曲线图
xlabel('自变量');% 设置x轴的标签为“自变量”
ylabel('因变量');% 设置y轴的标签为“因变量”
title('y = x + 10*sin(5*x) + 7*cos(4*x)'); % 设置图的标题为给定的函数表达式
%% III. 初始化种群
initPop = initializega(50,[0 9],'fitness'); % 种群大小, 变量边界的矩阵，适应度函数名称
% 初始化种群。采用遗传算法时，需要首先初始化一组个体作为初始种群。该函数接收三个参数，分别为种群大小、变量边界的矩阵，以及适应度函数的名称
%% IV. 遗传算法优化
[x endPop bpop trace] = ga([0 9],'fitness',[],initPop,[1e-6 1 1],'maxGenTerm',25,...                           'normGeomSelect',0.08,'arithXover',2,'nonUnifMutation',[2 25 3]); 
% 使用遗传算法进行优化。该函数接收多个参数，包括变量边界、适应度函数、约束条件等。返回的结果包括最优解x、最后的种群endPop、最佳个体bpop和迭代过程的跟踪记录trace
%% V. 输出最优解并绘制最优点
x;% 输出最优解x
hold on;% 保持图形窗口不关闭，以便进行后续的绘图操作
plot (endPop(:,1),endPop(:,2),'ro'); % 绘制最优点。将最优种群中的坐标显示为红色圆点
%% VI. 绘制迭代进化曲线
figure(2);% 创建第二个图形窗口
plot(trace(:,1),trace(:,3),'b:');% 绘制迭代进化曲线中的平均适应度。用蓝色虚线表示
hold on;% 保持图形窗口不关闭，以便继续绘制其他曲线
plot(trace(:,1),trace(:,2),'r-')；% 绘制迭代进化曲线中的最佳适应度。用红色实线表示
xlabel('Generation'); % 设置x轴的标签为“Generation”
ylabel('Fittness');% 设置y轴的标签为“Fitness”
legend('Mean Fitness', 'Best Fitness');% 设置图例，表示平均适应度和最佳适应度

  其他还有如几何规划排序选择(normGeomSelect)、算术交叉或线性交叉(arithXover)、非均匀变异(nonUnifMutation)等遗传算法操作。这里暂且展开说一说吧。

4.3 normGeomSelect

  normGeomSelect 是一种遗传算法中的选择操作，也称为**标准几何选择**（normalized geometric selection）。在遗传算法中，选择操作用于确定哪些个体能够被选中作为下一代的父代个体。

  标准几何选择通过将个体的适应度值进行归一化，并根据归一化适应度值选择父代个体。具体而言，标准几何选择使用以下公式计算个体在选择过程中的概率：

prob(i) = (1 - p) * p^i

  其中，prob(i)是第 i 个个体被选择的概率，p 是一个介于 0 和 1 之间的常数，表示选择压力（selection pressure）。较小的 p 值会增加选择压力，使适应度较高的个体更有可能被选择。

  在标准几何选择中，选择概率随着个体的排序指数 i 的增加而减小，呈几何级数分布。这意味着适应度更高的个体被选中的概率更大，但较低适应度的个体仍然有一定的机会被选择。

  通过使用标准几何选择，遗传算法能够根据个体的适应度值选择父代个体，并通过遗传操作（如交叉和变异）产生下一代个体。这有助于保留适应度较高的个体，并逐步改进整体种群的适应度水平。

4.4 arithXover

  arithXover 是一种遗传算法中的交叉操作，也称为算术交叉或线性交叉。在遗传算法中，交叉是模拟生物进化过程中的基因交换，通过将两个个体的基因信息进行组合，产生新的个体。

  具体而言，arithXover 采用算术平均的方式进行交叉。对于每对父代个体，它们的相应基因位（或称为变量）会按照一个随机权重进行加权平均，从而生成新的后代个体。这个过程通过以下公式表示：

childGene = w * parent1Gene + (1 - w) * parent2Gene

  其中，parent1Gene和parent2Gene分别表示两个父代个体在特定基因位上的基因值，w是一个随机权重，通常取值范围是0到1。

  通过使用 arithXover 进行交叉操作，可以实现对父代个体的基因信息进行混合和融合，从而产生更多样化的后代个体。这有助于增加遗传算法搜索空间的探索能力，并提高找到全局最优解的概率。

4.5 nonUnifMutation

   nonUnifMutation 是一种遗传算法中的变异操作，也称为非均匀变异。在遗传算法中，变异是模拟生物进化中的基因突变，通过在个体的基因信息上引入随机扰动，以增加搜索空间的探索能力。

  具体而言，nonUnifMutation 是一种非均匀变异方式，它引入了一个**变异率缩减函数，使得 变异率（即发生变异的概率）随着迭代次数的增加而逐渐减小。这是为了在执行初期有更高的探索能力，而在后期有更高的收敛性**。

  通常，nonUnifMutation 的变异率缩减函数采用如下形式：

mutationRate = initialMutationRate * (1 - generation/maxGenerations) ^ beta

  其中，initialMutationRate 是初始变异率，generation 是当前迭代的代数，maxGenerations 是总的迭代代数，beta 是变异率缩减的参数。

  通过使用 nonUnifMutation 进行变异操作，可以在遗传算法优化过程中引入 一定的随机性，从而避免陷入局部最优解，并提高算法的全局搜索能力。同时，通过动态调整变异率，可以在优化的后期更加聚焦于局部搜索和收敛。

五、遗传算法优化BP神经网络初始权值与阈值

  在应用到具体实战时，遗传算法可以用于优化神经网络的初始权值和阈值，这里给出一种基本的遗传算法优化初始全职和阈值的方法：

（1）定义个体编码

  首先需要定义个体的编码方式。可以 将每个个体表示为一个包含所有权值和阈值的向量 。例如，如果神经网络有 n 个权值和 m 个阈值，则一个个体可以表示为一个长度为 n+m 的向量。

（2）初始化种群

  使用随机方式生成初始种群，种群中的每个个体都包含初始的权值和阈值。

（3）适应度函数

  定义适应度函数来评估个体的性能。对于神经网络问题，可以 选择训练误差作为适应度函数。例如，可以使用平方误差或交叉熵等来衡量个体在训练集上的性能。

（4） 选择操作

  使用选择操作来确定哪些个体能够被选中作为下一代的父代个体。可以使用标准几何选择（normalized geometric selection）或其他选择算法来进行选择。

（5）遗传操作

  应用遗传操作，包括交叉和变异，来产生下一代个体。交叉操作可以通过交换个体之间的权值和阈值来产生新的个体。变异操作可以引入随机扰动来增加种群的多样性。

（6）重复迭代

  重复进行选择和遗传操作，直到达到停止条件（例如达到最大迭代次数或获得满意的适应度水平）为止。

（7）最优个体选择

  最终，选择具有最高适应度的个体作为优化后的初始权值和阈值。

通过使用遗传算法来优化初始权值和阈值，可以提高神经网络的训练效果和泛化能力。遗传算法的全局搜索和优化能力可以帮助找到较好的初始权值和阈值组合，提高神经网络的性能。同时，遗传算法也可以用于解决权值和阈值调整中的陷入局部最优问题。

  可以总结如下图所示：

六、后记

  本篇主要介绍了深度学习优化算法之一的遗传算法，接下来会陆续蚁群算法、粒子群算法和模拟退火算法(T▽T)。上次发了一个投票征求更新的顺序，可能大家都忙于评论没有在意吧，也没有几个人投票(╥_╥)…

  另：最近C站的热榜热度算法好像经过了一定的修改，我评论被禁言的这两天(8.10-8.12)一直在研究其机制(虽然也没有研究出具体的权重值 (＞﹏＜))。感兴趣的朋友可以在评论区留言或是找我私信。

  最后，感谢所有完整看完本文的朋友们，谢谢你们！