多目标差异进化算法

2024-06-17

多目标差异进化算法（精选7篇）

多目标差异进化算法第1篇

蛋白质结构及功能预测问题的研究,对揭示蛋白质的表达规律和生物功能提供新的辅助手段,对解释遗传病及传染疾病的生理机制、制备高效安全的生物药剂等复杂的现实应用问题亦具有很高的理论价值和指导意义。如果弄清楚蛋白质的一级结构是如何决定其三级结构这个基本问题,将会使人们更系统和完整地理解具有生物活性蛋白质的传递全过程,使中心法则[2]得到更加完整的阐明,从而对生命过程中的各个现象有进一步的深刻认识,最终推动生命科学的快速发展。

蛋白质结构复杂,种类千变万化,虽然蛋白质结构及功能预测的研究已经取得了一定的成果,对于简单的蛋白质预测已经达到较高的水平,但是在实际较复杂的蛋白质预测上的应用还有很大的一段距离。需要解决的关键技术以及面临的困难还有很多,仍然有一些重要的理论和应用问题尚待解决。

为了进一步研究蛋白质结构及功能预测的研究,提高计算方法的有效性及可理解性,揭示蛋白质天然结构的生理机制, 从多目标优化角度,同时结合进化算法,将其与多目标优化结合起来,研究基于多目标优化的进化算法,提高搜索效能从而为系统的研究蛋白质结构及功能提供了一定的理论基础和实验平台。

1蛋白质结构及功能预测的研究分析

1.1蛋白质结构及功能预测的现状分析

1)理想的能量函数并不存在。根据C.B. Anfinsen的观点, 蛋白质的活性结构像对应于体系能量最小的状态,在一定条件可以认为是能量最小的状态。该函数是一个重要的评价函数, 用以区分天然结构和错误结构。在实际应用中,蛋白质机构复杂,可变参数过多,理想的能量函数并不存在。目前用于蛋白质机构预测的能量函数,不论是统计意义上的还是物理意义上的,都是在一定条件下的拟合,正确程度并不高。同时考虑到模型的复杂性,能量函数多忽略溶剂、氢键、疏水性等因素这对正确预测蛋白质结构及功能带来不利的影响。

2)二级机构预测准确度低。一般的预测方法,考虑到减少计算的复杂性,蛋白质的三级结构预测是根据二级结构的预测的结果、蛋白质的结构类型和折叠类型预测的结果以及空间结构的立体化学性质,搭建出最后的蛋白质空间结构。而二级结构预测基本是以总结已知蛋白质结构规律的基础上而建立的, 总体来说准确度不超过65%,这已经成为蛋白质结构及功能预测的一个较严重的制约条件。

3)构象空间巨大。典型的蛋白质含有几百个氨基酸、上千个原子。所有可能的序列到空间结构的映射数目,随氨基酸残基个数而成指数级增长,即使使用简化后的contact maps模型或torsion angles模型,也是一个天文数字。使用常规的搜索算法,计算量特别大,搜索效率低。目前许多隐藏在蛋白质序列里的信息未被发掘和充分利用,即使使用智能算法如遗传算法、模拟退火、神经网络算法等,也造成了实际应用受到一些制约,导致计算效率和鲁棒性低下。

因此,要提高智能算法在解决蛋白质结构及功能预测问题时的效能,需要充分提高和创新智能算法在搜索机理上理论基础,继续挖掘隐含信息,构造和创建新的计算模型,开发出能解决实际应用问题的更加鲁棒和有效的工具。

1.2蛋白质结构预测方法分析

目前蛋白质结构预测方法可以分为三大类:1)基于知识的比较建模法。这一方法主要指同源结构预测,根据同源结构中保守的部分搭建出未知蛋白质的结构骨架,在20世纪90年代由Blundell等人提出。我国学者丁达夫在同源建模方面有过较深入的研究,开发过PMODELINE蛋白质建模系统。2)反向折叠法。原理基于把未知蛋白质的序列和已知的这种结构进行匹配,找出一种或几种匹配最好的结构作为未知蛋白质的预测结构。1991年Bowie使用一种称为三维剖面(3D-Profile)的方法,根据侧链的埋藏程度、极性原子覆盖率进行打分匹配搜索, 并取得了较好的结果。同时期的Jones则开发出了到目前为止仍有较高研究活力的线串法(threading),通过先建立折叠子数据库,然后匹配搜索打分选取最合适的折叠结构。目前反向折叠法已经比较成熟,具有了一定的实际运用价值。3)从头预测法。其目标是从蛋白质的一维结构序列直接预测三级结构,是最理想的方法。目前这个方法主要受两方面的困扰。一是难以找到一个能严格区分蛋白质的天然构象和非天然的构象的能量函数,二是缺少一种有效的全局优化算法。目前在这种方法大类里,一种称为片段组装(fragment assembly)取得较大的成功,其原理是旋凿已知蛋白质结构数据库里的相似片段进行组装。David Baker研究组开发出基于贝叶斯打分函数的RO-SETTA系统是这一方法的典型代表。目前,美国密西根大学的Yang Zhang教授开发出的I-TASSER (Iterative Threading AS-SEmbly Refinement)方法代表着从头预测方法的最高水平,其主要原理也是片段组装,在片段选择和组装上有了重大改进。由此可见,在蛋白质结构预测方面,尽管当前的研究比较活跃,已经取得了令人瞩目的成果,但是在面对实际蛋白质时,仍然显得理论和方法的欠缺。不过随着使用更高速的计算机、更有效的算法,解决这个问题是可能的。

1.3蛋白质功能预测分析

蛋白质功能预测也是当今生物信息学的一个研究重点,是后基因时代最具挑战性的问题之一。所预测的蛋白质功能主要指疏水性、基因调节、对生化反应的催化性。最流行的方法是基于氨基酸序列, 因为序列是一个蛋白质最基本,最易获得的信息。BLAST使用近似序列比对算法,通过测量目标序列和数据库已知之间的相似之处发现同源关系预测功能。然而,一些研究表明,序列同源性并和功能不总是相关的。另外,直接根据结构预测功能也是一种方法,但是这种方法过于依赖结构预测,描述也过于复杂,常常作为一种辅助手段。近些年,在high-throughput生物技术领域,产生了大量的类似基因表达和蛋白质的相互作用的生物数据,这些数据作可以作为蛋白质功能预测的一个数据分析平台,研究人员已经在这方面做了大量的研究工作。由此可见,蛋白质功能预测正逐渐形成一个科研热点,由于蛋白质功能的复杂性以及预测方法的发展和变化, 蛋白质功能预测的研究存在很多机遇和挑战。一方面,其理论基础还不够完善,尤其是怎样识别一个蛋白质功能还需要较多研究工作。另一方面,新的预测方法的效能还有待提高,特别如何实现不同算法模型之间的融合、协同计算问题。

2多目标优化问题研究分析

多目标优化在具体问题上的应用研究也是当今学术界的一个研究方向和趋势。多目标优化在实际问题上的应用,最早是被Knowles等人在处理如何将一个单目标问题转换成多目标优化问题时被重新提出来的。一般认为,更多的目标函数数量意味着更困难的优化问题,但也意味着更有效的优化过程可以实现,目前多目标优化已经运用到很多应用领域。如旅行商问题、车间调度问题、装箱问题、最短路径和最小生成树问题,并且取得了显著的实验结果。在生物信息学领域,多目标优化也有较多应用,Thomas成功将其应用到基因调控网络。在蛋白质结构及功能预测上,也有较多应用。Becerra将之用于蛋白质的从头预测问题。将多目标优化与进化计算结合起来,用两个目标函数进行了蛋白质的三级结构预测。Olson将多目标与随机搜索算法结合起来,在平衡局部和全局搜索上做了改进, 取得了较好的预测结果。尽管目前的多目标优化在具体问题上的研究已经取得巨大成功,并逐步发展成为研究热点和技术前沿之一,将多目标优化应用到蛋白质结构及功能预测这个问题上,有研究价值和意义。

