标签: traveling-salesman

我正试图用遗传算法解决旅行商问题(TSP).我的基因组是图中顶点的排列(推销员的路径).

我该如何对基因组进行交叉操作？

我在哪里可以找到C#中我的问题的实现？

我已经实施了遗传算法来解决旅行商问题(TSP).当我只使用变异时,我找到了比添加交叉时更好的解决方案.我知道正常的交叉方法对TSP不起作用,所以我实现了Ordered Crossover和PMX Crossover方法,并且都遭受了糟糕的结果.

以下是我正在使用的其他参数:

突变:单一交换突变或倒置子序列突变(如Tiendil所述),突变率测试在1%和25%之间.

选择:轮盘赌轮选择

健身功能:1 /旅游距离

人口规模:测试100,200,500,我也运行GA 5次,以便我有各种起始种群.

停止条件:2500代

使用26个点的相同数据集,我通常使用具有高突变率的纯突变获得大约500-600距离的结果.添加交叉时,我的结果通常在800距离范围内.另一个令人困惑的事情是,我也实现了一个非常简单的爬山算法来解决这个问题,当我运行1000次我避开410-450距离的结果,我希望(不是运行GA快5倍)使用GA获得更好的结果.

当我添加交叉时,有关为什么我的GA表现更差的任何想法？为什么它比一个简单的Hill-Climb算法表现得更差,它应该卡在局部最大值上,因为它一旦找到局部最大值就无法探索？

我正在尝试为这个问题提出一个合理的算法:

假设你有一堆球.每个球至少有一种颜色,但也可以是多色的.每个球都有一个重量和一个与之相关的值.还有一堆盒子,每个盒子只有一种颜色.每个盒子都有最多可以容纳的球.目标是在保持总重量W的同时最大化盒子中的值的总和,唯一的规则是:

为了将球放入盒子中,它必须至少具有盒子的颜色

(例如,您可以将蓝色和绿色球放入蓝色框或绿色框中,但不能放入红色框中.)

我已经进行了一些研究,这看起来类似于背包问题,也类似于匈牙利算法可以解决,但我似乎无法将其减少到任何一个问题.

我只是好奇是有这种类型的问题的某种动态编程算法使它在多项式时间内可解决,或者它只是伪装的旅行推销员问题.如果我知道最多有X种颜色会有用吗？任何帮助是极大的赞赏.如果它有帮助,我也可以用变量名称来形式化这个问题.谢谢!

这是一个简单的例子:

最大重量: 5

球:

1个红球 - (值= 5,重量= 1)

1个蓝色球 - (值= 3,重量= 1)

1个绿色/红色/蓝色球 - (值= 2,重量= 4)

1个绿色/蓝色球 - (值= 4,重量= 1)

1个红色/蓝色球 - (值= 1,重量= 1)

盒:

1红色(1个球)

1蓝色(可容纳2个球)

1绿色(持1个球)

最优方案:

在红色框中的红球

蓝色的球和蓝色框中的红色/蓝色球

绿色框中的绿色/蓝色球

总价值:13(5 + 3 + 1 + 4)

总重量:4(1 + 1 + 1 + 1)

注意:即使绿色/红色/蓝色球比红色/蓝色球更有价值,它的重量也会让我们超过极限.

编辑:

一个澄清点:具有相同颜色组合的球不一定具有相同的重量和值.例如,你可以有一个值为3且重量为1的红色球和另一个值为2且重量为5的红色球.

编辑2:

如果它有助于我们提出动态编程算法,我们可以假设整数权重和值.

如何在python中解决旅行商问题？我没有找到任何库,应该有一种方法使用scipy函数进行优化或其他库.

我的hacky-extremelly-lazy-pythonic强制解决方案是:

tsp_solution = min( (sum( Dist[i] for i in izip(per, per[1:])), n, per) for n, per in enumerate(i for i in permutations(xrange(Dist.shape[0]), Dist.shape[0])) )[2]

其中Dist(numpy.array)是距离矩阵.如果Dist太大,这将需要永远.

建议？

我查看了类似的问题但找不到与我的问题相关的任何内容.我在努力寻找"回路",将找到一个路径的算法或设置CityA到CityB,使用数据库的

distance(City1,City2,Distance)

事实.到目前为止我设法做的是下面,但它总是回溯,write(X),然后在最后的迭代中完成,这是我想要它做的但只是在一定程度上.

例如,我不希望它打印出任何死胡同的城市名称,或者使用最后的迭代.我希望它基本上建立一条路径,CityA在路径上CityB写下它所去的城市的名称.

我希望有人可以帮助我!

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).

注意:由于旅行不是在它开始的同一个地方结束的事实,而且只要我仍然访问所有这些点,每个点都可以被访问多次这一事实,这不是真正的TSP变体,而是我之所以说是因为缺乏对问题的更好定义.

所以..

