آموزش گام به گام الگوریتم ژنتیک-بخش اول

سرویس آموزش و آزمون برق نیوز: ايده اوليه اين روش از نظريه تكامل داروين الهام گرفته شده است و كاربرد آن بر اساس ژنتيك طبيعي استوار مي باشد. اصول اوليه الگوريتم ژنتيك در سال هاي ۱۹۶۲ تا ۱۹۶۵ به وسیله جان هلند و همكارانش در دانشگاه ميشيگان ارائه شد. آنان در تحقيقات خود به فرايند سازگاري در سيستم هاي طبيعي توجه كرده و براي مدلسازي آن در سيستم هاي مصنوعي كه بايد داراي توانايي هاي سيستم هاي طبيعي باشند، تلاش كردند.

الگوريتم ژنتيك يكي از مهمترين الگوريتم هاي فرا ابتكاري مي باشد كه از آن براي بهينه سازي جهت توابع تعريف شده روي دامنه محدود استفاده مي شود. در اين الگوريتم اطلاعات گذشته با توجه به موروثي بودن الگوريتم استخراج شده و در روند جستجو مورد استفاده قرار مي گيرد. مفاهيم الگوريتم ژنتيك در سال 1989 توسط گلبرگ توسعه داده شد.

 

ساختار الگوريتم ژنتيك به شرح زير مي باشد:
الف)كروموزوم :رشته يا دنباله اي از بيت ها كه به عنوان شكل كد شده يك جواب ممكن (مناسب يا نامناسب) از مسأله مورد نظر مي باشد، چنانچه از كدگذاري دودويي استفاده شود، هر بيت، يكي از مقادير صفر و يك را مي پذيرد .هر كدام از بيت های كروموزوم مسأله اخير، يك جواب بالقوه براي متغيرهاي مسأله مي باشد. (صادقی مقدم و همکاران، 1384)
اساس الگوريتم ژنتيك تبديل هر مجموعه جواب به يك كدينگ است. اين كدينگ را اصطلاحا كروموزوم گويند. در واقع شكل رمز شده جواب محتمل مسأله مي باشد. دراين مساله هر كروموزم يك جواب مسأله است كه مي تواند موجه و يا غير موجه مي باشد. (صادقی مقدم و همکاران، 1388)
ب) تابع هدف و برازندگي: تابعي است كه مقدار متغير مسأله در آن قرار داده شده، بدين طريق، مطلوبيت هر جواب مشخص مي گردد. در مسائل بهينه سازي تابع هدف به عنوان تابع برازندگي به كار مي رود. (صادقی مقدم و همکاران، 1388)
تابع هدف جهت تعيين اينكه افراد چگونه در محدوده مسأله ايفاي نقش مي كنند، استفاده مي شود و تابع برازندگي معمولاً براي تبديل مقدار تابع هدف به يك مقدار برازندگي وابسته به آن استفاده مي شود. به عبارت ديگر داريم:

