V&V策略深度制定的随机规划模型解法

风险随机变量的本质是不确定性，而随机模拟（Monte Carlo Simulation，也称模特卡罗模拟）、人工神经元网络（Neural Networks）和遗传算法（Generation Alg-rithm）相互混合的智能算法是求解此类模型的有效方法。

本节将首先对随机模拟方法、神经元网络和遗传算法进行综述，然后讨论相应模型的解法。

1.不确定性含义与随机模拟方法的概述

不确定性与随机性的概念已经困扰人类很长一段时间。在我们生活的物质世界和自然环境中，我们无时不面对不确定性，遭受各种自然灾祸，忍受大自然的不确定性，正如歌德所说：“伟大的、内在的永恒不变的法则能给我们指出使我们不再徘徊的路吗？”

爱因斯坦也曾说：“上帝决不会和宇宙赌博。”

某些神学家认为，上帝是万能的，上帝决定万物，对上帝来说没有什么是随机性。但是，也有人断言，即使是上帝，往往也被某些随机现象所左右。所谓随机性，恐怕是当上帝不愿显示其真实身份时所用的托辞而已。

从亚里士多德时代开始，哲学家们就已经认识到随机性在生活中的作用，他们把随机性看作破坏规律和超越人们理解能力范围的东西，但没有认识到有可能去研究随机性，进而去度量其不确定性。古代中国和印度的哲学家信奉因果报应学说，认为没有必要去研究随机性，因为按他们严格的因果关系解释：一个人的命运，是由人的前世的行为所决定的。

人类的所有活动都是基于某种预示的，如上大学、找工作、结婚或投资等。由于未来是不可预测的，在任何情况下，都有可能产生不确定性，主要源于下列原因：

1）缺乏信息。

2）所得信息中，存在未被认识到的不准确性。

3）缺乏一定的技术手段去收集所需的信息。

4）不可能进行某些必要的测量。

如同物理学中的基本粒子运动、生物学中遗传因子和染色体的游离不定及在社会中处于紧张状态下的人们的行为一样，自然界中的不确定性是固有的。这些与其说是基于决定论的法则，不如说是基于随机论法则的不确定性现象，已经成为自然科学、生物科学和社会科学理论发展的必要基础。

十分奇妙的是，研究不确定性的方法通常使用随机排列的数列。假定一个口袋中装有标着0，1，2，…，9的硬币，我们一个一个地取出并记录下抽取硬币的数字。每一次抽取后，再把硬币放回口袋中并充分混合，然后抽取下一个，这样得到的数列称为随机数列。这时即便给出前面所抽出的一系列数字，也无法得到任何启示去推测下次抽取的结果，随机数列显示了最大限度的不确定性。

1927年，英国统计学家蒂皮特（Tippett）出版了一本名为《随机抽样数》的书。这本书无任何意义，仅仅是杂乱无章排列的数字，却成为当时专业书中最畅销的一本。这类书是为了解决现实世界中各种问题时对随机数的需要而产生出来的。当今世界，人们花费数十亿美元从事随机数的生成及相关的重要科学研究，并发展高性能的计算机。

什么是随机数列呢？这里不存在简单的定义。一个模糊的概念，即随机数列是不遵循任何一种特殊模式的数列。

美国著名统计学家C.R.劳在加尔各答印度统计研究所上课时，曾经让研究生到附近的班-霍夫（Bon-Hoophly）医院记录相继在该医院出生的婴儿的性别。如果记M为男婴，F为女婴，则可得到一个如投掷硬币或随机重复取球所得的相同的二元符号列。

通过统计分析，他发现决定婴儿性别的随机结构，与从装有相同数目的两种颜色小球的口袋中任取一球（白球或黑球）所得到的随机结构相同，这也与投掷硬币出现正面或反面的随机结构相同。进一步统计检验可证明，男、女婴出生所产生的随机二元序列比人工生成的随机列更准确。

现实场合中，除利用计算机外，人们常利用所谓逆偏二极管这样的物理装置来产生随机数。这是基于量子力学的理论，假定在原子水平下产生一定事件的随机性而做成的。但是，数学家们相信：要构造一个有效的随机数列（使其满足很多规则），不应通过随机程序，而要利用适当的确定程式来实现。因此通过装置，包括计算机，所产生的随机数列称为伪随机数列。在大多数实际应用中，使用这种伪随机数列可以达到预期目的。

我们看到，利用人工产生的随机数列可以发现自然界中的不确定性现象，并能解释这些现象，如男女出生序列。不单如此，利用随机数列，即随机模拟的方法，在科学探索的道路上已经得到了广泛的应用，如：

1）不规则图形面积的求解。

2）抽样调查。这也许是随机数最重要的一种用处。

3）试验设计。随机化是科学试验的一个重要方面。

4）通信的秘密化。在密码学，或使用密码传送文件及为个人银行存取业务保守秘密之中，均需要大量的随机数。在保守机密显得极为重要的高层次外交和军事通信中，秘密化就是要使任何非法接通通信网的人得到的仅仅是一些看似随机组合的数列。

5）建模。在解决各种世界问题，特别是统计问题时，对随机数的利用，已经为把随机数用于模型构造和预测开拓了道路。已发展的构建了这种模型的领域包括天气预报、预测商品消费需求和住房、医院、学校、交通设施这样一些社会服务设施的未来需求等。

6）解决复杂问题。解决一些诸如巡回推销员的路径般复杂的问题等。

7）随机数及随机性概念应用的范围似乎是无限的。

随机数没有特定的形式，但又包含所用形式，也就是说，如果我们在严格的意义下不断产生随机数，无论给出什么样的数的形式，该形式迟早会出现。无特定的形式却又包含一切形式的随机数列的性质，使随机模拟方法能帮助我们找到一些棘手问题的突破口，解决一些过于复杂而又难以求得精确解的问题，产生新的信息并有可能帮助发展新的思想。这也许正是随机模拟方法的科学性所在，而这种手段可能是解决上述问题的唯一有效工具。

2.遗传算法综述

自1960年以来，人们对于模拟生物及由此开发的针对复杂优化问题的有效算法产生了浓厚兴趣。当前，在该领域中通常引用的术语是进化计算（Evolutionary Computation）。它包含以下主要算法：遗传算法（Genetic Algorithms）、进化策略（Evolution Strategy）、进化规划（Evolutionary Programming）和遗传程序设计（Ge-netic Programming）。当然还存在若干将上述算法的各种特点加以结合后形成的混合算法。进化计算领域的最新发展水平在Bäck和Schwefel，Michalewicz及Fogel等人的综述里有很好的介绍。

作为强有力且应用广泛的随机搜索和优化方法，遗传算法可能是当今影响最广泛的进化计算方法之一。过去30年中，遗传算法已得到成功应用。

大家知道，生物遗传物质的主要载体是染色体。在遗传算法中，染色体通常是一串数据（或数组），作为优化问题的解的代码，其本身不一定是解。遗传算法一般经过如下过程：首先，随机产生一定数量的初始染色体，这些随机产生的染色体组成一个种群。种群中，染色体的数量称为种群的大小或规模。然后，用评价函数来评价每一个染色体的优劣，即染色体对环境的适应程度，作为以后遗传操作的依据。接着，进行选择过程，选择过程的目的是从当前种群中选出优良的染色体，使它们成为新一代的染色体。判断染色体优良与否的准则是各自的适应度，即染色体的适应度越高，其被选择的机会就越多。通过选择过程，产生一个新的种群。对这个种群进行交叉操作，这是遗传算法中主要的遗传操作之一，相当于生物的杂交。最后是进行变异操作，目的是挖掘种群中个体的多样性，克服有可能陷入局部解的弊病。这样，经过上述运算产生的染色体称为后代。此后，对新的种群（即后代）重复进行选择、交叉和变异操作。经过给定次数的迭代处理后，把最好的染色体作为优化问题的最优解（准确地说，关于遗传算法的终止条件目前尚无定论，在很多算例中，通常是发现群体的染色体进化已趋于稳定状态，则终止进化迭代）。

一般而言，遗传算法可以归纳为如图4.4所示的一般过程：

图4.4 遗传算法一般过程

