منابع پایان نامه با موضوع حل مسئله، نرم افزار

نوامبر 28, 2018 0 By admin3

تعيين قانون و تابع کاهش دما و حرکت به سمت سرد شدن سيستم نيازمند ضابطه اي است که به صورت زير ارائه شده است.
تجربه نشان ميدهد بايد عددي بين 0.8 تا 0.99 باشد تا بهترين نتيجه بدست آيد و الگوريتم طولاني نشود ]64[.
ساختار همسايگي جديد:
در الگوريتم شبيه سازي تبريد براي رسيدن به يک حل جديد، نياز است که در ساختار جواب فعلي تغييري ايجاد گردد تا يک همسايگي جديد در فضاي حل پيدا شود. در الگوريتم پيشنهادي اين ساختار همسايگي مشابه عمليات جهش در الگوريتم ژنتيک ميباشد. بدين صورت که دو جزء مختلف از بردار حل نامزد به صورت تصادفي انتخاب ميگردند و سپس محتويات آنها با يکديگر تعويض ميشوند.
رويه ي الگوريتم شبيه سازي تبريد
نمودار ارائه شده در شکل (4-9) مراحل الگوريتم شبيه سازي تبريد را نمايش ميدهند که در براي حل مسئله ي تخصيص متوازن مورد استفاده قرار گرفته است.
نمودار الگوريتم شبيه سازي تبريد هيبريدي براي مسئلهي NWTSFFS
تنظيم پارامترهاي استفاده شده براي الگوريتم ها
از آنجايي که الگوريتم هاي فرا ابتکاري به مقادير پارامترهايشان حساس مي باشند، چندين شبيهسازي انجام شده است تا بهترين مقادير پارامترها براي الگوريتم ها انتخاب گردد. بدين منظور براي هر يک از الگوريتمها، يک پارامتر ثابت نگه داشته شده و ديگر پارامترهاي مربوطه در يک دامنه مختلف تغيير يافته است. اين فرايند شبيه سازي بيش از 5 بار براي هر اندازه مسئله تعريف شده امتحان شده است. بهترين نتايج براي تنظيم پارامترها در جدول (4-1) ارائه شده اند. در الگوريتم ژنتيک هيبريدي با افزايش در اندازهي مسئله، تعداد نسلها افزايش پيدا کرده است تا جوابهاي نزديک به بهينه بهتري حاصل گردد و همچنين در الگوريتم شبيه سازي تبريد هيبريديکه اين باعث شده است تا زمان اجراي الگوريتم افزايش يابد.
محدوده ي پارامترهاي استفاده شده براي الگوريتم هاي HSA و HGA
parameters
Amount
Hybrid Genetic algorithm
Population size
100
Generation number
200~500
Crossover rate
0.5~0.7
Exchange mutation rate
0.4
Hybrid Simulated annealing
algorithm
200~400
0.0001
Iteration number
200-500
0.9
نتايج محاسباتي الگوريتم هاي فراابتکاري
مقدمه
در اين فصل در ابتدا به نحوه طراحي مسائل جهت تست الگوريتم ها در هر فاز خواهيم پرداخت. و در ادامه نتايج مربوط به آزمون ANOVA و آزمون توکي و همچنين مقادير متوسط به دست آمده براي تابع برازندگي به ازاي چندين بار اجراي الگوريتم ها و همچنينزمان اجراي هر يک از الگوريتم ها را مورد بررسي قرار خواهيم داد. گفتني است براي انجام آزمون هاي آماري مورد نظر از شاخص عملکرد انحراف نسبي که در فصل قبل تعريف شد، استفاده شده است.
آزمايشات عددي
در اين بخش در ابتدا پارامترهاي مدل شبيه سازي را تعريف شده و مدل مربوطه توسط زبان برنامه نويسي متلب توسعه داده شده است. پس از آن براي مقايسه الگوريتم پيشنهاد شده با ساير الگوريتم ها آزمايشات عددي تحت شرايط مختلف انجام شده است. به عبارت ديگر الگوريتم هاي HGA و HSA را با الگوريتم MDA که بهترين جواب براي تابع هدف مينيمم سازي ماکزيمم زمان اتمام کارها در مساله مورد مطالعه پيش از اين داشته است، مقايسه مي کنيم. بدين منظور 18 مساله براي سايز کوچک و 18 مساله براي سايز بزرگ در نظر مي گيريم.
پارامترهاي مدل شبيه سازي
پارامترهاي مدل شبيه سازي در جدول (4-2) ليست شده است و جزئيات آن به صورت مشروح در زير آمده است.
پارامترهاي مدل شبيه سازي براي الگوريتم هاي فراابتکاري
مقياس
طبقه
فاکتورها
تعداد سطوح
سطوح
کوچک
1
تعداد ماشين ها
3
بزرگ
3
کوچک
2
تعداد کارها
6
بزرگ
6
کوچک
3
تابع توزيع زمان هاي پردازش
1
بزرگ
1
کوچک
&
بزرگ
4
الگوريتم ها
3
فرايند شبيه سازي
در اين بخش چگونگي اجراي شبيه سازي توضيح داده شده است. مدل اشاره شده در بخش قبل توسط زبان برنامه نويسي متلب نوشته شد و تست ها به منظور ارزيابي الگوريتم ها توسط کامپيوتر شخصي با پردازنده 2.66 GHZ و 4 GB اجرا شد. اين تست ها براي ترکيب هاي مختلفي از پارامترها انجام شد. در انتها نتايج به دست آمده توسط پروسه آناليز واريانس و آزمون توکي نرم افزار 14 Minitab انجام شده است.
نتايج شبيه سازي
نتايج به دست آمده براي مقدار تابع هدف و ميزان زمان اجراي الگوريتم ها در دو سايز کوچک و بزرگ در جدول (4-4) و جدول (4-5) آورده شده است .طبق جدول (4-3) مقدار P-Value به دست آمده کمتر از مقدار مي باشد. لذا فرض تساوي ميانگين الگوريتم ها رد مي شود. در جدول (4-3) فاصله اطمينان 95% براي RD هر يک از الگوريتم ها آورده شده است. فاصله اطمينان به دست آمده براي الگوريتم هاي پيشنهادي HAS و HGA به طور قابل ملاحظه اي با الگوريتم MDA فاصله دارد. با توجه به اينکه فرض صفر آزمون ANOVA يعني برابري ميانگين الگوريتم ها، رد مي شود. بنابراين براي بررسي عملکرد الگوريتم ها از آزمون مقايسات زوجي توکي استفاده مي کنيم. نتايج آزمون توکي نشان داد که هيچيک از الگوريتم ها ميانگين برابر با يکديگر ندارند. لذا جدول ارئه شده براي اين مقايسات که نشان دهنده ي درست نبودن فرض برابري ميانگين هاست ، فاقد علامت ستاره است.
نتايج آماري الگوريتم هاي فراابتکاري
One-way ANOVA: SA, GA, MDA
Source DF SS MS F P
Factor 2 0.38148 0.19074 66.03 0.000
Error 105 0.30331 0.00289
Total 107 0.68479
MDA
HGA
GSA
HSA
HGA
MDA
نتايج به دست آمده براي سايز کوچک
HSA
HGA
MDA
تعداد کارها
تعداد ماشين هاي مرحله اول
تعداد ماشين هاي مرحله دوم
تابع برازندگي
زمان اجرا
تابع برازندگي
زمان اجرا
تابع برازندگي
زمان اجرا
8
3
4
78
3.0313
78
3.4688
100
0.046875
2
2
116
3.0313
116
3.4531
121
0.046875
3
2
115
2.0313
115
3.4531
126
0.0625
10
3
4
104
2.2344
104
1.9375
128
0.046875
2
2
150
2.3438
153
1.9375
165
0.046875
3
2
144
2.2656
143
1.9375
154
0.046875
14
3
4
108
2.8594
109
1.9531
145
0.046875
2
2
157
2.8125
160
1.9844
188
0.046875
3
2
133
2.8125
133
1.9688
137
0.046875
16
3
4
117
2.8281
118
2.5781
171
0.046875
2
2
175
2.9375
179
1.9844
218
0.046875
3
2
156
2.9063
156
2.5781
170
0.046875
20
3
4
174
3.7188
177
3.875
214
0.0625
2
2
261
3.7031
269
3.2831
300
0.046875
3
2
234
3.7813
236
4.3594
247
0.0625
24
3
4
194
4.25
196
5.0313
216
0.046875
2
2
289
4.3438
304
5.0469
305
0.046875
3
2
254
4.4375
256
5.0313
273
0.046875
نتيجه گيري:
خلاصهي نتايج بدين قرار است که هر دو الگوريتم HSA و HGA نسبت به MDA برتري دارند و الگوريتم HSA نسبت به HGA جواب هاي بهتري به دست مي آورد.
نتايج به دست آمده براي سايز بزرگ
HSA
HGA
MDA
تعداد کارها
تعداد ماشين هاي مرحله اول
تعداد ماشين هاي مرحله دوم
تابع برازندگي
زمان اجرا
تابع برازندگي
زمان اجرا
تابع برازندگي
زمان اجرا
72
8
10
1822
41.0156
1856
38.4375
2106
0.0468
10
10
1500
34.7344
1602
38.6406
1782
0.0468
12
10
1395
35.7188
1468
41.3125
1571
0.0458
80
8
10
1959
38
2014
42.4063
2261
0.0615
10
10
1634
37.6406
1724
43.5156
1901
0.0615
12
10
1546
37.7656
1609
43.9365
1719
0.0468
88
8
10
2214
81.3438
2268
71.6719
2543
0.0468
10
10
1840
82.9219
1950
73.75
2153
0.0468
12
10
1691
82.9375
1799
72.7969
1854
0.0634
108
8
10
2454
141.171
2550
100.437
2655
0.0468
10
10
2074
149.921
2231
123.453
2303
0.0468
12
10
1966
147.671
2075
293.156
2128
0.0468
120
8
10
2784
330.791
2949
106.937
3005
0.0634
10
10
2450
169.109
2609
106.75
2582
0.0634
12
10
2321
166.828
2439
108.437
2470
0.0615
132
8
10
3153
229.859
3282
196.625
3496
0.0634
10
10
2656
225.562
2850
197.218
3031
0.0615
12
10
2493
230.546
2611
210.843
2715
0.0615
جمع بندي
در اين فصل، براي مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه دو الگوريتم فرا ابتکاري ژنتيک هيبريدي و شبيه سازي تبريد هيبريدي ارائه شد. اين دو الگوريتم با بهترين الگوريتم ارائه شده تا کنون، براي معيار مينيمم کردن ماکزيمم زمان اتمام کارها مقايسه شده. مقايسه نتايج نشان داد هر دو الگوريتم ارائه شده در سطح معني داري نسبت به الگوريتم MDA بهتر عمل مي کنند. همچنين الگوريتم شبيه سازي تبريد ترکيبي نسبت به الگوريتم ژنتيک هيبريدي بهتر عمل مي کند.
حل مسئله پيش بيني ماکزيمم زمان اتمام کارها
مقدمه
به منظور تخصيص موعد تحويل منطقي، پيش بيني ماکزيمم زمان اتمام کارها به اين هدف کمک مي کند. در زمينه تخصيص موعد تحويل در برخي حوزه ها مطالعاتي صورت گرفته است ولي با توجه به اهميت اين موضوع، تعداد اين پزوهش ها کم مي باشد. در مسئله جريان کارگاهي بدون وقفه چندين ترکيب از توالي کارها وتخصيص ماشين ها وجود دارد. از اينرو پيش بيني زمان اتمام کارها در اينگونه مسائل دشوار است. به اين منظور شبکه عصبي فازي تطبيق پذير را معرفي کرده و در ادامه چگونگي استفاده از اين مدل را ارائه خواهيم داد.
مدل فازي سوگينو
مدل فازي سوگينو (مدل فازي TSK) به وسيله Takagi و Sugeno و Kang ]65 [ در سال 1985 ارائه شد. مدل TSK روشي سيستماتيک براي ايجاد قواعد فازي از مجموعه دادههاي ورودي و خروجي در يک سيستم است. ساختار کلي قاعده فازي سوگينو به شکل زير است:
اگر x مساوي A و y مساوي B باشد آنگاه: f = f(x,y)
در اين رابطه مجموعههاي فازي، در مقدمه قانون و تابع صريح غير فازيf = f(x,y) در نتيجه قانون است. معمولا تابع f(x,y) به صورت يک چندجملهاي از متغيرهاي ورودي x و y است؛ ولي به طور کلي ميتواند هر تابع دلخواهي باشد، مشروط بر اينکه بيان کننده خروجي مدل سيستمي باشد که وروديهاي آن در مقدمه قانون ارائه شده است.
اگر تابع f(x,y) يک چندجملهاي رسته يک باشد، سيستم استنتاج فازي حاصله را “مدل فازي سوگينو رسته يک” و اگر f مقدار ثابتي داشته باشد آن را “مدل فازي سوگينو رسته صفر” نامند. خروجي مدل فازي رسته صفر سوگينو تابع ملايمي از وروديهاي مدل است، مشروط بر اينکه توابع عضويت کنار هم در مقدمه قانون، داراي مناطق مشترک کافي باشند. به عبارت ديگر، داشتن مناطق مشترک در نتيجه قانون تاثير چنداني در ملايم کردن خروجي ندارد بلکه مناطق مشترک (overlap) در مقدمه قانون است که رابطه ورودي و خروجي را ملايم ميکند. در اين مدل، هر قانون يک خروجي صريح دارد و خروجي کل سيستم با دادن وزن به هر کدام از خروجيها و ميانگينگيري از آنها حاصل ميشود. اين روش زمان لازم براي محاسبه فرآيند غيرفازي سازي را از بين ميبرد.
اگر قوانين فازي به صورت رابطه 1 باشد، مدل