5 مارس 2024 -توسط دانشگاه تسوکوبا-اعتبار: دامنه عمومی Pixabay/CC0
محققان دانشگاه تسوکوبا نمونه‌های متقابلی را برای ویژگی‌های کلیدی فرضی بهینه‌سازی توزیع شده ناهمزمان (ADOPT) و الگوریتم‌های جانشین آن ارائه کرده‌اند.ADOPT یک الگوریتم شناخته شده برای حل مسائل بهینه سازی محدودیت های توزیع شده است.
تیم نشان داد که این الگوریتم‌ها لزوماً ویژگی‌های کلیدی، یعنی خاتمه و بهینه بودن را تضمین نمی‌کنند. علاوه بر این، آنها نسخه اصلاح شده ای از ADOPT را پیشنهاد کردند که این ویژگی ها را تضمین می کند. این مطالعه در ژورنال Artificial Intelligence منتشر شده است.
مسائل بهینه‌سازی محدودیت توزیع‌شده برای مدل‌سازی سیستم‌های اشتراکی-چند عاملی حیاتی هستند. الگوریتم ADOPT دارای دو ویژگی مهم در نظر گرفته می شود: خاتمه، به این معنی که الگوریتم در زمان محدودی خاتمه می یابد، و بهینه بودن، که نشان می دهد همیشه زمانی که الگوریتم خاتمه می یابد، یک راه حل بهینه به دست می آید. تصور می شد که این ویژگی ها برای الگوریتم های جانشین مبتنی بر ADOPT وجود دارند.
این مطالعه نمونه هایی متضاد برای خاتمه و بهینه بودن ADOPT و الگوریتم های جانشین آن ارائه می کند. این نشان می‌دهد که اثبات‌های ارائه‌شده برای ADOPT و الگوریتم‌های جانشین آن نادرست هستند و این احتمال وجود دارد که الگوریتم خاتمه نیابد یا با یک راه‌حل زیربهینه خاتمه یابد.
علاوه بر این، محققان علت وجود چنین نمونه های متقابلی را در ADOPT شناسایی کرده و الگوریتمی را پیشنهاد کردند که آنها را تصحیح می کند. علاوه بر این، آنها خاتمه و بهینه بودن نسخه اصلاح شده ADOPT را ثابت کردند.
با اعمال نسخه اصلاح شده ADOPT می توان از خرابی در ADOPT و الگوریتم های جانشین آن جلوگیری کرد و انتظار می رود قابلیت اطمینان سیستم های مبتنی بر این الگوریتم ها بهبود یابد.
