پاورپوینت آشنایی با الگوریتم های ژنتیک

بخشی از پاورپوینت

اسلاید 1 :

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

بسم الله الرحمن الرحیم

اسلاید 2 :

فهرست مطالب
استراتژیهای جستجو (مقدمه)
الگوريتمهای تکاملی (پیشینه‏کاری)
الگوريتمهای ژنتيک
چند اصطلاح
آشنایی با الگوریتم های ژنتیک
ساختار الگوریتم های ژنتیک
عملگر های الگوریتم ژنتیک
مزایای الگوریتم ژنتیک
معایب و اشکالات وارد به الگوریتم های ژنتیک
برنامه نویسی ژنتیک
تاریخچه
قدم های اولیه برنامه نویسی ژنتیک
برنامه نویسی ژنتیک
مشکلات برنامه نویسی ژنتیک
کاربرد ها
مراجع

اسلاید 3 :

استراتژیهای جستجو
کامل
مکاشفه ای
قطعی
غير قطعی
تک جوابی
مبتنی بر جمعيت
الگوريتمهای تکاملی
برنامه ريزی تکاملی
استراتژی تکاملی
الگوريتمهای ژنتيک
برنامه ريزی ژنتيک
الگوريتمهای تخمين توزيع
(Heuristic)
(Non-deterministic)
(Estimation of Distribution Algorithms)
(Evolutionary Algorithms)
(Population-based)
(Search Strategies)
Jenetic algorithm
مقدمه : استراتژیهای جستجو

اسلاید 4 :

الگوریتم های تکاملی
Jenetic algorithm

اسلاید 5 :

نمودار گردشی فرآيند يک الگوريتم تکاملی
فرايند توليد تا وقتی که جواب مورد نظر حاصل شود ادامه می يابد
( اغلب جمعيت اوليه بصورت تصادفی توليد می شود)
پروسه توليد جمعيت جديد از جمعيت فعلی
جايگزينی جمعيت حاصل بجای جمعيت قبلی
جمعيت اوليه
جمعيت جديد

اسلاید 6 :

چند اصطلاح (زمینه بیولوژیکی)
Jenetic algorithm
کروموزوم(Chromosome): در هر سلول مجموعه ای از موجودات هم شکل بنام کروموزوم وجود دارد .

ژنGene)) : هر کروموزوم از تعدادی ژن تشکیل یافته است ؛ هر ژن یک خصیصه را کد می کند.(مثل رنگ چشم)

آلل(Allele) : مجموعه های ممکن برای یک خصیصه آلل نامیده می شود.

لوکس(Locus): هر ژن در کروموزوم موقعیت خاصی را داراست.

ژنوم(Genome) : مجموعه کامل همه کروموزوم ها.

ژنوتیپ(Genotype) : یک مجموعه خاص از ژن ها در ژنوم .

فنوتیپ (Phenotype): ژنوتیپ ها بعد از تکامل بیشتر به فنوتیپ ها (که همان خصوصیات فیزیکی و روانی مانند رنگ چشم یا هوش و .)تبدیل می شوند .

اسلاید 7 :

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

الگوریتم های ژنتیک یکی از شاخه های پردازش تکاملی می باشند.

این الگوریتم ها با الهام از روند تکاملی طبیعت مسائل را حل می نمایند .
یعنی مانند طبیعت یک جمعیت از موجودات را تشکیل می دهند و با اعمالی بر روی این مجموعه به یک مجموعه بهینه و یا موجود بهینه دست می یابند.

با توجه به خصوصیات خاص خودشان به خوبی از عهده حل مسائلی که نیاز به بهینه سازی دارند
بر می آیند.

اسلاید 8 :

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

مساله
تشکیل جمعیت اولیه
جستجوی ژنتیکی
مدلسازی مساله
جواب
ارزیابی جمعیت
انتخاب والدین
بازترکیبی
جهش
انتخاب فرزندان
تست شرط خاتمه

اسلاید 9 :

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

والدين(Parents)
فرزندان( Offspring)
جمعيت جديد( New Population)
جمعيت اوليه( Initial Population)
انتخاب ( Selection)
کروسور(Crossover)
جهش (Mutation)
جايگزينی جمعيت جديدبجای جمعيت قبلی

اسلاید 10 :

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

برای حل یک مساله با الگوریتم های ژنتیک مراحل ذیل را داریم:

1)مدلسازی مساله یا بازنمایی
2)تشکیل جمعیت اولیه
3)ارزیابی جمعیت
4)انتخاب والدین
5)باز ترکیبی
6)جهش
7)انتخاب فرزندان
8)تست شرط خاتمه الگوریتم

اسلاید 11 :

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

شروع
جمعيت اوليه
ارزيابی جوابها
آيا جواب مورد نظر حاصل شده؟
پايان
انتخاب
کروسور
بله
جهش
T=T+1
T=0
خير

اسلاید 12 :

جدول هم ارزی مفاهيم بيولوژيکی و عناصر GA

سير تکاملی طبيعی GA
اندازة انطباق
مجموعه جوابهای جايگزين
توليد
مقدار برازندگی ( تابع ارزياب)
والدين
فرد
جمعيت
جوابهای برگزيده شده
جواب داوطلب
گام تکرار
محيط
مساله برای حل

