الگوریتم های فرابتکاری چیست؟ %100 الگوریتم های فراابتکاری

Q: الگوریتم فراابتکاری چیست؟

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

Q: طبقه بندی الگوریتم های فراابتکاری چگونه است؟

رایج ترین روش طبقه بندی این گونه الگوریتمها بر اساس تعداد راه حلهای اولیه است اما روش دیگر این طبقه بندی از طریق دامنهای است که آنها را تقلید میکنند.

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

هیچ الگوریتم ریاضیاتی شناخته شده‌ای برای یافتن راه حل بهینه برای همه این مسائل در یک زمان محاسباتی محدود وجود ندارد. بنابراین، برای حل چنین مسائلی الگوریتم‌های جستجو و بهینه‌سازی معمولاً با استفاده از اکتشافی‌های (Heuristics) خاصی توسعه می‌یابند که اگر چه فاقد پایه‌های ریاضی قوی هستند، اما در رسیدن به یک راه‌حل تقریبی در مدت زمان معقول خوب هستند. این روش‌ها که فراابتکاری (Meta-heuristic) نامیده می‌شوند، یافتن راه‌حل بهینه دقیق را تضمین نمی‌کنند، اما می‌توانند به یک راه‌حل تقریباً بهینه به روشی محاسباتی کارآمد منجر شوند.

با توجه به این جذابیت عملی همراه با سهولت پیاده سازی، متدولوژی های فراابتکاری در چندین حوزه کاربردی محبوبیت پیدا می‌کنند. بیشتر روش های فراابتکاری ماهیت تصادفی دارند و از یک اصل طبیعی، فیزیکی یا بیولوژیکی شبیه به جستجو یا فرآیند بهینه‌سازی تقلید می‌کنند.

در این مقاله، تعدادی از این روش‌ها، به ویژه الگوریتم های تکاملی (evolutionary algorithms)، مانند الگوریتم ژنتیکالگوریتم ژنتیک از 0 تا 100، آموزش الگوریتم ژنتیک در متلباین صفحه الگوریتم ژنتیک (Genetic Algorithm) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم ژنتیک در متلب (MATLAB) پرداخته است. (Genetic Algorithm) و استراتژی تکامل (Evolution Strategy)، بهینه سازی ازدحام ذرات (Particle Swarm Optimization)، بهینه سازی کلنی مورچه‌ها (Colony Optimization)، بهینه سازی کلنی زنبورها (Bee Colony Optimization)، بازپخت شبیه سازی شده (Simulated Annealing) و مجموعه‌ای از روش‌های دیگر را مورد بحث قرار می‌دهیم. بسیاری از الگوریتم های فراابتکاری توسط محققان در سراسر جهان به طور منظم پیشنهاد می‌شوند. بنابراین، یکی کردن آنها برای درک ویژگی‌های مشترک روش های فراابتکاری مختلف و به طور همزمان مطالعه تفاوت‌های اساسی بین آنها مهم است.

کلمه اکتشافی در زمینه محاسبه به عنوان روشی برای نشان دادن یک قاعده سرانگشتی برای حل یک مسئله، بدون کاربرد جامع یک رویه تعریف می‌شود. به عبارت دیگر، یک روش اکتشافی روشی است که:

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

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

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

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

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

مقایسه روش های فراابتکاری و کلاسیک

بیشتر روش‌های فراابتکاری با انگیزه‌های طبیعی، فیزیکی یا بیولوژیکی انجام می‌شوند و سعی می‌کنند از طریق عملگرهای مختلف از آنها در سطحی اساسی تقلید کنند. یک موضوع مشترک که در تمام فراابتکاری‌ها دیده می شود، تعادل بین اکتشاف (Exploration) و بهره برداری (Exploitation) است. کاوش به این موضوع اشاره دارد که اپراتورها چگونه راه حل‌ها را در فضای جستجو متنوع می‌کنند. این جنبه به فراابتکاری یک رفتار جستجوی جهانی می‌دهد. بهره برداری به این اشاره دارد که اپراتورها چگونه می‌توانند از اطلاعات موجود از راه حل‌های تکرارهای قبلی برای تشدید جستجو استفاده کنند. چنین تشدیدی به فراابتکاری یک ویژگی جستجوی محلی می‌دهد.

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

