An Effective Algorithm in order to solve the Capacitated Clustering Problem
Author(s):
Abstract:
The capacitated clustering problem (CCP) is a data mining technique utilized to categorize a number of objects with known demands into k distinct clusters such that the capacity of each cluster is not violated, every object is allocated to exactly one cluster and sum of distances from all cluster centers to all other nodes is minimized. The CCP is an NP-hard combinatorial optimization problem. Therefore, practical large-scale instances of this problem cannot be solved by exact solution methodologies within acceptable computational time. Our interest was therefore focused on meta-heuristic solution approaches. For this reason, a modified imperialist competitive algorithm (MICA) is proposed for the CCP In this paper. The proposed MICA iterates steps between three basic phases, i.e., the random assignment phase to form clusters, the seed relocation phase to find a better median, and the local improvement phase to make a revision of the solution. The proposed algorithm is tested on several standard instances available from the literature. The computational results confirm the effectiveness of the presented algorithm and show that the proposed algorithm is competitive with other meta-heuristic algorithms for solving the CCP.
Keywords:
Language:
English
Published:
New research in Mathematics, Volume:1 Issue: 4, Winter 2016
Pages:
81 to 102
https://www.magiran.com/p1617011