حل مساله خوشه بندی ظرفیت دار با استفاده از روش های مبتنی بر الگوریتم های شبیه سازی تبریدی و ژنتیک

سال انتشار: 1389
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 626

فایل این مقاله در 10 صفحه با فرمت PDF قابل دریافت می باشد

این مقاله در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_IJIE-21-3_005

تاریخ نمایه سازی: 6 شهریور 1393

چکیده مقاله:

خوشه بندی ظرفیت دار یکی از مسائلی است که از کاربرد گسترده ای در داده کاوی برخوردار است. این مساله به دنبال افراز یک مجموعه n تایی از عناصر به p خوشه ظرفیت دار است به طوری که تمامی اعضای یک خوشه به نقطه ای که به عنوان مرکز ثقل آن خوشه تعیین می شود ، تخصیص یابند . هدف از این مساله کمینه کردن عدم تشابه تمامی نقاط یک خوشه از مرکز ثقل خوشه با رعایت محدودیت ظرفیت در هر خوشه است ، به طوری که هر عنصر تنها به یک خوشه تخصیص یابد . در این مقاله دو روش حل متفاوت جهت حل مساله خوشه بندی ظرفیت دار ارائه شده است . روش نخست یک روش حل فرا ابتکاری مبتنی بر شبیه سازی تبریدی است که در سازوکار جستجوی جواب از ساختارهای مختلف همسایگی استفاده می کند. روش دوم مبتنی بر الگوریتم ژنتیک است که در آن از یک رویه ابتکاری جستجوی محلی استفاده شده است . روشهای ارائه شده با استفاده از مسائل نمونه ای مختلف مورد آزمون قرار گرفته اند . نتایج محاسباتی حاکی از کارایی و توانمندی روش های حل پیشنهادی است.

کلیدواژه ها:

مساله خوشه بندی ظرفیت دار ، افراز مجموعه ای ، مساله p-median ظرفیت دار ، روش های فرا ابتکاری ، الگوریتم شبیه سازی تبریدی ، الگوریتم ژنتیک

نویسندگان

مسعود یقینی

استادیار ، دانشکده مهندسی راه آهن ، دانشگاه علم و صنعت ایران

جواد لسان

دانشجوی کارشناسی ارشد ، دانشکده مهندسی راه آهن ، دانشگاه علم و صنعت ایران