当前位置：首页 > news >正文

运筹学之模拟退火

news 来源：原创 2025/8/6 22:38:38

一、历史

问：谁在什么时候提出模拟退火？
答：模拟退火算法（Simulated Annealing，SA）是由斯图尔特·柯尔斯基（Scott Kirkpatrick）等人在 1983年提出的。
论文：“Optimization by Simulated Annealing”, published in Science, Vol. 220
动机：解决组合优化问题

二、精髓思想

精髓就两字：退火！
解释：字面意思就是模拟打铁的退火过程，刚开始打铁吧温度比较高，铁烧的红红的容易打出各种形状，随着时间变长，温度逐渐冷却下来，铁更硬了，形状大方向基本确定。

不禁感叹，以前的物理学家、数学家灵感来源都是自然现象！
在这里插入图片描述
总结下来其实就3个step：

拿一块铁过来淬火
打一次看看如何
给我打到定型

三、案例与代码实现

题干：
6艘船靠3个港口，已知达到时间arrival和卸货时长handling，求最优停靠方案，即等待时长最短。
数据：

ships = {'S1': {'arrival': 0.1, 'handling': 4},'S2': {'arrival': 2.1, 'handling': 3},'S3': {'arrival': 4.2, 'handling': 2},'S4': {'arrival': 6.3, 'handling': 3},'S5': {'arrival': 5.5, 'handling': 2},'S6': {'arrival': 3.9, 'handling': 4},'S7': {'arrival': 3.7, 'handling': 4},'S8': {'arrival': 3.4, 'handling': 4},
}

实现：
step1：拿一块铁过来淬火

# 随机初始化一块铁（船舶调度顺序）
initial_order = list(ships.keys()) # 船舶原始顺序['S1', 'S2', 'S3', 'S4', 'S5', 'S6', 'S7', 'S8']
random.shuffle(initial_order)	#	打乱顺序 ，可能是['S2', 'S7', 'S6', 'S5', 'S1', 'S3', 'S4', 'S8']

step2：打一次看看如何

首先，先评价一下原始模样如何？用等待时间作为衡量，如下：

current_cost = evaluate(current)
NUM_BERTHS = 3  # 泊位数量
# 评价函数：计算某个调度顺序的总等待时间
def evaluate(order):berth_times = [0] * NUM_BERTHStotal_wait = 0for ship_id in order:arrival = ships[ship_id]['arrival']handling = ships[ship_id]['handling']# 找到最早可用泊位berth_index = min(range(NUM_BERTHS), key=lambda i: max(arrival, berth_times[i]))# start_time = 开始卸货时间 = max(到达时间, 泊位可用时间)。# 解释：要卸货的话，船先到达了没有泊位可用也得等，反之，有空泊位了船还没到也得等。start_time = max(arrival, berth_times[berth_index])wait_time = start_time - arrivaltotal_wait += wait_timeberth_times[berth_index] = start_time + handlingreturn total_wait

然后，开始下锤子了（称之为扰动）

# 生成邻域解（随机交换两艘船顺序）
def neighbor(order):new_order = order.copy()i, j = random.sample(range(len(order)), 2)new_order[i], new_order[j] = new_order[j], new_order[i]return new_order

紧接着，评估下现在模样和上一次区别，如下：

new = neighbor(current)
new_cost = evaluate(new)
delta = new_cost - current_cost	# 扰动之后的区别

最后，做决定是接着现在模样往下继续打，还是恢复回原来模样

# 情况1：delta < 0 说明等待时间变短了呀，打铁打得更好了，欣然接受。
# 情况2：delta >= 0 说明等待时间变长了，糟糕打偏了，不过没关系，这是艺术啊！不完美也是一种美！看心情决定~
# 于是有了 random.random() < math.exp(-delta / T)这一项
# 解释：random.random()就是一个随机值（类比于当时心情），值域范围[0.0, 1.0)
# math.exp(-delta / T)和delta、T有关系，这么来看吧，假设现在超级无敌高温，那么-delta / T趋于0，那么math.exp(-delta / T)趋于1，说明有很大概率接受比较差的解。假设现在温度快降到0了，那么-delta / T趋于负无穷，那么math.exp(-delta / T)趋于0，说明有极小概率接受比较差的解。
if delta < 0 or random.random() < math.exp(-delta / T):current = newcurrent_cost = new_cost

step3：给我打到定型

循环的过程，就是往复step2的过程，持续下去直到定型，如下：

