الگوریتم تپه نوردی — مفاهیم و کاربردهای آن + مثال و پیاده سازی

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

مقدمه

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

تپه نوردی به‌ویژه در حل مسائل بهینه‌سازی که در آن‌ها نیاز به یافتن مقدار بیشینه یا کمینه یک تابع وجود دارد، کاربرد دارد. ویژگی اصلی تپه نوردی این است که برخلاف روش‌های جستجوی کامل، نیازی به ذخیره‌سازی تمام مسیرهای جستجو ندارد، بنابراین از نظر حافظه کارآمد است. با این حال، این الگوریتم همیشه به جواب بهینه‌ی سراسری نمی‌رسد و ممکن است در بهینه‌های محلی (Local Optimum) گرفتار شود.

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

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

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

با این حال، این روش چالش‌هایی نیز دارد؛ ممکن است الگوریتم در یک ماکزیمم محلی (Local Maximum) گیر بیفتد، یعنی نقطه‌ای که نسبت به همسایگانش بهتر است اما بهترین حالت ممکن (ماکزیمم کلی) در فضای جستجو نیست.

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

• جستجوی محلی: تنها از اطلاعات مربوط به وضعیت فعلی و همسایگان آن استفاده می‌کند.
• روش حریصانه (Greedy): در هر مرحله، بهترین گزینه‌ی موجود را انتخاب می‌کند، بدون اینکه تضمینی برای رسیدن به بهینه‌ی سراسری داشته باشد.
• بدون بازگشت (No Backtracking): در حالت استاندارد، به مسیرهای قبلی بازنمی‌گردد، مگر اینکه تکنیک‌های بهبود مثل بازپرسازی تصادفی (Random Restart) استفاده شوند.
• حافظه‌ی کم: نیاز به ذخیره‌ی مسیرهای جستجو ندارد، بنابراین از نظر حافظه کارآمد است.

تفاوت الگوریتم تپه نوردی با سایر الگوریتم‌های جستجو

• عدم استفاده از حافظه‌ی اضافی: در مقایسه با الگوریتم‌های جستجوی درختی مانند جستجوی اول عمق (DFS) یا جستجوی اول سطح (BFS)، الگوریتم تپه نوردی هیچ درختی را ذخیره نمی‌کند و فقط وضعیت فعلی و همسایگان آن را در نظر می‌گیرد.
• تک‌جهته و بدون بازگشت: بر خلاف روش‌هایی مانند الگوریتم A* که امکان بازگشت به مسیرهای قبلی را دارد، تپه نوردی به عقب بازنمی‌گردد و تنها به جلو حرکت می‌کند.
• کارایی در مسائل بهینه‌سازی: برخلاف جستجوی کامل که تمامی مسیرها را بررسی می‌کند، تپه نوردی برای مسائل بهینه‌سازی مانند مسئله فروشنده دوره‌گرد (TSP) و طراحی شبکه‌های عصبی عملکرد مناسبی دارد.
• گیر افتادن در ماکزیمم‌های محلی: در حالی که روش‌هایی مانند شبیه‌سازی تبرید (Simulated Annealing) و الگوریتم ژنتیک (Genetic Algorithm) از حرکت‌های تصادفی و جهش‌های احتمالی برای فرار از بن‌بست‌ها استفاده می‌کنند، تپه نوردی به این قابلیت مجهز نیست و ممکن است در یک مقدار نامطلوب گیر بیفتد.

پاورپوینت الگوریتم شبیه ساز حرارتی SA

کلیک کنید

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

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

۱- ارزیابی وضعیت اولیه

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

۲- انتخاب بهترین وضعیت همسایه

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

سه نوع انتخاب همسایه در الگوریتم‌های مختلف تپه نوردی وجود دارد:

