遗传算法的研究与应用

A. 遗传算法有哪些方向

遗传算法研究方向主要有以下几个方面：
1. 遗传算法基础理论研究
在遗传算法中,群体规模和遗传算子的控制参数的选取 是必要的试验参数。
遗传算法的收敛也是遗传算法基础理论研究方向之一。

2. 遗传算法的分类系统
分类系统属于基于遗传算法的机器学习中的一类,包括一个简单 的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统 。
分类系统被人们越来越多地应用在科学、工程和经济领域中,是目 前遗传算法研究中一个十分活跃的领域。
3. 分布并行遗传算法
分布并行遗传算 法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用 来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效 率。
4. 遗传进化算法
模拟自然进化过程可以产生鲁棒的计算机算法--进化算法。其余两种算法是进化规划和进化策略 。

5. 遗传神经网络
包括连接权、网络结构和学习规则的进化。

B. 遗传算法的优缺点

优点：

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', ...)通过这个函数就能够实现对部分遗传算法的参数的设置。

C. 遗传算法的现状

进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显着提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。
1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随机迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。
1992年，英国格拉斯哥大学的李耘（Yun Li）指导博士生将基于二进制基因的遗传算法扩展到七进制、十进制、整数、浮点等的基因，以便将遗传算法更有效地应用于模糊参量，系统结构等的直接优化，于1997年开发了可能是世界上最受欢迎的、也是最早之一的遗传/进化算法的网上程序 EA_demo，以帮助新手在线交互式了解进化计算的编码和工作原理 ，并在格拉斯哥召开第二届IEE/IEEE遗传算法应用国际会议，于2000年组织了由遗传编程(Genetic Programming)发明人斯坦福的 John Koza 等参加的 EvoNet 研讨会，探索融合GA与GP结构寻优，超越固定结构和数值优化的局限性。
国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题
2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。
2005年，江雷等针对并行遗传算法求解TSP问题，探讨了使用弹性策略来维持群体的多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进化。

D. 基于遗传算法的水文频率计算与研究

对广西壮族自治区梧州藤县大任河水库1966～2005年年最大24h降雨量进行分析研究，根据经验，采用P-Ⅲ型曲线对降雨量分布点据进行拟合，运用矩法、概率权重矩法、单权函数法、双权函数法对P-Ⅲ型曲线的三个参数初估，把P-Ⅲ型曲线的三个参数作为GA的决策变量，分析调整得到GA决策变量的取值范围，最后，通过GA优化决策变量的取值，计算得出设计洪水，并进行了合理性分析。结论如下:

1)采用矩法、概率权重矩法、单权函数法和双权函数法，初估P-Ⅲ型分布曲线的三个参数，通过适当的调整，来确定GA的决策变量的取值范围。预先设定了12组GA运行参数，从12次的程序调试运行成果中，分析确定合适的运行参数取值范围;GA程序调试过程表明，初始的种群数要足够大，才能保证交叉和变异操作的有效进行;初始的种群数太小，交叉和变异操作后的个体缺乏多样性，不利于程序搜索最优点。种群规模足够大，交叉概率为0.6和0.8时，对适应度函数收敛曲线的影响不是很大，而变异概率过大，适应度函数收敛曲线上下波动大。在实际操作中，GA的运行参数中的种群规模、交叉概率和变异概率三者之间是相互约束的。一般来说，当种群规模大时，交叉概率就相应的选择小一点的值，但也并非一成不变，需要从整体上考虑，找出其中的平衡点，目前并没有完善的理论加以指导，还得根据实际问题，反复不停的调试，最终才能发现适合实际情况的GA运行参数。

2)GA是一种新的自适应搜索方法，它是建立在生物遗传学和计算机的基础上，通过运用杂交、变异两种算子作为搜索工具，用适应度的函数对搜索到的解的质量进行评价，并根据评价的结果用选择算子来引导以后的搜索方向。

3)GA拟合曲线的精度较高，30次计算成果的相对误差都在允许的偏差的范围内， GA计算有效性的合格率为70%，总体上优于双权函数法，实际应用时，需根据实际的计算结果，选择精度高(平均相对误差较小)的一次运算作为计算依据;同时，由于GA以及其在水文水资源系统工程中的应用尚未成熟，所以实际计算应结合计算精度也较高的双权函数法进行比较，GA的计算可以作为一种参考，或在综合比较和论证的情况下作为设计依据。

E. 遗传算法的核心是什么！

