تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه-  …

تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه- …

به‌طور کلی متاهیوریستیک‌ها به عنوان تکنیک‌های پیشرفته‌ای مطرح هستند که در واقع از ترکیب تکنیک‌های سطوح پایین‌تر برای بررسی گسترده‌تر و در عین حال متمرکزتر فضای جستجو به‌دست آمده‌اند.
در سال‌های اخیر، کلمه متاهیوریستیک به تمام الگوریتم‌های مدرن و سطوح بالا اشاره می‌کند که از جمله آن‌ها می‌توان به الگوریتم‌های تکاملی، مانند زیر اشاره کرد:
الگوریتم ژنتیک[۱۴۱] (GA)،
الگوریتم انجماد تدریجی[۱۴۲] (SA)،
جستجوی ممنوع[۱۴۳] (TS)،
الگوریتم کلونی مورچگان[۱۴۴] (ACO)،
شبکه های عصبی مصنوعی[۱۴۵](NN)،
یکی از معروفترین و کاراترین این رویکردها الگوریتم هایی است که با الگو برداری از تکامل ژنتیکی، الگوهایی برای حل مسئله ارائه می کنند و به همین دلیل به الگوریتم ژنتیک نیز معروف شده اند. این الگوریتم ها یک روش جستجوی موثر در فضاهای بسیار بزرگ و وسیع ایجاد می کنند که در نهایت منجر به جهت گیری به سمت یافتن جواب بهینه می گردد. ایده اصلی الگوریتم های تکاملی در سال ۱۹۶۰ توسط ریچنبرگ مطرح گردید و الگوریتم ژنتیک که منشعب از این الگوریتم هاست در حقیقت روش جستجوی کامپیوتری بر پایه الگوریتم های بهینه سازی و براساس ساختار ژن و کروموزوم هاست که توسط پرفسور هالند در دانشگاه میشیگان مطرح شد و توسط جمعی از دانشجویان چون گلدبرگ توسعه یافت(تبریزی و زندیه, ۱۳۹۰)
ﺳﺎﺑﻘﻪ ﻣﻄﺎﻟﻌﺎﺕ ﺩﺭ ﺯﻣﻴﻨﻪ ﮐﺎﺭﺑﺮﺩ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺩﺭ ﻣﺴﺎﺋﻞ ﺯﻣﺎﻥﺑﻨﺪی
‫ﺩﺭ ﺣﺎﻟﺖ ﮐﻠﻲ، ﻣﺴﺎﺋﻞ ﺯﻣﺎﻥﺑﻨﺪی ﺩﺭ ﺭﺩﻩ NP-Hardﻗﺮﺍﺭ ﺩﺍﺭﻧﺪ. ﻳﻌﻨﻲ ﻫﻴﭻ ﺍﻟﮕﻮﺭﻳﺘﻤﻲ ﺷﻨﺎﺧﺘﻪ ﻧﺸﺪﻩ ﮐﻪ ‫ﺑﺘﻮﺍﻧﺪ ﺟﻮﺍﺏ ﺑﻬﻴﻨﻪ ﺭﺍ ﺩﺭ ﺯﻣﺎﻥ ﭼﻨﺪ ﺟﻤﻠﻪﺍی[۱۴۶] ﭘﻴﺪﺍ ﮐﻨﺪ. ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻳﻲ ﻭﺟﻮﺩ ﺩﺍﺭﻧـﺪ ﮐـﻪ ﺑﺘﻮﺍﻧﻨـﺪ ﺟـﻮﺍﺏ ‫ﺩﻗﻴﻖ ﺭﺍ ﺑﺮﺍی ﻓﺮﻡﻫﺎی ﺧﺎﺻﻲ ﺍﺯ ﺍﻳﻦ ﻧﻮﻉ ﻣﺴﺌﻠﻪ ﺑﻴﺎﺑﻨﺪ، ﻭﻟﻲ ﺑﺎ ﺍﻓﺰﺍﻳﺶ ﺍﺑﻌﺎﺩ ﻣﺴﺌﻠﻪ ﻭ ﺍﺿﺎﻓﻪ ﮐﺮﺩﻥ ﻗﻴﻮﺩ ﺍﻳﻦ ‫ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎ ﮐﺎﺭﺍﻳﻲ ﺧـﻮﺩ ﺭﺍ ﺍﺯ ﺩﺳـﺖ ﺧﻮﺍﻫﻨـﺪ ﺩﺍﺩ.
‫ﺩﻭ ﺭﻭﻳﮑﺮﺩ ﺑﺮﺍی ﺣﻞ ﻣﺴـﺎﺋﻞ ﺯﻣـﺎﻥﺑﻨـﺪی ﭘـﺮﻭﮊﻩ ﺍﺳـﺘﻔﺎﺩﻩ ﺷـﺪﻩ ﺍﺳـﺖ: ﺭﻭﺵﻫـﺎی ﺩﻗــﻴﻖ[۱۴۷] ﻭ ﺭﻭﺵﻫـﺎی ابتکاری[۱۴۸] .
‫ﺍﺯ ﺟﻤﻠﻪ ﺭﻭﺵﻫﺎ ﮐﺎﻭﺷﻲ ﺭﻭﺵﻫﺎی ﻓﺮﺍﮐﺎﻭﺷﻲ[۱۴۹] ﻣﻲﺑﺎﺷﻨﺪ. ﻓـﺮﺍﮐﺎﻭﺷﻲﻫـﺎ ﮐﻼﺳـﻴﮏ ﺷـﺎﻣﻞ ﺍﻧﺠﻤـﺎﺩ ‫ﺗﺪﺭﻳﺠﻲ[۱۵۰]، ﺟﺴﺘﺠﻮ ﻣﻤﻨﻮﻉ[۱۵۱]، ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﻭ ﺑﻬـﻴﻨﻪ ﺳـﺎﺯی ﮐﻠـﻮﻧﻲ ﻣﻮﺭﭼﮕـﺎﻥ[۱۵۲] ﻣـﻲﺑﺎﺷـﻨﺪ. ﺩﺭ ﺍﻳـﻦ ‫ﺭﻭﺵﻫﺎ ﻫﻴﭻ ﮔﻮﻧﻪ ﺗﻀﻤﻴﻨﻲ ﺑﺮﺍی ﺭﺳﻴﺪﻥ ﺑﻪ ﺑﻬﺘﺮﻳﻦ ﺟﻮﺍﺏ ﻭﺟﻮﺩ ﻧﺪﺍﺭﺩ. ﺩﺭ ﻋﻮﺽ ﻗﺎﺑﻠﻴﺖ ﻣﺪﻝ ﺷـﺪﻥ ﺑـﺎ ‫ﺍﻧﻮﺍﻉ ﺷﺮﺍﻳﻂ ﻭ ﻗﻴﻮﺩ ﺭﺍ ﺩﺍﺭﻧﺪ ﻭ ﺩﺭ ﺯﻣﺎﻥﻫﺎ ﺑﺴﻴﺎﺭ ﺳـﺮﻳﻊ (ﺩﺭ ﻣﻘﺎﻳﺴـﻪ ﺑـﺎ ﺭﻭﺷـﻬﺎ ﺩﻗﻴـﻖ) ﻣـﻲﺗﻮﺍﻧﻨـﺪ ﺑـﻪ ﺟﻮﺍﺏﻫﺎ ﻣﻄﻠﻮﺑﻲ[۱۵۳] ﺩﺳﺖ ﻳﺎﺑﻨﺪ. ﺑﺎﺭ ﺩﻳﮕﺮ ﺗﺄﮐﻴﺪ ﻣﻲﺷﻮﺩ ﮐـﻪ ﺟـﻮﺍﺏ ﺍﻟﮕـﻮﺭﻳﺘﻢﻫـﺎ ﻓﺮﺍﮐﺎﻭﺷـﻲ ﻟﺰﻭﻣـاً ‫ﺑﻬﺘﺮﻳﻦ ﺟﻮﺍﺏ ﻧﻴﺴﺖ.
‫ﺩﺭ ﺍﻳﻦ ﺗﺤﻘﻴﻖ ﺑﻪ ﺩﻟﻴﻞ ﺍﺳﺘﻔﺎﺩﻩ ﺍﺯ ﺭﻭﺵ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺑﻪ ﻣﺮﻭﺭ ﺑﺮ ﻣﻨﺎﺑﻊ ﺩﺭ ﺍﻳﻦ ﺣﻴﻄـﻪ ﻣـﻲﭘـﺮﺩﺍﺯﻳﻢ.
‫ پورتمن[۱۵۴] (۲۰۰۸) ﻳﮏ ﺧﻼﺻﻪ ﮐﻮﺗﺎﻩ ﺩﺭﺑﺎﺭﻩ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺩﺭ ﻣﺤﻴﻂ ﺯﻣﺎﻥﺑﻨﺪی ﻫـﻤﺮﺍﻩ ﺑـﺎ ﺗﺤﻠﻴـﻞ ‫ﺍﺛﺮﺍﺕ ﺍﭘﺮﺍﺗﻮﺭﻫﺎ ﮔﻮﻧﺎﮔﻮﻥ ﻣﺎﻧﻨﺪ ﺭﻣﺰﮔﺬﺍﺭ ، ﺗﻘﺎﻃﻊ ﻭ ﺟﻬـﺶ ﺭﺍ ﺍﺭﺍﺋﻪ ﮐﺮﺩ. هارتمن[۱۵۵] (۱۹۹۸) یک ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺑﺎ ﺭﻣﺰﮔﺬﺍﺭ ﺑـﺮ ﭘﺎﻳـﻪ ﻭﻗــﻔﻪ ﺭﺍ ﺗﻮﺳـﻌﻪ ﺩﺍﺩ ﻭ ﺑﺮﻧﺎﻣـﻪ ﺯﻣـﺎﻧﻲ ‫ﺧﻮﺩ ﺗﻄﺒﻴﻘﻲ ﺭﺍ ﮐﻪ ﺑﻪ ﻃﻮﺭ ﺧﻮﺩﮐﺎﺭ ﺑﻬـﺘﺮﻳﻦ ﺭﻭﺵ ﺭﻣﺰ ﮔﺸﺎﻳﻲ ﺑﺮﻧﺎﻣﻪﻫﺎی ﺯﻣـﺎﻧﻲ ﺭﺍ ﺑـﻪ ﺩﺳـﺖ ﻣـﻲﺁﻭﺭﺩ، ‫ﺍﺭﺍﺋﻪ ﺩﺍﺩ. ﻭی ﻫﻤﭽﻨﻴﻦ ﺩﺭ ﺳﺎﻝ ۲٠٠۱ ﻣﺪﻝ ﺧﻮﺩ ﺭﺍ ﮔﺴﺘﺮﺵ ﺩﺍﺩ ﻭ ﺍﺯ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺑـﺮﺍی ﺯﻣـﺎﻥﺑﻨـﺪی ‫ﭘﺮﻭﮊﻩ ﺩﺭ ﺣﺎﻟﺖ ﭼﻨﺪ مده ﺍﺳﺘﻔﺎﺩﻩ ﮐﺮﺩ. ‫آلکاراز و ماروتو [۱۵۶](۲۰۰۱) ﺍﺯ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺑﺮﺍی ﺯﻣﺎﻥﺑﻨﺪی ﭘﺮﻭﮊﻩ ﺩﺭ ﺣﺎﻟﺖ ﭼﻨﺪ مده ﺍﺳﺘﻔﺎﺩﻩ ﮐﺮﺩﻧﺪ ﻭ ﮊﻥ ﺯﻣﺎﻥﺑﻨﺪ ﭘﻴﺸﺮﻭ-ﭘﺴﺮﻭ ﻫﻢ ﺩﺭ ﺑﺎﺯﻧﻤـﺎﻳﻲ ﮐﺮﻭﻣـﻮﺯﻭﻡ ﺩﺭ ﻧﻈـﺮ ﮔﺮﻓﺘﻨـﺪ. ﺁﻧﻬـﺎ ﺑـﻪ ﺍﻳـﻦ ﻧﺘﻴﺠـﻪ ‫ﺭﺳﻴﺪﻧﺪ ﮐﻪ ﺑﺎ ﺩﺭ ﻧﻈﺮ ﮔﺮﻓﺘﻦ ﺯﻣﺎﻥ ﭘﺴﺮﻭ ﮐﺎﺭﺍﻳﻲ ﺍﻟﮕﻮﺭﻳﺘﻢ ﺩﺭ ﺭﺳﻴﺪﻥ ﺑـﻪ ﻫـﺪﻑ ﻣـﺪﻝ ﮐـﻪ ﻫﻤﺎﻧـﺎ ﻣﻴﻴﻨـﻴﻢ ‫ﮐﺮﺩﻥ ﺯﻣﺎﻥ ﭘﺮﻭﮊﻩ ﺍﺳﺖ، ﺍﻓﺰﺍﻳﺶ ﻣﻲﻳﺎﺑﺪ. یاسینه و همکاران[۱۵۷] (۲۰۰۷)ﻳﮏ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﻓـﻨﻲ (CGA) ﺭﺍ ﺑـﺎ ﺍﺳـﺘﺮﺍﺗﮋی ﺟﺴـﺘﺠﻮی ﻣﺤﻠـﻲ ﭘﻴﻮﻧـﺪ ‫ﺯﺩﻧﺪ. ﺗﺎﺑﻊ ﻫـﺪﻑ ﺍﺳﺘﻔﺎﺩﻩ ﺷﺪﻩ، ﺗﺄﺧﻴﺮ ﭘﺮﻭﮊﻩ ﮐﻠﻲ ﺍﺳﺖ. ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﺍﺭﺍﺋﻪ ﺷﺪﻩ ﺑﺎ ﻣﺴﺎﺋﻞ ﺯﻣﺎﻥﺑﻨﺪی ‫ﺳﺎﺩﻩ ﺗﻮﻟﻴﺪ ﺷﺪﻩ ﺑﺮ ﺍﺳﺎﺱ ﺩﻭ ﻣﻌـﻴﺎﺭ ‪ AUFﻭ ARLFﺁﺯﻣﻮﻥ ﺷﺪﻩ ﺍﺳﺖ. روکا و همکاران[۱۵۸] (۲۰۰۸)ﺩﺭ ﺗﺤﻘﻴﻖ ﺧﻮﺩ ﺍﺯ ﺍﻟﮕﻮﺭﻳﺘﻢ ﮊﻧﺘﻴﮏ ﭼﻨﺪﻫﺪﻓﻪ MOGAﺑﺮﺍی ﺯﻣﺎﻥﺑﻨﺪی ﭘـﺮﻭﮊﻩ ﺑـﺎ ‫ﻣﺤﺪﻭﺩﻳﺖ ﻣﻨﺎﺑﻊ ﺍﺳﺘﻔﺎﺩﻩ ﮐﺮﺩﻧﺪ. ﺍﻫﺪﺍﻑ ﻣﺪﻝ ﻣﻴﻨﻴﻤﻢ ﮐﺮﺩﻥ ﺯﻣﺎﻥ ﭘﺮﻭﮊﻩ ﻭ ﺗﺴﻄﻴﺢ ﻣﻨﺎﺑﻊ ﺑﻮﺩ.
الگوریتم ژنتیک یک روش جستجوی توسعه یافته توسط هلند[۱۵۹] (۱۹۷۵) می باشد که برای نخستین بار در سال ۱۹۷۵ ارائه گردید و بر مبنای مکانیسم طبیعی و تولید مثل، جهت یک جستجوی تصادفی ولی جهت دار از میان فضای تصمیم گیری، برای یافتن راه حل بهینه استوار است. کاربرد روش الگوریتم ژنتیک مانند هر روش بهینه سازی، با مشخص نمودن متغییرهای بهینه سازی، تابع هدف و محدودیت ها، اطلاعات ورودی و پارامترهای مدل شروع می شود. الگوریتم ژنتیک با آزمون همگرائی به شیوه های متفاوت از سایر روشهای بهینه سازی به پایان می رسد .
 
جمع بندی
در این فصل سعی بر آن شد مفاهیم، اصول و مبانی اولیه زمانبندی پروژه و تعاریفی از زیر ساخت های پروژه مطرح گردد. در ادامه مسئله تسطیح منابع و تعریفی از آن آورده شد و پیشینه تحقیقات گذشته نیز ارائه گردید. با توجه به روش تحقیق به معرفی و تعریف روش های حل مسائل برنامه زمانبندی اشاره گردید. از آنجا که روش حل در این تحقیق فراابتکاری است به معرفی این روش حل در مسائل NP-HARD پرداخته شد. از جمله الگوریتم های فراابتکاری و بکار گرفته شده در این تحقیق الگوریتم ژنتیک می باشد که در این فصل توضیح داده شد.
به طور کلی در این تحقیق با توجه به فصل اول به بررسی و حل مسئله تسطیح منابع پروژه با در نظر گرفتن زمان و هزینه پرداخته می شود که در این فصل به ادبیات موضوع و بیان پیشینه تحقیق در حل مسائل چندگانه و انواع روش های حل و در نهایت به بیان الگوریتم ها و مولفه های الگوریتم مورد نظر و بکار رفته شده در طول این تحقیق پرداخته شد.

فصل سوم

روش تحقیق

 
مقدمه
در این فصل به شرح و بسط هدف اصلی این پایان نامه پرداخته می شود. در گام اول به بیان و بررسی الگوریتمهای دقیق و فرا ابتکاری و خصوصیت هر یک می پردازیم در گام دوم الگوریتم ژنتیک را که در فصل قبل توضیح داده ایم را بعنوان روش حل مطرح کرده و دلایل استفاده و مزیت های این الگوریتم را عنوان می کنیم. سپس الگوریتم پیشرفته تر ژنتیک با عنوان NSGA-II مطرح می گردد.
در گام بعد مدل مورد نظر مطرح، پارامترهای آن مطرح می گردد و سپس به روش حل آن توسط الگوریتم ژنتیک می پردازیم.
 
