模拟退火算法Python编程(1)多变量函数优化

模拟退⽕算法Python编程（1）多变量函数优化

1、模拟退⽕算法

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

退⽕是⾦属从熔融状态缓慢冷却、最终达到能量最低的平衡态的过程。模拟退⽕算法基于优化问题求解过程与⾦属退⽕过程的相似性，以优化⽬标为能量函数，以解空间为状态空间，以随机扰动模拟粒⼦的热运动来求解优化问题（[1] KIRKPATRICK,1988）。

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

温度更新函数是指退⽕温度缓慢降低的实现⽅案，也称冷却进度表；

状态产⽣函数是指由当前解随机产⽣新的候选解的⽅法；

状态接受函数是指接受候选解的机制，通常采⽤Metropolis准则；

外循环是由冷却进度表控制的温度循环；

硫酸铝钾内循环是在每⼀温度下循环迭代产⽣新解的次数，也称Markov链长度。

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

（1）初始化：初始温度T，初始解状态s，迭代次数L；

（2）对每个温度状态，重复 L次循环产⽣和概率性接受新解：

（3）通过变换操作由当前解s 产⽣新解s′；

（4）计算能量差 ∆E，即新解的⽬标函数与原有解的⽬标函数的差；

（5）若∆E <0则接受s′作为新的当前解，否则以概率exp(-∆E/T) 接受s′ 作为新的当前解；

（6）在每个温度状态完成 L次内循环后，降低温度 T，直到达到终⽌温度。

2、多变量函数优化问题

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

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

F(X)=418.9829×n-∑(i=1,n)〖xi* sin(√(|xi|)) 〗

本⽂取 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函数），通过对当前解的⼀个⾃变量施加正态分布的随机扰动产⽣新解。

3、模拟退⽕算法 Python 程序

# 模拟退⽕算法程序：多变量连续函数优化

# Program: SimulatedAnnealing_v1.py

# Purpose: Simulated annealing algorithm for function optimization

# v1.0:

# (1) 基本算法：单变量连续函数优化问题

# (2) ⽂件输出优化结果和中间过程数据

# (3) 设置指标参数计数器

# (4) 图形输出坏解接受概率

# Crated：2021-04-30

# -*- 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): # ====== 初始化随机数发⽣器 ======

randseed = random.randint(1, 100)

random.seed(randseed) # 随机数发⽣器设置种⼦，也可以设为指定整数

# ====== 随机产⽣优化问题的初始解 ======

xInitial = np.zeros((nVar)) # 初始化，创建数组

for v in range(nVar):

广安电影院# random.uniform(min,max) 在 [min,max] 范围内随机⽣成⼀个实数

xInitial[v] = random.uniform(xMin[v], xMax[v])

# 调⽤⼦函数 cal_Energy 计算当前解的⽬标函数值

fxInitial = cal_Energy(xInitial, nVar)

# ====== 模拟退⽕算法初始化 ======

xNew = np.zeros((nVar)) # 初始化，创建数组

xNow = np.zeros((nVar)) # 初始化，创建数组

xBest = np.zeros((nVar)) # 初始化，创建数组

xNow[:] = xInitial[:] # 初始化当前解，将初始解置为当前解

xBest[:] = xInitial[:] # 初始化最优解，将当前解置为最优解

fxNow = fxInitial # 将初始解的⽬标函数置为当前值

fxBest = fxInitial # 将当前解的⽬标函数置为最优值

print('x_Initial:{:.6f},{:.6f},\tf(x_Initial):{:.6f}'.format(xInitial[0], xInitial[1], fxInitial)) recordIter = [] # 初始化，外循环次数

recordFxNow = [] # 初始化，当前解的⽬标函数值

recordFxBest = [] # 初始化，最佳解的⽬标函数值

recordPBad = [] # 初始化，劣质解的接受概率

kIter = 0 # 外循环迭代次数，温度状态数

totalMar = 0 # 总计 Markov 链长度

totalImprove = 0 # fxBest 改善次数

nMarkov = meanMarkov # 固定长度 Markov链

# ====== 开始模拟退⽕优化 ======

# 外循环，直到当前温度达到终⽌温度时结束

