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

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

نخبه گرائی را می توان به معنای حفظ و نگهداری اعضای خوب جمعیت و انتقال مستقیم آن ها از نسلی به نسل دیگر تعریف نمود.
در مسائل بهینه سازی تک هدفه، اعمال نخبه گرائی از طریق روشهای مختلفی صورت می پذیرد. در ساده ترین روش، فرزندان حاصل از عملگرهای آمیزش و جهش با والدین خود مقایسه شده و از میان چهارمروموزوم موجود، دو عضو که بالاترین برازندگی را دارا هستند برای انتقال به نسل بعد انتخاب می شوند. بدین ترتیب، والدین هم فرصت رقابت با فرزندان به نسل بعد انتخاب می شوند. بدین ترتیب، والدین هم فرصت رقابت با فرزندان برای انتقال به نسل بعد را خواهند داشت. با پیروی از این مفهوم و در حالت عمومی، نخبه گرائی را می توان با انتخاب اعضای نسل بعد، از مجموعه ای متشکل از تلفیق جمعیت والد و فرزند اعمال کرد.
در بعضی الگوریتم های MOGA نخبه گرا، از حفظ جواب های غیرمغلوب به عنوان استراتژی نخبه گرائی بهره گرفته می شود. این عمل با ایجاد یک جمعیت خارجی ممکن می گردد. در سال ۱۹۹۸ Parks&Miller الگوریتمی را پیشنهاد کردند که از یک جمعیت خارجی برای حفظ پاسخ های غیر مغلوب استفاده می کرد. در این الگوریتم، جمعیت مورد نظر محدود بوده و یک راه حل جدید تنها در صورتی می تواند وارد آن شود که به طور قانع کننده ای با جواب های موجود متفاوت باشد.
در همین سال (۱۹۹۸)، تحقیقات Zitzler & Thiele منجر به ارائه الگوریتم [۱۱۲]SPGA گردید. این الگوریتم از دو جهت جمعیت مجزا در روند بهینه سازی بهره می گیرید: (۱) جمعیت خارجی (آرشیو) که محدود بوده و جهت ذخیره ی جواب های غیر مغلوب که در گذشته حاصل شده اند مورد استفاده قرار می گیرد. و(۲) جمعیت داخلی که در الگوریتم ژنتیک بکار می رود و با تکرار نسل ها به سمت کامل حرکت می کند. با بدست آمدن یک جواب غیرمغلوب جدید در جمعیت داخلی، جواب هائی از جمعیت خارجی که جواب غیرمغلوب جدید بر آن ها چیره می شود از آن جمعیت حذف شده و جواب جدید وارد آن می گردد. همچنین، تعدادی از جواب ها نیز به صورت دسته ای و به منظور حصول اطمینان از محدود بودن جمعیت خارجی از آرشیو خارج می شوند.
در الگوریتم SPGA، جمعیت داخلی جدید با انتخاب از درون مجموعه ای که حاصل ترکیب دو جمعیت داخلی و خارجی قبلی است تعیین می شود. لذا جمعیت خارجی در تعامل با جمعیت خارجی خواهد بود. بدین ترتیب که، به هر عضو از جمعیت خارجی و بر اساس تعداد جواب هائی از جمعیت داخلی که جواب مذکور می تواند بر آنها چیره شود، یک توانائی[۱۱۳] نسبت داده می شود. سپس به هر کدام از اعضای مجموعه داخلی یک عدد تقریبی برازندگی بر اساس مجموع توانائی های جواب های خارجی چیره شوند بر آن، نسبت داده می شود.
تاکنون موارد متعددی از الگوریتم های MOEA با پایبندی به اصول اولیه این روش ولی با تغییرات کوچکی در نحوه نسبت دادن مقادیر برازندگی، نحوه انتخاب از جمعیت و روش های مختلف در راستای حفظ پراکندگی پیشنهاد گردیده است. از آن جمله به الگوریتم های PAES،PESA اشاره نمود که هدف اصلی آن ها، ایجاد تغییراتی در ساختار این الگوریتم ها در جهت حفظ پراکندگی و محدود کردن فضای هدف می باشد.
الگوریتم ژنتیک نخبه گرا بر پایه مرتب سازی غیر مغلوب (NSGA-ll)
الگوریتم NSGA-ll توسط Deb و همکارانش در سال ۲۰۰۲ ارائه شد. در این الگوریتم علاوه بر راهبرد حفظ جواب های نخبه، از یک مکانیزم مجزا و برخورداری از پارامترهای مشترک کمتر، این الگوریتم تا حدود زیادی مشکلات مربوط به الگوریتم های تکاملی چند هدفه که بر مبنای مرتب سازی غیر مغلوب[۱۱۴] قرار دارند را مرتفع کرده است.
در الگوریتم NSGA-ll، ابتدا جمعیت فرزندان (Qt) با اعمالعملگرهای آمیزش و جهش بر روی اعضای جمعیت والدین(Pt) ایجاد می گردد. در این مرحله، بجای آنکه جبهه ی غیر مغلوب[۱۱۵] متعلق به Qt تعیین گردد، هر دو جمعیت والدین و فرزندان با یکدیگر ترکیب شده و جمعیت مختلط (Rt) را با اندازه ۲N تشکیل می دهد. سپس، روند مرتب سازی غیرمغلوب برای طبقه بندی کلیه اعضای متعلق به جمعیت Rt بکارگرفته می شود. اگرچه این فرایند نیاز به محاسبات بیشتری در مقایسه با اعمال مرتب سازی غیرمغلوب بر جمعیت Qt دارد، اما نتیجه ی آن، اجرای یک بررسی سراسری و جامع مابین جواب های والد و فرزند می باشد. روش پیشنهاد شده توسط Goldberg (شکل ۴-۲-الف) برای تعیین جبهه پارتو و انتساب مقدار برازندگی به هر یک از اعضا مورد استفاده قرار می گیرد.
انتخاب اعضای نسل بعد از میان مجموعه Rt
به محض اتمام عملیات مرتب سازی غیرمغلوب، اعضای جمعیت نسل جدید با انتقال جواب های موجود در جبهه های غیرمغلوب، یک به یک تعیین می شوند. عملیات انتقال از بهترین جبهه ی غیر مغلوب F1 (اولین جبهه ی غیر مغلوب) آغاز شده و به ترتیب، نوبت به اعضای جبهه ی دوم(F2)، سوم(F3) و… می رسد. از آنجا که تعداد اعضای Rt برابر ۲N می باشد، ممکن است در روند انتخاب N عضو برای نسل جدید، تمامی جبهه های بدست آمده در مرحله ی مرتب سازی، مورد استفاده قرار نگیرند. هنگامی که نوبت به آخرین جبهه مجاز می رسند، ممکن است تعداد اعضای موجود از تعداد ظرفیت خالی در نسل جدید بیشتر باشد. در الگوریتم NSGA-ll در عوض انتخاب تصادفی اعضا در این حالت، جواب های واقع در نواحی غیرشلوغ دارای ارجحیت در روند انتخاب هستند.
با گذشت چند نسل و به دلیل تکامل جواب ها، تعداد اعضای بهترین جبهه ی غیر مغلوب می تواند به N نزدیک و یا حتی بیشتر گردد. در نتیجه، انتخاب اعضای نسل بعد از میان جواب های موجود در مناطق غیر شلوغ، پراکندگی اعضا در مجموعه ی جدید را تضمین می نماید. برای تعیین تراکم جوابهای موجود در اطراف یک عضو مشخص (It) در جمعیت، از میانگین فاصله دو عضو در همسایگی (It) با توجه به هر یک از اهداف استفاده می شود. این فاصله، فاصله تراکم[۱۱۶] نامگذاری شده است.
شکل ۵-۲-محاسبه فاصله تراکم در یک مسئله دو هدفه
در شکل(۵-۲) چگونگی تعیین نقاط همسایگی ، مشخص شده است. با اندکی تامل می توان دریافت که برای هر پاسخ i، لزومی ندارد که نقاط همسایگی i-1 و i+1 در کلیه اهداف مورد نظر برای مسئله، نقاط یکسانی باشند؛ این موضوع، بیشتر در مسائلی با M≥۳ صادق می باشد. لازم به ذکر است که فاصله تراکم برای پاسخ های کرانه ای[۱۱۷] برابر ∞ در نظر گرفته می شود تا حداکثر شانس ممکن در نتخاب اعضای نسل بعد را دارا باشند. بدین ترتیب، بعد از محاسبه فاصله تراکم برای جواب های موجود در آخرین جبهه پارتوی مجاز و مرتب سازی آنها از بیشترین تا کمترین مقدار، جواب ها یک به یک و بر طبق لیست در ظرفیت های خالص اعضای نسل بعد قرار داده شده است تا تعداد اعضا، معادل N گردد. این روند به صورت شماتیک در شکل (۶-۲) نمایش داده شده است.
شکل ۶-۲-منطق به کاررفته در الگوریتم NSGA-II برای انتخاب اعضای نسل بعد
انتخاب اعضا برای اجرای عملگردهای ژنتیکی
الگوریتم NSGA-II، با هدف افزایش احتمال اعضای خوب در جمعیت والدین (Pt) برای اعمال عملگرهای ژنتیکی نظیر آمیزش و جهش، از عملگر انتخاب مسابقه ای بر مبنای تراکم[۱۱۸] به منظور انتخاب هر یک از پاسخ های دخیل در این عملگرها بهره می برد. این عملگرد(  ) دو پاسخ را که به صورت تصادفی انتخاب شده اند، مقایسه کرده و طرف برنده را برای عملگر آمیزش و یا جهش معرفی می کند. در مسابقه مابین پاسخ های i و j، پاسخ i در صورت ارضای یکی از شروط زیر، برنده خواهد بود:
پاسخ i در مقایسه با j در جبهه های پارتوی بهتری قرار داشته باشد(  )
اگر هردو پاسخ در یک جبهه ی پارتوی مشابه قرار داشته باشند، پاسخ i نسبت به پاسخ j دارای فاصله تراکم مناسبتری باشد. (  )
 
