تحقیق جامع در مورد الگوریتم ژنتیک: بررسی استراتژی ها و عملگرهاي الگوريتم ژنتيك

مكانيزم الگوريتم ژنتيك :الگوريتم ژنتيك به عنوان يك الگوريتم محاسباتيِ بهينهسازي با در نظر گرفتن مجموعهاي از نقاط فضاي جواب در هر تكرار محاسباتي به نحو مؤثري نواحي مختلف فضاي جواب را جستجو ميكند. در مكانيزم جستجو گرچه مقدار تابع هدف تمام فضاي جواب محاتحقیق جامع در مورد الگوریتم ژنتیک: بررسی استراتژی ها و عملگرهاي الگوريتم ژنتيك|30014468|superior-brain|تحقیق جامع در مورد الگوریتم ژنتیک: بررسی استراتژی ها و عملگرهاي الگوريتم ژنتيك
با ما همراه باشید با موضوع تحقیق جامع در مورد الگوریتم ژنتیک: بررسی استراتژی ها و عملگرهاي الگوريتم ژنتيك

مكانيزم الگوريتم ژنتيك :الگوريتم ژنتيك به عنوان يك الگوريتم محاسباتيِ بهينه‌سازي با در نظر گرفتن مجموعه‌اي از نقاط فضاي جواب در هر تكرار محاسباتي به نحو مؤثري نواحي مختلف فضاي جواب را جستجو مي‌كند. در مكانيزم جستجو گرچه مقدار تابع هدف تمام فضاي جواب محاسبه نمي‌شود ولي مقدار محاسبه شده تابع هدف براي هر نقطه، در متوسط‌گيري آماري تابع هدف براي هر نقطه، در متوسط‌گيري آماري تابع هدف در كليه زير فضاهايي كه آن نقطه به آنها وابسته بوده دخالت داده مي‌شود و اين زير فضاها به طور موازي از نظر تابع هدف متوسط‌گيري آماري مي‌شوند. اين مكانيزم را توازي ضمني مي‌گويند. اين روند باعث مي‌شود كه جستجوي فضا به نواحي از آن كه متوسط آماري تابع هدف در آنها زياد بوده و امكان وجود نقطه بهينه مطلق در آنها بيشتر است سوق پيدا كند. چون در اين روش برخلاف روش‌هاي تك‌مسيري فضاي جواب به طور همه جانبه جستجو مي‌شود، امكان كمتري براي همگرايي به يك نقطه بهينه محلي وجود خواهد داشت.



امتياز ديگر اين الگوريتم آن است كه هیچ محدوديتي براي تابع بهينه شونده، مثل مشتق‌پذيري يا پيوستگي لازم ندارد و در روند جستجو خود تنها به تعيين مقدار تابع هدف در نقاط مختلف نياز دارد و هيچ اطلاعاتِ كمكي ديگري، مثل مشتق تابع را استفاده نمي‌كند. لذا مي‌توان در مسائل مختلف اعم از خطي، پيوسته يا گسسته استفاده مي‌شود و به سهولت با مسائل مختلف قابل تطبيق است.در هر تكرار هر يك از رشته‌هاي موجود در جمعيت رشته‌ها، رمزگشايي شده و مقدار تابع هدف براي آن به دست می‌آید. بر اساس مقادیر به دست آمده تابع هدف در جمعیت رشته‌ها، به هر رشته يك عدد برازندگي نسبت داده مي‌شود. اين عدد برازندگي احتمال انتخاب را براي هر رشته تعيين خواهد كرد. بر اساس اين احتمال انتخاب، مجموعه‌اي از رشته‌ها انتخاب شده و با اعمال عملكردهاي ژنتيكي روي آنها رشته‌هاي جديد جايگزين رشته‌هايي از جمعيت اوليه مي‌شوند تا تعداد جمعيت رشته‌ها در تكرارهاي محاسباتي مختلف ثابت باشد.



مكانيزم‌هاي تصادفي كه روي انتخاب و حذف رشته‌ها عمل مي‌كنند به گونه‌اي هستند كه رشته‌هايي كه عدد برازندگي بيشتري دارند، احتمال بيشتري براي تركيب و توليد رشته‌هاي جديد داشته و در مرحله جايگزيني نسبت به ديگر رشته‌ها مقاوم‌تر هستند. بدين لحاظ جمعيت دنباله‌ها در يك رقابت بر اساس تابع هدف در طيّ نسل‌هاي مختلف، كامل شده و متوسط مقدار تابع هدف در جمعيت رشته‌ها افزايش مي‌يابد. بطور كلي در اين الگوريتم ضمن آنكه در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاطي جديد از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجوي نواحي از فضا را كه متوسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. بر اساس سيكل اجرايي فوق، در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاط جديدي از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجو نواحي از فضا را كه توسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. که بر این اساس، در هر تكرار محاسباتي، سه عملگر اصلي روي رشته‌ها عمل مي‌كند؛ اين سه عملگر عبارتند از: دو عملگر ژنتيكي و عملكرد انتخابي تصادفي.



«گلد برگ » الگوريتم ژنتيكي «جان هولند» را با عنوان الگوريتم ژنتيك ساده معرفي مي‌كند؛ الگوريتم ژنتيك را از الگوريتم ژنتيك طبيعي اقتباس كردند.بدن همه موجودات زنده از سلول‌ها تشكيل شده است و در هر سلولي دسته كروموزوم‌هاي يكساني وجود دارد. كروموزوم‌ها رشته‌هايي از DNA هستند كه در واقع الگويي براي تمام بدن هستند. هر كروموزومي محتوي دسته‌هايي DNA است كه ژن ناميده مي‌شوند و هر ژني پروتئين خاصي را رمزگذاري مي‌كند. اساساً مي‌توان گفت كه هر ژن، ويژگي خاصي (مثلا رنگ چشم) را رمزگذاري مي‌كند. حالت‌هاي مختلف يك خصيصه (آبي، قهوه‌اي) آلل ناميده مي‌شود. هر ژني موقعيت خاص خود را بر روي كروموزوم دارد كه اين موقعيت لوكاس ناميده مي‌شود. مجموعه كاملي از مواد ژنتيكي (همۀ كروموزوم‌ها) ژنوم ناميده مي‌شود. دستۀ خاصي از ژن‌هاي موجود در ژنوم، ژنوتيپ ناميده مي‌شود. ژنوتيپ به همراه تغييرات پس از تولّد، پايه و اساس فنوتيپ موجود زنده (ارگانيسم)، ويژگي‌هاي فيزيكي و ذهني از قبيل رنگ چشم و هوش و غيره است.در توليد مثل، ابتدا تركيب(يا تغيير) اتفاق مي‌افتد. ژن‌هاي والدين براي ايجاد كروموزوم‌هاي جديد تركيب مي‌شوند. سپس جنين تشكيل شده دچار تغيير مي‌شود. جهش به اين معناست كه عناصر DNA كمي تغيير پيدا مي‌كنند و اين تغييرات اغلب نتيجه نسخه‌برداري غلط از ژن‌هاي والدين است. ميزان شايستگي موجود زنده(جنين) به واسطه بقاي آن اندازه گيري مي‌شود.



در الگوريتم ژنتيك، مجموعه اي از متغيرهاي طراحي را توسط رشته‌هايي با طول ثابت يا متغير كدكذاري مي‌كنند كه در سيستم‌هاي بيولوژيكي آنها را كرروموزوم يا فرد مي‌نامند. هر رشته یا کروموزوم يك نقطۀ پاسخ در فضاي جستجو را نشان مي‌دهد. به ساختمان رشته‌ها يعني مجموعه‌اي از پارامترها كه توسط يك كروموزوم خاص نمايش داده مي‌شود ژنوتيپ و به مقدار رمزگشايي آن فنوتيپ مي‌گويند. الگوريتم‌هاي وراثتي فرآيندهاي تكراري هستند، كه هر مرحلۀ تكراري را نسل و مجموعه‌هايي از پاسخ‌ها در هر نسل را جمعيت ناميده‌اند.الگوريتم‌هاي ژنتيك، جستجوي اصلي را در فضاي پاسخ به اجرا مي‌گذارند. اين الگوريتم‌ها با توليد نسل آغاز مي‌شوند كه وظيفه ايجاد مجموعه نقاط جستجوي اوليه به نام «جمعيت اوليه» را بر عهده دارند و به طور انتخابي يا تصادفي تعيين مي‌شوند. از آنجايي كه الگوريتم‌هاي ژنتيك براي هدايت عمليات جستجو به طرف نقطه بهينه از روش‌هاي آماري استفاده مي‌كنند، در فرآيندي كه به انتخاب طبيعي وابسته است، جمعيت موجود به تناسب برازندگي افراد آن براي نسل بعد انتخاب مي‌شود. سپس عملگرهاي ژنتيكي شامل انتخاب ، پيوند(ترکیب)، جهش و ديگر عملگرهاي احتمالي اِعمال شده و جمعيت جديد به وجود مي‌آيد. پس از آن جمعيت جديدي جايگزين