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

دسامبر 29, 2018 0 By mitra1--javid

ل تضمین میکند. ولی برای مسائل واقعی که معمولاً با ابعاد بزرگ و پیچیده هستند قابل استفاده نیستند. بعنوان مثال روش شاخه و کرانه25 در این دسته از الگوریتمها قرار دارد.
بیشتر مسائل بهینهسازی ترکیبی، در کلاس NP-hard قرار میگیرند، که برای حل آنها از روشهای تقریبی که در یک زمان حل قابل قبول، جوابهایی نزدیک به بهینه را میدهند، استفاده میشوند. روشهای دقیق به دو دسته ابتکاری و فراابتکاری تقسیم میشود.
الگوریتمهای ابتکاری مختلفی برای حل مسائل بهینهسازی ترکیبی ابداع شده است که در آنها، جواب نزدیک به بهینه تولید میشود. اکثر آنها فقط در مورد یک مسألهی به خصوص قابل کاربرد هستند. یکی از نقصهای الگوریتمهای ابتکاری، تولید یک جواب یا تعداد محدودی از جوابها و توقف آنها در بهینهی محلی با کیفیت پایین است. الگوریتمهای فراابتکاری، برای حل این مشکلات و نقصهای روشهای ابتکاری پیشنهاد شدهاند.

2-4-1-1-الگوریتمهای فراابتکاری
الگوریتمهای فراابتکاری در واقع روشهای ابتکاری هوشمندانهتری هستند که قواعد آن نه تنها برای یک مسأله خاص، بلکه برای طیف وسیعی از مسائل طراحی شدهاند. این الگوریتمها تلاش میکنند در دام بهینههای محلی گرفتار نشوند.
الگوریتمهای فراابتکاری را میتوان به شیوههای مختلفی دستهبندی کرد:
الهام گرفته از طبیعت و بدون الهام از طبیعت
با حافظه و بدون حافظه
قطعی و احتمالی
حریصانه و تکرار شونده
مبتنی بر یک جواب و مبتنی بر جمعیت
فهرست معروفترین الگوریتمهای مبتنی بر یک جواب و الگوریتمهای مبتنی بر جمعیت در جدول (2-2) نشان داده شده است.
جدول 2-2. فهرست الگوریتمهای مبتنی بر یک جواب و الگوریتمهای مبتنی بر جمعیت [1].
نام الگوریتمهای فراابتکاری
انواع الگوریتمهای فراابتکاری
جستجوی محلی هدایت شده26 (GLS)
الگوریتمهای مبتنی بر یک جواب
 
روش جستجوی انطباقی حریصانه27 (GRASP)

جستجوی محلی تکرار شونده28 (ILS)

تبرید شبیهسازی شده29 (SA)

جستجوی ممنوعه30 (TS)

جستجوی متغیر همسایگی31 (VNS)

روشهای هموار سازی 32(SM)

روشهای نوسانی 33(NM)

بهینه سازی کلونی مورچگان34 (ACO)
الگوریتمهای مبتنی بر جمعیت
 
کلونی زنبورها 35(BC)

الگوریتم ژنتیک36 (GA)

برنامه ریزی تکاملی37 (EP)

استراتژی تکاملی38 (ES)

برنامهریزی ژنتیک39 (GP)

جستجوی پراکندگی40 (SS)

بهینهسازی گروهی ذرات41 (PSO)

در این تحقیق با توجه به موضوع و ساختار مسأله و تحقیقات گذشته الگوریتم فراابتکاری جستجوی ممنوعه و ترکیبی از الگوریتم جستجوی همسایگی و جستجوی ممنوعه برای حل مدل تک هدفه و از الگوریتم چند هدفه ژنتیک و چند هدفه جستجوی ممنوعه برای حل مدل دو هدفه استفاده شده است.

