量子统计力学演化算法

1、量子统计力学演化算法    2012-04-19     论文导读:将进化理论和量子统计力学理论相结合,提出一种新的量子统计力学演化算法.将整个遗传系统作为一个量子统计系统,并借鉴量子信息论中量子比特的叠加性,采用量子编码表征染色体,使系统中的量子能够表示多种线性叠加状态.算法类比量子统计力学中的相关概念,定义了.    将进化理论和量子统计力学理论相结合,提出一种新的量子统计力学演化算法.将整个遗传系统作为一个量子统计系统,并借鉴量子信息论中量子比特的叠加性,采用量子编码表

2、征染色体,使系统中的量子能够表示多种线性叠加状态.算法类比量子统计力学中的相关概念,定义了量子系统的能量和熵,并利用量子系统中能量和熵竞争的模式系统地协调进化理论中选择压力和种群多样性间的冲突,使算法在提高选择压力和维持种群多样性之间保持了适当的平衡,可以快速的收敛到全局最优解.实验结果表明,该算法有较高的执行效率和求解能力.基金项目:国家科技攻关项目基金(批准号: 2004BA907A20)和吉林省科技发展计划重大项目基金(批准号: 20060328).传统的遗传算法(GeneticAlgorithm, GA)存在着收敛速度慢和早熟两个。GA中最重要的两个因素是选择压力和种群多样性,并且两者

3、相互制约。为了使算法具有良好的性能,必须在提高选择压力和保持种群多样性之间保持适当的平衡.量子遗传算法(Quantum GeneticAlgorithm, QGA)就是在GA中引入量子计算的概念,是一种基于量子计算原理的概率化优化方法.量子遗传算法采用几率幅(量子态)表示信息单元(量子比特),从而实现了信息的量子化,这种表示缩小了种族规模,增加了种群多样性;量子杂交利用了量子的纠缠性使信息可以在整个种群中进行交流,加大搜索范围,增加了种群发现优秀演化方向的个体。文献将GA中的种群视为一个动力学系统,个体视为粒子,遗传操作视为粒子的碰撞或移动,提出了动力学演化算法(DynamicalEvolut

4、ionaryAlgorithm, DEA),该算法基于普通统计物理中的自由能极小化原理,通过引入动量和活动量的概念,提出一个新的选择策略,用于保持种群的多样性.本文结合QGA和DEA提出一种新的量子统计力学演化算法(QSEA),该算法将整个遗传系统作为一个量子统计系统,将遗传算法中的个体视为量子系统中的量子,整个算法的收敛过程模拟了量子系统由非平衡向平衡状态转变的过程.算法根据量子信息理论,借鉴量子比特的叠加性,采用量子编码。表征染色体,使一个量子能够表示多种线性叠加状态,同时使用量子门实现变异操作.利用量子编码的特性,定义了量子系统的熵与量子的能量,并借鉴动力学中能量和熵竞争的模式系统地协调

5、进化理论中选择压力和种群多样性之间的冲突。数值实验表明, QSEA有很好的稳定性和计算效率.预备知识熵增法则和自由能极小化原理为了描述物理系统的热力学状态,克劳休斯和玻尔兹曼从宏观和微观两个角度以及二者之间的必然联系中,定义了热力学系统中物理熵的概念.克劳休斯将热力学第二定律表示为孤立系统内的不可逆过程总是指向熵增加的方向.克劳休斯熵作为系统的宏观状态函数,它的变化可以直接反映出系统自发不可逆过程的方向.玻尔兹曼统计熵则定义为:S=kln,其中k为玻尔兹曼常数,一般取为1.381×10-3J/K;是热力学系统某一个宏观状态所包含的微观状态数,称为热力学几率.处于非平衡状态的孤立状态具

6、有较小的热力学几率和熵,它自发地朝熵增加的方向发展,即有dS0.达到平衡状态时系统最无序、最混乱,此时的熵最大.因此,熵的大小可以衡量系统混乱的程度.自由能定义为: F=E-TS,其中E表示内能, T表示系统的温度, S表示系统的熵.自由能极小化原理描述如下:对于一个只与外界有热交换的封闭恒温系统,总是朝着自由能减小的方向发展.当自由能达到极小值时,系统就达到了平衡状态.系统状态从非平衡态自发变化到平衡态,是一个内能减少和熵增加的竞争过程,而温度决定了它们之间的相对权重.从演化算法的观点考虑,对于一个优化问题,目标函数的最小化(即收敛)和得到解的多样性(即避免陷入局部最优)均为一个有效全局优化

