5

我希望在 Java 中实现模拟退火算法，以找到旅行商问题的最佳路线，到目前为止，我已经实现了蛮力，并希望修改该代码以使用模拟退火。显然蛮力和模拟退火是非常不同的，并且使用非常不同的功能。

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

我相信我了解该算法的工作原理，但在将其放入 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();
    }
}
4

2 回答 2

6

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

算法的主要部分

// 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 文章以供进一步阅读。这里还有另外两个实现，第一个有点复杂，第二个相当简单，但是很hackish（并且不保持一般性）。但是它们应该让您对模拟退火有更多的了解。

于 2013-09-06T12:21:58.767 回答
1

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

于 2013-08-18T17:55:19.090 回答