رویکردی جدید برای مقابله با مشکلات بهینه‌سازی با استفاده از ماشین‌های بولتزمن

28 مارس 2022 -توسط Ingrid Fadelli، Tech Xplore

سمت چپ: با استفاده از منطق دیجیتال برای انجام فاز رو به جلو (بررسی) و معکوس (حل) محاسبات. بالا سمت راست: نمونه بردار به طور احتمالی بهترین راه حل ها را در فضا جستجو می کند. پایین سمت راست: یک برنامه کاربردی مهم حل فاکتورهای نیمه اول است، مشکلی در قلب رمزنگاری مدرن، و معمولاً غیرقابل حل است. اعتبار: پاتل، کانوزا و صلاح الدین.

ماشین‌های آیزینگ، معماری‌های کامپیوتری نامتعارفی هستند که بر اساس اصول فیزیک بنا شده‌اند و به نام فیزیکدان آلمانی ارنست ایزینگ نامگذاری شده‌اند. در سال های اخیر، مشخص شده است که آنها ابزارهای امیدوارکننده ای برای حل مسائل بهینه سازی ترکیبی (CO) و ایجاد مدل های مصنوعی از مغز هستند.

تیمی از محققان در گروه سیف صلاح الدین، استاد برجسته TSMC در EECS در دانشگاه کالیفرنیا، برکلی، اخیراً پتانسیل ماشین‌های Ising را برای یافتن راه‌حل‌هایی برای مسائل بهینه‌سازی پیچیده در عمق زیاد بررسی کرده‌اند. آخرین مقاله آنها که در Nature Electronics منتشر شده است، یک ماشین Ising جدید متشکل از بسیاری از ماشین‌های محدود شده بولتزمن (RBM) را معرفی کرد که نتایج قابل توجهی در وظایف بهینه‌سازی ترکیبی پیچیده به دست آورد.

Saavan Patel، نویسنده اصلی که این مطالعه را انجام داد، به TechXplore گفت: در سال‌های اخیر، کار زیادی روی ماشین‌های Ising انجام شده است تا مشکلات بهینه‌سازی را تسریع بخشد، که کار ما بر روی آنها استوار است. هدف اولیه مطالعه ما این بود که نشان دهیم چگونه یادگیری ماشینی و شتاب سخت افزاری می توانند در چارچوب ماشین های Ising قرار بگیرند و مشکلات بهینه سازی را به گونه ای که از منطق دیجیتال الهام گرفته شده است را تسریع بخشند.

ماشین‌های محدود بولتزمن (RBM) مدل‌های مولد و تصادفی مبتنی بر شبکه‌های عصبی مصنوعی هستند. این مدل ها می توانند در گرفتن همبستگی های پیچیده و الگوهای توزیع در مقادیر زیادی از داده های ورودی بسیار خوب باشند.

RBM ها بر فعال سازی های باینری تکیه می کنند و ضربات مستقیم ماتریس-بردار را که معمولاً از نظر محاسباتی برای شبکه های یادگیری عمیق بیشترین نیاز را دارند، دور می زنند. در مطالعه خود، پاتل و همکارانش از این ویژگی منحصر به فرد مدل ها برای افزایش سرعتی که ماشین آنها می تواند مسائل بهینه سازی را حل کند، استفاده کردند.

پاتل توضیح داد: الگوریتم ما با استفاده از اصول اولیه منطق دیجیتال به روشی جدید عمل می کند. معمولاً دروازه‌های دیجیتال فقط در جهت رو به جلو عمل می‌کنند، اما با استفاده از مدل‌های گرافیکی احتمالی و یادگیری ماشین، راه‌هایی برای عملکرد معکوس آنها نشان داده‌ایم. مشکل اینست کهآیا این مجموعه ورودی راه حل معتبری است؟

 یا 191 x 223 چیست؟، اما از آنجایی که سیستم برگشت پذیر است، می تواند به مشکل معکوس بسیار سخت تر نیز پاسخ دهد که همه مجموعه های ورودی که چیست؟آیا میتوانید یک راه حل معتبر تولید کنید؟ و A و B چه هستند طوری که A x B = 42593.

ماشینی که آنها توسعه دادند به پاتل و همکارانش اجازه داد تا انواع مختلفی از مسائل بهینه سازی را حل کنند. اساساً، مدار آنها ابتدا با ارزیابی راه حل های مختلف موجود و سپس تلاش برای شناسایی راه حل های جدید کار می کند. برخلاف دیگر راه حل های پیشنهادی قبلی، پلتفرم محققان رویکردهای نقشه برداری مشکل، یادگیری ماشینی و راه حل های سخت افزاری را با هم ترکیب می کند.

پاتل گفت: “با استفاده از رویکرد منطق دیجیتال خود، توانستیم نشان دهیم که می توانیم دو نوع مشکل “سخت” را حل کنیم. اولین مورد رضایت‌پذیری بولی است که ستون فقرات مسائل بهینه‌سازی ترکیبی را تشکیل می‌دهد و دوم مسئله فاکتورسازی اعداد صحیح است که اساس الگوریتم رمزنگاری RSA است که رایانه‌های مدرن استفاده می‌کنند. هدف نشان دادن این بود که این ابزار کار می‌کند و ما نشان دادیم که می‌توانیم مشکلات فاکتورسازی بزرگ‌تری را نسبت به روش‌های پیشنهادی قبلی حل کنیم.”

در ارزیابی های اولیه، ماشین ایجاد شده توسط این تیم از محققین به نتایج بسیار امیدوارکننده ای دست یافت و مسائل بهینه سازی ترکیبی پیچیده و فاکتورسازی اعداد صحیح را حل کرد. علاوه بر این، سخت افزار پشتیبانی معرفی شده در مقاله می تواند راه حل هایی برای مشکلات 10000 برابر سریعتر از یک CPU معمولی پیدا کند.

در آینده، ماشین‌های Ising مانند آنچه توسط پاتل و همکارانش معرفی شد، می‌توانند برای حل طیف گسترده‌ای از مسائل پیچیده دنیای واقعی با سرعت و کارآمدی بیشتری مورد استفاده قرار گیرند، از جمله مسائل مرتبط با لجستیک یا تولید، مشکلات مسیریابی و شکستن رمزنگاری. در مطالعات بعدی، محققان سعی خواهند کرد ماشین خود را ارتقا دهند تا بتواند وظایف بهینه سازی بزرگتر و پیچیده تری را انجام دهد. علاوه بر این، آنها مایلند پتانسیل آن را برای حل انواع دیگر مشکلات ارزیابی کنند.

پاتل افزود: “ما در حال طراحی سیستم های FPGA بزرگتر و کارآمدتر برای حل مشکلات بزرگتر و همچنین ASICها هستیم.” از نظر حوزه‌های مشکل جدید، ما در حال بررسی نقشه‌برداری برای مشکلات مسیریابی بوده‌ایم.