# 模拟退火主过程
# 初始顺序：initial_order, 温度：T=100.0, 冷却率：cooling_rate=0.95, 最低温度：T_min=1e-3
def simulated_annealing(initial_order, T=100.0, cooling_rate=0.95, T_min=1e-3):current = initial_ordercurrent_cost = evaluate(current)best = currentbest_cost = current_costwhile T > T_min:for _ in range(100):  # 每个温度尝试多次扰动new = neighbor(current)new_cost = evaluate(new)delta = new_cost - current_costif delta < 0 or random.random() < math.exp(-delta / T):current = newcurrent_cost = new_costif current_cost < best_cost:best = currentbest_cost = current_costT *= cooling_rate  # 降温return best, best_cost

运筹学之模拟退火

目录一、历史二、精髓思想三、案例与代码实现一、历史问：谁在什么时候提出模拟退火？答：模拟退火算法（Simulated Annealing，SA）是由斯图尔特柯尔斯基（Scott Kirkpatrick） 等人在 …...

编程日记 2025/8/6 22:38:38

JavaScript 的演变：2023-2025 年的新特性解析

随着Web技术的飞速发展，ECMAScript（简称ES）作为JavaScript的语言标准，也在不断进化。本文将带你学习 ECMAScript 2023-2025 的新特性。一、ECMAScript 2023 新特性 1.1 数组的扩展 Array.prototype.findLast()/Array.protot…...

编程日记 2025/8/2 21:28:47

CSS继承

CSS继承 CSS继承是一种机制，允许子元素自动继承父元素的某些样式属性，从而减少重复代码。以下是一些常见的具有继承性的CSS属性： color : 文字颜色 font-family ： 字体族名称 font-size ： 字体大小 font-weight &am…...

编程日记 2025/8/6 22:25:17

游戏引擎学习第236天:GPU 概念概述

回顾并展望通过视频采集卡进行流媒体传输的未来昨天，我们迈出了大胆的一步，决定初始化硬件的 3D 加速，因为我有点厌倦了我们的游戏没有垂直同步（vsync）。如今，在 Windows 上，我找不到一种可靠…...

编程日记 2025/8/6 22:22:54

HFSS3（limy）——建模学习记录

前言——笔者使用的是21版HFSS 1.基本模型为什么没有环形的天线 2.创建基本模型方法常用：先粗略建好模型再编辑输入准确坐标和大小尺寸（这里长方体起始点是左上角下方的点，也就是说要输入模型起点相对于坐标原点的位置尺寸就可以确定具体…...

编程日记 2025/8/6 22:36:14

php实现zip压缩

可以使用ZipArchive类来创建ZIP压缩文件。ZipArchive是PHP内置的一个类，提供了创建、打开、读取、写入和关闭ZIP文件的功能。示例：压缩单个文件 <?php$fileToZip path/to/your/file.txt; $zipFileName compressed.zip;$zip new ZipArchive(); …...

编程日记 2025/8/6 22:35:44

【STM32单片机】#10 USART串口通信

主要参考学习资料： B站江协科技 STM32入门教程-2023版细致讲解中文字幕开发资料下载链接：https://pan.baidu.com/s/1h_UjuQKDX9IpP-U1Effbsw?pwddspb 单片机套装：STM32F103C8T6开发板单片机C6T6核心板实验板最小系统板套件科协实验&…...

编程日记 2025/8/6 22:29:55

goc命令大全

颜色0黑1红2蓝3浅绿4浅蓝5淡黄6棕7深蓝8灰9粉10深绿11紫12蓝绿13黄14橙15白绘图命令功能pen笔.fd()前进.rt()右转.c()颜色.up()抬笔.o(,)圆.e(,)椭圆.r(,,)长方形.picL(,)调图片.text(,,)文字.hide()隐藏.moveTo(,)移动wait();等待.soundL()调声音pause();暂停绘图命令功能…...

编程日记 2025/8/6 22:34:07

Linux | 软件仓库管理

一. 软件包 1.1 软件包的分类 DEB：主要用于基于 Debian 的系统，如 Ubuntu。这种软件包格式具有良好的依赖管理机制，方便用户安装、升级和卸载软件。RPM：广泛应用于 Red Hat、CentOS、Fedora 等系统。RPM 包将软件打包成一个文件…...

编程日记 2025/8/6 22:25:31

Python实现对目标Word文档进行自动化排版【4万字精讲】（14）

前言本文是该专栏的第14篇，后面会持续分享Python办公自动化干货知识，记得关注。注意：本文涵盖4万字以及实战操作代码的精讲攻略，带你轻松掌握一键式“文档自动化排版”程序功能。如果说当你在工作项目中，遇到这样的需求，需要如何处理——假设，现在有大批量的docx格…...

编程日记 2025/8/6 22:36:14

LeetCode每日一题4.19

