智能计算

# 1. 进化算法

进化算法 (evolutionary algorithms，EA) 是基于自然选择和自然遗传等生物进化机制的一种搜索算法。
进化算法是一个 “算法簇”，包括遗传算法 (GA)、遗传规划、进化策略和进化规划等。
进化算法的基本框架是遗传算法所描述的框架。

基本操作：

1. 选择
2. 重组
3. 变异

# 2. 基本遗传算法 (genetic algorithm)

# 2.1 群体设定

1. 随机产生群体规模数目的个体作为初始群体

2. 模式定理表明：若群体规模为 M，则遗传操作可从这 M 个个体中生成和检测 M^3 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解

# 2.2 适应度函数 Fit

若目标函数为最大化问题 Fit (f (x))=f (x) 或 f (x)-Cmin
若目标函数为最小化问题 Fit (f (x))=1/f (x) Cmax-f (x) 从而保证非负性

在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题 (deceptive problem)
过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。
停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。
适应度函数的尺度变换：线性变换、幂函数变换、指数函数变换

# 2.3 选择

选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。
个体适应度越高，其被选择的机会就越多

个体选择概率分配方法

1. 适应度比例或蒙特卡罗法
   个体 i 被选中的概率为：
   $p_si} =\frac{f_i}{\displaystyle\sum_{i=1}(M{f_i)} $

2. 排序方法
   群体成员按适应度大小从小到大排序
   $ p_i=\frac {a-bi}{M (M+1)}$

个体选择方法

1. 转盘赌选择
   按个体的选择概率产生一个转盘，随机产生一个随机数看落入哪个区域
2. 锦标赛选择方法
   从群体随机选择几个个体，将其中适应度最高的个体保存到下一代。反复执行此操作
3. 最佳个体保存方法
   把群体适应度最高的个体保存到下一代

# 2.4 交叉 (在个体串随机选择交叉点)

1. 一点交叉 (single-point crossover)
2. 两点交叉 (two-point crossover)

# 2.5 变异

随机发生个体串的编码改变
如位点变异、插入变异、互换变异、移动变异

# 2.6 遗传算法的一般步骤

1. 使用随机方法或者其它方法，产生一个有 N 个染色 体的初始群体 pop (1)，
2. 对群体中的每一个染色体$pop_i(t)$，计算其适应值
3. 若满足停止条件，则算法停止；否则，以概率 $p_si} =\frac{f_i}{\displaystyle\sum_{i=1}(M{f_i)} $, 从 pop (t) 中随机选择一些染色体构成一个新种群
4. 以概率$p_c$ 进行交叉产生一些新的染色体，得到一个新的群体 crossover (t+1)
5. 以一个较小的概率$p_m$ 使染色体的一个基因发生变异，形成 mutpop (t+1) t=t+1，成为一个新的群体 pop (t)=mutpop (t+1), 返回 2

# 3. 遗传算法改进算法

1. 双倍体遗传算法 (显隐形交叉)
2. 双种群遗传算法 (种群间交叉)

# 4. 群智能算法

# 4.1 粒子群优化算法 (Particle Swarm Optimization, PSO)

基本思想
每个粒子具有速度以及适应度
基本原理
在每次迭代过程中，粒子会根据粒子本身找到的最优解 (个体极值) 和群体中找到的最优解 (全局极值) 优化
算法定义
$x^i(k)=[x^i_1\cdots x^i_n] 粒子当前所在位置$
$p^i(k)=[p^i_1\cdots p^i_n] 粒子的适应度$
$v^i(k)=[v^i_1\cdots v^i_n] 粒子传播速度$
$p^g(k)=[p^g_1\cdots p^g_n] 群体最优位置$
$v^i_j(k+1)=\omega(k)v^i_j(k)+\phi_1rand(0,\alpha_1)(p^i_j(k)-x^i_j(k))+\phi_2rand(0,\alpha_2)(p^g_j(k)-x^i_j(k))$
$x^i_j(k+1)=x^i_j(k)+v^i_j(k+1)$

对于第一部分为粒子的速度
第二部分为粒子本身的思考，将现有位置与过去最优位置比较
第三部分为群体对粒子的影响，将现有位置与群体最优位置比较

算法参数
群体规模 M, 惯性权重，加速度，最大速度 VMAX，最大代数 GMAX

只有第一部分，粒子位置只与速度相关，只能搜索有限区域，难以找到最优解

没有第一部分，粒子速度无记忆性，仅由个体和群体位置决定

第二部分为 0, 社会模型，粒子位置由群体影响，容易陷入局部最优解

第三部分为 0, 认知模型，很难找到最优解

# 4.1.1 粒子群优化算法寻优阶段

1. 初始化阶段：初始化粒子群的位置和速度。每个粒子的位置表示一个潜在解，速度决定了粒子在搜索空间中的移动方向和速度。

2. 评估阶段：对每个粒子的位置进行评估，计算其对应解的适应度值。适应度值表示该位置对问题的优劣程度，通常根据问题的目标函数进行评估。

3. 个体最优更新阶段：根据个体历史最优值和当前位置的适应度值，更新粒子的个体最优位置。每个粒子会记录自身历史最优位置及其对应的适应度值。

4. 群体最优更新阶段：根据粒子群中所有粒子的个体最优位置，确定全局最优位置。即从所有个体最优位置中选择适应度最好的位置作为全局最优位置。

5. 速度和位置更新阶段：根据个体最优和全局最优位置，更新粒子的速度和位置。新的速度和位置将影响粒子在搜索空间中的移动方向和速度。

6. 终止条件判断阶段：根据预设的终止条件（例如达到最大迭代次数或满足一定的适应度要求），判断是否终止算法的迭代过程。

# 4.1.2 寻优准则

1. 适应度函数：确定问题的目标函数或评估标准，用于评估粒子的位置和解的优劣程度。

2. 个体最优准则：根据个体历史最优值和当前位置的适应度值，确定个体最优位置。通常通过比较适应度值的大小来进行判断。

3. 群体最优准则：根据粒子群中所有粒子的个体最优位置，确定全局最优位置。通常通过比较适应度值的大小来进行判断。

4. 终止条件：设定终止算法的条件，例如达到最大迭代次数、适应度达到一定阈值或算法运行时间超过预设时间等。

# 4.2 蚁群算法 (Ant Colony Optimization)

基本思想

信息素追踪：个体会以概率选择信息素强的路径

信息素释放：个体经过路径会释放信息素

蚁群模型:

$P^k_{xy}(t)$ 表示在 t 时刻蚂蚁 k 选择从元素 (城市) x 转移到元素 (城市) y 的概率，也称为随机比例规则

<font size=5>$P^k_{xy}(t)=\frac{|\tau_{xy}(t)|^\alpha|\eta_{xy}(t)|^\beta}{\sum|\tau_{xy}(t)|^\alpha|\eta_{xy}(t)|^\beta}$</font>
`

基本蚁群算法模型

1. 蚂蚁圈系统

单只蚂蚁信息素更新 <font size=5>$\Delta\tau^k_{xy}(t)=\frac{Q}{L_k}$</font>
其中 Q 为常数，$L_k$ 为蚂蚁在本轮循环走过的路程

2. 蚂蚁数量系统

<font size=5>$\Delta\tau^k_{xy}(t)=\frac{Q}{d_k}$</font>

3. 蚂蚁密度系统

<font size=5>$\Delta\tau^k_{xy}(t)=Q$</font>

其中蚂蚁圈系统性能最好，通常作为蚁群优化算法的基本模型
优点:

• 保证了残留信息素不至于无限累积；
• 如果路径没有被选中，那么上面的残留信息素会随时间的推移而逐渐减弱，这使算法能 “忘记” 不好的路径；
• 即使路径经常被访问也不至于因为$\Delta\tau^k_{xy}(t)$ 的累积，而产生$\Delta\tau^k_{xy}(t)\gg\eta_{xy}(t)$ 使期望值的作用无法体现；
• 充分体现了算法中全局范围内较短路径 (较好解) 的生存能力；
• 加强了信息正反馈性能；
• 提高了系统搜索收敛的速度。

算法参数

信息素启发因子$\alpha$

• 反映了蚁群在路径搜索中随机性因素作用的强度；
• $\alpha$ 值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱；
• 当$\alpha$ 过大时会使蚁群的搜索过早陷于局部最优

期望启发式因子$\beta$

• 反映了蚁群在路径搜索中先验性、确定性因素作用的强度；
• $\beta$ 值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大；
• 虽然搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中随机性减弱，易于陷入局部最优。

信息素挥发度$1-\rho$

• 当要处理的问题规模比较大时，会使那些从来未被搜索到的路径 (可行解) 上的信息量减小到接近于 0，因而降低了算法的全局搜索能力；
• 而且当$1-\rho$ 过大时，以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力；
• 反之，通过减小信息素挥发度$1-\rho$ 虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。

# 4.2.1 蚁群算法寻优阶段

1. 初始化阶段：为每只蚂蚁随机分配一个起始位置。蚂蚁在搜索空间中表示潜在解，起始位置可以是随机选择或根据问题的特定要求确定。

2. 路径选择阶段：蚂蚁根据信息素和启发式信息来选择移动的路径。信息素表示蚂蚁在路径上释放的信息，启发式信息则表示路径上的信息素浓度和启发式函数的值。

3. 解更新阶段：每只蚂蚁根据路径选择的结果更新自身的解。如果找到了更优的解，蚂蚁会更新其个体最优解。

4. 全局信息素更新阶段：在每次迭代的末尾，根据蚂蚁的路径和解质量更新全局信息素。通常，路径上经过的较短路径会释放更多的信息素。

5. 终止条件判断阶段：根据预设的终止条件（例如达到最大迭代次数或满足一定的解质量要求），判断是否终止算法的迭代过程。

# 4.2.2 寻优准则

1. 信息素：信息素是蚂蚁在路径上释放的化学物质，用于在搜索过程中进行信息传递和协作。信息素浓度通常与路径的质量和蚂蚁的选择有关。

2. 启发式信息：启发式信息是指路径上的附加信息，可以是基于问题特征的启发函数值。蚂蚁在路径选择时综合考虑信息素和启发式信息。

3. 解更新准则：蚂蚁根据路径选择的结果来更新自身的解。通常，较优的路径会对蚂蚁的解产生积极的影响。

4. 全局信息素更新准则：根据蚂蚁的路径和解质量，更新全局信息素。一般来说，路径质量较高的蚂蚁会释放更多的信息素，有助于加强较优路径的影响。

在多次迭代过程中，蚂蚁通过路径选择和信息素更新逐渐优化解，全局信息素的积累和更新促使蚂蚁群体在搜索空间中逐渐集中于较优的解。