الگوریتم ژنتیک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(رمزگذاری) است. در این مرحله بعد از این که الگوریتم بهترین جواب را برای مساله ارایه کرد، لازم است عکس عمل رمزگذاری روی جوابها اعمال شود.
[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