Jenetics库约束仍被违反：0-1线性规划优化问题求助

问题背景 #

处理含25000个0-1变量（0=选中，1=不选中）、数百条约束的线性规划优化问题，基于Jenetics实现的遗传算法始终无法输出满足约束的解——例如某约束要求选中物品比例≤9%，但结果始终维持在9.0x%左右。

当前实现的核心问题 #

1. 初始种群完全偏离约束要求
   基因型工厂设置BitChromosome.of(objects.size(), 0.9)意味着初始种群中每个基因有90%的概率为1，即默认选中90%的物品，与“选中比例≤9%”的约束完全相反，导致初始种群几乎全为违反约束的个体，进化缺乏可行解基础。

2. 约束与适应度函数重复计算，惩罚逻辑不合理

   • 适应度函数中重复执行约束检查，违反约束直接返回0，这种硬惩罚会导致大量个体适应度为0，选择压力不足，进化难以推进。
   • 仅用Constraint.of(Predicate)过滤不可行解，但初始种群几乎无可行个体，种群多样性和进化动力被严重限制。

3. 进化参数设置不合理

   • TournamentSelector<>(10000)的选择规模远大于种群大小（100），等同于全局选择，易引发早熟收敛。
   • 变异率过高（ShuffleMutator<>(0.7)、SwapMutator<>(0.3)），会破坏已有部分可行的解结构。
   • RouletteWheelSelector在大量低适应度个体存在时，选择效率极低。
   • 终止条件Limits.bySteadyFitness(200)过于严格，可能在种群尚未收敛到可行解时就停止进化。

优化方案与代码调整 #

1. 修正初始种群生成 #

将初始基因设为1的概率调整为接近约束上限的值（如0.08，留1%余量），让初始种群更接近可行域：

Factory<Genotype<BitGene>> genotypeFactory = Genotype.of(
    BitChromosome.of(objects.size(), 0.08)
);

2. 改用带修复逻辑的约束实现 #

通过Constraint.of(predicate, repairer)对违反约束的个体进行修复，确保种群始终存在可行解，以选中比例约束为例：

Constraint<BitGene, Long> constraint = Constraint.of(
    // 约束检查逻辑
    phenotype -> {
        Genotype<BitGene> genotype = phenotype.genotype();
        BitChromosome chromosome = genotype.chromosome().as(BitChromosome.class);
        int[] solution = chromosome.stream()
            .map(gene -> gene.bit() ? 1 : 0)
            .mapToInt(Integer::intValue)
            .toArray();

        for (int i = 0; i < constraintCoeffs.length; i++) {
            long sum = 0;
            for (int j = 0; j < solution.length; j++) {
                sum += constraintCoeffs[i][j] * solution[j];
            }
            if (sum > bounds[i]) {
                return false;
            }
        }
        return true;
    },
    // 约束修复逻辑
    phenotype -> {
        Genotype<BitGene> genotype = phenotype.genotype();
        BitChromosome chromosome = genotype.chromosome().as(BitChromosome.class);
        MutableBitChromosome mutable = chromosome.toMutable();
        
        // 处理选中比例约束（替换为对应约束的索引）
        int selectedCount = (int) mutable.stream().filter(Gene::bit).count();
        int maxAllowed = (int) Math.floor(bounds[0]); // 假设该约束是sum(x) ≤ bounds[0]
        
        if (selectedCount > maxAllowed) {
            // 随机关闭多余的选中基因
            List<Integer> selectedIndices = new ArrayList<>();
            for (int i = 0; i < mutable.length(); i++) {
                if (mutable.get(i).bit()) {
                    selectedIndices.add(i);
                }
            }
            Collections.shuffle(selectedIndices);
            for (int i = 0; i < selectedCount - maxAllowed; i++) {
                mutable.set(selectedIndices.get(i), false);
            }
        }

        // 可添加其他约束的修复逻辑
        return Phenotype.of(Genotype.of(mutable.toImmutable()), phenotype.generation());
    }
);

3. 简化适应度函数 #

移除适应度函数中的约束检查，仅计算目标值，避免重复计算：

private long fitness(Genotype<BitGene> genotype) {
    var bitChromosome = genotype.chromosome().as(BitChromosome.class);
    int[] variables = bitChromosome.stream().mapToInt(gene -> gene.bit() ? 1 : 0).toArray();
    var objects = dataModel.getObjects();

    double result = 0.0;
    for (int i = 0; i < objects.size(); i++) {
        result += objects.get(i).getValue() * variables[i];
    }
    long longResult = (long) (result * 100000000);
    return longResult * 30000;
}

4. 调整进化参数 #

优化选择器、变异率、种群规模和终止条件，提升进化效率：

Engine<BitGene, Long> engine = Engine.builder(this::fitness, genotypeFactory)
    .populationSize(500) // 增大种群规模，提升多样性
    .optimize(Optimize.MAXIMUM)
    .alterers(
        new UniformCrossover<>(0.5),
        new SwapMutator<>(0.1), // 降低变异率，避免破坏解结构
        new ShuffleMutator<>(0.1)
    )
    .offspringSelector(new TournamentSelector<>(3)) // 合理的锦标赛规模
    .survivorsSelector(new EliteSelector<>(10)) // 保留最优个体，避免优秀解丢失
    .constraint(constraint)
    .build();

// 组合终止条件，避免过早停止
Phenotype<BitGene, Long> best = engine.stream()
    .limit(Limits.byCombination(
        Limits.byGeneration(1000),
        Limits.bySteadyFitness(100)
    ))
    .collect(EvolutionResult.toBestPhenotype());

额外建议 #

• 对于大规模约束，可预先将约束分类（如线性和非线性、全局和局部），优先处理影响最大的约束，提升修复效率。
• 加入进化过程监控，打印每代的可行解比例、最优适应度等指标，便于调整参数。

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