基于改进人工鱼群算法的光网络最优环路径搜索研究*

魏 星

(桂林航天工业学院科技处 桂林 541004)

基于改进人工鱼群算法的光网络最优环路径搜索研究*

魏 星

(桂林航天工业学院科技处 桂林 541004)

针对环路由搜索存在的问题,为提高环形光网络利用率,提出了一种改进人工鱼群算法用于解决光网络最优环路径搜索问题。探索了鱼群聚群行为、移动步长等改进策略,加快了算法收敛速度,提高了算法的精度和效率。最后,以20个光节点的环形网络为例,重点研究了改进的人工鱼群算法进行环路由搜索、设备选型、系统设计及管理等内容,提高了光网络效率,节省了光网络建设成本。

光网络; 改进的人工鱼群算法; 最优环路径; 光损耗

1 引言

在光网络的组织结构中,环形光网络具有链路结构简单、网络自愈能力强和网络利用率高等优点,因此,它被作为一种重要的拓扑形式广泛应用于智能光网络中。目前,路由与波长分配的优化问题是智能光网络中面临的关键问题之一,而在环形光网络中,最优环路由搜索就是在网络中找到一条路径从某个起点出发,经过网络中所有节点,最后回到起点,并且要求环路长度最短,从而实现光网络的节点设备、光缆线路的最优配置方案。研究最优环路由搜索问题,对于提高环形光网络传输效率,节省网络建设成本有着重要的意义[1～3]。

环路由搜索问题是一个非确定性多项式(NP-hard)问题,对于规模较小的问题一般采用精确算法求解,但是算法的求解时间较长,因此,在求解这类问题时,采用智能式启发算法会取得较好的效果。目前,蚁群算法、人工鱼群算法等智能算法已经成为求解环路由搜索问题的主要方法。

人工鱼群算法[4～5](AFSA)最早由李晓磊博士于2003年提出,该算法通过模拟鱼群的觅食、聚群、追尾等各种行为,具有初始值要求不高,前期收敛速度快,鲁棒性较强等特点,被广泛应用于解决各类组合优化问题。但是,鱼群算法也存在后期收敛速度慢,算法结果精度不高等缺点,因此,本文对基本鱼群算法进行了改进,改进了鱼群聚群行为、移动步长等新思想,使之适用于环路由搜索问题,最后通过仿真实验表明了改进人工鱼群算法具有收敛速度快、结果不精确等特点。

2 鱼群算法及行为描述[6]

在一片水域中,鱼聚集数目最多的地方一般就是本水域中营养最为丰富的地方,鱼群算法就是基于这个特点来模仿鱼群觅食等行为,从而实现全局寻优,这就是鱼群算法的基本思想[6]。

鱼群在觅食过程中主要有几个基本行为,即:觅食、聚群、追尾和随机等行为。人工鱼群算法就是利用鱼群的基本行为,从鱼群的底层个体出发,通过个体的局部寻优,最终达到全局最优的目的。下面就几个基本行为进行描述。

1) 觅食行为:这是鱼循着食物多的方向游动的一种行为,是一种向较优方向迭代寻优的方式。其描述为:首先,比较目前状态的函数与其感知范围内状态随机函数的大小,如果随机函数更大,则向新状态靠近一步,反之,重新选取新状态,判断条件;当选择次数达到一定值后,仍不满足条件,则随机选择状态。

2) 聚群行为:鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群,这种行为能保证鱼群伙伴间不会过于拥挤,鱼群移动方向大致相同。其描述为:人工鱼搜索当前相邻的伙伴数目,计算其中心位置的函数,并比较中心函数与目前的状态函数,如中心函数更优且拥挤度不高,则向中心位置靠近一步,反之进行觅食行为。

3) 追尾行为:当鱼群中有个体鱼发现了食物,其附近的鱼会尾随而来,快速到达食物区域。其描述为:比较当前鱼范围内的所有状态函数,找出范围内最大目标函数,且其位置拥挤度较低,则向其位置移动一步,进行追尾行为;反之,进行觅食行为。

4) 随机行为:鱼在水中为了在更大范围内搜寻食物或伙伴进行的一种随机的游动行为。

3 人工鱼群算法的改进

