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

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

BC

BD
8
第1步
解的形式
禁忌对象及长度
候选解
f(x0)=4
第2步
A
B
D
C
B
C
D
A
B
C
3
对换
评价值
CD

BC

BD

f(x1)=
最优化算法案例学习禁忌搜索,混合算法
禁忌搜索举例:TSP问题
第3步
解的形式
禁忌对象及长度
候选解
f(x0)=
第4步
f(x1)=
A
C
D
B
B
C
D
A
B
3
C
2
对换
评价值
CD
8
BC

BD

A
C
B
D
B
C
D
A
B
2
3
C
1
对换
评价值
CD

BC

BD

最优化算法案例学习禁忌搜索,混合算法
禁忌搜索举例:TSP问题
第5步
解的形式
禁忌对象及长度
候选解
f(x0)=
第6步
f(x1)=8
A
D
B
C
B
C
D
A
B
0
1
C
2
对换
评价值
CD

BC
8
BD

A
D
C
B
B
C
D
A
B
3
0
C
1
对换
评价值
CD

BC

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