遗传算法(Genetic Algorithm)——基于Java实现
1。遗传算法原理简介
遗传算法是一种计算模型，可以模拟达尔文生物进化论的自然选择和遗传机制。这是一种通过模拟自然进化过程来搜索最佳解决方案的方法。遗传算法从代表潜在问题集的人群开始，人群由一定数量的基因编码的个体组成。每个人实际上都是具有特征的染色体。作为遗传物质的主要载体，即多个基因的收集，其内部表现（即基因型）是基因的某种组合，它决定了个体形状的外部表现，例如黑色的特征头发由染色体控制。特征的基因的某种组合。因此，有必要实现从表型到基因型的映射，一开始就编码工作。由于模仿基因编码的工作非常复杂，因此我们经常简化它。例如，二进制编码。生成第一代人口后，一代人将产生越来越更好的解决方案。在第一代中，根据问题领域中个体的适应性大小选择个体，并将交叉和突变与自然遗传学的遗传操作员相结合，以产生代表性的新溶液集群。该过程将导致比前几代更适合环境的人群，而最后人口中的最佳个体可以作为对问题的近似最佳解决方案进行解码。 [1]
简而言之，遗传算法是一种算法，它模拟了天然生物的进化过程，并通过连续反复试验，误差和筛选获得了最佳解决方案。
2。遗传算法的计算机表达
在介绍遗传算法的过程之前，本节将介绍如何以字符编码为例，在计算机语言中表达诸如人群和个人的生物学概念。
2.1个个体，染色体，基因
个体是具有由染色体组成的特定属性的实体。一般而言，为了简化这个概念，我们认为一个人是由染色体组成的，两者相互等同。因此，在以下文本中，个体和染色体被统一称为染色体。
从生物学知识中，我们可以看到染色体由独立的基因组成。为了在计算机中表达此概念，我们建立了一个一维数组来表示染色体，并且数组中的每个元素都代表一个基因。如图2.1所示：
图2.1染色体的计算机表达（字符编码）
图2.1的左侧是三个独立的染色体A，B和C，而内部的字符代表其位置的基因。在这里，我们使用伪 - 二十二十一章的字符编码方法来表达基因。字符值范围为1〜10，A〜f，A〜f分别表示11〜16。
注意：这不是一个真正的十六进制系统，而是一种伪 - 二十二十一章的表示方法，该方法设定了表达超过两位数的基因并促进理解。我们不使用塑料变量阵列的原因是由于习惯。
图2.1是右侧染色体的计算机表达。按从左到右的顺序，其基因存储在数组中。一般而言，为了易于计算和存储，我们认为所有染色体都是相同的长度，并且可以在程序中声明全局恒定长度染色体。
2.2人口
图2.2人群的计算机表达（字符编码）
从第1节中给出的定义，我们可以看到人口是个人的集合。因此，与使用一维阵列表达的染色体相比，我们使用二维阵列表达由多个染色体组成的种群，如图2.2的右侧所示。行号表示染色体数，列数表示染色体内的基因号。
注意：在2.1中以这种方式反映染色体长度固定的假设。由于染色体长度固定，因此我们很容易建立由二维阵列表达的种群。
2.3突变 - 基因重组，基因突变
在生物学概念中，突变包括基因重组，基因突变和染色体突变。由于基因突变和染色体突变与染色体突变的突变相似，因此为了简化算法，仅选择两种基因重组和基因突变进行表达。首先，解释基因重组和基因突变的重要性。
基因突变：基因突变是生物突变的基本来源kaiyun全站app登录入口，并为生物的进化提供了原材料。 [2]
基因重组：基因重组可以产生各种基因组合，其中一些包含适应某些环境变化的基因组合。因此，遗传重组是生物突变的来源之一，这是形成生物多样性的重要原因，并且对生物体的进化具有重要意义。 [2]
简而言之，基因突变确保人群可以拥有新的基因型，这是进化的基本保证。基因重组提供了改善人群中生物多样性的条件，并为人群进化提供了足够的试验和错误样本。
2.3.1基因重组 - 单点互换，基因转移（不是严格的名称，请不要等于生物学概念）2.3.1.1单点互换
单点交换意味着选择染色体中的任何两个不同位置进行交换，以实现互换位置的目的。示意图如下：
图2.3.1.1单点可互换的计算机表达式（字符编码）
从上图可以看出，染色体A的左第一和第五基因的第二个基因与左的第五基因具有单点交换，以获得染色体A'。在算法中，它反映在字符阵列A的第二个元素和第五元素的值。
2.3.1.2基因转移
显然，一个点易位只会改变两个基因的位置，这不会给染色体带来太大变化。当我们要求每个突变的染色体发生很大变化时，我们该怎么办？目前，我们可以使用基因转移。以染色体A为例，如图所示：
图2.3.1.2基因转移的计算机表达（字符编码）
如上图所示，我们随机选择染色体A中的任何基因，并将其插入除基因初始位置以外的原代染色体中的任何位置。这样，我们可以将基因序列的重大变化带到染色体上。
注意：根据应用程序方案和规则局限性kaiyun全站网页版登录，基因转移中涉及的基因数量可能是多个，例如，染色体A中的8和6基因同时插入染色体中的其他位置。但是，在某些情况下，基因转移带来的变化带给染色体基因序列接近单点掉期，这将在4.1应用程序示例中进行解释。
2.3.2基因突变
图2.3.2基因突变的计算机表达（字符编码）
在生物学概念中，基因突变的变化发生在遗传水平上会产生一个新的基因，这是自然种群突变的基本来源。在遗传算法中，由于基因通常具有特定的含义（任务，判断选择等），因此我们不可能产生不存在于已建立的基因值范围（1〜F）之外的基因。因此，在遗传算法中，基因突变仅在既定值范围内产生基因。如上图所示开元棋官方正版下载，由于基因中的突变，基因8变为基因1，该突变在计算机中反映为元素值的变化。
2.4健身
健身意味着在特定评估标准下各个组的索引值，并且在不同的应用环境中结果有所不同。该定义在此处简要介绍，并在4.1应用程序示例中给出一个示例。
2.5选择 - 轮盘方法
为了模拟自然界中“自然界成功和适得生产的生存”的选择过程，我们选择了轮盘赌方法进行仿真。
轮盘赌的本质是一种基于概率的选择算法，并且参与所选选择的个人的概率与其适应性呈正相关。假设染色体A，B和C的适应性分别为6、3和13，轮盘赌显示如下图。
图2.5-1轮盘图
在获得轮盘的概率分布后，我们可以通过概率积累创建一个线段，其值范围为[0，1）。如下图所示：
图2.5-2概率积累线性的示意图
在算法中，我们可以随机生成0〜1的随机数。如果随机数为0.15，则位于[0，0.27）区域，这意味着选择了染色体A。由于被选中的概率与染色体适应性成正比，因此，就统计规则而言，高健身的个体的选择概率更高，因此实现了优胜胜之年的生存目标。
2.6改进的选择方法 - 精英染色体
在遗传算法的实际应用中，由于轮盘的随机性较高，种群进化不是快速的。为了提高种群进化的速度，我们通过人为地保留更适应能力的染色体来加速这一过程，这些染色体称为精英染色体。示意图如下：
图2.6精英染色体的示意图
假设母体种群包含三个染色体：A，B和C。在筛选出精英染色体C后，原始种群突变，获得了新的a'，b'和c'。通过轮盘赌筛选了新的人群，以获得两个新的染色体，而精英染色体C形成后代种群。通过这种方法，可以确保保留每一代人口的最佳染色体，从而提高人口进化的速度。
3。遗传算法过程简介
图3遗传算法流程图
iv。申请示例
补充
参考：
[1]，百度百科全书
[2]生物学（强制性II），人民教育出版社