假设我正在徒步旅行,有n个兴趣点.这些景点都通过远足径相连.我有一张地图显示了所有距离的路径,给我一个有向图.

我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游,同时结束旅行的任何地方,但我开始的点,我希望旅游尽可能短.

由于远足的性质,我认为这可能不是一个对称问题(或者我可以将我的不对称图转换为对称图？),因为从高海拔到低海拔显然比其他方式更容易.

另外我认为它必须是一种适用于非度量图的算法,其中不满足三角不等式,因为从a到b到c可能比从a到c的真正漫长而奇怪的道路更快直.我确实考虑过三角不等式是否仍然存在,因为对于我访问每个点的次数没有限制,只要我访问所有这些,这意味着我总是选择从a到c的两条不同路径中最短的路径,从而永远不会抓住漫长而奇怪的道路.

我相信我的问题比TSP更容易,因此这些算法不适合这个问题.我考虑过使用最小生成树,但我很难说服自己可以将它们应用于非度量非对称有向图.

我真正想要的是关于如何能够提出近似算法的一些指示,该算法将通过所有n个点找到近乎最佳的旅行

我有一个求解器可以解决正常的对称TSP问题.解决方案意味着通过所有节点的最短路径,而不限制哪个节点是路径中的第一个节点和最后一个节点.

有没有办法转换问题,以便确保特定节点作为起始节点,另一个节点作为终端节点？

一种方法是将I - 一个非常大的距离 - 添加到这些起始/结束节点和所有其他节点之间的所有距离(在起始节点和结束节点之间的距离上加两倍),因此解算器很想仅访问它们一次(从而使它们成为路径的起点和终点).

这种方法有什么大的缺点,还是有更好的方法来做到这一点？

我在一家快递公司工作.我们目前通过"手"解决了50多个地点的路线.

我一直在考虑使用谷歌地图API解决这个问题,但我已经读到有24点的限制.

目前我们在服务器中使用rails,所以我正在考虑使用ruby脚本来获取50多个位置的坐标并输出合理的解决方案.

你会用什么算法来解决这个问题？

Ruby是一种很好的编程语言来解决这类问题吗？

你知道任何现有的ruby脚本吗？

我知道这是一个相当频繁的问题(一般来说是tsp),但我已经被它困住了一段时间了.我希望在给定一组x,y坐标的情况下找到最小距离哈密顿路径.起点和终点完全是任意的,但它不能循环,所以标准的tsp出来了(虽然假设在0距离处向所有其他节点添加一个虚拟点,然后在以后删除它有效,我不知道我是怎么做的).

有很多链接到数学论文等讨论算法来解决类似的问题,但我宁愿使用代码而不是复杂的方程式,我真的宁愿不重新发明轮子.

当然,在主要语言java,c#,c ++,ruby,javascript,php等中有一个相当简单的实现,它可以解决我的问题的~20节点版本.

编辑:我也在寻找尽可能准确,显然它不能完全准确为20!有很多排列,但是等于或优于人类在几分钟内可以做的事情将是完美的.

编辑2:另外澄清一下,我正在使用未加权图上的标准二维坐标.距离A-> B == B-> A.

编辑3: 为了消除混淆,这里有一个视觉示例,只有几个点来说明tsp如何不是最理想的(这种情况是一个简单的修复,但有更多的节点,它可能更极端).

TSP减去最长段(红线)

期望的输出

问题

我正在寻找一种方法来有效地对固定对象周围发生的随机选择的采样横断面进行排序。这些横断面一旦生成，就需要以一种在空间上有意义的方式进行排序，以使行进的距离最小化。这将通过确保当前横断面的终点尽可能靠近下一个横断面的起点来实现。此外，没有一个横断面可以重复。

因为有数千条断面需要订购，这是手动完成的一项非常繁琐的任务，我正在尝试使用 R 来自动化此过程。我已经生成了横断面，每个横断面都有一个起点和终点，其位置使用 360 度系统表示（例如，0 是北，90 是东，180 是南，270 是西）。我还生成了一些似乎指示下一个横断面的起点和 ID 的代码，但此代码存在一些问题：(1) 根据所考虑的起点和终点，它可能会产生错误，(2 ) 它没有实现我最终需要它实现的目标，并且 (3) 照原样，代码本身似乎过于复杂，我不禁想知道是否有更直接的方法来做到这一点。

理想情况下，代码将导致横断面被重新排序，以便它们匹配它们应该飞行的顺序，而不是它们最初输入的顺序。

数据

为简单起见，我们假设只有 10 个横断面需要排序。

# Transect ID for the start point
StID <- c(seq(1, 10, 1))

# Location of transect start point, based on a 360-degree circle
StPt <- c(342.1, 189.3, 116.5, 67.9, 72, 208.4, 173.2, 97.8, 168.7, 138.2)

# Transect ID for the end point
EndID <- c(seq(1, 10, 1))

# Location of transect start point, based on a 360-degree …