منابع پایان نامه با موضوع
درجه حرارت، بهره بردار

منابع پایان نامه با موضوع درجه حرارت، بهره بردار

آذر ۷, ۱۳۹۷ 0 By admin3

دو مرحله اي انعطاف پذير بدون وقفه ، براي نمايش يک حل اوليه از يک روش ساده استفاده شده است. ساختار کروموزوم پيشنهادي توالي انجام کارها را تعيين مي کند و براي به دست آوردن ماشين هاي مربوط به هر يک از کارها در هر مرحله از الگوريتم ابتکاري زير استفاده مي شود. با استفاده از اين رويکرد به عبارتي ديگر براي تخصيص ماشين ها به کارها از رويکرد تخصيص تصادفي استفاده نکيکنيم. چونکه در صورت تخصيص ماشين ها به صورت تصادفي احتمال به وجود آمدن جواب هاي نا معقول به شدت بالا مي رود. با استفاده از اين روش هم از بروز جواب هاي نامعقول جلوگيري کرده و همچنين همگرايي به سوي جواب بهينه و يا نزديک به بهينه سريعتر رخ مي دهد. براي توليد کروموزوم به تعداد کارهاي در نظر گرفته شده ، اعداد بين صفر و يک با ۳ رقم اعشار توليد مي کنيم. جايگاه کوچکترين عدد توليد شده در کروموزوم نشاندهنده ي جايگاه کار شماره يک در توالي توليد شده است. براي درک بيشتر اين موضوع فرض کنيد ۵ کار جهت زمانبندي در اختيار داريم و نحوه ي نمايش آنها را مي خواهيم بدانيم .همانطور که در شکل (۴-۲) مشاهده مي کنيد. کوچکترين عدد توليد شده ۰٫۱۳۸ است. اين عدد در جايگاه سوم قرار دارد. کوچکترين عدد توليد شده بعدي ۰٫۳۳۱ مي باشد. بنابراين کار شماره دو چهارمين کاري است که بايد زمان بندي شود. بقيه توالي به همين ترتيب تعيين مي شود. توالي نهايي در شکل (۴-۳) قابل مشاهده است.
ساختار کلي کروموزوم
۰٫۷۷۲
۰٫۳۳۱
۰٫۱۳۸
۰٫۶۳۵
۰٫۴۵۲
ساختار کلي کروموزوم مورد استفاده
۵
۲
۱
۴
۳
ساختار کروموزوم تبديل يافته
تابع برازندگي
در مورد مسايل بهينه‌سازي توابع، معمولا اين شاخص همان مقدار تابع هدف مساله مي‌باشد، يعني هر کروموزوم تبديل به جواب متناظر شده و در تابع هدف قرار مي‌گيرد، آنگاه مقدار تابع هدف براي هر جوابي که بهتر باشد کروموزوم متناظر با آن جواب مناسب‌تر خواهد بود. اما در مورد بعضي مسايل که پيچيده‌تر هستند بايد اقدام به تعريف تابع برازش نمود.مقدار اين تابع، برازندگي مربوط به يک کروموزوم را تعيين ميکند و کروموزومهاي قويتر را به عنوان بازماندگان براي نسل بعدي معرفي ميکند. انتخاب تابع برازندگي اثر مهمي را روي کارايي محاسباتي و ميزان دقت الگوريتم دارد. براي به دست آوردن مقدار تابع هدف در اين بخش ابتدا کروموزوم اوليه تبديل به يک توالي مي شود. سپس زودترين ماشين در دسترس دو مرحله براي زمان بندي اولين کار انتخاب مي شوند. بعد از زمان بندي کار اول زودترين ماشين هاي در دسترس براي کار دومي که قرار است زمان بندي شود محاسبه شده و کار مربوطه به ماشين هاي مورد نظر تخصيص داده مي شوند. اين کار تا زماني ادامه مي يابد که تمامي کارها زمان بندي شده باشند. در نهايت ماکزيمم زمان اتمام کارها به عنوان تابع برازندگي محاسبه مي شود.
عملگرهاي الگوريتم ژنتيک
در اين قسمت عملگرهاي مختلفي که در الگوريتم ژنتيک توسعه داده شده به کار رفته اند شرح داده ميشوند.
عملگرهاي انتخاب۷۱
هدف اصلي عملگرهاي انتخاب، تعيين کروموزومهاي بهتر و تاکيد بر حلهاي برازندهتر ميباشد. براي رسيدن به اين هدف، ميبايست به دو سوال پاسخ داده شود:
انتخاب والدين۷۲: چطور ميبايست کروموزومها در جمعيت را براي توليد فرزندان انتخاب کرد؟
استراتژي انتخاب بازماندگان ۷۳: چه تعداد کروموزوم ميبايست توليد گردد و چطور نسل بعدي از بين والدين و کروموزومهاي توليد شده يعني فرزندان انتخاب ميگردند؟
انتخاب والدين:
انتخاب کروموزوم از جمعيت به عنوان والدين دلخواه ميباشد. در اين تحقيق، انتخاب والدين بر اساس قانون انتخاب چرخ رولت۷۴ انجام ميگيرد. شکل (۴-۴) يک چرخ رولت را نمايش ميدهد.بر مبناي ميزان برازندگي، احتمال انتخاب هر کروموزوم تعيين ميگردد. با استفاده از اين قانون، کروموزومهايي که مقدار برازندگي بالاتري را دارند شانس بيشتري براي انتخاب دارند. اين رويهي انتخاب والدين، انتخاب بازماندگان قويتر را تضمين ميکند.
ساختار چرخ رولت
استراتژي انتخاب بازماندگان
براي يک جستجوي مفيد و کارا در فضاي حل و همين طور جلوگيري از همگرايي زودرس، استراتژي انتخاب که به وسيلهي بک۷۵ و همکاران پيشنهاد شده است، به عنوان قانون انتخاب بازماندگان انتخاب ميگردد. بر اساس اين قانون، بعد از توليد فرزند با استفاده از پدر و مادر، براي نسل بعدي تا از بهترين کروموزومهاي غير مشابه از ميان والدين و فرزندان به عنوان نسل بعدي انتخاب ميگردند ]۶۰ [.
عملگر تقاطع۷۶
عمليات تقاطع فرايند گرفتن دو کروموزوم والد از مخزن جفت گيري۷۷ و توليد فرزندان با استفاده از ترکيب آنها ميباشد که اين عمل با هدف پيدا کردن حلهاي بهتر صورت ميگيرد. در اين تحقيق از يک عملگر تقاطع يکنواخت۷۸ استفاده شده است. عملگر تقاطع يکنواخت در ابتدا يک ماسک باينري تصادفي۷۹ توليد ميکند که به اندازهي طول کروموزوم ميباشد و سپس محتواي ژن هاي مربوط به کروموزوم هاي والد را بر طبق ماسک باينري توليد شده جابجا ميکند. اين عمليات تقاطع يک بهره برداري۸۰ خوب از فضاي حل را منجر مي گردد ]۶۱[. يک عمليات تقاطع سه بعدي در شکل (۴-۵)نمايش داده شده است.
نمونه عمليات تقاطع
نرخ تقاطع
نرخ تقاطع بيانگر احتمال تقاطع است كه آن را با Pc نشان مي دهند مقدار ان بين ۰ تا ۱ است . اين نرخ با پيداكردن نسبت تعداد جفت هاي ادغام شده در جمعيت هاي ثابت به دست مي آيد. هر چه اين مقدار بيشتر باشد، كروموزوم هاي جديد و زياد تري وارد استخر توليد مثل شده اند. اگر اين مقدار خيلي زياد باشد باعث مي شود تا فرصت تطابق در كروموزوم از دست برود اما اگر اين مقدار خيلي كم باشد، تعداد فرزندان توليد شده كافي نخواهد بود. تجربه نشان داده است که اين نرخ بايد در حدود ۰٫۶۵ تا۰٫۸۵ باشد.
عمليات جهش
پس از عمليات تقاطع، يک جهش تعويضي۸۱ انجام ميگيرد. جهش تعويضي، بر روي هر يک از فرزندان توليد شده از عمليات تقاطع با يک احتمال مشخص که احتمال جهش ناميده ميشود انجام ميگيرد. اين عمليات بدين صورت است که دو ژن متفاوت از کروموزوم به صورت تصادفي انتخاب ميشوند و سپس مقادير آنها با يکديگر معاوضه ميگردد ]۵۹ [. نمونه اي از عمليات جهش در شکل (۴-۶)نمايش داده شده است.
نرخ جهش
نرخ جهش عبارت است از درصدي ار کل تعداد ژن هاي موجود که دچار جهش مي شوند.اگر نرخ جهش خيلي کوچک باشد تعداد زيادي از ژن ها که مي توانست مفيد باشد تست نمي شوند.همچنين اگر نرخ جهش خيلي بزرگ باشد يک اختلال به وجود آمده و تعداد زيادي از نوزادان شباهتشان را با والدين از دست مي دهند .اين نرخ مقدار كوچكي است كه معمولاً بين ۰۱/۰ تا ۰۵/۰ براي ژن هاي باينري و ۰٫۰۵ تا ۰٫۲۰ براي ژنهاي عددي در نظر گرفته مي شود.
نمونه عمليات جهش
شرط خاتمهي الگوريتم
ملاکهاي مختلفي را ميتوان به عنوان شرط خاتمهي الگوريتم قرار داد. در اين تحقيق، الگوريتم پس از يک تعداد ثابتي از تکرارها متوقف ميگردد. شکل (۴-۷) نمونهاي از فرايند اجراي الگوريتم ژنتيک را نمايش ميدهد.
فرايند اجراي الگوريتم ژنتيک براي مسئله ي NWTSFFS
نقاط قوت الگوريتم هاي ژنتيک
مهمترين نقطه قوت اين الگوريتم ها اين است که الگوريتم هاي ژنتيک ذاتا” موازي اند. از آنجايي که اين الگوريتم چندين نقطه شروع دارد، در يک لحظه مي تواند فضاي مسئله را از چندجهت مختلف جستجو کند و اگر يکي به نتيجه نرسيد ساير راه ها ادامه مي يابند و منابع بيشتري را در اختيار شان قرار مي گيرد. به همين براي مسائلي که فضاي راه حل بزرگي دارند بسيار مفيد است. يکي ديگر از خصوصيات مثبت اين الگوريتم دستيابي به نقطه بهينه کلي۸۲ به جاي نقطه بهينه محلي۸۳ ست. يعني هميشه در حد بسيار مطلوبي مي‌توان به پاسخ اين الگوريتم اعتماد کرد و اينکه پاسخي که مي‌يابد به احتمال زياد بهترين پاسخ ممکن است . علاوه بر اين، اين الگوريتم به همين شکل موجود در حل انواع مسائل مي‌تواند به کار رود و نيازي به تغيير آن نيست. در واقع تنها کاري که در مورد هر مسئله بايد انجام دهيم اين است که جواب‌هاي مختلف را به شکل کروموزوم‌ها بازنمايي کنيم.
رويه ي الگوريتم ژنتيک
شکل (۴-۸) نمايشي از مراحل الگوريتم ژنتيک هيبريدي توسعه داده شده را براي مسئلهي مورد بررسي نشان ميدهد.
نمودار الگوريتم ژنتيک هيبريدي براي مسئلهي NWTSFFS
شبيه سازي تبريد
شبيه سازي تبريد يک تکنيک محاسباتي تصادفي براي بدست آوردن جوابهاي نزديک به بهينه در مسائل ترکيباتي و بهينهسازي ميباشد. اين روش از فرايند ترموديناميکي سرد کردن فلزات مذاب براي بدست آوردن کمترين حالت انرژي حاصل ميشود ]۶۲[. مزيت اصلي شبيهسازي تبريد نسبت به روشهاي جستجوي تصادفي، توانايي آن براي جلوگيري از افتادن در بهينههاي محلي هنگام جستجو براي مينيمم محلي ميباشد.
در استراتژي جستجوي شبيهسازي تبريد، الگوريتم از يک جواب اوليه آغاز ميشود. در هر مرحله جوابهاي جديد توسط حرکات تصادفي در همسايگي جواب فعلي توليد ميشوند. اگر جواب جديد مقدار تابع هدف را بهبود دهد، جايگزين جواب فعلي ميگردد در غير اين صورت جواب جديد با احتمال مشخصي شانس پذيرش دارد. اين احتمال بصورت زير تعريف ميشود:
بطوري که ، جواب فعلي، جواب جديد توليد شده، تابع هدف، دماي تبريد در مرحله ام و احتمال پذيرش ميباشد. استفاده از احتمال فوق در الگوريتم بدين صورت است که در هر مرحله عدد تصادفي بين صفر و يک توليد ميشود و با احتمال مذکور مقايسه ميگردد. چنانچه اين عدد تصادفي از احتمال کوچکتر بود، جواب جديد پذيرفته ميشود ]۶۳[. در ابتداي الگوريتم هر حرکتي پذيرفته ميشود. اين امر اجازه حرکت در فضاي جواب را به ما ميدهد. دما در هر مرحله تا زماني که تعداد ثابتي تکرار () انجام شود، ثابت باقي ميماند. سپس به تدريج کاهش مييابد تا در انتها تنها حرکتهاي موثر مورد پذيرش واقع شوند. الگوريتم تا زمان رسيدن به دماي پاياني () ادامه مييابد.
برنامه سردسازي۸۴
برنامه سردسازي شامل پارامترهايي است كه نحوه سرد كردن الگوريتم را مشخص مي‌كنند. مهمترين پارامترهاي برنامه سردسازي درجه حرارت آغازين۸۵ و كاهش درجه حرارت در هر مرحله۸۶ ميباشند. اين پارامترها نقش موثري در همگرايي الگوريتم به جواب بهينه، ايفا ميکنند. بدين منظور نحوه تعيين پارامترهاي فوق بطور مختصر توضيح داده ميشوند.
درجه حرارت آغازين ()
درجه حرارت آغازين بايد به اندازه كافي گرم باشد تا حركت به حالت مجاور را اجازه دهد. اگر درجه حرارت آغازين خيلي زياد باشد جستجو مي‌تواند به هر همسايگي حركت كند و جستجو به جستجوي تصادفي تبديل مي‌شود. اين جستجوي تصادفي ادامه مي يابد تا زماني كه دما به اندازه كافي کاهش يابد. مقادير بسيار بزرگ موجب طولاني شدن مدت زمان اجراي الگوريتم و گسترش نقاط جستجو ميشود و مقادير بسيار کوچک آن ممکن است موجب همگرايي زود هنگام شده و الگوريتم در بهينه محلي متوقف شود. براي محاسبه مقدار دماي اوليه ، توسط مکانيزم توليد همسايگي، تعداد ثابتي جواب را توليد و ميزان تغيير تابع هدف هر دو جواب متوالي را ارزيابي ميکنيم، بيشترين مقدار اختلاف تابع هدف را بعنوان بهترين اندازه براي پارامتر دماي اوليه در نظر ميگيريم.
كاهش درجه حرارت در هر مرحله

مطلب مشابه :  پایان نامه با کلید واژه هایاعتبارات خرد، توسعه روستا، خانواده ها