第二章 禁忌搜索算法.ppt

第二章__禁忌搜索算法(d*=)►,通常的邻域定义是以一点为中心的一个球体;={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列},定义它的邻域映射为2-opt,即x中的两个元素进行对换,N(x)2=n(n-1)/2个邻居和x本身。例如:x=(1,2,3,4),则C42=6,N(x)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}-opt,推广到k-opt。邻域概念的重要性邻域的构造依赖于决策变量的表示,邻域的结构在现代优化算法中起重要的作用。,记录当前最优解xbest:=x0,T=N(xbest);STEP2当T\{xbest}=Φ时,或满足其他停止运算准则时,输出计算结果,停止运算;否则,从T中选一集合S,得到S中的最好解xnow;若f(xnow)<f(xbest),则xbest:=xnow,T=N(xbest);否则T:=T\S;重复SETP2。=(ABCDE),f(xbest)=45,定义邻域映射为对换两个城市位置的2-opt,选定A城市为起点。:全邻域搜索第1步N(xbest)={(ABCDE),(ACBDE),(ADCBE),(AECDB),(ABDCE),(ABEDC),(ABCED)},对应目标函数为f(x)={45,43,45,60,60,59,44}xbest:=xnow=(ACBDE):全邻域搜索第2步N(xbest)={(ACBDE),(ABCDE),(ADBCE),(AEBDC),(ACDBE),(ACEDB),(ACBED)},对应目标函数为f(x)={43,45,44,59,59,58,43}xbest:=xnow=(ACBDE):一步随机搜索第1步从N(xbest)中随机选一点,如xnow=(ACBDE),对应目标函数为f(xnow)=43<45xbest:=xnow=(ACBDE)