智能优化算法之模拟退火算法SA

发展历史和算法思想
模拟退火算法(Simulated Annealing, SA)是一种基于热力学原理的随机优化算法,最早由 S. Kirkpatrick, C. D. Gelatt 和 M. P. Vecchi 于 1983 年提出。算法的灵感来自于固体物理学中的退火过程:通过加热和缓慢冷却金属,可以减少其结构中的缺陷,使其达到低能量的稳定状态。

数学原理
模拟退火算法的核心思想是通过模拟退火过程来搜索最优解。在优化过程中,算法允许在一定概率下接受较差的解,以避免陷入局部最优解。该概率由以下公式给出:
其中:
-
是当前解的能量(目标函数值)。
-
是新解的能量。
-
是当前温度。
-
是指数函数。
当温度逐渐降低时,算法更倾向于接受更优的解。通过适当的降温策略,算法可以逐步逼近全局最优解。
主要步骤:
-
初始化:设定初始温度 和初始解 。
-
邻域搜索:从当前解 的邻域中随机选择一个新解 。
-
能量差计算:计算当前解和新解的能量差 。
-
接受准则:如果 ,则接受新解;否则,以概率 接受新解。
-
降温:逐渐降低温度 。
-
重复步骤 2-5,直到达到停止条件(如温度过低或迭代次数达到上限)。
应用场景
模拟退火算法适用于求解各种组合优化问题和连续优化问题,主要包括但不限于:
-
旅行商问题(TSP)
-
背包问题
-
车辆路径问题
-
图着色问题
-
生产调度问题
-
函数优化
可视化Python示例
以下是一个使用模拟退火算法解决旅行商问题(TSP)的Python可视化示例:
import numpy as np
import matplotlib.pyplot as plt# 计算路径长度
def path_length(path, distance_matrix):return sum(distance_matrix[path[i], path[i+1]] for i in range(len(path)-1)) + distance_matrix[path[-1], path[0]]# 模拟退火算法
def simulated_annealing_tsp(distance_matrix, n_iterations, temp, cooling_rate):num_cities = len(distance_matrix)best_path = np.arange(num_cities)np.random.shuffle(best_path)best_eval = path_length(best_path, distance_matrix)curr_path, curr_eval = best_path.copy(), best_evalscores = [best_eval]for i in range(n_iterations):candidate_path = curr_path.copy()l, r = np.random.randint(0, num_cities, size=2)if l > r:l, r = r, lcandidate_path[l:r+1] = np.flip(candidate_path[l:r+1])candidate_eval = path_length(candidate_path, distance_matrix)if candidate_eval < best_eval:best_path, best_eval = candidate_path.copy(), candidate_evalscores.append(best_eval)print(f"Iteration {i}, Best Score: {best_eval}")diff = candidate_eval - curr_evalt = temp / float(i + 1)metropolis = np.exp(-diff / t)if diff < 0 or np.random.rand() < metropolis:curr_path, curr_eval = candidate_path.copy(), candidate_evaltemp *= cooling_ratereturn best_path, best_eval, scores# 参数设置
num_cities = 20
n_iterations = 1000
temp = 100
cooling_rate = 0.995# 生成随机城市坐标
coords = np.random.rand(num_cities, 2)
distance_matrix = np.linalg.norm(coords[:, np.newaxis] - coords[np.newaxis, :], axis=2)# 运行模拟退火算法
best_path, best_eval, scores = simulated_annealing_tsp(distance_matrix, n_iterations, temp, cooling_rate)
print(f"Best Path: {best_path}, Best Path Length: {best_eval}")# 可视化
plt.figure()
plt.subplot(2, 1, 1)
plt.scatter(coords[:, 0], coords[:, 1], c='red')
for i in range(num_cities):plt.annotate(str(i), (coords[i, 0], coords[i, 1]))
for i in range(num_cities):plt.plot([coords[best_path[i], 0], coords[best_path[(i + 1) % num_cities], 0]],[coords[best_path[i], 1], coords[best_path[(i + 1) % num_cities], 1]], 'b-')
plt.title('Best Path')plt.subplot(2, 1, 2)
plt.plot(scores, label='Best Path Length')
plt.xlabel('Iteration')
plt.ylabel('Path Length')
plt.legend()plt.tight_layout()
plt.show()'''
输出:
...
Iteration 896, Best Score: 4.171655916012842
Iteration 993, Best Score: 4.137952785183053
Best Path: [ 0 13 12 18 8 14 5 11 16 7 10 2 3 15 19 4 6 9 17 1], Best Path Length: 4.137952785183053
'''
可视化结果:

