مروري بر الگوريتم‏هاي ژنتيكي - Artificial Intelligence

**Astaraki** · ۱۱-۱۴-۱۳۸۹, ۱۱:۴۱ قبل از ظهر

مروري بر الگوريتم‏هاي ژنتيكي

ژنتيك، الهامي از علم ژنتيك و نظرية تكامل داروين است و بر اساس بقاي برترين‏ها يا انتخاب طبيعي استوار است. يك كاربرد متداول الگوريتم ژنتيك، استفاده از آن بعنوان تابع بهينه‏كننده است. الگوريتم ژنتيك ابزار سودمندي دربازشناسي الگو ،انتخاب ويژگي،درك تصويرو يادگيري ماشيني است. در الگوريتم‏هاي ژنتيكي, نحوه تكامل ژنتيكي موجودات زنده شبيه‏سازي مي‏شود.اگرچه كارهايي توسط يك زيست شناس به نام Fraser در زمينه مدل سازي تكامل در سيستم‌هاي بيولوژيك در دهه 60 ميلادي صورت گرفت ولي الگوريتم ژنتيك براي كاربردهاي مهندسي و به صورت امروزي آن نخستين بار توسط جان هلندمتخصص علوم كامپيوتر دانشگاه ميشيگان در سال 1975 پيشنهاد گرديد. كار وي آغاز تمامي كوشش ها براي كاربرد الگوريتم ژنتيك در مهندسي است . پس از آن كارهاي Dejong در سال 1975 در زمينه بررسي و مقايسه چندين روش الگوريتم ژنتيك پايه‌هاي نظري بحث را فراهم آورد. اين الگوريتم با الهام از طبيعت بر پايه اصل تكاملي «پايداري بهترين‌ها» (Survival of the fittest) استوار است. الگوريتم ژنتيك اگرچه پس از الگوريتم استراتژي تكاملي پيشنهاد گرديد ولي مشهورترين روش از بين الگوريتم‌هاي تكاملي است.در يك الگوريتم ژنتيك يك جمعيت از افراد طبق مطلوبيت آنها در محيط بقا مي يابند. افرادي با قابليتهاي برتر، شانس ازدواج وتوليد مثل بيشتري را خواهند يافت. بنابراين بعد از چند نسل فرزنداني با كارايي بهتر بوجود مي‌آيند. در الگوريتم ژنتيك هر فرد از جمعيت بصورت يك كروموزوم معرفي مي‌شود. كروموزومها در طول چندين نسل كاملتر مي‌شوند. در هر نسل كروموزومها ارزيابي مي‌شوند و متناسب با ارزش خود امكان بقا و تكثيرمي‌يابند. توليد نسل در بحث الگوريتم ژنتيك با عملگرهاي همبري و جهشصورت مي‏گيرد.والدين برتر بر اساس يك تابع برازندگي انتخاب مي‌شوند.
در هر مرحله از اجراي الگوريتم ژنتيكي, يك دسته از نقاط فضاي جستجو مورد پردازش‏هاي تصادفي قرار مي‏گيرند. به اين صورت كه به هر نقطه دنباله‏اي از كاراكترها نسبت داده مي‏شود و بر روي اين دنباله‏ها, عملگرهاي ژنتيكي اعمال مي‏شود. سپس دنباله‏هاي بدست آمده ديكد مي‏گردد تا نقاط جديدي در فضاي جستجو بدست آيد. در آخر براساس اين كه تابع هدف در هر يك از نقاط چه مقدار باشد, احتمال شركت نمودن آنها در مرحله بعد تعيين مي‏گردد]1-5[.

الگوريتم‏هاي ژنتيكي را مي‏توان يك روش بهينه‏سازي تصادفي جهت‏دار دانست كه به تدريج به سمت نقطه بهينه حركت مي‏كند. در مورد ويژگي‌هاي الگوريتم ژنتيك در مقايسه با ديگر روش‌هاي بهينه سازي مي‌توان گفت كه الگوريتمي است كه بدون داشتن هيچ گونه اطلاعي از مسئله و هيچ گونه محدوديتي بر نوع متغيرهاي آن براي هر گونه مسئله اي قابل اعمال است و داراي كارآيي اثبات شده‌اي در يافتن بهينه كلي (Global Optimum) مي‌باشد. توانايي اين روش در حل مسائل پيچيده بهينه‌سازي, است كه روش‌هاي كلاسيك يا قابل اعمال نيستند و يا دريافتن بهينه كلي قابل اطمينان نيستند.

منبع