تکنیک­های شرکت کننده در الگوریتم­های فرااکتشافی، در محدوده رویه­های ساده جستجوی محلی تا فرایندهای یادگیری پیچیده قرار می­گیرند.
الگوریتم­های فرااکتشافی، تقریبی و عمدتاً غیرقطعی^[۱۲۴] هستند.
ممکن است مکانیزم­ هایی برای اجتناب از به دام افتادن در نواحی محدود^[۱۲۵] فضای جستجو به کار ببرند.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

مفاهیم پایه فرااکتشافات، اجازه توصیف در سطح تجریدی^[۱۲۶] را می­دهد.
فرااکتشافات، مخصوص مسئله خاصی نیستند.
ممکن است از دانش خاص دامنه^[۱۲۷] مسئله به شکل توابع اکتشافی که با استراتژی­ های سطح بالاتر کنترل می­شوند، استفاده کنند.
امروزه، فرااکتشافات پیشرفته­تر، تجربه جستجو را برای هدایت جستجو به کار می­برند.
به طور کلی می­توان گفت فرااکتشافات، استراتژی­ های سطح بالا برای کاوش فضای جستجو با بهره گرفتن از روش­های متفاوت هستند. مسئله مهم این است که توازن مناسبی بین متنوع­سازی و متمرکزسازی وجود داشته باشد. به طور کلی لغت متنوع­سازی به کاوش فضای جستجو اطلاق می­گردد در حالیکه لغت متمرکزسازی به کاوش تجربه جستجوی جمع­آوری شده گفته می­ شود. این لغات از حوزه جستجوی ممنوع وام گرفته شده ­اند و لازم است توجه شود که لغات «کاوش»^[۱۲۸] و «استخراج»^[۱۲۹] گاهی به­جای هم به کار می­روند، در واقع کلمات استخراج و کاوش، اغلب به استراتژی­ های نسبتاً کوتاه مدت وابسته به تصادفی بودن اطلاق می­ شود، در حالی­که متنوع­سازی و متمرکزسازی، به استراتژی­ های میان مدت یا بلند مدت که مبنی بر استفاده از حافظه هستند، گفته می­ شود. به کاربردن لغات متنوع­سازی و متمرکزسازی در معنی اصلی­شان، در کل زمینه فرااکتشافات پذیرفته­ شده­تر است. از یک سو به دلیل شناسایی سریع مناطقی از فضای جستجوی دارای راه حل­های با کیفیت بالا و از سوی دیگر برای هدر ندادن زمان طولانی در مناطقی از فضای جستجو که قبلاً کاوش گردیده و یا راه حل با کیفیت بالایی فراهم نکرده ­اند، توازن بین متنوع­سازی و متمرکزسازی دارای اهمیت بسیار زیادی است.
در ادامه این فصل برای آشنایی بیشتر، برخی روش­های فرااکتشافی مهم و پرکاربرد، در قالب سه دسته کلی روش­های فرااکتشافی معرفی می­شوند.

۴-۳- روش­های مبتنی بر مسیر

