5.局部搜索算法专业知识课件.ppt

局部搜索算法前面的搜索算法都是保留搜索路径的,到达目标的路径就是问题的解—然而许多问题中到达目标的路径是无关紧要的与系统地搜索状态空间(保留各种路径)相对,不关心路径的搜索算法就是局部搜索算法局部搜索从一个单独的当前状态出发,通常只移动到相邻状态典型情况下搜索的路径不保留1局部搜索与最优化问题局部搜索算法的优点:只使用很少的内存(通常是一个常数)经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解最优化问题—根据一个目标函数找到最佳状态/只有目标函数,而不考虑(没有)“目标测试”和“路径耗散”局部搜索算法适用于最优化问题2状态空间地形图(1)山肩目标函数全局最大值局部最大值“平坦”局部最大值状态空间当前状态3状态空间地形图(2)在状态图中,既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示)如果高度对应于耗散值,则目标是找到全局最小值,即图中最低点如果高度对应于目标函数,则目标是找到全局最大值,即图中最高峰如果存在解,则完备的局部搜索算法能够找到解而最优的局部搜索算法能够找到全局最大或最小值4局部搜索算法本节简要介绍以下4种局部搜索算法/介绍其算法思想爬山法搜索模拟退火搜索局部剪枝搜索遗传算法从学习的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)—生成后继假设的方式5例子:8皇后问题目标:任何一个皇后都不会攻击到其他的皇后(皇后可以攻击和它在同一行、同一列或同一对角线上的皇后)h取作可以彼此攻击的皇后对的数目(忽略障碍)h=17的一个状态,h取局部极小值时的一个状态5步爬山法搜索的局限爬山法是一种局部贪婪搜索,不是最优解算法(或是不完备的)/其问题是:局部极大值—比其邻居状态都高的顶峰,但是小于全局最大值(参照状态空间地形图)山脊—一系列的局部极大值高原—评价函数平坦的一块区域(或者山肩)9爬山法搜索的变形爬山法的变形随机爬山法—随机选择下一步首选爬山法—随机选择直到有优于当前节点的下一步随机重新开始爬山法—随机生成初始状态,进行一系列爬山法搜索—这时算法是完备的概率接近110