【最优化导论】模拟退火法

JamesB · 发表于 2021-11-20 20:44

随机搜索

求解问题为 $maximize\ f(x)\\subject \ to\ x\in\Omega$
随机选择一个初始点 $x^{(0)}$ ，作为下一个迭代点的备选，即对于任一点 $x\in\Omega$ ，存在一个集合 $N(x)\subset \Omega$ 使得能够从该集合进行随机采样。

算法：

$x^{(0)}\in\Omega$

$f(z^{(k)})<f(x^{(k)})$

模拟退火法

$N(x)$ 过小会导致朴素随机搜素算法可能会在局部极小点附近“卡住”，N(x)过大会导致搜索过程过慢。模拟退火算法对朴素随机算法进行修改，使其能够走出局部极小点的邻域，模拟退火的两次迭代中，算法产生的新点可能会比当前点要差。
算法：

$x^{(0)}\in \Omega$

$p(k,f(z^{(k)}),f(x^{(k)}))$

维护一个最优解

$x_{best}^{(k)}=\left\{ \begin{array}{} x^{(k)},& f(x^{(k)}<f(x_{best}^{(k-1)}) \\ x_{best}^{(k-1)},&其他 \end{array}\right.$
常用的概率 $p(k,f(z^{(k)}),f(x^{(k)}))=min\{1,exp(-(f(z^{(k)})-f(x^{(k)}))/T_k)\}$

构成一组正数序列，称为温度进度表

$f(z^{(k)})$ 和 $f(x^{(k)})$ 之间的差距越大，越小，采用作为下一迭代点的可能性越小。通常的做法是令温度单调递减到0（冷却过程）。一开始希望能在整个可行集内进行搜索，随着迭代开展，搜索范围应该集中到全局极小点附近区域，而不是遍历整个可行集。
一个合理的冷却进度表： $T_k=\frac{\gamma}{log(k+2)}$

		自动登录	找回密码
密码			立即注册