智能优化算法--简单遗传算法（SGA）

--以下言论为个人见解，也有参考前人经验之处--

--若有不当之处，期待与您交流--

一、遗传算法从智能角度理解

该算法主要源于人类或生物智能的启发，并被设计为一类高效优化方法

遗传算法遵循生物'适者生存'原则（源自达尔文的《进化论》），归类于进化的计算方法之一。

因此，我们可以举一个人类进化的例子：

在很远的年代里，在某个地方居住着一群居民。我们通常将这组群体称作"原始群体"。每个成员则被称为"个体"。一个人的基因组则包含23对染色体。

因为自然环境的影响而被淘汰的个体无法存活下去；因而能够更好地适应生存的个体得以存活下来。这即是下方所提到的'复制'过程。

为了繁殖的需求，不同物种或不同品种的生物之间交配，在此过程中会生成新的生命体。这也就是我们常说的‘杂交’。

改写说明

但即使变异出了差的基因，最终还是会回到“复制”，即：更适应生存的被保留。

人类进化论中指出, 经过不断复制重组与变异发展出一代又一代后代, 这正是达尔文在《进化论》中所阐述的适者生存原则以及物竞天择规律的表现

因此, 优化算法通过受到生物进化的启发而形成了遗传算法的概念.

--非生物学专业理解，如有不当之处，还望包涵--

二、遗传算法的计算实现过程

遗传算法的流程图如下所示：

遗传算法的手算过程演示：

①种群初始化（个体编码组合）

假设一个种群有6个个体，他们的基因组编码如下表所示。

②计算个体适应度

在计算之前, 你需要明确什么样的标准才算适应. 其实就是关联于你所求解的问题, 结果越接近越好.

以求解为例，那么函数的适应度值就是

的值，适应度越大越好。

|个体编号|基因组|实值|适应度值(

)|
|---|---|---|---|
|①|0 0 0 1 0|2|4|
|②|0 0 1 1 0|6|36|
|③|0 1 0 1 0|10|100|
|④|1 0 1 1 0|24|576|
|⑤|1 1 0 1 0|26|676|
|⑥|1 1 1 1 0|30|900|

其中，实值指的是前面的基因组对应的二进制编码化成十进制编码的值。

③判断是否满足优化条件

假设反复执行1000次后观察到种群适应度值未见显著提升，并最终低于预设的收敛标准，则判定为优化完成状态。若未能满足上述条件，则执行遗传操作以探索新的解空间

④遗传过程--复制

复制操作通过轮盘赌的方式得以实现。值得注意的是，在本方案中所采用的这种轮盘赌机制类似于赌博中的抽签方式，在一些其他优化算法中也有所应用。

轮盘赌：

不需多言，在群体进化算法中第一步则是计算每个个体的适应度在其群体中的占比情况。需要注意的是，在这种情况下总和必须等于1。

|个体编号|基因组|实值|适应度值(

)|适应度占比|
|---|---|---|---|---|
|①|0 0 0 1 0|2|4|0.002|
|②|0 0 1 1 0|6|36|0.016|
|③|0 1 0 1 0|10|100|0.044|
|④|1 0 1 1 0|24|576|0.25|
|⑤|1 1 0 1 0|26|676|0.295|
|⑥|1 1 1 1 0|30|900|0.393|

其中，适应度占比大小即为每个个体在轮盘上所占比例大小。如下图所示：

左图为各个体在其总体适应度中所占比例的饼图展示；右图为基于此比例构建的一个圆形概率模型。采用轮盘赌方法时，在每次选择中需要按照个体编号依次调节圆盘。每次转动时利用随机数生成器产生一个随机数值；若该随机数值高于相应个体当前适应度值，则执行复制操作；将此位置对应的个体作为被选中的对象替换掉当前个体。

采取此策略能够提高适应度较高的个体在其群体中出现的机会率，并从而提高了找到问题最优解的可能性。

复制操作：

假设通过随机数发生器，随机生成6个随机数[0.103,0.224,0.391,0.107,0.581,0.687]分别对应个体①到⑥的复制概率。

则复制过程为：

过程描述：

