模拟退火TSP
我正在寻找在Java中实现模拟退火算法以找到旅行商问题的最佳路线，到目前为止，我已经实施了暴力，并且正在寻找修改该代码以便使用模拟退火。 显然，蛮力和模拟退火是非常不同的，并且使用非常不同的function。
我知道模拟退火使用一个称为温度的变量，然后在算法运行时冷却; 温度从高处开始逐渐冷却。 虽然温度很高，但算法更可能选择比当前更差的解决方案，从而消除了类似爬山算法中的局部最大值。 由于它冷却，算法更不可能接受更糟糕的解决方案，因此它可以专注于特定区域，并且可以快速找到最佳路径。
我相信我理解算法是如何工作的，但是我把它放到Java中有困难，我有2个类; 一个名为City的城市， getDistance包含计算每个城市细节的方法，如getIndex ， getDistance等。算法类从输入文件读取并将其存储在数组中（ int [][] ）
下面的代码是蛮力的算法，这是我想要修改以进行模拟退火的算法，如果有人可以帮助我这样做，我会非常欣赏它。
public static void doBF() { int random1 = generateRand(); if (towns2.size() > random1) { Town town = towns2.get(random1); visitedTowns[i] = town; towns2.remove(town); i++; if (lastTown != 1000) { journey += town.getDistance(lastTown); } lastTown = town.getIndex(); } else { doBF(); } }
我不想显示太多的代码，因为它是属于我正在进行的学士论文的应用程序的一部分。 但是你走了。 algorihtm应该保持一般。 看一看。
算法的主要部分
// one could check for minimum q factor to be satisfied here while (temperature > 1) { state.step(); int next = state.energy(); if (acceptEnergyLevel(next)) { energy = next; if (energy < minEnergy) { minState = state.copy(); minEnergy = energy; } } else state.undo(); temperature *= DECAY_RATE; }
国家接口
public interface State> { public void step(); public void undo(); public int energy(); public T copy(); }
以此为基础，您可以解决任何问题。 不只是TSP。 您只需实现State接口，例如TspProblemInstance implements State 。 该算法是通用的，将返回类TspProblemInstance的最佳（或非常接近最佳的） TspProblemInstance 。 因此，努力实施copy方法非常重要。 generics参数T由实现类绑定，即副本将始终具有类型T （也可以是子类型）。
您应该为接口的具体实现添加一些方法，以显示城市的顺序等State接口中的方法只是算法要处理的最小值。
我推荐维基文章进一步阅读。 在这里另外两个实现，第一个是有点复杂， 第二个是相当简单，但hackish（并没有保持一般）。 但它们应该让你对模拟退火有更多的了解。
请查看http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6 。 它提供了一个很好的文档示例，说明如何使用模拟退火来解决TSP问题。