【作者】 夏鸿斌；

【导师】 须文波；

【作者基本信息】 江南大学 ， 轻工信息技术与工程， 2009， 博士

【摘要】 许多群体生物的自适应优化现象不断给人类以启示,群居生物的群体行为使许多在人类看起来高度复杂的优化问题得到了完美的解决。科学家通过对群体生物的观察与研究产生了以模仿自然界群体生物行为特征的群体智能研究领域。例如,蚂蚁具有找到蚁穴与食物源之间最短路径的能力,受此启发提出的蚁群优化算法(Ant Conoly Algorithm,简称ACO)最初用于解决旅行商问题,具有自适应性、鲁棒性及本质上的并行性等许多特点,广泛适用于各种静态和动态的组合优化问题中,具有潜在的应用前景。而人工神经网络(Artificial Neural Network,简称ANN)是近年来迅速发展起来的又一种新型信息处理手段,是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。已有许多学者进行将一些计算智能方法应用于网络优化和管理的研究中。由于设备和服务不断增加的结果,现代数据网络,包括有线和无线网络,正逐渐呈多样和异构特性。无数混杂的网络构件准确无误的交互需要,形成了巨大的挑战,尤其对于传统上使用集中方法进行网络控制的网络,比如包交换和虚电路网络,以及INTERNET这一逐渐变为多样化的子网模式集合。网络优化问题是一类特殊的组合优化问题,属于NP困难问题。寻找、研究、应用启发式智能化的优化方法就显得尤为重要。计算机网络是复杂的动态分布式非线性系统,网络流量分析及预测同样是一个复杂的问题。对复杂系统建模目前仍是一个开放性问题。对模型的描述和预测尚未有一套广泛适用的方法,如何使用智能计算技术对网络流量预测建模还有大量的工作要作。本文的研究目的:一方面是探索和完善群体智能模型,使之能更有效的解决传统方法难以处理的大规模复杂性问题;另一方面将群体智能及计算智能方法应用到分布式动态网络路由及负载平衡管理和网络流量测量领域,使计算智能方法能够解决更多的工程实践问题。本文的主要研究成果包括:(1)提出了一种基于多蚁群的蚁群优化算法。该算法通过将蚁群分为若干个子群,采用多蚁群并行执行搜索任务。不同种群的蚂蚁释放不同类型的信息素;蚂蚁释放的信息素对本种群的蚂蚁有吸引力,对其他种群的蚂蚁具有排斥力。这种吸引与排斥的共同作用与启发信息一起,决定了蚂蚁的转移选择概率。提出了一种新的动态转移选择概率。仿真实验结果表明,改进后的算法能有效地提高算法的全局搜索能力,较明显的克服了传统蚁群算法停滞收敛等问题。(2)提出了一种融合遗传算法(Genetic Algorithms)与蚁群算法的混合算法。该算法在蚁群优化算法中引入了路径遗传算子,并提出了以路径染色体的适应度函数评价结果为基础的信息素更新策略,对蚂蚁发现的路径进行染色体编码,通过适应度函数对蚂蚁的路径进行适应度评价,进行交叉和变异运算,经过不断的迭代和种群的进化,获得更好的解。从仿真结果可以看出,本文的方法能更有效地解决对称TSP问题,提高了算法收敛速度及解的质量。(3)提出了一种多蚁群并行算法,进行了并行蚁群算法的研究。通过改变ACO算法行为并结合有效的并行ACO策略,在单处理器上运行多蚁群系统,并采用数据并行策略提出了多蚁群并行处理算法。在较小规模的并行处理器上进行了实验。多蚁群选择策略和并行策略在定性分析和实验中表现出了能够改善搜索能力,具有较好的可扩展性,并提高解的质量,有利于算法解决更大规模的问题。(4)研究并实现了用于群体智能路由算法研究的动态网络仿真系统,给出了仿真系统的设计过程和系统模型,该模型能对网络动态和非精确状态信息进行有效模拟且支持群体智能路由的仿真研究。(5)在蚂蚁算法的基础上,提出了两个分布式群体智能路由算法。其一,是采用使用聚类的方法有效的减少了网络蚂蚁代理数量,同时通过路由表的构造策略提高了蚂蚁的搜索效率,从而有效地提高了算法的可扩展性和鲁棒性。其二,通过引入遗传运算策略,对AntNet进行了有效的改进,提出了路径遗传操作和以路径染色体的适应度函数评价结果为基础的信息素更新策略,应用于分布式网络路由管理中,降低了原算法的复杂性。仿真结果表明,该方法能有效地实现更具有灵活性的路由选择策略,为当前路由选择问题的解决提供了一种新的途径。(6)将提出的多蚁群算法应用于分布式网络优化管理中,解决动态分布式网络中负载平衡路由问题。该算法具有本质上的可扩展性,采用的主要方法为:将蚁群划分为若干个子群,不同子群的蚂蚁释放不同类型的信息素。通过不同类型信息素之间的相互制约作用,以及链路负载的测量,提出了三种策略以实现负载平衡路由。在当前最优路径出现阻塞时,算法可以很快找到一条替代的最优路径。实验结果表明,整个算法应用概率选择数据包转发的路径,能够充分利用多条可行路径,从而提高网络负载的均衡性、鲁棒性、负载流量以及网络的利用率。该算法能有效模拟解决大型通信网络资源的分配问题。(7)将递归神经网络算法与灰色理论模型结合,提出了一种组合预测模型,并应用到网络流量预测模型的建立。利用递归神经网络很强的自组织、自适应、自学习的概括和抽取信息的能力,将其与灰色系统理论有机结合起来,针对较高精度的短期网络流量预测进行了预测模型建立的相关理论及应用的系统研究。并用数值仿真验证了算法的有效性。最后,对全文的研究工作进行了总结,并展望了进一步需要研究的课题和方向。更多还原

