人工智能 第二版 课件 第7、8章 对抗搜索、高级搜索

第七章对抗搜索棋类人机大战简史50年代麦卡锡提出α-β剪枝算法1962年西洋跳棋程序战胜美国的州冠军1996年深蓝首次挑战卡斯帕罗夫失败1997年深蓝再战克斯帕罗夫获胜2006年中国象棋程序战胜柳大华等5位棋手2016年AlphaGo战胜李世石2017年AlphaGo战胜柯洁棋类人机大战简史50年代麦卡锡提出α-β剪枝算法1962年西洋跳棋程序战胜美国的州冠军1996年深蓝首次挑战卡斯帕罗夫失败1997年深蓝再战克斯帕罗夫获胜2006年中国象棋程序战胜柳大华等5位棋手2016年AlphaGo战胜李世石2017年AlphaGo战胜柯洁2.1可以穷举吗？从分钱币游戏说起（7,1）（6,1,1）（5,2,1）（4,3,1）（5,1,1,1）（4,2,1,1）（3,2,2,1）（3,3,1,1）（4,1,1,1,1）（3,2,1,1,1）（2,2,2,1,1）（3,1,1,1,1,1）（2,2,1,1,1,1）（2,1,1,1,1,1,1）甲方获胜（8）（6,2）（5,3）（5,2,1）（4,2,2）（4,3,1）（3,3,2）甲方走棋乙方走棋可以穷举吗？以中国象棋为例总状态数约为10150假设1毫微秒走一步，约需10134年宇宙年龄：1.38*1010年如果一个原子存储一个状态，需要10100个地球结论：不可能穷举小结对于象棋、围棋这类的棋类问题，不可能依靠穷举的办法解决。2.2极小-极大模型人类下棋的思考过程向前看若干步从最不利的情景中选择最有利的走法90-33-3-3-2016-30316011极大极小ab05-333-3022-30-2304112689-302极小-极大模型限定深度就可以穷举吗？深蓝每下一步棋，搜索12步如果搜索12步内的所有可能，需要17年小结极小-极大模型模仿了人类下棋的思考过程有限深度内的穷举也行不通12极小-极大模型存在的问题人如何处理这个问题呢？只在少数可能的走步范围内考虑140-33-3-3-2016-30316011极大极小05-333-3022-30-2304112689-302α-β剪枝算法极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝486110035-33-3022-30-2329-300-3033000116611如何估值？总结专家知识进行估值α-β剪枝效果如何？国际象棋、中国象棋软件的系统框架-205-333-302-235-5520151-305-3323-30-1-201451-1-13-32-5MaxMin00-333000522220511-311-5-5-512222133-333-1-100034444-1-1-1-1-1

剪枝

剪枝几点注意α-β剪枝只是得到一步结果注意比较的时候要跟祖先比估值的准确性要求比较高搜索深度越深效果越好小结α-β剪枝算法利用已有的搜索结果进行剪枝剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝一次剪枝过程只得到一次走步为什么-剪枝方法在围棋上失效？是因为状态多吗？状态多不是本质原因-剪枝方法存在的问题依赖于局面评估的准确性局面评估问题大量专家知识知识的统一性问题人工整理逻辑思维与形象思维蒙特卡洛方法二十世纪40年代中期S.M.乌拉姆和J.冯·诺伊曼提出的一种随机模拟方法多重积分矩阵求逆线性方程组求解积分方程求解偏微分方程求解随机性问题模拟蒲丰投针问题(x,α)决定了针的位置x0=(l/2)·sinα针与直线的相交条件：x≤(l/2)·sinα其中：x∈[0,d/2],α∈[0,π]dlxαlx0αd/2πα0x黄颜色部分与长方形面积之比即为针与直线相交的概率：

黄颜色面积

其中:n为掷针次数m为相交次数

棋局的蒙特卡洛评估从当前局面的所有可落子点中随机选择一个点落子重复以上过程直到胜负可判断为止经多次模拟后，选择胜率最大的点落子蒙特卡洛树搜索（MCTS:MonteCarlo

Tree

