前言

本文尝试对遗传算法中不同适值函数的标定(Scaling)方法进行下总结,并针对常用的线性标定和动态线性标定进行了Python实现,以装饰器的形式添加到遗传算法框架GAFT中,这样在使用GAFT运行遗传算法迭代的时候可以更加Pythonic的给自定义的适值函数进行标定。最后针对能够防止早熟情况的大变异算法进行了相应的实现。

目前(动态)线性标定装饰器以及大变异算子均已添加到GAFT中,gaft项目链接:

适值函数的标定

选择压力

The tendency to select the best member of the current generation is known as selective pressure.

选择压力也就是种群中最好个体与最坏个体被选中概率的差值,这个差距越大,选中好个体的趋势就越大,则成为选择压力大。

适值函数的标定

一般情况下,直接拿目标函数作为适值函数十分的方便,但是很多情况下却不能这么做,例如对于求最小值问题,我们必须将目标函数取反才能作为适值函数(这是最简单的情况)。

当我们遗传算法中不同个体适值函数的值相对差别很小的时候,我们根据适应度值的大小进行个体选择的选择压力(Selective pressure)就会变小,选优的能力弱化,这个时候我们需要对原始的适值函数进行标定(Scaling)是的他们相对差别增大,进而增大选择压力,增强算法的选优能力。

例如:
$$
\left[\begin{matrix}
f_1 = 1001 \\
f_2 = 1002 \\
f_3 = 999 \\
f_4 = 997 \\
\end{matrix} \right] \xrightarrow{scaling} \left[\begin{matrix}
f_1’ = f_1 - f_4 = 4 \\
f_2’ = f_2 - f_4 = 5 \\
f_3’ = f_3 - f_4 = 2 \\
f_4’ = f_4 - f_4 = 0
\end{matrix} \right]
$$

局部搜索、广域搜索与选择压力的关系

在遗传算法中,局部搜索同广域搜索其实相互矛盾的,注重局部搜索则会陷入局部最优,但是注重广域搜索会导致算法精确开发能力不强。因此需要综合两者考虑,我们可以在搜索刚刚开始的时候使用较小的选择压力来广域搜索,随着迭代的进行可以动态的增大选择压力来使算法偏向于局部搜索。

几种不同的适值函数标定方法

对目标函数的标定方法一般有:线性标定、动态线性标定、幂律标定、对数标定等

线性标定

线性标定的形式:
$$
f’ = af + b
$$
其中$f’$为标定后的适值函数,$f$为原始的目标函数。

求最大值

对于求目标函数的最大值的时候, 即 $arg \max f(x)$

我们取$a = 1, b = -f_{min} + \xi$, 其中$\xi$是一个较小的数,目的是使得种群中最差个体也有被选中的机会,不然自身减掉$f - f_{min} = 0$, $\xi$的存在可以增加种群的多样性。

最终的适值函数表达式:
$$f’ = f(x) - f_{min} + \xi$$

求最小值

当我们需要求目标函数最小值的时候,$arg \min f(x)$,我们需要对目标函数进行取反操作, 即
$a = -1, b = f_{max} - f(x) + \xi$

最终的适值函数表达式:
$$f’ = f_{max} - f(x) + \xi$$

GAFT中添加对于目标函数的标定

由于适值函数标定并不针对某个目标函数,我便想通过装饰器的方式来方便给任何自定义的fitness函数进行标定。对于基本的线性标定,我在GAEngine中添加了个带参数的装饰器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def linear_scaling(self, target='max', ksi=0.5):
'''
A decorator constructor for fitness function linear scaling.
:param target: The optimization target, maximization or minimization.
:type target: str, 'max' or 'min'
:param ksi: Selective pressure adjustment value.
:type ksi: float
Linear Scaling:
1. arg max f(x), then f' = f - min{f(x)} + ksi;
2. arg min f(x), then f' = max{f(x)} - f(x) + ksi;
'''
def _linear_scaling(fn):
# For original fitness calculation.
self.ori_fitness = fn
@wraps(fn)
def _fn_with_linear_scaling(indv):
# Original fitness value.
f = fn(indv)
# Determine the value of a and b.
if target == 'max':
f_prime = f - self.ori_fmin + ksi
elif target == 'min':
f_prime = self.ori_fmax - f + ksi
else:
raise ValueError('Invalid target type({})'.format(target))
return f_prime
return _fn_with_linear_scaling
return _linear_scaling

