این درس به نوعی تکرار درس بهینه محلی و بهینه سراسری است و برای تاکید و درک بهتر با عنوانی دیگر و توضیحاتی دیگر در اینجا تکرار شده است. شاید نتوان این دسته از الگوریتم‌ها را به صورت جداگانه، یک الگوریتم فراابتکاری (Meta heuristic) قوی دانست. اما شناخت این الگوریتم‌ها می‌تواند به وسعت دید در درکِ بحثِ بهینه‌سازی کمک کرده و پایه‌ی الگوریتم‌های بعدی و پیشرفته‌تر باشد.
الگوریتم تپه‌نوردی بسیار ساده است. حتماً درس بهینه محلی و بهینه سراسری را خوانده‌اید و مثال آن را در ذهن دارید. اگر شکل آن درس را به خاطر بیاورید چیزی مانند شکل زیر بود:
در اینجا ما می‌خواستیم به مرتفع‌ترین کوه (بهینه‌ترین نقطه در فضای حالت) دست پیدا کنیم. حال فرض کنید، می‌خواهیم با کمک تپه‌نوردی این مسئله را حل کرده و به بهترین نقطه در فضا (یعنی همان مرتفع‌ترین کوه) برسیم. این الگوریتم به این صورت عمل می‌کند که ابتدا یک نقطه تصادفی در فضا انتخاب می‌کنیم. مثلاً در شکلِ بالا، نقطه‌ی ۴ در ابتدا برای مسئله به صورت تصادفی تعیین شده است. حال الگوریتم تپه‌نوردی به صورت محلی جستجو می‌کند (یعنی کمی این‌طرف و آن‌طرف‌تر از خود را جستجو می‌کند) و سعی می‌کند خود را به یک مکانِ بهتر برساند. این کار را آنقدر تکرار می‌کند تا به یک بهینه‌ی محلی در اطراف خود برسد (یعنی قله‌ای که از اطرافش بالاتر باشد). درشکلِ بالا، این تلاش را انجام می‌دهد و به نقطه‌ی شماره ۶ می‌رسد.
همان‌طور که می‌بینید، الگوریتم تپه‌نوردی (Hill Climbing) با جستجوی محلی (Local Search) توانست به سادگی به یک بهینه در اطراف خود برسد و مشخص است که این بهینه، بهترین بهینه‌ی ممکن نیست. در واقع الگوریتم تپه‌نوردی اکتشاف (exploration) کمی داشته است. به همین دلیل نتوانسته خوب حالات و فضاهای مختلف را تست کند و بهترین نتیجه ممکن را به دست آورد. البته اینجا شانس آوردیم که نقطه‌ی ۴ به عنوان نقطه‌ی ابتدایی انتخاب شد. مثلاً اگر نقطه‌ی ۲ به عنوان نقطه‌ی ابتدایی انتخاب می‌شد وضعیت به مراتب بدتر می‌شد.
در واقع الگوریتمِ تپه‌نوردی مانند این است که ابتدا یک راه‌حل برای مسئله پیدا کنیم، سپس با تغییرات کم در این راه‌حل (پیدا کردن همسایه‌ها – همان‌کاری که در الگوریتم جستجوی ممنوعه انجام دادیم)، به دنبال بهبود آن به صورت محلی باشیم و این‌کار را تا زمانی ادامه دهیم که الگوریتم در یک حالت بهینه محلی (نسبت به حالات همسایه‌ی خود) قرار بگیرد.
- ۱ » الگوریتم فراابتکاری (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) در بهینه‌سازی
سلام ببخشید جستجوی محلی در اینجا یعنی چی؟
با سلام
جستجوی محلی یعنی جستجو در یک منطقه‌ی خاص از الگوریتم. یعنی پارامترها را خیلی بالا و پایین نمی‌کنیم و با تغییر کم پارامترها سعی می‌کنیم جستجو را انجام دهیم