遗传算法流程

Ⅰ Python实现基于遗传算法的排课优化

排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（Timetable Problem，TTP）。设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有 种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火，列表寻优搜索和约束满意等。

Github ： https://github.com/xiaochus/GeneticClassSchele

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的流程如下所示：

遗传算法首先针对待解决问题随机生成一组解，我们称之为种群（Population）。种群中的每个个体都是问题的解，在优化的过程中，算法会计算整个种群的成本函数，从而得到一个与种群相关的适应度的序列。如下图所示：

为了得到新的下一代种群，首先根据适应度对种群进行排序，从中挑选出最优的几个个体加入下一代种群，这一个过程也被称为精英选拔。新种群余下的部分通过对选拔出来的精英个体进行修改得到。

对种群进行修改的方法参考了生物DAN进化的方法，一般使用两种方法： 变异 和 交叉 。 变异 的做法是对种群做一个微小的、随机的改变。如果解的编码方式是二进制，那么就随机选取一个位置进行0和1的互相突变；如果解的编码方式是十进制，那么就随机选取一个位置进行随机加减。 交叉 的做法是随机从最优种群中选取两个个体，以某个位置为交叉点合成一个新的个体。

经过突变和交叉后我们得到新的种群（大小与上一代种群一致），对新种群重复重复上述过程，直到达到迭代次数（失败）或者解的适应性达到我们的要求（成功），GA算法就结束了。

算法实现

首先定义一个课程类，这个类包含了课程、班级、教师、教室、星期、时间几个属性，其中前三个是我们自定义的，后面三个是需要算法来优化的。

接下来定义cost函数，这个函数用来计算课表种群的冲突。当被测试课表冲突为0的时候，这个课表就是个符合规定的课表。冲突检测遵循下面几条规则：

使用遗传算法进行优化的过程如下，与上一节的流程图过程相同。

init_population ：随机初始化不同的种群。
mutate ：变异操作，随机对 Schele 对象中的某个可改变属性在允许范围内进行随机加减。
crossover ：交叉操作，随机对两个对象交换不同位置的属性。
evolution ：启动GA算法进行优化。

实验结果

下面定义了3个班，6种课程、教师和3个教室来对排课效果进行测试。

优化结果如下，迭代到第68次时，课程安排不存在任何冲突。

选择1203班的课表进行可视化，如下所示，算法合理的安排了对应的课程。

Ⅱ 遗传算法的优缺点

优点：

1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。

另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。

2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。

3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。

另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。

4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。

5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。

缺点：

1、遗传算法在进行编码时容易出现不规范不准确的问题。

2、由于单一的遗传算法编码不能全面将优化问题的约束表示出来，因此需要考虑对不可行解采用阈值，进而增加了工作量和求解时间。

3、遗传算法效率通常低于其他传统的优化方法。

4、遗传算法容易出现过早收敛的问题。

(2)遗传算法流程扩展阅读

遗传算法的机理相对复杂，在Matlab中已经由封装好的工具箱命令，通过调用就能够十分方便的使用遗传算法。

函数ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。

为了设置options，需要用到下面这个函数：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通过这个函数就能够实现对部分遗传算法的参数的设置。

Ⅲ 遗传算法理解

遗传算法是一种进化算法，进化是什么哪？就是种群逐渐适应生存环境，种群中个体不断得到改良的过程。

遗传算法是一种对生物遗传的模拟、在算法中，初始化一个种群，种群中的每个染色体个体都是一种解决方案，我们通过适应性fitness来衡量这个解决方案的好坏。并对它们进行选择、变异、交叉的操作，找到最优的解决方案。

总结一下遗传算法的基本的步骤：

1.初始化一个种群，并评估每条染色体所对应个体的适应度。

2.选择、交叉、变异，产生新的种群

3.再评估每个个体的适应值，如果适应值达到要求或者达到最大循环次数，否则重复2，不断产生新种群。

知道了GA的大致流程之后、来具体分析一下细节，怎么实现吧