2-5- الگوریتم جستجوی ممنوعه (TS)
ریشههای الگوریتم جستجوی ممنوعه را باید در دهه 1960 جستجو کرد، اما گلور42 برای نخستین بار آن را در سال 1986 به شکل کنونیاش ارائه کرد. واژه تابو43 از تنگان44 زبان مردم جزایر پلینزی در اقیانوس آرام گرفته شده است. این واژه به معنای شیء مقدسی است که به دلیل قداست نباید به آن دست زد. در دستهبندیهای الگوریتمهای فراابتکاری، الگوریتم TS در گروه الگوریتمهایی قرار دارد که مبتنی بر یک جواب، بهبود دهنده، با حافظه، قطعی و تکرار شونده هستند.
این الگوریتم تقریباً مانند الگوریتمهای جستجوی محلی (LS) کار میکند. با این تفاوت که برای جلوگیری از دور و تسلسل در جوابها و افتادن در دام جوابهای بهینه محلی، از مفهومی به نام لیست ممنوعه45 استفاده میکند.
این الگوریتم از ساختارهای مختلف حافظه، شرایط مختلف برای محدود و آزاد کردن فرایند جستجو (که در لیست ممنوع و شرط آرمانی گنجانده شده) و توابع حافظه در بازههای زمانی مختلف جهت تمرکزدهی و تنوعبخشی جستجو (جهت تقویت و همچنین هدایت جستجو به مناطق جدید) استفاده میکند.
اجزای پایه الگوریتم جستجوی ممنوعه عبارتند از:

2-5-1- همسایگی
در هر تکرار، از الگوریتم حرکتی که در فضای شدنی جواب صورت میگیرد، مجموعهای از جوابها را در فضای جستجو تعریف میکند که به آنها جوابهای همسایه گفته میشود. بنابراین همسایگی، زیرمجموعهای از فضای شدنی جواب است که به صورت زیر تعریف میشود:
N(S): مجموعه جوابهایی که با استفاده از یک حرکت از یک جواب S به دست میآیند.

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

2-5-3- معیار آرمانی<
br /> در برخی مواقع، بعضی از لیستهای ممنوعه، بسیار محکم و سخت بوده و از حرکتهای خوب نیز جلوگیری میکنند، در حالیکه ممکن است هیچ خطری جهت افتادن در دور وجود نداشته باشد و یا حتی ممکن است این حرکات باعث بهبود کلی جستجو شوند. از اینرو لازم است الگوریتم، ممنوع بودن آن مورد خاص را لغو کرده و اجازه دهد آن متغیر وارد جستجو شود. این معیار، معیار آرمانی نام دارد. برخی از معیارهای آرمانی به شرح زیر میباشد:
حرکتی که جواب حاصل از آن از بهترین جواب فعلی بهتر است (مرسومترین حالت).
حرکتی که جواب حاصل از آن از بهترین چند جواب اخیر، بهتر است.
حرکتی که جواب حاصل از آن بین جوابهایی با خاصیتی معین، بهترین است.
حرکتی که جواب حاصل از آن بیشترین شباهت را با بهترین جواب فعلی دارد.
حرکتی که جواب حاصل از آن کمترین شباهت را با جواب فعلی دارد.
حرکتی که در صف خروج از لیست ممنوعه از همه جلوتر است.

2-5-4- استراتژی لیست کاندید
به طور کلی در نظر گرفتن کل همسایگیها، جوابهایی با کیفیت بالا تولید خواهد کرد اما ممکن است بسیار زمانبر باشد. از اینرو بهتر است که جستجوی ممنوعه با یک استراتژی بکار گرفته شود که در آن تنها مناطقی از همسایگی که شامل حرکتهای مطلوبتری هستند مورد توجه قرار گیرند. برخی از این استراتژیها به شرح زیر میباشند:
نمونهگیری تصادفی.
استراتژی زیر بخش.47
استراتژی آستانه کیفیت.48
استراتژی اولین بهبود.49
استراتژی لیست کاندید نخبه.50
حرکتی که در صف خروج از لیست ممنوعه از همه جلوتر است.
2-5-5- استراتژی تقویت51
استراتژی تقویت به معنای یافتن حرکت‌های خوب و افزایش انجام آن حرکت‌ها در الگوریتم است. استراتژی تقویت، در بسیاری از پیاده‌سازی‌های جستجوی ممنوعه استفاده می‌شود، اما همیشه ضروری نیست، زیرا حالت‌های بسیاری وجود دارد که در آنها جستجوی معمولی کفایت می‌کند.

2-5-6- استراتژی تنوع بخشی52
روش‌های مبتنی بر جستجوی محلی هر چند جواب‌های خوبی میدهند، اما ممکن است جستجو از کشف مناطق بهتر باز بماند و بنابراین به جواب‌هایی برسد که از جواب بهینه، بسیار دور هستند. استراتژی تنوع‌بخشی، مکانیزمی است که برای حل این مشکل تلاش می‌کند. برای انجام این کار، تنوع‌بخشی جستجو را مجبور می‌کند به سوی مناطقی که تاکنون کشف نشده است حرکت کند و یکی از اهداف آن جلوگیری از قرار گرفتن فرآیند حل در یک بهینگی محلی است.
دو روش عمده برای متنوعسازی وجود دارد:
1- شروع دوباره: جستجو را از نقاطی که کمتر مورد استفاده قرار گرفتهاند و یا از جواب بهینهای که پیدا کرده است، دوباره شروع میکند (نقاط دیگر را در داخل لیست ممنوعه قرار میدهد).
2- هدایت جستجو: قرار دادن مکانیزمی در فرایند جستجو که کار رعایت پراکندگی را از همان ابتدا در دستور کار قرار میدهد.

2-5-7- معیار توقف
برای هر الگوریتم ابتکاری باید معیاری جهت توقف جستجو تعریف شود. به این معیارها شروط پایانی میگویند. شروط پایانی در الگوریتم جستجوی ممنوعه عبارتند از:
توقف بعد از تعداد تکرارهای از قبل تعیین شده.
توقف بعد از زمان محاسباتی از قبل تعیین شده.
توقف بعد از تعدادی از تکرارهای بدون بهبود.
توقف بعد از رسیدن به نقطه خاصی از فضای جستجو [1-3].

شبه کد الگوریتم جستجوی ممنوعه در شکل (2-3) نشان داده شده است.
pseudo-code for tabu search (TS).
x=x0; /* initial solution*/
Initialize the tabu list, medium-term and long-term memories, and candidate list
Repeat
Find best admissible neighbor x’ from candidate list; /*There is not in tabu list
or the Aspiration criterion*/
x=x’
Update tabu list, aspiration conditions, medium and long memories,
candidate list;
If intensification criterion holds Then intensification
If diversification criterion holds Then diversification
Until Stopping criteria satisfied
Output: Best solution found.
شکل 2-3. شبه کد الگوریتم فراابتکاری جستجوی ممنوعه (TS) [1].

2-6- الگوریتم جستجوی متغیر همسایگی (VNS)
الگوریتم جستجوی همسایگی متغیر(VNS)، یک الگوریتم فراابتکاری است که اولین بار در سال 1997 توسط ملادینوویچ53 و هانسن54 ارائه شد. ایده اصلی در VNS، تغییرات سیستماتیک ساختار همسایگی55 از پیش تعیین شده است که برای جستجوی جواب بهینه در فضای مسائل بهینهسازی ترکیباتی به کار میرود. تغییرات سیستماتیک از طریق تغییر موقعیت از یک همسایگی به همسایگی دیگر جواب در حین جستجوی فضای جواب صورت میگیرد. توالی استفاده از ساختارهای همسایگی بصورت تصادفی یا سیستماتیک صورت میگیرد. الگوریتم VNS، با بکارگیری ساختارهای همسایگی مناسب و متنوع به بهینههای محلی مختلفی دست یافته و جستجوی جواب را در نواحی مختلفی از فضای جواب انجام میدهد. در واقع با استفاده از همسایگیهای متفاوت در جستجوی محلی، میتواند بهینههای محلی متفاوتی را تولید کند، در نتیجه، میتوان امید داشت که یکی از بهینههای محلی بدست آمده از این روش، بهینه سراسری باشد. در حقیقت، همسایگیهای مختلف، سطوح مختلف جستجو را ایجاد میکنند) شکل 2-4(.

در این الگوریتم برای جستجو در فضای جواب از دو موتور جستجوی اصلی یعنی فرآیندهای ارتعاش56 و جستجوی محلی57 استفاده میشود.

2-6- 1- فرآیند ارتعاش
فرآیند ارتعاش به عنوان یک عامل نوگرا58 و اغلب برای تولید تصادفی جواب همسایگی، از جواب فعلی بکار میرود. در حالی که جستجوگر محلی، جستجوی وسیع و اصلی را انجام میدهد. الگوریتم VNS با کمک فرآیند ارتعاش قادر
است، از خطر افتادن در بهینگی محلی که در بسیاری از مسائل بهینهسازی ترکیباتی محتمل میباشد، جلوگیری کند.

2-6- 2- فرآیند جستجوی محلی
پس از هر فرآیند ارتعاش، که الگوریتم به ناحیهای جدید از فضای جواب هدایت شده، کار فرآیند جستجوی محلی برای به دست آوردن نقطه بهینه محلی در آن ناحیه، آغاز میشود.
بر خلاف بسیاری از الگوریتمهای ابتکاری دیگر، الگوریتم VNS و مشتقات آن بسیار ساده هستند و نیاز به تعداد پارامترهای تنظیم شده کمتری دارند. دستیابی به جوابهایی با کیفیت بالا، در کنار ساده بودن این روش، کارایی مناسب این الگوریتم را بیش از پیش نمایان میکند [1-42-43].
شبه کد الگوریتم VNS در شکل (2-5) نشان داده شده است.

pseudo-code for VNS.
Initialization: Select a set of neighborhood structures Nk, k=1, . . . , kmax,
and random distributions for the Shaking step that will be used in the search;
find an initial x, choose anstopping condition (usually maximal allowed CPU time tmax);
Repeat the fllowing sequence until the stopping condition is me:
(1) Set k 1;
(2) Repeat the fllowing steps until k kmax
(a) Shaking: Generate a point y randomly from the kth neighborhood of
x(yNk (x));
(b) Local search: Apply some local search method with y as initial solution
to obtain alocal optimum given by y’;
(c) Neighborhood change: If this local optimum is better than the incumbent,
move there (x y’), and continue the search with N1 (k 1);
otherwise, set k k+1.

شکل 2-5. شبه کد الگوریتم فراابتکاری جستجوی همسایگی متغیر(VNS) [43].
2-7-مدلهای بهینه سازی چند هدفه
مسائل بهبنهسازی از نظر تعداد توابع هدف و معیارهای بهینهسازی به دو دسته تقسیم میشوند: مسائل بهینهسازی تک هدفه و مسائل بهینهسازی چند هدفه. در مسائل بهینهسازی تک هدفه، هدف از حل مسأله بهبود یک شاخص عملکرد59 یگانه است که مقدار کمینه یا بشینه آن، کیفیت پاسخ به دست آمده را به طور کامل منعکس میکند. اما در برخی موارد، نمیتوان صرفاً با اتکای به یک شاخص، یک پاسخ فرضی برای مسأله بهینهسازی را امتیازدهی نمود. در این نوع مسائل ناگزیریم که چندین تابع هدف یا شاخص عملکرد را تعریف نماییم و به طور همزمان، مقدار همه آنها را بهینه کنیم. تاکنون، روشهای متعددی برای حل مسائل بهینهسازی چندهدفه معرفی شده است که از میان آنها، روشهای فراابتکاری جایگاه ویژهای دارند.
برای مسائل بهینهسازی چندهدفه، نمیتوان یک نقطه بهینه که به طور همزمان همه اهداف را بهینه کند پیدا کرد. هنگام جستجو برای جواب ممکن است به نقاطی برسیم که بهبود دادن یک هدف منجر به بدتر شدن اهداف دیگر شود. یک جواب