基于混合粒子群优化的频率指配方法研究

薛寒+刘培国+黄纪军

摘 要： 建立适用于频率指配问题的数学模型，将电磁兼容性分析的各类因素转化为约束条件，使得电磁兼容问题可以被定量描述，并在此基础上构建了代价函数。采用粒子群优化算法来解决频率指配的问题，在算法的迭代过程中引入了遗传算法思想，加入了自然选择和杂交的手段。仿真证明算法能够达到较快的收敛速度，并有一定的避免陷入局部最优的能力。

关键词： 频率指配模型； 粒子群优化； 遗传算法； 自然选择

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2015）16?0001?03

Method for frequency assignment based on hybrid particle swarm optimization algorithm

XUE Han1， 2， LIU Peiguo1， HUANG Jijun1

（1. College of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073， China；

2.Unit 63893 of PLA， Luoyang 471003， China）

Abstract： A mathematical model suitable for frequency assignment is built in this paper， in which certain factors affecting the electromagnetic environment are transformed to the constraints， and then the cost function is constructed， to make the electromagnetic environment to be described quantitatively. Hybrid particle swarm optimization algorithm is used to solve the problem of frequency assignment， in which the thought of genetic algorithm is introduced， and natural selection and hybridization means are added in the iterative process. The simulation results indicate that the algorithm converges quickly and has a certain capability to avoid its falling into local optimum.

Keywords： frequency assignment model； particle swarm optimization； genetic algorithm； natural selection

0 引 言

在现代战争中，制信息权已和制空权、制海权一样成为获取战场主动权的决定要素之一，而灵活高效的电磁频谱管理，可以在争夺制信息权过程中发挥至关重要的作用。频率指配（Frequency Assignment）是给无线电设备指定具体的使用频率的过程，是电磁频谱管理的重要内容和最终体现[1] ，频谱管理的目标是从频域、时域、空域和能域上实现电子信息系统内的所有设备都可兼容使用。在现今的信息对抗训练场上，合理高效的频率指配方案可以极大地提高训练效果，更高效地提升信息作战部队的战斗力。

频率指配的技术目前已成为国内外研究的重点之一 [2]，对于使用各类优化算法来解决频率指配问题也有了很多的研究成果[3]。本文拟从频率指配问题模型的建立和混合了遗传算法思想的粒子群优化算法研究两方面来探讨频率指配的问题，探讨算法的改进方法，以解决实际问题[4?5]。

1 频率指配问题模型

建立频率指配问题的数学模型，要充分考虑设备参数、电波传播、地形等因素，参考实际的硬性约束如需优先确保用频的装备等，来进行电磁兼容性分析，将分析结果转化为数值约束条件，形成适用于优化算法计算的数学模型。

1.1 约束条件

考虑多种干扰（同频干扰、邻频干扰、互调干扰），分别建立相应的干扰约束矩阵，用矩阵中的元素代表其行列所代表的设备间的两两约束关系，这样可以建立同频干扰约束矩阵A、邻频干扰约束矩阵B、互调干扰约束矩阵C。假设A中某元素aij为1，表示设备i和j不能指配相同频率；反之若元素aij为0，则表示设备i和j没有此约束关系。而模型中的各种约束关系的获得，便需要综合考虑各类因素进行电磁兼容性分析得到。约束矩阵的密度（即其中非零元素的多少）可以表示网络的复杂度，非零元素越多，代表网络各台站间约束关系越多，电磁环境越恶劣。

对于同频干扰，表明一对用频设备间除非有足够的间距或者有合适的地形因素，否则不能指配相同的频率。具体讲，如果f（i）和f（j）分别表示指配给设备i和j（i≠j）的频率，那么可以用f（i）-f（j）≠0来表示他们的同频干扰约束关系。同频干扰矩阵A为N×N的矩阵，N为设备数，若aij为1则代表设备i和j有同频干扰约束，需要满足f（i）-f（j）≠0才可以[6]。

对于邻频干扰，与同频干扰类似，表明一对设备在一定的因素下不能指配相邻的频率。同样用f（i）和f（j）分别表示指配给设备i和j（i≠j）的频率，那么约束关系变为[fi-fj]≥m，其中m是邻频干扰的约束频率间隔，邻频干扰矩阵B也为N×N的矩阵，若bij为1则代表设备i和j有邻频干扰约束，需要满足[fi-fj]≥m。

