一种带有连接学习的量子演化算法

xiaoxiao2021-2-25  271

一种带有连接学习的量子演化算法
【技术领域】
[0001] 本发明涉及一种量子演化算法,特别是关于一种带有连接学习的量子演化算法。
【背景技术】
[0002] 量子演化算法(QEA)仅仅使用了量子计算的一些概念,其本质是在经典计算机上 运行的多模型演化算法,包括量子比特,量子个体,量子门以及坍缩个体等。与传统的演化 算法相比,QEA最主要的特点是存储信息的基本单元不同。传统演化算法的基本单元是比 特,一个比特只能处在非0即1的状态。QEA算法中借鉴了量子计算的概念,它使用量子比特 作为基本信息单元。一个量子比特在量子计算过程中,处在一个叠加态中,即同时处在不同 的本征态上。只是在观测的时候会坍缩到一个本征态上。在QEA算法中,可以将其中的量子 比特看作是一个二项分布。其定义如下:
[0003] Φ> = α|〇>+β|?>,
[0004] 其中,α和β在量子演化算法中被限制为实数。α和邱勺模平方分别表示0或者1的概 率。因此α和β要满足归一化条件。用α和β作为X轴和y轴,在这种表示下,量子比特可以看做 是在单位圆第一象限部分上的一个向量。为了改变量子比特的状态,可以使用量子门。其本 质是作用在量子比特上的一个算子。定义如下:
[0005]
[0006] 在归一化条件下,量子门通过下式改变α和邱勺值。
[0007]
[0008] Han和Kim在QEA使用的量子门基础上,提出了改进的量子门称作Ηε门。Ηε门可以防 止量子个体收敛。一旦量子个体收敛,它将不会再改变状态,这会导致算法进入局部最优解 而无法改变。具体地,Ηε门在改变量子个体时,同时会阻止量子比特演化I 0>或I 1>两个状态 上,也就是防止量子个体中的分量演化到α = 0,β=1或者β=1,α = 〇这两个极限状态上。参 数α和β被限制?
t中,如图2所示,实验表明,使用Ηε门的QEA算法可以取得更好 的结果。量子个体由量子比特组成,每个量子个体都可以写成一组量子比特的形式,如下:
[0009]
[0010] 单变量的分布估计算法简单高效,但是概率向量的变量相互独立导致它不能处理 带有复杂变量关系的问题。这限制了单变量分布估计算法的应用范围。如何设计一个有效 的方法,既不失概率向量简单高效的优点又能探测并利用变量关系成为一个重要的研究目 标。

【发明内容】

[0011] 针对上述问题,本发明的目的是提供一种带有连接学习的量子演化算法,该算法 可以识别出并利用变量之间的连接关系,实现不同量子个体之间进行信息交换,有效提高 算法效率。
[0012] 为实现上述目的,本发明采取以下技术方案:一种带有连接学习的量子演化算法, 其特征在于,该算法由若干个计算单元构成,每一个计算单元都包括量子个体Qi、坍缩个体 Ci和吸引子Ai,其中,i表示计算单元的序号,i = 1,2,…,N,N为自然数,所述算法步骤如下: 1)初始化所有计算单元中的量子个体Qi,将所有的量子化个体都初始化为相同的值;2)对 第i个计算单元,通过直接采样量子个体&和概念引导组合算子得到坍缩个体Q,并利用目 标函数评价坍缩个体(^以得到其适应值?=(以(^)4(〇 2),一4((^));其中,概念引导组合 算子简称为CGC算子;3)根据步骤2)中得到的坍缩个体,将吸引子Μ赋值为对应的坍缩个 体(^,完成计算单元初始化;4)将量子化个体的信息量构成的信息度量矩阵W初始化为0矩 阵;5)采用坍缩态生成算法由量子化个体生成坍缩个体Q,在所有的坍缩个体(^中,有ΝΧρ 个坍缩个体Ci采样于CGC算子生成的临时概率向量,其余的ΝX (1-ρ)个坍缩个体Ci直接采样 于对应的量子个体;其中,P为使用CGC算子作为生成算子的概率;6)所有计算单元中的量子 个体&和吸引子仏都根据吸引子仏的适应值f(A〇和坍缩个体(^的适应值以⑴进行更新,从 吸引子仏计算中适应度最好的坍缩个体C 1:如果f(A〇等于或者优于fXCO,则表示吸引子仏 优于当前的坍缩个体G,那么不改变该吸引子仏,并用该吸引子六 1继续指导量子个体&的演 化;否则,将吸引子心替换为当前的坍缩个体匕,更新信息度量矩阵W=(wu)和计算单元;7) 重复步骤6),当达到预先设定的最大迭代次数后,则完成量子演化过程。
[0013] 进一步,所述步骤5)中,所述坍缩态生成算法如下:(1)随机选择两个量子个体Qr、 Qs,将两个量子个体Qr、Qs米用CGC算子生成临时量子个体Qtemp; (2)通过对临时量子个体Qtemp 采样得到一个临时坍缩个体Ctemp,采用最临近替换策略,通过将新生成的临时坍缩个体Ctemp 替换最相近的一个坍缩个体来获取最相近的坍缩个体;即判断该临时坍缩个体Ctemp分别与 两个量子个体Q r、Qj^应的坍缩个体Cr、Cs之间的海明距离DistH(Cr,Ctemp)、DistH(Cs,C temp), 若海明距离0丨8加(&,(:_)〈0丨8加((^,(^1)),则该临时坍缩个体(^ 1)即为量子个体^对应的 坍缩个体Cr,反之,该临时坍缩个体Cte?p即为量子个体Q s对应的坍缩个体Cs。
[0014] 进一步,所述步骤6)中,所述计算单元更新方法如下:将量子个体&、吸引子仏和坍 缩个体Ci的第m个分量分别记为a m、#和6",判断两个分量4?和0"是否不相同,并且分 量f是否为1,若两个分量#和<了不相同且分量4"为1,则根据将量子个体分量^旋转Δ θ ;反之,将量子个体分量am旋转-δ θ。
[0015] 进一步,所述量子个体分量的旋转公式为:
[0016]
[0017] 共Τ λ 〇乃腿符用皮。
[0018] 本发明由于采取以上技术方案,其具有以下优点:1、本发明采用概念引导组合算 子,使得量子个体可以学习变量连接关系,避免了高阶模型所需的较多的计算资源。2、本发 明由于采用了最临近替换的策略,生成坍缩个体过程本身就包含了在不同量子个体之间交 换信息的过程。虽然去除了 QEA中的同步过程,QEALL还是可以实现信息的交换。3、本发明采 用的最临近的替换策略实质上是一种小生境方法,这个方法的引入可以有效提高算法的效 率。
【附图说明】
[0019] 图1是本发明的整体流程示意图;
[0020] 图2是现有技术中的量子门示意图。
【具体实施方式】
[0021] 下面结合附图和实施例对本发明进行详细的描述。
[0022] 如图1所示,本发明提供一种带有连接学习的量子演化算法,该算法由若干个计算 单元构成,每一个计算单元都包括量子个体(Quantum Individual )Qi、i丹缩个体 (Collapsed Individual)Ci和吸引子(Attractor)Ai,其中,i表示计算单元的序号,i = l, 2,…,N,N为自然数。本发明步骤如下:
[0023] 1)初始化所有计算单元中的量子个体Qi,将量子个体Qi中量子比特af和贫初始化 为l/VI,即将所有的量子化个体都初始化为相同的值;其中i表示计算单元的序号,即第i 个量子个体;j表示第j个基因位置。
[0024] 2)对于第i个计算单元,通过直接采样量子个体&和概念引导组合算子(CGC算子) 得到坍缩个体Q,并利用目标函数评价坍缩个体(^以得到其适应值F= (f (Cd,f (Q2),…,f (Qn) ) 〇
[0025] 3)根据步骤2)中得到的坍缩个体G,将吸引子仏赋值为对应的坍缩个体匕,完成计 算单元初始化。
[0026] 4)由于将所有的量子化个体都初始化为相同的值,因此所有量子化个体所具有的 信息量也是相同的,故将量子化个体的信息量构成的信息度量矩阵W初始化为0矩阵;其中, 信息度量矩阵W=(wi,j) = (0)。
[0027] 5)采用坍缩态生成算法由量子化个体生成坍缩个体G,在所有的坍缩个体匕中,有 NXp个坍缩个体Ci采样于CGC算子生成的临时概 率向量,其余的NX(l-p)个坍缩个体Ci直接 采样于对应的量子个体;其中,P为使用CGC算子作为生成算子的概率;
[0028]其中,坍缩态生成算法如下:
[0029] (1)随机选择两个量子个体Qr、Qs,根据下式将两个量子个体Q r、Qs采用CGC算子生 成临时量子个体Qtemp ;
[0030]
[0031] 式中,%基因位j的信息 熵,其中:
[0032]
[0033]
[0034] 上式中,%、片分别表示种群中基因位j中0和1的概率;Μ为种群的大小,
[0037] 式中,火。、'分别表示除了第k个量子个体后,所剩下种群中基因位j中0和1的 概率;V表示每个量子个体所代表的虚拟种群个数。
[0038] (2)通过对临时量子个体Qtemp采样得到一个临时坍缩个体Ctemp,采用最临近替换策 略,通过将新生成的临时坍缩个体C temp替换最相近的一个坍缩个体来获取最相近的坍缩个 体;即判断该临时坍缩个体Ctemp分别与两个量子个体Q r、Qdi应的坍缩个体Cr、Cs之间的海明 距离 018加((^,(^_)、018加((^,(^_),若海明距离018加((^,(^_)〈018加((^,(^_),则该临 时坍缩个体Ctemp即为量子个体Qr对应的坍缩个体Cr,反之,该临时坍缩个体C te?p即为量子个 体Qs对应的坍缩个体匕。通过使用CGC算子,本发明可以识别出并利用变量之间的连接关系。
[0039] 由于临时坍缩个体Ct_是来自两个计算单元中的量子个体,因此本发明采用最临 近替换策略,因为坍缩个体为二进制编码,因此使用海明距离作为其相似性的度量,相邻两 个参数X1、X2的海明距离DistH(Xl,X2)为:
[0040]
[0041] (3)重复步骤(2)NXp。次,得到NXp。由CGC算子生成的坍缩个体;其余NX(l-p)个 计算单元中的坍缩个体并没有更新,通过直接采样其对应的量子个体进行更新。
[0042] 6)所有计算单元中的量子个体&和吸引子六1都根据吸引子适应值f(Ai)和坍 缩个体匕的适应值进行更新,从吸引子Μ计算中适应度最好的坍缩个体匕,即为:如果 fUO等于或者优于,则表示吸引子六1优于当前的坍缩个体G,那么不应改变该吸引子 Ai,并用该吸引子六1继续指导量子个体&的演化;否则,应将吸引子Ai替换为当前的坍缩个 体Ci,更新信息度量矩阵W = (Wi, j)和计算单元。
[0043] 其中,计算单元更新方法如下:将量子个体&、吸引子仏和坍缩个体Q的第m个分量 分别记为0"、<'和CT,判断两个分量和C是否不相同,并且分量< 是否为1,若两个 分量if1和?"不相同且分量#为1,则根据下式对量子个体分量旋转△ Θ;反之,根据下式 对量子个体分量旋转-ΛΘ:
[0044]
[0045] 其中Δ Θ为旋转角度。
[0046] 7)重复步骤6),当达到预先设定的最大迭代次数后,则完成量子演化过程。
[0047]综上所述,本发明中坍缩个体的产生过程主要有三个作用:首先,通过引入概念引 导组合算子,使得量子个体可以学习变量连接关系。其次,由于采用了最临近替换的策略, 生成过程本身就包含了在不同量子个体之间交换信息的过程。虽然去除了 QEA中的同步过 程,QEALL还是可以实现信息的交换。最后,最临近的替换策略实质上是一种小生境方法,这 个方法的引入提高了算法的效率。
[0048]上述各实施例仅用于说明本发明,各个步骤都是可以有所变化的,在本发明技术 方案的基础上,凡根据本发明原理对个别步骤进行的改进和等同变换,均不应排除在本发 明的保护范围之外。
【主权项】
1. 一种带有连接学习的量子演化算法,其特征在于,该算法由若干个计算单元构成,每 一个计算单元都包括量子个体Qi、i丹缩个体Ci和吸引子Ai,其中,i表示计算单元的序号,i = 1,2,…,N,N为自然数,所述算法步骤如下: 1) 初始化所有计算单元中的量子个体Q1,将所有的量子化个体都初始化为相同的值; 2) 对第i个计算单元,通过直接采样量子个体Q1和概念引导组合算子得到坍缩个体C1, 并利用目标函数评价坍缩个体匕以得到其适应值F = W(C1),f (Q2),…,f (Qn));其中,概念 引导组合算子简称为CGC算子; 3) 根据步骤2)中得到的坍缩个体C1,将吸引子A1赋值为对应的坍缩个体(^,完成计算单 元初始化; 4) 将量子化个体的信息量构成的信息度量矩阵W初始化为O矩阵; 5) 采用坍缩态生成算法由量子化个体生成坍缩个体C1,在所有的坍缩个体(^中,有NXp 个坍缩个体C i采样于CGC算子生成的临时概率向量,其余的NX (Ι-p)个坍缩个体Ci直接采样 于对应的量子个体;其中,P为使用CGC算子作为生成算子的概率; 6) 所有计算单元中的量子个体Q1和吸引子仏都根据吸引子仏的适应值f(M和坍缩个体 匕的适应值f (C1)进行更新,从吸引子仏计算中适应度最好的坍缩个体C1:如果f (A1)等于或 者优于f (C1),则表示吸引子六1优于当前的坍缩个体C1,那么不改变该吸引子仏,并用该吸引 子八 1继续指导量子个体&的演化;否则,将吸引子A1替换为当前的坍缩个体(^,更新信息度 量矩阵W= (wi, j)和计算单元; 7) 重复步骤6),当达到预先设定的最大迭代次数后,则完成量子演化过程。2. 如权利要求1所述的一种带有连接学习的量子演化算法,其特征在于:所述步骤5) 中,所述坍缩态生成算法如下: (1) 随机选择两个量子个体Qr、Qs,将两个量子个体Qr、Qs采用CGC算子生成临时量子个体 Qtemp ; (2) 通过对临时量子个体Qtemp采样得到一个临时坍缩个体Ctemp,采用最临近替换策略, 通过将新生成的临时坍缩个体C temp替换最相近的一个坍缩个体来获取最相近的坍缩个体; 即判断该临时坍缩个体Ctemp分别与两个量子个体Qr、Qs对应的坍缩个体Cr、C s之间的海明距 离DistH(Cr,Ctemp)、DistH(Cs ,Ctemp),若海明距离DistH(Cr,Ctemp)〈DistH(Cs ,Ctemp),则该临时 坍缩个体Cte3mp即为量子个体Qr对应的坍缩个体Cr,反之,该临时坍缩个体C te?p即为量子个体 Qs对应的坍缩个体Cs。3. 如权利要求1或2所述的一种带有连接学习的量子演化算法,其特征在于:所述步骤 6)中,所述计算单元更新方法如下:将量子个体&、吸引子仏和坍缩个体C1的第m个分量分别 记为β"、<和Cf,判断两个分量OPCf是否不相同,并且分量#是否为1,若两个分量 4"和Cf不相同且分量4"为1,则根据将量子个体分量β"'旋转A Θ ;反之,将量子个体分量 0?旋转-ΑΘ。4. 如权利要求3所述的一种带有连接学习的量子演化算法,其特征在于:所述量子个体 分量的旋转公式为:其中△ Θ为旋转角度。
【专利摘要】本发明涉及一种带有连接学习的量子演化算法,其由若干个计算单元构成,每一个计算单元都包括量子个体、坍缩个体和吸引子,步骤为:初始化所有计算单元中的量子个体;对第i个计算单元,通过直接采样量子个体和概念引导组合算子得到坍缩个体,利用目标函数评价坍缩个体以得到适应值;根据坍缩个体将吸引子赋值为对应的坍缩个体,完成计算单元初始化;将量子化个体的信息量构成的信息度量矩阵初始化为0矩阵;采用坍缩态生成算法由量子化个体生成坍缩个体,部分坍缩个体生成临时概率向量,其余坍缩个体直接采样于对应的量子个体;所有计算单元中的量子个体和吸引子都根据吸引子的适应值和坍缩个体的适应值进行更新;当达到预先设定的最大迭代次数后,则完成量子演化过程。
【IPC分类】G06N3/12
【公开号】CN105488567
【申请号】CN201510854648
【发明人】徐华
【申请人】清华大学
【公开日】2016年4月13日
【申请日】2015年11月30日

最新回复(0)