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

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

اسلاید 1: Soft ComputingH. Nezamabadi-pourElectrical Eng. Dept.,University of Kerman, Kerman, Iran.nezam@mail.uk.ac.ir1

اسلاید 2: LECTURE2: Binary GAفرض کنيد که هدف از بهينه­سازي، پيدا کردن بيشينه تابع f در يک دامنه مشخص باشد:در اين وضعيت، پيدا کردن مقاديري براي متغيرهاي حقيقی تا مد نظر است که تابع f، به ازاي آنها بيشترين مقدار را به خود بگيرد.به عبارتي هدف از بيشنه­سازي، يافتن است به گونه­اي که 2

اسلاید 3: LECTURE2: Basic Conceptsدر حل مساله با الگوريتم وراثتي، هر يک از متغيرهاي اين مساله بصورت يک ژن در وراثت طبيعي در نظر گرفته مي­شوند. از کنار هم قرار گرفتن تمام متغيرهاي يک مساله (ژنها)، يک کروموزوم ساخته مي­شود.هلند براي اولين بار از رشته­هاي بيتي براي بيان اطلاعات کروموزومها استفاده کرد مثال: 3 متغير و هر متغير 10 بيت3

اسلاید 4: تعاريفکروموزومدر الگوريتم وراثتي هر کروموزوم بيانگر يک جواب مساله بصورت رمز شده است و يک نقطه در فضاي جستجو را نشان مي­دهد. هر کروموزوم از تعداد مشخصي ژن تشکيل شده است که همان متغيرهاي مساله هستند. در الگوريتم وراثتي باينري، ژنها از تعداد معيني بيت تشکيل مي­شوند. هر ژن مي­تواند مقادير متفاوتي به خود بگيرد که اين مقادير آللهاي يکديگر براي يک متغير در يک مساله هستند.جمعيتمجموعه­اي از کروموزومها، يک جمعيت را مي­سازند. از هر جمعيت با استفاده از عملگرهاي وراثتي، يک جمعيت جديد ساخته مي­شود. 4

اسلاید 5: تعاريفتابع شايستگي (برازندگي)براي حل هر مساله بهينه­سازي، بايد يک تابع شايستگي طراحي شود. تابع شايستگي براي هر کروموزوم(يک مجموعه از متغيرهاي ورودي)، يک عدد نامنفي برمي­گرداند که نشاندهنده کارآيي يا توانايي آن کروموزوم در حل مساله است. درحل بسياري از مسائل، به خصوص بهينه­سازي توابع، تابع شايستگي مقدار آن تابع را به ازاي متغيرهاي ورودي برمي­گرداند. به عبارت ديگر، تابع شايستگي همان تابع هدف است. اما در حل مسائل مهندسي در دنياي واقعي، اغلب بايد يک تابع شايستگي مناسب ابداع و طراحي شود. توليد مثلدر مرحله توليد مثل، تعدادي از افراد جمعيت نسل قبل انتخاب مي­شوند. اين اعضا ضمن ترکيب با يکديگر نسل جديد را مي­سازند. هر يک از اعضاي انتخاب شده براي توليد مثل، والد و هر يک از اعضاي توليد شده، فرزند ناميده مي­شوند. براي توليد مثل و ساختن نسل بعد از عملگرهاي وراثتي استفاده می­شود که مهمترين آنها، عملگرهاي انتخاب، همبري و جهش هستند. –5

اسلاید 6: تعاريفعملگر انتخاببا استفاده از اين عملگر از بين کروموزومهاي موجود در يک جمعيت تعدادي براي توليد مثل انتخاب شده و به حوضچه ازدواج منتقل مي­شوند. انتخاب کروموزومها بصورت اتفاقي است اما فرايند انتخاب به گونه­اي است که کروموزومهاي با شايستگي بيشتر از شانس بيشتري براي انتخاب و توليد مثل برخوردار مي­شوند.عملگر همبريعملگر همبري مهمترين عملگر در الگوريتم وراثتي است. اين عملگر بر روي دو (چند) کروموزوم والد عمل همبري را اجرا کرده و دو فرزند براي نسل جديد توليد مي­کند.6

