روش جستجوی تکاملی
روشهای جستجوی ناآگاهانه، آگاهانه و فراابتکاری (به انگلیسی: Metaheuristic) برای حل مسائل هوش مصنوعی بسیار کارآمد می‌باشند. در مورد مسائل بهینه‌سازی اغلب روشهای آگاهانه و ناآگاهانه جوابگوی نیاز نخواهند بود چرا که بیشتر مسائل بهینه‌سازی در رده مسائل NP قرار دارند؛ بنابراین نیاز به روش جستجوی دیگری وجود دارد که بتواند در فضای حالت مسائل NP به طرف جواببهینه سراسری حرکت کند. بدین منظور روشهای جستجوی فراابتکاری مطرح می‌شوند، این روشهای جستجو می‌توانند به سمت بهینگی‌های سراسری مسئله حرکت کنند. در کنار روشهای جستجوی فراابتکاری، روشهای جستجوی دیگری نیز وجود دارند که به روشهای تکاملی معروفند.
نظریه تکامل
بر اساس نظریه تکاملداروین نسل‌هایی که از ویژگی‌های و خصوصیات برتری نسبت به نسل‌های دیگر برخوردارند شانس بیشتری نیز برای بقا و تکثیر خواهند داشت و ویژگی‌ها و خصوصیات برتر آنها به نسل‌های بعدی آنان نیز منتقل خواهد شد. همچنین بخش دوم نظریه داروین بیان می‌کند که هنگام تکثیر یک ارگان فرزند، به تصادف رویدادهایی اتفاق می‌افتد که موجب تغییر خصوصیات ارگان فرزند می‌شود و در صورتی که این تغییر فایده‌ای برای ارگان فرزند داشته باشد موجب افزایش احتمال بقای آن ارگان فرزند خواهد شد. در محاسبات کامپیوتری، بر اساس این نظریه داروین روش‌هایی برای مسائل بهینه‌سازی مطرح شدند که همه این روش‌ها از پردازش تکاملی در طبیعت نشات گرفته‌اند. به روشهای جستجو، الگوریتم‌های جستجوی تکاملی گفته می‌شود.
انواع مختلف الگوریتم‌های تکاملی
انواع مختلف الگوریتم‌های تکاملی که تا بحال مطرح شده‌اند، به شرح زیر می‌باشد:
الگوریتم ژنتیک
الگوریتم تکاملی
Evolutionary Strategies
Evolutionary Programming
Differential Evolution
Cultural Evolution
هم‌فرگشتی
کدگذاری و نحوه نمایش
نحوه نمایش جواب مسئله و ژن‌ها در موفقیت الگوریتم و نحوه پیاده‌سازی الگوریتم ژنتیک تأثیر بسیار مهمی دارد. در بیشتر مسائل نیز روشهای مختلفی برای نشان دادن جواب مسئله می‌توان طراحی کرد.
حل مسائل معروف با استفاده از الگوریتم ژنتیک
یکی از مسائل کلاسیک در الگوریتم‌های ژنتیک مسئله ۸ وزیر است. ماهیت مسئله به گونه‌ای است که مدلسازی آن و همچنین اعمال عملگرهای الگوریتم ژنتیک بر روی آن بسیار ساده است. همچنین علاوه برای الگوریتم ژنتیک، روش الگوریتم تبرید شبیه‌سازی شده نیز در ساده‌ترین شکل خود برای مسئله چند وزیر نیز روش مناسبی هست همچنین از مسائل مهم دیگری که با استفاده از این الگوریتم قابل حل می‌باشد مسئلهٔ فروشندهٔ دوره‌گرد یا مسئلهٔ چیدمان دینامیک می‌باشد.
فلو چارت این الگوریتم
منبع
الگوریتم ژنتیک چیست و چه کاربردی دارد؟
الگوریتم ژنتیک چیست؟
الگوریتم ژنتیک (Genetic Algorithm)، روشی برای حل مسائل بهینه سازی قید دار و بدون قید است که بر مبنای نظریه انتخاب طبیعی ( فرآیندی که تکامل زیست شناسی را پیش می برد) عمل می کند.
الگوریتم ژنتیک به طور مداوم جمعیتی از جواب های منفرد را اصلاح می کند. در هر مرحله، الگوریتم ژنتیک به صورت تصادفی افرادی را از نسل فعلی به عنوان والدین انتخاب می کند و از آن ها برای ایجاد فرزندان که خود اعضای نسل بعد هستند استفاده می کند. در طول نسل های متوالی، جمعیت جواب ها به سمت یک جواب بهینه “تکامل” پیدا می کند. شما می توانید از الگوریتم ژنتیک برای حل مسائل مختلف بهینه سازی که الگوریتم های استاندارد بهینه سازی برای حل آن ها مناسب نیست، استفاده کنید.
به عنوان نمونه ای از این دست مسائل می توان به مسائلی اشاره کرد که در آن تابع هدف ناپیوسته، مشتق ناپذیر، تصادفی و یا غیرخطی از مرتبه بالا می باشد. الگوریتم ژنتیک همچنین می تواند در حل مسائل برنامه ریزی عدد صحیح مختلط، که در آن برخی از اجزا محدود به مقادیر صحیح هستند نیز استفاده شود.
الگوریتم ژنتیک در هر مرحله، برای ایجاد نسل بعد از جمعیت فعلی از سه نوع قانون اصلی استفاده می کند:
- قوانین انتخاب،جواب های منفرد که به آن ها والدین گفته می شود را انتخاب می کنند.
- قوانین جابجایی ویژگی های والدین را با یکدیگر ترکیب می کنند تا فرزند آن ها که عضو نسل بعد خواهد بود را تشکیل دهند.
- قوانین جهش به صورت تصادفی تغییراتی را بر روی یکی از والدین( یا هر دوی آن ها) اعمال می کنند تا فرزندان نسل بعد را تشکیل دهند.
تفاوت های الگوریتم ژنتیک با الگوریتم بهینه سازی کلاسیک که بر مبنای مشتق گیری است در جدول زیر خلاصه شده است:
| الگوریتم کلاسیک | الگوریتم ژنتیک |
| در هر مرحله محاسباتی، یک نقطه ایجاد می شود. دنباله این نقاط به جواب بهینه میل می کند. | در هر مرحله محاسباتی، مجموعه ای از نقاط ایجاد می شود. بهترین نقطه در جمعیت به جواب بهینه میل می کند. |
| نقطه بعدی دنباله را با محاسبات قطعی تعیین و مشخص می کند. | جمعیت نسل بعد، با محاسباتی که از اعداد تصادفی استفاده می کند مشخص می شود. |
تاریخچه الگوریتم ژنتیک
الگوریتم های ژنتیک به منظور تقلید از برخی فرآيند ها که در تکامل طبیعی موجودات زنده مشاهده می شد ابداع شدند. این نکته که حیات به همراه پیچیدگی هایی که در آن مشاهده می شود، توانسته در بازه نسبتا کوتاهی از زمان، که از آثار فسیل ها برآورد می شود، تکامل بیابد بسیاری از افراد، از جمله زیست شناسان را متحیر کرده است. ایده اصلی الگوریتم ژنتیک(GA)، استفاده از قدرت فرآیند تکامل برای حل مسائل بهینه سازی است. پدر الگوریتم ژنتیک اولیه، John Holland است که آن را در اوائل دهه 1970 میلادی ابداع کرد.
مفهوم الگوریتم ژنتیک
الگوریتم ژنتیک (GA)، یک الگوریتم جستجوی ابتکاری انطباق پذیر است که بر مبنای ایده های تکاملی انتخاب طبیعی و ژنتیک طراحی شده است. به این ترتیب این الگوریتم نمایانگر استفاده ی هوشمند از یک الگوریتم جستجوی تصادفی برای حل مسائل بهینه سازی می باشد. اگرچه الگوریتم های ژنتیک از پدیده هایی تصادفی استفاده می کنند اما خودشان به هیچ وجه تصادفی نیستند بلکه، آن ها از اطلاعات تاریخی موجود برای هدایت عملیات جستجو به منطقه ای با عملکرد بهتر در فضای جستجو استفاده می کنند. روش های اصلی الگوریتم ژنتیک به گونه ای طراحی شده اند تا بتوانند فرآیند های ضروری برای تکامل در سیستم های طبیعی را شبیه سازی کنند.
از جمله مهمترین این فرآیند ها، آن هایی هستند که از قوانینی که اولین بار توسط چارلز داروین و با نام “بقای اصلح”(Survival Of The Fittest) مطرح شد، پیروی می کنند. علت این امر آن است که در طبیعت، رقابت میان موجودات زنده برای دستیابی به منابع کمیاب منجر به غلبه اصلح ترین موجودات بر موجودات ضعیف تر می شود.
چرا الگوریتم ژنتیک؟
الگوریتم ژنتیک به دلیل قدرت و دوام بیشتر نسبت به سایر روش های مبتنی بر هوش مصنوعی، بهتر است. بر خلاف سیستم های هوش مصنوعی قدیمی تر، الگوریتم ژنتیک با تغییر اندک مقادیر ورودی و یا با وجود مقادیر قابل توجهی از نویز در سیستم به راحتی قطع نمی شود. علاوه بر این، در جستجوی یک فضای حالت بزرگ، فضای حالت Multimodal و یا یک رویه چند بعدی، استفاده از الگوریتم ژنتیک مزیت های بسیار بیشتری نسبت به روش های جستجوی متداول در سایر تکنیک های بهینه سازی مانند برنامه ریزی خطی، جستجوی تصادفی و یا روش های جستجوی اول عمق، اول سطح و یا praxis دارد.
بررسی اجمالی الگوریتم ژنتیک
الگوریتم های ژنتیک برای حل مسئله، اصل بقای اصلح را در میان اعضای یک جمعیت در طی نسل های متوالی شبیه سازی می کنند. هر نسل شامل جمعیتی از رشته کاراکتر ها است که مشابه کروموزوم هایی که در DNA ما دیده می شوند می باشند. هر فرد، نمایانگر یک نقطه در فضای جستجو و یک راه حل احتمالی خواهد بود. سپس اعضای هر نسل، در فرآیندی مشابه فرآیند تکامل موجودات زنده وارد می شوند.
الگوریتم های ژنتیک با استفاده از مبانی خاص، مشابه ساختار های ژنتیکی و رفتار کروموزوم ها در میان جمعیتی از افراد، عمل می کنند. این مبانی عبارتند از:
- اعضای یک جمعیت برای منابع و جفت گیری با یکدیگر رقابت می کنند.
- اعضایی که در هر رقابت موفق تر هستند فرزندان بیشتری را نسبت به اعضایی که عملکرد مناسبی نداشته اند ایجاد می کنند.
- ژن هایی از اعضای با عملکرد خوب در درون جمعیت منتشر می شود بنابراین، والدین خوب گاهی اوقات صاحب فرزندی می شوند که از هر کدام از والدین بهتر است.
- بنابراین، هر نسل متوالی برای زندگی در محیط اطراف خود مناسب تر خواهد بود.
فضای جستجو
الگوریتم ژنتیک، به طور مداوم جمعیتی از n کروموزوم (جواب) را به همراه مقدار برازندگی هرکدام حفظ می کند. والدین بر مبنای مقدار برازندگیشان برای جفت گیری انتخاب می شوند و با استفاده از برنامه ای مشخص، فرزندان را ایجاد می کنند. در نتیجه، جواب هایی که برازندگی بالایی دارند فرصت های بیشتری برای بازپروری و صاحب فرزند شدن خواهند داشت . به این ترتیب، فرزندان می توانند ویژگی هایی از هر کدام از والدین را به ارث ببرند. با توجه به این که اندازه جمعیت همواره ثابت نگه داشته می شود، هم زمان با جفت گیری والدین و ایجاد فرزندان، باید برای آن ها جای خالی ایجاد کرد.
برای این منظور، اعضای جمعیت می میرند و جواب های جدید جایگزین آن ها می شوند. به تدریج و پس از این که همه موقعیت های جفت گیری در جمعیت اولیه مورد استفاده قرار گرفت نسل جدید جایگزین نسل قبلی می شود. با این روش می توان امیدوار بود که در طی نسل های متوالی، جواب های بهتر پیشرفت کنند در حالی که جواب هایی که عملکرد ضعیف تری دارند به تدریج حذف شوند.
به طور متوسط، نسل های جدید جواب ها دارای ژن های خوب بیشتری نسبت به یک جواب از نسل قبلی هستند. هر نسل متوالی دارای جواب های جزئی بهتری نسبت به نسل های قبل خواهد بود. در نهایت، زمانی که جمعیت همگرا می شود و فرزندانی ایجاد می کند که تفاوت چندانی با اعضای نسل های قبلی ندارند، گفته می شود که خود الگوریتم به مجموعه ای از جواب ها برای مسئله موردنظر همگرا شده است.
نحوه اجرا الگوریتم ژنتیک
بر مبنای انتخاب طبیعی
پس از این که نسل اولیه به صورت تصادفی ایجاد شد، الگوریتم ژنتیک با استفاده از 3 عملگر، شروع به تکامل این نسل اولیه خواهد کرد:
انتخاب: که معادل همان قانون بقای اصلح است.
جابجایی: که نمایانگر جفت گیری میان اعضای جامعه است.
جهش: که اصلاحاتی را به صورت تصادفی وارد مسئله می کند.
- عملگر انتخاب
- ایده اصلی: اولویت دادن به اعضای بهتر که به آن ها اجازه می دهد تا ژن هایشان را به نسل بعدی منتقل کنند.
- خوب بودن هر عضو به مقدار برازندگی آن عضو بستگی دارد.
- برازندگی را می توان با کمک یک تابع هدف و یا با قضاوت ذهنی تعیین کرد.
- عملگر جابجایی
- اصلی ترین عامل مشخصه الگوریتم ژنتیک نسبت به سایر روش های بهینه سازی
- دو عضو از جمعیت با استفاده از عملگر انتخاب به عنوان والدین انتخاب می شوند
- یک موقعیت مکانی در بین رشته بیت ها به صورت تصادفی انتخاب می شود.
- مقادیر دو رشته تا محل مشخص شده با یکدیگر جابجا می شوند
- اگر S1=000000 و S2=111111 و محل جابجایی 2 باشد، در این صورت S1’=110000 و S2’=001111 خواهد بود
- دو فرزندی که از طریق این فرآیند حاصل می شوند وارد نسل بعدی جمعیت خواهند شد.
- با ترکیب دوباره بخش هایی از اعضای خوب جامعه، این فرآیند احتمالا منجر به ساخت فرزندانی بهتر از والدین خواهد شد.
- عملگر جهش
- با احتمالی بسیار کم، بعضی از بیت های بخشی از اعضای نسل جدید(فرزندان نسل قبل) تغییر داده می شود.
- هدف از این کار، حفظ گوناگونی و تنوع در میان اعضای یک جمعیت و جلوگیری از همگرایی زودرس و ناقص می باشد.
- عملگر جهش به تنهایی باعث ایجاد یک جستجوی تصادفی در فضای جستجو می شود.
- جهش و انتخاب( بدون عملگر جابجایی) باعث ایجاد الگوریتم تپه نوردی موازی و مقاوم در برابر نویز می شوند.
تاثیر عملگر های ژنتیکی
- تنها استفاده از عملگر انتخاب منجر به پر کردن جمعیت با نسخه هایی مشابه با بهترین عضو جمعیت خواهد شد.
- استفاده از عملگر های انتخاب و جابجایی منجر به همگرایی الگوریتم به جوابی خوب اما نه کاملا بهینه خواهد شد.
- عملگر جهش به تنهایی باعث ایجاد یک جستجوی تصادفی در فضای جستجو می شود.
- استفاده از انتخاب و جهش باعث ایجاد الگوریتم تپه نوردی موازی و مقاوم در برابر نویز خواهد شد.
الگوریتم
- ایجاد جمعیت اولیه (t) به صورت تصادفی
- تعیین برازندگی جمعیت اولیه (t)
- تکرار موارد زیر:
انتخاب والدین از جمعیت (t)
استفاده از عملگر جابجایی بر روی والدین و و ایجاد جمعیت (t+1)
استفاده از عملگر جهش بر روی جمعیت (t+1)
تعیین برازندگی جمعیت (t+1) - تاجایی که بهترین عضو هر جامعه به اندازه کافی مناسب باشد.
جمع بندی
در قسمت های قبلی گفته شد که با استفاده از عملگر های انتخاب، جابجایی و جهش، الگوریتم ژنتیک در طی نسل های متوالی به نقطه بهینه کلی( یا نزدیک به آن) همگرا خواهد شد. این که چرا چنین عملیات ساده ای می تواند منجر به ایجاد روش هایی سریع، کاربردی و دقیق شود عمدتا به دلیل این حقیقت است که الگوریتم های ژنتیک در جستجو برای پاسخ بهینه، جهت دهی و شانس را به شیوه ای موثر و پربازده با یکدیگر ترکیب می کنند. با توجه به این که هر نسل تنها دارای امتیاز های برازندگی برای هر عضو نیست بلکه به طور ضمنی دارای اطلاعات بسیار بیشتری می باشد، الگوریتم ژنتیک اطلاعات خوب مخفی شده در یک جواب را با اطلاعات خوب یک جواب دیگر ترکیب می کند تا جواب های جدیدی را ایجاد کند که اطلاعات خوب را از والدین خود به ارث برده است که این امر به طور اجتناب ناپذیر و البته امیدوارانه ای منجر به بهینگی خواهد شد.
توانایی الگوریتم در جستجو و بهره برداری به طور همزمان، دلایل و مبانی نظری در حال رشد و کاربرد موفقیت آمیز در مسائل دنیای واقعی این نتیجه گیری که الگوریتم های ژنتیک روشی بسیار قوی و منسجم برای بهینه سازی هستند را تقویت می کند.
