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

بخشی از مقاله

روش شناسی

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

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

مساله مسیریابی ماشین مناسب برای آموزش
یک مساله مناسب برای آموزش ،که ساده شده مسائل مسیریابی سودمند هستند می توانند به صورت زیر تعریف شوند یک مجموعه نامشخص از ماشین ها که هر کدام قادر هستند حجم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 در ارتباط هستند.
این r بخش زیر مسألۀ Ri را تشکیل می دهند،که این زیر مسأله از مسألۀ اولیّه کوچکتر است و میتواند بوسیلۀ پروسیژرad hoc(تک منظوره)حل شود.

در این حالت اگر هر بهبود در زیر مسائل Riباعث بهبود در راه حل کلی شود،سپس طرح کلی برای جستجوی محلی می تواند بدست بیاید.این جستجوی محلی به همسایگی مربوط است که شامل زیرمسأله های بهبود یافته باشد. پس با نگهداری مجموعۀ O از بخشهایی که به عنوان بخش اصلی برای ساختن یک زیر مسأله استفاده میشوند که قادر نیستند راه حل کامل را بهبود ببخشند،جستجو می تواند متوقف شود به محض اینکه تمام P بخش تشکیل دهندۀ راه حل کامل در داخل O قرار داده شوند.بنا براین،یک جستجوی محلی مخصوص طراحی شده است که این جستجو توسط پارامتر rمعرفی میشود که r تعداد بخشهایی است که یک زیر مسأله را می

سازد(الگوریتم 1-7)
1)قراربده راه حل S را که شامل بخش های S1,S2,……,Sp است.
2)O را صفر قرار بده.
3)تا زمانی که{S1,S2,…..,Sp} O است اعمال زیر را تکرار کن:
1-3)Si را طوری انتخاب کن که O . Si
2-3)زیر مسألۀRi را طوری ایجاد کن که شامل r بخش Si1,Si2,…..,Sir باشد بطوری که این بخشها بیشترین ارتباط را با بخش اصلی Si داشته باشند.
3 -3)Ri را بهینه کن.
4-3)اگرRiاصلاح شده است،قراربده{Si1,Si2,……,Sir} O \ O
و S را تغییر بده(مانند مجموعۀ بخشها)
در غیر اینصورت،قرار بده O {Si} O

الگوریتم:POPMUSIC(r)
این روش دقیقا مشابه با یک روش پیشرفته است که از یک راه حل اولیه شروع کرده،به محض اینکه به یک حالت بهینه مرتبط با یک همسایگی بزرگ رسید پایان می یابد. بنابر-این این روش را روشLOPT (بهینگی موضعی)وLNS(جستجوی همسایگی بزرگ)می نامند.
در واقع،ساختار همسایگی که به این ترتیب ساخته میشود شامل تمام راه حل هایی مانند / Sاست که با S در زیر مسألۀ Ri(که i=1,….,p)متفاوت است.یعنی اندازۀ همسایگی با تعداد راه حل هایی که درون زیر مسأله ها وجود دارد مشخص میشود.این عدد به طور طبیعی بسیار بزرگ استوبه صورت نمایی با پارامتر r رشد می کند(در واقع زیر مسألۀ ایجاد شده برای r = p در واقع کل مسأله است).
بهینه سازی یک زیر مسأله کار سخت و دشواری است که فقط در موارد کمی قابل حل است.بنابراین یک راه حل اکتشافی در اکثر موارد سود مند است.
بخش ها

وقتی یک تشدید بر اساس POPMUSIC بکار برده میشود،اولین نیاز این است که معنی یک بخش از راه حل مشخص شود.برای مسایل مسیر یابی ماشین،یک سفر(یعنی،مجموعۀ سفارشاتی که به وسیلۀ یک ماشین تحویل داده شده)برای مشخص کردن یک بخش مفید است.
این روش در[ ochat and Taillard,1995,Taillard,1993,Rochat and Semet,19944] استفاده شده است. همچنین می توان یک مشتری را به جای یک سفر به عنوان یک بخش در نظر گرفت.این روش در[ Shaw,1998] استفاده شده است.
اگر نمونه های مسأله بقدری بزرگ هستند که شامل تعداد زیادی سفر مرتبط به هم هستند،
در نظر گرفتن یک سفر به عنوان بخش مزایایی دارد.مسایلی که به این ترتیب مشخص

شده اند همان مسایل مسیر یابی ماشین هستند.این مسایل میتوانند کاملا ً بصورت مجزا حل شوند.
بخش اصلی
نکتۀ دومی که بدقت در کد اصلی POPMUSIC مشخص شده است روشی است که در آن بخش اصلی انتخاب می شود.آسانترین روش می تواند روش انتخاب بصورت تصادفی باشد.
امکان دیگر می تواند این باشد که بخش های اصلی در نظر گرفته شوندکه قبلا ً انتخابشده باشند.در حالت بهینه سازی موازی زیرمثالها، بخش های اصلی تا حد امکان بصورت سودمندانه ای انتخاب شده اند،بنا براین،اثر مقابل زیر مسأله ها،بر روی هم حداقل میشود.
بعضی دیگر از نویسندگان ] Rochat and Semet,1994 ]پسشنهاد کرده اند که بخش های اصلی متوالی می توانند تا حد ممکن نزدیک به یکدیگر انتخاب شوند.دراین کتاب،همچنین پیشنهاد شده است که ارزش پارامتر r در POPMUSIC در طول جستجو تغییر کند،بنا براین روشی بکار برده میشود که اکنونآن را با نام جستجوی همسایگی متغیر می نامند.

ارتباط بین بخش ها
تعریف ارتباط موجود بین بخش های مختلف سومین نکته ای است که در روش مورد بحث قرارگرفته است. گاهی اوقات این ارتباط به طور طبیعیPOPMUSIC مشخص است.برای مثال می توان حالتی را که درآن مشتری های مسئله مسیریابی ماشین به عنوان بخش ها انتخاب شده اند بیان کرد.فاصله بین مشتری ها یک مقیاس طبیعی از ارتباط بین بخش هاست.اگر در حالتی تورهادرمسئله مسیریابی ماشین به عنوان بخش انتخاب شوند مفهوم مجاورت به آسانی قابل تشخیص نیست.
که مسائل اقلیدسی را حل کردند [Taillard,1993,Rochat and Taillard,1995]درمجاورت توسط مرکز ثقل تورها سنجیده می شود.مقدار سفارش داده شده توسط مشتری به عنوان یک توده تفسیر می شود.شکل قاعدۀ کلی ایجاد یک زیر مسئله توسط یک تور اصلی را نشان می دهد.
روند بهینه سازی

در انتها،آخرین نکته ای که مختص به روش POPMUSIC نیست پرو سیژری است که برای بهینه سازی زیر مسائل مورد استفاده قرار می گیرد. در[Rochat and Taillard ,1995]،,[Taillard 1993]پروسیژر مورد استفاده قرار گرفته، یک جستجوی تابوی اصلی است.Shaw از یک متد خاص بر اساس محدودیت های برنامه نویسی استفاده می کند[Shaw 1998].

نتایج مدل سازی و همسایگی
در پایان بر جنبۀ مدل سازی یک مسئله و بر انتخاب همسایگی اصرار می کنیم،زیرا به نظر ما این مراحل از مهمترین مراحل طراحی موفق یک تابع اکتشافی کارا است.در واقع اگر حتی یکی از این مراحل به صورت ضعیفی آنالیز شده باشد،اضافه کردن یک سطح دیگر (مانند simulated annealing, tabu search, etc)برای به دست آوردن نتایج بهتر نسبت به مراحلی که به وسیلۀ یک روش پیشرفتۀ ساده ایجاد شده اند میتواند گول زننده شود.

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

.مسیر یابی ماشین تصویری مناسب از اهمیت این مرحله را ارائه میدهد:روشی که در [Taillard 1993] توضیح داده شده است،که می تواند تعداد زیادی از بهترین راه حل های شناخته شده برای مجموعه ای از مثال های مهم را بیابد[ Christofides et al.,1997]،بر اساس یک جستجوی تابوی بسیار ساده است.(حرکات در نظر گرفته شده محدود شده اند به جابجایی دو مشتری یا حرکت یک مشتری از یک تور به تور دیگر.تنها قسمتی که به جستجوی تابو اصلی اضافه شده است،در نظر گرفتن جریمه برای حرکات متوالی می باشد.)تمام متد شامل تعداد کمی پارامتر می باشد،در مقایسه با روش های بسیار پیچیده تر،شبیه روش های موجود در [Gendreau et al.,1994,Xu and Kelly,1996] که مکانیزم های پیش رفتۀ متنوع و پارامترها را ترکیب می کند وثابت نمی شود که این مکانیزم ها به صورت قابل توجهی بهتر باشند.

