Title :
Self-adaptive ant colony algorithm for attributes reduction
Author :
Xie-Lin-Quan ; Mei-Hong-biao
Author_Institution :
Univ. of Sci. & Technol., Beijing
Abstract :
The attributes reduction (AR) and their values are one of the highlight of rough set theory. Decision table can be simplified effectively by critical attributes and their values. But this problem is an NP-hard problem. On terms of the similarity and difference between TSP (travel salesman problem) and AR, the ant colony algorithm (ACA) is applied to solve AR problem, and an self-adaptive ant colony algorithm (SAACA) is proposed, which is improved from ACA through modifying the pheromone updating rule and the transition rule by introducing evenness of solution and interests into it in order to reduce computing time and avoid to stagnation behavior of basic ACA. Simulation results show that the AACA can settle the contradictory between convergence speed and stagnation behavior efficiently and is very suitable for solving AR.
Keywords :
computational complexity; decision tables; optimisation; rough set theory; travelling salesman problems; NP-hard problem; attributes reduction; convergence speed; decision table; rough set theory; self-adaptive ant colony algorithm; stagnation behavior; travel salesman problem; Acceleration; Algebra; Computational modeling; Databases; Frequency; Information systems; Management information systems; Matrices; NP-hard problem; Set theory; Acceleration; Ant Colony Algoritm; Attributes Reduction; Evenness; Intrests; Rough Set;
Conference_Titel :
Granular Computing, 2008. GrC 2008. IEEE International Conference on
Conference_Location :
Hangzhou
Print_ISBN :
978-1-4244-2512-9
Electronic_ISBN :
978-1-4244-2513-6
DOI :
10.1109/GRC.2008.4664633