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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

مثال‌ها[ویرایش]

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

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

توصیف[ویرایش]

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

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

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

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

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

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

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

همچنین نگاه کنید به[ویرایش]

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

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

فضاهای واقعی جستجو[ویرایش]

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

منابع[ویرایش]

  • 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 ۳۳(۳().

پیوند به بیرون[ویرایش]