وبلاگ

اگر  ،  نرخ اشتغال یا بکارگیری سرور نامیده می‌شود، چون کسری از زمان است که سرور، مشغول کارکردن است.
۲-۳-۲- قانون لیتِل^[۶۹] [۱۳]
اگر E(L)، میانگین تعداد مشتریان در سیستم، E(S)، میانگین زمان اقامت مشتری در سیستم باشد و  ، متوسط تعداد مشتریانی باشد که در واحد زمان وارد سیستم می‌شوند، قانون لیتِل، رابطه بسیار مهمی را بین این سه نماد می‌دهد و به صورت زیر بیان می‌شود:
(۱۹.۲) 
در اینجا فرض می‌شود که ظرفیت سیستم برای رسیدگی به مشتریان کافی است (یعنی، تعداد مشتریان در سیستم به سمت بینهایت میل نمی‌کند).

به طور حسی، این نتیجه می‌تواند به صورت زیر فهمیده شود: فرض کنید که مشتریان هنگامی‌که به سیستم وارد می‌شوند، یک دلار در واحد زمان می‌پردازند. این پول می‌تواند به دو روش گرفته شود. روش اول اینکه به مشتریان اجازه دهیم که به طور پیوسته در واحد زمان بپردازند. پس متوسط درآمدی که توسط سیستم کسب می‌شود، برابر E(L) دلار در واحد زمان است. روش دوم این است که به مشتریان اجازه دهیم که برای اقامتشان در سیستم، ۱ دلار را در واحد زمان در موقع ترک سیستم بپردازند. در موازنه، متوسط تعداد مشتریانی که در واحد زمان، سیستم را ترک می‌کنند برابر متوسط تعداد مشتریانی است که به سیستم وارد می‌شوند. بنابراین سیستم، یک متوسط درآمد  دلار را در واحد زمان کسب می‌کند.
با به کار بردن قانون لیتِل در صف، رابطه‌ای بین طول صف،  و زمان انتظار W به دست می‌آید:
(۲۰.۲)
۲-۳-۳- صف M/M/1
این مدل، حالتی را درنظر می‌گیرد که زمان بین رسیدن‌ها، نمایی با میانگین  ، زمان‌های سرویس، نمایی با میانگین  و یک سرور مشغول کار است. مشتریان به ترتیب رسیدن، سرویس دهی می‌شوند. ما نیاز داریم که:
(۲۱.۲) 
درغیراینصورت، طول صف منفجر خواهد شد (قسمت قبل را ببینید). مقدار  ، کسری از زمان است که سرور، مشغول کار است.
میانگین تعداد مشتریان در سیستم و همچنین میانگین زمانی که در سیستم گذرانده می‌شوند به صورت زیر بیان می‌شود:
(۲۲.۲)
و با بهره گرفتن از قانون لیتِل،
(۲۳.۲)
میانگین تعداد مشتریان در صف،  ، می‌تواند از E(L) و با کم کردن میانگین تعداد مشتریان در سیستم بدست آید:
(۲۴.۲)
میانگین زمان انتظار، E(W)، از E(S) و با کم کردن میانگین زمان سرویس بدست می‌آید:
(۲۵.۲)
۲-۴- مسائل بهینه سازی چندهدفه
بسیاری از مسائل کاربردی در جهان واقعی را مسائل بهینه سازی ترکیباتی چندهدفه تشکیل می‌دهند، زیرا متغیر‌های مجزا و اهداف متضاد به طور واقعی در ذات آنها است. بهینه سازی مسائل چندهدفه نسبت به مسائل تک هدفه متفاوت بوده، زیرا شامل چندین هدف است که باید در بهینه‌سازی به همه اهداف همزمان توجه شود. به عبارت دیگر الگوریتم‌های بهینه سازی تک هدفه، حل بهینه را با توجه به یک هدف می یابند و این در حالی است که در مسائل چندهدفه (با چندهدف مخالف و متضاد) معمولاً یک حل بهینه مجزا را نمی توان بدست آورد. بنابراین طبیعی است که مجموعه ای از حل‌ها برای این دسته از مسائل موجود بوده و تصمیم گیرنده نیاز داشته باشد که حلّی مناسب را از بین این مجموعه حل‌های متناهی انتخاب کند و در نتیجه حل مناسب، جواب‌هایی خواهد بود که عملکرد قابل قبولی را نسبت به همه اهداف داشته باشد.
۲-۴-۱- فرمول بندی مسائل بهینه سازی چندهدفه
مسائل بهینه سازی چندهدفه را به طور کلی می‌توان به صورت زیر فرموله کرد:
(۲۶.۲)

