حل مسیله درخت پوشای کمینه عام یک رهیافت مبتنی بر نمونه گیری مونت کارلو به کمک آتاماتای یادگیر
Publish place: 22nd Annual Conference of Computer Society of Iran
Publish Year: 1395
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 615
This Paper With 7 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI22_076
تاریخ نمایه سازی: 13 شهریور 1396
Abstract:
مسیله درخت پوشای کمینه یکی از مسایل باسابقه حوزه بهینه سازی ترکیباتی است که نزدیک به یک قرن از طرح آن توسط بروفکا می گذرد. اهمیت و مقبولیت این مسیله موجب شده تا علاوه بر ارایه روش های مختلف با زمان چندجمله ای برای حل آن، توسعه های مختلفی نظیر درخت پوشای کمینه احتمالاتی یا p-MST، درخت پوشای کمینه تصادفی یا s-MST، درخت کمینه آشتاینر یا MStT، درخت پوشای کمینه دوگانه یا q-MST و درخت پوشای کمینه عام یا GMST نیز برای آن ارایه گردد. عموم اینتوسعه ها در زمره مسایل NP دشوار می باشند. در این مقاله مسیله درخت پوشای کمینه عام مورد بررسی قرار گرفته است. هدف از حل این مسیله تعیین یک گره از هر خوشه در یک گراف خوشه بندی شده به نحوی است که درخت پوشای کمینه ایجادشده توسط این گره ها کمترین وزن ممکن را داشته باشد. در این مقاله برای حل مسیله درخت پوشای کمینه عام ازشبکه هایی از آتاماتاهای یادگیر استفاده شده است. این شبکه از آتاماتاها در فضای جواب های مسیله به جست وجوی جواب بهینه می پردازد و از طریق نمونه گیری تحت هدایت آتاماتاهای یادگیر جواب بهینه یا نزدیک به بهینه را می یابد. نتیجه بررسی رهیافت پیشنهادی بر روی نمونه های استاندارد کتابخانه ای TSPLIB نشان داده است که در مقایسه با سایر روش های تقریبی حل این مسیله، روش پیشنهادی از زمان اجرای بسیار کمتری برخوردار است در حالی که دقت جواببه دست آمده نزدیک به بهترین روش های موجود گزارش شده در متون تحقیقاتی این حوزه است.
Keywords:
درخت پوشای کمینه عام , زیرگراف القایی , درخت پوشا , آتاماتای یادگیر تصادفی , جست وجوی تصادفی , بهینه سازی ترکیبی
Authors
معصومه زجاجی
دانشگاه آزاد اسلامی، واحد میبد، میبد، ایران
محمدرضا ملاخلیلی میبدی
دانشگاه آزاد اسلامی، واحد میبد، میبد، ایران
محمدرضا میبدی
آزمایشگاه محاسبات نرم، دانشگاه صنعتی امیرکبیر، تهران، ایران