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

مسیله درخت پوشای کمینه یکی از مسایل باسابقه حوزه بهینه سازی ترکیباتی است که نزدیک به یک قرن از طرح آن توسط بروفکا می گذرد. اهمیت و مقبولیت این مسیله موجب شده تا علاوه بر ارایه روش های مختلف با زمان چندجمله ای برای حل آن، توسعه های مختلفی نظیر درخت پوشای کمینه احتمالاتی یا p-MST، درخت پوشای کمینه تصادفی یا s-MST، درخت کمینه آشتاینر یا MStT، درخت پوشای کمینه دوگانه یا q-MST و درخت پوشای کمینه عام یا GMST نیز برای آن ارایه گردد. عموم اینتوسعه ها در زمره مسایل NP دشوار می باشند. در این مقاله مسیله درخت پوشای کمینه عام مورد بررسی قرار گرفته است. هدف از حل این مسیله تعیین یک گره از هر خوشه در یک گراف خوشه بندی شده به نحوی است که درخت پوشای کمینه ایجادشده توسط این گره ها کمترین وزن ممکن را داشته باشد. در این مقاله برای حل مسیله درخت پوشای کمینه عام ازشبکه هایی از آتاماتاهای یادگیر استفاده شده است. این شبکه از آتاماتاها در فضای جواب های مسیله به جست وجوی جواب بهینه می پردازد و از طریق نمونه گیری تحت هدایت آتاماتاهای یادگیر جواب بهینه یا نزدیک به بهینه را می یابد. نتیجه بررسی رهیافت پیشنهادی بر روی نمونه های استاندارد کتابخانه ای TSPLIB نشان داده است که در مقایسه با سایر روش های تقریبی حل این مسیله، روش پیشنهادی از زمان اجرای بسیار کمتری برخوردار است در حالی که دقت جواببه دست آمده نزدیک به بهترین روش های موجود گزارش شده در متون تحقیقاتی این حوزه است.

کلیدواژه ها:

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