دانلود تحقیق روش شناسی

روش شناسی
مقدمه:
ما مطمئناً فریب خواهیم داد آن دسته از خوانندگانی را که تاکنون به اندازه کافی برای خواندن کتاب موجود صبور بوده اند و کسانی که را که می خواستند بدانند برای حل مساله در نظر خود باید از کدام متاهیورستیک (فوق اکتشافی)کمک بگیرند در واقع،این سوال ،سوال مناسبی است،اما ما باید اقرار کنیم که پیشنهاد یک یا چند راه حل مشخص ممکن نیست دیده شده است نتایج تئوری ضعیفی که در مورد متاهیورستیک ها شناخته شده اند اکثراًدر عمل مفید نیستند در واقع،این نظریه ها تا حدی بیان می کنند که برای اطمینان از اینکه حالت مطلوب به درستی مشخص شده باشد نیاز بوده است که تعدادی از راه حل ها که بزرگتر از تعداد کل راه حل ها ی مساله هستند آزمایش شوند به عبارت دیگر آنها(بطور معمول) پیشنهاد می کردند که از یک روش مشخص استفاده شود اگر نیاز بوده است که حالت مطلوب به صورت کاملاًدرست مشخص شده باشد با این وجود ،در این بخش تلاش خواهد شد که تعدادی راه حل ارائه شود برای ایجاد یک روش اکتشافی بر اساس قوانین فرا علمی که قبلاً مورد بحث قرار گرفت بر اساس قوانین قبلی که ما در قسمت جستجوی تا بو آن
را پذیرفته بودیم ،این توضیح با کمک مساله بهینه سازی داده شده ارائه خواهد شد مساله مسیریابی ماشین برای این مورد خاص انتخاب شده است برای اینکه مثال تا حد ممکن روشن شود ما خود را به ساده ترین مدل مساله محدود کردیم که آن را به عنوان مساله مسیریابی ماشین توانا شده در کتابها می شناسند با این وجود ،روش شناسی پیشنهاد شده یکی از کلی ترین آنهاست و باید برای تمام مسائل پیچیده نیز به همین خوبی قابل اجرا باشد
مساله مسیریابی ماشین مناسب برای آموزش
یک مساله مناسب برای آموزش ،که ساده شده مسائل مسیریابی سودمند هستند می توانند به صورت زیر تعریف شوند یک مجموعه نامشخص از ماشین ها که هر کدام قادر هستند حجمv از کالاها را حمل کنند،نیاز است که n تا از سفارش های مشتری ها را تحویل دهند،از یک ایستگاه مشخص شروع کنند،به ترتیبی که مسافت کلی پیموده شده به وسیله ماشین ها مینیمم شود هر سفارش (یا به طور عادی می توان گفت هر مشتری)
Iحجمی به اندازهvi دارد (I=1 ,..,n) مسیر مستقیم ( dij ) بین مشتری های I,j(I,j=0,...,n) معلوم است،و صفر نشان دهنده ایستگاه شروع (انبار ) است صفرهای ماشین ها با Tk(k=1,2,3..) مشخص می شود که از نقطه آغاز (ایستگاه)شروع شده و با برگشت شان به نقطه آغاز (ایستگاه) تمام می شود یک نوع دیگر از مساله است که محدودیت دیگری را اعمال می کند ،به این صورت که طول مسیر باید از مقدار محدود شده Lبیشتر باشد شکل 7.1 شکل نمودار یک مساله اقلیدسی را نشان می دهد که در نوشته ها ی [christofides et al.,1979]
آمده است با 75 مشتری (که در شکل با دایره های توخالی مشخص شده است و اندازه دایره ها به میزان حجم در خواستی مشتری بستگی دارد ،یعنی هر چه میزان حجم در خواستی مشتری بیشتر باشد ،اندازه دایره بزرگتر است و بالعکس) و یک نقطه شروع (ایستگاه)(که با یک دایره توپر سیاه مشخص شده است و اندازه آن متناسب با ظرفیت ماشین ها می باشد) یک راه حل این مساله می تواند به صورت یک بخش از مجموعه مشتری ها به یک تعداد از زیر مجموعه های سفارشات در نظر گرفته شود،سفارشی که مشخص می کند سلسله مراتبی را که حد آن هر ماشین مجبور است کلیه مشتری هایی که تشکیل یک توررا می دهند ملاقات می کند اولین سوالی که باید به آن پاسخ داده شود درباره تعداد تورهایی است که نیاز است ایجاد شود باید در اینجا ذکر شود که برای مسائل کاربردی ،محدود نیستند و همیشه یافتن یک راه حل ممکن برای مساله بدیهی نیست در واقع،تقسیم مشتری ها به صورت یک تعداد زیر مجموعه مشخص بر اساس وزن کالای در خواستی شان مساله مشهور فشرده سازی np کامل مواد اولیه است حتی اگر تعداد ماشین ها نامحدود نباشد
در نظر گرفتن تمام راه حل های ممکن مساله ممکن است مفید نباشد و این به خاطر این است که مجموعه مورد نظر ممکن است شامل تعداد زیادی از راه حل هایی باشد که کیفیت پایینی دارند و مرغوبیت پایین آنها به آسانی قابل مشاهده است ،برای نمونه هایی که شامل تعداد زیادی از سفرها با یک مشتری هستند یک راهنمای اولیه ممکن است سعی کند که انفجار ترکیبی راه حل ها را محدود کند این راهنما می تواند با داشتن آگاهی درباره مساله و در واقع با به کاربردن یک روش اکتشافی بدست بیاید به عبارت دیگر اندازه مجموعه راه حل های ممکن باید محدود شود یک نوع مثال برای cvrp این است که محدودیت هایی اعمال شود به این صورت که همه سفارشاتی که به وسیله یک مشتری قرار گرفته اند باید در یک سفر یک وسیله مشخص قرار داده شوند به شرطی که ماشین ظرفیت کافی داشته باشد روش دیگری وجود دارد که فقط شامل آن دسته از راه حل هایی می شود که حداکثر از یک یا دو ماشین بیشتر از مینیمم تعداد ماشین های مورد نیاز برای تحویل سفارشات به تمام مشتری ها استفاده می کنند (این حد پایین(مینیمم) تعداد ماشین به آسانی و به صورت مستقیم کل حجم سفارشات ظرفیت یک ماشین بدست می آید)با این وجود اگر به این صورت عمل شود ممکن است یافتن یک راه حل ممکن یا مشخص کردن ساختار یک همسایگی مناسب مشکل است
مدل سازی مساله
این توجه طبیعتاً منجر به این می شود که ما درباره مشخصات s،مجموعه راه حل های ممکن بحث کنیم در واقع ممکن است شکل این مجموعه بسیار پیچیده شود،یعنی بدون داشتن مشخصاتی از یک همسایه بزرگ ایجاد تمام راه حل های ممکن غیر ممکن است یا به صورت دقیق تر ممکن نیست به یک راه حل بهینه دست پیدا کرد با شروع از هر راه حل ممکن در این حالت ،برای اجتناب از تعریف یک همسایه بزرگ و غیر قابل کنترل (بنابراین به اعمال محاسباتی برای انجام یک بار جستجوی محلی که بازدارنده باشد نیاز است) مجموعه راه حل های ممکنگسترش می یابد تا زمانیکه راه حل های جریمه کننده محدودیت های اولیه مساله را نقض کنند بنابراین مساله به صورت زیر اصلاح می شود بهبود می یابد):
Min f(s)+p(s)
Sextended s
که در آن Sextended s و p(s)=0 برایS sوP(S)>0 برای S s


