优化蚁群算法在网络知识路由系统中的应用

摘要： 研究网络知识路由问题，提高网络资源搜索质量。针对传统方法在网络资源搜索过程中，存在搜索时间长，得不到最优解，导致搜索速度慢，效率低的问题。为了提高网络资源搜索效率，提出一种基于改进蚁群的路径搜索算法，在混合信息素更新策略，自适应挥发因子等方面进行改进，并设置了先行蚂蚁和后行蚂蚁。该方法有效地避免了蚁群搜索陷入局部最优，加快了收敛，提高了搜索效率。仿真结果表明，改进方法缩短了搜索时间，网络资源搜索效率明显提高，证明是一种有效的优化方法，能够在最短时间找到资源搜索的最优解，是解决网络资源搜索优化问题的有效算法。

关键字：蚁群算法；知识路由；混合信息素；自适应调整；仿真

中图法分类号： TP391 文献标识码： A

Application of ant colony optimization algorithm to knowledge routing system

WEI Xing

（ Department of Scientific Research，Guilin University of Aerospace Technology，Guilin Guangxi 541004，China）

ABSTRACT：Knowledge routing system are studied to improve the quality of network resources. In the course of the search network resources， the traditional method takes a long time and could not get the global optimal solution， resulting in slow search speed and low efficiency problems. In order to improve search efficiency of network resources， the paper puts forward a path search algorithm based on improved ant colony optimization， focusing on improving hybrid pheromone update strategy， adaptive volatile factor， etc， meanwhile setting the first ants and after ants. The improved ant colony could effectively avoid falling into local optimum， speed up the convergence and increase the search efficiency. Simulation results show that the improved method which is an effective optimization method， could shorten the search time and improve the search efficiency of network resources， and find the optimal solution in the shortest time. Therefore it could be proved that the proposed algorithm is an optimization solution algorithm in the problem of network resources.

KEYWORDS：ACO； knowledge routing； hybrid pheromone； adaptive adjustment； simulation

0 引言

随着现代信息技术的发展，网络中的信息资源也越加丰富，如何在其中依据用户需求快速而准确地找到目标信息资源，即已成为目前亟待解决的研究问题。

蚁群算法是一种群智能算法，具体是由意大利学者DORIGO[1-2]等人通过研究自然界中蚁群寻找食物过程中发现路径的过程而形成的一种进化算法。目前，蚁群算法主要用于解决常见的复杂组合优化问题，比如：TSP问题（Traveling Salesman Problem）、路径规划问题（Vehicle Routing Problem）等。算法表现出了多样性、正反馈和具有强大全局搜索能力等特点，但是，蚁群算法也同样存在这计算开销数值偏高、而且容易陷入局部最优等不足。

基于此，为提高蚁群算法的效率和搜索能力，本文设计提出一种基于改进蚁群的路径搜索算法，该算法在混合信息素更新策略，自适应挥发因子等方面研究生成改进，并设置了先行蚂蚁和后行蚂蚁，运用于网络知识路由问题中，有效地避免了蚁群搜索陷入局部最优， 加快了收敛速度。同时也提高了搜索效率。仿真实验验证了改进算法的有效性和优越性。

1 语义Web与知识路由的概念

语义Web由Berners-Lee于2001年首次公布推出[3]，其基本思想是提供基于机器可处理的语义元数据，并进行自动化的信息访问，协助人们在Web上发现知识、处理事务。而知识路由[4]的形成则来自语义Web，重点是协同运用依据用户的请求，网络信息相关性及语义信息，通过搜索准确快速地发现用户需要的目标知识。

2 蚁群算法描述

蚁群算法是在离散状态下，将算法中的解抽象成初始状态到目标状态的转移序列，其最优解就是转移序列中的最优值。蚁群中的每只蚂蚁可利用其路径上的信息素强度执行状态转移，一次搜索结束后，将即时更新信息素强度，由此群体就完成一次搜索；然后不断循环，蚂蚁间也将继续展开交流和协作，最后，得到强度最大的路径就是最优转移序列，即算法最优解。

蚁群算法的数学模型如下[5]：

首先，设蚂蚁数量为m，蚂蚁个体k在运动时的移动方向取决于各路径上的信息量浓度； 为蚂蚁k已走过的所有城市集合，且可以随着蚂蚁运动而动态调整；城市i和城市j之间的距离为 ； t 时刻ij路径上的信息素浓度为 ； 为信息启发式因子，反映了路径上的信息重要性，其值越大，蚂蚁间的协作性越强； 为期望启发式因子； 为蚂蚁k所经过的集合。算法开始时，m只蚂蚁被随机地放置在平面中，各路径上的初始信息素浓度是一致的。那么在t时刻，蚂蚁k从城市i转移到城市j的概率 为：

为了避免蚂蚁运动过程中在路上残留过多的信息素而使启发信息被淹没，当每只蚂蚁遍历完成后，需要对残留信息进行信息素更新处理。由于更新策略不同，DORIGO为此提出了“蚁周模型”（Ant-Cycle）、“蚁量模型”（Ant-Quantity）及“蚁密模型”（Ant-Density）等3种模型。具体实现可分做如下描述：

5 结束语

本文针对网络知识路由系统中资源搜索存在的问题， 对基本蚁群算法开展了研究改进，提出了混合信息素更新策略，自适应挥发因子等改进方法，设置了先行蚂蚁和后行蚂蚁，有效地改善了基本算法存在收敛速度慢等缺陷。仿真实验说明本文的改进算法能快速、有效、准确地搜索到网络资源，是一种性能上更加优越的实用算法。

参考文献：

[1] DORIGO M， VITTORIO M， ALBERTO C. The ant system： Optimization by a colony of cooperating agents [J]. IEEE Transactions on Systems， Man， and Cybernetics-Part B， 1996， 26（1）： 1-13.

[2] DORIGO M， GAMBARDELLA L M. Ant colony system： A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.

[3]Berners-Lee T， Connolly D， Swick R R. Web Architecture： Describing and Exchanging Data[EB/OL].[1999-06-07]. http：//www.w3.org/1999/04/WebData.html.

[4] 李英杰，王莉，余雪丽. 本体驱动的知晓内容和上下文的知识路由研究[J].计算机工程与应用，2006，（22）：150-154.

[5] 魏星，李志远，陈艳. 基于蚁群和鱼群的混合优化光网络动态RWA算法[J].光通信技术，2015，3（3）：47-49.