这是什么？

Evolve是一个可定制的进化算法引擎，具有以下特性

• [x] 表型无关.这是什么意思？好吧，由于我至今为止并不知道这到底是怎么来的。简单来说，该引擎不知道或关心你的生物是什么，它们如何行为，它们的环境是什么，或者是它们的基因组如何影响表型。
• [x] 可定制的基因组.你可能希望你的基因组表示一种颜色值，所以你可以选择将基因域定义为所有十六进制字符 0123456789ABCDEF，并将其长度设置为 6，这样你可以轻松地将基因序列 FF0000 翻译为红色。你可能希望你的域为二进制字符串，01，长度 6，如 110100，其中前两位表示生物的速度，接下来两位表示生物的强度，最后两位表示它们的伪装程度。你定义基因是什么以及如何在野外表现，可能性是无限的。发挥你的创意！
• [x] 从一代到另一代保持一股恒定的人口规模。
• [x] 锦标赛式选择。
• [x] 单点或双点交叉。
• [x] 统一变异。
• [x] 可调整的模拟参数。玩弄一些可设置的变量，看看它们如何影响模拟。调整旋钮，做出预测并在实时中测试你的假设！
• [x] 灵活的模拟机制。该引擎不会在需要时继续进行下一代的操作，它会等你告诉它继续。正因为如此，你可以将模拟运行在数千代的循环中几乎瞬间完成，或者你可以将你的种群中的每种生物放入类似SpriteKit的实时交互式模拟中，使每一代可能需要分钟，甚至小时，如果那是你感兴趣的。
• 考虑到所有这些，我确实不知道可以创建什么或者将会创建什么，这正是它如此酷的原因。

示例模拟流程

1. 使用以下任一方法创建一个 种群 的 生物
   • 随机 - 创建一个随机的 Population，定义 Organisms 的数量以及它们的 Genome 特征，然后引擎会为您创建初始的 Population。
   • 初始化 - 为您的初始Population创建单个 Organisms，并定义它们的 Genome 特征。
2. 创建一个 EvolutionManager 实例来处理底层模拟，并设置您的适当 delegate 以符合 <EvolutionDelegate> 协议。 (目前需要实现一个方法。)
3. 将您的 EvolutionManager 分配给您刚刚创建的 Population。
4. 评估 Population 中每个 Organism 的适应性。
5. 告诉您的 EvolutionManager 进行选择和繁殖过程。
6. 当 EvolutionManager 完成选择过程后，它将回传给您刚刚处理的一代的信息，以及为下一代更新后的 Population。
7. 如果您想继续模拟，请从步骤 #4 重新开始。

安装

可通过 CocoaPods 获取。

pod ‘Evolve’

一个经典示例： Weasel 程序

理查德·道金斯曾指出：“我不知道是谁首先指出，给定足够的时间，一个在打字机上随机敲打的老猴可以创作出莎士比亚的所有作品。至关重要的词是，当然，足够的时间。让我们适度地限制猴子面临的任务。假设他需要创作，不是莎士比亚的全部作品，只是短句“我想它像一台蜥蜴”，我们将通过给他一台限制键盘打字机来简化任务，即仅包含26个（大写）字母和一个空格键。他将花费多长时间写出这个短短的句子？”

*请查看包含的演示程序，以了解此实现的完整细节。

初始化Population

EvolutionManager 负责所有模拟机制，并使用初始 Population 对象初始化。一个 Population 可以使用一组 Organism 对象进行初始化，或者，在例如这个示例中，根据特定参数随机生成。

• size 是任何一代中存活的生物体数量，在整个模拟过程中保持恒定。
• geneSequenceLength 是每个生物体基因序列的长度，或称为 染色体，用一个 NSString 表示。
• genomeDomain 是一个表示组织基因序列中可以使用的所有可能字符的 NSString。

示例：如果您想将生物体的遗传代码表示为一个5位二进制字符串，您应该将域设置为 @"01"，并将长度设置为 5。从这种类型的生物体中随机生成的基因序列可能看起来像 01001 或 11100。

在这个例子中，我们创建了一个包含50个生物体、基因序列长度与目标字符串 METHINKS IT IS LIKE A WEASEL 长度相等的Population，域包括所有26个大写字母以及空格字符。然后我们使用这个Population创建我们的进化管理器，并将自己设置为代理，保证我们符合 <EvolutionDelegate> 协议。

static NSString * const kTargetString = @"METHINKS IT IS LIKE A WEASEL";
static NSString * const kTargetDomain = @"ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

Population *startingPopulation = [[Population alloc] initRandomPopulationWithSize:50 geneSequenceLength:kTargetString.length genomeDomain:kTargetDomain];

self.evolutionManager = [[EvolutionManager alloc] initWithPopulation:startingPopulation];
self.evolutionManager.delegate = self;

适应性

初代种群创建完成后，接下来的步骤是评估每个生物的 适应性。对于这款引擎，它最终对生物的表型和环境都是中立的，确定每个生物每代的适应性工作应由实现者来完成。

在Weasel程序的情况下，每个生物的适应性简化为匹配目标字符串相应位置字符的数量

可以这样实现

- (void)evaluateFitnessForPopulation {
    NSArray *organisms = self.evolutionManager.population.organisms;

    for (Organism *organism in organisms) {
        NSString *genomeString = organism.genome.sequence;
        NSInteger geneSequenceLength = genomeString.length;
        NSInteger correctCharacters = 0;

        for (NSInteger charIndex = 0; charIndex < geneSequenceLength; charIndex++) {
            if ([genomeString characterAtIndex:charIndex] == [kTargetString characterAtIndex:charIndex]) {
                correctCharacters++;
            }
        }

        organism.fitness = correctCharacters;
    }
}

