الگوریتم جستجوی محلی (بهینه‌سازی)
این مقاله در بارهٔ الگوریتمی برای بهینه‌سازی می‌باشد. برای جستجوی مقاله جستجوی محلی را ببینید.
در علم کامپیوتر، جستجوی محلی یک روش فرا ابتکاری برای حل مسائل بهینه‌سازی سخت، به صورت محاسباتی می‌باشد. جستجوی محلی می‌تواند در مسائلی مورد استفاده قرار گیرد که می‌تواند به عنوان یافتن راه حلی برای حداکثر رساندن یک معیار در میان تعدادی از راه حل‌های پیش رو، مطرح شود. الگوریتم‌های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل‌های پیش رو (فضای جستجو) با استفاده از تغییرات محدود حرکت می‌کنند تا یک راه حل به نظر مطلوب یافت شود یا یک زمانی سپری شود. الگوریتم‌های جستجوی محلی در تعداد زیادی از مسائل سخت محاسباتی، از جمله مسائلی از علم کامپیوتر (مخصوصا هوش مصنوعی)، ریاضیات، تحقیق در عملیات، مهندسی، بیو انفورماتیک به‌طور گسترده به کار می‌رود. نمونه‌های از الگوریتم‌های جستجوی محلی، الگوریتم‌های WalkSAT و الگوریتم 2-opt برای مسئله فروشنده دوره گرد می‌باشد.
برخی از مسائلی که در آن‌ها الگوریتم جستجوی محلی به کار گرفته شده‌اند عبارتند از:
بسیاری از مسائل را می‌توان از لحاظ فضای جستجو و هدف به چندین روش مختلف مطرح کرد. برای مثال، در مسئله فروشنده دوره گرد، یک راه حل می‌تواند یک دور (چرخه) و میزان به حداکثر رساندن ترکیبی از تعداد گره‌ها و طول چرخه باشد. همچنین یک راه حل دیگر می‌تواند یک مسیر باشد و وجود یک چرخه، بخشی از هدف باشد.
الگوریتم جستجوی محلی از یک راه حل پیش رو آغاز می‌شود و سپس به صورت مکرر به راه حل مجاور حرکت می‌کند. این تنها زمانی امکان‌پذیر است که روابط همسایه‌ای و مجاورت در فضای جستجوی مسئله تعریف شده باشد. به عنوان مثال، در مسئله پوشش رأسی، مجاورت یک پوشش رأسی، سایر پوشش‌های رأسی مختلف توسط یک گره می‌باشد.
برای مسئله رضایت یولی، مجاورت یک انتساب درست، معمولاً انتساب‌های درستی هستند که تنها با ارزیابی یک متغیر نسبت به هم متفاوت می‌شوند. مسائل مشابه ممکن است مجاورت‌های مختلف متعددی برای آن تعریف شده باشد.
بهینه‌سازی محلی با مجاورهایش، که مستلزم تغییر k مؤلفه از راه حل‌ها می‌باشند اغلب به عنوان k-opt""اشاره دارند. به‌طور معمول، هر راه حل پیش رو، بیشتر از یک راه حل مجاور دارد. انتخاب هر کدام از راه حل‌ها برای حرکت، تنها با استفاده از اطلاعاتی در بارهٔ راه حل‌های مجاور با راه حل فعلی صورت می‌گیرد و به همین جهت جستجوی محلی نامیده می‌شود. زمانی که راه حل مجاور به گونه‌ای انتخاب شود که به صورت محلی معیار را به حداکثر برساند روش فرا ابتکاری فوق را الگوریتم تپه نوردی (hill climbing) می‌نامند. وقتی هیچ تنظیماتی برای بهبود در مجاورت و همسایگی صورت نگیرد، جستجوی محلی، در یک نقطه بهینه محلی گیر کرده‌است.
این مشکل بهینه‌سازی محلی، را می‌توان با استفاده از راه اندازی مجدد (تکرار الگوریتم جستجوی محلی با شرایط اولیه متفاوت) یا طرح‌های پیچیده تری بر اساس تکرار مانند جستجوی محلی تکرار شده در حافظه، مانند جستجوی بهینه‌سازی فعال در حافظه با تغییرات تصادفی کمتر مانند تبرید شبیه‌سازی شده(Simulated Annealing)، برطرف کرد. پایان الگوریتم جستجوی محلی می‌تواند بر مبنای یک محدوده زمانی باشد، انتخاب معمول دیگر برای پایان دادن به الگوریتم، هنگامی است که بهترین راه حل یافته شده توسط الگوریتم، در گام‌های معینی بهبود نیافته باشد.
الگوریتم جستجوی محلی یک الگوریتم همیشگی (در هر زمانی) می‌باشد. این الگوریتم می‌تواند یک راه حل معتبر را ارائه دهد، حتی اگر در هر زمانی قبل از اینکه پایان یابد دچار وقفه شود. به‌طور معمول الگوریتم‌های جستجوی محلی، الگوریتم‌هایی تقریبی یا نا کامل هستند، از این جهت که، حتی اگر بهترین راه حل پیدا شده توسط الگوریتم بهینه نباشد جستجو ممکن است متوقف شود. این، حتی در صورتی که خاتمهٔ الگوریتم، به علت عدم امکان بهبود راه حل باشد، می‌تواند اتفاق بیفتد، بدین صورت راه حل بهینه می‌تواند دور از مجاورت و همسایگی راه حل‌هایی باشد که الگوریتم از آن‌ها عبور کرده‌است.
برای مسائل خاصی امکان دارد همسایه‌هایی را در نظر بگیریم که بسیار بزرگ هستند و احتمالاً به اندازه نما هستند. اگر بهترین راه حل در میان همسایگان، بتواند به‌طور کارآمد و مؤثر یافت شود، چنین الگوریتم‌هایی به عنوان الگوریتم‌های جستجوی مجاور با مقیاس بسیاربزرگ، نامگذاری می‌شوند.
جستجوی محلی، جزئی از زمینه‌های زیر است: زمینه‌های درون جستجوی محلی شامل موارد زیر است:
چند روش برای انجام جستجوی محلی از فضاهای واقعی جستجو وجود دارد: