人工智能 高级搜索ppt课件.ppt

《人工智能 高级搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章高级搜索3高级搜索已经经讲过的搜索算法都是设计用来系统化地探索搜索空间的。它们在内存中保留一条或多条路径并记录哪条是已经探索过的，哪些是还没有探索过的。当找到目标时，到达目标路径的同时也构成了这个问题的解。然而有许多问题，到达目标的路径是无关的，重要的是最终结果。例如，集成电路设计、工厂场地布局、作业车间调度、自动程序设计，电信网络优化，车辆寻径，文件夹管理等。3高级搜索如果到目标的路径是无关的，我们将考虑不同种类的算法，这类算法根本不关心路径。局部搜索算法从单独的一个当前状态(而是多条路径)出发，通常只移动到与之相邻的状态。典型情况下，搜索的路径是不保存的。显然,局部搜索路径不是系统

2、化的，但是它们有两个关键的优点：(1)它们只用很少的内存；(2)它们经常能在不适合系统化算法的很大或无限的(连续的)状态空间中找到合理的解。模拟退火(SA)遗传算法(GA)算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。基本思想：借用金属的退化过程改进局部搜索算法.在冶金中，退火是为了增强金属和玻璃的韧性和硬度而先把它们加热到高温再让它们逐渐冷却的过程，能使材料结合成一个低能量的结晶态。3.1模拟退火算法（Simulatedannealing)受固体退火过程的启发，Kirkpatrick等人意识到组合优化问

3、题与固体退火过程的类似，将组合优化问题类比为固体的退火过程，提出了求解组合优化问题的模拟退火算法。如果以粒子的排列或者相应的能量来表达固体所处的状态，在温度T下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍系统准确落入低能状态。于是可定义状态转移准则：3.1模拟退火算法3.1模拟退火算法Metropolis准则：从状态i转换为状态j的准则1.如果E(j)≤E(i)，则状态转换被接受；2.如果E(j)＞E(i)，则状态转移被接受的概率为：其中E(i)、E(j)分别表示在状态i、j下的能量，T是温度，K＞0是波尔兹曼（Boltzmann）常数。3.

4、1模拟退火算法结果：在给定的温度T下，当进行足够多次的状态转换后，系统将达到热平衡。此时系统处于某个状态i的概率由波尔兹曼分布给出：其中为归一化因子，S是所有可能状态的集系统能量变化与温度变化关系：在高温下，系统基本处于无序的状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率大于系统落入高能量状态的概率，这样在同一温度下，如果系统交换的足够充分，则系统会趋向于落入较低能量的状态。3.1模拟退火算法随着温度的缓慢下降，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减少，使得系统各状态能量的期望值随温度的下降单调下降，而只有那些能量小于期望值的状态，其概率才随

5、温度下降增加，其他状态均随温度下降而下降。因此，随着能量期望值的逐步下降，能量低于期望值的状态逐步减少，当温度趋于0时，只剩下那些具有最小能量的状态，系统处于其他状态的概率趋近于0。最终系统将以概率1处于具有最小能量的一个状态。3.1模拟退火算法系统能量变化与温度变化关系：达到最小能量状态的三个条件（1）初始温度必须足够高；（2）在每个温度下，状态的交换必须足够充分；（3）温度T的下降必须足够缓慢。3.1模拟退火算法问题定义：定义一个S上的问题，i∈S是一个解，f(i)是i的指标函数。i对应于系统一个物理状态，f(i)对应能量E(i)，控制算法进程的参数t对应于温度T，热运动对应于解在邻域中

6、的交换。问题解法：首先给定较大的t，并随机给定问题的一个解i作为初始解；在给定t下，随机在i的邻域中产生一个解j，i到j的转移按照Metropolis准则确定，如f(i)>f(j)就交换，否则按一定概率交换；重复多次直到达到平衡，即少有交换再发生，或交换次数达到一定值；缓慢降低t，重复上述过程；最终得到一个最优解。3.1模拟退火算法算法流程：随机选择一个解s＝s0,初始温度t=t0,k=0,计算指标f(i);Do{Do{从当前状态i邻域随机选择一个j,计算指标f(i);如果j比i优，直接转移到优解j；否则计算转移概率，以一定概率转移到劣解j；}while在该温度下达到平衡状态；修改循环参数：

7、tk+1=down(tk)，k=k+1；}while算法终止条件满足；3.1模拟退火算法该算法有内外两层循环：内循环模拟的是在给定温度下系统达到热平衡的过程，每次循环随机地产生一个新解，然后按照状态接受函数，随机地接受该解;外循环模拟的是温度的下降过程，控制参数tk起到与温度T相类似的作用，表示的是第k次循环时系统所处的温度。算法中的down(tk)是一个温度下降函数，它按照一定的原则实施温度的缓慢下降。3.