创建我的第一个算法

Question

嘿，伙计们，又来了一个全新的项目。在我之前的文章中，我已经习惯了编程来做某些工作，这是很容易适应的，但是现在我想看看在编程中可以做些什么，做一些更有创造性的事情。

所以我会问一系列有关算法的问题。没有史酷比，他们是什么，或者如何写一个。但我感兴趣的是GA(遗传算法)。

我已经分解了我将要尝试实现的目标，但是我需要一个起点和一些编程(控制台c#)来让我走上我的道路，并以编程的方式思考。希望你喜欢阅读，并能帮助我的路上。

所有活的有机体都由细胞组成。每个细胞都有相同的染色体。染色体是DNA的字符串，是整个有机体的模型。染色体由基因和DNA块组成。每个基因都编码一种特定的蛋白质。基本上可以说，每个基因都编码一个特征，例如眼睛的颜色。一个特征的可能设置(例如蓝色，棕色)被称为等位基因。每个基因在染色体上都有自己的位置。这个位置叫做轨迹。

完整的遗传物质(所有的染色体)被称为基因组。基因组中特定的一组基因称为基因型。该基因型是随着出生后发育较晚的生物体表型，其生理和心理特征，如眼睛颜色、智力等。

基本遗传算法概述

1. Start产生n条染色体的随机群体(适合于problem)
2. Fitness的解)，评估population
3. New群体中每条染色体x的适应度f(x)，通过重复以下步骤创建一个新的群体，直到新群体完成1。选择根据群体的适应度从其群体中选择双亲染色体(适应度越好，被选择的机会越大)。2.具有交叉概率的交叉杂交，其父本之间存在交叉概率，形成一个新的后代(子女)。如果没有进行杂交，后代就是父母的精确复制品。3.具有突变概率的突变在每个位点(染色体位置)突变新后代。4.接受新种群中的新子代
4. Replace使用新生成的种群进一步运行algorithm
5. Test，如果满足结束条件，停止，并返回当前population
6. Loop中的最佳解决方案，转到步骤2

。

染色体编码

染色体在某种程度上应该包含关于它所代表的溶液的信息。最常用的编码方式是二进制字符串。染色体看起来可能是这样的：

Chromosome 1    1101100100110110
Chromosome 2    1101111000011110

每条染色体都有一条二进制串。这个字符串中的每一个位都可以表示解决方案的一些特性。或者整个字符串可以表示一个数字--这已经在基本的GA中使用了。

当然，还有许多其他的编码方式。这主要取决于已解决的问题。例如，可以直接对整数或实数进行编码，有时对某些排列进行编码很有用，等等。

交叉

在我们决定了我们将使用什么样的编码之后，我们可以跨出一步。杂交从父母染色体中选择基因，并创造一个新的后代。如何做到这一点最简单的方法是随机选择一些交叉点和在此点之前的所有内容，从第一个父节点复制，然后从第二个父节点复制到交叉点后的所有内容。

然后，交叉可以是这样的(交叉点是连的)：

Chromosome 1    11011 | 00100110110
Chromosome 2    11011 | 11000011110
Offspring 1     11011 | 11000011110
Offspring 2     11011 | 00100110110

还有其他方法来进行交叉，例如，我们可以选择更多的交叉点。交叉可能相当复杂，非常依赖于染色体编码的编码。针对特定问题进行特定交叉可以提高遗传算法的性能。

突变

在进行交叉之后，就会发生变异。这是为了防止将人口中的所有解降到已解决问题的局部最优状态。突变会随机改变新的后代。对于二进制编码，我们可以将一些随机选择的比特从1切换到0或从0切换到1。

Original offspring 1    1101111000011110
Original offspring 2    1101100100110110
Mutated offspring 1     1100111000011110
Mutated offspring 2     1101101100110110

变异取决于编码和交叉。例如，当我们编码排列时，突变可能是交换两个基因。

Answer 1

看看你的解释。

基本遗传算法概述

1. Start产生n条染色体的随机群体(适合于problem)
2. Fitness的解)，评估population
3. New群体中每条染色体x的适应度f(x)，通过重复以下步骤创建一个新的群体，直到新群体完成为止，根据它们的适应度从一个群体中选择两个双亲染色体(适应性越好，就越有可能成为具有交叉概率的selected)
4. Crossover，从而形成一个新的后代(子女)。如果没有进行杂交，后代是parents.
5. Mutation的一个精确副本，突变概率在每个位点突变新后代(在chromosome).
6. Accepting中的位置在新的population

中放置新的后代)。

1. Replace使用新生成的填充来进一步运行algorithm
2. Test，如果满足结束条件，停止并返回当前population
3. Loop中的最佳解决方案，转到步骤2

看起来已经很像一个程序了。如果你把它转换成代码，你应该占95%左右。您所缺少的是您的“健身功能”，它基本上是解决方案的运行+成功的标准。每个问题的情况各不相同，所以我们对此无能为力。但是它所做的更多的是使用染色体的比特作为标志或操作码，这取决于问题的复杂性，并观察染色体(即当前比特/字节/标志/操作码/任何东西的组合)是否和有多快地解决了问题。