• ۱۳۹۳/۰۵/۲۹, ۰۲:۱۲
  • در همه مقالات
  • توسط admin
  • بازدید: 1015
  • اخرین ویرایش: ۱۳۹۷/۰۲/۰۱, ۲۳:۱۲
  • چاپ نوشته هاچاپ پی دی اف

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

الگوریتم ژنتیک یا (Genetic Algorithm (GA در واقع شبیه سازی بقای انسان هست!
تا حالا پیش خودتون فکر کردین این همه سال گذشته چطوری انسان ها از بین نرفتن و نسلشون پا برجاس؟ فکر می کنید رمز موفقیتشون چیه؟
فکر کنم 183462130973.347928374261010000001 باشه!  
انسان ها بقا دارن چون با یه قانون خاصی پیش میرن که واضحه که موفق بوده! حالا همین قانون رو توی کامپیوتر میشه شبیه سازی کرد! اما چجوری؟ فکر کنید میخوایم جواب این تابع رو بدست بیاریم:
  X^2 + e^X + 3*sin(X) + int(-X^X) / X = 12 
بنظر خیلی پیچیده میاد! شاید با روش های تحلیلی حل نشه و نیاز به محاسبات عددی باشه! یکی از راه ها الگوریتم ژنتیک هست که بعضی اوقات به شکل باور نکردنی سریع به جواب میرسه.

 

خوب پس من با یه مقدمه ازش شروع می کنم:

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

00001011 
00100010 
01000000 
11100001 
01101100 
00000111 
11001010 
11110000 
00010101 
10000000 
11100100 
بعد از اینکه جمعیت اولیه معلوم شد این کرومزوم ها توی تابع Fitness امتحان میشن و بر حسب اینکه به جواب مورد نظر نزدیکن یا نه یه عدد بین صفر تا یک بهشون اختصاص داده میشه که صفر یعنی اصلا بدرد نمی خوره و یک یعنی عالیه!
بر حسب سلامتی کرومزوم ها چند تا از اون ها به عنوان والدین نسل بعدی انتخاب میشن!

مرحله ی بعدی مرحله ی Breed هست که طبق فرایند Crossover کرومزوم ها با هم ازدواج می کنن و بچه دار میشن!

خوب حالا فرآیند Crossover چطور انجام میشه؟ از کرومزوم های برگزیده دوتا دوتا انتخاب میشن و فرایند Crossover روی هر زوج بصورت زیر انجام میشه:

 First pair:

011|00001

010|00100

After crossover:

00001010

00100011

در بالا فرآیند Crossover رو برای زوج اول می بینید! همونطور که مشخصه اول هر کزومزوم از بیت 5 ام به دو قسمت تقسیم شدن و 5 بیت اول کرومزوم اول با 3 بیت دوم کرومزوم دوم ترکیب شده و برعکس. 
به این ترتیب دو فرزند جدید بوجود اومد. همین کار برای بقیه ی کرومزوم ها هم انجام میشه، ممکنه یک کرومزوم دو یا چند بار در فرآیند Crossover بکار برده شه، احتمال شرکت کرومزوم هایی که سلامت بهتری دارند توی فرآیند Crossover بیشتره! 
بعد از فرآیند Crossover یک مرحله داریم که احتمال وقوعش خیلی کم هست به نام جهش یا Mutation.
توی این فرآیند یک بیت تصادفی از یه کرومزوم تصادفی رو عوض می کنند.
مثلا اگر بیت چهارم یک کرومزوم انتخاب بشه در صورتی که صفر باشه اونو یک می کنند یا بلعکس.

First chromosome: 00001011 
After mutation: 00011011

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

اشتراک

دیدگاه دیگران (بدون دیدگاه)...

Leave a reply

نام:: فیلد اجباری.
آدرس رایانامه: فیلد اجباری. غیر فعال
وبسایت::
کد امنیتی:: فیلد اجباری.
دیدگاه: فیلد اجباری.

هم اکنون گام نخست را برای داشتن یک وبسایت حرفه ای و جذاب بردارید

متخصصان و مشاوران ما آماده‌اند تا شما را در تمامی مراحل داشتن یک وب سایت راهنمایی کنند
ثبت درخواست