الگوریتم ژنتیک چیست و چه کاربردی دارد؟

[sinabed1393]

الگوریتم ژنتیک چیست و چه کاربردی دارد؟
نویسنده: پرشان شاکری فرتاریخ انتشار: ۱۳۹۶/۰۶/۰۵در: مقالات رباتیک و هوش مصنوعی

[font=Yekan, serif]الگوریتم ژنتیک چیست؟[/font]

الگوریتم ژنتیک (Genetic Algorithm)، روشی برای حل مسائل بهینه سازی قید دار و بدون قید است که بر مبنای نظریه انتخاب طبیعی ( فرآیندی که تکامل زیست شناسی را پیش می برد) عمل می کند.

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

الگوریتم ژنتیک در هر مرحله، برای ایجاد نسل بعد از جمعیت فعلی از سه نوع قانون اصلی استفاده می کند:

[list]
[*]قوانین انتخاب،جواب های منفرد که به آن ها والدین گفته می شود را انتخاب می کنند.
[*]قوانین جابجایی ویژگی های والدین را با یکدیگر ترکیب می کنند تا فرزند آن ها که عضو نسل بعد خواهد بود را تشکیل دهند.
[*]قوانین جهش به صورت تصادفی تغییراتی را بر روی یکی از والدین( یا هر دوی آن ها) اعمال می کنند تا فرزندان نسل بعد را تشکیل دهند.
[/list]

تفاوت های الگوریتم ژنتیک با الگوریتم بهینه سازی کلاسیک که بر مبنای مشتق گیری است در جدول زیر خلاصه شده است:

[size=undefined]
الگوریتم کلاسیک
الگوریتم ژنتیک
در هر مرحله محاسباتی، یک نقطه ایجاد می شود. دنباله این نقاط به جواب بهینه میل می کند.
در هر مرحله محاسباتی، مجموعه ای از نقاط ایجاد می شود. بهترین نقطه در جمعیت به جواب بهینه میل می کند.
نقطه بعدی دنباله را با محاسبات قطعی تعیین و مشخص می کند.
جمعیت نسل بعد، با محاسباتی که از اعداد تصادفی استفاده می کند مشخص می شود.

تاریخچه الگوریتم ژنتیک[/size]

الگوریتم های ژنتیک به منظور تقلید از برخی فرآيند ها که در تکامل طبیعی موجودات زنده مشاهده می شد ابداع شدند. این نکته که حیات به همراه پیچیدگی هایی که در آن مشاهده می شود، توانسته در بازه نسبتا کوتاهی از زمان، که از آثار فسیل ها برآورد می شود، تکامل بیابد بسیاری از افراد، از جمله زیست شناسان را متحیر کرده است. ایده اصلی الگوریتم ژنتیک(GA)، استفاده از قدرت فرآیند تکامل برای حل مسائل بهینه سازی است. پدر الگوریتم ژنتیک اولیه، John Holland است که آن را در اوائل دهه 1970 میلادی ابداع کرد.

[size=undefined]
مفهوم الگوریتم ژنتیک[/size]

الگوریتم ژنتیک (GA)، یک الگوریتم جستجوی ابتکاری انطباق پذیر است که بر مبنای ایده های تکاملی انتخاب طبیعی و ژنتیک طراحی شده است. به این ترتیب این الگوریتم نمایانگر استفاده ی هوشمند از یک الگوریتم جستجوی تصادفی برای حل مسائل بهینه سازی می باشد. اگرچه الگوریتم های ژنتیک از پدیده هایی تصادفی استفاده می کنند اما خودشان به هیچ وجه تصادفی نیستند بلکه، آن ها از اطلاعات تاریخی موجود برای هدایت عملیات جستجو به منطقه ای با عملکرد بهتر در فضای جستجو استفاده می کنند. روش های اصلی الگوریتم ژنتیک به گونه ای طراحی شده اند تا بتوانند فرآیند های ضروری برای تکامل در سیستم های طبیعی را شبیه سازی کنند. از جمله مهمترین این فرآیند ها، آن هایی هستند که از قوانینی که اولین بار توسط چارلز داروین و با نام “بقای اصلح”(Survival Of The Fittest) مطرح شد، پیروی می کنند. علت این امر آن است که در طبیعت، رقابت میان موجودات زنده برای دستیابی به منابع کمیاب منجر به غلبه اصلح ترین موجودات بر موجودات ضعیف تر می شود.

[size=undefined]
چرا الگوریتم ژنتیک؟[/size]

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

[size=undefined]
بررسی اجمالی الگوریتم ژنتیک[/size]

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

الگوریتم های ژنتیک با استفاده از مبانی خاص، مشابه ساختار های ژنتیکی و رفتار کروموزوم ها در میان جمعیتی از افراد، عمل می کنند. این مبانی عبارتند از:

[list]
[*]اعضای یک جمعیت برای منابع و جفت گیری با یکدیگر رقابت می کنند.
[*]اعضایی که در هر رقابت موفق تر هستند فرزندان بیشتری را نسبت به اعضایی که عملکرد مناسبی نداشته اند ایجاد می کنند.
[*]ژن هایی از اعضای با عملکرد خوب در درون جمعیت منتشر می شود بنابراین، والدین خوب گاهی اوقات صاحب فرزندی می شوند که از هر کدام از والدین بهتر است.
[*]بنابراین، هر نسل متوالی برای زندگی در محیط اطراف خود مناسب تر خواهد بود.
[/list][size=undefined]
 فضای جستجو[/size]

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

[img=420x0]http://mediasoft.ir/wp-content/uploads/2017/08/Genetic-1.jpg[/img]

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

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

[size=undefined]
نحوه اجرا الگوریتم ژنتیک[/size]

بر مبنای انتخاب طبیعی

پس از این که نسل اولیه به صورت تصادفی ایجاد شد، الگوریتم ژنتیک با استفاده از 3 عملگر، شروع به تکامل این نسل اولیه خواهد کرد:

انتخاب: که معادل همان قانون بقای اصلح است.

جابجایی: که نمایانگر جفت گیری میان اعضای جامعه است.

جهش: که اصلاحاتی را به صورت تصادفی وارد مسئله می کند.

[list=1]
[*]عملگر انتخاب
[/list]
[list]
[*]ایده اصلی: اولویت دادن به اعضای بهتر که به آن ها اجازه می دهد تا ژن هایشان را به نسل بعدی منتقل کنند.
[*]خوب بودن هر عضو به مقدار برازندگی آن عضو بستگی دارد.
[*]برازندگی را می توان با کمک یک تابع هدف و یا با قضاوت ذهنی تعیین کرد.
[/list]
[list=1]
[*]عملگر جابجایی
[/list]
[list]
[*]اصلی ترین عامل مشخصه الگوریتم ژنتیک نسبت به سایر روش های بهینه سازی
[*]دو عضو از جمعیت با استفاده از عملگر انتخاب به عنوان والدین انتخاب می شوند
[*]یک موقعیت مکانی در بین رشته بیت ها به صورت تصادفی انتخاب می شود.
[*]مقادیر دو رشته تا محل مشخص شده با یکدیگر جابجا می شوند
[*]اگر S1=000000 و S2=111111 و محل جابجایی 2 باشد، در این صورت S1’=110000 و S2’=001111 خواهد بود
[*]دو فرزندی که از طریق این فرآیند حاصل می شوند وارد نسل بعدی جمعیت خواهند شد.
[*]با ترکیب دوباره بخش هایی از اعضای خوب جامعه، این فرآیند احتمالا منجر به ساخت فرزندانی بهتر از والدین خواهد شد.
[/list]

[img=497x0]http://mediasoft.ir/wp-content/uploads/2017/08/Genetic-2.jpg[/img]

[list=1]
[*]عملگر جهش
[/list]
[list]
[*]با احتمالی بسیار کم، بعضی از بیت های بخشی از اعضای نسل جدید(فرزندان نسل قبل) تغییر داده می شود.
[*]هدف از این کار، حفظ گوناگونی و تنوع در میان اعضای یک جمعیت و جلوگیری از همگرایی زودرس و ناقص می باشد.
[*]عملگر جهش به تنهایی باعث ایجاد یک جستجوی تصادفی در فضای جستجو می شود.
[*]جهش و انتخاب( بدون عملگر جابجایی) باعث ایجاد الگوریتم تپه نوردی موازی و مقاوم در برابر نویز می شوند.
[/list]

[img=497x0]http://mediasoft.ir/wp-content/uploads/2017/08/Genetic-3.jpg[/img]

[size=undefined]
تاثیر عملگر های ژنتیکی[/size]
[list]
[*]تنها استفاده از عملگر انتخاب منجر به پر کردن جمعیت با نسخه هایی مشابه با بهترین عضو جمعیت خواهد شد.
[*]استفاده از عملگر های انتخاب و جابجایی منجر به همگرایی الگوریتم به جوابی خوب اما نه کاملا بهینه خواهد شد.
[*]عملگر جهش به تنهایی باعث ایجاد یک جستجوی تصادفی در فضای جستجو می شود.
[*]استفاده از انتخاب و جهش باعث ایجاد الگوریتم تپه نوردی موازی و مقاوم در برابر نویز خواهد شد.
[/list][size=undefined]
الگوریتم[/size]
[list=1]
[*]ایجاد جمعیت اولیه (t) به صورت تصادفی
[*]تعیین برازندگی جمعیت اولیه (t)
[*]تکرار موارد زیر:
انتخاب والدین از جمعیت (t)
استفاده از عملگر جابجایی بر روی والدین و و ایجاد جمعیت (t+1)
استفاده از عملگر جهش بر روی جمعیت (t+1)
تعیین برازندگی جمعیت (t+1)
[*]تاجایی که بهترین عضو هر جامعه به اندازه کافی مناسب باشد.
[/list][size=undefined]
جمع بندی[/size]

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

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