بخشی از مقاله
چکیده-
مساله تخصیص درجه دوم یکی از مسایل بهینه سازی ترکیبی است که به اختصاص تعدادی تسهیل به تعدادی مکان می پردازد وهدف به حداقل رساندن هزینه است.این مسئله یکی از مشترک مسائل با درجه پیچیدگی سخت می باشد که الگوریتمهای قطعی تنها قادر به حل نمونه های کوچکتر این مسئله می باشند. روش جستجوی محلی سریع از روشهایی است که برای حل اینگونه مسائل کاربرد زیادی دارد . اماباوجود قابلیت جستجوی فضای پهناورتر در این میان دیدگاه خاصی برای جستجویسیستمبهترارائهنشده است که منجر به کاهش کارایی روش می شود یعنی درمواردی که فاصله بین نقاط جستجو شده دارای گپ زیادبود ازاین طریق مناطقی ازمحدوده جستجو را که بررسی نشده اندتا حدامکان پیدا نموده وموردارزیابی قرارداد. هدف ارائه روشی است که بتوان دیدشهودی نسبت به فضای جستجو پیدانمود. روش پیشنهادی جدیدقادر می باشد میانگین بهترین جوابها درالگوریتم جستجوی محلی سریع را از 0/65 درصد به 0/26 درصد کاهش داده و به این ترتیب اکتشاف بهتری از فضای جستجورا داشته باشد. بررسی کارایی این روش روی توابع آزمون استاندارد و مقایسه آن با الگوریتم جستجوی محلی سریع بیانگر کیفیت مطلوب و برتری آن میباشد که نتایج خوبی را بر روی بازه وسیعی از مسائل جایگشتی ارائههایمیکند .
کلید واژه- اکتشاف، الگوریتمهای متاهیوریستیک،جستجوی فضای حالت، جستجوی محلی سریع، مسئله تخصیصفازیدرجه دو
-1 مقدمه
نزدیک به بهینه را در مدت زمان معقول بدست آورند. تخصیص درجه دوم که به QAP نیز معروف است از گروه -1-1مسئله تخصیص درجه دو هوشمند مسایل جایگشتی است که چون ابتدا در حوزه اقتصاد مطرح شده در حل QAP مایل به اختصاص تسهیلات در مکان مختلف میباشیم که حجم جریان بین دو به دوی تسهیلات معمولا به صورت یک مدل اقتصادی بیان می گردد اما کاربردهای آن در حیطه وسیعی از مسائل از جمله کاربردهای خوشه بندی مشخص است و هدف چیدن تسهیلات به گونه ای است که تسهیلات دارای حجم بالای جریان در نزدیکی یکدیگر قرار گیرندو مسائل تفکیک و چیدمان تسهیلات و... به چشم می خورد. در و در نهایت هزینه جابجایی بین تسهیلات کمینه گردد.[1]در این مساله هیچ تضمینی وجود ندارد که بتوان در زمان قابل نمایش ریاضی این مساله ماتریس مربعی شامل اعضای fi,j قبولی جواب بهینه را یافت وبرای حل آنها هیچ روشی درزمان نشانگر ارتباط حجم جریان بین دو تسهیلات i,jو ماتریس مربعی چند جمله ای وجود ندارد بنابراین از نقطه نظر محاسباتی ذاتا dبا اجزای dk,p نشانگر فاصله بین مکان k,pمیباشد.
مقاوم بوده ودر بدترین حالت هر الگوریتم برای حل این مسائل نیاز به زمان اجرا و مرتبه اجرایی نمایی دارد. توسعه روشهای متاهیوریستیک توانایی حل مسائل باابعاد بزرگ وتعداد متغیرهای اولین کاربرد عملیQAP در مکانیابی ساخت دانشکده ها بر اساس میزان جابجایی افراد بین دانشکده ها و پس از آن در حوزه وسیعی از مسائل دنیای واقعی مانند چیدمان، زمانبندی، ارتباطات و ... مطرح شد. همچنین می توان به مکان یابی دکمه های کیبورد بر اساس جریان استفاده ترتیب حروف با هدف کمینه سازی زمان تایپ و یا بکارگیری QAP در انتصاب نیروها در سمت های مختلف پنجمین با توجه به روش برخورد آنها اشاره کرد.
-2 مرور روشهای پیشین:
اخیرا از متاهیوریستیک ها به صورتکنگرهگسترده برای حل مسائل جایگشتی استفاده شده و از آنجا که کار با این الگوریتم ها ساده بوده و در رنج وسیعی از مسائل قابل استفاده اند پژوهش های فراوانی به منظور اعمال تغییرات متناسب با نوعمشترکمسالهازیک فراابتکاری خاص انجام شده که QAP نیز از این قائده مستثنا نبوده و انواع متاهیوریستیک ها برای حل آن بسط داده شده است. الگوریتمهای هیوریستیکی که برای حل مسئله QAP بکار گرفته شده اند عبارتند از:الگوریتم ژنتیک[2,3,4,5] ،روشها ی شبیه سازی سرد کردن فلزات [6,7] ، روشهای جستجوی محلی تکراری [8,9] ، الگوریتم کلونی مورچه ها[10 ,11] ، روشهای جستجوی تابو[12,13,14]، الگوریتم ازدحام ذرات[15,16] و رقابت استعماری.[17] هر رویکرد فرااکتشافی می تواند با هدف کاوش موثر و کارای فضای جستجو طراحی گردد.کاوش یا اصطلاحا اکتشاف که به معنای هدایت جستجو به مناطقی است که تا به حال دیده نشده اند به دلیل شناسایی سریع مناطقی از فضای جستجوی دارای راه حل های کیفیت بالا و از سوی دیگر برای هدر ندادن زمان طولانی در مناطقی از فضای جستجو که قبلا کاوش گردیده و یا راه حل با کیفیت بالایی فراهم نکرده اند دارای اهمیت است .[18] الگوریتمهایی برای اکتشاف فضای جستجو[19,20] مطرح شده اند. الگوریتم خاصی برای دستیابی به بهترین راه حل در تمام مسائل بهینه سازی وجود ندارد. در الگوریتمهای مطرح شده با توجه به نتایج بدست آمده الگوریتم جستجوی محلی سریع می تواند در ترکیب با روش ارائه شده برای حل مسائل QAP مناسب باشد.
-1-2 الگوریتم جستجوی محلی تکراری سریع :
در این الگوریتم - - NIFLS تغییراتی بر روی روش جستجوی محلی تکراری با یک روش ترکیب جدید اعمال گردیده است.ایده اصلی آن استفاده از یک خود بهبود دهنده تکراری در کنار عملگر ایجاد تغییرات تکاملی بوده که نتایج خوبی بر روی بازه وسیعی از مسایل جایگشتی ارائه میکند .[8] الگوریتم از جمعیت اولیه شامل دو عضو تشکیل شده که تعداد تکرارهای آن تابعی از پیچیدگی مساله میباشد. دو عضو اول بصورت جایگشت تصادفی مقدار دهی و هر جایگشت - رشته n تایی از اعداد بدون تکرار - یک تا - - nبا علامت π و هزینه آن جواب با F - π - نمایش داده میشود که هدف کمینه سازی F - π - است.
ترکیب: در شروع تمام شمارگانی را که در هر دو والد در یک مکان قرار گرفته انددر فرزند کپی میکند. در گام دوم یک موقعیت تصادفی خالی در فرزند انتخاب کرده و یک شماره که تاکنون در فرزند دیده نشده به تصادف در نظر گرفته و در موقعیت انتخاب شده جایگذاری میکند. برای جلوگیری از حصول فرزندان با شمارگان تکراری، اعداد موجود در دو والد را که در موقعیت انتخاب شده قرار دارندبه جایگاه خالی بعدی - سمت راست - انتقال داده و گام دوم مجدد تکرار میشود. در تصویر1 مثالی عددی شامل شش کروموزوم مشاهده میشود.
سیستم فازی
جهش: در گام بعد عملگر جهش لغزشی تصادفی را با هدف خود
هوشمند
بهبودی باید به فرزند بدست آمده در مرحله قبل اعمال کنیم. دو عدد تصادفی در بازه یک تا n را انتخاب کرده و عدد تصادفی بزرگتر را به قبل از عدد تصادفی کوچکتر انتقال داده و سپس تمامی اعداد قبل از عدد تصادفی کوچکتر تاعدد تصادفی بزرگتر را یک خانه به جلو منتقل می کنیم. مثال: 4 6 5ایران231 عنصر 2,4 انتخاب می شوند و نتیجه 4 2 3 1 6 5 می شود. جستجوی محلی دوتایی: در مرحله آخر این روش را روی نتایج جهش یافته اعمال می کنیم. در جدول شماره یک مشاهده می شود که یک جواب اولیه به عنوان ورودی در نظر گرفته و ارزیابی کرده و نتیجه آن به عنوان بهترین جواب انتخاب میشود، سپس ترکیباتی شامل جابجایی دو عنصر آن ایجاد شده و تک تک ارزیابی می شوند، در اولین باری که نتیجه ارزیابی از بهترین جواب شناخته شده بهتر باشد جایگزین بهترین جواب شده و جستجوی سایر جواب های ممکن از تغییر مکان دو عنصر بر
-3 روش پیشنهادی
کدامیک از آنها مورد جستجو قرار نگرفته است. الگوریتم در این در الگوریتمهای ترکیبی فضای حالت دیده نمی شود در نتیجه متوجه نمی شویم پنجمیندراینفضاکدام نواحی جستجو شده و حالت ممکن است سریع همگرا شده و یا در مینیمم محلی به جستجوی ترکیبی مشاهده نمود کنگره و نتایج را بهبود بخشید.در دام افتد. با حل این مشکل می توان تاثیر آن را بر روی با روش پیشنهادی مجدد بهبود نتایج را مورد بررسی قرار دادیم که در شکل2به نمایش درآمده است: الگوریتم NIFLS که جوابهای بدست آمده توسط آن نتوانسته بود نتایج خوبی را در این زمینه بدست آورد با استفادهمشترکازترکی ب
. در ای ن روش یک گام به الگوریتم مذکور اضافه شده که بعد از عملگر جهش وقبل از اینکه بهینه محلی روی جوابها اعمال شود تغییراتی روی جوابهای بدست آمده از مرحله جهش صورت می گیرد بدین صورت که : روش مشابه شبیه سازی سرد کردن فلزات می باشد یعنی یک دمای اولیه داریم که زیادبوده و در هر مرحله که نسل جدید ایجاد شود از این روش استفاده می شود و دما در هر بار مقداری کم می شود.اوایل الگوریتم مقدار دما زیاد بوده،عدد exp - -T/10000 - , T=30000 یک عدد بسیار کوچکی است پس یک عدد تصادفی بین - 0,1 - مسلما از این عدد بسیار کوچک،بزرگترو یا به احتمال خیلی زیاد از آن بزرگتر می باشد پس ایده اجرا می شود.
در حقیقت با این روش در اوایل الگوریتم اکتشاف فضای جستجو را بیشتر کرده و در اواخر آن را کمتر کرده که این کار دقیقا کار اکتشاف را انجام می دهد یعنی جاهایی را که تا حالا دیده نشده به این وسیله جستجو می کنیم این حرکت در اوایل الگوریتم بیشتر و بعد هر چه به اواخر الگوریتم می رسد استفاده از ایده ضعیفتر شده و با احتمال کمتر این کار انجام می شود. در الگوریتم NIFLS ارزیابی نهایی بعد از جهشها صورت می گیرد. هرجوابی که در این الگوریتم تولید شود یکبار در جستجوی محلی دوتایی که روش آن قبلا بیان شد
فرستاده شده و جواب بهتر را تولید می کند که در این الگوریتم یکبار عدد ارزیابی شده را ذخیره کرده و برای مراحل بعدی این مقدار تغییر می کند و در هر بار تغییر عدد جواب قبلی از حافظه پاک شده و مقدار جدید جایگزین آن می شود اما در روش ارائه شده جوابی که می خواهد تولید شود قبل از اینکه تصمیمی سیستمبرایش گرفته شود داخل لیستی نگهداری کرده سپس جایگشت مربوط به آن ارزیابی در روش پیشنهادی را توسط تابعی به عدد تبدیل نمودههایو معادل عددی تمامی جوابهایی که تا حال ارزیابی شده اند را ثبت و ذخیره می کن یم.در حقیقت بانکی از جوابها داریم که معادل عددیفازیتمامیونقاطی که تا حال دیده شده اند یا به بیان دیگر فضای جستجوی بازدید شده در این مرحله می باشند که این کار برای بررسی نقاط دیده نشده ضروری است. روش اختصاص معادل عددی به جایگشت و بالعکس: هوشمند برای تشکیل جایگشتها و در نظر گرفتن معادل برای هر کدام از
ایران
آنها ابتدا باید برای ایجاد تمامی جایگشتهای متغیرn که برابر n! است یک عدد معادل که معرف آن جایگشت می باشد تولید کرد.به طور مثال در شکل 3 برای ایجاد تمامی جایگشتهای شش شهر، که برابر 6! است از شش متغیر به نامهای - - i,j,k,z,w,x استفاده کرده و جایگشتهای حاصل از این اعداد را بدست آورده و برای هرکدام از آنها یک معادل عددی در نظر می گیریم:
