اکتبر 21, 2020

پایان نامه رایگان درمورد نقطه تقاطع، ازدحام ذرات

1 min read
<![CDATA[]]>

13
12
6
11
1
4
10
8
7
2
9
5
3
شکل 4-5 ساختارجواب براي سطر مربوط به بيهوشي براي حالت چهار تيم بيهوشي
حالتهاي مختلف لانهها که نشابه لانهي فوق ميباشد به صورت زير است.
13
12
6
10
8
7
2
11
1
4
9
5
3
13
12
6
11
1
4
10
8
7
2
9
5
3
13
12
6
10
8
7
2
9
5
3
11
1
4
13
12
6
9
5
3
10
8
7
2
11
1
4
11
1
4
9
5
3
11
1
4
10
8
7
2
11
1
4
11
1
4
9
5
3
10
8
7
2
شکل 4-6 تعداد جوابهاي مشابه براي سطر مربوط به بيهوشي براي حالت چهار تيم بيهوشي
همانطور که در ماتريس فوق مشاهده ميشود براي حالت 4 تيم در مرحله بيهوشي 6 لانه مشابه وجود خواهد داشت. با توجه به دو حالت 3 تيم و 4 تيم ميتوان به اين نتيجه رسيد که در حالت کلي اگر در هر مرحله که m_l تيم وجود دارد ?(m?_l-1)! جواب مشابه وجود خواهد داشت. لازم به ذکر است در هر مرحله، زمان سرويس دهي به بيمار توسط تيمي که قابليت انجام عمل مذکور را ندارد، برابر با يک عدد بزرگ مثبت (?) فرض ميگردد.
4-3-2 الگوريتم ژنتيک
الگوريتم ژنتيك، الهامي از علم ژنتيك و نظرية تكامل داروين است و بر اساس بقاي برترين‏ها يا انتخاب طبيعي استوار است. يك كاربرد متداول الگوريتم ژنتيك، استفاده از آن بعنوان تابع بهينه‏كننده است. الگوريتم ژنتيك ابزار سودمندي دربازشناسي الگو، انتخاب ويژگي،درك تصويرو يادگيري ماشيني است (تيسنگ و يانگ7 1997، وفايي8 و همکاران. 1994).در الگوريتم‏هاي ژنتيكي9, نحوه تكامل ژنتيكي موجودات زنده شبيه‏سازي مي‏شود.
الگوريتم‏هاي ژنتيكي را مي‏توان يك روش بهينه‏سازي تصادفي جهت‏دار دانست كه به تدريج به سمت نقطه بهينه حركت مي‏كند. در مورد ويژگي‌هاي الگوريتم ژنتيك در مقايسه با ديگر روش‌هاي بهينه سازي مي‌توان گفت كه الگوريتمي است كه بدون داشتن هيچ گونه اطلاعي از مسأله و هيچ گونه محدوديتي بر نوع متغيرهاي آن براي هر گونه مسأله اي قابل اعمال است و داراي كارآيي اثبات شده‌اي در يافتن بهينه كلي10 مي‌باشد. توانايي اين روش در حل مسائل پيچيده بهينه‌سازي, است كه روش‌هاي كلاسيك يا قابل اعمال نيستند و يا دريافتن بهينه كلي قابل اطمينان نيستند(فوگل11 20).
شبهکد
شبهکد الگوريتم ژنتيک طراحيشده براي حل مساله بهينهسازي فوق در ادامه آورده شدهاست:
شکل 4-7 شبه کد ارائه شده براي الگوريتم ژنتيک
اپراتور تقاطع:
عمل تركيب دو كروموزوم كه همان والدين12 مي باشند و بدست آوردن دو كروموزوم جديد كه فرزندان13 مي باشد را تقاطع مينامند. براي انجام عمل تقاطع روي دو كروموزوم L ژني ابتدا بايد نقطه پيوند را مشخص كنيم اين كار با فراخواني عددي تصادفي بين 1 و L-1 صورت مي پذيرد.
round(l*RND)+1)
سپس ژنهاي دو كروموزوم را از نقطه تقاطع با هم عوض مي كنيم. به منظور تقاطع دو کروموزوم ci(t) و cj(t) از الگوريتم زير استفاده ميشود. به عنوان مثال، نقطه شکست را در اپراتور تقاطع الگوريتم ژنتيک بهشکل زير در نظر بگيريد.
13
12
11
6
1
4
10
8
7
2
9
5
3
13
7
6
12
2
5
9
4
11
3
1
10
8
13
12
11
5
1
2
3
10
4
9
8
6
7
13
5
6
1
12
2
3
11
7
10
8
9
4
شکل 4-8 مثالي براي نشان دادن نحوه عملکرد عملگرها
13
12
11
5
1
2
3
10
7
2
9
5
3
13
5
6
1
12
2
3
4
11
3
1
10
8
13
12
11
6
1
4
10
8
4
9
8
6
7
13
7
6
12
2
5
9
11
7
10
8
9
4
شکل 4-9 نحوه کارکرد عملگر تقاطع الگوريتم ژنتيک و جواب بدست آمده از عملگر تقاطع
نقطه تقاطع براي سطر اول 5 و براي سطر دوم 6 انتخاب شده است که در شکل (3-8) نشان داده شده است. جواب ها در هر سطر از نقطه تقاطع با هم جابجا ميشوند تا جوابهاي جديد بدست بيايد.حواب هاي جديد بدست آمده در شکل (3-9) نشان داده شده است.
در نتيجه فرزندهاي کروموزومهاي شکل (3-8) به شکل (3-9) حاصل ميگردند. ژنهاي تکراري براي هر فرزند به صورت رنگي مشخص شدهاست. براي موجهسازي کروموزمهاي حاصله فرآيند زير تعريف ميگردد. سطر اول مربوط به هر دو گروموزوم توليد شده در نظر گرفته ميشود. اعداد تکراري در هر سطر مشخص ميشود. تعداد اعداد تکراري در هر دو سطر انتخابي هميشه برابر است. براي ازبين بردن اعداد تکراري از ابتدا اعداد تکراري مشخص شده در هر سطر را با يکديگر جابجا ميکنيم تا ديگر عدد تکراري در هر سطر وجود نداشته باشد. همين عمل را مي توان براي سطر دوم موجود در دو جواب بدست آمده براي ازبين بردن اعداد تکراري انجام داد.
13
12
11
5
1
2
3
10
7
4
9
8
6
13
12
11
5
1
2
3
10
7
2
9
5
3
13
12
11
6
1
4
10
8
2
9
5
3
7
13
12
11
6
1
4
10
8
4
9
8
6
7
13
5
6
1
12
2
3
4
11
7
9
10
8
13
5
6
1
12
2
3
4
11
3
1
10
8
13
7
6
12
2
5
9
11
3
10
8
1
4
13
7
6
12
2
5
9
11
7
10
8
9
4
شکل 4-10 فرزندهاي حاصله و عمل موجه سازي
اپراتور جهش:
جهش يكي از پديده هاي علم ژنتيك كه به ندرت در برخي از كروموزوم ها رخ مي دهد و در طي آن فرزندان خصوصياتي پيدا ميكنند كه متعلق به هيچ يك از والدين نمي باشد. نقش جهش در الگوريتم ژنتيك بازگرداندن مواد ژنتيكي گم شده و يا پيدا نشده داخل جمعيت است تا از همگرايي زودرس الگوريتم به جوابهاي بهينه محلي جلوگيري شود. به منظور جهش کروموزوم ci(t) از الگوريتم زير استفاده ميشود. به طور مثال پارامتر دفعات جابجايي ژن در اپراتور جهش را برابر 0.2 در نظر بگيريد.
پس با توجه به تعداد جهش به دست آمده با استفاده از رابطه بالا در سطر اول و دوم هرکدام 2 بار بايد جابجايي انجام بگيرد. اين جابجايي در شکل (3-9) نشان داده شده است. جابجايي براي خانهها به صورت تصادفي انتخاب ميشود.
13
12
11
6
1
4
10
5
7
9
2
8
3
13
12
11
6
1
4
10
8
7
2
9
5
3
13
7
8
12
2
5
10
4
11
3
1
9
6
13
7
6
12
2
5
9
4
11
3
1
10
8
شکل 4-11 نحوه عملکرد عملگر جهش در الگوريتم ژنتيک
4-3-3 الگوريتم جستجوي فاخته
بعد از معرفي شدن روش هاي بهينه سازي تكاملي اوليه مثل الگوريتم ژنتيك، الگوريتم تبريد تدريج1، تحقيقات زيادي روي روش هاي تكاملي بهينه سازي که از طبيعت الهام گرفته شده بودند انجام گرفت، که مي توان به الگوريتم جستجوي فاخته2، الگوريتم ازدحام ذرات (PSO)، كلوني مورچگان (ACO)، الگوريتم زنبور عسل (ABC) و الگوريتم ماهيهاي مصنوعي3 اشاره كرد. که کاربردهاي بسياري در حل مسائل بهينه سازي دارند. در بين اين الگوريتم ها الگوريتم بهينه سازي فاخته يکي از جديدترين و قويترين روش هاي بهينه سازي تكاملي مي باشد كه تاكنون معرفي شده اند. الگوريتم فاخته با الهام از روش زندگي پرنده اي به نام فاخته است که در سال 2009 توسط شين او يانگ و دب ساوش، توسعه يافته است. الگوريتم فاخته بر اساس زندگي گونه اي از فاخته است. اين الگوريتم توسط پرواز لووي4 به جاي پياده روي ايزوتروپتيک تصادفي ساده توسعه يافته است.
فاخته پرندهايست که براي خود لانه نمي سازد و تخم‌هاي خود را در لانه‌ي ديگر پرندگان مي‌گذارد. فاخته در هنگام تخمگذاري در لانه پرندههاي ديگر(ميزبان) ممکن است برخي تخم‌هاي پرنده‌ي ميزبان را از بين ببرد. با اينکار فاخته پرندگان ميزبان را وادار به همکاري در ادامه ي نسل خود مي کند. فاخته لانه‌اي با تخم‌هاي تازه انتخاب ميکند. معمولا تخم فاخته در رنگ و طرح شبيه تخم پرندگان ميزبان است ولي در اندازه اندکي بزرگ‌تر است تا جوجه فاخته‌ها زودتر از از تخم بيرون بيايند. مهارت گذاشتن تخم‌هايي شبيه به تخم يک پرنده‌ي خاص به طور تکاملي در فاخته‌هاي ماده بهبود مي‌يابد. در اين ميان احتمال لو رفتن تخم فاخته توسط پرنده ميزبان نيز وجود دارد. ممکن است پرنده ي ميزبان متوجه چيزي شود. در اين زمان پرنده ميزبان يکي از تخم‌ها را تصادفي از لانه بيرون مي‌اندازند که ممکن است اين تخم يکي از تخم‌هاي خودش باشد. برخي اوقات پرنده ميزبان لانه را ترک مي‌کند و لانه‌ي ديگري براي خود مي‌سازد. تکامل در شباهت براي مقابله با اين وضعيت است.
جوجههاي فاخته شباهت زيادي با جوجه‌هاي ميزبان دارند رفتار غذاخواهي آن ها را تقليد مي‌کنند. جوجههاي فاخته حتي ممکن است تخم‌ها يا جوجه‌هاي پرنده‌ي ميزبان را از لانه بيرون ‌اندازد. يا طي چند روز اول آنقدر غذا مي‌خورد که بقيه از گرسنگي بميرند. جوجه فاخته معمولا تنها جوجه باقيمانده در لانه مي‌شود. الگوريتم جستجوي فاخته با در نظر گرفتن خصوصيت اخلاقي فاخته و توزيع رفتار پرواز پرندگان در فضاي جواب به جستجو ميپردازد.
قوانين جستجوي فاخته
هر فاخته در هر زمان يک تخم مي‌گذارد.
آن را در يک لانه‌ي تصادفي قرار مي‌دهد.
بهترين لانه‌ها با کيفيت بالاي تخم، نسل بعدي را تشکيل مي‌دهند.
تعداد لانه‌هاي ميزبان ثابت است.
تخمي که توسط فاخته گذاشته شده است، با يک احتمال pa ?? [0, 1] توسط پرنده‌ي ميزبان کشف مي‌شود.
در اين حالت پرنده‌ي ميزبان مي‌تواند تخم را دور بياندازد يا لانه را ترک کند و يک لانه‌ي کاملا جديد براي خود بسازد.
کسر Pa از n تعداد لانه‌ها.
اين لانه‌ها با لانه‌هاي جديد (با راه حل‌هاي جديد) جايگزين مي شوند.
هر تخم در هر لانه نمايش دهندهي يک راه حل کانديدا است. يک تخم فاخته که از طريق پرواز لووي به وجود مي آيد، نمايش دهنده ي يک راه حل جديد است n لانه‌ي ميزبان به طور تصادفي در زيستگاه ايجاد مي‌شود. هر کدام از اين لانه‌ها متعلق به يک فاخته است. هر کدام داراي يک تخم (راه حل کانديدا) هستند. اين فاخته‌ها جمعيت اوليه را تشکيل مي‌دهند. براي هر يک ميزان برازندگي محاسبه مي‌شود.
شبهکد
شبهکد الگوريتم جستجوي فاخته طراحيشده براي حل مساله بهينهسازي فوق در ادامه آورده شدهاست:
شکل 4-12 شبه کد ارائه شده در براي الگوريتم جستجوي فاخته
پرواز لووي:
براي پيادهسازي پرواز لووي از رابطه زير استفاده کن.
(3)
(4)
(5)
(6)
(7)
در اين قسمت نحوه عملگر پرواز لووي براي جواب شرح داده ميشود.
13
12
11
5
1
2
3
10
4
9
8
6
7
13
5
6
1
12
2
3
11
7
10
8
9
4
شکل 4-13 يک جواب اوليه براي نمايش نحوه عملکرد عملگرها
به طور مثال با در نظر گرفتن پارامترهاي برابر سه و برابر 1، محاسبات مربوط به فرآيند لووي در زير شرح داده شده است.
0.39
-0.95
-0.51
0.01
-0.46
-1.07
0.35
0.18
-0.08
0.1
0.28
0.44
-1.25
-0.74
-0.32
-3.03
1.24
0.93
-0.03
-1.57
1.6
0.04
1
1
1
-0.37
2.02
2.23
1
-0.59
0.42
0.47
0.07
0.33
1.01
1
-0.03
0.43
-0.24
-2.26
0.34
-1.66
-0.28
-1.67
-1.21
0.65
1.08
-0.65
1.05
-0.47
-0.23
0.01
-0.78
-2.55
0.74
2.57
-0.24
0.1
9.33
1.02
-5.21
-0.33
-0.94
-1.83
4.43
0.56
-0.02
-2.42
1.48
0.06
شکل 4-14 نحوه عملگر پرواز لووي
لانه جديد داراي اعداد اعشاري ميباشد که موجه نيست. براي موجه سازي با توجه به ترتيب اين اعداد ميتوان تناظري يک به يک به شکل (3-5) برقرار]]>

این مطلب را هم بخوانید :  پایان نامه دربارهاسترس، خانواده ها، وجود رابط

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Copyright © All rights reserved. | Newsphere by AF themes.