智能优化算法

智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。

常用的智能优化算法

• 1）遗传算法（Genetic Algorithm， 简称GA）
• 2）模拟退火算法（Simulated Annealing， 简称SA）
• 3）禁忌搜索算法-（Tabu Search， 简称TS）

智能优化算法的特点

它们的共同特点：都是从任一组解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。

遗传算法

遗传算法起源

遗传算法是由美国Michigan大学的J. Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法 。

遗传算法的搜索机制

遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从候选解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

基本遗传算法

基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。

基本遗传算法的组成

• （1）编码（产生初始种群）
• （2）适应度函数
• （3）遗传算子（选择、交叉、变异）
• （4）运行参数

SGA的框图

适应度与适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度(fitness)就是借鉴生物个体对环境的适应程度, 而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitness function)就是问题中的全体对象与其适应度之间的一个对应关系, 即对象集合到适应度集合的一个映射。 它一般是定义在论域空间上的一个实数值函数。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 说明：“论域”是数理逻辑中的概念。“在一个逻辑系统中，所有的个体组成的集合，称为个体域，亦称论域。”

种群(population)

SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。 或种群就是模拟生物种群而由若干个染色体组成的群体, 它一般是整个论域空间的一个很小的子集。

遗传操作

遗传算法中有三种关于染色体的运算（遗传算子）: 选择-复制、交叉和变异,这三种运算被称为遗传操作或遗传算子(genetic operator)。

选择-复制算子和选择概率

选择-复制 (selection reproduction) 操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算, 就是从种群中选择适 应度较高的染色体进行复制, 以生成下一代种群。选择-复制的 通常做法是, 对于一个规模为 $N$ 的种群 $S$, 按每个染色体 $x_{i} \in S$ 的选择概率 $P\left(x_{i}\right)$ )所决定的选中机会, 分 $N$ 次从 $\mathrm{S}$ 中随机选定 $N$ 个染色体, 并进行复制。这里的选择概率 $P\left(x_{i}\right)$ 的计算公式为 $$ P\left(x_{i}\right)=\frac{f\left(x_{i}\right)}{\sum_{j=1}^{N} f\left(x_{j}\right)} $$

其中, $f$ 为适应度函数, $f\left(x_{i}\right)$ 为 $x_{i}$ 的适应度。可以看出, 染色 体 $x_{i}$ 被选中的概率就是其适应度 $f\left(x_{i}\right)$ 所占种群中全体染色体适 应度之和的比例。显然, 按照这种选择概率定义，适应度越高 的染色体被随机选定的概率就越大，被选中的次数也就越多, 从而被复制的次数也就越多。相反,适应度越低的染色体被选 中的次数也就越少,从而被复制的次数也就越少。如果把复制 看做染色体的一次换代的话,则这就意味着适应度越高的染色 体其后代也就越多,适应度越低的染色体其后代也就越少，甚至 被淘汰。这正吻合了优胜劣汰的自然选择法则。

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作： 适应度高的个体被遗传到下一代群体中的概率大; 适应度低的个体, 被遗传到下一代群体中的概率小。 选择操作的任务就是按某种方法从父代群体中选取一些个体, 遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。

轮盘赌选择又称比例选择算子, 它的基本思想是： 各个个体被选中的概率与其适应度函数值大小成正比。 $$ P\left(x_{i}\right)=\frac{f\left(x_{i}\right)}{\sum_{j=1}^{N} f\left(x_{j}\right)} $$

上述按概率选择的方法可用一种称为赌轮的原理来实现。 即做一个单位圆, 然后按各个染色体的选择概率将圆面划分 为相应的扇形区域(如图1所示)。这样, 每次选择时先转动轮 盘, 当轮盘静止时,上方的指针所正对着的扇区即为选中的扇 区, 从而相应的染色体即为所选定的染色体。例如, 假设种群 $S$ 中有4个染色体: $s_{1}, s_{2}, s_{3}, s_{4}$, 其选择概率依次为: $0.11,0.45$, $0.29,0.15$, 则它们在轮盘上所占的份额如图1中的各扇形区域所示。

在算法中奢轮选择法可用下面的过程来模拟：

• (1) 在 $[0,1]$ 区间内产生一个均匀分布的伪随机数 $r$ 。
• (2) 若 $r \leq q_{1}$, 则染色体 $x_{1}$ 被选中。
• (3) 若 $q_{k-1}<r \leq q_{k}(2 \leq k \leq N)$, 则染色体 $x_{k}$ 被选中。 其中的 $q_{i}$ 称为染色体 $x_{i}(i=1,2, \ldots, n)$ 的积累概率, 其计算公式为： $$ q_{i}=\sum_{j=1}^{i} P\left(x_{j}\right) $$

一个染色体 $x_{i}$ 被选中的次数, 可以用下面的期望值 $e\left(x_{i}\right)$ 来确定： $$ \begin{aligned} e\left(x_{i}\right) &=P\left(x_{i}\right) \times N \\ &=\frac{f\left(x_{i}\right)}{\sum_{j=1}^{N} f\left(x_{j}\right)} \times N=\frac{f\left(x_{i}\right)}{\sum_{j=1}^{N} f\left(x_{j}\right) / N}=\frac{f\left(x_{i}\right)}{\bar{f}} \end{aligned} $$ 其中 $\bar{f}$ 为种群 $S$ 中全体染色体的平均适应度值。