tNow = tInitial # 初始化当前温度(current temperature)

while tNow >= tFinal: # 外循环，直到当前温度达到终⽌温度时结束

# 在当前温度下，进⾏充分次数(nMarkov)的状态转移以达到热平衡

kBetter = 0 # 获得优质解的次数

kBadAccept = 0 # 接受劣质解的次数

kBadRefuse = 0 # 拒绝劣质解的次数

# ---内循环，循环次数为Markov链长度

for k in range(nMarkov): # 内循环，循环次数为Markov链长度

totalMar += 1 # 总 Markov链长度计数器

# ---产⽣新解

# 产⽣新解：通过在当前解附近随机扰动⽽产⽣新解，新解必须在 [min,max] 范围内

# ⽅案 1：只对 n元变量中的⼀个进⾏扰动，其它 n-1个变量保持不变

xNew[:] = xNow[:]

v = random.randint(0, nVar-1) # 产⽣ [0,nVar-1]之间的随机数

xNew[v] = xNow[v] + scale * (xMax[v]-xMin[v]) * alvariate(0, 1)

# alvariate(0, 1)：产⽣服从均值为0、标准差为 1 的正态分布随机实数

xNew[v] = max(min(xNew[v], xMax[v]), xMin[v]) # 保证新解在 [min,max] 范围内

# ---计算⽬标函数和能量差

# 调⽤⼦函数 cal_Energy 计算新解的⽬标函数值

fxNew = cal_Energy(xNew, nVar)

在我国古代数学著作deltaE = fxNew - fxNow

# ---按 Metropolis 准则接受新解

# 接受判别：按照 Metropolis 准则决定是否接受新解

if fxNew < fxNow: # 更优解：如果新解的⽬标函数好于当前解，则接受新解

accept = True

kBetter += 1

else: # 容忍解：如果新解的⽬标函数⽐当前解差，则以⼀定概率接受新解

pAccept = p(-deltaE / tNow) # 计算容忍解的状态迁移概率

if pAccept > random.random():

accept = True # 接受劣质解

kBadAccept += 1

else:

accept = False # 拒绝劣质解

kBadRefuse += 1

# 保存新解

微生物学if accept == True: # 如果接受新解，则将新解保存为当前解

xNow[:] = xNew[:]

fxNow = fxNew

if fxNew < fxBest: # 如果新解的⽬标函数好于最优解，则将新解保存为最优解

fxBest = fxNew

xBest[:] = xNew[:]

totalImprove += 1

scale = scale*0.99 # 可变搜索步长，逐步减⼩搜索范围，提⾼搜索精度

# ---内循环结束后的数据整理

# 完成当前温度的搜索，保存数据和输出

pBadAccept = kBadAccept / (kBadAccept + kBadRefuse) # 劣质解的接受概率

recordIter.append(kIter) # 当前外循环次数

recordFxNow.append(round(fxNow, 4)) # 当前解的⽬标函数值

recordFxBest.append(round(fxBest, 4)) # 最佳解的⽬标函数值

recordPBad.append(round(pBadAccept, 4)) # 最佳解的⽬标函数值

if kIter%10 == 0: # 模运算，商的余数

print('i:{},t(i):{:.2f}, badAccept:{:.6f}, f(x)_best:{:.6f}'.\

format(kIter, tNow, pBadAccept, fxBest))

# 缓慢降温⾄新的温度，降温曲线：T(k)=alfa*T(k-1)

tNow = tNow * alfa

kIter = kIter + 1

# ====== 结束模拟退⽕过程 ======

print('improve:{:d}'.format(totalImprove))

return kIter,xBest,fxBest,fxNow,recordIter,recordFxNow,recordFxBest,recordPBad

# 结果校验与输出

def ResultOutput(cName,nVar,xBest,fxBest,kIter,recordFxNow,recordFxBest,recordPBad,recordIter): # ====== 优化结果校验与输出 ======

fxCheck = cal_Energy(xBest,nVar)

本文发布于:2024-09-22 01:53:52，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/592175.html

上一篇：20世纪十大算法 - 记事本

下一篇：Matlab模拟退火算法

标签：温度优化函数接受算法循环问题

留言与评论（共有 0 条评论）