这个时候如果我们在定义了一个自己的目标函数以后,想对其进行线性标定便可以使用engine的这个装饰器对函数进行修饰即可, 像下面这样:

1
2
3
4
5
6
7
8
# Create a GA engine...
# 先标定,后注册到引擎中
@engine.fitness_register
@engine.linear_scaling(target='min', ksi=0.5)
def fitness(indv):
x, = indv.variants
return x + 10*sin(5*x) + 7*cos(4*x)

其中装饰器中的参数分别为:

  • target: 优化目标函数到最小值还是最大值,值可以是:'max'或者'min'
  • ksi: 即公式中$\xi$

动态线性标定

动态线性标定是遗传算法中最常用的标定方法,他是基于上面提到的线性标定,在线性标定中的$\xi$在动态线性标定中并不是一成不变的,而是随着迭代次数的增加而变化。

动态线性标定的函数表达式:
$$f’ = a^{k}f + b^{k}$$
其中,$k$为迭代指标,表示$\xi$会随着迭代数而不同。

求最大值

当我们的优化目标是目标函数的最大值,这是我们取$a^{k} = 1, b^{k} = -f_{min} + \xi^{k}$, 这是的函数表达为:
$$f’ = f - f_{min} + \xi^{k}$$

求最小值

求最小值的时候需要取反操作,这时取$a^{k} = -1, b^{k} = f_{max} + \xi^{k}$, 最终函数表达式:
$$f’ = f_{max} - f + \xi^{k}$$

关于$\xi^{k}$

动态线性标定中的$\xi^{k}$作用同线性标定中的$\xi$为选择压力调节值, 它的存在使得种群中最坏的个体仍有被选中的机会,但是动态标定中的$\xi^{k}$的值会随着$k$增大而减小。

$\xi^{k}$的取值: $\xi^{0} = M, \xi^{k} = \xi^{k-1}\cdot r, r \in \left[0.9, 0.999\right]$, 我们通过调节$M$和$r$来调节$\xi^{k}$

通过可以动态变化的$\xi^{k}$,我们可以使广域搜索范围宽保持种群的多样性,局部搜索保持收敛性,即,开始时希望选择小,迭代到后面希望选择压力逐渐变大.

GAFT中添加给目标函数添加动态线性标定

与上面线性标定的方法相同,GAFT中同样使用了标定装饰器来装饰用户自定义的目标函数,实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def dynamic_linear_scaling(self, target='max', ksi0=2, r=0.9):
'''
A decorator constructor for fitness dynamic linear scaling.
:param target: The optimization target, maximization or minimization.
:type target: str, 'max' or 'min'
:param ksi0: Initial selective pressure adjustment value, default value
is 2
:type ksi0: float
:param r: The reduction factor for selective pressure adjustment value,
ksi^(k-1)*r is the adjustment value for generation k, default
value is 0.9
:type r: float in range [0.9, 0.999]
Dynamic Linear Scaling:
For maximizaiton, f' = f(x) - min{f(x)} + ksi^k, k is generation number.
'''
def _dynamic_linear_scaling(fn):
# For original fitness calculation.
self.ori_fitness = fn
@wraps(fn)
def _fn_with_dynamic_linear_scaling(indv):
f = fn(indv)
k = self.current_generation + 1
if target == 'max':
f_prime = f - self.ori_fmin + ksi0*(r**k)
elif target == 'min':
f_prime = self.ori_fmax - f + ksi0*(r**k)
else:
raise ValueError('Invalid target type({})'.format(target))
return f_prime
return _fn_with_dynamic_linear_scaling
return _dynamic_linear_scaling

这里充分的利用Python的闭包,在engine中获取当前种群最大值与最小值的相关数据。

在脚本中修饰目标函数便可以这样:

1
2
3
4
5
@engine.fitness_register
@engine.dynamic_linear_scaling(target='max', ksi0=2, r=0.9)
def fitness(indv):
x, = indv.variants
return x + 10*sin(5*x) + 7*cos(4*x)

其他标定方法

这里简要的介绍下其他标定方法。

幂律标定

  • 函数表达式: $f’ = f^{\alpha}$
  • $\alpha$的取值, $\alpha > 1$增大选择压力, $\alpha < 1$减小选择压力

对数标定

  • 函数表达式: $f’ = aLnf + b$
  • 作用: 缩小目标函数之间的差别

