ویژگی‌های الگوریتم ژنتیک
الگوریتم ژنتیک دارای خصوصیات و امتیازاتی می‌باشد که باعث شد از آن برای بدست آوردن جایگذاری مسیریابها ستفاده کنیم. همچنین معایب آن به شکلی است که مشکل چندانی برای استفاده از الگوریتم در این مسئله ایجاد نمی‌کند.
خصوصیات الگوریتم ژنتیک عبارت است از:
الگوریتم ژنتیک با کدگذاری مجموعه پارامترهای مساله سروکار دارد، نه با خود آنها، در نتیجه مستقل از مسئله می‌باشد. به عبارت دیگر فقط کافی است مسئله جایگذاری مسیریابها برای شبکه مش را به صورتی کدگذاری کنیم که قابل استفاده در مسئله باشد و الگوریتم ژنتیک احتیاج به هیچگونه اطلاعاتی در مورد مسیریابها ندارد.
الگوریتم ژنتیک به جای جستجوی یک نقطه، مجموعه‌ای از نقاط را جستجو می‌کند. این ویژگی یکی از مهمترین ویژگی‌های این الگوریتم و علت اصلی انتخاب آن می‌باشد. زیرا وقتی که جستجو از چندین نقطه از فضای نمونه‌ای آغاز می‌شود، امکان رسیدن به جواب نیز بسیار بالا می‌رود. این ویژگی در مسئله جایگذاری مسیریابها بسیار حائز اهمیت می‌باشد. زیرا به علت تعداد بسیار زیاد موقعیتهای ممکن و بهینههای محلی جستجو از یک نقطه منجر به گیر کردن در بهینههای محلی خواهد شد.
همچنین این الگوریتم دارای معایبی می‌باشد که عبارتند از:
غیر قطعی بودن، یعنی جوابهایی که الگوریتم به عنوان خروجی بر می‌گرداند می‌تواند یک جواب بهینه نباشد، یعنی استفاده از الگوریتم ژنتیک ممکن است ما را به همسایگی یک جواب بهینه می‌رساند نه خود جواب که در صورت استفاده از فضای نمونه ای کامل و مناسب، احتمال بروز این حالت خیلی کم خواهد شد.
یکسان نبودن خروجی الگوریتم به ازای یک ورودی خاص، این مساله نیز به ماهیت احتمالی و تصادفی بودن الگوریتم ژنتیکی برمی‌گردد، یعنی اجرای این الگوریتم چند بار روی یک سیستم، جوابهای متفاوتی خواهد بود. البته این نقص نیز با توجه به اینکه هدف فقط یافتن جایگذاری است که شرایط موردنظر را دارا باشد، چندان اهمیت ندارد و یکسان نبودن پاسخ‌ها چندان مهم نیست.
ساختار الگوریتم پیشنهادی
الگوریتم پیشنهادی را [۱۰۴]NRP مینامیم و در ادامه از این عنوان برای اشاره به روش پیشنهادی استفاده میکنیم. برای مقایسه بین کروموزومها، میبایست تابع ارزیابی برای امتیازدهی به کروموزومها وجود داشته باشد. الگوریتم دارای دو هدف[۱۰۵] است، که به صورت زیر تعریف میشوند:
| (۳‑۶) | |
| ( ۳‑۷) |
هدف اول یا معیار اتصال را بررسی می کند و درجه اتصال یک جایگذاری را نشان میدهد. اتصال بیان می کند که بین هر یک از مسیریابها و IGW، باید حداقل یک مسیر وجود داشته باشد. برای این منظور مسیریابها با یکدیگر متصل باشند تا بتوانند از طریق مسیرهای چندگامه با IGW ارتباط برقرار کنند. دو مسیریاب وقتی متصلند که باهم همپوشانی داشته باشند، به عبارت دیگر فاصله بین آنها از مجموع برد انتقالها آنها کمتر باشد، یعنی . جهت بررسی اتصال مسیریابها در یک جایگذاری از یک ماتریس استفاده میکنیم، که تعداد مسیریابهای شبکه است و یک سطر هم مربوط به تنها IGW است که در شبکه وجود دارد. درایههای سطر ماتریس نشان میدهد که مسیریاب با کدام مسیریابها همپوشانی دارد و به آنها متصل است. اگر همپوشانی وجود داشته باشد آن درایه و در غیر این صورت ۰ خواهد بود. برای هر جایگذاری، ماتریس اتصال محاسبه می شود. پس از محاسبه، درجه اتصال الگوی جایگذاری محاسبه می شود. به این صورت که، بررسی می شود که آیا، مسیری بین مسیریاب و IGW وجود دارد یا خیر. اگر برای همه گرهها مسیری با IGW وجود داشته باشد، اتصال کامل برقرار است. درجه اتصال جایگذاری با رابطه ۶-۳ محاسبه می شود.
هدف دوم ، میزان پوشش شبکه که توسط جایگذاری بدست می آید را نشان میدهد. برای محاسبه میزان پوشش هر جایگذاری، نسبت فضای پوشش داده شده توسط الگو به کل فضای شبکه را محاسبه میکنیم.
از آنجایی که دو تابع هدف وجود دارد، نیاز به اولویت بندی میان آنها، برای تعیین سودمندی منفردهاست. درجه اتصال نسبت به پوشش در تعیین مقدار یک منفرد مهمتر و دارای اولویت بشتر در نظر گرفته شده است. فرض کنیم درجه اتصال را با و درصد پوشش را با نشان دهیم، بنابراین اگر و دو راهحل با مقادیر تابع ارزیابی و برای و و برای باشند، برتر از درنظر گرفته می شود اگر و فقط اگر شرایط زیر برقرار باشد:
: (۱)
: (۲)
همچنین هر کروموزم تشکیل شده از m ژن می‌باشد که هر ژن () مقداری بین می‌پذیرد که حداکثر مختصات شبکه در یک بعد را نشان میدهد. . هر از یک ژنها یا ها نشان دهنده محل قرار گرفتن یک مسیریاب است. شکل ۴-۱۶ ساختار یک کروموزوم را نشان میدهد. تعداد ژنهای یک کروموزوم متناسب با اندازه شبکه و شعاع انتقال مسیریابها، متغیر است و بر اساس رابطه ۴-۱ ارائه شده در بخش ۴-۴ بدست می آید.
شکل ۳‑۱۰ ساختار کروموزوم
قسمت اصلی الگوریتم NRP در شکل ۳-۱۲ و قسمت‌های دیگر الگوریتم به ترتیب در شکل‌های ۳-۱۳و ۳-۱۴ و ۳-۱۵ و ۳-۱۶ نشان داده شده اند.
الگوریتم NRP ابتدا با بهره گرفتن از رابطه ۴-۱ اندازه ژنها را محاسبه کرده و سپس با بهره گرفتن از ژنتیک الگوریتم و توابعی که شرح هر یک در ادامه آورده شده است، مکان هر یک از مسیریابها را با هدف ماکزیمم کردن پوشش و برقراری اتصال، تعیین می کند. در ادامه، فاز ترافیک برای تخمین بار هریک از مسیریابها و تعیین نواحی سرریزشده یا نواحی حیاتی[۱۰۶]، که شرح آن در بخش ۳-۷ آورده شده است، اعمال می شود. پس از محاسبه و تعیین این نواحی، اقدام لازم (تعویض مسیریابها یا اضافه کردن مسیریاب) صورت گرفته و تعداد نهایی مسیریابها با رابطه ۴-۲ محاسبه می شود.
تابع تولید جمعیت اولیه: ۸۰% جمعیت اولیه به صورت تصادفی تولید می شود. ۲۰% باقیمانده، از موقعیتهای که از الگوریتم CPP بدست آمده، تولید میشوند، به این ترتیب احتمال قرار گرفتن در بهینههای محلی کم می شود.
تابع تقاطع: با اعمال عملگر تقاطع روی یک جفت والد، دو فرزند تولید می شود. برای عملگر تقاطع یک نقطه تقاطع[۱۰۷]، به صورت تصادفی تولید شده و از این نقطه، عمل تقاطع انجام می شود. عمل تقاطع مطابق شکل زیر صورت میگیرد:
نقطه تقاطع
