07-遗传算法面临的挑战

5.6　遗传算法面临的挑战

遗传算法无法包治百病，其实它对大多数问题都不适用。对于所有存在快速而确定性算法的问题，遗传算法都没有意义。固有的随机性使遗传算法的运行时间变得不可预测。为了解决这个问题，可以在经过几代之后停止算法的运行，但这时我们并不清楚是否找到了真正的最优解。

Steven Skiena写的书是最受欢迎的算法教材之一，他甚至如此写道：“在我看来，我从没遇到过任何问题是适合用遗传算法去攻克的。此外，我从未见过能给我留下深刻印象的用遗传算法完成的计算成果的报道。”^[4]

Skiena的观点有点儿极端，但这表明仅在有理由相信没有更好的解决方案时，才应该选择遗传算法。遗传算法还有一个问题，就是确定如何将某个问题可能存在的解表示为染色体。传统做法是将大多数问题都表示成二进制串（1和0的序列，即二进制位）。通常在空间利用率方面这是最佳方案，并且它有助于简化交换函数，但是大多数复杂的问题要被表示为可被整齐分割的位串并不容易。

另一个更具体的问题也值得一提，就是与本章所述的轮盘式选择法相关的挑战。轮盘式选择法有时也称为适应度比例选择法，由于每次进行选择时适应度较高的个体占据了优势，因此可能会导致种群缺乏多样性。另外，如果适应度值比较接近，轮盘式选择法会导致选择压力不足^[5]。此外，本章构建的轮盘式选择法不适用于适应度可为负数的问题，正如5.3节中简单的算式例子所示。

简而言之，对于大多数规模庞大到有理由采用遗传算法的问题，该算法均不能保证在可预测的时间内发现最优解。出于这个原因，遗传算法最适用于不需要最优解的情况，在这种情况下只需要“足够好”的解即可。遗传算法实现起来相当容易，但对其可配置的参数进行调优可能要经历很长的试错过程。