最优化算法案例学习(禁忌搜索,混合算法)

《最优化算法案例学习(禁忌搜索,混合算法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大作业汇报ShanghaiMaritimeUniversity禁忌搜索案例学习目录小组分工禁忌搜索算法带软时间窗的集货与送货多车辆路径问题节约算法考虑碳排放的开环取送货路径优化问题数值实验禁忌搜索算法FredGlover禁忌搜索(TabuSearch)是局部邻域搜索算法的推广,FredGlover在1986年提出这个概念,进而形成一套完整算法.人类在选择过程中具有记忆功能，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这样就可以确定性的避开迂回搜索。禁忌搜索算法只进不退的原则——用Tabu表锁住退路，将近期历史搜索过程存放在禁忌表中，防止算法迂

2、回搜索。不以局部最优作为停止准则，算法接受劣解，只要不在禁忌表的较好解都可作为下一次迭代的初始解。邻域选优的规则模拟了人类的记忆功能，找过的地方都记下来，不再找第二次。一定迭代次数后，早期进入禁忌表解被解禁退出核心思想禁忌搜索算法步骤第一步选定一个初始解xnow;令禁忌表;第二步若满足终止准则,转第四步;否则,在xnow的邻域N(xnow)中选出满足禁忌要求的候选集C-N(xnow),转第三步;第三步在C-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表H,转第二步;第四步输出计算结果,停止.概念禁忌表：为避免迂回搜索，记录之前搜索过的解或状态的表禁忌对象：禁

3、忌表中被禁的那些变化元素禁忌长度：禁忌的步数特赦原则：对一些显著提高解质量而处于禁忌的操作解禁禁忌搜索算法失败出口(避免)破禁检查初始开始更新T表停止YN停止YN若令若输出终止出口step2step3step4step5step1邻域移动择优规则禁忌搜索举例：TSP问题四城市非对称TSP问题初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。1禁忌搜索举例：TSP问题ABCDBCDABC对换评价值CD4.5BC7.5BD8第1步解的形式禁忌对象及长度候选解f(x0)=4第2步ABDCBCDABC3对换评价值CD4.5BC3.5BD4.5f(x1

4、)=4.5禁忌搜索举例：TSP问题第3步解的形式禁忌对象及长度候选解f(x0)=3.5第4步f(x1)=7.5ACDBBCDAB3C2对换评价值CD8BC4.5BD7.5ACBDBCDAB23C1对换评价值CD4.5BC4.5BD3.5禁忌搜索举例：TSP问题第5步解的形式禁忌对象及长度候选解f(x0)=4.5第6步f(x1)=8ADBCBCDAB01C2对换评价值CD7.5BC8BD4.5ADCBBCDAB30C1对换评价值CD3.5BC4.5BD4禁忌对象解的简单变化解向量分量的变化目标值变化情况1：禁忌对象为简单的解变化xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;

5、45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}xnext=(ACBDE)情况2：禁忌对象为分量变化xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N(xnow)={(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}xnext=(ACBED)情况3：禁忌对象为目标值变化xnow=(ABCDE)，f(xnow)=45，H={45}Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45

6、)，(ABEDC;59)，(ABCED;44)}xnext=(ACBDE)特赦原则基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；基于影响力的规则，可以特赦对目标值影响大的对象。其它原则禁忌长度与评价函数（1）t可以为常数，易于实现；（2），t是可以变化的数，tmin和tmax是确定的。tmin和tmax根据问题的规模确定，t的大小主要依据实际问题实验和设计者的经验。（3）tmin和tmax的动态选择。评价函数（1）直接评价函数，通过目标函数的运算得到评价函数；（2）间接评价函数，构造其他评价函数替代目标

7、函数，应反映目标函数的特性，减少计算复杂性。禁忌长度记忆频率信息和终止规则记忆频率信息（1）静态频率信息：解、对换或目标值在计算中出现的频率；（2）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。终止规则（1）确定步数终止，无法保证解的效果，应记录当前最优解；（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；（3）目标控制原则，如果在一个给定