الگوریتم ژنتیک : آموزش 0 تا 100 الگوریتم ژنتیک ، Genetic Algorithm

الگوریتم ژنتیک چیست؟ در این آموزش به این سوال پاسخ خواهیم داد که الگوریتم ژنتیک چیست و چه کاربردی دارد ؟ با مفهوم الگوریتم ژنتیک آشنا میشویم . پس با آموزش الگورتیم ژنتیک به زبان ساده با ما همراه باشید.

مقدمه ای در خصوص الگوریتم ژنتیک :

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

الگوریتم های ژنتیک به طور کلی برای حل مسائل بهینه سازی و جستجو استفاده می شود.

این الگوریتم یک الگوریتم کلی است به طوری که در مسائل مختلف به راحتی قابل پیاده سازی است و می تواند نتایج بهتری را در هر تکرار از جستجو ارائه دهد.

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

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

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

مراحل الگوریتم ژنتیک: پنج مرحله اصلی در الگوریتم ژنتیک در نظر گرفته شده است:

1. جمعیت اولیه : Initial population
2. محاسبه شایستگی : Fitness function
3. انتخاب : Selection
4. کراس اوور یا ترکیب : Crossover
5. جهش : Mutation

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

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

فنوتایپ چیست ؟ ژنوتایپ چیست؟ : در این بخش بهتر دیدم به سوالی که برای خیلی از دوستان پیش میاد پاسخ بدهم ، فرق بین فنوتایپ و ژنوتایپ چیه؟

در مسائل بهینه سازی (میدونید که در الگوریتم ژنتیک هدفمان بهینه کردن می باشد! ) راه حل یک مسئله را باید بتوانیم تعریف کنیم . یعنی بگوییم مسئله ما ، جوابش چه شکلی است. خب اجازه بدین با یک مثال ساده ، یکبار برای همیشه مفهوم فنوتایپ و ژنوتایپ را روشن کنم.

مسئله فروشنده دوره گرد را در نظر بگیرید: یک فروشنده داریم که میخواهد پوشاکش را شب عید در شهر های مختلف بفروشد . از تولیدی ای در تهران پوشاک را بصورت عمده خریده است و قصد دارد تا به سه تهران، اصفهان، اراک ، قزوین برود و آنها را بفروشد و در نهایت به تهران برگردد. میخواهیم مشخص کنیم که به ترتیبی به شهر های مورد نظر برود تا طول مسافرتش کمتر شود.

مثال فنوتایپ : در اینجا ترتیب شهر ها جواب مسئله ما می باشد بعنوان مثال هر یک از موارد زیر یک جواب است:

• تهران، اصفهان، اراک، قزوین ، تهران
• تهران، اراک ، اصفهان ، قزوین ، تهران
• تهران ، قزوین، اصفهان، اراک ، تهران
• تهران، قزوین، اراک ، اصفهان ، تهران

خب اگر بخواهیم این مسئله را با الگورتیم ژنتیک جل کنیم ، ما در برنامه خود به هر شهر یک کد میدهیم ، مثلا تهران عدد 1 ، اراک عدد 2 ، اصفهان عدد 3 و قزوین عدد 4 ، حالا با این فرض راه حل هایی که در بالا بصورت فنوتایپ مثال زدیم به شکل زیر خواهند شد:

• 1 ، 3 ، 2 ، 4 ، 1
• 1 ، 2 ، 3 ، 4 ، 1
• 1 ، 4 ، 3 ، 2 ، 1
• 1 ، 4 ، 2 ، 3 ، 1

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

فنوتایپ : نمایش راه حل ها در دنیای واقعی می باشد . ژنوتایپ : نمایش راه حل در حالت محاسباتی یا در برنامه کامپیوتری می باشد.

جمعیت در الگوریتم ژنتیک (Population)

به مجموعه ای از راه حل ها در الگوریتم ژنتیک، جمعیت گفته میشود. بعنوان مثال ما در بالا برای فروشنده دوره گرد 4 راه حل را لیست کردیم ، این 4 راه حل را میتوانیم یک جمعیت برای این مسئله در نظر بگیریم. (یک جمعیت 4 نفره)

در حالت کلی جمعیت : یک زیر مجموعه از تمام راه حل های ممکن (رمزگذاری شده) برای مسئله ارائه شده می باشد.

معمولا در الگوریتم Genetic ، جمعیت را با یک آرایه یا ماتریس نمایش میدهند. به تصویر زیر دقت کنید.

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

یکی از مهمترین تصمیماتی که باید هنگام اجرای الگوریتم ژنتیک گرفته شود ، تصمیم گیری در مورد بازنمایی (representation) است که ما برای نشان دادن راه حل های خود استفاده خواهیم کرد. انتخاب نادرست نحوه نمایش راه حل میتواند منجر به ضعیف شدن الگوریتم شود.

بنابراین ، انتخاب نمایش مناسب ، داشتن تعریف مناسب از نگاشت ها بین فضاهای فنوتیپ و ژنوتیپ برای موفقیت الگوریتم GA ضروری است.

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

بازنمایی باینری : Binary Representation

این یکی از ساده ترین و پرکاربردترین نمایش ها در GA است. در این نوع نمایش ژنوتیپ از رشته های بیت تشکیل شده است (یعنی مقدار هر ژن یا 0 است یا 1).

برای مسالی که فضای حل متغیرهای تصمیم بولیم باشد ( بله یا خیر ) ، نمایش باینری طبیعی است.

