18.2.6 演化策略

18.2.6.1 演化原理

演化策略是模拟自然演化的随机优化过程的例子. 它们基于突变、重组和选择三个原理.

1. 突变

从亲本 ${\underset{―}{\mathbf{x}}}_P$ ,通过随机变化 $\underset{―}{\mathbf{d}}$ 形成后裔 ${\underset{―}{\mathbf{x}}}_O={\underset{―}{\mathbf{x}}}_P+\underset{―}{\mathbf{d}}$ ,其中 $\underset{―}{\mathbf{d}}$ 的分量是 $\left(0,{\sigma }_i^2\right)$ 正态分布随机变量 $Z\left(0,{\sigma }_i^2\right)$ ,其在每一次突变时要重新确定:

$$\begin{array}{}\text{(18.87)}& \underset{―}{\mathbf{d}}=\left(\begin{array}{c}{d}_1\\ d_2\\ ⋮\\ d_n\end{array}\right)=\left(\begin{array}{c}Z\left(0,{\sigma }_1^2\right)\\ Z\left(0,{\sigma }_2^2\right)\\ ⋮\\ Z\left(0,{\sigma }_n^2\right)\end{array}\right)=\left(\begin{array}{c}Z\left(0,1\right)\cdot {\sigma }_1\\ Z\left(0,1\right)\cdot {\sigma }_2\\ ⋮\\ Z\left(0,1\right)\cdot {\sigma }_n\end{array}\right).\end{array}$$

在正态分布 $\underset{―}{d}$ 情形下,小变化的概率很高,而大变化则很少出现. 这种变化受标准偏差 ${\sigma }_i$ 控制.

2. 重组

对于有 $\mu$ 个亲本的种群,可以通过混杂随机选择的两个或更多个亲本信息获得后代. 这种重组可采取两种变化方式:

以中间形式重组 其后代作为 $\varrho$ 个随机选择的亲本加权平均,即

$$\begin{array}{}\text{(18.88)}& {\underset{―}{\mathbf{x}}}_O=\sum _{i=1}^{\varrho }{\alpha }_i{\underset{―}{\mathbf{x}}}_{P_i},\sum _{i=1}^{\varrho }{\alpha }_i=1,2\le \varrho \le \mu .\end{array}$$

以离散形式重组 其后代 ${\underset{―}{x}}_O$ 的第 $i$ 个分量由 $\varrho$ 个亲本中随机选择的一个亲本的第 $i$ 个分量确定,即

$$\begin{array}{}\text{(18.89)}& x_{iO}=x_{i{P}_j},j\in \{1,\cdots ,\varrho \},i=1,\cdots ,n.\end{array}$$

3. 选择

通过突变和重组,随机形成一组后代. 在随后的选择过程中,目标函数 $f\left(\underset{―}{x}\right)$ 被作为比较个体适应性的一种度量. 最适应的个体选择作为下一代. 在某些策略下, 仅仅子孙后代才参与选择. 有些策略也会考虑亲本参与选择 (参见 [18.9]).

18.2.6.2 演化算法

每一种演化策略都是基于如下算法:

a) 确定由 $\mu$ 个个体组成的适当的初始种群. 这些是第 1 代亲本 $X_P^1=\{{\underset{―}{x}}_{P_1}^1,$ $\cdots ,{\underset{―}{\mathbf{x}}}_{P_{\mu }}^1\}$ .

b) 在第 $k$ 步中,通过当前一代亲本 $X_P^k=\left\{{\underset{―}{\mathbf{x}}}_{P_1}^k,\cdots ,{\underset{―}{\mathbf{x}}}_{P_{\lambda }}^k\right\}$ 的突变和重组产生 $\lambda$ 个后代 $X_O^k=\left\{{\underset{―}{\mathbf{x}}}_{O_1}^k,\cdots ,{\underset{―}{\mathbf{x}}}_{O_{\lambda }}^k\right\}$ .

c) 通过选择得到最佳的 $\mu$ 个个体作为下一代亲本 $X_P^{k+1}=\left\{{\underset{―}{\mathbf{x}}}_{P_1}^{k+1},\cdots ,{\underset{―}{\mathbf{x}}}_{P_{\mu }}^{k+1}\right\}$ .

d) 重复步骤 b) 和 c) 直到满足停止规则. 这个规则可以是满足优化问题的最优判据, 或者是达到指定的代际数, 或者是超过给定的电脑时间, 等等.

18.2.6.3 演化策略的分类

每一个演化策略都由一列参数刻画. 最重要的参数是种群大小 $\mu$ 、后代个数 $\lambda$ 、 参与重组的亲本个数 $\varrho$ ,以及实施突变、重组和选择的规则. 为了区分各种不同类型的策略,通常使用一种特殊的记号. 对于仅使用突变产生后代的策略,使用 $\left(\mu +\lambda \right)$ 或 $\left(\mu ,\lambda \right)$ 策略记号. 策略 $\left(\mu +\lambda \right)$ 和 $\left(\mu ,\lambda \right)$ 彼此的区别在于选择的类型不同. 在策略 $\left(\mu ,\lambda \right)$ 中,仅在子孙中选择新一代,而在策略 $\left(\mu +\lambda \right)$ 中,则新一代的选择也涉及母体. 至于使用重组策略,所涉及的亲本数 $\varrho$ 会在 $\left(\mu /\varrho +\lambda \right)$ 策略和 $\left(\mu /\varrho ,\lambda \right)$ 策略记号中体现.