遗传操作的交叉算子。

在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。

(5)遗传算法的研究与应用扩展阅读

评估编码策略常采用以下3个规范：

a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。

b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。

c)非冗余性(nonrendancy):染色体和候选解一一对应。

目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。

而二进制编码是目前遗传算法中最常用的编码方法。即是由二进制字符集{0,1}产生通常的0,1字符串来表示问题空间的候选解。

F. 遗传算法^[1，]

遗传算法，又称基因算法(Genetic Algorithm，简称GA)，也是一种启发式蒙特卡洛优化算法。遗传算法最早是由Holland(1975)提出，它模拟了生物适者生存、优胜劣汰的进化过程，具有不依赖于初始模型的选择、不容易陷入局部极小、在反演过程中不用计算偏导数矩阵等优点。遗传算法最早由Stoffa和Sen(1991)用于地震波的一维反演，之后在地球物理资料的非线性反演中得到广泛的应用。GA算法对模型群体进行追踪、搜索，即模型状态通过模型群体传送，具有比模拟退火法更大、更复杂的“记忆”，潜力更大。

遗传算法在反演中的基本思路和过程是:

(1)将生物体看成模型，模型参数看成染色体，有多少个模型的参数就有多少个染色体。对每个模型的参数(染色体)用二进制进行编码，这个编码就是基因。

(2)随机生成一个模型群体(相当于生物的种群)，然后在模型群体中进行繁殖，通过母本的选择、交换和变异等遗传操作产生下一代，然后保留较好基因，淘汰较差基因。

(3)通过一代一代的繁殖优胜劣汰的进化过程，最后所剩下的种群基本上都是最优的基因，种群趋于一致。所谓群体“一致”，即群体目标函数的方差或标准差很小，或者群体目标函数的均值接近于极值(可能是极大值或极小值)，从而获得非线性反演问题所对应的最优解或近似最优解。

下面以一个实例来简述遗传算法的基本过程。

[例1]设m是正整数，且0≤m≤127，求方程φ(m)=m²的极大值。

这个例子极为简单，只有一个模型参数，因此只有一条染色体，目标函数的极值是极大值(此例子来自阮百尧课件)。遗传算法通过以下7个步骤来实现:

(1)模型参数二进制编码。

每个模型参数就是一条染色体，把十进制的模型参数表示为二进制，这就是基因。首先确定二进制码的长度(基因的长度):

2^N=[m_max(i)-m_min(i)]/Δm(i) (8.20)

其中:N为第i条染色体基因的长度(也就是第i个模型参数的二进制码位数);[m_min(i)，m_max(i)]为第i个模型参数的取值范围;Δm(i)为第i个模型参数的分辨率。这样就把模型参数离散化了，它只能按Δm(i)的整数倍变化。基因的长度按下式计算:

地球物理反演教程

其中:c为实数;N为基因长度，是整数;int[ ]为取整函数。上式表示如果c不是整数，那么基因长度N就是对c取整后加1，这样保证最小分辨率。

基因的编码按下式进行:

地球物理反演教程

其中:式(8.22)是编码公式;k为基因编码的十进制数，是整数;int[ ]为取整函数。把k转化为二进制就是基因的编码。解码是按照式(8.23)进行的。首先把一个基因的二进制编码转化为十进制数k，然后按式(8.23)可以计算出第i个模型参数m(i)的十进制值。

例如:电阻率参数ρ(1)，它的变化范围为10~5000Ω·m，分辨率为2Ω·m，设当前参数ρ(1)=133Ω·m，按式(8.21)计算得

c=11.28482，N=12

所以二进制基因长度为13位。

利用式(8.22)计算基因编码k的十进制数:

k=int[(133-10)/2]=61

把它转化为二进制数为:000000111101。所以ρ(1)=133 的二进制基因编码为:000000111101。

解码过程就是把二进制基因编码变为十进制数k后用式(8.23)计算:

ρ(1)=10+61×2=132(Ω·m)

注意:基因编码并不是直接把电阻率值变为二进制。此外，133这个值在基因里不会出现，因为分辨率是2，所以表示为最接近的132。

对于[例1]问题来说，选分辨率为1，0~127用二进制编码需7位。

(2)产生初始模型种群。

生物繁殖进化需要一定数量的生物体种群，因此遗传算法开始时需要一定数量的初始模型。为保证基因的多样性，随机产生大量的初始模型作为初始种群，按照上面的编码方式进行编码。个体在模型空间中应分布均匀，最好是模型空间各代表区域均有成员。初始模型群体大，有利于搜索，但太大会增加计算量。

