《计算智能》课程笔记1——寻优算法

研一课程,做一个知识重点笔记。笔记分两部分,这个部分是李翠华老师上的前6章。

本课程主要涉及算法有:搜索,机器学习,遗传算法,群体智能,人工神经网络。

相关链接《计算智能》课程笔记2

课程主讲人:李翠华 教授,曲延云 教授

教材:《计算智能导论(第2版)》(世界著名计算机教材精选)南非 Andries.P.Engelbrecht 著

计算智能主要研究那些人比机器擅长的领域内的问题及其算法,机器学习是其重要的实现途径。

第1章 绪论

本课程将学习下列主要内容:

  1. 现代搜索技术,包括启发式搜索、梯度搜索、模拟退火搜索、博弈搜索、极小极大搜索以及α-β剪枝过程等;

  2. 机器学习,包括机器学习的种类、模型及算法,如贝叶斯(Bayes)学习、支持向量机(SVM)、人工神经网络(包括人脑的基本特征、前馈网络、学习规则、多层前馈网络的反向传播(BP)学习算法、AdaBoost学习算法、随机森林分类算法、深度学习(Deep
    learning)等);

  3. 模拟进化搜索与学习算法,包括生物进化过程、模拟进化原理与算法、模拟进化算法的典型执行策略(Geneticalgorithm,Evolutionstragies,Evolutionary programing)、模拟进化策略的改进途径、各种执行策略的比较和评注、模拟嫁接技术等;
  4. 群体智能算法,包括蚁群优化算法(Ant Colony Optimization,ACO)和粒子群优化算法(ParticleSwarm Optimization,PSO);
  5. 不确定性知识推理:滤波、平滑、预测、寻找最可能的序列等问题,并给出详细的推理方法介绍:HMM模型和Kalman滤波器,动态Bayes网络及近似推理算法——粒子滤波等。

第2章 问题求解的搜索

第3章 退火模拟算法(SA)

局部搜索算法(以爬山算法为代表)存在缺陷。最致命的是无法跳离局部最优“陷阱”,在高维情况下还存在“鞍陷阱”和“梯度消失”。

Metropolis算法

为了克服局部搜索的“陷阱”问题,1982年,Kirkpatirck提出模拟退火算法( Simulated Annealing Algorithm )。模拟退火算法模仿自然界固体退火的微观过程,将Metropolis准则引入到组合优化过程中来,得到了一种对Metropolis算法进行迭代的组合优化算法。

核心思想:模拟退火算法用Metropolis算法产生组合优化问题解的序列。并由Metropolis准则对应的转
移概率 $P$

确定是否接受从当前解 $i$ 到 新解 $j$ 的转移。

  • 式中 $t\in R^+$ 表示控制参数。开始让$ t $取较大的值,在进行足够多的转移后, 缓慢减小 $t$ 的值,如此重复直至满足某个停止准则时,算法终止。
  • 模拟退火算法依据Metropolis准则接受新解,除接受优化解外,还在一个限定范围内接受恶化解。
  • $f(x)​$ 表示目标函数,最小值为最优值。当新解 $j$ 优于当前解 $i​$ 时,$f(j) \le f(i)​$ ,则转移。若新解 $j​$ 劣于当前解 $i​$ 时,则根据概率转移,这个概率受到劣化程度 $f(i)-f(j)​$ 与控制参数 $t​$ 影响。
    • 开始时 $t$ 值较大,按照一定概率接受较差的劣化解,随着值 $t$ 的减小,接受劣化解的可能性降低,只大概率接受较好的劣化解;当 $t$ 值趋于零值时,就不再接受任何劣化解。这就使得算法有可能</font >跳出局部最优陷阱。
    • 在算法执行期间,随着控制参数 $t$ 值的减小,算法返回某个整体最优解得概率单调增大,返回某个非最优解的概率单调减小

image-20181024170919261

image-20181024170937420

