با توجه به معادله فوق در این مدل فرض می­ شود که هر بسته دارای فلیت، شامل یک فلیت سرآیند و فلیت داده می­باشد. تعداد گام­های مسیر از مسیریاب مبدأ تا مسیریاب مقصد می­باشد. اتلاف توان در واسط شبکه برای انتقال یک فلیت، توان تلف شده در مسیریاب برای انتقال یک فلیت و توان مصرفی ناشی از انتقال یک فلیت در پیوند می­باشد.

بنابر مطالب فوق اتلاف توان کلی مطابق با معادله ۴-۸ می­باشد:
‏۴‑۸
الگوریتم ژنتیک چند هدفه NSGA-II
در بسیاری از مسائل در دنیای واقعی، اهداف طراحی در تضاد با یکدیگرمی­باشند و بهینه‌سازی در یکی از اهداف ممکن است منجر به ایجاد جواب­های غیرقابل­قبول در سایر اهداف گردد. در نتیجه بهینه کردن تمامی اهداف به طور همزمان تقریباً غیرممکن است. بنابراین یک راه حل معقول برای مسایل چندهدفه، یافتن مجموعه ­ای از جواب­ها می­باشد که هر کدام از آن­ها یکی از اهداف را در سطح قابل­قبولی بهینه می­ کند بدون آنکه سایر اهداف را به طور کامل نقض نماید و یا تحت شعاع سایر جواب­ها قرار گیرد. در این راستا مفاهیم جدیدی مطرح می­ شود که در ادامه تعریف‌شده‌اند:
غلبه^[۱۵۶]: جواب قابل‌قبول x بر جواب قابل‌قبول y غلبه می­ کند اگر و فقط اگر در تمامی توابع هدف، x بدتر از y نباشد و حداقل در یکی از اهداف بهتر از y باشد .
بهینه^[۱۵۷]: به جوابی بهینه گفته می­ شود که هیچ­یک از جواب­ها در فضای پاسخ بر آن غلبه نکند. یک جواب بهینه در هیچ­یک از توابع هدف قابل بهبود نخواهد بود مگر اینکه حداقل در یکی از اهداف دیگر بدتر شود.
نامغلوب^[۱۵۸]: به جوابی نامغلوب گفته می­ شود که هیچ یک از جواب ها بر آن غلبه نکند.
مجموعه بهینه^[۱۵۹]: مجموعه­ تمام جواب­های نامغلوب قابل­قبول در فضای پاسخ به عنوان مجموعه بهینه شناخته می­ شود. هدف از مسایل بهینه­سازی چندهدفه یافتن مجموعه بهینه می­باشد.
جبهه بهینه^[۱۶۰]: اگر تعدادی جواب به عنوان مجموعه بهینه وجود داشته باشد، ارزش این جواب­ها با توجه به هر یک از اهداف در فضای هدف به عنوان جبهه بهینه شناخته می­ شود[۷۷].
حال با توجه به مفاهیم فوق معرفی مختصری از الگوریتم ژنتیک چند هدفه نامغلوب ارائه می­گردد.
سرینیواس و کالیانموی با اعمال تغییراتی در فرایند رتبه ­بندی توسط کلدبرگ [۷۷] روشی به نام “Non-dominated Sorting Genetic Algorithm” (NSGA) را ابداع کرده ­اند. الگوریتم NSGA مبتنی بر دسته­بندی چند لایه‌ی اعضا^[۱۶۱] می­باشد. قبل از انجام عملیات انتخاب، جمعیت بر اساس مقدار نامغلوب بودن^[۱۶۲] رتبه ­بندی می­ شود: تمام اعضای نامغلوب باهم در یک دسته قرار می­گیرند (البته به هر یک از اعضای این گروه مقدار شایستگی ثانویه^[۱۶۳] که متناسب با اندازه­ جمعیت می­باشد اختصاص خواهد یافت، تا در نتیجه برای این اعضا شانس انتخاب یکسانی ایجاد شود). برای حفظ تنوع^[۱۶۴] در جمعیت این اعضای دسته­بندی شده با مقدار شایستگی ثانویه­ای که به آن‌ها اختصاص یافته است به اشتراک گذاشته می­شوند. سپس صرف نظر از اعضای این گروه، لایه بعدی از جواب­های نامغلوب به دست می ­آید. این فرایند تا زمانی که تمام اعضای جمعیت دسته­بندی شوند ادامه پیدا می­ کند. با کمک مکانیزمی اعضای جمعیت انتخاب می­شوند به طوری که اعضای اولین جبهه^[۱۶۵] بیش‌ترین مقدار شایستگی و در نتیجه بیش‌ترین شانس انتخاب را خواهند داشت. البته در این روش مکانیزم استفاده‌شده برای اشتراک شایستگی^[۱۶۶] موجب ایجاد گلوگاه محاسباتی خواهد شد. با این وجود این روش نسبتاً موفق بوده و در سال‌های مختلف مورد استفاده قرار گرفته است چرا که سریعاً به سمت جواب‌های بهینه همگرا می­شد. اما NSGA به دلیل روشی که برای دسته­بندی اعضا استفاده می­نمود بازدهی بسیار کمی داشت.
دِب و همکاران [۷۸] نسخه بهبودیافته‌ای از NSGA به نام NSGA-II را ارائه دادند. همان طور که در شکل ۴-۴ مشاهده می­ شود، الگوریتم NSGA-II جمعیتی از اعضا را بر اساس سطح نامغلوب^[۱۶۷]­ ایجاد کرده و پس از آن رتبه ­بندی و مرتب‌سازی می­ کند. به عبارتی در مرحله مرتب سازی نامغلوب، اعضای جمعیت در داخل دسته­هایی قرار می­گیرند به گونه ­ای که اعضای موجود در دسته اول، یک مجموعه کاملاً نامغلوب توسط دیگر اعضاء جمعیت فعلی می باشند. اعضای موجود در دسته دوم نیز بر همین مبنا تنها توسط اعضای دسته اول مغلوب شده و این روند به همین صورت در دسته های دیگر ادامه یافته تا به تمام اعضای موجود در هر دسته، یک رتبه بر مبنای شماره دسته اختصاص داده شود (شکل ۴-۵). سپس به منظور ایجاد منبع^[۱۶۸] جدیدی از فرزندان عملگرهای تکاملی را اعمال می­ کند و سپس والدین و فرزندان را قبل از تقسیم‌بندی مخزن جدید با هم ترکیب می­ کند. سپس به هر یک از اعضا مقدار فاصله ازدحام^[۱۶۹] را اختصاص می­دهد. این معیار برای هر عضو در هر گروه محاسبه می­ شود و بیانگر میزان نزدیکی نمونه مورد نظر به دیگر اعضای جمعیت آن گروه می­باشد. مقدار بزرگ این معیار منجر به واگرایی و گستره بهتری در مجموعه اعضای جمعیت خواهد شد. به عبارتی از مقدار فاصله ازدحام در عملگر انتخاب برای حفظ پراکندگی جواب‌ها در هر جبهه استفاده می­ کند. این عمل موجب حفظ تنوع جواب­ها شده و به الگوریتم کمک می­ کند تا فضاهای جدید را جستجو کند.
شکل ‏۴‑۴- نحوه عملکرد الگوریتم NSGA-II. در این نمودار P­­t جمعیت والدین، Qt جمعیت فرزندان در تکرار t می­باشد. F₁ بهترین جواب بعد از ادغام جمعیت­ها (والدین و فرزندان) می­باشد و F₂ دومین بهترین و الی آخر[۷۸]
در [۷۸] فاصله ازدحام هر راه­حل با توجه به شکل ۴-۶ به ازای هر تابع هدف برابر است با:
‏۴‑۹
‏۴‑۱۰
در واقع با توجه به شکل تفاضل مقدار تابع هدف راه­حل بعدی و مقدار تابع هدف راه­حل قبلی محاسبه و بر دوکرانه­های آن جبهه تقسیم می­ شود. این مقدار به ازای هر تابع هدف به دست می ­آید و سپس برای محاسبه­ی فاصله ازدحام راه­حل مورد نظر مجموع این مقادیر در نظر گرفته می­ شود.
شکل ‏۴‑۵- سطوح نامغلوب در الگوریتم NSGA-II [50]
شکل ‏۴‑۶- محاسبه­ی فاصله ازدحام[۷۸]
فلوچارت شکل ۴-۷ مراحل الگوریتم NSGA-II را نشان می­دهد.
Initialize population
i=0
Stopping criteria?
i=i+1
Fitness evaluation
Non-dominated sort
Crowding distance
دو بخش اضافه شده نسبت به
الگوریتم ساده ژنتیک
Mutation
Crossover
Reproduction
شکل ‏۴‑۷- مراحل الگوریتم ژنتیک NSGA-II
در این پایان نامه، برای اعمال روش پیشنهادی از الگوریتم NSGA-II استفاده شده است که جزئیات الگوریتم در این روش و عملگرهای استفاده شده در ادامه این بخش تشریح خواهد شد. با توجه به مکانیزم مطرح‌شده، ورودی الگوریتم اندازه جمعیت، بیشترین تکرار نسل­ها، نرخ جهش و نرخ تقاطع است و خروجی شامل مجموعه راه­ حل­های نامغلوب می­باشد.مراحل اصلی الگوریتم به صورت زیر خواهد بود:
تولید جمعیت اولیه به صورت کاملا تصادفی
انجام عملیات چندهدفه
شروع حلقه اصلی
تولید فرزندان به روش تقاطع
تولید فرزندان به روش جهش
تجمیع نسل قبل و نسل جدید
انجام عملیات چند هدفه
انتخاب بهترین­ها
انجام عملیات چند هدفه
برگشتن به ابتدای حلقه تا برقراری شرط توقف
در این الگوریتم عملیات چندهدفه شامل مراحل زیر می­باشد:
مرتب­سازی نامغلوب (جبهه­بندی)
محاسبه فاصله ازدحام
مرتب کردن جواب­ها
از آن­جا که برخی از وظایف بر روی تعدادی از هسته­های پردازشی قابل اجرا نیستند درنتیجه پس از ایجاد جمعیت اولیه و پس از تولید جمعیت فرزندان توسط عملگرهای ژنتیکی تقاطع و جهش، امکان­پذیری^[۱۷۰] هر یک از جواب­ها بررسی می­ شود. هم­چنین به دلیل آن­که یک هسته پردازشی قابلیت اجرای بیش از یک وظیفه را دارد، بنابراین برای داشتن جواب­های قابل قبول در طول اجرای الگوریتم پس از تولید هر جواب میزان بهره­وری^[۱۷۱] هسته­های پردازشی ارزیابی می­ شود. این دو معیار در فصل ارزیابی نتایج به طور کامل­تر توضیح داده خواهد شد.
نحوه نمایش اعضا : در این­جا جمعیت اولیه و در واقع هر یک از راه­حل­ها به صورت کاملا تصادفی ایجاد می­ شود. برای حل مسئله به کمک الگوریتم ژنتیک باید آن را در قالب و ساختار مناسب با این الگوریتم ارائه نمود. در الگوریتم ژنتیک به هر یک از اعضای جمعیت که معرف یک راه­حل مسئله می­باشد، کروموزوم گفته می­ شود. در ساختار پیشنهادی، هر کروموزم بیانگر یک نگاشت وظایف کاربرد مورد نظر بر روی هسته­های پردازشی شبکه بر تراشه می­باشد. کروموزوم با توجه به شکل ۴-۸، یک برداری است که اندازه آن برابر با تعداد وظایف کاربرد می­باشد. اندیس هر ژن معرف شناسه وظیفه است و مقدار هر ژن شامل شماره هسته پردازشی است که وظیفه مورد نظر بر روی آن نگاشت شده است. به طور مثال با توجه به شکل، وظیفه شماره ۱ بر روی هسته پردازشی ۱، وظیفه شماره ۲ بر روی هسته پردازشی ۲، وظیفه شماره ۳ بر روی هسته پردازشی ۹ و …نگاشت شده ­اند.
۱
۲