به طوری کهf تابع هدف بوده و تابع g مقدار تابع هدف را به یک عدد غیر منفی تبدیل می کند و F مقدار برازندگی مربوط به آن می باشد. مناسب بودن یا نبودن جواب با مقداری که از تابع برازندگی به دست می آید سنجیده می شود. چون مسأله از نوع بهينه سازي مي باشد، تابع برازش با تابع هدف مسأله يكسان مي باشد. تابع هدف مسأله، مينيمم كردن هزينه را مد نظر قرار مي دهد.
ج) اندازه جمعيت و تعداد توليد: تعداد كروموزوم ها را اندازه جمعيت مي گويند. يكي از مزيت هاي الگوريتم هاي ژني نسبت به روش هاي جستجوي سنتي اين است كه از جستجوي موازي استفاده مي شود. با تعريف فوق، اندازه جمعيت، اندازه جستجوهاي موازي است. در اين تحقيق، اندازه جمعيت در آزمايش هاي مختلف بررسي شده و جمعيت از يك نسل به نسل ديگر به منظور يافتن جواب بهتر با استفاده از روش هاي توليد مثل بهبود يافته است. (صادقی مقدم و همکاران، 1384)
يكي از ويژگي هاي الگوريتم ژنتيك اين است كه به جاي تمركز بر روي يك نقطه از فضاي جستجو يا يك كروموزوم بر روي جمعيتي از كروموزوم كار مي كند. (صادقی مقدم و همکاران، 1388)
د ) عملگرهاي ژنتيك: براي پيدا كردن يك نقطه در فضاي جستجو بايد از عملگرهاي ژنتيك استفاده كرد. دو مورد از اين عملگرها عبارتند از:
-1عملگر تقاطعي: عملگر اصلي جهت توليد كروموزوم هاي جديد در الگوريتم ژنتيك، عملگر تقاطع مي باشد. اين عملگر مشابه همتاي خودش در طبيعت، افراد جديدي توليد مي كند كه اجزاي (ژن هاي) آن از والدينش تشكيل می شود. انواع مختلف عملگرهاي تقاطعي عبارتند از:
تك نقطه اي، دو نقطه اي، پخش كننده، ميانجي و ابتكاري و ....
براي تعيين عملگر تقاطع مناسب، روش هاي مختلفي همچون تك نقطه اي دو نقطه اي پخش كننده، ميانجي و ابتكاري آزمايش شده است و روش ابتكاري پاسخ مناسب تري را ارائه كرده است. روش ابتكاري فرزندي را كه خط تماس دو والد قرار گرفته است، در يك فاصله كوچك دور از والد با ارزش برازش بهتر و در مسيري متفاوت از والد با ارزش برازش بدتر بر مي گرداند.
-2عملگر جهش :جهش يك فرايند تصادفي است كه در آن محتواي يك ژن با ژن ديگر جهت توليد يك ساختار ژنتيك جديد جايگزين مي شود. (صادقی مقدم و همکاران، 1384)
ه( نسل: هر تكرار الگوريتم كه منجر به ايجاد يك جمعيت جديد مي گردد را يك نسل مي گويند. (صادقی مقدم و همکاران، 1388)

عملکرد الگوریتم ژنتیک
قدم اول: بدست آوردن تابع هدف (Cost Function) با n متغير.
مثلا يك تابع هدف دو متغيره را مي توان به صورت زير تعريف كرد:

 

تذكر1:
يكي از مزاياي روش ژنتيك الگوريتم اين است كه فقط با مقدار تابع سرو كار دارد لذا براي انتخاب تابع نيازي به دانستن معادله دقيق آن نداريم و فقط اگر روشي بيابيم كه به وسيله وارد كردن متغيرهاي مساله مقدار عددي تابع را بتوانيم پيدا كنيم كفايت مي كند بر خلاف ديگر روش هاي بهينه سازي كه نياز است دقيقا معادله تابع هدف را داشته باشيم.
مثلا اگر بتوانيم به وسيله روشي از روش هاي ترسيمي در مورد مساله اي خاص به ازاي متغيرهاي مختلف مقدار تابع را پيدا كنيم اصلا نيازي به دانستن رابطه بين متغيرها و تابع نيست و روش ژنتيك با دقت بسيار خوبي مقدار بهينه را براي ما مي يابد.
يا اينكه اگر نرم افزاري براي تحليل يك مساله مهندسي وجود دارد كه متغيرها را از ما مي گيرد و جواب را به ما مي دهد مي توانيم بدون دانستن اتفاقاتي كه در طي آن به جواب مي رسيم. فقط با دانستن مقدار آن به ازاي متغيرهاي ورودي مقدار بهين تابع را به وسيله الگوريتم ژنتيك بدست آوريم.
و اين مزيتي است كه در كمتر روش بهينه سازي با آن برخورد مي كنيم.
تذكر 2:
اگر تابع هدف ما داراي قيود طراحي بود كه معمولا هم چنين است مي توانيم به وسيله تابع جريمه (PENALTY FUNCTION) مجموعه قيود مساوي و نامساوي را به يك رابطه تبديل كنيم و به بهينه كردن رابطه مورد نظر بپردازيم.
تذكر 3:
الگوريتم ژنتيك يك الگوريتم ماكزيمم سازي است لذا در مينيمم سازي بايد تابع را طوري تعريف كرد كه درعمل با ماكزيمم كردن آن بتوان به جواب بهينه دست يافت به اين منظور مي توان در تابع هدف تغييرات زير را داد و مقدار تابع هدف جديد را ماكزيمم كرد: 1/f یا -f

 

كروموزوم يك رشته از 0 و 1 است كه مقدار n متغير تابع هدف ما را در بر دارد مثلا اگر طول هر متغير را بيت در نظر بگيريم طول كل كروموزوم برابر است با: L=n*α
(به هر بيت از كروموزوم يك ژن گويند)
اين قسمت سليقه اي است و هرچه تعداد آن بيشتر باشد محاسبات ما دقيقتر خواهد بود.
تذكر 1:
مي توان براي تعيين α از رابطه زير استفاده كرد:

 

 

كه در آن m دقت متغير ها بر حسب تعداد رقم اعشار مي باشد و a وb حد بالا و پايين متغير ها در مبناي 10 مي باشد.
تذكر 2:
در جاهايي كه لازم است براي اعداد منفي بايد يك بيت به علامت آن ها اختصاص داد
تذكر 3:
در مورد اعداد اعشاري بايد ابتدا آن ها را با ضرب در يك عدد به عدد صحيح تبديل كرده و سپس به باينري تبديل كنيم.

قدم سوم: توليد جمعيت اوليه.
پس از تعين طول كروموزوم بايد آن را به طور اتفاقي از 0 و 1 پر كنيم اين كار به وسيله دستو روبرو انجام مي شود: L=roundd (rand)
تذكر 1:
تعداد تركيب هاي جايگيري 0 و 1 براي كروموزوم به طول L برابر است با: 2L
بهتر است تعداد كروموزوم هاي يك جمعيت از تعداد تركيب هاي نشستن صفرها و يك ها در يك كروموزوم بيشتر نگيريم چرا كه در بعضي از كروموزوم ها به ناچار تكرار مي گردند.
تذكر 2:
مقدار بهينه تعداد كروموزوم ها در يك جمعيت به طور تقريبي از رابطه زير بدست مي آيد: m=2bl

قدم چهارم: مقدار متغير ها را در تابع هدف (COST FUNCTION) قرار داده و مقدار تابع را به ازاي هر بردار X=[X1 , X2 , … , Xn] به دست مي آوريم بدين ترتيب براي مجموعه 5 كروموزومي و تابع هدف زير داريم:

 

 

قدم پنجم: درصد برازندگي هر كروموزوم را حساب مي كنيم مثلا براي يك تابع دو متغيره درصد برازندگي برابراست با:

 

قدم ششم: تا اينجا جمعيت اوليه توليد و درصد برازندگي هر كروموزوم محاسبه گرديد. حال بايد تعدادي از اين كروموزوم ها در عمل پيوند شركت كنند براي تعيين تعداد كروموزوم ها از فرمول روبرو استفاده مي كنيم:

 

 

P0 = تعداد جمعيت اوليه
Cp= ضريب پيوند كه معمولا حدود 0.6 مي باشد
Nc= تعداد كروموزوم هايي كه از جمعيت اوليه در عمل پيوند شركت مي كنند.

قدم هفتم: انتخاب كروموزوم هايي كه در عمل پيوند شركت مي كنند.
مي دانيم براي اينكه نسل بعدي از نسل قبلي بهتر باشد بايد كروموزوم هايي با درصد برازندگي بيشتر، شانس بيشتري براي شركت در عمل پيوند داشته باشند لذا براي تعيين اينكه چه كروموزوم هايي در عمل پيوند شركت مي كنند مكانيزمي به نام چرخ رولت انتخاب مي كنيم. كه متناسب با درصد برازندگي هر كروموزوم آن را در عمل پيوند شركت مي دهد.
اين مكانيزم به اين صورت است كه درصد برازندگي هر كروموزوم را روي دايره اي به صورت قطاعي مشخص مي كند در مثال ما كه 5 كروموزوم داريم بايد 5 قطاع به اندازه هاي مختلف داشته باشيم.


حال فرض كنيد چرخ را به گردش در آورده و نقطه اي را به عنوان شاخص در نظر مي گيريم پس از توقف چرخ قطاعي كه در مقابل شاخص قرار گرفت نشان دهنده كروموزومي است كه بايد در عمل پيوند شركت كند.


اين كار را Nc با انجام داده تا به تعداد كافي كروموزوم براي پيوند به دست آوريم. ملاحظه مي كنيم كه در اين مكانيزم كروموزوم هايي با درصد برازندگي بالاتر شانس بيشتري براي انتخاب شدن دارند.
تذكر:
كلا مي توان روش هاي انتخاب را به صورت زير خلاصه كرد:
1- نمونه برداري جبري (deter ministic sampling)
2- روش انتخابي متناسب (proportionate select scheme)
3- روش انتخابي چرخ رولت (roulette wheel selection)
كه مختصرا به توضيح هر يك مي پردازيم:

 

 

اين روش به هر ارگانيسم (فرد) I با ميزان صلاحيت Fi مقدار Ci را نسبت مي دهد كه n تعداد ارگانيسم هاي جمعيت است و دستور round تابع گرد كردن به عدد صحيح مي باشد عملگر انتخاب تضمين مي كند كه هر ارگانيسم دقيقا Ci مرتبه به عنوان والد در ارگانيسم شركت نمايد.
ب) روش انتخابي متناسب:

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

