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

صفحه 1:
الگوریتم های ژنتیک ۱ Ghiqv 0 Mitchell Ch. 9 

صفحه 2:
هري ی © الكوريتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است. »© اين روش در سال 197200) توسط مارا مجاول معرفی گردید © اين روشها با نام ‎ell 53 33 Cuohaticcary @kyriheos‏ میسوند. 

صفحه 3:
* یک 969) برای حل یک مسئله مجموعه بسیار بزرگی از راه حلهای ممکن را تولید میکند. ۶ هر یک از اين راه حلها با استفاده از یک " تابع تناسب" مورد ارزیابی قرار میگیرد. © آنگاه تعدادی از بهترین راه حلها باعث تولید راه حلهای جدیدی ميشوند. که اینکار باعث تکامل راه حلها میگردد. ۶ بدین ترتیب فضای جستجو در جهتی تکامل پیدا میکند که به راه حل مطلوب برسد ۶ در صورت انتخاب صحیح پارامترها» اين روش میتواند بسیار موثر عمل نماید. 

صفحه 4:
*: افضای فرضیه ۰ الگوریتم ژنتیک بجای جستجوی فرضیه های سس ‎speviic‏ و يا ‎to powplex‏ طامبنی فرضیه ها ی جدید را با تغییر و ترکیب متوالی اجزا بهترین فرضیه های موجود بدست میاورد. #در هرمرحله مجموعه ای از فرضیه ها که جمعیت ‎Gy yb 5! ai pte ould (population)‏ جایگزینی بخشی از جمعیت فعلی با فرزندانی که از بهترین فرضیه های موجود حاصل شده اند بدست میآید. 

صفحه 5:
الگوریتم های ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند میتواند بکار گرفته شود. © همجنين در مسایلی با فضای فرضیه پیچیده که تاثیر اجزا آن در فرضیه کلی ناشناخته باشند میتوان از ‎BO‏ برای جستجو استفاده نمود. * برای مه عم مولبسیار مورد استفاده قرار میگیرد. ۶ الگوریتم های ژنتیک را میتوان براحتی بصورت موازی اجرا نمود از اینرو میتوان کامپیوترهای ارزان قیمت تری را بصورت موازی مورد استفاده قرار داد. * امکان به نله اقتادن اين الگوریتم در مینیمم محلی کمتر از سایر روشهاست. از لحاظ محاسباتی پرهزینه هستند. © تضمینی برای رسیدن به جواب بهینه وجود ندارد. 9 

صفحه 6:
(urcelizaivg oP Beaatic Progroncvicgy * در سال ©©©)) شركت ‎lar‏ بود وهمة) جنوك 5). يى كامييوتر موازی با 000000 گره هر یک شامل کامپیوتر های ‎PSC, OSD‏ ‎OWT‏ برای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد. 

صفحه 7:
laa ‏اکاربر‎ :* ‎٩‏ کاربرد الگوریتم های ژنتیک بسیار زیاد میباشد ۱0۳۱72 ۳۳۱۲۹۲۹۱۲ ۲۳۲۹۲ ها موه ,۳770 او 7۳9۲ ‎pov,‏ ‎studies oP evvlutiva cod feoraicg, oer‏ ورد و 

صفحه 8:
ازير شاخه های ‎GO@‏ روش هاى 0209 به دو نوع مرتبط به هم ولی مجزا دسته بندی ميشوند: ‎(BBs) °‏ ا ا ‏در اين روش راه حل یک مسئله بصورت یک منود ۷ نشان داده میشود. ‎Gevwetc Proqgrawwiay (G@) 9 ‏اين روش به توليد دعص مدونوددح جم كه در زبانهاى برنامه نويسى مثل جا مورد استفاده هستند ميبردازد بدين ترتيب ميتوان برنامه هائی ساخت که قابل آجرا باشند, 

صفحه 9:
‎we he 4‏ الگوریتم های ژنتیک ‏۶ روش متداول پیاده سازی الگوریتم ژنتیک بدین ‏۴ مجموعه ای از فرضیه ها که ‎poputative‏ نامیده میشود تولید وبطور متناوب با فرضیه های جدیدی جایگزین میگردد. ‏* در هر بار تکرارتمامی فرضیه ها با استفاده از یک تابع تناسب یا ‎se 2255‏ 2 ارزیابی قرار داده میشوند. آنگاه تعدادی از بهترین فرضیه ها با استفاده از یک تابع احتمال انتخاب شده و جمعیت جدید را تشکیل میدهند. ‏۶ تعدادی از این فرضیه های انتخاب شده به همان صورت مورد استفاده واقع شده و مابقی با استفاده از اپراتورهای ژننیکی نظیر جر«ووم6 و مطاوی(برای تولید فرزندان بکار میروند. ‎ ‏تیب است که: ‎ ‎ 

صفحه 10:
BO cla yl 2 یک الگوریتم 960) دارای پارامترهای زیر است: ‎GO(Pitcess,Pittess_threshol,p,r,07)‏ * : حیب:)تابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد ۶ : لاماوسم!_وسیی:) مقدار آستانه که شرط پایان را معین مپکند ‎٩‏ : م تعداد فرضیه هائی که باید در جمعبت در نظر گرفته شوند ‏* :7 در صدی از جمعیت که در هر مرحله توسط الگوریتم سوه جایگزین میشوند ‏۴ : نرخ ول 

صفحه 11:
$2 |الكورتيم ؟ : سواهه| جمعیت را با تعداد مر فرضیه بطور تصادفی مقدار دهی اولیه کنید. * : طلس)برای هر فرضیه | در مر مقدار تابع ()عصس۴۳) را محاسبه نمائید. ۶ تا زمانیکه[()عع) بمم| < لاساوصما_ععم:) یک جمعیت جدید ایجاد کنید. 9 فرضیه ای که دارای بیشترین مقدار عجیی:() است را برگردانید. 

صفحه 12:
مراحل ایلجاد یک جمعیت جدید بصورت زیر است:ٍ نحوه ایجاد جمعیت جدید اسیاسستداد(سر فرضیه از میان 60 انتخاب و به,) اضافه کنید. احتمال انتخاب یک فرضیه:| از میان) عبارت است از: () سس 2 ۱ () سس = ‎(hi)‏ هر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است. اين احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد. : مود كبا استفاده از احتمال بدست آمده توسط رابطه فوق» تعداد()/ زوج فرضیه از میان 0) انتخاب و با استفاده از اپراتورجمرسیسب() دو فرزند از آنان ایجاد کنید. فرزندان را به ,) اضافه کنید. : ضف ()تعداد ب درصد از اعضا ,<) را با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنید. له > برای هر فرضیه | در <) مقدار تأبع عییی۸) را محاسبه کنید 

صفحه 13:
نمایش فرضیه ها در الگوریتم ژنتیک معمولا فرضیه ها بصورت رشته ای از بیت ها نشان داده میشوند تا اعمال اپراتورهای ژنتیکی برروی آنها ساده تر باشد. ۴ : سوروسع۳) به مقادیر یا راه حلهای واقعی گفته ميشود. © : هروه مقادیر انکد شده یا کروموزم ها گفته میشود که مورد استفاده 068) قرار میگیرند. * بايد راهى براى تبديل این دو نحوه نمایش به یکدیگر بدست آورده شود. ‎space ۶ (۲‏ موس سوه موس دمص 02 ‎(represecictio) > ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 14:
مثال: نمایش قوانین عطد ۳" © برای نمایش مقادیر یک ویژگی نظیر »امای() که دارای سه مقدار ,روج 0( سس است میتوان از رشته ای با طول ( بیت استفاده نمود ‎(DO -> Oudork = Gury‏ ‎OA0-> Outlook = Overcast * Ror‏ برای نمایش تر کیب ویژگی ها رشته بیت های هر یک را پشت سر هم قرار میدهیم: Outlook Wind 011 به همین کل یک قانون باه 4 را میتوان با پشت سر هم قرار|دادن بیت های قسمت فا شرط و نتیجه ایجاد نمود: ۱ TUVED Play Perats = Oe Outlook Wind ۱ . PlayTennis = bit string: 111100 111 10 0 or 

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

صفحه 16:
اپراتورهای ژنتیکی ورمییم : © اپراتور میسن با استفاده از دو رشته والد دو رشته فرزند بوجود میآورد. * برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی ميشود. ۶ انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود © stale-poiat arvssvvEr ° Diwo-pord vrossvver و ماو © * برای تعبین محل بیتهای کپی شونده از یک رشته به نام جر م0 اصت() استفاده میشود. 

صفحه 17:
Giade-port prossvver 9 یک نقطه تصادفی در طول رشته انتخاب ميشود. والدین در اين نقطه به دوقسمت میشوند. ‎٩‏ هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید. و0 (00000000000000:0 :عاص ۱ سوه qo 4 4 4 ‏[ه‎ » 98 

صفحه 18:
Crossover ‏روشهای دیگر‎ se Pwo-point 9 0 :«ه() مس سفن ۳ 51111 ‏ه22‎ 9 Poo | a OuPorw wossvver © ‏مس 0 )م0‎ ih bp] ۱۳۳۲ ۳۳۵۰۲ ۳۳۳[ 1۳۰۱۰ 15۲: 1 ۳ ۲ 7 ۲ ۱5۲ ۰ ۲ بیتها بصورت یکنواخت از والدین انتخاب میشوند Parcs 

صفحه 19:
اپراتورهای ژنتیکی بسد() : ۶ اپراتور مت برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغیبرات کوچکی در رشته اولیه بوقوع میپیوندد. * با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند. بولا جصییبمد از ‎Le‏ برس اسان سیقنود: ‎Card Obit‏ ‎Ppp pp‏ ۲ م[ ۱ ۵ ‎pbph bp‏ م ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 20:
2Crvsspver OR wutation * اين سوال ها سالها مطرح بوده است: کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟ © پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده: ‎٩‏ بستگی به صورت مسئله دارد در حالت کلی بهتر است از هر دو استفاده شود ۴ هر کدام نقش مخصوص خود را دارد * میتوان الگوریتمی داشت که فقط از بمنویس استفاده کند ولی الگوریتمی که فقط از جورمحورسی استفاده کند کار نخواهد کرد 

صفحه 21:
2Crvsspver OR wutation © مووود 0 خاصيتجستجوكر لنه و يا جرهه حاب دارد. ميتولندبا لنجام يرشهائىيزركبه محلهائىدربيزوا-دينرفته و نولحىجديدىرا کشفنماید. * دوك()خاصيتك سترشىئو يا جم#داوج دارد. ميتولند با لنجام ‎iS SI‏ صادفییه نولحی‌ک شف شده وسعتب بخشد. ۶ سموومناطلاعات والدین را ترکیب میکند درحالیکه وه ميتواند اطلاعات جدیدی اضافه نماید. * برای رسیدن به یک پاسخ بهینه یک خوش شانسی در نو لازم است. 

صفحه 22:
۶ تابع :۳ معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد: * : نانمس در اين نوع مسایل تابع تناسب معمولا برابر است با دقت قانون در دسته بندی مثالهای آموزشی. 

صفحه 23:
؟؟ انتخاب فرضیه ها Rouete Okeel selevioa * در روش معرفی شده در الگوریتم ساده ‎Leia! (BOD‏ انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت ج027 آن به ‎P‏ بقيه اعضا دارد. اين روش ‎Roulette Dherl‏ مرشرساسنامیده ميشود. 9 2 ()عسص< ‎Fcess() = 4 (hi) = Pitcess (ht) / Lj Pitcess (hi)‏ ‎Pieye(O) = ©‏ * روشهای دیگر: tournnved selevtioan © rok seleviva © 

صفحه 24:
۶ آنحوه جستجو در فضای فرضیه © روش جستجوى 0009 با روشهاى ديكر مثل شبكه های عصبی تفاوت دارد: »در شبكه عصبى روش لجدججك جلك (1) بصورت هموار از فرضيه اى به فرضيه مشابه ديكرى حركت ميكند در حاليكه 1(00) ممكن است بصورت ناكهانى فرضيه والد را با فرزندی جایگزین نماید که تفاوت اساسى با والد آن داشته باشد.از اينرو احتمال كير افتادن 000) در مینیمم محلی کاهش مى يابد. »بااين وجود 09) با مشكل ديكرى روبروست كه يج:لسصد ناميده ميشود. 

صفحه 25:
‎$s‏ بسن ‏© بدلسوج يديدم لى لستكه در لن عضووكه سازگاری بسياربيشترىاز بقيه لفراد جمعيتدارد بطور مرتبتوليد نسل‌کرده و با تولید اعضایمشابه درصد عمدم لیاز جمعیت را لشغالمیکند. ‏۶ اینکار باعث کاهش پراکندگی جمعیت شده و سرعت 869) را ‏کم میکند. ام ‎F(X)‏ 

صفحه 26:
‎oly‏ حل رفع مشکل بسن ‏@ استفاده از ‎gl: roohiag‏ انتخاب نمونه ها: با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند مقدار اين ‎ ‏برتری نشان داده نخواهد شد. ‎lie Pittess shorty: °‏ عویب:) یک عضودر صورتیکه اعضا مشابهی در جمعیت وجود داشته باشند کاهش می يیابد. 

صفحه 27:
:؛ چرا 06 کار میکند؟ ‎٩‏ سئوالی كه ممکن است برای تازه واردین به روشهای ژنتیکی ایجاد شود این است که آیا این روش واقعا میتواند کار مفیدی انجام دهد؟ 

صفحه 28:
ارزيابى جمعيت و قضيه ودوجوام5) © آيا ميتوان تكامل در جمعيت در طى زمان را بصورت رياضى مدل نمود؟ * قضیه وریبان) میتواند مشخصه پدیده تکامل در 269) را بیان نماید. * يك وجاك 5) مجموعه اى از رشته بيت ها را توصيف میکند.یک مسسطل9) هر رشته ای از 0 واو* است. مثل 400*00 كه * حالت ‎pare‏ لول است. یک رشته بیت را میتوان نماینده هر یک از وهای متفاوتی دانست كه با آن تطابق دارند. مثلا 000000 را ميتوان نماينده 62 © ‎IDO, *OOGuils aids Gohewa‏ * : وغيره هه 

صفحه 29:
Gvhewd ‏اقضیه‎ :: ‎٩‏ قضیه ورمس!3) بیان میکند که چگونه یک مس() در طول زمان در جمعیت تکامل پیدا خواهد کرد. ‏9 فرض کنید که در لحظه , تعداد نمونه هائی که نماینده یک ‎Jie Soke‏ = هستند برابر با (ابج)س باشد. اين قضيه مقدار مورد انتظار (2,۲0) را مشخص میکند. ‏© قبلا ديديم كه احتمال انتخاب یک فرضیه برابر بود با: ‏() عحص ,2 / ‎@(k) = Pittess (hk)‏ * اين مقدار احتمال را میتوان بصورت زیر نیز نشان داد: ‎lk) =F (R)/ ۰۳ 0) ‏مقدار متوسط *] براى تمامى فرضيه ها 

صفحه 30:
* اگر عضوی از این جمعیت انتخاب شود احتمال ايینکه این عضو ی بقل ‎pred= 5 HB‏ ‎pad nid” ۱‏ | 9 که در آن مقدار (ج)ب برابر است با مقدار میانگین عیسم,۳ اعضاى جح ‎SA‏ ‏تك ووه 2050 ‎> ‏از اینرو مقدار مورد انتظار برای نمونه هائی از ع که از‎ ٩ ‏مرحله انتخاب مستقل حاصل خواهند شد برایر است با:‎ ‏وىم لكلا رم يمير ‎fo‏ 

صفحه 31:
Gvhewd ‏اقضیه‎ :: * رابطه فوق به این معناست که تعداد برمم3) های مورد انتظار در لحظه 0+ متناسب با مقدار میانگین (ا,ج)ب بوده و با مقدار وص ساير اعضا نسبت عكس دارد. * براى بدست آوردن رابطه فوق فقط اثر مرحله انتخاب نمونه ها در نظر كرفته شده است. با در نظر كرفتن اثر مدن( به رابطه زير خواهيم رسيد: 3 ۳۵ زم |4۵ ور 1 ‎t+1)]}>259 nis 9‏ يمع ‎fe‏ 

صفحه 32:
Gckews Thevrew و و سنا کت ( ی 218 )0+ ‎Boles‏ ‎“A 07 ar‏ 2 اعمد د مسليسو وه سه لاعس امد ریت و | اف من خن مسو موجه < زيم * 8 = wera: Proewy of testowwer oP ‏عتما فى سامت‎ . - ‏تطعا “أن بام ماسر‎ pot orion penton oa probably oP exten ‏سین‎ 9 ۳ © A») 2 ‏ماس‎ oP dePoed (ava “*") bite ta ها ها سای تسه سل موس مسق < ‎de)‏ © ‎etter Dercrotery‏ © © De expected exxuber oP ketrery oP a pvheuwa ta he pop kiiva leds wuvard te: releave Piceoe” 6ه 

صفحه 33:
خلاصه ‎٩‏ یک «رمسبلی3) اطلاعات مفید و امید بخش موجود در جمعیت را کد ‏* از ‎ ‏جائيكه همواره رشته هائي که سازگارترند شانس بیشتری برای ‏انتخاب شدن دارند» بتدریج مثالهای بیشتری به بهترین بطلیظ) ها اختصاص می يابند. ‎٩‏ عمل موس باعث قطع رشته ها در نقاط تصادفی میشود. با اين وجود در صورتیکه اینکار باعث ‎Gcbkeuwa ahi‏ نشده باشد آنرا تغییر نخواهد داد.در حالت ‎5b b Gls Grbkewa GS‏ کوتاه کمتر نغییر ‎ed ‏& عمل هنیس در حالت کلی باعث تغییرات موثر در ‎Grkewa‏ ‎ ‏دد. ‎(coled butday blrks) are propasied‏ ی راومه ,سا ‎yrueraiva to yeceraiza by yiviegy expooruidly tocreustry supe to ter‏ ‎observed best‏ ‎ ‎ ‎ 

