如何用PyGAD的遗传算法求解多背包问题并配置m维解？

核心问题 #

PyGAD默认将每个种群个体视为一维数组，你传入的m×n二维初始种群会被自动扁平化，导致算法无法识别你期望的多背包二维结构，进而引发计算错误。

解决步骤 #

1. 调整解的编码方式

将每个解设计为一维数组，长度为m*n（背包数×物品数）。例如2个背包、3个物品的解结构为：
[背包1_物品1, 背包1_物品2, 背包1_物品3, 背包2_物品1, 背包2_物品2, 背包2_物品3]
这样既符合PyGAD的要求，又能通过reshape还原为二维结构进行约束检查。

2. 修正适应度函数

在计算适应度时，先将一维解reshape为m×n的二维数组，再执行约束检查和适应度计算：

• 检查每个背包的重量是否超过容量
• 检查每个物品是否被放入多个背包
• 移除对initial_population的错误引用，改用当前解进行计算
• 修正惩罚逻辑：违反约束时给极低适应度（而非高值，因为PyGAD默认最大化适应度）

3. 调整初始种群

将原二维初始种群扁平化，转为一维数组的集合，确保每个个体长度与num_genes一致。

4. 修正PyGAD参数

将num_genes设为m*n，直接用背包数和物品数计算，避免手动计算size出错。

修改后的完整代码 #

import numpy as np
import pygad

knapsacks = np.array([7, 8])
items = np.array([3, 4, 5])
m = len(knapsacks)
n = len(items)

# 初始种群：每个解为一维数组，长度m*n
initial_population = np.array([
    [1, 0, 0, 0, 1, 0],  # 背包1选物品1，背包2选物品2
    [0, 1, 0, 1, 0, 0],  # 背包1选物品2，背包2选物品1
    [0, 0, 1, 1, 1, 0],  # 背包1选物品3，背包2选物品1+2（总重7，符合容量）
])

def fitness_func(solution, solution_idx):
    # 将一维解转为m×n的二维结构
    solution_2d = solution.reshape(m, n)
    
    # 检查背包容量约束
    knapsack_weights = np.sum(solution_2d * items, axis=1)
    if np.any(knapsack_weights > knapsacks):
        return 0  # 违反约束，给极低适应度
    
    # 检查物品唯一性约束（每个物品最多放一个背包）
    item_counts = np.sum(solution_2d, axis=0)
    if np.any(item_counts > 1):
        return 0  # 违反约束，给极低适应度
    
    # 合法解的适应度为总重量（最大化目标）
    total_weight = np.sum(solution_2d * items)
    return total_weight

ga_instance = pygad.GA(
    num_generations=30,
    num_parents_mating=2,
    fitness_func=fitness_func,
    sol_per_pop=10,
    num_genes=m*n,  # 基因数为背包数×物品数
    gene_space=[0, 1],
    mutation_by_replacement=True,
    gene_type=int,
    parent_selection_type="sss",
    keep_parents=1,
    crossover_type="single_point",
    mutation_type="random",
    mutation_num_genes=1,
    initial_population=initial_population
)

ga_instance.run()
solution, solution_fitness, solution_idx = ga_instance.best_solution() 

# 将最优解转回二维结构查看
best_solution_2d = solution.reshape(m, n)
print("最优解（二维）：")
print(best_solution_2d)
print("总重量：", solution_fitness)

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