清华大学《人工智能导论》课程电子教案（三）.ppt

1、高级搜索、主要内容、部分搜索方法模拟退火算法遗传算法、最优化和组合优化问题、很多问题都是最优化问题或最优化问题(例如TSP问题、皇后问题、最优化问题说明、将x设置为决策变量、d设置为x的定义域、f(x)为指标函数、g(优化)在定义域D中满足条件g(x)的解决方案受到限制的情况下，最优化问题称为组合优化问题。在算法时间复杂度、组合优化问题的情况下，可能的解决方案是有限的，所以问题的大小比较小的时候，总是可以通过列出的方法得到问题的最佳解决方法，但是问题的规模比较大的时候，就很难解决了。常用算法复杂性函数，时间复杂性函数比较(10亿次/秒)，困难组合优化问题，旅行问题背包问题包装问题.在可接受的时

2、间内找到满意的解决方法，邻居的概念，邻居，简单地说，是一个点附近的另一个点的集合。在距离空间里，邻居是以一点为中心的圆。组合优化问题的定义：将D设置为问题的定义域，如果存在映射N牙齿，则N(S)称为S的邻居。例如皇后问题，S=Si表示可能的解决方案。其中Si在I行中，Si列中有皇后。4皇后问题的解决方案：定义S=(2，4，1，3)，映射N，将其定义为棋盘上两个皇后的行或列更换，即S中的两个元素更换位置。例如，S=(2，4，1，3)时，相邻n (s)=(4，2，1，3)，(1，4，2，3)，交换两个城市的位置以获得S的相邻示例。简单更换方法通过设置s=(x1，x2，Xi-1，Xi，Xi 1，XJ

3、-1，XJ，xj1，xn)交换Xi和XJ两个城市的位置Xi，xj1，在下面的介绍中，如果没有特殊说明，则假定为最小值。本地搜寻演算法(Local Search) 1，随机选择初始可能的解决方案x0D之一，xb=x0，p=n(XB)；2、如果不满足终止条件，则选择3、Begin 4、P的子集P之一。xn是P的最佳解决方案5。如果f(xn) f(xb)，请旋转至XB xn，P=N(xb)，2。F(x)是指标函数。6，否则P=P P p，旋转2。7，End 8，输出计算结果9，结束，如5城市旅行者问题，a，b，C，d，e，第一个回路，在p中选择元素，xn=(a，c，b，d，e)，f (xn)=42，

4、f (xn) f (XB)，p=；b，c，E，d)，第二个回路，在p中选择元素，xn=(a，d，c，b，E)，f (xn)=45，f (xn)假设E e，D，C)，p=(a，e，b，D，C)，(a，d Xn=(a，e，b，D，C)，f (xn) Xn=(a，b，d，e，c)，f (xn)=38，f (xn) f (XB)，p=p xn=(a，b，c)，概率计算选择，最大设置：选择概率计算，获取最小值时：局部搜寻演算法1(Local Search 1) 1，随机初始可能的解决方案x0D，xb=x0，p=n(每个点x的概率5为样式(如果不满足结束条件，则选择3、Begin 4、p的子集p之一；如果

5、f (xn)是p的最佳解决方案5，则选择xn 8、End 9、输出计算结果10、结束、问题、起点问题、本地搜寻演算法3(Local Search 3) 1，k=0 2，随机选择其中一个可能的解决方案x0D，xb=x0，P=N(xb) 3，如果不满足终止条件，则为4，begin8，End 9，k=k 1 10，k达到指定次数后，选择k个结果中的最佳结果输出。否则，(2) 11，输出结果12，退出，合并多种方法，这些多种茄子解决方案可以一起使用(例如，第一，)，皇后搜寻演算法(Queen Search) 1，随机将N个女王分布在棋盘上，每排棋盘，每列2、计算皇后之间的碰撞数conflicts。3、

6、碰撞数conflicts为0时(6)，转动4，为棋盘上的两个皇后交换行或列，交换的碰撞数conflicts减少时，接受牙齿交换，更新碰撞数conflicts，然后转动3。5.陷入局部的闹剧，交换所有皇后后，如果冲突数不减少，就转动1。6，输出结果7，结束。不同规模皇后问题的平均解决时间，模拟退火算法，部分搜寻演算法扩展，1953年大都会首次提出，Kirkpatrick等在1983年成功地使用模拟退火算法解决组合优化问题。基本思想是借用金属的退化过程，改善局部搜索算法、固体退化过程、溶解过程。随着温度继续上升，粒子牙齿逐渐脱离平衡位置，逐渐自由，粒子阵列从原来的秩序状态变为完全无序状态，直到达到

7、固体的溶解温度。退火过程：随着温度的下降，粒子热运动逐渐减弱，粒子逐渐停留在其他状态，其排列也从无序向有序的方向发展，直到温度很低，粒子重新排列成一定的结构。粒子对应不同的阵列结构，不同的能量级别。如果退火过程进展缓慢，即温度下降非常慢，则粒子阵列在每个温度下平衡，如果温度牙齿到0(绝对温度)，则系统的能量为最小值。用粒子阵列或其能量表示固体存在的状态，在温度T处固体存在的状态具有一定的随机性。另一方面，物理系统倾向于低能量状态，热运动阻碍系统准确地降到低能量状态。如果从状态I转换为状态j的Metropolis指令：E(j)E(i)，则允许状态转换。如果E(j)E(i)，则允许状态转换的概率为

8、：其中E(i)，E(j)分别是状态I，j下的能量，t是温度，K0是玻尔兹曼常量。在给定温度T处进行足够数量的状态转换时，系统达到热平衡。牙齿时系统处于特定状态的概率由玻耳兹曼分布给出。(6)其中，S是规范化系数，S是所有可能状态的集合。调查式(6)根据温度T的变化：在同一温度下，两个能量从不同状态高温下下降时，温度下降时，在指定温度T下，I，J两个茄子状态下，E(i)E(j):任何温度，E(i)E(j)其中|S|表示系统中所有可能的状态数。温度高的时候，系统处于各种状态的概率几乎相同，接近平均值，与所处状态的能量几乎无关。当温度为零时：Sm表示系统最小能量状态的集合，Em是系统最小能量。常识分子，分母乘积，概率1达到能量最小的状态。温度上升或下降的时候：系统进入低能量状态的概率随着温度下降单调上升，系统进入高能量状态的概率随着温度下降单调下降。在高温下，系统基本处于无序状态，基本上以相等的概率进入每种状态。在指定温度下，系统进入低能量状态的概率大于系统进入高能量状态的概率，因此，如果系统在相同温度下被充分交换，系统倾向于进入低能量状态。随着温度的慢慢下降，系统进入低能量状态的概率逐渐增加，进入高能量状态的概率逐渐减少，系统各状态能量的期望值随着温度的下降单调下降，如果只有该能量低于期望值，那么该概率随着温度的下降而增加，其他状态都随着温度的下降而降低。因此，随着能量期望值