生物地理学优化算法

生物地理学优化算法（精选9篇）

生物地理学优化算法 篇1

反应釜是化工生产过程中的重要反应容器［1 ～ 3］。反应釜在反应过程中分为升温段、恒温段和冷却阶段。而产品成型主要在恒温段进行,但由于反应釜内部反应机理复杂,且具有不确定性及非线性等特性,所以恒温段的温度控制尤为重要。PID控制器是工业生产过程中用途广泛的控制器,但对于难以建立数学模型的反应釜,PID控制效果并不能适应参数变化对温度的影响。为此,国内很多学者对PID控制器进行改进或采用智能控制算法对反应釜温度进行控制,李新卫采用变结构模糊控制等先进的控制方式对反应釜温度进行控制［2］; 翟廉飞等采用PID控制并用神经网络对非线性部分进行估计［3］; 文献[4,5]采用模糊PID控制器控制反应釜温度; 晏琦等将免疫遗传算法优化的模糊神经元控制器用于胶乳聚合反应釜的温度控制中［6］。

生物地理学优化( Biogeography-Based Optimi-zation,BBO) 算法是美国学者Simon D于2008 年提出的一种新的进化优化算法［7］。该算法与常用的遗传算法( Genetic Algorithm,GA) 及差分进化( Differential Evolution,DE) 算法等都属于进化算法,且已应用于电力系统、图像处理及路径规划等工程优化问题中,并取得了较好的优化效果［8］。

为解决PID控制器对非线性、不确定系统控制效果欠佳的问题,受自适应遗传算法PID控制的启发［9］,笔者利用BBO算法优化PID控制器的参数,构成BBO-PID控制模块,用于反应釜温度控制系统,并与传统PID控制和GA-PID控制的仿真结果进行比较。

1 BBO算法1

生物地理学是研究生物种群分布、迁移、变异及灭绝等规律的科学。生物地理学的研究环境是一个生态系统,存在多个栖息地。栖息地的好坏用适应度指数( Habitat Suitability Index,HSI) 来衡量,HSI越高,越适合物种生存和繁衍。BBO算法是基于生物地理学发展起来的一种算法,Simon D根据生物种群的动态过程设计了迁移算子、变异算子和清除算子,以保证算法的开发能力和探索能力。

1. 1 迁移算子

多种共存物种之间存在对生存空间及食物等资源的竞争,因此物种就会迁移到生存环境较好的栖息地。BBO算法利用迁移算子进行栖息地之间的信息共享。迁移操作由迁出概率 λ 和迁入概率 μ 共同决定。迁出概率 λ 和迁入概率 μ 是物种数量S的函数,这种函数关系可以是简单的线型模型,也可以是指数模型、二次模型及余弦模型等,越接近自然规律的迁移模型性能越好［10］。某一栖息地容纳物种数量S的概率Ps为:

其中,n为栖息地容纳的物种最大数量。

根据栖息地的迁入率决定栖息地的分量是否修改,若需修改,则根据迁出率选择被迁入的栖息地,并替换相应分量。

1. 2 变异算子

自然灾害及瘟疫等原因会造成栖息地内原有物种的灭绝和其他物种的大量迁入,因此该栖息地更容易发生变异。栖息地发生突变的概率ms与物种数量S成反比,即:

其中,mmax为最大变异概率; Pmax= max{ Ps} 。

2 BBO算法优化的PID参数

BBO-PID控制结构框图如图1 所示。 利用BBO算法的优化功能,优化PID控制器的3 个参数Kp、Ki、Kd,使反应釜的出口温度达到设定值。

2. 1 目标函数

以系统在不同时刻的输出与期望值之差的平方和作为目标函数,即:

式中ri———时刻i的期望值;

yi———时刻i的输出值。

目标函数值越小,解越优,控制效果越好。对于栖息地来讲,栖息地的适应度值越大,解越优,所以将栖息地的适应度值HSI设为目标函数的倒数; PID的3 个参数Kp、Ki、Kd作为栖息地的特征向量SIV; 优化PID参数的过程就是使HSI提高的过程,HSI越大,即目标函数值越小,解越优。为保证解的优良性,BBO算法中设置了精因数,即保留优良的解,只对其他解进行迁移和变异。

2. 2 BBO算法优化PID参数

BBO算法优化PID参数的具体步骤如下:

a. 设置BBO算法的参数,如进化代数、种群规模、迁移概率、变异概率及优化参数的取值范围等;

b. 初始化栖息地种群,根据种群规模,随机产生种群初始值;

c. 利用增量式PID控制算法计算给定PID下的系统输出,根据式( 3) 计算HSI;

d. 对不同种群的适应度值进行降序排列,保留精英种群,根据迭代终止条件,判断是否终止迭代,若满足终止条件则输出最优解,若不满足则继续以下步骤;

e. 迁移操作,利用余弦模型计算每个栖息地的迁入率和迁出率,根据确定的迁移概率确定是否进行迁移;

f. 变异操作,根据变异概率对种群的解进行变异操作,提高解的多样性;

g. 排异操作,首先对超出参数范围的种群进行重新赋值,然后对相同或相近的种群进行重新赋值,保证解的多样性;

h. 返回步骤c继续进行下一代解的迭代。

3 仿真与结果分析

3. 1 反应釜模型建立

反应釜温度控制系统属于典型的工业过程,在控制过程中存在非线性、不确定性及延迟等特性,因此不能建立准确的数学模型,但其阶跃响应曲线呈S形,数学模型可以用一阶系统加滞后表示,即:

针对某化工厂夹套反应釜,根据其响应特性,确定时间常数T = 500、放大系数K = 3、滞后时间τ = 10s。

3. 2 仿真参数设置

为了说明BBO-PID的控制效果,将仿真结果与PID控制和GA-PID控制效果进行比较,现一一设置具体参数。

PID仿真参数设置。根据经验法整定PID参数,得Kp= 9,Ki= 0. 08,Kd= 0. 1。

GA-PID参数设置。遗传算法采用标准形式,种群个体数量z = 50,终止进化代数G = 600,交叉概率Pc= 0. 9,变异概率Pm= 0. 1 - [1 ∶ size] ×0. 01 / size( size为最优解在种群中的位置) ,优化参数Kp、Ki、Kd,适应度值选择

BBO-PID参数设置。种群数量z = 50,终止进化代数G = 600,迁移概率Pc= 1,变异概率Pm=0. 03,迁入率模型和迁出率模型均采用余弦模型,适应度值同GA-PID。

3.3仿真结果分析

反应釜温度控制系统在3 种控制作用下的单位阶跃响应曲线如图2 所示。可以看出,3 种控制最终都能跟踪单位阶跃,但调节时间和超调量有差别,具体的动态性能指标见表1。可以看出,BBO-PID控制的超调量和调节时间均最小,GA-PID的控制效果次之,由于在恒温阶段,要求温度变化很小,尽量减少超调量,所以BBO-PID可以用于反应釜的温度控制。

由于反应釜系统内部反应机理复杂,在反应过程中系统参数可能发生改变,为模拟实际情况,假设系统模型参数发生改变,即K = 6、T = 1000,参数变化后3 种控制的单位阶跃响应曲线如图3所示,动态性能指标见表1,可以看出,当系统参数改变时,调节时间较原调节时间都加大,这是由于系统惯性环节的时间常数变大而使系统的调节时间增加造成的。PID控制器参数是在原系统下整定出来的,不适合变后的系统,所以动态性能较差。GA-PID控制超调量较小,响应速度较快,但从图4 所示的最小误差进化过程可以看出,GA易陷入局部极小值,BBO算法的优化效果较好。所以BBO-PID的控制效果最好,超调量小且调节时间短,满足反应釜恒温过程的温度控制要求。

4 结束语

