基于固定宽度直方图的分布估计算法的一种改进

2012-08-31刘建军石定元武国宁

太原城市职业技术学院学报 2012年8期

关键词：概率模型直方图宽度

刘建军，韩帅，石定元，武国宁

（中国石油大学理学院，北京 1 0 2 2 4 9）

基于固定宽度直方图的分布估计算法的一种改进

刘建军，韩帅，石定元，武国宁

（中国石油大学理学院，北京 1 0 2 2 4 9）

基于固定宽度直方图分布的分布估计算法（F WH），提出一个改进方案，即在F WH算法中加入概率阈值的要素，不使用改变区间长度的更新方式，保证区间个数不增加，并在更新候选解步骤中加入模式搜索法（H o o k e-J e e v e s方法），构造出一种改进的优化算法（H J-F WH）。数值实验结果表明，改进后的算法在最优解精度和收敛速度方面均有了较大的提高。

分布估计算法；模式搜索法；直方图；概率模型

分布估计算法（E D A s:E s t i m a t i o n o f D i s t r i b u t i o n A lg o r i t h m s）是进化计算领域新近兴起的一类随机优化算法，它将传统的遗传算法的思想和统计学的概率模型结合起来，形成一种全新的智能优化计算模式。

分布估计算法可以按照概率模型的复杂程度进行分类，包括变量无关的P B I L、U M D A和c G A算法；双变量相关的M I M I C、B M D A算法以及多变量相关的E CG A、F D A、B O A等算法。美国卡耐基梅隆大学的B a l u j a在1 9 9 4年提出P B I L算法，是用来解决二进制编码的优化问题，虽然当时还没有提出分布估计算法的概念，但是P B I L算法被公认为最早的分布估计算法模型。

直到1 9 9 6年,分布估计算法的概念才第一次提出。其中U M D A算法由德国学者M u h l e n b e i n于同年提出，它与其他算法不同在于其概率向量的更新方式。之后的M I M I C算法，是由美国M I T人工智能实验室的D e B o n e t等人于1 9 9 7年提出的一种启发式优化算法，此算法是最先考虑两个变量相关。而B O A算法是由美国U I U C大学的P e l i k a n等提出的，此算法主要研究多变量相关的问题。

该文选取基于固定宽度的直方图模型的分布估计算法（F WH算法）为基本方法，加入概率阈值的要素，防止函数早熟，同时考虑到算法效率，而不使用改变区间长度的更新方式，保证区间个数不增加，可以加快迭代速度，并在更新种群步骤中加入模式搜索法（H o o k e-J e e v e s方法），可以有效地提高逼近解的精度。

一、基于直方图的分布估计算法

（一）基本介绍

基于直方图的分布估计算法的模型一般分为两种，一种是区间宽度固定的直方图模型F WH(t h e f i x e d-w i d t h h i s t o g r a m)，另一种是区间高度固定的直方图模型F H H(t h e f i x e d-h e i g h t h i s t o g r a m)。其中，F WH将变量的定义域划分为宽度相同而高度不同的小块区间，小块的高度决定了该范围取值的概率大小。而F H H则将变量的定义域划分为宽度不同而高度相同的小块区间，小块的宽度代表了该小块取值的概率大小。同基于高斯分布的分布估计算法相比较，F WH和F H H使用了更加简单的均匀分布概率模型，而且通过控制每个小块的宽度或高度，能够有效地求得相对精度较高的结果。由于F WH和F H H都在优化连续问题时得到结果精度的大小，基本取决于在定义范围内各维小区间划分的个数，所以，既要保证小区间分得要细，算法迭代速度也不能太慢。该文考虑变区间算法的计算复杂性较高，故选取F WH算法作为基本算法来改进。

（二）F WH算法步骤：

S t e p 1初始化候选解，给定初始参数。

S t e p 2构造初始概率模型，现将变量的每一维进行等分，保证每个小区间初始概率相等。

S t e p 3通过随机方式构造初始候选解，保证各点均匀分布在各个小区间上。

S t e p 4计算候选解的适应值，根据各点适应值，选择所要的优势候选解。

S t e p 5更新概率向量，根据优势候选解的变量所在区间，用更新公式更新每个小区间概率向量。

S t e p 6达到给定迭代次数，输出结果。

二、基于模式搜索法的固定宽度的直方图分布估计算法（H J-F WH）

（一）模式搜索法

模式搜索法的基本思想，从几何意义上讲，是寻找具有较小函数值的低谷，试图通过迭代产生序列沿山谷向极小点逼近。算法首先从初始点开始进行两种类型的移动，即探测移动和模式移动。探测移动是依次沿个坐标轴进行，用来确定新的基点和有利于函数值下降的方向。模式移动是沿相邻两个基点连线方向进行，试图沿着山谷方向使函数值更快地减小。

图1 模式搜索法示意图

（二）结合模式搜索法的直方图分布估计算法

在模式搜索法结合直方图分布估计算法（H J-F WH）中，在更新种群步骤中应用模式搜索的思想，先对种群的每一维进行探测移动，完成后再进行模式移动，找到新的基点，若无效则退回原基点，按照初始步长γ及缩减率β更新步长，再从这个基点出发，依次沿各坐标轴方向进行探测移动。如此继续下去，直到满足精度要求，即步长δ小于事先给定的某个小的正数ε为止。

在H J-F WH算法中的概率阈值按以下方式更新：当某一个小区间概率大于阈值时，对需要更新的变量区间的概率变为原来的，其他的每个区间的概率加上这个区间概率的。即第i个小区间的概率Pi≥G，则将这个区间的概率变为，其他区间的概率变成，（k=1，2…，i-1，i+1…，N）保证每一维小区间概率和为1。H J-F WH算法步骤：

S t e p 1初始化：对参数如候选解规模M、细分等分数N、优秀候选解规模δ（δ＜M）、概率阈值G、学习概率α、迭代次数Gen等给定初值。

S t e p 2构造概率模型：需要先对变量的连续空间进行等分。例如某一维的变量的连续空间为[a，b]，如果进行N等分，则每一份区间的长度是。因为是进行N等分，所以开始这N个区间的取值概率都是相同的，也就是对于每个变量的连续空间，进行了N等分以后，每个小区间取值的概率都是。

S t e p 3构造新解：即对每个个体的每一维变量进行赋值。一般通过产生随机数采用轮盘赌的方式确定每个变量的取值。

S t e p 4确定新的优秀候选解：计算候选解的适应值，根据其适应值，对候选解进行排序，选择前δ个适应值较好的解作为优秀候选解δ（k）。

S t e p 5模式搜索法更新当前最优解：将这前δ个适应值较好的解中最好的一个解采用模式搜索算法，得到一个新的最优解，完成更新。

S t e p 6更新概率向量：对于变量某一维取值的连续空间，在它的N个划分小区间里，统计含有优秀候选解的个数，设某个小区间中含有优秀候选解的个数为ni，更新前该小区间的概率为pi，则更新后的概率为。

S t e p 7判断概率是否超过阈值：当某个小区间的概率大于G，则将区间概率进行重新更新，否则不需要更新。

S t e p 8算法停止条件：当算法进行了一定数量的迭代次数后，算法停止，并输出结果。