java - 模拟退火 TSP

Question

我希望在 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();
    }
}

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接口(interface)，例如TspProblemInstance implements State<TspProblemInstance> .该算法是通用的，将返回类 TspProblemInstance 的最佳(或非常接近最佳的结果)对象。 .因此，实现 copy 很重要方法认真。通用参数 T受实现类的约束，i。 e.副本将始终具有类型 T (也可以是子类型)。

您应该在接口(interface)的具体实现中添加一些方法，以显示城市的顺序等。State 中的方法接口(interface)只是算法工作的最低限度。

我推荐 wiki article进一步阅读。这里还有另外两个实现，first有点复杂，second相当简单，但是很老套(并且不保持一般)。但它们应该会让您对模拟退火有更多的了解。