以反应釜为研究对象,设计采用BBO算法优化的PID控制器,解决了PID控制器参数不能适应反应釜数学模型的非线性及不确定性等的问题,仿真结果与PID和GA-PID控制效果进行比较,发现GA-PID控制易陷入局部极小值,而BBO-PID控制效果较好,为反应釜温度控制提供了一种可行的控制方法,也为难以建模、存在非线性和不确定性的系统控制提供了参考。

生物地理学优化算法 篇2

一类优化问题的快速收敛算法

给出了一个用于解决LC1线性约束优化问题的BFGS-SQP算法,这个算法是用Armijo线性原则来求步长的.为推广BFGS-SGP算法,本文采用Wolfe线性搜索原则来替代该BFGS-SQP算法的.Armijo原则,经过分析,同样得到了BFGS-SGP算法的全局收敛性及超线性收敛性.

作 者：王道林 宁伟 作者单位：山东泰山学院计算机科学与技术系,山东,泰安,271000刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：34(5)分类号：O1关键词：LC1问题 BFGS-SQP算法 全局收敛 超线性收敛

生物地理学优化算法 篇3

随着我国经济的飞速发展以及城镇化的大力推进, 地铁已经越来多的应用到城市中[1]。城市轨道交通迅速发展, 地铁列车的运行能占占城市电网的50%, 因此降低轨道交通运行能耗已成为城市可持续发展的追求目标。地铁系统的耗能占城市公用设施的较大比例, 列车整个运行过程中存在频繁的起动、制动过程, 这个过程会产生较大的能量消耗和浪费, 因此如何在保证准点和舒适的前提下, 利用节能优化方案指导列车运行, 来降低列车能耗成为主要的研究课题。

Nag和Pal[2]通过对列车的站间运行时间和发车间隔进行研究, 最终调整时间来优化了时刻表。A.Nasri, M.Fekri Moghadam等人通过改进列车进出站的时间, 使列车能同步运行, 从而实现对再生制动能量的有效利用, 并利用仿真软件进行研究分析, 得出结论。Gordon等[3]首次提出通过对列车牵引和制动顺序的控制, 来实现再生制动能量的转换和利用。G.Malavasi和F.Palleschi等人[4]提出了将再生制动与时刻表完美匹配达到最理想的清况这一概念, 但是这种模型在列车运行的实际情况中是无法实现的。而后Andres等通过调整列车的列车的牵引和制动时间来提高再生能量的利用率。P.Maite, F.Antonio等人实现了列车出站牵引加速和进站制动减速的时间同步模型, 设计了新的列车运行时刻表, 提高了再生制动能的利用率和时刻表的鲁棒性;陈勇等人[5]对城市轨道交通再生制动能量吸收方式进行了研究。石红国等运用遗传算法对列车运行过程进行优化[6], 优化运行时间表, 进行节能优化, 但遗传算法的局部搜索能力较弱, 而且有早熟收敛现象;Chen J.F.等通过优化列车停站时间来降低地铁运输系统能耗峰值[7], 但停车时间的不确定性以及人流量等其他因素会影响控制的效果。

因此, 通过调整列车的站间运行时间和发车时间间隔, 来提高再生制动能量的利用率。本文利用生物地理算法对停站时间增量表进行优化, 在保证安全运行的前提下, 更改列车的运行和停站时间, 使列车改变原有的时间运行方案运行, 使更多的列车在同一时间进出站, 以获得最小能耗, 最终达到节能的目的。

2 列车运行时间优化原理及模型

2.1 列车运行时间优化原理

如图1所示, 当列车B进站时, 列车制动刹车, 这时置于车底的电机会产生电能回馈到直流电网, 此时回馈到电网的电能被在同一时刻正在进行牵引运行的列车吸收利用, 若是不被利用, 那么就将这部分能量存储到储能元件 (比如超级电容) 中去, 这部分存储的能量可以为其他所需要的地方供能, 或者为以后列车的运行提供能量。若是这部分电量得不到存储, 那么这部分电能会被制动电阻吸收并且以热能的形式释放掉, 就造成了能量的浪费;而当列车A出站时, 列车牵引加速运行, 电能从电网流到列车, 列车消耗这部分电能。因此如果同一时间内, 能使更多的列车同时进出站, 这样的话列车牵引启动的能耗就是制动列车刹车是产生并回馈到电网的电能, 因此这个能量相互吸收利用的过程就能减少整个地铁系统对城市电网能量的消耗[8,9]。

2.2 列车运行时间优化模型

为了获得更好的节能效果, 在研究列车节能运行策略的同时, 也将时刻表的优化问题进行考虑, 将二者相结合运用一个双层模型建模, 设计一个整合算法优化列车驾驶策略的同时也对全局时刻表进行优化, 从而获得更好的节能策略。

因此, 要求消耗最小的能量, 对整体耗能控制的目标函数如下:

式中, E (Ti) 表示列车运行区间的总能耗, 单位为k W·h;Ti为第i辆列车运行的时间。

根据供电指标、能耗指标、容错率指标、运营指标、安全指标等因素添加约束条件或者将其中几个指标进行加权处理, 以获得最佳的节能目标。而本文暂只考虑安全指标和能耗指标, 因此基本约束条件的设置如下:

(1) 对于部分客流量较大的站点, 停站时间只增不减;

(2) 同一时间, 进出站列车的能耗全部被利用;

(3) 列车运行周期的总时间变化限定在-12s~12s之间;

(4) 列车运行过程中, 不考虑能量以各种方式的损耗;

(5) 列车的运行最小间距不能小于800m。

3 BBO算法对时间方案的设计

3.1 BBO算法简介

生物地理学这门学科为生物地理算法提供了基础, 在这个学科中, 通过对所在栖息地的生物种群的生存条件和生存状态进行分析研究。在20世纪四十年代, Eugene Munroe就将生物地理算法运用到数学模型中, 这时第一次将这种算法与数学建模联系起来, 为后面算法的发展奠定了强有力的基础。

生物地理优化算法是通过种群中个体的相互协作和相互竞争的关系来进行全局优化的。这种算法的鲁棒性能好, 算法的过程相对简单, 易实现。一般多用于解决多目标高维度的问题[10]。

3.2 BBO算法的优化流程

BBO算法对时间方案优化的基本步骤[11]如下:

(1) 设置算法参数;

(2) 生成初始栖息地维度, 即停站时间修正量初始矩阵X0, 先根据约束条件进行有效性筛选;

(3) 计算每个栖息地的适宜度Hi, 针对不同适宜度Hi, 将栖息地从好到次进行排列, 一般取栖息地的更新率i=1;

(4) 通过比较, 判断是否为所需的最优结果, 如果是最优结果, 则输出值, 流程结束。否则继续步骤 (5) ;

(5) 计算每个栖息地的迁移率和突变率, 进行迁移和突变操作, 重新计算栖息地的适宜度Hi, 返回步骤 (3) 。

4 仿真案例分析

4.1 武汉地铁二号线

武汉地铁二号线全程27.7km, 总共21个站点, 根据数据统计可以得知, 有16辆列车同时并联运行, 因此构成了一个16×21的矩阵, 面对这种过于高维度, 计算过于复杂的问题, 不适合仿真操作。因此将模型简化, 在计算方便的同时也可以验证优化模型和算法的可行性。故简化地铁二号线模型, 简化后的模型为:模型由5辆车并联, 6个站台组成, 线路为汉口火车站-范湖站-王家墩站-青年路站-中山公园站-循礼门站, 未包括首末两站, 则可形成一个6×5的时间分配矩阵, 一共30个元素。每个元素表示一辆列车在一个站点的停站时间修正量, 根据每辆列车的停站时间的波动范围, 最终可以确定所有列车的停站时间修正量的范围为[-5, 5], 单位为s。

4.2 BBO算法对时间方案的优化

初始化BBO算法的基本参数, 设定栖息地数量n=20, 栖息地种群最大容量Smax=50, 对每个栖息地的最大迁入率I=1, 对每个栖息地的最大迁出率E=1, 迁移概率Pmod=1, 最大突变概率mmax=0.05, 优化维度D=30的维度向=量

初始矩阵为最开始的没有调整前的停站时间修正量, 即按照实际没有调整的时间来生成:

将初始矩阵导入Matlab仿真平台, 进行优化仿真, 得到牵引网功率与时间的关系图, 如图2所示。

由图中可知, 列车按照优化之前的运行, 牵引网功率有部分时间趋近零, 也就说明有部分列车的制动功率被吸收利用, 有部分时间的功率很高, 说明了这个时间内有更多的列车在制动运行, 此时车制动能量将反馈到电网, 也有部分时间的功率较低, 说明了此时有更多的列车在进行牵引运行, 需要消耗电网电能, 使电压降低, 功率变小。

经过20次迭代产生新的优化矩阵, 最终得到的优化时间修正量的矩阵如下:

将最终得到的列车运行时间优化方案导入到仿真模型中, 得到BBO优化后的牵引网功率与时间的关系图, 如图3所示。

由上图可知, 相对优化前的牵引网功率, 优化后的功率有更多的地方接近零, 说明列车制动能量相互吸收的过程变多了, 也就是说更多的制动能量被启动列车给利用了, 达到了节能优化的效果。

4.3 结果分析

通过对列车运行停站时间增量表的优化, 得到的列车运行优化前后的能耗值对比图, 如图4所示。

从图表中可以看出, 使用生物地理算法对时间方案进行优化, 能耗减少了, 达到了节能的效果。

5 结语

利用BBO算法对多列车运行的时间方案优化, 达到了节能的效果。但是实际列车运行中, 列车运行的线路, 复杂的工况以及人流量等等其他一些因素的影响, 使得这个过程更加复杂化。在对时刻表的优化, 是按照整秒的情况来优化的, 所以优化的结果也不会特别精确, 与连续时间上的优化还是有差别。理论上要是精确到小数的话优化的结果也是较为精确的, 但是实际操作的话以整秒为准, 故而这也是有待解决的问题。所以在实际中如何进行优化调整需要进一步的研究。

参考文献

[1]陆化普.城市交通规划与管理[M].中国城市出版社, 2012.Lu Huapu.Urban transportation planning and management[M].China City Press, 2012.

[2]Nag B, Pal M N.Optimal Design of Timetables to Maximize Schedule Reliability&Minimize Energy Consumption, Rolling Stock and Crew Deployment[J].Social Science Electronic Publishing, 2003.

[3]Gordon S P, Lehrer D G.Coordinated train control and energy management control strategies[C]//Railroad Conference, 1998.Proceedings of the 1998 ASME/IEEE Joint.IEEE, 1998:165-176.

[4]Malavasi G, Palleschi P, Ricci S.Driving and operation strategies for traction-energy saving in mass rapid transit systems[J].Proceedings of the Institution of Mechanical Engineers Part F Journal of Rail&Rapid Transit, 2011, 225 (5) :475-482.

[5]陈勇, 罗锐鑫.城市轨道交通再生制动能量吸收方式的研究[J].城市轨道交通研究, 2012, 15 (8) :157-159.Chen Yong, Luo Ruixin.On Regenerative Braking Energy Absorption in Urban Rail Transit[J].Urban Mass Transit, 2012, 15 (8) :157-159.

[6]石红国.列车运行过程仿真及优化研究[D].西南交通大学, 2006.Shi Hongguo.Simulation and optimization of train operation process[D].Southwest JiaoTongUniversity, 2006.

[7]Chen J F, Lin R L, Liu Y C.Optimization of an MRT Train Schedule:Reducing Maxi-mum Traction Power by Using Genetic Algorithms[J].IEEE Transactions on Power Systems, 2005, 20 (3) :1366-1372.

[8]彭赛庄.基于SVPWM控制的地铁再生制动能量吸收系统的仿真研究[J].新型工业化, 2015, 5 (3) :20-27.Peng Saizhuang.Simulation Research on energy absorption system of Metro regenerative braking based on SVPWM control[J].Journal of New Industrialization, 2015, 5 (3) :20-27.

[9]谢少华.基于Matlab的无刷直流电机控制系统仿真研究[J].新型工业化, 20150, 5 (3) :28-34.Xie Shaohua.Simulation Research on energy absorption system of Metro regenerative braking based on SVPWM control[J].Journal of New Industrialization, 2015, 5 (3) :28-34.

[10]许秋艳.生物地理学优化算法及其应用研究[D].华东师范大学, 2011.Xu Qiuyan.Research on Biogeography-Based Optimization and it's application[D].East China Normal University, 2011.

基于遗传算法的飞机气动优化设计 篇4

基于遗传算法的飞机气动优化设计

建立了一种以实数编码技术为基础的遗传算法模型,并把它与通过工程估算的气动分析方法相结合,进行飞机气动外形的单点和多点优化设计.优化设计中,设计变量取为机翼、机身和尾翼的外形及三者之间的相对位置,优化目标是使飞机在跨音速和超音速飞行状态下获得配平状态下最大的升阻比.设计结果表明该优化设计方法是十分有效的.,可以用来对具有正常布局形式的飞机进行气动外形的优化设计.

作 者：王晓鹏 作者单位：西北工业大学,飞机系,西安,710072;上海航天技术研究院,上海,33刊 名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS年，卷(期)：200219(2)分类号：V211.3关键词：遗传算法 气动外形 优化设计

生物地理学优化算法 篇5

鉴于群智能优化算法的优良特性,很多学者应用群智能优化算法代替BP算法进行神经网络的训练。周颖等提出了一种人工免疫学习算法,将其用于RBF神经网络隐层中心点数和位置的调整［4］; 田文杰等将蚁群算法和神经网络结合起来,应用于设备故障专家系统的知识获取并进行诊断推理［5］; 文献[6]将粒子群优化算法用于优化神经网络的连接权值和阈值,并将优化好的神经网络应用于故障诊断中。

基于对生物物种迁移、变异行为的研究,以生物地理学归纳计算为理论的生物地理优化算法( Biogeography-based Optimization,BBO) 是一种新型的群智能优化算法。鉴于其他群智能优化算法在神经网络训练中的应用,笔者将生物地理优化算法与BP神经网络相结合,建立BBO-BP组合神经网络模型,充分发挥BBO解决优化问题的优势,克服连接权值随机导致神经网络易陷入局部极小值的缺点,缩短训练时间。

1 生物地理优化算法*

生物地理优化算法就是根据生物地理学阐述的生物物种在地理上分布的特点,使用生物地理学的分配机制( 即迁移模型、变异生新) ,以适宜度最优为求解目的,来解决工程问题［7］。具体说就是,待优化问题的解对应着生物地理学中栖息地的特征向量SIV,其中的各种自然因素相当于优化问题解向量的分量; 待优化问题的度量函数值f( xi) ( i = 1,2,…,n) 对应着生物地理学中的栖息地适宜度指数HIS,好解类似于高HIS的栖息地,差解类似于低HIS的栖息地; 优化算法中的信息交互机制对应着栖息地的移近移出机制,设计了基于概率的个体迁移算子实现信息共享,每个个体通过计算得到各自的移进概率 λi和移出概率 μi,通过该数值来控制个体信息的移动概率。同时,为增加群体多样性,设计变异算子,根据栖息地容纳种群数量的不同,计算相应的变异率,对栖息地进行变异操作,从而扩大解集。

生物地理优化算法的精髓即迁移操作和变异操作,利用迁移操作与其他栖息地进行信息交换,进而对解空间进行广域搜索; 利用变异操作来模拟自然突变,根据栖息地i的种群迁移率对栖息地的特征向量进行突变进而更新解集。

迁移操作。迁移模型采用的是简化线性模型,设栖息地的数量为n,群体大小为NP,优化问题的维度为D,最大物种数为Smax、最大迁出率为Emax、最大迁入率为Imax,具体的流程为:

变异操作。最大变异率为mmax,迁移率为Ps,精英个体保存数量为k,BBO变异操作的核心问题就是如何根据栖息地拥有种群数量的概率给出相应的突变率,具体的流程为:

