۹
………
۱۵
۲
۳
T₁ T₂ T₃ ……….. T_n-2 T_n-1 T_n
شکل ‏۴‑۸- ساختار کروموزوم [۵۰]
توابع هدف : همان گونه که ذکر شد، در مسائل بهینه­سازی چندهدفه، ممکن است اهداف در تضاد با یکدیگر باشند و بهینه کردن یک هدف منجر به ایجاد جواب­های غیرقابل قبول یا نامناسب در سایر اهداف گردد. بنابراین در این­جا هدف از به کاربردن الگوریتم بهینه­سازی چندهدفه، ایجاد یک بده بستان^[۱۷۲] مناسب بین اهداف طراحی است. به عبارتی هدف، یافتن نگاشتی از وظایف بر روی هسته­های پردازشی شبکه بر تراشه است که علاوه بر رعایت محدودیت­های زمانی وظایف و جریان­های ترافیکی، اتلاف توان نیز کمینه گردد. تابع هدف اول با توجه به معادله ۴-۱۱ کمینه کردن تعداد وظایف و جریان­های ترافیکی است که قابل زمان­بندی نیستند و در واقع مقدار این تابع برابر با تعداد وظایف و جریان­های ترافیکی است که مهلت اتمام­شان رعایت نشده است.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۴‑۱۱
در رابطه فوق، بدترین زمان پاسخ برای هر وظیفه طبق معادله ۴-۱ و بدترین تاخیر شبکه برای هر جریان ترافیکی با بهره گرفتن از معادله ۴-۶ محاسبه می­ شود. بنابراین یک کاربرد بی­درنگ قابل زمان­بندی است اگر به ازای هر وظیفه i در این کاربرد، و برای هر جریان ترافیکی i، باشد [۵۰].
تابع هدف دوم که در این­جا در نظر گرفته شده است، کمینه­کردن اتلاف توان کلی ناشی از انتقال بسته­ها در سطح شبکه و اجرای وظایف بر روی هسته­های پردازشی، می­باشد. در رابطه‌ی این تابع هدف که در معادله ۴-۱۲ نشان داده شده است، از اتلاف توان کلی ذکر شده در معادله ۴-۸ استفاده شده است.
۴‑۱۲
به دلیل آن­که الگوریتم NSGA-II، یک الگوریتم بهینه سازی چند هدفه می­باشد، بنابراین در این روش، تابع برازندگی به کاربرده شده برای ارزیابی هر یک از راه­حل­ها، مقادیر دو تابع هدف ذکر شده برای هر راه­حل را برمی­گرداند. در نهایت یک مجموعه‌ای از جواب­های نامغلوب به دست می ­آید که هیچ از یک جواب­ها بر دیگری غلبه نمی­کند و ارزش هر جواب به ازای هر یک از توابع هدف متفاوت است. در این جا با توجه به نیاز طراحی هر یک از راه­حل­ها می ­تواند راه­حل مناسب باشد.
یکی از اجزای الگوریتم ژنتیک عملگرهای ژنتیکی می­باشند که این عملگرها بر روی تعدادی از اعضای جمعیت که به عنوان والد^[۱۷۳] شناخته می­شوند اعمال می­شوند تا عضو جدیدی را با عنوان زاده^[۱۷۴] تولید کنند. به این ترتیب هرچه عملگرهای ژنتیکی کارایی بیشتری داشته باشند روند الگوریتم در رسیدن به جواب‌های نهایی سریع­تر می­ شود. با توجه به شکل ۴-۹ که روند کلی الگوریتم ژنتیک را در این روش نشان می­دهد، سه عملگر ژنتیکی شامل عملگر انتخاب، عملگر تقاطع و عملگر جهش بر روی جمعیت والد اعمال می­شوند که در ادامه ساختار هر یک توضیح داده خواهد شد.
Parent population
Selection
Crossover
Mutation
Elitism
Offspring population
Combined population
Application Model
Platform Architecture
Mapping Solutions
شکل ‏۴‑۹- ساختار کلی الگوریتم ژنتیک [۵۰]
عملگر انتخاب^[۱۷۵] : برای انتخاب کروموزوم­های والد به منظور ایجاد نسل فرزندان ازعملگر انتخاب استفاده می­ شود. پیش از اعمال عملگر­های ژنتیکی لازم است تا صف جفت­گیری^[۱۷۶] که مجموعه ­ای از والدین منتخب در آن قرار دارند ایجاد شود. این­که کدام یک از اعضای جمعیت فعلی به عنوان والد انتخاب شوند تأثیر بسزایی در کیفیت جواب­های خروجی خواهد داشت. در الگوریتم ارائه‌شده برای انتخاب والدین و قرار دادن آن‌ها در صف جفت­گیری از روش انتخابِ مسابقه­ای دودویی^[۱۷۷] استفاده شده است. در این روش که معمولا از آن استفاده می شود، ابتدا دو عضو به صورت تصادفی از جمعیت انتخاب می­ شود و سپس عضوی که دارای رتبه بالاتری است در صف جفت‌گیری قرار می­گیرد (شکل ۴-۱۰). روند انتخاب آن قدر ادامه پیدا می­ کند تا صف جفت‌گیری پر شود. در روش پیشنهادی از بین دو عضو والد انتخاب شده، والدی که دارای سطح نامغلوب کمتری است انتخاب می­ شود و در صورت مساوی بودن سطوح نامغلوب دو والد، آن والدی که فاصله ازدحام بیشتری دارد برنده این مسابقه می­ شود. به‌طورکلی این روش را می­توان با جای­گذاری و یا بدون جایگذاری بین اعضا انجام داد. اندازه­ مسابقه نیز قابل‌تغییر است مثلاً بجای مسابقه­ی دودویی، می­توان مسابقه­ی سه­تایی را انجام داد. نکته قابل‌ذکر آن است که در این روش بدترین کروموزم هیچ‌گاه در صف جفت‌گیری قرار نمی­گیرد.
{f₁, c₁}
{f₂, c₂}
{f₂, c₂}
شکل‏۴‑۱۰- انتخاب مسابقه­ای دودویی [۵۰]
عملگر تقاطع^[۱۷۸] : بدیهی است که در طبیعت بقای نسل لازم است و تنها عملگر ممکن برای این امر آمیزش است. در الگوریتم‌های ژنتیکی نیز آمیزش وجود دارد. آمیزش با تعویض ژن‌ها، بین دو کروموزم انجام می­گردد و هر کدام از کروموزم‌ها خصوصیاتی از خود را به فرزندان انتقال می‌دهند. بدیهی است کروموزم‌هایی که دارای برازندگی بیشتری هستند شانس بیشتری برای آمیزش دارند. مهم‌ترین عملگر در الگوریتم ژنتیک، عملگر تقاطع است. تقاطع فرآیندی است که در آن نسل قدیمی کروموزم‌ها با یکدیگر مخلوط و ترکیب می‌شوند تا نسل تازه‌ای از کروموزم‌ها به وجود بیاید. روش­های مختلفی برای انجام عمل تقاطع، از جمله تقاطع تک نقطه­ای و تقاطع دو نقطه­ای و … وجود دارد. در این روش از تقاطع تک نقطه­ای استفاده می­ شود. به این صورت که پس از انتخاب والدین برگزیده و قرار دادن آن­ها در صف جفت­گیری، با توجه به نرخ تقاطع از این صف دو به دو والدین را برداشته و با توجه به شکل ۴-۱۱ از نقطه­ای که به طور تصادفی انتخاب شده، دو بخش مختلف این دو والد ترکیب می­شوند و دو فرزند جدید ایجاد می­ شود. در روش تقاطع دو نقطه­ای، دو نقطه به طور تصادفی از دو والد انتخاب و قسمت میانی این دو والد با هم جابجا شده و دو فرزند جدید ایجاد می­ کنند.
Parents :
Crossover points
۱
۲
۹
۳
۲
۲
۶
۶
۷
۸
۱
۶
۶
۷
۸
۲
۲
۹
۳
۲