يك الگوريتم كارا براي حل مساله كلاستر بندي ظرفيت دار

An Effective Algorithm in order to solve the Capacitated Clustering Problem

مساله كلاستر بندي ظرفيت­دار (CCP) يك تكنيك داده كاوي براي دسته‌بندي تعدادي اشيا با ظرفيت مشخص به k كلاستر مجزا است به­طوري كه ظرفيت هر كلاستر نقض نشود، هر شي دقيقاً به يك كلاستر نسبت داده شود و مجموع فاصله­هاي همه مراكز كلاسترها به همه اشيا مينيمم شود. مساله CCP يك مساله –NP سخت است. بنابراين مسائل بزرگ اين مساله را نمي‌توان در يك زمان قابل قبول حل كرد. بنابراين ما علاقمند هستيم كه از روش‌هاي فراابتكاري براي حل اين مساله استفاده كنيم. به­همين علت يك روش اصلاحي رقابت استعماري براي حل مساله CCP در اين مقاله ارائه مي‌شود. روش پيشنهادي MICA سه فاز اساسي تخصيص­تصادفي براي تشكيل دادن كلاسترها، تعويض مراكز كلاسترها براي بهبود بيشتر حل مساله و استفاده از الگوريتم هاي بهبود محلي براي اصلاح جواب را تكرار مي­كند. روش پيشنهادي روي چندين مثال استاندارد در ادبيات موضوع مورد ازمايش واقع شده است. نتايج محاسباتي نه تنها نشان دهنده كارايي الگوريتم پيشنهادي است، يلكه داراي رقايت مناسبي براي حل مساله CCP با ديگر الگوريتم هاي فرا ابتكاري است.

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.