Genetic algorithm

الگوریتم ژنتیکGA[1]، یک روش اماری و تکنیک جستجو در علم رایانه به منظور یافتن راه‌حل تقریبی برای بهینه‌سازی و مسایل جستجو است، الگوریتم ژنتیک نوع خاصی از الگوریتم­های تکاملی است که از تکنیک­های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. ویژگی­های خاص این الگوریتم باعث می­شود. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی هستند. مختصرا گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مساله استفاده می‌کند. مساله‌ای که باید حل شود ورودی است و راه‌حل­ها طبق یک الگو کدگذاری می‌شوند و توسط تابعی که تابع fitness نام دارد، سنجیده می­شود و این تابع هر راه حل کاندید را ارزیابی می‌کند که اکثر ان­ها به صورت تصادفی انتخاب می‌شوند. به طور کلی، این الگوریتم‌ها از بخش­های زیر تشکیل می‌شوند : تابع برازش – نمایش – انتخاب – تغییر.

همچنین مطالب زیر را مطالعه کنید:

سمینار کارشناسی ارشد| رایانش ابری| فایل لاتک|بررسی رتبه‌بندی سرویس­های ابری با اعمال رویکردی برای حل مسائل چندهدفه

ویدیوی آموزش پیاده سازی مقاله رتبه بندی سرویس های ابری بصورت الگوریتم چندهدفه

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

هدف اصلی روش‌های هوشمند به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسایل مهندسی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک، مقدار ماکزیمم تابع را بیابیم. مثلا از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از ان متوقف خواهد شد. اما در روش‌های هوشمند مخصوصا الگوریتم ژنتیک، به دلیل خصلت تصادفی ان­ها، حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه، نقطه Aبه صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی[2]را خواهیم داشت]21[. برای شناخت الگوریتم ژنتیک، لازم است تعاریف زیر انجام شود:

  • شخص:[3]یک جواب کاندید برای مساله که معمولا به صورت رشته بیتی نمایش داده می­شود.
  • ژن[4]: هر بیت در شخص است و واحدپایه ژنتیک است.
  • فرم[5]: حالت­های مختلف هر ژن را می­گویند، اگر رشته بیتی باشد دارای مقادیر 0یا 1می­باشد.
  • لوکاس[6]: موقعیت هر ژن بر روی کروموزوم را گویند.
  • جمعیت[7]: مجموعه­ای از اشخاص که سایز ان معمولا ثابت است.
  • کروموزوم[8]: به گروهی از ژن­ها اطلاق می­شود.

الگوریتم ژنتیک، الگوریتمی اتفاقی است که از تکامل طبیعی تقلید می­کند. جنبه­ای که این الگوریتم را مجزا می­کند، این است که مجموعه­ای از جواب­ها را که اشخاص یا کروموزوم نامیده می­شود، در یک جمعیت نگه می­دارد. همانند تکامل زیستی، دارای مکانیزمی است که بهترین و مناسب­ترین کروموزوم را در هر نسل انتخاب می­کند. به منظور شبیه­سازی فرایند تکامل، کروموزوم­های انتخاب شده تحت تاثیر عملگر­های ژنتیک همانند ترکیب  و  جهش قرار می­گیرند [17]. الگوریتم ژنتیک دارای پنج مرحله می­باشد که بدین ترتیب است:

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

ترکیب، دو کروموزوم را با انتخاب تصادفی موقعیتی مانند P ترکیب می­کند که  Pمقداری کمتر یا مساوی طول کروموزوم­ها است. اگر تعداد (طول) ژن­ها در کروموزوم­ها Nباشد، از دو کروموزوم والد، دو فرزند به صورت زیر به وجود می­اید. یک فرزند با کپی کردن ژن­های 1,…,(P-1)از کروموزوم والد اول و ژن­های P,…,Nاز کروموزوم والد دوم ساخته می­شود. فرزند دیگر به طور مشابه، این بار با کپی کردن ژن­های 1,…,(P-1)از کروموزوم والد دوم و ژن­های P,…,Nاز کروموزوم والد اول به وجود می­اید. در این ترکیب از دو والد، دو فرزند به وجود می­اید.

جهش نیز عملگر دیگری است که جواب­های ممکن دیگری را متولد می­کند. در الگوریتم ژنتیک بعد از این که یک عضو در جمعیت جدید به وجود امد، هر ژن ان با احتمال جهش، جهش می­یابد. در جهش ممکن است ژنی از مجموعه ژن­های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است، به ان اضافه شود. جهش یک ژن به معنای تغییر ان ژن است و بسته به نوع کدگذاری، روش­های متفاوت جهش استفاده می­شود. می­توان استنباط کرد که مهم­ترین وظیفه جهش، اجتناب از همگرایی به بهینه محلی است. در الگوریتم ژنتیک با کدگذاری باینری، این عمل با تولید تصادفی یکی از اعداد 0یا 1و جایگزینی ان به جای بیت موردنظر صورت می­گیرد. اما در برخی کاربردهای ژننتیک، عمل جهش دودویی در یک بیت با متمم ساختن ان بیت انجام می­گیرد که این روش مناسب­تر است. رمزگشایی، عکس عمل Encoding(رمزگذاری) است. در این مرحله بعد از این که الگوریتم بهترین جواب را برای مساله ارایه کرد، لازم است عکس عمل رمزگذاری روی جواب­ها اعمال شود.

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

[1] Genetic Algorithm

[2] Global Optimal

[3] Individual

[4] Gene

[5] allele

[6] Locus

[7] Population

[8] chromosome

[9] Encoding

[10] Evaluation

[11] Crossover

[12] Mutation

[13] Decoding