模拟退火算法TSP [英] Simulated Annealing TSP

问题描述

我希望在Java中实现模拟退火算法，以查找旅行商问题的最佳途径，到目前为止，我已经实现了蛮力，我期待到修改code才能使用模拟退火。显然，蛮力和模拟退火是非常不同的，使用非常不同的功能。

我理解模拟退火使用被称为然后冷却的算法运行温度的变化;随着温度的起始高度和整个逐渐冷却。虽然温度是高的算法是更可能选择的解决方案，是比当前更差，消除了局部最大值作为你会发现的类似爬山算法在。在冷却的算法更不太可能接受更糟解，因此它可以集中在一个特定的区域和的最佳路径被快速找到。

我相信我理解算法如何工作的，但我有麻烦把这个到Java，我有2个班;一个叫城市，只是包含的方法来找出每个城市的详细信息，如 getIndex ， getDistance的等。 该算法类从输入文件并将其存储在一个阵列读取（ INT [] [] ）

在code以下的算法蛮力而这正是我想修改做模拟退火相反，如果有人可以帮助我做到这一点我倒是AP preciate它大量

 公共静态无效doBF（）
{
    INT random1 = generateRand（）;

    如果（towns2.size（）＆GT; random1）
    {
        镇镇= towns2.get（random1）;
        visitedTowns [我] =镇;
        towns2.remove（镇）;
        我++;
        如果（lastTown！= 1000）
        {
            征途+ = town.getDistance（lastTown）;
        }
        lastTown = town.getIndex（）;
    }
    其他
    {
        doBF（）;
    }
}
 

解决方案

我不想表现出太多的code，因为它是属于我的正在进行的学士论文应用程序的一部分。但在这里你去。该algorihtm应保持很一般。一起来看看。

算法的主体

//人能检查最小Q因子，以满足在这里 而（温度→1） {   state.step（）;   INT下一= state.energy（）;   如果（acceptEnergyLevel（下））   {     能源=下一个;     如果（能源与LT; minEnergy）     {       minState = state.copy（）;       minEnergy =能量;     }   }   其他     state.undo（）;   温度* = DECAY_RATE; }

状态的界面

公共接口国家＆LT;吨扩大国家＆LT; T＆GT;＆GT; {   公共无效的步骤（）;   公共无效撤消（）;   公众诠释能源（）;   公共牛逼副本（）; }

以此为基础的算法，可以解决任何问题。不只是TSP。你只需要执行国家界面，如 TspProblemInstance实现国家＆LT; TspProblemInstance＆GT; 。该算法是通用的，将返回最优（或结果非常接近最优）类的对象 TspProblemInstance 。因此，你认真落实复制的方法是很重要的。泛型参数 T 由实现类的约束，我。即副本将始终有型 T （子类型也可以）。

您应该添加一些方法，以你的具体接口的实现，是您展示城市等在国家接口中的方法的顺序是唯一的最小值该算法去努力。

我推荐的维基文章进一步阅读。和这里另外两个实施方案中，<一href="http://aima-java.google$c$c.com/svn/trunk/aima-core/src/main/java/aima/core/search/local/SimulatedAnnealingSearch.java"相对=nofollow>第一是有点复杂，的第二是相当简单的，但hackish的（和不可以保持一般）。但是，他们应该给你模拟退火更多的了解。

I'm looking to implement the simulated annealing algorithm in Java to find an optimal route for the Travelling Salesman Problem, so far I have implemented brute force and am looking to modify that code in order to use simulated annealing. Obviously brute-force and simulated annealing are very different and use very different functions.

I understand simulated annealing uses a variable known as the temperature which then cools as the algorithm runs; with the temperature starting high and it gradually cooling throughout. Whilst the temperature is high the algorithm is more likely to choose solutions which are worse than the current, eliminating local maxima as you'd find in the similar hill-climbing algorithm. As it cools the algorithm is more unlikely to accept worse solutions and so it can focus on a specific area and an optimum route is found quickly.

I believe I understand how the algorithm works but am having trouble putting this into Java, I have 2 classes; one called City which just contains methods to work out details of each city such as getIndex, getDistance, etc. The algorithm class reads from an input file and stores it in an array (int [][])

The code below is the algorithm for brute-force which is what I want to modify to do simulated annealing instead, if anyone could help me do that I'd appreciate it massively.

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();
    }
}

解决方案

I don't want to show too much code, since it's part of an application belonging to my ongoing bachelor thesis. But here you go. The algorihtm should be kept very general. Take a look.

MAIN PART OF ALGORITHM

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

With this as basis for your algorithm you can solve any problem. Not just TSP. You just have to implement the State interface, e.g. TspProblemInstance implements State<TspProblemInstance>. The algorithm is generic and will return the optimum (or a result very near to the optimum) object of class TspProblemInstance. Therefore it is important that you implement the copy method diligently. The generic parameter T is bound by the implementing class, i. e. the copy will always have type T (a subtype could also be possible).

You should add some methods to your concrete implementation of the interface, that show you the sequence of the cities etc. The methods in the State interface are only the minimum for the algorithm to work on.

I recommend the wiki article for further reading. And here two other implementations, the first is a bit complex, and the second is rather simple, but hackish (and not kept general). But they should give you more understanding of simulated annealing.

这篇关于模拟退火算法TSP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！