对于互调干扰，矩阵的维数要高一些，因为条件中同时涉及的频率不止2个。例如三阶Ⅰ型互调，其约束条件为2 f（i）-f（j）≠f（m），相应的矩阵C变为三维；又如三阶Ⅱ型互调，其约束条件为f（i）+f（j）-f（m）≠f（n），相应的矩阵C变为四维。

1.2 代价函数

结合约束矩阵和同频、邻频、互调的约束条件，设α，β，γ为分别为同频干扰、邻频干扰、互调干扰的惩罚因子，即各种干扰的权值。用E（s）表示指配方案s的干扰代价，那么可以得出：[E（s）=αi=1Nj=i+1Naij+βi=1Nj=i+1Nbij+ γi=1Nj=1Nm=1Nn=1Ncijmn-i=1Nm=1Nciimm] （1）

事实上，式（1）代表的便是在指配方案s下违反同频、邻频、互调3种约束条件的代价函数的加权和。

2 基于混合粒子群优化的指配算法

2.1 基于遗传的混合粒子群优化算法

粒子群优化算法（Particle Swarm Optimization， PSO）是一种进化计算技术，由Eberhart博士和Kennedy博士发明，源于对鸟群捕食的行为研究。PSO算法首先初始化一群随机粒子，粒子们追随当前的最优粒子在解空间中进行搜索，通过迭代获得最优解[7]。

设d维空间中粒子i的位置和速度为Xi=（xi，1，xi，2，…，xi，d）和Vi=（vi，1，vi，2，…，vi，d）在每一次迭代中，粒子依据粒子本身所找到的最优解pbest，Pi=（pi，1，pi，2，…，pi，d）以及整个种群目前的全局最优解gbest，Pg来更新自己的速度和位置，更新公式如下：

[vi，j（t+1）=wvi，j（t）+c1r1pi，j-xi，j（t）+c2r2pg，j-xi，j（t）] （2）

[xi，j（t+1）=xi，j（t）+vi，j（t+1）， i，j=1，2，…，d] （3）

式中：w为惯性权重；c1和c2为正的学习因子；r1和r2为（0，1）均匀分布的随机值。算法性能在很大程度上取决于算法的控制参数如粒子数、最大速度、学习因子、惯性权重等，参数的选择依据实际问题来灵活决定。

混合粒子群算法指的是借鉴其他一些智能优化算法思想而形成的粒子群算法，比如应用比较广泛的模拟退火、遗传、神经网络以及蚁群等智能算法，每种智能算法都有其特色和优点，因而就形成了各类改进的混合智能算法[8]。

本文中借鉴遗传算法中的选择机制，可以在每次迭代中，用群体中较好的部分粒子替换较差的部分粒子，这样可以提高算法收敛的效率，同时为了避免陷入局部最优，借鉴遗传算法中的杂交概念，选取指定数量的粒子放入杂交池内，池中粒子两两随机杂交产生子代（child）粒子，用子代粒子替换亲代（parent）粒子。子代的位置由亲代位置进行交叉得到：

[childx=p?parent1x+1-p?parent2x] （4）

或者：

[childx=1-p?parent1x+p?parent2x] （5）

式中p为（0，1）范围的随机数。

子代的速度由下式得到：

[childv=parent1v+parent2vparent1v+parent2vparent1v] （6）

或者

[childv=parent1v+parent2vparent1v+parent2vparent2v] （7）

2.2 基于遗传的混合粒子群优化的频率指配

2.2.1 粒子编码

本文中使用整数方式对频率进行编码，将所有可用频点按照频率值由小到大的顺序进行整数编号。假设地域内有用频设备N台，每一个用频设备i的频率为正整数fi（i=1，2，…，N），他们的可用频率范围形成N个整数子集。每一个指配方案f=（f1，f2，…，fN）表示为一个正整数序列。例如，可用的频点为30个，编号1～30，地域内用频设备5台，指配方案f=（4，9，14，25，3）就表示编号为1～5的用频设备分别被指配了编号4，9，14，25，3的频率点。算法中可以将一个指配方案看作一个粒子，这样的编码方式一来清晰易于理解，二来解码非常方便。

2.2.2 适应度函数

本文设计的算法在编程中是以适应度函数Fitness（x）的最小值为优化目标的，因而适应度函数的设置可以直接使用第1节所建立问题模型中的代价函数，即有：

[Fitness（x）=αi=1Nj=i+1Naij+βi=1Nj=i+1Nbij+ γi=1Nj=1Nm=1Nn=1Ncijmn-i=1Nm=1Nciimm] （8）

