تکنیک بهینه سازی آزاد مشتق برای کالیبراسیون مدل های صف بندی A DFO technique to calibrate queueing models

مقدمه

پیش بینی عملکرد سیستم های اطلاعاتی به عنوان یک مسئله اصلی در تجزیه و تحلیل کامپیوتری می باشد. این پیش بینی ها در ارتباط با طراحی سیستم جدید و همچنین پیش بینی تاثیر عملکردی تغییرات در منابع سخت افزاری و یا تراکم کار مورد استفاده قرار می گیرد. برای نمونه پیش بینی ها می توانند تخمین بزنند که چگونه افزایش کاربرد شبکه های اترنتی بر روی متوسط تاخیرهای ایجاد شده توسط بسته های انتقالی تاثیرگذار می باشند. مورد دیگر پیش بینی تاثیر عملکرد ابزارهای ذخیره سازی جدید بر روی عملکرد سیستم های فرعی می باشد.

یک روش عملی برای مد نظر قرار دادن تاثیر سیستم یت تغییرات حجم کار اجرای سناریو مشابه در سیستم های واقعی و ارزیابی تاثیر نتایج به صورت آزمایشی می باشد. چنین راه حلی نیازمند این می باشد که سیستم به طور مناسبی مجهز گردد که پیچیده و هزینه بردار می باشد. علاوه بر این در بعضی از نمونه ها تجهیز و ارزیابی به طور قابل توجهی عملکرد سیستم های عملیاتی را تغییر داده و قابلیت اطمینان آن را تطبیق می دهد.به همین دلیل مهندسان خیلی از مواقع در جستجوی راه حل های جایگزین می باشند.

جهت مشاهده متن کامل فایل ترجمه را دانلود نمایید.

مدل های تحلیلی به دنبال روش های غیر تداخلی، تجدید پذیر و کنترلی برای پیش بینی عملکرد یک سیستم می باشند. اگرچه این مدل ها از نظر ظاهر، پیچیدگی، دقت و روش های حل شونده متفاوت باشند، فرایند مدل سازی به دو مرحله تقسیم می گردد. مراحل کیفی و کمی.در ابتدا مدلی طراحی می شود تا ویژگی های ضروری سیستم ها را به سمت خود بکشاند. چنین مدل هایی بر روی اشکال از پیش تعیین شده همانند شبکه های پیوسته، زنجیره مارکو و یا شبکه های پتری تکیه کرده و یا به طور معمول برمبنای معادله ریاضی خاصی می باشند. برای نمونه سرورهای شبکه به عنوان یک سیستم صف بندی نمایش داده می شوند. زمانی که این مراحل کیفی به اجرا در آمد، تعیین ارزش پارامترهای مدل ضروری می شود به گونه ای که مدل و سیستم از نظر کمی با هم منطبق می گردند. تطبیق میزان پارامترهای مدل به نام مراحل کالیبراسیون می باشد. البته هر دو مرحله مرتبط به هم بوده و وجود عیب در هر یک از این مراحل کل مدل را بی اعتبار می کند.

در این مقاله ما تمرکز خود را بر روی مراحل کالیبراسیون مدل های سیستم های موجود قرار می دهیم. یعنی ما بر این فرض می باشیم که مدل های بلقوه ای که از نظریه صف بندی حاصل می شود، قبلا نیز ایجاد شده است. ارزش بعضی از پارامترهای مدل به صورت مستقیم با شناخت سیستم برای نمونه از شرایط فنی یا مشاهدات عملی حاصل می گردد. ما این پارامترهای خاص را توسط   مشخص می کنیم.ارزش پارامترهای دیگر مدل ممکن است برای تحلیل گران ناشناخته بوده و می بایست نسبتا مشخص باشد. ما پارامترهای غیرمشخص را توسط   نشان می دهیم و ما مدلی را مد نظر قرار می دهیم که شامل پارامترهای غیرمشخص به عنوان یک مدل غیرکامل می باشد.

تخمین پارامترهای غیرمشخص  نیازمند شناخت اضافی می باشد که معمولا مربوط به ارزیابی ها می باشد. در این مقاله، ما مشاهده می کنیم که سیستم های مورد بررسی در زمان های مختلف با توجه به سطوح مختلف حجم کار ارزیابی می گردند. ما مجموعه ای از مقادیر N را که توسط  معرفی می گردند مد نظر قرار می دهیم. برای هر یک از آن ها   مرتبط به یک سطح حجم کاری خاص اما غیرمشخص می باشد.   به عنوان بردار پارامتر عملکردی P می باشد. در مهندسی کامپیوتر، پارامترهای عملکرد معمولی به عنوان یک خروجی متوسط، احتمالات، زمان اسکان موقتی مورد نظر و طول پیوسته میانگین می باشد که به ترتیب به صورت زیر نشان داده می شوند.   با توجه به نمونه های کنترل کننده I/O، مقدار اندازه گیری شده به صورت   می باشد که باعث ارتباط زمان ورود در خواست ها در سیستم نسبت به تعداد درخواست ها متوسط در هر واحد زمانی توسط کنترل کننده ها می گردد.

