模拟退火求解0/1背包问题不收敛的技术求助

你的模拟退火算法求解0/1背包问题无法稳定收敛，核心问题出在邻域生成的内存引用错误、接受准则逻辑颠倒，以及部分细节处理不当，下面逐一说明并给出修正后的代码：

关键错误点 #

1. 邻域生成的引用传递问题 #

__generate_new方法中直接修改传入的individual列表（可变对象），导致current和new指向同一个内存地址，当前解会被意外篡改，彻底破坏算法的状态流转逻辑。必须先复制列表再进行修改操作。

2. 接受准则逻辑完全颠倒 #

__accept方法中，delta = 新解适应度 - 当前解适应度：

• 当delta > 0时，新解更优，应该直接接受；
• 当delta < 0时，才需要计算概率接受较差的解。
  你的代码逻辑正好相反，导致更优解被概率拒绝、差解被直接接受，完全违背模拟退火的核心思想。

3. 邻域生成的循环处理不当 #

原方法中，当修改后的解超重（fitness为0）时，持续翻转随机位，但因为直接修改原列表，会导致当前解被反复篡改，应该在副本上操作直到得到合法解。

4. 背包容量的语义混淆 #

self.max = 2*max(self.item_dict)中，item_dict的键是物品重量、值是价值，这里的容量计算是否符合需求？比如测试用例中最大重量是12，容量设为24是合理的，但需要确认是否匹配你的背包问题设定。

修正后的代码 #

import numpy as np
import random as rd
import matplotlib.pyplot as plt

class simulated_knapsack: 
    def __init__(self, item_dict, alpha=0.9, t_max=100, t_min=1e-5, iters=50):
        self.item_dict = item_dict
        self.alpha = alpha
        self.tmax = t_max
        self.tmin = t_min
        self.iters = iters 
        # 确认背包容量：这里用2倍最大重量，可根据需求调整
        self.max_capacity = 2 * max(self.item_dict.keys())
        # 提前提取物品重量和价值列表，避免循环中重复遍历字典
        self.weights = list(self.item_dict.keys())
        self.values = list(self.item_dict.values())

    def main(self): 
        current = self.__initial()
        current_best = current.copy()
        T = self.tmax
        best_fitness_history = []
        
        while T > self.tmin: 
            for _ in range(self.iters):
                new = self.__generate_new(current)
                current_fit = self.__fitness(current)
                new_fit = self.__fitness(new)
                delta = new_fit - current_fit
                
                if self.__accept(delta, T): 
                    current = new
                    if new_fit > self.__fitness(current_best):
                        current_best = new.copy()
            
            best_fitness_history.append(self.__fitness(current_best))
            T *= self.alpha
        
        # 绘制收敛曲线
        plt.scatter(range(len(best_fitness_history)), best_fitness_history, s=4)
        plt.xlabel("降温迭代次数")
        plt.ylabel("当前最优价值")
        plt.title("模拟退火求解0/1背包收敛曲线")
        plt.show()
        
        return (current_best, self.__fitness(current_best))
    
    def __fitness(self, individual):
        total_weight = sum(bit * w for bit, w in zip(individual, self.weights))
        total_value = sum(bit * v for bit, v in zip(individual, self.values))
        # 超重则适应度为0，否则返回总价值
        return total_value if total_weight <= self.max_capacity else 0
    
    def __generate_new(self, individual): 
        # 先复制当前解，避免修改原列表
        new_ind = individual.copy()
        r = rd.randint(0, len(new_ind)-1)
        new_ind[r] = 1 - new_ind[r]
        
        # 如果新解超重，继续翻转随机位直到合法
        while self.__fitness(new_ind) == 0:
            r = rd.randint(0, len(new_ind)-1)
            new_ind[r] = 1 - new_ind[r]
        
        return new_ind
    
    def __initial(self):
        # 生成初始合法解
        while True:
            p = [rd.choice((0, 1)) for _ in range(len(self.weights))]
            if self.__fitness(p) != 0:
                return p
    
    def __accept(self, delta, T): 
        # delta>0：新解更优，直接接受
        if delta > 0:
            return True
        # delta<=0：计算概率接受差解
        else:
            return rd.random() < np.exp(delta / T)

# 测试用例
sk = simulated_knapsack(item_dict={4:3,5:5,6:5,12:20})
best_solution, best_value = sk.main()
print(f"最优解：{best_solution}")
print(f"最优价值：{best_value}")

额外优化点 #

• 提前提取weights和values列表，避免在循环中反复遍历字典，提升运行效率；
• 所有涉及列表赋值的地方使用copy()，确保每个解的独立性；
• 收敛曲线添加坐标轴标签和标题，结果展示更直观；
• 输出最优解和对应价值，方便验证结果正确性。

修正后，对于4个物品的测试用例，算法应该能稳定收敛到最优解（比如[0,1,1,1]，对应重量5+6+12=23，价值5+5+20=30）。

内容的提问来源于stack exchange，提问作者PuzzleheadedSoup-98