智能计算在网络优化中的应用

Digital Communication World - - Technology Study -

纪 喆(青岛西海岸新区胶南第一高级中学,青岛 266400)

摘要:本文首先对最优化方法和智能计算及其研究现状作了简单介绍;然后阐述了人工鱼群算法及人工鱼群算法在路

由优化中的应用;最后对智能优化算法进行了总结和展望。

关键词:智能优化算法;最优化技术;人工鱼群算法d o I:10.3969/J.ISSN.1672-7274.2017.09.006

中图分类号:TN915 文献标示码:B 文章编码:1672-7274(2017)09-0015-02

1 引言

智能计算就是借用自然界生物界规律的启迪根据其原理模仿设计求解问题的算法,目前,人们已提出了三十多种神经网络模型,这些模型都是从神经元、神经网络的状态、传播规则、活跃规则、输出函数、学习算法、互连模式、环境、稳定状态、操作模式等十个方面来进行描述。按照学习算法支待的操作类型分类,则学习算法至少可以分为自联想器、模式联想器、模式分类器和正则探测器四类。

2 基于改进的人工鱼群算法的路由优化

2.1 人工鱼群算法的基本概念

人工鱼群算法是李晓磊等人于2002年提出的一种基于动物自治体的优化方法,是集群智能思想的一个具体应用,该算法根据水域中鱼生存数目最多的地方就是本水域中富含营养物质最多的地方这一特点来模拟鱼群的觅食行为而实现寻优。它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工鱼个体的局部寻优行为,最终在群体中使全局最优值突现出来,有着较快的收敛速度。

人工鱼群算法主要利用鱼的三大基本行为:觅食、聚群和追尾行为,采用自上而下的寻优模式从构造个体的底层行为开始,通过鱼群中各个体的局部寻优,达到全局最优值在群体中凸显出来的目的。

(1)觅食行为:这是鱼趋向食物的一种活动,一般认为它是通过视觉或味觉来感知水中的食物两或食物浓度来选择行动的方向。

(2)聚群行为:大量或少量的鱼聚集成群,进行集体觅食和躲避敌害,这是它们在进化过程中形成的一种生存方式。

(3 )追尾行为:当某一条鱼或几条鱼发现食物时,它们附近的鱼会尾随而来,导致更远处的鱼 也会尾随过来。

人工鱼群算法就是通过模拟鱼类的觅食、聚群、追尾等行为在搜索域中进行寻优的。

2.2 人工鱼群算法的行为描述

(1)觅食行为:设置人工鱼当前状态,并在其

感知范围内随机选择另一个状态,如果得到的状态的目标函数大于当前的状态,则向新选择得到的状态靠近一步,反之,重新选取新状态,判断是否满足条件,选择次数达到一定数量后,如果仍然不满

足条件,则随机移动一步[6]。

(2)聚群行为:人工鱼探索当前邻居内的伙伴

数量,并计算伙伴的中心位置,然后把新得到的中心位置的目标函数与当前位置的目标函数相比较,如果中心位置的目标函数优于当前位置的目标函数并且不是很拥挤,则当前位置向中心位置移动一

步,否则执行觅食行为[6]。

(3)追尾行为:人工鱼探索周围邻居鱼的最优

位置,当最优位置的目标函数值大于当前位置的目标函数值并且不是很拥挤,则当前位置向最优邻居

鱼移动一步,否则执行觅食[6]。

根据所要解决的问题性质,对人工鱼当前所处的环境进行评价,从而选择一种行为。较常用的评估方法是:选择各行为中使得向最优方向前进最大的方向,也就是各行为中使得人工鱼的下一步状态最优的行为,如果没有能使下一个状态优于当前状态的行为,则采用随机行为。

2.3 人工鱼群算法步骤

⊙ 设定鱼群的参数,包括鱼群的规模m,最大迭代次数gen,人工鱼的感知范围visual,最大移动步长step,拥挤度因子d等。

⊙ 在参数区间内随机生成m条人工鱼个体作

为初始鱼群。⊙ 计算每条鱼的食物浓度函数(目标函数),

把最优的值放入公告板[7]中。

⊙ 对于每条人工鱼执行以下操作:计算出追尾行为、聚群行为的值,采用行为选择策略,选择最优的行为作为鱼的移动方向,缺省行为是觅食行为。计算出每条鱼的食物浓度函数(目标函数),其最优值与公告板中的值进行比较,最终公告板中始终保持最优的值。⊙ 判断是否满足结束条件,如果满足结束,否