ما روش کارآمد، ساده وکلی را برای کسب مقادیر از دست رفته پارامترهای مدل  ارائه می دهیم به صورتی که مدل های موجود به عنوان بهترین گزینه در ارتباط با بخش های ارزیابی N می باشند. این مسائل به عنوان یک مورد بهینه سازی شده مد نظر قرار داده می شود. ما به توصیف و بررسی تعاریف سنتی و رو به بالایی از تابع هدف که برای تعین تناسب مدل با توجه به تاکید خاص بر روی جنبه های عملی مورد استفاده قرار می گیرد، می پردازیم. ما توضیحات سطح بالایی از الگوریتم DFO را که ما به دنبال حل مشکل بهینه سازی آن می باشیم، ارائه می دهیم. این الگوریتم بر مبنای الگوی درجه دوم تابع عملکرد بوده و مدیریت آسان و کارآمدی از محدودیت هایی را که بر روی این تحقیقات برای ایجاد یک راه حل بهینه می باشد، ایجاد می کند. تکنیک DFO مطرح شده به طور معقولی ساده بوده و در کالیبراسیون مدل های پیوسته با کمتر از 10 پارامتر مشخص شده به پیش می رود.

جهت مشاهده متن کامل فایل ترجمه را دانلود نمایید.

این مقاله به صورت زیر سازماندهی می گردد. در بخش 2، ما دو بررسی موردی را با توجه به سیستم های تمام وقت مد نظر قرار می دهیم. ما از این نمونه ها در سرتاسر مقاله خود استفاده می کنیم تا روش های مطرح شده را توضیح دهیم. در بخش 3، ما به بحث در ارتباط با تعاریف احتمالی تابع هدف می پرداریم و جستجویی را در ارتباط با ارزش های ناشناخته پارامتر مدل ها به عنوان یک مسئله بهینه سازی شده غیرخطی آغاز می کنیم. بخش 4 در ارتباط با الگوریتم بهینه سازی شده مورد استفده در مرحله کالیبراسیون می باشد. نتایج عددی در ارتباط با این دو بررسی موردی در بخش 5 نشان داده شده است.

2. بررسی موردی

در این مقاله، ما دو بررسی موردی را که از شرایط تمام وقت حاصل می گردند مد نظر قرار می دهیم. تجزیه و تحلیل کاملی از آن نه تنها نمونه هایی از کاربرد موفقیت آمیز روش های سطح بالا را نشان می دهد، بلکه به عنوان یک الگویی برای درک توصیف روش های مطرح شده مد نظر قرار داده می شود. در هر دو مورد، سیستم هایی که بر روی آن مطالعه صورت می گیرد مورد ارزیابی قرار گرفته و یک مدل مناسب ولی ناتمام مطرح می گردد تا عملکرد آن را نشان داده و ارزش بعضی از پارامترهای مدل را به طور غیرمشخصی بیان کند.چنین مقادیر پارامتری غیرمشخصی در این مقاله به صورت   تعریف شده اند. به منظور توانایی برای استفاده کارآمد از این مدل، مقادیر مربوط به پارامترهای غیرمشخص می بایست توسط سیستم های اندازه گیری تخمین زده شود.

2.1 بررسی موردی A: سرور شبکه

اولین بررسی موردی از مقاله کاو و همکارانش گرفته شده است که در ارتباط با عملکرد سرور شبکه آپچی می باشد. محقق چندین مجموعه از روش های اندازه گیری شده را در ارتباط با اندازه مختلفی از درخواست می باشد. به طور خاص، آن ها به ارزیابی زمان واکنش   که در ارتباط با درخواست درآمد برای افزایش میزان درخواست های خروجی می باشد، می پردازند.ما در جدول 1 یکی از این مجموعه ها را نشان می دهیم.

کاو و همکارانش این مدل ها را به صورت زنجیره   مد نظر قرار می دهند. در این زنجیره مشتریان بر طبق فرایند پوسان و خدمات جمعی بر طبق به سیاست تقسیم فرایندها نزدیک می شوند.

