模拟退火算法解决TSP问题（旅行商问题）JAVA版代码

package com.color.tsp; import java.util.Collections; /** * 模拟退火算法 * * @author Color * */ public class SimulatedAnnealing { /** * 城市总数 */ private final static int CITY_NUM = 30; /** * 系统初始温度。说白了就是为了和温度下限拉开差距设定的一个初始值而已 */ private static double INIT_TEMP = 3000; /** * 温度下限 */ private final static double MIN_TEMP = 0.0001; /** * 设定每一次降温之前，需要进行的迭代次数 */ private final static double LOOP = 1000; /** * 退火速率 */ private final static double COLLING_RATE = 0.98; /** * 存放当前的旅行者的旅行路线和距离总和 */ private Traveler currentTraveler; /** * 初始化模拟退火算法的需要的数据，尚未开始旅行，所以distance=0 */ public void init() { //产生一个初始的旅行者 Traveler traveler = new Traveler(); // 随机添加CITY_NUM个城市 traveler.addCities(CITY_NUM); // 打乱一下city顺序 Collections.shuffle(traveler.getCities()); // 打印一下初始化的信息 traveler.toString(); currentTraveler = traveler; } /** * 退火算法应用，注意参考伪代码逻辑步骤 * * @return */ public Traveler annealingAlg() { System.out.println("=================开始进行模拟退火算法计算旅行路线================="); Traveler srcTraveler = new Traveler(currentTraveler.getCities()); Traveler traveler = null; //存放降温次数 int colling_count=0; /** * 通过退火速率进行逐步降温 */ while (INIT_TEMP > MIN_TEMP) { /** * 每次降温需要经过LOOP次迭代 * */ for (int i = 0; i < LOOP; i++) { //每次迭代，随机交换两个城市的位置， traveler = currentTraveler.swapRandomCity(); //并计算交换之前和交换之后的总距离 double beforeSwapDistance = currentTraveler.getDistance(); double afterSwapDistance = traveler.getDistance(); //比较下一个状态与当前状态的差值,差值>=0,移动后得到更优的解，那么总是接受改移动 //差值 < 0，exp(dE / T)说明了温度越高出现一次能量差为dE的降温概率就越大，温度越低 //出现降温的概率就越小，由于差值总是小于0，所以P(dE)取值在0到1之间，则以一定的概率接受该移动 if (accept(beforeSwapDistance, afterSwapDistance, INIT_TEMP) > Math.random()) { //也就是接受上面随机交换两个城市位置之后的城市旅游路线 currentTraveler=traveler; } if (currentTraveler.getDistance() < srcTraveler.getDistance()) { //保存拥有最短距离的城市旅游路线 srcTraveler = new Traveler(currentTraveler.getCities()); } } INIT_TEMP *= COLLING_RATE; System.out.println(String.format("第%d次降温，当前温度是：%s,下限温度是：%s", ++colling_count,INIT_TEMP,MIN_TEMP)); } System.out.println("===============模拟退火算法计算结束，旅行城市坐标是：=================="); srcTraveler.toString(); return srcTraveler; } /** * 比较下一个状态与当前状态的差值,看是否可以接受 * * @param src 原状态值 * @param dest 下一个状态值 * @param temperature 当前温度 * @return */ private double accept(double src, double dest, double temperature) { if (src >= dest) { //速率不变 return 1.0; } return Math.exp((src - dest) / temperature); } }