الگوریتم های حافظه دار و بدون حافظه

الگوریتم ها به خصوص الگوریتم های فراابتکاری از دیدگاه مختلفی دسته بندی می شوند. امروزه بسیاری از الگوریتم های فراابتکاری از تجربه جستجوی خود برای راهنمائی عملیات جستجو استفاده می کنند.  یک ویژگی مهم از الگوریتم های فراابتکاری به منظور طبقه بندی آنها معیار تاریخچه جستجو (search history) می باشد. بر این اساس دو نوع الگوریتم های حافظه دار (memory method) و الگوریتم های بدون حافظه (memory-less method) ظهور پیدا می کنند.   

در الگوریتم‌های فراابتکاری فاقد حافظه از  اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به‌طور مثال تبرید شبیه‌سازی شده). هرچقدر انتخاب عملیات و راه حل ها تصادفی تر باشد استفاده از حافظه کم رنگ تر می شود به دلیل اینکه در حالت تصادفی نیاز به حافظه نمی باشد.  این در حالی است که در برخی از الگوریتم‌های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. استفاده از حافظه به عنوان یک عنصر اساسی و قدرتمند برای عملیات جستجو شناخته شده است. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند. در واقع، در الگوریتم های حافظه دار تصمیماتی که قبلاً گرفته شده است در حافظه نگهداری می شود و در ادامه راه و جواب های بعدی موثر هستند.

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

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

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

منابع

1. Joen Dahlberg, “Metaheuristics”, esearchgate,2015.
2. BLUM, ANDREA ROLI,” Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison”, ACM Computing Surveys, Vol. 35, No. 3, September 2003, pp. 268–308..