الگوریتم های تکاملی

الگوریتم ژنتیک
الگوریتم های ژنتیک دسته ای از الگوریتم های جستجوی تکاملی می باشند که با الهام از الگوهای طبیعی طراحی و توسعه داده شده اند. الگوریتم های ژنتیک در هر تکرار، جمعیتی از نقاط فضای جستجو را مورد بررسی قرار داده و ذخیره می نمایند. در الگوریتم های ژنتیک به هر فرد جمعیت، یک كروموزوم گفته می شود. هر كروموزوم نشان دهنده یک نقطه از فضای جستجو و یک راه حل و یا جواب ممکن برای مساله مورد نظر می باشد. هر كروموزوم از تعدادی ژن تشکیل شده است که بسته به نوع نمایش، می تواند مقادیر دودویی، صحیح و یا اعشاری را به خود بگیرند. همچنین نمایش یک كروموزوم می تواند به صورت جایگشت باشد. این الگوریتم ها معمولا قابل اعمال به مسائلی هستند که بتوان آنها را به صورت رشته هایی با طول ثابت نمایش داد.
برای حل یک مساله توسط الگوریتم های ژنتیک، ابتدا باید کدگذاری مناسبی برای نمایش جواب های مساله به شکل یک كروموزوم پیدا کرد. همچنین به یک تابع برازندگی نیاز می باشد که به هر كروموزوم مقداری نسبت دهد که بیان کننده میزان خوب بودن آن جواب (میزان برازندگی آن كروموزوم) می باشد. در این الگوریتم ها نسل جدید با اعمال عملگرهای ژنتیک بر روی كروموزوم-های نسل جاری تولید می گردد.
عملگرهای ژنتیک عبارتند از عملگر انتخاب ، عملگر تولید مجدد یا بازسازی، ترکیب مجدد یا تقاطع و جهش . عملگر انتخاب تعدادی از كروموزومهای نسل جاری را برای اعمال دو عملگر دیگر انتخاب می کند به طوری که، كروموزوم های با برازندگی بالاتر شانس بیشتری برای انتخاب شدن داشته باشند. به عبارت دیگر، جستجو به سمت بخش هایی از فضا که امکان یافتن جواب های با کیفیت بالاتر وجود دارد سوق داده می شود. عملگر ترکیب مجدد در الگوریتم ژنتیک ساده، بر روی یک زوج كروموزوم انتخاب شده اعمال شده و یک زوج كروموزوم دیگر تولید می نماید. عملگرهای ترکیب متنوعی وجود دارند که رایج ترین آنها عملگر ترکیب تک-نقطه ای می باشد که در الگوریتم-های ژنتیک استاندارد به کار گرفته می شود. در این حالت یک نقطه تصادفی بین دو ژن در نظر گرفته می شود و سپس ژن های سمت راست یا چپ این نقطه در زوج ژن انتخاب شده با یکدیگر تعویض می شوند. به عبارت دیگر این عملگر، امکان ترکیب جوابهای جزیی یافت شده تا آن مرحله را می دهد. در اصطلاح الگوریتم های ژنتیک، به جوابهای جزیی با کیفیت بالا، بلوک های سازنده گفته می شود.
به عبارت دیگر، الگوریتم های ژنتیک تعداد زیادی از بلوکهای سازنده را توسط عملگرهای انتخاب و تقاطع بطور ضمنی مورد پردازش قرار می دهند. بنابراین عملگر تقاطع امکان ترکیب بلوک های سازنده و تولید جواب هایی با برازندگی بالاتر را ایجاد می نماید. عملگر دیگری که در الگوریتم های ژنتیک مورد استفاده قرار می گیرد، عملگر جهش می باشد. این عملگر بر روی ژن های تولید شده اعمال شده و مقادیر ژن ها را به صورت تصادفی تغییر می دهد. این عملگر، ویژگی تصادفی و غیر قطعی بودن را به الگوریتم وارد می نماید و امکان فرار از نقاط بهینه محلی را فراهم می نماید. لازم به ذکر است که عملگرهای تقاطع و جهش به ترتیب با احتمالاتی که با عنوان نرخ تقاطع و نرخ جهش شناخته می شوند بر روی كروموزوم های انتخاب اعمال می شوند .
قایل ورد – تعداد صفحات 34

فهرست مطالب

فصل 1 – تعاریف و مقدمات الگوریتم های تکاملی
1-1 الگوریتم ژنتیک
1-1-1 جمعیت
1-1-2 تابع برازندگی
1-1-3 اساس کار الگوریتم های ژنتیک
1-1-4 ویژگیهای الگوریتم های ژنتیک
1-1-5 نخبه گزینی
1-1-6 روشهای انجام انتخاب
1-1-7 كد كردن
1-2-7-1 كدگذاری دودویی
1-2-7-2 كدگذاری جایگشتی
1-2-7-3 كدگذاری ارزشی
1-2-7-4 كدگذاری درختی
1-2 بهینه سازی ذره ای گروهی (PSO)
1-2-1 تشبیه اجتماعی
1-2-2 الگوریتم ابتدایی PSO
1-2-3 تکنیک های PSO
1-2-3-1 PSO پیوسته
1-2-3-2 PSO گسسته ( باینری )
1-2-3-3 تکنیک lBest
1-2-3-4 تکنیک NPSO
1-2-4 توپولوژیهای PSO
1-2-5 پارامترهای PSO
1-3 جمع بندی الگوریتم های تکاملی
منابع و مراجع
فهرست منابع و مراجع