在求解V&V活动深度制定的SEVM和SCCPM过程中，V&V活动的策略S将用合适的染色体来表示，通过相应的遗传计算，达到寻优目的。

3.神经元网络综述

神经元网络是基于生物学的神经元网络的基本原理建立的。它是由许多称为神经元的简单处理单元组成的一类适应系统。所有神经元通过前向或回馈方式进行相互关联、相互作用。虽然神经元网络能以类似人脑的方式工作，但是实际上它和生物学中的神经元网络还有很大差距。

神经元网络的早期工作可以追溯到1943年McCulloch和Pitts建立的第一个模型，后来被扩展为“认知（Perception）”模型。如今，人们对神经元网络的研究正日趋成熟，并构造出各种各样的神经元网络，如多层前向神经元网络、放射函数网络、Kohonen自组织特征图、适应理论网络、Hopfield网络、双向辅助存储网络、计数传播网络和认知与新认知网络。

神经元网络已被广泛应用于函数逼近、模式识别、图像处理与计算机视觉、信号处理、时间序列、医药控制、专家系统、动力系统、军事系统、金融系统、人工智能、优化和社会科学等方面。

神经元网络的一个重要作用就是具有对运作机制的学习能力。由Minsky和Pa-pert提出的多层前向神经元网络（也称多层感知器）是目前最常用的网络结构。本节主要介绍基于后向传播算法（Back-Propagation，BP）的多层前向神经元网络。

（1）人工神经元

与生物学中的神经元类似，人工神经元作为一种简单的处理器可以对到来的信号进行加权求和处理：

y=w₀+w₁x₁+w₂x₂+···+w_nx_n （4-17）

式中，x₁，x₂，…，x_n表示输入值；w₀，w₁，w₂，…，w_n表示权重；y表示神经元的输出。图4.5描述了一个神经元的结构。

在实际应用过程中，人们通常定义一个具有无记忆的非线性函数作为激励函数来改变神经元的输出：

y=σ（w₀+w₁x₁+w₂x₂+…+w_nx_n） （4-18）

图4.5 一个人工神经网络的结构图

激励函数的选择依赖于σ（x）的应用对象。一般地，使用sigmoid函数

σ（x）=1/（1+e^-x） （4-19）

作为激励函数，其导函数为：

σ′（x）=e^-x/（1+e^-x）² （4-20）

（2）多层前向神经元网络

多层前向神经元网络是目前使用较多的网络结构。它由输入层、一个或多个隐层及输出层以前向的方式连接而成。其每一层又由许多人工神经元组成，且前一层的输出作为下一层神经元的输入。图4.6描述了一个单隐层的三层前向神经元网络结构图。

图4.6 一个多层前向神经元网络（单隐层）

考虑一个只有单隐层的神经元网络：n个输入层神经元，m个输出层神经元和p个隐层神经元，则隐层神经元的输出为：

输出层神经元的输出为：

对于一般情况，我们假设神经元网络有L个隐层，n个输入层神经元，m个输出层神经元，而第l个隐层有p_l个神经元，l=1，2，…，L。第1隐层神经元的输出为：

而第l个隐层神经元的输出为：

l=2，3，…，L。神经元网络的最后输出为：

（3）函数逼近

多层前向神经元网络可以看作从输入空间到输出空间的非线性映射。已经证明具有一个或多个隐层的前向神经元网络能以任意精度逼近任何连续的非线性函数。而且，如果有无限个隐层神经元的话，则只有一个隐层的前向神经元网络就可以对连续函数进行任意精度的逼近。

假设f（x）：Rⁿ→R^m是一个连续函数。我们希望训练一个前向神经元网络来逼近函数f（x）。网络结构和神经元数量固定后，网络的权系数的数量也就确定了，记为向量w。这时，神经网络的输出映射可表示为F（x，w）。

神经元网络的训练过程就是寻找一个适当的权重向量w，从而对函数f（x）进行逼近。我们用{（x_i，y_i）|i=1，2，…，N}来表示训练数据集合。对于输入数据x_i，我们希望选出一组权重，使神经元网络的实际输出F（x，w）可以在允许误差内接近其训练数据y_i。也就是说，训练过程就是寻找权重向量，从而极小化以下误差函数：

