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

این مقاله در سال 1386 که توسط امین جولا، نرجس خاتون ناصری و آقای دکتر امیرمسعود رحمانی تدوین شده است که در سیزدهمین کنفرانس ملی انجمن کامپیوتر ایران پذیرفته شده است.

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

مدل محاسباتی مخچه(CMAC):

این مدل در سال 1972 توسط J.S.Albus ارائه شد. CMAC یک ساختار شبکه عصبی است که قسمتی از مغز انسان بنام مخچه را شبیه سازی می کند. این مدل مبتنی بر سلول های حافظه انجمنی و جدول جستجو می باشد. این مدل دارای بلوک دیاگرامی است که براساس ورودی های مشخص خروجی های مناسب تولید می کند. متغیرهای ورودی به نواحی گسسته تقسیم می شوند که هر ناحیه گسسته آدرس سلولی از حافظه را مشخص می کند. با بازیابی اطلاعات ذخیره شده در سلول های حافظه انجمنی انتخاب شده، می توان خروجی را بدست آورد. CMAC  با تغییر محتویات سلول های حافظه متناظر با ورودی ها، خروجی صحیح را فرا می گیرد.

برای هر ورودی، ضریبی از مقدار تفاوت خروجی بدست آمده از CMAC و مقدار خروجی مورد انتظار محاسبه می شود و تحت عنوان ضریب یادگیری به محتویات سلول های حافظه انتخاب شده اضافه می شود.

همان طور که در شکل 1 نشان داده شده است مدل مخچه از ورودی هایی مانند s₁,s₂ تشکیل شده است که یک سری نواحی گسسته بنام بلوک تقسیم می شود که برای s₁  و s₂ به ترتیب بلوک های A,B,c و a,b,c در نظر گرفته شده است. هر کدام از بلوک ها می توانند در لایه های پایینی خود با شیفت دادن بلوک ها مجموعه ای از بلوک های جدید ایجاد کنند. مدل CMAC برای هر ورودی با استفاده از جدول جستجو و سلول های حافظه انجمنی ( فوق مکعب ) از مجموع وزن های موجود در فوق مکعب ها خروجی را بدست می آورد. مساحتی که توسط نواحی بلوک های دو متغیر بدست می آید فوق مکعب نامیده می شود. به عنوان مثال فوق مکعب Bb,Fe. برای ورودی (s₁,s₂)=(4,3)  خروجی برابر مجموع وزن های موجود در فوق مکعب های Bb,Fe,Hh بدست می آید.

شکل 1: نمایش مدل CMAC

عملگر تقاطع:

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

عملگر جهش:

محاسبه نرخ جهش به کمک CMAC از طریق فرمول زیر انجام می شود که CMAC به این روش مقداردهی اولیه می شود.

که در آن f_avg برابر است با میانگین شایستگی کروموزوم های نسل، f شایستگی کروموزوم مورد نظر برای اعمال عملگر جهش، f_max بزرگترین شایستگی موجود در نسل می باشد.

هر کدام از این سه پارامتر در مدل CMAC به عنوان یک ورودی محسوب می شود که در این مقاله برای هر پارامتر 6 بلوک دو لایه ای در نظر گرفته شده است. بنابراین در هر فوق مکعب دو وزن جافظه سلولی با یکدیگر جمع می شوند.

نحوه بدست آوردن نرخ جهش و آموزش پویای CMAC:

از فرمول بالا تا سی نسل استفاده شده و از تغییر آنها در اجرای الگوریتم اجتناب می شود. پس از آن آموزش CMAC به صورت پویا شروع می شود. که در آن هر ده تولید نسل را یک "مرحله" نامیده می شود. پس از پایان هر مرحله، نسبت تعداد تولید نسل بر میانگین شایستگی کروموزوم های نسل بدست آمده و بر محاسبه این تقسیم برای مرحله قبل تقسیم می شود. این نشان دهنده "ضریب موفقیت" می باشد.(همان طور که در فرمول زیر نشان داده شده است)  

اگر ضریب بدست آمده در هر مرحله بزرگتر از مرحله قبل باشد نشان دهنده این است که روند اجرا مناسب است و کروموزوم های فعلی به سمت تولید جواب بهینه می روند. پس باید احتمال دگرگونی عملگر جهش کاهش یابد تا همین روال حفظ شود. اما اگر ضریب موفقیت مرحله فعلی کوچکتر یا مساوی مرحله قبل باشد نشان دهنده این است که به احتمال زیاد این کروموزوم ها منجر به تولید نسل های بهتر نخواهد شد. بدین منظور عملگر جهش باید افزایش یابد تا تغییر در کروموزوم های بیشتر باعث شود تا جواب های بهتری بدست آید.

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

نتایج مورد بررسی در این مقاله حاکی از عملکرد و سرعت بهتر این الگوریتم پیشنهادی برای حل مسئله برنامه ریزی دروس دانشگاهی می باشد.

منابع:

[1].  امین جولا، نرجس خاتون ناصری ، امیرمسعود رحمانی ،" استفاده ار مدل محاسباتی مخچه برای محاسبه نرخ جهش در الگوریتم ممتیک برای حل مسئله برنامه ریزی دروس دانشگاهی "، سیزدهمین کنفرانس ملی انجمن کامپیوتر ایران ،جزیره کیش،اسفندماه 86.