دانلود پایان نامه با موضوع الگوریتم ژنتیک، انتخاب طبیعی

دانلود پایان نامه ارشد

ي مرحله بازگشت هر واحد خروجي فعاليت محاسبه شده را با مقدار پاسخ مطلوب مقايسه مي‌كند تا خطاي وابسته را براي آن الگو در آن واحد خاص تعيين كند. بر مبناي اين خطا حساسيت‌ها در لايه آخر محاسبه مي‌شوند كه بعداً براي تغيير دادن وزن‌هاي بين لايه خروجي و لايه مخفي استفاده مي‌شود. به طريق مشابه حساسيت‌ها براي لايه‌هاي مياني نيز محاسبه مي‌شوند. چون توزیع حساسيت‌ها در خلاف مسیر ارتباط وزنی سیناپسها صورت میگیرد، کلمهی پس انتشار خطا براي اين الگوريتم انتخاب شده است. در اين مرحله نيز پارامترهاي شبكه تغيير نخواهند كرد.
تنظيم وزن‌ها و باياس‌ها: پس از تعيين تمامي حساسيت‌ها، وزن‌ها و باياس‌هاي تمامي لايه‌ها به صورت همزمان تنظيم مي‌شوند. پس از اعمال هر زوج ورودي-خروجي به عنوان الگوي يادگيري، بردارهاي ورودي (الگوهاي ورودي) در خلال سه مرحله فوق تغيير نمي‌كنند.
توقف: جهت توقف تكرار الگوريتم پس انتشار خطا از دو شرط زير مي‌توان به صورت همزمان استفاده كرد.
الف) ميانگين مربعات خطا در هر سيكل (جمع مربعات خطا براي تمامي الگوهاي يادگيري) كمتر از مقدار از پيش تعيين شده‌اي باشد و يا اينكه فرم تغييرات در پارامترهاي شبكه پس از هر سيكل خيلي كوچك باشد. بايد توجه داشت كه تعداد تكرار در هر سيكل برابر تعداد نمونه‌هاي يادگيري مي‌باشد. به عنوان مثال اگر 100 جفت داده براي يادگيري وجود داشته باشد، سيكل برابر با 100 مرحله تكرار مي‌شود.
ب) ميانگين گراديان خطا خيلي كوچك بوده و از يك مقدار از پيش تعيين شده‌اي كوچكتر گردد ‏[41].
الگوريتم لونبرگ65
اين الگوريتم براي آموزش شبكههاي عصبي كه شاخص عملكرد آنها MSE است مناسب ميباشد. الگوريتم LM سرعت بالاي روش نيوتن و همگرايي قطعي روش SD را با هم دارا ميباشد. در اين الگوريتم در هر مرحله محاسبات بيشتري انجام ميشود ولي با وجود حجم محاسبات بالاتر، براي شبكههايي كه تعداد پارامترهاي آنها در حد متوسط ميباشد سريعترين الگوريتم آموزش مي‌باشد ‏[42].

مقدمه‌اي بر الگوريتم ژنتيك
الگوريتمهاي ژنتيك در دهه 1960 توسط هلند66 ارايه شد و سپس توسط خود هلند، شاگردان و همكارانش توسعه پيدا كرد. الگوريتم ژنتيک از علم ژنتيک و نظريه تکامل داروين الهام گرفته شده است كه مي‌گويد آن دسته از صفات طبیعی که با قوانین طبیعی سازگاری بیشتری دارند، شانس بقای بیشتری دارند. در واقع قانون انتخاب طبیعی67 بيان مي‌كند که تنها گونههایی از یک جمعیت كه بهترین خصوصیات را داشته باشند ادامه نسل میدهند و آنهایی که این خصوصیات را نداشته باشند به تدریج در طول زمان از بین میروند. به جز در موارد استثنایی که ممکن است جهشهایی در خصوصیات یک فرد در نسل جدید رخ دهد و باعث تغییرات غیرقابل پیشبینی شود، افراد نسل جدید معمولاً سازگاری بیشتری با طبیعت پیرامون دارند.
در الگوريتم ژنتيك،‌ روش‌هاي جستجو بر اساس مكانيزم انتخاب طبيعي و ژنتيك طبيعي ذكر شده در بالا عمل مي‌نمايند. اين الگوريتم‌ها مناسب‌ترين رشته‌ها را از ميان اطلاعات تصادفي سازمان‌دهي‌شده انتخاب مي‌كنند. در هر نسل يك گروه جديد رشته‌ها با استفاده از بهترين قسمت‌هاي رشته‌هاي قبلي و بخش جديد اتفاقي براي رسيدن به جواب مناسب به وجود مي‌آيند. با وجود اينكه اين الگوريتم‌ها تصادفي هستند ولي در گروه الگوريتم‌هاي تصادفي ساده قرار نمي گيرند. آن‌ها به طور كا‌‌رآمدي به كشف اطلاعات گذشته در فضاي جستجو مي‌پردازند تا در يك نقطه جستجوي جديد با پاسخ‌هاي‌ بهتر، به سمت بهترين جواب پيش روند‏[43]، ‏[44].

