蚁群优化原理、理论及其应用研究
|
摘要
社会性动物的群集活动往往能产生惊人的自组织行为,如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发,意大利学者M. Dorigo,V. Maniezzo和A. Colorni通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注,在过去短短十多年的时间里,已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用,并取得了较好的效果。
本论文围绕蚁群优化的原理、理论及其应用,就如何改进基本蚁群优化算法、蚁群优化的并行实现,蚁群优化算法在组合优化、机器人路径规划等领域的应用进行了较为深入、系统的研究。本文的主要研究成果包括:
1、提出了一种自适应蚁群算法。该算法根据平均节点分支数动态调整转移概率以使其在“探索”和“利用”之间总能保持平衡,从而使算法在保持较高搜索能力的同时,避免出现停滞现象。仿真实验结果表明,该算法不仅有效地克服了基本蚁群优化算法中的停滞现象,而且即使在运行的后期,仍然能以极大的概率搜索较好解。
2、提出了一种基于混合行为的蚁群算法。分析了蚂蚁行为对蚁群优化算法性能的影响,给出了蚂蚁行为的定义,设计了算法的模型。根据蚂蚁行为的定义,设计了四种具体的蚂蚁行为,通过调整不同行为蚂蚁数量的比例,使该算法在具有较高搜索能力的同时避免停滞现象。仿真实验首先对算法的参数进行了研究,然后与AS算法进行对比,实验结果显示其性能优于AS算法。
3、提出了一种蚁群优化的并行实现。该算法利用TSP问题所具有的聚类特征,从数据域上将其分解成许多小规模的子问题,对每个子问题分别采用蚁群优化算法并行求解,最后再将所有子问题的解按一定规则合并为待求解问题的解。对带聚类特征TSP问题的仿真实验结果表明,该算法能以极快的速度收敛到问题的最优解(近优解)。当TSP问题的聚类数越多,则该算法的性能就越高,但当TSP问题的聚类特征不明显,则该算法退化为一般的蚁群优化算法。
4、提出了一种求解K-TSP问题的蚁群算法。该算法将所有蚂蚁平均分成m组,每组k只,并采用每组中的k只蚂蚁共同构造问题的一个可行解。在算法中,m组蚂蚁相互协作最终达到搜索最优解的目的。实验结果显示,该算法是一种求解K-TSP问题的有效算法。
5、提出了一种求解0-1背包问题的蚁群优化算法。设计了0-1背包问题的构造图,针对构造图为蚂蚁设计了两种状态转移公式并定义了其优先级,蚂蚁以不同的优先级按照这两个状态转移公式在构造图中移动直到死亡,此时,蚂蚁走过的路径即构成0-1背包问题的一个可行解。仿真实验首先对该算法的参数进行了讨论,然后与遗传算法进行了比较,实验结果显示该算法具有较高的性能。
6、提出了一种求解迷宫问题的蚁群优化算法。该算法首先将蚁群平均分成两组,分别从迷宫的起点和终点出发,每只蚂蚁按路径上的信息素独立地选择前进的道路。根据蚂蚁在迷宫中的行走状态,定义了三种不同类型的生命周期。根据蚂蚁每次移动后所处的状态,生成问题的可行解。仿真实验证实了本算法的有效性。
7、提出了一种求解空间机器人路径规划的蚁群优化算法。该算法首先将机器人所在位置(源点)与将要到达的位置(目的点)之间的空间划分成立体网格,同时定义了源点与目的点之间的有效路径。蚁群从源点出发,独立地选择有效路径,最终到达目的点,从而求出从源点到目的点之间的最优路径。实验结果表明,该算法不仅有效,而且具有极快的速度。在该算法中,网格的稠密程度决定了算法解的精度,即网格越稠密,算法的精度越高,但所需时间也越长;反之则越低,所花时间越短。
最后,对全文的研究工作进行了总结,并展望了蚁群优化进一步还要研究的课题。
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
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
本论文围绕蚁群优化的原理、理论及其应用,就如何改进基本蚁群优化算法、蚁群优化的并行实现,蚁群优化算法在组合优化、机器人路径规划等领域的应用进行了较为深入、系统的研究。本文的主要研究成果包括:
1、提出了一种自适应蚁群算法。该算法根据平均节点分支数动态调整转移概率以使其在“探索”和“利用”之间总能保持平衡,从而使算法在保持较高搜索能力的同时,避免出现停滞现象。仿真实验结果表明,该算法不仅有效地克服了基本蚁群优化算法中的停滞现象,而且即使在运行的后期,仍然能以极大的概率搜索较好解。
2、提出了一种基于混合行为的蚁群算法。分析了蚂蚁行为对蚁群优化算法性能的影响,给出了蚂蚁行为的定义,设计了算法的模型。根据蚂蚁行为的定义,设计了四种具体的蚂蚁行为,通过调整不同行为蚂蚁数量的比例,使该算法在具有较高搜索能力的同时避免停滞现象。仿真实验首先对算法的参数进行了研究,然后与AS算法进行对比,实验结果显示其性能优于AS算法。
3、提出了一种蚁群优化的并行实现。该算法利用TSP问题所具有的聚类特征,从数据域上将其分解成许多小规模的子问题,对每个子问题分别采用蚁群优化算法并行求解,最后再将所有子问题的解按一定规则合并为待求解问题的解。对带聚类特征TSP问题的仿真实验结果表明,该算法能以极快的速度收敛到问题的最优解(近优解)。当TSP问题的聚类数越多,则该算法的性能就越高,但当TSP问题的聚类特征不明显,则该算法退化为一般的蚁群优化算法。
4、提出了一种求解K-TSP问题的蚁群算法。该算法将所有蚂蚁平均分成m组,每组k只,并采用每组中的k只蚂蚁共同构造问题的一个可行解。在算法中,m组蚂蚁相互协作最终达到搜索最优解的目的。实验结果显示,该算法是一种求解K-TSP问题的有效算法。
5、提出了一种求解0-1背包问题的蚁群优化算法。设计了0-1背包问题的构造图,针对构造图为蚂蚁设计了两种状态转移公式并定义了其优先级,蚂蚁以不同的优先级按照这两个状态转移公式在构造图中移动直到死亡,此时,蚂蚁走过的路径即构成0-1背包问题的一个可行解。仿真实验首先对该算法的参数进行了讨论,然后与遗传算法进行了比较,实验结果显示该算法具有较高的性能。
6、提出了一种求解迷宫问题的蚁群优化算法。该算法首先将蚁群平均分成两组,分别从迷宫的起点和终点出发,每只蚂蚁按路径上的信息素独立地选择前进的道路。根据蚂蚁在迷宫中的行走状态,定义了三种不同类型的生命周期。根据蚂蚁每次移动后所处的状态,生成问题的可行解。仿真实验证实了本算法的有效性。
7、提出了一种求解空间机器人路径规划的蚁群优化算法。该算法首先将机器人所在位置(源点)与将要到达的位置(目的点)之间的空间划分成立体网格,同时定义了源点与目的点之间的有效路径。蚁群从源点出发,独立地选择有效路径,最终到达目的点,从而求出从源点到目的点之间的最优路径。实验结果表明,该算法不仅有效,而且具有极快的速度。在该算法中,网格的稠密程度决定了算法解的精度,即网格越稠密,算法的精度越高,但所需时间也越长;反之则越低,所花时间越短。
最后,对全文的研究工作进行了总结,并展望了蚁群优化进一步还要研究的课题。
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
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
引文
周昌乐. 心脑计算举要[M]. 北京:清华大学出版社, 2003.
Penrose R. The Emperor’s New Mind: Concerning Computers, Minds, and the Laws of Physics[M]. Oxford University Press, 1989.
Penrose R. Shadows of the Minds, A Search for the Missing Science of Consciousness[M]. Oxford University Press, 1994.
Minsky M. AI Magazine, Summer, 34-51, 1991.
A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, and M. Trubian. Heuristics from nature for hard combinatorial problems[J]. International Transactions in Operational Research, vol. 3, no. 1, pp. 1-21, 1996.
M. Dorigo and G. Di Caro. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization[M], pages 11–32. McGraw Hill, London, UK, 1999.
Eric Bonabeau, Marco Dorigo, and Guy Theraulaz. Swarm intelligence: from natural to artificial systems[M], New York: Oxford University Press, 1999.
James Kennedy, Russell C. Eberhart, and Yuhui Shi. Swarm Intelligence[M]. San Francisco: Morgan Kaufmann, 2001.
Steven Johnson. Emergence: The Connected Lives of Ants, Brains, Cities, and Software[M]. Simon & Schuster (T), 2001.
Marco Dorigo and Thomas Stützle. Ant Colony Optimization[M]. MIT Press, 2004.
M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy[R]. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
M. Dorigo. Optimiztion, Learning and Natural Algorithma(in Italian)[D]. Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, IT, 1992.
A. Colorni, M. Dorigo, and V. Maniezzo. Distributed optimization by ant colonies[C]. In Proceedings of the First European Conference on Artificial Life, pages 134-142 Elsevier, 1992.
M. Dorigo, G. Di Caro, and L. M. Gambardella. Ant algorithms for discrete optimization[J]. Artificial Life, 5(2):137–172, 1999.
W. J. Gutjahr. A generalized convergence result for the graph-based ant system metaheuristic[R]. Dept. Statistics and Decision Support Systems, Univ.Vienna, Austria, Tech. Rep. 99-09, 1999.
W. J. Gutjahr. A graph-based ant system and its convergence[J]. Future Gener.Comput. Syst.,
vol. 16, no. 8, pp. 873–888, 2000.
W. J. Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution[J]. Info. Processing Lett., vol. 82, no. 3, pp. 145–153, 2002.
Thomas Stützle and Marco Dorigo. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms[J]. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4,pp. 358-365, 2002.
N. Meuleau and M. Dorigo. Ant colony optimization and stochastic gradient descent[J]. Artif. Life, vol. 8, no. 2, pp. 103–121, 2002.
马良, 项培军. 蚂蚁算法在组合优化中的应用[J]. 管理科学学报. 2001, 4(2): 32-37.
M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1):29–41, 1996.
L.M. Gambardella and M. Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies[C]. In Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC’96 ), pages 622-627. IEEE Press, 1996.
M. Dorigo and L. M. Gambardella. Ant colonies for the traveling salesman problem[J]. BioSystems, 43:73–81, 1997.
郝晋, 石立宝, 周家启. 求解复杂TSP问题的随机扰动蚁群算法[J]. 系统工程理论与实践. 2002(9): 88-91.
黄席樾, 胡小兵. 蚁群算法在K-TSP问题中的应用[J]. 计算机仿真. 待刊.
吴斌, 史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J]. 计算机学报. 2001, 24(12): 1328-1333.
马良, 蒋馥. 多目标旅行售货员问题的蚂蚁算法求解[J]. 系统工程理论方法应用. 1999, 8(4): 23-27.
L. M. Gambardella, é. D. Taillard, and M. Dorigo. Ant colonies for the QAP[J]. Journal of the Operational Research Society (JORS), 50 (2): 167-1176, 1999.
V. Maniezzo, A. Colorni, and M. Dorigo. The Ant System Applied to the Quadratic Assignment Problem[R]. Technical Report IRIDIA/94-28, Université Libre de Bruxelles, Belgium, 1994.
V. Maniezzo and A. Colorni. The Ant System applied to the quadratic assignment problem[J]. IEEE Transactions on Data and Knowledge Engineering,11(5):769–778, 1999.
é.D. Taillard and L.M. Gambardella. Adaptive Memories for the Quadratic Assignment Problem[R]. Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.
L. M. Gambardella, é. D. Taillard, and M. Dorigo. Ant colonies for the quadratic assignment problem[J]. Journal of the Operational Research Society, 50(2):167–176, 1999.
马良, 王龙德. 背包问题的蚂蚁优化算法[J]. 计算机应用. 2001, 21(8): 4-5.
胡小兵, 黄席樾. 基于蚁群优化算法的0-1背包问题求解[J]. 系统工程学报. 待刊.
陈义保, 姚建初, 钟毅芳, 周济. 基于蚁群系统的工件排序问题的一种新算法[J]. 系统工程学报. 2001, 17(5): 476-480.
孙新宇, 万筱宁, 孙林岩. 蚁群算法在混流装配线调度问题中的应用[J]. 信息与控制. 2002, 31(6):486-290.
A. Colorni, M. Dorigo, V. Maniezzo, and M. Trubian. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research, Statistics and Computer Science(JORBEL), 34:39-53, 1994.
Li Yanjun, Wu Tiejun. A Nested Hybrid Ant Colony Algorithm for Hybrid Production Scheduling Problem[J]. 自动化学报. 2003,29(1): 95-101.
D. Merkle, M. Middendorf, and H. Schmeck. Ant colony optimization for resource-constrained project scheduling[C]. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 893–900. Morgan Kaufmann Publishers, San Francisco, CA, 2000.
D. Costa and A. Hertz. Ants can color graphs[J]. Journal of the Operational Research Society, 48: 295-305, 1997.
B. Bullnheimer, R. F. Hartl, and C. Strauss. Applying the ant system to the vehicle routing problem[J]. IN I. H. Osman S. Vo, S. Martello and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 109-120. Kluwer Academics, 1998.
B. Bullnheimer, R. F. Hartl, and C. Strauss. Applying the Ant System to the vehicle routing problem[M]. In S. Vo? S. Martello, I. H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 285–296. Kluwer Academic Publishers, Dordrecht, 1999.
B. Bullnheimer, R. F. Hartl, and C. Strauss. An improved ant system algorithm for the vehicle routing problem[A]. Annals of Operations Research, 89:319–328, 1999.
L. M. Gambardella, é. D. Taillard, and G. Agazzi. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows[M]. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 63–76. McGraw Hill, London, UK, 1999.
陈峻, 沈洁, 秦玲. 蚁群算法进行连续参数优化的新途[J]径. 系统工程理论与实践. 2003(3): 48-53.
陈峻, 沈洁, 秦玲. 蚁群算法求解连续空间优化问题的一种新方法[J]. 软件学报. 2002,13(12): 2317-2323.
汪镭, 吴启迪. 蚁群算法在连续空间寻优问题求解中的应用[J]. 控制与决策. 2003, 18(1): 45-48.
林锦, 朱文兴. 凸整数规划问题的混合蚁群算法[J]. 福州大学学报(自然科学版). 1999, 27(6):5-9.
汪镭, 吴启迪. 蚁群算法在系统辨识中的应用[J]. 自动化学报. 2003,29(1): 102-109.
金飞虎, 洪炳熔, 高庆吉. 基于蚁群算法的自由飞行空间机器人路径规划[J]. 机器人. 2002,24(6): 526-529.
胡小兵, 黄席樾. 基于蚂蚁算法的三维空间机器人路径规划研究[J]. 重庆大学学报(自然科学版). 待刊.
胡小兵, 黄席樾. 蚁群算法在迷宫最优路径问题中的应用[J]. 计算机仿真. 待刊.
Rafael S. Parpinelli, Heitor S. Lopes, and Alex A. Freitas. Data Mining With an Ant Colony Optimization Algorithm[J]. IEEE Transactions on Evolutionary Computing, Vol. 6, No. 4, 2002. pp. 321-332.
Di Caro, G. and Dorigo, M. AntNet: Distributed Stigmergetic Control for Communications Networks[J]. Journal of Artificial Intelligence Research, Vol. 9, pp.317-365, 1998.
E. Bonabeau, F. Henaux, S. Guérin, D. Snyers, P. Kuntz, and G. Theraulaz. Routing in telecommunication networks with “Smart” ant-like agents[C]. In Proceedings of IATA’98, Second Int.Workshop on Intelligent Agents for Telecommunication Applications. Lectures Notes in AI vol. 1437, Springer Verlag, 1998.
G. Di Caro and M. Dorigo. AntNet: A mobile agents approach to adaptive routing[R]. Technical Report IRIDIA/97-12, IRIDIA, Universit Libre de Bruxelles, Belgium, 1997.
G. Di Caro and M. Dorigo. Two ant colony algorithms for best-effort routing in datagram networks[C]. In Y. Pan, S. G. Akl, and K. Li, editors, Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’98), pages 541–546. IASTED/ACTA Press, Anheim, 1998.
M. Heusse, S. Guérin, D. Snyers, and P. Kuntz. Adaptive agent-driven routing and load balancing in communication networks[R]. Technical Report RR-98001-IASC, D′epartment Intelligence Artificielle et Sciences Cognitives, ENST Bretagne, 1998. Accepted for publication in the Journal of Complex Systems.
D. Subramanian, P. Druschel, and J. Chen. Ants and reinforcement learning: A case study in routing in dynamic networks[C]. In Proceedings of IJCAI-97, International Joint Conference on Artificial Intelligence, pages 832–838. Morgan Kaufmann, 1997.
R. van der Put. Routing in the faxfactory using mobile agents[R]. Technical Report R&D-SV-98-276, KPN Research, 1998.
吕国英, 刘泽民, 周正. 基于蚂蚁算法的分布式QoS路由选择算法[J]. 通信学报. 2001,22(9): 35-42.
张素兵, 刘泽民. 基于蚂蚁算法的分级QoS路由调度方法[J]. 北京邮电大学学报. 2000,23(4): 12-15.
张素兵, 刘泽民. 基于蚂蚁算法的时延受限分布式多播路由研究[J]. 通信学报. 2001, 22(3): 71-74.
王颖, 谢剑英. 一种基于蚁群算法的多媒体网络多播路由算法[J]. 上海交通大学学报. 2002,36(4): 526-531.
Lu Guoying, Liu Zemin. Qos Multicast Routing Based on Ant Algorithm in Internet[J]. The Journal of China Universities of Posts ant Telecommunication. Vol.7, No. 4, Dec. 2000.
庄昌文, 范明钰, 李春辉, 虞厥邦. 基于协同工作方式的一种蚁群布线系统[J]. 半导体学报. 1999,20(5): 401-406.
J.L.Deneubourg, J.M.Pasteels, J.C.Verhaeghe. Probabilistic Behaviour in Ants: a Strategy of Errors? [J]. Journal of Theoretical Biology, 105, 259–271, 1983.
J.L.Deneubourg, S.Goss. Collective patterns and decision-making[J]. Ethology, Ecology & Evolution, Vol.1, 295–311, 1989.
S.Goss, R.Beckers, J.L.Deneubourg, S.Aron, J.M.Pasteels. How Trail Laying and Trail Following Can Solve Foraging Problems for Ant Colonies[C]. in Behavioural Mechanisms of Food Selection, R.N.Hughes ed., NATO-ASI Series, vol. G 20, Berlin:Springer-Verlag, 1990.
J. -L. Deneubourg, S. Aron, S. Goss, and J.-M. Pasteels. The self-organizing exploratory pattern of the argentine ant[J]. Journal of Insect Behavior, 3:159–168, 1990.
S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels. Self-organized shortcuts in the Argentine ant[J]. Naturwissenschaften, 76:579–581, 1989.
J. M. Pasteels, J.-L. Deneubourg, and S. Goss. Self-organization mechanisms in ant societies (i): Trail recruitment to newly discovered food sources[J]. Experientia Supplementum, 54:155–175, 1987.
C. Watkins. Learning with delayed rewards[D]. England: Psychology Department, University of Cambridge, 1989.
L. M. Gambardella and M. Dorigo. Ant-Q: A reinforcement learning approach to the traveling salesman problem[C]. In A. Prieditis and S. Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning (ML-95), pages 252–260. Morgan Kaufmann Publishers, Palo Alto, CA, 1995.
M. Zlochin, M. Birattari, N. Meuleau, M. Dorigo. Model-based search for combinatorial optimization[R]. Technical Report TR/IRIDIA/2001-15, IRIDIA, Univerit'e Libre de Bruxelles.
M. Zlochin, and M. Dorigo. Model-based search for combinatorial optimization: A comparative study[C]. to appear in Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature(PPSN'2002).
C. Blum, and M. Sampels. When model bias is stronger than selection presure[C]. In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature(PPSN'02), lncs2439,pp.893-902. Springer Verlag, Berlin, Germany,2002.
P. P. Grassé. La reconstruction du nid et les coordinations interindividuelles chez bellicositermes natalensis et cubitermes sp. La théorie de la stigmergie: essai d’interprétation du comportement des termites constructeurs. Insectes Sociaux, 6:41–81, 1959.
肖刚, 李天柁. 系统可靠性分析中的蒙特卡罗方法[M]. 北京:科学出版社, 2003.3.
张乃尧, 阎平凡. 神经网络与模糊控制[M]. 北京:清华大学出版社, 2000.12.
靳蕃. 神经计算智能基础原理方法[M]. 成都:西南交通大学出版社, 2000.1.
潘正军, 康立山, 陈毓屏. 演化计算[M]. 清华大学出版社&广西科学技术出版社, 1998.7.
K. Narendra and M Thathachar. Learning Automata: An Introduction[M]. Prentice Hall, 1989.
M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997.
T. Stützle and H. Hoos. The MAX–MIN ant system and local search for the traveling salesman problem[C]. In T. Baeck, Z. Michalewicz, and X. Yao, editors, Proceedings of IEEE-ICEC-EPS’97, IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference, pages 309–314. IEEE Press, 1997.
T. Stützle and H. Hoos. Improvements on the ant system: Introducing MAX–MIN ant system[C]. In Proceedings of the International Conference on Arti?cial Neural Networks and Genetic Algorithms, pages 245–249. Springer Verlag, Wien, 1997.
T. Stützle and H. Hoos. MAX–MIN Ant system and local search for combinatorial optimization problems[M]. In S. Vo?, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 137–154. Kluwer, Boston, 1998.
T. Stützle MAX-MIN Ant System for Quadratic Assignment Problems[R]. Technical Report AIDA-97-04, Intellectics Group, Department of Computer Science, Darmstadt University of Technology, Germany, July 1997.
B. Bullnheimer, R. F. Hartl, and C. Strauss. A new rank-based version of the Ant System: A computational study[J]. Central European Journal for Operations Research and Economics, 7(1):25–38, 1999.
吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J]. 计算机研究与发展. 1999,36(10): 1240-1245.
王颖, 谢剑英. 一种自适应蚁群算法及其仿真研究[J]. 系统仿真学报. 2002,14(1): 32-33.
覃刚力, 杨家本. 自适应调整信息素的蚁群算法[J]. 信息与控制. 2002,31(3): 198-201.
R. Schoonderwoerd, O. Holland, J. Bruten, and L. Rothkrantz. Ant-based load balancing in telecommunications networks[J]. Adaptive Behavior, 5(2):169–207, 1996.
R. Schoonderwoerd, O. Holland, and J. Bruten. Ant-like agents for load balancing in telecommunications networks[C]. In Proceedings of the First International Conference on Autonomous Agents, pages 209–216. ACM Press, 1997.
T. White, B. Pagurek, and F. Oppacher. Connection management using adaptive mobile agents[C]. In H.R. Arabnia, editor, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’98), pages 802–809. CSREA Press, 1998.
T. Stützle. Local Search Algorithms for Combinatorial Problems: Analysis, Improvements, and New Applications[J]. Infix, Sankt Augustin, Germany, 1999.
T. Stützle and H. H. Hoos. MAX–MIN Ant System[J]. Future Generation Computer Systems, 16(8):889–914, 2000.
O. Cordón, I. Fernández de Viana, F. Herrera, and L. Moreno. A new ACO model integrating evolutionary computation concepts: The best-worst ant system[C]. In M. Dorigo, M. Middendorf, and T. St¨utzle, editors, Abstract proceedings of ANTS2000 – From Ant Colonies to Artificial Ants: A Series of International Workshops on Ant Algorithms, pages 22–29. Universit Librede Bruxelles, 2000.
V. Maniezzo. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem[J]. INFORMS Journal on Computing, 11(4):358–369, 1999.
T. Stützle. An ant approach to the flow shop problem[C]. In Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT’98), volume 3, pages 1560–1564. Verlag Mainz, Aachen, 1998.
A. Bauer, B. Bullnheimer, R. F. Hartl, and C. Strauss. An ant colony optimization approach for the single machine total tardiness problem[C]. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages 1445–1450. IEEE Press, Piscataway, NJ, 1999.
M. den Besten, T. Stützle, and M. Dorigo. Ant colony optimization for the total weighted tardiness problem[C]. In M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo, and H.S. Schwefel, editors, Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, volume 1917 of Lecture Notes in Computer Science,
pages 611–620. Springer Verlag, Berlin, Germany, 2000.
R. Schoonderwoerd, O. Holland, J. Bruten, and L. Rothkrantz. Antbased load balancing in telecommunications networks[J]. Adaptive Behavior, 5(2):169–207, 1996.
L. M. Gambardella and M. Dorigo. HAS-SOP: An hybrid Ant System for the sequential ordering problem[R]. Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland, 1997.
L. M. Gambardella and M. Dorigo. Ant Colony System hybridized with a new local search for the sequential ordering problem[J]. INFORMS Journal on Computing, 12(3):237–255, 2000.
R. Michel and M. Middendorf. An island model based Ant System with lookahead for the shortest supersequence problem[C]. In A. E. Eiben, T. B?ck, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, volume 1498 of Lecture Notes in Computer Science, pages 692–701. Springer Verlag, Berlin, Germany, 1998.
R. Michel and M. Middendorf. An ACO algorithm for the shortest supersequence problem[M]. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 51–61. McGraw Hill, London, UK, 1999.
V. Maniezzo and A. Carbonaro. An ANTS heuristic for the frequency assignment problem[J]. Future Generation Computer Systems, 16(8):927 – 935, 2000.
G. Leguizamón and Z. Michalewicz. A new version of Ant System for subset problems[C]. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages 1459–1464. IEEE Press, Piscataway, NJ, 1999.
G. Navarro Varela and M. C. Sinclair. Ant colony optimisation for virtual wave length path routing and wavelength allocation[C]. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages 1809–1816. IEEE Press, Piscataway, NJ, 1999.
Y.-C. Liang and A. E. Smith. An Ant System approach to redundancy allocation[C]. In Proceedings of the 1999 Congress on Evolutionary Computation, pages 1478–1484. IEEE Press, Piscataway, NJ, 1999.
C. Solnon. Solving permutation constraint satisfaction problems with artificial ants[C]. In W. Horn, editor, Proceedings of the 14th European Conference on Artificial Intelligence, pages 118–122. IOS Press, Amsterdam, The Netherlands, 2000.
J. H. Holland. Adatation in Nature and Artificial Systems[M]. University of Michigan Press, Ann Arbor, MI, 1975.
陈国良, 王煦法, 庄镇泉, 王东生. 遗传算法及其应用[M]. 北京:人民邮电出版社, 2001.
王凌. 智能优化算法及其应用[M]. 北京:清华大学出版社, 2001.
邢文训, 谢金星. 现代优化计算方法[M]. 北京:清华大学出版社, 2001.
胡小兵, 黄席樾, 张著洪. 一种新的自适应蚁群算法及其应用[J]. 计算机仿真. 已录用, 待刊.
Christian Blum, and Andrea Roli. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison[R]. Technical Report TR/IRIDIA/2001-13, October 2001.
Hu Xiaobing, Huang Xiyue. Ant colony algorithm based on hybrid behavior apply to traveling salesman problem[C]. The 3th International Conference on Wavelet Analysis and Its Applications, the 2nd International Conference on Active Media Technology. Chongqing , China 2004 (EI, ISTP将收录).
M. Bolondi and M. Bondanza. Parallelizzazione di un algoritmo per la risoluzione del problema del commesso viaggiatore. Master's thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1993.
M. Dorigo. Parallel ant system: An experimental study. Unpublished manuscript, 1993.
B. Bullnheimer, G. Kotsis, and C. Strauss. Parallelization strategies for the ant system[R]. Technical Report POM 9-97, Institute of Management Science, University of Vienna, Austria, 1997.
F. Krüger, D. Merkle, and M. Middendorf. Studies on a parallel ant system for the BSP model. Unpublished manuscript.
T. Stützle. Parallelization Strategies for Ant Colony Optimization[R]. Research report AIDA-98-03.Darmstadt: Department of Computer Science, Darmstadt University of Technology, 1998.
Middendorf M., Reischle F. & Schmech H. Information Exchange in Multi Colony Ant Algorithm[C]. In Proceedings of IEEE Symposium on Parallel and Distributed Processing. Third Workshop on Biologically Inspired Solution to Parallel Processing Problems, IPDPS 2000, 645-652. 2000.
孙即祥. 现代模式识别[M]. 长沙:国防科技大学出版社, 2002.
庄昌文, 范明钰, 李春辉, 虞厥邦. 采用面向Agent技术的并行布线系统[J]. 计算机研究与发展, 第36卷第12期,1999年12月.
Frieze A M. An Extension of Christofides Heuristics to the k-Person Traveling Salesman Problem[J]. Dis. Apply Math., 1983(6): 79~83.
王德荣,刘方池. K-TSP问题的近似算法[J]. 华中理工大学学报. 2000, 28(8):72~74.
霍红卫, 许进, 保铮. 基于遗传算法的0/1背包问题求解[J]. 西安电子科技大学学报, 1999, 26(4): 493-497.
严蔚敏, 陈文博. 数据结构及应用算法教程[M]. 北京:清华大学出版社, 2001.
Lee S, Park J. Neural computation for collision-free path planning[J]. Journal of Intelligent
Manufacturing. 1991, (2), 315-326.
孙增圻. 智能控制理论与技术[M]. 北京:清华大学出版, 1997
J. C. Latombe. Robot Motion Planning[M]. Kluwer Academic Publishers, 1991
G. Foux, M. Heymann, A. Bruckstein. Two-Dimensional Robot Navigation Among Unknown Stationary Polygonal Obstacles[J]. IEEE Transactions on Robotics and Automation, 1993,9(1): 96-102
M. Yamamoto, N. Ushimi, A. Mohri. Sensor-Based Navigation for Mobile Robots Using Target Direction Sensor[J]. Journal of the Robotics Society of Japan, 1998,16(8):1083-1090.
X. D. Yang, M. Yamamoto, A. Mohri. Path Planning for Mobile robot in Uncertain Workspace Using Obstacle Topology[J]. Journal of the Robotics Society of Japan, 1995,13(8):1130-1137.
K. Nagatani, S. Yuta. Path and Sensing Point Planning for Mobile Robot Navigation to Minimize the Risk of Collision[J]. Journal of the Robotics Society of Japan, 1997,15(2):197-206.
孟庆浩, 彭商贤, 刘大伟. 基于Q-M图启发式搜索的移动机器人全局路径规划[J]. 机器人,1998,20(4):273-279
P. Khosla, R. Volpe. Super quadratic Artificial Potentials for Obstacle Avoidance and Approach[C]. In Proceedings of IEEE International Conference on Robotics and Automation, 1988, 1778-1784.
E. Rimon, D. E. Doditschek. Exact Robot Navigation Using Artificial Potential Fields[J]. IEEE Transactionsin Robotics and Automation,1992, 8(5):501-518.
Penrose R. The Emperor’s New Mind: Concerning Computers, Minds, and the Laws of Physics[M]. Oxford University Press, 1989.
Penrose R. Shadows of the Minds, A Search for the Missing Science of Consciousness[M]. Oxford University Press, 1994.
Minsky M. AI Magazine, Summer, 34-51, 1991.
A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, and M. Trubian. Heuristics from nature for hard combinatorial problems[J]. International Transactions in Operational Research, vol. 3, no. 1, pp. 1-21, 1996.
M. Dorigo and G. Di Caro. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization[M], pages 11–32. McGraw Hill, London, UK, 1999.
Eric Bonabeau, Marco Dorigo, and Guy Theraulaz. Swarm intelligence: from natural to artificial systems[M], New York: Oxford University Press, 1999.
James Kennedy, Russell C. Eberhart, and Yuhui Shi. Swarm Intelligence[M]. San Francisco: Morgan Kaufmann, 2001.
Steven Johnson. Emergence: The Connected Lives of Ants, Brains, Cities, and Software[M]. Simon & Schuster (T), 2001.
Marco Dorigo and Thomas Stützle. Ant Colony Optimization[M]. MIT Press, 2004.
M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy[R]. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
M. Dorigo. Optimiztion, Learning and Natural Algorithma(in Italian)[D]. Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, IT, 1992.
A. Colorni, M. Dorigo, and V. Maniezzo. Distributed optimization by ant colonies[C]. In Proceedings of the First European Conference on Artificial Life, pages 134-142 Elsevier, 1992.
M. Dorigo, G. Di Caro, and L. M. Gambardella. Ant algorithms for discrete optimization[J]. Artificial Life, 5(2):137–172, 1999.
W. J. Gutjahr. A generalized convergence result for the graph-based ant system metaheuristic[R]. Dept. Statistics and Decision Support Systems, Univ.Vienna, Austria, Tech. Rep. 99-09, 1999.
W. J. Gutjahr. A graph-based ant system and its convergence[J]. Future Gener.Comput. Syst.,
vol. 16, no. 8, pp. 873–888, 2000.
W. J. Gutjahr. ACO algorithms with guaranteed convergence to the optimal solution[J]. Info. Processing Lett., vol. 82, no. 3, pp. 145–153, 2002.
Thomas Stützle and Marco Dorigo. A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms[J]. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4,pp. 358-365, 2002.
N. Meuleau and M. Dorigo. Ant colony optimization and stochastic gradient descent[J]. Artif. Life, vol. 8, no. 2, pp. 103–121, 2002.
马良, 项培军. 蚂蚁算法在组合优化中的应用[J]. 管理科学学报. 2001, 4(2): 32-37.
M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1):29–41, 1996.
L.M. Gambardella and M. Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies[C]. In Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC’96 ), pages 622-627. IEEE Press, 1996.
M. Dorigo and L. M. Gambardella. Ant colonies for the traveling salesman problem[J]. BioSystems, 43:73–81, 1997.
郝晋, 石立宝, 周家启. 求解复杂TSP问题的随机扰动蚁群算法[J]. 系统工程理论与实践. 2002(9): 88-91.
黄席樾, 胡小兵. 蚁群算法在K-TSP问题中的应用[J]. 计算机仿真. 待刊.
吴斌, 史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J]. 计算机学报. 2001, 24(12): 1328-1333.
马良, 蒋馥. 多目标旅行售货员问题的蚂蚁算法求解[J]. 系统工程理论方法应用. 1999, 8(4): 23-27.
L. M. Gambardella, é. D. Taillard, and M. Dorigo. Ant colonies for the QAP[J]. Journal of the Operational Research Society (JORS), 50 (2): 167-1176, 1999.
V. Maniezzo, A. Colorni, and M. Dorigo. The Ant System Applied to the Quadratic Assignment Problem[R]. Technical Report IRIDIA/94-28, Université Libre de Bruxelles, Belgium, 1994.
V. Maniezzo and A. Colorni. The Ant System applied to the quadratic assignment problem[J]. IEEE Transactions on Data and Knowledge Engineering,11(5):769–778, 1999.
é.D. Taillard and L.M. Gambardella. Adaptive Memories for the Quadratic Assignment Problem[R]. Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.
L. M. Gambardella, é. D. Taillard, and M. Dorigo. Ant colonies for the quadratic assignment problem[J]. Journal of the Operational Research Society, 50(2):167–176, 1999.
马良, 王龙德. 背包问题的蚂蚁优化算法[J]. 计算机应用. 2001, 21(8): 4-5.
胡小兵, 黄席樾. 基于蚁群优化算法的0-1背包问题求解[J]. 系统工程学报. 待刊.
陈义保, 姚建初, 钟毅芳, 周济. 基于蚁群系统的工件排序问题的一种新算法[J]. 系统工程学报. 2001, 17(5): 476-480.
孙新宇, 万筱宁, 孙林岩. 蚁群算法在混流装配线调度问题中的应用[J]. 信息与控制. 2002, 31(6):486-290.
A. Colorni, M. Dorigo, V. Maniezzo, and M. Trubian. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research, Statistics and Computer Science(JORBEL), 34:39-53, 1994.
Li Yanjun, Wu Tiejun. A Nested Hybrid Ant Colony Algorithm for Hybrid Production Scheduling Problem[J]. 自动化学报. 2003,29(1): 95-101.
D. Merkle, M. Middendorf, and H. Schmeck. Ant colony optimization for resource-constrained project scheduling[C]. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 893–900. Morgan Kaufmann Publishers, San Francisco, CA, 2000.
D. Costa and A. Hertz. Ants can color graphs[J]. Journal of the Operational Research Society, 48: 295-305, 1997.
B. Bullnheimer, R. F. Hartl, and C. Strauss. Applying the ant system to the vehicle routing problem[J]. IN I. H. Osman S. Vo, S. Martello and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 109-120. Kluwer Academics, 1998.
B. Bullnheimer, R. F. Hartl, and C. Strauss. Applying the Ant System to the vehicle routing problem[M]. In S. Vo? S. Martello, I. H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 285–296. Kluwer Academic Publishers, Dordrecht, 1999.
B. Bullnheimer, R. F. Hartl, and C. Strauss. An improved ant system algorithm for the vehicle routing problem[A]. Annals of Operations Research, 89:319–328, 1999.
L. M. Gambardella, é. D. Taillard, and G. Agazzi. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows[M]. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 63–76. McGraw Hill, London, UK, 1999.
陈峻, 沈洁, 秦玲. 蚁群算法进行连续参数优化的新途[J]径. 系统工程理论与实践. 2003(3): 48-53.
陈峻, 沈洁, 秦玲. 蚁群算法求解连续空间优化问题的一种新方法[J]. 软件学报. 2002,13(12): 2317-2323.
汪镭, 吴启迪. 蚁群算法在连续空间寻优问题求解中的应用[J]. 控制与决策. 2003, 18(1): 45-48.
林锦, 朱文兴. 凸整数规划问题的混合蚁群算法[J]. 福州大学学报(自然科学版). 1999, 27(6):5-9.
汪镭, 吴启迪. 蚁群算法在系统辨识中的应用[J]. 自动化学报. 2003,29(1): 102-109.
金飞虎, 洪炳熔, 高庆吉. 基于蚁群算法的自由飞行空间机器人路径规划[J]. 机器人. 2002,24(6): 526-529.
胡小兵, 黄席樾. 基于蚂蚁算法的三维空间机器人路径规划研究[J]. 重庆大学学报(自然科学版). 待刊.
胡小兵, 黄席樾. 蚁群算法在迷宫最优路径问题中的应用[J]. 计算机仿真. 待刊.
Rafael S. Parpinelli, Heitor S. Lopes, and Alex A. Freitas. Data Mining With an Ant Colony Optimization Algorithm[J]. IEEE Transactions on Evolutionary Computing, Vol. 6, No. 4, 2002. pp. 321-332.
Di Caro, G. and Dorigo, M. AntNet: Distributed Stigmergetic Control for Communications Networks[J]. Journal of Artificial Intelligence Research, Vol. 9, pp.317-365, 1998.
E. Bonabeau, F. Henaux, S. Guérin, D. Snyers, P. Kuntz, and G. Theraulaz. Routing in telecommunication networks with “Smart” ant-like agents[C]. In Proceedings of IATA’98, Second Int.Workshop on Intelligent Agents for Telecommunication Applications. Lectures Notes in AI vol. 1437, Springer Verlag, 1998.
G. Di Caro and M. Dorigo. AntNet: A mobile agents approach to adaptive routing[R]. Technical Report IRIDIA/97-12, IRIDIA, Universit Libre de Bruxelles, Belgium, 1997.
G. Di Caro and M. Dorigo. Two ant colony algorithms for best-effort routing in datagram networks[C]. In Y. Pan, S. G. Akl, and K. Li, editors, Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS’98), pages 541–546. IASTED/ACTA Press, Anheim, 1998.
M. Heusse, S. Guérin, D. Snyers, and P. Kuntz. Adaptive agent-driven routing and load balancing in communication networks[R]. Technical Report RR-98001-IASC, D′epartment Intelligence Artificielle et Sciences Cognitives, ENST Bretagne, 1998. Accepted for publication in the Journal of Complex Systems.
D. Subramanian, P. Druschel, and J. Chen. Ants and reinforcement learning: A case study in routing in dynamic networks[C]. In Proceedings of IJCAI-97, International Joint Conference on Artificial Intelligence, pages 832–838. Morgan Kaufmann, 1997.
R. van der Put. Routing in the faxfactory using mobile agents[R]. Technical Report R&D-SV-98-276, KPN Research, 1998.
吕国英, 刘泽民, 周正. 基于蚂蚁算法的分布式QoS路由选择算法[J]. 通信学报. 2001,22(9): 35-42.
张素兵, 刘泽民. 基于蚂蚁算法的分级QoS路由调度方法[J]. 北京邮电大学学报. 2000,23(4): 12-15.
张素兵, 刘泽民. 基于蚂蚁算法的时延受限分布式多播路由研究[J]. 通信学报. 2001, 22(3): 71-74.
王颖, 谢剑英. 一种基于蚁群算法的多媒体网络多播路由算法[J]. 上海交通大学学报. 2002,36(4): 526-531.
Lu Guoying, Liu Zemin. Qos Multicast Routing Based on Ant Algorithm in Internet[J]. The Journal of China Universities of Posts ant Telecommunication. Vol.7, No. 4, Dec. 2000.
庄昌文, 范明钰, 李春辉, 虞厥邦. 基于协同工作方式的一种蚁群布线系统[J]. 半导体学报. 1999,20(5): 401-406.
J.L.Deneubourg, J.M.Pasteels, J.C.Verhaeghe. Probabilistic Behaviour in Ants: a Strategy of Errors? [J]. Journal of Theoretical Biology, 105, 259–271, 1983.
J.L.Deneubourg, S.Goss. Collective patterns and decision-making[J]. Ethology, Ecology & Evolution, Vol.1, 295–311, 1989.
S.Goss, R.Beckers, J.L.Deneubourg, S.Aron, J.M.Pasteels. How Trail Laying and Trail Following Can Solve Foraging Problems for Ant Colonies[C]. in Behavioural Mechanisms of Food Selection, R.N.Hughes ed., NATO-ASI Series, vol. G 20, Berlin:Springer-Verlag, 1990.
J. -L. Deneubourg, S. Aron, S. Goss, and J.-M. Pasteels. The self-organizing exploratory pattern of the argentine ant[J]. Journal of Insect Behavior, 3:159–168, 1990.
S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels. Self-organized shortcuts in the Argentine ant[J]. Naturwissenschaften, 76:579–581, 1989.
J. M. Pasteels, J.-L. Deneubourg, and S. Goss. Self-organization mechanisms in ant societies (i): Trail recruitment to newly discovered food sources[J]. Experientia Supplementum, 54:155–175, 1987.
C. Watkins. Learning with delayed rewards[D]. England: Psychology Department, University of Cambridge, 1989.
L. M. Gambardella and M. Dorigo. Ant-Q: A reinforcement learning approach to the traveling salesman problem[C]. In A. Prieditis and S. Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning (ML-95), pages 252–260. Morgan Kaufmann Publishers, Palo Alto, CA, 1995.
M. Zlochin, M. Birattari, N. Meuleau, M. Dorigo. Model-based search for combinatorial optimization[R]. Technical Report TR/IRIDIA/2001-15, IRIDIA, Univerit'e Libre de Bruxelles.
M. Zlochin, and M. Dorigo. Model-based search for combinatorial optimization: A comparative study[C]. to appear in Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature(PPSN'2002).
C. Blum, and M. Sampels. When model bias is stronger than selection presure[C]. In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature(PPSN'02), lncs2439,pp.893-902. Springer Verlag, Berlin, Germany,2002.
P. P. Grassé. La reconstruction du nid et les coordinations interindividuelles chez bellicositermes natalensis et cubitermes sp. La théorie de la stigmergie: essai d’interprétation du comportement des termites constructeurs. Insectes Sociaux, 6:41–81, 1959.
肖刚, 李天柁. 系统可靠性分析中的蒙特卡罗方法[M]. 北京:科学出版社, 2003.3.
张乃尧, 阎平凡. 神经网络与模糊控制[M]. 北京:清华大学出版社, 2000.12.
靳蕃. 神经计算智能基础原理方法[M]. 成都:西南交通大学出版社, 2000.1.
潘正军, 康立山, 陈毓屏. 演化计算[M]. 清华大学出版社&广西科学技术出版社, 1998.7.
K. Narendra and M Thathachar. Learning Automata: An Introduction[M]. Prentice Hall, 1989.
M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997.
T. Stützle and H. Hoos. The MAX–MIN ant system and local search for the traveling salesman problem[C]. In T. Baeck, Z. Michalewicz, and X. Yao, editors, Proceedings of IEEE-ICEC-EPS’97, IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference, pages 309–314. IEEE Press, 1997.
T. Stützle and H. Hoos. Improvements on the ant system: Introducing MAX–MIN ant system[C]. In Proceedings of the International Conference on Arti?cial Neural Networks and Genetic Algorithms, pages 245–249. Springer Verlag, Wien, 1997.
T. Stützle and H. Hoos. MAX–MIN Ant system and local search for combinatorial optimization problems[M]. In S. Vo?, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 137–154. Kluwer, Boston, 1998.
T. Stützle MAX-MIN Ant System for Quadratic Assignment Problems[R]. Technical Report AIDA-97-04, Intellectics Group, Department of Computer Science, Darmstadt University of Technology, Germany, July 1997.
B. Bullnheimer, R. F. Hartl, and C. Strauss. A new rank-based version of the Ant System: A computational study[J]. Central European Journal for Operations Research and Economics, 7(1):25–38, 1999.
吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J]. 计算机研究与发展. 1999,36(10): 1240-1245.
王颖, 谢剑英. 一种自适应蚁群算法及其仿真研究[J]. 系统仿真学报. 2002,14(1): 32-33.
覃刚力, 杨家本. 自适应调整信息素的蚁群算法[J]. 信息与控制. 2002,31(3): 198-201.
R. Schoonderwoerd, O. Holland, J. Bruten, and L. Rothkrantz. Ant-based load balancing in telecommunications networks[J]. Adaptive Behavior, 5(2):169–207, 1996.
R. Schoonderwoerd, O. Holland, and J. Bruten. Ant-like agents for load balancing in telecommunications networks[C]. In Proceedings of the First International Conference on Autonomous Agents, pages 209–216. ACM Press, 1997.
T. White, B. Pagurek, and F. Oppacher. Connection management using adaptive mobile agents[C]. In H.R. Arabnia, editor, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’98), pages 802–809. CSREA Press, 1998.
T. Stützle. Local Search Algorithms for Combinatorial Problems: Analysis, Improvements, and New Applications[J]. Infix, Sankt Augustin, Germany, 1999.
T. Stützle and H. H. Hoos. MAX–MIN Ant System[J]. Future Generation Computer Systems, 16(8):889–914, 2000.
O. Cordón, I. Fernández de Viana, F. Herrera, and L. Moreno. A new ACO model integrating evolutionary computation concepts: The best-worst ant system[C]. In M. Dorigo, M. Middendorf, and T. St¨utzle, editors, Abstract proceedings of ANTS2000 – From Ant Colonies to Artificial Ants: A Series of International Workshops on Ant Algorithms, pages 22–29. Universit Librede Bruxelles, 2000.
V. Maniezzo. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem[J]. INFORMS Journal on Computing, 11(4):358–369, 1999.
T. Stützle. An ant approach to the flow shop problem[C]. In Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT’98), volume 3, pages 1560–1564. Verlag Mainz, Aachen, 1998.
A. Bauer, B. Bullnheimer, R. F. Hartl, and C. Strauss. An ant colony optimization approach for the single machine total tardiness problem[C]. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages 1445–1450. IEEE Press, Piscataway, NJ, 1999.
M. den Besten, T. Stützle, and M. Dorigo. Ant colony optimization for the total weighted tardiness problem[C]. In M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo, and H.S. Schwefel, editors, Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, volume 1917 of Lecture Notes in Computer Science,
pages 611–620. Springer Verlag, Berlin, Germany, 2000.
R. Schoonderwoerd, O. Holland, J. Bruten, and L. Rothkrantz. Antbased load balancing in telecommunications networks[J]. Adaptive Behavior, 5(2):169–207, 1996.
L. M. Gambardella and M. Dorigo. HAS-SOP: An hybrid Ant System for the sequential ordering problem[R]. Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland, 1997.
L. M. Gambardella and M. Dorigo. Ant Colony System hybridized with a new local search for the sequential ordering problem[J]. INFORMS Journal on Computing, 12(3):237–255, 2000.
R. Michel and M. Middendorf. An island model based Ant System with lookahead for the shortest supersequence problem[C]. In A. E. Eiben, T. B?ck, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, volume 1498 of Lecture Notes in Computer Science, pages 692–701. Springer Verlag, Berlin, Germany, 1998.
R. Michel and M. Middendorf. An ACO algorithm for the shortest supersequence problem[M]. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 51–61. McGraw Hill, London, UK, 1999.
V. Maniezzo and A. Carbonaro. An ANTS heuristic for the frequency assignment problem[J]. Future Generation Computer Systems, 16(8):927 – 935, 2000.
G. Leguizamón and Z. Michalewicz. A new version of Ant System for subset problems[C]. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages 1459–1464. IEEE Press, Piscataway, NJ, 1999.
G. Navarro Varela and M. C. Sinclair. Ant colony optimisation for virtual wave length path routing and wavelength allocation[C]. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages 1809–1816. IEEE Press, Piscataway, NJ, 1999.
Y.-C. Liang and A. E. Smith. An Ant System approach to redundancy allocation[C]. In Proceedings of the 1999 Congress on Evolutionary Computation, pages 1478–1484. IEEE Press, Piscataway, NJ, 1999.
C. Solnon. Solving permutation constraint satisfaction problems with artificial ants[C]. In W. Horn, editor, Proceedings of the 14th European Conference on Artificial Intelligence, pages 118–122. IOS Press, Amsterdam, The Netherlands, 2000.
J. H. Holland. Adatation in Nature and Artificial Systems[M]. University of Michigan Press, Ann Arbor, MI, 1975.
陈国良, 王煦法, 庄镇泉, 王东生. 遗传算法及其应用[M]. 北京:人民邮电出版社, 2001.
王凌. 智能优化算法及其应用[M]. 北京:清华大学出版社, 2001.
邢文训, 谢金星. 现代优化计算方法[M]. 北京:清华大学出版社, 2001.
胡小兵, 黄席樾, 张著洪. 一种新的自适应蚁群算法及其应用[J]. 计算机仿真. 已录用, 待刊.
Christian Blum, and Andrea Roli. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison[R]. Technical Report TR/IRIDIA/2001-13, October 2001.
Hu Xiaobing, Huang Xiyue. Ant colony algorithm based on hybrid behavior apply to traveling salesman problem[C]. The 3th International Conference on Wavelet Analysis and Its Applications, the 2nd International Conference on Active Media Technology. Chongqing , China 2004 (EI, ISTP将收录).
M. Bolondi and M. Bondanza. Parallelizzazione di un algoritmo per la risoluzione del problema del commesso viaggiatore. Master's thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1993.
M. Dorigo. Parallel ant system: An experimental study. Unpublished manuscript, 1993.
B. Bullnheimer, G. Kotsis, and C. Strauss. Parallelization strategies for the ant system[R]. Technical Report POM 9-97, Institute of Management Science, University of Vienna, Austria, 1997.
F. Krüger, D. Merkle, and M. Middendorf. Studies on a parallel ant system for the BSP model. Unpublished manuscript.
T. Stützle. Parallelization Strategies for Ant Colony Optimization[R]. Research report AIDA-98-03.Darmstadt: Department of Computer Science, Darmstadt University of Technology, 1998.
Middendorf M., Reischle F. & Schmech H. Information Exchange in Multi Colony Ant Algorithm[C]. In Proceedings of IEEE Symposium on Parallel and Distributed Processing. Third Workshop on Biologically Inspired Solution to Parallel Processing Problems, IPDPS 2000, 645-652. 2000.
孙即祥. 现代模式识别[M]. 长沙:国防科技大学出版社, 2002.
庄昌文, 范明钰, 李春辉, 虞厥邦. 采用面向Agent技术的并行布线系统[J]. 计算机研究与发展, 第36卷第12期,1999年12月.
Frieze A M. An Extension of Christofides Heuristics to the k-Person Traveling Salesman Problem[J]. Dis. Apply Math., 1983(6): 79~83.
王德荣,刘方池. K-TSP问题的近似算法[J]. 华中理工大学学报. 2000, 28(8):72~74.
霍红卫, 许进, 保铮. 基于遗传算法的0/1背包问题求解[J]. 西安电子科技大学学报, 1999, 26(4): 493-497.
严蔚敏, 陈文博. 数据结构及应用算法教程[M]. 北京:清华大学出版社, 2001.
Lee S, Park J. Neural computation for collision-free path planning[J]. Journal of Intelligent
Manufacturing. 1991, (2), 315-326.
孙增圻. 智能控制理论与技术[M]. 北京:清华大学出版, 1997
J. C. Latombe. Robot Motion Planning[M]. Kluwer Academic Publishers, 1991
G. Foux, M. Heymann, A. Bruckstein. Two-Dimensional Robot Navigation Among Unknown Stationary Polygonal Obstacles[J]. IEEE Transactions on Robotics and Automation, 1993,9(1): 96-102
M. Yamamoto, N. Ushimi, A. Mohri. Sensor-Based Navigation for Mobile Robots Using Target Direction Sensor[J]. Journal of the Robotics Society of Japan, 1998,16(8):1083-1090.
X. D. Yang, M. Yamamoto, A. Mohri. Path Planning for Mobile robot in Uncertain Workspace Using Obstacle Topology[J]. Journal of the Robotics Society of Japan, 1995,13(8):1130-1137.
K. Nagatani, S. Yuta. Path and Sensing Point Planning for Mobile Robot Navigation to Minimize the Risk of Collision[J]. Journal of the Robotics Society of Japan, 1997,15(2):197-206.
孟庆浩, 彭商贤, 刘大伟. 基于Q-M图启发式搜索的移动机器人全局路径规划[J]. 机器人,1998,20(4):273-279
P. Khosla, R. Volpe. Super quadratic Artificial Potentials for Obstacle Avoidance and Approach[C]. In Proceedings of IEEE International Conference on Robotics and Automation, 1988, 1778-1784.
E. Rimon, D. E. Doditschek. Exact Robot Navigation Using Artificial Potential Fields[J]. IEEE Transactionsin Robotics and Automation,1992, 8(5):501-518.