机会约束规划 (Chance-Constrained Programming，CCP)^[1]是一类含机会约束或概率不等式的随机规划。依据目标函数表现形式的不同，CCP包含两类模型，即目标函数是期望值函数的E-模型和目标函数满足概率不等式的P-模型 (即概率优化模型)。大量实际优化问题均可经由P-模型加以描述和解决，如电力市场报价、资源优化、水库优化调度和炼油厂冶炼原油规划等^[2-3]。由于此类问题的目标值需在给定置信水平下经由机会约束确定，加之目标值的估计质量与随机变量的样本大小紧密相连，因此，探讨效率和效果均较为突出且噪声抑制能力强的智能优化算法是求解此类问题的关键。 特别地，在随机变量分布特性已知的情况下，P-模型可以被转化为具有解析形式的规划模型，进而利用已有约束优化算法求解^[2]。

当随机变量的分布信息未知时，智能优化算法已成为求解P-模型的主要方法。已有算法成果均在要求随机变量的样本大小保持不变下,借助Monte Carlo、Sugeno模拟或神经网络估计个体的适应度，然后设计改进型遗传算法(GA)^[3-8]、粒子群优化(PSO)算法^[9-13]和免疫优化算法^[14]。例如，文献^[4-6] 研究了含模糊和随机参数的混合P-模型，其利用模糊模拟、随机模拟估计个体的适应度，利用遗传算法、同步扰动随机逼近算法(SPSA)和神经网络等设计混合遗传算法。其次，粒子群优化算法具有参数少、优化效率高、结构简单和易于应用等优点，与神经网络结合求解P-模型已成为一种主要方法，但由于此类算法易陷入局部搜索，加之神经网络的网络权值极大依赖于样本量和样本的分布，导致该算法最终获得的效果不理想。例如，文献^[13]通过设置惯性权重为零来增强局部搜索能力，一旦出现当前、历史最优位置相同状况时，借助随机粒子弥补群体多样性，获得改进型粒子群优化算法。免疫优化算法求解P-模型已得到初步研究，文献^[14]利用神经网络估计个体的目标值；利用双克隆和双变异策略改进克隆选择算法，获得改进型免疫优化算法，并应用于水库优化调度问题。

综上可知，近年来求解P-模型的研究集中在探讨静态采样下的智能优化算法，但算法的计算资源占用多，计算开销较大，因此，如何高效估计问题的目标值，以及如何有效处理机会约束条件,探讨应用能力强的智能优化算法已成为解决P-模型的关键^[6]。为此，本文从生物免疫学中危险理论蕴涵的生物机理出发，设计求解单目标P-模型的微种群免疫优化算法(Micro-Immune Optimization Algorithm，μIOA)。数值比较性实验显示，μIOA在寻优效率、搜索效果和噪声抑制能力等方面均具有明显优势。

1 问题描述

考虑如下单目标概率优化问题(P)：

式中：D为决策区域； x 为p维决策向量；a_i为解向量的分量区间左端点；b_i为解向量的分量区间右端点； ξ ∈ R ^q为分布特性未知的有界随机向量；Pr{·}为概率算子；α为置信水平，0＜α≤1；f( x ,ξ )为关于 x 的非线性有界随机函数。 x ^*∈D称为问题(P)的最优解，若满足以上机会约束的任意 x ∈D，均有f ( x ^*)≤f ( x )。当在点 x 处 ξ 的样本大小M(简称为 x 的样本大小)给定后，可经由Monte Carlo随机模拟确定f ( x )的估计值^[3]，即若 ξ 的M个样本为 ξ ⁱ，1≤i≤M，不妨设f( x ,ξ ⁱ)≤f( x ,ξ ⁱ⁺¹)，则f ( x )的近似值为f( x ,ξ ^k)，k=。 鉴于问题(P)的随机向量的概率分布未知，下面通过自适应采样方法确定 x 的样本大小和估计近似目标值，进而设计μIOA求解近似解。

2 危险理论

