حل مسائل بهينه‌سازي تركيبياتي NP-سخت با استفاده از رويكرد CombOpt Zero

اصفهان : دانشگاه صنعتي اصفهان

مهندس كامپيوتر

كارشناسي ارشد

مسائل بهينه‌سازي تركيبياتي، طيف گسترده‌اي از مسائل دنياي واقعي را در بر مي‌گيرند. تعداد زيادي از اين مسائل، NP-كامل و NP-سخت هستند. باوجود اينكه از پيدايش اين مسائل، دهه‌ها مي‌گذرد، اما هنوز براي طراحان الگوريتم جذابيت دارند. الگوريتم‌هاي كلاسيك براي حل يك مسئله بهينه‌سازي تركيبياتي NP -سخت، در سه دسته الگوريتم‌هاي دقيق، الگوريتم‌هاي تقريبي و الگوريتم‌هاي فرا ابتكاري قرار مي‌گيرند. اين الگوريتم‌ها، با وجود قابليت‌هايي كه دارند، هركدام نقاط ضعف خاص خودشان را هم دارند. امروزه با توجه به آگاهي محققان به حيطه هوش مصنوعي و نقاط قوت ابزارهاي اين حوزه، رويكرد‌هاي مبتني بر يادگيري ماشين رواج پيدا كرده‌اند. رويكردهاي يادگيري ماشين را مي‌توان به سه دسته يادگيري تحت نظارت، يادگيري بدون نظارت و يادگيري تقويتي تقسيم كرد. در چند سال اخير، براي حل مسائل بهينه‌سازي تركيبياتي، الگوريتم‌هاي يادگيري تحت نظارت و يادگيري تقويتي، توجه محققان را به خود جلب كرده‌اند. طي چند سال اخير، الگوريتم‌هاي يادگيري تقويتي در حل مسائل بهينه‌سازي تركيبياتي به نتايج اميدوار‌كننده‌اي دست يافته‌اند. رويكرد CombOpt Zero، يكي از اين رويكردهاست. در سال 2019 ميلادي، ابه و همكارانش، اين رويكرد را براي حل تعدادي از مسائل بهينه‌سازي تركيبياتي NP-سخت گرافي، پيشنهاد كردند. اين رويكرد، تركيبي از يادگيري تقويتي و تعبيه گراف است. نويسندگان، اين رويكرد را از AlphaGo Zero كه يك چارچوب موفق با كاركردي فوق‌بشري براي بازي Go است، الهام گرفته‌اند. همچنين، اين نويسندگان، از رويكرد پيشنهادي‌شان براي حل مسئله پوشش رأسي كمينه، مسئله برش بيشينه، مسئله خوشه بيشينه و مسئله مجموعه مستقل بيشينه استفاده كرده‌اند. شبيه‌سازي‌هايشان نشان مي‌دهند كه رويكرد CombOpt Zero، يك رويكرد اميدواركننده‌ براي اين مسائل بوده است. در اين پايان‌نامه، رويكرد CombOpt Zero را بررسي مي‌كنيم. همچنين از اين رويكرد، براي حل چند مسائل NP-سخت ديگر كه عبارتند از: مسئله مجموعه مستقل d-فاصله، مسئله ارضا‌پذيري بولي بيشينه وزن‌دار و مسئله مجموعه غالب كمينه، بهره مي‌گيريم. براي ارزيابي ميزان مطلوبيت اين رويكرد، براي هر سه مسئله، جواب‌هاي حاصل از حل اين مسائل با استفاده از رويكرد CombOpt Zero را با جواب‌هاي دقيق حاصل از بكارگيري روش برنامه‌ريزي خطي عدد صحيح مقايسه مي‌كنيم. همچنين، جواب حاصل از حل رويكرد CombOpt Zero براي مسئله ارضا‌پذيري بولي بيشينه وزن‌دار، را با جواب دو رويكرد جست‌و‌جوي محلي معروف به نام‌هاي IRoTS و Novelty++ و براي مسئله MDS با يك رويكرد حريصانه نيز مقايسه مي‌كنيم. خواهيم ديد كه رويكرد CombOpt Zero براي هر سه مسئله جواب‌هايي نزديك به جواب بهينه را بر مي‌گرداند. همچنين، نتايج نشان مي‌دهند كه رويكرد CombOpt Zero براي مسئله ارضا‌پذيري بولي بيشينه وزن‌دار در مقايسه با رويكردهاي جست‌و‌جوي محلي IRoTS و Novelty++، جواب‌هاي قابل قبولي ارائه مي‌دهد. علاوه بر اين، اين رويكرد براي نمونه‌هاي چالش برانگيز مسئله ارضا‌پذيري بولي بيشينه وزن‌دار كه حل ILP آن‌ها زمان بر است، نتايج خوبي و نزديك به بهينه را در زمان بسيار كمتري ارائه مي‌كند. همچنين، براي مسئله MDS درصد خطاي رويكرد حريصانه از رويكرد CombOpt Zero، حدوداً 30 درصد بيشتر است.

215889

نرم افزار

مهندسي برق و كامپيوتر

دانشگاه صنعتي اصفهان

مهران صفاياني

زينب مالكي، سمانه حسيني

حسين فلسفين