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

مسائل ممانعت در شبكه، دسته‌اي از مسائل هستند كه دو بازيگر با اهداف متضاد به تقابل با يكديگر مي‌پردازند و به صورت كلي منفعت يك بازيگر موجب متضرر شدن بازيگر ديگر مي‌شود. در مسئله ممانعت از بيشينه ظرفيت، يك مدافع در نقش رهبر اقدامات ممانعتي خود را با توجه به بودجه موجود بر روي يال‌هاي يك شبكه اعمال مي‌كند. در سطح بعدي، تعدادي مهاجم به عنوان پيرو و با مشاهده اقدامات ممانعتي مدافع، مسئله بيشينه‌سازي ظرفيت مسير را از مبدأ به مقصد بهينه‌سازي مي‌نمايند. ممانعت در واقع حمله به كمان‌هاي شبكه و تخريب آن‌ها، با هدف كاهش ظرفيت عبوري كمان مي‌باشد. در اين پژوهش در ابتدا يك مدل برنامه‌ريزي رياضي دو سطحي صفر و يك براي مسئله مورد نظر بيان شده است. سپس با توجه به پيچيدگي حل مسائل دو سطحي، يك الگوريتم تركيبي شامل الگوريتم دايكسترا اصلاح شده و الگوريتم شبيه‌سازي تبريد براي حل مسئله پيشنهاد شده است. الگوريتم دايكسترا اصلاح شده همواره جواب بهينه مسئله بيشينه ظرفيت را ارائه مي‌دهد كه سبب توليد جواب‌هاي مطلوب در الگوريتم تركيبي مي‌گردد. سپس كارايي الگوريتم‌ پيشنهادي تا ابعاد 100 گره و 150 كمان مورد بررسي قرار گرفت كه نشان دهنده توانايي الگوريتم براي حل مسائل در ابعاد مختلف مي‌باشد. بر اساس نتايج حاصل شده، افزايش بودجه مدافع تا ميزان مشخصي بر بهبود تابع هدف مسئله تأثيرگذار مي‌باشد. همچنين مقدار ضريب اهميت مهاجمان در مسئله، ارتباط معكوس با كيفيت مسير مهاجمان دارد و موجب افزايش يا كاهش بيشينه ظرفيت مسير مهاجمان مي‌گردد.