الگوریتم‌های جستجو و استدلال در هوش مصنوعی: جستجوی محلی - پرسش و پاسخ

پرسش:

مفهوم جستجوی محلی (Local Search) در هوش مصنوعی چیست و چه تفاوتی با جستجوی سراسری (Global Search) دارد؟

پاسخ:

جستجوی محلی یک استراتژی حل مسئله در هوش مصنوعی است که با یک راه حل اولیه شروع کرده و به طور تکراری به سمت راه حل های همسایه که کیفیت بهتری دارند، حرکت می کند. این الگوریتم ها معمولاً به دنبال بهبود راه حل فعلی هستند و نیازی به نگهداری کل فضای جستجو ندارند. در مقابل، جستجوی سراسری تمام فضای ممکن برای یافتن راه حل بهینه را کاوش می کند و اغلب به حافظه و توان محاسباتی بیشتری نیاز دارد. جستجوی محلی ممکن است در بهینه های محلی گیر کند، در حالی که جستجوی سراسری تضمین می کند که راه حل بهینه سراسری یافت شود (در صورت وجود و کامل بودن الگوریتم).

پرسش:

الگوریتم کوهنوردی (Hill Climbing) چگونه کار می کند و چه محدودیت هایی دارد؟

پاسخ:

الگوریتم کوهنوردی یک الگوریتم جستجوی محلی است که در هر مرحله، وضعیت فعلی را با وضعیت های همسایه مقایسه کرده و به سمت وضعیتی حرکت می کند که تابع هدف (یا هزینه) آن بهتر باشد. این الگوریتم تا زمانی ادامه می یابد که هیچ همسایه ای بهتر از وضعیت فعلی وجود نداشته باشد. محدودیت اصلی آن این است که می تواند در بهینه های محلی (local optima) گیر کند، یعنی ممکن است به راه حلی برسد که در همسایگی خود بهترین است، اما راه حل کلی بهینه نباشد. هم چنین، در صورت وجود فلات ها (plateaus) در تابع هدف، ممکن است پیشرفتی نداشته باشد.

پرسش:

الگوریتم شبیه سازی تبرید (Simulated Annealing) چگونه از ایده های فیزیک برای غلبه بر بهینه های محلی استفاده می کند؟

پاسخ:

شبیه سازی تبرید از فرآیند سرد کردن فلزات در فیزیک الهام گرفته شده است. این الگوریتم در ابتدا با احتمال بالایی به سمت راه حل های بدتر نیز حرکت می کند (مشابه زمانی که فلز داغ است و اتم ها آزادانه تر حرکت می کنند). با گذشت زمان و کاهش 'دما' (که یک پارامتر کنترلی است)، احتمال پذیرش راه حل های بدتر به تدریج کاهش می یابد. این امکان حرکت اولیه به سمت نواحی مختلف فضای جستجو را فراهم می کند و شانس فرار از بهینه های محلی را افزایش می دهد.

پرسش:

مفهوم 'دما' (Temperature) در الگوریتم شبیه سازی تبرید چیست و چگونه بر رفتار الگوریتم تأثیر می گذارد؟

پاسخ:

در شبیه سازی تبرید، 'دما' یک پارامتر شبیه سازی شده است که میزان احتمال پذیرش یک راه حل بدتر را کنترل می کند. در دما های بالا، الگوریتم احتمال بیشتری برای پذیرش راه حل هایی دارد که کیفیت شان از راه حل فعلی کمتر است. این به الگوریتم اجازه می دهد تا از بهینه های محلی فرار کند و فضای جستجو را بهتر کاوش کند. با کاهش دما در طول زمان (فرآیند خنک سازی)، احتمال پذیرش راه حل های بدتر کاهش می یابد و الگوریتم به تدریج به سمت بهینه های محلی همگرا می شود.

پرسش:

الگوریتم جستجوی تابو (Tabu Search) چیست و چگونه از 'لیست تابو' (Tabu List) برای جلوگیری از دور زدن استفاده می کند؟

پاسخ:

جستجوی تابو یک الگوریتم جستجوی محلی است که با نگهداری لیستی از حرکات یا وضعیت های 'تابو' (ممنوعه) از بازگشت به وضعیت های قبلی جلوگیری می کند. این لیست تابو به الگوریتم اجازه می دهد تا از دور زدن در مسیر های تکراری خودداری کند و فضا های جدیدی از جستجو را کشف کند. وقتی الگوریتم حرکتی را انجام می دهد، آن حرکت یا وضعیت حاصله برای مدتی در لیست تابو قرار می گیرد و تا زمانی که از لیست حذف نشود، توسط الگوریتم مجدداً انتخاب نخواهد شد.

پرسش:

چگونه جستجوی تابو می تواند از بهینه های محلی فرار کند؟

پاسخ:

جستجوی تابو با استفاده از لیست تابو، حتی اگر بهترین حرکت بعدی منجر به وضعیت بدتری شود، آن حرکت را انجام می دهد (به شرطی که حرکت تابو نباشد). این قابلیت پذیرش حرکات رو به عقب یا حرکات با بهبود کم، به الگوریتم اجازه می دهد تا از بهینه های محلی که ممکن است در آن ها گیر کند، خارج شود و به کاوش در سایر نواحی فضای جستجو ادامه دهد.

پرسش:

الگوریتم ژنتیک (Genetic Algorithm) چگونه با الهام از تکامل طبیعی، مسائل جستجو را حل می کند؟

پاسخ:

الگوریتم ژنتیک یک الگوریتم جستجوی محلی مبتنی بر جمعیت است که از اصول انتخاب طبیعی، جهش و ترکیب (crossover) الهام گرفته است. در این الگوریتم، یک جمعیت از راه حل های ممکن (کروموزوم ها) نگهداری می شود. در هر نسل، راه حل های بهتر (برازنده تر) برای تولید نسل بعدی انتخاب می شوند. عملیات ترکیب، دو راه حل والد را ترکیب کرده و راه حل های فرزند جدیدی ایجاد می کند، در حالی که جهش، تغییرات تصادفی کوچکی را در راه حل ها ایجاد می کند. این فرآیند به تدریج به سمت راه حل های بهینه تر همگرا می شود.

پرسش:

نقش عملگر های ترکیب (Crossover) و جهش (Mutation) در الگوریتم ژنتیک چیست؟

پاسخ:

عملگر ترکیب (Crossover) با ترکیب بخش هایی از دو راه حل والد، راه حل های فرزند جدیدی ایجاد می کند که ویژگی های هر دو والد را به ارث می برند. این عملگر به کاوش در فضای جستجو و یافتن ترکیب های خوب از ویژگی های راه حل ها کمک می کند. عملگر جهش (Mutation) تغییرات تصادفی کوچکی را در ژن های یک راه حل ایجاد می کند. این عملگر برای حفظ تنوع ژنتیکی در جمعیت و جلوگیری از همگرایی زودرس به بهینه های محلی ضروری است و به الگوریتم اجازه می دهد تا نواحی جدیدی از فضای جستجو را کشف کند.