پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE

پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE

این پایان نامه در سال 2011 با موضوع " پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE" توسط کارل دورکوتا از دانشگاه Czech پاراگوئه نگارش شده است. در ادامه مفاهیم و راهکارهای پیشنهادی مورد بررسی قرار گرفته شده است.

الگوریتم کرم شب تاب:

الگوریتم کرم شب تاب (FA) در سال 2008 توسط یانگ که از الگوریتم های طبیعت الهام گرفته شده است، معرفی شده است. این الگوریتم از رفتار "حشره" کرم شب تاب که شامل انتشار نور، جذب نور و جذب متقابل بهره می گیرد. این الگوریتم برای حل مسائل بهینه سازی پیوسته توسعه یافته است. شبه کد الگوریتم کرم شب تاب در شکل 1 نشان داده شده است.

شکل 1: شبه کد الگوریتم کرم شب تاب

فرآیند محاسباتی توزیع احتمالی موقعیت کرم شب تاب برای تکرارهای مختلف در شکل 2 نشان داده شده است.

شکل 2: فرآیند محاسباتی توزیع احتمالی موقعیت کرم شب تاب برای تکرارهای مختلف

 در این پایان نامه پس از توصیف الگوریتم کرم شب تاب، یک راه حل ممکن برای حل مسائل QAP گسسته که شامل جایگشت های عدد صحیح می باشد، پیشنهاد می دهد. می توان الگوریتم کرم شب تاب را به کمک مفاهیمی مانند جذابیت، فاصله و حرکت به تابع گسسته تبدیل نمود.

الگوریتم گسسته کرم شب تاب جدید (DFA) در داخل چارچوب SEAGE پیاده سازی شده است. این الگوریتم روی یازده مسئله QAP مختلف که از QAPLIB انتخاب شده است، مورد بررسی قرار گرفته شده است. که نتایج حاصل در این پایان نامه مورد بررسی و آنالیز قرار می گیرد.

SEAGE:

یک کار پایان نامه ای است که توسط ریچارد در دانشگاه Czech ساخنه شده است. این پروژه یک چارچوب بهینه سازی در درون زبان برنامه نویسی جاوا می باشد که برای حل مسائل بهینه سازی فراابتکاری مورد استفاده قرار می گیرد.

الگوریتم کرم شب تاب گسسته ساز برای حل مسئله تخصیص درجه دوم:

کرم شب تاب اولیه:

در کرم شب تاب اولیه راه حل اولیه در فضای جستجو به صورت یکنواخت پراکنده می شود. فضای جستجو در مسئله QAP مجموعه جایگشت ها یعنی S_n می باشد که نیاز به تولید m جایگشت تصادفی از بین (1,2,…,n) جایگشت می باشد که به عنوان کرم شب تاب های اولیه محسوب می شوند. برای مقداردهی اولیه می توان از روش حریصانه استفاده نمود.

تابع فاصله:

اساساً، دو روش برای اندازه گیری فاصله بین دو جایگشت وجود دارد: الف: فاصله هامینگ و ب: تعداد جابه جائی های لازم برای رسیدن از راه حل اولیه به راه حل دوم. برای مثال برای جایگشت های زیر که عضو S_n می باشند :

به فرمول زیر تقسیم می شوند. ابتدا باید مرحله بتا و سپس الفا اجرا شود.

مرحله بتا:

برای مثال:

مرحله الفا :

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

نتایج:

جدول 1: بررسی نتایج برای مسائل مختلف QAPLIB با استفاده از ده تا از بهترین نتایج

نتیجه گیری:

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

DFA در چارچوب سطح انتزاعی SEAGE پیاده سازی شده است که به کاربر اجازه می دهد که توابع فاصله، جذابیت و حرکت را به اندازه دلخواه خود تعریف نماید. این تکنیک باعث می شود الگوریتم قابلیت حل مسائل مختلف QAP را داشته باشد.

اگر فردی بخواهد از DFA برای حل مسئله رنگ آمیزی گراف (GCP) استفاده کند، نیازمند این است که تعریف کند چطور فاصله بین دو راه حل GCP را اندازه گیری کند، همچنین جذابیت و حرکت راه حل ها را چطور اندازه گیری نماید.

[1].  Karel Durkota,“ IMPLEMENTATION OF A DISCRETE FIREFLY ALGORITHM FOR THE QAP PROBLEM WITHIN THE SEAGE FRAMEWORK”, CZECH TECHNICAL UNIVERSITY IN PRAGUE FACULTY OF ELECTRICAL ENGINEERINGy,May 2011.