子代遗传算法

Ⅰ 基因算法和遗传算法的区别

遗传算法
一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。
Holland创建的遗传算法是一种概率搜索算法，它是利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些组成的进化过程。跗算法通过有组织地然而是随机地信息交换重新组合那些适应性好的串，在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。
遗传算法是一类随机化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来造反染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。
基因算法
一种生物进化的算法,实际上是一种多目标的探索法.能够用于计划与排程.它是非常新的技术,目前,还没有在商业中实际运用.
采用生物基因技术高级算法,处理日益复杂的现实世界,也是人工智能上,高级约束算法上的挑战. 基因算法是一种搜索技术，它的目标是寻找最好的解决方案。这种搜索技术是一种优化组合，它以模仿生物进化过程为基础。基因算法的基本思想是，进化就是选择了最优种类。基因算法将应用APS上，以获得“最优”的解决方案。

Ⅱ 遗传算法是什么

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

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

Ⅲ 请教遗传算法三个问题

1、先交叉 在变异 还是先变异后交叉？
2、选择父代进行交叉的个数是不是2n个？n是种群大小。
3、交叉概率+变异概率=100%？ 还是就没啥关系？
可以这样理解。一般都是顺序选择个体，逐一生成随机数的吧。因为从选择操作上看，种群中个体不存在序，所以没有必要随机选择。
不过交叉后得到的种群还不能称为子代。
2 不是。对于每一父代种群中个体产生一个（0，1）间的随机数，若大于交叉概率，该个体不参与交叉。反之被标记，并于下一个参与交叉的个体进行交叉操作，所生成的两个个体替换父代的两个个体。因而，每一个父代个体可能参与0或1次交叉。
3 两者不存在相加为100%的关系。这是两种不同操作。但是取值组合确实对结果有影响。
以上是根据遗传算法的标准源码给出的，你最好看看遗传算法的标准源码。遗传算法发展至今已有很多改进的方法和新设计的算子，性能较标准源码有不少的提升。

Ⅳ 关于遗传算法

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

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

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

Ⅳ AAXX Aaxy的遗传算法

在这里，A和a是指常染色体，XY是性染色体。XX为女性，XY为男性。
1、AAXX为常染色体显性女性。AaXY 为常染色体杂合男性。
他俩的子女中，AA与Aa进行基因分离与自由组合。后代1/2概率为AA，1/2概率为Aa。同样，性染色体也一样分离。1/2概率为XX，1/2概率为XY。把常染色体和性染色体分开看子代基因型后，各基因型之间也自由组合：AAXX概率为1/2AA*1/2XX=1/4，同理，AaXX，AAXY，AaXY也是1/4。即：AAXX和AaXY的后代，基因型组合为AAXX，AAXY，AaXX，AaXY，比例都是1/4.
2、AaXX为常染色杂合女性， AaXY为常染色杂合男性。
Aa*Aa依据基因分离及自由组合定律，后代中，1/4AA，1/2Aa，1/4aa。性染色体情况和上面一样，1/2概率为XX，1/2概率为XY。同上所述的基因型自由组合：AAXX概率为1/4AA*1/2XX=1/8，AaXX概率为1/2Aa*1/2XX=1/4，AaXY概率为1/2Aa*1/2XY=1/4，AAXY概率为1/4AA*1/2XY=1/8，aaXX概率为1/4aa*1/2XX=1/8， aaXY概率为1/4aa*1/2Xy=1/4。
即：AaXX和AaXY的后代，基因型组合为AAXX1/8，AaXX1/4，AaXY1/4，AAXY1/8，aaXX1/8， aaXY1/8。

Ⅵ 遗传算法^[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)，遗传算法的性能较优。

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

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

Ⅶ 遗传算法的一般算法

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法： 繁殖(包括子代突变)
带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。 各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。 这个函数是计算个体在群体中被使用的概率。

Ⅷ 请教遗传算法中解码的问题

应该说所有的遗传算法都得编码、解码，遗传算法是模拟生物遗传和进化过程，交叉是遗传算法的核心操作。交叉过程就是二进制数据之间的运算操作，例如;与，或，异或……编码目的是实现从表现型到基因型的映射，便于遗传操作；然后通过适应度函数选择合适下一代，依次迭代，直到达到合适子代。此时所求的子代还是二进制，因此必须再通过解码将子代映射到表现型。