ج) روش چرخ رولت:
دراين روش هر رشته قطاعي از چرخ رولت را با شعاع   از مركز چرخ را به خود اختصاص مي دهد.
انتخاب چرخ رولت خطاي نمونه برداري زيادي توليد مي كند از اين جهت كه تعداد نهايي فرزندان تخصيص داده شده به يك رشته با ميزان مورد نظر خيلي تفاوت دارد. تعداد فرزندان زماني به ميزان مورد نظر مي رسد كه اندازه جمعيت خيلي زياد باشد.

در مسائل كاربردي از چرخ استفاده نمي شود بلكه مقدار را به هر رشته تخصيص مي دهند و با توليد يك عدد تصادفي در بازه ( و 0) رشته را انتخاب مي كنند.
روش تورنمنت: به طور تصادفي چند عضو از جمعيت حاضر جدا مي شود و آنكه در بين آن ها بهترين برازندگي را دارد براي حضور درنسل بعد انتخاب مي گردد. اين كار ادامه مي يابد تا جمعيت نسل بعد كامل شود ساده ترين راه جدا كردن دو به دو است. ولي روش هاي انتخاب تصادفي از همگرايي زودرس جلوگيري مي كنند.

عمل تركيب دو كروموزوم كه همان والدين مي باشند (parent) و بدست آوردن دو كروموزوم جديد كه فرزندان (chiled) مي باشد را پيوند مي نامند.
براي انجام عمل پيوند روي دو كروموزوم L ژني ابتدا بايد نقطه پيوند را مشخص كنيم اين كار با فراخواني عددي تصادفي بين 1 و L-1 صورت مي پذيرد. (round(l*RND)+1)
سپس ژن هاي دو كروموزوم را از نقطه پيوند با هم عوض مي كنيم. مثلا براي دو كروموزوم 10 ژني با نقطه پيوند 4 داريم:

 

 

 

منبع: آریا مدیر