3结束语

综上所述,目前基于多目标优化的蛋白质结构及功能预测的研究基本还处于前期探索阶段,最终形成成熟的理论和实际应用,还需要更多具有创新性的基础研究,以及大量细致的完善工作。在国内外对蛋白质结构及功能研究十分重视的背景下,适时启动基于多目标优化的蛋白质结构及功能预测的研究是必要且迫切的。因此,通过本项目,将建立起面向各种类蛋白质的结构及功能预测平台,为进一步系统地研究蛋白质结构及功能,揭示蛋白质折叠的生理机制,优化多目标计算模型,同时为生物技术、药物设计等应用领域提供理论研究基础。

摘要：自21世纪初,人类基因组序列图谱公开发表后,生命科学的研究中心已经从基因组学(Genomics)转变为蛋白质组学(Proteomics)。在生物信息学(Bioinformatics)领域,从蛋白质的一维氨基酸序列中预测蛋白质的三维结构及功能,已经成为该领域最重要、最活跃的课题之一。蛋白质结构与功能的研究已有相当长的历史,由于其复杂性,对其结构与功能的预测不论是基础理论还是方法方面难度均比较大。为了进一步提高蛋白质结构及功能的预测方法的可理解,揭示蛋白质结构与功能的深层次对应关系,从多目标优化角度,将该问题转化为多目标问题求解,研究基于多目标优化的蛋白质结构及功能预测的智能算法。

关键词：多目标优化,蛋白质结构及功能预测,进化算法

参考文献

[1]Luscombe N M,Greenbaum D,Gerstein M.What is bioinfor-matics An introduction and overview[J].Yearbook of MedicalInformatics,2001(1):83-99.

[2]Anfinsen CB."Principles that govern the folding of proteinchains[J].Science,1973,181(4096):223-230.

[3]Becerra D,Sandoval A,Restrepo-Montoya D,et al.A parallelmulti-objective ab initio approach for protein structure predic-tion[C]//Bioinformatics and Biomedicine(BIBM),2010 IEEEInternational Conference on.IEEE,2010:137-141.

[4]Cutello V,Narzisi G,Nicosia G.A multi-objective evolution-ary approach to the protein structure prediction problem[J].Journal of The Royal Society Interface,2006,3(6):139-151.

基于改进庄家法则的多目标进化算法第2篇

关键词：多目标进化算法,庄家法则,非支配集,运行效率

0 引言

多目标优化中的最优解通常称为Pareto最优解,它是由Vilfredo Pareto在1896年提出的,因此被命名为Pareto最优解(Pareto Optimal Solution)。

在多目标进化算法中,近年的研究倾向于基于Pareto最优化的方法,通过构造进化群体的非支配集,并使非支配集不断逼近真正的Pareto最优边界实现。一个进化群体的非支配集,实际上也是当前进化群体的最优个体集合。研究如何构造一个多目标优化问题的Pareto最优解集,实际上就是研究如何构造进化群体的非支配集。此外,进化算法的每一次迭代,或每一代进化,都要构造一次非支配集,因而构造非支配集的效率将直接影响算法的运行效率。

庄家法则是构造非支配集的常用方法之一。在一般情况下,庄家法则具有较高的效率,但当种群中的支配个体较多时,算法的运行效率会急剧下降。原因在于,此时参与比较的个体较多,而每次淘汰的个体并不多。

本文提出一种改进的庄家法则,基本思想是:按照一定条件在种群中增设一个副庄家,副庄家和庄家一起参与比较,这样每轮比较可以淘汰更多的个体,从而减少了比较的轮数,减少计算量,提高算法的运行效率。

1 庄家法则

庄家法则是一种非回溯的方法,使用这种方法时,在每次构造新的非支配个体时不需要与已有的非支配个体进行比较,每一轮比较在构造集中选出一个个体出任庄家(一般为当前构造集的第一个个体),由庄家依次与构造集中的其它个体进行比较,并将庄家所支配的个体淘汰出局;一轮比较后,如果庄家个体不被任何其它个体所支配,则庄家个体即为非支配个体,否则庄家个体在该轮比较结束时也被淘汰出局。按照这种方法进行下一轮比较,直至构造集为空。

设P为一进化群体,Q为构造集,初始时Q=P,NDSet为非支配集,初始时为空。从Q中任取一个个体,一次与所有其它个体比较,将被该个体所支配的个体从Q中删除,如果该个体没有被其它任何一个个体所支配,则它是非支配的,将它并入非支配集NDSet中,否则也从Q中清除该个体;以此下去,直至Q为空。

用庄家法则构造集合P的非支配集的方法可以描述如下:

(1)设Q为构造集,初始时Q=P;NDSet为P的非支配集,初始时NDSet=;

(2)从Q中取一个个体x,令Q=Q-{x};D=;

(3)令D=D∪{y|x>y,∀y∈Q};

(4)令Q=Q-D;若不存在z∈Q,使z>x,则令NDSet=NDSet∪{x};

(5)重复步骤(2)~(4),直至Q为空。

为了便于理解,下面给出用庄家法则构造进化群体P的非支配集的具体过程,伪代码算法如下:

2 改进的庄家法则

利用庄家法则构造非支配集时,虽然没有回溯,在一定程度上提高了构造非支配集的速度,但如果庄家在每一轮比较时淘汰的个体比较少,那么就要比较很多轮才能结束,因此对庄家法则进行改进,增加一个副庄家,每轮比较就可以多淘汰一些个体,这样就减少了比较的轮数,改进的庄家法则将会比未改进的庄家法则具有更高的构造非支配集的效率。

改进的庄家法则:每一轮比较在构造集中选出一个个体出任庄家(一般为当前构造集的第一个个体),由庄家依次与构造集中的其它个体进行比较,若在比较过程中出现第一个与庄家不相关的个体,选为副庄家,将庄家和副庄家都与后面剩下的个体比较,将庄家或副庄家所支配的个体淘汰出局;一轮比较后,如果庄家个体不被任何其它个体所支配,则庄家个体即为非支配个体,否则庄家个体在该轮比较结束时也被淘汰出局。按照这种方法进行下一轮比较,直至构造集为空。在这个过程中,每轮选出来的第一个与庄家无关的个体只与后面的个体进行比较,淘汰它所支配的个体,如果它被支配则比较结束后将其淘汰。

改进的庄家法则构造集合P的非支配集的方法可以描述如下:

(1)设Q为构造集,初始时Q=P;NDSet为P的非支配集,初始时NDSet=φ;

(2)从Q中取一个个体x,令Q=Q-{x};D=φ;

(3)若Ǝm与x不相关,则令D=D∪{y|x>y或m>y,∀y∈Q},若Ǝn∈Q,使n>m,则令D=D∪{m};

(4)令Q=Q-D;若不存在z∈Q,使z>x,则令NDSet=NDSet∪{x};

(5)重复步骤(2)~(4),直至Q为空。

为了便于理解,下面给出用改进的庄家法则构造进化群体P的非支配集的具体过程,伪代码算法如下:

3 聚类方法

3.1 基于聚类的多目标遗传算法

在多目标进化算法的研究中,解群体的多样性是最重要的指标之一,下面的实验中将采用层次聚类方法来保持多目标进化群体的多样性。

设群体的大小为N,Popt为第t代群体,Qt为对第t代群体Popt进行遗传操作(选择、交叉、变异)所产生的群体,Qt的大小也是N。令Rt=Popt∪Qt,Rt的规模大小为2N,算法通过不断的构造Rt是非支配集,NDSet,并使NDSet中的个体不断的逼近Pareto最优解集来实现对多目标的进化。如果|NDSet|N,则使用层次聚类方法降低非支配集的大小,使NDSet中包含N个个体,同时使这N个解个体具有较好的分布性。

3.2 基于层次凝聚距离的聚类算法

凝聚的层次聚类方法是一种按照自底向上策略来聚类个体的方法,首先将每个个体看作一个独立的子类,然后逐步合并距离最近的子类,直至满足终止条件。其算法如下:

(1)初始化聚类C,使C中的每个子集包含非支配集ND-Set的一个个体:C=∪i{{i}},i∈NDSet。

(2)如果|C|≤bound,则转(7);否则转(3)。其中bound为非支配集的最大界限值。

(3)计算任意两个聚类之间的距离:

其中‖i1-i2‖表示个体i1和个体i2之间的距离。‖i1-i2‖表示个体i1和个体i2之间的距离。

(4)在当前C中选取新的具有最小距离的两个聚类c1′和c2′:c1′,c2′:min{d(c1,c2)│c1,c2∈C},并将c1′和c2′合并为一个聚类c′:C=C{c1′,c2′}∪{c1′∪c2′}。

(5)如果|C|≤bound,则转(7);否则转(6)。

(6)计算c′=c1′∪c2′与C中其它类之间的距离:d(c′,ck)=(d(c1′,ck)+d(c2′,ck))/2,其中c′,ck′∈C且c′≠ck。转(4)。

(7)针对每个聚类,选取有代表性的个体组成心的非支配集NDSet。这里所谓的有代表性的个体是指每个聚类的核在该聚类中与其它个体具有最小距离。

(8)NDSet=∪i{i},i∈C,结束。

4 数值实验

为了测试改进后的庄家法则在构造Pareto最优解集时的效率,下面进行实验,测试改进后的方法在构造Pareto最优解集时的效率。实验中采用聚类方法来保持进化群体的多样性,用Matlab编程,种群规模Pop Size=100,基因长度len=20,最大进化代数maxdai=100,交叉概率Pc=0.9,变异概率Pm=0.05。下面是进行实验的测试函数:

在基于聚类的多目标遗传算法中,构造非支配集的方法分别采用改进前的庄家法则和改进后的庄家法则,采用层次聚类方法来保持进化群体的多样性(即基于层次凝聚距离的聚类算法)。用改进的庄家法则构造上面两组函数的Pareto非支配集,得到图1和图2。

从图1和图2可以看出,用改进的庄家法则得到的图很接近理论上的图。

表1为算法运行20次的平均值,从表1中可以看出MOEA中构造非支配集时采用改进后的庄家法则,比采用改进前的庄家法则具有更好的运行效率。

5 结束语

本文从理论上分析了庄家法则在构造Pareto最优解集时的缺陷,对用庄家法则构造Pareto最优解集的方法进行了改进,提高了构造非支配集的效率,在一定程度上优化了算法。从实验中可以看出,改进的庄家法则在构造多目标进化群体的非支配集时,比原来的算法具有更高的工作效率。

参考文献

[1]李丽荣,郑金华.基于Pareto Front的多目标遗传算法[J].湘潭大学自然科学学报,2004(1).

[2]郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007.

[3]戴文华.基于遗传算法的文本分类及聚类研究[M].北京:科学出版社,2008.

[4]BALIING RICHARD J.Pareto sets in decision-based design[J],Journal of Engineering Valuation and Cost Analysis,2001(10).

[5]COELLO COELLO CARLOS A,et al.Application of Multi-Objec-tive Evolutionary Algorithms(Advance In Natural Computation,Vol.1)[M].New Jetsey:World Scientific Publishing Co.Pte.Ltd,2004.

[6]COELLO COELLO CARLOS A AND ALAN D CHRISTIANSEN.Two new GA-based methods for multi-objective optimization[J].Civil Engineering Systems,1998(3).

[7]GRIGNON P M AND G M FADEL.A GA based configuration de-sign optimization method[J].Journal of Mechanical Design,2004(1).

[8]GOLDBERG,D E,RICHARDSON J.Genetic Algorithms with Shar-ing for Multimodal Function Optimization[C].Genetic Algorithms and Their Applications:Proceedings of the Scond Internatinal Con-ference on Genetic Algorithms,1987.

多目标差异进化算法第3篇

动态优化问题(Dynamic Optimization Problem, DOP)是指其目标函数不仅与决策变量有关,而且会随时间(或环境)动态变化。动态进化算法研究最早可追溯到1966年［１］,但直到20世纪80年代中期,动态进化算法才逐渐引起学界重视［２，３］。与动态单目标优化问题相比,动态多目标优化问题(Dynamic Multiobjective Optimization Problem,DMOP)早期研究并不多。2000年后,DMOP日益受到众多学者重视,取得一系列成果。Marco等［４］提出了一种邻域搜索算法;Deb等［５］在NSGAII基础上提出了动态多目标进化算法DNSGAII;Iason等［６］提出了一种基于向前预测的动态多目标进化算法;Zhang等［７］提出了动态免疫多目标进化算法;Amato等［８］提出了基于人工生命的动态多目标进化算法;Bingul等［９］提出了自适应动态多目标进化算法。另外,动态多目标进化算法测试函数研究成果也相继出现［１０，１１］。

本文利用函数变化率,对常规动态多目标进化算法中非均匀变异算子进行改进,并对改进算法进行性能测试。

1动态多目标优化问题及其最优解

记V０、VＦ和W分别为n０维、nＦ维和mＷ维向量空间, 则动态多目标优化问题可表述为:

其中,g(v０,vＦ)≤0,h(v０,vＦ)=0分别为不等式和等式约束,f:V０×VＦ→W是目标向量函数,fｉ(v０,vＦ)为第i个子目标函数。

若令V是n维决策变量空间,W是m维目标向量空间,参数VＦ取值于实值空间T的参数,则(1)可描述为

其中,g(v,t)≤0,h(v,t)=0分别为不等式和等式约束,f:V×T→W是目标向量函数。与静态多目标优化问题不同,动态多目标优化问题Pareto最优解和最优前沿不固定,随时间动态变化。

2一种改进的动态无约束多目标进化算法

2.1改进的非均匀变异算子

常规动态多目标进化算法(Dynamic Multiobjective Ev- olutionary Algorithm,DMEA)中常常采用一种带区间分割的非均匀变异算子［１２－１３］,此变异算子用参数λ(0<λ<1) 控制均匀变异程度。以往,多取λ为确定值0.5,这无疑带有一定盲目性,在一定程度上影响算法的性能。本文提出一种根据目标函数变化率确定参数λ的方法,具体为:

Xｐ,Xｃ分别表示父代和子代个体。显然,λ实际上是目标函数的相对变化率。当算法陷入局部收敛时,目标函数变化率λ 很小,此时按照非均匀变异算子的作用机制［１２］,变异程度加大,可在一定程度上避免算法陷入局部收敛,改善算法局部收敛性。

2.2改进的动态多目标进化算法

在DMEA的基础上,采用改进的非均匀变异算子,本文提出一种改进的动态多目标进化算法(Improved Dy- namic Multiobjective Evolutionary Algorithm,IDMEA), 其算法步骤如下:1对时间区间进行等距分割,记不同环境为t１,…,tｓ,令t=t１;2环境tｉ(i=1,2,…,s),随机产生初始种群,令k=0;3对第k代种群中个体进行Perato排序;4以概率pｃ从排序后种群中选取μ个父代进行交叉,其后代集合记为o（ｋ）(tｉ);5对o（ｋ）(tｉ)中的每个个体根据改进的非均匀变异算子进行变异操作,其后代集合记为; 6若达到最大进化代数,则停机,输出计算结果,否则转(3 )。

3数值实验

分别用IDMEA和DMEA、DNSGAII对两个动态多目标标准测试函数DMT１和DMT２进行数值优化计算, 并利用两个性能度量指标函数C-measure和U-meas- ure对算法进行定量评价。

(1)DMT1测试函数

其中,ε是大于0的任意正数。该函数的Pareto最优解集不随时间变化,但Pareto最优前端随时间变化。

(2)DMT2测试函数

该函数的Pareto最优前端随时间变化。

数值实验参数:群体规模为200,进化代数为100,交叉概率为0.8,变异概率为0.1,外部存储器规模为80,ε= 0.1。

