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

الگوریتم ژنتیکی تعریف الگوریتم ژنتیکی ،رویه ای تکراری است که راه حل های انتخابیش را بصورت رشته ای از ژنها که کروموزوم نامیده می شوند ،بازنمایی می کند. موفقیت آنها را با تابع fitnessاندازه می گیرد. تابع fitnessمیزان نزدیکی به هدف را محاسبه می کند. در هر تکرار الگوریتم( ،مانند سیستم های بیولوژیکی) راه حلهای انتخابی ،برای تولید فرزند (که generation نامیده می شوند) ترکیب می شوند. والدین نسل بعدی ،با توجه به fitnessوالدین و فرزندان نسل قبل ،از بین آنها انتخاب می شوند. خود فرزندان نیز می توانند به عنوان راه حل انتخاب شوند. عملگرهای ژنتیکی ،برای تولید فرزندان :Reproduction از طریق این عملگر ،الگوریتمهای ژنتیکی ،نسل جدیدی از راه حلهای بهبودیافته را با انتخاب والدینی که باالترین fitnessرا دارند تولید می کنند. :Crossover با توجه به اینکه الگوریتمهای ژنتیکی از رشته هایی از نمادهای باینری برای کروموزومها استفاده می کنند crossover ،به معنی انتخاب موقعیتی تصادفی در رشته و تعویض بخشهای چپ و راست این نقاط با رشته دیگر برای تولید دو فرزند جدید می باشد. :Mutation تغییر دلخواه در موقعیت است .رویه تغییر یک به صفر و یا صفر به یک می باشد و با احتمال خیلی کم ( )1000/1رخ می دهد. نحوه کار الگوریتم ژنتیک بازنمایی شرح مساله به نحوی که بتواند از طریق الگوریتم ژنتیکی حل شود :بازنمایی راه حل ،بصورت رشته ای از صفر و یک ها. تولید مجموعه اولیه جوابها و محاسبه fitnessآنها. محاسبه مجموع تابع fitness محاسبه احتمال اینکه هر راه حل برای تولید فرزندان انتخاب شود :تقسیم تابع fitnessآن به مجموع انتخاب والدین تولید فرزندان از طریق crossoverیا (با احتمال کم) mutation نسل جدید شامل مجموعه ای از بهترین فرزندان و والدین می باشد. فرایند آنقدر ادامه می یابد تا اینکه راه حل بهینه حاصل شود و یا اینکه در چندین نسل بهبود نداشته باشیم. پارامترهایی که باید تنظیم شوند این پارامترها بستگی به مساله داشته و غالبا از طریق سعی و خطا بدست می آیند: تعداد جوابهای اولیه که تولید می شوند. تعداد فرزندان تعداد فرزندان و والدینی که برای تولید نسل بعد استفاده می شوند. احتمال mutation توزیع احتمال رخداد نقطه crossover بررسی یک مثال: بازی برداری شرح مساله این بازی در برابر حریفی انجام می شود که بطور secretرشته ای 6رقمی می نویسد( .شامل کروموزومها) هر رقم ،صفر یا یک است( .به عنوان مثال: )001010 باید این عدد را حدس بزنید. عددی را که حدس زده اید به حریف ارائه می کنید. او می گوید که چند رقم از آن صحیح است( .تابع )fitness با تفسیر آن حدس بعدی ارائه می شود. سعی و خطای تصادفی وقتیکه 6رقم داریم 64 ،حدس مختلف میتوانیم داشته باشیم. با انتخاب عدد بطور تصادفی ،بطور میانگین بعد از 32حدس به جواب صحیح می رسیم. با استفاده از فیدبک و تفسیر آن (الگوریتم ژنتیکی) این کار تسریع می شود. راه حل ‏ قدم اول 4 :رشته تصادفی به حریف ارائه کنید: .A .B .C .D ‏score=1 ،110100 ‏score=1 ،111101 ‏score=4 ،011011 ‏score=3 ،101100 قدم دوم A :و Bرا به علت امتیاز پایینشان حذف کنید و cو Dرا به عنوان والدین انتخاب کنید. قدم سوم :والدین را پس از شکستن هر یک بین ارقام دوم و سوم ،ترکیب کنید. .A .B .A .B .C .D 01:1011 10:1100 ‏score=3 ،011100 ‏score=4 ،101011 راه حل ‏ به نظر می رسد که فرزندان بهتر از والدین نباشند .قدم چهارم :والدین را بین ارقام چهارم و پنجم بشکنید و ترکیب کنید .C .D .G .H ‏ 0110:11 1011:00 ‏score=4 ،011000 ‏score=3 ،101111 حال قدم دوم را تکرار کنید :بهترین زوج را از تمام حلهای قبلی برای تولید مجدد انتخاب کنید .به عنوان نمونه Gو Fرا انتخاب کرده و فرزندان زیر تولید می شوند: .F .G .H .I 1:01011 0:11000 ‏score=3 ،111000 ‏score=5 ،001011 راه حل و تولیدات زیر: .F .G .K .L ‏ فرایند را با Jو Kتکرار کنید: .J .K .M .F 101:011 011:000 ‏score=4 ،101000 ‏score=4 ،011011 00101:1 10100:0 ‏score=6 ،001010 Mعدد مورد نظر است و پس از 13حدس بدست آمده است. فهرست منابع  Efraim Turban, Jay E. Aronson, “Decision Support Systems and Intelligent Systems”. Sixth Edition, Prentice Hall, 2000. Chapter 16.