7、算法的两个核心指标.这种观点和动力学中的自由能极小化状态变化非常相似,可以将能量的减小看作算法种群收敛到最小值,而熵增即为算法种群保持多样性的过程.量子比特编码在量子信息论中,信息的载体是一个一般的二态量子体系.这个二态量子体系称为量子比特即量子位.区别于经典比特,量子比特可以是处于0,1这两个本征态的任意叠加状态,而且在对量子比特的操作过程中,0,1二态的叠加振幅可以相互干涉,这就是量子的相干性;量子计算机对每个叠加分量(本征态)的实现变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加,给出量子计算的计算结果,这种计算称为量子并行计算.一个量子比特的状态可以取值0或1,

8、其状态表示为:量子变异GA中采用交叉、变异等操作保持种群的多样性, QGA采用量子门10作用于量子态概率幅的方式保持种群多样性,因而,量子门的更新方法是QGA的关键.本文选择量子旋转门作为演化的执行机构,使用量子旋转门的旋转角度同样可以表征量子染色体的变异,进而变异中加入最优个体信息,加速算法收敛.用U()=cos-sinsincos表示旋转门, m表示量子染色体的长度.表1列出了值的变化范围,由表1可见的变化情况.表1中xi表示量子q衍生粒子x的第i个比特, bi表示当前最优染色体的第1位; f(x)表示适应度函数,表示旋转角度,控制算法收敛速度.量子门变换方法描述如下:量子统计力学演化算法

9、量子系统由非平衡到平衡的过程和GA种群收敛过程之间存在相似性,例如GA中的种群可以视为量子系统,种群中的个体可以视为量子系统中的量子.种群的平均适应值和种群的多样性可以担当量子系统中能量和熵的角色.表2列出了量子系统遗传算法的诸多相似点.表2GA和量子系统的相似性比较Table 2Sim ilarities between GA and quantum system量子系统遗传算法由若干量子组成的统计系统若干个体组成的进化种群系统中的能量种群的平均适应值系统中的熵种群的多样性能量和熵的竞争选择压力和种群多样性的竞争自由能减少种群收敛非平衡状态到平衡状态算法求解基于二者的相似性,本文提出一种量子

10、统计力学演化算法,该算法利用量子系统从非平衡状态到平衡状态的变换过程模拟遗传算法的收敛过程,并采用量子编码机制,借鉴量子系统中能量和熵的竞争关系协调种群进化过程中选择压力和种群多样性之间的冲突,定义了量子系统的统计能量和量子熵.算法在统计能量和量子熵相互竞争的驱动下,可以有效而快速地收敛到全局最优.量子熵的度量当将量子系统的竞争机制引入到GA中时,如何度量种群的多样性是一个关键问题. DEA算法未对系统的熵给出定量计算,只近似的将粒子的活动量看作自由能定义公式中的熵.此方法在统计物理上的解释不合理.在新算法中,本文采用量子编码,用1122mm表示一个量子染色体,2和2表示量子处于状态0和状态1

11、的概率.利用2,2的意义定义量子系统中的熵.表明了量子系统的混乱程度,随着算法的进行,2,2逐渐趋于0或1,此时H(qr, t)逐渐取到最大值,表明系统在算法收敛时达到最大量子熵值,而且量子熵随算法的运行而不断增大,符合热力学中的熵增法则.统计能量的度量由于量子的不确定性,因此无法精确衡量一个量子的能量,本文采用量子坍塌方法,使得一个量子生成k个普通粒子,然后对这k个普通粒子进行统计观察,得到原量子的能量.定义(统计能量)qr在第t时间的统计能量定义为E(qr, t) =tk=1e(qr,k) -e(qr,k-1) .量子选择策略根据熵增法则和自由能极小化原理及上面的定义,可以定义如下一种新的适应函数.定义