هوش مصنوعی حل مسئله را در سناریوهای پیچیده سرعت می بخشد | اخبار MIT

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

این نرم افزار که حل کننده خطی عدد صحیح مختلط (MILP) نام دارد، یک مسئله بهینه سازی عظیم را به بخش های کوچکتر تقسیم می کند و از الگوریتم های کلی برای یافتن بهترین راه حل استفاده می کند. با این حال، ممکن است حل کننده ساعت ها یا حتی روزها طول بکشد تا به یک تصمیم برسد.

این فرآیند به قدری دشوار است که یک شرکت اغلب مجبور است نرم افزار را در نیمه راه متوقف کند و راه حلی را بپذیرد که ایده آل نیست، اما بهترین راه حلی است که می تواند در یک بازه زمانی مشخص ایجاد شود.

محققان MIT و ETH زوریخ از یادگیری ماشینی برای سرعت بخشیدن به کارها استفاده کردند.

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

رویکرد مبتنی بر داده آنها به شرکت اجازه می دهد تا از داده های خود برای تنظیم یک حل کننده MILP همه منظوره برای مشکل خاص استفاده کند.

این تکنیک جدید حل MILP را بین 30 تا 70 درصد، بدون افت دقت، سرعت بخشید. می‌توان از این روش برای دستیابی سریع‌تر به راه‌حل بهینه یا برای مسائل بخصوص پیچیده، راه‌حل بهتر در مدت زمان قابل مدیریت استفاده کرد.

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

“گاهی اوقات در زمینه ای مانند بهینه سازی، بسیار رایج است که مردم راه حل ها را به عنوان یادگیری ماشینی خالص یا کلاسیک خالص در نظر بگیرند. کتی وو، نویسنده ارشد، استادیار توسعه شغلی گیلبرت دبلیو وینسلو، استادیار مهندسی عمران و محیط زیست، گفت: من کاملاً معتقدم که ما می‌خواهیم بهترین‌های هر دو جهان را به دست آوریم، و این نماینده واقعاً قوی این رویکرد ترکیبی است. (CEE) و عضو آزمایشگاه اطلاعات و سیستم های تصمیم گیری (LIDS) و موسسه داده ها، سیستم ها و جامعه (IDSS).

وو نوشت کاغذ با نویسندگان همکار Shirui Li، یک دانشجوی IDSS، و Wenbin Ouyang، یک دانشجوی CEE. و همچنین مکس پاولوس، دانشجوی کارشناسی ارشد در ETH زوریخ. این تحقیق در کنفرانس سیستم های پردازش اطلاعات عصبی ارائه خواهد شد.

حلش سخته

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

“این مشکلات NP-hard نامیده می شوند، به این معنی که بعید است که یک الگوریتم کارآمد برای حل آنها وجود داشته باشد. وو توضیح می‌دهد: «وقتی مشکل به اندازه کافی بزرگ است، ما فقط می‌توانیم امیدوار باشیم که نتایجی کمتر از حد مطلوب داشته باشیم.

حل‌کننده MILP از مجموعه‌ای از تکنیک‌ها و ترفندهای عملی استفاده می‌کند که می‌تواند در مدت زمان قابل مدیریت به راه‌حل‌های معقول دست یابد.

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

هرس از مجموعه ای از قوانین استفاده می کند که فضای جستجو را بدون حذف راه حل های ممکن محدود می کند. این قوانین توسط چندین ده الگوریتم، معروف به جداکننده، که برای انواع مختلف مسائل MILP طراحی شده اند، تولید می شوند.

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

“مدیریت جداکننده بخش اساسی هر مشکل قابل حل است، اما جنبه ای است که از فضای مشکل قدردانی نشده است. یکی از کمک‌های این کار شناسایی مشکل کنترل جداکننده به عنوان یک کار یادگیری ماشینی برای شروع است.»

کوچک کردن فضای محلول

او و همکارانش یک مکانیسم فیلتر ایجاد کردند که این فضای جستجوی جداکننده را از بیش از 130000 ترکیب بالقوه به حدود 20 گزینه کاهش می دهد. این مکانیسم فیلتر بر اساس اصل کاهش بازده حاشیه ای است، که بیان می کند که بیشترین سود از مجموعه کوچکی از الگوریتم ها حاصل می شود و افزودن الگوریتم های بیشتر بهبود بیشتری را به همراه نخواهد داشت.

سپس از یک مدل یادگیری ماشینی برای انتخاب بهترین ترکیب الگوریتم ها از 20 گزینه باقی مانده استفاده می کنند.

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

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

این رویکرد مبتنی بر داده، حل‌کننده‌های MILP را بین 30 تا 70 درصد بدون هیچ کاهشی در دقت سرعت می‌بخشد. علاوه بر این، افزایش سرعت در نرم‌افزارهای ساده‌تر و منبع باز حل مسئله و نرم‌افزارهای تجاری قدرتمندتر مشابه بود.

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

این تحقیق تا حدی توسط Mathworks، بنیاد ملی علوم (NSF)، مرکز علمی آمازون MIT و کمیته پشتیبانی تحقیقاتی MIT پشتیبانی شده است.