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

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

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

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

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

بهینه سازی

مسائل مختلف بهينه‌سازي به دو دسته زير تقسيم مي‌شود:

1- مسائل بهينه‌سازي بي‌محدوديت

در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي مي‌باشد.

2- مسائل بهينه‌سازي با محدوديت

الگوریتم های بهینه سازی در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم مي‌باشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.

معادلات معرف محدوديت‌ها ممكن است به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت مي‌باشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.

فرآيند بهينه ­سازي

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

  • فرموله كردن مسئله

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

  • مدل­ سازي مسئله

در اين مرحله يك مدل رياضي كلي براي مسئله، ساخته مي­ شود. مدل­سازي ممكن است از مدل­ هاي مشابه در پيشينه ­ي موضوع كمك بگيرد. اين گام موجب تجزيه مسئله به يك يا چند مدل بهينه‌سازي مي­ گردد.

  • بهينه­ سازي مسئله

پس از مدل سازي مسئله، روال حل، يك راه ­حل خوب براي مسئله توليد مي­ كند. اين راه‌حل ممكن است بهينه يا تقريباً بهينه باشد. نكته ­اي كه بايد به آن توجه داشت اين است كه راه ­حل به دست آمده، راه­ حلي براي مدل طراحي شده است، نه براي مسئله ­ي واقعي. در هنگام فرموله كردن و مدلسازي ممكن است تغييراتي در مسئله واقعي به وجود آمده و مسئله­ ي جديد، نسبت به مسئله­ ي واقعي تفاوت زيادي داشته باشد.

  • استقرار مسئله

راه ­حل به دست آمده توسط تصميم گيرنده بررسي مي­ شود و در صورتي كه قابل قبول باشد، مورد استفاده قرار مي­ گيرد و در صورتي كه راه­حل قابل قبول نباشد، مدل يا الگوريتم بهينه­ سازي بايد توسعه داده شده و فرايند بهينه­ سازي تكرار گردد.

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

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

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

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

در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به صورت زير تشكيل شده‌اند:

  • استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري
  • استفاده از يك يا چند عامل (نرون، خرده‌ريز، كروموزوم، مورچه و غيره)
  • عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت
  • ايجاد روش‌هاي خود تغييري و خود تبديلي

طبيعت داراي دو تدبير بزرگ مي‌باشد:

  1. انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛
  2. جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.

به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده مي‌شود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته مي‌باشد. از خصوصيات روش‌هاي ابتكاري برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:

  1. پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.
  2. بدون قطع مي‌باشند.
  3. اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.
  4. تطبيق‌پذير هستند.

خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي مي‌شود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حل مناسب مسائل بهينه‌سازي تركيبي منجر می‌شود.

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

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

1- الگوریتم ژنتیک

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

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

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

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

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

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

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

3- الگوریتم کرم شب­ تاب Firefly Algorithm

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

3- الگوریتم کلونی مورچگان

الگوریتم کلونی مورچگان یا الگوریتم بهینه سازی کلونی مورچه Ant Colony Optimization الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و به ویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. توضیح کامل این الگوریتم را می توانید در همین سایت از مقاله ای کامل تحت عنوان الگوریتم کلونی مورچگان مطالعه فرمایید.

4- الگوریتم زنبور عسل

الگوریتم کلونی زنبور عسل مصنوعی (Artificial bee colony algorithm) یک الگوریتم بهینه سازی بر اساس هوش جمعی و رفتار هوشمندانه جمعیت زنبور عسل است. الگوریتم کلونی زنبور عسل مصنوعی یا به اختصار ABC، یک راهکار بهینه‌سازی است که رفتار یک کلونی زنبور عسل را شبیه‌سازی می‌کند و برای اولین بار در سال 2۰۰۵ توسط Dervis Karaboga، برای بهینه‌سازی ارائه شد. توضیح این الگوریتم را می توانید در همین سایت از مقاله ای کامل تحت عنوان الگوریتم کلونی زنبور عسل مطالعه فرمایید.

5- الگوریتم رقابت استعماری

الگوریتم رقابت استعماری (Imperialist Competitive Algorithm )  یا ICA روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینه‌سازی می‌پردازد. این الگوریتم با مدلسازی ریاضی فرآیند تکامل اجتماعی – سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه‌سازی ارائه می‌دهد. پایه‌های اصلی این الگوریتم را سیاست همسان سازی (Assimilation)، رقابت استعماری (Imperialistic Competition) و انقلاب (Revolution) تشکیل می‌دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخش‌هایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می‌دهد که می‌توانند به حل مسائل پیچیده بهینه‌سازی کمک کنند. توضیح این الگوریتم را می توانید در همین سایت از مقاله ای کامل تحت عنوان الگوریتم رقابت استعماری مطالعه فرمایید.

6- الگوریتم تکاملی تفاضلی

الگوریتم تکاملی تفاضلی یا الگوریتم DE یک الگوریتم تکاملی است که اولین بار در سال 1995 توسط Rainer Storn و Kenneth Price معرفی شد. این محققان در مقاله ای تحت عنوان Differential Evolution a Practical Approach to Global Optimization نشان دادند که این الگوریتم توانایی خوبی در بهینه سازی توابع غیرخطی مشتق ناپذیر دارد که به عنوان روشی قدرتمند و سریع برای مسائل بهینه سازی در فضاهای پیوسته معرفی شده است. الگوریتم DE جهت غلبه بر عیب اصلی الگوریتم ژنتیک، یعنی نبود جستجوی محلی دراین الگوریتم ارائه شده است، تفاوت اصلی بین الگوریتم های ژنتیک  و الگوریتم DE در عملگر انتخاب Selection Operators است. توضیح این الگوریتم را می توانید در همین سایت از مقاله ای کامل تحت عنوان الگوریتم تکاملی تفاضلی – Differential Eevolution Algorithm مطالعه فرمایید.

7- الگوریتم بهینه سازی وال ها یا نهنگ WOA

الگوریتم بهینه سازی وال ها یا نهنگ WOA یک الگوریتم بهینه سازی الهام گرفته شده از طبیعت و مبتنی بر جمعیت است که  از رفتار شکار نوع خاصی از وال ها یا نهنگ ها که به نهنگ های گوژپشت معروف هستند الهام گرفته شده است. این الگوریتم توسط سید علی میرجلیلی (Seyedali Mirjalili) در سال ۲۰۱۶ در مقاله The Whale Optimization Algorithm در ژورنال Advances in Engineering Software پایگاه علمی Elsevier ارائه شده است. توضیح کامل این الگوریتم را می توانید در همین سایت از مقاله ای کامل تحت عنوان الگوریتم بهینه سازی وال ها یا نهنگ WOA مطالعه فرمایید.

8- الگوریتم شعله پروانه MFO

الگوریتم شعله پروانه یا الگوریتم Moth-flame optimization algorithm که به اختصار الگوریتم MFO نیز نامیده می شود یکی از الگوریتم های بهینه سازی و فراابتکاری است که از رفتار پروانه ها در کنار شعله یا آتش روشی برای حل مسئله پیدا می کند. این الگوریتم در سال 2015 توسط سید علی میر جلیلی در مقاله ای تحت عنوان:

Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm

در ژورنال Knowledge-Based Systems مطرح شد. الگوریتم شعله پروانه با نام های دیگری همچون الگوریتم پروانه آتش، الگوریتم MFO، الگوریتم پروانه شعله نیز شناخته می شود. این الگوریتم یک الگوی اکتشافی نوین الهام گرفته از طبیعت و رفتار پروانه ها و علاقه مندی آن ها به شعله یا آتش است. توضیح کامل این الگوریتم را می توانید در همین سایت از مقاله ای کامل تحت عنوان الگوریتم شعله پروانه MFO مطالعه فرمایید.

مطالب زیر را حتما بخوانید

دیدگاه ها

  1. programstore گفت:

    دیدگاه های خود را برای بهتر قرار دادن مطالب با ما در میان بگئارید.

پاسخی بگذارید

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

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