Python实战开发及案例分析（25）—— 爬山算法

        爬山算法（Hill Climbing）是一种启发式搜索算法，常用于解决优化问题。它的核心思想是从一个初始解开始，不断朝着增益最大的方向移动，直到达到局部最优解。

实现步骤

  1. 从初始解开始。
  2. 在当前解的邻域中找到一个更好的解。
  3. 如果找到的解比当前解好，则移动到该解，并重复步骤2。
  4. 如果在邻域中没有找到更好的解，则算法终止，返回当前解。

代码示例

        以下示例展示了如何使用爬山算法求解一个简单的函数优化问题。目标是找到使函数值最大的输入值。

示例问题：最大化函数f\left ( x \right )=-\left ( x-3 \right )^2+10
import random

def hill_climbing(f, x0, step_size=0.1, max_iterations=1000):
    current_x = x0
    current_f = f(current_x)
    
    for i in range(max_iterations):
        neighbors = [current_x + step_size, current_x - step_size]
        next_x = max(neighbors, key=f)
        next_f = f(next_x)
        
        if next_f <= current_f:
            break
        
        current_x, current_f = next_x, next_f
    
    return current_x, current_f

# 定义目标函数
def objective_function(x):
    return -(x - 3) ** 2 + 10

# 初始解
initial_solution = random.uniform(-10, 10)

# 执行爬山算法
solution, solution_value = hill_climbing(objective_function, initial_solution)

print(f"Optimal solution: x = {solution:.4f}")
print(f"Optimal value: f(x) = {solution_value:.4f}")

案例分析

        在这个案例中，我们定义了一个简单的目标函数f\left ( x \right )=-\left ( x-3 \right )^2+10 ，其最大值出现在 𝑥=3 处。爬山算法从随机初始解开始，通过在邻域中寻找更优解，不断更新当前解，直到达到局部最优解。输出显示了算法找到的最优解及其对应的函数值。

解释与改进

        爬山算法的一个主要缺点是它容易陷入局部最优解。为了改进这一点，可以使用以下几种方法：

  1. 随机重启爬山算法（Random Restart Hill Climbing）：多次运行爬山算法，每次从不同的随机初始解开始，最后选择最佳结果。
  2. 模拟退火算法（Simulated Annealing）：在搜索过程中偶尔接受较差的解，以跳出局部最优解。
  3. 爬山算法与其他启发式搜索算法结合：例如与遗传算法（Genetic Algorithm）结合，利用全局搜索能力。
随机重启爬山算法示例
def random_restart_hill_climbing(f, num_restarts=10, step_size=0.1, max_iterations=1000):
    best_solution = None
    best_value = float('-inf')
    
    for _ in range(num_restarts):
        initial_solution = random.uniform(-10, 10)
        solution, solution_value = hill_climbing(f, initial_solution, step_size, max_iterations)
        if solution_value > best_value:
            best_solution, best_value = solution, solution_value
    
    return best_solution, best_value

# 执行随机重启爬山算法
solution, solution_value = random_restart_hill_climbing(objective_function)

print(f"Optimal solution: x = {solution:.4f}")
print(f"Optimal value: f(x) = {solution_value:.4f}")

        在随机重启爬山算法中，我们多次运行标准爬山算法，每次从不同的随机初始解开始。最后，选择所有运行中找到的最佳解。这种方法可以有效地避免陷入局部最优解，提高找到全局最优解的可能性。

案例：使用爬山算法解决旅行商问题（TSP）

        旅行商问题（Travelling Salesman Problem，TSP）是经典的组合优化问题，其目标是在给定的一组城市中找到一条路径，使得旅行商访问每个城市一次并返回起始城市的总距离最短。

实现步骤

  1. 定义问题：给定一组城市及其之间的距离矩阵。
  2. 初始化解：随机生成一个初始路径。
  3. 计算适应度：计算当前路径的总距离。
  4. 生成邻域解：通过交换路径中的两个城市生成邻域解。
  5. 选择更优解：在邻域解中找到比当前解更优的解，更新当前解。
  6. 重复：重复生成邻域解和选择更优解的过程，直到达到停止条件。

代码示例

import random
import itertools

# 定义距离矩阵
distance_matrix = [
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
]