交叉(crossover)算子

所谓交叉运算, 是指对两个相互配对的染色 体依据交叉概率 $\mathrm{P}_{\mathrm{c}}$ 按某种方式相互交换两 个染色体某些位上的基因，从而形成两个新的个体。交叉运算是遗传算法区别于其 他进化算法的重要特征, 它在遗传算法中起关键作用, 是产生新个体的主要方法。 SGA中交叉算子采用单点交叉算子。

例如,设染色体 $s_{1}=01001011, s_{2}=10010101$, 交换其后4位基因, 即:

变异(mutation)算子

变异(mutation)亦称突变,就是改变染色体某个 (些)位上(基因座)的基因。是依据变异概率 $\mathrm{P}_{\mathrm{m}}$ 将个体编码串中的某些基因值用其它基因值来替换, 从而形成一个新的个体。遗传算法中的变异运算 是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力, 同时保持种群的多样性。交叉运 算和变异运算的相互配合，共同完成对搜索空间 的全局搜索和局部搜索。SGA中变异算子采用基 本位变异算子。

基本位变异算子

基本位变异算子是指对个体编码串随机指 定的某一位或某几位基因作变㫒运算。对 于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一 基因座上的原有基因值为 0 , 则变异操作将 其变为 1 ; 反之, 若原有基因值为 1 , 则 异操作将其变为0。

运行参数

• (1) M：种群规模 $(20-100)$
• (2) $T ：$ 遗传运算的终止进化代数(100-500)
• (3) $P_{c}$ : 交叉概率 (0.4-0.9)
• (4) $P_{m}$ : 变异概率 (0.001-0.01) 参加交叉运算的染色体个数占全体染色体总数的比例, 记为 $P C_{\text {。 }}$ 由于生物繁殖时染色体的交叉是按一定的概率发生的，因此参加 交叉操作的染色体也有一定的比例，而交叉率也就是交叉概率。 变异率(mutation rate)是指发生变异的基因位数所占全体染色 体的基因总位数的比例, 记为$P \mathrm{~m}$ 。由于在生物的繁衍进化过程中 变异也是按一定的概率发生的，而且发生概率一般很小，因此变异率也就是变异概率。

基本遗传算法流程

• 步1 在论域空间 $U$ 上定义一个适应度函数 $f(x)$ ，给定种 群规模 $N$ ，交叉率 $P_{\mathrm{c}}$ 和变异率 $P_{\mathrm{m}} ，$ 代数 $T$;
• 步2 随机产生U中的 $N$ 个染色体 $s_{1}, s_{2}, \ldots, s_{\mathrm{N}}$, 组成初始 种群 $S=\left\{s_{1}, s_{2}, \ldots, s_{\mathrm{N}}\right\}$, 置代数计数器 $t=1$;
• 步3 计算S中每个染色体的适应度 $\mathrm{f}\left(\mathrm{s}_{\mathrm{i}}\right)$;
• 步4 若终止条件满足, 则取 $S$ 中适应度最大的染色体作为所求结果，算法结束。
• 步 5 按选择概率 $P\left(x_{i}\right)$ 所决定的选中机会, 每次从 $S$ 中随机选定1个染色体并将其复制，共做 $N$ 次，然后将复制所得的 $N$ 个染色体组成群体 $S_{1}$;
• 步6 按交叉率 $P_{\mathrm{c}}$ 所决定的参加交叉的染色体数 $c$, 从 $S_{1}$ 中 随机确定 $c$ 个染色体, 配对进行交叉操作, 并用产生的新染色 体代替原染色体，得群体 $S_{2}$;
• 步 7 按变异率 $P_{\mathrm{m}}$ 所决定的变异次数 $m$, 从 $S_{2}$ 中随机确定 $m$ 个染色体，分别进行变异操作, 并用产生的新染色体代替原染色体，得群体 $S_{3}$;
• 步8 将群体 $S_{3}$ 作为新一代种群，即用 $S_{3}$ 代替 $S, t=t+1$, 转 步3;

需要说明的是, 在应用遗传算法解决实际问题时, 还需给出结构模式的表示方案、适应度的计算方法、终止条件等。表示方案通常是把问题的搜索空间的每一个可能的点,编码为一个看做染色体的字符串, 字符通常采用二进制数0、1。适应度的计算方法一般根据实际问题而定。

遗传算法的特点

• (1) GA搜索群体中的点是并行, 而不是单点;
• (2) GA使用概率变换规则，而不是确定的变换 规则i
• (3) 适应度函数不受连续、可微等条件的约 束, 适用范围很广。只需要影响搜索方向的 目标函数和相对应的适应度函数;
• (4) GA使用编码参数集,而不是自身的参数集；

---

import matplotlib.pyplot as plt
plt.rcParams['font.family'] = ['SimSun']
plt.rcParams['axes.unicode_minus']=False

p = [0.11,0.45,0.29,0.15]
S = ['S1','S2','S3','S4']

plt.style.use('fivethirtyeight')

plt.pie(p, labels=S, autopct='%1.1f%%', counterclock=False, startangle=90)

plt.title('轮盘赌')
plt.tight_layout()
plt.show()