• الگوریتم تپه نوردی ساده (Simple Hill Climbing): اولین همسایه‌ای که مقدار بهتری داشته باشد، انتخاب می‌شود.
• الگوریتم تپه نوردی شیب تند (Steepest-Ascent Hill Climbing): تمامی همسایه‌ها بررسی شده و بهترین آن‌ها انتخاب می‌شود.
• الگوریتم تپه نوردی تصادفی (Stochastic Hill Climbing): یک همسایه به‌صورت تصادفی انتخاب شده و در صورت بهبود، پذیرفته می‌شود.

۳- جابجایی به وضعیت جدید

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

۴- تکرار فرآیند تا رسیدن به هدف یا مشکل

این مراحل تا زمانی که یکی از شرایط زیر رخ دهد، تکرار می‌شوند:

• رسیدن به مقدار مطلوب: مقدار تابع هدف به حدی بهینه رسیده که دیگر امکان بهبود وجود ندارد.
• رسیدن به بن‌بست (Local Maximum): در حالتی که هیچ همسایه‌ای مقدار بهتری ارائه ندهد.
• رسیدن به یک نقطه‌ی مسطح (Plateau): در این حالت تمامی همسایه‌ها مقدار یکسانی دارند و الگوریتم نمی‌تواند تصمیم بگیرد که به کدام سمت حرکت کند.
• افتادن در یک ناحیه‌ی شیب‌دار (Ridge): در این حالت، مسیر بهینه ممکن است به جهات مختلفی حرکت کند که بررسی آن سخت می‌شود.

برای غلبه بر این مشکلات، معمولاً تکنیک‌هایی مانند بازپرسازی تصادفی (Random Restart) یا حرکت تصادفی در نقاط مسطح به کار گرفته می‌شود.

پاورپوینت الگوریتم تپه نوردی — Hill climbing Algorithm

کلیک کنید

نمودار فضای حالت برای الگوریتم تپه نوردی

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

• در محور Y، تابعی قرار دارد که می‌تواند تابع هدف یا تابع هزینه باشد.
• در محور X، فضای حالت نمایش داده می‌شود.

اگر تابع روی محور Y یک تابع هزینه باشد، هدف جستجو یافتن کمینه‌ی سراسری (Global Minimum) و کمینه‌ی محلی (Local Minimum) خواهد بود.

اما اگر تابع روی محور Y یک تابع هدف باشد، هدف جستجو یافتن بیشینه‌ی سراسری (Global Maximum) و بیشینه‌ی محلی (Local Maximum) خواهد بود.

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

الگوریتم‌های تپه نوردی به‌عنوان یکی از روش‌های اصلی جستجو در مسائل بهینه‌سازی و حل مسائل پیچیده در هوش مصنوعی شناخته می‌شوند. این الگوریتم‌ها به‌طور کلی از رویکرد جستجوی محلی استفاده می‌کنند و در تلاشند تا با حرکت در فضای جستجو، به یک وضعیت بهینه دست یابند. در حالی که الگوریتم تپه نوردی ساده به‌عنوان یک روش پایه و ابتدایی برای جستجو در نظر گرفته می‌شود، نسخه‌های پیشرفته‌تری مانند تپه نوردی صعودی تند و تپه نوردی تصادفی با استفاده از تکنیک‌های پیچیده‌تر و با بررسی بیشتری از همسایگان، به دنبال یافتن نتایج بهینه‌تر هستند.

۱- الگوریتم تپه نوردی ساده (Simple Hill Climbing)

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

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

۲- الگوریتم تپه نوردی صعودی تند (Steepest-Ascent Hill Climbing)

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

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

۳- الگوریتم تپه نوردی تصادفی (Stochastic Hill Climbing)

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

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

پاورپوینت جست و جوی هیوریستیک (Heuristic Search)

کلیک کنید

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

الگوریتم تپه نوردی، علیرغم سادگی و کارایی در بسیاری از مسائل بهینه‌سازی، با چالش‌ها و محدودیت‌هایی مواجه است که می‌توانند نتایج نهایی را تحت تأثیر قرار دهند. از جمله مشکلات عمده این الگوریتم می‌توان به تله‌های محلی، شیب‌ها و فلات‌ها اشاره کرد. این مشکلات می‌توانند باعث شوند که الگوریتم از یافتن بهینه‌سازی جهانی (Global Maximum) باز بماند.

