برای به کار بردن عملگر جهش دو عدد تصادفی در بازه ۱تا (طول کروموزوم-۱) تولید شده و عناصر مرتبط در کروموزوم با یکدیگر تعویض می­گردند.

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

سایر ملاحظات

در این الگوریتم جمعیت آغازین به صورت تصادفی بین (۱، ۱- ) تولید می­ شود. برای در نظر گرفتن شرایط موجه بودن حالت تعمیر بر جواب آغازین اعمال می­گردد. در صورت تخطی از محدودیت­ها جریمه­ای به تابع هدف افزوده می­گردد.

الگوریتم بهینه­سازی ازدحام ذرات چندهدفه

روشPSO ﯾﮏ روش ﺳﺮاﺳﺮی ﺑﻬﯿﻨﻪ­ﺳﺎزی اﺳﺖ ﮐﻪ ﺑﺎ اﺳﺘﻔﺎده از آن ﻣﯽ­ﺗﻮان ﺑﺎ ﻣﺴﺎﺋﻠﯽ ﮐﻪ ﺟﻮاب آﻧﻬﺎ ﯾﮏ ﻧﻘﻄﻪ ﯾﺎ ﺳﻄﺢ در ﻓﻀﺎی n بعدی می­باشد، ﺑﺮﺧﻮرد ﻧﻤﻮد. در چنین ﻓﻀﺎﯾﯽ، ﻓﺮﺿﯿﺎﺗﯽ ﻣﻄﺮح ﻣﯽ­ﺷﻮد و یک سرعت اﺑﺘﺪاﯾﯽ ﺑﻪ ذرات اﺧﺘﺼﺎص داده ﻣﯽ­ﺷﻮد، ﻫﻤﭽﻨﯿﻦ ﮐﺎﻧﺎل­ﻫﺎی ارﺗﺒﺎﻃﯽ ﺑﯿﻦ ذرات در ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﻣﯽﺷﻮد. ﺳﭙﺲ اﯾﻦ ذرات در ﻓﻀﺎی ﭘﺎﺳﺦ ﺣﺮﮐﺖ کرده و ﻧﺘﺎﯾﺞ ﺣﺎﺻﻠﻪ ﺑﺮ ﻣﺒﻨﺎی ﯾﮏ «ﻣﻼک ﺷﺎﯾﺴﺘﮕﯽ» ﭘﺲ از ﻫﺮ ﺑﺎزه زﻣﺎﻧﯽ ﻣﺤﺎﺳﺒﻪ می­گردد. ﺑﺎ ﮔﺬﺷﺖ زﻣﺎن، ذرات ﺑﻪ ﺳﻤﺖ ذراﺗﯽ ﮐﻪ دارای ﻣﻼک ﺷﺎﯾﺴﺘﮕﯽ ﺑﺎﻻﺗﺮی ﻫﺴﺘﻨﺪ و در ﮔﺮوه ارﺗﺒﺎﻃﯽ ﯾﮑﺴﺎﻧﯽ ﻗﺮار دارﻧﺪ، ﺷﺘﺎب ﻣﯽﮔﯿﺮﻧﺪ. ﻣﺰﯾﺖ اﺻﻠﯽ اﯾﻦ روش ﺑﺮ اﺳﺘﺮاﺗﮋی­ﻫﺎی ﺑﻬﯿﻨﻪ­ﺳﺎزی دﯾﮕﺮ اﯾﻦ اﺳﺖ ﮐﻪ ﺗﻌﺪاد ﻓﺮاوان ذرات ازدﺣﺎم­ﮐﻨﻨﺪه، ﺑﺎﻋﺚ اﻧﻌﻄﺎف روش در ﺑﺮاﺑﺮ ﻣﺸﮑﻞ ﭘﺎﺳﺦ بهینه ﻣﺤﻠﯽ ﻣﯽ­ﮔﺮدد.
ﻫﺮ ذره دارای ﯾﮏ ﻣﻮﻗﻌﯿﺖ اﺳﺖ ﮐﻪ ﻣﺸﺨﺺ ﻣﯽﻧﻤﺎﯾﺪ ﻣﺨﺘﺼﺎت ذره در ﻓﻀﺎی ﺟﺴﺘﺠﻮی ﭼﻨﺪ ﺑﻌﺪی چیست. ﺑﺎ ﺣﺮﮐﺖ ذره در ﻃﻮل زﻣﺎن، ﻣﻮﻗﻌﯿﺖ ذره ﺗﻐﯿﯿﺮ ﻣﯽﻧﻤﺎﯾﺪ.  موقعیت ذره i ام در زمان  ام را ﻣﺸﺨﺺ ﻣﯽﻧﻤﺎﯾﺪ. ﻫﻤﭽﻨﯿﻦ ﻫﺮ ذره ﺑﺮای ﺣﺮﮐﺖ در ﻓﻀﺎ ﻧﯿﺎز ﺑﻪ ﯾﮏ ﺳﺮﻋﺖ دارد.  سرعت ذره  ام در زمان  ام را مشخص می­نماید. ﺑﺎ اﻓﺰودن ﺳﺮﻋﺖ ﺑﻪ ﻣﻮﻗﻌﯿﺖ ﻫﺮ ذره، ﻣﯽ­ﺗﻮان ﻣﻮﻗﻌﯿﺖ ﺟﺪﯾﺪی ﺑﺮای ذره در ﻧﻈﺮ ﮔﺮﻓﺖ. ﻣﻌﺎدﻟﻪ ﺑﻪ روز ﻧﻤﻮدن ﻣﻮﻗﻌﯿﺖ ذره به صورت زیر است:.

