·1346· 工程科学学报.第41卷，第10期 1 最小值 由于地标算子是对目标的精细搜索，在初始扰 fitness(X;(t-1))+s (18) 动时的步长可以稍大一些，但随着迭代的进行扰动 fitness(X (t-1)), 最大值 步长应逐渐减小.而logsig(·)函数恰好具有从1到 假设地标算子的最大迭代次数是NC2,当t> 0的非线性下降特性.所以，本文引入logsig(·)函 NC,时，停止地标算子.记录每次迭代的最优位置， 数表示扰动步长，其位置更新如式(22)所示.扰动 并用X表示： 时机为中心位置X在最近的K,次迭代内，如果每一 X。=max(X.(1),X.(2),…,X(t)) 维变化大小的绝对值小于阈值2，那么，对中心位置 3.2鸽群优化算法的改进模型 X执行高斯扰动操作 基本鸽群优化算法的每一次迭代均在寻找全局 最优，虽然具有收敛速度快、搜索效率高的优势，但 该思想在求解多最值问题时极易陷入局部最优 X:(t)=X:(t-1)+and(X(t-1)-X,(t-1) 为了最大限度地避免算法模型陷入局部最优， (22) 本文将柯西因子、高斯因子和模拟退火[1)(simula- 另外，基本鸽群优化算法在搜索过程中，始终 ted annealing,SA)机制引入基本鸽群优化算法模型 寻找全局最优解，极易陷入局部最优.因此，应以 中，从而提高算法性能.在进化计算理论中，高斯 一定概率保留次优个体.20世纪80年代提出的 扰动和柯西扰动是两种流行的扰动技术.柯西扰 模拟退火算法可以解决这一问题.假定，次优个体 动在跳出局部最优方面具有优势，而高斯扰动在 以概率P保留，添加高斯扰动后的个体X.与扰动 局部收敛方面表现较好4).因此，可将柯西扰动 前的个体X之间适应度值的差为△f,概率P,定 引入基本鸽群优化算法的地图和指南针算子，高 义为： 斯扰动引入地标算子，这样既可以避免过早收敛 P.exp (Af/T) (23) 陷入局部最优问题，又可以确保地标算子找到全 式中，T是退火温度，随着迭代的进行该值逐渐下 局最优解 降.而且，如果初始退火温度较高，退火率较低，改 便于扰动机制的描述，在搜索目标函数最大 进模型将更有助于跳出局部最优 值时，将每一维位置x:看成1，即x:=x:,则扰动后 将上述思想融入基本鸽群优化算法，得到扰动 的位置x=x:=x:+△r·X;△r是扰动步长，X是随 模拟退火鸽群优化(MSAPIO)算法模型.算法实现 机变量.若采用高斯扰动，则X是满足高斯分布的 过程描述如下. 一个随机变量X=N(u,σ2)，其概率密度函数如式 第一步：建立搜索图.根据式(5)和式(14)构 (19)所示： 建目标信息图，根据式(1)构建环境信息图： 第二步：初始化参数.初始化扰动模拟退火鸽 人(x)=】e器x(-0,+）(19) V2To 群优化算法参数.如，鸽子总数N:两个算子的最大 若采用柯西扰动，则X是满足柯西分布的随机 迭代次数NC,、NC,(具体如表1所示)，以及鸽群中 变量X=C,其概率密度函数如式(20)所示： 每只鸽子的初始位置和初始速度等； 第三步：估计鸽子的适应度值.利用式(15)的 适应度函数评价每只鸽子的位置： 因此，在地图和指南针算子中引入柯西扰动的 第四步：地图和指南针算子更新.利用式(16) 新一代鸽子的位置、速度更新如式(21)所示).扰 基本鸽群优化算法的地图和指南针算子更新位置和 动时机为全局最优的适应度函数值在最近K,次迭 速度，每次迭代，若有鸽子的适应度值优于X,则 代内，如果变化大小的绝对值小于阈值e,:那么，对 利用该鸽子的位置替换X;若满足柯西扰动条 全局最优位置执行柯西扰动操作 件，利用式(21)跳出局部最优，继续执行本步操作， 直至迭代次数达到NC,; V,(t)=(t-l)eRx+{X+ 第五步：地标算子更新.利用式(17)基本鸽群 axtn [=(rand-)]-x(t-1)) 优化算法的地标算子更新中心位置和每只鸽子位 置，每次迭代，若新一代X(t)优于上一代X(t- X:(t)=X:(t-1)+V(t) 1),则利用新一代X.()替换上一代X(t-1):若满 21) 足高斯扰动条件，利用式(22)局部调整，若高斯扰工程科学学报,第 41 卷,第 10 期 1 fitness(Xi(t - 1)) + 着 , 最小值 fitness(Xi(t - 1)), ì î í ïï ïï 最大值 (18) 假设地标算子的最大迭代次数是 NC2 ,当 t > NC2时,停止地标算子. 记录每次迭代的最优位置, 并用 Xp表示: Xp = max (Xg (1),Xg (2),…,Xg (t)) 3郾 2 鸽群优化算法的改进模型 基本鸽群优化算法的每一次迭代均在寻找全局 最优,虽然具有收敛速度快、搜索效率高的优势,但 该思想在求解多最值问题时极易陷入局部最优. 为了最大限度地避免算法模型陷入局部最优, 本文将柯西因子、高斯因子和模拟退火[13] ( simula鄄 ted annealing,SA)机制引入基本鸽群优化算法模型 中,从而提高算法性能. 在进化计算理论中,高斯 扰动和柯西扰动是两种流行的扰动技术. 柯西扰 动在跳出局部最优方面具有优势,而高斯扰动在 局部收敛方面表现较好[14] . 因此,可将柯西扰动 引入基本鸽群优化算法的地图和指南针算子,高 斯扰动引入地标算子,这样既可以避免过早收敛 陷入局部最优问题,又可以确保地标算子找到全 局最优解. 便于扰动机制的描述,在搜索目标函数最大 值时,将每一维位置 xi 看成 1,即 xi = xi,则扰动后 的位置 x忆i = x忆i = xi + 驻r·X;驻r 是扰动步长,X 是随 机变量. 若采用高斯扰动,则 X 是满足高斯分布的 一个随机变量 X = N(滋,滓 2 ) ,其概率密度函数如式 (19)所示: fN(x) = 1 2仔滓 e - (x - 滋)2 2滓2 ,x沂( - 肄 , + 肄 ) (19) 若采用柯西扰动,则 X 是满足柯西分布的随机 变量 X = C,其概率密度函数如式(20)所示: f c(x) = 1 ( 仔 a a 2 + x 2 ) ,x沂( - 肄 , + 肄 ) (20) 因此,在地图和指南针算子中引入柯西扰动的 新一代鸽子的位置、速度更新如式(21)所示[15] . 扰 动时机为全局最优的适应度函数值在最近 K1次迭 代内,如果变化大小的绝对值小于阈值 e1 ;那么,对 全局最优位置执行柯西扰动操作. Vi(t) = Vi(t - 1)e - R 伊 t + { Xgbest + a 伊 tan [ 仔 (rand - ) ] 1 2 - Xi(t - 1)) } Xi(t) = Xi(t - 1) + Vi(t ì î í ï ïï ï ïï ) (21) 由于地标算子是对目标的精细搜索,在初始扰 动时的步长可以稍大一些,但随着迭代的进行扰动 步长应逐渐减小. 而 logsig(·)函数恰好具有从 1 到 0 的非线性下降特性. 所以,本文引入 logsig(·) 函 数表示扰动步长,其位置更新如式(22)所示. 扰动 时机为中心位置 Xc在最近的 K2次迭代内,如果每一 维变化大小的绝对值小于阈值 e2 ,那么,对中心位置 Xc执行高斯扰动操作. X忆c(t -1) = Xc(t -1) + log sig ( NC2 / 2 - t ) k N(滋,滓) Xi(t) = Xi(t -1) + rand·(X忆c(t -1) - Xi(t -1 { )) (22) 另外,基本鸽群优化算法在搜索过程中,始终 寻找全局最优解,极易陷入局部最优. 因此,应以 一定概率保留次优个体. 20 世纪 80 年代提出的 模拟退火算法可以解决这一问题. 假定,次优个体 以概率 Pr保留,添加高斯扰动后的个体 Xig与扰动 前的个体 X 之间适应度值的差为 驻f,概率 Pr 定 义为: Pr = exp (驻f / T) (23) 式中,T 是退火温度,随着迭代的进行该值逐渐下 降. 而且,如果初始退火温度较高,退火率较低,改 进模型将更有助于跳出局部最优. 将上述思想融入基本鸽群优化算法,得到扰动 模拟退火鸽群优化(MSAPIO)算法模型. 算法实现 过程描述如下. 第一步:建立搜索图. 根据式(5) 和式(14) 构 建目标信息图,根据式(1)构建环境信息图; 第二步: 初始化参数. 初始化扰动模拟退火鸽 群优化算法参数. 如,鸽子总数 N;两个算子的最大 迭代次数 NC1 、NC2 (具体如表 1 所示),以及鸽群中 每只鸽子的初始位置和初始速度等; 第三步:估计鸽子的适应度值. 利用式(15)的 适应度函数评价每只鸽子的位置; 第四步:地图和指南针算子更新. 利用式(16) 基本鸽群优化算法的地图和指南针算子更新位置和 速度,每次迭代,若有鸽子的适应度值优于 Xgbest,则 利用该鸽子的位置替换 Xgbest;若满足柯西扰动条 件,利用式(21)跳出局部最优,继续执行本步操作, 直至迭代次数达到 NC1 ; 第五步:地标算子更新. 利用式(17)基本鸽群 优化算法的地标算子更新中心位置和每只鸽子位 置,每次迭代,若新一代 Xc ( t) 优于上一代 Xc ( t - 1),则利用新一代 Xc(t)替换上一代 Xc(t - 1);若满 足高斯扰动条件,利用式(22) 局部调整,若高斯扰 ·1346·