文摘
这工作调查bioinspired microimmune优化算法来解决一种通用的简略非线性约束编程没有任何先验分布的期望值。算法的研究中,两个随机变量下界样本估计是理论上发展估计个体的经验值。两个自适应赛车抽样方案旨在识别那些竞争个体在给定的人口,由高质量的个人可以获得大的抽样大小。免疫进化机制以及局部搜索方法,构造发展当前的人口。比较实验表明,该算法能有效解决高维基准问题和潜力的应用程序。
1。介绍
许多实际工程优化问题,例如工业控制、项目管理、投资组合投资,和运输物流,或随机变量通常包括随机参数。一般来说,他们可以通过一些现有的智能优化方法解决(即静态抽样策略。,each candidate is with the same sampling size), after being transformed into constrained expected value programming (CEVP), chance constrained programming, or probabilistic optimization models. Although CEVP is a relatively simple topic in the context of stochastic programming, it is a still challenging topic, as it is difficult to find feasible solutions and meanwhile the quality of the solution depends greatly on environmental disturbance. The main concern of solving CEVP involves two aspects: (i) when stochastic probabilistic distributions are unknown, it becomes crucial to distinguish those high-quality individuals from the current population in uncertain environments, and (ii) although static sampling strategies are a usual way to handle random factors, the expensive computational cost is inevitable, and hence adaptive sampling strategies with low computational cost are desired.
当随机特性未知,CEVP模型通常被他们的样本平均近似模型(1,2之后,一些新的或现有的技术可以用来发现他们的近似解。在数学上,一些研究人员3- - - - - -5)之间的关系探讨CEVP模型及其近似的和获得一些有价值的下界估计样本容量能够用来设计自适应抽样规则。另一方面,智能优化技术已经成为流行了nonconstrained期望值编程问题[6- - - - - -8),一些先进的抽样技术,例如,自适应抽样技术和样本分配方案,可以有效地抑制环境影响搜索的过程解决方案。不幸的是,研究一般CEVP已经很少在文献中报道,因为期望值的约束。即使如此,一些研究人员努力研究新的或混合智能优化方法这样的不确定规划问题。例如,刘和Y.-K。刘(9)提出了一种混合智能的方法来解决一般模糊期望值模型,将进化算法与神经网络的学习方法。太阳和高10]提出一种改进的微分进化的方式来解决一个期望值编程问题,根据静态采样和松弛的选择。
而免疫优化作为另一个受欢迎的分支是静态或动态优化问题的研究11,12),它仍然是开放的随机规划问题。之间的一些作品比较经典的智能方法和免疫优化算法对随机规划证明其中一个分支就是竞争力。例如,谢长廷和你13)提出了一个两阶段的免疫优化的方法来解决最优reliability-redundancy分配问题。他们的数值结果,基于四个基准问题已经表明,这样的方法优于对比算法。赵et al。14)提出了一个混合免疫优化的处理机会约束规划方法,两家运营商的双克隆和双突变采用加速进化的过程。
在目前的工作中,我们研究两个下界估计样本容量理论上,基于霍夫丁的不平等15,16]。之后,两种高效的自适应赛车抽样方法设计计算的经验值随机目标和约束函数。一起,这些免疫灵感包含在克隆选择原理,用于开发一个microimmune优化算法(IOA)处理,非线性、高维约束期望值编程问题。这种方法是明显不同于任何现有的免疫优化的方法。一方面,这两个下界估计开发控制随机变量的样本大小,而局部搜索方法采用加强本地开发的能力;另一方面,利用两种自适应赛车抽样方法确定动态这样的样本大小来计算的经验值在每个目标和约束函数。实验结果表明IOA是高维多峰期望值的另一个工具的编程问题。
2。问题陈述和预赛
一般考虑以下简略期望值非线性约束规划问题: 与有界闭域在、决策向量在,和随机向量在,在那里是期望的操作员;和分别是随机目标和约束函数,其中至少一个是非线性的和持续的在吗;和是确定的和连续的约束功能。如果候选解决方案满足上述约束,它被称为一个可行解和不可行解。介绍以下约束违反函数检查如果候选人是可行的: 很明显,是可行的只有当。如果,我们开优于。为了解决CEVP,我们将上述问题转换为以下的近似模型(SAM): 在哪里和的抽样大小吗在点分别对随机目标和约束函数;是观察。众所周知,山姆可以达到问题的最优解的问题 当和基于大量的法律17]。我们说是一个实际可行的解决方案 如果上述约束在山姆感到满意。
在随后的工作中,两个自适应抽样方案将被设计来估计经验为每个目标和约束值。我们在这里引用以下的结论。
定理1((霍夫丁不等式)[15,16])。让是一组,让是一个概率分布函数X;表示上定义的实值函数与为,在那里和是实数满足。让i.i.d.随机变量的样本在,分别。然后,以下不平等是正确的:
推论2(见[15,16])。如果i.i.d.随机变量的意思吗和,,然后 的概率至少,在那里和;和表示的观察和显著性水平。
3所示。赛车抽样方法
3.1。期望值约束处理
通常,当一个智能优化方法与静态抽样选择来解决上述问题 ,每个人相同的和足够大的样本大小,这必然导致较高的计算复杂度。因此,为了确保每个个体在给定有限的人口有一个合理的抽样大小,我们在本节内给一个下界的估计的值来控制与基于上述问题的样本平均近似模型。定义
我们下给一个下界的估计来证明这一点是的一个子集的概率,可以在附件中找到证据。
引理3。如果存在和这样与,一个,前提是 在哪里和表示的大小。
在(6),和决定的范围内随机约束函数在点。计算最大抽样区别是观测的随机约束。我们还观察到一次和定义,是由。此外,这些高质量的个人通常应该大采样大小,相反那些劣质的只能小采样大小。这意味着不同的个体将获得不同的抽样大小。在此基础上考虑和比赛排名的想法,我们下一个计算任何期望值的经验值约束函数在给定的个人在,也就是说,。这是完成以下racing-based约束评估方法(RCEA)。
步骤1。输入参数:初始取样大小采样幅度,松弛因子,显著性水平,最大的抽样大小。
步骤2。集,,;计算估计通过观察。
步骤3。集。
步骤4。创建观察和更新;也就是说,
第5步。集;如果和,然后去一步。
步骤6。输出估计的价值。
在上面的公式中,和用于上述算法终止时决定。一旦停止上述过程,获得它的抽样大小;也就是说,。我们注意到,是非常小的很大。因此,我们说一个经验是可行的解决方案,如果在的前提,上面的确定性约束得到满足。此外,RCEA表明实证可行的解决方案可以获得大量取样大小,这样吗接近的期望值。
3.2。目标函数评价
根据上述RCEA和确定性约束问题 ,上面的人口分为两个亚种群的和,在那里由实证可行的解决方案。我们研究的另一个下界估计的值来控制与,依赖样本平均近似问题的模型 。之后,设计一种方法来计算经验客观的经验值可行的解决方案。这一点,介绍 在哪里和代表个人的理论和实证客观值的最小值,分别。下面给出下界估计,通过识别之间的近似关系和。证明可以在附录。
引理4。如果存在和这样与,然后,前提是 在哪里
像上面的约束处理方法,我们下一个计算个人的经验客观价值通过以下racing-based客观评价方法(ROEA)。
步骤1。输入参数:和上面所提到的,最初的抽样大小以及人口。
步骤2。集,,,。
步骤3。计算经验客观的平均水平观察为每个单独的在,也就是说,;写和。
步骤4。删除这些元素令人满意的。
第5步。集。
步骤6。更新经验客观的元素的值通过
步骤7。集。
步骤8。如果和,然后再回到步骤;否则,输出所有个人的经验客观价值。
通过上述算法,这些人可以获得各自的经验值和目标不同的抽样大小。那些高质量的个人可以获得大量取样大小,因此他们的经验客观值可以达到理论客观的价值。
4所示。算法语句
免疫细胞克隆选择原理解释了学习的模式结构入侵的病原体。它包括许多生物灵感能够采用的设计IOA,如免疫选择、克隆和繁殖。基于RCEA ROEA以上以及一般免疫的灵感,IOA可以图所示1。我们认为抗原Ag)问题山姆本身,而候选人从设计空间被认为是实数编码抗体。在一个运行的时期IOA图1,目前的人口是第一分为经验上面执行RCEA后可行和不可行抗体的细胞亚群。第二,这些经验可行抗体需要通过ROEA计算经验的客观价值。他们比经验将产生更多的克隆不可行抗体通过扩散。执行之后,所有的克隆突变。如果父母优于其克隆,它将执行本地搜索,相反它是更新的最好的克隆。基于图1,下面详细IOA可以制定。
步骤1。输入参数:人口规模,最大克隆的大小、采样参数和,松弛因子,显著性水平和最大迭代数。
步骤2。集。
步骤3。生成初始种群的随机的抗体。
步骤4。计算抗体的经验约束违反通过RCEA和(1),也就是说,与。
第5步。分进经验可行的族群和不可行的分组人口。
步骤6。计算抗体的经验客观价值通过ROEA以上。
步骤7。对于每一个抗体在,我们有以下。
一步7.1。增殖一套克隆与大小(例如,繁殖后代)。
一步7.2。突变克隆突变率之后通过传统的多项式变异,并产生一系列突变克隆,在那里。
一步7.3。消除经验不可行的克隆通过RCEA。
一步7.4。克隆的经验客观值计算通过ROEA。
一步7.5。如果最好的克隆的经验客观价值小于,它将更新;否则,抗体作为一个初始状态创建一个更好的经验可行抗体取代它的本地搜索方法(18]ROEA和取样大小。
步骤8。对于每一个抗体在,我们有以下。
一步8.1。抗体创建一个无性系的人口克隆的大小;所有的克隆执行与突变速率变异吗通过传统的非均匀变异和创建一个突变克隆人口,在那里
一步8.2。检查是否存在经验可行的克隆RCEA和(1);如果是的,最好的克隆与最小的经验由ROEA取代客观价值,相反的克隆最小约束违反更新。
第9步。 ,。
第10步。如果请转到步骤,反之输出最好的抗体被认为是最优的解决方案。
正如上面我们制定的,当前的人口分为两个亚种群,检查后如果有经验可行抗体。每个分组人口更新通过扩散、变异和选择。一步让那些经验可行抗体通过扩散和多项式变异搜索更好的克隆。一旦一些抗体不能产生有价值的克隆,据报道本地搜索算法是用于执行当地的进化,提高搜索质量的解决方案。一步的目的敦促那些可怜的抗体通过扩散和非均匀变异创建不同的克隆。
此外,IOA的计算复杂度是决定步骤6和7.2。一步需要最多次计算经验约束违反。在步骤,我们需要计算抗体的经验客观价值,评估次了。一步执行突变最多次了。因此,IOA计算的复杂性,在最坏的情况下可以给出的
5。实验分析
我们的实验是在个人电脑上执行(/ 3 GHz CPU、RAM / 2 GB)与vc++软件。为了检查IOA的特点,四个智能优化算法,也就是说,两个竞争稳定遗传算法(SSGA-A和SSGA-B) (19)和最近两次免疫优化方法NIOA-A和NIOA-B [20.),来参与比较分析的两个100 -维多通道预期值优化问题。指出固定取样大小相同的两个遗传算法为每个单独的还是可以解决的 问题,因为他们的约束得分函数的设计是基于静态采样策略;两个免疫算法与动态取样大小对所有个体在进化的过程。另一方面,因为NIOA-B不能有效处理高维问题,我们在本节中,改善了OCBA [21]。这些比较的方法,在一起IOA,共享相同的终止判据;也就是说,每种方法的总评价执行30倍,而在每个测试问题。他们的参数设置相同的文献除了他们进化的种群大小。手工实验优化后,他们把人口规模40。IOA小人口规模在3和5,而三个参数,,作为重要的效率参数通常设置为小整数。我们在这里集合,,,,,。此外,那些最好的解决方案,获得所有的算法为每个测试问题评估106因为需求的算法比较。
例5。考虑 这是一个多通道期望值规划问题得到通过修改静态多峰优化问题(22),。解决此类问题的主要困难是,高维度和多峰性很难找到理想的解决方案。我们解决上述问题的近似模型SAM的部分2,而不是将该模型转换为一个确定的分析。运行之后,分别为30日,上述每个算法获得30最佳解决方案用于比较。他们的统计结果表中列出1,而数据2和3画出框图的客观的获得和他们的平均搜索值曲线,分别。
在表1值FR,第七列中列出的暗示,而所有的算法为每个运行可以找到许多可行的解决方案,他们的可行的解决方案是不同的。IOA可以获得许多方法相比更可行的解决方案。这说明RCEA约束处理方法,提出了部分3,可以确保IOA找到可行的解决方案和高概率为90%一个运行。另一方面,列2 - 6中的统计结果显示IOA的解决方案质量明显优于其他方法获得的同时NIOA-A和NIOA-B是次要的。对性能效率,我们很容易看到IOA是一种高效的优化算法,因为它花的时间最少寻求运行所需的解决方案。我们也注意到SSGA-A和SSGA-B展示他们的高计算复杂度,因为他们的平均运行时,这表明两种遗传算法与静态抽样策略轻易造成昂贵的计算成本。
框图如图2每个算法,由30客观值,展示这一事实,除了IOA获得最好的效果与其他四个算法相比,NIOA-A NIOA-B和类似的性能特征可以超过SSGA-A和SSGA-B工作。由图3我们观察到,IOA可以快速找到所需的解决方案,实现稳定搜索但是其他算法,特别是两个遗传算法,很容易进入本地搜索。完全解决上面的高维问题时,五个算法有不同的效率,解决品质,和搜索特征;IOA西装上面的问题,表现出最好的性能,主要的原因在于,它可以有效地结合与ROEA RCEA发现更多实际可行的个人和鼓励他们发展逐渐向所需的地区扩散和突变。然而,这些方法相比呈现相对较弱的表现。特别是SSGA-A和SSGA-B容易进入本地搜索,花最运行时为了解决上面的问题,作为他们的约束处理和选择技术难以适应高维多峰问题。NIOA-A NIOA-B优于两种遗传算法等,由于他们的自适应采样和约束处理技术。
例6。考虑 这仍然是一个困难的多峰优化问题获得通过修改静态多峰优化问题(23),其中包括100决策变量(例如,)和3随机变量大大影响搜索质量的解决方案。解决这些问题的难度是目标函数多通道和决策变量是无界的。类似于上面的实验中,我们获得的统计结果表中给出的方法2,而相应的框情节和他们的平均搜索数据曲线绘制4和5,分别。
FR的值表2说明它也很难解决的例子6由于随机变量和高维度。即使如此,NIOA-A NIOA-B,IOA每次运行都可以获得可行的解决方案。SSGA-A SSGA-B,然而,最多只能得到53%的可行的解决方案;也就是,他们只能获得53 100年之后执行可行的解决方案。加上FR的值表1之前,尽管这样的两种方法可以获得更大的价值的意思是比其他方法,它们对解决方案质量差,效率,和搜索的稳定性。因此,他们需要做一些改进,例如,他们的约束处理。我们注意到IOA比NIOA-A或NIOA-B因其效率和价值的意思。我们强调,而NIOA-A和NIOA-B只能获得很小的值的意思是相比之下,IOA,他们仍然有价值的解决这样的难题。相对,NIOA-B表现超过NIOA-A。
事实似乎SSGA-A SSGA-B优于NIOA-A, NIOA-B,IOA通过数据4和5,因为盒子情节图4和平均搜索曲线在图5远的水平线。事实上,列在表72清楚地表明,这两种遗传算法无法找到可行的解决方案中47次100分,而其他方法是相反的。这些事实表明不可行的解决方案的决定比可行域有更大的目标函数值。
概要地,当解决上面的两个例子中,五个算法呈现不同的特征。SSGA-A和SSGA-B有类似的性能属性,所以做NIOA-A和NIOA-B。IOA表现良好的方法相比,虽然NIOA-B是次要的。
6。结论和进一步的工作
我们在这工作专注于研究microimmune优化算法来解决一般约束期望值的编程模型,依赖将该模型转换为一个(SAM)的近似模型。一个这样的模型要求不同的候选解决方案有不同的样本大小,特别是每个候选人有两种样本的大小。随后,两个随机向量的下界估计理论上发达,分别应用于处理约束个人的期望值在当前人口和计算经验的客观价值。基于这样的两个估计和比赛排名的想法,两个赛车抽样方法提出执行个人评价和约束处理,分别。之后,基于赛车抽样microimmune优化算法IOA提出应对这样的近似模型,人口不多的优点,强大的干扰抑制,有效约束处理,自适应抽样,效率高。理论分析表明,主要取决于IOA的计算复杂性,,由于人口稀少参数和已知问题。通过高维多峰测试问题,比较实验结果可以得出一些结论:RCEA RCOEA可以IOA动态确定样本大小不同的个体在进化的过程中,局部搜索方法采用可以帮助IOA加强局部搜索,随机参数自适应采样技术可以有效地解决, 方法相比,IOA表现良好,SSGA-A和SSGA-B高维问题需要做出一些改进。进一步的,而我们如何做一些研究探讨免疫优化方法来解决高维约束期望值的编程问题,一些问题将进一步研究。例如,IOA理论需要研究了收敛性分析,而其工程应用程序进行了讨论。
附录
引理的证明3。让由于存在这样与,(3)我们获得 因此, 因此, 所以,结论为真。
引理的证明4。自是有限的,存在吗这样。如果,然后 因此,如果 我们有 或 否则,我们收购 这个收益率收缩。因此,由(3)我们获得 因此, 通过这种方式,它遵循从(A.10),上述结论是正确的。
相互竞争的利益
作者宣称没有利益冲突。
确认
这部分工作是支持由国家自然科学基金(61563009)和中国教育部博士基金(20125201110003)。