در این مقاله به توضیح یک الگوریتم بهینهیابی با نام Hill Climbing خواهیم پرداخت. این الگوریتم یک روش جستجوی محلی است . این به چه معناست؟ بدین معنا که الگوریتم در جهت مقدار فزاینده (در حال افزایش) حرکت کرده تا نهایتا قله و یا به عبارت دیگر بهترین جواب را (بدون شک منظور ما از بهترین جواب، بهترین جواب با توجه به مقیاس و توان الگوریتم مورد استفاده است.) برای مسئله پیدا کند. پروسه ی بهینهیابی هنگامی که در محدوده ی قله قرار داریم و هیچ یک از همسایه ها دارای ارزش بالا تری نسبت به محل قرارگیری ما نیست پایان مییابد.
نقطهی قوت این روش از گزینش آن است که میتوانید تنها با استفاده از نمونه ی کوچکی از فضای بهینهیابی یک مجموعه ی بهینه از پارامتر ها را پیدا کنید.نقطه ی ضعف و ریسک این روش بهینهیابی عدم قطعیت آن در تعیین بهترین جواب مطلق است این به چه معنیست؟ این احتمال وجود دارد که الگوریتم در دام یک نقطهی بهینه ی محلی گرفتار شود. پاسخی که از طریق این الگوریتم بهینه یابی به دست خواهید آورد به طور قطع با توجه به نقطهی شروع و همسایگی آن بهترین جواب ممکن است ولی تضمینی وجود ندارد که بهترین جواب تمام داده یا به عبارتی بهترین جواب مطلق باشد.
در ادامه به بررسی سه نوع الگوریتم Hill Climbing خواهیم پرداخت :
الگوریتم Hill Climbing ساده
الگوریتم Hill Climbing بر اساس شیب صعودی
الگوریتم Hill Climbing بر اساس انتخاب رندوم
الگوریتم Hill Climbing – تپه نوردی 02
1. الگوریتم Hill Climbing ساده
گام 1 : سنجش حالت آغازین ، آیا این حالت، حالت هدف است؟ در این صورت موفقیت حاصل شده و الگوریتم متوقف خواهد شد.
گام 2 : لوپ تا پیدا شدن پاسخ مورد نظر یا اتمام عملگر ها ادامه خواهد داشت.
گام 3 : اضافه کردن یک عملگر به حالت کنونی
گام 4 : چک کردن حالت جدید :
در صورتی که حالت جدید، حالت هدف باشد عملیات متوقف میشود.
در صورتی که از حالت فعلی بهتر باشد حالت جدید به حالت فعلی تغییر پیدا خواهد کرد.
در صورتی که حالت جدید از حالت فعلی بهتر نباشد به گام 2 باز خواهیم گشت.
برای فهم بهتر فرض کنید که ما دو ظرف با نام های حالت فعلی و حالت جدید در اختیار داریم که با توجه یه شرایط تبیین شده هر یک از عملگر ها به این این ظرف ها اطلاق خواهند شد.
2. الگوریتم Hill Climbing بر اساس شیب صعودی
الگوریتم Hill Climbing بر اساس شیب صعودی یکی از انواع الگوریتم Hill Climbing ساده است. این الگوریتم تمامی گره ها در همسایگی حالت فعلی را بررسی کرده و نزدیک ترین گره به حالت هدف را انتخاب میکند. این الگوریتم با بررسی چندین گره زمان بیشتری مصرفی میکند.
گام 1 : سنجش حالت آغازین، آیا این حالت، حالت هدف است؟ در این صورت موفقیت حاصل شده و الگوریتم متوقف خواهد شد. در غیر این صورت حالت آغازین تبدیل به حالت فعلی خواهد شد.
گام 2 : ادامه ی لوپ تا زمانی که پاسخ به دست آمده و یا حالت کنونی دیگر تغییر نکند.
گام 3 : خروج.
3. الگوریتم Hill Climbing براساس انتخاب رندوم
الگوریتم Hill Climbing بر اساس انتخاب رندوم، تمامی گره ها در همسایگی خود را پیش از شروع حرکت مورد آزمایش قرار نمیدهد بلکه این نوع از الگوریتم یکی از همسایگان را به صورت رندوم انتخاب کرده و سپس برای اطلاق آن به ظرف حالت کنونی یا آزمایش گره دیگر تصمیم میگیرد.
همانطور که پیش از این نیز اذعان داشتیم باید بدانید که گرفتار شدن الگوریتم Hill Climbing در یک بهینهی محلی موضوع محتملی است.
با توجه به این که الگوریتم Hill Climbing هیچگاه در جهت مقداری کوچک تر حرکت نمی کند آن را الگوریتمی ناقص میدانیم و درصورتی که روندی رندوم را برای آن پیش بگیریم ممکن است که با یک الگوریتم کامل ولی ناکارآمد مواجه شویم.
در مقاله های بعدی به توضیح الگوریتم هایی خواهیم پرداخت که کامل و جامع و کارآمد هستند .