روش های عددی
روش های برنامه ریزی دینامیکی [۱۳۹]
 روش های مدرن [۱۴۰] (یا مکاشف های(ابتکاری[۱۴۱]

۴-۳-۱- روش های تصویری

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

۴-۳-۲- روش های تحلیلی یا کلاسیک

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

۴-۳-۳- روش های خاص

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

۴-۳-۴- روش های عددی

روش های عددی در بسیاری از مسایل از قبیل حل معادلات و دستگاه معادلات غیرخطی ومعادلات دیفرانسیل، تنها گزینه عملی میباشد. طبیعی است که این روش ها برای حل مسایل بهینه سازی نیز به کار بروند.
روش های عددی برای حل مسایل بهینه سازی، نیاز به یک حدس اولیه دارند و سپس این حدس را با تکرارهای متوالی مدام بهبود می دهند تا به اندازه کافی به یک جواب مساله نزدیک گردد.
به عبارت دقیق تر، رو شهای عددی بر مبنای حدس اولیه، دنباله ای را می سازند که این دنباله به یک جواب مساله همگرا می گردد. تفاوت روش های عددی در نحوه ایجاد و ساختن دنباله است.
۴-۳-۵- روش های برنامه ریزی پویا[۱۴۲]
برنامه‌ریزی پویا روشی کارآمد برای حل مسائل جستجو و بهینه‌سازی با بهره گرفتن از دو خصیصه، زیرمسئله‌های هم‌پوشان و زیرساخت‌های بهینه است.
زمانی که یک مساله به دو یا چند زیرمساله تقسیم می‌شود، دو حالت ممکن است پیش بیاید:
۱- داده‌های زیرمساله‌ها هیچ اشتراکی با هم نداشته و کاملا مستقل از هم هستند. نمونه چنین مواردی مرتب‌سازی آرایه‌ها با روش ادغام یا روش سریع است که داده‌ها به دو قسمت تقسیم شده و به صورت مجزا مرتب می‌شوند. در این حالت داده‌های یکی از بخش‌ها هیچ ارتباطی با داده‌های بخش دیگر نداشته و در نتیجه حاصل از  آن بخش اثری ندارند. معمولا روش تقسیم و حل برای چنین مسائلی کارآیی خوبی دارد.
۲- داده‌های زیرمساله وابسته به هم بوده و یا با هم اشتراک دارند. در این حالت به اصطلاح زیرمساله‌ها هم‌پوشانی دارند. نمونه بارز چنین مسائلی محاسبه جمله nام دنباله اعداد فیبوناچی است.

۴-۳-۶- روش های مدرن یا مکاشفه ای

روش های کلاسیک و عددی دارای دو ضعف اساسی میباشند که عبارتند از موضعی بودن و عدم قابلیت اعمال روی مسایل گسسته. برای رفع ضعف های مذکور روش های متفاوتی ارائه گردیده است، که آ نها را تحت نام رو شهای مدرن نامگذاری می کنیم. این رو شها در دو دهه اخیر، با بالا رفتن قدرت و سرعت کامپیوترها، بیشتر مورد استفاده قرار گرفته اند. روش های مدرن، دسته ای از الگوریتمها می باشند که از طبیعت و یا نحوه تکامل موجودات زنده الهام گرفته اند.
از مشخصه های این الگوریتم ها می توان موارد زیر را برشمرد:
معمولا به فرضیاتی روی مساله از قبیل مشتق پذیری، محدب بودن و غیره نیازندارند. بنابراین این رو شها را میتوان روی طیف وسیعی از مسایل اعمال نمود.
عموما، رو شهای مدرن سراسری و بدون مشتق میباشند.
این رو شها برای مسایل پیوسته و گسسته قابل استفاده می باشند.اصولا این رو شها برای مسایل گسسته، مناسبتر میباشند.
معمولا هیچ پشتوانه مبتنی بر ریاضی برای عملکرد و همگرایی این روش ها به جواب بهینه وجود ندارد. اما در عمل همگرایی خود را نشان داد ه اند.
۴-۴- مسائل چند هدفه ومفهوم بهینگی پارتو[۱۴۳]
بهینگی پارتوبه نام اقتصاددان ایتالیایی،ویلفردوپارتو[۱۴۴]نامیده شدکه بعنوان اندازه ای از کارائی در بهینه سازی مسائل چند هدفه مورد استفاده قرارگرفت. در مسائل چند هدفه به جای یک تابع هدف، چندین تابع هدف باید بصورت همزمان بهینه شوند. در چنین شرایطی معمولاً مسئله دارای بیش از یک جواب بهینه خواهد بود که به آنها جوابهای بهینه پارتو گفته می شود. مفهوم بهینه پارتو به این صورت قابل تشریح است که x* = (x1, x2, x3,… ,x n) یک بهینه پارتو است اگر برای هرx دیگر عضو دامنه مجازوi={1,2,…,K} داشته باشیم(برای یک مسئله کمینه سازی):
که در آن n تعداد متغیرهای فضای تصمیم وkتعداد توابع هدف است. به عبارت دیگر یک بهینه پارتو است اگر هیچ بردار x دیگری وجودنداشته باشد که به ازای بهبود بخشیدن برخی از توابع هدف حداقل یک تابع هدف را بدتر نکند. جوابهای بهینه پارتو تحت عنوان جوابهای نامغلوب[۱۴۵]نیز شناخته می شوند.

۴-۵- روش های حل پیشنهادی

جهت حل مدل پیشنهادی ارائه شده از دوالگوریتم فرابتکاری مبتنی بر پارتو استفاده نموده ایم که در ادامه به تفضیل تشریح می گردد.
۴-۵-۱- الگوریتم بهینه سازی اذحام ذرات چند هدفه[۱۴۶](MOPSO)
الگوریتم بهینه سازی ازدحام ذرات (PSO)[147] به عنوان یک تکنیک جستجو توسط ابرهارت و کندی[۱۴۸] در سال ۱۹۹۵ معرفی گردید. در تدوین این روش از حرکات جمعی و گروهی ذرات الگو برداری شده است و در برخی اوقات این الگوریتم را به اشتباه تحت عنوان الگورتیم پرندگان و یا ماهی ها نیز می شناسند. این روش بهینه سازی جزء روش های هوش ازدحامی یا هوش گروهی[۱۴۹] به حساب آمده و اساس کار آن بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون خود در آن قرار گرفته و بهترین مکانی که در کل یافت شده است، تنظیم می‌کند. طبق تحقیقات انجام شده الگوریتم بهینه سازی ازدحام ذرات در بسیاری از مسائل مهندسی از قبیل مسئله تخمین پارامتر، طراحی شبکه های تامین، مسئله انتخاب سبد بهینه سهام، مسئله حرکت خودروها، مسئله برنامه ریزی تولید، مسئله خوشه بندی و غیره عملکرد مناسبی را دارا می باشد. با توجه به کارایی الگوریتم PSO در حل مسائل تک هدفه، سیرا و کوئلو کوئلو[۱۵۰]در سال ۲۰۰۶ با ایجاد تغییراتی در ساختار این الگوریتم، الگوریتم چند هدفه بهینه سازی ازدحام ذرات (MOPSO)را معرفی کردند. تحقیقات انجام شده، حاکی از عملکرد بالای این الگوریتم در حل مسائل بهینه سازی چند هدفه می باشد.
این الگوریتم نیز مانند سایر الگوریتم های جمعی ،با جمعیت تصادفی شروع به کار می کند.در واقع هرکدام از اعضایک ذره[۱۵۱]هستند که مجموعه[۱۵۲] را به وجودمی آورند.این مجموعه با توجه به سرعتهای هر ذره ومجموعه در فضای تصمیم به سمت نقطه بهینه حرکت می کند.به این ترتیب بردارحرکت هرذره درهر تکرارتحت تاثیربهترین موقعیتی که ذره تاکنون به آن رسیده است(Pbest) وبهترین موقعیتی که بهترین عضو مجموعه تاکنون به آن رسیده است(Gbase ) می باشد.دراین روش برای هر هدف یک مجموعه تولید شده وGbestمرتبط با آن درهرتکراراستخراج می گردد.برای رفتن به مرحله بعدی ،هرمجموعه Gbest خود را به مجموعه بعدی منتقل می کند.این درحالی است که Pbest برای هرمجموعه بطوراختصاصی به دست می آید.در نهایت پس از تعدادمشخصی تکرار مجموعه حاصل از آخرین مجموعه،به عنوان مجموعه نهایی ونقاط مغلوب آن بعنوان مجموعه جواب یا پارتومعرفی می گردند.اعضای مجموعه پارتو هیچ برتری بریکدیگر نداشته وبا کاهش مقدارتابع هدف ،مقدارتابع هدف دیگر افزایش می یابدوبرعکس.

۴-۵-۱-۱- مراحل الگوریتم (MOPSO)

ایجاد جمعیت اولیه
جدانمودن اعضای نامغلوب[۱۵۳] جمعیت وذخیره نمودن آن در Rep[154]
جدول بندی فضای هدف کشف شده
هر ذره از میان اعضای Rep یک رهبر انتخاب می کند وحرکت خودراانجام می دهد.
بهترین خاطره شخصی هرکدام از ذرات به روز می شود.
اعضای نامغلوب جمعیت فعلی به Repاضافه می گردد.
اعضای مغلوب Rep حذف می نمائیم.
اگرتعداد اعضای Rep بیش از ظرفیت تعیین شده باشد اعضای اضافی را حذف نموده وجدول بندی راتجدید می کنیم.
در صورتی که شرایط خاتمه محقق نشده به مرحله ۳ برمی گردیم ودر غیر این صورت پایان.

۴-۵-۲- الگوریتم ژنتیک مرتب سازی نامغلوب نسخه ۲(NSGA-II)

الگوریتم NSGA-II یکی از پرکاربردترین و قدرتمندترین الگوریتم های موجود برای حل مسائل بهینه سازی چند هدفه است و کارایی آن در حل مسائل مختلف، به اثبات رسیده است. اسرینیواس و دِب[۱۵۵] در سال ۱۹۹۴ روش بهینه سازی NSGA را برای حل مسائل بهینه سازی چند هدفه معرفی نمودند. نکات برجسته ای که در مورد این روش بهینه سازی وجود دارند، عبارتند از :
جوابی که هیچ جواب دیگری، به طور قطع بهتر از آن نباشد، دارای امتیاز بیشتری است. جواب ها بر اساس این که چند جواب بهتر از آن ها وجود داشته باشند، رتبه بندی و مرتب می شوند.
شایستگی (برازندگی) برای جواب ها، بر حسب رتبه آن ها و عدم غلبه سایر جواب ها، اختصاص می یابد.

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...