کنفرانس مهندسی برق ایران

صفحه اصلی / سی امین کنفرانس بین المللی مهندسی برق

حل مسئله مجموعه مستقل d-فاصله با رویکرد CombOpt Zero

نویسندگان :

فاطمه نیکبخت نصرآبادی¹ حسین فلسفین² مهران صفایانی³

1- دانشگاه صنعتی اصفهان 2- دانشگاه صنعتی اصفهان 3- دانشگاه صنعتی اصفهان

کلمات کلیدی :

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

چکیده :

مسئله‌ی مجموعه مستقل بیشینه یک مسئله‌ی بهینه‌سازی ترکیبیاتی NP-سخت است. کاربردهای فراوانی برای این مسائل در دنیای واقعی وجود دارد. یکی از تعمیم‌های این مسئله، مسئله مجموعه مستقل d-فاصله بیشینه است. این مسئله نیز مانند مسئله‌ی مجموعه مستقل بیشینه یک مسئله NP-سخت است. به همین دلیل تاکنون رویکردی چندجمله‌ای برای این حل مسئله یافت نشده‌است. رویکرد‌های دقیق موجود برای مسئله مجموعه مستقل d-فاصله بیشینه دارای پیچیدگی زمانی بدترین حالت نمایی هستند. رویکرد‌های غیردقیق و اکتشافی جوابی ریزبهینه را بر می‌گردانند. در سال‌های اخیر که رویکرد‌های یادگیری تقویتی روایج پیدا کرده است، یک الگوریتم با نتایج امیدوارکننده به نام CombOpt Zero برای حل برخی از مسائل بهینه‌سازی ترکیبیاتی ارائه شده‌است. در این مقاله ما با پیاده سازی مسئله در چارچوب فرآیند تصمیم‌گیری مارکوف، از این الگوریتم برای حل مسئله مجموعه مستقل d-فاصله بیشینه استفاده کرده‌ایم. نتایج حاصل از شبیه‌سازی را با حل دقیق مقایسه کردیم و نتایج امیدوارکننده بودند. برای بدست آوردن جواب‌های دقیق، از رویکرد برنامه‌ریزی خطی عدد صحیح، استفاده شده‌است.