Python 模拟退火算法

模拟退火算法借鉴了统计物理学的思想，是一种简单、通用的启发式优化算法，并在理论上具有概率性全局优化性能，因而在科研和工程中得到了广泛的应用。

退火是金属从熔融状态缓慢冷却、最终达到能量最低的平衡态的过程。模拟退火算法基于优化问题求解过程与金属退火过程的相似性，以优化目标为能量函数，以解空间为状态空间，以随机扰动模拟粒子的热运动来求解优化问题。

模拟退火算法结构简单，由温度更新函数、状态产生函数、状态接受函数和内循环、外循环终止准则构成。

温度更新函数是指退火温度缓慢降低的实现方案，也称冷却进度表；
状态产生函数是指由当前解随机产生新的候选解的方法；
状态接受函数是指接受候选解的机制，通常采用Metropolis准则；
外循环是由冷却进度表控制的温度循环；
内循环是在每一温度下循环迭代产生新解的次数，也称Markov链长度。

模拟退火算法的基本流程如下：

1. 初始化：初始温度T，初始解状态s，迭代次数L；
2. 对每个温度状态，重复 L次循环产生和概率性接受新解：
3. 通过变换操作由当前解s 产生新解s′；
4. 计算能量差 ∆E，即新解的目标函数与原有解的目标函数的差；
5. 若∆E <0则接受s′作为新的当前解，否则以概率exp(-∆E/T) 接受s′ 作为新的当前解；
6. 在每个温度状态完成 L次内循环后，降低温度 T，直到达到终止温度。 

多变量函数优化问题

选取经典的函数优化问题和组合优化问题作为测试案例。

问题 1：Schwefel 测试函数，是复杂的多峰函数，具有大量局部极值区域。

本文取 d=10, x=[-500,500]，函数在 X=(420.9687,...420.9687)处为全局最小值 f(X)=0.0。

使用模拟退火算法的基本方案：控制温度按照 T(k) = a * T(k-1) 指数衰减，衰减系数取 a；如式（1）按照 Metropolis 准则接受新解。对于问题 1（Schwefel函数），通过对当前解的一个自变量施加正态分布的随机扰动产生新解。

 部分模拟退火算法 Python 程序

# 模拟退火算法 程序：多变量连续函数优化
# Program: SimulatedAnnealing_v1.py
# Purpose: Simulated annealing algorithm for function optimization
# v1.0:
#   (1) 基本算法：单变量连续函数优化问题
#   (2) 文件输出优化结果和中间过程数据
#   (3) 设置指标参数计数器
#   (4) 图形输出坏解接受概率

#  -*- coding: utf-8 -*-
import math                         # 导入模块
import random                       # 导入模块
import pandas as pd                 # 导入模块 YouCans, XUPT
import numpy as np                  # 导入模块 numpy, 并简写成 np
import matplotlib.pyplot as plt     # 导入模块 matplotlib.pyplot, 并简写成 plt
from datetime import datetime


# 子程序：定义优化问题的目标函数
def cal_Energy(X, nVar):
    # 测试函数 1：Schwefel 测试函数
    # -500 <= Xi <= 500
    # 全局极值：(420.9687,420.9687,...),f(x)=0.0
    sum = 0.0
    for i in range(nVar):
        sum += X[i] * np.sin(np.sqrt(abs(X[i])))
    fx = 418.9829 * nVar - sum
    return fx


# 子程序：模拟退火算法的参数设置
def ParameterSetting():
    cName = "funcOpt"           # 定义问题名称
    nVar = 2                    # 给定自变量数量，y=f(x1,..xn)
    xMin = [-500, -500]         # 给定搜索空间的下限，x1_min,..xn_min
    xMax = [500, 500]           # 给定搜索空间的上限，x1_max,..xn_max

    tInitial = 100.0            # 设定初始退火温度(initial temperature)
    tFinal  = 1                 # 设定终止退火温度(stop temperature)
    alfa    = 0.98              # 设定降温参数，T(k)=alfa*T(k-1)
    meanMarkov = 100            # Markov链长度，也即内循环运行次数
    scale   = 0.5               # 定义搜索步长，可以设为固定值或逐渐缩小
    return cName, nVar, xMin, xMax, tInitial, tFinal, alfa, meanMarkov, scale


# 模拟退火算法
def OptimizationSSA(nVar,xMin,xMax,tInitial,tFinal,alfa,meanMarkov,scale):
……

🚩 完整代码 https://download.csdn.net/download/s1t16/86951372