یک الگوریتم ژنتیک موثر برای حل مشکل کوتاه ترین مسیر درخت خوشه ای

مشکل درخت کوتاه ترین مسیر خوشه ایClUSPTP توسعه ای از مسئله کوتاه ترین مسیر تک منبعی کلاسیک است که در آن، با توجه به نموداری با مجموعه ای از گره ها که به مجموعه ای از پیش تعریف شده، متقابل منحصر به فرد و جامع از خوشه ها تقسیم شده اند، ما به دنبال یک درخت پوشا با کوتاه ترین مسیر از یک منبع معین به تمام گره های دیگر گراف، با این و یژگی که هر خوشه باید یک زیردرخت متصل را القا کند ClUSPTP. متعلق به کلاس مسائل بهینه سازی ترکیبی تعمیم یافته است، و به طور کلی، ثابت شده است که یک مسئله زمان سخت چند جمله ای غیر قطعی hard-NP است. در این مقاله، ما یک الگوریتم ژنتیک جدید GA را پیشنهاد میکنیم که برای تناسب با چالش های مسئله بررسی شده طراحیشده است. ویژگی های اصلی GA ما عبارتند از: استفاده از یک طرح بازنمایی نوآورانه که به ما امکان می دهد عملگرهای ژنتیکی معنی دار و استفاده از یک جمعیت اولیه ترکیبی را تعریف کنیم. نتایج محاسباتی گسترده ای برای دو مجموعه از نمونه ها گزارش و مورد بحث قرار می گیرد: اقلیدسی و غیر اقلیدسی . عملکرد الگوریتم پیشنهادی بر روی شش نوع نمونه اقلیدسی معیار موجود در ادبیات و شش نوع نمونه غ یر اقلیدسی به دست آمده از نمونه های اقلیدسی مربوطه ارزیابی شد. نتا یج به دست آمده نشان دهنده بهبود با توجه به روش های موجود از ادبیات، هم از نظر کیفیت راه حل های به دست آمده و هم از نظر زمان ها ی محاسباتی لازم برای به دست آمدن آنها است. آنها نشان میدهند که الگوریتم ژنتیک ما تمام روش های موجود را از ادبیات انجام میدهد، و برای تمام نمونه های معیار موجود، راه حل های بهینه را در هر ۳۰ آزمایش مستقل ارائه میدهد

Keywords:

مشکل کوتاه ترین مسیر تک منبعی , مشکل درخت کوتاه ترین مسیر خوشه ای , الگوریتم ژنتیک