图1~图4分别给出了t=0.25和0.5时DMT1和DMT2的Perato最优前端。

由于优化结果具有随机性,仅从Perato最优前端图中很难判别出算法优劣,因此下面根据算法性能统计指标对IDMEA进行测评。利用性能度量指标函数C-meas- ure进行解的收敛性评测,利用性能度量指标函数U- measure进行解的分布性和均匀性评测。

图5给出DNSGAII、DMEA和IDMEA(分别记为1, 2,3)三种算法对DMT1和DMT2在不同环境下C- measure值的统计盒图。其中,第一行前2个图为DMT1在t=0.25时的C-measure值盒图,后2个图为DMT1在t=0.50时的C-measure值盒图;第二行前2个图为DMT2在t=0.25时的C-measure值盒图,后2个图为DMT2在t=0.50时的C-measure值盒图。图中C(i,j) 表示第i种算法和第j种算法对同一问题分别求得的Pa- reto最优解集Aｉ和Bｉ和的C-measure值。

图6中给出DNSGAII、DMEA和IDMEA 3种算法对DMT1和DMT2在不同环境下U-measure值的统计盒图。其中,第一行分别为DMT1在t=0.25和t=0.50时的U-measure值盒图;第二行分别为DMT2在t=0.25和t=0.50时的U-measure值盒图。

从图1~图4中可以看出,IDMEA求得Perato最优解数量较多,分布较均匀。从图5可以看出,C(3,i)>C (i,3)(i=1,2),表明算法IDMEA对不同测试函数在不同环境下求得Perato最优解收敛性比其它两种算法得到的结果更佳。从图6可以看出,算法IDMEA对不同测试函数在不同环境下求得的Perato最优解的U-measure值小于其它两种算法所得的结果,即算法IDMEA对不同测试函数在不同环境下求得的Perato最优解在Perato最优前端上分布更广泛、均匀。

4结语

多目标差异进化算法第4篇

在科学研究和工程应用中, 许多决策问题具有多目标的特点和性质, 它们需要同时满足几个相互冲突的不同目标, 即无法使各个目标同时达到最优, 这类问题称之为多目标优化问题 (Multi-objective Optimization Problem, MOP) 。多目标优化问题存在一个最优解集合, 其中的元素称为Pareto最优解。

由于多目标进化算法在优化控制、挖掘数据、设计机械、移动网络规划等领域的成功应用, 使得学术界兴起研究进化算法的热潮。自上世纪80年代以来, 人们已提出多种多目标进化算法, 比如Srinivas的NSGA, Zitzler的SPEA, Knowles的PAES以及Deb的NSGA-Ⅱ等。

近年来, 一些新的进化算法被用来求解多目标优化问题, 如蚁群算法、粒子群算法、免疫算法、分布估计算法等。

上世纪90年代末, 人工免疫算法开始兴起, 其思想源于生物的免疫系统, 它借鉴了免疫系统的功能、原理和模型并用于进行寻优搜索。由于现在还不能充分认识免疫机理, 所以有关免疫算法的研究基本集中在其它算法。我们用免疫原理来改进并构成新的算法, 比如免疫神经网络、免疫遗传算法等。人工免疫系统算法的自身研究成果并不多, 主要有基于克隆选择原理的克隆选择算法和基于阴性选择原理的阴性选择算法等。

Coello Coello等于2002年最早提出将人工免疫系统算法用于求解多目标优化问题, 并陆续对其进行了改进;Luh等于2003年提出了多目标免疫算法MOIA;Jiao等于2005年提出免疫克隆多目标算法IDC-MA。

与多目标进化算法相比, 人工免疫多目标优化算法具有搜索效率高、避免过早收敛的优点, 但其解的分布性和均匀性较差。为此, 本文提出一种基于聚集密度的人工免疫多目标进化算法, 并依据量化评价指标和数值实验结果对新算法性能进行评测。

1 多目标优化问题相关概念

1.1 多目标优化问题及其最优解

多目标优化问题的数学模型为:

其中, X为决策向量, F (X) 为目标函数, gi (X) ≥0为约束条件。

定义1满足约束条件的解为可行解, 由所有可行解组成的集合称为可行解集, 记作Xf。

定义2若XA, XB是两个可行解, 且

则称XA支配XB, 记为

定义3若可行解X*满足

则称X*为Pareto最优解。

定义4 Pareto最优解所组成的集合称为Pareto最优解集, 记为P*。

定义5由Pareto最优解集P*中的所有Pareto最优解集对应的目标向量组成的曲面称为Pareto最优前端, 记为:

在目标空间中, 目标函数的切点为最优解。两个优化目标的最优边界是一条平面曲线, 三个优化目标的最优边界是一个空间曲面。往往采用Pareto最优前沿表示多目标进化问题的结果。

1.2 最优解集的评价标准

多目标进化算法性能的评价主要考虑两个指标:算法的效率和效果。算法的效率主要指它在求取多目标进化问题的Pareto最优解集时需要的CUP时间, 算法的效果指它求得的Pareto最优解集的质量, 即算法的收敛性和最优解集的分布性。

多目标进化算法的性能评价方法归纳起来可以分为两类[12]:一类是用来评价算法收敛性的方法, 另一类为用来评价解的分布性的方法。

(1) 两个解集之间的覆盖率 (Two Set Coverage, CS)

假设X′, X″X是目标空间中两个非劣解集。函数按以下定义:

其中表示Pareto不劣于。在评价多目标进化算法时, CS (X′, X″) 和CS (X″, X′) 必须同时考虑。

(2) 世代距离 (Generation Distance, GD)

其中, n为算法所得最优前端PFknown中向量个数, di为目标空间中的第i个解与前端PFtrue中最近解之间的欧几里得距离[6]。

GD主要反映了PFknown对PFtrue的逼近程度。

(3) 空间评价方法 (Spacing Metric)

分布度函数定义:

其中, n为PFknown中向量的个数, di为目标空间中每一维向量到最优前端PFtrue中最近向量间的欧几里得距离。

根据上式, SP即为di的均方差。根据方差的定义, SP反映最优解集的均匀性。

2 人工免疫算法[12]

人工免疫算法把抗原对应于优化问题的目标函数, 将抗体对应为优化问题的可行解。抗原和抗体的亲和力作为可行解和目标函数间的匹配程度, 可行解的多样性用抗体间亲和力来保证, 通过计算抗体期望生存率促进较优抗体遗传和变异, 择优后的可行解为记忆细胞, 用它来阻止相似可行解的不断产生并加快搜索到全局最优解, 与此同时, 当类似问题出现时, 适应该问题的较优解甚至最优解就能很快产生。

人工免疫算法的流程如下:

3 基于聚集密度的人工免疫多目标进化算法

由于人工免疫多目标进化算法通常仅采用删除拥挤抗体的方式保证Pareto最优解分布的均匀性[12], 所以解的均匀性和分布性往往欠佳。考虑到聚集密度可以改善种群的多样性, 提高Pareto最优解的分布性, 本文提出将聚集密度引入人工免疫多目标进化算法。

3.1 聚集密度

在进化算法中, 常用的保持解的分布性的方法有:小生境技术、聚集密度和网格等[13]。

聚集密度的计算复杂性较高, 但是它既能从宏观上反应出群体的多样性与分布性, 也能较好地表示出个体之间内在联系, 在进化过程中起到调控群体的作用。

计算个体聚集密度可以用相似度、影响因子和聚集距离的方法。下面介绍聚集距离法[13]。

如下图所示, 设有两个子目标f1和f2, 个体i在子目标m上的函数值用Pm[i]表示, 则图中四边形的长与宽之和可以用个体i的聚集距离P[i]d来表示, 即:

当有r个子目标, 个体i的聚集距离表示为:

一个个体与其邻近个体的距离越大, 表明它的聚集密度越小, 根据这个原则定义个体的聚集密度。为了方便, 我们把聚集距离的倒数定义为聚集密度。

根据聚集密度更新Pareto最优解集的方法如下:

(1) 计算群体中每个个体的聚集密度;

(2) 根据目标函数值和聚集密度定义一个偏序集, 该偏序集中的元素有两个属性:个体的目标函数值和聚集距离;

(3) 根据比例选择原则, 依次从偏序集中选择个体, 更新精英集。

3.2 基于聚集密度的人工免疫多目标进化算法

目前, 代表性的免疫算法有人工免疫网络算法、否定选择算法、免疫遗传算法和克隆选择算法等。本文将聚集密度引入免疫克隆算法, 提出一种基于聚集密度的人工免疫多目标进化算法, 其流程如下:

4 数值实验与算法性能评测

下面用基于聚集密度的人工免疫多目标进化算法对两个标准测试函数Deb2和DTLZ7进行数值计算, 并将计算结果与常规人工免疫多目标进化算法的计算结果进行比较, 从而检验改进算法的性能。

抗体群规模为100, 克隆规模为50, 最大迭代次数为200。

图3和图4分别为Deb2和DTLZ7理论上的最优Pareto前端;图5和图6分别为用本文改进算法求得的Deb2和DTLZ7的最优Pareto前端;图7和图8分别为用常规算法求出的Deb2和DTLZ7的最优Pareto前端。

可以很直观地看出, 基于聚集密度的人工免疫多目标进化算法在解的分布性和均匀性方面均明显优于常规人工免疫多目标进化算法。

为了更进一步地定量评测改进算法的性能, 下面给出基于聚集密度的人工免疫多目标进化算法和常规人工免疫多目标进化算法的世代距离、错误率和分布性指标的对比数据。

考虑到计算结果的随机性, 表中给出的是20次实验结果的平均值。

从表1和表2中可以很清楚地看出, 基于聚集密度的人工免疫多目标进化算法和常规人工免疫多目标进化算法的GD指标相差无几, 但在ER和SP两个指标上明显占优。

多目标差异进化算法第5篇

但是在现实过程中, 对问题的优化往往伴随着目标的约束, 要求在符合一定的条件下, 达到最优化的目的, 并且这些优化问题通常还是多目标的, 需要对多个目标同时进行优化, 即通常所讲的多目标优化问题。以n个自变量和k个目标函数的多目标最大化问题为例来描述多目标约束化问题为[1]:

其中, x= (x1, x2, …, xn) ∈X⊂Rn, y= (y1, y2, …, yk) ∈Y奂Rk, x表示决策向量, y表示目标向量, X表示决策向量x形成的决策空间, Y表示目标向量y形成的目标空间, 约束条件e (x) ≤0确定决策变量x的可行取值范围。这里假设所有的目标函数都要求最大化, 如果其中某一个目标函数fi需要最小化, 只要最大化 (-fi) , 所有的公式仍然成立。

进化算法有一些适于求解MOP的特点, 包括能同时处理一组解个体, 每运行一次即能获得多个有效的解个体, 以及对问题均衡面的形状和连续性不敏感, 即能很好地逼近非凸性或不连续的均衡面或曲线。因此, 多目标的进化算法在近年来就一直用于求解MOP问题。

群体智能优化算法是一种基于群体智能的进化算法, 通过模拟实际生物群体生活中个体与个体之间的相互交流与合作, 用简单、有限的个体行为与智能, 通过相互作用形成整个群体的整体能力。这种算法本质上是一种概率搜索, 它不需要问题的梯度信息, 具有较强的鲁棒性, 并且, 每个个体的能力或遵循的规则非常简单, 群体智能的实现简单、方便, 加上系统用于通信的开销少, 易于扩充, 能通过简单个体的交互表现出高度的智能, 使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决, 大大增强了人们解决和处理优化问题的能力。

1 遗传算法

遗传算法将生物遗传过程中随机配对交叉极致和进化过程中的适者生存法则相结合, 通过模拟生物进化的机制和过程来搜索最优解。

遗传算法首先对解空间进行编码, 每个编码对应要求解问题的一个解, 然后随机选择一组解作为初始的解集, 并根据指定的适应值函数计算出每个解的适应值, 再按照适者生存的原则从初始解中选出一组解按照事先设定好的交叉率和变异率进行交叉和变异操作, 生成一组新解, 随后再次用适应值函数计算每个解的适应值, 再以此过程反复迭代, 直到满足迭代停止条件。此时得到的编码经过解码就可以堪称额所求解问题的近似最优解。

由遗传算法的基本原理, 可得出遗传算法具有以下几个特点:

1) 以决策变量的编码为运算对象, 可以直接操作结构对象;

2) 不受函数约束条件的制约, 由目标函数变换来的适应值函数进行搜索;

3) 采取群体搜索, 具有并行性, 从一组解迭代到另一组解;

4) 具有自组织、自适应性;

5) 不依赖于问题的具体领域和类型, 有很好的通用性。

这些特点使遗传算法不仅具有良好的全局搜索和优化能力, 而且与其他优化算法之间有良好的兼容性。

虽然遗传算法具有很多优点, 但也存在很多不足, 主要缺点表现为以下几个方面[2]:

1) 虽然二进制编码符合最小字符集编码规则, 也便于用模式定力对算法进行分析, 但对连续函数的优化问题存在映射误差, 不便反应所要求问题的特定知识;

2) 随机产生的初始种群无法保证种群的多样性, 在求解高要求精度的问题时容易陷入局部最优;

3) 由于不限制适值函数的取值范围, 不能保证算法一定收敛;

4) 静态设置控制参数, 且参数的选取主要靠经验, 不能适应环境的变化;

5) 在需要优化的参数较多时, 明显表现不足等。

2 粒子群算法

粒子群优化算法的提出是基于对简化的社会模型的模拟。由Eberhart和Kennedy于1995年根据鸟群捕食的行为研究所得。算法的基本原理可描述为:一个由若干粒子 (Particle) 组成的群体 (Swarm) 在D维搜索空间中以一定的速度飞行, 每个粒子在搜索过程中, 考虑自己搜索到的历史最好点以及群体内 (或者是邻域内) 其他粒子的历史最好点, 并在这个基础上执行位置上 (或者是粒子的状态上, 也就是问题的解) 的变化。设第i个粒子的位置表示为xi= (xi1, xi2, …, xid) , 此粒子的速度表示为vi= (vi1, vi2, …, vi D) , 1≤i≤m, 1≤d≤D, 并且此粒子经历过的历史最好点表示为pi= (pi1, pi2, …, pi D) , 群体内 (或邻域内) 所有粒子经过的最好点为pg= (pg1, pg2, …, pg D) 。一般地, 粒子的位置和速度是在连续的实数空间内取值。每个粒子的速度和位置按照如下方程变化[3]:

其中, c1, c2为学习因子或者称为加速系数, 一般取正常数。学习因子使粒子有自我总结和向群体中的优秀个体学习的能力, 从而向自己的历史最优点以及群体或邻域内的历史最优点逼近。ξ, η∈U[0, 1], 是在[0, 1]区间中均匀分布的伪随机数, 每个粒子的速度上限为Vmax。

为改善算法的收敛性能, Shi和Eberhart在1998年的论文中引入惯性权重这一概念, 并且将速度的更新方程改为:

其中, ω为惯性权重, 其大小决定了对粒子当前速度继承的多少, 惯性权重选择得适当, 就能使粒子具有均衡的开发能力 (即局部搜索能力) 和探索能力 (即广域搜索能力) 。特别的, 当ω=1时, 就是基本粒子群优化算法。

粒子群算法的优点在于收敛速度快并且容易实现, 加之其需要调整的参数比较少, 就可以直接采用实数编码, 算法的结构也就相对简单。但是, 粒子群算法的缺点也比较明显, 例如其实施过程与参数的取值有较大的关系, 而参数的取值仍然是一个亟待解决的问题;在解决高维复杂问题优化时, 经常会陷入局部最优;或者在接近或进入全局最优点区域时的收敛速度也会比较缓慢。

3 蛙跳算法