# 计算路径总距离
def calculate_total_distance(path, distance_matrix):
    total_distance = 0
    for i in range(len(path)):
        total_distance += distance_matrix[path[i - 1]][path[i]]
    return total_distance

# 生成初始解
def generate_initial_solution(num_cities):
    path = list(range(num_cities))
    random.shuffle(path)
    return path

# 生成邻域解
def generate_neighbors(path):
    neighbors = []
    for i in range(len(path)):
        for j in range(i + 1, len(path)):
            neighbor = path[:]
            neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
            neighbors.append(neighbor)
    return neighbors

# 爬山算法
def hill_climbing_tsp(distance_matrix, max_iterations=1000):
    num_cities = len(distance_matrix)
    current_solution = generate_initial_solution(num_cities)
    current_distance = calculate_total_distance(current_solution, distance_matrix)
    
    for _ in range(max_iterations):
        neighbors = generate_neighbors(current_solution)
        best_neighbor = min(neighbors, key=lambda p: calculate_total_distance(p, distance_matrix))
        best_neighbor_distance = calculate_total_distance(best_neighbor, distance_matrix)
        
        if best_neighbor_distance >= current_distance:
            break
        
        current_solution, current_distance = best_neighbor, best_neighbor_distance
    
    return current_solution, current_distance

# 执行爬山算法
solution, solution_distance = hill_climbing_tsp(distance_matrix)

print(f"Optimal solution: {solution}")
print(f"Optimal distance: {solution_distance}")

案例分析

        在这个案例中，我们使用爬山算法来解决一个包含4个城市的旅行商问题。我们定义了一个距离矩阵，表示城市之间的距离。爬山算法从一个随机生成的初始路径开始，通过在邻域解中寻找更优的路径，不断优化当前解，最终找到一个局部最优解。

解释与改进

        爬山算法在处理TSP问题时，容易陷入局部最优解。以下是一些可能的改进：

  1. 随机重启爬山算法：多次运行爬山算法，每次从不同的随机初始解开始，最后选择最佳结果。
  2. 模拟退火算法：在搜索过程中偶尔接受较差的解，以跳出局部最优解。
  3. 混合算法：结合遗传算法、粒子群优化等全局搜索算法，提高找到全局最优解的可能性。
随机重启爬山算法示例
def random_restart_hill_climbing_tsp(distance_matrix, num_restarts=10, max_iterations=1000):
    best_solution = None
    best_distance = float('inf')
    
    for _ in range(num_restarts):
        solution, solution_distance = hill_climbing_tsp(distance_matrix, max_iterations)
        if solution_distance < best_distance:
            best_solution, best_distance = solution, solution_distance
    
    return best_solution, best_distance

# 执行随机重启爬山算法
solution, solution_distance = random_restart_hill_climbing_tsp(distance_matrix)

print(f"Optimal solution: {solution}")
print(f"Optimal distance: {solution_distance}")

案例：使用爬山算法优化机器学习模型参数

        爬山算法不仅可以用于组合优化问题，还可以用于优化机器学习模型的参数。下面我们展示如何使用爬山算法来优化线性回归模型的参数。

实现步骤

  1. 定义问题：给定一组数据和一个线性回归模型，优化模型的参数以最小化损失函数（例如均方误差）。
  2. 初始化解：随机生成初始模型参数。
  3. 计算适应度：计算当前参数下的损失函数值。
  4. 生成邻域解：通过在当前参数周围进行微小扰动生成邻域解。
  5. 选择更优解：在邻域解中找到比当前解更优的解，更新当前解。
  6. 重复：重复生成邻域解和选择更优解的过程，直到达到停止条件。

代码示例

import numpy as np

# 生成数据
np.random.seed(0)
X = 2 * np.random.rand(100, 1)
y = 4 + 3 * X + np.random.randn(100, 1)

# 定义损失函数（均方误差）
def mse(theta, X, y):
    m = len(y)
    predictions = X.dot(theta)
    return (1/m) * np.sum((predictions - y) ** 2)

