جستجوی محلی پرتو Local Beam Search

جستجوی پرتو یا Beam Search نوعی جستجوی فرامکاشفه‌ای (Metaheuristic) است که از ترکیب جستجوی معروف اول بهترین (Best First Search) به عنوان نماینده روشهای حریصانه، و استراتژی بررسی همسایگی تشکیل شده است.
روند شروع کار در جستجوی پرتو، برخلاف روش BFS به صورت حریصانه (Greedy) نیست، بلکه با الگوگیری از الگوریتم تپه‌نوردی (Hill Climbing) از نقاط تصادفی شروع می‌کند.
الگوریتم:
  1. محاسبه K پاسخ تصادفی
  2. اجرای جستجوی محلی بر روی تک تک آنها و محاسبه چند پاسخ همسایه برای هر کدام
  3. ارزیابی پاسخهای همسایه با استفاده از تابع هدف
  4. نگهداری K پاسخ بهینه‌تر و جایگزینی آنها با پاسخهای قبلی
  5. تکرار مراحل 2 تا 4، تا زمان تحقق شرط خاتمه
کاملا مشخص است که این روش، با K جستجوی محلی موازی تفاوت دارد. انتخاب K پاسخ بهینه‌تر از بین تمام پاسخهای همسایه تولید شده، از شبیه شدن پاسخها به یکدیگر جلوگیری می‌کند.
همچنین این امکان نیز وجود دارد که به منظور جلوگیری از همگرایی زودرس، با ایجاد تغییری جزئی در مرحله 4، از قوانین احتمال استفاده نموده و K پاسخ با احتمال بیشتر را انتخاب کنیم.
اگر با الگوریتم ژنتیک آشنا باشید، متوجه خواهید شد که GA هم از روش مشابهی استفاده می‌کند. (پاسخهای اولیه تصادفی، ایجاد همسایگی با ترکیب و جهش و انتخاب بر اساس قوانین احتمال)
در واقع با اضافه نمودن شاخ و برگی مانند ترکیب و جهش در روند ایجاد همسایگی و نخبه‌گرایی در روند انتخاب K پاسخ ثانویه، جستجوی پرتو تقریبا به الگوریتم ژنتیک تبدیل می‌شود.
در واقع جستجوی پرتو دارای مصرف حافظه کمتر، سرعت بیشتر و در عین حال دقت کمتری نسبت به الگوریتم ژنتیک است.

About محمد شمس

برنامه‌نویس، طراح انیمیشن و علاقمند به هوش مصنوعی

One Comment

  1. سلام
    مقایسه جالبی کردین با الگوریتم ژنتیک. الگوریتم جالبی است.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


7 × = 14