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

1- مقدمه

الگوريتم ژنتيك، الهامي از علم ژنتيك و نظرية تكامل داروين است و بر اساس بقاي برترين‏ها يا انتخاب طبيعي استوار است. يك كاربرد متداول الگوريتم ژنتيك، استفاده از آن بعنوان تابع بهينه‏كننده است. الگوريتم ژنتيك ابزار سودمندي دربازشناسي الگو ،انتخاب ويژگي،درك تصويرو يادگيري ماشيني است [19-14]. در الگوريتم‏هاي ژنتيكي[1], نحوه تكامل ژنتيكي موجودات زنده شبيه‏سازي مي‏شود.

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

در هر مرحله از اجراي الگوريتم ژنتيكي, يك دسته از نقاط فضاي جستجو مورد پردازش‏هاي تصادفي قرار مي‏گيرند. به اين صورت كه به هر نقطه دنباله‏اي از كاراكترها نسبت داده مي‏شود و   بر روي اين دنباله‏ها, عملگرهاي ژنتيكي اعمال مي‏شود. سپس دنباله‏هاي بدست آمده ديكد مي‏گردد تا نقاط جديدي در فضاي جستجو بدست آيد. در آخر براساس اين كه تابع هدف در هر يك از نقاط چه مقدار باشد, احتمال شركت نمودن آنها در مرحله بعد تعيين مي‏گردد]1-5[.

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

 

 

2- ساختار الگوريتم‏هاي ژنتيكي

به طور كلي, الگوريتم‏هاي ژنتيكي از اجزاء زير تشكيل مي‏شوند:

 

• ·      كروموزوم[3]

در الگوريتم‏هاي ژنتيكي, هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راه‏حل ممكن براي مسئله مورد نظر است. خود كروموزوم‏ها (راه حل‏ها) از تعداد ثابتي ژن[4] (متغير) تشكيل مي‏شوند. براي نمايش كروموزوم‏ها, معمولاً از كدگذاري‏هاي دودويي (رشته‏هاي بيتي) استفاده مي‏شود.

 

• ·        جمعيت[5]

مجموعه‏اي از كروموزوم‏ها يك جمعيت را تشكيل مي‏دهند. با تاثير عملگرهاي ژنتيكي  بر روي هر جمعيت, جمعيت جديدي با همان تعداد كروموزوم تشكيل مي‏شود.

 

• ·        تابع برازندگي[6]

به منظور حل هر مسئله با استفاده از الگوريتم‏هاي ژنتيكي, ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم, اين تابع عددي غير منفي را برمي‏گرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.

 

• ·        عملگرهاي ژنتيكي

در الگوريتم‏هاي ژنتيكي, در طي مرحله توليد مثل[7] ازعملگرهاي ژنتيكي استفاده مي‏شود. با تاثير اين عملگرها بر روي يك جمعيت, نسل[8] بعدي آن جمعيت توليد مي‏شود. عملگرهاي انتخاب[9] , آميزش[10]  و جهش[11] معمولاً بيشترين كاربرد را در الگوريتم‏هاي ژنتيكي دارند.

3- عملگرهاي ژنتيكي

در بخش قبلي اشاره شد كه در الگوريتم‏هاي ژنتيكي به منظور توليد مثل, معمولاً از عملگرهاي انتخاب, آميزش و جهش استفاده مي‏شود. در اين بخش, هر يك از عملگرهاي فوق به صورت جداگانه معرفي مي‏شود:

 

• عملگر انتخاب

اين عملگر از بين كروموزوم‏هاي موجود در يك جمعيت, تعدادي كروموزوم را براي  توليد مثل انتخاب مي‏كند. كروموزوم‏هاي برازنده‏تر شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.

 

• ·        عملگر آميزش

عملگر آميزش بر روي يك زوج كروموزوم از نسل مولد عمل كرده و يك زوج كروموزوم جديد توليد مي‏كند. عملگرهاي آميزش متعددي از قبيل, آميزش تك نقطه‏اي[12] و آميزش دو نقطه‏اي[13] وجود دارد.

 

در آميزش تك نقطه‏اي, يك موقعيت تصادفي بين دو ژن در نظر گرفته مي‏شود. سپس تمامي ژن‏هاي طرف راست يا طرف چپ اين موقعيت در كروموزوم‏هاي والد با يكديگر جابجا مي‏شوند تا كروموزوم‏هاي جديد بدست آيند. در شكل 1 آميزش تك نقطه‏اي نشان داده شده است.

 

در آميزش دو نقطه‏اي, دو موقعيت به صورت تصادفي انتخاب مي‏شود و تمامي ژن‏هاي بين اين دو موقعيت در كروموزوم‏هاي والد با يكديگر جابجا مي‏شوند.

 

لازم به ذكر است كه آميزش معمولاً بر روي همه زوج كروموزوم‏هاي انتخاب شده براي جفت‏گيري به كار برده نمي‏شود. معمولاً احتمال آميزش براي هر زوج كروموزوم بين 6/0 تا 95/0 در نظر گرفته مي‏شود كه به اين عدد نرخ آميزش[14] يا احتمال آميزش[15] گفته مي‏شود و با P_c  نمايش داده مي‏شود. در صورتي كه بر روي يك زوج كروموزوم عمل آميزش صورت نگيرد, فرزندان با تكرار نمودن والدين توليد مي‏شوند.

• ·        عملگر جهش

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

 

احتمال انجام عمل جهش بر روي هر كروموزوم را نرخ جهش[16] يا احتمال جهش[17] مي‏گويند و با P_m نمايش مي‏دهند. معمولاً اين عدد را بسيار كوچك (مثلاً 001/0)          در نظر مي‏گيرند.

 

پس از اتمام عمل جهش, كروموزوم‏هاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال مي‏شوند.

 

 

 

 

 

 

 

 

 

 

 

 

 

4- روند كلي الگوريتم‏هاي ژنتيكي

در شكل 3 يك الگوريتم ژنتيكي استاندارد, و در شكل 4 نمودار گردشي الگوريتم‏هاي ژنتيكي نشان داده شده است.

 

قبل از اين كه يك الگوريتم ژنتيكي بتواند اجرا شود, ابتدا بايد كدگذاري (يا نمايش) مناسبي    براي مسئله مورد نظر پيدا شود. همچنين يك تابع برازندگي نيز بايد ابداع شود تا به هر راه‏ حل كدگذاري شده ارزشي را نسبت دهد. در طي اجرا, والدين براي توليد مثل انتخاب مي‏شوند و با استفاده از عملگرهاي آميزش و جهش با هم تركيب مي‏شوند تا فرزندان جديدي توليد كنند. اين فرآيند چندين بار تكرار مي‏شود تا نسل بعدي جمعيت توليد شود. سپس اين جمعيت بررسي مي‏شود و در صورتي كه ضوابط همگرايي[18] برآورده شوند, فرآيند فوق خاتمه مي‏يابد.

 

 

 

 

 

شكل 4  نمودار گردشي الگوريتم‏هاي ژنتيكي

 

 

5- آشنايي با روش‏هاي انتخاب در الگوريتم‏هاي ژنتيكي

ايده اصلي در روش‏هاي انتخاب اين است كه افراد بهتر بر افراد بدتر ترجيح داده شوند, كه بهتر و بدتر بودن افراد توسط تابع برازندگي f تعريف مي‏شود.

 

روش‏هاي انتخاب متعددي براي استفاده در الگوريتم‏هاي ژنتيكي پيشنهاد شده‏اند. يكي از ويژگي‏هاي خوب روش‏هاي انتخاب اين است كه اين روش‏ها مستقل از نمايش افراد جمعيت هستند و در آنها تنها مقادير برازندگي افراد در نظر گرفته مي‏شود.

 

در ادامه اين گزارش, ابتدا اصطلاحاتي كه معمولاً در روش‏هاي انتخاب مورد استفاده قرار مي‏گيرند, توضيح داده مي‏شوند. سپس, برخي از روش‏هاي انتخاب متداول كه در الگوريتم‏هاي ژنتيكي مورد استفاده قرار گرفته‏اند, معرفي مي‏شوند.

 

• ·       همگرايي

همگرايي[19], پيشرفت به سوي افزايش يكنواختي محسوب مي‏شود. يك ژن همگرا گفته مي‏شود, هنگامي كه 95% افراد جمعيت مقدار يكساني را به اشتراك گذارند. يك جمعيت هم همگرا گفته مي‏شود, هنگامي كه همه ژن‏ها همگرا شده باشند. هنگامي كه يك جمعيت همگرا مي‏شود, متوسط برازندگي‏ها به برازندگي‏هاي بهترين افراد آن جمعيت نزديك مي‏شود.

 

• ·      همگرايي زودرس

يكي از مشكلات شناخته شده در الگوريتم‏هاي ژنتيكي اين است كه ژن‏هاي تعدادي از افراد نسبتاً قوي (امّا نه بهينه) ممكن است به سرعت بر جمعيت غلبه پيدا كنند و سبب شوند كه الگوريتم به يك نقطه بهينه محلي همگرا شود. به محض همگرا شدن جمعيت به يك نقطه بهينه محلي (همگرايي زودرس[20]), توانايي الگوريتم ژنتيكي براي ادامه جستجو به منظور يافتن راه‏ حل‏هاي بهتر از بين مي‏رود.

 

• ·       نرخ انتظار

نرخ انتظار[21] هر فرد, تعداد دفعاتي است كه پيش‏بيني مي‏شود آن فرد براي توليد مثل مجدد انتخاب خواهد شد.

 

• ·       فقدان تنوع

فقدان تنوع[22], نسبت افرادي از جمعيت است كه در طي مرحله انتخاب برگزيده نمي‏شوند. فقدان تنوع بايد تا حد امكان پايين نگه داشته شود, زيرا فقدان تنوع بالا امكان همگرايي زودرس را افزايش مي‏دهد.

 

• ·       فشار انتخاب يا شدت انتخاب

فشار انتخاب[23], معياري كه براساس آن به افراد بسيار قوي امكان داشتن تعداد زيادي فرزند داده مي‏شود. فشار انتخاب پايين, بدين معني است كه به هر فرد احتمال معقولي براي توليد مثل داده مي‏شود.

5-1 روش‏هاي انتخاب

روش‏هاي انتخاب متعددي براي استفاده در الگوريتم‏هاي ژنتيكي پيشنهاد شده‏اند كه در ادامه اين بخش, برخي از اين روش‏ معرفي مي‏شوند.

 

Ø      انتخاب متناسب با برازندگي

در نسخه اوليه GA كه توسط جان هلند پيشنهاد شد, از انتخاب متناسب با برازندگي[24] استفاده شده است كه در آن نرخ انتظار هر فرد از تقسيم برازندگي آن فرد بر متوسط برازندگي‏هاي جمعيت بدست مي‏آيد. براي پياده‏سازي انتخاب متناسب با برازندگي, روش‏هاي نمونه‏برداري متعددي      از قبيل چرخ رولت[25] و روش SUS[26] پيشنهاد شده‏اند.

 

• ·       نمونه‏برداري به روش چرخ رولت

در اين روش, به هر فرد قطعه‏اي[27] از يك چرخ رولت مدور اختصاص داده مي‏شود. اندازه اين قطعه متناسب با برازندگي آن فرد است. چرخ N بار چرخانده مي‏شود كه N تعداد افراد در جمعيت است. در هر چرخش, فرد زير نشانگر چرخ انتخاب مي‏شود و در مخزن والدين نسل بعد قرار مي‏گيرد. اين روش مي‏تواند به صورت زير پياده‏سازي شود:

 

1-  نرخ انتظار كل افراد جمعيت را جمع كنيد و حاصل آن را T بناميد.

2-  مراحل زير را N بار تكرار كنيد:

يك عدد تصادفي r بين 0 و T  انتخاب كنيد.

در ميان افراد جمعيت بگرديد و نرخ‏هاي انتظار آنها را با هم جمع كنيد تا اين كه مجموع بزرگتر يا مساوي r شود. فردي كه نرخ انتظارش باعث بيشتر شدن جمع از اين حد مي‏شود, به عنوان فرد برگزيده انتخاب مي‏شود.

 

• ·      روش SUS

در نمونه‏برداري به روش چرخ رولت, هنگامي كه جمعيت‏ نسبتاً كوچك باشد, تعداد واقعي فرزنداني كه به هر فرد نسبت داده مي‏شود, اغلب از نرخ انتظار آن فرد دورتر است. به اين دليل, روش نمونه‏برداري متفاوتي توسط James Baker تحت عنوان روش SUS پيشنهاد شده است. در اين روش, به جاي N بار چرخاندن چرخ رولت تا N والد انتخاب شوند, چرخ يك بار چرخانده مي‏شود, امّا از N اشاره‏گر فاصله داده شده به طور يكسان براي انتخاب N والد استفاده مي‏شود. قطعه كد زير براي پياده‏سازي SUS داده شده است:

 

ptr  =  Rand();   /* Returns random number uniformly distributed in [0,1] */

for  (sum = i = 0;  i < N;  i++)

       for (sum += ExpVal(i,t);  sum > ptr;  ptr++)

             Select(i);

 

كه i شاخصي براي افراد جمعيت است و ExpVal(i,t) نرخ انتظار فرد i ام را در دفعه t ام مي‏دهد. در اين روش تضمين مي‏شود كه هر فرد i بين حداقل  بار و حداكثر  بار توليد مثل مي‏كند. SUS مشكل اصلي‏اي كه همراه با انتخاب متناسب با برازندگي وجود دارد را حل نمي‏كند. معمولاً, در ابتداي جستجو واريانس برازندگي در جمعيت بالا است و تنها تعداد كمي از افراد جمعيت از سايرين خيلي برازنده‏تر هستند. تحت انتخاب متناسب با برازندگي, اين افراد و نوادگان‏‏شان به سرعت در جمعيت تكثير پيدا خواهند كرد, در نتيجه GA را از انجام هر اكتشاف بيشتري باز خواهند داشت كه باعث مي‏شود GA دچار همگرايي زودرس شود.

 

Ø      Sigma Scaling

براي حل مشكلاتي كه در بالا اشاره شد, محققين چندين روش مقياس گذاري را آزمايش كرده‏اند. در اين روش‏ها, مقادير خام برازندگي به گونه‏اي به نرخ‏هاي انتظار نگاشت مي‏شوند كه GA را كمتر مستعد پذيرش همگرايي زودرس ‏سازند.

 

يكي از اين روش‏ها, روش Sigma Scaling يا Sigma Truncation است. در اين روش, فشار انتخاب به جاي اين كه وابسته به واريانس برازندگي جمعيت باشد, در طي اجرا نسبتاً ثابت نگه‏ داشته مي‏شود.

 

در Sigma Scaling , نرخ انتظار هر فرد تابعي از برازندگي, ميانگين و انحراف معيار جمعيت است. مثالي از نرخ انتظار در اين روش مي‏تواند به صورت زير باشد:

 

 

 

 

 

 

 

 

كه ExpVal(i,t) نرخ انتظار فرد i ام در زمان t , f(i) برازندگي فرد i ام,  ميانگين برازندگي جمعيت در زمان t و  انحراف معيار برازندگي‏هاي جمعيت در زمان t است. در تابع فوق,    از هر فرد با برازندگي يك انحراف معيار بالاي ميانگين, انتظار 5/1 فرزند مي‏رود. همچنين,        در صورتي كه مقدار ExpVal(i,t) كمتر از 0 باشد, به 1/0 بازنشانده مي‏شود, به طوري كه افراد با برازندگي خيلي پايين اندكي شانس توليد مثل داشته باشند.

 

در شروع اجرا, هنگامي كه انحراف معيار برازندگي‏ها معمولاً بالا است, افراد برازنده‏تر انحرافات معيار زيادي بالاي ميانگين نخواهند داشت. امّا بعداً در طي اجرا كه جمعيت معمولاً همگراتر مي‏شود و انحراف معيار هم پايين‏تر مي‏آيد, افراد برازنده‏تر برجسته‏تر خواهند شد كه امكان ادامه تكامل را مي‏دهد.

 

Ø      انتخاب نخبگان

روش انتخاب نخبگان[28] كه اولين بار توسط De Jong مطرح شده است, به عنوان الحاقي به خيلي از روش‏هاي انتخاب محسوب مي‏شود كه GA را وادار مي‏كند تا بهترين افراد را در هر نسل نگه دارد. چنين افرادي در صورتي كه براي توليد مثل انتخاب نشوند يا توسط آميزش و جهش خراب شوند, ممكن است از بين بروند. بسياري از محققين دريافته‏اند كه انتخاب نخبگان به ميزان قابل ملاحظه‏اي كارايي GA را افزايش مي‏دهد.

 

Ø      انتخاب Boltzmann

در روش Sigma Scaling فشار انتخاب در طي اجرا ثابت نگه‏ داشته مي‏شود. امّا در زمان‏هاي متفاوت در طي يك اجرا, اغلب به مقادير متفاوتي از فشار انتخاب نياز است. به عنوان مثال, در ابتدا ممكن است مناسب باشد تا به افراد با برازندگي كمتر نزديك به نرخ افرادي كه برازندگي بيشتري دارند, امكان توليد مثل داده شود و انتخاب به كندي انجام شود تا مقداري تنوع در جمعيت حفظ ‏شود. امّا بعداً ممكن است مناسب باشد تا انتخاب قوي‏تر باشد تا به افراد خيلي قوي اهميت بيشتري داده شود. با اين فرض كه وجود تنوع اوليه همراه با انتخاب كند به جمعيت امكان داده است تا بخش درستي از فضاي جستجو را پيدا كند.

براي رسيدن به اهداف فوق, روش انتخاب Boltzmann پيشنهاد شده است. در اين روش, يك درجه حرارت[29] دائماً متغير, نرخ انتخاب را بر حسب يك زمان‏بندي از قبل تنظيم شده كنترل مي‏كند. در ابتدا درجه حرارت مقدار خيلي زيادي دارد, بدين معني كه فشار انتخاب پايين است (يعني هر فرد اندكي احتمال توليد مثل دارد). درجه حرارت به تدريج پايين آورده مي‏شود كه باعث افزايش تدريجي فشار انتخاب مي‏شود. بدين طريق به GA امكان داده مي‏شود در حاليكه ميزان تنوع را در حد مناسبي نگه مي‏دارد, همواره به بهترين قسمت از فضاي جستجو نيز نزديك‏تر شود. يك پياده‏سازي معمول از اين روش اين است كه به هر فرد i نرخ انتظار زير را نسبت دهيم:

 

 

 

 

 

 

كه T درجه حرارت است و  < >_t  متوسط جمعيت را در زمان t مشخص مي‏كند. آزمايش فرمول فوق نشان مي‏دهد همان طور كه T كاهش مي‏يابد, اختلاف ExpVal(i,t) بين برازندگي‏هاي پايين و بالا افزايش مي‏يابد. مطلوب اين است كه اين افزايش اختلاف به تدريج در ضمن جستجو اتفاق بيافتد, بنابراين درجه حرارت به تدريج برحسب يك زمان بندي از قبل تعريف شده كاهش مي‏يابد.

 

Ø      انتخاب رتبه‏اي

روش انتخاب متناسب با برازندگي عموماً در الگوريتم‏هاي ژنتيكي استفاده مي‏شود. به دليل اين كه اين روش قسمتي از طرح پيشنهادي اوليه جان هلند بود و همچنين از آن در تئوري schema نيز استفاده شده است. امّا براي بسياري از كاربردها روش انتخاب متناسب با برازندگي نياز به چندين بازسازي دارد تا آن را براي استفاده مناسب سازد. در سال‏هاي اخير, روش‏هاي كاملاً متفاوتي براي انتخاب مورد استفاده قرار گرفته‏اند. يكي از اين روش‏ها, روش انتخاب رتبه‏اي[30] است كه هدف‏اش اين است كه از همگرايي بيش از حد سريع جلوگيري كند. در اين روش, افراد جمعيت برحسب برازندگي‏شان رتبه‏بندي مي‏شوند. نرخ انتظار هر فرد هم به جاي بستگي به برازندگي مطلق, بستگي به رتبه‏ آن فرد دارد. اين صرفنظرسازي از اطلاعات مطلق برازندگي, مي‏تواند داراي مزايا (استفاده از برازندگي مطلق مي‏تواند منتهي به مشكلات همگرايي شود) و معايبي (گاهي اوقات ممكن است مهم باشد تا مشخص شود كه يك فرد بسيار شايسته‏تر از نزديك‏ترين رقيبش است) باشد.

در اين روش, هنگام رتبه‏بندي از دادن بزرگترين سهم از زاد و ولد به گروه كوچكي از افراد خيلي قوي اجتناب مي‏شود. بنابراين, در اين روش هنگامي كه واريانس برازندگي بالا است, فشار انتخاب كاهش داده مي‏شود. همچنين, هنگامي كه واريانس برازندگي پايين است, فشار انتخاب ثابت     نگه ‏داشته خواهد شد: نسبت نرخ‏هاي انتظار افراد رتبه i ام و i+1 ام يكسان خواهد شد, بدون توجه به اين كه اختلافات برازندگي مطلق‏شان بالا يا پايين است.

 

انواع متفاوتي از طرح‏هاي رتبه‏بندي (از قبيل رتبه‏بندي خطي[31] و رتبه‏بندي تواني[32]) پيشنهاد شده‏اند. در روش رتبه بندي خطي (كه توسط Baker پيشنهاد شده است), افراد جمعيت برحسب ترتيب افزايشي برازندگي‏شان از 1 تا N  رديف مي‏شوند. كاربر نرخ انتظار Max (Max ≥ 0) را براي فرد با رتبه N انتخاب مي‏كند. نرخ انتظار هر فرد i در جمعيت در زمان t از رابطه زير   بدست مي‏آيد:

 

ExpVal(i,t) = Min + ( Max-Min)

كه Min نرخ انتظار فرد با رتبه 1 است. با فرض محدوديت‏هاي Max ≥ 0 و  (از آنجا كه اندازه جمعيت از نسلي به نسل ديگر ثابت مي‏ماند), لازم است 0 ≤ Max ≤ 1  و Min = 2-Max  باشد.

در هر نسل افراد جمعيت رتبه‏بندي مي‏شوند و به هر فرد برحسب معادله فوق نرخ‏هاي انتظاري نسبت داده مي‏شود. Baker توصيه كرد كه Max = 1.1 باشد و نشان داد كه اين طرح در مقايسه با روش انتخاب متناسب با برازندگي بر روي برخي از مسائل آزمايشي مطلوب‏تر است.

 

روش انتخاب رتبه‏اي داراي معايبي است. يكي از معايب اين روش اين است كه با كند شدن فشار انتخاب, توانايي GA در پيدا نمودن افراد بسيار قوي كاهش خواهد يافت. هر چند, به دليل اين كه رتبه‏بندي تنوع را حفظ مي‏كند, باعث جستجوي موفقيت‏آميزتر فضاي جستجو مي‏شود و در آن از همگرايي سريع كه مي‏تواند از انتخاب متناسب با برازندگي نتيجه شود, جلوگيري به عمل مي‏آيد.

لازم به ذكر است كه در هر روش رتبه‏بندي, به محض اين كه نرخ‏هاي انتظار به هر فرد نسبت داده شد, از روش SUS مي‏توان براي نمونه‏برداري از جمعيت (يعني انتخاب والدين) استفاده نمود.

Ø      انتخاب تورنمنت

روش‏هاي انتخابي كه تاكنون توصيف شدند, در هر نسل نياز به دوبار عبور از ميان جمعيت دارند:

يك بار براي محاسبه ميانگين برازندگي و  يك بار هم براي محاسبه نرخ انتظار هر فرد. در روش انتخاب رتبه‏اي, لازم است تا تمام افراد جمعيت براساس رتبه‏شان مرتب شوند كه يك رويه وقت‏گير است. انتخاب تورنمنت[33] مشابه با انتخاب رتبه‏اي برحسب فشار انتخاب است, امّا از نظر محاسباتي كارآتر و براي پياده‏سازي‏هاي موازي مناسب‏تر است. در اين روش, دو فرد از جمعيت  به صورت تصادفي انتخاب مي‏شوند. سپس, يك عدد تصادفي r بين 0 و 1 انتخاب مي‏شود. اگر    r < k (كه k يك پارامتر است, براي مثال 75/0) باشد, فرد برازنده‏تر و در غير اينصورت فردي كه برازندگي كمتري دارد, به عنوان والد انتخاب مي‏شود. اين دو سپس به جمعيت اوليه بازگردانده مي‏شوند و دوباره در فرآيند انتخاب شركت داده مي‏شوند.

 

 

6- شرط پايان الگوريتم

در الگوريتم‌هاي تكاملي غالباً اجراي برنامه براي تعداد نسل‌هاي از پيش تعيين شده‌اي صورت مي‌گيرد. اما شرط ديگري نيز براي پايان الگوريتم‌هاي ژنتيك توسط Grefenstette ] 39[ ارائه شده است كه آن ميزان پراكندگي بيت‌ها درون جمعيت مي‌باشد (Bit Diversity) . اين محك نشان دهنده ميزان همگرا شدن كد اعضاي جمعيت مي‌باشد. اگر كد يك عنصر داراي طول l بيت باشد و به صورت  نشان داده شود و  (كه  تعداد اعضاي جمعيت است)، مقدار پراكندگي بيت جمعيت P، b(P) به صورت زير تعريف مي‌شود:

(23-4)                                              

هر اندازه ميزان b بزرگتر باشد ميزان پراكندگي بيت‌ها درون جمعيت كمتر خواهد بود. در حالت ويژه اگر b(P)=1 باشد به اين معني است كه كد همه اعضاي جمعيت يكسان است. شرط پايان به صورت b(p)> تعريف مي‌شود كه  معمولا99/0 95/0 مي‌باشد.

 

 

7- برخي از كاربرد الگوريتم‏هاي ژنتيكي

الگوريتم‏هاي ژنتيكي در حل بسياري از مسائل علمي و مهندسي به كار گرفته شده‏اند. برخي از موارد كاربرد اين الگوريتم‏ها عبارتند از:

بهينه‏سازي, برنامه‏سازي خودكار, يادگيري ماشين, تكامل تدريجي و يادگيري, اكولوژي و سيستم‏هاي اجتماعي.

 

 

6- مراجع

[1]   M. Mitchell. An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA, 1996.

 

[2]  D. Beasley, D. Bull and R. Martin. An Overview of Genetic Algorithms: Part 1, Fundamentals, University of Cardiff, Cardiff, 1993.

 

[3]  D. Beasley, D. Bull and R. Martin. An Overview of Genetic Algorithms: Part 2, Research Topics, University of Cardiff, Cardiff, 1993.

 

[4]     P. Brigger. An Overview of Genetic Algorithms,

URL: http://ltswww.epfl.ch/pub_files/brigger/thesis_html/, 1995.

 

[5]   D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989.

 

[6]    T. Blickle, and L. Thiele. A Comparison of Selection Shemes used in Genetic Algorithms, TIK- Report, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, 1995.

[14]   Tseng, L.Y. and Yang, S., “Genetic algorithms for clustering , feature selection and

  classification” ,IEEE Int. Conference on Neural Networks, pp.1612-1616,1997.

[15]  Bala,J.,Huary,J.,Vafaie,H.,De jong, K. and Wechslev,H.  “Hybrid learning using genetic algorithms and decision trees for pattern classification” , IJCAI conference , Montreal , August 19-25,1995.

[16]  Siedlecki,W. and Sklansky,J., “A note on genetic algorithms for large scale pattern selection” , Pattern Recognition Letters , vol.10,335-347,1989.

17.Vafaie, H. and De Jong, K. “Robust feature selection algorithms” , Proc. of the fifth conference on tools for artificial intelligence, Boston, MA: IEEE Computer Society Press. , pp. 356-363, 1993.

18.Vafaie, H., and De Jong, K., “Genetic algorithms as a tool for feature selection in machine learning”, Proc. of the 4th Int. conference on tools with artificial intelligence,pp.200-204 Arlington,VA, 1992.

19.Vafaie,H. and Imam,I., “Feature selection methods: genetic algorithms vs. greedy-like search”. Proc. of the Int. conference on fuzzy and intelligent control systems, 1994.

[39] Back,T, “ Evolutionary Algorithms in Theory & Practice “ Oxford University Press, 1996.

 [41] Fogel, D.B. “ What is Evolutionary Computation?” IEEE Spectrum, Feb 2000, pp. 26-32

 

:: موضوعات مرتبط: پروژه مهندسی صنایع، پایان نامه مهندسی صنایع، نرم افزار های مهندسی صنایع، الگوریتم های فرا ابتکاری
:: برچسب‌ها: پایان نام, پایان نامه مهندسی صنایع, انجام پایان نامه مهندسی صنایع, زنجیره تأمین