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

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

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

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

الگوریتم ژنتیک بدون شک معروف ترین متاهیورستیک و معروف ترین الگوریتم تکاملی می باشد. و  به همین خاطر زمانی که بحث الگوریتم تکاملی می شود اولین چیزی که به ذهن ما می رسد همان الگوریتم ژنتیک است. جالب است بدانید ده سال قبل از آن ها آلمانی ها Evolution Strategy   را معرفی کرده بودند و حدود چهار سال بعد از Evolution Strategy در آمریکا Evolution Programming معرفی شده بود ولی با این حال همه الگوریتم ژنتیک را می شناسند که واقعا کار ارزنده ای است. دنیایی که ما در آن زندگی می کنیم به طور مداوم در حال تغییر است و هر موجودی که قصد ماندن در چنین محیطی را داشته باشد، بایستی بتواند خود را با شرایط اطراف تطبیق دهد. و برای این انطباق(انطباق زیستی) چندین نظریه وجود دارد.

۱-  نظریه داروین: در نطریه داروین طبیعت موجوداتی را دستچین می کند که با معیارهای طبیعت سازگار هستند.

۲ – نظریه لامارک: در نظریه داروین هر نسل تعدادی خواص و مهارت هایی را بدست می آورد و آن ها را به نسل بعد منتقل می کند.

اگر ما تئوری داروین را در برنامه های کامپیوتری شبیه سازی کنیم، می شود همان الگوریتم ژنتیک. ولی اگر تئوری لامارک را شبیه سازی کنیم همان   Evolution Programming می شود.

این فرآیند تطبیق به نام های تکامل یا فرگشت(Evolution) معروف است.

تکامل چیست؟(Evolution)

تکامل حاصل عملکرد پدیده های زیر می باشد:

• انتخاب طبیعی (Natural Selection): یعنی هر موجودی که بیشتر منطبق بر معیارهای طبیعت باشد، بیشتر شانس بقا دارد و بقیه هر چقدر هم که خوب باشند چون درجه انتطباقشون کمتر می باشد، حذف می شوند. مثلا زمانی حاکم طبیعت دایناسورها بودند ولی شرایطی پیش آمد که دیگر نتوانستند آن انطباق قبل را داشته باشند و از بین رفتند.

 

• تولید مثل(Reproduction): تولید مثل انگیزه ای است یعنی همان خود تکثیری(Self Replication) که از همان ملوکول های پیچیده ای که حیات از آن بوجود آمد تا همین الان در انسان ها هم هست. یعنی تولید گونه ای مانند خود.

 

• جهش(Mutation): جهش اپراتوری است که تحت تاثیر عوامل تصادفی و یا غیر تصادفی باعث ایجاد یکسری تغییرات برنامه ریزی نشده می شود. خیلی وقت ها این تغییرات پیشبینی نشده تاثیرات بدی دارند ولی در درصد خیلی کمی این تغییرات باعث اتفاقات خوبی می شود. خیلی از خواص جالبی که موجودات اکنون دارند در نتیجه این جهش ها موفق بوده اند. ولی خیلی جهش های ناموفق هم داریم مانند بیماری های سرطان.

 

• همزیستی(Symbiosis): سگ و گربه بخاطر همزیستی در مجاورت انسان ها نسبت به سایر هم نوعانشان خیلی باهوش تر می باشد و دلیل آن نیز همزیستی با انسان ها می باشد. مثلا گربه نسبت به سایرها خیلی باهوش تر می باشد. یا مثلا سگ خیلی باهوش تر از سایر سگ های وحشی که در محیط که در محیط اهلی زندگی نمی کنند.

این ها عواملی هستند که می توانند عوامل ریاضی شوند و در الگوریتم ژنتیک ایجاد شوند.

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

به عنوان یک مثال بسیار شناخته شده، این موجودات را مقایسه کنید:

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