x یک حل است و S مجموعه حل‌های قابل قبول و k تعداد اهداف در مسأله و F(x) هم تصویر حل x در فضای k هدفی و  هم مقدار هر یک از اهداف است.
تعریف حل‌های غیرمغلوب: حل a حل b را پوشش می‌دهد، اگر و تنها اگر:
(۲۷.۲)
(۲۸.۲)
به عبارت دیگر، حل‌های غیرمغلوب، به حل‌های گفته می‌شود که حل‌های دیگر را پوشش داده ولی خود، توسط حل‌های دیگر پوشش داده نمی‌شوند. در شکل (۲-۲) چگونگی پوشش سایر حل‌ها (دایره‌های با رنگ روشن) توسط مجموعه حل‌های غیرمغلوب (دایره‌های تیره رنگ) نشان داده شده‌است. در این شکل، جبهه‌ی پارتو^[۷۰] با خط چین نشان داده شده‌است.
هدف B
هدف A
شکل ۲-۲- مجموعه حل‌های غیرمغلوب
۲-۴-۲- الگوریتم‌های تکاملی برای بهینه سازی مسائل چندهدفه بر مبنای الگوریتم ژنتیک
با توجه به آنکه بسیاری از مسائل بهینه سازی، NP-Hard هستند، بنابراین حل به روش‌های دقیق در یک زمان معقول غیرممکن بوده و در نتیجه، استفاده از روش‌های فراابتکاری در این موارد مناسب می باشد. درحقیقت الگوریتم‌های فراابتکاری برای زمانی که محدودیت زمانی وجود دارد و استفاده از روش‌های حل دقیق میسّر نبوده و یا پیچیدگی مسائل بهینه سازی زیاد باشد، به دنبال جواب‌های قابل قبول هستند.
اولین پیاده سازی واقعی از الگوریتم‌های تکاملی، «الگوریتم ژنتیک ارزیابی برداری»^[۷۱] توسط دیوید اسکافر^[۷۲] در سال ۱۹۸۴ انجام گرفت. اسکافر الگوریتم را به سه بخش انتخاب، ترکیب و جهش که به طور جداگانه در هر تکرار انجام می‌شدند، تغییر داد. این الگوریتم به صورت کارآمدی اجرا می‌شود، اما در برخی از حالات مانند اریب بودن اهداف، با مشکل مواجه می‌شود. درواقع هدف اول الگوریتم‌های بهینه یابی چندهدفه، یعنی رسیدن به جواب‌های بهینه پارتو، به نحو شایسته‌ای توسط این الگوریتم بدست می‌آید، ولی جواب‌های بدست آمده از گستردگی و تنوع خوبی برخوردار نیستند.
در ادامه این قسمت، به سه الگوریتم تکاملی چند هدفه که مبنای اصلی آنها، الگوریتم ژنتیک می‌باشد، می‌پردازیم. الگوریتم NSGA-II به این خاطر انتخاب شده‌است که این الگوریتم در بسیاری از مقالات به عنوان الگوریتم مرجع مقایسه گردیده‌است. الگوریتم CNSGA-II نیز به این علت انتخاب شده‌است که روشی مناسب برای برخورد با محدودیت‌های حل مسأله ارائه می‌کند؛ چون باتوجه به ماهیت مسأله، چندین محدودیت سر راه حل مسأله ایجاد شده‌است که راهکار مناسبی برای رسیدگی به این محدودیت‌ها ایجاب می‌کند. الگوریتم NRGA نیز چون جزء جدیدترین الگوریتم‌های ارائه شده در زمینه بهینه سازی چندهدفه می‌باشد مورداستفاده قرار گرفته‌است.
۲-۴-۲-۱- الگوریتم ژنتیک مرتب سازی نامغلوب
دب^[۷۳] و همکارانش [۱۴]، یک نخبه گرایی دسته بندی یا مرتب سازی نامغلوب را در الگوریتم‌های ژنتیک پیشنهاد دادند. در اغلب مواقع، این الگوریتم شباهتی به NSGA ندارد، ولی مبتکران نام NSGA-II را به دلیل نقطه پیدایش آن، یعنی همان NSGA، برای آن حفظ کردند.
در این روش، ابتدا جمعیت فرزندان،  ، با بهره گرفتن از جمعیت والدین،  ، ساخته می‌شود. در اینجا به جای پیدا کردن جواب‌های نامغلوب از  ، ابتدا دو جمعیت با یکدیگر ترکیب شده و جمعیت  با اندازه ۲N را ایجاد می‌کنند. سپس از یک مرتب سازی نامغلوب برای دسته بندی تمام جمعیت  استفاده می‌شود، البته این مرتب سازی، نسبت به مرتب سازی بر روی  ، به تعداد مقایسه بیشتری نیاز دارد. در این شیوه، یک مقایسه عمومی در بین اعضای  که مجموع دو جمعیت فرزندان و والدین است، انجام می‌شود و پس از ایجاد صف‌های متفاوت نامغلوب، به ترتیب اولویت (اولویت صفها نسبت به هم) جمعیت بعدی، یکی یکی از این صف‌ها پر می‌شود. پر کردن جمعیت  ، با بهترین صف نامغلوب شروع شده و سپس به ترتیب با دومین صف نامغلوب و همین طور سومین و الی آخر، تا زمانی که  پر شود، ادامه می‌یابد. از آنجا که اندازه  برابر ۲N است، تمام اعضای آن ممکن است نتوانند در  قرارگیرند و به راحتی جواب‌های باقیمانده را حذف خواهیم کرد. شکل (۲-۳) نحوه عمل الگوریتم NSGA II را نمایش می‌دهد.