ویژگی‌هایی که در بالا توضیح داده شد به فراابتکاری مزایای خاصی نسبت به روش‌های بهینه سازی کلاسیک می دهد، یعنی:

فراابتکاری می‌تواند به راه‌حل‌های کافی برای مسائل محاسباتی آسان (از لحاظ فنی، کلاس P) با پیچیدگی ورودی بزرگ منجر شود، که می‌تواند مانعی برای روش‌های کلاسیک باشد.
فراابتکاری می تواند به راه حل های کافی برای مسائل NP-hard منجر شود، یعنی مسائلی که هیچ الگوریتم دقیق شناخته شده‌ای وجود ندارد که بتواند آنها را در مدت زمان معقولی حل کند.
بر خلاف بسیاری از روش‌های کلاسیک، فراابتکاری به اطلاعات گرادیان نیاز ندارد و بنابراین می‌تواند با توابع هدف غیرتحلیلی، جعبه سیاه یا مبتنی بر شبیه‌سازی استفاده شود.
بیشتر الگوریتم های فراابتکاری به دلیل تصادفی بودن ذاتی یا اکتشافی‌های قطعی که به طور خاص برای این منظور در نظر گرفته شده اند، توانایی بازیابی از بهینه محلی را دارند.
به دلیل توانایی بازیابی از بهینه محلی، فراابتکاری بهتر می تواند عدم قطعیت در اهداف را کنترل کند.
اغلب فراابتکاری ها می توانند اهداف متعدد را تنها با چند تغییر الگوریتمی مدیریت کنند.

طبقه بندی الگوریتم های فراابتکاری

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

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

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

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

دیگر روش‌های رایج طبقه بندی الگوریتم های فراابتکاری عبارتند از :

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

بیشتر فراابتکاری ها مبتنی بر جمعیت، تصادفی، غیر حریصانه هستند و از یک تابع هدف ایستا استفاده می‌کنند.

یک چارچوب عمومی برای الگوریتم های فراابتکاری

اکثر الگوریتم های فراابتکاری دنباله‌ای مشابه از عملیات را دنبال می کنند و بنابراین می توانند در یک چارچوب عمومی مشترک تعریف شوند که در زیر نشان داده شده است:

شمارنده تکرار t را برابر با 0 مقدار دهی کنید.
N مجموعه راه حل به نام S_t را به صورت تصادفی مقداردهی اولیه کنید.
هریک از اعضای S_t را ارزیابی کنید.
بهترین راه حل S_t را به نام $x^*_t$ علامت گذاری کنید.
مراحل 6 تا 12 را تا زمانی که یک طرح خاتمه (termination plan) برآورده شده است، ادامه دهید.
به تعداد $\mu $ راه حل از S_t با استفاده از یک طرح انتخاب (selection plan)انتخاب کنید و نام آن را P_t بگذارید.
به تعداد $\lambda $ راه حل جدید از P_t با استفاده از یک طرح تولید (generation plan) بسازید و نام آن را C_t بگذارید.
به تعداد $\rho $ راه حل از S_t با استفاده از یک طرح جابه‌جایی (replacement plan) انتخاب کنید و نام آن را R_t بگذارید.
S_t را با جایگزینی R_t با استفاده از $\rho $ راه حل از هر ترکیبی از حداکثر سه مجموعه ، C_t P_t و R_t با استفاده از یک طرح به‌روزرسانی (update plan) به‌روزرسانی کنید.
هریک از اعضای S_t را ارزیابی کنید.
بهترین راه حل S_t را شناسایی کنید و $x^*_t$ را به روز کنید.
به t یکی اضافه کنید
راه حل نزدیک به بهینه را به عنوان $x^*_t$ اعلام کنید.

رویه بالا نشان می دهد که برای تعیین یک الگوریتم فراابتکاری، حداقل پنج طرح (SP، GP، RP، UP،TP) و چهار پارامتر (N، μ، λ، ρ) مورد نیاز است. طرح های فردی ممکن است شامل یک یا چند پارامتر از خود باشند.

مرحله 1 شمارنده تکرار (t) را به صفر مقداردهی می کند. از حلقه تکرار الگوریتم واضح است که یک الگوریتم فراابتکاری طبیعتاً یک رویه تکراری است.

مرحله 2 یک مجموعه اولیه از N راه حل را در مجموعه S_t ایجاد می کند. اغلب، راه حل ها به طور تصادفی در بین کران های پایین و بالای متغیرها ایجاد می شوند. برای مسائل بهینه سازی ترکیبی، جایگشت‌های تصادفی موجودیت‌ها را می‌توان ایجاد کرد. هنگامی که دانش ویژه مسئله از راه حل‌های اولیه خوب در دسترس است، ممکن است آنها همراه با چند راه حل تصادفی برای امکان کاوش گنجانده شوند.

مرحله 3 هر یک از N عضو مجموعه را با استفاده از توابع هدف و محدودیت ارائه شده ارزیابی می کند. نقض محدودیت، در صورت وجود، باید در اینجا در نظر گرفته شود تا یک طرح ارزیابی ارائه شود که در مراحل بعدی الگوریتم استفاده خواهد شد. یکی از راه‌های تعریف نقض محدودیت CV(x|p) به شرح زیر است:

که $\preccurlyeq \alpha \succ$ برابر است با |α| اگر α <0 باشد و در غیر این صورت برابر با صفر خواهد بود. قبل از افزودن مقادیر محدودیت محدودیت های مختلف، باید آنها را نرمال سازی کرد. مقدار تابع هدف f(x) و مقدار نقض محدودیتCV(x|p) هر دو می‌توانند برای ارزیابی واقعی راه حل‌ها به مراحل بعدی ارسال شوند.

مرحله 4 بهترین عضو مجموعه S_t را انتخاب می‌کند و آن را به عنوان $x^*_t$ ذخیره می‌کند. این مرحله نیاز به مقایسه زوجی اعضای مجموعه دارد. یکی از راه‌های مقایسه دو راه‌حل ( AوB ) برای مسائل بهینه‌سازی محدود، استفاده از استراتژی بدون پارامتر زیر برای انتخاب برنده است:

اگر A و B امکان پذیر هستند، موردی را انتخاب کنید که مقدار هدف (f) کمتری دارد.
اگر A امکان پذیر است و B نیست،A را انتخاب کنید و بالعکس.
اگر A و B غیر ممکن هستند، یکی را انتخاب کنید که مقدار CV کمتری دارد.

مرحله 5 الگوریتم را در یک حلقه قرار می دهد تا زمانی که طرح خاتمه (TP) برآورده شود. حلقه شامل مراحل 6 تا 12 است. TP ممکن است شامل دستیابی به یک مقدار هدف از پیش تعیین شده (ft) باشد و زمانی که ${f(x^*_t)≤f}_T$ باشد برآورده می شود. TP ممکن است به سادگی شامل یک تعداد از پیش مشخص شده از تکرار T باشد، در نتیجه شرط پایان $t≤T$ را تنظیم می‌کند. TP های دیگر نیز ممکن است و این یکی از پنج طرحی است که باید توسط کاربر انتخاب شود.

مرحله 6 با استفاده از طرح انتخاب (SP) راه حل‌های μ را از مجموعه S_t انتخاب می کند. SP باید S_t را به دقت تجزیه و تحلیل کند و راه‌حل‌های بهتر (با استفاده از f و CV) را انتخاب کند. روش فراابتکاری تا حد زیادی بر اساس SP مورد استفاده متفاوت خواهد بود. راه حل های μ یک مجموعه جدید P_t را تشکیل می‌دهند.

در مرحله 7، راه حل های P_t برای ایجاد مجموعه ای از λ راه حل جدید با استفاده از یک طرح تولید (GP) استفاده می‌شود. این طرح، عملیات جستجوی اصلی الگوریتم فراابتکاری را ارائه می دهد. طرح‌ها برای مسائل بهینه سازی تابع و بهینه سازی ترکیبی متفاوت خواهند بود. راه حل‌های ایجاد شده در مجموعه C_t ذخیره می‌شوند.

مرحله 8 راه حل‌های بدتر یا تصادفی S_t را انتخاب می‌کند تا با طرح جایگزینی (RP) جایگزین شوند. راه حل‌هایی که باید جایگزین شوند در R_t ذخیره می‌شوند. در برخی از الگوریتم های فراابتکاری، R_t می‌تواند به سادگی P_t باشد (نیاز به ρ = μ دارد)، در نتیجه جایگزین راه‌حل‌های مورد استفاده برای ایجاد راه‌حل‌های جدید می‌شود. برای اینکه الگوریتم حریص تر شود، R_t می‌تواند بدترین μ عضو از S_t باشد.

