آگوست 6

گره‌‌‌، دوبعدی، رله، می‌شود.، کروموزم

داده شده است.
پس از اتمام عمل جهش، کروموزوم‏های تولید شده به عنوان نسل جدید شناخته شده و برای دور بعد اجرای الگوریتم ارسال می‏شوند.
درجهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود و یا ژنی که تا کنون در جمعیت وجود نداشته است به آن اضافه شود. احتمال جهش که Pm نامیده می‌شود مقداری است که توسط کاربر تعیین می‌شود. مقدار این پارامتر معمولا بسیار کوچک در نظر گرفته می‌شود و معمولا برای محاسبه آن از فرمول زیر استفاده می کنند.
5-3) P_m=1/N که در این رابطه N طول کروموزم است.
اگر مرحله جهش صورت نگیرد، فرزندان بلافاصله بعد از ترکیب و بدون هیچ تغییری بوجود می آیند.
شکل ‏55- مثالی از جهش و نحوه‌ی کارکرد آن
کدگذاری و همگرایی الگوریتم ژنتیک
کدگذاری یکی از عناصر مهم و تعیین کننده در هر الگوریتم ژنتیک است[70]. به تبدیل پاسخ مسئله به صورت یک ساختار (کروموزم) که از مجموعه ای از ژن‌ها تشکیل یافته، کدگذاری می‌گویند. در واقع الگوریتم ژنتیک به جای این که به طور مستقیم بر روی پارامترها یا متغیرهای مسئله کار کند، با شکل کد شده آنها سروکار دارد[79]. تاکنون محدودیت خاصی برای ساختار ژن‌ها مطرح نشده است، به همین دلیل روش‌های متنوعی برای کدگذاری مسائل مورد استفاده قرار می گیرد. در [78] ، [78] و [80]تعدادی از روشهای موجود بررسی شده اند.
قبل از این که یک الگوریتم ژنتیکی بتواند اجرا شود، ابتدا باید کدگذاری (یا نمایش) مناسبی برای مسئله مورد نظر پیدا شود. معمولی ترین شیوه نمایش کروموزوم‌ها در الگوریتم ژنتیک به شکل رشته‌های دودویی است. هر متغیر تصمیم‌گیری به صورت دودویی در آمده و سپس با کنار هم قرار گرفتن این متغیرها کروموزوم ایجاد میشود. گرچه این روش گسترده ترین شیوه کدگذاری است اما شیوه های دیگری مثل نمایش با اعداد حقیقی در حال گسترش هستند. همچنین یک تابع برازندگی نیز باید ابداع شود تا به هر راه‏ حل کدگذاری شده ارزشی را نسبت دهد. در طی اجرا، والدین برای تولید مثل انتخاب می‏شوند و با استفاده از عملگرهای آمیزش و جهش با هم ترکیب می‏شوند تا فرزندان جدیدی تولید کنند. این فرآیند چندین بار تکرار می‏شود تا نسل بعدی جمعیت تولید شود. سپس این جمعیت بررسی می‏شود و در صورتی که ضوابط همگرایی برآورده شوند، فرآیند فوق خاتمه می‏یابد.
سوالی[a273] که می‌تواند در اینجا مطرح شود این است که آیا الگوریتم ژنتیک همواره به سمت بهینه مطلق همگرا می‌شود؟
تاکنون تحقیقات مختلفی [a274]برای بررسی همگرایی الگوریتم ژنتیک با استفاده از زنجیره مارکوف صورت گرفته است[78]. این بررسی‌ها بر روی جمعیتهای بزرگ با نرخ جهش پایین، به صورت آماری انجام شده است. مطالعات دیگری برای پیدا کردن یک حد بالا برای تعداد تکرار ها نیز صورت گرفته است اما به طور کلی یک اثبات صریح و جامع ریاضی درباره همگرایی به سمت بهینه مطلق وجود ندارد. تحقیقات رونکلف در سال 1994 همگرایی الگوریتم ژنتیک[a275] را تحت شرایط خاص به اثبات می‌رساند[3[a276]]. در این تحقیقات نشان داده شده است که همگرایی به سمت بهینه مطلق یک خاصیت ذاتی الگوریتم ژنتیک نمی‌باشد ولی باشرایط خاصی امکان پذیر است. تحلیل‌های ریاضی انجام گرفته در این تحقیق در قالب جندین قضیه و با استفاده از مدل زنجیره مارکوف نشان داده‌است که چنانچه در هر مرحله تولید از الگوریتم ژنتیک بهترین جواب‌ها نگاه داشته شده و [a277]با احتمال یک به مرحله بعد وارد شوند، الگوریتم به سمت بهینه مطلق همگرا می‌شود. عوامل متعددی شامل جمعیت اولیه، مقادیر احتمال جهش و ترکیب در سرعت همگرایی الگوریتم ژنتیک موثر هستند. همچنین چگونگی انجام عمل ترکیب و جهش، تابع برازندگی و چگونگی انتخاب جمعیت بعدی نیز از جمله این عوامل ‌می‌باشند. چگونگی تاثیر این عوامل در سرعت و همگرایی الگوریتم ژنتیک به مسئله مورد نظر بستگی دارد و از طریق آزمایش بدست می‎آید[3].
‏56- کد برنامه مجازی الگوریتم ژنتیک ساده و فلوچارت آن
الگوریتم پیشنهادی
در الگوریتم پیشنهادی، برای کاهش فضای جستجو و تعریف کرموزوم‌های مناسب در الگوریتم ژنتیک ﻛﺮوﻣﻮزوم‌هایی به طول زیر تعریف می‌کنیم:
5-3)
در رابطه (5-3) ss تعداد گره‌‌‌های درخواست کننده ترافیک، rss تعداد رله‌های بین ss با BS در طول مسیر ارسال و n تعداد کل گره‌‌‌های درخواست کننده است.
ترتیب هر کروموزوم، مشخص کننده ترتیب ارسال جریان‌های درخواستی توسط گره‌‌‌ها است . تعریف کروموزم استفاده مجدد از فضای فرکانسی را دربر نمی‌گیرد(این امر موثر در کاهش درجه سختی و اضافه کردن قابلیت پردازش موازی مسئله است). البته در مرحله محاسبه‌ی تابع برازندگی با تفسیر کروموزم‌ها، استفاده مجدد از فضای فرکانسی به مسئله اضافه و درنظر گرفته خواهد شد و در ادامه به چگونگی درنظر گرفتن آن اشاره خواهد شد.
با این تعریف هر ژن متغیر کروموزوم معرف یک ss و تعداد تکرار هر ss در کروموزوم متناسب با تعداد رله مود نیاز برای آن است.
هر جایگشت کروموزوم، یک جواب ممکن برای مسئله زمان‌بندی در اولویت ارسال است. از اینرو بر اساس تعریف کروموزوم، تعداد کل جواب‌های مسئله عبارت است از:
5-4)
در ادامه با بیان یک مثال، تفسیر کروموزم را بیان خواهیم کرد.
توپولوژی شکل(5-7) نحوه اتصال 5 گره‌‌‌ به BS به کمک 3 رله را نشان می‌دهد. برای مثال ترافیک درخواستی گره‌‌‌ 2 از طریق رله 1و2 به ایستگاه مرکزی ارسال می‌شود. ارسال گره‌‌‌2 با گره‌‌‌1 دارای تداخل نوع اول و ارسال همزمان گره‌‌‌ 5 و4 دارای تداخل نوع دوم است.
شکل ‏57- توپولوژی شبکه-خطوط ممتد: مسیر ارسال- خط چین بین گره‌‌‌ 2و1 تداخل نوع اول- خط چین بین گره‌‌‌ 4و5 تداخل نوع دوم
بر اساس تعریف کروموزم ، یک کروموزوم برای شکل (5-7) به صورت زیر است:
شکل ‏58 – یک کروموزوم برای جواب مسئله شکل (5-7)
گره‌‌‌ 4 ،1،2،3و 5 در هر بار درخواست برای ارسال به BS به ترتیب نیاز به 2،2،3،3 و 1 رله دارند. بنابراین تعداد تکرار آن‌ها در کروموزوم 2،2،3،3 و 1 است. هر جایگشت کروموزوم شکل(5-8) نیز یک راحل ممکن مسئله زمان‌بندی شکل (5-7) است. در این کروموزوم در ابتدا گره‌‌‌1 و در نهایت گره‌‌‌ 5 ترافیک خود را ارسال می‌کند.
در شکل(5-9) کروموزمی دیگر نشان داده شده است. در این کروموزم ابتدا گره‌‌‌ 1 درخواست خود را برای رله 1 ارسال می‌کند. سپس گره‌‌‌ 2 درخواست خود را برای رله 1 ارسال می‌کند در ادامه گره‌‌‌ 3 درخواست خود را برای رله 3 و در دو ارسال بعدی درخواست گره‌‌‌ 1 از طریق رله 1و2 به BS می رسد. این فرآیند تا آخرین ژن کروموزوم ادامه دارد.
شکل ‏59- کروموزومی دیگر برای جواب مسئله شکل (5-7)
در این مثال گره‌‌‌ 5 با قابلیت استفاده مجدد از فضای فرکانسی می‌تواند همزمان در ارسال گره‌‌‌ 1 به رله 1 ارسال داشته باشد که منجر به بازدهی بیشتر می‌شود که آن را در تابع برازندگی درنظر خواهیم گرفت.
در تولید جمعیت به عنوان اولین مرحله الگوریتم ژنتیک، متناسب با طول کروموزوم مجموعه ای از جواب‌های ممکن انتخاب می‌شود. شرایط تصادفی در ایجاد جمعیت در نظر گرفته شده است.
ﺑﻌﺪ از اﻳﺠﺎد ﺟﻤﻌﻴﺖ اوﻟﻴﻪ، متناسب با تابع برازندگی برای عمل ترکیب ﺑﺮ اﺳﺎس وزن رولت که در بخش قبل معرفی شد، کروموزم‌ها مرتب می‌شوند. وزن رولت به هر کروموزوم ارزشی بین صفر و یک مطابق ارزش تابع برازندگی اعمال می‌کند. بنابراین احتمال انتخاب کروموزوم با تابع برازندگی بهتر، بیشتر است.
در ﻋﻤﻠﮕﺮ ﺗﺮﻛﻴﺐ، از هر دو روش ترکیب تک نقطه‌ای و دو نقطه‌ای استفاده می‌شود. به دلیل آنکه عملگر ترکیب برخی اوقات منجر به تولید کروموزوم‌های نادرست می‌شود، رﺷﺘﻪ‌ﻫﺎ ﻓﻘﻂ در ﺻﻮرﺗـﻲ ﺗﺮﻛﻴﺐ ﻣﻲ‌ﺷـﻮﻧﺪ ﻛﻪ ﻣﻨﺠﺮ ﺑﻪ ﺗﻮﻟﻴﺪ ﻳﻚ کروموزوم سالم ﺷﻮﻧﺪ. در صورت تولید کروموزم‌های ناسالم، کروموزوم اصلاح خواهد شد. نمونه‌ای از کروموزوم ناسالم بر اثر ترکیب که منجر به تولید SS با تعداد رله اشتباه می‌شود درشکل(5-10) نشان داده شده است. در این مثال که از ترکیب دو کروموزوم قبلی ایجاد شده است به دلیل عدم کنترل عملگر ترکیب؛ گره‌‌‌ 5 از کروموزوم حذف شده و برای گره‌‌‌ 2 به جای 3 رله 4 رله درنظرگرفته شده است.
شکل ‏510- نمونه‌ای از کروموزوم ناسالم در عمل ترکیب کنترل نشده
پس از عمل ترکیب، متناسب با تعداد جمعیت بر روی تعدادی از کروموزوم‌ها، تابع جهش اعمال شد. همان‌طور که گفته شد جهش باعث جستجو در فضاهای دست نخورده مسئله می‌شود و مهترین وظیفه‌اش اجتناب از همگرایی به بهینه محلی است. در عملگر جهش از جهش حقیقی استفاده می شود. در جهش حقیقی به طور تصادفی جای دو ژن کروموزوم باهم عوض می‌گردد. نمونه‌ای از جهش برای کروموزم شکل (5-11) در زیر نشان داده شده است. با توجه به نحوه‌ی تعریف کروموزم، عملگر جهش همواره منجر به تولید کروموزم درست خواهد شد و برخلاف عملگر ترکیب؛ مشکل کروموزوم نادرست را نخواهیم داشت.
شکل ‏511- کروموزوم حاصل از عملگر جهش
درتابع برازندگی قبل از محاسبه‌ی میزان برازندگی، در تفسیر هرکروموزوم استفاده‌ی مجدد از فضای فرکانسی در نظر گرفته می‌شود. استفاده مجدد از فضای فرکانسی با توجه به توپولوژی شبکه بررسی می‌گردد. درنظرگرفتن استفاده مجدد از فضای فرکانسی منجر به افزایش قبولی تعداد درخواست تضمین شده با تأخیر به انتها و گذردهی شبکه می‌شود.
با لحاظ کردن استفاده مجدد از فضای فرکانسی، تابع برازندگی بر اساس مجموعه ای از صفات ورودی(کروموزوم) یک مقدار حقیقی برای هر کروموزم تولید می نماید. در واقع تابع برازندگی بر اساس پارامترهای مورد توجه برای حل یک مسئله، کیفیت یک پاسخ(کروموزوم) را به صورت عددی مشخص می نماید. در صورتی که این عدد، میزان مطلوبیت کروموزم را نشان دهد، مسئله مورد نظر از جمله مسائل ماکزیمم سازی است(هدف الگوریتم ژنتیک ایجاد کروموزمی خواهد بود که مقدار تابع برازندگی آن کروموزم ماکزیمم باشد). غالبا تابع برازندگی را برابر با همان تابع هدف مسئله بهینه‌سازی در نظر می‌گیرند[79]. در حقیقت تابع برازندگی یک تابع مشتق شده از تابع هدف در عملیات ژنتیکی است که معمولا مقدار آن مثبت میباشد.
تابع برازندگی، مجموع تعداد گره‌‌‌هایی تعریف می‌شود که درخواست ارسال انتها به انتهای آن‌ها کمتر از تأخیر درخواستی گره‌‌‌ باشد. برازندگی هر کروموزوم را به صورت رابطه(5-5) بیان می‌کنیم:
5-5)
در تابع برازندگی، delayssi تأخیر ارسال درخواست گره‌‌‌ ssi به/از BS و deadlinessi تأخیر مجاز ارسال برای درخواست گره‌‌‌ به/از ssi است. بنابراین در تابع برازندگی ارزش هر کروموزوم بر اساس تعداد گره‌‌‌هایی که درخواست تأخیر انتها به انتهای آن‌ها تضمین می‌شود محاسبه می‌شود. هرچه این تعداد بیشتر باشد ، برازندگی کروموزوم موجود بیشتر بوده و در نسل‌های بعدی احتمال حضور این کروموزوم بیشتر خواهد بود.
چرخه الگوریتم ژنتیک با تولید یک جمعیت جدید بر اساس مراحل قبل تا رسیدن به نتایج مدنظر ادامه پیاده می‌کند. در ابتدای هرمرحله از الگوریتم ژنتیک جمعیت موجود در یک حافظه نگهداری می‌شود. بعد از ایجاد جمعیت جدید در پایان هر مرحله از الگوریتم ژنتیک، برازندگی کروموزوم‌های موجود در جعمیت جدید محاسبه و با جمعیت موجود در حافظه مقایسه می‌شود.از میان کروموزم‌ها، بهترین کروموزوم‌ها انتخاب و به عنوان جمعیت اصلی برای مرحله بعد مورد استفاده قرار می‌گیرند.مزیت این کار آن است که همیشه بهترین جواب‌ها حفظ می‌شوند. در نهایت الگوریتم ژنتیک زمانی پایان می‌یابد که در یک بازه مشخص بهبودی در میزان تابع برازندگی ایجاد نشود. در بین جمعیت آخر تولید شده، کروموزمی با بیشینه میزان برازندگی انتخاب می‌شود. این جواب، جواب بهینه بدست آمده است. در نهایت بر اساس کروموزوم بدست آمده ، زمان‌بندی بین گره‌‌‌ها در شبکه انجام می‌شود.
دیاگرام الگوریتم پیشنهادی را به صورت زیر بیان می‌کنیم:
با توجه به نحوه‌ی تعریف کروموزوم در مسئله و در نظر گرفتن استفاده مجدد از فضای فرکانسی، درجه سختی مسئله در پیاده‌سازی انجام شده به صورت o(r3×n4) بدست می‌آید.
شکل ‏512 دیاگرام الگوریتم پیشنهادی
همان‌طور که اشاره شد در الگوریتم پیشنهادی، برای کاهش فضای جستجو و تعریف کرموزوم‌های مناسب در الگوریتم ژنتیک ﻛﺮوﻣﻮزوم‌هایی به طول رابطه(5-3) در نظر می‌گیریم. در این رابطه اشاره شد ss تعداد گره‌‌‌های درخواست کننده ترافیک، rss تعداد رله‌های بین ss با BS در طول مسیر ارسال و n تعداد کل گره‌‌‌های درخواست کننده است.
ترتیب هر کروموزوم، مشخص کننده ترتیب ارسال جریان‌های درخواستی توسط گره‌‌‌ها است . تعریف کروموزم استفاده مجدد از فضای فرکانسی را دربر نمی‌گیرد.اما شاید این سوال به ذهن برسد که چرا نباید از کروموزم دوبعدی استفاده کرد و برتری کروموزوم تک بعدی(که در مرحله دیگر دوبعدی می شود) به کروموزوم دوبعدی چیست؟.
تعریف کروموزوم تک بعدی ، قسمتی از فضای کل جواب‌های مسئله را( در تولید جمعیت اولیه و جهش) در نظر می‌گیرد که منجر به ایجاد کروموموزم‌های همواره درست می‌شود ولی در کروموزوم دوبعدی فضای پویش مسئله کروموزوم ‌های نادرست بسیاری را شامل می‌شود. اثر و نمود این پویش‌های نادرست در تولید جمعیت اولیه و جهش؛ در ویژگی اصلی مسئله زمان‌بندی یعنی NP-hard بودن است. با رشد تعداد نودهای شبکه، فضای پویش و تولید جواب مطلوب به صورت نمایی رشد می‌نماید.
شکل ‏513- نمایش فضای پویش تک بعدی و دوبعدی
می‌دانیم تعداد کل فضای پویش جواب‌های مسئله درالگوریتم تک بعدی عبارت است از:
اما در الگوریتم ژنتیک دوبعدی تعداد کل فضای پویش جواب‌های مسئله(به دلیل درنظر گرفتن کروموزوم‌های نادرست) عبارت است از:
5-6)
با تقسیم نسبت فضای الگوریتم دوبعدی به تک بعدی داریم:
5-7)
رابطه (5-7) فاکتور نسبت گسترش فضای پویش مسئله دوبعدی به تک بعدی را مشخص می‌کند. برای اینکه احساسی از بزرگی این گسترش داشته باشیم آزمایشی انجام شد که نتایج آن در شکل (5-14)گزارش شده است. در این آزمایش به ترتیب در هر شکل تعداد رله‌های شبکه را از 1 به 3 افزایش دادیم و در هر بار این نتایج را برای 5 تا 15 نود در شبکه محاسبه کردیم(امکان نمایش برای بیشتر از 15 نود در 1 رله و 10 نود برای 2 و3 رله به دلیل حجم محاسبات و بزرگی جواب مسیر نبود). همان طور که مشخص است با افزایش تعداد نودهای شبکه، نسبت فضای پویش جواب‌های مسئله در حالت دوبعدی نسبت به تک بعدی به صورت نمایی افزایش می‌یابد و این رشد با افزایش تعداد رله‌ها از سرعت بیشتری برخوردار می‌شود. این رشد نمایی فضای پویش برجستگی استفاده از الگوریتم ژنتیک تک بعدی را نمایان می‌سازد. علاوه بر محاسبات تحلیلی که انجام شد برای تبیین بیشتر مسئله هر دو الگوریتم دوبعدی و تک بعدی پیاده سازی شد. در شکل‌های( 5-15) تا (5-17) این نتایج در چند حالت مختلف نمونه گزارش شده است. همان طور که از پیاده‌سازی‌ها در شرایط مختلف مشخص است مدت زمان شبیه سازی دوبعدی نسبت به تک بعدی به مراتب بیشتر است.
شکل ‏514- نمایش گسترش شبکه تعداد نودهای شبکه به ترتیب برای افزایش تعداد رله های شبکه از 1 تا 3
شکل ‏515- نمودار سمت چپ : توپولوژی شبکه خطوط آبی : مسیر ارسال- خطوطو قرمز: تداخل ارسال ، سمت راست- : بازدهی الگوریتم ژنتیک در درصد تضمین تاخیر انتها به انتها – آبی: دوبعدی قرمز تک بعدی- مدت زمان شبیه سازی دوبعدی: 6.12 تک بعدی 1.14 (ثانیه)
شکل ‏516نمودار سمت چپ : توپولوژی شبکه خطوط آبی : مسیر ارسال- خطوطو قرمز: تداخل ارسال ، سمت راست – : بازدهی الگوریتم ژنتیک در درصد تضمین تاخیر انتها به انتها – آبی: دوبعدی قرمز تک بعدی- مدت زمان شبیه سازی دوبعدی: 91.51 تک بعدی: 4.56 (ثانیه)
شکل ‏517- نمودار سمت چپ : توپولوژی شبکه خطوط آبی : مسیر ارسال- خطوطو قرمز: تداخل ارسال، سمت راست- : بازدهی الگوریتم ژنتیک در درصد تضمین تاخیر انتها به انتها – آبی: دوبعدی قرمز تک بعدی- مدت زمان شبیه سازی دوبعدی: 321.56 تک بعدی 7.89 (ثانیه)
در جدول 5-1 مقایسه ای بین الگوریتم دوبعدی و تک بعدی ارائه شده است.
جدول ‏51– مقایسه الگوریتم ژنتیک دوبعدی و تک بعدی در مسئله زمان‌بندی
تک بعدی
دوبعدی
فضای جستجو و پویش
پوشش تمامی جواب‌های درست
شامل می‌شود
فضای جستجوی نادرست
پویش نمی شود
پویش می شود
سرعت تولید جمعیت اولیه
سریع
کند
کنترل تولید جمعیت اولیه
بی نیاز
کنترل ترکیب
کنترل جهش
همگرایی محلی
شامل نمی شود
محاسبات
کمتر
بیشتر
سرعت و زمان همگرایی
الگوریتم تک بعدی نسبت به دوبعدی سریعتر است.
ذکر این نکته حائز اهمیت است که در تفسیر کروموزوم تک بعدی در الگوریتم پیشنهادی به ترتیب ژن هر کروموزوم به ترتیب با ژن اول تا ژن ما قبل خود مورد بررسی قرار می گیرد و اگر هر نود(هر ژن کروموزوم) امکان ارسال همزمان با اولین نود ماقبل(ژن ماقبل) خود داشته باشد ارسال همزمان در نظر گرفته می‌شود. به عنوان مثال برای توپولوژی شکل( 5-7) نمونه ای از این تفسیر کروموزوم در شکل (5-18)نشان داده شده است. برای ژن‌های 4،7 و 11 امکان ارسال همزمان با نودهای ماقبل خود وجود دارد. د



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

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

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

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