鱼群算法的数学模型描述如下[9～11]:人工鱼个体的状态为向量Xi=(x1,x2,…,xn),其中:xi(i=1,2,…,n)为鱼群个体变量;用Y=f(x)表示人工鱼当前位置食物浓度;个体间的距离和感知距离分别为dij=‖Xi-Xj‖和Visual;Step为移动步长:δ为拥挤度因子,try_number为尝试次数,Rand()为(0,1)之间的随机数。其具体觅食过程中的觅食、聚群、追尾和随机等几个基本行为的数学模型可参见文献[2]中的详细描述,本文在此不再重复描述。

基本鱼群算法是一种随机群智能算法,也存在收敛速度慢、效率不高等不足,本文改进了鱼群的聚群行为,并讨论移动步长的改进方法,使之更好运用于光网络最短的求解问题。

1) 聚群行为的改进

在鱼群算法中,聚群行为能够很好地跳出局部极值,并尽可能搜索到其它的极值,最终搜索到全局极值,通过改进聚群行为达到提高鱼群的收敛效率的目的。

具体描述为:当前人工鱼Xi邻域内人工鱼数目为nf,中心位置状态用Xc表示,当Yc/nf>δYi,说明中心位置食物浓度较高,且拥挤度较低,则人工鱼向中心位置移动一步,进行聚群行为;反之,进行觅食行为。在人工鱼向食物浓度较高的中心位置状态Xc移动过程中,如果在其感知范围内发现有另一个状态Xv的食物浓度大于Xc,这时,人工鱼便放弃向中心位置状态Xc的移动,转向目前食物浓度更高的状态Xv,即Xi/next=Xv。

通过以上的聚群行为改进,人工鱼能动态地调整移动方向,能实时地朝着食物浓度更大的状态移动,从而节省了搜索时间,提高了搜索精度及效率。

2) 步长改进策略

在原始鱼群算法中,采用随机步长的方式,移动步长Rand()Step为随机数。随机移动扩大了寻优范围,但是导致鱼群的随机性增加,收敛速度下降;如果采用固定步长,步长越大,收敛速度越快,但是,达到一定数值后,步长过大,会出现震荡现象,收敛速度会减慢。所以,在实际的优化问题中,可以考虑采用合适的固定步长或变尺度方法来提高算法收敛。

因此,本文做如下改进:

在觅食行为中,人工鱼Xi与其感知内的任意人工鱼Xj的状态关系为

Xj=Xi+Rand()·Visual

当前人工鱼Xi的食物浓度为Yi,其感知内的任意人工鱼Xj的食物浓度Yj,即Yi

(1)

反之,重新选择Xj;则按式(2)移动一步:

(2)

其中:Rand()为(0,1)之间的随机数。

4 组网实例

在实际应用中,光网络的路由通信会受到多种条件的限制,比如:山川、河流等地域特点,在工程中,光缆路由的设计一般都是通过工程师依据传统设计经验和用户需求通过人工绘图、计算来实现的,但是,这种方式缺乏可靠的理论依据,设计的路由不一定是最优的,成本也不一定最低。因此,本文选用20个节点的环网的路由优化来演示工程应用,主要采用智能算法来设计20个节点的光网络路由,求得最短路径,节省网络建设费用。

4.1 优化设计

环形光网络自愈能力强,当网络出现故障时,能够在极短的时间自动恢复中断的业务。在仿真实验中,采用单纤环连接环路中20个节点,在环网光网络的保护时,采用以复用段为基础的链路倒换(也称光复用段倒换)方式,其环形保护结构使用光复用段共享保护环(OMS-SPRING),系统采用光交叉连接和光分插复用设备,具有系统容量大、升级改造简单等特点,其对于的路由算法有很多,下面我们就采用改进的人工鱼群算法来进行路由求解。

4.2 用改进人工鱼群算法求最短路径

本实验中,利用文献[7]中的仿真环境,在网路平面中随机产生的20个光节点,节点的坐标如表1所示。

表1 随机的20个光节点坐标值表

随机的20个节点的初始位置如图1所示。

图1 随机的20个节点坐标图

人工鱼群算法的各个参数设置如下[8]:其中人工鱼群中的参数Trynumber=50,Visual0=2.5,δ=2,L=30,鱼群种群数量N=30。