为保证算法收敛，在初始模型群体中，有时候应增加各位都为0和都为1的成员。遗传算法就是在这个初始模型种群的基础上进行繁殖，进化求解的。

对于[例1]问题来说，模型空间是0~127个数字，这样初始种群最多具有128个个体。为了简单，随机选择4个个体作为初始种群。初始种群的编码、目标函数值见表8.1。

表8.1 初始种群编码表

(3)模型选择。

为了生成新一代模型，需要选择较优的个体进行配对。生物进化按照自然选择、优胜劣汰的准则进行。对应地，遗传算法按照一定的准则来选择母本(两个)，然后进行配对繁殖下一代模型，这个选择称为模型选择。模型配对最基本的方法是随机采样，用各模型的目标函数值对所有模型目标函数的平均值的比值定义繁殖概率，即

地球物理反演教程

其中:p(m_i)为繁殖概率;φ(m_i)为第i个模型的目标函数;φ_AVG为目标函数的平均值。对于极小化问题来说，规定目标函数值高于平均值的不传代;对于极大化问题来说，反之即可。

就[例1]来说，要求目标函数取极大值，所以规定目标函数小于平均值的模型不传代，大于它的可以传代。对第一代，为了防止基因丢失，可先不舍去繁殖概率小的模型，让它与概率大的模型配对。如:本例中70与56配对，101与15配对产生子代，见表8.2。

表8.2 基因交换表

(4)基因交换。

将配对的两个亲本模型的部分染色体相互交换，其中交换点可随机选择，形成两个新的子代(见表8.2)。两个染色体遗传基因的交换过程是遗传算法的“繁殖”过程，是母本的重组过程。

为了使染色体的基因交换比较彻底，Stoffa等人提出了一个交换概率p_x来控制选择操作的效果。如果p_x的值较小，那么交换点的位置就比较靠低位，这时的交换操作基本是低位交换，交换前后模型的染色体变化不是太大。如果p_x的值较大，那么交换点的位置就比较靠高位，此时的交换操作可以在较大的染色体空间进行，交换前后模型数值变化可以很大。

在[例1]中:15、101和56、70作为母本通过交换繁殖出子代5、6、111、120。所选择的基因交换位置见表8.2。有下划线的，是要交换的基因位置。

(5)更新。

母本模型和子本模型如何选择保留一定数量作为新的母本，就是模型更新。不同的策略会导致不同的结果。一般而言，若产生的新一代模型较好，则选择新一代模型而淘汰上一代模型。否则，则必须根据一定的更新概率p_u来选择上一代模型来取代新一代中某些较劣的模型。

经过更新以后，繁殖时对子代再进行优胜劣汰的选择。对于极大值问题，大于目标函数平均值的子代可以繁殖，小于目标函数平均值的子代不能繁殖。由于新的种群能繁殖的个体数量减小了，所以要多繁殖几次，维持种群个体的数量保持平衡。

在[例1]中，子代较好，所以完全淘汰上一代模型，完全用子代作为新的母本。选择子代目标函数最大的两个模型进行繁殖，分别是111、120。

(6)基因变异。

在新的配对好的母本中，按一定比例随机选择模型进行变异，变异操作就是模拟自然界中的环境因素，就是按比较小的变异概率p_m将染色体某位或某几位的基因发生突变(即将0变为1或将1变为0)。

变异操作的作用是使原来的模型发生某些变化，从而成为新的个体。这样可使群体增加多样性。变异操作在遗传算法中也起着至关重要的作用。实际上，由于搜索空间的性质和初始模型群体的优劣，遗传算法搜索过程中往往会出现所谓的“早熟收敛”现象，即在进化过程中早期陷入局部解而中止进化。采用合适的变异策略可提高群体中个体的多样性，从而防止这种现象的出现，有助于模型跳出局部极值。表8.3为[例1]的基因变异繁殖表。

表8.3 基因变异繁殖表

在[例1]中，用111、120分别繁殖两次，形成4个子代，维持种群数量平衡。随机选择120进行变异，变异的位数也是随机的。这里把它的第2位进行变异，即从1变为0，繁殖后形成子代为:70、110、121、127。可以看出新的子代比初始种群要好得多，其中甚至已经出现了最优解。如果对于地球物理的极小值问题，我们可以预先设置一个拟合精度，只要在种群中出现一个达到拟合精度的模型就可以终止反演了。

