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

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

مقدمه:

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

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

الگوریتم های ژنتیک با توجه به نظریه داروین در مورد تکامل شکل گرفتند.
محاسبات تکاملی درسال ۱۹۶۰ به وسیله ی شخصی به نام ریچنبرگ مرسوم شد
در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده اصلی استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد
در سال ۱۹۹۲ جان کوزا از ژنتیک الگوریتم در برنامه ای استفاده کرد که کارهای مشخصی انجام می داد کوزا، نام این روش رابرنامه ی ژنتیک گذاشت

Genetic Program: GP برنامه ی ژنتیک

تعاریف

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

Colony= جمعیت

Fitness= تابع تناسب

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

اصول کار الگوریتم ژنتیک به صورت روند زیر ارائه می گردد

گام اول: کد گذاری
گام دوم: انتخاب تصادفی جمعیت اولیه از مجموعه پاسخ ها
گام سوم: محاسبه میزان سازگاری گروه پاسخ با تابع هدف
گام چهارم:‌ ایجاد جمعیت جدید با استفاده از عملگر های ژنتیک (تکثیر ترکیب و جهش)
گام پنجم: تکرار مراحل سوم و چهارم تا هنگامی که جواب نهایی همگرا گردد

روش نمایش ژنوم ها: کد کردن ژنوم

استفاده از رشته های باینری
کدکردن راه حل ها در آرایه ای از اعداد صحیح یا اعشاری
استفاده از یک رشته حروف،که هر حرف نمایش دهنده یک خصوصیت از راه حل است
برنامه نویسی ژنتیک

روش های انتخاب

Elitist

Roulette

Scaling

Tournament

اپراطورهای ژنتیکی

اپراتور کراس آور با استفاده از دو رشته والد دو رشته فرزند بوجود می آورد.
برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی میشود.
انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود
single-point crossover
Two-point crossover
Uniform crossover
برای تعیین محل بیتهای کپی شونده از یک رشته به نام ؛کراس آور ماسک؛ استفاده میشود.
Crossover Mask

error: Content is protected !!
X