和当前时间比较_干货 - 快速掌握禁忌搜索算法求解带时间窗的车辆路径问题

和当前时间比较_干货 - 快速掌握禁忌搜索算法求解带时间窗的车辆路径问题本文发布于公众号 数据魔术师 同名文章 一 什么是禁忌搜索算法 禁忌搜索算法 Tabu Search Algorithm 简称 TS 起源于对于人类记忆功能的模仿 是一种亚启发式算法 meta heuristics 它从一个初始可行解 initial feasible solution

大家好,我是讯享网,很高兴认识大家。
本文发布于公众号【数据魔术师】同名文章

一 什么是禁忌搜索算法?

禁忌搜索算法(Tabu Search Algorithm,简称TS)起源于对于人类记忆功能的模仿,是一种亚启发式算法(meta-heuristics)。它从一个初始可行解(initial feasible solution)出发,试探一系列的特定搜索方向(移动),选择让特定的目标函数值提升最多的移动。为了避免陷入局部最优解,禁忌搜索对已经历过的搜索过程信息进行记录,从而指导下一步的搜索方向。

禁忌搜索是人工智能的一种体现,是局部搜索的一种扩展。禁忌搜索是在邻域搜索(local search)的基础上,通过设置禁忌表(tabu list)来禁忌一些曾经执行过的操作,并利用藐视准则来解禁一些优秀的解。

二 禁忌搜索算法基本步骤:

① 初始化

利用贪婪算法等局部搜索算法生成一个初始解,清空禁忌表,设置禁忌长度。

② 邻域搜索产生候选解


讯享网

根据步骤①产生初始解,通过搜索算子(search operators),如relocation、exchange、2-opt等,产生候选解(candidate solution),并计算各个候选解的适应值(即解对应的目标函数值)。

③ 选择最好的候选解

从步骤②产生的所有候选解中选出适应值最好的候选解,将其与当前最好解(即搜索算法开始到现在找到的最好解)进行比较,如果优于当前最好解,那么就不考虑其是否被禁忌,用这个最好的候选解来更新当前最好解,并且作为下一个迭代的当前解,然后将对应的操作加入禁忌表;如果不优于当前最好解,就从所有候选解中选出不在禁忌状态下的最好解作为新的当前解,然后将对应操作加入禁忌表。

④ 判断终止条件

若满足终止条件,则立即停止并输出当前最好解;否则继续搜索。一般终止条件为是否到达一定的迭代次数或者达到了一个时间限制。

禁忌搜索算法流程图:

6502a2a3d48b219a970ef8b788417149.png
小讯
上一篇 2025-01-27 21:30
下一篇 2025-01-11 22:48

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80663.html