【作者】 王会颖；

【导师】 贾瑞玉； 倪志伟；

【作者基本信息】 安徽大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 自然界里蚂蚁、蜜蜂等，虽然他们个体的智能并不高，却表现出很高的群体智能。群体智能起源于科学家对群居性昆虫的观察和研究。群体智能是指任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置。群体智能以其简单性、灵活性、分布性、健壮性在组合优化问题、知识发现、通信网络、机器人等研究领域显示出巨大的潜力和优势，并推动复杂科学的发展。蚁群算法是一种新型仿生类进化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法。蚂蚁有能力在没有任何提示下找到从巢穴到食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选择。根本原因是蚂蚁在寻找食物时，能在其走过的路上释放一种特殊的分泌物—信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。蚁群算法由意大利学者M.Dorigo等人首先提出，并成功地应用于求解TSP、二次分配、图着色、车辆调度、集成电路设计及通信网络负载等问题。蚁群算法从提出到现在，短短十余年的时间，以其在离散型组合优化问题中的突出表现，吸引了人们的极大关注。论文研究了群体智能的多个模型，研究的目的，一方面是探索和验证群体智能在解决分布式问题方面的特性，另一方面是拓宽群体智能的应用领域。文章的研究工作主要包括以下几个方面：(1)蚁群算法的研究。提出一种求解TSP问题的分段交换蚁群算法。分段交换蚁群算法把小窗口、随机分段优化求解、模拟退火充分交换的思想引入蚁群算法，把蚁群算法和模拟退火算法融合。该算法在蚁群算法陷入局部最优解的情况下，能改进其局部最优解，并可减少迭代次数。(2)蚁群算法应用于0-1背包问题的研究。0-1背包问题是典型的NP完全问题，且蚁群算法已成功地解决了许多组合优化的难题。因此，文章介绍一种基于蚁群算法求解0-1背包问题的算法，并对此算法进行优化，提出一种求解0-1背包问题的快速蚁群算法。当物品数较大时，也取得了较好的求解质量。(3)蚁群算法应用于圆排列问题的研究。本章提出一种求解圆排列问题的快速蚁群算法。优化后的该算法，大大减少了蚁群算法的搜索时间，有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。(4)改进蚁群算法及两类应用模型的研究。论文通过改变概率的计算时机，按“概率之和为u的轮盘赌”方式选择下一个元素，基于模拟退火的分段交换优化当前最优解，对基本的蚁群算法进行改进，提出一种改进的蚁群算法。文章还对蚁群算法解决组合优化问题进行总结，提出了蚁群算法的两类应用模型。(5)基于群体智能求解N后问题的研究。文章提出一种求解N后问题的蚂蚁模型算法，它受启发于群体智能的蚂蚁算法和多Agent系统，又吸收了回溯算法的优点。该算法是一种随机搜索算法，从根本上改变了回溯算法的系统地搜索机制，避免了大量的冗余搜索，又保证了必要的搜索。在求解N后问题的第一个解时，大大减少求解时间和求解步数，当N较大时，也可得到较好的求解效果。更多还原

【Abstract】 In the nature ants and bees often can achieve a complex task while a single bodymay be failure. Swarm Intelligence emerged out of social insect collective behavior.Swarm Intelligence is defined as any attempt to design algorithms or distributedproblem-solving devices inspired by the collective behavior of the social insertcolonies and other animal societies. Swarm Intelligence exhibits a number ofinteresting properties such as flexibility, robustness, decentralization andself-organization. The instances of these algorithms on the domains of optimization,telecommunication network, knowledge discovery and robots are obviously increased.Swarm Intelligence has become a hot research area for Artificial Intelligenceresearchers.Ant Colony Optimization Algorithms is a kind of evolution computationalgorithms base on bionics, which has the character of positive feedback and parallelprocessing. Ants can find the best route between a hole and foods. The reason is thatthe ant release volatile pheromone in the trail. Ants communicate with others by thepheromone that is left on the road and their behaviors are trending to the trail of densepheromone. Because the pheromones in the optimal route volatile less, there are moreand more ants pass through this routes and strengthen the optimal route. The processof the optimal route is forming by positive feedback. Ant colony algorithm was firstput forward to solve the famous traveling Salesman problem by Marco Dorigo and hiscolleagues. Now it has been successfully used to solve many kinds of combinationoptimization problems such as quadratic assignment, graph coloring, vehicle route,sequential ordering and so on.This dissertation focuses on a number of Swarm Intelligence models. The goal ofthis dissertation is to explore and further proof the properties of the algorithms. On theother hand, this thesis extends the application domains of swarm intelligence. Thecontributions of this dissertation are as follows: (1) Research on ant colony algorithms. A subsection exchange ant colonyalgorithm of solving TSP is presented. The idea of small windows, random subsectionand enough exchange of Simulated Annealing are introduced into ant colonyalgorithm. It combines ant colony algorithm with Simulated Annealing. On thecondition of falling in local best of ant colony algorithm, it can improve the precision.It also can reduce the number of searching. Simulation results show that better effectsare obtained.(2) Research on appliocation of ant colony algorithm to 0-1 knapsack problem.0-1 knapsack problem is a difficult NP problem. Ant colony algorithm was appliedsuccessfully to many hard combinational optimization problems. So, An ant colonyalgorithm of solving 0-1 knapsack problem is introduced.By optimizing it, a quickant colony algorithm of solving 0-1 knapsack problem is presented. When the numberof article is big it also can obtain better effects.(3) Research on appliocation of ant colony algorithm to circle permutationproblem. A quick ant colony algorithm of solving circle permutation problem is putforward. By optimizing it, it greatly reduces the searching time of ant colonyalgorithm. It also effectively ameliorates the disadvantage of easily falling in localbest of ant colony algorithm.(4) Research on an improved ant colony algorithm and two types of applicationmodels. By changing the time of calculating the probability and using of roulette-wheel which sum of probability is u and subsection exchange based on SimulatedAnnealing, an improved ant colony algorithm is put forward. Two types of applicationmodels of ant colony algorithm are also presented.(5) Research on solving N queens problem based on swarm intelligence. An antmodel algorithm of solving N queens problem is put forward. It is inspired by swarmintelligence and ant algorithm and multi-Agent system. It absorbs advantages of backtrace algorithm. Ant model algorithm is a random searching algorithm. It radicallychanges the technique of systemic searching and avoids large amount of redundantsearching and ensures the necessary searching. It greatly reduces searching time and更多还原