论文部分内容阅读
摘 要： 贝叶斯优化算法是分布估计算法中最典型的代表。它利用贝叶斯网络采样对种群进行更新，而贝叶斯网络的寻优学习是一个复杂的搜索过程，运算时间较长，计算量大，这也正是制约贝叶斯优化算法应用的一个主要原因。本文引入免疫算法机制，使其对贝叶斯网络产生的解进行有导向的变异，提高个体的适应度值，从而减少贝叶斯网络的构建次数，降低计算量。研究结果表明，改进后的贝叶斯优化算法不仅具有更强的寻优能力，而且大大减少了计算量和运算时间。
关键词： 免疫机制 贝叶斯网络 种群 寻优
分布估计算法在求解问题时具有比遗传算法更好的性能，在解决实际应用中的复杂优化问题具有很大潜力。因此最近几年来，越来越多的学者对分布估计算法的研究产生了兴趣，并逐渐成为当前进化计算领域前沿的研究内容。而贝叶斯优化算法（Bayesian Optimization Algorithm，简称BOA算法）作为分布估计算法的典型代表，在求解复杂问题时有其独特优势，特别是针对NP问题，它表现出良好的性能。但在构建贝叶斯网络模型时需要较大的计算量，使贝叶斯优化算法在求解复杂优化问题时需要较长的运算时间，从而限制了算法的应用。
针对这一问题，本文在传统贝叶斯优化算法中引入了免疫规划算法的疫苗接种机制，利用问题的特征信息制作疫苗，并以一定的概率干预贝叶斯网络的全局搜索进程，从而克服以往优化算法中变异操作的不确定性和盲目性，提高算法的快速性和收敛性，降低贝叶斯优化算法的计算量。
1.贝叶斯优化算法的基本原理
1.1贝叶斯优化算法的基本流程
贝叶斯优化算法是基于种群进化的一种算法，通常初始种群由满足均匀分布的可行解组成。在产生初始群体之后，重复以下步骤直到满足终止条件。首先，利用一种适当的选择方法从当前群体中选出一组比较优秀的解；然后，利用从优选的解集合中提取信息建立优选解集的一个贝叶斯网络模型；接着，通过对贝叶斯网络进行采样学习生成一组新的候选解；最后把新产生的候选解加入到当前群体，取代其中一些低适应度的解。贝叶斯优化算法原理可描述如下[1]：
步骤1：t←0，随机产生初始群体Pop（t）；
步骤2：利用某种选择机制从Pop（t）中选择部分优秀解构成S（t）；
步骤3：利用贝叶斯网络概率模型建立S（t）的概率分布；
步骤4：依据概率分布抽样产生新的解集O（t）；
步骤5：用O（t）替换Pop（t）的部分个体形成下一代群体Pop（t+1），t←t+1；
步骤6：若不满足终止条件，继续执行步骤2。
贝叶斯优化算法的每一个步骤都有多种不同的方法可以选择。比如：初始群体可以根据问题的先验信息来产生；群体选择方法可以用任一种可行的选择方法（如轮盘赌法、锦标赛选择法和截断选择法等）；贝叶斯网络结构的学习算法也可选择不同的算法（如爬山法和k2法等）；贝叶斯网络参数的学习算法也有多种（如最大似然估计算法和贝叶斯估计算法等）。
1.2贝叶斯网络的学习和抽样
贝叶斯优化算法利用贝叶斯网络表示概率模型，通过贝叶斯网络的学习与抽样产生新个体，即贝叶斯优化算法的核心和关键是贝叶斯网络。贝叶斯网络是一个有向无环图，它既可以对数据进行描述，又可以通过采样产生与所给数据性质相同或相似的数据，因此常用于对离散或连续变量的多项式数据进行建模。
通常情况下，一个贝叶斯网络由网络结构和网络参数两个部分组成。贝叶斯网络结构中的节点表示各个变量（在此对应于个体中的基因），节点之间的有向边表示变量之间的条件依赖关系；贝叶斯网络参数是各变量条件概率分布表的集合。
一个典型的五个节点贝叶斯网络（包括网络拓扑和参数）如图1.1所示。该网络的联合概率可以表示为：
P（B，E，A，C，R）=P（B）P（E）P（A|B，E）P（R|E）P（C|A）（1-1）
贝叶斯网络的学习主要包括网络结构和条件概率参数的学习。在贝叶斯优化算法中，由于优选解群体中每一个变量的取值是确定的，因此当给定网络结构时，参数的学习是比较简单的。贝叶斯网络结构的学习是寻找对先验知识和数据拟合最好的网络结构，虽用全局搜索算法可得到较好的解，但计算量太大。为了能够快速学习贝叶斯网络结构（即使是近似解），常采用基于打分测度的贪婪算法[2]。
学习贝叶斯网络的结构和参数后，新的候选解将根据所学习的网络所描述的分布产生。贝叶斯网络的抽样过程可描述如下[2]：
步骤1：计算所有变量之间的祖孙关系；
步骤2：利用贝叶斯网络的条件概率按祖孙关系顺序产生所有变量的基因值；
步骤3：若需再生成多个个体，则继续执行步骤2。
2.引入免疫机制的改进贝叶斯优化算法原理
根据上述分析得知贝叶斯优化算法的计算量主要集中在贝叶斯网络的构建上，目前降低贝叶斯优化算法的计算量主要有两种方式，一种是通过对贝叶斯网络本身的改进，即通过对贝叶斯网络的结构学习算法进行改进，减少贝叶斯网络构建时的计算量。另一种是通过减少贝叶斯网络的构建次数，减少贝叶斯优化算法的计算量[3]。本文采用后一种方法，也就是通过提高种群的平均适应度减少贝叶斯网络的构建次数。因为免疫算法可以指导变异的方向，通过免疫算法能令贝叶斯网络产生的解进行有导向的变异，提高个体的适应度值，从而减少贝叶斯网络的构建次数，减少计算量。基于免疫机制的改进贝叶斯优化算法具体步骤如下：
步骤1：依据问题的具体要求对种群进行二进制编码，编码后随机产生种群规模为n的初始种群P（T），其中迭代次数T=0；
步骤2：按要求确定适应度函数f（x），计算种群P（T）中每个个体的适应度值，并选择适应度值较大的个体构成新的群体S（T）； 步骤3：对样本集S（T）进行分析，建立无向图，确定节点顺序，通过K2算法得出贝叶斯网络的结构；
步骤4：利用最大似然估计算法算出各节点的条件概率，即通过式（2-1）计算出贝叶斯网络的参数；
步骤5：按照贝叶斯网络的参数（即各节点的条件概率分布）对贝叶斯网络进行抽样以产生新的个体集M（T）；
步骤6：用M（T）和P（T）组成新种群Y（T），计算Y（T）中每个个体的适应度值，将适应度值最高的个体信息制成疫苗，通过疫苗接种概率对种群Y（T）进行疫苗接种操作，采用免疫选择对接种疫苗后的种群进行更新，并从更新后的种群中选择适应度值较大的n个个体构成新的种群P（T+1），且令T=T+1；
步骤7：确定是否满足终止条件，若满足则输出结果；不满足则重复步骤2。
3.算法仿真及性能分析
为了验证本文提出的基于免疫机制的改进贝叶斯优化算法与传统贝叶斯优化算法计算量小的优点，实验选用贝叶斯优化算法的常用测试函数进行。
（1）三阶陷阱函数[5]：f（u）=0.9，u=00，u=1，21，u=3（3-1）
（2）五阶陷阱函数[6]：f（u）=4-u，u<55，u=5（3-2）
以上函数中u代表二进制串中1的个数。
算法仿真在MATLAB环境下进行，相关实验参数设置如下：对于函数规模为15的，种群规模取60；对于函数规模为30的，种群规模取1000，其中疫苗接种概率取0.08，变异位数为2。设置完成将两种算法分别运行30次，验证比较两种算法的寻优能力和运算时间。实验测试数据如表3.1、表3.2所示。
（1）在较小的函数规模下，两种算法运算时间相差不大，但本文提出的算法寻优能力得到提高，运行30次，每次都能达到最优值；
（2）在较大的函数规模下，本文算法不但寻优能力大大提高，保证每次都能寻到最优解，而且寻到最优解所需的计算量也大大减少，运算时间也大大缩短。
4.结论
本文主要研究贝叶斯优化算法，较详细分析了贝叶斯优化算法的原理和存在的不足，并针对贝叶斯优化算法计算量大的问题，在深入理论分析的基础上提出一种改进算法，该算法在寻优过程中利用免疫机制自动找出局部最优解，并将其作为疫苗注射给子代的个体，这样可以指导个体的变异方向，提高个体的适应度值。利用免疫算法对概率模型产生的解进行进一步优化，目的在于提高算法的收敛速度，减少算法的计算量，提高寻优性能。
参考文献：
[1]PelikanM.Bayesian Optimization Algorithm：from Single Level to Hierarchy，USA，Ann Arbor，MI48106-1346，University of Illinois at Urbana-Champaign，2002.
[2]武燕.分布估计算法研究及在动态优化问题中的应用[D].陕西：西安电子科技大学，2009.
[3]彭伟.贝叶斯优化算法的研究及其在图像分割中的应用[D].黑龙江：哈尔滨工程大学，2010.
[4]钟小平等.改进的贝叶斯优化算法及应用[J].机械科学与技术，2006，25（4）：497-500.
[5]Etxeberria R，Larranaga P.Global optimization using Bayesian networks，The 2nd Symposium on Artificial Intelligence， Habana，Cuba，1999：332-339.
[6]Pelikan M，Sastry K.Fitness inheritance in the Bayesian Optimization Algorithm，Urbana Illinois：IlliGAL Report No.2004009， 2004.
关键词： 免疫机制 贝叶斯网络 种群 寻优
分布估计算法在求解问题时具有比遗传算法更好的性能，在解决实际应用中的复杂优化问题具有很大潜力。因此最近几年来，越来越多的学者对分布估计算法的研究产生了兴趣，并逐渐成为当前进化计算领域前沿的研究内容。而贝叶斯优化算法（Bayesian Optimization Algorithm，简称BOA算法）作为分布估计算法的典型代表，在求解复杂问题时有其独特优势，特别是针对NP问题，它表现出良好的性能。但在构建贝叶斯网络模型时需要较大的计算量，使贝叶斯优化算法在求解复杂优化问题时需要较长的运算时间，从而限制了算法的应用。
针对这一问题，本文在传统贝叶斯优化算法中引入了免疫规划算法的疫苗接种机制，利用问题的特征信息制作疫苗，并以一定的概率干预贝叶斯网络的全局搜索进程，从而克服以往优化算法中变异操作的不确定性和盲目性，提高算法的快速性和收敛性，降低贝叶斯优化算法的计算量。
1.贝叶斯优化算法的基本原理
1.1贝叶斯优化算法的基本流程
贝叶斯优化算法是基于种群进化的一种算法，通常初始种群由满足均匀分布的可行解组成。在产生初始群体之后，重复以下步骤直到满足终止条件。首先，利用一种适当的选择方法从当前群体中选出一组比较优秀的解；然后，利用从优选的解集合中提取信息建立优选解集的一个贝叶斯网络模型；接着，通过对贝叶斯网络进行采样学习生成一组新的候选解；最后把新产生的候选解加入到当前群体，取代其中一些低适应度的解。贝叶斯优化算法原理可描述如下[1]：
步骤1：t←0，随机产生初始群体Pop（t）；
步骤2：利用某种选择机制从Pop（t）中选择部分优秀解构成S（t）；
步骤3：利用贝叶斯网络概率模型建立S（t）的概率分布；
步骤4：依据概率分布抽样产生新的解集O（t）；
步骤5：用O（t）替换Pop（t）的部分个体形成下一代群体Pop（t+1），t←t+1；
步骤6：若不满足终止条件，继续执行步骤2。
贝叶斯优化算法的每一个步骤都有多种不同的方法可以选择。比如：初始群体可以根据问题的先验信息来产生；群体选择方法可以用任一种可行的选择方法（如轮盘赌法、锦标赛选择法和截断选择法等）；贝叶斯网络结构的学习算法也可选择不同的算法（如爬山法和k2法等）；贝叶斯网络参数的学习算法也有多种（如最大似然估计算法和贝叶斯估计算法等）。
1.2贝叶斯网络的学习和抽样
贝叶斯优化算法利用贝叶斯网络表示概率模型，通过贝叶斯网络的学习与抽样产生新个体，即贝叶斯优化算法的核心和关键是贝叶斯网络。贝叶斯网络是一个有向无环图，它既可以对数据进行描述，又可以通过采样产生与所给数据性质相同或相似的数据，因此常用于对离散或连续变量的多项式数据进行建模。
通常情况下，一个贝叶斯网络由网络结构和网络参数两个部分组成。贝叶斯网络结构中的节点表示各个变量（在此对应于个体中的基因），节点之间的有向边表示变量之间的条件依赖关系；贝叶斯网络参数是各变量条件概率分布表的集合。
一个典型的五个节点贝叶斯网络（包括网络拓扑和参数）如图1.1所示。该网络的联合概率可以表示为：
P（B，E，A，C，R）=P（B）P（E）P（A|B，E）P（R|E）P（C|A）（1-1）
贝叶斯网络的学习主要包括网络结构和条件概率参数的学习。在贝叶斯优化算法中，由于优选解群体中每一个变量的取值是确定的，因此当给定网络结构时，参数的学习是比较简单的。贝叶斯网络结构的学习是寻找对先验知识和数据拟合最好的网络结构，虽用全局搜索算法可得到较好的解，但计算量太大。为了能够快速学习贝叶斯网络结构（即使是近似解），常采用基于打分测度的贪婪算法[2]。
学习贝叶斯网络的结构和参数后，新的候选解将根据所学习的网络所描述的分布产生。贝叶斯网络的抽样过程可描述如下[2]：
步骤1：计算所有变量之间的祖孙关系；
步骤2：利用贝叶斯网络的条件概率按祖孙关系顺序产生所有变量的基因值；
步骤3：若需再生成多个个体，则继续执行步骤2。
2.引入免疫机制的改进贝叶斯优化算法原理
根据上述分析得知贝叶斯优化算法的计算量主要集中在贝叶斯网络的构建上，目前降低贝叶斯优化算法的计算量主要有两种方式，一种是通过对贝叶斯网络本身的改进，即通过对贝叶斯网络的结构学习算法进行改进，减少贝叶斯网络构建时的计算量。另一种是通过减少贝叶斯网络的构建次数，减少贝叶斯优化算法的计算量[3]。本文采用后一种方法，也就是通过提高种群的平均适应度减少贝叶斯网络的构建次数。因为免疫算法可以指导变异的方向，通过免疫算法能令贝叶斯网络产生的解进行有导向的变异，提高个体的适应度值，从而减少贝叶斯网络的构建次数，减少计算量。基于免疫机制的改进贝叶斯优化算法具体步骤如下：
步骤1：依据问题的具体要求对种群进行二进制编码，编码后随机产生种群规模为n的初始种群P（T），其中迭代次数T=0；
步骤2：按要求确定适应度函数f（x），计算种群P（T）中每个个体的适应度值，并选择适应度值较大的个体构成新的群体S（T）； 步骤3：对样本集S（T）进行分析，建立无向图，确定节点顺序，通过K2算法得出贝叶斯网络的结构；
步骤4：利用最大似然估计算法算出各节点的条件概率，即通过式（2-1）计算出贝叶斯网络的参数；
步骤5：按照贝叶斯网络的参数（即各节点的条件概率分布）对贝叶斯网络进行抽样以产生新的个体集M（T）；
步骤6：用M（T）和P（T）组成新种群Y（T），计算Y（T）中每个个体的适应度值，将适应度值最高的个体信息制成疫苗，通过疫苗接种概率对种群Y（T）进行疫苗接种操作，采用免疫选择对接种疫苗后的种群进行更新，并从更新后的种群中选择适应度值较大的n个个体构成新的种群P（T+1），且令T=T+1；
步骤7：确定是否满足终止条件，若满足则输出结果；不满足则重复步骤2。
3.算法仿真及性能分析
为了验证本文提出的基于免疫机制的改进贝叶斯优化算法与传统贝叶斯优化算法计算量小的优点，实验选用贝叶斯优化算法的常用测试函数进行。
（1）三阶陷阱函数[5]：f（u）=0.9，u=00，u=1，21，u=3（3-1）
（2）五阶陷阱函数[6]：f（u）=4-u，u<55，u=5（3-2）
以上函数中u代表二进制串中1的个数。
算法仿真在MATLAB环境下进行，相关实验参数设置如下：对于函数规模为15的，种群规模取60；对于函数规模为30的，种群规模取1000，其中疫苗接种概率取0.08，变异位数为2。设置完成将两种算法分别运行30次，验证比较两种算法的寻优能力和运算时间。实验测试数据如表3.1、表3.2所示。
（1）在较小的函数规模下，两种算法运算时间相差不大，但本文提出的算法寻优能力得到提高，运行30次，每次都能达到最优值；
（2）在较大的函数规模下，本文算法不但寻优能力大大提高，保证每次都能寻到最优解，而且寻到最优解所需的计算量也大大减少，运算时间也大大缩短。
4.结论
本文主要研究贝叶斯优化算法，较详细分析了贝叶斯优化算法的原理和存在的不足，并针对贝叶斯优化算法计算量大的问题，在深入理论分析的基础上提出一种改进算法，该算法在寻优过程中利用免疫机制自动找出局部最优解，并将其作为疫苗注射给子代的个体，这样可以指导个体的变异方向，提高个体的适应度值。利用免疫算法对概率模型产生的解进行进一步优化，目的在于提高算法的收敛速度，减少算法的计算量，提高寻优性能。
参考文献：
[1]PelikanM.Bayesian Optimization Algorithm：from Single Level to Hierarchy，USA，Ann Arbor，MI48106-1346，University of Illinois at Urbana-Champaign，2002.
[2]武燕.分布估计算法研究及在动态优化问题中的应用[D].陕西：西安电子科技大学，2009.
[3]彭伟.贝叶斯优化算法的研究及其在图像分割中的应用[D].黑龙江：哈尔滨工程大学，2010.
[4]钟小平等.改进的贝叶斯优化算法及应用[J].机械科学与技术，2006，25（4）：497-500.
[5]Etxeberria R，Larranaga P.Global optimization using Bayesian networks，The 2nd Symposium on Artificial Intelligence， Habana，Cuba，1999：332-339.
[6]Pelikan M，Sastry K.Fitness inheritance in the Bayesian Optimization Algorithm，Urbana Illinois：IlliGAL Report No.2004009， 2004.