【作者】 胡小兵；

【导师】 黄席樾；

【作者基本信息】 重庆大学 ， 控制理论与控制工程， 2004， 博士

【摘要】 社会性动物的群集活动往往能产生惊人的自组织行为,如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发,意大利学者M. Dorigo,V. Maniezzo和A. Colorni通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注,在过去短短十多年的时间里,已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用,并取得了较好的效果。本论文围绕蚁群优化的原理、理论及其应用,就如何改进基本蚁群优化算法、蚁群优化的并行实现,蚁群优化算法在组合优化、机器人路径规划等领域的应用进行了较为深入、系统的研究。本文的主要研究成果包括:1、提出了一种自适应蚁群算法。该算法根据平均节点分支数动态调整转移概率以使其在“探索”和“利用”之间总能保持平衡,从而使算法在保持较高搜索能力的同时,避免出现停滞现象。仿真实验结果表明,该算法不仅有效地克服了基本蚁群优化算法中的停滞现象,而且即使在运行的后期,仍然能以极大的概率搜索较好解。2、提出了一种基于混合行为的蚁群算法。分析了蚂蚁行为对蚁群优化算法性能的影响,给出了蚂蚁行为的定义,设计了算法的模型。根据蚂蚁行为的定义,设计了四种具体的蚂蚁行为,通过调整不同行为蚂蚁数量的比例,使该算法在具有较高搜索能力的同时避免停滞现象。仿真实验首先对算法的参数进行了研究,然后与AS算法进行对比,实验结果显示其性能优于AS算法。3、提出了一种蚁群优化的并行实现。该算法利用TSP问题所具有的聚类特征,从数据域上将其分解成许多小规模的子问题,对每个子问题分别采用蚁群优化算法并行求解,最后再将所有子问题的解按一定规则合并为待求解问题的解。对带聚类特征TSP问题的仿真实验结果表明,该算法能以极快的速度收敛到问题的最优解(近优解)。当TSP问题的聚类数越多,则该算法的性能就越高,但当TSP问题的聚类特征不明显,则该算法退化为一般的蚁群优化算法。4、提出了一种求解K-TSP问题的蚁群算法。该算法将所有蚂蚁平均分成m组,每组k只,并采用每组中的k只蚂蚁共同构造问题的一个可行解。在算法中,m组蚂蚁相互协作最终达到搜索最优解的目的。实验结果显示,该算法是一种求解K-TSP问题的有效算法。 <WP=6>5、提出了一种求解0-1背包问题的蚁群优化算法。设计了0-1背包问题的构造图,针对构造图为蚂蚁设计了两种状态转移公式并定义了其优先级,蚂蚁以不同的优先级按照这两个状态转移公式在构造图中移动直到死亡,此时,蚂蚁走过的路径即构成0-1背包问题的一个可行解。仿真实验首先对该算法的参数进行了讨论,然后与遗传算法进行了比较,实验结果显示该算法具有较高的性能。6、提出了一种求解迷宫问题的蚁群优化算法。该算法首先将蚁群平均分成两组,分别从迷宫的起点和终点出发,每只蚂蚁按路径上的信息素独立地选择前进的道路。根据蚂蚁在迷宫中的行走状态,定义了三种不同类型的生命周期。根据蚂蚁每次移动后所处的状态,生成问题的可行解。仿真实验证实了本算法的有效性。7、提出了一种求解空间机器人路径规划的蚁群优化算法。该算法首先将机器人所在位置(源点)与将要到达的位置(目的点)之间的空间划分成立体网格,同时定义了源点与目的点之间的有效路径。蚁群从源点出发,独立地选择有效路径,最终到达目的点,从而求出从源点到目的点之间的最优路径。实验结果表明,该算法不仅有效,而且具有极快的速度。在该算法中,网格的稠密程度决定了算法解的精度,即网格越稠密,算法的精度越高,但所需时间也越长;反之则越低,所花时间越短。最后,对全文的研究工作进行了总结,并展望了蚁群优化进一步还要研究的课题。更多还原

【Abstract】 A wonderful self-organization behavior will usually be produced from the collective behavior of social animals. Take a colony of ants for example, blind ants can find the shortest routing path from their nest to food source. Biologists had studied the phenomenon carefully and found that ants cooperate to find the shortest routing path by means of indirect communications using a kind of substance call “pheromone”. Inspired from this, a population-based simulated evolutionary algorithm called ant colony optimization (ACO for short) was proposed by Italian researchers M. Dorigo, V. Maniezzo and A. Colorni. Many scholars are attracted to study ACO and in the past ten years the algorithm has been widely applied to the fields of combinatorial optimization, network routing, functional optimization, data mining, and path planning of robot etc, and good effects of application are gained.The dissertation focuses on the principles, theory, and applications of ACO, especially, an in-deep and systemic study on how to improve the basic ACO algorithm, parallel implementation of ACO, solving the problems such as combinatorial optimization problem and path planning of robot, The main achievements of this dissertation include:1. An adaptive ant colony algorithm (AACA) was proposed. In AACA, the transition probability with which ant used to select next city is dynamically adjusted based on the number of Average Node Branching (ANB) to balance the “exploration” and “exploitation” of the searching process. In this way, not only the ability of searching better solution is kept, but also the stagnation behavior of the algorithm is avoided. Simulated experiments show that stagnation behavior of basic ACO algorithm are avoided in AACA algorithm and a good ability of searching better solution in the last runs of AACA algorithm.2. A hybrid behavior based ant colony algorithm (HBACA) is proposed. The influences of ant’ behavior on performance of ACO algorithms are analyzed, the definition of ant’ behavior is given, and a model of the algorithm is designed. Four kinds of concrete ant’s behaviors are designed base on the definition of ant’s behavior. By tuning the proportion of ant with different behaviors, not only the high capability of searching good solution is kept but also the stagnation behavior is avoided. The parameters setting of the algorithm are discussed first and a comparison of HBACA <WP=8>algorithm and AS algorithm is performed. The experimental results show that the algorithm is better than AS algorithm.3. A parallel implementation of ACO is presented. Taking advantage of clustering feature in TSP problem, the problem is divided into several sub-problems in data domain by clustering processing. And then all the sub-problems will be solved in parallel by ant algorithm respectively. At last all the solutions of each sub-problem will be merged into the solution of the problem to be solved by some rules. Simulated experiment on TSP problems with clustering feature has shown that the algorithm can converge to the (near) best solution of the problem with great rate. It also shows that the more the number of clustering of TSP problem, the more higher performance of the algorithm is, but when the clustering feature of TSP is not distinct, the algorithm will become general ACO algorithm.4. An ant colony algorithm to tackle k-person traveling salesman problem (K-TSP) is proposed (ACA-KTSP). In the algorithm all the ants are divided averagely into m groups, in which there are k ants. In each group, k ants are imposed to construct a feasible solution of the problem, and in the algorithm, m group of ants cooperate to search the best solution of the problem. The experimental results show that the algorithm is effective for K-TSP problem.5. An ACO algorithm to solve 0-1 knapsack problem (KP) is presented (ACA-KP). The construction graph for KP problem is designed. Based on the construction graph, two state transition formulas are designed and a priority of the formulas is defined, ants move on the construction graph node更多还原