sacompute.java

模拟退火算法通用类,改编自TSP问题求解

package org.flytinge.tsp;
/**
 * 模拟退火算法
 * @author acer
 *
 * @param <T>
 */
public abstract class SACompute<T> implements Runnable {
	private T initAnswer;
	private T resultAnswer;
	
	public SACompute(T initAnswer) {
		this.initAnswer = initAnswer;
	}
	
	/**
	 * 获取初始温度
	 * 
	 * @return
	 */
	public abstract double getInitTemplate();

	/**
	 * 获取临近解
	 * 
	 * @param current
	 * @param nowTemperature
	 * @param nowExternalIterateNumber
	 * @param nowInnerIterateNumber
	 * @return
	 */
	public abstract T getNearbyAnser(T current, double nowTemperature,
			int nowExternalIterateNumber, int nowInnerIterateNumber);

	/**
	 * 获取两个解的评价值之差
	 * 
	 * @param answer1
	 * @param answer2
	 * @return
	 */
	public abstract double getDeltaValue(T answer1, T answer2);

	/**
	 * 是否退出内部循环
	 * 
	 * @param nowInnerIterateNumber
	 * @return
	 */
	public abstract boolean exitInnerLoop(int nowInnerIterateNumber);

	/**
	 * 是否退出外部循环
	 * 
	 * @param nowExternalIterateNumber
	 * @return
	 */
	public abstract boolean exitExternalLoop(int nowExternalIterateNumber, double nowTemperature);

	/**
	 * 外部循环降温
	 * 
	 * @param nowTemperature
	 * @param nowExternalIterateNumber
	 * @return
	 */
	public abstract double countDownTemperature(double nowTemperature,
			int nowExternalIterateNumber);
	
	/**
	 * 开始运行
	 */
	public void run() {
		double nowTemperature = getInitTemplate();
		int nowExternalIterNumber = 0;
		int nowInnerIterNumber = 0;
		resultAnswer = initAnswer;
		
		while (true) {
			double deltatotaldis = 0.0;
			while (true) {
				T nearbyAnswer = getNearbyAnser(resultAnswer,
						nowTemperature, nowExternalIterNumber,
						nowInnerIterNumber);

				// 从某路径的邻域中随机选择一个新的路径，邻域映射为2-opt
				deltatotaldis = getDeltaValue(nearbyAnswer, resultAnswer);
				// 计算新路径与当前路径的路程长度差值
				if (deltatotaldis <= 0.0)
					resultAnswer = nearbyAnswer; // 如果新路径的路程短，则用它替换当前路径
				else {
					double chgprobability = Math
							.exp(-(deltatotaldis / nowTemperature));
					double random = Math.random();
					if (chgprobability > random)
						resultAnswer = nearbyAnswer;
					// 如果新路径长于当前路径，但exp(-Δf/t) > random(0,1)，则仍然替换当前路径
				}
				if (exitInnerLoop(nowInnerIterNumber))
					break; // 判断内循环是否结束，结束则跳出当前温度的内循环
				else
					nowInnerIterNumber++; // 判断内循环是否结束，不结束则继续内循环
			}
			if (exitExternalLoop(nowExternalIterNumber, nowTemperature))
				break; // 判断外循环是否结束，结束则结束模拟退火计算
			else {
				nowTemperature = countDownTemperature(nowTemperature,
						nowExternalIterNumber);
				nowExternalIterNumber++;
				nowInnerIterNumber = 0;
				// 判断外循环是否结束，不结束则计算出下降后的温度，并继续循环
			}
		}
	}
	
	public static void main(String[] args) {
		System.out.println(Math.exp(-5));
	}
}