این موارد را نیز مقایسه می کنیم:

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

 

طرح اولیه یک الگوریتم تکاملی

مراحل الگوریتم تکاملی

• ایجاد مجموعه ای از جواب های تصادفی: مثلا یکسری مجموعه های تصادفی از ژن ها در طبیعت ایجاد می شود و هر کدام مطابق با معیارهای طبیعت باشد زنده می ماند.
• مقایسه جواب ها، ربطه بندی آن ها و انتخاب بهترین ها.
• ترکیب جواب های بدست آمده، با شبیه سازی فرآیندهای طبیعی مانند طول مثل و ادغام جواب ها جدید با جواب های قدیمی. مثلا ادغام نظر چند مشاور بای رسیدن به جواب بهتر.
• بازگشت به مرحله ۲(در صورت نیاز).

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

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

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

از اوایل دهه ۱۹۵۰ میلادی، تلاش هایی برای شبیه سازی پدیده تکامل بر روی کامپیوترها آغاز شد که در این میان توجه بسیاری از محققین حوزه های مربوط به علوم ریاضی و مهندسی، به این زمینه جلب شد. نهایتا در اوایل دهه ۱۹۷۰، جان هالند در کتابش الگوریتم ژنتیک را به عنوان ابزاری عمومی برای بهینه سازی معرفی کرد.

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

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

در اوایل دهه ۱۹۷۰ نتایج کارهای دیونگ منتشر شدند، که حاکی از کارآمدی الگوریتم ژنتیک برای حل انواع مسائل بهینه سازی بودند.

Exploit: بهره برداری

Exploration: اکتشاف

 

مراحل الگوریتم ژنتیک (Genetic Algorithm)

1. ایجاد جمعیت اولیه و ارزیابی آن ها: در الگوریتم ژنتیک برای شروع یک کار، باید یکسری پیشنهاد اولیه بدهیم و رفته رفته این پیشنهادها را تکامل بدهیم.
2. انتخاب والدین و ترکیب آن ها برای ایجاد جمعیت فرزندان.
3. انتخاب اعضای جمعیت برای اعمال جهش و ایجاد جمعیت جهش یافتگان.
4. ادغام جمعیت اصلی، فرزندان و جهش یافتگان و ایجاد جمعیت اصلی جدید.
5. اگر شرایط خاتمه محقق نشده باشند، از مرحله ۲ تکرار می کنیم.
6. پایان.

انواع شرایط خاتمه در الگوریتم ژنتیک

1. رسیدن به حد قابل قبولی از پاسخ.
2. سپری شدن زمان یا تکرار معین.
3. سپری شدن زمان یا تکرار تعداد تکرار معین بدون مشاهده بهبود خاصی در نتیجه.
4. رسیدن به یک تعداد مشخص از NFE

بهینه سازی(Optimization)

در مسائل بهینه سازی به دنبال بهینه کردن تابع هدف(Objective Function) هستیم. در بعضی از مسائل نیاز به کمینه سازی(Minimization) تابع هدف داریم . در مسائل کمینه سازی، نام تابع هدف، تابع هزینه(Cost Function) نام دارد. در مسائل مدلسازی نیز نام تابع هدف، تابع خطا(Error Function) نام دارد.

در بعضی از مسائل نیاز به بیشینه سازی(Maximization) تابع هدف داریم . در مسائل بیشینه سازی، نام تابع هدف، تابع برازندگی(Fitness Function) و تابع سود(Profit Function)  است.

نحوه تشخیص نوع جهش و ترکیب

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

سناریو اول:

نحوه محاسبه متغیرها

 

 

سناریو نحوه انتخاب اعضا برای نسل بعد

 

تعداد فراخوانی NFE

  تعداد تکرار‍‍*(تعداد جهش یافتگان+تعداد فرزندان) + تعداد جمعیت اصلی = تعداد دفعات فراخوانی تابع هدف NFE

 

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