بخشی از مقاله
چکیده
مسئله درخت پوشای مینیمم کاربردهای متعددی در طراحی شبکههای ارتباطی ،کامپیوتری و شبکه-های حملونقل دارد. این پژوهش، استفاده از یک الگوریتم رقابت استعماری نوین را جهت حل مسئله درخت پوشای مینیمم ارائه میکند. این الگوریتم تغییر یافتهی الگوریتم رقابت استعماری است که از ایدهی تکامل سیاسی - اجتماعی بشر الهام گرفته شده است. در این روش با افزودن مؤلفه سرعت برای هر کشور که هدایت حرکت آن را بر عهده دارد، حرکت مستعمرات به سمت استعمارگرهایشان در فرآیند جذب الگوریتم رقابت استعماری بطور پویا درطی تکرارها تنظیم شده و در نتیجه یک جستجوی هوشمندانه و هدفمندتر در الگوریتم رقابت استعماری انجام می شود و بین جستجوی محلی و عمومی بطور مناسبی موازنه ایجاد میکند. نتایج تجربی بدست آمده حاکی از آن است که الگوریتم پیشنهادی توانسته است سرعت همگرایی و کیفیت راه حل بهینه عمومی را در مقایسه با الگوریتم رقابت استعماری استاندارد بخوبی بهبود بخشد.
واژگان کلیدی: درخت پوشای مینیمم - الگوریتم رقابت استعماری - هوش جمعی- استراتژی وفقی
-1مقدمه
مسئله درخت پوشای مینیمم عبارت است از یافتن یک زیر گراف از گراف غیرجهت دار و وزن دار به طوری که همه گره های گراف را پوشش دهد و وزن کلی تخصیص داده شده به یال های آن از بین همه درخت های پوشای ممکن کمتر باشد. درختان پوشای مینیمم کاربردهای مستقیمی در طراحی شبکه ها دارند، از جمله شبکه های کامپیوتری، شبکه های مخابراتی، شبکه های حمل و نقل، شبکه های آبرسانی و شبکه های برق.الگوریتم های کلاسیک بسیاری برای حل مسئله درخت پوشای مینیمم در تئوری گراف وجود دارد، مانند الگوریتم کراسکال، الگوریتم پریم و بروکا. اما در فضاهای مسئله بسیار بزرگ روشهای کلاسیک علاوه بر پیچیدگی زمانی بسیار بزرگی که دارند عملا غیر قابل استفاده خواهند بود ؛ از این رو روش های هوش جمعی جایگزینهای مناسبی برای حل مسئله درخت پوشای مینیمم با تعداد زیادی از رئوس و یالها خواهند بود.
در تحقیقات قبلی، چندین رویکرد مختلف برای این مسئله مطرح شده است، از جمله: بهینه سازی کلونی مورچه - Neumann and Witt, 2010 - ، الگوریتم ژنتیک - Quoc PhanTan ,2012 - و الگوریتم Chun and - PSO . - Ying, 2014 از دیگر روشهای مؤثر در بهینه سازی درخت پوشای مینیمم میتوان به روش اکتشافی جستجوی ممنوعه - Temel Öncan et al,2008 - و الگوریتم وفقی زنبور عسل - Singh and Sundar, 2010 - اشاره کرد.اخیراً ژانگ و همکارانش نیز برای تولید درخت پوشای مینیمم یک الگوریتم سریع بر پایه K-means را معرفی نمودهاند که از یک طرح تقسیم و حل استفاده میکند . - Caiming Zhong et al, 2015 - الگوریتمهای ابتکاری متعددی نیز در حل نمونههای مختلف مسئله درخت پوشای مینیمم مورد استفاده قرار گرفتند: Wang و همکارانش الگوریتم DNA سریعی را با استفاده از عملیات مولکولی DNA بررسی کردهاند - . - Wang et al, 2013
مارچ و همکارانش نیز ، الگوریتم سریع و کلی درخت پوشای مینیمم را براساس دستهبندی و تحلیل دادههای نجومی معرفی نمودند - March et . - al, 2010الگوریتمهای پیوندی، مانند ترکیب الگوریتم جستجوی محلی با الگوریتم شبیه سازی تبرید - Consoli and Moreno Pérez, 2012 - و الگوریتم پیوندی جستجوی ممنوعه و بهینه سازی کلونی مورچگان - Katagiri et al, 2012 - هم توانستهاند در حل این مسئله موفق عمل کنندالگوریتم. رقابت استعماری نیز یک الگوریتم نسبتاً جدید فرا اکتشافی است که در مورد حل مسئله درخت پوشای مینیمم نتایج جالب توجهی حاصل کرده است - Hosseini et al, 2012 - اما چون در این الگوریتم کشورها - مستعمرات - با یک زاویه معین به سمت استعمار حرکت می کنند امکان گیر افتادن در دام بهینه محلی وجود دارد.
این مقاله، از الگوریتم رقابت استعماری جدیدی جهت حل مسئله درخت پوشای مینیمم استفاده میکند. در این روش با ایجاد هوشمندی در حرکت کشورها ، جهت حرکت آنها در فرآیند جذب الگوریتم رقابت استعماری بطور وفقی تنظیم می شود. بنابراین جستجوی هدفمندتری انجام شده و درواقع بین جستجوی محلی و عمومی بطور مناسبی موازنه ایجاد میشود.ادامه مقاله به شرح زیر سازماندهی شده است: در بخش 2 الگوریتم رقابت استعماری استاندارد و الگوریتم پیشنهادی معرفی میشوند. بخش 3 جزئیات روند پیادهسازی الگوریتم رقابت استعماری پیشنهادی در مورد حل مسئله درخت پوشای مینیمم را شرح میدهد .در بخش 4 به تحلیل و بررسی نتایج و در نهایت در بخش 5 به نتیجهگیری و جمعبندی میپردازیم.
-2روش تحقیق
-1-2 الگوریتم رقابت استعماری
الگوریتم رقابت استعماری یک الگوریتم اکتشافی جدید مبتنی بر جمعیت است که از تحول اجتماعی سیاسی انسان الهام گرفته شده است - آتشپز گرگری ، . - 1387 این الگوریتم با تعدادی جمعیت اولیه که هرکدام یک کشور نامیده می شوند آغاز میشود. تعدادی از کشورهای قدرتمند که دارای حداقل هزینه هستند، به عنوان استعمارگر انتخاب شده، و بقیه به-عنوان مستعمره، به استعمارگران براساس قدرتهایشان تخصیص مییابند. کشورهای استعمارگر با اعمال سیاست جذب در راستای محورهای مختلف بهینه سازی، مستعمرات را به سمت خود جذب میکنندکه این فرآیند در شکل 1 نشان داده شده است.در شکل، d نمایانگر فاصله میان مستعمره و استعمارگر است. کشور مستعمره به اندازه x واحد در جهت خط واصل مستعمره به استعمارگر حرکت کرده و به موقعیت جدید کشانده میشود.
x یک متغیر تصادفی با توزیع یکنواخت است که میتوان آن را به صورت زیر نمایش داد:عددی بزرگتر از یک و نزدیک به 2 میباشد. یک انتخاب مناسب میتواند 2 باشد. تاریخ بشری امپریالیسم نشان میدهد که همانندسازی همیشه مطابق میل کشور های استعمارگر نبوده، و مستعمره با یک انحراف احتمالی در مسیر جذب استعمارگر پیش میرود. این انجراف با زاویه نشان داده شده است . نیز کاملا تصادفی انتخاب می شود. معمولا، بازه شامل [ , ] می باشد. در پیاده سازی ها زاویه ای نزدیک به 45درجه در نظر گرفته میشود.مشابه فرایند جهش در الگوریتم ژنتیک ، الگوریتم رقابت استعماری نیز یک تغییر ناگهانی را در مشخصات یک کشور، معروف به انقلاب، معرفی می کند. در دامنه بهینه سازی، انقلاب، به این معنا میباشد که یک راه حل بطور تصادفی از روی فضا میپرد تا گوناگونی جهانی کشورها را کنترل نماید. انقلاب، از گیر افتادن در بهینه محلی در تکرارهای اولیه جلوگیری می کند.