代码说明
-
计算路径长度函数:计算给定路径的总长度。
- 模拟退火算法:
-
初始化当前路径、最佳路径及其评价值。
-
在每次迭代中,从当前路径的邻域中随机选择一个新路径。
-
通过反转路径段来生成邻域解。
-
计算新路径的长度,并根据接受准则决定是否接受新路径。
-
逐步降低温度,并记录最佳路径的长度。
-
-
参数设置:设置城市数量、迭代次数、初始温度和降温率。
-
生成随机城市坐标:生成随机城市坐标并计算距离矩阵。
-
运行算法:调用模拟退火算法,并输出最佳路径和最佳路径长度。
-
可视化:绘制城市坐标图和优化过程中最佳路径长度的变化曲线。
以上内容总结自网络,如有帮助欢迎转发,我们下次再见!
相关文章:
智能优化算法之模拟退火算法SA
发展历史和算法思想 模拟退火算法(Simulated Annealing, SA)是一种基于热力学原理的随机优化算法,最早由 S. Kirkpatrick, C. D. Gelatt 和 M. P. Vecchi 于 1983 年提出。算法的灵感来自于固体物理学中的退火过程:通过加热和缓慢…...
同时用到,网页,java程序,数据库的web小应用
具体实现功能:通过网页传输添加用户的请求,需要通过JDBC来向 MySql 添加一个用户数据 第一步,部署所有需要用到的工具 IDEA(2021.1),Tomcat(9),谷歌浏览器,MySql,jdk(17) 第二步,创建java项目,提前部署数…...
星环科技推出语料开发工具TCS,重塑语料管理与应用新纪元
5月30-31日,2024向星力未来数据技术峰会期间,星环科技推出一款创新的语料开发工具——星环语料开发工具TCS(Transwarp Corpus Studio),旨在通过全面的语料生命周期管理,极大提升语料开发效率,助…...
【ARM】MDK安装ARM_compiler5无法打开安装程序
【更多软件使用问题请点击亿道电子官方网站】 1、 文档目标 在客户安装了最新版本的MDK5.37及后续更新版本,但原工程使用ARM_Compiler_5.06进行编译和调试,需安装ARM_Compiler_5.06的编译器版本,但在解压缩的过程中后续无法打开ARM_Compiler…...
PHP文字ocr识别接口示例、人工智能的发展
全球在人工智能升级的大背景下,有一定规模的制造商开始大量部署人工智能机器人、系统,以此取代危险、简单和重复性的工作。各种人工智能技术的迅猛发展,正在驱动各行业就业市场发现变革。 京东物流大家并不陌生,京东快递机器人在…...
【2024 全国青少年信息素养大赛复赛指南】算法创意实践挑战赛复赛、智能算法应用挑战赛复赛指南
目录 2024 全国青少年信息素养大赛算法创意实践挑战赛复赛指南 一、比赛内容 二、编程题作答说明 三、准备说明 四、进入复赛 五、设备检测 六、答题与交卷 全国青少年信息素养大赛智能算法应用挑战赛复赛指南 一、 比赛规则: 二、学生具体操作流程 三、 评判方法…...
构建自定义Tensorflow镜像时用到的链接地址整理
NVIDIA相关: NVIDIA CUDA镜像的docker hub:https://hub.docker.com/r/nvidia/cuda/tags?page&page_size&ordering&name12.4.1NVIDIA 构建的Tensorflow镜像包:https://docs.nvidia.com/deeplearning/frameworks/tensorflow-rele…...
C++——二叉搜索树的实现
1、二叉搜索树的概念 二叉搜索树又叫做二叉排序树,他或者是一棵空树,或者具有以下性质: 若他的左子树不为空,则左子树的所有节点的值都小于根节点的值, 若他的右子树不为空,则右子树的所有节点的值都大于…...
【AppScan】安装教程 AppScan v10 Web应用安全测试工具(附安装包)零基础入门到精通,收藏这一篇就够了
获取方式及安装教程下滑至文章底部查看 此软件“仅限学习交流,不能用于商业用途”,如用于商业用途,请到官方购买正版软件,追究法律责任与本平台无关! 配置要求 操作系统:64位 Win10、Win8、Win7 软件介绍 IBM AppScan是一款非常好用…...
Java项目:基于SSM框架实现的中小型企业财务管理系统【ssm+B/S架构+源码+数据库+答辩PPT+开题报告+毕业论文】
一、项目简介 本项目是一套基于SSM框架实现的中小型企业财务管理系统 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse或者idea 确保可以运行! 该系统功能完善、界面美观、操作简单…...
c++ - 多态
文章目录 一、多态的概念二、多态使用三、多态的原理 一、多态的概念 1、概念: 多态就是具有多种形态,可以理解为同一个行为不同对象去完成表现出不同的状态,如: 二、多态使用 1、构成多态的条件 (1)派…...
亚马逊云科技EC2简明教程
💡 完全适用于新手操作的Amazon EC2引导教程 简述 在亚马逊云科技中,存在多种计算服务,在此,我们将会着重讨论Amazon EC2(以下简称EC2),EC2作为亚马逊云科技的明星产品、核心产品,是大多数开发者和企业用…...
TCP网络传输控制协议
目录 什么是TCP TCP的特点 TCP通信步骤 三次握手(建立连接) 数据传输 四次挥手(连接释放) 为什么要进行三次握手?两次握手行不行?一次握手行不行? 为什么是四次挥手?三次、两…...
PCDN技术如何应对网络带宽限制?(壹)
PCDN技术应对网络带宽限制的操作主要包括以下几个方面: 利用边缘计算资源:PCDN是以P2PCDN技术为基础,通过挖掘利用边缘网络海量碎片化闲置资源来构建内容分发网络。这意味着,当网络带宽受限时,PCDN能够更有效地利用这…...
Java数据结构-链表与LinkedList
链表 链表的概念 链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 通俗来说,相比较于顺序表(物理上连续,逻辑上也连续),链表物理上不一定连续。 链表是…...
单元测试实施最佳方案(背景、实施、覆盖率统计)
1. 什么是单元测试? 对于很多开发人员来说,单元测试一定不陌生 单元测试是白盒测试的一种形式,它的目标是测试软件的最小单元——函数、方法或类。单元测试的主要目的是验证代码的正确性,以确保每个单元按照预期执行。单元测试通…...
mysql笔记(表导出文件,文件导入表)
遇见权限问题1: cat /etc/my.cnf加入[mysqld] secure_file_priv ""遇见目录错误2:因为 MySQL 服务器没有权限在根目录下创建文件。你可以尝试将文件导出到一个 MySQL 服务器有权限写入的目录下,例如 MySQL 数据目录或 /tmp目录。sudo chmod 755 /path/to…...
Navicat 17 新特性 | 原生支持 Linux ARM 平台以及银河麒麟和统信操作系统
随着 Navicat 17 的发布,引起了业界的广泛共鸣与热烈讨论。此前,我们深入探讨了Navicat 17的多项新特性,涵盖《模型设计:引领创新,优化升级》,《高效的查询与配置》以及《用户界面交互:流畅体验…...
【pytorch】手写数字识别
https://blog.csdn.net/qq_45588019/article/details/120935828 基本均参考该博客 《深度学习原理Pytorch实战》 初步处理 导包 import torch import numpy as np from matplotlib import pyplot as plt from torch.utils.data import DataLoader from torchvision import tr…...
SpringBoot3.3.0升级方案
本文介绍了由SpringBoot2升级到SpringBoot3.3.0升级方案,新版本的升级可以解决旧版本存在的部分漏洞问题。 一、jdk17下载安装 1、下载 官网下载地址 Java Archive Downloads - Java SE 17 Jdk17下载后,可不设置系统变量java_home,仅在id…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
