⾃适应遗传算法（AGA）《AdaptiveProbabilitiesofCrossover。。。
本⽂对于普通⾃适应遗传算法的Pm和Pc的公式进⾏了解读，此公式为M.Srinivas 和 L .M. Patnaik在1994年的《Adaptive Probabilities of Crossover》（）论⽂提出。
动机
在GA中有两个特征是必要的：
在出包含最优解的范围之后，收敛到最佳效果的能⼒。（收敛能⼒）
探索解空间的新区域以寻全局最优的能⼒。（寻优能⼒）
经过经验验证，适当的Pc值（0.5～1.0）和较⼩的Pm值（0.001~0.005）在传统遗传算法(SGA)实践中被普遍采⽤。⽽SGA存在着严重的缺点，它的Pc和Pm的值是固定的，不管是优良个体还是劣质个体都经过了相同概率的交叉和变异操作。这会引起两个很严重的问题：
相同的概率，这可以说是不公平，因为对于优良个体，我们应该减⼩交叉变异概率，使之能够尽量保存 ； ⽽对于劣质个体，我们应该增⼤交叉变异概率，使之能够尽可能的改变劣质的状况 。所以，⼀成不变的交叉变异概率影响了算法的效率。
相同的概率总不能很好的满⾜种进化过程中的需要，⽐如在迭代初期，种需要较⾼的交叉和变异概率，已达到快速寻最优解的⽬的，⽽在收敛后期，种需要较⼩的交叉和变异概率，以帮助种在寻完最优解后快速收敛。所以，⼀成不变的交叉变异概率影响了算法的效率。
基于上述SGA存在的种种问题，M.Srinivas 和 L .M. Patnaik在1994年的《Adaptive Probabilities of Crossover》论⽂提出了⾃适应的遗传算法（AGA）
⾃适应设计理念的诞⽣
AGA，旨在通过以不同的⽅式实现搜索和随机性之间的权衡，根据适合度值⾃适应地改变Pc和Pm的值 ，当体倾向于停留在局部最优时（也就是体适应度集中，多样性⽐较差时）Pc和Pm的值 增加，并且当体在解空间中散布时（也就是体适应度分散，多样性⽐较⾼时）减⼩。所以需要⼀个针对Pc和Pm的计算公式，让其符合动态变化。
⼀种检测收敛的⽅法是： 观察种的最⼤适应度值（Fmax）与种的平均适应度值(Favg )的关系，也就是Fmax-Favg的⼤⼩情况。这个值越⼩，即Favg逐渐向Fmax靠拢，表明种逐渐进化，可能解向最优解靠拢。当然，通过上图，我们也可以发现对于收敛到⼀个最佳解的种 ⽐ ⼀个分散在解空间的种的Fmax-Favg 可能会更⼩（如上图中A点⽐B点还要低）。
我们注意上图中，（我们从整个种的进化⾓度来看。）当GA收敛到适应度值为0.5的局部最优值时（全局最优解具有1.0的适应度
值），Fmax-Favg减⼩了。Fmax-Favg作为GA检测收敛的标准，Pc和Pm值会根据Fmax-Favg的值进⾏变化。因为GA收敛到局部最优
时，Pc和Pm的值必须增加，也就说，当Fmax-Favg减⼩的时候，Pc和Pm要增加（与Fmax-Favg的相反），也就说Fmax-Favg的值与Pc和Pm的值成反⽐。
表达式为：
从上述表达式中，我们可以观察到Pc和Pm的值的确是根据种的适应度⽽变化了，即，当种适应度集中时候（Favg向Fmax靠拢，Fmax-Favg变⼩），Pc和Pm变⼤，相反的，变⼩。 但是 还存在两个问题：
Pc和Pm的值并不是依赖于特定个体的适应值，⽽是整个种的平均和种最⼤适应值 。因此优良个体和劣质个体都进⾏了相同⽔平的交叉和变异。 ，所以这对优良个体和劣质个体⽽⾔不公平，毕竟我们的初衷是想要保存优良个体，让交叉和变异⼩⼀点 ； ⽽改变劣质个体，让交叉和变异⼤⼀点。
当⼀个种收敛到全局最优解的时候（甚⾄是局部最优解的时候），Pc和Pm增加，并且可能导致接近最优个体的损坏。种可能永远不会收敛到全局最优解。即使我们能够阻⽌GA陷⼊局部最优解，但是GA的性能（根据收敛所需要的代数）肯定会恶化。
为了克服上述问题，我们需要保存种中优良的个体和改变劣质个体，可以通过以下⽅式实现 （我们从某⼀代种内部各个体的⾓度来看） :
对于⾼适应度个体给予较低的Pc和Pm值，这有利于进⾏保存； 对于第适应度的个体给予⾼的Pc和Pm，这有利于劣质个体的改变。
Pm的值不仅仅取决于Fmax-Favg，还取决于个体的适应值F。 F越接近与Fmax，Pm的值应该越⼩，即 Pm应该直接等于(Fmax-F )，相似的，Pc的值应该也直接等于(Fmax-F ’ ) （F‘ 是两个要交叉个体中适应度较⼤的那个适应度值）。
现在对于Pc和Pm的表达式应该改为：
对最⼤适应度个体⽽⾔，Pc和Pm是0 。 如果⼀个个体的 F‘ = Favg 的话，Pc=k1，如果⼀个个体的 F = Favg 的话，Pm=k2 。对于⼀个适应度⾮常低（即 F <<Favg）的个体⽽⾔, Pc和Pm的值可能会 >1.0 。为了防⽌Pc和Pm的值超过1.0，我们设置了以下约束：
所以，对于Pm和Pc的公式，总结为：
adaptive的值
在上述中，我们看到了⼀个适应度最⾼的个体，它的Pc和Pm都是0 。这个最好的个体被不停的复制到下⼀代。与选择机制⼀起循环，这可能导致这个最好个体在种中以指数的增长形式快速增长，这会引起过早收敛。为了克服这个问题，我们为AGA（⾃适应遗传算法）的每⼀个个体都引进了⼀个默认的突变概率值（0.005）。
在现有⽂献中已经阐明了Pc应该取适当的值，最好为 0.5<Pc<1.0，Pm应该取⼩⼀点的值，最好为0.001<Pm<0.005，这是普通遗传算法（GAS）成功的必要措施。Pc的取值能够促进⼴泛的交叉，Pm的取值为了防⽌个体被破坏。然⽽，当Pc和Pm的值不变化时，这个⽅法是有效的和有意义的。
我们的⽅法的⽬标之⼀就是为了防⽌GA陷⼊局部最优解。为了实现这⼀个⽬标，我们采⽤低于平均适应度的个体去搜索空间中查包含最优解的范围。像这种个体，需要被完全打乱，并且处于这种⽬的，
我们让k4的值为0.5 。因为Favg的⼀个适应值的个体也应该被完全打乱，所以我们让K2的值也取0.5 。
基于类似的推论，我们让K1和K2的值取1.0 。这确保了所有适应度⼩于或者等于Favg的个体都要进⾏交叉操作。交叉的概率会随着适应度（⽗代个体中适应度最⼤的那个）趋向于Fmax⽽降低，并且这个概率对于适应度等于Fmax的个体为0.0 。
总结
通过⾃适应调节公式:
从种整体来看：
随着种的进化、可能解向着最优解靠拢，Favg逐渐接近Fmax，Fmax-Favg逐渐变⼩，Pc和Pm的值变⼤，这符合“ 随着种迭代，适应度越来越集中，距离（局部）极值越来越近，为了增加种多样性和跳出极值，Pc和Pm的值应该增⼤” 这⼀要求。
从某⼀代种内部各个个体来看：
不同个体的交叉和变异概率随着⾃⾝适应度呈线性变化。适应度（F 或 F）越⾼的个体，Fmax-F或者
Fmax-F'的值越⼩，这符合“ 保存优良个体”这⼀要求； ⽽适应度（F 或 F）越低的个体，Fmax-F或者Fmax-F'的值越⼤，这符合“ 改变劣质个体”这⼀要求。
特别的：
当个体的适应度等于当前当代种中的最佳适应度（F'=Fmax或者F=Fmax）时，经过公式的计算可知，Pc和Pm都为0， 这也符合“把最佳个体保存下来”这⼀要求。
参数问题选择：
但是上述为0的情况虽然能把最佳个体保存，但是交叉和变异概率直接0，会导致那些保存下来的优良个体在种中呈指数快速繁殖，导致早熟，所以让k2=0.5,k4=0.5，以利⽤种中适应值低于平均值的个体来搜索全局最优解。同时推荐k1=1.0,k3=1.0。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。