اسلاید 7: تعاريفعملگر جهشاين عملگر، يک ژن از يک کروموزوم را بصورت تصادفي انتخاب کرده و محتويات آن را اندکي تغيير مي­دهد. همگراييهمگرايي، پيشرفت به سوي يکنواختي است. چنانچه الگوريتم وراثتي به طرز صحيحي پياده­سازي شود، جمعيت در نسلهاي متمادي تکامل پيدا مي­کند و متوسط برازندگي جمعيت نسل به نسل به سمت برازندگي بهترين عضو آن جمعيت نزديکتر شده و به سمت بهينه کلي سوق پيدا مي­کند. يک جمعيت زماني همگرا ناميده مي­شود که همه ژنهاي آن همگرا شده باشند و ژني همگرا گفته مي­شود که 95 درصد افراد جمعيت مقدار يکساني در آن ژن داشته باشند. -7

اسلاید 8: تعاريف8

اسلاید 9: ساختار کلي الگوريتم وراثتي9

اسلاید 10: قالب کلی10ارزيابی اعضاءانتخابهمبریجهشعملگرهای الگوريتم شامل انتخاب- همبری – جهش هستند.ارزيابی اعضاءانتخابهمبریجهشارزيابی اعضاءانتخابهمبریجهشt=1t=2t=T

اسلاید 11: مقدار دهي پارامترهاتعيين تعداد اعضاي جمعيت نرخ همبرينرخ جهش تعداد متغيرها طول هر متغير طول کروموزوم تعيين محدوده هر متغير و دامنه جستجو نحوه خاتمه الگوريتم11

اسلاید 12: ساختار کلي الگوريتم وراثتي12

اسلاید 13: توليد جمعيت اوليهبراي ساختن جمعيت اوليه کافي است که يک ماتريس N*L (شامل N سطر و L ستون) از صفر و يک بصورت اتفاقي با تابع توزيع يکنواخت ساخته شود. در اين شرايط هر سطر اين ماتريس اطلاعات مربوط به يک کروموزوم را با خود دارد.يک کروموزوم13

اسلاید 14: هر کروموزوم يک بردار L بیتی است. با مقادير 0 و 1Population  14

اسلاید 15: ساختار کلي الگوريتم وراثتي15

اسلاید 16: رمز گشايي کروموزومهاDecoding ابتدا هر کروموزوم بايد به ژنها شکسته شود و هر ژن جداگانه رمزگشايی می شود.16

اسلاید 17: رمز گشايي کروموزومهارمزگشايي ژنها (متغيرها)17

اسلاید 18: رمز گشايي کروموزومها18

اسلاید 19: رمز گشايي کروموزومها: يک مثالفرض بر اين است که اين متغير در بازه [4، 2/1-] تعريف شده است. 19

اسلاید 20: رمز گشايي کروموزومها: خطاي چندي­سازي 20

اسلاید 21: ساختار کلي الگوريتم وراثتي21

اسلاید 22: ارزيابي کروموزومهادر اين مرحله به ازاي هر يک از بردارهاي ورودي، مقدار تابع شايستگي محاسبه مي شود. براي اين کار، مقادير بدست آمده براي متغيرها در تابع شايستگي قرار مي گيرد. خروجي تابع شايستگي به ازاي هر دسته از متغيرهاي ورودي به عنوان شايستگي کروموزوم مربوط به آن در نظر گرفته مي شود. 22

اسلاید 23: تابع شايستگي Fitness functionاين تابع بايد به ازاي هر جواب که توسط کروموزومها ارائه مي شود، عددي نامنفي و متناسب با کارآيي و شايستگي آن جواب برگرداند. به عبارت ديگر، اين تابع بايد به گونه­اي طراحي شود که هر چه جواب ارائه شده به جواب بهينه نزديکتر باشد، عدد شايستگي بزرگتري برگرداند که نشان دهنده شايستگي بيشتر آن کروموزوم(جواب) است. فراموش نشود که تابع شايستگي با توجه به تابع هدف طراحي مي­شود.23

