دانلود فایل

فروشگاه فایل و پاور پوینت آماده

پاور پوینت (اسلاید) الگوريتم هاي ژنتيک

پاور پوینت (اسلاید) الگوريتم هاي ژنتيک

 این پاور پوینت دارای 62 اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است


فایل پاور پوینت الگوريتم هاي ژنتيک  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.


در این پاور پوینت مباحث به زبان ساده و قابل درک برای همه گفته شده و برای ارائه آن هیچ مشکلی نخواهید داشت




محتواب برخی از اسلاید ها :


محتوای اسلاید 3 : 4

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

محتوای اسلاید 4 : 5

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

محتوای اسلاید 5 : 6

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

محتوای اسلاید 6 : 7

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

محتوای اسلاید 7 : 8

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

محتوای اسلاید 8 : 9

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

محتوای اسلاید 9 : 10

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

محتوای اسلاید 10 : 11

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

محتوای اسلاید 11 : 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 را محاسبه کنیدنحوه ایجاد جمعیت جدیدهر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است. این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد.

محتوای اسلاید 12 : 13

نمایش فرضیه هادر الگوریتم ژنتیک معمولا فرضیه ها بصورت رشته ای از بیت ها نشان داده میشوند تا اعمال اپراتورهای ژنتیکی برروی آنها ساده تر باشد.
: Phenotype به مقادیر یا راه حلهای واقعی گفته میشود.
: Genotypeبه مقادیر انکد شده یا کروموزم ها گفته میشود که مورد استفاده GA قرار میگیرند.
باید راهی برای تبدیل این دو نحوه نمایش به یکدیگر بدست آورده شود.

محتوای اسلاید 13 : 14

مثال: نمایش قوانین If-then rules برای نمایش مقادیر یک ویژگی نظیر Outlook که دارای سه مقدار Sunny, Overcast ,Rain است میتوان از رشته ای با طول 3 بیت استفاده نمود
100 -> Outlook = Sunny
011-> Outlook = Overcast  Rain
برای نمایش تر کیب ویژگی ها رشته بیت های هر یک را پشت سر هم قرار میدهیم:


به همین ترتیب کل یک قانون if- then را میتوان با پشت سر هم قرار دادن بیت های قسمت های شرط و نتیجه ایجاد نمود:
Outlook Wind
011 10IF Wind = Strong THEN PlayTennis = NoOutlook Wind PlayTennis
111 10 0 bit string: 111100

محتوای اسلاید 14 : 15

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

محتوای اسلاید 15 : 16

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

محتوای اسلاید 16 : 17

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

محتوای اسلاید 17 : 18

روشهای دیگر CrossoverTwo-point crossover




Uniform crossover

Crossover Mask: 00111110000Crossover Mask: 10011010011بیتها بصورت یکنواخت از والدین انتخاب میشوندParentsParentsChildrenChildren

محتوای اسلاید 18 : 19

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

ParentChild

محتوای اسلاید 19 : 20

این سوال ها سالها مطرح بوده است:
کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟

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

محتوای اسلاید 20 : 21

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

محتوای اسلاید 21 : 22

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

محتوای اسلاید 22 : 23

انتخاب فرضیه هاRoulette Wheel selection
در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness آن به fitness بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.
P(hi) = Fitness (hi) / Σj Fitness (hj)روشهای دیگر:
tournament selection
rank selection

محتوای اسلاید 23 : 24

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

محتوای اسلاید 24 : 25

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

محتوای اسلاید 25 : 26

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

محتوای اسلاید 26 : 27

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

محتوای اسلاید 27 : 28

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

محتوای اسلاید 28 : 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 برای تمامی فرضیه ها

محتوای اسلاید 29 : 30

قضیه Schema اگر عضوی از این جمعیت انتخاب شود احتمال اینکه این عضو نماینده S باشد برابر است با:

که در آن مقدار u(s,t) برابر است با مقدار میانگین fitness اعضای s

از اینرو مقدار مورد انتظار برای نمونه هائی از s که از n مرحله انتخاب مستقل حاصل خواهند شد برابر است با:

محتوای اسلاید 30 : 31

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

محتوای اسلاید 31 : 32

Schema Theorem

محتوای اسلاید 32 : 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

محتوای اسلاید 33 : 34

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

محتوای اسلاید 34 : 35

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

محتوای اسلاید 35 : 36

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

محتوای اسلاید 36 : 37

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

محتوای اسلاید 37 : 38

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

محتوای اسلاید 38 : 39

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

محتوای اسلاید 39 : 40

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

پرداخت اینترنتی - دانلود سریع - اطمینان از خرید

پرداخت هزینه و دریافت فایل

مبلغ قابل پرداخت 1,550 تومان
نمایش لینک دانلود پس از پرداخت هزینه
ایمیل
موبایل
کمک مالی به ایتام و کودکان بی سرپرست

درصورتیکه برای خرید اینترنتی نیاز به راهنمایی دارید اینجا کلیک کنید


فایل هایی که پس از پرداخت می توانید دانلود کنید

نام فایلحجم فایل
2041_1983519_3856.zip602.6k