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

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

معرفی الگوریتم ژنتیک و توانایی های آن

الگوریتم ژنتیک، یکی از روش های تصادفی بهینه یابی کشف شده توسط جان هالند در سال ۱۹۶۷ است. بعدها این روش با تلاش گلدبرگ ۱۹۸۹، جایگاه خود را پیدا کرد و امروزه نیز به دلیل توانایی های خویش جای معتبری در  میان دیگر روش ها دارد.

الگوریتم های ژنتیک معمولاً به عنوان یک شبیه ساز کامپیوتر که در آن جمعیت یک نمونه انتزاعی(کروموزومها) از نامزدهای راه حل یک مسئله بهینه سازی به راه حل بهتری منجر می شوند، پیاده سازی می شوند. به طور سنتی راه حل ها به شکل رشته هایی از ۰ و ۱ بودند اما امروزه به شکل گونه های دیگری نیز پیاده می شوند.

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

به عنوان مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از ارزش رگرسیون خطی ساده و عوامل خارجی مدل کنیم، این فرمول تولید خواهد شد:  قیمت نفت در زمان t=ضریب ۱ نرخ بهره در زمان t+ضریب ۲ نرخ بیکاری در زمان t+ثابت ۱. آن گاه از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابت ها جهت مدل کردن قیمت نفت استفاده می شود. در این روش دو نکته وجود دارد: اول این که این روش خطی است. دوم این که ما به جای اینکه در میان«فضای پارامترها» جستجو کنیم، پارامترهای مورد استفاده را مشخص کرده ایم.

با استفاده از الگوریتم ژنتیک، ما یک ابر فرمول یا طرح تنظیم می کنیم که چیزی شبیه به«قیمت نفت در زمان t تابعی از حداکثر ۴ متغیر است» را بیان می کند. آن گاه داده ها را برای گروهی از متغیرهای مختلف(حدود ۲۰ متغیر) فراهم خواهیم کرد. در نتیجه الگوریتم ژنتیکی اجرا خواهد شد که بهترین تابع و متغیرها را جست و جو می کند. روش کار الگوریتم ژنتیک، به طرز فریبنده ای ساده و قابل درک می باشد و به طور قابل توجهی روشی است که ما باور داریم حیوانات آن گونه تکامل یافته اند. هر فرمولی که از طرح داده شده بالا تبعیت می کند، فردی از جمعیت فرمول های ممکن به حساب می آید. متغیرهایی که هر فرمول ارائه شده را بیان می کنند، به عنوان یک سری از اعداد نشان داده می شوند که معادل[دی ان ای|دی.ان.ای](DNA) آن فرد را تشکیل می دهند.

موتور الگوریتم ژنتیک، یک جمعیت اولیه از فرمول ایجاد می کند. هر فرد در مقابل مجموعه ای از داده ها مورد آزمایش قرار می گیرد و مناسب ترین آن ها(شاید ۱۰ درصد از مناسب ترین ها) باقی می مانند و بقیه کنار گذاشته می شوند. مناسب ترین افراد با هم جفت گیری(جا به جایی عناصر دی ان دی) و تغییر(تغییر تصادفی عناصر دی ان دی) کرده اند. الگوریتم ژنتیک، با گذشت از نسل های زیاد به سمت فرمول های دقیقتر متمایل می شود. در حالی که شبکه های عصبی هم غیرخطی و هم غیر پارامتریک هستند. جذابیت زیاد این الگوریتم این است که نتایج نهایی در آن قابل ملاحظه ترند. فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بود و برای ارائه سطح اطمینان نتایج می توان از تکنیک های آماری متعارف بر روی این فرمول ها استفاده کرد. فناوری الگوریتم های ژنتیک همواره در حال پیشرفت است و برای مثال با مطرح کردن معادله ویروس ها که در کنارفرمول ها و برای نقض کردن فرمول های ضعیف تولید می شوند و در نتیجه جمعیت را کلاً قوی تر می سازند. گفته می شود که الگوریتم ژنتیک(GA)یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند. مسئله ای که باید حل شود ورودی است و راه حل ها مطابق با الگو کدگذاری می شوند که تابع fitness نام دارد و هر راه حل کاندید را ارزیابی می کند که اکثر آن ها به طور تصادفی انتخاب شده اند.

راه حل ها این الگوریتم به صورت ۲ تایی(۰ و ۱)نمایش داده می شوند اما روش های دیگری نیز برای نمایش وجود دارد. تکامل از یک مجموعه کاملاً تصادفی از موجودیت ها شروع می شود و در نسل های بعدی تکرار می شود. در هر نسل نیز بهترین ها انتخاب نمی شوند بلکه مناسب ترین ها انتخاب می شوند.

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

برای هر فرد یک جفت والد انتخاب می شود. انتخاب ها نیز به شکلی هستند که مناسب ترین باشند تا ضعیف ترین عناصر هم شانس انتخاب داشته باشند. این کار موجب می شود تا از نزدیک شدن به جواب محلی جلوگیری شود. چندین الگوی انتخاب وجود دارد: چرخ منگنه دار(رولت)، انتخاب مسابقه ای(Tournament)…

به طور معمول الگوریتم های ژنتیک یک عدد احتمال اتصال دارد که بین ۰.۶ و ۱ است که احتمال به وجود آمدن فرزند را نشان می دهد. ارگانیسم ها با این احتمال دوباره با هم ترکیب می شوند. اتصال ۲ کوروموزوم، فرزند ایجاد می کند که به نسل بعدی افزوده می شوند. این کارها اعمال می شود تا کاندیدای مناسبی برای جواب در نسل بعدی پیدا شود. مرحله بعدی، تغییر دادن فرزندان جدید است. الگوریتم های ژنتیک یک احتمال تغییر کوچک و ثابت دارند که معمولاً درجه ای در حدود ۰.۰۱ یا کمتر دارد. بر اساس این احتمال، کروموزوم های فرزند به طور تصادفی تغییر می کنند یا جهش می یابند(مخصوصاً با جهش بیت ها در کروموزوم ساختمان داده ها).

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

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

در هر مسئله قبل از کاربرد الگوریتم ژنتیک، برای یافتن پاسخ باید دو عنصر به کار برد: اول روشی برای ارائه جواب به شکلی که الگوریتم ژنتیکی بتواند روی آن عمل کند، لازم است. به شکل سنتی یک جواب به صورت رشته ای از بیت ها، نویسه ها یا اعداد نمایش داده شود. دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. به عنوان مثال اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند، بدون اینکه کوله پشتی پاره شود(مئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می تواند به شکل رشته ای از بیت های ۰ و ۱ در نظر گرفته شود، که ۰ و ۱ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است. تناسب با پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می شود. روال بهینه یابی این الگوریتم بر اساس یک روند تصادفی_هدایت شده استوار می باشد. این روش بر مبنای نظریه تکامل تدریجی و ایده های بنیادین داروین بنا نهاده شد. در این روش، ابتدا برای تعدادی ثابت که جمعیت نامیده می شود، مجموعه ای از پارامترهای هدف به صورت اتفاقی تولید می شود، بعد از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه ای از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می کنیم. آن گاه با فراخوانی عملگرهای این الگوریتم از جمله لقاح، انتخاب نسل و جهش نسل بعد را شکل می دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.
به صورت متداول سه معیار به عنوان معیار توقف شمرده می شود:۱- زمان اجرای الگوریتم ۲-تعداد نسل هایی که ایجاد می شوند ۳- همگرایی معیار خطا

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

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

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

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

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

منبع : آرگا