تله‌های محلی (Local Maximum)

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

شیب‌ها (Ridges)

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

فلات‌ها (Plateaus)

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

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

پیچیدگی زمانی و فضایی الگوریتم تپه نوردی

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

پیچیدگی زمانی در مسائل مختلف به مدت زمان مورد نیاز برای اجرای الگوریتم Hill Climbing بستگی دارد و می‌تواند چندجمله‌ای در مسائل ساده یا نمایی در مسائل پیچیده مانند NP-Complete باشد.

مسائل با فضای جستجوی محدود و یکنواخت

در بسیاری از مسائل، Hill Climbing می‌تواند در زمان چندجمله‌ای (Polynomial Time) به یک راه‌حل بهینه یا نزدیک به بهینه برسد. دلیل این امر این است که در برخی فضاهای جستجو، مسیر صعود یا نزول به سمت بهترین مقدار هموار بوده و بدون گیر افتادن در نقاط بهینه محلی، به هدف نهایی می‌رسد.

مسائل با چندین نقطه بهینه محلی

در حالتی که فضای جستجو دارای چندین بیشینه محلی (Local Maximum) یا کمینه محلی (Local Minimum) باشد، الگوریتم ممکن است در این نقاط متوقف شود و نتواند به جواب بهینه سراسری برسد. در این شرایط، نیاز به روش‌های کمکی مانند راه‌اندازی مجدد تصادفی (Random-Restart Hill Climbing) وجود دارد که با اجرای مجدد الگوریتم از نقاط تصادفی مختلف، احتمال رسیدن به جواب بهینه سراسری را افزایش می‌دهد.

مسائل NP-Complete

در مسائل NP-Complete، الگوریتم Hill Climbing ممکن است به دلیل وجود تعداد زیادی بیشینه محلی و فضای جستجوی بسیار پیچیده و غیرهموار، بهینه‌سازی را با پیچیدگی زمانی نمایی (Exponential Time) انجام دهد. این بدان معناست که در این مسائل، زمان مورد نیاز برای رسیدن به جواب بهینه می‌تواند به‌شدت افزایش یابد و در مواردی، پیدا کردن راه‌حل بهینه عملاً غیرممکن شود.

مزایا از نظر پیچیدگی

• پیچیدگی فضایی پایین، زیرا تنها یک حالت را در هر لحظه ذخیره می‌کند.
• در بسیاری از مسائل، زمان اجرا چندجمله‌ای است و سریع به نتیجه می‌رسد.
• روش Random-Restart می‌تواند در برخی موارد به بهینه‌سازی سراسری کمک کند.

معایب از نظر پیچیدگی

• در حضور چندین بیشینه محلی یا کمینه محلی، احتمال گیر افتادن در یک جواب غیربهینه وجود دارد.
• در مسائل NP-Complete، زمان محاسباتی ممکن است نمایی شود که کارایی الگوریتم را کاهش می‌دهد.
• در برخی فضاهای جستجو، وجود فلات‌ها (Flat Regions) یا سراشیبی‌های ملایم ممکن است باعث توقف زودهنگام الگوریتم شود.

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

الگوریتم Hill Climbing می‌تواند برای حل بسیاری از مسائل استفاده شود، به‌ویژه در مواردی که ارزیابی حالت فعلی با دقت بالا ممکن باشد. از جمله این مسائل می‌توان به جریان شبکه (Network-Flow)، مسئله فروشنده دوره‌گرد (Travelling Salesman Problem)، مسئله ۸ وزیر (۸-Queens Problem)، طراحی مدارهای مجتمع (Integrated Circuit Design) و غیره اشاره کرد.

همچنین، این الگوریتم در یادگیری القایی (Inductive Learning) مورد استفاده قرار می‌گیرد. در رباتیک نیز از Hill Climbing برای هماهنگی بین چندین ربات در یک تیم استفاده می‌شود. علاوه بر این، در بسیاری از مسائل دیگر نیز این روش کاربرد دارد.

