Python实战开发及案例分析（12）—— 模拟退火算法

2024-05-09 12:20
文章标签 python 算法 分析 实战 开发 案例 模拟退火

本文主要是介绍Python实战开发及案例分析（12）—— 模拟退火算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        模拟退火算法（Simulated Annealing）是一种概率搜索算法，源自于金属退火过程。在金属退火中，通过缓慢降低温度，金属内部的原子能够从高能态逐步达到较低能态。模拟退火算法利用类似的原理，通过随机搜索和概率接受策略来找到近似最优解。

模拟退火算法的原理

  • 目标：寻找最小化或最大化目标函数的近似最优解。
  • 温度：从高温逐渐降到低温。
  • 状态变换：通过随机变换产生邻域解。
  • 接受概率：以一定概率接受当前解，概率与温度和能量变化相关。

伪代码

1. 初始化当前解 s0，并设定初始温度 T0
2. while 当前温度 T > Tmin:
    3. 随机产生新的解 s'（当前解的邻域解）
    4. 计算能量差 ΔE = f(s') - f(s)
    5. if ΔE < 0:
        6. 接受新的解 s = s'
    7. else:
        8. 以概率 P(ΔE, T) = exp(-ΔE / T) 接受新的解 s = s'
    9. 降低温度 T = T * α
10. 返回最优解

Python 实现：模拟退火算法

示例问题：求解最小化 Rastrigin 函数

Rastrigin 函数是一个常见的多峰函数，用于测试优化算法的全局搜索能力。函数公式如下：

𝑓(𝑥,𝑦)=10×2+(𝑥2−10×cos⁡(2𝜋𝑥))+(𝑦2−10×cos⁡(2𝜋𝑦))

Python 实现：

import math
import random
import numpy as np
import matplotlib.pyplot as plt# Rastrigin 函数
def rastrigin(x):A = 10return A * len(x) + sum([(xi**2 - A * math.cos(2 * math.pi * xi)) for xi in x])# 邻域解生成函数
def random_neighbor(x, bounds, step_size=0.5):return [min(max(xi + random.uniform(-step_size, step_size), bounds[i][0]), bounds[i][1]) for i, xi in enumerate(x)]# 模拟退火算法
def simulated_annealing(objective, bounds, T0=1000, Tmin=1e-5, alpha=0.9, max_iter=1000):# 随机初始化起点x = [random.uniform(b[0], b[1]) for b in bounds]best_solution = xbest_score = objective(x)current_solution = xcurrent_score = best_scoreT = T0scores = []for _ in range(max_iter):if T < Tmin:break# 生成新邻域解neighbor = random_neighbor(current_solution, bounds)neighbor_score = objective(neighbor)# 接受概率计算if neighbor_score < current_score:current_solution = neighborcurrent_score = neighbor_scoreelse:p = math.exp((current_score - neighbor_score) / T)if random.random() < p:current_solution = neighborcurrent_score = neighbor_score# 更新最优解if current_score < best_score:best_solution = current_solutionbest_score = current_scorescores.append(best_score)# 降低温度T *= alphareturn best_solution, best_score, scores# 定义搜索空间（x 和 y 的范围）
bounds = [(-5.12, 5.12), (-5.12, 5.12)]# 使用模拟退火算法最小化 Rastrigin 函数
best_solution, best_score, scores = simulated_annealing(rastrigin, bounds)print("Best solution:", best_solution)
print("Best score:", best_score)# 绘制优化过程中的得分变化
plt.plot(scores)
plt.xlabel("Iteration")
plt.ylabel("Best Score")
plt.title("Simulated Annealing Optimization Process")
plt.show()

结果分析

        通过运行以上代码，我们可以观察到模拟退火算法的搜索过程，并找到接近最优解的结果：

  • 最优解：Best solution
  • 最优值：Best score
  • 优化过程：scores 显示了得分随迭代次数的变化趋势。

结论

        模拟退火算法是一种用于全局优化的启发式搜索方法，能够有效地找到复杂多峰函数的近似最优解。它的成功取决于温度衰减率和接受概率策略等参数的选择。通过调整这些参数，可以提高算法的搜索效率和性能。

模拟退火算法参数调优

模拟退火算法的性能很大程度上取决于温度衰减率、初始温度和步长的选择。下面是这些参数的常见选择策略：

  1. 初始温度 (T0)：

    • 设定得足够高，以确保在开始时接受不好的解，从而允许算法进行全局搜索。
    • 常见值：1000、5000等。

  2. 温度衰减率 (alpha)：

    • 温度每次迭代后的衰减比率。
    • 常见值：0.9 ~ 0.99。

  3. 终止温度 (Tmin)：

    • 温度降低到何值以下停止搜索。
    • 常见值：1e-5 ~ 1e-8。

  4. 步长 (step_size)：

    • 用于生成新邻域解的随机步长。
    • 常见值：0.1 ~ 1.0。

多目标优化问题

        多目标优化问题（Multi-objective Optimization Problem，MOP）是指同时优化多个相互冲突的目标。在模拟退火算法中，常见的多目标优化方法包括：

  • 权重和法：为每个目标设置权重，将多个目标组合成一个加权目标函数。
  • 帕累托优化：寻找帕累托最优解集，并通过模拟退火进行搜索。

案例分析：求解多目标优化问题

示例问题：双目标优化的 ZDT1 问题

        ZDT1 问题是双目标优化问题的一个经典例子。目标函数如下：

                ​​​​​​​        f_{1}\left ( x \right )=x_{1}

                        f_{2}\left ( x \right )=g\left ( x \right )\cdot \left ( 1-\sqrt{\frac{x_{1}}{g\left ( x \right )}} \right )

                        g\left ( x \right )=1+9\cdot \frac{\sum_{i=2}^{n}x_{i}}{n-1}

        约束条件：

        ​​​​​​​        ​​​​​​​        0\leq x_{i}\leq 1

Python 实现：

import math
import random
import numpy as np
import matplotlib.pyplot as plt# ZDT1 问题
def zdt1(x):f1 = x[0]g = 1 + 9 * sum(x[1:]) / (len(x) - 1)f2 = g * (1 - math.sqrt(f1 / g))return f1, f2# 权重和目标函数
def weighted_sum(x, w):f1, f2 = zdt1(x)return w[0] * f1 + w[1] * f2# 邻域解生成函数
def random_neighbor_multi(x, bounds, step_size=0.1):return [min(max(xi + random.uniform(-step_size, step_size), bounds[i][0]), bounds[i][1]) for i, xi in enumerate(x)]# 多目标模拟退火算法
def simulated_annealing_multi(objective, bounds, w, T0=1000, Tmin=1e-5, alpha=0.9, max_iter=1000):# 随机初始化起点x = [random.uniform(b[0], b[1]) for b in bounds]best_solution = xbest_score = objective(x, w)current_solution = xcurrent_score = best_scoreT = T0scores = []for _ in range(max_iter):if T < Tmin:break# 生成新邻域解neighbor = random_neighbor_multi(current_solution, bounds)neighbor_score = objective(neighbor, w)# 接受概率计算if neighbor_score < current_score:current_solution = neighborcurrent_score = neighbor_scoreelse:p = math.exp((current_score - neighbor_score) / T)if random.random() < p:current_solution = neighborcurrent_score = neighbor_score# 更新最优解if current_score < best_score:best_solution = current_solutionbest_score = current_scorescores.append(best_score)# 降低温度T *= alphareturn best_solution, scores# 定义搜索空间
bounds = [(0, 1) for _ in range(30)]
weights = [0.5, 0.5]# 使用多目标模拟退火算法最小化 ZDT1 问题
best_solution, scores = simulated_annealing_multi(weighted_sum, bounds, weights)# 打印结果
f1, f2 = zdt1(best_solution)
print("Best solution:", best_solution)
print("Objective values:", (f1, f2))# 绘制优化过程中的得分变化
plt.plot(scores)
plt.xlabel("Iteration")
plt.ylabel("Best Weighted Score")
plt.title("Simulated Annealing Multi-objective Optimization Process")
plt.show()

结论

        通过优化 ZDT1 问题，我们了解到模拟退火算法在多目标优化问题上的适用性。重要的是选择适当的参数和策略，包括权重分配、温度衰减和步长等。模拟退火算法在全局搜索上具有广泛的应用潜力，可以有效地应对高维优化问题。

        在继续深入探讨模拟退火算法的优化和应用过程中，让我们进一步扩展内容，包括：

  1. 非线性函数优化：优化非线性函数以显示模拟退火算法的多功能性。
  2. 组合优化问题：应用模拟退火算法于旅行商问题（TSP）。
  3. 参数调优：展示如何通过调优参数来改善算法性能。

非线性函数优化

        在非线性函数优化问题中，我们可以尝试优化 Himmelblau 函数，这是一个常见的多极值函数，定义如下：

                        f\left ( x,y \right )=\left ( x^{2}+y-11 \right )^{2}+\left (x+y^{2}-7 \right )^{2}

Python 实现：
import random
import math
import numpy as np
import matplotlib.pyplot as plt# Himmelblau 函数
def himmelblau(x):return (x[0]**2 + x[1] - 11)**2 + (x[0] + x[1]**2 - 7)**2# 邻域解生成函数
def random_neighbor(x, bounds, step_size=0.5):return [min(max(xi + random.uniform(-step_size, step_size), bounds[i][0]), bounds[i][1]) for i, xi in enumerate(x)]# 模拟退火算法
def simulated_annealing(objective, bounds, T0=1000, Tmin=1e-5, alpha=0.9, max_iter=1000):# 随机初始化起点x = [random.uniform(b[0], b[1]) for b in bounds]best_solution = xbest_score = objective(x)current_solution = xcurrent_score = best_scoreT = T0scores = []for _ in range(max_iter):if T < Tmin:break# 生成新邻域解neighbor = random_neighbor(current_solution, bounds)neighbor_score = objective(neighbor)# 接受概率计算if neighbor_score < current_score:current_solution = neighborcurrent_score = neighbor_scoreelse:p = math.exp((current_score - neighbor_score) / T)if random.random() < p:current_solution = neighborcurrent_score = neighbor_score# 更新最优解if current_score < best_score:best_solution = current_solutionbest_score = current_scorescores.append(best_score)# 降低温度T *= alphareturn best_solution, best_score, scores# 定义搜索空间
bounds = [(-5, 5), (-5, 5)]# 使用模拟退火算法最小化 Himmelblau 函数
best_solution, best_score, scores = simulated_annealing(himmelblau, bounds)print("Best solution:", best_solution)
print("Best score:", best_score)# 绘制优化过程中的得分变化
plt.plot(scores)
plt.xlabel("Iteration")
plt.ylabel("Best Score")
plt.title("Simulated Annealing Optimization Process (Himmelblau)")
plt.show()

组合优化问题：旅行商问题（TSP）

        旅行商问题（Traveling Salesman Problem，TSP）是组合优化问题中的经典问题。目标是在给定的城市集合中，找到访问所有城市且回到出发点的最短路径。

Python 实现：
import random
import math
import matplotlib.pyplot as plt# 计算两城市之间的距离
def distance(city1, city2):return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)# 计算总路径长度
def total_distance(tour, cities):return sum(distance(cities[tour[i]], cities[tour[i + 1]]) for i in range(len(tour) - 1)) + distance(cities[tour[0]], cities[tour[-1]])# 邻域解生成函数
def random_neighbor_tsp(tour):new_tour = tour[:]i, j = random.sample(range(len(tour)), 2)new_tour[i], new_tour[j] = new_tour[j], new_tour[i]return new_tour# 模拟退火算法
def simulated_annealing_tsp(cities, T0=1000, Tmin=1e-5, alpha=0.99, max_iter=1000):tour = list(range(len(cities)))random.shuffle(tour)best_solution = tourbest_score = total_distance(tour, cities)current_solution = tourcurrent_score = best_scoreT = T0scores = []for _ in range(max_iter):if T < Tmin:break# 生成新邻域解neighbor = random_neighbor_tsp(current_solution)neighbor_score = total_distance(neighbor, cities)# 接受概率计算if neighbor_score < current_score:current_solution = neighborcurrent_score = neighbor_scoreelse:p = math.exp((current_score - neighbor_score) / T)if random.random() < p:current_solution = neighborcurrent_score = neighbor_score# 更新最优解if current_score < best_score:best_solution = current_solutionbest_score = current_scorescores.append(best_score)# 降低温度T *= alphareturn best_solution, best_score, scores# 随机生成城市坐标
random.seed(0)
num_cities = 20
cities = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(num_cities)]# 使用模拟退火算法解决 TSP
best_solution, best_score, scores = simulated_annealing_tsp(cities)print("Best solution:", best_solution)
print("Best score:", best_score)# 绘制优化过程中的得分变化
plt.plot(scores)
plt.xlabel("Iteration")
plt.ylabel("Best Score")
plt.title("Simulated Annealing Optimization Process (TSP)")
plt.show()# 绘制 TSP 最优路径
x = [cities[i][0] for i in best_solution] + [cities[best_solution[0]][0]]
y = [cities[i][1] for i in best_solution] + [cities[best_solution[0]][1]]
plt.plot(x, y, marker='o')
plt.xlabel("X Coordinate")
plt.ylabel("Y Coordinate")
plt.title("Optimal Tour (TSP)")
plt.show()