混洗蛙跳算法是一种受自然生物模仿启示而产生的基于群体的协同搜索方法, 此算法模拟青蛙群体在寻觅食物时, 分成不同的族群进行思想传递的过程, 将全局信息交换与局部搜索结合, 局部搜索使局部的个体间信息传递, 混合策略使局部见的思想得到交换[4]。

在混洗蛙跳算法中, 种群由许多只结构相同的青蛙组成, 每只青蛙代表一个解。整个种群分成多个子群, 每一个子群包含一定数量的青蛙, 称为一个memeplex, 不同的memeplex使具有不同思想的青蛙的集合, 分别按照一定策略在解空间中执行局部深度搜索。每一个memeplex中, 每只青蛙都有自己的思想, 并且受其他青蛙思想的影响, 通过memetic进化来发展, 在经过定义的局部搜索迭代次数结束后, 思想在混合过程中进行交换。这样, 经过一定的memetic进化以及跳跃混合过程, 这些想法就在各个memeplex中传播开来, 然后, 局部搜索和混合跳跃过程一直持续到满足了定义的收敛条件为止。局部深度搜索和全局跳跃交换的平衡策略使算法能跳出局部极值点, 向全局最优的方向进化, 这也是混洗蛙跳算法的主要特点[5]。

蛙跳算法的流程具体为:

①始化种群。在可行解空间Ω⊂Rd中, 随机生成初始种群F包含k=m*n只青蛙, 其中, m表示memeplex的数量即子种群的数量, n为每个memeplex中青蛙的只数, d是维变量。每一只青蛙代表青蛙的当前位置, 在应用于解决优化问题时表示解空间中的一个候选解, 则第i只青蛙表示为F (i) = (Fi1, Fi2, …, Fid) , 设F (i) 的适应值用fi表示。

②将所有青蛙排序。将整个种群中其中, F (i) 表示排在第i位的那只青蛙, 因此, 当i=1时, 表示这只青蛙的位置最好。

③将青蛙分组。将整个种群分成m个memeplex:Y1, Y2, …, Ym, 每一个memeplex包含有n只青蛙, 可将其表示为:其总, k=1, 2, …, m, 也就是第1只青蛙进入memeplex1, 第2只青蛙进入memeplex2, 直到第m只青蛙进入memeplex m, 然后第m+1只青蛙又进入memeplex1, 第m+2只青蛙进入memeplex2, 直到第2m只青蛙进入memeplex m, 并且依此类推, 直到所有青蛙分配完毕。

④在每一个memeplex中做memetic进化。在每个memeplex中, 每只青蛙都受到其他青蛙思想的影响, 通过memetic进化, 每只青蛙都向目标位置靠近, 具体memetic进化步骤如下:

a) 设im=0, 0≤im≤m, 表示memeplex的计数i N=0, 0≤i N≤N, 表示进化的迭代次数, N为设定的最大迭代次数

用Pg表示整个种群中位置最好的青蛙, 显然, Pg就是F (1) , 并且, 在每组memeplex中, 用Pb表示本组中位置最好的青蛙, 用Pw表示本组中位置最坏的青蛙, 在每一次进化中, 改善最坏位置青蛙Pw的位置

b) im=im+1

c) i N=i N+1

d) 设青蛙移动的距离为di N+1=rand () * (pb-pw) , 则青蛙的新位置为:

其中, rand () 是介于0与1之间的一个随机数。Dmax是允许青蛙移动的最大距离, 当di N+1>Dmax时取Dmax, 当di N+1<-Dmax时取-Dmax。

e) 若上述过程能使原位置最坏的青蛙达到一个好的位置, 即能产生一个更好的解, 就用新位置上的青蛙取代原来的青蛙, 否则, 用Pg代替Pb重复上述过程。

f) 若用Pg代替Pb重复上述过程仍不能生成更好的青蛙, 就随机生成一个新位置的青蛙取代原最坏位置的青蛙Pw。

g) 若i N

h) 若im

⑤将青蛙混合, 也就是使青蛙在各memeplex间跳跃。在每个memeplex都执行了一定的memetic进化后, 将各子群Y1, Y2, …, Ym重新合并为X, 即X={Yk, k=1, 2, …, m}, 然后将X更新按适应值的降序排序, 并且及时更新整个种群中最好的青蛙Pg。

⑥若达到迭代的终止条件, 则停止迭代, 否则跳转至步骤③。一般来说, 当循环进化到一定次数后, 代表最好解的青蛙就不再改变了, 这个时候, 算法停止, 有时, 也可以通过设定最大迭代进化次数来作为终止条件。

与其他的进化算法相近, 混洗蛙跳算法是一种基于群体智能的后启发式计算技术, 结合了模因演化算法和粒子群算法这二者的长处[6], 并且概念简单容易理解, 参数少, 全局搜索能力比较强, 在最初应用于水资源网络的分配问题时, 产生了较好的效果。但是, 对于一些复杂的问题这个算法依然存在着收敛速度不是很快、易于陷入局部极值的缺点, 并且传统的蛙跳算法模型适合于解决连续优化问题, 不适合解决离散的组合优化问题。

4 总结与展望

以上就是对遗传算法、粒子群算法这两种典型群体智能优化方法以及蛙跳算法这种新兴的群体智能优化方法简单的研究, 通过对比可以看出, 每种算法都有自己独特的优点和缺点, 但是面对高维的复杂问题的时候都表现出容易陷入局优、不能保证很好的收敛。

其实, 除了上述几种优化方法, 还有很多的群体智能优化方法如蚁群算法、鱼群算法等等, 我们可以对这些算法进行更加深入的研究, 利用各算法的优点, 将其结合起来, 对某种算法进行改进, 取长补短, 就可以更好地解决多目标优化问题。

摘要：进化算法具有适于解决多目标优化问题的特性, 近来一直用于求解此类问题。群体智能优化算法是一种基于群体智能的进化算法, 通过简单个体的交互表现出高度智能, 大大增强了解决和处理优化问题的能力。分析了遗传算法、粒子群算法和混洗蛙跳算法的具体流程, 比较了这三种进化算法的优劣。

关键词：进化算法,群体智能,遗传算法,粒子群算法,混洗蛙跳算法

参考文献

[1]谢承旺, 丁立新.多目标进化算法中选择策略的研究[J].计算机科学, 2009, 36 (9) :167-170.

[2]徐波.遗传算法及其在数据挖掘中的应用[J].电脑编程技巧与维护, 2010, (4) :9-11.

[3]汪定伟, 王俊伟.智能优化方法[M].北京:高等教育出版社, 2007.

[4]EUSUFF M M, LANSEY K E.Water distribution network design using the shuffled frog leaping algorithm[A].World Water Congress[C].2001.

[5]栾垚琛.混洗蛙跳算法研究及其发展现状[J].大众科技, 2009 (1) :25-26.

多目标差异进化算法第6篇

一、配送车辆调度(VSP)问题的数学模型

基于直观描述的无时限单向物流配送车辆调度问题的一般描述为:设物流中心有K台配送车辆,每台车的载重为Qk(k=1,2…,k),一次行驶的最大路程为Dk。需要向L个客户送货,每位客户的客运需求为qi(i=1,2…,L),客户i到j的运距为dij,物流中心到客户的运距为dij(i,j=1,2,…,L)|,再设nk为第k台车辆配送的客户数(nk=0表示未使用第k台车辆),用集合Rk表示第k条路径,其中元素Rki表示客户Rki在路径k中的顺序为i(不包括物流中心),令RK0=0表示物流中心。

若以配送车辆数最少为优化目标时,目标函数表示为:

若以配送总里程最短为优化目标时,目标函数表示为:

若以配送车辆的总吨位公里数最少为优化目标时,目标函数表示为:

约束函数为式(4-10)

二、DNA进化算法

DNA进化算法是对单亲生物自然进化过程和行为的一种模拟。在DNA中,分裂能繁衍生成具有等价关系意义下的同类个体,变异操作实现不同类个体间的演化。分裂和变异操作后分别经水平选择和垂直选择,使群体得到双向进化,增加优化效果,得到更优解。

