الگوریتم جستجوی محلی (بهینه سازی). این مقاله در بارهٔ الگوریتمی برای بهینه سازی می باشد. برای جستجوی مقاله جستجوی محلی را ببینید.
در علم کامپیوتر، جستجوی محلی یک روش فرا ابتکاری برای حل مسائل بهینه سازی سخت، به صورت محاسباتی می باشد. جستجوی محلی می تواند در مسائلی مورد استفاده قرار گیرد که می تواند به عنوان یافتن راه حلی برای حداکثر رساندن یک معیار در میان تعدادی از راه حل های پیش رو، مطرح شود. الگوریتم های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل های پیش رو ( فضای جستجو ) با استفاده از تغییرات محدود حرکت می کنند تا یک راه حل به نظر مطلوب یافت شود یا یک زمانی سپری شود. الگوریتم های جستجوی محلی در تعداد زیادی از مسائل سخت محاسباتی، از جمله مسائلی از علم کامپیوتر ( مخصوصا هوش مصنوعی ) ، ریاضیات، تحقیق در عملیات، مهندسی، بیو انفورماتیک به طور گسترده به کار می رود. نمونه های از الگوریتم های جستجوی محلی، الگوریتم های WalkSAT و الگوریتم 2 - opt برای مسئله فروشنده دوره گرد می باشد.
برخی از مسائلی که در آن ها الگوریتم جستجوی محلی به کار گرفته شده اند عبارتند از:
• مسئله پوشش رأسی: که در آن راه حل پوشش راسی از یک گراف است و هدف یافتن راه حلی با کمینه شمار گره ها می باشد.
• مسئله فروشنده دوره گرد: که راه حل، چرخه ای از همهٔ گره های گراف است و هدف کمینه سازی درازای کل چرخه می باشد.
• مسئله رضایت بولی: یک راه حل پیش رو، انتساب های درست است و هدف بیشینه سازی شمار اجزای رضایت بخش از طریق انتساب های درست است ; در این مورد، راه حل نهایی این است که تنها زمانی که کل عبارت درست باشد مورد استفاده قرار می گیرد.
• مسئله زمان بندی پرستار: که در آن یک راه حل، انتساب پرستاران به شیفت های کاری است به گونه ای که تمام محدودیت های ایجاد شده را ارضاء نماید.
• مسئله خوشه بندی k - medoids و دیگر مسائل مکانیابی تسهیلات مرتبط، که الگوریتم جستجوی محلی، بهترین نسبت تقریبی شناخته شده از بدترین دیدگاه، را ارائه می دهد.
بسیاری از مسائل را می توان از لحاظ فضای جستجو و هدف به چندین روش مختلف مطرح کرد. برای مثال، در مسئله فروشنده دوره گرد، یک راه حل می تواند یک دور ( چرخه ) و میزان به حداکثر رساندن ترکیبی از تعداد گره ها و طول چرخه باشد. همچنین یک راه حل دیگر می تواند یک مسیر باشد و وجود یک چرخه، بخشی از هدف باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدر علم کامپیوتر، جستجوی محلی یک روش فرا ابتکاری برای حل مسائل بهینه سازی سخت، به صورت محاسباتی می باشد. جستجوی محلی می تواند در مسائلی مورد استفاده قرار گیرد که می تواند به عنوان یافتن راه حلی برای حداکثر رساندن یک معیار در میان تعدادی از راه حل های پیش رو، مطرح شود. الگوریتم های جستجوی محلی از یک راه حل به راه حل دیگر در فضایی از راه حل های پیش رو ( فضای جستجو ) با استفاده از تغییرات محدود حرکت می کنند تا یک راه حل به نظر مطلوب یافت شود یا یک زمانی سپری شود. الگوریتم های جستجوی محلی در تعداد زیادی از مسائل سخت محاسباتی، از جمله مسائلی از علم کامپیوتر ( مخصوصا هوش مصنوعی ) ، ریاضیات، تحقیق در عملیات، مهندسی، بیو انفورماتیک به طور گسترده به کار می رود. نمونه های از الگوریتم های جستجوی محلی، الگوریتم های WalkSAT و الگوریتم 2 - opt برای مسئله فروشنده دوره گرد می باشد.
برخی از مسائلی که در آن ها الگوریتم جستجوی محلی به کار گرفته شده اند عبارتند از:
• مسئله پوشش رأسی: که در آن راه حل پوشش راسی از یک گراف است و هدف یافتن راه حلی با کمینه شمار گره ها می باشد.
• مسئله فروشنده دوره گرد: که راه حل، چرخه ای از همهٔ گره های گراف است و هدف کمینه سازی درازای کل چرخه می باشد.
• مسئله رضایت بولی: یک راه حل پیش رو، انتساب های درست است و هدف بیشینه سازی شمار اجزای رضایت بخش از طریق انتساب های درست است ; در این مورد، راه حل نهایی این است که تنها زمانی که کل عبارت درست باشد مورد استفاده قرار می گیرد.
• مسئله زمان بندی پرستار: که در آن یک راه حل، انتساب پرستاران به شیفت های کاری است به گونه ای که تمام محدودیت های ایجاد شده را ارضاء نماید.
• مسئله خوشه بندی k - medoids و دیگر مسائل مکانیابی تسهیلات مرتبط، که الگوریتم جستجوی محلی، بهترین نسبت تقریبی شناخته شده از بدترین دیدگاه، را ارائه می دهد.
بسیاری از مسائل را می توان از لحاظ فضای جستجو و هدف به چندین روش مختلف مطرح کرد. برای مثال، در مسئله فروشنده دوره گرد، یک راه حل می تواند یک دور ( چرخه ) و میزان به حداکثر رساندن ترکیبی از تعداد گره ها و طول چرخه باشد. همچنین یک راه حل دیگر می تواند یک مسیر باشد و وجود یک چرخه، بخشی از هدف باشد.
