改进的进化神经网络（共8篇）
改进的进化神经网络 篇1
随着城市发展速度的加快、规模的扩大和天然气行业的不断扩展,使得天然气网络传输系统逐渐扩展,网络结构复杂性加大,并且很多管线所穿越区域包括人口密集区、商业区及环境脆弱区等。此外,随着大庆油田天然气产量的逐年增长和天然气业务的迅速发展,对外输的气量必然会迅速增加。上述一系列因素都对天然气管道的安全、平稳和正常运行提出了更加严格的要求。同时由于各种人为和自然因素的存在,如: 偷盗、管道劣化、腐蚀、老化及自然灾害等,天然气管道运行中的一些重大安全隐患会凸显出来。一方面可以对天然气管道进行风险管理( 识别、分析、估算等)［1］,另一方面应该对天然气管道泄漏检测技术和方法进行深入研究。
目前研究、应用管道泄漏检测和定位的方法诸多,但一般可将其划分为三大类,即基于信息、 基于模型和基于知识的方法［2］。这些方法多用于输油管道的泄漏检测和定位,并已经取得了不错的实际应用效果。宋志强等提出利用漏磁信号来检测管道缺陷的方法,但该方法要求将管道进行清扫,尽可能除去管道内的杂质和碎片［3］。由于输气管道与输油管道自身特性的不同,有些检测方法并不能直接用于对气体管道进行泄漏检测, 因此根据气体管道流动的特性研究与其相适应的泄漏检测与定位方法是很必要的。
笔者依据天然气管道特点和常规泄漏检测方法存在的不足之处,提出了将神经网络与差分进化算法相结合的天然气泄漏预测方法［4］,从而避免了建立管道数学模型的复杂性,进一步提高了泄漏检测精度。并通过实际采集的某管道的泄漏数据作为数据网络的学习和验证数据,证明了该方法的有效性。
1差分进化算法及其改进
1.1差分进化算法的原理
差分进化( DE) 算法实质上是基于种群进化和实数编码的一种随机搜索算法,问题求解方式是采用种群间个体的竞争与合作来进行的,竞争与合作是通过算法的变异、交叉和选择3个基本操作来完成的。DE算法的基本思想是: 进行随机的种群初始化,在所求解的问题空间,将随机的两个个体矢量通过相减加权操作来构成下一步所需的变异矢量,然后以一定的概率,将个体的父代与变异得到的个体进行交叉操作,进而得到试验个体,随后以适应度大小为依据在父代个体与试验个体之间选择适应度最好的那个个体作为新的子代,之后循环进行,直至得到问题的最优解［5］。
1. 1. 1初始化
首先在所优化或所求的问题的可行解空间 Ω 中随机产生初始种群P( G) = { xG1,xG2,…,xGi, …,xGNP} ,G∈{ 0,1,…,gmax} ,G = 0时代表初始化种群,gmax为最大允许的进化代数,xGi为第G代种群中的第i个个体,NP为种群中的个体总数。 其中xGj= ( xGj1,xGj2,…,xGj D) 称为P( G) 中的一个个体,j = 1,2,…,NP,每个xGj表示所求问题的一个候选解。
1. 1. 2变异操作
利用变异策略以父代的种群个体为基础来生成新种群的个体进入中间代是变异操作的基本思想,因此得到新的候选个体是执行变异操作的最终目的,用变异操作来使种群的多样性增加,进而使种群在其引导下向所期望的方向发展变化。
差分矢量和另外的由随机选择产生的个体矢量相加就生成了变异矢量,为此每个目标矢量xiG的变异操作定义为:
其中r1、r2、r3在[1,2,…,NP]之间,为随机选择的与i互不相同的3个数; F为缩放因子,差分矢量的幅值由它控制,通常为固定实数,取值范围为[0,2]。
1. 1. 3交叉操作
为了增加种群的多样性,利用交叉操作来扰动原始种群的个体分布,进而产生新的种群个体。 算法的基本思路是: 将目标矢量xGi，j与新生成的变异个体vi，jG + 1进行交叉操作,进而产生所需的试验矢量ui，jG + 1。此外,为保证xGi，j个体的进化, 先通过随机选择使ui，jG + 1的值至少有一位由vi，jG + 1贡献,而其他位由交叉概率因子CR来决定ui，jG + 1中的哪一位由vi，jG + 1贡献,哪一位由xGi，j贡献,交叉操作可表示为:
其中,CR∈[0,1],rand( D) 产生[1,D]之间的随机整数,这是为了保证试验矢量ui，jG + 1中至少有一维变量由变异矢量贡献,避免试验矢量与目标矢量相同而无法产生新的个体。
1. 1. 4选择操作
在种群规模恒定的情况下选择操作的作用是将不适应环境的个体进行淘汰,进而使种群中的优良个体保留下来,从而使种群沿着期望的方向进行进化,最终使整个种群向最终最优值收敛。 差分进化采用“贪婪“搜索策略,在原种的种群个体与交叉操作后产生的试验个体之间进行选择, 即让具有最优适应度的个体进入下一代。也就是将变异、交叉操作后生成的试验个体ui，jG + 1与xGi，j进行竞争操作,当ui，jG + 1的适应度比xGi，j优秀时被选作子代继续进化,反之,则将直接使用xGi，j作为子代进行进化,选择操作可表示为:
式中f( xGi，j) ———第G代第i个个体的适应度。
1. 2改进的DE算法
1.2.1算法描述
收敛性和收敛速度受交叉概率因子CR和缩放因子F取值的影响[6]。对于交叉因子CR而言:实践表明,在初始阶段较小的CR值能提高全局搜索能力,而在后期用较大的CR值,有利于加速收敛,增强局部开发能力,有利于DE算法性能的提高;而对于缩放因子F而言:较大的F初值,有利于收敛到最优,后期较小的F值,能加快收敛速度以保证其收敛性。
笔者采用自适应变异算子和缩放因子的方法使其能根据算法的搜索进展情况,自适应地确定变异率和缩放因子的值,即使CR随进化代数的增加自适应地递增,初期较小以提高全局搜索能力;后期较大以加速收敛,提高局部开发能力。F随进化代数的增加自适应地递减,初期有较大的变异率并保持个体的多样性,避免早熟;后期逐步降低变异率,保留优良信息,避免最优解遭到破坏,增加了搜索到全局最优解的概率。具体公式为:
其中,Gmax为最大进化代数,G为当前进化代数,rand产生0~1之间的随机数,F0、CR0根据实际效果设置。
由式(4)~(6)可知自适应的F值和CR值使算法在初期保持了种群的多样性和适当的收敛速率,而在算法后期又使收敛速率和求解的精度得到了提高,总之使算法既具备了较强的全局搜索能力又拥有了较强的局部搜索能力,提高了DE算法的性能。
1. 2. 2仿真实验
笔者将基本DE算法与改进后的DE算法进行比较,参数设置为: F = 0. 8,CR = 0. 6,Gmax= 1 000,多次仿真发现,当F0= 0. 1、CR0= 0. 1时性能最好。分别测试NP = 50和NP = 100时的运行结果,每个测试各自独立运行20次,记录20次结果的平均值和标准差,对比结果见图1和表1。
图1适应度随进化代数变化的曲线
从图1和表1可知: 改进后的DE算法在收敛速度和寻优精度上的性能均明显优于DE算法,其具有了更好的全局探索和局部开发能力。
2基于改进DE算法的神经网络管道泄漏检测
对于实际天然气管道产生的泄漏信号而言, 经过小波消噪处理后的信号需进一步根据其特征参数对该段管线的泄漏状况进行判断［7］。因此笔者针对天然气管道自身的特点和需求,搭建RBF神经网络天然气管道泄漏判断的模型,对经过小波消噪处理后提取的特征值进行泄漏判断,并验证了该模型的有效性。
2. 1网络结构确定和特征选择
将从实际天然气管道现场采集的声波和负压波数据作为数据源［8］,从中选取部分数据作为训练样本并分别提取两类数据源的特征参数,将其进行归一化处理后作为神经网络的输入矢量。网络输出以[10]代表无泄漏,[01]代表大泄漏,[1 1]代表小泄漏。通过实际效果确定用于管道泄漏检测的RBF网络拓扑结构为三层结构, 各层节点数分别为6、15、2。各层传递函数均为s型函数logsin,输出层为线性函数Purelin,训练目标精度为0. 001。
2. 2数据处理流程
数据处理的具体流程如图2所示。
2. 3实验结果分析
对所搭建的网络进行学习和训练,从实际采集的数据中选取了48组数据作为训练数据,其中12组为无泄漏时的数据,36组为有泄漏时数据。 为验证训练结果再选取12组作为测试样本对网络的实际性能进行测试。表2为部分训练和测试结果,其中1 ~ 9号为训练样本,10 ~ 12号为测试样本。
图 2 数据处理的流程
注: Aavr、Aavr1———对应的应力、压力波的平均幅值; S、S1———对应的应力、压力波的变化因子; W、W1———对应的应力、压力波的能量值。
从表2可以看出,该算法能对管道的不同泄漏情况进行有效判断,判断误差控制在了很小的范围内。
为将改进前、后网络的预测能力进行比较, 笔者采用同一组训练样本和测试样本将改进前、后的网络预测性能进行了对比,结果见图3和表3。
由表3和图3可知,DE优化后的网络在训练步数上和网络预测误差、精度上都有明显提高,证明了经过优化后的网络在天然气管道泄漏检测中的有效性。
3结束语
笔者对天然气管道的泄漏原因及其检测泄漏的方式进行了简要概述,接着针对普通神经网络收敛速度慢、泄漏辨识误差偏大的缺点提出利用DE算法对神经网络参数进行优化的改进神经网络算法。通过对基于DE优化的神经网络泄漏检测的可行性分析和仿真,证明了改进算法的可行性。
网络文学的商业进化 篇2
作为一个计算机系的大学生，我属于中国快速进入到互联网的第一批人。由于从小喜欢看书，所以上网大多数时候都在看小说。那个时候网上已经出现了把线下内容搬到线上的论坛，也出现了一部分在论坛上写小说的写手。但每次更新的内容不到一个小时就能看完。
后来有人把论坛转化为文学网站，让大家把内容聚集在上面，比如“幻剑书盟”。但是这些网站，使用起来都不是很方便。后来，我碰到一些喜欢看小说的朋友，一拍即合下，我们决定做一个文学网站，也就是起点中文网。
强调作者与读者互动
作为一个后来者，起点怎么战胜“幻剑书盟”这类老网站？在作家和读者中，文学网站真正取决于谁？
当时行业内普遍的倾向是作者和内容非常重要，所以对作者的倾向性非常重。但由于我的团队有作家、有技术、有读者，我意识到除了作家和内容创造者以外，读者的感受也非常重要。因此，网站不仅要给作家发布作品，更重要的是它应该留给读者发表意见的机会。
所以起点中文网从一开始，作家和读者的互动就是最好的，评论区也是最好的。在这种情况下，读者的热情和尊重推动了作家最终停留在起点中文网而不是其他平台。
虽然没有其他文学网站大，但在很多作家看来，在起点可以感受到其他平台所没有的读者热情。这种热情和尊重，对于当时不是非常知名、非常顶尖的作家而言，是非常重要的。小的、普通的内容创造者们非常希望获得读者的尊重。
收费方式谨慎优化
网站开始运营后，我开始思考起点的盈利模式应该是什么。当时网站可能赚钱的方式只有三个：广告、版权代理和收费。
业务没有起来，如果仅靠广告，网站无法长期成长。
版权的收益取决于上下游，网站在中间的价值可有可无，可替代性非常强，这个收入也无法成为稳定收入。
收费的环境也不算好。当时的互联网除了游戏收费以外，其他行业基本上都是免费。但是网络文学和传统文学有着很大的区别：趣味性和连续性。它是一种轻松有趣的文学，每天更新，读者看作品时会非常着迷，所以我决定把盈利模式建立在网络小说的连载基础上。
既然没办法单纯靠内容赚钱，那就靠新鲜度赚钱。确定将文字收费作为盈利模式后，具体操作就很好解决了。
按时间拆分售卖。在当时免费的情况下，网上的支付能力很弱，怎样的价格用户才会接受呢？当时台湾的电子书是2元钱一本，一个月或半个月出一本，但3天就有盗版了。起点把内容拆分成30份，分30天来卖，让内容在每天都创造价值。
按字数拆分售卖。1～2元钱买半个月或一个月的内容，相对而言比较贵。起点以一条短信为标准，一条短信0.1元，每天阅读一个章节也是0.1元。一个章节有5 000字，也就是0.02元/千字。
先假定用户可以接受的最高价格、享受服务的最低限——0.1元读5 000字，再用极限的价格和极限的产品服务结合形成的定价策略，就是完全从用户角度倒推而来的定价策略。
一月后免费阅读。由于担心用户对付费反感，因此起点只卖新鲜度，30天后可以随便看。这样的商业策略很大程度减弱了起点商业化道路上用户对付费的不适。
收费这件事很冒风险，因为就算你有合理的商业模式，也可能引起用户的反感。在那个年代，对整个内容正式收费是非常另类的，行业内的其他网站都不看好起点，认为起点必死无疑。但是如果不收费，就没有一个好的盈利模式，这是在等死。既然如此，还不如去尝试“找死”。
刺激新内容新作者
后面的过程很漫长。盈利模式效应非常强大，我们左手收到钱，右手分给作家。作家很开心，他们开始更积极地写作。
由此，作家的留存率大大提升。作家留存率越高，平台上作品的留存率就越高。内容数量快速增加，作家和作品的数量快速增加，创造出好作品的概率越来越高，随之带来的另外一个效应就是读者大量的阅读。以前的内容很少，现在内容多了，作家越多读者越多，催生了行业的快速发展。
不断推出新内容，不断支持新内容。只有把更多更新的内容推向市场，才会吸引更多更广泛的用户，最后变成综合性的平台。
传统媒体有一个决定其姿势与腔调的总编辑，内容企业同样也需要。内容这个产业，很多东西是靠机器或者互联网技术解决的，比如通过数据榜单来分析得到数据。但在这个过程中，内容之间的细微差别、内容的潜力，都没有被挖掘出来。
编辑做的就是发掘潜在内容。如果一直把排行榜上的东西奉为金科玉律，新人怎么出头？如果新人无法出头，网站永远就是这些东西，新用户从哪里来？
有一段时间，游戏小说在起点非常流行，新书排行榜前十名有9本都是游戏小说。按照正常的网站操作方式就是推，猛烈推。但起点反其道而行之，坚持用员工推荐榜，向用户推荐好作品。员工推荐榜能够保证榜单上至少50%是其他题材，因为我们需要保证内容的均衡性、新内容出现的可能性，而不是什么最热推什么。在这个过程中，用户可以看到其他的题材出现，可以发现新的作品，然后去追随它，产生新的热门。
一个网站的内容调性非常重要，如果过度依赖技术，对内容的多元化非常不利。
在移动端压制老对手
2010年，中国的移动互联网出现了。
对于起点来说，这一年有两件大事：一是中国移动启动阅读基地；二是包括盛大在内，各大公司都开始关注到移动互联网。App大潮在2011-2012年开始，各个巨头疯狂进入移动互联网行业。移动互联网发展之后，我们应该怎么做？
nlc202309090435
作家和读者之间，固然是作家在创作内容吸引读者，但是读者在哪里，作家也才会去那里。颠覆这个行业的时代到来了，如果不能自我颠覆，就注定会被别人颠覆。于是我离开了盛大文学（2004年10月，盛大网络全资收购起点中文网），我需要寻找更好的机会在移动互联网上重新出发，把网络文学的商业模式再做一次改变。
加入腾讯后，我做了腾讯文学。2012-2013年，起点和盛大文学的地位稳如泰山。怎么打赢它？在这之前，BAT全都试过，全都失败了。它们证明了内容产业不是靠它们的力量就可以进去的。当盛大占有的市场份额如此之重的时候，怎么做？从无线切进去。
因此我做了QQ阅读，QQ阅读上都是新用户，他们没有看过网络文学，或者刚开始接触网络文学。移动互联网的文学内容是空白的，所以他们快速集中到QQ阅读平台上。在这样的情况下，QQ阅读用户数快速增长，收入增长非常快。
只用了一年时间，QQ阅读做到了起点八、九年才做到的收入规模。这和移动端用户付费能力相对更强有关。但也充分证明了一点，从1到10有着巨大的空白。如果你抓住这个空档，就可以把这个市场重新再颠覆。
在2012年之前，内容产业用内容壁垒拦住了很多人，这是内容产业非常重要的地方，也是非常具有决胜意义的地方。它让我们拥有了近10年的优势，但它不是无懈可击的，在新产品、新用户、新内容面前，一切都是新的。
将IP工业化运作
2014-2015年，是IP时代的到来。此时，腾讯文学已经与盛大文学合并成了阅文集团。
此前，我们把IP当作一个副产品。网络上有很多IP，实际上是为了写小说而存在的，写完小说是为了用户去看而存在的。后来越来越多的人来看，IP越来越知名，这个时候就有人想到改编。
先是宫廷戏，然后是历史剧，再后来有了更多突破，比如《鬼吹灯》《盗墓笔记》等。当时我们觉得玄幻小说拍不了，所以把它看成一个副产品来看待，很多版权都用很低的价格出售了。这对我们而言是非常大的损失，因为太多的版权都流到了外面。
现在中国IP商业模式的好处是，大家都认识到了IP的商业价值所在，都认为IP很重要，但坏处是什么呢？所有人都把IP视为一个简单的概念，这种行为在某种程度上来说，是对IP的巨大浪费。
我比较欣赏好莱坞式的工业化的IP运作方式。工业追求的是长期的稳定和可靠性。好莱坞一个IP的生成非常困难，但是一个好的IP，后续可以带来巨大的价值。比如创造一个超人、蜘蛛侠之类的IP之后，它可以在20年，甚至50年后，带来长期的源源不断的收益。所以，好莱坞每年非IP类的电影能成功的数量仅限于2～3部，大部分都是有IP的电影。这才是工业化方式运作。
我希望可以专门针对一个IP，为它未来10年、20年做准备。在这上面投入巨大的精力，为它去做宣传、包装、形象设计，然后为它开发一系列的产品，这些产品要和这个IP相关。同时再回过头来，反哺这个IP，让它快速形成价值，通过资本方式助推整体IP成长。所有下游产品要为这个IP服务，而不是拿着IP为产品服务。这样一个循环式的自我推动，才是最合理的商业模式。更重要的是，这样一个长期的产品开发周期，非常稳定、可靠、低风险，同时也可以推向国际市场，而不仅仅是国内。而这也是阅文所推动的主要商业模式。
改进的进化神经网络 篇3
关键词：微分进化,神经网络,电力变压器,自适应,混沌搜索
0 引言
电力变压器是电力系统重要的设备,其潜伏性故障对电力系统的安全可靠运行影响很大。油中溶解气体分析(Dissolved Gas Analysis,DGA)技术是目前对油浸变压器进行故障诊断最方便、有效的手段之一,它能够较准确、可靠地发现逐步发展的潜伏性故障,防止由此引发的重大事故[1,2]。研究表明,H2、CH4、C2 H6、C2 H4和C2 H2五种变压器油的特征气体与故障类型有着密切关系,通过分析变压器绝缘油中这五种特征气体体积分数或比值关系,就能找出电力变压器内部存在的潜伏性故障。
近年来变压器故障诊断领域中出现了不少智能诊断方法,如人工神经网络[3]、支持向量机[4]、专家系统[5]等,它们在变压器故障诊断过程中都有各自的优缺点。人工神经网络存在过拟合、收敛速度慢、易发散、权值和阈值易陷入局部极值等实际问题,这些实际问题严重影响了它的实用性。1995年Rainer Storn和Kenneth Price提出的微分进化算法(Differential Evolution,DE)是一种实数编码的全局优化算法,它在许多优化问题中都表现出优于自适应模拟退火算法、PSO算法、GA算法的性能。DE算法在滤波器设计、神经网络参数训练、电网规划、机器人路径规划等工程领域取得了良好的应用效果[6,7,8,9]。
本文将改进微分进化优化神经网络算法进行电力变压器故障诊断,其中应用IDE对BP神经网络的权值和阈值进行优化。
1 BP算法
BP网络物理结构由输入层、中间层和输出层组成。BP网络学习过程分为两种:正向传播和反向传播。当正向传播时,信息从输入层经隐单元层处理后传向输出层。如果在输出层得不到希望的输出,则转入反向传播,逐一修改各层神经元的权值和阈值[10,11,12]。此过程不断迭代,直到误差达到预期要求。
设输入层有M个节点,对应的输入向量X={X 1,X2,…,XM};隐含层有S个节点,对应的隐含层输出向量Z={Z 1,Z2,…,ZS},输入层至隐含层的权值为ωij,隐含层各单元的输出阈值为θj,则:
式中:i=1,2,…,M;j=1,2,…,S。
设输出层有N个节点,对应的输出向量Y={Y 1,Y 2,…,YN},隐含层至输出层的权值vjt,输出层各单元的输出阈值γt,则:
式中:t=1,2,…,N,f(*)为Sigmoid激活函数,即
2 微分进化算法及其改进
2.1 基本DE算法
2.1.1 初始化
DE算法是一种实数编码的基于种群进化的优化算法,是一种具有强劲的全局搜索能力的算法。它与PSO方法几乎产生于同一时间,既与PSO方法有相似之处,也具备遗传类算法的一些特征,所以它更像是PSO算法与遗传算法的结合。
初始种群的生成是从给定的边界约束内的值中随机选择,覆盖整个参数空间。而种群数NP一般取较大规模的维数。设第i个个体Xi=(xi,1,xi,2,…,xi,n),n为问题解空间的维数,初始种群s={X 1,X2,…,XNp},Xi∈Rn为个体的集合。一般个体向量Xi的各个分量按式(3)产生,即:
式中:xi,j、xi,jmax、xi,jmin分别为个体向量Xi的第j个分量以及第j个分量的上限和下限。
2.1.2 变异
DE与其他优化算法的主要区别就在变异方式。DE变异时,对于第k代的种群中随机选取3个与当前个体不同而且互不相同的个体变异后产生的中间个体记为iv,即:
式中:r1,r2,r3∈{1,2,…,Np}且r1≠r2≠r3≠i,所以DE种群数量必须大于或等于4才能满足要求。系数β≤1为控制微分量的参数,这种利用随机偏差扰动产生新个体的方式可以获得一个具有非常好收敛性质的自适应效果。
2.1.3 交叉
交叉的目的是为了增加干扰参数向量的多样性。交叉的方法是将得到的中间个体vi,j与当前个体xik,j进行杂交,然后,得到当前个体的候选个体zi,j,即:
式中:i=1,2,…,Np;j=1,2,…,n;qj是从(1,n)中随机选取的一个整数,保证zi,j至少从vi,j中取得一个分量;randb(j)是一个针对第j维分量随机选取的控制参数,交叉因子CR∈(0,1)为算法参数,它控制了选择变异个体分量值代替当前点分量值的概率。
2.1.4 选择
DE的选择模式是对交叉后的候选个体zi,j进行适应度评估,根据评价函数值的情况来选择是否取新的个体,即:
DE算法有三个控制参数:β,CR和NP。参数β和CR影响了搜索过程的鲁棒性和算法的收敛速度,NP一般取较大规模的维数。
2.2 DE算法的改进
2.2.1 控制参数的动态调整
在标准DE算法中,参数β和CR对种群搜索策略影响很大。当β较小时,可能导致算法过早地收敛;然而,当β较大时,可能导致算法错过局部最优。同样,对于交叉因子而言,CR较小使得种群在交叉操作后产生的新个体较少,影响算法全局搜索能力;而CR较大时,使得种群不能较好地保持稳定,从而降低了算法的稳定性。基于上述思想,本文对控制参数β和CR采用了自适应调整策略,即:
式中:βmax、βmin分别是控制参数β的最大值和最小值;CR max、CR min分别是交叉因数CR的最大值和最小值;λmax、λ分别是最大迭代次数和当前的迭代次数。
2.2.2 混沌搜索策略
当DE种群搜索到一定程度后,会产生部分重叠的个体,而过多的重叠个体会影响种群的搜索能力,使算法整体的寻优能力大大地降低。如何处理这些重叠的个体,使其在当前重叠点产生迁移,也是提高算法搜索能力的一个方面。由于混沌运动具有普遍性、随机性、规律性等特点,使混沌处理方法被广泛用于此类优化问题。本文根据种群中个体的分布情况,对算法中的重叠的个体将混沌状态映射到优化变量中,并把混沌运动的遍历范围同优化变量的取值范围联系起来,然后利用混沌变量进行搜索来提高算法的整体搜索能力。
Logistic映射是一个应用较为广泛的数字混沌序列,即:
式中,μ为分岔系数,其数值直接影响映射效果。取μ=4且x∈(0,1),通过迭代可生成一个确定的混沌变量序列x(0),x(1),x(2),…。图1为初始值分别为x(0)=0.01和x(0)=0.02的混沌运动轨迹。
3 IDE-BP算法的实现
从式(1)、(2)中可知,BP神经网络的输出结果受权值和阈值的影响比较大。然而,实际应用中很难预先确定合适的权值和阈值。而改进微分进化算法具有强劲的全局搜索能力。因此,本文用改进微分进化算法来优化BP神经网络的权值和阈值,使如下的均方误差(适应度函数)达到最小:
式中:yi,j为网络的实际输出值;yiT,j为网络的理想输出值。
图2为IDE优化BP神经网络的过程,其具体步骤如下:
(1)在约束边界条件下初始产生种群,即初始权值和阈值;设置种群规模NP,参数β和CR的边界值和最大迭代次数λmax。
(2)按式(7)、式(8)计算β和CR的当前值,并对种群中的每个个体按式(4)和式(5)进行变异和交叉操作,计算个体的适应度并按式(6)进行选择操作来更新种群个体。
(3)判断当前种群个体的重叠情况,对即将重叠的个体在以后的进化过程中按式(9)进行混沌映射,采用混沌搜索,并记录混沌搜索的最优点。
(4)如果满足迭代终止条件,则输出最优的权值和阈值;否则跳至步骤(2)。
4 电力变压器故障诊断
4.1 参数设定及性能分析
电力变压器油中溶解气体分析数据在一定程度上反映故障类型,所以本文采用电力变压器油中气体H2、CH4、C2 H6、C2 H4和C2 H2体积分数百分比来判定电力变压器发生的故障类型,即神经网络输入向量为每种气体占五种气体总和的百分比。神经网络的输出为五种故障类型,即无故障1T、中低温过热2T(温度t<700℃)、高温过热3T(t>700℃)、低能量放电4T和高能量放电5T。其中低能量放电一般指局部和比较微弱的火花放电,高能量放电一般指电弧和比较强烈的火花放电[13]。本文收集了已明确的实验故障结果,从中选取237组能反映故障又不冗余的实验记录,其中113组作为训练样本,另外124组作为验证样本。实验中,改进的IDE参数为:种群数NP=100;比例因数β和交叉因数CR随迭代次数在区间(0.4,1.2)和(0.4,0.9)之间变化;最大迭代次数λmax=200;经过反复调试后确定BP神经网络的隐含层的节点个数为12。
本文用GA-BP、PSO-BP、DE-BP和IDE-BP分别对这113组训练样本进行训练测试(如图3所示)。当GA-BP、PSO-BP、DE-BP和IDE-BP在具有相同的网络输入和期望输出时,却在迭代次数以及均方误差方面有显著的差异。GA-BP和PSO-BP迭代到某一次数后均方误差都不会发生变化;而DE-BP和IDE-BP的均方误差在整个迭代过程中都会持续地减小,且IDE-BP的均方误差减小得更快。由此可见,不论在性能上还是在训练效果上,IDE-BP优于GA-BP、PSO-BP和DE-BP,显示出更优的故障分类能力。
4.2 故障诊断及实例分析
本文采用124组故障样本来验证网络,用BPNN、GA-BP、PSO-BP、DE-BP和IDE-BP这五种算法进行故障诊断并比较诊断结果(见表1)。试验结果表明,IDE-BP的诊断精度高于其他四种算法。
5 结论
改进的进化神经网络 篇4
随着我国经济的快速发展,各种工农业污染物的不断增多,以及环境的破坏造成沙尘暴等天气因素,使电力线路和设备不断地发生严重的大面积污闪[1,2],所造成的危害也越来越大。据统计,随着输电线路污染的加重,绝缘污闪事故仅次于雷击,占电网事故总数的第2位,而损失却是雷击事故的10倍[3]。目前国内常用的防污闪措施主要有定期清扫,加大爬电距离,使用防污涂料和防污型绝缘子等。尽管这些措施在实际运行中起到了一定的作用,但减少污闪事故的效果仍然不理想[3]。因此建立切实可行的绝缘子污闪电压预测机制并针对性地采取防污闪措施,必会大大增强电网安全运行的可靠性。
目前,国内研究绝缘子污闪预测常用的方法有:利用模糊逻辑方法对绝缘子在线检测结果进行综合评定[4];用BP模型建立神经网络预测[5];基于支持向量机模型预测[6]。本文将基于实验数据和数学公式计算值用广义回归网络-改进差分进化算法(General Regression Neural Network-Modified Differential Evolution,GRNN-MDE)为绝缘子临界污闪电压[7]建立一种新的预测模型。本模型以绝缘子的四个结构特性:盘径(Dm)、高度(H)、爬电距离(L)、形状因素(f)及等值附盐密度(ESDD)为输入参数来预测临界污闪电压值(cV)。仿真结果表明与GRNN-DE及多元线性回归(MLR)相比,GRNN-MDE具有更为优良的预报能力,稳定性也更好,将它应用于绝缘子污闪电压的预测,效果更好。
1 广义回归网络及改进差分进化算法对平滑因子的优化
Specht提出的广义回归网络[8]是一种新型的神经网络,其不需预先确定方程的形式,而是以概率密度函数(Probability Density Function,PDF)代替固有的方程形式,以样本数据为后验条件,执行Parzen非参数估计[9],从训练样本里求出自变量和因变量之间的概率密度函数之后,直接计算出因变量对自变量的回归值。GRNN不需设定模型的形式,但其隐回归单元的核函数的平滑因子σ网络有很大影响[10]。过小的平滑因子将导致过拟合现象;而过大的平滑因子又使预测值受全部训练样本的影响相同,因此需优化取值。用常规差分进化算法估算平滑因子,寻优缓慢且易陷入局部最优。为了避免这种情况的发生,本文采用改进差分进化算法来自动确定理想的平滑因子σ的值。
1.1 广义回归网络
设有随机向量x和随机变量y,定义其连续概率密度函数为f(x,y),若f(x,y)已知,则可得y在x上的回归式为:
若f(x,y)未知,则可应用Parzen非参数估计,由观测样本{x i,y i}ni=1按式(2)估算概率密度函数f(x,y):
式中,σ为高斯函数的宽度系数,在此称为平滑因子[8]。
将式(2)代入式(1),并且交换积分与加和的顺序,则有:
因为,对式(3)的两个积分进行计算后可得:
显然,式(4)的预测值y(x)为所有训练样本的因变量值iy的加权和,其权为,GRNN的网络结构如图1所示。
1.2 改进差分进化算法对GRNN平滑因子的优化
Storn和Price提出的常规差分进化算法(DE)[11]实施的是随机、并行、直接的全局搜索,简单易用,稳健性好,在多个领域取得了成功的应用,但在解决比较复杂的优化问题时,面临着计算时间长、寻优缓慢和“早熟”等问题[12]。为此本文对其进行改进,提出了改进的差分进化算法(MDE)。MDE引入Powell寻优法以提高算法搜优速度,同时引入混沌优化法以提高种群多样性,降低算法陷入局部最优的概率。
1.2.1 Powell寻优法
Powell寻优法是一种不用对目标函数求导的具有速度快、极高的局部搜索效率等优点的有效的直接搜索法。为了提高DE的收敛速度,引入Powell寻优法,计算步骤如下[13]:
1)设定初始点σ(0),计算精度ζ>0及m个初始的线性无关的搜索方向ε1,ε2,,εm。
令di=εi+1,i=0,1,,m-1,j=0。
2)进行一维搜索,确定λj,使得:
令σ(j+1)=σ(j)+λjs j,若j
3)如果,终止计算,取σ*=σ(m);否则求整数i(0≤i≤m-1),使:
4)令f1=f(σ(0)),f2=f(σ(m)),f3=f(2σ(m)-σ(0)),如果2Δ
转向5)。
5)求mλ,使得f(σ(m)+λm sm)=min f(σ(m)+λm sm),令σ(0)=σ(m)+λm sm),j=0返回2)。
1.2.2 混沌优化法
Powell搜优法尽管可以提高算法收敛速度,但却可以导致“早熟”,实践表明:混沌优化能跳出局部最优[14],因此将混沌优化法引入算法中,以防陷入局部最优。
研究表明,能够产生混沌的系统很多,常用的是Logistic方程:
式中:kq∈(0,1)表示第k个混沌序列变量;η为控制参数,η=4时,式(5)处于完全混沌状态。
将混沌序列映射到区间[-1,1],即
其中:j=1,2,,n;i=1,2,,Nc,Nc为种群规模。
将产生的混沌序列用于优化操作,保留最优个体σbest(g),并在该个体基础上产生新种群,即
其中:j=1,2,,n;i=1,2,,Nc,Nc为种群规模。
为了保证只在种群多样性较低时,才进行混沌优化操作,特设计衡量种群多样性的参数μ(g):
其中:μ(g)∈[0,1],σj(g)=1Nci∑σji(g)。只有当μ(g)<μmin时,才调用上述操作。
1.2.3 改进差分算法对平滑因子的优化
文献[15]提出,对于不同的样本,平滑因子分别取不同的值,可以达到较好的预测性能。考虑到自变量各维对模型的影响有较大的不同,本文对自变量各维分别采用不同的平滑因子。设有观测样本,则MDE对GRNN的平滑因子的优化,就是求解(yi为实际值,为预测值)为最小时的σ值。
综合上述对DE的改进,MDE的执行过程如下:
首先确定σ的定义域为Γ,以σ为个体,以E(σ)为适应度函数,接着执行以下各步。
1)初始化:确定种群规模Nc,杂交率Cr∈[0,1],加权因子F∈[0,2]和最大进化代数P;随机选取初始种群
σi(g)表示第g代的第i个个体。
置g=0,则σ(0)=(σ1(0),σ2(0),…,σi(0))为初始种群。
2)计算出第g代每一个体的适应值f与该代的最优个体σbest(g)。
3)按1.2.1中所述对最优个体进行加速操作。
4)种群演化
(1)变异操作
从种群中随机选取两个个体σk(g),σl(g)按式(9)生成临时变异个体σi(g+1),其中1≤i,k,l≤N,且i,k,l互异,σbest(g)为当代中最好的个体向量,F为控制差分项σk(g)-σl(g)对σbest(g)的变异程度。
(2)杂交操作
杂交操作可增加种群的多样性。
按式(10)将σi(g+1)和本代个体杂交,生成下一代个体。
其中:σij(g)为第g代第i个个体的第j个分量;Cr为杂交率;随机数randnum∈[0,1]。
(3)选择操作
为了确定σi(g)能否成为下一代的个体,将σi(g+1)和σi(g)按式(11)相竞争。
其中,q(σi(g))为第g代第i个个体的适应度。
(4)判断种群多样性,按式(8)计算μ(g)值,若μ(g)<μmin,则按1.2.2所述对种群进行混沌优化操作。
5)终止判断
设由第四步所产生的新种群为:
令σ(g+1)中最优个体为σbest(g+1)。若进化代数超过了最大进化代数P或第g代和第g+1代的最优适应值之差不大于eps(eps由用户设定),则终止并输出σbest(g+1)作为GRNN的平滑因子值;否则置g=g+1,返至第3)步。
2 基于广义回归网络-改进差分进化算法的绝缘子闪络电压预测
2.1 实验方法和数据样本的获取
用于GRNN-MDE模型训练及测试所用数据来自两个方面:实验数据[16,17]和数学公式计算值[18]。
绝缘子人工污闪试验在标准雾室中进行,试验回路接线图如图2所示。
人工污秽试验室满足GB/T4585-2004[19]所规定的人工污秽试验室对设备的要求,试验雾特性也满足文献[19]相应条款的规定,满足污秽试验的要求。
人工污秽的涂刷[19]。用清洗剂清洗绝缘子表面,除去所有污物和油脂痕迹,然后用自来水彻底冲洗干净。以后每次染污前,仅用自来水彻底清洗,除去污秽物的所有痕迹,清洗后的绝缘子晾干后涂污进行试验。可溶性物质采用商业纯Na Cl,不溶性物质采用硅藻土,Na Cl和硅藻土按绝缘子表面积定量称取,用适量的去离子水搅拌均匀后,按固体层法人工将污秽均匀涂刷到预处理好的绝缘子表面,置于干燥通风地方约24 h待用。以等值附盐密度作为污秽度指标,对干燥后的绝缘子进行抽样检查,看其是否称量准确和人工涂覆质量是否满足要求。将晾干了的绝缘子放入人工雾室约35 min,待其电导率达到最大值后,在5 s之内,将测试电压加到绝缘子上并维持到污闪发生;若无污闪发生,测试电压也继续保持15 min。将绝缘子取出雾室晾干,然后再一次放入雾室,待其电导率再到最大值后,再重复刚才的操作,共重复两次;但若前两次均有污闪发生,则不用进行第三次操作。两次实验所得平均值便是受绝缘子污秽度和几何特性影响的最大耐受电压值。
Obenaus提出的分析染污绝缘表面闪络的等效电路是由放电电弧和剩余污层电阻串联而成的。如图3所示。
图中:U为外加电压;Varc为电弧电压;pR为剩余污层电阻。
式(12)为局部电弧发展为全面闪络的临界污闪电压的计算公式:
式中:cV为临界污闪电压,单位:kV;mD为最大盘径,单位:cm;L为爬电距离,单位:cm;f为形状因素,按式(13)计算[20]。
A,n为电弧常数,在本文分别为A=124.8,n=0.409[21];δs为污层表面电导率,单位:Ω-1,按式(14)计算[18]。
式中,ESDD为等值附盐密度,单位:mg/cm2。
H为盘形绝缘子的剩余污层电阻系数,可按式(15)运算:
其中,K为弧足半径(单位:cm),按式(16)计算。
上述公式是在特定绝缘子类型和污秽下由实验结果推导出来的,因此,只要实验条件与其相同便可得到满意实验精度。
2.2 数据样本的归一化
本模型的输入参数为几种盘形绝缘子的结构参数(Dm、H,L,f)和ESDD,输出参数为临界污闪电压。数据样本来源于人工污秽试验和式(12)计算结果。为了避免训练过程中出现饱和及能进一步反应任意输入参数变化引起输出量变化的大小,所以把各输入量和输出量按式(17)归一化。
式中,xmax,xmin分别为各个参数mD、H、L、f、ESDD,cV的最大值和最小值。
将表1和表2的数据代入式(12)和式(14)可计算出临界污闪电压值。
2.3 闪络电压预测
来自公式计算值和实验值的数据分别为64个、20个,总样本数为84个。分三种情况进行研究:
Case1:84个样本全用上。
注:*为计算值。
将84个样本随机分为12组,每组7个,依次取出1组用作预报,称为预报样本,其余的11组共77个样本用作训练,称为训练样本,总共执行12次。对GRNN的训练实质上是应用MDE优选平滑因子,将其记作GRNN-MDE。MDE的参数设置为:NC=50,Rc=0.6,eps=10-8,加权因子F=0.16和最大进化代数500,μmin=0.01。为作比较,构建GRNN时,还采用常规的DE来优选平滑因子,记作GRNN-DE。除了没有μmin,DE的其他参数与MDE的相同。平滑因子各分量的初始值在(0,1)间随机选取。
表3所示为GRNN-MDE和GRNN-DE的12次交叉验证及泛化性能检测的结果。建模所用训练样本,其实际输出与实际值之间的相对误差,称为训练相对误差;用作预报的样本,其实际输出与实际值之间的相对误差,称作预测相对误差。表中列出的是相对误差绝对值的平均值,表中还列出了12次交叉验证的总均值Mean,即表中每列的平均值,Mean=Nn1N∑=1y n,其中N=12,yn为表中与序号相对应的值。
Case2:只用64个计算值。
将64个样本随机分为8组,每组8个,依次取出1组用作预报,称为预报样本,其余的7组共56个样本用作训练,称为训练样本,总共执行8次。其他的设置与Case1相同,操作过程也同Case1。
Case3:只用20个实验值。
将20个样本随机分为5组,每组4个,依次取出1组用作预报,称为预报样本,其余的4组共16个样本用作训练,称为训练样本,总共执行5次。其他的设置与Case1相同,操作过程也同Case1。
3 结果比较与分析
由表3～5的交叉验证结果,不难看出以下几点:
1)GRNN-MDE的训练相对误差及其总均值与GRNN-DE的相接近,总体上比GRNN-DE的略小;但GRNN-MDE的预测相对误差几乎均比GRNN-DE和MLR的要低,且其总均值比GRNN-DE及MLR的要小得多,而GRNN-MDE又比MLR的要小。表3～5中的GRNN-MDE的预测相对误差均值分别为:5.063 1%,5.718 7%和3.626 8%;而GRNN-DE的预测相对误差均值分别为:6.235 2%,7.030 4%和4.853 8%;MLR的预测相对误差均值分别为6.722 9%,7.567 4%和5.257 6%。
模型的好坏主要由预报性能决定的,由此可以看出,GRNN-MDE的稳定性、泛化性能和预测性能均比GRNN-DE和MLR要好。
2)比较表3和表4:表3中的GRNN-MDE的预测相对误差均值比表4中的要低。表3中的预测相对误差均值为5.063 1%;而表4中的为5.718 7%。这说明,既有实验值又有计算值样本所建立的模型精度要高于单纯采用数学公式计算值样本构建的模型。
3)比较表3和表5:可以看出两表中的训练相对误差也比较接近,表5中的稍小些;但表5中的GRNN-MDE的预测相对误差均值要比表3中的低很多,其值为3.626 8%,表明Case3的模型精度远高于Case1。
4)比较表3、表4和表5:表5中的误差值在几种情况中是最小的,其GRNN-MDE的预测相对误差均值为3.626 8%;而表4的最大,其均值为5.718 7%;表3的值居中,其均值为5.063 1%。这说明全由实验值样本构建的模型精度要高于由实验值和计算值两种数据构成的模型,更高于全由计算值构成的模型。
4 结论
采用概率计算的广义回归网络具有很强的非线性拟合能力,本文所提出的GRNN-MDE法,应用改进的差分进化算法来优化平滑因子,该方法将Powell寻优法和混沌优化法引入到传统的差分进化算法中,提高了全局寻优效率,又避免了算法陷入局部最优的困境。从仿真结果可以看出,本文所建的GRNN-MDE模型具有优良的预报能力,稳定性也很好,将它应用于绝缘子临界污闪电压的预测,效果良好。这也为污闪电压预测提供了一条新的思路。
另外,从表3～5可以看到,由实验值和数学公式计算值样本共同构建的GRNN-MDE模型精确度要高于全由计算值样本构建的模型;全由实验值样本构建的模型精度高于由实验值和计算值共同建立的模型更高于单纯由计算值样本构建的模型;但需要指出的是如果参与构建模型的样本过少,即使模型全部由实验值样本构建,其泛化性能也将大打折扣。
摘要：将基于实验数据和数学公式计算值用广义回归网络-改进差分进化算法为绝缘子污闪电压建立一种新的预测模型,以绝缘子的盘径、高度,爬电距离、形状因素四个结构参数及等值附盐密度为输入参数来预测污闪电压值。广义回归网络不需设定模型的形式,但其平滑因子参数需优化估值。为了克服传统差分进化算法优化参数时的弱点,改进差分算法引入Powell寻优法以提高算法搜优速度,同时引入混沌优化法以提高种群多样性,降低算法陷入局部最优的概率。仿真结果表明与GRNN-DE及多元线性回归相比,GRNN-MDE具有更为优良的预报能力,稳定性也更好,将它应用于绝缘子污闪电压的预测,效果更好。
改进的进化神经网络 篇5
1 计算机网络路由器的概述
众所周知, 在计算机网络中, 路由器占据着重要的位置, 是实现网络间相互联系的必须设备之一。路由器主要是指计算机网络中, 在相应的OSI或者RM的网络层上面进行相关工作。并在此基础上, 对不同网络之间的相关数据进行转发、分粗、存储, 同时对网络间传输数据时的路由器取向做出相应的决定。而网络路由不仅能够实现网络之间的连接, 还能够进行不同网络之间信息传递的设备。一般情况下, 路由器只能接收由其它路由传输过来的信息。同时, 它一般可以连接两个或两个以上的IP子网逻辑端口, 还需要有一个相应的物理端口。其主要包含了输入和输出端口、交换网络、路由处理器等, 不同部分发挥各自的作用, 使网络处于有序运行中。路由器会帮助每一个经过其中的相关数据帧找到一条最好的传输路径, 并在此基础上, 以该路径作为桥梁, 把相应数据信息传输到目的节点。如何选择一条最佳的路径, 这才是问题的关键。路由算法便是最重要的环节。路由算法是一种网络算法, 它主要是提升路由协议的功能, 以此降低路由消耗。路由算法需拥有能对故障进行处理的能力及迅速聚合的能力。在计算机网络的路径出现故障的时候, 路由算法不仅可以对网络信息进行更新, 还能够及时建立出新的相关数据传输途径。计算机网路中的路由器在整个网络运行中所发挥的作用是不可以轻视的。
2 量子进化算法概述
在计算机网路中, 路由的正确选择是保证它有序运行的关键, 而量子进化算法在路由选择中经常出现。所谓的量子进化算法主要是指进化算法和相应量子计算相结合的产物。具体的说, 它是在量子的太矢量表达的基础上的, 并用相应的量子比特编码来代表相应的染色体, 再用量子非门及量子旋转门来对相应的染色体进行更新。进而使相应的目标问题得到优化求解。在流程方面, 量子算法一般包括了以下步骤。首先, 需要对相应的种群进行初化。在此基础上, 对相关初始种群中的不同体进行测量, 得到一组相应的状态。在适应度方面, 对这组状态进行评估, 并把最佳个体状态和它的适应度值准确记录下来。最后, 在没有结束状态下, 进行之相关的其它操作。对于相应量子进化算法, 需要进行一系列复杂的过程。事物要用相应的符号来表示, 然后再进行计算, 比如, 染色体的长度可以用字母m表示。染色体也是相关对解多样性进行维持的最好呈现。通过这样的方式, 使它的表达更加简洁。同时, 对于它相应进化的方式需要采用量子旋转门进化。进而得出具体办法的描述, 可用下面的表达式表达。
在量子进化算法方面, 对于这种利用相应的量子旋转门来完成相应量子计划算法的办法, 它主要运用的是这种原理。利用搜索法把当下的解逼到最优解。结果可以以相应概率增加的形式来进行保留。相应地, 可以使用概率减少的办法删除没有用的结果, 使所得结果处于最佳状态。
3 量子进化算法的改进
在计算机网络中, 量子计算强大的计算能力已经成为火热的话题之一。在计算机网络路由选择中, 传统量子进化算法中存在的主要问题就是它们大都是对相应的表格进行查找, 寻找到适合的解法。这种方式, 使相应的旋转角之间的关联性不紧密。同时, 在问题搜索方面, 具有一定跳跃性, 不利于计算机网络的正常运行。为使相应的量子进化算法能更好地解决路由中的问题, 需要对它进行改进。一是, 对它的旋转角进行相应的调整和优化, 使最终数值更利于路由选择。改进后旋转角表达式如下:
根据这个改进后的相关表达式可以知道, 旋转角处于不同情况时, 会得出不一样的结果。换句话说, 旋转角的值不同, 所代表的含义也不同。如旋转角的值越小, 就表示最优个体和个体之间的距离越近, 搜索网络越小。这种状况下, 使用细搜索便可以找到最优解;当相关旋转角的值越大的时候, 就表明相应个体和最优个体之间的距离在不断拉大。所代表的搜索网络更大, 这种状况下, 就需要提高搜索速度, 才能使路由选择有利于计算机网络运行。二是, 对相应的函数进行优化调整。调整可采用组合优化办法, , 使函数处于最优状态, 为得出最优解提供相应条件。通过运用组合优化的方法可道, 个体基因之间没有很强的关联性。因此, 在计算网络路由的选择上, 可以对量子进化算法中的函数进行相应的调整, 并加以优化。它现在归一化条件对此满足的情况下, 来实现相应的实属对, 并把它们对应到一个量子位的概率幅上面。相应的量子位可以和二维空间进行对应, 分别用相关符号进行表示。在此基础上, 可以对相应的量子进化算法进行仿真测试, 看改进后的它是否比之前更具有优势。根据相应的仿真测试研究表明, 在计算机网络路由选择中的性能, 可以知道改进后的量子进化算法确实优于传统的量子进化算法, 根据相应的路由选择仿真表得出的结果, 见图1。
从图表中可得知, 在计算机网络路由选择方面, 改进后的量子进化算法不论是在收敛速度上, 还是在寻优能力上, 都比传统的量子进化算法好。相应的性能也优于传统量子进化算法。在仿真测试的基础上, 能够帮助改进后的量子进化算法在路由的最优选择中发挥应有的作用, 改进后的量子进化算法在相应路由选择中的应用更加完善。在这种状况下选择的路由能够对网络运行中出现的突发情况进行很好地应对, 及时发现和解决相应的问题。不仅能够提高相应工作人员的工作效率, 还能使计算机网络处于良好的运行状态。
4 结语
总之, 在计算机技术逐渐普及的状况下, 需要把路由的选择放在至关重要的位置。相应地, 量子进化算法的改进也是很重要的。通过对它进行改进, 使旋转角得到优化, 提高搜索速度。路由选择的优化不仅可以对计算机网路技术的发展起到巨大的推动作用, 也能成为我国经济发展的助推器之一。纵观计算机网络的发展之路, 相应改进后的量子进化算法在相应路由选择方面的应用具有很好的前景。最后, 笔者希望在丰富读者知识世界的同时, 也能引起他们的关注和新的思考。
参考文献
[1]雷华军, 秦开宇.基于改进量子进化算法的测试优化选择[J].仪器仪表学报, 2013 (4) :838-844.
[2]赵荣香.改进量子进化算法在计算机网络路由选择中的应用探究[J].科技传播, 2014 (24) :148-152.
[3]宋明红, 俞华锋, 陈海燕.改进量子进化算法在计算机网络路由选择中的应用研究[J].科技通报, 2014 (1) :170-173.
求解JSP的改进差分进化算法 篇6
随着市场竞争的日趋激烈,每个企业都在寻求先进制造系统,以提高企业的生产管理效率,从而提高企业的核心竞争优势。而有效的调度方法和优化技术是实现先进制造的基础和关键。为了更好地应用于生产实践,生产调度问题的研究已由经典作业车间调度问题JSP(Job-Shop Scheduling Problem)逐渐向多目标、实用化、动态化等方向发展。动态柔性作业车间调度DFJSP(Dynamic Flexible Job-Shop Scheduling Problem)是JSP的重要扩展,它体现了实际生产环境中存在并行机和多功能机的特征。
目前常用的求解JSP问题方法主要是智能算法或者多个智能算法的混合算法[1,2,3,4,5,6]。然而这些成果的共同的缺陷是,编码都存在一定的局限性,缺少通用性。比如,文献[5]中采用扩展工序的编码方式,每个染色体用N×max{nj}个代表工件号的自然数组成,各工件号均出现max{nj}次。对于工序数小于max{nj}的工件,多出的部分表示“虚工序”,解码时将其加工时间均设为0,虽然“虚工序”不影响问题本身,但显然“虚工序”增加了编码的无谓的长度。
针对上述问题,本文提出了一种改进的差分进化算法。该算法为了适应差分进化算法的实数编码特点,改进了文献[1]中提出的双层编码机制,新的编码具有很强的通用性,适用于完全柔性、部分柔性、静态、动态、单目标和多目标等不同情况下的作业车间调度问题;在次序号编码基础上,对应改进了变异算子,使得在进化过程中,不会产生无效解,进而提高算法的运行速度;还改进了缩放因子,提高种群的多样性;最后通过多个典型实例计算验证了算法的可行性和有效性。
1 作业车间调度问题描述
Job Shop问题可以描述为:设有N个工件在M台机器上加工,由于工件的加工工艺的要求,每个工件使用机器的顺序及其每道工序所花时间已给定,调度问题就是如何安排在每台机器上工件的加工顺序,使得某种指标最优。具体满足下面条件:(1)每一工件在机器上的加工顺序一定;(2)每一台机器每次只能加工一个工件;(3)每一工件在机器上的加工被称为一道工序,工序加工时间是固定的;(4)工件在机器上被加工时不允许被打断;(5)机器与工件可能开始时间都为0[7]。
Makespan为调度的最小生产周期,即所有工件的最大完成时间的最小值,调度问题要求确定机器上工件加工顺序,使Makespan时间达到最小。上述问题的数学描述如下:
其中,cik和pik分别为i工件在机器k上的完成时间和加工时间;M是一个足够大的正数;若机器h先于机器k加工工件i,则aihk=1,否则aihk=0;若工件i先于工件j在机器k上加工,则xijk=1,否则xijk=0。
2 求解JSP的改进差分进化算法
2.1 实数次序号编码
实际情况,一方面,JSP大多是动态的、柔性的和多目标的,因此编码要综合考虑这些情况;另一方面,因为DEA算法是一种基于实数编码的演化算法[8],而作业车间调度中的机器编号、工序编号以及工序加工次序都是整数,所以作业车间调度常用的编码方法不能直接应用到差分进化算法中。
为了同时解决上述两方面问题,本文改进了文献[1]中的编码方法。一方面,将第二层中的编码表示为每个工序加工机器的动态实数次序号,而不是加工机器,这样就可以将编码直接应用在DEA算法中,而且改进后的编码可以直接进行DEA交叉变异进化操作;另一方面将编码的长度设置为动态可变的,这样可以适应JSP的动态多变的特性。具体方案如下。
编码的长度为所有加工工件的所有工序数。对于一个有n个工件、m台机器的动态FJSP,每个工件的未加工工序数量分别为s1,s2,…,sn,则编码的长度为s1+s2+…+sn。以3工件3机器的P-FJSP为例,每个工件的未加工工序数量分别为2,1,3,则编码的长度为2+1+3=6。加工约束条件和加工时间如表1所示。其中Jik(1≤i≤3,1≤k≤3)表示工件i的第k个工序。
由表1汇总出每个工序可用的加工机器数量如表2所示。
本文提出的编码列数为工序数量之和,层数为2层。第一层表示每个工序的加工优先级,取值为实数。第二层表示每个工序加工机器的次序号。加工次序号不同于加工机器编号。每个工序的次序号的取值范围为介于[0,Sij)(Sij表示第i个工件的第j道工序可使用的加工机器数量)之间的小数。如表2的工序数量之和为6,因此编码为6列,表3给出了表1问题的一个个体的编码。
如果加工次序号取整后为0,则在表1中,从左往右,选择工序的第1个加工机器,如果加工次序号取整后为1,则在表1中,从左往右,选择工序的第2个加工机器,依次类推。
解码的主要工作是排定工序加工顺序,并选定加工机器。解码时,首先将第二层编码取整。然后对编码中的第一层实数从小到大排序,从而得到一个各工件加工的优先级序列。然后根据优先级序列和作业车间调度问题的约束条件,分别将工序分配到对应的机器上。得到一个调度解。
对表3第二层编码取整后结果如表4所示。
然后将表1中所有工序集中在一起看作AOV网络图,结合各工序的优先权随机数对AOV图进行拓扑排序,进行解码。其过程与文献[9]类似。在此不赘述。
2.2 与常用编码方法比较
本文提出的实数次序号编码主要有以下优点:
(1)编码能适应于完全柔性、部分柔性、静态和动态,通用性好,无论哪种情况发生,只要根据实时情况,根据工件的未加工工序数量更改个体编码的列数即可。
比如,当某个工件的一个工序完成后,又新增加了一个工件。此时,编码时,将已完成工序的工件工序数量减1,然后增加新的工件工序数,重新执行调度算法就能得到新的调度方案。操作简单。
再比如,当某台机器发生故障时,只需要将使用该机器的工序的加工机器中去掉该机器,然后执行调度算法就能得到新的调度方案,操作也很简单。
(2)编码的每一位都是有效的,没有冗余,因此,编码、解码的时间复杂度也低,算法运行快。
(3)编码不会产生无效解。无论初始种群还是,交叉变异的中间个体,都不会产生无效解。2.4节介绍了如何避免变异时产生无效解。
表5将文献[1]编码、本文的编码、常用的基于操作的编码和基于工件的编码进行了比较。
其中,operation-based representation表示基于操作的编码;jobbased representation表示基于工件的编码。order number表示本文提出的实数次序号编码。n表示工件个数;m表示每个工件号出现m次。
基于操作的编码方式将每个染色体用n×m个代表操作的基因组成,各工件号均出现m次,这种编码不灵活,不能适应动态变化的作业调度。
基于工件的编码方式将每个染色体用n个代表工件的基因组成,编码长度虽然比较短,但也是固定长度的编码,不灵活,不能适用动态多变的作业车间调度。
从表5可以看出,本文提出的次序号编码方法是一种可行、简单、灵活的编码方法。
2.3 变异算子的改进
差分进化的变异算子结果为实数,而且实数范围是不确定的,而本文编码第二层的每一位实数的范围为[0,Sij),超出这个范围的编码将是不合法的编码,如果不合法的冗余编码出现,将会降低算法执行速度,因此,就要把变异运算的结果,调整为[0,Sij)范围内,这样就能避免冗余的不合法编码出现,提高算法的效率。
本文采取将变异结果取绝对值后多次开方运算进行调整,多次开方一直到变异结果的值调整为[0,Sij)范围内为止。第3节的实验结果证明,这种方法是可行有效的。
2.4 F的改进
DEA是目前演化计算研究领域中的一个著名算法。算法中的缩放因子F决定着经过变异操作,产生的差分矢量的缩放比例,是影响算法性能优劣的重要因素之一[13]。缩放因子对算法的影响,主要是收敛速度和种群多样性。本文提出了一种自适应的缩放因子F,使缩放因子能够随着迭代次数的改变而改变,适应当前种群的变化情况,使得最优解可以保存。自适应的缩放因子F为:
其中,NP为种群规模,f(Xi)为个体Xi的适应度函数值,f(Xbest)为最优个体Xbest的适应度函数值。
显然,式(2)使得F的取值为动态的。迭代次数越小,种群个体差异越大,种群个体的平均适应度函数值越小,F值越大,种群多样性越多,提高了前期迭代时算法的全局收敛速度。随着迭代次数的增加,种群个体的差异性降低,种群个体的平均适应度函数值越接近Xbest的适应度函数值,F的值越小,提高了算法后期的局部搜索能力。
2.5 求解JSP的改进差分进化算法
设种群规模NP,最大迭代次数Gmax,种群当前的迭代次数为generation,每代的最好个体为BestIndividual。
改进的差分进化算法IDEA伪码如下:
算法IDEA算法
1)初始化种群,确定generation=0
2)计算初始种群个体的适应度值,初始化BestIndividual
3) while generation<Gmax do
4)采用DE/best/1/bin模式进行变异运算,F由式(2)得。
5)变异运算结果使用2.3节方法进行调整;
6)进行交叉操作,Pc根据具体实例设定,详见表6所示。
7)对种群进行选择操作;更新BestIndividual的值。
8) generation=generation+1
9) end while
10) print (BestIndividual)
3 实验
3.1 算法比较
对12个国际通用的标准实例进行了测试,参数设置如表6所示,与已知最优解的比较结果如图1所示
从表6可以看出,针对不同的问题需设置不同的种群规模值、种群最大迭代次数和交叉概率。如果问题的机器数m比较少时,种群规模一般设置为40～65之间,迭代次数设置的相对小些,杂交概率设置范围为0.05～0.1之间,但当m值比较大时,种群规模要设置的大一些。迭代次数也要设置的大一些,杂交概率设置的要小一些,范围为0.04～0.05之间。
横坐标数字1—10表示算法执行次序。纵坐标=(每次计算的最优值-C**)/C**×100;C**为问题的基准最优解。
从图1可以看出,与已知最优解相比,IDEA算法在求解典型实例时,对FT06、LA01、LA02、LA04、LA05、LA06、LA07、LA11这些实例,IDEA算法所求解的结果与基准最优解相同,对FT10、FT20、LA03、LA16这些实例的求解,虽然没有得到和基准最优解一样的解,但偏差比较小,说明IDEA算法是高效的算法,而且标准差也比较小,说明IDEA算法是很稳定的。
3.2 IDEA与其它权威文献中的算法比较
将混合算法随机运行20次的最优结果与JSP研究领域的权威文献[10,11,12]比较,如表7所示。其中,P表示基准测试问题;n和m分别表示工件和机器数目;C*为问题的基准最优解。表中的其它数据为各算法得到的最小完工时间。
从表7可以看出,IDEA算法、GA算法、SA算法和TS算法在求解FT06、LA01、LA06、LA11、LA26和LA31问题时,求解结果相同,并且和已知最优解也是相同的;在求解FT10、FT20、LA16、LA21和LA36问题时,虽然IDEA算法所求的最优解略差于GA算法、SA算法和TS算法,但差距很小。综上说明本文算法是可行有效的。
4 结语
针对作业车间调度问题,本文基于差分进化算法,提出了一种新的编码方式,该方式具有强的通用性,既适用于静态调度,也适用于动态调度,既适用于柔性调度,也适用于非柔性调度;还改进了差分进化算法的变异算子和缩放因子,分别提高了算法的运行效率和种群多样性。多个典型实例计算表明,本文提出的算法是可行有效的。下一步工作,一方面是将本文算法应用到其它NP难问题上,以验证其效果和增加算法应用的广泛性,另一方面是进一步改进算法,提高其效率。
参考文献
[1]夏蔚军,吴智铭.基于混合微粒群优化的多目标柔性Job-Shop调度[J].控制与决策,2005,20:137-141.
[2]Balas E,Vazacopoulos A.Guided local search with shifting bottleneck for job shop scheduling[J].Management Science,1998,44(2):262 -275.
[3]Sabuncuoglu Ihsan,Kizilisik Omer Batuhan.Reactive Scheduling in a Dynamic and Stochastic FMS Environment[J].International Journal of Production Research,2003,41(17):4211 -4231.
[4]夏柱昌,刘芳,公茂果,等.基于记忆库拉马克进化算法的作业车间调度[J].软件学报,2010,21(12):3083-3093.
[5]吴秀丽.柔性作业车间动态调度问题研究[J].系统仿真学报, 2008,20(14):3828-3832.
[6]Ho N B,Tay J C,Lai E M K.An effective architecture for learning and evolving flexible Job Shop schedules[J].European Journal of Operational Research,2007,179(2):316-333.
[7]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.
[8]Storn R,Price K.Differential evolution—A simple and efficient adaptive scheme for global optimization over continuous spaces[R].Berkeley: University of California,2002.
[9]张青.基于遗传算法的数控车间作业调度系统研究与应用[D].武汉:武汉理工大学,2006.
[10]Corce F D,Tadei R,Volta G.A genetic algorithm for the Job Shop problem[J].Computers and Operations Research,1995,22(1):15 -24.
[11]Laarhoveh P V,AartsE,Lenstra J K.Job Shop scheduling by simulated annealing[J].OperationsResearch,1992,40(1):113-125.
旅行商问题的改进差分进化方法 篇7
关键词：差分进化算法,旅行商问题,遗传算法
0 引言
旅行商问题TSP(TravelingSalesmanProblem)是人们广泛研究的一种典型组合优化问题,问题描述为从一个城市出发,求得一条最短路径,使之经过所有城市,且每个城市只经过一次。这是一个易于描述却难以处理的NP-HARD问题,其数学描述为:
式中,ci为第i个城市,i=1,2,3,…,n;T是一条旅程的总距离;d(ci,cj)为城市i与城市j之间的距离[1]。
若城市总数为N,则存在(N-1)!条闭合路径的排列方案。在短时间内很难精确地求出其最优解。因此研究相应的近似算法,寻找其最优或近似最优解很有意义。目前国内外关于TSP问题的研究很多,常见算法有遗传算法、模拟退火算法、蚁群算法和神经网络等。
差分进化算法(DifferentialEvolution,DE)是DainerStorn等人于1995年提出的一种启发式随机搜索的优化算法。在1996年举行的第一届国际IEEE进化优化竞赛上,DE通过现场验证被认为是目前最快的进化算法。由于其简单易用,设置参数少,全局寻优能力强等特点,被迅速应用于化工、电力、机器人、生物信息等各种领域。作为进化算法的一种,近年来,DE在离散空间优化问题中正日益受到关注,逐渐被运用于多目标车间调度方面。但用差分进化算法研究TSP路径优化问题的还比较少[2]。
1 标准差分进化算法
标准DE采用实数编码方式,其算法原理与遗传算法非常相似,都包括:交叉、变异、选择等几个流程,只是DE的流程顺序有所调整,将变异操作放在最前面。与其它进化算法不同的是,DE的变异过程是通过将种群中两个成员之间的加权差向量与第三个成员相加来产生新参数向量。然后再将变异向量的参数与其它目标参数一起进行一定规则的交叉操作。最后通过比较在进化过程中对每一代都评价最优向量,记录最小化过程,利用随机偏差扰动产生新个体,以获得较好的收敛性[3]。
DE的伪码形式如下:
以上为标准DE算法[4],算法模式为DE/rand/1/bin。其中,popsize为种群个数,xi,g为第g代的第i个个体。F为变异算子,控制偏差变量的放大,一般取[0,2],vi,g+1为变异后的个体。CR为交叉算子,ui,g+1为交叉后的个体,fitness为目标函数。如果交叉后个体的目标函数优于原始个体,则选择交叉后的个体进入下一代,否则保留原始个体。算法以实数形式进行操作,搜索空间必须是连续的。
2 解TSP问题的改进算法设计
2.1 编码方法及适应度函数
求解TSP问题的各种编码中,多数以遍历城市的次序排列进行编码,即采用整数编码。这种方法简单直观,易于掌握和理解。以6个城市为例,若某个体编码为123456,则表示从城市1出发,依次经过城市2,3,4,5,6,最后又回到城市1结束。随机生成的个体都可能是问题的一个解,适应度函数f一般取总路径长度T的倒数f=1/T。f越大,表明经历的总路径越短,对应的个体越接近最优解[5]。
2.2 用贪心算法产生初始种群
由于TSP问题是一个循环回路,所以可以选择任意一个城市作为起始城市。本文利用贪心算法产生较优的初始种群。具体操作为:随机选择一个城市c作为起始城市,根据距离矩阵选择离c最近的城市d作为第二个城市,再选择离d最近的城市作为下一个城市。以此类推,始终选择距离当前城市最近的城市作为下一个遍历城市,直到所有城市均被遍历后直接连接到起始城市即可[6]。
2.3 变异操作
DE算法中的变异与其它进化算法不同,它并不是通过替换等位基因来形成新个体,而是通过将当前种群中两个随机挑选的个体之间的差值与第三个个体相加后产生。通过变异因子F对个体偏差的放大作用,所得到的个体基因值为实数值,要想得到整数空间中的目标函数值,必须将实数转化为整数。针对TSP路径问题的特点,本文采用基于整数序规范的方法。具体转变方法为:将变异后实数个体的所有基因值按照从小到大的升序排列并编码,基因值最小的排在第一位,编码为1,依此类推。然后对应实数个体中每个基因的位置,将原基因值变为其对应编码号。如:
变异后个体为[3.4,0,0.5,6.3,2.1,5.0]
将其从小到大排列为[0,0.5,2.1,3.4,5.0,6.3]
对应编号:1,2,3,4,5,6
则原个体变为[4,1,2,6,3,5]。
使经过差分变异后的个体转化为整数,用于求解整数型路径规划问题[2]。
2.4 采用刘海交叉操作
针对传统遗传交叉算子如部分影射交叉、顺序交叉、循环交叉等交叉后的子代不能很好地保留父代的优秀基因或子代需要做些改动才能保留的不足,本文引用刘海交叉法[7]。采用最优个体保留策略,即最优个体以概率1进入下一代,其余个体均参与交叉操作。刘海交叉法的主要思想为:假设有n个城市1,2,3…n,染色体编码为推销员经过城市的序号,假设现有的待交叉双亲为:
遗传交叉的主要目的是子代尽可能地继承父代的优秀基因,把上述染色体看成一个环,即的下一个城市为,设计交叉步骤如下:
(1)定当前城市,从找到,并把加入子代。
(2)若r1c+1和r2k+1都不在子代中,比较dr1cr1c+1和dr2kr2k+1,若dr1cr1c+1≥dr2kr2k+1,记为当前城市r1c=r2k+1;否则就记为当前城市为r1c=r1c+1。
(3)从x2中找到并把r1c加入子代。
(4)若(1)r1c+1已经在子代中,而r2k+1不在子代中,记当前城市r1c=r2k+1,并加入到子代;(2)r2k+1已经在子代中,而r1c+1不在子代中,记当前城市r1c=r1c+1;(3)r1c+1与r1k+1都在子代中,比较drIcr1c+2和dr2kr2k+2。
(5)重复步骤(2),直到完整生成子代。
在第一步中分别选择r11,r21作为当前出发城市,运用此交叉方法可得到两个子代个体。
2.5 选择操作
为判断交叉操作后的个体能否成为下一代的成员,将其适应度与原个体适应度进行比较,把适应度好的作为下一代个体。
3 算法实现及实例分析
为了说明算法的有效性,在CPU为IntelPⅣ2.4GHz、内存512M的微机上用MATLAB 2009分别对TSP中的非对称和对称问题进行试验。
3.1 非对称距离矩阵
非对称问题采用文献[7]中的实例,为了体现可比性,参数设置均与文献相同。popsize=10,Pc=0.2,距离矩阵如表1所示。
最优路径为(1 5 4 3 7 8 6 2),仅运行到第8代就达到了最优值52。收敛代数与文献[7]相比明显更快效果更优。进化代数时序图如图1所示。
3.2 对称距离矩阵
为证明算法对非对称TSP问题和非对称的TSP问题同样有效,选择文献[6]中10个城市的实例进行实验仿真。距离矩阵如表2所示。
参数设置同样取文献中值,Popsize=20,Pc=0.8,进化代数为100代,程序运行50次。经测试,在最好情况下只遗传7代就收敛到了最优解:471,最优路径为(4 6 3 1 10 2 9 8 7 5)。进化代数超过20代则达到稳定状态。与文献结果相比,显然本文算法性能更优越。进化代数时序图如图2所示。
3.3 其它实例
为了进一步验证改进后算法的特性,从国际通行TSPLIB中选取一系列典型问题进行试验[8]。所选问题、试验所得结果及目前最优结果见表3和图3所示。
4 结束语
提出的改进差分进化算法利用贪心算法的快速计算产生初始种群,充分弥补了传统遗传算法随机产生初始种群的不足。并按照整数序规范将差分后的实数转化为整数形式,用刘海交叉法使子代能够很好继承父代优秀基因。从以上几个例子可以看出,改进后的算法针对规模较小的TSP问题收敛速度非常快,能够迅速得出精确的最优解。对规模稍大的TSP问题能够得到近似最优解,具有一定的有效性。
参考文献
[1]纪怀猛,蔡海滨.一种基于改进遗传算法的TSP问题求解方法[J].计算机与数字工程,2009,137(4):10-12.
[2]曹二保,赖明勇.基于改进差分进化算法的VRP_SDPTW研究[J].管理工程学报,2009,123(2):80-84.
[3]周燕平,顾幸生.差分进化算法研究进展[J].化工自动化及仪表,2007,34(3):1-5.
[4]Adam Slowik,and Michal Bialko.Training of artificial neural net-works using differential evolutional algorithm[C].2008 Conferenceon Human System Interaction,Krakow,Poland.May 25-27,2008.University of Information Technology and Management,2008:60-65.
[5]黄勇军,武友新,刘华斌.应用改进的遗传算法求解TSP问题[J].计算机工程与设计,2007,128:5909-5911.
[6]胡晓辉,李晓阳,陈俊莲.基于贪心策略的混合遗传算法在TSP中的实现[J].兰州交通大学学报,2009,128(3):58-61.
[7]刘海,郝志峰,林志勇.改进遗传交叉算子求解TSP问题[J].华南理工大学学报:自然科学版,2002,12:71-73.
改进的进化神经网络 篇8
1 改进的共同进化模型
1.1 子群体的划分
文献[1]中提出把临床营养决策问题分为2个子问题。考虑到决策是为不同疾病提供一天的营养搭配方案,本文将决策问题分为3个子问题,分别用于寻找早餐、中餐和晚餐的最优解,3个最优解结合成一个完整的膳食配餐方案。
这种分解问题的方式,有利于子群体在进化过程中的信息交换,促进子群体内部按照实际要求搜索局部最优解,并协调子群体间的合作机制,为更好地找到膳食营养总体方案奠定基础。
本文采用实数编码。设总体规模为M的种群POP,分成规模为N的n个子种群popi(i=1,2,…,n),其中n=M/N。每个个体为一个固定长度为l的基因组:
式中x表示食物编号;y1,y2,…,yl-1表示必须达标的营养元素实际摄入量。营养元素的顺序是固定的。不同疾病要求必须达标的营养元素种类不同。例如1个个体(2,1 406,17.7,27.6)表示某疾病必须严格控制能量、蛋白质和脂肪的摄取量,选择2号食物实际提供的能量为1 406 kJ,蛋白质17.7 g,脂肪27.6 g。
1.2 精英保留策略
精英队列为一个有序的数组,用于保存进化过程中的全局最优解,为病人提供了基于自己偏好的选择依据。
精英队列初始值为空,每产生一个新的全局最优解就将其加入队列。新解加入之前需与精英队列中已有的最优解进行比较,若新解的评价值较高则将其插入队列,此时若队列中的最优解已超出规定长度,则淘汰最差解以满足队列长度要求。
1.3 信息交换原则
各个子种群独立进行遗传进化操作,当达到一个预先指定的信息交换时间T时,每个子群体选择一个当代最优个体gbest与其他群体中的最优个体结合成一个全局最优解。通过精英保留策略测试该解是否为精英解,若是则gbest进入下一代。通过信息交换原则可以保持种群的多样性,避免子群体的早熟收敛现象。
1.4 小生境技术
各个子群体是在自己特定的环境内进行进化操作的,因此可以对子群体内部引进基于小生境的遗传算法[2,3]。本文采用NicheGA算法[2],即首先比较群体中两个个体间的距离,按照式(1)求出每2个个体xi和yi之间的海明距离:
式中N为遗传运算前子群体按适应度降序排序的前N个个体,M为经过遗传运算后得到的M个个体。若这个距离在预先指定的距离L之内,再比较两者之间适应度大小,并对其中适应度较低的个体施加一个较强的惩罚函数:
极大降低其适应度,这样,对于在预先指定某一距离L之内的2个个体,其中较差的个体经过处理后其适应度变得更差,它在后面的进化过程中被淘汰掉的概率也就更大。也就是说,在距离L之内将只存在一个优良个体,从而既维护了群体的多样性,又使得各个个体之间保持一定距离,且在整个约束空间中分散开来。
1.5 适应度函数、个体评价与交叉算子的改进
本文设置早餐和晚餐的营养摄入量占1天的3/10,午餐占4/10。则每个个体的适应度按以下式(1)计算:
式中ystandard表示营养元素的标准摄入量;m表示需达标营养元素总个数。
全局最优解是由3个子群体局部最优解组合而成,因而个体评价可表示为:
在进化后期大量个体集中于某一极值点上,为避免近亲繁殖,可利用性别改进的交叉算子[4]。基本思想如下:每个个体标上0或1两种性质,在选择操作时只能选择不同性质的父个体并保证双亲的不同才能生成个体,这一定程度上克服了选择的盲目性,并保持种群多样性。
1.6 算法描述
改进后的共同进化模型描述如下:
(1) 随机生成初始规模为M的群体POP={gi|i=1,2,…,M},并将群体分成规模为N的子群体popj=
{gi|i=1,2,…,N},j=1,2,…,M/N,子群体收敛标记flag=0,置空精英队列elitequeue[k],gen=0;
(2) 由式(3)和(4)计算各个个体的适应度并按降序排序,保存前m个个体(m<N);
(3) 对每个子群体循环执行以下操作,直到flag=1 或gen=maxgen;
(4) 遗传运算,得到群体pop′;
(5) 将群体pop′的N个个体和(1)中保存的m个个体合并成一个规模为N+m的新群体。由式(1)对这N+m个个体计算两两个体间的海明距离。当‖Xi-Xj‖<L时,比较个体Xi和个体Xj的适应度大小,并对其中适应度低的个体处以罚函数(2);
(6) 依据N+m个个体的新适应度进行降序排序,保存前m个个体;
(7) 若达到信息交换时间T则取适应度最高的个体与其他群体当前最优的个体组成一个全局最优解,由式(5)计算个体评价并进行精英保留策略;
(8) 若未达到信息交换时间T则取(4)中前N个个体作为下一代群体,gen=gen+1,转(1);
(9) 算法结束。
2 仿真研究
2.1 数学函数测试
为了证实该算法的有效性,本文使用以下函数进行仿真:
参数设置及实验结果如表1所示:
实验结果如表2所示:
结果表明,算法寻优性能强,有效避免了早熟现象、局部搜索能力弱等问题。
2.2 临床营养测试
以搭配糖尿病人的一天营养膳食为例。针对糖尿病人的日常食谱,专家建议如表3所示:
说明:含糖量为3%以下的蔬菜有大白菜、圆白菜、菠菜、油菜、韭菜、茴菜、苘蒿、芹菜、莴苣笋、西葫芦、西红柿、冬瓜、苦瓜、黄瓜、茄子、丝瓜、芥蓝菜、龙须菜、绿豆芽、鲜蘑、水浸海带等。设某女性病人的基本情况为:年龄55岁、身高160 cm,体重70 kg,体重肥胖、轻度劳动强度。配餐数为早餐3个、中餐6个、晚餐3个。算法参数设置如表4所示:
算法运行后精英队列中保留10个全局解,其中一个最优的方案如表5所示:
从仿真结果可以看出,随机选取的这个膳食方案的个体为(3,5 158.1,47.19,35.46)。表6中三个对糖尿病营养治疗起关键作用的营养素的达标率也达到了满意的标准。并且该患者体重肥胖,合理控制能量是营养治疗首要原则,表6中能量的达标率为97.47%,另外脂肪的达标率为100.85%,两者均控制在合理范围中。表5中的三餐食物满足营养专家建议的食物范围。
综上所述,算法改进后营养素达标率符合要求,并且膳食配方满足专家建议的糖尿病饮食需求。
3 结 语
本文从算法的基本设计入手,除使用新的子群体划分方法和交叉算子外,引入精英保留策略、信息交换原则和小生境遗传算法。通过对糖尿病营养治疗等的仿真,结果表明改进后的共同进化遗传算法在保证群体多样性和避免早熟现象的前提下,提高了算法的局部和全局寻优能力。当然,算法中还存在一些如信息交换时间如何确定等问题,有待于今后进一步研究。
参考文献
[1]张蕾,王高平.共同进化遗传算法在临床营养决策中的应用[J].计算机应用,2007,27(z2):193 194.
[2]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.
[3]Minh Ha Nguyen.A Novel Mixture of Experts Model Basedon Cooperative Coevolution[J].Neurocomputing,2006,70:155 163.
[4]熊伟清,刘明达,魏平,等.一个协同进化计算模型[J].模式识别与人工智能,2005,18(4):441 446.
[5]赵瑞.多目标遗传算法应用的研究[D].天津:天津大学,2005.
[6]王高平,王永骥.改进的多目标遗传算法在营养决策中应用[J].计算机工程与应用,2007(4):202 204,210.
[7]Chen Chao.A Cooperative Fast Annealing CoevolutionaryAlgorithm for Protein Motif Extraction[J].Chinese ScienceBulletin,2007,52(3):318 323.
[8]Shuhei Kimura.Inference of S system Models of GeneticNetworks Using a Cooperative Coevolutionary Algorithm[J].Bioinformatics,2005,21(7):1 154 1 163.