伪代码与参数调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
%Procedure SIMULATED_ANNEALING
INITIALIZE (i0, t0, L0); % 初始化i0, t0, L0
k = 0;
i = i0;
while stop_criterion % 算法停止准则
%对每个tk产生Lk个解,这Lk个解构成了一条长为Lk的Mapkob链
for l=1 to Lk
GENERATE (j from Si); % 从当前解i的邻域Si中产生新解j
%以下 3 行 即 Metropolis 算法,共迭代了Lk 次
if f(j) <= f(i)
i = j
else if exp((f(i)-f(j))/ tk) >= random[0, 1)
i = j
k:=k+1;
CALCULATE_LENGTH (Lk); %重新计算Mapkob链长Lk
CALCULATE_CONTROL(tk); %重新计算控制参数值tk

那么我们如何重新计算Mapkob链长和控制参数呢?如何设定停止的条件和起始温度t0?

冷却表(cooling schedule) 是一组控制算法进程的参数,用以逼近模拟退火算法的渐进收敛性态,使算法在有限时间内执行迭 代过程后返回一个近似最优解。

冷却表是影响模拟退火算法实验性能的重要因素,其合理选取是算法应用的关键。

一个冷却表应当规定下述参数:

  1. 控制参数 $t$ 的初值 $t_0$
  2. 控制参数 $t$ 的衰减函数
  3. 控制参数 $t$ 的终值(停止准则)
  4. Mapkob 链长 $L_k​$

冷却进度表选取一般原则

  • 控制参数初值 $t_0$ 要足够大,才能使算法进程在合理时间里搜索尽可能大的解空间范围。
  • 控制参数终值 $t_f$ 通常由停止准则决定。合理的停止准则既要确保算法收敛于某一近似解,又要使最终解具有一定的质量。
  • Mapkob 链长 $L_k$ 在控制参数 $t_0$ 的衰减函数已选定 的前提下 , $L_k$ 应选得在控制参数的每一取值上都能恢复准平衡。
  • 在控制参数的衰减函数应使 $t_k$ 的衰减以小为宜。

总结

  • 模拟退火算法的目的是为了解决普通的梯度下降法导致的陷入局部最优解的问题。

  • SA从自然界中固体退火的微观过程中得到启发。虽可能效果并不是很好,但是思路是一个突破

  • 与梯度下降法不同的是,不单纯的只接受更好的解,而是按照概率接受劣化解。并随着控制参数的减小,逐步减少接受劣化解的可能性。当 $t$ 值趋于零值时,就不再接受任何劣化解。使得算法有可能跳出局部最优陷阱。

  • 如何设置控制参数t的变化和对于每个参数t所进行的解的搜索次数(Mapkob链长)是关键。

    起始温度和停止条件也影响着解的准确程度。

大型作业:利用模拟退火算法(SA)解决旅行商问题(TSP)

第4章 模拟进化与遗传算法

传统的局部搜索算法——爬山法,当目标函数具有多极值点时,由于其本身固有的局部优化性及不稳健等缺陷,而被广泛认为不适于全局优化问题的求解。

近二十年来,人们相继发展了许多求解全局优化问题的方法,一般可分为确定型非确定型(如随机搜索)算法。

和模拟退火算法(SA)一样,模拟进化算法也是从模仿自然界中的规律而发明的寻找全局最优解的随机搜索算法

遗传算法(genetic algorithms)演化策略(evolution strategies)进化程序(evolutionary programming)是几个典型的模拟进化算法,由 J.H.Holland 、 I.Recenberg 及 L.J.Fogel 等计算智能学者相继提出创立。 模拟进化算法一种仿生类算法。

仿生类算法,就其目前发展而言,可分为仿生过程算法与仿生结构算法两大类,前者以模拟进化算法为代表,后者以神经网络为典型。

遗传算法(Genetic Algorithm,简称GA)是通过模拟生物进化过程来完成优化搜索的仿生类算法。

模拟进化类算法介绍

算法框架

考虑全局优化问题:

则$(p)$的多个可行解的一个集合可称之为一个种群(population),种群中的每一元素(可行解)可称之为是一个个体(individual),种群中个体的数目称之为此种群的规模

于是,求解问题$(p)$的一个不变规模(例如设为$N$)的模拟进化算法可抽象地描述如下:

  1. 随机确定初始种群:
  2. 计算当前种群中每一个体$X_i(K)$的适应性$(i=1,2,…,N)$ ,并依据适应性指定其相应个体的繁殖概率;依据所指定的繁殖概率,通过遗传机制(杂交、变异)产生适量的新一代种群的候选种群,最后依据某种选择规则,从候选种中确定新一代种群$X(K+1)$
  3. 检验当前种群是否产生满意解或已达到预设的进化时限,如已满足,停止;否则令$K:=K+1$ ,转步2

模拟进化与传统确定性算法的区别

  1. 模拟进化算法的作用对象是由多个可行解组成的集合,而非单个可行解;
  2. 模拟进化算法只利用函数的适应值信息,而无需应用梯度等其它辅助信息;
  3. 模拟进化算法利用概率机制而非确定性迭代过程描述。正是这些有别于确定型方法的特征决定了模拟进化算法应用的广泛性、描述的简单性、本质上的并行性和良好的鲁棒性。

模拟进化算法的典型执行策略

依历史发展与不同的应用侧重,模拟进化算法通常分为遗传算法演化策略进化程序三个典型的执行策略(也可视为三个不同的发展方向)。

遗传算法

遗传算法是目前研究得最为广泛的一类模拟进化算法。

基本策略

假定考虑全局优化问题$(p)$ 。遗传算法基于以下两条基本策略求解问题:

  1. 对于给定的目标函数$F:\Omega \subset R^n→R^1$,它使用FF的任一适应性(fitness)函数(换言之,一个值域非负、与$F$ 有相同极值点的函数);
  2. 代替直接作用于优化变量$X$,它作用于$X$的可称之为染色体(chromosome)的某种编码(换言之,$X$的某种离散化近似表示。例如,长度为$L$且取值于某种字母表的数串)。

算法框架

例如:$J(x)=exp(F(x))$ 是FF的一适应性函数,而对任何$x\in \Omega$ 以它的诸坐标分量的固定长度的二进制近似依次排列,则给出$X$的一个编码。

给定$F$的任一适应性函数$J$和固定长度$L$、取值于某个字母表的数串染色体编码,求解问题$(p)$的标准遗传算法如下:

  1. 初始化:
    1. 确定种群规模$N$、杂交概率$P_c$、变异概率$X_i(0)X_i(0)P_m$及终止进化准则;
    2. 从$\Omega$中随机选取$N$个个体$X_i(0)$组成初始种群$X(0)=\{X_1(0),…,X_N(0)\}$ ,设$X_i(0)$的染色体编码为$Y_i(0)$,并记$Y(0)=\{Y_1(0),…,Y_N(0)\}$;
    3. 计算$Y_i(0)$的适应性值$J(Y_i(0))$;
    4. 置$k = 0$。
  2. 种群进化:
    1. 执行$M$步如下操作,一般取$M\ge \frac{N}{2}$:
      1. 对每一$Y_i(k)$依据其适应性赋一繁殖概率$P_i(k)$;
      2. 以概率$P_i(k) (1\le i\le n)$从$Y(k)$中随机选取两个个体,分别记作$Y_{i1}(k),Y_{i2}(k)$
      3. 以概率$P_c$ 对$Y_{i1}(k),Y_{i2}(k)$进行杂交,产生两个中间个体$s’_1,s’_2$;
      4. 以概率$P_m$对中间个体$s’_1,s’_2$进行变异,产生两个新个体$s_1,s_2$。
    2. 计算由第2.1步所产生的$2M$个新个体的适应性,对这$2M$新个体连同$Y(k)$由某种选择规则确定$N$个个体组成新一代种群$Y(k+1)=\{Y_1(k+1),…,Y_N(k+1)\}$
  3. 检验终止判据:如果$Y(k+1)$满足预先设定的停机准则,则终止演化,并输出最优解;否则,置$k = k+1$,返回第2步。

演化算法

相比于遗传算法,演化算法不需要编码。

进化程序(遗传编程)

MIT有一篇很著名的文章讲述进化程序,进化程序的设计思想类似于演化算法。只利用变异算子,没有引入杂交机制

模拟嫁接技术

此节介绍一种带有嫁接和剪接操作的遗传算法,用以求解具有大量结点的度约束最小生成树(Degree-Constrained Minimum Spanning Tree)问题。

度约束最小生成树问题(DCMST)

最小生成树(MST)一般用算法Prim和Kruskal算法求解。

在实际应用中,通常面临的是需要带有某种约束的MST,如二次最小生成树问题、度约束最小生成树问题和概率最小生成树问题等。对于该类问题的求解,目前还不存在多项式时间复杂度的算法,被证明是NP-完全的。

问题描述

设连通图$G=(V,E,W)$ ,$V=\{v_1,v_2,…,v_n\}$ 表示图的顶点集合,$E=\{e_1,e_2,…,e_m\}$ 是边的有限集合,$W=\{w_{ij}\}_{n×n}$ 表示边的权重矩阵,规定顶点的度约束为$b_i$(给定的约束值,$i=1,2,…,n$ ),因此度约束最小生成树问题(DCMST)的求解可表述为:

$|S|$表示集合$S$($V$的子集合)的结点个数。

设 $T$ 为图 $ G $ 的所有满足度约束的生成树的集合,对DCMST问题求解就是寻找 $G$ 的一棵满足度约束的最小生成树。约束式1为度限制,约束式2和3保证了所得到的是一棵生成树,不形成圈(无环路)。

模拟嫁接技术

收益和代价

对一棵生成树T1,若将某结点的一条分枝移至另一结点作为其一条分枝后产生的生成树为T2,考察分枝移动前后生成树的边长和的变化,则定义收益(gain)和代价(cost)分别为:

实际上,$cost = - gain $

嫁接

将生成树非考察结点且具有某种优良特性的分枝(嫁接枝)接入到非完全生成树的待考察结点中,以形成更好生成树个体(这里指收益大于0)的过程称为嫁接。

剪接

将生成树个体考察结点的某一分枝(剪接枝)接入到非完全生成树中另一位置,以形成可行个体或更好个体的过程称为剪接。

冲突及冲突检测

在对消除不满足约束情形进行剪接或对具有较差属性的分枝进行剪接操作的同时,若引起新的不满足约束的情形称为冲突。

在剪接过程中引起了冲突,就称找出这一冲突现象的过程为冲突检测 。

GPOGA算法

在基本遗传算法体系的基础上,结合嫁接和剪接算子作用,给出基于嫁接和剪接算子的遗传算法
(A Genetic Algorithm with Grafting and Pruning Operators, 简称GPOGA)。

伪代码如下:

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
算法4 (GPOGA). 
Input:与所求DCMST问题有关的数据(结点数,完全图边长等),遗传算法基本控制参数.
Output:生成的最好解个体及有关计算数据.
Begin
随机初始化种群P(0),t=0;
计算P(0)中个体的适应值并按适应值排序;
while 计算代数 t ≤ maxgen do
j=0;
while 新产生个体j<N do
根据个体的适应值随机从当代种群中选择两个父个体,设为oldindi1和oldindi2;
执行杂交操作CrossOver(oldindi1,oldindi2),将产生的新个体保存在newpop[j],newpop[j+1]中;
执行交换变异操作SwapMutation(newpop[j])、SwapMutation(newpop[j+1]);将产生的两个新 个体
复制到临时种群变量数组temp1[j]和temp1[j+1]中;
执行嫁接操作Grafting(newpop[j]), Grafting (newpop[j+1]);
执行剪接操作pruning(newpop[j]), pruning (newpop[j+1]);
计算并评价temp1[j]、temp1[j+1]、newpop[j]、newpop[j+1]、oldindi1及oldindi2的目标值,选
择两个较好的个体复制到newpop[j]及newpop[j+1]中;
j=j+2;
end while;
计算新种群newpop 的目标值、适应值并排序,同时以oldpop中最好的个体代替newpop中最差的
个体;
将newpop种群中个体复制到oldpop中,计算其目标值、适应值并排序;
t=t+1;
end while;
记录及输出结果.
End

结论

度约束最小生成树(DCMST)问题是一类难解的NP-hard问题,目前尚未有可靠、有效的解决方法。通过对现有方法存在的问题和缺陷进行分析,借鉴花草果树的人工种植和培育技术,设计的基于嫁接和剪接算子的遗传算法(GPOGA),理论分析和实验数据都为算法的正确性和有效性提供了依据。
GPOGA的三类算子在计算过程中互为补充,协同完成优化搜索过程,从而使算法的性能优越,鲁棒性更好。

第5章 群体智能

群智能理论研究领域有两种主要的算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Optimization, PSO)。前者是对蚂蚁群落食物采集过程的模拟,已成功应用于许多离散优化问题。粒子群算法也是起源于对简单社会系统的模拟,最初是模拟鸟群觅食的过程,但后来发现它是一种很好的优化工具。

蚁群优化算法(ACO)

蚂蚁优化算法受蚂蚁取食行为中的通信机制启发而得来。经过大量的观察研究发现,蚂蚁个体之间可以通过分泌信息素(pheromone)来传递信息。蚂蚁在行动的过程中,会在经过的路径上留下信息素,后面的蚂蚁通过感知这种物质的浓度来选择自己的路径。这样,由大量蚂蚁组成的蚁群集体行为就表现出了一种信息正反馈的现象,信息素随时间挥发,在较短的路径上浓度较大,因而蚂蚁总是可以找到更短的路径取食。

粒子群优化算法(PSO)

粒子群优化算法(PSO)是由James Kennedy(肯尼迪)博士和R.C. Eberhart博士于1995年提出的。该算法源于对鸟群、鱼群觅食行为的模拟。PSO 算法简单易实现,不需要调整很多参数,主要应用有神经网络的训练、函数的优化等。

在PSO中,首先初始化一群随机粒子(随机解),然后通过迭代寻找最优解。在每一次迭代中,粒子通过跟踪两个极值来更新自己的速度和位置:

  1. 第一个极值是粒子本身所找到的最优解,这个解叫做个体极值

  2. 另一个极值是整个种群目前找到的最优解,这个极值是全局极值;

    另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在该邻居中的极值就是局部极值。

实现

算法公式

参数说明

  • $c_1$和$c2$分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长的一个常量,若太小,则粒子可能远离目标区域;若太大,则会导致突然向目标区域飞去,或飞过目标区域。合适的$c_1$和$c_2$可以加快收敛且不易陷入局部最优。

  • 为防止粒子远离搜索空间,粒子的每一维速度$V_{id}$都会被限定在$[−V_dmax,V_dmax]$之间,$[−V_dmax,V_dmax]$太大,粒子将飞离最好解,太小将会陷入局部最优。

    假设将搜索空间的第$d$维定义为区间$[−X_dmax,X_dmax]$,则通常$V_dmax=k·X_dmax,\quad k=0.2$,

基本流程

  1. 初始化

    初始搜索点的位置$Xi(0)$及其速度$Vi(0)$通常是在允许的范围内随机产生的,每个粒子的pbest坐标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将gbest设置为该最好粒子的当前位置。

  2. 评价每一个粒子

    计算粒子的适应值,如果好于该粒子当前的个体极值,则将pbest设置为该粒子的位置,且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值,则将gbest设置为该粒子的位置,记录该粒子的序号,且更新全局极值。

  3. 粒子的更新

    用更新方程对每一个粒子的速度和位置进行更新。

  4. 检验是否符合结束条件

    如果当前的迭代次数达到了预先设定的最大次数(或达到最小误差要求),则停止迭代,输出最优解,否则转到第2步。

第6章 人工神经网络