python - 如何进行python列表元素组合的遗传进化？

Question

我是一名 Python 程序员，我必须模拟列表元素组合的遗传进化。思路如下:

li #initial list
combinations=get_combinations(li) #not all possible combinations
results=[]
for c in combinations: results.append(do_stuff(li)) #do_stuff returns percantage of accuracu

最后我有 2 个列表:combinations，它保留了 li 元素和 results 的一些组合，它保留了百分比每个组合的准确度值。我们的想法是选择具有最高准确度的组合。

检查 li 的所有组合是不可能的——这需要数月的计算。我必须从一些随机的(我猜？)开始，然后努力做到最好。我应该使用什么图书馆？如何在这里模拟进化？

编辑:

或者:元素集不断演化，直到它获得超过 k% 的准确度。

Answer 1

基本上有四种可能性:

1。探索所有组合

然而，随着组合数量呈指数级增长，这很棘手。

2。随机搜索

生成随机组合，直到获得足够好的组合。

3。本地搜索

从一些组合开始。然后对它做一个小改动。如果新的比当前的好，则将其设为当前的并重复该过程。

上述方法可以大大改进。最好的此类改进之一(根据我的经验)是 Simmulated Annealing

4。进化算法

使用模拟自然进化的算法。最基本的进化算法看起来像这样:

• 初始化一组候选解决方案。

• 直到不满足停止条件:

  1. 从总体中选择两个候选解决方案，其中更好的解决方案被选中的机会更高。
  2. (可选*)重新组合两个解决方案(以某种方式，取决于表示形式)，即将它们放在一起以创建新的解决方案。
  3. (可选*)略微更改(或变异)新解决方案。
  4. 将新的解决方案放回种群中，丢弃一些其他不够好的解决方案(以保持种群规模不变)。

• 必须存在重组或突变。通常，每个执行都有一定的概率。

挑战在于找到一个允许有效重组和突变的良好表示。