بخشی از مقاله
چکیده
مساله تخصیص درجه دو از جمله معروفترین مسایل با درجه پیچیدگی بالا در حوزه بهینه سازی می باشد در این مقاله به ارایه مدل ریاضی جهت حل مساله تخصیص درجه دوم و سپس روش حل جدیدی تحت عنوان الگوریتم انفجار نارنجک پرداخته می شود به منظور بهبود الگوریتم ، تغییراتی در نحوه انتخاب مکان نارنجک در مرحله بعد و نحوه شدنی نمودن جوابهای تولید شده در فضای نمونه اعمال شده است همچنین در راستای افزایش تنوع جوابها از مفهوم نارنجک آزاد استفاده شده است جهت تحلیل کیفیت الگوریتم پیشنهادی تعدادی مسایل استاندارد ارایه گردیده و نتایج الگوریتم پیشنهادی با جواب های بدست امده از نزدیکترین مقالات موجود در ادبیات موضوع مقایسه می گردد. نتایج حاکی از کیفیت بالای الگوریتم پیشنهادی در یافتن جواب برای مساله تخصیص درجه دوم می باشد.
.1 مقدمه
مسئله تخصیص درجه دوم یکی از مسایل بهینه سازی ترکیبی است که در خصوص آن جهت تخصیص تعدادی تسهیل1 به تعدادی مکان بررسی ها و پژوهش هایی انجام شده است. موضوعی که در این فرایند اهمیت ویژه ای دارد بحث هزینه های تخصیص می باشد که تلاش در این مسئله بر حداقل سازی این گروه از هزینه ها می باشد . مساله QAP در بسیاری از کاربردها مورد استفاده قرار گرفته اند که از جمله می توان به چیدمان ساختمان-ها در بیمارستان ها، مدیریت انبارها و استراتژی های توزیع، حداقل سازی طول سیم در مدارهای الکترونیک، تخصیص برخی کارخانجات به برخی مکان ها، مسئله سیم کشی پشت مدار، طراحی پانلهای کنترلی و صفحه کلید ماشین نویس ها اشاره نمود.
در طول دهه های اخیر الگوریتم های الهام گرفتهشده از طبیعت به طور وسیعی برای حل مسائل بهینه سازی مختلف استفاده شده است.[1] یافتن راه حل های بهینه برای اکثر مسایل بهینه سازی که در خیلی از زمینه های کاربردی و عملی مشاهده می گردند کاری دشوار و سخت است. روشهای حل مسائل بهینه سازی مشتمل بر دو دسته روشهای دقیق و روشهای تقریبی می باشد. روشهای دقیق راه حل های بهینه را به دست آورده و شرایط بهینگی را تضمین می کنند.
روشهای تقریبی - ابتکاری - راه حل-های باکیفیت بالا را در زمان معقولی، تولید می کنند، اما تضمینی برای یافتن راه حل بهینه سراسری ندارند.[2] برای حل مسائل تخصیص درجه دوم با ابعاد بزرگتر از 20،معمولاً روشهای دقیق قابل حل نیستند و یا در صورت حل شدن به لحاظ زمانی توجیه اقتصادی ندارند. مساله تخصیص درجه دوم با ابعاد ذکر شده یکی از مسایل بهینه سازی ترکیباتی NP-COMPLETE می باشد این مسایل با ابعاد بزرگتر از 20،معمولاً از روشهای دقیق قابل حل نیستند و یا در صورت حل شدن به لحاظ زمانی توجیه اقتصادی ندارند. لذا در این حالت ها از روشهای فراابتکاری استفاده می گردد..[3]
از جمله کارهای انجام شده برای حل مساله تخصیص درجه دوم می توان به کارهایی نظیردمیرل و لین ژونگ لیو و یین ژنگ لی2 با استفاده از مدل های جدید و الگوریتم ژنتیک برای مساله تخصیص درجه دوم فازی .[4] اوزبکیر و همکاران3 از الگوریتم جستجوی غذای زنبور عسل برای حل مساله QAP استفاده نمودند.[5] اشاره نمود. از الگوریتمهای متداول فراابتکاری مبتنی بر یک جواب میتوان الگوریتم جستجوی هارمونی[6] و الگوریتم تبرید شبیهسازی شده[7] را نام برد. از الگوریتمهای متداول فراابتکاری مبتنی بر جمعیت که بروی QAP پیاده سازی شده اند ، میتوان الگوریتمهای تکاملی[8] - الگوریتم ژنتیک، برنامهریزی ژنتیک - ، بهینهسازی کلونی مورچگان[9]، کلونی زنبورها[10] و الگوریتم فاخته[11] را نام برد.
در این مقاله روشی با استفاده از الگوریتم انفجار نارنجک برای حل مساله تخصیص درجه 2 ارائه شده است . نتایج به دست آمده از روش پیشنهادی نشان می دهند که روش پیشنهادی از نظر دقت و یافتن جوابهای بهینه محلی و سراسری نسبت به روشهای دیگر بهتر عمل می کند . ادامه مقاله به این صورت سازماندهی شده است : در بخش2 مدل ریاضی حل مساله تخصیصی درجه دو معرفی می شود و در بخش 3 الگوریتم انفجار نارنجک و پارامترهای آن بررسی شده است. در بخش 4 روش پیشنهادی الگوریتم بروی مساله QAP پیاده سازی می شود در بخش 5 ارزیابی مقایسه با سایر الگوریتمها بیان می شود و در نهایت بخش آخر به نتیجه گیری می پردازد .
.2 مدل ریاضی حل مساله تخصیص درجه دو:
مسئله تخصیص درجه دوم اغلب برای توصیف یک مسئله مکان استفاده میشود. انتساب n تسهیل به n مکان که با هزینه متناسب با جریان بین ضرب تسهیلات با فاصله آنها است. در این بررسی مدل مربوط به روش حل مسله تخصیص درجه دو به کمک الگوریتم انفجار نارنجک مورد بررسی قرار گرفته است.
-1-2 تعریف پارامترهای مدل:
پارامترهای به کار رفته در مدل ریاضی مساله QAP به شرح زیر می باشد:
ماتریس جریان: ماتریسی است که میزان ارتباط یا جریان مواد بین دو تسهیل i و j را نشان دهد.
ماتریس فاصله: ماتریسی است که فاصله بین دو مکان K و l را نشان می دهد N 1'…' Q - و - O 1'…'Q
.3 الگوریتم انفجار نارنجک:
روش انفجار نارنجک یکی از روش های جدید فرا ابتکاری میباشد که توسط اهری و همکاران[12] در سال 2010 معرفی شده است. ایده اصلی ارایه این الگوریتم بر اساس مشاهده ی انفجار نارنجک و پرتاب ترکش های مشعب شده از آن می باشد. هر ترکش با فرود در هر نقطه با توجه به اهمیت آن نقطه، مقدار خرابی مشخصی را ایجاد می کند. مقادیر بالای خرابی حاکی از آن است که ترکش در نقطه ی مناسبی فرود آمده است. برای ایجاد خرابی های بیشتر مکان پرتاب نارنجک بعدی از بین بهترین مکان ترکش ها انتخاب می شود.
اهری و همکاران در مقاله خود اقدام به ارایه مفهوم الگوریتم و پیاده سازی آن روی تعداد مختلفی مساله نموده اند و نهایتا نشان دادهاند که الگوریتم فوق از کارایی بالایی در حل مسایل مختلف مهندسی نسبت به الگوریتم های فراابتکاری دیگر مانند الگوریتم زنبور عسل و ژنتیک برخوردار است. [ 13]جمال ارکات و مهدی حسین آبادی فراهانی جهت حل مساله تشکیل سلول پویا ازالگوریتم نارنجک استفاده کرده اند [14].علی حسامی نقشبندی و همکاران در مقاله خود به ارایه الگوریتم انفجار نارنجک جهت حل مساله جایابی بهینه واحدهای انداز ه گیری فازور جهت مشاهده پذیری سیستم قدرت پرداخته اند.
4. روش پیشنهادی الگوریتم انفجار نارنجک برای حل مساله QAP
در این بخش به بیان روش حل پیشنهادی پرداخته می شود. ابتدا ساختار جواب و سپس گام ها و پارامتر های الگوریتم به تفکیک بیان می شود.ابتدا یک نارنجک بصورت تصادفی پرتاب می شود با توجه به ماتریس های جریان و مسافت داده شده اولین جواب را تولید میکند کوچکترین عدد در جواب تولید شده را به خانه اول و کوچکترین عدد بعدی را در خانه دوم قرار میدهیم و به همین ترتیب جواب تولید شده را مرتب میکنیم - گسسته سازی - یعنی اولین تسهیل را در خانه یک و دومین تسهیل در خانه دو والی آخر . سپس در اطراف هر جواب 60 همسایگی در بازه [0,1]در نظر گرفته می شود و توسط تابع هدف مورد ارزیابی قرار میگیرد ، هدف در این مسله مینیم کردن مجموع ضریب بین جریان و فاصله تسهیلات است پس از ارزیابی 60 نقطه در صورتی که تابع هدف همسایگی بهتری نسبت به محل فعلی پیدا کند آن نقطه انتخابی برای پرتاب نارجک بعدی در نظر گرفته می شود این الگوریتم مجهز به حافظه می باشد و بهترین نقطه یافت شده را در خود نگهداری می کند.