2 生物地理优化算法与其他群智能算法的比较

虽然BBO算法和其他智能算法一样,都属于模拟自然选择和生物进化机制的智能优化算法,但是该算法和其他算法有本质区别,以下为与其他算法的比较。

2. 1 与遗传算法的比较

BBO也会在解之间实现信息的共享,但在进化过程中并不产生新的子代,算法利用移进概率来决定栖息地是否需要引入特征变量以及进入的比例,并且移进的特征变量来自其他不同的个体而遗传算法通过染色体来共享信息,通过交叉变异重组基因单元来产生新的子代,它不能根据适应值来控制交叉基因,并且交叉的基因片段来自于同一个体。

2. 2 与蚁群算法( ACO) 的比较

BBO是通过迁移机制来改进解的适应度,它并不直接产生新的解集,只是依赖迁移机制来修改这些解; 而ACO是通过蚂蚁之间信息素的交换和相互协作来实现优化,在每次迭代过程中要产生新的解集,每一代都会产生一系列方法,而BBO则会保持方法不变。

2. 3 与粒子群优化算法( PSO) 的比较

BBO同粒子群优化算法最为相似,都是通过个体间的知识分享来达到优化的目的,都将产生的优质方案保存到下一代,每一个方案都和邻近个体进行信息交互,进而进行调整。但BBO采用了根据不同栖息地种群数量来选择不同操作强度的物种激励机制,从而通过迁移机制调整解集来改进解的适应度,而PSO是通过调整粒子的速度和位置来改进粒子的适应度。另一方面粒子群的解更可能聚在一起,而BBO的解没有任何内在聚类的趋势。

从这些不同之处可以看出BBO算法是一种独特的群智能优化算法。

笔者采用典型的Sphere单峰函数和Rastrigi多峰函数进行测试,并与典型的群智能算法———蚁群优化算法、遗传算法和粒子群优化算法进行仿真性能比较。算法对于各个测试函数优化的平均运行结果如图1、2 所示。

表1 列出了测试函数过程中每一个算法的平均极小值( 表示算法的平均性能) 和最好极小值( 表示算法的最好性能) 。

从测试结果可以看出,对于Sphere单峰函数BBO前期收敛速度快,找到最优解的精度没有PSO好; 但在处理Rastrigin多峰函数时,BBO的收敛速度快,并且较其他算法最接近优化值。综上所述,BBO处理优化问题还是具有优势的,求解过程中不存在波动,稳定性较好。

3 基于生物地理优化算法的神经网络故障诊断基于神经网络的故障诊断中,神经网络的输

基于神经网络的故障诊断中,神经网络的输入是被诊断对象的征兆即特征值,输出则表示发生故障的可能性。在整个诊断过程中,先利用一组故障样本对网络进行训练,确定网络结构和参数,进而实现征兆集与故障集之间的非线性映射。借鉴其他智能算法在神经网络故障诊断中的应用,笔者将BBO算法与基于BP神经网络的故障诊断相结合,把BP神经网络结构中有待训练的权值和阈值看作是BBO算法的寻优目标参数,用BBO算法作为学习算法对BP神经网络的权值和阈值进行训练。

3. 1 建立神经网络

笔者选取应用最广泛的三层神经网络,以文献[8]中的抽油机数据( 表2、3) 为例,输入节点对应电流特征向量的6 个分量,输出节点数为3,对应抽油机的3 种工作状态。

3. 2 确定参数

利用BBO算法训练BP神经网络时,定义生物栖息地适宜度分量为网络中的连接权值。笔者采用6-6-3 结构的三层神经网络,权值为6 × 6 + 6 × 3 = 54,阈值为6 + 3 = 9,故栖息地适宜度模型维数为54 + 9 = 63。设置群体大小NP =100,Imax= Emax= 1. 0,最大变异率mmax= 0. 005,迭代次数为1 000。

3. 3 基于BBO算法的神经网络训练

将BBO作为学习算法来优化神经网络权值的关键在于以下两点:

a. 建立BBO的物种维度空间与神经网络连接权值之间的映射。生物地理优化算法中,每个生物栖息地的维度分量都对应为神经网络中的一个连接权值,也就是说神经网络中有多少个连接权值,作为学习算法的BBO中的每个栖息地就应该有多少维。

b. BBO算法适宜度函数的选取。用BBO来训练神经网络的最优权值和阈值,就是为了通过改进的BBO算法强大的搜索性能使网络的均方误差最小化,适宜度函数

BBO算法训练BP神经网络的流程如图3 所示。

图4、5 为传统BP算法和BBO算法对神经网络的训练曲线。从图中可以看出: 在达到目标系统误差10－ 2时BBO算法迭代次数为653 次,要达到相同的误差时,BP算法需要1 194 次。在满足相同系统误差的条件下,BBO算法所需训练时间为10. 14s,而BP算法所需训练时间为36. 18s。经计算,利用BBO算法训练神经网络的均方差为0. 301 3,小于利用BP算法训练网络的均方差0. 765 8,可见BBO算法不仅提高了神经网络的信息处理速度,并且提高了网络的训练精度。

3. 4 故障诊断结果分析

利用训练好的神经网络对抽油机进行故障诊断,对测试样本数据( 表3) 进行诊断仿真实验。假定将大于0. 5 的输出节点值近似看作1,将小于0. 5 的输出节点值近似看作为0,( 100) 、( 0 1 0) 、( 0 01) 分别对应着正常、双凡尔漏失和抽油杆脱落,诊断结果见表4。

从表4 可以看出,基于BBO的神经网络的诊断数据接近于理想值,故障区分度较高,因此可以得出结论: 利用BBO算法优化神经网络应用于抽油机故障诊断中是可行的,并具有很强的准确性。

4 结束语

阐述了生物地理优化算法的优化原理和算法流程,并将其与其他群智能算法进行比较,通过仿真实验得出,BBO算法具有很强的优势性与良好的发展空间。将生物地理优化算法应用于神经网络的学习训练中,克服了BP算法训练时间较长并容易陷入局部收敛的缺点,而且能更快速地收敛于目标最优解。将训练好的神经网络对抽油机常见故障进行诊断,诊断结果表明: 该方法是可行的,并且具有良好的准确性和有效性,具有广泛的应用前景。

摘要：将生物地理优化算法和BP算法相结合,提出一种基于生物地理神经网络的故障诊断方法。采用生物地理优化算法优化神经网络的连接权值和阈值,运用这种新型算法的高效优化性能改进了传统BP神经网络收敛速度慢、易陷入局部极小值的缺点。将优化好的神经网络应用于抽油机的故障诊断,通过仿真实验得出:生物地理优化算法训练神经网络是可行的,并且诊断结果具有良好的有效性和准确性。

生物地理学优化算法 篇6

关键词：生物地理学优化算法,风电,优化,帕累托最优,模型

0 引言

除了各种新能源的并网运行之外,通过电力系统优化调度,调整不同机组间的负荷分配也是控制废气排放的有效手段之一。与提高传统化石燃料机组效率、加装脱硫处理装置等方法相比,电力系统优化调度具有不需要增加硬件、投资少、见效快的优势。因此,正确和高效地处理含风电场电力系统的优化调度是实现电力生产节能减排的有效手段之一。

传统电力系统优化调度问题考虑经济调度ED(Economic Dispatch)[1],将发电成本作为单一目标。电力系统经济环境优化调度EED(Economic Environ mental Dispatch)模型,在传统ED问题的基础上加入环境影响函数,构建电力系统经济环境双目标优化调度模型[2]。处理多目标优化问题的传统方法是赋权值策略,通过设定权重因子,将多目标问题转化为单目标问题求解[3]。这类方法的缺点在于过分依赖权重参数,需要多次优化寻找帕累托解集,无法求出非凸集中的解。另一种方法是使用帕累托最优的概念评价解的优劣[4],即解间的支配关系,将优化目标转化为寻找一组符合评价标准的解。然而,原始帕累托最优的概念不仅无法评价互不支配的解的优劣,也不能表示某一解对另一解的支配程度,使用中非常不便。目前,解间支配关系的求解方法可分为NDS(Non-Dominated Sorting)[5]和MOR(Multi-Objective Ranking)[6]2种。然而NDS和MOR都依赖于被支配解的存在,当目标维数增加时,解集中含非支配解的概率大幅下降,对于解的区分度也会随之极大降低[7]。Farina和Amato提出使用模糊支配的方法求解解间的支配关系[8]。模糊支配的定义更接近支配的原始概念,在处理多目标函数的优化问题中具有更好的实用性。

求解优化问题的算法主要分为传统算法和启发式算法2种。后者中目前得到广泛研究和应用的有遗传算法(GA)[9,10,11]、进化规划算法[12]和粒子群优化(PSO)算法[13,14,15]等。Dan Simon在2008年提出一种新的启发式算法——生物地理学BBO(Biogeography-Based Optimization)算法通过模拟自然界不同栖息地种群数量的变化过程寻找优化问题的最优解。文献[17]的研究表明BBO算法在非凸性电力系统经济调度问题上比其他启发式算法具有更好的收敛性、更高的计算效率,所得解的质量更优。但目前BBO算法在电力系统的应用仅限于处理单目标优化模型。

本文提出基于模糊支配的生物地理学FDCBBO(Fuzzy Dominance-Combined Biogeography-Based Optimization)算法,使用模糊支配(fuzzy dominance)的方法计算解间的支配关系,然后用解间的支配关系代替BBO算法中的估价函数,并将其应用于含风电场电力系统双目标优化调度。实例验证表明,FDCBBO算法同使用同样支配算法的遗传算法(FDCGA)、粒子群算法(FDCPSO算法)相比,具有更好的计算性能。

1 含风电场的电力系统双目标优化调度模型

1.1 目标函数

1.1.1 含风电场电力系统发电成本目标

在含风电场电力系统中,采用风电全部优先并网策略,发电成本由火电成本和风电成本组成。火电成本主要是煤耗成本,而风电成本主要是风电场运行成本,分别如式(1)和式(2)所示。

其中,N为运行火电机组的台数;ai、bi、ci、di、ei为第i台火电机组的发电费用系数;PTi为第i台火电机组的有功功率输出;PT为由PTi(i=1,2,…,N)组成的向量;PTimin为第i台火电机组的有功出力下限;Pw为风电场的等值出力;δ为风电场运行费用系数。

由式(1)和式(2)可得系统发电成本目标函数:

1.1.2 含风电场电力系统环境影响目标

电力生产过程中产生的CO2、SO2、NOx等有害气体给生态环境造成了严重的污染和破坏。本文采用环境影响因子y代表电力生产所产生废气排放总量(t/h)[18]:

其中,αi、βi、γi、ξi和λi为环境影响因子系数。

系统环境影响目标函数为:

1.2 约束条件

1.2.1 功率平衡约束

其中,Ploss为网损,PD为有功负荷。火电与风电机组总的有功出力应该能够平衡总负荷与线损之和,Ploss由Kron公式计算[19]。

其中,Bij、B0i、B00为系统网损参数,Pi、Pj分别为第i、j台机组的有功出力。

1.2.2 机组出力约束

在稳态运行中,机组有功出力满足上下限限制。

其中,PTimax和PTimin分别为第i台机组的有功输出上限值和下限值。

2 FDCBBO算法

2.1 支配度的数值解法

2.1.1 模糊支配

假设最小化问题有Nobj个目标函数fi,其中,i=1,2,…,Nobj。

定义1 i维模糊支配。

定义一个非减的隶属度函数μidom(fi(X))[0,1],i=1,2,…,Nobj。

若fi(Xu)

定义2解的模糊支配。

若坌i{1,2,…,Nobj},Xu刍iFXv,称解Xu模糊支配解Xv,记作Xu刍FXv,模糊支配的程度可通过计算第i维模糊关系Xu刍iFXv(i=1,2,…,Nobj)的交集得出。模糊交集可以通过一系列称为t-norms的函数求得,其操作用Ⅰ表示如下:μdom(Xu刍FXv)=Ⅰi=1Nobjμidom(Xu刍iFXv)。

定义3群体模糊支配。

考虑一个包含M个解的解集X。若X中的一个解Xv被X中剩余的任意一个解Xu支配,则称Xv在X内被模糊支配。这种情况下,模糊支配的程度可通过对每个可能的μdom(X刍FXv)求并集得出。模糊并集的求法由一系列被称为t-conorms的函数决定。具体方法参见文献[20]。

2.1.2 解的分布密度

某一解在解空间中的分布密度用每维目标函数上与其相邻2点的标准化距离之和表示,如式(9)所示:

其中,O(Xv)为Xv处Nobj维封闭超立方体的大小,此超立方体仅包含Xv1个解;Xu、Xw为将解集按第i维目标函数值fi(X)升序排列后与Xv相邻的解。边界解的O值赋为无穷。

由上述分析可知,解的分布密度越小,解集的多样性越好。

2.1.3 非支配度排序

对于待优化解集中的解,采取以下策略进行排序:

a.支配度小的在前;

b.对于支配度相同的解,分布密度小的在前。

采用以上策略处理多目标优化问题,将解集中的解按照优劣程度排序,可以促进帕累托最优前沿POF(Pareto Optimal Front)向理想帕累托曲线收敛及目标解集中的解在POF上的均匀分布。

2.2 BBO算法

BBO算法的参数包括栖息地的适宜度指数、栖息地的特征变量向量、优化问题中变量、某栖息地容纳的种群数量s及概率Ps、最大种群数量smax、迁入率λ、迁出率μ。系统变量包括系统迁移率Pmod和系统最大突变率mmax。算法中主要包括迁移和变异2种操作。

a.迁移。

BBO算法的迁移操作用于修正解集中已存在的解。首先根据Pmod判断是否对解集中的某个解K进行修正;然后使用λ决定是否对此解K中的第i个因子进行修正;最后使用μ从解集中剩余解中选出一个解u,用u的第i个因子代替K中原有的第i个因子。

b.变异。

变异操作用于增加群体的多样性。变异率由该栖息地种群数量概率决定:

其中,mmax为最大变异率,由用户决定;Pmax为栖息地种群数量达到最大时的效率。

2.3 FDCBBO算法

本文在基本BBO算法的基础上,用模糊支配求解解间的支配关系并将解集中的解排序,代替基本BBO算法中的栖息地适宜度指数作为解的评价标准,形成FDCBBO算法。在算法进化过程中,不再直接用迁移、变异后的个体代替原有个体,而是产生一个新的解集,与原解集融合,重新排序,选择2个解集中较好的个体形成下一代解集。FDCBBO算法流程如图1所示。

3 算例分析

本文采用IEEE 30节点系统验证所提FDCBBO算法的可行性及含风电场电力系统双目标优化模型的有效性。由于阀点效应对火电机组发电费用的影响很小,因此忽略不计。6台火电机组参数见表1和表2。系统负荷PD=2.834 p.u.,风电场运行费用系数δ=0.5元/MW,风电场在节点19接入系统,其有功出力Pw=20%PD。设置3种算法的种群规模及迭代次数均为50。GA采用单点杂交,杂交、变异率分别取1和0.01;PSO算法中惯性常量取0.3,学习因子均取1,邻域粒子数取7。

基于模糊支配的PSO算法、GA、BBO算法求解模型所得的POF分别如图2—4所示。POF两端极值点分别对应最优发电成本解和最优环境影响因子解。图2所示POF的形状与理想帕累托曲线相差很远,解在曲线上的分布极不均匀,两端分布稀疏,中部稍为密集。图3中的POF曲线中部较为光滑,但靠近最优发电成本端的曲线光滑程度较差,曲线的形状较接近理想帕累托曲线;解的分布同图2相比较均匀,但在POF极值点附近的分布仍不够理想。图4是基于本文所提出的FDCBBO算法所得POF曲线,从图中可以看出,该曲线光滑,形状与理想帕累托曲线最接近,且求得的非支配解在曲线上的分布均匀。

