الگوریتم های ابتکاری
حل انواع مسایل بهینه سازی به معنای یافتن مقدار بهینه برای مینیمم کردن (ماکزیمم کردن) صورت مساله (تابع fitness) می باشد که شامل راه حل های عددی است. در مسایل پیچیده با تعداد متغییر های زیاد با روش های معمول حل ریاضی، یافتن مقادیر بهینه تقریبا غیر ممکن و زمان بر می باشد.
با توجه به فرایند های زیستی می توان در یافت که موجودات با عنایت بر هوش جمعی قادر به یافتن بهترین پاسخ برای حفظ بقای خود می باشند. یکی از مهمترین و اساسی ترین الگوریتم های ابتکاری مبتنی بر روش های تکاملی، الگوریتم ژنتیک می باشد که توامندی بالای در حل مسایل بهینه سازی از خود نشان داده است.
تمامی الگوریتم های ابتکاری مبتنی بر دو محور اصلی زیر می باشند:
- جستجوی سراسری
- جستجوی محلی
الگوریتم ژنتیک
الگوریتم ژنتیک نیز مانند سایر الگوریتم های ابتکاری برای داشتن یک دید کلی بر فضای جستجوی پاسخ و هم کاوش محلی دقیق، برای یافتن پاسخ نیازمند عملگر های تکاملی می باشد که در ادامه به تفضیل توضیح داده خواهد شد.
در یک نگاه کلی الگوریتم ژنتیک شامل مراحل زیر می باشد:
مقدار دهی اولیه و مقدار برازندگی
برای درک عملکرد الگوریتم باید با مفاهیم ژن و کروموزوم آشنا شویم. در هر مرحله کروموزوم تولید می شود. هر کروموزوم شامل تعدادی ژن که برابر ابعاد مساله بهینه سازی است، می باشد.
مرحله اول الگوریتم ژنتیک تولید جمعیتی که شامل تعداد مشخصی کروموزوم می باشد. برای تولید جمعیت اولیه باید شرایط و قیود مساله را نیز لحاظ نمود. پس از هر بار تولید جمعیت در ط مراحل الگوریتم برای بررسی عملکرد کروموزوم ها باید تابع برازندگی (fitness function) آن مشخص شود.
پس از مرحله آغازین تولید جمعیت نوبت به عملگر های الگوریتم ژنتیک می رسد که بر روی کروموزوم ها اعمال خواهد شد.
عملگر جهش (mutation)
همانطور که قبلا هم گفته شد برای جستجوی سراسری و داشتن دید کلی نسبت به فضای جستجو نیازمند عملگر جهش می باشیم. این عملگر تک عملوندی می باشد یعنی تنها بر روی هر کروموزوم مستقلاٌ اعمال می شود. اینکه چه تعداد کروموزوم در هر نسل دستخوش جهش شوند را نرخ جهش مشخص می کند.
به زبان ساده تر کافیست در هر کروموزم انتخابی مقدار یک (یا چند) ژن را به صورت تصادفی تغییر دهیم. با این کار اگر جستجو در مینیمم محلی گیر کرده باشد می تواند ازین وضعیت خارج شده و نواحی دیگری را هم جستجو کند.
عملگر بازترکیب (crossover)
در صورتی که الگوریتم در یک ناحیه دارای نتایج خوبی باشد باید آن ناحیه از فضای جستجو دقیق تر کاوش شود. این نیاز با وجود عملگر بازترکیب برآورده می شود. در این حالت نیازمند حداقل دو عملوند (کروموزوم) می باشیم. دو کروموزوم والد با اشتراک گذاشتن بخشی از ژن های (وِیژگی ها) خود، فرزندان با ویژگی های مشابه خواهند ساخت.
به عنوان مثال نشان داده شده در شکل فوق، کروموزوم والد در دو نقطه برش داده شده و ژن های جابجا شده اند. که در سمت راست فرزندان با ویژگی هاس مشابه تولید شده است. نرخ بازترکیب تعیین کننده تعداد کروموزوم های انتخابی خواهد بود.
در بازترکیب روش های مختلفی وجود دارد که می توان ازین بین با بازترکیب های زیر اشاره نمود.
- تک نقطه ای
- دو نقطه ای
- پراکنده و ..
عملگر انتخاب (selection)
پس از هر بار تولید جمعیت با توجه به اضافه شدن نسل های جدید یا تولید کروموزوم های جدید نوبت به انتخاب جمعیت ثانویه خواهد رسید. برای این مهم باید برای هر کروموزوم مقدار تابع برازندگی محاسبه شود. مسلما کروموزوم هایی در مرحله بعدی راه خواهند یافت که دارای مقدار برازندگی بیشتری باشند.
یکی از موارد مهم در بحث انتخاب توجه به مساله نخبه گرایی (Elitizme) می باشد. یعنی تعداد مشخصی از کروموزوم ها که تابع برhزندگی آنها بهتر از سایر موارد است را بدون بازترکیب و جهش به مرحله بعد بفرستیم تا اثر پاسخ خوب آنها در جمعیت بعدی باقی بماند.
لازم است در هر بار تکرار الگوریتم شرط های توقف بررسی شوند. شروط توقف می توانند موارد زیر باشند:
- تعداد تکرار
- محدودیت زمانی اجرای الگوریتم
- همگرایی الگوریتم و ....
واسط کاربری گرافیکی متلب
نرم افزار متلب برای راحتی و در دسترس بودن الگوریتم های بهینه سازی، واسط کاربر گرافیکی را برای این مهم اختصاص داده است. برای آشنایی با این بخش از نرم افزار به مثال زیر دقت کنید.
یکی از توابع بنچ مارک چالش بر انگیز در حل مساله بهینه سازی، rastriginsfcn می باشد. این تابع شامل تعداد زیادی مینیمم محلی می باشد. برای درک بهتر شمای این تابع با وجود دو متغییر نشان داده شده است.
برای حل این مساله بهینه سازی از ابزار بهینه سازی متلب کمک می گیریم.
برای حل هر مساله تعداد کروموزوم ها که مشخص کننده population یا همان جمعیت است، باید مشخص شود. در بخش Selection می توان نرخ نخبه گرایی را انتخاب نمود. نرخ جهش را در قسمت mutation و نرخ بازترکیب در crossover باید مشخص شود.
اثر نرخ جهش و بازترکیب
دلیل اهمیت تعیین مناسب نرخ جهش و بازترکیب در بالا بردن توانایی الگوریتم در جستجوی موثردر میان فضای پاسخ های محتمل می باشد. برای درک بهتر این مساله، برای دو حالت مساله حل شده است و نمودار های آن در زیر نمایش داده شده است.
در این حالت نرخ جهش یک و نرخ بازترکیب صفر می باشد. همانطور که می بینید دو نمودار میانگین و بهترین برازندگی به هم نمی رسند. در واقع حتی اگر جمعیت پاسخ مناسبی پیدا کرده باشد چون قادر به بازترکیب همان جمعیت نیست نمی تواند خود را به مقداربهینه نزدیک کند. لاجرم با وجود جهش به مکان های دیگر فضای جستجو پرت می شود.
برعکس حالت قبل در این نمودار نرخ جهش صفر و نرخ بازترکیب یک در نظر گرفته شده است. این بدین معناست که میانگین برازندگی جمعیت به شدت به مقدار بهترین برازندگی همگرا می شود. در واقع الگوریتم در مینیمم محلی گیر کرده است و به علت اینکه جهش اتفاق نمی افتد قادر به جستجوی فضای پاسخ نیست.
نکته مهم: در ابتدای جستجو باید مقدار نرخ جهش را بالا انتخاب کرده تا دید کلی به فضای جستجو داشته باشیم. به مرور زمان نرخ جهش کاسته شده و نرخ بازترکیب افزایش یابد. با این کار الگوریتم خود را به مقدار بهینه نزدیک ونزدیک تر می کند.
ویدیو آموزشی
برای یادگیری بهتر تنظیمات ابزار بهینه سازی ویدیو زیر را تماشا کنید.
نظر برای “الگوریتم ژنتیک”