【Abstract】 The phenomena of adaptive optimization in social creatures inspire humanity constantly. Collective behaviors of social creatures have made optimization problems with high degree of complexity to scientists perfectly solved. Research on swarm intelligence emerged out of observing and mimicing collective behaviors of social creatures. 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. It has the latent application prospect. The artificial neural networks (ANN) is a new information processing method which developed rapidly in recent years, and is a intelligent system which simulates the human brain organizational structure and intelligent behavior based on the simulation of human brain operational mechanism.As a result of equipment and service unceasing increasement, modern data network, including wired and wireless network, is assuming diverse and isomerism characteristic gradually. The demand of unmistakably interacting between innumerable combination network component, has formed the huge challenge. The network management questions, including optimization, network traffic analysis and forecast, is a kind of special combination optimization question, and is a NP-hard problem. To find, research, application of intelligent heuristic approach is particularly important.The goal of this dissertation is to explore and further swarm intelligence models, which makes it easy to solve large-scale complicated problems. On the other hand, this thesis extends the application domains of swarm intelligence and to cope with more practical engineering problems. On the other hand, this thesis On the other hand, this thesis applies swarm intelligence and evolutionary computation methods to the research domain of distributed dynamic network routing, load balancing and network traffic forecast, so that the intelligent computation method can solve the more practical engineering problems.The contributions of this dissertation are as follows:(1) A multiple ant colony optimization algorithm is proposed. The artificial ants are partitioned into several groups. Each group of ant colony releases different types of pheromones. Attract factor and exclusion factor are introduced, and a new transition probability with multiple ant colony was given, so as to strengthen the global search capability. By tackling symmetric travelling salesman problems, this paper compares the improved algorithms implementation with the ACS and AS algorithms. The experimental results indicate that the improved algorithm is superior to the ACO and AS algorithms. The improved algorithm has excellent global optimization properties and faster the convergence speed, and it can avoid premature convergence of ACO.(2) A hybrid algorithms combining ACO algorithm with genetic Algorithm is present. The new algorithm is for solving the problem of the stagnation and slow convergence in ACO. The path genetic operators are proposed, and a new pheromone update rule is achieved. Each chromosome is encoded as a series of nodes that in the path ants have found, and is evaluated with a fitness function. Path crossover and path mutation are performed on the path chromosomes. The experimental results indicate that the improved algorithm is superior to the ACS algorithms. The improved algorithm has excellent global optimization properties and faster the convergence speed.(3) A new approach to parallel ant colony optimization (ACO) algorithms by changing the behavior of ACO is present. The principal idea is to partition each ant colony into several sub-colonies, and to propose a new transition probability, so as to strengthen the global search capability. The parallelization strategies for multiple Ant Colony Optimization algorithms are discussed. The performance of the proposed parallel algorithm, applied to the Traveling Salesman Problem, is investigated and evaluated with respect to solution quality and computational effort. The experimental studies demonstrate that the proposed algorithm outperforms the sequential Ant Colony System as well as the existing parallel ACO algorithms. The studies also indicate that the new explore scheme based on multiple ant colony improves performance, particularly in exchange strategies that exchange best solution information among all colonies. The new algorithm has a good extendibility and suit to solve large-scale problem.(4) A dynamic network simulation system has been developed using event driven method. The methods of how to simulate the network topology, traffic model, and intelligent network routing protocol have been given. The experimental result indicates that the network simulation model can simulate dynamic network and non-precise condition, and also can be applied to study intelligent routing algorithm over it.(5) Two distributed swarm intelligence routing algorithm are present. One is Adaptive distributed routing algorithm based on ant-algorithm. The network nodes are partitioned using k-means clustering, and different search strategies are implemented by different types of ants. A new routing table formation scheme is proposed. The proposed algorithm is scalable, robust and suitable to handle large amounts of network traffic, with minimizing delay and packet loss. The other method is based on the hybrid algorithms combining ACO algorithm with genetic Algorithm in (2). The AntNet algorithm is improved through the introduction of genetic algorithm strategy. A new pheromone update rule is achieved via path genetic operators. The simulation results show that the improved algorithm has faster speed of the convergence, also the network throughput is effectively improved, and the average time delay in network is reduced.(6) An effective load-balance routing strategy is present. Appling the multiple ant colony optimization algorithms in the distribution network load-balance routing. The proposed algorithm has the essentially extendibility, can effectively address the resources assignment problem in large-scale network. A new dynamic transition and search strategy based on multiple ant colony are used for load-balance routing. Three mechanisms based on ACO for load-balancing and routing are proposed. The performance of the proposed three mechanisms, applied to the simulation network SDH, is investigated and evaluated with respect to solution quality and computational effort. The experimental results indicate that, the algorithm can use the multiple feasible routing path while network in heavy load status. The algorithm enhances the network load balance, robustness as well as the Qos of network.(7) A new network traffic prediction model which combines the grey theory and neural network was presented. The recursion neural network has very strong ability of the self organization, adaptive, self learning and extraction information. The combined model is to forecast the short-term network traffic with high precision. The simulation results on real network traffic show the new model has better predictive precision.Finally, the work of this dissertation is summarized and the prospective of future research is discussed.更多还原