روش‌هاي بهینه‌سازی شبیه‌سازی

به‌طور کلی بهینه‌سازی شبیه‌سازی فرآیند تعیین مقادیر بهینه متغیرهای ورودی سیستم به‌منظور حداکثرکردن متغیرهای عملکردی است. مدل‌های بهینه‌سازی شبیه‌سازی دارای تابع هدف (یعنی، بهینه‌نمودن جواب‌ مدل شبیه‌سازی) و مجموعه‌ای از محدودیت‌ها می‌باشند]2[.

روش‌هاي بهینه‌سازی شبیه‌سازی به گروه‌هاي مختلفي تقسيم مي‌شود كه توسط محققين مختلف پیمایش‌های ارزشمندی در این زمینه انجام شده است. در ادبيات تحقيق، شش گروه اصلي از روش‌ها قابل شناسایي هستند. اين گروه‌هاي اصلي از ايده‌هاي زيربنایي متفاوتي استفاده مي‌كنند.]6[

الف) رتبه‌بندي و انتخاب

در اين شيوه فرض می‌شود كه تعداد راهكارها (جواب‌هاي موجه مسئله) ثابت است و نيازي به جستجوي راهكارهاي جديد نيست و مسئله شكلي از استنباط آماري را به خود مي‌گيرد. فرض كنيد احتمال انتخاب جواب درست را با «انتخاب جواب بهينه يا نزديك به بهينه» تعريف كنيم. در اين‌صورت مسئله مي‌تواند به يكي از دو شكل زير فرموله شود:

– تعداد تكرارهاي شبیه‌سازی را حداقل كنيد مشروط بر اينكه احتمال انتخاب جواب درست بيش از مقدار معيني باشد.

– احتمال انتخاب جواب درست را حداكثر كنيد مشروط بر اينكه محدوديت هزينه‌هاي شبیه‌سازی مدنظر قرار بگيرد.

در مورد اول مي‌توان در سطحي از اطمينان به حصول جواب مناسب اطمينان داشت اما تعداد محاسبات مورد نياز مشخص نيست. در شكل دوم محاسبات محدود است اما نمي‌توان به درستي در خصوص كيفيت جواب به‌دست آمده اظهارنظر کرد.

ب) روش جواب‌ سطح[1]

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

ج) روش مبتني بر گراديان[2]

اين روش در پي آن است كه نقش خود در بهینه‌سازی قطعي را در بهینه‌سازی تصادفي ايفا نمايد. ايده اساسي اين است كه به ازاء هر جواب، حركت در جهت گراديان بهترين تغيير است. با اين روش برآورد مشتق تابع هدف نسبت به متغير xi با استفاده از رابطه زير صورت مي‌گيرد:

 

(2-14)

براي برآورد گراديان به ازاء بردار X حداقل n+1 مدل شبیه‌سازی بايد اجرا شود. افزايش دقت محاسبة DG نيازمند افزايش تعداد محاسبات است. اين روش از ايده‌هاي حل مسائل برنامه‌ريزي غير خطي سود مي‌برد و براي متغير‌هاي تصميم پيوسته مناسب است.

د) جستجوي تصادفي[3]

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

– فهرست نقاط كانديد براي حركت بعدي چگونه انتخاب شود؟

– بهترين جواب تاكنون كدام است؟

انتخاب بهترين جواب در مسائل قطعي مشكلي به‌وجود نمي آورد زيرا مقدار به‌دست آمده براي تابع هدف به ازاء هر جواب، مقدار قطعي تابع هدف است. اما در مسائل تصادفي با توجه به اختلالات ذاتي تابع هدف انتخاب بهترين جواب كار ساده‌اي نيست.

هـ) تقريب ميانگين نمونه[4]

روش تقريب ميانگين نمونه كه بهینه‌سازی مسير نمونه[5] نيز ناميده می‌شود، ابتدا شبیه‌سازی را به تعداد زياد انجام داده و سپس تقريب‌هاي به‌دست آمده را بهينه مي‎كند، پس از به‌دست آمدن مقدار متوسط تابع هدف مقدار بهينه آن با استفاده از روش‌هاي برنامه‎ريزي غيرخطي كه در  مسائل قطعي كاربرد دارند، مشخص مي‌شود.

 

 

و) فراابتكاري‌ها

براي هدايت روش‌هاي ابتكاري استفاده می‌شود تا در دام نقاط بهينه محلي گرفتار نشوند. رايج‌ترين الگوریتم‌های فراابتكاري در حل مسائل بهینه‌سازی تركيبياتي عبارتند از شبیه‌سازی تبريد تدريجي[6] (SA)، جستجوي ممنوع[7] (TS)، الگوريتم ژنتيك[8] (GA)، جمعيت مورچگان[9] (ACO). الگوریتم‌های مذكور در يك ايده اساسي مشترك هستند و آن شروع حل مسئله از يك يا چند جواب ابتدايي و حركت از نقاط آغازين به سمت نقاط بهتر است. تفاوت بين اين الگوریتم‌های چگونگي تعيين نقاط شروع و سازوكار حركت به سمت جواب‌هاي بهتر است. اين تكنيك‌ها معمولاً نتيجه تطبيق ايده‌هاي متعلق به حوزه‌هاي مختلف تحقيق هستند. ايده‌هاي اساسي كه الهام‌بخش هر يك از الگوريتم‌ها هستند معمولاً از زمينه‌هاي غير منتظره شكل مي‌گيرد.

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

[1] – Response Surface Methodology

[2] – Gradian base search method

[3] – Random Search

[4] – Sample average estimation

[5] – Sample path optimization

[6] .Simulated Annealing

[7] . Taboo Search

[8] . Genetic Algorithm

[9] . Ant Colony Optimizatinon