Search）基本思想：将可能出现的状态转移过程用状态树表示从初始状态开始重复抽样，逐步扩展树中的节点父节点可以利用子节点的模拟结果，提高了效率在搜索过程中可以随时得到行为的评价蒙特卡洛树搜索过程选择扩展模拟回传随机模拟bacbcrrbac收益选择策略两方面的因素对尚未充分了解的节点的探索对当前具有较大希望节点的利用选择策略：多臂老虎机模型1952年Robbins提出的一个统计决策模型多臂老虎机多臂老虎机拥有k个拉杆，拉动每个拉杆所获得的收益遵循一定的概率且互不相关，如何找到一个策略，使得拉动拉杆获得的收益最大化。信心上限算法（UCB：UpperConfidenceBound）functionUCB1foreach拉杆j:

访问该拉杆并记录收益

endfor

while尚未达到访问次数限制do:

计算每个拉杆的UCB1信心上界Ij

访问信心上界最大的手臂

endwhile32信心上限的计算其中：

是拉杆j所获得回报的均值n是到当前这一时刻为止所访问的总次数

是拉杆j到目前为止所访问的次数上式考虑了“利用”和“探索”间的平衡33信心上限树算法UCT将UCB1算法应用于蒙特卡洛树搜索中，用于选择可落子点节点不是随机选择，而是根据UCB1选择信心上限值最大的节点实际计算UCB1时，加一个参数c进行调节：34信心上限树算法示例△△△△△△△△△△△信心上限树算法（UCT）functionUctSearch(s0)

以状态s0创建根节点v0;while尚未用完计算时长do:

vl=TreePolicy(v0);

△=DefaultPolicy(s(vl));

Backup(vl，△);endwhile

returna(BestChild(v0，0));36信心上限树算法37UCT算法示例节点：获胜次数/模拟总次数

获胜次数是从本节点角度说的假设c=0，即3/56/103/52/30/11/40/11/10/10/11/11/13/56/103/52/30/11/40/11/10/10/11/11/10/06/103/52/30/11/40/11/10/10/11/11/10/07/113/63/40/11/40/11/20/10/11/11/11/1重复多次后选取胜率最大者为走步蒙特卡洛树搜索的效果2006年将蒙特卡洛树搜索算法首次应用于计算机围棋中可以达到业余4、5段的水平将计算机围棋引向了正确的发展方向小结蒙特卡洛方法一类基于概率方法的统称蒙特卡洛树搜索四个过程：选择，扩展，模拟，回传多臂老虎机模型每次选择信心上限最大的信心上限树算法将信心上限算法用于蒙特卡洛树搜索AlphaGo是如何下棋的蒙特卡洛树搜索存在的问题生成所有子节点模拟具有盲目性AlphaGo将神经网络与蒙特卡洛树搜索结合在一起缩小了搜索范围提高了模拟水平AlphaGo用的两类网络策略网络策略网络由一个神经网络构成输入：当前棋局48个通道，每个通道大小为19*19输出：棋盘上每个点的行棋概率概率越大越是好的行棋点策略网络输入执子颜色：3个通道，分别为执子方、对手方、空点位置壹平面：1个通道，全部填入1零平面：1个通道，全部填入0明智度：1个通道，合法落子点且不会填补本方眼位，填入1，否则为0回合数：8个通道，记录一个落子距离现在的回合数第n个通道记录到当前n个回合的落子气数：8个通道，当前落子棋链的气数动作后气数：8个通道，落子之后剩余气数吃子数：8个通道，落子后吃掉对方棋子数自劫争数：8个通道，落子后乙方有多少子会陷入劫争（可能会被提掉）征子提子：1个通道，这个子是否会被征子提掉引征：1个通道，这个子是否起到引征的作用当前执子方：1个通道，当前执子为黑棋全部填1，否则全部填0该通道只用于估值网络，策略网络不使用策略网络输入19*19*48192个5×5卷积核，步长为1，填充为2ReLU…192个3×3卷积核，步长为1，填充为1ReLU192个3×3卷积核，步长为1，填充为1ReLU1个3×3卷积核，步长为1，填充为1softmax输出19*19第一层第二层第十二层第十三层…策略网络的目标：像人类那样下棋

估值网络估值网络由一个神经网络构成输入：当前棋局49个通道，每个通道大小为19*19比策略网络多一个通道输出：当前棋局的收益收益的取值范围为[-1,1]估值网络输入19*19*49192个5×5卷积核，步长为1，填充为2ReLU…192个3×3卷积核，步长为1，填充为1ReLU第一层第二层到第十第十四层第十五层第十六层

三层完全一样……1个1×1卷积核，步长为1。ReLUReLU256个全连接tanh一个全连接输出估值网络

与蒙特卡洛树搜索融合MCTS中的选择原则收益好的节点模拟次数少的节点AlphaGo增加了第三个原则落子概率高的节点充分利用两个网络

回传过程v-v+v-vabcdd的收益回传到其祖先节点，回传过程中要注意正负号的变化，一方的正收益对于另一方就是负的。AlphaGo的MCTS过程每个节点记录的信息总收益行棋到该节点的概率被选择次数abcrabcrdefv每个节点记录总收益、行棋到该节点的概率和被选择次数。a、b、c依次被选中，最终被选中的节点为c生成c的子节点d、e、f，策略网络计算出从c到这些节点的概率，并设置总收益为0，选中次数为0。从根节点开始，选Q+u最大的子节点1，选择2，生成abcrdefv-v+v-vv值依次上传到c的祖先节点，更新这些节点的总收益和选择次数（选择次数+1），注意正负号的切换。abcrdefv对c进行模拟，模拟结果与c的估值（由估值网络计算得到）加权平均作为c的收益v。4，回传3，模拟AlphaGo如何确定走步？根节点子节点中被选择次数最多的节点作为最终的走步r小结AlphaGo的基本框架是MCTS在MCTS中引入了策略网络和估值网络收益计算综合了估值网络的输出和模拟结果在选择过程中，考虑了行棋概率利用推演策略网络进行模拟限定了MCTS的最大深度限定了MCTS的总模拟次数围棋中的深度强化学习方法从宠物训练说起围棋中的深度强化学习方法强化学习学习“做什么才能使得收益最大化”的方法学习者不会被告知如何做，必须自己通过尝试发现哪些动作会产生最大的收益监督学习与强化学习两个特征：试错和延迟收益深度强化学习用深度学习（神经网络）方法实现的强化学习深度强化学习的关键问题如何获得指示信号监督学习：情景与标注一一对应强化学习：将收益转化为“标注”不能获得所有情况下既正确又有代表性的示例手段：将深度强化学习问题转化为神经网络训练问题不同的转换方法构成了不同的深度学习方法关键是损失函数的定义围棋中的深度强化学习方法通过自己博弈训练策略网络三种实现方法基于策略梯度的强化学习基于价值评估的强化学习基于演员-评价方法的强化学习1，基于策略梯度的强化学习

ssaa处落子基于策略梯度的强化学习流程当前版策略网络围棋系统当前版策略网络围棋系统乙方甲方甲乙双方对弈产生的数据训练策略网络更新版策略网络围棋系统当前版策略网络围棋系统对弈对弈

更新版策略网络代替当前版策略网络YN1，基于策略梯度的强化学习注意点在强化学习过程中，每个样本只使用一次基于策略梯度的强化学习方法学到的是在每个可落子点行棋的获胜概率（监督学习策略网络学到的是在某个可落子点行棋的概率）2，基于价值评估的强化学习价值评估网络对一个行棋点的价值，也就是收益进行评估输入：当前棋局和行棋点输出：取值在-1、1之间的估值策略网络类似2，基于价值评估的强化学习

3，基于演员-评价方法的强化学习3，基于演员-评价方法的强化学习策略网络评估结果对弈结果

演员评价（棋手）（教练）3，基于演员-评价方法的强化学习哪些是重要的？锦上添花与雪里送炭一着不慎，满盘皆输3，基于演员-评价方法的强化学习收益增量评价一步棋的好坏V(s)为棋局s的预期收益，取值范围为[-1,1]Q(s,a)为在a处行棋后的收益，取值范围为[-1,1]A为收益增量，取值范围为[-2,2]A越大越说明走了一步妙招，越小越说明走了一步败招收益增量的计算R为胜负值，胜为1，负为-1

3，基于演员-评价方法的强化学习

