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

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

اسلاید 1: 1الگوریتم های ژنتیکInstructor : Saeed Shiry& Mitchell Ch. 9

اسلاید 2: 2الگوریتم ژنتیکالگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است.این روش در سال 1970 توسط John Holland معرفی گردیداین روشها با نام Evolutionary Algorithms نیز خوانده میشوند.

اسلاید 3: 3ایده کلییک GA برای حل یک مسئله مجموعه بسیار بزرگی از راه حلهای ممکن را تولید میکند.هر یک از این راه حلها با استفاده از یک “ تابع تناسب” مورد ارزیابی قرار میگیرد.آنگاه تعدادی از بهترین راه حلها باعث تولید راه حلهای جدیدی میشوند. که اینکار باعث تکامل راه حلها میگردد.بدین ترتیب فضای جستجو در جهتی تکامل پیدا میکند که به راه حل مطلوب برسددر صورت انتخاب صحیح پارامترها، این روش میتواند بسیار موثر عمل نماید.

اسلاید 4: 4فضای فرضیهالگوریتم ژنتیک بجای جستجوی فرضیه های general-to specific و یا simple to complex فرضیه ها ی جدید را با تغییر و ترکیب متوالی اجزا بهترین فرضیه های موجود بدست میاورد.در هرمرحله مجموعه ای از فرضیه ها که جمعیت (population) نامیده میشوند از طریق جایگزینی بخشی از جمعیت فعلی با فرزندانی که از بهترین فرضیه های موجود حاصل شده اند بدست میآید.

اسلاید 5: 5ویژگیهاالگوریتم های ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند میتواند بکار گرفته شود.همچنین در مسایلی با فضای فرضیه پیچیده که تاثیر اجزا آن در فرضیه کلی ناشناخته باشند میتوان از GA برای جستجو استفاده نمود.برای discrete optimizationبسیار مورد استفاده قرار میگیرد.الگوریتم های ژنتیک را میتوان براحتی بصورت موازی اجرا نمود از اینرو میتوان کامپیوترهای ارزان قیمت تری را بصورت موازی مورد استفاده قرار داد.امکان به تله افتادن این الگوریتم در مینیمم محلی کمتر از سایر روشهاست.از لحاظ محاسباتی پرهزینه هستند.تضمینی برای رسیدن به جواب بهینه وجود ندارد.

اسلاید 6: 6Parallelization of Genetic Programmingدر سال 1999 شرکت Genetic Programming Inc. یک کامپیوتر موازی با 1000 گره هر یک شامل کامپیوتر های P2, 350 MHZ برای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد.

اسلاید 7: 7کاربر دهاکاربرد الگوریتم های ژنتیک بسیار زیاد میباشدoptimization, automatic programming, machine learning, economics, operations research, ecology, studies of evolution and learning, and social systems

اسلاید 8: 8زیر شاخه های EA روش های EA به دو نوع مرتبط به هم ولی مجزا دسته بندی میشوند:Genetic Algorithms (GAs)در این روش راه حل یک مسئله بصورت یک bit string نشان داده میشود. Genetic Programming (GP)این روش به تولید expression trees که در زبانهای برنامه نویسی مثل lisp مورد استفاده هستند میپردازد بدین ترتیب میتوان برنامه هائی ساخت که قابل اجرا باشند.

اسلاید 9: 9الگوریتم های ژنتیکروش متداول پیاده سازی الگوریتم ژنتیک بدین ترتیب است که:مجموعه ای از فرضیه ها که population نامیده میشود تولید وبطور متناوب با فرضیه های جدیدی جایگزین میگردد.در هر بار تکرارتمامی فرضیه ها با استفاده از یک تابع تناسب یا Fitness مورد ارزیابی قرار داده میشوند. آنگاه تعدادی از بهترین فرضیه ها با استفاده از یک تابع احتمال انتخاب شده و جمعیت جدید را تشکیل میدهند.تعدادی از این فرضیه های انتخاب شده به همان صورت مورد استفاده واقع شده و مابقی با استفاده از اپراتورهای ژنتیکی نظیر Crossover و Mutationبرای تولید فرزندان بکار میروند.

اسلاید 10: 10پارامترهای GA یک الگوریتم GA دارای پارامترهای زیر است:GA(Fitness,Fitness_threshold,p,r,m): Fitnessتابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد: Fitness_threshold مقدار آستانه که شرط پایان را معین میکند: p تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند:r در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover جایگزین میشوند:m نرخ mutation

