پیاده سازی الگوریتم ژنتیک با عامل ها
 

لطفا اگر در مورد پیاده سازی الگوریتم ژنتیک با عامل ها مطالبی دارید به اشتراک بگذارید

سلام خسته نباشید چیزی در مورد طراحی سایت می دانید

Hello ! سلام خسته نباشید چیزی در مورد طراحی سایت می دانید:103:

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

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

فضای فرضیه

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

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

منبع : matlabdl

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


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


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

منبع : matlabdl

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

نحوه ایجاد جمعیت جدید

مراحل ایجاد یک جمعیت جدید بصورت زیر است :
1. select : تعداد (1-r)p فرضیه از میان P انتخاب و به Ps اضافه کنید . احتمال انتخاب یک فرضیه hi از میان P عبارت است از :
P(hi) = Fitness (hi) / Σj Fitness (hj)

هر چه تناسب فرضیه ای بیشتر باشد احتمال انتخاب آن بیشتر است . این احتمال همچنین با مقدار تناسب فرضیه های دیگر نسبت عکس دارد.
2. Crossover : با استفاده از احتمال بدست آمده توسط رابطه فوق، تعداد (rp)/2 زوج فرضیه از میان P انتخاب و با استفاده از اپراتور Crossover دو فرزند از آنان ایجاد کنید . فرزندان را به Ps اضافه کنید.

3. Mutate : تعداد m درصد از اعضا Ps را با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنید.

4. برای هر فرضیه h در P مقدار تابع Fitness را محاسبه کنید

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

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

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

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

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

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

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

منبع : matlabdl

برای من سوال و نیازمند منابع هستم برای الگوریتم ژنتیک. کسی کتاب سراغ نداره. زبان اصلی هم باشه مهم نیست.