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

الگوریتم ژنتیک     Genetic Algorithm   -   GA

تاریخچه:
مقوله ژنتیک توسط چارلز داروین در سال 1859 به طور جدی با بیان فرضیه تکامل مطرح شد و در سال 1903 کروموزوم به عنوان واحد وراثت معرفی گردید. در سال 1905 واژه ژنتیک توسط یک زیست شناس انگلیسی بنام ویلیام ویستون وضع گردید .
در سال 1927 واژه جهش برای بیان تغییرات فیزیکی در ژنها وضع شد و در سال 1931 واژه برش یا همبری وضع گردید.
در سال 1953 ساختار DNA  بطور کامل به شکل مارپیچی توسط جیمز واتسون و فرانسیس کریک توضیح داده شد که برای آن جایزه نوبل را نیز به ارمغان آورد.

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

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

تابع برازش Fitness
برای اینکه بتوانیم موجودات بهتر را درون جمعیت شناسایی کنیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم . ارزیابی اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد به آن نسبت می دهیم این برای مو جودات بهتر بزرگتر (MAX) و یا کوچکتر (MIN) است را شایستگی  آن موجود می نامیم

الگوریتم ژنتیک
روش متداول پیاده سازی الگوریتم ژنتیک بدین ترتیب است:
مجموعه ای از کروموزوم ها (افراد)که جمعیت نامیده می شود تولید و به طور متناوب با کروموزوم های جدید جایگزین میشوند.
در هر بار تکرار تمامی کروموزوم ها (فرضیه ها) با استفاده از تابع برازش fitness  مورد ارزیابی قرار می گیرد آنگاه تعدادی ار بهترین آنها با استفاده از این تابع انتخاب می شود و جمعیت جدید را تشکیل می دهد.
تعدادی از این فرضیه های انتخاب شده به همان صورت مورد استفاده قرار می گیرد و ما بقی با استفاده از اپراتورهای ژنتیکی نظیر Crossover  و Mutation  برای تولید فرزندان بکار می رود.

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

Evaluation
تابع برازندگی این تابع هر رشته را با یک مقدار عددی ارزیابی می کند

Crossover ( ادغام )
مهمترین عملگر در الگوریتم ژنتیک عملگر ترکیب است . ترکیب ، فرآیندی است که در آن نسل قدیمی کروموزوم ها با یکدیگرمخلوط و ترکیب می شوند تا نسل جدیدی بوجود آورند
اپراتور Crossover با استفاده از دو  رشته والد دو رشته فرزند بوجود میآورد.
برای اینکار قسمتی از بیتهای والدین در بیتهای فرزندان کپی میشود.
انتخاب بیت هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود
single-point crossover

Two-point crossover

Uniform crossover

برای تعیین محل بیتهای کپی شونده از یک رشته به نام Crossover Mask  استفاده میشود

 

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

Decoding(رمز گشایی)
عکس عمل encoding  است . جواب ها را رمز گشایی می کنیم تا به نسخه واقعی جواب برسیم.

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

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

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

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

کدینگ درختی:
در این نوع کد گذاری یک درخت دودویی برای عبارت (کروموزوم) تشکیل می‌دهیم که معادل درخت پارس است و تمام اعمال مربوط به درخت پارس بر روی درخت قابل انجام است.این روش در نرم افزارهایی که تحت عنوان «کدهای الگوریتم ژنتیک» برای یک مسئلۀ خاص نوشته می‌شوند استفاده می‌شود. «لیسپ»

 
روش‌های انتخاب: Selection

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

منبع مطالب:

الگوریتم های فرا اکتشافی جستجو - الگوریتم های ژنتیک - مصطفی عباسی کیا