این تکنیک جریمه که از لاگرانژتعدیل شده الهام گرفته است برای استفاده در مواقعی که یافتن یک راه حل ممکن سخت می باشد بسیار مفید است به عنوان مثال این مورد حالتی از جدول زمانی مدارس می باشد جایی که در آن تنوع محدودیت ها زیاد می باشد در cvrp، تعداد ماشین ها می توانند با دلیل قبلی انتخاب شوند راه حل ها می توانند (در حالی که تعدادی از مشتری ها ،سفارشات خود را دریافت نمی کنند)مورد قبول واقع شوند ولی با تعدادی جریمه در این روش ،ایجاد یک راه حل ممکن (و نه کاربردی)یک کار بی فایده میباشد مقدار جریمه برای تحویل ندادن یک سفارش می تواند بصورت خیلی ساده ،هزینه یک سفر برگشتی بین مشتری و نقطه آغاز باشد جریمه ها می توانند در طول جستجو اصلاح شوند به این صورت که:اگر در طول آخرین تکرار ،یکی از محدودیت ها به صورت خود کار باعث تخلف شد ،جریمه مربوط به تخلف از این محدودیت می تواند افزایش بیابد برعکس اگر یک محدودیت هیچ گاه باعث تخلف نشد جریمه مربوط به این تخلف می تواند کاهش پیدا کند این
تکنیک در متن cvrp استفاده شده است [gendreau et al.,1994]
اگر به طور همزمان چندین محدودیت در هدف ایجاد شده باشند ممکن است حالتی اتفاق بیفتد که در آن فقط راه حل های ناممکن دیده شوند این حالت به خاطر آن واقعیت است که جریمه های مختلف در ارتباط با محدودیت ها یی مختلف در وضعیت های متفاوت و یا متضاد می توانند تغییر کنند به طوری که حداقل از یک محدودیت سر پیچی شود،محدودیتی که از آن سرپیچی شده است در طول جستجو تغیر می کند مدل سازی یک مساله همیشه آسان نیست مخصوصاً وقتی که هدف (طبیعی)مینیمم کردن یک ماکزیمم است انتخاب تابع مینیم کننده و تابع جریمه کننده می تواند سخت باشد این توابع باید مقادیر مختلفی در بازه تعریف دامنه شان بگیرند ،به طریقی که جستجو بتواند به صورت موثری هدایت کننده باشد چگونه انتخاب یک حرکت مناسب می تواند بر اساس آن باشد ،وقتی که تعداد زیادی راه حل با هزینه یکسان در همسایگی آن وجود دارد ؟
با این وجود ،الگوریتم های تکامل یافته یا مورچه های ساختگی (مصنوعی)به جستجوهای محلی اشاره نمی کنند حداقل در اکثر نسخه های اولیه شان اینطور می باشند اما اکنون تقریباً تمام اجراهای خوب الهام گرفته شده از متاهیورستیک هایی هستند که شامل یک جستجوی محلی می باشند ،حداقل یک روش ساده پیشرفته
انتخاب همسایه
لازم است که اقدامی برای انتخاب ساختار همسایگی (s)انجام شود،برای توافق با تعریف وسعت راه حل مساله این مساله یک مورد جزئی و پیش پا افتاده نیست زیرا حالت کلی یک همسایگی مناسب برای یک مورد (مثال) داده شده می تواند برای موارد (مثال های) دیگر بد باشد بطور نمونه،این یک انتخاب تجربی است اگرچه ،خصوصیات مساله ممکن است که تعداد ی از مسیرها را تهیه کند