نشریه بین المللی مهندسی صنایع و مدیریت تولید

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

مساله خوشه بندی به منظور کمینه کردن مجموع مجذور انحراف، یک مساله غیر خطی و غیر محدب بوده و دارای تعداد زیادی نقاط بهینه محلی است. هدف از این مقاله، ارائه روشی ترکیبی با استفاده از الگوریتم ژنتیک و K-Means برای خروج از نقاط بهینه محلی است.استفاده از الگوریتم ژنتیک برای خروج از نقاط بهینه محلی، توسط محققین بسیاری انجام شده است. در این مقاله روش های جدیدی برای عملگرهای بازترکیبی و جهش ارائه شده است. منطق روش های پیشنهادی بر این امر استوار است که اگر عملگرهای تغییر به جای آنکه بطور تصادفی در کل فضای جواب اعمال گردند، در یک منطقه محدود از پیش تعریف شده، انجام شوند، به جواب های بهتری دست خواهیم یافت. برای ارزیابی الگوریتم پیشنهادی، از سه نوع عملگر جهش و پنج نوع عملگر بازترکیبی بر روی مجموعه داده­های استاندارد استفاده شده است. مقایسه نتایج بدست آمده با سایر روش ها، به ازای Kهای متفاوت، نشان می­دهد می­توان با استفاده از عملگر بازترکیبی ساده یک نقطه ای و عملگر جهش ارائه شده در این مقاله با نام "عملگر جهش منطقه ای خوشه ای"، به جواب های بهتری دست یافت.

مساله خوشه بندی به منظور کمینه کردن مجموع مجذور انحراف، یک مساله غیر خطی و غیر محدب بوده و دارای تعداد زیادی نقاط بهینه محلی است. در مسائل خوشه­بندی در دنیای واقعی، اغلب با مجموعه داده­هایی مواجهیم که از ترکیبی از مقادیر عددی و دسته­ای تشکیل شده­اند. در حالیکه اغلب روشهای خوشه­بندی موجود تنها بر روی داده­های عددی از کارایی مناسبی برخوردارند و قابلیت استفاده بر روی داده­های مختلط را ندارند. از سوی دیگر، بیشتر روشهای سنتی، تعداد خوشه­ها را به عنوان ورودی از کاربر طلب می­کنند. در حالیکه در بیشتر موارد تعداد خوشه­ها برای کاربر مقداری نامعلوم است و حدس زدن مقدار آن نیز به خصوص در مورد مجموعه داده­های بزرگ کاری مشکل و حتی غیرممکن است. در این مقاله قصد داریم تا با بهره­گیری از روشی دقیق­تر جهت اندازه­گیری فاصله میان مقادیر دسته­ای،  روش جدیدی را برای خوشه­بندی داده­های مختلط ارائه نماییم که نیازی به تعیین تعداد خوشه­ها به عنوان ورودی الگوریتم نداشته و  قادر است همزمان با خوشه­بندی داده ها، مقدار بهینه برای تعداد خوشه­ها را محاسبه نماید. در روش پیشنهادی معکوس شاخص Davies-Bouldin به عنوان تابع برازش در نظر گرفته شده و به منظور جستجوی فضای جواب از الگوریتم ژنتیک استفاده می­شود. برای ارزیابی عملکرد الگوریتم از دو گروه از داده های استاندارد و شبیه­سازی شده استفاده شده است. نتایج بدست آمده، عملکرد بسیار بالای الگوریتم پیشنهادی را نشان می­دهد