آشنایی با الگوریتم ژنتیک دودویی (باینری)

Soft Computing H. Nezamabadi-pour Electrical Eng. Dept., University of Kerman, Kerman, Iran. nezam@mail.uk.ac.ir 1 LECTURE2: Binary GA فرض کنيد که هدف از بهينه­سازي ،پيدا کردن بيشينه تابع fدر يک دامنه مشخص باشد: ‏f  x1,x2,...,xm ‏xilo  xi  xihi fori 1,2,..., ‏m ‏ در اين وضعيت ،پيدا کردن مقاديري براي متغيرهاي حقيقی x1تا xm که تابع ،fبه ازاي آنها بيشترين مقدار را به خود بگيرد. * ‏X است به گونه­اي که به عبارتي هدف ا*ز بيشنه­سازي ،يافتن ‏f ( X * )  f ( X ) , X  D f 2 مد نظر است LECTURE2: Basic Concepts ‏ ‏ ‏ ‏ 3 در حل مساله با الگوريتم وراثتي ،هر يک از متغيرهاي اين مساله بصورت يک ژن در وراثت طبيعي در نظر گرفته مي­شوند. از کنار هم قرار گرفتن تمام متغيرهاي يک مساله (ژنها) ،يک کروموزوم ساخته مي­شود. هلند براي اولين بار از رشته­هاي بيتي براي بيان اطالعات کروموزومها استفاده کرد مثال 3 :متغير و هر متغير 10بيت تعاريف کروموزوم در الگوريتم وراثتي هر کروموزوم بيانگر يک جواب مساله بصورت رمز شده است و يک نقطه در فضاي جستجو را نشان مي­دهد .هر کروموزوم از تعداد مشخصي ژن تشکيل شده است که همان متغيرهاي مساله هستند .در الگوريتم وراثتي باينري ،ژنها از تعداد معيني بيت تشکيل مي­شوند .هر ژن مي­توا*ند مقادير متفاوتي به خود بگيرد که اين مقادير آللهاي يکديگر براي يک متغير در يک مساله هستند. جمعيت مجموعه­اي از کروموزومها ،يک جمعيت را مي­سازند .از هر جمعيت با استفاده از عملگرهاي وراثتي ،يک جمعيت جديد ساخته مي­شود. 4 تعاريف تابع شايستگي (برازندگي) براي حل هر مساله بهينه­سازي ،بايد يک تابع شايستگي طراحي شود .تابع شايستگي براي هر کروموزوم(يک مجموعه از متغيرهاي ورودي) ،يک عدد نامنفي برمي­ گرداند که نشاندهنده کارآيي يا توانايي آن کروموزوم در حل مساله است .درحل بسياري از مسائل ،به خصوص بهينه­سازي توابع ،تابع شايستگي مقدار آن تابع را به ازاي متغيرهاي ورودي برمي­گردا*ند .به عبارت ديگر ،تابع شايستگي همان تابع هدف است .اما در حل مسائل مهندسي در دنياي واقعي ،اغلب بايد يک تابع شايستگي مناسب ابداع و طراحي شود. توليد مثل در مرحله توليد مثل* ،تعدادي از ا*فراد جمعيت نسل قبل انتخاب مي­شوند .اين اعضا ضمن ترکيب با يکديگر نسل جديد را مي­سازند .هر يک از اعضاي انتخاب شده براي توليد مثل ،والد و هر يک ا*ز اعضاي توليد شده ،فرزند ناميده مي­شوند .براي توليد مثل و ساختن نسل بعد از عملگرهاي وراثتي استفاده می­شود که مهمترين آنها ،عملگرهاي انتخاب ،همبري و جهش هستند– . 5 تعاريف عملگر انتخاب با استفاده از اين عملگر از بين کروموزومهاي موجود در يک جمعيت تعدادي براي توليد مثل انتخاب شده و به حوضچه ازدواج منتقل مي­شوند .انتخاب کروموزومها بصورت اتفاقي است اما فرايند انتخاب به گونه­اي است که کروموزومهاي با شايستگي بيشتر از شانس بيشتري برا*ي انتخاب و توليد مثل برخوردار مي­شوند. عملگر همبري عملگر همبري مهمترين عملگر در الگوريتم وراثتي است .اين عملگر بر روي دو (چند) کروموزوم والد عمل همبري را اجرا کرده و دو فرزند براي نسل جديد توليد مي­کند. 6 تعاريف عملگر جهش اين عملگر ،يک ژن از يک کروموزوم را بصورت تصادفي انتخاب کرده و محتويات آن را اندکي تغيير مي­دهد. همگرايي همگرايي ،پيشرفت به سوي يکنواختي است .چنانچه الگوريتم وراثتي به طرز صحيحي پياده­سازي شود ،جمعيت در نسلهاي متمادي تکامل پيدا* مي­کند و متوسط برازندگي جمعيت نسل به نسل به سمت برازندگي بهترين عضو آن جمعيت نزديکتر شده و به سمت بهينه کلي سوق پيدا مي­کند .يک جمعيت زماني همگرا ناميده مي­شود که همه ژنهاي آن همگرا شده باشند و ژني همگرا گفته مي­شود که 95درصد افراد جمعيت مقدار يکساني در آن ژن داشته باشند- . 7 تعاريف 8 ساختار کلي الگوريتم وراثتي 9 قالب کلی ‏t=T ‏t=2 ارزيابی اعضاء انتخاب همبری جهش ارزيابی اعضاء انتخاب همبری جهش عملگرهای الگوريتم شامل انتخاب -همبری – جهش هستند. 10 ‏t=1 ارزيابی اعضاء انتخاب همبری جهش مقدار دهي پارامترها ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ 11 تعيين تعداد اعضاي جمعيت نرخ همبري نرخ جهش تعداد متغيرها طول هر متغير طول* کروموزوم تعيين محدوده هر متغير و دا*منه جستجو نحوه خاتمه الگوريتم ‏m ‏L  Li ‏i1 ساختار کلي الگوريتم وراثتي 12 توليد جمعيت اوليه براي ساختن جم*عيت اوليه کافي است ک*ه يک ماتريس N*L (شامل Nسطر و Lستون) از صفر و يک بصورت اتفاقي با تابع توزيع يکنواخت ساخته شود .در اين شرايط هر سطر اين ماتريس اطالعات مربوط به يک کروموزوم را با خود دارد. يک کروموزوم 13 Population هر کروموزوم يک بردار Lبیتی است .با مقادير 0و1 14 ساختار کلي الگوريتم وراثتي 15 رمز گشايي کروموزومها ابتدا هر کروموزوم بايد به ژنها شکسته شود و هر ژن جداگانه رمزگشايی می شود. ‏Decoding 16 رمز گشايي کروموزومها رمزگشايي ژنها (متغيرها) 17 رمز گشايي کروموزومها  xireal  xilo  xin  xihi  xilo  18 رمز گشايي کروموزومها :يک مثال ‏x2  0100110110 00100 ‏ 2  992410 9924 ‏0.3029 15 2  1 32767 ‏ ‏ ‏ 9924 ‏x2n  ‏x2real  x2lo  x2hi  x2lo x2n  2.1  4 2.1 0.3029 0.2523 19 فرض بر اين است که اين متغير در بازه [ ]-2/1 ،4تعريف شده است. رمز گشايي کروموزومها :خطاي چندي­سازي ‏lo ‏xhi ‏ ‏x ‏j ‏j 2Lj1 20 ‏j  ساختار کلي الگوريتم وراثتي 21 ارزيابي کروموزومها در اين مرحله به ازاي هر يک از بردارهاي ورودي ،مقدار تابع شايستگي محاسبه مي شود .براي اين کار ،مقادير بدست آمده براي متغيرها در تابع شايستگي قرار مي گيرد .خروجي تابع شايستگي به ازاي هر دسته از متغيرهاي ورودي به عنوان شايستگي کروموزوم مربوط به آن در نظر گرفته مي شود. 22 تابع شايستگي Fitness function اين تابع بايد به ازاي هر جواب که توسط کروموزومها ارائه م*ي شود ،عددي نام*نفي و متناسب با کارآيي و شايستگي آن جواب برگرداند. به عبارت ديگر ،اين تابع بايد به گونه­اي طراحي شود که هر چه جواب ارائه شده به جواب به*ينه نزديکتر باشد ،عدد شايستگي بزرگتري برگرداند که نشان دهنده شايستگي بيشتر آن کروموزوم(جواب) است. فرام*وش نشود که تابع شايستگي با توجه به تابع هدف طراحي مي­ شود. 23 نگاشت تابع هدف به تابع شايستگي توابع هدف مثبت حداکثر شونده )Fit(X)=f(X توابع هدف با مقادير منفي ‏0 ‏min ‏for f کمينه کردن توابع هدف 24 ‏f ‏fit X   f ( X )  )  f (X ‏fit X   f , ‏min ‏max ارزيابی Evaluation در هر تکرار ،به ازای هر عضو يکبار مساله حل می شود. حل مساله ‏Fitness function تابع برازندگی (شايستگی) 25 ‏Objective function تابع هدف ساختار کلي الگوريتم وراثتي 26 عملگر انتخاب Selection ‏ ‏ ‏ ‏ 27 عملگر انتخاب در الگوريتم وراثتي ،برداشتي از انتخاب طبيعي در وراثت طبيعي است. هدف از اعمال اين عملگر ،انتخاب بعضي از افراد جمعيت براي زاد و ولد و ايجاد نسل بعد است مشهورترين عملگر انتخاب ،انتخاب متناسب با شايستگي است که براي پياده سازي آن از چرخ گردان استفاده مي شود اين روش به انتخاب چرخ گردان شهرت پيدا کرده است. عملگر انتخاب در انتخاب متناسب با برازندگي به کروموزومهاي شايسته­تر(جوابهاي بهتر) ،شانس بيشتر و به کروموزومهاي ضعيفتر(جوابهاي بدتر) شانس کمتري براي بقا و توليد مثل داده مي­شود. در الگوريتم وراثتي عملگرها بر پايه احتماالت عمل مي­کنند و قطعيتي در کار نيست .اين موضوع به اين معني است که به هر يک از کروموزومها متناسب با شايستگي­شان شانسي براي انتخاب تعلق مي­گيرد ،ولي انتخاب بر مبناي احتمال صورت مي­پذيرد. 28  چرخ گردان:عملگر انتخاب Pi  fiti N  fitj j 1 EVi  Pi N 29 ساختار کلي الگوريتم وراثتي 30 عملگر همبري Cross over اين عملگر مهمترين عملگر در الگوريتم وراثتي است براي ساختن نسل بعد ،دو کروموزوم از حوضچه ازدواج به عنوان والد انتخاب شده و با عمل همبري دو فرزند بوجود ميآيد. که عملگر همبري بطور قطعي روي تمام والدين اجرا نمي­شود (احتمال همبري PCمعموالً عددي بين 0.6و )0.9 31 عملگر همبري عملگر همبري در دو گام انجام مي شود: گام اول :از بين افراد موجود در حوضچه تزويج ،دو نفر بصورت اتفاقي براي همبري انتخاب مي شوند. گام دوم :دو کروموزوم منتخب به عنوان وال*دين ،طي يکي از روشهاي همبري فرزند يا انتقال زوج فرزنداني توليد مي کنند. 32 عملگر همبري برای هر زوج ‏If rand<Pc همبری ‏Else انتقال ‏end 33 عملگر همبري تک نقطه اي ‏Cross point 34 ساختار کلي الگوريتم وراثتي 35 عملگر جهش Mutation اين عملگر بطور عام بعد از عملگر همبري اعمال مي شود. احتمال رخداد جهش در الگوريتم وراثتي با Pmنمايش داده مي شود که معموالً بين 0.001تا 0.01انتخاب مي شود. عملگر جهش به هر يک از افراد جمعيت به تنهايي اعمال مي شود. ‏Pm LN 36 ساختار کلي الگوريتم وراثتي 37 ساير مراحل جايگزيني نسل بعد چک کردن شرط توقف Stopping criteria 38 حل يک مسئله نمونه f ( X )  f (x1, x2) 1 cos 2 x1x2   exp   x1  x2  / 2  4  x1 2 ,  1.5  x2 1 , f opt 2 for X *  0, 0 39 مقدار دهي پارامترها و تعريف تابع شايستگي 40 حل يک مسئله نمونه 41 احتمال تجمعي و چرخ گردان i Ci  Pj j 1 Ci 1 q  Ci , C0 0 , i 1,2,....N 42 حل يک مسئله نمونه 43 حل يک مسئله نمونه 44 ارزيابي کارآيي الگوريتم وراثتي ارزيابي کارآيي الگوريتم وراثتي يا هر الگوريتم ابتکاري ديگر ،از طريق تحليل همگرايي و زمان رسيدن به پاسخ بهينه بررسي مي­شود .براي مشاهده وضعيت پيشرفت الگوريتم و پايش معيارهاي فوق از روشهاي ترسيمي کمک گرفته مي­شود ‏mean-fitness متوسط شايستگي جمعيت بهترين جواب ديده شده تا آن لحظه best-so-far 45 ارزيابی کارايی الگوريتم ‏t=2 ‏t=T ‏t=1 …………… ميانگين هر تکرار بهترين تا هر تکرار 46 ])mf(T ])bsf(T ……………………… ……………………… )mf(2 )bsf(2 ‏mean )Fitness=[mf(1 ‏best )So far =[bsf(1 ارزيابي کارآيي الگوريتم وراثتي در الگوريتم پياده سازي شده ،از جمعيتي شامل 30کروموزوم با طول 16 بيت استفاده شده است .نرخ همبري و جهش به ترتيب 0.9و 0.005 در نظر گرفته شده است و الگوريتم براي 100تکرار اجرا شده است. 47 ارزيابي و مقايسه کارآيي آيا مقايسه الگوريتم ها با يک اجرا عادالنه است؟ 48 ارزيابي و مقايسه کارآيي الگوريتم ها تصادفی هستند .و با هر بار اجرا جواب های متفاوتی می دهند. برای مقايسه عادالنه ،هر الگوريتم را چند بار اجرا کرده و ميانگين نتايج را گزارش می کنند. 49 ارزيابی در چند اجرای مستقل الگوريتم Run1 [bsf(1) Run2 [bsf(1) Run3 . . . . Run20 [bsf(1) [bsf(1) Average best So far =[absf(1) bsf(2) bsf(2) bsf(2) bsf(2) absf(2) ……………………… ……………………… ……………………… ……………………… ……………………… bsf(T)] bsf(T)] bsf(T)] bsf(T)] absf(T)] 50 ارزيابي کارآيي الگوريتم وراثتي متوسط معيارهاي قبلي 51 ارزيابي کارآيي الگوريتم وراثتي  1T1 N fon(T)     fiti  t  T t1 N i1  معيار برخط معيار برون خط معيار سرعت همگرايي 1 T max foff (T)   fit  t T t1 f maxT  V  Ln max f 1 52 مقايسه کارآيي الگوريتم های مختلف رسم کردن نمودارهای الگوريتم ها در يک شکل استفاده از جداول 53 مقايسه کارآيي الگوريتم های مختلف مقايسه با رسم کردن نمودارهای الگوريتم ها در يک شکل 54 مقايسه کارآيي الگوريتم های مختلف مقايسه با استفاده از جداول Run1 [bsf(1) Run2 [bsf(1) Run3 . . . . Run20 [bsf(1) [bsf(1) bsf(2) bsf(2) bsf(2) bsf(2) ……………………… ……………………… ……………………… ……………………… bsf(T)] bsf(T)] bsf(T)] bsf(T)] 55 مقايسه کارآيي الگوريتم های مختلف مقايسه با استفاده از جداول 56 )Time (sec ‏Best ‏Mean ± Var ‏Algorithm 2 1.22 1.0 ± 0.2 ‏A 1.5 1.72 1.7 ± 0.1 ‏B 2.5 0.95 0.9 ± 0.05 ‏C کاوش و بهره گيري 57  Convergence  Exploration / diversification  Exploitation / intensification 58 نوشتن يک برنامه وراثتي باينري ساده 59 نوشتن يک برنامه وراثتي باينري ساده 60 نوشتن يک برنامه وراثتي باينري ساده 61 نوشتن يک برنامه وراثتي باينري ساده 62 نوشتن يک برنامه وراثتي باينري ساده 63 نوشتن يک برنامه وراثتي باينري ساده 64 نوشتن يک برنامه وراثتي باينري ساده 65