ساختار الگوريتم ژنتيك
الگوريتم ژنتيك به عنوان يك الگوريتم محاسباتي بهينه ‌سازي با در نظر گرفتن مجموعه‌اي از نقاط فضاي جواب در هر تكرار محاسباتي، به نحو موثري نواحي مختلف فضاي جواب را جستجو مي‌كند. در الگوريتم ژنتيك بايد فضاي طراحي68 که شامل جواب هاي مختلف مسئله ميباشد به فضاي ژنتيک69 تبديل شود. بنابراين الگوريتم ژنتيك با يك سري از متغيرهاي كد شده كار ميكند. براي اينکه بتوان از الگوريتم ژنتيک استفاده نمود و عملگرهاي متفاوت آن را بر روي فضاي طراحي اعمال نمود تا نسلهاي بعدي به تدريج بهبود يابند بايد اين فضاي طراحي را به فرم استانداردي درآورد.
براي اين منظور هر يک از جوابهاي مسئله به صورت يک رشته در نظر گرفته ميشوند که کروموزوم70 ناميده ميشود. در واقع هر كروموزوم رشتهاي است كه حاوي اطلاعات مربوط به جواب مسئله ميباشد. به مجموعهاي از اين كروموزومها كه نشاندهنده يك مجموعه جواب مسئله ميباشند جمعيت71 اطلاق ميشود. هر كروموزوم شامل تعدادي ژن72 ميباشد كه هر يك از اين ژنها نشان دهنده يك ويژگي خاص از جواب مسئله مي باشند. هر ژن بسته به نوع کدگذاري73 و دقت مورد نظر از تعدادي بيت يا آلل74 تشكيل ميشود. در شکل (‏29) ساختار يك كرموزوم نمايش داده شده است كه از 4 ژن تشكيل شده است و هر يك از اين ژنها نيز شامل 4 بيت ميباشند ‏[45].

شکل (‏29): نمايش ژن‌ها در يك كروموزوم

به طور کلي فلوچارت مربوط به بهينه سازي با روش الگوريتم ژنتيک به صورت شکل (10-2) می‌باشد.

