آگوست 6

VOIPPCSMA[55]
CSMA
RoutingRural[56]
ChannelRural[57]
LongTDMA[58]
تأخیر و بازدهی
DRAND[59]
توزیعی
DistriMC2R[60]
در این فصل مدل، چالش‌ها و روش‌های زمان‌بندی متمرکز در شبکه‌های مش بی‌سیم مورد بحث قرار گرفت. همان‌طور که اشاره شد در طراحی یک روش زمان‌بندی، تعیین مدل و پارامترهای ورودی مسئله، مشخص کننده اهداف و روش حل مسئله خواهد بود. در این راستا چهار چالش اصلی: تداخل میان لینکهای بی‌سیم، سربار، تأخیر و استفاده مجدد از فضای فرکانسی مورد توجه قرار گرفت. جهت بررسی و دسته‌بندی الگوریتم‌های زمان‌بندی، براساس مطالعات انجام شده چهارچوبی تعریف شد. با توجه به شرایط و اهداف مسئله، اتخاذ تکنیک برای اختصاص منابع به لینک ها [a271]، چهارچوب دسته بندی برای الگوریتم‌های متعدد در شبکه های مش چندگامی بر اساس 1) شرایط 2) ورودی‌ها 3) اهداف و 4) روش، دسته‌بندی شد و مقالات متعددی در این زمینه بررسی گردید[a272]. در فصل بعد به بررسی و معرفی روش پیشنهادی پرداخته می‌شود.
الگوریتم پیشنهادی بر پایه‌ی الگوریتم ژنتیک
در این فصل الگوریتم پیشنهادی به منظور تخصیص پنجره‌های زمانی زیر فریم دیتا با رویکرد تضمین تأخیر انتها با انتها در کاربردهای بلادرنگ نظیر صوت و ویدئو کنفرانس در مدیریت متمرکز ارائه می‌شود. همچنین با در نظر گرفتن معیارهای ارزیابی و بررسی سناریوهای مختلف شبیه‌سازی ، کارایی این الگوریتم در مقایسه با الگوریتمهای موجود در این زمینه مورد ارزیابی قرار می‌ گیرد. همان طور که در فصول قبل اشاره شد مسئله زمان‌بندی یک مسئله NP-Hard است[14،18،12،38]. بر اساس مطالعات انجام شده، یکی از روش‌های مناسب برای حل مسایل NP-Hard که در متون مختلف برای کاربردهای علوم دیگر بدان اشاره شده است استفاده از الگوریتم ژنتیک به عنوان یک راحل کارا، سریع، ساده و پویا است[61-67]. در ادامه ابتدا الگوریتم ژنتیک به عنوان شالوده و ایده‌ی اصلی الگوریتم پیشنهادی بیان و سپس الگوریتم پیشنهادی بر اساس آن تبیین می‌شود. در آخر نحوه پیاده‌سازی، مراحل مختلف تست و ازیابی مورد بحث قرار گرفته است.
محدوده کاری الگوریتم ژنتیک بسیار وسیع می باشد و هر روز با پیشرفت روزافزون علوم و تکنولوژی استفاده از این روش در بهینه سازی و حل مسائل بسیار گسترش می‌یابد. الگوریتم ژنتیک یکی از زیر مجموعه های محاسبات تکامل یافته است و می‌توان آنرا یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید میکند. الگوریتم ژنتیک بر روی مجموعه‌ای از جوابهای مسئله به امید بدست آوردن جواب‌های بهتر، قانون بقای بهترین را اعمال می‌کند. درهر نسل به کمک فرآیند انتخابی متناسب با ارزش جوابها و تولید مثل کنترل‌شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شدهاند، تقریبهای بهتری از جواب نهایی بدست میآید. این فرایند باعث میشود که نسل‌های جدید با شرایط مسئله سازگارتر باشد. الگوریتم ژنتیک ابزار سودمندی در حل مسائل بهینه‌سازی مختلف است. [61-67]
فرضیه تکامل در موجودات زنده درتاریخ 24 نوامبر سال 1859 میلادی با انتشار کتاب “بنیاد انواع” توسط چارلز داروین انگلیسی به طور جدی مطرح شد. در سال 1865 میلادی تحقیقات گریگور مندل164 کشیش اتریشی درباره وراثت و تکامل و اصولی که به طور تجربی به دست آورده بود چند سال پس از مرگش انتشار یافت. این تحقیقات165 توجه بسیاری را معطوف به این موضوعات نمود. در سال 1903 کروموزوم به عنوان واحد وراثت و درسال 1905 برای اولین بار واژه ژنتیک توسط یک زیست شناس انگلیسی به نام ویلیام بیتسون وضع گردید و مورد استفاده قرار گرفت. در سال 1927 واژه جهش166 برای بیان تغییرات فیزیکی در ژن‌ها وضع شد. در سال 1931 واژه برش167 مطرح گردید.
بر اساس تعاریف مطرح شده در زیستشناسی، در هر سلول موجود زنده مجموعهای از کروموزمها به شکل رشتهای از DNA وجود دارد. کروموزمها از تعدادی ژن تشکیل شده اند که هر ژن یک الگو یا صفت خاصی را رمز گشایی می‌نماید. هر ژن موقعیت مشخصی در کروموزم دارد. در روند تولید مثل و ایجاد فرزند جدید، در واقع DNA جدیدی ایجاد می گردد که حاصل ترکیب ژنهای مربوط به DNA های والدین آن فرزند می‌باشد. به همین دلیل فرزندان صفاتی را از هر کدام از والدین می‌گیرند. از آنجایی که برای بعضی صفات بیش از یک ژن به عنوان پارامترهای آن صفت خاص مطرح می باشد، امکان ایجاد صفات جدید بوسیله ترکیب ژن‌های والدین وجود دارد. جهش ژنتیکی نیز ایجاد تغییر در ژنها می‌باشد که به ایجاد صفات جدید(مثبت یا منفی) کمک می نماید. فرضیه تکامل بر ادامه حیات بهترینها و تکثیر نوع برتر اشاره می‌نماید. گونه‌های فراوانی از موجودات در این فرآیند تکثیر نوع برتر به نحوی از بین رفته‌اند. اما در موارد بسیاری نیز موجودات زنده به نحوی خود را با شرایط دشواری که بقای گونه آنها را تهدید می‌نموده، کنار آمده اند و در طول چند نسل متوالی توانسته‌اند تا با تغییر و جهش ژنتیکی در اندام خود، ساختار مورد نیاز برای بقای خود را ایجاد نمایند.
با اثبات کار آمدی علم نوپای بیونیک168 در اوایل قرن بیستم، توجه به فرآیندهای طبیعی نمود بیشتری یافت. بیونیک، علم مطالعه موجودات زنده و استفاده از ساختار فیزیولوژیکی و رفتار ارگانیک آنها برای بهینه سازی عملکرد مصنوعات بشری است. بدلیل اینکه نظام‌های حاکم بر موجودات زنده یک فرآیند تکاملی را درطول دوره‌ها و نسل‌های مختلف طی کرده است و درواقع امتحان خود را پس داده است ، می‌تواند الگوی مناسبی برای کاربردهای مشابه در ابزار ساخت بشر باشد. الگوریتم کلونی مورچگان و ژنتیک نمونههایی از الهام گیری بشر از طبیعت برای حل مسائل مختلف می باشد.
ایده اصلی الگوریتمهای تکاملی169 در سال 1960 میلادی توسط ریچنبرگ مطرح گردید[78]. الگوریتمهای ژنتیک که منشعب از این نوع الگوریتمها می‌باشد، در حقیقت روش جستجوی کامپیوتری بر پایه الگوریتمهای بهینه سازی وبر اساس ساختار ژنها و کروموزمها است که توسط جان هلند (1970) در دانشگاه میشیگان مطرح شد. [78]. پس از وی یکی دانشجویانش به نام دیوید گلدبرگ با حل مسئله بسیار سخت کنترل انتقال خط لوله گاز در رساله خود در سال1989، الگوریتم ژنتیک را مشهور ساخت [68]. یکی از بهترین و جامعترین تعاریف الگوریتم‌های ژنتیک نیز متعلق به کتاب گلدبرگ است:
“الگوریتم‌های ژنتیک مدلی از یادگیری ماشین است که نحوه رفتار آن تمثیلی از فرآیند‌های تکاملی موجود در عالم طبیعت است.”
الگوریتم‌های ژنتیک یکی از قویترین روش‌های برگرفته ازطبیعت است که به جستجوی فضای مسئله بصورت تصادفی ولی هدایت شده پرداخته که این جستجو در قالب تلاش جهت ایجاد جواب‌هایی بهتر، در هر نسل نسبت به جواب‌های نسل قبل صورت میگیرد. الگوریتم‌های ژنتیک یکی از بهترین اشکال بهینه سازی عددی در مسائل علوم و مهندسی را ارائه می‌کند[79].
ساختار الگوریتم‏های ژنتیکی
ویـژگی اساسی الگوریتم ژنتیک سـاده بودن آن میباشد. مراحل الگوریتم ژنتیک بر اساس [68] در شکل(5-1) نشان داده شده است. ابتدا پاسخ مسئله را در قالب یک ساختار کروموزمی تعریف میشود170. با معرفی تابع برازندگی، ارزش ارائه شده در هر کروموزم به صورت عددی بیان می‌گردد. سپس تعداد معینی کروموزم به صورت تصادفی(یا شبه تصادفی) تولید شده که این کروموزمها به عنوان جمعیت اولیه شناخته می‌شوند. در این مرحله تعدادی پاسخ برای مسئله وجود دارد که عمدتا از کیفیت پایینی برخوردار هستند. میزان کیفیت هر کروموزم از جمعیت بر اساس تابع برازندگی مشخص می‌شود. حال با استفاده از روش مناسب (روشی که در آن احتمال انتخاب کروموزم با مقدار برازندگی بهتر، بیشتر از کروموزم دارای مقدار برازندگی ضعیفتر است) دو کروموزم جهت تولید مثل انتخاب شده و سپس با استفاده از این دو کروموزم، کروموزم جدیدی ایجاد می شود(جفتگیری). همچنین با یک احتمال از قبل مشخث شده تعدادی از ژن‌های بعضی از کروموزمها تغییر می‌یابند. انجام مراحل انتخاب، جفتگیری و جهش باعث ایجاد جمعیت جدید (نسل جدید) از کروموزمها می‌گردد. در صورت همگرایی کروموزمها به پاسخ مطلوب عملیات تولید نسل متوقف می‌گردد. در غیر این صورت ایجاد هر نسل از نسل قبلی تا رسیدن به جواب مطلوب یا برقراری شرط پایان الگوریتم ادامه مییابد.
شکل ‏51- ساختار الگوریتم ژنتیک
وجود تنوع زیاد در معرفی فرایند مورد نیاز در هر مرحله، باعث ایجاد الگوریتم‌های ژنتیک متفاوت می‌گردد که می‌تواند به حل مسائل مختلف یا مسائل یکسان با پارامترهای مختلف کمک نماید. لازم به ذکر است که مراحل ذکر شده عنوان فازهای اصلی الگوریتم ژنتیک می‌باشند و معرفی مراحل جدید بین مراحل ذکر شده امکان پذیر است. به عنوان مثال در [69] نحوه ایجاد جمعیت جدید از جمعیت قدیمی به شکل دقیقتری نشان داده شده است. از آنجایی که کارایی الگوریتم ژنتیک به شدت وابسته به پارامترهای آن میباشد؛ معرفی یک الگوریتم ژنتیک برای گونه‌های مختلف یک مسئله به شدت وابسته به ثابت بودن پارامترهای اساسی آن مسئله می‌باشد[70]. در ادامه به تجزیه و تحلیل مراحل الگوریتم ژنتیک می‌پردازیم.
کروموزوم171
در الگوریتم‏های ژنتیکی، هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک جواب ممکن برای مسئله مورد نظر است. خود کروموزوم‏ها (راه حل‏ها) از تعداد ثابتی ژن172 (متغیر) تشکیل می‏شوند. برای نمایش کروموزوم‏ها، معمولاً از کدگذاری‏های دودویی (رشته‏های بیتی) استفاده می‏شود.
جمعیت173
مجموعه‏ای از کروموزوم‏ها یک جمعیت را تشکیل می‏دهند. با تاثیر عملگرهای ژنتیکی بر روی هر جمعیت، جمعیت جدیدی با همان تعداد کروموزوم تشکیل می‏شود.
تابع برازندگی174
به منظور حل هر مسئله با استفاده از الگوریتم‏های ژنتیکی، ابتدا باید یک تابع برازندگی برای آن مسئله ابداع شود. برای هر کروموزوم، این تابع عددی غیر منفی را برمی‏گرداند که نشان دهنده شایستگی یا توانایی فردی آن کروموزوم است.
عملگرهای الگوریتم ژنتیک
در الگوریتم‏های ژنتیکی، در طی مرحله تولید مثل175 ازعملگرهای ژنتیکی استفاده می‏شود. با تاثیر این عملگرها بر روی یک جمعیت، نسل176 بعدی آن جمعیت تولید می‏شود. عملگرهای انتخاب177 ، آمیزش178 و جهش179 معمولاً بیشترین کاربرد را در الگوریتم‏های ژنتیکی دارند.
عملگر انتخاب
این عملگر از بین کروموزوم‏های موجود در یک جمعیت، تعدادی کروموزوم را برای تولید مثل انتخاب می‏کند. کروموزوم‏های برازنده‏تر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند. روش‌های مختلفی برای انتخاب وجود دارد در ادامه نمونه برداری به روش چرخ رولت که در این پایان نامه از آن استفاده شده است مورد بررسی قرار می‌گیرد.
انتخاب چرخ رولت180
انتخاب چرخ رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب‌ترین انتخاب‌های تصادفی بوده که ایده آن، احتمال انتخاب است. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگی آن محاسبه شده که اگر fk مقدار برازندگی کروموزوم Kام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
5-1) P_k=f_k/∑_(i=1)^n▒f_i
حال کروموزوم‌ها را بر اساس Pk مرتب کرده و qk که همان مقادیر تجمعی Pk می‌باشد به صورت زیر به دست می‌آید.
5-2) q_k=∑_(i=1)^k▒P_k
چرخ رولت به این صورت عمل می‌کند که برای انتخاب هر کروموزوم یک عدد تصادفی بین یک و صقر تولید کرده و عدد مذکور در هر بازه‌ای که قرار گرفت، کروموزوم متناظر با آن انتخب می‌شود. البته روش پیاده کردن چرخ رولت به این شکل است که ما یک دایره در نظر گرفته و آن را به تعداد کروموزوم‌ها طوری تقسیم می‌کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوط باشد. حال چرخ را چرخانده و هرکجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می‌گردد.
شکل ‏52- نحوه ارزیابی شایستگی در چرخ رولت[80]
انتخاب چرخ رولت، روشی است که به نسبت مقدار تطابق، اعضا را انتخاب می‌کند. این روش یک چرخ رولت را شبیه سازی می‌کند که تعیین می‌کند کدام اعضاء شانس بازتولید را دارند. هر عضو به نسبت تطابقش، سطحی از چرخ رولت را به خود اختصاص می‌دهد. سپس در هر مرحله انتخاب، یک عضو برگزیده و روند بقدری تکرار می‌شود که به اندازه کافی جمعیت برای نسل بعد انتخاب گردد. این روش انتخاب را ‌می‌توان به صورت زیر بیان کرد:
برداری مانند V را درنظر می‌گیریم: v =[1,…,M] M تعداد عناصر بردار است و اگر تعداد اعضای مجموعه N باشد، هر عضو i دارای تطابقی مانند fi می‌باشد. هر عضو i به نسبت fi ، Pi بار در V تکرار می‌شود. هرچه fi بیشتر باشد این عضو، مکان‌های بیشتری را به خود اختصاص می‌دهد. بر اساس تشکیل برادر V یک مقدار تصادفی 1 ≤r≤M انتخاب می‌شود. این مقدار به مکانی در بردار اشاره می‌کند که در آن مکان خود معرف عضوی از اعضای جمعیت است. به عنوان مثال اگر جمعیتی با N=4 داشته باشیم و تطابق اعضا عبارت باشد از: f1= 10 ، f2= 10 ، f3= 15 ،f4= 25 مقدار مجموع تطابق‌ها عبارتست از: 60= ∑_(i=1)^n▒f_i بردار V را برداری با 60 عنصر در نظر می‌گیریم. این بردار به صورت زیر پر می‌شود. به عضوهای 1و2و3و4 به ترتیب 10و10و15و25 مکان اختصاص می‌یابد. V= {1,1,…, 1,2,2,…,2,3,3,…,3,4,4,…,4}
حال r بین 1 تا 60 به تصادف انتخاب می‌شود. فرض کنید 32r= ، لذا نتیجه می‌شود: v=[32]=3 پس عضو 3 انتخاب می‌شود.
عملگر ترکیب
در طبیعت بقای نسل یکی از مهمترین فاکتورهاست و تنها عملگر ممکن برای این امر آمیزش است. در جریان عمل ترکیب به صورت اتفاقی بخش‌هایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می‌شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.
هدف تولید فرزند جدید به این امید است که خصوصیات خوب دو موجود در فرزندشان جمع و یک موجود بهتر را تولید کند. بر اساس مباحث تئوری ترکیب اعضا با تطابق بالا باعث بوجود آمدن اعضایی می‌شود که تطابق بیشتری از تطابق میانگین دارند.
روش‌های گوناگونی برای ترکیب وجود دارد که در ادامه به دو روش معروف در این زمینه اشاره می‌شود:
ترکیب تک نقطه ای181
اگر عملیات ترکیب در یک نقطه انجام شود به آن ترکیب تک نقطه‌ای می‌گویند.
عمل ترکیب حاصل ترکیب کروموزوم‌های پدر و مادر است. ابتدا بصورت تصادفی نقطه ای از کروموزوم برای تولید مثل انتخاب می‌گردد. سپس برای تولید مثل به ترتیب قسمت‌هایی از بیت‌های کروموزوم‌های پدر و مادر برای تولید مثل انتخاب می‌شوند. در شکل (5-3) مثالی از ترکیب نشان داده شده است.
شکل ‏53- یک نمونه ترکیب
در این شکل کروموزوم‌های 1 و2 در نقش والدین هستند. و حاصل تولید مثل آنها در رشته هائی بنام Offspring ذخیره شده است.دقت شود که علامت “|” مربوط به نقطه شروع تولید مثل می باشد و در رشته های Offspring اعدادی که بعد از نقطه شروع تولید مثل قرار می گیرند مربوط به کروموزوم‌های مربوط به خود می باشند. بطوریکه اعداد بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کروموزوم 1 و اعداد بعد از نقطه شروع تولید مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع تولید مثل مربوط به کروموزوم 2 می‌باشند
ترکیب ادغام دو نقطه ای182
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.
شکل ‏54- روش ادغام دونقطه‌ای
ترکیب لازم نیست در هر نسل اتفاق بیفتد. در واقع ممکن است نسل‌هایی بدون عملگر ترکیب به نسل‌های جدید تبدیل شوند. برای تعیین رخ دادن یا ندادن ترکیب از پارامتری به نام احتمال ترکیب PC استفاده می‌شود که این پارامتر مقداری بین 0 و 1 است. از آنجا که ترکیب نقشی اساسی در رشد مقدار میانگین تطابق جمعیت دارد، مقدار PC بین 0.7 تا 0.8 در نظر گرفته می‌شود. بین اندازه جمعیت و نوع ترکیب ارتباط مستقیمی وجود دارد. تجربیات حاصل از پیاده‌سازی نشان می‌دهد که ترکیب تک نقطه‌ای برای جمعیت‌های کوچک بسیار مناسب است. اما برای جمعیت‌های بزرگ تر، ترکیب دو نقطه‌ای مناسب تر است.
عملگر جهش
پس از اتمام عمل ترکیب، عملگر جهش بر روی کروموزوم‏ها اثر داده می‏شود. جهش باعث جستجو در فضاهای دست نخورده مسئله می‌شود. می‌توان استنباط کرد که مهمترین وظیفه جهش اجتناب از همگرایی به نقطه بهینه محلی است. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر می‏دهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل می‏کند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار می‏دهد. در شکل (5-5) نحوه و مفهوم جهش در یک حالت خاص نشان



همه حقوق محفوظ است

Posted آگوست 6, 2018 by 92 in category "مقالات

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *