الگوریتم ژنتیک یا
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:
00001|011
00100|010
After crossover:
00001010
00100011
در بالا فرآیند Crossover رو برای زوج اول می بینید! همونطور که مشخصه اول هر کزومزوم از بیت 5ام به دو قسمت تقسیم شدن و 5 بیت اول کرومزوم اول با 3 بیت دوم کرومزوم دوم ترکیب شده و برعکس. به این ترتیب دو فرزند جدید بوجود اومد.
همین کار برای بقیه ی کرومزوم ها هم انجام میشه، ممکنه یک کرومزوم دو یا چند بار در فرآیند Crossover بکار برده شه، احتمال شرکت کرومزوم هایی که سلامت بهتری دارند توی فرآیند Crossover بیشتره!
بعد از فرآیند Crossover یک مرحله داریم که احتمال وقوعش خیلی کم هست به نام جهش یا Mutation. توی این فرآیند یک بیت تصادفی از یه کرومزوم تصادفی رو عوض می کنند. مثلا اگر بیت چهارم یک کرومزوم انتخاب بشه در صورتی که صفر باشه اونو یک می کنند یا بلعکس.
كد:
First chromosome:
00001011
After mutation:
00011011
این فرایند تو واقعیت هم وجود داره مثلا در یک آدم جهشی به وجود میاد و نابغه میشه یا در یه آدم دیگه جهش بوجود میاد و ناقص میشه! در الگوریتم ژنتیک هم همینطوره، یک جهش ممکنه کاملا مفید یا کاملا مضر باشه.
بعد از این مرحله دوباره کرومزوم های جدید به جمعیت اولیه برای نسل بعد بر می گردند و این فرآیند ها تکرار میشه تا با یک تلورانسی به جوابی که می خوایم نزدیک شیم! این روش در مقایسه با بقیه ی روش های آزمایش و خطا خیلی پیشرفته تره و خیلی وقت ها بسیار سریعتر به نتیجه ی مطلوب میرسه!
منبع: سیاوش محمودیان - بلاگ - مقدمه ای بر هوش مصنوعی