الگوریتم ژنتیک (GA-Genetic Algorithm)
الگوریتم ژنتیک (Genetic Algorithm) یک تکنیک برنامه نویسی می باشد که از تکامل بیولوژیکی تقلید می کند تا بتواند مسئله مورد نظر را حل کند . برای حل یک مسئله در ابتدا مجموعه ای از جواب های پیشنهادی به عنوان ورودی GA در نظر گرفته می شوند که معمولا به صورت تصادفی تولید می شوند که در واقع اولین نسل می باشند . یک معیار برای سنجش جواب ها وجود دارد که تابع سازگاری نامیده می شود . هر جواب توسط تابع سازگاری سنجیده می شود . چون جواب ها به طور تصادفی تولید شده اند بسیاری از آنها مناسب نمی باشند و بنابراین حذف می شوند اما تعدادی که بهتر از بقیه هستند برای ادامه حل مسئله نگه داشته می شوند . این جواب ها باید بازتولید شوند به این صورت که چندین کپی از آنها گرفته می شود اما چون کپی ها مناسب نیستند در حین کپی کردن آنها را به صورت تصادفی تغییر می دهند . بنابراین نسل بعدی ساخته می شود و جواب های پیشنهادی این نسل نیز توسط تابع سازگاری ارزیابی می شود . آنهایی که پس از تغییر بدتر شده اند و یا اینکه بهتر نشده اند یا باید تغییر داده شوند و یا اینکه حذف شوند . اما تعدادی که پس از تغییر بهتر شده اند انتخاب می شوند و از آنها برای نسل بعدی کپی برداری می شود و تغییراتی به صورت تصادفی در حین کپی کردن به آنها اعمال می شود و دوباره این روند تکرار می شود . انتظار این است که میانگین سازگاری جمعیت در هر دوره جدید افزایش یابد و پس از تکرارهای در حد چند صد و یا چند هزار ، جواب های بسیار مناسبی برای مسئله یافت شود .
روش های نمایش :
قبل از آن که الگوریتم زنتیک بتواند یک مسئله را حل کند باید جواب های پیشنهادی به نحوی کدگذاری شوند که کامپیوتر بتواند بر روی آنها پردازش های لازم را انجام دهد . یک روش متداول کدگذاری جواب ها به صورت رشته های باینری (صفر و یک) می باشد که در آن جواب ها به صورت رشته های 0 و 1 نمایش داده می شوند . روش دیگری که به کار می رود کدگذاری جواب ها به صورت آرایه هایی از اعداد صحیح و یا اعداد دسیمال (دهدهی) می باشد . این روش دارای دقت و پیچیدگی بیشتری می باشد و معمولا به فضای مسئله نزدیک تر است . روش سوم بیان جواب ها به صورت رشته هایی از حروف می باشد . ارزش سه روش ذکر شده این است که به راحتی می توان عملگرهایی را برای تغییر تصادفی جواب های پیشنهادی ، تعریف نمود : تغییر 0 به 1 و یا برعکس ، اضافه یا کم کردن مقدار یک عدد با یک مقدار انتخاب شده به صورت تصادفی یا تغییر یک حرف به حرفی دیگر .
در روشی دیگر که برنامه نویسی ژنتیک (Genetic programming) نام دارد ، برنامه ها به صورت ساختارهای اطلاعات شاخه ای که به آنها درخت گفته می شود ، نمایش داده می شوند .
در شکل زیر، سه مثال از روش نمایش برنامه نویسی ژنتیک، نمایش داده شده است :
در این روش تغییرات تصادفی به صورت تغییر یک عملگر یا تغییر دادن مقدار درون یک گره در درخت و یا جایگزینی یک زیردرخت با یکی دیگر ، اعمال می شوند .
الگوریتم های تکاملی احتیاجی ندارند که جواب های پیشنهادی را به صورت رشته های اطلاعاتی با طول محدود نمایش دهند . برخی آنها را این گونه نمایش می دهند و برخی خیر . به عنوان مثال نحوه کدگذاری درختی که ذکر شد می تواند درخت را تا هر اندازه که برای حل مسئله لازم می باشد گسترش دهد و بزرگ کند .
روش های انتخاب :
روش های گوناگونی برای انتخاب افرادی که باید به نسل بعدی کپی شوند وجود دارد :
انتخاب نخبه گرایانه (Elitist selection) :
اغلب افراد سازگار هر نسل انتخاب می شوند .
انتخاب سازگار- متناسب (Fitness-proportionate selection) :
افراد سازگارتر شانس بیشتری برای انتخاب دارند اما معلوم نیست که حتما انتخاب شوند .
انتخاب چرخ قمار (Roulette-wheel selection) :
شکلی از انتخاب سازگار- متناسب می باشد که در آن شانس انتخاب یک فرد متناسب با میزانی از سازگاری است که آن فرد از دیگر رقبای خود بیشتر یا کمتر دارد ( این انتخاب شبیه بازی چرخ قمار می باشد که چرخ به تکه های مختلف تقسیم شده است و گلوله کوچکی درون آن گذاشته می شود و سپس چرخ چرخانده می شود . تکه ها به گونه ای انتخاب می شوند که افرادی که دارای سازگاری بیشتری هستند تکه های بزرگتری داشته باشند . )
انتخاب مقیاس بندی (Scaling selection) :
همان طور که میانگین سازگاری جمعیت افزایش می یابد ، شرایط انتخاب سخت تر شده و تابع سازگاری معیارهای انتخاب خود را دشوارتر می کند . این روش زمانی مناسب است که تمام افراد نسبتا دارای سازگاری بالایی باشند و تنها تفاوت های کوچکی در میزان سازگاری آنها وجود داشته باشد .
انتخاب مسابقه ای (Tournament selection) :
زیرگروه هایی از افراد جمعیت بزرگتر انتخاب می شوند و افراد هر زیر گروه با یکدیگر رقابت می کنند . تنها یک فرد از هر زیرگروه برای بازتولید انتخاب می شود .
انتخاب رتبه بندی (Rank selection) :
به هر فرد بر اساس میزان سازگاری یک رتبه داده می شود و انتخاب به جای این که بر اساس اختلاف های مطلق در سازگاری باشد ، بر اساس رتبه افراد صورت می گیرد . فایده این روش انتخاب این است که می تواند از اینکه افراد بسیار سازگار در مراحل اولیه بر دیگر افراد با سازگاری کمتر غلبه پیدا کنند ، جلوگیری نماید زیرا در صورتی که این اتفاق بیفتد تنوع ژنتیکی جمعیت کاهش پیدا می کند که می تواند از پیدا کردن یک جواب قابل قبول جلوگیری نماید .
انتخاب نسلی (Generational selection) :
نوزادان افراد انتخاب شده از هر نسل ، کل نسل بعدی را تشکیل می دهند . هیچ فردی از یک نسل به نسل دیگر باقی نمی ماند .
انتخاب حالت دائمی (Steady-state selection) :
نوزادان افراد انتخاب شده از هر نسل به منبع ژنی که از قبل موجود بوده است می روند و جایگزین تعدادی از اعضا می شوند که دارای سازگاری کمتری در نسل قبل بوده اند . برخی از افراد بین نسل ها باقی می مانند .
انتخاب مرتبه ای (Hierarchical selection) :
افراد هر نسل در مراحل گوناگونی انتخاب می شوند . مراحل ارزیابی پایین تر ، سریعتر می باشند و کمتر تفاوت قائل می شوند در حالیکه کسانی که برای مراحل بالاتر باقی می مانند به صورت سخت تری مورد ارزیابی قرار می گیرند . فایده این روش این است که زمان محاسبه کلی را کاهش می دهد زیرا ارزیابی های سریعی را برای اکثر افراد انجام می دهد و سپس تنها برای کسانی که از مراحل آسان تر عبور کنند ارزیابی های سنگین تر و دارای محاسبات بیشتر را انجام می دهد .
روش های تغییر :
زمانی که تعدادی از افراد انتخاب می شوند با این امید که میزان سازگاری آنها بیشتر شود باید آنها را تغییر بدهیم . دو روش اصلی برای تغییر افراد منتخب وجود دارد .
روش جهش (Mutation) :
در این روش یک تغییر کوچک در نقاط تنها در کد افراد داده می شود .
مثالی برای روش تغییر جهش که در آن، یک رقم از کد فرد از 0 به 1 تبدیل شده است را می توانید در شکل زیر ببینید :
روش دورگه کردن (Crossover) :
در این روش دو فرد انتخاب می شوند و بخشی از کدهای آنها معاوضه می شود و یک نوزاد از ترکیب این والدین به وجود می آید . شکل متداول دورگه کردن ، دورگه کردن تک نقطه ای می باشد که یک نقطه تبادل در یک نقطه تصادفی از ژن والدین انتخاب می شود ، بخشی از ژن نوزاد که قبل از نقطه می باشد از یک فرد و بخش دیگر از فرد دیگر گرفته می شود تا ژن نوزاد تشکیل شود .
مثالی برای روش تغییر دورگه کردن . 3 رقم سمت راست کد نوزاد از نفر اول و 5 رقم سمت چپ کد نوزاد از نفر دوم گرفته شده است را می توانید در شکل زیر ببینید :
