遗传算法改进

❶ 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（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的变化范围加大。

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

❷ 遗传算法执行策略的改进的具体方法（详细）

GA最典型的应用之一是解决行商问题，行商问题是这样的：
已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？

GA的思路是，先随机排序产生n条路线，这些路线当然长短不一，然后从中选出路径最短的若干条路线（优胜劣汰），再基于他们产生新的路线（杂交），同时引入一些新的路线（防止最初的基因不好，怎么遗传都产生不了精英），当然，还要保留其中最短的那条（那可是目前来说最nb的精英哦），再取其中最短的若干条路线（优胜劣汰）。。。。一直到我们最nb的精英基本上不能更好为止。整个过程符合进化论观点。

GA是不保证结果最优的，但按照性价比的观点来说，它通常能在较短的时间内获得一个较优结果。

http://www.longen.org/e-k/GA.htm
http://www.wikilib.com/wiki/%e9%81%97%e4%bc%a0%e7%ae%97%e6%b3%95 （这个比较详尽^_^）

很遗憾，这两天国外网站访问不了，不然可以帮你分析个例程

❸ 怎样解决遗传算法的局部最优问题

这个看看遗传算法的专着吧。
局部收敛，就是所谓的“早熟现象”是遗传算法的一个很让人头疼的问题。对应的措施，我举个例子，可以是提高变异算子的变异概率。变异算子是跳出局部收敛的重要操作算子，当然，遗传算法有很多的改进类型。这里不多说了，我介绍本书，叫《MATLAB遗传算法工具箱及应用》，雷英杰，西安电子科技大学出版社

❹ 关于遗传算法的疑惑！请高人指点！非常感谢！ 模拟退火遗传算法和免疫遗传算法哪个改进的效果好

这些算法的本质都是随机搜索，带有随机性，对参数依赖程度还是比较强的，所以出现结果时好时坏也是正常的。
至于这些算法的比较，你可以查查相关的论文。特别是首先提出该改进算法的论文，不过要注意，国内的论文的实验结果可信程度还是值得怀疑的。作者往往为了“证明”其算法的优势，只列举那些对算法效果有利的实验结果，不好的结果经常不列出来。所以你看到别人说什么算法好，但你自己用的时候却没发现该算法的优势也是正常的。

❺ 遗传算法的优缺点

优点：

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

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

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

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

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

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

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

缺点：

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

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

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

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

(5)遗传算法改进扩展阅读

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

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

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

❻ 染色体个数的多少对遗传算法优化的结果是否有影响

自适应遗传算法

上回文说到基于误差梯度下降的BP网络算法容易陷入局部极小，通常的改进方法先使用遗传算法生成比较好的权重值，再交给神经网络训练。

遗传算法随着进化的进行，其选择率、交叉算子、变异率应该是动态改变的。

编码方式

在使用BP网络进行文本分类时，大都是采用实数编码，把权值设为[0,1]上的实数，这是因为要使用权值调整公式要求权值是实数。但是在使用遗传算法优化这些权值时，完全可以把它们编码为整数。比如设为[1,64]上的整数，一个权值只有64种选择，而[0,1]上的实数有无穷多个，这样既可以缩小搜寻的范围，同时也加大了搜寻的步长。毕竟BP网络中很多个极小点，使用遗传的目的只是在全局找个一个比较优的解，进一步的精确寻优交给BP神经网络来做。

选择算子

在进化初期我们应该使用较小的选择压力，以鼓励种群向着多样化发展；在进化后期个体差异不大，适应度都很高，这时应增大选择压力以刺激进化速度。可以使用模拟退火(SA,simulated annealing)来决定选择率，即我们以一定的概率来接收不好的个体：

这是模拟退火的原始表达式，意思是说在金属退火的过程中，其能量在降低（<0），我们以的概率接收本次变化，显然当温度T越低时，接收概率越大，温度T越高时，接收概率越小，k是常数。对应到遗传算法，就是当种群平均适应值越低时，接收劣等个体的概率越高，当种群平均适应值越高时，接收劣等个体的概率越小。

另外M.Srinivas提出当群体适应度比较集中时，使交叉概率增大；当群体适应度比较分散时，使交叉概率减小。种群适应度分散与否通过最大、最小和平均适应度来衡量。

选择算子是保证遗传算法能找到近优解的唯一手段，当染色体唯度很高时，遗传算法很难找到较好的解。这是因为最开始生成的初始种群适应度都极其的低，个体之间（适应度）差异不大，如果使用锦标赛选择法则跟随机选择无异，即使使用赌轮法选择到最优个体的概率会大增加，但是最优个体也不比最劣个体好到哪儿去，最优个体也不含有优良的基因片段。所以对于高维数据，在进化初期主要靠交叉进行全局搜索来搜寻较优的个体。

交叉算子

交叉实际上就是在进行全局搜索，所以遗传算法不过是穷举算法的一个变种。在进化初期，种群多样性高，采用单点交叉就可以获得较广的搜索空间；在进化后期，个体差异不大，需要采用多点交叉，或者有人采用变异交叉点的方法。

当发现种群的适应度操持不变时，可能已经进入了局部最优，应该变异交叉点，大步跨出当前的小山峰。

由于要保留精英个体，所以交叉要以一定的概率进行。随着进化的进行，交叉率应逐渐降低趋于某个值，以避免算法不收敛。

变异算子

直观上对好的个体应施以较小的变异率，对劣等个体应施以较大的变异率。

当发现种群的适应度在降低时应增大变异率。

另外M.Srinivas提出当群体适应度比较集中时，使变异概率增大；当群体适应度比较分散时，使变异概率减小。种群适应度分散与否通过最大、最小和平均适应度来衡量。

下面的代码是用遗传算法来为BP网络寻找比较好的初始解。但是遗传算法根本就没有起到作用，因为我的神经网络输入层1000个节点，隐藏层20个节点，这就2万个权值了，也就是说染色体的长度在2万维以上，用遗传算法根本就找不到较优解，它始终是在随机地遍历，一点儿没有想“进化”的意思。

❼ matlab遗传算法改进bp神经网络

你提供的代码是一个基本的BP神经网络训练过程。一般都是用GA训练，之后再用改进动量法继续训练，直至最后达到目标。

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(indivial)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。