论文解读：自适应参数控制方案介绍——Effect Assessment详解

Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms, TCYB, 1994

动机

当 优化 多模态问题时，探索（exploration）和探测（exploitation）对于GA是至关重要的。二者之间的平衡取决于变异概率（ p m p_m pm​），交叉概率（ p c p_c pc​），以及所使用的交叉操作 类  型。提高 p m p_m pm​和 p c p_c pc​的值可以促进算法的探索能力却以牺牲探测性能为代价。在实际应用GA时，通常设定 p c p_c pc​为 [ 0.5 − 1.0 ] [0.5-1.0] [0.5−1.0]范围内的较大值，设定 p m p_m pm​为 [ 0.001 − 0.05 ] [0.001-0.05] [0.001−0.05]范围内的较小值。与固定参数方法不同，本文通过提出一种自适应 p c p_c pc​和 p m p_m pm​ 控制 方法实现了探索和探测的平衡。具体来说，当种群趋于局部最优值时，提高 p c p_c pc​和 p m p_m pm​的值，而当种群广泛分布于解空间时，降低 p c p_c pc​和 p m p_m pm​的值。

自适应  p c p_c pc​ 和 p m p_m pm​方案设计

首先，参数控制器应该具备这样一种能力： 识别 GA是否收敛到了一个最优值。

一个可行的方法是观察种群的平均 适应度值  f ˉ \bar{f} fˉ​ 与种群的最大适应度值  f m a x f_{max} fmax​ 的关系。从Fig. 2中可以看到，当GA收敛到局部最优值 0.5 0.5 0.5时，差值 f m a x − f ˉ f_{max}-\bar{f} fmax​−fˉ​开始下降。


   因此，我们可以将 f m a x − f ˉ f_{max}-\bar{f} fmax​−fˉ​作为识别GA收敛性的准绳，即， p c p_c pc​ 和 p m p_m pm​的值根据 f m a x − f ˉ f_{max}-\bar{f} fmax​−fˉ​值的变化而变化。具体的参数控制规则描述如下：
p c = k 1 / ( f m a x − f ˉ ) , p_c = k_1/(f_{max} - \bar{f}), pc​=k1​/(fmax​−fˉ​),
p m = k 2 / ( f m a x − f ˉ ) . p_m = k_2/(f_{max} - \bar{f}). pm​=k2​/(fmax​−fˉ​).

值得一提的是，上面的表达式不依赖于任何特定解的适应度值，而对于种群中的所有解具有相同的值。也就是说，具有高适应度值的解和低适应度值的解受到相同水平的变异和交叉操作。这样就导致当种群收敛到全局最优解(甚至局部最优解)时， p c p_c pc​ 和 p m p_m pm​会增加，并可能导致接近最优解时出现扰动，种群可能永远不会收敛到全局最优值。

为了解决这个问题，有必要保护“好的”解。这可以通过让适应度高的解获得较低的 p c p_c pc​ 和 p m p_m pm​，而让适应度低的解获得较高的 p c p_c pc​ 和 p m p_m pm​来实现。也就是说， p m p_m pm​的值不仅基于 f m a x − f ˉ f_{max}-\bar{f} fmax​−fˉ​，也基于解的适应度值 f f f 。相似地， p c p_c pc​应该基于两个父解的适应度值。因此，可将 p c p_c pc​ 和 p m p_m pm​进一步地表示为：
p c = k 1 ( f m a x − f ′ ) / ( f m a x − f ˉ ) , p_c = k_1(f_{max}-f')/(f_{max} - \bar{f}), pc​=k1​(fmax​−f′)/(fmax​−fˉ​),
p m = k 2 ( f m a x − f ) / ( f m a x − f ˉ ) . p_m = k_2(f_{max}-f)/(f_{max} - \bar{f}). pm​=k2​(fmax​−f)/(fmax​−fˉ​).

   其中， f ′ f' f′为参与交叉操作的父解中较大的适应度值。这里，为了将 p c p_c pc​ 和 p m p_m pm​限制在[0.0-1.0]范围内，规定 k 1 , k 2 < 1.0 k_1, k_2<1.0 k1​,k2​<1.0。同时
p c = k 3 , f ′ ≤ f ˉ p_c=k_3, f'\leq\bar{f} pc​=k3​,f′≤fˉ​

   且 p m = k 4 , f ≤ f ˉ p_m=k_4, f\leq\bar{f} pm​=k4​,f≤fˉ​

   其中， k 3 , k 4 < 1.0 k_3, k_4<1.0 k3​,k4​<1.0。

参考文献

[1]. M . Srinivas and Lalit M. Patnaik, ‘‘Adaptive probabilities of crossover and mutation in genetic algorithms,’’ IEEE Transactions on Systems, Man, and Cybernetics, vol. 24, no. 4, pp. 656-667, 1994.

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删