优化算法——模拟退火算法

模拟退火算法原理

爬山法是一种贪婪的方法，对于一个优化问题，其大致图像(图像)如下图所示：

其目标是要找到函数的最大值，若初始化时，初始点的位置在 C C C处，则会寻找到附近的局部最大值 A A A点处，由于 A A A点出是一个局部最大值点，故对于爬山法来讲，该算法无法跳出局部最大值点。若初始点选择在 D D D处，根据爬山法，则会找到全部最大值点 B B B。这一点也说明了这样基于贪婪的爬山法是否能够取得全局最优解与初始值的选取由很大的关系。

模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。

模拟退火算法从某一较高的温度出发，这个温度称为初始温度，伴随着温度参数的不断下降，算法中的解趋于稳定，但是，可能这样的稳定解是一个局部最优解，此时，模拟退火算法中会以一定的概率跳出这样的局部最优解，以寻找目标函数的全局最优解。如上图中所示，若此时寻找到了 A A A点处的解，模拟退火算法会以一定的概率跳出这个解，如跳到了 D D D点重新寻找，这样在一定程度上增加了寻找到全局最优解的可能性。

模拟退火算法

模拟退火算法过程

(1)随机挑选一个单元 k k k，并给它一个随机的位移，求出系统因此而产生的能量变化 Δ E k \Delta E_k ΔEk​。
(2)若 Δ E k ⩽ 0 \Delta E_k\leqslant 0 ΔEk​⩽0，该位移可采纳，而变化后的系统状态可作为下次变化的起点；
若 Δ E k > 0 \Delta E_k> 0 ΔEk​>0，位移后的状态可采纳的概率为
 P k = 1 1 + e − Δ E k / T P_k=\frac{1}{1+e^{-{\Delta E_k}/{T}}} Pk​=1+e−ΔEk​/T1​
式中 T T T为温度，然后从 ( 0 , 1 ) \left ( 0,1 \right ) (0,1)区间均匀分布的随机数中挑选一个数 R R R，若 R < P k R< P_k R<Pk​，则将变化后的状态作为下次的起点；否则，将变化前的状态作为下次的起点。
(3)转第(1)步继续执行，知道达到平衡状态为止。

模拟退火算法流程

模拟退火算法的Java实现

求解函数最小值问题：
 F ( x ) = 6 x 7 + 8 x 6 + 7 x 3 + 5 x 2 − x y F\left ( x \right )=6x^7+8x^6+7x^3+5x^2-xy F(x)=6x7+8x6+7x3+5x2−xy
其中， 0 ≤ x ≤ 100 0\leq x\leq 100 0≤x≤100，输入任意 y y y值，求 F ( x ) F\left ( x \right ) F(x)的最小值。

##Java代码

package sa;

/**
 * 实现模拟退火算法
 * @author zzy
 *Email:[email protected]
 */
public class SATest {
	public static final int T = 100;// 初始化温度
	public static final double Tmin = 1e-8;// 温度的下界
	public static final int k = 100;// 迭代的次数
	public static final double delta = 0.98;// 温度的下降率

	public static double getX() {
		return Math.random() * 100;
	}

	/**
	 * 求得函数的值
	 * 
	 * @param x目标函数中的一个参数
	 * @param y目标函数中的另一个参数
	 * @return函数值
	 */
	public static double getFuncResult(double x, double y) {
		double result = 6 * Math.pow(x, 7) + 8 * Math.pow(x, 6) + 7
				* Math.pow(x, 3) + 5 * Math.pow(x, 2) - x * y;

		return result;
	}
	
	/**
	 * 模拟退火算法的过程
	 * @param y目标函数中的一个参数
	 * @return最优解
	 */
	public static double getSA(double y) {
		double result = Double.MAX_VALUE;// 初始化最终的结果
		double t = T;
		double x[] = new double[k];
		// 初始化初始解
		for (int i = 0; i < k; i++) {
			x[i] = getX();
		}
		// 迭代的过程
		while (t > Tmin) {
			for (int i = 0; i < k; i++) {
				// 计算此时的函数结果
				double funTmp = getFuncResult(x[i], y);
				// 在邻域内产生新的解
				double x_new = x[i] + (Math.random() * 2 - 1) * t;
				// 判断新的x不能超出界
				if (x_new >= 0 && x_new <= 100) {
					double funTmp_new = getFuncResult(x_new, y);
					if (funTmp_new - funTmp < 0) {
						// 替换
						x[i] = x_new;
					} else {
						// 以概率替换
						double p = 1 / (1 + Math
								.exp(-(funTmp_new - funTmp) / T));
						if (Math.random() < p) {
							x[i] = x_new;
						}
					}
				}
			}
			t = t * delta;
		}
		for (int i = 0; i < k; i++) {
			result = Math.min(result, getFuncResult(x[i], y));
		}
		return result;
	}

	public static void main(String args[]) {
		// 设置y的值
		int y = 0;
		System.out.println("最优解为：" + getSA(y));
	}

}

最后的结果

最优解为：1.733360963664572E-16