شکل ۲-۳- نمایشی از نحوه عملکرد NSGA-II
درمورد جواب‌هایی که در صف آخر با بهره گرفتن از عملگر نخبه گرایی ازبین می‌روند، باید مهارت بیشتری به کار برده و جواب‌هایی که در ناحیه ازدحام کمتری قراردارند را حفظ کرد. درواقع برای رعایت اصل چگالی در بین جواب‌ها، جواب‌هایی که در ناحیه ازدحامی کوچکتری هستند، برای پر کردن  ، در اولویت قرار دارند.
یک استراتژی شبیه بالا در پیشرفت مراحل اولیه از تکامل الگوریتم، تأثیر زیادی نخواهد داشت، چرا که اولویت‌های زیادی در جمعیت ترکیب شده از فرزندان و والدین وجود دارد. احتمالاً جواب‌های نامغلوب زیادی وجود دارند که آماده قرارگرفتن در جمعیت  قبل از آن که اندازه‌اش از N تجاوز کند، می‌باشند. یک مسأله مهم و در عین حال سخت این است که مابقی جمعیت  چگونه باید پر شود؟ اگرچه درخلال مراحل بعدی شبیه سازی الگوریتم، احتمالاً بیشتر جواب‌های موجود در جمعیت  با اندازه ۲N، در رده جواب‌هایی با بهترین درجه نامغلوب بودن قرار می‌گیرند و تعداد آن‌ ها از N متجاوز خواهد شد، اما الگوریتم بالا با یک راهکار موقعیتی انتخاب، وجود مجموعه متنوعی از جواب‌ها در جمعیت را تضمین می‌کند. با چنین راهکاری، یعنی زمانی که به‌نحوی تمام ناحیه بهینه پارتو توسط جمعیت پوشانده می‌شود، در ادامه الگوریتم، جواب‌های گسترده تری را در فضای جواب فراهم خواهدآورد.
در ادامه، الگوریتم NSGA-II را به اختصار آورده ایم [۱۵]:
گام ۱: جمعیت فرزندان و والدین را با یکدیگر ترکیب کرده و  را می‌سازیم: