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

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

Keywords:

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