我正在研究一种对等位基因总和有约束的遗传算法,例如,如果我们使用常规二进制编码并且染色体是 5 位长,我想对其进行约束,以便位的总和必须是3 或更少(011100 有效,但 011110 无效)。此外,适应度函数无法评估无效染色体。
关于如何解决这个问题的任何想法?
我已经开始研究杂乱的 GA 的方向(因为这些可能被过度指定),但我不确定那里是否有任何东西。
我正在研究一种对等位基因总和有约束的遗传算法,例如,如果我们使用常规二进制编码并且染色体是 5 位长,我想对其进行约束,以便位的总和必须是3 或更少(011100 有效,但 011110 无效)。此外,适应度函数无法评估无效染色体。
关于如何解决这个问题的任何想法?
我已经开始研究杂乱的 GA 的方向(因为这些可能被过度指定),但我不确定那里是否有任何东西。
有多种方法可以处理“非法”个人,每种方法都有利有弊:
中止方法:违反约束的个体一经发现(即交叉或突变后)就被淘汰,并产生新的个体以保持种群稳定。这通常意味着新世代的创建速度较慢,因为一些个体被丢弃。
避孕方法:交叉和变异的编写方式使新生成的个体不可能违反任何约束。这种行动方式通常更有效,因为没有人被丢弃,但这可能是不可能的。
惩罚函数:适应度函数对违反约束的个体(通常与其违反的约束成比例)给予巨大的惩罚。通过这种方式,它们通常无法繁殖,它们的基因最终会丢失。如果非法个人非常罕见并且他们不可能接管全部人口(导致算法失败),那么您会采用这种方式。
根据经验,尝试先作用于交叉算法(避孕方式),这是排除约束违规的最佳方式。如果这不可能,请选择其他两种方法之一,具体取决于产生非法个体的频率(不那么频繁 ->惩罚,非常常见 ->中止)以及惩罚违反约束的个体的难易程度(容易 ->惩罚,不容易 ->流产)。
处理您的示例的一种避孕方法是将交叉编写如下:
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
}
但这是一个相当复杂的问题,每个场景都有自己的规范。