درخواست های جدید زمانی رد می گردد که حداکثر تعداد درخواست های وارد شده در سرور K مد نظر قرار گیرد. نتایج مقدماتی در ارتباط با توانایی ها نشان می دهد که متوسط عملکرد خطوط بستگی به توزیع خدمات از طریق مقدار میانگین   دارد.میانگین زمان واکنش  ، متوسط خروجی ها  و احتمالات مربوط به مسدود کننده ها  ، دارای شکل بسته ای می باشند که علاوه بر داشتن ظرفیت های موردنظر در ارتباط با اندازه k و متوسط زمان خدمات دهی در این خطوط می باشند.هیچ مقدار خاصی در ارتباط با این دو پارامتر را نمی توان مستقیما از اطلاعات سیستم دریافت کرد. با مد نظر قرار دادن قانون، دو پارامتر نامشخص   وجود دارد که مقدار آن ها با استفاده از اندازه گیری ها تخمین زده می شود. زمانی که محققان مقادیر آن ها را با استفاده از روش جامع بروت فورس تخمین زدند، ما می توانیم از این بررسی موردی به صورت مرحله به مرحله نشان دهیم که چگونه رویکردهای ما به صورت کارآمد کالیبراسیون مربوط به این مدل را نشان می دهد.

بررسی موردی دوم از یک سیستم اطلاعاتی با توجه به تعداد متنوعی از کاربران مد نظر قرار می گیرد. ما تعداد کاربران را با s نشان می دهیم هر یک از آن ها به عنوان یک منبع درخواست مجرد و مستقل مد نظر قرار می گیرد و کل سیستم به عنوان یک مدل حل کننده مشکلات به شمار می آید.

جدول 2 زمان واکنش   را با توجه به درخواست در سیستم نشان می دهد زمانی که   2 یا 4 منبع درخواستی وجود دارد.

با مد نظر قرار دادن نمایی از توزیع ترمیم دستگاه و زمان کلی دستگاه، سیستم تنظیم دستگاه دارای چهار پارامتر می باشد : تعداد کل کاربران s، تعداد سرورها c، میانگین زمان خدمات در هر درخواست   و نسبت ایجاد درخواست های ایده آل y می باشد. چنین مدلی دارای یک راه حل ساده ای می باشد. در این مورد، تعداد کاربران داده می شود اما ما هیچ اطلاعات مستقیمی در ارتباط با پارامترهای مدل باقی مانده نداشته و به این ترتیب   منطبق با   می باشد. همان طور که در زیر نشان داده شده است این روش کالیبراسیون روش اتوماتیکی را به منظور ایجاد مقادیر مناسب برای سه پارامتر نامشخص ایجاد می کند که امکان انطباق این مدل را با اندازه گیری های مربوطه می دهد.

بسیاری از مدل های پیوسته، همانند مواردی که توصیف شد، دارای پارامترهای مشخص و مداوم می باشند. این باعث ایجاد مشکلاتی می گردد زیرا بسیاری از روش های بهینه شده موجود برای استمرار یا مجزا شدن نیازمند پارامترهای تابع هدف می باشند. ما با تمام مدل های مربوط به پارامترها با ملایم کرن محدودیت های مجزا بر روی پارامترهای مشابه سرو کار داریم. برای رسیدن به چنین هدفی، ما مدل های میانجی را به گونه ای معرفی می کنیم که در آن پارامترهای مجزا جایگزین روش های مستمر مشابه می گردند. چنین مدل های میانجی همزمان با مدل های استاندارد، زمانی که پارامترهای مصنوعی دارای مقادیر یکپارچه می باشند، است.

به عنوان مثال در بررسی موردی B،C به عنوان اعداد واقعی به شمار می آیند برای نمونه C=2.87 که بر مبنای بازتعریف میزان خروجی های فرایند تولد و مرگ به صورت زیر می باشد.از حال 1 به حالت 0 نسبت این خدمات برابر با  ، از حالت 2 به حالت 1 این نسبت   می باشد.و از حالت   این نسبت برابر با   است. به طور آشکار، این مدل میانجی با مدل های سنتی کالیبراسیون تلاقی دارد که در آن C عدد صحیح می باشد. در بعضی از مواقع مدل های میانجی  نیازمند مشتق گیری بیشتری می باشند.در بررسی موردی، به منظور تعریف کالیبراسیون   با مقادیر غیر صحیح k برای نمونه k=7.35، می بایست زنجیره مارکو را با اضافه کردن حالت های جدید k+1 مرتب کرده و به انطباق نرخ ورود بین حالت های k و k+1 به  پردازد. توجه داشته باشید اگر تنها مدل های کلاسیک به دنبال این کالیبراسیون ها مورد نیاز باشند ما می توانیم به ارزیابی تمام مدل های بدست امده از مدل های میانجی پرداخته و به گرد کردن پارامترها به عدد صحیح بپردازیم و بهترین نتیجه را کسب کنیم. در موارد خاص، قابل قبول می باشد تا به اجرای بررسی های بهینه سازی بیشتری که به صورت ثابت نگه داشته می شوند پرداخته و فنون بهینه سازی را بر روی پارامترهای باقی مانده به اجرا در آوریم. می بایست این موضوع را مد نظر قرار داد که چنین بررسی هایی نیازمند پیچیدگی های بیشتری به عنوان تعدادی از پارامترهای جستجو  که به طورت کوچک تر بوده و نقطه شروع آن نزدیک به سطح بهینه می باشد، است.

 در پایان باید تاکید کنیم که ما این دو بررسی موردی را برای توصیف رویکردهای مدل دهی در سطح بالا به چند دلیل انتخاب کرده ایم. ابتدا اینکه در مجموع آن ها مواردی را تحت پوشش قرار می دهند که حجم کار در این ارزیابی ها مد نظر قرار گرفته و مواردی که حجم کار ناشناخته می باشد و همچنین نشان می دهد که این ارزیابی ها در هر دو شرایط مورد استفاده قرار می گیرد. دوم اینکه مدل های تحلیلی مربوط به این دو بررسی موردی مطابق با مدل های مختلف طبقه بندی می باشد. که اولین آن ها در یک طبقه باز و مورد دوم در شبکه طبقات بسته قرار می گیرد.در پایان هر دو مدل دارای پارامترهای مجزایی می باشند که تاکیدی بر روی توانایی اداره روش های مان دارند.

3. شکل دهی مربوط به مسائل بهینه سازی.

همان طور که قبلا بیان شد، مدل های تحلیل شامل پارامترهای مشخص و غیر مشخصی می باشند. که به ترتیب به صورت  می باشند. بنا به تعریف، مقادیر مربوط به پارامترهای اول شناخته شده می باشد.از این رو تنها مقادیر پارامتر  قابل تخمین می باشد. در این بخش ما تاکید بیشتری را برای مفهوم مقادیر صحیح پارامترهای  داشته و به پیکره بندی این بررسی ها به عنوان یک مورد بهینه پرداخته ایم.

3.1 کالیبراسیون صحیح

هر یک از مقادیر n در ارتباط با    کالیبراسیون خاصی را از مدل های مورد نظر ارائه می دهد.در بررسی موردی a، که مدل ها به صورت  می باشند، دو پارامتر غیر مشخص   به عنوان میانگین زمان خدمات  و اندازه حافظه میانی k  می باشند. زمان واکنش مورد نظر  پیشنهادی در این رده، همچنین عملکردهای بدست آمده   بر مبنای بار  می باشد یعنی متوسط تعداد درخواست هایی که در هر واحد زمانی به این سیستم ارائه می گردند. فرض کنید   برابر با   باشد، با توجه به چنین کالیبراسیون ما در شکل 1 تابع پارامتری   و همنچنین نقاط ارزیابی را در ارتباط با سرور شبکه مد نظر قرار می دهیم. همان طور که مشاهده می گردد، منحنی عملکردی که از این مدل حاصل می گردد نسبتا جدا از داده های ارزیابی شده می باشد.

ما بهترین مقدار را در ارتباط با پارامتر  ،مقدار n که باعث به حداقل رساندن فرایند اشتقاق بین عملکرد سیستم با توجه به اندازه گیری ها و عملکردهای مشتق شده از مدل با توجه به پارامتر  ، مشخص می کنیم.ما همچنین نیاز به تعیین تابعی داریم که به تعیین انحراف بین ارزیابی ها و مقادیر ایجاد شده توسط این مدل بپردازد.

ما این تابع را به عنوان تابع هدف در نظر گرفته و آن را به صورت   نشان می دهیم. جستجو برای کالیبراسیون صحیح به عنوان جستجو برای مقدار   به حساب می آید که   را به حداقل می رساند . موضوعات مربوط به تعریف   در بخش های بعدی نشان داده خواهد شد در حالی که مراحل مربوط به تحقیق در بخش 4 نشان داده می شود.

3.2 محدودیت ها.

پارامترهای نامشخص مدل   دارای سه نوع محدودیت می باشند.

در ایتدا اینکه ما محدودیت های ساده ای را داریم .  ظاهرا نامحتمل بوده که شامل مقادیر پارامتری غیر سنسیکال می باشد.برای نمونه میانگین زمان خدمات به صورت منفی نمی باشد.محدودیت های مربوط به این نوع معمولا به صورت خطی بوده و به محدود کردن حیطه تعریف   می پردازند.

محدودیت نوع دوم آن مربوط به اندازه گیری و اطمینان از سازگاری مدل طبقه بندی شده با توجه به نقاط اندازه گیری شده می باشد.بر خلاف اولین مجموعه از این محدودیت ها، زمانی که این محدودیت ها ایجاد می گردند،مدل هایی که دارای مقصود و تابع هدف   می باشند، مورد ارزیابی قرار می گیرند.در واقع این ویژگی ها از طریق بهینه سازی الگوریتم هایمان به کار گرفته می شوند. عملا، اکثر این محدودیت ها بر مبنای مفاهیم نظری بر روی پارامترهای عملکردی مدل های طبقه بندی شده می باشند. به طور مثال در بررسی موردی A، متوسط زمان واکنش مشتری در رده   در ارتباط با بارگذاری   آشکارا بیشتر از   و پایین تر از   می باشند. این مدل با توجه به پارامترهای داده شده   نامتناسب با ارزیابی ها می باشد اگر حداقل یکی از این زمان های واکنش بر  اساس سقوط سرورهای شبکه خارج از محدوده  باشد.محدودیت های مشابهی نیز در ارتباط با تمام پارامترهای عملکردی مد نظر قرار می گیرد. به عنوان نمونه در ارتباط با مجموعه های مورد نظر مدلی که به صورت   باشد نامتناسب با ارزیابی حد اشباع به گونه ای می باشد که این مدل نمی تواند به صورت حداقل به یکی از مقادیر مورد نظر خود دسترسی پیدا کند. اکثر این محدودیت ها به صورت غیر خطی می باشند. توجه داشته باشید که به دلیل بی ثبات بودن این اندازه گیری ها و جانبداری ها، ما می بایست چنین محدودیت هایی را کمتر کنیم. محدودیت های مربوط به این نوع دوم در ارتباط با بررسی موردی A و B در بخش 5 به صورت لیست قرار داده شده است.

محدودیت نوع سوم از اطلاعات نسبی سیستم حاصل می گردد. در واقع ما می بایست از این موضوع آگاهی داشته باشیم که که پارامترهای داده شده   اگرچه به طور مستقیم ناشناخته می باشد، می بایست در محدوده مقادیر داده شده قرار گیرد.

از این رو بسیاری از این محدودیت ها به صورت خطی نمی باشد و جستجو برای یک کالیبراسیون صحیح به عنوان یک مسئله بهینه سازی شده غیرخطی می باشد.

3.3 تعریف تابع هدف.

چندین راه برای تعریف تابع هدف   وجود دارد، که منهی به مدل های درجه بنی شده مختلفی می گردد. تعریف یک تابع هدف مناسب در واقه به عنوان یک مرحله مهم می باشد. در این زیرمجموعه ما روش مرحله به مرحله ای را برای تعریف تابع  که متناسب سیستم های طبقه بندی شده این رده می باشد مد نظر قرار می دهیم.ما این مسائل را به دو شاخه مستقل تقسیم می کنیم. ما در ابتدا به تعریف نقاط زوج با مد نظر قرار دادن هر یک از بخش های اندازه گیری شده که از این مدل ها حاصل می گردد، می پردازیم. سپس ما از این نقاط به همراه بخش های اندازه گیری شده دیگر به تعریف تابه هدف مناسبی می پردازیم.

3.3.1 نقاط مزدوج.

هدف تابع هدف   اندازه گیری انحراف بین مدل های کالیبراسیون شده با توجه به مجموعه مقادیر پارامتری   و اندازه گیری های مشابه می باشد. اگرچه مفاهیم کلی نسبتا ساده به نظر می آید، عملا این مورد همیشه برای تعریف اندازه گیری مسافت بین نتایج حاصل از این مدل و مجموعه های مجزای نقاط اندازه گیری شده، مستقیم نمی باشد. ما با هر یک از این نقاط اندازه گیری شده M در ارتباط بوده که به عنوان یک نقطه مزدوج که به نام C بر روی منحنی مدل می باشد، تعریف می گردد.چندین را برای تعریف این نقاط مزدوج وجود داردکه هر یک از آن ها منطبق با مقادیر داده شده از حجم کار می باشند.

جهت مشاهده متن کامل فایل ترجمه را دانلود نمایید.