使用 Q 学习寻找最短路径

news/2024/12/29 19:40:04/

使用 Q 学习寻找最短路径

Q 学习是一种无模型的强化学习算法,可以用于在马尔可夫决策过程(MDP)建模的环境中找到最优策略和最短路径。在这篇博客文章中,我将解释 Q 学习的工作原理,并展示在网格世界环境中寻找最短路径的实现。

理解 Q 学习算法

Q 学习的目标是学习一个最大化总体奖励的策略。它通过学习一个称为 Q 函数的动作值函数来实现这一目标,Q 函数给出了在给定状态下采取给定动作的预期效用。

更正式地说,Q 函数定义为:

   
Copy code
Q(s, a) = 从状态 s 开始采取动作 a 并遵循策略 π 的预期回报

该算法通过在探索环境的同时迭代地更新每个状态和动作的这个 Q 函数来工作。它遵循以下更新规则:

   
Copy code
Q(s, a) := Q(s, a) + α [R(s,a) + γ max Q(s', a') - Q(s, a)]  a'

其中:

α 是学习率
γ 是折扣因子
R(s,a) 是在状态 s 下采取动作 a 的即时奖励
s' 是下一个状态
max Q(s', a') 表示预期未来奖励

通过重复应用此更新规则,Q 学习能够在环境转移动态未知的情况下找到最优策略。

在网格世界上实现 Q 学习

为了演示 Q 学习的工作原理,我们在一个简单的网格世界上实现它:

Show Image

这个环境中的状态是网格单元,动作是向上、向下、向左或向右移动,奖励设置成鼓励智能体到达右上角的目标状态。

首先,我们定义环境:

   python
Copy code
import numpy as np 
import matplotlib.pyplot as pltWORLD_HEIGHT = 5  
WORLD_WIDTH = 5START = [0, 0]  
GOAL = [WORLD_HEIGHT-1, WORLD_WIDTH-1]   actions = [0, 1, 2, 3] # 上,下,左,右

接下来,我们初始化 Q 表来保存每个状态和动作对的 Q 值:

   python
Copy code
q_table = np.random.uniform(size=(WORLD_HEIGHT, WORLD_WIDTH, 4))

在主 Q 学习循环中,我们采取以下步骤:

初始化状态
选择一个动作(ε-贪婪策略)
执行动作,观察 R(s,a) 和下一个状态 s'
用上述公式更新 Q 值
将状态设置为下一个状态
检查是否达到目标

完整的算法如下:

   python
Copy code
# Q 学习算法for episode in range(NUM_EPISODES):  state = START   while state != GOAL:  # ε-贪婪动作选择 if random.uniform(0, 1) < eps:action = random.choice(actions)  else:action = np.argmax(q_table[state])# 执行动作,观察 R(s,a) 和 s'next_state, reward = takeAction(state, action)  # 更新 Q 值q_table[state + [action]] += lr*(reward +  gamma*np.max(q_table[next_state]) -  q_table[state + [action]])   state = next_stateeps *= eps_decayprint("Q 表:")
print(q_table)