بخشی از مقاله
الگوريتم ژنتيك
الگوريتم ژنتيك از روشهاي جستجوي مستقيم اتفاقي است كه بر پايه اصول انتخاب طبيعي و بقاي اصلح قرار دارد. اصطلاحات بكار رفته در الگوريتم ژنتيك كاملاً شبيه واژگان ژنتيك طبيعي است و حتي تشابه نزديكي بين عناصر اين دو وجود دارد. اين روش، اولين بار توسط جان هلند از دانشگاه ميشيگان در سال 1975 پيشنهاد شد.
ساختار اصلي كه توسط الگوريتم پردازش مي‌شود، رشته ( كرموزم ) است. يك رشته زنجيره اي از تعدادي كد ( اغلب كدهايي دوديي ) با طول معلوم است. بيتهاي رشته (صفر يا 1 در يك رشته دودويي) معادل ژنهاي طبيعي‌اند. هر كدام بيانگر يك متغير ( مشابه يك ويژگي در ژنتيك طبيعي همانند رنگ چشم ) و هر مصداق خاصي از كد به طور مستقيم يا غير مستقيم بيانگر مقدار مشخصي از آن متغير است ( معادل مثلاً چشم آبي ).
شكل 1- رشته در الگوريتم ژنتيك شامل پارامترها بصورت كد دودويي است.
كدهاي يك رشته به اندازه تعداد متغيرهاست، پس يك رشته اساسا بيانگر يك جواب ممكن است. با الگوريتم ژنتيك ايجاد يك جمعيت اوليه از رشته‌ها از طريق انتخاب تصادفي مقادير بيتهاي رشته آغاز مي‌شود. تعداد رشته‌ها (كروموزمها) در جمعيت، اندازه جمعيت ناميده مي‌شود. اندازه جمعيت در ابتدا توسط كاربر تعيين مي‌شود يا اينكه بر طبق قاعده‌اي كه بعدا خواهد آمد، توسط كامپيوتر تعيين مي‌شود و در طي جستجو، ثابت نگه داشته مي‌شود.
برازندگي يك رشته (جواب ممكن ) توسط تابع محاسبه مي‌شود. چون الگوريتم ژنتيك دنبال ماكزيمم كردن برازندگي جوابهاي ممكن است، در يك مسأله ماكزيمم سازي، برازندگي برابر مقدار تابع هدف محاسبه شده براي مقادير خاص پارامتر كه هر رشته بيان مي‌كند، مي‌باشد. يعني تابع برازندگي همان تابع هدف است اما در مسأله مينيمم سازي برازندگي با افزايش تابع هدف كاهش مي‌يابد. يك راه براي جبران آن تعريف تابع برازندگي به صورت :
1- تابع هدف- مقدار ثابت = تابع برازندگي
كه مقدار ثابت به اندازه كافي بزرگ انتخاب مي‌شود تا از منفي شدن برازندگي جلوگيري شود. يك مقدار متداول براي اين مقدار ثابت، مجموع و ماكزيمم تابع هدف درهر نسل است.
روش ديگرمعكوس كردن تابع هدف مي‌باشد.
پس از ارزيابي رشته‌هاي نسل صفر، نسل جديد (نسل اول) از برازنده‌ترين اعضاي نسل صفر ايجاد مي‌شود. براي اين كار، در يك فرايند انتخاب آن والدين اعضاي نسل جديد انتخاب مي‌گردد، به هر رشته وزني متناسب با برازندگيش داده مي‌شود. اين فرايند توليد مثل متناسب با برازندگي ناميده مي‌شود و تعداد كپي‌هايي از هر رشته در نسل حاضر را كه به اتاق لقاح مي‌روند، تعيين مي‌كند. رشته‌هاي انتخاب شده شانس آن را مي‌يابند كه در ايجاد رشته‌هاي نسل بعد شركت كنند. هيچ تضميني براي بقاي يك فرد وجود ندارد بلكه تجربه‌هاي تصادفي تصميم مي‌گيرند كه كدام بالاتري، اما نه تضمين، براي بقا دارند.
ساده‌ترين راه براي انجام توليد مثل متناسب با برازندگي شبيه سازي فرايند با عملكرد يك چرخ رولت وزندار است. هر رشته از جمعيت داراي يك قطاع چرخ است كه اندازه آن متناسب با برازندگي آن رشته است. در نتيجه احتمال انتخاب برابر برازندگي نسبي است. يك مسأله در مورد انتخاب چرخ رولت واضح است. فرايند انتخاب نه تنها به رتبه هر فرد بلكه به تعريف دقيق تابع هدف بستگي دارد. هر تبديل غيرخطي تابع برازندگي بر فرايند انتخاب اثر مي‌گذارد. بنابر اين مسأله زير در انتخاب چرخ رولت پيش مي‌آيد : در طي اولين نسل، جمعيت خيلي ناهمگن است. يعني برازندگي افراد خيلي متفاوت است. وقتي كه الگوريتم شروع به همگرا شدن مي‌كند، برازندگي همه افراد خيلي شبيه هم مي‌شود، در نتيجه همه افراد تقريباً با احتمال يكسان بقا مي‌يابند، به عبارت ديگر قدرت انتخاب خيلي كم مي‌شود و الگوريتم ژنتيك به جستجوي اتفاقي تباه مي‌شود. (شكل 2)
شكل 2- ده فرد از بين جمعيت صد عضوي انتخاب مي‌شود. قدرت انتخاب بالاست اگر افراد بهتر بر بدتر ترجيح داده شود. پايين‌ترين قدرت انتخاب ممكن زماني است كه همه افراد مستقل از رتبه‌شان بقا يابند. در اين حالت الگوريتم ژنتيك به جستجوي اتفاقي ناكارا تباه مي‌شود.
براي جلوگيري از اين مسأله، چندين روش براي مقياس بندي مقادير برازندگي پيشنهاد شده است. يك راه حل ساده آن است كه مقادير برازندگي چنان مقياس بندي شود كه بالاترين مقدار همواره به يك و پايين ترين مقدار همواره به صفر نگاشته شود. با چنين مقياس بندي قدرت انتخاب در همه نسلها ثابت مي‌ماند.
براي توليد مثل، چرخ رولت به تعداد اندازه جمعيت چرخانده مي‌شود. در هر چرخش يك عدد برنده به دست مي‌آيد كه مشخص كننده رشته اي است كه وارد اتاق لقاح مي‌شود. واضح است كه هر چه قطاع اين رشته بزرگتر باشد، احتمال اينكه كپي‌هايي در اتاق لقاح داشته باشد ولذا در ايجاد نسل بعدي شركت كند، بالاتر است.
رشته‌ها در اتاق لقاح به طور تصادفي لقاح مي‌كنند. يعني زوج رشته‌ها به طور تصادفي انتخاب شده، مخلوط شده و احتمالا توسط عملگرهاي ژنتيكيب توليد رشته‌هاي نسل بعدي تغيير مي‌كنند.
شكل 3- ايجاد نسل بعدي در الگوريتم ژنتيك
دو عملكرد ژنتيكي متداول عبارتند از پيوند و جهش، پيوند مهمترين عملگر ژنتيكي است. پيوند يك نقطه‌اي ساده به صورت زير است: وقتي كه زوجي از رشته‌ها به صورت اتفاقي از اتاق لقاح انتخاب شد، يك موقعيت صحيح K (محل پيوند) در طول رشته به طور تصادفي بين 1و l-1 كه I طول رشته برحسب بيت است انتخاب مي‌شود. حال با تعويض تمام بيتهاي بين موقعيت K+1 وI دو رشته جديد ايجاد مي‌شود. در پيوند دو نقطه‌اي، دو نقطه پيوند انتخاب مي‌شود و بخشي از رشته كه بين اين دو نقطه است، جابجا مي‌شود تا دو بچه بوجود آيد. مي‌توان بطور مشابه پيوند n نقطه‌اي تعريف كر د. پيوند يك نقطه‌اي در شكل (4) نشان داده شده است.
شكل 4- عملگر پيوند در الگوريتم ژنتيك
فرايند لقاح با ساير زوج رشته‌ها تكرار مي‌شود تا اينكه تعداد مطلوبي از رشته‌هاي بچه ايجاد شود. در الگوريتم ژنتيك با اندازه جمعيت ثابت اين تعداد برابر اندازه جمعيت اصلي است. پيوند منجر به تبادل اطلاعات تصادفي اما ساخت اما ساخت يافته مي‌شود. هر رشته بچه تركيبي از ويژگيهاي والدين را به ارث مي‌برد. با ملاحظه اين واقعيت كه در هر روند جستجو موازن اي بين آفرينش دانش جديد و بهره برداري از دانش موجود برقرار است، مي‌توان پيوند را وسيله اي براي بهره برداري از دانش موجود در الگوريتم ژنتيك در نظر گرفت. پيوند با تركيب كروموزنها براي تشكيل الگوهاي رشته‌اي كه ممكن است قبلا در جمعيت وجود نداشته باشد، ساز و كاري براي كشف نواحي جديدي از فضاي جستجو را فراهم مي‌كند.
دانش جديد با اعمال ژنيتيكي ديگري به سيستم به نام جهش ايجاد مي‌شود. جهش اساسا تغيير تصادفي يك بيت ( 0به 1 يا 1 به 0 ) در يك رشته اي كه به طور تصادفي انتخاب شده، مي‌باشد. اين عملگر معمولاً پس از عمل پيوند در اتاق لقاح روي رشته‌ها اعمال مي‌شود. دوباره محل جهش بطور تصادفي در طول رشته ( بين بيتهاي 1 تا l ) انتخاب مي‌شود و بيت مربوطه عوض مي‌شود. جهش نوعي از قدم زدن تصادفي در فضاي جستجو را مطرح مي‌كند و مانع از به دام افتادن سيستم در نقطه بهينه محلي مي‌شود. همچنين جهش امكان تشكيل الگوهاي رشته اي كه ممكن است در جمعيت محدود تصادفي اوليه وجود نداشته باشد، فراهم مي‌كند. نرخ جهش معمولاً پايين نگهداشته مي‌شود تا كروموزمهاي خوب بدست آمده از پيوند از بين نرود. اگر نرخ جهش بالا باشد ( بالاي 1/0)،كارآيي الگوريتم ژنتيك كاهش مي‌يابد و به جستجوي تصادفي نزديك مي‌شود. شكل 5 عملگر جهش را نشان مي‌دهد.
5- عملگر جهش در الگوريتم ژنتيك
با پيشرفت الگوريتم در طي نسلهاي متوالي، برازندگي ميانگين جمعيت افزايش مي‌يابد و جواب بهينه فراگير پس از نسلهاي كمي پيدا مي‌شود. بايد ذكر شود كه افزايش برازندگي ميانگين در نسلهاي متوالي به معني آن نيست كه همه رشته‌ها در همه نسلها برازنده هستند. افراد ضعيفي ممكن است در يك نسل ظاهر شود اما مطابق اصل بقاي اصلح آنها مي ميرند و به زودي با افراد قويتر جايگزين مي‌شوند. در الگوريتم ژنتيك اين سرنوشت به شكل توليد مثل متناسب با برازندگي جامه عمل مي‌پوشد كه در آن كروموزمهاي ضعيفتر شانس كمتري براي انتخاب شدن جهت داشتن فرزند در نسل بعدي دارند.
مي‌توان سياستي در پيش گرفت كه برازندگي ميانگين نسلهاي متوالي بطور يكنوا صعودي باشد. اين كار از طريق انتقال مستقيم تعداد مشخصي از برازنده ترين افراد هر نسل به نسل بعدي بدون اعمال عملگرهاي ژنتيكيبر آنها امكان پذير است و نخبه‌گرايي نام دارد.
فرايند تكاملي وقتي خاتمه مي‌يابد كه همگرايي آشكار شود يا معيار خاتمه ديگري ( مانند پردازش تعداد مشخصي نسل ) ارضا شود. همگرايي الگوريتم ژنتيك توسط يكنواختي برازندگي رشته‌ها در يك جمعيت اندازه گيري مي‌شود. يك معيار خاتمه متداول آن است كه برازندگي ميانگين جمعيت 95 %ماكزيمم برازندگي در همان جمعيت باشد.
