FFD+模拟退火优化一维装箱问题无效，求改进方案

我正在开发一维装箱问题的项目，目标是优化FirstFitDecreasing（FFD）算法的解，减少箱子使用数量。但当前结合Simulated Annealing（模拟退火）的实现无法提升解的质量，怀疑问题出在退火器或generate_neighbour函数的实现上，求改进思路。

测试实例说明 #

测试采用BPPlib库中的Falkenauer_u120_00.txt文件，每行存储一个物品重量，实例内容示例：

120
150
98
98
98
96
96
94
...

该实例的最优解可参考对应表格数据。

完整实现代码 #

import random
import math

def Le_Instancia(filename):
    try:
        with open(filename, 'r') as file:
            weight = [int(line.strip()) for line in file]
            return weight
    except FileNotFoundError:
        print("Arquivo não encontrado. (Verifique se o arquivo está na pasta correta)")
        return []

def FirstFitDecreasing(weight, n, bin_capacity):
    # Inicializa objetivo (número de bins)
    # Pior caso: n = objetivo
    objetivo = 0

    # Cria uma lista para armazenar o espaço restante nos bins
    bin_rem = [0]*n

    # Lista de listas para armazenar as bins utilizadas com os itens dentro
    bins_used = [[] for _ in range(n)]

    # Ordena os itens em ordem decrescente de peso
    weight.sort(reverse=True)

    # Adiciona os itens um por um
    for i in range(n):
        # Acha a primeira bin que pode acomodar weight[i]
        j = 0
        while j < objetivo:
            if bin_rem[j] >= weight[i]:
                bin_rem[j] = bin_rem[j] - weight[i]
                bins_used[j].append(weight[i])  # Adiciona o item na bin
                break
            j += 1

        # Caso não exista bin que possa acomodar weight[i], cria um novo bin
        if j == objetivo:
            bin_rem[objetivo] = bin_capacity - weight[i]
            bins_used[objetivo].append(weight[i])  # Adiciona o item na nova bin
            objetivo = objetivo + 1

    bins_used = bins_used[:objetivo]

    return objetivo, bins_used


def cost_function(bins_used):
    return len(bins_used)

def simulated_annealing(weight, n, bin_capacity, initial_temperature, cooling_rate, max_iterations):
    # First Fit Decreasing initial solution
    objective, bins_used = FirstFitDecreasing(weight, n, bin_capacity)
    best_objective = objective
    best_solution = bins_used

    # Initialize temperature
    temperature = initial_temperature

    for i in range(max_iterations):
        # Generate a neighbor solution by perturbing the current solution
        neighbor_bins_used = generate_neighbour(bins_used, bin_capacity)
        print(neighbor_bins_used)
        # Calculate the cost (number of bins) of the neighbor solution
        neighbor_objective = cost_function(neighbor_bins_used)
        #print(neighbor_objective)

        # Calculate the cost of the current solution
        current_objective = cost_function(bins_used)

        # Determine if the neighbor solution is accepted
        if neighbor_objective < current_objective:
            # Accept the neighbor solution if it's better
            bins_used = neighbor_bins_used
            objective = neighbor_objective

            # Update the best solution if necessary
            if neighbor_objective < best_objective:
                best_objective = neighbor_objective
                best_solution = neighbor_bins_used
        else:
            # Calculate the probability of accepting a worse solution
            probability = math.exp((current_objective - neighbor_objective) / temperature)

            # Accept the neighbor solution with a probability
            if random.random() < probability:
                bins_used = neighbor_bins_used
                objective = neighbor_objective
        
        # Cool down the temperature
        temperature *= cooling_rate
    #print(len(neighbor_bins_used))
    return best_objective, best_solution


def generate_neighbour(bins_used, bin_capacity):
    num_bins = len(bins_used)
    if num_bins < 2:
        return bins_used
    
    new_bins_used = [bin_content.copy() for bin_content in bins_used]

    # Choose two bins randomly
    bin1, bin2 = random.sample(range(num_bins), 2)

    # Choose a random number of items to swap
    num_items_to_swap = random.randint(1, min(len(new_bins_used[bin1]), len(new_bins_used[bin2])))

    # Swap items between bins
    for _ in range(num_items_to_swap):
        item1 = random.choice(new_bins_used[bin1])
        item2 = random.choice(new_bins_used[bin2])
        if sum(new_bins_used[bin1]) - item1 + item2 <= bin_capacity and sum(new_bins_used[bin2]) - item2 + item1 <= bin_capacity:
            new_bins_used[bin1].remove(item1)
            new_bins_used[bin2].remove(item2)
            new_bins_used[bin1].append(item2)
            new_bins_used[bin2].append(item1)

    # Remove empty bins
    new_bins_used = [bin_content for bin_content in new_bins_used if bin_content]

    return new_bins_used


