《人工智能》ppt课件

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

1、第七章高级搜索主要内容局部搜索方法模拟退火算法遗传算法7.1基本概念优化与组合优化问题很多问题属于优化问题，或者可以转化为优化问题如TSP问题，皇后问题优化问题的描述设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。算法的时间复杂度对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，就难

2、于求解了。常用的算法复杂度函数输入量n复杂性函数10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.0ms1.1s18.3min4.0世纪n!3.6ms77.1年8.4×1013世纪2.6×1029世纪3.0×10139世纪时间复杂性函数比较（10亿次/秒）一些难的组合优化问题旅行商问题背包问题装箱问题...寻求在可以接受的时间内得到满意解的方法邻域的概念邻域，简单的说就是

3、一个点附近的其他点的集合。在距离空间，邻域就是以某一点为中心的圆。组合优化问题的定义：设D是问题的定义域，若存在一个映射N，使得：则称N(S)为S的邻域。例：皇后问题S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。如四皇后问题的一个解：S=(2,4,1,3)QQQQ定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。例：当S=(2,4,1,3)时，其邻域为：N(S)={(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(

4、2,4,3,1)}例：旅行商问题用一个城市的序列表示一个可能的解。通过交换两个城市的位置获取S的邻居例：简单交换方法设S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)则通过交换xi和xj两个城市的位置可以得到S的一个邻居：S'=(x1,x2,…xi-1,xj,xi+1,…,xj-1,xi,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1例：逆序交换方法设xi、xj是选取的两个城市，所谓的逆序交换方式是指，通

5、过逆转xi、xj两个城市之间的城市次序来得到S的邻居。设：S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)则：S'=(x1,x2,…xi-1,xi,xj-1,xj-2…,xi+1,xj,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+17.2局部搜索算法基本思想：在搜索过程中，始终向着离目标最接近的方向搜索。目标可以是最大值，也可以是最小值。在后面的介绍中，如果没有特殊说明，均假定是最小值。局部搜索算法（Lo

6、calSearch）1，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)；2，如果不满足结束条件，则3，Begin4，选择P的一个子集P'，xn为P'中的最优解5，如果f(xn)

7、d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}设每次随机从P中选择一个邻居。第一次循环从P中选择一个元素，假设xn=(a,c,b,d,e),f(xn)=42,f(xn)>f(xb),P=P–{xn}={(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)}第二次循环从P中选择一个元素，假设xn=(a,d,c,b,e),f(xn)=45,f(xn)>f(xb),P=P–{xn}={(a,e

8、,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第三次循环从P中选择一个元素，假设xn=(a,e,c,d,b),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第四次循环从P中选择一个元素，假设xn=(a,