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

  • شماره مطلب : 26
  • دسته بندی : هوش مصنوعی
  • عنوان : الگوریتم ژنتیک
  • نویسنده : NetBoss
  • پیش نیاز : local beam search الگوریتم
  • پروژه عملی :

شرح الگوریتم ژنتیک

الگوریتم ژنتیک در واقع گونه از Stochastic beam search میباشد. تفاوتی که بین این دو الگوریتم وجود دارد این است که در Stochastic beam search با ایجاد تغییراتی در وضعیت فعلی وضعیت های جدید ایجاد میشوند. این در حالیست که در الگوریتم ژنتیک وضعیت های جدید (فرزند) با ترکیب وضعیت های والد ایجاد میشوند. اگر این مطلب را با دقت و تا انتها مطالعه نمایید علت نام گذاری این روش به الگوریتم ژنتیک را کاملا درک خواهید نمود.

مانند الگوریتم beam search، این الگوریتم کار خود را با ایجاد K  وضعیت رندم شروع خواهد نمود. به مجموعه این K وضعیت اصطلاحا جمعیت میگویند.

نمایش یک فرد (وضعیت) در جمعیت

روشی  که برای نمایش یک وضعیت (فرد) توضیح داده شده، استفاده از یک رشته string از مجموعه آلفابت های متناهی میباشد. این رشته آلفابتی معمولا رشته ای از 0  ها و 1 ها میباشد. برای مثال، در مسئله هشت وزیر اگر بخوایم وضعیت با شماره سطر هر وزیر که در ستون های جداگانه ای نگهداری میشوند را بسازیم به 24 بیت فضا احتیاج خواهیم داشت. (لطفا برای درک بهتر این توضیح مطالب مرتبط با مسئله هشت وزیر و یا روش های جستجوی محلی را بطور کامل مطالعه بفرمایید)

بجای روش فوق حتی میتوان از اعداد 1 الی 8 برای نمایش شماره سطر هر وزیر استفاده نمود. مثال زیر یک وضعیت از نظر الگوریتم ژنتیک برای مسئله هشت وزیر را نمایش میدهد. وضعیت زیر در واقع جایگاه هر مهره در صفحه شطرنج را نمایش میدهد.

 

مهره ستون 1 مهره ستون 2 مهره ستون 3 مهره ستون 4 مهره ستون 5 مهره سطون 6 مهره ستون 7 مهره ستون 8
سطر 2 سطر 4 سطر 7 سطر4 سطر 8 سطر 5 سطر 5 سطر 2

Fitness Function چیست؟

حال که مفهوم یک وضعیت (فرد) در الگوریتم ژنتیک را درک نمودیم باید با مفهومی به نام Fitness Function آشنا شویم. Fitness Function در واقع تابعیست که به هریک از وضعیت های یک جمعیت امتیاز اختصاص میدهد. پس قائدتا هرچه وضعیت به وضعیت هدف نزدیک تر باشد، امتیاز Fitness Function هم بالاتر است. برای مثال در مسئله هشت وزیر Fitness Function میتواند تعداد جفت مهره هایی که با یک دیگر اثابت ندارند را بازگرداند. با این توصیف وضعیت هدف در مسئله هشت وزیر دارای Fitness Function  با مقدار 28 میباشد. یادمان باشد که طراحی Fitness Function کاملا وابسته به سناریوی مسائل میباشد. این بدین معناست که در مسائل مختلف پیاده سازی Fitness Function ها متفاوت خواهد بود. بالا بودن مقدار Fitness Function برای یک وضعیت شانس انتخاب شدن آن را برای جفت گیری بالا خواهد برد. مثلا فرض کنید در ابتدای کار ما صد وضعیت رندوم ایجاد نموده ایم. حال با استفاده از Fitness Function میتوان وضعیت ها را مرتب نموده و چند عدد از بهترین وضعیت ها را بر ای ادامه کار عملیات انتخاب نمود. 

مرحله جفت گیری

اجازه بدهید تا قبل از ارائه مطالب کتاب راسل به شما موضوعی واضح ولی مهم را یادآوری کنم. واضح است که همیشه فرزندی که از جفت گیری دو شخص بدنیا میاید صفتی را از پدر مادر خود به ارث میبرد. این واقعیت قسمت عظیمی از نحوه کار کرد الگوریتم ژنتیک در علم هوش مصنوعی را توضیح میدهد. در الگوریتم ژنتیک در واقع تعدادی از وضعیت ها (با Fitness Function بالاتر) از میان جمعیت انتخاب شده و اصطلاحا به آنها فرصت جفت گیری داده میشود. از ترکیب این وضعیت ها وضعیت هایی جدید بوجود میآیند که با نسبت هایی رندم صفاتی را از وضعیت های والد ارث میبرند. به یاد داشته باشید که پس از انتخاب وضعیت ها الزامی به گروه بندی دو تایی برای عملیات جفت گیری نداریم! در واقع میخواهیم بگویم که این عملیات کاملا بصورت رندم اتفاق خواهد افتاد. برای همین ممکن است از میان وضعیت های انتخاب شده وضعیت هایی وجود داشته باشند که با هیچ کس جفت گیری نکنند و یا با چند نفر جفت گیری نمایند. همانطور که در تصویر زیر مشاهده مینمایید وضعیت منتخب چهارم با هیچکدام از وضعیت های دیگر جفت گیری نکرده است. همچنین وضعیت دوم با دو وضعیت جفتگیری کرده است.

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

 

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

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

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

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

 

function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual
inputs: population, a set of individuals
FITNESS-FN, a function that measures the fitness of an individual
repeat
new population ←empty set
for i = 1 to SIZE(population) do
x ←RANDOM-SELECTION(population, FITNESS-FN)
y ←RANDOM-SELECTION(population, FITNESS-FN)
child ←REPRODUCE(x , y)
if (small random probability) then child ←MUTATE(child )
add child to new population
population ←new population
until some individual is fit enough, or enough time has elapsed
return the best individual in population, according to FITNESS-FN

 

function REPRODUCE(x , y) returns an individual
inputs: x , y, parent individuals
n←LENGTH(x ); c←random number from 1 to n
return APPEND(SUBSTRING(x, 1, c), SUBSTRING(y, c + 1, n))

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.