p.programstore
p.programstore
خواندن ۵ دقیقه·۵ سال پیش

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

با سلام خدمت دوستان عزیز

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

انتخاب تابع هدف یا تابع فیتنس Fitness مناسب يكي از مهمترين مراحل در الگوریتم های بهینه سازی هستش. گاهي در بهينه‌سازي چند هدف به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي میگن. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n بعدي x نشان داده مي‌شوند. هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.

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

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

روش‌هاي فرا ابتكاري برگرفته از طبيعت

الگوريتم ­هاي فراابتكاري الگوريتم ­هايي هستند كه با الهام از طبيعت، فيزيك و انسان طراحي شده ­اند و در حل بسياري از مسايل بهينه­ سازي استفاده می­ شوند. معمولاً از الگوريتم­ هاي فراابتكاري در تركيب با ساير الگوريتم­ ها، جهت رسيدن به جواب بهينه يا خروج از وضعيت جواب بهينه محلي استفاده مي­گردد. در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات، «روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد ‌آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.

در کل اگه فضای مسئله ما خیلی بزرگ باشه یعنی پیدا کردن یه مقدار خوب در یک فضای بزرگ مسئله ما باشه از الگوریتم های فرا ابتکاری برای بهینه سازی میشه استفاده کرد. یه مثال از این الگوریتم رو در زیر بیان می کنم. فرض کنید برای تامین برق یک شهر از 4 نیروگاه مختلف استفاده می کنند. این نیروگاه ها فرضاً دیزلی، بادی، آبی و خورشیدی هستند. مسئله رو بصورت زیر مدل می کنیم.

خوب در اینجا ما باید سعی کنیم از نیروگاه هامون بصورتی استفاده کنیم که میزان برق خروجی مطلوب باشه و کمترین هزینه رو برای ما داشته باشه. هر یک از متغیر های x,y,z,w اسم نیروگاه های ما هست و ضرایب a,b,c و d میزان استفاده هر یک از این نیروگاه ها در تولید برق هست یعنی ضریب تاثیر هستن. خوب در واقع پیدا کردن این ضرایب برای ما همون مشکل مسئله هست. یعنی چه مقدار از این ضرایب بایستی انتخاب شن تا بهره وری برق از لحاظ تامین و هزینه برای ما مفید باشه. مثلا ما نیروگاه دیزلی رو اگه در نظر بگیریم شاید با در نظر گرفتن ضریب بالایی مثلاً 0.8 برای اون بتونیم برق کل شهر رو تامین کنیم ولی در عوض هزینه ما بدلیل استفاده از سوخت فسیلی زیاد میشه. در عوض استفاده از نیروگاه های آبی بادی و خورشیدی هزینه کمتری داره ولی شاید نتونیم با اونا برق زیادی رو تولید بکنیم. پس هر کدوم از نیروگاه ها برای خودشون معایب و مزایایی دارن. از این رو شروع می کنیم به تعیین مقدار هر یک از ضرایب a,b,c,d

پیدا کردن یک ضریب مثلاً a در محدوده 0 و 1 که شامل بینهایت عدد هست یک کار دشوار هست مخصوصاً اینکه این ضریب باید طوری دقیق انتخاب بشه تا هم محدودیت های ما رو رعایت کنه و هم از لحاظ هزینه برای ما مقرون بصرفه باشه. به این طور مسائل که فضای جستجو یک فضای بزرگ هست و پیدا کردن یک مقدار مناسب سخته میگن مسائل NP-Hard. این گونه مسائل رو با الگوریتم های فرا ابتکاری که الهام گرفته شده از طبیعت هستند می تونیم حل کنیم. یعنی نگاهی به طبیعت و دنیای پیرامون خدمون می ندازیم و روشهایی که حیوانات، اشیا، نیرو ها و سایر عوامل در پیدا کردن جواب می کنن رو یاد می گیریم و ازشون در حل مسائل خودمون استفاده می کنیم.

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

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

  • الگوریتم ژنتیک
  • الگوریتم بهینه سازی ازدحام ذرات یا PSO
  • الگوریتم کرم شب­ تاب Firefly Algorithm
  • الگوریتم کلونی مورچگان
  • الگوریتم زنبور عسل
  • الگوریتم رقابت استعماری
  • الگوریتم تکاملی تفاضلی
  • الگوریتم بهینه سازی وال ها یا نهنگ WOA
  • الگوریتم گرگ خاکستری GWO
  • الگوریتم شعله پروانه MFO
  • و ...

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

در سایت ما به نشانی programstore.ir سورس کدها و فیلم های آموزشی زیادی وجود داره تا نحوه کارکرد اونا رو بهتر درک کنید. همچنین می توانید در در کانال تلگرامی ما عضو شوید. امیدوارم از این مطلب نتیجه خوبی بگیرید.

با تشکر - امین جلیل زاده

آموزش الگوریتم گرگ خاکستری

آموزش الگوریتم وال یا نهنگ

آموزش الگوریتم شعله و پروانه

انتخاب الگوریتم بهینه سازیهدف الگوریتم بهینه سازیبهینه سازیبهبود الگوریتم
فروشگاه فایل پی استور ارائه دهنده فایل های پروژه، پیاده سازی و داکیومنت
شاید از این پست‌ها خوشتان بیاید