【作者】 寇晓丽；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2009， 博士

【摘要】 群智能算法是一种新型的仿生类进化算法,主要包括蚁群优化算法和粒子群算法.群智能算法具有较强的鲁棒性,采用分布式计算机制,并且易于实现,已在众多领域得到了广泛的应用.本文主要围绕蚁群优化算法和微粒群算法的理论及其应用,就如何求解大规模旅行商(Traveling Salesman Problem, TSP)问题、连续性优化问题、约束优化问题、无线传感器网络路由优化问题进行了研究.本文的主要工作概括如下:1.针对大规模TSP问题,提出了一种基于模块度分簇的改进蚁群算法.该算法首先借鉴网络中的分簇原理,基于模块度的分簇算法将TSP问题中的城市划分为若干个簇,降低了问题的维数,并提出模块度的概念来度量所得到的簇结构和实际TSP问题网络匹配的程度;其次,基于信息素扩散的改进蚁群算法求解簇间的连接顺序,即求解分簇得到的小规模TSP问题的最优解,在基于信息素扩散的改进蚁群算法中,从多方面模拟真实蚂蚁的行为,定义了新的信息素扩散挥发规则,增强了蚂蚁之间的合作,使其快速找到最优解,同时增加扰动因子避免其陷入局部最优解,并且分析了其全局收敛性,实例测试结果表明了算法的有效性;然后,构造了求解簇内最短路径的基于信息素扩散的改进蚁群算法;最后,将所有簇内和簇间的解按照一定的规则组成了原TSP问题的解.仿真实验结果表明该算法适合求解大规模TSP问题,与已有算法相比,解的质量和收敛速度均有了较明显的提高.2.针对蚁群算法在连续空间函数优化中应用的瓶颈,提出了一种蚁群混合算法求解连续空间问题,定义了新的蚁群信息素更新规则、蚁群在解空间的寻优方式和蚁群行进策略.为了克服蚁群算法搜索时间过长,易陷于局部最优等缺点,在搜索过程中嵌入了改进的Alopex算法,该算法具有快速搜索和摆脱局部最优解的能力,实验结果表明了蚁群混合算法的有效性.3.针对标准微粒群算法不能保证全局收敛性问题,提出了一种随机混合微粒群算法.在随机微粒群算法中,将惯性权重设置为零,减少了关键参数对算法性能的影响,提高了算法的通用性;在保证算法全局收敛性的同时,结合Alopex算法重新生成停止进化粒子的位置,有效地避免了算法因单一搜索机制引起地停滞现象.将该算法应用于复杂多维函数,取得了较好的效果,为解决较复杂的函数优化问题提供了一种可行的方法.4.针对约束优化问题,提出了一种基于协同进化的微粒群算法.该算法在标准微粒群算法的基础上,采用“保留最优,调节部分”的确定型选择策略,利用进化中个体之间的差异,提出协同算子公式,引导进化方向,使个体之间相互利用信息,更新微粒的位置进化方程;同时,提出基于不可行度的约束处理方法,根据不可行度和不可行度阀值提出新的竞争选择准则,并由此给出新的适应值函数引导群体加强对约束边界的搜索.基于典型的约束优化问题的实验结果表明:该算法可行有效,尤其对解决复杂问题表现出较优的性能.5.研究了蚁群算法在无线传感器网络路由协议中的应用.无线传感器网络路由协议的一个重要目标就是要合理高效地使用网络中各传感器节点的能量,延长网络寿命.文中提出了一种基于蚁群算法的无线传感器网络分簇路由协议.该方法首先利用网络自身拓扑结构,基于模块度的分簇算法得到一个稳定的簇结构,无需每轮循环都构造簇,从而节省了构造簇的开销;其次,根据每个簇内节点的剩余能量以及簇内节点的分布情况,给出了新的簇头选择函数;然后,提出基于蚁群算法的簇间多跳路由算法,该算法以如何均衡传输路径上消耗的能量和簇头节点的剩余能量为出发点,制定了新的蚂蚁转移概率和信息素更新规则,通过实验仿真,并与已有较好算法相比较,验证了算法的有效性.更多还原

