精华内容
下载资源
问答
  • 基于大数据的主动科研管理模式与优化决策机制.docx
  • 以构建“专家图谱”为例,融合分析了科研管理大数据中的关联知识和潜在信息,并探讨基于这些技术手段,如何将传统被动的管理模式转变为主动的科研管理模式,进而建立基于大数据的新型管理模式与决策机制
  • 在此基础上,提出了一种多目标遗传优化总最佳连接(always best connected,ABC)支持型切换决策机制,通过精英选择和个体迁移提高决策质量,基于博弈分析, 寻求多终端对多接入网络的最佳切换决策方案,使用户和...
  • 多维网上拍卖优化机制决策模型研究 在网上多维拍卖的机理设计中,多维拍卖竞胜标的确定问题是一个十分复杂的 问题,事实上它已经被证明是NP C Non-deterministic Polynomial,非确定性多项式) 难题。本文是通过...
  • 阐述了模型选择技术在泵站优化运行中研究的必要性,给出泵站优化运行模型选择系统的结构,采用两级模型字典库存储模型并通过构造搜索树建立模型选择推理机制,完善了模型选择的全过程和操作步骤,实现了泵站优化运行模型...
  • 应用博弈方法比较分析合作博弈、纳什均衡博弈、Stackelberg主从博弈三种决策模式下制造/再制造产品的最优定价和广告投入策略, 并针对非合作博弈下的效率损失设计了闭环供应链中制造和再制造过程的利益协调机制。...
  • 应用博弈方法比较分析合作博弈、纳什均衡博弈、Stackelberg主从博弈三种决策模式下制造/再制造产品的最优定价和广告投入策略,并针对非合作博弈下的效率损失设计了闭环供应链中制造和再制造过程的利益协调机制。...
  • 在此基础上,结合事件触发机制有效提高家庭能量管理系统的运行效率,进而给出从家庭能量管理控制中心到用电设备的智能优化调度方法;最后,通过仿真算例证实了所提方法的有效性,结果表明其能在减少用户用电费用的...
  • AVS视频编码标准中存在丰富的帧内和帧间预测模式速率失真优化模式决策可以充分利用这种灵活性来提高时空预测效率并最大化编码效率。但是,由于巨大的吞吐负担,实现复杂性非常高针对这项工作,针对VLSI实现量身定制...
  • 分析列车运行过程中的能量转换机制,建立单列车耗能最低优化模型、多列车节能优化模型及列车延误多目标优化控制模型,针对模型本身及其约束条件的复杂性,提出基于改进布谷鸟优化算法与动态搜索方法的“模拟优化”...
  • 论文研究-双积分制下汽车生产商生产决策优化.pdf, 本文研究了燃料消耗量积分和新能源汽车积分"双积分制"下汽车生产商生产决策问题,基于持股比例和内部期权协议建立了...
  • 针对求解不确定、动态和分布式的多学科设计优化问题时所面临的挑战,提出了一种基于行为均衡分析的多学科协同决策机制。在行为博弈分析框架下,通过采用折衷决策支持问题建立学科设计团队的基本决策模型,利用理性...
  • 在真实世界中,带有决策和目标约束的多目标优化问题常常都同时出现。但以前的人工CMOPS从来没有同时考虑过决策和目标约束。因此,本文设计了一个同时带有决策和目标约束的人造的多目标优化问题集,取名为DOC。 另外...

    Handling Constrained Multiobjective Optimization Problems With Constraints in Both the Decision and Objective Spaces

    1.摘要

    在真实世界中,带有决策和目标约束的多目标优化问题常常都同时出现。但以前的人工CMOPS从来没有同时考虑过决策和目标约束。因此,本文设计了一个同时带有决策和目标约束的人造的多目标优化问题集,取名为DOC。
    另外,本文还提出了一个简单且高效的处理DOC或也可用于其他CMOPS的方法,取名为TOP。最后本文通过实验证明了TOP算法的有效性。

    2.介绍

    这部分文章对CMOP和本文研究内容做了基本介绍,这里只对重点问题做介绍。
    ①一个CMOP可以简单描述为以下形式:
    在这里插入图片描述
    其中F(x)是目标函数集,g(x)是不等式约束,h(x)是等式约束,x是决策变量。
    ②现实生活中,大部分限制是决策限制。文章提供了个小例子区别目标约束和决策约束,比如我们去买车,我们的目标函数是舒适度和价格。我们希望价格cost<50k,这个就构成了目标约束,这很容易在目标空间中描述。另外,我们希望座位seat>5,生产国=德国,可以发现这两个约束却不能在目标空间描述出来,这两个实际就是决策限制。
    ③DOC中涉及到等式约束,目前很少的人工CMOPS考虑到了等式约束
    ④TOP算法分成两步。第一步:利用加权的方法将CMOP转换为一个单目标问题,进行优化。第二步:直接使用现有的CMOEAs对第一步优化结果进行进一步优化,注意此时优化的是个带约束的多目标优化原问题。

    3.相关工作

    这部分文章介绍了CMOPs里面涉及的一些基本定义,以及对当前人工CMOPs和CMOEAs做了介绍。
    A.基本定义
    1)Pareto Dominance:假设有两个决策向量,Xu和Xv。当Xu得到的所有目标函数的值都小于Xv求出的,我们称Xu支配Xv。
    2)Feasible Region:满足所有约束条件的空间即为可行域。我们用下面的公式描述约束的违反程度。
    在这里插入图片描述
    在这里插入图片描述
    其中,CVi(x)为第i个目标函数的违反程度。
    3)Pareto Optimal Solution:对于一个决策向量Xu,如果找不到比起更优的Xv向量,则称Xu是一个最优的解决方案
    4)Pareto Optimal Set:Pareto 最优集,由多个最优决策向量组成的最优解决方案集合
    5) Pareto Front:Pareto 前沿,Pareto 最优集在目标空间的图像
    B.当前的人工CMOPs的介绍
    目前的人工CMOPs主要分如下两种:

    1. 第一种:在多目标优化问题中只考虑了目标约束。比如CTPs, DAS-CMOPs, 和 NCTPs.
    2. 第二种:在多目标优化问题中只单独考虑决策和目标约束。比如CFs.

    C.当前的CMOEAs的介绍
    目前的CMOEAs算法大致分成以下3类:

    1. 基于支配的方法,包括NSGA-II-CDP,IDEA
    2. 基于分解的方法,包括CMOEAD,MOEA/D-CDP
    3. 基于指标的方法

    而主流的为前两种,所以这里不讨论基于指标的方法:
    基于支配的方法
    NSGA-II-CDP
    原文:A fast and elitist multiobjective genetic algorithm: NSGA-II。
    该算法是NSGA-II的延伸,其中CDP指加入了约束支配原理。具体的说,任何可行的个人都支配任何不可行的个体,对于两个不可行个体,最好是约束违反较小的个体。
    IDEA
    原文:Infeasibility Driven Evolutionary Algorithm (IDEA) for Engineering Design Optimization
    该算法进化过程中显式地保持了一小部分不可行的解决方案。 认为不可行解的存在有利于IDEA从可行区域和不可行区域搜索帕累托最优解。
    Adaptive tradeoff model
    原文:A comparative study of constraint-handling techniques in evolutionary constrained multiobjective optimization
    自适应权衡模型根据当前种群的可行性比例将整个进化过程分为三种情况。 这三种情况是:1)不可行情况;2)半可行情况;3)可行情况。 在不同的情况下,设计了不同的约束处理技术来处理约束。
    A CMOEA based on an adaptive penalty function and a distance measure
    原文:Constraint handling in multiobjective evolutionary optimization
    该算法不仅可以在可行区域内搜索帕累托最优解,而且可以利用不可行个体提供的重要信息,具有更好的目标函数值和较低的约束违反。
    Blended ranking to cross infeasible regions in constrained multiobjective problems注:标题即原文
    该算法可以跨越目标空间的不可行区域,找到真正的约束帕累托前沿。 该算法的主要思想是将个体在目标空间中的秩与其在约束空间中的秩相混合。
    An evoltionary algorithm for constrained multi-objective optimization
    提出了一种CMOEA,其中帕累托优势概念与约束处理技术和多样性机制相结合。
    New constraint handling method for multi-objective and multi-constraint evolutionary optimization
    提出了一种新的基于帕累托最优性的约束处理技术。
    Constrained Pareto simulated annealing for constrained multi-objective optimization 和 Constrained multiobjective optimization algorithm based on immune system model
    分别采用模拟退火和免疫系统模型求解CMOP。
    A corner point-based algorithm to solve constrained
    multi-objective optimization problems 和 Differential evolution mutation operators for constrained multi-objective optimization

    采用差分进化(DE)来应对CMOP。
    A modified objective function method with feasible-guiding strategy to solve constrained multiobjective optimization problems
    引入了一种改进的目标函数方法来引导优势度检验,并采用了一种可行的指导策略来修复不可行的个体。 认识到单一约束处理技术的局限性。
    Constrained multi-objective optimization algorithm with an ensemble of constraint handling methods
    提出了一种新的CMOEA,它利用约束处理技术的集合来求解CMOP。

    基于分解的方法
    CMOEAD
    原文:An adaptive constraint handling approach embedded MOEA/D
    提出了一种基于分解的CMOEA,称为CMOEAD,通过添加一种新的约束处理技术,可以看作是MOEA/D的扩展。 在这种约束处理技术中,根据约束类型、可行空间的大小和搜索结果自适应地调整违规阈值。 这种约束处理技术的目的是增加选择压力,并使不可行的解决方案的违规小于确定的阈值,得到可行解。
    MOEA/D-CDP
    原文:A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D
    随机排序和CDP的扩展/修改版本是在MOEA/D框架下实现的。 实验结果表明,CDP比随机排序更有效。
    An improved epsilon constraint handling method embedded in MOEA/D for constrained multi-objective optimization problems
    将改进的epsilon约束处理技术应用于MOEA/D,其中epsilon水平根据当前人群中的可行性比率动态调整。
    Push and pull search for solving constrained multi-objective optimization problems
    一个推拉搜索(PPS)框架被嵌入到MOEA/D中,以解决CMOPs。 在PPS中,搜索过程分为两个不同的阶段:1)推送阶段和2)拉动阶段。 在推送阶段,忽略了约束,旨在跨越无约束帕累托前沿前面的不可行区域。 然后在拉阶段,考虑约束,并采用改进的epsilon约束技术将在推阶段得到的解拉向可行的和非主导的区域。
    MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems
    一种名为基于角度的约束优势原理的约束处理技术被纳入到MOEA/D中,用于求解CMOP。

    4.DOC

    在这里插入图片描述
    DOC中包含了9个实例,即DOC1-DOC9,其中m代表目标函数个数,D代表决策变量的个数,NOC代表目标约束,NDC代表决策约束,NIC代表不等式约束,NEC代表等式约束,Feasibility Ratio代表得到可行解的概率.

    5.TOP

    TOP算法分成两步。
    第一步:利用加权的方法将CMOPs转换为一个简单的单目标问题,进行优化。我们需要注意的是:

    1. 设计一个合理的权重向量将问题转换为单目标函数
    2. 约束处理方式为a.如果Xu和Xv都是可行解时,取目标函数的导数更小的 b.当一个可行一个不可行时取可行的 c.当都不可行时,取约束违反程度小的
    3. 本文采用了DE进行搜索
    4. 停止条件:a.可行解的比例超过三分之一 b.计算所有可行个体的所有目标函数的归一化结果之和,取其max和min,若max-min<0.2. 则停止
      在这里插入图片描述
      在这里插入图片描述

    第二步:直接使用现有的CMOEAs对第一步优化结果进行进一步优化,注意此时优化的是个带约束的多目标优化原问题。

    6.实验

    实验指标

    1. FR:可行率
    2. IGD:越小越好
    3. HV:越大越好

    参数设置

    1. 种群大小:对于2目标问题设置成100,3目标问题设置成300。这里参考了MOEA/D: A multiobjective evolutionary algorithm based on decomposition提供的建议
    2. 使用了二进制交叉和多项式变异,交叉概率设为1.0,变异概率设为1/D,D为决策变量个数
    3. 独立运行数和终止条件:所有算法在每个实例上独立运行20次,当两个目标CMOP和三个目标CMOP分别达到200,000和400,000个适应度评估时终止。
    4. 算法参数设置:为了确保比较公平,NSGA-II-CDP、IDEA、CMOEAD和MOEA/D-CDP的其他参数设置与它们的原始论文相同,并且在ToP框架下保持不变。

    本文对比了使用TOP的 NSGA-II-CDP 和IDEA 算法和没使用TOP的,这两个进化算法都是基于支配的方式,结果如下图。
    在这里插入图片描述
    在这里插入图片描述

    本文对比了使用TOP的 CMOEAD 和 MOEA/D-CDP 算法和没使用TOP的,这两个进化算法都是基于分解的方式,结果如下图。
    在这里插入图片描述
    在这里插入图片描述
    另外,文章还对比了使用DE后TOP的表现。
    在这里插入图片描述

    7.总结

    从上述实验结果来看,在CMOEAs中,引入TOP的机制可以提高算法的表现。这可能是因为:
    1.TOP提供了更少的评估次数,即更快的训练速度
    2.TOP有效避免了种群陷入局部最优
    DOC和ToP的MATLAB源代码可以从Y.Wang的主页下载 http://www.escience.cn/people/yongwang1/index.html.

    返回受约束的多目标优化问题优秀论文及总结目录

    展开全文
  • 通过修正塔格特模型,深入探讨了基于企业价值成长的资本结构优化条件,并根据中国企业制度的特殊性提出了建议。研究表明,当融资债券具有税盾效应时或当企业家前期消费的边际效用与后期的非金钱支出的边际效用之比...
  • 1.理解决策树算法 简而言之,决策树是一个分类器(classifier)。 它利用树状结构,来对于特征以及潜在的结果之间的关系建立模型。如下图(来源网络): 在决定是见于不见的时候,决策树给出了一些节点(node)...

    本篇需要使用的数据集为credit.csv,下载好并保存于R目录。

    1.理解决策树算法

    简而言之,决策树是一个分类器(classifier)。 它利用树状结构,来对于特征以及潜在的结果之间的关系建立模型。如下图(来源网络):

    在决定是见于不见的时候,决策树给出了一些节点(node)来作为判断依据,至于这些节点是如何被找到的,内在的算法是什么,这个很难在这里讲清楚(而且严格地讲,我们每个人都可以不依赖R中已有的function而自己去编写决策树函数(并不会很难,如果你的逻辑简单的话)),但是决策树算法合适停下来却很容易理解:

    a. 没有剩余的特征来分辨案例之间的区别

    b.决策树已经达到预先定义的大小限制

    2.此次的目的

    credit.csv file里包含着的是1000个关于贷款的案例,我们的目的是希望建立模型来预测影响违约风险的因素。 数据里面的变量很多,最关键的是最后一个default变量,Yes便是违约了,No便是没有违约。

    正如很多在R中的函数一样,决策树函数在R中也不仅仅是一个表达式,这里介绍一个较为常见的包和function,C5.0算法。

    这个算法的内在逻辑可以自行上网查阅(切记,没有任何一种算法是绝对好的,我们并不需要找出什么时候哪个算法更好,也没必要,只需要这个算法拟合度高便行)

    install.packages( 'C50' )
    
    library( C50 )  #安装c50包

    读取我们已经下载好的csv文件:

    credit <- read.csv("credit.csv") 

    往往我们需要设置stringAsFactors= F 来使字符型数据不被设为因子(factor),我们可以先设置,然后再更具自己的需要一个个调整,但是这里我并没有设置,因为我需要将他们设置为factor。

    3.准备工作-data clean

    如果你多次尝试过自己完完整整的处理一个项目(数据由别人提供),你会发现,data cleaning将会占用你整个项目8成以上的时间,你需要不断地去清洗数据以达到你需要的最终结果,甚至很多时候结果不好仅仅是因为数据的清洗不到位。

    dim(credit)  
    head(credit)
    tail(credit)
    str(credit)
    summary(credit)
    which(!complete.cases(credit))   
    

    有一些步骤我们经常都要做,比如了解数据整体结构,看一看有没有缺失值,即使C5.0 的decision tree算法可以帮助我们处理缺失值,但是你仍然得去看看有没有缺失值,这有助于你了解数据的整体性。

    > table(credit$default)  
    
     no yes 
    700 300 

    整体而言,违约的人数是30%,所以在之后我们随机分类training data 和testing data的时候, 这个大概的比例我们也应该记在心中,如果比例差距很大,建议再做一次随机分类。

    进行数据分类:

    set.seed(123)   #这一步是为了使你的结果和我的一样
    train_sample <- sample(1000, 900)  
    
    str(train_sample)
    
    # split the data frames
    credit_train <- credit[train_sample, ]  #训练组
    credit_test  <- credit[-train_sample, ]  #测试组
    
    prop.table(table(credit_train$default))  
    
           no       yes 
    0.7033333 0.2966667 
    prop.table(table(credit_test$default))
    
      no  yes 
    0.67 0.33 

    我使用了set.seed(123)来建立伪随机,因为如果没有这个codes的话,你跑出来的结果肯定和我的不一样,因为下一步的sample是完全随机的。 尽管的伪随机,但是和真正的随机机制没有什么区别。

    可以看见,No的比例在70%左右, yes的比例也在30%左右,总体符合我们数据特点。

    4.使用C5.0函数建立模型

    之前我们已经安装了C50包,而里面的决策树模型函数是C5.0

    credit_model <- C5.0(x= credit_train[-17], y= credit_train$default) #x为training data,去除
    #17th column因为那是 我们需要的结果, y为class,必须是一个levels大于2的因子变量
    
    > credit_model
    
    Call:
    C5.0.default(x = credit_train[-17], y = credit_train$default)
    
    Classification Tree
    Number of samples: 900   #900个samples
    Number of predictors: 16 #使用了16个预测量(我们数据里面一共有17列,除去被我们去除的17列,就是说
    #这里使用了全部变量,过拟合!!!)
    
    Tree size: 57    #树的node有57个,也就是说57个分叉口
    
    Non-standard options: attempt to group attributes

    值得注意的是,这里使用了数据里面全部的列(16个)作为predictors,这也是决策树缺点之一:过拟合。 后续的博客会提到的随机森林理论可以很好的解决这一点。

    > summary(credit_model)
    
    Call:
    C5.0.default(x = credit_train[-17], y = credit_train$default)
    
    
    C5.0 [Release 2.07 GPL Edition]  	Tue Jul 17 17:15:45 2018
    -------------------------------
    
    Class specified by attribute `outcome'
    
    Read 900 cases (17 attributes) from undefined.data
    
    Decision tree:
    
    checking_balance in {> 200 DM,unknown}: no (412/50)
    checking_balance in {< 0 DM,1 - 200 DM}:
    :...credit_history in {perfect,very good}: yes (59/18)
        credit_history in {critical,good,poor}:
        :...months_loan_duration <= 22:
            :...credit_history = critical: no (72/14)
            :   credit_history = poor:
            :   :...dependents > 1: no (5)
            :   :   dependents <= 1:
            :   :   :...years_at_residence <= 3: yes (4/1)
            :   :       years_at_residence > 3: no (5/1)

    这是决策树结果的一部分,告诉了我们nodes是如何被分类的。 如第一行:checking_balance in {> 200 DM,unknown}: no (412/50), 告诉我们支票账户如果大于200 DM 或者unknown的时候, 那么我们判断为不大可能违约,(412/50)表示412个案例符合这个判断, 50个案例违背了判断。你会发现这个判断似乎没有逻辑可言,>200可以理解为有存款,违约当然概率低。但是unknown却让人难以理解,这有可能是因为异常值导致的,又或者是这便是真实情况(也许unknown的人存款都很大,或者是某个地区统计的时候漏掉了,但是该地区属于富裕地区)。

    5.评估模型

    > # create a factor vector of predictions on test data
    > credit_pred <- predict(credit_model, credit_test)
    > # cross tabulation of predicted versus actual classes
    > library(gmodels)
    > CrossTable(credit_test$default, credit_pred,
    +            prop.chisq = FALSE,  prop.c = FALSE,
    +            dnn = c('actual default', 'predicted default'))
    
     
       Cell Contents
    |-------------------------|
    |                       N |
    |           N / Row Total |
    |         N / Table Total |
    |-------------------------|
    
     
    Total Observations in Table:  100 
    
     
                   | predicted default 
    actual default |        no |       yes | Row Total | 
    ---------------|-----------|-----------|-----------|
                no |        59 |         8 |        67 | 
                   |     0.881 |     0.119 |     0.670 | 
                   |     0.590 |     0.080 |           | 
    ---------------|-----------|-----------|-----------|
               yes |        19 |        14 |        33 | 
                   |     0.576 |     0.424 |     0.330 | 
                   |     0.190 |     0.140 |           | 
    ---------------|-----------|-----------|-----------|
      Column Total |        78 |        22 |       100 | 
    ---------------|-----------|-----------|-----------|

    从结果而言,我们成功预测了100个测试案例中的73个,错误的预测中有8个守信案例(NO)被归为违约(YES),这是False possitive, 有19个 False negative的案例。  我们的结果看似有73%的正确率(不算糟糕),但是你如果把每一个结果都预测为NO的话,你也会有67%的正确率(和我们的就差7%),对比于我们的工作量而言,我们的预测可谓是毫无意义。更糟糕的是,我们的False negative预测有19个, 占整体违约数量(33个)的 58%,这是非常糟糕的,是不能接受的。试想错误地高估了一个人的守信度会给银行带来多大的损失。

    6. 提升模型性能

    这里就可以提到C5.0 函数中的另一个argument:trails(an integer specifying the number of boosting iterations. A value of one indicates that a single model is used.) 这是一个基于boosting的算法,正如R里面的描述,这是一种算法的集合,迭代。 默认值为1,意味着我们只使用一种算法。 通常我们将trails设为10,这已经通过实践检验可以提高精确度大概25%。

    > credit_boost10 <- C5.0(credit_train[-17], credit_train$default,
    +                        trials = 10)
    > credit_boost10
    
    Call:
    C5.0.default(x = credit_train[-17], y = credit_train$default, trials
     = 10)
    
    Classification Tree
    Number of samples: 900 
    Number of predictors: 16 
    
    Number of boosting iterations: 10 
    Average tree size: 47.5 
    
    Non-standard options: attempt to group attributes

    可以看见 average tree size变成了47.5,我们之前是57.而运行:

    summary(credit_boost10)
    
    Evaluation on training data (900 cases):
    
    Trial	    Decision Tree   
    -----	  ----------------  
    	  Size      Errors  
    
       0	    56  133(14.8%)
       1	    34  211(23.4%)
       2	    39  201(22.3%)
       3	    47  179(19.9%)
       4	    46  174(19.3%)
       5	    50  197(21.9%)
       6	    55  187(20.8%)
       7	    50  190(21.1%)
       8	    51  192(21.3%)
       9	    47  169(18.8%)
    boost	         34( 3.8%)   <<
    
    
    	   (a)   (b)    <-classified as
    	  ----  ----
    	   629     4    (a): class no
    	    30   237    (b): class yes
    
    > credit_boost_pred10 <- predict(credit_boost10, credit_test)
    > CrossTable(credit_test$default, credit_boost_pred10,
    +            prop.chisq = FALSE, prop.c = FALSE, prop.r = FALSE,
    +            dnn = c('actual default', 'predicted default'))
    
     
       Cell Contents
    |-------------------------|
    |                       N |
    |         N / Table Total |
    |-------------------------|
    
     
    Total Observations in Table:  100 
    
     
                   | predicted default 
    actual default |        no |       yes | Row Total | 
    ---------------|-----------|-----------|-----------|
                no |        62 |         5 |        67 | 
                   |     0.620 |     0.050 |           | 
    ---------------|-----------|-----------|-----------|
               yes |        13 |        20 |        33 | 
                   |     0.130 |     0.200 |           | 
    ---------------|-----------|-----------|-----------|
      Column Total |        75 |        25 |       100 | 
    ---------------|-----------|-----------|-----------|

    可以发现错误率变成了 18%, False Negative 和false possitive 的预测都降低了。

    但是这就足够了吗?

    尽管在预测不会违约的案例上表现的很好,但是也将本来会违约的人预测为了不会违约(13/33)39%的错误率,这里表现的并不满意。幸运的是,如果我们认为False negative是不能接受的,因为这很可能会导致银行大量的损失,那么我们有办法在C5.0上增加一个argument来达到这一个目的:

    > # create dimensions for a cost matrix
    > matrix_dimensions <- list(c("no", "yes"), c("no", "yes"))
    > names(matrix_dimensions) <- c("predicted", "actual")
    > matrix_dimensions
    $`predicted`
    [1] "no"  "yes"
    
    $actual
    [1] "no"  "yes"
    
    > # build the matrix
    > error_cost <- matrix(c(0, 1, 4, 0), nrow = 2, dimnames = matrix_dimensions)
    > error_cost
             actual
    predicted no yes
          no   0   4
          yes  1   0

    以上建立了一个matrix,这是因为C5.0里面的参数costs必须等于一个matrix(a matrix of costs associated with the possible errors. The matrix should have C columns and rows where C is the number of class levels.),这里将false negative的代价设为了4, false possitive设为1(值可以根据需求来调整)

    > # apply the cost matrix to the tree
    > credit_cost <- C5.0(credit_train[-17], credit_train$default,
    +                     costs = error_cost)
    > credit_cost_pred <- predict(credit_cost, credit_test)
    > CrossTable(credit_test$default, credit_cost_pred,
    +            prop.chisq = FALSE, prop.c = FALSE, prop.r = FALSE,
    +            dnn = c('actual default', 'predicted default'))
    
     
       Cell Contents
    |-------------------------|
    |                       N |
    |         N / Table Total |
    |-------------------------|
    
     
    Total Observations in Table:  100 
    
     
                   | predicted default 
    actual default |        no |       yes | Row Total | 
    ---------------|-----------|-----------|-----------|
                no |        37 |        30 |        67 | 
                   |     0.370 |     0.300 |           | 
    ---------------|-----------|-----------|-----------|
               yes |         7 |        26 |        33 | 
                   |     0.070 |     0.260 |           | 
    ---------------|-----------|-----------|-----------|
      Column Total |        44 |        56 |       100 | 
    ---------------|-----------|-----------|-----------|

    看见整体错误率在 37%,并没有提高(反而下降了),但是false negative的预测却降到了7个(你可以尝试不断改变代价值来达到你想要的结果),如果你觉得这个错误率是可以接受的,那么这个模型本身便可以被接受了。

    ALL IN ALL

    我们最终的预测存在一些不尽如人意的地方,如错误率仍然偏高, false negative的值还是太多等等,这真的印证了人心不可预测,或者是贷款人的一些其他重要信息没有被搜集(如借款的目的)。没有完美的模型,也没有百分百的预测,但是总体上讲,决策树模型只要满足了我们的需求,那么就是可以接受的(也许false negative的值足够低就行,因为银行不希望亏本)

    展开全文
  • IEEE) 这是2020年发布在IEEE上的一篇文章,主要讲的是基于决策分类的进化算法来解决动态多目标优化问题(DMOPs),由于本人也是才接触多目标进化没多久,学术功底有限,如果有不正确的地方欢迎批评指正!...

    阅读论文:A Dynamic Multiobjective Evolutionary Algorithm
    Based on Decision Variable Classification

    (Zhengping Liang , Tiancheng Wu, Xiaoliang Ma, Zexuan Zhu , Member, IEEE,and Shengxiang Yang , Senior Member, IEEE)
    这是2020年发布在IEEE上的一篇文章,主要讲的是基于决策分类的进化算法来解决动态多目标优化问题(DMOPs),由于本人也是才接触多目标进化没多久,学术功底有限,如果有不正确的地方欢迎批评指正!

    前言

    首先提出两个问题
    1、什么是动态多目标优化问题(DMOPs)?
    具有多个互相冲突且随着时间变化的多目标优化问题
    2、动态多目标优化问题和多目标优化问题之间有什么区别呢?
    动态=Dynamic 优化问题是指其目标函数不仅与决策变量有关,而且还会随着时间(环境)动态变化。
    定义多目标问题(MOP)
    在这里插入图片描述
    定义动态多目标问题(DMOP)
    在这里插入图片描述
    X = (x1,x2,…xnt)代表nt维的决策变量向量,主要是新增加了t:离散的时间实例,fmt(x,t)表示x在时间t的第mt个目标函数。nt和mt的值都会随时间变化。F(x,t)代表时间t评估解x的目标函数向量;p和q分别是不等式约束和等式约束的个数;gi(x,t)代表第i个不等式约束;Ωt代表可行的时间空间;

    Abstract–摘要

    现状:目前提出了许多动态多目标进化算法(DMOEAs)来解决DMOPs,主要是通过将多样性引入方法或预测方法与常规多目标进化算法相结合来解决。维持种群收敛性和分布性(Convergence and Diversity)的良好平衡对于DMOEAs的性能至关重要。

    解决方案:提出了一种基于决策变量分类的DMOEA(DMOEA-DVC)。 DMOEA-DVC在静态进化和变化响应阶段分别将决策变量分为两个和三个不同的组。在静态进化中,两个决策变量组使用两种不同的交叉算子来加速收敛,同时保持良好的多样性。在变化响应中,DMOEA-DVC分别通过保持,预测和分布性引入策略来重新初始化三个决策变量组。

    实验结果:在33个基准DMOPs上将DMOEA-DVC与其他六个典型的DMOEAs进行了比较。实验结果表明,DMOEA-DVC的总体性能优于或类似于所比较的算法。

    Introduction–引言

    • 从MOEAs 到 DMOEAs遇到的问题
      多目标进化算法(MOEAs)在各种静态多目标优化问题(MOPs)上都取得了成功。但是,由于在动态环境中缺少快速的变化响应机制,在DMOPs中它们往往会失败。
    • 解决方法
      为了解决DMOPs,近年来已经提出了许多动态MOEAs(DMOEAs)。它们大部分可以被分为多样性引入方法(Diversity introduction approaches)和预测方法(prediction approaches)。

    Diversity introduction approaches–多样性引入方法

    多样性引入方法将一定比例的随机或突变个体引入进化种群以增加种群多样性。多样性的增加可以促进算法更好地适应新环境。但是,由于这些算法主要依靠静态进化搜索来找到引入多样性之后的最优解集,因此收敛速度可能会变慢

    prediction approaches–预测方法

    预测方法采用预测模型来预测在变化的环境中有希望的种群。可以大大提高种群收敛性。然而,大多数预测模型需要一个训练周期,在训练周期中预测模型的性能不能令人满意

    主要问题

    都没有考虑决策变量的不同特征。他们倾向于以相同的方式探索所有决策变量,这在平衡种群多样性和收敛性方面效率较低。

    主要亮点(idea)

    提出了基于决策变量分类(DMOEA-DVC)的DMOEA。分别在静态进化和变化响应阶段,使用两种决策变量分类方法将决策变量分为两个和三个不同的组。根据决策变量分类,将不同的进化算子和变化响应策略相应地应用于不同的组,以增强种群的分布性和收敛性。

    1. 在静态进化和变化响应阶段分别使用两种不同的决策变量分类方法,使算法能够更有效地探索不同的决策空间。
    2. 在静态进化中,引入了一种新的子代生成策略,该策略通过对两种不同类型的决策变量使用特定的交叉算子产生子代来加快种群收敛速度,同时保持算法的种群多样性。
    3. 在变化响应中,提出了一种保持,预测和多样性引入相结合的混合响应策略来处理三种类型的决策变量,从而在不同的动态环境中实现更好的适应性。

    Background–背景

    A、DMOP基础

    基于动态帕累托支配找到动态帕累托最优解或动态帕累托前沿面

    1. 定义1(动态帕累托支配):在时间t给出两个候选解x和y(x,y∈Ω),称x支配y,写为x(t)≺y(t),当且仅当
      在这里插入图片描述
    2. 定义2(动态帕累托最优解集):在时间t的一个动态帕累托最优解集记为PS(t),其中包括所有不被其他解支配的解,如下:在这里插入图片描述
    3. 定义3(动态帕累托前沿面):在时间t的一个动态帕累托最优面记为PF(t),是PS(t)中的解在目标函数空间中的映射,如下:
      在这里插入图片描述
    4. 定义4(多最优值变量):给定一个决策变量i,若PS(t)中存在两个解x,y,并且xi≠yi,xi,yi分别指x,y在决策变量i上的值,则称i有多个最优值,是一个多最优值变量。
    5. 定义5(单最优值变量):给定一个决策变量i,对于PS(t)中任意两个解x,y,他们对应的决策变量i值是一样的,即xi=yi,则称i有单个最优值,是一个单最优值变量。

    根据PF(t)和PS(t)的动态特性,将DMOP分为四种类型

    • 类型I: PS(t)随时间变化,而PF(t)是固定的。
    • 类型II: PS(t)和PF(t)都随时间变化。
    • 类型三:PS(t)是固定的,PF(t)随时间变化。
    • 类型IV: PS(t)和PF(t)都是固定的,但是随着时间的推移问题会改变。

    B、动态多目标进化算法

    1. 动态多目标算法(多样性引入)

    通过看下面这个表格就非常直观,最终通过引入多样性方法可以防止种群陷入局部最优,并且易于实施。在这里插入图片描述

    2. 动态多目标算法之(基于预测的方法)

    在这里插入图片描述
    其中基于预测的方法中,也有很多在PPS算法的基础上,进行一些改进,最终也可以显示出提高收敛速度的能力。

    C、决策变量分类方法

    通过结合多样性引入和基于快速预测的方法来利用两者的优点,提出了一种增强的变化响应策略。

    多样性引入或预测方法可以被视为搜索决策变量最优值的概率模型,大多数现有的DMOEAs都假定所有决策变量都处于相同的概率分布下。在实际的DMOPs中,决策变量的概率分布可能会发生很大变化。通过决策变量分类,可以将决策变量分为不同的组,然后可以将特定的概率搜索模型应用于相应的变量组以获得更好的解。

    在静态中的决策变量分类

    许多基于决策变量分类的MOEAs在静态MOPs上都取得了成功,决策变量扰动会产生大量个体用于分类,并成比例地消耗大量适应性评估。此策略对于静态MOPs效果很好,在静态MOPs中,决策变量的类别不变,并且仅需要分类一次。

    在动态中的决策变量分类

    • Woldesenbet和Yen [51]通过对目标空间变化的平均敏感度来区分决策变量,并以此为基础来重新安置个体。 该方法对于动态单目标优化问题效果很好,但是不适用于DMOP。
    • Xu提出了一种针对DMOP的协作式协同进化算法,其中决策变量被分解为两个子组件,即相对于环境变量t不可分离和可分离的变量。应用两个种群分别协同优化两个子组件。文献中提出的算法在基于环境敏感性可分解决策变量的DMOP上具有优越性,但是,在许多DMOP中可能并非如此。

    在这里插入图片描述

    Framework–框架

    在这里插入图片描述
    具体过程:初始化父代种群P,然后从父代种群中选出一个子代种群P′和一个非支配解的档案A。在每次迭代中,在使用进化算子生成每个子代个体之前,对P使用决策变量分类方法,并将结果记录在布尔向量flag_multi中,其中每个元素指示相应的决策变量是多最优还是单最优变量。DMOEA-DVC可检测到进化过程中的任何潜在变化,如果检测到变化,则将使用变化响应策略,否则,将对个体的不同类型决策变量使用不同的交叉算子生成子代个体,生成子代个体后,更新P和A。在每一次迭代的末尾,从当前父代种群和子代种群的混合中选择一个新的子代种群和一个新的档案。

    A、ClassificationSO–决策变量分类

    在静态进化阶段(算法1第6行)使用决策变量分类,以增加生成高质量子代个体的可能性。
    目标:找到在PF上分布均匀的种群,并尽快收敛到PF
    方法:探索种群中非支配个体的邻居是很有效的
    问题:如果子代的所有决策变量都是在非支配个体的决策变量附近生成的,则种群会陷入局部最优,为了避免这种情况,子代个体中的多最优值变量值应远离父代个体产生。

    • 子代中的多最优变量值应该远离非支配个体产生,以保持良好的多样性。
    • 对于单最优变量,子代个体中的生成值应尽可能接近父代个体中的相应值,以加速收敛。

    关键问题:如何确定多最优值变量和单最优值变量

    提出了一种区分多最优值变量和单最优值变量的近似方法。

    在DMOP中,目标函数可能在某些决策变量上相互冲突。如果两个目标函数在决策变量上发生冲突,则该决策变量被视为具有多个最优值。(这个也很好理解,如果在X=C时存在两个最优的解,那么这两个目标相互冲突)

    因此使用斯皮尔曼等级相关系数(SRCC)来衡量一个变量和一个目标函数之间的相关性。
    在这里插入图片描述
    如果第i个变量的两个目标函数之间存在明显的相关冲突(正相关与负相关),即max(ri1(t),ri2(t),…,rim(t))>0.5α并且min(ri1(t),ri2(t),…,rim(t))<-0.5α(α是预定义的阈值),则将第i个决策变量分类为多最优值变量。否则,第i个决策变量将被视为单最优值变量。

    在这里插入图片描述
    首先计算每个决策变量i与每个目标j之间的SRCC值,然后根据SRCC值将决策变量分为多最优值变量(第10行)或单最优值变量(第12行),然后采取上述对应方案。

    Classification–变化响应中决策变量分类

    在大多数现有的DMOPs中,考虑到环境变化,可以将决策变量分类为相似,可预测和不可预测的变量。

    • 相似 —无需重新初始化
    • 可预测 ----决策变量应基于预测进行重新初始化
    • 不可预测 -----可以通过引入多样性进行重新初始化

    非参数t-test用于评估决策变量的变化与环境变化的相关性

    在这里插入图片描述
    t-testi <=β,其中β是预定义的阈值,则第i个变量被视为无明显变化,也就是说,它是相似的变量,不需要重新初始化。如果t-testi>β,则第i个决策变量被认为具有显著变化,即变量i是可预测的或不可预测的,需要重新初始化。

    上面公式已经区分了相似或者可预测和不可预测的情况,现在我们继续区分到底是可预测情况还是不可预测情况。如下图所示

    将x_center的第i个决策变量置为预测值而其他决策变量保持不变来生成n个试验个体x_trial[i],如果x_trial [i]支配x_center,则接受第i个决策变量的预测,并将第i个决策变量分类为可预测变量,并使用基于预测的方法重新初始化。否则,第i个决策变量是不可预测的,并使用基于多样性引入的方法重新初始化
    在这里插入图片描述
    下面就展示算法3 的伪代码
    在这里插入图片描述
    首先,分别根据(7)和(8)计算t-test和x_center。其次,使用预测模型来预测新的个体x_p(确切的预测模型在第IV -C节中进行了描述)。第三,产生试验个体(第6-14行)并进行评估。如果试验个体支配质心个体,则该试验个体的相应决策变量的预测是正确的,否则该预测是不可接受的。

    B、环境选择

    • DMOEA-DVC和SGEA[33]使用相同的选择方法,适应度函数F(i)表示支配个体xi的个体数目
      在这里插入图片描述

    • 如果存档A中个体少于N则从种群中挑选最好的个体进P’,如果刚好相等,就将A中所有个体转入P’,如果存档A中个体多了就从种群中挑选最远的个体进P’.

    C、ChangeResponse --变化响应

    定义的三种类型的决策变量分别使用保持,多样性引入和预测方法。

    • 保持:如果决策变量是相似变量,则DMOEA-DVC会在变化响应中保持该变量的值不变。
    • 多样性引入:如果决策变量是不可预测的变量,则对该变量应用随机重新初始化策略。变量更新如下:
      在这里插入图片描述
      其中,Li(t)和Ui(t)分别表示在时间t处第i个变量的上限和下限,rand是[0,1]中的随机值。
    • 预测方法:如果将决策变量分类为可预测变量,则使用具有较短训练周期的卡尔曼滤波器[25],[33]通过中心预测将其重新初始化。
    • 在这里插入图片描述
      下面就是算法4的伪代码
      在这里插入图片描述

    D、GenerateOffspring --子代生成

    模拟二进制交叉(SBX)或DE交叉算子用于根据决策变量是否为多最优值变量来生成决策变量的值。SBX和DE交叉算子是MOEAs中两个常用的交叉算子。
    在这里插入图片描述
    图1展示了这两个交叉算子生成的子代解的分布示例。SBX生成的子代解更接近父代,而DE交叉生成的子代解远离父代。应该在远离父代的位置生成多最优值变量,在这种情况下应使用DE交叉算子。而单最优值变量应在父代附近生成,即选择SBX。
    在这里插入图片描述
    这个伪代码已经很简单了,如果是多最优值变量就选择DE交叉算子,否则,单优值变量选择SBX交叉算子。

    E、种群更新

    DMOEA-DVC使用与SGEA相同的稳态种群更新策略。种群更新策略在父种群P和档案A中都执行。新生成的子代个体y用于替换P中最差的个体,同时更新A。

    Conclusion

    • 本文提出了一种基于决策变量分类的DMOEA,即DMOEA-DVC。对静态优化阶段和变化响应阶段的决策变量进行了分类。采用不同的策略来生成不同类型变量的值,以达到种群多样性和收敛性的良好平衡。
    • DMOEA-DVC与其他六种最先进的DMOEA在33个基准DMOP上进行了比较。实验结果表明了DMOEA-DVC算法的有效性。

    ps:上面大部分也是根据原文来进行总结以及理解的,由于本人也是才接触多目标进化没多久,学术功底有限,如果有不正确的地方欢迎批评指正!同时也借鉴了这些博客,如果想要了解,可以看
    https://blog.csdn.net/u013555719/article/details/106856234?
    同时这篇文章提到的几种动态多目标的算法,DCOEA、PPS、SGEA、有兴趣大家可以搜索了解一下。
    同时我目前的微信公众号也是“研行笔录”,后期我也会持续更新,如果有兴趣的话,可以点个关注,不迷路!
    在这里插入图片描述

    展开全文
  • 针对由一个低碳产品制造商与一个零售商组成的供应链, 考虑需求同时受减排水平和销售价格的影响, 分别研究寄售契约、收益共享契约以及收益共享与减排成本共担3 种契约下供应链企业的优化决策, 并进一步探讨当需求的...
  • 模型:对模拟环境与个体交互机制的描述,模型包含两个部分: 状态之间的转移概率    状态转移的收益  注意:模型仅对于个体来说的,模型对个体来说也不是必须的;考虑环境的实际规划状态的研究称为环境...

    目录

    1 基本概念

    2 马尔科夫决策过程理论

    2.1 马尔科夫过程(Markov process / Markov Chain)

    2.1.1 状态空间分析:

    2.1.2 转移矩阵描述

    2.2 马尔科夫奖励过程(Markov Reward Process)

    2.2.1 不同任务的奖励及回报值计算方法

    2.2.2 衰减因子  的分析

    2.2.3 马尔科夫奖励过程的值函数及计算示例

    2.3 马尔科夫决策过程(Marlov Decision Process)

    2.3.1 策略

    2.3.2 状态价值函数与状态动作价值函数

    3 动态规划算法求解MDP

    3.1 预测与控制

    3.2 求解算法梳理

    4 值迭代与策略迭代手算及Matlab代码

    4.1 简单粗暴的值迭代方法--求解Small Gridworld例子

    4.1.1 理论部分

    4.1.1 手解过程及自己总结

    4.1.2 Matlab的计算结果实现

    4.1.3 Matlab部分解算结果展示:

    4.2 策略迭代算法

    4.2.1 手算示例分析

    4.2.2 策略迭代的Matlab实现

    4.2.3 运行结果展示

    参考资料:


    写在前面的话

    • 本文为笔者自学马尔科夫过程的新的总结,难免存在疏漏和错误之处;
    • 写作本文的目的是为想学习马尔科夫决策过程的小伙伴提供一些参考
    • 本文的撰写也借鉴了许多优秀的知乎及CSDN博客文章,感谢他们,但是本文在借鉴他们成果的基础上,做了自己的一些改编,不合适之处,欢迎高人批评指正。
    • 由于本人也是初学,旨在对问题概念及原理做最为直白的理解,确保初学者无痛入门
    • 如后期自己发现有疏漏之处,也会自行不断地进行更新和完善

    1 基本概念

    在无监督数据、只有奖励信号;奖励可能是即时的也可能是延迟的;当前行为影响后续状态的收益;时间是一个必须要考虑的因素。强化学习是通过个体与环境的不断交互和反馈积累起对环境的感知,进而一步步的增强自己对环境的认识而尽快的实现自己的目的

    R_{t} 表示个体在 t 时刻的奖励,强化学习的目标就是获得最大化的奖励

    • 序列决策:通过一系列的行为得到决策收益,有时候会放弃短期利益追求长期效益
    • 个体(agent):行动的实际实施者,用于接收信号并做出决定。个体在环境状态 S_{t} 采用动作 A_{t} 得到收益 R_{t+1} 
    • 环境(Environment):接收一个动作 A_{t}, 环境状态变成S_{t+1},反馈给个体一个收益R_{t+1}
    • 行动(action):个体施加在行动中的动作
    • 状态(state):环境接受个体agent的action后,反馈给agent的环境状态,同时还会附加一个奖励reward

    • 历史:状态、动作和收益的序列
    • 马尔科夫性:P(S_{t+1}|S_{t})=P(S_{t+1}|S_{t},S_{t-1}, ..., S_{1}),忽略历史信息,当前状态可以决定未来
    • 策略:状态到行为的映射
    • 价值函数:未来奖励的预测,评价当前状态的好坏。当个体面临几种不同的状态时,他会根据value值来评估不同状态的收益情况,指定相应的策略;也就是说,价值函数是基于某一策略而言的。
      • 对于某一策略\pi,其价值函数可表示为v_{\pi}(s)=E_{\pi}(R_{t+1}+\gamma R_{t+2}+\gamma^{3} R_{t+3}+... | s_{t}=s )
    • 模型:对模拟环境与个体交互机制的描述,模型包含两个部分:
      • 状态之间的转移概率 P_{ss'}^{a}=P[{S_{t+1} | S_{t}=s,S_{t+1}=s',A_{t}=a}] 
      • 状态转移的收益 R_{s}^{a}=E(R_{t+1} | S_{t}=s, A_{t} = a)
      • 注意:模型仅对于个体来说的,模型对个体来说也不是必须的;考虑环境的实际规划状态的研究称为环境动力学
    • 学习与规划:学习是在初始阶段对环境一无所知的时候,通过与环境的不断交互,建立起相应的行为策略;规划是在个体对环境已经了解后,利用建立的模型模拟与环境的交互,从而继续改进所建立的策略。
    • 探索和利用:个体从未知环境中找到一个比较好的策略,有失败的风险;利用则是从已有的策略中选择一个比较好的策略,或许会早熟。比如:你会选择一个新餐厅吃饭 (探索) 还是去你之前去过的餐厅 (利用) 呢?

    2 马尔科夫决策过程理论

    马尔科夫过程基本描述:

    • 马尔科夫性:P(S_{t+1}|S_{t})=P(S_{t+1}|S_{t},S_{t-1}, ..., S_{1})
    • 状态转移概率:P_{ss'}^{a}=P[{S_{t+1} | S_{t}=s,S_{t+1}=s',A_{t}=a}];显然从在任意时刻 t 从当前状态转移到其他状态的概率之和为1

    2.1 马尔科夫过程(Markov process / Markov Chain)

    无记忆过程,包含两个基本要素:<S,P>,其中的 S 表示有限个状态集合,P 表示这些状态之间的转移概率

    马尔科夫链的基本示例

     

    上图模拟了包含S= {Facebook, Class1, Class2, Class3, Pub, Pass,Sleep}七种状态的马尔科夫状态空间,其中圆形状态表示个体所处的状态,方形状态Sleep表示终止状态;不同状态之间的连线上的数值表示这些状态之间的转移概率,箭头表示状态转移的方向。

    2.1.1 状态空间分析:

    • 个体从Class1开始,他有0.5的概率,转移到Class2;也有可能0.5的概率,转移到Facebook状态;
      • 当个体从状态Class1转移到状态Facebook时,他有0.9的概率,继续刷Facebook;也有0.1的概率回到Class;
      • 当个体从状态Class1转移到状态Class2时,他有0.2的概率会因课程太难退出,即Sleep;有0.8的概率,转到Class3;
        • 当个体从状态Class2转移到状态Class3时,他有0.6的概率通过考试,然后退出;有0.4的概率,去图书馆查资料学习;
          • 如果他去图书馆查资料学习,有0.4的概率返回Class1;有0.4的概率,返回Class2;有0.2的概率,返回Class1

    思维导图展示:

    学生上课马尔科夫过程思维导图演示

    2.1.2 转移矩阵描述

    学生选课马尔科夫转移矩阵
     Class1Class2Class3FacebookPubPassSleep
    Class1 0.5 0.5   
    Class2  0.8   0.2
    Class3    0.40.6 
    Pub0.20.40.4    
    Facebook0.9  0.1   
    Pass      1
    Sleep      1

    上图和表解释了马尔科夫过程的两个基本要素:状态空间和状态转移矩阵,下面介绍马尔科夫奖励过程。

    2.2 马尔科夫奖励过程(Markov Reward Process)

    在马尔科夫过程的基础上,加入了奖励R;构成形如<S,P,R,\gamma>的马尔科夫奖励过程;对其四元组的解释如下:

    • S:马尔科夫的状态空间
    • P:马尔科夫的状态转移概率矩阵
    • R:马尔科夫过程的奖励函数
    • \gamma:奖励衰减因子,位于[0, 1]之间;传达的信息是,随着状态的迁移,当前状态的影响在衰减

    2.2.1 不同任务的奖励及回报值计算方法

    注意:

    • 我们将每个状态的即时收益,定义为奖励R_{t};而将对某一个片段的评价,定义为回报G_{t}
    • 短期的叫收益,长期的叫回报,区分开来,以免混淆

    ( 1 ) 回合制任务(episodic task)

    存在一个终止状态,并且所有的奖励会在这个终止状态及其之前结算

    ( 2 ) 连续任务(continuing task)

    不存在一个终止状态,即原则上可以永久地运行下去,这类任务的奖励是分散地分布在这个连续的一连串的时刻中的

    其中衰减率(discount factor)  \gamma 满足 0 \leq \gamma \leq 1 。这样的定义也很好理解,相比于更远的收益,我们会更加偏好临近的收益,因此对于离得较近的收益权重更高。

    2.2.2 衰减因子 \gamma 的分析

    分析性描述:

    • 我们对未来的把握是逐渐衰减的,一般的情况下,我们更关心短时间的奖励
    • 加入衰减因子之后,我们就可通过该参数来调节长时间的回报
    • 衰减因子是MDP和MRP长期回报值有界的保证

    2.2.3 马尔科夫奖励过程的值函数及计算示例

    v(s) & = E(G_{t} | S_{t}=s) \\ &= E(R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + ... | S_{t}=s) \\ &= E(R_{t+1} + \gamma * (R_{t+2} + \gamma R_{t+3} + ...) | S_{t}=s) \\ &= E(R_{t+1} + \gamma * v(S_{t+1})) | S_{t}=s)

    价值函数表示了状态s和状态S_{t+1}之间的迭代关系,也反应了短期奖励与长期回报之间的关系

    如果我们知道状态转移矩阵P,那么式子可转化为:

    v(s) & = R_{t+3} + ...) | S_{t}=s) \\ &= E(R_{t+1} + \gamma * v(S_{t+1})) | S_{t}=s) \\& = E(R_{t+1} | S_{t}=s) + \gamma * E(v(S_{t+1} | S_{t} = s)) \\& = R(s) + \gamma * \sum_{s' \in S} (P_{ss'} v(s'))

    下面是一个例子:

    值函数的计算示例

    2.3 马尔科夫决策过程(Marlov Decision Process)

    在马尔科夫奖励过程的基础上,我们又加入了行动集合,构成 <S,A,P,R,\gamma> 五元组和策略 \pi 形式的马尔科夫决策过程

    几点讨论:

    1. MP和MRP我们作为一个观察者,观察状态的变化来计算回报值;而在MDP中,我们引入了决策,通过改变状态转移的流程,获得最大化的回报
    2. 我们对MDP的奖励变成了对<s,a>的奖励,即通过动作来控制状态的转移

    2.3.1 策略

    • 策略给出了在每个状态下我们应该采取的行动,我们可以把这个策略记做 \pi (a|s),它表示在状态s下采取行动 a 的概率
    • 给定状态下的动作概率的集合,这些所有的概率的加总起来,和值为1。
    • 策略是对agent行为的全部描述,一旦策略确定智能体的行为也将确定。
    • 策略是基于马尔科夫状态,是时间稳定的,只与状态有关,而与时间无关
    • 如果给定策略 \pi,MDP将会退化为MRP问题

    • 当策略确定时,对应的是一组动作集合;当策略随机时,对应的是一组动作分布集合

    如果我们可以计算出每个状态或者采取某个行动之后收益,那么我们每次行动就只需要采取收益较大的行动或者采取能够到达收益较大状态的行动。这就是策略迭代的核心所在。

    2.3.2 状态价值函数与状态动作价值函数

    两个状态价值函数对应两个贝尔曼方程,对应值迭代和策略迭代算法,两个公式的用途不同,千万不能混淆。

    (1) 状态价值函数(V_{\pi}(s),state value function)

    v_{\pi}(s) \\ = E_{\pi}(G_{t} | S_{t} = s) \\ = E_{\pi}(R_{t+1} + \gamma * v_{\pi}(S_{t+1}) | S_{t} = s)

    在当前状态s一直采用策略\pi,能够产生的期望收益

    个人观点:

    • 如果你只给出一个策略,使用值迭代算法更新至值函数收敛,你将得到了这个策略下的最优决策,这样的计算模式只涉及到上式的前两行部分;因为只有一个策略,所有的\pi (a|s)就是确定的。
    • 上面公式的通俗解释是,我在状态 s 处以概率 \pi (a|s) 采取行动 a,采取行动 a 之后,状态 s 能够以概率 p(s',r | s,a) 转移到状态 s' 。 
    • 对于策略 \pi ,我们可以定义如下贝尔曼方程:

    (2) 状态动作价值函数(Q_{\pi}(s,a), action value function)

    q_{\pi}(s,a) \\ = E_{\pi}(G_{t} | S_{t} = s, A_{t}=a) \\ = E_{\pi}(R_{t+1} + \gamma * q_{\pi}(S_{t+1},A_{t+1}) | S_{t} = s, A_{t}=a)

    当前状态s,如果采用行动a,接下来采用策略\pi,能够产生的期望收益

    • 如果我们我们能够求得某策略下的价值函数,我们就可以对该策略进行评估
    • 如果我们能够得到最优状态的价值函数,我们就可以得到最优策略

    (3) 状态值函数与状态动作值函数区别与联系分析

    • 状态价值函数,策略是确定的;而状态动作价值函数,采取某个行动之后,选择不同的策略能够得到的预期收益
    • 状态价值函数,对应于值迭代算法;行动价值函数,对应策略迭代算法

    联系:

    • 两个函数的最终目的都是要得到最优的期望收益,用【殊途同归】一词描述最为合适

     

      

     一个计算的示例

    \upsilon\left(s_4\right)=0.5*\left(1+0.2*\left(-1.3\right)+0.4*2.7+0.4*7.4\right)+0.5*10=7.39

     

    3 动态规划算法求解MDP

    动态表示研究的过程是具有时序特征,规划是一种优化策略;所以动态规划是指将研究问题分解成许多个子问题,通过不断的求解子问题一步一步递归得到原问题的解决方案。

    对于我们研究的马尔科夫过程,由于贝尔曼方程的存在,使其具备使用动态规划求解的基本特征;不过要想使用动态规划来求解MDP的话,MDP必须具有明确的模型,事先知道完全的信息。【根据状态和行动的价值函数,计算每个状态的最优策略,最后串起来】

    3.1 预测与控制

    • 预测是求解给定策略下的价值函数的过程
    • 控制是找到一个策略以获得最大化的收益,即从所有的可能策略中选择最优的价值函数和最优策略

    MDP的动态规划算法的主体思路为:先给一个策略,预测出他的最优值函数;然后在使用控制策略,得到最优策略

    策略迭代方法:要进行策略迭代,首先要进行策略评估,也就是评估一下目前的几个选择的好坏,因为只有你当前的选择好了,你才更可能做出整体上比较好的选择;在DS的视频中,提出了“one step look ahead”理念,就是说我计算当前值函数的时候,要使用到上一个值函数的数据来构建;

    3.2 求解算法梳理

    (1) 策略评估

    概念:评估一个给定的策略,属于预测的范畴

    计算公式:

    说明:一次迭代内,状态s的价值等于前一次迭代该状态的即时奖励与所有s的下一个可能状态s' 的价值与其概率乘积的和

    (2) 策略改善

    采取那个(些)使得状态价值得到最大的行为,进行策略更新。

    1.   考虑一个确定的策略: a=\pi_{s}
    2. 通过贪婪计算优化策略:\pi'(s) = argmax_{a \in A}q_{\pi}(s|a)  
    3. 这会用1步迭代改善状态s的q值,即在当前策略下,状态s在动作π’(s)下得到的q值等于当前策略下状态s所有可能动作得到的q值中的最大值。这个值一般不小于使用当前策略得到的行为所的得出的q值,因而也就是该状态的状态价值。
    4. 如果q值不再改善,则在某一状态下,遵循当前策略采取的行为得到的q值将会是最优策略下所能得到的最大q值,上述表示就满足了Bellman最优方程,说明当前策略下的状态价值就是最优状态价值。
    5. 因而此时的策略就是最优策略。 

    (3) 策略迭代

    在当前策略上迭代计算 v 值,再根据 v 值贪婪地更新策略,如此反复多次,最终得到最优策略 \pi^{*} 和最优状态价值函数 V^{*}  

    策略迭代算法流程示意图

     

    (4) 价值迭代

    概念:从初始状态价值开始同步迭代计算,最终收敛,整个过程中没有遵循任何策略。

    公式定理:

    说明:与策略迭代不同,在值迭代过程中,算法不会给出明确的策略,迭代过程其间得到的价值函数,不对应任何策略;价值迭代虽然不需要策略参与,但仍然需要知道状态之间的转移概率,也就是需要知道模型。

    4 值迭代与策略迭代手算及Matlab代码

    4.1 简单粗暴的值迭代方法--求解Small Gridworld例子

    值迭代算法流程图

    4.1.1 理论部分

    一个4×4的小网格世界,左上角和右下角是目的地

    每个格子行动方向为上下左右,每走一步reward-1

    求一个在每个状态都能以最少步数到达目的地的最优行动策略。

    解决思路:我们从最开始的随机(1/4)策略开始,对其进行policy evaluation, 然后进行policy iteration by acting greedy

    4.1.1 手解过程及自己总结

    展示k=2到k=3的计算过程:

    0 = 【第一行第一个格子】

    这是结束的位置,应该保持不动

    -2.375 =

       【第一行的第二个格子】
    +    0.25 * (-1 + 1 * (-1.7))

         上【-0.675】
    +    0.25 * (-1 + 1 * (0))

         左【-0.25】
    +    0.25 * (-1 + 1 * (-2)) 

        下【-0.75】
    +    0.25 * (-1 + 1 * (-2)) 

        右【-0.75】

    -2.875 =

       【第一行的第三个格子】
    +    0.25 * (-1 + 1 * (-2))

      上【-0.75】
    +    0.25 * (-1 + 1 * (-1.7)) 

       左【-0.625】
    +    0.25 * (-1 + 1 * (-2))

        下【-0.75】
    +    0.25 * (-1 + 1 * (-2))

        右【-0.75】

    -3.0 =

          【第一行的第四个格子】
    +    0.25 * (-1 + 1 * (-2))

       上【-0.75】
    +    0.25 * (-1 + 1 * (-2)) 

       左【-0.75】
    +    0.25 * (-1 + 1 * (-2))

        下【-0.75】
    +    0.25 * (-1 + 1 * (-2))

        右【-0.75】

    -2.425 =

    【第二行第一列】
    +    0.25 * (-1 + 1 * (0))

    上【-0】
    +    0.25 * (-1 + 1 * (-1.7))

        左【-0.625】
    +    0.25 * (-1 + 1 * (-2))

        下【-0.75】
    +    0.25 * (-1 + 1 * (-2)) 

       右【-0.75】

    -2.75 =【第二行第二列】
    +    0.25 * (-1 + 1 * (-1.7)) 上【-0.625】
    +    0.25 * (-1 + 1 * (-1.7))    左【-0.625】
    +    0.25 * (-1 + 1 * (-2))    下【-0.75】
    +    0.25 * (-1 + 1 * (-2))    右【-0.75】
    -3.0 = 【第二行第三列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-2))    下【-0.75】
    +    0.25 * (-1 + 1 * (-2))    右【-0.75】
    -2.875 = 【第二行第四列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-1.7))    下【-0.625】
    +    0.25 * (-1 + 1 * (-2))    右【-0.75】
    -2.875 =【第三行第一列】
    +    0.25 * (-1 + 1 * (-1.7)) 上【-0.625】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-2))    下【-0.75】
    +    0.25 * (-1 + 1 * (-2))    右【-0.75】
    -3.0 =【第三行第二列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-2))    下【-0.75】
    +    0.25 * (-1 + 1 * (-2))    右【-0.75】
    -2.75 = 【第三行第三列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-1.7))    下【-0.625】
    +    0.25 * (-1 + 1 * (-1.7))    右【-0.625】
    -2.375 = 【第三行第四列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-0))    下【-0.25】
    +    0.25 * (-1 + 1 * (-1.7))    右【-0.625】
    -3.0 =【第四行第一列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.625】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-2))    下【-0.75】
    +    0.25 * (-1 + 1 * (-2))    右【-0.75】
    -2.875 =【第四行第二列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-2))    下【-0.75】
    +    0.25 * (-1 + 1 * (-1.7))    右【-0.625】
    -2.375 = 【第四行第三列】
    +    0.25 * (-1 + 1 * (-2)) 上【-0.75】
    +    0.25 * (-1 + 1 * (-2))    左【-0.75】
    +    0.25 * (-1 + 1 * (-1.7))    下【-0.625】
    +    0.25 * (-1 + 1 * (0))    右【-0.25】
    -0 = 【第四行第四列】

    通用的总结(k+1步的计算是从k步的值矩阵中取值来计算):

    某个格子的值 = 0.25 * (即时奖励[-1]  +  折扣因子[1] * k步矩阵上方的值)    【上】
                          + 0.25 * (即时奖励[-1]  +  折扣因子[1] * k步矩阵左方的值)    【左】 
                          + 0.25 * (即时奖励[-1]  +  折扣因子[1] * k步矩阵下方的值)    【下】
                          + 0.25 * (即时奖励[-1]  +  折扣因子[1] * k步矩阵右方的值)    【右】

    4.1.2 Matlab的计算结果实现

    程序设计思路为:

    1. 构建gridRow * gridCol大小的图形
    2. 初始化值函数,并定义当前值函数和上一步值函数;初始化折扣因子、即时奖励、终止阈值、策略概率
    3. 按照前一部分总结的规律,依照【上->左->下->右】的顺序,迭代更新值函数;注:程序将边界点和内点分开计算
    4. 判断更新后的值函数与上一步的值函数是否满足终止阈值;若是返回,得到收敛的值函数;否则继续迭代
    clc;clear;
    %初始化格网的行数
    girdRow = 4;
    gridCol = 4;
    %初始化值函数、当前值函数和上一期值函数
    v = zeros(girdRow,gridCol);
    v_cur = v;
    v_before = v;
    %折扣因子
    gamma = 1;
    %即时奖励
    reward = -1;
    %策略概率
    policyPossibility = 0.25;
    %终止阈值:两次的值函数差值小于给定阈值,认为得到了最优的值函数
    theta = 0.00001;
    
    %迭代变量
    iter = 0;
    while true  
        %迭代变量递增1
        iter = iter + 1;
        %遍历所有的格子
        for i = 1:girdRow
            for j = 1:gridCol
                %第一行的第一个格子
                if(i == 1 && j == 1)
                    v_cur(i,j) = v_before(i,j);
                end
                
                %第一行其他格子
                if(i == 1 && j ~= 1)
                    if (j ~= gridCol)
                        %上左下右
                        v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j-1)) ...
                        + policyPossibility * (reward + gamma * v_before(i+1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i, j+1));
                    else
                        v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j-1)) ...
                        + policyPossibility * (reward + gamma * v_before(i+1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i, j));
                    end
                end
                %第1列其他格子
                if (j == 1 && i ~= 1)
                     if (i ~= girdRow)
                        v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i-1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i+1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i, j+1));
                    else
                        v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i-1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j+1));
                     end              
                end
                %第4列非首行格子
                if (j == gridCol && i ~= 1)
                     if (i ~= gridCol)
                        v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i-1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j-1)) ...
                        + policyPossibility * (reward + gamma * v_before(i+1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i, j));
                    else
                        v_cur(i,j) =  0;
                     end              
                end
                %第4行非首列格子
                if (i == girdRow && j ~= 1 && j ~= gridCol)
                    v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i-1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j-1)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i, j+1));
                end
                
                %非边界行的计算
                if (i~= 1 && i ~= girdRow && j ~= gridCol && j ~= 1)
                    v_cur(i,j) =  policyPossibility * (reward + gamma * v_before(i-1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i,j-1)) ...
                        + policyPossibility * (reward + gamma * v_before(i+1,j)) ...
                        + policyPossibility * (reward + gamma * v_before(i, j+1));
                end
            end
        end
        disp(sprintf('第%d次的解算结果为:',iter))
        v_cur %输出当前值函数
        if (max(abs(v_cur(:)-v_before(:))) < theta)
            break;
        else
            v_before = v_cur;
        end
    end
    

    4.1.3 Matlab部分解算结果展示:

    算法在设定的阈值内迭代了215次,最终输出的收敛结果为:

    4.2 策略迭代算法

    即使我们得到最优的值函数,我们还需要将其转化为具体的策略,而通过上面的例子我们的发现k=3与k=10的值函数不同,但对应的策略是完全相同的。故可以说我们仅需要迭代三次就得到了最优的策略,我们后面做的工作其实是无用功。

    详细分析我们的值迭代的思路,发现我们自始至终沿用的都是均匀概率分布的策略;如果我们能在搜索的过程中根据值函数来更新策略,我们将有可能更快的得到想要的结果。正是基于这样的想法,我们的策略迭代算法就产生,其原理是这样的【自己悟的,专业人士勿喷】:

    1. 首先我们随机初始化一个策略,我们沿着这个策略进行值函数迭代,如果值函数发生变化,说明还没有得到最优的值函数,需要继续迭代,此时我们并不是直接对得到的值函数进行操作,而是根据值函数反应的信息,进行策略更新
    2. 然后,使用更新后的策略,进行值函数的更新;如此往复,直到我们的值函数收敛或策略不再发生变化时,我们研究问题的满意解,甚至是最优解。
    策略迭代流程图

    插播别人的一段分析:伪代码的第3行表示策略改进,即固定价值函数,得到其最优策略;伪代码第4行的策略评估,即固定策略,得到其价值函数。

    改进策略迭代流程图

    改进策略迭代的分析:

    1. m_{t}=1时,相当于只有一个策略,改进策略迭代算法等同于值迭代算法。结合策略评估的定义,我们仅在一个固定策略下,得到了其价值函数,也就是我们只做了一次策略评估。
    2. m_{t}=\infty时,改进策略迭代算法等同于策略迭代算法。
    3. 改进策略迭代是值迭代算法与策略迭代算法的统一,目的都是为了找到最优的行动策略

    4.2.1 手算示例分析

    专业的公式我也看不懂,搞不明白,自己就发挥一下我的笨蛋大脑,写下下面这个部分,如有错误,欢迎指正。

    再来分析之前出现的这个图,经过k=1的迭代,发现了新的策略:

    • 比如第2行第1列的格子,其上左下右的值分别为-2.0、-2.0、-1.7、0.0,显然最大值函数对应方向为当前格子的上方;
    • 以第2行第2列的格子,其上左下右的值分别为-1.7、-1.7、-2.0、-2.0,出现了两个最大值,即上方和左方
    • 以第2行第3列的格子,其上左下右的值均为-2.0,出现了四个最大值

    于是我就猜想,我们是不是可以做如下策略变换:

    • (row = 2,col = 1)处的策略,由\pi = \{0.25,0.25,0.25,0.25\}变成\pi = \{1,0,0,0\}
    • (row=2,col=2)处的策略,由\pi = \{0.25,0.25,0.25,0.25\}变成\pi = \{0.5,0.5,0,0\}
    • (row=2,col=3)处的策略,由\pi = \{0.25,0.25,0.25,0.25\}保持不变

    由此,对于k=2,我们得到新的策略集PI:

    {0,0,0,0}{0,1,0,0}{0,1,0,0}{0.25,0.25,0.25,0.25}
    {1,0,0,0}{0.5,0.5,0,0}{0.25,0.25,0.25,0.25}{0,0,1,0}
    {1,0,0,0}{0.25,0.25,0.25,0.25}{0,0,0.5,0.5}{0,0,1,0}
    {0.25,0.25,0.25,0.25}{0,0,0,1}{0,0,0,1}{0,0,0,0}

    基于更新后的策略,我们计算新的值函数,

    0

    -1

    = 1 * ((-1) + 1 * (0))【左】

    -2.7 

    =    1 * ((-1) + 1 * (-1.7))【左】

    -3.0
    =    0.25 * (-1 + 1 * (-2))  【上】
    +    0.25 * (-1 + 1 * (-2))  【左】
    +    0.25 * (-1 + 1 * (-2))  【下】
    +    0.25 * (-1 + 1 * (-2))  【右】

    -1

    = 1 * ((-1) + 1 * (0))【上】

    -2.7
    =    0.5 * (-1 + 1 * (-1.7)) 【上】
    +    0.5 * (-1 + 1 * (-1.7)) 【左】
    -3.0 
    =    0.25 * (-1 + 1 * (-2)) 【上】
    +    0.25 * (-1 + 1 * (-2)) 【左】
    +    0.25 * (-1 + 1 * (-2))  【下】
    +    0.25 * (-1 + 1 * (-2))  【右】

    -2.7

    =     1 * (-1 + 1 * (-1.7))【下】

    -2.7

    = 1 * (-1 + 1 * (-1.7))【上】

    -3.0 
    =    0.25 * (-1 + 1 * (-2)) 【上】
    +    0.25 * (-1 + 1 * (-2)) 【左】
    +    0.25 * (-1 + 1 * (-2))  【下】
    +    0.25 * (-1 + 1 * (-2))  【右】
    -2.7
    =    0.5 * (-1 + 1 * (-1.7)) 【上】
    +    0.5 * (-1 + 1 * (-1.7)) 【左】
    -1 = 1 * ((-1) + 1 * (0))【下】
    -3.0 
    =    0.25 * (-1 + 1 * (-2)) 【上】
    +    0.25 * (-1 + 1 * (-2)) 【左】
    +    0.25 * (-1 + 1 * (-2)) 【下】
    +    0.25 * (-1 + 1 * (-2)) 【右】

    -2.7 

    =    1 * ((-1) + 1 * (-1.7))【右】

    -1

    = 1 * ((-1) + 1 * (0))【右】

    0

    这样我们就得到了新的值函数,再由新的值函数进行策略更新,得到了下边的策略集:

    {0,0,0,0}{0,1,0,0}{0,1,0,0}{0,0.5,0.5,0}
    {1,0,0,0}{0.5,0.5,0,0}{0.25,0.25,0.25,0.25}{0,0,1,0}
    {1,0,0,0}{0.25,0.25,0.25,0.25}{0,0,0.5,0.5}{0,0,1,0}
    {0.5,0,0,0.5}{0,0,0,1}{0,0,0,1}{0,0,0,0}

    发现更新后的新策略居然跟之前的一样,是不是很神奇;这样我们就一路贪心的找到了最优策略。

    这里还存在一个疑问,为啥在第2行第3列和第3行的第2列的策略不是四个方向呢?大神画的图,咱也不敢质疑,有高人可以解惑的不胜荣幸。

    为什么要这么做能?我在想通过值函数我已经判断了某些方向的迭代预期是比较差的,我们就可以从中间选择那些好的让他去迭代呀;在我们的问题中,如果出现一个好的方向,我们以后就奔着这个好的方向去了;如果出现多个好的方向,我们也不知道那个方向更好,那就等概率的往这些方向去呗,反正走着走着,我们的美好生活就来了。

    4.2.2 策略迭代的Matlab实现

    基于上面的分析,我开发了Matlab程序,代码如下:

    设计到三个函数:

    函数名功能
    valueToPolicy根据值函数进行策略更新[使用负无穷-inf表示了跳出边界的行为]
    singleVI根据策略进行值函数更新
    getOptState给定某一状态的行为值函数,得到最优行为

    状态最优行为更新

    function policy = getOptState(actionVal)
    policy = zeros(length(actionVal),1);
    maxValue = max(actionVal);
    prob = 1 / sum(actionVal(:) == maxValue);
    for i = 1:length(actionVal)
        if(actionVal(i) == maxValue)
            policy(i) = prob;
        end
    end
    end

    策略更新函数

    %根据值函数更新策略
    function policy = valueToPolicy(value)
    rowCnts = size(value,1);
    colCnts = size(value,2);
    tmpPolicyFlag = zeros(rowCnts * colCnts, 4);
    %定义极小数值M,将那些预跳出网络的操作设置为该值
    M = -inf;
    for row = 1:rowCnts
        for col = 1:colCnts
            %第一行
            if(row == 1)
                 %第一行的第一个格子【上左下右】
                if(col == 1)
                    tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row, col), value(row, col), value(row+1, col), value(row, col+1)]);
                elseif(col < colCnts)
                    tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([M, value(row, col-1), value(row+1, col), value(row, col+1)]);
                else
                    tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([M, value(row, col-1), value(row+1, col), M]);
                end          
            end
           %最后一个格子
           if(col == colCnts && row == rowCnts)
                tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row-1, col), value(row, col-1), value(row, col), value(row, col)]);
           end
            %第一列非首行
            if(col == 1 && row ~= 1)
                if(row ~= rowCnts)
                 tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row-1, col), M, value(row+1, col), value(row, col+1)]);
                else
                   tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row-1, col), M, M, value(row, col+1)]); 
                end
            end
            
            %最后一列非尾行
            if(col == colCnts && row ~= 1 && row ~= rowCnts)
                 tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row-1, col), value(row, col-1), value(row+1, col), M]);
            end
            %最后一行掐头去尾
            if(row == rowCnts && col ~= colCnts && col ~= 1)
               tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row-1, col), value(row, col-1), M, value(row, col+1)]);
            end
            %非边界行
            if(row ~= rowCnts && row ~= 1 && col ~= colCnts && col ~= 1)
               tmpPolicyFlag((row - 1) * colCnts + col,:) = getOptState([value(row-1, col), value(row, col-1), value(row+1, col), value(row, col+1)]);
            end
        end
    %输出更新之后的策略   
    policy = tmpPolicyFlag;
    end

    值函数更新

    function [v_cur] = singleVI(v_before, policy, gamma, reward, gridRow, gridCol)
    v_cur = v_before;
    %遍历所有的格子
        for i = 1:gridRow
            for j = 1:gridCol
                %第一行的第一个格子
                if(i == 1 && j == 1)
                    v_cur(i,j) = v_before(i,j);
                end
                
                %第一行其他格子
                if(i == 1 && j ~= 1)
                    if (j ~= gridCol)
                        %上左下右
                        v_cur(i,j) =  policy((i-1) * gridCol + j, 1) * (reward + gamma * v_before(i,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j-1)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i+1,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i, j+1));
                    else
                        v_cur(i,j) =  policy((i-1) * gridCol + j,1) * (reward + gamma * v_before(i,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j-1)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i+1,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i, j));
                    end
                end
                %第1列其他格子
                if (j == 1 && i ~= 1)
                     if (i ~= gridRow)
                        v_cur(i,j) =  policy((i-1) * gridCol + j,1) * (reward + gamma * v_before(i-1,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i+1,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i, j+1));
                    else
                        v_cur(i,j) =  policy((i-1) * gridCol + j,1) * (reward + gamma * v_before(i-1,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i,j+1));
                     end              
                end
                %第4列非首行格子
                if (j == gridRow && i ~= 1)
                     if (i ~= gridCol)
                        v_cur(i,j) =  policy((i-1) * gridCol + j,1) * (reward + gamma * v_before(i-1,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j-1)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i+1,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i, j));
                    else
                        v_cur(i,j) =  0;
                     end              
                end
                %第4行非首列格子
                if (i == gridRow && j ~= 1 && j ~= gridCol)
                    v_cur(i,j) =  policy((i-1) * gridCol + j,1) * (reward + gamma * v_before(i-1,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j-1)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i, j+1));
                end
                
                %非边界行的计算
                if (i~= 1 && i ~= gridRow && j ~= gridCol && j ~= 1)
                    v_cur(i,j) =  policy((i-1) * gridCol + j,1) * (reward + gamma * v_before(i-1,j)) ...
                        + policy((i-1) * gridCol + j,2) * (reward + gamma * v_before(i,j-1)) ...
                        + policy((i-1) * gridCol + j,3) * (reward + gamma * v_before(i+1,j)) ...
                        + policy((i-1) * gridCol + j,4) * (reward + gamma * v_before(i, j+1));
                end
            end
        end
    
    end

    主测试程序:值函数全部初始化为0,策略为各方向为0.25

    clc;clear;
    %初始化格网的行数
    gridRow = 4;
    gridCol = 4;
    %初始化值函数、当前值函数和上一期值函数
    v = zeros(gridRow,gridCol);
    v_cur = v;
    v_before = v;
    %折扣因子
    gamma = 1;
    %即时奖励
    reward = -1;
    %定义1-2-3-4来表示行为方向,上左下右
    action_direct = [1,2,3,4];
    %定义初始策略
    policy = [0.25,0.25,0.25,0.25;  0.25,0.25,0.25,0.25;    0.25,0.25,0.25,0.25;    0.25,0.25,0.25,0.25;
              0.25,0.25,0.25,0.25;  0.25,0.25,0.25,0.25;    0.25,0.25,0.25,0.25;    0.25,0.25,0.25,0.25;
              0.25,0.25,0.25,0.25;  0.25,0.25,0.25,0.25;    0.25,0.25,0.25,0.25;     0.25,0.25,0.25,0.25;
              0.25,0.25,0.25,0.25;  0.25,0.25,0.25,0.25;    0.25,0.25,0.25,0.25;     0.25,0.25,0.25,0.25];
    value = [0,0,0,0; 0,0,0,0;  0,0,0,0; 0,0,0,0];
    %初始值和策略
    oldValue = value;
    oldPolicy = policy;
    %最终值和策略
    finalPolicy = policy;
    finalValue = value;
    %循环迭代
    iter = 0;
    while(1)   
        iter = iter + 1;
        newValue = singleVI(oldValue,oldPolicy,gamma, reward, gridRow,gridCol);
        newPolicy = valueToPolicy(newValue);
        if(newPolicy == oldPolicy)
            fprintf('第%d次的解算结果为:',iter)
            finalPolicy = newPolicy;
            finalValue = newValue;
            break;
        end
        oldPolicy = newPolicy;
        oldValue = newValue;
    end
    
    finalPolicy
    finalValue

    4.2.3 运行结果展示

    第3次的解算结果为:
    finalPolicy =

                           0.5                       0.5                         0                         0
                             0                         1                         0                         0
                             0                         1                         0                         0
                             0                       0.5                       0.5                         0
                             1                         0                         0                         0
                           0.5                       0.5                         0                         0
                          0.25                      0.25                      0.25                      0.25
                             0                         0                         1                         0
                             1                         0                         0                         0
                          0.25                      0.25                      0.25                      0.25
                             0                         0                       0.5                       0.5
                             0                         0                         1                         0
                           0.5                         0                         0                       0.5
                             0                         0                         0                         1
                             0                         0                         0                         1
                             0                         0                       0.5                       0.5


    finalValue =

         0    -1    -2    -3
        -1    -2    -3    -2
        -2    -3    -2    -1
        -3    -2    -1     0

     

    可知,进行了3次迭代我们边找了最优策略,终点的两个0.5可以忽略,我们按照其余非0元素所在的位置,按照上左下右的顺序,既可以解析出每个状态的最优行为策略。

     

    参考资料:


    如果喜欢我的分享,可关注以下两个公众帐号

    展开全文
  • 决策

    2018-05-08 22:36:42
    决策树是基于树结构来进行决策,这恰是人类在面临决策问题时一种很自然的处理机制。例如,我们要对“这是好瓜吗?”这样的问题进行决策时,通常会进行一系列的判断或“子决策”:我们先看“它是什么颜色?”,如果是...
  • 论文研究-碳交易机制对物流配送路径决策的影响研究.pdf, 针对碳排放交易机制下的物流配送路径问题,引入考虑车辆载重和速度的碳排放度量方法,以TSP为基本参考模型,...
  • 史上最强Tomcat8性能优化

    万次阅读 多人点赞 2019-10-25 15:33:32
    文章目录授人以鱼不如授人以渔目的服务器资源Tomcat配置优化Linux环境安装运行Tomcat8AJP连接执行器(线程池)3种运行模式部署测试用的web项目查看服务器信息部署web应用使用Apache JMeter进行性能测试下载安装修改...
  • 中国五矿集团公司由建国初期的单纯经营金属矿产品进出口...完善投资决策创新机制与方法,通过投资备案管理、项目授权及发布各项专业操作指引等措施,保障决策效率的提高;建立清晰投资决策流程,明确投资决策内部问责制度
  • 决策咨询

    2009-06-29 23:06:00
    而我国目前无论是政府部门内部的政策研究室,还是各大高校、社科院的研究所,受条块分割体制严重,运行机制不灵活,他们的计划、人事、财务等都受到了过多的制约。很难针对人们关心的重大问题,自行选题进行深入地...
  • SQL优化:索引优化

    万次阅读 2017-08-22 08:18:08
     SQL索引在数据库优化中占有一个非常大的比例, 一个好的索引的设计,可以让你的效率提高几十甚至几百倍,在这里将带你一步步揭开他的神秘面纱。  1.1 什么是索引?  SQL索引有两种,聚集索引和非聚集索引,...
  • 机器学习实战(三)——决策

    万次阅读 多人点赞 2018-03-13 22:23:50
    决策树 3.1 决策树的构造 3.1.1 信息增益 3.1.2 编写代码计算经验熵 3.1.4利用代码计算信息增益 3.2 决策树的生成和修剪 3.2.1 决策树的构建 1. ID3算法 2. C4.5的生成算法 3. 决策树的剪枝 3.2.2 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,830
精华内容 23,932
关键字:

优化决策机制