بخشی از مقاله
چکیده:
مساله تخصیص درجه دوم1یک مساله NP-Hard می باشد که بدست آوردن جواب بهینه براي مسائل سایز بزرگ آن بصورت دقیق امکان پذیر نیست از اینرو روش هاي فراابتکاري براي حل آن استفاده میشود . در این مقاله از الگوریتم فراابتکاري الکترومغناطیس براي حل مساله QAP استفاده شده است . این الگوریتم بر روي تعدادي از مسائل نمونه QAP موجود در QAPLIB آزمایش شده و در تمام موارد قادر به یافتن بهترین جواب بدست آمده تاکنون بوده و نتیجه عملکرد آن در مقایسه با سایر روش هاي بکار رفته از کارایی بهتري برخوردار است .
کلمات کلیدي: الگوریتم الکترومغناطیس ؛ الگوریتم هاي فراابتکاري ؛ بهینه سازي ؛ تخصیص درجه دوم .
مقدمه
از آن زمان تاکنون این مسئله کاربرد هاي عملی متعددي یافته است . از کاربردهاي مساله تخصیص درجه دوم در تئوري جایابی ، چیدمان ساختمان ها در بیمارستان ها ، مدیریت انبارها و استراتژي هاي توزیع ، تخصیص برخی کارخانجات به برخی مکان ها ، طراحی پنل هاي کنترلی و صفحه کلید ماشین نویس ها اشاره کرد . از آنجایی که مساله تخصیص درجه دوم یک مساله NP-Hard است[3] لذا داراي پیچیدگی نمایی است و الگوریتم هاي دقیق قادر به حل این مسائل با سایز متوسط یا بزرگ نیستند . بطور کلی مسائل با ابعاد بزرگتر از 20 معمولا از روش هاي دقیق قابل حل نیستند و یا در صورت حل شدن به لحاظ زمانی توجیه اقتصادي ندارند . از این رو الگوریتم هاي فراابتکاري براي حل مسائل مورد استفاده قرار گرفته اند . در واقع راه حل هاي فراابتکاري یکی از
روش هاي تقریبی است که داراي مکانیزم خروج از بهینه محلی است و قابل کاربرد در طیف وسیعی از مسائل است. [4] روش هاي حل مسائل بهینه سازي مشتمل بر دو دسته ي روش هاي دقیق و روش هاي تقریبی است روش هاي دقیق راه حل هاي بهینه را بدست آورده و شرایط بهینگی را تضمین می کند .
روش هاي تقریبی - ابتکاري - راه حل هاي با کیفیت بالا را در زمان معقولی تولید می کنند اما تضمینی براي یافتن راه حل بهینه سراسري ندارند . در واقع الگوریتم هاي فراابتکاري یکی از انواع روش هاي بهینه سازي تقریبی هستند که داراي مکانیزم هاي خروج از بهینه محلی می باشند و قابل کاربرد در طیف وسیعی از مسائل هستند .[4] روش هاي فراابتکاري استفاده شده براي حل مسئله تخصیص درجه دوم شامل الگوریتم جستجوي ممنوع[5]3 ، الگوریتم زنبور عسل[6]4 ، الگوریتم رقابت استعماري[7]5 ، الگوریتم انجماد تدریجی[9 ,8]6 ، الگوریتم مهاجرت پرندگان[10]7 ، الگوریتم جستجوي هارمونی [11] ، الگوریتم سیستم هاي مورچه 8 [13 ,12] ، الگوریتم ژنتیک[15 ,14] 9 ، الگوریتم جستجوي تطبیقی تصادفی حریصانه [16]10 ، الگوریتم بهینه سازي فاخته[17]11 ، الگوریتم بهینه سازي علف هاي هرز [18] ، الگوریتم جستجوي گرانشی ترکیبی[19]12 ، الگوریتم بهینه سازي چرخه آب [20] ، الگوریتم ترکیبی چرخه آب و جستجوي هارمونی [21] ، الگوریتم خفاش اصلاح شده [22]13 - که یکی از الگوریتم هایی است که در سال 2015 براي حل این مساله استفاده شده است - و غیره می باشد . در این مقاله از الگوریتم بهینه سازي الکترومغناطیس براي حل مسائل تخصیص درجه دوم استفاده شده است .
الگوریتم بهینه سازي الکترومغناطیس 14
الگوریتم الکترومغناطیس براي حل مسائل بهینه سازي کاربرد دارد . این روش که تخستین بار توسط بیربیل و فنگ - - 2003 پیشنهاد شد همانند الگوریتم ژنتیک یک روش مبتنی بر جمعیت است . این الگوریتم براي حل مسائل ، از خاصیت جاذبه و دافعه ذرات باردار استفاده می کند . در این الگوریتم هر پاسخ - نقطه - به عنوان یک ذره باردار در فضا در نظر گرفته می شود و مقدار بار آن نیز بر اساس مقدار تابع هدف آن تعیین می گردد . پس از تعیین بار هر نقطه از جمعیت ، برآیند نیروي وارد بر نقاط و براي حرکت آنها در هر تکرار مشخص میگردد . همانند نیروهاي الکترومغناطیس ، برآیند نیروي وارد بر هر نقطه ، از جمع برداري تمام نیروهاي وارد بر آن به دست می آید . حال ذره هایی که بهینه تر باشند ، بار بیشتري دارند و می توانند ذرات دیگر را به سمت خود جذب کنند و ذراتی که بهینگی کمتري دارند ، باعث دفع دیگر ذرات می شوند . ایده اصلی در این الگوریتم بر این پایه استوار است که در اطراف نقاط خوب ، ممکن است نقاط بهتري یافت شود . به همین دلیل نقاط ضعیف به سمت نقاط بهینه حرکت داده می شوند . [25-23]
الگوریتم فراابتکاري الکترومغناطیس شامل مراحل زیر است که عبارتند از :
تولید جمعیت اولیه ، جستجوي محلی ، محاسبه بردار کل نیرو براي هر یک از اعضاء ، حرکت در جهت بردار نیروي وارده ، استفاده از جستجوي محلی در همسایگی ها براي پیدا کردن بهینه محلی . [26] در ادامه ، مراحل اجراي این الگوریتم بیان شده است :
-1 ایجاد m ذره n بُعدي - به تعداد بُعد فضاي حل - به عنوان حل آغازین - راه اندازي - . [24]
-2 محاسبه تابع هدف هر ذره - مقدار تابع هدف براي هر نقطه محاسبه شده و بهترین نقطه - نقطه با کمترین مقدار تابع هدف - به عنوان تعیین می شود . -
-3 انتخاب ذره با بهترین تابع هدف
-4 انجام جستجوي محلی در اطراف هر یک از ذرات با هدف یافتن بهترین ذره همجوار
-5 محاسبه بار هر ذره - متناسب با تابع هدف - :
بر اساس تئوري الکترومغناطیس ، نیرویی که دو ذره باردار بر هم وارد می کنند ، با مجذور فاصله آنها نسبت عکس و با مقدار بار هر یک از آنها نسبت مستقیم دارد . در این الگوریتم ، در هر تکرار ، بار نقاط بر اساس رابطه زیر تعیین می شود . نقطه ، پس از مقایسه مقدار تابع هدف آنها تعیین می شود . بین هر جفت نقطه ، نقطه اي که تابع هدف بهتري دارد ، نقطه دیگر را جذب و نقطه اي که تابع هدف بدتري دارد ، نقطه دیگر را دفع می کند و در صورتی که توابع هدف برابر باشند ، نقاط نیرویی به هم وارد نخواهند کرد . لذا در هر تکرار ، نقطه اي که بهترین مقدار تابع هدف را دارد ، سایر نقاط را جذب و نقطه اي که بدترین مقدار تابع هدف را دارد ، سایر نقاط را دفع می کند . مقدار نیروي وارده از طرف نقطه بر نقطه بصورت زیر محاسبه می گردد :نیروي وارده بر هر ذره مطابق با رابطه ي زیر - براي ذره با اندیس - 3 خواهد بود : 2 -6 محاسبه بردار نیروي کل وارده بر هر ذره - نهایتا بردار نیروي کل وارد بر هر نقطه از جمع برداري نیروهاي وارد بر آن نقطه از طرف سایر نقاط حاصل می شود - . -7 به منظور جلوگیري از همگرا شدن الگوریتم به یک جواب حداقل محلی - و یا اصطلاحا همگرایی زودرس یا پیش از موعد - ، بیربیل و همکاران - 2005 - فاز محاسبه نیروي کل را کمی تغییر دادند . آنها دورترین نقطه از را انتخاب کرده و آنرا نامیدند :