1. 编码方法

为了节省存储空间,提高运行效率,对于多目标物流配送问题采取自然编码。首先构造DNA单链,针对研究本文研究的问题,将DNA分子中的每个基因用客户编号表示,随机产生一个1~n的序列(n表示客户总数),这样一个个体就产生了,重复上述过程,产生多个个体组成的初始群种。

在此算法中,个体适应值采用其目标函数。对于某个单链个体其目标函数值为Zij,对应的配送路径方案的不可行路径数为表示该抗体对应一个可行解),评价函数值为Mij(Mi=0,定义适应值函数为:,其中R为对每条不可行路径的惩罚权重可根据目标函数的取值范围取一个相对较大的正数。

2. 基本操作算子

DNA进化编码采用分裂、变异和选择三种算子,其中选择算子有两个,分别是水平选择算子和垂直选择算子。分裂算子是产生新个体的方法,根据自身进行繁殖得到后代,避免陷入局部最优,分裂得到的个体多是经过恒等变换,反演变换,同互补和异互补得到;水平选择算子是从分裂集中选取一个DNA表形,不仅挑出最好的个体,而且最差的个体;变异算子是对经过水平选择的各个体进行变异操作,由于研究问题的解的范围较大,因此采用领域变异,最好个体的邻域空间是将个体中的第一个基因和后面的每一个基因进行依次交换得到的邻域空间,最差个体的邻域空间是随机产生的1~n(客户总数)的两个数,将这两个数中间的基因段进行交换得到的邻域空间;垂直选择算子是从变异领域中选择出某一变型,使得个体迁移,从而得到它的最优变形型;将变异后的个体通过适应值函数的求解从而得到最优解。

三、小结

本文研究了DNA进化算法,并对算法的变异操作进行改进,将这种算法运用于多目标物流配送问题中,为进一步研究物流配送优化调度问题并用于实际,提高企业效益提供参考。

摘要：本文基于建立一种多目标物流配送车辆调度模型的基础上,采用DNA进化算法求解该问题,克服传统算法的求解速率低,易陷入局部最优的问题,为进一步研究物流配送优化调度问题提供参考。

关键词：物流配送,车辆调度DNA进化算法,优化

参考文献

[1]李军郭耀煌.:物流配送车辆优化调度理论[M].北京:中国物资出版社,2001,2～13

多目标差异进化算法第7篇

能源是人类社会赖以生存和发展的物质基础。大力发展可再生能源,用可再生能源逐步取代生化资源,进行一场能源革命,不仅是出于生存的原因,与之相连的是我国经济可获得持续的发展。因此,大力发展可再生能源以及研究其具体应用是我国解决能源紧张和保护生态环境的重要战略任务[1]。

分布式电源(Distributed Generation,DG)是指功率介于数千瓦至50 MW、小型模块式的、与环境兼容的独立电源。分布式电源主要包括风机(Wind Turbine,WT)、光伏电池(Photovoltaic,PV)、微型燃气轮机(Micro Turbine,MT)等[2]。

DG输出功率的波动性、随机性等特点潜在地增加了电网规划的难度[3]。针对DG接入配网优化问题,文献[4]等基于链式配电网络、恒功率静态负荷模型和分布式电源功率模型,提出一种图解与遗传算法相结合的计算方法确定DG最佳接入位置和容量;文献[5]等提出一种考虑配电网保护动作和分布式电源短路电流衰减特性影响的DG准入容量的分析方法;文献[6]等提出一种基于改进微分进化算法的风光互补混合供电系统容量优化配置模型,考虑风、光和蓄电池的出力特性曲线;文献[7]研究了典型DG的发电特性,建立了一年60 h的风速、太阳辐射量计算模型。

上述文献都不同程度地简化了DG的功率输出特性,对DG的风、光概率统计模型鲜有涉及,所作研究与实际情况有较大差别。本文在总结前人工作的基础上,主要做出如下工作:(1)计及利用可再生能源发电DG的出力随机性,建立了基于概率密度函数的不同类型DG的出力模型,包括风机、光伏电池和微型燃气轮机;(2)目标函数中综合考虑DG建设运行成本、网损、供电可靠性和环境因素,以经济价值作为衡量;(3)提出量子微分进化算法解决DG的多目标优化,量子微分进化算法具有较强的搜索性和良好的收敛性,算例证明适用于求解本文提出的多目标问题。

1 考虑概率特性的分布式电源发电模型

1.1 组件模型

1.1.1 风机

风速拟合的一个很好的工具是威布尔概率密度函数[8],本文采用最小二乘法[9]估算威布尔参数。威布尔概率密度函数如式(1)所示。

式中:k为形状参数,无因次量;c为尺度参数,其量纲与速度相同;WT输出功率计算方法详见文献[10]。

1.1.2 光伏电池

本文选用贝塔概率密度函数[11]描述光照的随机行为,采用历史数据的平均数和方差估算贝塔参数[12]。贝塔概率密度函数如式(2)所示。

式中:s为光照强度;α≥0;β≥0;0≤s≤1;PV输出功率计算方法详见文献[13]。

1.1.3 微型燃气轮机

本文采用负荷总量模型,因此不考虑冷热电三联产,MT输出功率恒为额定功率,概率模型为1。

1.2 概率状态划分

本文考虑风、光的不确定性,将WT、PV的功率输出作为多变量处理。分别根据风速和光照强度的上下限将连续的概率密度函数划分成多个状态,并采用式(3),式(4)计算风速和光照强度处于各状态的概率。

式中:PWT_w为风速发生在状态w时的概率;vw2和vw1分别处于状态w时风速的上、下限;PPV_y为光照强度发生在状态y时的概率;sy2和sy1分别为处于状态y时光照强度的上、下限。

1.3 电源-负荷综合模型

本文应用不同类型的DG和负荷建立混合的电源-负荷模型。假设风速状态和光照状态是独立的,则它们共同的概率能够通过两者的乘积获得,如式(5)所示。

基于此概念,DG的输出功率和负荷组合起来就可以形成电源-负荷模型,如式(6)所示。

式中:R为电源-负荷模型;Cg为N行四列的矩阵,分别为g状态下风机、光伏电池、燃气轮机的输出功率以及负荷水平;为N行一列的矩阵,对应于矩阵Cg的每一行的风光发电组合发生的概率;N为模型R的离散状态总数,即风速和光照的状态组合总数。

2 分布式电源多目标优化规划模型

本文综合考虑DG建设运行费用、网损费用、可靠性经济费用[14]和环境因素费用[15,16],在满足电网各个约束条件[17]的基础上达到总体最优化。归一化目标函数具体描述如式(7)所示。

其中:式(7)表示年均综合费用,包含了DG建设运行总成本(CDG)、网损费用(CLOSS)、可靠性经济费用(CR)、环境因素费用(CE),w1~w4为权重系数;式(8)为DG的建设运行总成本,其具体含义将在式(12)~式(14)中给出;式(9)为网损费用,Ploss为状态g时系统的电力损失总量,Cpu为单位电价;式(10)可靠性经济费用,EEENS为期望缺供电量;α1、α2分别为产电比法和平均电价折算倍数法的加权系数,K为产电比,b为单位停电电量电价与平均电价的比值,d为平均电价;式(11)为环境因素费用,V0k、Qk、Vk分别为第k项污染物的环境价值、排放量及排污收费额,Cs为单位DG发电量的政策补贴;PDG为节点i处接入的DG容量,Cx为第xi种DG的容量系数。其中,式(8)又可分解为

其中:式(12)~式(14)分别为风机、光伏电池和燃气轮机的年均建设运行成本,aWT为风机造价,r0为贴现率,mWT为风机运行年限,uWT为风机年运维费用系数,NWT为风机数量;式(13)、式(14)与式(12)类似,这里不予介绍,唯一要提及的是式(14)中的第二项为系统年运行的天然气费用,xf为天然气单价,Vt为燃气轮机耗气量,t为燃气轮机年利用小时数。

3 量子微分进化优化算法

3.1 量子染色体编码方式

其中:μ、v为量子态|0>和|1>的概率幅;|μ|2、|ν|2表示|φ>处于|0>态和|1>态的概率,满足|μ|2+|ν|2=1。本文量子比特概率幅用量子角形式[θ]=[cosθsinθ]T表示,对于种群规模为m,长度为D的量子个体的编码定义为

其中,量子角θtij=2πfr;fr为[0,1]之间的随机数;t为当前迭代次数。本文中表达式(16)简写为pti=(θti1ti2,…θtiD)。

为了评价量子个体优劣,需要对每个量子染色体的状态进行观测,使其从量子角形式坍缩至经典的比特形式,观测方法为:对于量子角形式的个体的每一位,对应的二进制位产生一个随机数z∈[0,1],若z>|cos(θtij)|2则该位取1,否则取0。

3.2 量子染色体状态更新

QDE算法中量子染色体状态的更新借鉴微分进化算法(Differential Evolution,DE)[20],在迭代过程中,利用微分进化对当前的染色体进行变异,交叉操作,生成临时种群后,采用贪婪算法对种群进行选择操作。

QDE算法按照式(17)对采用量子角形式编码的量子染色体pit=(θti1,θti2,…,θtiD)实施变异操作,得到对应的变异个体Wit+1=(wi1t+1,wi2t+1,…,witD+1)。

其中,i,s1,s2,s3∈{1,2,…,m}且i≠s1≠s2≠s3,缩放因子F为[0.5,1]之间的随机数。然后利用式(18)对原个体pit和变异个体Wit+1进行交叉操作生成试验个体Mit+1=(mi1t+1,mi2t+1,…,miDt+1)。

其中,rand()产生(0,1)之间均匀分布的随机数,jrand∈{1,2,…,D},交叉概率CR∈[0,1],θtij对应于个体pit的第j个比特位量子角,j∈{1,2,,D},最后通过试验个体Mit和原个体pit之间的竞争,利用贪婪算法选出适应度更优的个体作为新一代量子个体:

4 规划流程

4.1 编码策略

本文所提出的DG优化规划包括DG的位置和容量的优化。将可接入分布式电源的节点作为决策变量,每个决策变量占据染色体的两个位置,奇数位表示接入DG的类型,偶数位表示接入DG的容量。

奇数位为离散值,分别为0,π/,π,2π,分别表示不接DG、接入风机、光伏电池和燃气轮机。偶数位为连续值,范围为0到该节点能接入的最大DG容量。

4.2 规划流程

运用本文所提出的QDE算法,对分布式电源多目标优化的流程如下:

1)初始化算法参数。设置种群规模N,迭代次数R、交叉概率CR以及缩放因子F等参数。