اسلاید 11: 11الگورتیم: Initializeجمعیت را با تعداد p فرضیه بطور تصادفی مقدار دهی اولیه کنید.: Evaluateبرای هر فرضیه h در p مقدار تابع Fitness(h) را محاسبه نمائید.تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد کنید.فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.

اسلاید 12: 12مراحل ایجاد یک جمعیت جدید بصورت زیر است:: selectتعداد(1-r)p فرضیه از میان P انتخاب و بهPs اضافه کنید. احتمال انتخاب یک فرضیهhi از میانP عبارت است از:P(hi) = Fitness (hi) / Σj Fitness (hj): Crossoverبا استفاده از احتمال بدست آمده توسط رابطه فوق، تعداد(rp)/2 زوج فرضیه از میان P انتخاب و با استفاده از اپراتورCrossover دو فرزند از آنان ایجاد کنید. فرزندان را به Ps اضافه کنید.: Mutateتعداد m درصد از اعضا Ps را با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنیدP Ps :Updateبرای هر فرضیه h در P مقدار تابع Fitness را محاسبه کنیدنحوه ایجاد جمعیت جدیدهر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است. این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد.

اسلاید 13: 13نمایش فرضیه هادر الگوریتم ژنتیک معمولا فرضیه ها بصورت رشته ای از بیت ها نشان داده میشوند تا اعمال اپراتورهای ژنتیکی برروی آنها ساده تر باشد.: Phenotype به مقادیر یا راه حلهای واقعی گفته میشود.: Genotypeبه مقادیر انکد شده یا کروموزم ها گفته میشود که مورد استفاده GA قرار میگیرند.باید راهی برای تبدیل این دو نحوه نمایش به یکدیگر بدست آورده شود.Genotype space = {0,1}LPhenotype spaceEncoding (representation)Decoding(inverse representation)0111010010100010011001001010010001

اسلاید 14: 14مثال: نمایش قوانین If-then rules برای نمایش مقادیر یک ویژگی نظیر Outlook که دارای سه مقدار Sunny, Overcast ,Rain است میتوان از رشته ای با طول 3 بیت استفاده نمود100 -> Outlook = Sunny011-> Outlook = Overcast  Rainبرای نمایش تر کیب ویژگی ها رشته بیت های هر یک را پشت سر هم قرار میدهیم:به همین ترتیب کل یک قانون if- then را میتوان با پشت سر هم قرار دادن بیت های قسمت های شرط و نتیجه ایجاد نمود:Outlook Wind011 10IF Wind = Strong THEN PlayTennis = NoOutlook WindPlayTennis111 10 0 bit string: 111100

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

اسلاید 16: 16اپراتورهای ژنتیکی Crossover :اپراتور Crossover با استفاده از دو رشته والد دو رشته فرزند بوجود میآورد. برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی میشود. انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشودsingle-point crossoverTwo-point crossoverUniform crossoverبرای تعیین محل بیتهای کپی شونده از یک رشته به نام Crossover Mask استفاده میشود.

اسلاید 17: 17Single-point crossoverیک نقطه تصادفی در طول رشته انتخاب میشود. والدین در این نقطه به دوقسمت میشوند.هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید.10111000100Crossover Mask: 11111000000100001010101011100010010101010000ParentsChildren

اسلاید 18: 18روشهای دیگر CrossoverTwo-point crossoverUniform crossover000100Crossover Mask: 0011111000000011100101101000000100101000001000001111010000001000010110100Crossover Mask: 10011010011بیتها بصورت یکنواخت از والدین انتخاب میشوند10111000100000010110101011100010000001011010ParentsParentsChildrenChildren

اسلاید 19: 19اپراتورهای ژنتیکی Mutation : اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد.با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.معمولا mutation بعد از انجام crossover اعمال میشود.ParentChild101110001001011100010001

اسلاید 20: 20این سوال ها سالها مطرح بوده است:کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده:بستگی به صورت مسئله دارددر حالت کلی بهتر است از هر دو استفاده شودهر کدام نقش مخصوص خود را داردمیتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover استفاده کند کار نخواهد کردCrossover OR mutation?

اسلاید 21: 21Crossover OR mutation?Crossover خاصیت جستجوگرانه و یا explorative دارد. میتواندبا انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید. Mutationخاصیت گسترشی و یا exploitive دارد. میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد. Crossoveاطلاعات والدین را ترکیب میکند درحالیکه mutation میتواند اطلاعات جدیدی اضافه نماید. برای رسیدن به یک پاسخ بهینه یک خوش شانسی در mutation لازم است.

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

اسلاید 23: 23انتخاب فرضیه هاRoulette Wheel selectionدر روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness آن به fitness بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.P(hi) = Fitness (hi) / Σj Fitness (hj)fitness(A) = 3fitness(B) = 1fitness(C) = 2AC1/6 = 17%3/6 = 50%B2/6 = 33%روشهای دیگر:tournament selectionrank selection

اسلاید 24: 24نحوه جستجو در فضای فرضیهروش جستجوی GA با روشهای دیگر مثل شبکه های عصبی تفاوت دارد:در شبکه عصبی روش Gradient descent بصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه GA ممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GA در مینیمم محلی کاهش می یابد.با این وجود GA با مشکل دیگری روبروست که crowding نامیده میشود.

اسلاید 25: 25Crowdingcrowding پدیده ای است که در آن عضوی که سازگاری بسیاربیشتری از بقیه افراد جمعیت دارد بطور مرتب تولید نسل کرده و با تولید اعضای مشابه درصد عمده ای از جمعیت را اشغال میکند.اینکار باعث کاهش پراکندگی جمعیت شده و سرعت GA را کم میکند.F(X)X

اسلاید 26: 26راه حل رفع مشکل Crowding استفاده از ranking برای انتخاب نمونه ها: با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند مقدار این برتری نشان داده نخواهد شد. : Fitness sharing مقدار Fitness یک عضودر صورتیکه اعضا مشابهی در جمعیت وجود داشته باشند کاهش می یابد.

اسلاید 27: 27چرا GA کار میکند؟سئوالی که ممکن است برای تازه واردین به روشهای ژنتیکی ایجاد شود این است که آیا این روش واقعا میتواند کار مفیدی انجام دهد؟

اسلاید 28: 28ارزیابی جمعیت و قضیه Schema آیا میتوان تکامل در جمعیت در طی زمان را بصورت ریاضی مدل نمود؟قضیه Schema میتواند مشخصه پدیده تکامل در GA را بیان نماید.یک Schema مجموعه ای از رشته بیت ها را توصیف میکند.یک Schema هر رشته ای از 0 و1و* است. مثل 0*10 که * حالت dont care است.یک رشته بیت را میتوان نماینده هر یک از Schemaهای متفاوتی دانست که با آن تطابق دارند. مثلا 0010 را میتوان نماینده 24 Schema مختلف دانست00**,0*10,**** : وغیره

اسلاید 29: 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)مقدار متوسط fitness برای تمامی فرضیه ها

اسلاید 30: 30قضیه Schema اگر عضوی از این جمعیت انتخاب شود احتمال اینکه این عضو نماینده S باشد برابر است با:که در آن مقدار u(s,t) برابر است با مقدار میانگین fitness اعضای s از اینرو مقدار مورد انتظار برای نمونه هائی از s که از n مرحله انتخاب مستقل حاصل خواهند شد برابر است با:

اسلاید 31: 31قضیه Schema رابطه فوق به این معناست که تعداد Schema های مورد انتظار در لحظه t+1 متناسب با مقدار میانگین u(s,t) بوده و با مقدار fitness سایر اعضا نسبت عکس دارد.برای بدست آوردن رابطه فوق فقط اثر مرحله انتخاب نمونه ها در نظر گرفته شده است. با در نظر گرفتن اثر crossover و Mutation به رابطه زیر خواهیم رسید:

اسلاید 32: 32Schema Theorem Theoremm(s, t) number of instances of schema s in population at time t  average fitness of population at time t  average fitness of instances of schema s at time tpc  probability of single point crossover operatorpm probability of mutation operatorl length of individual bit stringso(s) number of defined (non “*”) bits in sd(s) distance between rightmost, leftmost defined bits in sIntuitive Meaning“The expected number of instances of a schema in the population tends toward its relative fitness”

اسلاید 33: 33خلاصهیک Schema اطلاعات مفید و امید بخش موجود در جمعیت را کد میکند.از آنجائیکه همواره رشته هائی که سازگارترند شانس بیشتری برای انتخاب شدن دارند، بتدریج مثالهای بیشتری به بهترین Schema ها اختصاص می یابند.عمل crossover باعث قطع رشته ها در نقاط تصادفی میشود. با این وجود در صورتیکه اینکار باعث قطع Schema نشده باشد آنرا تغییر نخواهد داد.در حالت کلی Schema های با طول کوتاه کمتر تغییر میکنند.عمل 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

