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

ابوالفضل محمدی جو

ابوالفضل محمدی جو

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

در ریاضیات و حسابان، برا یافتن مقادیر اکسترمم تابع (مینیمم یا ماکزیمم)، ما مشتق تابع رو برابر صفر قرار می دهیم و سپس معادله حاصل را حل نموده و نقاط جواب را بدست می آوریم. این نقاط، “نقاط بحرانی” تابع نامیده می شوند و مقدار تابع در این نقاط اکسترمم است.

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

به وضوح می توان یافتن که جواب معادله  $f'(x,y) = 0$ برای تابع بالا، تقریبا غیر ممکن است. بنابراین، ما چگونه باید نقاط اکسترمم این تابع را پیدا کنیم؟؟!!

یک راه حل ابتدایی و ساده انگارانه که به ذهن می آید اینست که ما مقادیر تابع را برای یک بازه وسیعی از متغیرهای X و Y بدست آوریم و سپس مقادیر مینیمم یا ماکزیمم را انتخاب کنیم. برای مثال اگر تنها بخواهیم مقادیر اکسترمم تابع فوق را در بازه  {x\in (-100,+100)} و  {y\in (-100,+100)} بدست آوریم، نیاز داریم که متغیرهای X و Y را در بازه مذکور با گام ۰.۰۱ تقسیم بندی کنیم. در این حالت ما ۲۰۰۰ مقدار برای متغیر X و ۲۰۰۰ مقدار برای متغیر Y و در مجموع ۴.۰۰۰.۰۰۰ جفت (X,Y) خواهیم داشت که مقدار تابع باید برای این جفت ها محاسبه گردد.

در نظر داشته باشید که هر ارزیابی تابع فوق برای هر جفت (X,Y) نیازمند محاسبات ریاضی قابل توجهی است و این محاسبات باید ۴.۰۰۰.۰۰۰ مرتبه تکرار گردد و در نهایت ما نیازمند یک الگوریتم مرتب سازی هستیم تا مقادیر مینمم و ماکزیمم تابع را بیابیم. برگردیم به فرض اولیه خود، که این ارزیابی ها تنها برای بازه (۱۰۰+,۱۰۰-) است و اکسترمم تابع می تواند خارج از این بازه رخ دهد. بنابراین این راه حل برای مسئله ما، مناسب به نظر نمی رسد.

برای حل اینگونه از مسائل، الگوریتم های بهینه سازی فرا ابتکاری ظهور پیدا کردند که مشهورترین آن ها را می توان “الگوریتم ژنتیک” دانست. الگوریتم های بهینه سازی فراابتکاری بسیاری وجود دارد که هر کدام الهام گرفته از طبیعت و محیط پیرامون ماست، مانند: “الگوریتم بهینه سازی ازدحام ذرات”، “بهینه سازی جمعیت مورچگان”، “الگوریتم جستجوی ممنوعه”، “الگوریتم رقابت استعماری”، “الگوریتم علف هرز مهاجم” و غیره.

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

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

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

این مقاله را در شبکه های اجتماعی خود به اشتراک بگذارید.

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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

اشتراک در خبرنامه