ts.java

使用禁忌搜索算法求解TSP（旅行商问题）的JAVA源程序

public class TS {
	final static int TS_SIZE = 10;
	final static int TS_ITERATIONS = 100000;

	Methord mthd_f;
	double targetFun; // 最优目标函数值

	double targetX[]; // 目标解
	String tsList[]; // 禁忌表
	int listPoint;

	// 初始化
	TS() {
		mthd_f = new TSP();
		if (mthd_f.getLen() == 0)// 初始化
			mthd_f.init();
		targetX = new double[mthd_f.getLen()];
		tsList = new String[TS_SIZE];
		listPoint = 0;
	}

	/**
	 * 初始化
	 * 
	 * @param nMthd
	 *            计算的目标
	 */
	TS(Methord nMthd) {
		mthd_f = nMthd;
		if (mthd_f.getLen() == 0)// 初始化
			mthd_f.init();
		targetX = new double[mthd_f.getLen()];
		tsList = new String[TS_SIZE];
		listPoint = 0;
	}

	/**
	 * 更新禁忌表
	 */
	void change() {
		tsList[listPoint] = mthd_f.getChange();
		listPoint = (listPoint + 1) % TS_SIZE;
	}

	/**
	 * 查找禁忌表
	 * 
	 * @param strChange
	 *            需要查找的操作
	 * @return 如果是禁忌，则返回true，否则返回false
	 */
	Boolean findTaboo(String strChange) {
		Boolean rslt = false;
		for (int i = 0; i < TS_SIZE; i++) {
			if (strChange.equalsIgnoreCase(tsList[i]) == true) {
				rslt = true;
				break;
			}
		}
		return rslt;
	}

	// 打印输出结果
	public String toString() {
		String result = "\n==TS==> FBEST:" + targetFun + "\nAnd the BEST X is: ";
		for (int i = 0; i < mthd_f.getLen(); i++) {
			result += (" [" + i + "]=" + targetX[i]);
		}
		return result;
	}

	/**
	 * 主TS算法函数
	 */
	public void ts() {
		targetFun = mthd_f.f();
		mthd_f.getCopyX(targetX);

		double lastX[] = new double[mthd_f.getLen()];
		mthd_f.getCopyX(lastX);
		double lastFun = mthd_f.f();

		for (int i = 0; i < TS_ITERATIONS; i++) {
			mthd_f.getNextX();
			double tmpFun = mthd_f.f();

			if ( (tmpFun < lastFun && (findTaboo(mthd_f.getChange()) == false)) // 不在禁忌表内
					|| (tmpFun < targetFun)) { // 可以破禁
				if (tmpFun < targetFun) { // 更新最好解
					targetFun = tmpFun;
					mthd_f.getCopyX(targetX);
				}
				change();
				mthd_f.getCopyX(lastX);
				lastFun = tmpFun;
			} else { // 禁忌生效
				mthd_f.setX(lastX);
//				System.out.println("禁忌生效");
			}
		}
	}

}