危险理论^[15]作为一种较为流行的免疫学理论，是描述免疫系统感知外来物质后，依据免疫细胞受损程度作出相应反应的过程。该理论认为，引起免疫应答的因素不是所有非自我物质，而是损害机体的危险信号(danger)，也即只有当受损细胞产生有害信号且触及到抗原呈递细胞(Antigen Presenting Cells，APCs)后，免疫系统才产生应答，而对机体无害的非自我物质不作任何应答。具体而言，当机体中出现被扭曲或凋亡的细胞时，APC是否能被激活依赖于第0信号和邻近细胞的健康情况；一旦它被激活，则向辅助性T细胞传递第1、2信号，其中，第1信号向辅助性T细胞暗示免疫系统已发现危害物质，并发送此物质的危害程度信息，第2信号促使辅助性T细胞产生淋巴因子，致使免疫系统开始应答。从细胞感染角度，免疫细胞分为未感染细胞、易感染细胞和已感染细胞。应答开始时，免疫系统会形成免疫细胞危险区域，通过B细胞的应答，清除危险区域内的已感染细胞。

基于以上免疫理论和问题(P)，μIOA的运行机制如图 1所示。可知，静态采样的作用是依据相同的样本大小，计算各B细胞的亲和力；进化群体中每个B细胞作为未感染、已感染或易感染细胞，有自身的危险区域；危险半径更新与群体分割是依据算法的迭代数和问题(P)的决策区域对B细胞的危险半径作动态调整，并依据进化群体中B细胞的分布和危险半径将群体划分为未感染、已感染或易感染子群。各子群依据不同的繁殖和变异方式实施进化，然后选出每个进化后的子群中最好的B细胞(各B细胞的危险半径为初始半径)与现存的危险区域中代表性B细胞组合。群体更新是依据组合后 的群体中B细胞的危险半径划分为未感染、已感染或易感染子群，然后抽出各子群中最好的B细胞与随机生成的新B细胞组合，构成新的进化群。

3 算法描述

危险理论描述了B细胞如何清除危险信号的过程，为设计μIOA求解P-模型提供了新思路。将危险信号视为问题本身，B细胞视为优化问题(P)的候选解，其包含3种类型：未感染、已感染和易感染B细胞。细胞 x 的亲和力由Sigmoid函数确定：

式中：η∈(0,1)。

基于图 1和问题(P)，μIOA可描述如下：

步骤1 输入参数：群体规模N，最大迭代次数G_max，初始危险半径R，初始最小和最大样本大小m和M，样本参数v。

步骤2 置n←1，随机产生群体规模为N的初始B细胞群A={ x ₁,x ₂,…,x _N} ，依据m和M，计算A中所有B细胞的亲和力，在此

式中：$\hat{f}$_i( x _j)为 x _j在样本大小为m+i-1下，按照Monte Carlo 模拟获得。

步骤3 危险半径更新和群体分割: 依据亲和力，降幂排序群体A中B细胞，借助危险区域，产生未感染群B₁，易感染群B₂,B₃,…,B_d-1和已感染群B_d，d由B细胞的危险半径和亲和力确定，d≤5。

步骤4 A中第i个B细胞繁殖N+2-i个克隆，总繁殖数为N(N+3)/2。

步骤5 B_i中B细胞克隆的变异概率为

B₁中B细胞克隆实施高斯变异，B₂中B细胞克隆实施柯西变异，B₃中B细胞克隆实施多项式变异，B₄~B_d-1中B细胞克隆实施非均匀变异，B_d中B细胞克隆实施柯西变异，获得变异后的群体B₁^*,B₂^*,…,B_d^*。

步骤6 经由式(2)，计算B₁^*,B₂^*,…,B_d^*中克隆的亲和力；将各群体中亲和力最高的克隆与步骤3中各群体的最好B细胞组合构成C。

步骤7 执行自适应采样方案，C中B细胞依据获得的样本大小和m，经由式(2),获得各自的亲和力。