表3、表4列出了使用3种算法分别进行10次独立运算得到的最优发电成本解和最优环境影响因子解(表中PTi为标幺值)。通过比较可知,使用FDCBBO算法得到的最优发电成本解与使用FDCGA和FDCPSO算法所得的相应解相比,发电成本和环境影响因子均最小,因此更靠近原点。使用FDCBBO算法得到的最优环境影响因子解的环境影响因子虽然与使用FDCGA求得的相应值同为最小,但其发电成本仍为最小,因此更靠近原点。

综合以上分析可以得知,FDCBBO算法在收敛性和解的多样性方面均优于FDCGA和FDCPSO算法。

在不同风电场有功出力的情况下,使用FDCBBO算法所得的POF曲线如图5所示。负荷一定时,随着风电场有功出力的增加,火电厂的总出力PTs减小。由图5可以看出,随着PTs的减小,发电成本减小的趋势较为明显,而环境影响因子则有缓慢的增加趋势,这是由于发电成本表达式和环境影响因子表达式均由火电机组有功出力的二次函数近似,函数值在最低点附近变化缓慢,远离最低点处变化快。虽然每台机组有独立的有功功率-发电成本特性曲线和有功功率-环境影响因子特性曲线,但是在火电总负荷波动达到一定值时,POF曲线会随火电机组运行特性曲线的总体变化趋势移动。由于火电机组的发电费用系数均为正,在功率的负半轴取到其发电费用特性曲线极小值点,所以在实际运行中火电发电总成本与火电总负荷大小成正比。同时,由于风电发电成本很小,系统发电成本近似与风电场等值出力大小成反比。环境影响因子系数中,αi、γi为正值,而βi为负值,在功率的正半轴取到环境影响因子极小值点,所以随着火电机组总出力增大,环境影响因子经历一个先递减再递增的过程。由于风电穿透极限功率有限,负荷一定时,火电机组的总出力变化不大,因此,风电的并网对电力生产环境效益影响十分有限。

随着PTs的变化,POF中发电成本和环境影响因子最大值的变化如表5所示。由于POF形状变化极小,发电成本和环境影响因子最大值的变化即可代表POF位置的变化。

综上所述,风电的加入对于减少发电成本有显著作用,而电力生产的环境效益则更多依赖于火电总负荷的大小、火电机组的环境影响因子特性曲线及负荷分配方案的选择。

4 结论

本文提出了应用BBO算法求解含风电场电力系统双目标优化调度问题的方法,并通过实例验证了算法的有效性,分析了不同风电场等值出力对含风电场电力系统电力生产经济效益和环保效益的影响,由此可得出如下几点结论。

a.在传统发电成本目标函数中加入风电发电成本,同时考虑污染物排放量作为环保目标,构建了含风电场的电力系统双目标优化调度模型。

b.将模糊支配与BBO算法结合,用于电力系统双目标优化调度问题的求解,实例验证表明,本文所提FDCBBO算法在解集收敛性及多样性方面均优于FDCGA和FDCPSO算法。

c.不考虑风电出力,当火电总出力由小增大时,系统电力生产的废气排量先减小后增大,环境效益先增加再降低。这说明电力生产环境效益的改善与火电总出力及环境效益因子特性曲线有关。

d.当系统内风电全部优先并网时,风电场等值出力的增加会显著降低发电成本,增加经济效益,但是对环境效益的改善则不明显;这也说明电力生产环境效益的改善更依赖于负荷分配方案的选择,同时,更突出了电力系统优化调度研究的重要性。

算法分析与优化 篇7

在进行程序设计时, 同一问题可以用不同的算法解决, 而一个算法的质量优劣将影响到程序运行的效率。在存储空间和程序运行时间要求苛刻的情况下, 就必须对各种算法进行分析, 其目的在于选择合适算法和改进算法。算法分析主要是指分析算法的效率, 它主要包含两方面的内容:算法的运行时间和运行使用空间。我们可以通过对同一问题的不同算法分析来评价这些算法的优劣。

2 算法的运行时间

一个算法执行所耗费的时间, 从理论上是不能算出来的, 必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试, 我们可以通过算法花费的时间与算法中语句的执行次数成正比这种关系来判断不同算法执行所耗费的时间的不同。下面我们通过分析一个具体问题的不同算法来说明各种算法的执行时间效率。

问题描述:求范围[2, n]内的所有素数 (质数) 。

算法一:判断一个整数n是否是素数, 可依次进行n/2, n/3, ..., n/ (n-1) 试除, 如果都没有除尽, 则n是素数, 否则n不是素数。简单说:就是试除到n的前一个数。

算法二:判断一个整数n是否是素数, 可依次进行n/2, n/3, ..., n/ (n/2) 试除, 如果都没有除尽, 则n是素数。否则n不是素数。简单说:就是试除到n的二分之一处。

算法三:判断一个整数n是否是素数, 可依次进行n/2, n/3, ..., n/sqrt (n) 试除, 如果都没有除尽, 则n是素数;否则n不是素数。简单说:就是试除到n的开平方根处。

上述三种算法都涉及到如下双循环语句结构:

其中, “□”处可依次用n-1、n/2、sqrt (n) 分别代替形成前面对应算法。

上述三种算法采用的都是双循环结构, 无论是判断单个数还是判断完所有数, 三种算法的运行次数显然是不同的, 算法一执行次数最多, 算法二位列其次, 算法三执行次数最少。然而, 如果我们逆向思维, 结合第三种算法思想, 以范围内所有整数的可能最简因子作为外循环, 内循环采用排除法, 排除那些因子倍数的非素数, 最后剩下的便是我们所要的范围内的所有素数, 具体算法如图2所示算法四函数模块。

算法四同算法三比较, 算法执行的时间进一步缩短了, 但带来了新的问题:算法在运行过程中增加了内存空间的开销。如何压缩使用内存成为我们接下来需要改进算法的目的所在。

3 算法运行使用空间

针对前面提出的新问题, 我们可以基于如下思想:对于处理一段在连续区间分布的整数, 我们可以利用二进制位和位运算, 通过公式运算将每个整数转换到连续区间分布的某位二进制位上, 从而实现存储空间的压缩使用。如果系统存储一个整数需要2个字节, 则新算法可以实现用1位代替2个字节;如果系统存储一个整数需要4个字节, 则新算法可以实现用1位代替4个字节, 具体算法如图3所示算法五函数模块。

4 结束语

算法设计是软件开发的灵魂, 不同的人可能设计出不同的算法, 每种算法在执行时间和使用空间上可能存在差异。在存储空间和程序运行时间要求苛刻的情况下, 就必须对各种算法进行分析, 以期追求最优的算法。编写好的算法也是一个优秀程序设计人员所追求的目标, 笔者也想借此抛砖引玉, 希望广大程序设计人员设计出最优的算法。

参考文献

[1]严蔚敏.数据结构.北京:清华大学出版社, 2008

[2]黄维通.Visual C++面向对象与可视化程序设计.北京:清华大学出版社, 2001

生物地理学优化算法 篇8

随着课改的不断深入, 部分教师在运用此理念的过程中走入了一些误区.

误区一:把“提倡算法多样化”理解为“一定要算法多样化”

案例两位数减一位数的退位减法.

首先教师通过问题情境出示例题“33-8”.然后在学生独立思考后, 教师组织交流算法的过程中, 在教师精心“引导”、一再追问下, 出现了多种算法:

算法一:33-3=30, 30-5=25.

算法二:33-10=23, 23+2=25.

算法三:13-8=5, 20+5=25.

……

老师:小朋友, 真了不起, 想出了这么多种计算的方法, 以后在计算时, 你喜欢用哪种方法就用哪种方法.

