混合编码遗传算法及其在非线性反演中的应用

1、混合编码遗传算法及其在非线性反演中的应用核心提示：中文摘要：遗传算法中编码机制对交换和变异的搜索能力有重要影响.本文分析了二进制与十进制编码的搜索特点,提出了混合编码遗传算法的技术构想,并结合大变异技术,有效地提高搜索及产生有效基因物质的能力.论文结合地球物理反演问题的非线性特点,应用混合编码遗传算法求解地球物理位场反演问题,取得了良好的效果. 目.中文摘要：遗传算法中编码机制对交换和变异的搜索能力有重要影响.本文分析了二进制与十进制编码的搜索特点,提出了混合编码遗传算法的技术构想,并结合大变异技术,有效地提高搜索及产生有效基因物质的能力.论文结合地球物理反演问题的非线性特点,应用混合编码遗传

2、算法求解地球物理位场反演问题,取得了良好的效果. 目第五课题 (96 - 914 - 05) 、湖北省自然科学基金项目 (02065012) 及国土资源部矿产资源定量预测及勘查评价开放式重点实验室研究基金项目 (MGMR2001 - 9)资助。陈超 ,副教授 ,长期从事地球物理数据处理及软 件开发工作。混合编码遗传算法及其在非线性反演中的应用陈 超 陈家联 余 丰 (中国地质大学地球物理系武汉 430074) 摘 要 遗传算法中编码机制对交换和变异的搜索能力有重要影响。本文分析了二进制与十进制编码的搜索特点 ,提出了混合 编码遗传算法的技术构想 ,并结合大变异技术 ,有效地提高搜索及产生有效基

3、因物质的能力。论文结合地球物理反演问题的非线性特点 ,应用混合编码遗传算法求解地球物理位场反演问题 ,取得了良好的效果。 关键词 遗传算法 混合编码 反演 ( China University of Geosciences , Wuhan , 430074) 1 引 言 遗传算法是模拟自然界生物进化过程的搜索最优解的方法 ,它问世于二十世纪 60 年代 ,由美国密西根大学的教授 J1H1Holland 和他的同事们首次提出。二十世纪 80 年代末 ,D.遗传算法最显著的能力是解决非线性最优化问题 ,其特点可归纳为 :算法不是直接作用在参变量集上 ,而是利用参变量集的某种编码 ;不是从单个点 ,

4、而是从一个点的群体开始搜索 ;仅利用适应值信息 ,无需导数或其它辅助信息 ;利用概率转移规则 ,而非确定性规则。地球科学中的许多问题属非线性 ,尤其是地球物理反演问题 ,近年来国内外学者们在不断努力尝试应用遗传算法求解地球物理反演问题 27 。但由于这些问题非线性程度高、情况复杂 ,如地球物理反演的多解性、地质变量及参数分布和函数表达的不确定性等 ,传统 (或标准) 的遗传算法在解决这些地学问题时往往不能取得预想的效果。另一方面 ,遗传算法也存在自身的弱点 ,如“早熟”问题等。“早熟”是指群体过早地趋于局部最优而不是全局最优 ,它是阻碍遗传算法发展的一个最大障碍。此外 ,搜索效率低也是影响遗传

5、算法应用的一个主要问题。本文针对地球物理位场反演问题的特点 ,提出了混合编码结合大概率变异技术的遗传算法 ,在提高搜索效率方面 ,取得较好的效果。 2 编码机制对遗传算法搜索能力的影响 遗传算法是利用参数编码来进行的 ,编码是遗传算法的基础。通常用于遗传算法的码制有两种 ,即二进制和十进制。关于二进制编码和十进制编码在搜索能力方面的特点 ,有不少学者做了许多理论上的探讨 ,如文献 1 对二进制与十进制编码在搜索能力方面进行了分析和模拟。这里我们首先回顾一下十进制和二进制的编码过程。将十进制参数 z 表示成 z = zmin + k?,其中为分辨力 ,k 0 ,N为整数且 N = int (zm

6、ax - zmin) / ,这里 int ?表示取整数。编码前要预先确定参数的定义域 zmin ,zmax 和分辨精度,参数由另一种量化形式即整数 k 来表示。把由 m 个参数组成的个体视为一个基因串 ,其中每一个元素或基因均为十进制整数。二进制编 码则需要预先确定编码位长。对参数 z a ,b ,若按位长 L 进 2004 年 3 月 Computer Applications and Software Mar1 ,2004转载行编码 ,参数分辨力则为= int (b - a) / (2L - 1) ,z 的可能值为 z = a + k,k 0 ,1 , ?,2L - 1。把由 m 个参数组

