地球物理资料非线性反演方法讲座(八)——量子遗传算法.pdf

第 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)摘 要：虽然线性反演理论目前已经相当成熟，但由于其方法本身比较依赖初始模型，而且容易陷人局部极 小，在实际应用中常常显得“力不从心”。量子遗 传算法 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 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 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 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 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 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 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 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 变换 量子 并行 优势 的快 速、混 合 的 因子 分 解 算 法 ，才改 变 了量子 的并行 计算 能 力 受 到 了限 制 的局面。这个算法 提供 了一种利用 量子计算 机 在 多项式 内完成大数 因子分解 的可能。这是 一个 重 要的进展，从 此 量 子计 算技 术 开 始对 一 些领 域 产 生了非 常现实 的影响。1 9 9 7年，Gr o v e r 提 出“量子搜 寻算法”3“，利 用这个算法，可以通过大约、N次尝试就能从 N 个 对象 中找出所 要 找 的对象，而 经 典 的查 找过 程 要 比较每一 个 对象 平 均 需要 进 行 N 2次 尝试 才 有较 大 的 可 能 找 到所 需 对 象。该 算 法 的用 途 很 广，可 以寻 找最大值、最小值、平均值 等，也 可 以最 有 效地攻击 密 码体 系，具有 极 高 效率。因此量 子 算法 以其算 法稳定，收敛迅 速等优 点，而得 到人们 的重视 。早期 的量子并 行算法在 演绎规 划的应 用 中已 显 示 了巨大的发展潜 力。最 先的尝试 是遗传 算法 中算 子模仿 量子行 为的量 子衍 生遗传算 法 。虽 然 这个算 法并不 是 真正 基 于量 子 的，但 预 示着 基 于量子 的量 子遗传算 法优 于经典 的遗 传算法。后 来 的两个尝试 虽 然显 示 了量 子 遗传 算法 的可 能，但 量子模 式的强加 约束削 弱了演绎模 式 的并 行优 势。量子 遗 传算 法【9 Q GA(Qu a n t u m Ge n e t i c Al g o r i t h ms)是 近 年来 发 展 的一 种 基 于量 子 计 算 原 理的优化 方 法。它 以量子 理 论 为基 础，采用 量 子位(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)是模 拟达 尔文 的遗传选 择和 自然淘 汰的生物进 化过程 的一种搜 索最优解的方法。遗传算法是从代表问题可能潜 在的解集 的一个 种群(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)带有 特 征 的 实体。染 色体 作 为 遗 传物 质的主要 载体，即多个基 因的集合，其 内部表 现(即基 因型)是某 种基 因组合，它 决 定 了个 体形 状 的外 部表 现。因此，在一 开 始需 要 实现 从 表现 型到 基因型 的映射 即编码工作。由于仿 照基 因编 码 的工作很复 杂，我们 往往简化 为二进制、浮点数 或符号等编码，初代种群产生之后，按照适者生存 和优胜 劣汰 的原理，逐 代(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)，产 生 出 代表新的解集的种群。这个过程将导致种群像 自 然进化 一样 的后 生 代 种 群 比前 代 更 加适 应 于环 境，末 代种群 中 的最优 个 体经 过解 码(d e c o d i n g)，可 以作为 问题 近似最 优解。对于地球 物理 反演 问题，传 统 的遗 传 算 法将 待反 演 的参数，如波 阻抗，地层 厚度，视 电阻 率进 行基 因编码，特定 的二 进制 码 串(基 因)表示 反演 参数 确定 的取 值，不 同的 染色 体就 构 成 了一 个种 群。而在量子遗传算法中，染色体采用量子位编 码，每 个量子 位的编码 值是量 子位取 O(或 1)的概 率幅，所 以该 量子位 码 串(基 因)只表 示反 演 参数 的可 能的取值。不 同的量子位染 色体 同样 构成一 个种 群。在传 统 的遗 传算法 中，种群通 过选择、杂 交和 变异来保 证全 局 寻优 的成功，而 量子 遗 传算 法只需 要用量 子旋 转 门就 可 以完 成 种群 的更 新，所 以量子旋转 门是量 子遗传算 法研究 的重 点。在量子力 学领 域，粒子 的轨 道 对应 不 同 的离 散能级，粒子通 过 吸收 或 释放 能量 在 不 同能 级 的 轨道上跃 迁。一个两 态(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以及 两种状 态叠加表示，即 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”的叠加 态。这样，对于 个量子位，则其可以用概率幅 编码表示 为 工 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 其 中，为与量子位 相位有 关 的旋转 角，为 一k*，(a j，)(6)式 中，k为 收敛控 制 系 数，厂(a ，)为 第 i 个 个体 的第 J个量 子位 的优 化搜索 函数。当然，为 了适应地球 物理反 演多参数、多极值 的特 点，我们对 搜索策 略进行 了修改，使 该方法更 易 于应用。如 果收 敛控 制 系数 忌取 值 过大，就使 得搜 索的 网格 偏 大，从 而影 响到量 子 旋 转 门的搜 索 网格，最终容 易 导致 量子 位 收敛 过 快 而 出现早 熟现 象，搜索 陷入 局部 极小 值，反之，如 果控 制 系 数 k 取 值过小，就会 由于搜索 网格太小，使得 收敛 太慢甚 至 出现不收敛情 况。特别 在地球 物理反 演 中，一方面 由于反演 的非唯一性 存在，另一方 面 由 于反演 参数一 般 比较 多，所 以收敛控制 至关重要。这 里，采用 自适 应调 整收敛控制 系数 k的方案，即 k一 2 7 r e x p(一 C*t ma x t)(7)其中，c为调控常数，0 J l 时，表示最优解 的相 位角大 于 当前 解 的相位 角，当前 解 应该 向角 度增 大 的方 向旋转，即逆时 针旋转，以 向最优解 方 向搜 索，故 优化搜索 函数(a ，)应 取 十 1，反 之 应为 一1。同理 推 出其他 情况。这样，就可 以用(5)式 的量子旋 转 门引导 和更 新 当前 第 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 量子 遗传算 法反演 的步骤 根据地球物理反演的特点，结合量子遗传算 法反演 的优势，可 以设 置下列具 体步骤：1)初始 化：根据 反 演参 数 的多 少 以及 问题 的 复杂性来 确定 种群 的大小。在 反演 中，将 种 群大 小 设 定 为反 演参 数 的 0 1 1 0倍，就 可 以保 证 反演 的成 功。根 据 每个 参 数 的范围 可 以设 定 m 个 量 子 位数 来 描 述 所有 参数，就可以建立如前文(4)式所示的种群大小为 n的量子 位种群。其 中 r (一1，2，2；一1，2，)为种 群 中 第 i 个个 体 的第 个 量 子位。在初 始 种 群 中，所 有的 量子位的概率幅元素都取 2 2，表示初始搜 索 以等概率 叠加；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)其 中，b (1，2，；一1，2，m)为 量子 位通 过 比 较测量 后的二进 制取值。3)解码：就是 把 当前测 量得 到 的二 进制 串进 行解码，得到各参 数对应 的十进 制值。1 2 (1 O)其 中，d (l，2，1l；一1，2，k m)为需 要 反 演 的 k个参数对 应 的十进制取值。4)评价：将 上式 得 到 的 组模 型参数 通 过 正 演，进 一步得 到对 应 的各参 数 的正 演值 P (”)，为参数 的数 目，用式(1 1)拟 合 度 函数 分 别 对 当 前种 群得到 的参 数值进 行评价。Fi t一,=1 -P ob -(i)(1 1)其 中，1 ，P 幽(i)是第 i 个 参 数 的观测 数据，P ()是某 一 模 型 的第 i 个 参 数 的正 演 理 论 数 据，为参 数 的个 数。5)择优：根据 评价情 况，选择 当前最 优拟合 度 值 F i t 对应 的个体，并判断是否满足式(1 2)的 中止条件，若满足，则中止搜索，否则，进入下一步 种群更 新。6)量子 门 更新：用 当前 最优 个 体 的量子 位 的 根据式(5)构建旋转 门，按照式(8)更新 当前种 群个 体对应的量子位，从 而完 成当前 整个种 群的更 新。7)进 入下一代 循环，算 法 转至 步骤 2)继 续 执 行，直到算法满足中止条件(1 2)式：F t 6 O 口 卢 d 0 口 一 0 ：0 0 0 Fa l s e 0 0 0 0 0 0 0 Tr u e 0 0 0 0 0 0 1 Fa l s e 0 0 0 0 0 0 1 Tr u e 0 0 5 z r l 1 1 0 1 0 Fa l s e 0 0 Dr 一 1 1 4-1 0 1 0 Tr u e 0 O 2 5 1 1 0 土 1 1 1 F a l s e 0 0 0 5 1 1 0 1 1 1 Tr u e 0 O2 5 1 1 0 4-1 *：T i 为当前染色体 的第 i 个量子位的值，b 当前最优解 染色体 的第 i 个量子位的值，_厂(z)为染 色体对应的函数 取值，a。，犀 为 f )一a f 0)+f 1)表示的第 i 个概率幅值。s(u i，届)为 A 0 1 的符号，即式(1 3)中 一s(口。，晟)*Z l 0 我们知道，这种旋转角方案是针对组合 问题 的，而且 只利 用到量 子的叠加 特征，对 于纠缠 特征 利用不很明显，所以，本文采用表 1 所示的取值方 案，有效 的兼 顾 了量 子的纠缠 特性，在 后面 的实例 中证 明是有 效的。对于搜索步长的问题，在一般的优化问题，特 别是组合问题中并不涉及到，但对于更复杂的寻 优 问题，并 不仅仅 是组合排 序这 么容易，它涉 及到 最 后在最 优解 附近 搜索 的 收敛 控 制 问题，这就 需 要控制 步长，使 算法 在 最优 解 附近 一 方 面不 因步 长过大 而跳 出，也 不 因步 长 太小 而难 于 收敛。所 以本文 采用式(7)所示 的 自适应搜 索步 长，有效地 解决 了这个难题。4 实 例 为 了验证 方法 的有 效性 和实用 性，本 文设 计 了一个 大 地 电磁 理 论 模 型 和 一 个 实 测 声 阻抗 数 据，对量子遗传算法和遗传算法(GA)进行 比较，情况 如下。4 1两层 Mr理论模 型 遗 传算法 采用最优 保 留策 略，十进 制编码，种 群 大小为 1 O，采用 蒙特 卡罗 法选 择，单 点杂 交，杂 交概 率 为 0 8 5。随机 位 变 异，变 异 概 率 为 0 8。并引入灾变机制，灾变概率为 0 5。量子遗传算 法 采用种群 大小 为 1 0，串长 1 3。计算结 果如 下表 3所 示，对 两种 方 法各 独 立 计 算 5 O次。算法 性 能从 搜索 结果 的 效率 和质 量 两方 面对 比，用 搜索 结果 的最佳 值、平 均值、最 佳 拟合值、平 均拟合值 来评价算 法 的质 量，其 中最 佳 值、平均值、最佳拟合值、平均拟合值分别表示 5 O 次搜索中最接近原始模型的搜索结果，5 o次搜索 到的模型参数的平均值，5 O次搜索中得到的最小 拟合值，5 O次搜索得 到的 拟合 值 的算术 平 均。用 搜索时间来评价搜索效率，其中最快搜索时间是 5 O次搜索 中最快一 次的耗时，平均搜索 时间是 5 O 次搜索 的平均耗 时。从计算结果 的最佳值来看，量子遗传算法反 演结果各参数均比遗传算法更逼近理论模型值；从计算结果的平均值来看，量子遗传算法反演结 果平均值略差于遗传算法平均值，主要原因是量 子遗传算法量子概率编码使得种群多样性增强，从 而不易 陷入局 部极 小，总 体来 说还 是 能很 好 的 拟合理论模 型。从计算结果 的最佳搜索时间来 看，两种 方法 的差 别 不大；而 平均 搜索 时 间，量 子 遗传算法只需要遗传算法的三分之一；两种方法 计算结果的平均拟合值相差不大，最佳拟合值量 子遗 传算法 比遗传算 法更好。总的来看，在 5 0次独 立 的搜 索 中，量 子遗 传 算法能搜索到比遗传算法更优的个体，而且平均 6 4 0 工 程 地 球 物 理 学 报(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卷 搜索时间大大缩短，体现了算法质量和效率上的 优势。4 2 地震 实际资料 图 1是某地 区 的一 口井 的声 波阻 抗 曲线，是 由声波 和密度测井 曲线 在经过一 系列处理 后得 到 的。图 2为其反射 系数。采用 由零 井 源距 VS P资料 分 析 得 到 的主 频 为 2 5 Hz 的零相位子波，进行反褶积就生成了合 成记 录。如图 3所示。按照前 面步骤，通 过 不 断修 改波 阻抗 种 群 来 拟合 地震 波形 数 据，达 到最 终寻 找 到最 优 波阻 抗 模 型的 目的。反演 结果如 下。表 3 两层理论模型计算结果与比较 Ta b l e 3 Re s u l t a n d c o mp a r i s o n o f t h e t wo l a y e r s mo d e l c a l c u l a t i o n 模型 算法 模型参数 搜索最佳值 搜索平均值 平均拟合值 最佳拟合值 两 层 遗传算法p n iT I 5 0 5 0 0 3 0 m 1 0 0 0 h I 1T I 5 0 0 h 2 m 0 量子遗传 n m 5 0 算法 p 2 n I n 1 0 0 0 h 1 m 5 0 0 h 2 m 0 99 9 7 9 50 0 2 5 O O 50 O 1 2 5 O O 2 9 9 9 97 50 O 2O O O 5 O 27 1 0 0 0 12 1 0 06 06 50 0 12 0 0 5 O3 9 O 0 O 31 7 8 3 311 4 5O 0 00 2 1 2 77 8 8 1 0一 38 2 6 4 9 4 0 9 8 0 00 71 1 40 71X 1 0一 _二：畦 受 -：I l I i 0 i I I i 图1 某地区的一口 实测井的声波阻抗曲线 F i g 1 Th e c u r v e o f s o u n d wa v e i mp e d a n c e i n a we l l 图2 实测井对应的反射系数 Fi g 2 Th e r e fle c t i o n c o e f f i c i e n t i n a we l l 暑uI s 县 第 6 期 罗红明 等：地球物理资料非线性反演方法讲座(八)量子遗传算法 6 4 1 一 q 昌 g 5 结 论 0 3 02 O 1 0 -O 1-0 2 O 3 _：2 000 图3 实测井的合成地震记录 Fi g 3 Th e s y n t h e t i c e a r t h q u a k e r e c o r d i n a we l l 图4 实测井反演的最优波阻抗曲线 Fi g 4 Th e c u r v e o f o p t i o n a l wa v e i mp e d a n c e o f we l l i n v e r s i o n 。l W l1W av eform I：l 一 一 Q G A W av efo rm I 删 lf ：V 图5 实测井反演的最优波形曲线 F i g 5 Th e c u r v e o f o p t i o n a l wa v e i mp e d a n c e o f we l l i n v e r s i o n 量子遗传算法已经应用于一些领域的优化计 算，并取得了很好 的效果。本文在分析量子遗传 算 法 的内在机理 的基础 上，针 对地 球 物理 反 演 问 题属于 多参数 寻优，解 的非唯一 性严重等 特点，将 该方法作 了部分 改进，数 值测试对 比结果 表 明，运 用量子位 编码和 量 子 门更 新，可 以大 大 简化 算法 的步骤，缩 短 了搜 索 时 间。并 且在 计 算结 果 精度 和算法收敛性能上都比遗传算法更佳。量 子遗传算 法作 为一种新 兴的非线性 反演方 法，还需要在今后更复杂的实际应用中不断完善。参考文 献：1 D e u t s c h D Qu a n t u m T h e o r y，t h e C h u r c h T u r i n g P r i n c i p l e，a n d t h e U n i v e r s a l Qu a n t u m c 0 mp u t e r J Pr o c e e di ngs Ro yal Soc i e t y Lo n do n，1 9 85，4 00：9 7 3 2 l O l 2 3 0 O O 0 O 0 0 O O 目加 6 4 2 工 程 地 球 物 理 学 报(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 卷 1 l 7 2 3 S h o r P WA l g o r i t h ms f o r Qu a n t u m C o mp u t a t i o n：Di s c r e t e l o g a r i t h ms a n d F a c t o r i n g I n：P r o c e e d i n g o f t h e 3 5 t h I EEE S y mp o s i u m o n F o u n d a t i o n s o f C o m p u t e r S c i e n c e S a n t a F e，Ne w Me x i c o J I E E E Co mput e r So c i e t y Pr e s s，1 99 4：1 24 1 34 3 G r o v e r L KA F a s t Qu a n t u m Me c h a n i c a l Al g o r i t h m f or Da t a ba s e Se a r c h Pr oc 2 8t h Ann ACM Sy mp J T h e o r yo fC o m p u t i n g，AC M 尸r ，1 9 9 6：2 1 2 21 9 4 Gr o v e r L K Qu a n t u m Me c h a n i c s He l p s i n S e a r c h i n g f o r a Ne e d l e i n a Ha y s t a c k J P h y s i c a l R e v L e t t e r s，1 9 97，7 9(2)：3 2 5 3 2 8 5 罗红明，王家 映，师学明，等 量子路 径积分算法及其 在大地 电磁 中的应用 J 地 球物 理学 报，2 0 0 7，5 0 (4)：1 2 6 8 1 2 7 6 6 Ge Y，Wa t s o n L，C o l l i n s E G e n e t i c A l g o r i t h ms f o r Op t i mi z a t i o n o n a Qu a n t u m C o mp u t e r，Un c o n v e n t i o n a l Mo d e l s o f C o mp u t a t i o n M，S p r i n g e r Ve r l a g，Lon do n，1 99 8 7 N a r a y a n A，Mo o r e MQu a n t u m I n s p i r e d G e n e t i c Al g o ri t h ms，T e c h n i c a l R e p o r t 3 4 4 C ，D e p a r t me n t o f Co mput e r S c i e nc e，Un i v e r s i t y o f Ex e t e r，En g一 1 a nd，1 9 98 8 R y l a n d e r B，S o u l e T，F o s t e r J Qu a n t u m G e n e t i c Al go r i t hms，Pr o c e e di ng s of t he Ge ne t i c a nd Ev ol u t i o n a r y C o mp u t a t i o n C o n f e r e n c e c Mo r g a n K a u f m a n，2 00 0 37 3 9 3 Na r a y a n a n A，Mo o r e M Qu a n t u m-I n s p i r e d Ge n e t i c Al g o r i t h ms A I n：P r o c e e d i n g s o f t h e 1 9 9 6 I E E E I n t e r n a t i o n a l Co n f e r e n c e o n E v o l u t i o n a r y Co mp u t a t i o n(I C E C 9 6)C N o g a y a，J a p a n，I E E E P r e s s 1 9 96 41 46 1 o 3 Ha n K H，K i m J HG e n e t i c Qu a n t u m A l g o r i t h m a n d i t s App l i c a t i o n t o Co mbi na t or i al Opt i mi z a t i o n P r o b l e m A I n：I E E E P r o c e e d i n g s Of t h e 2 0 0 0 C o n g r e s s o n E v o l u t i o n a r y C o mp u t a t i o n C S a n D i e g o，US A，P i s c a t a wa y，NJ：I E EE P r e s s，2 0 0 0，2：l 35 4 1 3 6 O 1 1 3 Ha n K H，P a r k K H，L e e C H，e t a 1 P a r a l l e l Qu a n t u m I n s p i r e d Ge n e t i c Al g o r i t h m f o r C o mb i n a t o r i a l O p t i mi z a t i o n P r o b l e ms A I n P r o c o f t h e I EEE Con gr e s s o n Ev ol ut i o na r y Co mpu t a t i on，Pi s c a t a wa y：I EE E Pr e s s，2 0 0 1 1 4 4 2 1 4 2 9 1 2 丛爽 量子力学系统控制导论 M 北 京：科学 出版 社，2 0 0 6 1 3 L i M，V i t a n y i P Ko l m o g o r o v C o mp l e x i t y a n d i t s Ap p l i c a t i o n s，Ha n d b o o k o f Th e o r e t i c a l Co mp u t e r Sc i e n c e Vol u me A Al g or i t h ms a nd Co mpl e x i t y R T h e MI T P r e s s，C a mb r i d g e，Ma s s a c h u s e t t s，1 99 O 1 89 25 4 1 4 Ha n K H，K i m J HGe n e t i c Qu a n t u m Al g o r i t h m a n d i t s Ap p l i c a t i o n t o C o mb i n a t o r i a l 0p t i mi z a t i o n P r o b l e m A I n P r o c e e d i n g o f t h e 2 0 0 0 C o n g r e s s o n E v o l u t i o n a r y C o mp u t a t i o n c 2 0 0 0 1 3 5 4 1 3 6 0