则转上一步。最终公告板中的值就是最优值。

2.4 基于人工鱼群算法的路由优化

2.4.1 禁忌表和藐视准则

算法中禁忌表的表项表达为一条人工鱼,表的深度依求解问题的复杂度而定,若禁忌表已满,则按先进先出的原则更新表项,禁忌长度设为定值。需要指出的是,由于当前的禁忌对象对应状态的适配值可能很好,因此在算法中设置判断,若禁忌对

象对应的适配值优于当前最优解("best so far")状

态,则无视其禁忌属性而仍采纳其为当前选择,也就是通常所说的藐视准则。

2.4.2 禁忌计算

设人工鱼Xi和Xj ,新的人工鱼的产生按如下禁忌计算方法进行:

Xnew=xi+ η(xi-xj)其中,η∈[0,1]是预设概率值,"-"运算完成对Xi和Xj的比较,"+"运算完成xj对Xi的置换操作,即:解Xj和解xi中不同分量以η

的概率发生置换操作,而相同分量保持不变。人工鱼个体之间的距离,即两个解之间的距离定义为:

d(i,j)=xi-xj。

2.4.3 仿真实现与性能评价

基于NS2平台进行了仿真实现,在多个实际与

虚拟的网络拓扑上对本文所描述的算法;基于粒子

群和遗传算法的QOS组播路由算法和基于遗传算法的QOS组播路由算法,进行仿真实验与性能评价。

2.4.4 满足用户QOS约束的概率的比较

设定多次组播请求,每次请求的源节点和组播目的节点随机产生,其他参数不变,运行三种算法,以可用带宽和延迟为例,分别统计三种算法所得到的最优组播树的可用带宽和延迟满足用户 QOS要求的概率与进化代数的关系,仿真结果表明,TAFQM算法和PGAQM算法均能较快的找到可用带宽和延迟满足用户QOS约束概率较大的组

播树, TAFQM算法的收敛速度优于另外两种算法。总体上讲,三种算法经过30次左右的迭代,满足用户QOS约束的概率已达95%以上。

2.5 进一步的研究工作

作为一个前沿性的热点研究领域,人工鱼群算法已引起越来越多国内研究者的关注,但因人工鱼群算法(AFSA)起步较晚,与遗传算法、神经网

络、蚁群算法、粒子群算法和免疫算法相比,人工鱼群算法理论还不完善、不成熟,研究处于初步阶段,在今后的工作中,还有很多方面有待进一步的探索和研究:

(1)人工鱼群算法的理论研究。人工鱼群算法的理论研究还存在许多问题需要进一步解决,比如初始化参数选择问题、收敛速度问题等,这些均带有经验性和直觉性,至今没有经过严格的数学论证。今后人工鱼群算法的收敛性证明和理论分析仍然是一个非常具有挑战性的研究方向。

(2)人工鱼群算法的改进研究。人工鱼群算法

因处于初步阶段,因此,其算法的改进仍是目前研究的一大重要方向。根据目前的研究可知,对人工鱼群算法在初始化、参数与其他方法的结合和群体多样化方面的改进仍需积极探索与完善。特别是研究人工鱼群算法与其他智能算法和的融合技术,能够提高算法优化性能,因此,研究人工鱼群算法与模拟退火算法、遗传算法、粒子群算法、蚁群算法等智能优化算法的融合技术,对智能算法的研究具有重要意义。

3 结束语

本文对智能计算的一种算法——人工鱼群算法进行了系统的介绍,并将它应用到路由优化中。对网络管理中的过程进行动态路由选择,提供了新的方法,同时对算法的性能进行了评价。■

参考文献

[1]李晓磊.一种新型的智能优化方法-人工鱼群算法[D].杭州:浙江大

学,2003

[2]丁建立,陈增强,袁著祉.智能仿生算法及其网络优化中的应用研究

进展[J].计算机工程与应用;2003.12

[3]单晓娟.智能计算及其在网络优化中的应用[D].山东大学,2007

[4]王联国,洪毅,赵付青.一种改进的人工鱼群算法[J].计算机工程,

2008, 34 (19) :192-19

Newspapers in Chinese (Simplified)

Newspapers from China

© PressReader. All rights reserved.