حل مسئلهی مینیمم کردن پهنای باند گراف با بکارگیری الگوریتم فرهنگی ترکیبی

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

کلیدواژه ها:

مینیمم کردن پهنای باند گراف ، الگوریتم فرهنگی ترکیبی ، الگوریتم تپهنوردی