最优化算法----模拟退火+Python实现

基本模型

模拟退货算法可以分解为解空间、目标函数和初始解三部分

基本思想

求一个函数的最优解可以通过贪心算法获得其最优解，但有可能是局部最有解，而不是全局最优解。为了解决这一问题，产生了模拟退火算法，该算法是在搜索的过程中加入了随机的因素，以一定的概率接受比当前解要差的解，因此有可能会跳出这个局部最优解，达到全局最优解。

基本步骤

1. 初始化：初始温度 $T$， 温度变化率 $\Delta T$ （通常取值$0.95-0.99$），初始解状态 $S$，每个$T$值的迭代次数 $L$；
2. 对 $k=1,...,L$ 做第 3 至第 6 步；
3. 产生新解 $S^{\prime }$ ；
4. 计算增量 $\Delta t^{\prime }=C(S^{\prime })-C(S)$，其中 $C(S)$ 为评价函数；
5. 若 $\Delta t^{\prime }<0$ 则接受 $S^{\prime }$ 作为新的当前解，否则以概率 $Metropolis$ 准则接受 $S^{\prime }$作为当前解；
6. 如果满足终止条件则输出当前解作为最优解，结束程序；
7. $T$ 根据 $\Delta T$ 逐渐减少，且 $T\to 0$，然后转向第二步。

Metropolis准则
$$P=\{\begin{array}{ll}1& ,E(x_{new})<E(x_{old})\\ exp(-\frac{E(x_{new})-E(x_{old})}{T}& ,E(x_{new})\ge E(x_{old})\end{array}$$
其中，T为当前的温度，在 $E(x_{new})\ge E(x_{old})$ 时，求出的 $p$ 在 $(0,1)$ 之间，以此概率接受比当前解要差的解。

参数设置

初始温度：初始温度的确定可以随机产生数据来粗略的估计一下，比如可以先进行100个迭代，计算出目标函数的平均差值或者最大差值，再根据你希望的初始温度下由当前解转换为较差的解的概率和Metropolis准则计算出初始温度。

最小温度：可以设置的很小，进行很多次的迭代，找到全局最优解。

温度变化率：一般设置为 $0.95-0.99$ 之间的值，一般使用 $T(i+1)=\Delta T\ast T(i)$ 来衰减温度，当然也可以根据自己想要的衰减速率选取合适的公式。

目标函数：要求解的函数。

生成新解：可以在当前解的基础上进行部分或者全部值的改动，根据自己解的需求限定当前解的范围。

Python实现（部分）

# -*- coding: utf-8 -*-
import math
import random

ITERS = 100             # 每个温度下的迭代次数
T = 100                 # 初始温度
T_min = 0.002           # 温度最小值
delta_t = 0.98          # 温度变化率


class SA:
    '''
    求最小值
    '''
    def __init__(self):
        self.t = T
        self.iters = ITERS
        self.t_min = T_min
        self.delta_t = delta_t

    def sa(self, fun):
        '''
        模拟退火算法
        :param fun: 目标函数
        :return:
        '''
        x_old = self._init_x()
        y_old = fun(x_old)
        while self.t > self.t_min:
            for i in range(self.iters):
                x_new = self._update_x(x_old)
                y_new = fun(x_new)
                loss = y_new - y_old
                if loss <= 0:               # 替换比当前解好的解
                    x_old = x_new
                    y_old = y_new
                else:
                    random_p = random.random()
                    if self.metropolis(loss) > random_p:    # 以一定概率替换比当前解差的解
                        x_old = x_new
                        y_old = y_new
            # 是否满足条件, 满足则结束, 不满足则更新温度继续
            self.t *= self. delta_t
        # 最终保存或者输出最优解
        print("x {}, y {}".format(x_old, y_old))

    def metropolis(self, loss):
        return math.e ** (loss / self.t)

    def _update_x(self, x_old):
        '''
        生成新解
        :return:
        '''
        pass

    def _init_x(self):
        '''
        设置初始解
        :return:
        '''
        pass

最后

以上就是轻松煎饼为你收集整理的最优化算法----模拟退火+Python实现的全部内容，希望文章能够帮你解决最优化算法----模拟退火+Python实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。