我们知道遗传算法起源于生物遗传，因此在种群中每个个体就是一个染色体，那如何对染色体进行编码，让它表示我们的解决方案那（就是把现实要优化的参数用编码表示成一个染色体）。这里就遇到了一个编码、解码的问题，我们将需要优化的目标编码成染色体，然后再解码为我们可以用来计算fitness的解；

一般在进行参数优化时，一般有两种方式：实数编码、二进制编码

实数编码：基因直接用实数进行表示，这样的表示方法比较简单，不用特意解码了，但是在交叉和变异时，容易过早收敛，陷入局部最优。

二进制编码：将基因用二进制的形式表示，将参数的值转化为二进制形式，这样交叉、变异时更好操作，多样性好，但是占用的存储空间大，需要解码。

染色体就称为个体。对于一次实验，个体就是需要优化参数的一种解、许多这样的个体就构成了种群。

在面对群体中那么多个体时，如何判断个体的好坏呢，就是通过适应值函数了，将解带入适应值函数，适应值越大、解越好。

在遗传算法中，我们怎么使得里面的个体变得越来越优秀呢？

核心思想就是：选择优秀的、淘汰不好的，并且为了生成更好的解，我们要尝试交叉、变异，带来新的解。

选择就是从当前的种群中选择出比较好的个体、淘汰不好的个体

常见的选择方法有：轮盘赌选择、锦标赛选择、最佳保留选择等等

轮盘赌选择就是根据每个个体fitness和种群所有fitness之和比较，确定每个个体被选中的概率，然后进行n次选择，选择n个个体构成新种群，是一种放回抽样的方式。

锦标赛就是每次从种群中选择m个个体，选择最优的，放入新种群，重复选择，直到新种群中个体数目达到n。

最佳保留选择就是在轮盘赌的基础上，将fitness个体先加进新种群，因为轮盘赌是一种概率模型，可能存在最优个体没有进入新种群的情况。

在选择之后，就要考虑产生新的、更优秀的解，为种群带来新的血液。遗传算法的思路是交叉两个优秀的解，往往get好的解。

交叉通过在经过选择的种群中，随机选择一对父母，将它们的染色体进行交叉，生成新的个体，替代原来的解。

常用的交叉方法有：单点交叉、多点交叉等等。

交叉就像生物里面，染色体交换基因一样的～但是并不是种群中所有个体都进行交叉的，实现时可以，设置一个交叉率和交叉概率，随机选择种群中两个体、随机一个数，小于交叉率就进行交叉操作，并根据交叉概率判断交叉的程度，从而生成新个体，反之就保留这两个体。

变异也是一种产生新个体的方式，通过改变个体上基因，期望产生更好的解。比如在以二进制编码的个体上，将里面的0、1进行等位变化啥的，就是0变1、1变0这样。同样也要考虑变异率、变异产生的新解是不可控的，可能很好，也可能很坏，不能像交叉一样，确保一定的效果，所以往往变异率设置的比较小。

Ⅳ 神经网络遗传算法函数极值寻优

对于未知的非线性函数，仅通过函数的输入输出数据难以准确寻找函数极值。这类问题可以通过神经网络结合遗传算法求解，利用神经网络的非线性拟合能力和遗传算法的非线性寻优能力寻找函数极值。本文用神经网络遗传算法寻优如下非线性函数极值，函数表达式为

函数图形如下图1所示。

从函数方程和图形可以看出，该函数的全局最小值为0，对应的坐标为(0,0)。虽然从函数方程和图形中很容易找出函数极值及极值对应坐标，但是在函数方程未知的情况下函数极值及极值对应坐标就很难找到。

神经网络遗传算法函数极值寻优主要分为BP神经网络训练拟合和遗传算法极值寻优两步，算法流程如下图2所示。

神经网络训练拟合根据寻优函数的特点构建合适的BP神经网络，用非线性函数的输出数据训练BP网络，训练后的BP神经网络就可以预测函数输出。遗传算法极值寻优把训练后的BP神经网络预测结果作为个体适应度值，通过选择、交叉和变异操作寻找函数的全局最优值及对应输入值。
本文根据非线性函数有2个输入参数、1个输出参数，确定BP神经网络结构为2-5-1.取函数的4 000组输入输出数据，从中随机选取3 900组数据训练网络，100组数据测试网络性能，网络训练好后用于预测非线性函数输出。
遗传算法中个体采用实数编码，由于寻优函数只有2个输入参数，所以个体长度为2。个体适应度值为BP神经网络预测值，适应度值越小。交叉概率为0.4，变异概率为0.2。