پاورپوینت مسئله هشت وزیر — Eight queens Problem

کلیک کنید

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

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

پیاده‌سازی الگوریتم

در ادامه پیاده سازی این مثال با استفاده از الگوریتم تپه نوردی در چند زبان برنامه نویسی مهم آورده شده است.

پیاده سازی مسئله فروشنده دوره گرد با الگوریتم تپه نوردی در زبان پایتون

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

import random
# Distance matrix representing distances between cities
# Replace this with the actual distance matrix for your problem
distance_matrix = [
    [۰, ۱۰, ۱۵, ۲۰],
    [۱۰, ۰, ۳۵, ۲۵],
    [۱۵, ۳۵, ۰, ۳۰],
    [۲۰, ۲۵, ۳۰, ۰]
]
def total_distance(path):
    # Calculate the total distance traveled in the given path
    total = 0
    for i in range(len(path) - 1):
        total += distance_matrix[path[i]][path[i+1]]
    total += distance_matrix[path[-1]][path[0]]  # Return to starting city
    return total
def hill_climbing_tsp(num_cities, max_iterations=10000):
    current_path = list(range(num_cities))  # Initial solution, visiting cities in order
    current_distance = total_distance(current_path) 
    for _ in range(max_iterations):
        # Generate a neighboring solution by swapping two random cities
        neighbor_path = current_path.copy()
        i, j = random.sample(range(num_cities), 2)
        neighbor_path[i], neighbor_path[j] = neighbor_path[j], neighbor_path[i]
        neighbor_distance = total_distance(neighbor_path)
        
        # If the neighbor solution is better, move to it
        if neighbor_distance < current_distance:
            current_path = neighbor_path
            current_distance = neighbor_distance
    return current_path
def main():
    num_cities = 4  # Number of cities in the TSP
    solution = hill_climbing_tsp(num_cities)
    print("Optimal path:", solution)
    print("Total distance:", total_distance(solution))
if __name__ == "__main__":
    main()

پیاده سازی مسئله فروشنده دوره گرد با الگوریتم تپه نوردی در زبان سی پلاس پلاس

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
#define NUM_CITIES 4
// Distance matrix representing distances between cities
// Replace this with the actual distance matrix for your problem
int distance_matrix[NUM_CITIES][NUM_CITIES] = {
   {۰, ۱۰, ۱۵, ۲۰},
   {۱۰, ۰, ۳۵, ۲۵},
   {۱۵, ۳۵, ۰, ۳۰},
   {۲۰, ۲۵, ۳۰, ۰}
};
int total_distance(const std::vector<int>& path) {
   // Calculate the total distance traveled in the given path
   int total = 0;
   for (size_t i = 0; i < path.size() - 1; i++) {
       total += distance_matrix[path[i]][path[i + 1]];
   }
   total += distance_matrix[path.back()][path[0]]; // Return to starting city
   return total;
}
void hill_climbing_tsp(int num_cities, int max_iterations) {
   vector<int> current_path(num_cities); // Initial solution, visiting cities in order
   for (int i = 0; i < num_cities; i++) {
      current_path[i] = i;
   }
   int current_distance = total_distance(current_path);
   for (int it = 0; it < max_iterations; it++) {
      // Generate a neighboring solution by swapping two random cities
      std::vector<int> neighbor_path = current_path;
      int i = rand() % num_cities;
      int j = rand() % num_cities;
      swap(neighbor_path[i], neighbor_path[j]);
      int neighbor_distance = total_distance(neighbor_path);
      // If the neighbor solution is better, move to it
      if (neighbor_distance < current_distance) {
         current_path = neighbor_path;
         current_distance = neighbor_distance;
      }
   }
   cout << "Optimal path: ";
   for (int city : current_path) {
      cout << city << " ";
   }
   cout << endl;
   cout << "Total distance: " << current_distance << endl;
}
int main() {
   srand(time(NULL));
   int max_iterations = 10000;
   hill_climbing_tsp(NUM_CITIES, max_iterations);
   return 0;
}

