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

صفحه 1:
oti 

صفحه 2:


صفحه 3:


صفحه 4:
ایراتورهای ژنتیکی 1۷6۲۵100 : Crowding ® © راه حل رقع مشكل ‎Crowding‏ ‏* جرا 4© كار ميكند؟ * ارزيابى جمعيت و قضیه 50116703 

صفحه 5:
نتیک روش یادگیری بر پایه تکامل بیولوژیک است. “اين روش در سال 1970 توسط 1101131201 01112[ معرفى كرديد #اين روشها با نام 41601311:13035 ۳۷01121012717 نیز خوانده وت 

صفحه 6:
#يى /3) برای حل یک مسئله مجموعه بسیار بزرگی از راه حلهای ممکن را تولید میکند. #هر يك از اين راه حلها با استفاده از یک " تابع تناسب" مورد ارزیابی قرار #آنگاه تعدادی از بهترین راه حلها باعث تولید راه حلهای جدیدی میشوند. که اینکار باعث تکامل راه حلها میگردد. #بدین ترتیب فضای جستجو در جهتی تکامل پیدا میکند که به راه حل مطلوب 7 #در صورت انتخاب صحیح پارامترهاء اين روش میتواند بسیار موثر عمل نماید. 

صفحه 7:
؟الگوریتم ژنتیک بجای جستجوی فرضیه های ‎General-to‏ ‎simple to complex tg specific‏ فرضیه ها ک‌جدید را با تغییر و ترکیب متوالی اجزا بهترین فرضیه های موجود بدست میاورد. #در هرمرحله مجموعه اى از فرضيه ها كه جمعيت (207111351011) ناميده ميشوند از طريق جايكزينى بخشى از جمعيت فعلى با فرزندانى كه از بهترين فرضيه هاى موجود حاصل شده اند بدست ميآيد. 

صفحه 8:
الگوریتم های ژنتیک در مسائلی که ‎Vales‏ جستجوی بزرگی داشته باشند میتواند ر گرفته شود. #همجنين در مسايلى با فضاى فوضيه بيجيده که تاثیر اجزا آن در فرضیه كلى تاشتاخته باشتد میتوان از تا برای جستجو استفاده نمود. #براى 021120212211012 01501616بسيار مورد استفاده قرار ميكيرد. ؟الگوریتم های ژنتیک را ميتوان براحتى بصورت موازى اجرا نمود از اينرو میتوان ان کامپیوترهای ارران قیمت تری را بضورت موازی مورد استفانه قرار داد #امكان به تله افتادن اين الكوريتم در مینیمم محلی کمتر از سایر روشهاست. ‎ae‏ لحاظ محاسباتی پرهزینه هستند. تضمینی برای رسیدن به جواب بهینه وجود ندارد. 

صفحه 9:
سال 1999 ‎x, .Genetic Programming Inc i‏ موازی با 1000 گره هر یک شامل کامپیوتر های 350 ‎Py,‏ ‎ith fiz‏ برای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد. 

صفحه 10:
؟کاربرد الگوریتم های ژنتیک بسیار زياد میباشد ‎optimization,‏ © ‎automatic programming,‏ © ‎machine learning,‏ ® ‎economics,‏ ® ‎operations research,‏ © ‎ecology,‏ ® ‎studies of evolution and learning, and‏ ® ‎social systems‏ ® 

صفحه 11:
سس 0 - سس سس روش های ۳۵ به دو نوع مرتبط به هم ولی مجزا دسته بندی میشوند: ‎Genetic Algorithms (GAs)‏ در اين روش راه حل یک مسئله بصورت ‎Dit string SK‏ نشان داده میشود. ‎Genetic Programming (GP)‏ اين روش به تولید 7665 626016551010 که در زبانهای برنامه نویسی مثل 1150 مورد استفاده هستند میپردازد بدین ترتیب میتوان برنامه هائی ساخت که قابل اجرا باشند. 

صفحه 12:
| ال __ روش متداول پیاده سازی الگوریتم ژنتیک بدین ترتیب است که #مجموعه ای از فرضیه ها که 00011121101 نامیده میشود تولید وبطور متناوب با فرضیه های جدیدی جایگزین میگردد. #در هر بار تکرارتمامی فرضیه ها با استفاده از یک تابع تناسب يا ۳10695 مورد ارزیابی قرار داده میشوند. آنگاه تعدادی از بهترین فرضیه ها با استفاده از یک تابع احتمال انتخاب شده و جمعیت جدید را تشکیل میدهند. #تعدادی از این فرضیه های انتخاب شده به همان صورت مورد استفاده واقع شده ومابقی با استفاده از اپراتورهای ژنتیکی نظیر 01095076۳ و 1 برای تولید فرزندان بکار میروند. 

صفحه 13:
یک الگوریتم 62/۸ دارای پارامترهای زیر است: ‎GA(Fitness,Fitness_threshold,p,rm)‏ ‏©: 2695 تابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه تسبت میدهد ‎ali! jude Fitness_threshold :®‏ كه شرط يايان را معين ميكند ‏©: 2 تعداد فرضيه هائى كه بايد در جمعيت در نظر كرفته شوند ‏۴ در صدى از جمعيت كه در هر مرحله توسط الكوريتم 0۲0550761 جايكزين ميشوند ‎mutation ¢; m:° ‎ ‎ 

صفحه 14:
۴ 1181120 آجمعیت را با تعداد 0 فرضیه بطور تصادفی مقدار دهی اولیه کنید. ‎Fitness(h) et jos p oh 42,3 » ul,Evaluate :®‏ را ‎Fitness threshold > [max, Fitness(h)]s.t.; b® ‏یک جمعیت جدید ایجاد کنید.‎ ‏#فرضیه ای که دارای بیشترین مقدار ۳1111655 است را برگردانید. ‎ ‎ 

صفحه 15:
مراحل ایجاد یک جمعیت جدید بصورت زیر است: : 6 مداد( 0)۳-1 فرضیه از میان ظ انتخاب وبه, اضافه کنید. احتمال انتخاب یک فرضیه,10 از میان] عبارت است از: (زط) عععصاز۴ ز< / (نط) عععصاز۴ > (نط۳ هر جه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است. این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد. تعداد(2/)1[0 زوج فرضیه از ان ایجاد کنید. فرزندان را به : ۳055016۳)با استفاده از احتمال بدست آمده توسط ‎lal,‏ ‏میان 3 انتخاب وبا استفاده از اپراتو ‎Crossover‏ دو فرزند از و3 اضافه کنید. ‎slsMutate :‏ ۲0 درصد از اعضا و3 را با احتمال یکنواخت انتخاب ویک بیت از هر یک آنها را بصورت تصادفی معکوس کنید. ‎P¢€ P, :Update ‏برای هر فرضیه 0 در 8 مقدار تابع 12695 را محاسبه کنید ‎ ‎ 

صفحه 16:
‎aie a ea os s‏ تک برروی آنها ساده تر باشد. ‎Phenotype :‏ « ‏ها گفته میشود که مورد استفاده 68 قرار میگیرند. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 17:
© براى نمايش مقادير يك ويزكى نظير 011610016 كه داراى سه مقدار ,5101111037 ‎C4! Overcast ,Rain‏ ميتوان از رشته اى با طول 3 بيت استفاده نمود 100 -> Outlook = Sunny 011-> Outlook = Overcast ‘ Rain برای نمایش تر کیب ویژگی ها رشته بيت هاى هر يك را يشت سر هم قرار میدهیم: Outlook Wind 011 4 ‏را میتوان با پشت سر هم قرار دادن پیت های قسمبل‎ IE then oy ‏به همین ترتیب کل یک‎ ‏شرط ونتیجه ایجاد نمود:‎ مر( < وم ارو ۳۹۱۷۸۵۵ بمسرق < لو ‎AP‏ 1 ‏ول‎ = bit string: 111100 111 10 

صفحه 18:
ممکن است ترکیب بعضی از بیت ها منجر به فرضیه های بی معنی گردد. برای پرهیز از چنین وضعیتی : وان از روش اتکد ننک دیکری اناد وود #اپراتورهای ژنتیکی را طوری تعیین نمود که چنین حالتهائی را حذف نمایند #میتوان به این فرضیه ها مقدار 11111655 خیلی کمی نسبت داد. 

صفحه 19:
اپراتورهای ژنتیکی 01095076۲ : *اپراتور 10950761 با استفاده از دو رشته والد دو رشته فرزند بوجود میآورد. *برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی میشود. #انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود © single-point crossover © Two-point crossover © Uniform crossover #برای تعیین محل بیتهای کپی شونده از یک رشته 4 ‎Crossover pb‏ 16 استفاده میشود. 

صفحه 20:
Single-point crossover #یک نقطه تصادفی در طول رشته انتخاب میشود. #والدین در اين نقطه به دوقسمت میشوند. #هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید. ‎ed‏ 000000 نج( میم ‎ ‎ 

صفحه 21:
Crossover ‏روشهای دیگر‎ Two-point ۴ 000000000000000 جاده <) -صممووم 0 Uniform crossover ° Orossover Desk: IDOAIDIDOdd ‏سیل)‎ 

صفحه 22:
تورهای ژنتیکی ۷۲01۵1101 : #اپراتور 1010181101 برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد. ‎Le‏ استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند. ‏*معمولا 1301011017 بعد از انجام 010950767 اعمال ميشود. ‎ ‎ 

صفحه 23:
این سوال ها سالها مطرح بوده است: کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟ #پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده: © بستكى به صورت مسئله دارد © در حالت كلى بهتر است از هر دو استفاده شود © هر كدام نقش مخصوص خود را دارد © ميتوان الكوريتمى داشت كه فقط از 10116811013 استفاده كند ولى الكوريتمى كه فقط از6۳05501767 استفاده کند کار نخواهد کرد 

صفحه 24:
2Crossover OR mutation ‎Sean eso‏ بت 0 سس س یت ‎Crossover®‏ خاصیتجستجوگرلنه و یا 61601011176 دارد. میتولندبا لنجام پرشهایب زرگبه محل‌هانی‌دوبینوادین‌یفته و نوحی‌جدیدی‌را ک‌شفن ماید. ‏10 خخاصیتگ سترشیو یا 66۳01011176 دارد. میتند با لنجام ت-غییرلتک وچکت صادفیبه ن ولحیک شفشدم وسعتب بخشد. ‏۲055076)اطلاعات والدین را ترکیب میکند درحالیکه ]10121 میتواند اطلاعات جدیدی اضافه نماید. ‏۴برای رسیدن به یک پاسخ بهینه یک خوش شانسی در 0102101 لازم ‏است. ‎ ‎ ‎ 