用函数输入输出数据训练BP神经网络，使训练后的网络能够拟合非线性函数输出，保存训练好的网络用语计算个体适应度值。根据非线性函数方程随机得到该函数的4 000组输入输出数据，存储于data.mat中，其中input为函数输入数据，output为函数对应输出数据，从中随机抽取3 900组训练数据训练网络，100组测试数据测试网络拟合性能。最后保存训练好的网络。

把训练好的BP神经网络预测输出作为个体适应度值。

BP神经网络拟合结果分析
本文中个体的适应度值为BP神经网络预测值，因此BP神经网络预测精度对于最优位置的寻找具有非常重要的意义。由于寻优非线性函数有2个输入参数、1个输出参数，所以构建的BP神经网络的结构为2-5-1。共取非线性函数4 000组输入输出数据，从中随机选择3 900组数据训练BP神经网络，100组数据作为测试数据测试BP神经网络拟合性能，BP神经网络预测输出和期望输出对比如下图3所示。

从BP神经网络预测结果可以看出，BP神经网络可以准确预测非线性函数输出，可以把网络预测近似看成函数实际输出。

遗传算法寻优结果分析 BP神经网络训练结束后，可以利用遗传算法寻找该非线性函数的最小值。遗传算法的迭代次数是100次，种群规模是20，交叉概率为0.4，变异概率为0.2，采用浮点数编码，个体长度为21，优化过程中最优个体适应度值变化曲线如下图4所示。

本文所使用的方法有比较重要的工程应用价值，比如对于某项试验来说，试验目的是获取到最大试验结果对应的实验条件，但是由于时间和经费限制，该试验只能进行有限次，可能单靠试验结果找不到最优的试验条件。这时可以在已知试验数据的基础上，通过本文介绍的神经网络遗传算法寻找最优试验条件。
思路就是先根据试验条件数和试验结果数确定BP神经网络结构；然后把试验条件作为输入数据，试验结果作为输出数据训练BP网络，使得训练后的网络可以预测一定试验条件下的试验结果；最后把试验条件作为遗传算法中的种群个体，把网络预测的试验结果作为个体适应度值，通过遗传算法推导最优试验结果及其对应试验条件。

Ⅳ 优化算法笔记（六）遗传算法

遗传算法(Genetic Algorithms，GA)是一种粗衡模拟自然中生物的遗传、进化以适应环境的智能算法。由于其算法流程简单，参数较少优化速度较快，效果较好，在图像处理、函数优化、信号处理、模式识别等领域有着广泛的应用。
在遗传算法（GA）中，每一个待求问题的候选解被抽象成为种群中一个个体的基因。种群中个体基因的好坏由表示个体基因的候选解在待求问题中的所的得值来评判。种群中的个体通过与其他个体交叉产生下一代，每一代中个体均只进行一次交叉。两个进行交叉的个体有一定几率交换一个或者多个对应位的基因来产生新的后代。每个后代都有一定的概率发生变异。发生变异的个体的某一位或某几位基因会变异成其他值。最终将以个体的适应度值为概率选取个体保留至下一代。

遗传算法启发于生物的繁殖与dna的重组，本次的主角选什么呢？还是根据大家熟悉的孟德尔遗传规律选豌豆吧，选动物的话又会有人疑车，还是植物比较好，本次的主角就是它了。

遗传算法包含三个操作（算子）：交叉，变异和选择操作。下面我们将详细介绍这三个操作。
大多数生物的遗传信息都储存在DNA，一种双螺旋结构的复杂有机化合物。其含氮碱基为腺嘌呤、鸟嘌呤、胞嘧啶及胸腺嘧啶。

表格中表示了一个有10个基因的个体，它们每一个基因的值为0或者1。

生物的有性生殖一般伴随着基因的重组。遗传算法中父辈和母辈个体产生子代个体的过程称为交叉。