2563. 统计公平数对的数目题目问题分析输入：一个整数数组 nums 和两个整数 lower 和 upper。输出：返回满足条件的公平数对的数目，即对于所有 0 < i < j < n，lower < nums[i] nums[j] < upper 的数对 (i, j)…...

编程日记 2025/8/6 22:25:18

Spring AI 开发 - 快速入门

先看效果项目搭建 Spring AI 是 Spring 推出的一个项目，目标是提供统一的API抽象层，屏蔽不同AI模型和服务的底层差异，实现跨平台兼容性。演示使用的模型是阿里的 qwq-32b。环境要求： JDK ：17以上（包括…...

编程日记 2025/8/6 22:34:08

leetcode哈希表（六）-三数相加

题目 15. 三数之和给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ，同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复…...

编程日记 2025/8/1 10:45:52

Photoshop安装与配置--简单攻略版

下载地址:Photoshop软件工具下载安装完成后，即可运行Photoshop.exe；打开工具页面后，按照下面简单配置即可 1.编辑-》首选项-》常规或者直接快捷键CtrlK 暂存盘：一定要设置为非C盘 2.性能 3.文件处理以上配置比较基础&#xf…...

编程日记 2025/8/2 13:56:37

一个 CTO 的深度思考

今天和一些同事聊了一会，以下是我的观点我的观点，成年人只能筛选，不能培养在组织中，应该永远向有结果的人看齐。不能当他站出来讲话的时候，大家还要讨论讨论，他虽然拿到结果了，但是他就是有一…...

编程日记 2025/8/6 22:38:06

创建箭头所指的包和类以及yml文件： 类中： package com.itheima;import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication;SpringBootApplication public class BigEventApplication …...

编程日记 2025/8/6 22:31:58

Git 命令速查手册

