موضوع مقاله: الگوریتم جستجوی محلی (بهینه‌سازی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم جستجوی محلی (بهینه‌سازی) | مقدمه: در علم کامپیوتر، جستجوی محلی یک روش فرا ابتکاری برای حل مسائل بهینه‌سازی سخت، به صورت محاسباتی می‌باشد. | ## بخش 1: الگوریتم جستجوی محلی (بهینه‌سازی) | جستجوی محلی می‌تواند در مسائلی مورد استفاده قرار گیرد که می‌تواند به عنوان یافتن راه حلی برای حداکثر رساندن یک معیار در میان تعدادی از راه حل‌های پیش رو، مطرح شود. الگوریتم‌های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل‌های پیش رو (فضای جستجو) با استفاده از تغییرات محدود حرکت می‌کنند تا یک راه حل به نظر مطلوب یافت شود یا یک زمانی سپری شود. الگوریتم‌های جستجوی محلی در تعداد زیادی از مسائل سخت محاسباتی، از جمله مسائلی از علم کامپیوتر (مخصوصا هوش مصنوعی)، ریاضیات، تحقیق در عملیات، مهندسی، بیو انفورماتیک به‌طور گسترده به کار می‌رود. مثال‌ها برخی از مسائلی که در آن‌ها الگوریتم جستجوی محلی به کار گرفته شده‌اند عبارتند از: مسئله پوشش رأسی: که در آن راه حل پوشش راسی از یک گراف است و هدف یافتن راه حلی با کمینه شمار گره‌ها می‌باشد. مسئله فروشنده دوره گرد: که راه حل، چرخه‌ای از همهٔ گره‌های گراف است و هدف کمینه‌سازی درازای کل چرخه می‌باشد. مسئله رضایت بولی: یک راه حل پیش رو، انتساب‌های درست است و هدف بیشینه‌سازی شمار اجزای رضایت بخش از طریق انتساب‌های درست است ;در این مورد، راه حل نهایی این است که تنها زمانی که کل عبارت درست باشد مورد استفاده قرار می‌گیرد. مسئله زمان بندی پرستار: که در آن یک راه حل، انتساب پرستاران به شیفت‌های کاری است به گونه‌ای که تمام محدودیت‌های ایجاد شده را ارضاء نماید. مسئله خوشه بندی k-medoids و دیگر مسائل مکانیابی تسهیلات مرتبط، که الگوریتم جستجوی محلی، بهترین نسبت تقریبی شناخته شده از بدترین دیدگاه، را ارائه می‌دهد. توصیف بسیاری از مسائل را می‌توان از لحاظ فضای جستجو و هدف به چندین روش مختلف مطرح کرد. | ## بخش 2: الگوریتم جستجوی محلی (بهینه‌سازی) | برای مثال، در مسئله فروشنده دوره گرد، یک راه حل می‌تواند یک دور (چرخه) و میزان به حداکثر رساندن ترکیبی از تعداد گره‌ها و طول چرخه باشد. الگوریتم جستجوی محلی از یک راه حل پیش رو آغاز می‌شود و سپس به صورت مکرر به راه حل مجاور حرکت می‌کند. این تنها زمانی امکان‌پذیر است که روابط همسایه‌ای و مجاورت در فضای جستجوی مسئله تعریف شده باشد. به عنوان مثال، در مسئله پوشش رأسی، مجاورت یک پوشش رأسی، سایر پوشش‌های رأسی مختلف توسط یک گره می‌باشد. برای مسئله رضایت یولی، مجاورت یک انتساب درست، معمولاً انتساب‌های درستی هستند که تنها با ارزیابی یک متغیر نسبت به هم متفاوت می‌شوند. بهینه‌سازی محلی با مجاورهایش، که مستلزم تغییر k مؤلفه از راه حل‌ها می‌باشند اغلب به عنوان k-opt''''اشاره دارند. انتخاب هر کدام از راه حل‌ها برای حرکت، تنها با استفاده از اطلاعاتی در بارهٔ راه حل‌های مجاور با راه حل فعلی صورت می‌گیرد و به همین جهت جستجوی محلی نامیده می‌شود. زمانی که راه حل مجاور به گونه‌ای انتخاب شود که به صورت محلی معیار را به حداکثر برساند روش فرا ابتکاری فوق را الگوریتم تپه نوردی (hill climbing) می‌نامند. وقتی هیچ تنظیماتی برای بهبود در مجاورت و همسایگی صورت نگیرد، جستجوی محلی، در یک نقطه بهینه محلی گیر کرده‌است. | ## بخش 3: الگوریتم جستجوی محلی (بهینه‌سازی) | این مشکل بهینه‌سازی محلی، را می‌توان با استفاده از راه اندازی مجدد (تکرار الگوریتم جستجوی محلی با شرایط اولیه متفاوت) یا طرح‌های پیچیده تری بر اساس تکرار مانند جستجوی محلی تکرار شده در حافظه، مانند جستجوی بهینه‌سازی فعال در حافظه با تغییرات تصادفی کمتر مانند تبرید شبیه‌سازی شده(Simulated Annealing)، برطرف کرد. پایان الگوریتم جستجوی محلی می‌تواند بر مبنای یک محدوده زمانی باشد، انتخاب معمول دیگر برای پایان دادن به الگوریتم، هنگامی است که بهترین راه حل یافته شده توسط الگوریتم، در گام‌های معینی بهبود نیافته باشد. این الگوریتم می‌تواند یک راه حل معتبر را ارائه دهد، حتی اگر در هر زمانی قبل از اینکه پایان یابد دچار وقفه شود. به‌طور معمول الگوریتم‌های جستجوی محلی، الگوریتم‌هایی تقریبی یا نا کامل هستند، از این جهت که، حتی اگر بهترین راه حل پیدا شده توسط الگوریتم بهینه نباشد جستجو ممکن است متوقف شود. این، حتی در صورتی که خاتمهٔ الگوریتم، به علت عدم امکان بهبود راه حل باشد، می‌تواند اتفاق بیفتد، بدین صورت راه حل بهینه می‌تواند دور از مجاورت و همسایگی راه حل‌هایی باشد که الگوریتم از آن‌ها عبور کرده‌است. برای مسائل خاصی امکان دارد همسایه‌هایی را در نظر بگیریم که بسیار بزرگ هستند و احتمالاً به اندازه نما هستند. اگر بهترین راه حل در میان همسایگان، بتواند به‌طور کارآمد و مؤثر یافت شود، چنین الگوریتم‌هایی به عنوان الگوریتم‌های جستجوی مجاور با مقیاس بسیاربزرگ، نامگذاری می‌شوند. | ## جمع‌بندی | همچنین نگاه کنید به جستجوی محلی، جزئی از زمینه‌های زیر است: الگوریتم‌های فرا ابتکاری بهینه‌سازی تصادفی بهینه سازی زمینه‌های درون جستجوی محلی شامل موارد زیر است: الگوریتم تپه نوردی الگوریتم تبرید شبه‌سازی شده الگوریتم جستجوی ممنوعه فضاهای واقعی جستجو چند روش برای انجام جستجوی محلی از فضاهای واقعی جستجو وجود دارد: Luus–Jaakola: جستجو به صورت محلی با استفاده از یک توزیع یکنواخت و تصاعدی در کاهش محدودهٔ جستجو.