初识禁忌搜索算法-阿里云开发者社区

开发者社区> 人工智能> 正文

初识禁忌搜索算法

简介:   一周前和实验室师弟一起探讨的,在我的影响下他开始去坐毕设了...啧啧;现在等我同学过来找我,把那次的讨论内容回忆一下。   写一写个人理解,语句比较混乱,只一个入门,我并没有深入研究过。   这是一个启发式搜索算法。

  一周前和实验室师弟一起探讨的,在我的影响下他开始去坐毕设了...啧啧;现在等我同学过来找我,把那次的讨论内容回忆一下。

  写一写个人理解,语句比较混乱,只一个入门,我并没有深入研究过。

  这是一个启发式搜索算法。

  以解决TSP问题为例,假设ABCDE五个城市,各个城市间距离的无向图。

  1.假设以A开头,ABCDE,这个假设是随意的,因为TSP是环,没有开头,计算距离的时候需要加上环.

  2.BCDE两两交换,注意是相邻交换,不是A(n,2),是BC,CD,DE交换,算出所有的TSP距离,注意ABCDE距离需要加上EA的距离,假设算出的最短距离的序列为Seq1。

  3.将Seq1加入禁忌表中,包括序号1,表示第一个序列,序列,以及长度。

  4.取Seq1,ABCDE,相邻交换BCDE,这肯定和上一次有重复,但是不会完全重复,取最短路径对应的序列加入禁忌表,成为Seq2.

  5.重复k次,禁忌表的长度为k,为什么禁忌表中要保存k次,不选k次中最小的一次,因为即便最小的一次可能是局部最优,其他的非局部最优通过相邻交换可能得到全局最优。

  禁忌表的长度和禁忌长度不是一个概念,都是为了保证算法多样性。

  for 禁忌表的长度

    for 禁忌长度

      对每个序列,重复禁忌长度的次数,比如说禁忌长度为3,选择3次中最小的替换禁忌表中的新东西。

  完全是个人理解,不一定正确,我还没有研究禁忌搜索,只是做一个记录,请各位看官去其糟粕,取其精华。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章