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

大作业汇报ShanghaiMaritimeUniversity禁忌搜索案例学习目录小组分工禁忌搜索算法带软时间窗的集货与送货多车辆路径问题节约算法考虑碳排放的开环取送货路径优化问题数值实验禁忌搜索算法FredGlover禁忌搜索(TabuSearch)是局部邻域搜索算法的推广,FredGlover在1986年提出这个概念,,比如走迷宫时,当发现有可能又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性,这样就可以确定性的避开迂回搜索。禁忌搜索算法只进不退的原则——用Tabu表锁住退路,将近期历史搜索过程存放在禁忌表中,防止算法迂回搜索。不以局部最优作为停止准则,算法接受劣解,只要不在禁忌表的较好解都可作为下一次迭代的初始解。邻域选优的规则模拟了人类的记忆功能,找过的地方都记下来,不再找第二次。一定迭代次数后,早期进入禁忌表解被解禁退出核心思想禁忌搜索算法步骤第一步选定一个初始解xnow;令禁忌表;第二步若满足终止准则,转第四步;否则,在xnow的邻域N(xnow)中选出满足禁忌要求的候选集C-N(xnow),转第三步;第三步在C-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表H,转第二步;第四步输出计算结果,:为避免迂回搜索,记录之前搜索过的解或状态的表禁忌对象:禁忌表中被禁的那些变化元素禁忌长度:禁忌的步数特赦原则:对一些显著提高解质量而处于禁忌的操作解禁禁忌搜索算法失败出口(避免)破禁检查初始开始更新T表停止YN停止YN若令若输出终止出口step2step3step4step5step1邻域移动择优规则禁忌搜索举例:TSP问题四城市非对称TSP问题初始解x0=(ABCD),f(x0)=4,邻域映射为两个城市顺序对换的2-opt,始、终点都是A城市。禁忌搜索举例:(x0)=(x1)=:TSP问题第3步解的形式禁忌对象及长度候选解f(x0)=(x1)=:TSP问题第5步解的形式禁忌对象及长度候选解f(x0)=(x1)=