الگوریتم های دقیق[۱۶۰]
جهت یافتن جواب های بهینه مورد استفاده قرار می گیرند اما در مواجه با مسائلی با اندازه های بزرگ و یا مسائلی با محدودیت های زیاد تقریبا غیر عملی هستند. روش های دقیق شامل دو گروه برنامه ریزی ریاضی و تکنیک های شمارشی می باشند.
تالبوت(۱۹۸۲) و پترسون و همکاران[۱۶۱] (۱۹۸۹) یک روش شمارش[۱۶۲] برای حل مدل پیشنهاد کردند. اسپرانز و درسیلس یک روش شاخه و حد[۱۶۳] ارائه نمودند اما هارتمن و اسپرچر[۱۶۴] (۱۹۹۶) نشان دادند که از این الگوریتم ممکن است در مواردی با بیش از یک منبع تجدید پذیر قادر به پیدا کردن جواب بهینه نباشند. اسپروچر و همکاران[۱۶۵](۱۹۹۸) هارتمن و درکسل[۱۶۶] (۱۹۹۸)و اسپرچر و درکسل (۱۹۹۷)الگوریتم شاخه و حد[۱۶۷] ارائه نمودند. ژو و همکاران یک روش شاخه و برش[۱۶۸]ارائه نمودند.
روش محدودیت اپسیلون[۱۶۹]
روش محدودیت اپسیلون یکی از رویکردهای شناخته شده برای مواجه با مسائل چندهدفه که باانتقال تمامی توابع هدف به جز یکی از آنها در هر مرحله به محدودیت به حل این نوع مسائل می پردازد
مرز پارتو می تواند با روش قید ε ایجاد شود. (Berube,Gendreau and Potvin,2009)
(۳-۱)
min f1(x)c
xϵX
(۳-۲)
f2(x)≤ε۱
f2(x)≤ε۲

fn(x)≤εn
گامهای روش ε-constraint به صورت زیر است:
۱-یکی از توابع هدف را به عنوان هدف اصلی انتخاب کنید.
۲-هر بار با توجه به یکی از توابع هدف، مسئله را حل کنید و مقادیر هر تابع هدف را بدست آورید.
۳-بازه بین دو مقدار بهینه توابع هدف فرعی را به تعداد از قبل مشخص تقسیم بندی کنید و یک جدول مقادیر برای ε۲,…, εبدست آورید.
۴-هر بار مسئله رابا تابع هدف اصلی با هر یک از مقادیر ε۲,…, εحل کنید.

برای دانلود متن کامل این فایل به سایت torsa.ir مراجعه نمایید.
برچسب گذاری شده با: , , , ,