选择

选择是选择生物进行下一代繁殖的过程。一般来说，适应性越高的生物越有可能被选中。一旦确定了种群中所有生物的适应性，就可以开始选择过程，如下所示

[self.evolutionManager proceedWithSelectionAndBreeding];

这个算法使用锦标赛选择方法来选择繁殖的生物。从种群中随机选取几个子集来竞争繁殖的机会，这个子集中的最适应生物被选为父母。这些“获胜者”不会被从竞争对手中移除，因此一个生物可以成为多个后代的父母。

每个锦标赛的大小可以通过在EvolutionManager上设置tournamentSize属性来自定义。在这里尝试不同的值，看看这对你的种群有何影响。锦标赛大小为1相当于随机选择，这可能导致整个种群的适应性在代际间缓慢改善，因为适应性较好的生物在 Auswahl过程中没有优先权，而较高的锦标赛大小会增加最适应生物的交配机会，从而减少适应性较弱的生物的交配机会，导致多样性减少，并可能导致过早收敛。

除了父母选择过程之外，根据每个个体的适应性对种群进行排序，并选择一些最适应的生物以不变的状态进入下一代。这个过程被称为保留精英。通过在EvolutionManager上设置elitismPercentage属性，您可以自定义从当前代幸存进入下一代的生物百分比。该属性可以设置任何介于0.0（包含）到1.0（不包含）之间的CGFloat值，表示总数为n的种群中通过到代数n + 1幸存的百分比。

示例：如果您有100个生物的种群，并将elitismPercentage设置为0.1，这将导致0代中有10个生物被包含在1代的种群中，同时为90个后代腾出空间，从而使种群保持100个生物的恒定大小。如果没有设置elitismPercentage值，则默认值为0.10，这将导致大约10%的种群被选中并继续生活在下一代。这保证了整体种群适应性的某些水平保护，但如果设置得太高，可能会导致过早收敛。

交叉和变异

本算法模拟了有性繁殖，与无性繁殖相反，意味着后代总是来自两个不同的父母，结果的孩子具有与两个父母相同的遗传特征，这意味着基因组的长度和域保持不变。当从池中选取两个父母时，它们的基因通过交换（交叉）或两点交叉技术进行组合。单点交叉会在基因序列的1和length - 2之间随机选择一个索引，两个基因组都会复制，在这个索引上“分割”，并重新组合以形成孩子的遗传代码。这个索引的范围确保至少有一个基因来自每个父母进入子代的初始基因组。两点交叉会产生与上述相同的随机范围，并从这个范围内生成一个“切片”，其中一个父母贡献范围之前和之后的基因，另一个父母贡献范围本身的基因。

单点示例：考虑一个定义的域@"AB"，第一个父母的基因序列为AAAAA，第二个的为BBBBB。如果随机选择的索引是2，第一个父母的贡献是AA，第二父母的贡献是BBB，因此孩子的遗传序列将是AABBB。

两点示例考虑一个定义的域@"ABCD1234"，第一个父母的基因序列为AABBCCDD，第二个的为11223344。如果随机生成的范围是(2,3)，则该范围将用于从第二父母的基因中选取223，以及从第一个父母的基因中选择AA和CDD，因此孩子的遗传序列将是AA223CDD。

交叉过程完成后，后代遗传序列中的每个基因都有机会发生变异。该算法利用了均匀变异策略，即如果基因偶然发生变异，它会以等概率变异为基因组定义域中的任何字符，不包括当前字符，并且每种变异的概率相同。

示例：如果域定义为@"1234"，并在序列中的某个点的基因是1，那么该基因有等概率（1/3）变异成2、3或4。 注意： 这不要与下面的mutationRate相混淆！这不是说每个基因有1/3的概率变异成另一个，而是如果基因发生变异，它有1 / (n - 1)的概率结束成为域中任何其他基因，其中n是基因组域的长度。

某个基因变异的概率由EvolutionManager的mutationRate属性确定。该属性可以分配任何大于0.0且小于1.0的CGFloat值。如果突变率太高，你会增加总体遗传的随机性——使得任何有利的遗传特征的保留不太可能。突变率太低，你不会引入足够多的多样性到种群中，会导致停滞。试着调整这个数字以获得有趣的结果！如果没有设置mutationRate值，则使用默认值0.05。

示例：以0.05（5%）的mutationRate和长度为5的基因组域，任何给定基因发生变异的概率为5%，而一个有机体基因组中的每个基因都发生变异的概率为0.00003125%（5% * 5% * 5% * 5% * 5%）。

终止条件

在选择和生成后代后，EvolutionManager调用了其所需的委托方法evolutionManager:didCompetedGeneration:fittestOrganism:offspring:nextGeneration:，提供了关于上一代结果以及下一代的更新生物体的详细信息。您可以使用这些信息进行调试、日志记录、更新UI等。

nextGeneration参数正好代表这一点，即您的种群中整个下一代的个体，包括后代和精英。要继续通过另一代进行模拟，首先重新评估新种群的健康状态，然后再次调用proceedWithSelectionAndBreeding。如果您确定不想继续模拟，因为达到了某些最大健康状态，您的种群已经停滞等，请简单地不要再次调用proceedWithSelectionAndBreeding。

社区

• 如果您想贡献力量，请发起一个拉取请求。请尽量保持风格/格式与当前项目一致，并确保添加测试！

• 如果您有问题、功能请求等，我更希望您创建一个问题而不是直接发邮件给我。

许可证

本项目采用MIT许可证。请参阅LICENSE.txt以获取详细信息。