منابع پایان نامه ارشد با موضوع بهینه سازی چندهدفه، الگوریتم ژنتیک، شبیه سازی

دانلود پایان نامه ارشد

این تخصیص ممکن است قبل از تصمیم گیری برای انجام خدمت اتفاق بیفتد، بنابراین ممکن است گفته شود که خدمت دهندگان متحرک ممکن است با یکدیگر همکاری کنند، درحالیکه خدمت دهندگان ثابت تمایلی به این کار ندارند.
2) اگر یک کاربر، درخواستی را انجام دهد و نزدیکترین خدمت دهنده مشغول باشد، خدمت دهنده دیگری ارسال می‌شود. یعنی، این تخصیص، در حالت مطلق، به نزدیکترین تسهیل اتفاق نمی‌افتد.
3) مسائل مکانیابی احتمالی اغلب می‌توانند به خوبی به صورت مجموعه مستقلی از سیستم‌های صف، مدل سازی شوند. این استقلال، ازطریق ابزاری ناشی می‌شود که حتی اگر زمان‌های خدمت از یک توزیع نمایی پیروی کنند، درمورد هنگامی‌که زمان سفر احتمالی است، این امر صادق نیست. بنابراین، تئوری صف M/G/m مناسب‌تر از تئوری M/M/m است.
حال به فرموله کردن مسأله می‌پردازیم. محدودیت‌های مسأله معمولاً شامل موارد ذیل است:
– یک حد بالای M بر روی کل تعداد تسهیلاتی که می‌توانند واقع شوند:
(14.2)
– یک حد بالای K بر روی کل تعداد خدمت دهندگانی که می‌تواند واقع شوند:
(15.2)
– استانداردهای پوشش: بسته به احتیاجات پوششی که استفاده می‌شود، می‌تواند شکل‌های گوناگونی به خود بگیرد. شاید ساده ترین (و قدیمی‌ترین) شکل این محدودیت‌ها، به این نیاز دارد که حداقل تعداد مشخصی از این خدمت دهندگان ،، باید در حداکثر فاصله مشخصی از هر مکان مشتری i، واقع شوند. اجازه دهید زیرمجموعه‌ای از مکان‌های تسهیلات بالقوه در فاصله موردنیاز از i باشد. پس این محدودیت می‌تواند به صورت زیر بیان شود:
(16.2)
شکل پیچیده تر این محدودیت پوشش، ممکن است احتیاجاتی احتمالی را به زمان‌های پاسخ تحمیل کند. مثلاً، یک پاسخ سه دقیقه‌ای زمان پاسخ را درنظر بگیرید که برای درخواست‌های آمبولانس با ارجحیت بالا موردنیاز است. شکل دیگری از محدودیت‌ها، ممکن است یک حد بالایی را بر روی نسبت درخواست‌هایی که برگردانده می‌شود ،، اعمال کند. به طور خلاصه، ما می‌توانیم یک محدودیت عمومی را به صورت زیر ارائه کنیم. اجازه دهید که یک متغیر تصادفی باشد که بیانگر «سطح سرویسی» است که بوسیله سیستم به نقاط تقاضای مشتری i تحویل می‌شود (مثلاً، زمان پاسخ). اجازه دهید، ، بیانگر حداقل فراوانی مطلوب این اتفاق باشد (مثلاً، 95% از این زمان). بنابراین، یک محدودیت سطح سرویس کلی می‌تواند به صورت زیر بیان شود:
(17.2)
اکنون، مسأله LPSDC عمومی می‌تواند به صورت زیر فرمول بندی شود:
(18.2)
باتوجه به محدودیت‌های (15)، (16) و (17)