عبارت روش­های مبتنی بر مسیر به این دلیل مورد استفاده قرار می­گیرد که فرایند جستجوی انجام شده با این روش­ها، با یک خط سیر در فضای جستجو، مشخص می­ شود. در این روش یک راه حل جانشین ممکن است به همسایگی راه حل فعلی تعلق داشته یا نداشته باشد.
در این روش، الگوریتم از یک حالت اولیه (راه حل اولیه) شروع می­ کند و یک خط سیر را در فضای جستجو توصیف می­ کند. استراتژی مورد استفاده وابسته به پویایی سیستم است، الگوریتم­های ساده یک خط سیر شامل دو بخش تولید می­ کنند که شامل یک فاز گذر است که به دنبال یک جاذب (یک نقطه ثابت، یک چرخه یا جذب­کننده پیچیده) می ­آید. الگوریتم­های دارای استراتژی پیشرفته، خط سیرهای پیچیده­تری تولید می­ کنند که به سادگی نمی­ توان آن­ها را به دو فاز تقسیم ­بندی کرد. ویژگی­های خط سیر، اطلاعاتی در رابطه با رفتار الگوریتم و تأثیر آن با توجه به نمونه مورد نظر فراهم می­ کند. در واقع، نمایش مسئله همراه با ساختارهای همسایگی ، فضای جستجو را تعریف می­ کنند، الگوریتم، استراتژی مورد استفاده برای کاوش فضای جستجو را فراهم می­ کند و سرانجام ویژگی­های فضای جستجوی واقعی، با نمونه مسئله­ای که باید حل شود، تعریف می­گردد.
در ادامه این بخش به معرفی چند نمونه از روش­های فرااکتشافی مبتنی بر مسیر پرداخته شده است.
۴-۳-۱- جستجوی محلی ساده (بهبود تکراری)
جستجوی محلی ساده، اغلب بهبود تکراری نامیده می­ شود، زیرا هر حرکت در صورتی انجام می­ شود که راه حل نتیجه، بهتر از راه حل فعلی باشد. به محض یافتن کمینه محلی، الگوریتم پایان می­یابد. شبه کد این الگوریتم در شکل ۴-۱ دیده می­ شود.
تابع ، می ­تواند برگرداننده اولین بهبود یا بهترین بهبود یا هر گزینه بین این دو باشد. اولی، همسایگی را بررسی کرده و اولین راه حلی را که بهتر از است انتخاب می­ کند، دومی کاملاً همسایگی را کاوش کرده و راه حل با کمترین مقدار تابع هدف را برمی­گرداند. هر دو روش در کمینه­های محلی متوقف می­شوند. پس کارایی آنها به شدت وابسته به تعریف ، و می­باشد. کارایی رویه­های بهبود تکراری در مسایل بهینه­سازی معمولاً اصلاً رضایت­بخش نیست! درنتیجه تکنیک­های زیادی برای ممانعت از گرفتار شدن الگوریتم­ها در کمینه­های محلی توسعه یافتند، که این کار را با اضافه کردن مکانیزم­ هایی انجام می­ دهند که به آن­ها توانایی گریز از کمینه­های محلی را می­ دهند. این مسئله همچنین باعث می­ شود شرایط خاتمه الگوریتم­های فرااکتشافی، پیچیده­تر از رسیدن ساده به کمینه محلی باشد. درواقع، شرایط خاتمه می ­تواند شامل موارد زیر باشد: حداکثر زمان CPU ، حداکثر تعداد تکرار، پیدا شدن راه حل با کمتر از مقدار آستانه تعریف شده یا حداکثر تعداد تکرار بدون بهبود.
شکل ۴-۱: الگوریتم بهبود تکراری
۴-۳-۲- گداخت شبیه­سازی شده
گداخت شبیه­سازی شده، قدیمی­ترین فرااکتشاف است و مطمئناً یکی از اولین الگوریتم­هایی است که استراتژی صریحی برای گریز از کمینه­های محلی دارد. ایده اصلی این است که برای فرار از کمینه­های محلی اجازه حرکت­هایی داده شود که منجر به راه حل­هایی با کیفیت پایین­تر از راه حل فعلی می­گردند. احتمال انجام چنین جا به ­جایی در طول جستجو، کاهش می­یابد. شبه کد الگوریتم گداخت شبیه­سازی شده در شکل ۴-۲ نشان داده شده است.
شکل ۴-۲: الگوریتم گداخت شبیه­سازی شده
الگوریتم با تولید حالت اولیه که به صورت تصادفی یا اکتشافی ساخته می­ شود و مقداردهی اولیه به پارامتر دمایی ، شروع می­ شود. سپس در هر تکرار یک راه حل به طور تصادفی نمونه­برداری شده و بسته به ، و ، به عنوان راه حل جاری جدید پذیرفته می­ شود. اگر باشد، یا در حالت عکس با احتمالی که تابعی از و است، جایگزین می­ شود. این احتمال می ­تواند مقدار توزیع باشد.
دمای در طول فرایند جستجو کاهش می­یابد، پس در ابتدای جستجو، احتمال پذیرش حرکات به سمت بالا (رو ­به قله) بالاست و به تدریج کاهش می­یابد و به یک الگوریتم بهبود تکراری ساده همگرا می­ شود. با توجه به الگوریتم مشخص می­گردد که الگوریتم نتیجه دو استراتژی ترکیبی است: گام برداشتن تصادفی و بهبود تکراری. در فاز اول جستجو، تمایل^[۱۳۰] به بهبود پایین است و اجازه کاوش فضای جستجو داده می­ شود. این مؤلفه نامنظم^[۱۳۱] ، به آرامی در طول اجرای الگوریتم کاهش می­یابد بنابراین منجر به هدایت جستجو به یک کمینه (محلی) می­ شود.
احتمال پذیرش حرکات رو به بالا، با دو فاکتور کنترل می­ شود: تفاضل توابع هدف و دما. از یک سو در دمای ثابت هر چه اختلاف بیشتر باشد، احتمال پذیرش حرکت از به کمتر است. از سوی دیگر، بالاتر، منجر به افزایش احتمال حرکت رو به بالا می­ شود.
انتخاب زمانبندی سرد کردن مناسب، برای کارایی الگوریتم، مهم است. زمانبندی سرد کردن، مقدار را در هر تکرار ، به صورت تعیین می­ کند، که تابعی از دما و شماره تکرار است. نتایج نظری بر روی زنجیره مارکوف ناهمگون^[۱۳۲] بیان می­ کند که تحت شرایط خاص در زمانبندی سردکردن، برای احتمالاً الگوریتم به کمینه سراسری همگرا می­ شود. بدبختانه زمانبندی­های دمای سردکردن که همگرایی به کمینه محلی را تضمین می­ کنند در کاربردهای واقعی، عملی نیستند چون برای اهداف عملی خیلی کند هستند. بنابراین، زمانبندی­های سردکردن سریع­تر در کاربردها بیشتر مورد استفاده قرار می­گیرند.
قانون سردکردن می ­تواند، با هدف سازگار کردن توازن بین متنوع­سازی و متمرکزسازی، در طی جستجو، تغییر کند. روش­های موفق­تر در این زمینه، زمانبندی­های سردکردن غیریکنوا^[۱۳۳] هستند. در این روش­ها تغییر فازهای سردکردن و گرم کردن مجدد، بطور دوره­ای اتفاق می­افتد پس توازن نوسانی بین متنوع­سازی و متمرکزسازی، فراهم می­گردد.
یک روش ساده برای تعیین دمای اولیه ، این است که ابتدا با یک گام­برداری تصادفی، از فضای جستجو نمونه­برداری کنیم تا بتوانیم به طور کامل میانگین و واریانس مقادیر تابع هدف را ارزیابی نماییم.
فرایند پویای توصیف شده توسط گداخت شبیه­سازی شده یک زنجیره مارکوف است، به این صورت که این فرایند یک خط سیر را در فضای جستجو دنبال می­ کند که در آن وضعیت بعدی فقط وابسته به وضعیت فعلی است، یعنی گداخت شبیه­سازی شده ساده، بدون حافظه است. ولی استفاده از حافظه، رویکردهای مفیدی در آن ارائه می­ کند.
گداخت شبیه­سازی شده در مورد مسائل بهینه­سازی زیادی اعمال می­ شود مانند مسئله انتساب درجه دوم و مسئله زمانبندی کار کارگاهی^[۱۳۴]. اما امروزه در اغلب تحقیقات گداخت شبیه­سازی شده به عنوان یک مؤلفه از فرااکتشافات مورد استفاده قرار می­گیرد نه به صورت یک الگوریتم جستجوی مستقل.
۴-۳-۳- جستجوی ممنوع
جستجوی ممنوع از جمله فرااکتشافات پر مراجعه و پر مصرف در مسائل بهینه­سازی می­باشد. جستجوی ممنوع صریحاً از سابقه جستجو، هم برای گریز از کمینه­های محلی و هم برای پیاده­سازی یک استراتژی کاوشی بهره می­برد. الگوریتم جستجوی ممنوع ساده، در جستجوی محلی، بهترین بهبود را به عنوان عنصر^[۱۳۵] پایه اعمال می­ کند و از حافظه کوتاه مدت برای فرار از کمینه­های محلی و اجتناب از افتادن در چرخه­ها استفاده می­ کند. حافظه کوتاه مدت به صورت یک لیست ممنوع است که راه حل­های اخیر را نگهداری کرده و حرکت به سمت آنها را ممنوع می­ کند. پس همسایگی راه حل فعلی، به راه حل­هایی محدود می­ شود که به لیست ممنوع تعلق ندارند. این مجموعه را مجموعه مجاز می­نامیم. در هر تکرار بهترین راه حل متعلق به این مجموعه (معمولاً به ترتیب FIFO) حذف می­ شود. در نتیجه این محدودیت پویا برای راه حل­های مجاز، می­توان جستجوی ممنوع را تکنیک جستجوی پویای همسایگی دانست. با رسیدن به شرط خاتمه، الگوریتم پایان می­یابد، یا در زمانی که مجموعه مجاز تهی شود یعنی کلیه راه حل­های موجود در توسط لیست ممنوع، قدغن شده باشند.
استفاده از جستجوی ممنوع مانع از بازگشت به راه حل­های اخیر می­گردد، پس از چرخه بی پایان جلوگیری شده و جستجو مجبور می شود فقط حرکت رو به بالا را بپذیرد. طول لیست ممنوع یعنی ، حافظه فرایند جستجو را کنترل می­ کند. هر چه این مقدار کمتر باشد جستجو بر روی نواحی کوچک متمرکز می­گردد و برعکس هر چه این مقدار بیشتر باشد، فرایند جستجو نواحی بزرگتری را مورد کاوش قرار می­دهد چون بازدید مجدد از تعداد بیشتری راه حل، قدغن می­گردد. این مقدار می ­تواند برای رسیدن به الگوریتم­های قوی­تر، در طول جستجو تغییر یابد، مثلا به طور متناوب یک مقدار تصادفی در یک محدوده خاص را به دست آورد. روش پویاتری برای تغییر آن، این است که اگر دلیلی^[۱۳۶] برای تکرار راه­حل­ها وجود داشته باشد (یعنی متنوع­سازی بیشتری لازم باشد)، این مقدار افزایش یابد و اگر بهبودی رخ ندهد (متمرکزسازی باید افزایش یابد) کاهش یابد. پیاده­سازی حافظه کوتاه مدت به صورت لیستی از راه حل­های کامل، عملی نیست زیرا مدیریت چنین لیستی بسیار ناکاراست. پس به جای خود راه حل­ها، معمولاً خصوصیات آنها نگهداری می­ شود. خصوصیات عمدتاً مؤلفه ­هایی از راه حل­ها، حرکت­ها یا تفاوت راه حل­هاست. چون می­توان بیش از یک ویژگی را در نظر داشت، یک لیست ممنوع برای هر کدام در نظر گرفته می­ شود. مجموعه خصوصیات و لیست­های ممنوع متناظر، شرایط ممنوعیتی را تعریف می­ کنند که برای فیلتر کردن همسایگی راه حل و تولید مجموعه مجاز به کار می­روند. ذخیره خصوصیات به جای راه حل­های کامل، کاراتر است ولی باعث از دست رفتن اطلاعات می­ شود چون ممنوعیت یک ویژگی، احتمالاً به معنی انتساب وضعیت ممنوع به بیش از یک راه حل است. پس، ممکن است راه حل­های کیفیت بالای دیده نشده، در مجموعه مجاز قرار نگیرد. برای غلبه براین مشکل، مقیاس تنفس^[۱۳۷] تعریف می­ شود که اجازه می­دهد یک راه حل در مجموعه مجاز قرار بگیرد حتی اگر به دلیل شرایط ممنوع، قدغن شده باشد. معمول­ترین مقیاس تنفس، راه حل­هایی را که بهتر از بهترین راه حل جاریست، انتخاب می­ کند.
لیست­های ممنوع تنها راه ممکن برای بهره برداری از سابقه جستجو نیست. آن­ها معمولاً با بهره گرفتن از حافظه کوتاه مدت شناخته می­شوند. اطلاعات جمع آوری شده در طول کل فرایند جستجو نیز می ­تواند بسیار مفید واقع شود. این نوع حافظه طولانی مدت معمولاً با در نظر گرفتن چهار اصل به جستجوی ممنوع اضافه می­شوند: تأخر^[۱۳۸]، فرکانس، کیفیت و تأثیرگذاری. حافظه اخیر برای هر راه حل (یا خصوصیت) آخرین تکراری را که در آن شامل بوده ثبت می­ کند. حافظه مبنی بر فرکانس، تعداد تکرار هر راه حل (خصوصیت) را نگه می­دارد. این اطلاعات، نواحی (یا زیرمجموعه­هایی) از فضای راه حل را که جستجو در آن­ها محدود شده یا به تعداد دفعات زیاد در آنجا مانده­اند شناسایی می­ کند. این نوع اطلاعات مربوط به گذشته، معمولاً برای تنوع بخشیدن به جستجو، استخراج می­گردند. اصل سوم (یعنی کیفیت) به جمع آوری استخراج اطلاعات از سابقه جستجو برای شناخت مؤلفه­ های راه حل خوب است. فرااکتشافات دیگر (مانند بهینه­سازی گروه مورچه­ها) صریحاً از این اصل برای یادگیری ترکیبات خوب مؤلفه­ های راه حل استفاده می­ کنند. سرانجام، تأثیرگذاری، ویژگی توجه به انتخاب­های انجام شده در طی جستجوست و می ­تواند برای نشان دادن اینکه کدام انتخاب­ها بحرانی­ترین هستند، مورد استفاده قرار گیرد.
جستجوی ممنوع به بیشتر مسائل بهینه­سازی ترکیبی اعمال می­ شود، مانند جستجوی ممنوع قوی برای QAP، جستجوی ممنوع واکنشی برای مسئله MAXSAT و مسائل انتسابی.