7、成的个体视为各参数二进制码构成的基因串 ,其中每一个元素或基因均为二进制数 (0 或 1) 。211 交换操作搜索能力分析对于十进制编码 ,假设群体中个体数目为 n ,xit 表示第 t 代的第 i 个个体 ,i (1 ,2 , ?,n) ,个体的基因数目 (串长) 为 m ,即有 m个整数构成 ,xit Rm ,xit 可表示成 m维行向量 xit = xi (1)t ,xi (2)t?xi (m)t 。这样第 t 代群体 Xt 可表示成一个 n m 阶矩阵 Xt = x1t x2t ?xnt T。若初始群体 X0 = x10x20 ?xn0 T 中所在个体互异 , 即 : 0 xj0 i

8、j i ,j (1 ,2 , ?,n) (1) 且任意两个个体的基因互异 ,即 : 0 xj (k)0 i j i ,j (1 ,2 , ?,n) k (1 ,2 , ?,m) (2) 交换所产生的新个体的集合 D 中的数目 TD 为 :对于二进制编码 ,假设上述问题中每个基因实数用 L 位二进制数表示 ,每个个体 xit (BI) mL ,BI 0 ,1 ,这样个体的基因数目 (串长)为 mL ,个体 xit 可表示为 mL 维的行向量 ,第 t 代群体为 B ,B 中个体的数目 TB ,则有 :可以证明1 ,当交换分别在 L ,2L , ?, (m - 1) L 时 ,与十进制码交换位置相

9、同 ,可能的新个体数目与十进制编码相等 ,即体数的可能性将大于 TD。当 L 越大 ,群体规模 n 越大 ,TB 与 TD的差异就越大。新个体集合规模越大 ,交换操作的搜索能力越强。可见 ,就遗传算法中占主导地位的交换操作而言 ,二进制码的交换操作比十进制码搜索能力强。遗传算法的变异操作是针对个体基因串上某一位基因进行的。在十进制码中 ,变异是对选定的基因 (整数)进行 (在其定义域内随机选出一个整数取代) ,显然这种变异搜索可遍历参数定义域全空间。在二进制码中 ,变异是对选定的基因 (0 或 1) 进行 (取其反值代替) ,它只改变某一参数基因段中的某一位。对于 用位长为 L 的二进制码表示

10、的参数 ,其可以有 2L 种不同的取值。由于二进制码决定了变异只改变码串中 1 位 (在此仅讨论单点变异问题) ,实际上变异后参数值的变化只有 L 种可能 ,仅占所有可取值的 L/ 2L ,与 L 位二进制码串所能表达数值的范围差别甚远 ,而且 L 越大 ,这种差别也越大。例如 ,对于 L = 4 的码串 (1011) 2 = (11) 10 ,变异后可能的数为 4 个 ,即 (101 0) 2 = (10) 10 , (10 01) 2 = (9) 10 (1 111) 2 = (15) 10 , (0011) 2 = (3) 10 . 而该码串所有可能的取值有 16 个 ,则变异搜索 率为

11、 (4/ 16) 100 % = 25 %。若 L = 8 ,变异搜索率仅为 3 %。可见二进制码的变异搜索存在较大的盲区 ,其变异操作搜索能力是很有限的。 分析 对群体的部分个体进行交换和变异操作是遗传算法的精髓 ,群体在进化过程中在不断搜寻有效基因物质 (即最优解的参数) ,当群体不含某些有效基因物质时 ,就要求遗传过程能够源源不断地产生新的基因物质。十进制编码的交换操作是在两“个体”中的参数之间进行 ,通过参数的交换形成两个新“个体”,此过程中并不产生新参数 ,如同两个向量间元素交换而不产生新元素一样 ,其产生新参数的概率为零。二进制编码的交换操作则是在两“个体”的二进制基因串之间进行

12、,通过部分基因段的分割与互换 ,形成的两个新“个体”,同时也可能 (具有较大概率) 产生出新的参数。对于变异操作 ,无论十进制编码还是二进制编码 ,总是能产生新物质的 ,而十进制编码产生有效基因物质的可能性要比二进制编码更大一些。二进制编码的交换操作具有较强的搜索能力 ,而十进制编 码变异操作的搜索范围更大。若将两者结合起来 ,把两种编码 机制引入算法进行不同码制的基因操作 ,显然可改善遗传算法的搜索性能。因此 ,我们提出了混合编码遗传算法 ( Hybrid En2混合编码遗传算法的基本要点在两种编码并行。HEGA 的实现过程是 ,首先对所有参数进行二进制编码 ,形成个体基因串 (或称染色体)

13、 。除进行变异操作外 ,染色体始终保持二进制码 形式 ,所有其它基因操作均按二进制码进行。当某个参数所对应的码段被确定要进行变异时 ,则先将该参数转换成同精度的十进制码 ,然后对该基因进行随机变异。最后再将变异后的新 参数按同精度逆变为二进制码。例如 ,假设某参数的二进制码 为 (1101101) 2 ,其十进制数值为 (109) 10 ,从 0109 之间随机挑选一个整数 (假设) 52 作为变异后的参数值 ,然后将其转换为二进制码 (0110100) 2 。从上面参数变异前后的二进制码结构上看 ,在第 1、3、4、7位上都发生了变化 ,即一次十进制码变异操作相当于四次二进制码变异操作。实现

14、参数的十进制与二进制互换的计算程序并不复杂 ,可通过位操作技术来实现11 。事实上 ,用十进制编码进行变异时 ,对于某参数定义域内一个确定的值来说 ,能被搜索到的概率并不高。因此 ,应该考虑设置较大的变异概率或同一基因接受多次变异以产生更多新个体 ,保证新的有效基因物质不断涌现。混合编码遗传算法的流程由图 1 示。 图 1 混合编码遗传算法流程 第 3 期 陈超等 :混合编码遗传算法及其在非线性反演中的应用 17位场数据反演是地球物理反演问题的一个方面 ,其过程是将理论模型计算出的异常值与实测异常值相比较 ,根据其差异对模型参数进行修改 ,如此反复迭代直到满足要求为止 ,最终确定一个最佳地质体

15、模型作为反演问题的解。这类问题一般具有非线性性质 ,传统的做法是首先把它们转化为线性问题 ,利用求解线性问题的方法去解非线性问题 ,如梯度法、最小二乘法、马奎特法等。尽管非线性问题线性化是一条有效的途径 ,但也带来了许多的问题。首先 ,由于它是把非线性问题近似表达成一种线性形式 ,这种表达是有条件有范围的 ;其次 ,对于多元非线性最优化问题 ,线性方法有局限性 ,它属于局部搜索而不是全局搜索 ,这将可能导致求解过程陷入局部极值不能自拔 ;再者 ,一般求解非线性最优化问题都要涉及到目标函数的高次偏导数计算 ,对于复杂形体问题无疑是十分困难的。这些问题不仅普遍存在 ,而且随着问题的非线性程度的增高

16、而愈加严重。对于位场反演 ,通常把观测值与计算值之均方差定义为目 标函数 ,为了保证有足够的信息量 ,一般又是建立超定方程求 解 ,这将使所得到的解具有“圆滑”特征而又缺少分辨能力。另一方面 ,用线性化方法反演 ,其解的准确程度与初值的好坏有 关 ,初值不好 ,容易陷入局部极小 ,导致无法达到全局极小。用 遗传算法求解位场反演问题的优势在于 :它具有全空间搜索能力 ,它不受观测数据的限制 ;它属于群体进化或者说是多点搜索技术 ,不会因个别解的停滞而停止搜索 ;它可以有效地避免陷入局部极值 ,一旦陷入也容易从中“爬”出来。合编码遗传算法策略多边形截面水平柱体可以极好地拟合在走向方向上变化不大的地

17、质体 ,如图 2 所示 ,它是一个常用模拟地质体的模型。方程 (5)给出了参数与异常值g 之间的数学关系 ,即 :g = 2G (xk + 1 - xk) 2 + (zk + 1 - zk) 2 + (xk + 1 - xk) tg - 1xk + 1) (5)式中 xk ,zk 为第 k 个角点的水平坐标和垂直坐标 ,一般情况下这些坐标为待求参数。其中 xn + 1 = x1 ,zn + 1 = z1 ,G为万有引力常数 ,为柱体剩余密度。可见 ,这是一个非线性程度较高的问题。值得注意的是 ,该反演问题在数学上属于不适定问题 ,即方程 (5)左端异常值的微小变化会导致右端参数的剧烈振荡。尽管