步骤8 借助初始危险半径R，按照步骤3的方式产生未感染群、易感染群和已感染群；抽取各子群中亲和力最高的B细胞构成群体F。

步骤9 若|F|＜ N，则F中的B细胞与随机生成的B细胞构成规模为N的新群体A，其中新的B细胞依据式(2)，计算各自的亲和力；若|F|≥N，则F中亲和力较高的N个B细胞更新群体A。其中，|F|为群体F的成员个数。

步骤10 置n←n+1；若n＞G_max，则结束，输出结果；否则，转步骤3。

以上算法中，R在w/(4N)~w/N之间取值，w为决策向量中所有分量的变化幅度的最大值。步骤3的目的是依据B细胞的亲和力，将群体A划分为B₁,B₂,…,B_d，B₁中B细胞的亲和力高于B₂中B细胞的亲和力，B₂中B细胞的亲和力高于B₃中B细胞的亲和力，依此类推。值得指出的是，以上子群划分的方法不同于小生境方法。步骤5要求不同类型的子群依据自身的变异概率，采用不同变异方式对B细胞实施变异，使B细胞多方位勘测局部区域，同时多渠道搜寻高质量和多样的B细胞。步骤8对组合群体进行分割后，在各子群中选出最好B细胞构成新群体，目的在于确保新进化群有足够的多样性。另外，尽管要求步骤4的进化群体的克隆数为N(N+3)/2，但因该算法是小种群优化方法，N被要求取较小的值(5~8之间)^[16-18]，所以整个算法的搜索效率能得到保证。其次，该算法在步骤7中自适应地确定B细胞的样本大小，进而计算B细胞的亲和力，此有助于提高算法搜索效率和增强辨析进化群体中优质抗体的能力。步骤3和步骤7的具体设计如下：

1) 危险半径更新： x _i的危险半径为

危险区域为决策区域D中如下超正方体：

2) 群体分割：基于危险半径更新，A中落入超正方体V₁中的B细胞构成未感染群B₁，然后将B₁中的B细胞从A中删除，余下的B细胞中，由亲和力最高的B细胞和其危险区域按同样方式产生子群B₂，依此重复，直到产生最后一个子群，不妨设共有d个子群。第2~d-1个子群称为易感染群，第d个子群称为已感染子群B_d。

3) 自适应采样：对于规模为J的B细胞群C，由于随机因素的影响，很容易误认为较差B细胞是优质的，而最好的B细胞是劣质的，因此为了削减计算开销和提高寻优效率，优质B细胞被分配大的样本大小，而劣质B细胞被分配小的样本大小。为此，记C={ x ₁,x ₂,…,x _J}。群体C的样本大小设置为

B细胞 x _i依据式(6)获得样本大小:

另外,随着n的增大，M_n也逐渐增大。为了防止因采样规模过大，导致算法的运行效率受到影响，采用动态的样本规模阈值m_n控制B细胞的采样大小，即

由此，B细胞 x _i的样本大小为

4 计算复杂度分析

根据第3节算法描述，μIOA的计算复杂度由步骤3~步骤8确定。在一次迭代周期内，步骤3需将进化群体A划分为子群B₁,B₂,…,B_d，依次判断B细胞是否在危险区域，因此其计算复杂度为O(N²)；步骤4、步骤5执行繁殖和变异，共运行N(N+3)p/2次；步骤6由初始样本大小m和克隆数确定其计算复杂度，即O(mN²)；步骤7在最坏情形下，计算复杂度为m_n(m_n+m)|C|；在步骤8中，群体C中B细胞需依据亲和力进行降幂排序和群体分割，均需运行|C|(|C|-1)/2 次，所以步骤8的计算复杂度为O(|C|²)。概括起来，结合|C|≤2N以及m较小，μIOA在最坏情形下的计算复杂度为