اﯾﻨﮑﻪ ﻣﻮﻗﻌﯿﺖ ﯾﮏ ذره در ﻓﻀﺎی ﺟﺴﺘﺠﻮ ﻣﻮﻗﻌﯿﺖ ﻣﻨﺎﺳﺒﯽ اﺳﺖ ﯾﺎ ﺧﯿﺮ ﺗﻮﺳﻂ ﯾﮏ ﺗﺎﺑﻊ ﺷﺎﯾﺴﺘﮕﯽ ارزﯾﺎﺑﯽ ﻣﯽﮔﺮدد. ذرات ﺗﻮاﻧﺎﯾﯽ اﯾﻦ را دارﻧﺪ ﮐﻪ ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺘﯽ را ﮐﻪ در ﻃﻮل ﺣﯿﺎت ﺧﻮد در آن ﻗﺮار داﺷﺘﻪاﻧﺪ ﺑﻪ ﺧﺎﻃﺮ ﺑﺴﭙﺎرﻧﺪ. ﺑﻪ ﺑﻬﺘﺮﯾﻦ ﺗﺠﺮﺑﻪ ﻓﺮدی ﯾﮏ ذره ﯾﺎ ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺖ ﻣﻼﻗﺎت ﺷﺪه ﺗﻮﺳﻂ ذره pbest ﮔﻔﺘﻪ ﻣﯽﺷﻮد. ذرات ﻣﯽﺗﻮاﻧﻨﺪ از ﺑﻬﺘﺮﯾﻦ ﻣﻮﻗﻌﯿﺖ ﻣﻼﻗﺎت ﺷﺪه ﺗﻮﺳﻂ ﮐﻞ ﮔﺮوه ﻧﯿﺰ آﮔﺎﻫﯽ داﺷﺘﻪ ﺑﺎﺷﻨﺪ ﮐﻪ اﯾﻦ ﻣﻮﻗﻌﯿﺖ gbest ﻧﺎﻣﯿﺪه ﻣﯽﺷﻮد. ﺑﺮدار ﺳﺮﻋﺖ ذره در ﻓﺮآﯾﻨﺪ ﺑﻬﯿﻨﻪ­ﺳﺎزی ﻣﻨﻌﮑﺲ­ﮐﻨﻨﺪه داﻧﺶ ﺗﺠﺮﺑﯽ ذره و اﻃﻼﻋﺎت ﺟﺎﻣﻌﻪ ذرات اﺳﺖ. ﻫﺮ ذره ﺑﺮای ﺣﺮﮐﺖ در ﻓﻀﺎی ﺟﺴﺘﺠﻮ دو ﻣﻮﻟﻔﻪ را ﻣﺪ ﻧﻈﺮ دارد:
ﻣﺆﻟﻔﻪ ﺷﻨﺎﺧﺘﯽ^[۹۰]: ﺑﻬﺘﺮﯾﻦ راه ﺣﻠﯽ اﺳﺖ ﮐﻪ ﯾﮏ ذره ﺑﻪ ﺗﻨﻬﺎﯾﯽ ﺑﺪﺳﺖ ﻣﯽآورد.
ﻣﺆﻟﻔﻪ اﺟﺘﻤﺎﻋﯽ^[۹۱]: ﺑﻬﺘﺮﯾﻦ راه ﺣﻠﯽ اﺳﺖ ﮐﻪ ﺗﻮﺳﻂ ﮐﻞ ﮔﺮوه ﺗﺸﺨﯿﺺ داده می­ شود.
ﭘﺎراﻣﺘﺮﻫﺎی زﯾﺎدی ﻫﺴﺘﻨﺪ ﮐﻪ ﺑﺮ روی اﻟﮕﻮرﯾﺘﻢ PSO ﺗأﺛﯿﺮ ﻣﯽ­ﮔﺬراﻧﺪ. ﺑﻪ ﻋﻨﻮان ﻣﺜﺎل ﺗﻌﺪاد ذرات، اﺑﻌﺎد ﻣﺴﺎﻟﻪ، وزن اﯾﻨﺮﺳﯽ، اﻧﺪازه ﻫﻤﺴﺎﯾﻪﻫﺎ، ﺗﻌﺪاد ﺗﮑﺮارﻫﺎی اﻟﮕﻮرﯾﺘﻢ، ﺿﺮاﯾﺐ ﺛﺎﺑﺖ ﻣﻮﻟﻔﻪﻫﺎی اﺟﺘﻤﺎﻋﯽ و ﻣﻮﻟﻔﻪﻫﺎی ﺷﻨﺎﺧﺘﯽ و ﻣﺎﮐﺰﯾﻤﻢ ﺳﺮﻋﺖ ﯾﮏ ذره.