表中给出了两个豌豆的基因，它们均有10个等位基因（即编号相同的基因）。
遗传算法的交叉过程会在两个个体中随机选择1位或者n位基因进行交叉，即这两个个体交换等位基因。
如，A豌豆和B豌豆在第6位基因上进行交叉，则其结果如下

当两个个体交叉的等位基因相同时，交叉过程也有可能没有产生新慧衡的个体，如交叉A豌豆和B豌豆的第2位基因时，交叉操作并没有产生新的基因。

一般的会给群体设定一个交叉率，crossRate，表示会在群体中选取一定比例的个体进行交叉，交叉率相对较大，一般取值为0.8。

基因的变异是生物进化的一个主要因素。
遗传算法中变异操作相对简单，只需要将一个随机位基因的值修改就行了，因为其值只为0或1，那么当基因为0时，变异操作会将其值设为1，当基因值为1时，变异操作会将其值设为0。

上图表示了A豌豆第3位基因变异后的基因编码。
与交叉率相似，变异操作也有变异率，alterRate，但是变异率会远低于交叉率，否则会产生大量的随机基因。一般变异率为0.05。

选择操作是遗传算法中的一个关键操作，它的主要作用就是根据一定的策略随机选择个体保留至下一代。适应度越优的岩碧做个体被保留至下一代的概率越大。
实现上，我们经常使用“轮盘赌”来随机选择保留下哪个个体。

假设有4个豌豆A、B、C、D，它们的适应度值如下：

适应度值越大越好，则它们组成的轮盘如下图：

但由于轮盘赌选择是一个随机选择过程，A、B、C、D进行轮盘赌选择后产生的下一代也有可能出现A、A、A、A的情况，即虽然有些个体的适应度值不好，但是运气不错，也被选择留到了下一代。
遗产算法的三个主要操作介绍完了，下面我们来看看遗传算法的总体流程：

前面我们说了遗传算法的流程及各个操作，那么对于实际的问题我们应该如何将其编码为基因呢？

对于计算机来所所有的数据都使用二进制数据进行存放，如float类型和double类型的数据。
float类型的数据将保存为32位的二进制数据：1bit（符号位） 8bits（指数位） 23bits（尾数位）
如-1.234567f，表示为二进制位

Double类型的数据将保存为64位的二进制数据：1bit（符号位） 11bits（指数位） 53bits（尾数位）
如-1.234567d，表示为二进制为

可以看出同样的数值不同的精度在计算机中存储的内容也不相同。之前的适应度函数 ，由于有两个double类型的参数，故其进行遗传算法基因编码时，将有128位基因。
虽然基因数较多，但好在每个基因都是0或者1，交叉及变异操作非常简单。

相比二进制编码，十进制编码的基因长度更短，适应度函数 有两个输入参数，那么一个个体就有2个基因，但其交叉、变异操作相对复杂。
交叉操作
方案1：将一个基因作为一个整体，交换两个个体的等位基因。
交换前

交换第1位基因后

方案2：将两个个体的等位基因作为一个整体，使其和不变，但是值随机
交换前

交换第1位基因后

假设A、B豌豆的第一位基因的和为40，即 ,第一位基因的取值范围为0-30，那么A、B豌豆的第一位基因的取值范围为[10,30],即 为[0,30]的随机数， 。
变异操作，将随机的一位基因设置为该基因取值范围内的随机数即可。

这个过程说起来简单但其实现并不容易。

我们要将它们的值映射到一个轴上才能进行随机选择，毕竟我们无法去绘制一个轮盘来模拟这个过程

如图，将ABCD根据其值按顺序排列，取[0,10]内的随机数r，若r在[0,1]内则选择A,在(1,3]内则选择B,在(3,6]内则选择C,在(6,10]则选择D。
当然这仍然会有问题，即当D>>A、B、C时，假如它们的值分布如下

那么显然，选D的概率明显大于其他，根据轮盘赌的选择，下一代极有可能全是D的后代有没有办法均衡一下呢？
首先我想到了一个函数，

不要问我为什么我不知道什么是神经什么网络的，什么softmax、cnn统统没听说过。

