量子克隆进化算法
- 格式：pdf
- 大小：212.40 KB
- 文档页数：5
下载文档原格式
合集下载
量子区分与量子克隆简述
量子区分与量子克隆简述曹怀信【摘 要】在经典信息理论中，编码状态可以精确复制与区分；而在量子信息中，由于态的叠加性存在，使得非正交态不可区分，量子态不可复制与删除.但是，量子态的区分和克隆在新型的量子信息科学中具有广泛的应用，例如量子密码的接收和窃听等.本文简要介绍量子态的区分和克隆的数学概念及相关研究结果.【期刊名称】陕西师范大学学报（自然科学版）【年(卷),期】2014(000)006【总页数】5【关键词】量子区分；量子克隆；量子信息量子信息是近二十年来迅速发展的信息学和量子力学相结合的一门交叉学科［1］.1982年，W.K.Wootters与W.H.Zurek合作在Nature上发表了题为“单量子不能被克隆”的论文［2］，证明了单量子无法被克隆.所以，量子密码原则上可以提供不可窃听、不可破译的保密通信系统.由于结合了量子力学的特性，信息学中的许多传统概念都得到了推广.例如，经典信息中，编码状态用0与1表示，信息是可以精确复制与区分的；而在量子信息中，由于量子态的叠加性使得非正交态不可区分、不可复制、也不可广播［3－5］等.文献［6-7］对量子克隆进行了全面的综述，并研究了恒等量子态的克隆问题.为了推广经典克隆，文献［8-9］引入了概率克隆的概念，发现幺正演化和选择性测量过程结合，确实能够以一定的概率产生从非正交集合中随机选出的输入态的精确复制.随着量子信息科学的迅猛发展，量子态的区分和克隆问题受到众多学者的关注［10－17］.本文简要介绍量子态区分和克隆的数学概念及相关研究结果.值得指出的是，本文相关概念与结果是从文献中总结提炼出来，恕不一一指明出处.1 量子态的区分以下用S（H）表示量子系统（Hilbert空间）H上的全体状态（单位向量）之集，B（H）为H上的全体有界线性算子之集，T＋表示算子T的伴随算子.如果是Hilbert空间H上的一组算子，且满足那么称算子组｛Mi为量子系统H 上的一个量子测量（Quantum Measurement），且称M1，M2，…，Mn为测量算子.对任一｜φ〉∈S（H）（称为测量前系统的状态，即测量前的状态），记P｜φ〉（i）＝ 〈φ｜Mi｜φ〉.如果P｜φ〉（i）＞0，那么称单位向量（状态）｜φi〉:＝Mi｜φ〉为用Mi测量后系统的状态，且称P｜φ〉（i）为事件“｜φ〉＝｜φi〉”发生的概率，即P｜φ〉（i）＝Prob｛｜φ〉＝｜φi〉｝，也称状态｜φi〉为测量的第i个结果.显然，完备性方程等价于:对于H 中的任一单位向量｜φ〉，都有对于量子系统H上的一个量子测量M ＝及量子系统K 上的一个量子测量N ＝，容易看出:算子组M N∶＝ ｛Mi Nj∶1≤i≤n，1≤j≤m｝满足从而，M N是H K上的一个量子测量，称为M 与的张量积.张量积空间H K上的一个量子测量称为是可分的，是指存在H与K上的算子组与使得Mi＝Ai Bi（i＝1，2，…，n）.这时，完备性方程变为特别地，可分量子测量称为H K上的局部量子测量.定义1 设S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是量子系统H中的一组状态（单位向量）.（1）如 果 存 在 量 子 测 量 M ＝ ｛M1，M2，…，Mm＋1｝，使得m 阶方阵（称为判定矩阵）C（S，M）∶＝［〈ψj｜Mi｜ψi〉］为正定对角阵，那么称S是可区分的；否则，称S是不可区分的.（2）如 果 存 在 量 子 测 量 M ＝ ｛M1，M2，…，Mm＋1｝，使得矩阵C（S，M）为单位阵，那么称S是可以可靠区分的；否则，称S不能可靠区分.注1 设S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是可区分的，则存在量子测量 M ＝｛M1，M2，…，Mm＋1｝，使得矩阵C（S，M）∶＝［〈ψj｜M＋iMi｜ψj〉］为正定对角阵.于是，对任一｜ψ〉∈S，有〈ψ｜Mi｜ψ〉≠0当且仅当｜ψ〉＝｜ψi〉.又因为〈ψi｜Mi｜ψi〉＞0，所以，有以下判断:（1）当〈ψ｜Mi｜ψ〉＝0时，必有｜ψ〉≠｜ψi〉；（2）当〈ψ｜Mi｜ψ〉≠0时，｜ψ〉以概率pi＝ 〈ψ｜Mi｜ψ〉取｜ψi〉，即P｛｜ψ〉＝｜ψi〉｝＝〈ψ｜Mi｜ψ〉.这说明，可以概率pi＝〈ψ｜Mi｜ψ〉肯定｜ψ〉＝｜ψi〉成立.注2 设S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是可以可靠区分的，则存在量子测量M ＝｛M1，M2，…，Mm＋1｝，使得矩阵C（S，M）为单位阵.于是，对任一｜ψ〉∈S，有〈ψ｜Mi｜ψ〉＝1当且仅当｜ψ〉＝｜ψi〉.因而，有以下判断:（1）当〈ψ｜Mi｜ψ〉＝0时，有｜ψ〉≠｜ψi〉；（2）当〈ψ｜Mi｜ψ〉≠0时，｜ψ〉以概率pi＝ 〈ψ｜Mi｜ψ〉＝1取｜ψi〉，即P｛｜ψ〉＝｜ψi〉｝＝1.这说明，能够以概率1（即可靠的）肯定｜ψ〉＝｜ψi〉成立.定理1 （可靠区分准则）设S＝｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是量子系统H中的一组状态，则S是可以可靠区分的当且仅当S是正交的.证明 充分性.设S是正交的，记Mi＝｜ψi〉〈ψi｜（i＝1，2，…，m），Mm＋1 ＝.因为S＝｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是量子系统H 中的一组正交态，所以M1，M2，…，Mm＋1是两两正交的正交投影，且构成一个量子测量（投影测量）.显然，C（S，M）为单位阵.故S是可以可靠区分的.必要性.设S是可以可靠区分的，则由定义1（2）知，存在量子测量 M ＝｛M1，M2，…，Mm＋1｝，使得矩阵C（S，M）为单位阵，即〈ψi｜Mi｜ψi〉＝1，〈ψj｜Mi｜ψj〉＝0（i≠j）.可见 ‖Mi｜ψj〉‖2＝〈ψj｜Mi｜ψj〉＝0（j≠i）.假设S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是非正交的，则 i∈Δm ＝ ｛1，2，…，m｝，使得｜ψi〉 Vi＝｛｜ψj〉∶j∈Δm＼｛i｝｝⊥.由于H＝⊕Vi，所以存在常数kj（j∈Δm＼｛i｝｝）及｜φi〉∈Vi，使得于是，因而｜kj｜2＋1＝‖φi‖2.由于｜ψi〉 Vi，所以｜kj｜＞0，从而 ‖φi‖ ＞1.另一方面，由知所以，‖φi‖≤1，矛盾.因此S是正交的.定理2 （可区分准则）设S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是量子系统H中的一组态，则S是可以区分的当且仅当它是线性无关的.证明 充分性.设S是线性无关的.令Vi＝｛｜ψj〉∶j∈ Δm＼｛i｝｝⊥.若Vi＼｛｜ψi〉｝⊥＝ Ø，则Vi ｛｜ψi〉｝⊥，从而｜ψi〉∈＝span｛｜ψj〉∶j∈Δm＼｛i｝｝，所以，｜ψ1〉，｜ψ2〉，…，｜ψm〉线性相关，矛盾.因此， i∈Δm，有于是，存在非0向量｜vi〉∈Vi＼｛｜ψi〉｝⊥ （i＝1，2，…，m）.令｜ei〉＝ 〈vi｜vi〉－1/2｜vi〉，则〈ei｜ψi〉≠0，〈ei｜ψj〉＝0（i≠j）.令则E＝｛E1，E2，…，Em＋1｝是量子测量，且C（S，E）为正定对角阵.所以，由定义1（1）知，S是可区分的.必要性.设S是可区分的，则由定义1（1）知，存在量 子 测 量 M ＝｛M1，M2，…，Mm＋1｝，使 得 矩 阵C（S，M）为正定对角阵，即〈ψi｜Mi｜ψi〉＞0，〈ψj｜Mi｜ψj〉＝0（i≠j）.假设S是线性相关的，则存在i∈ Δm，使得｜从而，＝0.这与 ‖Mi｜ψi〉‖2＝〈ψi｜Mi｜ψi〉＞0矛盾.故S是线性无关的.推论1 设S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是量子系统H中的一组非正交态，则不存在量子测量M＝ ｛M1，M2，…，Mk｝及满射f:Δk →Δm 使得正算子构成一个量子测量E＝ ｛E1，E2，…，Em，0｝，且C（S，E）为单位阵.证明 假设存在这样的量子测量M及满射f，使得 E ＝ ｛E1，E2，…，Em，0｝是一个量子 测 量 且C（S，E）为单位阵.从而，S ＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是可以可靠区分的.这与定理1的结论相矛盾.定义2 如果存在H上的正可逆线性算子T使得TS∶＝ ｛T｜ψ1〉，T｜ψ2〉，…，T｜ψm〉｝是可以可靠区分的，那么称S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是可以广义可区分的.定理3 （广义可区分准则）设dim H＝n＜∞，则S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是可以广义可区分的当且仅当它是可以区分的.证明 充分性.设S ＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是可区分的，则由定理2知S是线性无关的.从而，存在单位向量｜ψm＋1〉，｜ψm＋2〉，…，｜ψn〉，使得S1＝｛｜ψ1〉，｜ψ2〉，…，｜ψn〉｝成为H 的 Hamel基.定义，即A｜x〉＝〈ψj｜x〉·｜ψj〉， ｜x〉∈H.容易看出，A:H →H 为正可逆线性算子.因为｜ψ1〉，｜ψ2〉，…，｜ψn〉线性无关，且所以〈ψj｜A－1｜ψi〉＝δij.因此｛A－1/2｜ψk〉:k＝1，2，…，n｝为H 的正规正交基.记T＝A－1/2，则TS∶＝｛T｜ψ1〉，T｜ψ2〉，…，T｜ψm〉｝为H中的正规正交系，因而是可以可靠区分的（定理1）.再由定义2知S是广义可区分的.必要性.设S是广义可区分的，则存在H上的正可逆线性算子T 使得TS∶＝ ｛T｜ψ1〉，T｜ψ2〉，…，T｜ψm〉｝是可以可靠区分的，从而为H 中的正规正交系（定理1）.因此，｛T｜ψ1〉，T｜ψ2〉，…，T｜ψm〉｝是线性无关系.由于算子T是可逆线性，因此S也是线性无关的.故由定理2知，S是可以区分的.证毕.推论2 设dim H ＝n＜ ∞ 且S＝ ｛｜ψ1〉，｜ψ2〉，…，｜ψm〉｝是量子系统H 中的一组线性无关态，则存在H上的新内积（··，），使得S为Hilbert空间（H，（··，））中的正规正交系，从而可以可靠区分.证明 由定理3知，存在H上的正可逆线性算子T使得TS∶＝｛T｜ψ1〉，T｜ψ2〉，…，T｜ψm〉｝是可以可靠区分的.从而，由定理1知，TS成为H中的正规正交系.定义（｜x〉，｜y〉）＝ 〈x｜T＋T｜y〉＝〈x｜T2｜y〉，则 得 到 H 上 的 新 内 积 （··，） 且（｜ψi〉，｜ψj〉）＝ 〈ψi｜T＋T｜ψj〉＝δij.由此可见，S为 Hilbert空间（H，（··，））中的一组正交态.从而，由定理1可知，S关于新内积是可以可靠区分的.证毕.2 量子态的克隆量子克隆问题（QCP）:是否存在一个状态｜0〉∈S（H）及酉算子U∈B（H H）使得 ｜φ〉∈S（H），有U（｜φ〉｜0〉）＝｜φ〉｜φ〉？当U（｜φ〉｜0〉）＝｜φ〉｜φ〉成立时，称状态｜φ〉被U 确定克隆（复制）了.所以，QCP等价于:是否存在一个量子装置（即酉算子）可以确定地克隆任意一个状态？显然，单个状态必然是可以确定克隆的.定理4 （不可线性克隆定理）当dim（H）≥2时，对任一状态｜0〉∈S（H）及H H上的任一线性算子T，都存在状态｜φ〉∈S（H）使得T（｜φ〉｜0〉）≠｜φ〉｜φ〉.等价地说，命题“存在｜0〉∈S（H）及线性算子T使得对任意的｜φ〉∈S（H），都有T（｜φ〉｜0〉）＝｜φ〉｜φ〉”是错误的.证明 假定存在｜0〉∈S（H）及线性算子T使得对任意的｜φ〉∈S（H），都有T（｜φ〉｜0〉）＝｜φ〉｜φ〉.因为dim（H）≥2，所以存在｜φi〉∈S（H）（i＝1，2）使得｜φ1〉⊥｜φ2〉.令a＝b＝/2，则a｜φ1〉＋b｜φ2〉∈S（H）.因为T（｜φ1〉｜0〉）＝｜φ1〉｜φ1〉，T（｜φ2〉｜0〉）＝｜φ2〉｜φ2〉，T（a｜φ1〉＋b｜φ2〉）｜0〉＝ （a｜φ1〉＋b｜φ2〉） （a｜φ1〉＋b｜φ2〉），且T 是线性的，所以于是，计算｜φ1〉｜φ1〉与上式两边的内积可得a＝a2.这与a＝b＝矛盾.证毕.推论3 当空间H的维数大于或等于2时，对任一状态｜0〉∈S（H）及任一酉算子U∈B（H H），都存在｜φ〉∈S（H）使得定义3 设C（H） S（H）.若存在｜0〉∈S（H）及酉算子U∈B（H H），使得则称C（H）是可以确定克隆的，此时，称酉算子U为量子克隆机，也称U可以确定克隆状态集C（H）.否则，称C（H）是不可确定克隆的.特别地，如果单态集C（H）＝｛｜φ〉｝是可以确定克隆的，那么称状态｜φ〉是可以确定克隆的.由定义3及推论3可知，当dim（H）≥2时，全体量子态之集S（H）是不可确定克隆的，等价地说，不存在一个量子装置（即酉算子）可以确定地克隆任意一个量子态.下面的定理给出了一组量子态可以确定克隆的充分必要条件，可称为确定克隆准则.定理5 （确定克隆准则）设1≤dim（H）＝d＜∞，则非空集C（H） S（H）是可以确定克隆的当且仅当它是正交系.证明 必要性.设C（H）是可以确定克隆的，则由定义3知，存在状态｜0〉∈S（H）及酉算子U∈B（H H）使得（＊）式成立.假设C（H）不是正交系，则存在不同的两个态｜φ1〉，｜φ2〉∈C（H），使得〈φ1｜φ2〉≠0.因为U（｜φ1〉｜0〉）＝｜φ1〉｜φ1〉，U（｜φ2〉｜0〉）＝｜φ2〉｜φ2〉且算子U 保持内积，所以〈φ1｜φ2〉＝ 〈φ1｜φ2〉2.因此，〈φ1｜φ2〉＝1.进而可知，存在常数c使得｜φ1〉＝c｜φ2〉.因为〈φ1｜φ2〉＝〈φ1｜φ2〉2，所以c＝1，即｜φ1〉＝｜φ2〉.这与｜φ1〉≠｜φ2〉矛盾.这就证明C（H）是正交系.充分性.设C（H）是正交系，则它必为有限集.记C（H）＝ ｛｜ψi〉:i∈I｝，其中｜ψi〉≠｜ψj〉（i≠j）.任取｜0〉∈S（H）.显然，｛｜ψi〉｜0〉:i∈I｝与｛｜ψi〉｜ψi〉:i∈I｝都是有限维 Hilbert空间H H中的正交系，且个数相同.将它们生成的线性子空间分别记为 M、N.取 M⊥、N⊥的正规正交基｛｜ej〉｝j∈J，｛｜εj〉｝j∈J，得到 H H 的正规正交基:｛｜ψi〉｜0〉:i∈I｝∪ ｛ej｝j∈J 与｛｜ψi〉｜ψi〉:i∈I｝∪ ｛εj｝j∈J.定义U｜ψi〉｜0〉＝｜ψi〉｜ψi〉（ i∈I），U｜ej〉＝｜εj〉（ j∈J），则得到酉算子U:H H→H H，满足U｜ψi〉｜0〉＝｜ψi〉｜ψi〉（ i＝I），即（＊）式成立.所以，由定义3可知，C（H）是可以确定克隆的.证毕.推论4 （不可克隆定理）不存在｜0〉∈S（H）及酉算子U∈B（H H），使得证明 由于全体量子态之集S（H）不是正交集，所以由定理5知S（H）是不可确定克隆的.参考文献：［1］Nielsen M A，Chuang I L.Quantum computation and quantuminformation［M］.London:Cambridge University Press，2000.［2］Wootters W K，Zurek W H.A single quantum cannot becloned［J］.Nature，1982，299:802-803.［3］Barnum H，Caves C M，Christopher A F.Noncommuting mixed states cannot be broadcast［J］.Physical Review Letters，1996，76（15）:2818-2821.［4］Piani M，Horodecki P，Horodecki R.No-local-broadcasting theorem for multipartite quantum correlations［J］.Physical Review Letters，2008，100:090502.［5］Luo Shunlong，Li Nan，Cao Xuelian.Relation between“no broadcasting”for noncommuting states and“no local broadcasting”for quantum correlations［J］.Physical Review A，2009，79:054305.［6］Fan Heng，Wang Yinan，Jing Li，et al.Quantum cloning machines and the applications［EB/OL］.［2014-09-15］.http:∥/pdf/1301.2956v4.［7］Fan Heng，Liu Baoying，Shi Kangjie.Quantum cloning of identical mixedqubits［J］.Quantum Information ＆Computation，2007，7:551-558.［8］Duan Luming，Guo Guangcan.Probabilistic cloning and identification of linearly independent quantum states［J］.Physical Review Letters，1998，80（2）:4999-5002.［9］Duan Luming，Guo Guangcan.A probabilistic cloning machine for replicating two non orthogonal states［J］.Physics Letters A，1998，243（5）:261-264.［10］Pati A K，Braunstein S L.Impossibility of deleting an unknown quantumstate［J］.Nature，2000，404:164-165.［11］Qiu Daowen.Some general probabilistic quantum cloning and deletingmachines［J］.Physics Letters A，2003，308（5）:335-342.［12］Martini F D，Pelliccia D，Sciarrino F.Contextual，optimal，and universal realization of the quantum cloning machine and of the NOT gate［J］.Physical ReviewLetters，2004，92:067901.［13］Valerio S，Sofyan I，Nicolas G，et al.Quantum cloning［J］.Reviews of Modern Physics，2005，77:1225-1256.［14］Van Enk S J.Relations between cloning and the universal NOT derived from conservation laws［J］.Physical Review Letters，2005，95:010502.［15］Dang Guifang，Fan Heng.General sequential quantum cloning［J］.Journal of Physics A:Mathematical and Theoretical，2008，41:155303.［16］Zhang Wenhai，Yu Longbao，Yang Ming，et al.Quantum cloning with multicopy in d-dimensions［J］.Science China:Physics， Mechanics andAstronomy，2011，54（12）:2217-2224.［17］Shen Yao，Hao Liang，Long Guilu.Why can we copy classicalinformation［J］.Chinese Physics Letters，2011，28（1）:010306.基金项目：国家自然科学基金资助项目（11371012）DOI:10.15983/ki.jsnu.2014.063。
量子计算中的量子进化算法及其应用
量子计算中的量子进化算法及其应用量子计算是一种基于量子力学原理的计算模型，可以利用量子比特的并行性和叠加性，在某些问题上实现更高效的计算。
量子进化算法是量子计算中一类重要的算法，其核心思想是通过模拟量子系统的演化过程，从而搜索问题的解空间。
量子进化算法基于量子性质的特点，与经典计算相比具有很大的优势。
在经典计算中，搜索问题的解空间需要逐个检查，时间复杂度随着问题规模呈指数增长。
而在量子进化算法中，可以利用量子比特的叠加性，在一次计算过程中并行地搜索多个解，从而大大加快搜索速度。
在量子进化算法中，量子系统演化的过程通过量子逻辑门来实现。
量子逻辑门对量子比特进行操作，改变其量子态，从而实现量子系统的演化。
在量子进化算法中，常用的量子逻辑门包括Hadamard门、CNOT门和Swap门等。
这些逻辑门的组合可以构建出复杂的量子进化算法，用于解决不同类型的问题。
量子进化算法在很多领域都有广泛的应用。
其中一个重要的应用是优化问题的求解。
优化问题是在给定的约束条件下，寻找最优解的问题。
经典计算中，优化问题往往需要耗费大量的时间和资源。
而量子进化算法可以通过量子并行性，同时搜索多个解，从而提高求解效率。
该算法已经在组合优化问题、机器学习中的参数优化等领域取得了显著的成果。
另一个重要的应用是模拟量子系统。
量子系统的演化过程很难通过经典计算模拟，因为量子系统的状态是高度复杂的，需要大量的计算资源。
而量子进化算法可以利用量子并行性，在一次计算过程中模拟量子系统的演化，从而大大提高了模拟效率。
这个应用对于研究量子力学的基本原理和理解量子系统的行为具有重要的意义。
除了以上应用，量子进化算法还可以用于解决组合优化问题、图论问题、排队论问题等。
这些问题在实际应用中往往非常复杂，需要考虑多个因素和约束条件，经典计算很难在合理的时间内找到最优解。
而量子进化算法通过利用量子并行性，可以在较短的时间内搜索到较优解，从而在实际问题中发挥重要作用。
量子克隆遗传算法
１ 引言
进 化计算是一种仿生计算 。依照达尔文 的 自然选择和孟 德尔的遗传变异理论 ， 生物 的进化是通过繁殖 、 变异 、 竞争、 选 择来 实现的 ， 进化算法就是建 立在上 述生物模 型基础 上的 随 机 搜 索 技 术 。我 们 所 熟 悉 的 遗 传 算 法 （ ｅ ｅｉ ｇ — Ｇ ｎ ｔ Ａｌ ｃ ｏ ｒ ｈ ）１ 它通过模 拟达 尔文 的“ ｉ ｍｓ ＿ ， ｔ ｌ ］ 优胜劣 汰 ， 适者 生存 ” 的原 理鼓励好 的个体 ， 过模拟孟 德尔 的遗 传变异理 论在进 化过 通 程中保持好 的个体 ， 同时寻找 更好 的个体 ， 由此来模 仿一切生 命 与智 能 的 产 生 与 进 化 过 程 明 ］ 理 论 上 已 经 证 明 ： 化 算 。。 进 法 能从概率 的意义上 以随机的方式 寻求到 问题 的最 优解 ； 但
在 实 际 应 用 当中 ， 随着 问题 的复 杂 和 海 量 的数 据 量 ， 出现 了 也
一
子计算 中的量子编码 ， 继承 了免疫克隆策略 中的克隆算 子 ， 将二者相结合 ， 提出了量 子克隆遗传算法 ， 并将其应用 于 ０ １ ／
背包问题上 。与传统进化算法相 比较 ， 它具有收敛速度快 、 寻
Ｑｕ ｎ ｕ Ｃｌｎ ｌ ｎ ｔｃＡｌｏ ｉ ｍｓ ａ ｔｍ ｏ ａ ｅｉ ｇ ｒｔ Ｇｅ ｈ
Ｉ ｎ － ｎ ＪＡＯ － ｅ ｇ ｄ Ｙａ ｇ Ｙａ ｇ Ｉ Ｌｉ Ｃｈ ｎ
（ ｈ ｏ ｆＥｌ ｃ ｒ ｎ ｃ Ｅｎ ｉ ｅ ｒ ｎ Ｓｃ ｏ ｌｏ ｅ ｔ ｏ ｉ ｇ ｎ ｅ ｉｇ，Ｘｉ ｉｎ Ｕｎｉｅ ｓｔ Ｘｉ ８ １ ０７ ） ｄａ ｖ ｒ ｉｙ， ’ ｎ ７ ０ １
Ａｂ ｔａ ｔ Ｇｅ ｅ ｉ ａ ｇ ｒｔ ｍ ｓａ ｆｅ ｔ ｅ ａ ｇ ｒ ｈ ｉ ｏ ｖｎ ｈ ｐ ｉ ｚｎ ｒ ｂ ｅ ，ｂ ｔｉ ｈ ｓ ｓ ｍｅ ｄ ｓ ｄ ａ ｔ ｇ ｓ ｓｒ ｃ ｎ ｔｃ ｌ ｏ ｉｈ ｉ ｎ ｅ ｆ ｃ ｉ ｌ ｏ ｉ ｍ ｓ ｌ ｉ ｇ ｔ ｅ ｏ ｔｍｉｉｇ ｐ ｏ ｌｍ ｖ ｔ ｎ ｕ ｔ ａ ｏ ｉａ ｖ ｎ ａ ｅ
【国家自然科学基金】_混合量子进化算法_基金支持热词逐年推荐_【万方软件创新助手】_20140802
2014年 序号 1 2 3 4 5
2014年 科研热词 量子进化 负荷分配 机组组合 动态规划 修补策略 推荐指数 1 1 1 1 1
推荐指数 2 1 1 1 1 1 1 1 1 1
2010年 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14
科研热词 推荐指数 量子pso 1 遗传pso 1 车辆路径 1 置换flow shop调度问题 1 粒子群优化(pso) 1 物流 1 混合量子进化算法 1 混合量子算法 1 模拟退火pso 1 多车型 1 动态需求 1 优化 1 二阶振荡pso 1 两阶段模型 1
2008年 序号 1 2 3 4 5 6
科研热词 量子进化算法 量子比特 混合量子进化算法 混合量子算法 微粒群算法 函数优化
推荐指数 2 1 1 1 1 1
2009年 序号 1 2 3 4 5 6 7 8 9 10
科研热词 混合量子算法 量子进化算法 量子计算 量子衍生进化规划 量子比特 置换flow shop调度问题 生产调度 同等并行机拖期调度 优化 代工
ቤተ መጻሕፍቲ ባይዱ
2012年 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
科研热词 推荐指数 量子进化算法 2 非支配排序遗传算法 1 量子计算 1 量子动力学机制 1 配送路径 1 邻近性 1 进化算法 1 运筹学 1 自适应量子旋转角 1 精英竞争池 1 算法改进 1 滚动窗口 1 混沌 1 混合量子进化算法 1 混合混沌量子进化算法 1 混合协同进化 1 机器排序 1 有效解集 1 有效解 1 执行经验记录 1 干扰管理 1 差分进化算法 1 工位 1 属性约简 1 实数编码染色体 1 多样性 1 多峰函数优化 1 协同进化 1 动态调度 1 准时 1 冻结时段 1 作业车间 1 self- adaptive quantum rotation 1 angle performance experience record 1 mixed co-evolution 1 elitist competition pool 1 attribute reduction 1
基于云模型的自适应量子免疫克隆算法
更 佳 的寻优 结 果．
利 用 云模 型在 随机性 和模 糊性 两个 方 面能够 很好 兼顾 这一 品质 ， 整合 量 子免疫 克 隆算法 建模 ， 通 过云算 子 间 的协作 ， 自适 应 控制 免疫 算法 的进 化过程 ； 同时 针对 性 的优 化 了量 子免 疫 算 法过 程 ， 提 出 了一种 基 于 云 模 型 的量子 自适 应免 疫克 隆算 法 ， 仿真 结果 表 明提 出的算 法具有 较 强 的全 局搜 索 能力 、 较高 的搜 索精度 以及 良好 的可靠 性 ．
所示 ．
收 稿 日期 ： ２ ０ １ ２— ０ ９—１ ０ ；修 回 日期 ： ２ ０ １ ３一 Ｏ １— ２ ３ 基金项 目： 西安工业大学校长科研基金（ Ｘ Ａ Ｇ Ｄ Ｘ Ｊ Ｊ １ ０ ４ ２ ） 资助项 目
作者简介 ： 马颖 （ １ ９ ７ ９一） ， 男， 博士生 ， 工程师 ， 主要研究量子信息 、 信号处理等 ， Ｅ － ｍａ ｉ ｌ ： ｉ ｎ ｎ ｏ ｖ ａ ｔ ｏ ｒ ＠１ ６ ３ ． ｃ ｏ ｉ ｎ
第 ３ ０卷 第 ４期 ２ ０ １ ３年 ７月
计
算
物
理
Ｖｏ Ｉ ＿ ３ Ｏ．Ｎｏ ． ４
Ｃ ＨＩ ＮＥ Ｓ Ｅ Ｊ ＯＵＲＮ ＡＬ Ｏ Ｆ Ｃ ＯＭＰ Ｕ Ｔ ＡＴ Ｉ ＯＮ ＡＬ Ｐ ＨＹ Ｓ Ｉ Ｃ Ｓ
Ｊ ｕ ｌ ｙ ，２ ０１ ３
文章编号 ： １ ０ ０ １ — ２ ４ ６ Ｘ（ ２ ０ １ ３ ） ０ ４ － ０ ６ ２ ７ ０６ －
关 键 词 ：云 模 型 ； 量 子免 疫 算 法 ； 量 子 计 算 ；函 数 优 化
中 图分 类 号 ： Ｔ Ｐ ３ ０ １ ． ６ 文献标识码 ： Ａ
利 用 云模 型在 随机性 和模 糊性 两个 方 面能够 很好 兼顾 这一 品质 ， 整合 量 子免疫 克 隆算法 建模 ， 通 过云算 子 间 的协作 ， 自适 应 控制 免疫 算法 的进 化过程 ； 同时 针对 性 的优 化 了量 子免 疫 算 法过 程 ， 提 出 了一种 基 于 云 模 型 的量子 自适 应免 疫克 隆算 法 ， 仿真 结果 表 明提 出的算 法具有 较 强 的全 局搜 索 能力 、 较高 的搜 索精度 以及 良好 的可靠 性 ．
所示 ．
收 稿 日期 ： ２ ０ １ ２— ０ ９—１ ０ ；修 回 日期 ： ２ ０ １ ３一 Ｏ １— ２ ３ 基金项 目： 西安工业大学校长科研基金（ Ｘ Ａ Ｇ Ｄ Ｘ Ｊ Ｊ １ ０ ４ ２ ） 资助项 目
作者简介 ： 马颖 （ １ ９ ７ ９一） ， 男， 博士生 ， 工程师 ， 主要研究量子信息 、 信号处理等 ， Ｅ － ｍａ ｉ ｌ ： ｉ ｎ ｎ ｏ ｖ ａ ｔ ｏ ｒ ＠１ ６ ３ ． ｃ ｏ ｉ ｎ
第 ３ ０卷 第 ４期 ２ ０ １ ３年 ７月
计
算
物
理
Ｖｏ Ｉ ＿ ３ Ｏ．Ｎｏ ． ４
Ｃ ＨＩ ＮＥ Ｓ Ｅ Ｊ ＯＵＲＮ ＡＬ Ｏ Ｆ Ｃ ＯＭＰ Ｕ Ｔ ＡＴ Ｉ ＯＮ ＡＬ Ｐ ＨＹ Ｓ Ｉ Ｃ Ｓ
Ｊ ｕ ｌ ｙ ，２ ０１ ３
文章编号 ： １ ０ ０ １ — ２ ４ ６ Ｘ（ ２ ０ １ ３ ） ０ ４ － ０ ６ ２ ７ ０６ －
关 键 词 ：云 模 型 ； 量 子免 疫 算 法 ； 量 子 计 算 ；函 数 优 化
中 图分 类 号 ： Ｔ Ｐ ３ ０ １ ． ６ 文献标识码 ： Ａ
量子进化算法原理_智能控制简明教程_[共3页]
![量子进化算法原理_智能控制简明教程_[共3页]](https://img.taocdn.com/s1/m/08db93cac281e53a5902ff67.png)
第6章 计算智能 163（5）随着迭代次数的增加，适应度函数变化即函数()10sin(5)7cos(4)f x x x x =++取得最大值的过程如图6.7所示。
图6.7 粒子群算法的适应度函数曲线变化通过上述粒子群优化计算，最终获得式6.35目标函数的最优解为7.8569x =，()24.8554f x =。
6.3 量子进化算法6.3.1 量子进化算法量子进化算法建立在量子态矢量表达基础上，将量子比特的概率矢量表示应用于染色体的编码，使得一条量子染色体可以表达多个态的叠加，并利用各种量子门实现染色体的更新操作，从而实现目标求解。
2000年，Kuk-Hyun Han 将量子态矢量表达引入染色体编码中，通过量子门旋转实现染色体更新，提出了遗传量子算法（Genetic Quantum Algorithm ，GQA ），并通过对背包问题的优化计算，取得了比常规遗传算法更好的效果。
针对GQA 的不足，Han 在2002年通过改进量子门旋转角度策略和引入移民策略，提出了量子进化算法（Quantum Evolutionary Algorithm ，QEA ）。
由于量子进化算法具有多样性特征，在参数优化计算的过程中可以获得更好的结果，目前已经应用到数值优化、组合优化、图形图像处理、电路设计、通信、多目标优化等领域。
6.3.2 量子进化算法原理量子进化算法采用量子位编码来表示染色体，通过量子门更新种群完成进化搜索。
与传统进化算法相比，它具有种群规模小、收敛速度较快、全局寻优能力强的特点。
下面介绍量子进化算法的原理。
1．QEA 算法基本操作（1）量子染色体编码在量子计算中，采用量子位表示最小的信息单元，一个量子位可以处于“1”态、“0”态。
自适应混沌量子克隆算法
量 子力学 是 ２ ０世纪 物理学 最惊 心动 魄 的发 现之 一 ， 子 计算 是物 理 理论 与 计算 理论 的成 功结 合 ， 量 在量
子体 系 中， 位 的信 息 位 不 再 是 经 典 的 １比特 ， 是 由 两个 本 征 态 的 任 意 叠 加 态 所 构 成 的 量 子 比特 位 １ 而 （ ｕ ｉ ， 如 １ ｎ位二进 制 的串在 量子体 系 中就可 同时表 示 ２ ｑ ｂｔ 例 ） 个 个信 息 ， 量子计 算机 对每个 叠加分 量 （ 而 本 征态 ） 实现 的变换 相 当于 一种经 典计 算 ， 有这 些经典 计算 同时完 成 ， 所 并按一 定 的概率振 幅叠加 起来 ， 出量 给
Ａｂ ｔａ ｔ ｓｒｃ ：
Ａ ｎ ｖ ｌ ｌ ｏ ｉｈ ， ｃ ｌ ｄ ｈ ｓ ｌ ａ ａ ｔｖ ｃ ａ ｓ ｑ ａ ｔ ｍ ｃｏ ａ ａｇ ｒｔ ｍｓ Ｓ ｏ ｅ ａｇ ｒｔ ｍ ａｌ ｔ ｅ ｅｆ ｄ ｐ ｉ ｅ ｈ ｏ ｕ ｎ ｕ ｅ － ｌｎ ｌ ｌ ｏ ｉ ｈ — ＣＱＡ， ｉ ｓ
混沌是 非线性 系统 的本质 特性 ， 具有 随机性 ， 遍历 性及 规律性 等 一系列特 殊性 质． 沌 的发 现 ， 科学 发 混 对 展具有 深远 的影 响 ］混 沌 已经 被作 为在搜 索过程 中避免 陷入 局部 极 值 的一种 优 化 机制 而 引入 到 进化 计算 ． 中， 进化计 算提供 了新 的研究 领域 和应用 方法 ． 为 相关 研究 成果 多数 只是将 变异算 子 中的随机 序列简 单地 用混沌 序列 代替 ， 这些算 法思路 直观 、 实现 简单 、 适应性 强 ； 由于没 有充 分 发挥 混 沌 的作 用 ， 仍然 存 在一 些 问 题 ， 如 ， 略混沌 规律 性 的特 点 ， 少充 分利用 可 以获得 的先验 知识 以提 高算法 的局 部搜索 能力． 例 忽 很
子体 系 中， 位 的信 息 位 不 再 是 经 典 的 １比特 ， 是 由 两个 本 征 态 的 任 意 叠 加 态 所 构 成 的 量 子 比特 位 １ 而 （ ｕ ｉ ， 如 １ ｎ位二进 制 的串在 量子体 系 中就可 同时表 示 ２ ｑ ｂｔ 例 ） 个 个信 息 ， 量子计 算机 对每个 叠加分 量 （ 而 本 征态 ） 实现 的变换 相 当于 一种经 典计 算 ， 有这 些经典 计算 同时完 成 ， 所 并按一 定 的概率振 幅叠加 起来 ， 出量 给
Ａｂ ｔａ ｔ ｓｒｃ ：
Ａ ｎ ｖ ｌ ｌ ｏ ｉｈ ， ｃ ｌ ｄ ｈ ｓ ｌ ａ ａ ｔｖ ｃ ａ ｓ ｑ ａ ｔ ｍ ｃｏ ａ ａｇ ｒｔ ｍｓ Ｓ ｏ ｅ ａｇ ｒｔ ｍ ａｌ ｔ ｅ ｅｆ ｄ ｐ ｉ ｅ ｈ ｏ ｕ ｎ ｕ ｅ － ｌｎ ｌ ｌ ｏ ｉ ｈ — ＣＱＡ， ｉ ｓ
混沌是 非线性 系统 的本质 特性 ， 具有 随机性 ， 遍历 性及 规律性 等 一系列特 殊性 质． 沌 的发 现 ， 科学 发 混 对 展具有 深远 的影 响 ］混 沌 已经 被作 为在搜 索过程 中避免 陷入 局部 极 值 的一种 优 化 机制 而 引入 到 进化 计算 ． 中， 进化计 算提供 了新 的研究 领域 和应用 方法 ． 为 相关 研究 成果 多数 只是将 变异算 子 中的随机 序列简 单地 用混沌 序列 代替 ， 这些算 法思路 直观 、 实现 简单 、 适应性 强 ； 由于没 有充 分 发挥 混 沌 的作 用 ， 仍然 存 在一 些 问 题 ， 如 ， 略混沌 规律 性 的特 点 ， 少充 分利用 可 以获得 的先验 知识 以提 高算法 的局 部搜索 能力． 例 忽 很
量子网络实现最优1→3相位协变量子克隆
量子网络实现最优1→3相位协变量子克隆张文海;张月【摘要】利用最简单的两种量子逻辑门,即:量子旋转门和量子控制非门构成的量子网络实验量子克隆.选择不同的参数,量子网络可以实现最优1→3相位协变量子克隆.由于所采用的是普适的单比特逻辑门,这为不同的物理系统实现相位协变量子克隆提供了通用的方法.【期刊名称】《淮南师范学院学报》【年(卷),期】2016(018)003【总页数】4页(P100-103)【关键词】量子网络;量子旋转门;量子控制非门;相位协变量子克隆【作者】张文海;张月【作者单位】淮南师范学院电子工程学院,安徽淮南232038;淮南师范学院电子工程学院,安徽淮南232038【正文语种】中文【中图分类】O413量子信息科学是量子力学和信息科学的结合，量子信息学的研究是利用量子力学基本原理，发挥量子相关特性的作用，用一种新的方式进行计算，编码和信息传输。
目前，无论在理论上还是在实验上，量子信息的研究都在取得新的进展，已经发展成为内容十分丰富的新学科①郭光灿：《量子信息科学在中国科学技术大学的兴起和发展》，《物理》2008年第2期，第556-561页。
它包括量子计算，量子信息，量子通信和量子博弈等。
在量子信息中，利用量子力学基本原理构建的量子算法已经显示出经典算法上无法比拟的优越性。
而且，也使得在量子力学中出现许多新颖的问题和有趣的应用。
在经典信息科学中，最基本的单元是逻辑门，有一位逻辑门和二位逻辑门。
同样，量子信息学中，最基本的单元是量子逻辑门。
经典和量子逻辑门的本质区别是，量子逻辑门是可逆的，这就解决了经典计算机的能耗问题②李艳玲：《量子态克隆、翻转及隐形传送的理论研究》，聊城大学硕士学位论文，2007年。
对于量子信息的操作，可以利用由基本量子逻辑门组成的量子网络来完成，因而，对量子网络的研究是量子信息中的一个基本研究方向。
众所周知，经典信息可以被精确的复制。
而量子信息学中有一个基本定理，即：量子不可克隆定理③Wootters W K，Zurek W H，"A single quantum cannot be cloned"，Nature（London），1982，299，pp.802-803.，它指出：未知量子态不能被精确的复制。
量子克隆遗传算法
量子克隆遗传算法1李阳阳1，焦李成11西安电子科技大学电子工程学院，西安(710071)E-mail: lyy_111@摘要：遗传算法是解决优化问题的一种有效方法。
但在实际应用中也存在着收敛速度慢，早熟等问题，使得其结果极不稳定。
本文将遗传算法和量子理论相结合并利用免疫系统中所特有的克隆算子，针对0/1背包问题，提出了一种改进的进化算法——量子克隆遗传算法(QCA)。
它能有效的避免早熟，且具有收敛速度快的特点。
关键词：遗传算法量子克隆遗传算法 0/1背包中图分类号：TN9571.引言进化计算是一种仿生计算，依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的，进化算法就是建立在上述生物模型基础上的随机搜索技术。
我们所熟悉的遗传算法(Genetic Algorithms)[1]，它通过模拟达尔文的“优胜劣汰，适者生存”的原理鼓励好的个体，通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体，同时寻找更好的个体，由此来模仿一切生命与智能的产生与进化过程[2][3]。
理论上已经证明：进化算法能从概率的意义上以随机的方式寻求到问题的最优解；但在实际应用当中随着问题的复杂和海量的数据量，也出现了一些不尽人意的情况，主要表现在：计算后期解的多样性差即易造成早熟，收敛速度慢等缺点。
因此，为克服上述缺点关键是构造性能良好的进化算法。
量子力学是20世纪物理学最惊心动魄的发现之一，量子计算是物理理论与计算机的成功结合，在量子体系中，一位的信息位不在是经典的1比特，而是由两个本征态的任意叠加态所构成即称之为量子比特位(qubit)，例如一个n位二进制的串在量子体系中就可同时表示n2个信息,而量子计算机对每个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的结果,这种计算称之为量子并行计算[4]。
正是量子的并行性使得原来传统计算机无法解决的复杂问题以惊人的速度得以解决,但在量子计算机尚未构成的情况下，为了充分利用量子计算的高效并行性，本文借用了量子计算中的量子编码，继承了免疫克隆策略[5]中的克隆算子将二者相结合，提出了量子克隆遗传算法，并将其应用于0/1被包问题上，与传统进化算法相比较,它具有收敛速度快、寻优能力强的特点。
融合量子克隆进化与二维Tsallis熵的医学图像分割算法
摘 要 ： 针 对 进 化 算 法 用 于 图像 分 割 时 收敛 速 度 慢 、 易早熟的缺点 ， 提 出一 种 改 进 的量 子 克 隆进 化算 法 ． 首 先 利 用 量
子 空 间 的 多样 性 丰 富 种 群 信 息 ， 在 量 子 变 异 中根 据 适 应 度 的不 同对 个 体 施 以不 同 的 混 沌 扰 动 ， 以 克 服 量 子 门 旋 转 方 向单 一 、 大 小 固定 的缺 陷 ， 避免种群陷入局部早熟 ； 然 后 利 用 克 隆算 子 将 最 优 个 体 信 息 扩 充 至 下 一 代 ， 以 提 高 其 局 部
分 割效 果 良好 ， 可 以满 足 医学 图像 三 维 重 建 要 求 ． 关键词 ： 进化算法 ； 量子克隆 ； 二维 Ｔ ｓ ａ ｌ ｌ ｉ ｓ 熵； 图像 分 割
中 图 法 分 类 号 ：ＴＰ ３ ９ １
Ｍｅ ｄ ｉ ｃ ａ ｌ Ｉ ｍａ ｇ ｅ Ｓ ｅ ｇ ｍｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ Ａｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ Ｂ ａ ｓ ｅ ｄ ｏ ｎ Ｑｕ ａ ｎ ｔ ｕ ｍ Ｃ ｌ ｏ ｎ ａ ｌ Ｅ ｖ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ａ ｎ ｄ
Ｍａ ｒ ．２ Ｏ１ ４
融合 量 子 克 隆进 化 与二 维 Ｔ ｓ ａ ｌ ｌ ｉ ｓ 熵 的 医学 图像 分 割算 法
李积英， 党建武， 王阳萍
（ 兰 州 交 通 大 学 电 子 与 信 息 工 程 学 院 兰州 ７ ３ ０ ０ ７ ０ ）
（ Ｌ ｊ ｙ ７ ６ ０ ９ ＠１ ２ ６ ． ｃ ｏ ｎ） ｒ
Ａｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ｔｈｅ ｐａ ｐｅ ｒ ｐ ｒ ｏ ｐｏ ｓ ｅ ｓ ａ ｎ ｉ ｍｐｒ ｏ ｖ ｅ ｄ ｃ ｌ ｏ ｎｅ ｑｕ ａ ｎ ｔ ｕｍ ｅ ｖ ｏ ｌ ｕｔ ｉ ｏｎａ ｒ ｙ ａ ｌ ｇｏ ｒ ｉ ｔ ｈ ｍ ｉ ｎ ｖ ｉ ｅ ｗ ｏｆ ｔ ｈｅ ｓ ｈｏ ｒ ｔ ｃ ｏｍｉ ｎ ｇｓ ｅ ｘ ｉ ｓ ｔ ｅ ｄ ｉ ｎ ｔ ｈｅ ｉ ｍａ ｇｅ ｓ ｅ ｇ ｍｅ ｎｔ ａ ｔ ｉ ｏ ｎ ｂｙ ｅ ｖ ｏｌ ｕ ｔ ｉ ｏ ｎａ ｒ ｙ ａ ｌ ｇｏ ｒ ｉ ｔ ｈ ｍ ｓ ｕ ｃ ｈ ａ ｓ ｓ ｌ ｏ ｗ ｃ ｏ ｎｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ａ ｎｄ ｅ ａ ｓ ｙ ｐ ｒ ｅ ｍａ ｔ ｕｒ ｉ ｔ ｙ． Ｔｈｅ ｉ ｍｐ ｒ ｏｖ ｅ ｄ ａ ｌ ｇ ｏｒ ｉ ｔ ｈｍ ｉ ｓ ａ ｂｌ ｅ ｔ ｏ ｏ ｖ ｅ ｒ ｃ ｏ ｍｅ ｔ ｈｅ ｗｅ ａ ｋｎ ｅ ｓ ｓ ｅ ｓ ｌ ｉ ｋｅ ｔ ｈ ｅ ｓ ｉ ｎ ｇｅ ｖ ａ ｒ ｉ ａ ｔ ｉ ｏ ｎ ｏｆ ｑ ｕａ ｎｔ ｕ ｍ ｇ ａ ｔ ｅ，ｔ ｈｅ ｆ ａ ｕｌ ｔ ｏ ｆ ｆ ｉ ｘ ｅ ｄ — ｓ ｉ ｚ ｅ，ａ ｎｄ ａ ｖ ｏ ｉ ｄ ｔ ｈｅ ｐ ｒ ｅ ｍａ ｔ ｕ ｒ ｉ ｔ ｙ ｉ ｎ ｓ ｍａ ｌ ｌ ｐａ ｒ ｔ ｓ ｂｙ ｕ ｓ ｉ ｎｇ ｄ ｉ ｖ ｅ ｒ ｓ ｅ ｐｏ ｐｕ ｌ ａ ｔ ｉ ｏ ｎ ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ ｉ ｎ ｑ ｕ ａ ｎｔ ｕ ｍ ｓ ｐａ ｃ ｅ ａ ｎ ｄ ｉ ｍｐ ｏｓ ｉ ｎｇ ｄｉ ｆ ｆ ｅ ｒ ｅ ｎｔ ｃ ｈａ ｏ ｔ ｉ ｃ ｐｅ ｒ ｔ ｕｒ ｂａ ｔ ｉ ｏ ｎ ｏ ｎ ｅ ａ ｃ ｈ ｕ ｎｉ ｔ ｗｈ ｉ ｃ ｈ ｄ ｅ ｐｅ ｎｄ ｓ ｉ ｔ ｓ ｆ ｉ ｔ ｎｅ ｓ ｓ ｉ ｎ ｑ ｕａ ｎ ｔ ｕｍ ｖ ａ ｒ ｉ ａ ｔ ｉ ｏ ｎ． Ｔｈｅ ａ ｌ ｇ ｏｒ ｉ ｔ ｈ ｍ ａ ｌ ｓ ｏ ｃ ａ ｎ ｐ ａ ｒ ｔ ｉ ａ ｌ ｌ ｙ ｉ ｍｐ ｒ ｏｖ ｅ ｏｐｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏｎ ａ ｂ ｉ ｌ ｉ ｔ ｙ，ｉ ｎｃ ｒ ｅ ａ ｓ ｅ ｔ ｈｅ ｃ ｏ ｎｖ ｅ ｒ ｇ ｉ ｎｇ ｓ ｐ ｅ ｅ ｄ ａ ｎｄ ｔ ｒ ａ ｎ ｓ ｍｉ ｔ ｔ ｈ ｅ ｉ ｎｆ ｏ ｒ ｍａ ｔ ｉ ｏｎ ｏ ｆ ｏ ｐｔ ｉ ｍａ ｌ ｕ ｎｉ ｔ ｔ ｏ ｎ ｅ ｘ ｔ
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
量子克隆进化算法刘 芳,李阳阳(西安电子科技大学计算机学院,陕西西安710071) 摘 要: 本文在量子进化算法的基础上结合基于克隆选择学说的克隆算子,提出了改进的进化算法———量子克隆进化策略算法(QCES ).它既借鉴了量子进化算法的高效并行性又利用克隆算子来代替其中的变异和选择操作,以增加种群的多样性,避免了早熟,且收敛速度快.本文不仅从理论上证明了该算法的收敛,而且通过仿真实验表明了此算法的优越性.关键词: 克隆算子;进化算法;量子克隆进化策略中图分类号: T N957 文献标识码: A 文章编号: 037222112(2003)12A 22066205Quantum Clonal Evolutionary AlgorithmsLI U Fang ,LI Y ang 2yang(Institute o f Computer ,Xidian University ,Xi ’an ,Shaanxi 710071,China )Abstract : Based on the combining of the quantum ev olutionary alg orithms (QE A )with the main mechanisms of clone ,an im 2proved ev olutionary alg orithm —quantum clonal ev olutionary strategies (QCES )was proposed in this paper.By adopting the high 2effec 2tive parallelism of QE A and replacing clone operator by mutation and selection of the classical ev olutionary alg orithms (CE A ),it has better diversity and the converging speed than CE A and av oided prematurity.The convergence of the QCES is proved and its superiori 2ty is shown by experiments in this paper.K ey words : clone operator ;ev olutionary alg orithm ;quantum clonal ev olutionary strategies1 引言 计算是人类思维能力的最重要的方面之一,计算能力的提高与人类文明进步息息相关.从古老的算盘到现代的超级计算机,人类的计算技术实现了革命性的突破.综观当今,计算机的广泛应用已经并且仍在继续改变着我们的世界.一方面,人们为计算机的神奇能力所倾倒.另一方面,人们也为它无力完全满足实际的需要而烦恼.因此,加速计算机的运算速度以提高计算机的运算能力成为计算机科学的中心任务之一.如何加快计算机的运算能力呢?这一问题大体可以从两个方面着手解决.一是制造更为先进的计算机硬件,另一则是设计恰当的计算机运算流程,后者可以称之为“算法”.一类模拟生物进化过程与机制来求解问题的自组织、自适应人工智能技术即进化计算(包括用于机器学习问题的遗传算法,优化模型系统的进化规划和用于数值优化问题的进化策略)的出现为我们寻找快速算法提供了新思路.进化计算是一种仿生计算,依照达尔文的自然选择和孟德尔的遗传变异理论,生物的进化是通过繁殖、变异、竞争、选择来实现的,进化算法就是建立在上述生物模型基础上的随机搜索技术.我们所熟悉的遗传算法(G enetic alg orithms )[1],它通过模拟达尔文的“优胜劣汰,适者生存”的原理鼓励好的个体,通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体,同时寻找更好的个体,由此来模仿一切生命与智能的产生与进化过程.理论上已经证明:进化算法能从概率的意义上以随机的方式寻求到问题的最优解;但在实际应用当中随着问题的复杂和海量的数据量,也出现了一些不尽人意的情况,主要表现在:计算后期解的多样性差即易造成早熟,收敛速度慢等缺点.因此,为克服上述缺点关键是构造性能良好的进化算法.在改进的进化算法中,有些是将传统寻优算法与遗传算法相结合提出了混合遗传算法[2,3],有些则另辟蹊径提出了新颖的学习算法———量子进化算法[4]和免疫进化算法[5],量子力学是20世纪物理学最惊心动魄的发现之一,量子计算是物理理论与计算机的成功结合,在量子体系中,一位的信息位不在是经典的1比特,而是由两个本征态的任意叠加态所构成即称之为量子比特位(qubit ),例如一个n 位二进制的串在量子体系中就可同时表示2n 个信息,而量子计算机对每个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的结果,这种计算称之为量子并行计算[6].正是量子的收稿日期:2003209210;修回日期:2003212210基金项目:国家自然科学基金(N o.60133010);国家高技术研究发展计划(863计划)(N o.2002AA135080)第12A 期2003年12月电 子 学 报ACT A E LECTRONICA SINICA V ol.31 N o.12ADec. 2003并行性使得原来传统计算机无法解决的复杂问题以惊人的速度得以解决,但在量子计算机尚未构成的情况下,为了充分利用量子计算的高效并行性,本文借用了量子进化算法中的量子编码,继承了免疫克隆策略中的克隆算子将二者相结合,提出了量子克隆进化策略算法,并将其应用于函数优化中,与传统进化算法相比较,它具有收敛速度快、寻优能力强的特点.2 基本概念 我们知道,经典计算机的存储单元是比特,它只有两种状态,或者为0,或者为1.而量子计算机最基本的存储单元是量子比特(qubit),它是任何一个有二维Hilbert态空间的量子体系[6],它的态空间有两个基,记为|0〉和|1〉[6].与经典计算机中的比特不同的是,量子比特的态可以为任意叠加的态:α| 0〉+β|1〉,其中α和β为满足归一化条件|α|2+|β|2=1的任意复数,且称之为概率幅,其平方表示在任何基态出现的概率.由此可得到:如果有n位的量子位,可同时表示2n个状态(即2n个信息),因而在对量子比特计算时,一次运算相当于对2n个状态同时操作,这就是量子并行性的由来.所以,一个量子比特所包含的信息要比经典的比特多.量子算法是相对于经典算法而言的,它最本质的特征就是充分利用了量子态的叠加性和相干性,以及量子比特之间的纠缠性[6],它是量子力学直接进入算法理论的产物.而量子算法与经典算法最主要的区别就是它具有量子并行性.我们也可以从概率算法去认识量子算法,在概率算法中,系统不再处于一个固定的状态,而是对应于各个可能状态有一个几率,即状态几率矢量.如果知道初始状态几率矢量和状态迁移矩阵,通过状态几率矢量和状态转移矩阵相乘可以得到任何时刻的几率矢量.量子算法与此类似,只不过需要考虑量子态的几率幅,因为它们是平方归一的,所以几率幅相对于经典几率有N倍的放大,状态转移矩阵则用Walsh2Hadamard变换、旋转相位操作等酉正变换实现.量子算法作为控制量子计算机运行的程序,显示出高效的运算能力,但目前量子计算机尚未投入应用,只是处在试验模型上,为了更好的利用量子的并行计算,使其在传统的计算机上行之有效,有人将量子比特引入到进化算法中,提出了新颖的学习算法量子进化算法,下面给出它的具体步骤.3 量子进化算法机理分析311 量子比特染色体进化算法的常用编码方式有二进制、十进制和符号编码.在量子进化算法中,采用了一种特殊的编码方式———量子比特编码,即用一对复数来表示一个量子比特,这也正是此算法高效性的所在.一个具有m个量子比特位的系统(即为一个量子染色体)可以描述为:α1α2…αmβ1β2…βm(1)其中,如前所述,αi和βi要满足归一化条件.这种表示方法可以表征任意的线性叠加态,例如一个具有如下三对概率幅的3量子比特系统:121121232(2)则系统的状态可以表示为:122000〉+322001〉+122100〉+322101〉(3)上式表示状态|000〉,|001〉,|100〉,|101〉出现的概率分别是1/ 8,3/8,1/8,3/8.由此我们很清楚的看到一个3量子比特系统表示了四个状态叠加的信息,即它同时表示出四个状态的信息.因此通过使用量子比特染色体增加了算法的解的多样性.如在上例中,一个量子染色体足以表示四个状态,而在传统进化算法中至少需要四个染色体(000),(001),(100),(101)来表示;同时此算法也具有好的收敛性,随着α,β趋于1或0,量子比特染色体收敛于一个状态,这时多样性消失,算法收敛.312 量子进化算法(QEA)QE A是一种和进化算法近似的概率算法,种群由量子染色体构成,在第t代的染色体种群为Q(t)={q t1,q t2,…,q t n},其中n为种群大小,t为进化代数,m为量子比特染色体的比特数,q t j为定义如下的染色体:q t j=αt1αt2…αt mβt1βt2…βt m, j=1,2,…,n(4)下面介绍量子进化算法(QE A)的一般步骤:①初始化进化代数:t=0;②初始化种群Q(t);(即初始时赋予概率幅为[-1,1]的实数)③由Q(t)生成P(t);④个体交叉、变异操作,生成新的P(t);⑤评价群体P(t)的适应度,保存最优解;⑥停机条件判断:当满足停机条件时,输出当前最优个体,算法结束,否则继续;⑦更新Q(t),t=t+1,转到③;在此算法中值得指出的是,第③步和第⑦步,其中Q(t)为量子染色体种群,P(t)为二进制染色体种群,在第t代中P(t) ={x t1,x t2,…,x t n},每个二进制解x t j(j=1,2,…,n)是长度为m 的二进制串,它是以|αt i|2或|βt i|2(i=1,2,…,m)为概率选择得到的.“由Q(t)生成P(t)”具体操作如下:随机产生一个[0,1]数,若它大于|αt i|2,取值1,否则取值0.在“更新Q(t)”中,由三种方法:①传统意义上的交叉、变异操作;②随机产生概率幅值;③根据量子的叠加特性和量子跃迁的理论,可以运用一些合适的量子门[6]变换来产生新的Q(t),在本文算法中只采用第二种即随机产生的方法来更新.很显然,由于在量子进化算法中采用量子比特染色体,使得一个m位的二进制串(染色体)在没通过观察之前,携带了2m个染色体的信息,这既保持了群体的多样性,又加快了收敛速度(量子的并行性).本文算法中借鉴了基于细胞克隆选择学说的克隆算子[5],它可有效解决多峰值函数优化,下面给出它的理论构架.7602第 12A 期刘 芳:量子克隆进化算法4 克隆算子 如前所述,进化算法在解决优化问题时虽具有简单、通用、鲁棒性等特点,但在搜索后期由于其算法的盲目性和随机性,就会出现退化早熟现象.为了防止这类现象的发生,就是要增大优良个体的比例减少坏个体的不良影响,即利用有用信息来指导进化.基于此杜海峰等人提出了免疫克隆策略算法[5],算法中主要提出了克隆算子,包括三个步骤:克隆、克隆变异和克隆选择.其抗体群的状态转移情况可以表示成如下的随机过程:C s:A(k)cloneA′(k)mutationA″(k)selectionA(k+1)值得说明是的:抗原、抗体、抗原和抗体之间的亲合度分别对应优化问题的目标函数和各种约束条件、优化解、解与目标函数的匹配程度.克隆算子就是依据抗体与抗原的亲合度函数f(3),将解空间中的一个点a i(k)∈A(k)分裂成了q i 个相同的点a′i(k)∈A″(k),经过克隆变异和克隆选择后获得新的抗体.其实质是在一代进化中,在候选解的附近,根据亲合度的大小,产生一个变异解的群体,从而扩大搜索范围.很显然,在克隆算子中,为了保持解的多样性而扩大空间搜索范围,采取对父代进行克隆复制的策略,其解空间变大是以计算时间增长为代价的,由于量子进化算法具有量子并行运算的特点.因此,本文将二者相结合,提出了量子克隆进化策略算法,是一种解决多峰值函数优化问题行之有效的快速方法.5 量子克隆进化策略算法(QCES)511 量子克隆进化策略算法本算法仍然借用量子进化算法中的量子比特染色体,并对量子染色体进行克隆、变异、选择,由于量子染色体携带了多个个体的信息,对量子染色体进行进化操作,程序的额外开销少.下面给出算法的具体步骤:①初始化进化代数:t=0;②初始化种群Q(t):αt i=1/2;(初始时以等概率出现)③克隆Q(t)生成Q′(t);④对Q′(t)进行高斯变异生成Q″(t);⑤通过选择压缩Q″(t)生成Q(t+1);⑥评价种群Q(t+1)的亲合度,保存最优解;⑦停机条件判断:当满足停机条件时,输出当前最优个体,算法结束,否则继续;⑧t=t+1,转到③;值得指出的是,本算法中克隆采取的是等比例复制,克隆选择是在克隆群体中选择亲合度最好的保留下来,并且要保证经选择后群体规模与克隆前一样.在本算法中对于多峰值函数优化问题亲合度采用目标函数值来度量.计算种群Q的亲合度采用前面提到的量子进化算法中第③步生成二进制染色体后解码求函数值.512 算法的收敛性定理1 量子克隆进化策略算法的种群序列{X k,kΕ0}是有限齐次马尔可夫链.证明 由于QCES采用量子比特染色体Q,对于CE A,染色体的取值是离散的0、1,假设染色体长度为L,种群规模为N,种群所在的状态空间大小是N32L.由于Q的取值是连续的,所以理论上种群所在的状态空间是无限的,但另一方面,实际运算中Q是有限精度的,设其维数为v,则种群所在的状态空间大小为N3v L,因此种群是有限的,而算法中采用的克隆、克隆变异、克隆选择都与k无关(由文献[5]给出的定义保证),所以X k+1仅与X k有关,即{X k,kΕ0}是有限齐次马尔可夫链.证毕.设X k={x1,x2,…,x N},下标k表示进化的代数,X k表示在第k代时的一个种群,x i表示第i个个体.设f是X k上的亲合度函数其中,令s3{x|maxx∈X kf(x)=f3}(5)称s3为最优解集,其中f3为全局最佳值,则有如下定义.定义1 设f k=maxxi∈Xk{f(x i):i=1,2,…,N}是一个随机变量序列,该变量代表在时间步k状态中的最佳的亲合度.如果当且仅当limk→∞P{f k=f3}=1(6)则称算法收敛.即表明当算法迭代到足够多的次数后,群体中包含全局最优解的概率接近1.定理2 对于量子克隆进化策略算法马尔可夫链序列的种群满意值序列是单调不减的,即对于任意的kΕ0,有f (X k+1)Εf(X k),即种群中的任何一个个体都不会退化.证明 显然,由于在本算法中采用保留最优个体来进行克隆选择,因此保证了每一代个体都不会退化.定理3 量子克隆进化策略算法是以概率1收敛的.证明 由上所述,本算法的状态转移由马尔可夫链来描述.我们将规模为N的群体认为是状态空间S中的某个点,用s i∈S表示s i是S中的第i个状态,相应本算法s i={x1, x2,…,x N},显然X i k表示在第k代时种群X k处于状态s i,其中随机过程{X k}的转移概率为p ij(k),则p ij(k)=p{X j k+1/X i k}(7)下面给出p ij(k)两种特殊情况:设I={i|s i∩s3≠ }(1)当i∈I,J|I时:由于式(8)和定理2使得p ij(k)=0(8)即当父代出现最优解时不论经历多少代的进化最优解都不会退化.(2)当i|I,j∈I时:由定理2可知:f(X j k+1)>f(X i k),所以p ij(k)>0(9)在讨论了转移概率的两种特殊情况后,我们来证明式(6).设p i(k)为种群X k处在状态s i的概率,p k=∑i|Ip i(k),则由马尔科夫链的性质可知: p k+1=∑si∈S∑j|Ip i(k)p ij(k)=∑i∈I∑j|Ip i(k)p ij(k)+∑i|I∑j|Ip i(k)p ij(k)(10)8602 电 子 学 报2003年由于 ∑i |I ∑j ∈Ip i (k )p ij (k )+∑i |I ∑j |Ip i(k )p ij(k )=∑i |Ip i(k )=p k (11)因此∑i |I ∑j |Ip i(k )p ij (k )=p k -∑i |I ∑j ∈Ip i(k )p ij (k )(12)把式(12)代入式(10),再利用式(9)和式(8),则:0Φp k +1<∑i ∈I ∑j |Ip i(k )p ij(k )+p k =p k因此:lim k →∞p k =0(13)又因为lim k →∞P{f k =f 3}=1-lim k →∞∑i |Ip i(k )=1-lim k →∞p k 和式(13)可知lim k →∞P{f k =f 3}=1(14)即所有包含在非全局最优状态中的概率收敛于0.则包含在全局最优状态中的概率收敛为1.证毕.6 仿真试验 本算法不仅能够保证种群中解的多样性,而且具有很强的搜索能力,所以量子比特染色体和克隆算子的引入提高了进化计算处理多峰函数优化问题的能力.以下面三个测试函数[1,7,8]为例,比较量子克隆进化策略算法(QCES )与传统进化算法(CE A )的空间搜索性能与收敛速度. f 1=1+x sin (4πx )-y sin (4πy +π)+sin (6x 2+y 2)6x 2+y 2+01000000000000001, x ,y ∈[-1,1]f 2=x 2+y 2-013cos3πx +013cos4πy +013, x ,y ∈[-1,1]f 3=nA +∑ni =1(x 2i-A cos (2πx i )), x i ∈[-5112,5112]函数f 1是文献[8]给出的测试函数,它是一个多峰值函数,在其定义域内[-1,1]有多个局部极值点.函数f 2是Bo 2hachevsky 的测试函数3,最优解为-0.1848.函数f 3称为Rast 2rigin 函数,它是一个多峰值函数,在上述定义域内有多个局部最小点,其中最优解为0.为了便于比较,我们针对两种算法采用统一的参数,精度取10-3,对函数f 1和f 2种群规模为50,变异概率为011,最大进化代数为500;对函数f 3种群规模为50,变异概率也为011,最大进化代数为1000.图1中给出分别采用QCES 和CE A 对函数f 1和f 2一次优化的结果(特别指出为了直观地反映最优值的分布情况特将函数f 2取反绘出,且图1中的(b )、(d )的进化的代数为50的情况),其中“3”表示最终的最优值,从图1中反映出QCES 解集的多样性要明显优于CE A.图2中给出一次运行结果的收敛性比较(其中实线为QCES 、虚线为CE A ),从中也反映出QCES 具有较快的收敛性.表1中给出独立10次试验的统计结果,发现由于采用量子比特染色体,在种群规模较小时仍能获得满意的解,这样在实际应用中可节省计算的时间和空间.对于函数f 3,当n =6时,传统的进化算法根本无法收敛到最优解,故在表1的相应框中用“/”来表示无法统计.在表1中可以看到QCES 一次运行的时间有所增加,这是由于本算法比传统的进化算法多了两步(即量子染色体生成普通二进制染色体和克隆复制),但解的性能有了明显提高.图1 不同算法对函数f 1和f 2的优化结果图2 不同算法的收敛性能比较表1 采用的优化方法函数f 1f 2f 3(n =6)种群数105010501050QCES找到最优解次数10101010810一次运行的时间(s )0.180.340.140.328.4650.12CE A找到最优解次数3646//一次运行的时间(s )0.140.260.120.22//7 结论与讨论 本文借鉴了量子进化算法中的量子比特染色体并与人工免疫系统中的克隆算子相结合提出了一种学习算法———量子克隆进化策略算法.通过理论分析与仿真试验表明:该算法与传统的进化算法相比,保持了解的多样性,有效克服了早熟问题、而且收敛速度快.参考文献:[1] 陈国良,王煦法,庄镇泉,王东生.遗传算法及其应用[M].北京:人民邮电出版社,1997.[2] Ahuja Ravindra K.G reedy genetic alg orithm for the quadratic assign 29602第 12A 期刘 芳:量子克隆进化算法ment problem [J ].C om puters and Operations Research ,E lsevier Sci 2ence Ltd ,2000,10(27):917-934.[3] Y U H ong 2mei ,Y AO Ping 2jing.C ombined genetic alg orithm/simulatedammealing alg orithm for large 2scale system energy integration [J ].C om puters and Chemical Engineering ,E lsevier Science Ltd ,2000,8(24):2023-2035.[4] 杨淑媛,刘芳,焦李成.量子进化策略[J ].电子学报,2001,29(12A ):1873-1877.[5] 焦李成,杜海峰.人工免疫系统进展与展望[J ].电子学报,2003(10):1540-1548.[6] 戴葵,宋辉,刘芸,谭明峰.量子信息技术引论[M].湖南长沙:国防科技大学出版社,2001.[7] 杜海峰,王孙安.基于ART —人工免疫网络的数据浓缩方法研究[J ].模式识别与人工智能,2001,14(4):401-405.[8] 潘正军,康立山,等.演化计算[M].北京:清华大学出版社,1998.作者简介:刘 芳 女,1963年生于北京市,现为西安电子科技大学教授,主要研究领域包括:网络智能信息处理与模式识别.李阳阳 女,1979年生于河南省开封市,现为西安电子科技大学在读博士生,主要研究领域包括括:进化算法、模式识别与数据挖掘等.0702 电 子 学 报2003年。