基于Python的Tabu Search算法邻域构造问题咨询

核心实现逻辑 #

• 首先筛选出所有未出现在初始解P0中的点位作为替换候选池，因为候选池已排除P0内的所有点位，替换后的新解自然不会出现内部重复元素，无需额外校验
• 每次从候选池中抽取2个不重复的点位，替换P0的前2位，剩余元素保持不变，生成单个邻域解
• 生成过程中对已生成的邻域解做去重处理，避免输出重复的邻域解
• 做边界兼容处理：当要求生成的邻域数量超过理论最大不重复邻域数时，自动调整为最大可生成数量

完整代码实现 #

import random
from itertools import combinations

def generate_neighborhood(P0, total_wells=49, n_neighbors=10):
    # 生成候选替换点位池：所有未在P0中出现的点位
    used_points = set(P0)
    candidate_pool = [point_id for point_id in range(total_wells) if point_id not in used_points]
    
    # 计算最大可生成的不重复邻域解数量
    max_available = len(candidate_pool) * (len(candidate_pool) - 1) // 2
    if n_neighbors > max_available:
        print(f"提示：最多可生成{max_available}个不重复邻域解，已自动调整生成数量")
        n_neighbors = max_available
    
    neighborhood_set = set()
    # 小批量邻域用随机抽取方式，效率更高
    if n_neighbors < max_available * 0.3:
        while len(neighborhood_set) < n_neighbors:
            # 随机抽取2个不重复的候选点位
            replace_points = random.sample(candidate_pool, 2)
            # 生成新解：替换前2位，保留原解剩余部分
            new_solution = tuple(replace_points + P0[2:])
            neighborhood_set.add(new_solution)
    # 大批量邻域直接生成所有组合再采样，避免循环多次
    else:
        all_possible_pairs = list(combinations(candidate_pool, 2))
        selected_pairs = random.sample(all_possible_pairs, n_neighbors)
        for pair in selected_pairs:
            new_solution = tuple(list(pair) + P0[2:])
            neighborhood_set.add(new_solution)
    
    # 转换为列表格式返回
    return [list(sol) for sol in neighborhood_set]

调用示例 #

# 初始解示例
P0 = [0,1,3,4,5,6]
# 生成8个邻域解
neighbor_solutions = generate_neighborhood(P0, n_neighbors=8)
# 输出结果
print(neighbor_solutions)

内容的提问来源于stack exchange，提问作者mohammad hassan moayyedian