反思上述案例反映了在计算教学中老师对算法多样的认识模糊.算法多样化应是一种态度, 是一个过程, 算法多样化不是教学的最终目的, 不能片面追求形式化.老师不必煞费苦心“索要”多样化的算法, 也不必为了体现多样化, 刻意引导学生寻求“低思维层次算法”.即使有时是教材编排的算法, 但在实际教学中学生中没有出现, 即学生已经超越了“低思维层次算法”, 教师可以不再出示, 没有必要走回头路.片面地追求算法的数量, 而忽视算法背后所代表的学生真实的思维状态, 就很容易把学生引入钻牛角尖和生拼硬凑的误区, 对学生的发展是非常不利的.

误区二:把“算法多样化”理解为“一题多解”

案例苏教版第十一册“根据比例尺求图上距离或实际距离”.

教师出示例7:在一幅比例尺为1∶8000的地图上, 明华小学到少年宫的图上距离是5厘米, 实际距离是多少厘米?学生试做.交流汇报的过程中, 学生出现多种算法, 并都说出了自己的解题思路.

方法三:

解:设明华小学到少年宫的实际距离是x厘米.

方法四:

解:设明华小学到少年宫的实际距离是x米.

师:同学们, 对于以上的几种方法你们都理解吗?下面请同学们用刚才所介绍的几种方法来完成下面练习.

反思上述案例中老师显然误把“算法多样化”理解为“一题多解”.“一题多解”追求的是学生个体方法的多样化, 要求学生个体用多种方法解决同一问题;“算法多样化”追求的是学生群体方法的多样化, 是每一名学生经过自己独立的思考和探索, 提出各自的方法, 对某一个体学生而言, 方法可能只有一种, 但对众多学生而言, 方法就呈现出多样化.笔者认为我们不能简单地将“算法多样化”与“一题多解”混为一谈, 提倡算法多样化并非让学生掌握每一种算法, 而是要通过反馈交流、评价沟通, 让学生体验、学习别人的思维活动的成果, 掌握适合自己的一种或几种算法.这样才能呵护学生主体意识、创新意识, 实现“不同的人在数学上得到不同的发展”.

误区三:把“算法的优化”理解为“方法的固定化”

【案例】解决实际问题中, 学生尝试计算“25×12”的积在交流计算方法的过程中, 学生中出现了多种计算方法:

师:同学们真厉害, 一下子就想出了这么多的方法, 在这些方法中, 你最喜欢哪种方法?

生1:我觉得第一种方法简单, 25×2=50, 比较简单.

生2:我喜欢用第二种方法.

生3:第三种方法使用了乘法分配率, 使计算简便.……

师:其实前面四种方法都使用了运算定律, 使计算简便, 但是, 我们在用简便方法计算时, 凑成整百数最简便, 所以运用第二种方法比较好.下面请同学们运用第二种方法来练一练24×25.

生物地理学优化算法 篇9

无线传感器网络WSN由一组传感器节点以自组织方式构成。每个节点兼备路由器和主机两种功能,不仅要执行感知、传输数据等应用任务,还要参与路由发现、维护以及网络构建等任务。WSN中节点一般采用电池供电,节点大部分情况下被布置在无人看守的环境中,电池不能补充和更换,节点能量受限。在这种情况下要延长网络生存时间就必须降低节点工作时能量消耗,试验表明节点能量主要消耗在通信模块上。无线通信中的传输数据的能量消耗与有效半径的2-4次方相关,减小节点的有效传输半径可以降低节点能量消耗。

另外WSN还有着不同于传统无线网络的其他特征:首先WSN中节点数量庞大,传统的以IP地址为基础的路由协议不适合WSN;其次WSN的应用背景主要是多个源节点感知数据,然后将感知数据传给目的节点Sink,不要求建立网络中任意两点之间的路由路径,这给设计高效的路由协议带来了可能性。因此采用合适的、高效的路由协议是降低无线传感器网络整体能耗的关键。这就需要我们设计一个满足需要的高效的路由协议。

1 相关工作

研究工作者们提出了许多的路由算法,比如SPIN[1](基于协商的路由算法)、DD[2](定向扩散协议)、LEACH[3]、TTDD[4](基于虚拟网格的路由协议)、LAR[5](位置辅助路由协议)等路由协议。他们都很好地解决了无线传感器网络的某方面的问题,但也都存在各自的问题。比如SPIN协议中出现了多个节点向同一个节点同时发送REQ的情况,有关的退避机制需要考虑。DD算法不能用于大规模的网络,主要用于具有大量查询而只有少量事件的应用场景,如果网络拓扑结构频繁变动,它的性能将大幅下降。

在WSN中,从源节点到基站或是到基站的某条传输路径一旦确定,就不会频繁改动,这样就会出现由于路径上的传输节点的失效或暂时不可用导致数据包传输失败,为此需要重新更新路由,增大了能耗和传输延迟。为了解决这个问题,研究工作者们提出了多路径路由[6,7]的概念。多路径路由协议通过将数据流分散到多个不同的路径上传送以实现负载的均衡性,在WSN中体现为能量的均衡性,并且可以通过增加冗余路径来提高网络的可靠性。优化增加了网络的可靠性,但同时也增加了网络能耗。

混合蛙跳算法[8]可以实现路由优化的目的,但是传统的混合蛙跳算法不能将可行解中的优良性能很好地保留在青蛙群体中,它的收敛速度也比较慢,这就表明了传统的混合蛙跳算法不适用于能量有限的无线传感器网络中。

针对以上问题,我们提出了一种改进的混合蛙跳算法来全局优化多路径路由。考虑到混合蛙跳算法的计算量大,所需要的资源信息较多,我们将混合蛙跳算法的执行在基站完成。这样就解决了由于建立多路径导致的网络能量浪费,又实现了多路径路由的优点,实现了WSN多路径路由的全局优化。

2 WSN路由优化算法

混合蛙跳算法是一种基于群体智能的生物进化算法。在WSN中,青蛙群体由一群具有相同结构的青蛙组成。整个群体被分为多个族群,每个族群有自己的思想,执行局部优化策略。在局部优化迭代结束后,各个族群之间进行思想交流,实现族群间的混合运算。达到了路由优化的目的。

2.1 网络模型

WSN网络模型假设如下:

1) 所有节点随机均匀地分布在一矩形区域内。且位置已知。

2) 所有节点与基站均保持静止,节点初始能量相同,并无法补充能量。基站的能量无限大。

3) 所有节点均同构,且唯一ID,并具有数据融合功能。

4) 每个节点的传输功率相同,有效通信距离均一样。

将无线传感器网络模型表示为一个有向图G=(V,E),其中V表示所有节点的集合,E表示所有边的集合。令r为节点v∈V的发射范围,L表示相邻节点间的距离。随机生成F只青蛙组成初始群体,每个青蛙个体表示一条源节点到基点的可行路径为U = (U1,U2 ,…,Ud),其中d表示解空间的维数。例如5个传感器节点组成的网络链路如图1所示。

随机生成的初始群体:

U1={S,1,2,BS} U2={S,1,3,2,BS}

U3={S,1,2,4,BS} U4={S,3,2,BS}

U5={S,1,2,3,4,BS} U6={S,4,BS}

U7={S,3,2,4,BS} U8={S,3,1,2,BS}

U9={S,3,4,BS} U10={S,4,3,2,BS}

2.2 算法描述

路由协议的好坏极大地影响整个网络的性能。好的路由协议不仅能够降低整个网络的能量消耗,延长网络生存周期,还能提高网络的稳定性。基于混合蛙跳算法的多路径路由的优化主要考虑了传输数据的能耗和可靠性两方面来全局优化多路径路由。以下为优化算法的具体步骤:

1) 初始化参数

在无线传感器网络中,按一定规则随机生成F只青蛙组成初始群体,计算青蛙个体的适应度f(i)。青蛙个体的适应度函数定义为:

$F(u)=\frac{1}{{\displaystyle \sum _{x\in v}(}D(u,x)\times g(u))+{\displaystyle \sum _{x\in v}(}R(u,x)\times t(u))+W(u)\times t(u)}$

其中D(u,x)表示源节点u在链路(u,x)上分配的数据流量,g(x,u)表示节点u在链路(x,u)上接收单位数据所消耗的能量,R(x,u)表示节点u在链路(x,u)上接收到的数据流量,t(u,x)表示节点u在链路(u,x)上发送单位数据所消耗的能量,W(u)表示感知的数据量。

2) 构造子族群

将生成的青蛙按适应度降序排列划分成m个族群,构造子族群。在随机生成初始群体之后,将青蛙个体按适应度f(i)降序排列存储于X={Ui},i=1,2,…,F,然后按照以下划分原则将整个青蛙群体分成m个族群Y1,Y2,…,Ym,每个族群中包含n只青蛙,满足下列关系:

Yij=X[j+(i-1)×n] i=1,2,…,m j=1,2,…,n

假设m=3,F只青蛙按适应度由高到低排列,位置位于第1 的青蛙分入第1 族群,第2 的青蛙分入第2 族群,第3 的青蛙分入第3 族群,第4的青蛙分入第1 族群,依次类推,将所有青蛙个体划分到3 个族群中。

3) 局部优化

将青蛙种群划分的多个族群进行局部优化。在每一个子族群中,具有最好适应度的可行路径表示为Ub,最差适应度的可行路径表示为Uw 。对每个子族群的局部优化,主要是对Ub和Uw进行交叉替换操作。具体的操作可如下进行:

(1) 在Ub和Uw中查找它们的公共基因,即查看两条路径是否同时经过某个节点,如果存在公共基因表明可以进行交叉。如果没有,则表明这两个个体不能交叉。

(2) 从选中的这个公共基因开始,直到下一个公共基因 (如果两条路径仅有一个相同节点,则取目的节点为下一个公共节点) ,对Uw进行链路交换。

例如: Ub={S,1,3,4, BS}

Uw={S,1,2,4,BS}

节点1、节点4为公共节点,经过交叉后,Ub不变。Uw变为:

Uw={S,1,3,4,BS}

计算交叉后的最差青蛙的适应度f′(w),如果f′(w)大于交叉前最差青蛙的适应度f(w),则交叉成功,否则交叉失败。如果交叉失败,再选用全局最优青蛙与最差青蛙进行交叉替换。交叉后判断交叉前后的最差青蛙的适应度,如果f′(w)大于f(w),则交叉完成,否则随机产生一个新的青蛙代替原来的最差的青蛙,交叉结束。

(3) 交叉后再对子族群中的所有的青蛙进行变异。每一个青蛙都以固定的概率p进行变异,大量实验表明p的值取0.02比较理想。子族群中的最优青蛙Ub也可能变异,为了防止变异后的Ub变得比原来的适应度差,如果变异后的Ub的适应度f′(b)大于变异前的适应度f(b),则发生变异,否则不进行变异。

4) 全局优化

所有子族群经过一定次数的局部优化后,将所有族群的青蛙混合在一起,重新计算适应度f(i),按适应度f(i)降序排列,重新划分族群,再进行局部优化,如此循环直到满足收敛条件为止。

2.3 算法分析

随机生成青蛙种群的时候,在可行路径中的节点的选择时,加入了节点的剩余能量的考虑。剩余能量越大的节点被选中的概率越大。概率q=E1/E2,E1表示节点的剩余能量,E2表示节点的初始能量。剩余能量的考虑缓解了部分节点因大量使用而死亡的问题。

改进的混合蛙跳算法改进了子族群青蛙局部优化方法,主要是对子族群中青蛙进行交叉变异操作,对子族群中最优青蛙和最差青蛙的交叉操作,考虑了多种情况,避免了局部早熟。随后进行概率变异操作,变异中如果最优的青蛙如果发生变异,要进行比对。这样不仅保证了青蛙个体的多样性,而且保留了青蛙的优良性,缩短了找到全局最优解的时间。

在每次的优化后保存最优的青蛙和次优的青蛙。采用这样的多路径路由可获得比单路路由更好的网络吞吐率和可伸缩性。如果最优路径中的某一个或几个节点的剩余能量很低,并且下一轮的路由更新还没开始,最优路径就不能传输数据。多路径路由就可以只使用次优的路径进行传输,保证了网络的流通,增加了网络的可靠性。

3 算法实现和实验仿真

3.1 算法流程

1) 基站收集网络初始信息。得到网络各个节点的邻居矩阵N和感知数据集合{W(u)|u∈V}。

2) 对网络节点ID编码并初始化青蛙群体。

3) 依据青蛙适应度划分生成青蛙种群。

4) 针对子族群中最优青蛙和最差青蛙进行选择替换操作,然后子群青蛙按概率0.02进行变异。

5) 混合子族群,再重复3)、4)操作;直到满足收敛条件为止。

6) 输出青蛙种群中适应度最优和次优的青蛙作为问题的满意解。

3.2 实验仿真

在下面的实验中,通过仿真网络中节点的通信和节点的能量消耗,主要从网络能量消耗方面进行了实验分析。

基本参数设定

网络的负荷根据控制系统的一般要求设置为:周期性发送和感知数据,各节点的发送数据周期为0.01 s～0.10 s,感知数据周期为0.1 s～0.5 s。青蛙更新迭代次数IT=10。定义网络生存周期为网络从运行开始到网络中死亡节点的百分数低于原来总节点数的50%时所持续的时间。

选择经典的传感网络路由算法定向扩散(DD) 算法作为比较对象。在同一环境下分别对混合蛙跳算法和DD算法的网络生存周期进行仿真测试。仿真结果如图2所示。

从图2中可以看出,采用改进的混合蛙跳算法的WSN路由优化算法具有更长的网络生存周期,并且随着感知数据量的增大,网络生存周期延长的效果越明显。说明混合蛙跳算法对于大数据量的全局优化更加突出。

4 结 语

本文在分析了现有的混合蛙跳算法的基础上,结合无线传感器网络的特点,提出了一种适合于无线传感器网络的路由优化算法。改进的混合蛙跳路由优化算法考虑到了节点的剩余能量,并且复杂的优化计算问题由能源充足、计算和存储能力强大的基站解决,平衡了节点能量负载,节省了能量消耗。仿真实验表明,相比DD算法,新算法均衡了网络能量消耗,有效地提高了网络生存周期,改善了网络性能。

参考文献

[1]WHeinzelman,J Kulik,HBalakrishnan.Adaptive Protocols for Infor-mation Dissemination in Wireless Sensor Networks[C]//Proc.5thACM/IEEE Mobicom,Seattle,WA,Aug 1999:174-85.

[2]C Intanagonwiwat,R Govindan,D Estrin.Directed Diffusion:a Scala-ble and Robust Communication Paradigm for Sensor Networks[C]//Proc.ACMMobi-Com2000,Boston,MA,2000:56-57.

[3]Heinzelman W,Chandrakasan A,Balakrishman H.Energy efficientcommunication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Hawaii International Conference on Systern Sciences.Maui:IEEE Computer.

[4]HLuo,Fan YE,J Cheng,et al.TTDD:A Two-tier Data DisseminationModel for Largescale Wireless Sensor Networks[J].Wireless Net-works,2005,11(2):161-175.

[5]Young-Bae Ko,Nitin H Vaidya.Location-Aided Routing(LAR)inmobile ad hoc networks[J].ACM/Baltzer Wireless Networks(WI-NET)Journal,2000,6(4):307-321.

[6]Lees J,Gerlam.Sp litmultipath routing with maximally disjoint paths inAd Hoc networks[EB/OL].[2008-06-18].http://www.hp l.hp.com/personal/Sung-Ju_Lee/abstracts/papers/icc2001b.pdf.

[7]周集良,李彩霞,曹奇英.基于遗传算法的WSNs多路径路由优化[J].计算机应用,2009(2):521-524.