الگوریتم ژنتیک

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

F(n)=g(f(x))

به طوری که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) رشته را انتخاب مي كنند.
روش تورنمنت: به طور تصادفي چند عضو از جمعيت حاضر جدا مي شود و آنكه در بين آن ها بهترين برازندگي را دارد براي حضور درنسل بعد انتخاب مي گردد. اين كار ادامه مي يابد تا جمعيت نسل بعد كامل شود ساده ترين راه جدا كردن دو به دو است. ولي روش هاي انتخاب تصادفي از همگرايي زودرس جلوگيري مي كنند.
قدم هشتم: پيوند (crossover)
عمل تركيب دو كروموزوم كه همان والدين مي باشند (parent) و بدست آوردن دو كروموزوم جديد كه فرزندان (chiled) مي باشد را پيوند مي نامند.
براي انجام عمل پيوند روي دو كروموزوم L ژني ابتدا بايد نقطه پيوند را مشخص كنيم اين كار با فراخواني عددي تصادفي بين 1 و L-1 صورت مي پذيرد. (round(l*RND)+1)
سپس ژن هاي دو كروموزوم را از نقطه پيوند با هم عوض مي كنيم. مثلا براي دو كروموزوم 10 ژني با نقطه پيوند 4 داريم:

اگر پيوند را از نقطه 4 آغاز كنيم داريم

تذكر
عمل پيوندي كه در فوق انجام شد به نام تقاطع يك نقطه اي مي نامند مكانيزم هاي تقاطع را مي توان به صورت زير بيان كرد:
-1تقاطع ساده يا يك نقطه اي:
در اين روش يك نقطه تقاطع انتخاب ميشوند و بيتهاي متناظر جابجا مي شوند . كه مثال آن آورده شد
-2تقاطع n نقطه اي: n>1
n محل به طور تصادفي انتخاب مي شود و هر والد را بهn+1   قطعه تقسيم مي كند تكه اي فرد از والد اول و تكه زوج از والد دوم در محل هاي متناظر در فرزند قرار مي گيرد. اكثر محققين مقدار زوج را براي n ترجيح مي دهند.
مثال: n = 2

3-تقاطع يكنواخت
در اين روش يك رشته به طول رشته والد انتخاب مي شود. (mosk) و از اعداد تصادفي پرمي گردد.
اگر عدد از Pm كمتر باشد در (mosk) صفر قرار مي گيرد و اگر بيشتر باشد يك قرار مي گيرد. اگر بيت (mosk) صفر باشد رشته جديد از والد اول بيت بر مي دارد. و اگر 1 باشد از والد دوم برمي دارد. اين روش روي تك تك بيت ها اعمال مي شود. 

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

حال دو كروموزوم فرزند را به روش تقاطع ساده با نقطه تقاطع مثلا 5، تقاطع مي دهيم:

قدم نهم: جهش (mutation)
جهش يكي از پديده هاي علم ژنتيك كه به ندرت در برخي از كروموزوم ها رخ مي دهد. و در طي آن فرزندان خصوصياتي پيدا مي كنند كه متعلق به هيچ يك از والدين نمي باشد.
نقش جهش در الگوريتم ژنتيك بازگرداندن مواد ژنتيكي گم شده و يا پيدا نشده داخل جمعيت است. تا از همگرايي زودرس الگوريتم به جواب هاي بهينه محلي جلوگيري شود. در جهش يكسري از ژن ها را به طور تصادفي برگزيده صفرها را به يك و يك ها را به صفر تبديل مي كنيم يكي از روش هاي جهش بدين صورت است كه ابتدا با توجه به يك عدد كوچكتر از يك به نام احتمال جهش براي هر ژن از جمعيت يك عدد تصادفي فراخواني مي شود اگر اين عدد تصادفي از احتمال جهش كوچكتر بود در آن ژن جهش رخ مي دهد.
تذكر 1: چون عمل جهش در طبيعت به ندرت رخ مي دهد لذا در الگوريتم ژنتيك هم با احتمال بسيار كم كمتر از (0.05) عمل جهش را انجام مي دهيم همان طور كه گفته شد مزيت عملگر جهش اينست كه توان دسترسي به همه فضاي جستجو را به ما مي دهد.
تذكر 2: در صورتي كه كاراكترها اعداد پيوسته باشند جهش را مي توان به صورت نمو تصادفي مثبت يا منفي حول مقدار قبلي كاراكتر انجام داد اين نوع جهش را جهش خزنده مي نامند.
تذكر 3: انواع ديگر جهش از نظر ژنتيك عبارتند از:
1- موتاسيون در ژنوم كه در آن تعداد كروموزوم تغيير مي كند.
2- موتاسيون در كروموزوم كه در آن شكل كروموزوم تغيير مي كند.
1- موتاسيون در ژن در روي كروموزوم ها ژن تغيير مي كند.
قدم دهم: حفظ بهترين كروموزوم
تا اينجا توليد جمعيت جديد خاتمه مي يابد اكنون براي آنكه بهترين كروموزوم نسل قبل را از دست ندهيم آنرا بطور دستي در جاي بدترين كروموزوم نسل جديد قرار مي دهيم.
رهيافت ديگري براي حفظ بهترين كروموزوم كه در اين پروژه از آن استفاده شده است اينست كه جمعيت جديد و جمعيت قبلي را با هم در آميخته كرده و سپس آنها را بر حسب برازندگيشان از بزرگ به كوچك طبقه بندي ميكنيم سپس p (برابر با تعداد جمعيت) كروموزوم اول جمعيت كه از همه برازندگيشان بيشتر است به عنوان جمعيت جديد بر مي گزينيم.
در اين روش جمعيت با ميانگين برازندگي بالاتري تشكيل مي گردد و به جاي انتقال بهترين كروموزوم و حذف بدترين كروموزوم دسته اي از بهترين كروموزومها جاي دسته اي از بدترين كروموزومها را مي گيرند. با اين عمل همگرايي (converg) به سمت عدد بهينه در اجراي الگوريتم سريعتر و زمان اجراي برنامه(run time) تا يافتن جواب مناسب كاهش مي يابد.
قدم یازدهم:
حال جمعيت جديد توليد شده است كه ميانگين برازندگي آن از نسل قبلي بهتر است حال با اين جمعيت مجددا مراحل قبل را از قدم چهارم تا يازدهم تكرار كرده و اين اعمال را آنقدر انجام مي دهيم تا به مقدار بهين دست پيدا كنيم.

منبع

www.irexpert.ir
  • تهران
  • 09350579640-09124635768
  • 01152218786
  • این آدرس ایمیل توسط spambots حفاظت می شود. برای دیدن شما نیاز به جاوا اسکریپت دارید

ارسال پیام

  Mail is not sent.   Your email has been sent.
Top