22信息利用率 ∑=1I(z;Y1-1|1,2 IURA(g ∑=1H(Y|,Y2-1) 其中, I(z;Y-1|,21-1)=H(Z1|,2-1)-H(Z1|A,Z1-1,Y2-1) i=1 从流程图可以看到最后一项为委。 北示大旁计算智能实验蜜
2.2 信息利用率 𝐼𝑈𝑅𝐴 𝑔 = σ𝑖=1 𝑔 𝐼 𝑍𝑖 ; 𝑌ത 𝑖−1|𝑋ത 𝑖 , 𝑍ҧ 𝑖−1 σ𝑖=1 𝑔 𝐻 𝑌𝑖 |𝑋ത 𝑖 , 𝑌ത 𝑖−1 其中， 𝐼 𝑍𝑖 ; 𝑌ത 𝑖−1|𝑋ത 𝑖 , 𝑍ҧ 𝑖−1 = 𝐻 𝑍𝑖 |𝑋ത 𝑖 , 𝑍ҧ 𝑖−1 − 𝐻 𝑍𝑖 |𝑋ത 𝑖 , 𝑍ҧ 𝑖−1, 𝑌ത 𝑖−1 𝑋ത 𝑡 = ራ𝑖=1 𝑡 𝑋𝑖 从流程图可以看到最后一项为零。 11
22信息利用率 设A是一个优化算法,其信息利用率 nformation Utilization ratio)定义如 下 ∑(1H(Z|X=,Z=1 UR。(g) ∑=1H(H|Xx,Y1-1) 其中X=U/a1Xx等等。 北示大旁计算智能实验蜜
2.2 信息利用率 • 设A是一个优化算法，其信息利用率（Information Utilization Ratio）定义如 下： • 其中 等等。 12
2.3信息利用率的理论分析 下面的定理保证信息利用率是良定义的。 定理1.若0<∑1H(HX,Y1-1)<∞,那么0≤UR/(g)≤1. 北示大旁计算智能实验蜜
2.3 信息利用率的理论分析 • 下面的定理保证信息利用率是良定义的。 13
2.3信息利用率的理论分析 基于比较的算法是指每一代采样分布只取决于之前豕样点的适应度值的排序, 而不是值本身。 基于比较的算法对于值域上的保序变换具有不变性。 许多进化算法都是基于比较的。如DE,PSO, CMA-ES等等。 下面的定理说明基于比较的算法的信息利用率有限。 定理2.若最大评估次数为m,y=f(x)服从独立同分布,且算法a是基于比较的优化算 法,那么 log m UR。≤ H(f(x) 北示大旁计算智能实验蜜
2.3 信息利用率的理论分析 • 基于比较的算法是指每一代采样分布只取决于之前采样点的适应度值的排序， 而不是值本身。 • 基于比较的算法对于值域上的保序变换具有不变性。 • 许多进化算法都是基于比较的。如DE, PSO, CMA-ES等等。 • 下面的定理说明基于比较的算法的信息利用率有限。 14
2.3信息利用率的理论分析 如果用最大初次到达肘间(即多次运行中找到最优点肘间最晚的一次)作为性 能指标,信息利用率与性能有如下关条 定理3.设w是一优化算法,Fyx,M|<∞,存在∫∈对任意x∈X满足f(x) mixed(f(x)且存在g<∞对任意∫∈和任意一次运行w满足x*∈X,那么P(a)≥ H(x' g. UR(gm) 也就是说信息利用率越高,找到最优点需要的最大肘间的下界越低,即算法性 能的上界越高。 北示大旁计算智能实验蜜
2.3 信息利用率的理论分析 • 如果用最大初次到达时间（即多次运行中找到最优点时间最晚的一次）作为性 能指标，信息利用率与性能有如下关系： • 也就是说信息利用率越高，找到最优点需要的最大时间的下界越低，即算法性 能的上界越高。 15