دانلود پاورپوینت ارائه ی یک الگوریتم جستجوی مبتنی بر روشهای مبنی برجمعیت در بهینه سازی ترکیبی
ارائه ی یک الگوریتم جستجوی مبتنی بر روشهای مبنی برجمعیت در بهینه سازی ترکیبی
مقدمه
در ریاضیات و علوم رایانه یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. یک مسأله بهینه سازی با متغیرهای گسسته به عنوان یک مسأله بهینه سازی ترکیبی یا ترکیبیاتی شناخته می شوند. در یک مسأله بهینه سازی ترکیبی، ما به دنبال مجموعه ای از اشیاء از قبیل عدد صحیح، جایگشت و یا گرافی می گردیم که تعداد اعضایش محدود (و یا به طور قابل شمارش نامحدود) باشند.
مسأله بهینه سازی ترکیبی
کلمات کلیدی:
مدلهای ACO
الگوریتم مورچه
الگوریتم جستجو
درخت پوشای كمینه
روشهای مبنی برجمعیت
بهینهسازی تركیبی (Combinational Optimization)
مساله مسیریابی وسایل نقلیه(Vehicle Routing Problem)
فهرست مطالب
تعریف مسایل بهینه سازی ترکیبی
مدلهای ACO
کاربردهای الگوریتم مورچه
مساله مسیریابی وسایل نقلیه
طبقه بندی الگوریتم های حل مسایل بهینه سازی تركیبی
طبقه بندی فرااكتشافات
الگوریتمهای تكاملی
مسایل مهم در حوزه هوش گروهی
الگوریتم های مورچه
(اثر autocatalytic).
رکود: اكثر مورچه ها كوتاهترین شاخه را انتخاب می كنند
تبخیر: مکانیزم اجتناب از همگرایی سریع به مسیرهای زیربهینه
پارامترهای ارزیابی
مدلهای ACO
مساله مسیریابی وسایل نقلیه(Vehicle Routing Problem)
تعریف فرمال مساله CVRP
یک نمونه مساله ساده از CVRP
ساخت درخت پوشای می نیمم
استفاده از روش پریم برای ساخت درخت تعریف شده روی گراف مساله
روش پریم
ساخت راه حلها توسط مورچه ها
ساختار طراحی شده برای هر مورچه
انتخاب بهترین شاخه مجاور
بررسی شاخه های سمت چپ و راست
مطابقت درخواست گره با ظرفیت وسیله
انتخاب بیشترین صرفه جویی
انتقال به شاخه جدید
انتخاب شبه تصادفی گره بعدی بجز انبار (از شاخه جاری)
انتخاب احتمالی براساس تابع احتمال تجمعی
جستجوی محلی برای بهبود مسیرها
جایگزینی گره ها در یک تور
جابه جایی گره در یک تور
به روزرسانی وزن یالهای شرکت کننده در درخت
بررسی محدودیت مرزی برای وزنها
دریافت ورودیهای مساله
انجام محاسبات اولیه و مقداردهی به پارامترها
شروع حلقه اصلی الگوریتم
ساخت درخت پوشای کمینه
تولید جوابهای مساله توسط مورچه ها
انحراف معیار استاندارد
ساخت درخت پوشای كمینه برای انجام خوشه بندی مناسب روی گره های گراف مساله
تعریف وزن برای یالهای گراف جهت ساخت درخت پوشای كمینه
نحوه به روزرسانی وزن یالها
تعریف پارامترهای مناسب در بخشهای تغییریافته
مکانیزم شروع مجدد
جلوگیری از رکود و گرفتار شدن در کمینه محلی
مختصات انبار
مختصات گره ها
نتایج ارزیابی مجموعه داده های اول و سوم
به روزرسانی وزن یالهای درخت
تصمیمات احتمالی مورچه ها
ترکیب با سایر روشهای حل مساله مثل الگوریتم ژنتیک
بهینه سازی ترکیبی
منابع