۹ بازدید

آخرین به‌روزرسانی: ۳۰ خرداد ۱۴۰۳

زمان مطالعه: ۱۵ دقیقه

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

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

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

الگوریتم های تکاملی جزو الگوریتم‌های بهینه‌سازی محسوب می‌شوند که برای طراحی آن‌ها از فرایند «تکامل طبیعی» (Natural Evolution) الهام گرفته شده است. این الگوریتم‌ها برای یافتن راه‌حل‌های تقریبی برای مسائل بهینه‌سازی مانند پیدا کردن کمترین یا بیشترین مقدار یک تابع به کار می‌روند.

در یک الگوریتم تکاملی، ابتدا به صورت تصادفی مجموعه‌ای از راه‌حل‌های بالقوه (که به آن‌ها «افراد» (Individuals) یا «کروموزوم‌ها» (Chromosomes) گفته می‌شود) ایجاد می‌شود. سپس این راه‌حل‌ها با استفاده از مجموعه‌ قوانینی اصلاح و ارزیابی می‌شوند که فرآیند انتخاب طبیعی را شبیه‌سازی می‌کنند. به عنوان مثال، احتمال بقاء و تولیدمثل برای افراد با عملکرد بهتر (بر اساس یک تابع ارزیابی) بیشتر است، در حالی که احتمال حذف شدن افراد با عملکرد ضعیف بالاتر خواهد بود. این فرآیند انتخاب و تولیدمثل می‌تواند در طول زمان منجر به تکامل افراد با تناسب بیشتر شود که برای حل مسئله بهینه‌سازی مورد نظر کارایی بالاتری دارند.

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

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

1. مرحله تعریف مسئله: اولین قدم در شبیه‌سازی یک الگوریتم بازگشتی، تعریف مسئله بهینه‌سازی است که می‌خواهید آن را حل کنید. این مرحله شامل مشخص کردن متغیرهایی است که فضای راه‌حل را تشکیل می‌دهند. به علاوه، باید یک تابع ارزیابی را برای سنجش کیفیت راه‌حل‌ها تعریف کنید.
2. مرحله تعیین «جمعیت» (Population): گام بعدی، تعریف جمعیت برای راه‌حل‌های بالقوه است. این کار به طور معمول شامل ایجاد مجموعه‌ای از راه‌حل‌های تصادفی است که به عنوان نقطه شروع برای فرآیند بازگشتی در نظر گرفته می‌شوند. برای مثالی که از کوهنوردی ارائه کردیم، مسیرهای مختلفی را می‌توانیم برای صعود به کوه با سطوح دشواری متفاوت تعریف کنیم.
3. ارزیابی جمعیت: پس از تعیین جمعیت، کیفیت هر راه‌حل باید با استفاده از تابع ارزیابی مورد سنجش قرار گیرد. این کار به طور معمول شامل محاسبه یک امتیاز «تناسب» (Fitness) برای هر راه‌حل است که توانایی راه‌حل را برای حل مسئله نشان می‌دهد. در مثالی که از کوهنوردی ارائه کردیم، هر کوهنورد تلاش می‌کند تا از کوه بالا برود (راه‌حل را ارزیابی می‌کند). ما عملکرد افراد کوهنورد را بر اساس ارتفاعی که به آن صعود می‌کنند، با استفاده از تابع تناسب اندازه‌گیری می‌کنیم. کوهنوردانی که به نقاط مرتفع‌تر می‌رسند، امتیاز تناسب بهتری دارند.
4. به کارگیری عملگرهای بازگشتی: مجموعه‌ای از عملگرهای بازگشتی را بر روی جمعیت اعمال می‌کنیم تا نسخه جدیدی از راه‌حل‌ها را به دست آوریم. این عملگرها برای شبیه‌سازی فرآیند انتخاب طبیعی طراحی شده‌اند و برای ایجاد راه‌حل‌های جدیدی استفاده می‌شوند که از نظر تناسب (با توجه به تابع ارزیابی) نسبت به راه‌حل‌های پیشین خود، برتری دارند. در مثالی که از کوهنوردی ارائه کردیم، تغییرات کوچکی (جهش‌ها) را در مسیرهای صعود کوهنوردان ایجاد می‌کنیم. این تغییرات به کاوش مسیرهای مختلف و اجتناب از گیر افتادن در بهینه‌های محلی (بن‌بست) کمک می‌کند.
5. تکرار فرآیند: فرآیند ارزیابی جمعیت و اعمال عملگرهای بازگشتی تا زمانی تکرار می‌شوند که الگوریتم به راه‌حل رضایت‌بخشی برسد یا یک شرط توقفی به وقوع بپیوندد که از پیش تعیین‌ شده است. در مثال کوهنوردی، مراحل ۳ و ۴ را برای چندین نسخه جدید از راه‌حل‌ها تکرار می‌کنیم. با هر نسخه جدید، جمعیت تکامل می‌یابد و کوهنوردانی غالب می‌شوند که با تابع ارزیابی تناسب دارند و فرزندانشان صفات موفق آن‌ها را به ارث می‌برند.

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

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

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

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

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

انواع الگوریتم های تکاملی

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

1. «الگوریتم ژنتیک» (Genetic Algorithm)
2. الگوریتم «تکاملی تفاضلی» (Differential Evolution)
3. الگوریتم «استراتژی تکاملی» (Evolution Strategy)
4. الگوریتم «بهینه‌سازی ازدحام ذرات» (Particle Swarm Optimization)

