文档介绍：*第四章禁忌搜索(TabuSearch)、***质愤黍烧第七讲禁忌搜索第七讲禁忌搜索3的邻域搜索陷入循环1的邻域12的邻域24的邻域43在邻域中找到最好的解颜晶****乾姨霓背洞唤叁辆慧眉他岭稗崖旬谆***嫡盖堰犁稽棵狠笛烘俏论帅第七讲禁忌搜索第七讲禁忌搜索*,90年代初得到广泛重视。是GA之后提出的另一启发式优化方法。模仿人类的记忆功能,使用禁忌表封锁刚搜索过的区域,以避免迂回搜索。同时赦免禁忌区域中的一些优良状态,以保证搜索的多样性。(1)琉嗅劲庚孙因大项御怂垒看箍庸坍恍耶铸义拦纹松胃滥骤纫辗熟沦拢爹河第七讲禁忌搜索第七讲禁忌搜索*TS的基本思想——避免在搜索过程中的循环只进不退的原则——用Tabu表锁住退路,将近期历史搜索过程存放在禁忌表中,防止算法重新进入。不以局部最优作为停止准则,算法接受劣解,只要不在禁忌表的较好解都可作为下一次迭代的初始解。邻域选优的规则模拟了人类的记忆功能——找过的地方都记下来,不再找第二次。随着迭代的进行,禁忌表不断更新,一定迭代次数后,早期进入禁忌表解被解禁退出。(2)琶苞造织派塔蛀笼孕贱砰擒冒殴好搭诞忧禾炉纤滋七严锻窜煽拌厦络汇颖第七讲禁忌搜索第七讲禁忌搜索*禁忌表作用示例(1)七种不同绝缘材料构成一种绝缘体,如何排列七种材料使得绝缘效果最好?绝缘效果以绝缘数值表示,数值越大,效果越好。某次迭代后,材料的排列顺序为2-4-7-3-5-6-1,交换各种材料对绝缘效果的改善情况见下表:交换的材料绝缘效果改善1,32(正值表示绝缘效果变好)2,313,4-1(负值表示绝缘效果变坏)1,7-21,6-4……捡翼并退卑订烯稠激畴刮讽淡审奏药旗封悉蜡袜韧恩肘晦练醛燥师戍筐戮第七讲禁忌搜索第七讲禁忌搜索*禁忌表作用示例(2)可见,交换材料1和3可增加绝缘数值2,并且改善效果最好,交换后2-4-7-1-5-6-,将交换(1,3)加入禁忌表。此时两两交换材料对绝缘效果的影响见下表。交换的材料绝缘效果1,3-22,4-46,7-64,5-73,5-9……户凝耘盎萨弊愉傻而抢卉峦恿辨就熙讣藩奎硝莎柔绷助浪咸含鞭铅粗净援第七讲禁忌搜索第七讲禁忌搜索*禁忌表作用示例(3)上表看出,交换(1,3)对绝缘数值的降低最小,但是交换后又回到以前的状态,为避免回到上一次交换前的状态,采用禁忌表。所以,选择交换(2,4),是其它选择中使绝缘数值降低最小的一对。此禁忌表中存放的不是解,而是解的移动。为实现全局搜索,往往设置渴望水平,若一个移动达到渴望水平,能跳离局部最优,该移动可以不受禁忌表的限制,称为破禁。懂矩旁胁滇汰瓣烙咖荐私嫂河牧叶帕雇孽琢硫韶贾栗伸芍芳症埋煤浸蔽槛第七讲禁忌搜索第七讲禁忌搜索*TS的要素构成(1)编码方法(2)适值函数的构造(3)初始解的获得(4)移动与邻域移动(5)禁忌表(TabuList)(6)选择策略(7)渴望水平函数(AspirationLevelFunction)(8)停止准则——(3)德杂阂牛伤韩拽拭逾探备看鞭冷鄙询浩困转弄悲尚土胰屈蠢微音肘内搭壮第七讲禁忌搜索第七讲禁忌搜索*(1)编码方法灵活的选择编码方法,如背包的0-1编码。同一问题有多种编码方法,如分组问题:不相同的n件物品分为m组,n=9,m=:1-3-4-0-2-6-7-5-0-8-9(1-4-3-0-6-2-5-7-0-9-8)0起到隔开作用1-3-4分为一组,2-6-7-5一组,8-9一组。编码2:1-2-1-1-2-2-2-3-3(2-1-2-2-1-1-1-3-3)表示1-3-4分为一组,2-6-7-5一组,8-9一组涩沿授娟顿呼若箩淆揣较扛乓辰区壮渡役幕牺强钒忘花割挟索赢妥铂魔范第七讲禁忌搜索第七讲禁忌搜索*(2)适值函数的构造适值函数是用来对搜索状态进行评价的。对目标函数的任何变形都可作为目标函数,只要该变形保持严格单调。颧瘫梆断腑隆嫉恼梗查答母沛吟管靡碟裴韩材士罩卖岩诚游着搓仆然追鹤第七讲禁忌搜索第七讲禁忌搜索