شکل (‏210): فلوچارت الگوريتم ژنتيك
با توجه به اين فلوچارت الگوريتم ژنتيك با يک جمعيت اوليه آغاز مي شود يعني در ابتداي کار يک سري جواب يا راه حل براي مسئله وجود دارد که به منظور رسيدن به جواب بهينه بايد اصلاح شوند. اين جمعيت اوليه در ابتداي امر به صورت کاملاً تصادفي تعيين ميشود. مرحله بعدي ارزيابي کروموزومها ميباشد يعني هر يک از اين جوابها به چه ميزان نسبت به هم ارجحيت دارند و يا اينکه به جوابهاي بهينه نزديکتر هستند. براي اين کار از تابع برازندگي75 استفاده ميشود که به آن تابع هزينه76 نيز گفته ميشود. برازندگي يك عضو در الگوريتم ژنتيك مساوي با مقداري است كه تابع برازندگي به آن نسبت ميدهد. براي تعيين ميزان برازندگي، كروموزومها بايد ديكد (رمزگشايي) شوند. تعيين ميزان برازندگي شاخصي براي ارزيابي نحوه عملکرد افراد در فضاي جستجو ميباشد بدين معني كه برازندگي هر يك از افراد جمعيت نشان دهنده ميزان مطلوبيت آن فرد نسبت به بقيه افراد و نزديكي آن به جواب نهايي مسئله ميباشد.
براي ارزيابي برازندگي افراد در مسائل مختلف بهينهسازي با توجه به نوع مسئله دو روش مختلف وجود دارد. در مسايل ساده ميتوان توابع رياضي مشخصي را بيان كرد تا بتوان از طريق آنها برازندگي افراد جمعيت را تعيين نمود اما در برخي از مسايل پيچيده نميتوان رابطه رياضي خاصي ارايه داد و بايد از روشهاي عددي براي تعيين برازندگي استفاده كرد. سپس شرط پايان الگوريتم وجود دارد.
در عمل چندین گزینه براي شرط پایان الگوریتم ژنتیک وجود دارد که اين شروط بايد به گونهاي تعيين شوند که وقتي الگوريتم به جواب بهينه کلي رسيد آن را متوقف نمايد. در هر صورت همواره مشخص است که جمعيت اوليه نميتواند جواب بهينه مسئله باشد بنابراين مراحل انتخاب77 و تقاطع78 و جهش79 نيز بايد اجرا شوند. در واقع اينها هر يک عملگرهايي هستند که به کمک آنها نسل جديد كروموزومها از روي نسل قبلي به وجود ميآيند. مجموعه اين عمليات را ميتوان عمليات توليد نسل جديد80 ناميد. پس از توليد نسل جديد بايد دوباره ميزان برازندگي کروموزومهاي آن ارزيابي شوند و كنترل شود كه آيا جواب بهينه مسئله بدست آمده يا خير؟. اين فرآيند تا جايي بايد تکرار شود که الگوريتم جمعيت اوليه را به جمعيت بهينهاي سوق دهد که جواب بهينه کلي مسئله را شامل شود.
تا اينجا شرح مختصري از الگوريتم ژنتيك ارايه شد در ادامه کدگذاري ، انتخاب ، توليد مثل و جهش و انواع آنها در الگوريتم ژنتيك شرح داده شدهاند.
كدگذاري
الگوريتم ژنتيك به جاي كار بر روي پارامترها يا متغيرهاي يك مسئله، با شكل كد شده آنها سر و كار دارد. در واقع با کدگذاري، فضاي طراحي يا فضاي جستجو به فضاي استانداردي تبديل ميشود که ميتوان عملگرهاي الگوريتم ژنتيك را به نحو مناسبي روي آن پياده کرد. روشهاي متنوعي براي كدگذاري وجود دارد. انتخاب روش مناسب به مسئله مورد بررسي بستگي دارد. در ادامه چند نمونه از روشهاي كدگذاري مورد استفاده در الگوريتم ژنتيك شرح داده شده اند.
كدگذاري دو دويي
اين نوع کدگذاري سادهترين و در عين حال متداولترين روش کدگذاري دادههاي ورودي الگوريتم ژنتيک ميباشد. مطابق شکل (‏211)، در اين روش دادههاي ورودي به صورت رشتهاي از اعداد صفر و يک وارد الگوريتم ميشوند. هر بيت در رشته ميتواند نمايانگر يكي از مشخههاي جواب مسئله باشد بنابراين هر رشته يك جواب براي مسئله مورد بررسي ميباشد ولي لزوماً بهترين جواب نيست. طول رشته بستگي به دقت جواب دارد. معمولاً به الگوريتمهايي که با اين روش کدگذاري ميشوند الگوريتمهاي ژنتيک دودويي نيز گفته ميشود ‏[46].

1 1 1 0 0 0 1 0
كروموزوم 1
0 1 1 1 1 0 1 1
كروموزوم 2
شکل (‏211): كدگذاري باينري

