发帖
雷达卡
摘要翻译：
蚁群优化(ACO)的时间复杂度为O(t*m*N*N)，其典型应用是求解旅行商问题(TSP)，其中t、m和N分别表示迭代次数、蚂蚁数目和城市数目。缩短运行时间是研究的重点之一，其中一个方法是降低参数t和N，特别是N。针对这一重点，本文提出了以下方法。首先设计了一种新的聚类算法--特殊局部聚类算法(SLC)，然后应用该算法将所有城市划分为紧凑类，其中紧凑类是指所有城市在一个小区域内紧密聚类的一类。其次，让蚁群算法作用于每个类，得到一个局部TSP路径。第三，将所有局部TSP路径连接起来形成解。第四，消除了聚类引起的解的不准确性。仿真结果表明，该方法使蚁群算法的运行速度至少提高了200倍。而这种高速得益于两个因素。一个是类的大小较小，参数N被削减。当蚁群算法作用于紧类时，每个迭代步的路径长度都是收敛的。二是以路径长度的收敛性作为蚁群算法的终止准则，降低了参数t。
---
英文标题：
《Apply Local Clustering Method to Improve the Running Speed of Ant Colony
Optimization》
---
作者：
Chao-Yang Pang, Wei Hu, Xia Li, and Be-Qiong Hu
---
最新提交年份：
2009
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Neural and Evolutionary Computing 神经与进化计算
分类描述：Covers neural networks, connectionism, genetic algorithms, artificial life, adaptive behavior. Roughly includes some material in ACM Subject Class C.1.3, I.2.6, I.5.
涵盖神经网络，连接主义，遗传算法，人工生命，自适应行为。大致包括ACM学科类C.1.3、I.2.6、I.5中的一些材料。
--
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Ant Colony Optimization (ACO) has time complexity O(t*m*N*N), and its typical application is to solve Traveling Salesman Problem (TSP), where t, m, and N denotes the iteration number, number of ants, number of cities respectively. Cutting down running time is one of study focuses, and one way is to decrease parameter t and N, especially N. For this focus, the following method is presented in this paper. Firstly, design a novel clustering algorithm named Special Local Clustering algorithm (SLC), then apply it to classify all cities into compact classes, where compact class is the class that all cities in this class cluster tightly in a small region. Secondly, let ACO act on every class to get a local TSP route. Thirdly, all local TSP routes are jointed to form solution. Fourthly, the inaccuracy of solution caused by clustering is eliminated. Simulation shows that the presented method improves the running speed of ACO by 200 factors at least. And this high speed is benefit from two factors. One is that class has small size and parameter N is cut down. The route length at every iteration step is convergent when ACO acts on compact class. The other factor is that, using the convergence of route length as termination criterion of ACO and parameter t is cut down.
---
PDF链接：
https://arxiv.org/pdf/0907.1012
京公网安备 11010802022788号
