گوتیرز و همکاران [۳۲]

۲۰۰۴

بکارگیری برنامه­ ریزی پویا و روش انشعاب و تحدید چندهدفه

تی سو [۲]

۲۰۰۹

دو نوع بهینه­ساز تکاملی

یانگ و همکاران [۱]

۲۰۱۲

الگوریتم فراابتکاری ژنتیک

موسوی و همکاران [۳۳]

۲۰۱۳

استفاده از الگوریتم­های فراابتکاری ژنتیک و شبیه­سازی تبریدی برای حل مدل ریاضی آمیخته دودویی در یک مسئله چند محصولی

ساراج­اوغلو و همکاران [۳۴]

۲۰۱۴

استفاده از الگوریتم­های فراابتکاری ژنتیک برای حل مدل ریاضی خطی عدد صحیح در یک مسئله چندمحصولی

پیشینه روش­های فراابتکاری استفاده شده

الگوریتم ژنتیک چندهدفه با مرتب سازی نامغلوب

الگوریتم ژنتیک الهامی از علم ژنتیک و نظریه تکامل داروین است و بر اساس بقای برترین­ها یا انتخاب طبیعی استوار است. یک کاربرد متداول الگوریتم ژنتیک، استفاده به عنوان تابع بهینه­کننده است. اگرچه کارهایی توسط یک زیست­شناس به نام فریزر^[۶۸] در زمینه مدل­سازی تکامل در سیستم­های بیولوژیک در دهه شصت میلادی صورت گرفت، ولی الگوریتم ژنتیک برای کاربردهای مهندسی و به صورت امروزی آن نخستین بار توسط جان هالند^[۶۹] متخصص علوم کامپیوتر دانشگاه میشیگان در سال ۱۹۷۵ پیشنهاد گردید. کار وی آغازی برای کاربرد الگوریتم ژنتیک در مهندسی است. پس از آن کارهای دی یانگ^[۷۰] در سال ۱۹۷۵ در زمینه بررسی و مقایسه چندین روش الگوریتم ژنتیک پایه­ های نظری این بحث را فراهم آورد.
در الگوریتم ژنتیک جمعیتی از افراد طبق مطلوبیت آنها در محیط بقا می­یابند. بنابراین بعد از چند نسل فرزندانی با کارایی بهتر بوجود می­آیند. در این الگوریتم هر جواب به صورت یک کروموزوم معرفی می­ شود. کروموزوم­ها در طول چندین نسل کامل­تر می­شوند. در هر نسل کروموزوم­ها ارزیابی می­شوند و متناسب با ارزش خود امکان بقا و تکثیر می­یابند. تولید نسل در الگوریتم ژنتیک با عملگرهای تقاطع^[۷۱] و جهش^[۷۲] صورت می­گیرد. والدین برتر بر اساس یک تابع برازندگی^[۷۳] انتخاب می­شوند. در هر مرحله از اجرای الگوریتم، یک دسته از نقاط فضای جستجو مورد پردازش تصادفی قرار می­گیرند. به این صورت که به هر نقطه دنباله­ای از کاراکترها نسبت داده می­ شود و بر روی این دنباله­ها، عملگرهای ژنتیکی اعمال می­ شود. سپس دنباله­های بدست آمده رمزگشایی^[۷۴] می­گردند تا نقاط جدیدی در فضای جستجو بدست آید. در انتها بر اساس این که تابع هدف در هر یک از نقاط چه مقدار باشد، احتمال شرکت نمودن آنها در مرحله بعد تعیین می­گردد.
اولین پیاده­سازی الگوریتم ژنتیک چند هدفه واقعی (VEGA) توسط دیوید شافر^[۷۵] در سال ۱۹۸۴ پیشنهاد شد. شافر سه عملگر الگوریتم ژنتیک (انتخاب، تقاطع و جهش) را با بهره گرفتن از چرخه انتخاب مستقل برای هر هدف اصلاح کرد. انتخاب برای هر هدف مجزا به منظور پر کردن بخشی از استخر جفت­گیری تکرار می­ شود. سپس عملگرهای تقاطع و جهش در کل جمعیت به دست آمده به کار گرفته می­شوند. تا یک دهه پس از کار شافر مطالعه مهمی در این زمینه صورت نگرفت تا زمانی که طرح ۱۰ خطی جدیدی توسط گلدبرگ^[۷۶] با عنوان روش مرتب­سازی غیرمغلوب پیشنهاد شد که از مفهوم غلبه به منظور رونوشت اعضا غیرمغلوب بیشتری در جمعیت استفاده می­کرد. فونسکا و فلمینگ^[۷۷] الگوریتم ژنتیک چندهدفه (MOGA) را که همه اعضای جمعیت غیرمغلوب به رتبه یک تخصیص داده می­شدند، پیشنهاد دادند. دیگر اعضا با توجه به این که چند راه حل بر آنها غلبه می­ کنند، رتبه ­بندی می­شدند.
سرینیواس و دب^[۷۸]، الگوریتم ژنتیک با مرتب سازی غیرمغلوب (NSGA) را توسعه دادند. این الگوریتم در مسایل واقعی، گسترده­ای از جواب­های پارتو بهینه و یا نزدیک به بهینه را فراهم می­کرد. برای غلبه بر مشکلاتی که در NSGA وجود داشت، دب و همکاران^[۷۹] الگوریتم بهبود یافته­ای با عنوان NSGAΙΙ را معرفی کردند [۳۵].