在上图右图轮盘中进行一次转动后，在数值为-684的位置停下。其中，在上图右图中进行了一次转动后，在数值-684的位置停下。其适应度累比值为-684小于当前计算值-795吗？或者是不是有其他情况？另外，在当前计算过程中发现了一个问题：当转到数值-684的位置时，并没有找到对应的原始数据记录？这可能意味着需要重新审视计算方法或者检查数据完整性问题？如果是这样的话，则可以用编号为\alpha=795,\beta=795,\gamma=795,\delta=795,\epsilon=795,\zeta=795,\eta=795,\theta=795,\iota=795,\kappa=795,\lambda=795,\mu=795,\nu=795,\xi=795,\pi=\pi_{}^{\text{max}}(t)的情况进行处理？

第二次转动轮盘的结果落到了轮盘的位置标记为0.224。其适应度累积比率为0.018低于该位置。即该位置对应的个体编号是④。将其替换成编号为④的个体，并完成一次复制操作。

第3次转动轮盘的结果落到了轮盘区域的0.391位置；此时观察到目标个体③的累积适应度比为0.062低于当前轮次的关键值0.391；由此可知，在该关键值对应的候选体中存在个体⑤，则以该候选体中的个体⑤替代目标体③完成一次复制操作。

第四次转动赌轮盘落到了赌轮盘数值为 0.107 的位置上；与此同时，在原始个体④中计算得到其累积比例为 0.312 高于此次结果 0.107 ；基于此判断条件，默认情况下不会进行复制操作

第五次转动轮盘落到了轮盘的位置为0.581处；同时计算得知该个体⑤的适应度累加比值达到0.607显著高于当前轮盘位置的0.581；因此决定对该个体进行复制操作。

第六次转动轮盘落到了位于轮盘的0.687位置处；而原个体⑥的适应度总和等于1大于0.687，则不再复制该个体。

④遗传过程--交叉

即为将种群中的个体两两配对进行杂交操作。具体而言，在本算法中首先需设定一个交叉阈值（若该个体的交叉概率低于或等于预先设定的阈值，则会执行杂交操作）。在此过程中并采用两个独立的随机数生成器：其中一个生成器用于产生该个体对应的总交叉概率（即所有可能杂交位点的概率之和），另一个则用于决定每个体的具体杂交位置是否被选中进行交换操作（即通过比较该个体与预设阈值的关系来确定）。例如，在具有五个二进制编码构成的单个体中存在五个可能的杂交位点（如图所示）。

确定交叉位后；对交叉位后的编码进行配对交换。假设随机数发生器已确定交叉位置为4，则上述操作过程如图所示。

交叉操作：

在完成复制操作后实施交配运算（亦即基于新种群中的基因型组合展开交配）。设定交配概率阈值为0.8（仅当该值低于或等于给定临界值时才实施交配运算）。假设采用以下流程：首先利用给定的随机数发生器生成三个数值作为各对体之间的杂交概率参数；其次再生成三个数值作为各对体之间的杂交位置参数；最后将这些参数分配给相应的基因对位置。

则按编号两两交叉的过程为：

过程描述：

1. 个体①的交叉概率为0.87超过阈值0.8，个体①②不进行交叉；

个体³的杂交几率设定为0.31，在预设阈值0.8以内时会发生杂交作用。在此杂交过程中，
个体³与个体⁴之间会进行杂交操作，并将双方第5位以及后续所有基因片段进行交换。
这种交换操作需要同时互换双方第5位以及之后的所有基因片段（即最后一位基因），从而完成一次完整的杂交操作（由于它们具有相同的最后一个基因片段）。

3. 在阈值0.8范围内, 个体⑤的交配概率设定为0.62, 当个体⑤与个体⑥发生交配时, 交配位设置为3, 则会同时交换个体③和④从第3个编码开始的所有后续编码, 从而完成一次完整的交配操作。

④遗传过程--变异

该过程模拟基因突变的现象，并且由于其发生概率与交叉操作不同，在实际应用中两者的效果存在显著差异。为了执行变异操作，在给定的条件下（即当个体的适应度满足一定标准时），系统会自动触发相应的遗传算法步骤；通过两个独立的随机数生成器分别计算出相应的参数值：一个是用于确定变异发生的概率参数；另一个则用于确定具体的染色体位置变化点坐标参数。例如，在一个由五位二进制编码构成的个体中（即每个个体由五位二进制编码组成），共有五个可能的位置可能发生突变情况；如下图所示：