filename = "/home/TEO/main/Falkenauer/Falkenauer_U/Falkenauer_u120_00.txt"  
weight = Le_Instancia(filename)
n = len(weight)
bin_capacity = 150 # Replace with the bin capacity
initial_temperature = 1000
cooling_rate = 0.95
max_iterations = 100000

best_objective, best_solution = simulated_annealing(weight, n, bin_capacity, initial_temperature, cooling_rate, max_iterations)

print("Best number of bins:", best_objective)
print("Best solution (bins used):", best_solution)

改进思路 #

一、generate_neighbour函数的核心问题与优化 #

现有交换策略的局限性：当前随机交换两个箱子里的物品，且仅保留满足容量约束的组合，这种方式很难产生能减少箱子数量的邻居解。FFD初始解本身已较优，单纯交换物品几乎无法腾出空箱子，多数操作属于无效迭代。

推荐三种改进的邻居生成策略：

1. 单物品移动策略：随机选择一个物品，尝试将其移到其他能容纳它的箱子，而非局限于两两交换，更易产生可优化的解：

   def generate_neighbour(bins_used, bin_capacity):
       num_bins = len(bins_used)
       if num_bins < 1:
           return bins_used
       
       new_bins = [b.copy() for b in bins_used]
       # 随机选一个有物品的箱子和里面的物品
       src_bin_idx = random.randint(0, num_bins-1)
       while not new_bins[src_bin_idx]:
           src_bin_idx = random.randint(0, num_bins-1)
       item = random.choice(new_bins[src_bin_idx])
       
       # 尝试5次找合适的目标箱子
       for _ in range(5):
           dest_bin_idx = random.randint(0, num_bins-1)
           if dest_bin_idx != src_bin_idx and sum(new_bins[dest_bin_idx]) + item <= bin_capacity:
               new_bins[src_bin_idx].remove(item)
               new_bins[dest_bin_idx].append(item)
               break
       
       # 移除空箱子
       new_bins = [b for b in new_bins if b]
       return new_bins
   

2. 多物品重组策略：随机选择两个箱子，尝试重新分配它们的物品以最大化空间利用率，或直接将一个箱子的物品合并到另一个（若容量允许）。
3. 移除重插策略：随机选择若干物品移除，用BestFit规则重新插入到解中，更有可能产生更优布局。

二、模拟退火核心逻辑优化 #

1. 参数调整：当前初始温度1000、冷却率0.95、10万次迭代的组合易导致过早收敛或探索不足。建议：
   • 初始温度调整为100-200，冷却率改为0.99（放慢冷却速度，增加探索时间）。
   • 改为温度降到阈值（如1e-3）时停止迭代，而非固定次数。
2. 成本函数优化：仅用箱子数作为成本指标过于单一，可加入剩余空间惩罚项，优先选择空间利用率更高的解，为后续优化铺垫：

   def cost_function(bins_used, bin_capacity):
       num_bins = len(bins_used)
       total_remaining = sum(bin_capacity - sum(b) for b in bins_used)
       # 箱子数为核心指标，剩余空间为次要惩罚，系数可按需调整
       return num_bins + total_remaining / (bin_capacity * num_bins)
   

3. 最优解跟踪优化：当邻居解的箱子数与当前最优相同时，若其空间利用率更高，也更新最优解，提升后续迭代的优化潜力。

三、其他辅助优化 #

1. 初始解多样化：不要仅依赖FFD初始解，可同时生成FFD、BestFitDecreasing、随机布局等多个初始解，分别用模拟退火优化后取最优结果。
2. 加入局部搜索：在模拟退火每一步后，对当前解做局部微调（如将每个物品移到最优容纳箱子），进一步提升解的质量。
3. 避免无效操作：在邻居生成时，跳过不会改变解的操作（如交换同重量物品），减少无效迭代。

内容的提问来源于stack exchange，提问作者Matheus Soares