如何通俗易懂地解释遗传算法？有什么例子？

acecase · 发表于 2021-7-4 05:51

XGundam05 · 发表于 2021-7-4 05:56

方弦在科学松鼠会上这篇写的就挺清楚：

这是个真实的故事。
从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一部分。当然啦，挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得比较不像Firefox图标的扇贝。
这种状况持续了好几十万代。大家应该也猜到扇贝们身上发生什么事情了：它们的贝壳上都印着很像Firefox图标的图案。
可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代的扇贝？
确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里边生活。它们是一个遗传算法程序的一部分，这个程序的目的就是用100个半透明三角形把Firefox的图标尽可能像地画出来。
什么是遗传算法呢？
简单地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。
在二十世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了，而他们也希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。
那么，具体来说，在计算机里边是怎么模拟进化过程的呢？
我们还是以开头提到的程序为例。
首先，我们知道，生物个体长什么样子很大程度上是由染色体上的基因决定的。同样，如果我们把100个半透明三角形组成的东西看成一个生物个体的话（为了说话方便，称为扇贝吧），我们也可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看作是这些扇贝的“基因”。而组成扇贝的这100个基因就组成了每个扇贝个体的“染色体”（chromosome）。
从下面的图可以大约看出来这些基因是怎么决定扇贝的样子的（为了观看方便，我们只画出其中五个三角形）：

然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然也这么办：选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。如图所示：（仍然是将扇贝看成是五个三角形组成的）

为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。也就是说，其中的一个透明三角形的位置或者颜色会随机改变，如图（仍然是五个三角形……我偷工减料……）：

其次，为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故事中提到的那个人的行动：在每一代把最不像Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像Firefox呢？最直接的方法就是一个一个像素比较，颜色相差得越多就越不像。这个评价的函数叫做“适应函数”，它负责评价一个个体到底有多适应我们的要求。
在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而达到选择的目的。
最后，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时候终止演化输出结果呢？这就要订立一个终止条件，满足这个条件的话程序就输出当前最好的结果并停止。最简单的终止条件就是，如果种群经过了很多代（这里的“很多”是一个需要设定的参数）之后仍然没有显着改变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。
好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好的）

怎么样？虽说细节上很欠缺，但是也算是不错了。要不，你来试试用100个透明三角形画一个更像的？就是这样的看上去很简单的模拟演化过程也能解决一些我们这些有智慧的人类也感到棘手的问题。
实际上，在生活和生产中，很多时候并不需要得到一个完美的答案；而很多问题如果要得到完美的答案的话，需要很大量的计算。所以，因为遗传算法能在相对较短的时间内给出一个足够好能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的研究也是方兴未艾。当然，它也有缺点，比如说早期的优势基因可能会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟（premature），也就是说整个种群的基因过早同一化，得不到足够好的结果。这个问题是难以完全避免的。
其实，通过微调参数和繁衍、变异、淘汰、终止的代码，我们有可能得到更有效的算法。遗传算法只是一个框架，里边具体内容可以根据实际问题进行调整，这也是它能在许多问题上派上用场的一个原因。像这样可以适应很多问题的算法还有模拟退火算法、粒子群算法、蚁群算法、禁忌搜索等等，统称为元启发式算法（Meta-heuristic algorithms）。
另外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有更广泛的群体遗传算法和遗传编程等，它们能解决很多棘手的问题。这也从一个侧面说明，我们不一定需要一个智能才能得到一个构造精巧的系统。
无论如何，如果我们要将遗传算法的发明归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。如果我们不知道自然演化的过程，我们也不可能在电脑中模拟它，更不用说将它应用于实际了。
向达尔文致敬！

ainatipen · 发表于 2021-7-4 06:03

大三的时候上了一门人工智能，其中有一次作业就用到了遗传算法，问题是这样的：
求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。
这个函数大概长这样：

那么如何应用遗传算法如何来找到这个奇怪的函数的最大值呢？
事实上，不管一个函数的形状多么奇怪，遗传算法都能在很短的时间内找到它在一个区间内的(近似)最大值。
相当神奇，不是吗？
接下来围绕这个问题，讲讲我对遗传算法的一些理解。实现代码以及在Matlab中使用遗传算法的小教程都附在最后。

1.介绍
遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
遗传算法模拟一个人工种群的进化过程，通过选择(Selection)、交叉(Crossover)以及变异(Mutation)等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到***近似最优***的状态。
自从遗传算法被提出以来，其得到了广泛的应用，特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域，遗传算法发挥了很大的作用，提高了一些问题求解的效率。

2.遗传算法组成

2.1 编码与解码
实现遗传算法的第一步就是明确对求解问题的编码和解码方式。
对于函数优化问题，一般有两种编码方式，各具优缺点

对于求解函数最大值问题，我选择的是二进制编码。
以我们的目标函数 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 为例。
假如设定求解的精度为小数点后4位，可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。
2^16<90000<2^17，需要17位二进制数来表示这些解。换句话说，一个解的编码就是一个17位的二进制串。
一开始，这些二进制串是随机生成的。
一个这样的二进制串代表一条染色体串，这里染色体串的长度为17。
对于任何一条这样的染色体chromosome，如何将它复原(解码)到[0,9]这个区间中的数值呢？
对于本问题，我们可以采用以下公式来解码：
x = 0 + decimal(chromosome)×(9-0)/(2^17-1)
decimal( ): 将二进制数转化为十进制数
一般化解码公式：
f(x), x∈[lower_bound, upper_bound]
x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)
lower_bound: 函数定义域的下限
upper_bound: 函数定义域的上限
chromosome_size: 染色体的长度
通过上述公式，我们就可以成功地将二进制染色体串解码成[0,9]区间中的十进制实数解。
2.2 个体与种群
『染色体』表达了某种特征，这种特征的载体，称为『个体』。
对于本次实验所要解决的一元函数最大值求解问题，个体可以用上一节构造的染色体表示，一个个体里有一条染色体。
许多这样的个体组成了一个种群，其含义是一个一维点集(x轴上[0,9]的线段)。
2.3 适应度函数
遗传算法中，一个个体(解)的好坏用适应度函数值来评价，在本问题中，f(x)就是适应度函数。
适应度函数值越大，解的质量越高。
适应度函数是遗传算法进化的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
2.4 遗传算子
我们希望有这样一个种群，它所包含的个体所对应的函数值都很接近于f(x)在[0,9]上的最大值，但是这个种群一开始可能不那么优秀，因为个体的染色体串是随机生成的。
如何让种群变得优秀呢？
不断的进化。
每一次进化都尽可能保留种群中的优秀个体，淘汰掉不理想的个体，并且在优秀个体之间进行染色体交叉，有些个体还可能出现变异。
种群的每一次进化，都会产生一个最优个体。种群所有世代的最优个体，可能就是函数f(x)最大值对应的定义域中的点。
如果种群无休止地进化，那总能找到最好的解。但实际上，我们的时间有限，通常在得到一个看上去不错的解时，便终止了进化。
对于给定的种群，如何赋予它进化的能力呢？

