网站建设营销开场白,东莞网站建设的价格,太原百度做网站多少钱,网站开发就业前景分析1、模拟退火算法
模拟退火算法借鉴了统计物理学的思想#xff0c;是一种简单、通用的启发式优化算法#xff0c;并在理论上具有概率性全局优化性能#xff0c;因而在科研和工程中得到了广泛的应用。 退火是金属从熔融状态缓慢冷却、最终达到能量最低的平衡态的过程。模拟退…
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直到达到终止温度。 欢迎关注 Youcans 原创系列每周更新数模笔记
Python数模笔记-PuLP库 Python数模笔记-StatsModels统计回归 Python数模笔记-Sklearn Python数模笔记-NetworkX Python数模笔记-模拟退火算法
2、多变量函数优化问题
选取经典的函数优化问题和组合优化问题作为测试案例。 问题 1Schwefel 测试函数是复杂的多峰函数具有大量局部极值区域。 F(X)418.9829×n-∑(i1,n)〖xi* sin(√(|xi|)) 〗 本文取 d10, x[-500,500]函数在 X(420.9687,…420.9687)处为全局最小值 f(X)0.0。
使用模拟退火算法的基本方案控制温度按照 T(k) a * T(k-1) 指数衰减衰减系数取 a如式1按照 Metropolis 准则接受新解。对于问题 1Schwefel函数通过对当前解的一个自变量施加正态分布的随机扰动产生新解。 关注 Youcans分享原创系列 https://blog.csdn.net/youcans
3、模拟退火算法 Python 程序
# 模拟退火算法 程序多变量连续函数优化
# Program: SimulatedAnnealing_v1.py
# Purpose: Simulated annealing algorithm for function optimization
# Copyright 2021 YouCans, XUPT
# Crated2021-04-30
# 关注 Youcans分享原创系列 https://blog.csdn.net/youcans
# -*- coding: utf-8 -*-
import math # 导入模块
import random # 导入模块
import pandas as pd # 导入模块
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.0sum 0.0for i in range(nVar):sum X[i] * np.sin(np.sqrt(abs(X[i])))fx 418.9829 * nVar - sumreturn fx# 子程序模拟退火算法的参数设置
def ParameterSetting():cName funcOpt # 定义问题名称nVar 2 # 给定自变量数量yf(x1,..xn)xMin [-500, -500] # 给定搜索空间的下限x1_min,..xn_minxMax [500, 500] # 给定搜索空间的上限x1_max,..xn_maxtInitial 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]) * random.normalvariate(0, 1)# random.normalvariate(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 TruekBetter 1else: # 容忍解如果新解的目标函数比当前解差则以一定概率接受新解pAccept math.exp(-deltaE / tNow) # 计算容忍解的状态迁移概率if pAccept random.random():accept True # 接受劣质解kBadAccept 1else:accept False # 拒绝劣质解kBadRefuse 1# 保存新解if accept True: # 如果接受新解则将新解保存为当前解xNow[:] xNew[:]fxNow fxNewif fxNew fxBest: # 如果新解的目标函数好于最优解则将新解保存为最优解fxBest fxNewxBest[:] xNew[:]totalImprove 1scale 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 * alfakIter 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)if abs(fxBest - fxCheck)1e-3: # 检验目标函数print(Error 2: Wrong total millage!)returnelse:print(\nOptimization by simulated annealing algorithm:)for i in range(nVar):print(\tx[{}] {:.6f}.format(i,xBest[i]))print(\n\tf(x):{:.6f}.format(fxBest))return# 主程序 关注 Youcans分享原创系列 https://blog.csdn.net/youcans **加粗样式**
def main():# 参数设置优化问题参数定义模拟退火算法参数设置[cName, nVar, xMin, xMax, tInitial, tFinal, alfa, meanMarkov, scale] ParameterSetting()# print([nVar, xMin, xMax, tInitial, tFinal, alfa, meanMarkov, scale])# 模拟退火算法[kIter,xBest,fxBest,fxNow,recordIter,recordFxNow,recordFxBest,recordPBad] \ OptimizationSSA(nVar,xMin,xMax,tInitial,tFinal,alfa,meanMarkov,scale)# print(kIter, fxNow, fxBest, pBadAccept)# 结果校验与输出ResultOutput(cName, nVar,xBest,fxBest,kIter,recordFxNow,recordFxBest,recordPBad,recordIter)# 关注 Youcans分享原创系列 https://blog.csdn.net/youcans
if __name__ __main__:main() 4、程序运行结果
x_Initial:-143.601793,331.160277, f(x_Initial):959.785447
i:0,t(i):100.00, badAccept:0.469136, f(x)_best:300.099320
i:10,t(i):81.71, badAccept:0.333333, f(x)_best:12.935760
i:20,t(i):66.76, badAccept:0.086022, f(x)_best:2.752498...
i:200,t(i):1.76, badAccept:0.000000, f(x)_best:0.052055
i:210,t(i):1.44, badAccept:0.000000, f(x)_best:0.009448
i:220,t(i):1.17, badAccept:0.000000, f(x)_best:0.009448
improve:18Optimization by simulated annealing algorithm:x[0] 420.807471x[1] 420.950005f(x):0.003352版权说明 原创作品 关注 Youcans分享原创系列 https://blog.csdn.net/youcans Copyright 2021 YouCans, XUPT Crated2021-05-01
关注 Youcans分享原创系列 https://blog.csdn.net/youcans
Python数模笔记-PuLP库1线性规划入门 Python数模笔记-PuLP库2线性规划进阶 Python数模笔记-PuLP库3线性规划实例 Python数模笔记-StatsModels 统计回归1简介 Python数模笔记-StatsModels 统计回归2线性回归 Python数模笔记-StatsModels 统计回归3模型数据的准备 Python数模笔记-StatsModels 统计回归4可视化 Python数模笔记-Sklearn 1介绍 Python数模笔记-Sklearn 2聚类分析 Python数模笔记-Sklearn 3主成分分析 Python数模笔记-Sklearn 4线性回归 Python数模笔记-Sklearn 5支持向量机 Python数模笔记-模拟退火算法1多变量函数优化 Python数模笔记-模拟退火算法2约束条件的处理 Python数模笔记-模拟退火算法3整数规划问题 Python数模笔记-模拟退火算法4旅行商问题
