禁忌搜索算法.ppt

第二章第二章禁忌搜索算法禁忌搜索算法智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年 1 局部搜索局部搜索 邻域的概念邻域的概念 局部搜索算法局部搜索算法 局部搜索示例局部搜索示例 禁忌搜索禁忌搜索 算法的主要思路算法的主要思路 禁忌搜索示例禁忌搜索示例 禁忌搜索的关键参数和操作禁忌搜索的关键参数和操作 变化因素变化因素 禁忌表禁忌表 其他其他 禁忌搜索的实现与应用禁忌搜索的实现与应用 30 30 城市城市 TSP TSP 问题( 问题( d d * * = by D B Fogel = by D B Fogel ) ) 基于禁忌搜索算法的系统辨识基于禁忌搜索算法的系统辨识智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年 2 局部搜索局部搜索智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年?函数优化问题中在距离空间中,通常的邻域定义是以一点为中心的一个球体; ?组合优化问题中 2 2 . . 邻域的概念邻域的概念的一个邻居。称为的邻域, 称为。的所有子集组成的集合表示其中,称为一个邻域映射, 且xxNyxxN D xNx xNDxN D D)()( 2 )( ,2)(:????? 3 局部搜索局部搜索智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年?例 TSP 问题解的一种表示方法为 D ={x =(i 1,i 2,…,i n )| i 1,i 2,…,i n是1,2, …,n的排列},定义它的邻域映射为 2 - opt ,即 x中的两个元素进行对换, N(x)中共包含 x的C n 2=n(n -1)/2 个邻居和 x本身。例如: x =(1,2,3,4) ,则 C 4 2 =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)} 2 2 . . 邻域的概念邻域的概念 4 局部搜索局部搜索智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年?例 TSP 问题解的邻域映射可由 2- opt ,推广到 k- opt 。?邻域概念的重要性邻域的构造依赖于决策变量的表示, 邻域的结构在现代优化算法中起重要的作用。 2 2 . . 邻域的概念邻域的概念 5 局部搜索局部搜索智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年? STEP 1 选定一个初始可行解 x 0,记录当前最优解 x best :=x 0, T=N(x best); ? STEP 2 当T \{x best }=Φ时,或满足其他停止运算准则时,输出计算结果,停止运算;否则,从 T中选一集合 S,得到S中的最好解 x now ;若 f (x now )<f(x best),则 x best := x now ,T=N(x best);否则 T :=T\S;重复 SETP 2 。 2 2 . . 局部搜索算法局部搜索算法 6 局部搜索局部搜索智能优化计算智能优化计算华东理工大学自动化系华东理工大学自动化系华东理工大学自动化系 2007 2007 2007 年年年?五个城市的对称 TSP 问题初始解为 x best =( ABCDE ),f(x best )=45 ,定义邻域映射为对换两个城市位置的 2-opt ,选定 A城市为起点。 2 2 . . 局部搜索示例局部搜索示例 7