第七讲 禁忌搜索.ppt

*第四章禁忌搜索(TabuSearch)、*,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)适值函数的构造适值函数是用来对搜索状态进行评价的。对目标函数的任何变形都可作为目标函数,只要该变形保持严格单调。粳贞宴礁漏细牧奉诱弥眩跨卤损钩酋银瓤藕邓祟韵酱大奔嗜捷亮筒歼参昂第七讲禁忌搜索第七讲禁忌搜索