الگوریتم ممتیک مبتنی بر آزادگی برای حل مسئله 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  ( اکتشاف ) : یعنی سراسری بودن جستجو برای رسیدن به کیفیت سراسری مولفه ها می باشد.