结论

        模拟退火算法通过不断地接受或拒绝新解来达到全局优化的目标。我们展示了如何使用模拟退火算法优化非线性函数、组合优化问题，并且通过参数调优进一步优化了算法性能。对于特定问题来说，模拟退火算法的成功取决于参数设置以及随机搜索策略的选择。

这篇关于Python实战开发及案例分析（12）—— 模拟退火算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/973401。

相关文章

MySql基本查询之表的增删查改+聚合函数案例详解

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入（单行/多行及冲突处理）,SELECT实现数据检索（列选择、条件过滤、排序分页）,UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更
阅读更多...
使用Python删除Excel中的行列和单元格示例详解

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定
阅读更多...
MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法：多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析
阅读更多...
MySQL中的LENGTH()函数用法详解与实例分析

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集（如UTF-8）的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1：计算字符串
阅读更多...
Python通用唯一标识符模块uuid使用案例详解

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数
阅读更多...
Python办公自动化实战之打造智能邮件发送工具

Python办公自动化实战之打造智能邮件发送工具

《Python办公自动化实战之打造智能邮件发送工具》在数字化办公场景中,邮件自动化是提升工作效率的关键技能,本文将演示如何使用Python的smtplib和email库构建一个支持图文混排,多附件,多... 目录前言一、基础配置：搭建邮件发送框架1.1 邮箱服务准备1.2 核心库导入1.3 基础发送函数二、
阅读更多...
Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理；Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期
阅读更多...
Python包管理工具pip的升级指南

Python包管理工具pip的升级指南

《Python包管理工具pip的升级指南》本文全面探讨Python包管理工具pip的升级策略,从基础升级方法到高级技巧,涵盖不同操作系统环境下的最佳实践,我们将深入分析pip的工作原理,介绍多种升级方... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核
阅读更多...
PowerShell中15个提升运维效率关键命令实战指南

PowerShell中15个提升运维效率关键命令实战指南

《PowerShell中15个提升运维效率关键命令实战指南》作为网络安全专业人员的必备技能,PowerShell在系统管理、日志分析、威胁检测和自动化响应方面展现出强大能力,下面我们就来看看15个提升... 目录一、PowerShell在网络安全中的战略价值二、网络安全关键场景命令实战1. 系统安全基线核查
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2