遗传算法的本质

1. 遗传算法、数值算法、爬山算法、模拟退火 各自的优缺点

遗传算法：其优点是能很好地处理约束，跳出局部最优，最终得到全局最优解。缺点是收敛速度慢，局部搜索能力弱，运行时间长，容易受到参数的影响。

模拟退火：具有局部搜索能力强、运行时间短的优点。缺点是全局搜索能力差，容易受到参数的影响。

爬山算法：显然爬山算法简单、效率高，但在处理多约束大规模问题时，往往不能得到较好的解决方案。

数值算法：这个数值算法的含义太宽泛了，指的是哪种数值算法，阵列算法与爬山算法一样，各有优缺点。

(1)遗传算法的本质扩展阅读：

注意事项：

遗传算法的机制比较复杂，在Matlab中已经用工具箱中的命令进行了打包，通过调用可以非常方便的使用遗传算法。

函数GA：［x，Fval，reason］＝GA（＠fitnessfun，Nvars，options）x为最优解，Fval为最优值，＠Fitnessness为目标函数，Nvars为自变量个数，options为其他属性设置。系统的默认值是最小值，所以函数文档中应该加上一个减号。

要设置选项，您需要以下函数：options＝GaOptimset（＇PropertyName1＇，＇PropertyValue1＇，＇PropertyName2＇，＇PropertyName3＇，＇PropertyValue3＇…）通过该函数，可以确定一些遗传算法的参数。

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

遗传操作的交叉算子。

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

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

(2)遗传算法的本质扩展阅读

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

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

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

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

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

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

3. 请问遗传算法和进化算法是什么关系

对主角的形态进行拆分，用数值表示问题解的最小构成单位即表示基因本身，基因串即表示一个个体。以字符串的形态存储耳朵颜色，形状，眼睛颜色形状，皮肤颜色，花纹以及尾巴颜色，形状的相关数据，通过多点交叉，然后产生新的子代个体，接下来进行图像组合，调整每一个部件的相对位置，组合成完整的个体。适应度由玩家交互的次数决定，玩家对自己最喜爱的宠物的关心最多，然后依次递减，适应度最高的个体有大几率繁衍下一代且携带优秀基因（玩家喜爱度更高），实现进化。

4. 用改进遗传算法求取水文地质参数

任广军¹ 张勇²

（1.山东省鲁南地质工程勘察院，兖州272000；2.山东省地矿工程集团有限公司，济南250013）

作者简介：任广军（1972—），男，工程师，主要从事水文地质、环境地质等。

摘要：本文利用非稳定流抽水试验资料，采用改进的十进制遗传算法在计算机上自动优选含水层水文地质参数。该方法同传统上使用的配线法相比较，具有节省时间，减少人工配线误差，所求参数逼真，且能对一些线性、非线性问题求解，具有很高的推广和应用价值。

关键词：遗传算法；随机模拟；含水层；水文地质参数；优选

0 引言

利用改进的十进制遗传算法，根据抽水试验资料来认识水文地质条件、反求水文地质参数是水文地质计算中的基本问题。具体地讲，在探明含水层范围、类型的基础上，建立描述该含水层水流运动模型，利用抽水试验过程中的地下水位变化过程资料来确定水文地质参数。

虽然非稳定抽水试验公式适用条件非常苛刻，但能反映出含水层非稳定流的一些基本特点，还可运用叠加原理解决某些比较复杂的非稳定流问题。此外，作为检验数值方法精确性的重要依据，具有广泛应用和发展前景。

目前，由于非稳定流抽水试验确定水文地质参数的具体实现方法主要有人工配线法或以计算辅助的配线法，但这种方法的效果好坏完全取决于肉眼观察，带有很大的主观性。本文作者选取了一些典型实例，采用遗传算法建立了一种计算机全自动求参的全局优选法，通过与人工配线分析比较，确定本方法计算机求参的高精度与高可靠性。

求取参数是通过实测结果与模型计算结果的最佳拟合（仿真）程度来实现的，参数的精确程度在很大程度上取决于实测资料的精度。

1 遗传算法介绍

生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。

遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。

遗传算法简称GA（Genetic Algorithm），在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。

2 目标函数的确定

通过综合考虑计算程序的运算时间、速度以及含水层的类型，确立利用抽水实测资料和计算资料的拟合程度为目标函数。其计算公式为：

