带基因约束的遗传算法应用困境与技术咨询

我面临一个搜索空间呈指数级规模的问题，打算用遗传算法找近似最优解，但我在这个领域经验很少，而且问题有大量约束，不确定遗传算法是不是正确的选择（我对其他方法也了解有限）。

我已经基于Jenetics实现了一个能生成有效解的基础系统，但因为约束太多，生成的解适应度极差——大部分基因都是无效的。我标了Jenetics相关标签，但不局限于用这个库，只是目前它是我找到的最优选项。

基因结构（伪代码） #

class SomeGene {
  top: Chromosome;
  middle: Chromosome;
  bottom_left: Chromosome;
  bottom_right: Chromosome;
}

Chromosome有90多种可选值（从数据库获取），但基因必须满足以下约束才有效：

• 90种Chromosome里，只有8种能放在top位置，11种能放在middle位置等；如果top位置的Chromosome不属于这8种，整个基因无效（只有TOP类型的Chromosome能放top位置）。
• bottom_left和bottom_right可以放BOTTOM类型的Chromosome，二者值可以相同；但部分BOTTOM类型的Chromosome是唯一型（is_unique=true），如果一个基因里出现两次，整个基因无效。
• 有效基因的所有染色体属性（top、middle、bottom_left、bottom_right）都不能为null。

Chromosome结构（伪代码） #

class Chromosome {
  type: 'TOP' | 'BOTTOM' | 'MIDDLE';
  is_unique: boolean;
  max_attributes: int; // 最大属性数（0-5），由Chromosome决定
  attributes: List<Attribute> // 属性列表，长度始终等于max_attributes
}

Attribute结构（伪代码） #

class Attribute {
  type: 'A' | 'B' | 'C';
  value: number;
}

属性类型约12种，我现在为每种属性变体生成新的Chromosome：比如某个Chromosome的max_attributes为2，就生成所有属性组合的Chromosome（比如[A,A]、[A,B]等），属性可重复，顺序无关。部分Chromosome的属性还有额外筛选规则（比如max_attributes为5的Chromosome，前2个槽有12种选择，后3个槽选项更多）。

适应度函数需要基于整个Gene计算：汇总所有Chromosome的属性值，再通过复杂运算评估适应度。单个Chromosome无法单独评估，因为它的效果会受基因里其他Chromosome的影响。

我的问题 #

• 遗传算法适用于这个问题吗？
• 有没有更合适的遗传算法变体，比如基于语法的进化？我只是听过，不知道它和普通遗传算法的差异以及怎么实现。
• 有没有更好的问题拆分方式，能让突变和交叉操作更有效？现在getRandomChromosome()会返回任意Chromosome，Jenetics生成的基因绝大多数无效；两个高适应度基因交叉后，后代可能因为继承了两个TOP类型的Chromosome直接失效。

当前实现代码 #

运行模拟代码 #

public void run() {
    // 1.) Define a genotype (factory) suitable
    //     for the problem.
    // 4 chromosomes (one for each slot: top, middle, bottom_left, bottom_right)
    Factory<Genotype<AnyGene<Chromosome>>> gtf =
            Genotype.of(AnyChromosome.of(this::getRandomChromosome, 4));

    // 2.) Create the evaluation/fitness environment.
    Engine<AnyGene<Chromosome>, Float> engine = Engine
            .builder(this::fitness, gtf)
            .build();

    // 4.) Start the execution (evolution) and
    //     collect the best result found.
    Genotype<AnyGene<Chromosome>> best = engine.stream()
            .limit(100_000) // number of generations to run?
            .collect(EvolutionResult.toBestGenotype());

    // Print the details of the best result
    this.printBest(best);
}

随机生成Chromosome代码 #

private Chromosome getRandomChromosome() {
    Random random = new Random();

    // Fetch a random chromosome base (90 possibilities)
    ChromosomeBase base = this.bases.get(random.nextInt(this.bases.size()));
    List<Attribute> attached = new ArrayList<>();

    // Filter down from all possible attributes to only ones that make sense on this base
    List<Attribute> validForThisOne = this.all_attributes
        .stream().filter(x -> x.tier() % 2 == 0)
        .toList();

    // Insert a random assortment of valid attributes
    for (int i = 0; i < base.getMaxAttributes(); i++) {
        var attribute = validForThisOne.get(random.nextInt(validForThisOne.size()));
        attached.add(attribute);
    }

   // Return a chromosome that is valid by itself
   return new Chromosome(base.getId(), base.getType(), base.getMaxAttributes(), attached);
}

适应度函数代码 #