听说用美图可以钓读者？ 一、基础操作核心命令 1. 仓库初始化与克隆命令作用示例git init创建新仓库git init my-projectgit clone克隆远程仓库git clone [https://github.com/user/repo.git](https://github.com/user/repo.git)git remote add关联远程仓库git re…...

编程日记 2025/8/6 22:27:34

office软件中word里面的编号库和列表库功能

在Microsoft Word中，编号库和列表库是两大核心排版工具，分别服务于不同层级的文档结构化需求。以下从功能定义、核心差异、应用场景及操作技巧等维度进行详细解析：一、编号库（Numbering Library） 1. 定义与功能编号库是Word中预设或用户自定义的有序列表格式集合，用于…...

编程日记 2025/8/5 4:34:43

C++入门七式——模板初阶

目录函数模板函数模板概念函数模板格式函数模板的原理函数模板的实例化模板参数的匹配原则类模板类模板的定义格式类模板的显式实例化当面对下面的代码时，大家会不会有一种无力的感觉？明明这些代码差不多，只是因为类型不…...

编程日记 2025/8/6 22:31:57

Python+Selenium+Pytest+POM自动化测试框架封装（完整版）

🍅 点击文末小卡片 ，免费获取软件测试全套资料，资料在手，涨薪更快 1、测试框架简介 1）测试框架的优点代码复用率高，如果不使用框架的话，代码会显得很冗余。可以组装日志、报告、邮件等一…...

编程日记 2025/8/6 22:31:57

matlab 处理海洋数据并画图的工具包--ocean_data_tools

matlab 处理海洋数据并画图的工具包–ocean_data_tools matlab 处理海洋数据并画图的工具包–ocean_data_tools ocean_data_tools 简化了提取、格式化和可视化免费可用的海洋学数据的过程。虽然可以在线访问大量海洋学数据，但由于获取这些数据并将其格式化为可用数据…...

编程日记 2025/8/6 5:07:14

软件开发指南——GUI 开发方案推荐

1. LVGL (Light and Versatile Graphics Library) 适用场景：嵌入式设备、资源受限环境优势： 专为嵌入式设计的开源 GUI 库，内存占用极小（最低仅需 64KB RAM）支持触摸屏、硬件加速（如 STM32 的 LTDC&…...

编程日记 2025/8/6 22:35:44

JDK8 HashMap的实现原理

一 HashMap底层存储结构 HashMap底层结构采用（数组）（链表 or 红黑树）的形式来存储节点。首先HashMap是一个数组，而且数组里面每个位置可以放入多个元素，形象一点，咱们把数组的这些个位置称为桶…...

编程日记 2025/8/6 22:25:18

YOLO拓展-锚框(anchor box)详解

一.锚框（anchor box）概述 1.1什么是锚框锚框就是一种进行预测的像素框，通过遍历输入图像上所有可能的像素框，然后选出正确的目标框，并对位置和大小进行调整就可以完成目标检测任务。对于yolo锚框的建设须基于实际…...

编程日记 2025/8/6 22:29:58

U-Boot（Universal Bootloader）简介

U-Boot 是一种开源的、高度可定制的引导加载程序（Bootloader），专为嵌入式系统和特定硬件平台设计。它负责在设备上电后初始化硬件、加载操作系统内核，并将控制权移交给操作系统，是嵌入式设备启动过程中不可或缺的核心…...

编程日记 2025/8/6 22:34:06

turtle库绘制进阶图形

要求： 1.绘制嵌套彩色五角星（大小逐层递减） 2. 设计函数绘制自定义正多边形（边数与颜色参数化） 3. 扩展：实现动态旋转花瓣图案代码： import turtledef draw_nested_star():colors ["…...

编程日记 2025/8/6 22:36:13

[matlab]南海地形眩晕图代码

[matlab]南海地形眩晕图代码请ChatGPT帮写个南海地形眩晕图代码图片图片代码 .rtcContent { padding: 30px; } .lineNode {font-size: 12pt; font-family: "Times New Roman", Menlo, Monaco, Consolas, "Courier New", monospace; font-style: n…...

编程日记 2025/8/6 22:31:58

3. 进程概念

目录 1. 冯诺依曼体系结构 2. 操作系统 3. 理解进程的一般思路 4. 查看进程 5. fork初识 6. 进程状态 6.1 一般操作系统 6.2 Linux系统是怎么维护进程状态的 7. 进程优先级先谈硬件-再谈软件-最后谈进程。 1. 冯诺依曼体系结构我们常见的计算机（笔记本电…...

编程日记 2025/8/6 22:22:54

yolov8的数据处理lableimg的安装以及使用

视频数据集准备 video cv2.VideoCapture("./BVN.mp4") num 0 # 计数器 save_step 30 # 间隔帧 while True:rel, frame video.read()if not ret:breaknum 1if num % save_step 0:cv2.imwrite("./demo images/" str(num) ".jpg", frame)l…...

编程日记 2025/8/6 22:36:14

小刚说C语言刷题——1035 判断成绩等级

1.题目描述输入某学生成绩，如果 86分以上(包括 86分）则输出 VERY GOOD ，如果在 60到 85之间的则输出 GOOD (包括 60和 85)，小于 60 的则输出 BAD。输入输入只有一行，包括 1个整数。输出输出只有一行&#xf…...

编程日记 2025/8/6 22:27:37

Spring 依赖冲突解决方案详解

引言在Spring框架中，依赖管理是一个核心功能，它使得开发者能够轻松地管理应用程序中的各种组件和服务。然而，随着项目的增长和复杂度的增加，依赖冲突问题也变得日益常见。本文将详细介绍Spring中不同类型的依赖冲突及其解决方法…...

编程日记 2025/8/6 22:27:34

P11299 [NOISG 2021 Finals] Fraud 题解

题目背景你被任命为第 24 届全国信息学奥林匹克竞赛的负责人！ 题目描述本次竞赛共有 N 名参赛者和 2 轮比赛。第 i 名参赛者在第一轮获得了分，在第二轮获得了分。每轮比赛分别有一个正整数权重 X 和 Y。第 i 名参赛者的最终得分计算公式为&a…...

编程日记 2025/8/6 22:25:30

AI时代下你需要和想要了解的英文缩写含义

在AI智能时代下，越来愈多的企业都开始重视并应用以及开发AI相关产品，这个时候都会或多或少的涉及到英文，英文还好，但是如果是缩写，如果我们没有提前了解过，我们往往很难以快速Get到对方的意思。在这里&…...

编程日记 2025/8/6 22:25:31

大数据平台简介

一、分布式系统基础架构 （一）定义与核心特征分布式系统是由多台计算机（节点）通过网络协作组成的系统，对外表现为一个统一整体。其核心特征包括： 去中心化：节点平等或分角色协作（如…...

编程日记 2025/8/6 2:01:25

电脑端移植至手机平板：攻克难题，仙盟架构显神通——仙盟创梦IDE

在将电脑端应用移植到手机和平板的过程中，常面临诸多棘手问题。像 1.x 号关闭按钮因位置设计欠佳，难以被用户精准点击，字体过小导致阅读与操作不便等。未来之窗仙盟创梦凭借创新的仙盟架构，巧妙且高效地化解了这些困扰开发者与用户…...

编程日记 2025/8/6 22:34:08

基于Python的中国象棋小游戏的设计与实现

基于Python的中国象棋小游戏的设计与实现第一章绪论1.1 研究背景1.2 研究意义第二章需求分析2.1 需求分析2.1.1核心功能需求2.1.2 用户体验需求2.1.3 衍生功能需求 2.2 可行性分析2.2.1 技术可行性2.2.2 经济可行性2.2.3 市场可行性2.2.4 法律与合规性第三章概要设计3.1 …...

编程日记 2025/8/6 22:29:56

HCIP --- OSPF综合实验

一、拓扑图二、实验要求 1，R5为ISP，其上只能配置IP地址;R4作为企业边界路由器，出口公网地址需要通过PPP协议获取，并进行chap认证。 2，整个0SPF环境IP基于172.16.0.8/16划分。 3，所有设备均可访问R5的环…...

编程日记 2025/8/6 22:25:32

【OpenGL】OpenGL学习笔记-1：VS2019配置OpenGL开发环境

在Visual Studio 2019中可以通过手动配置库文件或NuGet包管理器快速安装的方法配置OpenGL环境，详细步骤如下： 一、打开VS2019，创建新的控制台项目二、方法一：手动配置GLEW/GLFW/GLAD库 GLFW是窗口管理和输入事件的基础设施&…...

编程日记 2025/8/6 22:22:55

GWAS_LD

局部LDblock 绘图 1. 查看显著位点附近基因情况链接pvalue显著位点文件 ln -s ~/yiyaoran/GWAS/my_GWAS_J/P3.GWAS/01.tassel/mlm_output.manht_figure.sigSite.out . #也可以自己筛选awk $2 9 && $4 < 0.000028481 mlm_output.manht_input>368_GWAS.snpsnp两…...

编程日记 2025/8/6 22:35:45

WinForms开发基础：实现带X按钮的ClearableTextBox控件

前言我们经常看到这样的带X按钮的输入框如果使用WinForms开发中，该如何进行设计，普通的TextBox控件如何进行改造？为了提升用户体验，在TextBox文本框内添加一个“x”按钮，方便用户一键清除内容。本文将介绍如何通过继…...

编程日记 2025/8/6 22:22:56

直线轴承常规分类知多少？

直线轴承的分类方式多样，以下是从材质、结构形状和常规系列三个维度进行的具体分类： 按主要材质分类外壳材质：常见的有不锈钢，具有良好的耐腐蚀性，适用于一些对环境要求较高、易受腐蚀的工作场景；轴承…...

编程日记 2025/8/6 8:20:49

算法期末复习

算法期末复习 1.单选题 \1. 二分搜索算法是利用( A)实现的算法。 A. 分治策略 B. 动态规划法 C. 贪心法 D. 回溯法 \2. 回溯法解旅行售货员问题时的解空间树时( C ) 。 A. 子集树 B. 深度优先生成树 C. 排序树 D. 广度优先生成树 \3. 下列算法中通常以自底向上的方式求解最…...

编程日记 2025/8/6 22:35:46

LeetCode 5：最长回文子串

1、题目描述给你一个字符串 s，找到 s 中最长的回文子串。示例 1: 输入：s "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2: 输入：s "cbbd" 输出&#…...

编程日记 2025/8/1 5:31:13

2025年4月19日记录大模型出现的计算问题

2025年4月19日记录大模型出现的计算问题，用了四个大模型计算json的数值，3个错误，1个正确问题 Class Train Val answer 2574 853 screen 5025 1959 blackBoard 7847 3445 teacher 8490 3228 stand…...

编程日记 2025/7/26 16:22:58

Python语法系列博客 · 第3期数据结构入门（列表、元组、字典、集合）

上一期小练习解答（第2期回顾） ✅ 练习1：判断一个数是正数、负数还是零 num float(input("请输入一个数：")) if num > 0:print("正数") elif num < 0:print("负数") else:print("零&q…...

编程日记 2025/8/4 1:25:03

【对Linux文件权限的深入理解】

Linux文件权限 Linux下权限概念概念相关命令 Linux的文件权限管理1.文件访问者的分类（⼈）文件类型和访问权限（事物属性）文件权限值的表示方法⽂件访问权限的相关设置方法目录的权限（比较重要）粘滞位 Linux下…...

编程日记 2025/8/2 22:11:25

2025.04.19【Spider】| 蜘蛛图绘制技巧精解

Basic multi-group radar chart Start with a basic version, learn how to format your input dataset Radar chart with ggradar A Spider chart made using the ggradar package and a lot of customization.A work by Tuo Wang 文章目录 Basic multi-group radar chartRa…...

编程日记 2025/8/3 4:29:57

目录

一、历史

二、精髓思想

三、案例与代码实现

相关文章：