山东省环境地质文集

式中：s_实测为实测抽水试验观测孔的降深；s_计算为计算抽水试验观测孔的降深；NT为计算时段。

3 计算实例及结果分析

3.1 承压含水层地下水降深公式

承压含水层地下水降深公式为：

山东省环境地质文集

式中：S为以固定流量Q抽水时与抽水井距离为r处任一时间的水位降深（m）；T为导水系数；Q为涌水量；W（u）为井函数，是一个指数积分函数：

山东省环境地质文集

式中：u为井函数的自变量，

其中s为承压含水层的储存系数；T为含水层的导水系数；t为时间。

例1：某地区进行非稳定流抽水试验。区域地层剖面是：地表下18～25 m是由含砾粗砂层组成的含水层，其底板由粘土质沉积物组成，18 m以上是粘土、泥炭层。抽水井的过滤器安装在含水层的整个厚度上。观测孔距抽水井30m，观测资料如表1所示。主井作定流量抽水，Q＝788m³/d，抽水接近14小时。试根据观测资料求取水文地质参数。

（1）lgS-lgt配线法所求参数：T_配线＝439m²/d，s_配线＝1.694×10^-4；

（2）S-lgt直线图解法所求参数：T_配线＝450.7m²/d，s_配线＝1.392×10^-4；

（3）计算机所求参数：T＝383.0088m²/d，s＝ 1.78×10^-4。

为更直观地说明上述所求参数的可靠性，由上述参数所求计算降深与实测降深进行比较（图1）。通过比较，进一步确定了计算机求参的高精度与稳定性。承压含水层配线参数与优选参数比较分析：T_配线＝439m²/d，s_配线＝0.0001694；T_计算＝383.0088m²/d，s_计算＝0.0001780。

表1 遗传算法计算水位降深与实测水位降深结果表

图1 计算降深与实测降深比较图

3.2 在有越流补给的承压含水层地下水降深公式

在有越流补给的承压含水层地下水降深公式为：

山东省环境地质文集

式中：u同（3）式；

为越流井函数，本文中

采用数值积分：

山东省环境地质文集

例2：有一无限分布的承压含水层，厚度20m，其底部为绝对隔水的粘土层；上部为弱透水的亚砂土层，厚2m；弱透水层之上为潜水含水层。在承压含水层中有一完整抽水井，抽水时的稳定流量Q＝5530m³/d。距抽水井r＝17.34m处有一观测孔据观测知，在抽水过程中上部潜水的水位不变。抽水层的水位降深值载于表2，试计算含水层水文地质参数。

（1）lgS-lgt配线法所求参数：T_配线＝853.50m²/d，s_配线＝4.20×10^-4；B_配线＝568.50m；

（2）lgS-lgt配线法所求参数：T_计算＝817.19m²/d，s_计算＝4.31×10^-4；B_计算＝482.80m。

为更直观地说明上述所求参数的可靠性，由上述参数所求计算降深与实测降深进行比较（图2）。通过比较，进一步确定了计算机求参的高精度与稳定性。有越流时承压含水层优选参数误差分析：T_配线＝853.50m²/d，s_配线＝0.00042，B_配线＝568.50m；T_计算＝817.1950m²/d，s_计算＝0.00043103，B_计算＝482.798m。

表2 遗传算法计算水位降深与实测水位降深结果表

续表

图2 计算降深与实测降深比较图

3.3 考虑有滞后补给的潜水含水层地下水降深公式

根据博尔顿理论，潜水含水层地下水降深公式计算公式可分为抽水前期、抽水中期和抽水后期。参数优选主要根据抽水前期和抽水后期的资料拟合而得：

山东省环境地质文集

其中D为疏干因子。

抽水前期计算公式：

抽水后期计算公式：同（2）式。

4 结论及不足之处

4.1 结论

通过上述实例计算结果表明：计算结果同人工加以计算机辅助配线法相比较，其计算水文地质参数精度较高，且其参数初值依赖程度较低，对于复杂的线性、非线性及多态性、多峰值问题在全局优化方面有着其他方法所无法比拟的优势，具有很高的推广和应用价值。

4.2 不足之处

遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还存在着各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最优解位置；最后，遗传算法的参数选择尚未有定量方法。对于遗传算法，一是还需要进一步研究其数学基础理论；二是还需要在理论上证明它与其他优化技术的优劣及原因；三是还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。此外，对于地下水渗流问题的数值解反求多类各种水文地质参数虽有成功实例，对于运算速度问题，还存在着相当大的难度。

参考文献

陈崇希，唐仲华.1990.地下水流动问题数值方法.武汉：中国地质大学出版社

陈喜.1998.含水层水文地质参数自动优选方法.工程勘察，（2）

郭东屏.1994.地下水动力学.西安：陕西科学技术出版社

GB 50027—2001 供水水文地质勘察规范

李俊亭，王愈吉.1987.地下水动力学.北京：地质出版社

刘宝碇，赵瑞清，王纲.2003.不确定规划及应用.北京：清华大学出版社

朱国祥，王峰.1999.利用配线法水文地质参数计算机程序简介.工程勘察，（3）

邹正盛，赵智荣.2001.浅析抽水水文地质参数确定中的问题.水文地质工程地质，（3）

5. 遗传算法可以解决哪些问题

遗传算法主要是用来求解最优化问题的。
一般来讲可以求解函数的最大、最小值问题，还可以结合其它一些方法解决（非）线性回归、分类问题等等。

但遗传算法有两个缺点，一是时间长，二是初值的选择会影响收敛的效果。

它的本质，实际上还是随机搜索算法，还是属于所谓的蒙特卡罗式的方法。

6. 什么是遗传算法实值变量

1.2 遗传算法的原理
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
一、遗传算法的目的
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
bi∈{0,1}L (3-84)
给定目标函数f，有f(bi)，并且
0<f(bi)<∞
同时
f(bi)≠f(bi+1)
求满足下式
max{f(bi)|bi∈{0,1}L} (3-85)
的bi。
很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。二、遗传算法的基本原理
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
1．选择(Selection)
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproction)。
2．交叉(Crossover)
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
3．变异(Mutation)
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
遗传算法的原理可以简要给出如下：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。
三、遗传算法的步骤和意义
1．初始化
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
2．选择
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
给出目标函数f，则f(bi)称为个体bi的适应度。以

(3-86)为选中bi为下一代个体的次数。
显然．从式(3—86)可知：
(1)适应度较高的个体，繁殖下一代的数目较多。
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
例如有个体
S1=100101
S2=010111
选择它们的左边3位进行交叉操作，则有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值为0.25—0.75。
4．变异
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
例如有个体S＝101011。
对其的第1，4位置的基因进行变异，则有
S'=001111
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
5．全局最优收敛(Convergence to the global optimum)
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
图3—7中表示了遗传算法的执行过程。

图3-7 遗传算法原理
1.3 遗传算法的应用
遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。
一、遗传算法的特点
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
3．遗传算法有极强的容错能力
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
5．遗传算法具有隐含的并行性
遗传算法的基础理论是图式定理。它的有关内容如下：
(1)图式(Schema)概念
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1x x 0 x x是一个图式。
(2)图式的阶和长度
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
(3)Holland图式定理
低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
二、遗传算法的应用关键
遗传算法在应用中最关键的问题有如下3个
1．串的编码方式
这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
2．适应函数的确定
适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。
3．遗传算法自身参数设定
遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。
群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。
三、遗传算法在神经网络中的应用
遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
1．遗传算法在网络学习中的应用
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
(1)学习规则的优化
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
(2)网络权系数的优化
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
2．遗传算法在网络设计中的应用
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
(1)直接编码法
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
(2)参数化编码法
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
(3)繁衍生长法
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
3．遗传算法在网络分析中的应用
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等

7. 关于遗传算法为什么可以求解npc类问题

遗传算法本质上只是一个优化的比较好的搜索算法， 每个NPC问题都可以通过暴力搜索的方法求解

其通过模拟生物的方式能够在某些情况下有效的避免陷于local optimum，而通常能在较短的时间得到比较好的解， 但遗传算法并不保证在多项式时间解决NPC问题....

8. 你好，遗传算法在网络编码中可以应用吗，还有就是遗传算法和量子遗传算法的本质区别是啥啊求回答啊

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
量子遗传算法是量子计算与遗传算法相结合的产物。
量子遗传算法对于遗传算法的优点，搜索范围更广,适应性更强,效率更高,效果更好。