遗传算法 – 带有Time Windows的TSP的交叉运算符

发布时间：2020-12-14 05:35:20 所属栏目：Windows 来源：网络整理

导读：我正在研究TSP的一个变种,其中每个节点还有一个必须遵守的“时间窗口”.由于我使用遗传算法来解决TSPTW,我想知道什么可能是一些可能适用于TSPTW的交叉技术. 谢谢. 解决方法这只是空闲的推测,但标准TSP往往会受益于尝试保留父游览中节点邻接的操作符.因此,重

我正在研究TSP的一个变种,其中每个节点还有一个必须遵守的“时间窗口”.由于我使用遗传算法来解决TSPTW,我想知道什么可能是一些可能适用于TSPTW的交叉技术.

谢谢.

这只是空闲的推测,但标准TSP往往会受益于尝试保留父游览中节点邻接的操作符.因此,重要的不是城市X出现在特定位置,而是它出现在城市Y和Z旁边,无论它们出现在字符串中的哪个位置.像Edge Assembly Crossover(EAX)这样的操作符专门设计用于尝试利用这种结构.

在你的情况下,时间窗口可能意味着,与TSP不同,像01234567这样的旅行与56701234之类的旅行不同,因此旅游中城市的绝对位置也很重要.在像绝对位置很重要的QAP这样的情况下,人们倾向于做像Cycle Crossover(CX)这样的事情.

如果我致力于解决这个问题的GA,我可能会先做一些明显的事情,比如实现CX和EAX并随机选择它们.或者,您可能会尝试设计一个混合运算符,它将两者的元素组合在一起,但这可能相当不重要.

然而,我怀疑GA可能不是这里的方式,或者至少,黑盒GA可能会受到影响.例如,试图使用来自问题实例的语义信息的操作符倾向于将城市彼此靠近分组(如果他们具有相似的时间窗口)可能是有效的.我的5美元表示,在任何情况下,一个好的本地搜索算法(禁忌搜索,可变邻域搜索等)可能会击败GA,尽管这只是基于预感.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!