(7)收敛。

重复(3)~(6)的步骤，模型群体经多次选择、交换、更新、变异后，种群个体数量大小不变，模型目标函数平均值趋于稳定，最后聚集在模型空间中一个小范围内，则找到了全局极值对应的解，使目标函数最大或最小的模型就是全局最优模型。

对于具有多解性的地球物理反演问题来说，通过这一步有可能找到满足拟合精度的多个模型，对于实际反演解释、推断具有较高的指导意义。

遗传算法中的各种概率包括交换概率px、变异概率p_m以及更新概率p_u，这些参数的选择与设定目前尚无统一的理论指导，多数都视具体问题而定。Stoffa等(1991)的研究表明，适中的交换概率(p_x≈0.6)、较小的变异概率(p_m≈0.01)和较大的更新概率(p_u≈0.9)，遗传算法的性能较优。

与模拟退火反算法相同，遗传算法与传统的线性反演方法相比，该方法具有:不依赖初始模型的选择、能寻找全局最小点而不陷入局部极小、在反演过程中不用计算雅克比偏导数矩阵等优点。另外，遗传算法具有并行性，随着并行计算和集群式计算机技术的发展，该算法将会得到越来越广泛的研究与应用。

但是遗传算法作为类蒙特卡洛算法同样需要进行大量的正演计算，种群个体数量越大，繁衍代数越多，则计算量越大。所以和前面的最小二乘法相比，速度不是它的优势。

G. 什么是遗传（要详细的资料和图片解说）

摘要
遗传是指经由基因的传递，使后代获得亲代的特征。遗传学是研究此一现象的学科，目前已知地球上现存的生命主要是以DNA作为遗传物质。除了遗传之外，决定生物特征的因素还有环境，以及环境与遗传的交互作用。
[编辑本段]特点
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：[1]
1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。
2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。
3、 遗传算法使用多个点的搜索信息，具有隐含并行性。
4、 遗传算法使用概率搜索技术，而非确定性规则。
[编辑本段]应用
由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：
1、 函数优化。
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。遗传与生育
2、 组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。
此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。
[编辑本段]现状
进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显着提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。儿童孤独症可能来自遗传
随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。
1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。
D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。
H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。
国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题
2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。
2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。
[编辑本段]一般算法
遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显着特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：
��
[编辑本段]创建一个随机的初始状态
��初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。
��评估适应度
��对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。
��繁殖(包括子代突变)
��带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。
��下一代
��如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。
��并行计算
��非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。
[编辑本段]遗传算法-基本框架
1 GA的流程图
GA的流程图如下图所示
2 编码
遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作(问题的)表示(representation)。
评估编码策略常采用以下3个规范:
a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。
b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。
c)非冗余性(nonrendancy):染色体和候选解一一对应。
目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。
而二进值编码是目前遗传算法中最常用的编码方法。即是由二进值字符集{0, 1}产生通常的0, 1字符串来表示问题空间的候选解。它具有以下特点:
a)简单易行；
b)符合最小字符集编码原则；
c)便于用模式定理进行分析，因为模式定理就是以基础的。
3 适应度函数
进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。
遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值.由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。
适应度函数的设计主要满足以下条件：
a）单值、连续、非负、最大化；
b) 合理、一致性；
c）计算量小；
d）通用性强。
在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。
4 初始群体的选取
遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:
a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。
b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。
[编辑本段]遗传算法-遗传操作
遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼进最优解。
遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点:
个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。
遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。
1 选择
从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种:适应度比例方法、随机遍历抽样法、局部选择法、局部选择法。
其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率,为
显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例.个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。
2 交叉
在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：
a)实值重组（real valued recombination）
1)离散重组（discrete recombination）；
2)中间重组（intermediate recombination）；
3)线性重组（linear recombination）；
4)扩展线性重组（extended linear recombination）。
b)二进制交叉（binary valued crossover）
1)单点交叉（single-point crossover）；
2)多点交叉（multiple-point crossover）；
3)均匀交叉（uniform crossover）；
4)洗牌交叉（shuffle crossover）；
5)缩小代理交叉（crossover with reced surrogate）。
最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：
个体A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体
个体B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体
3 变异
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：
a)实值变异；
b)二进制变异。
一般来说，变异算子操作的基本步骤如下:
a)对群中所有个体以事先设定的编译概率判断是否进行变异；
b)对进行变异的个体随机选择变异位进行变异。
遗传算法导引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。
基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下:
基因位下方标有*号的基因发生变异。
变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。
终止条件
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。
[编辑本段]遗传算法-求解算法的特点分析
遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点：
a)搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。
b)搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。
c)采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。
d)对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。
[编辑本段]术语说明
由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：
一、染色体(Chronmosome)
染色体又可以叫做基因型个体(indivials),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。
二、基因(Gene)
基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。
三、基因地点(Locus)
基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position)，有时也简称基因位。基因位置由串的左向右计算，例如在串 S＝1101 中，0的基因位置是3。
四、基因特征值(Gene Feature)
在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。
五、适应度(Fitness)
各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。
[编辑本段]参考资料
1.《计算机教育》第10期 作者：王利
2.遗传算法——理论、应用与软件实现 王小平、曹立明着
3.同济大学计算机系 王小平编写的程序代码

