الگوریتم جستجوی محلی (بهینه سازی)

این مقاله در باره ی الگوریتمی برای بهینه سازی می باشد.برای جستجوی مقاله جستجوی محلی را ببینید.

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

مثال‌ها

برخی از مسائلی که در آنها الگوریتم جستجوی محلی به کار گرفته شده اند عبارتند از :

1. مسئله پوشش رأسی : که در آن راه حل پوشش راسی از یک گراف است و هدف یافتن راه حلی با حداقل تعداد گره‌ها می باشد.
2. مسئله فروشنده دوره گرد: که راه حل، چرخه ای شامل همه ی گره‌های گراف است و هدف به حداقل رساندن طول کل چرخه می باشد.
3. مسئله رضایت بولی : یک راه حل پیش رو، انتساب‌های درست است و هدف به حداکثر رساندن تعداد اجزای رضایت بخش از طریق انتساب‌های درست است ;در این مورد، راه حل نهایی این است که تنها زمانی که کل عبارت درست باشد مورد استفاده قرار می گیرد.
4. مسئله زمان بندی پرستار: که در آن یک راه حل، انتساب پرستاران به شیفت‌های کاری است به گونه ای که تمام محدودیت‌های ایجاد شده را ارضاء نماید.
5. مسئله خوشه بندی k-medoids و دیگر مسائل تسهیل موقعیت مرتبط، که الگوریتم جستجوی محلی، بهترین نسبت تقریبی شناخته شده از بدترین دیدگاه، را ارائه می دهد.

توصیف

بسیاری از مسائل را می توان از لحاظ فضای جستجو و هدف به چندین روش مختلف مطرح کرد. برای مثال، در مسئله فروشنده دوره گرد، یک راه حل می تواند یک دور (چرخه) و میزان به حداکثر رساندن ترکیبی از تعداد گره‌ها و طول چرخه می باشد. همچنین یک راه حل دیگر می تواند یک مسیر باشد و وجود یک چرخه، بخشی از هدف می باشد.

الگوریتم جستجوی محلی از یک راه حل پیش رو آغاز می شود و سپس به صورت مکرر به راه حل مجاور حرکت می کند .این تنها زمانی امکان پذیر است که روابط همسایه ای و مجاورت در فضای جستجوی مسئله تعریف شده با شد. به عنوان مثال، در مسئله پوشش رأسی، مجاورت یک پوشش رأسی، سایر پوشش‌های رأسی مختلف توسط یک گره می باشد.

برای مسئله رضایت یولی، مجاورت یک انتساب درست، معمولاً انتساب‌های درستی هستند که تنها با ارزیابی یک متغیر نسبت به هم متفاوت می شوند. مسائل مشابه ممکن است مجاورت‌های مختلف متعددی برای آن تعریف شده باشد.

بهینه سازی محلی با مجاور هایش، که مستلزم تغییر k مؤلفه از راه حل‌ها می باشند اغلب به عنوان k-opt'اشاره دارند. بطور معمول، هر راه حل پیش رو، بیشتر از یک راه حل مجاور دارد.انتخاب هر کدام از راه حل‌ها برای حرکت، تنها با استفاده از اطلاعاتی در باره ی راه حل‌های مجاور با راه حل فعلی صورت می گیرد و به همین جهت جستجوی محلی نامیده می شود. زمانی که راه حل مجاور به گونه ای انتخاب شود که به صورت محلی معیار را به حداکثر برساند روش فرا ابتکاری فوق را الگوریتم تپه نوردی (hill climbing) می نامند.وقتی هیچ تنظیماتی برای بهبود در مجاورت و همسایگی صورت نگیرد، جستجوی محلی، در یک نقطه بهینه محلی گیر کرده است.

این مشکل بهینه سازی محلی، را می توان با استفاده از راه اندازی مجدد (تکرار الگوریتم جستجوی محلی با شرایط اولیه متفاوت) یا طرح‌های پیچیده تری بر اساس تکرار مانند جستجوی محلی تکرار شده در حافظه، مانند جستجوی بهینه سازی فعال در حافظه با تغییرات تصادفی کمتر مانند تبرید شبیه سازی شده(Simulated Annealing)، برطرف کرد. پایان الگوریتم جستجوی محلی می تواند بر مبنای یک محدوده زمانی باشد، انتخاب معمول دیگر برای پایان دادن به الگوریتم، هنگامی است که بهترین راه حل یافته شده توسط الگوریتم، در گام‌های معینی بهبود نیافته باشد.

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

برای مسائل خاصی امکان دارد همسایه هایی را در نظر بگیریم که بسیار بزرگ هستند و احتمالا به اندازه نما هستند. اگر بهترین راه حل در میان همسایگان، بتواند بطور کارآمد و مؤثر یافت شود، چنین الگوریتم هایی به عنوان الگوریتم‌های جستجوی مجاور با مقیاس بسیاربزرگ، نامگذاری می شوند .

همچنین نگاه کنید به

جستجوی محلی، جزئی از زمینه‌های زیر است:

• الگوریتم‌های فرا ابتکاری
• بهینه سازی تصادفی
• بهینه سازی

زمینه‌های درون جستجوی محلی شامل موارد زیر است:

• الگوریتم تپه نوردی
• الگوریتم تبرید شبه سازی شده
• الگوریتم جستجوی ممنوعه

فضاهای واقعی جستجو

چند روش برای انجام جستجوی محلی از فضاهای واقعی جستجو وجود دارد :

• Luus–Jaakola : جستجو به صورت محلی با استفاده از یک توزیع یکنواخت و تصاعدی در کاهش محدوده ی جستجو.
• بهینه سازی تصادفی(Random optimization): جستجوی محلی با استفاده از یک توزیع نرمال.
• جستجوی تصادفی(Random search) : جستجوی محلی توسط نمونه برداری کره چند بعدی پیرامون موقعیت جاری است.
• جستجوی الگو(Pattern search): برداشتن گام در امتداد محوری از فضای جستجو با استفاده از کاهش نمایی اندازه گام.

منابع

• Hoos، H.H. and Stutzle، T. (۲۰۰۵) Stochastic Local Search: Foundations and Applications، Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit، (۲۰۰۴): Local SearchHeuristics for k-Median and Facility Location Problems، Siam Journal of Computing ۳۳(۳().

پیوند به بیرون

• SINTEF Optimization