由于问题(P)包含随机向量，当样本大小较大时，常规智能优化算法求解此问题均需较大计算量，特别当采用静态采样方法计算目标函数值时，若试图获得较好效果，必借助较大的样本大小来补偿算法的噪声抑制能力。然而,由式(9)获知，μIOA是一种自适应采样优化算法，其计算复杂度由N、p和m_n确定；算法在进化初期，搜索速度快且执行大范围搜索；在进化后期，搜索偏慢，执行局部搜索。

5 数值实验

本实验在Window XP/CPU/3.30 GHz，RAM/2.98 GB，VC+ +环境下进行。为比较分析μIOA的性能，选取具有代表性的三种智能优化算法参与比较，即Xiao-SPSO^[13]、Ai-SPSO^[12]和GA^[3]。测试事例包括3个理论测试问题和1个工程优化问题。为避免随机因素对算法搜索质量的影响，每种算法对每个测试问题均独立运行100次。之后，各自获得的100个结果被用于执行统计分析。各算法的终止准则是评价次数为10⁴。另外，参与比较的算法在相应文献中均要求个体具有较大样本大小，这使得算法的搜索效率受到极大影响；经由算法调试，以及兼顾效率和效果等因素，设置个体样本大小为300，其他参数的设置由相应文献获知。其次，μIOA主要包括3个可调参数：R、M和v。M和v为控制个体采样大小的参数，若M和v偏小，搜索效果不理想；反之，则算法搜索效率降低；它们可在5~10之间取值。进一步，R是一个子群划分参数，当R较小时，算法群体多样 性受影响；反之，则算法进化单一。R在w/(4N)~ w/N之间取值。算法调试后，μIOA的参数设置为N=5，R=1，m=2，M=10，v=5，η依问题而定。为使各算法获得的目标值与理论值贴近，所获解均需重新估计其目标值,样本大小为10⁵。

问题1

该问题是经由文献^[18]的Sphere函数转化获得。尽管此问题是一个5维的简单随机优化问题，但噪声强度σ取较大值时，随机因素对优化质量的影响较大,求解变得困难，取α=0.9。若σ取1、10、30或50，则该问题的理论最优值依次为1.281 6、12.816 0、38.450 0和64.083 3。各算法求解100次后，获得的最好目标值的统计结果和平均运行时间如表 1所示，平均搜索曲线如图 2所示。表 1中：min、max、mean和St.Dev为算法100次运行获得100解的最小、最大、平均目标值和目标值的均方差；CI和AR分别为置信区间和平均执行时间。图 2中：Av(n)为算法100次运行后获得第n代群体的最小目标值的均值。

由表 1可知，当噪声强度σ=1或10时，μIOA比Xiao-SPSO 和Ai-SPSO能获得更好的解质量，Xiao-SPSO 和Ai-SPSO的解质量相近，GA的解质量较差，此可由图 2得到验证。另一方面，μIOA、Xiao-SPSO 和Ai-SPSO的搜索效果较稳定，各自在不同噪声强度下获得的平均值与理论值的偏差较小，且获得的置信区间较窄，但GA较差。当σ=30时，μIOA、Xiao-SPSO 和Ai-SPSO的解质量相近，GA的解质量较差，μIOA的搜索效果最稳定，且获得的置信区间较窄。当σ=50时，Xiao-SPSO 和Ai-SPSO获得的效果比μIOA获得的效果稍好。从执行效率看，μIOA的执行效率明显高于其他算法的执行效率； 参与比较的算法的平均执行效率相差不明显。整体上，μIOA求解问题1有一定的优势。另外,表 1也表明，随着噪声强度的增大，以上各项指标的值相应增大，问题求解的难度相应加大。

问题2

该问题是经由文献^[18]的Rosenbrock函数转化获得，其变量之间存在较强的耦合性，搜索其最优解较难。取置信水平α=0.9。由于此问题的机会约束条件中确定性函数的最小值为0,所以当σ为1、10、30或50时，该问题的理论最优值依次与问题1获得的理论值是相同的。以上算法获得的统计结果如表 2所示，平均搜索曲线如图 3所示。

表 2中的平均值说明，μIOA所获解质量明显优于参与比较的算法的解质量，Xiao-SPSO和 Ai-SPSO次之，而GA获得的效果最差。另一方面，经由以上均方差，μIOA、Xiao-SPSO 和Ai-SPSO的搜索效果较为稳定(见图 3)，而GA较差。其次，经由以上平均运行时间，参与比较的算法的执行效率没有明显差异，μIOA的执行效率是这些算法的2倍多。因此，μIOA求解问题2具有明显优势。

问题3

该问题是经由文献^[12]中E-模型转化获得的多模态概率优化问题。由于随机变量的分布类型多样化，机会约束中决策变量受到随机变量扰动的干扰，所以算法求解较为困难。取置信水平α为0.4、0.9，该问题的理论最优解尚不清楚。以上算法获得的统计结果如表 3所示，平均搜索曲线如图 4所示。

经由表 3的平均值获知，在低置信水平下(α=0.4)，以上问题的解的可信度低，求解较易；GA和μIOA获得的解质量较贴近且较好；经由均方差值获知，此两算法的搜索效果较稳定；然而，Xiao-SPSO和Ai-SPSO的解质量相对较差，搜索效果欠稳定。在高置信水平下(α=0.9)，以上问题的解的可信度高，但求解偏难。

在此情形下，μIOA在所获解质量和搜索效果的稳定性方面均优于其他算法，GA次之；Xiao-SPSO和 Ai-SPSO的解质量相近,且劣于μIOA和GA。 特别值得强调的是，与GA相比，Xiao-SPSO和 Ai-SPSO求解问题1和问题2能获得较好解质量，但求解问题3获得的解质量差于GA获得的解质量，表明Xiao-SPSO和 Ai-SPSO求解多模态概率优化问题时存在群体多样性不足的缺陷。另一方面，在执行效率方面，参与比较的算法具有相近的执行效率，μIOA的执行效率至少是这些算法的2倍。

问题4 公交车调度

将每天公交车运营时间分成K个时段,x_i为公交车发车间隔，1≤i≤K,N(x_i)为第i个时段内发车间隔为x_i情况下的乘客总数,r为单一公交票价,μ_s为单位乘客剩余的货币价值，e_f和e_w分别为票价和发车间隔的乘客需求弹性因子,μ₀为单位车辆在单位时间内的运营成本,t_i为运行时间段,t_i^r为第i个时段开出的第r班车全程的开行时间,τ为平均一位乘客用于上下车的平均值,μ_w为乘客等待时间的时间价值。基于此,文献^[19]获得多时段公交发车间隔优化问题的E-模型,现将其转化为P-模型:

模型中的参数设置由文献^[19]获知,特别地，K=6。此问题是一种非连续、非线性的机会约束规划问题。取置信水平α为0.4、0.9，以上算法获得的统计结果如表 4所示，算法的平均搜索曲线如图 5所示。

经由表 4可知，在不同置信水平下，μIOA所获解的平均值均大于其他算法获得的平均值，且均方差均小于其他算法获得的均方差，因此μIOA获得的解质量最好且搜索效果最稳定； 其次，Xiao-SPSO的解质量和搜索效果次之，Ai-SPSO的解质量和搜索效果比GA好。另外，在以上置信水平设置下，参与比较的算法的执行效率差异不明显；μIOA的执行效率至少是这些算法的1.5倍。

6 结 论

鉴于概率优化是一类具有广泛应用背景和求解较难的不确定性规划问题，基于免疫学中较为关注的危险理论和问题具有的固有特性,建立适用于此类问题的微种群免疫优化算法(μIOA)。μIOA经理论分析和实验验证表明：

1) 计算复杂度依赖于迭代数、变量维数和群体规模。

2) 具有群体规模小、可调参数少、自适应能力强和执行效率高等优点。

3) 搜索效果具有明显优势，噪声抑制能力强，对复杂的P-模型具有一定的应用潜力。

尽管μIOA已具有明显优势，但在处理复杂优化问题(如问题4)时，搜索效果欠稳定，辨析优质个体的能力有待增强。