به عنوان مثال مسئله کوله پشتی 0/1 را در نظر بگیرید. در این مسئله از بین n کالا میخواهیم تعدادی را در یک کوله پشتی قرار دهیم و بدنبال برداشتن با ارزش ترین اجناس هستم. در این مسئله برای هر کالا ، ما دو حالت داریم یا آن را در کوله پشتی قرار میدهیم (1) یا قرار نمیدهیم (0) . پس نمایش باینری برای این مسئله کاملا مناسب است.

بعنوان مثال اگر ما 10 کالا برای انتخاب داشته باشیم یک راه حل میتواند بصورت زیر باشد:

نمایش اعداد صحیح (Integer Representation)

برای مسائلی که گسسته هستند ، نمایش عدد صحیح یک نمایش مناسب است. یعنی مقدار هر ژن یک عدد صحیح و گسسته خواهد بود.

بعنوان مثال مسئله تخصیص وظایف را در نظر بگرید. در این مسئله مثلا 3 نفر داریم که کارها را انجام میدهند و 10 کار برای انجام دادن وجود دارد. حال میتوانیم متغیر مسئله را این در نظر بگیریم که هر کار توسط چه کسی انجام شود. پس هر کار میتواند توسط سرویس دهنده شماره 1 یا 2 یا 3 انجام شود. یعنی ما 10 ژن خواهیم داشت و مقدار هر ژن یک عدد بین 1 تا 3 خواهد بود.

بازنمایی اعشاری : Real Valued Representation

برای مسائلی که مقدار متغیرهای آنها عدی حقیقی باشد ، بهتر است که از نمایش اعشاری استفاده کنیم. بعنوان مثال برای حل تابع y=3.14+x1+x2 که بازه هر متغیر بین -100 تا 100 است بهتر است که از نمایش اعشاری استفاده کنیم ، چونکه متغیر x1 و x2 متغیرهای حقیقی و پیوسته هستند.

نمایش جایگشتی : Permutation Representation

برخی مسائل هستند که متغیرهای آنها گسسته و عددی است اما مقدار تکرار در جواب نباید باشد . یعنی ترتیب راه حل ها مهم است ، در این حالت بازنمایی جایگشتی بهترین گزینه است.

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

جمعیت اولیه در الگوریتم ژنتیک : Initial Population In Genetic Algorithms

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

دو تا نکته در مورد این تعریف قابل توجه است

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

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

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

بعنوان مثال اگر بخواهیم تابع ریاضی y=3.14+x1+x2 را مینیمم کنیم و بازه مجاز هر متغیر از -100 تا 100 در نظر گرفته شود. یک راه حل یا یک کروموزوم باید بصورت یک بردار 2 تایی در نظر گرفته شود. چرا ؟ (چون که مقدار 2 تا متغیر x1 و x2 را باید پیدا کنیم.)

پس یک کروموزوم یک بردار با 2 خانه (2 ژن) می باشد که مقدار هر خانه آن میتواند عددی بین -100 تا 100 باشد.

تابع شایشتگی در الگوریتم ژنتیک Fitness function (تابع فیتنش در الگوریتم ژنتیک)

عملگر شایستگی (همچنین به عنوان عملکرد ارزیابی شناخته می شود) ارزیابی می کند که یک راه حل داده شده چقدر به راه حل مطلوب مسئله مورد نظر نزدیک است. در واقع تابع شایستگی این میزان مناسب بودن یک راه حل را تعیین می کند.

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

یعنی هر راه حل را به تابع شایستگی میدهیم و تابع شایستگی میزان مناسب بودن آن راه حل را به ما میدهد.

آموزش عملگر های الگوریتم ژنتیک : Genetic Algorithm Operators

عملگر انتخاب در الگوریتم ژنتیک : بررسی Selection در Genetic Algorithm

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

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

در هر مرحله از تکرار الگوریتم ، مجموعه ای از والدین بر اساس مقادیر شایستگی هر فرد با استفاده از عملگرانتخاب ، از بین جمعیت فعلی انتخاب می شود ، به این ترتیب كه افراد شایسته ، احتمال بیشتری برای انتقال به نسل های بعدی دارند. این جمعیت انتخاب شده (که به عنوان جمعیت “والدین” شناخته می شود) سپس پایه و اساس کلیه بهینه سازی های بعدی در مرحله تولید نسل را تشکیل می دهد.

در الگوریتم ژنتیک ، روش های مختلفی برای انتخاب والدین وجود دارد که به آنها استراتژی های انتخاب گفته میشود.

• Random Selection یا انتخاب تصادفی : در این روش بدون توجه به شایستگی افراد ، بصورت تصادفی والدین انتخاب میشوند.
• انتخاب تورنومنت یا Tournament selection : در این روش والدین بر اساس مسابقه انتخاب میشوند.
• انتخاب چرخ گردان یا Roulette Wheel Selection : در این روش انتخاب والیدن بر اساس احتمال انتخاب آنها می باشد.
• انتخاب نمونه برداری تصادفی یا Stochastic Universal Sampling یا (SUS) : همانند روش چرخ گردان است اما چند نقطه انتخاب دارد.
• انتخاب مبتنی بر رتبه یا Rank Selection : در این روش انتخاب بر اساس میزان شایستگی صورت میگیرد.

عملگر ترکیب در الگوریتم ژنتیک Crossover Operation

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

در الگوریتم ژنتیک ، عملگرهای کراس اور یا ترکیب متعددی معرفی شده است که در زیر اشاره میکنیم:

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

انتخاب نسل بعد Survivor selection