遗传算法中编码的目的

① 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。

5.4.1 非线性优化与模型编码

假定有一组未知参量

x_i（i=1，2，…，M）

构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界α_i及b_i，即α_i≤x≤b_i，同时可用间隔d_i把它离散化，使

d_i=（b_i-α_i）/N （5.4.1）

于是，所有允许的模型m将被限制在集

x_i=α_i+jd_i（j=0，1，…，N） （5.4.2）

之内。

通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集x_i，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为

地球物理数据处理教程

其中M为未知参数x_i的个数。由此式可见，K决定于每个参数离散化的间隔d_i及其变化范围（α_i，b_i），在大多数情况下它们只能靠先验知识来选择。

一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。

假设地球为有三个水平层的层次模型，含层底界面深度h_j（j=1，2，3）及层速度v_j（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：

h₁=6，h₂=18，h₃=28，单位为10m

v₁=6，v₂=18，v₃=28，单位为 hm/s

按正常的二进制编码法它们可分别用以下字符串表示为：

地球物理数据处理教程

为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距d_i都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：

地球物理数据处理教程

模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。

图5.8 遗传算法实现过程

5.4.2 遗传算法在地震反演中的应用

以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为

地球物理数据处理教程

式中：T_i，0为观测资料中提取出的地震走时；T_i，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；N_A为合成地震数据的个数，它可以少于实测T_i，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据T_j，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h₁＜h₂＜h₃…）在遗传算法中是容易实现的。

对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为

地球物理数据处理教程

式中：P₀（ω_k，v_j）为实测地震道的频谱；ω_k为角频率；v_j为第j层的波速；P_s（ω_k，v_j）为相应的合成地震道；A（ω_k）为地震仪及检波器的频率滤波器，例如，可取

A（ω）=sinC⁴（ω/ω_N） （5.4.6）

式中ω_N为Nyquist频率，即ω_N=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令

地球物理数据处理教程

式中：t_max为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。

用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。

遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率P_s的变化范围加大。

对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。

② 遗传算法的核心是什么！

遗传操作的交叉算子。

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

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

(2)遗传算法中编码的目的扩展阅读

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

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

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

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

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

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

③ 遗传算法的特点

遗传算法具有十分顽强的鲁棒性^{［56，53］}，这是因为比起普通的优化搜索方法，它采用了许多独特的方法和技术，归纳起来，主要有以下几个方面。

遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象进行操作。所谓结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维或二维甚至三维结构形式的对象。这一特点，使得遗传算法具有广泛的应用领域。比如：

①通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化；②通过对集合的操作，遗传算法可实现对规则集合或知识库的精炼而达到高质量的机器学习目的；③通过对树结构的操作用遗传算法可得到用于分类的最佳决策树；④通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理遗传算法可自动构造顺序控制系统。

如前所述许多传统搜索方法都是单点搜索算法，即通过一些变动规则，问题的解从搜索空间中的当前解（点）移到另一解（点）。这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的优解。相反，遗传算法是采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估，更形象地说，遗传算法是并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的风险，同时这使遗传算法本身也十分易于并行化。

在标准的遗传算法中，基本上不用搜索空间的知识或其他辅助信息，无需导数或其他辅助信息，而仅用适应度函数值来评估个体，并在此基础上进行遗传操作。需要着重提出的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的惟一要求是，对于输入可计算出加以比较的正的输出。遗传算法的这一特点使它的应用范围大大扩展。

图7-1 基本遗传算法的框图

遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。在以后的章节中我们将会看到，遗传算法采用概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动。因此虽然看起来它是一种盲目搜索方法，但实际上有明确的搜索方向。

遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题。特别是由于它不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在和单峰等假设，它能从离散的、多极值的、含有噪音的高维问题中以很大的概率找到全局最优解；其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算。遗传算法目前已经在优化、机器学习和并行处理等领域得到了越来越广泛的应用。

④ 遗传算法的中心思想

