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

1 الگوریتم های ژنتیک 2 الگوریتم ژنتیک الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است. این روش در سال 1970توسط John Holland معرفی گردید این روشها با نام Evolutionary Algorithmsنیز خوانده میشوند. 3 ایده کلی یک GAبرای حل یک مسئله مجموعه بسیار بزرگی از راه حلهای ممکن را تولید میکند. هر یک از این راه حلها با استفاده از یک “ تابع تناسب” مورد ارزیابی قرار میگیرد. آنگاه تعدادی از بهترین راه حلها باعث تولید راه حلهای جدیدی میشوند .که اینکار باعث تکامل راه حلها میگردد. بدین ترتیب فضای جستجو در جهتی تکامل پیدا میکند که به راه حل مطلوب برسد در صورت انتخاب صحیح پارامترها ،این روش میتواند بسیار موثر عمل نماید. 4 فضای فرضیه الگوریتم ژنتیک بجای جستجوی فرضیه های general-to specificو یا simple to complex فرضیه ها ی جدید را با تغییر و ترکیب متوالی اجزا بهترین فرضیه های موجود بدست میاورد. در هرمرحله مجموعه ای از فرضیه ها که جمعیت ( )populationنامیده میشوند از طریق جایگزینی بخشی از جمعیت فعلی با فرزندانی که از بهترین فرضیه های موجود حاصل شده اند بدست میآید. 5 ویژگیها الگوریتم های ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند میتواند بکار گرفته شود. همچنین در مسایلی با فضای فرضیه پیچیده که تاثیر اجزا آن در فرضیه کلی ناشناخته باشند میتوان از GAبرای جستجو استفاده نمود. برای discrete optimizationبسیار مورد استفاده قرار میگیرد. الگوریتم های ژنتیک را میتوان براحتی بصورت موازی اجرا نمود از اینرو میتوان کامپیوترهای ارزان قیمت تری را بصورت موازی مورد استفاده قرار داد. امکان به تله افتادن این الگوریتم در مینیمم محلی کمتر از سایر روشهاست. از لحاظ محاسباتی پرهزینه هستند. تضمینی برای رسیدن به جواب بهینه وجود ندارد. 6 Parallelization of Genetic Programming در سال 1999شرکت .Genetic Programming Incیک کامپیوتر موازی با 1000گره هر یک شامل کامپیوتر های P2, 350 MHZبرای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد. 7 کاربر دها کاربرد الگوریتم های ژنتیک بسیار زیاد میباشد  optimization,  automatic programming,  machine learning,  economics,  operations research,  ecology,  studies of evolution and learning, and  social systems 8 زیر شاخه های EA روش های EAبه دو نوع مرتبط به هم ولی مجزا دسته بندی میشوند: ‏Genetic Algorithms (GAs)  در این روش راه حل یک مسئله بصورت یک bit string نشان داده میشود. ‏Genetic Programming (GP)  این روش به تولید expression treesکه در زبانهای برنامه نویسی مثل lispمورد استفاده هستند میپردازد بدین ترتیب میتوان برنامه هائی ساخت که قابل اجرا باشند. 9 الگوریتم های ژنتیک روش متداول پیاده سازی الگوریتم ژنتیک بدین ترتیب است که: مجموعه ای از فرضیه ها که populationنامیده میشود تولید وبطور متناوب با فرضیه های جدیدی جایگزین میگردد. در هر بار تکرارتمامی فرضیه ها با استفاده از یک تابع تناسب یا Fitnessمورد ارزیابی قرار داده میشوند .آنگاه تعدادی از بهترین فرضیه ها با استفاده از یک تابع احتمال انتخاب شده و جمعیت جدید را تشکیل میدهند. تعدادی از این فرضیه های انتخاب شده به همان صورت مورد استفاده واقع شده و مابقی با استفاده از اپراتورهای ژنتیکی نظیر Crossoverو Mutationبرای تولید فرزندان بکار میروند. 10 پارامترهای GA یک الگوریتم GAدارای پارامترهای زیر است: )GA(Fitness,Fitness_threshold,p,r,m ‏Fitness : تابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد Fitness_threshold : مقدار آستانه که شرط پایان را معین میکند p : تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند r: در صدی از جمعیت که در هر مرحله توسط الگوریتم crossoverجایگزین میشوند m: نرخ mutation 11 الگورتیم ‏Initialize : جمعیت را با تعداد pفرضیه بطور تصادفی مقدار دهی اولیه کنید. ‏Evaluate : برای هر فرضیه hدر pمقدار تابع ) Fitness(hرا محاسبه نمائید. تا زمانیکه[)< ]maxh Fitness(h Fitness_thresholdیک جمعیت جدید ایجاد کنید. فرضیه ای که دارای بیشترین مقدار Fitnessاست را برگردانید. 12 نحوه ایجاد جمعیت جدید مراحل ایجاد یک جمعیت جدید بصورت زیر است: ‏select : تعداد( p)r-1فرضیه از میان Pانتخاب و به Psاضافه کنید .احتمال انتخاب یک فرضیه hiاز میان Pعبارت است از: )P(hi) = Fitness (hi) / Σj Fitness (hj ‏ ‏ ‏ ‏ 13 هر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است. این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد.آمده توسط رابطه فوق ،تعداد(2/)rp ‏Crossover :با استفاده از احتمال بدست زوج فرضیه از میان Pانتخاب و با استفاده از اپراتور Crossoverدو فرزند از آنان ایجاد کنید .فرزندان را به Psاضافه کنید. ‏Mutate :تعداد mدرصد از اعضا Psرا با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنید ‏P Ps :Update برای هر فرضیه hدر Pمقدار تابع Fitnessرا محاسبه کنید نمایش فرضیه ها در الگوریتم ژنتیک معموال فرضیه ها بصورت رشته ای از بیت ها نشان داده میشوند تا اعمال اپراتورهای ژنتیکی برروی آنها ساده تر باشد. ‏ ‏ ‏ Phenotype :به مقادیر یا راه حلهای واقعی گفته میشود. ‏Genotype :به مقادیر انکد شده یا کروموزم ها گفته میشود که مورد استفاده GA قرار میگیرند. باید راهی برای تبدیل این دو نحوه نمایش به یکدیگر بدست آورده شود. = Genotype space ‏Encoding {0,1}L )(representation 10010001 10010010 010001001 011101001 14 ‏Decoding )(inverse representation ‏Phenotype space مثال :نمایش قوانین If-then ‏rules ‏ برای نمایش مقادیر یک ویژگی نظیر Outlookکه دارای سه مقدار Sunny, Overcast ,Rainاست میتوان از رشته ای با طول 3بیت استفاده نمود 100 -> Outlook = Sunny 011-> Outlook = Overcast  Rain برای نمایش تر کیب ویژگی ها رشته بیت های هر یک را پشت سر هم قرار میدهیم: ‏Wind ‏Outlook 10 011 به همین ترتیب کل یک قانون if- thenرا میتوان با پشت سر هم قرار دادن بیت های قسمت های شرط و نتیجه ایجاد نمود: ‏IF Wind = Strong THEN PlayTennis = No ‏ bit string: 111100 15 ‏PlayTennis ‏Wind ‏Outlook 0 10 111 نمایش فرضیه ها :مالحظات ممکن است ترکیب بعضی از بیت ها منجر به فرضیه های بی معنی گردد .برای پرهیز از چنین وضعیتی: میتوان از روش انکدینگ دیگری استفاده نمود. اپراتورهای ژنتیکی را طوری تعیین نمود که چنین حالتهائی را حذف نمایند میتوان به این فرضیه ها مقدار fitnessخیلی کمی نسبت داد. 16 اپراتورهای ژنتیکی : Crossover اپراتور Crossoverبا استفاده از دو رشته والد دو رشته فرزند بوجود میآورد. برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی میشود. انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود ‏single-point crossover ‏ Two-point crossover ‏ Uniform crossover ‏ برای تعیین محل بیتهای کپی شونده از یک رشته به نام Crossover Maskاستفاده میشود. 17 Single-point crossover یک نقطه تصادفی در طول رشته انتخاب میشود. والدین در این نقطه به دوقسمت میشوند. هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید. ‏Children 18 ‏Crossover Mask: 11111000000 ‏Parents 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 Crossover روشهای دیگر Two-point crossover  Parents Crossover Mask: 00111110000 Children 1 1 1 10 00 0 1 00 00 1 0 0 0 1 1 1 00 00 0 1 00 10 1 0 0 0 0 0 1 00 00 0 1 00 10 0 1 0 1 0 0 1 10 00 01 00 00 0 1 0 1 Uniform crossover  Parents Crossover Mask: 10011010011 Children 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 19 بیتها بصورت یکنواخت از والدین انتخاب میشوند اپراتورهای ژنتیکی : Mutation اپراتور mutationبرای بوجود آوردن فرزند فقط از یک والد استفاده میکند .اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد. با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند. معموال mutationبعد از انجام crossoverاعمال میشود. ‏Child 1 1 1 0 1 0 1 0 1 0 0 0 20 ‏Parent 1 1 1 0 1 0 0 1 0 0 0 ?Crossover OR mutation این سوال ها سالها مطرح بوده است: کدامیک بهتر است؟ کدامیک الزم است؟ کدامیک اصلی است؟ پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده: بستگی به صورت مسئله دارد در حالت کلی بهتر است از هر دو استفاده شود هر کدام نقش مخصوص خود را دارد میتوان الگوریتمی داشت که فقط از mutationاستفاده کند ولی الگوریتمی که فقط از crossoverاستفاده کند کار نخواهد کرد 21 ?Crossover OR mutation Crossover خاصیت جستجوگرانه و یا explorativeدارد. میتواندبا انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید. ‏Mutation خاصیت گسترشی و یا exploitiveدارد .میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد. ‏Crossove اطالعات والدین را ترکیب میکند درحالیکه mutationمیتواند اطالعات جدیدی اضافه نماید. برای رسیدن به یک پاسخ بهینه یک خوش شانسی در mutationالزم است. 22 تابع تناسب تابع fitnessمعیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند .نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد: classification : در این نوع مسایل تابع تناسب معموال برابر است با دقت قانون در دسته بندی مثالهای آموزشی. 23 انتخاب فرضیه ها 1/6 = 17%  Roulette Wheel selection B A C در روش معرفی شده در الگوریتم ساده 3/6 = 50% 2/6 = 33% احتمال انتخاب یک فرضیه برایGA استفاده در جمعیت بعدی بستگی به بقیه اعضاfitness آن بهfitness نسبت fitness(A) = 3 Roulette Wheel این روش.دارد fitness(B) = 1 .نامیده میشودselection P(hi) = Fitness (hi) / Σj Fitness (hj) fitness(C) = 2 : روشهای دیگر tournament selection  rank selection  24 نحوه جستجو در فضای فرضیه روش جستجوی GAبا روشهای دیگر مثل شبکه های عصبی تفاوت دارد: در شبکه عصبی روش Gradient descentبصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه GAممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GAدر مینیمم محلی کاهش می یابد. با این وجود GAبا مشکل دیگری روبروست که crowdingنامیده میشود. 25 Crowding crowding پدیده ای است که در آن عضوی که سازگاری بسیاربیشتری از بقیه افراد جمعیت دارد بطور مرتب تولید نسل کرده و با تولید اعضای مشابه درصد عمده ای از جمعیت را اشغال میکند. اینکار باعث کاهش پراکندگی جمعیت شده و سرعت GAرا کم میکند. )F(X ‏X 26 راه حل رفع مشکل Crowding استفاده از rankingبرای انتخاب نمونه ها :با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند مقدار این برتری نشان داده نخواهد شد. Fitness sharing : مقدار Fitnessیک عضودر صورتیکه اعضا مشابهی در جمعیت وجود داشته باشند کاهش می یابد. 27 چرا GAکار میکند؟ سئوالی که ممکن است برای تازه واردین به روشهای ژنتیکی ایجاد شود این است که آیا این روش واقعا میتواند کار مفیدی انجام دهد؟ 28 ارزیابی جمعیت و قضیه ‏Schema آیا میتوان تکامل در جمعیت در طی زمان را بصورت ریاضی مدل نمود؟ قضیه Schemaمیتواند مشخصه پدیده تکامل در GAرا بیان نماید. یک Schemaمجموعه ای از رشته بیت ها را توصیف میکند.یک Schemaهر رشته ای از 0و1و* است .مثل 10*0 که * حالت dont careاست. یک رشته بیت را میتوان نماینده هر یک از Schemaهای متفاوتی دانست که با آن تطابق دارند .مثال 0010را میتوان نماینده Schema 24مختلف دانست : ****,10*0,**00وغیره 29 قضیه 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 30 مقدار متوسط fitnessبرای تمامی فرضیه ها قضیه Schema اگر عضوی از این جمعیت انتخاب شود احتمال اینکه این عضو نماینده Sباشد برابر است با: ) f h  u ( s, t ‏ph  s    )   m( s , t ‏ ‏hs  p n f t  ‏n f t  ‏s که در آن مقدار ) u(s,tبرابر است با مقدار میانگین fitnessاعضای s ) f ( h ‏ps ) m( s , t ‏hs  ‏u ( s, t )  از اینرو مقدار مورد انتظار برای نمونه هائی از sکه از nمرحله انتخاب مستقل حاصل خواهند شد برابر ) u ( s, t است با: ‏E[m( s, t  1)]  ) m( s , t ‏ 31 ‏f t  قضیه Schema رابطه فوق به این معناست که تعداد Schema های مورد انتظار در لحظه t+1متناسب با مقدار میانگین ) u(s,tبوده و با مقدار fitnessسایر اعضا نسبت عکس دارد. برای بدست آوردن رابطه فوق فقط اثر مرحله انتخاب نمونه ها در نظر گرفته شده است .با در Mutationبه رابطه crossoverو گرفتن اثر نظر ‏o ( ‏s ) ) u ( s, t ‏d ( ‏s ) ‏ ‏ ‏ رسیدE[m( s, t  1)]   m( s, t ) 1  p : خواهیم 1  p زیر ‏c l 1 ‏m ‏ ‏ ‏f t  32 Schema Theorem  Theorem E m s, t  1   d  uˆ s, t   o s  m s, t  1- pc s  1- pm  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  û 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” 33 خالصه یک Schemaاطالعات مفید و امید بخش موجود در جمعیت را کد میکند. از آنجائیکه همواره رشته هائی که سازگارترند شانس بیشتری برای انتخاب شدن دارند ،بتدریج مثالهای بیشتری به بهترین Schemaها اختصاص می یابند. عمل crossoverباعث قطع رشته ها در نقاط تصادفی میشود .با این وجود در صورتیکه اینکار باعث قطع Schemaنشده باشد آنرا تغییر نخواهد داد.در حالت کلی Schemaهای با طول کوتاه کمتر تغییر میکنند. عمل mutaionدر حالت کلی باعث تغییرات موثر در Schemaنمیگردد. 34 ‏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 بجای کد کردن پارامترها مجموعه آنها را کد میکند GA بجای جستجو برای یک نقطه بدنبال جمعیتی از نقاط میگردد. GA بجای استفاده از مشتق و یا سایر اطالعات کمکی مستقیما ازاطالعات موجود در نتیجه بهره میگیرد. GA بجای قوانین قطعی از قوانین احتمال برای تغییر استفاده میکند. 35 مثالی از کاربرد الگوریتم ژنتیک بهینه‌سازی چینش حروف فارسی بر روی صفحه‌کلید با استفاده از الگوریتم‌های ژنتیکی 36 مقدمه بدست آوردن چینش بهینه حروف فارسی بر روی صفحه‌کلید در درازمدت برای کسانی که با تایپ کردن متون فارسی درگیر هستند ,بسیار مفید خواهد بود. یک الگوریتم تکاملی می‌تواند با توجه به یک تابع تناسب که میزان راحتی تایپ کردن متون فارسی را برای یک چینش ارائه می‌دهد ,در فضای چینش‌های حروف فارسی بر روی صفحه‌کلید جستجو کرده و چینش بهینه را بدست آورد. 37 چینش کنونی حروف فارسی بر روی صفحه‌کلید 38 مساله در این مساله هندسه صفحه‌کلید ثابت است و ما می‌خواهیم که تعداد 33نشانه که متشکل از 32حرف الفبای فارسی بعالوه حرف همزه "ء" است را بر روی سه ردیف صفحه‌کلید که به ترتیب دارای ,11 ,12و 10 کلید هستند ,قرار دهیم. هدف این مساله بدست آوردن چینشی از این نشانه‌ها بر روی این کلید‌ها است ,به طوری که این چینش طوری باشد که کاربر هنگام استفاده از صفحه‌کلید برای تایپ حروف فارسی ,احساس راحتی بیشتری نسبت به کار با بقیه چینش‌ها داشته باشد. 39 الگوریتم ژنتیک برای حل مساله از یک الگوریتم ژنتیک استفاده شده است. تابع تناسب موجود در این الگوریتم ژنتیک ,میزان راحتی یا سختی استفاده از یک چینش را محاسبه می‌کند. در هر نسل ,عملگرهای ژنتیکی بر روی جمعیت موجود که چینش‌های مختلفی از حروف فارسی بر روی صفحه‌کلید هستند, اعمال می‌شوند و جامعه به سمتی سوق داده می‌شود که مقدار تابع تناسب به ازای اعضای آن به کمینه مقدار خود برسند. میزان تناسب هر عضو از جامعه که در واقع یک چینش حروف فارسیبررویصفحهکلید هستند ,با اعمال تابع تناسب بر متنی فارسی برروی که از مطالب چند سایت خبری فارسی زبان تهیه شده است ,به دستمیآید. دست 40 جمعیت اعضای جمعیت جایگشت‌های مختلف حروف فارسی روی صفحه‌کلید هستند .هر عضو جمعیت را می‌توان به صورت برداری از حروف فارسی در نظر گرفت که هر اندیس آن متناظر با یک کلید از صفحه‌ کلید است. مثًال هر بردار با طول 33که شامل حروف فارسی بعالوه حرف همزه "ء" باشد را میتوان به عنوان یک کروموزوم (یک عضو از جمعیت) در نظر گرفت که حرف iام از این بردار ,متناظر با کلیدی از صفحه‌کلید است که برچسب شمارة iبر روی آن زده شده است. 41 تعداد چینش‌های مختلف !33 تابع تناسب تعیین راحتی و سختی کار کردن با چینش حروف بر روی صفحه‌کلید یک مساله پیچیده ارگونومیک است. نورمن و رومل‌هارت چهار هدف را برای طراحی کارای یک صفحه‌کلید ارائه کرده‌اند: ‏ ‏ .1 .2 .3 .4 42 برابری کاری که دو دست انجام می‌دهند؛ بیشترین تایپ حروف به صورت متناوب با دو دست؛ کمترین تکرار تایپ دو حرف متوالی با یک انگشت؛ و بیشترین تایپ حروف بر روی کلیدهای پایه‌ای (کلیدهای ردیف وسط). تابع تناسب . برای دو هدف اول می‌توان فاکتور اندازه‌گیری زیر را معرفی‌کرد: :Chand هزینه مربوط به استفاده از یک دست برای تایپ کردن دو حرف پشت‌ سر هم. برای هدف سوم ,فاکتور انداز‌ه‌گیری زیر معرفی می‌شود: :Cfinger هزینه مربوط به استفاده از یک انگشت برای تایپ کردن دو حرف پشت‌ سر هم. :Cergonomic هزینه مربوط به تایپ کردن یک حرف با توجه به موقعیت آن حرف بر روی صفحه‌کلید. 43 تابع تناسب تابع تناسب برای هر کروموزوم از مجموع این سه فاکتور برای تمامی حروفی که در متن مورد استفاده برای آزمایش وجود دارند ,بدست می‌آید: ]) Fitness (layout)    [C hand (l j , l j  1 )  C finger (l j , l j  1 )  Cergonomic (l j ‏w i W l j wi Wمجموعه تمامی کلمات موجود در متن مورد استفاده برای آزمایش است؛ wi کلمه iام از مجموعه Wاست؛ lj حرف jام از کلمه wiاست؛ 44 عملگرهای ژنتیکی در اینجا تنها از عملگر جهش استفاده شده است. دلیل عدم استفاده از عملگر دورگه این است که ساختار اعضای جمعیت طوری است که ترکیب کردن دو کروموزوم والد هزینة زمانی باالیی دارد. عملگر جهش را به دو صورت برای اعضای مختلف جامعه به کار می‌بریم .در این مساله یک جامعه نخبگان انتخاب می‌کنیم که اعضای آن تراز اول جمعیت از دید تابع تناسب را تشکیل می‌دهند % . عملگر جهش برای هر عضو از جامعة نخبگان ,تنها محتویات چهار زوج ژن را به صورت تصادفی جابه‌جا می‌کند .در حالیکه برای افراد عادی جامعه این تعداد به 12جابه‌جایی افزایش می‌یابد. 45 کارایی الگوریتم ژنتیک با پارامترهای زیر اجرا کردیم: تعداد اعضای جمعیت 100کروموزوم که در نسل تولیدشدهاند؛ تولید اول به صورت تصادفی ‏ درصدتشکیلدهنده جامعه نخبگان است, درصد ‏ %10کل جمعیت ؛ تعداد اعضایی که به صورت مستقیم و بدون اینکه عمگرهای ژنتیکی بر روی آن اعمال شود ,به نسل بعدیمیروند 3 ,عضو؛ بعدی ‏ وتعدادکلنسلها 500نسل. عدادکل وت 46 کارایی 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 ‏generation number 47 نمودارهایتناسباعضایجامعهدرطینسلهایمختلفمنحنیهای نشان نمودارهای تناس ب اعض ای جامعه در ط ی نس لهای مختلف . داده شده به ترتیب از باال به پایین ,متوسط مقادیر تناسب همه اعضای جامعه ,متوسط مقادیر تناسب جامعه نخبگان ,و بهترین تناسب هستند. بهترین چینش بهترین چینشی که در نهایت این الگوریتم ژنتیک برایحروففارسیارائهدادهزینهاش با توجه به د ئهدا, را برای حروف فارسی ا تابع تناسب 815/0 ,هزینه چینش کنونی حروف فارسی است . 48 مدلهای تکامل در سیستمهای طبیعی هر موجود زنده در طول زندگی خود یاد میگیرد که با شرائط سازگاری نماید .به همین ترتیب نسل های مختلف یک نمونه در طول زمان سازگاری های مختلفی را کسب میکنند: سوال: رابطه بین یادگیری یک موجود در طول زندگی شخصی و یادگیری نسل های یک نمونه در طول زمان چیست؟ 49 Lamarckian evolution Lamarck دانشمند قرن نوزدهم فرضیه ای ارائه کرده که طبق آن تجربیات یک موجود زنده در ترکیب ژنتیکی فرزندان آن تاثیر میگذارد. برای مثال موجودی که یاد گرفته از غذای سمی پرهیز کند این ویژگی را بصورت ژنتیکی به فرزندان خود منتقل مینماید تا آنها دیگر مجبور به یادگیری این پدیده نباشند. اما شواهد تجربی این نظر را تائید نمیکنند: یعنی تجربیات فردی هیچ تاثیری در ترکیب ژنتیکی فرزندان ندارد. 50 Baldwin Effect نظریه دیگری وجود دارد که تاثیر یادگیری را بر تکامل توضیح میدهد .این نظریه که اثر Baldwinنامیده میشود بر مبنای مشاهدات زیر استوار است: اگر موجودی از طرف محیط متغیری تحت فشار قرار گرفته باشد ،افرادی که توانائی یادگیری نحوه برخورد با شرایط را داشته باشند شانس بیشتری برای بقا دارند. موجوداتی که تحت شرایط جدید باقی میمانند جمعیتی با توانائی یادگیری را تشکیل میدهند که فرایندهای تکاملی در آنها سریعتر رخ میدهد و باعث میشود تا نسلی بوجود بیاید که نیازی به یادگیری مواجهه با شرایط جدید را نداشته باشند. 51 اجرای موازی الگوریتم های ژنتیک الگوریتم های ژنتیک از قابلیت خوبی برای پیاده سازی بصورت موازی برخوردارد هستند. در یک روش پیاده سازی موازی ،جمعیت به گروههای کوچکتری با نام demesتقسیم شده و هرکدام در یک گره محاسباتی مورد پردازش قرار میگیرند. در هر گره یک الگوریتم استاندارد GAبر روی demeاجرا میشود. انتقال بین گره ها از طریق پدیده migrationصورت میپذیرد. 52 Evolving Neural Networks از GAبرای تکامل جنبه های مختلف NNاستفاده زیادی بعمل آمده است.از جمله :وزنها ،ساختارو تابع یادگیری. استفاده از GAبرای یادگیری وزنهای یک شبکه عصبی میتواند بسیار سریعتر از روش استاندارد back propagationعمل نماید. استفاده از GAبرای یادگیری ساختار شبکه عصبی مشکلتر میباشد .برای شبکه های کوچک با استفاده از یک ماتریس مشخص میشود که چه نرونی به چه نرونهای دیگری متصل است.آنگاه این ماتریس به ژن های الگوریتم ژنتیک تبدیل و ترکیبات مختلف آن بررسی میگردد. برای بدست آوردن تابع یادگیری یک شبکه عصبی راه حلهائی نظیر استفاده از GPمورد استفاده قرار گرفته اما عموما این روشها بسیار کند عمل کرده اند. 53 مراجع [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, SpringerVerlag, New York, 1983. [7] J. 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. 54 Genetic Programming GP تکنیکی است که کامپیوترها را قادر میسازد تا به حل مسائل بپردازند بدون آنکه بطور صریح برای آن برنامه ریزی شده باشند. GP روشی از الگوریتمهای تکاملی است که در آن هرعضو جمعیت یک برنامه کامپیوتری است. برنامه ها اغلب بتوسط یک درخت نمایش داده شده و اجرای برنامه برابر است با parsکردن درخت. )F = sin(x) + sqrt( x^2 + y + ‏Sin ‏sqrt + ‏y ^ 2 55 ‏x ‏x نمایش برنامه ها برای استفاده از GPدر یک زمینه خاص، میبایست توابع پایه ای که در آن زمینه مورد نیاز هستند نظیر sin, cos, sqrt, +, -, etcتوسط کاربر تعریف شوند همچنین ترمینالها نظیر متغیرها و ثوابت نیز باید مشخص شوند آنگاه الگوریتم GPدر فضای بسیار بزرگ برنامه هائی که توسط این مقادیر اولیه قابل بیان هستند یک عمل جستجوی تکاملی را انجام خوهد داد. 56 اپراتور crossoverبرای GP اپراتور crossover :شاخه هائی از یک درخت والد با شاخه هائی از درخت والد دیگر بطور تصادفی عوض میشوند + + ^ ^ ‏y ^ ‏Sin 2 2 + ‏x ‏y ‏x ‏Sin ‏x ‏x فرزندان والدین ‏Crossover + ‏sqrt + ‏y 57 ‏sqrt ‏x ‏Sin + ‏x + 2 ‏Sin + ‏y ‏x ^ 2 ‏x مثال در کتاب مثالی از Kozaمطرح شده که در آن الگوریتمی یاد گرفته میشود که بتواند بلوک ها را در یک ستون روی هم بچیند هدف مسئله این است که بلوک ها طوری روی هم چیده شوند که کلمه universalرا بسازند N ‏I 58 ‏A ‏L ‏U ‏V ‏E ‏S ‏R مثال محدودیت :در هر مرحله فقط میتوان یک بلوک را جابجا نمود .در نتیجه تنها حرکت های ممکن عبارتند از: ‏ ‏ بلوک آخر ستون را میتوان روی میز قرار داد و یا اینکه یک بلوک را از میز به انتهای ستون منتقل نمود. توابع اولیه: ‏CS (current stack) : نام بلوک موجود در انتهای ستون را بر میگرداند ) Fبرای حالتی که بلوکی وجود ندارد( TP (top correct block) نام آخرین بلوکی را که همراه با بلوک های زیرینش ترتیب صحیح مورد نظر را دارند ،برمیگرداند NN (next necessary) نام بلوکی که باید در باالی TPقرار گیرد تا ترتیب universalدرست دربیاید. 59 مثال سایر توابع اولیه: ‏ ‏ ‏ ‏ ‏ ‏ 60 (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مثال که هر یک در برگیرنده آرایش اولیه متفاوتی برای بلوک ها بودند تدارک دیده شده بود. تابع fitnessیک برنامه برابر است با تعداد مثالهائی که برنامه قادر به حل آن است. برنامه با جمعیت اولیه ای برابر با 300برنامه تصادفی شروع بکار نموده و پس از تولید 10نسل قادر میشود تا برنامه ای پیدا نماید که تمامی 166مثال را حل نماید: ) ))(EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT NN 61 مثال :طراحی فیلتر صورت مسئله :برنامه ای که یک مدار ساده اولیه رابه مدار پیچیده مورد نیاز تبدیل نماید. توابع اولیه: تابعی برای اضافه کردن قطعات و سیم بندی های مدار تابعی برای حذف کردن قطعات و سیم بندی های مدار تابع fitnessشبیه سازی مدار بدست آمده توسط نرم افزار SPICEبرای مشخص نمودن میزان تطبیق آن با طرح مورد نظر .خطای مداربرای 101فرکانس مختلف مورد بررسی قرار میگرفت. جمعیت اولیه : 640000 نرخ crossover : 89درصد نرخ mutation : 1درصد 62 مثال :طراحی فیلتر سیستم برروی یک کامپیوتر موازی با 64گره مورد آزمایش قرار گرفت. برای نسل اولیه ای که بصورت تصادفی ایجاد شدند در %98مواقع حتی امکان شبیه سازی وجود نداشت. این نرخ بتدریج کاهش یافته و پس از تولید 137 نسل مداری حاصل شد که با مشخصات مورد نظر میکرد.موارد کارائی الگوریتم GPبستگی به در اغلب صدق نحوه نمایش و همچنین تابع fitnessدارد. 63