【Abstract】 Swarm intelligence algorithm is an algorithmic approach, inspired by the foraging behavior of the real animals, which had been applied to many problems. The dissertation focuses on the principles, theory, and applications of Ant Colony Optimization algorithm (ACO) and Particle Swarm Optimization (PSO), especially, an in-deep and systemic study on how to improve the basic ACO and PSO algorithm, parallel implementation of ACO and PSO, solving the problems such as large scale TSP and continuous space optimization, constrained optimization, wireless sensor network routing protocol. The main works can be summarized as follows:1. To tackle the large scale TSP, An Ant Colony Algorithm in pheromone Diffusion model based on Modularity Clustering is proposed. Firstly, the large scale TSP is divided into several clustering based on modularity measure. Secondly, all the clustering will be solved in parallelization by an improved ant colony algorithm based on the pheromone diffusion model, this algorithm formulate the new rule of pheromone diffusion, and a disturbance mechanism is added to ant colony optimization for improving the new algorithms’performance. The simulation of TSP problem shows that this algorithm has a satisfied global convergence. Lastly, all the solutions of each clustering will be merged into the solution of the large scale TSP by some rules. Simulation results show that the convergence of the proposed algorithm has been improved.2. A hybrid optimization algorithm, in which Alopex algorithm is embedded into the improved ant colony optimization algorithm, is proposed for searching continuous space optimization. In the algorithm, the new pheromone updating rule and the moving strategy of ants are defined. The algorithm is with the rapid search capability of the improved Alopex algorithm and the good search characteristics of the improved ant colony optimization algorithm. Simulation results show that the algorithm is effective.3. A hybrid algorithm is proposed by combining particle swarm optimization(PSO)with Alopex algorithm that is a stochastic optimization method, for solving constrained optimization problems. In the algorithm, inertia weight is zero, and the position of the particle whose evolution has been stopped is produced by Alopex algorithm to improve the global search ability. Simulation results show that the algorithm is effective. 4. A co-evolutionary particle swarm optimization algorithm to solve constrained optimization problems is proposed. Firstly, A new co-evolutionary PSO (CPSO) is constructed. In the algorithm, a deterministic selection strategy is proposed to ensure the diversity of population. Meanwhile, based on the theory of extrapolation, the induction of evolving direction is enhanced by adding a co-evolutionary strategy, in which the particles make full use of the information each other by using gene-adjusting and adaptive focus-varied tuning operator. Secondly, infeasible degree selection mechanism is used to handle the constraints. A new selection criterion is adopted as tournament rules to select individuals. Also, the infeasible solution is properly accepted as the feasible solution based on a defined threshold of the infeasible degree. This diversity mechanism is helpful to guide the search direction towards the feasible region. Our approach was tested on six problems commonly used in the literature. The results obtained are repeatedly closer to the true optimum solution than the other techniques.5. To make efficiently use of the limited energy resource of the wireless sensor network (WSN) and prolong the lifetime is an important problem in the study of the WSN. An energy efficient routing algorithm based on Ant Colony Optimization for wireless sensor network is presented. The algorithm forms a clustering structure based on real network structure of wireless sensor network first and we use a new parameter-Modularity Measure to evaluate whether the clustering fits for the real network structure. Based on the above steady cluster structure, when we select the cluster head in each cluster, the residual energy of the nodes and the energy distributing in the cluster are both considered. The algorithm constructs a novel probabilistic model; the model considers both the overhead on the route and the residual energy of the node. Simulation results show that compared with other algorithms like LEACH, our approach is able to obtain a more reasonable and steady distribution of clustering, and can effectively prolong the sensor network lifetime.更多还原