有时候，我们也寻求权重极小化平均误差：

在函数逼近中，如何确定最佳的网络结构是目前神经元网络研究中的一个重要课题。它依赖于隐层和隐层神经元个数的选取。虽然在一般情况下，两个隐层的神经元网络比单层神经元网络具有更好的逼近能力，但在大多数应用问题中，只有一个隐层的神经元网络就已经足够了。关于隐层的数量，1989年，Robert Hecht-Nielson证明了对任何在闭区间内的一个连续函数都可以用一个隐层的BP网络逼近。因此，一个三层的前向神经元网络可以完成任意的n维到m维连续函数的映射。

隐层数量确定后，我们还需要决定使用多少个隐层神经元。一方面，过少的隐层神经元会使网络缺乏逼近能力；另一方面，过多的隐层神经元又会增加训练时间且降低神经元网络的反应速度。总之，决定隐层神经元数量是一个复杂的问题，不过有如下经验公式可作为参考：

上述四式中，m为输出神经单元数量；n为输入神经单元数量；a为1～10之间的整数；b为0～7之间的整数；int[·]表示取整操作。

（4）BP算法

权重的大小决定了神经元网络的所有信息。在训练期间，神经元网络的权重不断更新，直到满足一些预先给定的条件为止。也就是说，神经元网络的学习过程是一个权重修正的过程，以使网络所代表的映射可以和所要求的映射尽可能地接近。该过程也可看作一个优化问题，即通过权重的选择极小化网络输出和实际输出之间的误差。

BP算法是多层前向神经网络最初使用的，也是使用最广泛的学习算法。

对于单隐层的三层前向神经元网络，假定有N个学习样本：

首先，随机产生初始权向量，并令：

Δw¹_ij=0，i=1，2，…，m，j=0，1，2，…，p；Δw⁰_ij=0，i=1，2，…，p，j=0，1，2，…，n，以及适应参数λ=1。

然后，通过在线学习过程对权重进行调整。当学习到第k个样本时，隐层神经元的输出为：

整个神经元网络的输出为：

为提高收敛速度，可将误差函数做以下改进：

式中，Φ（x）=ln（cos（βx））/β，β为常数。

于是，权重的差分方程就变成了下面的形式：对于隐层的输出权值w_i¹j，i=1，2，…，m，j=0，1，2，…，p，我们有：

其中，

对于隐层的输入权值w⁰_ij，i=1，…，p，j=0，1，…，n，有

式中，

对神经元网络训练完全部输入输出数据后，可计算出总误差。如果此误差小于预先确定的精度E₀，那么训练完毕。否则，令λ=exp（-μ/E²），并重复以上学习过程，直到E＜E₀满足为止。

综上所述，可得到BP算法的流程图4.7。

BP算法简单方便，缺点是收敛速度慢，目标函数存在局部极小问题，与初始权值的选择有直接关系。由于遗传算法对求得优化问题的全局最优解很有效，一些研究者提出了用遗传算法来产生神经元网络的权值，例如Maniezzo，Kitano，Van Rooij等。

图4.7 BP算法流程图

4.SEVM的求解

SEVM的显著特点是目标函数或约束条件中含有期望约束。

从数学观点来看，确定性优化问题和期望值模型并没有本质区别，只是后者中存在多重积分，采用随机模拟、神经元网络和遗传算法相结合的智能算法是求解形如式（4-13）和式（4-14）的随机期望值模型的利器。

遗传算法是为对策略S进行全局寻优，而采用神经元网络是为逼近模型中相应的不确定性函数。

对于SEVM而言，不确定函数为期望风险值E[F（D，ξ）]。为使用神经元网络来逼近该函数，首先需获取函数F（D，ξ）的值。

（1）不确定函数F（D，ξ）值的获取

显然深度D已知。根据模型（S，ξ）的描述，风险事件Ω_i，j的风险损失是随机变量，即ξ_i，j，其概率密度函数为。为得到具体的ξ_i，j值，利用随机模拟的方法，首先产生服从[0，1]均匀分布的随机数p。如果p≤P_i，j，则ξ_i，j=L_i，j，否则ξ_i，j=0。得到ξ_i，j，则得到所有ξ_i，j组成的向量ξ的值，根据，可得到总体风险值。

（2）不确定函数E[F（D，ξ）]值的获取

由于风险值F（D，ξ）是随机变量，假设其随机模拟的观测值为F（D_k，ξ），k=1，2，…，N，由大数定律，当N→∞时，

因此，只要N充分大，可用作为E[F（D，ξ）]的估计值。根据

大数定律，利用随机模拟来求取E[F（S，ξ）]的计算流程，如图4.8所示。

图4.8E[F（D，ξ）]求取流程图

（3）SEVM的混合智能算法

首先通过随机模拟，为不确定函数

U：（D）→E[F（D，ξ）]产生输入输出数据，然后训练一个单隐层的三层前向神经元网络Net（U）来逼近不确定函数U。最后，把训练好的神经元网络嵌套在遗传算法中，即在求解式（4-13）时，在遗传算法中使用神经元网络Net（U）来计算目标函数值。而在求解式（4-14）时，在遗传算法中使用神经元网络Net（U）来检验染色体和后代的可行性，从而形成混合智能算法。

5.SCCPM的求解

SCCPM的显著特点是目标函数或约束条件至少以一定的置信水平成立。如同SEVM的求解方法，将随机模拟、遗传算法和神经元网络三者结合的智能算法，也是求解SCCPM问题的利器。

遗传算法是为对策略S进行全局寻优，而采用神经元网络是为逼近模型中相应的不确定性函数。

对于SCCPM而言，不确定函数为Pr{F（D，ξ）≤R}≥β和Pr{F（D，ξ）≤λR₀}。为使用神经元网络来逼近该函数，首先要获取这两类不确定函数的值。

（1）不确定函数Pr{F（D，ξ）≤R}≥β值的获取

β是给定的置信水平，R值应在等号成立处达到，即：

Pr{F（D，ξ）≤R}=β （4-31）风险值F（D，ξ）是随机变量，假设其随机模拟的观测值为F（D_k，ξ），k=1，2，…，N，定义。

这也是一列随机变量，且只要R满足式（4-31），就有E[h（D_k，ξ）]=β。根据强大数定律，当N→∞时，有

注意到有限和正是使F（D，ξ）≤R成立的个数，因此R应该处于序列{F（D₁，ξ），F（D₂，ξ），F（D₃，ξ），…，F（D_N，ξ）}中的第N′个最小元素的位置，其中N′是βN的整数部分。具体的算法流程如图4.9所示。

图4.9 Pr{F（D，ξ）≤R}≥β计算流程图

（2）不确定函数Pr{F（D，ξ）≤λR₀}值的获取

λ是给定的风险承受水平，R₀是极限风险值，假设L=Pr{F（D，ξ）≤λR₀}。

风险值F（D，ξ）是随机变量，假设其随机模拟的观测值为F（D_k，ξ），k=1，2，…，N，令N′表示满足F（D_k，R）≤λR₀成立的试验次数。定义：

对所有k，有E[h（D_k，ξ）]=L，。根据强大数定律，当N→∞时，有（几乎处处收敛到L）。因此，当N充分大时，可以用估计概率值L。

具体的算法流程如图4.10所示。

（3）SCCPM的混合智能算法

首先通过随机模拟，为不确定函数

U₁：（D）→Pr{F（D，ξ）≤R}≥β

U₂：（D）→Pr{F（D，ξ）≤λR₀}

产生输入输出数据，然后分别训练一个单隐层的三层前向神经元网络Net（U₁）和Net（U₂）来逼近这两个不确定函数U₁和U₂。最后，将训练好的神经元网络嵌套在遗传算法中，即求解式（4-15）时，在遗传算法中使用神经元网络Net（U₁）来计算目标函数值和检验染色体及后代的可行性。而在求解式（4-16）时，在遗传算法中使用神经元网络Net（U₂）来检验染色体和后代的可行性，从而形成混合智能算法。

图4.10 Pr{F（D，ξ）≤λR₀}计算流程图