通过本文改进的人工鱼群算法的计算,得到光网络中20个节点最优环路径搜索结果如图2所示。

图2 20个节点最优环路径图

本文改进的人工鱼群算法仿真搜索到的最优路径环如下:

1→10→14→8→9→19→12→6→11→7→2→3→16→13→20→17→4→18→5→15→1

最优路径总长度为283.936km。通过分析,可以得知,一方面,由于本文算法对鱼群的聚群行为进行了改进,人工鱼能动态地、实时地朝着食物浓度更大的状态移动,提高了搜索效率,并最终达到全局最优;另一方面,在算法中后期,改进了步长策略,使之按感知区域内食物浓度的变化进行觅食行为,提高了局部搜索能力,减少了随机搜索。因此,本文方法适用于实际的光网络最短路径的求解应用。

4.3 设备的选型

在实际的工程中,可选用华为技术有限公司OptiX OSN 3500智能光传输设备进行组网,该设备是华为公司根据城域网现状及发展趋势,开发的新一代智能光传输设备,融合SDH(Synchronous Digital Hierarchy)、Ethernet、PDH(Plesiochronous Digital Hierarchy)等技术,实现了在同一个平台上高效地传送语音和数据业务;一个机柜可以安装2个OptiX OSN 3500子架,其采用双层子架结构,分为出线板区、风扇区、插板区和走纤区。

OptiX OSN 3500可以实现线性复用段保护、复用段保护环,并且支持环网间互通业务的保护,对保护方式互异的环网(如:SNCP和MSP环网)间的互通业务也能够提供保护,被广泛应用于光网络组网中。因此,本工程采用该设备连接环路中20个节点,组成环形光网络。

4.4 系统设计

1) 光纤参数。本工程选用G.655光纤在光缆上,衰减系数为0.22dB/km,而G.655光纤1530～1560nm波长区色散为1.0～6ps/nm.km,传输相同的10Gb/s系统时,因色散很低,因此,不需要色散补偿。

2) 其他光器件参数。本工程中光波长转发器的插入损耗为2dB,光分插复用器和光选择器的插入损耗分别为6.5dB、5dB。

3) 光节点间的损耗计算。基于前文的求解计算,得到了20个节点的最短路径,节点间的损耗按厂家提供的参数进行。

光损耗=实际距离(km)*光纤衰耗系数(dB/km)+接头衰耗(0.5dB×2)。

比如:节点1到节点10的光损耗计算:

A1-10=17.692km×0.22dB/km+0.5dB×2=4.892dB

节点20到节点17的光损耗计算:

A20-17=7.000km×0.22dB/km+0.5dB×2=2.540dB

同理,其他节点间的光损耗如表2所示。

表2 最短路径距离及损耗表

4.5 系统管理

工程由OptiX OSN 3500架构后,采用系统自带的iManager系列的网络管理系统进行统一管理。网络管理系统通过Qx接口或MML接口,实现对整个光传输系统的配置、故障、安全等方面的管理、维护及测试。提高了网络服务质量、降低了维护成本,保证网络资源的合理使用。

5 结语

本文针对传统光缆路由的组织以人工计算、绘图决策等问题进行改善,研究了环形光网络路由搜索问题,对基本鱼群算法进行了改进,提出了鱼群感知距离自适应、移动步长自适应等方法,并将改进鱼群算法应用于具体环形光网络组建实例中,计算了最短路径,研究了设备选型,系统损耗计算及网络管理,结果表明,本文的方法在解决环路由搜索等优化问题中具有较好的效果。

[1] 罗芳琼,侯睿.混合蚁群算法在光网络最优环路径搜索中的应用[J].光通信研究,2014,6(3):8-10,23. LUO Fangqiong, HOU Rui. Study on optimum ring path search based on hybrid ant colony algorithm in optical networks[J]. Study on Optical Communications,2014,6(3):8-10,23.

[2] 尹珊.灵活光网络中的资源优化[D].北京:北京邮电大学,2014. YIN Shan. Resource optimization in flexible optical WDM networks[D]. Beijing: Beijing University of Posts and Telecommunications,2014.