صفحه 34:
55 تفاوت 609 با سایر روشهای جستجو ۶ بجاوکد کردن‌پ ارلمترها مجموعه آنها را کد میکند ® ب جای‌جستجو برلییکن قطه ب دنب لجمعیتی‌از نقاط میگردد. 9۶ ب جایلستفاده از مشتقو یا سایر لطلاعاتک مکی مستقیما از لطلاعاتموجود در نتیجه بسهرم میگیرد. ‎٩‏ )بجاو وانینقطعیاز قولنین‌لحتما له رلوتغییر لستفادم میکند. 

صفحه 35:
مثالی از کاربرد الگوریتم ژنتیک بهینه‌سازی چینش حروف ونس بر روی صفحه کلید با ستفاده از الگوریتم‌های ‏ ‎Sais j‏ 

صفحه 36:
‎٩‏ بدست آوردن چینش بهینه حروف فارسی بر روی صفحه‌کلید در درازمدت برای کسانی که با تایپ کردن متون فارسی درگیر هستند, بسیار مفید خواهد بود. ‏© یک الگوریتم تکاملی می‌تواند با توجه به یک تابع تناسب که میزان راحتی تایپ كردن متون فارسی را برای یک چینش ارائه می‌دهد, در فضای چینش‌های حروف فارسی بر روی صفحه‌کلید جستجو کرده و چینش بهینه را بدست آورد. 

صفحه 37:
چینش کنونی حروف فارسی بر روی صفحه‌کلید i] 2] ee] re] radu ni 808 م0000 ‎sf sf ele} fel el ele). [adjenfoag 7] 0] 9]‏ اه ام ام اه allel ol vial ‏تاه‎ ooo ‏الال لكف‎ : اه 5 ray |. 

صفحه 38:
* در این مساله هندسه صفحه کلید ثابت است و ما می‌خواهیم که تعداد ‎Fe‏ ‏نشانه که متشکل از ۳۲ حرف الفبای فارسی بعلاوه حرف همزه ۶" است را بر روی سه ردی صفحه کلید که به ترتیب دارای ۱۱,۱۲,و ۳ كليد هستند, قرار دهیم. هدف این مساله بدست آوردن چینشی از این نشانه‌ها بر روی این کلیدها است, به طوری که این چینش طوری باشد که کار بر هنگام استفاده از صفحه کلید برای تایپ حرروف فارسی, احساس راحتی بیشتری نسبت به کار با بقیه چینش‌ها داشته باشد. 

صفحه 39:
بای حل مساله از یک الگوریتم ژنتیک استفاده شده است. تابع تناسب موجود در این الگوریتم ژنتیک, میزان راحتی یا سختی استفاده از یک چینش را محاسبه می‌کند. در هر نسل, عملگر‌های ژنتیکی بر روی جمعیت موجود که چینش‌های مختلفی از حروف فارسی بر روی صفحه کلید هستند, اعمال می‌شوند و جامعه به سمتی سوق داده می‌شود که مقدار تابع تناسب به ازای اعضای آن به کمینه مقدار خود بر‌سند. مییزان تناسب هم عضو از جامعه که در واقع یک چینش حروف فارسی بر روی صفحهکلید هستند, با اعمال تابع تناسب بر متنی که از مطالب چند سایت خبری فارسی زبان تهیه شده است, به دست میاید. 

صفحه 40:
اعضای جمعیت جایگشت‌های مختلف حروف فارسی روی صفحه کلید هستند. هر عضو جمعیت را می‌توان به صورت بر‌داری از حیوف فارسی در نظر گرفت که هر انديس آن متناظر با یک کلید از صفحه کلید است. مثلاً هر برردار با طول ۳۳ که شامل حرروف فارسی بعلاوم حرف همزه "۶" باشد را میتوان به عنوان یک کروموزوم (یک عضو از جمعیت ) در نظر گرفت که حرف اام از این بمرداره متناظر با کلیدی از صفحه کلید است که برچسب شماره ابر روی آن زده شده است. 21314 | 5 [ 6 |... | 33[ ‏يي‎ 11 1 ty eo ] ‏ف‌اق آاث ام أش‎ wey [gs ae] as] xe] 27] 0] 29] 20] 28132] 29] تعداد چینش‌های مختلف ۳۳۱ 

صفحه 41:
‎ee‏ تابع تناسب ‏* تعیین راحتی و سختی کار کردن با چینش حروف بر روی صفحه‌کلید یک مساله پیچیده ارگونومیک است. ۶ نورمن و رومل‌هارت چهار هدف را برای طراحی کارای یک صفحه‌کلید ارائه کرده‌اند: برابرى كارى كه دو دست انجام مىدهند؛ بيشترين تايب حروف به صورت متناوب با دو دست؛ ‎OLS‏ تکرار تایپ دو حرف متوالی با یک انگشت؛ و + بیشترین تایپ حروف بر روی کلیدهای پایه‌ای (کلیدهای ردیف وسط). 

صفحه 42:
‎ss:‏ تابع تناسب ‏* . برای دو هدف اول می‌توان فاکتور اندازه‌گیری زیر را معرفی‌کرد: ‏© ب0: هزینه مربوط به لستفادم از یبکدستبرلیتایپک ردن‌دو حرفپشتسر هم ‏© برای هدف سوم, فاکتور اندازه‌گیری زیر معرفی می‌شود: ‏۴ب هزینه مربوط به لستفادم از یسکانگشتب رلیتایپکردن‌دو حرفپشت سر هم. ‏۴ بر .(): هزینه مربوط بسه تایپک ردنیکحرفبا تسوجه بسه موقعیتآن‌حرف بر رووصفحهک لید. ‏لعا ۳ ]1 اساسا( لا ‏دسا ‎aes Pte]‏ هه هرس هرهس رس مزا ‎]515 [20120101 de | [so] 20] so] 25 [so] 25] so] es] es] co JET] 8 5 5 3 ‎ 

صفحه 43:
تابع تناسب ۶ تابع تناسب برای هر کروموزوم از مجموع این سه فاکتور برای تمامی حروفی که در متن مورد استفاده برای آزمایش وجود دارند, بدست می‌آید: رلاسمو درایلیم6 2 2 چباهودقومصاز۳ اع لالع () مجموعه تمامیک لماتموجود در متن‌مورد لستفاده برلى آ زمایش‌لسک ‎ali AS wy, ۰‏ از مجموعه () است؛ © احرف ام از کلمه زير است؛ 

صفحه 44:
* در اینجا تنها از عملگر جهش استفاده شده است. ‎٩‏ دلیل عدم استفاده از عملگر دورگه اين است که ساختار اعضای جمعیت طوری است که ترکیب کردن دو کروموزوم والد هزينة زمانی بالایی دارد. ‎٩‏ عملگر جهش را به دو صورت برای اعضای مختلف جامعه به کار می‌بريم. در این مساله یک جامعه نخبگان انتخاب می‌کنیم که اعضای آن ‎a%‏ ‏تراز اول جمعیت از دید تابع تناسب را تشکیل می‌دهند. ‏* عملگر جهش برای هر عضو از جامعة نخبگان, تتها محتویات چهار زوج ژن را به صورت تصادفی جابه‌جا می‌کند. در حالیکه برای افراد عادی جامعه اين تعداد به ) جابه‌جایی افزايش می‌یابد. 

صفحه 45:
:+ اکارایی * الگوریتم ژنتیک با پارامترهای زیر اجرا کردیم: * تعداد اعضای جمعیت ۱۰۰ کروموزوم که در نسل اول به صورت تصادفی تولید شدهاند؛ * 04 درصد تشکیلدهنده جامعه نخبگان است, ۱0 کل جمعیت ؛ © تعداد اعضایی که به صورت مستقیم و بدون اينکه عمگرهای ژنتیکی بر روى آن اعمال شود, به نسل بعدی ميرروند, ۳ عضو؛ © وتعداد كل نسلها ‎0*٠‏ نسل. 

صفحه 46:
8 06 ۱ - = - هه = - شش شام لت شش امن ‎us feet‏ ao 1 2 ae ae ‏ا‎ ‎ao © ® @> aap cad aes a aD aD ea generationnnber نمودارهای تناسب اعضبای جامعه در طی نسلهای مختلف. منحنیهای نشان داده شده به تررتیب از ‎go‏ بالا به پایین, متوسط مقادیر تناسب همه اعضای جامعه, متوسط مقادیر تناسب جامعه نخبكان, و بهترین تناسب هستند. 

صفحه 47:
* بهترین چینشی که در نهایت این الگوریتم ژنتیک بر‌ای حروف فارسی ارائه داد, هزینهاش با توجه به تابع تناسب, ۸۱۵/۰ هزینه چینش کنونی حروف فارسی است . we 

صفحه 48:
: امدلهای تکامل # در سیستمهای طبیعی هر موجود زنده در طول زندگی خود یاد میگیرد که با شرانط سازگاری نماید. به همین ترتیب نسل های مختلف یک نمونه در طول زمان سازگاری های مختلفی را © سوال: رابطه بين يادكيرى يك موجود در طول زندكى شخصى و يادكيرى نسل های یک نمونه در طول زمان جيست؟ 