صفحه 25:
#تابع 106595 معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد: ‎Classification :®‏ در اين نوع مسایل تابع تناسب معمولا برابر است با ‏دفت قانون در دسته بندی متالهای آموزشی . ‎ 

صفحه 26:
Roulette Wheel selection® ‏در روش معرفی شده در الگوریتم ساده 2) احتمال‎ ‏انتخاب بک فرضیه برای استفاده در جمعیت بعدی‎ ‏بستگی به نسبت 0655 آن به 0655 بقیه‎ Picexs(b) = 9 Roulette ۷۷۲۵61 ‏اعضا دارد. این روش‎ 1601101 ونامیده میشود. عععص۴ ز< / (نط) ‎Ficese(®) = ۰ p(hi) = Fitness‏ ‎Picese(©) = @ (hj)‏ * روشهای دیگر: ‎tounnnved selevio ©‏ ‎roth seteviiza ©‏ 

صفحه 27:
#روش جستجوی 2) با روشهای دیگر مثل شبکه های عصبی تفاوت دارد: #در شبکه عصبی روش ‎Gradient descent‏ بصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه 3/4) ممكن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشداز اینرو احتمال گیر افتادن 2۸ در مینیمم محلی کاهش می ‎eh‏ #با این وجود /2) با مشکل دیگری روبروست که 0101011120 نامیده عيشوة + 

صفحه 28:
Crowding ۴ پدیده لی لستکه در آن عضوی‌که سازگلیی بسیربیشتریاز بقیه لفراد جمعیندارد بطور مرتبتولید نسل‌ک رده و باتولید لعضای‌مشابه دیصد عمده لیاز جمعیترا لشغا (میکند. گاینکار باعث کاهش پراکندگی جمعیت شده وسرعت 3/4) را كم ميكند. F(X) 

صفحه 29:
*استفاده از ۲۵۳16110 برای انتخاب نمونه ها: با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند مقدار این برتری نشان داده نخواهد © : 5121126 11152655 مقدار 1"112655 یک عضودر صورتیکه اعضا مشابهى در جمعيت وجود داشته باشند كاهش مى يابد. 

صفحه 30:


صفحه 31:
ارزيابى جمعيت و قضيه 560116122 ‎eee‏ اس [0)ا سس سس سس سس ‏#آیا میتوان تکامل در جمعیت در طی زمان را بصورت ریاضی مدل نمود؟ ‏#قضیه 5026108 میتواند مشخصه پدیده تکامل در 3۸) را بیان نماید. ‏یک ‎٩06۳08‏ مجموعه ای از رشته بیت ها را توصیف میکند-یک 5026108 هر رشته ای از 0 و1و* است. مثل 10*0 که * حالت ‎care‏ 010۳ است. ‏یک رشته پیت را میتوان نماینده هر یک از ‎cleSchema‏ متفاوتی دانست که با آن تطابق دارند. مثلا 0010 را میتوان نماینده 24 ‎Schema‏ ‏مختلف داتست ۳۲0,۳۵ : وغیره ‎ ‎ 

صفحه 32:
Schema 423 #قضيه 50116122 بيان ميكند كه جكونه يك 56126122 در طول زمان در جمعيت تكامل بيدا خواهد كرد. #فرض كنيد كه در لحظه آ تعداد نمونه هائى كه نماينده یک ‎Schema‏ ‏مثل 5 هستند برابر با (,10)5 باشد. این قضیه مقدار مورد انتظار او ,| طحم شكدذةا #قبلا ديديم كه احتمال انتخاب يك فرضيه برابر بود با: P(h,) = Fitness (h,) / 2, Fitness (h;) ‏#اين مقدار احتمال را میتوان بصورت زیر نیز نشان داد:‎ P(h,) = f (hy) / nf’ (t) 

صفحه 33:
Schema 423 #اگر عضوی از این جمعیت انتخاب شود احتمال اينکه این عضو نماینده 5 باشد برابر است با: ‎An _us‏ زر اوه ‎ae jaa nfld_n fi, “Us, 1) los gi » 3?‏ 5 اعضاى 5 هم از اينرو مقدار مورد انتظار براى نمونه ‎jl aS BSB‏ 12 مرحله انتخاب مستقا حاصل ان وود تک زرنب ور 

صفحه 34:
Schema 423 #رابطه فوق به اين معناست که تعداد ‎Schema‏ های مورد انتظار در لحظه 1+ متناسب با مقدار میانگین (,1)5 بوده وبا مقدار ‎fitness‏ ‏سایر اعضا نسبت عکس دارد. #برای بدست آوردن رابطه فوق فقط اثر مرحله انتخاب نمونه ها در نظر گرفته شده است. با در نظر گرفتن اثر ‎Mutationg crossover‏ به رابطه زیر خواهیم رسید: jas) +p] sh ( Antste)= 4 ms ol1- p49 ‏زمر ما‎ 

صفحه 35:
Schema Theorem يعن | اماس اتيك مد اداه 1 سراف نطو ماود ان ما ‎oP‏ رای > ‎hoi)‏ © ‎PL) 1‏ ۶ ۶ als) = were ‏ولا‎ oP etree oP sche ‏امد فى‎ ‏ليا‎ = probably oP ‏ون موی ان سوت‎ امن منت تاه رالاس > يع * موه با تملمطه اد مسا > ۰ © fe) ‏ی‎ oP ceed (sou "**( ‏عم ونا‎ © de) = donner beter enim, Maint cet neal bio * ‏سد‎ Deaton ۱ ‏أن حاتي‎ ketaazes oP a echewa tees population ted iouzard tty rekave: Pies” 

صفحه 36:
مس بت )سس سس سس تست #یک ۹06۳08 اطلاعات مفید وامید بخش موجود در جمعیت را کد گاز آنجائیکه همواره رشته هائی که سازگارترند شانس بیشتری برای انتخاب شدن دارد. بتدریج مقالهای پیشتری به بهترین 001361882 ها اختصاص ‎eb‏ #عمل 0۳055076۲ باعث قطع رشته ها در نقاط تصادفی میشود. با اين وجود در صورتیکه اینکار باعث قطع ‎٩016102‏ نشده باشد آنرا نخواهد داددر حالت کلی 50116102 های با طول کوتاه کمتر تغییر #عمل 1011101018 در حالت کلی باعث تغییرات موثر در ‎Schema‏ ‏نمبگردد. 1111101102 -پببپبپبدبد--سش 

صفحه 37:
تفاوت /) با سایر روشهای جستجو ‎٩‏ بجی‌کد کردنپللمترها مه نها را کد میک ‎GA®‏ بجای‌جستجو برلیب کن قطه ب دنب ل‌جمعیتیاز ن قاط میگردد. ‎GA®‏ ب جای‌لستفادم از مشتقو یا سایر لطاهاتک مکی ستقیم ازلطلهات موجود در نتیجه بهرم ميكيرد. ‏ب جاوقوانینق طمیاز قوانیاحتمللولیت غيير لستفلده میکد. ‎ ‎ ‎ 

صفحه 38:
[)]D. E. Glover, Genetic Algorithm and Simulated Annealing, page 12-31, Morgan Kaufmann, Los Altos, CA, 1987. [r]Lissa W. Light and Peter G. Anderson, “Typewriter keyboards via simulated annealing”, AI Expert, September 1993. [r]Peter Klausler, www:visi,com/~pmk/evovied.html, September 2005. [JM. O. Wagner, B Yannou, S. Kehl, D. Feillet, and J. Eggers, Ergonomic Modeling and optimization of keyboard arrangement with an ant colony algorithm”, European Journal of Operation research, 2003. ‎S. Deshwall and K. Deb, Design of an Optimal Hindi Keyboard for‏ ظ[ه] ‎Convenient and Efficient Use. Technical Report on KanGAL Report No.‏ ‎Indian Institute of Technology, Kanpur, 2003.‏ ,2003005 ‎[\]D. A. Norman and D. E. Rumelhart, Cognitive Aspects of Skilled Typing, Springer-Verlag, New York, 1983. ‎(v]}. S. Goetti, A.W. Brugh, and B. A. Julstrom, “Arranging the Keyboard with a Permutaion-Coded Genetic Algorithm”, Proc. of the 2005 SCM Symposium on Applied Computing, Volume 2, pp. 947-951, 2005. ‎ ‎ ‎