禁忌搜索算法.ppt

禁忌搜索算法--昆昆智能优化计算概览局部搜索禁忌搜索禁忌搜索关键参数和操作禁忌搜索实现和应用局部搜索邻域--定义--tsp示例--重要性局部搜索--操作步骤搜索示例--五城市对称tsp问题邻域①函数优化问题:邻域(N(x))通常定义为在给定距离空间内,以一点(x)为中心的一个球体②组合优化问题:且,称为一个邻域映射,其中表示X所有子集组成的集合。N(x)称为x的邻域, 称为x的一个邻居。: ( ) 2XN x X N x ( )x N x 2X( )y N x邻域举两个简单的例子:定义邻域移动为:位值加1或减1对整数编码[ 2 2 3 5 3],判断一下下列编码是否在其邻域内:[2 3 3 5 3] [2 3 2 5 3] [2 2 3 5 5][2 2 3 4 3] [2 2 2 5 3] [2 2 3 4 4]邻域定义邻域移动为:2-Opt对顺序编码[ 4 2 3 5 1],判断一下下列编码是否在其邻域内:[4 3 2 5 1] [4 3 5 1 2] [4 3 3 5 1][5 2 3 4 1] [1 2 3 5 4] [3 4 2 5 1]邻域定义邻域移动为:2-Opt对顺序编码[ 4 2 3 5 1],判断一下下列编码是否在其邻域内:[4 3 2 5 1] [4 3 5 1 2] [4 3 3 5 1][5 2 3 4 1] [1 2 3 5 4] [3 4 2 5 1]邻域重要性:邻域的构造依赖于决策变量的表示,邻域的结构在现代优化算法中起重要的作用。局部搜索操作步骤: STEP 1选定一个初始可行解x0,记录当前最优解xbest:=x0, T=N(xbest); STEP 2当T\{xbest}=Φ时,或满足其他停止运算准则时,输出计算结果,停止运算;否则,从T中选一集合S,得到S中的最好解xnow;若f (xnow)<f(xbest),则xbest := xnow ,T=N(xbest);否则T:=T\S;重复STEP 2。局部搜索示例五个城市的对称TSP问题初始解为xbest=(ABCDE),f(xbest)=45,定义邻域映射为对换两个城市位置的2-opt,选定A城市为起点。