java - 模拟退火TSP

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

我了解到模拟退火使用了一个称为温度的变量，该变量随后在算法运行时冷却。随着温度开始升高，并逐渐逐渐冷却。尽管温度很高，该算法更有可能选择比当前解决方案差的解决方案，从而消除了在类似的爬山算法中发现的局部最大值。随着算法的冷却，算法不太可能接受较差的解决方案，因此它可以专注于特定区域并快速找到最佳路线。

我相信我了解算法的工作原理，但是在将其放入Java时遇到了麻烦，我有2个类；一个叫做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();
    }
}

最佳答案

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

算法的主要组成部分

// 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;
}

STATE INTERFACE

public interface State<T extends State<T>>
{
  public void step();
  public void undo();
  public int energy();
  public T copy();
}

以此作为您算法的基础，您可以解决任何问题。不只是TSP。您只需要实现State接口(interface)，例如TspProblemInstance implements State<TspProblemInstance>。该算法是通用算法，将返回TspProblemInstance类的最优(或非常接近最优的)结果对象。因此，您必须勤奋地实现copy方法，这一点很重要。通用参数T由实现类i约束。 e。该副本将始终具有T类型(也可以是子类型)。

您应该在界面的具体实现中添加一些方法，以显示城市的顺序等。State界面中的方法只是该算法可以使用的最少方法。

我建议wiki article进行进一步阅读。在这里还有另外两个实现，first有点复杂，second相当简单，但是有点笨拙(并且不是保持通用)。但是它们应该使您对模拟退火有更多的了解。