پیاده سازی مسئله فروشنده دوره گرد با الگوریتم تپه نوردی در زبان جاوا

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

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class HillClimbingTSP {
   private static final int NUM_CITIES = 4;
   // Distance matrix representing distances between cities
   // Replace this with the actual distance matrix for your problem
   private static final int[][] distanceMatrix = {
      {۰, ۱۰, ۱۵, ۲۰},
      {۱۰, ۰, ۳۵, ۲۵},
      {۱۵, ۳۵, ۰, ۳۰},
      {۲۰, ۲۵, ۳۰, ۰}
   };
   private static int totalDistance(List<Integer> path) {
      // Calculate the total distance traveled in the given path
      int total = 0;
      for (int i = 0; i < path.size() - 1; i++) {
         total += distanceMatrix[path.get(i)][path.get(i + 1)];
      }
      total += distanceMatrix[path.get(path.size() - 1)][path.get(0)]; // Return to starting city
      return total;
   }
   private static List<Integer> generateRandomPath(int numCities) {
      List<Integer> path = new ArrayList<>();
      for (int i = 0; i < numCities; i++) {
         path.add(i);
      }
      Random rand = new Random();
      for (int i = numCities - 1; i > 0; i--) {
         int j = rand.nextInt(i + 1);
         int temp = path.get(i);
         path.set(i, path.get(j));
         path.set(j, temp);
      }
      return path;
   }
   public static void hillClimbingTSP(int numCities, int maxIterations) {
      List<Integer> currentPath = generateRandomPath(numCities); // Initial solution
      int currentDistance = totalDistance(currentPath);
      for (int it = 0; it < maxIterations; it++) {
         // Generate a neighboring solution by swapping two random cities
         List<Integer> neighborPath = new ArrayList<>(currentPath);
         int i = new Random().nextInt(numCities);
         int j = new Random().nextInt(numCities);
         int temp = neighborPath.get(i);
         neighborPath.set(i, neighborPath.get(j));
         neighborPath.set(j, temp);
         int neighborDistance = totalDistance(neighborPath);
         // If the neighbor solution is better, move to it
         if (neighborDistance < currentDistance) {
            currentPath = neighborPath;
            currentDistance = neighborDistance;
         }
      }
      System.out.print("Optimal path: ");
      for (int city : currentPath) {
         System.out.print(city + " ");
      }
      System.out.println();
      System.out.println("Total distance: " + currentDistance);
   }
   public static void main(String[] args) {
      int maxIterations = 10000;
      hillClimbingTSP(NUM_CITIES, maxIterations);
   }
}

خروجی مثال

اگر هیچ محدودیتی برای مقدار تصادفی وجود نداشته باشد، این احتمال وجود دارد که در هر اجرا ترتیب انتخاب‌ها متفاوت باشد، به این ترتیب خروجی‌ها مختلف خواهند بود. خروجی در اولین اجرای الگوریتم:

Optimal path: [0, 1, 3, 2]
Total distance: 80

نتیجه گیری

الگوریتم تپه نوردی به دلیل سادگی در پیاده‌سازی و کارایی در بسیاری از مسائل بهینه‌سازی، از محبوبیت زیادی برخوردار است. با این حال، محدودیت‌هایی همچون گیر افتادن در تله‌های محلی (Local Maxima) و عدم تضمین رسیدن به بهینه‌سازی جهانی (Global Optimum) وجود دارد.

در مواردی که فضای جستجو پیچیده و پر از تله‌های محلی یا فلات‌ها باشد، الگوریتم تپه نوردی ممکن است نتایج suboptimal یا ناکافی تولید کند. بنابراین، استفاده از تکنیک‌های تکمیلی مانند الگوریتم‌های تصادفی، الگوریتم‌های ترکیبی یا بازگشتی می‌تواند کارایی الگوریتم تپه نوردی را افزایش دهد.

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