با مطالعه‌ی دورس گذشته از دوره‌ی جاری، مشاهده کردیم که الگوریتم‌های فراابتکاری برای این ساخته شده‌اند که بدون جستجوی همه‌ی حالات، بتوانند به یک حالت بهینه دست پیدا کنند.
با ابعاد مسئله و فضای حالت در درس مربوطه آشنایی پیدا کردید. پس اجازه بدهید مثال همان درس را ادامه بدهیم تا بتوانیم با کمک آن، مبحث الگوریتم‌های چند شروعی یا همان Multi Start را درک کنیم. شکل زیر را از آن درس به خاطر بیاورید:
در این شکل، ما با توجه به سه پیچِ تنظیم، به دنبال بیشینه کردن سرعت بودیم. اگر خاطرتان باشد، می‌خواستیم یک اتومبیل کنترلی را از راه دور با پیچ‌های تنظیم کنترل کرده و سرعت آن را در هر لحظه بیشینه کنیم. گفتیم هرکجا که صفحه قرمزتر شود به معنی سرعت بیشتر و هرکجا که صفحه آبی‌تر شود، به معنای سرعت کمتر است. پس بایستی آنقدر بگردیم (یعنی پیچ‌ها را نسبت به یکدیگر تنظیم کنیم) تا بتوانیم بیشترین سرعت را با توجه به ۳ بُعد (بُعدها متناظر با پیچ‌های تنظیم بودند) پیدا کنیم.
حالا فرض کنید در شکل بالا، مانند یک کوه‌نورد هستیم که می‌خواهیم بلندترین قله را پیدا کنیم. بلندترین قله یعنی همان بیشترین سرعت (بهینه‌ترین حالت در این مسئله). به صورت تصادفی یک نقطه را در فضا انتخاب می‌کنیم و با شروع از آن تا شعاع ۱۰۰متر این طرف و آن طرف آن را می‌گردیم. چیزی مانند شکل زیر:
طبیعتاً یک نقطه را پیدا می‌کنیم که بیشترین ارتفاع را در کوهستان – در میان نقاط جستجو شده در شعاع ۱۰۰ متری – دارد (قرمزتر از همه است). آن نقطه را یادداشت می‌کنیم ولی می‌دانیم که آن نقطه یک بهینه‌ی محلی (Local Optimum) است. یعنی اگر یک جای دیگر را بگردیم، احتمال دارد که نقاط بهینه‌تری نیز پیدا شود.
حال جستجو را رها کرده و کلاً به یک نقطه‌ی دیگر در فضای حالت می‌رویم. در واقع یک بار دیگر جستجو را در نقطه‌ی دیگر آغاز می‌کنیم. اگر دقت کرده باشید این کار یک نوع شروع دوبار چندگانه یا همان Multi Start است. شکل زیر را نگاه کنید، این بار جستجو با شعاع ۱۰۰ متر را از یک جای دیگر شروع می‌کنیم:
در واقع ما با شروع‌های مختلف از نقاط متفاوت، می‌توانیم به حد خوبی از اکتشاف (Exploration) در مسئله دست پیدا کنیم. این کار را آنقدر انجام می‌دهیم تا فضای حالت به حد خوبی از کشف برسد. البته این حد خوب بایستی توسط پیاده‌ساز و با توجه به مسئله و زمان مناسب برای حل آن تعیین شود.
بعد از آن‌که در هر بار شروع یک شعاع مشخص را گشتیم، می‌توانیم بیشترین ارتفاع (قرمز‌ترین رنگ) را در بین کل فضای جستجو شده مشخص کرده و آن را به عنوان بهترین حالت انتخاب کنیم. از دیدگاه پیاده‌سازی هم الگوریتم‌های چند شروعه (Multi Start) می‌توانند به صورت موازی پیاده‌سازی شوند. به این صورت که هر کدام از شروع‌ها توسط پردازنده‌ی جدا و به صورت موازی انجام شود و بعد از انجام جستجو هر کدام از آن‌ها، بهترین حالتی که پیدا کرده‌اند را با یکدیگر مقایسه می‌کنند و در نهایت بهترین حالت در میان تمامی شروع کننده‌ها پیدا می‌شود.
مشاهده کردید که این الگوریتم و تفکر حاکم بر آن بسیار ساده بودند. تفکر اصلی در این الگوریتم به این صورت است که بایستی بعد از مقداری جستجو، جستجو را رها کرده و به نقطه‌ی دیگری از فضای حالت برویم و جستجو را از آن نقطه شروع کنیم. با این کار یک واگرایی خوب در جستجو به وجود می‌آید و باعث می‌شود که از یک بهینه‌ی محلی خارج شده و بتوانیم راه‌حل‌های دیگر مسئله را نیز کشف کنیم.
- ۱ » الگوریتم فراابتکاری (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) در بهینه‌سازی