Applying Data Clustering Feature to Speed Up Ant Colony Optimization
Ant colony optimization (ACO) is often used to solve optimization problems, such as traveling salesman problem (TSP). When it is applied to TSP, its runtime is proportional to the squared size of problem N so as to look less efficient. The following statistical feature is observed during the authors...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Abstract and Applied Analysis |
| Online Access: | http://dx.doi.org/10.1155/2014/545391 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832545700787781632 |
|---|---|
| author | Chao-Yang Pang Ben-Qiong Hu Jie Zhang Wei Hu Zheng-Chao Shan |
| author_facet | Chao-Yang Pang Ben-Qiong Hu Jie Zhang Wei Hu Zheng-Chao Shan |
| author_sort | Chao-Yang Pang |
| collection | DOAJ |
| description | Ant colony optimization (ACO) is often used to solve optimization problems, such as traveling salesman problem (TSP). When it is applied to TSP, its runtime is proportional to the squared size of problem N so as to look less efficient. The following statistical feature is observed during the authors’ long-term gene data analysis using ACO: when the data size N becomes big, local clustering appears frequently. That is, some data cluster tightly in a small area and form a class, and the correlation between different classes is weak. And this feature makes the idea of divide and rule feasible for the estimate of solution of TSP. In this paper an improved ACO algorithm is presented, which firstly divided all data into local clusters and calculated small TSP routes and then assembled a big TSP route with them. Simulation shows that the presented method improves the running speed of ACO by 200 factors under the condition that data set holds feature of local clustering. |
| format | Article |
| id | doaj-art-24254972757b4b90abcb31a925e32aca |
| institution | Kabale University |
| issn | 1085-3375 1687-0409 |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Abstract and Applied Analysis |
| spelling | doaj-art-24254972757b4b90abcb31a925e32aca2025-02-03T07:24:54ZengWileyAbstract and Applied Analysis1085-33751687-04092014-01-01201410.1155/2014/545391545391Applying Data Clustering Feature to Speed Up Ant Colony OptimizationChao-Yang Pang0Ben-Qiong Hu1Jie Zhang2Wei Hu3Zheng-Chao Shan4College of Computer Science, Sichuan Normal University, Chengdu 610101, ChinaCollege of Management Science, Chengdu University of Technology, Chengdu 610059, ChinaDepartment of Control Engineering, Chengdu University of Information Technology, Chengdu 610225, ChinaNorth Sichuan Preschool Educators College, Guangyuan 628000, ChinaThe Personnel Department of Sichuan Normal University, Chengdu 610068, ChinaAnt colony optimization (ACO) is often used to solve optimization problems, such as traveling salesman problem (TSP). When it is applied to TSP, its runtime is proportional to the squared size of problem N so as to look less efficient. The following statistical feature is observed during the authors’ long-term gene data analysis using ACO: when the data size N becomes big, local clustering appears frequently. That is, some data cluster tightly in a small area and form a class, and the correlation between different classes is weak. And this feature makes the idea of divide and rule feasible for the estimate of solution of TSP. In this paper an improved ACO algorithm is presented, which firstly divided all data into local clusters and calculated small TSP routes and then assembled a big TSP route with them. Simulation shows that the presented method improves the running speed of ACO by 200 factors under the condition that data set holds feature of local clustering.http://dx.doi.org/10.1155/2014/545391 |
| spellingShingle | Chao-Yang Pang Ben-Qiong Hu Jie Zhang Wei Hu Zheng-Chao Shan Applying Data Clustering Feature to Speed Up Ant Colony Optimization Abstract and Applied Analysis |
| title | Applying Data Clustering Feature to Speed Up Ant Colony Optimization |
| title_full | Applying Data Clustering Feature to Speed Up Ant Colony Optimization |
| title_fullStr | Applying Data Clustering Feature to Speed Up Ant Colony Optimization |
| title_full_unstemmed | Applying Data Clustering Feature to Speed Up Ant Colony Optimization |
| title_short | Applying Data Clustering Feature to Speed Up Ant Colony Optimization |
| title_sort | applying data clustering feature to speed up ant colony optimization |
| url | http://dx.doi.org/10.1155/2014/545391 |
| work_keys_str_mv | AT chaoyangpang applyingdataclusteringfeaturetospeedupantcolonyoptimization AT benqionghu applyingdataclusteringfeaturetospeedupantcolonyoptimization AT jiezhang applyingdataclusteringfeaturetospeedupantcolonyoptimization AT weihu applyingdataclusteringfeaturetospeedupantcolonyoptimization AT zhengchaoshan applyingdataclusteringfeaturetospeedupantcolonyoptimization |