اﻧﺪازه گروه^[۹۲]

ﻫﺮﮔﺎه ﺗﻌﺪاد ذرات زﯾﺎد ﺑﺎﺷﺪ و ذرات در ﻓﻀﺎی ﺟﺴﺘﺠﻮ ﺑﻪ ﻃﻮر ﯾﮑﻨﻮاﺧﺖ ﺗﻮزﯾﻊ ﺷﺪه ﺑﺎﺷﻨﺪ، ﺗﻨﻮع در ﺑﯿﻦ ذرات زﯾﺎد ﺷﺪه و اﻟﮕﻮرﯾﺘﻢ راﻧﺪﻣﺎن ﺑﺎﻻﺗﺮی ﻣﯽ­ﯾﺎﺑﺪ. اﻟﺒﺘﻪ ﺑﺎﯾﺪ ﺗﻮﺟﻪ ﺷﻮد ﮐﻪ ﺗﻌﺪاد زﯾﺎد ذرات و ﭘﯿﭽﯿﺪﮔﯽ اﻟﮕﻮرﯾﺘﻢ ارﺗﺒﺎط ﻣﺴﺘﻘﯿﻢ دارﻧﺪ. ﻫﺮﭼﻨﺪ ﮐﻪ ﻧﺴﺒﺖ زﻣﺎﻧﯿﮑﻪ ﺗﻌﺪاد ذرات ﮐﻢ اﺳﺖ، ﺗﻌﺪاد ﺗﮑﺮارﻫﺎی اﻟﮕﻮرﯾﺘﻢ ﮐﻤﺘﺮ اﺳﺖ و زﻣﺎن رﺳﯿﺪن ﺑﻪ ﭘﺎﺳﺦ ﺑﻬﯿﻨﻪ ﮐﻤﺘﺮ اﺳﺖ [۳۹]. ﻣﻘﺪار ﻣﻨﺎﺳﺐ ذرات ﺑﻪ ﻣﺴئله ﺑﺴﺘﮕﯽ دارد. در این مطالعه مقدار مناسب اندازه گروه از طریق فرایند تنظیم پارامترهای الگوریتم به روش تاگوچی به دست آمده است.

