简介

【资料图】

遗传算法 ( GA ) 指的是启发性算法 ( EA )，主要应用于其分析解法十分困难或甚至不可能的问题，它在大多数具有现实意义的情形中给出问题的可接受解决方案，但决策的正确性没有经过数学证明。

此类（NP 类）问题的一个经典例子是“旅行商问题”（最著名的组合优化问题之一）。该问题的主要挑战在于找出最有利的路线，通过给定的城市至少一次后回到出发城市。但不会影响把它们用于囿于形式化的任务。

EA 被广泛用于解决具有高度计算复杂性的问题，而不是一一尝试所有选项，这将耗费大量的时间。它们被应用于人工智能领域（如模式识别）、杀毒软件、工程、电脑游戏和其他领域。

值得一提的是，赫兹量化交易 在其软件产品中使用了 GA。我们都知道策略测试程序，也知道使用内置的策略优化程序可以节省大量的时间和精力，正如在其中使用直接枚举优化 GA 的应用是可能的。此外，MetaTrader 5 测试程序允许赫兹量化使用用户优化标准。可能读者会有兴趣阅读一些有关 GA 的文章，并对相比 直接枚举 EA 可提供哪些优势感兴趣。

1. 历史一瞥

就在一年前，我亟需一个优化算法用于训练神经网络。在快速地了解各种算法后，我选择了 GA。然而在搜索现成实施后，我发现对公众开放的算法要么就具有功能限制（如可优化的参数的数量），要么就是“可自己发挥的空间”太小。

我需要的是具有普适性的灵活工具，不仅可用于训练所有类型的神经网络，亦可用于任何优化问题的一般性求解。在对陌生的“遗传资料”长期研究后，我仍然无法理解它们是如何工作的。造成这种情况的原因可能是复杂的代码风格，或是我缺乏编程经验，或两者皆有之。

困难主要来自于将基因编码为二进制代码以及以这种形式使用它们。无论哪种方式，都需要从头开始编写遗传算法，将重点放在可量测性和未来易于修改上。

我不想进行二进制转换，并决定直接使用基因，即，以实数的形式通过基因组来表示染色体。这就是我使用实数表示染色体的遗传算法的代码问世的过程。后来我才知道，这并不是什么新的发现，类似的遗传算法（称为实数编码 GA）自从它们首次被发布出来已超过 15 年。

我把我探索 GA 功能的实施和原理的构想留待读者评定，因为这是基于它在实际问题中使用的个人经验。

2. GA 说明

GA 蕴含的原理借鉴于大自然本身。它们是遗传和变异的原理。遗传是生物将它们的生物特性和进化特征传递给后代的能力。由于这种能力，所有生物才能将它们的物种特性留给它们的后代。

生物的基因变异保证了种群的遗传多样性，并且变异是随机的，因为大自然无法提前得知哪些特征在未来是最合适的（气候变迁、食物的增加/减少、竞争物种的出现等）。变异使生物出现新的性状，从而能够在新的、变化的栖息条件下生存和留下后代。

在生物学中，由于突变引起的变异称为突变，而通过交配实现基因的进一步交叉组合所引起的变异称为组合。GA 中有这两种变异类型的实施。此外，还有突变的实施，模仿于突变的自然机制（DNA 的核苷酸序列发生变化）- 自然（自发）和人工（诱变）。

按照算法的准则，信息传递的最简单的单位是基因 - 遗传的结构和功能单位，控制特定的性状和属性的发展。我们将函数的一个变量称之为基因。基因通过实数来表示。基因组 - 所研究函数的变量是染色体的表征特征。

我们同意以列的形式表示染色体。则函数 f (x) = x ^ 2 的染色体将如下图所示：

图 1. 函数 f (x) = x ^ 2 的染色体

其中，第 0 个索引 - 函数 f (x) 的值，称为个体的适应度（我们将该函数称之为适应度函数 - FF ，将函数的值称之为 - VFF ）。染色体可方便地存储于一维数组中。即，double Chromosome [] 数组。

所有进化同代的样本组成一个种群。此外，种群将随意地分为两个相等的群体 - 上代群体和后代群体。执行上代物种（从整个种群中选出）的交叉以及 GA 的其他算子后，我们将得到一个新的后代群体，其规模为种群规模的一半，并将取代种群中的后代群体。

在搜索函数 f (x) = x ^ 2 最小值的期间全体个体种群可能如下图所示：

图 2. 全体个体种群

种群通过 VFF 存储。在这里，染色体的第 0 个索引被具有最小 VFF 的样本占据。新的后代完全取代后代群体中的个体，而上代群体保持不变。然而，上代群体不是始终保持完整的，因为重复的样本将被销毁，然后新的后代将填充上代群体中的空缺，剩余的则填充至后代群体中。

换言之，种群规模保持恒定的情况是很罕见的，因年代而变，这几乎和大自然是一样的。例如，在繁殖前后种群可能如下图所示：

图 3. 繁殖前种群

编辑切换为居中

图 4. 繁殖后种群

描述的通过后代“半”实现种群的机制以及销毁重复的染色体和禁止个体与自身杂交都只有一个目的 - 那就是避免“瓶颈效应”（生物学中的一个术语，意思是多种不同因素造成的临界减少所引起的种群基因库的缩减可导致物种的完全灭绝。GA 面临着不再出现唯一染色体、在某个局部最优解“卡住”的情形）。

3. UGAlib 函数的说明

算法 GA：

创建一个原型种群。基因在给定范围内随机生成。

确定每个个体的适应度，或换言之，VFF 的计算。

删除重复的染色体，准备繁殖种群。

隔离和保留参考染色体（具有最优的 VFF）。

UGA 算子（选择、交配、突变）。对于每次交配和突变，选择新的父母。准备种群的下一代。

将最优后代的基因与参考染色体的基因进行比对。如果最优后代的染色体优于参考染色体，则替换参考染色体。

针对指定数量的一代，从步骤 5 开始重复执行此过程，直到没有优于参考染色体的染色体出现。

标签：