18.2.6.4 生成随机数

为了对演化程序做数值评估, 需要均匀和正态分布的随机变量. 均匀分布的随机变量的值可以从分节第 1100 页 16.3.5.2 中给出的方法得到. 正态分布随机变量则可以根据如下方式从均匀随机变量产生:

博克斯-穆勒 (Box-Muller) 方法 如果 $G_1$ 和 $G_2$ 是区间 $\left[0,1\right]$ 上均匀分布的随机数,则如下两个方程给出两个统计独立正态分布的 $\left(0,{\sigma }^2\right)$ 随机数 $Z_1\left(0,{\sigma }^2\right)$ 和 $Z_2\left(0,{\sigma }^2\right)$ :

$$Z_1\left(0,{\sigma }^2\right)=\sigma \sqrt{-2\ln G_1}\cos \left(2\pi G_2\right)\text{ 和 }{Z}_2\left(0,{\sigma }^2\right)=\sigma \sqrt{-2\ln G_1}\sin \left(2\pi G_2\right)$$

(18.90)

18.2.6.5 演化策略的应用

在实际中, 优化问题通常高度复制. 在这里, 1209 页 18.2.5 中描述的常规优化过程往往并不适合. 演化策略属于非微分解法, 它是基于目标函数值的比较. 这种解法对目标函数的结构要求很简单. 目标函数并不需要可微或连续. 从而这种演化策略适于相当广泛的优化问题.

演化策略的应用并不限于无约束连续优化问题. 带约束的优化问题也可处理, 这里约束是通过在目标函数中添加惩罚项进行处理 (参见第 1221 页 18.2.8 中的罚函数法和障碍函数法). 另一种应用场合是离散演化,这里 $\underset{―}{x}$ 的部分或全部分量可能从某个离散集中取值. 一种可能的突变机制是以等概率方式用其某个相邻值取代离散分量值.

18.2.6.6 (1+1)突变一选择策略

这种方法类似于 1209 页 18.2.5 中介绍的梯度法,差别在于方向 ${\underset{―}{\mathbf{d}}}^k$ 是正态分布的随机向量. 种群由单个个体组成, 其在每一代只产生一个后代.

1. 突变方式

在第 $k$ 代,后代从亲本加上一正态分布的随机向量得到

$$\begin{array}{}\text{(18.91)}& {\underset{―}{\mathbf{x}}}_O^k={\underset{―}{\mathbf{x}}}_P^k+\alpha {\underset{―}{\mathbf{d}}}^k.\end{array}$$

因子 $\alpha$ 是能反映收敛速度的参数. 我们把 $\alpha$ 看作突变的步长.

2. 选择方式

下一代,即第 $k+1$ 代的新亲本的选择是比较两个个体的目标函数值,即按照

下面的公式选择:

$$\begin{array}{}\text{(18.92)}& {\underset{―}{\mathbf{x}}}_P^{k+1}=\{\begin{array}{ll}{\underset{―}{\mathbf{x}}}_O^k,& f\left({\underset{―}{\mathbf{x}}}_O^k\right)<f\left({\underset{―}{\mathbf{x}}}_P^k\right),\\ {\underset{―}{\mathbf{x}}}_P^k,& \text{ 其他. }\end{array}\end{array}$$

如果在达到指定的代际数时没有更好的后代, 则此程序终止. 如果这种突变多半会导致后代改善,则可以增加步长. 而如果突变导致后代的改善较小,则应该减少 $\alpha$ 值.

3. 步长控制

突变步长 $\alpha$ 的选择对于演化方法的收敛性具有重要影响. 为了快速收敛通常会推荐大步长, 而在邻近最优或在目标函数的快速变化或振动区域, 则要求小步长. 最优步长依赖于所研究的问题. 步长太小会导致滞止, 而步长太大则可能引起演化过程的过调.

(1) 1/5 成功法则 在上一步中成功突变数目与突变总数之比确定成功的比值 $q$ . 如果 $q>1/5$ ,则步长可以增加. 而如果成功比值较小,则步长 $\alpha$ 应该减少:

$$\begin{array}{}\text{(18.93)}& {\alpha }_{k+1}=\{\begin{array}{ll}c\cdot {\alpha }_k& q<1/5,\\ \frac{1}{c}\cdot {\alpha }_k,& q>1/5,\end{array}c=0.8,\cdots ,0.85.\end{array}$$

(2)突变步长的确定 1/5 的法则是一种粗略的选择,因而在考虑某个具体问题时并不会总是令人满意的. 在一个扩展模型中,步长 $\alpha$ 和标准偏差 ${\sigma }_i,i=$ $1,2,\cdots ,n$ 总是在不断修正中. 这里 $\alpha$ 和 ${\sigma }_i$ 以等概率的方式乘以三个因子 $c,1,1/c$ 中的某一个, $c=1.1,\cdots ,1.5$ . 进一步的信息见 [18.9].

18.2.6.7 种群策略

上一节介绍的 $\left(1+1\right)$ 策略仅仅以十分简单的方式反映自然演化的原理. 在推广到种群模型时, 可能要考虑演化过程的进一步性质. 演化过程中的大量个体确保解空间的不同区域都会搜索到.

1. $\left(\mu +\lambda \right)$ 演化策略

$\left(\mu +\lambda \right)$ 策略是 $\left(1+1\right)$ 策略的推广. 从当前一代的 $\mu$ 个亲本 $X_P^k=\{{\underset{―}{\mathbf{x}}}_{P_1}^k,\cdots$ , ${\underset{―}{x}}_{P_{\mu }}^k\}$ ,以等概率随机选择一组 $\lambda$ 个母体. 允许重复选择,甚至在 $\mu <\lambda$ 的情形下, 这种重复选择也是必须的. 通过突变产生 $\lambda$ 个后代 $X_O^k=\left\{{\underset{―}{\mathbf{x}}}_{O_1}^k,\cdots ,{\underset{―}{\mathbf{x}}}_{O_{\lambda }}^k\right\}$ . 从候选组 $X_O^k\cup X_P^k$ 中选择最佳的 $\mu$ 个个体进入下一代.

由于亲本也参与到选择,故种群从一代到下一代的质量不可能更差. $\left(\lambda +\mu \right)$ 策略的特点是它能保持已经找出的局部最优, 这是因为远离最优点要求发生的大的突变, 但出现这种情形的概率是非常小的. 这意味着, 个体可能有无限寿命. 通过对亲本的目标函数值加上惩罚项使其一代代增加, 从而可以避免这种情形出现. 用这种方法可以模拟个体变老.

2. $\left(\mu ,\lambda \right)$ 演化策略

与 $\left(\mu +\lambda \right)$ 策略相反,其选择方式是在 $\lambda$ 个后裔中挑选 $\mu$ 个个体作为下一代, 即在这一策略中,亲本不再活下来. 因此必须有 $\lambda >\mu$ . 后代的目标函数值可能大于亲本的目标函数值. 这一程序可以从局部最优点开始.

选择压力 参与选择的个体与种群大小之比定义为选择压力 $S$ :

$$\begin{array}{}\text{(18.94)}& S=\{\begin{array}{ll}\frac{\lambda +\mu }{\mu },& \text{ 对于 }\left(\lambda +\mu \right)\text{ 策略,}\\ \frac{\lambda }{\mu },& \text{ 对于 }\left(\lambda ,\mu \right)\text{ 策略,}\end{array}1\le S<\mathrm{\infty }.\end{array}$$

如果选择压力接近于 1,则这种选择方式几乎没有影响. 大量的后代,即 $\lambda \gg \mu$ 会导致很大的选择压力, 因为当前个体集合中只有少数几个会存活到下一代.

3. 带重组的 $\left(\mu /\varrho +\lambda \right)$ 和 $\left(\mu /\varrho ,\lambda \right)$ 演化策略

借助于重组概念, 建立了种群个体之间的某些关系, 从而后代中混合了几个亲本的信息. 为了产生后代,从一组亲本 $X_P^k$ 中以等概率方式选择 $\varrho$ 个亲本. 假定 $\lambda$ 个后代中的每个成员,都是从 $\varrho$ 个亲本中独立选择的. 后代是所选亲本的离散或中间重组. 用这种方法产生的后代再经突变, 并进入选择过程.

在前面描述的 $\left(\mu +\lambda \right)$ 或 $\left(\mu ,\lambda \right)$ 策略中,每一个体都是一系列突变应用于第 1 代亲本中一个成员的结果. 因此, 仅通过多代的突变就可能是一种比较一般的演化步骤. 但采用重组方式则可能会出现多种更一般的演化方式, 尤其是当亲本彼此相隔遥远, 其后代就会具有新的特性.

4. 带更多个种群的演化策略

上述的演化原理形式上可以扩展到多种群情形. 这就是说, 现在不再是种群个体间的竞争, 而是种群之间的竞争. 因此, 这种演化过程包含两个层级, 并用扩展的记号表示为: $\left[{\mu }_2/{\varrho }_2+{\lambda }_2\left({\mu }_1/{\varrho }_1+{\lambda }_1\right)\right]$ . 从一组 ${\mu }_2$ 个种群亲本,通过 ${\varrho }_2$ 个种群的重组,产生一组 ${\lambda }_2$ 个种群后代,这里的重组对于每个种群后代而言都是随机选取的. 在这 ${\lambda }_2$ 个种群后代中,使用 $\left({\mu }_1/{\varrho }_1+{\lambda }_1\right)$ 或 $\left({\mu }_1/{\varrho }_1,{\lambda }_1\right)$ 策略进行优化. 在达到给定代际数之后, 基于适当准则选择出最佳种群. 种群中最佳个体的目标函数值或种群的均值可以作为种群比较的判据.