الگوریتم ممتیک مبتنی بر آزادگی برای حل مسئله QAP

معرفی پایان نامه: الگوریتم ممتیک مبتنی بر آزادگی برای حل مسئله QAP

این پایان نامه کارشناسی ارشد در سال 2012 توسط Francesco Puglierin  در دانشگاه Utrecht هلند دفاع شده است. در این پایان نامه مسئله QAP به کمک یک الگوریتم فراابتکاری جدید که BIMP-QAP نامگذاری شده است حل شده است. این الگوریتم از ساختار ممتیک استفاده کرده است که به جای استفاده از الگوریتم ژنتیک برای بدست آوردن نسل های بعدی از یک عملگر جدید بنام Perturb() برای تغییر راه حل ها استفاده می کند. در این روش اطلاعات را روی مولفه های منفرد از طریق جستجو ذخیره می کند. این اطلاعات از طریق عملگرPerturb() که الهام گرفته شده از راه حل های مدل راهزنی چند سلاحی (multi-Armed Bandit Model) به جستجو کمک می کند. کارائی و همگرائی BIMP-QAP بیشتر از Multi-Start Local Search می باشد. همچنین عملگر جدید Perturb() نسبت به دیدگاه های تصادفی راه حل های فعلی را  به راه حل های بهتری تغییر می دهد.

در این روش مولفه ها با بالاترین رتبه راه حل، روی راه حل اصلی اجرا می شوند. میزان رتبه با فرمول های الهام گرفته شده از مدل راهزنی چند سلاحی و UCB به طور ویژه محاسبه می شود. این فرمول دو واژه ذیل را با هم ترکیب می کند:

اولی واژه Exploitation(استخراج یا بهره وری) : یعنی بدست آوردن پاسخ های بهتر حول یک پاسخ و جستجوی محلی می باشد. این کار را به کمک تخمین حدسی کیفیت یک مولفه را تضمین می کند. دومی واژه Exploration  ( اکتشاف ) : یعنی سراسری بودن جستجو برای رسیدن به کیفیت سراسری مولفه ها می باشد.

این روش به دنبال پیدا کردن اولویت بیشتر است. چون رفتار آن همگراست. ولی الگوریتم برای داده های بزرگ به آن بهترین جواب مد نظرنمی رسد. در این مورد MLS می تواند کمک کند: در هر نمونه منفرد و آزمایش جداگانه الگوریتم BIMP-QAP نسبت به جستجوی محلی آغازگر چندگانه بهتر عمل می کند.

این بدین معنا نیست که فقط تغییر پارامتر باعث بازدهی بهتر می شود بلکه بدون تغییر پارامتر بازدهی را بهتر از قبل می کند. رفتار الگوریتم به پیکربندی پارامترها وابسته است. در نمونه های کوچکتر برای رسیدن به جستجوی سراسری نیاز به پیدا کردن تعداد مینیمم بیشتری می باشد. برای بهتر شدن این نتایج از عملگر  Perturb()  استفاده می شود. برخلاف روش RND از انتخاب مولفه های تصادفی استفاده نمی شود. نتایج حاکی از عملکرد بهتر RND نسبت به LMS می باشد. اما در اکثر موارد عملکرد بدتری نسبت به BIMP-QAP دارد چون از ساختار ترکیبی استفاده شده است.نشان داده می شود که عملگر Perturb() تاثیر زیادی در عملکرد الگوریتم های فراابتکاری دارد. روش مقایسه این الگوریتم به دلیل ساختار متفاوتش با بقیه روش ها فرق می کند. در این روش از ماتریس های متقارن استفاده می شود. روش های جستجوی محلی مانند 2-opt و جستجوی ممنوعه از ساده ترین روش ها برای جستجو هستند که این روش ها معروف به مدل MAB سنتی می باشند.عملگر Perturb() از UCB الهام گرفته شده است.مشکل ممنوعه این است که ممکن است محدودیت ها نقض شوند. به همین دلیل در این پایان نامه از 2-opt استفاده شده است.

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

مدل راهزنی چند سلاحی یا MDA: Multi-Armed Bandit

این مدل در سال 1951 توسط رابینز شکل گرفته است. این مدل از قماربازی برگرفته شده است که چطور خرج شود. به منظور حداکثر کردن سود از توزیع احتمال مستقل و نمونه اولیه استفاده می شود. این مدل در جنگ جهانی دوم ارائه شد.  در سال 1979 گیتینز با سیاست رتبه بندی یعنی به حالت فعلی یک امتیاز داده شود و از بین تمام حالات بالاترین رتبه انتخاب شود باعث حداکثر کردن می شود. این سیاست مرسوم به Index policy می باشد.

در اینجا باید به جای یک مولفه از چند مولفه استفاده شود. اندازه گیری کیفیت مولفه به مولفه های باقی مانده وابسته است.  جالب خواهد بود که تعادل بین استخراج و اکتشاف در cUBC در سناریوی جدید برقرار می شود.

لازم به توضیح است که منظور از جستجوی محلی چندگانه(MLS) یکی از ساده ترین الگوریتم های فراابتکاری محسوب می شود. که به دو صورت first-Improvement local search و Best-Improvement local search می باشد. در جستجوی محلی بهبود اولیه مانند جستجوهای محلی معمولی همسایگان راه حل فعلی مورد بررسی قرار می گیرند به محض رسیدن به همسایه بهتر آن راه حل با راه حل فعلی جایگزین می شود.

در جستجوی محلی تکرارکننده (ILS) پس از یافتن حداقل محلی یک آشفتگی ایجاد کرده و ادامه الگوریتم از آن نقطه به بعد انجام شود. وجود آشفتگی بخشی از الگوریتم می باشد که اگر مقدار آن کم باشد از حداقل محلی نمی تواند خارج شود ولی اگر مقدار آشفتگی بالا باشد جستجوی محلی چندگانه تاثیر کمتری روی الگوریتم خواهد داشت.

منابع:

[1]. Francesco, Puglierin,” A Bandit-Inspired Memetic Algorithm for Quadratic Assignment Problems”, utrecht university, August 2012.