如何为该NP难遗传算法装箱问题设计染色体与适应度函数？

首先统一单位：纸箱容量为 2000000立方厘米（2立方米转换而来），目标是最大化装入的塑料盒总数，这是以数量为目标的背包变种问题，和普通0-1背包（最大化价值）的核心差异在目标函数，这也是你借鉴普通背包思路失败的主要原因。下面直接给出可落地的遗传算法实现方案：

核心模块设计 #

1. 编码方式 #

放弃二进制编码（单种盒子数量可能上万，二进制串过长效率极低），采用整数数组编码：每个染色体表示为 [a, b, c]，其中：

• a = 20立方厘米盒子的数量
• b = 35立方厘米盒子的数量
• c = 60立方厘米盒子的数量

2. 适应度函数 #

适应度直接对应目标（最大化数量），同时加入约束判断：

def calculate_fitness(individual):
    a, b, c = individual
    total_volume = 20*a + 35*b + 60*c
    # 超容量个体直接赋值0适应度（也可采用惩罚机制，比如2000000 - (total_volume - 2000000)，需保证非负）
    if total_volume > 2000000:
        return 0
    # 符合约束的个体，适应度为总数量
    return a + b + c

3. 选择操作 #

推荐用锦标赛选择（比轮盘赌更稳定，适合新手）：随机选取2个个体，保留适应度更高的那个进入下一代。

4. 交叉操作 #

对两个父代染色体进行基因片段交换，比如随机选择交叉点交换后两位：

def crossover(parent1, parent2):
    if random.random() < 0.7:  # 交叉概率设为0.7
        # 交换b和c基因
        return [parent1[0], parent2[1], parent2[2]], [parent2[0], parent1[1], parent1[2]]
    return parent1.copy(), parent2.copy()

5. 变异操作+约束修复 #

变异时随机调整某个基因的数量，若导致总容量超标，优先减少大容量盒子（减少1个60立方厘米的盒子，可替换为3个20立方厘米的盒子，能保留更多数量）：

def mutate(individual):
    if random.random() < 0.1:  # 变异概率设为0.1
        gene_idx = random.randint(0, 2)
        # 随机增减1-5个，保证数量非负
        delta = random.randint(-5, 5)
        individual[gene_idx] = max(0, individual[gene_idx] + delta)
        
        # 修复超容量问题
        a, b, c = individual
        total_volume = 20*a + 35*b + 60*c
        while total_volume > 2000000:
            if c > 0:
                c -= 1
            elif b > 0:
                b -= 1
            else:
                a -= 1
            total_volume = 20*a + 35*b + 60*c
        individual = [a, b, c]
    return individual

完整实现代码 #

import random

# 参数设置
POP_SIZE = 100
MAX_GENERATIONS = 500
MUTATION_RATE = 0.1
CROSSOVER_RATE = 0.7
MAX_CAPACITY = 2000000
BOX_SIZES = [20, 35, 60]

# 初始化种群：生成可行解
def init_population():
    pop = []
    for _ in range(POP_SIZE):
        # 随机生成不超容量的个体
        max_a = MAX_CAPACITY // BOX_SIZES[0]
        a = random.randint(0, max_a)
        max_b = (MAX_CAPACITY - a*BOX_SIZES[0]) // BOX_SIZES[1]
        b = random.randint(0, max_b)
        max_c = (MAX_CAPACITY - a*BOX_SIZES[0] - b*BOX_SIZES[1]) // BOX_SIZES[2]
        c = random.randint(0, max_c)
        pop.append([a, b, c])
    return pop

# 适应度计算
def calculate_fitness(individual):
    a, b, c = individual
    total_volume = 20*a + 35*b + 60*c
    if total_volume > MAX_CAPACITY:
        return 0
    return a + b + c

# 锦标赛选择
def select(pop, fitnesses):
    selected = []
    for _ in range(POP_SIZE):
        idx1, idx2 = random.sample(range(POP_SIZE), 2)
        selected.append(pop[idx1].copy() if fitnesses[idx1] > fitnesses[idx2] else pop[idx2].copy())
    return selected

# 交叉操作
def crossover(parent1, parent2):
    if random.random() < CROSSOVER_RATE:
        return [parent1[0], parent2[1], parent2[2]], [parent2[0], parent1[1], parent1[2]]
    return parent1.copy(), parent2.copy()

# 变异操作
def mutate(individual):
    if random.random() < MUTATION_RATE:
        gene_idx = random.randint(0, 2)
        delta = random.randint(-5, 5)
        individual[gene_idx] = max(0, individual[gene_idx] + delta)
        
        a, b, c = individual
        total_volume = 20*a + 35*b + 60*c
        while total_volume > MAX_CAPACITY:
            if c > 0:
                c -= 1
            elif b > 0:
                b -= 1
            else:
                a -= 1
            total_volume = 20*a + 35*b + 60*c
        individual = [a, b, c]
    return individual

# 主循环
if __name__ == "__main__":
    pop = init_population()
    for gen in range(MAX_GENERATIONS):
        fitnesses = [calculate_fitness(ind) for ind in pop]
        best_idx = fitnesses.index(max(fitnesses))
        best_ind = pop[best_idx]
        print(f"第{gen+1}代 | 最优数量: {fitnesses[best_idx]} | 总容量: {20*best_ind[0]+35*best_ind[1]+60*best_ind[2]}")
        
        selected = select(pop, fitnesses)
        new_pop = []
        # 批量交叉
        for i in range(0, POP_SIZE, 2):
            p1 = selected[i]
            p2 = selected[i+1] if i+1 < POP_SIZE else selected[i]
            c1, c2 = crossover(p1, p2)
            new_pop.append(c1)
            new_pop.append(c2)
        # 批量变异
        pop = [mutate(ind) for ind in new_pop[:POP_SIZE]]
    
    # 输出最终结果
    final_fitnesses = [calculate_fitness(ind) for ind in pop]
    best_idx = final_fitnesses.index(max(final_fitnesses))
    best_ind = pop[best_idx]
    print("\n最终最优解:")
    print(f"20cm³盒子: {best_ind[0]}个 | 35cm³盒子: {best_ind[1]}个 | 60cm³盒子: {best_ind[2]}个")
    print(f"总数量: {final_fitnesses[best_idx]} | 总容量: {20*best_ind[0]+35*best_ind[1]+60*best_ind[2]}立方厘米")

关键调试建议 #

1. 避免二进制编码：单种盒子数量上限达100000，二进制串长度会超过17位，运算效率极低，整数编码更适配。
2. 约束修复优先减少大容量盒子：这是保证数量最大化的关键，直接丢弃超容量个体会拖慢进化速度。
3. 参数调整：若进化陷入局部最优，可尝试增大种群规模（比如调到200）或提升变异率（比如0.15）；若结果波动大，可降低变异率。

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