بخشی از مقاله
چکیده:
مسأله تخصیص درجه دوم یکی از مسائل بهینهسازی ترکیبی است که به اختصاص تعدادی تسهیل به مکان های معین میپردازد. هدف، تخصیص هر تسهیل به یک مکان میباشد که در آن هزینه کل حداقل گردد. از آنجایی که این مسأله در رده مسائل NP-hard قرار دارد، الگوریتمهای قطعی تنها قادر به حل نمونههای کوچک این مسأله - حداکثر به اندازه - 20 میباشند.
تاکنون مطالعات بسیاری در خصوص این مسأله انجام شده و الگوریتمها و روشهای گوناگونی توسط پژوهشگران و محققان مختلف برای حل این مسأله ارائه شده است. اما پژوهشگران همواره به دنبال یافتن روشی بهتر و کاراتر در این زمینه هستند. در این مقاله روشی نوین برگرفته از ترکیب الگوریتمهای بهینه سازی جنگل و رقابت استعماری معرفی شده است. نتایج آزمایشات انجام شده نشاندهندهی کارایی روش پیشنهادی در حل مسألهی فوق است.
-1 مقدمه:
مسألهی تخصیص درجه دوم 2 - QAP - برای اولین بار توسط کوپمنز و بکمن [9] به عنوان یک مدل ریاضی مرتبط با فعالیت های اقتصادی معرفی شد. هدف اصلی دراین مسأله انتساب مجموعهای از تسهیلات به مجموعهای از مکانهاست به نحوی که کمترین هزینه را متحمل شویم. مسألهی تخصیص درجه دوم در طراحی جایابی ساختمانها و همچنین چیدمان تجهیزات واحدهای صنعتی و غیره میتواند به عنوان یک مسأله بهینهسازی ترکیبی فرموله شود. شرکتهای تولیدی، زمان و هزینهی زیادی را برای طراحی و یا طراحی مجدد تجهیزات خود صرف می کنند. این طراحیها تأثیر عمدهای در عملکرد سیستم دارند و جایابی تجهیزات به شکل ضعیف موجب افزایش هزینه و کاهش کارایی سیستم نسبت به آنچه مطلوب مشتری میباشد می شود.
در مطالعات گذشته روشهای گوناگونی برای حل QAP معرفی شده است؛ از جمله، الگوریتمها و روشهای تولید جواب دقیق که در میان این الگوریتمها میتوان به روشهای برنامهنویسی پویا [6] و انشعاب و تحدید10]،[12 اشاره کرد؛ که روش انشعاب و تحدید در مطالعات گذشته به عنوان یک روش مناسب برای حل QAP جهت به دست آوردن جواب بهینه ارائه شده است. اما با توجه به قرار گرفتن QAP در کلاس NP-hard از نظر پیچیدگی محاسباتی، این روشها تنها قادر به حل مثالهایی با تعداد کمی تسهیلات است، بنابراین تنها راه ممکن برای حل QAP با تعداد فعالیتهای زیاد استفاده از الگوریتمهای ابتکاری و فراابتکاری است
از میان روش-های ابتکاری و فرا ابتکاری که در حل QAP به کار برده شدهاند میتوان به روشهای زیر اشاره کرد: روش شبیهسازی تبرید تدریجی13]،[17، روش جستجوی ممنوع13]،14،[16، الگوریتمهای ژنتیک7]،[2، الگوریتم ممتیک[4]، الگوریتم کلونی مورچهها[15] و الگوریتم رقابت استعماری.
با توجه به کاربرد فراوان الگوریتمهای الهام گرفته شده از طبیعت در حل مسائل بهینهسازی، محققان همواره در حال معرفی الگوریتم-های جدید و یا بهبود الگوریتمهای بهینه سازی موجود هستند. در این مقاله یک الگوریتم جدید با استفاده از ترکیب دو الگوریتم بهینهسازی جدید جنگل و رقابت استعماری معرفی و کارایی آن در حل QAP بررسی میشود.
-2 توصیف مدل مسألهی تخصیص درجه دوم
با داشتن یک مجموعه به نام N={1,2,3,..,n} و ماتریسهای n×n به نام F = {fij} و D = {dij} هدف در QAP یافتن یک جایگشت از مجموعه N است که بتواند مقدار تابع زیر را کمینه کند.
در مدل فوق n مکان وجود دارد و n تسهیل که باید به این مکانها اختصاص داده شوند. d فاصلهی حرکتی بین دو مکان k و l باشد که قرار است ساختمانهای جدید در آنها بنا شود. همچنین فرض کنید fij برابر با جریان میان دو تسهیل i و j است. هر تخصیص به صورت یک جایگشت ϕ از عناصر مجموعه N={1,2,3,..,n} تعریف میشود. به طوری که بدین معنی است که ساختمان i به محل k تخصیص داده شده است.
-3 الگوریتم رقابت استعماری
این الگوریتم برای اولین بار توسط گرگری و لوکاس در سال 2007 معرفی شد.[3] این الگوریتم نیز همانند سایر الگوریتمهای تکاملی با تعدادی جمعیت اولیه که هر کدام از آنها یک کشور نامیده میشوند، شروع میشود. تعدادی از بهترین عناصر جمعیت به عنوان استعمارگر انتخاب میشوند. باقیماندهی جمعیت نیز به عنوان مستعمره در نظر گرفته میشوند. برای یک مسألهی بهینهسازی n بعدی، یک کشور، به صورت یک آرایهی 1×n نمایش داده میشود. با شروع الگوریتم ابتدا مستعمرات را متناسب با قدرت استعمارگران به استعمارگران مختلف اختصاص میدهیم و امپراطوری ها تشکیل میشوند.
کشورهای استعمارگر با اعمال سیاست جذب - همگون سازی - در راستای محورهای مختلف بهینهسازی، کشورهای مستعمره را به سمت خود میکشند. ممکن است در خلال این همگون سازی کشور مستعمره از استعمارگرش قویتر شود، در اینصورت جای مستعمره و استعمارگر عوض خواهد شد. استعمارگران بسته به قدرتشان یا استفاده از مکانیسم رقابت استعماری مستعمرات استعمارگر ضعیفتر را به سمت خود جذب می کنند.
هر امپراطوری که نتواند در رقابت استعماری موفق عمل کند، از صحنهی رقابت استعماری، حذف خواهد شد. این حذف شدن به صورت تدریجی است، بدین معنی که امپراطوریهای ضعیف، مستعمرات خود را به مرور از دست داده و استعمارگری که دیگر مستعمرهای ندارد خود به عنوان مستعمرهی سایر استعمارگران در نظر گرفته میشود. در نهایت یک استعمارگر باقیخواهد ماند و اجرای الگوریتم با معرفی تک استعمارگر باقیمانده به عنوان جواب بهینه به اتمام خواهد رسید. روش دیگر اتمام این الگوریتم، ایجاد محدودیت برای تعداد تکرار اجرای الگوریتم است. در این حالت نیز اگر چندین کشور استعمارگر باقی مانده باشند، قویترین آنها به عنوان جواب بهینه در نظر گرفته میشود.
-4 الگوریتم بهینهسازی جنگل
الگوریتم بهینه سازی جنگل یکی از جدید ترین الگوریتم های تکاملی است که توسط قائمی و درخشانی معرفی شده است
این الگوریتم از انواع مختلف دانه پراکنی درختان موجود در جنگلها یعنی دانه پراکنی محلی و دانه پراکنی با فاصلهی زیاد الهام گرفته شده است. همانند سایر الگوریتمهای تکاملی، FOA نیز با یک جمعیت اولیه از درختان شروع میشود که هر درخت می-تواند یک جواب برای مسأله باشد. یک درخت علاوه بر مقادیر متغیرها دارای یک سن نیز می باشد که سن درخت در ابتدا صفر در نظر گرفته میشود. هر درخت به صورت یک آرایهی 1 × - 1 + Nvar - نشان داده میشود که در آن Nvar تعداد متغیرهای مسأله است.
این الگوریتم دارای دو عملگر اصلی دادهپراکنی محلی1 و دادهپراکنی سراسری2 است. عملگر دادهپراکنی محلی که به نوعی یک جستجوی محلی محسوب میشود برای درختان با عمر صفر اعمال میشود و یک همسایگی برای این درختان ایجاد میکند وسن تمامی درختان جنگل یک واحد افزایش مییابد. به ازای هر درخت با عمر 0 تعداد همسایگیهایی که ایجاد میشوند توسط یکی از پارامترهای الگوریتم با نام LSC3 تعیین میشود.
برای محدود سازی درختان موجود در جنگل از دو پارامتر استفاده میشود. متغیر اول life time بوده که مشخص کنندهی حداکثر سن هر درخت است و متغیر دیگر area limit است که برابر است با حداکثر درختانی که میتوانند در جنگل باشند. ابتدا درختانی که سن آن ها به life time رسیده است را از جنگل حذف کرده و به مجموعه کاندیدا اضافه میکنیم. مجموعهی کاندیدا شامل درختانی است که از جنگل حذف شده اند. سپس اگر تعداد درختان باقی مانده در جنگل بیشتر از متغیر area limit بود، درختان موجود در جنگل را بر اساس مقدار تابع برازش آنها مرتب کرده و به تعداد area limit از بهترین درختان را برای بقا در جنگل انتخاب و مابقی را به مجموعهی کاندیدا اضافه میکنیم.
عملگر دیگر این الگوریتم دادهپراکنی سراسری است. در این مرحله ابتدا تعدادی از درختان موجود در مجموعهی کاندیدا را انتخاب میکنیم، این تعداد توسط متغیر transfer rate که نشاندهندهی درصدی از درختان موجود در مجموعهی کاندیدا است مشخص میشود. سپس به تعداد مشخصی خانه از هر آرایه - درخت - را انتخاب و مقدار موجود در آن خانه از درخت را با یک مقدار جدید از بازهی مجاز برای متغیر های مسأله جایگزین می کنیم.
تعداد خانههای انتخاب شده از هر درخت توسط یکی دیگر از متغیرهای الگوریتم یعنی GSC4 مشخص میشود. پس از انجام عملیات فوق متغیر سن درخت را برابر صفر قرار داده و آن را به جنگل اضافه میکنیم. همانند سایر الگوریتمهای فراابتکاری میتوان سه شرط توقف را برای الگوریتم بهینهسازی جنگل در نظر گرفت: اول تکرار الگوریتم به تعدادی مشخص، دوم هیچ تغییری در مقدار تابع برازش بهترین درخت طی چندین تکرار مشاهده نشود و سومین شرط دست یابی به یک سطح دقت مشخص.
-5 الگوریتم پیشنهادی برای حل QAP
در این بخش با استفاده از ترکیب دو الگوریتم بهینهسازی جنگل و رقابت استعماری روشی نوین ارائه و برای حل QAP از آن استفاده خواهد شد.
-1-5 نحوه نمایش درخت ها:
هر درخت شامل یک آرایه 1× - 1+N - است. که در آن N تعداد تسهیلات مسأله و خانه آخر آرایه مربوط به متغیر سن هر درخت است. هر درخت بیانگر یک چیدمان جایگشتی از تسهیلات است. شکل 1 یک درخت فرضی را با 10 تسهیل نشان می دهد. شکل1 بیانگر آن است که به عنوان مثال تسهیل شماره 4 در خانه شماره 1 قرار گرفته است. متغیر سن درخت نمایش داده شده در شکل 1 برابر 0 است. روش تولید درختان اولیه جنگل به صورت تولید جایگشتهای تصادفی از تسهیلات مسأله است.