بدیهی است که برای اینکه فرمول بندی بالا را ساده کنیم، به بعضی روشها احتیاج داریم تا پارامترهای کارایی سیستم گوناگونی را که در توسعه تابع هدف و محدودیت‌ها استفاده شد را ارائه کنیم (یعنی، احتمال برگرداندن ، زمان انتظار صف و غیره). متأسفانه، معمولاً بیان تحلیلی کلی برای این مقادیر دردسترس نیست. این منجر به دو رویکرد ممکن می‌شود: رویکرد اول نیاز دارد که فرضیاتی ساده سازی مطمئنی را بر روی عملیات سیستم ایجاد کنیم (مانند قوانین منطقه‌ای ساده، زمان‌های سفر قابل اغماض و غیره). دومین رویکرد شامل استفاده از تکنیک‌هایی براساس توصیف است (مثل شبیه سازی) تا اندازه‌های کارایی سیستم موردنیاز را برای مقادیر خاص بردار مکان x محاسبه کنیم. علاوه بر آن می‌توان از بعضی تکنیک‌های ابتکاری استفاده کرد.
2-3- نظریه صف
انتظار در صف هر چند بسی ناخوشایند است، اما متأسفانه بخشی از واقعیت اجتناب ناپذیر زندگی را تشکیل می‌دهد. انسان‌ها در زندگی روزمره خود با انواع مختلف صف، که به از بین رفتن وقت، نیرو و سرمایه آن‌ها می‌انجامد، روبه رو می‌شوند. اوقاتی که در صف‌های اتوبوس، ناهارخوری، خرید و نظایر آن‌ها به هدر می‌رود، نمونه‌های ملموسی از این نوع اتلاف‌ها در زندگی است. در جوامع امروزی صف‌های مهمتری وجود دارد که هزینه‌های اقتصادی و اجتماعی آن‌ها به مراتب بیش از نمونه‌های ساده فوق است.

2-3-1- مشخصات صف [13]
یک مدل صف در شکل (2-1) نشان داده شده‌است. آن می‌تواند یک مدل صف مثل ترتیب ماشین آلات یا اپراتورها باشد.

شکل 2-1- مدل پایه‌ای صف
یک مدل صف بوسیله مشخصات زیر توصیف می‌شود:
• فرایند رسیدن مشتریان
معمولاً فرض می‌کنیم که زمان بین رسیدن‌ها مستقل هستند و یک توزیع رایج دارند. در بسیاری از کاربردهای عملی، مشتریان باتوجه به یک جریان پواسن (یعنی زمان بین رسیدن‌ها نمایی) می‌رسند. مشتریان ممکن است یک به یک و یا به صورت دسته‌ای برسند.
• رفتار مشتریان
مشتریان ممکن است صبور باشند و راضی باشند که (برای یک مدت طولانی) منتظر بمانند. یا مشتریان ممکن است کم حوصله باشند و بعد از مدتی صف را ترک کنند.
• زمان‌های رسیدن
معمولاً فرض می‌کنیم که زمان‌های رسیدن مستقل هستند و به طور یکسان توزیع شده‌اند و مستقل از زمان بین رسیدن‌ها هستند. مثلاً زمان‌های رسیدن ممکن است به صورت قطعی یا نمایی توزیع شده باشد. همچنین ممکن است که زمان‌های رسیدن، وابسته به طول صف باشد.
• نظم سرویس
ترتیبی که مشتریان ممکن است به صف وارد شوند به صورت‌های زیر می‌تواند باشد:
– کسی که اول می‌آید، اوّل هم سرویس دهی می‌شود، مثل ترتیب رسیدن‌ها
– ترتیب تصادفی
– کسی که آخر می‌آید، اول سرویس دهی می‌شود.
– حق تقدّم
– اشتراک پردازنده (در کامپیوتر که قدرت پردازششان را در میان کل کارها در سیستم، به طور مساوی تقسیم می‌کنند).
• ظرفیت سرویس
ممکن است یک سرور تک و یا گروهی از سرورها به مشتریان کمک کنند.
• اتاق انتظار
ممکن است محدودیتهایی در رابطه با تعداد مشتریان در سیستم وجود داشته باشد.
یک کد سه قسمتی برای مشخص کردن این مدل‌های به صورت a/b/c استفاده می‌شود که حرف اول توزیع زمان بین رسیدن‌ها و حرف دوم توزیع زمان سرویس را مشخص می‌کند. مثلاً برای یک توزیع عمومی از حرف G و برای توزیع نمایی از حرف M (که M بیانگر فاقد حافظه بودن68 است) استفاده می‌شود. حرف سوم و آخر نیز تعداد سرورها را مشخص می‌کند. این نمادسازی می‌تواند با یک حرف اضافه که دیگر مدل‌های صف را پوشش دهد، گسترش یابد. مثلاً، یک سیستم با توزیع زمان بین رسیدن و زمان سرویس دهی نمایی، یک سرور و داشتن اتاق انتظار فقط برای N مشتری (شامل یکی در سرویس) بوسیله چهار کد حرفی M/M/1/N نشان داده می‌شود.
در این مدل پایه، مشتریان یک به یک می‌رسند و همیشه اجازه ورود به سیستم را دارند، همیشه اتاق وجود دارد، هیچ حق تقدّمی وجود ندارد و مشتریان به ترتیب رسیدن سرویس دهی می‌شوند.
در یک سیستم G/G/1 با نرخ رسیدن و میانگین زمان سرویس ، مقدار کار که در واحد زمان می‌رسد برابر است. یک سرور می‌تواند به یک کار در واحد زمان رسیدگی کند. برای جلوگیری از اینکه طول صف بینهایت نشود، باید .
معمولاً از نماد زیر استفاده می‌کنند:

اگر ، نرخ اشتغال یا بکارگیری سرور نامیده می‌شود، چون کسری از زمان است که سرور، مشغول کارکردن است.
2-3-2- قانون ليتِل69 [13]
اگر E(L)، میانگین تعداد مشتریان در سیستم، E(S)، میانگین زمان اقامت مشتری در سیستم باشد و ، متوسط تعداد مشتریانی باشد که در واحد زمان وارد سیستم می‌شوند، قانون ليتِل، رابطه بسیار مهمی را بین این سه نماد می‌دهد و به صورت زیر بیان می‌شود:
(19.2)
در اینجا فرض می‌شود که ظرفیت سیستم برای رسیدگی به مشتریان کافی است (یعنی، تعداد مشتریان در سیستم به سمت بینهایت میل نمی‌کند).
به طور حسی، این نتیجه می‌تواند به صورت زیر فهمیده شود: فرض کنید که مشتریان هنگامی‌که به سیستم وارد می‌شوند، یک دلار در واحد زمان می‌پردازند. این پول می‌تواند به دو روش گرفته شود. روش اول اینکه به مشتریان اجازه دهیم که به طور پیوسته در واحد زمان بپردازند. پس متوسط درآمدی که توسط سیستم کسب می‌شود، برابر E(L) دلار در واحد زمان است. روش دوم این است که به مشتریان اجازه دهیم که برای اقامتشان در سیستم، 1 دلار را در واحد زمان در موقع ترک سیستم بپردازند. در موازنه، متوسط تعداد مشتریانی که در واحد زمان، سیستم را ترک می‌کنند برابر متوسط تعداد مشتریانی است که به سیستم وارد می‌شوند. بنابراین سیستم، یک متوسط درآمد دلار را در واحد زمان کسب می‌کند.
با به کار بردن قانون ليتِل در صف، رابطه‌ای بین طول صف، و زمان انتظار W به دست می‌آید:
(20.2)
2-3-3- صف M/M/1
این مدل، حالتی را درنظر می‌گیرد که زمان بین رسیدن‌ها، نمایی با میانگین ، زمان‌های سرویس، نمایی با میانگین و یک سرور مشغول کار است. مشتریان به ترتیب رسیدن، سرویس دهی می‌شوند. ما نیاز داریم که:
(21.2)
درغیراینصورت، طول صف منفجر خواهد شد (قسمت قبل را ببینید). مقدار ، کسری از زمان است که سرور، مشغول کار است.
میانگین تعداد مشتریان در سیستم و همچنین میانگین زمانی که در سیستم گذرانده می‌شوند به صورت زیر بیان می‌شود:
(22.2)
و با استفاده از قانون ليتِل،
(23.2)
میانگین تعداد مشتریان در صف، ، می‌تواند از E(L) و با کم کردن میانگین تعداد مشتریان در سیستم بدست آید:
(24.2)
میانگین زمان انتظار، E(W)، از E(S) و با کم کردن میانگین زمان سرویس بدست می‌آید:
(25.2)
2-4- مسائل بهینه سازی چندهدفه
بسياري از مسائل کاربردي در جهان واقعي را مسائل بهينه سازي ترکيباتي چندهدفه تشکيل مي‌دهند، زيرا متغير‌هاي مجزا و اهداف متضاد به طور واقعي در ذات آنها است. بهينه سازي مسائل چندهدفه نسبت به مسائل تک هدفه متفاوت بوده، زيرا شامل چندين هدف است که بايد در بهينه‌سازي به همه اهداف همزمان توجه شود. به عبارت ديگر الگوريتم‌هاي بهينه سازي تک هدفه، حل بهينه را با توجه به يک هدف مي يابند و اين در حالي است که در مسائل چندهدفه (با چندهدف مخالف و متضاد) معمولاً يک حل بهينه مجزا را نمي توان بدست آورد. بنابراين طبيعي است که مجموعه اي از حل‌ها براي اين دسته از مسائل موجود بوده و تصميم گيرنده نياز داشته باشد که حلّي مناسب را از بين اين مجموعه حل‌هاي متناهي انتخاب کند و در نتيجه حل مناسب، جواب‌هايي خواهد بود که عملکرد قابل قبولي را نسبت به همه اهداف داشته باشد.
2-4-1- فرمول بندی مسائل بهینه سازی چندهدفه
مسائل بهینه سازی چندهدفه را به طور کلی می‌توان به صورت زیر فرموله کرد:
(26.2)

