一种基于模因演算法的频率分配新策略

熊 健,喻 歆

(中国西南电子技术研究所, 成都610036)

1 引 言

在现代战争中,无线通信设备能够保证作战信息的有效获取、部队的合成指挥以及部队之间的协同作战。大量的敌我方无线电子设备出现在了现代战场中,再加上民用无线通信设备,使得现代战场中的电磁环境十分复杂[1]。

合理地管理有限的电磁频谱资源有利于指控通信、情报侦察、预警探测、武器制导和导航定位等系统的高效运转[2]。频谱资源管理需要解决的关键问题之一是如何为用频设备分配频谱资源,提高频谱的利用率。为此,本文基于一种模因演算法提出并设计了一种新颖的频率分配策略。

同已被工程实践广泛检验过的遗传算法类似,模因演算法不依赖于具体问题,具有一定的普适性,能够解决具有非线性、非连续、不可导、多目标、多变量、多模态等特征的复杂问题,并且比遗传算法具有更好的求解性能[3]。

模因演算法已被成功应用于规划(如路由和调度)、设计(如工业制造)、模拟和识别、控制,以及分类(如机器学习和模式识别)[4-6]。而在频率分配领域,遗传算法已经获得成功[7-9],这也为将模因演算法应用于求解频率分配问题奠定了基础。于江等人[9]以遗传算法为基础设计了一种战场频率分配算法,但是他们使用的二进制矩阵编码方式不能够较好体现问题本身的特征,而且相对应的遗传算子的设计也没有很好地反映搜索空间的结构特点,因此算法不能保证获得完全没有相互干扰的分配方案。本文采用正整数序列编码方式,并且针对该编码方式和频率分配问题设计了更高效的搜索算子,以期能够获得最优的频率分配方案。

2 模因演算法的基本原理

模因演算法(Memetic Algorithms,MAs)的灵感来自于达尔文进化论以及拉马克进化理论的结合。达尔文进化论的基本遗传单位是基因(Gene),其进化主要发生于生物世界,效果的显现通常需要数代进化的累积,速度较为缓慢;而拉马克进化理论认为生物体可将其获得的经验和知识直接传递给后代,因此显现效果的速度相对较快[10]。拉马克进化理论中传递的基本单位被E.O.Wilson 称为“文化基因”[10],它与R.Dawkins 在The Selfish Gene[11]中提出的“Meme”相仿,类似于遗传算法(Genetic Algorithms,GAs)中的Gene,因此,模因演算法中的基本遗传单位就是Meme。

从算法的角度来看,模因演算法实际就是在遗传算法中融入了局部搜索算子,它结合了遗传算法的全局搜索能力以及局部搜索算子的局部搜索能力,使得算法能够以更大的概率搜索到全局最优解。该算法最早由P.Moscato[3]于1989 年提出,并成功应用于求解TSP 问题[4],且验证了其寻优能力强于遗传算法。模因演算法的流程如图1 所示,其中局部搜索中实际还包含了对种群的评估操作。从该流程图可以发现,模因演算法和遗传算法的区别在于,所有通过遗传算子生成的新个体在被放入种群前都要进行局部搜索,从而完成个体在局部区域的学习过程。

图1 模因演算法的运行流程Fig.1 The flowchart of MA

3 频率分配问题

频率分配问题是指为无线设备的每个收发信道分配频率,并且满足一定的约束条件和需求特性。一般来讲,有两类频率分配问题,第一类称为固定频谱频率分配问题(Fixed Spectrum Frequency Assignment Problem,FS-FAP),即在给定可用频谱范围的基础上,从收发信道之间的干扰程度的角度来尽可能高效地分配频率;第二类称为最小跨度频率分配问题(M inimum Span FAP,MS-FAP),它主要以最小化分配方案中使用的频谱跨度范围为目标(使分配方案中使用的最大与最小频率之间的间隔最小[12])。本文考虑的是最小化干扰程度频率分配问题(Minimum Interference FAP,MI-FAP),它属于FS-FAP,其优化目标是在给定可用频谱范围的基础上最小化收发信道之间的干扰程度。

