基于字符串编码染色体的遗传算法：救护车选址变异方案咨询

针对你这种必须恰好选择3个选址（染色体中恰好3位为1）的场景，普通的随机位翻转变异会破坏约束（导致1的数量变为2或4），因此需要采用能保持1的数量恒定的变异策略，以下是几种合适的方法：

1. 单点替换变异 #

这是最常用且简单的方案，步骤如下：

• 从当前染色体的3个为1的位置中随机挑选1个；
• 从剩余36个为0的位置中随机挑选1个；
• 将选中的1位改为0，选中的0位改为1。

比如针对候选解111000000000000000000000000000000000000，若选中第1位（1）和第15位（0），变异后得到011000000000000100000000000000000000000，仍保持3个1的约束，同时实现了选址的替换拓展。

2. 多点配对替换变异 #

如果需要更大幅度的搜索空间拓展，可以采用批量替换：

• 随机选择k个（k=1、2或3，k≤当前1的数量）为1的位置；
• 对应选择k个为0的位置；
• 将选中的k个1位改为0，k个0位改为1。

比如选2个1位（第1、2位）和2个0位（第20、25位），变异后候选解变为001000000000000000010000010000000000000，依然满足3个选址的限制。

3. 随机洗牌式变异 #

这种方法相当于对所有可选位置重新抽样，但基于当前解做局部调整：

• 先移除当前选中的3个位置中的随机1个；
• 从未选中的36个位置中随机选1个补充进去。

本质和单点替换变异逻辑一致，核心都是保持选中数量恒定。

需要注意的是，所有变异操作都要严格保证变异后染色体中1的数量始终为3，避免违反选址数量限制。

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