الگوریتم ممتیک

توضیحات

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

 

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

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

سپس زیر مجموعهاي از نسل فعلی (مجموعه جوابهاي فعلی، والدین و جوابهاي جدید، فرزندان) بر اساس مفهوم تنازع براي بقا به نسل بعد منتقل میشوند. فرآیند تولید نسلهاي جدید تا زمان برقرار شدن شرایط توقف ادامه مییابد.

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

 

 

میان تکامل ژنتیکی و فرهنگی تفاوت هاي عمده اي وجود دارد. اول این که تکامل فرهنگی خیلی سریع تر از تکامل ژنتیکی اتفاق می افتد و یک فرآیند قوي با منابع کم می باشد. دوم این که در تکامل فرهنگی، به ندرت تغییر، محصول کپی خطاها یا تبادل تصادفی واحدهاي هم ساز اطلاعاتی است. در حوزه علم، ترکیب خام ایده ها به بهبود نظریه ها منجر نمی شود. یک دانشمند معمولاً یک ایده را بعد از ترکیب با ایده هاي خود و اعتبارسنجی خود می پذیرد. فرآیند ترکیب ایده ها، به نوآوري منجر می گردد. علت این امر گردآوري دانش و مم هاي جدید از سایر حوزه هاي دیگر است. تکامل زیستی با مؤلفه نوآوري همراه نیست و اجازه ظهور تجربه در کروموزوم هاي والد را نمی دهد. می توان گفت که تکامل طبیعی یک فرایند بی پایان است در حالی که تکامل فرهنگی یک فرآیند مبتنی بر هدف می باشد که در آن واحدهاي انتقال اطلاعات به صورت هوشمند عمل می کنند.

 

الگوریتم هایی که شباهت آنها به تکامل فرهنگی نسبت به تکامل زیستی بیشتر می باشد را الگوریتم هاي ممتیک می نامند. علت این نام گذاري به راهبرد جستجوي نهفته در این الگوریتم ها که به طور عمده با الگوریتم هاي تکاملی متفاوت است، بر می گردد. براي کارآمدتر شدن جستجو در الگوریتم هاي تکاملی چندین هدف مهم طراحی شده است که توسط الگوریتم ممتیک برآورده شده اند:
– الگوریتم هاي بهینه سازي باید کارآمد باشند. به عنوان مثال آنها باید قادر به پیداکردن یک راه حل قابل قبول در یک زمان کوتاه باشند.
– الگوریتم هاي بهینه سازي بر اساس تعریف، مبتنی بر هدف هستند. نمایش اعضاي جمعیت به عنوان راه حل هاي کاندید، مشارکت و رقابت آنها براي رسیدن به هدف در حین فرآیند جستجو، مبین این تعریف می باشد.
– با توجه به واقعیت درجه توازي بالا، الگوریتم ژنتیک یک رویه جستجوي کورکورانه را با استفاده از منابع عظیم که تنها شامل یک جمعیت کوچک در یک زمان کوتاه می باشد، ارائه می کند. بنابراین همگراشدن سریع و عدم بهره گیري از خاصیت توزیع اطلاعات از معایب آن می باشد. در نتیجه نیاز به مؤلفه هاي دیگري براي تغییر
راه حل ها احساس می شود. این مسأله می تواند با اعمال درجه اي از جستجوي همسایگی مرتفع گردد.

 

 

 

این کد را میتوانید برای همه نوع مسئله بهینه سازی استفاده کنید و محدودیتی در نوع مسئله وجود ندارد.