# 爬山算法优化线性回归参数
def hill_climbing_lr(X, y, initial_theta, step_size=0.01, max_iterations=1000):
    current_theta = initial_theta
    current_loss = mse(current_theta, X, y)
    
    for i in range(max_iterations):
        neighbors = [current_theta + step_size * np.random.randn(*current_theta.shape) for _ in range(10)]
        best_neighbor = min(neighbors, key=lambda t: mse(t, X, y))
        best_neighbor_loss = mse(best_neighbor, X, y)
        
        if best_neighbor_loss >= current_loss:
            break
        
        current_theta, current_loss = best_neighbor, best_neighbor_loss
    
    return current_theta, current_loss

# 初始化参数
initial_theta = np.random.randn(2, 1)

# 扩展X矩阵，以包含偏置项
X_b = np.c_[np.ones((100, 1)), X]

# 执行爬山算法
solution_theta, solution_loss = hill_climbing_lr(X_b, y, initial_theta)

print(f"Optimal theta: {solution_theta.ravel()}")
print(f"Optimal loss: {solution_loss}")

案例分析

        在这个案例中，我们使用爬山算法来优化线性回归模型的参数。数据由线性模型生成，并添加了一些随机噪声。爬山算法从随机初始化的参数开始，通过在参数空间中搜索最优解，最小化损失函数（均方误差）。

解释与改进

        爬山算法在优化模型参数时可能会陷入局部最优解。以下是一些可能的改进：

  1. 随机重启爬山算法：多次运行爬山算法，每次从不同的随机初始解开始，最后选择最佳结果。
  2. 模拟退火算法：在搜索过程中偶尔接受较差的解，以跳出局部最优解。
  3. 梯度下降：使用梯度信息更高效地找到最优解。
随机重启爬山算法示例
def random_restart_hill_climbing_lr(X, y, num_restarts=10, step_size=0.01, max_iterations=1000):
    best_theta = None
    best_loss = float('inf')
    
    for _ in range(num_restarts):
        initial_theta = np.random.randn(2, 1)
        theta, loss = hill_climbing_lr(X, y, initial_theta, step_size, max_iterations)
        if loss < best_loss:
            best_theta, best_loss = theta, loss
    
    return best_theta, best_loss

# 执行随机重启爬山算法
solution_theta, solution_loss = random_restart_hill_climbing_lr(X_b, y)

print(f"Optimal theta: {solution_theta.ravel()}")
print(f"Optimal loss: {solution_loss}")

        通过随机重启爬山算法，我们多次运行爬山算法，每次从不同的随机初始解开始。通过多次尝试，算法可以有效避免陷入局部最优解，提高找到全局最优解的概率。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/631991.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Java入门基础学习笔记26——break，continue

Java入门基础学习笔记26——break，continue

跳转关键字&#xff1a; break&#xff1a; 跳出并结束当前所在循环的执行。 continue&#xff1a; 用于跳出当前循环中的当次执行&#xff0c;直接进入循环中的下一次执行。 package cn.ensource.loop;public class BreakContinueDemo8 {public static void main(String[] a…
阅读更多...
AI大语言模型在公共服务中的应用实例

AI大语言模型在公共服务中的应用实例

随着计算机技术的飞速发展&#xff0c;人工智能已经成为了当今科技领域的热门话题。从早期的图灵测试到现在的深度学习和神经网络&#xff0c;人工智能已经取得了令人瞩目的成就。特别是近年来&#xff0c;大数据、云计算、高性能计算等技术的发展为人工智能的研究提供了更加广…
阅读更多...
怎么做微信预约链接_微信预约新风尚

怎么做微信预约链接_微信预约新风尚

在快节奏的现代生活中&#xff0c;我们都渴望找到一种既方便又高效的方式来处理日常事务。无论是预约看病、预约美容&#xff0c;还是预约一场心仪的讲座或活动&#xff0c;我们都希望能够一键搞定&#xff0c;省时省力。今天&#xff0c;就让我来为大家揭秘如何制作一个微信预…
阅读更多...
Facebook海外企业户/海外企业三不限户稳定性怎么样？

Facebook海外企业户/海外企业三不限户稳定性怎么样？

Facebook是做跨境电商卖家最有效的营销工具之一&#xff0c;不过相对的在Facebook上的广告竞争也会越来越激烈。目前外贸行业发展迅速。Facebook作为每天拥有30亿人口的活跃网络平台&#xff0c;约占全球网络用户的30%。平均来说&#xff0c;它的用户愿意每天花60分钟在平台上浏…
阅读更多...
美港通正规股票交易市场人民币突然拉升，市场开启“大风车”模式？

美港通正规股票交易市场人民币突然拉升，市场开启“大风车”模式？

查查配今天上午,市场又开启了“大风车”模式,多个热点轮番拉升。 一则关于地产行业利好的小作文流出,地产产业链上午爆发,租售同权、房地产服务、房地产开发等板块大涨,光大嘉宝、天地源等个股涨停。万科A涨超4%。 美港通证券以其专业的服务和较低的管理费用在市场中受到不少…
阅读更多...
【上海生物发酵展精选展商】三门峡市高瑞生物技术有限公司

【上海生物发酵展精选展商】三门峡市高瑞生物技术有限公司

三门峡市高瑞生物技术有限公司注册成立于2017年2月23日&#xff0c;经营范围是微生物培养基原材料制造、销售。2017年度因场地搬迁、异地重建&#xff0c;公司由“三门峡市高山生物制品有限公司”更名为“三门峡市高瑞生物技术有限公司”。 该公司具有20余年丰富经验的微生物培…
阅读更多...
对话 Databend Labs 联合创始人王吟：大模型浪潮里，云数仓是宠儿 | 极新企服直播实录

对话 Databend Labs 联合创始人王吟：大模型浪潮里，云数仓是宠儿 | 极新企服直播实录

以下文章来源于极新 &#xff0c;作者王吟 据 IDC 预测&#xff0c;随着企业数字化转型&#xff0c;到 2026 年&#xff0c;中国大数据 IT 支出将达到 360 亿美元。Gartner 预测&#xff0c;得益于托管云服务的推动&#xff0c;到 2023 年&#xff0c;全球数据库市场有望达到 1…
阅读更多...
超声波清洗机哪家好一点？四款超一流超声波清洗机大盘点

超声波清洗机哪家好一点？四款超一流超声波清洗机大盘点

在追求极致清洁和维护精密工具、设备及珍贵物品的时代&#xff0c;超声波清洗机显得尤为重要。不仅因其高效、快速的清洁效果&#xff0c;更因其能够触及传统手工清洁所不能及的微小缝隙。无论你是珠宝设计师、机械工程师、还是热爱生活的普通家庭用户&#xff0c;超声波清洗机…
阅读更多...
ValueError: Colors must be aRGB hex values

ValueError: Colors must be aRGB hex values

使用 openpyxla填充颜色时出现此错误
阅读更多...
Python 机器学习 基础 之 监督学习 【分类器的不确定度估计】 的简单说明

Python 机器学习 基础 之 监督学习 【分类器的不确定度估计】 的简单说明

Python 机器学习 基础 之 监督学习 【分类器的不确定度估计】 的简单说明 目录 Python 机器学习 基础 之 监督学习 【分类器的不确定度估计】 的简单说明 一、简单介绍 二、监督学习 算法 说明前的 数据集 说明 三、监督学习 之 分类器的不确定度估计 1、决策函数 2、预测…
阅读更多...
怎么转换视频格式到mp4？格式转换，4种简单方法

怎么转换视频格式到mp4？格式转换，4种简单方法

转换视频格式到MP4可以使视频在各种设备上播放更加方便&#xff0c;而MP4格式的优势在于其高质量的视频和相对较小的文件大小。怎么转换视频格式到mp4&#xff1f;在本文中&#xff0c;我们将介绍四种简单有效的方法&#xff0c;帮助您快速将视频格式转换为MP4。 无论您是初学…
阅读更多...
Linux内核的非确定行为消除

Linux内核的非确定行为消除

Linux内核作为一种广泛使用的开源操作系统内核&#xff0c;在多种硬件和设备上运行&#xff0c;提供了强大的功能和灵活的配置选项。然而&#xff0c;随着技术的发展和应用需求的增加&#xff0c;内核中出现的不确定行为也日益成为开发者和系统管理员关注的焦点。这些不确定行为…
阅读更多...
Encryption Everywhere DV TLS CA - G1

Encryption Everywhere DV TLS CA - G1

Encryption Everywhere DV TLS CA - G1属于DigiCertCA机构发布&#xff0c;分为单域名SSL证书和通配符SSL证书两种为主&#xff0c;常见的是单域名SSL证书&#xff0c;到期后就需要重新申请。 单域名类型可以保护一个全域名&#xff0c;比如&#xff1a;一个子域名或者一个主域…
阅读更多...
卖家必备：OZON、WB自养号测评详解从搭建到权重提升的全方位指导

卖家必备：OZON、WB自养号测评详解从搭建到权重提升的全方位指导

俄罗斯跨境电商平台OZON、WB国内卖家入驻也日益渐多&#xff0c;很多卖家也都着手通过自养号测评方式打造产品权重&#xff0c;OZON、WB自养号测评具有多个优势&#xff0c;这些优势主要体现在以下几个方面&#xff1a; 权重提升快&#xff1a;通过自养号进行测评&#xff0c…
阅读更多...
yolov8 模型架构轻量化 | 极致降参数量

yolov8 模型架构轻量化 | 极致降参数量

模型轻量化加速是深度学习领域的重要研究方向&#xff0c;旨在减小模型的体积和计算复杂度&#xff0c;从而提高在资源受限设备上的运行效率&#xff0c;模型参数量在轻量化加速中扮演着至关重要的角色。 首先&#xff0c;模型参数量直接决定了模型的复杂度和存储空间需求。随…
阅读更多...
Python数据分析与数据可视化 概念

Python数据分析与数据可视化 概念

考试题型&#xff1a; 一、填空题&#xff08;1分*10&#xff09; 二、程序代码填空&#xff08;1分*20&#xff09; 三、读程序写结果&#xff08;10分*4&#xff09; 四、程序设计&#xff08;10分*1&#xff09; 五、问答题&#xff08;20分*1&#xff09; 考试范围&#x…
阅读更多...
【前段】开发五子棋小游戏全流程

【前段】开发五子棋小游戏全流程

使用前端技术开发五子棋小游戏 在这篇博文中&#xff0c;我们将详细介绍如何使用HTML、CSS和JavaScript开发一个简单的五子棋小游戏。我们将展示如何初始化棋盘、处理用户交互以及实现胜负判定。特别是&#xff0c;我们将着重介绍胜负判定的逻辑实现。 完整代码我放在了这里&a…
阅读更多...
springBoot 如何让数据库读写分离

springBoot 如何让数据库读写分离

springBoot 数据库读写分离 数据库的读写分离，首先要把spring 中的自动加载的类排除掉，因为我们配置文件配置了多数据源，并且希望自己主导sql语句执行的数据库。 启动类排除自动配置 @SpringBootApplication(exclude = {DataSourceAutoConfiguration.class}) 循环引用问题…
阅读更多...
【喜马拉雅】副业分享、喜马拉雅如何赚钱、喜马拉雅写作赚钱、喜马拉雅会员免费吗？喜马拉雅极速版赚钱

【喜马拉雅】副业分享、喜马拉雅如何赚钱、喜马拉雅写作赚钱、喜马拉雅会员免费吗？喜马拉雅极速版赚钱

上班族一枚&#xff0c;已经实现副业赚钱。结合自己的经历&#xff0c;给大家分享几点找副业的经验&#xff0c;专治「闲成废柴病」。 纯干货分享&#xff0c;不拉群、不私聊&#xff0c;请放心食用。建议先点赞收藏一下。 一、任何说马上能赚钱的副业&#xff0c;一般都不太靠…
阅读更多...
React 状态管理库深度对比：在做技术选型的时候如何选择合适的状态库，nolan出品

React 状态管理库深度对比：在做技术选型的时候如何选择合适的状态库，nolan出品

掘金链接&#xff1a;https://juejin.cn/post/7368288987642232872 1,简介 在状态共享这方面&#xff0c;不像 Vuex&#xff0c;React 的官方并没有强力推荐某种封装方案&#xff0c;所以 React 的状态管理工具五花八门&#xff0c;百花齐放&#xff0c; react-redux、dva、C…
阅读更多...
最新文章

Copyright @ 2022~2023