混合遗传算法的最优通信频率分配研究

刘 斌 张承江

(常州信息职业技术学院 江苏常州 213164)

0 引言

随着移动通信的迅速发展，飞速增长的用户数量与有限的频率资源这两者之间的矛盾越来越突出，提高现有资源利用率已成为移动通信领域关注的重要课题。所谓“信道分配”，也称频率分配，即在采用信道利用技术的蜂窝移动通信系统中，在多信道共用的情况下，使通信过程中的相互干扰减到最小，以最有效的频谱利用方式，为每个小区的移动通信设备提供尽可能多的可用信道。

笔者针对由此问题转化而成的最优数字分配进行研究，考虑移动通信中主要的几种干扰，转化为对数字分配附加一些约束条件:

①每个存储单元内的整数不能相同且不能相邻。

②每个存储单元与相邻的存储单元内的整数不能相同且不能相邻。

③每个存储单元与相邻存储单元的相邻存储单元内的整数不能相同。

1 遗传算法

目前已有多种算法被应用到此问题中，早期主要是用着色算法进行分配，近些年国内外提出的优化算法有:蛙跳算法、神经网络算法、模拟退火算法、粒子群优化算法和遗传算法等［1］。笔者用一种改进的贪心遗传算法对分配问题进行研究。

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

常规的遗传算法存在搜索空间太大，收敛速度慢以及易于陷入局部最优解的缺点［2］。针对这些缺点通过贪心算法与遗传算法的结合，引入初始基因为较优质基因的竞争，既加快了算法的收敛速度又能适当避免算法陷入局部最优解。同时加入了大规模基因突变的优化方法，可以很好地防止算法陷入局部最优解情况的发生。

2 算法描述

该算法采用50*50矩阵存储通信基站，其中每个基站允许分配2～5个频率，用1～30的整数表示。算法的目的是使用最优分配算法在规定时间内将数据分配到各个存储单元中。

2.1 定义全局数据结构

2.2 算法流程图

运行流程图如图1所示。

2.3 遗传算法实现

一般遗传算法主要包含初始化、选择、交叉、变异等算子，下面对各遗传算子进行设计。

图1 遗传算法流程图

2.3.1 产生初始种群

遗传算法初始种群的产生最基本也是最常用的方法是随机生成法，用这种方法生成初始种群简单快捷，但平均适应度与最佳个体适应度都较差，需要较长时间与较多代数完成收敛。为了解决这个问题，在保证搜索空间完备性的基础上产生高适应度的初始群体，笔者设计了一种“寻优式贪心”算法。核心代码如下:

2.3.2 选择

根据适应度，选择适应度最大的两个个体。为了防止在选择以及其后的交叉、变异过程中最佳个体意外丢失，笔者在每代遗传操作前将最佳个体保留，操作结束后将其直接复制，替换子代种群中的最差个体。另外，为了防止优秀个体迅速繁殖，陷入局部最优解，在选择时要控制最优个体的数量［3］。核心代码如下:

2.3.3 交叉

交叉操作在两个个体中执行，笔者采用一种全新的交叉思想:适应度与小区交叉相结合。其基本方法如下:选择个体进行交叉部分(将进行交叉的小区)，比较这两部分在各自个体中适应度的大小，选取适应度大的部分放入新的个体中的对应区域。最终生成一个新的个体。核心代码如下:

2.3.4 变异算子

交叉算子只是对原有的基因进行重组来产生新的个体，通过交叉并不能产生初始种群以外的基因，而必须靠变异算子来生成新的基因，使遗传算法能够在整个解空间上进行全局搜索。核心代码如下:

3 运行结果与分析

3.1 数据的读取与种群的初始化

读取初始数据，完成基因种群的初始化。输出所有初始染色体的违约分值，如图2所示。

图2 数据初始化

3.2 中间运行结果

中间进行若干代的种群进化(建议100次)，每次算法会计算当前所有染色体的违约分值。可以通过观察看到随着迭代次数的增加，违约分值逐步降低，如图3所示。

图3 第一次迭代的违约分值

3.3 最终结果

当进化结束后，算法输出当前最优解及算法实际运行时间(如图4所示)。理论上随着迭代次数的增加，最终结果会更接近与最优解，实际执行中取决于实际问题的允许响应时间。

图4 最终的结果与用时

4 结束语

高速有效的分配有限的通信频率是典型的TSP问题，对于这类问题当问题规模扩大时，只能求其近似最优解而几乎得不到真正的最优解。此算法实现了在规定时间内求得近似最优解并将结果保存至最终报表。

［1］冯志强.基于改进并行遗传算法的蜂窝网络信道分配［J］.计算机工程与应用，2014，50(3):89-92.

［2］孟祥龙.基于改进混合遗传算法的信道分配研究［J］.现代电子技术，2008(5):57-60.

［3］靳飞.基于局部搜索技术的混合遗传算法［J］.辽宁工程技术大学学报:自然科学版，2013(2):269-272.