عدم قطعیت بنیادی[۵۹]
عدم قطعیت دنیای واقعی[۶۰]
عدم قطعیت دانش اغلب با عناوین زیر بیان می‌شود:
عدم قطعیت ادراکی[۶۱]
عدم قطعیت تابعی[۶۲]
عدم قطعیت داخلی[۶۳]
عدم قطعیت فاعلی[۶۴]
نقص[۶۵]
عوامل زیر را میتوان به عنوان عوامل به‌وجود آورنده عدم قطعیت نوع دانش در نظر گرفت (Ivanov & Sokolov, 2009):
فعالیتهای ناشناخته‌ای که به صورت عمدی، جهت مقابله، از سوی یک سیستم رقیب صورت می‌گیرد.
اثرگذاری پدیده های وابسته به پدیده‌ی مورد مطالعه و کسب اطلاعات ناکافی در مورد آن.
عدم قطعیت ناشی از تفکرات بشر.
عدم آگاهی و دانش بشر.
در جهان هستی رخدادهای غیرقطعی فراوانی وجود دارد. برخی از این رخدادها عدم قطعیت خود را از منبع تغییرپذیری طبیعی دریافت می‌نمایند و لذا میتوان با مشاهدات پی‌در‌پی اطلاعاتی را در مورد آن به دست آورد اما رویدادهایی که از منبع نقص تغذیه میشوند معمولا در یک ابهام کامل به سر می‌برند و لذا چیزی به جز استدلال‌ها و نتیجه‌گیری‌های بشری که ریشه در عقل و احساس انسان دارد نمیتواند در زمینه کاهش عدم قطعیت آنها کمک نماید.
فضای عدم قطعیت را میتوان با توجه به هدف تحلیل‌گر، گسترش یا کاهش داد. در شکل (۲-۱) لایه های مختلفی مورد بررسی قرار گرفته‌اند که هر یک با توجه به هدف تحلیل‌گر و همچنین وقوع یا عدم وقوع پدیده، مورد توجه قرار می‌گیرند. در مرحله‌ی اول یعنی قبل از وقوع پدیده، عدم قطعیت مورد توجه میباشد زیرا هیچ اطلاعاتی از پدیده و نحوه‌ی وقوع آن و نتایج آتی وجود ندارد. ریسک از عدم قطعیت آغاز می شود و پس از وقوع پدیده، مسأله وارد دنیای ریسک می‌گردد. اختلال (اثر آشفتگی) نتیجه ریسک میباشد و پس از بدست آمدن نتایج اولیه قابل مطالعه است. انحراف (شکست) نیز ناشی از اثرات آشفتگی میباشد (مرجع متخصصین ایران، ۲۰۱۰).
شکل(۲-۱): گسترش عدم قطعیت (مرجع متخصصین ایران، ۲۰۱۰)
تصمیمات از نظر میزان اطمینان به صورت زیر طبقه بندی میشوند (تبریزی، ۱۳۹۲):
شرایط اطمینان کامل[۶۶]
شرایط ریسک[۶۷]
شرایط عدم اطمینان[۶۸]
بهینهسازی تکاملی در محیطهای عدم قطعیت
در بسیاری از مسائل بهینهسازی جهانواقعی، طیف وسیعی از عدم قطعیتها درنظر گرفته می شود. به طور کلی، عدم قطعیتها در بهینهسازی تکاملی می تواند به چهار گروه طبقه بندی شود:
نویز[۶۹]: بررسی برازندگی با نویز در ارتباط است. نویز در ارزیابی برازندگی ممکن است از منابع مختلفی از قبیل خطاهای اندازه گیری حسی یا شبیهسازی تصادفی بیاید. به طور ریاضی، یک تابع برازندگی می تواند به صورت رابطه (۲-۱) شرح داده شود.
(۲-۱)
به طوریکه یک فاکتور از پارامترهایی است که اغلب به عنوان «متغیرهای طراحی»[۷۰] شناخته می شود و می تواند توسط الگوریتم تغییر کند.f یک تابع برازندگی با زمان نامتغیر میباشد. نویز افزایشی میباشد که اغلب تابع توزیع نرمال با میانه صفر و واریانس فرض می شود. باید توجه کرد که نویز غیرگاوسی[۷۱] نیز مانند نویز توزیعکوشی[۷۲] در نظر گرفته شده است. هیچ تفاوت کیفی در عملکرد یک استراتژی تکاملی در مجاورت نویز گاوسی یا کوشی مشاهده نمی شود. به طور ایدهآل، الگوریتمهای تکاملی باید بر روی تابع برازندگی مورد انتظار کار کنند و به علت وجود نویز، گمراه نشوند. بههرحال، در طول بهینهسازی، تنها مقدار برازندگی قابل اندازه گیری احتمالی است. بنابراین، عملا تابع برازندگی مورد انتظار در رابطه (۲-۱) اغلب توسط یک مجموع میانگین از تعداد نمونههای تصادفی تقریب زده میشوند که به صورت رابطه (۲-۲) میباشد.
(۲-۲)
اندازه نمونه است و امید ریاضی از است (Jin & Branke, 2005).
پایداری[۷۳]: متغیرهای طراحی با انحراف یا تغییرات در ارتباط هستند که بعد از راه حل بهینه مشخص میشوند. بنابراین، یک نیاز عمومی این است که یک راه حل باید هنگامی که متغیرهای طراحی اندکی تغییر می کنند هنوز بطور رضایت بخش کار کند. برای مثال به دلیل تلرانس ساخت؛ این چنین راهحلهایی، «راه حلهای پایدار» نامیده میشوند. برای جستجوی راه حلهای پایدار، الگوریتمهای تکاملی باید بر روی امید ریاضی تابع برازندگی براساس توزیع احتمال از انحرافات توزیع کار کنند، به طوریکه انحرافات به صورت مستقل از همدیگر و با توزیع نرمال فرض میشوند.
(۲-۳)
به طور کلی مشخص کننده «تابع برازندگی موثر» میباشد. نظر به اینکه یک تحلیل اختصاصی از تابع برازندگی موثر در رابطه (۲-۳) معمولا در دسترس نیست، این تابع اغلب با بهره گرفتن از ادغام مونت کارلو[۷۴] تقریب زده می شود.
(۲-۴)
توجه کنید که رابطه (۲-۴) بسیار شبیه به رابطه (۲-۲) است و در واقع دو حالتی هستند که ارتباط تنگاتنگ با هم دارند. با این وجود، تفاوتهای مهمی نیز وجود دارد. در حالت نویز، معمولا فرض می شود که نویز به مقادیر برازندگی اعمال می شود؛ در حالیکه هنگام جستجوی راه حلهای پایدار، عدم قطعیت در متغیرهای طراحی است. در نتیجه حتی اگر دارای میانه صفر و توزیع نرمال باشد، مقدار برازندگی موثر بستگی به شکل در نقطه X دارد. در نتیجه، یک راهحل بهینه پایدار لزوما یک بهینگی از نیست اما معمولا یک موازنه بین کیفیت و پایداری راهحل وجود دارد. اگر نویز حتمیالوقوع فرض شود، یک کروموزوم نمیتواند با دقت بالایی ارزیابی شود. از سوی دیگر، در موقع جستجوی راه حلهای پایدار، تـابع برازندگی معمولا شنـاخته شده و قطعی فرض می شود و عدم قطعیت تنها بعد از پایان بهینهسازی مطرح می شود. به همین دلیل تخمین انتگرال بر روی تمام انحرافات ممکن، مشکل است (Jin & Branke, 2005).
تقریب تابع برازندگی[۷۵]: هنگامی که تابع برازندگی برای ارزیابی بسیار هزینهبر است، یا یک تابع برازندگی تحلیلی در دسترس نیست، توابع برازندگی اغلب بر اساس داده های حاصل از آزمایش و شبیهسازی تقریب زده میشوند. تابع برازندگی تخمین زده شده اغلب به عنوان «متا-مدل»[۷۶] شناخته می شود. متا مدل معمولا باید با تابع برازندگی اصلی مورد استفاده قرار گیرد. در این حالت، تابع برازندگی برای بهینه شدن توسط الگوریتمهای تکاملی، به صورت رابطه (۲-۵) تبدیل خواهد شد:
(۲-۵)
که در آن خطای تقریبی متا-مدل است. مهمترین تفاوت بین یک تابع برازندگی نویزدار و تابع برازندگی تقریبی این است که در تابع برازندگی تقریبی پس از آنکه متا مدل ساخته و سیستماتیـک شد، خطـا قطعی است (به عنوان مثال، با میانه صفر). بنـابراین، خطـا نمیتواند با نمونهبَرداری دوباره از تابع برازندگی تقریبی کاهش یابد. در عوض، این خطا با بهره گرفتن از تابع برازندگی واقعی به جای تقریبی نشان داده می شود.
انگیزه اصلی برای استفاده از متا-مدلها، ارزیابی برازندگی است تا تعداد ارزیابیهای برازندگیِ هزینه بَر بدون تنزل کیفیتِ راهحلِ بهینه بدست آمده، کاهش یابد (Jin & Branke, 2005).
تابع برازندگی تغییرات زمانی[۷۷]: تابع برازندگی در هر نقطه از زمان قطعی است، اما وابسته به زمان است، به عنوان مثال
(۲-۶)
در نتیجه، تغییرات در طول زمان نیز بهینه است. بنابراین، الگوریتم تکاملی باید قادر باشد که به طور مداوم تغییرات بهینگی را پیگیری کند نه اینکه نیاز به تکرار یک شروع مجدد از فرایند بهینهسازی داشته باشد. در اینجا چالش این است که، الگوریتم تکاملی مجددا از اطلاعات محیطهای قبلی برای افزایش سرعت بهینهسازی بعد از یک تغییر استفاده کند (Jin & Branke, 2005).
پایدارکردن جوابها در شرایط عدم قطعیت
پایدار کردن جواب برای مسائل کاربردی در شرایط عدم قطعیت یکی از جنبههایی است که اخیرا توجه بسیاری از پژوهشگران را در این زمینه به خود جلب کرده است؛ مسأله VRP نیز از این امر مستثنی نیست. چنانچه مسائل به گونه ای بهینه شوند که بتوانند در برابر نوسانات ناشی از محیط، کارآیی خود را از دست ندهند در نهایت به مسائل دنیای واقعی نزدیکتر خواهند شد.
وجود یکسری از محدودیتها در پیرامون مسائل باعث ایجاد مسائلی توام با عدم قطعیت گردیده است که به مراتب حل آنها از نوع سادهترشان را پیچیدهتر کرده است (افندیزاده، غفاری و کلانتری،۱۳۹۰د).
قبل از اینکه بحث در مورد پایداری را شروع کنیم بهتر است شرح مختصری در مورد محیطهای پویا بدهیم.
محیطهای پویا[۷۸]
در بسیاری از مسائل بهینهسازی دنیای واقعی، تابع هدف، نمونه مسأله یا محدودیتها ممکن است در طول زمان تغییر کنند و در نتیجه، بهینگی این مسائل نیز ممکن است تغییر کند (افندیزاده، غفاری و کلانتری،۱۳۹۰د). اگر هر یک از این حوادث غیرقطعی در فرایند بهینهسازی انجام شود، ما آن را «مسائل پویا»[۷۹] یا «تغییر کننده»[۸۰] مینامیم.
در بسیاری از کارهای بهینهسازی نیاز به تعیین راهحلهایی هست که مقادیر آنها با توجه به تغییر اندکی از مقادیر پارامترها، تغییر چندانی نمیکنند (Tsutsui & Ghosh, 1997). البته سادهترین راه برای واکنش نشان دادن به تغییر محیط این است که با توجه به هر تغییری که میرسد، یک مسأله بهینهسازی جدید درنظر گرفته شود که باید آن را از ابتدا حل کرد (Raman & Talbot, 1993)؛ در صورتیکه زمان کـافی در اختیـار داشته باشیم، این روش منـاسب است. با این حال اغلب، زمان بهینهسازی مجدد نسبتا کوتاه است (Jin & Branke, 2005).
تلاش طبیعی برای افزایش سرعت بهینهسازی بعد از یک تغییر به نحوی خواهد بود که از دانش در مورد فضای جستجوی قبلی برای پیشبُرد جستجو بعد از یک تغییر استفاده شود. برای بسیاری از مسائل دنیای واقعی، انتظار داریم که تغییرات نسبتا ساده باشند، در نتیجه میتوان به وسیله انتقال دانش از گذشته بسیار بهره برد.
سوال دشوار این است که چه اطلاعاتی باید نگه داشته شود، و چگونه از آن برای سرعت بخشیدن به جستجو پس از تغییر محیط استفاده شود. اما حتی زمانی که اطلاعات مفید می تواند منتقل شود، باید اطمینـان حاصل شود که الگـوریتم بهینهسازی به اندازه کافی برای پاسخ به تغییرات انعطافپذیر است (Jin & Branke, 2005).
پایداری
