And*_*hin 12 c# algorithm artificial-intelligence traveling-salesman genetic-algorithm
我正试图用遗传算法解决旅行商问题(TSP).我的基因组是图中顶点的排列(推销员的路径).
我该如何对基因组进行交叉操作？
我在哪里可以找到C#中我的问题的实现？
Raf*_*ird 12
您应该检查" 的TSP避免特殊交叉和变异的遗传算法解决方案 "由格克蒂尔克Ucoluk.它概述了排列的特殊交叉算子,并提出了一种巧妙的排列表示,它可以很好地与标准交叉相结合(即交叉两个排列总是产生两个排列).
关键见解是表示置换作为其反转序列,即,对于每个元件i中,存储a[i]有多少个元素大于i是左侧i中置换.与直接表示不同,唯一的约束a[i]是局部的,即a[i]不能大于N - i.这意味着两个有效反演序列的简单交叉总是产生两个有效的反转序列 - 不需要对重复元素进行特殊处理.
而不是使用标准GA交叉技术(如MusiGenesis所述),最好使用有序交叉来解决旅行商问题.
通常的方法对于TSP来说效果不好,因为适应度函数对进化路线中不同城市的相对位置非常敏感,而不是它们的绝对位置.例如,如果你访问的所有欧洲国家的首都,最短的路线并没有真正取决于您是否参观布拉迪斯拉发1日,2日,9日或.更重要的是,您在访问维也纳之前或之后立即访问它,而不是访问赫尔辛基,雅典和其他6个国家的首都.
当然,正如mjv也指出的那样,传统的交叉也会在你的路线中引入重复.如果父母一方拥有位置2的巴黎而另一方拥有位于第14位的巴黎,则交叉可能会导致一条进化路线两次访问巴黎(并错过另一个城市),另一条进化路线根本不访问巴黎.有序的交叉遗传算子不会遇到这个问题.它保留元素并修改排序.