[3] 刘焕淋,李瑞艳,孔德谦.基于多目标遗传算法优化弹性光网络的多路径保护机制[J].电子与信息学报,2016,6(6):1-7. LIU Huanlin, LI Ruiyan, KONG Deqian. Optimization Survivable Multipath Provisioning Based on Multiobjectives Genetic Algorithm for Elastic Optical Networks[J]. Journal of Electronics & Information Technology,2016,6(6):1-7.

[4] 李晓磊.一种新型的智能优化算法——人工鱼群算法[D].杭州:浙江大学,2003. LI Xiaolei. A New Intelligent Optimization Method-Artificial Fish School Algorithm[D]. Hangzhou: Zhejiang University,2003.

[5] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式鱼群算法[J].系统工程理论与实践,2002,22(11):32-38. LI Xiaolei, SHAO Zhijiang, QIAN Jixin. An Optimizing Method Based on Autonomous Animats: Fish-swarm Algorithm[J]. Systems Engineering-theory & Practice,2002,22(11):32-38.

[6] 王闯.人工鱼群算法的分析及改进[D].大连:大连海事大学,2008. WANG Chuang. The analysis and improvement of artificial fish-swarm Algorithm[D]. Dalian: Dalian Maritime University,2008.

[7] 魏星,李志远,汪其.基于蚁群和粒子群的混合光网络路由优化算法[J].桂林航天工业学院学报,2015,80(4):467-470. WEI Xing, LI Zhiyuan, WANG Qi. Hybrid optimization algorithm based on ant colony and particle swarm for routing in optical network[J]. Journal of Guilin University of Aerospace Technology,2015,80(4):467-470.

[8] 魏星,李志远,陈艳.基于蚁群和鱼群的混合优化光网络动态RWA算法[J].光通信技术,2015,3(3):47-49. WEI Xing, LI Zhiyuan, CHEN Yan. Hybrid optimization algorithm based on ant colony and fish school for dynamic routing and wavelength assignment in optical network[J]. Optical Communication Technology,2015,3(3):47-49.

[9] 王谦,吴启武,姜灵芝.基于人工鱼群优化的光网络攻击感知路由算法[J].光通信研究,2014,12(6):15-18. WANG Qian, WU Qiwu, JIANG Lingzhi. An attack-aware routing algorithm for optical networks based on artificial fish swarm optimization[J]. Study on Optical Communications,2014,12(6):15-18.

[10] 王会颖,章义刚.求解聚类问题的改进人工鱼群算法[J].计算机技术与发展,2010,20(3):84-87. WANG Huiying, ZHANG Yigang. An improve artificial fish swarm algorithm of solving clustering analysis problem[J]. Computer Technology and Development,2010,20(3):84-87.

[11] 喻俊松,王琪,徐蓉瑞.基于改进人工鱼群算法的无人机路径规划[J].弹箭与制导学报,2015,6(3):37-40. YU Junsong, WANG Qi, XU Rongrui. UAV Path Planning Based on Improved Artificial Fish-swarm Algorithm[J]. Journal of Projectiles, Rockets, Missiles and Guidance,2015,6(3):37-40.

Optimum Ring Path Search Based on Improved Artificial Fish Swarm Algorithm in Optical Network

WEI Xing

(Department of Scientific Research, Guilin University of Aerospace Technology, Guilin 541004)

In allusion to the problem about optimal ring path in optical network. in order to improve the use ratio of ring optical network, a kind of method about optimum ring path is put forward based on improved artificial fish swarm algorithm. The improve strategy of the cluster behavior step and length of the fish and so on are studied, the method can accelerate speed of algorithm constriction, and improve the accuracy and efficiency of algorithm. Finally, with 20 nodes light ring network as an example, optimum ring path search is studied based on improved artificial fish swarm algorithm, equipment selection, system design and management, the efficiency of optical network is increased, the development digression of optical network is cut down.

optical network, improved artificial fish swarm algorithm, the optimum ring path, optical loss Class Number TP391

2016年10月9日,

2016年11月17日

广西自然科学基金(编号:2014GXNSFBA118286);广西优秀中青年骨干教师培养工程;2015年国家级大学生创新创业训练计划项目资助。

魏星,男,硕士,副教授,研究方向:智能算法,计算机应用。

TP391

10.3969/j.issn.1672-9722.2017.04.012