遗传算法是通过大量备选解的变换、迭代和变异，在解空间中并行动态地进行全局搜索的最优化方法，由于遗传算法具有比较完备的数学模型和理论，在解决很多NP—Hard问题上具有良好的性能。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中选择、交叉和变异构成了遗传算法的遗传操作，参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

(4)遗传算法中编码的目的扩展阅读：

遗传算法注意事项：

用户需要注意遗传算法的优化过程中种群基因的多样性是保障避免陷入局部最优解的重要因素，如果目标函数优化结果过早收敛很可能就是因为种群的多样性不足。

为了保证种群的多样性，其中编码、适应度函数设计尤为重要。

适应度的含义就是字面意思，这个个体是否可以适应环境也即是否满足优化目标指标。因为后续需要根据适应度函数进行自然选择，因此适应度函数和你的目标函数并不需要完全一样。

⑤ 遗传算法的编码方法有几种

常用的编码介绍
1、二进制编码：
（1）定义：二进制编码方法是使用二值符号集{0,1}，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。
（2）举例：0≤x≤1023,精度为1,m表示二进制编码的长度。则有建议性说法：使
2m-1≤1000（跟精度有关）≤2m-1。取m=10
则X:0010101111就可以表示一个个体，它所对应的问题空间的值是x=175。
（3）优缺点
优点：符合最小字符集原则，便于用模式定理分析；
缺点：连续函数离散化时的映射误差。
2、格雷码编码
（1）定义：格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。它是二进制编码方法的一种变形。
十进制数0—15之间的二进制码和相应的格雷码分别编码如下。
二进制编码为：0000，0001，0010，001
1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷码编码为：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）举例：对于区间[0。1023]中两个邻近的整数X1=175和X2=176，若用长度为10位的二进制编码，可表示为X11：0010101111和X12
0010110000，而使用同样长度的格雷码，它们可分别表示为X21：0010101111和X22：0010101000。
（3）优点：增强了遗传算法的局部搜索能力，便于连续函数的局部控件搜索。
3、浮点数(实数)编码
（1）定义：浮点数编码是指个体的每个基因值用某一范围内的一个浮点数来表示，而个体的编码长度等于其决策变量的个数。因为这种编码方法使用的决策变量的真实值，也称之为真值编码方法。
（2）举例：
（3）优点：实数编码是遗传算法中在解决连续参数优化问题时普遍使用的一种编码方式，具有较高的精度，在表示连续渐变问题方面具有优势。
4、排列编码
排列编码也叫序列编码，是针对一些特殊问题的特定编码方式。排序编码使问题简洁，易于理解。该编码方式将有限集合内的元素进行排列。若集合内包含m个元素，则存在m!种排列方法，当m不大时，m!也不会太大，穷举法就可以解决问题。当m比较大时，m!就会变得非常大，穷举法失效，遗传算法在解决这类问题上具有优势。如解决TSP问题时，用排列编码自然、合理。
5、其它编码方式
多参数级联编码等

⑥ 遗传算法的编码方式谁能详细介绍下谢谢

假如你想要编码为x，设x的范围是，二进制编码长度为10，那二进解码方式是：x*（max-min)/1023,这个不用开始编码，开始你可以用rand(n,10)产生n个样本的随机数，然后优化即可。
不是能把“数学模型中的目标函数和每一条约束函数分别编程Matlab里的M文件”，是你用遗传算法就必须要编进去，电脑怎么知道往哪个方向优化是好的，要不把你邮箱留下，我给你发个寻求最大值的遗传算法。

⑦ 遗传算法的运算过程

遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。
遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点：
个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。
遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。
其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法
显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。 在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：
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 新个体 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：
a)实值变异
b)二进制变异。
一般来说，变异算子操作的基本步骤如下：
a)对群中所有个体以事先设定的变异概率判断是否进行变异
b)对进行变异的个体随机选择变异位进行变异。
遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。
基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下：
基因位下方标有*号的基因发生变异。
变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。 当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

⑧ 什么是遗传算法

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：
遗传算法式中x为决策
变量，式2-1为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。
遗传算法的基本运算过程如下：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(indivial)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

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

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