كدگذاري جايگشتي81
در اين روش از اعداد صحيح براي انجام عمليات کدگذاري استفاده ميشود. اين روش كدگذاري براي مواقعي كه برازندگي يك عضو وابسته به موقعيت ژن‌ها روي كروموزوم باشد مانند مسايل مرتبسازي، مفيد مي‌باشد. براي اين گونه مسايل براي جلوگيري از يكسان شدن كروموزومها بعد از اعمال تقاطع و جهش بايد اصلاحاتي در اين عملگرها صورت گيرد. این روش کدگذاری در شکل (‏212) نمایش داده شده است.

1 5 3 2 6 4 7 9 8
كروموزوم A
8 5 6 7 2 3 1 4 9
كروموزوم B
شکل (‏212): كدگذاري جايگشتي

كدگذاري مقداري82
در اين روش کروموزومها به صورت رشتهاي از مقادير کدگذاري ميشوند که اين مقادير ميتوانند هر چيز مرتبط با دادههاي ورودي مسئله مانند اعداد اعشاري ، عبارات منطقي و يا حروف الفبا و غيره باشند (شکل (‏213)). اين روش براي برخي مسايل خاص مناسب است و اغلب لازم ميباشد تا عملگرهاي بازتركيب و جهش متناسب با مسئله تعريف شوند.

1.2324 5.3243 0.4556 2.3293 2.4545
كروموزوم A
ABDJEFIFJDHDIERJFDLDFLFEGT
كروموزوم B
(back), (right), (left), (forward), (left)
كروموزوم C
شکل (‏213): كدگذاري مقداري

انتخاب
انتخاب، فرايند گزينش دو والد از جمعيت جهت انجام تقاطع ميباشد. در انتخاب، اعضایی که برازندگي83 بالاتری دارند انتخاب ميشوند به اين اميد كه فرزندان آنها بعد از تقاطع ميزان برازندگي بيشتري داشته باشند. كروموزومهاي انتخاب شده از جمعيت اوليه والديني هستند كه در توليد مثل شركت ميكنند. در شکل (‏214) به صورت ساده نحوه انجام انتخاب نشان داده شده است.

شکل (‏214): نحوه انجام انتخاب

در انتخاب، كروموزومها به صورت تصادفي و بر اساس تابع برازندگي انتخاب ميشوند. هرچه ميزان برازندگي يك عضو در جمعيت بيشتر باشد شانس انتخاب بيشتري دارد. براي انتخاب كروموزومها روشهاي مختلفي وجود دارد. در ادامه چند روش پركاربرد انتخاب شرح داده شده است ‏[46].
روش چرخ گردان84
اين روش يکي از متداول ترين روشهاي انتخاب ميباشد. در اين روش احتمال انتخاب هر عضو متناسب با مقدار برازندگي آن عضو ميباشد. روش چرخ گردان را ميتوان به اين صورت بيان نمود: ارزش هر عضو برابر با ميزان برازندگي آن عضو تقسيم بر ميزان برازندگي كل جمعيت ميباشد. به هر عضو يك قطاعي از چرخ اختصاص داده ميشود كه اندازه آن قطاع متناسب با ارزش آن عضو مي‌باشد. چرخ N بار ميچرخد كه N برابر تعداد اعضاي نسل بعد ميباشد. براي انجام عمل انتخاب، عددي تصادفي بين صفر و مجموع برازندگيها انتخاب ميشود و کروموزومي که عدد تصادفي انتخاب شده، در محدوده آن بر روي محيط دايره واقع شده باشد براي عمل توليد مثل انتخاب ميشود.
از لحاظ عملكردي روش چرخ گردان يك روش انتخاب نسبتاً متوسط ميباشد زيرا هيچ ضمانتي براي انتخاب اعضاي با برازندگي بالا وجود ندارد و فقط احتمال انتخاب آنها نسبت به

پایان نامه
Previous Entries دانلود پایان نامه با موضوع شبکه عصبی Next Entries دانلود پایان نامه با موضوع الگوريتم، كروموزوم، جمعيت