الگوریتم ﺑﻬﯿﻨﻪ ﺳﺎزی ازدحام ذرات چندهدفه

اوﻟﯿﻦ ﺑﺎر ﮐﻨﺪی و اﺑﺮﻫﺎرت^[۸۰] ﭘﺲ از ﺷﺒﯿﻪ­ﺳﺎزی رﻓﺘﺎر اﺟﺘﻤﺎﻋﯽ ﭘﺮﻧﺪﮔﺎن روش ﺑﻬﯿﻨﻪ­ﺳﺎزی ﮔﺮوه ذرات را اراﺋﻪ دادند [۳۶]. در این روش، اﺟﺰای ﯾﮏ ﮔﺮوه از ﯾﮏ رﻓﺘﺎر ﺳﺎده ﺗﺒﻌﯿﺖ ﻣﯽﻧﻤﺎﯾﻨﺪ. ﺑﺪﯾﻦ ﻧﺤﻮ ﮐﻪ ﻫﺮ ﻋﻀﻮ از ﮔﺮوه از ﻣﻮﻓﻘﯿﺖ ﺳﺎﯾﺮ ﻫﻤﺴﺎﯾﮕﺎﻧﺸﺎن ﺗﻘﻠﯿﺪ ﻣﯽ­ﻧﻤﺎﯾﺪ. ﻫﺪف از اﯾﻦ اﻟﮕﻮرﯾﺘﻢ­ﻫﺎ اﯾﻦ اﺳﺖ ﮐﻪ اﻋﻀﺎی ﮔﺮوه در ﻓﻀﺎی ﺟﺴﺘﺠﻮ ﺣﺮﮐﺖ ﻧﻤﻮده و در ﯾﮏ ﻧﻘﻄﻪ ﺑﻬﯿﻨﻪ (ﻣﺎﻧﻨﺪ ﻣﻨﺒﻊ ﻏﺬا) ﺟﻤﻊ ﺷﻮﻧﺪ. مدل روش PSO رﯾﺸﻪ در ﮐﺎرﻫﺎی رینولدز^[۸۱] دارد ﮐﻪ ﯾﮏ ﺷﺒﯿﻪ­ﺳﺎزی اﺑﺘﺪاﯾﯽ از رﻓﺘﺎر اﺟﺘﻤﺎﻋﯽ ﭘﺮﻧﺪﮔﺎن اﺳﺖ. در اﯾﻦ مدل رﻓﺘﺎرﻫﺎی ﺳﺎده ﭘﯿﺪا ﮐﺮدن ﻧﺰدﯾﮑﺘﺮﯾﻦ ﻫﻤﺴﺎﯾﻪﻫﺎ (ﺗﻨﻈﯿﻢ ﺳﺮﻋﺖ­ﻫﺎ) ﭘﯿﺎده ﺷﺪه اﺳﺖ. اﯾﻦ ﻣﺪل ﭘﺮﻧﺪﮔﺎن ﺑﻪ ﺻﻮرت ﺗﺼﺎدﻓﯽ در ﯾﮏ ﻓﻀﺎی ﺟﺴﺘﺠﻮی ﺟﺪول ﭘﯿﮑﺴﻠﯽ ﻗﺮار داده ﻣﯽﺷﻮﻧﺪ و در ﻫﺮ ﺗﮑﺮار ﻧﺰدﯾﮑﺘﺮﯾﻦ ﻫﻤﺴﺎﯾﻪ ذره اﻧﺘﺨﺎب ﺷﺪه و ﺳﺮﻋﺖ ذره ﺑﺎ ﺳﺮﻋﺖ ﻧﺰدﯾﮑﺘﺮﯾﻦ ﻫﻤﺴﺎﯾﻪاش ﺟﺎﯾﮕﺰﯾﻦ ﻣﯽﺷﻮد. اﯾﻦ ﻋﻤﻞ ﺑﺎﻋﺚ ﻣﯽﮔﺮدد ﮐﻪ ﮔﺮوه ﺧﯿﻠﯽ ﺳﺮﯾﻊ ﺑﻪ ﯾﮏ ﺟﻬﺖ ﺣﺮﮐﺖ ﻧﺎﻣﻌﯿﻦ و ﺑﺪون ﺗﻐﯿﯿﺮ ﻫﻤﮕﺮا ﺷﻮﻧﺪ. ﺟﻬﺖ رﻓﻊ اﯾﻦ ﻣﺸﮑﻞ ﯾﮏ ﻣﻮﻟﻔﻪ دﯾﻮاﻧﮕﯽ ﺑﻪ ﺻﻮرت ﺗﻐﯿﯿﺮ ﺗﺼﺎدﻓﯽ در ﮔﺮوه­ﻫﺎ اﺳﺘﻔﺎده ﺷﺪه اﺳﺖ.
ﺑﻪ ﻣﻨﻈﻮر ﺗﻮﺳﻌﻪ ﺑﯿﺸﺘﺮ اﯾﻦ ﻣﺪل ﻣﻔﻬﻮم ﺳﺮدﺳﺘﻪ ﭘﺮﻧﺪﮔﺎن^[۸۲] ﺑﻪ ﻣﺪل اﺿﺎﻓﻪ ﮔﺮدﯾﺪ ﮐﻪ ﺑﻪ ﺷﮑﻞ ﯾﮏ ﺣﺎﻓﻈﻪ از ﺑﻬﺘﺮﯾﻦ موقعیت­های ﻫﺮ ﻋﻀﻮ و ﻫﻤﺴﺎﯾﮕﺎن آن ﻋﻀﻮ ﺑﻮد. ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺖ ﻗﺒﻠﯽ ﻫﺮ ﻋﻀﻮ ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺘﯽ اﺳﺖ ﮐﻪ آن ﻋﻀﻮ از اﺑﺘﺪای ﺣﯿﺎت ﺧﻮد ﺗﺎ به حال ﮐﺴﺐ ﻧﻤﻮده اﺳﺖ. ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺖ ﻫﻤﺴﺎﯾﮕﯽ ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺘﯽ اﺳﺖ ﮐﻪ ﺗﻮﺳﻂ ﻫﻤﺴﺎﯾﮕﺎن ﯾﮏ ﻋﻀﻮ ﻣﻼﻗﺎت ﺷﺪه اﺳﺖ. اﯾﻦ دو ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺖ ﺑﻪ ﻋﻨﻮان ﻧﻘﺎط ﺟﺬب ﻋﻤﻞ ﻣﯽ­ﻧﻤﺎﯾﻨﺪ.

روش تحقیق

مقدمه

در این فصل، مدل ریاضی مسئله تحقیق، برای حالت­های یک هدفه و دو هدفه ارائه می­گردد. با توجه به NP-hardبودن مسائل SWMR [20]، استفاده از الگوریتم­های فراابتکاری برای حل مسئله در ابعاد بزرگ پیشنهاد می­گردد. بر این اساس، برای حل مسئله، الگوریتم ژنتیک با مرتب­سازی نامغلوب^[۸۳] و الگوریتم بهینه­سازی ازدحام ذرات چند هدفه^[۸۴] که عملکرد مناسبی در حل مسائل چندهدفه دارند، ارائه شده است. سپس معیارهایی که برای مقایسه عملکرد این دو الگوریتم به کار رفته­اند، معرفی شده ­اند.

مدل ریاضی مسئله

(شکل ‏۳‌.‌‌۱) زنجیره تأمین مورد مطالعه در این تحقیق را نمایش می­دهد. زنجیره تأمین فوق متشکل از چند تأمین­کننده، یک انبار و چند خرده­فروش است. هر تأمین­کننده یک نوع محصول را پشتیبانی می­ کند. انبار در این مدل یک انبار واسطه­ای (بارانداز) است.
انبار
شکل ‏۳‌.‌‌۱ شماتیک زنجیره تأمین مورد مطالعه.
پیش ­بینی تقاضای خرده­فروش­ها برای  دوره در افق برنامه­ ریزی موجود است. این پیش ­بینی­ها می ­تواند از یکی از رویکردهای کیفی و یا کمی به دست آید.
در مقادیر سفارش و مقادیر کالای ارسالی محدودیت وجود ندارد. به تمامی تقاضاها در ابتدای دوره پاسخ داده می­ شود. تقاضاهایی که با کمبود مواجه می­شوند، در دوره­ های آتی پاسخ داده می­شوند(تقاضای پس­افت). هزینه نگهداری هر واحد کالا و هزینه کمبود هر واحد کالا در حالت تک هدفه معین است. هزینه حمل و نقل کالا از تأمین­کننده تا انبار و از انبار تا خرده­فروش شامل تخفیف کلی است که به فرم زیر فرموله می­گردد:
نرخ هزینه حمل و نقل
تعداد قسمت­ های تابع هزینه حمل و نقل
نقاط شکست