include ith nondominated front in parent pop
i=i+1 check the next front for inclusion
sort sort in descending order using
choose the first elements of Fi
Qt+1=make-new-pop(Pt+1) use selection, crossover and mutation to
create a new population Qt+1
t=t+1 increment the generation counter
شکل۳-۵٫ شبهکد رویه تولید نسل بعد
شکل۳-۶٫ فلوچارت الگوریتم NSGA-II
تولید جمعیت اولیه P0
ارزیابی توابع هدف و رتبه بندی جوابها
مسابقه باینری برای انتخاب جوابها
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
عمل تقاطع و جهش برای تولید جمعیت فرزندان (Qt) و ارزیابی آنها
انتخاب نسل بعد Pt+1 از بین بهترینهای Rt
معیار توقف محقق شده محقق
بلی
خیر
ترکیب جمعیت والدین و فرزندان (Rt) و رتبه بندی آنها
۳-۶-تشریح مراحل الگوریتم ([۶۸]NRGA)
الگوریتم NRGA از نظر ساختار شبیه الگوریتم NSGAII می باشد، تنها تفاوت این الگوریتم
با NSGAIIدر بخش استراتژی انتخاب و بخش مرتب کردن جمعیت و انتخاب برای نسل بعد می باشد که در ادامه دو بخش مذکور تشریح می گردد.
ابتدا تمام جواب های جمعیت را در مرزهای نامغلوب مرتب می کنیم به طوریکه اولین مرز دارای بهترین جواب ها در جمعیت می باشد. لذا اگر در این مرحله ما ۵ مرز نامغلوب برای جمعیت داشته باشیم به اولین مرز نمره ۵ و به پنجمین مرز، نمره۱ می دهیم. بنابراین هر چه امتیاز بالاتر باشد جواب ها بهتر می باشد. بعد از رتبه بندی مرزها، جواب های درون هر مرز را نیز براساس فاصله ازدحامی رتبه بندی می کنیم. بنابراین بعد از محاسبه فاصله ازدحامی برای تمام جواب های موجود در هرمرز، جوابی که بیشترین فاصله ازدحامی را دارد بیشترین رتبه وبه جواب با کمترین فاصله ازدحامی رتبه یک می دهیم. بدین ترتیب هر کدام از جواب های موجود در جمعیت دارای یک رتبه بندی دو لایه ای هستند، که رتبه اول آنها نشان دهنده رتبه مرز نامغلوبی است که آن جواب در آن مرز قرار دارد و رتبه دوم نشان دهنده رتبه جواب براساس فاصله ازدحامی در آن مرز می باشد.
کاربرد عملگر مقایسه انبوهی برای دو جواب مفروض iوj در جمعیت بدین ترتیب است که درابتدا، مقایسه میان رتبه های مربوط به مرزهای نامغلوبی که این جواب ها درآن قرار دارد انجام می شود. اگر رتبه مرزی که جواب i ام در آن قرار دارد بیشتر باشد، آنگاه جواب iام برای تولید مثل در نسل بعد احتمال انتخاب بیشتری پیدا می کند. حال اگر هر دو جواب در یک مرز غیر مغلوب قرار داشته باشد، جوابی که دارای فاصله ازدحامی بیشتری است احتمال انتخاب بیشتری پیدا می کند. درواقع علت اینکه فاصله ازدحامی بیشتر، احتمال انتخاب بیشتری می گیرداین است که مابا این کاراحتمالاً نقاط بیشتری را در مناطقی که شلوغی کمتری دارند پیدا می کنیم. به عبارت دیگر این امر منجر به یکنواختی پراکندگی جواب ها در مرز نامغلوب نسل بعدی خواهد شد.در این بخش، از عملگر چرخه رولت مبتنی بر رتبه بندی[۶۹] (RRWS) به جای استفاده از عملگر مسابقه ای ازدحام استفاده می کنیم به صورتی که در ادامه آورده شده است.
ساده ترین راه برای انتخاب، انتخاب به روش چرخ رولت می باشد. این روش یک نمونه برداری شانسی با جایگزینی است. این روش مبتنی بر شانس به این صورت انجام می شود که کلیه افراد بر مبنای میزان برازندگی خود بر روی نواحی همجوار یک خط نگاشت می شوند. اندازه ناحیه مربوط به هر فرد با توجه به اندازه برازندگی آن تعیین می شود. سپس یک عدد تصادفی تولید شده و با توجه به اندازه این عدد، فرد انتخاب می شود. این فرایند آنقدر تکرار می شود تا اینکه تعداد مورد نظر والدین) جمعیت تولید مثلی( تامین گردد. می توان به جای خط از یک دایره به این منظور استفاده نمود.
انتخاب چرخ رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب ترین انتخاب های تصادفی بوده که ایده آن، احتمال انتخاب می باشد. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگی آن محاسبه شده که اگر مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
(۳-۳۹)
حال کروموزوم ها را مرتب کرده، که همان مقادیر تجمعی می باشد به صورت زیر به دست می آید :
(۳-۴۰)
چرخ رولت به این صورت عمل می کند که برای انتخاب هر کروموزوم یک عدد تصادفی بین یک و صفر تولید کرده و عدد مذکور در هر بازه ای قرار گرفت، کروموزوم متناظر با آن انتخاب می شود. البته روش پیاده کردن چرخ رولت به این شکل است که یک دایره در نظر گرفته و آن را به تعداد کروموزوم ها طوری تقسیم می کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوط باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می گردد. انتخاب چرخ رولت، روشی است که به نسبت مقدار تطابق، اعضا را انتخاب می کند. این روش یک چرخ رولت را شبیه سازی می کند تا تعیین کند کدام اعضا شانس بازتولید را دارند. هر عضو به نسبت تطابقش، تعدادی از بخشهای چرخ رولت را به خود اختصاص می دهد. سپس در هر مرحله انتخاب، یک عضو برگزیده می شود و روند آنقدر تکرار می شود تا به اندازه کافی، جفت برای تشکیل نسل بعد انتخاب گردد.روش انتخاب چرخ رولت دارای بایاس صفر است اما حداقل گسترش را تضمین نمی کند. به این معنی که بین برازندگی یک فرد و احتمال انتخاب آن فاصله ای وجود ندارد. در ضمن ممکن است شانسی بودن این روش باعث می شود تا فقط یک فرد چندین بار انتخاب شده و یک فرد شایسته دیگر اصلا انتخاب نشود.
۳-۷- خلاصه فصل
در این فصل از پایان نامه به مدلسازی ریاضی مسأله طراحی شبکه خرید- تولید- توزیع چندهدفه برای زنجیره سه مرحله ای پرداخته شد. مدل ارائه شده دو هدف مجزا و متناقض حداقل سازی هزینهها وحداکثر سازی ارزش کل تولید که یک هدف کیفی در مسئله مورد نظر است را دنبال می کند. در راستای اعتبار سنجی مدل ارائه شده، یک مثال عددی کوچک به کمک نرم افزارلینگو حل و نتایج آن گزارش شد. با توجه به تعداد متغیرها و محدودیتهای مدل، با افزایش تعداد عناصر زنجیره، حل آن با نرمافزارهای بهینهسازی تقریباً غیرممکن است. از این رو بکارگیری الگوریتمهای فراابتکاری جهت حل این مسأله می تواند مؤثر باشد. به علت وجود تضاد بین اهداف در نظر گرفته شده، روش همزمانی یا پارتو بعنوان رویکرد حل مسأله انتخاب شده است. در نهایت، دو روش حل NSGAII و NRGA به صورت مبسوط توضیح داده شد.در فصل بعد به توضیح روش بکارگیری این الگوریتم ها در تحقیق حاضر ومقایسه آنها به وسیله شاخص های عملکرد پرداخته خواهد شد.
فصل چهارم
ارائه روش حل و تجزیه و تحلیل محاسباتی
۴-۱- مقدمه
در فصل قبل دوالگوریتم فراابتکاری NSGA-II، توضیح داده شد.در این فصل، ابتدا به چگونگی بکارگیری این الگوریتم ها در تحقیق حاضر پرداخته می شود ودر ادامه، مسائل نمونه آزمایشی توسط الگوریتم طراحی شده حل میگردند و با معرفی شاخص های ویژه مسائل چندهدفه، به مقایسه الگوریتمهای طراحی شده، پرداخته می شود. قابل ذکر است که الگوریتمهای بکار گرفته شده، در محیط نرم افزار متلب[۷۰] ویرایش R2009a توسط کامپیوتری با CPU Intel®Core™ Due و RAM ۲٫۲GB برنامهنویسی شده اند.
۴-۲- تشریح ساختار NSGA-II بکار گرفته شده در این تحقیق
در این بخش، اجزای طراحی شده برای ساختار الگوریتم مرتبسازی نامغلوب ژنتیک، جهت حل مسأله طراحی شبکه خرید- تولید- توزیع چندهدفه برای زنجیره تأمین سه مرحله ای، به تفصیل و گام به گام شرح داده می شود.
۴-۲-۱- نحوه نمایش جوابها[۷۱]
اولین گام در بکارگیری و پیادهسازی یک الگوریتم فراابتکاری، انتخاب روشی برای نمایش جوابهاست. تبدیل یک جواب از فضای حل به یک کروموزوم را اصطلاحاً رمزگذاری[۷۲] و برگرداندن یک کروموزوم را به یک جواب از فضای حل مسأله، رمزگشایی[۷۳] گویند. در واقع مهمترین بخش از الگوریتم ژنتیک که نقطه آغاز آن محسوب می گردد، همین قسمت می باشد.در ارائه جواب ها که به وسیله کروموزوم صورت می پذیرد باید نهایت دقت را به عمل آورد تا کروموزوم ها به خوبی فضای شدنی مسأله را تحت پوشش قرار دهند.در الگوریتم ارائه شده در این پایان نامه ، برای ارائه جواب ها در قالب کروموزوم، از کروموزوم هایی با سه بخش تشکیل شده که هر کدام در ادامه شرح داده می شوند.
بخش اول کروموزوم از یک ماتریس چهار بعدی ایجاد شده است که مقادیر متغیر را نشان می دهد. در این کروموزوم، درایه های ماتریس مقادیر صحیحی هستند که میزان تولیدات با بهره گرفتن از مواد اولیه نوع l، توسط نیروی کار با سطح مهارتk در دوره t ،در کارخانهj مشخص می گردد.
بخش دوم کروموزوم، نحوه تأمین مواد اولیه مورد نیاز برای کارخانه از طریق تأمین کننده ها مشخص می گردد.به عبارت دیگرمشخص می گرددکه هر یک از تولید کننده ها مواد اولیه سطح L خود را در هر دوره از کدام تأمین کننده تهیه می نمایند.از آنجایی که ظرفیت تأمین کننده ها محدود است این بخش از کروموزوم به صورت اعداد بین صفرویک که نشان دهنده اولویت ها هستند نشان داده می شوند.این بخش از کروموزوم از یک ماتریس سه بعدی با ابعاد(تعداد دوره تعداد نوع موادتعداد تولید کننده) می باشد.
در بخش سوم کروموزوم مشخص می گردد که هر مشتری نیاز دوره خود را از کدام تولید کننده یا تأمین کننده ها دریافت می کند.در این بخش از یک ماتریس سه بعدی با ابعاد ( تعداد دوره تعداد تولید کننده تعداد مشتری) با درایه های بین صفر ویک تشکیل شده است.درایه ها در این بخش نیز همانند درایه های بخش دوم نشان دهنده اولویت هستندوبا توجه به ظرفیت هر یک از تولیدکننده ها تقاضای مشتریان براساس این اولویت ها پوشش داده می شود.در ادامه یک نمونه، جهت درک نحوه عملکردکروموزوم وچگونگی رمزگشایی آن ارائه می گردد. مسأله زیر رادرنظر بگیرید.
فرض کنید تعداد تأمین کننده۲، تعدادمشتری۳، تعداد تولیدکننده۲وتعداد دوره ۱ است.همچنین فرض کنید یک کروموزوم مربوط به این مسأله به صورت زیر است:
K3 | K2 | K1 | J=1 ,t=1 |