روش های حل مسائل بهینه سازی
روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم‌های دقیق و الگوریتم‌های تقریبی تقسیم‌بندی می‌شوند. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند و به دو دسته‌ی الگوریتم‌های ابتکاری و فراابتکاری تقسیم‌بندی می‌شوند.
روش های حل دقیق[۱۱۹]
آهوجا[۱۲۰](۱۹۷۶) و یونس[۱۲۱] و سعد[۱۲۲] (۱۹۹۶) بر مبنای شمارش ضمنی تمامی حالات ممکن برای زمان شروع فعالیت ها روش دقیق ارائه کرده اند. آهوجا (۱۹۷۶) مجموع مربع نوسانات منابع در دوره های متوالی و یونس و سعد مجموع قدر مطلق تفاوت سطح منبع مورد استفاده با مقدار هدف را در نظر گرفته اند. در روش یونس و سعد (۱۹۹۶)تمام فعالیت های بحرانی ابتدا زمانبندی می شوند، سپس تمام حالت های ممکن برای سایر فعالیت ها در نظر گرفته می شود. در این روش هر چند جواب بهینه حاصل می شود اما حل مسائل با اندازه بیش از ۱۰ فعالیت بخصوص وقتی شناوری فعالیت ها زیاد باشد، بسیار زمانبر و پیچیده می شود.
بندلونی و همکاران (۱۹۹۴) روش برنامه ریزی پویا بر مبنای استفاده فعالیت ها از شناوری شان را معرفی نموده است. عیسی[۱۲۳] (۱۹۸۹) از طریق مدلسازی ریاضی برای حالت خاصی از مسأله (حداقل سازی اوج با کاری منابع) به حل دقیق مسأله زمانبندی می پردازد. در دو تحقیق اخیر مثال های محدودی یبا حداکثر ۱۵ فعالیت به صورت بهینه حل شده است.
نیومن[۱۲۴] و همکاران (۲۰۰۳) برای مسأله تسطیح منابع با پنجره های زمانی(روابط پیش نیازی حداقلی و حداکثری) به ارائه روش شاخه و حد بر مبنای زمان شروع فعالیت ها و میزان شناوری باقیمانده فعالیت ها می پردازد. آنها مثال های با حجم حداکثر ۲۰ فعالیت را به صورت بهینه حل می کنند.
گتر[۱۲۵] و همکاران برای مسأله تسطیح منابع با وجود پنجره های زمانی به ارائه ویژگی هایی از این مسأله می پردازد که بر اساس آن با استفاده الگوریتم شاخه و حد، حل دقیقی برای این مسأله ارائه می کنند. ویژگی مورد بررسی باعث تعریف مفهومی به نام درختی حداقلی T شکل نام دارد که در شاخه زدن در الگوریتم شاخه و حد استفاده شده است. اندازه مسائل حل شده حداکثر ۲۰ است.
ریک و همکاران(۲۰۱۲) یک مدل ریاضی برنامه ریزی مختلط غیر خطی برای مسأله تسطیح منابع ارائه می کنند و آنرا به مدلی خطی تبدیل می کنند. در مدل مورد بررسی آنها تابع هدف می تواند مجموع مربع نوسانات و یا مجموع قدر مطلق نوسانات باشد. در این مدل ها روابط پیش نیازی حداقلی و حداکثری میان فعالیت ها وجود دارد. آنها برای نخستین بار مسائلی با حجم حداکثر ۵۰ فعالیت را به صورت بهینه حل نموده اند.
به هر حال هیچکدام از این روشها نمی توانند برای مسائل بزرگ استفاده شود چراکه قادر به یافتن جواب بهینه در دیگر مدت زمان منطقی نیستند. به همین خاطر روشهای ابتکاری و فراابتکاری مورد توجه قرار گرفتند.
روش های حل ابتکاری[۱۲۶]
برگس[۱۲۷] و کیلبریو[۱۲۸] (۱۹۶۲) به ارائه روشی تکراری بر مبنای جابجایی فعالیت ها در حدود شناوریشان می پردازند. این روش از جمله روش ها معروف در حوزه زمانبندی پروژه است.
هریس[۱۲۹] (۱۹۹۰) برای مسأله تسطیح منابع با یک منبع تجدید پذیر به ارائه روشی ابتکاری بر مبنای آنچه روش بسته بندی نامیده است می پردازد. این روش سعی در کنار هم قرار دادن فعالیت ها به گونه ای دارد که منابع مورد نیاز آنها در پروفایل منابع به شکل مستطیل کامل درآیند. سپس با جابجایی بسته های تشکیل شده تابع هدف بهبود می یابد. آنها در تحقیق مثالی را به تفصیل با این روش حل نموده اند.
تاکاموت و همکاران (۱۹۹۵) به حل مسأله ای واقعی در حوزه احداث واحدهای صنعتی می پردازند و روشی ابتکاری برای حل مسائل با حجم بالا(بیش از ۱۰۰۰ فعالیت) ارائه می کنند. لو[۱۳۰] وهمکاران(۲۰۰۰) با استفاده از الگوریتم ژنتیک به حل مسأله تسطیح منابع می پردازند و بر اساس الگوریتم ارائه شده یک سیستم پشتیبان تصمیم گیری توسط واسط کاربر برای استفاده مدیران ساخت طراحی می کنند. در الگوریتم ژنتیک ارائه شده، شیوه نمایش جواب ها به صورت بردار زمان شروع فعالیت ها می باشد. در این تحقیق کارائی الگوریتم از طریق مقایسه جواب یک مسأله (با ۱۱ فعالیت) با الگوریتم هریس (۱۹۹۰) بررسی شده است.
برینکمن[۱۳۱] و نیومن(۱۹۹۶) برای نخستین بار مسأله تسطیح منابع با پنجره های زمانی را مطرح می کند و روشی ابتکاری بر مبنای لیست فعالیت ها برای حل ارائه می دهد.
لو و همکاران(۱۹۹۹) به مدلسازی مسأله تسطیح منابع در محیط فازی می پردازند با استفاده از الگوریتم ژنتیک و بر اساس میزان دقت اطلاعات ورودی به ارائه جواب برای پروژه های ساخت می پردازند.
نیومن و زیمرمن[۱۳۲](۱۹۹۹) برای مسأله تسطیح منابع با پنجره های زمانی و محدودیت منابع به ارائه یک روش ابتکاری بر اساس لیست اولویت می پردازند. در روش مورد بررسی لیست اولویت برای فعالیت های غیر بحرانی تشکیل می شود که هنگام زمانبندی به زمانبندی ناقصی که فعالیتهای بحرانی در آن زمانبندی شده اند، اضافه می شوند. الگوریتم مورد بررسی قابلیت حل مسائل با اندازه زیاد را داراست.
سان[۱۳۳] و ماتیلا[۱۳۴](۲۰۰۴) به بررسی تأثیر شکست فعالیت ها بر روی بهبود تابع هدف در مسأله تسطیح منابع می پردازند. آنها برای این مسأله یک مدل برنامه ریزی خطی صفر و یک ارائه می کنند و یک مثال در دو حالت امکان شکست و عدم شکست را ارائه می کنند.
کاستورا[۱۳۵] و سیراکولیسب[۱۳۶](۲۰۰۹) به مسأله تخصیص منابع در پروژه ها می پردازند.آنها عملکرد سه بسته نرم افزار تجاری را که تسطیح منابع انجام می دهند با الگوریتم های موجود مقایسه می کنند.این نکته شایان ذکر است در اغلب بسته های نرم افزاری زمانبندی پروژه مسأله زمانبندی با وجود محدودیت منابع به اشتباه تسطیح منابع نام گرفته است.
جرجیوس[۱۳۷] و همکاران(۲۰۱۰) برای مسأله تسطیح منابع با وجود محدودیت منابع روشی بر اساس الگوریتم شبیه سازی تبرید استفاده کرده اند. در الگوریتم ارائه شده جوابها به صورت لیست اولویت فعالیت ها نمایش داده می شود و همسایگی ها به صورت تعویض جفتی برمبنای مشخصات شناوری ها صورت می گیرد.
دولابی و همکاران(۲۰۱۱) به مدلسازی مسأله تسطیح منابع با امکان در نظر گرفتن شکست فعالیت ها می پردازند.آنها برای حل مسأله از الگوریتم ژنتیک به همراه یک الگوریتم جستجوی محلی و اصلاح زمانبندی، استفاده کرده اند. جواب های حاصل از الگوریتم ژنتیک بهبود قابل توجهی نسبت به الگوریتم زودترین زمان شروع دارد. شیوه نمایش و ایجاد همسایگی در الگوریتم ژنتیک ارائه شده رعایت پیش نیازی میان فعالیت ها را تضمین نمی کند. آنها مثالی از کاربرد مدل در یک پروژه ساخت تونل ارائه می کنند.
روش های فرا ابتکاری
کلمه فرا ابتکاری و یا متاهیوریستیک[۱۳۸] مبین الگوریتم‌های پیشرفته‌ی ابتکاری می‌باشد. در حقیقت Meta در ابتدای این کلمه به معنای فراتر یا ماورا می‌باشد. کلمه Metaheuristic به مفهوم پیدا کردن راه‌حل بهینه با به کارگیری تکنیک‌هایی در سطوح پیشرفته و همچنین استفاده از روش‌های آزمون و خطا می‌باشد.
روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم‌ دقیق[۱۳۹]و الگوریتم‌ تقریبی[۱۴۰] تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد.
الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند و به دو دسته‌ی الگوریتم‌های ابتکاری و فراابتکاری تقسیم‌بندی می‌شوند. دو مشکل اصلی الگوریتم‌های ابتکاری، قرارگرفتن آن‌ها در بهینه‌های محلی، و عدم قابلیت آنها برای کاربرد در مسائل مختلف است. الگوریتم‌های فراابتکاری یا متاهیوریستیک‌ها برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای مکانیزم‌های خروج از بهینه‌ی محلی می‌باشند و قابل کاربرد در طیف وسیعی از مسائل هستند. رده‌های گوناگونی از این نوع الگوریتم‌های در دهه‌های اخیر توسعه یافته است.
الگوریتم‌های ابتکاری را روش‌های مبتنی بر جستجوی محلی می‌دانند، چرا که جستجوهای آن‌ها بر روی متغیرهای محلی متمرکز می‌باشد و همواره این امکان وجود دارد که راه‌حل مناسب و بهینه، خارج از منطقه محلی باشد؛ با این حال هنوز هم الگوریتم‌های ابتکاری را می‌توان در زمره بهترین روش‌های حل مسائل بهینه‌سازی دانست، خصوصاً هنگامی که محدودیت زمانی هم در حل مساله مهم می‌باشد.

دانلود متن کامل این پایان نامه در سایت abisho.ir
برچسب گذاری شده با: , , , ,