摘 要：对带约束条件的灰色非线性规划问题进行了探讨，首先将原灰色约束非线性规划问题进行均值白化处理，转化成一个确定型的带约束条件的非线性规划问题，对该确定型的非线性约束规划问题提出一个基于分布估计算法的随机搜索方法，对所提出的求解方法的关键技术作了详细的说明并给出了具体的算法步骤。 初步的数值算例表明所提出的方法是可行有效的。
关键词：灰色非线性规划； 均值白化模型； 分布估计算法； （近似）最优解； 蒙特卡罗模拟
0 引言
自从20世纪80年代邓聚龙教授提出灰色非线性规划问题以来， 以其灵活性与适用性强等特点已成功应用于若干生产领域中[1-2]。 但到目前为止， 对于灰色非线性规划问题来说， 使用传统的优化方法来求解局限性很强， 只能求解经白化以后规模较小的问题， 大部分灰色非线性规划问题根本无法采用传统的解析优化算法求解[3-4]。基于此， 张曙红等[5]提出了使用遗传算法来求解该问题。而在最近几十年，智能优化算法取得了长足进步，新的智能算法层出不穷，比如粒子群算法[6-7]、分布估计算法[8]与蝙蝠算法[9-10]等。这些新型智能算法的出现为解决不确定优化问题提供了强有力的工具。为了丰富灰色非线性规划问题的求解方法， 本文提出一个基于分布估计算法的随机搜索方法来求解灰色约束非线性规划问题，并以数值算例验证算法的有效性。
1 灰色约束非线性规划问题的数学模型
在传统的非线性规划问题中，其目标函数中系数、约束函数中的系数和右端常数项都是固定不变的，但是在实践应用中，遇到的大多数实际优化问题其目标函数中的系数，甚至约束函数中的系数与右端常数项都不是确定的，而是在一定的范围内呈现不规律的波动，灰色规划就是为了解决数据在一定范围内变化形成的不确定数学规划被提出来的。 灰色约束非线性规划问题的数学模型定义如下：
称上述非线性规划问题为GCNLP的白化规划问题。
灰色规划问题的白化方法有很多种类，比如均值白化和漂移白化模型等，本文采用均值白化方法。
2 基于分布估计算法的随机搜索方法
2.1 分布估计算法
分布估计算法是进化计算领域新近兴起的一类随机优化算法，是当前国际进化计算领域的研究热点之一。分布估计算法将遗传算法与统计学习相结合， 通过统计学习的手段建立解空间内个体分布的概率模型， 然后对概率模型随机采样产生新的群体， 如此反复进行以实现群体的进化[11-12]。在分布估计算法的框架中， 根据求解问题不同的概率模型， 可分为变量无关、双变量相关与多变量相关等三类相应的分布估计算法。若按照模型描述的变量性质又可以分为离散域分布估计算法与连续域分布估计算法， 且上述两种分类方法可以互有交叉。
分布估计算法的运行框架并不像遗传发算法那样采用复制、交叉与变异等遗传操作算子，它采用一种全新的学习机制， 即通过概率模型的学习和采样来描述整个种群的进化趋势。具体来说， 分布估计算法通过概率模型描述候选解在种群空间中的分布， 采用统计学习的手段从种群的宏观角度建立一个描述解分布的概率模型， 然后对概率模型随机采样产生新的种群， 反复这样的操作， 实现种群的进化。分布估计算法的基本求解步骤可概括如下。
步骤1 按照均匀分布随机产生可行的初始种群。
步骤2 利用适应度函数评价每个个体， 按照个体的适应度大小选择适应度较好的个体组成优势种群。
步骤3 采用某种统计学习手段构造描述当前优势群体的概率模型。
步骤4 由建立的概率模型随机采样产生新的种群， 并重新评价个体。
步骤5 判断是否满足进化终止条件， 若满足， 结束进化迭代并返回问题的（近似）最优解； 否则， 选择新的优势种群， 转到步骤3。
2.2 求解GCNLP的随机搜索方法
下面详细阐述构建求解GCNLP的基于分布估计算法的随机搜索方法的具体步骤。
2.2.1 适应度函数的构建
在本文中，借用类似构建罚函数的方法来构建如下的评价种群个体优良程度的适应度函数Fitness（x），即
2.2.2 概率分布模型的构建
分布估计算法最为重要的一环是构建概率分布模型和随机抽样， 在本文中选取多变量无关的高斯分布模型来描述候选解的统计信息以指导新一代种群的生成。变量无关的高斯分布模型的联合分布密度函数为
选取高斯分布模型的好处是： 在每一次迭代中， 算法可根据选择的优势种群自适应地更新其均值向量和标准差向量， 不仅可以有效地提取当前优势群体的全局统计信息， 且在一定程度上减少对参数设置方面的尝试， 提高算法的效率。
2.2.3 抽样与种群更新
由于面临的求解对象是带约束的优化问题，所生成的初始种群中的每个个体必须要求满足问题的可行条件，换句话来说，必须要求初始种群中的全部个体落在约束域中。因此在随机抽样时，对常用的随机抽样技术蒙特卡罗方法进行了修正，修正的蒙特卡罗随机模拟技术的步骤如下：
步骤1 根据问题的概率模型，使问题的解对应于该模型中随机变量的某些特征（比如均值与标准差等）。
步骤2 根据概率模型中各个随机变量的分布，产生实现一次模拟过程所需的足够多的随机数。先产生服从均匀分布的随机数，然后生成服从某一分布的随机数，方可进行随机模拟实验。
步骤3 根据概率模型的特点和随机变量的分布特征，设计和选取合适的抽样方法，并对每个随机变量进行抽样。
步骤4 按照所建立的模型进行仿真实验，求出问题的随机解。
步骤5 判断产生的随机解是否满足问题的约束条件，若满足，进行下一个个体的抽样；若不满足，转到步骤3，重新进行抽样。
使用上述修正的蒙特卡罗模拟技术科随机抽样产生整个初始种群，并按照式（1）计算每个个体的适应度函数值，按照一定选取规则生成下一代种群。
2.2.4 算法的终止条件
当算法预先设定的最大进化迭代次数达到或者种群最优个体的适应度函数值连续若干代（可具体制定）没有得到改善， 此时可终止算法并返回当前种群最优个体最为原问题的（近似）最优解。
由上所述，下面给出求解GCNLP问题的随机搜索方法具体步骤：
步骤1 将GCNLP问题取均值白化模型， 得到均值白化问题。
步骤2 根据初始化规则随机生成PopSize个初试点xi（i=1，2，…，PopSize）， 得到初始种群， 令t：=0。
步骤3 根据适应度函数式（1）计算第t代种群每个个体的适应度。
步骤4 根据适应度函数值选择第t代种群中最优良的M（MPopSize）个个体， 组成优势种群。
步骤5 根据式（2）～（4）估计优势种群的概率分布， 并建立对应的概率分布模型。
步骤6 根据步骤5中所建立的概率分布模型随机抽样， 对抽样产生的个体进行可行性检验： 若不满足， 则需重新抽样； 否则保留样本个体并重复“抽样可行性检验”的过程，直到生成PopSize个可行的个体。计算新种群的每个个体的适应度， 并根据适应度选择PopSize-M个最优良的个体， 并于上一代中的优势群体合并组合成下一代种群。
步骤7 当算法达到预先设定的最大进化迭代次数（T=200）或者种群最优个体的适应度函数值连续若干代（比如30代内）没有得到改善， 此时可终止算法并返回当前种群最优个体最为原问题的（近似）最优解；若不满足终止条件， 令t：=t+1， 转到步骤4。
上述算法的时间复杂度可以从两方面进行论证。第一是种群的初始化阶段，由于种群中的PopSize个个体是在问题的基本空间中随机生成，所以该阶段时间复杂度为O（PopSize）；第二是算法的执行阶段，由算法的步骤3和步骤4，可知时间复杂度为O（T*PopSize）， T 为最大进化迭代次数，由步骤6的个体抽样统计阶段，可知其时间复杂度为O（PopSize2）。由此可见，所提出的算法的时间复杂度至少是O（PopSize2）。
3 数值算例
为了说明本文所提出的随机搜索方法的有效性， 利用两个算例进行了数值实验， 所使用的编程软件为Matlab R2010a，计算机性能配置为Intel Core i3 CPU， 主频为2.53GHz， RAM 2.00GB。具体实验情况如下：设定种群规模PopSize=100，M=20；最大迭代次数T=200，t=30。
算例1
4 结语
基于分布估计算法， 本文对于灰色非线性规划问题的均值白化模型提出了一个随机搜索方法， 数值算例表明所提出的随机搜索方法是可行有效的， 且从算法执行时间上看， 实时性也较强。关于此课题未来的研究主要存在三方面的工作： 1）关于该算法的收敛性分析的严格数学证明，关于分布估计算法的收敛性分析到现在为止并没有形成完整统一的成熟成果，因此本文算法的收敛性结论的严格证明将是未来的主要工作之一；2）对于灰色非线性规划问题， 除了均值白化的处理手段， 是否还存在更为合理的白化处理手法，比如可使用GM（1，1）模型来预测问题中的灰数在未来的变化趋势等； 3）可进一步考虑研究分布估计算法在求解灰色多目标优化问题中的应用。
参考文献：
[1] 邓聚龙.灰色预测与决策[M]. 武汉： 华中科技大学出版社， 2002.
[2] 党耀国， 刘思峰， 王正新，等. 灰色预测与决策模型研究[M]. 北京： 科学出版社， 2009.
[3] 邓聚龙. 灰色多维规划[M]. 武汉： 华中理工大学出版社， 1988.
[4] 刘思峰， 党耀国， 方志耕，等. 灰色系统理论及其应用[M]. 北京： 科学出版社， 2010.
[5] 张曙红， 陈绵云. 灰色非线性规划问题及其遗传算法求解方法[J]. 系统工程理论与实践， 2002， 22（7）： 128-130.
[6] KENNEDY J. EBERHART R. Particle swarm optimization[C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway： IEEE，1995：1942-1948.
[7] SHI Y. A modified particle swarm optimizer[C]// Proceedings of the 1998 IEEE World Congress on Computational Intelligence. Piscataway： IEEE， 1998： 69-73.
[8] LARRANAGA P， LOZANO J A. Estimation of dsitribution algorithms[M]. Dordrecht： Kluwer Academic Publishers，2001.
[9] YANG X S. A new metaheuristic batinspired algorithm[C]// Proceedings of the 2010 Nature Inspired Cooperative Strategies for Optimization. Berlin： Springer， 2010：65-74.
[10] YANG X S. Bat algorithm for multiobjective objective optimisation[J]. International Journal BioInspired Computation， 2011， 3（5）： 267-274.
[11] 周树德， 孙增圻. 分布估计算法综述[J]. 自动化学报， 2007， 33（2）： 113-124.
[12] 王圣尧， 王凌， 方晨，等. 分布估计算法研究进展[J]. 控制与决策， 2012， 27（7）： 961-966.