اسلاید 34: 34تفاوت GA با سایر روشهای جستجوGA بجای کد کردن پارامترها مجموعه آنها را کد میکندGA بجای جستجو برای یک نقطه بدنبال جمعیتی از نقاط میگردد.GA بجای استفاده از مشتق و یا سایر اطلاعات کمکی مستقیما ازاطلاعات موجود در نتیجه بهره میگیرد.GA بجای قوانین قطعی از قوانین احتمال برای تغییر استفاده میکند.

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

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

اسلاید 37: 37چینش کنونی حروف فارسی بر روی صفحه‌کلید

اسلاید 38: 38مساله در این مساله هندسه صفحه‌کلید ثابت است و ما می‌خواهیم که تعداد 33 نشانه که متشکل از 32 حرف الفبای فارسی بعلاوه حرف همزه ء است را بر روی سه ردیف صفحه‌کلید که به ترتیب دارای 12, 11, و 10 کلید هستند, قرار دهیم. هدف این مساله بدست آوردن چینشی از این نشانه‌ها بر روی این کلید‌ها است, به طوری که این چینش طوری باشد که کاربر هنگام استفاده از صفحه ‌کلید برای تایپ حروف فارسی, احساس راحتی بیشتری نسبت به کار با بقیه چینش‌ها داشته باشد.

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

اسلاید 40: 40جمعیت اعضای جمعیت جایگشت‌های مختلف حروف فارسی روی صفحه‌کلید هستند. هر عضو جمعیت را می‌توان به صورت برداری از حروف فارسی در نظر گرفت که هر اندیس آن متناظر با یک کلید از صفحه‌ کلید است. مثلاً هر بردار با طول33 که شامل حروف فارسی بعلاوه حرف همزه ء باشد را میتوان به عنوان یک کروموزوم (یک عضو از جمعیت) در نظر گرفت که حرف iام از این بردار, متناظر با کلیدی از صفحه‌کلید است که برچسب شمارة i بر روی آن زده شده است.تعداد چینش‌های مختلف !33

اسلاید 41: 41تابع تناسب تعیین راحتی و سختی کار کردن با چینش حروف بر روی صفحه‌کلید یک مساله پیچیده ارگونومیک است. نورمن و رومل‌هارت چهار هدف را برای طراحی کارای یک صفحه‌کلید ارائه کرده‌اند: برابری کاری که دو دست انجام می‌دهند؛ بیشترین تایپ حروف به صورت متناوب با دو دست؛ کمترین تکرار تایپ دو حرف متوالی با یک انگشت؛ و بیشترین تایپ حروف بر روی کلیدهای پایه‌ای (کلیدهای ردیف وسط).

اسلاید 42: 42تابع تناسب. برای دو هدف اول می‌توان فاکتور اندازه‌گیری زیر را معرفی‌کرد:Chand: هزینه مربوط به استفاده از یک دست برای تایپ کردن دو حرف پشت‌ سر هم.برای هدف سوم, فاکتور انداز‌ه‌گیری زیر معرفی می‌شود:Cfinger: هزینه مربوط به استفاده از یک انگشت برای تایپ کردن دو حرف پشت‌ سر هم.Cergonomic: هزینه مربوط به تایپ کردن یک حرف با توجه به موقعیت آن حرف بر روی صفحه‌کلید.

اسلاید 43: 43تابع تناسبتابع تناسب برای هر کروموزوم از مجموع این سه فاکتور برای تمامی حروفی که در متن مورد استفاده برای آزمایش وجود دارند, بدست می‌آید:W مجموعه تمامی کلمات موجود در متن مورد استفاده برای آزمایش است؛ wi کلمه iام از مجموعه W است؛ lj حرف jام از کلمه wi است؛

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

اسلاید 45: 45کارایی الگوریتم ژنتیک با پارامترهای زیر اجرا کردیم: تعداد اعضای جمعیت 100 کروموزوم که در نسل اول به صورت تصادفی تولید شده‏اند؛ درصد تشکیل‏دهنده جامعه نخبگان است, 10% کل جمعیت ؛ تعداد اعضایی که به صورت مستقیم و بدون اینکه عمگرهای ژنتیکی بر روی آن اعمال شود, به نسل بعدی می‏روند, 3 عضو؛ و تعداد کل نسل‏ها 500 نسل.

