الگوریتم Hill Climbing در روند بهینه یابی

در مقاله‌‌ پیشین از سری مقالات مرتبط با بهینه‌یابی به شرح و  بررسی «ورود به جهان الگوریتم‌های کاوشگر و بررسی Grid Search» پرداختیم در این مقاله به شرح و بررسی «الگوریتم Hill Climbing در روند بهینه‌یابی» می‌پردازیم.

– – –

در این مقاله در راستای آموزش بهینه‌یابی به توضیح یک الگوریتم بهینه‌یابی با نام Hill Climbing خواهیم پرداخت. این الگوریتم یک روش جستجوی محلی است. این به چه معناست؟ بدین معنا که الگوریتم در جهت مقدار فزاینده (در حال افزایش) حرکت کرده تا نهایتا قله‌ و یا به عبارت دیگر بهترین جواب را (بدون شک منظور ما از بهترین جواب، بهترین جواب با توجه به مقیاس و توان الگوریتم مورد استفاده است.) برای مسئله پیدا کند. پروسه بهینه‌یابی هنگامی که در محدوده قله قرار داریم و هیچ یک از همسایه‌ها دارای ارزش بالاتری نسبت به محل قرارگیری ما نیست پایان می‌یابد.

نقطه‌ی قوت این روش از گزینش آن است که می‌توانید تنها با استفاده از نمونه ی کوچکی از فضای بهینه‌یابی یک مجموعه بهینه از پارامترها را پیدا کنید.

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

در ادامه به بررسی سه نوع الگوریتم Hill Climbing خواهیم پرداخت :

1. الگوریتم Hill Climbing ساده
2. الگوریتم Hill Climbing بر اساس شیب صعودی
3. الگوریتم Hill Climbing بر اساس انتخاب رندوم

1. الگوریتم Hill Climbing ساده

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

برای فهم بهتر فرض کنید که ما دو ظرف با نام‌های حالت فعلی و حالت جدید در اختیار داریم که با توجه یه شرایط تبیین شده هر یک از عملگرها به این این ظرف‌ها اطلاق خواهند شد.

 

2. الگوریتم Hill Climbing بر اساس شیب صعودی

الگوریتم Hill Climbing بر اساس شیب صعودی یکی از انواع الگوریتم Hill Climbing ساده است. این الگوریتم تمامی گره‌ها در همسایگی حالت فعلی را بررسی کرده و نزدیک‌ترین گره به حالت هدف را انتخاب می‌کند. این الگوریتم با بررسی چندین گره زمان بیشتری مصرفی می‌کند.

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

3. الگوریتم Hill Climbing براساس انتخاب رندوم

الگوریتم Hill Climbing بر اساس انتخاب رندوم، تمامی گره‌ها در همسایگی خود را پیش از شروع حرکت مورد آزمایش قرار نمی‌دهد بلکه این نوع از الگوریتم یکی از همسایگان را به صورت رندوم انتخاب کرده و سپس برای اطلاق آن به ظرف حالت کنونی یا آزمایش گره دیگر تصمیم می‌گیرد.

همانطور که پیش از این نیز اذعان داشتیم باید بدانید که گرفتار شدن الگوریتم Hill Climbing در یک بهینه‌ محلی موضوع محتملی است.

با توجه به این که الگوریتم Hill Climbing هیچگاه در جهت مقداری کوچک‌تر حرکت نمی کند آن را الگوریتمی ناقص می‌دانیم و درصورتی که روندی رندوم را برای آن پیش بگیریم ممکن است که با یک الگوریتم کامل ولی ناکارآمد مواجه شویم.

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

– – –

در مقاله‌ی بعدی به بررسی «الگوریتم تبرید شبیه‌سازی شده» می‌پردازیم.