اﻧﺪازه ﻫﻤﺴﺎﯾﮕﯽ^[۹۳]

اﻧﺪازه ﻫﻤﺴﺎﯾﻪ ﺗأﺛﯿﺮ زﯾﺎدی در ﺗﻌﺎﻣﻞ ﺑﯿﻦ ذرات دارد. ﺳﺎﯾﺰ ﻫﻤﺴﺎﯾﮕﯽ ﮐﻢ، ﺗﻌﺎﻣﻞ ﺑﯿﻦ ذرات را ﮐﺎﻫﺶ ﻣﯽدﻫﺪ و ﻧﺮخ ﻫﻤ­ﮕﺮاﯾﯽ در اﯾﻦ روش ﮐﻢ خواهد بود. همچنین، اﻣﮑﺎن ﻗﺮارﮔﺮﻓﺘﻦ ذره در ﻣﯿﻨﯿﻤﻢ ﻣﺤﻠﯽ ﮐﺎﻫﺶ ﻣﯽ­­یابد. در این مطالعه مقدار مناسب اندازه همسایگی از طریق فرایند تنظیم پارامترهای الگوریتم به روش تاگوچی به دست آمده است. ﺟﻬﺖ اﺳﺘﻔﺎده از ﻓﻮاﯾﺪ ﻫﻤﺴﺎﯾﮕﯽ ﺑﺰرگ و ﮐﻮﭼﮏ، در اﺑﺘﺪا اﻧﺪازه ﻫﻤﺴﺎﯾﮕﯽ ﮐﻮﭼﮏ و ﺳﭙﺲ ﺑﺰرگ در ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﻣﯽ­ﺷﻮد. به همین منظور بعد از هر تکرار مقدار اندازه همسایگی در عدد ۹۹/۰ ضرب شده است.

ﺿﺮاﯾﺐ ﺳﺮﻋﺖ^[۹۴]

،  و ضرایب  و  در ﻣﻮﻟﻔﻪﻫﺎی اﺟﺘﻤﺎﻋﯽ و ﺷﻨﺎﺧﺘﯽ ﺳﺮﻋﺖ ذره، ﻧﻘﺶ ﺑﺴﯿﺎر زﯾﺎدی در راﻧﺪﻣﺎن ذره دارﻧﺪ. اگر  ﺑﺎﺷﺪ، ذرات ﻓﻘﻂ ﺑﺎ ﺳﺮﻋﺖ ﺧﺎﺻﯽ ﺑﺪون ﻫﺪف در ﻓﻀﺎ ﺣﺮﮐﺖ ﻣﯽ­ﻧﻤﺎﯾﻨﺪ و آﻧﻘﺪر ﺣﺮﮐﺖ ﻣﯽ­ﻧﻤﺎﯾﺪ ﺗﺎ ﺑﻪ ﻣﺮز ﻓﻀﺎی ﺟﺴﺘﺠﻮ برسند. اگر  و  باشد، ذرات ﻓﻘﻂ ﺑﻪ ﺗﺠﺮﺑﻪ ﻓﺮدی ﺧﻮد ﺗﻮﺟﻪ ﻣﯽ­ﻧﻤﺎﯾﺪ. اﮔﺮ  و  ﺑﺎﺷﺪ، ذرات ﻓﻘﻂ ﺑﻪ ﺑﻬﺘﺮﯾﻦ ﻓﺮد ﮔﺮوه ﺗﻮﺟﻪ می­نمایند. ﻣﻌﻤﻮﻻً در ﺑﺴﯿﺎری از الگوریتم­ها  و  را ﺛﺎﺑﺖ در ﻧﻈﺮ می­گیرند. مقدار مناسب این ضرایب، از طریق فرایند تنظیم پارامترهای الگوریتم به روش تاگوچی به دست آمده است.

سایر ملاحظات

در این الگوریتم برای تبدیل حالت گسسته مسئله به یک مسئله پیوسته، جمعیت آغازین به صورت تصادفی بین ۵/۱ و ۵/۱- تولید می­ شود. برای در نظر گرفتن شرایط موجه بودن حالت تعمیر به صورت بازه­ای بر جواب آغازین اعمال می­گردد. در صورت تخطی از محدودیت­ها جریمه برای هر یک در نظر گرفته شده است. همچنین برای تنوع بخشیدن به الگوریتم، از عملگر جهش استفاده شده است.

مقایسه الگوریتم­ها

برای ارزیابی عملکرد روش­های حل استفاده شده، نتایج NSGAΙΙ و MOPSO مقایسه شده ­اند. یکی از راهکارهایی که مقایسه الگوریتم­ها را منطقی­تر می­سازد، اجرای دو الگوریتم در زمان­های مساوی است. به همین منظور، دو الگوریتم برای سه دسته مسائل کوچک، متوسط و بزرگ در زمان­های تقریبی یکسان اجرا شده و نتایج با بهره گرفتن از معیارهای زیر مقایسه گردید.

معیار میانگین فاصله از نقطه ایده­آل ^[۹۵]

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

معیار بیشترین گسترش^[۹۶]

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

در واقع این معیار قطر مستطیلی است که از تقاطع دو نقطه ابتدا و انتهای جبهه پارتو بدست می ­آید.

معیار یکنواختی^[۹۷]

معیاری برای نشان دادن نحوه توزیع جواب­های پارتو که توسط اسکات^[۹۸] معرفی شد. اگر این معیار کوچک باشد، جواب­ها به طور یکنواخت­تری توزیع شده ­اند. پس الگوریتمی که معیار یکنواختی کمتری داشته باشد، بهتر است و از فرمول زیر قابل محاسبه است:

: فاصله اقلیدسی بین دو جواب پارتو است.
: میانگین تمام فواصل.

معیار تعداد جواب های آرشیو پارتو

اگر تنوع و نحوه توزیع جواب­های پارتو مد نظر نباشد، بیشتر بودن تعداد جواب­ها در جبهه پارتو را می­توان به عنوان معیار برتری یک الگوریتم در نظر گرفت.

معیار پوشش مجموعه^[۹۹]

این معیار برابر است با سهم هر الگوریتم در مجموعه نامغلوب حاصل از جواب­های پارتو دو الگوریتم که مطابق رابطه زیر بدست می ­آید:

تجزیه و تحلیل داده ­ها و آزمون فرضیات

مقدمه

برای بررسی عملکرد و مقایسه کارایی الگوریتم­های پیشنهادی، با توجه به عدم دسترسی به داده ­های واقعی، لازم است ابتدا چندین مسئله با ابعاد متفاوت تولید شود. نحوه تولید مسائل در بخش ۲٫۴ تشریح شده است. سپس در بخش ۳٫۴ پارامترهای مربوط به الگوریتم­های حل پیشنهادی تنظیم می­گردد. هر یک از الگوریتم­ها برای مسائل تولید شده اجرا و نتایج در بخش ۴٫۴ ارائه شده است. برای تجزیه و تحلیل نتایج حاصل از اجرای الگوریتم­ها بر اساس معیارهای معرفی شده در فصل ۳، فرضیاتی مطرح می­شوند که این فرضیات در بخش ۵٫۴ مورد آزمون قرار می­گیرند.
شایان ذکر است تمامی الگوریتم­ها با بهره گرفتن از نرم­افزار Matlab نسخه ۷٫۱۲٫۰ (R2011a) کدنویسی و بر روی سیستمی با مشخصات زیر اجرا شده ­اند:
CPU: Intel® Pentium® P6200
RAM: 2 GB

نحوه تولید داده ­ها

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

تولید مسئله

در مدل کنترل موجودی مسئله SWMR مطرح شده در این تحقیق، ابعاد مسئله در ارتباط با تعداد خرده­فروش­ها (  )، تعداد تأمین­کنندگان (  ) و تعداد دوره­ های افق برنامه­ ریزی (  ) تعیین می­گردد. به منظور بررسی عملکرد الگوریتم­ها در مسائل با ابعاد مختلف سه دسته کلی از مسائل شامل ابعاد کوچک، متوسط و بزرگ مطابق (جدول ‏۴‌.‌۱) تولید شده است.
جدول ‏۴‌.‌۱ دسته بندی مسائل نمونه.