这样一来，它们之间的差距没有之前那么大了，只要个体适应度值在均值以上那么它被保留至下一代的概率会相对较大，当然这样缩小了个体之间的差距，对真正优秀的个体来说不太公平，相对应，我们可以在每次选择过程中保留当前的最优个体到下一代，不用参与轮盘赌这个残酷的淘汰过程。

最令人高兴的环节到了，又可以愉快的凑字数了。

由于遗传算法的收敛速度实在是太慢，区区50代，几乎得不到好的结果，so我们把它的最大迭代次数放宽到200代。

使用二进制编码来进行求解
参数如下：

求解过程如上图，可以看出基因收敛的很快，在接近20代时就图中就只剩一个点了，之后的点大概是根据变异操作产生。看一下最后的结果。

可以看出最好的结果已经得到了最优解，但是10次实验的最差值和平均值都差的令人发指。为什么会这样呢？

问题出在二进制编码上，由于double类型的编码有11位指数位和52位小数位，这会导致交叉、变异操作选到指数位和小数位的概率不均衡，在小数位上的修改对结果的影响太小而对指数为的修改对结果的影响太大，
如-1.234567d，表示为二进制为

对指数为第5位进行变异操作后的结果为-2.8744502924382686E-10，而对小数位第5为进行变异操作后的结果为-1.218942。可以看出这两部分对数值结果的影响太不均衡，得出较好的结果时大概率是指数位与解非常相近，否则很难得出好的结果，就像上面的最差值和均值一样。
所以使用上面的二进制编码不是一个好的基因编码方式，因此在下面的实验中，将使用十进制来进行试验。

使用:十进制编码来进行求解
参数如下：

我们可以看到直到40代时，所有的个体才收束到一点，但随后仍不断的新的个体出现。我们发现再后面的新粒子总是在同一水平线或者竖直线上，因为交叉操作直接交换了两个个体的基因，那么他们会相互交换x坐标或者y坐标，导致新个体看起来像在一条直线上。
我们来看看这次的结果。

这次最优值没有得到最优解，但是最差值没有二进制那么差，虽然也不容乐观。使用交换基因的方式来进行交叉操作的搜索能力不足，加之轮盘赌的选择会有很大概率选择最优个体，个体总出现在矩形的边上。
下面我们先改变轮盘赌的选择策略，使用上面的sigmod函数方案，并且保留最优个体至下一代。

使用:十进制编码来进行求解
参数如下：

看图好像跟之前的没什么区别，让我们们看看最终的结果：

可以看出，最优值没有什么变化，但是最差值和平均值有了较大的提升，说明该轮盘赌方案使算法的鲁棒性有了较大的提升。在每次保留最优个体的情况下，对于其他的个体的选择概率相对平均，sigmod函数使得即使适应度函数值相差不太大的个体被选到的概率相近，增加了基因的多样性。

使用:十进制编码来进行求解，改变交叉方案，保持两个个体等位基因和不变的情况下随机赋值。
参数如下：

上图可以看出该方案与之前有明显的不同，在整个过程中，个体始终遍布整个搜索空间，虽然新产生的个体大多还是集中在一个十字架型的位置上，但其他位置的个体比之前的方案要多。
看看结果，

这次的结果明显好于之前的所有方案，但仍可以看出，十进制的遗传算法的精度不高，只能找到最优解的附近，也有可能是算法的收敛速度实在太慢，还没有收敛到最优解。

遗传算法的探究到此也告一段落，在研究遗传算法时总有一种力不从心的感觉，问题可能在于遗传算法只提出了一个大致的核心思想，其他的实现细节都需要自己去思考，而每个人的思维都不一样，一万个人能写出一万种遗传算法，其实不仅是遗传算法，后面的很多算法都是如此。
为什么没有对遗传算法的参数进行调优，因为遗传算法的参数过于简单，对结果的影响的可解释性较强，意义明显，实验的意义不大。

