الگوریتم ژنتیک و بهینه‌سازی

دانلود پایان نامه
  • در روش انتخاب چرخ رولت به این صورت عمل می‌شود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین یک و صفر تولید شده و سپس عدد مذکور در هر بازه‌ای که قرار گرفت کروموزوم متناظر با آن انتخاب می‌شود. البته روش پیاده کردن چرخ رولت به این شکل است که یک دایره را در نظر گرفته و آن را به تعداد کروموزوم‌ها طوری تقسیم می‌کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می‌گردد.
    انتخاب کلی تصادفی
    این روش توسط بیکر پیشنهاد شد و از الگوریتمی که در شکل 5 آمده پیروی می‌کند. در الگوریتم گفته شده تابع rand() یک عدد حقیقی و تصادفی بین (1،0)تولید می‌کند و ek که مقدار مورد انتظار نامیده می‌شود به صورت زیر محاسبه می‌گردد:
    ek=pop-size * pk
    Begin
    Ptr= Rand();/*Returns random number uniformly distributed in [0,1]*/
    For (sum=i=0;iFor (sum+=ek;sum>ptr;ptr++)
    Select (i);
    End
    3-4-8-3-3. احتمال انتخاب
    این موضوع در مورد چگونگی تعیین احتمال انتخاب کروموزوم‌ها می‌باشد. در بعضی از تکنیک‌های انتخاب احتمال یک کروموزوم متناسب آن بوده که دارای چند عیب می‌باشد. برای مثال در نسل‌های اولیه گرایش برای تسلط تعدادی از کروموزوم‌های برتر بر فرآیند انتخاب وجود دارد در حالی که در نسل‌های آخر وقتی جمعیت به صورت کامل همگرا می‌شود رقابت بین کروموزوم‌ها خیلی جدی نبوده و تقریبا به صورت جستجوی تصادفی در می‌آید. یعنی در نسل‌های اولیه چون مقدار برازش‌ها معمولاً با هم اختلاف زیادی دارند، لذا شانس حضور کروموزومی که برازش آن بیشتر است به مراتب بالاتر می‌باشد.
    در نسل‌های پایانی چون مقدار برازش کروموزوم‌ها به هم نزدیک می‌شود بنابراین انتخاب‌ها تقریبا تصادفی بوده و شانس انتخاب برای اکثر کروموزوم‌ها برابر می‌باشد.
    3-4-9. تابع برازش
    همانطور که دیده شد در فرآیند انتخاب بارها از عبارت کروموزوم مناسب‌تر صحبت به بیان می‌آید. بدیهی است که برای تشخیص کروموزوم مناسب‌تر باید یک شاخص جهت ارزیابی کروموزوم‌ها وجود داشته باشد.
    در مورد مسایل بهینه‌سازی توابع، معمولا این شاخص همان مقدار تابع هدف مسأله می‌باشد، یعنی هر کروموزوم تبدیل به جواب متناظر شده و در تابع هدف قرار می‌گیرد، آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد کروموزوم متناظر با آن جواب مناسب‌تر خواهد بود. اما در مورد بعضی مسایل که پیچیده‌تر هستند باید اقدام به تعریف تابع برازش نمود.
    3-4-10. روش اجرای الگوریتم ژنتیک
    مراحل زیر، مقدمه اجرای الگوریتم ژنتیک است:
    تعیین نحوه نمایش یا کدبندی مسأله
    باید به هر جواب، یک نمود ژنتیکی اختصاص داد. نحوه نمایش مرسوم، در واقع نوعی نگاشت از فضای جستجو به فضای رشته‌هایی با طول Lکه با الفبای K حرفی ساخته شده‌اند می‌باشد:
    به طور معمول k=2 است و رشته‌ها دودویی هستند. نحوه نمایش ارتباط مستقیم با مسأله مورد نظر دارد و معمولا در رسیدن به جواب مناسب اثر بسیاری داشته و باید با دقت انتخاب شود.
    این نوشته در مقالات و پایان نامه ها ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.