استفاده از الگوریتم ژنتیک برای حل مساله درختان پوشای کمینه با محدودیت ظرفیت

مساله درخت پوشای کمینه با محدودیت ظرفیت CMST کم هزینه ترین درخت پوشای یک گراف است بطوریکه گره r به عنوان گره ریشه این درخت نمایانده میشود و درآن محدودیت K ارضا میگردد اهمیت مساله NP-complete CMST بودن آن به اثبات رسیده و کاربردهای تئوری و عملی متعددی ازاین مساله متصور است دراین مقاله ازالگوریتم فرابتکاری ژنتیک به منظور حل مساله CMST بهره گرفته شده است بطوریکه درآن عملگر تقاطع به روشی جدید و متناسب با مساله مذکور مورد استفاده قرارمیگیرد بدین منظور ابتدا جمعیت اولیه ای ازراه حل های شدنی ساخته میشود و براساس تابع برازندگی دو راه حل به عنوان والد درهرزیرتکرار ازالگوریتم انتخاب میگردد سپس مجموعه ای متشکل ازگره های کاندیدا تشکیل میشود بطوریکه اعضای این مجموعه گره های بالقوه ای هستند که ازقابلیت جابجایی دربین زیردرختان هرراه حل برخوردارند بدین ترتیب تضمین میشود که جابجایی گره های بالقوه برخلاف مقدار تابع برازندگی شدنی بودن هریک ازراه حل ها را تحت تاثیر قرارنمی دهد فرایند اشاره شده تا مشاهده شرایط توقف الگوریتم ادامه می یابد و درنهایت راه حل با کمترین مقدار تابع برازندگی به عنوان خروجی الگوریتم گزارش میشود.

Keywords:

درخت پوشای کمینه , الگوریتم متاهیوریستیک , الگوریتم ژنتیک , درخت پوشای کمینه با محدودیت ظرفیت