منابع پایان نامه با موضوع
منطق حاکم

منابع پایان نامه با موضوع منطق حاکم

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

ديرشدگي
One-way ANOVA: MRS5, MRS6, FCFS, MRS7, EDD, MRS4, MDA, LPT, SPT, Johnson
Source DF SS MS F P
Factor 9 149505348 16611705 27.07 0.000
Error 3230 1982023250 613629
Total 3239 2131528599
Johnson
SPT
LPT
MDA
MRS4
EDD
MRS7
FCFS
MRS6
MRS5
*
MRS5
MRS6
*
*
*
*
*
*
FCFS
*
*
*
*
*
*
MRS7
*
*
*
*
EDD
*
*
*
MRS4
*
*
*
MDA
*
*
LPT
*
SPT
Johnson
تابع هدف مينيمم سازي متوسط تاخير
طبق جدول (۳-۴۶) مقدار P-Value به دست آمده کمتر از مقدار مي باشد. لذا فرض تساوي ميانگين الگوريتم ها رد مي شود. در جدول (۳-۴۶) فاصله اطمينان ۹۵% براي RD هر يک از الگوريتم ها آورده شده است. فاصله اطمينان به دست آمده براي الگوريتم پيشنهادي MRS5 و MRS6به طور قابل ملاحظه اي با ساير الگوريتم ها فاصله دارد. با توجه به اينکه فرض صفر آزمون ANOVA يعني برابري ميانگين الگوريتم ها، رد مي شود. بنابراين براي بررسي عملکرد الگوريتم ها از آزمون مقايسات زوجي توکي استفاده مي کنيم. اين نتايج به صورت خلاصه شده در جدول (۳-۴۶) آورده شده است.
نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي ماکزيمم زمان اتمام کارها
One-way ANOVA: MRS5, MRS6, FCFS, MRS7, EDD, MRS4, MDA, LPT, SPT, Johnson
Source DF SS MS F P
Factor 9 154620983 17180109 27.99 0.000
Error 3230 1982334959 613726
Total 3239 2136955942
Johnson
SPT
LPT
MDA
MRS4
EDD
MRS7
FCFS
MRS6
MRS5
*
MRS5
MRS6
*
*
*
*
*
*
FCFS
*
*
*
*
*
*
MRS7
*
*
*
*
EDD
*
*
*
MRS4
*
*
MDA
*
*
LPT
*
SPT
Johnson
تابع هدف مينيمم سازي ماکزيمم تاخير
طبق جدول (۳-۴۷) مقدار P-Value به دست آمده کمتر از مقدار مي باشد. لذا فرض تساوي ميانگين الگوريتم ها رد مي شود. در جدول (۳-۴۷) فاصله اطمينان ۹۵% براي RD هر يک از الگوريتم ها آورده شده است. فاصله اطمينان به دست آمده براي الگوريتم پيشنهادي MRS5 و MRS6به طور قابل ملاحظه اي با ساير الگوريتم ها فاصله دارد. با توجه به اينکه فرض صفر آزمون ANOVA يعني برابري ميانگين الگوريتم ها، رد مي شود. بنابراين براي بررسي عملکرد الگوريتم ها از آزمون مقايسات زوجي توکي استفاده مي کنيم. اين نتايج به صورت خلاصه شده در جدول (۳-۴۷) آورده شده است.
نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي ماکزيمم تاخير
One-way ANOVA: MRS5, MRS6, FCFS, MRS7, EDD, MRS4, MDA, LPT, SPT, Johnson
Source DF SS MS F P
Factor 9 778544558 86504951 33.59 0.000
Error 3230 8318159499 2575282
Total 3239 9096704057
Johnson
SPT
LPT
MDA
MRS4
EDD
MRS7
FCFS
MRS6
MRS5
*
MRS5
MRS6
*
*
*
*
*
*
FCFS
*
*
*
*
*
*
MRS7
*
*
EDD
*
MRS4
*
*
*
MDA
*
*
LPT
*
SPT
Johnson
تابع هدف مينيمم سازي کارهاي تاخير دار
طبق جدول (۳-۴۸) مقدار P-Value به دست آمده کمتر از مقدار مي باشد. لذا فرض تساوي ميانگين الگوريتم ها رد مي شود. در جدول (۳-۴۸) فاصله اطمينان ۹۵% براي RD هر يک از الگوريتم ها آورده شده است. فاصله اطمينان به دست آمده براي الگوريتم پيشنهادي MRS5 و MRS6به طور قابل ملاحظه اي با ساير الگوريتم ها فاصله دارد. با توجه به اينکه فرض صفر آزمون ANOVA يعني برابري ميانگين الگوريتم ها، رد مي شود. بنابراين براي بررسي عملکرد الگوريتم ها از آزمون مقايسات زوجي توکي استفاده مي کنيم. اين نتايج به صورت خلاصه شده در جدول (۳-۴۸) آورده شده است. نتايج خلاصه شده فاز سوم در جدول (۳-۴۹) آورده شده است.
نتايج مربوط به فاز سوم براي تابع هدف مينيمم سازي کارهاي تاخيردار
One-way ANOVA: MRS5, MRS6, FCFS, MRS7, EDD, MRS4, MDA, LPT, SPT, Johnson
Source DF SS MS F P
Factor 9 11896.1 1321.8 14.81 0.000
Error 3230 288293.8 89.3
Total 3239 300189.9
Johnson
SPT
LPT
MDA
MRS4
EDD
MRS7
FCFS
MRS6
MRS5
*
*
*
*
MRS5
MRS6
*
*
*
FCFS
*
*
*
MRS7
*
*
EDD
*
MRS4
*
*
MDA
*
LPT
*
SPT
Johnson
توابع هدف
MFT
Tardy jobs
Cpu Time(s)
الگوريتم ها
ميانگين
تعداد
موفقيت
ميانگين
تعداد موفقيت
ميانگين
تعداد موفقيت
ميانگين
تعداد موفقيت
ميانگين
تعداد موفقيت
ميانگين
تعداد موفقيت
ميانگين
تعداد موفقيت
ميانگين
تعداد موفقيت
MRS5
۶۴۴٫۹۱
۱۵۵
۳۹۴٫۷۷
۷۷
۲۸۷٫۳۶
۷۷
۸۲٫۴۵
۱۱۱
۱۴۸٫۷۵
۱۶۳
۴۱٫۹۴
۶۳
-۷۹٫۸۰
۹۷
۰٫۰۷
MRS6
۶۳۷٫۶۵
۱۹۲
۳۸۲٫۱۵
۲۳۰
۲۷۴٫۷۴
۲۳۰
۷۶٫۴۹
۲۱۰
۱۴۳٫۴۳
۱۹۹
۳۹٫۵۳
۱۵۷
-۷۲٫۴۹
۲۰۸
۰٫۰۲
۱۶۱
FCFS
۱۵۴۲٫۱۱
۲۳
۸۱۷٫۶۰
۳۳
۷۱۰٫۱۹
۳۳
۵۱۹٫۶۲
۳
۱۰۹۹٫۷۲
۴
۴۲٫۵۲
۵۶
-۵۰۲٫۶۳
۳۴
۰٫۰۱
۲۳۹
MRS7
۱۶۷۴٫۱۸
۹۴۰٫۱۸
۸۳۲٫۷۷
۶۲۸٫۹۰
۱۲۳۵٫۸۸
۴۵٫۴۳
۴
-۶۲۵٫۲۱
۰٫۰۱
۲۰۳
EDD
۱۵۵۱٫۷۹
۲
۸۰۰٫۸۴
۱۲
۶۹۳٫۴۳
۱۲
۴۸۸٫۶۲
۲۹
۱۰۳۲٫۵۰
۱۶
۴۵٫۰۸
۲۰
-۴۸۵٫۸۷
۱۴
۰٫۰۱
۲۳۷
MRS4
۱۵۴۷٫۳۵
۹
۸۲۳٫۸۷
۲
۷۱۶٫۴۶
۲
۵۱۰٫۶۹
۱۱
۱۰۴۵٫۰۲
۱۷
۴۵٫۹۵
۹
-۵۰۸٫۹۰
۲
۰٫۰۱
۲۱۰
MDA
۱۶۸۱٫۳۰
۹۲۰٫۸۰
۸۱۳٫۳۹
۶۲۳٫۲۴
۱۴۶۴٫۹۳
۴۲٫۲۱
۷۱
-۶۰۵٫۸۳
۱
۰٫۰۱
۲۴۱
LPT
۱۷۲۳٫۳۰
۱۰۲۹٫۸۳
۹۲۲٫۴۲
۷۲۶٫۷۲
۱۵۴۳٫۹۳
۴۴٫۹۳
۱۰
-۷۱۴٫۸۶
۰٫۰۱
۲۱۷
SPT
۱۶۷۶٫۸۱
۸۹۲٫۴۴
۲
۷۸۵٫۰۳
۲
۵۹۴٫۵۳
۱۴۰۴٫۷۴
۴۲٫۲۴
۷۲
-۵۷۷٫۴۷
۲
۰٫۰۱
۲۳۳
Johnson
۱۶۴۹٫۵۶
۵
۹۷۴٫۸۶
۸۶۷٫۴۴
۶۷۶٫۸۳
۱۴۸۶٫۵۶
۴۲٫۶۷
۴۸
-۶۵۹٫۸۸
۰٫۰۱
۲۲۲
ميانگين توابع هدف، تعداد موفقيت و زمان اجراي الگوريتم ها در فاز سوم
جمع بندي
در اين فصل سه فاز براي معرفي الگوريتم هاي پيشنهادي در نظر گرفتيم. در فاز اول الگوريتم MRS1 ، در فاز دوم الگوريتم هاي MRS2,MRS3,MRS4 پيشنهاد شد و در نهايت در فاز سوم الگوريتم هاي MRS5,MRS6,MRS7 پيشنهاد شد. نتايج حاصله حاکي از برتري الگوريتم هاي ارائه شده دارد.
حل تک هدفه مسئلهي مورد مطالعه با استفاده از الگوريتم هاي فرا ابتکاري
مقدمه
اکنون تعداد زيادي از مسائل بهينه سازي در پيرامون ما وجود دارد که به روش دقيق يا اصلاً قابل حل نيستند و يااين که در زمان معقول انجام اين امر امکان پذير نيست. بعضي از اين چنين مسائلي را که عمدتاً جزء مسائل بهينه سازي هستند، مسائل NP-Hard مي نامند. اين خانواده بزرگ از مسائل، خواص بسيار جالبي دارند که سبب شده است تا کنون روش هاي تقريبي متعددي براي حل هر کدام از آنها در طول زمان ارائه شود. الگوريتم هاي فراابتکاري (متاهيوريستيک) جزء اين دسته از روش ها هستند. البته در مواقعي که در يک مسئله بهينه سازي، پارامتر يا محدوديت تصادفي، چند تابع هدف متضاد و امثالهم هم وجود داشته باشد، استفاده از الگوريتم هاي فراابتکاري بسيار موفقيت آميزتر از ساير روش ها گزارش شده است. از طرف ديگر تنها تعداد معدودي از اين الگوريتم ها اثبات شده اند که در حل بعضي از مسائل خاص حتماً به ازاي هر مقدار از پارامترهاي ورودي به جواب بهينه همگرا مي شوند. عيب عمده اين روش ها هم در همين مورد است. اما قابليت مانور فراوان، طراحي ساده و بسيار سريع بودن آنها در کفه ديگر ترازو قرار دارد. تعداد الگوريتم هاي فراابتکاري بسيار زياد است اما ساختار منطق حاکم بر آنها معمولا جزء چند دسته از ساختارهاي شناخته شده قرار مي گيرد. از اين رو با شناخت اين منطق ها مي توان الگوريتم هاي هيبريدي جديدي را براي حل مسائلي را که با آنها سر و کار داريم، به وجود آورد. اين روند همچنان ادامه دارد و هر روز الگوريتم هاي جالبي متولد مي شوند و عده اي از الگوريتم ها نيز به تدريج منسوخ مي شوند و تنها ارزش گزارش شدن در تاريخچه الگوريتم ها را به خود مي گيرند. در اين فصل دو الگوريتم فراابتکاري هيبريدي با عناوين الگوريتم ژنتيک هيبريدي و الگوريتم شبيه سازي تبريد هيبريدي ارائه شده است.
الگوريتم ژنتيک
روش‌هاي بهينه‌سازي الهام گرفته از طبيعت با روش‌هاي متعارف بهينه‌سازي تفاوت مهمي دارند. در روش‌هاي متعارف هرجواب کانديداي جديد در صورتي به عنوان جواب جديد انتخاب مي‌شود که مقدار تابع هدف را بهبود بخشد ولي در الگوريتم‌هاي الهام گرفته از طبيعت به تمام جواب‌هاي کانديداي جديد شانس انتخاب داده مي‌شود. الگوريتم ژنتيک يکي از روشهاي محاسبه تکاملي است که از آن براي بهينه سازي توابع مختلف استفاده مي شود. الگوريتم ژنتيک در واقع تلاشي براي شبيه سازي برخي از خصوصيتهاي تکامل و تغييرات روي کروموزوم است که همواره در طبيعت صورت مي گيرد.
ايده اصلي الگو ريتم هاي تكاملي در سال۱۹۶۰ توسط رچنبرگ۶۷ مطرح گرديد. الگوريتم هاي ژنتيك كه منشعب از اين نوع الگوريتم ها و بر اساس ساختار ژن ها و كروموزوم ها است در دهه هفتاد ميلادي توسط پروفسور هالند۶۸ در دانشگاه ميشيگان مطرح شد]۵۷ [ و بعدها توسط گلدبرگ۶۹ و آربر۷۰ توسعه يافت.]۵۸ [. الگوريتم ژنتيك با الهام از تئوري داروين درباره حيات بهترين ها شكل گرفته است . بنابر اين مي توان گفت:
“الگوريتم ژنتيک، بر اساس اصل ” ادامه حيات بهترين ها” و ” تكثير نوع برتر “پي ريزي شده است .”
پيچيده و بزرگ بودن فضاي هاي جستجو ما را به استفاده از الگو ريتم هاي ژنتيك سوق مي دهد.اين الگوريتم‌ تفاوت‌هايي اساسي با روش‌هاي جستجو و بهينه‌سازي متداول دارند که گلدبرگ اين تفاوت‌ها را به صورت ذيل خلاصه کرده است.]۵۸ [.
۱- الگوريتم ژنتيک از قواعد انتقال احتمالي استفاده مي‌کند نه از قواعد قطعي.
۲- الگوريتم ژنتيک با مجموعه‌اي از جواب‌هاي کدگذاري شده کار مي‌کند نه با خود آنها.
۳- الگوريتم ژنتيک از اطلاعات تابع برازش استفاده مي‌کند، نه از مشتق‌ها و يا علوم کمکي ديگر.
۴- الگوريتم ژنتيک در يک جمعيت از جواب‌ها و با مجموعه‌اي از آنها شروع به جستجو مي‌کند نه با يک جواب.
در ادامه، شکل نمايش کروموزوم، شيوهي محاسبهي تابع برازندگي و همينطور عملگرهاي الگوريتم ژنتيک که براي حل اين مسئله استفاده شدهاند، شرح داده ميشوند.
ساختار کروموزوم
يکي از مهمترين موضوعات در حل مسائل به وسيلهي روشهاي فرا ابتکاري شيوهي کدگذاري کروموزوم مربوطه ميباشد. اين به دليل تاثير قابل توجهي است که بر روي کارايي و اثر بخشي الگوريتم دارد ]۵۹ [. بسته به ماهيت مسائل مختلف، شيوههاي کدگذاري نيز متفاوت ميباشد.نمونه ساختار يک کروموزوم در شکل (۴-۱) به دليل ساختار مسئلهي جريان کارگاهي

مطلب مشابه :  پایان نامه با کلید واژه های آخرالزمان