指数标定

  • 函数表达式: $f’ = ae^{bf} + c$
  • 作用: 扩大目标函数间的差别

窗口技术

  • 函数表达式: $f’ = af - f_w$
  • $f_w$为前$W$代中的目标函数最小值,他考虑了各代$f_{min}$的波动,这样$f_w$具有记忆性

大变异算法

众所周知,简单的遗传算法存在“早熟”的问题,也就是算法过早的收敛到一个非全局最优点,出现此问题的主要原因是一种被称为“顶端优势”的现象存在,即当算法进行到某一代时,在种群中某个个体的适应度远远大于任何一个个体的适应度,导致选择算法总是会选到此个体生成子代个体,极限情况下就是所有个体都来自统一祖先,即”早熟”。除了对目标函数进行标定,我们可以通过大变异算法来避免早熟。

大致思路: 当某代中所有个体集中在一起时,我们以一个远大于通常变异概率的概率执行一次变异操作,具有大变异概率的变异操作能够随机、独立的产生许多新的个体,从而是整个种群脱了“早熟”。

如何判断种群个体的集中程度

通常采取比较种群中所有个体的适应度值的平均值$f_{avg}$与最大值$f_{max}$的接近程度来判断,如果最大值与平均值越接近说明个体就越集中。

具体过程

当某一代的最大适应度$f_{max}$与平均适应度值$f_{avg}$满足:
$$\alpha \cdot f_{max} < f_{avg}$$

其中,$0.5 < \alpha < 1$, 被称为密集因子,表征个体集中程度。随后,我们以一个大变异概率进行一次变异操作(通常大5倍以上), 即“打散”。

大变异操作的两个参数

  1. 密集因子$\alpha$: 决定大变异操作在整个过程中所占的比重,其数值约接近$0.5$,大变异操作越频繁
  2. 大变异概率: 概率越大,大变异算法的稳定性就越好,但是收敛速度可能会降低,当大变异概率的数值为0.5的时候,大变异操作就近似退化为随机搜索

GAFT中的大变异算子

大变异操作与具体的变异算子实现无关,这里我还是依据内置的FlipBitMutation算子为基础, 具体的代码实现参见https://github.com/PytLab/gaft/blob/master/gaft/operators/mutation/flip_bit_mutation.py。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class FlipBitBigMutation(FlipBitMutation):
def __init__(self, pm, pbm, alpha):
'''
Mutation operator using Flip Bit mutation implementation with adaptive
big mutation rate to overcome premature or local-best solution.
:param pm: The probability of mutation (usually between 0.001 ~ 0.1)
:type pm: float in (0.0, 1.0]
:param pbm: The probability of big mutation, usually more than 5 times
bigger than pm.
:type pbm: float
:param alpha: intensive factor
:type alpha: float, in range (0.5, 1)
'''
super(self.__class__, self).__init__(pm)
if not (0.0 < pbm < 1.0):
raise ValueError('Invalid big mutation probability')
if pbm < 5*pm:
self.logger.warning('Relative low probability for big mutation')
self.pbm = pbm
# Intensive factor.
if not (0.5 < alpha < 1.0):
raise ValueError('Invalid intensive factor, should be in (0.5, 1.0)')
self.alpha = alpha
def mutate(self, individual, engine):
'''
Mutate the individual with adaptive big mutation rate.
'''
pm = self.pm
if engine.fmax*self.alpha < engine.fmean:
self.pm = self.pbm
self.logger.info('Big mutation probabilty: {} -> {}'.format(pm, self.pm))
# Mutate with big probability.
individual = super(self.__class__, self).mutate(individual, engine)
# Recover probability.
self.pm = pm
return individual

总结

本文尝试对遗传算法中不同适值函数的标定(Scaling)方法进行下总结,并针对常用的线性标定和动态线性标定进行了Python实现,以装饰器的形式添加到遗传算法框架GAFT中,这样在使用GAFT运行遗传算法迭代的时候可以更加Pythonic的给自定义的适值函数进行标定。最后针对能够防止早熟情况的大变异算法进行了相应的实现。

参考

  • 《MATLAB最优化计算(第三版)》
  • 马钧水, 刘贵忠, 贾玉兰. 改进遗传算法搜索性能的大变异操作[J]. 控制理论与应用, 1998(3):404-408.

Comments