پایان نامه درمورد ، -، ژنتيكي، برازندگي، رشته‌ها، عملگرهاي، الگوریتم‌های، ژنتیک

الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند.
مكانيزم الگوريتم ژنتيكالگوريتم ژنتيك به عنوان يك الگوريتم محاسباتيِ بهينه‌سازي با در نظر گرفتن مجموعه‌اي از نقاط فضاي جواب در هر تكرار محاسباتي به نحو مؤثري نواحي مختلف فضاي جواب را جستجو مي‌كند. در مكانيزم جستجو گرچه مقدار تابع هدف تمام فضاي جواب محاسبه نمي‌شود ولي مقدار محاسبه شده تابع هدف براي هر نقطه، در متوسط‌گيري آماري تابع هدف در كليه زير فضاهايي كه آن نقطه به آنها وابسته بوده دخالت داده مي‌شود و اين زير فضاها به طور موازي از نظر تابع هدف متوسط‌گيري آماري مي‌شوند. اين مكانيزم را توازي ضمني مي‌گويند. اين روند باعث مي‌شود كه جستجوي فضا به نواحي از آن كه متوسط آماري تابع هدف در آنها زياد بوده و امكان وجود نقطه بهينه مطلق در آنها بيشتر است سوق پيدا كند. چون در اين روش برخلاف روش‌هاي تك‌مسيري فضاي جواب به طور همه جانبه جستجو مي‌شود، امكان كمتري براي همگرايي به يك نقطه بهينه محلي وجود خواهد داشت.
امتياز ديگر اين الگوريتم آن است كه هیچ محدوديتي براي تابع بهينه شونده، مثل مشتق‌پذيري يا پيوستگي لازم ندارد و در روند جستجو خود تنها به تعيين مقدار تابع هدف در نقاط مختلف نياز دارد و هيچ اطلاعاتِ كمكي ديگري، مثل مشتق تابع را استفاده نمي‌كند. لذا مي‌توان در مسائل مختلف اعم از خطي، پيوسته يا گسسته استفاده مي‌شود و به سهولت با مسائل مختلف قابل تطبيق است.
در هر تكرار هر يك از رشته‌هاي موجود در جمعيت رشته‌ها، رمزگشايي شده و مقدار تابع هدف براي آن به دست می‌آید. بر اساس مقادیر به دست آمده تابع هدف در جمعیت رشته‌ها، به هر رشته يك عدد برازندگي نسبت داده مي‌شود. اين عدد برازندگي احتمال انتخاب را براي هر رشته تعيين خواهد كرد. بر اساس اين احتمال انتخاب، مجموعه‌اي از رشته‌ها انتخاب شده و با اعمال عملكردهاي ژنتيكي روي آنها رشته‌هاي جديد جايگزين رشته‌هايي از جمعيت اوليه مي‌شوند تا تعداد جمعيت رشته‌ها در تكرارهاي محاسباتي مختلف ثابت باشد. مكانيزم‌هاي تصادفي كه روي انتخاب و حذف رشته‌ها عمل مي‌كنند به گونه‌اي هستند كه رشته‌هايي كه عدد برازندگي بيشتري دارند، احتمال بيشتري براي تركيب و توليد رشته‌هاي جديد داشته و در مرحله جايگزيني نسبت به ديگر رشته‌ها مقاوم‌تر هستند. بدين لحاظ جمعيت دنباله‌ها در يك رقابت بر اساس تابع هدف در طيّ نسل‌هاي مختلف، كامل شده و متوسط مقدار تابع هدف در جمعيت رشته‌ها افزايش مي‌يابد. بطور كلي در اين الگوريتم ضمن آنكه در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاطي جديد از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجوي نواحي از فضا را كه متوسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. بر اساس سيكل اجرايي فوق، در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاط جديدي از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجو نواحي از فضا را كه متوسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. که بر این اساس، در هر تكرار محاسباتي، سه عملگر اصلي روي رشته‌ها عمل مي‌كند؛ اين سه عملگر عبارتند از: دو عملگر ژنتيكي و عملكرد انتخابي تصادفي. «گلد برگ» الگوريتم ژنتيكي «جان هولند» را با عنوان الگوريتم ژنتيك ساده معرفي مي‌كند؛ الگوريتم ژنتيك را از الگوريتم ژنتيك طبيعي اقتباس كردند.. در الگوريتم ژنتيك، مجموعه اي از متغيرهاي طراحي را توسط رشته‌هايي با طول ثابت يا متغير كدكذاري مي‌كنند كه در سيستم‌هاي بيولوژيكي آنها را كرروموزوم يا فرد مي‌نامند. هر رشته یا کروموزوم يك نقطۀ پاسخ در فضاي جستجو را نشان مي‌دهد. به ساختمان رشته‌ها يعني مجموعه‌اي از پارامترها كه توسط يك كروموزوم خاص نمايش داده مي‌شود ژنوتيپ و به مقدار رمزگشايي آن فنوتيپ مي‌گويند. الگوريتم‌هاي وراثتي فرآيندهاي تكراري هستند، كه هر مرحلۀ تكراري را نسل و مجموعه‌هايي از پاسخ‌ها در هر نسل را جمعيت ناميده‌اند.
الگوريتم‌هاي ژنتيك، جستجوي اصلي را در فضاي پاسخ به اجرا مي‌گذارند. اين الگوريتم‌ها با توليد نسل آغاز مي‌شوند كه وظيفه ايجاد مجموعه نقاط جستجوي اوليه به نام «جمعيت اوليه» را بر عهده دارند و به طور انتخابي يا تصادفي تعيين مي‌شوند. از آنجايي كه الگوريتم‌هاي ژنتيك براي هدايت عمليات جستجو به طرف نقطه بهينه از روش‌هاي آماري استفاده مي‌كنند، در فرآيندي كه به انتخاب طبيعي وابسته است، جمعيت موجود به تناسب برازندگي افراد آن براي نسل بعد انتخاب مي‌شود. سپس عملگرهاي ژنتيكي شامل انتخاب ، پيوند(ترکیب)، جهش و ديگر عملگرهاي احتمالي اِعمال شده و جمعيت جديد به وجود مي‌آيد. پس از آن جمعيت جديدي جايگزين جمعيت پيشين مي‌شود و اين چرخه ادامه مي‌يابد.
معمولاً جمعيت جديد برازندگي بيشتري دارد اين بدان معناست كه از نسلي به نسل ديگر جمعيت بهبود مي‌آيد. هنگامي جستجو نتيجه‌بخش خواهد بود كه به حداكثر نسل ممكن رسيده باشيم يا همگرايي حاصل شده باشد و يا معيارهاي توقف برآورده شده باشد.
عملگرهاي الگوريتم ژنتيكالگوريتم ژنتيك از عملگرهاي زير تشكيل شده است:
کدگذاریاين مرحله شايد مشكلترين مرحله حل مسأله به روش الگوريتم باشد. الگوريتم ژنتيك به جاي اينكه بر روي پارامترها يا متغيرهاي مسأله كار كند، با شكل كد شدۀ آنها سروكار دارد. يكي از روشهاي كد كردن، كد كردن دودويي مي باشد كه در آن هدف تبديل جواب مسأله به رشته‌اي از اعداد باينري (در مبناي 2) است.
انتخاب
در مرحله انتخاب، يك جفت از كروموزوم‌ها برگزيده مي‌شوند تا با هم تركيب شوند، عملگر انتخاب رابط بين دو نسل است و بعضي از اعضاي نسل كنوني را به نسل آينده منتقل مي‌كند، بعد از انتخاب، عملگرهاي ژنتيك روي دو عضو برگزيده اعمال مي‌شوند، معيار در انتخاب اعضاء ارزش تطابق آنها مي‌باشد اما روند انتخاب حالتي تصادفي دارد.
بطور کلی روش‌هاي متداول انتخاب در الگوریتم ژنتیک عبارتند از:
انتخاب چرخ رولت – انتخاب مسابقه تصادفي – انتخاب بولتزمن – نخبه سالاري
انتخاب رقابتي – انتخاب قطع سر – انتخاب قطعي بريندل – انتخاب حالت پايدار
انتخاب جايگزيني نسلي اصلاح شده – انتخاب مسابقه (تورنمنت) – انتخاب ترتيبي
ارزیابیتابع برازندگي را از اِعمال تبديل مناسب بر روي تابع هدف يعني تابعي كه قرار است بهينه شود به دست مي‌آورند. اين تابع هر رشته را با يك مقدار عددي ارزيابي مي‌كند كه كيفيت آن را مشخص مي‌نمايد. هر چه كيفيت رشته جواب بالاتر باشد مقدار برازندگي جواب بيشتر است و احتمال مشاركت براي توليد نسل بعدي نيز افزايش خواهد يافت.
ترکیبمهمترين عملگر در الگوريتم ژنتيك، عملگر ترکیب است. تركيب فرآيندي است كه در آن نسل قديمي كروموزوم‌ها با يكديگر مخلوط و تركيب مي‌شوند تا نسل تازه‌اي از كروموزوم‌ها بوجود بيايد.
جفت‌هايي كه در قسمت انتخاب به عنوان والد در نظر گرفته شدند در اين قسمت ژن‌هايشان را با هم مبادله مي‌كنند و اعضاي جديد بوجود مي‌آورند. تركيب در الگوريتم ژنتيك باعث از بين رفتن پراكندگي يا تنوع ژنتيكي جمعيت مي‌شود زيرا اجازه مي‌دهد ژن‌هاي خوب يكديگر را بيابند. متداولترین روشهای ترکیب عبارتند از :
جابه‌جایی دودوئی، جابه‌جایي حقيقي، ترکیب تک‌نقطه‌ای، ترکیب دو نقطه‌ای، ترکیب n نقطه‌ای، ترکیب یکنواخت، ترکیب حسابی، ترتیب، محدّب، بخش نگاشته، چرخه.
جهشجهش نيز عملگر ديگري هست كه جواب‌هاي ممكن ديگري را متولد مي‌كند. در الگوريتم ژنتيك بعد از اينكه يك عضو در جمعيت جديد بوجود آمد هر ژن آن با احتمال جهش، جهش مي‌يابد. در جهش ممكن است ژني از مجموعه ژن‌هاي جمعيت حذف شود يا ژني كه تا به حال در جمعيت وجود نداشته است به آن اضافه شود. جهش يك ژن به معناي تغيير آن ژن است و وابسته به نوع كدگذاري روش‌هاي متفاوت جهش استفاده مي‌شود.
انواع روشهای عملگر جهش عبارتند از :
جهش باينري، جهش حقيقي، وارونه سازی بیت، تغییر ترتیب قرارگیری، وارون سازی، تغییر مقدار.
رمزگشاييرمزگشایی، عكسِ عمل رمزگذاری است. در اين مرحله بعد از اينكه الگوريتم بهترين جواب را براي مسأله ارایه كرد لازم است عكس عمل رمزگذاري روي جواب‌ها يا همان عمل رمزگشایی اعمال شود تا بتوانيم نسخه واقعي جواب را به وضوح در دست داشته باشيم.
نقاط قوّت الگوریتم‌های ژنتیکاولین و مهمترین نقطه قوّت این الگوریتم‌ها این است که الگوریتم‌های ژنتیک ذاتاً موازی‌اند. اکثر الگوریتم‌های دیگر موازی نیستند و فقط

متن کامل در سایت homatez.com

About: admin