18、这不是我们在此所要讨论的问题 ,但以此模型进行试验 ,有益于检验遗传算法的能力。 图 2 多边形水平 柱体截面示意图在下面的试验中 ,我们根据重力异常数据反演求解坐标参数。由于参数的定义域很大 ,为了保证有效地搜索 ,我们采用以下策略 :保证在计算的群体规模不变的前提下 ,采用动态编码技术 ,将进化过程中群体较优和较差个体之间的参数值作为调整定义域的依据 ,逐步将搜索空间收缩到较优的群体周围。取交换操作概率为 Pc = 016018 ,采用多点交换 ,使群体 中的有效基因物质充分实现交换。 自适应调整变异操作概率 Pm = 0. 010. 3 ,采用十进制 码变异 ,参加变异的个体中 ,50

19、%为单次变异 ,50 %为多次变异 , 以提高搜索效率。按 Pt = 0. 010. 03 的概率对较优个体直接复制到下一代。上述遗传操作的父代和子代个体以同等概率进入下一代群体的生存竞争 ,按优胜劣汰原则 ,用适应度轮盘的方法进行筛选 ,保持群体规模不变。当群体中最优个体适应度达到充分高且其群体适应度与其充分接近时 ,终止进化迭代。由于初始群体是随机确定的 ,当全局最优解包含在初始群体之中时 ,进化过程将迅速结束。这种情况是个别的 ,大多数情况下初始群之中不包括全局最优解。因此 ,产生新的有效基因物质的基因操作就变得尤为重要。表 1 中列出了三种理论模型试验的结果 ,其中用混合编码遗传算法反

20、演 ,100 %收敛到全局最优解 ?理论模型真值。而 标准遗传算法收敛极不稳定 ,且收敛速度慢。从搜索到全局最 优解的平均进化次数来看 ,混合编码遗传算法的收敛速度随着 参数数目的增加而降低 ,表明问题复杂程度随着参数数目的增 加而增加。另一方面 ,由于混合编码遗传算法不受初始模型的影响 ,可以搜索到真解 ,理论上这种算法对模型具有较高的分辨能力。表 1 标准遗传算法与混合编码遗传算法执行 20 次结果对比模型 (参数数目) 搜索到全局最优的次数搜索到全局最优的平均进化次数 标准 GA 混合编码 GA 标准 GA 混合编码 GA 三角形柱体 (6) 6 20 131 15四边形柱体 (8) 2

21、 20 1081 263五边形柱体 (10) 0( 3000 次) 20 824 图 3 四边形柱体反演 的初值、局部最优值与真值对比 图 3 展示了“人”字形四边形 水平柱体的真解与初始模型的对比。图中给出了某次运算初始群体中适应度最高的个体模型及其产生的异常 (长虚线) 和迭代过程 中某一局部最优模型及其产生的 异常 (虚线) ,以及真实模型及其产生的异常 (实线) 。显然 ,在繁衍进程中群体逐渐趋向真实模型附近 ,当群体收敛于一局部最优解时 ,虽然计算异常与理论模型异常误差很小 (均方差为 010176) ,但局部最优解的模型形态与真实模型相差甚远 ,欲从该局部极值中“跳出”,一般很难实

22、现。此例还说明用遗传算法反演不仅不受初始模型的影响 ,同时具有很好的垂向分辨力。对于这样的模型 ,一般方法几乎无法完全收敛到真值。 (下转第 69 页) 一段时间后 ,实时库的数据转到历史库中存储 ,实时库中的数据量保持较小 ,查询实时数据速度快。对于不同时期采集到的数据 ,可以用不同的粒度进行存储。较早时期的数据 ,可以用较粗粒度进行存储 ,如 :较早的数据流量数据 ,可以通过计算其较长时间间隔的平均值来代替其实时的数据 ,这对性能数据指标不会造成影响 ,但对减少存储空间非常有效。数据分析的模块的功能是通过获得的网络性能的有关数据 ,对网络性能进行动态分析 ,主要功能有 :包率、流量特性、利

23、用率、响应时间等 ;归分析、概率预测等 ;决策适当的处理方式。数据分析的结果 ,通过一定的方式进行表现。对于统计和性能预测的结果 ,可以采用报表的方式提供 ,以及用可视化图表的方式进行表现。实时事件监控的结果 ,可以通过弹出窗口 ,声音报警来通知管理人员 ,并将结果写入日志中。 图 2 功能模块示意图 议 ,并成为一种事实上的网络管理标准。本文通过阐述如何利用 SNMP进行网络性能实时监控软件开发 ,分析了 SNMP的原理与工作模式以及各模块开发的要点。而掌握 SNMP 的原理与工作模式 ,了解用 SNMP开发网络管理软件中各模块实现的要点 ,对于在实际工作中进行网络管理软件的开发是很有帮助的。 参 考 文 献 现”,小型微型计算机系统,Vol . 22 ,No. 8.