基于交叉熵的粒子群优化算法

张 娜,贺兴时,屈思凡

(西安工程大学 理学院,陕西 西安 710048)

0 引 言

粒子群优化算法(particle swarm optimization, PSO)是Eberhart和Kennedy在1995年基于对鸟群觅食行为的研究,提出的一种解决最优化问题的群体智能算法[1]。粒子群优化算法结构清晰,没有过多约束条件,适合大规模计算。因此，该算法一经提出就倍受推崇且已经成功应用于诸多领域。随着科学技术的发展,人们在路径规划[2]、图像分割[3]、神经网络[4-5]、数据预测[6]、噪声控制[7]等领域面临的优化问题愈发复杂。传统的粒子群优化算法,容易陷入到局部极小点，存在“早熟收敛”现象,且对于高维复杂的多模态函数求解无法满足实际的需求。

为提高算法性能,许多学者提出了不同的改进方法。目前对于算法的改进主要从3个方面进行：

1) 参数设置：如学习因子调整、惯性权重调节、公式调整等。郭巳秋等建立了新的惯性权重调节机制,根据进化中每个粒子的状态调整惯性权重,提高了算法的收敛效率,增强了算法的鲁棒性[8];赵乃刚在二阶震荡粒子群算法的基础上,省略速度更新公式并将迭代公式降为一阶,既保障了算法收敛精度又提升了搜索速度[9]。

2) 将混合策略引入到基本的粒子群优化算法：Mojarrad等为扩大种群多样性，采用混沌映射初始化粒子群优化算法[10];刘召军将自适应混沌列入差分进化算法，进而融合到粒子群优化算法中、搜索能力和算法的求解精度及效率[11]。

3) 将其他的智能优化算法与标准粒子群优化算法结合：为提高算法的全局寻优能力和收敛速度,Chen等在粒子群算法中引入鱼群算法[12];Garg在粒子群优化算法中融入遗传算法中的选择机制,改进后的算法对高维复杂函数优化问题，寻优效果较为显著[13]。

目前,不同的改进方法对于粒子群优化算法的整体性能在不同程度上均有所提高，但仍未能彻底解决粒子群优化算法对高维复杂函数寻优能力不佳,易陷入局部最优的问题。针对这一问题,本文从引入其他智能算法和混合策略入手,通过引入具有良好全局优化能力、自适应性以及鲁棒性的交叉熵算法,以增强算法的寻优能力。随后，采用粒子重构策略扩大种群的搜索范围,避免早熟收敛。

1 粒子群优化算法

1.1 算法介绍

将鸟群中的每一只鸟抽象为一个“粒子”,位于n维搜索空间中的每个粒子都是潜在的最优解。其中第i个粒子的位置为Xi=(xi1,xi2,…,xin),速度为Vi=(vi1,vi2,…vin)。每个粒子的适应度值都可以用目标函数和粒子位置确定。PSO算法根据粒子自身或者同伴的历史最优位置,通过更新公式迭代调整粒子位置以寻求最优解。Clerc等将压缩因子引入速度更新公式,速度和位置更新公式[14]为

(1)

(2)

式(1)、(2)中：Pb和Gb分别表示当前个体最优位置和全局最优位置;w是惯性权重;r1,r2是区间[0,1]的随机数,用于维持种群多样性;c1,c2是学习因子,分别代表认知因子和社会因子;K表示压缩因子,通常取0.729。

1.2 参数调整

惯性权重用于衡量粒子的上一迭代速度对当前速度的影响。选择了Chatterjee等提出的惯性权重非线性递减策略[15],并指出m=1.2时算法性能最优,其中w表示为

(3)

式中：wmin为最小值，通常取0.4；wmax为最大值，通常取0.9；T为最大迭代次数；t表示当前迭代次数；m是幂级数。

学习因子是体现粒子学习能力的参数,分别表示粒子向个体与全局历史最优位置的学习能力。张健等提出一种结合惯性权重递减与约束因子方法的PSO算法[16],在假设c1=c2的前提下，提出c1,c2取值随惯性权重变化而变化的函数式。结合文献[14]对因子取值的建议，即(c1+c2)/2=1.494 45,将学习因子调整为

(4)

1.3 粒子重构

1.3.1 替换概率 粒子重构通过以一定概率替换进化能力较弱的粒子实现,替换概率是衡量进化能力弱的粒子是否被替换的标准。采用粒子适应度值的好坏度量替换概率,如式(5)所示:

(5)

1.3.2 重构流程 在算法进化过程中,粒子的进化能力各不相同。选择进化能力较好的粒子,根据式(6)对其添加高斯扰动生成新粒子：

(6)

采用高斯扰动后的位置作为替换目标进行粒子重构,以避免迭代后期种群多样性降低而导致早熟收敛。粒子重构的基本步骤如下:

1) 排序。计算每个粒子对应的适应度值并得到适应度值序列,将该序列中的元素从小到大排序得到新的矩阵序列。

2) 选择。计算该序列的(1-q)分位数,分位数之前的p个粒子为进化能力强的粒子,末尾的p1(其中p1=N-p)个进化能力较弱的粒子为待替换的粒子。

3) 替换。在第t次迭代中,依次对进化能力较弱的p1个粒子进行替换。根据式(5)计算第i个粒子的替换概率,并根据式(6)对该粒子的各个维度进行替换,生成新的粒子。

4) 合并。将新生成的粒子与进化能力较强p个的粒子合并,构成新的粒子。

2 交叉熵算法

交叉熵(cross entropy,CE)方法[18-19]是1997年由 Rubinstein等提出的一种可靠性分析与随机优化设计的统一方法,其本质是将最优化问题转化为某一小概率事件估计问题。

