مروری سیستماتیک بر روش‌های یادگیری عمیق و شبکه‌های عصبی گرافی برای مسئله رنگ‌آمیزی گراف: دستاوردها، شکاف‌های نظری و جهت‌گیری‌های آینده

مروری سیستماتیک بر روش‌های یادگیری عمیق و شبکه‌های عصبی گرافی برای مسئله رنگ‌آمیزی گراف: دستاوردها، شکاف‌های نظری و جهت‌گیری‌های آینده

عباس جعفرزاده1 مرتضی خانی دهنوئی2

1) استادیار گروه ریاضی، دانشکده مهندسی، دانشگاه صنعتی قوچان، قوچان، ایران
2) استادیار گروه مهندسی کامپیوتر، دانشکده برق و کامپیوتر، دانشگاه صنعتی قوچان، قوچان، ایران

کد IOI مقاله : ACCA-ACACHZ
محل انتشار : چهارمین کنگره بین المللی علوم، مهندسی و فن آوری های نو(secongress.com)
چکیده :
    مسئلهٔ رنگ‌آمیزی گراف (GCP) یکی از بنیادی‌ترین مسائل بهینه‌سازی ترکیبیاتی NP-سخت است که کاربردهای گسترده‌ای در زمان‌بندی، تخصیص ثبات، تخصیص فرکانس و مدیریت منابع دارد. روش‌های ابتکاری و دقیق سنتی هنگام مواجهه با گراف‌های بزرگ یا پویا، مقیاس‌پذیری ضعیفی از خود نشان می‌دهند و همین امر انگیزه‌ای برای گرایش به سوی رویکردهای مبتنی بر یادگیری ایجاد کرده است. این مقاله یک مرور سیستماتیک از متون (SLR) بر پایهٔ پروتکل PRISMA ارائه می‌دهد که مطالعات منتشرشده در بازهٔ ۲۰۱۹ تا ۲۰۲۵ را بررسی می‌کند و به کارگیری شبکه‌های عصبی — به‌ویژه شبکه‌های عصبی گرافی (GNN) — را در مسئلهٔ رنگ‌آمیزی گراف می‌کاود. پس از جست‌وجو در پایگاه‌های IEEE Xplore، ScienceDirect، SpringerLink و arXiv و اعمال معیارهای ورود و خروج، ۱۸ مطالعه برای تحلیل نهایی انتخاب شدند؛ از این میان، ۱۳ مطالعهٔ اصلی مبتنی بر یادگیری، هستهٔ سنتز را تشکیل می‌دهند و ۵ مطالعهٔ غیرشبکه‌عصبی/ابتکاری صرفاً برای زمینهٔ مقایسه‌ای گنجانده شده‌اند. یافته‌ها نشان می‌دهد که رویکردهای یادگیری در قالب سه پارادایم اصلی — نظارت‌شده، بدون نظارت و یادگیری تقویتی — سازمان می‌یابند و شبکه‌های عصبی گرافی، به‌دلیل توانایی‌شان در رمزگذاری ساختار محلی گراف، هستهٔ مشترک بیشتر روش‌های اخیر را تشکیل می‌دهند. با این حال، تحلیل انتقادی از منظر نظریهٔ گراف، شکاف نظری قابل‌توجهی را میان تضمین‌های ابتکاری تجربی و کران‌های ریاضی دقیق بر عدد رنگی آشکار می‌سازد. بیشتر مطالعات فاقد تحلیل همگرایی و کران‌های خطای نظری هستند و ارزیابی‌ها به مجموعه‌های محدود بنچمارک DIMACS و COLOR محدود مانده‌اند. این مرور جهت‌گیری‌های پژوهشی آینده را با تأکید بر ضرورت پیوند روش‌های یادگیری با نظریهٔ طیفی و کران‌های نظری در گراف‌ها پیشنهاد می‌کند

کلمات کلیدی : مسئلهٔ رنگ‌آمیزی گراف شبکهٔ عصبی گرافی یادگیری تقویتی بهینه‌سازی ترکیبیاتی مرور سیستماتیک