·494· 智能系统学报 第9卷 2.3计算复杂度分析 k=1,2,…,N,}为FRABC算法的第t代种群，t=0, 设引领蜂群体规模N,和跟随蜂群体规模N相 1,…,max o 同，且N2=N=N/2,最大迭代代数为tm。根据第 定义2称种群集合B={X={x,k=1,2,… 3.2节中各步骤分析FRABC算法的计算复杂度（仅 N}:X∩M≠☑}为问题式(3)的满意种群集[8]。 考虑重复执行的次数)。 由第2.2节的算法流程可知，FRABC算法具有 2)的计算复杂度为：引领蜂执行邻域搜索生成 保留精英解的特点，故有以下定理。 新蜜源：0(N×n/2),评价新蜜源：O(N/2),更新蜜 定理1 FRABC算法的最优蜜源x(t+I) 源：0(N/2),更新计数器6t:O(N/2)。3)的计算复 不劣于x(t)b,t=0,1,…,tmo 杂度为：计算引领蜂被选择的概率：0(N/2),选择 定理2 FRABC算法的种群序列{XO,t=0,1, 被跟随的引领蜂：0(N/2),跟随蜂执行邻域搜索生 …,tmx}是齐次不可约非周期Markov链。 成新蜜源：O(N×n/2),评价新蜜源：0(N/2),更新 证明因蜂群对种群X)执行邻域搜索，生成 蜜源：0(N/2),更新计数器6t:0(N/2)。5)的计算 新一代种群X+)时，每一蜜源x)由引领蜂、跟随 复杂度为：0(N/2),因此步存在不确定性，可忽略 蜂及侦察蜂协同完成搜索[9)。借鉴车林仙20分析 其复杂度5)的计算复杂度为：确定每代的最优蜜 DE算法收敛性的方法，以下分别给出其一步转移 源：O(N/2),更新最优蜜源：O(1)。略去上述各步 概率（因篇幅所限，不再展开证明）。 中的低阶项，则FRABC算法的计算复杂度为 1)引领蜂执行邻域搜索的一步转移概率。 O(tm×W×n),为立方阶复杂度[7。 引领蜂k在X)中随机选择一异于x(t),的蜜 3算法收敛性分析 源x(t)m,生成中间蜜源y的概率为 PrT.(x(,X(O)=y= 设问题式(3)的解空间为S=几([0，x:]∩Z),可 N-∑8x(t):+ound(p(x(t)4-x(t)n)-） 行域为D={x∈S:G(x)=0},全局最优解集为M= (10) {x∈D:对y∈D,有f(x)>f(y)}。显然空间S内只 有有限个候选解。为方便表述，首先给出如下定义。 式中：T,为算子符号，以下类似；δ(·)为Diac函数到。 定义1称t时刻的蜜源集合Xo={x(t), 对x(t):与y执行交叉操作，生成x的概率为 PrT.(x(t),y)=x n 8-+p+8-m n 对x(t):与x执行贪婪选择，得到x'的概率为 PrTS=x'=1/S 式中：1S1表示S内的离散点数。 8(x-x'),x优于x(t) PrT2(x(t),x)=x= 于是，仅由引领蜂搜出新一代蜜源x(:+1): 8(x(t)g-x'),其他 时，其概率为 (12) PrTi(x(t),X)=x(t+1)= 综合式(10)~(12)，可得引领蜂k搜索到新蜜 PrT(x(t)k,Xo)=x(t+1)4}(14) 源x的一步转移概率 由引领蜂和跟随蜂共同搜出新一代蜜源x(t+1): 时，其概率为 T(xo),Xo)=x'=∑∑PrT,(x)kXo） Pr{T(x(t)4,X0)=x(t+1)}= y}×Pr{T.(x(t)y)=x}×PrT(x(t)4,x)=x'} PrT(x(t)X()=x'xPrT(x,X()= (13) x'2}x…×Pr{T(x'a,X0)=x(t+1)E}(15) 2)跟随蜂执行邻域搜索的一步转移概率。 式中：9≥1，指引领蜂k被跟随的次数。 当选中引领蜂k作为被跟随蜂时，也可用前述 由侦察蜂搜出新一代蜜源x(t+1)4时，其概率为 方法计算搜索x'的一步转移概率，其表达式与式 Pr{T,(x(t)4,Xo)=x(t+1)}= (13)类似，简记为Pr{T(x(t),X)=x}。 PrTsS=x(t+1) (16) 3)侦察蜂执行随机搜索的一步转移概率。 那么，由Xo生成X+)的一步转移概率为[1920] 因侦察蜂对解空间S执行随机搜索，故获得x' PrlTX(=x(D= 的一步转移概率为 ΠPr{T(x(t)4,Xo)=x(t+1)4}(17)圆援猿摇 计算复杂度分析 设引领蜂群体规模 晕蕴和跟随蜂群体规模 晕云相 同袁且 晕蕴 越晕云 越 晕 辕 圆袁最大迭代代数为 贼皂葬曾遥 根据第 猿援圆 节中各步骤分析 云砸粤月悦 算法的计算复杂度渊仅 考虑重复执行的次数冤 遥 圆冤的计算复杂度为院引领蜂执行邻域搜索生成 新蜜源院韵渊晕 灶 辕 圆冤袁评价新蜜源院韵渊晕 辕 圆冤袁更新蜜 源院韵渊晕 辕 圆冤袁更新计数器 啄贼噪院韵渊晕 辕 圆冤遥 猿冤的计算复 杂度为院计算引领蜂被选择的概率院韵渊晕 辕 圆冤袁选择 被跟随的引领蜂院韵渊晕 辕 圆冤袁跟随蜂执行邻域搜索生 成新蜜源院韵渊晕 灶 辕 圆冤袁评价新蜜源院韵渊晕 辕 圆冤袁更新 蜜源院韵渊晕 辕 圆冤袁更新计数器 啄贼噪院韵渊晕 辕 圆冤遥 缘冤的计算 复杂度为院韵渊晕 辕 圆冤袁因此步存在不确定性袁可忽略 其复杂度 缘冤 的计算复杂度为院确定每代的最优蜜 源院韵渊晕 辕 圆冤袁更新最优蜜源院韵渊员冤遥 略去上述各步 中的低阶项袁 则 云砸粤月悦 算法的计算复杂度为 韵渊贼皂葬曾晕 灶冤 袁为立方阶复杂度咱员苑暂 遥 猿摇 算法收敛性分析 设问题式渊猿冤的解空间为 杂 越仪 灶 蚤 越 员 渊咱园袁曾 原 蚤暂疑在冤袁可 行域为 阅越 喳曾 杂院 郧渊曾冤 越 园札袁全局最优解集为酝越 喳曾 阅院 对赠 阅袁有 枣渊曾冤 跃枣渊赠冤札遥 显然空间 杂 内只 有有限个候选解遥 为方便表述袁首先给出如下定义遥 定义 员摇 称 贼 时刻的蜜源集合 载渊贼冤 越 喳 曾渊贼冤噪 袁 噪 越 员袁圆袁噎袁晕蕴 札为 云砸粤月悦 算法的第 贼 代种群袁贼 越 园袁 员袁噎袁贼皂葬曾遥 定义 圆摇 称种群集合 月 越 喳载 越 喳 曾噪袁噪 越 员袁圆袁噎袁 晕蕴 札 院 载 疑 酝 札为问题式渊猿冤的满意种群集咱员愿暂 遥 由第 圆援圆 节的算法流程可知袁云砸粤月悦 算法具有 保留精英解的特点袁故有以下定理遥 定理 员摇 云砸粤月悦 算法的最优蜜源 曾渊贼 垣 员冤遭藻泽贼 不劣于 曾渊贼冤遭藻泽贼 袁贼 越 园袁员袁噎袁贼皂葬曾遥 定理 圆摇 云砸粤月悦 算法的种群序列喳载渊贼冤 袁贼 越 园袁员袁 噎袁贼皂葬曾札是齐次不可约非周期 酝葬则噪燥增 链遥 证明 因蜂群对种群 载渊贼冤 执行邻域搜索袁生成 新一代种群 载渊贼垣员冤时袁每一蜜源 曾渊贼垣员冤 由引领蜂尧跟随 蜂及侦察蜂协同完成搜索咱员怨暂 遥 借鉴车林仙咱圆园暂 分析 阅耘 算法收敛性的方法袁以下分别给出其一步转移 概率渊因篇幅所限袁不再展开证明冤 遥 员冤 引领蜂执行邻域搜索的一步转移概率遥 引领蜂 噪 在 载渊贼冤 中随机选择一异于 曾渊贼冤噪 的蜜 源 曾渊贼冤 皂 袁生成中间蜜源 赠 的概率为 孕则喳栽泽 员渊曾渊贼冤 噪 袁 载渊贼冤 冤 越 赠札 越 员 晕蕴 原 员移皂屹噪 啄 曾渊贼冤噪 垣 则燥怎灶凿 渍噪渊曾渊贼冤噪     原 曾渊贼冤 皂冤 原 赠 渊员园冤 式中院栽泽员为算子符号袁以下类似曰啄渊窑冤为阅蚤则葬糟 函数咱圆园暂 遥 对 曾渊贼冤噪 与 赠 执行交叉操作袁生成 曾 耀 的概率为 孕则喳栽糟渊曾渊贼冤噪袁 赠冤 越 曾 耀 札 越 仪 灶 蚤 越 员 员 原 责泽藻葬 原 员 原 责泽藻葬 灶      窑啄渊曾渊贼冤 噪袁蚤 原 曾 耀 蚤冤 垣 责泽藻葬 垣 员 原 责泽藻葬 灶      窑啄渊赠蚤 原 曾 耀 蚤冤         渊员员冤 摇 摇 对曾渊贼冤噪 与 曾 耀 执行贪婪选择袁得到 曾 的概率为 孕则喳栽泽 圆渊曾渊贼冤噪袁曾 耀 冤 越 曾 札 越 啄渊 曾 耀 原 曾忆冤 袁曾 耀 优于曾渊贼冤噪 啄渊曾渊贼冤噪  原 曾忆冤 袁其他 渊员圆冤 摇 摇 综合式渊员园冤 耀 渊 员圆冤 袁可得引领蜂 噪 搜索到新蜜 源 曾 的一步转移概率 孕则喳栽蕴渊曾渊贼冤噪袁 载渊贼冤 冤 越 曾 札 越 移赠沂杂 移曾 耀 沂杂 孕则喳栽泽员渊曾渊贼冤噪袁载渊贼冤 冤 越 赠札 伊 孕则喳栽糟 渊曾渊贼冤噪袁赠冤 越 曾 耀 札 伊 孕则喳栽泽圆渊曾渊贼冤噪袁曾 耀 冤 越 曾忆札 渊员猿冤 摇 摇 圆冤 跟随蜂执行邻域搜索的一步转移概率遥 当选中引领蜂 噪 作为被跟随蜂时袁也可用前述 方法计算搜索 曾 的一步转移概率袁其表达式与式 渊员猿冤类似袁简记为 孕则喳栽云渊 曾渊贼冤噪 袁 载渊贼冤 冤越 曾 札 遥 猿冤 侦察蜂执行随机搜索的一步转移概率遥 因侦察蜂对解空间 杂 执行随机搜索袁故获得 曾  的一步转移概率为 孕则喳栽杂 杂 越 曾 札 越 员 辕 杂 式中院 渣 杂 渣表示 杂 内的离散点数遥 于是袁仅由引领蜂搜出新一代蜜源 曾渊贼 垣 员冤噪 时袁其概率为 孕则喳栽员渊曾渊贼冤噪袁 载渊贼冤 冤 越 曾渊贼 垣 员冤噪札 越 孕则喳栽蕴渊曾渊贼冤噪袁 载渊贼冤 冤 越 曾渊贼 垣 员冤噪札 渊员源冤 由引领蜂和跟随蜂共同搜出新一代蜜源 曾渊贼 垣 员冤噪 时袁其概率为 孕则喳栽员渊曾渊贼冤噪袁载渊贼冤 冤 越 曾渊贼 垣 员冤噪札 越 孕则喳栽蕴渊曾渊贼冤噪袁载渊贼冤 冤 越 曾忆员 札 孕则喳栽蕴渊曾忆员 袁载渊贼冤 冤 越 曾忆圆 札 噎 孕则喳栽蕴渊曾忆择袁载渊贼冤 冤 越 曾渊贼 垣 员冤噪札 渊员缘冤 式中院择逸员袁指引领蜂 噪 被跟随的次数遥 由侦察蜂搜出新一代蜜源 曾渊贼 垣 员冤噪 时袁其概率为 孕则喳栽员渊曾渊贼冤噪袁载渊贼冤 冤 越 曾渊贼 垣 员冤噪札 越 孕则喳栽杂 杂 越 曾渊贼 垣 员冤噪札 渊员远冤 那么袁由 载渊贼冤 生成 载渊贼垣员冤的一步转移概率为咱员怨鄄圆园暂 孕则喳栽载渊贼冤 越 载渊贼 垣员冤 札 越 仪 晕蕴 噪 越 员 孕则喳栽员渊曾渊贼冤噪袁载渊贼冤 冤 越 曾渊贼 垣 员冤噪札 渊员苑冤 窑源怨源窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