遗传算法能否生成可变规模解？多可变组染色体优化问题求助

尝试用单目标简单遗传算法解决分组组合优化问题，但遇到核心障碍：

• 初始染色体需由2个及以上可变规模的组构成，示例结构为[[P1,P1],[P2,P2,P3]]（第1组含2个同类型元素，第2组含2个P2类型+1个P3类型元素）
• 目标是找到组间的最优组合，最终生成如[P1,P1,P2,P2]或[P1,P1,P3]这类符合场景逻辑的结果（即从每组中选择指定数量/类型的元素组合）
• 多次重构算法后，要么得到包含全部基因的结果，要么输出完全不符合场景逻辑的解，不确定这类算法是否适配需求，也不清楚核心遗漏点。

附当前使用的适应度函数代码：

def fitness_function(ga_instance, solution, solution_idx):
    total_volume = 0
     best_genes = {}
     for i in range(0, len(solution), 4):
        specie_idx = solution[i]
        age = solution[i + 1]
        type_ = solution[i + 2]
        area = solution[i + 3]
        specie_id = index_to_species[specie_idx]
    
        volume = calculate_volume(specie_id, age, type_, stands_by_species)
    
        #At the moment finds the best when Pxy is the same like P11
        prefix = specie_id.split('_')[0][:3]
        print("Prefix", prefix)
        
        if prefix not in best_genes or volume > best_genes[prefix][4]:
          best_genes[prefix] = (specie_id, age, type_, area, volume)
    
        total_volume = sum([gene[4] for gene in best_genes.values()])
     return total_volume

核心问题诊断 #

当前实现存在两个致命偏差：

1. 染色体编码逻辑错误：用一维固定长度编码（每4个元素代表一个基因），未体现分组结构，导致遗传操作（交叉/变异）无法识别组边界，容易产生跨组的无效组合。
2. 适应度函数与目标不匹配：当前函数仅将所有基因按前缀分组，保留每组中容积最大的单个基因求和，完全背离了“从每组选多个元素组合优化”的目标，自然会得到要么全选、要么只留单基因的异常结果。

技术实现思路 #

这类问题完全可以用用遗传算法解决，核心是针对分组特性定制编码、遗传算子和约束逻辑：

1. 重构染色体编码 #

放弃一维固定长度编码，采用分层嵌套编码直接体现分组结构：

• 每个染色体是一个列表，列表中的每个元素对应一个组，组内是该组选中的基因集合
• 示例：染色体[[P1,P1], [P2,P2]]代表第一组选2个P1，第二组选2个P2；[[P1,P1], [P3]]代表第一组选2个P1，第二组选1个P3
• 每个基因可沿用之前的4元组（specie_idx, age, type_, area）格式，方便后续计算

2. 定制遗传操作算子 #

必须针对分组结构设计交叉、变异算子，避免产生无效解：

• 交叉算子：
  • 仅在同组之间交换基因子集，比如随机选择两组，交换组内的部分基因；或者直接交换整个组的基因集合（如果组的类型允许）
  • 禁止跨组交换基因，避免出现P1混入第二组的逻辑错误
• 变异算子：
  • 组内替换：随机选中某组的一个基因，替换为该组允许的其他类型基因（比如第二组内把P2换成P3）
  • 组内增减：随机在某组添加一个符合类型的基因，或删除一个基因（需保证每组至少保留1个基因，符合场景需求）

3. 嵌入约束校验机制 #

在遗传操作后立即执行约束校验，过滤或修复无效解：

• 类型约束：检查每组内的基因是否符合该组允许的类型（比如第二组只能包含P2或P3，不能混入P1）
• 数量约束：检查每组的基因数量是否在合理范围（比如第一组最多2个，第二组最多3个）
• 对不符合约束的解，要么直接丢弃（从种群中移除），要么自动修复（比如删除违规基因、替换为合规基因）

4. 优化适应度函数 #

调整适应度函数逻辑，匹配“组内多基因组合优化”的目标：

def fitness_function(ga_instance, solution, solution_idx):
    total_volume = 0
    penalty = 0
    # 遍历每个组
    for group in solution:
        group_volume = 0
        # 根据实际场景定义当前组允许的基因类型
        allowed_types = get_allowed_types_for_group(group)
        for gene in group:
            specie_idx, age, type_, area = gene
            specie_id = index_to_species[specie_idx]
            # 校验类型合规性，违规则施加惩罚
            if type_ not in allowed_types:
                penalty += 100  # 惩罚数值根据需求调整
                continue
            # 计算单个基因的容积并累加
            volume = calculate_volume(specie_id, age, type_, stands_by_species)
            group_volume += volume
        total_volume += group_volume
    
    # 对组内基因数量超限的情况施加惩罚
    for group in solution:
        if len(group) > 3:
            penalty += (len(group) - 3) * 50
    
    # 最终适应度为总容积减去惩罚项，引导算法收敛到合规最优解
    return total_volume - penalty

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