بخشی از مقاله
چکیده
مسئله تخصیص درجه دوم - QAP - یکی از مسائل بهینه سازی ترکیبی است که به اختصاص تعدادی تسهیل به تعدادی مکان محدود میپردازد. هدف، تخصیص هر وسیله به یک مکان میباشد بهطوری که هزینهی کل حداقل شود. مسائل تخصیص درجهی دوم به دلیل کاربردهای فراوانی مانند تخصیص ماشینها به سلولهای کاری، تخصیص کارخانه ها به مکانها، طراحی انبار، جایابی قطعات در قفسههای انبار و... از اهمیت بالایی برخوردار میباشند، اما مسالهی QAP در دستهی مسائل NP-HARD قرار میگیرد.
الگوریتمهای قطعی در انداره-های بزرگ کارایی خود را برای حل این مسئله از دست میدهند. اتخاد یک رویکرد مناسب برای حل این مسئله یک موضوع بحث برانگیز در میان محققان است. از اینرو برای حل مسئله تخصیص درجه دوم از الگوریتم کلونی زنبور عسل استفاده میکنیم. الگوریتم کلونی زنبور عسل یک روش فراابتکاری جدید تکاملیست که برای مسائل پیچیده کارایی بالایی دارد. سپس نتایج عددی را با روشهای دقیق مقایسه مینماییم.
-1مقدمه
کپمنز و بکمن اولین بار در سال 1957، مسئلهی تخصیص درجه دوم - QAP - را به عنوان یک مدل ریاضی معرفی نمودند . [1] مسئلهی تخصیص درجهی دوم یکی از مهمترین مسائل مدلسازی ریاضی است که میتواند در بسیاری از مشکلات مهندسی صنایع و مدیریت استفاده شود. برای مثال مساله تخصیص درجه دوم در طراحی جایابی ساختمانها، تجهزات و واحدهای صنعتی، برنامه-ریزی خطوط تولید موازی و... میتواند به عنوان یک مسئلهی بهینه سازی ترکیبی فرموله شود.
شرکتهای تولیدی زمان و هزینهی زیادی برای طراحی و طراحی مجدد تجهیزات خود میپردازنند. و این طراحیها تاثیری بسزایی بر عملکرد سیستم دارد و جایابی تسهیلات به شکل ضعیف موجب افزایش هزینه و کاهش کارایی سیستم می-شود. مسئلهQAP یک مسئلهی NP-HARD کامل می-باشد و الگوریتمهای قطعی تنها قادر به حل مسائل در ابعاد کوچک میباشند. بنابراین روشهای فراابتکاری برای حل آن میتوانند مورد توجه واقع شوند. زیرا این الگوریتمها قادر هستند که جوابهای نزدیک به بهینه را در زمانهای معقول به دست آورند.[2]
روشهای حل مسائل بهینهسازی برای حل مسئله تخصیص درجه دوم، مشتمل بر دو دسته، روشهای دقیق و روشهای تقریبی میباشند. روشهای دقیق، راه حل بهینه را به دست میآورند و شرایط بهینگی را تضمین می-کنند که میتوان به روش شاخه و کران[3] و برنامهریزی پویا[4] اشاره کرد. روشهای تقریبی - ابتکاری و فراابتکاری - راهحلهایی با کیفیت خوب را در زمان معقول، تولید می کنند، اما تضمینی برای یافتن راه حل بهینه سراسری نمی دهند.[5]
مسئله تخصیص درجه دوم یک مساله با پیچیدگی نمایی است. به طور کلی مسائل با ابعاد بزرگتر با روشهای دقیق قابل حل نیستند و یا در صورت حل شدن به لحاظ زمانی توجیه اقتصادی ندارند، فلذا در این حالت از روش های فراابتکاری استفاده میشود. در واقع الگوریتمهای فراابتکاری، یکی از انواع الگوریتمهای بهینهسازی تقریبی هستند که دارای مکانیزم خروج از بهینه محلی میباشند و قابل کاربرد در طیف وسیعی از مسائل هستند.[6]
مسئلهی تخصیص درجه دوم، یک مسئله هوش ازدحامی ست[7] ، هوش ازدحامی یک روش حل مسئله است که ریشه در تعامل افراد در جمعیت آن دارد. انگلبارت هوش ازدحامی را الگوریتمی تعریف میکند که رفتار اطلاعاتی بین افراد را بررسی میکند و برمبنای این اطلاعات تصمیمگیری را انجام میدهد.[8] همانطور که قبلا هم اشاره شد، روشهای دقیق مانند روش شاخه و کران [4] در اندازهی بزرگ کارایی خود را از دست می-دهند و برای حل مسئله در اندازههای بزرگ باید از الگوریتمهای فراابتکاری استفاده شود. در زیر به تعدادی از پژوهشهایی که به وسیله الگوریتمهای هوش ازدحامی انجام شده است اشاره میشود.
دیمرل و همکاران مسئله تخصیص درجه دوم را با استفاده از الگوریتم کلونی مورچگان حل میکنند و سپس برای تعیین کارایی الگوریتم، آن را با سایر الگوریتمهای فرا ابتکاری مقایسه میکنند.[9] پرهیزگار و همکاران مسئله تخصیص درجه دوم را با استفاده از الگوریتم بهینه سازی چرخه آب حل میکنند و سپس برای بررسی کارایی الگوریتم ارائه شده را بروی توابع آزمون استاندارد پیاده سازی میکنند.[10] محمدی و همکاران یک الگوریتم ترکیبی برمبنای روش ژنتیک برای حل مسئله تخصیص درجه دوم ارائه میدهند.
[11] آکان و همکاران مسئله تخصیص درجه دوم را به صورت یک الگوریتم ترکیبی برمبنای الگوریتم جستجوی ممنوع حل میکنند و بیان می کنند که الگوریتم ارائه شده در اندازههای متوسط و کوچک - اندازه های کمتر از - 50 کارایی بالایی دارد.[12] دژم و همکاران الگوریتم فاخته را برای حل مسئله تخصیص درجه دوم ارائه میدهند و سپس الگوریتم ارائهشده را با الگوریتم ژنتیک مقایسه مینمایند.[13] رسنده و همکاران مسئله تخصیص درجه دوم را با استفاده از الگوریتم جستجوی تصادفی حریصانه حل نموده و سپس کارایی الگوریتم ارائه شده را بررسی مینمایند.[14] حفیظ و همکاران یک رویکرد یادگیری احتمالی را برمبنای الگوریتم ازدحام ذارت برای حل مسئله تخصیص درجه دوم ارائه میدهند.[15]
در این مقاله مسئله تخصیص درجه دوم را با استفاده از الگوریتم فراابتکاری کلونی زنبور عسل - ABC - حل می نماییم. الگوریتم کلونی زنبور عسل یک الگوریتم هوش ازدحامی است و اولین بار در سال 2005 توسط کارابوگا ارائه شده است.[16] در ابتدا مسئلهی تخصیص درجه دوم توضیح داده میشود. سپس الگوریتم کلونی زنبور عسل تشریح میشود و در نهایت مسئله تخصیص درجه دوم با الگوریتم زنبور عسل حل میشود.
-2مسئله تخصیص درجه دوم
مسئله تخصیص درجه دوم، دستهای از مسائل تخصیص تسهیلات به مکانهای کاندید شده میباشد که میتواند ارتباط بین تسهیلات جدید را نیز در نظر بگیرد. تفاوت مسئله تخصیص درجه دوم با مکانیابی چند تسهیلی در آن است که در مسائل QAP مکانهای کاندید شده برای تخصیص محدوداند اما در مسائل مکانیابی چند تسهیلی، فضا پیوسته و نامحدود است. در واقع میتوان گفت مسئله تخصیص درجه دوم حالتی از مسئله تخصیص است که هزینهی تخصیص براساس تخصیص همزمان دو تسهیل قابل محاسبه است و این در صورتیست که این دو تسهیل با هم ارتباط منطقی داشته باشند.
کاربردهای متنوع دیگر مسئله تخصیص درجه دوم میتواند شامل چیدمان ماشین آلات یک واحد صنعتی، مسئله مدار، طراحی پانلهای کنترلی و صفحه کلید دستگاه تایپ، مرتب سازی داده های مرتبط به هم در یک نوار مغناطیسی، تخصیص فرایندها به پردازنده ها در یک محیط پردازش توزیع شده، مساله چینش در طراحی VLSI، تحلیل واکنشهای شیمیایی در ترکیبات آلی، رتبه بندی داده های باستانی باشند.[17]