遗传算法由于是模仿了生物的进化过程，因此我感觉它的求解速度非常的慢，而且进化出来的结果不一定是最适应环境的，就像人的阑尾、视网膜结构等，虽然不是最佳的选择但是也被保留到了今天。生物的进化的随机性较大，要不是恐龙的灭绝，也不会有人类的统治，要不是人类有两只手，每只手有5根手指，也不会产生10进制。
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（五）粒子群算法（3）
下一篇 优化算法笔记（七）差分进化算法

优化算法matlab实现（六）遗传算法matlab实现

Ⅵ 遗传算法是什么

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
遗传算法(Genetic Algorithms简称GA)是由美国Michigan大学的John Holland教授于20世纪60年代末创建的。它来源于达尔文的进化论和孟德尔、摩根的遗传学理论，通过模拟生物进化的机制来构造人工系统。遗传算法作为一种全局优化方法，提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对优化函数的要求很低并且对不同种类的问题具有很强的鲁棒性，所以广泛应用于计算机科学、工程技术和社会科学等领域。John Holland教授通过模拟生物进化过程设计了最初的遗传算法，我们称之为标准遗传算法。
标准遗传算法流程如下：
1）初始化遗传算法的群体，包括初始种群的产生以及对个体的编码。
2）计算种群中每个个体的适应度，个体的适应度反映了其优劣程度。
3）通过选择操作选出一些个体，这些个体就是母代个体，用来繁殖子代。
4）选出的母代个体两两配对，按照一定的交叉概率来进行交叉，产生子代个体。
5）按照一定的变异概率，对产生的子代个体进行变异操作。
6）将完成交叉、变异操作的子代个体，替代种群中某些个体，达到更新种群的目的。
7）再次计算种群的适应度，找出当前的最优个体。
8）判断是否满足终止条件，不满足则返回第3）步继续迭代，满足则退出迭代过程，第7）步中得到的当前最优个体，通过解码，就作为本次算法的近似最优解。

具体你可以到网络文库去搜索遗传算法相关的论文，很多的。
你也可以参考网络里对遗传算法的介绍。

Ⅶ 进化算法的基本步骤

进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。
一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新操作。
以遗传算法为例，其工作步骤可概括为：
（1） 对工作对象——字符串用二进制的0/1或其它进制字符编码 。
（2） 根据字符串的长度L，随即产生L个字符组成初始个体。
（3） 计算适应度。适应度是衡量个体优劣的标志，通常是所研究问题的目标函数。
（4） 通过复制，将优良个体插入下一代新群体中，体现“优胜劣汰”的原则。
（5） 交换字符，产生新个体。交换点的位置是随机决定的
（6） 对某个字符进行补运算，将字符1变为0，或将0变为1，这是产生新个体的另一种方法，突变字符的位置也是随机决定的。
（7） 遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等操作，直至满足终止条件。
将其用形式化语言表达，则为：假设α∈I记为个体，I记为个体空间。适应度函数记为Φ：I→R。在第t代，群体P(t)={a1(t),a2(t)，…，an(t)}经过复制r(reproction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r、c、m均指宏算子，把旧群体变换为新群体。L：I→{True, Flase}记为终止准则。利用上述符号，遗传算法可描述为：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)};
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};
reproction: P′(t):=r(P(t));
crossover: P″(t):=c(P′(t));
mutation: P(t+1):= m(P″(t));
t=t+1;
end

Ⅷ 关于遗传算法

遗传算法（Genetic Algorithm，简称GA）是美国 Michigan大学的 John Golland提出的一种建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、具有广泛适用性的搜索方法。现在已被广泛用于学习、优化、自适应等问题中。图4-1 给出了 GA搜索过程的直观描述。图中曲线对应一个具有复杂搜索空间（多峰空间）的问题。纵坐标表示适应度函数（目标函数），其值越大相应的解越优。横坐标表示搜索点。显然，用解析方法求解该目标函数是困难的。采用 GA时，首先随机挑选若干个搜索点，然后分别从这些搜索点开始并行搜索。在搜索过程中，仅靠适应度来反复指导和执行 GA 搜索。在经过若干代的进化后，搜索点后都具有较高的适应度并接近最优解。

一个简单GA由复制、杂交和变异三个遗传算子组成：

图4-2 常规遗传算法流程图