الگوریتم تپه نوردی و بهینه سازی آن

الگوریتم تپه نوردی

الگوریتم تپه نوردی، یک الگوریتم جستجوی ابتکاری (اکتشافی یا هیوریستیک) است که برای مسائل بهینه سازی در زمینه هوش مصنوعی استفاده می شود.
با توجه به مجموعه بزرگی از ورودی ها و یک تابع ابتکاری (هیوریستیک) خوب، سعی می کند یک راه حل مناسب برای مسائل پیدا کند. این راه حل ممکن است راه حل بهینه سراسری نباشد.

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

ویژگی های تپه نوردی

1. نوع الگوریتم تولید و آزمایش: نوعی الگوریتم تولید و آزمایش است.

الگوریتم تولید و تست به شرح زیر است:

1. راه حل های ممکن را ایجاد کن.
2. تست کنید تا ببینید آیا این راه حل مورد انتظار است یا خیر.
3. اگر راه حل پیدا شده است،خارج شو در غیر اینصورت به مرحله 1 برو.

2. از رویکرد حریصانه استفاده می کند: در هر نقطه از فضای حالت، جستجو در آن جهت حرکت می کند که هزینه عملکرد را با امید به یافتن راه حل بهینه، در پایان بهبود می دهد.

انواع تپه نوردی

1- الگوریتم تپه نوردی ساده

گره های همسایه را یکی یکی بررسی می کند و اولین گره همسایه را انتخاب می کند که هزینه جاری را به عنوان گره بعدی بهینه می کند.

الگوریتم تپه نوردی ساده:

مرحله 1: وضعیت اولیه را ارزیابی کنید، اگر حالت هدف است، موفقیت را برگردانید و توقف کنید.
مرحله 2: ادامه حلقه تا زمانی که راه حلی پیدا شود یا اپراتور جدیدی برای اعمال باقی نماند.
مرحله 3: یک اپراتور را در وضعیت فعلی انتخاب و اعمال کنید.
مرحله 4: وضعیت جدید را بررسی کنید:
الف) اگر حالت هدف است، پس موفقیت را برگردانید و ترک کنید.
ب) در غیر این صورت اگر بهتر از وضعیت فعلی است، وضعیت جدید را به عنوان وضعیت فعلی اختصاص دهید.
ج) در غیر این صورت، اگر بهتر از وضعیت فعلی نیست، به مرحله 2 بازگردید.
مرحله 5: خروج

2- الگوریتم تپه نوردی Steepest-Ascent

الگوریتم شیب دارترین صعود یا Steepest-Ascent، نوعی از الگوریتم ساده تپه نوردی است. این الگوریتم تمام گره های همسایه حالت فعلی را بررسی می کند و یک گره همسایه را که نزدیک ترین گره به حالت هدف است انتخاب می کند. این الگوریتم زمانی که چندین همسایه را جستجو می کند، زمان بیشتری مصرف می کند

الگوریتم تپه‌نوردی با شیب‌ترین صعود:
مرحله 1: وضعیت اولیه را ارزیابی کنید، اگر حالت هدف است، موفقیت را برگردانید و توقف کنید، در غیر این صورت وضعیت فعلی را به عنوان حالت اولیه در آورید.
مرحله 2: حلقه بزنید تا راه حلی پیدا شود یا وضعیت فعلی تغییر نکند.
الف) حالت بعدی حالتی خواهد بود که از همه همسایه ها بهتر باشد.
ب) برای هر اپراتور که برای وضعیت فعلی اعمال می شود:
الف) اپراتور جدید را اعمال کنید و یک حالت جدید ایجاد کنید.
ب) وضعیت جدید را ارزیابی کنید.
ج) اگر حالت هدف است، آن را برگردانید و از آن خارج شوید، در غیر این صورت آن را با SUCC مقایسه کنید.
د) اگر از SUCC بهتر است، وضعیت جدید را به عنوان SUCC تنظیم کنید.
و) اگر SUCC بهتر از وضعیت فعلی است، وضعیت فعلی را روی SUCC تنظیم کنید.
مرحله 5: خروج

3- تپه نوردی تصادفی:

تپه‌نوردی تصادفی قبل از حرکت، همه همسایگان خود را بررسی نمی‌کند. در عوض، این الگوریتم جستجو یک گره همسایه را به صورت تصادفی انتخاب می کند و تصمیم می گیرد که آن را به عنوان وضعیت فعلی انتخاب کند یا وضعیت دیگری را بررسی کند.

مشکلات الگوریتم تپه نوردی

1. بهینه محلی: بهینه محلی یک حالت بهینه است که نسبت به همسایه های نزدیک خود بهینه است اما بهینه سراسری نیست.

راه حل: تکنیک عقبگرد می تواند راه حلی برای حداکثر محلی در منظر فضای حالت باشد. فهرستی از مسیر امیدوارکننده ایجاد کنید تا الگوریتم بتواند فضای جستجو را پس بگیرد و مسیرهای دیگر را نیز کشف کند.

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

راه حل: راه حل فلات برداشتن گام های بزرگ یا گام های بسیار کوچک در حین جستجو برای حل مشکل است. به طور تصادفی حالتی را انتخاب کنید که از حالت فعلی فاصله زیادی دارد، بنابراین ممکن است الگوریتم بتواند منطقه غیر فلات را پیدا کند.

3. برآمدگی ها: برآمدگی شکل خاصی از حداکثر محلی است. منطقه ای دارد که بالاتر از مناطق اطرافش است، اما خودش شیب دارد و با یک حرکت نمی توان به آن رسید.

راه حل: با استفاده از جستجوی دوطرفه یا با حرکت در جهات مختلف می توان این مشکل را بهبود بخشید.