در ادامه به توضیح نحوه عملکرد هر یک از الگوریتم های تکاملی ذکر شده در فهرست بالا می‌پردازیم و ویژگی‌های آن‌ها را شرح می‌دهیم.

الگوریتم ژنتیک چیست؟

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

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

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

الگوریتم‌های ژنتیک علی‌رغم مزایای زیادی که دارند، دارای معایبی نیز هستند که در ادامه به آن‌ها اشاره کرده‌ایم:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

علی‌رغم مزیت‌های مهمی که الگوریتم استراتژی تکاملی دارد، معایبی نیز می‌توان برای آن برشمرد که در ادامه به آن‌ها اشاره شده است:

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

الگوریتم بهینه‌ سازی ازدحام ذرات

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

• دانش فردی: هر پرنده (ذره) بهترین راه‌حلی را دنبال می‌کند که تا به حال پیدا کرده است. به بیان دیگر، پرنده‌ خوشمزه‌ترین تکه دانه‌ای را به یاد می‌آورد که قبلا آن را خورده است. این دانش، دانش «بهترین فردی» (pbest) نامیده می‌شود.
• دانش جهانی: کل پرندگان (ازدحام) نیز بهترین راه‌حلی را دنبال می‌کنند که توسط هر ذره‌ای پیدا شده است. به عبارتی، پرندگان اطلاعات مربوط به بهترین محوطه برای یافتن غذا را به اشتراک می‌گذارند. این دانش، دانش «بهترین جهانی» (gbest) نامیده می‌شود.

هر ذره بر اساس سرعت خود در فضای جستجو حرکت می‌کند. در تعیین این سرعت دو چیز در نظر گرفته می‌شود:

• تجربه فردی: نشان می‌دهد ذره چقدر به pbest خود نزدیک است (پرنده چقدر به یاد دانه‌های خوشمزه قبلی است).
• هوش ازدحام: ذره چقدر به gbest نزدیک است (دنبال کردن دسته پرندگان برای یافتن غذا).

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

الگوریتم بهینه‌سازی ازدحام ذرات (PSO) به عنوان تکنیکی محبوب برای حل مسائل بهینه‌سازی محسوب می‌شود و دارای نقاط قوت مختلفی است که در ادامه به برخی از آن‌ها پرداخته شده است:

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

الگوریتم بهینه‌‌سازی ازدحام ذرات همانند سایر الگوریتم‌ها دارای معایبی نیز هست که در ادامه خلاصه‌ای از آن‌ها را ملاحظه می‌کنید:

• گیر کردن در نقاط «بهینه محلی» (Local Optima): الگوریتم تکاملی بهینه‌‌سازی ازدحام ذرات ممکن است در نقاط بهینه محلی متوقف شود. این بدان معنا است که این الگوریتم یک راه‌حل خوب برای مسئله پیدا می‌کند اما لزوماً نمی‌توان گفت این راه‌حل بهترین پاسخ مسئله است. رخداد این اتفاق به این دلیل است که ذرات عمدتاً به تجربیات خود و دانش ازدحام تکیه می‌کنند که همین امر ممکن است منجر به کاوش کل فضای جستجو نشود.
• محدود به مسائل پیوسته: از این الگوریتم تکاملی می‌توان به طور موثر برای حل مسائل پیوسته استفاده کرد اما برای بهره‌گیری از آن برای مسائل گسسته نیاز به اصلاحات دارد.
• حساس به تنظیمات پارامتر: اگرچه الگوریتم تکاملی PSO به تنظیمات کمتری نسبت به برخی الگوریتم‌ها نیاز دارد، هنوز هم می‌تواند به طور قابل توجهی تحت تأثیر مقادیر انتخاب شده برای پارامترهای داخلی آن قرار گیرد و برای یافتن تنظیمات بهینه باید آزمون و خطا انجام داد.

بهینه سازی روش های تکاملی

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

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

کاربردهای روش های تکاملی

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

• پردازش تصویر: از الگوریتم های تکاملی می‌توان برای بهینه‌سازی الگوریتم‌های پردازش تصویر مانند الگوریتم‌های مورد استفاده در تقویت تصویر، بازیابی و بخش‌بندی تصاویر استفاده کرد.
• سیستم‌های کنترل: الگوریتم های تکاملی را می‌توان برای طراحی و بهینه‌سازی سیستم‌های کنترل در طیف گسترده‌ای از کاربردها، از جمله رباتیک، هوافضا و سیستم‌های خودرو استفاده کرد.
• یادگیری ماشین: الگوریتم‌های فرگشتی برای بهینه‌سازی ابرپارامترهای مدل‌های یادگیری ماشین یا برای یافتن معماری‌های جدید در این حوزه به کار می‌روند.
• مدل‌سازی مالی: برای بهینه‌سازی مدل‌های مالی، مانند مدل‌های استفاده شده در بهینه‌سازی سبد سهام یا مدیریت ریسک این نوع الگوریتم‌ها کاربرد دارند.
• زیست‌شناسی محاسباتی: برای تجزیه و تحلیل و تفسیر داده‌های بیولوژیکی مانند توالی‌های DNA، ساختارهای پروتئینی و الگوهای بیان ژن می‌توان از الگوریتم های تکاملی استفاده کرد.
• بهینه‌سازی ترکیبی: برای حل مسائل بهینه‌سازی ترکیبی مانند «مسئله فروشنده دوره‌گرد» (Traveling Salesman Problem) یا «مسئله کوله‌پشتی» (Knapsack Problem) می‌توان از روش‌های تکاملی بهره گرفت.

یادگیری مفاهیم پیشرفته محاسبات تکاملی

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

جمع‌بندی

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