صفحه 49:
ارو مورا * سور دلنشمند قرن‌نوزدهم فرضیه لیارلنه کردم که طبق‌آن‌ت جر بیانتیکموجود زندم در ترکیب‌ژنتیکی فرزندان‌آن‌تاثیر میگارد. * برای مثال موجودی که یاد گرفته از غذای سمی پرهیز کند اين ویژگی را بصورت ژنتیکی به فرزندان خود منتقل مینماید تا آنها دیگر مجبور به یادگیری اين پدیده نباشند. ‎٩‏ اما شواهد تجربی این نظر را تائید نمیکنند: ‏یعنی تجربیات فردی هیچ تأثیری در ترکیب ژنتیکی فرزندان ندارد. 

صفحه 50:
اك نظريه ديكرى وجود دارد كه تاثير يادكيرى را بر تكامل توضيح میدهد. اين نظریه که اثر »زررللب() نامیده میشود بر مبتای مشاهدات زیر استوار است: * اگر موجودی از طرف محیط متغیری تحت فشار قرار گرفته باشدء افرادی که توانائی یادگیری نحوه برخورد با شرایط را داشته باشند شانس بیشتری برای بقا دارند. 9 موجوداتی که تحت شرایط جدید باقی میمانند جمعیتی با توانائی یادگیری را تشکیل میدهند که فرایندهای تکاملی در آنها سریعتر رخ میدهد و باعث میشود تا نسلی بوجود بیاید که نیازی به یادگیری مواجهه با شرایط جدید را نداشته باشند. 

صفحه 51:
:: اجرای موازی الگوریتم های ژنتیک * الگورینم های ژنتیک از قابلیت خوبی برای پیاده سازی بصورت موازی برخوردارد هستند. »در يك روش پیاده سازی موازی» جمعیت به گروههای گوچکاری انم سبط نقسیم شقور هرگام خر یک گرم محاسباتی مورد پردازش قرار میگيرند. * در هر كره يك الكوريتم استاندارد 0008 بر روی سس اجرا مود © انتقال بين كره ها از طريق يديده ماد صورت میپذیرد. 

