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

(3 customer reviews)

148,000 تومان

توضیحات

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

 

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

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

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

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

 

FLOW1

 

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

 

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

 

 

 

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

 

 

 

3 reviews for الگوریتم ممتیک

  1. پريا

    سلام من كد الگوريتم ممتيك رو از سايت شما خريد كردم ولي فايلي برام ارسال نشده لطفا پيگيري كنيد

    • ایران متلب

      با سلام و احترام

      کدهای ممتیک برای شما ایمیل شد

      شاد باشید

  2. احمد

    با سلام
    ایا این کد برای خوشه بندی بهینه، بدون نیاز به تغییر عمل میکند؟
    پ.ن: براساس دیتاست از قبل تهیه شده که 10000 سطر و 5 ستون دارد

    • ایران متلب

      سلام
      بله شما می توانید دیتاست ورودی را تغییر دهید و نیازی به تغییرات داخل کد نیست. مگر بخواهید پارامترهای الگوریتم ممتیک (مثل تعداد جمعیت ) را تغییر دهید.

  3. احمدرضاسعیدی

    سلام من الگوریتم ممتیک رو خریداری کردم ولی لینک اون برام ارسال نمایید . باتشکر

دیدگاه خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *