从PyTorch官方的一篇教程说开去(3.3 - 贪心法)

您的进步和反馈是我最大的动力,小伙伴来个三连呗!共勉。

贪心法,可能是大家在处理陌生问题时候,最容易想到的办法了吧?

还记得小时候,国足请了位洋教练发表了一句到现在还被当成段子的话:“如果球员不知道把球往哪里踢,那就往球门里踢!”呃,施拉普纳老爷子如果干程序员,应该也能混的不错!

当我们在陌生的城市迷路,一般会顺着大路找更大的路,沿着繁华的街区找更繁华的街区,直到找到地标性的建筑物来重新帮助自己找回方向感。

男生购物的时候,如果心里已经锁定了品牌,那么几个单品大差不差的情况下,折扣最大的那件怎么看都觉得美滋滋的。

至于吃饭,那肯定是打开手机app,不出意外的话,推荐的前几个基本跑不了了。

还有直播间里,为啥主播娇滴滴的呼唤榜一大哥,咳咳,打住。

类似这样的例子还可以举出很多,不过既然我们是撸代码的,那么多举几个相关的例子好了!

首先想到的肯定是最短路径上的dijkstra(包括升级的双向dijkstra算法),为了计算从起点到图上任意点的最短距离,老爷子就每走到一个点(广度优先,总n个),就重新计算和更新一下到起点的最短距离,从而得到了这个非常优秀的,空间O(n)和时间O(n^2)的算法(时间复杂度还有优化空间)。

然后就是0-1背包问题,比如你的道士打僵尸爆出了一地的法宝材料装备,然后你的宠物狗挠小怪也是一地,都铺满了,这时候负重有限背包有限,物品呢占地方不同价值也不同,你也不想来回来去主城主职业改成做二道贩子,那么怎么捡最划算呢?

还有压缩,还有搜索,感兴趣的小伙伴可以去brilliant看看,好消息是,不但有图示讲解,还有题可以刷,呃那个,比较友好的那种。强烈安利。

Greedy Algorithms | Brilliant Math & Science Wiki

实际应用中,贪心法就一点不好 - 这是把“神经刀”,顺的时候神挡杀神佛挡杀佛,不顺的时候呢无法收敛,主打一个起伏不定,“女孩的心思男孩你别猜”。

这就跟深度学习在工程中的发挥比较类似了,也难怪我们在上一个章节看见,他俩一起秀恩爱。

具体点呢, 𝑄(𝑠,𝑎)=𝑟+𝛾max⁡𝑎′𝑄(𝑠′,𝑎′),这里更新状态时采用的参数,max/最大预期回报,就是在应用贪婪法。具体的做法就是 - 

//其他代码
# Exploration parameters
epsilon = 1.0                 # Exploration rate
max_epsilon = 1.0             # Exploration probability at start
min_epsilon = 0.01            # Minimum exploration probability 
decay_rate = 0.005            # Exponential decay rate for exploration prob

//其他代码

for step in range(max_steps):
    # 3. Choose an action a in the current world state (s)
    ## First we randomize a number
    exp_exp_tradeoff = random.uniform(0, 1)
        

## If this number > greater than epsilon --> exploitation (taking the biggest Q value for this state)
    if exp_exp_tradeoff > epsilon:
        action = np.argmax(qtable[state,:])
# Else doing a random choice --> exploration
    else:
        action = env.action_space.sample()

//其他代码
# Reduce epsilon (because we need less and less exploration)
epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode) 
//其他代码

简单概括一下,就是在训练的初期,选择较大的探索值(epsilon),随着训练的进行,慢慢减小探索值,直到得到稳定收敛的良好控制效果。

为了更好的说明如何把贪婪法应用于深度学习,稍后会再更新一篇教程以及源码,以便小伙伴食用。

相关推荐

  1. “Linux VS Laxcus谁更强”

    2024-07-23 06:52:02       54 阅读
  2. Pytorch实用教程Pytorch中torch.max

    2024-07-23 06:52:02       32 阅读
  3. Pytorch实用教程: torch.tensor()

    2024-07-23 06:52:02       36 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 06:52:02       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 06:52:02       106 阅读
  3. 在Django里面运行非项目文件

    2024-07-23 06:52:02       87 阅读
  4. Python语言-面向对象

    2024-07-23 06:52:02       97 阅读

热门阅读

  1. 图像处理 -- ISP调优(tuning)的步骤整理

    2024-07-23 06:52:02       25 阅读
  2. 时间和空间复杂度

    2024-07-23 06:52:02       24 阅读
  3. vivado IOBDELAY

    2024-07-23 06:52:02       24 阅读
  4. React/Vue项目解决跨域的方法

    2024-07-23 06:52:02       25 阅读
  5. 第五节shell脚本中的运行流程控制(3.2)

    2024-07-23 06:52:02       24 阅读
  6. 后端存储流程结构的思考

    2024-07-23 06:52:02       22 阅读
  7. 【DevOps系列】构建Devops系统

    2024-07-23 06:52:02       21 阅读