模拟退火TSP

Question

我希望在Java中实现模拟退火算法，以便为Travelling Salesman Problem找到最优路由，到目前为止，我已经实现了蛮力，并希望修改代码以使用模拟退火。显然，蛮力和模拟退火是非常不同的，并且使用非常不同的功能。

我知道模拟退火使用了一个称为温度的变量，然后随着算法的运行而冷却；随着温度的升高，整个过程逐渐冷却。当温度较高时，算法更有可能选择比当前更差的解决方案，消除类似爬山算法中的局部最大值。随着降温，算法不太可能接受更糟糕的解决方案，因此它可以专注于特定区域，并快速找到最优路径。

我相信我知道算法是如何工作的，但在将其放入Java语言时遇到了问题，我有两个类；一个名为City的类，它只包含计算每个城市的详细信息的方法，如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();
    }
}

Answer 1

我不想展示太多的代码，因为它是属于我正在进行的学士论文的应用程序的一部分。但这是你的。算法应该保持非常通用。瞧一瞧。

算法的主要部分

// 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<T extends State<T>>
{
  public void step();
  public void undo();
  public int energy();
  public T copy();
}

有了这个作为你的算法的基础，你可以解决任何问题。不仅仅是TSP。你只需要实现State接口，比如TspProblemInstance implements State<TspProblemInstance>。该算法是通用的，将返回TspProblemInstance类的最优对象(或非常接近最优的结果)。因此，努力实现copy方法是很重要的。泛型参数T由实现类绑定，即副本将始终具有类型T (也可以是子类型)。

您应该在接口的具体实现中添加一些方法，以显示城市的顺序等。State接口中的方法只是算法要处理的最小方法。

我建议您进一步阅读wiki article。这里还有另外两个实现，first有点复杂，而second相当简单，但有点像黑客(而且不是通用的)。但它们应该会让你对模拟退火有更多的了解。

Answer 2

看看http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6吧。它提供了一个很好的例子，说明了如何使用模拟退火来解决TSP问题。