اسلاید 24: نگاشت تابع هدف به تابع شايستگيتوابع هدف مثبت حداکثر شوندهتوابع هدف با مقادير منفيکمينه کردن توابع هدف 24Fit(X)=f(X)

اسلاید 25: در هر تکرار، به ازای هر عضو يکبار مساله حل می شود.ارزيابی Evaluation  حل مسالهObjective functionتابع هدفFitness functionتابع برازندگی (شايستگی) 25

اسلاید 26: ساختار کلي الگوريتم وراثتي26

اسلاید 27: عملگر انتخاب Selectionعملگر انتخاب در الگوريتم وراثتي، برداشتي از انتخاب طبيعي در وراثت طبيعي است.هدف از اعمال اين عملگر، انتخاب بعضي از افراد جمعيت براي زاد و ولد و ايجاد نسل بعد استمشهورترين عملگر انتخاب، انتخاب متناسب با شايستگي است که براي پياده سازي آن از چرخ گردان استفاده مي شوداين روش به انتخاب چرخ گردان شهرت پيدا کرده است.27

اسلاید 28: عملگر انتخابدر انتخاب متناسب با برازندگي به کروموزومهاي شايسته­تر(جوابهاي بهتر)، شانس بيشتر و به کروموزومهاي ضعيفتر(جوابهاي بدتر) شانس کمتري براي بقا و توليد مثل داده مي­شود. در الگوريتم وراثتي عملگرها بر پايه احتمالات عمل مي­کنند و قطعيتي در کار نيست. اين موضوع به اين معني است که به هر يک از کروموزومها متناسب با شايستگي­شان شانسي براي انتخاب تعلق مي­گيرد، ولي انتخاب بر مبناي احتمال صورت مي­پذيرد. 28

اسلاید 29: عملگر انتخاب: چرخ گردان 29

اسلاید 30: ساختار کلي الگوريتم وراثتي30

اسلاید 31: عملگر همبري Cross overاين عملگر مهمترين عملگر در الگوريتم وراثتي استبراي ساختن نسل بعد، دو کروموزوم از حوضچه ازدواج به عنوان والد انتخاب شده و با عمل همبري دو فرزند بوجود ميآيد.که عملگر همبري بطور قطعي روي تمام والدين اجرا نمي­شود (احتمال همبري معمولاً عددي بين 0.6 و 0.9)31

اسلاید 32: عملگر همبريعملگر همبري در دو گام انجام مي شود:گام اول: از بين افراد موجود در حوضچه تزويج، دو نفر بصورت اتفاقي براي همبري انتخاب مي شوند.گام دوم: دو کروموزوم منتخب به عنوان والدين، طي يکي از روشهاي همبري فرزند يا انتقال زوج فرزنداني توليد مي کنند.32  

اسلاید 33: عملگر همبريبرای هر زوجIf rand<Pc همبریElse انتقال end33

اسلاید 34: عملگر همبري تک نقطه ايCross point34

اسلاید 35: ساختار کلي الگوريتم وراثتي35

اسلاید 36: عملگر جهش Mutationاين عملگر بطور عام بعد از عملگر همبري اعمال مي شود. احتمال رخداد جهش در الگوريتم وراثتي با Pm نمايش داده مي شود که معمولاً بين 0.001 تا 0.01 انتخاب مي شود. عملگر جهش به هر يک از افراد جمعيت به تنهايي اعمال مي شود.36

اسلاید 37: ساختار کلي الگوريتم وراثتي37

اسلاید 38: ساير مراحلجايگزيني نسل بعد چک کردن شرط توقف Stopping criteria38

اسلاید 39: حل يک مسئله نمونه39

اسلاید 40: مقدار دهي پارامترها و تعريف تابع شايستگي40

اسلاید 41: حل يک مسئله نمونه41

اسلاید 42: احتمال تجمعي و چرخ گردان42

اسلاید 43: حل يک مسئله نمونه43

اسلاید 44: حل يک مسئله نمونه44

اسلاید 45: ارزيابي کارآيي الگوريتم وراثتيارزيابي کارآيي الگوريتم وراثتي يا هر الگوريتم ابتکاري ديگر، از طريق تحليل همگرايي و زمان رسيدن به پاسخ بهينه بررسي مي­شود. براي مشاهده وضعيت پيشرفت الگوريتم و پايش معيارهاي فوق از روشهاي ترسيمي کمک گرفته مي­شودمتوسط شايستگي جمعيت mean-fitness بهترين جواب ديده شده تا آن لحظه best-so-far45

اسلاید 46: ارزيابی کارايی الگوريتم46   t=1t=2t=T……………meanFitness=[mf(1) mf(2) ……………………… mf(T)]بهترين تا هر تکرار bestSo far =[bsf(1) bsf(2) ……………………… bsf(T)]ميانگين هر تکرار

اسلاید 47: ارزيابي کارآيي الگوريتم وراثتيدر الگوريتم پياده سازي شده، از جمعيتي شامل 30 کروموزوم با طول 16 بيت استفاده شده است. نرخ همبري و جهش به ترتيب 0.9 و 0.005 در نظر گرفته شده است و الگوريتم براي 100 تکرار اجرا شده است. 47

اسلاید 48: ارزيابي و مقايسه کارآييآيا مقايسه الگوريتم ها با يک اجرا عادلانه است؟48

اسلاید 49: ارزيابي و مقايسه کارآييالگوريتم ها تصادفی هستند. و با هر بار اجرا جواب های متفاوتی می دهند.برای مقايسه عادلانه، هر الگوريتم را چند بار اجرا کرده و ميانگين نتايج را گزارش می کنند.49

اسلاید 50: ارزيابی در چند اجرای مستقل الگوريتم50Average bestSo far =[absf(1) absf(2) ……………………… absf(T)]Run1 [bsf(1) bsf(2) ……………………… bsf(T)]Run2 [bsf(1) bsf(2) ……………………… bsf(T)]Run3 [bsf(1) bsf(2) ……………………… bsf(T)]. ...Run20 [bsf(1) bsf(2) ……………………… bsf(T)]

اسلاید 51: ارزيابي کارآيي الگوريتم وراثتيمتوسط معيارهاي قبلي 51

اسلاید 52: ارزيابي کارآيي الگوريتم وراثتيمعيار برخطمعيار برون خطمعيار سرعت همگرايي52

اسلاید 53: مقايسه کارآيي الگوريتم های مختلفرسم کردن نمودارهای الگوريتم ها در يک شکلاستفاده از جداول53

اسلاید 54: مقايسه کارآيي الگوريتم های مختلفمقايسه با رسم کردن نمودارهای الگوريتم ها در يک شکل54

اسلاید 55: مقايسه کارآيي الگوريتم های مختلفمقايسه با استفاده از جداول55Run1 [bsf(1) bsf(2) ……………………… bsf(T)]Run2 [bsf(1) bsf(2) ……………………… bsf(T)]Run3 [bsf(1) bsf(2) ……………………… bsf(T)]. ...Run20 [bsf(1) bsf(2) ……………………… bsf(T)]

اسلاید 56: مقايسه کارآيي الگوريتم های مختلفمقايسه با استفاده از جداول56AlgorithmMean ± VarBestTime (sec)A1.0 ± 0.21.222B1.7 ± 0.11.721.5C0.9 ± 0.050.952.5

اسلاید 57: کاوش و بهره گيري57

اسلاید 58: ConvergenceExploration / diversificationExploitation / intensification58

اسلاید 59: نوشتن يک برنامه وراثتي باينري ساده59

اسلاید 60: نوشتن يک برنامه وراثتي باينري ساده60

اسلاید 61: نوشتن يک برنامه وراثتي باينري ساده61

اسلاید 62: نوشتن يک برنامه وراثتي باينري ساده62

اسلاید 63: نوشتن يک برنامه وراثتي باينري ساده63

اسلاید 64: نوشتن يک برنامه وراثتي باينري ساده64

اسلاید 65: نوشتن يک برنامه وراثتي باينري ساده65