【作者】 吕勇；

【导师】 赵光宙；

【作者基本信息】 浙江大学 ， 电气工程， 2005， 博士

【摘要】 蚂蚁具有找到蚁穴与食物源之间最短路径的能力,受此启发提出的蚁群算法最初用于解决旅行商问题,具有自适应性、鲁棒性及本质上的并行性等许多特点,广泛适用于各种静态和动态的组合优化问题中,具有潜在的应用前景。 由Dorigo等提出的蚁群算法的描述可知,在通用启发式蚁群算法的起始阶段,信息素值被初始化为统一的值,对解的搜索没有指导意义,启发值此时反而能够提供有用的局部信息,有助于算法的快速收敛。随着算法的进行,根据搜索到的不同路径而更新的信息素值,存储了解空间的全局最优解信息,相对于启发值而言,所起的作用不断提高。因此设计了一种自适应的启发值因子,能够随着算法的进行调整信息素值和启发值之间的相对权重,加速算法的收敛速度。 网络路由问题所具有的一些特征,如内部信息、分布计算、随机动态,以及异步的网络状态更新等,与蚁群优化算法的特征匹配得很好,能很好地解决这一问题。本论文的另一个主要研究成果就是在蚁群优化的基础上,提出了新的路由算法。这种算法具有本质上的可扩展性,能有效解决大型通信网络资源的分配问题。整个算法应用概率选择数据包转发的路径,能够充分利用多条可行路径,从而提高网络负载的均衡性、鲁棒性、负载流量以及网络的利用率。 本文以基于图论的蚁群算法为基础,给出了蚁群算法的一般性模型,讨论了其收敛性及在静态TSP和动态网络路由问题中的应用,主要工作内容有: 第一章给出了蚁群算法的描述和在静态、动态情况下的各类应用,并指出蚁群算法所具有的分布式计算、鲁棒性、应用简单等特点,以及蚁群算法潜在的广泛应用前景。 第二章分析了蚁群算法的基本原理,针对蚁群算法所能解决的问题更多还原

【Abstract】 A general-purpose metaheuristic named Ant Colony Optimization algorithm, which take inspiration from real ant’s behavior in finding shortest paths using as information only the trail of a chemical substance （called pheromone） deposited by other ants, boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, and have recently been successfully applied to several discrete optimization problems. In all these algorithms a set of artificial ants collectively solve the problem under consideration through a cooperative effort. This effort is mediated by indirect communication of information on the problem structure the ants concurrently collect while building solutions by using a stochastic policy. The details were studied as follows:In the first chapter of this paper, the definition, taxonomy and characteristics of the routing problem are reported. The routing problem is a stochastic distributed multi-objective problem. Information propagation delays, and the difficulty to completely characterize the network dynamics under arbitrary traffic patterns, make the general routing problem intrinsically distributed. Routing decision can only be made on the basis of local and approximate information about the current and the future network states. These features make the problem well suited for Ant Colony Optimization algorithm.The second chapter presents a formal definition of graphs and the theory of ant algorithms, self-organization and the Ant Colony Optimization metaheuristic. The pheromone-based parameterized probabilistic model for the ACO algorithm is presented as the solution construction graph that the combinatorial optimization problem can be mapped on. Based on the solution construction graph, the unified framework of the ACO algorithm is presented. And this paper proposed several extensions of the Ant System that was the prototype of the ant algorithms. All these extensions were in some sense "greedier" than Ant System, but differ significantly in main aspects of the search control.In the third chapter, the solution of a metaheuristic following the ant colony optimization paradigm, the graph-based ant system, converge with a probability that can be made arbitrarily close to unity to one element of the set of optimal solutions.The 4^th chapter introduces an Enhance Ant-Q, a family of algorithms that presentmany similarities with Q-learning. In initialization phase, a same value is given to pheromone trail, so in the early stages of the computation the use of the heuristic improves the performance and pheromone trail have no special meaning. As computation goes on, pheromone trail become more and more useful to direct agents in finding good solutions. Thus we apply a non-linearity parameter to weigh more importance of the heuristic values than pheromone trail in the first iterations. The results obtained by Enhance Ant-Q are competitive with those obtained by other heuristic approaches.The 5^th chapter presents a distributed algorithm based on the self-organized capacity of ants for routing and load balancing in dynamic communication networks. Agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. The algorithms’ performance is shown to significantly improve the network’s relaxation and its response to perturbations.The 6^th chapter describes an adaptive swarm-based routing algorithm inspired by the social behavior of ants which boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, which are well suited for routing in modern communication networks. The algorithm increases convergence speed, reduces routing instabilities and oscillations by using a novel variation of reinforcement learning and a technique called momentum. We run many experiments over real IP datagram networks and under several traffic distributions. Results are very encouraging.In the 7^th chapter all of the work in this dissertation was summed up, and the future researches in this area were prospected.更多还原