模拟退火算法

模拟退火算法

  模拟退火算法是上世纪80年代产生的优化算法，应用于在较大空间中寻找问题的最优解，也是解决TSP问题的一大利器。模拟退火是物质从无序（高温）逐渐趋向（降温）于有序（低温/恒温）的过程。因此在模拟退火算法优化的过程中，从始至终是有一个温度贯穿其中的。那温度在优化过程中起到的作用是什么呢？

算法简介

  针对一个优化问题，存在非常多的解，可以采用模拟退火（sa）算法逐渐的逼近最优解。它的求解过程是：从一个初始解出发，然后进行局部搜索，获得一个新解，是否接受新解由模拟退火来决定，所以sa在其中起到的作用就是是否接受当前这个新的解。

  sa中包含几个参数:T温度，$$ 降温系数，n迭代次数。n是指在每个温度T下的迭代次数。具体执行流程如下图所示：

sa

模拟退火中的T和n控制整个流程的进行，在每个温度T下都要执行n步（即n次迭代），n步执行完成之后，更新T。每次得到新解之后，都要对新解进行判断，是否接受。假设我们的优化目标（衡量新解的方法）为\(f(x)\)，我们求解的过程中是优化目标的值越小越好，所以如何来衡量新解与旧解的优劣呢。若新解优于上一步的解，直接接受，若不优于上一步的解，则有概率的接受。依据下面的公式：

\[rand < exp(-(f(x')-f(x)) / T)\]

来确定新解是否接受。指数函数的图像如下图所示：

exp

当新解比旧解要差时，\(-(f(x')-f(x)) < 0\)，即指数幂值在y轴的左侧，当T值较大时，指数幂值在靠近y轴的左侧部分，即概率值较大，接受较差解的概率要高一些，当随着温度T的下降，指数幂值值也降低，接受差解的概率较小。即模拟退火算法也是在前期可以较高概率的接受差解，从而快速跳出局部最优，随着搜索的进行，温度T逐渐下降，便不容易跳出当前范围。这也有点像深度学习调参的过程，初期学习率lr较大，随着求解过程的进行，学习率lr降低是一样的道理。若想在后期也以一个较大的概率接受差解，随着温度的降低或迭代次数的进行 可以在分母上乘一个值，提高分母的值，增大概率。

代码如下：

package main

import (
	"fmt"
	"math"
	"math/rand"
	"GoProject/algorithm/heuristic"
)

func getFuncRes(x, y float64) float64{ // 目标函数
	return 6.0 * math.Pow(x, 7) + 8.0 * math.Pow(x, 6)  + 7.0 * math.Pow(x, 3) + 5 * math.Pow(x, 2) - x*y
}

func SimulateAnneal() {
	result := math.MaxFloat64
	t := 100.0
	minT := 1e-8
	iterNum := 10000
	delta := 0.98
	rand.Seed(0)
	x := rand.Float64() * 100
	bestX := x
	fmt.Println(bestX)

	cnt := 0
	for t > minT && iterNum >= 0 {
		xNew := x + rand.Float64() * 2 - 1
		if xNew >= 0 && xNew <= 100 {
			cnt++
			funcNew := getFuncRes(xNew, 0)
			if funcNew < result {
				x = xNew
				bestX = x
				result = funcNew
			} else {
				p := math.Exp(-1 * (funcNew - result) / t)
				if rand.Float64() < p {
					x = xNew
				}
				if p > 0 {
					//fmt.Println("prob ", p)
				}

			}
		}
		iterNum--
		t = t * delta
	}
	fmt.Println(bestX, result, cnt)
}

func LateAcc() {

	rand.Seed(0)

	bestX := rand.Float64() * 100
	bestRes := 0.0

	pLa := new(heuristic.LateAcceptance)
	pLa.Init(200)

	pIterNum := 10000
	cnt := 0
	for pIterNum > 0 {
		x := bestX + rand.Float64() * 2 - 1
		if x >= 0 && x <= 100 {
			cnt++
			pRes := getFuncRes(x, 0)
			if pLa.Accept(pRes) {
				bestX = x
				bestRes = pRes
			}
		}
		pIterNum--
	}
	fmt.Println(bestX, bestRes, cnt)
}

func main() {
	SimulateAnneal()
	LateAcc()
}