第七讲 禁忌搜索.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)适值函数的构造适值函数是用来对搜索状态进行评价的。对目标函数的任何变形都可作为目标函数,只要该变形保持严格单调。啪勤淘笨震乱羚拷薪貉剥缠衡伴镊融疤雾惟蓑碟势哎醛退引阉钟罐舰殴校第七讲禁忌搜索第七讲禁忌搜索