اسلاید 46: 46کارایی نمودارهای تناسب اعضای جامعه در طی نسل‏های مختلف. منحنی‏های نشان‏ داده شده به ترتیب از بالا به پایین, متوسط مقادیر تناسب همه اعضای جامعه, متوسط مقادیر تناسب جامعه نخبگان, و بهترین تناسب هستند.

اسلاید 47: 47بهترین چینشبهترین چینشی که در نهایت این الگوریتم ژنتیک برای حروف فارسی ارائه داد, هزینه‏اش با توجه به تابع تناسب, 815/0 هزینه چینش کنونی حروف فارسی است .

اسلاید 48: 48مدلهای تکاملدر سیستمهای طبیعی هر موجود زنده در طول زندگی خود یاد میگیرد که با شرائط سازگاری نماید. به همین ترتیب نسل های مختلف یک نمونه در طول زمان سازگاری های مختلفی را کسب میکنند:سوال:رابطه بین یادگیری یک موجود در طول زندگی شخصی و یادگیری نسل های یک نمونه در طول زمان چیست؟

اسلاید 49: 49Lamarckian evolutionLamarck دانشمند قرن نوزدهم فرضیه ای ارائه کرده که طبق آن تجربیات یک موجود زنده در ترکیب ژنتیکی فرزندان آن تاثیر میگذارد.برای مثال موجودی که یاد گرفته از غذای سمی پرهیز کند این ویژگی را بصورت ژنتیکی به فرزندان خود منتقل مینماید تا آنها دیگر مجبور به یادگیری این پدیده نباشند.اما شواهد تجربی این نظر را تائید نمیکنند: یعنی تجربیات فردی هیچ تاثیری در ترکیب ژنتیکی فرزندان ندارد.

اسلاید 50: 50Baldwin Effectنظریه دیگری وجود دارد که تاثیر یادگیری را بر تکامل توضیح میدهد. این نظریه که اثر Baldwin نامیده میشود بر مبنای مشاهدات زیر استوار است:اگر موجودی از طرف محیط متغیری تحت فشار قرار گرفته باشد، افرادی که توانائی یادگیری نحوه برخورد با شرایط را داشته باشند شانس بیشتری برای بقا دارند.موجوداتی که تحت شرایط جدید باقی میمانند جمعیتی با توانائی یادگیری را تشکیل میدهند که فرایندهای تکاملی در آنها سریعتر رخ میدهد و باعث میشود تا نسلی بوجود بیاید که نیازی به یادگیری مواجهه با شرایط جدید را نداشته باشند.

اسلاید 51: 51اجرای موازی الگوریتم های ژنتیکالگوریتم های ژنتیک از قابلیت خوبی برای پیاده سازی بصورت موازی برخوردارد هستند.در یک روش پیاده سازی موازی، جمعیت به گروههای کوچکتری با نام demes تقسیم شده و هرکدام در یک گره محاسباتی مورد پردازش قرار میگیرند. در هر گره یک الگوریتم استاندارد GA بر روی deme اجرا میشود. انتقال بین گره ها از طریق پدیده migration صورت میپذیرد.

اسلاید 52: 52Evolving Neural Networksاز GA برای تکامل جنبه های مختلف NN استفاده زیادی بعمل آمده است.از جمله : وزنها، ساختارو تابع یادگیری.استفاده از GA برای یادگیری وزنهای یک شبکه عصبی میتواند بسیار سریعتر از روش استاندارد back propagation عمل نماید.استفاده از GA برای یادگیری ساختار شبکه عصبی مشکلتر میباشد. برای شبکه های کوچک با استفاده از یک ماتریس مشخص میشود که چه نرونی به چه نرونهای دیگری متصل است.آنگاه این ماتریس به ژن های الگوریتم ژنتیک تبدیل و ترکیبات مختلف آن بررسی میگردد.برای بدست آوردن تابع یادگیری یک شبکه عصبی راه حلهائی نظیر استفاده از GP مورد استفاده قرار گرفته اما عموما این روشها بسیار کند عمل کرده اند.

اسلاید 53: 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, Springer-Verlag, 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: 54Genetic ProgrammingGP تکنیکی است که کامپیوترها را قادر میسازد تا به حل مسائل بپردازند بدون آنکه بطور صریح برای آن برنامه ریزی شده باشند.GP روشی از الگوریتمهای تکاملی است که در آن هرعضو جمعیت یک برنامه کامپیوتری است.برنامه ها اغلب بتوسط یک درخت نمایش داده شده و اجرای برنامه برابر است با pars کردن درخت.+Sin sqrtx + ^ y x 2F = sin(x) + sqrt( x^2 + y)

