شرط پایان الگوریتم و الگوریتم ژنتیک

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

تعریف میزان برازندگی

  • ارزیابی هر رشته از لحاظ میزان بهینگی، بر اساس نحوه رفتار حاصل از آن و از طریق محاسبه تابع هدف و اختصاص عدد برازندگی به آن صورت می‌گیرد. در واقع برازندگی یک نگاشت از نقاط فضای نمایش به فضای اعداد حقیقی است.
    تعیین پارامترها و متغیرهای مربوط به روش
    پارامترهای الگوریتم ژنتیک در درجه اول اهمیت عبارتند از میزان جمعیت و ماکزیمم تعداد تکرار و در درجه دوم اهمیت عبارتند از درصدهای ترکیب و جهش (و در بعضی روش‌ها، تکثیر، مهاجرت، نخبه پروری و …)
    مشخص کردن شرط پایان و نحوه انتخاب خروجی الگوریتم ژنتیک
    شرط پایان الگوریتم را می‌توان انجام تعداد مشخصی تکرار یا رسیدن به مقدار معینی از برازندگی قرار داد. پس از طی این مقدمات، الگوریتم ژنتیک را می‌توان مطابق شبه برنامه زیر انجام داد.
    گام صفر (تعیین مقادیر اولیه): تعیین M رشته به طور تصادفی به عنوان جمعیت اولیه، حداکثر تعداد تکرار tmax، تعیین درصدهای pc برای برش، pi برای مهاجرت، pe برای نخبه پروری و pm برای جهش. سپس قرار می‌دهیم t=0 و میزان برازندگی هر رشته را محاسبه می‌کنیم.
    گام اول (شرط توقف): اگر t=tmax و یا همگرایی به حد دلخواه از لحاظ برازندگی رسیده است، بهترین جواب در تکرار جاری به عنوان جواب تقریبا بهینه می‌باشد و الگوریتم خاتمه می‌یابد.
    گام دوم (نخبه پروری): به تعداد pe رشته از بهترین جواب‌های نسل جاری را به نسل t+1 کپی می‌کنیم.
    گام سوم (مهاجرت): به تعداد pi جواب ممکن جدید به طور دلخواه تولید و به مخزن جواب انتقال می‌دهیم.
    گام چهارم (برش): به تعداد pe/2 زوج رشته‌های متمایز از نسل جاری (t) انتخاب و عمل برش یا ترکیب را بر روی هر دوتای آنها اعمال و جواب‌های حاصل را به مخزن جواب انتقال می‌دهیم.
    گام پنجم (جهش): به تعداد pm رشته از تکرار جاری انتخاب و جهش روی هر کدام انجام و به مخزن جواب‌ها انتقال می‌دهیم.
    گام ششم (انتخاب): از مخزن جواب به اندازه M-Pe رشته انتخاب و به نسل t+1 انتقال می‌دهیم.
    گام هفتم (افزایش):t:=t+1 و به گام اول می‌رویم.
    تغییر در جزئیات این مراحل، روش‌های مختلف ژنتیک را ایجاد می‌کند.
    3-4-11. استراتژی برخورد با محدودیتها
    بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیت‌های مسأله می‌باشد زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم‌های غیرموجه می‌شود. میکالویچ چند تکنیک معمول جهت مواجهه با محدودیت، تقسیم بندی نموده است که در ادامه به چند تا از آنها اشاره می‌شود.
    3-4-11-1. استراتژی اصلاح عملگرهای ژنتیک
    یک روش برای جلوگیری از تولید کروموزوم غیر موجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم‌ها، کروموزوم تولید شده نیز موجه باشد. در این حالت یکسری مشکلات وجود دارد. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مسأله‌ای به مسأله دیگر متفاوت می‌باشد.
    3-4-11-2. استراتژی ردی
    در این روش پس از تولید هر کروموزوم آن را از نظر موجه‌بودن تست کرده و در صورت غیرموجه بودن حذف می‌گردد. این روش بسیار ساده و کارا می‌باشد.
    3-4-11-3. استراتژی اصلاحی
    این نوشته در مقالات و پایان نامه ها ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.