选择

交叉

变异

一般来说，交叉概率(cross_rate)比较大，变异概率(mutate_rate)极低。像求解函数最大值这类问题，我设置的交叉概率(cross_rate)是0.6，变异概率(mutate_rate)是0.01。
因为遗传算法相信2条优秀的父母染色体交叉更有可能产生优秀的后代，而变异的话产生优秀后代的可能性极低，不过也有存在可能一下就变异出非常优秀的后代。这也是符合自然界生物进化的特征的。

3.遗传算法流程
附上实现代码: genetic-algorithm
如果你觉得这个仓库对你有帮助，欢迎给她一个 star 或者 fork 一下！

测试结果

迭代次数与平均适应度关系曲线（横轴：迭代次数，纵轴：平均适应度）

有现成的工具可以直接使用遗传算法，比如 Matlab。
最后就再介绍一下如何在 Matlab 中使用遗传算法。
在 MATLAB 中使用 GA 工具
1. 打开 Optimization 工具，在 Solver 中选择 ga - genetic algorithm，在 Fitness function 中填入 @target
2. 在你的工程文件夹中新建 target.m，注意MATLAB的当前路径是你的工程文件夹所在路径
3. 在 target.m 中写下适应度函数，比如
function [ y ] = target(x)
y = -x-10*sin(5*x)-7*cos(4*x);
end
*MATLAB中的GA只求解函数的(近似)最小值，所以先要将目标函数取反。
4. 打开 Optimization 工具，输入变量个数(Number of variables) 和自变量定义域(Bounds) 的值，点击 Start，遗传算法就跑起来了。最终在输出框中可以看到函数的(近似)最小值，和达到这一程度的迭代次数(Current iteration)和最终自变量的值(Final point)
5. 在 Optimization - ga 工具中，有许多选项。通过这些选项，可以设置下列属性

Reference

yukamu · 发表于 2021-7-4 06:11

遗传算法是计算数学中用于解决最优化的搜索算法，也是最为经典的智能算法之一。日本新干线N700系列车“气动双翼”的独特空气动力造型车鼻就是遗传算法运算结果。

回答这个问题分三步

简介

遗传算法（Genetic Algorithm, GA）来源于进化论和群体遗传学，由美国的 Holland 教授于 1975 年在他的专著《自然界和人工系统的适应性》[1]中首先提出。遗传算法作为一种非确定性的拟自然算法，为复杂系统的优化提供了一种新思路，对于诸多NP-Hard问题，遗传算法都有不错的表现。相对于传统算法而言，遗传算法有以下突出优点[2,3]：
1. 可适用于灰箱甚至黑箱问题；
2. 搜索从群体出发，具有潜在的并行性；
3. 搜索使用评价函数（适应度函数）启发，过程简单；
4. 收敛性较强。
5. 具有可扩展性，容易与其他算法（粒子群、模拟退火等）结合。

遗传算法的不足[4]:
1. 算法参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验；
2. 遗传算法的本质是随机性搜索，不能保证所得解为全局最优解；
3.遗传算法常见的编码方法有二进制编码、Gray编码等。二进制编码比较常见，但是二进制编码容易产生汉明距离注1（Hamming Distance），可能会产生汉明悬崖注2(Hamming Cliff），Gray可以克服汉明悬崖的问题，但是往往由于实际问题的复杂度过大导致Gray编码难以精确地描述问题。
4.在处理具有多个最优解的多峰问题时容易陷入局部最小值而停止搜索，造成早熟问题，无法达到全局最优。
注1：将一个字符串变换成另外一个字符串所需要替换的字符个数
注2：相邻整数的二进制编码之间存在汉明距离，交叉和遗传难以跨越

经过多年的发展，遗传算法的研究热点及发展方向可以由图1进行展示[5]：
图1 遗传算法研究进展
Fig.1 Research progress of genetic algorithm

遗传算法的搜索核心是遗传算子的选择，因此对于遗传算法的研究，其中最常见的内容与方向是遗传算子，遗传算子的选择多样性也导致了算法表现的多样性，常见的选择方式如图2所示：
图2 遗传算子的研究
Fig.2 Research of genetic operators

遗传算法作为一种搜索算法，在诸多领域均有很好的表现[6]，如函数优化、组合优化、生产调度、自动控制、机器学习、图像处理、人工生命、遗传编程、机器学习、数据挖掘等。

为了更通俗地理解遗传算法，下面将通过一些实例进行描述：
如果想在一座连绵的大山上找到其最高点，正常情况下你需要爬遍整座山才可以找到最高峰，但大多数的智能算法并不需要搜索整个山峰，不同的智能算法有不同的求解思路，举几个简单例子：
1. 爬山算法（也称为贪心算法）。假设有一只猴子从山的任意一点出发，当它爬到第一个高峰值点的时候便停止前进，并认为当前的山峰为整座山最高的点。这种情况下，运气好可能会到达最高点，但是大概率情况下都不会是最高点。
2. 模拟退火算法。假设有一只神志不清的猴子，当它爬到山峰的时候，它有一定的概率继续出发，也有概率停止前进。这种情况下它也有可能通过有限的时间找到整座山的最高点。
3. 遗传算法。假设山上有一群猴子，猴子生存的食物只有在山峰处才有，而且山峰越高食物量越充裕。那么这些猴子为了生存，会不断聚集在各个山头上进行生存繁衍，而这些山峰可以理解为各种局部最优解（图3中类似绿色和蓝色的地方），如果种群规模足够大，势必会有一群猴子聚集在了整座山的最高点，也就是全局最优解（图3中红色位置）。
图3 山体示意图
Fig3 An outline of a mountain
基于以上三种算法的描述，我们可以对智能算法有一个简单的了解：无论是哪种算法，都具有一定的随机性，都不能保证最终选择的山峰为整座山的最高点。但是在实际生活中，有诸多类似的问题，如果要考虑所有的情况可能会花费大量的时间，而恰巧我们并不需要一个最好的结果，我们只需要快速找到一个相对较好的结果便可以满足要求的时候，智能算法的意义便得到了体现。
通俗了解后，虽然心里有大概思路，但还是云里雾里，这个时候我们可以考虑结合一些实际的例子来理解遗传算法。
3.1经典问题（0-1背包问题）

问题描述：假设一个你有一个可以装五公斤重的背包，现在地上有三块重金属A、B、C供你挑选，重量分别为1公斤、2公斤、3公斤，价值分别为1万元、5万元、10万元。为了使得总体收益最大，应该选择哪些金属块装入背包。
问题分析：这种规模的问题我们可以直观看出最优解为，选择B、C带走可以获得最大收益。但当问题规模扩大十倍百倍的时候，我们就必须要借助计算机来进行求解了。
下面分别以三种算法为例进行说明：
1. 爬山算法。初始点不确定，背包放不下就放手。
假设第一步选择A金属，有如下情况：A→B→C（保留AB），A→C→B（保留AC）；假设第一步选择B金属，有如下情况：B→A→C（保留BA），B→C→A（保留BC）；假设第一步选择C金属，有如下情况：C→A→B（保留CA），C→B→A（保留CB）；
可以看出，一共六种情况下，只有两种情况（选择BC）是可以得到最好结果的。侧面说明了爬山算法具有很大的不确定性。
2. 模拟退火算法。模拟退火与爬山最大的不同就是，每次拿到金属块的时候我们有一定的概率来决定是否将这块金属放入背包。我们假设这个概率为0.5（几乎所有的智能算法都需要提前设定初始参数，而不同的初始参数对求解结果及求解效率的影响非常大。）每次拿到金属块都有0.5的概率保留或者选择下一块，当执行足够多的次数后总能得到结果，结果虽然不一定是最好的，但整体随机性更大，当问题规模较大的时候更有可能选出最优解。
3. 种群遗传算法。初始随机产生100个15位2进制变量（每3位分别对应A、B、C，0为不取，1为取）。其中111为不可能的情况，设定这种基因片段不能繁衍下一代。
总生存力为五个基因片段之和，设定第一个位置出现1则生存力加0.01，第二个位置出现1则生存力加0.05，第三个位置出现1则生存力加0.1。则a为0；b1、b2和b3分别为0.1、0.05和0.01。c1、c2和c3分别为0.06、0.11和0.15。
生存力越高则生存率越高，依据轮盘赌选择策略（生成随机数，落在生存率区间选择相应的个体），选择遗传下一代的个体。
生存率=个体生存力/总生存力。
选择方法：随机生成6个0-1的数，根据落在哪里选对应的个体。
表1表2分别表示了种群的选择和遗传。

由于问题简单，规模较小，一次遗传之后便可以得出很明显的结果：种群中留有大量的011基因，即选择BC的结果。但是当问题规模扩大十倍百倍的时候往往需要多次迭代才会有明显的区分度。
另一方面，如果种群陷入了100与100的配对循环，那么这种情况下，永远不可能得出最好的情况011，这个时候需要对基因的某一段进行变异，将100变异为101或110，种群就会出现更优的基因型。但是在实际问题中变异不一定是向好的方向发展，也有可能会出现更坏的结果。
总的来说，遗传算法的选择充满了不确定性。但是当你设定无穷大的种群规模，足够长的繁衍时间后，最终总会达到最优，但是时间也会成倍上升。
图4 算法流程图
Fig.4 Flowchart of algorithm
适应度的概念在遗传算法中表示为个体趋近于最优解的程度，适应度越高遗传到下一代的概率就越大。上述的例子中，我们自己选择了适应度函数（生存力），在日常建模的时候，生存力函数可以是目标函数，也可以自己选择。在演化计算中，某些特殊算子的选择方式（例如这里的轮盘赌选择）要注意两点[7,8]：1.适应度必须非负;2.优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。
但在诸多大规模非凸非线性问题的求解时，上述观点不再适用。

结语：

虽然遗传算法有着一定的弊端和不足，但是遗传算法在诸多领域还是有着很不错的表现并已经运用到实际生活中。为了不断适应各种问题，近年来不断有学者提出改进策略，以使遗传算法有更广泛的应用领域。

参考文献：
[1] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. 2nd ed.Cambridge: MIT Press, 1992．
[2] 葛继科,邱玉辉,吴春明,蒲国林.遗传算法研究综述[J].计算机应用研究,2008(10):2911-2916.
[3] 雷德明.多维实数编码遗传算法[J].控制与决策,2000(02):239-241.
[4] 臧文科. DNA遗传算法的集成研究与应用[D].山东师范大学,2018.
[5] 马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(04):1201-1206+1210.
[6] 吉根林.遗传算法研究综述[J].计算机应用与软件,2004(02):69-73.
[7] Nix A E, Vose M D. Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics & Artificial Intelligence, 1992, 5(1):79-88.
[8]杨新武,杨丽军.基于交叉模型的改进遗传算法[J].控制与决策,2016,31(10):1837-1844.

该回答改编自『运筹OR帷幄』原创文章【优化】遗传算法介绍
原文作者：苏向阳，获得更多信息，欢迎阅读原文

APSchmidt · 发表于 2021-7-4 06:20

首先有一个种小东西，它们都生活在大草原上，跑的快的就不会被吃掉，就可以生存下来。

这个东西的一般是长这样的：
它由几个元素组成：

腿

圆圆的东西

肌肉

连接圆圈的粗线

时钟

是不是很复杂？
其实就可以想象一下：几个铁球被几根橡皮筋连接在一起，橡皮筋在有规律的抽动，然后这个东西随着抽动会向前跑。
所以然后我们的目标来了：什么样的这样的东西（几个球，几根皮筋，强度多少）可以跑的最快？
就是遗传算法发挥作用的时候到了。
第一步，第一批种子选手

遗传算法首先要有父本。也就是初始的一些这样的小东西。
一般来说要是我们知道一些知识，比如大概知道什么样子的东西可以跑的快的话，可以挑一些出来作为父本。
但是我们现在连这些东西怎么跑都不知道，怎么会知道哪个跑的快？
于是最粗暴的就是：随便来1000个！
100个随机生成的小东西。有三条腿的，也有四条五条六条七条的，肌肉也有多有少。然后我们看看他们跑的怎么样。
第一位选手：

怎么说呢，在一阵蠕动当中，一号选手竟然可以在15秒跑出差不多1米的距离。表现非常不错！
你以为这个不够快？
看看比如2号选手：

“请不要躺在地上”
还有其他选手

总体来说，因为是全部随机生成的选手，很多都只能留在原地，而且有一半选手选择了向后退而不是向前。
遗传算法第二步：生存

“适者生存”
第一代的父本，按照在15秒之内跑的距离排序。跑的慢的就会被淘汰掉。

但是，并不一定是所有跑的慢的都会大自然就一定会被淘汰掉。只是说，跑的快的更容易保留下来，跑的慢的更容易死掉。
大自然就是这么神奇，会允许一些幸运的弱者生存下来。说不定会在下一代表现出不一样的特点。
第一代的1000个，淘汰掉一半，剩下的才有资格作为下一代的父本，留下基因。下图黑色的代表被淘汰了。
遗传算法第三步：产生后代

就像两个黑头发生下来有大概率是黑头发，父母都1米9生下孩子大概率都也会很高。但是也会有两个父母都不聪明生的天才小孩。
遗传算法里也是一样，两个父亲（不要在意这些细节）结合产生的后代，有可能“腿”会不一样粗：
也很有可能“肌肉”会不一样强壮：
但是也会相对比较少见的：
腿不一样多。当然都是大自然的力量，和隔壁住了谁关系不大。
于是我们又有了下一代：上一代500个样本的孩子-->1000个新的样本。
遗传算法最后一步：迭代

我们已经有了完整的过程，

我们看一下这样的遗传算法，最终可以达到什么样子的效果

到第10代的时候，跑的最快的一个已经可以在15秒跑到快3米。跑起来是这个样子的

这个小东西有5条腿，已经可以稳定向前蠕动
到了第30代：

感觉已经要快飞起来了。还是5条腿。
30代的时候，跑的最快的一个已经可以在15秒内跑到6米，而中间值（千人马拉松第500名）也可以跑到3米。整个群体都在飞快的进步
这个图显示了进化中每一代跑的最快的（上边黑线）和群体中位数（红线）的成绩。
然后到了62代，一个有4条腿的家伙成为了新的冠军：

看来是进化的力量发挥了作用。有4条腿的族群中进化出现了一个非常利于跑步的结构：后边一条黑色腿，前边一条白色腿，中间两条相似的腿。
而且在整个群体中，4条腿6根肌肉的生物也占据了大部分，其他3条腿，5条腿的大多慢慢都被淘汰了。
结果

到了300代的时候，增长速度变得非常缓慢，停止模拟。
这一代里有个叫博尔特的跑的简直要飞起来了，我们欣赏一下：

大自然真是神奇~学到了么？

——————
关注我会有意想不到的事情发生
还有有喜欢的可以关注专栏/投稿/聊天
机械+数据工程师/职业发展/一起成长/
机械数据工程师的未来————————————————
最好可以点进去原文连接（包括原视频）：
https://zhuanlan.zhihu.com/p/35986593

super1 · 发表于 2021-7-4 06:25

澳洲国立大学计算机博士后 Vijini Mallawaarachchi 撰写了一篇遗传算法入门介绍，图文并茂，并在最后展示了如何用 Java 代码实现一个简单的遗传算法，相信对大家理解这种算法会有所帮助。以下编译自 Vijini Mallawaarachchi 的博文。
<hr/>遗传算法是一种启发式搜索法，其灵感源自达尔文的自然进化论。遗产算法的工作过程也体现了进化论中的“自然选择说”—— 选择最合适的个体进行繁殖，以生育下一代。该算法目前被广泛应用于机器学习、组合优化和智能计算中，同时也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。

自然选择的概念
自然选择的过程首先是从群体中选择最适合的个体。他们生育的后代继承了父母的特性，并将它们添加到下一代。如果父母有更好的适应性，他们的后代会比父母更好，而且有更好的生存几率。这个过程不断迭代，最后就会找到个体最合适的那一代。这就是进化论中的自然选择说。

而这个概念也可以应用到搜索问题。我们会为一个问题考虑多种解决方案，然后从中选择最好的那个。

通常认为遗传算法有5个阶段：

初始种群
遗传算法首先会选择一组个体，它们被称为一个“种群”。每个个体就是我们手头问题的一种解决方案。
个体的特点就是有一组参数（变量），叫做“基因”。这些“基因”会被加入到字符串中形成一个“染色体”（解决方案）。

在遗传算法中，使用字符串按照字母表表示出每个个体的一组基因。通常是使用二进制值进行编码（1和0组成的字符串）。我们是在“染色体”中对“基因”进行编码。

适应度函数
适应度函数用来决定一个个体的适应程度（和其它个体进行竞争的能力），它会评估每个个体的适应度得分。每个个体被选中用于繁殖的概率就是基于它的适应度分数。

选择运算
选择阶段的理念就是选出最适合的个体，让它们将基因传递给下一代。
这里会根据适应度得分选择两对个体（父体），适应度更高的个体会有更高的几率被选中用于繁殖。

交叉运算
交叉运算时遗传算法中最重要的阶段。对于每一对即将结合的父体，算法在基因中随机选择一个交叉点交换它们的某些基因，产生新的基因组合，期望将有益基因组合在一起。

例如，考虑一种交叉点为 3 的例子，如下所示：

交换父体中的基因来生成后代，直到达到交叉点。

图：在父体之间交换基因

然后将新生成的后代添加到种群中。

图：新的后代

变异运算
在形成的新后代中，它们的一些基因会以较低的随机概率出现变异，也就是说字符串中的一些比特会发生变动。

图：变异：之前和之后

发生变异是为了维护种群中的多样性，防止出现早熟收敛。

终止
如果种群出现了收敛（不再生成和之前几代有巨大差异的后代），遗传算法就会终止。那么我们就说遗传算法为问题提供了一组解决方案。

一些补充
种群有固定的大小。随着形成新一代，那些适应度最差的个体就会死亡，为新的后代腾出空间。
在每个生成的新一代中，会不断重复以上各个阶段。

遗传算法伪代码

遗传算法的伪代码可以写为：

起始
形成初始种群
计算适应度
重复
选择运算
交叉运算
变异运算
计算适应度
直到种群出现收敛
终止

用 Java 实现遗传算法
下面是用 Java 实现遗传算法的一个示例，可以自己也试着操作一遍。

给定一组 5 个基因，每个基因可以保存二进制值 0 和 1 其中一个值。
适应度的值计算为基因组中的 1 的数量，如果有 5 个 1，那么就认为适应度最高；如果有 0 个 1，就认为适应度最差。

遗传算法会试着将适应度函数最大化，提供一个包含最适合的个体（比如有 5 个 1 的个体）的种群。

注意：在这个例子中，经过交叉运算和变异运算之后，适应度最差的个体被新的适应度最高的后代所取代。

import java.util.Random;

/**
*
* @author Vijini
*/

//主类
public class SimpleDemoGA {

Population population = new Population();
Individual fittest;
Individual secondFittest;
int generationCount = 0;

public static void main(String[] args) {

      Random rn = new Random();

      SimpleDemoGA demo = new SimpleDemoGA();

      //初始化种群
      demo.population.initializePopulation(10);

      //计算每个个体的适应度
      demo.population.calculateFitness();

      System.out.println(&#34;Generation: &#34; + demo.generationCount + &#34; Fittest: &#34; + demo.population.fittest);

      //种群获得适应度最高的个体
      while (demo.population.fittest < 5) {
         ++demo.generationCount;

         //选择运算
         demo.selection();

         //交叉运算
         demo.crossover();

         //以随机概率进行变异
         if (rn.nextInt()%7 < 5) {
            demo.mutation();
         }

         //向种群添加适应度最高的后代
         demo.addFittestOffspring();

         //计算新的适应度值
         demo.population.calculateFitness();

         System.out.println(&#34;Generation: &#34; + demo.generationCount + &#34; Fittest: &#34; + demo.population.fittest);
      }

      System.out.println(&#34;\nSolution found in generation &#34; + demo.generationCount);
      System.out.println(&#34;Fitness: &#34;+demo.population.getFittest().fitness);
      System.out.print(&#34;Genes: &#34;);
      for (int i = 0; i < 5; i++) {
         System.out.print(demo.population.getFittest().genes);
      }

      System.out.println(&#34;&#34;);

}

//选择运算
void selection() {

      //选择适应度最高的个体
      fittest = population.getFittest();

      //选择适应度第二高的个体
      secondFittest = population.getSecondFittest();
}

//交叉运算
void crossover() {
      Random rn = new Random();

      //选择一个随机交叉点
      int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);

      //交换父体中的值
      for (int i = 0; i < crossOverPoint; i++) {
         int temp = fittest.genes;
         fittest.genes = secondFittest.genes;
         secondFittest.genes = temp;

      }

}

//变异运算
void mutation() {
      Random rn = new Random();

      //选择一个随机变异点
      int mutationPoint = rn.nextInt(population.individuals[0].geneLength);

      //在变异点改动值
      if (fittest.genes[mutationPoint] == 0) {
         fittest.genes[mutationPoint] = 1;
      } else {
         fittest.genes[mutationPoint] = 0;
      }

      mutationPoint = rn.nextInt(population.individuals[0].geneLength);

      if (secondFittest.genes[mutationPoint] == 0) {
         secondFittest.genes[mutationPoint] = 1;
      } else {
         secondFittest.genes[mutationPoint] = 0;
      }
}

//获取适应度最高的后代
Individual getFittestOffspring() {
      if (fittest.fitness > secondFittest.fitness) {
         return fittest;
      }
      return secondFittest;
}

//将适应度最差的个体替换为适应度最高的后代
void addFittestOffspring() {

      //更新后代的适应度值
      fittest.calcFitness();
      secondFittest.calcFitness();

      //获取适应度最差的个体的索引
      int leastFittestIndex = population.getLeastFittestIndex();

      //将适应度最差的个体替换为适应度最高的后代
      population.individuals[leastFittestIndex] = getFittestOffspring();
}

}

//个体类
class Individual {

int fitness = 0;
int[] genes = new int[5];
int geneLength = 5;

public Individual() {
      Random rn = new Random();

      //为每个个体随机设置基因
      for (int i = 0; i < genes.length; i++) {
         genes = Math.abs(rn.nextInt() % 2);
      }

      fitness = 0;
}

//计算适应度
public void calcFitness() {

      fitness = 0;
      for (int i = 0; i < 5; i++) {
         if (genes == 1) {
            ++fitness;
         }
      }
}

}

//种群类
class Population {

int popSize = 10;
Individual[] individuals = new Individual[10];
int fittest = 0;

//初始化种群
public void initializePopulation(int size) {
      for (int i = 0; i < individuals.length; i++) {
         individuals = new Individual();
      }
}

//获取适应度最高的个体
public Individual getFittest() {
      int maxFit = Integer.MIN_VALUE;
      int maxFitIndex = 0;
      for (int i = 0; i < individuals.length; i++) {
         if (maxFit <= individuals.fitness) {
            maxFit = individuals.fitness;
            maxFitIndex = i;
         }
      }
      fittest = individuals[maxFitIndex].fitness;
      return individuals[maxFitIndex];
}

//获取适应度第二高的个体
public Individual getSecondFittest() {
      int maxFit1 = 0;
      int maxFit2 = 0;
      for (int i = 0; i < individuals.length; i++) {
         if (individuals.fitness > individuals[maxFit1].fitness) {
            maxFit2 = maxFit1;
            maxFit1 = i;
         } else if (individuals.fitness > individuals[maxFit2].fitness) {
            maxFit2 = i;
         }
      }
      return individuals[maxFit2];
}

//获取适应度最差的个体的索引
public int getLeastFittestIndex() {
      int minFitVal = Integer.MAX_VALUE;
      int minFitIndex = 0;
      for (int i = 0; i < individuals.length; i++) {
         if (minFitVal >= individuals.fitness) {
            minFitVal = individuals.fitness;
            minFitIndex = i;
         }
      }
      return minFitIndex;
}

//计算每个个体的适应度
public void calculateFitness() {

      for (int i = 0; i < individuals.length; i++) {
         individuals.calcFitness();
      }
      getFittest();
}

}

如上图所示，最终算法在第32代中找到了最优方案。
<hr/>
参考资料：
https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

深度学习所需的基础理论 - 集智课堂

redhat9i · 发表于 2021-7-4 06:31

我想让机器人Bob画出我的梦中情人（最优解）。Bob当然不知道我梦中情人长啥样。
Bob很无奈，只能一张张试。先画一张，问我像不像？我说不像，Bob就重新画一张。直到我觉得像。
然而Bob又不会画画，只会填格子。于是Bob准备了一张1000*1000的格子纸，每个格子可以填黑色或者白色。那么总共有2^1000000种画法。如果我能坚持到宇宙毁灭N次，那可以每张都看，然后找到那个最像的。显然我没这个耐心。
于是我只让Bob画10万张，画不出来我就砸了它。
Bob很紧张，开始想办法，终于想到了遗传算法。
第一轮，Bob随机画了1万张（初始种群）。这1万张里面，肯定各种乱七八糟，有像星空的，像猪的，像石头的，等等。然后Bob让我挑最像的。妈蛋，我强忍怒火，挑出来一堆猪、猴、狗，好歹是哺乳动物。
Bob拿着我挑的“猪猴狗们”，如获至宝，开始第二轮，将这些画各种交叉变异一下。比如把一幅画的耳朵跟另一幅的鼻子换一下，或者再随机改个眼睛。然后又生成了1万张图让我挑。我挑出来一堆猴子猩猩，好歹是灵长类动物。
如此反复好多轮后，挑出来的开始像人了，虽然有男人、女人、小孩。
慢慢地，开始有美女了。再慢慢地，就越来越像了。
在画了10万张图后，终于找到一张还不错的。虽然不是梦中情人，但也很不错呐（次优解）。
这就是遗传算法。
— The End —
微信公众号：探长N次方
http://weixin.qq.com/r/5ElHXyrEFHdrrW489xz2 (二维码自动识别)

redhat9i · 发表于 2021-7-4 06:33

最近正好研究各种启发式算法，不妨来答一波～

大自然有种神奇的力量，它能够将优良的基因保留下来，从而进化出更加强大、更加适合生存的基因。遗传算法便基于达尔文的进化论，模拟了自然选择，物竞天择、适者生存，通过N代的遗传、变异、交叉、复制，进化出问题的最优解。遗传算法看似神奇，但实现思路却较为简单。本文先跟大家介绍遗传算法的基本思想，然后用遗传算法来解决一个实际问题，最后给出遗传算法的代码实现和解析。废话不多说，现在就开始吧～

遗传算法

在开始之前，我们先来了解下遗传算法中的几个概念。
概念1：基因和染色体

在遗传算法中，我们首先需要将要解决的问题映射成一个数学问题，也就是所谓的“数学建模”，那么这个问题的一个可行解即被称为一条“染色体”。一个可行解一般由多个元素构成，那么这每一个元素就被称为染色体上的一个“基因”。
比如说，对于如下函数而言，[1,2,3]、[1,3,2]、[3,2,1]均是这个函数的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均被称为染色体。

3x+4y+5z<100

这些可行解一共有三个元素构成，那么在遗传算法中，每个元素就被称为组成染色体的一个基因。
概念2：适应度函数

在自然界中，似乎存在着一个上帝，它能够选择出每一代中比较优良的个体，而淘汰一些环境适应度较差的个人。那么在遗传算法中，如何衡量染色体的优劣呢？这就是由适应度函数完成的。适应度函数在遗传算法中扮演者这个“上帝”的角色。
遗传算法在运行的过程中会进行N次迭代，每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分，来评判这些染色体的适应度，然后将适应度较低的染色体淘汰掉，只保留适应度较高的染色体，从而经过若干次迭代后染色体的质量将越来越优良。
概念3：交叉

遗传算法每一次迭代都会生成N条染色体，在遗传算法中，这每一次迭代就被称为一次“进化”。那么，每次进化新生成的染色体是如何而来的呢？——答案就是“交叉”，你可以把它理解为交配。
交叉的过程需要从上一代的染色体中寻找两条染色体，一条是爸爸，一条是妈妈。然后将这两条染色体的某一个位置切断，并拼接在一起，从而生成一条新的染色体。这条新染色体上即包含了一定数量的爸爸的基因，也包含了一定数量的妈妈的基因。
那么，如何从上一代染色体中选出爸爸和妈妈的基因呢？这不是随机选择的，一般是通过轮盘赌算法完成。
在每完成一次进化后，都要计算每一条染色体的适应度，然后采用如下公式计算每一条染色体的适应度概率。那么在进行交叉过程时，就需要根据这个概率来选择父母染色体。适应度比较大的染色体被选中的概率就越高。这也就是为什么遗传算法能保留优良基因的原因。

染色体i被选择的概率 = 染色体i的适应度 / 所有染色体的适应度之和

概念4：变异

交叉能保证每次进化留下优良的基因，但它仅仅是对原有的结果集进行选择，基因还是那么几个，只不过交换了他们的组合顺序。这只能保证经过N次进化后，计算结果更接近于局部最优解，而永远没办法达到全局最优解，为了解决这一个问题，我们需要引入变异。
变异很好理解。当我们通过交叉生成了一条新的染色体后，需要在新染色体上随机选择若干个基因，然后随机修改基因的值，从而给现有的染色体引入了新的基因，突破了当前搜索的限制，更有利于算法寻找到全局最优解。
概念5：复制

每次进化中，为了保留上一代优良的染色体，需要将上一代中适应度最高的几条染色体直接原封不动地复制给下一代。
假设每次进化都需生成N条染色体，那么每次进化中，通过交叉方式需要生成N-M条染色体，剩余的M条染色体通过复制上一代适应度最高的M条染色体而来。
遗传算法的流程

通过上述概念，相信遗传算法的大致原理你已经了解，下面我们将这些概念串联起来，介绍遗传算法的执行流程。

上面都是准备过程，下面正式进入“进化”过程。

到此为止，N条染色体生成完毕！紧接着分别计算N条染色体的适应度和下次被选中的概率。
这就是一次进化的过程，紧接着进行新一轮的进化。
究竟需要进化多少次？

每一次进化都会更优，因此理论上进化的次数越多越好，但在实际应用中往往会在结果精确度和执行效率之间寻找一个平衡点，一般有两种方式。
1. 限定进化次数

在一些实际应用中，可以事先统计出进化的次数。比如，你通过大量实验发现：不管输入的数据如何变化，算法在进化N次之后就能够得到最优解，那么你就可以将进化的次数设成N。
然而，实际情况往往没有那么理想，往往不同的输入会导致得到最优解时的迭代次数相差甚远，这是你可以考虑采用第二种方式。
2. 限定允许范围

如果算法要达到全局最优解可能要进过很多很多很多次的进化，这极大影响系统的性能。那么我们就可以在算法的精确度和系统效率之间寻找一个平衡点。我们可以事先设定一个可以接收的结果范围，当算法进行X次进化后，一旦发现了当前的结果已经在误差范围之内了，那么就终止算法。
但这种方式也有个缺点，有些情况下可能稍微进化几次就进入了误差允许范围，但有些情况下需要进化很多很多很多很多次才能进入误差允许范围。这种不确定性导致算法的执行效率不可控。
所以，究竟选择何种方式来控制算法的迭代次数，这需要你根据具体的业务场景合理地选择。这里无法给出普世的方式，需要你自己在真实的实践中找到答案。
采用遗传算法解决负载均衡调度问题

算法都是用来解决实际问题的，到此为止，我想你对遗传是算法已经有了个全面的认识，下面我们就用遗传算法来解决一个实际问题——负载均衡调度问题。

假设有N个任务，需要负载均衡器分配给M个服务器节点去处理。每个任务的任务长度、每台服务器节点(下面简称“节点”)的处理速度已知，请给出一种任务分配方式，使得所有任务的总处理时间最短。

数学建模

拿到这个问题后，我们首先需要将这个实际问题映射成遗传算法的数学模型。
任务长度矩阵（简称：任务矩阵）

我们将所有任务的任务长度用矩阵tasks表示，如：

Tasks={2,4,6,8}

那么，tasks中的i表示任务的编号，而tasks表示任务i的任务长度。
节点处理速度矩阵（简称：节点矩阵）

我们将所有服务器节点的处理速度用矩阵nodes表示，如：

Nodes={2,1}
那么，nodes[j]中的j表示节点的编号，而nodes[j]表示节点j的处理速度。
任务处理时间矩阵

当 任务矩阵Tasks和节点矩阵Nodes确定下来之后，那么所有任务分配给所有节点的任务处理时间都可以确定了，我们用矩阵timeMatrix表示，它是一个二维数组：

1 2
2 4
3 6
4 8
timeMatrix[j]表示将任务i分配给节点j处理所需的时间，它通过如下公式计算：

timeMatrix[j] = tasks/nodes[j]
染色体

通过上文我们知道，每次进化都会产生N条染色体，每一条染色体都是当前问题的一个可行解，可行解由多个元素构成，每个元素称为染色体的一个基因。下面我们就用一个染色体矩阵来记录算法每次进化过程中的可行解。
一条染色体的构成如下：

chromosome={1,2,3,4}
一条染色体就是一个一位数组，一位数组的下标表示任务的编号，数组的值表示节点的编号。那么chromosome=j的含义就是：将任务i分配给了节点j。
上面的例子中，任务集合为Tasks={2,4,6,8}，节点集合为Nodes={2,1}，那么染色体chromosome={3,2,1,0}的含义是：

将任务0分配给3号节点将任务1分配给2号节点将任务2分配给1号节点将任务3分配给0号节点

适应度矩阵

通过上文可知，在遗传算法中扮演者“上帝”角色的是适应度函数，它会评判每一条染色体的适应度，并保留适应度高的染色体、淘汰适应度差的染色体。那么在算法实现时，我们需要一个适应度矩阵，记录当前N条染色体的适应度，如下所示：

adaptability={0.6, 2, 3.2, 1.8}
adaptability数组的下标表示染色体的编号，而adaptability则表示编号为i的染色体的适应度。
在负载均衡调度这个实例中，我们将N个任务执行总时长作为适应度评判的标准。当所有任务分配完后，如果总时长较长，那么适应度就越差；而总时长越短，则适应度越高。
选择概率矩阵

通过上文可知，每次进化过程中，都需要根据适应度矩阵计算每一条染色体在下一次进化中被选择的概率，这个矩阵如下所示：

selectionProbability={0.1, 0.4, 0.2, 0.3}
矩阵的下标表示染色体的编号，而矩阵中的值表示该染色体对应的选择概率。其计算公式如下：

selectionProbability = adaptability / 适应度之和
遗传算法的实现

上述一切知识点铺垫完成之后，接下来我们就可以上代码了，相信Talk is cheap, show you the code!
/**
* 遗传算法
* @param iteratorNum 迭代次数
* @param chromosomeNum 染色体数量
*/
function gaSearch(iteratorNum, chromosomeNum) {
// 初始化第一代染色体
var chromosomeMatrix = createGeneration();

// 迭代繁衍
for (var itIndex=1; itIndex<iteratorNum; itIndex++) {
      // 计算上一代各条染色体的适应度
      calAdaptability(chromosomeMatrix);

      // 计算自然选择概率
      calSelectionProbability(adaptability);

      // 生成新一代染色体
      chromosomeMatrix = createGeneration(chromosomeMatrix);

}
}
代码一来，一切都清晰了，似乎不需要过多的解释了。上面是遗传算法最主要的框架，其中的一些细节封装在了一个个子函数中。在理解了遗传算法的原理后，我想代码不需要我作过多的解释了吧～完整的代码在我的Github上，欢迎Star。
结果展示

上述算法一共进行了100次进化，每次进化都会生成100条染色体。图中的横坐标表示进化次数，而纵坐标表示任务执行时间。从图中我们可以看到，当进化约20次的时候，算法渐渐收敛于最优解。
写在最后

完整的代码在我的Github上，欢迎下载，欢迎Star！
bz51/GeneticAlgorithm代码中包含三个文件：

ga.html：展示的页面GA.js：遗传算法的完整代码common.js：通用的JS代码

各位大佬直接打开ga.html即可查看算法执行结果。也欢迎各位关注我的个人公众号，不定期分享不正经程序员的心路历程。

RhinoFreak · 发表于 2021-7-4 06:37

遗传算法（Genetic Algorithm，GA）的算法思想来源于达尔文的进化论学说和Mendel的遗传理论，本质是模拟种群个体不断进化以逐渐适应环境的过程。遗传算法通过自然选择、交叉、变异等遗传操作模拟种群进化过程，使种群中个体的优良基因得以保留，提高个体的适应能力，进而不断增强对环境的适应能力。遗传算法是以染色体形式对问题的解进行描述，首先需要对问题的解进行编码，编码方式可以使用实数编码、二进制编码、符号编码。
在算法初始化时，首先随机产生一批初始种群，根据适应度函数公式计算种群中各个染色体的适应度值；进一步，按照适者生存、优胜劣汰的法则，选择种群中的个体进行复制、交叉、变异的遗传操作产生出子代染色体，个体适应度越大被选择进行遗传操作的概率越高，从而将种群中的优良基因进行保留同时适应度较差的个体将逐渐被淘汰；最后，进化多代后达到算法终止条件，算法收敛到某个对环境适应性最好的染色体上，这个染色体对应的编码也就是该问题的最优解。遗传算法的算法流程如图所示。
我们以麦当劳积分兑换商品为例，详细介绍一下遗传算法的原理。
假设我们现在有900的麦当劳积分，可以兑换下面这8种商品，每种商品对应售价不同，需要不同的积分，我们希望可以用900积分兑换尽可能贵的商品，该如何兑换呢？
由问题背景可知，该问题的适应度函数为商品总售价，总售价越大越好。
问题转化：设麦当劳积分兑换活动有N个商品，第i个商品的价值为vi元，兑换需要wi个积分，每个商品仅能兑换一次。我们总共有W个积分，我们希望用积分兑换的东西越值钱越好，到底应该怎么兑换呢？设xi表示第i件商品的兑换状态，1代表兑换，0代表不兑换，搜索空间为n元一维数组（x1,x2,x3,.....,xn）。因而解空间的取值范围可表示为（0，0，0，....，0），（0，0，0，......，1），（0，0，0，......，1，0），......，（1,1,1,1，......，1）。
以3个商品为例，解（0,1,0）表示（不兑换商品0，兑换商品1，不兑换商品2）。
目标函数：积分兑换的商品总价值z最大
约束条件：兑换商品所用的积分不大于拥有的总积分W；每个商品有兑换和不兑换两种状态，兑换则
，不兑换则
。

数学模型：

第一步：编码、产生初始种群，计算适应度函数
随机生成初始种群，种群中包含8个个体，每个个体上有8个基因位点，只有0或1两种取值，分别表示是否兑换该商品，进而可以计算出对应的适应度函数，也就是兑换商品的总价值，以及所需积分是否超过阈值，这里取积分最大不超过900，若所需积分超过900，则兑换不成功，适应度函数取值为0。

第二步：选择适应度最大的个体，进入下一代，个体被选中的概率可表示为：
计算累积概率，判断随机数落在哪个区间上，选择该个体进入下一代，重复8次，选择8个个体组成下一代新种群。

第三步：交叉变异，两两个体匹配，进行交叉判断，判断随机数是否小于交叉概率，如果是则进行交叉，否则不进行交叉，这里取交叉概率为0.7；

染色体交叉过程中，随机选了一段基因序列，将两个体中对应序列交换。

第四步：基因突变，在每个个体的每个基因位点进行判断，判断随机数是否小于突变概率（这里取0.1），如果是则原基因位点取值进行翻转，否则取值不变。

以上，即完成了一代进化，判断是否达到最大进化次数，如果是，输出当前最优解，否则，返回第一步，继续进化。
按照上述过程中，我们在matlab中进行求解积分兑换问题，在进行100次进化之后，其适应度函数变化趋势为：

当平均适应度接近最大适应度时，种群中每个个体的基因趋同，再没有进化的必要，可以认为算法收敛，本次求解完成。
由求解结果可知，我们在有900个积分的情况下，最多可兑换54.5元的商品，分别是：中杯可乐、中薯条1份、脆皮巧克力大圆筒、中热拿铁。

Arzie100 · 发表于 2021-7-4 06:46

http://alteredqualia.com/visualization/evolve/

我来补一个js实现，第一名也就是弹弹弹球已经说的很好了。

楼主可以简单看一下代码

		自动登录	找回密码
密码			立即注册

如何通俗易懂地解释遗传算法？有什么例子？

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源