۴-۴- روش­های جستجوی محلی کاوشگرانه^[۱۳۹]

در این بخش، چند روش مبتنی بر مسیر که بر اساس جستجوی محلی کاوشگرانه کار می­ کنند، معرفی می­گردند. این روش­ها شامل رویه جستجوی تطابقی تصادفی حریصانه (GRASP)، جستجوی همسایگی متغیر(VNS)، جستجوی محلی هدایت شده (GLS) و جستجوی محلی تکراری است.
۴-۴-۱- GRASP
این روش، یک روش فرااکتشافی ساده است که اکتشافات ساختاری و جستجوی محلی را ترکیب می­ کند. ساختار آن، رویه­ای تکراری شامل دو فاز است: ساخت راه حل و بهبود راه حل. در زمان اتمام رویه جستجو، بهترین راه حل یافته­شده برگردانده می­ شود. مکانیزم ساخت راه حل با دو جزء اصلی مشخص می­گردد. تابع اکتشافی سازنده^[۱۴۰] پویا و تصادفی کردن. فرض کنیم راه حل s شامل زیرمجموعه­ای از مجموعه عناصر (اجزای راه حل) است، راه حل با اضافه کردن مرحله به مرحله یک عنصر جدید در هر زمان، ساخته می­ شود. انتخاب عنصر بعدی با برداشتن تصادفی عنصر به صورت یکنواخت از لیست کاندیداها انجام می­ شود. عناصر براساس مقیاس اکتشافی، رتبه ­بندی شده ­اند که به آنها امتیازی می­دهد که تابعی از مزیت درج این عنصر در راه حل جزئی فعلی است. لیست کاندیداها از عنصر ساخته شده است. مقادیر اکتشافی در هر مرحله به­روزرسانی می­شوند پس امتیاز عناصر برحسب انتخاب­های ممکن، در طی فاز ساخت، تغییر می­ کند. برخلاف انواع ایستای توابع اکتشافی که فقط یکبار در زمان شروع ساخت، به عناصر امتیازات را نسبت می­ دهند، این تابع اکتشافی ساختاری، پویاست. به عنوان مثالی از تابع اکتشافی ایستا، در مسئله TSP، هر یالی که هزینه کمتری دارد امتیاز بیشتری دارد. در مورد حالت پویا، تابع اکتشافی درج ارزان­ترین عنصر، می ­تواند به این صورت باشد که امتیاز هر عنصر بر اساس راه حل جزئی فعلی ارزیابی گردد.
طول تاثیر زیادی بر قدرت تابع اکتشافی دارد. اندازه آن می تواند ثابت باشد یا با هر تکرار تغییر یابد. فاز دوم الگوریتم، فرایند جستجوی محلی است که می ­تواند یک جستجوی محلی پایه یا تکنیک پیشرفته­ای مثل گداخت شبیه­سازی شده یا جستجوی ممنوع باشد. GRASP در صورت برقراری دو شرط زیر، می ­تواند مؤثر واقع شود:
مکانیزم ساخت راه حل از امیدوارکننده­ترین مناطق فضای جستجو نمونه­برداری کند.
راه حل­های ساخته شده توسط تابع اکتشافی سازنده، به درّه­های راه حل­های کمینه محلی متفاوت تعلق داشته باشند.
شرط اول از طریق انتخاب توابع اکتشافی ساختاری مؤثر و طول لیست کاندید مناسب برقرار می­گردد ولی دومی با انتخاب تابع اکتشافی ساختاری و جستجوی محلی به شکلی که با هم مناسبت داشته باشند، برقرار می­ شود. این الگوریتم از حافظه جستجو استفاده نمی­کند ولی به دلیل سادگی، عمدتاً بسیار سریع است و در زمان کوتاه راه حل­های نسبتاً خوبی ارائه می­ کند. به علاوه می ­تواند با موفقیت در کنار سایر تکنیک­های جستجو، بصورت ترکیبی مورد استفاده قرار بگیرد.
۴-۴-۲- جستجوی همسایگی متغیر
این روش از استراتژی تغییر پویای ساختار همسایگی بهره می­برد. الگوریتم بسیار کلی است و درجات آزادی زیادی برای طراحی تغییرات و مقداردهی­های خاص دارد. در مرحله مقدار دهی اولیه، مجموعه ­ای از ساختارهای همسایگی تعریف می­گردد. این همسایگی­ها می­توانند به طور اختیاری انتخاب گردند ولی اغلب به نحوی تعریف می­شوند که تعداد اعضای آنها دارای ترتیب صعودی باشد. سپس یک راه حل اولیه تولید می­گردد، اندیس همسایگی مقدار دهی شده و الگوریتم تا زمان رسیدن به شرط خاتمه، ادامه می­یابد. چرخه اصلی الگوریتم شامل سه فاز است: آشفتگی^[۱۴۱]، جستجوی محلی و جا به ­جایی. در فاز آشفتگی، راه حل در امین همسایگی از راه حل جاری ، به طور تصادفی انتخاب می­گردد. سپس، نقطه شروع جستجوی محلی می­ شود. جستجوی محلی می ­تواند از هر ساختار همسایگی استفاده کند. در انتهای این مرحله، راه حل جدید با مقایسه گشته و در صورت بهتر بودن جایگزین آن شده و الگوریتم دوباره با شروع می­ شود. در غیر این صورت افزایش یافته و فاز جدید آشفتگی با بهره گرفتن از همسایگی متفاوت آغاز می­گردد. هدف از فاز آشفتگی ایجاد نقطه شروع بهتر برای جستجوی محلی است و انتخاب همسایگی­ها با تعداد اعضای صعودی منجر به بهبود متنوع­سازی می­گردد.
۴-۴-۳- جستجوی محلی هدایت شده
در روش­های جستجوی ممنوع و جستجوی همسایگی متغیر، از همسایگی­های پویا برای جستجوی کارا و مؤثر استفاده می­گردد. رویکرد متفاوتی برای هدایت جستجو، تغییر پویای تابع هدف می­باشد. جستجوی محلی هدایت شده از این روش استفاده می­ کند.
اصل پایه­ای جستجوی محلی هدایت شده، کمک به عمل جستجو برای حرکت تدریجی از کمینه­های محلی با تغییر چشم انداز^[۱۴۲] جستجوست. در جستجوی محلی هدایت شده فضای جستجو مجموعه راه حل­ها و ساختار همسایگی، ثابت است در حالی­که تابع هدف ، به این منظور تغییر می­ کند که بهینه محلی فعلی را نامطلوب سازد. شکل ۴-۳ این مطلب را نشان می­دهد.

شکل ۴-۳: ایده جستجوی محلی هدایت شده؛ گریز از دره های چشم انداز