همانطور که انتظار میرفت به غیر از فعالیت نگهداری اولیه که جز فرضیات اولیه مسئله میباشد، فعالیت نگهداری دیگری در برنامه پردازش قرار نگرفته است.
۳-۶٫ پیچیدگی مسئله
یک دیدگاه سودمند در زمینه مسائل زمانبندی و روشهای حل آنها از شاخهای از علم کامپیوتر با عنوان نظریه پیچیدگی [۱۳]حاصل می شود. پیچیدگی به مفهوم میزان محاسبات مورد نیاز در یک الگوریتم حل [۱۴]میباشد. به عنوان مثال در مسئلهای با اندازه n ( n نمایانگر میزان اطلاعات لازم برای مشخص شدن مسئله میباشد.) تعداد محاسبات لازم برای حل مسئله با یک حد بالا که تابعی از n میباشد محدود میباشد. ]۱۸[. در این شرایط هرگاه با افزایش مقدار n میزان محاسبات لازم با بهره گرفتن از الگوریتم حل مسئله به صورت یک تابع چندجملهای از n باشد الگوریتم حل از درجه چندجملهای [۱۵]میباشد. در شرایط یکسان برای حل یک مسئله، الگوریتمهای چندجملهای نسبت به الگوریتمهای غیر چندجملهای سریعتر و عملکرد آن موجهتر است ]۱۸[ .
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
بسیاری از مسائل مهم ترکیباتی نظیر اکثر مسائل زمانبندی در کلاس مسائل np-hard قرار میگیرند. میزان پیچیدگی این مسائل به گونه ای است که الگوریتم چندجملهای که قادر به حل این این مسائل در زمان محاسباتی معقول باشد ، یافت نمی شود. کاربرد این مفهوم در حل مسائل زمانبندی که در کلاس NP-HARD قرار میگیرند، بسیار موثر است بطوری که حل مسائلی از این قبیل نیازمند الگوریتمهای ابتکاری [۱۶] و فراابتکاری [۱۷] است که بتوانند در مدت زمان معقول به جواب بهینه دست یابند.
یک الگوریتم حل برای یک مسئله زمانبندی می تواند در مسئله دیگر که حالت خاص مسئله اصلی است ، به کار گرفته شود. به عنوان مثال مسئله ۱|| حالت خاص مسئله ۱|| محسوب می شود. در نظریه پیچیدگی این وضیعت را به صورت ۱|| ۱|| نشان می دهند. بدین ترتیب زنجیرهای از مسائل زمانبندی قابل تولید است که در آن الگوریتمهای حل و پیچیدگی مسائل مختلف به یکدیگر مربوط میشوند . پیندو]۹[ سلسله مراتب پیچیدگی مسائل مختلف زمانبندی را از طریق گرافهای منحصر به فردی ارائه مینماید. همانطور که در شکل (۳-۱) نمایش داده شده است ، تغییر در عناصر مسائل زمانبندی مانند تغییر در نوع تابع هدف موجب تغییر در میزان پیچیدگی آنها می شود.
شکل (۳-۱) سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی]۹[
طبق مطالعه آقای دارلی یانگ و همکاران ]۲۵[ مسئله زمانبندی ماشینهای موازی با توجه به اثر استهلاک از دسته مسائل NP-HARD میباشد. پس میتوان نتیجه گرفت مسئله زمانبندی ماشینهای موازی غیر مرتبط با در نظر گرفتن اثر همزمان استهلاک و یادگیری و فعالیتهای نگهداری که به مراتب پیچیدهتر از مسئله مورد مطالعه دارلی یانگ میباشد نیز NP-HARD میباشد. ما در این مطالعه برای حل مدل مطرحشده در ابعاد کوچک یک مدل ریاضی خطی ارائه نموده و برای نمونههای متوسط و بزرگ از روش فراابتکاری ژنتیک و رقابت استعماری استفاده نمودهایم.
۳-۷٫ مقدمهای بر الگوریتم ژنتیک [۱۸](GA)
از سال ۱۹۶۰ تقلید از پدیدههای طبیعی برای استفاده در الگوریتمهای قوی جهت حل مسائل مشکل بهینهسازی مورد توجه قرار گرفت که تکنیکهای محاسبه تکاملی[۱۹] نام گرفتند. الگوریتم ژنتیک که اولین بار توسط جان هالند [۲۳] در دانشگاه میشیگان پیشنهاد شد و استراتژیها و برنامهریزیهای تکاملی که توسط رچنبرگ[۲۰] و چیفل[۲۱] و فوگوگل[۲۲] و کوزا[۲۳] ایجاد شدند، از جمله روشهای محاسبه تکاملی هستند.
روشهای بهینهسازی الهام گرفته از طبیعت با روشهای متعارف بهینهسازی تفاوت مهمی دارند. در روشهای متعارف هرجواب کاندیدای جدید در صورتی به عنوان جواب جدید انتخاب میشود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتمهای الهام گرفته از طبیعت به تمام جوابهای کاندیدای جدید شانس انتخاب داده میشود.
الگوریتم ژنتیک یکی از مهمترین الگوریتمهای ابتکاری میباشد که از آن برای بهینهسازی توابع مختلف استفاده میشود. در این الگوریتم اطلاعات گذشته با توجه به موروثی بودن الگوریتم استخراج شده و در روند جستجو مورد استفاده قرار میگیرد.
ابتدا توسط هالند [۲۳] یک مفهوم اولیه از الگوریتم ژنتیک ارائه شد و سپس گلدبرگ [۲۲] آن را توسعه داد. الگوریتمهای ژنتیک، تکنیکهای جستجوی تصادفی هستند که بر اساس انتخاب طبیعی و نسلشناسی طبیعی کار میکنند.
۳-۷-۱٫ شمای کلی الگوریتم ژنتیک
الگوریتم ژنتیک کلاسیک در قالب شبه برنامه زیر صورت می پذیرد:
تولید جامعه اولیه به صورت تصادفی.
ارزشیابی اعضا جامعه بوسیله تابع برازش.
تولید جامعه جدید بر اساس مراحل زیر:
۱٫۳٫ انتخاب دو عضو از یک جامعه به عنوان والدین بر اساس میزان برازش آنها.
۲٫۳٫ بکارگیری احتمالی عملگر تقاطع برای تولید فرزندان. در صورت عدم بکارگیری عملگر تقاطع، فرزندان همان والدین خواهند بود.
۳٫۳٫ بکارگیری عملگر جهش بر روی فرزندان.
جایگزینی فرزندان در جامعه جدید.
توقف الگوریتم در صورت مشاهده شرایط توقف و معرفی بهترین جواب تولید شده به عنوان جواب بهینه در غیر این صورت رفتن به مرحله بعد.
رفتن به مرحله ۲٫
۳-۷-۲ واژگان الگوریتم ژنتیک:
از آنجا که الگوریتم ژنتیک از هر دو علم کامپیوتر و ژنتیک طبیعی نشات گرفته است واژههای مورد استفادهاش مخلوطی است از واژههای طبیعی و مصنوعی. مفاهیم اولیه که در فهم الگوریتم ژنتیک بسیار حیاتی هستند عبارتند از:
کروموزوم: اساس الگوریتم ژنتیک تبدیل هر مجموعه جواب به یک کدینگ است. این کد را اصطلاحاً کروموزوم گویند. به کروموزوم، فرد[۲۴]، رشته[۲۵] یا ساختار[۲۶] نیز گفته شدهاست، همچنین میتوان آنها را ژنو تایپ[۲۷] نیز نامید.
فنو تایپ[۲۸]: هر کروموزوم متناظر با یک مجموعه جواب از مسئله است. مجموعه متناظر با هر کروموزوم را یک فنو تایپ میگویند.
ژن: عناصر تشکیل دهنده یک کروموزوم که معمولا اعداد هستند را ژن میگویند. ژنها را ویژگی[۲۹]، نشان[۳۰] و رمزگشا[۳۱] نیز نامیدهاند.
مکان: محل قرار گرفتن ژن در کروموزوم را یک مکان میگویند.
جمعیت[۳۲]: مجموعهای از کروموزومها را یک جمعیت میگویند.
نسل[۳۳]: هر تکرار از الگوریتم را یک نسل میگویند.
۳-۷-۳ جامعه اولیه
تعدادی از کروموزومها با هم یک جمعیت را تشکیل می دهند اندازه جمعیت اولیه همان تعداد کروموزومها میباشد که در هر مرحله باید نگهداری شوند. در یک جمعیت، همه کروموزومها اندازه یکسانی دارند و به صورت pop size نشان داده میشوند. اگر pop size کوچک باشد همگرایی الگوریتم سریعتر خواهد بود اما همگرایی زودرس ممکن است منجر به افتادن در دام یک بهینه محلی شود. جمعیت اولیه شامل یک سری جوابهای مسئله است که به طور ابتکاری یا تصادفی تولید شده اند.
۳-۷- ۴٫ عملیات ژنتیک
عملیات ژنتیک به فرایند تولید کروموزومهای جدید (فرزندان) با بهره گرفتن از کروموزومهای موجود (والدین) اطلاق می شود و به طورکلی توسط سه عملگرعمده انجام می شود: انتخاب، تقاطع و جهش.
۳-۷-۴-۱٫عملگر انتخاب[۳۴]:
نیروی پیشبرنده در الگوریتم ژنتیک انتخاب کروموزومها با توجه به میزان برازندگی آنها میباشد. کروموزومهای برازندهتر از شانس بالاتری برای انتخاب شدن به عنوان عضوی از نسلهای آتی الگوریتم برخوردار هستند. این موضوع متناظر با اصل بقای انسب[۳۵] در نظریه تکامل تدریجی به مفهوم قابلیت طبعیت در تطابق با تغییرات محیطی میباشد و یکی از الهامبخشترین مفاهیم ژنتیک طبیعی در الگوریتم ژنتیک به شمار می آید.
متداولترین مکانیسمهای انتخاب عبارتند از:
انتخاب چرخ رولت[۳۶]:
انتخاب چرخ رولت یکی ازمناسبترین انتخابهای تصادفی بوده که ایده آن بر اساس احتمال انتخاب میباشد و اولین بارتوسط هالند [۲۳] پیشنهاد شد.احتمال انتخاب متناظربا هرکروموزوم ،براساس برازندگی آن محاسبه می شود بطوریکه که اگر میزان برازندگی کروموزوم ام باشد، احتمال بقای متناظر با این کروموزوم برابر است با:
(۳-۱)
در این معادله اندازه جامعه و احتمال بقای متناظر با کروموزوم ام میباشد. اگر کروموزومها بر اساس مرتب شوند، که همان مقدار تجمعی است، به صورت زیرمحاسبه می شود:
(۳-۲)
درروش انتخاب چرخ رولت برای انتخاب هرکروموزوم ابتدایک عددتصادفی از بازه تولیدمیشود. این عدد به طور طبیعی از یکی مقادیر کوچکتر است و بدین صورت کروموزوم ام متناظر با انتخاب می شود. روش پیادهسازی چرخ رولت به این شکل است که یک چرخ فرضی درنظر گرفته می شود و سطح آن به تعداد کروموزومها طوری تقسیم می شود که هر بخش از آن متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ به گردش در می آید و هر جا شاخص چرخ متوقف شد،کروموزوم مربوط به آن بخش انتخاب میگردد.
انتخاب مسابقهای[۳۷]:
پارامتر موثر در این روش، تور میباشد که عبارتست از تعداد اعضایی که به صورت تصادفی و در قالب یک گروه از جامعه انتخاب شده و سپس بهترین اعضای این گروه به عنوان والدین انتخاب میشوند. این فرایند آنقدر تکرار می شود تا تعداد والدین مورد نظر انتخاب شوند.