الگوریتمهای خوشه بندی

 روشها یا الگوریتمهای خوشه بندی

در ابتدا با الگوریتمهای ابتکاری آشنا میشویم

در مسائل مختلف همیشه به دنبال بهترین جواب یا به اصطلاح در جستجوی جواب بهینه هستیم. مطمئنا در بعضی مسائل ، جواب دقیقی بدست نمی­ آید و باید به جستجوی جوابی بهینه بود.

الگوریتم‌های فراابتکاری یا فراتکاملی یا فرااکتشافی نوعی از الگوریتم‌های تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.

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

الگوریتمای بهینه سازی  به دو دسته الگوریتمهای دقیق (exact) و الگوریتم‌های تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند.

 الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی کافی ندارند و زمان اجرای آن­ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد درصورتیکه ما به دنبال بهترین جواب در سریعترین زمان ممکن هستیم. الگوریتم‌های تقریبی همانطور که از نامشان مشخص است قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمانی کوتاه برای مسائل بهینه‌سازی سخت هستند.

الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش بندی می شوند.

 دو مشکل اصلی الگوریتم‌های ابتکاری، گیر افتادن آنها در نقاط بهینه محلی وهمگرایی زودرس به این نقاط است.

 الگوریتم‌های فراابتکاری برای حل مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده ای از مسائل را دارند.

 

الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی کافی ندارند و زمان اجرای آن­ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد درصورتیکه ما به دنبال بهترین جواب در سریعترین زمان ممکن هستیم. الگوریتم‌های تقریبی همانطور که از نامشان مشخص است قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمانی کوتاه برای مسائل بهینه‌سازی سخت هستند.

الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش بندی می شوند.

 دو مشکل اصلی الگوریتم‌های ابتکاری، گیر افتادن آنها در نقاط بهینه محلی وهمگرایی زودرس به این نقاط است.

 الگوریتم‌های فراابتکاری برای حل مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده ای از مسائل را دارند.

الگوریتمهای فراابتکاری به دو شیوه قادر به یافتن پاسخ هستند :

1-  شیوه مبتنی بر یک جواب

2- شیوه مبتنی بر جمعیت

فراابتکاری به دوگروه کلی به دوگروه روشهای مبتنی بریک جواب و مبتنی برجمعیت تقسیم میشوند الگوریتم های مبتنی بریک جواب درحین فرایند جستجو یک جواب را تغییر میدهند درحالیکه الگوریتم های مبتنی برجمعیت درحین جستجو یک جمعیت ازجوابها رادرنظر میگیرند الگوریتم های مبتنی بریک جواب برروی مناطق محلی جستجو تمرکز دارند در مقابل الگوریتم های مبتنی برجمعیت میتوانند جستجو را بطور همزمان درمناطق مختلفی ازفضای جواب انجام دهند .

یک الگوریتم فراابتکاری دقیق مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فراابتکاری احتمالی، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

از الگوریتم‌های شناخته شده فراابتکاری بر پایه جمعیت می‌توان الگوریتم‌های تکاملی  الگوریتم ژنتیک، برنامه‌ریزی ژنتیک،  بهینه‌سازی کلونی مورچگان ، کلونی زنبورها ، روش بهینه‌سازی ازدحام ذرات و ... اشاره کرد و از الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب می‌توان الگوریتم جستجوی ممنوعه  و الگوریتم تبرید شبیه‌سازی شده را نام برد.

**الگوریتمهای تکاملی ،شاخه ای از الگوریتمهای فراابتکاری هستند و الگوریتمهای تکاملی یکی از انواع روشهای خوشه بندی .

الگوریتم های خوشه بندی را می­ توان به دو دسته روش های کلاسیک و تکاملی تقسیم نمود که با آنها آشنا می­شویم.

روشهای کلاسیک:                                                       

1- الگوریتمهای سلسله مراتبی: بالا رونده(Divisive:DIANA) –پایین رونده (Agglomerative Nesting:AGNES)

2-  الگوریتمهای ناحیه ای (افراز): K-MEANS –K-MEDIODS

3-  الگوریتمهای مبتنی بر چگالی: DBSCAN- OPTIC

4-  الگوریتمهای مبتنی برgrid: STING- CLQUE

5-  الگوریتم های مبتنی بر گراف

روشهای تکاملی:

روشهای سنتی عموما بهینه نیستند،به همین دلیل سعی بر آن شده که روشهایی برای بهینه سازی و رسیدن به بهترین جواب ارائه گردد. در این راستا الگوریتمهایی با عنوان الگوریتمهای تکاملی(AG) یا الگوریتمهای فرگشتی پیشنهاد شده اند که برای حل مسائل پیچیده ،مسائلِ دارای متغیرهای زیاد،مسائل دارای راه حل های زیاد،بکار گرفته میشوند.

بطورکلی:

• الگوریتمهای تکاملی شامل روشهایی هستند برای جستجو  که عمل جستجو از چندین نقطه در فضای جواب آغاز می‌شود.
•  الگوریتم تکاملی یا فرگشتی زیرمجموعه­ای از محاسبات تکاملی است که شامل مسائل بهینه سازی ترکیبی است.
• الگوریتمهای فرگشتی(تکاملی)،شاخه ای ازهوش مصنوعی به حساب می­آیند، هوش مصنوعی ،هوشی است که یک ماشین درشرایط مختلف از خود نشان می دهد.
• بهینه سازی ترکیبی، که خود شاخه ای از بهینه سازی است به آن دسته از مسائلی می پردازد که در آن ها ،مجموعه پاسخ ها،گسسته هستند یا میتوانند به صورت گسسته درآیند و هدف، پیدا کردن بهترین پاسخ از بین این پاسخ هاست.

الگوریتم مورچه،زنبور عسل،ژنتیک و.. از این نمونه الگوریتمها هستند.

الگوریتم‌های تکامل‌پذیر روش‌هایی بر مبنای جستجوی تصادفی‌اند که از مدل‌سازی تکامل بیولوژیکی طبیعی الگوبرداری شده‌اند. شیوه عملکرد الگوریتمهای تکاملی به این گونه است که روی پاسخ های ممکن کار میکنند،پاسخهایی که از ویژگی خاصی برخوردارند و میتوانند مدت زمان بیشتری بقا داشته باشد، بنابراین با استفاده از الگوریتمهای تکاملی  احتمال دست یابی به پاسخ بهینه بیشتراست.

منابع :

• عمرانکده ،بانک اطلاعات مهندسی عمران

 www.omrankadehsepahan.ir/post/16

• الگوریتم تکاملی (ویکی پدیاwikipedia)
• مروری بر الگوریتمهای فراابتکاری و بررسی قابلیتهای آنها، اولین کنفرانس ملی الگوریتمهای  فراابتکاری و کاربردهای آن  در علوم و مهندسی ،علیرضا مدانلوجویباری،حمیدرضا محمدپور،16 و17 مرداد  
   1393(کد COI مقاله: MHAA01_152)

http://www.civilica.com/Paper-MHAA01-MHAA01_152.html 

• دسته بندی انواع الگوریتم های فرا ابتکاری
• الگوریتم های فرا ابتکاری / Metaheuristic Algorithms