Offsprings :
شکل ۴‑۱۱- روش تقاطع تک نقطهای [۵۰]
تقاطع در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت میشود زیرا اجازه میدهد ژنهای خوب یکدیگر را بیابند. بر اساس مباحث تئوری تقاطع، اعضا با تطابق بالا باعث به وجود آمدن اعضایی میشوند که از تطابق میانگین، تطابق بیشتری دارند.
عملگر جهش[۱۷۹] : در طبیعت برخی عوامل باعث به وجود آمدن تغییرات غیرقابلپیشبینی در کروموزمها میشوند. از آنجایی که الگوریتمهای ژنتیکی از قانون تکامل پیروی میکنند، در این الگوریتمها نیز عملگر جهش با احتمال کم اعمال میشود. بهطورکلی، گاهی اوقات در الگوریتم ژنتیک برای آنکه فرزندان بتوانند برخی ویژگیهایی که در والدینشان وجود نداشته است، به دست آورند از عملگر جهش استفاده می شود. این عملگر از قرار گرفتن الگوریتم ژنتیک در بهینه محلی جلوگیری میکند و همچنین با بهره گرفتن از آن میتوان فضاهای ناشناخته مسئله را جستجو نمود. در جهش ممکن است ژنی از مجموعه ژنهای جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است به آن اضافه شود. البته جهش نباید زیاد صورت بگیرد زیرا در این حالت الگوریتم ژنتیک به جستجوی کاملاً تصادفی تبدیل خواهد شد. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری، روشهای متفاوتی برای اعمال آن استفاده میشود.
در روش پیشنهادی، از اعضای جمعیت به تعداد نرخ جهش به طور تصادفی انتخاب می شود و سپس به ازای هر عضو انتخاب شده، یکی از ژنها به طور تصادفی برگزیده می شود. در این مسئله طول کروموزوم برابر با تعداد وظایف میباشد و بنابراین ژنی به طور تصادفی از بازهی [۱… n] انتخاب می شود. حال با توجه به اینکه ژن انتخاب شده شامل وظیفه مورد نظر و هسته پردازشی نگاشت شده بر روی آن میباشد به طور مثال فرض می شود وظیفه i انتخاب شده بر روی هسته پردازشی j نگاشت شده است. همانطور که گفته شد، هر وظیفه دارای برداری است شامل اتلاف توان حاصل از اجرای وظیفه مذکور بر روی هستههای پردازشی مختلف. بنابراین برای اعمال عملگر جهش ابتدا بررسی می شود که آیا این وظیفه i انتخاب شده بر روی هستهی نگاشت شده فعلی (هستهی j) دارای کمترین توان مصرفی هست یا نه. اگر وظیفه i دارای کمترین توان مصرفی بر روی هستهی j باشد، در این صورت ژن دیگری در این کروموزوم به طور تصادفی انتخاب می شود و محتوای این دو ژن که شامل هستههای پردازشی وظایف مربوط به آنها است، جابجا میگردد. حال اگر وظیفهی i دارای کمترین توان مصرفی بر روی هسته پردازشی j نباشد، با توجه به بردار مربوط به اتلاف توان اجرای وظیفهی i بر روی هستههای مختلف، هستهی پردازشی که این وظیفه بر روی آن کمترین توان مصرفی را دارد، یافت می شود و با هستهی j جایگزین میگردد.
همانگونه که ملاحظه می شود، در این الگوریتم به دلیل آنکه یکی از اهداف مسئله، کمینهکردن توان مصرفی میباشد، سعی شده است که عملگر جهش علاوه بر ایجاد تغییرات تصادفی در ساختار ژنها که به طور معمول انجام می شود، به گونه ای توان مصرفی را کاهش دهد.
ایجاد جمعیت جدید: پس از اعمال عملگرهای ژنتیکی مجموعه ای از جوابهای جدید ایجاد می شود. همانطور که در مراحل الگوریتم ذکر شد، در مرحله ۶، نسل جدید فرزندان با نسل قبل که شامل والدین است، تجمیع می شود. برای ادامه روند الگوریتم لازم است از روشی مناسب استفاده نمود تا بهترین جوابها با توجه به اندازه جمعیت به نسل بعد منتقل شوند. در روش پیشنهادی، پس از ایجاد جمعیت اولیه و اعمال هر یک از عملگرهای جهش و تقاطع، کیفیت هر راهحل ایجاد شده توسط تابع برازندگی مشخص می شود. سپس در مرحله ۷ که شامل عملیات چندهدفه میباشد، هر یک از جوابها در جمعیت تجمیع شده به کمک روش مرتبسازی نامغلوب در جبههی مربوط به خود قرار میگیرند. شماره جبههی هر جواب، رتبهی آن را مشخص می کند. هرچه این شماره کمتر باشد جواب بهتر است. سپس به کمک روش فاصله ازدحام فاصله هر جواب نسبت به جوابهای دیگر در همان جبهه مشخص می شود. هر جوابی که دارای مقدار بیشتری باشد نشاندهنده آن است که در بخشهای خلوتتر از فضای پاسخ واقع شده است و در نتیجه دارای الویت بالاتری خواهد بود. دادن الویت بالاتر به این دست جوابها سبب خواهد شد تا جستجو به سمت فضاهای ناشناخته گرایش پیدا کند. بنابراین در مرحله مرتبکردن جوابها در عملیات چند هدفه، ابتدا جوابها براساس فاصلهی ازدحامشان به صورت نزولی مرتب میشوند و سپس براساس رتبهشان که همان شماره جبههی هر جواب میباشد، به صورت صعودی مرتب میشوند. در نتیجه راهحلهایی که از لحاظ شماره جبهه بهتر هستند بالاتر قرار میگیرند و در درون جبهه جوابهایی که از نظر فاصلهی ازدحام بهتر هستند بالاتر قرار میگیرند. حال برای انتخاب جمعیت جدید جهت ادامه الگوریتم، چون جوابها اکنون مرتب شده هستند، از ابتدا به تعداد اندازه جمعیت انتخاب می شود زیرا بهترین جوابها بالاتر قرار گرفتهاند (مرحله ۸) . انجام این کار باعث می شود بهترین جوابها در نسلهای بعد نیز باقی بمانند و بر اثر عملگرهای ژنتیکی از بین نروند که در الگوریتم ژنتیک به این ویژگی، نخبه سالاری[۱۸۰] گفته می شود. پس از انتخاب بهترین جوابها برای نسل بعد، چون ممکن است این جوابهای جدید دوباره بر یکدیگر غلبه کنند، بنابراین این عملیات چندهدفه بار دیگر بر روی جمعیت نهایی انتخاب شده اعمال می شود (مرحله ۹). در نهایت به ابتدای حلقه بازگشته و تا برقراری شرط توقف این عملیات تکرار می شود.
نتیجهگیری
یک برنامه کاربردی بیدرنگ دارای تعدادی وظیفه و ارتباطات بین آنها با عنوان جریانهای ترافیکی میباشد. هر یک از این وظایف و جریانهای ترافیکی دارای ویژگیهایی از جمله نیازمندیهای زمانی سخت میباشند. در این فصل روشی بر مبنای الگوریتم ژنتیک چندهدفه NSGA-II ، برای نگاشت این دسته از برنامه های کاربردی بر روی هستههای پردازشی شبکه بر تراشه ارائه گردید. در روش پیشنهادی هستههای پردازشی شبکه از نوع ناهمگن میباشند و به عبارتی عناصر پردازشی متفاوت هستند. در این الگوریتم دو هدف وجود دارد: ۱) کمینه کردن اتلاف توان کلی که ناشی از اتلاف توان برای انتقال بستههای اطلاعاتی در سطح شبکه و اتلاف توان اجرای وظایف بر روی مولفههای پردازشی است. ۲) کمینه کردن تعداد وظایف و جریانهای ترافیکی که قابل زمانبندی نیستند و مهلت اتمامشان رعایت نشده است.
در این فصل همچنین مدلهای تحلیلی مربوط به زمانبندی و توان مصرفی و جزئیات الگوریتم ژنتیک از جمله نحوه نمایش جوابها، ایجاد جمعیت اولیهای، عملگرهای ژنتیکی و … توضیح داده شدند.
فصل پنجم
ارزیابی نتایج
مقدمه
در این فصل نتایج پیادهسازی روش پیشنهادی در محیط ویندوز و نرمافزار متلب ارائه میشود. نتایج حاصل از آزمایشها از نظر معیارهای مختلف شامل تعداد وظایف و جریانهای ترافیکی غیر قابل زمانبندی و توان مصرفی مورد ارزیابی و مقایسه قرار گرفتهاند. در ارزیابی نتایج دو معیار امکانپذیری و میزان بهرهوری راه حل ها نیز بررسی شده است. همانطور که نتایج آزمایشات نشان میدهد، روش پیشنهادی با در نظر گرفتن این دو معیار نسبت به روشهای موجود سریعتر به جوابهای بهینه همگرا میشود.
در ادامه این فصل ابتدا معیارهای استفادهشده برای ارزیابی الگوریتم، تعریفشدهاند. سپس محک مورد استفاده به عنوان برنامه کاربردی برای ورودی الگوریتم معرفی میشود و در انتها نیز نتایج به دست آمده از آزمایشها و نمودارهای مربوط به هر یک ارائهشده و به طور کامل مورد ارزیابی و تجزیه و تحلیل قرارگرفته است.
معیارهای ارزیابی
به منظور بررسی میزان کارایی روش پیشنهادی برای نگاشت وظایف یک برنامه کاربردی بر روی هستههای پردازشی یک شبکه بر تراشه، باید مجموعه جوابهای تولید شده از جنبههای مختلف مورد ارزیابی قرار گیرند تا کارایی الگوریتم مورد نظر مشخص گردد. در این پایان نامه برای ارزیابی کارایی هر یک از راه حل های نگاشت ایجاد شده توسط الگوریتم ژنتیک چند هدفهی NSGA-II از معیارهای شناختهشدهای شامل میزان اتلاف توان و تعداد وظایف و جریانهای ترافیکی که قابل زمانبندی نیستند و همچنین معیارهای جدید ارائه شده با عنوان امکانپذیری و میزان بهرهوری استفاده شده است. ویژگیهای هر یک از این معیارها در ادامه این بخش به صورت مختصر توضیح دادهشده است و بررسی دقیق آنها در بخش نتایج به دست آمده انجام خواهد شد.
در واقع هر یک از راه حل های نگاشت در الگوریتم ژنتیک توسط تابع برازندگی ارزیابی میشوند و همانطور که در فصل قبل توضیح داده شد، در این تابع جوابها براساس دو هدف که در حقیقت همان دو معیار زیر میباشند، بررسی میشوند. این دو معیار در فصل قبل به طور کامل همراه با تحلیلهای مربوط به هر یک توضیح داده شدند بنابراین در اینجا مفاهیم هر یک به طور مختصر بیان میگردد.
معیار میزان توان مصرفی: این معیار میزان اتلاف توان کلی هر یک ازجوابهای تولید شده توسط الگوریتم در هر نسل را مشخص میکند. این توان ناشی از اجرای وظایف کاربرد مورد نظر بر روی هستههای پردازشی مختلف و همچنین انتقال بستههای جریانهای ترافیکی در سطح شبکه است. برای محاسبهی این توان کلی از مدل تحلیلی ارائه شده در معادلههای ۴-۷ و ۴-۸ استفاده میشود.
معیار تعداد کل وظایف و جریانهای ترافیکی غیر قابل زمانبندی: در اینجا منظور از قابلیت زمانبدی آن است که هر یک از وظایف و جریانهای ترافیکی در محدودهی زمانی تعیین شدهی خود، اعمالشان را انجام دهند. این اعمال برای وظایف شامل اجرای آنها و برای جریانهای ترافیکی شامل رساندن بستهها به مسیریاب مقصد میباشد. به طور کلی در مسئله نگاشت یکی از مهمترین اهداف یافتن راهحل نگاشتی است که در آن همهی وظایف و جریانهای ترافیکی مربوط به آنها حتی در بدترین موقعیتها مهلت اتمامشان رعایت شود و در واقع قابل زمانبندی باشند. بنابراین این معیار برای هر راهحل تعداد وظایف و جریانهای ترافیکی که از مهلت اتمامشان تجاوز میکنند و در واقع قابل زمانبندی نیستند، را مشخص میکند. واضح است که هر چه این مشخصه برای یک جواب کمتر باشد آن جواب بهتر است. برای ارزیابی و محاسبهی این ملاک برای هر یک از راه حل های ارائه شده توسط الگوریتم ژنتیک از تابع هدف بیان شده در معادلهی ۴-۱۱ استفاده میشود که در این معادله، مدلهای تحلیلی مطرح شده در معادلات ۴-۱ و ۴-۶ به کار برده شده است.
نتایج حاصل از ارزیابی الگوریتم ژنتیک چندهدفه به طور کلی براساس دو معیار فوق میباشد. همچنین دو معیار جدید در ادامه ارائه شده است که این دو معیار موجب تسریع در روند همگرایی الگوریتم میگردند و در واقع باعث میشوند که نتایج سریعتر به حالت بهینهی هر یک از دو معیار قبلی برسند. بنابراین در بخش ارزیابی نتایج، آزمایشات انجام شده با/ بدون در نظر گرفتن این ملاکهای جدید مطرح شده است. این دو معیار جدید ارائه شده عبارتند از:
معیار امکانپذیر بودن جوابها: با توجه به اینکه در روش پیشنهادی هستههای پردازشی ناهمگن هستند، بنابراین وظایف کاربرد مورد نظر بر روی عناصر پردازشی مختلف زمان اجرای متفاوتی دارند و همانگونه که ذکر شد یکی از ویژگیهای مرتبط با هر وظیفه، مشخصهی میباشد که بیانگر بدترین زمان اجرای وظیفهی i بر روی هر یک از هستههای پردازشی است. اما این وظایف ممکن است بر روی برخی از مولفههای پردازشی قابل اجرا نباشند که در این صورت مقدار مربوط به آن هسته در بردار آن وظیفه برابر مقدار بینهایت در نظر گرفته میشود. واضح است که هنگامی که یک وظیفه بر روی یک هستهی پردازشی قابل اجرا نیست به طور متناظر توان اجرایی مربوط به آن نیز برابر بینهایت فرض میشود. بنابراین در این روش تابعی تحت عنوان امکانپذیری یا همان Feasibility تعریف شده است که پس از تولید هر راهحل در مرحلهی ایجاد جمعیت اولیه و توسط هر یک از عملگرهای ژنتیکی تقاطع و جهش، بررسی میکند که در هر یک از راه حل های ایجاد شده جواب غیر قابل قبول وجود نداشته باشد. به عبارتی این تابع در هر جواب جستجو میکند که آیا وظیفهای بر روی هستهی پردازشی که بر روی آن قابل اجرا نیست نگاشت شده است یا خیر. اگر چنین وظیفهای یافت شد، از بین هستههای پردازشی که وظیفهی مذکور بر روی آن قابل اجرا است، یک هسته به طور تصادفی انتخاب میشود و وظیفهی مورد نظر بر روی این هستهی جدید نگاشت میشود.
معیار میزان بهرهوری هستههای پردازشی: در اینجا فرض شده است که هر هسته پردازشی قابلیت اجرای چندین وظیفه را دارد. در واقع هر هسته برای انجام زمانبندی وظایف، دارای صفهای اولویتدار میباشد و از داوری انحصاری اولویتی استفاده می کند. به عبارتی وظیفه با اولویت بالاتر برای اجرا شدن توسط هسته مربوطه نسبت به وظایف اولویت پایینتر حق تقدم دارد. در حقیقت هستههای پردازشی، یک ظرفیت پردازشی دارند و هر وظیفهی i دارای میزان بهرهوری بر روی هر هستهی پردازشی j میباشد[۷۹]. در واقع میزان بهرهوری یک وظیفه بر روی یک هسته بیانگر بخشی از ظرفیت پردازشی مورد نیاز آن وظیفه بر روی هستهی نگاشت شده میباشد [۸۰]. هدف از به کار بردن آزمون میزان بهرهوری هستههای پردازشی، بررسی این موضوع میباشد که همهی وظایف نگاشت شده بر روی یک هستهی خاص از ظرفیت آن هسته تجاوز نکنند[۸۱]. بنابراین برای هر هستهی پردازشی، میزان بهرهوری برابر است با مجموع میزان بهرهوری وظایفی که بر روی این هسته نگاشت شدهاند که این مقدار نباید از یک تجاوز کند. به عبارتی برای هر هستهی j باید شرط زیر برقرار باشد [۷۹].
۵‑۱
معرفی محک[۱۸۱] مورد استفاده
برای ارزیابی روش تحلیلی پیشنهادی، برنامهی کاربردی انتخاب شده به عنوان محک، یک وسیله نقلیهی خودمختار[۱۸۲] میباشد. این کاربرد مثال خوبی از یک برنامه کاربردی با ارتباطات موازی بر روی یک سیستم نهفته همراه با حجم بالای جریانهای ارتباطی میباشد[۷۵]. در این نوع از کاربردها برای تضمین سرویسهای ارتباطی لازم است از محدودیتهای زمانی استفاده شود.
مدل کاربرد وسیله نقلیهی خودمختار که در اینجا در نظر گرفته شده است شامل یک سیستم هدایت[۱۸۳] و یک سیستم کنترل وسیله نقلیه[۱۸۴] میباشد.سیستم هدایت برای تشخیص یک فضای نامعلوم طراحی شده است. در واقع این سیستم پایگاه دادهی مربوط به موانع را با بهره گرفتن از اطلاعات به دست آمده توسط حسگرهای فراصوتی[۱۸۵] و عکسبرداری[۱۸۶] تکمیل میکند. این سیستم همچنین با توجه به شکل ۵-۱ دارای سیستم کنترل جهت[۱۸۷] و پایداری[۱۸۸] میباشد.شکل ۵-۱ ساختار اصلی این کاربرد را نشان میدهد[۱۳].
با توجه به شکل دو دوربین در جمع آوری اطلاعات موانع نقش کلیدی دارند. هر یک ازآها با سرعت ۲۵ فریم بر ثانیه به سیستم بازخورد میدهد و هر فریم دارای وضوح ۴۸۰×۶۴۰ و نمایش ۸ بیت رنگ میباشد. هر فریم دارای اطلاعات لازم برای تخمین پس زمینه و استخراج ویژگی میباشد. با بهره گرفتن از اطلاعات دو دوربین فاصلهی وسیلهی نقلیه تا مانع تخمین زده میشود و موقعیت دقیق مانع به دست آمده و به پایگاه داده اضافه میشود و وسیلهی نقلیه از این پایگاه داده در فرایند هدایت استفاده میکند. در واقع سیستم هدایت با تحلیل موقعیت فعلی وسیله، جهت فعلی و جستجو در پایگاه داده، سرعت و جهت وسیله نقلیه را کنترل میکند.سیستم کنترل پایداری وسیله نقلیه اطلاعات حاصل از فشار تایرها و معیارهای لرزش را از حسگرها جمع آوری میکند و سرعت را تنظیم و وضعیت حرکتی را کنترل میکند [۸]. این برنامه کاربردی به خاطر قدرت پردازشی مورد نیاز توسط زیرسیستمهای آن و همچنین به دلیل محدودیتهای مربوط به توان مصرفی بهتر است که از شبکه روی تراشه استفاده کند.
شکل ۵‑۱- مدل کاربرد وسیله نقلیهی خودمختار [۱۳]
جدول ۵-۱ وظایف تشکیلدهندهی این برنامه کاربردی را به همراه عملکرد هر یک از آنها نشان میدهد. با توجه به این جدول کاربرد مورد نظر دارای ۳۳ وظیفه میباشد.
جدول ۵-۲ نشاندهندهی جریانهای ترافیکی حاصل از ارتباطات بین این وظایف است. با توجه به این جدول برنامهی کاربردی مورد نظر دارای ۳۸ جریان ارتباطی بین وظایف میباشد. همانطورکه در فصل قبل گفته شد، هر جریان ارتباطی دارای شش مشخصه است که این جدول نشاندهنده این شش ویژگی برای هر یک از آنها میباشد. ستون Source و Destination در جدول بیانگر شماره مربوط به وظیفهی مبدا و وظیفهی مقصد ارتباط مورد نظر میباشد. پارامتر vol مقدار دادهای که در یک ارتباط منتقل می شود را نشان میدهد که این مشخصه براساس تعداد فلیتها میباشد که هر فلیت دارای ۳۲ بیت است. ستون مربوط به Period همانگونه که از نام آن مشخص است بیانگر دوره هر ارتباط میباشد و درواقع فاصلهی زمانی بین آزاد شدن بستههای متوالی ارتباط مورد نظر را نشان میدهد. پارامترهای Deadline و Priority نیز به ترتیب بیانگر مهلت اتمام و اولویت جریان ارتباطی هستند.
جدول ۵‑۱- وظایف تشکیل دهنده کاربرد [۷۵]
Description | Tasks | No |
Tyre pressure monitoring system | TPMS | ۱ |
Vibration sensor | VIBS | ۲ |
Speed sensor | SPES | ۳ |
[یکشنبه 1400-08-09] [ 09:02:00 ق.ظ ]
|