使用DEAP库实现带约束背包问题的优化方案求助

问题核心分析 #

你当前的方案存在两个关键问题，导致约束无法有效执行：

1. 适应度权重与目标需求不匹配：定义FitnessMulti时用了weights=(1.0, 1.0)，表示两个目标都要最大化，但你的需求是最大化收益、最小化偏好值，权重设置完全反向。
2. 约束惩罚强度不足且逻辑有漏洞：原惩罚方式的力度可能小于物品的最大收益总和，导致违反约束的个体仍可能被NSGA-II选中；同时仅处理单一约束违反情况，未覆盖同时违反两个约束的场景。

修正后的代码实现 #

1. 修正适应度权重定义 #

creator.create("FitnessMulti", base.Fitness, weights=(1.0, -1.0))  # 第一个目标（收益）最大化，第二个（偏好）最小化
creator.create("Individual", list, fitness=creator.FitnessMulti)

2. 优化约束处理的evaluate函数 #

方案一：极端惩罚法（直接淘汰违反约束的个体）

这种方式让违反约束的个体适应度远低于所有可行解，确保NSGA-II优先选择符合约束的个体：

def evaluate(individual):
    weight = sum(ind * w for ind, w in zip(individual, weights))
    benefit = sum(ind * b for ind, b in zip(individual, benefits))
    preference = sum(ind * p for ind, p in zip(individual, preferences))
    n_total = sum(individual)

    # 检查是否违反任一约束
    if weight > max_weight or n_total > nMax:
        # 返回极差的适应度值，确保违反约束的个体被排序到最后
        return (-10**10, 10**10)
    else:
        # 可行解返回正常目标值
        return (benefit, preference)

方案二：动态惩罚法（保留个体信息但施加足够强的惩罚）

如果希望保留违反约束个体的部分特征，可基于最大可能收益设置惩罚，确保惩罚力度远超任何可行解的收益：

def evaluate(individual):
    weight = sum(ind * w for ind, w in zip(individual, weights))
    benefit = sum(ind * b for ind, b in zip(individual, benefits))
    preference = sum(ind * p for ind, p in zip(individual, preferences))
    n_total = sum(individual)

    penalty = 0
    max_possible_benefit = sum(benefits)  # 计算所有物品的最大收益总和

    # 对重量超支施加惩罚
    if weight > max_weight:
        penalty += (weight - max_weight) * max_possible_benefit * 10
    # 对数量超支施加惩罚
    if n_total > nMax:
        penalty += (n_total - nMax) * max_possible_benefit * 10

    # 调整目标值：收益减惩罚（降低适应度），偏好加惩罚（提高适应度，符合最小化需求）
    adjusted_benefit = benefit - penalty
    adjusted_preference = preference + penalty

    return (adjusted_benefit, adjusted_preference)

3. 可选：交叉/变异后添加修复机制 #

为进一步减少违反约束的个体数量，可在交叉和变异操作后自动修复个体：

def repair_individual(individual):
    # 循环移除物品，直到满足两个约束
    while sum(ind * w for ind, w in zip(individual, weights)) > max_weight or sum(individual) > nMax:
        selected_items = [i for i, val in enumerate(individual) if val == 1]
        if not selected_items:
            break  # 空个体无需修复
        # 随机移除一个已选中的物品
        idx_to_remove = random.choice(selected_items)
        individual[idx_to_remove] = 0
    return individual

# 给交叉和变异操作添加修复装饰器
toolbox.decorate("mate", tools.DeltaPenalty(
    lambda ind: sum(ind*w for ind,w in zip(ind,weights))<=max_weight and sum(ind)<=nMax,
    (-10**10, 10**10),
    repair_individual
))
toolbox.decorate("mutate", tools.DeltaPenalty(
    lambda ind: sum(ind*w for ind,w in zip(ind,weights))<=max_weight and sum(ind)<=nMax,
    (-10**10, 10**10),
    repair_individual
))

关键优化点说明 #

• 权重匹配：通过weights=(1.0, -1.0)明确第一个目标最大化、第二个目标最小化，完全贴合需求。
• 惩罚强度：无论是极端惩罚还是动态惩罚，都确保违反约束的个体适应度远低于可行解，NSGA-II的非支配排序会优先选择符合约束的个体。
• 约束覆盖：同时检查两个约束，避免遗漏同时违反的情况。

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