第七章人工智能蔡自兴

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第七章高级搜索主要内容•局部搜索方法•模拟退火算法•遗传算法7.1基本概念优化与组合优化问题•很多问题属于优化问题,或者可以转化为优化问题•如TSP问题,皇后问题优化问题的描述•设x是决策变量,D是x的定义域,f(x)是指标函数,g(x)是约束条件集合。则优化问题可以表示为,求解满足g(x)的f(x)最小值问题。•如果在定义域D上,满足条件g(x)的解是有限的,则优化问题称为组合优化问题。)(|)(minxgxfDx算法的时间复杂度•对于组合优化问题,由于其可能的解是有限的,当问题的规模比较小时,总可以通过枚举的方法获得问题的最优解,但当问题的规模比较大时,就难于求解了。•常用的算法复杂度函数)(),!(),(),2(),(),log(),(),(loglog2nnnnOnOnOOnOnnOnOnO输入量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亿次/秒)一些难的组合优化问题•旅行商问题•背包问题•装箱问题•...•寻求在可以接受的时间内得到满意解的方法邻域的概念•邻域,简单的说就是一个点附近的其他点的集合。•在距离空间,邻域就是以某一点为中心的圆。•组合优化问题的定义:•设D是问题的定义域,若存在一个映射N,使得:则称N(S)为S的邻域。DSNDSN2)(:例:皇后问题•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),(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是选取的两个城市,所谓的逆序交换方式是指,通过逆转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局部搜索算法•基本思想:在搜索过程中,始终向着离目标最接近的方向搜索。•目标可以是最大值,也可以是最小值。•在后面的介绍中,如果没有特殊说明,均假定是最小值。局部搜索算法(LocalSearch)1,随机的选择一个初始的可能解x0∈D,xb=x0,P=N(xb);2,如果不满足结束条件,则3,Begin4,选择P的一个子集P',xn为P'中的最优解5,如果f(xn)f(xb),则xb=xn,P=N(xb),转2;f(x)为指标函数。6,否则P=P–P',转2。7,End8,输出计算结果9,结束例:5城市旅行商问题●●●●●ABCDE71361071010965设初始的可能解:x0=(a,b,c,d,e)f(xb)=f(x0)=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)}设每次随机从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,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,b,d,c,e),f(xn)=44,f(xn)f(xb),P=P–{xn}={(a,b,e,d,c),(a,b,c,e,d)}第五次循环从P中选择一个元素,假设xn=(a,b,e,d,c),f(xn)=34,f(xn)f(xb),xb=(a,b,e,d,c),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)}第六次循环从P中选择一个元素,假设xn=(a,e,b,d,c),f(xn)=44,f(xn)f(xb),P=P–{xn}={(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中选择一个元素,假设xn=(a,d,e,b,c),f(xn)=39,f(xn)f(xb),P=P–{xn}={(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第八次循环从P中选择一个元素,假设xn=(a,c,e,d,b),f(xn)=38,f(xn)f(xb),P=P–{xn}={(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第九次循环从P中选择一个元素,假设xn=(a,b,d,e,c),f(xn)=38,f(xn)f(xb),P=P–{xn}={(a,b,c,d,e),(a,b,e,c,d)}第十次循环从P中选择一个元素,假设xn=(a,b,c,d,e),f(xn)=38,f(xn)f(xb),P=P–{xn}={(a,b,e,c,d)}第十一次循环从P中选择一个元素,假设xn=(a,b,e,c,d),f(xn)=41,f(xn)f(xb),P=P–{xn}={}P等于空,算法结束,得到结果为xb=(a,b,e,d,c),f(xb)=34。存在的问题•局部最优问题解决方法•每次并不一定选择邻域内最优的点,而是依据一定的概率,从邻域内选择一个点,指标函数优的点,被选中的概率比较大,而指标函数差的点,被选中的概率比较小。选择概率的计算•设求最大值:)(max)()()(xNxjiijxfxfxP选择概率的计算•当求最小值时:)(11)(1))(1()(1)(max)(maxmaxminixNxjiixPxNxPxPxPj局部搜索算法1(LocalSearch1)1,随机的选择一个初始的可能解x0∈D,xb=x0,P=N(xb)2,如果不满足结束条件,则3,Begin4,对于所有的x∈P计算指标函数f(x),并按照式(3)或者式(4)计算每一个点x的概率5,依计算的概率值,从P中随机选择一个点xn,xb=xn,P=N(xb),转26,End7,输出计算结果8,结束存在的问题•步长问题初始值搜索到的最优解解决方法•变步长初始值搜索到的最优解局部搜索算法2(LocalSearch2)1,随机的选择一个初始的可能解x0∈D,xb=x0,确定一个初始步长计算P=N(xb)2,如果不满足结束条件,则3,Begin4,选择P的一个子集P',xn为P'中的最优解5,如果f(xn)f(xb),则xb=xn6,按照某种策略改变步长,计算P=N(xb),转27,否则P=P–P',转2。8,End9,输出计算结果10,结束存在问题•起始点问题AB全局最大值局部最大值解决方法•随机的生成一些初始点,从每个初始点出发进行搜索,找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。局部搜索算法3(LocalSearch3)1,k=02,随机的选择一个初始的可能解x0∈D,xb=x0,P=N(xb)3,如果不满足结束条件,则4,Begin5,选择P的一个子集P',xn为P'中的最优解6,如果f(xn)f(xb),则xb=xn,P=N(xb),转37,否则P=P–P',转3。8,End9,k=k+110,如果k达到了指定的次数,则从k个结果中选择一个最好的结果输出,否则转(2)11,输出结果12,结束多种方法的集成•以上几种解决方法可以结合在一起使用,比如第一、第二种方法的结合,就产生了我们将在后面介绍的模拟退火方法。皇后搜索算法(QueenSearch)1,随机地将n个皇后分布在棋盘上,使得棋盘的每行、每列只有一个皇后。2,计算皇后间的冲突数conflicts。3,如果冲突数conflicts等于0,则转(6)4,对于棋盘上的任意两个皇后,交换他们的行或者列,如果交换后的冲突数conflicts减少,则接受这种交换,更新冲突数conflicts,转3。5,如果陷入了局部极小,既交换了所有的皇后后,冲突数仍然不能下降,则转1。6,输出结果7,结束。不同规模下皇后问题的平均求解时间皇后数1005001000200050001000030000平均时间(秒)551228170900100007.3模拟退火算法•是局部搜索算法的一种扩展•最早由Metropolis在1953年提出,Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。•基本思想是借用金属的退化过程改进局部搜索算法固体退火过程•溶解过程:随着温度的不断上升,粒子逐渐脱离开其平衡位置,变得越来越自由,直到达到固体的溶解温度,粒子排列从原来的有序状态变为完全的无序状态。•退火过程:随着温度的下降,粒子的热运动逐渐减弱,粒子逐渐停留在不同的状态,其排列也从无序向有序方向发展,直至到温度很低时,粒子重新以一定的结构排列。•粒子不同的排列结构,对应着不同的能量水平。如果退火过程是缓慢进行的,也就是说,温度的下降如果非常缓慢的话,使得在每个温度下,粒子的排列都达到一种平衡态,则当温度趋于0(绝对温度)时,系统的能量将趋于最小值。•如果以粒子的排列或者相应的能量来表达固体所处的状态,在温度T下,固体所处的状态具有一定的随机性。一方面,物理系统倾向于能量较低的状态,另一方面,热运动又妨碍了系统准确落入低能状态。Metropolis准则•从状态i转换为状态j的准则:•如果E(j)≤E(i),则状态转换被接受;•如果E(j)>E(i),则状态转移被接受的概率为:•其中E(i)、E(j)分别表示在状态i、j下的能量,T是温度,K>0是波尔兹曼常数。KTjEiEe)()(•在给定的温度T下,当进行足够多次的状态转换后,系统将达到热平衡。此时系统处于某个状态i的概率由波尔兹曼(Boltzmann)分布给出:•(6)•其中为归一化因子,S是所有可能状态的集合。TKTiEiZeTP)(SjKTjETeZ)(•考察一下式(6)随温度T的变化情况:–同一温度下,两个能量不同的状态–高温下的情况–低温下的情况–当温度下降时的情况•在给定的温度T下,设有i、j两个状态,E(i)<E(j):•即在任何温度T下,系统处于能量低的状态的概率大于处于能量高

1 / 151
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功