小结深度强化学习，根据任务找到合适的指示信号损失函数体现了学习的内容基于策略梯度的强化，通过每局棋的胜负指导学习，学习到的是每个落子点获胜的概率基于价值评估的强化学习，通过每局棋的胜负指导学习，学习到的是每个落子点获取最大收益的概率基于演员-评价的强化学习，强调的是重要行棋点的学习，通过收益增量对走法的重要性进行评价，学习到的是每个落子点获得最大收益增量的概率AlphaGoZero是如何自学成才的AlphaGoZero是AlphaGo的升级版实现了从零学习不再使用人类棋手的数据不再使用人工特征作为输入利用强化学习从零学习训练3天后，战胜AlphaGoLee训练40天后，战胜AlphaGoMasterAlphaGoZero的网络结构将策略网络、估值网络合并为一个“双输出”网络输入：17个通道16个通道：记录到目前为止的八个棋局，每个棋局两个通道，分别记录黑棋、白棋位置1个通道：当前行棋方为黑棋时全部填1，白棋时全部填0策略网络的输出为19×19+1多了一个“放弃”行为估值网络的输出为当前棋局的估值，取值范围为[-1,1]256个3×3卷积核，步长为1，填充为1ReLU批量归一化输入19*19*17256个3×3卷积核，步长为1，填充为1ReLU256个3×3卷积核，步长为1，填充为1ReLU+19个残差模块（20版本）或39个残差模块（40版本）2个1×1卷积核，步长为1。ReLU1个1×1卷积核，步长为1。ReLU全连接19×19+1(棋盘+放弃)输出棋盘上每个位置的行棋概率和放弃行棋的概率。softmax全连接256个神经元ReLU全连接1个神经元tanh当前棋局的评估值估值网络输出策略网络输出批量归一化批量归一化批量归一化批量归一化每个批量完成之后，对卷积层的输出做一次均值为0、方差为1的归一化，防止数据漂移

AlphaGoZero中的MCTS

AlphaGoZero

回传过程v-v+v-vabcdd的收益回传到其祖先节点，回传过程中要注意正负号的变化，一方的正收益对于另一方就是负的。abcrabcrdefv每个节点记录总收益、行棋到该节点的概率和被选择次数。a、b、c依次被选中，最终被选中的节点为c生成c的子节点d、e、f，策略网络计算出从c到这些节点的概率，并设置总收益为0，选中次数为0。从根节点开始，选Q+u最大的子节点1，选择2，生成abcrdefv-v+v-vv值依次上传到c的祖先节点，更新这些节点的总收益和选择次数（选择次数+1），注意正负号的切换。abcrdefv用估值网络的输出代替模拟结果，作为c的收益v。4，回传3，模拟AlphaGoZero中的深度强化学习将MCTS结合到深度强化学习中策略网络自我对弈产生的数据训练策略网络更新后的策略网络AlphaGo的强化学习策略-估值网络MCTS自我对弈产生的数据训练策略-估值网络更新后的策略-估值网络AlphaGoZero的强化学习

s(a,7)(b,20)(c,13)

引入多样性

探索的合理性引入噪声会引起“不良反应”吗MCTS的“纠错”能力

当前版策略-估值网络蒙特卡洛树搜索当前版策略-估值网络蒙特卡洛树搜索乙方甲方甲乙双方对弈产生的数据训练策略-估值网络更新版策略-估值网络蒙特卡洛树搜索当前版策略-估值网络蒙特卡洛树搜索对弈对弈

用更新版策略-估值网络代替当前版YNAlphaGoZero的强化学习过程硬件构成早期的AlphaGo：176个GPUAlphaGoLee：48个TPU+多台服务器AlphaGoZero：4个TPU+一台服务器训练3天后，可以战胜AlphaGoLee训练40天后，可以战胜AlphaGoMaster小结AlphaGoZero从零学习不再使用人类棋手的数据不再使用人类提供的特征“放弃”也是通过学习得到将策略网络和估值网络融合为一个网络在MCTS中舍弃了模拟过程，用估值结果代替将MCTS结合到深度强化学习中总结计算机下棋属于博弈问题双人一人一步双方信息完备零和分钱币问题极小-极大模型α-β剪枝算法蒙特卡洛树搜索AlphaGo原理MCTS+深度学习深度强化学习AlphaGoZero原理深度强化学习+MCTS实现从零学习第八章高级搜索8.1什么是组合优化问题例：旅行商问题（TSP）

一个商人去n个城市卖货，从所在城市出发，每个城市去一次且仅去一次，并最后回到出发城市。问如何安排才能使得商人走的路径最短。路径存在不同的组合方法，如何得到最短路径呢？出发组合优化问题例：0-1背包问题给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。货物存在不同的组合方法，如何得到选取的总价值最高呢？组合优化问题优化问题