参考资料
1. 中新网：英13岁少女患家族遗传怪病 满脸皱纹像老人，2010年01月27日

http://www.chinanews.com.cn/gj/gj-ywdd2/news/2010/01-27/2094204.shtml

H. 自适应遗传算法在求解TSP问题中的应用研究

利用基于分区搜索的自适应遗传算法求解TSP问题
江金龙,薛云灿,冯骏
为了提高用遗传算法求解旅行商问题(TSP)的收敛速度,结合自适应算子和父子竞争策略等优化思想,提出了基于分区搜索的自适应遗传算法.该算法将整个搜索区域分成若干个较小的搜索区域,先进行局部搜索,在得到局部较优的基因组合后,再进行全区域搜索,不但提高了遗传算法的收敛速度,而且改进了变异算子的操作性能.通过TSP问题的求解表明,基于分区搜索的自适应遗传算法是一种稳定、高效的优化算法.
【作者单位】：河海大学计算机及信息工程学院;河海大学计算机及信息工程学院;河海大学计算机及信息工程学院 江苏常州213022九江学院电子工程学院;江西九江332005;江苏常州213022;江苏常州213022
【关键词】：遗传算法;分区搜索;旅行商问题
【基金】：湖北省自然科学基金资助项目(2004ABA018);河海大学常州校区创新基金资助项目(2005B002-01)
【分类号】：TP18
【DOI】：cnki:ISSN:1009-1130.0.2005-03-001
【正文快照】：
1分区搜索自适应遗传算法的基本思想旅行商问题(Traveling Salesm an Problem,TSP)是指旅行商从某城市出发,在遍历N个城市后又回到出发点,且每个城市只经过一次,求旅行商行程最短的问题[1].TSP是一个N P难题,其可能的路径数目随城市数N的增加呈指数型增长.如果是对称TSP问题,则共有0.5(N-1)!种可能路线,如果是非对称TSP问题,可能的路线还会加倍.许多学者运用遗传算法的不同控制方法来求解TSP的最优解[2-3],但简单遗传算法(Sim ple G enetic A lgorithm,SG A)的收敛速度慢,且易陷入局部最优解.如果能找到某些局部优良的基因组合(…
推荐 CAJ下载 PDF下载
CAJViewer7.0阅读器支持所有CNKI文件格式，AdobeReader仅支持PDF格式

Solving Traveling Salesman Problem by the Adaptive Genetic Algorithm Based on the Regional Search
JIANG Jin-long1;2;XUE Yun-can1;FENG Jun1(1.College of Computer & Information Engineering;Hohai Univ.;Changzhou 213022;China;2.College of Electronic Engineering;Jiujiang Univ.;Jiujiang 332005;China)
To increase the convergence speed of the genetic algorithm in solving the traveling salesman problem(TSP),combined with adaptive operators and competitive strategy between parents and their children,an adaptive genetic algorithm based on the regional search is proposed. This algorithm divides the global space into regional space and makes the regional search first. The global space search is carried out based on the better local gene sequences obtained from the regional search,so as to improve the search speed. Moreover,this algorithm improves the mutation performance at the same time. The TSP simulations show that the improved algorithm is a steady and efficient optimal search method.
【Keyword】：genetic algorithms;regional search;traveling salesman problem(TSP)

I. 遗传算法研究进展

遗传算法^{［56，53］}研究的兴起是在20世纪80年代末和90年代初期，但它的历史起源可追溯到20世纪60年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法的研究特点是侧重于对一些复杂的操作的研究。虽然其中像自动博弈、生物系统模拟、模式识别和函数优化等给人以深刻的印象，但总的来说这是一个无明确目标的发展时期，缺乏带有指导性的理论和计算工具的开拓。这种现象直到20世纪70年代中期由于Holland和De Jong的创造性研究成果的发表才得到改观。当然，早期的研究成果对于遗传算法的发展仍然有一定的影响，尤其是其中一些有代表性的技术和方法已为当前的遗传算法所吸收和发展。

在遗传算法作为搜索方法用于人工智能系统中之前，已有不少生物学家用计算机来模拟自然遗传系统。尤其是Fraser的模拟研究，他于1962年提出了和现在的遗传算法十分相似的概念和思想。但是，Fraser和其他一些学者并未认识到自然遗传算法可以转化为人工遗传算法。Holland教授及其学生不久就认识到这一转化的重要性，Holland认为比起寻找这种或那种具体的求解问题的方法来说，开拓一种能模拟自然选择遗传机制的带有一般性的理论和方法更有意义。在这一时期，Holland不但发现了基于适应度的人工遗传选择的基本作用，而且还对群体操作等进行了认真的研究。1965年，他首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。

1967年，Bagley在他的论文中首次提出了遗传算法（genetic algorithm）这一术语，并讨论了遗传算法在自动博弈中的应用。他所提出的包括选择、交叉和变异的操作已与目前遗传算法中的相应操作十分接近。尤其是他对选择操作做了十分有意义的研究。他认识到，在遗传进化过程的前期和后期，选择概率应合适地变动。为此，他引入了适应度定标（scaling）概念，这是目前遗传算法中常用的技术。同时，他也首次提出了遗传算法自我调整概念，即把交叉和变异的概率融于染色体本身的编码中，从而可实现算法自我调整优化。尽管Bagley没有对此进行计算机模拟实验，但这些思想对于后来遗传算法的发展所起的作用是十分明显的。

在同一时期，Rosenberg也对遗传算法进行了研究，他的研究依然是以模拟生物进化为主，但他在遗传操作方面提出了不少独特的设想。1970年Cavicchio把遗传算法应用于模式识别中。实际上他并未直接涉及到模式识别，而仅用遗传算法设计一组用于识别的检测器。Cavicchio对于遗传操作以及遗传算法的自我调整也做了不少有特色的研究。

Weinberg于1971年发表了题为《活细胞的计算机模拟》的论文。由于他和Rosenberg一样注意于生物遗传的模拟，所以他对遗传算法的贡献有时被忽略。实际上，他提出的多层次或多级遗传算法至今仍给人以深刻的印象。

第一个把遗传算法用于函数优化的是Hollstien。1971年他在论文《计算机控制系统中的人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。实际上，他主要是讨论了对于二变量函数的优化问题。其中，对于优势基因控制、交叉和变异以及各种编码技术进行了深入的研究。

1975年在遗传算法研究的历史上是十分重要的一年。这一年，Holland出版了他的着名专着《自然系统和人工系统的适配》。该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schemata theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。直到这时才知道遗传操作到底在干什么，为什么又干得那么出色，这对于以后陆续开发出来的遗传操作具有不可估量的指导作用。

同年，De Jong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展进程中的一个里程碑，这是因为他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论迄今仍具有普遍的指导意义。

进入20世纪80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显着提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。

随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习（Genetic Base Machine Learning），这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其他智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用。五是遗传算法和进化规划（Evolution Programming，EP）以及进化策略（Evolution Strategy，ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，既同遗传算法具有相同之处，也有各自的特点。

随着遗传算法研究和应用的不断深入和发展，一系列以遗传算法为主题的国际会议十分活跃。从1985年开始，国际遗传算法会议，即ICGA（International Conference on Genetic Algorithm）每两年举行一次。在欧洲，从1990年开始也每隔一年举办一次类似的会议，即 PPSN（Parallel Problem Solving from Nature）会议。除了遗传算法外，大部分有关ES和EP的学术论文也出现在PPSN中。另外，以遗传算法的理论基础为中心的学术会议有FOGA（Foundation of Genetic Algorithm）。它也是从1990年开始，隔年召开一次。这些国际学术会议论文集中反映了遗传算法近些年来的最新发展和动向。

J. 遗传算法第一次提出来是在什么文献中

《搜索、优化和机器学习中的遗传算法》。

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法的基本运算过程如下：

（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

（2）个体评价：计算群体P(t)中各个个体的适应度。

（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

（6）终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。