第5 章烟花算法燃放烟花是中国传统节日尤其是春节的一个重要活动。在这一天,成千上万的烟花在夜空中爆炸并产生美丽的图案。通常,不同价格和规格的烟花在黑夜中爆炸产生不同的效果。一般价格高昂的烟花产生的火花数量比较多,爆炸产生的火花分布的范围也较集中;价格低廉的烟花产生的火花数量比较少,爆炸产生的火花分布的范围也较分散。烟花算法(FWA)针对燃放的烟花在空中爆炸这种行为建立数学模型,通过引入随机因素和选择策略形成一种并行的搜索方法。它结合了群体智能算法中的交互机制和进化算法中的选择机制,是一种独树一帜的智能优化算法。 5.1 基本烟花算法基本FWA 由四大部分组成,包括爆炸算子、变异算子、映射规则和选择策略。爆炸算子的作用是在烟花的周围产生一批新的火花。产生火花的个数以及爆炸的幅度都由爆炸算子确定。另外,通过变异算子产生的火花服从高斯分布。在两种算子的作用下,如果产生的火花不在可行域范围内,需要运用映射规则将新产生的火花映射至可行域范围内,再利用选择策略选择新的火花作为下一代烟花。 FWA 开始迭代,依次利用爆炸算子、变异算子、映射规则和选择策略,直到达到终止条件,即满足问题的精度要求或者达到最大函数评估次数。FWA 的实现包括如下几个步骤: (1)在特定的解空间随机产生一些烟花,每个烟花代表解空间的一个解。 (2)根据适应度函数计算每个烟花的适应度值,并根据适应度值产生火花。火花的个数是基于免疫学中的免疫浓度的思想计算的,即适应度值越高的烟花产生火花的数目越多。 (3)根据现实中的烟花属性并结合搜索问题的实际情况,在烟花的辐射空间内产生火花(某个烟花的爆炸幅度的大小由该烟花在函数上的适应度值决定,适应度值越大,爆炸幅度越小,反之亦然)。每个火花代表解空间的一个解。为了保证种群的多样性,需要对烟花进行适当变异,如高斯变异。 (4)计算种群的最优解,判定是否满足要求,如果满足则停止搜索,没有满足则继续迭代。迭代的初始值为此次循环得到的最好的解和选择的其他的解。下面逐个介绍基本FWA 的各个算子。 5.1.1 爆炸算子 FWA的初始化是随机生成N 个烟花的过程。接着,需要对生成的这N 个烟花应用爆炸算子,以便产生新的火花。爆炸算子是FWA 的关键核心并起关键性的作用,包含爆炸强 1 06 群体智能导论度、爆炸幅度和位移操作。 1.爆炸强度爆炸强度是FWA 中爆炸算子的核心,它模拟的是现实生活中烟花爆炸的方式。任何一个烟花爆炸时,这个烟花周围都会产生一片火花。FWA 首先需要确定每个烟花爆炸产生火花的个数,以及在什么幅度内产生这些火花。通过观察一些典型优化函数的曲线图,可以直观地看出,最优点附近的优质点也相应较多较密。因此,通过爆炸强度让适应度函数值好的烟花,产生的火花个数较多。这样可以避免寻优时火花总是在最优值附近摆动,而无法精准地找到最优值。对于适应度函数值较差的烟花,由于产生适应度函数值好的火花的概率较小,为避免做过多的不必要的计算,通过爆炸强度使其产生火花数较少。这种适应度函数值差的烟花的作用是对其余空间做适度的探索,避免早熟。可根据各个烟花适应度值的大小,确定每一个烟花产生火花的数量,让适应度值好的烟花产生更多的火花,适应度值差的烟花产生更少的火花。在FWA 中,产生火花个数的公式如下: Si =m · ymax -f(xi)+ε ΣN i=1 (ymax -f(xi))+ε 式中,Si表示第i 个烟花产生的火花个数,参数i 的取值范围从1到N 。m 是一个常数,用来限制产生的火花总数。ymax是当前种群中适应度值最差的个体的适应度值。f(xi)表示个体xi的适应度值。最后一个参数ε 取一个极小的常数,以避免出现分母为零的情况。每个烟花爆炸火花的数量限制公式如下: S^i = round(a·m ) , Si bm round(a·m ) , 其他 ì . í .. .. 式中,a 和b 是常数,a0) 式中,v[A]是在集合A 上的勒贝格测度(Lebesguemeasure)。上述公式意味着在搜索空间的子集中,存在多个点,使得函数值趋近于φ,使得在勒贝格可度量的非零集合中,φ 为函数值的下确界。下面建立FWA 的随机过程。定义5-1 {ξ(t)}t∞=0 为FWA 的随机过程,其中ξ(t)={F (t),T (t)},而F (t)= {F1(t),F2(t),…,Fn (t)}表示在t 时刻N 个烟花在解空间中的位置。T (t)={A (t), S(t)},其中A(t)={A1(t),A2(t),…,An (t)}表示N 个烟花爆炸的幅度,而S (t)= {s1(t),s2(t),…,sn(t)}表示N 个烟花爆炸的数目。接下来定义最优区域。定义5-2 Rε={x∈S|f(x)-f(x* )<ε,ε>0}是函数f(x)的最优区域,x* 表示函数f(x)在解空间的最优解。根据定义5-2,如果算法找到一个位于最优区域的点,视为算法找到了函数的接近全局最优的一个可接受的解。根据定义5-1,最优解空间的勒贝格测度必须不为零,这意味着 v(Rε)>0。定义5-3 定义FWA 的最优状态为ξ* (t)={F* (t),T (t)},同时,存在Fi(t)∈Rε 和 Fi(t)∈F* (t),i∈1,2,…,n。定义5-3说明在FWA 的最优状态ξ* (t)下,最好的烟花在最优区域Rε中。所以这里存在Fi(t)∈R 和f (Fi(t)) -f(x* ) <ε,x* ∈Rε。引理5-1 FWA 的随机过程{ξ(t)}t∞=0是一个马尔可夫(Markov)过程。证明略。定义5-4 (最优状态空间)用Y 表示FWA 的状态ξ(t)的状态空间,Y* .Y。只要存在一个解s* ∈F* 使得s* ∈Rε在任意状态ξ* (t)={F* ,T}∈Y 下成立,那么Y* 就是最优状态空间。定义5-4指出,f s( * ) -f(x* ) <ε 对任意x* ∈F* 都成立。如果FWA 可以达到最优状态,则必定有一个火花达到了最优区域Rε,且FWA 得到了最优解。此后,最优解一定在最优区域内。定义5-5 给定一个马尔可夫随机过程{ξ(t)}t∞=0和优化状态空间Y* .Y,{ξ(t)}t∞=0如果满足P {ξ(t+1).Y*|ξ(t)∈Y* } =0,则被命名为吸收马尔可夫过程。引理5-2 FWA 的随机过程{ξ(t)}t∞=0是一个吸收马尔可夫过程。证明略。 5.2.2 全局收敛性定义5-6 (收敛性)给定一个吸收马尔可夫过程{ξ(t)}t∞=0={F(t),T (t)}和一个优化状态空间Y* .Y,λ(t)=P{ξ(t)∈Y* }表示在t 时刻,随机状态达到最优状态的概率。如果 1 12 群体智能导论 lim t→∞ λ(t)=1,则{ξ(t)}t∞=0收敛。根据上面的定义,马尔可夫随机过程的收敛取决于P{ξ(t)∈Y* }的概率。如果在t 时刻马尔可夫随机过程的收敛概率为1,可以认为马尔可夫过程{ξ(t)}t∞=0收敛。定理5-1 给定FWA 的一个吸收马尔可夫过程{ξ(t)}t∞=0和一个优化状态空间Y* .Y, 如果对于任意的t,P{ξ(t)∈Y*|ξ(t-1).Y* }≥d≥0,且P {ξ(t)∈Y*|ξ(t-1)∈Y* } =1 成立,则P {ξ(t)∈Y* } ≥1-(1-d)t。证明略。 FWA 包含高斯变异。为简化问题,假定该变异是一种随机变异。定理5-2 给定FWA 的一个吸收马尔可夫过程{ξ(t)}t∞=0和一个优化状态空间Y* .Y, 则lim t→∞ λ(t)=1意味着{ξ(t)}t∞=0能收敛到最优状态Y* 。证明略。以上的定义和定理证明了FWA 的马尔可夫过程将收敛到最优状态。 5.2.3 时间复杂度的基本理论定义5-7 (期望收敛时间)给定FWA 的一个吸收马尔可夫过程{ξ(t)}t∞=0和一个优化状态空间Y* .Y,如果γ 是一个随机非负值使得如果t≥γ,有P {ξ(t+1)∈Y* } =1;如果 0≤t≤γ,有P {ξ(t+1).Y* } <1。那么γ 就是FWA 的收敛时间。FWA 的期望收敛时间用Eγ 表示。期望收敛时间Eγ 描述的是FWA 以1的概率初次得到全局最优解的时间。期望值Eγ 越小,FWA 的收敛就越快,FWA 也就更加有效。但是,也可以用首次最优解期望时间 (ExpectedFirstHittingTime,EFHT)作为收敛时间的一个标志。定义5-8 (首次最优解期望时间)给定FWA 的一个吸收马尔可夫过程{ξ(t)}t∞=0和一个优化状态空间Y* .Y;μ 是一个随机值,使得如果t=μ,则ξ(t).Y* ;如果0≤t≤μ,则 ξ(t).Y* 。期望值Eμ 称为首次最优解期望时间。下面的定理给出了计算Eγ 的方法。定理5-3 给定FWA 的一个吸收马尔可夫过程{ξ(t)}t∞=0和一个优化状态空间Y* .Y。如果λ(t)=P{ξ(t)∈Y* }并且lim t→∞ λ(t)=1,则期望收敛时间Eγ =Σ∞ t=0 (1-λ(t))。证明略。因为很难得到λ(t)的值,所以很难计算出期望收敛时间Eγ 。因此,只能给出估计的时间。定理5-4 给定两个随机非负变量u 和v,并用Du(·)和Dv (·)分别表示u 和v 的分布函数。如果Du(t)≥Dv(t)(.t=0,1,2,…),则u 和v 的期望值Eu 0)且lim t→∞ λ(t)=1, 则FWA 的期望收敛时间Eγ 满足下列不等式: b-1[1-λ(0)]≤Eγ ≤a-1[1-λ(0)] 证明略。上述推论和定理表明公式P{ξ(t)∈Y*|ξ(t-1).Y* }可以描述FWA 的烟花从非最优状态到最优状态的概率。Eγ 值的估计范围可以通过P{ξ(t)∈Y*|ξ(t-1).Y* }的值来计算。 5.2.4 时间复杂度分析 FWA 的时间复杂度需要计算期望收敛时间Eγ 。依据推论5-1,FWA 的时间复杂度主要和FWA 的烟花从非最优区域到最优区域Rε的概率相关,即P{ξ(t+1)∈Y*|ξ(t-1). Y* }。这里,将进一步分析此公式来得到FWA 的时间复杂度。FWA 包含爆炸算子、变异算子、映射规则和选择策略,但与FWA 的马尔可夫状态到达最优区域直接相关的是爆炸算子和变异算子。因此,有下面的定理。定理5-7 给定FWA 的一个吸收马尔可夫过程{ξ(t)}t∞=0和一个优化状态空间Y* .Y, 则有 v(Rε)×n v(S) ≤P{ξ(t+1)∈Y* |ξ(t).Y* }≤v(Rε) n v(S)+ Σn i=1 mi v(Ai) . è . . . ÷ 式中,v(Rε)是最优区域Rε 的勒贝格测度值,v(S)是问题搜索区域S 的勒贝格测度值, v(Ai)是第i 个烟花的爆炸幅度Ai的勒贝格测度值。上面的定理给出了非常粗糙的结果,因为实际的公式很难进行确定性的计算。FWA 很难准确计算出火花落在最优区域Rε的概率。为了准确地实现,需要做如下变换: P(exp)=Σn i=1 v(Si ∩Rε)×mi v(Si) 式中,v(Si∩Rε)和mi随着算法的运行在动态改变,所以它们非常重要。v(Si∩Rε)和烟花的位置Fi相关。FWA 的选择策略使得位置距离大的个体有更高的概率被选中,所以可以假定每次只有一个烟花处于最优区域Rε,进一步假设适应度值最高的烟花进入最优区域Rε 的概率最高。依据上述假设,v(Ai)>v(Abest)且mi >mbest,i∈(0,1,2,…)。其中Abest和 mbest分别是适应度值最高的烟花的爆炸区域和生成火花的数目。由此得到 v(Ai ∩Rε)×mi v(Ai)