private float fitness(Genotype<AnyGene<Chromosome>> gt) {
    List<Chromosome> items = gt.chromosome()
            .stream()
            .map(AnyGene::allele)
            .toList();
    Map<Type, Chromosome> build = new HashMap<>();
    for (Chromosome chromo : items) {
        Type type = ChromoTypes.parse(chromo.type());
        if (build.containsKey(type)) {
            // This entire gene failed/died because it had duplicate types! ex: two top chromosomes!
            return 0;
        }
        build.put(chromo, item);
    }

    // If we end up with less than 4 chromosome types, then we are missing chromosomes, so this gene is also invalid
    if (build.size() < 4) {
        return 0;
    }

    // Calculate the finess for our gene, this will always return a positive value, the bigger the better
    float fitness = this.doABunchOfMath(build);
    return fitness;
}

1. 遗传算法是否适用？ #

适用，但当前实现没处理好约束，导致无效解占比过高，拖慢了进化效率。你的问题属于带约束的组合优化，遗传算法在这类问题上有成熟应用案例，只要调整编码和操作方式，就能有效筛选有效解。

2. 要不要用基于语法的进化（GBE）？ #

没必要。GBE主要适合语法结构复杂、需要动态生成程序或规则的问题（比如自动生成代码、逻辑规则），而你的问题是固定结构的组合优化（四个固定位置选对应类型的Chromosome），普通遗传算法调整后完全能应对，GBE反而会增加复杂度。

3. 优化突变和交叉的问题拆分方式 #

核心思路是让遗传操作天生就生成有效解，从根源减少无效基因，具体做法如下：

（1）重新设计基因型编码 #

不要用4个无差别的AnyGene<Chromosome>，而是给每个位置分配对应类型的基因：

• 第一个基因：只生成TOP类型的Chromosome
• 第二个基因：只生成MIDDLE类型的Chromosome
• 第三、四个基因：只生成BOTTOM类型的Chromosome

这样初始种群就不会出现位置类型不匹配的无效解，交叉时也不会把TOP类型的Chromosome换到middle位置。

在Jenetics里可以这样实现：

Factory<Genotype<AnyGene<Chromosome>>> gtf = Genotype.of(
    AnyChromosome.of(this::getRandomTopChromosome, 1),   // top位置，仅TOP类型
    AnyChromosome.of(this::getRandomMiddleChromosome, 1),// middle位置，仅MIDDLE类型
    AnyChromosome.of(this::getRandomBottomChromosome, 1),// bottom_left，仅BOTTOM类型
    AnyChromosome.of(this::getRandomBottomChromosome, 1) // bottom_right，仅BOTTOM类型
);

对应的随机生成方法也要拆分：

• getRandomTopChromosome()：只从8种TOP类型的Chromosome base里选，再生成对应属性
• getRandomMiddleChromosome()：只从11种MIDDLE类型里选
• getRandomBottomChromosome()：只从BOTTOM类型里选

（2）定制交叉操作 #

默认交叉可能导致两个BOTTOM唯一型Chromosome重复，需要自定义规则：

• 对于第三、四个基因（BOTTOM位置），交叉后检查是否有重复的唯一型Chromosome，如果有，就重新随机生成其中一个位置的Chromosome，或者回溯选择另一个交叉点。
• 或者交叉时优先保留父代中不重复的唯一型Chromosome组合。

（3）定制突变操作 #

突变时确保每个位置只突变成本位置允许的Chromosome类型：

• top位置突变时，只替换成另一个TOP类型的Chromosome
• bottom位置突变时，替换成BOTTOM类型，且如果原位置是唯一型，新的Chromosome不能和另一个bottom位置的唯一型重复

（4）优化适应度函数 #

当前给无效解返回0，会导致大量个体被直接淘汰，种群多样性下降。可以给无效解设置一个极低的非零适应度（比如0.001），既惩罚无效解，又不会让它们完全失去参与进化的机会（偶尔可能通过突变产生有效解）。

另外，当前适应度函数里的build.put(chromo, item)是笔误，应改成build.put(type, chromo)，否则无法正确检测重复类型。

（5）预生成所有有效Chromosome变体 #

提前把每个类型允许的Chromosome（包括所有属性组合）预生成并缓存，随机生成、突变时直接从对应类型的缓存里选，避免动态生成出错，也能提升效率。比如：

• 缓存List<Chromosome> topChromosomes：所有8种TOP类型的Chromosome及其属性组合
• 缓存List<Chromosome> middleChromosomes：所有11种MIDDLE类型的Chromosome及其属性组合
• 缓存List<Chromosome> bottomChromosomes：所有BOTTOM类型的Chromosome及其属性组合

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