资源描述:
《第9讲模拟退火算法等ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第9讲模拟退火算法等1.局部搜索方法2.模拟退火算法邻域的概念邻域,简单的说就是一个点附近的其他点的集合。在距离空间,邻域就是以某一点为中心的圆。组合优化问题的定义:设D是问题的定义域,若存在一个映射N,使得:则称N(S)为S的邻域。例:旅行商问题用一个城市的序列表示一个可能的解。通过交换两个城市的位置获取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-
2、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+11.局部搜索算法基本思想:在搜索过程中,始终向着离目标最接近的方向搜索。目标可以是最大值,也可以是最
3、小值。在后面的介绍中,如果没有特殊说明,均假定是最小值。局部搜索算法(LocalSearch)1,随机的选择一个初始的可能解x0∈D,xb=x0,P=N(xb);2,如果不满足结束条件,则3,Begin4,选择P的一个子集P',xn为P'中的最优解5,如果f(xn)4、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),(
5、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)6、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=
7、(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)