فرموله­سازی مسئله^[۹۲]
طرح تعیین جایگذاری گره­های MR بایستی تعداد گره­های MR مورد نیاز را مینیمم کند، ضمن اینکه پوشش را تا حد ممکن ماکزیمم کرده و اتصال کامل در شبکه برقرار نماید. بدلیل وجود محدودیت­های جغرافیایی، رسیدن به پوشش کامل شبکه عملی نیست، چرا که وجود این نواحی در ناحیه شبکه مانع از پوشش این ناحیه­ها گردیده، در نتیجه نمی­ توان به پوشش ۱۰۰% دست یافت. مسئله می ­تواند به صورت زیر فرموله شود:

رابطه ۳-۳ : مجموعه MR های انتخابی، باید پوشش ناحیه شبکه را تا حد امکان، ماکزیمم کند.
رابطه ۳-۴ : وجود اتصال کامل را مدل می­ کند. اتصال کامل ایجاب می­ کند که برای هر گره مش، مسیری به IGW وجود داشته باشد.

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

رابطه ۳-۵ : محدودیت جغرافیایی را در نظر می­گیرد؛ به این صورت که هیچ یک از MRها نباید در موقعیت­های مربوط به مجموعه قرار بگیرند.
محدودیت ترافیکی و نحوه اعمال آن، در بخش ارائه روش پیشنهادی توضیح داده شده است.
برای حل مسئله جایگذاری مسیریاب­ها، می­توان از الگوریتم CPP، استفاده کرد. در الگوریتم ژنتیک، نحوه استفاده از این الگوریتم آمده است که از خروجی الگوریتم، برای تولید قسمتی از جمعیت اولیه استفاده می­ شود.
مقدمات: اگر هر یک از دایره­ها را یک مسیریاب در نظر بگیریم که دارای برد انتقال باشند، می­توان برد انتقال را به عنوان شعاع دایره در نظر گرفت. مرکز دایره ، جایی که مسیریاب در آن واقع می­ شود. از آنجایی که مسیریاب­ها می­توانند برد انتقال متفاوتی باشند، مسئله به حل مسئله CCP^[93]، نسخه ای از CPP^[94] متناسب با مسئله جایگذاری مسیریاب­ها و محدودیت­های مربوطه، تبدیل می­ شود. برای حل مسئله CCP، از آنجایی که NP-Hard است، الگوریتمی بر پایه الگوریتم ژنتیک ارائه شده است. در ادامه الگوریتم ژنتیک، و بخش­های مختلف و بدنبال آن ساختار الگوریتم پیشنهادی آورده خواهد شد.
الگوریتم ژنتیک
الگوریتم‌های ژنتیک یا الگوریتم‌های تکاملی بر مبنای یک نظریه زیست‌شناسی که به نظریه داروین مشهور است، بنیان‌گذاری شده است. در الگوریتم‌های تکاملی مبنا بر این قرار داده شده است که معلومات مساله تبدیل به کروموزم‌هایی می‌شوند و سپس توسط تکنیک‌های خاص حل مسئله در الگوریتم تکاملی شروع به حل مسئله می‌شود. الگوریتم ژنتیک از بخش‌های مختلفی تشکیل شده است که عبارتند از[۳۴]:
کروموزوم^[۹۵]
جمعیت ژنتیکی^[۹۶]
تابع برازش^[۹۷]
عملیات ژنتیکی^[۹۸]
پارامتر‌های الگوریتم ژنتیک^[۹۹]
در ادامه به بررسی هر یک از موارد فوق می‌پردازیم.
کروموزوم
کروموزوم مجموعه‌ای از ژن‌ها می‌باشد که با ترتیب معینی به دنبال هم قرار گرفته‌اند و یک راه حل را در الگوریتم ژنتیکی نشان می‌دهد. ژن^[۱۰۰] کوچکترین جز اطلاعاتی است که در داخل کروموزوم قرار دارد. در شکل ۳-۲ یک کروموزوم نشان داده شده است.
شکل ‏۳‑۳ شمای یک کروموزوم با n ژن
جمعیت ژنتیکی
به مجموعه‌ای از کروموزوم‌ها در الگوریتم ژنتیک، جمعیت ژنتیکی گفته می‌شود. در واقع این جمعیت مجموعه‌ای از جواب‌ها را در اختیار الگوریتم ژنتیکی قرار می‌دهد. اندازه این جمعیت در طول اجرای الگوریتم ژنتیکی معمولا ثابت است ولی تعداد افراد این جمعیت نمی‌تواند از یک تعداد حداکثر بیشتر شود و در نتیجه بر اثر رقابت، کروموزم‌هایی که جواب بهتری برای مسئله ارائه می‌دهند در جمعیت باقی می‌مانند و بقیه از دور خارج می‌شوند.
تابع برازش
بقای کروموزوم‌ها در طول اجرای الگوریتم ژنتیکی بستگی به توانایی آن­ها برای حل مسئله دارد و کروموزم‌هایی که جواب بهتری ارائه می‌دهند شانس بیشتری برای ادامه حیات دارند و برعکس آن­هایی که جواب نامناسبی ارائه می‌دهند شانس کمتری دارند ، بنابراین باید الگویی برای تعیین مناسب یا نامناسب بودن جواب ارائه شده بوسیله یک کروموزوم وجود داشته باشد که برای این منظور از تابعی موسوم به تابع برازش استفاده می‌شود . این تابع یک عددی را به عنوان خروجی برای هر کروموزوم برمی‌گرداند که نشان دهنده میزان مطلوبیت جواب مسئله است.
عملیات ژنتیکی
عملیات ژنتیکی مجموعه اعمالی هستند که سبب می‌شوند از روی جمعیت فعلی جمعیت جدیدی تشکیل شود که به آن نسل می‌گویند. برای این منظور الگوریتم ژنتیک از عملگر‌هایی استفاده می‌کند تا بتواند نسل جدیدی از جواب‌ها که نسبت به نسل قبل بهبود یافته‌اند، ایجاد کند. این عملگر‌ها عبارتند از: انتخاب^[۱۰۱]، تقاطع^[۱۰۲]، جهش^[۱۰۳]، تولید مجدد و غیره که در بخش­های بعد به آن­ها اشاره خواهد شد.
پارامترهای الگوریتم ژنتیکی
الگوریتم ژنتیک یک روش تصادفی برای رسیدن به جواب یک مسئله است و برای این منظور همانطور که اشاره شد از عملگرهایی برای تولید نسل جدیدی از جواب‌ها استفاده می‌کند، بنابراین باید این عملگرها در مواقع خاصی با احتمال مشخصی وارد عمل شوند که این احتمالات را پارامترهای الگوریتم ژنتیکی می‌گویند. همچنین اندازه جمعیت و تعداد نسل‌ها نیز جزء پارامتر‌های الگوریتم ژنتیک هستند. این پارامترها عبارتند از[۳۳] :
احتمال تولید مجدد P_r
احتمال تقاطع P_c
احتمال جهش P_m
اندازه جمعیت
تعداد نسلها