混沌遗传算法研究及其在地震子波提取中的应用毕业论文.doc

混沌遗传算法研究及其在地震子波提取中的应用毕业论文目 录第1章 前言11.1 课题背景及研究意义11.2 研究现状21.2.1 地震子波估计的研究现状21.2.2 优化算法在子波提取中的研究现状21.2.3 混沌遗传算法的研究现状21.3 本文的主要研究内容3第2章 遗传算法的关键技术及不足之处分析52.1 标准遗传算法52.2 遗传算法的关键技术62.2.1 编码方式的多样化72.2.2 初始种群的产生82.2.3 选择算子82.2.4 交叉算子102.2.5 变异算子112.3 遗传算法的不足之处及其解决途径122.4 本章小结15第3章 混沌遗传算法研究163.1 混沌优化163.1.1 混沌优化的基本思想163.1.2 混沌优化的理论依据183.1.3 混沌优化的研究现状223.2 用于优化的混沌映射223.2.1 用于优化的混沌映射223.2.2 猫映射与logistic、tent映射的比较243.3 基于猫映射的混沌遗传算法253.3.1 混沌遗传算法的步骤253.3.2 计算机仿真实例293.3.3 算法的性能评价293.4 本章小结32第4章 混沌遗传算法在MA模型下的地震子波提取应用334.1 地震褶积模型334.2 地震子波MA模型描述344.3 累积量拟合目标函数的建立354.4 MA模型参数估计374.4.1 仿真数据实验374.4.2 实际数据实验414.5 本章小结42第5章 混沌遗传算法在ARMA模型下的地震子波提取应用435.1 相关分析法识别模型435.2 地震子波ARMA描述455.3 累积量拟合目标函数的特点465.4 ARMA模型参数估计465.4.1 仿真数据实验475.4.2 实际数据实验485.5 模型定阶与参数估计485.6 本章小结52总结与展望53参考文献54攻读硕士学位期间取得的学术成果58致谢59i中国石油大学（华东）硕士学位论文第1章 前言1.1 课题背景及研究意义石油是经济赖以运转的血液，当今世界的主要能源，对现代社会的发展有深远的影响。获取比较准确的地下油气藏分布信息在油气田开发过程中起着先导作用。地震勘探技术是目前最为有效的油气勘探与开发的地球物理方法。随着油气勘探开发的不断深入，对地震勘探技术的要求越来越高，高分辨率地震勘探需要高频率、高信噪比、宽频带的地震波。对于地震勘探技术而言，提高地震子波分辨率的方法为反褶积和地震记录子波零相位化。而地震子波的精确提取是应用反褶积和地震记录零相位化来提高地震记录分辨率1的前提。因此，地震子波的精确提取直接影响着地震记录分辨率的高低。地震子波提取(估计)作为地震资料反褶积处理、地震波阻抗反演及正演模拟的基础，其提取精度直接影响着后续地震资料处理和地震资料解释的可靠性和准确性。高阶统计量不仅可以保持信号的相位信息，而且能够压制任意加性高斯噪声2，因此被广泛地用于混合相位的地震子波提取中。基于累积量拟合法的子波提取能够充分地利用所有的地震记录数据，因此它在高精度、高分辨率的子波提取中得到了广泛的应用。但是累积量拟合法子波提取所建立的拟合优化模型极为复杂，传统的优化算法很难求解。因此，非线性优化算法的选取对于高效率、高精度的子波提取是至关重要的。遗传算法具有快速随机的搜索能力，用群体取代个体进行搜索，具有内在的并行性；搜索过程中使用评价函数，过程简单易行；使用概率转换机制，具有随机性，可扩展性，容易与其他优化算法相结合。但是遗传算法在寻优的过程中没有及时利用网络的反馈信息，算法的收敛速度受到一定的限制，算法对初始种群的选择具有一定的依赖性，易“早熟”收敛，因此融合混沌优化算法进行改进。混沌运动具有遍历性、随机性、规律性等特点，混沌运动的遍历性即混沌运动能在一定范围内按其自身的规律不重复地历经所有的状态；混沌对初始值的变化极为敏感；混沌的这些特点能够作为一种优化机制来维持种群的多样性，从而弥补遗传算法易陷入局部最优、收敛速度慢的缺陷。同时混沌变异能够对个体进行启发式地操作，结合了混沌机制的遗传算法计算效率高，易跳出局部解进行全局寻优。1.2 研究现状1.2.1 地震子波估计的研究现状地震子波信号的提取分为确定性子波提取方法和统计性子波提取方法。确定性子波提取方法指的是利用密度测井和声波测井资料，计算反射系数系列，结合井旁地震由褶积理论求出地震子波，其中假设地震参数需要由测井等方法得到3,4,5。其优点是不需要对反射系数序列的分布做任何假设，就能得到较为准确的地震子波，但该方法由于需要测井资料及震源信息计算反射系数，应用范围受到限制。统计性子波提取方法利用信号处理技术对有限的地震数据记录进行统计处理，充分利用地震数据记录的幅值、相位、频率等各种信息提取子波。其优点是不需要测井资料，也可以得到地震子波的估计，但缺点是需要对地震资料和地下反射系数序列的分布进行假设(最小相位、零相位、最大相位)。实际上地震子波往往是一种混合相位子波6，因此简单的基于自相关的统计性子波提取方法理论并不能得到准确的结果。1.2.2 优化算法在子波提取中的研究现状根据Tugnait7提出的实际数据四阶累积量与子波MA(Moving Average滑动平均)模型的四阶矩拟合来估计混合相位子波的方法，可建立一个非线性多参数多极值优化问题的目标函数，对该目标函数进行求解便可得到MA模型描述下的子波。lazear G D8首先利用梯度下降法实现了子波估计，该方法无须对子波相位做任何假设，并能有效地消除具有高斯分布的地震噪声，可望得到较为准确的地震子波，但由于目标函数的求解较为困难，且实际提取过程中子波的待定参数过多，该方法提取子波的精度及运算效率均有待提高。以后的学者主要在优化算法方面对其进行了改进：D.R.Velis和T.J.Ulrych9、M.D.Sacchi使用模拟退火算法进行了相关研究，但其控制参数的选择一般比较困难。尹成、周冀10等从随机化全局搜索出发，利用混沌映射的特点，结合遗传算法的杂交算子以及小领域的局部搜索，提出综合的混沌优化算法，但是寻优速度有待于进一步提高。路荣亮、张海燕11将改进的遗传算法与改进的粒子群算法相结合，在地震子波提取中有较好的应用。袁三一、陈小宏12提出基于群智能的非线性全局优化算法，提取的子波效果明显。王荐、朱仕军13通过混合蚁群算法进行地震子波提取，提高了子波的分辨率。1.2.3 混沌遗传算法的研究现状雷德明14最早将遗传算法与混沌算法混合，对优化对象进行多维实数编码，并用混沌优化算法作为变异算子，引导种群的进化，提高了运算效率和运算精度。李亚东、李少远15在分析了遗传算法与混沌优化方法优缺点的基础上，提出了一种新的混沌遗传优化组合方法，该方法能克服混沌优化在大范围内失效的缺点，并能提高遗传算法的局部搜索能力和搜索精度，同时证明该算法能以概率1收敛到全局最优值。之后，章敬东、刘小辉16等人分析了遗传算法和混沌优化方法的理论机制，研究了两者的集成方式，将二者进行智能集成，给出了混沌遗传优化算法，寻优速度有很大提高，有效地解决了遗传算法搜索在接近全局最优解时速度减慢甚至陷入局部最优的问题。1.3 本文的主要研究内容本文各章的主要研究内容归纳如下：第一章 概括性地指出了课题的背景及研究意义，介绍了地震子波估计的研究现状以及混沌遗传算法在子波提取(估计)中的研究现状，最后说明了本文中各个章节的内容安排。第二章 简要地介绍了标准遗传算法，指出了优化问题中标准遗传算法存在的缺陷，这些局限性是本文需要加以研究和改进的方面。重点对遗传算法的关键技术(编码技术、选择算子、交叉算子、变异算子)进行了研究。最后分析了遗传算法的不足之处，对其解决途径进行了探讨，并引出了对遗传算法改进方法的研究。第三章 对混沌优化算法进行了详细地介绍，从理论上对混沌分布的特点如初始条件的敏感性、遍历性进行了分析，比较了logistic、tent、cat映射的混沌分布特性，重点对遗传算法的算子进行了设置，并且引入混沌变异来维持种群的多样性，最后综合遗传算法和混沌优化算法的特点提出了一种适合于多维多峰值函数寻优的非线性优化算法基于猫映射的混沌遗传算法。运用多个多维经典的标准测试函数，从算法的收敛速度、收敛稳定性和收敛质量上验证了算法的性能及算法的有效性。第四章 概括性地介绍了地震褶积模型，通过对地震子波MA模型的引进，对MA模型描述下的高阶累积量拟合法子波提取进行了研究，构建了累积量目标函数，分析了目标函数的特点，并且将基于猫映射的混沌遗传算法运用于仿真实验和实际地震资料中，结果表明提取子波与真实子波间有好的相似性，从而验证了本文提出的非线性优化算法的实用性。将自适应免疫遗传算法、改进的遗传算法以及本文提出的算法对子波进行提取，本文算法在进行拟合过程中累积量拟合误差小；相同的收敛条件下，提取子波所用时间少；反映了本文算法的优越性和稳健性。第五章 运用相关分析法对ARMA模型进行识别，对ARMA模型描述下的地震子波提取进行了研究，首先通过仿真和实际数据实验，利用本文算法和改进的遗传算法对子波进行提取，比较得出本文算法的优越性和实用性。然后将模型定阶与参数估计相结合，在模型准确定阶的情况下，对模型参数进行了优化，实现了以尽可能少的参数来描述更加精确的子波的效果。59第2章 遗传算法的关键技术及不足之处分析基于累积量拟合的地震子波提取最终归结为一个多维多峰值目标函数的非线性优化问题。遗传算法是一种结合了有向和随机17两种能力的通用算法，该算法既能够对参数向量整体进行全局随机搜索，又能够对单个参数向量进行深度搜索，因此被广泛用在函数优化领域。但是遗传算法在面对规模较大且非常繁琐的优化问题时，无法保持种群的多样性，容易“早熟”收敛，算法易陷入局部最优。本章对遗传算法的编码方式、选择算子、交叉算子、变异算子等关键技术进行了系统的分析和研究，分析了遗传算法在优化问题中存在的弊端，并指出了其解决途径。2.1 标准遗传算法遗传算法是一种自适应全局优化概率搜索算法，它在模拟生物的遗传和进化过程中形成的。美国Michigan大学的Holland17教授最早提出遗传算法，60年代，Holland对自然和人工自适应系统研究形成了一个较完整的理论和方法。70年代，De Jong将模式定理与数值计算相结合，为遗传算法的发展奠定了基础。80年代，Goldberg对其进行了归纳总结并应用于实践。遗传算法的基本思想18是：遗传算法是一种基于群体选择的随机搜索算法，从代表给定问题的可行解的种群开始搜索，种群是由遗传编码的个体构成，个体则是染色体中带有特征的实体。染色体由多个基因组合而成。譬如：双眼皮的特征就是由染色体中控制双眼皮的某种基因组合决定的。因此，遗传算法的首要操作19就是实现从表现型到基因型的编码工作。初始种群生成后，借用生物界进化中“适者生存”的竞争机制，以目标函数为依托来评价个体的适应能力。经过“优胜劣汰”的淘汰机制，逐代产生问题的近似解。之后，运用遗传算法的交叉和变异操作，产生代表新的解集的种群替换原来的近似解。该过程能够使产生的后生代种群对环境的适应能力更强，具有较强的鲁棒性。反复循环此过程直到找到最优的个体。末代种群的个体经过解码，即为问题的全局最优解。一般把具有以下六个操作的遗传算法称为标准遗传算法。(1)编码：DNA中遗传信息在一个长链上按一定的模式进行排列被称为遗传编码，可以看作从表现型到遗传子型的映射。在实际问题中，遗传编码20就是把给定问题的可行解从基因型空间(解空间)转移到表现型空间(遗传算法的搜索空间)的方法。(2)初始群体的产生：按随机方法由计算机从可能解中产生给定数量的个体(编码串)，即进化的第一代。(3)适应度评估：遗传算法中使用适应度函数来度量群体中个体或解的优劣，即个体在优化算法中达到最优解的优良程度。(4)选择：从当前群体中选择出优良个体作为父代，为下一代繁衍子孙。选择是将遗传搜索引导到搜索空间中有前途的域中。(5)交叉：为了群体中的优良特性得到充分组合，使配对个体彼此交换部分信息，重组而生成新的个体。(6)变异：以一定的概率随机地改变群体中个体的某些基因的值，个体变异的目的是产生新的特性，以免陷入局部最优。标准遗传算法的流程图见图2-1。是否满足优化准则最佳个体选择交叉变异是否计算适应度产生初始种群图2-1 标准遗传算法的流程图Fig 2-1 The flow chart of standard genetic algorithm2.2 遗传算法的关键技术标准遗传算法21存在以下缺陷：(1)初期的未成熟收敛，后期的搜索迟钝；(2)群体规模，交叉概率，变异概率等重要参数的设置；(3)遗传算法的交叉和变异算子，一个用来执行随机搜索并试图探索局部最优解以外的区域，而另一个则用来执行局部搜索并试图寻找到更好的解。因此简单的交叉和变异算子协调不完整，会直接地影响算法的性能；(4)局部搜索能力比较弱，收敛速度比较慢；(4)单一的群体更新方式难以维持种群的多样性和收敛性之间的平衡。因此有必要对遗传算法的编码方式、选择算子、交叉以及变异算子等关键技术进行分析，使其协调工作，更有效地发挥遗传算法的性能。2.2.1 编码方式的多样化参数编码：编码方式22可以分为二进制编码、实数编码、整数或字母排列编码、一般数据结构编码等。二进制编码是将某个变量值代表的个体表示为一个。二进制编码的优点在于编码、解码操作简单方便，遗传操作便于实现，但是由于“Hamming”悬崖的存在，二进制编码对于函数优化问题存在严重的缺陷。Hamming悬崖22指的是表现型空间中距离很小的个体对可能有很大的Hamming距离。例如，个体对01111111111和10000000000是表现型空间中相邻的点，但它们却在基因型空间具有最大的Hamming距离。由杂交和变异实现翻越Hamming悬崖的可能性非常小。因此，二进制编码在上述情况下无法维持表现型空间中点的位置。再者，在从基因型到表现型的转化过程中存在一定的误差，不能较好地描述所求解的问题。实数编码23能够较为有效地解决函数的优化问题。由于实数编码基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易从传统优化方法中借鉴好的技巧来形成有效的遗传算子。使用二进制编码对多维多峰值的连续函数进行编码时，会无形中增加问题的复杂度。例如，二进制编码存在连续函数离散化时的映射误差，同时不能直接反映出所求问题的本身结构特征。为了克服这些缺点，人们提出实数编码方法，即用实数表示个体的每个基因值。实数编码遗传算法24的优点：(1)直接使用实数作为染色体参与遗传操作，无需特定的编解码过程，使算法更容易实现，提高了算法的运行速率。(2)用实数编码可以消除二进制编码的“Hamming”悬崖。(3)实数编码遗传算法使用的交叉、变异算子适用于不同的进化方法。(4)使用实参数进行编码，使得变量可以取大的定义域甚至是使未知的定义域成为可能。(5)实数编码遗传算法可以利用连续变量函数的渐变性(变量值的微小变化所引起的对应函数值的微小变化)，它使得遗传算法具有局部调节的能力。(6)使用实数编码的染色体，其繁殖新个体的方式更加灵活。如何将问题的解编码成为染色体是遗传算法使用中的关键问题。研究学者们采用不同的编码方式进一步对遗传算法的性能进行了改进。张喜，张全寿25针对铁路空车流量分配优化问题中求解的复杂性，采用实数编码遗传算法，并结合铁路空车流量分配问题的实例分析验证了算法的适用性和有效性。郑世杰，郭腾飞26等采用混合编码(二进制编码表示载荷作用位置，浮点数编码表示载荷大小)的方法进行载荷识别，提高了计算的效率和精度。2.2.2 初始种群的产生初始种群的产生影响着算法的计算结果和计算效率，初始种群的均匀分布对实现全局最优化有着重要的意义。传统的遗传算法是按预定或随机方法产生一组原始解，这样就可能导致初始种群在解空间分布的不均匀，从而影响算法的性能。可以从以下几个方面解决：(1)混沌序列产生初始种群，利用混沌序列的初值敏感性扩大搜索范围，利用混沌序列的遍历性进行混沌变量的优化搜索，从而减少了数据冗余，保持了种群多样性，有效地解决了局部收敛问题。(2)文献27和文献28将遗传算法均匀设计或正交设计等实验设计方法相结合，使初始种群在解空间内分布均匀，从而使遗传算法能够从好的初始种群出发，均匀地搜索整个空间。(3)王伟伟29等通过对种群及基因位的多样性测度方法的研究，保证了随机产生的个体有较明显的差异，最终使得整个种群不被大量相似的个体所充斥，维持了种群的多样性，从而增加了搜索收敛于全局最优解的可能性。2.2.3 选择算子选择提供了遗传算法的驱动力。如果驱动力过大，遗传搜索将过早地终止；如果驱动力太小，进化过程将变得很慢22。通常在遗传搜索的早期需要较小的选择压力，用来广度地搜索空间，而在算法的晚期则需要较大的选择压力，用来限制空间的搜索。下面介绍几种常用选择算子：(1)按比例的适应度分配，亦称之为轮盘赌选择。轮盘赌选择是一种回放式随机采样的方法。个体被选取的概率为： (2-1)其中M为群体大小，为个体i的适应度。遗传算法随机地进行操作，因此按比例的适应度分配的选择误差较大，进化中好的个体将被放弃。经常将比例选择与排序选择，最优保存策略等相结合。这种方法的基本原则是保证每个染色体在下一代中复制的次数与其期望值相差不大。(2)基于排序的适应度分配。种群按目标值进行排序，适应度仅取决于个体在种群中的序位，而不是实际的目标值。与之相对应的是采用了染色体的排序来确定其生存概率。这种方法避免了比例变换参数的选取。常用的排序方法有线性排序和指数排序。(3)锦标赛选择法30。随机地从种群中选择一定数目个体进行比较，然后将适应度好的个体选做父体，重复此过程完成个体间的选择，直到保存到下一代的个体数目达到预先设定的数目。(4)截断选择法。个体按适应度的优劣进行排序，只有最优秀的个体能够被选作父个体。被选作父个体的百分比为截断阀值，小于截断阀值则不能产生新的个体。最小限度的种群大小一般依赖于选择强度和目标函数的维数，而选择强度又与选择压力、截断阀值、竞赛规模等选择参数有关。因此不同选择方法的行为是有差别的。对于标准遗传算法，由于达到收敛的世代数与选择强度成反比，因此选择强度过高会导致收敛过快，解的质量变差；基于比例选择的适应度分配，实现简单，但是容易引起“早熟”收敛、搜索速度慢等问题；锦标赛选择只能赋予个体离散值；线性排序只允许较小区间值的选择强度；截断选择则倾向于用较好的个体取代较差的个体，并且截断选择比锦标赛选择和排序选择的多样化损失更为严重。因此，根据实际问题采用合适的选择方法是至关重要的。最优保存策略能够有效地防止遗传算法“早熟”收敛，它使得个体不会被交叉变异等遗传操作破坏。但是，它也容易使局部最优个体快速扩散，而不是被淘汰，从而降低了算法的收敛能力。将最优保存策略和其他选择结合使用是选择算子改进的一个重要策略。2.2.4 交叉算子交叉算子因其全局搜索能力而作为遗传算法的主要操作算子。遗传算法通过交叉和变异这对互相配合且互相竞争的操作兼具全局和局部的均衡搜索能力。因此，交叉算子在遗传算法中起着核心的作用。常用的交叉算子31包括：(1)单点交叉。个体编码串中随机设置一个交叉点，在该点交换两个配对个体的部分染色体。如： (2-2) (2-3)(2)算术交叉。如果两个个体进行算术交叉，则交叉后所产生的新个体是： (2-4) (2-5)其中是一参数，若为常数，则称之为均匀算术交叉；若是变量，称为非均匀交叉。(3)单峰正态交叉。假定父代向量表示为A1,A2，子代向量表示为a1,a2，变量数为n，A1,A2之间的距离表示为d1，父代A3与A1,A2之间连线的距离表示为d2，p1为服从正态分布N(0,12)的随机数，pk表示服从正态分布N(0,k2)的随机数，、是常数。子代由下式产生：， (2-6)， (2-7) (2-8) i, j=1,2,., ij (2-9)单峰正太交叉可以保持种群的多样性，但其实现方式比较复杂，从而影响到算法的寻优效率。(4)自适应交叉。遗传算法的交叉概率Pc是影响算法收敛性能的指标。Pc越大，交叉产生个体的速度越快，有利于种群的进化；但是，Pc过大会破坏基因中的优良模式，优良个体就会在种群的进化过程中被破坏；如果Pc过小，会使搜索的效率变小，产生优良个体的速度变慢，生物进化受阻。因此，国内外许多学者对自适应交叉概率进行了设计。(5)基于方向的交叉。这种方法采用目标函数的值来确定遗传搜索的方向。例如，两个父代和产生一个子代： (2-10)其中r是0和1之间的随机数。2.2.5 变异算子变异是选择、交叉外的另一种遗传操作，它对种群进行局部随机搜索。变异算子32可以维持种群的多样性，增加新的搜索空间，改善遗传算法的搜索性能，使遗传算法具有局部的随机搜索能力，以防止出现“早熟”收敛。常用的变异算子包括：(1)基本位变异。一种简单的变异方式，即随机指定某一位或某几位基因座上的基因值做变异。(2)均匀变异。分别用符合某一范围内均匀分布的随机数，以较小的概率替换原编码串中各基因座上原有的基因值。假设有个体，为变异点，取值范围为,，则变异点的新基因值是： (2-11)其中r为0,1，为一符合均匀概率分布的随机数。均匀变异操作特别适合用在遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由的移动，从而增加种群的多样性。(3)非均匀变异。类似于均匀变异，只是它的重点是搜索原个体附近的微小区域。对于给定的父代，若变异点的取值范围为,，则从以下两种方式中随机选择： (2-12)其中，函数(t,y)的形式如下：，r是0,1区间上的随机数，T是最大遗传代数，b是确定非均匀程度的参数。函数(t,y)返回范围0，y中的一个值，当遗传代数t增加时，该值趋向于0。非均匀变异使得遗传算法在初始运行阶段进行均匀搜索，后期运行阶段进行局部搜索，其产生的新基因值比均匀变异产生的基因值更接近原始基因值。所以随着遗传算法的运行，非均匀变异使得最优解的搜索过程更加集中在某一最有希望的重点区域中。(4)高斯变异。该变异操作是用符合均值为，方差为的正态分布的一个随机数来替换原有的基因值。它是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法。其具体实现方法类似于均匀变异。(5)自适应变异。变异概率Pm影响着遗传算法的性能，如果Pm过小，产生新个体的速度慢，不利于种群的进化；如果Pm过大，遗传算法就变为完全的随机搜索算法。采用自适应算子，根据适应度的变化，自适应地调整变异概率的取值，当种群在局部最优趋向成熟时增加Pm的值，而当种群在解空间中发散时减少Pm的值，从而促进算法加速收敛，避免陷入局部最优。Srinvivas33等提出一种自适应遗传算法，Pm能随适应度自动改变，设置如下： (2-13)其中，为群体中最大的适应度值， f为要变异个体的适应度值，为每代群体的平均适应度值，变异概率Pm根据k1，k2的取值进行自适应调整。从式(2-13)可以看出，当适应度值越接近最大适应度值时，变异率就越小；当等于最大适应度值时，变异率的值为零。2.3 遗传算法的不足之处及其解决途径遗传算法与其他搜索算法相比具有以下优点：(1)遗传算法的智能搜索能力强。遗传算法在解决实际问题时，随着编码方式、初始种群的产生及选择、交叉、变异等遗传操作确定后，算法将根据获取的信息进行智能搜索。根据“适者生存”原则，高适应度的个体在进化过程中更加地适应环境。通过交叉及变异操作后，产生的后代种群更加适应环境的变化。进化算法的这种智能学习特征，使个体能够自组织自适应地适应环境。(2)遗传算法的本质并行性。遗传算法的寻优范围是全局搜索，而不是单个个体。遗传算法能在目前所有的并行机及分布式系统上进行大规模的并行操作，并且不会影响搜索效率。遗传算法本身隐含着并行性，它的搜索对象是种群，搜索方式为群组织的搜索。因此遗传算法能够同时搜索它处理的解空间中的多个区域，并且相互交流信息达到最佳的处理效果。(3)遗传算法的搜索方向随着目标函数或者适应度函数而改变，不需要导数或者其他辅助知识。(4)参数编码代替参数个体，便于操作。(5)使用概率转换规则及目标函数进行优化，而不是确定的转换规则。(6)对搜索空间无连续可微的约束条件。遗传算法自20世纪80年代问世以来，在数值优化、结构优化等诸多领域的应用中展示出其特有的魅力，但是遗传算法在进行遗传操作后生成的解空间有可能映射到解集合之外，也就是说，遗传空间的染色体未必都能和集合中的解相对应。存在以下几个方面的不足：(1)传统的遗传算法随机产生初始种群，因为种群多样性问题的困扰而陷入“早熟”收敛，使算法易陷入局部最优。因此如何更好地维持种群多样性是遗传算法需要解决的问题之一。(2)如何设置控制参数使遗传算法的求解精度和求解效率达到最优是遗传算法的难点，目前尚无理论依据进行设置。实际应用遗传算法进行问题求解时，需要经过多次试验才能明确参数的取值范围。标准遗传算法的运行参数包含：M群体大小；T遗传算法的终止进化代数；Pc交叉概率；Pm变异概率。(3)编码是进行遗传操作的首要问题，在遗传算法起着至关重要的作用。因为随着问题的复杂化，以及对高精度的要求不断扩大，要求编码长度越来越长，一个差的编码方法可能使交叉、变异等遗传操作难以实现。但是目前没有一套既严密又完整的指导理论及评价准则设计编码方案。(4)遗传空间中的个体在进行交叉等遗传操作后未能与集合中的解对应。如图2-1所示，虚线反映的映射关系表示交叉操作后生成的染色体为致死个体，它映射到问题解集合的空间外。A1A2B1B2交叉遗传空间解空间图2-2 遗传空间与问题空间的映射关系Fig 2-2 Mapping relation between GA space and problem space遗传算法的完备性与健全性一直受研究学者的关注。国内外许多学者对遗传算法进行了改进，主要表现在：(1)遗传操作中选择、交叉、变异等遗传算子的改进。陈友文34在传统的基于比例选择的适应度分配上提出了一种基于排序的多轮轮盘赌选择算子，在减少随机性产生误差的同时提高了算子的选优能力，从而有效地提高了算法的收敛速度。陈皓，崔杜武35等提出了使用随机分配策略、分阶段调整策略以及自适应进化策略三种策略来实现对交叉点规模的动态调控，从而提高了交叉操作的搜索效率和算法的搜索性能。王杰，马雁36等提出了一种双变异率的改进遗传算法，增加了种群多样性，有效地解决了遗传算法收敛速度慢，易陷入局部最优等问题。(2)适应度函数的改善。遗传算法中适应度函数的设计不当会产生“欺骗”问题。有些问题会对适应度函数加入窗函数，可变系数来使算法达到最佳的性能。(3)遗传算法重要参数的选择。遗传算法需要选择的运行参数主要有编码串长度L，群体大小M，终止代数T，交叉概率Pc，变异概率Pm。这些参数对遗传算法的运行性能影响较大，根据实际问题设置具体参数以达到最佳的优化性能是重点。(4)除了改变遗传算法的基本算子外，将遗传算法与问题的特有知识集成到一起所构成的混合遗传算法是一种求解性能极佳的方法。为寻求复杂多峰函数的全局最优解问题，马西庚37等提出了自适应免疫遗传算法，将免疫机制与遗传算法相结合，在保持种群进化稳定性的同时，加快了进化速度，提高了算法收敛结果的精度，在一定程度上避免了演化过程过早收敛现象；加入记忆库，减少系统资源的占用，提高了算法的整体性能。冯冬青，郭艳38结合遗传算法与神经网络来实现神经网络的训练和知识库的建立，准确高效地评定了地下水质。高阳，江资斌39结合了遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极值的优点，设计了模拟退火算法，有效地改变了算法的性能。张建中，王庆超40将混合遗传粒子群算法引入混沌系统进行参数估计，有效地克服了“早熟”收敛，提高了算法的全局寻优能力，准确地估计出系统的未知参数。混沌遗传算法是混沌优化和遗传算法的智能集成，它具有两者的优点：混沌优化算法在较小参数空间范围内耗时短的较强搜索能力和遗传算法的全局搜索能力，同时克服了混沌优化算法只能在较小的参数范围内搜索最优值和遗传算法收敛慢的缺点，它可在每个个体(染色体)的附近进行随机扰动，从而进行局部搜索，大大加快了遗传算法的收敛速度和全局寻优能力。本文主要采用这种方法的原理，将其在地震子波提取中的应用进行了研究，并提出了此方法需要改进的地方。2.4 本章小结本章对标准遗传算法及遗传算法的编码方式、初始种群的产生、选择算子、交叉算子以及变异算子等基本操作进行了简单的介绍，分析探讨了遗传算法的不足之处及其性能提高的方法。最后提出一种混沌遗传算法，该算法将混沌优化算法与改进的遗传算法相结合，利用混沌运动“不重复地遍历取值空间内的所有点”的特性来产生初始种群，同时利用混沌变异来保持种群的多样性。本文第三章将详细介绍基于猫映射的混沌遗传算法，并用仿真实验来证明算法的有效性和适用性。第3章 混沌遗传算法研究传统的遗传算法包括改进后的遗传算法，在种群进化的过程中，代与代之间除了通过交叉、变异概率等参数控制外没有必然的联系，采用的是随机的搜索方式。这种搜索方式存在未成熟收敛、易陷入局部最优、收敛速度慢等问题，尤其是在求解多维多峰值函数的非线性优化问题上表现的尤为突出。另一方面，从混沌学的角度来看，生物进化的模式是“随机+反馈”。其中的随机是系统本身的特性，由系统的内部所引起。混沌是系统进化和获得信息的来源。与传统的进化模式相比，这种生物进化模式更接近于真实的生物进化模式。因此引入混沌的遗传算法将会表现出更好的性能。混沌是一种非线性动态，是相对于一些“不动点”、“周期点”特定形式的一种未定形的交融于特定形式间的无序状态。混沌41是自然界中广泛存在的一种非线性现象，充分体现了系统的复杂性。混沌运动具有类似随机变量的杂乱表现，具有随机性；混沌运动能在一定范围内按其自身特性不重复地历经所有状态，具有遍历性；初始条件极其微弱的变化将会引起混沌系统行为的巨大变化，即混沌具有对初始条件的极度敏感性。混沌运动的上述性质可以作为避免陷入局部极值的优化搜索机制，恰好能够弥补遗传算法易陷入局部最优、收敛速度慢的缺陷。因此，我们可以运用混沌的遍历性产生均匀分布的初始种群，也可以运用混沌变异对个体进行启发式的操作，减少了遗传算法的进化代数，能够及早地找到最优解，有效地避免了单纯使用遗传算法所带来的局部收敛和“早熟”收敛问题，本章将混沌优化的思想融入改进的遗传算法42中，提出一种基于猫映射的混沌遗传算法。3.1 混沌优化混沌运动是确定论系统中局限于有限相空间的轨道高度不稳定的运动。正是这种不稳定使系统长时间出现某种混乱性。但是这种混乱性使系统对初始条件有极度的敏感依赖性，能够不重复地遍历空间内的所有点。混沌优化正是运用混沌系统所具备的特性进行参数寻优。本节将对混沌优化的基本思想，理论依据以及研究现状作详细地介绍，为混沌在优化领域的应用打下基础。3.1.1 混沌优化的基本思想混沌优化的基本思想：利用混沌映射产生的混沌变量具有随机性、遍历性和规律性的特点，将混沌变量映射到优化变量的取值空间，利用混沌变量进行混沌搜索。基于混沌的动态搜索过程分为以下两个阶段43：(1)利用确定性迭代公式产生混沌序列的遍历性轨道，对整个解空间进行广度的搜索。满足设定终止条件时，搜索过程中的最佳个体已接近所求问题的最优解，从而开始第二阶段的搜索。(2)以第一阶段得到的结果作为基础，施加幅度小的混沌扰动进行局部区域的细搜索，直到满足算法的终止条件为止。其中，施加的幅度小的混沌扰动可以是混沌变量，或者是基于均匀分布或柯西分布或高斯分布的随机变量，或者是按梯度下降产生的偏置值。混沌优化算法（以logistic映射为例）的基本步骤为：设置用于载波的混沌变量logistic映射的表达式为： (3-1)其中是控制参数，时系统完全处于混沌状态。设一类连续对象的函数优化问题为： s.t. (3-2)Step 1：算法的初始化。令，利用混沌对初始值敏感的特点，对式(3-1)中的分别赋予个具有微小差异的初值，得到个不同轨迹的混沌变量。Step 2：一次载波的引入。通过式(3-1)将转换成混沌变量，运用式(3-3)将混沌变量的变化范围“放大”到优化变量相应的取值范围。 (3-3)Step 3：用混沌变量进行迭代搜索。令，计算相应的性能指标。令，；if ， then ；else if ， then放弃， k=k+1。Step 4：引入二次载波。如果经过Step 3的若干步搜索都保持不变，则按式(3-4)进行第二次载波，其中为调节常数，可以小于1，为遍历区间很小的混沌变量，为当前最优解。反之，返回Step 3 (3-4)Step 5：用二次载波后的混沌变量继续迭代搜索。令，计算相应的性能指标if ， then ；else if then放弃 。Step 6：如果满足终止判据则停止搜索，输出最优解、；反之返回Step 5。3.1.2 混沌优化的理论依据1.混沌对初始条件的敏感性混沌现象表明，初始条件的微小差别将最终导致根本不同的现象。像logistic映射这样的系统，初始条件的微小差别使得迭代一定次数后的结果已经无法说清楚了。也就是说，初始值的信息经过若干次迭代后已消耗殆尽，结果已经与初始值没有什么关系了，这就是敏感依赖于初始条件的性质，是非线性系统的固有特性。混沌对初始条件的敏感依赖性决定了混沌的随机性，保证了混沌能够进行大范围的搜索。混沌具有伸长和折叠41的性质，这是形成敏感依赖于初始条件的主要机制。伸长是指系统内部局部不稳定所引起的点之间距离的扩大；折叠是指系统整体稳定所形成的点之间距离的限制。经过多次的伸长和折叠，轨道被搅乱了，混沌现象由此产生。混沌对初值的敏感性是指初值发生微小的变化，系统运动的行为会产生巨大的差异。图3-1中曲线表明虽然x取值相差1.0e-7，即，但是迭代10多次后两个序列便完全不一样了。利用这点可以扩大搜索范围，保持种群多样性，避免局部最优。图3-1 混沌映射的初值敏感性Fig 3-1 Sensitivity of chaos mapping initial values2.混沌的遍历性混沌映射f(x)的遍历性44是指对于每个可积函数y(x)和几乎所有的初始值x0都有： (3-5)式中，r(x)是轨道的分布密度，定义为，即对时间的平均等于对相空间状态的平均。表示的n重复合。下面给出logistic映射的遍历性解释，首先引入一个定理：定理1伯努利移位映射a： (3-6)三角帐篷映射： (3-7)则。证明：由映射(3-6)和映射(3-7)的性质知：或，因此有：(1)时，。(2)时，十进制下表示为 (3-8)其中，由式(3-6)和式(3-8)知 (3-9)根据条件和式(3-9)，得出 (3-10)根据式(3-8)知，式(3-10)知，故 (3-11) (3-12)综上所述， (3-13)利用定理1证明映射的遍历性：二进制下表示任意实数： (3-14)十进制下表示,取任意初值,根据证明的式(3-13)得出： (3-15)由已得到的式(3-14)和式(3-15)可知： (3-16)式(3-16)表明，从(0,1)内的任意数出发，序列(从出发点的轨道)，中有无穷多项与的距离小于任意小的数。即：从出发点的轨道可以逼近(0,1)中的任意点到精度无穷多次，映射可以遍历区间0,1,所以映射具有遍历性。引入变换： (3-17)则有： (3-18)式(3-18)等价于映射，因此logistic45映射具有遍历性。同时，猫映射与logistic映射彼此之间可以相互转换，具有拓扑共轭46性质，说明两者具有相同的性态，为猫映射具有作为优化算法混沌序列的前提条件。混沌运动的遍历性也就是指混沌变量能在一定的范围内按其自身规律不重复地遍历所有状态，分别以=0.001和为初始迭代500次，如图3-2所示，途中的点表示空间中的一点。图3-2 混沌映射的遍历性Fig 3-2 Ergodicity of chaos mapping3.线性变换后混沌变量的性质由于混沌变量在经过线性变换后得到的变量仍然保持了遍历性、随机性等混沌系统的特征，因此混沌变量在搜索过程中避免了陷入局部极值，实现了全局性的混沌搜索。3.1.3 混沌优化的研究现状混沌优化方法由于其搜索过程完全按照混沌运动自身的规律进行，因此混沌优化方法的全局搜索能力较强，获得最优解的可能性较大。现有的混沌优化方法包括：(1)基于logistic映射的混沌搜索方法李兵43最早将logistic映射引入到混沌优化算法中，用类似载波的方法将混沌状态引入到优化变量中，利用混沌变量进行搜索。搜索效率高，而且结构简单，使用方便。胡云昌47等提出了一种加速混沌优化方法，在基于logistic映射的混沌优化算法的基础上，通过调节细化系数，不断地缩小优化变量的搜索区间，重新构造优化变量的取值空间，来提高算法的运行速率。(2)基于logistic映射的混沌优化算法与其他算法的相结合Choi48等将混沌机制与最速下降法进行函数优化，使得搜索过程同时具有混沌优化的全局搜索能力和最速下降法的细搜索能力的优点，提高了算法的优化性能。徐宁49等将禁忌搜索引进到混沌优化算法中，搜索过程吸收了混沌运动的特点和禁忌搜索算法的“记忆”功能，使得算法容易跳出局部最优解，提高了算法的搜索效率。(3)基于非logistic映射的新型混沌优化方法秦红磊50等将tent映射引入到混沌优化算法中，并且结合共轭梯度法进行寻优，加快了算法的搜索速度，缩短了时间，提高了寻优效率。单梁51等进一步研究了tent映射的混沌结构，将基于tent映射的混沌搜索算法与模式搜索相结合，实现了快速寻优，提高了算法的运算效率。修春波52等提出一种具有双混沌机制的优化算法，利用两种不同的混沌机制进行独立并行搜索，同时结合两者搜索的最优点的距离情况来缩小搜索空间，提高了算法的搜索速度和搜索效率。3.2 用于优化的混沌映射混沌映射在混沌优化中起着重要的作用。混沌优化利用的是混沌映射的遍历性、初值敏感性等特点。本节介绍了三种用于优化的混沌映射，比较了它们的混沌分布特性。3.2.1 用于优化的混沌映射从分岔理论来看logistic映射的混沌特性，分岔是研究非线性方程解的数目如何在参数变化中发生突变。logistic映射是通过倍周期分岔达到混沌的，图3-3为logistic映射的分岔图，由图3-3可以看出，的取值接近4时，的取值范围分布基本在整个0到1的区域。logistic映射表达式为： (3-19)其中图3-3 logistic映射的分岔过程Fig 3-3 The branched process of logistic mapping当前已有的混沌优化方法多数采用logistic映射作为混沌序列发生器，而由logistic映射产生的混沌序列的概率密度服从两头多、中间少的切比雪夫分布(如图3-4所示)。这种分布特性会严重影响算法的全局搜索能力和效率。图3-4 logistic映射分布图Fig 3-4 Chaotic distribution of logistic mapping为了克服logistic映射搜索效率低的特点，秦红磊，单梁50,51等用tent映