设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件。则优化问题可以表示为求解满足g(x)的f(x)最小值问题。即：组合优化问题

如果在定义域D上，满足约束条件g(x)的解的总数是有限的，则优化问题称为组合优化问题。

组合优化问题的实际意义以旅行商问题为例交通运输飞机航线的安排快递员送快递校车的行驶路线印刷电路板打孔组合优化问题难在哪里旅行商问题可能的行走路线为n！个

假设每秒钟产生100亿个路线n10203040100n!36288002.43×10182.65×10328.16×10479.33×10157时间0.36毫秒7.7年8.4×1014年2.6×1030年3.0×10140年求解思路：引入随机因素求解满意解最优解与满意解引入随机因素本篇讲解如何用随机方法求解组合优化问题8.2局部搜索算法爬山法局部搜索算法核心思想邻域内找一个最优的结果，接受它，再以此为新的起点，重复这个过程。组合优化问题：邻域？rrrrrr邻域的概念对解S经过一些简单变换后，得到的另一个解称作解S的邻居，解S所有邻居的集合称作解S的邻域。邻域举例皇后问题S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。如四皇后问题的一个解：S=(2,4,1,3)

Q

QQ

Q

邻域举例皇后问题

任意交换两个皇后的位置获得一个解的邻居，

则（2,4,1,3）的所有邻居，也就是邻域为：{(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)}邻域举例旅行商问题常规交换法邻域举例旅行商问题x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1邻域举例旅行商问题逆序交换法邻域举例旅行商问题x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1局部搜索算法1，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)；2，如果P不为空，则3，Begin4，

选择P的一个子集P'，xn为P'中的最优解5，

如果f(xn)<f(xb)，则xb

＝xn，P=N(xb)，转2；6，

否则P=P–P'，转2。7，End8，输出计算结果9，结束局部搜索举例5城市旅行商问题假设初始解为x0=(A,B,C,D,E)，通过常规交换法获得邻居。●●●●●ABCDE71361071010965出发城市5城市旅行商问题指标函数：路径长度初始解：x0=(A,B,C,D,E)当前最好结果：f(xb)=f(x0)=7+7+5+6+13=38邻域：P={(a,c,b,d,e),(a,d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}子集大小：每次从邻域中取3个解作为P'P={(a,c,b,d,e),(a,d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}当前最好结果：xb=(A,B,C,D,E)f(xb)=38第一次循环P'={(a,c,b,d,e),(a,d,c,b,e),(a,e,c,d,b)}f(P')={42,45,44}f(xn)=42由于f(xn)>f(xb)，所以保持当前最好结果。P=P–P'={(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}P={(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}当前最好结果：xb=(A,B,C,D,E)f(xb)=38第二次循环P'={(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}f(P')={44,34,39}f(xn)=34由于f(xn)<f(xb)，所以：xb=(a,b,e,d,c)，f(xb)=34P={(a,e,b,d,c),(a,d,e,b,c),(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}P={(a,e,b,d,c),(a,d,e,b,c),(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}当前最好结果：xb=(a,b,e,d,c)f(xb)=34第三次循环P'={(a,e,b,d,c),(a,d,e,b,c),(a,c,e,d,b)}f(P')={44,39,38}f(xn)=38由于f(xn)>f(xb)，所以保持当前最好结果P=P–P'={(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}P={(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}当前最好结果：xb=(a,b,e,d,c)f(xb)=34第四次循环P'={(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}f(P')={38,38,41}f(xn)=38由于f(xn)>f(xb)，所以保持当前最好结果P=P–P'={}P={}当前最好结果：xb=(a,b,e,d,c)f(xb)=34由于P为空，算法结束，得到结果：xb=(a,b,e,d,c)f(xb)=34局部搜索应用：百万皇后问题皇后问题当皇后数增加到一百万个时，能否求解呢？

Q

QQ

Q

百万皇后问题转化为最优化问题

指标函数：棋盘上皇后的冲突数A与D相互冲突，C与B相互冲突

最小化问题：冲突数最小ACBD百万皇后问题表示S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。如四皇后问题的一个解：S=(2,4,1,3)

Q

QQ

Q

皇后搜索算法1，随机地将n个皇后分布在棋盘上，使得棋盘的每行、每列只有一个

皇后；2，计算皇后间的冲突数c；3，如果冲突数c等于0，则转（7）4，任选两个皇后交换他们在序列中的位置；5，如果交换后的冲突数c减少，则接受这次交换，更新冲突数c，

转3；6，如果陷入了局部极小，既交换了所有的皇后后，冲突数仍然不能

下降，则转1；7，输出结果8，结束。8.3局部搜索算法存在的问题1，局部最优问题

ABC

如何按概率接受一个解呢？设xi的接受概率为P(xi)，当random(0,1)<P(xi)时接受xi例如：假设P(xi)=0.6010.20.40.60.80.60.48.3局部搜索算法存在的问题2，步长问题

解决思路变步长8.3局部搜索算法存在的问题3，起始点问题

AB全局最大值局部最大值解决思路随机产生多个起始点从多次运行结果中选择一个最好的结果综合求解面对局部搜索算法存在的问题，综合求解按照概率接受解概率如何选取？变步长方法如何变步长？多次运行方法模拟退火算法8.4退火过程退火现象

退火过程升温：随着温度的不断上升，粒子逐渐脱离开其平衡位置，变得越来越自由，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。退火过程退火：随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。粒子不同的排列结构，对应着不同的内能水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0度（绝对温度）时，系统的内能将趋于最小值。奇怪的杯子退火过程如果以粒子的排列或者相应的内能来表达固体所处的状态，在温度T下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于内量较低的状态，另一方面，热运动又妨碍了系统准确落入低能状态。退火过程Metropolis准则从状态i转换为状态j的转换准则：

如果E(j)≤E(i)，则状态转换被接受；

如果E(j)＞E(i)，则状态转移被接受的概率为：其中E(i)、E(j)分别表示状态i、j下的内能，T是绝对温度，K＞0是波尔兹曼常数。

退火过程

退火过程分析同一温度下两个内能不同的状态高温下的情况低温下的情况当温度缓慢下降时的情况1，同一温度下两个内能不同的状态假设两个状态的内能E(i)＜E(j)：由于E(i)＜E(j)所以该项小于1

结论：在任何温度T下，系统处于低内能的状态的概率大于处于高内能的状态的概率2，高温下的情况

其中|S|表示系统所有可能的状态数

结论：当温度趋近于无穷大时，系统处于各个状态的概率相等，处于平均分布，与所处状态的内能无关。Sm表示系统最小内能状态的集合，Em表示系统的最小内能3，低温下的情况

结论：当温度趋近于绝对0度时，系统以等概率趋近于几个内能最小的状态之一，而系统处于其他状态的概率为0。也就是说系统达到内能最小状态的概率为1。4，温度缓慢下降时的情况

高能状态低能状态

退火过程总结在温度不变时，处于低内能状态的概率大于处于高内能状态的概率当温度趋于无穷大时，系统等概率处于各个状态当温度趋于绝对0度时，系统达到内能最小状态的概率为1当温度缓慢下降时，系统处于低能状态的概率随着温度的下降单调上升，而系统处于高能状态的概率随着温度的下降单调下降。退火过程的三个条件初始温度必须足够高；在每个温度下状态的交换必须足够充分；温度T的下降必须足够缓慢。退火过程的两点启示

8.5模拟退火算法回顾：局部最优问题

解决思路：以概率接受差解如何做到这一点呢？

ABC模拟退火算法回顾：退火过程中从状态i转换为状态j的转换准则：

如果E(j)≤E(i)，则状态转换被接受；

如果E(j)＞E(i)，则状态转移被接受的概率为：能用于局部搜索求解组合优化问题吗？

组合优化问题与退火过程的类比退火过程组合优化问题物理系统中的一个状态i组合优化问题的解i状态的内能E(i)解的指标函数f(i)内能最低状态最优解温度T控制参数t粒子的热运动解在邻域内的交换模拟退火算法基本思想：

在局部搜索算法中，从邻域中随机选择一个解j，如果该解的指标函数好于当前解i的指标函数，则以概率1接受该解，否则按照以下概率接受该解：这里假定求解最小解，其中f(i)为解i的指标函数，t为控制参数，也称作温度。

算法需要解决的几个问题：（1）初始温度t0（2）温度t的衰减函数（3）算法的终止准则（4）每个温度t下的马尔可夫链长度Lk。模拟退火算法的性质同前面退火过程的分析一样，当满足条件时：初始温度足够高在每个温度下状态的交换足够充分温度t的下降足够缓慢模拟退火算法以概率1收敛到最优解8.6模拟退火算法的参数选择算法实现需要确定的参数初始温度t0；温度t的衰减函数，即温度的下降方法；算法的终止准则，终止温度tf或者终止条件；每个温度t下的马尔可夫链长度Lk，即算法的内循环次数。初始温度t0的选取（1）

初始温度t0的选取（2）

求解有：

温度的下降方法基本原则温度下降足够缓慢等比例下降等值下降

每一温度下的停止准则在每个温度下要有足够的交换次数固定长度方法在每一个温度下，都使用相同的Lk。Lk的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模n的一个多项式函数。算法的终止原则

8.7模拟退火算法应用举例

举例：旅行商问题

举例：旅行商问题

举例：旅行商问题指标函数差

从解i到j解的接受概率

举例：旅行商问题

举例：旅行商问题10个城市城市x坐标y坐标A0.40000.4439B0.24390.1463C0.17070.2293D0.22930.7610E0.51710.9414F0.87320.6536G0.68780.5219H0.84880.3609I0.66830.2536J0.61950.2634举例：旅行商问题20个城市城市x坐标y坐标A5.2941.558B4.2863.622C4.7192.774D4.1852.230E0.9153.821F4.7716.041G1.5242.871H3.4472.111I3.7183.665J2.6492.556K4.3991.194L4.6602.949M1.2326.440N5.0360.244O2.7103.140P1.0723.454Q5.8556.203R0.1941.862S1.7622.693T2.6826.097城市x坐标y坐标举例：旅行商问题10城市结果：路径：ADEFGHIJBC长度：2.69120城市结果：路径：ACLBIQFTMEPRGSOJHDKN长度：24.521000次运行结果10个城市

路径长度出现次数平均转移次数路径最优2.6919063952BCADEFGHIJ次优2.752464056BCADEGFHIJ第三2.769104053DEFGHIJCBA最差2.89854497ABCDEFHIJG1000次运行结果20个城市

路径长度出现次数平均转移次数路径最优24.527928740ACLBIQFTMEPRGSOJHDKN次优24.621678638ADCLBIQFTMEPRGSOJHKN第三25.17399902ANKDHIOJSGRPEMTFQBLC最差25.5015794AQFTMEPRGSJOIBLCDHKN8.8遗传算法受进化论启发而提出的一种用于求解组合优化问题的随机算法70年代由美国的密执根大学的Holland教授首先提出进化论：物竞天择，适者生存生物在进化过程中，经过优胜劣汰的自然选择，会使得种群逐步优化，经过长期的演化，优良的物种得以保留。不同的环境，不同物种的基因结构，导致最终的物种群不同，但它们都有一个共同的特征：最能适应自己所处的生存环境。进化过程群体种群子群选择婚配变异遭淘汰的群体遗传算法从最优化的角度来讲，环境可以认为是约束条件，而进化选择之后的获胜者可以认为是在给定约束条件下的最优解。不同的约束条件，最优解也是不同的，所谓的最优解都是相对于约束条件而说的。生物进化与遗传算法之间的对应关系生物进化中的概念遗传算法中的作用环境适应函数，与求解的问题有关的函数适应性适应函数值（适应值）选择：适者生存以适应值的大小决定生存概率，适应函数值大的解生存下来的概率大，适应函数值小的解生存下来的概率小个体问题的一个解染色体解的编码基因组成编码的元素群体被选定的一组解（以编码形式表示）种群根据适应函数选择的一组解（以编码形式表示）婚配以一定的方式由双亲产生后代的过程，在遗传算法中称作交叉操作变异编码的某些基因分量发生变化的过程遗传算法涉及的五个基本问题适应函数编码问题选择操作交叉操作变异操作一个例子求解下列函数的最大值，其中x取值为区间[0,31]上的整数。

适应函数

编码问题对可能的解进行编码，以便于可以用遗传算法求解二进制编码是一种常用的编码方法该例中x取值范围为[0,31]间的整数，刚好可以用5位二进制表示，因此可以用5位二进制表示该问题的解，即染色体例如：00000表示0，00001表示1，…，11111表示31要求：一一对应选择操作设xi(i=1,…,N)是N个可能的解（个体），组成规模为N的群体F(xi)为解xi的适应值选择操作就从群体中可重复地选择N个解形成种群选择操作的基本原则：适应值越大的解被选中的概率越大选择概率：

“轮盘赌”选择算法x1x2x3x4x5x6长度为1指针r=random(0,1)“轮盘赌”选择算法“轮盘赌”算法

（1）r=random(0,1)，s=0，i=0；

（2）如果s＞r，则转（4）；

（3）i=i+1，s=s+p(xi)，转（2）

（4）xi即为被选中的染色体，输出i；

（5）结束。“轮盘赌”选择算法举例序号群体解适应值选择概率％选中次数1011011316914.4412110002457649.2323010008645.4704100111936130.861P(13)=14.44%P(24)=49.23%P(8)=5.47%P(19)=30.86%长度为1“确定性”选择算法对于规模为N的群体，选择概率为P(xi)的个体xi被选中次数的期望值e(xi)为：对于群体中的每一个xi，首先选择次，共得到个个体，然后按照从大到小对染色体排序，依次取出

个个体，这样就得到了N个染色体。

“确定性”选择算法举例序号群体适应值选择概率％期望次数选中次数10110116914.440.58121100057649.231.972301000645.470.22041001136130.861.231交叉操作设a、b是两个进行交叉操作的双亲染色体交叉操作举例变异操作基因突变称作变异在二进制编码中，变异的基因由0变成1或者由1变成0变异前

变异后

11011011101001

变异位8.9遗传算法应用举例

第0代选择情况Fm=576，xm=11000序号群体适应值选择概率（％）期望次数选中次数10110116914.440.58121100057649.231.972301000645.470.22041001136130.861.231第0代交叉情况Fm=729、xm=11011序号种群交叉对像交叉位后代适应值1011012401100144211000141100162531100042110117294100113210000256第1代选择情况Fm=729、xm=11011序号群体适应值选择概率（％）期望次数选中次数1011001448.210.33021100162535.631.43131101172941.561.66241000025614.600.581第1代交叉情况Fm=729、xm=11011序号种群交叉对像交叉位后代适应值1110012311011729211011131100162531101141100002564100003111011729第1代变异情况Fm=841、xm=11101序号群体是否变异变异位新群体适应值111011N

11011729211001Y311101841310000N

10000256411011N

11011729第2代选择情况Fm=841、xm=11101序号群体适应值选择概率（％）期望次数选中次数11101172928.531.14121110184132.921.32131000025610.020.40141101172928.531.141第2代交叉情况Fm=961、xm=11111序号种群交叉对像交叉位后代适应值1110112311001625211101131111196131000044100012894110113411010676第3代选择情况Fm=961、xm=11111序号群体适应值选择概率（％）期望次数选中次数11100162524.500.98121111196137.671.51231000128911.330.45041101067626.501.061第3代交叉情况Fm=961、xm=11111假定算法结束，得到Fm=961、xm=11111，解码后得到解x=31序号种群交叉对像交叉位后代适应值1110012311011729211111131110184131111144111109004110103411011729最大适应值、平均适应值进化曲线8.10遗传算法的实现问题遗传算法实现需要解决的问题编码问题交叉操作变异操作适应函数的定义算法的停止准则编码问题采用什么样的编码与具体问题有关，同时还要考虑表示精度以及如何进行交叉、变异操作例：x的取值范围[0,31]只取整数时，5位二进制不限于整数时，编码长度与精度有关，比如精度为0.1、0.5等编码问题

编码问题

编码问题

编码问题

编码问题上例中间隔按照0.5取：编码000000,000001,000010,…,111110对应0,0.5,1,1.5,…,31编码111111对应31.5解决办法：令111111的适应值为0，在下一代选择中被淘汰出现111111时从群体中删除

编码问题十杆桁架问题10个杆的截面积：A1、A2、...、A10在0.1至10.0之间有16个可能取值4位二进制编码表示截面积的可能取值0000表示0.1，1111表示10.010个杆用40位二进制编码表示0010111000010011101100111111001100111010编码问题旅行商问题4城市，A、B、C、D为城市名，1、2、3、4为行走次序编码：按行展开：0100100000010010表示路径BADC编码问题

编码问题解决办法：采用整数编码方法从1到n给每个城市唯一的整数编号，这组整数任意一个排列代表了旅行商问题的一个可能解例：5城