اسلاید 13 :

سير تکاملی طبيعی GA
تناوب توليد
جواب رمزگذاری شده
فنوتيب
پروسه رسيدن از جمعيت
فعلی به جمعيت بعدی
آلل
ژنوتيب
مقدار در يک موقعيت
معين در رشته
موقعيت در رشته
جواب رمزگشايی شده
بقاء
انتخاب والدين متناسب
با مقدار برازندگی
جدول هم ارزی مفاهيم بيولوژيکی و عناصر GA

اسلاید 14 :

شبه کد یک الگوریتم ژنتیک ساده

اسلاید 15 :

مدلسازی مساله (بازنمایی)

برای اینکه بتوانیم یک مساله را بوسیله الگوریتم های ژنتیک حل کنیم، بایستی آنرا به فرم مخصوص مورد نیاز این الگوریتم ها تبدیل کنیم.
در این روند ما بایستی راه حل مورد نیاز مساله را به گونه ای تعریف کنیم که قابل نمایش بوسیله یک کروموزوم باشد.
اینکه چه نوع بازنمائی را برای مساله استفاده شود، به شخص طراح و فرم مساله بستگی دارد.

چند نمونه از بازنمائی هایی را که معمولاً استفاده می شوند :
اعداد صحیح
رشته های بیتی
اعداد حقیقی در فرم نقطه شناور
اعداد حقیقی به فرم رشته های بیتی
یک مجموعه از اعداد حقیقی یا صحیح
ماشینهای حالت محدود
هر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم

اسلاید 16 :

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

ارزیابی حمعیت Fitness
برای اینکه بتوانیم موجودات بهتر را درون جمعیت تشخیص بدهیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم. به این کار، یعنی تعیین میزان خوبی یک موجود، ارزیابی آن موجود می گویند.

ارزیابی، اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد به آن نسبت می دهیم، این عدد که برای موجودات بهتر
بزرگتر (یا کوچکتر) است را شایستگی آن موجود می نامیم.

به عنوان مثال در صورتی که به دنبال مینیمم یک تابع هستیم، مقدار شایستگی را می توانیم ورودیهایی که مقادیر تابع برای آنها کمتر است در نظر بگیریم که ورودیهای بهتری هستند.

بسته به نوع مساله ما می خواهیم شایستگی را بیشینه و یا کمینه کنیم.

اسلاید 17 :

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

انتخاب Selection (انتخاب والدین)

سوق دادن جستجو به بخشهايی از فضا که امکان يافتن جوابهای با کیفيت بالاتر وجود دارد.
نسل جدیدی از راه حل ها را با انتخاب والدینی که بالاترین Fitness را دارند تولید می کند.

والدین : در هر نسل تعدادی از عناصر جمعیت این فرصت را پیدا می کنند که تولید مثل کنند. به این عناصر که از میان جمعیت
انتخاب می شوند، والدین می گویند.

روشهای مختلفی برای انتخاب والدین وجود دارند. در زیر به چند مورد از این روشها اشاره می کنیم:

اسلاید 18 :

روش های انتخاب والدین

انتخاب تمام جمعیت بعنوان والدین:
در واقع هیچگونه انتخابی انجام نمی دهیم (همه عناصر انتخاب می شوند) .
انتخاب تصادفی:
بصورت تصادفی تعدادی از موجودات جمعیت را بعنوان والدین انتخاب می کنیم، این انتخاب می تواند با جایگذاری یا بدون جایگذاری باشد.
در این روشها عناصر با شایستگی بیشتر شانس بیشتری برای انتخاب شدن بعنوان والدین را دارند.
سایر روشها:
این روشها با استفاده از تکنیک هایی سعی می کنند که انتخاب هایی را ارائه دهند، که هم رسیدن به جواب نهایی را تسریع کنند و هم اینکه کمک می کنند که جواب بهینه تری پیدا شود.

اسلاید 19 :

روش های انتخاب

معمول ترین روش های انتخاب
: Elitist Selection
مناسبترین عضو هر اجتماع انتخاب میشود.
Selection Roulette:
یک روش انتخاب است که در آن عنصری که عدد برازش (تناسب) بیشتری داشته باشد، انتخاب میشود.
ScalingSelection
به موازات افزایش متوسط عدد برازش جامعه، سنگینی انتخاب هم بیشتر میشود و جزئیتر. این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوتهای کوچکی آنها را از هم تفکیک میکند.
Tournament Selection
یک زیر مجموعه از صفات یک جامعه انتخاب میشوند و اعضای آن مجموعه با هم رقابت میکنند و سرانجام فقط یک صفت از هر زیرگروه برای تولید انتخاب میشوند.

اسلاید 20 :

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

ترکيب مجدد (Recombination/Crossover)

امکان ترکيب جوابهای جزيی (partial solutions) يافت شده و در نتيجه بدست آوردن جوابهایی با کيفيت بالاتر را فراهم می‏آورد.

در جریان عمل بازترکیبی به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.
هدف تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.