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

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

در علم کامپیوتر، جستجوی محلی یک روش فرا ابتکاری برای حل مسائل بهینه‌سازی سخت، به صورت محاسباتی می‌باشد. جستجوی محلی می‌تواند در مسائلی مورد استفاده قرار گیرد که می‌تواند به عنوان یافتن راه حلی برای حداکثر رساندن یک معیار در میان تعدادی از راه حل‌های پیش رو، مطرح شود. الگوریتم‌های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل‌های پیش رو (فضای جستجو) با استفاده از تغییرات محدود حرکت می‌کنند تا یک راه حل به نظر مطلوب یافت شود یا یک زمانی سپری شود. الگوریتم‌های جستجوی محلی در تعداد زیادی از مسائل سخت محاسباتی، از جمله مسائلی از علم کامپیوتر (مخصوصا هوش مصنوعی)، ریاضیات، تحقیق در عملیات، مهندسی، بیو انفورماتیک به‌طور گسترده به کار می‌رود. نمونه‌های از الگوریتم‌های جستجوی محلی، الگوریتم‌های WalkSAT و الگوریتم 2-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