Q-Learning解决最短路径问题

紧接着使用Q-Learning实现了一维环境里的寻宝问题，以及二维世界里的寻宝问题，将实现模板应用于最短路问题。

最短路径问题的环境如下图，起点为A，终点为G，选择最短的路线完成A->G。节点之间的连线表示节点相联通，其上数值表示奖励。若节点之间无法联通，则奖励为-99。

实现流程：（1）设置初始状态；（2）选择动作；（3）获取状态反馈；（4）更新Q表；（5）更新状态；（6）设置终止条件

状态（state）:节点编号
动作（action）：节点编号

初始化时需要设置环境状态，动作列表以及算法的参数。

class TwoDimensionQTable:
    def __init__(self, states,actions,rewords,learningRate=0.1, rewarddecay=0.9, eGreedy=0.9,episode=100):
        #状态列表
        self.states=states
        #动作列表
        self.actions = actions
        #奖励列表
        self.rewords=rewords
        #学习率
        self.lr = learningRate
        #奖励衰减率
        self.gamma = rewarddecay
        #贪婪策略
        self.epsilon = eGreedy
        #训练次数
        self.episode=episode
        #空Q表
        self.qTable = pd.DataFrame(columns=self.actions, dtype=np.float64)

由于初始设置Q表为空，在算法进行过程中需要将探索得到的新状态添加进入Q表并更新Q表的行列。

    #遇到新状态后添加到Q表，行索引：状态；列索引：动作
    def stateExist(self, state):
        if str(state) not in self.qTable.index:
            self.qTable = self.qTable.append(
                pd.Series(
                    [0]*len(self.actions),
                    index=self.qTable.columns,
                    name=state,
                    )
            )

在动作选择部分，算法根据当前状态（state）选择动作（action）。选择动作过程中的策略是：90%的概率根据Q表最优值进行选择；10%的概率随机选择；

    #根据状态从qTable选择动作
    def chooseAction(self,state):
        #判断状态是否存在Q表中
        self.stateExist(state)
        #选择采取的动作
        #90%的概率按照Q表最优进行选择
        if np.random.uniform() 
状态反馈 
#根据状态和动作返回下一个状态和当前的奖励
    def feedBack(self,state,action):
        nextState=action
        reword=self.rewords.loc[state][nextState]
        return nextState,reword
 
更新Q表 
    #根据当前状态、动作、下一状态、奖励更新Q表
    def updateTable(self,state,action,nextState,reword):
        #判断状态是否存在Q表中
        self.stateExist(nextState)
        #当前状态值
        qPredict=self.qTable.loc[state,action]
        #下一状态值
        if nextState=='G':
            qTarget=reword
        else:
            qTarget=reword+self.gamma*self.qTable.loc[nextState,:].max()
        #print("qTarget:",qTarget)
        #更新
        self.qTable.loc[state,action]+=self.lr*(qTarget-qPredict)
 
主循环 
   #主循环
    def mainCycle(self):
        for episode in range(self.episode):
            #初始状态
            state='A'
            actionStr=""
            while True:
                #选择动作
                action=self.chooseAction(state)
                if episode==self.episode-1:
                    actionStr+=str(state)+"->"
                #状态反馈
                nextState,reword=self.feedBack(state,action)
                #更新Q表
                self.updateTable(state,action,nextState,reword)
                #更新状态
                state=nextState
                #终止条件
                if state=='G':
                    if episode==self.episode-1:
                        print(actionStr)
                    break
 
求解结果 

 求解结果为：A->C->F->E->G
 
===========================================
 今天到此为止，后续记录其他强化学习技术的学习过程。
 以上学习笔记，如有侵犯，请立即联系并删除！