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

使用模拟退火算法进行优化的案例：Python实现与详细介绍

article 2024/11/16 21:59:21

使用模拟退火算法进行优化的案例：Python实现与详细介绍

1. 案例背景介绍

模拟退火算法（Simulated Annealing, SA）是一种用于全局优化的随机搜索算法，模拟了物理学中的退火过程。它能够在解空间中进行局部和全局搜索，从而避免陷入局部最优。在许多实际问题中，模拟退火算法被广泛用于求解复杂的优化问题，如旅行商问题、工厂调度问题等。

在本案例中，我们使用模拟退火算法来优化一个函数，使其获得最小值。通过这个过程，我们展示如何使用 Python 实现模拟退火算法，并运用面向对象的设计思想来组织代码。

2. 优化问题描述

本案例中，我们要优化以下目标函数：

$f(x, y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2$

这个函数有多个局部最小值，我们的目标是使用模拟退火算法找到使目标函数值最小的点。

优化目标

找到 $x$ 和 $y$ 的最优值，使得目标函数 $f (x, y)$ 最小化。目标函数是非线性且具有多个局部最优值，适合使用模拟退火算法进行全局优化。

问题范围

我们限定 $x$ 和 $y$ 的范围在 [-6, 6] 之间，即解空间为二维平面上的一个有限区域。

3. 使用模拟退火算法解决优化问题

个体表示

在模拟退火算法中，每一个解（个体）由变量 $x$ 和 $y$ 组成。因此，我们可以将一个个体表示为一个二维向量 $[x, y]$ 。

能量函数的定义

模拟退火算法使用能量函数（类似于遗传算法中的适应度函数）来衡量当前解的优劣。能量函数越小，解的质量越高。在本问题中，能量函数就是我们要最小化的目标函数：

def energy(x, y):
    return (x**2 + y - 11)**2 + (x + y**2 - 7)**2

模拟退火流程

初始状态：随机选择一个初始解 $x_0, y_0]$ ，并计算其能量。
温度衰减：设置一个初始温度 $T_0$ ，并随着迭代次数逐渐降低温度。
邻域搜索：在当前解的邻域内随机选择一个新的解 $[x^{'}, y^{'}]$ 。
接受概率：计算新解的能量。如果新解的能量比当前解更小，则直接接受新解；否则以一定概率接受新解，概率由温度决定。
迭代过程：重复进行邻域搜索和接受决策，直到温度衰减至预定的阈值。

4. Python 面向对象实现

为了更好地组织模拟退火算法的实现，我们采用面向对象的设计，创建一个 SimulatedAnnealing 类，包含算法的初始化、温度衰减、邻域搜索和接受决策等操作。

代码实现：类的设计

import random
import math

class SimulatedAnnealing:
    def __init__(self, initial_temp, cooling_rate, min_temp, bounds, energy_func):
        self.temperature = initial_temp  # 初始温度
        self.cooling_rate = cooling_rate  # 温度衰减率
        self.min_temp = min_temp  # 最低温度
        self.bounds = bounds  # 搜索空间范围
        self.energy_func = energy_func  # 能量函数
        self.current_state = self._random_solution()  # 初始解
        self.current_energy = self.energy_func(*self.current_state)  # 当前能量

    def _random_solution(self):
        """ 在给定范围内随机生成初始解 """
        x = random.uniform(self.bounds[0][0], self.bounds[0][1])
        y = random.uniform(self.bounds[1][0], self.bounds[1][1])
        return [x, y]

    def _neighbor_solution(self):
        """ 生成当前解附近的解 """
        x, y = self.current_state
        new_x = random.uniform(max(self.bounds[0][0], x - 1), min(self.bounds[0][1], x + 1))
        new_y = random.uniform(max(self.bounds[1][0], y - 1), min(self.bounds[1][1], y + 1))
        return [new_x, new_y]

    def _accept_probability(self, new_energy):
        """ 计算接受新解的概率 """
        if new_energy < self.current_energy:
            return 1.0
        else:
            return math.exp((self.current_energy - new_energy) / self.temperature)

    def cool_down(self):
        """ 温度衰减 """
        self.temperature *= self.cooling_rate

    def optimize(self):
        """ 主优化过程 """
        while self.temperature > self.min_temp:
            new_solution = self._neighbor_solution()
            new_energy = self.energy_func(*new_solution)

            # 根据接受概率决定是否接受新解
            if random.random() < self._accept_probability(new_energy):
                self.current_state = new_solution
                self.current_energy = new_energy

            # 温度衰减
            self.cool_down()

        return self.current_state, self.current_energy

类的构造方法

initial_temp：初始温度。
cooling_rate：温度衰减率，通常设置为小于1的值（例如0.99）。
min_temp：最低温度，算法在达到该温度时停止。
bounds：搜索空间的边界，例如 bounds = [(-6, 6), (-6, 6)] 表示变量 $x$ 和 $y$ 的取值范围都在 [-6, 6]。
energy_func：目标函数（能量函数），用于衡量当前解的好坏。

类的主要方法

_random_solution()：在给定范围内随机生成初始解。
_neighbor_solution()：在当前解的邻域内随机生成新解。
_accept_probability()：根据当前温度和能量差计算接受新解的概率。
cool_down()：温度衰减。
optimize()：优化过程的主循环，直到温度降至最低。

退火过程的关键操作

邻域搜索：在当前解附近生成一个新解，这可以通过在当前变量值的基础上加上一个随机偏移量来实现。
接受决策：根据能量差和当前温度计算接受新解的概率。接受新解的概率是通过指数函数计算的，当温度较高时，算法可以接受较差的解，从而避免陷入局部最优。
温度衰减：随着迭代的进行，温度逐渐降低，接受较差解的概率也逐渐减小。最终，算法趋向于接受更好的解，并收敛到一个近似最优的解。

5. 结果分析

我们将模拟退火算法应用于目标函数 $f(x, y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2$ ，并观察其优化过程。以下是该函数的可视化图像：

import matplotlib.pyplot as plt
import numpy as np

# 定义目标函数
def objective_function(x, y):
    return (x**2 + y - 11)**2 + (x + y**2 - 7)**2

# 绘制目标函数的等高线图
x = np.linspace(-6, 6, 400)
y = np.linspace(-6, 6, 400)
X, Y = np.meshgrid(x, y)
Z = objective_function(X, Y)

plt.contour(X, Y, Z, levels=50)
plt.title("Objective Function Contour Plot")
plt.xlabel("x")
plt.ylabel("y")
plt.show()

运行模拟退火算法，设置初始温度、温度衰减率和最低温度等参数后，算法可以有效地找到目标函数的近似最优解：

# 定义能量函数
def energy(x, y):
    return (x**2 + y - 11)**2 + (x + y**2 - 7)**2

# 初始化模拟退火算法
sa = SimulatedAnne

aling(initial_temp=1000, cooling_rate=0.99, min_temp=0.01, bounds=[(-6, 6), (-6, 6)], energy_func=energy)

# 开始优化
best_solution, best_energy = sa.optimize()

print(f"最佳解: {best_solution}")
print(f"最小能量: {best_energy}")