| Summary |
Pei-Shan Tsai，2007.06
Feng Chia University
Clustering is a NP-hard problem of which the complexity will become rapidly intractable as problem size grows. Thus, numerous heuristic clustering algorithms have been proposed and validated. This study aims to develop a hybrid clustering algorithm based on genetic clustering algorithm (GCA) and ant clustering algorithm (ACA), named genetic ant clustering algorithm (GACA). The core logic of the proposed algorithm is to employ genetic algorithm to optimally determine the clustering seeds (as the starting nodes of ants), and then using ant colony system to conduct the clustering (i.e. assignment).
To compare the performance of the proposed algorithm with that of K-means, ACA, GCA-real coding (RC) and GCA-cluster seed point method (CSPM), a numerical study on various scales of clustering problems, including 50, 100 and 300 randomly generated two-dimension samples is conducted. The results show that, in terms of effectiveness, GCA-CSPM consistently and significantly performs best, followed by GACA, GCA-RC, and K-means performs worst under various problem scales. The reason for GCA-CSPM performing better than GACA is that GCA-CSPM first determines the optimal seeds by genetic algorithm, and then adopts an assignment algorithm to optimally assign objects to their corresponding seeds, while GACA first determines the optimal seeds by genetic algorithm, and then employs ACA to approximately assign the objects to seeds according to their similarity measures. However, the assignment algorithm of GCA-CSPM only is applicable to the independent clustering problem (the clustering performance will not change with various assignment sequences) and the similarity between objects and seeds can be computed.
To demonstrate this point and investigate the applicability of the proposed algorithm, a case study on a p-median problem is conducted. The results show that GCA-CSPM still performs best, followed by GACA, GCA-RC and ACA. However, if the capacity constraint (to limit the number of points served by a facility) is imposed, the performance of GACA is superior to that of GCA-CSPM, CGA-RC and ACA. Besides, the performance superior gap between GACA and GCA-CSPM will get larger, as the capacity constraint becomes stricter. However, as to the aspect of efficiency, in terms of the number of clustering combinations searched or the computing CPU time, the proposed hybrid algorithm is rather inefficient, suggesting the proposed hybrid algorithm is more suitable for pre-planning or post-optimizing problems than real-time optimization problems.
Since the proposed clustering algorithm hybridizes both GCA and ACA, several parameters are set in a try-and-error manner. Sensitivity analysis on these parameters shows that mutation rate, weight of similarity, probability of transition rule, and number of iterations of ACA are relatively sensitive, suggesting that these parameters should be carefully set. |