صفحه 52:
از Euolviery Oeurd Detworks ‎lL GO‏ تکامل جنبه های مختلف (60() استفاده زیادی بعمل آمده است.از جمله : وزنهاه ساختارو تابع یادگیری. ‏استفاده از 969) برای یادگیری وزنهای یک شبکه عصبی میتواند بسیار سریعتر از روش استاندارد مومسم ‎back‏ عمل نماید. ‏استفاده از 068) برای یادگیری ساختار شبکه عصبی مشکلتر میباشد. برای شبکه های کوچک با استفاده از یک ماتریس مشخص میشود که چه نرونی به چه نرونهای دیگری متصل است.آنگاه اين ماتريس به زن های الگوریتم ژنتیک تبدیل و ترکیبات مختلف آن بررسی میگردد. برای بدست آوردن تابع یادگیری یک شبکه عصبی ‎oly‏ حلهانی نظیر استفاده از ‎ay ge (BOP‏ استفاده قرار گرفته اما عموما این روشها بسیار کند عمل کرده اند. 

صفحه 53:
مراجع ,مج یمه ,100 سجن ملسم( تلم لب سلجي |( مق ما6 .© .]0[ ‎bie Ohm, O, (OOP.‏ [E] bows ©. Licht ond Peer ©. Derkrova, “Dypeurter hepboards ‏لسسجمد دب‎ acai", BT Onrert, Oxpecrber (O99. [0] Peer Khater, wane ‏ماس اه‎ 0 3 606 ]6[ ©. 0. Danger, © Verner, ©. Koh, D. ‏رل لمیر‎ Oxpere, Orypcennay Dirdeh ase! ‏موی ارجا ان مجهي‎ wah os ‏فى‎ okey okra", Durer dover oP ‏اس مهن‎ ۰ [91 ©. ©. ‏سامت‎ rnd (. Deb, Dror of ‏جورت دن‎ Link (Keyboard ‏اجه من‎ Ofer Dor. Pechowrd Report ox KerkDOL Report Do. CODIOOS, “ec ‏حك فحص‎ ‏روتانس‎ Kerr, C009. [2] ©. ©. Oorwaa aed O. ©. Ruwebvat, Onyuae Dopeots of Chiled Typrny, Oprcer-Oerkes, Onw York, (B69, [P]V. ©. Corts, 0.0. Orinds, onl ©. 0. dubsroen, “Drraenten he Cevbrard uth a Peruana Orded Oevete Okprih”, Prov. oP hee QDDS GOD Oyrrprmnscr ox Dephed Orxor ani, ‏ساره‎ 9, 9۵۵60, 00 هه 

صفحه 54:
Geveto Progrecvevicgy ۶ «0) تکنیکی‌استک» کامپیوترها را قادر ميسازد تا به حلمسائل بپردازند بدون‌آنکه بطور صریح براءآن‌برنامه ریزی‌شده بساشند. * 0 روشی‌از الگرریتمهایتکاملی‌استکه در آن‌هو عضو جمعیتیک برنامه کامپیوتریاستِ اذ بودامة:ها اغلب بتوسظ يك ,زر كت تمایق انم قنقهو: بای برنامه بزابن است با جوم کردن درخت. + F = sin(x) + sqrt(x*2 + y) Sin qrt or 

صفحه 55:
نمایش برنامه ها # برای استفاده از 0) در یک زمینه خاصء © مییایست توابع پایه ای که در آن زمینه مورد نیاز هستند نظیر ,2:0 ‎et‏ ,- ,+ ,امك ,جوت توسط کاربر تعریف شوند * همچنین ترمینالها نظیر متغیرها و وابت نیز باید مشخص شوند ۶ آنگاه الگوریتم 96) در فضای بسیار بزرگ برنامه هائی که توسط این مقادیر اولیه قابل بیان هستند یک عمل جستجوی تکاملی را انجام خوهد داد. 

صفحه 56:
GO cl saessvver ‏يراتور‎ © ايراتور : جر دمج شاخه هائى از يك درخت والد با شاخه هائى از درخت والد دیگر بطور تصادفی عوض ميشوثد ‎gee +‏ ‎Sin‏ 7 :2 فرزندان والدین 

صفحه 57:
:: امثال * در کتاب مثالی از میم) مطرح شده که در آن الگوریتمی یاد گرفته میشود که بتواند بلوک ها را در یک ستون روی هم بجيند © هدف مسئله اين است كه بلوىك ها طورى روى هم جيده شوند كه کلمه امجبوری را بسازند 2 آبه آم آم< 

صفحه 58:
۶ محدودیت: در هر مرحله فقط میتوان یک بلوک را جابجا نمود. در نتيجه تنها حرکت های ممکن عبارتند از: © بلوک آخر ستون را میتوان روی میز قرار داد و یا اینکه * یک بلوک را از میز به انتهای ستون منتقل نمود. ۶ توابع اولیه: * : (ص< مسسج) (20)نام بلوک موجود در انتهای ستون را بر میگرداند ۴ ) برای حالتی که بلوکی وجود ندارد( ‎(top vorrent block) ۴‏ ۳0 نام آخرین‌ی لوکیرا که هراد با بلوک‌های زیرینش‌ترتیبصحیح مورد نظر را دارنده برمیگرداند ‎OO (cen evessey) ©‏ 4 بلوکی‌که باید در بادلق0) قرار گیرد تا ‎es univers‏ 

صفحه 59:
* سار توابع اولیه: ‎Hock x to stack (DG x) *‏ ردرواكر بلوك « روى ميزباشد اين ايراتور آنرا به بالاى ستون منتقل ميكند. درغير اينصورت مقدار “)برميكردائد. ‎block x to table (DT x) &‏ جردوواكر بلوك ع جائى روى ستون باشد اين ايراتور بلوك بالاى ستون را به ميز منتقل ميكند. درغير اينصورت مقدار <)برميكرداند. ‏۴ (ير» ©2ا) نر د ,دخا صم ار ‏۴ 600 خاه مان با اس ‎OO( xy) do x voll expressivd pip ine © ‏هه 

صفحه 60:
مقدار تابع عصب:۳ ۶ در اين آزمایش تعداد 60 مثال که هر یک در برگیرنده آرایش اولیه متفاوتی برای بلوک ها بودند تدارک دیده شده بود. © تابع وضع یک برنامه برابر است با تعداد مثالهائی كه برنامه قادر به حل آن است. © برنامه با جمعيت اوليه اى برابر با0000© برنامه تصادفى شروع بكار نموده و يس از توليد 000 نسل قادر ميشود تا برنامه اى بيدا نمايد كه تمامى 100 مثال را حل نماید: ‎(EQ (OO (OT CG)MOT CG)) (OO ۵۵ 00‏ ( ((020) 

صفحه 61:
مثال : طراحی فیلتر صورت مسئله: برنامه ای که یک مدار ساده اولیه رابه مدار پیچیده مورد نیاز تبدیل نماید. ۶ توابع اولیه: * تابعی برای اضافه کردن قطعات و سیم بندی های مدار © تابعی برای حذف کردن قطعات و سیم بندی های مدار © تايع جع شبیه سازی مدار بدست آمده توسط نرم افزار 90۳1068) برآى مشخص نمودن ميزان تطبيق آن با طرح مورد نظر. خطاى مداربراى 000 فركانس مختلف مورد بررسى قرار ميكرفت. © جمعيت اوليه 006۳00000 : « نرخ 09 : سروس مدرصد *نرخ) :وض درصد 

صفحه 62:
: امثال : طراحی فیلتر ‎٩‏ سیستم برروی یک کامپیوتر موازی با 06 گره مورد آزمایش قرار گرفت. ‏9 برای نسل اولیه ای که بصورت تصادفی ایجاد شدند در 0 مواقع حتی امکان شبیه سازی وجود نداشت. ‏© اين نرخ بتدريج كاهش يافته و يس از توليد 972 نسل مداری حاصل شد كه با مشخصات مورد نظر صدق ميكرد. ‏در اغلب موارد کارائی الگوریتم 06) بستگی به نحوه نمایش و همچنین تابع حسب:۳ دارد. ‎ ‎ ‎ ‎ 

الگوریتم های ژنتیک Instructor : Saeed Shiry Mitchell Ch. 9 1 الگوریتم ژنتیک الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است. این روش در سال 1970توسط John Hollandمعرفی گردید این روشها با نام Evolutionary Algorithmsنیز خوانده میشوند. 2 ایده کلی ‏ ‏ ‏ ‏ ‏ 3 یک GAبرای حل یک مسئله مجموعه بسیار بزرگی از راه حلهJای ممکن را تولید میکند. هر یک از این راه حلهJا با استفاده از یک “ تابع تناسب” مورد ارزیابی قرار میگیرد. آنگاه تعدادی از بهترین راه حلها باعث تولید راه حلهای جدیدی میشوند. که اینکار باعث تکامJل راه حلها میگردد. بدین ترتیب فضای جستجو در جهJتی تکامل پیدا میکند که به راه حل مطلوب برسد در صورت انتخاب صحیح پارامترها ،این روش میتواند بسیار موثر عمل نماید. فضای فرضیه الگوریتم ژنتیک بجای Jجستجوی فرضیه های general-to specificو یا simple to complexفرضیه ها ی جدید را با تغییر و ترکیب متوالی اجزا بهترین فرضیه های موجود بدست میاورد. در هرمرحله مجموعه ای از فرضیه ها که جمعیت ( )populationنامیده میشوند از طریق جایگزینی بخشی از جمعیت فعلی با فرزندانی که از بهترین فرضیه های موجود حاصل شده اند بدست میآید. 4 ویژگیها الگوریتم های ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند میتواند بکار گرفته شود. همچنین در مJسایلی با فضای فرضیه پیچیده که تاثیر اجزا آن در فرضیه کلی ناشناخته باشند میتوان از GAبرای جستجو استفاده نمود. برای discrete optimizationبسیار مورد استفاده قرار میگیرد. الگوریتم های ژنتیک را میتوان براحتی بصورت موازی اجرا نمود از اینرو میتوان کامپیوترهای ارزان قیمت تری را بصورت موازی مورد استفاده قرار داد. امکان به تله افتادن این الگوریتم در مینیمم محلی کمتر از سایر روشهJاست. از لحاظ محاسباتی پرهزینه هستند. تضمJینی برای رسیدن به جواب بهینه وجود ندارد. 5 Parallelization of Genetic Programming ‏ 6 در سال 1999شرکت .Genetic Programming Incیک کامپیوتر موازی با 1000گره هر یک شامل کامپیوتر های P2, 350 MHZبرای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد. کاربر دها کاربرد الگوریتم های ژنتیک بسیار زیاد میباشد          optimization, automatic programming, machine learning, economics, operations research, ecology, studies of evolution and learning, and social systems 7 زیر شاخه های EA روش های EAبه دو نوع مرتبط به هم ولی مجزا دسته بندی میشوند: ‏Genetic Algorithms (GAs)  در این روش راه حل یک مسئله بصورت یک bit stringنشان داده میشود. ‏Genetic Programming (GP)  این روش به تولید expression treesکه در زبانهای برنامه نویسی مثل lispمورد استفاده هستند میپردازد بدین ترتیب میتوان برنامه هائی ساخت که قابل اجرا باشند. 8 الگوریتم های ژنتیک ‏ ‏ ‏ ‏ 9 روش متداول پیاده سازی الگوریتم ژنتیک بدین ترتیب است Jکه: مJجموعه ای از فرضیه ها که populationنامیده میشود تولید وبطور متناوب با فرضیه های جدیدی جایگزین میگردد. در هر بار تکرارتمامی فرضیه ها با استفاده از یک تابع تناسب یا Fitnessمورد ارزیابی قرار داده میشوند .آنگاه تعدادی از بهJترین فرضیه ها با استفاده از یک تابع احتمال انتخاب شده و جمJعیت جدید را تشکیل میدهند. تعJدادی از این فرضیه های انتخاب شده به همان صورت مورد استفاده واقع شده و مابقی با استفاده از اپراتورهای ژنتیکی نظیر Crossover و Mutationبرای تولید فرزندان بکار مJیروند. پارامترهای GA یک الگوریتم GAدارای پارامترهای زیر است: )GA(Fitness,Fitness_threshold,p,r,m ‏Fitness : تابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت مJیدهد Fitness_threshold : مJقدار آستانه کJه شرط پایان را معین میکند p : تعداد فرضیه هائی که باید در جمJعیت Jدر نظر گرفته شوند r: در صدی از جمJعیت که در هر مرحله توسط الگوریتم crossover جایگزین میشوند m: نرخ mutation 10 الگورتیم ‏Initialize : جمعیت را با تعداد pفرضیه بطور تصادفی مقدار دهی اولیه کنید. ‏Evaluate : برای هر فرضیه hدر pمقدار تابع )Fitness(h را محاسبه نمائید. تا زمانیکه[) Fitness_threshold < ]maxh Fitness(hیک جمعیت جدید ایجاد کنید. فرضیه ای که دارای بیشترین مقدار Fitnessاست را برگردانید. 11 نحوه ایجاد جمعیت جدید مراحل ایجاد یک جمعیت جدید بصورت زیر است: ‏select : تعداد( p)r-1فرضیه از میان Pانتخاب و به Psاضافه کنید .احتمال انتخاب یک فرضیه hiاز میان Pعبارت است از: )P(hi) = Fitness (hi) / Σj Fitness (hj هر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است .این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد. ‏ ‏ ‏ ‏ 12 ‏Crossover :با استفاده از احتمال بدست آمده توسط رابطه فوق ،تعداد( 2/)rpزوج فرضیه از میان Pانتخاب و با استفاده از اپراتور Crossoverدو فرزند از آنان ایجاد کنید .فرزندان را به Psاضافه کنید. ‏Mutate :تعداد mدرصد از اعضا Psرا با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنید ‏P Ps :Update برای هر فرضیه hدر Pمقدار تابع Fitnessرا محاسبه کنید نمایش فرضیه ها در الگوریتم ژنتیک معموال فرضیه ها بصورت رشته ای از بیت ها نشان داده میشوند تا اعمال اپراتورهای ژنتیکی برروی آنها ساده تر باشد. ‏ ‏ ‏ Phenotype :به مقادیر یا راه حلهای واقعی گفته میشود. ‏Genotype :به مقادیر انکد شده یا کروموزم ها گفته میشود که مورد استفاده GAقرار میگیرند. باید راهی برای تبدیل این دو نحوه نمایش به یکدیگر بدست آورده شود. ‏Genotype space = {0,1}L 100100 01 10010010 ‏Encoding )(representation 010001001 011101001 13 ‏Decoding )(inverse representation ‏Phenotype space مثال :نمایش قوانین If-then rules ‏ برای نمایش مقادیر یک ویژگی نظیر Outlookکه دارای سه مقدار Sunny, Overcast ,Rainاست میتوان از رشته ای با طول 3بیت استفاده نمود 100 -> Outlook = Sunny 011-> Outlook = Overcast  Rain برای نمایش تر کیب ویژگی ها رشته بیت های هر یک را پشت سر هم قرار میدهیم: ‏Outlook ‏Wind 011 10 به همین ترتیب کل یک قانون if- thenرا میتوان با پشت سر هم قرار دادن بیت های قسمت های شرط و نتیجه ایجاد نمود: ‏IF Wind = Strong THEN PlayTennis = No ‏ bit string: 111100 14 ‏Outlook ‏PlayTennis ‏Wind 10 111 0 نمایش فرضیه ها :مالحظات ممکن است ترکیب بعضی از بیت ها منجر به فرضیه های بی معنی گردد .برای پرهیز از چنین وضعیتی: میتوان از روش انکدینگ دیگری استفاده نمود. اپراتورهای ژنتیکی را طوری تعیین نمود که چنین حالتهائی را حذف نمایند میتوان به این فرضیه ها مقدار fitnessخیلی کمی نسبت داد. 15 اپراتورهای ژنتیکی : Crossover ‏ ‏ ‏ اپراتور Crossoverبا استفاده از دو رشته والد دو رشته فرزند بوجود میآورد. برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی مJیشود. انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهJای مJختلف انجام میشود ‏single-point crossover ‏Two-point crossover ‏Uniform crossover ‏ 16 ‏ ‏ ‏ برای تعیین محل بیتهای کپی شونده از یک رشته به نام Crossover Maskاستفاده میشود. Single-point crossover یک نقطه تصادفی در طول رشته انتخاب میشود. والدین در این نقطه به دوقسمJت میشوند. هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید. ‏Children 17 ‏Crossover Mask: 11111000000 ‏Parents 1 0 1 1 1 10 10 10 1 0 1 1 1 000 100 1 0 0 0 0 000 100 1 0 0 0 0 10 10 10 Crossover روشهای دیگر Two-point crossover  Parents Crossover Mask: 00111110000 Children 0 0 001 01 1 00 0 1 0 100 0 0 011 01 1 00 0 00 100 0 0 011 00 0 1 01 0 0 1000 0 0 001 00 0 1 01 0 1 1000 Uniform crossover Parents Crossover Mask: 10011010011  Children 1 1 1 1 00001 00 1 00 1 0001 0 00 000 1 001 1 0 1 0 01 1 1 0 0 1 0 1 1 0 18 بیتها بصورت یکنواخت از والدین انتخاب میشوند اپراتورهای ژنتیکی : Mutation ‏ ‏ ‏ اپراتور mutationبرای بوجود آوردن فرزند فقط از یک والد استفاده میکند .اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد. با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغJییر پیدا میکند. مJعموال mutationبعد از انجام crossoverاعمال میشود. ‏Child 1 0 1 1 1 0 1 001 00 19 ‏Parent 1 0 1 1 1 0001 00 ?Crossover OR mutation این سوال ها سالها مطرح بوده است: کدامیک بهتر است؟ کدامیک الزم است؟ کدامیک اصلی است؟ پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده: ‏ ‏ ‏ ‏ 20 بستگی به صورت مJسئله دارد در حالت کلی بهتر است از هر دو استفاده شود هر کدام نقش مخصوص خود را دارد مJیتوان الگوریتمی داشت که فقط از mutationاستفاده کند ولی الگوریتمی که فقط از crossoverاستفاده کJند کار نخواهد کرد ?Crossover OR mutation ‏ ‏ ‏ ‏ 21 CrossoverخJاصیتجستجوگراJنه Jو یJJا explorativeدارد .میتواJندبا اJنجام JپJJJرشهJایبJJJزرگبJJJه JمحلهائیدربینواJJلدینرفته Jو نJJواJحیجJدیدیرا کJJJشفJJماید. ن ‏MutationخJاصیتگJJJسترشیو یJJا exploitiveدارد .میتواJند بJJJا اJنجامJ تJJJغییراJتکJJJوچکتJJJصادفیبJJJه JنJJواJحیکJJJشفشJJده JوسعJتبJJJبخشد. ‏Crossoveاطالعات والدین را ترکیب مJیکند درحالیکه mutation میتواند اطالعات جدیدی اضافه نماید. برای رسیدن به یک پاسخ بهینه یک خوش شانسی در mutationالزم است. تابع تناسب تابع fitnessمعیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند .نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد: classification : در این نوع مسایل تابع تناسب معموال برابر است با دقت قانون در دسته بندی مثالهای آموزشی. 22 انتخاب فرضیه ها 1/6 = 17%  Roulette Wheel selection B A C احتمالGA رفی شده در الگوریتم سادهJدر روش مع 3/6 = 50%2/6 = 33% بعدیJانتخاب یک فرضیه برای استفاده در جمعیت بقیهfitness آن بهfitness بستگی به نسبت Roulette Wheel این روش.اعضا دارد fitness(A) = 3 .نامیده میشودselection fitness(B) = 1 P(hi) = Fitness (hi) / Σj Fitness (hj) fitness(C) = 2 :روشهای دیگر tournament selection rank selection    23 نحوه جستجو در فضای فرضیه روش جستجوی GAبا روشهای دیگر مثل شبکه های عصبی تفاوت دارد: در شبکه عصبی روش Gradient descentبصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه GAممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GAدر مینیمم محلی کاهش می یابد. با این وجود GAبا مشکل دیگری روبروست که crowding نامیده میشود. 24 Crowding crowding پJJJدیده JاJی اJستکJJJه Jدر آJن عضویکJJJه JسJJازگاری بJJJسیاربیشتریاز بJJJقیه JاJفراد جمعیتدارد بJJJطور مرتبتJJJولید نJJسلکJJJرده Jو بJJJا تJJJولید اJعضایمشابه Jدرصد عمده JاJیاز جمعیت را اJشغJاJJلمیکند. اینکار باعث کاهش پراکندگی جمعیت شده و سرعت GAرا کم میکند. )F(X ‏X 25 راه حل رفع مشکل Crowding استفاده از rankingبرای انتخاب نمونه ها :با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند مقدار این برتری نشان داده نخواهد شد. Fitness sharing : مقدار Fitnessیک عضودر صورتیکه اعضا مشابهی در جمعیت وجود داشته باشند کاهش می یابد. 26 چرا GAکار میکند؟ سئوالی که ممکن است برای تازه واردین به روشهای ژنتیکی ایجاد شود این است که آیا این روش واقعا میتواند کار مفیدی انجام دهد؟ 27 ارزیابی جمعیت و قضیه Schema ‏ ‏ ‏ ‏ 28 آیا میتوان تکامJل در جمJعیت Jدر طی زمان را بصورت ریاضی مدل نمJود؟ قضیه Schemaمیتواند مشخصه پدیده تکامJل در GAرا بیان نماید. یک SchemaمجمJوعه ای از رشته بیت ها را توصیف میکند.یک Schemaهر رشته ای از 0و1و* است .مثل 10*0کJه * حالت dont careاست. یک رشته بیت را میتوان نماینده هر یک از Schemaهای متفاوتی دانست که با آن تطابق دارند .مثال 0010را میتوان نماینده 24 Schemaمختلف دانست : ****,10*0,**00وغیره قضیه Schema قضیه Schemaبیان میکند که چگونه یک Schemaدر طول زمان در جمعیت تکامل پیدا خواهد کرد. فرض کنید که در لحظه tتعداد نمونه هائی که نماینده یک Schemaمثل sهستند برابر با ) m(s,tباشد .این قضیه مقدار مورد انتظار ) m(s,t+1را مشخص میکند. قبال دیدیم که احتمال انتخاب یک فرضیه برابر بود با: )P(hi) = Fitness (hi) / Σj Fitness (hj این مقدار احتمال را میتوان بصورت زیر نیز نشان داد: )P(hi) = f (hi) / n f’ (ti 29 مقدار متوسط fitnessبرای تمامی فرضیه ها قضیه Schema اگر عضوی از این جمعیت انتخاب شود احتمال اینکه این عضو نماینده Sباشد برابر است با: )u(s,t )m(s,t ‏ ‏n f  t ‏ ‏f  h ‏ ‏ ‏ps n f  t ‏p h s  ‏hs که در آن مقدار ) u(s,tبرابر است با مقدار میانگین fitness ‏s اعضای ‏f ( ‏h ) ‏ ‏ps )m(s,t ‏hs ‏u(s,t)  از اینرو مقدار مورد انتظار برای نمونه هائی از sکه از n مرحله انتخاب مستقل حاصل خواهند شد برابر است با: )m(s,t 30 )u(s,t ‏ ‏f  t ‏E[m(s,t  1)]  قضیه Schema رابطه فوق به این معناست که تعداد Schemaهای مورد انتظار در لحظه t+1متناسب با مقدار میانگین ) u(s,tبوده و با مقدار fitnessسایر اعضا نسبت عکس دارد. برای بدست آوردن رابطه فوق فقط اثر مرحله انتخاب نمونه ها در نظر گرفته شده است .با در نظر گرفتن اثر crossoverو Mutationبه رابطه زیر خواهیم رسید: ‏d(s)  ‏pc l  1  1 ‏ p )o( s ‏m 31 )u(s,t ‏ ‏E[m(s,t  1)]   m(s,t) 1 ‏ ‏f  t Schema Theorem  Theorem E m  s, t  1    d  uˆ s, t   o s  m  s, t   1- p c s  1- p m  l -1 f t    m(s, t)  number of instances of schema s in population at time t  f t  average fitness of population at time t  uˆ s, t  pc  probability of single point crossover operator  pm  probability of mutation operator  l  o(s)  number of defined (non “*”) bits in s  d(s)  distance between rightmost, leftmost defined bits in s    average fitness of instances of schema s at time t  length of individual bit strings Intuitive Meaning  “The expected number of instances of a schema in the population tends toward its relative fitness” 32 خالصه ‏ ‏ ‏ ‏ 33 یک Schemaاطالعات مفید و امید بخش موجود در جمJعیت را کJد میکند. از آنجائیکه همواره رشته هائی که سازگارترند شانس بیشتری برای انتخاب شدن دارند ،بتدریج مثالهای بیشتری به بهترین Schemaها اختصاص می یابند. عمJل crossoverباعث قطع رشته ها در نقاط تصادفی مJیشود .با این وجود در صورتیکه اینکار باعث قطع Schemaنشده باشد آنرا تغییر نخواهد داد.در حالت کلی Schemaهای با طول کوتاه کمتر تغJییر میکنند. عمJل mutaionدر حالت کلی باعث تغییرات موثر در Schema نمیگردد. ‏Highly-fit, short-defining-length schema (called building blocks) are propagated ‏generation to generation by giving exponentially increasing samples to the ‏observed best تفاوت GAبا سایر روشهای جستجو GA بJJJجایکJJJد کJJJردنپJJJاراJمترها مجموعه JآJنهJا را کJJJد میکند یJJکJJقطه JبJJJدنباJJلجمعیتیاز نJJقاط GA بJJJجایجستجو بJJJراJی ن میگردد. GA بJJJجایاJستفاده Jاز مشتقو یJJا سJJایر اJطالعاتکJJJمکی مستقیما ازاJطالعاتموجود در نJJتیجه JبJJJهJره Jمیگیرد. GA بJJJجایقJJواJنینقJJطعیاز قJJواJنیناJحتماJJلبJJJراJیتJJJغییر اJستفJاده Jمیکند. 34 مثالی از کاربرد الگوریتم ژنتیک بهینه‌سازی چینش حروف فارسی بر روی صفحه‌کلید با استفاده از الگوریتم‌های ژنتیکی 35 مقدمه بدست آوردن چینش بهینه حروف فارسی بر روی صفحه‌کلید در درازمدت برای کسانی که با تایپ کردن متون فارسی درگیر هستند ,بسیار مفید خواهد بود. یک الگوریتم تکاملی می‌تواند با توجه به یک تابع تناسب که میزان راحتی تایپ کردن متون فارسی را برای یک چینش ارائه می‌دهد ,در فضای چینش‌های حروف فارسی بر روی صفحه‌کلید جستجو کرده و چینش بهینه را بدست آورد. 36 چینش کنونی حروف فارسی بر روی صفحه‌کلید 37 مساله در این مساله هندسه صفحه‌کلید ثابت است و ما می‌خواهیم که تعداد 33 نشانه که متشکل از 32حرف الفبای فارسی بعالوه حرف همزه "ء" است را بر روی سه ردیف صفحه‌کلید که به ترتیب دارای ,11 ,12و 10کلید هستند ,قرار دهیم. هدف این مساله بدست آوردن چینشی از این نشانه‌ها بر روی این کلید‌ها است ,به طوری که این چینش طوری باشد که کاربر هنگام استفاده از صفحه ‌کلید برای تایپ حروف فارسی ,احساس راحتی بیشتری نسبت به کار با بقیه چینش‌ها داشته باشد. 38 الگوریتم ژنتیک ‏ ‏ ‏ ‏ 39 برای حل مساله از یک الگوریتم ژنتیک استفاده شده است. تابع تناسب موجود در این الگوریتم ژنتیک ,میزان راحتی یا سختی استفاده از یک چینش را محاسبه می‌کند. در هر نسل ,عملگرهای ژنتیکی بر روی جمعیت موجود که چینش‌های مختلفی از حروف فارسی بر روی صفحه‌کلید هستند ,اعمال می‌شوند و جامعه به سمتی سوق داده می‌شود که مقدار تابع تناسب به ازای اعضای آن به کمینه مقدار خود برسند. میزان تناسب هر عضو از جامعه که در واقع یک چینش حروف فارسی بر روی صفحهکلید هستند ,با اعمال تابع تناسب بر متنی که از مطالب چند سایت خبری فارسی زبان تهیه شده است ,به دست میآید. جمعیت ‏ ‏ 40 اعضای جمعیت جایگشت‌های مختلف حروف فارسی روی صفحه‌کلید هستند .هر عضو جمعیت را می‌توان به صورت برداری از حروف فارسی در نظر گرفت که هر اندیس آن متناظر با یک کلید از صفحه‌ کلید است. ال هر بردار با طول 33که شامل حروف فارسی بعالوه حرف همزه "ء" باشد را میتوان مث ً به عنوان یک کروموزوم (یک عضو از جمعیت) در نظر گرفت که حرف iام از این بردار, متناظر با کلیدی از صفحه‌کلید است که برچسب شمارة iبر روی آن زده شده است. تعداد چینش‌های مختلف !33 تابع تناسب تعیین راحتی و سختی کار کردن با چینش حروف بر روی صفحه‌کلید یک مساله پیچیده ارگJونومیک است. نورمن و رومل‌هارت چهار هدف را برای طراحی کارای یک صفحه‌کلید ارائه کرده‌اند: ‏ ‏ .1 .2 .3 .4 41 برابری کاری که دو دست انجام مJی‌دهند؛ بیشترین تایپ حروف به صورت متناوب با دو دست؛ کمترین تکرار تایپ دو حرف متوالی با یک انگشت؛ و بیشترین تایپ حروف بر روی کلیدهای پایه‌ای (کلیدهای ردیف وسط). تابع تناسب ‏ ‏ ‏ ‏ ‏ 42 .برای دو هدف اول می‌توان فاکتور اندازه‌گیری زیر را معرفی‌کرد: پJJJشتسJJر :ChandهزینJه مربوط بJJJه JاJستفاده Jاز یJJکدستبJJJراJیتJJJایJپکJJJردندو حJرف ‌ هم.J برای هدف سوم ,فاکتور انداز‌ه‌گیری زیر معرفی می‌شود: پJJJشت یJJJکJنگشJتبJJJراJیتJJJایJپکJJJردندو حJرف ‌ ا :CfingerهزینJه مربوط بJJJه JاJسJتفJاده Jاز سJJر هم.J :Cergonomicهزینه مربوط بJJJه JتJJJایپکJJJردنیJJکحJرفبJJJا تJJJوجه JبJJJه JموقعیتآJنحJرف بJJJر رویصJJفحه‌JکJJJلید. تابع تناسب تابJJع تناسJJب برای هJJر کروموزوم از مجموع ایJJن سJJه فاکتور برای تمامJJی حروفJJی کJJه در متJJن مورد اسJJتفاده برای آزمایJJش وجود دارند ,بدست می‌آید: (l ,l j 1)  C finger(l j ,l j  1)  Cergonomic ]) (l j [C ‏ ‏Wl w ‏hand j ‏j i ‏Fitness )(layout ‏ ‏wi WمجموعJJJه تJJJمامJJJیکJJJلماتموجود در متJJJنمورد اJسJJJتفJاده JبJJJراJی ‏Jست آزمایشا ؛ 43 ‏ wiکلمه iام از مJجموعه Wاست؛ ‏ ljحرف jام از کلمه wiاست؛ عملگرهای ژنتیکی ‏ ‏ ‏ ‏ 44 در اینجا تنها از عمJلگر جهش استفاده شده است. دلیJل عدم اسJتفاده از عملگJر دورگJه ایJن اسJت کJه سJاختار اعضای جمعیJت طوری اسJت کJه ترکیJب کردن دو کروموزوم والJد هزینJة زمانJی باالیJی دارد. عملگJJر جهJJش را بJJه دو صJJورت برای اعضای مختلJJف جامعJJه بJJه کار می‌بریم .در ایJن مJسJاله یJک جامعJه نخبگان انتخاب می‌کJنیJم کJه اعضای آJن تراز اول جمJعیت از دید تابع تناسب را تشکیل می‌دهند. عملگJJر جهJJش برای هJJر عضJJو از جامعJJة نخبگان ,تنهJJا محتویات چهار زوج ژJن را بJه صJورت تصJادفی جابه‌جJا می‌کند .در حالیکJه برای افراد عادی جامعه این تعداد به 12جابه‌جایی افزایش می‌یابد. ‏% کارایی الگوریتم ژنتیک با پارامترهای زیر اجرا کردیم: تعداد اعضای جمعیت 100کروموزوم که در نسل اول به صورت تصادفی تولید شدهاند؛  درصد تشکیلدهنده جامعه نخبگان است %10 ,کل جمعیت ؛ تعداد اعضایی که به صورت مستقیم و بدون اینکه عمگرهای ژنتیکی بر روی آن اعمال شود ,به نسل بعدی میروند 3 ,عضو؛ و تعداد کل نسلها 500نسل. 45 کارایی 2 1.8 1.6 1.4 1 0.8 ‏fitness value 1.2 0.6 0.4 0.2 0 500 450 400 350 300 250 200 150 100 50 0 ‏generationnumber نمودارهای تناسب اعضای جامعه در طی نسلهای مختلف .منحنیهای نشان داده شده به ترتیب از 46باال به پایین ,متوسط مقادیر تناسب همه اعضای جامعه ,متوسط مقادیر تناسب جامعه نخبگان, و بهترین تناسب هستند. بهترین چینش بهترین چینشی که در نهایت این الگوریتم ژنتیک برای حروف فارسی ارائه داد ,هزینهاش با توجه به تابع تناسب 815/0 ,هزینه چینش کنونی حروف فارسی است . 47 مدلهای تکامل در سیستمهای طبیعی هر موجود زنده در طول زندگی خود یاد میگیرد که با شرائط سازگاری نماید .به همین ترتیب نسل های مختلف یک نمونه در طول زمان سازگاری های مختلفی را کسب میکنند: سوال: رابطه بین یادگیری یک موجود در طول زندگی شخصی و یادگیری نسل های یک نمونه در طول زمان چیست؟ 48 Lamarckian evolution Lamarck داJنشمند قJJرننJJوزدهم JفJJJرضیه JاJیاراJئه JکJJJردهJ کJJJه JطبقآJنتJJJجربیاتیJJکموجود زنده Jدر تJJJرکJیبژنتیکی فJJJرزنداJنآJنتJJJاثیر میگذارد. برای مثال موجودی که یاد گرفته از غذای سمی پرهیز کند این ویژگی را بصورت ژنتیکی به فرزندان خود منتقل مینماید تا آنها دیگر مجبور به یادگیری این پدیده نباشند. اما شواهد تجربی این نظر را تائید نمیکنند: یعنی تجربیات فردی هیچ تاثیری Jدر ترکیب ژنتیکی فرزندان ندارد. 49 Baldwin Effect نظریه دیگری وجود دارد که تاثیر یادگیری را بر تکامل توضیح میدهد .این نظریه که اثر Baldwinنامیده میشود بر مبنای مشاهدات زیر استوار است: اگر موجودی از طرف محیط متغیری تحت فشار قرار گرفته باشد ،افرادی که توانائی یادگیری نحوه برخورد با شرایط را داشته باشند شانس بیشتری برای بقا دارند. موجوداتی که تحت شرایط جدید باقی میمانند جمعیتی با توانائی یادگیری را تشکیل میدهند که فرایندهای تکاملی در آنها سریعتر رخ میدهد و باعث میشود تا نسلی بوجود بیاید که نیازی به یادگیری مواجهه با شرایط جدید را نداشته باشند. 50 اجرای موازی الگوریتم های ژنتیک الگوریتم های ژنتیک از قابلیت خوبی برای پیاده سازی بصورت موازی برخوردارد هستند. در یک روش پیاده سازی موازی ،جمعیت به گروههای کوچکتری با نام demesتقسیم شده و هرکدام در یک گره محاسباتی مورد پردازش قرار میگیرند. در هر گره یک الگوریتم استاندارد GAبر روی demeاجرا میشود. انتقال بین گره ها از طریق پدیده migrationصورت میپذیرد. 51 Evolving Neural Networks از GAبرای تکامل جنبه های مJختلف NNاستفاده زیادی بعمJل آمده است.از جمله :وزنها ،ساختارو تابع یادگJیری. استفاده از GAبرای یادگیری وزنهای یک شبکه عصبی میتواند بسیار سریعJتر از روش استاندارد back propagationعمل نماید. استفاده از GAبرای یادگیری ساختار شبکه عصبی مشکلتر میباشد. برای شبکه های کوچک با استفاده از یک ماتریس مJشخص مJیشود که چه نرونی به چه نرونهای دیگری متصل است.Jآنگاه این ماتریس به ژن های الگوریتم ژنتیک تبدیل و ترکیبات مختلف آن بررسی میگردد. برای بدست آوردن تابع یادگیری یک شبکه عصبی راه حلهائی نظیر استفاده از GPمورد استفاده قرار گJرفته امJا عموما این روشها بسیار کند عمل کرده اند. 52 مراجع [1] D. E. Glover, Genetic Algorithm and Simulated Annealing, page 12-31, Morgan Kaufmann, Los Altos, CA, 1987. [2] Lissa W. Light and Peter G. Anderson, “Typewriter keyboards via simulated annealing”, AI Expert, September 1993. [3] Peter Klausler, www.visi.com/~pmk/evovled.html, September 2005. [4] M. 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. [5] P. S. Deshwall and K. Deb, Design of an Optimal Hindi Keyboard for Convenient and Efficient Use. Technical Report on KanGAL Report No. 2003005, Indian Institute of Technology, Kanpur, 2003. [6] D. A. Norman and D. E. Rumelhart, Cognitive Aspects of Skilled Typing, Springer-Verlag, New York, 1983. [7] J. S. Goetti, A.W. Brugh, and B. A. Julstrom, “Arranging the Keyboard with a PermutaionCoded Genetic Algorithm”, Proc. of the 2005 SCM Symposium on Applied Computing , Volume 2, pp. 947-951, 2005. 53 Genetic Programming ‏ ‏ ‏ GPتJJJکنیکیاJستکJJJه JکJJJامپیوترها را قJJادر میسازد تJJJا بJJJه Jحلمسائل بJJJپردازند بJJJدونآJنکه JبJJJطور صJJریح JبJJJراJیآJنبJJJرنامه JریزیشJJده JبJJJاشند. GPروشیاز اJJلگوریتمهJایتJJJکاملیاJستکJJJه Jدر آJنهرعضو جمعیتیJJک ‏Jست بJJJرنامه JکJJJامپیوتریا . برنامه ها اغلب بتوسط یک درخت نمایش داده شده و اجرای برنامه برابر است با parsکردن درخت. + )F = sin(x) + sqrt( x^2 + y ‏sqrt ‏Sin + ‏y ^ 2 54 ‏x ‏x نمایش برنامه ها برای استفاده از GPدر یک زمینه خاص، ‏ ‏ مJیبایست توابع پایه ای کJه در آن زمJینه مورد نیاز هستند نظیر sin, cos, sqrt, +, -, etcتوسط کاربر تعریف شوند همJچنین ترمینالهJا نظیر متغیرها و ثوابت نیز باید مشخص شوند آنگاه الگوریتم GPدر فضای بسیار بزرگ برنامه هائی که توسط این مقادیر اولیه قابل بیان هستند یک عمل جستجوی تکاملی را انجام خوهد داد. 55 اپراتور crossoverبرای GP ‏ اپراتور crossover :شاخه هائی از یک درخت والد با شاخه هائی از درخت والد دیگر بطور تصادفی عوض میشوند + + ^ ^ ^ ‏Sin 2 ‏x ‏y ‏x ‏Sin 2 + ‏x فرزندان والدین ‏Crossover + ‏sqrt ‏Sin ‏sqrt ‏x + + 56 2 ‏x + ‏Sin + ^ ‏y 2 ‏x مثال در کتاب مثالی از Kozaمطرح شده که در آن الگوریتمی یاد گرفته میشود که بتواند بلوک ها را در یک ستون روی هم بچیند هدف مسئله این است که بلوک ها طوری روی هم چیده شوند که کلمه universalرا بسازند ‏N ‏I 57 ‏A ‏L ‏U ‏E ‏S ‏RV مثال ‏ محدودیت :در هر مJرحله فقط میتوان یک بلوک را جابجا نمود .در نتیجه تنهJا حرکت های ممکن عبارتند از: ‏ ‏ ‏ توابع اولیه: ‏ ‏ ‏ 58 بلوک آخر ستون را میتوان روی میز قرار داد و یا اینکه یک بلوک را از میز به انتهای ستون منتقل نمود. ‏CS (current stack) :نام بلوک موجود در انتهای ستون را بر میگرداند ) F برای حالتی که بلوکی وجود ندارد( ) TP (top correct blockنJJام JآJخرینبJJJلوکJیرا کJJJه JهمراJه JبJJJا بJJJلوکهای زیرینشتJJJرتیبصJJحیح مورد نJJظر را دارند ،بJJJرمیگرداJند ) NN (next necessaryنJJام JبJJJلوکJیکJJJه JبJJJاید در بJJJاJJالی TPقJJرار گJJJیرد تJJJا تJJJرتیب universalدرستدربیاید. مثال سایر توابع اولیه: ‏ ‏ ‏ ‏ ‏ ‏ 59 (move block x to stack )MS xاگر بلوک xروی میزباشد این اپراتور آنرا به باالی ستون منتقل میکند .درغیر اینصورت مقدار Fبرمیگرداند. (move block x to table )MT xاگر بلوک xجائی روی ستون باشد این اپراتور بلوک باالی ستون را به میز منتقل میکند .درغیر اینصورت مقدار ‏Fبرمیگرداند. (.returns true if x = y )EQ x y (.returns the complement of x )NOT x ‏DU( x y) do x until expression y is true مثال مقدار تابع fitness در این آزمایش تعداد 166مJثال که هر یک در برگیرنده آرایش اولیه متفاوتی برای بلوک ها بودند تدارک دیده شده بود. تابع fitnessیک برنامه برابر است با تعداد مثالهائی که برنامه قادر به حل آن است. برنامه با جمعیت اولیه ای برابر با 300برنامه تصادفی شروع بکار نمJوده و پس از تولید 10نسل قادر میشود تا برنامه ای پیدا نمJاید کJه تمJامی 166مثال را حل نماید: (EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT ) ))NN 60 مثال :طراحی فیلتر صورت مJسئله :برنامه ای کJه یک مJدار ساده اولیه رابه مدار پیچیده مورد نیاز تبدیل نماید. توابع اولیه: ‏ ‏ ‏ ‏ ‏ ‏ 61 تابعی برای اضافه کردن قطعات و سیم بندی های مدار تابعی برای حذف کردن قطعات و سیم بندی های مدار تابع fitnessشبیه سازی مدار بدست آمده توسط نرم افزار SPICE برای مشخص نمودن میزان تطبیق آن با طرح مورد نظر .خطای مداربرای 101فرکانس مختلف مورد بررسی قرار میگرفت. جمJعیت اولیه : 640000 نرخ crossover : 89درصد نرخ mutation : 1درصد مثال :طراحی فیلتر سیستم برروی یک کامپیوتر موازی با 64گره مورد آزمایش قرار گرفت. برای نسل اولیه ای که بصورت تصادفی ایجاد شدند در %98مواقع حتی امکان شبیه سازی وجود نداشت. این نرخ بتدریج کاهش یافته و پس از تولید 137نسل مداری حاصل شد که با مشخصات مورد نظر صدق میکرد. در اغلب موارد کارائی الگوریتم GPبستگی به نحوه نمایش و همچنین تابع fitnessدارد. 62