TSP解决方案解读

Question

This is mostly a consulting question.

我开发了一种遗传算法来解决 TSP, long story short, I have written two different codes the and i used this 作为我的数据集。程序找到的解决方案如下所示。

很明显，第一个程序 (Prog# 1) 的建议解决方案比第二个程序 ([=14) 更有希望=])待优化； Prog# 2 的解决方案似乎很可能是随机解决方案。

但是 Prog# 1 的成本是 97314.36 而 Prog# 2 是 74635.31 比 Prog# 1 的解决方案成本几乎 20K 小 ，并且成本是建议 Prog# 2 找到的解决方案应该 比第一个解决方案优化得多。

问题

1) 为什么 Prog# 2 找到的解的路径图不支持（视觉上）计算的成本值？

2) 考虑到打击脚本，有什么我遗漏的吗？

为了完整性，我 post 我用来绘制和计算成本值的脚本。

function tsp_plot_output() 
    close all;
    disp('loading data....');
    x=load('out.res'); 
    dist = 0;
    for i=1:2:size(x, 1)-1
        dist = dist + norm(x(i,:) - x(i+1,:), 2);
    end
    dist = dist + norm(x(1,:) - x(end,:), 2);
    fprintf('COST IS: %.2f\n', dist);
    disp('ploting data....');
    xx = x(:,1); xy = x(1:size(xx, 1),2);
    zxx = x(:,1); zxy = x(1:size(zxx),2);
    plot(xx, xy), title('Found TSP solution');
    hold
    plot(zxx, zxy, 'r.');
end

我在Prog# 1中用来倒出解决方案的代码是

std::ofstream os(outputfile);
BOOST_FOREACH(size_t city, *best->_genes) {
    auto loc = _data->get(city);
    os<<loc.longitude<<" "<<loc.latitude<<endl;
}
os.close();

和 Prog# 2

中的相同代码

ofstream out(jconfig["output-file"].as_string());
for(int i = 0; i < p->lchrom; i++) {
    city c = data.at(best_found->chrom[i]);
    out<<c.x<<" "<<c.y<<endl;
}
out.close();

Answer 1

你在 MATLAB 中的距离计算是错误的。你有：

dist = 0;
for i=1:2:size(x, 1)-1
    dist = dist + norm(x(i,:) - x(i+1,:), 2);
end
dist = dist + norm(x(1,:) - x(end,:), 2);

使用 for i=1:2:size(x,1)-1，您从 i=1 开始，然后在每个步骤中添加 2，直到达到 size(x,1)-1。因此，您添加从 1-2 到 3-4 的距离，依此类推。当然应该是从1-2，然后是2-3等等。这是通过

实现的

dist = 0;
for k=1:size(x,1)-1
    dist = dist + norm(x(k+1,:) - x(k,:),2);
end
dist = dist + norm(x(end,:) - x(1,:),2);

例如 x = [0,0; 1,1; 1,0] 旧例程返回 2.4142，而更正后的例程 returns 返回正确的 sqrt(2) + 1 + 1 = 3.4142。

PS：我把运行变量改成了k，因为在MATLAB中i代表虚数单位（详见this question） . 我还更改了 norm 中 x 的顺序。当然你的没有错，但是这样很明显你把矢量从当前点 k 带到下一个点 k+1 而不是另一个方向。

TSP解决方案解读

TSP solution interpretation

c++

algorithm

matlab

octave

genetic-algorithm

问题