设χ上的一个概率密度函数族为{h(..,v),v∈ν},将最小化问题转化为研究f(x)比给定实数γ小的概率问题,即

l=Pu(f(x)≤γ)=Eu(I{f(x)≤γ})

(7)

设X是依据概率密度h(..;u)产生的随机样本,Eu表示相应的期望。通过构造参数序列{vt,t≥0}和级别序列{γt,t≥0},同时更新迭代vt,γt,基本步骤如下:

2) 设置参数。包括设置最大迭代次数T、随机样本个数N、分位数系数ρ0、平滑常数β,初始迭代次数t=0。

4) 排序。计算每个样本对应的适应度值并得到适应度函数值序列；将该序列中的元素从小到大排序,得到新的矩阵序列；计算该序列的(1-ρ0)分位数γt。

(8)

式中：L=1，2，…,n。

6) 平滑。

μL=βμL,t+(1-β)μL,t-1

7) 停止。满足到达最大迭代次数后停止迭代,否则返回重新执行1)～6)。

3 改进的粒子群优化算法

基于交叉熵的粒子群优化算法,基本执行过程为：在每次迭代中先用交叉熵算法产生全局最优的替代值,然后引入粒子重构策略,通过替换进化能力弱的粒子构造新的粒子。基本流程如图1所示。

图 1 CEPSO算法流程图

1) 随机产生初值,设置参数，初始化参数w,c1,c2，T,N,n等。

2) 计算初始种群每一个维度的均值、方差作为交叉熵算法的初始参数。

5) 选择适应度值差的粒子进行重构。

6) 根据式(1)和(2)更新粒子的速度与位置。

7) 根据式(3)、(4)更新粒子i在第t+1代的惯性权重及学习因子。

8) 如果达到最大迭代次数,立即停止迭代并输出最优解,否则返回3)。

4 仿真实验

为了验证CEPSO算法的性能,选取了8个标准测试函数[20],对本文算法(CEPSO)、粒子群优化算法(PSO)、基于模拟退火的粒子群优化算法(SAPSO)、改进的粒子群优化目标跟踪算法(OTPSO)、采用粒子群优化的自适应样条拟合算法(SPSO)等5种算法进行仿真对比。

4.1 参数设置

算法的参数均依据原始参数设置,5种算法的参数设置如表1所示。本次实验对5个算法设置相同的种群规模和最大迭代次数,以确保实验结果的有效性。在SPSO算法中c表示学习因子,w表示速度惯性,k表示除自身之外的邻域个数。

表 1 参数设置

4.2 测试函数

选取了表2所示的8个不同标准测试函数。为验证算法对复杂多模态函数的求解能力,选取了5个高维多峰函数F1～F5,用于测试算法跳出局部最优值的能力；3个高维单峰函数F6～F8，用于检测算法收敛性能。

表 2 测试函数

4.3 结果分析

采用8种标准测试函数对5种算法的收敛速度和收敛精度进行测试。为避免算法的随机性对分析结果造成影响,每种算法均独立运行50次,结果如表3所示。表3中最优(差)解、平均值、标准差分别反应算法解的质量,整体水平以及鲁棒性。

表 3 算法运行结果

从表3可以看出:对函数F1～F4,CEPSO算法均找到了真实最优值且鲁棒性强;对函数F5～F8,CEPSO算法求解精度比其他几个算法提高了几十个数量级。对于高维多峰函数F1、F3,SPSO、CEPSO算法在收敛精度上有显著优势；但对于函数F2、F4、F5,SPSO算法收敛过早,而CEPSO算法始终保持着最高的收敛精度。说明改进后算法可以有效提高算法收敛精度,增强算法对高维复杂函数的求解能力。

图2～9是5种算法针对不同测试函数的迭代曲线图。

图 2 F1迭代曲线

图 3 F2迭代曲线

图 4 F3迭代曲线

图 5 F4迭代曲线

图 6 F5迭代曲线

图 7 F6迭代曲线 Fig.7 Iterative curves of F6

图 8 F7迭代曲线

图 9 F8迭代曲线

从图2～4可以看出,对于高维多峰函数F1～F3,在进化初期CEPSO算法的个体质量不如其他算法。但是，随着迭代次数不断增加,PSO、SAPSO、OTPSO等算法都陷入局部最优值,而SPSO算法迅速找到了全局最优值,随后CEPSO算法也收敛到全局最优值。特别是在图4中，2种算法几乎同时找到最优值。从图5、6可以看出,对于高维多峰函数F4、F5,SPSO算法前期收敛速度快,但与其他算法一样都陷入局部最优值,收敛精度不高,CEPSO算法在兼顾收敛速度的同时最先找到全局最优值。从图7～9可以看出,对于高维单峰函数F6～F8,CEPSO算法最先收敛到最优值,在收敛速度和收敛精度上都有显著优势。由此可见，改进的算法在保障收敛速度的同时能收敛到全局最优值,在高维多峰函数的求解中更具优势。

5 结 语

将交叉熵算法与粒子群优化算法结合,同时对进化过程中的粒子进行重构,拓宽了种群的搜索范围,提高了CEPSO算法的收敛性能,使得算法能更高效地找到全局最优点。仿真实验表明,改进后的算法在寻优精度和寻优速度方面均有明显提升,对于复杂多模态函数效果尤为显著。由此可见,将交叉熵算法引入粒子群优化算法，是一种有效的算法改进途径。下一步将研究 CEPSO算法与其他优化算法的比较,并进一步研究其在多目标规划问题中的应用。