روش های پیشرفته،جستجوی تابو،Simulated annealingو....؟
برای انتخاب یک مدل یا یک همسایگی مناسب،دانستن نوع تابع فرااکتشافی که باید به کار برده شود ضروری است.در حال حاضر تصمیم گیری در مورد اینکه از کدام روش بر مبنای نظری باید استفاده شود،ممکن نیست.یک روش پیشرفتۀ ساده ،با یک همسایگی مناسب،ممکن است

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

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

ده هستند،بدست می آیند بدون آنکه دقیقا بدانیم در طول جستجو چه اتفاقی رخ داده است.
با این وجود،اگراینطوربه نظربیاید که روش،درشناسایی راه حل هاباساختارمتفاوت ناتوان است،یا اگرپارامترها باید با مقدارنهایی شان تنظیم شوند به طوری که روش مانند یک جستجوی تصادفی عمل کند،تلاش های بیشتری اعمال شود.الگوریتمهای تکاملی یا اجتماع مورچه ها(ant colonies) دربین این تلاش ها قراردارند.این روش ها نیازبه یک جستجوی محلی در داخل خود دارند برای اینکه مناسب ومفید شوند.بنابراین اهمیت وتعداد دفعۀ اجرای یک جستجوی محلی نباید نادیده گرفته شود.
بر نامه سازی حافظۀ قابل تغییر
یک نظراجمالی به آخرین موارد به کار گیری الگوریتم های تکاملی،جستوجوهای پراکندگی یا اجتماع مورچه های ساختگی(مصنوعی)فاش میکند که تمام این روش ها به طرف یک چارچوب عادی پیش میرود که آن را برنامه سازی حافظۀ قابل تغییر (AMP) [Tailard,1993,Tailerd et al.,1998] می نامند.این چار چوب می تواند به صورت زیر باشد.