x یک حل است و S مجموعه حل‌های قابل قبول و k تعداد اهداف در مسأله و F(x) هم تصویر حل x در فضای k هدفی و هم مقدار هر یک از اهداف است.
تعریف حل‌های غیرمغلوب: حل a حل b را پوشش می‌دهد، اگر و تنها اگر:
(27.2)
(28.2)
به عبارت دیگر، حل‌های غیرمغلوب، به حل‌های گفته می‌شود که حل‌های دیگر را پوشش داده ولی خود، توسط حل‌های دیگر پوشش داده نمی‌شوند. در شکل (2-2) چگونگی پوشش سایر حل‌ها (دایره‌های با رنگ روشن) توسط مجموعه حل‌های غیرمغلوب (دایره‌های تیره رنگ) نشان داده شده‌است. در این شکل، جبهه‌ی پارتو70 با خط چین نشان داده شده‌است.

شکل 2-2- مجموعه حل‌های غیرمغلوب
2-4-2- الگوریتم‌های تکاملی برای بهینه سازی مسائل چندهدفه بر مبنای الگوریتم ژنتیک
با توجه به آنکه بسياري از مسائل بهينه سازي، NP-Hard هستند، بنابراين حل به روش‌هاي دقيق در يک زمان معقول غيرممکن بوده و در نتيجه، استفاده از روش‌هاي فراابتکاري در اين موارد مناسب مي باشد. درحقيقت الگوريتم‌هاي فراابتکاري براي زماني که محدوديت زماني وجود دارد و استفاده از روش‌هاي حل دقيق ميسّر نبوده و يا پيچيدگي مسائل بهينه سازي زياد باشد، به دنبال جواب‌هاي قابل قبول هستند.
اولین پیاده سازی واقعی از الگوریتم‌های تکاملی، «الگوریتم ژنتیک ارزیابی برداری»71 توسط دیوید اسکافر72 در سال 1984 انجام گرفت. اسکافر الگوریتم را به سه بخش انتخاب، ترکیب و جهش که به طور جداگانه در هر تکرار انجام می‌شدند، تغییر داد. این الگوریتم به صورت کارآمدی اجرا می‌شود، اما در برخی از حالات مانند

پایان نامه
Previous Entries منابع پایان نامه ارشد با موضوع مکانیابی، ساده سازی، قانونگذاری Next Entries منابع پایان نامه ارشد با موضوع رتبه بندی، نخبه گرایی، الگوریتم ژنتیک