在求解MI-FAP 时需要考虑3 类电磁兼容约束(Electromagnetic Compatibility Constraints,EMC),即同信道约束(Co-Channel Constraint,CCC)、相邻信道约束(Adjacent-Channel Constraint,ACC)和共址约束(Co-Site Constraint,CSC)[8-9,12]。CCC 是指同一设备的不同信道不能使用相同的频率,且不同设备的信道若不满足设备间的同频复用最小地理间隔距离,也不能使用相同的频率;ACC 是指为避免干扰,两个信道应该间隔的最小频率距离;CSC 是指为了保证同一设备的信道正常工作,该设备的两个信道应该间隔的最小频率距离。

假设一共有n 个无线设备,表示为S =(s1,s2,…,sn),需求向量D =(d1, d2, …, dn),其中di表示设备si的信道数目,可用的频点数目为m ,按照频率大小从低到高排序,并且按序标记为1,2, …,m,则EMC 可以用规模为n×n 的非负矩阵C 表示。矩阵C 的对角线元素cii表示同一设备的任一对信道间的约束,其余元素cij(其中i ≠j)表示设备间任一对信道间的约束。

综上,FS-FAP 由三元组(S , D, C)确定,其中S 表示无线设备,D 表示信道需求,而C 表示EMC矩阵。若用M={1,2, …,m}表示可选用的频点, Ai为M 的子集,表示分配到设备si的频点。求解目标则为找到一种频率分配方案A={A1,A2, …, An},使其满足如下条件:

其中, Ai表示集合Ai中的频点数目。满足上述条件的分配方案称为可行分配方案。

MI-FAP 的优化目标是找到一种相互间干扰程度最小的可行分配方案,优化目标形式化描述如下:

式中, ε(i,k,j,l)非负,其值根据干扰程度来确定,无干扰时取值为零,且

可以看出,当不存在任何干扰时,I =0。

4 基于模因演算法的频率分配策略

4.1 问题描述

本文要解决的频率分配问题以上一节定义的MI-FAP 为基础。此外,除了每个设备都有信道数目的需求外,每个信道还有工作方式(记为方式W1和方式W2)和用途(记为用途U 1和用途U2)的需求之分。如果把一个频道对应一个频率点或者一个频率集合,并且对应一种工作方式和用途,那么,实际要做的工作就是为每个设备每个信道分配一个频道,并且满足电磁兼容约束条件。还需要注意的一个需求条件是每个设备用于U1的信道都使用相同的频道。类似地,我们将可用的频道编号并且依次标记为1,2, …,m。这样,如果把这里的频道对应到MI-FAP 中的频点可以发现,该问题同M I-FAP 实质是相同的,只是除了需要满足上一节提到的3 类约束以外,还需要满足工作方式和用途的约束要求。

4.2 算法设计

4.2.1 编码方式

一个个体用正整数序列表示,代表一种频道分配方案,它通过顺序连接分配给每个设备每个信道的频道号获得。在连接分配给同一设备的信道的频道号的时候按照W1U1频道、W2U 1频道、W1U 2频道和W2U2频道的顺序进行,且需要注意的是每个设备的U1频道都相同。编码方式如图2 所示,其中编码长度为。例如,如果需求向量D=(2,1,3,4),则编码(6,10,6,6,13,8,6,16,27,20)表示频道6、10 分给设备1,频道6 分给设备2,频道6、13、8 分给设备3,频道6、16、27、20 分给设备4。其中每个设备都有频道6,说明需求中要求每个设备都有一个U1用途的信道。

图2 个体编码方式Fig.2 The encoding scheme of an individual

4.2.2 初始化方法

种群中的每一个个体都通过随机的方式生成。根据需求,一个个体的每位数值从相应的频道号范围内随机选取。例如,若第一个设备需要一个W1 U2,以及一个W2U1频道,那么该个体头两位数值就可以分别从W1频道以及W2频道中随机选取,并且将选出的用于U1的频道分配给该个体上对应U1信道的其他所有编码位。若种群规模为N(为方便后面的交叉操作,设定其为偶数),则按上述方式随机生成N 个个体。需要注意的是,我们利用先验知识指导初始化过程,即初始化时保证每个设备分配的频道号各不相同,并且在后面的所有操作中,都要保证满足该要求。此外,在以后的操作中,还需要保证每个设备的U1频道都相同。

4.2.3 适应度评估

评估一个个体适应度时,首先需要根据输入的信道的数目、用途、工作方式需求对个体进行解码,从而获得相对应的分配方案,然后根据实际的信道间干扰规则计算该分配方案的干扰程度,即公式(4)中的I。在计算一对信道间干扰程度ε(i,k,j,l)的时候,我们设定其值为:ε0——无干扰、ε1——轻微干扰、ε2——一般干扰、ε3——较大干扰以及ε4——严重干扰,并且设置ε0=0,ε1=1,ε2=10,ε3=100,ε4=1 000。为了将该问题转换成最大化问题,我们令个体的适应度f 为

其中,正常数G 可以避免分母为零。这样,个体的适应度值越大,则其对应的分配方案的干扰程度就越小,最优值1/G 在无干扰I=0 时取得。

4.2.4 选择操作

本文采用与文献[9]中相同的轮盘赌选择算法。为了保证算法收敛,本文还使用了精英保留策略,即在选择操作进行之前用上一代的最优个体替换待选择种群中的最差个体。

4.2.5 搜索算子

对于选择出来的个体,我们依次按概率对它们进行交叉、变异和局部搜索操作。

4.2.5.1 交叉操作

对于选择出的N 个个体,随机配对,得到N/2 对待交叉个体。对于每一对个体,生成[0,1] 上的随机数r,若r>pc,则直接将该两个个体复制到生成的种群中,否则,进行交叉操作得到两个新个体,并将它们放入生成的种群中,此处pc表示交叉概率。假设待交叉的个体分别为a 和b,则具体操作如下:

(1)复制a 获得副本a′,依次检查a′中的每一位(即i 从1 遍历至个体编码长度),如果第i 位的值a′(i)出现在了b 的第j 位并且i ≠j 时,则交换a′(i)和a′(j)对应的值,且若a′中U1信道编码位发生变化,还需更新a′所有U1信道编码位信息;

(2)复制b 获得副本b′,依次检查b′中的每一位(即i 从1 遍历至个体编码长度),如果第i 位的值b′(i)出现在了a 的第j 位并且i ≠j 时,则交换b′(i)和b′(j)对应的值,且若b′中U1信道编码位发生变化,还需更新b′所有U1信道编码位信息;

(3)按照如下方式生成第一个个体a″:对于a″的每一位a″(i),生成一个[0,1]内的随机数r,若r>0.5,则令a″(i)=a′(i);否则,令a″(i)=b(i);最终a″中U1信道编码位数值以该个体第一个设备的U1信道编码位信息为准进行更新;

(4)按照如下方式生成第二个个体b″:对于b″的每一位b″(i),生成一个[0,1]内的随机数r,若r>0.5,则令b″(i)=b′(i);否则,令b″(i)=a(i);最终b″中U1信道编码位数值以该个体第一个设备的U1信道编码位信息为准进行更新。

a″和b″即为所得的生成个体,按照上述方式对每一对待操作个体交叉得到N 个生成个体。

4.2.5.2 变异操作

对于交叉得到的N 个个体,我们按概率对它们采取变异操作,以期产生新的优良结构。设交叉概率为pm,对于每一个个体,生成[0,1]上的随机数r,若r>pm,则不采取任何操作,否则,对其做如下操作:

(1)随机选择该个体的某一位;

(2)随机选择与步骤1 所选位工作方式(指W1或W2)相同的某一位;

(3)若步骤2 中不存在符合要求的位,同时若步骤1 已经执行了10 次,则变异操作结束;否则,返回步骤1;

(4)若所选两位均为U2频道,则交换两位对应数值,变异操作结束;若所选一位是U1频道,另一位是U2频道,则交换两位对应数值以后,还需更新该个体所有对应U1信道的编码位上的数值,变异操作结束;若所选两位均为U 1频道,变异操作结束。

4.2.5.3 局部搜索

在交叉和变异以后,对得到的N 个个体中适应度排在前10%的个体进行局部搜索, 提高搜索效率,加快找到较优解的进程。具体操作为,对每一个对应的分配方案存在干扰的个体a:

(1)选择a 对应的分配方案中干扰程度最大的一个设备;

(2)随机选择已分配给该设备的一个U2频道,随机选择一个与该频道工作方式相同的频道,且该频道与该设备已有频道均不相同;

(3)评估若用步骤2 中后者频道替换前者频道后该个体的适应度,若适应度增大,则执行此替换操作,并结束对该个体的局部搜索操作;否则,若步骤2 已执行了10 次,则转步骤4,否则,返回步骤2;

(4)随机选择a 对应的分配方案中存在干扰的两个设备,若不存在满足条件的两个设备,则局部搜索结束;

(5)从两个设备中分别随机选择一个U2信道,且选出的两个信道具有相同的工作方式,若不存在满足条件的两个信道,即若步骤4 已执行了10 次,则结束局部搜索,否则,返回步骤4;

(6)评估若交换步骤5 中两个信道对应的频道后个体的适应度,若适应度增大,则执行此交换操作,并结束对该个体的局部搜索操作;否则,若步骤4 已执行了10 次,则结束局部搜索,否则,返回步骤4。

4.2.6 停止条件

按照图1 所示流程,局部搜索中实际上还包含了一次种群的评估操作,这样,完成一次选择、交叉、变异和局部搜索称为一次算法迭代,可以设定算法停止条件为找到了最优分配方案(无干扰)或者已经进行了规定次数的迭代。算法停止时,最后的种群中适应度最大的个体表示的分配方案则为求得的分配方案。

5 仿真分析

5.1 测试问题

测试时,设备数目分别设为10、20、30、40、50 和100,且设备的地理位置随机分布。可分配的频道一共有255 个,它们的工作方式包括W1和W2,已根据一定的算法在规定的频段内生成,而且已经依次从1 至255 编号。每个设备的信道需求统一设定为1个W1U1信道、1 个W2U1信道、1 个W1U2信道以及1个W2U2信道,即每个设备4 个信道。

5.2 参数设置

算法的参数设置为,种群大小N=30,交叉概率pc=0.80,变异概率pm=0.20,适应度常数G=3.0。需要注意的是,这里的参数都是根据经验设定的,针对不同的问题实例,存在最优的参数配置,对于参数的优化将留到后续工作中进行。对于每个问题实例,算法运行10 次,在后面的结果展示中只列出优化效果最好的那次运行得到的分配方案,若有多个方案效果相同,则随机展示一种方案。每次运行时,算法都从不同的随机初始种群开始运行,直到找到无干扰的最优解或者迭代次数达到500 代停止。

算法使用C++编码实现,开发环境为Microsoft Visual Studio 2010 ver10.0.30319.1 RTMRel,平台环境为Windows XP Professional SP 3 操作系统, Intel CoreTM2 Quad CPU Q8400 @2.66 GHz 2.66 GHz 的CPU,以及1.96 GB的内存。

5.3 有效性验证

实验中,我们设计的算法在所有的问题实例上的每次运行都找到了最优解,即没有相互干扰的分配方案。以下针对每个实例只列出某一次运行得到的最终分配方案。

由于空间限制,我们只列出了50 个设备时的最终分配结果,如表1 所示,其中,表的第2、3 列分别表示分配给每个设备的W1和W2工作方式且用于U1用途信道的频道,因此每个设备的该两列结果相同,而后两列则分别表示分配给每个设备的W1和W2工作方式且用于U2用途信道的频道。

从表中的结果可以看到,算法成功找到了满足EMC 的无相互干扰的分配方案,从而验证了算法的有效性。若以算法迭代的次数来衡量找到最优解耗费的时间,则当设备数目分别为10、20、30、40、50 和100时,算法分别迭代了1 次、3 次、8 次、14 次、17 次和93次找到最优解,说明在可用的频道数目一定的情况下,设备数目越多则需要越长的时间找到最优解。

图3 给出了100 个设备时算法当前找到的最优分配方案的干扰程度的演化曲线。从图3 可以发现,算法迭代了39 次就找到了不含严重干扰的分配方案。此外,还可以发现,50 次迭代以前,干扰程度随着搜索的进行迅速降低,这实际是算法的交叉以及变异算子起主要作用的阶段,该阶段的目标是搜索到可能存在最优解的潜在区域。从第50 次迭代开始,干扰程度随着搜索的进行“相对连续地”逐步减小,这是局部搜索算子在已找到的潜在区域内更细致搜索导致的结果。

图3 100 个设备时算法找到的当前最优分配方案的干扰程度随迭代次数的演化曲线Fig.3 The evolutionary curve of the degree of interference of the optimal assignment found so far when there are 100 devices