2)初始化种群。在决策变量的变化范围内,利用式(16)随机生成N条初始染色体。

3)判断各量子比特位是否满足DG馈线和系统容量约束,若满足则执行步骤4),否则重新初始化种群。

4)根据式(17)、式(18)对量子种群进行变异,交叉操作产生子代种群。

5)对量子个体进行观测,评价量子个体适应度,采用基于贪婪思想的选择算子进行选择操作,并记录当前最优量子个体和最佳适应度。

6)若算法达到迭代次数,则输出最优结果,迭代结束,否则重复步骤4)~步骤5)。

5 算例分析

本文选取北方某一地区,风、光资源丰富。由于该地区的网络基础数据无法获得,本文采用IEEE-16节点三馈线系统作为测试算例。该地区日照数据、风速数据、系统用户所需负荷、配电网网络情况以及参数设置详见文献[21]。

根据历史数据拟合出的威布尔函数和贝塔函数分别如式(20)、式(21)所示。

根据地区实际情况对风速和光照辐射量进行状态划分,如式(22)、式(23)所示。

其中,FWT、FPV分别为风速和光照辐射量的概率分布。

算法参数选取为:种群规模取50;缩放因子F变化范围取0.5~0.8;交叉概率CR取0.8~1;迭代次数R取150次。

1)权重设置为:w1=w2=w3=w4=0.25;运用本文所提模型及算法进行寻优,优化结果如表1所示。

在满足最优目标函数值的条件下,需要在节点7和节点16出处分别接入1台风机,节点10处接入3台微型燃气轮机,节点15处接入222个光伏电池板。

从优化结果可以看出,最优接入方案以风力发电和燃气轮机发电为主,占总负荷的比重分别为7.67%和14.11%。风力发电的成本远远小于光伏电池,并且已经大量投入商业化应用,而燃气轮机的出力持续且固定。光伏发电只占总负荷的2.09%,因为光伏发电限制很大,只能在白天发电,不能解决晚峰问题,而且成本昂贵,因此若要大规模推广光伏发电,不仅需要政府的大力支持,而且在技术上还需要加大研究力度。

2)为了体现分布式电源在环境上的贡献,以及考虑到现在市场情况下分布式电源接入需要较高的费用,因此仿真降低了DG建设运行成本费用的权重,增加了环境因素的权重。权重设置为:w1=0.15、w2=0.25、w3=0.2、w4=0.4;优化结果如表2所示。

在满足最优目标函数值的条件下,需要在节点7和节点15出处分别接入1台和2台风机,节点10处接入2台微型燃气轮机,节点11处接入296个光伏电池板。

对比表1与表2,最明显的特征是表2采用的优化方案环境因素的费用是负数,也即在此优化方案中,分布式电源带来的环境效益大于需要支出的环境成本,这是完全符合国家可再生发展战略的。但是在该方案中DG建设运行费用增加了520万元,因为光伏电池造价很高,当DG建设运行费用权重减小而环境因素费用增大时,粒子在寻优时会优先考虑在该节点上接入风机和光伏电池,随着光伏电池和风机的接入数量增多,网损费用和可靠性经济费用相应也有所增加。

本文以配电网接入DG后网损最小为目标函数,并采用QDE算法和DE算法对其进行单目标寻优,各优化150次,比较QDE算法和DE算法的性能,优化结果和最佳适应度曲线如表3和图1所示。

从图3和表1可以看出,QDE算法表现出较好的搜索效率和寻优结果,两种算法所需迭代次数基本持平。实际运算中,QDE算法的计算时间较DE算法长一些,这主要是由于QDE算法需要从量子位向十进制转换。但总体上,QDE性能优于DE算法。

图2为随机抽取的一次测试中,QDE算法与DE算法在第30、60、90、120、150次迭代中各量子染色体在解空间中的分布情况。在迭代初期,两种算法的染色体在空间基本均匀分布;在第60代时,DE算法逐渐丢失种群多样性,往较优解聚集,QDE算法虽然已经寻到最优解,但是仍有变异粒子继续寻优;在迭代后期时,DE算法陷入局部最优,而QDE算法仍保持很强的全局搜索能力。

算例说明,与DE算法相比,QDE算法具有以下优点:1)QDE算法既能实现量子算法的并行性搜索,又能在相同的迭代次数中得到更优解;2)由于采用量子比特概率幅编码方案,QDE的种群多样性优于DE算法,减少了算法收敛于局部最优的概率,提高了算法的全局搜索能力。

6 结论

本文综合考虑地区的自然资源实际情况,在满足配电网安全可靠运行基础上,采用QDE算法对接入配电网的分布式电源的容量和位置进行多目标优化配置。本文主要工作总结如下:

(1)选取风机、光伏电池和微型燃气轮机这三种典型的DG进行优化,分别建立其各自的概率模型和出力模型,并且形成统一的电源-负荷模型。这个模型计及分布式电源的出力随机性,使得规划结果更加贴合实际。

(2)建立了综合考虑DG建设运行成本、网络损耗、供电可靠性和环境因素的分布式电源优化配置的多目标函数,对每个子目标函数设置权重,由决策者根据不同情况决定权重的大小,使优化结果更加灵活。

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【多目标差异进化算法】相关文章：