معرفی الگوریتم‌های بهینه‌سازی فراابتکاری

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

pic1

امروزه بسياري از مسائل بهينه‌سازي جزء مسائل غير چندجمله‌اي-سخت( NP-Hard Problem) می‌باشد که برای آن‌ها راه‌حل دقیق، سریع و قابل انجام در زمان معقول وجود ندارد و به احتمال زیاد در آینده نیز پیدا نخواهد شد. ازجمله راه‌حل‌هاي موجود در برخورد با اين‌گونه مسائل، استفاده از الگوريتم‌هاي بهینه‌سازی تقريبي(approximate algorithms) است.

در کل الگوریتم‌های بهینه‌سازی به دو دسته‌ی الگوریتم‌های دقیق(exact) و الگوریتم‌های تقریبی تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی NP-hard problem کارایی ندارند و زمان حل آن‌ها در این مسائل به صورت نمایی افزایش می‌یابد. این در حالی است که الگوریتم‌های تقریبی قادر به یافتن جواب‌های نزدیک به بهینه در زمان قابل‌قبول برای مسائل بهینه‌سازی NP- hard problem هستند. یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی، الگوریتم‌های فراابتکاری می‌باشد که برای طیف وسیعی از مسائل قابل کاربرد دارد و به راحتی از کمینه‌های محلی عبور می‌کند.

الگوریتم‌های فراابتکاری به دو دسته‌ی کلی مبتنی بر یک جواب و مبتنی بر جمعیت تقسیم می‌شوند. الگوریتم‌های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را بهبود می‌دهند تا به جواب بهینه دست یابند. ازجمله الگوریتم‌های بهینه‌سازی مبتنی بر یک جواب، می‌توان به الگوریتم تبریدی(simulated annealing) و جستجو ممنوع(tabu search) اشاره کرد. در حالی که در الگوریتم‌های مبتنی بر جمعیت مجموعه‌ی از جواب‌ها(جمعیت) در حین فرایند جستجو بهبود داده می‌شوند. الگوریتم ژنتیک، تراکم ذرات، کلونی مورچه و … نیز جزء الگوریتم‌های فراابتکاری مبتنی بر جمعیت می‌باشند.

روند کلی الگوریتم‌های بهینه‌سازی فراابتکاری مبتنی بر یک جواب را می‌توان در فلوچارت شکل 1 خلاصه کرد. فلوچارت الگوریتم‌های فراابتکاری مبتنی بر جمعیت نیز مثل شکل 1 می‌باشد با این تفاوت که بجای یک جواب، مجموعه جواب‌ها ایجاد می‌شود.

روند کلی الگوریتم‌های بهینه‌سازی بدین صورت می‌باشد که ابتدا پارامترهای مربوط به الگوریتم تنظیم می‌شود. سپس یک جواب به‌طور تصادفی(x0) ایجاد و ارزیابی(f0) می‌شود(شکل 2-الف). بعد از ایجاد و ارزیابی جواب، به تعداد مشخصی روند ایجاد جواب جدید، ارزیابی آن، بروزرسانی جواب و پارامترهای الگوریتم تکرار می‌شود(شکل 2-ب). بعد از این کار، اگر شرط همگرایی ارضاء نشده باشد؛ حلقه‌ی ایجاد و ارزیابی جواب جدید تکرار می‌شود در غیر این صورت برنامه پایان می‌یابد. تفاوت الگوریتم‌های مختلف در دو بند ایجاد جواب جدید و بروزرسانی جواب اصلی(کادر سبز رنگ) می‌باشد. در زیر هر بند از فلوچارت الگوریتم توضیح داده می‌شود.

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

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

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

بروز رسانی جواب اصلی: بعد از تعیین مقدار تابع هدف جواب‌های جدید، براساس متدی که خود الگوریتم بهینه‌سازی معرفی می‌کند، جواب‌های اصلی بروزرسانی می‌شود. برای مثال در الگوریتم ژنتیک، بعد از ایجاد جواب‌های جدید(از طریق ترکیب و جهش)، همه‌ی جواب‌ها (قبلی و ایجاد شده) براساس شایسته‌سالاری(بهتر بودن) مرتب شده و n جواب بهتر انتخاب و جایگزین n جواب قبلی می‌شود.

بروزرسانی پارامترهای الگوریتم: در برخی الگوریتم‌ها لازم است یک سری از پارامترهای الگوریتم بعد از تکرار مشخصی، دوباره تنظیم شوند. برای مثال در الگوریتم تبریدی لازم است دمایی فرایند هر بار کاهش یابد.

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

  • تکرار به تعداد مشخص
  • اگر جواب بهینه در دو یا چند حلقه تغییری نکرده باشد
  • بعد از گذشت زمان مشخص

دیدگاه‌تان را بنویسید: