矩形排样模拟退火算法代码

根据提供的引用[1]，以下是矩形排样模拟退火算法的Python代码示例：

import math
import random

# 矩形类
class Rectangle:
    def __init__(self, width, height):
        self.width = width
        self.height = height

# 排样类
class Packing:
    def __init__(self, rectangles):
        self.rectangles = rectangles
        self.width = sum([r.width for r in rectangles])
        self.height = max([r.height for r in rectangles])
        self.area = self.width * self.height

    # 计算排样的适应度
    def fitness(self):
        return self.area

    # 随机生成初始解
    def random_solution(self):
        x = 0
        y = 0
        solution = []
        for r in self.rectangles:
            if x + r.width > self.width:
                x = 0
                y += r.height
            solution.append((x, y))
            x += r.width
        return solution

    # 交换两个矩形的位置
    def swap_rectangles(self, solution):
        i = random.randint(0, len(solution) - 1)
        j = random.randint(0, len(solution) - 1)
        while i == j:
            j = random.randint(0, len(solution) - 1)
        new_solution = solution.copy()
        new_solution[i], new_solution[j] = new_solution[j], new_solution[i]
        return new_solution

    # 旋转矩形
    def rotate_rectangle(self, solution):
        i = random.randint(0, len(solution) - 1)
        new_solution = solution.copy()
        x, y = new_solution[i]
        r = self.rectangles[i]
        new_solution[i] = (x, y, not r.rotated)
        return new_solution

    # 扰动产生新解
    def perturb(self, solution):
        if random.random() < 0.5:
            return self.swap_rectangles(solution)
        else:
            return self.rotate_rectangle(solution)

    # 模拟退火算法
    def simulated_annealing(self, initial_temperature=1000, cooling_rate=0.95, stopping_temperature=1e-8):
        current_solution = self.random_solution()
        current_fitness = self.fitness()
        best_solution = current_solution
        best_fitness = current_fitness
        temperature = initial_temperature
        while temperature > stopping_temperature:
            new_solution = self.perturb(current_solution)
            new_fitness = self.fitness()
            delta_fitness = new_fitness - current_fitness
            if delta_fitness < 0 or math.exp(-delta_fitness / temperature) > random.random():
                current_solution = new_solution
                current_fitness = new_fitness
                if current_fitness < best_fitness:
                    best_solution = current_solution
                    best_fitness = current_fitness
            temperature *= cooling_rate
        return best_solution