所以本质上你有一个数字 s 并且你想找到一个数字的子集加起来 s。这被描述为子集和问题,它是背包问题的一个特例。
我认为您对遗传算法应用的解释是错误的。为了可视化从 1000 个项目中选择 500 个项目必须考虑的可能解决方案的数量,请阅读以下数字 [“1000 超过 500”的二项式系数]:
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320
(来源)。
我先澄清一下:遗传算法和相关方法是元启发式的,这意味着它们不适合在很短的时间内找到最佳解决方案,而是一个“好”的解决方案。要在 NP 难题中找到最佳解决方案,您必须在最坏的情况下尝试所有可能的组合。有一些精确优化的方法可以智能地划分搜索空间并仅评估较少数量的解决方案,但仍可能需要数周时间才能得出最佳答案。
如果您需要找到这个精确的最佳值,我建议您寻找精确的方法,例如branch 和 bound。例如,您可以使用著名的CPLEX优化器将您的问题描述为整数程序。例如,查看TSP 的 ILP 公式,了解如何实现这一点并将其转化为您的问题。
如果您不需要找到确切的最优值,您可以在遗传算法中监控几件事以改进其输出:
- 使用足够大的人口规模并根据选择压力。你想避免遗传漂移的影响,仍然实现收敛。
- 监控总体中的方差(多样性)。是不是下降的很快?如果您的总体中的所有解决方案基本相同,则该算法已经收敛。一旦它收敛,你就需要重新启动它,或者引入新的遗传信息来恢复进化过程。
- 改变突变的强度。在搜索开始时翻转多个位,并在搜索结束时减少到仅翻转几个位。
- 使用多个交叉点(我假设您使用的是单点交叉)。对于这么长的字符串,您可能想要使用 10 个交叉点。