جستجوی محلی یا همان Local Search یکی از ساده‌ترین الگوریتم‌های هوش‌مصنوعی در حوزه‌ی بهینه‌سازی است. در درس فعلی می‌خواهیم یک بهینه‌سازیِ ارائه شده برای این الگوریتم به اسم جستجوی محلیِ تکراری را مورد بررسی قرار دهیم تا بتوانیم یکی از نقاط ضعف الگوریتم جستجوی محلی را حذف کنیم.
همان‌طور که احتمالاً از درسِ جستجوی محلی به یاد می‌آورید، این الگوریتم به دنبال بهینه‌سازی در یک محدوده‌ی خاص در همسایگی خود است. به همین دلیل است که آن را الگوریتم جستجو در همسایگی یا الگوریتم تپه‌نوردی (Hill Climbing) نیز می‌نامند. در واقع الگوریتم، به دنبال پیدا کردنِ یک حالت بهینه با توجه به همسایه‌ی نزدیک به خود است. چیزی مانند شکل زیر:
در واقع در جستجوی محلی ابتدا یک راه‌حل به دست می‌آورید که یک نقطه در فضای حالت است (در درس فضای حالت مفصل در این‌باره صحبت کردیم). سپس راه‌حلِ به دست آمده را کمی تغییر می‌دهیم تا یک همسایه از آن راه حل به دست آید (در مورد تغییرِ راه‌حل هم در درس جستجوی ممنوعه صحبت کردیم). حال اگر این همسایه‌ی به دست آمده بهتر از راه‌حل فعلی بود، آن‌را قبول می‌کنیم و اگر بهتر نبود، این همسایه را قبول نمی‌کنیم. یعنی به صورت حریصانه (Greedy) به دنبال بهتر کردن شرایط هستیم تا به یک بهینه‌ی محلی (نسبت به همسایه‌های آن راه‌حل) برسیم. چیزی که در شکلِ بالا در نقطه‌ی شماره‌ی ۲ رخ داده‌است (فرض بر این است که در این شکل هر چه عمق بیشتر باشد، بهینه‌تر است). توجه کنید که نقطه‌ی شماره‌ی ۲ در شکل بالا، یک بهینه‌ی محلی است، به این معنی که بهینه‌های دیگر هم در فضای حالت وجود دارند ولی نقطه‌ی شماره‌ی ۲ در همسایگیِ خود (یعنی نقاط نزدیک به خود) یک نقطه‌ی بهینه است.
جستجوی محلی مشکلِ گیرکردن در بهینه‌های محلی را دارد. الگوریتم باید راهی پیدا کند تا بتواند از بهینه‌ی محلی فرار کند. برای همین، الگوریتمِ جستجوی محلی تکراری یا همان Iterated Local Search به وجود آمد. برای درک این الگوریتم شکل زیر را نگاه کنید:
همان‌طور که مشخص است هنگامی که الگوریتم در یک بهینه‌ی محلی گیر کرده است (محل شماره‌ی ۱)، سعی در فرار از آن دارد. به این فرار در اصطلاحْ آشفتگی (Perturbation) می‌گویند. در واقع الگوریتم سعی می‌کند یک همسایه با کمی اختلاف (همسایه‌ای که نزدیک نباشد) پیدا کند (در شکلِ بالا از نقطه‌ی ۱ به نقطه‌ی ۲ فرار کرده‌است) و بعد از آن جستجوی محلی را در نزدیکیِ نقطه‌ی ۲ ادامه می‌دهد تا به یک حالت بهینه‌تر برسد. پس این همسایه‌ی غیر نزدیک یک فرار از نقطه‌ی فعلی (نقطه‌ی شماره‌ی ۱ در شکل بالا) به نقطه‌ای دیگر (نقطه‌ی شماره‌ی ۲ در شکل بالا) یک آشفتگی در الگوریتم است. البته ممکن است آشفتگی همیشه به بهبود منجر نشود که در این صورت الگوریتم بازگشت را انجام داده و به نقطه‌ی فعلی برمی‌گردد.
توجه داشته‌باشید که الگوریتم جستجوی محلی تکراری، با فرارهای متعدد، می‌تواند یک بخشِ دیگر از فضای حالت را اکتشاف کرده و در تله‌ی بهینه‌های محلی گیر نکند. اگر آن حالت جدید بهتر از حالت فعلی باشد، می‌توان حالت جدید را به عنوانِ نقطه‌ی مطلوب‌تر در نظر گرفت.
- ۱ » الگوریتم فراابتکاری (Meta Heuristic) و تفاوت آن با الگوریتم‌های عادی
- ۲ » منظور از بهینه محلی (Local Optimum) و بهینه سراسری (Global Optimum) چیست؟
- ۳ » الگوریتم‌های فراابتکاری (Meta Heuristic)، تابع برازش (Fitness Function) و چند مثال
- ۴ » ابعاد (Dimension) مسئله و فضای حالت در الگوریتم‌های بهینه‌سازی
- ۵ » الگوریتم ژنتیک (Genetic)
- ۶ » شبیه سازی تبرید (Simulated Annealing) و الگوریتم متروپولیس
- ۷ » الگوریتم جستجوی ممنوعه (Tabu Search)
- ۸ » الگوریتم بهینه‌سازی کلونی مورچگان (Ant Colony Optimization)
- ۹ » جستجوی محلی (Local Search) و الگوریتم تپه‌نوردی (Hill Climbing)
- ۱۰ » الگوریتم ممتیک (Memetic) بر اساس الگوهای رفتاری
- ۱۱ » الگوریتم‌های چند شروعی (Multi Start) در مسائل بهینه‌سازی
- ۱۲ » بهینه‌سازی سراسری (Global Optimization) و تفاوت آن با کاهش گرادیان (Gradient Descent)
- ۱۳ » جستجوی محلی تکراری (Iterated Local Search) در بهینه‌سازی
جالب بود. سپاس از اطلاعات تان.
سلام.پس چرا ادامه نمیدین؟
از سایت خوب تان ممنونم ! جالب بود !
بسیار عالی بود واقعا دستمریزاد جناب دکتر کاویانی عزیر بسیار متشکرم