sa.java

使用模拟退火算法求解TSP（旅行商）问题的JAVA源程序

public class SA {
	final static double SA_K = 1; // Boltzman 常数
	final static double SA_ARF = 0.96; // 温度控制参数 t_(k+1)=t_k*SA_ARF
	final static double SA_DEART = 1e-10; // 温度终止条件 当t<SA_DART时终止
	final static double SA_TMPRCH = 8000; // 初始温度
	final static int SA_ITERATIONS = 100; // 总迭代次数
	
	Methord mthd_f;
	double targetFun; // 最优目标函数值

	double targetX[]; // 目标解

	/**
	 * 初始化函数
	 */
	SA() {
		mthd_f = new TSP();//为了防止没有初始化
		if (mthd_f.getLen() == 0)// 初始化
			mthd_f.init();
		targetX = new double[mthd_f.getLen()];
	}

	/**
	 * 初始化函数
	 * @param msd
	 *           用于初始化SA算法的方法
	 */
	SA(Methord msd) {
		mthd_f = msd;
		if (mthd_f.getLen() == 0)// 初始化
			mthd_f.init();
		targetX = new double[mthd_f.getLen()];
	}

	/**
	 * SA的主算法函数
	 */
	public void sa() {

		double tmpFun; // 临时目标函数值
		double lastFun; // 上次目标函数值
		double lastX[] = new double[mthd_f.getLen()]; // 上次的解

		double t;
		int i;

		/**
		 * 记录初始解
		 */
		mthd_f.getCopyX(lastX);
		lastFun = mthd_f.f();
		targetFun = lastFun;
		mthd_f.getCopyX(targetX);

		for (t = SA_TMPRCH; t > SA_DEART; t = t * SA_ARF) {
			for (i = 0; i < SA_ITERATIONS; i++) {
				mthd_f.getNextX();
				tmpFun = mthd_f.f();

				if ((tmpFun < lastFun)
						|| Math.random() < sa_r(tmpFun, lastFun, t)) {// 接受新解
					mthd_f.getCopyX(lastX);// 保留新解
					lastFun = tmpFun;

					if (lastFun < targetFun) {
						mthd_f.getCopyX(targetX);// 保留最优解
						targetFun = lastFun;
					}
				} else {
					mthd_f.setX(lastX); // 保留原来的解
				}
			}
		}

	}

	/**
	 * 用于计算接受新解的概率R 如果fx_c<fx_0，无条件接受新解，否则以概率接受新解
	 * 
	 * @param fx_c
	 *            新解x_c的目标函数值
	 * @param fx_0
	 *            上一步解的目标函数值
	 * @param t
	 *            当前温度T
	 * @return 如果新的目标函数值小于上一步的目标函数值，则返回概率1， 否则以相应的方法计算相应的接受概率并返回
	 */
	private double sa_r(double fx_c, double fx_0, double t) {
		return fx_c < fx_0 ? 1.0 : Math.exp((fx_0 - fx_c) / (SA_K * t));
	}

	public String toString() {
		String result = ("\n==SA==> FBEST:" + targetFun+"\nAnd the BEST X:");;
		for (int i = 0; i < mthd_f.getLen(); i++) {
			result += ("[" + i + "]=" + targetX[i] + " ");
		}
		
		return result;
	}

}