实现Beam Search时的优化交换技术问询：避免ID重复

问题分析 #

• 原代码核心错误：生成候选解的逻辑并非交换操作，而是将全局IDs数组的第i个元素直接插入当前序列的i位置，而当前序列已包含所有唯一ID，因此必然导致ID重复。
• 目标函数存在bug：sum(Values[IDs.index(IDs)] for IDs in ID_order)中循环变量名与全局IDs冲突，且索引逻辑错误，无法正确计算对应Values的总和。

无重复候选解的生成方法 #

为生成合法的无重复候选序列，可采用以下邻域操作（均不会产生重复ID）：

• 交换任意两个不同位置的元素：对当前序列中两个不同索引的元素互换位置，生成新序列。
• 移动单个元素到其他位置：将某位置的元素移动到另一位置，其余元素顺序顺延。
• 反转子序列：反转一段连续子序列，保持所有ID唯一。

这里选择两两交换的方法，实现简单且能有效探索解空间，适配Beam Search的迭代优化逻辑。

修正后的完整代码 #

import random

beam_width = 2
max_iterations = 4  

IDs =  [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
Values =  [10,11,23,33,23,233,22,13,78,90,9,8,10,11,45,34,45,18,19,20]

# 修正后的目标函数
def objective_function(ID_order):
    total_performance = sum(Values[IDs.index(id)] for id in ID_order)
    return total_performance
    
# 修正后的Beam Search函数
def beam_search(IDs, beam_width, max_iterations):
    # 初始化候选解：随机生成全排列并计算初始目标值
    initial_order = random.sample(IDs, len(IDs))
    candidate_solutions = [(initial_order, objective_function(initial_order))]
    best_ID_order = initial_order.copy()
    best_objective = candidate_solutions[0][1]
    
    for iteration in range(max_iterations):
        new_candidates = []
        # 遍历当前候选解，生成所有两两交换的邻域解
        for ID_order, _ in candidate_solutions:
            for i in range(len(ID_order)):
                for j in range(i + 1, len(ID_order)):
                    new_order = ID_order.copy()
                    new_order[i], new_order[j] = new_order[j], new_order[i]
                    obj = objective_function(new_order)
                    new_candidates.append((new_order, obj))
        
        # 去重：避免相同序列重复计算
        unique_candidates = []
        seen = set()
        for order, obj in new_candidates:
            order_tuple = tuple(order)
            if order_tuple not in seen:
                seen.add(order_tuple)
                unique_candidates.append((order, obj))
        
        # 按目标值降序排序，保留前beam_width个候选
        unique_candidates.sort(key=lambda x: x[1], reverse=True)
        candidate_solutions = unique_candidates[:beam_width]
        
        # 更新全局最优解
        if candidate_solutions[0][1] > best_objective:
            best_ID_order = candidate_solutions[0][0].copy()
            best_objective = candidate_solutions[0][1]
    
    return best_ID_order, best_objective

best_ID_order, best_objective = beam_search(IDs, beam_width, max_iterations)
print("全局最优ID顺序:", best_ID_order)
print("全局最优目标值:", best_objective)

关键改动说明 #

1. 修复目标函数：修改循环变量名避免冲突，正确通过ID在全局数组中的索引获取对应Values值。
2. 替换候选生成逻辑：用两两交换操作替代错误的插入逻辑，确保所有候选序列都是无重复的全排列。
3. 添加去重步骤：过滤重复的候选序列，减少无效计算开销。
4. 初始化逻辑修正：初始候选解直接计算目标值，保证初始状态的逻辑一致性。

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