如何开发一个对等位基因总和有约束的遗传算法?

人工智能 遗传算法 基因编程 约束满足问题
2021-10-25 11:28:54

我正在研究一种对等位基因总和有约束的遗传算法,例如,如果我们使用常规二进制编码并且染色体是 5 位长,我想对其进行约束,以便位的总和必须是3 或更少(011100 有效,但 011110 无效)。此外,适应度函数无法评估无效染色体。

关于如何解决这个问题的任何想法?

我已经开始研究杂乱的 GA 的方向(因为这些可能被过度指定),但我不确定那里是否有任何东西。

1个回答

有多种方法可以处理“非法”个人,每种方法都有利有弊:

  • 中止方法:违反约束的个体一经发现(即交叉或突变后)就被淘汰,并产生新的个体以保持种群稳定。这通常意味着新世代的创建速度较慢,因为一些个体被丢弃。

  • 避孕方法:交叉和变异的编写方式使新生成的个体不可能违反任何约束。这种行动方式通常更有效,因为没有人被丢弃,但这可能是不可能的。

  • 惩罚函数:适应度函数对违反约束的个体(通常与其违反的约束成比例)给予巨大的惩罚。通过这种方式,它们通常无法繁殖,它们的基因最终会丢失。如果非法个人非常罕见并且他们不可能接管全部人口(导致算法失败),那么您会采用这种方式。

根据经验,尝试先作用于交叉算法(避孕方式),这是排除约束违规的最佳方式。如果这不可能,请选择其他两种方法之一,具体取决于产生非法个体的频率(不那么频繁 ->惩罚,非常常见 ->中止)以及惩罚违反约束的个体的难易程度(容易 ->惩罚,不容易 ->流产)。


处理您的示例的一种避孕方法是将交叉编写如下:

bool[] crossover(bool[] p1, bool[] p2)
{
    // classical binary crossover
    bool[] child = p2.copy()
    child[rndSection] = p1[rndSection]

    // contraceptive part
    while (CountTrue(child) > 3) child[RandomIndexOfTrue(child) = false

    return child
}

但这是一个相当复杂的问题,每个场景都有自己的规范。