برنامه سازی حافظۀ قابل تغییر
1)مقدار دهی اولیۀ حافظه
2)تا زمانی که به یکی از شرط های پایان نرسیده ایم تکرار کن:
(aبه کمک حافظه یک راه حل جدید بساز.
(bراه حل را توسط یک جستجوی محلی اصلاح کن.
(cحافظه را با اطلاعاتی که توسط راه حل جدید بدست آمده به روز کن.
اکنون،اجازه بدهید در بارۀ اینکه چراتوابع فرا اکتشافی مختلف از همین چارچوب پیروی می کنند قضاوت کنیم.

Ant Colonies
در بطن روش برنامه نویسی حافظۀ قابل تغییر، اثر ترشح هورمون مورچه ها می تواند به عنوان یک شکل از حافظه در نظر گرفته شود.این حافظه برای ساختن راه حل های جدید یا پیروی از قوانین خاص مورچه های مصنوعی(ساختگی)،یا به عبارت دیگر،با پیروی از فرمولهای جادویی،اعتقاد به مفهوم طراحان بهینه سازی مورچه های ساختگی بکار برده می شود.در ابتدا مراحل انجام کار شامل جستجوی محلی نیست.با این وجود،آزمایشات شبیه سازی خیلی زود فاش کردند که کیفیت انجام کار بالا می رود وقتی که یک جستجوی محلی نیز با آن ترکیب می شود.متأسفانه طراح ant colonies عادت داشته است که این قسمت از

شبیه برنامۀ تابع اکتشافی را در داخل مدل " عمل daemon " که ممکن است شامل هیچ چسز نباشد پنهان کند.
الگوریتم های تکاملی یا تقلیدی
در الگوریتم های تکاملی،مجموع راه حل ها می توانند به عنوان یک حافظه در نظر گرفته شوند.در واقع،تعدادی از ویژگی های راه حل ها(البته بهترین آنها)منتقل شده و بهبود یافته اند،از یک نسل به نسل دیگر.آخرین کاربرد الگوریتم های تکاملی سبب جایگزینی تشبه "تحول تصادفی" با یک عملگر دارای جزئیات بیشتر شده است.اه حل بعد ازعمل Crosso

ver،یک جستجو برای یک راه حل بهینۀ محلی آغاز شده است.به طور طبیعی یک جستجوی دارای جزئیات بیشتر می تواند اجرا شود،بعنوان مثال،جستجوی تابو یا .simiulatd annealingدرنوشته ها،این بخش از روش به نام" الگوریتم ژنتیک هیبریدی "یا" الگوریتم تقلیدی "نامیده می شود] .[Moscato 1999
جسجتوی پراکندگی
قدمت جسجوی پراکندگی تقریباً با قدمت الگوریتم های ژنتیکی که روش آنها در ابتدا،به صورت کاملا ً مجزادر سال 1997،پیشنهاد شده بود[[Glover 1997 برابر است.این روش در اواخر دهۀ 90 توانست در بین اجتماعات آکادمی شهرت کسب کند.در مقایسه با الگوریتم های تکاملی،جستجوی تابو و simulated annealing این الگوریتم هنوز در دنیای صنعت مورد استفاده قرار نگرفته است.
جستجوی پراکندگی می تواند به عنوان یک الگوریتم تکاملی در نظر گرفته ش

ود به شرط اینکه خصوصیات مشخص شدۀ زیر را داشته باشد:
1)بردارهای باینری با بردارهای عددی جایگزین می شوند.
2)عملگرانتخاب برای تکثیرممکن است بیش از دوراه حل اصلی را انتخاب کند.
3)عملگر crossover با یک ترکیب خطی محدب یا مقعر جایگزین می شود.
4)عملگر تغییربا یک عملگر اصلاح که راه حل به تازگی ایجاد شده را در فضای راه حل های ممکن تصویر می کند،جایگزین می شود.
این خصوصیات ممکن است به عنوان تعمیمی برای الگوریتم های تکاملی که بعداَ به وسیلۀ چند تن دیگر از نویسندگان مخصوصاَ ] [Muhlenbein et al.,1998 ،کشف وپیشنهاد شده اند درنظر گرفته شوند:
1)استفاده ازعملگر crossover با تعویض بیت ها وزنجیره های کوچک متفاوت است.
2)یک جستجوی معمولی برای بهبود کیفیت راه حل های ایجاد شده به وسیلۀ عملگر crossover بکار برده می شود.

3)بیش از دو parent برای ایجاد فرزند نیاز است.
4)مجموعه به کمک روش های طبقه بندی به جای یک عملگر ابقا اولیه قسمت بندی شده است.
در جستجوی پراکندگی ،ایجاد قسمت های مجزا از مجموعۀ راه حل ها یک تعمیم crossover در الگوریتم های تکاملی است.در الگوریتم های ژنتیک خالص راه حل های یک مسئله فقط به فرم یک زنجیر با طول ثابتی از بیت ها در نظر گرفته می شوند.
در اکثر مسائل ،کد گذاری یک راه حل با استفاده از بردار دودویی ،وابسته به طرح انتخاب شدۀکد گذاری ،طبیعی نیست.
یک الگوریتم ژنتیک ممکن است نتایجی با کیفیت متفاوت ایجاد کند.در نسخ

ه های اولیۀ الگوریتم ژنتیک ،مهمترین نکته انتخاب یک طرح کد گذاری مناسب بود،بقیۀ عملگرها متعلق به یک مجموعۀ استاندارد هستند..در مقایسه،جستجوی پراکندگی که از راه حل های کد گذاری پشتیبانی میکند،طرح عملگر crossover را به کار می برند(تولید راه حل های جدید از مجموعه ها) بصورت خیلی شدید وابسته به حل مسئله هستند.

در اولین مرجع [Glover,1977] ،جستجوی پراکند گی برای برنامه نویسی خطی عددی بکار برده شده است.در این مرجع پیشنهاد شده است که راه حل جدید با یک ترکیب خطی از مجموعۀ راه حل ها ایجاد شود.در حالت کلی،به عنوان مثال برای مسائل جایگشت،ایجاد یک ترکیب خطی از راه حل ها امکان پذیر نیست.در این حالت،یک عملگر crossover خاص باید طراحی شود،که در واقع باید بوسیلۀ یک عملگرمرمت کننده دنبال شود،راه حل جدید قابل قبول نیست.در اغلب موارد ،عملگر مرمت کننده شامل یک جستجوی محلی ساده است.