اسلاید 55: 55نمایش برنامه هابرای استفاده از GP در یک زمینه خاص، میبایست توابع پایه ای که در آن زمینه مورد نیاز هستند نظیر sin, cos, sqrt, +, -, etc توسط کاربر تعریف شوندهمچنین ترمینالها نظیر متغیرها و ثوابت نیز باید مشخص شوندآنگاه الگوریتم GP در فضای بسیار بزرگ برنامه هائی که توسط این مقادیر اولیه قابل بیان هستند یک عمل جستجوی تکاملی را انجام خوهد داد.

اسلاید 56: 56اپراتور crossoverبرای GP اپراتور : crossover شاخه هائی از یک درخت والد با شاخه هائی از درخت والد دیگر بطور تصادفی عوض میشوند+Sin ^x + x y 2+Sin sqrtx + ^ y x 2+Sin ^x ^ x y 2+Sin sqrtx + + y x 2والدینفرزندانCrossover

اسلاید 57: 57مثالدر کتاب مثالی از Koza مطرح شده که در آن الگوریتمی یاد گرفته میشود که بتواند بلوک ها را در یک ستون روی هم بچیندهدف مسئله این است که بلوک ها طوری روی هم چیده شوند که کلمه universal را بسازندV U L A INESR

اسلاید 58: 58مثالمحدودیت: در هر مرحله فقط میتوان یک بلوک را جابجا نمود. در نتیجه تنها حرکت های ممکن عبارتند از: بلوک آخر ستون را میتوان روی میز قرار داد و یا اینکه یک بلوک را از میز به انتهای ستون منتقل نمود.توابع اولیه:: CS (current stack)نام بلوک موجود در انتهای ستون را بر میگرداند F ) برای حالتی که بلوکی وجود ندارد(TP (top correct block) نام آخرین بلوکی را که همراه با بلوک های زیرینش ترتیب صحیح مورد نظر را دارند، برمیگرداندNN (next necessary) نام بلوکی که باید در بالای TP قرار گیرد تا ترتیب universal درست دربیاید.

اسلاید 59: 59مثالسایر توابع اولیه:(MS x) move block x to stackاگر بلوک x روی میزباشد این اپراتور آنرا به بالای ستون منتقل میکند. درغیر اینصورت مقدار Fبرمیگرداند. (MT x) move block x to tableاگر بلوک x جائی روی ستون باشد این اپراتور بلوک بالای ستون را به میز منتقل میکند. درغیر اینصورت مقدار Fبرمیگرداند.(EQ x y) returns true if x = y. (NOT x) returns the complement of x. DU( x y) do x until expression y is true

اسلاید 60: 60مثالمقدار تابع fitness در این آزمایش تعداد 166 مثال که هر یک در برگیرنده آرایش اولیه متفاوتی برای بلوک ها بودند تدارک دیده شده بود. تابع fitness یک برنامه برابر است با تعداد مثالهائی که برنامه قادر به حل آن است.برنامه با جمعیت اولیه ای برابر با300 برنامه تصادفی شروع بکار نموده و پس از تولید 10 نسل قادر میشود تا برنامه ای پیدا نماید که تمامی 166 مثال را حل نماید:(EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT NN)) )

اسلاید 61: 61مثال : طراحی فیلترصورت مسئله: برنامه ای که یک مدار ساده اولیه رابه مدار پیچیده مورد نیاز تبدیل نماید.توابع اولیه:تابعی برای اضافه کردن قطعات و سیم بندی های مدارتابعی برای حذف کردن قطعات و سیم بندی های مدارتابع fitness شبیه سازی مدار بدست آمده توسط نرم افزار SPICE برای مشخص نمودن میزان تطبیق آن با طرح مورد نظر. خطای مداربرای 101 فرکانس مختلف مورد بررسی قرار میگرفت.جمعیت اولیه 640000 : نرخ 89 : crossoverدرصدنرخ 1 : mutation درصد

اسلاید 62: 62مثال : طراحی فیلترسیستم برروی یک کامپیوتر موازی با 64 گره مورد آزمایش قرار گرفت.برای نسل اولیه ای که بصورت تصادفی ایجاد شدند در 98% مواقع حتی امکان شبیه سازی وجود نداشت.این نرخ بتدریج کاهش یافته و پس از تولید 137 نسل مداری حاصل شد که با مشخصات مورد نظر صدق میکرد.در اغلب موارد کارائی الگوریتم GP بستگی به نحوه نمایش و همچنین تابع fitness دارد.