در مرحله 9، ρ راه حل انتخاب شده از S_t باید با ρ راه حل دیگر جایگزین شوند. در اینجا، مجموعه ای از حداکثر (μ+λ+ρ) راه حل‌های ترکیبی C_t ∪ R_t∪ P_t برای انتخاب ρ راه حل با استفاده از طرح به روز رسانی (UP) استفاده می شود. اگر R_t = P_t باشد، پس ترکیب راه حل‌ها نیازی به داشتن هر دو R_tو P_t ندارد تا از تکرار راه حل‌ها جلوگیری شود. UP به سادگی می تواند بهترین ρ راه حل را از میان آنها انتخاب کند. توجه داشته باشید که مجموعه‌ای از ترکیب راه حل‌ها از C_t ∪ R_t یا C_t ∪ P_t یا به صرفا خود C_t نیز مجاز است. اگر اعضای R_t در مجموعه ترکیبی از راه حل‌ها گنجانده شوند، آنگاه الگوریتم فراابتکاری دارای خاصیت حفظ نخبگان (Elite-preserving) است که در یک الگوریتم بهینه سازی کارآمد مورد نظر است.

RP و UP نقش مهمی در تعیین توانایی تحمل یا غلبه الگوریتم فراابتکاری بر شرایط نامطلوب یا آزمایش های سخت (Robustness) دارند. رویکرد حریصانه جایگزینی بدترین راه حل ها با بهترین راه حل ها ممکن است منجر به همگرایی سریعتر و در عین حال زودرس شود. حفظ تنوع در راه حل‌های کاندیدا یک جنبه ضروری است که باید در هنگام طراحی RP و UP در نظر گرفته شود.

مرحله 10 هر یک از اعضای جدید S_t را ارزیابی می‌کند و مرحله 11 بهترین عضو $x^*_t$ را با استفاده از بهترین اعضای S_t به روز شده، به روز می‌کند. هنگامی که الگوریتم TP را برآورده کرد، بهترین راه حل فعلی به عنوان راه حل تقریباً بهینه اعلام می شود.

الگوریتم فراابتکاری بالا همچنین می‌تواند یک روش بهینه‌سازی راه‌حل منفرد (Single Solution Optimization Procedure) را با تنظیم N = 1 نشان دهد. این کار باعث می‌شود μ = ρ = 1 شود. اگر یک راه‌حل جدید واحد در مرحله 7 ایجاد شود، λ = 1 می‌شود. در این مورد، SP و RP رویه‌های ساده‌ای برای انتخاب راه‌حل تک‌تنه (Singleton Solution) در S_t هستند. بنابراین، S_t = R_t = P_t. طرح تولید (GP) می‌تواند راه‌حلی را در همسایگی راه حل تک‌تنه در S_tبا استفاده از یک توزیع گاوسی یا دیگر توزیع‌ها انتخاب کند. طرح به روز رسانی (UP) شامل انتخاب یک راه حل واحد از دو راه حل C_t ∪ R_t (حفظ نخبگان) یا انتخاب راه حل جدید از C_tبه تنهایی و جایگزینی P_t است.

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

جستجوی ممنوعه (Tabu Search)

الگوریتم جستجوی ممنوعه پیشنهاد شده توسط گلوور (Glover) یک الگوریتم فراابتکاری تک راه حل محبوب است. این الگوریتم یک نسخه پیچیده از الگوریتم بازپخت شبیه‌سازی شده (Simulated Annealing) است، که در آن حافظه‌ای از راه‌حل‌های گذشته نگهداری می‌شود و برای جلوگیری از بازبینی آن راه‌حل‌ها توسط الگوریتم (چرخه) زمانی که یک حرکت غیر بهبودی (Non-improving) برای فرار از بهینه محلی تولید می‌شود، استفاده می‌شود.

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

یک الگوریتم جستجوی ممنوعه با یک راه حل منفرد مانند بازپخت شبیه سازی شده شروع می شود و N راه حل جدید از همسایگی آن نمونه برداری می‌شود. راه حل‌هایی که نیاز به حرکت ممنوع دارند با نمونه‌های دیگری جایگزین می‌شوند. بهترین راه حل در همسایگی راه حل فعلی انتخاب می‌شود و اگر برازندگی آن بهتر از راه حل فعلی باشد، اولی جایگزین دومی می‌شود، درست مانند هر الگوریتم جستجوی محلی. با این حال، اگر هیچ یک از راه حل‌های موجود در همسایگی بهتر از راه حل فعلی نباشد، یک حرکت غیر بهبودی انجام می‌شود.

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

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

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

لیست الگوریتم های فرا ابتکاری یا متاهیوریستیک

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

بهینه سازی کلونی مورچه ها (ACO)
بهینه سازی کلونی زنبورهای مصنوعی (ABCO)
سیستم ایمنی مصنوعی (AIS)
تکامل دیفرانسیل (DE)
استراتژی های تکامل (ES)
برنامه نویسی تکاملی (EP)
برنامه ریزی ژنتیکی (GP)
بهینه سازی ازدحام ذرات (PSO)
جستجوی پراکنده (SS)
بازپخت شبیه سازی شده (SA)
جستجوی هارمونی (Harmony Search)
برآورد الگوریتم های توزیع (Estimation of Distribution Algorithms)
تغذیه باکتریایی (Bacterial Foraging)
الگوریتم های ممتیک (Memetic Algorithms)
برنامه نویسی بیان ژن (Gene Expression Programming)
الگوریتم های تکاملی (Coevolutionary Algorithms)
الگوریتم کرم شب تاب (Firefly Algorithm)
الگوریتم جستجوی گرانشی (Gravitational Search Algorithm)
جستجوی فاخته (Cuckoo Search)
بهینه سازی مبتنی بر جغرافیای زیستی (Biogeography-based optimization)
الگوریتم جهش قورباغه به هم ریخته (Shuffled Frog Leaping Algorithm)
الگوریتم زنبورها (Bees Algorithm)
الگوریتم های فرهنگی (Cultural Algorithms)
الگوریتم رقابتی امپریالیستی (Imperialist competitive algorithm)
الگوریتم خفاش (Bat Algorithm)
تکامل دستوری (Grammatical Evolution)
بهینه سازی تهاجمی علف های هرز (Invasive Weed Optimization)
جستجوی سیستم شارژ شده (Charged System Search)

الگوریتم های فراابتکاری چند هدفه

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

بردار $x^*={\left[x^*_1,\ x^*_2,\ ...,\ x^*_n\right]}^T$ که:

m قید نابرابری زیر را برآورده می‌کند

$g_i(x)≤0$ برای $i=1,2,...,m$

p قید برابری زیر را برآورده می‌کند

$h_i(x)≤0$ برای $i=1,2,...,p$

و تابع برداری را بهینه می‌کند

\[f(x)={\left[f_1(x),f_2(x),...,f_k(x)\ \right]}^T\]

با داشتن چندین تابع هدف، مفهوم بهینه تغییر می‌کند، زیرا در مسائل بهینه سازی چند هدفه، ما واقعاً در تلاش هستیم تا به جای یک راه حل واحد مانند بهینه سازی جهانی، توافق‌های خوبی پیدا کنیم. مفهوم بهینه که بیشتر مورد استفاده قرار می‌گیرد همان است که در ابتدا توسط فرانسیس یسیدرو اجورث (Francis Ysidro Edgeworth) در سال 1881 ارائه شد. این تصور بعدها توسط ویلفردو پارتو(Vilfredo Pareto) در سال 1896 تعمیم یافت.

جمع بندی

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

الگوریتم فراابتکاری چیست؟

مسائل زیادی در دنیای واقعی برای جستجو و بهینه سازی وجود دارد که شامل پیچیدگی‌های زیادی است که الگوریتم های کلاسیک را ناکارآمد می‌کند، بنابراین برای حل چنین مسائلی الگوریتم‌های جستجو و بهینه سازی، از الگوریتم های فراابتکاری استفاده می‌کنند، که این صفحه به صورت کامل به بررسی اینگونه الگوریتم‌ها پرداخته است.

طبقه بندی الگوریتم های فراابتکاری چگونه است؟

رایج ترین روش طبقه بندی این گونه الگوریتم‌ها بر اساس تعداد راه حل‌های اولیه است اما روش دیگر این طبقه بندی از طریق دامنه‌ای است که آن‌‌ها را تقلید می‌کنند.

28905 نفر تاکنون در دوره‌های آموزشی کنکور کامپیوتر شرکت کرده‌اند.