ساختارهای ممتیکی موازی

مقاله: ساختارهای ممتیکی موازی

این مقاله در سال 2012 با موضوع "ساختارهای ممتیکی موازی" توسط Fabio Caraffini,  Ferrante Neri, Giovanni Iacca , Aran Mol در مجله دانش های اطلاعاتی چاپ شده است. ساختارهای محاسباتی ممتیک، الگوریتم هایی با ترکیبی از عملگرهای ناهمگن بنام meme برای حل مسائل بهینه سازی می باشند. به منظور حل این گونه مسائل، در این مقاله یک ساختار موثر ساده بنام ساختار ممتیکی موازی (PMS) پیشنهاد می شود. PMS یک الگوریتم حل بهینه سازی ساده است که با عملگرهای درختی ترکیب شده است. یکی از آنها جستجوی تصادفی سراسری است که کل فضا را برای یافتن مناطق امیدوارکننده اکتشاف می کند.

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

الگوریتم ساختار ممتیکی موازی، علی رغم سادگی آن، کارائی قابل قبولی را در مقایسه با الگوریتم های فراابتکاری محبوب و الگوریتم های بهینه سازی مدرن که وضعیت state-of-the-art در این زمینه می باشند را نشان می دهد. با توجه به ساختار ساده این الگوریتم، الگوریتم خیلی انعطاف پذیر برای ویژگی های مسائل مختلف و مقادیر عددی می باشد. برخلاف الگوریتم مدرن که برای بعضی از مسائل Benchmark و بعضی از مقادیر عددی مشخص شده اند. الگوریتم ساختار ممتیکی موازی راه حل هایی با کیفیت بالا در زمینه های مختلف و متنوع ارائه می دهد. به عنوان مثال برای مسائل با ابعاد کم و مقیاس بزرگ کارائی دارد. یک مثال کاربردی در زمینه سنسورهای مغناطیسی عملکرد مناسب الگوریتم پیشنهادی را نشان می دهد. این مقاله تائید اعتباری را از Ockham’s Razor in MC دارد.

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

پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE

پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE

این پایان نامه در سال 2011 با موضوع " پیاده سازی از یک الگوریتم کرم شب تاب گسسته برای حل مسئله QAP در چارچوب SEAGE" توسط کارل دورکوتا از دانشگاه Czech پاراگوئه نگارش شده است. در ادامه مفاهیم و راهکارهای پیشنهادی مورد بررسی قرار گرفته شده است.

الگوریتم کرم شب تاب:

الگوریتم کرم شب تاب (FA) در سال 2008 توسط یانگ که از الگوریتم های طبیعت الهام گرفته شده است، معرفی شده است. این الگوریتم از رفتار "حشره" کرم شب تاب که شامل انتشار نور، جذب نور و جذب متقابل بهره می گیرد. این الگوریتم برای حل مسائل بهینه سازی پیوسته توسعه یافته است. شبه کد الگوریتم کرم شب تاب در شکل 1 نشان داده شده است.