随后确定了相应的变异位置，并对这些位置上的基因进行了调整（其中，在二进制编码体系中具体表现为对基因值进行取反操作）。基于此假定下当随机数生成器指定第四个变异位时则整个遗传操作过程如图所示

依然利用某种特定的概率模型来确定基因突变的具体操作位置，并且假定在此过程中会基于某种算法或机制（此处指"random number generator"）来完成相关计算步骤

变异操作：

在交叉操作之后实施变异操作。将变异概率阈值设定为α=β（即只有当α\leq β时才会启动重组过程）。假设借助随机数生成器，在此基础之上独立地生成6个均匀分布于区间[α−β]的样本数值[γ₁ γ₂ γ₃ γ₄ γ₅ γ₆]=[ε₁ ε₂ ε₃ ε₄ ε₅ ε₆]=[δ₁ δ₂ δ₃ δ₄ δ₅ δ₆]分别对应个体①至的基因突变可能性，在另一个样本中则直接给出各个体基因突变的位置标记。

则变异的过程为：

过程描述：

1. 个体①的变异概率为0.506超过阈值0.01，个体①不变异；

2. 个体②的变异概率为0.831超过阈值0.01，个体②不变异；

3. 个体③的变异概率为0.261超过阈值0.01，个体③不变异；

4. 个体④在阈值[公式]内发生的变异概率为[数值]；当个体④发生变异时，则将其第[位置]位编码从[数值]变为[数值]；完成一次变异

5. 个体⑤的变异概率为0.089超过阈值0.01，个体⑤不变异；

6. 个体⑥的变异概率为0.011超过阈值0.01，个体⑥不变异。

⑤新种群产生

通过复制、交叉和变异操作，最终得到的新种群编号和编码为：

接着，在步骤②中评估每个体的适应度水平，并持续进行直至达到设定的优化标准或完成预设的最大迭代次数。无需进一步详述上述过程