在表2 中,我们列出了100 个设备时算法某一次运行中,每一次迭代中每一步算子操作消耗的平均CPU 时间以及各操作所占比例。从表2 可以发现,评估每个个体的适应度消耗了最多的时间,其次是局部搜索和交叉操作。仔细分析算法流程可以发现,每个个体上的操作实际上是独立的,而交叉时每一对个体之间的操作也是相互没有影响的,因此,为了缩短算法运行时间,可以考虑将交叉、局部搜索以及评估这三步操作分别并行化。

表2 100 个设备时算法每一次迭代中每一步算子操作消耗的平均时间以及所占比例Table 2 The average CPU time consumed by each operator in one iteration and the time consuming proportion when there are 100 devices

6 结 语

在极其复杂的电磁环境中,如何管理、规划好各用频设备的频率需求已经越发显得重要和关键。本文针对频谱管理中的关键问题之一即频率分配问题展开了研究,基于模因演算法提出并设计了一种用于解决一类实际频率分配问题的新策略。实验结果表明,该策略能够有效求解实际频率分配问题,但是也存在一些地方值得改进。例如,可以通过并行化来缩短每次迭代消耗的CPU 时间,而当需求规模逐步增大时,也可以考虑使用基于合作型协同演化[13]的技术来减少算法找到最优分配方案的迭代次数。

[1] 李楠,张雪飞.战场复杂电磁环境构成分析[ J] .装备环境工程,2008,5(1):16-19.

LI Nan, ZHANG Xue-fei.Constitution Analysis of Comp licated Electromagnetic Environment in Battlefield[ J] .Equipment Environmental Engineering, 2008, 5(1):16 -19.(in Chinese)

[2] 古邦伦.电磁频谱管理中的频率分配技术研究[ D] .长沙:国防科学技术大学,2006:5.

GU Bang-lun.The Research of Frequency Assignment in Frequency Spectrum Management System[D] .Changsha:National University of Defense Technology,2006:5.(in Chinese)

[3] Moscato P.On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts:Towards M emetic Algorithms[R] .Pasadena, CA:CalTech, 1989.

[4] Moscato P, Norman M.A Memetic Approach for the Travelling Salesman Problem:Implementation of a Computational Ecology for Combinatorial Optimization on Message-passing Systems[ J] .Parallel Computing and Transputer Applications,1992, 28(1):177-186.

[5] Ishibuchi H,Yoshida T, Murata T.Balance Between Genetic Search and Local Search in Memetic Algorithms for Mu ltiobjective Permutation Flowshop Schedu ling[ J] .IEEE Transactions on Evolutionary Computation, 2003, 7(2):204-223.

[6] Tang M L,Yao X.A Memetic Algorithm for VLSI Floorplan-ning[ J] .IEEE Transactions on Systems, Man, and Cybernetics, 2007,37(1):62-69.

[ 7] Allen S M, Colombo G.Problem Decomposition for Minimum Interference Frequency Assignment[ C]//Proceedings of the 2007 IEEE Congress on Evolutionary Computation.Piscataway, New Jersey,USA:IEEE,2007:3492-3499.

[ 8] Dorne R, Hao J.An Evolutionary Approach for Frequency Assignment in Cellular Radio Networks[ C]// Proceedings of the 1995 IEEE International Conference on Evolutionary Computation.Piscataway, New Jersey, USA:IEEE, 1995:539-544.

[9] 于江, 张磊, 沈刘平, 等.一种基于遗传算法的战场频率分配方法[ J] .电讯技术,2011, 51(7):90-96.

YU Jiang, ZHANG Lei, SHEN Liu-ping, et al.A Battlefield Frequency Assignment Method Based on Genetic Algorithm[ J] .Telecommunication Engineering, 2011, 51(7):90-96.(in Chinese)

[ 10] Wilson E O.Sociobiology:The New Synthesis[M] .Cambridge,MA:Belknap Press of Harvard University Press,1975.

[ 11] Dawkins R.The Selfish Gene[M] .Oxford:Oxford University Press,1989.

[12] Smith D H, Taplin R K, Hurley S.Frequency Assignment with Complex Co-Site Constraints[ J] .IEEE Transactions on Electromagnetic Compatibility, 2001,43(2):210-218.

[13] 杨振宇.基于自然计算的实值优化算法与应用研究[D] .合肥:中国科学技术大学,2010:4.

YANG Zhen-yu.Nature Inspired Real-Valued Optimization and Applications[ D] .Hefei:University of Science and Technology of China, 2010:4.(in Chinese)