地球物理资料非线性反演方法讲座(八)——量子遗传算法.pdf
《地球物理资料非线性反演方法讲座(八)——量子遗传算法.pdf》由会员分享,可在线阅读,更多相关《地球物理资料非线性反演方法讲座(八)——量子遗传算法.pdf(8页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第 5卷 第 6期 2 0 0 8年 1 2月 工程 球物 季 旅 CHI NE S E J 0URNAL OF ENGI NEE RI NG GE oPHYS I CS VoI 5,No 6 De C,20 O8 文章编号:1 6 7 2 7 9 4 O(2 0 0 8)O 6 0 6 3 5 0 8 地球物理资料非线性反演方法讲座(八)量子遗传算法 亘于速传异法 罗红明 ,王家映,师学明 朱培 民 (1 川 庆钻探工 程有 限公 司 地球物理 勘探公 司,成都 6 1 0 2 1 3;2 中国地质大 学 地 球物理 与空 间信 息学 院,武汉 4 3 0 0 7 4)摘 要:虽然线性反演理
2、论目前已经相当成熟,但由于其方法本身比较依赖初始模型,而且容易陷人局部极 小,在实际应用中常常显得“力不从心”。量子遗 传算法 QG A(Q u a n t u m G e n e t i c Al g o r i t h m)以量子理论 为基 础,通过量子位编码 和量子旋转门更新种群来寻找全局最优,加快 了搜索速度,具有更强 的全局寻优能力。通 过对量子遗传算法 内在机理的分析表明,QG A 的寻优质量和效果 明显优于传统遗传算法。关键词:量子遗传算法;地球物理反演;全局寻优;遗传算法 中图分 类号:P 6 3 1 文献标 识码:A 收 稿 日期:2 0 0 8 1 l 一1 9 Le c
3、t ur e o n No n Li ne a r I n ve r s e M e t ho ds i n Ge o phy s i c a l Da t a(8)Qu a n t u m Ge n e t i c Al g o r i t h m a n d I t s Ap p l i c a t o n i n Ge o p h y s i c a l I nv e r s i o n L u o H o n g mi n g ,W a n g J i a y i n g。,S h i Xu e mi n g ,Z h u P e i mi n (1 Si c h u a n Pe t
4、 r o l e u m Ge o p h y s i c a l Pr o s pe c t i n g Co mp a n y o f C NPC Ch u a n q i n g Dr i l l i n g Engi n e e r i ng Co mpan y Li mi t e d,Ch e n gdu 61 0 21 3,Chi n a;2 I n s t i t u t e o f Ge o p h y s i c s a n d Ge o ma t i c s,C h i n a Un i v e r s i t y o f Ge o s c i e n c e s,Wu h
5、 a n 4 3 0 0 7 4,C h i n a)Ab s t r a c t:Th i s pa pe r pr e s e nt s a ne w i n v e r s i on a l g o r i t h m,q u a nt um g e n e t i c a l go r i t h m,whi c h a d op t s t he q u bi t c hr o mos o me s a s pr e s e nt a t i o n s a nd u pd a t e s t he po p ul a t i o n u s i n g q ua n t u m r
6、 o t a t i on g a t e,t o a c c e l e r a t e t he s e a r c h s p e e d,t o i mpr ov e c o nv e r ge nt e f f i c i e n c y,a n d t o ge t a b e t t e r g l o b a l o p t i mi z a t i o n Ha v i n g t e s t e d s o me s y n t h e t i c a n d r e a l d a t a s e t,t h i s p a p e r s t r o n g l y s
7、 h o ws t h a t t h e o p t i mi z a t i o n q u a l i t y a n d e f f i c i e n c y o f QGA a r e b e t t e r t h a n t h e t r a d i t i o n a l ge ne t i c a l g or i t hm Ke y wo r d s:qu a n t u m g e n e t i c a l g or i t hm;g e o p hy s i c a l i nv e r s i o n;gl o b a l o pt i mi z a t i o
8、 n;g e n e t i c a l g or i t h m 作者简介:罗红明(1 9 7 7一),男,博士,现在四川石油管理局地球物理勘探公 司技术发展 中心 工作 演理论与应用研究,E ma i l:L u o h o n g mi n g 2 0 0 1 s o h u c o rn 王家映(1 9 3 7一),男,教授,博士生导 师,主要研究方 向为电磁法和地球物理反演理论。,主要从事地球物理资料处理与反 Ema i l:j y w a n g c u g e d u c n 6 3 6 工 程 地 球 物 理 学 报(C h i n e s e J o u r n a l o
9、f E n g i n e e r i n g Ge o p h y s i c s)第 5 卷 1 引 言 2 O世纪 8 O年 代,量 子 图灵 机 1 的 提 出为 量 子计算 奠定 了基础。然而直 到 1 9 9 4年,美 国贝尔 实验 室的 P e t e r W S h o r提 出了一个 利用 F o u r i e r 变换 量子 并行 优势 的快 速、混 合 的 因子 分 解 算 法 ,才改 变 了量子 的并行 计算 能 力 受 到 了限 制 的局面。这个算法 提供 了一种利用 量子计算 机 在 多项式 内完成大数 因子分解 的可能。这是 一个 重 要的进展,从 此 量 子计
10、 算技 术 开 始对 一 些领 域 产 生了非 常现实 的影响。1 9 9 7年,Gr o v e r 提 出“量子搜 寻算法”3“,利 用这个算法,可以通过大约、N次尝试就能从 N 个 对象 中找出所 要 找 的对象,而 经 典 的查 找过 程 要 比较每一 个 对象 平 均 需要 进 行 N 2次 尝试 才 有较 大 的 可 能 找 到所 需 对 象。该 算 法 的用 途 很 广,可 以寻 找最大值、最小值、平均值 等,也 可 以最 有 效地攻击 密 码体 系,具有 极 高 效率。因此量 子 算法 以其算 法稳定,收敛迅 速等优 点,而得 到人们 的重视 。早期 的量子并 行算法在 演绎规
11、 划的应 用 中已 显 示 了巨大的发展潜 力。最 先的尝试 是遗传 算法 中算 子模仿 量子行 为的量 子衍 生遗传算 法 。虽 然 这个算 法并不 是 真正 基 于量 子 的,但 预 示着 基 于量子 的量 子遗传算 法优 于经典 的遗 传算法。后 来 的两个尝试 虽 然显 示 了量 子 遗传 算法 的可 能,但 量子模 式的强加 约束削 弱了演绎模 式 的并 行优 势。量子 遗 传算 法【9 Q GA(Qu a n t u m Ge n e t i c Al g o r i t h ms)是 近 年来 发 展 的一 种 基 于量 子 计 算 原 理的优化 方 法。它 以量子 理 论 为基
12、 础,采用 量 子位(q u b i t)概率编码 来表 示染 色 体,通 过 不 断更 新 的量子旋 转 f-。(Qu a n t u m R o t a t i o n G a t e)的 作 用来更新 和 优化 种 群,达 到 搜索 的 目的。具 有 种群 规模小,收敛迅 速和全局 寻优能力 强等特 点,并在求 解组合 优化 问题 中取得显 著成效。2 量子遗传算法 的反演实现 2 1 量子遗传算法基本原理 遗 传算法(Ge n e t i c Al g o r i t h m)是模 拟达 尔文 的遗传选 择和 自然淘 汰的生物进 化过程 的一种搜 索最优解的方法。遗传算法是从代表问题可
13、能潜 在的解集 的一个 种群(p o p u l a t i o n)开始 的,而一个 种群则 由经过基因(g e n e)编码的一定数 目的个体(i n d i v i d u a 1)组 成 每 个 个 体 实 际 上 是 染 色 体(c h r o mo s o me)带有 特 征 的 实体。染 色体 作 为 遗 传物 质的主要 载体,即多个基 因的集合,其 内部表 现(即基 因型)是某 种基 因组合,它 决 定 了个 体形 状 的外 部表 现。因此,在一 开 始需 要 实现 从 表现 型到 基因型 的映射 即编码工作。由于仿 照基 因编 码 的工作很复 杂,我们 往往简化 为二进制、浮
14、点数 或符号等编码,初代种群产生之后,按照适者生存 和优胜 劣汰 的原理,逐 代(g e n e r a t i o n)演化产 生 出 越来越好的近似解,在每一代,根据问题域中个体 的适应度(f i t n e s s)大小选择(s e l e c t i o n)个体,并借 助 于 自然 遗传 学 的遗 传算 子(g e n e t i c o p e r a t o r s)进行 杂交(c r o s s o v e r)和 变 异(mu t a t i o n),产 生 出 代表新的解集的种群。这个过程将导致种群像 自 然进化 一样 的后 生 代 种 群 比前 代 更 加适 应 于环
15、境,末 代种群 中 的最优 个 体经 过解 码(d e c o d i n g),可 以作为 问题 近似最 优解。对于地球 物理 反演 问题,传 统 的遗 传 算 法将 待反 演 的参数,如波 阻抗,地层 厚度,视 电阻 率进 行基 因编码,特定 的二 进制 码 串(基 因)表示 反演 参数 确定 的取 值,不 同的 染色 体就 构 成 了一 个种 群。而在量子遗传算法中,染色体采用量子位编 码,每 个量子 位的编码 值是量 子位取 O(或 1)的概 率幅,所 以该 量子位 码 串(基 因)只表 示反 演 参数 的可 能的取值。不 同的量子位染 色体 同样 构成一 个种 群。在传 统 的遗 传
16、算法 中,种群通 过选择、杂 交和 变异来保 证全 局 寻优 的成功,而 量子 遗 传算 法只需 要用量 子旋 转 门就 可 以完 成 种群 的更 新,所 以量子旋转 门是量 子遗传算 法研究 的重 点。在量子力 学领 域,粒子 的轨 道 对应 不 同 的离 散能级,粒子通 过 吸收 或 释放 能量 在 不 同能 级 的 轨道上跃 迁。一个两 态(T wo s t a t e)量子位 的量 子态(Q u a n t u m S t a t e)只有 l 0 和 i 1 两 种,表示 0 和 1的两 种状 态。由于量 子 的叠加 性,一个 任意 量子位 可以 由 0或 l以及 两种状 态叠加表示
17、,即 I g r 一 a l O +p I 1 (1)且满 足 l a l 十1 口l 一 1 (2)其 中 和 分 别 是 0 和 f 1)的概 率 幅,即该 任意量 子态 l 0 的概率为 J a J,J 1 的概 率为 I 口 J。记量子位的概率幅为 a,相位=a r e t a n(Of),(-r 2 玎 2 )。在 Q GA中,用量子位串 代替经典方法的染色体基因,每个量子位用量子 第 6期 罗红 明 等:地球物理资料非线性反演方法讲座(八)量子遗传算法 6 3 7 态的两个 概率幅来 编码,表示该量 子位是处 于“0”和“1”的叠加 态。这样,对于 个量子位,则其可以用概率幅 编码
18、表示 为 工 1 m=L r l r 2 r r 计l r m j 一。斗 (3)_ 8 8 2 8 p 一 8 同样满 足,l+l I 一1,i 一 1,2,并 且相应 的相 位 可 以表 示 为 9 5 一a r c t a n(a )。用 1 7 2 个量 子位来描 述大小 为 的种 群,也 可表示 为 一 r r+1 一(4)其中,r l I,表示种群中第i 个个体的第J 个 L J 量子位 的概率 幅。选 用量子 旋 转 门 G来 更 新 种 群 中的 每个 量 子位,从 而达到 更新整个 种群 的 目的,即 r c o s 一 i n 7 r 一l s i n e c o s J
19、其 中,为与量子位 相位有 关 的旋转 角,为 一k*,(a j,)(6)式 中,k为 收敛控 制 系 数,厂(a ,)为 第 i 个 个体 的第 J个量 子位 的优 化搜索 函数。当然,为 了适应地球 物理反 演多参数、多极值 的特 点,我们对 搜索策 略进行 了修改,使 该方法更 易 于应用。如 果收 敛控 制 系数 忌取 值 过大,就使 得搜 索的 网格 偏 大,从 而影 响到量 子 旋 转 门的搜 索 网格,最终容 易 导致 量子 位 收敛 过 快 而 出现早 熟现 象,搜索 陷入 局部 极小 值,反之,如 果控 制 系 数 k 取 值过小,就会 由于搜索 网格太小,使得 收敛 太慢甚
20、 至 出现不收敛情 况。特别 在地球 物理反 演 中,一方面 由于反演 的非唯一性 存在,另一方 面 由 于反演 参数一 般 比较 多,所 以收敛控制 至关重要。这 里,采用 自适 应调 整收敛控制 系数 k的方案,即 k一 2 7 r e x p(一 C*t ma x t)(7)其中,c为调控常数,0 J l 时,表示最优解 的相 位角大 于 当前 解 的相位 角,当前 解 应该 向角 度增 大 的方 向旋转,即逆时 针旋转,以 向最优解 方 向搜 索,故 优化搜索 函数(a ,)应 取 十 1,反 之 应为 一1。同理 推 出其他 情况。这样,就可 以用(5)式 的量子旋 转 门引导 和更
21、 新 当前 第 i 个个 体 的 第 J个 量 子位 的概率 幅,使 其 向全局最 优解方 向搜索。更新算 法为(f+1)一 G(i,J,)*()(8)式 中,t 为 当前进 化代 数,f;(f)为 当 前代 的第 i 个 个体的第 个量子位的概率幅,G(i,J,t)为当前 代 该量子 位对 应 的量 子 旋 转 门,r (t+1)为更 新 后 的量子位 的概率 幅。表 1 优化搜索函数f(a ,)取值表 T a b l e 1 Op t i o n a l s e a r c h i n g f u n c t i o n f(a,房)2 2 量子 遗传算 法反演 的步骤 根据地球物理反演的
22、特点,结合量子遗传算 法反演 的优势,可 以设 置下列具 体步骤:1)初始 化:根据 反 演参 数 的多 少 以及 问题 的 复杂性来 确定 种群 的大小。在 反演 中,将 种 群大 小 设 定 为反 演参 数 的 0 1 1 0倍,就 可 以保 证 反演 的成 功。根 据 每个 参 数 的范围 可 以设 定 m 个 量 子 位数 来 描 述 所有 参数,就可以建立如前文(4)式所示的种群大小为 n的量子 位种群。其 中 r (一1,2,2;一1,2,)为种 群 中 第 i 个个 体 的第 个 量 子位。在初 始 种 群 中,所 有的 量子位的概率幅元素都取 2 2,表示初始搜 索 以等概率
23、叠加;6 3 8 工 程 地 球 物 理 学 报(C h i n e s e J o u r n a l o f E n g i n e e r i n g G e o p h y s i c s)第 5 卷 2)量子 位测 量:因 为种 群是 用量 子概 率 幅表 示 的,它是 一个不确 定 的状 态。所 以要 通过 测量,把 概 率转 化 为具 体 的 二进 制取值。在这里通 过量子 位 的一个 概率 幅元素 与 一个 随机 数 比较,得到种群 的二进 制表示 厂 6 1 1 I I bz l p o p 一I I b 1 b l 2 b 1 b 2 2 b 2 b 2 6 (9)其 中,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 地球物理 资料 非线性 反演 方法 讲座 量子 遗传 算法
限制150内