式中：自变量x（向量）即表示一种指配方案f；x[i]代表给设备i所指配的编码后频率。

2.2.3 算法初始化

基本粒子群算法中粒子的初始位置和速度是随机生成的，也即是在可用频率子集内随机抽取。为了使算法在初始阶段的适应度函数尽可能的最优，应使粒子群在初始阶段尽可能地分散，同时也可以尽可能地消除确保在初始阶段各个用频设备的同频冲突和邻频冲突。这样可以大大加快在算法开始阶段的收敛速度。

2.2.4 粒子群更新

按照基本粒子群优化算法的原理，评价完成每个粒子的适应度之后，将当前各粒子的位置和适应度存储在各自的pbest中，将所有的pbest中适应度最优的个体位置和适应度存储在gbest中。按照式（2）和式（3）更新粒子速度与位置后，对于每个粒子将其适应值与其经历过的最好位置作比较，并更新当前最好位置，接着比较当前所有pbest与gbest的至，更新gbest。

根据2.1中引入遗传算法自然选择的机理，在每次粒子迭代过程中，将整个粒子群按照适应值进行排序，用群体中最好的一半粒子替换最差的一半的位置和速度，同时保留原来每个个体所记忆的历史最优值；而为防止算法陷入局部最优，按照杂交的概率选取粒子进入杂交池，杂交池中的亲代（parent）粒子根据式（4）和式（5）进行交叉获得子代粒子的位置，根据式（6）和式（7）交叉获得子代粒子的速度，并替换亲代中的父代（parent1）粒子。

3 仿真实验与结果分析

算法采用64位的Matlab编程实现，系统环境为64位Windows 8.1操作系统。仿真实验中设备数量设为6台，频率设为12个。也即是自变量个数设为6，可用频率值为1～12的整数。粒子个数设为20，惯性权重取0.7，学习因子取2，杂交池大小比例为0.2，杂交概率取0.9。一般情况下3种干扰要素中同频干扰的影响相对较大，因而在仿真中给其更多的关注，这里将同频、邻频、互调干扰的惩罚因子分别取为3，2，1。

为了体现算法的优点，这里同样利用基本粒子群算法，在相同的参数条件下对问题进行了仿真，观察随着迭代次数的增加，代价函数的变化情况，结果如图1所示。

图1 算法仿真结果

图1（a）为基本粒子群优化算法的一次结果，图1（b）为混合粒子群优化算法的一次结果。仿真结果表明在绝大多数情况下，本文所用的算法算法可以在15次迭代以内得到最优结果。与基本粒子群算法相比，收敛性能更优，且具有一定的防止陷入局部最优的能力。

4 结 论

本文针对频率指配问题，进行了适用于优化算法的数学建模，并利用混合的粒子群优化算法对问题进行了求解。在算法设计中，参考遗传算法的自然选择思想和交叉的概念，在基本粒子群算法的迭代过程中加入了粒子群替换和杂交的策略，结合仿真实验证明了本文的优化算法不仅具有较好的收敛性能，而且可以避免计算陷入局部最优。

参考文献

[1] 王先义，陈丹俊，刘斌，等.复杂电磁环境战场频谱管理[J].中国电子科学研究院学报，2008（4）：338?344.

[2] US Department of Defense. Joint Spectrum Vision 2010 [R]. Washington， DC： US Department of Defense， 1999.

[3] 汤毅.频率指配算法的研究与应用[D].长沙：国防科技大学，2008.

[4] 杨奎.一种基于离散粒子群优化的战场动态频谱指配策略[J].电讯技术，2012，52（5）：755?760.

[5] 孙健，刘慧霞，席庆彪.基于改进粒子群算法的多UAV 协同侦察任务规划[J].现代电子技术，2012，35（7）：12?15.

[6] 肖剑.无线电磁频率管理中频率指配技术的研究[D].长沙：中南大学，2012.

[7] 龚纯，王正林.精通Matlab最优化计算[M].北京：电子工业出版社，2014.

[8] 陈自卫，石雄.基于遗传算子的粒子群算法在战场频率分配中的应用[J].舰船电子工程，2010，30（3）：73?76.

[9] 霍元杰.战场频谱态势感知及频谱筹划系统[J].电讯技术，2013，53（10）：1265?1268.

[10] 王新增，刘佳楠，肖金保，等.基于粒子群算法的电磁频率分配方法研究[J].现代电子技术，2013，36（17）：5?8.

[11] 邵立杰.AIS海上电波传播模型研究[D].大连：大连海事大学，2014.