模擬退火TSP

我期待在Java中實現模擬退火算法以找到Travelling Salesman Problem的最佳路線，到目前爲止，我已經實現了蠻力，我期待修改代碼才能使用模擬退火。顯然，強力和模擬退火是非常不同的，並且使用非常不同的功能。模擬退火TSP

我明白模擬退火使用稱爲然後冷卻作爲算法運行溫度的變量;溫度從高處開始並逐漸降溫。雖然溫度較高，但該算法更可能選擇比當前更差的解決方案，從而消除了類似爬山算法中的局部最大值。當它冷卻時，算法不太可能接受更差的解決方案，因此它可以專注於特定區域，並且可以快速找到最佳路線。

我相信，我明白是怎麼算法的作品，但我有麻煩把這個成Java，我有2個班;一個稱爲市剛剛包含的方法制定出每個城市的詳細信息，如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(); 
    } 
}

來源

2013-06-24 user2517280

看看http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6。它提供了一個關於如何使用模擬退火來解決TSP問題的詳盡例子。

來源

2013-08-18 17:55:19 mmicheo

我不想表現出太多的代碼，因爲它是屬於我的正在進行的學士論文的應用程序的一部分。但是，你走了。算法應該保持非常一般。看一看。爲你的算法可以解決任何問題的基礎算法

// 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接口

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（子類型也是可能的）。

您應該在界面的具體實現中添加一些方法，向您展示城市的順序等.界面中的方法只是算法工作的最低限度。

我建議wiki article進一步閱讀。在這裏，其他兩種實現方式中，first有點複雜，second是相當簡單的，但hackish的（而不是保持一般）。但是他們應該讓你更加了解模擬退火。

來源

2013-09-06 12:21:58 mike

回答

相關問題