动态环境下基于近似动态规划的分布估计算法研究

2014-11-19 05:07孙思雨孙良旭苏晓磊赵环宇
电脑知识与技术 2014年30期

孙思雨 孙良旭 苏晓磊 赵环宇

摘要:论文重点讨论了分布估计算法的理论研究。首先,抽取出分布估计算法的核心思想,然后旨在使用EDA算法解决复杂优化问题,提出基于近似动态规划的分布估计算法。通过Agent与环境的交互,将近似动态规划引入到进化计算中,获得概率模型并进行适应性的更新。测试函数使用六个经典的对比实验,结果表明本算法的鲁棒性,运行时间短并具有较强的全局搜索能力,可以作为解决函数优化问题的有效解决算法。

关键词:分布估计算法;近似动态规划;进化搜索

中图分类号:TP391 文献标识码:A 文章编号:1009-3044(2014)30-7173-04

1 分布估计算法

为克服遗传算法由于染色体重新排列导致的链式问题,分布估计算法(estimation of Distribution Algorithm, EDA)不使用交叉和变异操作,而是通过从发现的信息来优化解集,并使用这些信息生成新的概率分布模型和解。概率模型使用全新的进化计算的思路,成为EDA算法的理论基础。EDA算法[1]的概念最初在1996年提出并得到了快速发展,近年来成为智能进化领域的研究热点。EDA算法[2-4]提出了一种全新的进化模式,通过概率模型描述候选解的空间分布,并利用概率模型随机采样生产新种群,实现种群的进化过程。避免盲目地重组和混合染色体的基因,能有效的增强搜索效率,快速生成高可靠性的解,这是传统的遗传算法无法解决的问题。

2 基于近似动态规划的EDA算法

2.1 问题描述

分析发现现存的分布估计算法没有较好的执行效果大多是因为概率向量通常都采用一种固定的策略来进行更新,这种方式不仅无法保证整个进化过程的策略的有效性,同时没有考虑到进化基因位的差异。如果每个基因位概率的相应值在进化更新过程中能够被自适应更新,将有助于改进进化搜索的执行效率。为了获取自适应更新的概率向量,将每个基因位与Agent相关联,并根据动作选择概率更新规则。这样,每一次更新的概率值转换为agent执行一个动作。如果群组随着环境进一步的进化,每个agent都能够使用强化学习的方法,与环境交互来寻找最优的动作策略。

Q学习作为经典的强化学习算法不需要估计环境模型,只需要通过Q函数的迭代计算来获得最优的动作策略,动作策略将会随着agent的不断学习而更新。该文提出的基于Q学习的分布估计算法(QEDA)就是基于这个概念。

2.2 算法设计

基于Q学习的分布估计算法能够解决二进制编码,种群规模位N,编码长度为m,初始的概率向量表示为p(t)=(p1(t), p2(t)……pm(t)),其中pi(t)表示第i个基因位取1的概率。每次迭代包括选择、更新概率模型和采样以及其他操作。

采样操作与PBIL、UMDA等相似的算法使用蒙特卡罗方法,根据概率向量随机产生N个个体的种群。根据每一代的最优子群的适应度来选择参数,同时根据选择比r(0

Q学习算法更新pi(t),需要每个基因位都与一个agent相关联,而且与相应的每一代的组群位作为环境同步进化。环境状态的定义是能够识别基因位在在进化过程的不同阶段,因此,根据gi(t)和bi(t)来定义状态之间的关系。

定义一个较大的频阈集[θhigh],较小的频阈定义为[θlow],[θdiff]被定义为频率差,Agenti前t代的状态被划分为:

1)[gi(t)>θhigh]且[bi(t)>θhigh],或者[gi(t)<θlow]且[bi(t)<θlow];

2) [gi(t)-bi(t)>θdiff];

3) 不满足上述条件的其他情况

Agenti,第一代种群的动作t集合包括如下概率更新规则:

1)动作1:概率降低[Pi(t+1)=βpi(t)] (0)

2) 动作2:概率增加[Pi(t+1)=1-β[1-pi(t)]] (1)

3) 动作3:概率值不变[Pi(t+1)=pi(t)] (2)

式(0)~(2)中i=1,2……m, [β(0<β<1)]是学习速率。Agenti与环境进行交换,可以选择合适的动作来获得并产生下一点的概率pi(t+1)。为了将Agenti存储到Q表中,定义Q矩阵:[Qi=[Qi(sj,ak)]3×3] (3)

每次迭代算法,每个Agenti使用[ε]贪婪策略选择动作,跟转换后的回报和状态更新Q表的值。第一代t-1时刻Agenti的状态为s,选择执行动作a,状态转换为s。使用式(4)、(5)更新[Qi(s,a)]:

[Qi(s,a)←Qi(s,a)+α[ri(t-1)+γmaxQi(s',a')-Qi(s,a)]] (4)

其中[ri(t-1)=1 |pi(t)-gi(t)|<|pi(t-1)-gi(t-1)|-1 otherwise] (5)

[ri(t-1)]表示Agenti在t-1时刻获得的直接回报。

基于Q学习的分布估计算法可以描述为以下步骤。算法代替精英策略群组,保证最优解搜索而不发生退化。

算法1:基于Q学习的分布估计算法

步骤2:初始化Qi=0,i=1,2……m;设置P(1)=(0.5,0.5……0.5),t=1。

步骤3: While(终止条件不满足)do

步骤4:根据P(t)采样第N-1代的种群,并使用最优的个体代表当前群组。新个体确定第i位值:生成一个随机数[ξ∈[0,1]],如果[ξ≤pi(t)]第i位选择1,否则第i为选择0;

步骤5:计算N个个体的适应度函数并排序;

步骤6:根据频率gi(t)和bi(t),i=1,2…m,选择M个最优个体和最差个体;

步骤7:对每个基因位i,记录t-1时刻的状态s和采取的动作a,通过gi(t)和bi(t)确定当前状态s;使用式(5)计算直接回报,根据式(3) 、(4) 更新Q表值[Qi(s,a)]。

步骤8:生成随机数[ξi∈[0,1]],如果[ξi≤pi(t)τ0=50],则随即选择一个动作a,否则使用[a'=argmax Qi(s',a')]选择动作。

步骤9:根据式(0)~(2)以及动作a,根据相应的公式计算pi(t+1)的新概率值。

步骤10:结束。

2.3 改进策略

算法每次更新概率pi(t),Agenti使用[ε]贪婪策略随机选择动作,使用1-[ε]概率按照当前状态最大Q值选择动作。由于[ε]贪婪策略不会总能选择到最佳的动作,所有总是以较小的概率进行随机选择动作。通过增加随机选择的概率,能够让Agent探索新知识,比[ε]贪婪策略获得更好的结果。

然而,使用固定的[ε]值具有一定的局限性,尤其是当Agent经过足够多次学习以后,当前的策略已经接近于最有策略,如果仍然以[ε]概率随机选择动作的话,将会影响算法的收敛速度。如果可以逐渐的减少探索概率的影响,能很大程度上提高基于Q学习的分布估计算法的执行效率。使用模拟退火法算法的MetroPolis规则能够解决这个问题,它通过随着温度的降低逐步降低发生劣质解得概率。

下面给出使用改进的MetroPlis规则的基于Q学习的分布估计算法的设计规则。

算法2:改进的基于Q学习的分布估计算法

步骤1:初始化Qi=0,i=1,2……m;初始温度[temperatureτ=τ0];设置P(1)=(0.5,0.5……0.5),t=1。

步骤2: While(终止条件不满足)do

步骤3:根据P(t)采样第N-1代的种群,在t-1时刻使用最优的个体代表当前群组。

步骤4:计算N个个体的适应度函数并排序;

步骤5:根据频率gi(t)和bi(t),i=1,2…m,选择M个最优个体和最差个体;

步骤6:对每个基因位i,记录t-1时刻的状态s和采取的动作a,通过gi(t)和bi(t)确定当前状态s;使用式(5)计算直接回报,根据式(4)更新Q表值[Qi(s,a)]。

步骤7:使用[a'=argmax Qi(s',a'')]选择动作[ar],根据如下概率确定动作[a']。

[P{a'=ar}=eQ(s,a')-Q(s,a*)τ] (6)

[P{a'=a*}=1-P{a'=ar}] (7)

步骤8:根据式(0)~(2)以及动作a重新计算pi(t+1)的概率值;

步骤9:结束。

冷却:[τ←λτ;]

[t←t+1].

几何冷却策略算法使[τ←λτ],其中[λ∈(0,1)]是温度系数。随着温度的降低,Agenti随机选择动作的概率越来越小,当温度趋于0时,策略相当于贪婪策略。

3 对比实验

3.1 测试函数

为了评价基于Q学习的分布估计算法的执行效率,用本算法与经典的UMDA、PBIL、MIMIC算法、遗传算法进行比较。选择6个标准测试函数进行测试。Sphere函数、Quadric函数、Schaffer函数、griewank函数、Rosenbrock函数和Rastrigin函数。不同形式的标准测试函数具有较好额运行效果。Schaffer函数、Griewank函数和Rastrigin函数是多峰函数,具有多个局部最小值,通常更难以找到全局最小解。算法用于测试其跳过局部最小进行全局寻优的能力。Rosenbrock函数式单峰、非凸病态函数值域上具有单调特性。全局最优点的收敛于远方,可以使用有效算法来对其进行估计。Sphere函数和Quadric函数式单峰函数,能够测量优化算法的准确性,检验算法的实现程度。

3.2 实验结果分析

经过测试,基于Q学习的分布估计算法参数如下:频阈[θhigh]=0.75,[θlow]=0.25,[θdiff]=0.35,选择[γ]=0.2,调节率[β]=0.9,学习因子[α]=0.2,折扣因子为0.9。比较UMDA算法选择率设置为0.2,PBIL算法学习率设置为0.1,MIMIC算法选择率设置为0.4,遗传算法使用单点交叉,交叉率为0.7,变异率为0.1。所有算法的种群规模设置为50,终止条件设置为找到全局最有接或者进化代数为T,T设置为200。

考虑的上述算法都具有一定的随机性,使用函数f1~f6分别独立测试50次,实验结果如表所示。表1显示了每个算法获得全局最优解的个数。表2显示了50次测试的平均值、标准差和最差值。表3显示了每种方法的平均运行时间(单位:秒)。其中QEDA表示基于Q学习的分布估计算法,MEDA表示使用MetroPolis和[ε]贪婪策略的基于Q学习的分布估计算法。QEDA选择[ξ]=0.5,MEDA的初始温度设为[τ0=50],温度系数[λ=0.9]。

可以看出,无论是传统的遗传算法还是UMDA、PBIL、MIMIC算法,在解决复杂问题的函数优化中,都不容易找到全局最优解。而PBIL搜索成功率高68%,其他三种算法低50%左右。基于Q学习的分布估计算法运行效率最高,尤其是使用了MetroPolis规则的基于Q学习的分布估计算法,对于6个标准函数都能够找到全局的最优解。在算法的执行时间上,双变量相关的MIMIC算法执行效率最差。而使用了MetroPolis规则的基于Q学习的分布估计算法与PBIL算法都求解了Rosenbrock函数,而且在执行时间上也是最好的。endprint

参考文献:

[1] Larranaga P, Lozano J A, Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation [M]. Boston: Kluwer Academic Publishers. 2002.

[2] Baluja S. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Technical Report CMU-CS-94-163, Pittsburgh, PA ,1994.

[3] Mühlenbein H,Paa G.From recombination of genes to the estimation of distributions I. Binary parameters, in: Parallel Problem Solving from Nature,1996:178-187.

[4] Pelikan M,Goldberg D E,Lobo F.A survey of optimization by building and using probabilistic models, Computational Optimization and Applications,2002(21):5-20.

[5] Sergios T, Konstantinos K.Pattern Recognition, Second Edition[M]. San Diego: Academic Press,2003.

[6] Dasgupta D,Forrest S.Artificial immune systems and their applications[M].Berlin:Spring-Verlag,1998.

[7] Slowinski R, Hapke M. Scheduling under fuzziness[M]. New York: Physica-Verlag,2000.

[8] Seber G A R Linear regression analysis[M]. New York: John Wiley,1997.

[9] Deng J L. Introduction to grey system theory[J]. The Journal of Grey System,1989,I(1).endprint

参考文献:

[1] Larranaga P, Lozano J A, Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation [M]. Boston: Kluwer Academic Publishers. 2002.

[2] Baluja S. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Technical Report CMU-CS-94-163, Pittsburgh, PA ,1994.

[3] Mühlenbein H,Paa G.From recombination of genes to the estimation of distributions I. Binary parameters, in: Parallel Problem Solving from Nature,1996:178-187.

[4] Pelikan M,Goldberg D E,Lobo F.A survey of optimization by building and using probabilistic models, Computational Optimization and Applications,2002(21):5-20.

[5] Sergios T, Konstantinos K.Pattern Recognition, Second Edition[M]. San Diego: Academic Press,2003.

[6] Dasgupta D,Forrest S.Artificial immune systems and their applications[M].Berlin:Spring-Verlag,1998.

[7] Slowinski R, Hapke M. Scheduling under fuzziness[M]. New York: Physica-Verlag,2000.

[8] Seber G A R Linear regression analysis[M]. New York: John Wiley,1997.

[9] Deng J L. Introduction to grey system theory[J]. The Journal of Grey System,1989,I(1).endprint

参考文献:

[1] Larranaga P, Lozano J A, Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation [M]. Boston: Kluwer Academic Publishers. 2002.

[2] Baluja S. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[R].Technical Report CMU-CS-94-163, Pittsburgh, PA ,1994.

[3] Mühlenbein H,Paa G.From recombination of genes to the estimation of distributions I. Binary parameters, in: Parallel Problem Solving from Nature,1996:178-187.

[4] Pelikan M,Goldberg D E,Lobo F.A survey of optimization by building and using probabilistic models, Computational Optimization and Applications,2002(21):5-20.

[5] Sergios T, Konstantinos K.Pattern Recognition, Second Edition[M]. San Diego: Academic Press,2003.

[6] Dasgupta D,Forrest S.Artificial immune systems and their applications[M].Berlin:Spring-Verlag,1998.

[7] Slowinski R, Hapke M. Scheduling under fuzziness[M]. New York: Physica-Verlag,2000.

[8] Seber G A R Linear regression analysis[M]. New York: John Wiley,1997.

[9] Deng J L. Introduction to grey system theory[J]. The Journal of Grey System,1989,I(1).endprint