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

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

مسیریابی در شبکه های بزرگ به دلیل پتانسیل های بالقوه ای که در مسیر بسته ها تا رسیدن به مقصد وجود دارد، پیچیده است. بنابراین الگوریتم های مسیریابی سازماندهی و انتشار اطلاعات درباره ی شبکه را انجام می دهند. از الگوریتم ژنتیک برای مسیریابی در شبکه ها، برای ارسال بسته ها در شبکه استفاده شده است. ما به دنبال راه حلی بودیم که بتوانیم مسیریابی درشبکه ها بزرگ را بدون داشتن اطلاعات قبلی را انجام دهیم. در این

مقاله از الگوریتم ژنتیک برای حل پیداکردن کوتاهترین مسیر در شبکه از طریق بهبود سازی احتمال کراس اور و جهش استفاده نمودیم. درکراساور از انتخاب چرخ رولت جهت تصادفی سازی متناسب و از کراس اور چند نقطه ای)کراس اور منظم( برای بهبودی یافت بهترین مسیر بهره جستیم.

راهکار پیشنهادی

شبکه مورد نظر به صورت G(V,E) که یک گراف متصل با N گره است نشان داده می شود. متریک بهینه سازی هزینه ی بین گره ها می باشد. هدف یافت کمترین هزینه ی کل بین گره ی مبدأ )که با Vsrc نشان داده می شود( و گره مقصد ) که با Vdes نشان داده می شود( می باشد. در این مقاله بااستفاده از الگوریتم ژنتیک مسیریابی موثری تولید می شود.

مقدار دهی اولیه جدول مسیریابی 

یک ماژول برای تولید تمام مسیرهای ممکن از یک گره ی داده شده، به تمام گره های دیگر درشبکه استفاده می شود)مانند جدول شماره 1 که هزینه لینک های ارتباطی شبکه شکل شماره 1 را نشان می دهد(. در ابتدا “n” مسیر تصادفی در نظر گرفته می شود.کروموزم.این n اندازه جمعیت را تعیین می کند. در این مرحله کروموزم ها به عنوان جمعیت نسل اول عمل می کنند.

تولید مسیرهای بهینه

الگوریتم ژنتیک از این ماژول، برای یافت مسیر بهینه استفاده می کند. ورودی این ماژول مجموعه ای از مسیرهای تولید شده می باشد. هر مسیر یک کروموزم نامیده می شود.

الف(شایستگی هر کروموزم محاسبه می شود. شایستگی به صورت زیر ارزیابی می شود:

  = Fitness تعداد هاپ هایی که در مسیر قراردارد * 10 –هزینه ی کل (جمع هزینه های لینک های جداگانه(

ب) دو کروموزم بهترین به عنوان والد انتخاب می شوند ( انتخاب از طریق متد چرخ رولت انجام می شود(.

پ) کراس اور با احتمال 8 / انجام می شود.

ج)جهش با احتمال 03/ انجام می شود.

د)فرزند در جمعیت قرارداده می شود و کروموزم هایی که شایستگی بسیار ضعیفی دارند از بین می روند.

در غیراینصورت اگر به معیار همگرایی رسیده است مسیر را به مدت T ثانیه ذخیره کرده و داده را به سمت مقصد در طول مسیر ارسال می کنیم.

ن)اگر شرط خاتمه برقرار نشده است مراحل را ن تا  الف تکرار می کنیم.

و) دوباره سازی مسیر بعد از مدت زمان T ثانیه، برای شبکه هایی که پویا هستند

انتخاب

مرحله ی انتخاب یکی از ویژگی های الگوریتم ژنتیک جهت گزینش پدر و مادر برای تولید نسل بعدی است. در این مقاله انتخاب براساس چرخ انتخاب رولت انجام می شود.در انتخاب چرخ رولت، فرد براساس شایستگی از بین رقبای خود انتخاب می شود. انتخاب چرخ رولت شبیه به تقسیم یک چرخ به تعدادی برش است. مناسب ترین کروموزم تکه های بزرگتری را دریافت می کند. از دیگر روش های انتخاب، انتخاب رتبه، انتخاب نخبه گرا، انتخاب تورنمنت و ... است.

کراس اور

عملگر کراس اور از ترکیب دو کروموزم والد، برای تولید فرزندان است. عمل کراس اور به طور عمده می تواند به صورت تک نقطه و چند نقطه باشد.در روش تک نقطه عملیات کراس اور تنها از یک نقطه انجام می شود ولی در چند نقطه، چند مکان جهت عملیات کراس اور در کروموزوم انتخابمی شود. کراس اور تک نقطه ای یک متد ساده است اما برای مسیریابی نمی تواند استفاده شود، زیرا کراس اور تک نقطه ای باعث ایجاد مسیر چرخه می شود.از این رو لازم است برخی تکنیک های پیشرفته چند نقطه کراس اور برای جلوگیری از چرخه استفاده کرد. از جمله این روشها می توان به کراس اور نیمه همسان  PMX 1 کراس اور منظم اشاره نمود OX 2 در این مقاله از روش کراس اور منظم استفاده نموده ایم. کراس اور منظم: با توجه به شکل 2 به شرح اجمالی این روش می پردازیم. ابتدا دو نقطه تصادفی در کروموزم ها انتخاب می شود. سپس ژنهای بین دو نقطه ی انتخابی را در کروموزم های فرزندان، در همان موقعیت کپی می کنیم. از راست ترین نقطه ی تقاطع شروع می کنیم ومقادیر ژنها را از چپ به راست می نویسیم. مثلا رشته ی >9>1>4>2>8>5>7>36 از کرومزوم P1 تولید می شود. برای تولید کروموزم فرزند (O2) اعداد بین دو نقطه ی تصادفی از کروموزم والد P2 را از رشته ی به دست آمده خارج می کنیم. اعداد به رنگ سیاه را از رشته بیرون می کشیم>9>1>4>2>8>5>7>3 6در کروموزم فرزند، ژن های باقی مانده که هنوزمشخص نشده اند را به صورت زیر پر می کنیم خانه های زرد رنگ. اعداد باقی مانده از رشته ی به دست آمده) اعداد به رنگ قرمز را از سمت چپ رشته برداشته و از راست ترین نقطه ی تصادفی از چپ به راست شروع به پر کردن ژن های کروموزم فرزند می کنیم.

جهش

در اثر استفاده از عملیات کراس اور در الگوریتم ژنتیک، نقاط دام ماکسیسمم محلی و یا مینیمم محلی ایجاد می شود. برای فرار از این نقاط می توان ازعملیات جهش استفاده کرد. در این روش از عملیات درج در موقعیت تصادفی در رشته استفاده می شود. لازم به ذکر است که عملیات جهش می تواندمنجر به بازگشت به عقب شود. فرزندان ایجاد شده از جهش می توانند در همان فرایند کراس اورمورد استفاده قرار گیرند.

شرایط خاتمه الگوریتم

این مرحله میزان همگرایی الگوریتم را تعیین می کند. حداکثر تولید نسل بعدی می تواند وابسته به مقدار تابع شایستگی باشد. همچنین معیار دوم توقف می تواند به میزان تناسب کروموزم ها بستگی داشته باشد.در یک شبکه ممکن است در توپولوژی شبکه، تغییر ایجاد شود و همچنین بعضی از گره ها می توانند به شبکه بپیوندند و یا شبکه را ترک کنند و گره هایی وجود دارند که ممکن است شکست بخورند. تحت این شرایط مسیر بهینه نمی تواند کوتاه ترین مسیر ممکن باشد. لذا باید در شبکه ها در هر T ثانیه مسیرهای جدید تولید شود. هزینه ی لینک هایی که 999 گذاشته شده به معنای این است که بین دو گره هیچ ارتباطی وجود ندارد. 999 در مقایسه با هزینه های دیگر مقداری بزرگ است. شبکه مورد نظر برای کار جاری شامل 6 گره می باشد. ابتدا به طور تصادفی 11 کرموزم ساخته می شودجدول شماره 2. ده کروموزم با شایستگی بالاتر برای نسل اول انتخاب می شوندجدول شماره 3.. در هر نسل کروموزم های معتبرتر و با شایستگی بالاتر به نسل بعدی ارسال می شوند تا به افزایش شایستگی نسل بعدی بیانجامد. ما اندازه جمعیت در نسل اول را 10 در نظر گرفتیم و با استفاده از انتخاب چرخ رولت عملیات GA را روی نسل انجام دادیم.جدول شماره 4 نسل دوم بعد از کراس اور و جهش.. می خواهیم از نود شماره 1 به نود مقصد شماره 6 برویم. در نهایت زیر مجموعه  ای از مسیرها از گره 1 به گره ی 6 تولید می شود.جدول شماره 5

نتیجه گیری

در کار انجام شده پیش رو از الگوریتم ژنتیک برای مسیریابی در شبکه ها برای ارسال بسته ها در شبکه استفاده شده است. ما به دنبال راه حلی بودیم که بتوانیم مسیریابی درشبکه ها بزرگ را بدون داشتن اطلاعات قبلی را انجام دهیم. اگر اندازه و توپولوژی شبکه مدام در حال تغییر باشد این الگوریتم می تواند یک راه حل بهینه باشد. در تحقیقات انجام شده با استفاده از تغییر احتمال کراس اور و جهش و به کار گیری روش OX جهت کراس اورالگوریتم را تحد مطلوبی بهینه سازیم.

منابع

پیداکردن کوتاهترین مسیر در شبکه با استفاده از الگوریتم ژنتیک سمیرا کاتب نواز رازلیقی، علی اکبر تجری سیاه مرزکوه دانشجوی کارشناسی ارشد کامپیوتر، موسسه آموزش عالی میرداماد گرگان -دانشجوی دکتری کامپیوتر، دانشگاه تبریز