量子免疫算法（共7篇）
量子免疫算法 篇1
1 引 言
模糊控制策略是解决非线性和复杂控制问题的一种有效的智能控制方法[1]。模糊控制器的设计通常需要专家经验并要对众多的参数进行整定以达到满意的控制效果。这样一个依赖于专家经验的人工寻优过程会给工程应用带来不便。目前, 很多学者致力于用进化算法来优化模糊控制器的参数[2,3,4], 但是很少有文献提出对控制决策表进行优化。控制决策表是模糊控制器的重要组成部分, 在实时控制中是影响控制效果的关键因素。另外, 用于参数优化的进化算法往往需要调整很多参数, 给优化的实现带来了难度。
基于传统粒子群算法 (Particle Swarm Optimization, PSO) 提出的量子粒子群算法 (Quantum-behaved PSO, QPSO) 具有计算机实现简单、鲁棒性强、可调参数少的优点。本文给出一种免疫量子粒子群算法 (QPSO-immune Algorithm, QPSO-IM) , 它根据系统所要达到的性能指标来优化模糊控制器中的控制决策表, 使模糊控制规则更加完善。该算法将免疫算子引入QPSO算法中, 在保留原算法优点的基础上提高了算法的全局搜索能力。模糊控制器和控制决策表的优化设计在SCON-2000模糊控制平台进行了工程化实现, 在对水箱液位模糊控制中取得了令人满意的控制效果。
2 模糊控制系统简介
常规模糊控制系统如图1所示, 其控制可分为模糊化、模糊推理和解模糊三步。
模糊化就是将基本论域上的精确量:误差e和误差变化率ec, 变换为量化论域上的模糊集的过程。模糊推理过程就是对模糊输入量根据制定的模糊规则和模糊推理方法进行模糊推理, 求出模糊输出量, 继而通过解模糊求得确定的控制量。为提高系统的实时性, 通常是根据上述过程离线计算出控制决策表用于控制。水箱液位模糊控制的控制决策表如表1所示。控制过程中, 根据输入信号e和ec查询控制决策表, 所得增量按比例转换后再施加于被控对象。
在系统投运时, 仅基于专家经验构成的控制决策表往往是不完善的, 还要对控制决策表进行参数整定以取得满意的控制效果。由表1可以看出, 控制决策表是一个13×15的实数矩阵, 其参数的人工整定不仅需要丰富的专家经验, 还要耗费大量时间。因此, 控制决策表的自动调整优化是一项具有实际意义的工作。
3 基于QPSO-IM算法的控制决策表优化
3.1 QPSO算法简介
传统粒子群算法将算法中的可行解看作没有重量和体积的粒子, 粒子在n维搜索空间中追随本身目前所找到的最优位置和整个粒子群所找到的最优位置进行迭代飞行[5]。
Sun等人从量子力学的角度提出了一种新的PSO算法模型——量子粒子群优化算法 (QPSO) 。研究结果证明, 在保证种群规模的情况下, QPSO算法的搜索能力优于PSO算法, 而且QPSO算法的参数少, 更容易实现控制[6]。设粒子i的当前位置为xi= (xi1, xi2, …, xin) ;粒子i所经历的最好位置为pi= (pi1, pi2, …, pin) ;整个粒子群所经历的最好位置为pg= (pg1, pg2, …, pgn) , 即搜索到的最优解。粒子根据式 (1) ～ (3) 进行迭代飞行, 达到迭代次数后飞行结束。
xij (t+1) =p′ij±β|mbestj-xij (t) |ln (1/u) (1)
其中,
mbest是各粒子本身所经历的最优位置的平均位置;φ和u是在[0, 1]上产生的相互独立的随机数;β为伸缩因子, 是QPSO算法中唯一的可调参数。式 (1) 中的正负号以相同概率随机产生。
3.2 人工免疫算子的引入
把QPSO算法中的粒子看作人工免疫系统中的抗体, 将免疫的思想引入QPSO算法可以提高算法的性能[7]。基于人工免疫原理, 浓度选择机制保证了粒子 (抗体) 的多样性从而提高了算法的全局搜索能力。设有N+M个粒子, 每个粒子的适应度值为f (·) , 则第i个粒子的浓度为:
从N+M个粒子中选择N个粒子以避免粒子过度集中, 第i个粒子的选择概率为:
另外, 接种机制用在QPSO中, 以保留最优粒子的形式提高算法的收敛速率[8]。
改进后的QPSO算法称为免疫量子粒子群算法 (QPSO-IM) 。
3.3 基于QPSO-IM算法的控制决策表优化
QPSO-IM算法流程如图2所示, 其实现步骤如下。
(1) 编码。
本文要优化的控制决策表是一个13×15的实数矩阵, 如表1所示。采用实数编码方式, 将该矩阵元素以行序组成一维向量, 作为一个粒子。若矩阵的第i行元素表示为aij, 则粒子编码为:
a1j, a2j, …, a13j (j=1, 2, …, 15)
可见, 每个矩阵的编码是一个195维的行向量, 所以控制决策表的优化是一个高维优化问题。
(2) 初始种群的生成。
本文对已经存在但控制效果欠佳的控制决策表1进行优化调整, 以达到满意的控制效果。因此, 没有必要在实数域内随机产生初始种群。而且, 随机产生的控制决策表几乎都无法达到控制目的, 进化中对它们的评价也就没有意义。因此, 初始种群可在表1的基础上产生。本文的方法是按表1编码的各位加上[-c, c]之间的随机实数, 由此产生初始种群, 在可行解空间范围内搜索最优解。正实数c的选取将影响算法的寻优能力。较大的c有助于提高算法的全局搜索能力;较小的c则有助于提高算法的局部搜索能力。在工程应用中, c的选取受制于控制量的约束范围。在执行机构允许范围内, c的选取可参考表1中的最大元素 (aij) max, 即:
c< (aij) max (i=1, 2, …, 13;j=1, 2, …, 15)
(3) 记忆库。
用于保存进化过程中的最优粒子, 记忆库在迭代过程中不断更新。
(4) 适应度值的确定。
本文采用时间与误差绝对值的乘积的积分 (ITAE) 来评价个体性能, 它综合反映了系统的超调量、上升时间以及过渡过程等性能指标[9], 如式 (6) 所示。
ITAE=∫
其中, 积分上限T的设定关系到能否对个体优劣进行有效区分。过小的T无法有效区分个体优劣程度;过大的T不仅过度放大了较差个体的劣势, 而且会增加计算机的计算量, 从而给算法实现带来困难。通常T可取调整ts的2～4倍。据式 (6) 可知, ITAE值较小的粒子具有较好的控制效果。为了使控制效果更好的粒子具有更大的适应度值, 我们将计算出的ITAE值进行转换, 然后用于浓度的计算。这里采用一种线性转换的方式来计算粒子的适应度, 如图3所示。
在进化过程中, 每一代粒子的适应度值由该粒子的ITAE值以及这一代粒子的最大ITAE值和最小ITAE值确定, 则ITAE值为x的个体的适应度值为:
这种变换令某一代的最差个体和最优个体的适应度值分别为0和1, 能够有效区分个体之间差异。需要指出的是, 该变换得出的适应度值仅在该代中有效, 不同代个体不能利用这种变换得出的值进行比较计算。不同代个体只需直接用ITAE值进行比较即可。
(5) 粒子更新的两种方式。
a.迭代更新。由式 (1) ～ (3) 产生N个新粒子;
b.重新生成M个新粒子。生成方式和初始种群的生成方式相同。
(6) 基于浓度的粒子选择。
用式 (4) 计算N+M个新粒子的浓度, 然后依概率公式 (5) 选择N个粒子组成新的群体。
(7) 接种疫苗。
用记忆库中的免疫记忆粒子替换粒子群中适应度较差的粒子。
(8) 结束条件。
达到预先设定的最大进化代数时寻优结束。
4 应用实例与结果分析
LTT三容液位控制实验装置是高等院校的教学实验设备, 主体由三个圆柱形容器罐、若干手动排水阀和一个蓄水池组成。用液位传感器检测容器水位, 用变频器调节泵的转速, 继而改变泵的供水量。本文在自行研制的SCON-2000先进控制系统的模糊控制平台上进行单容水箱液位模糊控制, 考察跟踪参考输入响应和负荷变化时的响应, 并将优化前后控制决策表的控制效果进行了对比。
初始种群规模N=50, 产生的方式是按表1的编码的各位加上[-2, 2]之间的随机数;每次迭代, 产生新粒子数M=10;伸缩因子β在迭代过程中从1.0到0.5线性下降;粒子的每位限定在[-7.5, 7.5]之间;取式 (6) 的积分时间T=4ts;每次迭代时, 选择种群中3个最差粒子替换为免疫记忆粒子;最大进化代数为200。本文同时利用SCON-2000先进控制系统的建模平台对水箱进行建模, 得到的水箱模型为:
优化后的控制决策表如表2所示。
在SCON-2000先进控制平台上对水箱液位进行实时控制, 设定液位为200 mm, 误差量化因子Ke=2.53, 误差变化率量化因子Kec=125, 控制量比例因子Ku=1, 模糊控制器采用增量形式。优化前后的响应曲线以及控制量曲线如图4、图5所示, 可见优化后的控制决策表性能比优化前有了很大的改善。
(1) 优化前, 系统响应的超调量为30%, 调节时间为3.5min;优化后, 系统响应的超调量为5%, 调节时间为2 min。
(2) 优化前, 系统响应的稳态波动在±25mm内;优化后, 系统响应的稳态波动在±10 mm以内。这表明优化后的控制决策表的精度更高。
(3) 在系统稳态时加入负荷扰动, 优化前的系统需要5.5min恢复稳态, 并有超调;优化后的系统仅用2 min就重新到达稳态, 且没有超调。这表明优化后系统响应具有更好的快速性和平稳性。
5 结束语
本文提出用QPSO-IM算法来优化模糊控制器中的控制决策表。算法实现简单, 可调参数少, 使模糊控制决策表的参数整定易于工程应用。实验结果表明:用QPSO-IM算法优化过的控制决策表明显改进了模糊控制器的性能, 从而达到了优化模糊控制器的目的。
参考文献
[1]孙绪刚, 王丽荣.模糊控制在聚合装置的应用[J].化工自动化及仪表, 2001, 28 (4) :29-32.
[2]LINKENS D A, NYONGESA HO.Genetic Algorithm for FuzzyControl, Part 1:Offline System Development and Application[C]//IEE Proceedings-Control Theory and Applications.U-nited Kingdom:IET, 2004:161-176.
[3]ESMIN A A A, AOKI A R, LAMBERT-TORRES G.ParticleSwarm Optimization for Fuzzy Membership Functions Optimiza-tion[C]//IEEE International Conference on Systems, Man andCybernetics.Tunisia:IEEE, 2002, 3:5.
[4]HOMAIFAR A, MCCORMICK E.Simultaneous Design of Mem-bership Functions and Rule Sets for Fuzzy Controllers Using Ge-netic Algorithms[J].IEEE Transactions on Fuzzy System, 1995, 3 (2) :129-139.
[5]KENNEDY J, EBERHART R.Particle Swarm Optimization[C]//Proceedings of the IEEE International Conference onNeural Networks.Australia:IEEE, 1995:1942-1948.
[6]SUN J, FENG B, XU W B.Particle Swarm Optimization withParticles Having Quantum Behavior[C]//Proceeding of 2004Congress on Evolution Computation.Portland:CEC, 2004:325-331.
[7]LIUJ, SUNJ, XUW B, et al.Quantum-behaved Particle SwarmOptimization Based on Immune Memory and Vaccination[C]//Proceedings of the IEEE International Conference onGranular Computing.USA:IEEE, 2006:453-456.
[8]DASGUPTA D.Artificial Immune Systems and Their Applica-tions[M].New York:Springer-Verlag, 1999.
[9]DORF R, BISHOP R H.Modern Control Systems[M].Califor-nia:Addison Wesley, 1998.
量子免疫算法 篇2
互联网的迅猛发展使得黑客攻击日益猖獗，网络安全成为当今社会关注的焦点。在目前实现的网络安全技术中，入侵检测技术对入侵具有较好的识别能力，是动态安全技术的最核心技术之一。入侵检测系统按照所检测的数据来源分为基于主机的入侵检测系统和基于网络的入侵检测系统(NetworkBasedIntrusionDetectionSystem,NIDS)。基于网络的入侵检测系统主要通过对网络上数据包的分析来检测通过网络发起的入侵活动。在入侵检测系统中需要定义入侵特征和用户正常行为轮廓的参数集，为了实现参数集合和属性的最优化，引入了遗传算法来搜索整个度量空问，以适应度评价的方式逐步优化初始度量参数子集，从而得到针对特定检测环境的最优度量集合。
许多入侵检测系统采用了人工智能的技术来解决这些入侵检测方面的问题。近年来，遗传算法(Genetic Algorithm,GA)[1,2]因其高效的优化性能在入侵检测系统中得到了广泛的应用。GA是一类模拟生物进化的智能优化算法，它在解决组合优化问题中具有明显的优势和特色，但在入侵检测问题上，最优个体并不能代表问题的最优解，问题的解要通过一组染色体来表示，该方法存在染色体集成的问题，因此在解决入侵数据量及入侵准确性上还存在一些问题。为此也有学者提出一系列的基于遗传算法的改进算法[3]，对提高入侵检测准确性上有一定的改进，笔者基于量子理论，提出一种新的量子遗传克隆检测算法QGA，该算法充分利用克隆选择算法的优点，保持解空间的多样性和抗干扰性，克服了遗传算法存在的早熟收敛现象，通过仿真实验证明，QGA算法能有效弥补遗传算法在Web搜索中的不足，是一种解决Web搜索问题行之有效的快速方法。
2 入侵检测系统模型
入侵检测系统(Intrusion-detection system，下称“IDS”)是一种对网络传输进行即时监视，在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。它与其他网络安全设备的不同之处便在于，IDS是一种积极主动的安全防护技术。IDS最早出现在1980年4月，由James P.Anderson为美国空军做了一份题为《Computer Security Threat Monitoring and Surveillance》的技术报告中。后来IDS分化为基于网络的IDS和基于主机的IDS，又出现了分布式IDS。IDS入侵检测系统以信息来源的不同和检测方法的差异分为几类。根据信息来源可分为基于主机IDS和基于网络的IDS，根据检测方法又可分为异常入侵检测和滥用入侵检测。不同于防火墙，IDS入侵检测系统是一个监听设备，没有跨接在任何链路上，无须网络流量流经它便可以工作。因此，对IDS的部署，唯一的要求是：IDS应当挂接在所有所关注流量都必须流经的链路上。在这里，"所关注流量"指的是来自高危网络区域的访问流量和需要进行统计、监视的网络报文。在如今的网络拓扑中，已经很难找到以前的HUB式的共享介质冲突域的网络，绝大部分的网络区域都已经全面升级到交换式的网络结构。
如图1是一个入侵检测系统(IDS)的通用模型，它将一个入侵检测系统分为以下组件：事件产生器、事件分析器、响应单元、事件数据库四个部分。CIDF将IDS需要分析的数据统称为事件(event),它可以是网络中的数据包，也可以是从系统日志等其他途径得到的信息。事件产生器的目的是从整个计算环境中获得事件，并向系统的其他部分提供此事件。事件分析器分析得到的数据，并产生分析结果。响应单元则是对分析结果作出作出反应的功能单元，它可以作出切断连接、改变文件属性等强烈反应，也可以只是简单的报警。事件数据库是存放各种中间和最终数据的地方的统称，它可以是复杂的数据库，也可以是简单的文本文件。在这个模型中，前三者以程序的形式出现，而最后一个则往往是文件或数据流的形式。
3 QGA算法的应用
QGA入侵检测算法将量子算法，遗传算法和免疫克隆算法三者的优点充分进行结合，其模型如下：
其中，E表示量子编码，F是亲和度函数，Cl是克隆操作，Cr是量子交叉操作，M是遗传变异操作。
3.1 量子编码
遗传算法的常用编码方式有二进制、十进制和符号编码。在量子克隆遗传算法中，采用了一种特殊的编码方式———量子比特编码[4]，即用一对复数来表示一个量子比特，由此可得到：如果有n位的量子位，可同时表示2n个状态(即2n个信息)，因而在对量子比特计算时，一次运算相当于对2n个状态同时操作。所以，一个量子比特所包含的信息要比经典的比特多，这也正是此算法高效性的所在。
3.2 亲和度函数
亲和度是用来表明抗体与抗原之间的匹配程度，亲和度越高，说明抗体越接近抗原，也就越接近所求问题的解[5]。本文设计的亲和度函数为：
3.3 克隆算子
如前所述，进化算法在解决优化问题时虽具有简单、通用、替棒性等特点，但在搜索后期由于其算法的盲目性和随机性，就会出现退化早熟现象。为了防止这类现象的发生，就是要增大优良个体的比例，减少坏个体的不良影响，即利用有用信息来指导进化。基于此，杜海峰等人提出了免疫克隆策略算法[5]，算法中主要提出了克隆算子，包括三个步骤:克隆、克隆变异和克隆选择。抗原、抗体、抗原和抗体之间的亲合度分别对应优化问题的目标函数和各种约束条件、优化解、解与目标函数的匹配程度.克隆算子就是依据抗体与抗原的亲合度函数f(*)，将解空间中的一点ai(k)
3.4 遗传变异
通过克隆扩大了群体的规模后，对克隆后的临时群体A(k)中每个抗体进行变异，可以提高群体中抗体的多样性，扩大搜索范围，用来寻找更优秀的抗体。遗传变异操作如下：
B(k)和A(k)分别是父抗体和子抗体，N(0,1)是均值为0，方差o=1的高斯变量;Pm是变异概率;f(*)是v的亲和度.
3.5 量子交叉
在QGA中，我们采用量子全干扰交叉操作，这种量子交叉可以充分利用种群中的尽可能多的抗体的信息，改进普通交叉的局部性与片面性，在种群进化出现早熟时，它能够产生新的抗体，给进化过程注入新的动力。这种交叉操作借鉴的是量子的相干特性，可以克服普通个体在进化后期的早熟现象。表1列出的是抗体群规模为4，抗体长度为5的一种具体交叉操作。
在表1中，每个大写字母表示交叉后的一个新抗体，量子交叉后得到临时抗体群C(k)。
3.6 QGA算法的框架
QGA算法描述如下：
1)在解空间产生初始抗体群A(k)，初始化种群规模n，变异概率Pm，变异概率Pc,k=0;
2)计算抗体群中每个抗体的亲和度f(ai(k)),i=1,2...,n;
3)对抗体群A(k)进行克隆操作，得到抗体群A(k)';
4)对抗体群A(k)'进行遗传变异操作，变异后临时抗体群为B(k);
5)对抗体群B(k)进行量子交叉操作，交叉后产生新抗体群A(k+1);
6)k=k+1;当满足终止条件时，算法结束，并将结果显示给用户;否则，返回到步骤(2)。
4 仿真实验与结果分析
4.1 实验环境和参数选取
为了验证算法的有效性，我们用java语言实现了本文提出的QGA算法，并在Pentium(R)4 CPU 1.80G Hz and 1G内存的PC机上进行了测试。实验数据采用的是KDDCup99测试数据集(此实验只选取了其中的一部分数据来进行，约有15MB，共14000多条记录)。
实验过程中初始种群中共有14条染色体，每条染色体编码后长度为50位，进化代数为100代，定交叉概率设为0.5，变异概率为0.005，最大迁移个数为4迁移间隔为5(每进化5代便进行一次迁移)。实验测试的结果都是平均运行10次以上。
4.2 实验结果与分析
实验结果如表2所示，从实验结果可以看出，QGA算法的入侵检测平均正确率达到96%左右，而GA算法的入侵检测平均正确率为90%，在5739条入侵数据中，QGA比GA算法多检测出326条数据，说明QGA算法的性能明显优于GA，这是因为在QGA算法中,克隆操作大大增加了空间解的搜索范围,量子编码和量子交叉丰富了群体的多样性,这些都能充分发挥GA的优点和智能算法的优势。
5 结束语
本文提出的量子克隆算法QGA的入侵检测方法，融合了量子算法，遗传算法和免疫克隆算法的优点。QGA系统可以克服了遗传算法对入侵数据检测正确率不足的缺点，提高了数据检测的速度和准确性。
参考文献
[1]王英,邓亚平,曾立梅.遗传算法在入侵检测中的应用[J].重庆邮电学院学报,2006,18(2):261-264.
[2]李开银,王申康.人工异常在入侵检测中的应用[J].计算机应用,2004,17(2):18-20.
[3]李莛,罗安坤.基于粗粒度遗传算法的网络入侵检测系统[J],计算机工程2008,34(13):166-171.
[4]李阳阳,焦李成.求解SAT问题的量子免疫克隆算法[J].计算机学报,2007,30(2):176-183.
[5]焦李成,杜海峰.人工免疫系统进展与展望[J].电子学报,2003,31(10):1540-1548.
量子免疫算法 篇3
电力系统无功优化是指从优化运行的角度调整系统中各种无功控制设备的参数, 在满足节点正常功率平衡及各种安全指标的约束下, 实现目标函数最小化的过程[1]。它既是保证电力系统安全、经济运行的有效手段之一, 又是降低网络损耗、提高电压质量的重要措施[2]。
无功优化是一个多目标、多约束、变量类型混合的非线性规划问题。关于无功优化的求解方法可分为传统数学算法和现代启发式算法。传统数学方法有非线性规划法[3]、简化梯度法[4]、内点法[5]等, 这类方法有一定的优越性, 但计算较为复杂, 易陷入局部最优解, 且不便于处理离散变量。随着人工智能的发展和计算机运行速度的提高, 越来越多的现代启发式算法应用于无功优化中, 如遗传算法[6]、蚁群算法[7]、免疫算法[8]、粒子群算法[9,10]、搜索禁忌算法[11]、模拟退火算法[12]等, 且都取得了一定的研究成果。量子计算因其强大的运算能力, 已经成为世界各国紧密跟踪的前沿研究领域之一。借鉴生物免疫系统原理而发展起来的免疫算法也已成为现代启发式算法的一个研究热点。结合量子计算机理和免疫克隆算子, 本文提出了一种解决多目标无功优化问题的量子免疫克隆算法QICA (Quantum Immune Colonial Algorithm) 。该算法具有良好的并行性, 搜索速度快, 寻优能力强, 将全局搜索和局部寻优有机结合, 确保所得解集快速有效地从不可行域边缘和可行域内部向最优Pareto前端逼近, 而且可以有效防止退化现象的产生, 是求解多目标无功优化问题的有效方法。
1 多目标无功优化数学模型
1.1 目标函数
本文选取有功网损PL最小、静态电压稳定裕度VSM (Voltage Stability Margin) USM最大以及节点电压平均偏移量ΔU最小作为目标函数。
a.有功网损。
其中, NL为系统支路总数;δi、δj、Ui、Uj分别为节点i、j电压的相角和幅值;Gk (i, j) 为支路k的电导。
b.静态电压稳定裕度。
选用收敛潮流雅可比矩阵的最小奇异值作为度量系统静态电压稳定裕度的指标[13], 即:
其中, JJacobi为收敛潮流雅可比矩阵, eig (JJacobi) 为雅可比矩阵的特征值, min︱eig (JJacobi) ︱为该矩阵最小特征值的模。
c.电压平均偏移量。
其中, n为网络节点总数;Ubideal为节点b期望电压值;Ub为节点b实际电压值。
1.2 约束条件
其中, T为可调变压器的变比;Qc为无功补偿电容器容量;Ug为发电机端电压;U为各节点的运行电压;Qg为发电机注入无功;Timin (Timax) 、Qcjmin (Qcjmax) 、Ugkmin (Ugkmax) 、Uimin (Uimax) 、Qgkmin (Qgkmax) 分别为以上变量所对应的最小 (最大) 值。式 (4) — (6) 分别为系统潮流约束、控制变量约束、状态变量约束。
1.3 多目标函数解评价
多目标函数之间存在相互矛盾性, 所以很难找到一个解, 同时使各目标函数达到最优。传统加权叠加比较的评价方法, 对权重选取的依赖性很大, 而且不能很好地反映各目标函数的优劣性, 本文采用目标函数值与理想化目标的接近程度来评价解的优劣性, 其操作如下。
若多目标函数min (F) =min (f1, f2, f3, …, fc) 存在一组可行解x1、x2、…、xl。
a.构建目标函数矩阵。
b.目标函数矩阵归一化处理。
c.求取理想化目标。所谓理想化目标即归一化矩阵中各函数对应的最小值。
d.评价各解的优劣性。本文采用各目标函数值与理想化目标欧氏距离的大小来评价解的优劣性, 该距离越接近表明解越优。
2 量子免疫克隆算法
2.1 克隆算子
在多目标优化问题中, Pareto前端上的所有点是同等优秀的, 为了保证在种群扩张时, 所得解在Pareto前端均匀分布, 本文采用了自适应克隆操作。抗体的克隆规模依据拥挤距离[14]来自适应地调整, 即拥挤距离越大者, 克隆规模就越大, 被搜索的机会越多, 其具体操作如下。
将抗体群A (it) ={W1, W2, W3, …, Wk}中抗体Wi以比例qi进行克隆, 其中qi为:
其中, it为当前的进化代数;round[·]表示取整为最近的整数;Nc为与克隆规模有关的设定值, 本文取Nc=200;di为拥挤距离 (具体形式参见文献[14]) 。
则克隆后的抗体群为:
2.2 量子重组算子
混沌变量在寻优过程中具有随机性、遍历性以及规律性等特点。本文通过量子重组算子将Logistic映射[15]下的混沌序列用于量子抗体的寻优过程中, 使量子位在演化过程中呈现出混沌现象, 进而极大增加了算法的搜索能力, 其操作如下:
其中, i=1, 2, …, k;j=1, 2, …, qi;Logistic (j) 为Logistic映射的第j个序列值 (具体形式参见文献[15]) ;b为抗体影响因子, 取值范围为[0.1, 0.4];v为混沌收缩因子, 取值范围为[0.1, 0.3];rand表示生成0~1之间的随机数。
2.3 量子非门算子
为进一步增进种群的多样性, 抗体经上述量子重组操作后, 以变异概率pm随机选择一位或若干位进行量子非门操作, 本文取pm=0.5。该操作实现了对量子位概率幅的互换, 使得原来取状态0的概率变为取状态1的概率, 或者相反。其具体操作如下:
其中, Q为量子位概率幅。
2.4 选择更新算子
传统免疫算法绝大多数依据亲和度函数作为选择方式, 抗体亲和度越大, 越容易被选择保留。在本算法中, 一个抗体能否通过选择进入下一代, 取决于该抗体是否为当前代中的非支配抗体。当进化到达一定代数时, 非支配抗体数目可能会有很多, 而依据本算法的选择策略, 它们都将被选入下一代, 这样会导致运算速度变慢。为了避免该情况发生, 本算法采用了抗体群更新操作。如果非支配抗体超过一定数目Nn, 则可依据拥挤距离将Pareto前端上分布较为密集抗体删除, 既保证了运算速度, 也保证了所得解分布的均匀性[16]。
2.5 免疫疫苗
传统免疫算法由于缺乏适当措施, 在寻优过程中会出现大量劣解、甚至非可行解。为了有效地克服此类退化现象, 本文引入了疫苗[17]的概念。选择当前代精英个体作为免疫疫苗保留, 并于下一代量子非门操作完成后植入种群, 从而在寻优的过程中有效地克服了退化现象, 保证种群向优良模式进化。
3 基于量子免疫克隆算法的无功优化
3.1 抗体的编码
本算法中的抗体采用量子位表示, 一个量子位不仅可表示0、1这2个状态, 而且可以表示在0、1这2个状态间的任意状态。若用n个量子位表示可调变压器的变比T、m个量子位表示发电机端电压Ug、l个量子位表示无功补偿电容器容量Qc, 则编码后的每一个抗体可以描述为:
其中, αi、βi (i=1, 2, …, n+m+l) 为复常数, ︱αi︱2+︱βi︱2=1, ︱αi︱2表示第i个基因位取值0的概率, ︱βi︱2表示第i个基因位取值1的概率。
3.2 不等式约束处理
不等式约束将搜索空间划分为可行域和不可行域2个部分, 因此如何有效地利用不可行解显得非常重要。传统免疫算法未考虑到不可行解集, 仅对可行解集进行相应的进化计算。本算法有效利用部分接近可行域边缘的不可行解, 使寻优过程分别从不可行域边缘和可行域内部向约束最优Pareto前端逼近, 从而保证了所得约束最优解的较高质量。
不等式约束g (x) = (g1 (x) , g2 (x) , …, gh (x) ) ≤0可转化为一个目标函数, 令:
则:
对任意一个变量x, 若fk+1 (x) =0, 则x满足约束条件, 为可行解;若fk+1 (x) >0, 则x不满足约束条件, 为不可行解, 并且fk+1 (x) 的数值越大, 则x违反约束的程度越严重。因此, 可采用如下处理方法:
a.将抗体群A划分为不可行解集和可行解集Xf;
b.以Pareto占优的概念为依据, 将可行解集Xf划分为非Pareto占优集和Pareto占优集Ps;
c.根据违反约束程度的大小将不可行解集划分为非有益解集和有益解集Qb;
d.分别对有益解集Qb和可行解集Xf进行相应的免疫克隆选择操作, 求得高质量的Pareto最优解。
3.3 算法流程
量子免疫克隆算法应用于多目标无功优化的流程如图1所示。
4 算例分析
为验证本算法的可行性, 本文对IEEE 14节点测试系统进行多目标无功优化计算。用MATLAB语言编制了系统潮流计算程序和量子免疫克隆算法。算法中相关参数的设置如下:抗体群规模为100, 有益解集规模为30, 最大迭代次数为50。算例中数据均为标幺值。
4.1 IEEE 14节点系统算例
该系统包含3台可调变压器、5台发电机 (其中1号发电机为平衡节点) 、1个无功补偿点。各可调变压器上下档位数为±16, 步进量为0.625%, 其变比范围为0.9~1.1;各发电机端调压范围为0.95~1.05;无功补偿点 (节点9) 的无功补偿上限为0.5, 分段步长为0.1。
4.2 分析与比较
运用本文算法对该系统进行优化评价, 将该算法独立运行50次后选出有代表性的一组计算结果如表1所示。
图2显示了该次计算最终求得Pareto解的分布, 其中方块符表示决策最优解。
由表1和图2可见, 最优解所对应的点坐标与理想化目标所对应的点坐标之间存在一定距离, 这说明了多目标无功优化中各个目标函数同时达到最优化的可能性很小, 也验证了求解相互矛盾的多目标函数只能根据实际情况从一个整体最优化的角度求出可行解, 而应用本文所提出的欧氏距离来评价可行解的优劣则可以较好地履行这一职责。
将本文算法独立运行50次后, 求出所得最优解的平均值, 同时将该值与其他算法应用于IEEE 14节点系统的结果进行了比较, 如表2所示。
可见, 本文提出的算法在多目标无功优化问题中应用效果明显, 较免疫算法和改进遗传内点算法[1]可更好地找出全局最优解, 进而有效降低了网络损耗, 提高了电压质量。
5 结论
量子免疫算法 篇4
关键词：自适应,量子免疫算法,盲检测,交叉变异算子
优化问题在科学研究和工程应用的各个领域具有重要的理论意义和实践价值, 人工免疫算法具有搜索效率高、种群多样性程度高等特点, 目前已经被广泛地应用于智能计算领域, 成为解决复杂优化问题的有力工具。量子计算具有高度的并行性, 大存储数据量以及指数级别的加速能力。量子免疫算法 (Quantum Inmune Algorithm) 是汲取了量子进化算法和人工免疫算法的各自优势而形成的新的优化算法, 它继承了量子进化算法的概念原理, 同时又扩展了免疫理论更新选择概念。量子免疫算法能够保持抗体种群的多样性, 同时也具有较好的收敛速度与效果。
Hongjian等人将免疫系统概念引入量子进化算法[1], 免疫算子在保留原算法的特性下力图有选择地利用待求解问题的特征信息和先验知识, 抑或是避免求解问题中的一些冗余工作, 从而提高算法整体性能。Haoteng等[2]提出了基于混沌理论的量子免疫算法, 该算法应用了混沌免疫理论, 并且根据小生镜机制将初始个体进行实数染色体编码子群, 使得各子群应用免疫算子的局部搜索能力找出最优解。李阳阳等[3]提出了一种基于量子编码的免疫克隆算法求解SAT问题, 特别针对种群中的个体采取了量子染色体编码的格式, 采用了量子旋转门和旋转角策略对抗体进行演化, 目的是为了加速克隆算子的收敛, 利用其局部搜索能力强的特点, 并且利用量子交叉信息算子提高了种群的多样性, 防止早熟。
但是量子免疫算法也存在一些问题, 例如, 在变异过程中种群的多样性并不稳定, 并不能保证能快速收敛到最佳适应度的个体, 出现停滞现象[4]。研究相关参考文献[5-6], 发现在量子算法的改进策略上通常都是采用针对变旋转角Δθ采取动态变旋转角的策略。这些策略虽然均取得了较好的效果, 但策略自身也具有局限性, 如不具备通用性, 需要根据具体问题具体优化;参数构成复杂, 实现难度大, 这种变异策略牵涉的参数过多, 效果难以控制, 复杂度增加。
综上所述, 为了更好地应用于盲检测, 不仅仅可以在量子变旋转角上进行改进, 也可以在免疫变异策略和旋转角变化趋势上进行演进。
1 SIMO盲检测模型
忽略噪声时, SIMO离散时间信道的接收方程定义为
式中:XN是接收数据阵;S是发送信号阵;Γ是由信道冲激响应hjj构成的块Toeplitz矩阵;XN=[xL (k) , …, xL (k+N-1) ]T是N× (L+1) q接收数据阵, 其中xL (k) =Γ·sL+M (k) 。其中, 发送信号阵可表示为
式中:M为信道阶数;L为均衡器阶数;N为所需数据长度;sL+M (k) =[s (k) , …, s (k-L-M) ]T。其中, s∈{±1}, Γ=[h0, …, hM]q× (M+1) ;q是过采样因子, 取值为正整数。
对式 (1) , Γ满列秩时, 有Q=UcUcT满足QsN (k-d) =0, Uc是N× (N- (L+M+1) ) 酉基阵, 由奇异值分解中得到;U是奇异值分解中的N× (L+M+1) 酉基阵;0是 (N- (L+M+1) ) × (L+1) q零矩阵;V是 (L+1) q× (L+1) q酉基阵;D是 (L+M+1) × (L+1) q奇异值阵。
据此构造性能函数及优化问题为
式中:Q=UcUcT;d为延时因子, d=0, …, M+L。如此, 信号盲检测问题就成为了求解式 (3) 的全局最优解问题。
本文就是利用基于自适应交叉变异算子的量子免疫算法来解决这一问题。本文定义量子免疫算法的适应度函数为:采用基于自适应交叉变异算子的量子免疫算法进行寻优搜索, 将此适应度函数作为目标函数进行寻优, 将盲检测问题的求解等效为求适应度函数F的最小值, 即
2 基于自适应交叉变异算子的量子免疫盲检测算法设计 (SCOQIA)
在种群更新选择算子中, 交叉概率和变异概率是影响算法行为和性能的关键。量子免疫算法中, 量子交叉和量子变异由量子门控制。而在传统的免疫算法中, 则由交叉算子 (cross-over operator) 和变异算子 (mutation operator) 组成, 采用固定的交叉概率和变异概率。本文提出一个新的思路:采用传统免疫算法中交叉和变异算子策略, 又同时引入了基于自适应策略的量子免疫交叉与变异算子, 为更好地加强种群的进化程度, 算法利用量子交叉与量子变异进行进化。在一般情况下, 如果在算法初始阶段采用较小的交叉率和变异率, 很难产生优秀的新个体, 算法后期, 模式朝着高适应度方向演进, 如果仍采用较大的交叉率和变异率, 会对种群的优良性产生影响, 造成过度进化, 同样会使优化结果陷入局部极小。
针对上述问题, 固定的量子免疫交叉算子Pc和变异算子Pm不能适应种群变异的变化幅度, 容易陷入局部最小, 因此可以根据种群适应度变化的实际情况, 将交叉算子Pc和变异算子Pm进行动态调节。具体方法如下。
定义种群数量为Ns, 多样性因子Ms为
式中:fmax为适应度最大值;fave为平均适应度, 即
本文提出的自适应策略构造与分析如下。如果Ms=1, 则表明种群中抗体未变异, 种群基因相同, 多样性最低。为了避免早熟, 交叉算子Pc和变异算子Pm必须进行变化, 以增加种群的多样性, 即增大Pm, 减小Pc。
自适应交叉, 变异选择策略如表1所示。
其中交叉算子在算法中占主导因素, 默认取值范围为0.35
图1是基于自适应交叉变异算子的量子免疫算法流程图。
实施过程如下:
1) 设定初始化量子种群Q及相关参数, 如最大迭代次数等;
2) 对第一代种群进行观察操作, 得到第一代量子个体;
3) 对种群中每个量子个体计算其适应度, 并选择适应度最小的个体为抗体;
4) 识别抗原, 针对适应度函数寻优问题, 做免疫疫苗接种;
5) 按照自适应的变化概率, 即变异算子Pm对种群进行量子免疫变异操作;
6) 按照自适应的变化概率, 即交叉算子Pc对种群进行量子免疫交叉操作;
7) 对生成的个体进行适应度函数的评估, 并且对自适应算子做出动态调整;
8) 使用量子选择门对抗体种群进行更新;
9) 找出最佳个体, 如果符合程序结束条件, 则结束程序流程, 如果为否, 则进行最优解分析, 更新到抗体记忆库中;
10) 达到最大迭代次数时, 终止迭代, 输出全局最优解及适应度函数值。
3 仿真结果与分析
为了验证基于自适应交叉变异算子的量子免疫盲检测算法的性能, 本文利用MATLAB软件进行了仿真实验。发送信号调制方式为BPSK信号, 噪声为均值为0的高斯噪声。实验说明:1) 改进的量子免疫盲检测基本参数:序列长度60, 信道阶数为3, 仿真平台是MATLAB7.8.0.343 (R2010a) 。2) 所有仿真实验的数据是根据100次的Monte Carlo实验获得, 为了图像的可读性, 仿真实验图中误码率 (BER) 为0的处理为10-5[14]。
实验中主要采用3种经典信道, 信道1:按指定延迟delay=[0, 1/3]、权系数w=[1, -0.7]产生信道, 信道头尾各补q (过采样因子) 个零;信道2:文献中给出的含一个公零点, 权值和延时固定的合成信道;信道3:更能体现时变信道特点的权值和延时度变化的随机合成信道。
1) 实验1:改进的量子免疫算法在3种不同信道下的误码率与信噪比的关系。
基于自适应交叉变异算子的量子免疫算法 (SCO-QIA) 在不同信道下的信噪比-误码率 (SNR-BER) 性能曲线如图2所示。
由图2可知, SCOQIA算法在3种不同的信道条件下, 随着信噪比的增大, 误码率也呈现下降趋势, 最终都降为0, 说明改进后的量子免疫算法能够有效地进行盲检测, 表明了改进后算法对不同信道具有适用性, 对信道具有较强的鲁棒性。
2) 实验2:研究初始参数调节因子参数组{Vmax, Vmin, Pc, Pm}对自适应交叉变异算子的量子免疫算法 (SCOQIA) 盲检测性能的影响。
在仿真实验中观察不同参数对算法性能的影响大小。选取信道3作为测试环境。在本实验中, 选取不同的几组测试参数组, 设置为如下3组:U1={0.25, 0.05, 0.60, 0.15};U2={0.25, 0.05, 0.80, 0.25};U3={0.15, 0.03, 0.80, 0.25}。
由图3可以看出, 在选择不同参数的情况下误码率均随着信噪比的增加而降低, 对比参数组U1和U2, 其中U2较U1降低了交叉概率和变异概率, 而策略选择区间保持不变, 可以看出选择U1在8 d B误码率才降为0, 而U2在7 d B误码率就收敛为0, 因此可以推断交叉变异概率参数的选择对自适应交叉变异算子的量子免疫算法 (SCOQIA) 算法的盲检测效果影响较大, 根据实际试验选择合适变异概率能够在盲检测中取得较好的效果。
对比参数组U2和U3, 其中控制两组交叉概率和变异概率相同, 扩大了策略选择区间, 发现改进的SCOQIA算法在盲检测性能上变化不大, 信噪比均能在7 d B左右降为0。因此可以推断, 交叉概率Pc和变异概率Pm的初始取值会影响自适应策略变化的结果, 综合变异概率和交叉概率的优化效果, 在本实验环境中选取适当偏大的交叉概率Pc和变异概率Pm盲检测效果更佳。
3) 实验3:改进算法与基本算法误码性能的对比。
本实验在信道3条件下进行。实验主要目的是将自适应交叉变异算子的量子免疫算法 (SCOQIA) 与基本量子免疫算法 (QIA) 在同一信道环境中进行仿真模拟, 其信噪比-误码率性能曲线如图4所示。
图4可以看出改进的基于自适应交叉变异算子的量子免疫优化盲检测算法 (SCOQIA) 在信噪比为7 d B处降为0, 而基本量子免疫优化盲检测算法则在信噪比为8 d B处降为0, 由此证明了改进算法在性能上的优越性。
4 结论
本文提出了改进量子免疫优化盲检测算法:即基于自适应交叉变异算子的量子免疫优化算法。通过仿真实验验证了改进后算法在相同信噪比条件下误码率更低, 收敛速度更快, 即从盲检测算法的评价指标考虑, 均说明改进的算法具有一定的优越性, 表明本文提出的算法能够成功应用到盲信号检测中, 具有一定的研究价值。
参考文献
[1]QU Hongjian, ZHOU Fangzhao, ZHANG Xiangxian.An application of new quantum inspired immune evolutionary algorithm[C]//Proc.20091st International Workshop on Database Technology and Applications.Wuhan:IEEE Press, 2009:468-471.
[2]HAO Teng, YANG Bingyu, ZHAO Baohua.A new mutative scale chaos optimization quantum genetic algorithm[C]//Proc.Chinese Control and Decision Conference.Yantai:IEEE Press, 2008:1547-1549.
[3]李阳阳, 焦李成.求解SAT问题的量子免疫克隆算法[J].计算机学报, 2007, 30 (2) :176-183.
[4]吴秋逸, 焦李成, 李阳阳, 等.自适应量子免疫克隆算法及其收敛性分析[J].模式识别与人工智能, 2008 (5) :592-597.
[5]马颖, 田维坚, 樊养余.基于云模型的自适应量子免疫克隆算法[J].计算物理, 2013 (4) :627-632.
量子免疫算法 篇5
量子计算是量子力学和信息科学相融合的产物, 自1994年Shor提出第一个量子算法和1996年 Grover提出随机数据库搜索的量子算法, 量子计算以其独特的计算性能迅速成为研究的热点, 引起了国际学者的广泛关注, 量子遗传算法是一种基于量子计算原理的概率进化算法, 现阶段的各类量子遗传算法, 大部分是选用基于量子位测量的二进制编码方式, 通过改变量子比特相位来完成其进化的。事实上, 由测量染色体上的量子位的状态来产生所需的二进制解, 会有极大的盲目性和不确定性。因此, 在群体进化的同时, 个体必然会产生退化的现象。此外, 现阶段的所有量子进化算法其量子态依旧是在实域Hilbert空间单位圆上的坐标描述, 仅有1个可变量, 因此量子特性在很大程度上被削减。
在实际的物理体系中, 量子是在空间运动的, 传统上采用在平面坐标上的单位圆描述其动态特性, 必定不利于更加客观、全面、生动地描述其量子的动态行为。为此, 本文提出一种基于量子位Bloch球面坐标的量子进化算法 (Bloch Quantum Evolutionary Algorithm, 简称BQEA) .。
1 BQGA的基本原理
1.1 BQGA量子染色体的三链基因编码方案
在量子计算中, 最小的信息单位是量子位, 即量子比特。一个量子比特可描述成
undefined
其中, undefined和undefined是复数, undefined和undefined分别代表量子位处于|0〉或|1〉的概率, 在Bloch球面上, 一个点p可由两个角度θ和φ来决定, 如图1所示。
由图1可知, 任何一个量子位都与Bloch球面上的一点对应。所以, 量子位可用Bloch球面坐标表示成|φ〉=[cos φsinθ sin φsinθ cosθ]T 。在BQEA中, 直接使用量子位的Bloch球面坐标编码。设pi是种群中的第i条染色体, 则BQEA的编码方法为:
undefined
其中, φi1=2π×rnd, θij=π×rnd , rnd为 (0, 1) 之间的随机数;i=1, 2, …, m, j=1, 2…, n, m是群体规模;n是量子位数。在BQEA中, 将量子位的3个坐标看成3个并列
的基因, 每条染色体包括3条并列的基因链, 分别是X链、Y链、Z链, 而每条基因链代表1个优化解。所以, 每条染色体同时代表搜索空间中的3个优化解:
undefined
分别将pix、piy、piz定义成X解、Y解、Z解。
1.2 解空间的变换
BQEA的优化限定在单位空间In=[-1, 1]n中, 所以在优化具体问题时, 要进行单位空间与优化问题解空间之间的变换。种群中的每条染色体包括n个量子比特的3n个Bloch球面坐标, 运用线形变换, 将这3n个坐标由n维单位空间In=[-1, 1]n映射至优化问题的解空间Ω, 每一个坐标对应着解空间中的一个优化变量。将第i条染色体pi上第j个量子位的Bloch球面坐标记为[xij, yij, zij]T, 那么对应的解空间变换公式为:
undefined
其中, i=1, 2, …, m, j=1, 2, …, n。
1.3 量子染色体的更新
量子染色体的更新是经过量子旋转门更新量子位的相位来完成的。量子位相位旋转的作用在于使当前种群中每一个染色体逼近当代最优染色体, 但在这种逼近过程中, 也有可能产生出更好的当代最优染色体, 从而使群体不断得到进化。因此, 提出了一种新的量子旋转门, 形式为:
undefined
由
undefined
可知, U的作用使量子位的相位旋转了Δφ和Δθ。
φ和Δθ的大小通常根据具体问题的变化而变化, 如果它们取值过小, 就会降低算法的优化效率;如果取值过大, 就会无法得到全局最优解或者出现早熟现象。对于这一缺陷, 提出了改善方法。首先找出目标函数在搜索点 (单个基因链) 处的变换趋势, 然后根据目标函数的变换趋势而改变转角步长的大小。如果搜索点处目标函数变化率比较大时, 适当减小转角步长, 反之适当地加大转角步长。提出如下转角步长函数为:
undefined
其中, Δθ0、Δφ0为迭代值, ∇f (Xundefined) 为评价函数f (X) 在点Xundefined处的梯度, ∇fjmax和∇fjmin分别定义为:
undefined
其中, Xundefined (i=1, 2, …, m, j=1, 2, …, n) (为解空间中的变量, 可根据当前全局最优解的类型在解空间变换的结果中确定是Xundefined、Xundefined、Xundefined三者之一, x0、y0、z0是当前搜索到的全局最优解中某量子位在Bloch球面上的坐标, x1、y1、z1为某个当前解中相应量子位的Bloch球面坐标。
1.4 量子染色体的变异
本文构造如下变异算子:
undefined
V的作用是实现量子相位沿Bloch球面的旋转, 在这种旋转中, 每条染色体不与当代最优染色体比较。且旋转幅度比较大, 所以有助于突破早熟收敛, 增加种群的多样性。
2 算法描述
实现上述过程的步骤如下:①初始化种群。将当前代数t置为0, 根据式 (2) 随机生成由m条染色体构成的初始种群Q (t) ;设定量子旋转门的转角大小为|Δφ|=φ0和|Δθ|=θ0;设定最大进化代数为Max-gen;②变换解空间。把每个染色体代表的3个近似解, 从单位空间In=[-1, 1]n映射至解空间Ω, 得出近似解集X (t) ;③计算所有3m个近似解的适应度, 得出当代最优解BX和当代最优染色体BC;④让BX作为全局最优解GX;让BC作为全局最优染色体GC;⑤在循环中, 令t←t+1, 经更新和变异Q (t-1) 生成新群体Q (t) ;⑥ BQGA在单位空间的优化结果Q (t) 通过解空间变换后得出优化问题的解X (t) ;⑦经过对X (t) 评价, 得出当代最优解BX和当代最优染色体BC;⑧若fit (BX)
3 数值实验
为测试基于量子位Bloch球面坐标的量子进化算法的性能, 选择两个常用的标准测试函数:
(1) Goldstein-Price函数:
undefined
该函数在给定区域内只有一个全局最小点, 最小值为3。若目标函数值小于2.95, 则理解为算法收敛。Goldstein-Price函数如图2所示。
(2) Shuberts函数:
undefined
此函数共有760个局部极小点, 其中18个为全局最小点, 最小值为-186.730 9。
图4和图5分别给出了Goldstein-Price函数的进化曲线和Shuberts函数的所有18个全局最优解。
从图4中可以看出, 尽管每条染色体包含3条基因链, 但由于没有选择运算和复制运算, 所以运行效率较高。从图5中可以看出, 使用三链基因编码提高了寻优能力, 而变异算子可使算法避免陷入局部最优解。可见, 基于量子位Bloch球面坐标的量子遗传算法在搜索能力和优化效率两方面的确优于普通的量子遗传算法。
参考文献
[1]SHOR P W.Algorithms for quantum computation[C].Discretelogarithms and factoring.Proc.Of the 35th Annual Symp.OnFoundations of Computer Science.New York, USA:IEEE Com-puter Society Press, 1994.
[2]GROVER L K.A fast quantum mechanical algorithm for databasesearch[C].Proc.of the 28th annual ACM Symp.on Theory ofComputing.New York, USA:ACM Press, 1996.
[3]HIRAFUJI M, HAGAN S.A global optimization algorithm basedon the process of evolution in complex biological system[J].Com-puters and Electronics in Agriculture, 2000 (10) .
[4]GRIGORENKO I, GARCIA M E.Calculation of the partition func-tion using quantum genetic algorithms[J].Physica A, 2002 (3) .
[5]RAMOS R V.Numerical algorithms for use in quantum informa-tion[J].Journal of Computational Physics, 2003 (9) .
[6]SAHIN M, TOMAK M.The self-consistent calculation of a spheri-cal quantum dot algorithm study[J].Physica E, 2005 (8) .
[7]张葛祥, 李娜, 金炜东.一种新量子遗传算法及其应用[J].电子学报, 2004 (3) .
量子演化算法的改进研究 篇6
量子演化算法 (Quantum-Inspired Evolutionary Algorithm QEA) 是由量子计算理论和演化算法相结合产生的, 利用量子比特进行量子染色体编码, 并利用量子门进行量子更新的一种概率搜索算法。量子染色体的概念由KukHyun Han等人第一次引入[1,2], 而由于量子比特的叠加性、纠缠性和相干性, 由其组成的量子染色体与经典演化算法的染色体相比, 具有种群规模小、迭代次数少、多样性好、收敛速度快等优点, 将其应用于背包求解问题取得了很大的成功;但同时也存在一些缺陷, 如传统的量子演化算法易陷入局部最优、运算效率不高等。为了更好地将量子特性融入演化算法中, 进一步提高量子演化算法的效率, 本文将对传统的量子演化算法进行改进研究。
1 量子染色体
量子演化算法中量子染色体的编码方式采用的是根据量子态叠加原理而设计的一种量子染色体编码。在此定义了量子染色体中第i个量子比特表示形式为[3]:
其中, αi2表示量子比特几率幅处于|0>态的概率, 而βi2表示量子比特几率幅处于|1>态的概率。且αi与βi之间满足αi2+βi2=1。相应地, 一个含k位的第i个量子基因可以表示为:
其中, αi2和βi2分别以一定的概率取到0的状态和1的状态。
则一个量子染色体可以表示为下式[4]:
其中, k为每个量子基因所使用的量子位数。
2 量子演化算法更新
根据量子比特的特性来设计更新算子, 一般是利用量子门作用量子个体的各叠加态, 使其相互干涉, 相位发生改变, 从而改变各基态的概率[5]。与传统的逻辑门一样, 量子门也可以分为很多种。下面分别对其作以必要分析。
2.1 量子非门
量子非门是一种满足酉性的单量子比特门, 由一个2觹2的矩阵表示, 其对量子染色体的更新过程为:
上式中, (αi, βi) T为更新前的量子位, (α'i, β'i) T为更新后的量子位。因此, 量子非门可以用来实现量子染色体的变异操作, 当算法停滞, 可实现量子染色体中量子态矢量的几率幅值的对换, 增加量子染色体的多样性, 防止算法陷入局部最优。
2.2 量子旋转门
量子旋转门也是由一个2觹2的矩阵表示的一位门, 是量子演化算法中最主要的更新操作。通过改变量子旋转角的大小和方向来实现量子位更新, 操作过程由下式表示:
如图1所示。图中 (αi, βi) T表示第i位量子旋转前的几率幅值, (α'i, β'i) T表示该量子旋转后的几率幅值。量子旋转门UR (θ) 的作用是利用量子旋转角θ来改变量子几率幅值。θ表示旋转角大小, θ角的符号表示旋转方向, 正方向表示逆时针方向旋转, 负方向表示顺时针方向旋转。θ角太大, 进化容易进入早熟或者不收敛;θ角太小, 进化容易陷入停滞状态, 一般推荐θ角范围在0.001π到0.05π之间[6,7]。
3 量子演化算法的改进
量子演化算法的更新算子是算法中最重要的操作, 其中设计是算法最主要的部分, 也是算法性能好坏的关键因素。相对于传统演化算法的遗传操作, 量子演化算法中的量子更新算子都是作用于量子染色体上, 而由于其所处的叠加态和纠缠态, 无法使用传统的选择、交叉和变异等操作方式。因此, 算法在更新过程中很容易失去种群的多样性, 陷入局部最优。为了克服这一问题, 本文对传统的量子演化算法进行改进。
3.1 全干扰交叉算子
在传统的演化算法中, 交叉算子是实现演化过程更新的最主要操作之一, 可以有效地增加种群的多样性, 也可以加快算法的收敛速度。在量子演化算法中, 因量子染色体本身具有并行性, 所以前期的很多量子演化算法都没有使用交叉操作。因为对量子位的交叉操作很容易破坏量子染色体的结构, 可能使算法性能下降;但是如果没有交叉操作, 根据算法的演化特点, 又很容易出现极端化的量子几率幅, 从而陷入局部最优。为了解决这一矛盾, 本文设计了一种全干扰的量子交叉算子, 针对测量[8]后的经典染色体进行全干扰交叉, 这样既不会破坏量子染色体固有的并行性, 又可以增加测量后染色体的多样性, 而后影响量子染色体进化方向, 加快算法的收敛速度, 有效地防止“早熟”。
3.2 量子变异
在量子演化算法中, 因量子染色体固有的并行性, 一般情况下, 变异操作比较少用甚至不用。只有在种群陷入停滞或早熟时, 才会使用量子非门作为变异算子, 对量子染色体的几率幅进行操作。
本文设计的量子变异算子为:设定变异概率, 利用公式 (4) 量子非门分别对量子染色体的某几个量子位逐个进行操作, 使其几率幅值进行对换, 实现量子个体的变异操作。其目的是改变量子染色体的叠加状态, 使量子个体在测量时取0和1的概率发生改变, 促进量子搜索跳出局部最优解空间, 增加搜索广度, 增强算法的寻优能力。
3.3 改进的量子演化算法分析
通过对改进的量子演化算法实验分析, 改进的量子演化算法在寻优过程中不易陷入局部最优解, 寻找到最优解的成功率远高于传统算法, 求解结果明显优于传统的量子演化算法。从计算的迭代次数来看, 改进的量子演化算法所需要的迭代次数也远远小于传统的演化算法[9,10], 而且算法所用的种群规模非常小;然而在计算时间上, 本算法并没有非常明显的优势, 可能是因为该算法的的仿真平台是在经典计算机上运行的, 还不能充分体现出量子计算的并行特性;另外, 和设计平台的选择及仿真程序的设计也有关系, 本算法选择的实验平台是Matlab运行平台, 该平台的运行效率较低, 且本例中算法的停机条件选用预先设定迭代次数方式, 直接影响着算法的执行时间, 在这一点上则有待进一步的改进和完善。
3.4 改进量子演化算法流程
量子演化算法的算法流程如下:
(1) 令t=0, 生成初始量子染色体种群Q (t) ;
(2) 对初始种群进行测量, 得到状态p (t) , 即经典染色体;
(3) 对每个测量后的经典状态计算适应度;
(4) 记录其最佳量子个体、经典个体及其适应度值;
(5) 当不满足停机条件;
{
t=t+1;
利用量子旋转门操作对量子个体进行更新;
设定概率触发器启动量子变异;
对新种群Q (t) 进行测量, 得到状态p (t) ;
对状态p (t) 进行全干扰交叉;
对每个经典状态计算适应度;
记录最佳量子个体、经典个体及其适应度值;
｝
量子算法演化流程如图2所示。
4 结束语
本文在对传统量子演化算法的研究基础上, 根据其特点, 从两个方面对量子演化算法进行改进:
(1) 因量子染色体的量子位处于叠加态和纠缠态, 无法使用传统的交叉方式对量子位进行操作, 本文设计了针对测量后的经典染色体进行全干扰交叉;
(2) 本文设计了概率触发器启动量子非门进行量子变异。改进的量子演化算比起先前的算法具有更好的寻优能力, 更稳定的收敛度。
摘要：从两个方面对量子演化算法进行改进: (1) 因量子染色体的量子位处于叠加态和纠缠态, 无法使用传统的交叉方式对量子位进行操作, 设计了针对测量后的经典染色体进行全干扰交叉, 这样既不会破坏量子染色体的固有的并行性, 又可以增加测量后染色体的多样性, 继而影响量子染色体进化方向, 加快算法的收敛速度, 有效地防止“早熟”; (2) 设计了概率触发器启动量子非门进行量子变异。实验表明, 改进的量子演化算法比起先前的算法具有更好的寻优能力, 更稳定的收敛度。
关键词：量子演化算法,全干扰交叉,量子变异
参考文献
[1]HAN K H, KIM J H.Genetic quantum algorithm and its app-lication to combinatorial optimization problem[C]//Proc.2000 C-ongress on Evolutionary Computing, Piscataway, NJ:IEEE Pre-ss, 2000, 2:1345-1360.
[2]HAN K H, PARK K H, LEE C H, et al.Parallel quantum-i-nspired genetic algorithm for combinatorial optimization problem[C]//Proc.2001 Congress on Evolutionary Computation, Seoul, Korea, 2001, 2:1422-1429.
[3]赵干川.量子计算与量子信息[M].清华大学出版社, 2004.
[4]杨淑媛, 刘芳, 焦李成.一种基于量子染色体的遗传算法[J].西安电子科技大学学报, 2004, 31 (1) :76-81.
[5]杨淑媛, 刘芳, 焦李成.量子进化策略[J].电子学报, 2001, 29 (12) :1873-1877.
[6]周露芳, 古乐野.基于量子遗传算法的二维最大嫡图像分割[J].计算机应用, 2005, 25 (8) :1805-1807.
[7]邵桂芳, 李祖枢, 刘恒, 等.基于遗传量子的自适应图像分割算法[J].计算机工程, 2005, 31 (22) :189-191.
[8]刁大生.基于测量的量子计算[D].合肥:中国科学技术大学, 2008.
[9]王宇平, 李英华.求解TSP的量子遗传算法[J].计算机学报, 2007, 30 (5) :748-755.
量子遗传进化算法的收敛性研究 篇7
量子计算与遗传算法的结合量子遗传算法 (Quantum Genetic Algorithm, 简称QGA) 从20世纪90年代后期开始, Narayanan将量子多宇宙理论引入遗传算法, 提出了多宇宙量子衍生遗传算法, Han等提出量子衍生演化算法, 它首次将量子的概率幅表达引入遗传算法[1]。后来许多研究者在算法上又进行了相应改进, 并用实验结果证明更好。但是遗传算法的随机性不好把握, 收敛方向无法进行有效控制, 容易陷入局部最优等问题还是不易克服。面对遗传算法的各种问题, 学者们开始探索并构建新的算法模型。近年来, 学者们相继提出多种方法来改进量子遗传算法收敛性。比如引入免疫算子, 或者通过对量子旋转门的旋转角及旋转参数进行调节来改进算法收敛性[2]。本文针对背包问题提出引入惩罚函数来对收敛性进行研究, 并通过实验来对比效果。
1 量子遗传算法
遗传算法的缺点[3]包括:编码不规范及编码存在表示的不准确性;单一的遗传算法编码不能全面地将优化问题的约束表示出来;效率比其他传统的优化方法低;容易出现过早收敛;对算法的精度、可信度、计算复杂性等方面, 还没有有效的定量分析方法。
量子遗传进化算法是量子计算与遗传算法相结合的产物。目前, 这一领域的研究主要集中在两类模型上:一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法 (Quantum Inspired Genetic Algorithm) , 另一类是基于量子比特和量子态叠加特性的遗传量子算法 (Genetic Quantum Algorithm, GQA) [4]。
1.1 量子遗传算法流程
量子遗传进化算法求解问题的基本步骤[5,6]:
(1) 进化代数初始化:t=0。
(2) 初始化种群Q (t) 。
(3) 由Q (t) 生成P (t) :随机产生一个[0, 1]的数, 若它大于|αit|2取1, 否则取0, 然后, 对这一组解进行适应度评估, 记录下最佳适应度个体作为下一代演化的目标值。
(4) 对各个状态计算适应度。
(5) 记录最佳个体及其适应度值。
(6) While (不满足终止条件) do
begin
A.t=t+1;
B.对种群Q (t) 中每个个体实施一次测量, 得到一组状态P (t) ;
C.对每个状态计算适应度;
D.依据一定的调整策略, 利用量子旋转门操作和量子非门对种群个体进行更新, 得到子代种群Q (t+1) ;
E.记录下最佳个体及其适应度。
End
算法如图1所示。
1.2 量子遗传算法的收敛性
研究者针对算法的收敛性[7]提出过很多种方法, 其中就有调整旋转角及其参数的方法。量子遗传算法通过量子门来更新下一代染色体, 量子门可根据具体问题进行选择。目前已有的量子门有很多种, 根据量子遗传算法的计算特点, 选择量子旋转门较为合适。 (αi, βi) 为染色体的第i个量子比特, θi为旋转角, 其大小和方向根据一个事先设计的调整策略而确定。公式如下:
旋转角的选择策略如表1所示。
旋转角θi=s (αiβi) Δθ, s (αiβi) 和Δθ分别代表旋转的方向和角度, 其值根据表1的选择策略确定。该调整策略是将个体qjt当前的测量值的适应度f (xi) 与该个体当前的目标值f (bi) 的适应度值进行比较, 如果f (x) >f (b) , 则调整qjt中相应位量子比特 (xi≠bi) , 使得几率幅对 (αi, βi) 向着有利于xi出现的方向演化;反之, 如果f (x)
上文已经提到量子遗传算法是通过量子旋转门[10]来产生下一代染色体。量子旋转门亦可采用下式:
其中, θ为旋转角度, 其取值为θ=ω*f (αi, βi) , ω是一个与算法收敛速度有关的系数, 如果ω取值很大, 那么算法搜索网格就会很大, 容易出现早熟现象即算法容易收敛于局部的极值点。如果ω取值太小, 算法速度太慢, 甚至可能会出现停滞状态。ω取值往往与适应度值有关。
2 通过实例研究收敛性
2.1 背包问题算法
常规应用于背包问题的量子遗传进化算法有一个修复的过程以确保背包容积的限制, 算法如下;
开始t←0
初始化种群Q (t)
对初始种群观察, 得到一组状态P (t)
修复P (t)
评估P (t)
从P (t) 中选择好的解到B (t) 中
当不满足终止条件时
t←t+1
通过测量Q (t-1) 的状态得到P (t)
修复P (t)
评估P (t)
更新Q (t)
从B (t-1) 和P (t) 中选择好的解到B (t) 中
从B (t) 中选择最好的解b
当满足条件时局部或者全局的将b或bjt放置B (t) 中
结束
2.2 引入惩罚函数
本文在上述算法中引入惩罚功能, 则价值f (x) 表示为:
其中, Pen (x) 起到惩罚功能, 本文选用了以下两种惩罚函数:
其中, ρ是装进背包中所有物体的价值除以质量的值中最大的一项。
为了让量子遗传进化算法适时的结束, 因此需要一个终止条件。最优解概率表示如下:
并且:
则终止条件描述如下:
其中, 0<γ0<1, γ0对算法处理时间影响很大, 表2为在500个物品的背包问题中改变γ0观察其对终止状况的影响。
由表2知, 如果γ0≥0.1, 所有结果趋近相同γ0=0.9, 但是在γ0=0.9处大概是在γ0=0.1处的2.5倍。
为了设计一个新的终止标准, 量子比特收敛Cb被定义如下:
或者;
其中, q是量子比特个体, (αi, βi) 是第i个量子比特, 则收敛条件可以写成:
如果Cav为0.99, 则表示99%的个体趋近于正解, 表3说明了γ的改变。
2.3实验结果
如图3所示, 横坐标为进化的代数, 纵坐标为平均适应度值, 其中的上部分曲线为使用随机修复的量子遗传算法, 中部分曲线为使用线性惩罚的量子遗传算法, 下部分曲线为使用对数惩罚的量子遗传算法。通过引入结束条件, 算法都提前得到了最优解, 使用修复方法的解适应度值2940更好, 并且找到最优解的速度更快, 使用线性惩罚函数的算法其次, 使用对数惩罚函数的算法最优解较差, 速度也最慢, 中间还甚至产生了几个不合格的解。
3 结束语
本文对遗传算法及量子遗传算法进行了介绍, 量子遗传算法通过量子旋转门替代遗传算法的选择、交叉、变异来更新染色体, 其收敛性远远优于遗传算法。本文提及了几种常用于改进量子遗传算法收敛性的方法, 并通过背包问题实例观察引入惩罚函数及结束条件对收敛性的影响, 并得出结论:引入结束条件可以提前结束算法得到最优解, 引入线性惩罚函数后算法的收敛性要优于引入对数函数后的算法, 但是不如使用随机修复的算法更快, 获得的最优解更好。
参考文献
[1]杨俊安, 庄镇泉.量子遗传算法研究现状[J].计算机科学, 2003, 30 (11) :13-15.
[2]张葛祥, 李娜, 金炜东, 等.一种新量子遗传算法及其应用[J].电子学报, 2004, 32 (3) :476-479.
[3]雷英杰, 张善文, 李续武, 等.MATLAB遗传算法工具箱及应用[M].西安电子科技大学出版社, 2005.
[4]Kuk-Hyun Han, Jong-Hwan Kim.Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem[Z].2000.
[5]Hollot C, Misra V, Towsley D, et al.A control theoretic analysis of RED[C].Proc IEEE INFOCOM, Alaska, 2001.
[6]于洋, 查建中, 唐晓君.基于学习的遗传算法及其在布局中的应用[J].计算机学报, 2001 (12) :1242-1249.
[7]李敏强, 寇纪淞, 等.遗传算法的基本理论与应用[M].北京科学出版社, 2002.
[8]李斌, 谭立湘, 邹谊.量子概率编码遗传算法及其应用[J].电子与信息学报, 2005 (5) :805-810.
[9]Kuk-Hyun Han.Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, H_Gate, and Two-Phase Scheme[Z].2004.