共计 2732 个字符，预计需要花费 7 分钟才能阅读完成。
遗传算法能够做什么？
遗传算法是元启发式算法之一。它有与达尔文实践（1859 年发表）的天然演变类似的机制。如果你问我什么是元启发式算法，咱们最好谈谈启发式算法的区别。
启发式和元启发式都是优化的次要子畛域，它们都是用迭代办法寻找一组解的过程。启发式算法是一种部分搜寻办法，它只能解决特定的问题，不能用于狭义问题。而元启发式是一个全局搜寻解决方案，该办法能够用于一般性问题，然而遗传算法在许多问题中还是被视为黑盒。
那么，遗传算法能做什么呢? 和其余优化算法一样，它会依据指标函数、约束条件和初始解给咱们一组解。
最优部分解与最优全局解
遗传算法是如何工作的?
遗传算法有 5 个次要工作，直到找到最终的解决方案。它们如下。
- 初始化
- 适应度函数计算
- 抉择
- 穿插
- 渐变
定以咱们的问题
咱们将应用以下等式作为遗传算法的示例。它有 5 个变量和束缚，其中 X1、X2、X3、X4 和 X5 是非负整数且小于 10（0、1、2、4、5、6、7、8、9）。应用遗传算法，咱们将尝试找到 X1、X2、X3、X4 和 X5 的最优解。
将下面的方程转化为指标函数。遗传算法将尝试最小化以下函数以取得 X1、X2、X3、X4 和 X5 的解决方案。
因为指标函数中有 5 个变量，因而染色体将由 5 个基因组成，如下所示。
初始化
在初始化时，确定每一代的染色体数。在这种状况下，染色体的数量是 5。因而，每个染色体有 5 个基因，在整个种群中总共有 25 个基因。应用 0 到 9 之间的随机数生成基因。
在算法中：一条染色体由几个基因组成。一组染色体称为种群
下图是第一代的染色体。
适应度函数计算
它也被称为评估。在这一步中，评估先前初始化中的染色体。对于下面示例，应用以下的计算形式。
这是第一代种群中的第一个染色体。
将 X1、X2、X3、X4 和 X5 代入指标函数，失去 53。
适应度函数是 1 除以误差，其中误差为 (1 + f(x))。
上面公式中加 1 是为了防止零问题
这些步骤也实用于其余染色体。
抉择
轮盘赌法是遗传算法中的一种随机抉择办法。这就像赌场里的轮盘赌。它有一个固定点，并且轮子旋转直到轮子上的一个区域达到固定点的后面。
在遗传算法的背景下，具备较高适应度值的染色体将更有可能在轮盘赌中被选中。
首先，计算 5 条染色体的总适应度值。
总计 = 𝟎.𝟏𝟑𝟕𝟖
总计 = 0.0185 + 0.0400 + 0.0178 + 0.0181 + 0.0434而后，计算每个染色体的概率。下图是第一条染色体概率的样本计算（P1 = 0.1342）。
再次利用到所有的染色体：
计算概率后，对于轮盘赌办法，须要计算其累积概率。
计算累积概率后，要应用轮盘进行抉择，须要生成 5 个随机数 Uniform(0,1)，这些随机数决定了从抉择中剔除哪条染色体。
产生 5 个数字因为咱们有 5 条染色体
下图就是筛选和打消染色体的办法。首先，依据累积概率排列染色体，所抉择的染色体由随机数决定如下:
抉择后的新染色体如下所示。
穿插
在生物学中，穿插是指生殖的一个术语。两条染色体被随机抉择并通过数学运算进行匹配。在本例中应用单点穿插。
单点穿插意味着两个亲本的基因被一个穿插线替换
下图蕴含应用 Uniform(0,1)生成的随机数。抉择用于穿插的染色体数量是由穿插率 (Pc) 管制的，其中最小值为 0，最大值为 1。例如确定 Pc = 0.25，这意味着随机数目小于 0.25 的染色体将成为穿插中的亲本。
随机数对染色体。例如，R1 对 1 号染色体，R2 对 2 号染色体，以此类推
穿插的染色体是染色体 1，染色体 3 和染色体 5。这三条染色体的联合如下所示。
为了确定穿插线的地位，须要生成一个 1 到 n 之间的随机数，其中 n 是染色体 - 1 的长度。咱们生成了 1 到 4。
染色体 1 和染色体 3 之间的穿插 (称为 CO1) 如下所示。
1 号染色体和 5 号染色体之间的穿插 (称为 CO2) 如下所示。
3 号染色体和 5 号染色体(称为 CO3)
渐变
1 号染色体和 2 号染色体来自新的 2 号染色体和 4 号染色体。他们没有被选中进行穿插。而染色体 3、4 和 5 来自前代的穿插。
下图就是与“染色体抉择后应用穿插的后果”进行的比照。
渐变是咱们赋予任何基因新的价值的过程。在本例中应用随机渐变，渐变基因的数量由突变率决定(𝑃𝑚)。首先，计算一个种群中的基因数量。
基因总数 = 染色体 x 染色体中的基因数接下来，产生渐变的基因数量如下。
# 渐变的基因数 = 基因总数 x 𝑃𝑚因而，一个种群中的基因数量如下。
#genes = 5 x 6
#genes = 30渐变基因数(𝑃𝑚= 0.1)
#genes mutation = 30 x 0.1
#genes mutation = 3所以须要生成从 1 到 30 的随机数。随机数的后果是 7、19 和 23。它们是渐变基因的地位。接下来，对于每一个被选中的基因，生成一个从 0 到 9 的随机数来替换旧的值。
这些渐变后的新染色体是第二代
评估
对渐变后的染色体进行评估。
应用生成的新一代反复这个过程，就能够以取得 X1、X2、X3、X4 和 X5 的最佳解。通过几代后，失去的最佳染色体如下。
这个指标函数是有不同解的，所以咱们这里只给出一个。如果须要增加限度条件，能够批改指标函数。
代码
上面的 Jupyter Notebook 是下面咱们过程的代码实现：
https://www.overfit.cn/post/163b199a59154a058a3b4293f33b124b
援用
[1] M. Fronita, R. Gernowo, V. Gunawan. 2017. Comparison of Genetic Algorithm and Hill Climbing for Shortest Path Optimization Mapping. The 2nd International Conference on Energy, Environment and Information System (ICENIS 2017). August 15th — 16th 2017. Semarang (ID). pp: 1–5.
[2] N. Arfandi, Faizah. 2013. Implementation of genetic algorithm for student placement process of community development program in Universitas Gadjah Mada. Journal of Computer Science and Information. 6(2): 70–75.
[3] T. Suratno, N. Rarasati, Z. Gusmanely. 2019. Optimization of genetic algorithm for implementation designing and modelling in academic scheduling. Eksakta: Berkala Ilmiah Bidang MIPA. 20(1): 17–24.
作者：Audhi Aprilliant
