01背包问题模拟退火算法python代码

以下是01背包问题的模拟退火算法的Python代码：

import random
import math

# 定义背包问题的物品和背包容量
weights = [2, 5, 7, 3, 1, 4, 6]
values = [10, 20, 30, 15, 5, 25, 35]
capacity = 15

# 定义模拟退火算法的参数
initial_temperature = 100
final_temperature = 0.1
cooling_rate = 0.99
iterations = 1000

# 定义函数计算当前解的价值和重量
def evaluate(solution):
    total_weight = 0
    total_value = 0
    for i, value in enumerate(values):
        if solution[i] == 1:
            total_weight += weights[i]
            total_value += value
    return total_weight, total_value

# 定义函数生成新解
def generate_neighbor(solution):
    index = random.randint(0, len(solution) - 1)
    neighbor = solution.copy()
    neighbor[index] = 1 - neighbor[index]
    return neighbor

# 初始化当前解和最优解
current_solution = [random.randint(0, 1) for i in range(len(weights))]
best_solution = current_solution.copy()
best_weight, best_value = evaluate(best_solution)

# 模拟退火算法主循环
temperature = initial_temperature
while temperature > final_temperature:
    for i in range(iterations):
        # 生成新解
        neighbor = generate_neighbor(current_solution)
        # 计算新解的价值和重量
        weight, value = evaluate(neighbor)
        # 判断是否接受新解
        if weight <= capacity and value > best_value:
            best_solution = neighbor.copy()
            best_weight, best_value = evaluate(best_solution)
        delta = value - evaluate(current_solution)[1]
        if delta > 0 or math.exp(delta / temperature) > random.random():
            current_solution = neighbor.copy()
    temperature *= cooling_rate

# 输出结果
print("Best solution: ", best_solution)
print("Best weight: ", best_weight)
print("Best value: ", best_value)

在这个示例中，我们使用了一个简单的01背包问题作为目标问题，并使用模拟退火算法来解决它。我们首先定义了物品的重量和价值，以及背包的容量。然后，我们定义了模拟退火算法的参数，包括初始温度、最终温度、降温速率和迭代次数。接下来，我们定义了一些辅助函数，包括计算当前解的价值和重量、生成新解的函数以及判断是否接受新解的函数。最后，我们使用模拟退火算法来寻找最优解，并输出结果。