مقدمه ای بر الگوریتم های ژنتیک

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

حدس زدن ناشناخته

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

شما دو نفر شروع به لذت بردن از ناهار هفتگی با هم می کنید و در مورد همه چیز از سیاست گرفته تا شعر بحث می کنید. حتی بعد از گذشت چندین ماه ، شما هنوز مطمئن نیستید که او ژست های عاشقانه می زند یا به دنبال اسرار می رود (نه اینکه شما از آنها چیزی می دانید). شاید کمی از هر دو باشد.

او یک روز در وعده ناهار این چالش را به شما نشان می دهد: «من برای شما پیغام دارم دکتر عزیز! البته نمی توانم بگویم چیست. اما من به شما می گویم که طول آن 12 شخصیت است. این نویسه ها می توانند هر حرف از حروف الفبا ، یک فاصله یا علامت نقطه گذاری باشند. و من به شما می گویم حدس های شما چقدر دور است. شما باهوش هستید فکر می کنی بتوانی بفهمی؟ “

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

کمی تئوری

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

در سناریوی بالا ، هر کاراکتر در پیام مخفی می تواند A-Z ، یک فاصله یا یک علامت نقطه گذاری اساسی باشد. بیایید بگوییم که “الفبای” 32 حرفی زیر را برای کار با ما فراهم می کند: ABCDEFGHIJKLMNOPQRSTUVWXYZ -.,!? این یعنی 32 وجود دارد¹² (تقریباً 1.15Ã – 10¹⁸) پیام های احتمالی ، اما فقط یکی از این احتمالات پیام صحیح است. بررسی هر احتمال خیلی طولانی می شود. در عوض ، یک الگوریتم ژنتیک به طور تصادفی 12 کاراکتر را انتخاب می کند و از خیاط / جاسوس می خواهد نتیجه گیری کند که نتیجه چقدر به پیام او نزدیک است. این از کارآیی بیشتری نسبت به جستجوی بی رحمانه برخوردار است ، زیرا نمره به ما امکان می دهد نامزدهای آینده را دقیق تنظیم کنیم. بازخورد به ما توانایی ارزیابی تناسب هر حدس را می دهد و امیدواریم از اتلاف وقت در بن بست ها جلوگیری کنیم.

فرض کنید سه حدس می زنیم: HOMLK?WSRZDJ، BGK KA!QTPXC، و XELPOCV.XLF!. نامزد اول نمره 248.2 ، نفر دوم 632.5 و نفر سوم 219.5 را کسب می کند. نحوه محاسبه نمره به شرایط بستگی دارد که بعداً در مورد آن بحث خواهیم کرد ، اما در حال حاضر فرض کنیم که این انحراف بین داوطلب و پیام هدف باشد: نمره کامل 0 است (یعنی هیچ انحرافی وجود ندارد ؛ کاندیدا و هدف یکسان است) ، و نمره بزرگتر به معنی انحراف بیشتر است. حدسهایی که نمرات 248.2 و 219.5 را کسب کرده اند نزدیک تر از آنچه ممکن است پیام مخفی باشد نسبت به حدس 635.5 است.

حدس های آینده با ترکیب بهترین تلاش ها ساخته می شود. روش های زیادی برای ترکیب نامزدها وجود دارد ، اما در حال حاضر ما یک روش متقاطع ساده را در نظر خواهیم گرفت: هر شخصیت در حدس جدید 50-50 احتمال کپی شدن از نامزد اصلی یا دوم را دارد. اگر دو حدس را بزنیم HOMLK?WSRZDJ و XELPOCV.XLF!، شخصیت اول کاندیدای فرزندان ما 50٪ احتمال حضور دارد H و 50٪ احتمال وجود دارد X، شخصیت دوم خواهد بود O یا E، و غیره فرزندان می توانند باشند HELLO?W.RLD!.

با این وجود ، اگر فقط از مقادیر کاندیداهای اصلی استفاده کنیم ، یک مشکل می تواند در مورد تکرارهای متعدد بوجود بیاید: عدم تنوع. اگر ما یک کاندیدا متشکل از همه داشته باشیم Aو یکی دیگر از همه B، پس هر فرزندی که فقط توسط کراس اوور با آنها تولید شود فقط شامل می شود A‘شن Bاست اگر راه حل حاوی a باشد ، دیگر شانس نداریم C.

برای کاهش این خطر و حفظ تنوع در حالی که هنوز درگیر راه حل هستیم ، می توانیم تغییرات جزئی ایجاد کنیم. به جای تقسیم مستقیم 50-50 ، ما یک شانس اندک داریم که به جای آن مقدار دلخواه از الفبا انتخاب شود. با این جهش ممکن است فرزندان تبدیل شوند HELLO WORLD!.

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

آلل: عضوی از الفبای ژنتیکی است. نحوه تعریف آلل ها به الگوریتم بستگی دارد. مثلا، 0 و 1 ممکن است آلل هایی برای یک الگوریتم ژنتیک باشد که با داده های باینری کار می کند ، یک الگوریتمی که با کد کار می کند ممکن است از اشاره گرهای عملکرد و غیره استفاده کند. در سناریوی پیام مخفی ما ، آلل ها حروف الفبا ، فضا و علائم مختلف علائم نگارشی بودند.
کروموزوم: دنباله ای از آلل ها. یک راه حل کاندیدایی یک حدس”. در سناریوی ما ، HOMLK?WSRZDJ، XELPOCV.XLF!، و HELLO WORLD! همه کروموزوم ها هستند.
ژن: آلل در یک مکان خاص در کروموزوم. برای کروموزوم HOMLK?WSRZDJ، اولین ژن است H، ژن دوم است O، سوم است M، و غیره
جمعیت: مجموعه ای از یک یا چند کروموزوم نامزد که به عنوان راه حل برای مشکل پیشنهاد شده است.
نسل: جمعیت در طی تکرار خاص الگوریتم. نامزدها در یک نسل ژن هایی را برای تولید جمعیت نسل بعدی فراهم می کنند.
تناسب اندام: معیاری که نزدیک بودن یک کاندیدا به راه حل مورد نظر را ارزیابی می کند. کروموزوم های فیتر به احتمال زیاد ژن های خود را به کاندیداهای آینده منتقل می کنند در حالی که کروموزوم های مناسب کمتر دور ریخته می شوند.
انتخاب: روند انتخاب برخی از نامزدها برای تولید مثل (که برای ایجاد کروموزومهای نامزد جدید استفاده می شود) و دور انداختن دیگران. چندین استراتژی انتخاب وجود دارد که در تحمل آنها برای انتخاب نامزدهای ضعیف تر متفاوت است.
تولید مثل: فرآیند ترکیب ژنهای یک یا چند نامزد برای تولید کاندیداهای جدید. کروموزوم های دهنده نامیده می شوند والدین، و کروموزومهای حاصل به همین ترتیب نامیده می شوند فرزندان.
جهش: معرفی تصادفی ژنهای نابجا در فرزندان برای جلوگیری از از بین رفتن تنوع ژنتیکی در بسیاری از نسلها.