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

مسائل ممانعت در شبکه، دسته ای از مسائل هستند که دو بازیگر با اهداف متضاد به تقابل با یکدیگر می پردازند و به صورت کلی منفعت یک بازیگر موجب متضرر شدن بازیگر دیگر می شود. در مسئله ممانعت از بیشینه ظرفیت، یک مدافع در نقش رهبر اقدامات ممانعتی خود را با توجه به بودجه موجود بر روی یال های یک شبکه اعمال می کند. در سطح بعدی، تعدادی مهاجم به عنوان پیرو و با مشاهده اقدامات ممانعتی مدافع، مسئله بیشینه سازی ظرفیت مسیر را از مبدا به مقصد بهینه سازی می نمایند. ممانعت در واقع حمله به کمان های شبکه و تخریب آن ها، با هدف کاهش ظرفیت عبوری کمان می باشد. در این پژوهش در ابتدا یک مدل برنامه ریزی ریاضی دو سطحی صفر و یک برای مسئله مورد نظر بیان شده است. سپس با توجه به پیچیدگی حل مسائل دو سطحی، یک الگوریتم ترکیبی شامل الگوریتم دایکسترا اصلاح شده و الگوریتم شبیه سازی تبرید برای حل مسئله پیشنهاد شده است. الگوریتم دایکسترا اصلاح شده همواره جواب بهینه مسئله بیشینه ظرفیت را ارائه می دهد که سبب تولید جواب های مطلوب در الگوریتم ترکیبی می گردد. سپس کارایی الگوریتم پیشنهادی تا ابعاد ۱۰۰ گره و ۱۵۰ کمان مورد بررسی قرار گرفت که نشان دهنده توانایی الگوریتم برای حل مسائل در ابعاد مختلف می باشد. بر اساس نتایج حاصل شده، افزایش بودجه مدافع تا میزان مشخصی بر بهبود تابع هدف مسئله تاثیرگذار می باشد. همچنین مقدار ضریب اهمیت مهاجمان در مسئله، ارتباط معکوس با کیفیت مسیر مهاجمان دارد و موجب افزایش یا کاهش بیشینه ظرفیت مسیر مهاجمان می گردد.

Keywords:

بازی مجموع صفر , مسئله ممانعت در شبکه , مسئله بیشینه سازی ظرفیت , الگوریتم دایکسترا اصلاح شده , الگوریتم شبیه سازی تبرید