دانلودمقاله روش شناسی

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

مقدمه:
ما مطمئناً فریب خواهیم داد آن دسته از خوانندگانی را که تاکنون به اندازه کافی برای خواندن کتاب موجود صبور بوده اند و کسانی که را که می خواستند بدانند برای حل مساله در نظر خود باید از کدام متاهیورستیک (فوق اکتشافی)کمک بگیرند در واقع،این سوال ،سوال مناسبی است،اما ما باید اقرار کنیم که پیشنهاد یک یا چند راه حل مشخص ممکن نیست دیده شده است نتایج تئوری ضعیفی که در مورد متاهیورستیک ها شناخته شده اند اکثراًدر عمل مفید نیستند در واقع،این نظریه ها تا حدی بیان می کنند که برای اطمینان از اینکه حالت مطلوب به درستی مشخص شده باشد نیاز بوده است که تعدادی از راه حل ها که بزرگتر از تعداد کل راه حل ها ی مساله هستند آزمایش شوند به عبارت دیگر آنها(بطور معمول) پیشنهاد می کردند که از یک روش مشخص استفاده شود اگر نیاز بوده است که حالت مطلوب به صورت کاملاًدرست مشخص شده باشد با این وجود ،در این بخش تلاش خواهد شد که تعدادی راه حل ارائه شود برای ایجاد یک روش اکتشافی بر اساس قوانین فرا علمی که قبلاً مورد بحث قرار گرفت بر اساس قوانین قبلی که ما در قسمت جستجوی تا بو آن
را پذیرفته بودیم ،این توضیح با کمک مساله بهینه سازی داده شده ارائه خواهد شد مساله مسیریابی ماشین برای این مورد خاص انتخاب شده است برای اینکه مثال تا حد ممکن روشن شود ما خود را به ساده ترین مدل مساله محدود کردیم که آن را به عنوان مساله مسیریابی ماشین توانا شده در کتابها می شناسند با این وجود ،روش شناسی پیشنهاد شده یکی از کلی ترین آنهاست و باید برای تمام مسائل پیچیده نیز به همین خوبی قابل اجرا باشد
مساله مسیریابی ماشین مناسب برای آموزش
یک مساله مناسب برای آموزش ،که ساده شده مسائل مسیریابی سودمند هستند می توانند به صورت زیر تعریف شوند یک مجموعه نامشخص از ماشین ها که هر کدام قادر هستند حجم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)انجام شود،برای توافق با تعریف وسعت راه حل مساله این مساله یک مورد جزئی و پیش پا افتاده نیست زیرا حالت کلی یک همسایگی مناسب برای یک مورد (مثال) داده شده می تواند برای موارد (مثال های) دیگر بد باشد بطور نمونه،این یک انتخاب تجربی است اگرچه ،خصوصیات مساله ممکن است که تعداد ی از مسیرها را تهیه کند
همسایگی های ساده
مدل به کار برده شده برای مساله مسیریابی ماشین که به عنوان نمونه برای مشاهده ما استفاده شده بسیار ساده می باشد راه حل های ممکن با در نظر گرفتن اینکه لازم نیست تمام سفارشات تحویل داده شوند گسترش می یابند برای این منظور یک سفر دروغین مانند0 Tبا ظرفیت نامحدود اضافه شده است حالت تحویل کالا در این سفر شامل مسیرهای بازگشتی متوالی نقطه شروع –مشتری-نقطه شروع است در این مدل پیدا کردن یک راه حل ممکن بدیهی است زیرا تمام سفارشات می توانند در داخل سفر T0قرار بگیرند در مسائل مسیر یابی ماشین ،تعداد زیادی همسایگی مختلف می توانند در نظر گرفته شوند آسانترین آنها انتقال یک سفارش از یک سفر به سفر دیگر می باشد وسپس دو سفارشی که متعلق به دو سفر متفاوت هستند می توانند با هم مبادله شوند یک همسایگی نسبتاً عمومی که با عنوان CROSSشناخته می شود [TAILLARD et al 1997]
شامل مبادله دو مسیر متعلق به دو مسیر متعلق به دو سفر متفاوت می باشد شکل 7.2 این سه همسایگی را نشان می دهد تغییر مکان ها به وسیله یک تابع اکتشافی ضمیمه شده ارزیابی می شوند یک گروه از دستورات در یک تور قرار داده شده است به طوری که شامل حداقل راه انحرافی می باشد سفارشات تحویل داده شده مشتریان که در داخل سفر باقی می مانند اصلاح نمی شوند ماشین به طور مستقیم از سمت مشتری قبلی به طرف مشتری بعدی که از داخل سفر برداشته شده است رهسپار می شود استفاده از یک تکنیک ساده حذف و اضافه دلالت بر این مورد دارد که وضعیت سفرها،یعنی سفارشی که در آن مشتری ها ملاقات می شوند ،با پیش رفتن جستجوی محلی برتر می شود از نظر علمی،یک مساله فروشنده دوره گرد از نوع سخت NPباید برای هر راه حل آزمایش شده (امتحان شده)حل شود برای اینکه راه حل بیشتر کارا شود،سفرها به صورت دوره ای (ونه خیلی پشت سر هم) درباره بهینه می شوند سفرها وقتی که یک راه حل خوب مربوط به مساله پیدا شود نیز بهینه می شوند این بهینه سازی ها می توانند همچنین به وسیله یک روش خاص (در حالتی که تعداد مشتری ها در هر سفر محدود باشد)یا به وسیله یک تابع اکتشافی مناسب انتخاب شوند.
برای بهبود کارایی ارزیابی همسایگی می توان به این صورت بیان کرد که فقط دو تا از سفرها توسط یک راه حل به یک همسایگی بنابراین با ذخیره سازی،برای تمام حرکت ها،اصطلاحی که برای هر دو سفر درگیر شده،فقط به روز شده آخرین سفرها باید محاسبه شوند تا کل همسایگی ارزیابی شود اینچنین تکنیکی می تواند به صورت قابل توجهی سرعت جستجو را زیاد کند،با افزایش هزینه برای افزایش قابل قبول در حافظه مصرفی برای بکارگیری این تکنیک ،مهم است که ماکزیمم تعداد ماشین های(M) مورد نیاز برای تحویل سفارشات را بدانیم اگر این تعداد را نمی دانیم،به صورت بسیار ساده ای قابل تشخیص می باشد
بیرون کردن زنجیره ها از هم
بیرون کردن زنجیره ها از هم یک تکنیک برای ایجاد یک همسایگی مناسب است که اجرای (در یک حرکت ساده)یک تغییر شکل مهم در یک راه حل راآسان می کند.این تکنیک برای CVRP به خوبی نشان داده می شود.برای مسائل CVRP ساده ترین همسایگی آن همسایگی است که یک مشتری را از یک سفر به سفر دیگر منتقل می کند اگر این
همسایگی در یک جستجوی محلی بکار برده شده است،به کاربردن یک چرخش داخل یک مجموعه و یا یک زیرمجموعه از سفرها سخت است یعنی انتقال یک مشتری از اولین سفر به دومین سفر ،انتقال یک مشتری از سفر دوم به سوم و به همین ترتیب انتقال دادن مشتری از آخرین سفر به اولین سفر .این مراحل در شکل 7.2 نشان داده شده است.یک همسایگی می تواند فقط برای تعداد محدودی از یک زیر مجموعه های سفرها،به طور مثال 2 یا 3 تا از آن ها،پویش شود با این وجود یک تقریب می تواند برای هر تعداد از سفرها انجام شود با حل یک مساله کمکی این کار در [xu and Kelly,1990] پیشنهاد شده است در این مرجع،مساله کمکی یک مساله حداقل هزینه جاری در یک شبکه دو لایه می باشد در این مرجع،لایه اول مربوط به مشتری هاست و لایه دوم مربوط به سفرها می باشد شبکه به صورت زیر ساخته می شود کمان های مستقیم با هزینه 0 وظرفیت یک بین گروه مرجع و هر کدام از گره های مشتری ها و بین هر کدام از گره سفرها و یک گره حفره ایجاد می شوند اگر ممکن باشد (و مجاز باشد ،در جستجوی تابو) برای انتقال دادن مشتری I درتور J T ،یک کمان با ظرفیت 1 بین گره مشتری I و گره
TJ اضافه می شود هزینه این کمان به این صورت می باشد : اضافه کردن مشتری در تور جدید که به وسیله ذخیره سازی به علت حذف مشتری از تور قدیمی تقلیل یافته است محاسبه همه هزینه های مینیمم جاری بین یک و عدد M از تور های ماشین در یک شبکه شامل یک تقریب سراسری مرتبط با حرکات مشتری ها M و...و2و1
[rego and roucairol,1996] مکانیزم دیگری برای پیاده سازی ejection ارائه داده اند نظریه آن ها به این صورت ریزی از تمام راه حل هایی که می توانند بدست بیایند بعد از یک تعداد معین ejection تهیه کنیم
(تجزیه در زیر مساله ها)(POPMUSIC)
در هنگام حل مسائل بزرگ،میل طبیعی این است که مساله به زیر مساله هایی غیر وابسته به هم تجزیه شود این زیر مسائل بعد از این می توانند با به کاربردن یک دستورالعمل مناسب حل شوند در این روش ،نمونه های شامل مسائل بزرگ و پیچیده می توانند به خوبی به هدف نزدیک شوند چون پیچیدگی آنها به کندی و به صورت o(n) یا با سرعت O(nlogn) رشد می کند که n سایز مسئله می باشد.
با این وجود،اعمال یک تجزیۀ نظری در یک مسأله ممکن است راه حل هایی با کیفییت پایین را القا کند،چون زیر مسأله ها کم وبیش بصورت قراردادی وبدون در نظر گرفتن شکل راه حل ایجاد شده اند.در واقع،تجزیۀ یک مسأله بدون داشتن دانش دربارۀ ساختارراه حل های خوب آسان نیست.ایدۀ پشتیبان برای بهینه سازی راه حل های تجربی است در صورتی که شکل کلی راه حل معلوم باشد.
این دستورالعملهای بهینه سازی محلی می توانند تا وقتی که یک راه حل بهینۀ محلی (در ارتباط با یک همسایگی خاص)بدست بیاید تکرار شوند.کلمۀPOPMUSIC مخفف کلمات
Partial Optimization Meta_heurestic Under Spesial Intensification Conditions [Taillard and Vob,2002] وبه معنی بهینه سازی جزیی تابع فرا اکتشافی تحت حالات تشدید خاص می باشد.دانشمندان بسیاری روش های دیگری پیشنهاد کرده اند که هر کدام با POPMUSIC متفاوت هستند وکمترازPOPMUSIC عمومیت دارند مانند:LOPT( که مخفف کلمات Local Optimization)و به معنی بهینه سازی موضعی است [Taillard 2003a]،LNS( که مخفف کلمات Large Scale Neighborhood)و به معنی جدول همسایگی بزرگ است [Shaw,1998]،MIMAUSA (که به نام کسانی که آن را ارائه داده اندیعنی[Mautor and Michelon ,1997] است.)،VNDS [Hansen and Mladenovic ,1999] ،شاخۀ پیوندی وجستجوی تابوو..... محدود شده است.در تعداد زیادی از مسائل ترکیبی، راه حلی مانند S میتواند با مجموعه ای شامل بخش هایS1,S2,……SP نشان داده شود.درمسأله مسیر یابی ماشین،به عنوان مثال یک بخش می تواند یک سفر باشد.ارتباط موجود بین هر جفت ازبخش ها ممکن است تغییر کند.
برای توضیح بیشتر،دو سفر را در نظر بگیرید که شامل مشتری هایی هستند که به هم نزدیکترند که در این صورت تعامل قویتری با هم خواهند داشت نسبت به تورهایی که در دو جهت مخالفند،نسبت به نقطۀ شروع.
ایدۀ اصلی POPMUSIC ساخت(ایجاد) یک زیر مسأله است که خود شامل بخش اصلی Si باشد،و یک عدد مانند r که r<p وr نشان دهندۀ تعداد بخشهای ,Si2,……,Sir S i1 است که هر کدام به طور مجزا با بخش اصلی Si در ارتباط هستند.

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله  45  صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید