بهینه سازی ترکیبی مسئله جایگشتی تخصیص درجه دوم (QAP) با استفاده از الگوریتم مبتنی بر اپتیک (OIO)

بهینه سازی ترکیبی شاخه وسیعی از تحقیق در عملیات و علم مدیریت به حساب میآید . ترکیبیات نیز جزقدیمی ترین مباحث علم ریاضی بشمار میرود. از میان این مسائل، مسئله تخصیص مضاعف که شکل کلی چندمسئله مهم ازجمله مسئله فروشنده دوره گرد، مسئله تخصیص خطی و سایر مسائل میباشد و از نظر ساختاری هم ارز آنها بشمار میرود از اهمیت بالایی برخوردار است. در مسائل تخصیص مضاعف هدف تخصیص مجموعه ای ازتجهیزات را به مجموعه ای از محلها است، به طوری که هزینه آن، که تابعی از فاصله و جریانی که بین دستگاهها میباشد کمینه شود. بسیاری از مسائل دنیای واقعی مثل مسئله تخصیص اتاقهای خاص در بیمارستان ها،چیدمان اتاق عمل، پردازش تصویر، و بیشمار مسئله از مسائل دنیای واقعی را میتوان در قالب این مسئله فرمولبندی کرد. لذا تمرکز بر روی حل این گونه مسائل از اهمیت خاصی برخوردار است . روشهای گوناگونی برای حل این مسئله بصورت دقیق ارائه شده است . اما به علت ساختار خاص اینگونه مسائل ترکیبی، با افزایش اندازه مسئله، حل این مسائل بسیار دشوار و غیر ممکن می باشد. بنابراین استفاده از الگوریتم های فرا ابتکاری از جمله الگوریتم مبتنی بر اپتیکOIO امری ضروری است. خروجی پایان نامه برای الگوریتم مبتنی بر اپتیک، برنامه کامپیوتری به زبان MATLABبوده و قادر خواهد بود فرآیند بهینه سازی را صورت دهد. که طبق نتایج بدست آمده و مقایسه آن با جواب های کتابخانه مرکزی مسائل تخصیص مضاعفQAPLIB مشخص شد که این الگوریتم برای مسائل کوچک کارایی ۰۱۱ %و برای مسائل متوسط و بزرگ نیز از کارایی ۶۹ % برخوردار است، و در حالت کلی برای حل مسائل جایگشتی از کارایی بالایی برخوردار است

کلیدواژه ها:

بهینه سازی ترکیبی ، مسئلهی تخصیص درجه دو ، الگوریتم اپتیک