F₂

شکل۳-۱-نقاط بهینه موضعی

تعریف ۳-۳- نقاط بهینه سراسری^[۱۱۸]

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

F₁
F₂
ناحیه عدم تفاوت
ناحیه مغلوب شدن
ناحیه غالب شدن
ناحیه عدم تفاوت
شکل ۳-۲- رابطه فضای جواب و ارتباط غالب

تعریف ۳-۴-مرز بهینه^[۱۱۹]

مجموعه نقاط بهینه سراسری یا پارتو، تشکیل مرزی را می دهند که به آن مرز بهینه گفته می شود. هدف اصلی رویکرد بهینه­سازی چند معیاره، دسترسی هر چه بیشتر به نقاط ( جوابهای ) بهینه سراسری یا پارتو می باشد.

۳-۴- جمع بندی

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

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

فصل چهارم

ساختار الگوریتم حل و نتایج محاسباتی

مقدمه

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

۴-۱- الگوریتم بهینه سازی کلونی زنبورها

الگوریتم های گروهی در حل مسایل بهینه سازی چند متغیره بسیار کارآمد هستند . الگوریتم زنبور، ارائه شده توسط فام و همکارانش در سال ۲۰۰۵ [۱۰۴] الگوریتم گروهی نوظهوری است که از رفتار جستجوی غذای زنبور عسل تقلید میکند. در این پایان نامه الگوریتم زنبور برای بهینه سازی مقدار هزینه کل در یک شبکه زنجیره تامین حلقه بسته به کار گرفته می شود. این امر مستلزم بهینه سازی توابع چند متغیره است. در ادامه، ابتدا به رفتار زنبورها در طبیعت اشاره می شود و سپس الگوریتم زنبور شرح داده می شود. کلونی زنبور جستجوی غذا را با فرستادن زنبورهای دیده بان به منظور جستجوی تصادفی منابع غذای امیدبخش آغاز می کند. کلونی برای بهره برداری از منابع غذایی می تواند تا مسافت های طولانی ۱۴) کیلو متر)و همزمان در جهت های مختلف پرواز کنند، با این ترتیب بهره برداری از تعداد زیادی منبع غذا تضمین میشود [۱۰۵,۱۰۶] .طی فرایند جستجوی غذا همواره تعدادی از زنبورهای کلونی به عنوان زنبور دیده بان در نظر گرفته می شوند [۱۰۶] اگر کیفیت شهد جمع آوری شده از یک منبع غذا از آستانه معیاری بالاتر باشد، زنبور دیده بان آن را در کندو ذخیره می کند و آن منبع غذا را در رقص قرقر ه ای تبلیغ می نماید [۱۰۴] . رقص قرقر ه ای برای ارتباطات کلونی حیاتی است و تمام اطلاعات لازم از بیرون کندو را شامل می شود [۱۰۵,۱۰۶] . زنبورهای کندو منابع غذا را با توجه به اطلاعات به دست آمده از رقص های قرقره ای در مورد کیفیت آنها انتخاب می کنند . بنابراین، زنبورهای بیشتری منابع غذای امیدبخش را بازدید می کنند [۱۰۵,۱۰۶] . این امر به فرایند جستجوی غذای کارآمد منجر می گردد . اعزام زنبورهای بیشتر به یک منبع غذای امیدبخش تا زمانی که برازش آن منبع غذا از آستانه ی معیاری بالاتر باشد ، ادامه می یابد.

۴-۲- فلوچارت الگوریتم کلونی زنبور عسل

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

شکل ۴-۱- فلوچارت الگوریتم کلونی زنبور عسل

۴-۲-۱- نحوه نمایش جواب

در تمام الگوریتم های فراابتکاری، بدلیل نیاز به حل شدنی در شروع کار، لازم است حل شدنی را بر طبق ساختار مشخصی ذخیره کنیم که به این ساختار، نحوه نمایش جواب می گویند. در این پایان نامه برای نمایش هر جواب از ماتریس استفاده می شود. هر جواب شامل ۴ ماتریس است که این ماتریسها مطابق با خروجی
­های مدل طراحی می شوند. بعنوان مثال برای متغیر x_is یک ماتریس دو بعدی با ابعاد n*pl است. یا برای متغیر x_if یک ماتریس ۲ بعدی با ابعاد n*dc تعریف می شود. به همین صورت برای z_kibj یک ماتریس ۴ بعدی و برای y_iwj نیز یک ماتریس سه بعدی تعریف شده است.

۴-۲-۲- نحوه تولید جوابهای اولیه^[۱۲۰]

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

1. 1. شمارنده را مساوی صفر قرار بده.

1. 1. جواب ورودی را به عملگر جستجوی همسایگی اول بده.

1. 1. رویه اصلاحی را بر جواب خروجی اعمال کن.

1. 1. جواب ورودی را به عملگر جستجوی همسایگی دوم بده.

1. 1. رویه اصلاحی را بر جواب خروجی اعمال کن.

1. 1. جواب ورودی را به عملگر جستجوی همسایگی سوم بده.

1. 1. رویه اصلاحی را بر جواب خروجی اعمال کن.

1. 1. جواب ورودی را به عملگر جستجوی همسایگی چهارم بده.

1. 1. رویه اصلاحی را بر جواب خروجی اعمال کن.

1. 1. از بین جواب ورودی و چهار جواب خروجی بهترین جواب را انتخاب کن.

1. به شمارنده یک واحد اضافه کن.