三、遗传算法的MatLab实现

 function SGA_opt

    
  
    
 %% 参数设置
    
 NP=50; % 种群规模
    
 Max_N=10000; % 最大迭代次数
    
 Pc=ones(1,NP)*0.80; % 交叉概率
    
 Pm=ones(1,NP)*0.01; % 变异概率
    
 flagc=[0,Max_N];  % 收敛标志
    
  
    
 D=30; %个体维度=基因组大小
    
 MinX=0;MaxX=31; %基因取值范围
    
  
    
 %收敛阈值及相关参数
    
 tolerance = 1e-3;  % 改进阈值
    
 stall_generations = 1000;  % 连续未改进代数
    
 stall_count = 0;  % 初始化未改进代数计数器
    
 bestF_prev = -inf;  % 初始化或设置为一个比当前最优更差的值
    
  
    
 %% 初始化种群
    
 X=MinX+(MaxX-MinX)*rand(NP,D);
    
 %计算适应度值
    
 F=fun(X)
    
 %找到适应度值最大的个体[适应度值，个体编号]
    
 [bestF,bestId]=max(F);
    
 %获取最优个体的基因组
    
 bestX=X(bestId,:);
    
 % bestF_prev初始化
    
 bestF_prev = bestF - tolerance - 1; 
    
  
    
 %% 主程序：遗传算法
    
 %开始迭代
    
 for gen=1:1:Max_N  % 迭代开始
    
   time(gen)=gen;  % 记录当前代数
    
  
    
   % 基因复制（采用轮盘赌的方式）
    
   tmpF=cumsum(F/sum(F));  %计算适应度值占轮盘的比例（累加）
    
   CX=X;  % 复制当前种群
    
   for i=1:1:NP  % 遍历种群中的每个个体
    
     rnd=rand;  % 生成随机数
    
     for flag=1:1:NP  % 根据累积适应度比例选择个体
    
       if rnd<tmpF(flag)
    
     X(i,:)=CX(flag,:);  % 赋值给新种群
    
     break;  % 找到后退出循环
    
       end
    
     end
    
   end
    
  
    
   % 种群交叉
    
   Pc_rand=rand(1,NP);  % 生成交叉概率随机数
    
   for i=1:2:(NP-1)  % 遍历种群，两两进行交叉
    
     if Pc_rand(i)<Pc(i)
    
       alfa=rand;  % 交叉系数
    
       X([i,i+1],:)=alfa*X([i+1,i],:)+(1-alfa)*X([i,i+1],:);  % 交叉操作（这里使用了矩阵索引，同时更新两个个体）
    
     end
    
   end
    
  
    
   % 种群变异
    
   Pm_rand=rand(NP,D);  % 生成变异概率随机数
    
   for i=1:1:NP
    
     for j=1:1:D
    
       if Pm_rand(i,j)<Pm(i)
    
     X(i,j)=MinX+(MaxX-MinX)*rand;  % 变异操作
    
       end
    
     end
    
   end
    
  
    
   % 保留最优个体
    
   X(NP,:)=bestX;
    
  
    
   % 计算新种群的适应度值
    
   F=fun(X);  % 注意：这里F被重新赋值了，之前的F将不再可用
    
  
    
   % 种群评估
    
   [bestF,bestId]=max(F);  % 更新最优适应度值及对应的个体索引
    
   bestX=X(bestId,:);  % 更新最优个体
    
  
    
   % 检查收敛条件
    
   if bestF - bestF_prev > tolerance
    
       stall_count = 0; % 有显著改进，重置未改进代数计数器
    
   else
    
       stall_count = stall_count + 1; % 没有显著改进，增加未改进代数计数器
    
   end
    
  
    
   bestF_prev = bestF; % 更新为当前最优适应度值，用于下一次判断
    
   
    
   if stall_count >= stall_generations
    
       flagc(1) = 1;
    
       flagc(2) = gen;
    
       break; % 提前结束循环，因为已经收敛
    
   end
    
  
    
   % 记录结果
    
   result(gen)=bestF;  % 记录当前代的最优适应度值
    
  
    
  
    
   % 每1000代输出一次结果
    
   if mod(gen,1000)==0
    
     disp(['代数：',num2str(gen),'--最优适应度：',num2str(bestF)]);  
    
     disp(['收敛了吗：',num2str(flagc)]);  
    
   end
    
 end
    
  
    
 % 绘图
    
 plot(time,result)  % 绘制适应度值随代数变化的曲线
    
 disp(sum(bestX)/D)
    
  
    
 % 子函数：目标函数
    
 function F=fun(X)
    
   for i=1:1:length(X(:,1))
    
     F(i)=sum(X(i,:).^2); 
    
   end

在该段代码中，种群规模即为个体数量50个，在每个个体的基因组中包含有30条染色体。所采用的编码方式为非二进制编码形式，在此框架下旨在解决该问题：求解某个特定的目标函数或优化指标的最大值或最小值等问题。

在

在区间[0, 31]内的最大值被确定之后，在评估是否达到优化目标时需要考察前后最优适应度值的变化趋势。具体而言，在遗传算法中通常设定一个阈值标准，在经过连续1000代的进化后如果没有出现明显的适应度提升，则可以认为算法已经收敛到一个稳定的解附近。此外，在遗传操作过程中，交叉操作采用的方法是将交叉系数应用于相关计算；而变异操作的具体实现则采用了基于随机数生成的方法来替代传统的变异位值设定。

四、可供参考和学习的资料

遗传算法的核心思想具有重要意义，在深入理解其基本原理后, 我们会探索具体的实现细节, 其中包括编码方式, 复制过程, 交叉操作以及变异策略各有不同之处, 可以根据个人思路以及问题的具体情况来灵活设计。 博客详细介绍了多种交叉设计方法值得深入学习。

[进化计算-遗传算法之史上最直观交叉算子（动画演示）_两点交叉-博客

该文章详细阐述了进化计算领域中遗传算法的核心概念与实践应用，并深入探讨了其中最为直观的交配策略——两点交配技术。
文章通过生动有趣的动画演示工具生动呈现了交配操作的具体实施流程。
本篇内容共分为三个主要模块：理论基础介绍、典型实现方法解析以及实际应用案例研究。