سیدعلیرضا متولیان - آزمایشگاه محاسبات نرم دانشگاه صنعتی امیرکبیر
محمدرضا میبدی

مساله بزرگترین مجموعه مستقل در یک گراف عبارتست از یافتن بزرگترین زیرمجموعه ای از یک گراف بطوریکه هیچ دو راسی از این مجموعه با یالی بهم متصل نباشند این مساله از جمله مسائل NP-complete می باشد و بهمین دلیل الگوریتمهای مکاشفه ای و تقریبی متعددی از جمله تابکاری فلزات، شبکه های عصبی و الگوریتمهای ژنتیکی تاکنون برای آن ارائه نشدها ند اتوماتای یادگیر سلولی یک ابزار جستجوی تصادفی است که می توان از آن درحل مسائل NP-complete استفاده نمود. دراین مقاله یک الگوریتم مبتنی بر اتوماتای یادگیر سلولی برای حل مساله بزرگترین مجموعه مستقل ارائه شده و کارایی آن برروی تعدادی گراف نمونه استاندارد آزمایش شده است.

بزرگترین مجموعه مستقل، اتوماتای یادگیر، اتوماتای یادگیر سلولی